An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Qin Ding;Cho-Jui Hsieh;J. Sharpnack
中科院分区：
文献类型：
--
作者：
Qin Ding;Cho-Jui Hsieh;J. Sharpnack
我们考虑的上下文强盗问题，玩家顺序决策的基础上，过去的观察，以最大限度地提高累积奖励。虽然已经提出了许多算法的上下文强盗，他们中的大多数依赖于找到最大似然估计在每次迭代，这需要$O（t）$时间在$t$-th迭代和内存效率低。解决这个问题的一个自然的方法是应用在线随机梯度下降（SGD），使每一步的时间和内存的复杂度可以减少到恒定的相对于$t$，但上下文的强盗政策的基础上在线SGD更新，平衡勘探和开发仍然难以捉摸。在这项工作中，我们表明，在线SGD可以应用到广义线性强盗问题。所提出的SGD-TS算法，它使用一个单步SGD更新来利用过去的信息，并使用汤普森采样探索，实现$\tilde{O}（\sqrt{dT}）$遗憾的总时间复杂度在$T$和$d$中线性缩放，其中$T$是总轮数，$d$是特征数。实验结果表明，SGD-TS算法在合成数据集和真实的数据集上的性能均优于现有算法.
We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. Although many algorithms have been proposed for contextual bandit, most of them rely on finding the maximum likelihood estimator at each iteration, which requires $O(t)$ time at the $t$-th iteration and are memory inefficient. A natural way to resolve this problem is to apply online stochastic gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant with respect to $t$, but a contextual bandit policy based on online SGD updates that balances exploration and exploitation has remained elusive. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information and uses Thompson Sampling for exploration, achieves $\tilde{O}(\sqrt{dT})$ regret with the total time complexity that scales linearly in $T$ and $d$, where $T$ is the total number of rounds and $d$ is the number of features. Experimental results show that SGD-TS consistently outperforms existing algorithms on both synthetic and real datasets.