The Statistical Complexity Of Interactive Decision Making

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfoster2021the

Related papers

• Tight Guarantees For Interactive Decision Making With The Decision-estimation Coefficient (2023)0.00
• On The Complexity Of Multi-agent Decision Making: From Learning In Games To Partial Monitoring (2023)0.00
• Instance-optimality In Interactive Decision Making: Toward A Non-asymptotic Theory (2023)0.00
• GEC: A Unified Framework For Interactive Decision Making In MDP, POMDP, And Beyond (2022)0.00
• Implications Of Regret On Stability Of Linear Dynamical Systems (2022)6.34
• Model-free Online Learning In Unknown Sequential Decision Making Problems And Games (2021)5.24
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• First-order Regret In Reinforcement Learning With Linear Function Approximation: A Robust Estimation Approach (2021)0.00