Learning for Bandits under Action Erasures

Multi-armed bandit (MAB) problems have gained popularity in a wide range of applications that include recommendation systems, clinical trials, advertising, and distributed robotics [1, 2]. MABs are sequential decision problems where a learner, at each round, selects an action from a set of $K$ available actions (arms) and receives an associated reward; the aim is to maximize the total reward over $T$ rounds. In this paper, we develop a theoretical framework that explores a new setup, MAB systems with action erasures.

In particular, we consider a MAB system where the learner needs to communicate the actions to be taken to distributed agents over wireless channels subject to erasures with some probability $\epsilon$, while the rewards for the actions taken are directly available to the learner through external sensors. For example, the learner may be regulating drone traffic in a slowly varying environment (weather conditions, obstacles) where passing by drones receive which path to take or which maneuvers to perform, and the learner monitors the outcome through video cameras, magnetic and other sensors. Similarly, since online learning has been used in medical micro-robots [3, 4], our setup can help with problems such as directing inside veins micro-robots on how to move or how much of a medical substance to release, and observing the results through patient medical imaging and vital sign measurements. In our model, while the agent knows if an action is erased, the learner does not (there is no feedback); therefore, the learner at each round receives a reward that may be a result of playing the requested action or another action (if an erasure occurs).

Note that at any given round, although the requested action may be erased and not received by the agent, the agent still needs to play an action - the micro-robot needs to release some amount (perhaps zero) of substance and the drone needs to continue moving in some way. We make the assumption that if at a round the agent does not receive an action, the agent continues to play the most recently received action, until a new action is successfully received to replace it. This is we believe a reasonable assumption. Indeed, during exploitation, we would like the agents to persistently play the identified optimal action, which this strategy achieves. In contrast, as we discuss in Section III playing a random or a fixed action results in suboptimal performance, while using more sophisticated strategies (e.g., keeping track of all previous actions played and accordingly optimizing) may not be possible in distributed systems, where multiple agents may be playing different actions and where agents may not even be able to observe the rewards.

To the best of our knowledge, this setup has not been systematically studied, although there exists extensive MAB literature.

Indeed, existing work has examined MAB systems under a multitude of setups and constraints such as stochastic bandits [5, 6, 7], adversarial bandits [8, 9, 10], or contextual bandits [10, 11]; and over a number of distributed setups as well [12, 13, 14, 15]. In particular, a number of works examine the case where rewards are corrupted adversarially or stochastically [16, 17, 18, 19]. However, all the works we know of assume that the requested actions can be sent through perfect communication channels. This assumption makes sense for delay-tolerant applications, where we can leverage feedback and error-correcting codes to ensure perfect communication of the desired action; yet as the applicability of the MAB framework expands to agents, such as micro-robots, that are communication limited, we believe that our proposed model can be of interest, both in terms of theory and practice.

The main questions we ask (and answer) in this paper are: for our action erasure model (i) what is an optimal strategy? and (ii) if a MAB algorithm is already deployed, can we couple it, at low regret cost, with a generic layer, akin to erasure coding, that makes the MAB algorithm operation robust to erasures?

Our main contributions include:

• •

  We propose a scheme that can work on top of any MAB algorithm and make it robust to action erasures. Our scheme results in a worst-case regret over the erasure channel 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\in[0,1)$ is the erasure probability.

• •

  We propose a modification of the successive arm elimination algorithm and prove that its worst-case regret is $\tilde{O}(\sqrt{KT}+K/(1-\epsilon))$.

• •

  We prove a matching $\Omega(\frac{K}{1-\epsilon})$ regret lower bound.

In this paper we consider a specific agent operation, namely, the agent simply plays the most recently received action. In this section, we argue that this is a reasonable choice, by considering alternate simple strategies and explaining why they do not work well. We also discuss the technical challenges of our approach.

We note that our selected agent strategy introduces memory and a challenge in the analysis since it creates a more complicated dependency between the action and erasures. For example, any of the previously sent actions by the learner has a non-zero probability of being played at the current iteration, where the probability changes with time and the sequence of previous actions. In the previous two strategies, the learner still observes a reward with fixed mean and can be treated as a valid MAB instance (although the optimal action might be different from the ground truth). The last received action strategy unfortunately changes the reward distribution and standard MAB analysis no longer holds.

In this section we propose a scheme that works on top of any MAB algorithm to make it robust to erasures. Our scheme adds a form of repetition coding layer on top of the MAB algorithm operation. In particular, if the underlying MAB algorithm selects an action to play, our scheme sends the action chosen by the algorithm $\alpha$ times to the agent, and only associates the last received reward with the chosen action (hence the name Repeat-the-Instruction). Since the agent plays the last received action, one successful reception within the $\alpha$ slots is sufficient to make the last reward sampled from the distribution of the chosen arm. Thus our algorithm, summarized in Agorithm 1, effectively partitions the $T$ rounds into $T/\alpha$ groups of rounds, where each group of $\alpha$ rounds is treated by the underlying bandit algorithm as one time slot. The next theorem describes what is the resulting performance.

Proof. We use “run" to refer to the $\alpha$ rounds that repeat each action dictated by ALG. Let $G$ be the event that all runs contain at least one round with no erasure. Conditioned on $G$, the maximum number of consecutive plays for an action due to erasures is $2\alpha-1$ (across two runs, when the action transmitted at the first round of the first run is not erased, while the first $\alpha-1$ rounds of the next run are erased). Hence, we have that

where $a^{\star}$ is the optimal arm, the second term bounds the regret for the first $\alpha$ iterations. Note that, conditioned on $G$, if $t\equiv 0\text{ mod }\alpha$ with $t\geq\alpha$, we have that $\tilde{a}_{t}=a_{t-\alpha+1}$, that is, the reward $r_{t}$ is sampled from arm $a_{t-\alpha+1}$. Indeed in Algorithm 1 $r_{t}$ is the reward associated with arm $a_{t-\alpha+1}$ for $t\equiv 0\text{ mod }\alpha,t\geq\alpha$. We observe that as erasures occur independently of the bandit environment and learners actions, we have that for $t\equiv 0\text{ mod }\alpha,t\geq\alpha$, any set $A\subseteq\mathbb{R}$ and action $a_{t-\alpha+1}$, we have that $\mathbb{P}[r_{t}\in A|G,a_{t-\alpha+1}]=\mathbb{P}[r_{t}\in A|\tilde{a}_{t}=a_{t-\alpha+1}]$ (note that $G$ only depends on erasures). In particular, conditioned on $G$, the algorithm ALG receives rewards generated from a bandit instance with the same reward distributions as the original instance, hence, the same gaps, and time horizon $\lceil\frac{T}{\alpha}\rceil$. Hence, its regret is upper bounded by $R^{\text{ALG}}_{\lceil\frac{T}{\alpha}\rceil}(\{\Delta_{i}\}_{i=1}^{K})$. Substituting in (3) we get that

We finally upper bound the probability of the event $G$. Let $G_{i}$ denote the event that run $i$ contains at least one slot with no erasure. The probability of $G^{C}$ can be bounded as

where $(1)$ follows by the union bound. From (4), we get that

This follows from Theorem 1 by observing that $\log(1/\epsilon)=\Omega(1-\epsilon)$, and that the worst-case regret for any algorithm is $\Omega(\sqrt{KT})$. The next corollary follows by substituting the regret bound of the UCB algorithm [5, 7] in Theorem 1.

The intuition behind the repeat-the-instruction algorithm is that we do not frequently switch between arms - and thus playing the last successfully received action often coincides with playing the desired action. In this section, we propose “Lingering Successive Arm Elimination" (L-SAE), an algorithm that by design does not frequently switch arms, and evaluate its performance; in the next section, we prove a lower bound establishing L-SAE is order optimal.

L-SAE builds on the Successive Arm Elimination (SAE) algorithm [22]. SAE works in batches of exponentially growing length, where at the end of each batch the arms that appear to be suboptimal are eliminated. In batch $i$, each of the surviving arms is pulled $4^{i}$ times. We add two modifications to SAE to make it robust to erasures. First, we do not use the frequent arm switches of the first batches, when $4^{i}$ is small. Instead, in the first batch, the algorithm pulls each arm $4\alpha$ times. Then, the number of pulls for surviving arms in a batch is $4$ times that of the previous batch. Second, we ignore the first half of the samples for each arm. This ensures that all the chosen rewards are picked from the desired arm with high probability, as the probability of half the samples being erased is small. Given these modifications, we also update the arm elimination criterion to account for the higher variance in the mean estimates. In particular, the algorithm starts with $A=[K]$ as the good arms set and at the end of batch $i$, the algorithm eliminates arms with empirical mean that is away by more than $\sqrt{\log(KT)/(\alpha 4^{i-2})}$ from the empirical mean of the arm that appears to be best. The pseudo-code of the algorithm is provided in Algorithm 2.

By the exponential increase in the number of pulls of each arm, we get that until eliminated, arm $a$ will be pulled by the learner at most

for some absolute constant $c>0$. We also notice that on event $G$, the agent will pull arm $i$ at most $4T_{i}(T)$ times. This results in a regret that is at most $c(\alpha+\log(KT)/\Delta_{a})$. Summing the regret over all arms, we get that conditioned on $G\cap G^{\prime}$ we have that

The proof is concluded by noticing that $\log(1/\epsilon)=O(1-\epsilon)$. $\blacksquare$
The previous theorem directly implies the following worst-case regret bound $R_{T}\leq c\left(\frac{K\log T}{1-\epsilon}+\sqrt{KT}\right).$

We here prove a lower bound that matches the upper bound in Theorem 2 up to $\log$ factors. A lower bound of $\Omega(\sum_{i:\Delta_{i}>0}\frac{1}{\Delta_{i}})$ on the gap-dependent regret is already provided in [20] and a lower bound on the worst-case regret of $\Omega(\sqrt{KT})$ is provided in [21]. Thus it suffices to prove a lower bound of $\Omega(K/(1-\epsilon))$ which we provide next in Theorem 3.

We will show that there is no policy $\pi$ that can make $\mathbb{E}[R_{T}(\pi,\nu_{i})|E_{i}\cap E^{\prime}_{i}]$ to be small for all $i$. We first note that there are at least¹¹1We assume for simplicity that $K$ is divisible by $4$. The proof easily generalizes by taking the floor in divisions, which only affects the constants. $K/2$ arms with $\mathbb{P}[E^{\prime}_{i}]\geq 1/2$. Pick a set $I\subseteq[K]$ with $|I|=K/2$, and $\mathbb{P}[E^{\prime}_{i}]\geq 1/2$ $\forall i\in I$. Now define the event $\mathcal{P}_{i}$:
$\mathcal{P}_{i}$: arm $i$ is picked no more than $\frac{1}{\log(1/\epsilon)}$ times by the learner in the first $\frac{K}{4\log(1/\epsilon)}$ rounds.
We next consider the minimum worst case probability of $\mathcal{P}_{i}$ conditioned on $E_{i}\cap E^{\prime}_{i}$ under the distribution induced by instance $\nu_{i}$; namely,

Let the set $A$ denote the indices of arms for which $\mathcal{P}_{i}$ holds, i.e., $A=\{i\in I|\mathcal{P}_{i}\}$, and let $B=I/A$. We have that $A,B$ are disjoint and their union is the set $I$. Moreover, the quantity in (13) can be rewritten as

We make two observations: (i) after $\frac{K}{4\log(1/\epsilon)}$ rounds, there exist at least $\frac{|I|}{2}=\frac{K}{4}$ arms in $I$ for which $\mathcal{P}_{i}$ holds (hence, $|A|\geq|I|/2$ and $|B|\leq|I|/2$); and (ii) if for instance $\nu_{i}$, conditioned on $E_{i}\cap E^{\prime}_{i}$, arm $i$ is picked less than $1/\log(1/\epsilon)$ times by the learner, then all the rewards received by the learner will be zeros, thus no information will be provided to the policy during the first $\frac{K}{4\log(1/\epsilon)}$ rounds.
From observation (ii) and the fact that the result of whether $i\in A$ or not, does not change after the first reward feedback that is $1$, it follows that the optimal value for (13) does not change if the learner does not observe rewards. Hence, the learner can proceed assuming that all previous rewards are zeros. As a result, the learner can decide on the arms to pull in the first $K/(4\log(1/\epsilon))$ slots ahead of the time (i.e., at $t=1$; since no feedback is required); equivalently, the learner can divide the set $I$ into two sets $A$ and $B$ (possibly in a random way) ahead of the time with $|B|\leq|I|/2$ (from observation $(i)$). As the learner decides on $A$ ahead of the time, the probability of $i\in A$ does not depend on the instance, reward outcomes and $\tilde{a}_{0}$, hence, we can simply denote $\mathbb{P}_{\nu_{i}}[i\in A|E_{i}\cap E^{\prime}_{i}]$ as $\mathbb{P}[i\in A]$. This shows that, the problem of minimizing $\max_{i\in I}\mathbb{P}_{\nu_{i}}[\mathcal{P}_{i}|E_{i}\cap E^{\prime}_{i}]$ is equivalent to partitioning the set $I$ into two sets $A$ and $B$ (with $A$ containing the indices where $\mathcal{P}_{i}$ holds), $|A|\leq|I|/2$ and with the goal of minimizing $\max_{i\in I}\mathbb{P}[i\in A]$. It is easy to see that the minimum value for $\max_{i\in I}\mathbb{P}[i\in A]$, and similarly, $\max_{i\in I}\mathbb{P}_{\nu_{i}}[\mathcal{P}_{i}|E_{i}\cap E^{\prime}_{i}]$, is at least $1/2$ as $\sum_{i=1}^{|I|}\mathbb{P}[i\notin A]\leq|I|/2$.

Hence, for any policy $\pi$, there is an instance $\nu_{i},i\in I$ such that conditioned on $E_{i}\cap E^{\prime}_{i}$, arm $i$ is picked no more than $1/\log(1/\epsilon)$ times by the learner in the first $K/2\log(1/\epsilon)$ rounds with probability at least $1/2$. But for instance $\nu_{i}$, whenever arm $i$ is not pulled we incur a regret of value $1$, we get that there is $i\in I$ such that $\mathbb{P}\left[R_{T}(\pi,\nu_{i})\geq\frac{K}{4\log(1/\epsilon)}|E_{i}\cap E^{\prime}_{i}\right]\geq 1/2$. Then, we have that $\mathbb{E}[R_{T}(\pi,\nu_{i})|E_{i}\cap E^{\prime}_{i}]\geq c\frac{K}{\log(1/\epsilon)}$. By non-negativity of regret, we have that

where $(i)$ follows from the fact that $E_{i},E^{\prime}_{i}$ are independent, and $(ii)$ follows since $i\in I$ and thus $P(E^{\prime}_{i})\geq\frac{1}{2}$. Moreover, $\mathbb{P}[E_{i}]=\epsilon^{1/\log(1/\epsilon)}=e^{-1}$ and thus $\mathbb{E}[R_{T}(\pi,\nu_{i})]\geq c\frac{K}{\log(1/\epsilon)}$. The proof is concluded by observing that $\log(1/\epsilon)=O(1-\epsilon)$ for $\epsilon\geq 1/2$. $\hfill{\blacksquare}$