mlsanityData to 7 Oct 2026

A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation

arXiv 2207.08342 ↗First posted 18 Jul 2022cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

The current paper studies sample-efficient Reinforcement Learning (RL) in settings where only the optimal value function is assumed to be linearly-realizable. It has recently been understood that, even under this seemingly strong assumption and access to a generative model, worst-case sample complexities can be prohibitively (i.e., exponentially) large. We investigate the setting where the learner additionally has access to interactive demonstrations from an expert policy, and we present a statistically and computationally efficient algorithm (Delphi) for blending exploration with expert queries. In particular, Delphi requires tildeO(d) expert queries and a textttpoly(d,H,|A|,1/varepsilon) amount of exploratory samples to provably recover an varepsilon-suboptimal policy. Compared to pure RL approaches, this corresponds to an exponential improvement in sample complexity with surprisingly-little expert input. Compared to prior imitation learning (IL) approaches, our required number of expert demonstrations is independent of H and logarithmic in 1/varepsilon, whereas all prior work required at least linear factors of both in addition to the same dependence on d. Towards establishing the minimal amount of expert queries needed, we show that, in the same setting, any learner whose exploration budget is polynomially-bounded (in terms of d,H, and |A|) will require at least tildeOmega(√d) oracle calls to recover a policy competing with the expert's value function. Under the weaker assumption that the expert's policy is linear, we show that the lower bound increases to tildeOmega(d).

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 16 of its 37 references that are in the map. First posted on arXiv 18 Jul 2022.

Builds on

16 of 37 references.

References · 16

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  9. 2017Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Predictioncited by 93
  10. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  11. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  12. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
4 more
  1. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  2. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  3. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  4. 2021TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functionscited by 7

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 3; 2025: 1.

7 papers.

  1. 2024Overcoming the Sim-to-Real Gap: Leveraging Simulation to Learn to Explore for Real-World RLcited by 17
  2. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  3. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  4. 2025Efficient Imitation under Misspecificationcited by 4
  5. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  6. 2022Linear Reinforcement Learning with Ball Structure Action Spacecited by 1
  7. 2024Interactive and Hybrid Imitation Learning: Provably Beating Behavior Cloningcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2023Demonstration-Regularized RL
  2. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  3. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity
  4. 2024A Model-Based Approach for Improving Reinforcement Learning Efficiency Leveraging Expert Observations
  5. 2025Sample-Efficient Expert Query Control in Active Imitation Learning via Conformal Prediction
  6. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling
  7. 2024Hybrid Inverse Reinforcement Learning
  8. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review