Off-Policy Evaluation via the Regularized Lagrangian

Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, Dale Schuurmans

Introduction

In Reinforcement Learning (RL), Off-Policy Evaluation (OPE) is the critical task of estimating how well a new "target" policy will perform using only historical data collected by a different "behavior" policy. This is essential in high-stakes real-world scenarios—such as healthcare or autonomous driving—where testing an unproven policy live is too dangerous or expensive.

Recently, a family of methods known as DICE (DIstribution Correction Estimation) has advanced the state of the art in OPE. These methods estimate the ratio between the target policy's visitation distribution and the behavior policy's distribution to "correct" the historical data. However, different DICE variants (like DualDICE, GenDICE, and GradientDICE) were originally derived using seemingly incompatible mathematical tricks. This paper addresses the lack of a theoretical "map" for these methods, providing a unified framework to understand, compare, and ultimately improve them.

A Unified Framework: The Regularized Lagrangian

The authors demonstrate that the value of a policy can be expressed as the solution to a specific Linear Program (LP). This LP has two equivalent forms:

  1. The Primal (Q-LP): Solves for state-action values ($Q^\pi$).
  2. The Dual (d-LP): Solves for the stationary visitation distribution ($d^\pi$).

By forming the Lagrangian of this LP and introducing different types of regularization (to stabilize optimization) alongside redundant constraints (such as ensuring probabilities sum to 1), the authors successfully recreate all existing DICE algorithms.

Crucially, this unified framework allows researchers to mix and match components to create entirely new estimators. The paper specifically analyzes three types of estimators derived from the optimized Lagrangian:

  • Primal estimator: Relies on the learned Q-values.
  • Dual estimator: Relies on the learned visitation ratios ($\zeta$).
  • Lagrangian estimator: A "doubly robust" combination of both primal and dual variables.

Key Findings and Empirical Results

The researchers evaluated their framework across three distinct environments of varying complexity: Grid World (tabular), Cartpole (discrete action space), and Reacher (continuous action space), using both linear function approximation and neural networks.

The Superiority of the Dual Estimator

A major insight from exploring this unified space is that estimators based on the dual solution are significantly more robust and accurate than those based on the primal solution. While the RL community traditionally focuses heavily on learning Q-values (the primal), this paper finds that the dual estimator consistently yields the lowest error across tasks.

Comparison of estimator performance across environments

By identifying the optimal configuration—specifically, a dual estimator paired with dual regularization and redundant constraints—the authors discovered a "BestDICE" setup that consistently outperforms previously published DICE methods.

Robustness to Reward Transformations

One of the most striking advantages of the dual estimator is its resilience to reward scaling and shifting. In experiments where rewards were drastically scaled (e.g., multiplied by 100) or shifted, the dual estimator remained stable and accurate. In stark contrast, primal and Lagrangian estimators were severely affected by these transformations, often failing to converge entirely.

Robustness of estimators to reward scaling and shifting

The Role of Redundant Constraints

The theoretical unification also highlights the practical importance of "redundant" constraints. Adding constraints that enforce positivity on the distribution ratio or ensure normalization significantly improves optimization stability and accuracy. Even if these constraints aren't strictly necessary for the mathematics to resolve in a perfect, tabular world, they are essential for stability when using function approximators like neural networks, particularly in average-reward settings.

Limitations and Future Directions

While the regularized Lagrangian framework provides a powerful lens for OPE, challenges remain:

  • Function Approximation Bias: The paper provides a recipe for unbiased estimators in theory, but in practice, using neural networks introduces approximation errors. Eliminating bias when the function class is limited remains an open problem.
  • Hyperparameter Sensitivity: Although the dual estimator is highly robust, the choice of regularization strength still requires tuning. This is inherently difficult in strictly offline settings where validation against the true environment is impossible.

Looking forward, the authors suggest that this unified framework could be extended beyond evaluation to policy optimization (offline RL). Leveraging the regularized Lagrangian approach could pave the way for more stable algorithms capable of learning entirely new policies from scratch using offline data.

Summary updated

Abstract

The recently proposed distribution correction estimation (DICE) family of estimators has advanced the state of the art in off-policy evaluation from behavior-agnostic data. While these estimators all perform some form of stationary distribution correction, they arise from different derivations and objective functions. In this paper, we unify these estimators as regularized Lagrangians of the same linear program. The unification allows us to expand the space of DICE estimators to new alternatives that demonstrate improved performance. More importantly, by analyzing the expanded space of estimators both mathematically and empirically we find that dual solutions offer greater flexibility in navigating the tradeoff between optimization stability and estimation bias, and generally provide superior estimates in practice.
BibTeX
@inproceedings{yang2020off,
  author = {Mengjiao Yang and Ofir Nachum and Bo Dai and Lihong Li and Dale Schuurmans},
  title = {{Off-Policy Evaluation via the Regularized Lagrangian}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=SuW4J2m9cx5},
}
Figure