Research map / Reinforcement learning / MDPs and planning
Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
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 pure exploration (best policy identification) in contextual bandits and tabular RL, showing policy-difference estimation suffices for bandits but not tabular RL, and proposes PERP, which estimates differences relative to a reference policy for the tightest known tabular RL bound.
Problem
Sample complexity of identifying an epsilon-optimal policy from a finite policy set in tabular RL and contextual bandits, where existing RL bounds estimate each policy's value separately rather than the differences between policies.
Approach
Estimate the state-visitation of a single reference policy, then estimate only how every other policy deviates from it (via reduced-variance difference estimator with covariance-based experiment design), and eliminate policies in epochs; shows a separation between contextual bandits (rho_Pi suffices) and tabular RL (it does not).
Key results
- Shows a tabular MDP instance where the rho_Pi complexity is a constant (<=15) while any PAC algorithm needs E[tau] >= (1/epsilon) log(1/(2.4 delta)) samples, so O(rho_Pi) is not sufficient for tabular RL.
- PERP's upper bound is never worse than the PEDEL complexity and is strictly tighter in epsilon dependence on a family of MDPs (e.g., max_pi H*U/max(eps^2,Delta^2) = 3H/eps vs. H/eps^2 for PEDEL-type terms).
- In contextual bandits with unknown context distribution, PERP achieves O(rho_Pi) up to lower-order terms, matching the known-context lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate policy behavior relative to a reference policy instead of estimating each policy separately | PERP in tabular RL · Tabular MDP instance M | sample complexity: 15; 3H/ε; H/ε^2 | Helped |
| Use PERP’s difference-based complexity instead of the individual-visitation complexity | Tabular RL policy identification · Any MDP instance and policy set Π | sample complexity bound | Helped |
| Apply PERP to contextual bandits with unknown context distribution | PERP · Tabular contextual bandits | sample complexity: O(ρ_Π) | Helped |
Surprising findings
- Estimating only differences between policies is not sufficient in tabular RL, unlike in bandits, because reaching-probability of states must also be learned.
Limitations
- PERP is computationally expensive, requiring enumeration of the policy set Pi.
- Upper bound contains unfortunate lower-order terms.
- Unclear whether U(pi, pi*)/max(Delta^2, eps^2) is unavoidable in general MDPs.
Experimental setup
Metrics: sample complexity bound
Baselines: PEDEL
Builds on: PEDEL linear bandit best-arm identification differences Soare et al. linear bandit exploration
Closest papers by meaning
- Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.90)
- Replicability in Reinforcement Learning (NeurIPS 2023 · similarity 0.90)
- Reinforcement Learning with Feedback Graphs (NeurIPS 2020 · similarity 0.88)
- Multi-Reward Best Policy Identification (NeurIPS 2024 · similarity 0.88)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.88)
- Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts (NeurIPS 2026 · similarity 0.88)
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.