# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 5 A Solution to the Problem with Bounded Regret  
In this section, we explore a sample-based index policy, which is a UCB-type policy, modified from the one introduced by [32]. This approach is adapted to our setting, where each arm evolves according to a Markovian state process. Algorithm 1 shows the policy, which we call the Markovian UCB (MC-UCB) policy. Let \(r^{(i)}(m)\) denote the \(m\)-th observed reward from arm \(i\) and \(M^{i}(n)\) the number of times arm \(i\) has been selected up to (and including) time \(n\). We define the empirical mean reward for arm \(i\) after \(n\) steps as  
\[\overline{r}^{(i)}(M^{i}(n))=\frac{r^{(i)}(1)+r^{(i)}(2)+\cdots+r^{(i)}(M^{i} (n))}{M^{i}(n)}.\]  
At each time step, the policy assigns an index to each arm. For arm \(i\) at step \(n\), this index is denoted by \(h^{(i)}_{n,M^{i}(n)}\). The arm chosen at time \(n\) is the one with the highest index. The index is computed as follows. Initially, each arm is played exactly once. Every time an arm is played, its empirical mean \(\overline{r}^{(i)}(\cdot)\) is updated and forms the first component of the index. For arms that are not played, the uncertainty regarding their true mean reward increases, captured by an exploration term added to the index. The resulting index at time \(n\) for arm \(i\) is of the form  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]  
where the constant \(\alpha\) is set to 2, similar to the standard UCB policy [32]. The proposed MC-UCB algorithm demonstrates favorable scalability with respect to both the number of arms \(K\) and the number of states per arm. At each time step, the algorithm performs a straightforward computation of the empirical mean reward for each arm, which can be efficiently maintained using incremental updating formulas. Specifically, instead of storing all past rewards, the algorithm only requires maintaining a running sum and count of rewards for each arm; thereby, it ensures constant time and space complexity per arm. Consequently, the overall computational complexity per round scales linearly with the number of arms, i.e., \(\mathcal{O}(K)\), which makes it highly efficient even as \(K\) grows. Moreover, since each arm is modeled with a finite and small number of states (up to three in our theoretical framework), the state transition management incurs minimal overhead. The known transition probabilities allow for precomputing stationary distributions, which can be utilized to optimize the index calculations without necessitating real-time state inference. This precomputation further reduces the computational burden during the decision-making process. However, it is important to acknowledge that extending the model to accommodate a significantly larger number of states or unknown transition probabilities would introduce additional complexity. Future work could explore approximate methods or hierarchical indexing strategies to mitigate potential inefficiencies in such scenarios. Nonetheless, within the current scope of three-state arms, the MC-UCB algorithm remains computationally tractable and well suited for possible applications that require rapid and scalable decision-making. Below, we will show that the expected regret of this index policy grows at most on the order of \(\ln(n)\). To establish this, we will upper-bound the expected frequency with which any suboptimal arm (those with mean reward smaller than \(\
u^{*}\)) is chosen. A crucial tool for this analysis is a lemma from [PERSON] [43], which provides a bound on the probability that the empirical frequency of visits to a subset of states deviates significantly from its stationary distribution. ```
0: Number of arms \(K\), horizon \(T\), and known transition kernels \(\{p_{uv}^{(i)}:u,v\in\mathcal{X}^{(i)}\) for each \(i\}\). 0: Sequence of selected arms \(\{a_{1},a_{2},\ldots,a_{T}\}\). Initialization:\(t\gets 1\). 1:while\(t\leq K\)do
2: Select arm \(a_{t}=t\). 3:\(t\gets t+1\).