On the Relation between Policy Improvement and Off-Policy Minimum-Variance Policy Evaluation

Alberto Maria Metelli, Samuele Meta, Marcello RestelliUAI 2023 · OpenReview

Abstract

Off-policy methods are the basis of a large number of effective Policy Optimization (PO) algorithms. In this setting, Importance Sampling (IS) is typically employed for off-policy evaluation, with the goal of estimating the performance of a target policy, given samples collected with a different behavioral policy. However, in Monte Carlo simulation, IS represents a variance minimization approach. In this field, a suitable behavioral distribution is employed for sampling, allowing diminishing the variance of the estimator below the one achievable when sampling from the target distribution. In this paper, we analyze IS in these two guises in the context of PO. We provide a novel view of off-policy PO, showing a connection between the policy improvement and variance minimization objectives. Then, we illustrate how minimizing the off-policy variance can, in some circumstances, lead to a policy improvement, with the advantage, compared with direct off-policy learning, of implicitly enforcing a trust region. Finally, we present numerical simulations on continuous RL benchmarks, with a particular focus on the robustness to small batch sizes.

Introduction

In Reinforcement Learning (RL), off-policy evaluation typically relies on Importance Sampling (IS) to estimate the performance of a target policy using data from a different behavioral policy. However, IS is often a double-edged sword: if policies diverge significantly, the estimator's variance can explode, leading to unstable updates. Traditionally, this is managed through explicit "trust regions" (e.g., TRPO or PPO).

This paper reveals a fascinating duality: the quest to minimize the variance of an off-policy estimator is mathematically linked to the goal of improving the policy itself. By seeking the "best" distribution for data collection—the one that yields the most stable estimates—the authors derive a new class of algorithms that naturally improve performance while implicitly staying within a safe trust region, proving exceptionally robust even when data is scarce.

Methods

The researchers bridge the gap between variance reduction and policy optimization through three key steps:

  1. The $\mathcal{I}_f$ Operator: They define a mathematical operator that transforms a distribution into its "minimum-variance" counterpart. They prove that applying this operator is equivalent to a performance improvement step—the distribution that minimizes variance is naturally drawn toward regions of higher reward.
  2. Implicit Trust Regions: Minimizing the $\alpha$-Rényi divergence between updates naturally bounds the variance. This means the algorithm doesn't need an explicit, hand-tuned constraint; the math of variance minimization enforces one automatically.
  3. MBPExPI Algorithm: They introduce Minimum-Variance Policy Evaluation for Policy Improvement (MBPExPI). This algorithm uses a "moment projection" to find the best possible policy parameters that minimize the estimator's variance.

Experimental Results

The authors evaluated their approach on four classic continuous control benchmarks: Cartpole, Inverted Double Pendulum, Mountain Car, and Mujoco Swimmer.

Average return across four continuous control benchmarks comparing MBPExPI variants with POIS and TRPO.

Key Findings

  • Superior Stability: In the Inverted Double Pendulum task, MBPExPI consistently reached optimal performance, whereas TRPO often converged to a sub-optimal "safe" policy that failed to keep the pole upright.
  • Sample Efficiency: The algorithm matched or outperformed state-of-the-art methods like POIS (Policy Optimization via Importance Sampling) across the board.
  • Robustness to Small Batches: One of the most significant results is the algorithm's performance with limited data. While standard methods like TRPO might fail or become highly unstable with small batch sizes (e.g., only 11 episodes), MBPExPI remains steady because its objective function is explicitly designed to keep uncertainty in check.
Performance comparison with varying batch sizes (n=50 vs n=11) and sensitivity to the parameter beta.

Conclusion

By treating variance as a signal for improvement rather than just noise, this work provides a robust alternative to standard off-policy learning. While the current framework assumes non-negative rewards and involves computational complexity in the inner loop, it offers a principled way to enforce trust regions implicitly. Future work includes extending this approach to actor-critic architectures to further boost performance.

Summary updated

Abstract

Off-policy methods are the basis of a large number of effective Policy Optimization (PO) algorithms. In this setting, Importance Sampling (IS) is typically employed for off-policy evaluation, with the goal of estimating the performance of a target policy, given samples collected with a different behavioral policy. However, in Monte Carlo simulation, IS represents a variance minimization approach. In this field, a suitable behavioral distribution is employed for sampling, allowing diminishing the variance of the estimator below the one achievable when sampling from the target distribution. In this paper, we analyze IS in these two guises in the context of PO. We provide a novel view of off-policy PO, showing a connection between the policy improvement and variance minimization objectives. Then, we illustrate how minimizing the off-policy variance can, in some circumstances, lead to a policy improvement, with the advantage, compared with direct off-policy learning, of implicitly enforcing a trust region. Finally, we present numerical simulations on continuous RL benchmarks, with a particular focus on the robustness to small batch sizes.
BibTeX
@inproceedings{metelli2023relation,
  author = {Alberto Maria Metelli and Samuele Meta and Marcello Restelli},
  title = {{On the Relation between Policy Improvement and Off-Policy Minimum-Variance Policy Evaluation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=tmsHJNctTK},
}
Figure