Increasing the Action Gap: New Operators for Reinforcement Learning

By Marc G. Bellemare, Georg Ostrovski, Arthur Guez, Philip S. Thomas, R´emi Munos. 2015

168 citations recorded by the source corpus.

This paper introduces new optimality-preserving operators on Q-functions. We first describe an operator for tabular representations, the consistent Bellman operator, which incorporates a notion of local policy consistency. We show that this local consistency leads to an increase in the action gap at each state; increasing this gap, we argue, mitigates the undesirable effects of approximation and estimation errors on the induced greedy policies. This operator can also be applied to discretized continuous space and time problems, and we provide empirical results evidencing superior performance in this context. Extending the idea of a locally consistent operator, we then derive sufficient conditions for an operator to preserve optimality, leading to a family of operators which includes our consistent Bellman operator. As corollaries we provide a proof of optimality for Baird's advantage learning algorithm and derive other gap-increasing operators with interesting properties. We conclude with an empirical study on 60 Atari 2600 games illustrating the strong potential of these new operators.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Reinforcement Learning

Citations in the corpus

Asynchronous Methods for Deep Reinforcement Learning (2016, methodology): “All of the value-based methods we investigated could beneﬁt from different ways of reducing over-estimation bias of Q-values (Van Hasselt et al., 2015; Belle-mare et al., 2016).”
Taming the Noise in Reinforcement Learning via Soft Updates (2015, background): “In this sense, the Ψ-learning update (27) is an informationtheoretic gap-increasing Bellman operator [25].”
Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents (2017, background): “Finally, intrinsically generated rewards (Bellemare et al., 2016b) may also provide a useful learning signal which the agent can use to build a representation.”
Prioritized Experience Replay (2015, methodology): “…for playing Atari with deep reinforcement learning, including deep Q-networks (DQN) (Mnih et al., 2013; 2015; Guo et al., 2014; Stadie et al., 2015; Nair et al., 2015; Bellemare et al., 2016), and the Double DQN algorithm (van Hasselt et al., 2016), which is the current published state-of-the-art.”
Dueling Network Architectures for Deep Reinforcement Learning (2015, background): “The results of Schaul et al. (2016) are the current published state-of-the-art.”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, methodology): “25 as has been previously used in Bellemare et al. (2016).”
Conservative Q-Learning for Offline Reinforcement Learning (2020, background): “4, is related to how gap-increasing Bellman backup operators [6, 37] are more robust to estimation error in online RL.”
A Deep Hierarchical Approach to Lifelong Learning in Minecraft (2016, methodology): “While different variations of the DQN algo-rithm exist [ Van Hasselt et al. , 2015; Schaul et al. , 2015; Wang et al. , 2015; Bellemare et al. , 2015 ] , we will refer to the Vanilla DQN [ Mnih et al. , 2015 ] unless otherwise stated.”
A General Family of Robust Stochastic Operators for Reinforcement Learning (2018, methodology): “To address issues of nonstationarity of this and related forms arising in practice, Bellemare et al. [3] propose the so-called consistent Bellman operator deﬁned as where 1 {·} denotes the indicator function.”
EMaQ: Expected-Max Q-Learning Operator for Simple Yet Effective Offline and Online RL (2020, methodology): “…on how to design effective RL exploration policies (Weng, 2020), in this work we used a simple UCB-style exploration criterion (Chen et al., 2017) as follows: explore ( s, a ) = mean Given N sampled actions from the modiﬁed proposal distribution, we take the action with highest Q explore.”
Weighted QMIX: Expanding Monotonic Value Function Factorisation (2020, neutral): “Value (the action gap [1]).”
Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks (2016, background): “In ALE, partial observability has been artiﬁcially introduced by blanking out a fraction of the input screen (Hausknecht & Stone, 2015).”
FeUdal Networks for Hierarchical Reinforcement Learning (2017, background): “(Bellemare et al., 2016a) have signiﬁcantly advanced the state-of-the-art on Montezuma’s Revenge by us-ing pseudo-count based auxiliary rewards for exploration, which stimulate agents to explore new parts of the state space.”
Dopamine: A Research Framework for Deep Reinforcement Learning (2018, methodology): “Bellemare et al. (2016b) depicted the exploratory behaviour of intrinsically-motivated agents using maps from the game M ONTEZUMA ’ S R EVENGE .”
Learning values across many orders of magnitude (2016, background): “Natural gradients [Amari, 1998] are invariant to reparameterizations of the function approximation, thereby avoiding many scaling issues, but these are computationally expensive for functions with many parameters such as deep neural networks.”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, background): “These intrinsic rewards can for example be based on the (pseudo) state visit count (Bellemare et al., 2016a), on the temporal di ﬀ er-ence error (Achiam and Sastry, 2017) or on the prediction accuracy of a simultaneously learned dynamics model (Schmid-huber, 1991).”
Munchausen Reinforcement Learning (2020, methodology): “Taking the limit τ → 0, we retrieve Advantage Learning (AL) [5, 7] (see Appx.”
Estimating the Maximum Expected Value in Continuous Reinforcement Learning Problems (2017, background): “Since the positive bias of the maximum operator increases when there are multiple actions with an expected value that is close to the maximum one, a modified Bellman operator that reduces the bias by increasing the action gap (that is the difference between the best action value and the second best)”
The Importance of Pessimism in Fixed-Dataset Policy Optimization (2020, background): “And, indeed, on deep RL benchmarks, which are selected due to their similarity to real-world seings, overestimation has been widely observed, and is oen identied as a cause of poor performance [2, 7, 42].”