# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 6 Simulations
### Additional Markovian Network Scenario and Results  
To further illustrate the flexibility of MC-UCB under a Markovian reward structure, we also conduct a complementary numerical experiment wherein the arms represent network links transitioning among three distinct quality states (High, Medium, and Low). The rewards are interpreted as throughput (in Mbps), reflecting the link's capacity at each time step. Unlike the fully randomized approach in the previous settings, here we fix the transition matrices and reward means (sampled from the dataset [44]) to highlight how variability in observation noise (i.e., the standard deviation \(\sigma\)) impacts each algorithm's performance.  
We consider a simple network setting that translates to \(K=3\) arms, each with a three-state Markov chain. The probability of remaining in or transitioning between these states is encoded by a fixed transition matrix \(P^{(i)}\) for each arm \(i\in\{1,2,3\}\). For example, an arm in a High state remains there with probability 0.80, transitions to Medium with probability 0.15, and drops to Low with probability 0.05. We interpret the per-round reward \(r_{t}^{(i)}\) as a throughput measurement drawn from a Gaussian distribution with mean \(\mu_{u}^{(i)}\) (the average throughput for state \(u\) of arm \(i\)) and variance \(\sigma^{2}\). Thus, higher reward corresponds to higher link throughput. We vary the standard deviation \(\sigma\in\{2.0,\,3.0,\,4.0\}\) to simulate increasingly fluctuating network conditions.  
We employ the same core policy classes introduced previously, with the key difference being that we now deal with throughput (Mbps) as reward:  
1. MC-UCB: Our proposed Markovian UCB policy that can exploit knowledge of the transition probabilities.
2. Classical UCB: A reference baseline assuming iid rewards.
3. Baseline-Greedy: A purely greedy strategy, always picking the arm with the highest observed average so far.  
We set the horizon to \(T=10,\!000\) rounds. At each round, the selected arm yields a random throughput sample from \(\mathcal{N}(\mu_{u}^{(i)},\sigma^{2})\) for its current state \(u\), and all arms then transition. Our performance metric is the time-averaged throughput achieved by each policy, since throughput is a key measure of network performance.  
For each fixed \(\sigma\), we run three numerical evaluations on the network simulations (one for each policy) and compute the running average throughput over time. We then plot the final average-throughput curves for each policy. The transition matrices, state means, and values of \(\sigma\) remain consistent in all runs to isolate the effect of observation noise (reward variability).  
Figure 4 illustrates the key results for each \(\sigma\). The results clearly demonstrate the consistent superiority of the MC-UCB algorithm across all tested noise levels (\(\sigma\)). For \(\sigma=2.0\), MC-UCB quickly stabilizes around 6 Mbps, outperforming both classical UCB and Baseline-Greedy, which exhibit slower convergence and slightly lower steady-state  
throughput. As the noise level increases to \(\sigma=3.0\), MC-UCB maintains a noticeable advantage, achieving higher initial throughput and stabilizing at a value above 6 Mbps, whereas the other algorithms lag behind, converging closer to 5.5 Mbps. Even under the highest noise level, \(\sigma=4.0\), MC-UCB continues to outperform its counterparts, demonstrating faster convergence and sustaining higher throughput near 6 Mbps, while classical UCB and Baseline-Greedy fall short. These results highlight the robustness and adaptability of MC-UCB, making it the most effective approach in scenarios with varying noise conditions.