The Challenge of Off-Policy Evaluation
In Reinforcement Learning (RL), Off-Policy Evaluation (OPE) is the critical task of estimating a new policy's performance using only historical data collected by a different, older policy. This is essential for high-stakes real-world applications—like healthcare or autonomous driving—where deploying an untested, potentially flawed policy is too risky.
Traditionally, the "gold standard" for OPE has been Importance Sampling. However, it suffers from the "curse of horizon": its variance grows exponentially as the task length increases. To mitigate this, researchers have turned to minimax methods that rely on function approximation for two key components:
- Value functions ($Q$): Estimating the expected long-term reward.
- Marginalized importance weights ($w$): Correcting the distribution shift between the historical data and the new target policy.
While promising, these minimax methods have historically been fragmented into competing "weight-learning" and "value-learning" styles. Furthermore, because they rely on function approximation, they introduce biases that are notoriously difficult to quantify.
A Unified Minimax Value Interval
This paper bridges the gap between these fragmented approaches by slightly modifying the underlying math to derive a unified Minimax Value Interval.
Instead of producing a single, potentially biased point estimate, the authors solve for an upper bound ($UB$) and a lower bound ($LB$). The core of their method relies on a loss function based on the Bellman equation:
- Weight-learning style: Searches for a weight function that minimizes the worst-case error across a class of "discriminator" value functions.
- Value-learning style: Searches for a value function that minimizes error across a class of weight functions.
The authors prove that if the function classes are convex and compact, these two styles are mathematically the reverse of each other. By computing both, practitioners obtain a single interval $[LB, UB]$. Crucially, this interval exhibits a powerful form of double robustness: it is guaranteed to contain the true value of the policy as long as at least one of your function classes (either $Q$ or $w$) is "realizable" (i.e., capable of representing the true function).
Key Insights: Interval Reversal and Bias Quantification
Unlike previous methods that output a single number, the length of this new interval ($UB - LB$) directly quantifies the misspecification of the function classes. A wide interval serves as a warning: "The function approximators cannot be trusted here."
A fascinating theoretical and empirical finding in the paper is the Interval Reversal phenomenon.
Which bound acts as the "upper" versus the "lower" bound depends entirely on the expressivity of the function classes. As shown in the CartPole experiments above, if the value-function class $Q$ is too small (poorly specified), the bounds can actually "flip." This reversal provides a valuable diagnostic hint about which part of the model architecture is failing.
Policy Optimization Under Non-Exploratory Data
The authors also extend their interval to policy optimization. They observe that "insufficient data coverage"—when historical data fails to visit states the new policy wants to explore—can be treated mathematically as a special case of weight-class misspecification.
By optimizing the bounds of the interval, the framework naturally balances exploration and exploitation:
- Optimizing the upper bound leads to optimism (encouraging efficient exploration).
- Optimizing the lower bound leads to pessimism (ensuring safe exploitation).
The authors demonstrated that their lower-bound-based algorithm (MLB-PO) could reliably optimize policies even when restricted to non-exploratory data. As seen in the results above, MLB-PO successfully learns a high-performing policy, whereas standard deep RL methods like DQN become highly unstable and fail in the same setting.
Limitations and Future Directions
While the Minimax Value Interval represents a significant step forward for trustworthy RL, several challenges remain:
- Statistical Errors: The core theory assumes infinite data (exact expectations). While the authors successfully use bootstrapping to maintain valid intervals with finite samples, rigorously integrating sampling error with approximation bias theory is an open challenge.
- Optimization Difficulty: Jointly optimizing the policy ($\pi$), weights ($w$), and value functions ($q$) creates a "min-max-max" or "min-min-max" objective. Stabilizing this optimization, especially with deep neural networks, remains practically difficult.
- Realizability Assumption: The double robustness guarantee still requires one of the two classes to be well-specified. Developing an interval that remains valid even when both classes are misspecified is a high-bar goal for future research.
Summary updated