# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 4 Problem Formulation
Let \(B_{k}\) be the \(k\)th \"block\" of the chain:  
\[B_{k}=(X_{\tau_{k-1}+1},X_{\tau_{k-1}+2},\ldots,X_{\tau_{k}-1}).\]  
By the regenerative property of Markov chains, the blocks \(B_{k}\) are iid. The expected number of visits to \(x\) in a typical block is \(E[N(x,B_{1})]=\phi_{x}E[l(B_{1})]\), where \(l(B_{1})\) is the length of the block \(B_{1}\). Define \(T\) as the first return time to \(X_{1}\) after time \(\tau\):  
\[T=\min\{t>\tau\mid X_{t}=X_{1}\}=\tau_{\kappa}\]  
for some \(\kappa\). Note that \(T-\tau\) is also finite in expectation due to irreducibility. Applying Wald's identity,\[E\Big{[}\sum_{t=1}^{T-1}I(X_{t}=x)\Big{]}=E[\kappa]E[N(x,B_{1})]=\phi_{x}E[l(B_{1}) ]E[\kappa].\]  
Similarly,  
\[E(T-1)=E[\kappa]E[l(B_{1})].\]  
Because \(E(T-\tau)\leq D(P)\) for some constant \(D(P)\), we have for any \(x\in S\)  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]0 \[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]1 \[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]2 \[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]3  
Thus, we have shown the stated bound, completing the proof. Next, we relate the regret \(R^{\alpha}(n)\) to \(E^{\alpha}[M^{\alpha,i}(n)]\), the expected count of plays of each arm \(i\) up to time \(n\). Lemma 2: _Under the conditions of Lemma 1, consider any strategy \(\alpha\) that ensures the average time between successive pulls of any given arm remains bounded. Then, there exists a constant \(D(\mathcal{X},\mathcal{P},\mathcal{R})\)--depending on the sets \(\{\mathcal{X}^{(i)}\}\), the probability matrices \(\{P^{(i)}\}\), and the reward structures \(\{r_{u}^{(i)}\}\)--such that_  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]4  
Proof of Lemma 2: For each arm \(i\), let \(H^{i}=\bigvee_{j\
eq i}F^{(j)}\) be the \(\sigma\)-algebra generated by the observations of all arms except arm \(i\). Since the arms are independent, \(H^{i}\) is independent of \(F^{(i)}\), the filtration associated with arm \(i\). Note that \(M^{\alpha,i}(n)\) is a stopping time with respect to \(\{H^{i}\lor F_{t}^{(i)}:t\geq 1\}\). Denote by \(\{X^{(i)}(1),X^{(i)}(2),\ldots,X^{(i)}(M^{\alpha,i}(n))\}\) the sequence of states visited by arm \(i\) within the first \(n\) steps of the policy \(\alpha\). The total collected reward up to time \(n\) is  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]5  
By definition of regret,  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]6  
Rewriting and employing linearity of expectation,  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]7 \[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]8 \[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]9Since \(|E[N(v,M^{a,i}(n))]-\phi_{v}^{(i)}E^{a}[M^{a,i}(n)]|\leq D(P^{(i)})\) by Lemma 1 (applied to each arm's Markov chain), we have  
\[N(x,\tau)=\sum_{t=1}^{\tau}I(X_{t}=x).\]0  
This upper bound depends on all the arms' state spaces, transition laws, and reward distributions. We thus denote this cumulative constant by \(D(\mathcal{X},\mathcal{P},\mathcal{R})\), concluding the proof. In essence, Lemma 2 states that the regret of any policy can be bounded by a term that sums, over all arms, the product of their respective expected selection counts and their suboptimality gap \((v^{\star}-v^{i})\), plus a constant. This insight lays the groundwork for subsequent analysis and the development of regret-minimizing strategies.