mlsanityData to 14 Oct 2026

The Pareto Regret Frontier for Bandits

arXiv 1511.00048 ↗First posted 30 Oct 2015cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

Given a multi-armed bandit problem it may be desirable to achieve a smaller-than-usual worst-case regret for some special actions. I show that the price for such unbalanced worst-case regret guarantees is rather high. Specifically, if an algorithm enjoys a worst-case regret of B with respect to some action, then there must exist another action for which the worst-case regret is at least Omega(nK/B), where n is the horizon and K the number of actions. I also give upper bounds in both the stochastic and adversarial settings showing that this result cannot be improved. For the stochastic case the pareto regret frontier is characterised exactly up to constant factors.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). First posted on arXiv 30 Oct 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

14 papers.

Sort:

  1. 2021The Pareto Frontier of model selection for general Contextual Banditscited by 24
  2. 2022Adaptively Exploiting d-Separators with Causal Banditscited by 18
  3. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  4. 2021Can Q-Learning be Improved with Advice?cited by 13
  5. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  6. 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
  7. 2022Online Learning with Off-Policy Feedbackcited by 4
  8. 2022Safety Aware Changepoint Detection for Piecewise i.i.d. Banditscited by 2
  9. 2024Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginalscited by 2
  10. 2025Best of Both Worlds: Regret Minimization versus Minimax Playcited by 2
  11. 2025Efficiently Solving Discounted MDPs with Predictions on Transition Matricescited by 2
  12. 2026Learning Safely Without Knowing the World:COMPASS-Hedgecited by 0
2 more
  1. 2026Trading off rewards and errors in multi-armed banditscited by 0
  2. 2026Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Banditscited by 0