On the Sample Complexity of Reinforcement Learning with a Generative Model

2012/06/27 by Mohammad Gheshlaghi Azar, Remi Munos, Azar, Mohammad Gheshlaghi +3 · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1206.6461

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

arxiv created 2012/06/27 · arxiv updated 2012/07/02

Abstract

We consider the problem of learning the optimal action-value function in the discounted-reward Markov decision processes (MDPs). We prove a new PAC bound on the sample-complexity of model-based value iteration algorithm in the presence of the generative model, which indicates that for an MDP with N state-action pairs and the discount factor γ∈[0,1) only O(Nlog(N/δ)/((1-γ)³ε²)) samples are required to find an ε-optimal estimation of the action-value function with the probability 1-δ. We also prove a matching lower bound of Θ(Nlog(N/δ)/((1-γ)³ε²)) on the sample complexity of estimating the optimal action-value function by every RL algorithm. To the best of our knowledge, this is the first matching result on the sample complexity of estimating the optimal (action-) value function in which the upper bound matches the lower bound of RL in terms of N, ε, δand 1/(1-γ). Also, both our lower bound and our upper bound significantly improve on the state-of-the-art in terms of 1/(1-γ).

Cited by

• Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
• Position: RL Researchers Need to Distinguish Between Solving Simulators and Using Simulators as a Proxy

Related

• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Optimal Sample Complexity for Average Reward Markov Decision Processes
• Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model
• Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes