Q-learning With Uniformly Bounded Variance: Large Discounting Is Not A Barrier To Fast Learning

Abstract

Sample complexity bounds are a common performance metric in the Reinforcement Learning literature. In the discounted cost, infinite horizon setting, all of the known bounds have a factor that is a polynomial in \(1/(1-\gamma)\), where \(\gamma < 1\) is the discount factor. For a large discount factor, these bounds seem to imply that a very large number of samples is required to achieve an \(\epsilon\)-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded for all \(\gamma < 1\). One may argue that this is impossible, due to a recent min-max lower bound. The explanation is that this previous lower bound is for a specific problem, which we modify, without compromising the ultimate objective of obtaining an \(\epsilon\)-optimal policy. Specifically, we show that the asymptotic covariance of the Q-learning algorithm with an optimized step-size sequence is a quadratic function of \(1/(1-\gamma)\); an expected

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydevraj2020q

Related papers

• Sample Complexity Of Variance-reduced Distributionally Robust Q-learning (2023)0.00
• Is Q-learning Minimax Optimal? A Tight Sample Complexity Analysis (2021)0.00
• Q-learning With UCB Exploration Is Sample Efficient For Infinite-horizon MDP (2019)0.00
• Sample Complexity Of Asynchronous Q-learning: Sharper Analysis And Variance Reduction (2020)11.19
• Variance-reduced Cascade Q-learning: Algorithms And Sample Complexity (2024)0.00
• A Minimal-assumption Analysis Of Q-learning With Time-varying Policies (2025)0.00
• Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00
• Pessimistic Q-learning For Offline Reinforcement Learning: Towards Optimal Sample Complexity (2022)0.00