On the Performance of Thompson Sampling on Logistic Bandits
On the Performance of Thompson Sampling on Logistic Bandits
复制标题
汤普森采样对Logistic Bandits的性能研究
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Benjamin Van Roy
中科院分区：
文献类型：
--
作者：
Shi Dong;Tengyu Ma;Benjamin Van Roy
我们研究逻辑斯蒂多臂老虎机问题，其中奖励为二元的，成功概率为\(\frac{\exp(\beta a^\top \theta)}{1 + \exp(\beta a^\top \theta)}\)，动作\(a\)和系数\(\theta\)均在\(d\)维单位球内。尽管此前针对逻辑斯蒂多臂老虎机的算法所给出的遗憾界对斜率参数\(\beta\)呈现指数依赖关系，但我们为汤普森采样（Thompson Sampling）建立了一个与\(\beta\)无关的遗憾界。具体而言，我们证明了，当可行动作集与可能的系数向量集相同时，汤普森采样的贝叶斯遗憾为\(\tilde{O}(d\sqrt{T})\)。我们还建立了一个更具普适性的\(\tilde{O}(\frac{\sqrt{d\eta T}}{\lambda})\)界，其中\(\lambda\)是最坏情况下的最优对数优势比，\(\eta\)是“脆弱维度”，这是我们定义的一个新统计量，用于刻画一个模型的最优动作对其他模型的满足程度。我们通过证明对于任意\(\epsilon > 0\)，不存在算法能实现\(\mathrm{poly}(d, 1/\lambda)\cdot T^{1 - \epsilon}\)的遗憾，来说明脆弱维度起着至关重要的作用。
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.