In reinforcement learning, we usually ask, "What is the average reward I can expect?" But in many real-world scenarios—like financial trading or autonomous driving—the average isn't enough. We need to know the risk, which means understanding the entire distribution of possible returns.
This paper, "Distributional Off-policy Evaluation with Bellman Residual Minimization," introduces a more practical and theoretically sound way to estimate these distributions using offline data.
TL;DR
The authors propose EBRM (Energy Bellman Residual Minimizer), a new method for distributional off-policy evaluation that is easier to compute in continuous spaces than previous approaches. Crucially, it provides strong statistical guarantees without requiring the restrictive "completeness" assumption common in prior literature.
What Problem Does This Paper Address?
Off-Policy Evaluation (OPE) is the task of predicting how well a new "target" policy will perform using data already collected by a different "behavior" policy. Distributional OPE takes this a step further by trying to estimate the full probability distribution of future rewards, not just the mean.
The major hurdle in this field has been a gap between theory and practice:
- Tractability: Most existing theories rely on "supremum-extended" distances (looking at the worst-case difference across all possible states). While mathematically elegant, these are nearly impossible to estimate accurately from finite data in complex, high-dimensional environments.
- Restrictive Assumptions: To prove that an algorithm works, researchers often assume "completeness"—the idea that your model is "closed" under the Bellman operator. In reality, models are almost always approximations, and this assumption is frequently violated.
Methods
The authors bridge this gap by shifting the focus to expectation-extended distances. Instead of worrying about the worst-case state, they minimize the average discrepancy over the states observed in the data.
Key components of their method include:
- Energy Distance: EBRM uses "energy distance" to measure the gap between the estimated and true return distributions. This metric is particularly powerful because it handles multi-dimensional rewards gracefully and doesn't require you to know the exact "shape" (density function) of the distribution.
- Bellman Residual Minimization: The algorithm works by finding a distribution that satisfies the distributional Bellman equation as closely as possible.
- Multi-step Extension: For cases where the model is "misspecified" (meaning the true distribution isn't actually representable by your model), the authors introduce a multi-step version. By looking several steps into the future, the algorithm can "pull" the estimate closer to the true target, effectively reducing bias.
Datasets
The authors evaluated EBRM using:
- OpenAI Gym Classical Games: Acrobot, Cartpole, and MountainCar. These are standard benchmarks for testing how RL algorithms handle different physics and control constraints.
- Synthetic Tabular Environments: A controlled environment with 30 states and 2 actions used specifically to test "realizable" vs. "non-realizable" (misspecified) scenarios.
Key Insights and Ideas
- Realizability > Completeness: The paper demonstrates that you can get strong theoretical guarantees (finite-sample error bounds) just by assuming "realizability"—that the true answer exists somewhere within your model's search space. This is a much lighter lift than the "completeness" assumption required by previous state-of-the-art methods like FLE.
- The Power of Averages: By moving from supremum-based theory to expectation-based theory, the authors provide a theoretical foundation that actually matches how practitioners build models in non-tabular (continuous) settings.
- Multi-step as a Tool for Misspecification: One of the most interesting "aha" moments is the use of multi-step operators not just for speed, but to combat model errors. As the number of steps $m$ increases, the objective function naturally aligns better with the true inaccuracy of the model.
Key Results
- Superior Accuracy: In OpenAI Gym experiments, EBRM consistently outperformed baselines like QRDQN and MMDRL in terms of both Energy distance and Wasserstein-1 distance.
- Stability under Misspecification: In tests where the model was intentionally "wrong" (non-realizable), EBRM remained stable and converged toward the best possible approximation. In contrast, the FLE method (which relies on completeness) actually saw its performance deteriorate as more data was added.
- Convergence Rate: The authors proved a convergence rate of $O(\sqrt{\log N / N})$, providing a solid mathematical guarantee for how quickly the estimate improves as you collect more samples ($N$).
Limitations and Future Work
While EBRM is a significant step forward, the authors note a few areas for further exploration:
- Computational Intensity: The multi-step version can be computationally expensive. While they proposed a bootstrap-based version to make it more practical, scaling this to massive datasets remains a challenge.
- Hyperparameter Tuning: Choosing the optimal number of steps ($m$) involves a bias-variance trade-off. While they provide a heuristic (Lepski’s rule), a more automated or adaptive way to choose $m$ would be beneficial.
- Deterministic Transitions: Some of the deepest theoretical results in the paper are focused on environments with deterministic transitions; extending the full weight of that theory to highly stochastic environments is a logical next step.
Summary updated