Stochastic Bandits with Delayed Composite Anonymous Feedback
This addresses a complex bandit setting relevant for applications with aggregated feedback, but it is incremental as it extends existing UCB methods.
The paper tackles the Multi-Armed Bandit problem with stochastic delayed composite anonymous feedback, where rewards are spread over future time steps and cannot be linked to specific past actions, and presents two phase-based UCB algorithms that achieve sub-linear regret guarantees.
We explore a novel setting of the Multi-Armed Bandit (MAB) problem inspired from real world applications which we call bandits with "stochastic delayed composite anonymous feedback (SDCAF)". In SDCAF, the rewards on pulling arms are stochastic with respect to time but spread over a fixed number of time steps in the future after pulling the arm. The complexity of this problem stems from the anonymous feedback to the player and the stochastic generation of the reward. Due to the aggregated nature of the rewards, the player is unable to associate the reward to a particular time step from the past. We present two algorithms for this more complicated setting of SDCAF using phase based extensions of the UCB algorithm. We perform regret analysis to show sub-linear theoretical guarantees on both the algorithms.