Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning

Understand

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 $\varepsilon$-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$.