Learning What to Recommend: Minimax Optimal Simple Regret in Logistic Bandits

Problem Formulation
This paper investigates stochastic logistic bandits under the simple-regret objective. In this setting, a learner interacts with an environment over $T$ rounds, selecting actions $A_t$ from a set $\mathcal{A}$ and observing Bernoulli rewards $X_t$ with mean $\mu(\phi(A_t)^\top \theta^*)$, where $\mu$ is the sigmoid function, $\phi$ is a known feature map, and $\theta^*$ is an unknown parameter in $\mathbb{R}^d$. Unlike cumulative regret, where the goal is to maximize the sum of rewards during exploration, the simple-regret objective evaluates the learner solely on the quality of a single final recommendation $\hat{a}$ after $T$ rounds. The regret is defined as the difference between the expected reward of the optimal action and the expected reward of the recommended action.

A critical challenge in logistic bandits is the non-uniform informativeness of actions. Due to the sigmoid link, actions in "saturated" regions (where the mean reward is near 0 or 1) yield nearly deterministic rewards but provide little information about the parameter $\theta^*$. Conversely, actions near the origin (where the sigmoid is steepest) are highly informative but may yield lower immediate rewards. This creates a geometry where the actions best for immediate reward (exploitation) differ from those best for identifying the optimal action (exploration).

Methodology
The authors propose two curvature-aware algorithms designed to exploit the local geometry of the sigmoid function:

1. MULOG (Max-Uncertainty-Log): A deterministic pure-exploration algorithm.

   • Mechanism: MULOG maintains a confidence set $W_t$ for $\theta^*$ and constructs a curvature-weighted design matrix $L_t$. The uncertainty score for an action $a$ and parameter $\theta$ is defined as $U(a, \theta, L_t) = \sqrt{\dot{\mu}(\phi(a)^\top \theta)} \|\phi(a)\|_{L_t^{-1}}$, where $\dot{\mu}$ is the derivative of the sigmoid (representing local curvature).
   • Selection: In each round, the algorithm selects the action-parameter pair $(A_t, \theta_t)$ that maximizes this uncertainty score.
   • Termination: After $T$ rounds, it returns the action greedy with respect to a parameter vector sampled from the final confidence set.
   • Optimization: For finite action sets, the selection step reduces to solving a finite collection of convex optimization problems.

2. THATS (Try Hard Thompson Sampling): A randomized, computationally lighter alternative.

   • Mechanism: Instead of solving for the exact maximum uncertainty, THATS samples a direction $\tilde{\theta}_t$ from a zero-centered Gaussian distribution with covariance $L_t^{-1}$.
   • Selection: It selects the action maximizing the randomized uncertainty score $\sqrt{\dot{\mu}(\phi(a)^\top \bar{\theta}_t)} |\phi(a)^\top \tilde{\theta}_t|$, where $\bar{\theta}_t$ is a constrained maximum likelihood estimate.
   • Trade-off: This approach avoids the convex optimization required by MULOG but incurs a statistical cost, resulting in a slightly looser regret bound.

Key Contributions

• Minimax Lower Bound: The paper establishes a first-order minimax lower bound of order $\Omega\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, where $\kappa^*$ is the inverse slope of the sigmoid at the optimal action (i.e., $\kappa^* = 1/\dot{\mu}(\phi(a^*)^\top \theta^*)$).
  • Distinct Hardness Mechanism: Unlike cumulative regret lower bounds (e.g., Abeille et al., 2021) which rely on the cost of information (forcing the learner to play near-optimal arms), this lower bound is derived from a "shifted saturated hypercube" construction. In this construction, both statistical information and value sensitivity are controlled by the same local curvature in a saturated region. This reveals that even with the freedom to sample purely for information, the problem remains hard if the optimal action lies in a flat region of the sigmoid.
• Optimal Algorithms:
  • MULOG achieves a simple regret upper bound of $\tilde{O}\left(\frac{d}{\sqrt{\kappa^* T}}\right)$, matching the lower bound up to logarithmic factors. This is the first direct pure-exploration guarantee for logistic bandits that achieves instance-wise minimax optimality.
  • THATS achieves a bound of $\tilde{O}\left(\frac{d^{3/2}}{\sqrt{\kappa^* T}}\right)$. The extra $\sqrt{d}$ factor arises from using a geometry-agnostic randomized approximation to the max-uncertainty direction.
• Geometric Insight: The authors demonstrate that the worst-case geometry (shifted saturated instances) is not the only case. They show that "informative low-reward actions" (probes) can exist in the action set. These actions lie in the high-curvature region of the sigmoid, providing significant information about the optimal direction despite having low expected rewards.

Results

• Theoretical: The derived bounds confirm that the difficulty of logistic simple regret is governed by the curvature at the optimal action. The algorithms successfully control uncertainty in the curvature-weighted feature directions.
• Empirical: Experiments on both "hard" geometries (shifted saturated hypercubes) and "easy" geometries (with added informative probe arms) support the theoretical findings:
  • On hard instances, MULOG and THATS perform as predicted by the minimax bounds.
  • On easy instances with probe arms, pure-exploration methods (MULOG and THATS) significantly outperform cumulative-regret baselines (like Cumulative Thompson Sampling and online-to-batch conversions). The pure-exploration methods actively sample the low-reward, high-information probes, drastically reducing the rounds needed to reach a low simple regret threshold.
  • Cumulative-regret methods fail to exploit these probes effectively because their online-to-batch conversion penalizes the inclusion of low-reward actions in the final recommendation distribution.

Significance
The paper claims that pure exploration in logistic bandits possesses a distinct geometry from cumulative regret problems. The primary contribution is identifying that the local curvature at the optimal action ($\kappa^*$) is the governing factor for the first-order minimax rate. By developing algorithms that explicitly account for this curvature, the authors achieve minimax-optimal performance in the worst case. Furthermore, the work highlights a practical implication: in settings like A/B testing or reward-model data collection, actively seeking out "informative but low-reward" actions can substantially accelerate the identification of the best final policy, a behavior that standard cumulative-regret algorithms are structurally unable to exhibit. The results serve as a starting point for a sharper theory of decision-focused exploration in nonlinear bandits.