Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition

Abstract

We study the reinforcement learning problem in the setting of finite-horizon episodic Markov Decision Processes (MDPs) with $S$ states, $A$ actions, and episode length $H$. We propose a model-free algorithm UCB-Advantage and prove that it achieves $\tilde{O}(\sqrt{H^{2}SAT})$ regret where $T=KH$ and $K$ is the number of episodes to play. Our regret bound improves upon the results of [Jin et al., 2018] and matches the best known model-based algorithms as well as the information theoretic lower bound up to logarithmic factors. We also show that UCB-Advantage achieves low local switching cost and applies to concurrent reinforcement learning, improving upon the recent results of [Bai et al., 2019].

arXiv comment26 pages

References in corpus (9)

• Trust Region Policy Optimization
• Dueling Network Architectures for Deep Reinforcement Learning
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Minimax Regret Bounds for Reinforcement Learning
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Provably Efficient Q-Learning with Low Switching Cost
• Variance Reduction Methods for Sublinear Reinforcement Learning
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Cited by in corpus (28)

• Model-Based Reinforcement Learning with Value-Targeted Regression
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• $Q$-learning with Logarithmic Regret
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Task-agnostic Exploration in Reinforcement Learning
• UCB Momentum Q-learning: Correcting the bias without forgetting
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learning
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation
• Online Learning in Unknown Markov Games
• Can Q-Learning be Improved with Advice?