Research map / Reinforcement learning / MDPs and planning
SaVeR: Optimal Data Collection Strategy for Safe Policy Evaluation in Tabular MDP
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies safe behavior-policy selection for minimum-variance off-policy-style policy evaluation in tabular/tree MDPs under a cumulative cost constraint, proving lower bounds and proposing the SaVeR algorithm with O~(n^{-3/2}) regret.
Problem
Collecting data for accurate policy evaluation of a target policy in tabular MDPs while keeping the cumulative cost of behavior policies above a fraction of a known safe baseline's cost throughout learning.
Approach
Extends variance-minimizing adaptive sampling (optimal proportions proportional to policy weight times reward standard deviation, propagated through the tree) with a safety budget: run the baseline when the budget is negative, use forced exploration early, and otherwise follow a plug-in UCB-style variance-reduction sampling rule; shows a tractability condition under which safe collection is feasib
Key results
- On a bandit (A=11), SaVeR achieves lower MSE than SEPEC and safe on-policy as rounds increase while respecting the safety constraint.
- Theory: SaVeR's regret scales as O(log(n)/n^{3/2}) and its constraint regret as O(log(n)/n^{1/2}).
- Proves a lower bound of Omega(sqrt(SAL^2)/n^{3/2}) for tree MDPs and a bandit lower bound of A^{1/3}/n^{3/2} under the tractability condition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SaVeR instead of SEPEC or safe on-policy data collection | Bandit with A=11 · Bandit | MSE | Helped |
| Use SaVeR instead of safe on-policy or SEPEC data collection | Movielens 1M, A=30 · Movielens 1M | MSE | Helped |
| Use SaVeR instead of safe on-policy data collection | 4-depth, 2-action deterministic tree MDP · Tree MDP | MSE | Helped |
| Use SaVeR instead of safe on-policy data collection | 4×4 stochastic gridworld · Gridworld | MSE | Helped |
| Use the oracle data-collection strategy instead of safe on-policy data collection | 4×4 stochastic gridworld · Gridworld | MSE | Helped |
| Apply the tested safe data-collection algorithms | Oracle, SaVeR, safe on-policy, and SEPEC · Experiments | constraint satisfaction | Helped |
Limitations
- Theory is for tree-structured MDPs; DAG extension is approximate and gridworld violates tree assumptions.
- Requires a sufficiently large budget and a tractability condition on the MDP.
- Assumes known transition model and deterministic baseline policy.
Experimental setup
Datasets: MovieLens 1M
Benchmarks: MovieLens 1M bandit synthetic bandit tree MDP gridworld
Metrics: MSE cumulative constraint violation
Baselines: SEPEC safe on-policy unconstrained oracle
Builds on: optimal sampling proportions for MSE (Hanna et al.) SEPEC MC-UCB PEDEL
Closest papers by meaning
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.86)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.86)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.86)
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.85)
- Flipping-based Policy for Chance-Constrained Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.