REVIEW 3 major objections 4 minor 40 references
Generalized Linear Markov Decision Process
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper extends linear MDPs to generalized-linear rewards while preserving Bellman completeness, and proves pessimistic offline value iteration attains 1/sqrt(n) suboptimality, improved by unlabeled trajectories in the transition term.
desk verdict A clean, useful GLMDP extension of linear MDPs with a sensible semi-supervised idea, but the advertised SS-GPEVI rate is not fully supported in v1: the promised relaxation of Assumption 2 is missing and the Corollary 2 bound drops a term present in Theorem 2. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The mechanism is the parametric function class $F$ together with the $\xi$-uncertainty quantifier $\Gamma_h=\Gamma_{r,h}+\Gamma_{p,h}$. $\Gamma_{r,h}$ is a GLM confidence bound built from the derivative-weighted covariance $\Sigma_h(\theta)=\sum_\tau \dot g(\langle\phi_r(x_\tau,a_\tau),\theta\rangle)\phi_r\phi_r^\top$; $\Gamma_{p,h}$ is the standard feature covariance ellipsoid $(\Lambda_h+\lambda I)^{-1}$. The semi-supervised variant feeds both labeled and unlabeled pairs into $\hat\Lambda_h$, so the transition ellipsoid shrinks with $n+N$ while the reward ellipsoid continues to shrink only with $n$.
What would settle it
Build a binary-reward GLMDP with a feature direction that the logging policy rarely observes with both outcomes, and compute $\lambda_{\min}(\Sigma_h(\theta^*_h))$ from the logging distribution. If that minimum is zero or far below the claimed $\rho$, Assumption 2 is violated and the stated $\sqrt{d_r/n}$ reward-error rate has no support; running GPEVI on such an instance and observing $\hat\theta_h$ fail to concentrate at the predicted rate would refute Corollary 1 as stated.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that moving the reward from linear to GLM form does not destroy the property that makes linear-MDP value iteration work. Proposition 1 shows the GLMDP is Bellman complete with respect to $F = \{ (x,a)\mapsto g(\langle\phi_r(x,a),\theta\rangle) + \langle\phi_p(x,a),\beta\rangle\}$, so the optimal Q-function satisfies $Q^*_h(x,a)=g(\langle\phi_r(x,a),\theta^*_h\rangle)+\langle\phi_p(x,a),\beta^*_h\rangle$ with $\beta^*_h=\int_{\mathcal{S}} V^*_{h+1}(x')\,\mu_h(dx')$. The paper then constructs GPEVI and SS-GPEVI, whose pessimism penalty is split into a GLM reward uncertainty $\tilde\Gamma_{r,h}$ and a transition uncertainty $\tilde\Gamma_{p,h}$. The headline rates are $\mathrm{SubOpt}(\tilde\pi;x)\le \tilde O(\sqrt{d_r H^2/n} + \sqrt{(d_p+d_r)^2H^4/n})$ for GPEVI and, for SS-GPEVI, $\tilde O(\sqrt{d_r H^2/n} + \sqrt{(d_p+d_r)^2H^4/(n+N)})$, with the second term strictly improving whenever unlabeled trajectories are available.
Load-bearing premise
The rates stand only if the reward feature covariance under the logging policy, weighted by the link derivative at the true parameter, is uniformly well conditioned (Assumption 2, $\lambda_{\min}(\Sigma_h(\theta^*_h))\ge \rho>0$); with binary rewards and rare outcomes this can fail, and the paper's announced penalty-based relaxation, Theorem J.3 in Appendix J, is not present in this version.
Editorial extensions
If this is right
- In the identity-link case the GLMDP bound reduces to the linear-MDP PEVI rate, so the framework is a strict generalization rather than a separate model.
- SS-GPEVI strictly improves the transition term whenever $N>0$, and when $d_p \gg d_r$ and $N$ is large it reaches $\tilde O(\sqrt{d_r H^2/n})$, so unlabeled trajectories substitute for labeled ones in the dynamics component.
- Because transitions are estimated from any state-action-next-state triplets, the algorithm never needs to impute or pseudo-label rewards, removing a common leakage in semi-supervised RL pipelines.
- Bellman completeness over $F$ means standard value-iteration machinery is available, so algorithms built on linear-MDP pessimism can be adapted to GLM rewards without changing their error-propagation arguments.
Reading between the lines
- A practical consequence the authors only hint at is a division of labor: labeling budgets should be spent on reward observations, while unlabeled transition data can be collected at population scale, and the theory predicts the transition error, not the reward error, is what improves with $N$.
- If the same $\Gamma_{r,h},\Gamma_{p,h}$ split were carried into an online learner, exploration bonuses for rewards and transitions could be tuned at different rates, a possible route to regret bounds for GLM rewards that the paper does not explore.
- Because the link function can vary with horizon, the framework is ready-made for mixed-outcome clinical episodes such as continuous vital signs early and binary mortality later; a simulation test on zero-inflated count rewards would be a natural next check.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Generalized Linear MDP (GLMDP), an episodic MDP in which the reward satisfies E[r_h(x,a)] = g(<φ_r(x,a), θ*_h>) for a known link function g, while the transition kernel remains linear in features φ_p(x,a). Proposition 1 shows that GLMDP is Bellman complete with respect to the class F = {g(<φ_r,θ>) + <φ_p,β>}, so the optimal Q-function has the form in Eq. (6). The paper then develops two offline algorithms: GPEVI (Algorithm 1), which uses a pessimism-style uncertainty quantifier Γ~_h = Γ~_{r,h} + Γ~_{p,h}, and SS-GPEVI (Algorithm 2), which estimates the transition component from both labeled and unlabeled trajectories. The main theoretical claims are suboptimality bounds of O(sqrt(d_r H^2 log(H/ξ)/n)) + O(sqrt((d_p+d_r)^2 H^4 log(...)/n)) for GPEVI and a semi-supervised bound with the second term replaced by O(sqrt((d_p+d_r)^2 H^4 log(...)/(n+N))). Simulation studies on logistic and beta regression tasks and a PointMaze experiment are reported.
Significance. If the stated guarantees hold, the paper extends the linear MDP framework to nonlinear and discrete rewards in a principled way, and the semi-supervised SS-GPEVI variant offers a useful modular way to exploit unlabeled state-action-next-state data. Proposition 1 is correct and elementary, and the overall pessimistic value iteration strategy follows a well-established template. The semi-supervised decomposition of the uncertainty into a reward part that depends only on labeled data and a transition part that benefits from unlabeled data is a genuine conceptual contribution. However, in the submitted v1 the central discrete-reward claims are not fully supported: Assumption 2 is load-bearing for the reward uncertainty quantifier, yet its promised relaxation is relegated to a missing Appendix J, and Corollary 2 drops a term present in Theorem 2 without an explicit dominance argument. Once these gaps are addressed, the contribution should be a solid theoretical extension of offline RL.
major comments (3)
- [Section 7; Appendix J (missing)] The paper states in Section 7 that Assumption 2 can be relaxed by introducing an ℓ2-penalty term and formalizes this in 'Theorem J.3 in Appendix J', but Appendix J is not present in arXiv v1. Since Assumption 2 (λmin(Σ_h(θ*_h)) ≥ ρ) is the only condition in the submitted text that justifies the reward uncertainty quantifier Γ~_{r,h} in Eq. (10) and hence the O(sqrt(d_r/n)) terms in Corollaries 1 and 2, and since binary logistic rewards can violate this condition when the logging policy produces near-deterministic outcomes in some feature directions, the advertised discrete-reward guarantee is not established in the visible text. The missing relaxation is load-bearing rather than cosmetic.
- [Theorem 2 and Corollary 2] Theorem 2 states SubOpt(π^;x) ≤ Σ_h E_{π*}[Γ~_{r,h} + 2Γ^_h] + Σ_h E_{π^}[Δ_err] with Δ_err = Õ(d_r^{3/4}/n^{3/4}), but Corollary 2 claims only the two O-terms and does not mention Δ_err or give a condition under which it is absorbed. At minimum, a dominance argument is needed, e.g., a condition such as d_r^{3/4}/n^{3/4} ≤ c sqrt(d_r H^2/n) when H is sufficiently large, and the paper provides no such argument. As written, the advertised semi-supervised rate does not follow directly from the stated theorem.
- [Section 5.2 and Figure 3] The empirical comparison for SS-GPEVI is informative, but the paper does not verify the key theoretical prediction that the transition term benefits specifically from unlabeled data in the regime d_p ≫ d_r. In both the synthetic semi-supervised experiments and the PointMaze study, the state dimensions are small and d_p = d_r, so the experiments do not exercise the regime in which the semi-supervised gain is claimed to be largest. A sentence acknowledging this would improve the interpretation.
minor comments (4)
- [Section 3.2] The unlabeled dataset Du is written as {(x^τ_h, a^τ_h)}_{τ=n+1}^{n+N, h=1}^H, but Eq. (11) uses x^τ_{h+1}; unlabeled trajectories must include next-states for the transition estimate to be defined, and this should be stated explicitly.
- [Section 3.1, Eq. (7)] The loss L_h(θ) is described as arising from the negative log-likelihood of a GLM with canonical link. For a non-canonical link, such as the logit link in the beta-regression experiments, this loss is a quasi-likelihood rather than the actual negative log-likelihood; the wording should be corrected or the assumptions on the noise model should be stated.
- [Section 5.1, Eq. (13)] The rejection sampling acceptance probability in Eq. (13) is notationally ambiguous: the denominator 'Σ x_{h+1}·(a_h+1)+a_h' mixes a sum over entries of a state vector with a vector expression, and the formula should be rewritten with explicit parentheses and definitions.
- [Appendix A] In the paragraph following Eq. (A.3), the text writes 'Γ^h_nrm = Γ^h / g_max' in one place and '/ (g_max - g_min)' in another; this appears to be a typo since the definition above uses the denominator g_max - g_min.
Circularity Check
No load-bearing circularity: Bellman completeness is a direct consequence of the GLMDP definitions, and the suboptimality rates follow from standard pessimism and concentration arguments rather than from fitted values or self-citations.
full rationale
The derivation chain is self-contained. Proposition 1 is a direct calculation from the two structural equations (1) and (2): for any value function V, (B_h V)(x,a) = g(<phi_r(x,a), theta*_h>) + <phi_p(x,a), integral V dmu_h>, so the optimal Q-function lies in the class F. No fitted parameter, subset prediction, or author-imported uniqueness theorem is used to obtain this. GPEVI and SS-GPEVI estimate theta*_h by the GLM likelihood (7) and beta*_h by ridge regression (8)/(11), and Theorems 1-2 bound suboptimality by the uncertainty terms (10)/(12); Corollaries 1-2 then specialize those bounds under Assumptions 1-2 and the eigenvalue lower bounds. The rates are not defined as functions of the same fitted values used to report them, and no quantity is fit to one subset and then announced as a prediction on an adjacent subset. The only self-citations (Zhou et al. 2024, Xu et al. 2025, Sonabend et al. 2020) appear in motivating examples and related work, not as load-bearing support for the technical claims. Section 7 states that Assumption 2 can be relaxed via an l2-penalized estimator formalized as Theorem J.3 in Appendix J, but that appendix is not present in the submitted v1; this is a missing-support or completeness issue for the advertised relaxation, not a circular reduction, so it does not raise the circularity score. The Bellman completeness claim is proven from the model definition, and the suboptimality theorems are derived from explicit uncertainty quantifiers and concentration inequalities, so the paper does not reduce its advertised results to its inputs.
Assumptions & free parameters
free parameters (2)
- Confidence constants c_r and c_p =
Absolute constants; in simulations a single c is tuned from {0.005, 0.001, 0.0005, 0.0001} via 5-fold CV
- Regularization lambda =
1
assumptions (6)
- domain assumption Known feature maps phi_r and phi_p and known link function g
- domain assumption Assumption 1: gdot is L-Lipschitz and |gddot| <= gdot
- domain assumption Assumption 2: lambda_min(Sigma_h(theta*_h)) >= rho > 0
- domain assumption Bounded features: ||phi_r||_2, ||phi_p||_2 <= 1 and |||mu_h(S)||| <= sqrt(d_p)
- domain assumption lambda_min(Lambda_h) > 0 for the transition feature covariance
- domain assumption Bounded rewards r_h in [0,1]
Cite this review
Pith. "Pith review of Generalized Linear Markov Decision Process." pith.science (2026). https://pith.science/paper/K7J65GQM
@misc{pith2026250600818,
author = {Pith},
title = {Pith review of: Generalized Linear Markov Decision Process},
year = {2026},
howpublished = {\url{https://pith.science/paper/K7J65GQM}},
note = {Machine review of arXiv:2506.00818}
}
read the original abstract
The linear Markov Decision Process (MDP) framework offers a principled foundation for reinforcement learning (RL) with strong theoretical guarantees and sample efficiency. However, its restrictive assumption-that both transition dynamics and reward functions are linear in the same feature space-limits its applicability in real-world domains, where rewards often exhibit nonlinear or discrete structures. Motivated by applications such as healthcare and e-commerce, where data is scarce and reward signals can be binary or count-valued, we propose the Generalized Linear MDP (GLMDP) framework-an extension of the linear MDP framework-that models rewards using generalized linear models (GLMs) while maintaining linear transition dynamics. We establish the Bellman completeness of GLMDPs with respect to a new function class that accommodates nonlinear rewards and develop two offline RL algorithms: Generalized Pessimistic Value Iteration (GPEVI) and a semi-supervised variant (SS-GPEVI) that utilizes both labeled and unlabeled trajectories. Our algorithms achieve theoretical guarantees on policy suboptimality and demonstrate improved sample efficiency in settings where reward labels are expensive or limited.
Figures
Reference graph
Works this paper leans on
-
[1]
Berner, C., G. Brockman, B. Chan, V. Cheung, P. D e biak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, et al. (2019). Dota 2 with large scale deep reinforcement learning
work page 2019
-
[2]
Cai, Q., A. Filos-Ratsikas, P. Tang, and Y. Zhang (2018). Reinforcement mechanism design for e-commerce. In Proceedings of the 2018 World Wide Web Conference , pp.\ 1339--1348
work page 2018
-
[3]
Chang, J., K. Wang, N. Kallus, and W. Sun (2022). Learning bellman complete representations for offline policy evaluation. In International Conference on Machine Learning , pp.\ 2938--2971. PMLR
work page 2022
- [4]
-
[5]
Du, S. S., Y. Luo, R. Wang, and H. Zhang (2019). Provably efficient q-learning with function approximation via distribution shift error checking oracle
work page 2019
-
[6]
Duan, Y., Z. Jia, and M. Wang (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning , pp.\ 2701--2709. PMLR
work page 2020
- [7]
-
[8]
Fujimoto, S. and S. S. Gu (2021). A minimalist approach to offline reinforcement learning. Advances in Neural Information Processing Systems\/ 34 , 20132--20145
work page 2021
Show all 40 references
-
[9]
Gao, D., H.-Y. Lai, P. Klasnja, and S. A. Murphy (2024). Harnessing causality in reinforcement learning with bagged decision times
2024
-
[10]
Johansson, M
Gottesman, O., F. Johansson, M. Komorowski, A. Faisal, D. Sontag, F. Doshi-Velez, and L. A. Celi (2019). Guidelines for reinforcement learning in healthcare. Nature Medicine\/ 25\/ (1), 16--18
2019
-
[11]
Johansson, J
Gottesman, O., F. Johansson, J. Meier, J. Dent, D. Lee, S. Srinivasan, L. Zhang, Y. Ding, D. Wihl, X. Peng, et al. (2018). Evaluating reinforcement learning algorithms in observational health settings
2018
-
[12]
Hu, H., Y. Yang, Q. Zhao, and C. Zhang (2023). The provable benefits of unsupervised data sharing for offline reinforcement learning
2023
-
[13]
Jin, C., Z. Yang, Z. Wang, and M. I. Jordan (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory , pp.\ 2137--2143. PMLR
2020
-
[14]
Yang, and Z
Jin, Y., Z. Yang, and Z. Wang (2021). Is pessimism provably efficient for offline RL? In International Conference on Machine Learning , pp.\ 5084--5096. PMLR
2021
-
[15]
Hawke, D
Kendall, A., J. Hawke, D. Janz, P. Mazur, D. Reda, J.-M. Allen, V.-D. Lam, A. Bewley, and A. Shah (2019). Learning to drive in a day. In 2019 International Conference on Robotics and Automation (ICRA) , pp.\ 8248--8254. IEEE
2019
-
[16]
Zolna, Y
Konyushkova, K., K. Zolna, Y. Aytar, A. Novikov, S. Reed, S. Cabi, and N. de Freitas (2020). Semi-supervised reward learning for offline reinforcement learning
2020
-
[17]
Kumar, A., A. Zhou, G. Tucker, and S. Levine (2020). Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems\/ 33 , 1179--1191
2020
-
[18]
Kumar, G
Levine, S., A. Kumar, G. Tucker, and J. Fu (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems
2020
-
[19]
Huang, and S
Lu, R., G. Huang, and S. S. Du (2021). On the power of multitask representation learning in linear mdp
2021
-
[20]
Lyu, J., X. Ma, X. Li, and Z. Lu (2022). Mildly conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems\/ 35 , 1711--1724
2022
-
[21]
McCullagh, P. and A. N. John (1989). Generalized Linear Models, Section Edition . Chapman & Hall
1989
-
[22]
Kavukcuoglu, D
Mnih, V., K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. (2015). Human-level control through deep reinforcement learning. Nature\/ 518\/ (7540), 529--533
2015
-
[23]
Modi, A. and A. Tewari (2019). Contextual markov decision processes using generalized linear models
2019
-
[24]
Ostrovskii, D. M. and F. Bach (2021). Finite-sample analysis of M -estimators using self-concordance . Electronic Journal of Statistics\/ 15\/ (1), 326 -- 391
2021
-
[25]
Shakya, A. K., G. Pillai, and S. Chakrabarty (2023). Reinforcement learning algorithms: A brief survey. Expert Systems with Applications\/ 231 , 120495
2023
-
[26]
Huang, C
Silver, D., A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. (2016). Mastering the game of go with deep neural networks and tree search. Nature\/ 529\/ (7587), 484--489
2016
-
[27]
Sonabend, A., J. Lu, L. A. Celi, T. Cai, and P. Szolovits (2020). Expert-supervised reinforcement learning for offline policy learning and evaluation. In Advances in Neural Information Processing Systems , Volume 33, pp.\ 18967--18977
2020
-
[28]
Thomas, P. and E. Brunskill (2016). Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning , pp.\ 2139--2148. PMLR
2016
-
[29]
Trella, A. L., K. W. Zhang, H. Jajal, I. Nahum-Shani, V. Shetty, F. Doshi-Velez, and S. A. Murphy (2025). A deployed online reinforcement learning algorithm in an oral health clinical trial. In Proceedings of the AAAI Conference on Artificial Intelligence , Volume 39, pp.\ 287...
2025
-
[30]
Wang, Y., R. Wang, S. S. Du, and A. Krishnamurthy (2019). Optimism in reinforcement learning with generalized linear function approximation
2019
-
[31]
Cheng, N
Xie, T., C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems\/ 34 , 6683--6694
2021
-
[32]
Xie, T. and N. Jiang (2021). Batch value-function approximation with only realizability. In International Conference on Machine Learning , pp.\ 11404--11413. PMLR
2021
-
[33]
Zhong, C
Xiong, W., H. Zhong, C. Shi, C. Shen, L. Wang, and T. Zhang (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game
2022
-
[34]
Jajal, S
Xu, Z., H. Jajal, S. W. Choi, I. Nahum-Shani, G. Shani, A. M. Psihogios, P.-Y. Hung, and S. Murphy (2025). Reinforcement learning on aya dyads to enhance medication adherence
2025
-
[35]
Yang, L. and M. Wang (2019). Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning , pp.\ 6995--7004. PMLR
2019
-
[36]
Yang, L. and M. Wang (2020). Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning , pp.\ 10746--10756. PMLR
2020
-
[37]
Zanette, A., M. J. Wainwright, and E. Brunskill (2021). Provable benefits of actor-critic methods for offline reinforcement learning. Advances in Neural Information Processing Systems\/ 34 , 13626--13640
2021
-
[38]
Zhang, W., Y. Lin, Y. Liu, H. You, P. Wu, F. Lin, and X. Zhou (2022). Self-supervised reinforcement learning with dual-reward for knowledge-aware recommendation. Applied Soft Computing\/ 131 , 109745
2022
-
[39]
Henaff, B
Zheng, Q., M. Henaff, B. Amos, and A. Grover (2023). Semi-supervised offline reinforcement learning with action-free trajectories. In International Conference on Machine Learning , pp.\ 42339--42362. PMLR
2023
-
[40]
Zhang, A
Zhou, D., Y. Zhang, A. Sonabend-W, Z. Wang, J. Lu, and T. Cai (2024). Federated offline reinforcement learning. Journal of the American Statistical Association\/ 119\/ (548), 3152--3163
2024
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.