We show that the \emph{stochastic gradient} bandit algorithm converges to a
\emph{globally optimal} policy at an $O(1/t)$ rate, even with a \emph{constant}
step size. Remarkably, global convergence of the stochastic gradient bandit
algorithm has not been previously established, even though it is an old
algorithm known to be applicable to bandits. The new res
本研究提出了一种基于在线随机梯度下降的广义线性赌博机算法，它使用单步 SGD 更新来利用过去的信息并使用汤普森抽样实现探索，能够在探索与利用之间取得平衡，在合成和实际数据集上始终优于现有算法，其总时间复杂度为 T 和 d 的线性比例，其中 T 是总轮次数，d 是特征数量，并实现了 O（T）的遗憾，其中 T 是回合数。
通过分析高斯过程臂带问题，针对确定性观察结果，运用分支限定算法攻击了确定性情况并获得了更快的指数收敛率，显示出后悔随着时间推移而按高概率下降，估计呈现 O（e ^ - tau * t / (ln t)^（d/4））的结果，其中 d 是搜索空间的维度，tau 是目标函数在其全局最大值附近的行为所依赖的常数。