# ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling

arXiv: https://arxiv.org/abs/2203.04510 · HTML: https://mlsanity.com/paper/2203.04510/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 9 Mar 2022.

## Builds on (most cited first, 15 of 15)

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1911.06854/) (2019)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Data-Efficient Policy Evaluation Through Behavior Policy Search](https://mlsanity.com/paper/1706.03469/) (2017)
- [Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates](https://mlsanity.com/paper/1711.03591/) (2017)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Chernoff Sampling for Active Testing and Extension to Active Regression](https://mlsanity.com/paper/2012.08073/) (2020)
- [Reducing Sampling Error in Batch Temporal Difference Learning](https://mlsanity.com/paper/2008.06738/) (2020)
- [Online Learning to Sample](https://mlsanity.com/paper/1506.09016/) (2015)
- [Adaptive Monte Carlo via Bandit Allocation](https://mlsanity.com/paper/1405.3318/) (2014)
- [Learning Multiple Markov Chains via Adaptive Allocation](https://mlsanity.com/paper/1905.11128/) (2019)

## Built on by (most cited first, 16 of 16)

- [Efficient Policy Evaluation with Offline Data Informed Behavior Policy Design](https://mlsanity.com/paper/2301.13734/) (2023)
- [Doubly Optimal Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2410.02226/) (2024)
- [On-Policy Policy Gradient Reinforcement Learning Without On-Policy Sampling](https://mlsanity.com/paper/2311.08290/) (2023)
- [Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experiments](https://mlsanity.com/paper/2403.17285/) (2024)
- [Efficient Policy Evaluation with Safety Constraint for Reinforcement Learning](https://mlsanity.com/paper/2410.05655/) (2024)
- [Adaptive Exploration for Multi-Reward Multi-Policy Evaluation](https://mlsanity.com/paper/2502.02516/) (2025)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP](https://mlsanity.com/paper/2406.02165/) (2024)
- [Behaviour Policy Optimization: Provably Lower Variance Return Estimates for Off-Policy Reinforcement Learning](https://mlsanity.com/paper/2511.10843/) (2025)
- [Truncating Trajectories in Monte Carlo Reinforcement Learning](https://mlsanity.com/paper/2305.04361/) (2023)
- [Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach](https://mlsanity.com/paper/2410.13463/) (2024)
- [Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation](https://mlsanity.com/paper/2505.22492/) (2025)
- [Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learning](https://mlsanity.com/paper/2602.01853/) (2026)
- [Centralized Adaptive Sampling for Reliable Co-Training of Independent Multi-Agent Policies](https://mlsanity.com/paper/2508.01049/) (2025)
- [Tail-Influence Sampling for CVaR Policy Evaluation](https://mlsanity.com/paper/2609.38096/) (2026)
- [Instance-Dependent Regret for CMDPs with Step-Wise Constraints](https://mlsanity.com/paper/2610.02520/) (2026)

## Abstract (arXiv)

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.