mlsanityData to 7 Oct 2026

The Statistical Complexity of Interactive Decision Making

arXiv 2112.13487 ↗First posted 27 Dec 2021cs.LG math.OC math.STcited by 208

Not on the map. Why?

Cited by 20 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. The main result of this work provides a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. In particular, we provide: 1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit. 2. a unified algorithm design principle, Estimation-to-Decisions (E2D), which transforms any algorithm for supervised estimation into an online algorithm for decision making. E2D attains a regret bound that matches our lower bound up to dependence on a notion of estimation performance, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient. Taken together, these results constitute a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds. More broadly, the approach can be viewed as a decision-theoretic analogue of the classical Le Cam theory of statistical estimation; it also unifies a number of existing approaches -- both Bayesian and frequentist.

Key facts. Cited by 208 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Dec 2021.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 44; 2023: 53; 2024: 49; 2025: 35; 2026: 26.

208 papers.

Sort:

By area:

  1. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  2. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  3. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  4. 2023Is RLHF More Difficult than Standard RL?cited by 96
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  7. 2025Outcome-based Exploration for LLM Reasoningcited by 79
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  9. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  12. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
38 more
  1. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  2. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  5. 2022On the Complexity of Adversarial Decision Makingcited by 32
  6. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  7. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  8. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  9. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  10. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  11. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  12. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  13. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  14. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  15. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  16. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methodscited by 27
  17. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  18. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  19. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
  20. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  21. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  22. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  23. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  24. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  25. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  26. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  27. 2022Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spacescited by 17
  28. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  29. 2023Optimal Exploration for Model-Based RL in Nonlinear Systemscited by 17
  30. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  31. 2024From Words to Actions: Unveiling the Theoretical Underpinnings of LLM-Driven Autonomous Systemscited by 17
  32. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  33. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  34. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  35. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 16
  36. 2023Online Learning in Stackelberg Games with an Omniscient Followercited by 15
  37. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  38. 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14

50 most cited of 208 All 208 (JSON)