Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

2020/10/01 by He, Jiafan, Zhou, Dongruo, Gu, Quanquan · 2 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2010.00587

Abstract

We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-γ, which is based on the optimism in the face of uncertainty principle and the Bernstein-type bonus. We show that UCBVI-γ achieves an O(√(SAT)/(1-γ)^1.5) regret, where S is the number of states, A is the number of actions, γ is the discount factor and T is the number of steps. In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least Ω(√(SAT)/(1-γ)^1.5). Our upper bound matches the minimax lower bound up to logarithmic factors, which suggests that UCBVI-γ is nearly minimax optimal for discounted MDPs.

Cited by

• Scalable Policy-Based RL Algorithms for POMDPs
• Online Bayesian Risk-Averse Reinforcement Learning

Related

• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Near-optimal Reinforcement Learning in Factored MDPs
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function