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

In this paper we consider the problem of learning an $\\epsilon$-optimal\npolicy for a discounted Markov Decision Process (MDP). Given an MDP with $S$\nstates, $A$ actions, the discount factor $\\gamma \\in (0,1)$, and an\napproximation threshold $\\epsilon > 0$, we provide a model-free algorithm to\nlearn an $\\epsilon$-optimal policy with sample complexity\n$\\tilde{O}(\\frac{SA\\ln(1/p)}{\\epsilon^2(1-\\gamma)^{5.5}})$ (where the notation\n$\\tilde{O}(\\cdot)$ hides poly-logarithmic factors of $S,A,1/(1-\\gamma)$, and\n$1/\\epsilon$) and success probability $(1-p)$. For small enough $\\epsilon$, we\nshow an improved algorithm with sample complexity\n$\\tilde{O}(\\frac{SA\\ln(1/p)}{\\epsilon^2(1-\\gamma)^{3}})$. While the first bound\nimproves upon all known model-free algorithms and model-based ones with tight\ndependence on $S$, our second algorithm beats all known sample complexity\nbounds and matches the information theoretic lower bound up to logarithmic\nfactors.\n