Delayed Feedback in Generalised Linear Bandits Revisited
This addresses a key limitation in sequential decision-making for real-world applications like advertising or recommendations where feedback is often delayed, offering a theoretical improvement over existing methods.
The paper tackles the problem of delayed rewards in stochastic generalised linear bandits, showing that an adapted optimistic algorithm achieves a regret bound with a delay penalty independent of the horizon, improving upon prior work where it increased with the horizon.
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.