Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time

2023/05/24 by Ji, Xiang, Li, Gen · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2305.15546

Abstract

A crucial problem in reinforcement learning is learning the optimal policy. We study this in tabular infinite-horizon discounted Markov decision processes under the online setting. The existing algorithms either fail to achieve regret optimality or have to incur a high memory and computational cost. In addition, existing optimal algorithms all require a long burn-in time in order to achieve optimal sample efficiency, i.e., their optimality is not guaranteed unless sample size surpasses a high threshold. We address both open problems by introducing a model-free algorithm that employs variance reduction and a novel technique that switches the execution policy in a slow-yet-adaptive manner. This is the first regret-optimal model-free algorithm in the discounted setting, with the additional benefit of a low burn-in time.

Cited by

• Statistical and Algorithmic Foundations of Reinforcement Learning

Related

• A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regret
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
• Fast Rates for the Regret of Offline Reinforcement Learning
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes