PaperlayerView exact revision on arXiv

Source-linked AI summary

The Uncertainty Bellman Equation and Exploration

Brendan O'Donoghue, Ian Osband, Remi Munos, Volodymyr Mnih

arXiv:1709.05380v4cs.AIcs.LGmath.OCstat.ML

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.

  • Method

    The paper defines uncertainty as Bayesian posterior variance over policy Q-values and uses an uncertainty Bellman equation, learned with deep-RL machinery, to guide exploration.

  • 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.

  • Takeaways & Limitations

    Propagated Q-value uncertainty lets agents select states and actions for exploration while reusing reinforcement-learning machinery for value functions.

  • Takeaways & Limitations

    The deep-RL application is heuristic because its MDPs are not acyclic, policies change, local uncertainty is approximate, and the UBE is not solved exactly.

Abstract

from arXiv · show

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.
  • Motivation: Randomized schemes such as ϵ-greedy eventually explore reachable state-action pairs but can take exponentially long to learn the optimal policy.
  • Existing approaches: Optimism-based methods encourage exploration with bonuses, but simultaneously optimistic estimates can become excessively over-optimistic for the MDP as a whole.
  • 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.
  • Core contribution: 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.

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.
  • MDP formulation: A policy assigns each state-action pair a probability of selecting that action at each time-step.
  • MDP formulation: At each step, the agent observes a state and reward, selects an action, and transitions probabilistically to the next state.
  • Objective: The objective is to maximize the expected total discounted return, averaging over initial states, transitions, rewards, and policy actions.
  • 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.
  • 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.

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.
  • UBE formulation: 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.
  • UBE formulation: 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.
  • 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.
  • 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.
  • Comparison to traditional exploration bonus: 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.

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.
  • 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.
  • 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.
  • Linear value estimate: 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.
  • Linear value estimate: 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.
  • 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.

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.
  • 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.
  • 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.
  • 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.
  • Experimental results: 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.
  • 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.

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.
  • Contribution: 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.
  • 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.

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.
  • 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.
  • Variance decomposition: 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.
  • 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.
  • Downstream bound: 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.

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.
Loading 1709.05380v4…