2022

The Phenomenon of Policy Churn

Schaul, Tom, Barreto, André, Quan, John et al.

Understand

We identify and study the phenomenon of policy churn, that is, the rapid change of the greedy policy in value-based reinforcement learning.

Policy churn operates at a surprisingly rapid pace, changing the greedy action in a large fraction of states within a handful of learning updates (in a typical deep RL set-up such as DQN on Atari).
We characterise the phenomenon empirically, verifying that it is not limited to specific algorithm or environment properties.
A number of ablations help whittle down the plausible explanations on why churn occurs to just a handful, all related to deep learning.

Built on

On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
W. R. Thompson · 1933
Earlier work this paper cites.
Stable function approximation in dynamic programming
G. J. Gordon · 1995
Earlier work this paper cites.
Neuro-Dynamic Programming
D. P. Bertsekas and J. N. Tsitsiklis · 1996
Earlier work this paper cites.
Tag-trigger-consolidation: a model of early and late long-term-potentiation and depression
C. Clopath, L. Ziegler, E. Vasilaki, L. Büsing, and W. Gerstner · 2008
Earlier work this paper cites.
Bayesian learning via stochastic gradient Langevin dynamics
M. Welling and Y. W. Teh · 2011
Earlier work this paper cites.
RMSProp: Divide the gradient by a running average of its recent magnitude
T. Tieleman, G. Hinton, et al · 2012
Earlier work this paper cites.
The arcade learning environment: An evaluation platform for general agents
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling · 2013
Earlier work this paper cites.
Playing Atari with deep reinforcement learning
Original
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller · 2013
Earlier work this paper cites.
Adam: A method for stochastic optimization
Original
D. P. Kingma and J. Ba · 2014
Earlier work this paper cites.
Policy oscillation is overshooting
P. Wagner · 2014
Earlier work this paper cites.
Human-level control through deep reinforcement learning
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis · 2015
Earlier work this paper cites.
Deepmind lab
Original
C. Beattie, J. Z. Leibo, D. Teplyashin, T. Ward, M. Wainwright, H. Küttler, A. Lefrancq, S. Green, V. Valdés, A. Sadik, et al · 2016
Earlier work this paper cites.
Increasing the action gap: New operators for reinforcement learning
M. G. Bellemare, G. Ostrovski, A. Guez, P. Thomas, and R. Munos · 2016
Earlier work this paper cites.
On large-batch training for deep learning: Generalization gap and sharp minima
Original
N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang · 2016
Earlier work this paper cites.
Deep exploration via bootstrapped DQN
I. Osband, C. Blundell, A. Pritzel, and B. Van Roy · 2016
Earlier work this paper cites.
An overview of gradient descent optimization algorithms
Original
S. Ruder · 2016
Earlier work this paper cites.
Prioritized experience replay
T. Schaul, J. Quan, I. Antonoglou, and D. Silver · 2016
Earlier work this paper cites.

Similar

Deep reinforcement learning with double Q-learning
H. Van Hasselt, A. Guez, and D. Silver · 2016
Cited alongside, same era.
Dueling network architectures for deep reinforcement learning
Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas · 2016
Cited alongside, same era.
Noisy networks for exploration
Original
M. Fortunato, M. G. Azar, B. Piot, J. Menick, I. Osband, A. Graves, V. Mnih, R. Munos, D. Hassabis, O. Pietquin, C. Blundell, and S. Legg · 2017
Cited alongside, same era.
Intrinsic volatility of synaptic connections a challenge to the synaptic trace theory of memory
G. Mongillo, S. Rumpel, and Y. Loewenstein · 2017
Cited alongside, same era.
JAX: composable transformations of Python+NumPy programs, 2018
J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang · 2018
Cited alongside, same era.
IMPALA: Scalable distributed Deep-RL with importance weighted actor-learner architectures
Original
L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al · 2018
Cited alongside, same era.
Rainbow: Combining improvements in deep reinforcement learning
M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver · 2018
Cited alongside, same era.
An alternative view: When does sgd escape local minima?
B. Kleinberg, Y. Li, and Y. Yuan · 2018
Cited alongside, same era.
Reinforcement learning: An introduction
R. S. Sutton and A. G. Barto · 2018
Cited alongside, same era.
Recurrent experience replay in distributed reinforcement learning
S. Kapturowski, G. Ostrovski, W. Dabney, J. Quan, and R. Munos · 2019
Cited alongside, same era.
Behaviour suite for reinforcement learning
Original
I. Osband, Y. Doron, M. Hessel, J. Aslanides, E. Sezener, A. Saraiva, K. McKinney, T. Lattimore, C. Szepesvari, S. Singh, et al · 2019
Cited alongside, same era.
Adapting behaviour for learning progress
Original
T. Schaul, D. Borsa, D. Ding, D. Szepesvari, G. Ostrovski, W. Dabney, and S. Osindero · 2019
Cited alongside, same era.

Then

Haiku: Sonnet for JAX, 2020
T. Hennigan, T. Cai, T. Norman, and I. Babuschkin · 2020
Later among the works it cites.
Optax: Composable gradient transformation and optimisation, in JAX!, 2020
M. Hessel, D. Budden, F. Viola, M. Rosca, E. Sezener, and T. Hennigan · 2020
Later among the works it cites.
Stimulus-dependent representational drift in primary visual cortex
T. D. Marks and M. J. Goard · 2020
Later among the works it cites.
Model-based reinforcement learning: A survey
Original
T. M. Moerland, J. Broekens, and C. M. Jonker · 2020
Later among the works it cites.
DQN Zoo: Reference implementations of DQN-based agents, 2020
J. Quan and G. Ostrovski · 2020
Later among the works it cites.
Mastering Atari, Go, Chess and Shogi by planning with a learned model
J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, et al · 2020
Later among the works it cites.
Gradient descent on neural networks typically occurs at the edge of stability
Original
J. M. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar · 2021
Later among the works it cites.
Temporally-extended ϵ \epsilon -greedy exploration
W. Dabney, G. Ostrovski, and A. Barreto · 2021
Later among the works it cites.
Podracer architectures for scalable reinforcement learning
Original
M. Hessel, M. Kroiss, A. Clark, I. Kemaev, J. Quan, T. Keck, F. Viola, and H. van Hasselt · 2021
Later among the works it cites.
Revisiting peng’s q ( λ \lambda ) for modern reinforcement learning
T. Kozuno, Y. Tang, M. Rowland, R. Munos, S. Kapturowski, W. Dabney, M. Valko, and D. Abel · 2021
Later among the works it cites.
Estimates for the branching factors of Atari games
Original
M. J. Nelson · 2021
Later among the works it cites.
The difficulty of passive learning in deep reinforcement learning
Original
G. Ostrovski, P. S. Castro, and W. Dabney · 2021
Later among the works it cites.
Self-healing neural codes
M. E. Rule and T. O’Leary · 2021
Later among the works it cites.
Return-based scaling: Yet another normalisation trick for deep RL
Original
T. Schaul, G. Ostrovski, I. Kemaev, and D. Borsa · 2021
Later among the works it cites.
Representational drift in primary olfactory cortex
C. E. Schoonover, S. N. Ohashi, R. Axel, and A. J. P. Fink · 2021
Later among the works it cites.
When should agents explore?
M. Pîslar, D. Szepesvari, G. Ostrovski, D. Borsa, and T. Schaul · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…