REVIEW 13 cited by
The Statistical Complexity of Interactive Decision Making
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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.
Forward citations
Cited by 13 Pith papers
-
On the Complexity of Offline Reinforcement Learning with $Q^\star$-Approximation and Partial Coverage
Q*-realizability plus Bellman completeness is insufficient for sample-efficient offline RL under partial coverage, and a new decision-estimation framework recovers and improves existing bounds.
-
Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
An OCO algorithm with only O(√T) static regret, pluggable as a preconditioner selector, recovers the classical O(1/√T) stationarity rate on smooth stochastic nonconvex problems and the O(T^{-2/7}) rate on nonsmooth ones.
-
Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing
CABS-C and CABS-D use correlation graphs plus surrogate rewards to cut effective exploration in contextual bandits for LLM routing, with CABS-D giving best-of-both-worlds regret and better empirical accuracy-cost frontiers.
-
Bellman-sufficient Information Complexity
When a Bellman-sufficient state and index make the log-penalized upper value and Bellman–Fano ghost lower value close at the same radius, they certify the same interactive information-risk scale.
-
Efficient Controllable Diffusion via Optimal Classifier Guidance
SLCD provably converges, under no-regret learning and a strong score-estimation assumption, to the KL-regularized optimal distribution using only supervised classification oracles.
-
Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
Outcome-based online RL is tractable under coverability with general function approximation, but there are MDPs where trajectory-level feedback costs exponentially more samples than per-step feedback.
-
Combinatorial Reinforcement Learning with Preference Feedback
MNL-VQL is the first algorithm with regret bounds for combinatorial reinforcement learning with multinomial-logit preference feedback, and it is nearly minimax-optimal in linear MDPs.
-
Outcome-based Exploration for LLM Reasoning
Outcome-based exploration bonuses (UCB-Con and Batch) improve pass@1 and pass@32 for LLM math reasoning while slowing diversity collapse, supported by a bandit model with a strong generalization assumption.
-
Aligning Learning and Endogenous Decision-Making
A decision-aware loss and robust uncertainty-set method for learning under endogenous uncertainty, plus a two-stage information-gathering extension, with experiments on pricing, assortment, and power scheduling.
-
Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL
VAC is a new actor-critic method with a single optimistic objective and a provably near-optimal regret bound in linear Markov decision processes.
-
The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
An optimism-based algorithm with nonparametric instrumental variables learns an epsilon-optimal policy under information asymmetry and knowledge transfer with O~(1/epsilon^2) sample complexity.
-
Sample Complexity and Representation Ability of Test-time Scaling Paradigms
Best-of-n sampling provably needs about 1/Δ samples versus 1/Δ² for self-consistency, and a constructed Transformer can route among experts using verifier feedback to reach near-optimal final responses.
-
Statistical and Algorithmic Foundations of Reinforcement Learning
A tutorial collecting minimax sample complexity results for tabular RL across generative model, online, offline, robust, and human-feedback settings.
Discussion (0). Continue with ORCID to comment.