📊 statistics

Generalized Linear Markov Decision Process

This paper introduces GRASP-MDP, a novel framework for offline reinforcement learning in longitudinal studies that addresses the challenges of binary/bounded rewards and partial reward observations by separating reward and transition modeling to leverage all available transition data without imputation, thereby providing finite-sample guarantees and improved empirical performance.

Original authors: Sinian Zhang, Kaicheng Zhang, Ziping Xu, Zongqi Xia, Jue Hou, Tianxi Cai, Doudou Zhou

Published 2026-08-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sinian Zhang, Kaicheng Zhang, Ziping Xu, Zongqi Xia, Jue Hou, Tianxi Cai, Doudou Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to navigate a maze. In the ideal world, the robot would get a perfect scorecard after every single move: "You turned left, you found a coin, +10 points!" But in the real world—like in hospitals or on social media apps—things are messier. The robot might see exactly what happened next (it turned left and saw a wall), but the scorecard for that specific move is missing, delayed, or only available for a few lucky turns. This is the challenge of "offline reinforcement learning," where we try to teach AI using old, recorded data instead of letting it learn by trial and error in real-time.

To make this learning possible, scientists often use a mathematical shortcut called a "Linear Markov Decision Process." Think of this as assuming the maze is built with simple, straight lines: if you know the starting point and the direction, you can easily predict the next spot and the points you'll get. This works great if the "points" (rewards) are simple numbers. But what if the reward is something tricky, like a patient's health score that can only go from 0 to 10, or a binary "yes/no" outcome? These rewards don't follow simple straight lines; they curve and bend. Furthermore, if we throw away all the data where the scorecard is missing, we lose valuable information about how the maze is actually laid out. This paper tackles the problem of teaching robots when the rules are curved and the scorecards are incomplete.

The researchers behind this study, led by Sinian Zhang and colleagues, introduce a new method called GRASP-MDP. You can think of this as a clever two-part detective strategy for solving the maze. Instead of trying to guess the missing scorecards (which can lead to bad guesses), GRASP-MDP separates the mystery into two distinct clues: how the world moves and what the reward is.

First, the method looks at the "movement" part. Even if we don't know the score for a specific turn, we might still see the robot move from one spot to another. GRASP-MDP uses all these movement records—whether or not a score was attached—to build a perfect map of the maze. It treats the movement rules as simple and linear, which makes the math easy and reliable.

Second, it tackles the "reward" part. Since rewards like health scores or binary outcomes are curved and complex, the method uses a special tool called a "Generalized Linear Model" to fit the curve. Crucially, it only uses the data where the score was actually recorded to figure out this curve. It doesn't try to invent a score for the missing data; it just admits, "We don't know the score here, but we know exactly how the maze works."

By keeping these two clues separate, GRASP-MDP avoids the trap of guessing wrong scores. It says, "We know the path is clear because we saw the movement, even if we missed the points." The paper proves mathematically that this approach works better than older methods that either ignore the missing data or try to fill in the blanks with assumptions.

To test their idea, the team ran computer simulations with both simple and complex rewards. They found that GRASP-MDP consistently learned better strategies than previous methods, especially when the reward data was incomplete. They also applied it to a real-world medical dataset involving 4,295 patients with multiple sclerosis (MS). In this scenario, the "maze" was the patient's journey through treatment, and the "reward" was their disability score (EDSS), which was only checked at certain visits. The method successfully used the vast amount of treatment history (the movement data) even when the disability scores were missing, to recommend better treatment plans. The results showed that by keeping the "missing score" data for learning the movement rules, the AI could make smarter decisions than if it had thrown that data away.

In short, GRASP-MDP is a smarter way to learn from messy, real-world data. It respects the fact that we often know what happened (the transition) even when we don't know how good it was (the reward), and it uses that knowledge to build better, more reliable decision-making systems without making up fake numbers.

Technical Summary: Generalized Linear Markov Decision Process (GRASP-MDP)

1. Problem Statement

Offline reinforcement learning (RL) for longitudinal studies, particularly in healthcare and digital interventions, faces two interconnected challenges:

Non-Linear Reward Structures: Outcomes are often binary (e.g., relapse) or bounded continuous (e.g., disability scores on a 0–10 scale), which are naturally modeled by Generalized Linear Models (GLMs) rather than the linear reward assumptions standard in Linear Markov Decision Processes (MDPs).
Semi-Supervised Data Scarcity: While state-action-next-state trajectories are often fully recorded, the corresponding reward observations may be available only for a subset of trajectories or specific time points. Existing methods either discard transition-only data (losing information about continuation values) or rely on reward imputation (introducing unverified assumptions).

Standard Linear MDP methods fail here because a nonlinear reward mean breaks the linear Bellman recursion, and existing semi-supervised approaches do not explicitly separate the estimation of transition dynamics from reward modeling.

2. Methodology: GRASP-MDP

The authors propose GRASP-MDP (Generalized Reward And Semi-supervised Pessimism for Markov Decision Processes), a framework that decouples reward and transition estimation while maintaining a tractable Bellman structure.

2.1 Model Assumptions

GRASP-MDP assumes a hybrid structure:

Transition Dynamics: The transition kernel remains linear in a feature map $\phi_p$ :
$P_h(x_{h+1} | x_h, a_h) = \langle \phi_p(x_h, a_h), \mu_h(x_{h+1}) \rangle$
Reward Dynamics: The conditional mean reward follows a Generalized Linear Model (GLM) with a known link function $g$ :
$E[r_h(x_h, a_h) | x_h, a_h] = g(\langle \phi_r(x_h, a_h), \theta^*_h \rangle)$
Here, $\phi_r$ and $\phi_p$ are distinct feature maps, allowing reward-relevant and transition-relevant information to play different statistical roles.

2.2 Nonlinear-Plus-Linear Bellman Completeness

The core theoretical insight is that while the nonlinear reward breaks the standard linear Bellman class, the model induces a nonlinear-plus-linear function class $\mathcal{F}$ :
$f_{\theta, \beta}(x, a) = g(\langle \phi_r(x, a), \theta \rangle) + \langle \phi_p(x, a), \beta \rangle$
The authors prove (Proposition 1) that the Bellman backup of any bounded value function $V$ belongs to this class $\mathcal{F}$ . Specifically, the backup decomposes into a nonlinear reward term and a linear continuation term. This structure allows for explicit Bellman completeness without requiring the reward to be linear.

2.3 Algorithm: Componentwise Pessimistic Value Iteration

The learning procedure utilizes a decomposed pessimistic value iteration (Algorithm 1):

Reward Estimation: The reward parameter $\theta_h$ is estimated using only the subset of data where rewards are observed ( $I^r_h$ ) via a GLM (e.g., binomial or beta regression).
Transition Estimation: The continuation parameter $\beta_h$ is estimated using all available state-action-next-state transitions ( $n + N$ trajectories), regardless of whether the reward was observed. This is done via ridge regression.
Pessimism: The algorithm constructs a pessimistic Q-function by subtracting separate uncertainty radii for the reward and transition components:
$\hat{Q}_h(x, a) = \min \left\{ (\hat{B}_h \hat{V}_{h+1})(x, a) - \hat{\Gamma}_{r,h}(x, a) - \hat{\Gamma}_{p,h}(x, a), H-h+1 \right\}_+$
- $\hat{\Gamma}_{r,h}$ is derived from the GLM curvature and the size of the reward-observed set.
- $\hat{\Gamma}_{p,h}$ is derived from the transition feature covariance and the total number of trajectories.

This approach ensures that transition-only observations reduce transition estimation error without requiring reward imputation.

3. Key Contributions

Theoretical Framework: Establishment of Bellman completeness for a nonlinear-plus-linear function class induced by the reward-transition separation.
Algorithm Development: A componentwise pessimistic value iteration algorithm that separately controls reward and transition uncertainties.
Finite-Sample Guarantees: Theoretical bounds showing that the suboptimality of the learned policy is governed by two distinct terms:
- A reward term scaling with $O(\sqrt{d_r/n})$ , where $n$ is the number of reward-observed trajectories.
- A transition term scaling with $O(\sqrt{d_p/(n+N)})$ , where $n+N$ is the total number of trajectories.
  This proves that transition-only data ( $N$ ) improves policy learning by reducing transition uncertainty, even when rewards are missing.
Extensions: The framework is shown to extend to step-level reward observation (where rewards are missing at random within trajectories) and sub-Gaussian rewards with finite mean ranges.

4. Empirical Results

4.1 Simulations

Settings: Experiments covered complete and partial reward observation with binary and bounded continuous rewards (Beta distribution).
Findings: GRASP-MDP consistently outperformed Linear MDP baselines (PEVI, Local/Global Q-learning) when rewards were nonlinear. Under partial reward observation, retaining transition-only trajectories significantly improved policy performance compared to methods that discarded them or used only labeled data.

4.2 Real-World Application: Multiple Sclerosis (MS)

Context: Learning Disease-Modifying Treatment (DMT) strategies using Electronic Health Records (EHRs).
Data: A cohort of 4,295 patients from the Mass General Brigham EHR and CLIMB registry. Rewards were based on the Expanded Disability Status Scale (EDSS), which is bounded (0–10) and observed intermittently (missing in ~40% of patient-periods).
Outcome: The GRASP-MDP policy utilizing reward-missing data (retaining transition-only trajectories) achieved numerically favorable estimates for average EDSS and months with EDSS $\le$ 4 compared to methods using only labeled data or standard linear baselines. This demonstrated the practical benefit of leveraging transition-only information in clinical settings with sparse outcome reporting.

5. Significance and Claims

The paper claims that GRASP-MDP provides a principled solution for offline RL in settings with structured, intermittently observed outcomes. Its significance lies in:

Preserving Tractability: It maintains the computational and statistical tractability of Linear MDPs while accommodating the nonlinear reward structures common in real-world data.
Efficient Data Utilization: It formally justifies the use of transition-only observations for policy learning without imputing missing rewards, thereby avoiding the bias introduced by imputation assumptions.
Separation of Uncertainty: By controlling reward and transition errors separately, the method provides finite-sample guarantees that clearly delineate the value of additional transition data versus additional reward data.

The authors note that the method relies on standard assumptions such as missing-at-random for rewards and sufficient coverage (positivity) of state-action regions. They acknowledge that non-ignorable missingness and distribution shifts between reward-labeled and transition-only trajectories remain open challenges. The framework is also noted to support online extensions (GLSVI-UCB) with sublinear regret guarantees.