# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 6 Simulations
### Numerical Results  
The results of the simulations are presented in Figures 2 and 3, which illustrate the cumulative regret for the algorithms across multiple values of \(\sigma\) (reward standard deviation) and the number of rounds. The comparison includes MC-UCB, UCB, and \(\epsilon\)-Greedy with \(\epsilon=0.1\) and \(\epsilon=0.5\).  
In Figure 2, we observe that as the value of \(\sigma\) increases, the overall regret grows for all algorithms. However, the rate at which regret accumulates varies significantly across the algorithms. The MC-UCB algorithm consistently outperforms the baselines as it exhibits the lowest cumulative regret across all values of \(\sigma\).  
Figure 2: The simulation results for the specified settings under various values of \(\sigma\).  
Specifically, the following trends can be identified:  
* Effect of Increasing \(\sigma\): As the value of \(\sigma\) increases, the cumulative regret grows at a faster rate for all algorithms. This is expected because higher variability in rewards makes it more challenging to distinguish between the optimal and suboptimal arms. Nevertheless, MC-UCB demonstrates a robust ability to adapt to this increased variability and to maintain a clear performance advantage over the classical UCB and \(\epsilon\)-Greedy algorithms.
* Comparison with \(\epsilon\)-Greedy: The \(\epsilon\)-Greedy algorithms, with \(\epsilon=0.1\) and \(\epsilon=0.5\), perform consistently worse than MC-UCB. Notably, \(\epsilon=0.5\) results in lower regret compared to \(\epsilon=0.1\), as the excessive exploration prevents the algorithm from exploiting the optimal arms efficiently. This is especially prominent in settings with low \(\sigma\), where unnecessary exploration leads to regret accumulation.
* Performance of Classical UCB: The classical UCB algorithm achieves lower regret than the \(\epsilon\)-Greedy variants but fails to match the performance of MC-UCB. The classical UCB assumes \(\mathrm{id}\) rewards and does not account for the Markovian structure, which limits its ability to leverage state transitions effectively. This leads to slower learning of the optimal arms.
* MC-UCB's Adaptability: Across all settings of \(\sigma\), MC-UCB demonstrates superior performance, particularly as the number of rounds increases. MC-UCB achieves faster convergence to the optimal arms and maintains lower cumulative regret by leveraging the Markovian structure. This advantage becomes more pronounced at higher \(\sigma\) values, where the increased reward variability exacerbates the shortcomings of the baseline algorithms.  
Figure 3 provides a three-dimensional view of the total regret for each algorithm as a function of \(\sigma\) and the number of rounds. The plots reveal a clear trend: while all algorithms experience regret growth with increasing \(\sigma\), MC-UCB consistently maintains the smallest  
Figure 3: Full view of how the total regret changes under the different algorithms as the value of \(\sigma\) changes.  
regret surface. In contrast, the classical UCB and \(\epsilon\)-Greedy algorithms exhibit higher regret surfaces, with \(\epsilon\)-Greedy particularly struggling under larger \(\sigma\) values.