Improved Analysis of UCRL2 with Empirical Bernstein Inequality

Abstract

We consider the problem of exploration-exploitation in communicating Markov Decision Processes. We provide an analysis of UCRL2 with Empirical Bernstein inequalities (UCRL2B). For any MDP with $S$ states, $A$ actions, $\Gamma \le S$ next states and diameter $D$, the regret of UCRL2B is bounded as $\tilde{O}(\sqrt{D\Gamma SAT})$.

arXiv commentDocument in support of the tutorial at ALT 2019

Cited by in corpus (8)

• Understanding Domain Randomization for Sim-to-real Transfer
• No-Regret Exploration in Goal-Oriented Reinforcement Learning
• Tightening Exploration in Upper Confidence Reinforcement Learning
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Improved Exploration in Factored Average-Reward MDPs