Learning for Bandits under Action Erasures
This addresses a practical issue for distributed systems using bandit algorithms in unreliable communication environments, with incremental improvements to existing methods.
The paper tackles the problem of multi-arm bandit learning when actions are communicated over erasure channels without feedback, proposing a scheme that makes any MAB algorithm robust to erasures, resulting in a worst-case regret at most a factor of O(1/√(1-ε)) away from no-erasure regret, and an optimal modified algorithm with regret Õ(√(KT) + K/(1-ε)).
We consider a novel multi-arm bandit (MAB) setup, where a learner needs to communicate the actions to distributed agents over erasure channels, while the rewards for the actions are directly available to the learner through external sensors. In our model, while the distributed agents know if an action is erased, the central learner does not (there is no feedback), and thus does not know whether the observed reward resulted from the desired action or not. We propose a scheme that can work on top of any (existing or future) MAB algorithm and make it robust to action erasures. Our scheme results in a worst-case regret over action-erasure channels that is at most a factor of $O(1/\sqrt{1-ε})$ away from the no-erasure worst-case regret of the underlying MAB algorithm, where $ε$ is the erasure probability. We also propose a modification of the successive arm elimination algorithm and prove that its worst-case regret is $\Tilde{O}(\sqrt{KT}+K/(1-ε))$, which we prove is optimal by providing a matching lower bound.