Source-linked AI summary
The Uncertainty Bellman Equation and Exploration
Brendan O'Donoghue, Ian Osband, Remi Munos, Volodymyr Mnih
TL;DR
Reinforcement learning must balance exploiting known rewards with exploring uncertain states and actions. The paper introduces an uncertainty Bellman equation to propagate Q-value uncertainty across time, and a heuristic based on learned uncertainty improves standard deep-RL performance despite violated assumptions.
Problem
Reinforcement learning agents must balance maximizing current rewards with investigating poorly understood states and actions to improve future performance.
Source: §1 · p. 1Method
Results
The learned-uncertainty heuristic boosts standard deep-RL performance; in Montezuma’s Revenge, the n-step agent consistently reaches around 3000 points after 500M frames.
Source: §5.1 · p. 7, §6 · p. 8Takeaways & Limitations
Propagated Q-value uncertainty lets agents select states and actions for exploration while reusing reinforcement-learning machinery for value functions.
Source: §2 · p. 2, §6 · p. 8The deep-RL application is heuristic because its MDPs are not acyclic, policies change, local uncertainty is approximate, and the UBE is not solved exactly.
Source: §5 · p. 6
Abstract
from arXiv · showhide
We consider the exploration/exploitation problem in reinforcement learning. For exploitation, it is well known that the Bellman equation connects the value at any time-step to the expected value at subsequent time-steps. In this paper we consider a similar \textit{uncertainty} Bellman equation (UBE), which connects the uncertainty at any time-step to the expected uncertainties at subsequent time-steps, thereby extending the potential exploratory benefit of a policy beyond individual time-steps. We prove that the unique fixed point of the UBE yields an upper bound on the variance of the posterior distribution of the Q-values induced by any policy. This bound can be much tighter than traditional count-based bonuses that compound standard deviation rather than variance. Importantly, and unlike several existing approaches to optimism, this method scales naturally to large systems with complex generalization. Substituting our UBE-exploration strategy for $ε$-greedy improves DQN performance on 51 out of 57 games in the Atari suite.
1. Introduction
The paper addresses exploration–exploitation in uncertain reinforcement-learning environments, where common exploration strategies can learn inefficiently. It introduces the uncertainty Bellman equation to propagate posterior Q-value uncertainty across time and guide deep exploration.
Motivation
- The agent must balance investigating poorly understood states and actions against maximizing rewards using current knowledge.The environment is modeled as an MDP whose dynamics and mean rewards are initially uncertain.Source: §1 · p. 1
- Randomized schemes such as ϵ-greedy eventually explore reachable state-action pairs but can take exponentially long to learn the optimal policy.Source: §1 · p. 1
Existing approaches
- Optimism-based methods encourage exploration with bonuses, but simultaneously optimistic estimates can become excessively over-optimistic for the MDP as a whole.Source: §1 · p. 1
Core contribution
- The uncertainty Bellman equation propagates Bayesian posterior variance of policy Q-values across multiple time-steps, enabling deep exploration.The paper uses uncertainty about value estimates to identify regions where additional data may improve Q-value estimates.Source: §1 · p. 2
- The approach learns UBE uncertainty values with existing deep-reinforcement-learning machinery and compounds variances rather than standard deviations.It requires minimal changes to existing network architectures and targets epistemic uncertainty over the value function.Source: §1 · p. 2
2. Problem formulation
The paper formulates finite-horizon reinforcement learning as an MDP with stochastic rewards, transitions, and policies. Standard Bellman recursion defines policy values and Q-values, motivating an analogous recursion for propagating Q-value uncertainty.
MDP formulation
- The environment is a finite-horizon MDP with horizon H, state space S, action space A, and real-valued rewards at each time period.Source: §2 · p. 2
- A policy assigns each state-action pair a probability of selecting that action at each time-step.Source: §2 · p. 2
- At each step, the agent observes a state and reward, selects an action, and transitions probabilistically to the next state.Source: §2 · p. 2
Objective
- The objective is to maximize the expected total discounted return, averaging over initial states, transitions, rewards, and policy actions.Source: §2 · p. 2
Value functions
- A Q-value is the expected total return after taking an action in a state and then following the policy, while the state value averages Q-values over policy actions.Source: §2 · p. 2
Bellman recursion
- The Bellman operator relates values at one time-step to subsequent values, and Q-values are the unique fixed point with terminal value QH+1 defined as zero.Reinforcement-learning algorithms minimize Bellman residuals to propagate immediate-reward information to long-term values; the paper applies the same idea to uncertainty.Source: §2 · p. 2
3. The uncertainty Bellman equation
The uncertainty Bellman equation propagates posterior Q-value variance across time, producing a unique uncertainty solution that upper-bounds posterior variance and guides deep exploration. In a simple decision problem, it avoids the over-large bonuses caused by compounding standard deviations and reduces regret relative to count-based exploration.
UBE formulation
- The uncertainty Bellman equation propagates Bayesian posterior variance over Q-values across multiple time-steps, extending the potential benefit of exploration beyond individual decisions.This relationship is intended to support deep exploration and statistically efficient reinforcement learning.Source: §3 · p. 2
- The UBE decomposes uncertainty into local uncertainty terms and recursively propagates them through expected future uncertainties.The local uncertainty depends on quantities available at each state-action pair and contributes to the Bellman-style variance bound.Source: §3.1 · p. 3
- Under the stated assumptions, the uncertainty Bellman equation has a unique solution u that pointwise upper-bounds the posterior variance of Q-values for any policy.The result uses a finite-horizon setting, an acyclic MDP assumption, and bounded mean rewards.Source: §3.1 · p. 3
Exploration strategy
- The method approximates the posterior over Q-values as N(Q̄, diag(u)) and uses Thompson sampling to select actions toward states and actions with higher uncertainty.This provides an exploration heuristic without computing the full posterior distribution.Source: §3.1 · pp. 3–4
Comparison to traditional exploration bonus
- When action uncertainty concentrates as 1/n, both actions have true uncertainty σ^2/n, but standard-deviation bonuses compound across the chain instead of following a Bellman-style variance relationship.The resulting overestimation forces the long-chain action to be sampled H times more often to receive the same effective bonus.Source: §3.2 · p. 4
- In the simple decision problem, UBE exploration quickly identifies the better first action, whereas the exploration-bonus agent receives excessive bonuses for the long chain and incurs significantly higher regret.The compared problem has one direct action and one length-H chain; the count-based bonus can be H times larger than the true uncertainty.Source: §3.2 · p. 4
4. Estimating the local uncertainty
The paper estimates local uncertainty using tabular counts, linear regression features, and neural-network representations, then uses these estimates to approximate global uncertainty. These approaches trade exactness for practical generalization in richer environments.
Estimating local uncertainty
- The paper presents tabular, linear, and neural-network approximations as pragmatic choices rather than uniquely optimal estimators of local uncertainty.It identifies the choice of approximation as an area for future research.Source: §4 · p. 5
Tabular value estimate
- Tabular local uncertainty is modeled as a constant divided by the state-action visit count under Gaussian reward and Dirichlet transition assumptions.The transition posterior variance concentrates reciprocally with category counts under the stated conjugate assumptions.Source: §4 · p. 5
Linear value estimate
- Linear value estimates use fixed basis functions and least-squares weights to generalize uncertainty across states and actions.The resulting estimator variance serves as a proxy for inverse counts.Source: §4 · p. 5
- For a new state vector, the variance of the linear Q-value estimate provides an inverse-count estimate used to construct an uncertainty bonus.The approach evaluates feature-dependent variance through the design-matrix inverse.Source: §4 · p. 5
- The linear implementation maintains Σ_a and updates it incrementally with the Sherman-Morrison-Woodbury formula as new data arrive.Each update requires one matrix multiply and one matrix-matrix subtraction per step.Source: §4 · pp. 5–6
Neural networks value estimate
- With a linear final neural-network layer, the method reuses the linear uncertainty analysis while ignoring uncertainty in the learned feature mapping.The network supplies task-relevant basis functions that can distinguish important state differences while aliasing irrelevant variation.Source: §4 · p. 6
5. Deep Reinforcement Learning
The deep-RL implementation learns uncertainty alongside Q-values and uses that uncertainty for Thompson-sampling exploration, while retaining the standard DQN architecture. Across Atari, the heuristic improves performance over naive exploration strategies and shows substantial progress on Montezuma’s Revenge.
Implementation
- The deep-RL method uses a neural network with separate Q-value and uncertainty outputs, preventing uncertainty gradients from changing the Q-value representation.The uncertainty estimates are learned with a one-step SARSA Bellman backup and can be extended to n-step updates.Source: §5 · p. 6
Experimental setup
- The Atari evaluation replaces DQN’s ϵ-greedy policy with Thompson sampling over learned uncertainty values while keeping the same network architecture.The Thompson-sampling parameter β was set to 0.01 for all games after a parameter sweep.Source: §5.1 · p. 7
Implementation
- The 1-step and n-step variants differ only in uncertainty updates; the n-step version uses 150 steps to propagate uncertainty faster at the cost of higher signal variance.Q-learning remains one-step in both variants.Source: §5.1 · p. 7
Experimental results
- UBE won in 14 games, compared with 1 for DQN and 7 for the exploration-bonus strategy, with 3 ties.Strategies were trained for 200M frames, evaluated across three random seeds, and scores were averaged.Source: §5.1 · p. 7
- After 200M frames, the 1-step method consistently reached about 500 points on Montezuma’s Revenge, while the n-step method reached around 3000 points by 500M frames.The n-step result represents progress through several rooms and was reported as close to state-of-the-art.Source: §5.1 · p. 7
Comparison
- Direct numerical comparison with prior intrinsic-motivation results is unavailable because those methods also changed DQN to use full Monte Carlo returns.The paper attributes the resulting performance difference to a change unrelated to exploration.Source: §5.1 · p. 7
6. Conclusion
The paper derives an uncertainty Bellman equation and uses it to propagate epistemic uncertainty through time for exploration. A heuristic implementation improves DQN performance across Atari compared with naive ϵ-greedy exploration.
Contribution
- The paper derives a Bellman recursion for uncertainty over policy Q-values, allowing uncertainty to propagate across multiple time-steps.This mirrors the temporal propagation of value in standard dynamic programming.Source: §6 · p. 8
- The learned uncertainty guides exploration toward states and actions where additional data can improve the agent’s policy.The agent learns uncertainty with reinforcement-learning machinery developed for value functions.Source: §6 · p. 8
Conclusion
- A heuristic UBE-based algorithm boosts standard deep-RL performance and significantly improves DQN across the Atari suite over naive ϵ-greedy strategies.The conclusion describes the result as empirical because the method is applied through learned uncertainty estimates.Source: §6 · p. 8
Proof of Lemma 1
The proof decomposes posterior Q-value variance into local reward uncertainty and downstream transition/value uncertainty, then bounds the downstream contribution using conditional independence, Jensen’s inequality, and bounded Q-values.
Posterior construction
- Posterior samples of rewards and transitions induce a posterior sample of Q-values through the Bellman solution.The sampled Q-values are the unique solution to the corresponding sampled Bellman equation.Source: Proof of Lemma 1 · p. 11
Variance decomposition
- The conditional-variance calculation separates uncertainty in the immediate reward from uncertainty propagated through transitions and successor Q-values.The proof uses the definition of conditional variance to organize these terms.Source: Proof of Lemma 1 · p. 11
- Conditional independence makes the reward term independent of transition and downstream-Q terms conditioned on the history.The proof invokes this independence for both the immediate reward and successor quantities.Source: Proof of Lemma 1 · p. 11
Downstream bound
- Jensen’s inequality bounds the quadratic downstream contribution after transition probabilities are treated as a distribution over successor state-action pairs.The transition probabilities are nonnegative and normalized over successor pairs.Source: Proof of Lemma 1 · p. 11
- The proof further uses bounded Q-values and the stated assumptions to obtain the final variance bound and define local uncertainty.Unreachable successor states can be removed because they contribute no variance.Source: Proof of Lemma 1 · pp. 11–12
Atari suite scores
Table 2 reports Atari performance from random starts, normalized as a percentage of human normalized score.
Atari suite scores
- Table 2 reports normalized Atari-suite scores from random starts as percentages of human normalized score.The table’s caption defines the evaluation setting and normalization.Source: Table 2 · p. 13