Off-policy learning based on weighted importance sampling with linear computational complexity

Ashique Rupam Mahmood, Richard S. SuttonUAI 2015 · OpenReview

Abstract

This paper introduces the first reinforcement learning algorithms that achieve the variance-reduction benefits of Weighted Importance Sampling (WIS) with linear computational complexity ($O(n)$). By developing a novel adaptive step-size technique based on "feature usage" and a generalized online equivalence framework, the authors bridge the gap between high-performance but expensive batch methods and efficient but high-variance online algorithms. The resulting algorithms, such as WIS-TD($\lambda$), demonstrate superior performance across multiple benchmarks while maintaining the scalability required for large-scale problems.

1. Introduction

In reinforcement learning, off-policy learning allows an agent to learn about a "target" policy while following a different "behavior" policy. This is crucial for learning from historical data or exploring safely. To correct the mismatch between these policies, researchers use Importance Sampling (IS). Ordinary Importance Sampling (OIS) is simple to implement but often suffers from extreme variance, making learning unstable. Weighted Importance Sampling (WIS) provides much lower variance and is generally preferred in practice. However, when using function approximation, WIS previously required computational complexity of $O(n^2)$ or $O(n^3)$, where $n$ is the number of features. This paper solves this "complexity tax," bringing WIS to the world of efficient, linear-time algorithms.

2. Methodology

The authors achieve linear-time WIS through three key innovations:

2.1 Usage-based SGD (U-SGD)

The authors identified that standard Stochastic Gradient Descent (SGD) does not naturally reduce to a simple sample average in the tabular case. They introduced a "usage vector" $\mathbf{u}$ that tracks how much each feature has been used over time. This vector is used to determine component-wise adaptive step sizes, effectively mimicking a sample average within a gradient descent framework.

2.2 WIS-SGD Algorithms

Two new off-policy SGD variants were derived. While the first (WIS-SGD-1) is a direct translation of WIS but remains computationally expensive, the second (WIS-SGD-2) is specifically designed to be compatible with efficient, linear-time updates.

2.3 Generalized Online Equivalence

To make these algorithms practical, the authors developed a new mathematical "online equivalence" technique. This allows them to take an intuitive but "acausal" algorithm (one that requires looking into the future) and transform it into a "causal" backward-view algorithm using eligibility traces. This technique introduces "provisional weights" into online updates for the first time, providing a general tool for deriving $O(n)$ algorithms like the flagship WIS-TD($\lambda$).

3. Experimental Evaluation

The algorithms were evaluated on three primary benchmarks:

  1. 11-State Random Walk: A classic environment for testing basic convergence and variance.
  2. Small Random MDP (10 states): Tests performance in more complex state-transition structures.
  3. Large Random MDP (100 states): Evaluates scaling and performance with more features.

Performance was measured using Normalized Mean Squared Error (NMSE) across a range of the trace decay parameter $\lambda$.

4. Key Results

Empirical results confirm that the new WIS-based $O(n)$ algorithms significantly outperform existing linear-time methods.

Performance comparison across three benchmarks: Random Walk (11 states), Small MDP (10 states), and Large MDP (100 states). The new WIS-based algorithms (WIS-TD, WIS-GTD) consistently outperform standard $O(n)$ methods like GTD and TO-GTD, often approaching the performance of the $O(n^3)$ WIS-LSTD.

As illustrated in the figures, WIS-TD($\lambda$) and WIS-GTD($\lambda$) provide substantial variance reduction compared to standard $O(n)$ algorithms like GTD($\lambda$) and True Online GTD($\lambda$). Remarkably, these linear-time algorithms perform competitively with WIS-LSTD($\lambda$), which is much more computationally expensive ($O(n^3)$). Furthermore, the usage-based step-size technique (U-TD) improved performance even in on-policy settings, particularly at higher values of $\lambda$.

5. Conclusion and Future Work

This work provides a scalable solution for low-variance off-policy learning. By reconciling SGD with sample averages through feature usage, the authors have enabled the practical use of WIS in large-scale reinforcement learning. While the algorithm introduces new hyperparameters ($u_0$ and $\eta$), they are unit-free and potentially easier to tune than standard step sizes. Future research will focus on formal theoretical convergence analysis and integrating these usage-based insights into other adaptive optimizers like Adam or vSGD.

Summary updated

BibTeX
@inproceedings{mahmood2015off,
  author = {Ashique Rupam Mahmood and Richard S. Sutton},
  title = {{Off-policy learning based on weighted importance sampling with linear computational complexity}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=-9OPcjwCh0Y},
}
Figure