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.
- 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.
- 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.
- 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.
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