Research map / Reinforcement learning / MDPs and planning
Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
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.
Derives an instance-specific (eps,delta)-PAC sample complexity lower bound and a convex relaxation for online multi-reward multi-policy policy evaluation, and adapts MR-NaS as an asymptotically near-optimal adaptive exploration scheme validated on tabular MDPs.
Problem
Online evaluation of multiple target policies over finite or convex reward sets in discounted tabular MDPs with (epsilon,delta)-PAC guarantees, where prior work lacked instance-dependent sample complexity bounds and PAC guarantees.
Approach
Defines a value-deviation quantity rho and an instance-specific lower bound on sample complexity via confusing alternative models; relaxes the characteristic time into a convex upper bound U_eps whose optimal stationary allocation drives an MR-NaS-style sampling and stopping rule.
Key results
- MR-NaS achieves good accuracy across all four tabular environments in multi-policy finite-reward and reward-free settings (30 seeds).
- SF-NR and GVFExplorer show mixed performance; GVFExplorer underperforms where certain rewards are hard to obtain under a uniform policy.
- Theoretical result: MR-NaS has limsup E[tau]/log(1/delta) <= 4 U*_eps(M), i.e. asymptotic optimality up to a constant factor 4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MR-NaS adaptive exploration | multi-reward multi-policy evaluation · Riverswim, Forked Riverswim, DoubleChain, and NArms | accuracy | Helped |
| optimize the behavior policy while neglecting the forward equations | GVFExplorer · environments where certain rewards are hard to obtain under a uniform policy | accuracy | Hurt |
Surprising findings
- The convex relaxation of the characteristic time can be loose; the gap to the true characteristic time is left unquantified.
- Sample complexity is governed by the worst-case policy-reward pair rather than the sum over pairs.
Limitations
- Assumes the optimal allocation is unique and lies in the interior of the allocation set.
- Requires the 2epsilon separation, losing a constant factor in the lower bound.
- Gap between the relaxed and exact characteristic time is not quantified.
Experimental setup
Datasets: Riverswim Forked Riverswim DoubleChain NArms
Benchmarks: Riverswim Forked Riverswim DoubleChain NArms
Metrics: estimation error of value vector sample complexity
Baselines: SF-NR GVFExplorer Noisy Policy - Uniform Noisy Policy - Visitation
Builds on: MR-NaS NaS Best Policy Identification GVFExplorer SF-NR
Closest papers by meaning
- Multi-Reward Best Policy Identification (NeurIPS 2024 · similarity 0.91)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.88)
- Efficient Multi-Policy Evaluation for Reinforcement Learning (AAAI 2025 · similarity 0.87)
- Scalable Online Exploration via Coverability (ICML 2024 · similarity 0.87)
- Learning the Optimal Policy for Balancing Short-Term and Long-Term Rewards (NeurIPS 2024 · similarity 0.87)
- Policy Gradient Algorithms in Average-Reward Multichain MDPs (NeurIPS 2026 · similarity 0.87)
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.