mlsanityData to 7 Oct 2026

On the Complexity of Adversarial Decision Making

arXiv 2206.13063 ↗First posted 27 Jun 2022cs.LG math.OC math.STcited by 32

Not on the map. Why?

Abstract (arXiv)

A central problem in online learning and decision making -- from bandits to reinforcement learning -- is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. Our main result is to show -- via new upper and lower bounds -- that the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. in the stochastic counterpart to our setting, is necessary and sufficient to obtain low regret for adversarial decision making. However, compared to the stochastic setting, one must apply the Decision-Estimation Coefficient to the convex hull of the class of models (or, hypotheses) under consideration. This establishes that the price of accommodating adversarial rewards or dynamics is governed by the behavior of the model class under convexification, and recovers a number of existing results -- both positive and negative. En route to obtaining these guarantees, we provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures, including the Information Ratio of Russo and Van Roy and the Exploration-by-Optimization objective of Lattimore and Gy"orgy.

Key facts. Cited by 32 papers in the map (data through 7 Oct 2026). Builds on 31 of its 75 references that are in the map. First posted on arXiv 27 Jun 2022.

Builds on

31 of 75 references.

References · 31

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
  5. 2013Learning to Optimize Via Posterior Samplingcited by 253
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2014Learning to Optimize via Information-Directed Samplingcited by 168
19 more
  1. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  3. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  6. 2016Kernel-based methods for bandit convex optimizationcited by 63
  7. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 59
  8. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  9. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  10. 2020Information Directed Sampling for Linear Partial Monitoringcited by 39
  11. 2020Mirror Descent and the Information Ratiocited by 39
  12. 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
  13. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  14. 2019Exploration by Optimisation in Partial Monitoringcited by 20
  15. 2019Provably Efficient Reinforcement Learning with Aggregated Statescited by 20
  16. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  17. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  18. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 13
  19. 2021Minimax Regret for Bandit Convex Optimisation of Ridge Functionscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 9; 2024: 10; 2025: 8; 2026: 4.

32 papers.

Sort:

  1. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  2. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  3. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  4. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  5. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  6. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  7. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  8. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  9. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  10. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  11. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  12. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
20 more
  1. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 7
  2. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  3. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  4. 2024Contextual Multinomial Logit Bandits with General Value Functionscited by 4
  5. 2025Research Program: Theory of Learning in Dynamical Systemscited by 4
  6. 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
  7. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  8. 2024Online Learning with Unknown Constraintscited by 2
  9. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  10. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  11. 2025Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Banditscited by 2
  12. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  13. 2025Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoringcited by 1
  14. 2025Sparse Optimistic Information Directed Samplingcited by 1
  15. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  16. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  17. 2023Tight Bounds for γ-Regret via the Decision-Estimation Coefficientcited by 0
  18. 2025Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spacescited by 0
  19. 2026A Complete Characterization of Learnability for Adversarial Noisy Banditscited by 0
  20. 2026Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximationcited by 0