Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting. We propose a model-based algorithm named UCBVI-$\gamma$, which is based on the \emph{optimism in the …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-…
Multi-Armed Banditsreinforcement-learningReinforcement LearningReinforcement Learning (RL)Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
Modern tasks in reinforcement learning have large state and action spaces. To deal with them efficiently, one often uses predefined feature mapping to represent states and actions in a low-dimensional space. In this pape…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs
Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon ta…
Multi-Armed Banditsreinforcement-learningReinforcement LearningReinforcement Learning (RL)Variational Regret Bounds for Reinforcement Learning
We consider undiscounted reinforcement learning in Markov decision processes (MDPs) where both the reward functions and the state-transition probabilities may vary (gradually or abruptly) over time. For this problem sett…
General Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)