{'fraction_non_alphanumeric': 0.03801877324517386, 'fraction_numerical': 0.006907137375287797, 'mean_word_length': 4.367553865652725, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Restless Multi-Armed Bandits under Exogenous Global Markov Process

We consider an extension to the restless multi-armed bandit (RMAB) problem with unknown arm dynamics, where an unknown exogenous global Markov process governs the rewards distribution of each arm. Under each global state, the rewards process of each arm evolves according to an unknown Markovian rule, which is non-identical among different arms. At each time, a player chooses an arm out of N arms to play, and receives a random reward from a finite set of reward states. The arms are restless, that is, their local state evolves regardless of the player's actions. The objective is an arm-selection policy that minimizes the regret, defined as the reward loss with respect to a player that knows the dynamics of the problem, and plays at each time t the arm that maximizes the expected immediate value. We develop the Learning under Exogenous Markov Process (LEMP) algorithm, that achieves a logarithmic regret order with time, and a finite-sample bound on the regret is established. Simulation results support the theoretical study and demonstrate strong performances of LEMP.


I. INTRODUCTION
The multi-armed bandit (MAB) problem is a popular model for sequential decision making with unknown information: a player chooses actions repeatedly among N different arms. After each action it receives a random reward having an unknown probability distribution that depends on the chosen arm. The objective is to maximize the expected total reward over a finite horizon of T periods. Restless multi-armed bandit (RMAB) problems are generalizations of the MAB problem. Differing from the classic MAB, where the states of passive arms remain frozen, in the RMAB setting, the state of each arm (active or passive) can change. In this paper we consider an extension to the RMAB problem, in which we assume that an exogenous (global) Markov process governs the distribution of the restless arms, and thus the reward depends on both the state of the global process, and the local state of the chosen (active) arm.
This model captures a common application of dynamic spectrum access, where a network consists of a wideband primary user and a narrow-band secondary user. The exogenous Markov process models the presence/absence of the primary user in the wide-band frequency (e.g., the Gilbert-Elliott model [1]), and the dynamics of the This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
This work has been accepted to IEEE ICASSP 2022. arms captures the quality of the different narrow-band frequencies.
As commonly adopted in RMAB problems, the objective is to select the arm that has the highest immediate expected value at each time slot under unknown arm dynamics [2]- [4]. In this paper, the value function (and thus the arm selection) depends on both the mean reward of the arms and the transition probabilities of the global Markov process. We define the regret as the reward loss of an algorithm with respect to a genie that knows the transition probabilities of the global process and the expected rewards of the local arms. Due to the exogenous process, each global state is associated with different "best" arm (i.e., the arm that maximizes the expected value given the current global state). Thus, we note that the regret is not defined with respect to the best arm on average, but with respect to a strategy tracking the best arm at each step, which is stronger.

A. Main Results
Due to the restless nature of both active and passive arms, learning the Markovian reward statistics requires that arms will be played in a consecutive manner for a period of time (i.e., epoch) [5]- [7]. We thus divide the time horizon into separated exploration and exploitation phases. The goal of the exploration phase is to identify the best arm for each global state before entering the exploitation epoch. It is well known that UCB policies used to identifying the best arm require parameter tuning depending on the unobserved hardness of the task [8]. In the classic MAB formulation, the hardness of the task is characterized by where µ * , µ i are the means of the best arm and arm i, respectively. As shown in [8], the hardness parameter is indeed characteristic of the hardness of the problem, in the sense that it determines the order of magnitude of the sample complexity required to find the best arm with a required probability. However, since the hardness parameter is unknown, existing algorithms use an upper bound on max i H i (e.g., [5]), which increases the order of magnitude of exploration epochs, and consequently the regret.
Our main results are summarized next. First, we develop a novel algorithm, dubbed Learning under Exogenous Markov Process (LEMP), that estimates online the appropriate hardness parameter from past observations (Sec. III-A), resulting in adaptive sizes of exploration epochs, designed to explore each arm in each global state with the appropriate number of samples. Thus, LEMP avoids oversampling bad arms, and at the same arXiv:2202.13665v1 [cs.LG] 28 Feb 2022 time identifies the best arms with sufficient high probability. To ensure the consistency of the restless arms' mean estimation, LEMP performs regenerative sampling cycles (Sec. III-B). In the exploitation epochs, LEMP dynamically chooses the best estimated arm, based on the evaluation of the global state (Sec.III-C). Interestingly, the size of the exploitation epochs is deterministic and the size of the exploration epochs is random. The rules that decide when to enter each epoch are adaptive in the sense that they are updated dynamically and controlled by the current sample means and the estimated global transition probabilities in a closed-loop manner (Sec. III-D). Second, we provide a rigorous theoretical analysis of LEMP. Specifically, we establish a finite sample upper bound on the regret, and show that its order is logarithmic with time. We also characterize the appropriate hardness parameter for our model (the D i parameter defined in (3)), and we demonstrate that estimating the hardness parameter indeed results in a scaled regret proportional to the hardness of the problem. The result in Theorem 1 also clarifies the impact of different system parameters (rewards, mean hitting times of the states, eigenvalues of the transition probability matrices, etc.) on the regret. Finally, we provide numerical simulations that support the theoretical results.

B. Related Work
The extended RMAB model considered here is a generalization of the classic MAB problem [9]- [13]. RMAB problems have been studied under both the non-Bayesian [5]- [7], [14]- [18], and Bayesian [19]- [21], [22]- [28] settings. Under the non-Bayesian setting, special cases of Markovian dynamics have been studied in [6], [14], [16]. There are a number of studies that focused on special classes of RMABs. In particular, the optimality of the myopic policy was shown under positively correlated twostate Markovian arms [22]- [24], [29] under the model where a player receives a unit reward for each arm that was observed in a good state. In [25], [30], the indexability of a special classes of RMAB has been established. It is also related to models of partially observed Markov decision process (POMDP) [31], [32], with the goal of balancing between increasing the immediate reward and the benefits of improving the learning accuracy of the unknown states. Other related studies can be found in [33], [34].
The setting in this paper is also related to the nonstationary bandit problems, where distributions of rewards may change in time [3], [35]- [37]. However, the distribution that governs the non-stationary models in these studies differs from our settings, and leads to a different problem structure. Finally, [38], [39] and recently [40] considered the setting of global Markov process that governs the reward distribution. However, they addressed the linear/affine model, which is different from the RMAB formulation in this paper.

II. SYSTEM MODEL AND PROBLEM FORMULATION
We consider a set of N arms, indexed by {1, . . . , N } N , and a global system state process (s t ) t=1,2,... , which is a finite space, irreducible, and aperiodic discrete time S Markov chain with unknown transition matrix P S . We denote the transition probability between statess andš in S by psš, and we denote by π s the stationary distribution of states s ∈ S. For each global state s ∈ S, the i th arm is modeled as a finite space, irreducible, and aperiodic discrete time X i s Markov chain with unknown transition matrix P X i s . We assume that X ĩ s X ǐ s = ∅ for all i,s,š (i.e., we can recover the global state in each time slot). We also define the stationary distribution of state x in arm i at global state s to be π i s (x). At each time, the player chooses one arm to play. Each arm, when played, offers a certain positive reward that defines the current state of the arm, x i st . The player receives the reward of the chosen arm, and infers the current global state s t . Then, the global state transitions to a new state, which is unknown to the player before choosing the next arm to play. We assume that the arms are mutually independent and restless, i.e., the local states of the arms continue to evolve regardless of the player's actions according to the unknown Markovian rule P X i s . The unknown stationary reward mean of arm i at global state s, µ i s , is given by: We further define the expected value of arm i in global state s to be V i s š∈S Let i * t be the arm with the highest expected value at time t, i.e., i * t arg max i V i st , and let φ(t) ∈ {1, 2, ..., N } be a selection rule indicating which arm is chosen to be played at time t, which is a mapping from the observed history of the process to N . The expected regret of policy φ is defined as: (2) The objective is to find a policy that minimizes the growth rate of the regret with time (this notion of regret is similar to the "regret against arbitrary strategies" introduced in Section 8 of [2] and in [3] for the non-stochastic bandit problem). We note that, in this paper, the regret is not defined with respect to the best arm on average, but with respect to the best arm at each step according to the global state, which is a stronger regret.

III. THE LEARNING UNDER EXOGENOUS MARKOV
PROCESS (LEMP) ALGORITHM The LEMP algorithm divides the time horizon into exploration and exploitation phases. The strategy estimates the required exploration rate of each arm, and updates the arm selection dynamically with time, controlled by the random sample means and transition probabilities estimation in a closed loop manner.

A. Design Principles of LEMP
In order to ensure sufficient small regret in exploitation epochs (i.e., to reduce the probability for choosing suboptimal arms in exploitation), we should take a sufficiently large number of samples in the exploration epochs. From (1) we observe that we should estimate accurately two terms: the mean reward of each arm i in each global state s, µ i s , and the transition probabilities of the global Markov chain S, pšs.
In the analysis, we show that in each global state s, we must explore a suboptimal arm i with a local exploration rate of at least D i s log(t) times for being able to distinguishing it from i * s (i.e., the arm that maximizes the expeted value in state s) with a sufficiently high accuracy, where where V * s max i V i s , and L is constants that depends on the system parameters, defined in (11). The D i s parameter is a type of hardness parameter [8], appropriate for the setting considered in this paper, in the sense that it determines the order of magnitude of the sample size required to find the best arm in each global state with a required probability.
We point out that in order to derive D i s we should know {p sš } , µ ǐ s . Since the reward means and the transition probabilities are unknown, we estimate D i s by replacing µ i s , p sš by their estimators: where t i s (n) is the time index of the n th play on arm i in global state s in sub-block SB2 only (SB2 is detailed in Sec. III-B), T i s (t) is the number of samples from arm i in global state s in sub-block SB2 up to time t, N s (t) is the number of occurrences of the state s until time t, and Nsš(t) is the number of transitions froms toš up to time t. We also define: Denote the estimator of D i s by: where: V * s (t) max iV i s (t), and > 0 is a fixed tuning parameter.
Using {D i s (t)}, which are updated dynamically during time and controlled by the corresponding estimators, we can design an adaptive arm selection for sampling arm i at state s that will converge to its exploration rate, required for efficient learning, as time increases. Whether we succeed to obtain a logarithmic regret order depends on how fastD i s (t) converges to a value which is no smaller than D i s (so that we take at least D i s samples from bad arms in most of the times). B. The structure of exploration epochs: Due to the restless nature of both active and passive arms, learning the Markovian reward statistics requires that arms will be played in a consecutive manner for a period of time (i.e., epoch). Therefore, the exploration epochs are divided into sub-blocks SB1 and SB2. Consider time t (and we remove the time index t for convenience). We

D. Choosing between epoch types:
At the beginning of each epoch, the player needs to decide whether to enter an exploration epoch for one of the N arms, or whether to enter an exploitation epoch. We recall that the purpose of the exploration epochs is to estimate both the expected rewards of the arms, and the transition probabilities of the global process. We therefore define: The decision to explore or exploit will be made due to the next two conditions: First, if there exists an arm i and a global state s such that the following condition holds: then the player enters an exploration epoch for arm i. Second, if there exists a global state s ∈ S where Theorem 1. Assume that LEMP is implemented and the assumptions on the system model described in Section II hold, and an upper bound on ∆ in known. Let λ i s be the second largest eigenvalue of P X i s , and let M s,i x,y be the mean hitting time of state y starting at initial state x for arm i in global state s. Define x max max s∈S,i∈N x i s , |X max | max s∈S,i∈N |X i s | , π min min s∈S,i∈N ,x∈X i s π i s (x), π max max s∈S,i∈N ,x∈X i Then, the expected regret at time t is upper bounded by: , and K s is defined as the set of all indices i ∈ {2, ..., N } in global state s that satisfy: The proof separates the regret of the exploration rounds from that of the exploitation rounds. It can be found in the extended version of this paper [41].
We next analyze the regret numerically. In Fig. 2 we simulated LEMP for |S| = 2,N = 3. The global state models the presence of the primary user that uses the entire bandwidth by a Gilbert-Eliot model [1] that comprises a Markov chain with two binary states, where global state s = 1 denotes a transmitting primary user and s = 0 denotes a vacant channel, i.e., inactive primary user. To limit the interference to the primary user, a secondary user may choose to transmit over one of three possible channels (i.e., N = 3), where the channels are modeled by a Finite-State Markovian Channel (FSMC) [42]. We compared the LEMP algorithm to an extended version of the DSEE algorithm [5], and to an algorithm that chooses in the exploitation epochs the best arm on average. The DSEE algorithm uses deterministic sequencing of exploration and exploitation epochs, however, it does not estimate the hardness parameter, and explores each arm ∆ · log(t) times, which results in oversampling bad arms, to achieve the desired logarithmic regret. It can be seen that LEMP significantly outperforms the extended DSEE algorithm. Fig. 2 also shows the superior of LEMP against a strategy that chooses the best arm on average, demonstrating the gain in tracking the best arm at each step according to the global process evolution. The full parameter setting and more extensive simulation results can be found in the extended version of this paper [41].

V. CONCLUSION
We developed a novel Learning under Exogenous Markov Process (LEMP) algorithm for an extended version of the RMAB problem, where an exogenous Markov global process governs the distribution of the arms. Inspired by recent developments of sequencing methods of exploration and exploitation epochs, LEMP estimates the hardness parameter of the problem which controls the size of exploration epochs. During the exploitation epochs, LEMP switches arms dynamically according to the global process evolution. Simulation results support the theoretical analysis, and shows superior performances of LEMP against competitive strategies.