ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling

Subhojyoti Mukherjee, Josiah P. Hanna, Robert D. Nowak

Abstract

This paper studies the problem of data collection for policy evaluation in Markov decision processes (MDPs). In policy evaluation, we are given a target policy and asked to estimate the expected cumulative reward it will obtain in an environment formalized as an MDP. We develop theory for optimal data collection within the class of tree-structured MDPs by first deriving an oracle data collection strategy that uses knowledge of the variance of the reward distributions. We then introduce the Reduced Variance Sampling (ReVar) algorithm that approximates the oracle strategy when the reward variances are unknown a priori and bound its sub-optimality compared to the oracle strategy. Finally, we empirically validate that ReVar leads to policy evaluation with mean squared error comparable to the oracle strategy and significantly lower than simply running the target policy.

Introduction

Policy evaluation—the task of estimating the expected cumulative reward of a specific target policy—is a foundational requirement for deploying reinforcement learning (RL) in the real world. Before a self-driving car or a medical diagnostic system is deployed, we must accurately estimate its performance to ensure safety and reliability.

Traditionally, this is done through "on-policy sampling," where the target policy is simply executed in the environment and the resulting rewards are averaged. However, this approach is often data-inefficient. If the target policy rarely visits states with high reward variance, the final estimate remains highly uncertain. This paper introduces ReVar (Reduced Variance Sampling), an algorithm designed to collect data using a specialized "behavior policy" that actively targets high-variance actions to minimize the Mean Squared Error (MSE) of the value estimate.

The Challenge of Sequential Variance

While variance-reduction techniques are well-understood in the context of Multi-Armed Bandits (MABs), extending them to multi-step Markov Decision Processes (MDPs) is significantly more complex. In a bandit setting, an action only affects the immediate reward. In an MDP, an action today determines which state you visit tomorrow, thereby influencing the variance of all future rewards.

To minimize the MSE of a value estimate, a data collection strategy must account for this "variance-to-come." A state might have a deterministic reward (zero variance) but lead to a highly stochastic sub-tree. A naive strategy would ignore such a state, whereas an optimal strategy must recognize its downstream uncertainty.

The ReVar Algorithm

The authors first derive an Oracle strategy for tree-structured MDPs. Given perfect knowledge of reward variances and transition probabilities, the Oracle identifies the exact distribution of samples across actions that minimizes the total MSE.

Since these parameters are typically unknown, the ReVar algorithm approximates this Oracle through three key mechanisms:

  1. Adaptive Variance Estimation: ReVar maintains running estimates of reward variances, utilizing an Upper Confidence Bound (UCB) approach to handle the uncertainty of these estimates.
  2. Recursive Variance Propagation: The algorithm employs a recursive "B-factor" to calculate how much the variance in a future state contributes to the total uncertainty of the starting state. This allows the algorithm to "look ahead" and prioritize paths that lead to noisy outcomes.
  3. Deterministic Action Selection: Rather than sampling randomly, ReVar uses a deterministic rule to ensure the empirical sampling proportions match the estimated optimal proportions as closely as possible at every step.

While the theoretical foundations are built on tree-structured MDPs (where each state has a unique parent), the authors also propose a heuristic for Directed Acyclic Graphs (DAGs), where multiple paths can converge on the same state.

Empirical Validation

The performance of ReVar was tested in two primary simulated environments:

  • Deterministic Tree MDP: A 4-depth tree designed as a "trap" for on-policy evaluation. In this environment, the target policy prefers low-variance arms, leaving the high-variance regions of the state space unexplored. ReVar achieved an MSE orders of magnitude lower than on-policy sampling by identifying and exploring these high-variance regions.
  • Stochastic Gridworld: A $4 \times 4$ grid representing a DAG structure. Despite violating the strict tree-structure assumption, ReVar outperformed both on-policy sampling and bandit-style variance-aware baselines (such as CB-Var) that do not account for downstream variance.

Key Insights and Theoretical Results

  • On-Policy Suboptimality: The research demonstrates that the "natural" choice of running the target policy is rarely the most efficient way to evaluate it. Active exploration of uncertainty is required for precision.
  • Regret Bounds: The authors prove a regret bound for ReVar, showing that the gap between ReVar and the Oracle strategy closes at a rate of $O(n^{-3/2})$. This indicates that ReVar converges to the theoretically optimal sampling strategy very rapidly.
  • Bridging the Gap: The paper successfully generalizes optimal sampling laws from the bandit literature to the sequential setting of MDPs by incorporating the recursive structure of the value function.

Limitations and Future Directions

The current work focuses on Tree and DAG structures. In many real-world RL problems, MDPs are cyclic or have infinite horizons, where recursive variance calculations become more complex due to cyclical dependencies. Additionally, the current analysis assumes transition probabilities are known, though the algorithm can estimate them.

Future research directions include extending ReVar to infinite-horizon MDPs, incorporating function approximation (such as neural networks) to handle continuous state spaces, and developing strategies that simultaneously learn the transition model while optimizing for variance reduction.

Summary updated

Abstract

This paper studies the problem of data collection for policy evaluation in Markov decision processes (MDPs). In policy evaluation, we are given a target policy and asked to estimate the expected cumulative reward it will obtain in an environment formalized as an MDP. We develop theory for optimal data collection within the class of tree-structured MDPs by first deriving an oracle data collection strategy that uses knowledge of the variance of the reward distributions. We then introduce the Reduced Variance Sampling (ReVar) algorithm that approximates the oracle strategy when the reward variances are unknown a priori and bound its sub-optimality compared to the oracle strategy. Finally, we empirically validate that ReVar leads to policy evaluation with mean squared error comparable to the oracle strategy and significantly lower than simply running the target policy.
BibTeX
@inproceedings{mukherjee2022revar,
  author = {Subhojyoti Mukherjee and Josiah P. Hanna and Robert D. Nowak},
  title = {{ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=pU-JmFyOu69},
}
Figure