Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity

2020/06/06 by Zhang, Zihan, Zhou, Yuan, Ji, Xiangyang · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2006.03864

Abstract

In this paper we consider the problem of learning an ε-optimal policy for a discounted Markov Decision Process (MDP). Given an MDP with S states, A actions, the discount factor γ∈ (0,1), and an approximation threshold ε> 0, we provide a model-free algorithm to learn an ε-optimal policy with sample complexity O(\fracSAln(1/p)ε²(1-γ)^5.5) (where the notation O(⋅) hides poly-logarithmic factors of S,A,1/(1-γ), and 1/ε) and success probability (1-p). For small enough ε, we show an improved algorithm with sample complexity O(\fracSAln(1/p)ε²(1-γ)³). While the first bound improves upon all known model-free algorithms and model-based ones with tight dependence on S, our second algorithm beats all known sample complexity bounds and matches the information theoretic lower bound up to logarithmic factors.

Cited by

• Statistical and Algorithmic Foundations of Reinforcement Learning
• Improving Reinforcement Learning Sample-Efficiency using Local Approximation

Related

• Near-Optimal Sample Complexity for MDPs via Anchoring
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?