On the Performance of Thompson Sampling on Logistic Bandits
This work addresses the logistic bandit problem for researchers in online learning and bandit algorithms, offering a significant improvement in regret bounds by eliminating exponential dependence on β.
The paper tackles the logistic bandit problem, where prior regret bounds depend exponentially on the slope parameter β, and establishes that Thompson sampling achieves a Bayesian regret bound of Õ(d√T) independent of β, with a broader bound involving a new fragility dimension statistic.
We study the logistic bandit, in which rewards are binary with success probability $\exp(βa^\top θ) / (1 + \exp(βa^\top θ))$ and actions $a$ and coefficients $θ$ are within the $d$-dimensional unit ball. While prior regret bounds for algorithms that address the logistic bandit exhibit exponential dependence on the slope parameter $β$, we establish a regret bound for Thompson sampling that is independent of $β$. Specifically, we establish that, when the set of feasible actions is identical to the set of possible coefficient vectors, the Bayesian regret of Thompson sampling is $\tilde{O}(d\sqrt{T})$. We also establish a $\tilde{O}(\sqrt{dηT}/λ)$ bound that applies more broadly, where $λ$ is the worst-case optimal log-odds and $η$ is the "fragility dimension," a new statistic we define to capture the degree to which an optimal action for one model fails to satisfice for others. We demonstrate that the fragility dimension plays an essential role by showing that, for any $ε> 0$, no algorithm can achieve $\mathrm{poly}(d, 1/λ)\cdot T^{1-ε}$ regret.