2019/05/12 by Tengyu Ma, Dong, Shi, Ma, Tengyu +2 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.1905.04654
openalex publication_date 2019/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(d√(T)). We also establish a O(√(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 poly(d, 1/λ)⋅ T1-ε regret.