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

Abstract

In this paper we consider the problem of learning an $\epsilon$-optimal policy for a discounted Markov Decision Process (MDP). Given an MDP with $S$ states, $A$ actions, the discount factor $\gamma \in (0,1)$, and an approximation threshold $\epsilon >0$, we provide a model-free algorithm to learn an $\epsilon$-optimal policy with sample complexity $\tilde{O}(\frac{SA\ln (1/p)}{{\epsilon }^2(1-\gamma {)}^{5.5}})$ (where the notation $\tilde{O}(\cdot )$ hides poly-logarithmic factors of $S,A,1/(1-\gamma )$, and $1/\epsilon$) and success probability $(1-p)$. For small enough $\epsilon$, we show an improved algorithm with sample complexity $\tilde{O}(\frac{SA\ln (1/p)}{{\epsilon }^2(1-\gamma {)}^3})$. 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.

References in corpus (4)

• Trust Region Policy Optimization
• Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• On the Sample Complexity of Reinforcement Learning with a Generative Model

Cited by in corpus (7)

• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs