Online Learning and Bandits with Queried Hints
Online Learning and Bandits with Queried Hints
复制标题
DOI：
10.48550/arxiv.2211.02703
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala
中科院分区：
文献类型：
--
作者：
Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala
我们考虑经典的在线学习和随机多军匪徒（MAB）问题，在每个步骤中，在线政策可以调查并找出少数数字（$ k $）的选择中的哪个选择更好（或损失）做出选择。在此模型中，我们得出了与经典的遗憾界面相比，其遗憾界限的依赖性呈指数级的依赖。特别是，我们表明，以$ k = 2 $的探测足以实现在线线性和凸优化的时间无关的后悔界限。相同数量的探针将随机mAb的遗憾与独立武器的遗憾从$ o（\ sqrt {nt}）$到$ O（n^2 \ log t）$，其中$ n $是武器数量和$ t $是地平线长度。对于随机mab，我们还考虑了一个更强大的模型，其中探针揭示了探测器的奖励值，并表明在这种情况下，$ k = 3 $探针足以实现与参数无关的常数遗憾，$ o（n^2） ）$。即使在比赛结束后，即使有完整的反馈也无法实现这种遗憾的界限，在制作比赛之前通过探测来展示有限的``建议''的力量。我们还向提示不完美的设置以及随机mAb的情况下提供了扩展，其中手臂的奖励可以相关。
We consider the classic online learning and stochastic multi-armed bandit (MAB) problems, when at each step, the online policy can probe and find out which of a small number ($k$) of choices has better reward (or loss) before making its choice. In this model, we derive algorithms whose regret bounds have exponentially better dependence on the time horizon compared to the classic regret bounds. In particular, we show that probing with $k=2$ suffices to achieve time-independent regret bounds for online linear and convex optimization. The same number of probes improve the regret bound of stochastic MAB with independent arms from $O(\sqrt{nT})$ to $O(n^2 \log T)$, where $n$ is the number of arms and $T$ is the horizon length. For stochastic MAB, we also consider a stronger model where a probe reveals the reward values of the probed arms, and show that in this case, $k=3$ probes suffice to achieve parameter-independent constant regret, $O(n^2)$. Such regret bounds cannot be achieved even with full feedback after the play, showcasing the power of limited ``advice'' via probing before making the play. We also present extensions to the setting where the hints can be imperfect, and to the case of stochastic MAB where the rewards of the arms can be correlated.