Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
arXiv:1905.11527
Abstract
State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing \emph{full-planning} on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon MDP setting and establish that exploring with \emph{greedy policies} -- act by \emph{1-step planning} -- can achieve tight minimax performance in terms of regret, . Thus, full-planning in model-based RL can be avoided altogether without any performance degradation, and, by doing so, the computational complexity decreases by a factor of . The results are based on a novel analysis of real-time dynamic programming, then extended to model-based RL. Specifically, we generalize existing algorithms that perform full-planning to such that act by 1-step planning. For these generalizations, we prove regret bounds with the same rate as their full-planning counterparts.
arXiv commentNeurIPS 2019
References in corpus (10)
- (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
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
- Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
- On Lower Bounds for Regret in Reinforcement Learning
- Planning by Prioritized Sweeping with Small Backups
- Policy Certificates: Towards Accountable Reinforcement Learning
- Feedback-Based Tree Search for Reinforcement Learning
- Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs