Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities

Abstract

We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret $\tilde{\mathcal{O}}(\sqrt{DSAT})$ up to logarithmic factors, and so our work closes a gap with the lower bound without additional assumptions on the MDP. We perform experiments in a variety of environments that validates the theoretical bounds as well as prove UCRL-V to be better than the state-of-the-art algorithms.

arXiv commentthe algorithm has been simplified (no need to look at lower bound of the reward and transitions). Proof has been significantly clean-up. The previous "assumption" is clarified as a condition of the algorithm well-known as sub-modularity. The proof that the bounds satisfy the submodularity is clean-up

References in corpus (7)

• (More) Efficient Reinforcement Learning via Posterior Sampling
• Empirical Bernstein Bounds and Sample Variance Penalization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Minimax Regret Bounds for Reinforcement Learning
• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Cited by in corpus (9)

• Learning Near Optimal Policies with Low Inherent Bellman Error
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Tactical Optimism and Pessimism for Deep Reinforcement Learning
• Exploratory Grasping: Asymptotically Optimal Algorithms for Grasping Challenging Polyhedral Objects
• A Survey of Exploration Methods in Reinforcement Learning
• Towards Tractable Optimism in Model-Based Reinforcement Learning
• Reinforcement Learning in Reward-Mixing MDPs
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process
• Communication Efficient Parallel Reinforcement Learning