The stochastic generalised linear bandit is a well-understood model for sequential decision-making problems, with many algorithms achieving near-optimal regret guarantees under immediate feedback. However, the stringent requirement for immediate rewards is unmet in many real-world applications where the reward is almost always delayed. We study the phenomenon of delayed rewards in generalised linear bandits in a theoretical manner. We show that a natural adaptation of an optimistic algorithm to the delayed feedback achieves a regret bound where the penalty for the delays is independent of the horizon. This result significantly improves upon existing work, where the best known regret bound has the delay penalty increasing with the horizon. We verify our theoretical results through experiments on simulated data.
翻译:随机广义线性赌博机是一种用于顺序决策问题的一个广为人知的模型,许多算法在立即反馈下实现了近似最优的遗憾保证。然而,在许多实际应用中,及时的奖励是难以实现的,奖励几乎总是被延迟的。我们以理论的方式研究了在广义线性赌博机中延迟奖励的现象。我们展示了一种自然的乐观算法在延迟反馈上的一种适应,它实现了一个遗憾绑定,其中惩罚因延迟而独立于地平线。这个结果显著提高了现有的工作,其中最好的已知遗憾约束随地平线而增加。我们通过模拟数据的实验验证了我们的理论结果。