The Uncertainty Bellman Equation and Exploration

By Brendan O'Donoghue, Ian Osband, R´emi Munos, Volodymyr Mnih. 2017

215 citations recorded by the source corpus.

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 $\epsilon$-greedy improves DQN performance on 51 out of 57 games in the Atari suite.

Subfields: Artificial Intelligence, Management Science and Operations Research, Ocean Engineering, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Ocean Engineering

In Reinforcement Learning

Citations in the corpus

Addressing Function Approximation Error in Actor-Critic Methods (2018, background): “Further, the variance of the value estimate has been considered directly for risk-aversion (Mannor & Tsitsiklis, 2011) and exploration (O’Donoghue et al., 2017), but without connection to overestimation bias.”
Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “…et al., 2010), or directly representing samples from the distribution over Q-functions, for example via bootstrap ensembles (Osband et al., 2016), or by parameterizing the distribution over Q-values using a known (e.g., Gaussian) distribution with learned parameters (O’Donoghue et al., 2018).”
RUDDER: Return Decomposition for Delayed Rewards (2018, background): “[88] derived bias and variance expressions for updating Q-values.”
Off-Policy Deep Reinforcement Learning without Exploration (2018, neutral): “Uncertainty estimates in deep reinforcement learning have generally been used to encourage exploration (Dearden et al., 1998; Strehl & Littman, 2008; O’Donoghue et al., 2018; Azizzadenesheli et al., 2018).”
Exploration by Random Network Distillation (2018, neutral): “Since then a number of other works have achieved similar performance (O’Donoghue et al., 2017; Ostrovski et al., 2018; Machado et al., 2018; Osband et al., 2018), without exceeding it.”
Maximum a Posteriori Policy Optimisation (2018, background): “The most prominent examples for this are formed by work on Boltzmann exploration such as Kael-bling et al. (1996); Perkins & Precup (2002); Sutton (1990); O’Donoghue et al. (2017), which can be connected back to soft Q-learning (and thus to our approach) as shown in Haarnoja et al. (2017).”
Randomized Prior Functions for Deep Reinforcement Learning (2018, methodology): “2 However, there is a deeper problem to this line of research that is common across many works in this field: even given access to an oracle method for exact inference, applying independent inference to the Bellman error does not propagate uncertainty correctly for the value function as a whole [44]”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, methodology): “[3], and they were adopted as a primary source of stochasticity in most subsequent papers working in the Atari domain [3, 26, 27, 34, 38, 41, 42, 45, 67–73].”
Deep Exploration via Randomized Value Functions (2017, background): “Further, these approaches add uncertainty bonus that is uncoupled across states, which can lead to a substantial negative impact on statistical efficiency, as discussed in (Osband and Van Roy, 2017; O’Donoghue et al., 2017).”
Exploration with Unreliable Intrinsic Reward in Multi-Agent Reinforcement Learning (2019, methodology): “(2) As each head of the IQL value function qa(ua|τat ) is a linear function of the last network layer, that is, the hidden state φa(τat ) of a GRU, O’Donoghue et al. (2018) suggest to use r+t := √ Vt[qa](uat |τat ) as a measure of local uncertainty.”
Hypermodels for Exploration (2020, background): “O’Donoghue et al. (2018) consider such an approach for approximating Thompson sampling in reinforcement learning.”
QUOTA: The Quantile Option Architecture for Reinforcement Learning (2018, methodology): “Different approaches are used to achieve this optimism, e.g., count-based methods (Auer 2002; Kocsis and Szepesv ´ ari 2006; Bellemare et al. 2016; Ostrovski et al. 2017; Tang et al. 2017) and Bayesian methods (Kaufmann, Capp ´ e, and Garivier 2012; Chen et al. 2017; O’Donoghue et al. 2017).”
Unicorn: Continual Learning with a Universal, Off-policy Agent (2018, background): “Additions include optimizing for risk-aware, [46], robust [45, 27] as well as exploratory [6, 31] objectives to yield improved performance.”
A Review of Uncertainty Quantification in Deep Learning: Techniques, Applications and Challenges (2020, background): “[172] proposed the uncertainty Bellman equation (UBE) to quantify uncer-”
Distributional Reinforcement Learning for Efficient Exploration (2019, methodology): “Both count-based methods (Auer, 2002; Kaufmann et al., 2012; Bellemare et al., 2016; Ostrovski et al., 2017; Tang et al., 2017) and Bayesian methods (Kaufmann et al., 2012; Chen et al., 2017; O’Donoghue et al., 2017) follow this optimism principle.”
Exploration in Deep Reinforcement Learning: A Survey (2022, methodology): “[121] derived Bayesian uncertainty such that it can be computed using the Bellman principle and the output of the neural network.”
Risk-Averse Bayes-Adaptive Reinforcement Learning (2021, methodology): “The uncertainty Bellman equation (O’Donoghue et al., 2018) computes an upper bound on the variance of the value function due to parametric uncertainty, and this can be used to attain a policy which is robust to model misspecification (Derman et al.”