Unknown Delay for Adversarial Bandit Setting with Multiple Play
This addresses a challenge in robotics and similar applications where multiple actions are taken simultaneously, but it is incremental as it extends existing single-play methods to multiple play with delays.
The paper tackles the problem of unknown delays in adversarial multi-armed bandits with multiple arms selected per round, proposing the DEXP3.M algorithm and showing its regret bound is only slightly worse than that of the single-play DEXP3 algorithm.
This paper addresses the problem of unknown delays in adversarial multi-armed bandit (MAB) with multiple play. Existing work on similar game setting focused on only the case where the learner selects an arm in each round. However, there are lots of applications in robotics where a learner needs to select more than one arm per round. It is therefore worthwhile to investigate the effect of delay when multiple arms are chosen. The multiple arms chosen per round in this setting are such that they experience the same amount of delay. There can be an aggregation of feedback losses from different combinations of arms selected at different rounds, and the learner is faced with the challenge of associating the feedback losses to the arms producing them. To address this problem, this paper proposes a delayed exponential, exploitation and exploration for multiple play (DEXP3.M) algorithm. The regret bound is only slightly worse than the regret of DEXP3 already proposed for the single play setting with unknown delay.