# Generalized Linear Markov Decision Process

arXiv: https://arxiv.org/abs/2506.00818 · HTML: https://mlsanity.com/paper/2506.00818/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 29 of its 39 references that are in the map.
- First posted on arXiv 1 Jun 2025.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 29 of 29)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [A Minimalist Approach to Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06860/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Learning to Drive in a Day](https://mlsanity.com/paper/1807.00412/) (2018)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Top-K Off-Policy Correction for a REINFORCE Recommender System](https://mlsanity.com/paper/1812.02353/) (2018)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Mildly Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.04745/) (2022)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Evaluating Reinforcement Learning Algorithms in Observational Health Settings](https://mlsanity.com/paper/1805.12298/) (2018)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [On the Power of Multitask Representation Learning in Linear MDP](https://mlsanity.com/paper/2106.08053/) (2021)
- [Semi-Supervised Offline Reinforcement Learning with Action-Free Trajectories](https://mlsanity.com/paper/2210.06518/) (2022)
- [Semi-supervised reward learning for offline reinforcement learning](https://mlsanity.com/paper/2012.06899/) (2020)
- [Learning Bellman Complete Representations for Offline Policy Evaluation](https://mlsanity.com/paper/2207.05837/) (2022)
- [Expert-Supervised Reinforcement Learning for Offline Policy Learning and Evaluation](https://mlsanity.com/paper/2006.13189/) (2020)
- [A Deployed Online Reinforcement Learning Algorithm In An Oral Health Clinical Trial](https://mlsanity.com/paper/2409.02069/) (2024)
- [The Provable Benefits of Unsupervised Data Sharing for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.13493/) (2023)
- [Harnessing Causality in Reinforcement Learning With Bagged Decision Times](https://mlsanity.com/paper/2410.14659/) (2024)
- [No-regret Exploration in Contextual Reinforcement Learning](https://mlsanity.com/paper/1903.06187/) (2019)
- [Reinforcement Learning on Dyads to Enhance Medication Adherence](https://mlsanity.com/paper/2502.06835/) (2025)

## Abstract (arXiv)

Offline reinforcement learning for longitudinal studies often faces two linked challenges: rewards may be binary or bounded, and reward observations may be available only for a subset of trajectories or time points even when the corresponding state-action-next-state histories are available. Linear Markov decision process methods are tractable because Bellman backups remain linear, but they require linear rewards and do not indicate how transition-only observations should be used. We introduce GRASP-MDP, Generalized Reward And Semi-supervised Pessimism for Markov Decision Processes, a reward-transition separated framework addressing both issues through one Bellman decomposition. It preserves linear transition dynamics while modeling reward means through generalized linear models. Although this breaks the usual linear Bellman form, the backup remains explicit as a nonlinear reward component plus a linear continuation component, yielding a nonlinear-plus-linear Bellman-complete class. In the resulting recursion, observed rewards estimate the generalized reward component, while all available transitions estimate the continuation component. The resulting pessimistic value iteration controls the two estimation errors separately without reward imputation. Finite-sample guarantees show that transition-only observations reduce transition-estimation error while reward uncertainty remains governed by observed rewards. Simulations and a multiple sclerosis electronic health record application illustrate the empirical benefit of retaining transition-only observations.