On the Performance of Thompson Sampling on Logistic Bandits

Abstract

We study the logistic bandit, in which rewards are binary with success probability $\exp (\beta a^{\top }\theta )/(1+\exp (\beta a^{\top }\theta ))$ and actions $a$ and coefficients $\theta$ 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 $\beta$, we establish a regret bound for Thompson sampling that is independent of $\beta$. 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\eta T}/\lambda )$ bound that applies more broadly, where $\lambda$ is the worst-case optimal log-odds and $\eta$ 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 $\epsilon >0$, no algorithm can achieve $\mathrm{poly}(d,1/\lambda )\cdot T^{1-\epsilon }$ regret.

arXiv commentAccepted for presentation at the Conference on Learning Theory (COLT) 2019

References in corpus (3)

• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• Information Directed Sampling for Stochastic Bandits with Graph Feedback

Cited by in corpus (11)

• Improved Optimistic Algorithms for Logistic Bandits
• Randomized Exploration in Generalized Linear Bandits
• Algorithms for Non-Stationary Generalized Linear Bandits
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Reinforcement Learning, Bit by Bit
• Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
• On the Theory of Reinforcement Learning with Once-per-Episode Feedback
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits
• Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification
• On Learning to Rank Long Sequences with Contextual Bandits