Introduction
The "logistic bandit" problem serves as a critical mathematical framework for modeling sequential decision-making with binary outcomes, such as whether a user clicks an ad or a patient responds to a treatment. While Thompson Sampling is a widely used heuristic for these problems, its theoretical guarantees have historically lagged behind its empirical performance. Specifically, prior analyses suggested that the difficulty of the problem grows exponentially with the "sharpness" of the signal—a result that contradicts both intuition and practical observation. This paper, presented at COLT 2019, resolves this discrepancy by providing a new, tighter regret bound for Thompson Sampling.
What Problem Does This Paper Address?
In a logistic bandit, an agent selects an action $a$ and receives a binary reward. The probability of success is modeled by the logistic function: $P(\text{reward}=1) = \text{exp}(\beta a^\top \theta) / (1 + \text{exp}(\beta a^\top \theta))$. Here, $\beta$ represents the "slope" or "separability" of the model.
Intuitively, a larger $\beta$ should make the problem easier because the distinction between the optimal action and suboptimal ones becomes more pronounced. However, traditional frequentist and Bayesian bounds for algorithms like GLM-UCB and earlier Thompson Sampling analyses included a factor of $e^\beta$. This meant that as the signal became stronger (larger $\beta$), the theoretical performance guarantees became exponentially worse.
The Theoretical Gap
The core challenge was that existing analysis techniques were too loose to capture the true complexity of the logistic model. By relying on the global Lipschitz constant of the logistic function, previous researchers were forced to include the $e^\beta$ term to account for the "flat" regions of the curve.
As shown in the table above, the authors' new analysis for Thompson Sampling achieves a regret bound that is independent of $\beta$, provided certain geometric conditions are met. This aligns the theory with the intuitive understanding that sharper signals should not penalize the learner.
A New Analytical Framework: Fragility Dimension
The authors move away from standard Lipschitz-based arguments and instead employ an information-theoretic analysis based on the Information Ratio. This approach quantifies the trade-off between immediate regret and the information gained about the hidden parameter $\theta$. To make this work, they introduce two novel statistics:
- Worst-case optimal log-odds ($\lambda$): This parameter assumes that for any possible model, the best action provides a success probability strictly greater than 0.5.
- Fragility Dimension ($\eta$): This is a geometric property of the action set. It measures the maximum number of models such that the optimal action for any one model is "bad" (success probability $\leq 0.5$) for all others. It captures how easily an agent can be "misled" by the geometry of the available choices.
Key Insights and Results
The paper's findings reshape our understanding of logistic bandits:
- The Aligned Case: If the set of possible actions is identical to the set of possible parameter vectors ($\mathcal{A} = \Theta$), Thompson Sampling achieves a regret bound of $\tilde{O}(d\sqrt{T})$, which is completely independent of the slope $\beta$. This matches the minimax lower bounds for linear bandits.
- General Regret Bound: In more complex geometries, the bound is $\tilde{O}(\frac{1}{\lambda}\sqrt{d \cdot (\eta \vee d) \cdot T})$. While $\eta$ can be large in pathological cases, it typically scales linearly with dimension $d$ in practical scenarios.
- The 50% Threshold: A significant revelation is that the behavior of the bandit changes fundamentally based on whether the optimal action's success probability exceeds 0.5. If the best possible outcome is still likely to be a failure, the authors conjecture that the exponential dependence on $\beta$ may be unavoidable.
Conclusion and Future Work
By introducing the fragility dimension, the authors demonstrate that the "hardness" of a logistic bandit is rooted in the geometry of the action space rather than the nonlinearity of the logistic function itself. This work provides the first $\beta$-independent regret bounds for Thompson Sampling, closing a significant gap in bandit theory. Future research may focus on extending these concepts to continuous action spaces and exploring the "low-reward" regime where the 0.5 probability threshold cannot be met.
Summary updated