mlsanityData to 7 Oct 2026

The Pareto Frontier of model selection for general Contextual Bandits

arXiv 2110.13282 ↗First posted 25 Oct 2021cs.LGcited by 24

Not on the map. Why?

Abstract (arXiv)

Recent progress in model selection raises the question of the fundamental limits of these techniques. Under specific scrutiny has been model selection for general contextual bandits with nested policy classes, resulting in a COLT2020 open problem. It asks whether it is possible to obtain simultaneously the optimal single algorithm guarantees over all policies in a nested sequence of policy classes, or if otherwise this is possible for a trade-off α∈[frac12,1) between complexity term and time: ln(|Pim|)1-αTα. We give a disappointing answer to this question. Even in the purely stochastic regime, the desired results are unobtainable. We present a Pareto frontier of up to logarithmic factors matching upper and lower bounds, thereby proving that an increase in the complexity term ln(|Pim|) independent of T is unavoidable for general policy classes. As a side result, we also resolve a COLT2016 open problem concerning second-order bounds in full-information games.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 20 of its 41 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

20 of 41 references.

References · 20

  1. 2013Non-stationary Stochastic Optimizationcited by 173
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2016Corralling a Band of Bandit Algorithmscited by 99
  4. 2018Learning to Optimize under Non-Stationaritycited by 85
  5. 2021Adapting to Misspecification in Contextual Banditscited by 81
  6. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  7. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  8. 2019Model selection for contextual banditscited by 60
  9. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  10. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 47
  11. 2020Regret Bound Balancing and Elimination for Model Selection in Bandits and RLcited by 45
  12. 2017Tracking the Best Expert in Non-stationary Stochastic Environmentscited by 35
8 more
  1. 2019OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual banditscited by 28
  2. 2020Problem-Complexity Adaptive Model Selection for Stochastic Linear Banditscited by 26
  3. 2020Corralling Stochastic Bandit Algorithmscited by 23
  4. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  5. 2015The Pareto Regret Frontier for Banditscited by 13
  6. 2020Open Problem: Model Selection for Contextual Banditscited by 12
  7. 2020Upper Confidence Bounds for Combining Stochastic Banditscited by 7
  8. 2015Achieving All with No Parameters: Adaptive NormalHedgecited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 5; 2024: 4; 2025: 3; 2026: 6.

24 papers.

Sort:

By area:

  1. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  2. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  3. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 17
  4. 2024Efficient Sequential Decision Making with Large Language Modelscited by 16
  5. 2022Best of Both Worlds Model Selectioncited by 11
  6. 2023Data-Driven Online Model Selection With Regret Guaranteescited by 11
  7. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  8. 2025Offline-to-online hyperparameter transfer for stochastic banditscited by 6
  9. 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
  10. 2022Adaptive Bandit Convex Optimization with Heterogeneous Curvaturecited by 2
  11. 2024Sparsity-Agnostic Linear Bandits with Adaptive Adversariescited by 2
  12. 2024Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginalscited by 2
12 more
  1. 2026Parameter-Free Dynamic Regret for Unconstrained Linear Banditscited by 2
  2. 2022Adversarial Bandits against Arbitrary Strategiescited by 1
  3. 2024Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Gamescited by 1
  4. 2026Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescited by 1
  5. 2023Leveraging User-Triggered Supervision in Contextual Banditscited by 0
  6. 2023Estimating Optimal Policy Value in General Linear Contextual Banditscited by 0
  7. 2025Decentralized Contextual Bandits with Network Adaptivitycited by 0
  8. 2025Improved Training Mechanism for Reinforcement Learning via Online Model Selectioncited by 0
  9. 2026Bayesian Online Model Selectioncited by 0
  10. 2026A Perturbation Approach to Unconstrained Linear Banditscited by 0
  11. 2026Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversarycited by 0
  12. 2026Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivitycited by 0