This paper, authored by A. Rupam Mahmood, Hado van Hasselt, and Richard S. Sutton, addresses a long-standing hurdle in reinforcement learning (RL): how to effectively combine the stability of weighted importance sampling with the scalability of linear function approximation.
TL;DR
The authors introduce WIS-LSTD($\lambda$), a new algorithm that brings the variance-reduction benefits of Weighted Importance Sampling (WIS) to off-policy learning with linear function approximation. By reframing WIS as a least-squares problem that weights errors rather than samples, they achieve significantly faster and more reliable convergence than standard off-policy methods.
What Problem Does This Paper Address?
In reinforcement learning, off-policy learning is the "holy grail"—it allows an agent to learn about an optimal "target" policy while actually following a different "behavior" policy (perhaps one that explores more). To do this correctly, we use Importance Sampling (IS) to account for the mismatch between the two distributions.
There are two main flavors of IS:
- Ordinary Importance Sampling (OIS): Unbiased, but suffers from extremely high (sometimes infinite) variance.
- Weighted Importance Sampling (WIS): Slightly biased but much lower variance and generally more stable.
While WIS is preferred in simple "tabular" settings, it was historically difficult to use with linear function approximation (where we represent the value of a state as a weighted sum of features). Because function approximation is essential for solving large-scale, real-world problems, the lack of a "WIS-style" approach for these models was a major gap in the field.
Methods
The authors bridge this gap through a two-step theoretical move:
- Reinterpreting WIS as Least Squares: They show that while OIS can be seen as a least-squares solution where the samples are weighted, WIS is the solution where the individual squared errors are weighted by the importance-sampling ratio.
- WIS-LSTD($\lambda$): They extend this "error-weighting" logic to the Least-Squares Temporal Difference (LSTD) framework. This results in a new objective function for off-policy learning.
Crucially, they derive an efficient online algorithm. Usually, WIS requires looking at the whole dataset to normalize weights. The authors use "provisional parameters"—variables that track updates that might need to be "undone" if the behavior policy deviates too far from the target—to allow the agent to update its model step-by-step with $O(m^3)$ complexity (where $m$ is the number of features).
Datasets
The authors evaluated their algorithm on two versions of a Random-Walk Task:
- Tabular Task: An 11-state Markov chain where each state is represented by a unique "one-hot" feature vector. This tests the algorithm in a perfectly representable environment.
- Function Approximation Task: The same 11-state chain, but states are mapped to 4-component binary vectors. This forces the algorithm to approximate, as the features underrepresent the true state space.
In both cases, the behavior policy was random, while the target policy was highly biased toward one end of the chain.
Key Insights and Ideas
- Error Weighting is the Key: The "aha moment" is realizing that the difference between OIS and WIS isn't just a normalization constant; it's about what you weight. Weighting the error (the difference between your prediction and the target) provides the stability that weighting the target value lacks.
- Consistency > Unbiasedness: In RL, we often obsess over unbiased estimators. This paper reinforces the idea that a small amount of bias is a cheap price to pay for a massive reduction in variance. WIS is "consistent" (it converges to the right answer as you get more data), which is often more important in practice than being unbiased at every single step.
- Provisional Updates: The derivation of the online algorithm is a mathematical feat. It shows that even complex, non-linear weighting schemes can be implemented recursively if you track the right auxiliary variables.
Key Results
- Superior Convergence: In both the tabular and function approximation tasks, WIS-LSTD($\lambda$) converged much faster than the conventional off-policy LSTD($\lambda$) algorithm.
- Lower Error: The Mean Squared Error (MSE) for the new algorithm was often an order of magnitude lower than the baseline.
- Robustness: WIS-LSTD($\lambda$) was significantly less sensitive to hyperparameters like the regularization parameter ($\epsilon$) and the bootstrapping parameter ($\lambda$). While standard LSTD would often "blow up" with high variance for certain settings, the WIS version remained stable.
Limitations and Future Work
- Computational Cost: The current online implementation has a per-step complexity of $O(m^3)$. Standard LSTD is $O(m^2)$. While $O(m^3)$ is manageable for many problems, it is a bottleneck for very large feature sets. The authors note that they are unsure if an $O(m^2)$ version is possible.
- Linear Only: This work is strictly for linear function approximation. Extending these "error-weighting" insights to non-linear models (like Deep Neural Networks) is a clear next step for the community.
- Scaling: Future research could explore "linear-complexity" ($O(m)$) versions of this idea to make it applicable to massive, real-time systems.
Summary updated