In reinforcement learning (RL), standard value functions track the expected value of cumulative future rewards. While knowing the expected return allows an agent to find a policy that maximizes average performance, it completely hides risk, uncertainty, and volatility. To build risk-aware agents or prove tight statistical bounds on learning efficiency, we need to know the variance of the return.
At first glance, estimating variance seems to require expensive Monte Carlo rollouts across entire trajectories. However, a powerful insight unites a large body of RL literature: just like the expected return, the variance of the return (and its higher-order moments) satisfies a recursive, Bellman-like structure. By exploiting the Markov property, we can learn, decompose, and bound variance online and sample-efficiently.
The Intuition: Why Variance is Recursive
To understand why variance can be computed recursively, it is easiest to look at the second moment of the return. Let the return from a state $S_t$ be defined as the discounted sum of future rewards:
$$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \dots = R_t + \gamma G_{t+1}$$
Standard value functions estimate the first moment, $J(s) = \mathbb{E}[G_t \mid S_t = s]$. If we want to find the variance, $\text{Var}(G_t \mid S_t = s)$, we can use the identity:
$$\text{Var}(G_t \mid S_t = s) = \mathbb{E}[G_t^2 \mid S_t = s] - J(s)^2$$
The core breakthrough is that the second moment, $M(s) = \mathbb{E}[G_t^2 \mid S_t = s]$, can be expanded recursively by squaring the return relation:
$$G_t^2 = (R_t + \gamma G_{t+1})^2 = R_t^2 + 2\gamma R_t G_{t+1} + \gamma^2 G_{t+1}^2$$
Taking the conditional expectation of both sides reveals a linear relation that mirrors the classic Bellman equation:
$$M(s) = \mathbb{E}[R_t^2] + 2\gamma \mathbb{E}[R_t J(S_{t+1})] + \gamma^2 \mathbb{E}[M(S_{t+1})]$$
Notice the structure: the second moment at the current state depends on the second moment of the next state, discounted by $\gamma^2$. As shown by Tamar et al. and later expanded in Tamar et al., this linearity means we can adapt standard Temporal Difference (TD) and Least Squares Temporal Difference (LSTD) methods to learn the second moment simultaneously alongside the mean.
An alternative but mathematically equivalent formulation targets the variance directly rather than the second moment. As analyzed by Sherstan et al., one can treat the squared TD error of the primary value function as a "reward" signal for a secondary value function. By discounting this secondary estimator by $\gamma^2$, the variance itself is mapped directly onto a standard TD learning problem, allowing practitioners to seamlessly deploy eligibility traces and off-policy updates.
Breaking the Curse of the Horizon in Theory
While estimating variance is practically useful for risk management, its recursive decomposition is also a cornerstone of modern RL theory.
When proving how many samples an algorithm needs to find an optimal policy (sample complexity or regret bounds), a major obstacle is the planning horizon $H$ (or the effective horizon $1/(1-\gamma)$). Naive theoretical analyses assume that errors accumulate in a worst-case, additive fashion at every step, causing error bounds to scale polynomially with the horizon.
By applying the law of total variance recursively across a trajectory, theorists can tightly control how estimation errors propagate. Azar et al. introduced this component-wise variance analysis to establish the very first minimax-optimal sample complexity bounds for MDPs with a generative model. Instead of bounding errors by the maximum possible value of the reward function, the recursive structure bounds them by the actual environmental variance encountered along the path.
This recursive variance decomposition has allowed researchers to systematically eliminate horizon dependencies across various settings:
- Fixed-Horizon RL: Dann and Brunskill leveraged a recursive value variance structure to drastically reduce the horizon dependency in episodic sample complexity bounds.
- Offline RL: Ren et al. utilized iterative higher-order value variance estimations to achieve "horizon-free" bounds, proving that offline policy evaluation complexity can be decoupled from episode length.
- Linear Function Approximation: Zhang et al. treated transition variance as a quadratic function of model parameters, recursively estimating higher-order moments to establish horizon-free regret bounds for linear mixture MDPs.
- Discounted MDPs: He et al. closed a long-standing theoretical gap by using recursive variance decomposition to achieve minimax-optimal regret bounds that scale optimally with the discount factor.
Practical Applications: Exploration, Safety, and Tuning
Because recursive variance estimation avoids the high sample variance of non-recursive Monte Carlo sampling, it can be computed stably online. This opens up several practical capabilities for active agents.
Uncertainty-Driven Exploration and Safety
If an agent can track the variance of its rewards, it can identify which parts of the state space have unpredictable outcomes. In Jain et al., the authors developed an exploration strategy that actively shifts an agent's behavior toward state-action pairs with high return variance, accelerating the simultaneous learning of multiple general value functions.
Conversely, variance can signal a need for safety. Singi et al. trained a secondary value function to track the second moment of a robot's return. When the calculated variance spikes, it triggers a state of "self-doubt," allowing the robotic agent to autonomously request human intervention before a catastrophic failure occurs.
Dynamic Parameter Tuning
Variance estimation also helps optimize the learning process itself. In TD learning, the eligibility trace parameter $\lambda$ balances the bias of bootstrapping against the variance of long-term rollouts. Konidaris et al. demonstrated that the classic $\lambda$-return implicitly assumes a geometric model of variance growth over time. By accurately tracking the true variance of returns, White et al. introduced an algorithm that adaptively tunes $\lambda$ on a per-state basis, minimizing estimation error dynamically as the agent learns.
Key Foundational Work
Temporal Difference Methods for the Variance of the Reward To Go (2013) — contributed 2 concept elements to this direction.
Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model (2013) — contributed 2 concept elements to this direction.
Policy Evaluation with Variance Related Risk Criteria in Markov Decision Processes (2013) — contributed 1 concept elements to this direction.