  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-\epsilon})$ away from the no-erasure worst-case regret of the
underlying MAB algorithm, where $\epsilon$ 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-\epsilon))$, which we
prove is optimal by providing a matching lower bound.
