Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis

A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation

(2021) Jalaj Bhandari et al.   OPERATIONS RESEARCH

Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction

(2021) Gen Li et al.   IEEE TRANSACTIONS ON INFORMATION THEORY

Instance-Dependent ℓ∞-Bounds for Policy Evaluation in Tabular Reinforcement Learning

(2020) Ashwin Pananjady et al.   IEEE TRANSACTIONS ON INFORMATION THEORY

Concentration inequalities for Markov chains by Marton couplings and spectral methods

(2015) Daniel Paulin   ELECTRONIC JOURNAL OF PROBABILITY

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

(2013) Mohammad Gheshlaghi Azar et al.   MACHINE LEARNING

Error bounds for constant step-size -learning

(2012) C.L. Beck et al.   SYSTEMS & CONTROL LETTERS