# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 5 A Solution to the Problem with Bounded Regret
4:while\(t\leq T\)do
5:for each arm \(i\in\{1,2,\ldots,K\}\)do
6: Calculate \(\tilde{r}^{(i)}(M^{i}(t))=\frac{r^{(i)}(1)+r^{(i)}(2)+\ldots+r^{(i)}(M^{i}(t)) }{M^{i}(t)}\). 7: Select arm \(a_{t}=\arg\max_{i}\{\tilde{r}^{(i)}(M^{i}(t))+\sqrt{\frac{\alpha\ln t}{M^{i}(t) }}\}\). 8:\(t\gets t+1\). 9:return\(\{a_{1},a_{2},\ldots,a_{T}\}\). ```  
**Algorithm 1** Markovian UCB (MC-UCB)  
**Lemma 3** (Based on Theorem 2.1 in [43]). : _Consider a reversible, irreducible, aperiodic Markov chain with a finite state space \(\mathcal{X}\) and transition matrix \(P\). Let \(\mathbf{q}\) be an initial distribution, and define \(N_{\mathbf{q}}=\big{\|}(q_{x}/\phi_{x},x\in\mathcal{X})\big{\|}_{2}\). Let \(\lambda_{2}\) be the second largest eigenvalue of \(P\) and define \(\epsilon=1-\lambda_{2}\). For a subset of states \(W\subseteq\mathcal{X}\), define \(\phi_{W}=\sum_{x\in W}\phi_{x}\) and let \(t_{W}(n)\) be the count of visits to \(W\) up to time \(n\). Then, for any \(\beta\geq 0\),_  
\[P\big{(}t_{W}(n)-n\phi_{W}\geq\beta\big{)}\leq(1+\beta\epsilon/(10n))N_{ \mathbf{q}}e^{\left(-\frac{\beta_{\epsilon}^{2}\epsilon}{2n}\right)}. \tag{5}\]  
**Proof of Lemma 3. ** The proof can be directly derived from Theorem 2.1 in [43]. We now proceed to the main theorem for our policy. The proof utilizes techniques analogous to those in [32] to derive logarithmic regret bounds for the MC-UCB policy. **Theorem 1**. : _Consider \(K\) arms, each arm \(i\) being modeled as a finite-state, irreducible, aperiodic, and reversible Markov chain with a state space \(\mathcal{X}^{(i)}\). All rewards \(r_{x}^{i}\) are strictly positive. Let_  
\[\phi_{\min}=\min_{1\leq i\leq K,x\in\mathcal{X}^{(i)}}\phi_{x}^{i},\quad r_{ \max}=\max_{1\leq i\leq K,x\in\mathcal{X}^{(i)}}r_{x}^{i},\quad r_{\min}=\min_{ 1\leq i\leq K,x\in\mathcal{X}^{(i)}}r_{x}^{i},\]  
\[X_{\max}=\max_{1\leq i\leq K}|\mathcal{X}^{(i)}|,\quad\epsilon_{\max}=\max_{1 \leq i\leq K}\epsilon^{i},\quad\epsilon_{\min}=\min_{1\leq i\leq K}\epsilon^{ i}.\]_Define the constant \(\alpha\geq 100X_{\max}^{2}r_{\max}^{2}/\epsilon_{\min}\). Then, the upper bound on the regret \(R(n)\) of the UCB policy is_  
\[R(n) \leq 5\alpha\sum_{ix^{i}<v^{*}}\frac{\ln n}{v^{*}-v^{i}}\ +\ \sum_{ix^{i}<v^{*}}(v^{*}-v^{i})\,C^{i}\] \[\qquad+\ D(\mathcal{S},\mathcal{P},\mathcal{R})\] (6) _where_ \[C^{i} =(D^{i}+D^{*})\,\beta+1,\] \[D^{i} =\frac{|\mathcal{X}^{(i)}|}{\phi_{\min}}\bigg{(}1+\frac{\epsilon _{\max}\sqrt{\alpha}}{12|\mathcal{X}^{(i)}|r_{\min}}\bigg{)},\] \[\beta =\sum_{t=1}^{\infty}\frac{1}{t^{2}}=\pi^{2}/6.\]  
Proof of Theorem 1.: We analyze the performance of the UCB strategy with a parameter \(\beta\) dictating the magnitude of the confidence intervals. Unless noted otherwise, the notation omits superscripts related to the policy for brevity. For each arm \(i\), let \(\overline{r}^{i}(M^{i}(n))\) denote the empirical mean reward after \(M^{i}(n)\) plays. Define  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]0  
to represent the confidence width. Let \(m\) be a positive integer.