# Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion

arXiv: https://arxiv.org/abs/2310.18554 · HTML: https://mlsanity.com/paper/2310.18554/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 76 references that are in the map.
- First posted on arXiv 28 Oct 2023.

## Builds on (most cited first, 30 of 40)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [An elementary introduction to information geometry](https://mlsanity.com/paper/1808.08271/) (2018)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Universal Inference](https://mlsanity.com/paper/1912.11436/) (2019)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [Self-Concordant Analysis of Generalized Linear Bandits with Forgetting](https://mlsanity.com/paper/2011.00819/) (2020)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [Efficient improper learning for online logistic regression](https://mlsanity.com/paper/2003.08109/) (2020)
- [A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit](https://mlsanity.com/paper/2011.14033/) (2020)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)

## Built on by (most cited first, 24 of 24)

- [Active Preference Optimization for Sample Efficient RLHF](https://mlsanity.com/paper/2402.10500/) (2024)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [Neural Logistic Bandits](https://mlsanity.com/paper/2505.02069/) (2025)
- [Inference-Time Personalized Alignment with a Few User Preference Queries](https://mlsanity.com/paper/2511.02966/) (2025)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)
- [Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm](https://mlsanity.com/paper/2507.05306/) (2025)
- [Achieving Limited Adaptivity for Multinomial Logistic Bandits](https://mlsanity.com/paper/2508.03072/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Learning Contextual Runtime Monitors for Safe AI-Based Autonomy](https://mlsanity.com/paper/2601.20666/) (2026)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression](https://mlsanity.com/paper/2605.01628/) (2026)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [Linear Bandits with Non-i.i.d. Noise](https://mlsanity.com/paper/2505.20017/) (2025)
- [Exploration via Feature Perturbation in Contextual Bandits](https://mlsanity.com/paper/2510.17390/) (2025)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)

## Abstract (arXiv)

Logistic bandit is a ubiquitous framework of modeling users' choices, e.g., click vs. no click for advertisement recommender system. We observe that the prior works overlook or neglect dependencies in S ≥ lVert θ_star rVert2, where θ_star ∈ ℝd is the unknown parameter vector, which is particularly problematic when S is large, e.g., S ≥ d. In this work, we improve the dependency on S via a novel approach called it regret-to-confidence set conversion (R2CS), which allows us to construct a convex confidence set based on only the textitexistence of an online learning algorithm with a regret guarantee. Using R2CS, we obtain a strict improvement in the regret bound w.r.t. S in logistic bandits while retaining computational feasibility and the dependence on other factors such as d and T. We apply our new confidence set to the regret analyses of logistic bandits with a new martingale concentration step that circumvents an additional factor of S. We then extend this analysis to multinomial logistic bandits and obtain similar improvements in the regret, showing the efficacy of R2CS. While we applied R2CS to the (multinomial) logistic model, R2CS is a generic approach for developing confidence sets that can be used for various models, which can be of independent interest.