2020

Optimistic Policy Optimization with Bandit Feedback

Efroni, Yonathan, Shani, Lior, Rosenberg, Aviv et al.

Understand

Policy optimization methods are one of the most widely used classes of Reinforcement Learning (RL) algorithms.

Yet, so far, such methods have been mostly analyzed from an optimization perspective, without addressing the problem of exploration, or by making strong assumptions on the interaction with the environment.
In this paper we consider model-based RL in the tabular finite-horizon MDP setting with unknown transitions and bandit feedback.
For this setting, we propose an optimistic trust region policy optimization (TRPO) algorithm for which we establish $\tilde O(\sqrt{S^2 A H^4 K})$ regret for stochastic rewards.

Built on

Constrained Markov decision processes , volume 7
Altman, E · 1999
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y · 2000
Earlier work this paper cites.
The nonstochastic multiarmed bandit problem
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E · 2002
Earlier work this paper cites.
Approximately optimal approximate reinforcement learning
Kakade, S. and Langford, J · 2002
Earlier work this paper cites.
A natural policy gradient
Kakade, S. M · 2002
Earlier work this paper cites.
Near-optimal reinforcement learning in polynomial time
Kearns, M. and Singh, S · 2002
Earlier work this paper cites.
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A. and Teboulle, M · 2003
Earlier work this paper cites.
Error bounds for approximate policy iteration
Munos, R · 2003
Earlier work this paper cites.
Inequalities for the l1 deviation of the empirical distribution
Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. J · 2003
Earlier work this paper cites.
Policy gradient methods for robotics
Peters, J. and Schaal, S · 2006
Earlier work this paper cites.
Reinforcement learning of motor skills with policy gradients
Peters, J. and Schaal, S · 2008
Earlier work this paper cites.
Empirical bernstein bounds and sample variance penalization
Maurer, A. and Pontil, M · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Jaksch, T., Ortner, R., and Auer, P · 2010
Earlier work this paper cites.
The online loop-free stochastic shortest-path problem
Neu, G., György, A., and Szepesvári, C · 2010
Earlier work this paper cites.
Pilco: A model-based and data-efficient approach to policy search
Deisenroth, M. and Rasmussen, C. E · 2011
Earlier work this paper cites.

Similar

Online learning in episodic markovian decision processes by relative entropy policy search
Zimin, A. and Neu, G · 2013
Cited alongside, same era.
Markov decision processes: discrete stochastic dynamic programming
Puterman, M. L · 2014
Cited alongside, same era.
Approximate policy iteration schemes: a comparison
Scherrer, B · 2014
Cited alongside, same era.
Local policy search in a convex space and conservative policy iteration as boosted policy search
Scherrer, B. and Geist, M · 2014
Cited alongside, same era.
Continuous control with deep reinforcement learning
Original
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D · 2015
Cited alongside, same era.
Explore no more: Improved high-probability regret bounds for non-stochastic bandits
Neu, G · 2015
Cited alongside, same era.
Trust region policy optimization
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P · 2015
Cited alongside, same era.
End-to-end training of deep visuomotor policies
Levine, S., Finn, C., Darrell, T., and Abbeel, P · 2016
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Azar, M. G., Osband, I., and Munos, R · 2017
Cited alongside, same era.
Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning
Dann, C., Lattimore, T., and Brunskill, E · 2017
Cited alongside, same era.
Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates
Gu, S., Holly, E., Lillicrap, T., and Levine, S · 2017
Cited alongside, same era.
A unified view of entropy-regularized markov decision processes
Original
Neu, G., Jonsson, A., and Gómez, V · 2017
Cited alongside, same era.

Then

Politex: Regret bounds for policy iteration using expert prediction
Abbasi-Yadkori, Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G · 2019
Later among the works it cites.
Optimality and approximation with policy gradient methods in markov decision processes
Original
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G · 2019
Later among the works it cites.
Global optimality guarantees for policy gradient methods
Original
Bhandari, J. and Russo, D · 2019
Later among the works it cites.
Provably efficient exploration in policy optimization
Original
Cai, Q., Yang, Z., Jin, C., and Wang, Z · 2019
Later among the works it cites.
Tight regret bounds for model-based reinforcement learning with greedy policies
Efroni, Y., Merlis, N., Ghavamzadeh, M., and Mannor, S · 2019
Later among the works it cites.
A theory of regularized markov decision processes
Geist, M., Scherrer, B., and Pietquin, O · 2019
Later among the works it cites.
Learning adversarial markov decision processes with bandit feedback and unknown transition
Original
Jin, C., Jin, T., Luo, H., Sra, S., and Yu, T · 2019
Later among the works it cites.
Neural proximal/trust region policy optimization attains globally optimal policy
Original
Liu, B., Cai, Q., Yang, Z., and Wang, Z · 2019
Later among the works it cites.
A modern introduction to online learning
Original
Orabona, F · 2019
Later among the works it cites.
Online convex optimization in adversarial markov decision processes
Rosenberg, A. and Mansour, Y · 2019
Later among the works it cites.
Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps
Original
Shani, L., Efroni, Y., and Mannor, S · 2019
Later among the works it cites.
On connections between constrained optimization and reinforcement learning
Original
Vieillard, N., Pietquin, O., and Geist, M · 2019
Later among the works it cites.
Model-free reinforcement learning in infinite-horizon average-reward markov decision processes
Original
Wei, C.-Y., Jafarnia-Jahromi, M., Luo, H., Sharma, H., and Jain, R · 2019
Later among the works it cites.
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Zanette, A. and Brunskill, E · 2019
Later among the works it cites.

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…