2020/06/06 by Zihan Zhang, Yuan Zhou, Zhang, Zihan +3 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #Algorithm #Artificial intelligence #Combinatorics #Computational complexity theory #Computer science #Discrete mathematics #FOS: Computer and information sciences #Logarithm #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov decision process #Markov process #Mathematical analysis #Mathematics #Regret #Reinforcement Learning in Robotics #Reinforcement learning #Sample complexity #Statistics #Tilde #Upper and lower bounds #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2006.03864
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2020/06/06 · arxiv created 2020/12/24 · arxiv updated 2020/12/25 · openalex created_date 2021/06/22 · openalex updated_date 2026/07/28
In this paper we consider the problem of learning an \ε-optimal\npolicy for a discounted Markov Decision Process (MDP). Given an MDP with S\nstates, A actions, the discount factor \γ \∈ (0,1), and an\napproximation threshold \ε > 0, we provide a model-free algorithm to\nlearn an \ε-optimal policy with sample complexity\n\O( fracSA\ln(1/p)\ε2(1-\γ)5.5) (where the notation\n\O(\⋅) hides poly-logarithmic factors of S,A,1/(1-\γ), and\n1/\ε) and success probability (1-p). For small enough \ε, we\nshow an improved algorithm with sample complexity\n\O( fracSA\ln(1/p)\ε2(1-\γ)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