## 3 System Architecture
### Correlated Arms  
The deterministic nature of D-UCB poses challenges in the detection of reward changes in currently low-performing arms, which may eventually become the optimal ones in subsequent time steps, without incurring expensive arm exploration by increasing \(C\). Resets allow the agent to deal with this problem, enabling all actions to be sufficiently sampled. M-UCB samples all arms periodically to achieve this purpose. However, setting a proper full sampling period may be difficult without knowing the environment dynamics beforehand. A long period may not be sufficient to gather enough evidence to engage in a reset in due time, whereas a short period may gather redundant evidence, negatively impacting regret without added value. Moreover, the rewards from one arm can provide information on the (pseudo-)rewards of correlated arms [24], as often occurs in paths sharing network links, rendering these valuable in spreading the sampling over time rather than periodically.  
To cope with these challenges, React-UCB samples actions according to a distribution, ensuring that all arms have a positive probability of being sampled in every time step, while ensuring that the more promising arms, according to their accumulated rewards and correlations, are more densely sampled. In this way, the algorithm becomes continuously sensible to reward distribution changes, rather than only periodically. This stochastic approach borrows from algorithms such as Thompson-Sampling [27] and Exp3 [19], bringing a new algorithmic ability to handle adversarial bandits. An alternative to this approach would be to use pseudo-rewards to restrict, in each time step, the activity of the basic bandit algorithm (e.g., UCB) to a sub-set of competitive arms [24]. However, by not including randomness and by ruling out some arms in each time step, it is not clear how this alternative handles piecewise-stationary bandits.  
Let us define \(Y_{t}\) and \(Y_{t-1}\) as random variables representing the distributions underlying arm pulls \(I_{t}\) and \(I_{t-1}\), respectively. Although arm pulls in React-UCB are not actually ruled by these distributions, these will be used to reason about the value of each arm. Let us also define the probability that arm \(i\) has been pulled in the previous step, \(t-1\), as the softmax of its upper confidence bound, which, despite not being accurate, is a useful approximation (\(\eta\) to sharpen the distribution, \(\eta=10\) in our tests):  
\[P(Y_{t-1}=i)=\frac{e^{\eta U_{t-1}(i)}}{\sum_{k\in K}e^{\eta U_{t-1}(k)}}. \tag{25}\]  
Let the probability that arm \(i\) is the pulled one in the current time step \(t\), given that arm \(j\) was the pulled one in the previous time step, \(t-1\), be defined as the softmax of a correlation function between arms \(a\) and \(b\), \(s(a,b):\mathcal{K}^{2}\mapsto[0,1]\), which, in the network case, is the ratio of shared links between arms:\[P(Y_{t}=i|Y_{t-1}=j)=\frac{e^{\eta s(i,j)}}{\sum_{k\in\mathcal{K}}e^{\eta s(i,k)}}. \tag{26}\]  
It follows that the joint probability of arm \(i\) being selected at time step \(t\) and arm \(j\) being selected at time step \(t-1\) is given by:  
\[P(Y_{t}=i,Y_{t-1}=j)=P(Y_{t}=i|Y_{t-1}=j)P(Y_{t-1}=j). \tag{27}\]  
The probability of arm \(i\) being selected at time step \(t\) can be obtained by marginalizing over the distribution of the arms selected in the previous time step \(t-1\):  
\[P(Y_{t}=i)=\sum_{k\in\mathcal{K}}P(Y_{t}=i,Y_{t-1}=k). \tag{28}\]  
Finally, the probability mass function \(F_{Y_{t}}\) identifies promising arms (i.e., those correlated with the most-rewarded arms):  
\[F_{Y_{t}}(i)=P(Y_{t}=i),\forall i\in\mathcal{K}. \tag{29}\]