mlsanityData to 7 Oct 2026

ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling

arXiv 2203.04510 ↗First posted 9 Mar 2022cs.LGcited by 15

Not on the map. Why?

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.

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

Builds on

15 of 35 references.

References · 15

  1. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  2. 2018Exploration by Random Network Distillationcited by 966
  3. 2016Deep Exploration via Bootstrapped DQNcited by 518
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  5. 2019Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learningcited by 121
  6. 2017The Uncertainty Bellman Equation and Explorationcited by 81
  7. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  8. 2017Data-Efficient Policy Evaluation Through Behavior Policy Searchcited by 25
  9. 2017Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimatescited by 20
  10. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  11. 2020Reducing Sampling Error in Batch Temporal Difference Learningcited by 11
  12. 2020Chernoff Sampling for Active Testing and Extension to Active Regressioncited by 11
3 more
  1. 2015Online Learning to Samplecited by 9
  2. 2014Adaptive Monte Carlo via Bandit Allocationcited by 2
  3. 2019Learning Multiple Markov Chains via Adaptive Allocationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 5; 2025: 4; 2026: 2.

15 papers.

Sort:

  1. 2023Efficient Policy Evaluation with Offline Data Informed Behavior Policy Designcited by 12
  2. 2024Doubly Optimal Policy Evaluation for Reinforcement Learningcited by 7
  3. 2023On-Policy Policy Gradient Reinforcement Learning Without On-Policy Samplingcited by 6
  4. 2024Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experimentscited by 6
  5. 2024Efficient Policy Evaluation with Safety Constraint for Reinforcement Learningcited by 5
  6. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 5
  7. 2023SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Banditscited by 3
  8. 2023Truncating Trajectories in Monte Carlo Reinforcement Learningcited by 1
  9. 2024SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDPcited by 1
  10. 2024Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approachcited by 1
  11. 2025Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluationcited by 1
  12. 2025Behaviour Policy Optimization: Provably Lower Variance Return Estimates for Off-Policy Reinforcement Learningcited by 1
3 more
  1. 2026Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learningcited by 1
  2. 2025Centralized Adaptive Sampling for Reliable Co-Training of Independent Multi-Agent Policiescited by 0
  3. 2026Tail-Influence Sampling for CVaR Policy Evaluationcited by 0