Linear Approximate Value Iteration (LAVI) is a powerful tool for reinforcement learning (RL) in environments with massive or continuous state spaces. However, it is notorious for diverging because least-squares projections can amplify errors exponentially. This paper introduces LAVIER (Linear AVI with Extrapolation Reduction), an algorithm that uses "anchor points" and interpolation to bound error propagation. LAVIER provides the first polynomial sample complexity guarantees for linear AVI while remaining stable on classic counterexamples where traditional methods fail.
The Problem: The "Deadly Triad" and Extrapolation
In reinforcement learning, estimating the "value" of being in a certain state is crucial. When state spaces are too large to memorize, practitioners use LAVI to represent these values as a linear combination of features.
However, LAVI suffers from the "deadly triad": combining function approximation, bootstrapping (using current estimates to update future ones), and off-policy sampling can lead to divergence. The standard approach uses least-squares regression to fit the value function. If the Bellman operator (the update rule) pushes the function into a shape that the linear model cannot perfectly represent, the least-squares projection can wildly "extrapolate." This extrapolation magnifies small errors at every step until the entire system blows up.
The authors aim to bridge the gap between stable but computationally expensive "averagers" (like nearest-neighbors) and efficient but unstable linear models.
The Solution: LAVIER and Anchor Points
The authors propose LAVIER, built on a core subroutine called IER (Interpolation for Extrapolation Reduction). The algorithm shifts away from fitting all data points equally and instead relies on a constrained interpolation strategy:
- Anchor Points: The algorithm selects a specific set of "anchor" state-action pairs rather than treating all states equally.
- Pointwise Estimation: It estimates the Q-values (action-values) specifically at these anchor points using samples from a generative model (a simulator).
- Constrained Interpolation: To predict the value of a new, unseen state, the algorithm solves a linear optimization problem to find an "interpolation vector." This vector reconstructs the features of the new state as a combination of the features of the anchor points.
- Amplification Control: The key innovation is minimizing the $\ell_1$-norm of these interpolation weights. This norm acts as an amplification factor. By keeping it small, the algorithm ensures that errors from one iteration do not explode in the next.
Evaluation and Key Results
The paper evaluates LAVIER on synthetic environments specifically designed to test theoretical stability and error propagation.
Preventing Divergence in Classic Counterexamples
The most famous test case for this problem is Tsitsiklis and Van Roy’s Two-State MDP, a "minimal" counterexample where standard least-squares AVI is mathematically proven to diverge.
As shown above, while traditional LS-AVI diverges rapidly (the red line showing value function error exploding over the horizon), LAVIER remains completely stable and converges to the correct values (the flat blue line). The paper identifies that the primary cause of divergence in linear RL isn't just the approximation error itself, but how that error is amplified when projected onto the linear space. By keeping the amplification factor $\le 1$, errors propagate linearly (slowly) rather than exponentially.
Superior Performance in Chain MDPs
The authors also tested the algorithm on a Chain MDP, a 50-state environment used to evaluate how well the algorithm handles suboptimality and noisy rewards over a long horizon.
In this environment, LAVIER consistently achieves lower suboptimality compared to LS-AVI across varying sample sizes. Unlike standard "averagers" which can be very biased, LAVIER's interpolation is designed to be "exact" if the underlying value function is truly linear, meaning it doesn't sacrifice the strengths of linear modeling for the sake of stability.
Theoretical Guarantees
Beyond empirical success, the authors prove a polynomial sample complexity bound of $\tilde{O}(KH^5/\epsilon^2)$. This means the number of samples needed to find a good policy scales reasonably with the number of anchors ($K$) and the time horizon ($H$).
Limitations and Future Work
While LAVIER offers a robust solution to extrapolation, it comes with a few trade-offs:
- Anchor Selection Complexity: Finding the absolute minimum set of anchor points to satisfy stability conditions is an NP-hard problem. While the authors' greedy heuristic works well, it isn't guaranteed to be optimal.
- Feature Dependency: Like all linear methods, performance is strictly limited by the quality of the human-designed (or pre-learned) feature map.
- Generative Model Requirement: The current analysis assumes access to a generative model (the ability to sample any state-action pair), which isn't always available in real-world "online" RL.
Future directions include developing adaptive versions of the algorithm that can identify where extrapolation is happening during training and add new anchor points on the fly, as well as extending this framework to batch RL settings.
Summary updated