# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 2 Related Work  
The literature on the MAB problem is vast and has evolved considerably from the original formulations focusing on independent and identically distributed (iid) reward processes. Early seminal work by [PERSON] and [PERSON] [9; 10] established foundations for the iid case for certain known environments. Over time, researchers have explored a broad spectrum of MAB extensions that incorporate various forms of structure and dynamics. Notably, Markovian reward processes represent a key generalization and enable the modeling of scenarios where arm states--and thus rewards--evolve with memory and dependence on previous states. Early explorations into Markovian bandits can be found in the work of [PERSON] et al. [29], which analyzed index policies effective for arms governed by irreducible, finite-state, aperiodic Markov chains. Their approach demonstrated how arms with state-dependent rewards could still be tackled through index strategies that generalize the Gittins index concept [30]. While these studies set important precedents for handling Markovian structures, they often made simplifying assumptions, such as a single-parameter transition function or identical state spaces across arms. In contrast, our framework does not presume a single-parameter form for transition probabilities, nor does it require identical state spaces. By allowing each arm to transition among up to three states under distinct probability kernels, we offer a more flexible setting that can model diverse types of network dependencies. Building upon this foundation, research has examined the problem of achieving low regret under more general conditions. [PERSON] [31] and [PERSON] et al. [32] established classical logarithmic regret results for iid settings. Their contributions included index and UCB-based strategies that guarantee optimal asymptotic and even uniformly logarithmic performance over time. They rely heavily on the iid assumption and do not directly address the complexities introduced by state transitions or network-like interdependencies. More recent works have begun to relax these assumptions. For instance, [PERSON] and [PERSON] [33] and [PERSON] et al. [34] considered bandit problems with non-stationary reward distributions in a way that captures some aspects of temporal dynamics without fully embracing Markovian state dependence. Such approaches typically rely on \"resetting\" or \"sliding-window\" techniques that do not directly exploit known Markovian transition structures. In parallel, other authors have studied scenarios where multiple users or decision-makers interact with the same set of arms in network settings, leading to complex dynamics and collisions among players [35; 36; 37]. Here, the challenge lies in coordinating multiple agents to minimize interference and collectively achieve low regret. While such multi-playerframeworks mirror network complexity, their primary focus is on handling concurrency and competition rather than modeling state evolution within each arm. Our approach differs by focusing explicitly on Markovian transitions at the arm level rather than strategic interactions among multiple decision-makers. The distinction between rested and restless bandits further highlights the complexity in Markovian settings. In classical rested bandits, the state of an unplayed arm remains frozen until chosen again, as examined in works like those of [PERSON] [38] and [PERSON] and [PERSON] [39]. However, in restless bandits, arm states evolve regardless of selection, making the problem significantly more complex. The restless bandits formulation has explored structural results and approximation algorithms for special cases [11; 40]. Our framework takes a step forward by considering a setting in which all arms transition at every round, falling somewhere between the fully rested and fully restless extremes, and by establishing logarithmic regret bounds in this intermediate regime. Compared to the closely related studies such as [15; 29], our work introduces a novel solution. For instance, [PERSON] et al.