Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions

Seoungbin Bae; Dabeen Lee

cs.LGApr 24, 2026

Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity AssumptionsLogistic Bandits with \tilde{O}(\sqrt{dT}) Regret without Context Diversity Assumptions

Authors: Seoungbin Bae, Dabeen Lee

Organizations: Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Abstract

We study the $K$ -armed logistic bandit problem, where at each round, the agent observes $K$ feature vectors associated with $K$ actions. Existing approaches that achieve a rate-optimal $\tilde{\mathcal{O}}(\sqrt{dT})$ regret bound rely heavily on context diversity assumptions, such as strict positivity of the minimum eigenvalue of a context covariance matrix. These assumptions, however, impose strong restrictions on the context process, as they rule out the situation where the context vectors are concentrated in a low-dimensional subspace. In this paper, we propose SupSplitLog, which, to the best of our knowledge, is the first algorithm for logistic bandits that achieves $\tilde{\mathcal{O}}(\sqrt{dT})$ regret without any context diversity assumption. The key idea is to split the collected samples into two disjoint subsets when constructing estimators; one is used to compute an initial-point estimator, while the other is used to apply a Newton-type one-step correction procedure. The splitting rule is carefully designed to balance the accuracy requirements of the initial-point estimator and the one-step correction procedure. Moreover, SupSplitLog strictly improves on the existing algorithms in terms of the dependence on dimension $d$ in the regret upper bound. Furthermore, SupSplitLog can be adapted simply to deduce a regret bound that grows with a data-dependent complexity measure, avoiding a direct dependence on $d$ , which is favorable when the context vectors are concentrated in a low-dimensional subspace. We also provide experimental results that demonstrate numerically the superiority of our algorithm, validating the theoretical results.

Explore similar work

Sep 14, 2026cs.LG

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let

d

be the dimension,

K

be the menu size, and

T

the time horizon. For

2\le K\le d

, we prove an upper bound

\widetilde O(K^{1/4}\sqrt{dT})

. When

T\ge d^2

, we further prove a lower bound

Ω(K^{1/4}\sqrt{dT})

. Thus, for

T\ge d^2

and

2\le K\le d

, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on

K

is optimal. Compared with the previous

\widetilde O(\sqrt{dKT})

bound, our upper bound improves the dependence on

K

by a factor of

K^{1/4}

. For

K\ge d

, we prove an upper bound

\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)

and a lower bound

Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)

. Here,

\widetilde O_{d,T}

omits logarithmic factors only in

d

and

T

. In particular, for polynomially large

K\ge d

, the upper and lower bounds both scale as

d^{3/4}\sqrt T

up to logarithmic factors, improving the standard

\widetilde O(d\sqrt T)

rate by a factor of

d^{1/4}

. As

K

grows further, the regret smoothly recovers the

d\sqrt T

scale once

\log K

reaches order

d

Tianyuan Jin

Topic pending

Ask PDF

May 19, 2026cs.LG

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

Multi-Objective Bandits Adaptive Sampling Reward Learning

Ask PDF

May 31, 2026stat.ML

Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates

We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only

O(\log\log T)

parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in

T

) simultaneously in both the small-

K

and large-

K

regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under

O(\log\log T)

parameter updates that are also computationally efficient in practice.

Sanghoon Yu, Min-hwan Oh

Updates Rare Events

Ask PDF