# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 5 A Solution to the Problem with Bounded Regret
The number of times arm \(i\) is selected up to time \(n\) is  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]1  
We bound this as follows:  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]2 \[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]3  
Define the event \(\delta^{i}(t,m)\) by the inequality  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]4  
and let \(\tilde{\varsigma}^{i}(t,m)\) correspond to  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]5  
Since \(\{\beta(t)=i,\,M^{i}(t-1)\geq m\}\) implies \(\delta^{i}(t,m)\), and \(\delta^{i}(t,m)\) implies \(\tilde{\varsigma}^{i}(t,m)\), we have  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]6  
Expanding over all indices, one can rewrite as follows:  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]7To have \(\bar{r}^{*}(s)+c_{t,s}\leq\bar{r}^{i}(s_{i})+c_{t,s_{i}}\), at least one of the following must hold:  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]8  
To prevent \(v^{*}<v^{i}+2c_{t,s_{i}}\) from holding, choose  
\[h^{(i)}_{n,M^{i}(n)}=\overline{r}^{(i)}(M^{i}(n))+\sqrt{\frac{\alpha\ln n}{M^ {i}(n)}}.\]9  
to ensure \(2c_{t,s_{i}}\leq v^{*}-v^{i}\). Let \(k=\big{\lceil}3\alpha\ln n/(v^{*}-v^{i})^{2}\big{\rceil}\). Consequently,  
\[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}\]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}\]1  
We now employ the Markov chain deviation bounds. For each arm \(i\), let \(\mathbf{q}^{i}\) be the initial distribution and  
\[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}\]2  
Since \(q^{i}_{y}>0\) and \(\phi^{i}_{x}\geq\phi_{\text{min}}\), we have \(N_{\mathbf{q}^{i}}\leq 1/\phi_{\text{min}}\) (using [PERSON]'s inequality). Thus, consider the probability  
\[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}\]3  
Rewriting this event in terms of state visits and leveraging the deviation bounds (analogously to Lemma 3's result but adapted here), we obtain  
\[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}\]4 \[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}\]5  
Summing over all suboptimal arms \(i\) such that \(v^{i}<v^{*}\),  
\[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}\]6  
Incorporating the additional constant term \(D(\mathcal{S},\mathcal{P},\mathcal{R})\) from Lemma 2, we finally establish  
\[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}\]7  
This proves the stated theorem. The obtained bound on \(R(n)\) is of order \(\ln n\), similar to known asymptotic results, but holds uniformly in \(n\). The constant factors, however, depend on various parameters, including the stationary distributions, the eigenvalue gaps \(e^{i}\), and the reward range. Proper selection of a sufficiently large \(\alpha\) (based on \(\epsilon_{\text{min}}\), \(X_{\text{max}}\), and \(r_{\text{max}}\)) makes our result stronger.