# Modified Index Policies for Multi-Armed Bandits with Network-like Markovian Dependencies
## 1 Introduction  
Decision-making in environments with network-like dependencies presents a fundamental challenge across various fields, including communication networks, finance, and complex distributed systems [1, 2, 3, 4]. In such environments, a decision-maker faces interconnected structures where actions taken on one element may influence the states or rewards of others, thereby creating dynamic dependencies reminiscent of those found in networked systems. Examples of such networks can be found in resource allocation across multiple communication channels in IoT (Internet of Things) sensor networks [5], throughput optimization in distributed blockchain ecosystems [6], adaptive QoS (Quality of Service) management in communication networks [7], and security or intrusion detection frameworks in large-scale system administration scenarios [8]. In these contexts, the multi-armed bandit (MAB) problem, where a player repeatedly selects among multiple uncertain options (arms), becomes more intricate due to underlying and often hidden state transitions that evolve over time. The original classical MAB formulation, introduced by [PERSON] [9; 10], assumes that each arm's reward distribution remains fixed and independent over time. However, in networked scenarios, these assumptions rarely hold: the reward distributions may shift due to underlying Markovian state transitions that are hidden from the decision-maker [11]. Arms in such a scenario can represent network nodes, communication links, or distributed resources whose performance and reliability evolve with time. The agent must continually learn and adapt, taking into account latent transitions that are reminiscent of evolving network conditions. In this paper, we lay a theoretical framework for a modified MAB model in which each arm's reward is generated by a hidden Markov process. This approach models the type of network-like dependencies found, for example, in dynamic IoT sensor networks--where channel conditions and sensor states change stochastically and are not directly observable, yet these state changes critically affect the rewards (e.g., reliable data transmission or efficient resource utilization). Each arm in our model can transition among up to three states, each associated with a different reward distribution, regardless of whether the arm is played. The result is a problem setting that demands sophisticated exploration-exploitation strategies that identify the best arms under evolving conditions and also cope with underlying dynamics that reflect network interdependencies. In this context, we evaluate the decision-maker's performance using the concept of regret, a metric that captures the cost of uncertainty in networked decision-making environments. Regret is defined as the difference between the expected reward an ideal policy--one with complete knowledge of all arm statistics or hindsight advantage--would achieve, and the reward achieved by the decision-maker's actual strategy. An ideal policy would consistently select the arm yielding the highest expected reward over time. This concept, commonly referred to as weak regret, is a central performance measure in uncertain decision problems, as highlighted by [PERSON] et al. [12]. Our study focuses on regret, particularly within interconnected, network-like settings. MAB problems with Markovian rewards significantly heighten complexity due to dynamic dependencies that reflect networked interactions. Here, each arm is modeled as a Markov process with a finite set of states, each linked to a unique reward distribution. The transition between states follows a known probability matrix, introducing a memory element into the decision process where rewards depend not only on the current choice but also on the hidden state of each arm [13; 14; 15; 16]. This Markovian structure effectively simulates a network in which states and rewards are dynamically interdependent over time. The state transitions are determined by predefined probabilities, yet the exact state of each arm remains hidden.