Recursive Variance Estimation in Markov Decision Processes

This direction is split into other directions: recursive variance decomposition. Its last version stays readable and citable here.

Version 1 of 131 papers39 conceptsfrozen 2026-10-04

In standard Reinforcement Learning (RL), we typically focus on the Bellman equation, a recursive relationship that allows us to estimate the expected sum of future rewards (the "value"). However, the expected value only tells half the story. To build agents that are safe, risk-aware, or theoretically efficient, we need to understand the variance of those rewards.

Recent research has demonstrated that variance and uncertainty in Markov Decision Processes (MDPs) are not just static properties; they follow their own recursive, Bellman-style structures. By treating variance as something that can be propagated and learned just like value, researchers have unlocked tighter theoretical bounds and more robust agents.

The Bellman Equation for Variance

The core insight, popularized by Aviv Tamar, Dotan Di Castro, and Shie Mannor, is that the second moment of cumulative rewards satisfies a linear recursive relationship analogous to the standard Bellman equation.

While variance itself is non-linear—and thus difficult to estimate directly with standard temporal difference (TD) methods—the second moment behaves linearly. In Policy Evaluation with Variance Related Risk Criteria in Markov Decision Processes, the authors show that you can adapt standard tools like LSTD to estimate reward variability in large state spaces. This allows for the optimization of risk-sensitive objectives, such as the Sharpe Ratio, by calculating gradients of the variance with respect to policy parameters Di Castro and Tamar.

Learning Variance as a Secondary Task

If variance follows a recursive structure, can we learn it using the same TD algorithms we use for value? Craig Sherstan, Adam White, and their colleagues developed a "direct" method to do exactly this.

The trick is to treat the squared temporal-difference error of the primary value function as a "reward" signal for a secondary learner. In Directly Estimating the Variance of the λ-Return Using Temporal-Difference Methods, they show that by using this squared error and a squared discount factor ($\gamma^2$), a secondary value function will converge to the variance of the return.

This approach is powerful because it is "model-free." An agent doesn't need to know the transition dynamics of the environment; it simply observes its own prediction errors to learn how "surprised" it should expect to be in the future. This "self-doubt" is used in frameworks like HULA Singi to help robotic agents decide when to stop acting autonomously and ask a human for help.

Propagating Uncertainty in Model-Based RL

In model-based RL, agents learn a transition model to plan ahead. However, small errors in the model compound over long horizons—a phenomenon often called the "curse of horizon."

To combat this, Houqiang Li and Qi Zhou introduced POMBU Li et al.. Instead of treating model uncertainty as a local property of a single state-action pair, they propagate it through time using a Bellman-style recursive equation. This allows the agent to estimate the cumulative variance of future rewards caused by model inaccuracies. By performing "conservative" policy updates in regions where this propagated uncertainty is high, the agent avoids overfitting to flawed simulations and achieves better stability in complex control tasks.

Breaking the Curse of Horizon

The recursive nature of variance isn't just useful for building algorithms; it is the key to proving that RL is more efficient than we previously thought.

In theoretical analysis, the Law of Total Variance is used to decompose the total error of a value function into a sum of variances across the trajectory. Christoph Dann and Emma Brunskill used this recursive structure in Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning to reduce the sample complexity of RL by a factor of the time horizon ($H$).

More recently, Tongzheng Ren and Simon S. Du demonstrated that this technique can lead to "nearly horizon-free" offline RL Ren et al.. By iteratively estimating the variance of higher-order value functions, they show that the data needed to evaluate a policy can be made nearly independent of the task's length. Similarly, Jiafan He and Quanquan Gu used recursive variance decomposition to reach the minimax-optimal regret bound for discounted MDPs He et al., closing a long-standing gap in the field.

By recognizing that variance follows the same temporal logic as value, these researchers have transformed variance from a nuisance to be managed into a structured signal that can be learned, propagated, and optimized.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_recursive_variance_estimation_in_markov__f3082499,
  title = {Recursive Variance Estimation in Markov Decision Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-variance-estimation-in-markov-decision-processes/rdr_f3082499ca034658b640fc83ada70c38},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_recursive_variance_estimation_in_markov__f3082499_v1,
  title = {Recursive Variance Estimation in Markov Decision Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-variance-estimation-in-markov-decision-processes/rdr_f3082499ca034658b640fc83ada70c38/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}