Policy Evaluation Using the Ω-Return

Philip S. Thomas, Scott Niekum, Georgios Theocharous, George KonidarisNeurIPS 2015 · OpenReview

TL;DR

The $\Omega$-return introduces a novel approach to estimating the value of a policy in reinforcement learning by accounting for the statistical correlations between returns of different lengths. By treating policy evaluation as a Generalized Least Squares problem, it consistently outperforms the industry-standard $\lambda$-return and the more recent $\gamma$-return in accuracy, yielding significantly lower Mean Squared Error.

Introduction

In reinforcement learning, "policy evaluation" is the task of estimating how much reward a specific strategy (policy) will gather over time. Traditionally, researchers use complex backups—weighted averages of $n$-step returns—to form these estimates.

For decades, the gold standard has been the $\lambda$-return, which blends short-term estimates (low variance, high bias) with long-term Monte Carlo observations (high variance, low bias). However, the $\lambda$-return is built on a flawed statistical foundation: it assumes that returns of different lengths are independent and that their variance grows geometrically.

In reality, a 19-step return and a 20-step return from the same state are almost perfectly correlated because they share nearly all the same rewards. Ignoring this correlation leads to inefficient estimates. This paper introduces the $\Omega$-return to fix this by explicitly modeling the covariance between returns of different lengths.

The $\Omega$-Return Methodology

The authors reformulate the problem of combining different length returns as a linear regression problem.

  1. Generalized Least Squares (GLS): Instead of using arbitrary decay weights (like $\lambda$), they use GLS to find the Best Linear Unbiased Estimator (BLUE). This requires a covariance matrix, $\Omega$, which tracks how returns of different lengths vary together.
  2. The $\Omega$ Weighting Scheme: The weights for the $\Omega$-return are derived directly from the inverse of the covariance matrix. This allows the algorithm to "de-duplicate" information from highly correlated returns, extracting more information from fewer trajectories.
  3. Approximation (App $\Omega$): Because the true covariance matrix $\Omega$ is rarely known and hard to estimate from limited data, the authors propose a compact 4-parameter model to approximate it. This model assumes a smooth growth in variance and leverages the Markov property to simplify off-diagonal correlations.

Experimental Setup & Results

The authors evaluated the $\Omega$-return on four diverse domains: a standard 5x5 Gridworld, the classic Mountain Car continuous-state control problem, a real-world Digital Marketing dataset, and Functional Electrical Stimulation (FES) for biomedical engineering.

Comparison of empirical vs. approximate covariance matrices (top), variance and weight distributions (bottom left/middle), and Mean Squared Error across different return types (bottom right).

The primary metric for evaluation was Mean Squared Error (MSE) in off-policy evaluation.

  • Superior Accuracy: Across all four domains, the $\Omega$-return (both empirical and approximate versions) achieved lower MSE than the $\gamma$-return and the $\lambda$-return for any choice of $\lambda \in [0, 1]$.
  • Data Efficiency: In the Mountain Car and Gridworld tasks, the approximate $\Omega$-return provided much more stable estimates when only a handful of trajectories were available. In contrast, the empirical covariance matrix from small data was too noisy to be useful.
  • Robustness of Approximation: Even with a simple 4-parameter approximation of the complex covariance matrix, the $\Omega$-return significantly outperformed fine-tuned $\lambda$ values. This suggests that capturing the structure of the correlation is far more important than having a perfect estimate of every individual covariance value.
  • Generalization: The paper demonstrates that both the $\lambda$-return and $\gamma$-return are actually special, restricted cases of the $\Omega$-return where the covariance matrix is forced to be diagonal (falsely assuming zero correlation).

Limitations and Future Work

While highly accurate, the $\Omega$-return has a few current limitations:

  • Computational Complexity: Unlike the $\lambda$-return, which can be updated online in linear time, the $\Omega$-return currently requires batch processing of trajectories and matrix inversions. Finding a "linear-time" version is a key open question.
  • Batch Requirement: It requires a set of trajectories to estimate the covariance, making it less straightforward for purely online, single-stream learning.
  • Bias vs. Variance: The estimator assumes returns are unbiased. In many RL settings, returns are biased because they rely on an imperfect value function estimate. Future work could explore "biased" versions of the $\Omega$-return that might further reduce MSE.

Extending this methodology from pure policy evaluation to full policy improvement (control) with function approximation remains an exciting frontier for future research.

Summary updated

Abstract

We propose the Ω-return as an alternative to the λ-return currently used by the TD(λ) family of algorithms. The benefit of the Ω-return is that it accounts for the correlation of different length returns. Because it is difficult to compute exactly, we suggest one way of approximating the Ω-return. We provide empirical studies that suggest that it is superior to the λ-return and γ-return for a variety of problems.
BibTeX
@inproceedings{thomas2015policy,
  author = {Philip S. Thomas and Scott Niekum and Georgios Theocharous and George Konidaris},
  title = {{Policy Evaluation Using the Ω-Return}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=B1V2uubOWH},
}
Figure