mlsanityData to 7 Oct 2026

LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits

arXiv 2403.03219 ↗First posted 5 Mar 2024cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

We investigate the linear contextual bandit problem with independent and identically distributed (i.i.d.) contexts. In this problem, we aim to develop a Best-of-Both-Worlds (BoBW) algorithm with regret upper bounds in both stochastic and adversarial regimes. We develop an algorithm based on Follow-The-Regularized-Leader (FTRL) with Tsallis entropy, referred to as the α-Linear-Contextual (LC)-Tsallis-INF. We show that its regret is at most O(log(T)) in the stochastic regime under the assumption that the suboptimality gap is uniformly bounded from below, and at most O(√T) in the adversarial regime. Furthermore, our regret analysis is extended to more general regimes characterized by the margin condition with a parameter β ∈ (1, ∞], which imposes a milder assumption on the suboptimality gap. We show that the proposed algorithm achieves Oleft(log(T)^frac1+β2+βT^frac12+βright) regret under the margin condition.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 30 of its 53 references that are in the map. First posted on arXiv 5 Mar 2024.

Builds on

30 of 53 references.

References · 30

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  6. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  7. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  8. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  9. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  10. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  11. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  12. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
18 more
  1. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  2. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  3. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  4. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  5. 2016BISTRO: An Efficient Relaxation-Based Method for Contextual Banditscited by 20
  6. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  7. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  8. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  9. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  10. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  11. 2023Best of Both Worlds Policy Optimizationcited by 17
  12. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  13. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  14. 2016Improved Regret Bounds for Oracle-Based Adversarial Contextual Banditscited by 13
  15. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  16. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  17. 2021Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Banditcited by 8
  18. 2016Online Learning with Low Rank Expertscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  2. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  3. 2026Model-Adaptive and Risk-Constrained Frequency Hopping Against Predictive Jammerscited by 0
  4. 2026Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Banditscited by 0