2019

If MaxEnt RL is the Answer, What is the Question?

Eysenbach, Benjamin, Levine, Sergey

Understand

Experimentally, it has been observed that humans and animals often make decisions that do not maximize their expected utility, but rather choose outcomes randomly, with probability proportional to expected utility.

Probability matching, as this strategy is called, is equivalent to maximum entropy reinforcement learning (MaxEnt RL).
However, MaxEnt RL does not optimize expected utility.
In this paper, we formally show that MaxEnt RL does optimally solve certain classes of control problems with variability in the reward function.

Built on

Tsallis reinforcement learning: A unified framework for maximum entropy reinforcement learning
Original
Kyungjae Lee, Sungyub Kim, Sungbin Lim, Sungjoon Choi, and Songhwai Oh · 1902
Earlier work this paper cites.
Efficient exploration via state marginal matching
Original
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov · 1906
Earlier work this paper cites.
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
William R Thompson · 1933
Earlier work this paper cites.
Equilibrium points in n-person games
John F Nash et al · 1950
Earlier work this paper cites.
Iterative solution of games by fictitious play
George W Brown · 1951
Earlier work this paper cites.
Some comparative psychology
ME Bitterman, Jerome Wodinsky, and Douglas K Candland · 1958
Earlier work this paper cites.
Probability-matching in the pigeon
Donald H Bullock and ME Bitterman · 1962
Earlier work this paper cites.
Further experiments on probability-matching in the pigeon 1
Virgil Graf, DH Bullock, and ME Bitterman · 1964
Earlier work this paper cites.
Children’s behavior in a probabilistic situation
Harold W Stevenson and Richard D Odom · 1964
Earlier work this paper cites.
Developmental changes in problem-solving strategies
Morton W Weir · 1964
Earlier work this paper cites.
Competitive foraging in mallards: “ideal free” ducks
DGC Harper · 1982
Earlier work this paper cites.
Foraging theory
David W Stephens and John R Krebs · 1986
Earlier work this paper cites.
The organization of learning
Charles R Gallistel · 1990
Earlier work this paper cites.
Function optimization using connectionist reinforcement learning algorithms
Ronald J Williams and Jing Peng · 1991
Earlier work this paper cites.
Memory dynamics and foraging strategies of honeybees
Uwe Greggers and Randolf Menzel · 1993
Earlier work this paper cites.
Learning to achieve goals
Leslie Pack Kaelbling · 1993
Earlier work this paper cites.
Foraging wood-ants formica aquilonia yarrow (hymenoptera: Formicidae) tend to adopt the ideal free distribution
AE Lamb and JG Ollason · 1993
Earlier work this paper cites.
Using expectation-maximization for reinforcement learning
Peter Dayan and Geoffrey E Hinton · 1997
Earlier work this paper cites.
Essentials of robust control , volume 104
Kemin Zhou and John Comstock Doyle · 1998
Earlier work this paper cites.
An economist’s perspective on probability matching
Nir Vulkan · 2000
Earlier work this paper cites.

Similar

Risk-sensitive reinforcement learning
Oliver Mihatsch and Ralph Neuneier · 2002
Cited alongside, same era.
Optimal feedback control as a theory of motor coordination
Emanuel Todorov and Michael I Jordan · 2002
Cited alongside, same era.
Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory
Peter D Grünwald, A Philip Dawid, et al · 2004
Cited alongside, same era.
Optimal feedback control and the neural basis of volitional motor control
Stephen H Scott · 2004
Cited alongside, same era.
Path integrals and symmetry breaking for optimal control theory
Hilbert J Kappen · 2005
Cited alongside, same era.
Evidence for the flexible sensorimotor strategies predicted by optimal feedback control
Dan Liu and Emanuel Todorov · 2007
Cited alongside, same era.
Linearly-solvable markov decision problems
Emanuel Todorov · 2007
Cited alongside, same era.
The smart potential behind probability matching
Wolfgang Gaissmaier and Lael J Schooler · 2008
Cited alongside, same era.
The actor-critic learning is behind the matching law: Matching versus optimal behaviors
Yutaka Sakai and Tomoki Fukai · 2008
Cited alongside, same era.
On an upper bound for jensen’s inequality
Slavko Simic · 2009
Cited alongside, same era.
Robot trajectory optimization using approximate inference
Marc Toussaint · 2009
Cited alongside, same era.
A generalized path integral control approach to reinforcement learning
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal · 2010
Cited alongside, same era.

Then

Taming the noise in reinforcement learning via soft updates
Original
Roy Fox, Ari Pakman, and Naftali Tishby · 2015
Later among the works it cites.
Learning continuous control policies by stochastic value gradients
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa · 2015
Later among the works it cites.
Continuous control with deep reinforcement learning
Original
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra · 2015
Later among the works it cites.
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Later among the works it cites.
Universal value function approximators
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver · 2015
Later among the works it cites.
Reward augmented maximum likelihood for neural structured prediction
Mohammad Norouzi, Samy Bengio, Navdeep Jaitly, Mike Schuster, Yonghui Wu, Dale Schuurmans, et al · 2016
Later among the works it cites.
Artificial intelligence: a modern approach
Stuart J Russell and Peter Norvig · 2016
Later among the works it cites.
Hindsight experience replay
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba · 2017
Later among the works it cites.
Bridging the gap between value and policy based reinforcement learning
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans · 2017
Later among the works it cites.
Robust adversarial reinforcement learning
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta · 2017
Later among the works it cites.
Maximum a posteriori policy optimisation
Original
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller · 2018
Later among the works it cites.
Understanding the impact of entropy in policy learning
Original
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans · 2018
Later among the works it cites.
Path consistency learning in tsallis entropy regularized mdps
Yinlam Chow, Ofir Nachum, and Mohammad Ghavamzadeh · 2018
Later among the works it cites.
Composable deep reinforcement learning for robotic manipulation
Tuomas Haarnoja, Vitchyr Pong, Aurick Zhou, Murtaza Dalal, Pieter Abbeel, and Sergey Levine · 2018
Later among the works it cites.
Reinforcement learning and control as probabilistic inference: Tutorial and review
Original
Sergey Levine · 2018
Later among the works it cites.
Variational bayesian reinforcement learning with regret bounds
Original
Brendan O’Donoghue · 2018
Later among the works it cites.
Unsupervised control through non-parametric discriminative rewards
Original
David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih · 2018
Later among the works it cites.
Adversarial examples are not bugs, they are features
Original
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry · 2019
Closest in time.
Skew-fit: State-covering self-supervised reinforcement learning
Original
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine · 2019
Closest in time.
End-to-end robotic reinforcement learning without reward engineering
Original
Avi Singh, Larry Yang, Kristian Hartikainen, Chelsea Finn, and Sergey Levine · 2019
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…