Sample-Optimal Parametric Q-Learning Using Linearly Additive Features

Lin Yang, Mengdi WangICML 2019 · OpenReview

TL;DR

This paper introduces the first sample-optimal Q-learning algorithm for large-scale Markov Decision Processes (MDPs) that use linear features to represent transition dynamics. By leveraging variance reduction and a "monotonicity" property, the authors prove that their algorithm finds a near-optimal policy using a number of samples proportional only to the feature dimension ($K$), making it completely independent of the total number of states ($S$).

What Problem Does This Paper Address?

In Reinforcement Learning, the "curse of dimensionality" is a constant foe. In a standard "tabular" setting, the number of samples needed to learn a good policy scales with the number of states ($S$) and actions ($A$). If you are dealing with raw pixels or complex sensor data, $S$ can be effectively infinite, making tabular methods useless.

To solve this, researchers use function approximation, assuming that states can be represented by a smaller set of $K$ features. However, most existing algorithms either lack theoretical guarantees or are "sample-inefficient"—meaning they require far more data than theoretically necessary to reach a specific accuracy ($\epsilon$). The authors set out to find the absolute theoretical limit (the lower bound) for how many samples are needed in a linear transition model and then build an algorithm that actually hits that limit (the upper bound).

Methods

The paper focuses on a Feature-based Linear Transition Model, where the probability of moving to a new state is a linear combination of known features $\phi(s, a)$.

The authors propose two algorithms:

  1. PPQ-Learning (Phased Parametric Q-Learning): A basic version that performs value iteration on the parameters of the Q-function. While simple, it is not sample-optimal.
  2. OPPQ-Learning (Optimal Phased Parametric Q-Learning): This is the "star" of the paper. It achieves optimality through three clever tricks:
  3. Variance Reduction: It uses an outer loop to establish a high-accuracy "reference" value and an inner loop to refine it using smaller mini-batches. This prevents noise from overwhelming the learning process.
  4. Monotonicity Preservation: Using an "Anchor State" assumption (the idea that a small set of "basis" state-action pairs can represent all others via convex combinations), the algorithm ensures that value estimates improve monotonically. This prevents the "oscillations" often seen when combining Q-learning with linear approximation.
  5. Confidence Bounds: It shifts estimates downward based on calculated uncertainty, ensuring the algorithm stays conservative and approaches the optimal value from below.

Datasets

As a theoretical paper focused on proving sample complexity bounds, no empirical datasets (like Atari or MuJoCo) were used. The "evaluation" consists of rigorous mathematical proofs demonstrating that the algorithm's performance matches the information-theoretic lower bounds.

Key Insights and Ideas

  • The "Anchor" Secret Sauce: The most critical insight is the use of Anchor State-Action Pairs. By assuming these anchors exist, the authors can treat the transition kernel as having a non-negative factorization. This is the mathematical "bridge" that allows them to maintain monotonicity in the feature space, which is usually lost in linear models.
  • Bridging Models: The authors prove that a linear transition model is essentially equivalent to a linear Q-function model with "zero Bellman error." This provides a strong theoretical justification for using linear features in Q-learning.
  • Independence of State Space: The sample complexity depends on the feature dimension $K$, not the state space size $S$. This means you could have a trillion states, but if they can be described by 100 features, the problem remains tractable.

Key Results

  • Information-Theoretic Lower Bound: The authors prove that any algorithm requires at least $\Omega\left(\frac{K}{(1-\gamma)^3 \epsilon^2}\right)$ samples to find an $\epsilon$-optimal policy.
  • Sample Optimality: Their OPPQ-Learning algorithm achieves an upper bound of $\tilde{O}\left(\frac{K}{(1-\gamma)^3 \epsilon^2}\right)$. Because the upper and lower bounds match (up to logarithmic factors), the algorithm is considered sample-optimal.
  • Massive Efficiency Gains: Compared to their basic algorithm (PPQ), the optimized version (OPPQ) is significantly faster. For a discount factor of $\gamma = 0.99$, the optimized version is theoretically $10^8$ times more sample-efficient.

Limitations and Future Work

  • Generative Model Requirement: The algorithm assumes access to a "generative model" (a simulator), meaning it can query transitions for any state-action pair at any time. This is common in simulation but doesn't apply to "online" RL where an agent must move through the environment sequentially.
  • The Anchor Assumption: While the authors argue that the anchor assumption is a natural analog to conditions in topic modeling, it may not hold for all real-world feature sets.
  • Beyond Linearity: The paper is strictly limited to linear additive features. A natural next step is extending these sample-optimal guarantees to non-linear function approximators, such as neural networks.

Summary updated

Abstract

Consider a Markov decision process (MDP) that admits a set of state-action features, which can linearly express the process’s probabilistic transition model. We propose a parametric Q-learning algo...
BibTeX
@inproceedings{yang2019sample,
  author = {Lin Yang and Mengdi Wang},
  title = {{Sample-Optimal Parametric Q-Learning Using Linearly Additive Features}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=ryVMl2bOWH},
}
Figure