# Learning for Bandits under Action Erasures

arXiv: https://arxiv.org/abs/2406.18072 · HTML: https://mlsanity.com/paper/2406.18072/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Builds on (most cited first, 4 of 4)

- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)

## Abstract (arXiv)

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/√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 TildeO(√KT+K/(1-ε)), which we prove is optimal by providing a matching lower bound.