# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 4 Problem Formulation  
We consider a scenario comprising \(K\) distinct arms, each labeled by an index \(i\in\{1,2,\ldots,K\}\). Each arm \(i\) is represented as an irreducible Markov chain with a finite state space denoted by \(\mathcal{X}^{(i)}\). The transition kernel of arm \(i\) is known and is described by a probability matrix \(P^{(i)}=\{p_{u}^{(i)}:u,v\in\mathcal{X}^{(i)}\}\). Every state \(u\) of arm \(i\) yields a stationary and strictly positive reward \(r_{u}^{(i)}\). We assume that the \(K\) Markov chains (one per arm) are mutually independent. Let \(\phi^{(i)}=\{\phi_{u}^{(i)}:u\in\mathcal{X}^{(i)}\}\) be the stationary distribution of the \(i\)th arm. The mean reward of arm \(i\), denoted by \(v^{i}\), can then be expressed as  
\[v^{i}=\sum_{u\in\mathcal{X}^{(i)}}r_{u}^{(i)}\phi_{u}^{(i)} \tag{1}\]  
The arm with the largest mean reward is indicated by a superscript \(\star\), so that \(v^{\star}=\max_{1\leq i\leq K}v^{i}\). We define the regret of a policy \(\alpha\) after \(n\) steps, \(R^{\alpha}(n)\), as the difference between the expected cumulative reward that would be obtained by always selecting the best arm and the actual expected cumulative reward gathered under policy \(\alpha\). If \(\alpha(t)\) denotes the arm chosen by \(\alpha\) at time \(t\) and \(x_{\alpha(t)}\) the state visited by that arm at time \(t\), we have  
\[R^{\alpha}(n)=nv^{\star}-E^{\alpha}\left[\sum_{t=1}^{n}r_{x_{\alpha(t)}}^{( \alpha(t))}\right] \tag{2}\]  
In principle, if one always knew which arm has the highest mean reward, playing that arm indefinitely would constitute the optimal single-arm selection strategy. Nonetheless, this does not necessarily identify the best policy among all possible stationary and non-stationary policies if the entire statistical structure of the arms were fully known. In the broader scenario over an infinite horizon, the optimal policy is characterized by the Gittins index, as introduced by [PERSON] [30]. If each arm's rewards were iid, then the optimal solution over all admissible policies would simply be to consistently choose the best single-action arm. In our work here, we limit our comparison of performance to this single-action benchmark. To investigate policies that minimize regret, we employ a series of preliminary results to relate the regret \(R^{\alpha}(n)\) to the expected number of times suboptimal arms are played. For a given policy \(\alpha\), let \(M^{\alpha,i}(t)\) represent the total number of times arm \(i\) is pulled up to time \(t\). Understanding the connection between regret and \(E^{\alpha}[M^{\alpha,i}(n)]\) proves critical. We invoke the following lemma to establish a key relationship. We adapt and modify its proof here for completeness:  
**Lemma 1** (Adapted from Lemma 2.1 in [29]). : _Consider a Markov chain \(Y\) that is irreducible, aperiodic, and has a finite state space \(S\). Its transitions are governed by a probability matrix \(P\), and it begins with an initial distribution in which all states have strictly positive probability. Let \(F_{t}\) be the \(\sigma\)-algebra generated by the sequence of states \(X_{1},X_{2},\ldots,X_{t}\), where \(X_{t}\) is the state at time \(t\). Suppose \(G\) is a \(\sigma\)-algebra independent of \(F=\vee_{t\geq 1}F_{t}\). Consider a stopping time \(\tau\) with respect to the sequence of \(\sigma\)-algebras \(\{G\lor F_{t}:t\geq 1\}\). Define the visitation count of a particular state \(x\in S\) up to time \(\tau\) by_  
\[N(x,\tau)=\sum_{t=1}^{\tau}I(X_{t}=x).\]  
_If \(E[\tau]\) is finite, then there exists a constant \(D(P)\) (depending solely on \(P\)) such that_  
\[D(P)\geq\left|\phi_{x}E[\tau]-E[N(x,\tau)]\right| \tag{3}\]  
_where \(\phi=\{\phi_{x}:x\in S\}\) is the stationary distribution of the chain._  
Proof of Lemma 1.: Consider the sequence of regeneration times \(\{\tau_{k}:k\geq 0\}\) defined by  
\[\tau_{0} =0,\] \[\tau_{k} =\min\{t>\tau_{k-1}\mid X_{t}=X_{1}\},\quad\forall k\in\mathbb{N}\]  
Given the chain's irreducibility, we assert that \(\tau_{k}<\infty\) for every \(k\).