mlsanityData to 7 Oct 2026

SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP

arXiv 2406.02165 ↗First posted 4 Jun 2024cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we study safe data collection for the purpose of policy evaluation in tabular Markov decision processes (MDPs). In policy evaluation, we are given a textittarget policy and asked to estimate the expected cumulative reward it will obtain. Policy evaluation requires data and we are interested in the question of what textitbehavior policy should collect the data for the most accurate evaluation of the target policy. While prior work has considered behavior policy selection, in this paper, we additionally consider a safety constraint on the behavior policy. Namely, we assume there exists a known default policy that incurs a particular expected cost when run and we enforce that the cumulative cost of all behavior policies ran is better than a constant factor of the cost that would be incurred had we always run the default policy. We first show that there exists a class of intractable MDPs where no safe oracle algorithm with knowledge about problem parameters can efficiently collect data and satisfy the safety constraints. We then define the tractability condition for an MDP such that a safe oracle algorithm can efficiently collect data and using that we prove the first lower bound for this setting. We then introduce an algorithm SaVeR for this problem that approximates the safe oracle algorithm and bound the finite-sample mean squared error of the algorithm while ensuring it satisfies the safety constraint. Finally, we show in simulations that SaVeR produces low MSE policy evaluation while satisfying the safety constraint.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 56 of its 78 references that are in the map. First posted on arXiv 4 Jun 2024.

Builds on

56 of 78 references.

References · 56

  1. 2016Concrete Problems in AI Safetycited by 1,582
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  3. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  4. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  5. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  6. 2021How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learnedcited by 201
  7. 2015Doubly Robust Policy Evaluation and Optimizationcited by 158
  8. 2020Exploration-Exploitation in Constrained MDPscited by 146
  9. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  10. 2022Legged Locomotion in Challenging Terrains using Egocentric Visioncited by 131
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  12. 2016Optimal and Adaptive Off-policy Evaluation in Contextual Banditscited by 111
38 more
  1. 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 109
  2. 2016Off-policy evaluation for slate recommendationcited by 102
  3. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  4. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  5. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  6. 2019Doubly robust off-policy evaluation with shrinkagecited by 87
  7. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  8. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  9. 2020Stochastic Bandits with Linear Constraintscited by 68
  10. 2024Safe Offline Reinforcement Learning with Feasibility-Guided Diffusion Modelcited by 62
  11. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 61
  12. 2016Conservative Banditscited by 58
  13. 2016Conservative Contextual Linear Banditscited by 56
  14. 2019Safe Exploration for Interactive Machine Learningcited by 51
  15. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  16. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  17. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  18. 2019Safe Linear Thompson Sampling with Side Informationcited by 37
  19. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
  20. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  21. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  22. 2020Optimal Off-Policy Evaluation from Multiple Logging Policiescited by 30
  23. 2023Safe Exploration in Reinforcement Learning: A Generalized Formulation and Algorithmscited by 27
  24. 2017Data-Efficient Policy Evaluation Through Behavior Policy Searchcited by 25
  25. 2023Survival Instinct in Offline Reinforcement Learningcited by 20
  26. 2020Improved Algorithms for Conservative Exploration in Banditscited by 16
  27. 2022Active Learning with Safety Constraintscited by 16
  28. 2021Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learningcited by 15
  29. 2022Safe Exploration for Efficient Policy Evaluation and Comparisoncited by 15
  30. 2022ReVar: Strengthening Policy Evaluation via Reduced Variance Samplingcited by 15
  31. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  32. 2020Deep Jump Learning for Off-Policy Evaluation in Continuous Treatment Settingscited by 14
  33. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  34. 2020Chernoff Sampling for Active Testing and Extension to Active Regressioncited by 11
  35. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  36. 2021A Reduction-Based Framework for Conservative Bandits and Reinforcement Learningcited by 9
  37. 2023Directional Optimism for Safe Linear Banditscited by 8
  38. 2017Active Learning for Accurate Estimation of Linear Modelscited by 6

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Tail-Influence Sampling for CVaR Policy Evaluationcited by 0