mlsanityData to 13 Oct 2026

Jointly Efficient and Optimal Algorithms for Logistic Bandits

arXiv 2201.01985 ↗First posted 6 Jan 2022cs.LGcited by 41

Not on the map. Why?

Abstract (arXiv)

Logistic Bandits have recently undergone careful scrutiny by virtue of their combined theoretical and practical relevance. This research effort delivered statistically efficient algorithms, improving the regret of previous strategies by exponentially large factors. Such algorithms are however strikingly costly as they require Omega(t) operations at each round. On the other hand, a different line of research focused on computational efficiency (O(1) per-round cost), but at the cost of letting go of the aforementioned exponential improvements. Obtaining the best of both world is unfortunately not a matter of marrying both approaches. Instead we introduce a new learning procedure for Logistic Bandits. It yields confidence sets which sufficient statistics can be easily maintained online without sacrificing statistical tightness. Combined with efficient planning mechanisms we design fast algorithms which regret performance still match the problem-dependent lower-bound of Abeille et al. (2021). To the best of our knowledge, those are the first Logistic Bandit algorithms that simultaneously enjoy statistical and computational efficiency.

Key facts. Cited by 41 papers in the map (data through 13 Oct 2026). Builds on 12 of its 19 references that are in the map. First posted on arXiv 6 Jan 2022.

Builds on

12 of 19 references.

References · 12

  1. 2021Convex optimizationcited by 2,488
  2. 2019Introduction to Online Convex Optimizationcited by 798
  3. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  4. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  5. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  6. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  7. 2017Provably Optimal Algorithms for Generalized Linear Contextual Banditscited by 38
  8. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  9. 2020Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Banditscited by 31
  10. 2020An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Samplingcited by 30
  11. 2015Online Stochastic Linear Optimization under One-bit Feedbackcited by 26
  12. 2020Efficient improper learning for online logistic regressioncited by 16

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 11; 2025: 10; 2026: 15.

41 papers.

Sort:

By area:

  1. 2024Active Preference Optimization for Sample Efficient RLHFcited by 61
  2. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 28
  3. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  4. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  5. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  6. 2022Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Banditscited by 19
  7. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  8. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 14
  9. 2023Exploration via linearly perturbed loss minimisationcited by 13
  10. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  11. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  12. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
29 more
  1. 2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
  2. 2023VITS : Variational Inference Thompson Sampling for contextual banditscited by 6
  3. 2024Second Order Methods for Bandit Optimization and Controlcited by 5
  4. 2025Neural Logistic Banditscited by 5
  5. 2024Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewardscited by 3
  6. 2025Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithmcited by 3
  7. 2024Near Optimal Pure Exploration in Logistic Banditscited by 2
  8. 2025Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedbackcited by 2
  9. 2025Achieving Limited Adaptivity for Multinomial Logistic Banditscited by 2
  10. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  11. 2026Eluder dimension: localise it!cited by 2
  12. 2023Overcoming Prior Misspecification in Online Learning to Rankcited by 1
  13. 2025Preference Learning with Response Time: Robust Losses and Guaranteescited by 1
  14. 2026Learning Contextual Runtime Monitors for Safe AI-Based Autonomycited by 1
  15. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  16. 2026Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptionscited by 1
  17. 2026Generalized Linear Bandits with Memorycited by 1
  18. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  19. 2025Exploration via Feature Perturbation in Contextual Banditscited by 0
  20. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0
  21. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0
  22. 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPscited by 0
  23. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0
  24. 2026Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identificationcited by 0
  25. 2026Variance-sensitive Thompson sampling for generalised linear bandits, revisitedcited by 0
  26. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0
  27. 2026Contextual Slate GLM Bandits with Limited Adaptivitycited by 0
  28. 2026On the Complexity of Preference-Based Banditscited by 0
  29. 2026Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairnesscited by 0