# Improved Optimistic Algorithms for Logistic Bandits

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

## Key facts

- Cited by 118 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

## Built on by (most cited first, 30 of 118)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [DPO Meets PPO: Reinforced Token Optimization for RLHF](https://mlsanity.com/paper/2404.18922/) (2024)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHF](https://mlsanity.com/paper/2401.16335/) (2024)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Language Model Personalization via Reward Factorization](https://mlsanity.com/paper/2503.06358/) (2025)
- [Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.11489/) (2022)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences](https://mlsanity.com/paper/2403.01857/) (2024)
- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Generalized Linear Bandits with Limited Adaptivity](https://mlsanity.com/paper/2404.06831/) (2024)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2205.13924/) (2022)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Regret Bounds for Generalized Linear Bandits under Parameter Drift](https://mlsanity.com/paper/2103.05750/) (2021)
- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Exploration via linearly perturbed loss minimisation](https://mlsanity.com/paper/2311.07565/) (2023)
- [Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift](https://mlsanity.com/paper/2407.18676/) (2024)

## Abstract (arXiv)

The generalized linear bandit framework has attracted a lot of attention in recent years by extending the well-understood linear setting and allowing to model richer reward structures. It notably covers the logistic model, widely used when rewards are binary. For logistic bandits, the frequentist regret guarantees of existing algorithms are tildeO(kappa √T), where kappa is a problem-dependent constant. Unfortunately, kappa can be arbitrarily large as it scales exponentially with the size of the decision set. This may lead to significantly loose regret bounds and poor empirical performance. In this work, we study the logistic bandit with a focus on the prohibitive dependencies introduced by kappa. We propose a new optimistic algorithm based on a finer examination of the non-linearities of the reward function. We show that it enjoys a tildeO(√T) regret with no dependency in kappa, but for a second order term. Our analysis is based on a new tail-inequality for self-normalized martingales, of independent interest.