mlsanityData to 14 Oct 2026

Model-Free Reinforcement Learning with the Decision-Estimation Coefficient

arXiv 2211.14250 ↗First posted 25 Nov 2022cs.LG math.OC math.STcited by 11

Not on the map. Why?

Abstract (arXiv)

We consider the problem of interactive decision making, encompassing structured bandits and reinforcement learning with general function approximation. Recently, Foster et al. (2021) introduced the Decision-Estimation Coefficient, a measure of statistical complexity that lower bounds the optimal regret for interactive decision making, as well as a meta-algorithm, Estimation-to-Decisions, which achieves upper bounds in terms of the same quantity. Estimation-to-Decisions is a reduction, which lifts algorithms for (supervised) online estimation into algorithms for decision making. In this paper, we show that by combining Estimation-to-Decisions with a specialized form of optimistic estimation introduced by Zhang (2022), it is possible to obtain guarantees that improve upon those of Foster et al. (2021) by accommodating more lenient notions of estimation error. We use this approach to derive regret bounds for model-free reinforcement learning with value function approximation, and give structural results showing when it can and cannot help more generally.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 20 of its 34 references that are in the map. First posted on arXiv 25 Nov 2022.

Builds on

20 of 34 references.

References · 20

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 159
  11. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
8 more
  1. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  2. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  3. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
  4. 2022On the Complexity of Adversarial Decision Makingcited by 33
  5. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32
  6. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  7. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  8. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 3; 2025: 4; 2026: 2.

11 papers.

  1. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 30
  2. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  3. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  4. 2024Optimistic Information Directed Samplingcited by 7
  5. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  6. 2025Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Makingcited by 2
  7. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  8. 2025OnRL-RAG: Real-Time Personalized Mental Health Dialogue Systemcited by 1
  9. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  10. 2024A Fast Convergence Theory for Offline Decision Makingcited by 0
  11. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0