Research map / Reinforcement learning / MDPs and planning
Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity
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.
Proves that sample-efficient policy evaluation and best-policy identification under d-dimensional realizable linear function approximation in infinite-horizon discounted MDPs require Omega(log log d) batches of adaptivity, using subspace-packing constructions.
Problem
Determining the minimum level of adaptivity (number of batches K) needed for sample-efficient policy evaluation and best-policy identification in discounted MDPs with d-dimensional linear function approximation.
Approach
Extends the offline lower-bound framework to a multi-batch model and uses subspace packings under chordal distance so the environment can erase information along m-dimensional subspaces per round, showing the adaptivity boundary depends on dimension rather than being between K=1 and K>1.
Key results
- Policy evaluation under policy-induced or policy-free queries requires K = Omega(log log d) batches for any sample-efficient learner better than (1,1/2)-sound.
- Policy-free queries give Omega(log log d) lower bounds for both PE and BPI under all-policy realizability.
- In the fully adaptive setting (K=n), exact policy evaluation is possible in d queries under a feature covering assumption, and d queries is also a matching lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the learner to K = o(log log d) batches while keeping total queries polynomial in d | PE with linear action-value realizability · Infinite-horizon discounted MDPs | sample efficiency: K = Ω(log log d) | Hurt |
| Restrict to policy-free queries and use K = o(log log d) batches | PE and BPI with all-policy realizability · Infinite-horizon discounted MDPs | sample efficiency: K = Ω ( loglog d) | Hurt |
| Use fully adaptive querying with the feature-space condition | PE learner · Realizable PE problem | queries for exact solution: at most d | Helped |
| Require a fully adaptive learner to achieve better than (1,1/2)-soundness | PE and BPI · Realizable PE and BPI problems | required queries: K = n ≥ d | Hurt |
Surprising findings
- Adaptivity with K>1 does not guarantee sample-efficiency; the boundary lies within a dimension-dependent adaptivity regime rather than between offline and adaptive RL.
Limitations
- Lower bound is Omega(log log d) and it is unclear whether it is tight; a log d bound would require subspace packings not known in the literature.
- Lower bounds do not hold for finite action spaces or with coverage assumptions for BPI.
- Unclear whether policy-induced query lower bound also holds for BPI.
Experimental setup
Builds on: offline RL lower bound under linear function approximation (Wang et al. 2021) deployment efficiency chordal distance subspace packing
Closest papers by meaning
- On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling and Beyond (NeurIPS 2023 · similarity 0.91)
- Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting (NeurIPS 2021 · similarity 0.90)
- Provably Good Batch Off-Policy Reinforcement Learning Without Great Exploration (NeurIPS 2020 · similarity 0.90)
- Iteratively Refined Behavior Regularization for Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.89)
- Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.88)
- EfficientZero V2: Mastering Discrete and Continuous Control with Limited Data (ICML 2024 · 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.