Source-linked AI summary
Improved Optimistic Algorithms for Logistic Bandits
Louis Faury, Marc Abeille, Clément Calauzènes, Olivier Fercoq
TL;DR
Existing logistic-bandit regret guarantees can depend on κ, which is prohibitive when the sigmoid reward model is highly nonlinear. The paper studies improved optimistic algorithms and reports bounds whose dependencies on κ are reduced, with Logistic-UCB-2 retaining a second-order term.
Problem
Existing generalized-linear-bandit guarantees can scale poorly with κ, which is especially large for logistic bandits and can worsen regret guarantees and practical performance.
Source: Introduction · pp. 1–2Method
The paper develops optimistic logistic-bandit algorithms using a finer analysis of reward nonlinearity and a new self-normalized martingale tail inequality.
Source: Introduction · p. 2, §4.2 · p. 9Results
When κ = T, GLM-UCB’s guarantee is linear in T, Logistic-UCB-1’s regret scales as T^3/4, and Logistic-UCB-2’s second term scales as d^2T.
Source: §5 · p. 11Takeaways & Limitations
The discussion identifies instances where the new algorithms’ regret guarantees remain sublinear even when GLM-UCB’s guarantee becomes vacuous.
Source: §5 · p. 11The tail-inequality result assumes a process in B2(d) and martingale differences bounded in absolute value by 1.
Source: §3.1 · p. 6
Abstract
from arXiv · showhide
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.
Introduction
Generalized linear bandits model richer reward structures than linear bandits, but existing GLB guarantees can depend prohibitively on κ. For logistic bandits, this work develops optimistic algorithms with improved κ-dependence and a new martingale tail inequality.
Introduction
- Existing GLB regret guarantees depend on κ, which can be prohibitively large for highly nonlinear models and worsen both guarantees and practical performance.The logistic bandit is particularly affected because its sigmoid link is highly nonlinear and κ is large even in typical instances.Source: Introduction · p. 2
- A modified GLM-UCB answers Filippi et al. (2010)’s conjecture by improving the κ-dependence of frequentist regret guarantees.Previous work suggested a possible reduction from κ to √κ, but left the frequentist question open.Source: Introduction · p. 2
- A further optimistic algorithm pushes κ-dependence into a second-order term, yielding better regret guarantees.The work studies logistic bandits explicitly to improve the dependency on κ.Source: Introduction · p. 2
- A new Bernstein-like self-normalized martingale tail inequality is a key ingredient of the analysis and is presented as independently interesting.The inequality supports the improved treatment of logistic-bandit nonlinearity.Source: Introduction · p. 2
1. Preliminaries
The preliminaries define the logistic-bandit setting and the optimistic algorithm framework used in the paper. They also introduce the maximum-likelihood estimator and properties of the sigmoid loss relevant to the analysis.
1. Preliminaries
- The preliminaries define weighted ℓ2 norms, the smallest eigenvalue, positive-semidefinite matrix ordering, and asymptotic notation that suppresses logarithmic factors.For symmetric matrices, A ≻ B means A − B is positive semi-definite.Source: §1 · p. 2
1.1. Setting
- In the setting, rewards are Bernoulli with sigmoid mean µ(x_t^T θ*), where θ* is fixed but unknown and lies in a compact parameter set.The objective is to minimize cumulative pseudo-regret relative to the optimal arm.Source: §1.1 · pp. 2–3
1.2. Reminders on optimistic algorithms
- An optimistic algorithm selects an action using an estimator and exploration bonus; bounding prediction error with the bonus controls regret.Tighter prediction bounds can reduce the bonus and regret, while large bonuses can cause over-exploration and larger regret.Source: §1.2 · p. 3
1.3. Maximum likelihood estimate
- The regularized log-likelihood is strictly concave, and its maximizer defines the maximum-likelihood estimator; the negative log-loss is generalized self-concordant.For the sigmoid, the stated property is |¨µ| ≤ ˙µ.Source: §1.3 · pp. 3–4
2. Challenges and contributions
The paper targets regret bounds whose dependence on κ becomes prohibitive for logistic bandits. It develops locally informed prediction analysis and optimistic algorithms to reduce that dependence.
On the scaling of κ
- For click prediction with P(click)=10^-3, κ∼10^3; its exponential scaling with decision-set size can make existing κ-dependent guarantees prohibitive.The paper notes that κ can be even larger in some settings, including κ≥exp(S) when X=B2(d).Source: §2 · p. 4
Uniform vs local control over ˙µ
- Because the sigmoid reward is flat where repeated observations make estimation difficult, global derivative bounds can be loose; local analysis better reflects the reward there.The paper motivates switching from uniform derivative bounds to analysis localized to the relevant region of the sigmoid.Source: §2 · pp. 4–5
On Filippi et al. (2010)’s conjecture
- Logistic-UCB-1 improves previous guarantees by √κ, using a new Bernstein-like inequality and generalized self-concordance for local derivative comparisons.These tools compare sigmoid derivatives without uniform L and κ^-1 bounds.Source: §2 · p. 5
Dropping the κ dependency
- Logistic-UCB-2 achieves ˜O(d√T + κ log T) regret, moving κ out of the leading term and into a second-order term.The algorithm combines the refined prediction bound with careful design.Source: §2 · p. 5
3. Improved prediction guarantees
The section develops tighter logistic prediction bounds, beginning with a Bernstein-like self-normalized martingale inequality and confidence sets that reflect local sigmoid curvature. It then derives bounds whose first-order term uses local information while global quantities, including κ, are relegated to a second-order term.
3.1. New tail-inequality for self-normalized martingales
- The new Bernstein-like inequality handles martingale increments satisfying a Bernstein condition and supports tail bounds re-normalized by quadratic variation.In the stated case, it strictly improves bounds involving the scalar ω.Source: §3.1 · pp. 6–7
3.2. A new confidence set
- The resulting confidence sets are valid for θ* and use local curvature, producing non-ellipsoidal sets that do not penalize all estimators equally.The local metric H_t(θ) is described as better suited than V_t for measuring parameter distances.Source: §3.2 · pp. 7–8
3.3. Prediction error bounds
- Lemma 2 improves Filippi et al.’s prediction bound by √κ and rigorously establishes their asymptotic argument for finite-time adaptive design.The guarantee holds on event Eδ, with probability at least 1−δ.Source: §3.3 · p. 8
- Lemma 3 makes the first-order prediction term local through the sigmoid slope and H_t(θ), while global M and κ enter a quickly vanishing second-order term.This decomposition is the basis for the later Logistic-UCB-2 design.Source: §3.3 · p. 8
- The Lemma 3 bound depends on the choice of θ∈C_t, so the associated exploration bonus also requires careful design.The paper notes that the two terms in the bound cumulate at different rates.Source: §3.3 · p. 8
4. Algorithms and regret bounds
The section presents two optimistic algorithms for logistic bandits: Logistic-UCB-1 reduces the dependence on κ, and Logistic-UCB-2 moves it out of the leading regret term. Logistic-UCB-2 uses a refined prediction bound and a restricted set of admissible estimates.
4.1. Logistic-UCB-1
- Logistic-UCB-1 uses a feasible estimator and bonus to match the heuristic regret bound conjectured by Filippi et al. (2010, §4.2).Its regret guarantee improves previous results by a factor of √κ.Source: §4.1 · p. 9
4.2. Logistic-UCB-2
- Logistic-UCB-2 uses an improved prediction bound to remove Logistic-UCB-1’s remaining √κ dependence from the leading regret term.Because its bonus depends on the estimate, the method restricts the confidence set to admissible estimates so that the bonus can sum sub-linearly.Source: §4.2 · pp. 9–10
- Logistic-UCB-2 has a leading regret term independent of κ, with remaining κ-dependence only in a second-order term growing as log(T)^2.The bound follows from a prediction bound whose first bonus term accumulates sub-linearly and independently of κ, up to a second-order term growing as log(T).Source: §4.2 · p. 10
5. Discussion
The discussion concludes that tighter prediction bounds improve optimistic logistic-bandit regret guarantees, culminating in a leading term independent of κ. It identifies extensions to other GLMs and randomized algorithms as future directions.
5. Discussion
- Logistic-UCB-2’s leading regret term is independent of κ, bridging logistic and linear bandits up to polynomial terms in constants such as S.The discussion contrasts this with Logistic-UCB-1’s √κ dependence and previous guarantees’ κ dependence.Source: §5 · p. 11
- The approach may extend to other GLMs whose mean functions have analogous variance and generalized self-concordance properties, including Poisson regression.The paper identifies extending the results to other GLMs as an avenue for future work.Source: §5 · p. 11
- Extending the lessons for optimistic algorithms to randomized methods such as Thompson Sampling is proposed as future work.The authors note that randomized algorithms are often preferred in practice for their superior empirical performances.Source: §5 · p. 11
Appendix A. Proof of Theorem 1
The appendix proves the self-normalized martingale result using a pseudo-maximization argument adapted to a bounded parameter domain. It combines a mixture-process supermartingale with a stopping-time argument to obtain a high-probability bound.
Appendix A. Proof of Theorem 1
- The proof adapts the pseudo-maximization principle to ξ in B2(d), refining the Laplace-trick argument for a high-probability bound on the maximum of log M_t(ξ).The authors contrast this bounded domain with the unrestricted domain used in the linear-bandit argument they follow.Source: Appendix A · p. 13
- A density supported on B2(d) is used to form a mixture process that remains a non-negative supermartingale.The proof defines a density h on the ball and invokes the mixture-process supermartingale property.Source: Appendix A · p. 13
- A stopping-time construction yields a bound holding for all t with probability at least 1 − δ.The proof uses the stopping-time argument before combining its bounds to establish the announced result.Source: Appendix A · pp. 14–15
A.1. Proof of Lemma 5
The appendix establishes supporting martingale and prediction bounds, then uses the logistic loss’s self-concordance to control quantities needed for the regret analysis.
A.1. Proof of Lemma 5
- A.1 proves the mixture process is a non-negative supermartingale using a lemma for centered, almost surely bounded random variables.The lemma assumes variance σ² and |ε| ≤ 1.Source: §A.1 · pp. 15–16
A.2. Proof of Lemma 6
- A.2 bounds the ratio of the normalizing constants N(h)/N(g) by changes of variables and the volume of a d-dimensional ball.The ball’s volume scales proportionally to β^d.Source: §A.2 · pp. 16–17
Appendix B. Proofs of prediction and concentration results
- Appendix B relates the GLM quantities G_t and H_t to V_t, with both bounded below by κ^-1 V_t.The text also identifies α and G_t as quantities that arise naturally when studying GLMs.Source: Appendix B · p. 17
B.1. Proof of Lemma 1
- B.1 applies Theorem 1 to bounded martingale-difference residuals around the log-likelihood maximizer to prove the confidence result.The proof checks that the residual sequence is adapted and almost surely bounded by 1 before assembling the inequalities.Source: §B.1 · p. 18
B.2. Key self-concordant results
- B.2 uses the logistic loss’s generalized self-concordance, expressed as |µ''| ≤ µ', to derive lower bounds on µ' and control G_t.The section states that this control is used to relate G_t to H_t.Source: §B.2 · p. 19
B.3. Proof of claims in Section 3.2
The proofs establish high-probability membership in confidence sets and examine how matrix choices preserve local information or introduce dependence on κ.
B.3. Proof of claims in Section 3.2
- When θ̂_t∈Θ, the confidence-set width can be reduced by a factor of 2.Source: §B.3 · p. 20
- Self-concordance permits replacing G_t(θ*, θ^NL) with H_t(θ*), retaining local information and enabling use of Theorem 1 through Lemma 8.The passage says the replacement follows from Lemma 10.Source: §B.3 · p. 21
- Replacing G_t(θ*, θ^NL) with V_t trades local information for global information and adds a dependency on κ instead of S.Source: §B.3 · p. 21
- With probability at least 1−δ, θ* belongs to E_t(δ) for every t≥1.The proof also states high-probability membership in E^NL, though its passage is truncated.Source: §B.3 · pp. 20–21
B.4. Proof of Lemma 2
These proofs establish prediction bounds on a high-probability event, first using local curvature and then refining the analysis to retain a separate κ-dependent term.
B.4. Proof of Lemma 2
- On E_δ, Lemma 2 gives a prediction bound for every t≥1, θ∈C_t(δ), and x∈X.Source: §B.4 · p. 22
- The Lemma 2 proof uses self-concordance to replace G_t(θ*, θ) with H_t(θ*) and H_t(θ), but loses local information twice.This route uses a 1+2S factor instead of √κ; the proof says Lemma 3 corrects these losses.Source: §B.4 · p. 22
B.5. Proof of Lemma 3
- Lemma 3’s proof uses a first-order Taylor expansion and separates a local G_t-norm term from a κ-weighted global term.Source: §B.5 · pp. 22–23
B.6. Proof of Lemma 4
The proof bounds cumulative terms on a good event and connects optimistic action selection to regret through a prediction-error bonus condition.
B.6. Proof of Lemma 4
- Under E_δ, Lemma 13 gives a cumulative bound with no κ dependence except in logarithmic terms.The result applies to the sequences specified in Lemma 13.Source: §B.6 · p. 23
- On E_δ, θ* belongs to W_t for every t, so these sets are nonempty; the proof rewrites W_t using monotonicity of the logistic derivative.Source: §B.6 · p. 23
C.1. Regret decomposition
- For an optimistic algorithm, the regret lemma yields its stated guarantee when the exploration bonus is at least the prediction error.Source: §C.1 · p. 25
C.2. Proof of Theorem 2
The theorem proofs apply the prediction and regret lemmas, while the appendix recalls a potential lemma for bounded feature sequences.
C.2. Proof of Theorem 2
- For Theorem 2, λ=d log(T) gives γ_T(δ)=O(d^1/2·log(T)^1/2) after applying Lemma 2 and the regret decomposition.Source: §C.2 · p. 26
C.3. Proof of Theorem 3
- For Theorem 3, the proof applies Lemma 3 and Lemma 4 through the regret decomposition; λ=d log(T) gives γ_T(δ)=O(d^1/2·log(T)^1/2).Source: §C.3 · p. 27
Appendix D. Useful lemmas
- Appendix D recalls an Elliptical Potential Lemma for bounded feature sequences and regularized V_t, attributed to Abbasi-Yadkori et al. (2011).Source: Appendix D · p. 27