Regret Bounds for Reinforcement Learning via Markov Chain Concentration

2018/08/06 by Ortner, Ronald · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1808.01813

Abstract

We give a simple optimistic algorithm for which it is easy to derive regret bounds of O(√t_{\rm mix} SAT) after T steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t_{\rm mix}. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.

Cited by

• Infinite-Dimensional Operator/Block Kaczmarz Algorithms: Regret Bounds and λ-Effectiveness

Related

• Variational Regret Bounds for Reinforcement Learning
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Posterior sampling for reinforcement learning: worst-case regret bounds
• Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs
• Square-root regret bounds for continuous-time episodic Markov decision processes