Understand
We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner.
- We show $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A$ is the action space, and $L$ is the length of each episode.
- Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode) , as well as improve previous regret bounds.
Built on
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Puterman, M. L · 1994
Earlier work this paper cites.
Efficient algorithms for online decision problems
Kalai, A. and Vempala, S · 2003
Earlier work this paper cites.
Convex Optimization
Boyd, S. and Vandenberghe, L · 2004
Earlier work this paper cites.
Online Markov Decision Processes
Even-Dar, E., Kakade, S. M., and Mansour, Y · 2004
Earlier work this paper cites.
Prediction, learning, and games
Cesa-Bianchi, N. and Lugosi, G · 2006
Earlier work this paper cites.
Similar
Near-optimal regret bounds for reinforcement learning
Auer, P., Jaksch, T., and Ortner, R · 2008
Cited alongside, same era.
REGAL: A regularization based algorithm for reinforcement learning in weakly communicating mdps
Bartlett, P. L. and Tewari, A · 2009
Cited alongside, same era.
Markov Decision Processes with arbitrary reward processes
Yu, J. Y., Mannor, S., and Shimkin, N · 2009
Cited alongside, same era.
The online loop-free stochastic shortest-path problem
Neu, G., György, A., and Szepesvári, C · 2010
Cited alongside, same era.
The adversarial stochastic shortest path problem with unknown transition probabilities
Neu, G., György, A., and Szepesvári, C · 2012
Cited alongside, same era.
Then
Online learning and online convex optimization
Shalev-Shwartz, S · 2012
Later among the works it cites.
Online learning in episodic markovian decision processes by relative entropy policy search
Zimin, A. and Neu, G · 2013
Later among the works it cites.
Online Markov Decision Processes under bandit feedback
Neu, G., György, A., Szepesvári, C., and Antos, A · 2014
Later among the works it cites.
Minimax regret bounds for reinforcement learning
Azar, M. G., Osband, I., and Munos, R · 2017
Later among the works it cites.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…