Improved Optimistic Algorithms for Logistic Bandits

By Louis Faury, Marc Abeille, Clément Calauzènes, Olivier Fercoq. 2020

140 citations recorded by the source corpus.

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 $\tilde{\mathcal{O}}(\kappa \sqrt{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 $\tilde{\mathcal{O}}(\sqrt{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.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Following Faury et al. (2020), and recalling Assumption 1, we define a data matrix and a transformation of ŵMLEt given by Vt = κλId + t−1∑ `=1 ( φ(τ1` )− φ(τ2` ) ) ( φ(τ1` )− φ(τ2` ) )> gt(w) = t−1∑ `=1 σ(〈φ(τ1` )− φ(τ2` ),w〉) ( φ(τ1` )− φ(τ2` ) ) + λw Then, the projected parameter, along with its…”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, methodology): “As stated above to estimate the reward parameter we rely on the recent results by Russac et al. (2021) who in term built on earlier work (Faury et al., 2020; Filippi et al., 2010) that analyzed the GLM-UCB algorithm.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…comparisons (Yue et al., 2012; Zoghi et al., 2014b; Yue and Joachims, 2009, 2011; Saha and Krishnamurthy, 2022; Ghoshal and Saha, 2022; Saha and Gopalan, 2018a; Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha and Gopalan, 2018b, 2019; Faury et al., 2020).”
Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint (2023, methodology): “Given x, a c , a r , fitting the model with the loss in Equation (21) yields a MLE for the preference probability (Lemma E.1) by training the LLM as a reward model.”
Contextual Slate GLM Bandits with Limited Adaptivity (2026, unknown): “Intuitively, κ quantifies the deviation of the reward model from linearity, and can be exponential in ∥ θ ⋆ ∥ 2 [FACF20].”
Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback (2025, unknown): “…Faury et al., 2022], we assume that ∥ θ ⋆ ∥ 2 ≤ S , where S is known to the learner, and √ Recent logistic bandit literature [Filippi et al., 2010, Faury et al., 2020, Abeille et al., 2021, Faury et al., 2022] also identifies a critical parameter κ , that captures the non-linearity of the reward…”