On the Performance of Thompson Sampling on Logistic Bandits

Abstract¶

We study the logistic bandit, in which rewards are binary with success probability exp(betaa^(top) theta) / (1 + exp(betaa^(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 tildeO(dsqrt(T)). We also establish a tildeO(sqrt(detaT)/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 poly(d, 1/lambda)* T^(1)-epsilon regret.

Links¶

Similar Papers¶