Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms

Michael J. Kearns, Satinder P. SinghNeurIPS 1998 · OpenReview

Introduction

In the late 1990s, Reinforcement Learning (RL) researchers understood that algorithms like Q-learning would eventually find the optimal policy given infinite time and data (asymptotic convergence). However, there was a massive gap in understanding sample complexity: exactly how much experience does an agent actually need to get "close enough" to the best possible behavior?

Furthermore, a heated debate existed between two primary camps in RL:

  1. Direct Methods (e.g., Q-learning): These algorithms learn policies directly from experience without attempting to understand the underlying physics or transition dynamics of the world. Proponents argued this is more efficient because learning a full environmental model is inherently "harder" than just learning what action to take.
  2. Indirect Methods (Model-based): These approaches use experience to build an empirical model of the environment's transitions and rewards, then use planning algorithms (like value iteration) to find a policy. Proponents argued that having a model allows for unlimited "mental rehearsal" via off-line computation.

In this seminal paper, Kearns and Singh set out to provide a formal mathematical framework to compare these two approaches on equal footing. In doing so, they provided the first finite-sample convergence rates for both Q-learning and model-based RL, proving that both are surprisingly efficient.

Theoretical Framework: The Parallel Sampling Model

To isolate the fundamental efficiency of the learning algorithms from the specific difficulty of exploring a given environment, the authors introduced an idealized abstraction called the Parallel Sampling Model (PS(M)). This model acts as an "oracle" that, when called, provides one random transition for every state-action pair in the Markov Decision Process (MDP) simultaneously.

Using this framework, they analyzed two specific algorithms:

  • Phased Q-Learning: A variant of standard Q-learning that gathers a batch of samples for each state-action pair before performing a value update. While mathematically easier to analyze, it behaves similarly to the standard, incremental version of Q-learning.
  • The Indirect Algorithm: A model-based agent that collects samples to build an empirical transition matrix (counting how many times state $i$ led to state $j$ under action $a$) and then runs standard Value Iteration on this estimated model.

By leveraging Uniform Convergence Lemmas, the authors proved that the errors in value estimates remain tightly bounded across all states and all phases of the learning process.

Key Insights and Sample Complexity

The "Sparse Model" Surprise

Perhaps the most counter-intuitive finding of the paper is that an indirect (model-based) algorithm can find a near-optimal policy using a "terrible" model. To obtain a policy within $\epsilon$ of the optimal, the agent only needs $O(\log N)$ samples per state-action pair. This results in an extremely sparse empirical transition matrix that looks nothing like the true environment's dynamics, yet it contains enough "signal" to derive the correct optimal actions. This effectively debunked the myth that model-based methods require highly accurate models to succeed.

Direct vs. Indirect Parity

The mathematical gap between Q-learning and model-based learning turned out to be remarkably small. The indirect approach is slightly more efficient, but only by a factor of $\log(1/\epsilon)$. In the grand scheme of computational and sample complexity, both approaches are essentially in the same league.

Memory Efficiency

Because the indirect method only needs a sparse model to succeed, its memory requirements are vastly reduced. Instead of the $O(N^2)$ memory typically assumed necessary for storing full transition matrices in an $N$-state MDP, the required memory scales closer to $O(N \log N)$.

Rapid Convergence Rates

Both algorithms converge to near-optimality at a rate that is logarithmic in the number of states ($N$). The paper defines the number of calls to the sampling oracle required to be within $\epsilon$ of the optimal policy with probability $1-\delta$:

  • Indirect Algorithm: $O\left(\frac{1}{\epsilon^2} \left( \log \frac{N}{\delta} + \log \log \frac{1}{\epsilon} \right)\right)$
  • Phased Q-Learning: $O\left(\frac{\log(1/\epsilon)}{\epsilon^2} \left( \log \frac{N}{\delta} + \log \log \frac{1}{\epsilon} \right)\right)$

When translated to total transitions witnessed (by multiplying by $N$ states and $A$ actions), the sample complexity is roughly $O(N \log N)$. This was a significant advance over previous pessimistic views that suggested RL might require an impractical amount of data for large state spaces.

The authors also demonstrated how these bounds translate to real-world scenarios where an agent follows a fixed exploration policy, successfully relating the data requirements to the mixing time (how long it takes the policy to visit all parts of the state space).

Limitations and Future Directions

While foundational, this theoretical work has boundaries. The analysis is strictly constrained to MDPs with a finite, discrete number of states ($N$) and actions. It does not account for continuous state spaces or the use of function approximation (such as Deep Q-Networks).

Additionally, while the paper bridges the gap to arbitrary exploration policies, it assumes the exploration policy is fixed. It does not address the "active" exploration-exploitation trade-off where an agent dynamically changes its behavior to learn more effectively. Finally, the Parallel Sampling model is a mathematical abstraction; real-world RL agents usually receive samples sequentially along a single trajectory, introducing temporal correlations that the PS(M) model bypasses.

Summary updated

Abstract

In this paper, we address two issues of long-standing interest in the re(cid:173) inforcement learning literature. First, what kinds of performance guar(cid:173) antees can be made for Q-learning after only a finite number of actions? Second, what quantitative comparisons can be made between Q-learning and model-based (indirect) approaches, which use experience to estimate next-state distributions for off-line value iteration? We first show that both Q-learning and the indirect approach enjoy rather rapid convergence to the optimal policy as a function of the num(cid:173) ber of state transitions observed. In particular, on the order of only (Nlog(1/c)/c2 )(log(N) + loglog(l/c)) transitions are sufficient for both algorithms to come within c of the optimal policy, in an idealized model that assumes the observed transitions are "well-mixed" throughout an N-state MDP. Thus, the two approaches have roughly the same sample complexity. Perhaps surprisingly, this sample complexity is far less than what is required for the model-based approach to actually construct a good approximation to the next-state distribution. The result also shows that the amount of memory required by the model-based approach is closer to N than to N 2 • For either approach, to remove the assumption that the observed tran(cid:173) sitions are well-mixed, we consider a model in which the transitions are determined by a fixed, arbitrary exploration policy. Bounds on the number of transitions required in order to achieve a desired level of performance are then related to the stationary distribution and mixing time of this policy.
BibTeX
@inproceedings{kearns1998finite,
  author = {Michael J. Kearns and Satinder P. Singh},
  title = {{Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
  url = {https://openreview.net/forum?id=SkW41YZuWH},
}
Figure