Olivier Brun

Nicolas Gast

Christine Fricker

Audrey Denis

Elise Gonza

Vir Jere Juan

Nico Ro

Fede, Lean, Pablo Harmonie Mati

Balta, el Guido

Ale, Gasti, Maxi Parce

Fela

Pablo Pepe

Mauro Gracias

Agus, Pablo, Emi Caro

Ernesto Quiero Agradecer Especialmente A María

I would like to express my deepest gratitude to my advisors Maaike and Urtzi. Their generosity and trust during my work were the most important help I could have received. Moreover, I always felt them by my side during these three and a half years, and they provided me with the tools and challenges needed to learn and grow. I also

Chapter 1 environment, whereas in the observable environment case, the decision maker observes the current state of the environment in order to choose actions. Under both settings, we are interested in deriving efficient control policies.

Another topic we address is the resource allocation in large-scale storage systems. We consider a model of storage systems, where there are files distributed across nodes, and the nodes break down following random times. When a breakdown occurs, the system allocates the files present in the broken node to other nodes at random, according to a particular allocation policy. Since exact analysis of the system seems out of reach, we study the performance as the number of nodes grows large.

Overview of research problems

We describe now the three problems we address in the thesis, each one of them corresponds to a chapter.

The results obtained in each problem are described in Section 1.3.

Control with unobservable environments

In Chapter 2, we study a large-scale resource allocation problem with controllable processes affected by unobservable environments. We assume that the decision maker takes actions when the controllable processes change state, and the available information is the current state of the controllable processes but not the state of the environments. Considering unobservable environments can be motivated from the fact that it might be too costly to observe the environment and/or change action each time the environment changes.

We focus on a Multi-Armed Restless Bandit Problem (MARBP), a specific subclass of MDPs in which there are a number of concurrent projects, known as bandits, that can be made active or passive. In Section 1.2.3 we provide more details on MARBP. The main goal is to find policies that minimise the average cost incurred by the bandits in a long-run criterion.

We do this in an asymptotic regime, where the number of bandits and the speed of the environments grow large. This regime is known as the mean-field limit. See Section 1.2.5 for an introduction to the mean-field theory. Among our main results, we propose a set of priority policies that is asymptotically optimal, and we describe an implementable policy that is inside this set. This policy is derived from an averaged version of Whittle's index as studied for the classical MARBP, see Section 1.2.4 for an introduction to Whittle's index.

We cite here related work where models on stochastic control with (partially) unobservable environments have been studied. In [START_REF] Budhiraja | Scheduling control for Markov-modulated single-server multiclass queueing systems in heavy traffic[END_REF], the authors study a multi-class single-server queueing network with arrival and service rates modulated by an unobservable environment. Note that in the multi-class single-server queue without environments the standard cµ rule is optimal. Under this rule, the served class is the one maximising the product c k µ k , where c k is the holding cost and µ -1 k is the mean service time of class-k customers [START_REF] Buyukkoc | The cµ rule revisited[END_REF][START_REF] George | Dynamic control of a queue with adjustable service rate[END_REF]. In the main result in [START_REF] Budhiraja | Scheduling control for Markov-modulated single-server multiclass queueing systems in heavy traffic[END_REF], it is shown that an "averaged" version of the classical cµ-rule is asymptotically optimal in the heavy-traffic regime. In [START_REF] Anselmi | Asymptotically optimal open-loop load balancing[END_REF], optimal load balancing is studied when the queue lengths of the servers are unobservable. A set of round-robin policies is proved to be optimal in a heavy-traffic many-server limiting regime. In [START_REF] Asanjarani | The role of information in system stability with partially observable servers[END_REF][START_REF] Nazarathy | The challenge of stabilizing control for queueing systems with unobservable server states[END_REF], the authors study optimal control in a multi-class queueing system where the servers' capacity varies according to a Markov-modulated random environment.

The environment can be partially observed for the activated server. As the control decision influences the observation made, the authors search for policies that achieve maximum stability.

Control with observable environments

In Chapter 3, we consider a control problem with environment processes that can be observed. Again, we focus on a Multi-Armed Restless Bandit problem, where each bandit is formed by two processes, a controllable process and an environment. The decision maker bases its decisions on the current state of the controllable processes and the current state of the environments. Whenever any of the processes changes state, the action can be changed as well. These problems arise naturally when there is an exogenous phenomenon that can be observed but cannot be controlled. For example in the context of wireless communications, the available download rate depends on weather conditions, and in cloud computing systems the arrival rates of new jobs fluctuate according to the time of the day.

For the approach of the problem, we provide an algorithm that computes Whittle's index, which gives rise to Whittle's index policy. We are able to obtain an analytical characterisation of the index in the concrete example of a multi-class abandonment queue: the queues are the controllable processes that may be served or not, and their transition rates depend on an exogenous environment. More details on our contributions are provided in Section 1.3.

Optimal control with observable environments has been studied in [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Anand | A Whittle's index based approach for QoE optimization in wireless networks[END_REF][START_REF] Gast | A mean field approach for optimization in discrete time[END_REF]. In [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Anand | A Whittle's index based approach for QoE optimization in wireless networks[END_REF], the problem of scheduling tasks in a wireless setting is modelled through MARBPs with an observable environment. The controllable process is the remaining service time of tasks -which is a decreasing process-, and the environment is given by the capacity of the channel -which fluctuates over time in an uncontrollable manner-. Both previous references consider that the environments across processes are independent. In [START_REF] Gast | A mean field approach for optimization in discrete time[END_REF] the authors consider an MDP in a mean-field regime, with independent processes evolving in a common environment.

It is shown that as the number of processes tends to infinity, the optimal policy converges to the optimal policy of a deterministic discrete time system.

Performance analysis for large-scale storage systems

In Chapter 4, we address an allocation problem in large storage systems using a stochastic modelling approach. We consider a model where there are files distributed across a set of nodes, and each node breaks down after an exponentially distributed amount of time that depends on the number of files it handles.

When a node breaks down, all the files it had are reallocated to other nodes, and the node goes back to a state with zero files. The destination node of the files is chosen at random and independently across the files.

Since the model with a fixed number of nodes involves a complex analysis, we focus on the mean-field regime, as we did in Chapter 2. We take the total number of nodes and the total number of files to infinity, with a fixed average number of files per node. We study the existence of the process that represents the load of a single node in the mean-field limit. We further consider the case where the average number of files per node tends to infinity, and we show the convergence in distribution of the load in steady state.

The problem studied here is motivated by the replication methods used in many large storage systems that rely on data redistribution, such as Hadoop Distributed File System (HDFS) [START_REF] Borthakur | HDFS architecture guide[END_REF], Google File System (GFS) [START_REF] Ghemawat | The google file system[END_REF] and Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF]. Whenever there is a loss of content of a node due to its breakdown, the system regenerates the lost data blocks from other copies and allocates them in other functioning nodes. The fact of a node breaking down is closely related to its level of activity: the more data it stores and the more tasks it handles, the faster it presents failures.

Consistency and fault-tolerance in replicated data stores have been largely studied, see for example [START_REF] Tanenbaum | Distributed systems: principles and paradigms[END_REF]Chapters 7 and 8] and [START_REF] Özsu | Principles of distributed database systems[END_REF]Chapter 13]. In [START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF] the authors study the evolution of the load of a node in an equivalent problem to the one we consider. They propose a model of nodes that breakdown after an exponentially distributed amount of time with constant rates. When a node crashes, all the files that were in the node are reallocated following different allocation policies. This model does not take into account the fact that a node breaks down according to its level of activity. The novelty of our work relies on considering nodes whose time of failure is determined by a function of the current load they have.

Methodology

We introduce here the methodology used in the thesis. In Section 1.2.1 we define the Markov Decision Processes (MDPs), a general framework used for modelling stochastic optimisation problems. In Section 1.2.2 we describe the value iteration method, a numerical technique that can be used for solving MDPs. The Multi-Armed Restless Bandit Problem (MARBP), a particular subclass of MDPs, is presented in Section 1.2.3. In Section 1.2.4 a relaxation approach for the MARBP is discussed, which allows us to derive wellperforming heuristics policies. The mean-field technique used in Chapter 4 to study systems in large-scale regimes is outlined in Section 1.2.5.

Markov Decision Processes

In this section we introduce a powerful framework related to the study of stochastic optimisation problems, the Markov Decision Processes (MDPs). They have been largely studied in literature and are one of the main tools used in the thesis. MDPs were introduced by Bellman in 1957 ( [START_REF] Bellman | A Markovian decision process[END_REF]) as a generalisation of Markov Processes where decisions take a role. For a full overview we refer to the textbooks [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF][START_REF] Hernández-Lerma | Discrete-time Markov control processes: basic optimality criteria[END_REF][START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF][START_REF] Ross | Introduction to stochastic dynamic programming[END_REF].

A continuous-time MDP is a tuple (X , A, q, C), where • X is the state space of the process. We will consider the discrete state space X = N ∪ {0}.

• A is a finite set of actions, and A(m) ⊂ A is the set of actions for state m ∈ X .

• q : X × A × X → R + is the transition rates function.

• C : X × A → R is the cost function.

In an MDP, a decision maker knows the current state m ∈ X and selects an action a from the space of actions A(m). The transition to the next state m is defined by the exponential transition rate q(m |m, a) that depends not only on the current state of the Markov Process but also on the action. Let ϕ be a policy that prescribes which action to take in each moment in time. We will denote by X ϕ (t) and A ϕ (t) the state and the action of the process at time t under policy ϕ, respectively.

When the process visits state m and the action taken is a, C(m, a) determines the incurred cost. The objective is to find a policy that minimises some cost criterion. Typically, one studies finite-horizon, discounted infinite-horizon and average-cost criterion. We will focus on the latter, and we will consider stationary policies. Hence, our objective is to find a policy ϕ that minimises lim sup

T →∞ 1 T E T 0 C(X ϕ (t), A ϕ (t))dt .
Obtaining an optimal policy of an MDPs is typically out of reach. The existence of a solution cannot always be assured, and when it exists, its complexity rapidly scales with the dimensions of the state space, the so-called "curse of dimensionality" [START_REF] Bellman | A Markovian decision process[END_REF].

A method for proving the existence and identifying an optimal policy of an MDP comes after the study of the average-cost optimality equations, also known as Bellman equations. Let τ (m, a) = m ∈X q(m |m, a)

denote the total transition rate for state m and action a. If there is a pair (g, V (•)) such that

g + τ (m, a)V (m) = min a∈A(m) C(m, a) + m q(m |m, a)V (m ) ∀m, (1.2.1)
then a policy that is the argument of the minimum in (1.2.1) is average-cost optimal [60, Section V]. The value g is the incurred optimal average cost per unit of time, and V (•) is known as the value function, which captures the difference in cost between starting in state m and an arbitrary reference state.

Uniformisation and value iteration

We present now the discrete-time MDPs with time steps n = 1, 2, . . .. A discrete-time MDP is a tuple X , Ã, P, C , where X , Ã and C are the state space, the set of actions and the cost function, respectively, as in the continuous-time MDP. The function P (m |m, a) is the probability that the process makes a transition to state m in one step given that the current state is m and the action taken is a.

We are interested in discretising a continuous-time MDP in order to get an equivalent discrete-time one. In this sense, we use a discretisation method known as uniformisation. Let (X , A, q, C) be a continuous-time MDP, and let τ (m, a) be the total transition rate for state m and action a. We say the transition rates are uniformly bounded if there is a constant γ such that τ (m, a) ≤ γ for every m, a. In order to uniformise (X , A, q, C), we assume it has uniformly bounded rates.

We define an associated discrete-time MDP X , Ã, P, C , where the time between steps represents exponentially distributed time intervals of mean 1/γ in the continuous-time MDP. We let X = X and à = A be defined as in the continuous-time MDP, and C(m, a) = C(m, a)/γ is the cost function per time step. Then, for the probabilities, we set

P (m |m, a) =    q(m |m, a)/γ if m = m 1 -τ (m, a)/γ if m = m,
where 1-τ (m, a)/γ is the probability of having a "dummy" transition, i.e., the chain does not change its state.

The resulting discrete-time process is embedded in the original continuous-time one. As a consequence, the optimal policy for the discrete-time model is the same as for the continuous-time MDP. For a deeper insight in uniformisation see [START_REF] Norris | Markov chains[END_REF]Chapter 3].

We can now introduce the discrete version of the Bellman Equation for a given discrete-time MDP. If there is a pair (g, V (•)) such that g + V (m) = min then the argument of the minimum in Equation (1.2.2) is an optimal average cost policy. Note that g = g/γ is the average optimal cost per transition and V (•) is the value function, as described in the continuous-time

Bellman Equation (1.2.1).

Equation (1.2.2) can be numerically solved with algorithms like policy iteration or value iteration. We focus here on the latter, which we use to characterise optimal policies in Sections 3.4.1 and 3.4.2, and to numerically determine the performance of an optimal policy in Sections 2.5 and 3.6. Value iteration works as follows. For each m ∈ X set

V 0 (m) = 0 V n+1 (m) = min a∈ Ã(m) C(m, a) + m P (m |m, a)V n (m )
for n = 0, 1, . . . . (

The function V n (m) is the minimum expected finite-horizon cost that can be achieved in n steps when starting in state m. It can also be written as V n (m) = min ϕ E n-1 s=0 C(X ϕ (s), A ϕ (s))|X 0 = m . When taking the limit in n of the sequence of functions V n (•), whose existence can be assured under certain conditions, the value function V (•) and the average optimal cost g from Equation (1.2.2) can be retrieved: the limits V n (•) -ng → V (•) and V n+1 (•) -V n (•) → g as n → ∞ hold. The sequence of actions defined as the minimising action in each step n in (1.2.3) also converges, and the limit is an average-cost optimal policy, see [START_REF] Hernández-Lerma | Discrete-time Markov control processes: basic optimality criteria[END_REF] for details. In addition, when properties of the value function V (•), such as monotonicity and convexity, can be proved for the functions V n (•), these carry over to V (•). We use this approach in the proof of Theorem 3.14 in Appendix 3.7.5 and for Proposition 3.9 in Section 3.4.1.

We present how value iteration can be numerically applied to obtain an optimal policy of a discrete-time MDP with finite state space. The algorithm consists in building the functions V n (•) in a recursive fashion as defined in Equation (1.2.3). Since for any m, V n+1 (m) -V n (m) converges to the average optimal cost g, we will stop the recursion when the difference max m∈X (V n+1 (m) -V n (m)) -min m∈X (V n+1 (m) -V n (m)) is sufficiently small. Some of the models we study have infinite state space with rates that are not uniformly bounded, namely the abandonment queue studied in Section 3.4. When we consider abandonments, each customer in the queue can abandon at a fixed rate, which means that the rates grow linearly with the number of customers.

A method used to handle infinite state spaces and unbounded rates is the so-called truncation. We fix a state L such that the process does not visit any state m > L, i.e. q(m |m, a) = 0 for any m, a and m > L.

The rates q(m |m, a) for m, m ≤ L remain unchanged.

When we use this truncation method for proving analytical properties for V (•) (e.g. monotonicity), boundary effects may appear. We will then make use of a smoothing rate truncation method, see [START_REF] Bhulai | On structural properties of the value function for an unbounded jump Markov process with an application to a processor sharing retrial queue[END_REF]. We modify the rates of the original process for states m < L, such that they decrease to 0 as m grows large, up to state L, where there are no transitions to states m > L. The obtained smoothed process, and its corresponding value function V L (•), converges to the original one when L → ∞, as it is stated in [START_REF] Bhulai | On structural properties of the value function for an unbounded jump Markov process with an application to a processor sharing retrial queue[END_REF]Theorem 3.1]. The proofs in Sections 3.7.2 and 3.7.5 are based on this method.

Multi-Armed Restless Bandits

We present a particular subclass of MDPs, the Multi-Armed Restless Bandit Problem (MARBP) introduced in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF]. The restless bandit model has been proved to be a powerful stochastic optimisation framework to model control problems. In this thesis we study an MARBP in Chapters 2 and 3.

We consider a set of N bandits. The bandits are controllable stochastic processes whose transition rates depend on whether they are made active or passive, with the constraint of having at most R < N active bandits at the same time. We use the same notation as in Section 1.2.1 for the continuous-time MDPs. The state space of the bandits is X = N ∪ {0}, and the set of actions is A = {0, 1}, where a = 0 denotes the action of making a bandit passive and a = 1 of making it active. Let ϕ be the policy that determines the action taken for each bandit, which is a function of the states of the bandits.

For a given policy ϕ, X ϕ k (t) ∈ X denotes the state of bandit k at time t, and

X ϕ (t) := (X ϕ 1 (t), . . . , X ϕ N (t)). A ϕ k (t) ∈ A denotes the action of bandit k at time t, and A ϕ (t) := (A ϕ 1 (t), . . . , A ϕ N (t)).
The constraint can then be expressed as

N k=1 A ϕ k (t) ≤ R ∀t ≥ 0. (1.2.4)
We define the set of feasible policies Φ as the set of all policies that satisfy (1.2.4).

When X ϕ k (t) = m and A ϕ k (t) = a, bandit k makes a transition from state m to state m at rate q k (m |m, a). The restless term means that bandits may change state even if they are passive. If C k (m, a) denotes the cost per unit of time of bandit k, the objective of the optimisation problem is to find the policy ϕ that minimises the long-run average cost:

lim sup T →∞ 1 T E T 0 N k=1 C k (X ϕ k (t), A ϕ k (t))dt . (1.2.5)
In summary, we look for a policy ϕ that minimises (1.2.5) under constraint (1.2.4).

In order to solve the MARBP, there exists a methodology, explained in Section 1.2.4, that allows us to derive efficient index-based policies. An index policy assigns an index to each bandit depending on its current state, and makes active the R bandits having currently the largest indices. Index type policies are simple to implement. A first seminal work with an index-type solution for the multi-armed bandit problem has been proposed by Gittins in the classical non-restless model [START_REF] Gittins | Bandit processes and dynamic allocation indices[END_REF], i.e., where the passive bandits do not change their state.

Optimal control in restless bandit problems provides a powerful optimization framework to model dynamic scheduling of activities. In particular, regarding optimal control of computing systems, the restless bandit framework has been successfully applied in, for example, the context of wireless downlink scheduling [START_REF] Anand | A Whittle's index based approach for QoE optimization in wireless networks[END_REF][START_REF] Ayesta | A Modeling Framework for Optimizing the Flow-Level Scheduling with Time-Varying Channels[END_REF][START_REF] Ouyang | Asymptotically optimal downlink scheduling over Markovian fading channels[END_REF], load balancing problems [START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: application to resource-allocation problems[END_REF], systems with delayed state observation [START_REF] Ehsan | On the optimality of an index policy for bandwidth allocation with delayed state observation and differentiated services[END_REF], broadcast systems [START_REF] Raghunathan | Index policies for real-time multicast scheduling for wireless broadcast systems[END_REF],

multi-channel access models [START_REF] Ahmad | Optimality of myopic sensing in multichannel opportunistic access[END_REF][START_REF] Liu | Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access[END_REF], stochastic scheduling problems [START_REF] Ansell | Whittle's index policy for a multi-class queueing system with convex holding costs[END_REF][START_REF] Glazebrook | An index policy for a stochastic scheduling model with improving/ deteriorating jobs[END_REF][START_REF] Niño-Mora | Dynamic priority allocation via restless bandit marginal productivity indices[END_REF] and scheduling in systems with abandonments [START_REF] Ayesta | A Nearly-Optimal Index Rule for Scheduling of Users with Abandonment[END_REF][START_REF] Glazebrook | Index policies for the admission control and routing of impatient customers to heterogeneous service stations[END_REF][START_REF] Larrañaga | Index Policies for multi-class queues with convex holding cost and abandonments[END_REF][START_REF] Niño-Mora | Marginal productivity index policies for admission control and routing to parallel multi-server loss queues with reneging[END_REF].

Lagrangian relaxation

We describe now the methodology pioneered by Whittle to derive well-performing heuristics for the MARBP problem [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF]. A key step in the methodology is a relaxation of the constraint (1.2.4), which states that the number of active bandits must be satisfied on average, and not in every decision epoch:

lim sup T →∞ 1 T E T 0 N k=1 A ϕ k (t)dt ≤ R. (1.2.6)
Let Φ REL denote the set of policies satisfying the relaxed constraint (1.2.6), and in particular Φ ⊆ Φ REL .

We consider the problem of finding a policy ϕ that minimises (1.2.5) under constraint (1.2.6). Using the Lagrangian multipliers approach we can rewrite the problem and obtain the following unconstrained version, which we call relaxed optimisation problem. Find a policy ϕ that minimises lim sup

T →∞ 1 T E T 0 N k=1 C k (X ϕ k (t), A ϕ k (t)) -W N k=0 A ϕ k (t) dt . (1.2.7)
The Lagrange multiplier W represents a subsidy for making each bandit passive. The Lagrange multipliers' theory states that there exists a multiplier W such that constraint (1.2.6) is satisfied. This new formulation does not have a common constraint, and hence it allows us to decompose the problem in N subproblems, one for each bandit. For a given W , we will consider the one-dimensional problem of minimising lim sup

T →∞ 1 T E T 0 (C k (X ϕ k (t), A ϕ k (t)) -W A ϕ k (t)) dt , (1.2.8)
for each bandit k. As a direct consequence, the optimal policy of the relaxed problem is obtained by combining the optimal policies of the N subproblems. Studying the one-dimensional problem is the key idea introduced by Whittle [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF], used in order to simplify the original problem. Whittle further showed that, in case the technical condition known as indexability holds, the solution to (1.2.8) is of index type, i.e., there exists a function W k (m) such that the optimal policy is to make active a bandit if and only if

W k (m) > W .
This in turn implies that the optimal policy to solve (1.2.7) is of index type as well, and it activates all bandits such that their respective current indices are larger than W .

The indexability condition establishes that as the subsidy for passivity W increases, the set of states in which it is optimal to be passive for bandit k (denoted by P k (W )) increases as well, i.e., W < W implies

P k (W ) ⊆ P k (W ).
In other words, indexability states that, given a state m ∈ X , if it is optimal to make bandit k passive in state m for a given W , it is also optimal to make it passive for any W ≥ W .

If the indexability condition holds, the solution to (1.2.8) is given by

W k (m) := inf {W : m ∈ P k (W )} . (1.2.9)
Note that W k (m) is the smallest value for the subsidy such that it is optimal for that bandit to be passive in that state. This approach as proposed by Whittle has developed into a large research area, and as a consequence (1.2.9) is commonly known as Whittle's index.

Since the solution to the relaxed optimisation problem (1.2.7) will in general not be feasible for the original problem with constraint (1.2.4), Whittle proposed the following heuristic also based on the Whittle's index:

in every decision epoch make active the R bandits having currently the largest Whittle's index. We will refer to this policy as Whittle's index policy. This heuristic has been proved to be well-performing in many important examples, see Niño-Mora [START_REF] Niño-Mora | Sensor scheduling for hunting elusive hiding targets via Whittle's restless bandit index policy[END_REF], and asymptotically optimal under certain circumstances, see Weber and Weiss [START_REF] Weber | On an index policy for restless bandits[END_REF], Ji et al. [START_REF] Ji | Achieving optimal throughput and near-optimal asymptotic delay performance in multichannel wireless networks with low complexity: a practical greedy scheduling policy[END_REF], Ouyang et al. [START_REF] Ouyang | Asymptotically optimal downlink scheduling over Markovian fading channels[END_REF] and Verloop [START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF].

Mean-field theory

In this section we present the mean-field limit theory. We consider systems with interacting Markov processes, and we aim to describe the behaviour of the whole system as the number of processes grows large.

We use this approach to study large-scale systems, in Chapters 2 and 4. For more details we refer to the lectures [START_REF] Sznitman | Topics in propagation of chaos[END_REF], and the works in continuous-time [START_REF] Bobbio | Analysis of large scale interacting systems by mean field method[END_REF], in discrete-time [START_REF] Boudec | A generic mean field convergence result for systems of interacting objects[END_REF] and in discrete-time with vanishing intensity [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF].

Assume we have N continuous-time Markov processes living in the finite state space X , that are identically distributed and indistinguishable. This means that the transition rates of a given process depend on the total number of processes present in each state i ∈ X , and not on the current state of one of them. Let X(t)

denote the state of a randomly chosen process. We further define N i (t) for each i ∈ X as the number of processes in state i at time t. Let N (t) := (N i (t) : i ∈ X ) be the state of the whole system, which satisfies i∈X N i (t) = N for all time t. We assume that the evolution of the system is such that there are no synchronous transitions in different processes. Under these definitions, the transition rates of X(t) when the state of the system is N (t) are given by the matrix Q ij defined as follows:

Q ij ( N (t)) =    lim h→0 1 h P X(t + h) = j|X(t) = i, N (t) = N n if N i (t) > 0 0 if N i (t) = 0 (1.2.10) Q ii ( N (t)) = - j∈X ,j =i Q ij ( N (t)),
where

P X(t + h) = j|X(t) = i, N (t) = N n
is the probability of the process to be in state j at time t + h conditioned to the fact that at time t it is in state i and the whole system is in state N n.

Let n(t) = N (t)/N denote the normalised vector, i.e., n i (t) is the proportion of processes in state i at time t, we omit the dependence on N for the ease of the reading. The transition rate function associated to n(t) is given by ) is defined at discrete points whose coordinates are integer multiples of 1/N . We will focus on the latter since we are interested in studying the limit in distribution of n(t) as N goes to infinity.

q (N ) ij ( n(t)) := Q ij (N • n(t)
An important result in mean-field limit theory ( [START_REF] Boudec | A generic mean field convergence result for systems of interacting objects[END_REF][START_REF] Bobbio | Analysis of large scale interacting systems by mean field method[END_REF]) states that, under certain conditions, there exists a

function q ij ( n(t)) such that q ij ( n(t)) = q (N ) ij ( n(t)
), for all N ≥ 1 and all n proportions out of N . Then, the normalised vector n(t) converges in distribution to a deterministic vector as N tends to infinity. Moreover, for each i ∈ X we have the following differential equation:

d dt n i (t) = j∈X n j (t)q ij ( n(t)).
This result can be adapted to different contexts. In Chapter 2 we refer to the limiting results in [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] for mean-field results in the presence of an environment process. In Chapter 4 we make a detailed analysis of the evolution of the load of a node in a storage system in the mean-field limit.

Main contributions

In this section we present the structure of the manuscript and the main contributions obtained.

In Chapter 2, we consider a stochastic problem with controllable processes and unobservable environments, as described in Section 1.1.1. The chapter is based on our publication [START_REF] Duran | Asymptotic optimal control of Markov-modulated restless bandits[END_REF]. We assume that the decision maker takes actions based only on the current state of the controllable process. We study a continuous-time multi-armed restless bandits problem (MARBP) in an asymptotic regime, where the number of bandits grows large together with the speed of the environments. The main goal is to find policies that asymptotically minimise the long-run average cost.

Our main result is Theorem 2.5, where we provide sufficient conditions for a policy to be asymptotically optimal. We further introduce a set of priority policies that satisfy those conditions. The second main result is stated in Proposition 2. [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF], where an averaged version of Whittle's index policy is proved to be inside the set of asymptotic optimal policies. In Section 2.5, we evaluate numerically the performance under Whittle's index policy, outside the asymptotic regime. We study a multi-class scheduling problem in a wireless downlink with two classes. We observe that already for two bandits the performance of the averaged Whittle's index policy becomes close to optimal as the speed of the modulated environment increases.

The key step of the proofs of Chapter 2 follows from studying a system with the averaged parameters of the stochastic process, where the average is determined by the stationary measure of the environments. In particular, we consider a fluid process and a linear programming (LP) problem with the defined parameters. This is based on the results in [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] for the evolution of a particle system under a rapidly changing environment. The policies proved to be asymptotically optimal are the ones that make the fluid process converge to the equilibrium of the LP problem.

In Chapter 3, we study an MARBP with observable environments, as described in Section 1.1.2. The chapter is based on [START_REF] Duran | On the Whittle's Index of Markov-modulated restless bandits[END_REF]. Each bandit is formed by two processes, a controllable process and an environment.

The decision maker observes the current state of the environment when choosing actions for the controllable processes. The challenge relies on finding optimal control of bandits living in a multi-dimensional state space.

We study the dynamics of one bandit, based on the relaxed version of the system as introduced in Section 1.2.4. We consider policies of threshold type, where the controllable process is made active if and only if its state is above a certain threshold. We assume the optimality of threshold policies, which is typically the case in many queuing models, and we propose Algorithm 3.4 to find the optimal threshold policy for each value of the Lagrangian multiplier. Whittle's index is then derived. In Proposition 3.8 we show that, if we consider a slow environment process, Whittle's index coincides with Whittle's index of a bandit that only sees a fixed state of the environment.

As a relevant case study, we consider a queuing system with abandonments, under linear holding cost.

Our main results are Theorem 3.14, where indexability is proved, and Theorem 3.15, where closed-form expressions for Whittle's index are provided. Various techniques have been used for the proofs, such as the comparison of stochastic processes as described in [START_REF] Boucherie | Queueing networks: a fundamental approach[END_REF]Chapter 9], or the smoothing truncation method, as presented in Section 1.2.1.

In Proposition 3.19 we derive simpler expressions for the queues with abandonments when the environments vary slowly, and when they vary fast. In particular, the result for the fast regime allows us to compare the observable model of Chapter 3 with the unobservable model of Chapter 2: in Chapter 3 the index remains dependent on the state of the environment, in contrast to the index that takes the averaged parameter values in Chapter 2. This is studied numerically in Section 3.6.3, where we conclude that there can be an important gain in performance when we allow the decision maker to observe the environment, enlarged in cases where the optimal policy strongly depends on the state of the environment.

We include a further comparison between the results for the unobservable and observable regimes in the conclusions of the thesis, see Chapter 5.

In Chapter 4, we study a problem of allocation in large distributed storage system, as introduced in Section 1.1.3. This chapter is based on [START_REF] Duran | Analysis of a stochastic model of replication with linear breakdown rates[END_REF]. We consider files distributed among a set of nodes. When one of the nodes breaks down all the files it has are reallocated at random to other nodes, and the node goes back to a state with zero files. The analysis is focused on the mean-field regime of the system, i.e., when the number of nodes and files grow large, assuming a fixed average number of files per node. Under this regime, the evolution of the load of a node is studied. The main difficulty of the problem relies on the fact that the rate of the breakdowns of the nodes depend on the load they currently have.

We first consider the so-called Random Weighted allocation policy, that assigns to each node a weighted probability of receiving a file that depends on its current load. Our main contribution is Theorem 4.5, where we show the existence of the process in the mean-field limit, together with the existence and uniqueness of its stationary measure. In a following result in Theorem 4.7, we make the average number of files per node grow large, and we prove the convergence in distribution of the load in steady state. Alternative proofs are presented for the Random allocation policy, where the probability of assigning a file is uniform among all servers. This is done in Theorems 4.8 and 4.10.

We work with urn models in order to describe the dynamics of the process. In an urn model, there is a set of identical balls moving across urns. Each ball waits an exponentially distributed amount of time and then it jumps to another urn. For our case, we consider a model where all the balls in an urn jump at the same time. We study the global balance equations of such a process, and using the properties of the allocation functions, we characterise the stationary measure of the process as the solution of a fixed point equation, see Section 4.3.

Chapter 2

Optimal control with unobservable environments In this chapter we study a large-scale resource allocation problem with controllable processes affected by unobservable environments. We focus on a multi-armed restless bandit problem, as introduced in Section 1.2.3. The bandits are the controllable processes, whose transition rates depend on the current state of the environments. We consider that the environments change state relatively fast with respect to the controllable processes. We study the mean-field limit of the processes, obtained by letting the population of bandits grow large, together with the speed of the environment.

In our first main contribution, we present sufficient conditions for a policy to be asymptotically optimal and we show that a set of priority policies satisfies these. In our second main contribution, we introduce the averaged Whittle's index policy and prove it to be inside the set of asymptotically optimal policies. We further provide a numerical evaluation of the performance of the averaged Whittle's index policy.

For our proofs we consider techniques as used in [START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF][START_REF] Weber | On an index policy for restless bandits[END_REF], where MARB problems without environments are studied in a mean-field regime. In the seminal work [START_REF] Weber | On an index policy for restless bandits[END_REF], Whittle's index policy is shown to be asymptotically optimal as the number of bandits that can be made active grows proportionally to the total number of bandits. In [START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF], the author does not assume indexability, and, using fluid-scaling techniques, proves that a set of priority policies is asymptotically optimal.

Another technique that we use is based on convergence results for particle systems living in rapidly varying environments. We refer to [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF][START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF], where the authors derived that in the limit the system is described by an ODE, and the transitions rates of the particles are averaged according to the steady-state distribution of the environments. The paper [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] considers a countable state space and each particle is associated its 13 own modulated environment (no assumption is made on the joint evolution of the environments). On the other hand, in [START_REF] Benaïm | A class of mean field interaction models for computer and communication systems[END_REF] a finite state space and one common environment is considered, resulting in less complex technical conditions.

In order to infer the state of the unobservable environment, one could apply learning techniques as the ones studied in [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. However, we will not use such techniques, since the environments change at a much faster time scale than the controllable processes, and we assume that it will be too costly to learn from them. We follow up this discussion in Section 5.2.2, where in the context of reinforcement learning, we introduce a method for the case where the environments do not change relatively fast.

The chapter is organized as follows. In Section 2.1, we define the multi-class restless bandit control problem and introduce the Markov-modulated environments. Section 2.2 contains the asymptotic optimality results.

In Section 2.3, we define a set of priority policies and prove it to be asymptotically optimal when the state space is finite. In Section 2.4 we define an averaged version of Whittle's index policy and prove it to be asymptotically optimal. Section 2.5 presents our numerical results.

Model description

We consider a multi-class restless bandit problem in continuous time. There are K classes of bandits and there are N k class-k bandits present in the system. We further define N := k N k as the total number of bandits and define γ k := N k /N as the fraction of class-k bandits. At any moment in time, a class-k bandit is in a certain state j ∈ {1, 2, . . . , J k }, with J k ≤ ∞. In particular, the state space can be countable infinite.

At any moment in time, a bandit can either be kept passive or active, denoted by a = 0 and a = 1, respectively. There is the restriction that at most αN bandits can be made active at a time, α ≤ 1.

The transitions of the class-k bandits depend on a process called environment, described by the Markov process D k (t) that lives in a countable state space Z = {1, . . . , d, . . .} and is positive recurrent. We make no further assumptions on the distribution of the joint vector D(t) = (D 1 (t), . . . , D K (t)). For example, it could be that there is one common environment for all classes of bandits, or instead, the environments per class are independently distributed. We further let φ( d) denote the stationary probability vector that the k (j|i, a), j = 1, . . . , J k , j = i. The scaling 1/N makes sure that the evolution of the state of a bandit is relatively slow compared to that of its environment, i.e., the environment changes relatively fast. We assume that the evolution of one bandit (given its action and the state of its environment) is independent of that of all the other bandits. We further define the averaged transition rate by q k (j|i, a) := d∈Z φ k (d)q (d) k (j|i, a). The fact that the state of a bandit might evolve even under the passive action explains the term of a restless bandit. Throughout the chapter, we assume that the transition rates are uniformly bounded, i.e.,

J k j=1 q (d) k (j|i, a) < C 2 , for all a, d, i, k, (2.1.1)
for some C 2 < ∞.

A policy determines at each decision epoch which αN bandits are made active. Decision epochs are moments when one of the N bandits changes state. We focus on Markovian policies that base their decisions only on the current proportion of bandits present in the different states. Hence, this means that the decision maker cannot observe the state of the environment D(t). In addition, we assume the decision maker does not attempt to learn the state of the environment either. We write x := (x j,k ; k = 1, . . . , K, j = 1, . . . , J k ), where x j,k represents the proportion of class-k bandits that are in state j, hence,

x ∈ B :=    x : 0 ≤ x j,k ≤ 1 ∀j, k and j x j,k = γ k    .
Given policy ϕ, we then define the function y ϕ,1 :

B → [0, 1] K k=1
J k that distinguishes the action chosen for the bandits. That is, given a policy ϕ, y ϕ,1 j,k ( x) denotes the proportion of class-k bandits in state j that are activated when the proportion of bandits in each state is given by x. Hence, y ϕ,1 (•) satisfies y ϕ,1 j,k ( x) ≤ x j,k and y ϕ,1 j,k ( x) ≤ α, ∀j, k. We focus on the set of policies such that y ϕ,1 (•) is continuous. We further define y ϕ,0 j,k ( x) := x j,k -y ϕ,1 j,k ( x), as the proportion of class-k bandits in state j that are kept passive. For a given policy ϕ, we define X N,ϕ (t) := (X N,ϕ j,k (t); k = 1, . . . , K, j = 1, . . . , J k ), with X N,ϕ j,k (t) the number of class-k bandits that are in state j at time t.

Our performance criteria are stability and long-run average holding cost. For a given policy ϕ, we will call the system stable if the process X N,ϕ (t) has a unique invariant probability distribution. We will denote by X N,ϕ and X N,ϕ j,k the random variables following the steady state distributions, assuming they exist. In case the state space is finite, the process X N,ϕ (t) being unichain is a sufficient condition for stability of the policy ϕ. For infinite state space, whether or not the system is stable can depend strongly on the employed policy. We will only be interested in the set of stable policies.

We denote by C (d) k (j, a) ∈ R, j = 1, . . . , J k , the holding cost per unit of time for having a class-k customer in state j under action a and when in environment d. We note that C (d) k (j, a) can be negative, i.e., representing a reward. We define the holding cost averaged over the states of the environment as C k (j, a) :=

d∈Z φ k (d)C (d)
k (j, a). We further introduce the following value functions for given policy ϕ, and initial proportion of bandits

X N,ϕ (0) N = x ∈ B: V N,ϕ - ( x) := lim inf T →∞ 1 T E   T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a)y ϕ,a j,k X N,ϕ (t) N dt   and V N,ϕ + ( x) := lim sup T →∞ 1 T E   T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a)y ϕ,a j,k X N,ϕ (t) N dt   . (2.1.2) If V N,ϕ - ( x) = V N,ϕ + ( x) for all x, then we define V N,ϕ ( x) := V N,ϕ + ( x).
We assume there exists a stable policy for which V N,ϕ ( x) < ∞. Our objective is to find a policy ϕ * that is average optimal,

V N,ϕ * + ( x) ≤ V N,ϕ - ( x)
, for all x and for all policies ϕ, (2. 1.3) under the constraint that at any moment in time at most αN bandits can be made active, that is,

K k=1 J k j=1 y ϕ,1 j,k X N,ϕ (t) N ≤ α, for all t.
(2.1.4)

Rapidly varying modulated environments

In this section we study the system as the environment is fast changing and the number of bandits scales.

In Section 2.2.1 we prove asymptotic independence between the proportion of bandits in each state and the environment. In Section 2.2.2 we establish convergence to a fluid limit and use this to lower bound the performance for any policy. This lower bound allows to prove asymptotic optimality of certain policies, which is presented in Section 2.2.3.

Asymptotic independence

In the lemma below we prove that the bandits are asymptotically independent of the environment, i.e., when the amount of bandits N tends to infinity. The proof can be found in the Appendix 2.6.

Lemma 2.1. Assume ϕ is a stable policy for any N . Then, for any subsequence of N such that X N,ϕ /N N ∈N converges in distribution, we have

lim N →∞ E e -s11 X N,ϕ 11 N . . . e -s J K K X N,ϕ J K K N 1 ( D= d) = φ( d) lim N →∞ E e -s11 X N,ϕ 11 N . . . e -s J K K X N,ϕ J K K N . (2.2.1)

Fluid control problem and lower bound

In this section we study the behaviour of the system as N grows large, that is, as the number of bandits grows large and the environments vary rapidly. We state convergence to the fluid limit and derive an associated fluid control problem. The latter allows to derive a lower bound on the average holding cost for any policy ϕ.

Before presenting the fluid process to which the stochastic system converges, we first provide some intuition.

Recall that the transition rate of a bandit in state j to state i, when action a is performed, is given by

1 N q (d)
k (i|j, a). Since the rates of the environment do not scale with N , when we take N → ∞, the bandit will perceive a rapidly changing environment. Before it can make a new transition, its environment has already changed infinitely many times. Its transition rate will therefore be the average over the states the environment can be in, that is q k (j|i, a) = d∈Z φ k (d)q (d) k (j|i, a). The fluid process then arises by taking into account only the mean drifts q.

We denote by u a fluid control and let x u (t) be the corresponding fluid process. Let x u,a j,k (t) denote the proportion of class-k fluid in state j under action a at time t and let x u j,k (t) = x u,0 j,k (t) + x u,1 j,k (t) be the proportion of class-k fluid in state j.

We consider fluid controls u(t) that base their actions only on the state of the fluid process x(t). As such, policies for the stochastic process can be reduced to controls for the fluid problem. In particular, when given a policy ϕ, the corresponding fluid control u = ϕ is defined as

x u,a j,k (t) = y ϕ,a j,k ( x ϕ (t)). (2.2.2)
We define the dynamics of x u (t) as follows:

dx u j,k (t) dt = 1 a=0 J k i=1,i =j x u,a i,k (t)q k (j|i, a) - 1 a=0 J k i=1,i =j x u,a j,k (t)q k (i|j, a) = 1 a=0 J k i=1 x u,a i,k (t)q k (j|i, a), (2.2.3)
where the last step follows from q k (j|j, a) := -

J k i=1,i =j q k (i|j, a).
The constraint on the fluid control u is that the total proportion of active fluid satisfies

K k=1 J k j=1 x u,1 j,k (t) ≤ α, for all t ≥ 0. (2.2.4)
In the lemma below we formally state the convergence of the stochastic process X ϕ (t)/N of the proportions of bandits. This result will not be used in any of the proofs of our results, but is presented for completeness.

The proof can be found in the Appendix 2.6.

For the convergence to hold, it is assumed in Lemma 2.2 that the process describing the state of a class-k bandit at time t, is tight [START_REF] Billingsley | Convergence of probability measures[END_REF] in N , that is, roughly speaking that the processes must not oscillate too wildly so that probability mass cannot disappear from compact sets. For either a finite state space (J k < ∞) or when the possible transitions in each state is finite, tightness follows directly, see [17, page 12] We will be interested in finding an optimal equilibrium point x of the fluid dynamics that minimises the holding cost averaged over the environments,

|y ϕ * ,1 j,k ( x) -y ϕ * ,1 j,k ( z)| ≤ C sup i,l |x i,l -z i,l |,
K k=1 J k j=1 1 a=0 d∈Z φ k (d)C (d) k (j, a)x a j,k = K k=1 J k j=1 1 a=0 C k (j, a)x a j,k .
Setting (2.2.3) equal to zero, this gives us the following linear optimisation problem:

(LP ) v * := min (x a j,k ) K k=1 J k j=1 1 a=0 C k (j, a)x a j,k s.t. 0 = 1 a=0 J k i=1 x a i,k q k (j|i, a), ∀ j, k, (2.2.6) K k=1 J k j=1 x 1 j,k ≤ α, (2.2.7) J k j=1 1 a=0 x a j,k = γ k , ∀ k (2.2.8)
x a j,k ≥ 0, ∀ j, k, a, (2.2.9)

Let x * and v * denote an optimal solution and optimal value of the (LP) problem, respectively.

In Lemma 2.4 below, we use the LP formulation to find a lower bound on the original stochastic optimisation problem. Before that, we need the following condition.

N →∞ V N,ϕ - ( x) ≥ v * , (2.2.10)
with v * the optimal value of the (LP) problem.

The proof can be found in the Appendix 2.6.

Asymptotic optimality

In this section we present the asymptotic optimality results.

Theorem 2.5. Let x * be an optimal solution of the (LP) problem. Let ϕ * be a policy for which the fluid process x ϕ * (t) converges to x * as t → ∞, and x * is the unique equilibrium point (global attractor property). Assume ϕ * satisfies Condition 2.3 and the assumptions made in Lemma 2.2. Then, ϕ * is asymptotically optimal, that is, for all x and all policies ϕ, it holds that

lim N →∞ V N,ϕ * ( x) ≤ lim inf N →∞ V N,ϕ - ( x). ( 2
N →∞ P X N,ϕ * N = x * , D = d = φ( d).
(2.2.12)

Recall that C k (j, a) = d∈Z φ k (d)C (d) k (j, a). Thus lim N →∞ V N,ϕ * + ( x) = lim N →∞ K k=1 J k j=1 1 a=0 d∈Z x C (d) k (j, a)y ϕ * ,a j,k ( x) • P X N,ϕ * N = x, D = d = K k=1 J k j=1 1 a=0 d∈Z C (d) k (j, a)y ϕ * ,a j,k ( x * )φ k (d) = K k=1 J k j=1 1 a=0 C k (j, a)x * ,a j,k = v * .
where the first equality follows from the ergodicity theorem, the second equality from uniform integrability of X/N (interchange of limit and summations) and (2.2.12), the third equality from the fact that y ϕ * ,a j,k ( x * ) = x * ,a j,k (see (2.2.2) and lim t→∞ x ϕ * (t) = x * ), and the last step follows since x * is an optimal solution of (LP). This concludes the proof of Theorem 2.5. 2

Priority policies

In this section we will define an important class of priority policies for which we can prove asymptotic optimality results.

A priority policy is defined as follows. There is a predefined priority ordering on the states each bandit can be in. At any moment in time, a priority policy makes active a maximum number of bandits being in the states having the highest priority among all the bandits present. Hence, for a given priority policy prio, we would have that the proportion of class-k bandits in state j that see action 1 is given by

y prio,1 j,k ( x) = min      α - (i,l)∈S prio k (j) x i,l    + , x j,k    , (2.3.1)
where S prio k (j) denotes the set of pairs (i, l), i = 1, . . . , J l , l = 1, . . . , K such that class-l bandits in state i have higher priority than class-k bandits in state j under policy prio. In the lemma below we show that this function satisfies (2.2.5) when bandits have a finite state space. The proof is in the Appendix 2.6.

Lemma 2.6. If J k < ∞, Equation (2.2.5) is valid for any priority policy.

We now define a set of priority policies Π * that will play a key role in the chapter. The priority policies are derived from (the) optimal equilibrium point(s) x * of the (LP) problem: for a given equilibrium point x * , we consider all priority orderings such that the states that in equilibrium are never passive (x * ,0 j,k = 0) are of higher priority than states that receive some passive action (x * ,0 j,k > 0). In addition, states that in equilibrium are both active and passive (x * ,0 j,k • x * ,1 j,k > 0) receive higher priority than states that are never active (x * ,1 j,k = 0). Further, if the full capacity is not used in equilibrium (that is, k j x * ,1 j,k < α), then the states that are never active in equilibrium are never activated in the priority ordering. The set of priority policies Π * is formalized in the definition below. In particular, in the next section we will prove that an averaged version of the well-known Whittle's index policy is in fact inside this set of policies. Definition 2.7 (Set of priority policies Π * ). We define

X * := {x * : x * is an optimal solution of (LP) with x k (0) = X k (0) }.
The set of priority policies Π * is defined as

Π * := ∪ x * ∈X * Π(x * ),
where Π(x * ) is the set of all priority policies that satisfy the following rules:

1. A class-k bandit in state j with x * ,1 j,k > 0 and x * ,0 j,k = 0 is given higher priority than a class-k bandit in state j with x * ,0 j, k > 0.

2. A class-k bandit in state j with x * ,0 j,k > 0 and x * ,1 j,k > 0 is given higher priority than a class-k bandit in state j with x * ,0 j, k > 0 and x * ,1 j, k = 0.

If

K k=1 J k j=1 x * ,1
j,k < α, then any class-k bandit in state j with x * ,1 j,k = 0 and x * ,0 j,k > 0 will never be made active.

We can now state the asymptotic optimality result for priority policies in the class Π * . Intuitively, this result can be explained as follows. Let ϕ * be some policy from the set Π(x * ) ⊂ Π * . It is easily verified that x * is an equilibrium point of the fluid process x ϕ * (t). If in addition, the point x * is a global attractor, that is, for any initial point, the process x ϕ * (t) converges to x * , then using Theorem 2.5 one obtains the result.

Corollary 2.8. Assume a finite state space, J k < ∞, for all k. For a given policy ϕ * ∈ Π(x * ) ⊂ Π * , assume x * is the global attractor of the fluid process x ϕ * (t). If in addition, the process X N,ϕ * (t) is unichain, then ϕ * is asymptotically optimal, that is, (2.2.11) is satisfied.

Proof: Lemma 2.6 gives that ϕ * satisfies (2.2.5). Hence the result follows directly from Theorem 2.5. 2 Remark 2.9 (Infinite state space). The assumption of finite state space in Corollary 2.8 was made in order to assure uniformly Lipschitz continuity of the function y ϕ * ,1 j,k (•). In fact, when J k = ∞, one can easily construct a setting in which (2.2.5) does not hold. For example, for K = 1, take x (l) s.t.

x (l) i = α/l for i < l, x (l) l = 1 -α, and x (l) i = 0, for i > l. Take z (l) s.t. z (l) i = 0 for i < l, z (l) l = 1 -α, and z (l) i = α/l, for i > l. Then, y prio,1 l ( x (l) ) = 0 and y prio,1 l ( z (l) ) = 1 -α,
where prio is the policy that prioritizes state 1 over state 2, and state 2 over state 3, etc. However, sup j |x

(l) j -z (l) j | = α/l.
Since the state space is infinite, we can now take l → ∞. We then directly see that (2.2.5) does not hold.

We however note that in our numerical example, where we consider an infinite state space, we do observe a very close to optimal performance of the priority policies.

Averaged Whittle's index policy

In this section we introduce an averaged version of Whittle's index. The averaged Whittle's index policy is a particular case of a priority policy. It is however only defined in case the system is indexable, while our definition of the set of policies Π * is well-defined for both indexable and non-indexable systems.

In Section 1.2.3 we introduced the relaxation technique and Whittle's index. We recall here the needed concepts, based on this chapter's model. We start by Whittle's relaxation. In (2.1.4) we set the constraint that at most αN bandits can be active at a time. We replace it by its time-average version: lim

T →∞ 1 T E   T 0 K k=1 J k j=1 y ϕ,1 j,k X N,ϕ (t) N dt   ≤ α, (2.4.1)
and we consider the relaxed-constraint problem, i.e., minimise (2.1.2) under constraint (2.4.1). Using the Lagrangian approach, this can then be written as minimising lim

T →∞ 1 T E   T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a)y ϕ,a j,k X N,ϕ (t) N dt +W   T 0 K k=1 J k j=1 y ϕ,1 j,k X N,ϕ (t) N dt -α     ,
where W is the Lagrange multiplier (chosen such that the time-average constraint (2.4.1) holds). The latter can be decomposed into K subproblems, one for each class of bandit, where in each subproblem one needs to minimise the cost term plus a cost W whenever the bandit is made active. Each subproblem can be written as:

lim T →∞ 1 T E T 0 (C (D k (t)) k (S ϕ k (t), A ϕ l (t)) + W 1 (A ϕ k (t)=1) )dt , (2.4.2)
where S ϕ k (t) denotes the state of a class-k bandit at time t and A ϕ k (t) denotes the action chosen for the class-k bandit under policy ϕ (for the one-dimensional process).

We have then the following definitions. Definition 2.10 (Whittle's index). Whittle's index W k (j) is defined as the least value of W for which it is optimal in (2.4.2) to make the class-k bandit in state j passive.

We introduce now the indexability condition, that assures structural properties on the optimal policy of the relaxed control problem, and allows us to derive a policy from Whittle's index.

Definition 2.11 (Indexability).

A bandit is indexable if the set of states in which passive is an optimal action in (2.4.2) is increasing in W .

When indexability holds, the solution for the relaxed subproblem (2.4.2) is to activate all bandits that are currently in a state j such that their Whittle index W k (j) is larger than W . This solution is however not feasible for the original K-dimensional problem, since sometimes it may activate more than αN bandits at a time. For the original problem, the following heuristic was then proposed: active those αN bandits having currently the highest index value. This is what we call Whittle's index policy. The relaxation technique as such provides a systematic approach to get a simple index policy.

In this chapter, we study restless bandits living in a modulated environment. In the limiting regime, as the environment varies rapidly, we found that a bandit observes only the averaged (over the steady state of the environment) parameters, that is, q k (•) and C k (•, •). This motivates us to define the averaged Whittle index policy. Definition 2.12 (Averaged Whittle's index policy). The averaged Whittle's index W k (j) for our restless bandit problem living in a modulated environment is defined as the Whittle index that would result from the restless bandit problem with parameters q k (i|j, a), C k (j, a), and no modulating environment.

The averaged Whittle index policy activates those αN bandits having currently the highest averaged Whittle index value W k (S n,k (t)), where S n,k (t) is the state of the nth class-k bandit, k = 1, . . . , K, n = 1, . . . , N k .

Proposition 2.13. If for the averaged version of the restless bandit problem the process describing the state of a class-k bandit is unichain, regardless of the policy employed, and in addition the averaged restless bandit

problem is indexable, then there is an x * such that the averaged Whittle's index policy is inside the set of

priority policies Π(x * ) ⊂ Π * .
If in addition J k < ∞, for all k, and x * is the global attractor of the fluid process x ϕ * (t), then the averaged Whittle index policy is asymptotically optimal.

The above proposition extends the asymptotic optimality result of Whittle's index policy as obtained in [START_REF] Hodge | On the asymptotic optimality of greedy index heuristics for multi-action restless bandits[END_REF][START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF][START_REF] Weber | On an index policy for restless bandits[END_REF] to that of restless bandits living in rapidly varying Markov-modulated environments. The assumptions made in Proposition 2.13 are the same as those needed in [START_REF] Hodge | On the asymptotic optimality of greedy index heuristics for multi-action restless bandits[END_REF][START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF][START_REF] Weber | On an index policy for restless bandits[END_REF].

Proof of Proposition 2.13:

In [69, Proposition 5.6] it was proved that for the standard restless bandit problem, Whittle's index policy was inside some set of priority policies defined by some linear program problem ( LP ). Since we defined our averaged Whittle's index policy based on the standard restless bandit problem with averaged parameters, we directly have that the averaged Whittle index policy is inside the set of priority policies defined for ( LP ) based on the averaged parameters. However, it can be checked that the ( LP ) for the averaged parameters is equivalent to our (LP) problem, hence, the averaged Whittle index policy is inside Π * , which is equal to Π * .

From the unichain assumption, we obtain that Condition 2.3 is satisfied when J k < ∞. The asymptotic optimality result now follows directly from Theorem 2.5. 2

Numerical evaluation

The objective of this section is to evaluate the performance of the averaged Whittle index policy (and other heuristics) outside the asymptotic regime. We do this for a multi-class scheduling problem in a wireless downlink channel. The model we consider is the following. There is one wireless downlink channel that is shared by two classes of users. For a given policy, let M ϕ k (t) denote the number of class-k users in the system. Each class of users is associated a Markov-modulated environment, D k (t), k = 1, 2, which can be in two states. When D k (t) = d, class-k users arrive according to a Poisson process with parameter λ

(d) k , k = 1, 2.
At each moment in time, the base station can send data to at most one of the classes. Given

D k (t) = d and M ϕ k (t) = m k , class k (if served) has departure rate µ (d) k m k m k + 1 .
This mimics opportunistic scheduling, since the more class-k users present in the system, the higher will be the maximum capacity available among the class-k users. See for further details the discussion in [45, Section

The scheduler now needs to decide at each moment in time which of the two classes to activate. We assume

ρ := 2 k=1 λ k µ k < 1, with λ k = 2 d=1 λ (d) k φ k (d) and µ k = 2 d=1 µ (d) k φ k (d)
, so any work-conserving policy makes the system stable. The objective will be to minimise the mean number of users in the system.

The performance for a given policy will be computed using the value iteration approach, as introduced in Section 1.2.2, by writing the dynamic programming equation for the process

(M ϕ 1 (t), M ϕ 2 (t), D 1 (t), D 2 (t)).
Note that we only consider policies that cannot observe the environments when the scheduling decision is taken.

We describe the averaged Whittle index policy in Section 2.5.1. We calculate a benchmark policy and numerically evaluate index policies for several settings: in Section 2.5.3 each class is associated its own environment in order to model Markov-modulated arrival processes. In Section 2.5.4 we will study the effect of having one common environment that influences the departure rates of the classes. In Section 2.5.5

we introduce a discussion for the observable case. Our overall conclusion is that the averaged Whittle index policy performs close to optimal when the modulated environments varies rapidly.

Averaged Whittle's index

This model fits in the restless bandit framework with Markov-modulated environments, as presented in this chapter. In particular, there are two bandits, each bandit representing a class of users, and the state j ∈ {1, 2, . . .} of the class-k bandit represents its queue length. Hence, when D k = d, the class-k bandit makes a transition from state j to state j + 1 at rate λ

(d)
k , and from j to j -1 at rate µ

(d) k j j+1
a, where a = 1 when the class-k bandit is served, and a = 0 otherwise. At most one bandit can be activated at a time.

Using the expression of Whittle's index as derived in [START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: application to resource-allocation problems[END_REF], we obtain that the averaged Whittle index for the class-k bandit in state n (its queue length), is given by

W k (n) = E(M n k ) -E(M n-1 k ) π n k (n) -π n-1 k (n -1) , n = 1, 2, . . . .
Here M n k denotes the stationary random variable of the process M n k (t), where ϕ = n is known as the threshold policy with threshold n. It is a one-dimensional birth-and-death process with birth rates λ k and death rates in state j at rate 1 (j>n) µ k j j+1 . π n k (•) denotes the stationary measure of M n k (t). We will study threshold policies in detail in Chapter 3.

The averaged Whittle index policy serves at each moment in time the class of users having the highest index value W k (M k (t)). From Proposition 2.13 we have that this policy is asymptotically optimal under certain conditions. One of the conditions concerns indexability, which is easily verified for this example using [45, Proposition 2]. The global attractor property is verified numerically for the different examples presented in this section. Another condition needed is that the state space is bounded, which is not the case for our example. The numerical results however do indicate a good performance.

The optimality results in this chapter are for the limiting regime where both the number of bandits (classes) as well as the speed of the modulated environments grow large. In the numerical examples we will instead keep the number of bandits equal to two, which allows to evaluate the performance of our policy outside the asymptotic regime. We then evaluate the performance of the averaged Whittle index policy, as well as other heuristics, for different speeds of the environments.

Benchmark policy

The modulated environments are unobservable. In addition, their evolution does not depend on the state of the bandits. We consider the following benchmark policy, derived from the Bellman equation:

V ( n) = n 1 + n 2 + 2 k=1 2 d=1 φ k (d)λ (d) k V ( n + e k ) + min a∈{1,2} 2 k=1 2 d=1 1 (a=k) φ k (d)µ (d) k V (( n -e k ) + ) , (2.5.1)
that is, in every state n = (n 1 , n 2 ), the only information available to the decision maker is the steady-state distribution of the environment. In the next sections we compare the performance of our heuristics to that of the performance under the actions as defined in (2.5.1).

Markov-modulated arrival processes

Our first numerical example studies Markov-modulated arrival processes. That is, environments D 1 (t) and D 2 (t) are two independent Markov processes. Each environment can be in two states {1, 2} and environment

D k (t) makes a transition from state d to state d at rate r k (d |d). When class k sees environment d, the arrival rate is λ (d)
k (while the departure rates remain unchanged). Example 1: We set the parameters as follows: λ

(1) 1 = 5, λ (2) 1 = 0.1, λ (1) 2 = 0.5, λ (2) 2 = 5, and µ (d) 1 = 7.5, µ (d) 2 = 9, for d = 1, 2. We take r k (2|1) = 0.001 • γ, r k (1|2) = 0.009 • γ, k = 1, 2,
and let γ vary from 1 up to 5000, in order to study the effect of the speed of the modulated environments. We then have φ 1 (1) = φ 2 (1) = 0.9, hence ρ ≈ 0.67. In Table 2.1 we show the average performance under the averaged Whittle index policy and that of the benchmark policy. We also show the performance under three other index policies: we consider the index policy

2 d=1 φ k (d)W (d) k (n),
which is the Whittle index averaged over the different environments, and we consider the index policy W (d) k (n) for d = 1, 2, which is the Whittle index in case the environment would be always in state d. We denote by g B the performance of the policy as defined in Section 2.5.2 and let g ϕ denote the average cost under policy ϕ. We define by Rel(ϕ) := g ϕ -g B g B * 100% the loss gap (in %). We observe that the averaged Whittle index policy W is 2.5% away from the benchmark policy for γ = 25, i.e., when the transition rates of the environment are r k (2|1) = 0.025 and r k (1|2) = 0.225. Hence, already for a normal scaled environment, the performance of the averaged Whittle index policy is very high. For slow speed, γ = 1, the averaged Whittle index policy is only 16% away from the benchmark policy. The index

policy 2 d=1 φ k (d)W (d) k (n)
gives slightly worse performance than that of W . For any speed of the environment, we observe that the index policy W k (n) gives very bad performance ranging between a loss gap of 30% until 53%. This can be explained from the fact that the environment is 90% of the time in state 1.

One common environment affecting the departure rates

We now consider one common environment D(t), which can be in two states {1, 2}, with transition rates r(d |d). This time, we let the arrival rates be independent of the environment. Instead, the state of the environment influences both the departure rate of class 1 and class 2.

λ (d) 1 = 0.6, λ (d) 2 = 1.2, for d = 1, 2, and µ (1)
1 = 4, µ (2)
1 = 0.5, µ (1)
2 = 0.1, µ (2)
2 = 6. We take r(2|1) = 0.004 • γ, r(1|2) = 0.006 • γ. We then have φ 1 (1) = φ 2 (1) = 0.6, hence ρ ≈ 0.72.

Note that for these parameters, λ

(2) 1 > µ (2) 1 and λ (1) 2 > µ (1) 2 . That is, if D(t) = 1, then class 2 is in overload, while if D(t) = 2,
then class 1 is in overload. In particular, this implies that the indices W (d) k (n) are not well-defined. We therefore only simulate the performance under the averaged Whittle index policy W . The results can be found in Table 2.2. We observe that the averaged Whittle index policy is 6.4% away from the benchmark policy when γ = 1000, i.e., r(2|1) = 4 and r(1|2) = 6. Hence, we observe that already for a normal scaled environment, the performance of the averaged Whittle index policy is very high. When γ = 2500, i.e., r(2|1) = 10 and r(1|2) = 15, the gap reduces to 0.8%. For γ = 500, i.e., r(2|1) = 2 and r(1|2) = 3, and smaller γ, the loss gap becomes significantly large. Example 3: In this example, we chose the parameters such that the departure rate of class 1 is always lower than that of class 2, in each environment. In addition, the departure rate for class 1 is considerably higher in environment 2 compared to its rate in environment 1.

The values for the parameters are: λ andµ (1)

(d) 1 = 1, λ (d) 2 = 3.5, for d = 1, 2,
1 = 1.5, µ (2) 1 = 10, µ (1) 2 = 12, µ (2) 2 = 11. We take r(2|1) = 0.002 • γ, r(1|2) = 0.008 • γ. We then have φ 1 (1) = φ 2 (1) = 0.8, hence ρ ≈ 0.61.
The results can be found in Table 2.3. We observe that the averaged Whittle index policy W is 7% away from the benchmark policy for γ = 5000, i.e., the transition rates of the environment are r k (2|1) = 10 and r k (1|2) = 40. For slow speed, γ = 1, the averaged Whittle index policy is 29% away from the benchmark policy. The index policy

2 d=1 φ k (d)W (d)
k (n) gives worse performance than that of W . For any speed of the environment, we observe that the index policy W [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF] k (n) outperforms the averaged Whittle index policy, while the index policy W [START_REF] Ahmad | Optimality of myopic sensing in multichannel opportunistic access[END_REF] k (n) gives very bad performance ranging between a loss gap of 32% until 21%. Again, this difference can be explained from the fact that the environment is 80% of the time in environment 1.

Observable environments

Until now, in the numerical examples, we observed that already for a rather normal speed of the environment, the averaged Whittle index policy works well. Hence, in case the decision maker aims for a policy that is robust without observing the environment, our heuristic seems to be a good choice.

We introduce now an analysis considering that the decision maker can observe the environments, as it will be studied in Chapter 3. For Example 3 we have calculated the performance under the optimal policy when the environment can be observed, and where decision epochs are moments when one of the bandits changes state, or the environment changes state. Note that for the observable setting, the stability condition strongly depends on the policy employed. Numerically, we derived that being able to observe the environment gives an improvement of 16% when γ = 1, and of 60% when γ = 5000. The large improvement, especially when γ = 5000, comes from the fact that the policy will schedule in an opportunistic manner. Recall that the departure rate of class 1 is much larger in environment 2 (compared to environment 1). Hence, in environment 2, an optimal policy will give more preference to class 1. However, in environment 1, class 2 has a much higher departure rate compared to class 1, hence, more priority will be given to class 2. Observing the environment, and being able to change the action when the environment changes, makes this large improvement in the performance possible.

Appendix

Proof of Lemma 2.1: For ease of notation, we remove the superscripts ϕ and N in the proof. For the random vector X N (t), we define the following Probability Generating Function (2.6.1) and the Moment Generating Function (2.6.2), conditioned on the environment vector d:

g ( d) ( z) := E z X 11 N 11 z X 21 N 21 . . . z X jk N jk . . . z X J K K N J K K 1 ( D= d) = x z x 11 N 11 z x 21 N 21 . . . z x jk N jk . . . z x J K K N J K K P X N = x, D = d , (2.6.1)
and

g( d) ( s) = g ( d) (e -s ) = E e -s X N 1 ( D= d) . (2.6.2)
The balance equations for the Markov process X(t) N , D(t) state that for each ( x, d), we have

P X N = x, D = d   d ∈Z K r( d | d) + k,a,i,j 1 N q (d k ) k (j|i, a)y a i,k ( x) • N   (2.6.3) = d ∈Z K r( d| d )P X N = x, D = d + k,a,j i/x i,k >0 j/x j,k <1 1 N q (d k ) k (i|j, a)y a j,k ( x + e j,k N - e i,k N ) • N • P X N = x + e j,k N - e i,k N , D = d .
Note that we have to restrict the sum on the rhs in order to consider the boundary cases. Multiplying (2.6.3) by z x11 11 . . . z

x J K K J K K , summing over x on both sides of the equality, we then obtain the following expression:

g ( d) ( z) d ∈Z K P ( d | d) + x z x11 11 . . . z x J K K J K K P X N = x, D = d k,a,i,j q (d k ) k (j|i, a)y a i,k ( x) (2.6.4) = d ∈Z K P ( d| d ) g ( d ) ( z) + x z x11 11 . . . z x J K K J K K k,a,j i/x i,k >0 j/x j,k <1 q (d k ) k (i|j, a)y a j,k ( x + e j,k N - e i,k N ) • P X N = x + e j,k N - e i,k N , D = d .
Below we will show that the second terms in both the LHS and the RHS of (2.6.4) are equal when taking limits. We begin rewriting the second term in the LHS. By changing variables z → e -s (since in the limit we have that X N is a continuous variable), we have that it is equal to

x e -s11x11 . . . e -s J K K x J K K k,a,i,j q (d k ) k (j|i, a)y a i,k ( x) • P X N = x, D = d .
(2.6.5)

We make the same change of variables in the second term in the RHS. Furthermore, the sums in k, a, i, j are bounded, because of the hypothesis (2.1.1), the fact that y a j,k (.) is a proportion and mathbbP is a probability. Thus, as a consequence of Fubini's theorem, we can interchange the order of summations:

k,a,i,j x/x i,k >0 x j,k <1 e -s11x11 . . . e -s J K K x J K K q (d k ) k (i|j, a) • y a j,k ( x + e j,k N - e i,k N ) • P X N = x + e j,k N - e i,k N , D = d .
For each fixed k, i and j, we also make the change of variables x → y

+ e i,k N - e j,k N , k,a,i,j y/y i,k <1 y j,k >0 e -s11y11 . . . e -s J K K y J K K e -k s i,k N e -k s j,k N • q (d k ) k (i|j, a)y a j,k ( y)P X N = y, D = d = y e -s11y11 . . . e -s J K K y J K K e -s i N e -s j N • k,a,j i/y i,k <1 j/y j,k >0 q (d k ) k (i|j, a)y a j,k ( y)P X N = y, D = d . (2.6.6)
Comparing (2.6.5) and (2.6.6) there are two aspects that remain different. The first one is the restriction of summing only when y j,k > 0 and y i,k < 1 in (2.6.6), but we can add the boundary cases which only sum 0: note that when y j,k = 0, there would be a y a j,k ( y) = 0 multiplying, and when y i,k = 1, as it's a proportion in class k bandits, this means that y j,k = 0 and again there would be a y a j,k ( y) = 0 multiplying. The second aspect is the factor e

-k s i,k N e -k s j,k N
, which converges to 1 as N → ∞. Since y a j,k ( x) ≤ 1, in the limit both terms are the same.

So we can conclude from (2.6.4) that lim obtained, which would prove our lemma. Hence, to use the results obtained in [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] we need to verify several the assumptions A0-A8 as made in that paper. We will do so below.

N →∞ g( d) ( s) d ∈Z K r( d | d) = d ∈Z K r( d| d ) lim N →∞ g( d ) ( s), ( 2
Each bandit represents a particle, and a transition of a class-k bandit/particle from state j to state i when in environment d occurs at rate 1 N

1 a=0 q (d) k (i|j, a)y ϕ,a j,k X(t) N , (2.6.8)
where y ϕ,a j,k

X(t) N
needs to be interpreted as the probability for a class-k bandit in state j to see action a.

Expression (2.6.8) is the equivalence of [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF]Equation (3)].

In [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] a discrete-time setting is considered. In the model we consider, the transition rates are uniformly bounded 1 , hence we can uniformise our system to obtain a discrete-time model [START_REF] Norris | Markov chains[END_REF]Section 2.6]. Furthermore, we consider a multi-class particle system, while the results in [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] are for an exchangeable system.

As noted in [17, page 38], this is easily generalized to a multi-class model, when adding a class description to the state of the bandit and having the class of the vector of bandits at time 0 be determined by an exchangeable random vector.

We are left with verifying Assumptions A0-A8 as stated in [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF]. Most of them are true by definition, except for A0 and A2, which we discuss in the remainder of the proof.

[A0.] states a weak correlation between the bandits' transitions. That is, let A n,k (t) denotes the event of the n-th class-k bandit to have a transition at time t. Then in A0 of [START_REF] Bordenave | A particle system in interaction with a rapidly varying environment: Mean field limits and applications[END_REF] it is assumed that P (A n1,k1 (t)A n2,k2 (t)) ≤ ρ(N )/N, with ρ(N ) → 0. For our model this is satisfied, since bandits behave independently from each other, hence this probability is equal to zero.

[A2.] states that the transition rates of the bandits are uniformly Lipschitz, using the total variation between two empirical measures. That is, there exists a constant C such that for every x, z,

sup j,k,d J k i=1 |q (d) k (i|j, 0)y ϕ,0 j,k ( x) + q (d) k (i|j, 1)y ϕ,1 j,k ( x) -q (d) k (i|j, 0)y ϕ,0 j,k ( z) -q (d) k (i|j, 1)y ϕ,1 j,k ( z)| ≤ C sup j,k |x j,k -z j,k |.
(2.6.9)

1 The transition rate out of state (

X, D) are i,k X j,k q (d) k (i|j, a)/N + d r( d | D) ≤ C 1 +max j,k i q (d) k (i|j, a) < C 1 +C 2 ,
where we use the assumption made on the environment in Section 2.1 and (2.1.1).

The LHS is equal to

sup j,k,d J k i=1 |q (d) k (i|j, 0) y ϕ,0 j,k ( x) -y ϕ,0 j,k ( z) + q (d) k (i|j, 1) y ϕ,1 j,k ( x) -y ϕ,1 j,k ( z) | ≤ sup j,k,d J k i=1 q (d) k (i|j, 0)|y ϕ,0 j,k ( x) -y ϕ,0 j,k ( z)| + q (d) k (i|j, 1)|y ϕ,1 j,k ( x) -y ϕ,1 j,k ( z)| ≤ C 2 sup j,k,d |y ϕ,0 j,k ( x) -y ϕ,0 j,k ( z)| + |y ϕ,1 j,k ( x) -y ϕ,1 j,k ( z)| ≤ C 2 sup j,k,d |x j,k -z j,k | + 2|y ϕ,1 j,k ( x) -y ϕ,1 j,k ( z)| ≤ C 2 (2C + 1) sup j,k |x j,k -z j,k |,
where we used (2.1.1) and (2.2.5). That is, (2.6.9) is satisfied. 2

Proof of Lemma 2.4: Let ϕ be a policy that satisfies Condition 2.3. We first prove that the feasible set of the (LP) problem is non-empty.

Note that we have relative compactness for the sequence of random variables X N,ϕ /N N ∈N

. In case J k < ∞ for every class k, this is valid because the random vectors live on a compact space. In case J k = ∞ for some k, relative compactness comes from Condition 2.3 and [15, Theorem 6.1]. As a consequence, we can consider a subsequence of N (for ease of notation still denoted as N ) such that X N,ϕ /N converges in distribution when N → ∞. Together with Condition 2.3 we can then define the following limiting point y := (y ϕ,a j,k ), where

y ϕ,a j,k := E lim N →∞ lim inf T →∞ 1 T T 0 y ϕ,a j,k X N,ϕ (t) N dt .
It is important to note that this limit can depend on the subsequence of N considered. For ease of notation, we are not writing this dependence. We will first prove that y ϕ is a feasible solution of the (LP) problem.

Since at most N bandits are in the system, we have lim t→∞ X N,ϕ j,k (t) t = 0, for all j, k.

(2.6.10)

Note that t 0 y ϕ,a j,k ( X N,ϕ (s) N )
• N ds is the total aggregated amount of time spent on action a on class-k bandits in state j during the interval (0, t]. Hence, we can write the following sample-path construction of the process X N,ϕ j,k (t):

X N,ϕ j,k (t) =X N,ϕ j,k (0) + 1 a=0 i =j d∈Z N q (d) k (j|i,a) N t 0 1 (D k (s)=d) y ϕ,a i,k X N,ϕ (s) N • N ds - 1 a=0 i =j d∈Z N q (d) k (i|j,a) N t 0 1 (D k (s)=d) y ϕ,a j,k X N,ϕ (s) N • N ds , (2.6.11)
where N q (d) k (j|i,a)/N (t) are independent Poisson processes having as rates q (d) k (j|i, a)/N , i, j = 1, . . . , J k , k = 1, . . . , K, a = 0, 1. By the ergodic theorem [START_REF] Çinlar | Introduction to Stochastic Processes[END_REF] and because of X N having an invariant distribution (see Condition 2.3, item a), we obtain that

1 t t 0 1 (D k (s)=d) y ϕ,a j,k ( X N,ϕ (s) N )•N ds converges to E 1 (D k =d) y ϕ,a j,k ( X N,ϕ N ) • N < ∞ as t → ∞, for all j, k, a, d, N . Because of Lemma 2.1 we further have lim N →∞ E 1 (D k =d) y ϕ,a j,k X N,ϕ N = φ k (d)y ϕ,a j,k .
(2.6.12)

Now, when dividing both sides in (2.6.11) by t, taking t → ∞, and using that N θ (at)/t → aθ and (2.6.10) hold, we obtain

0 = 1 a=0 J k i=1,i =j d∈Z q (d) k (j|i, a) N E 1 (D k =d) y ϕ,a i,k X N,ϕ N • N - 1 a=0 J k i=1,i =j d∈Z q (d) k (i|j, a) N E 1 (D k =d) y ϕ,a j,k X N,ϕ N • N = 1 a=0 J k i=1,i =j d∈Z q (d) k (j|i, a)E 1 (D k =d) y ϕ,a i,k X N,ϕ N - 1 a=0 J k i=1,i =j d∈Z q (d) k (i|j, a)E 1 (D k =d) y ϕ,a j,k X N,ϕ N .
(2.6.13)

Letting N → ∞, together with (2.6.12), we then obtain

0 = 1 a=0 J k i=1,i =j d∈Z q d k (j|i, a)φ k (d)y ϕ,a i,k - 1 a=0 J k i=0,i =j d∈Z q d k (i|j, a)φ k (d)y ϕ,a j,k , = 1 a=0 J k i=1,i =j q k (j|i, a)y ϕ,a i,k - 1 a=0 J k i=0,i =j q k (i|j, a)y ϕ,a j,k , (2.6.14)
a.s., that is, y ϕ satisfies Equation (2.2.6). By definition, y ϕ satisfies k,j y ϕ,1 j,k ≤ α and y ϕ,a j,k ≥ 0. Hence, y ϕ is a feasible solution of (LP). Note that the interchange of limit and summations to go from (2.6.13) to (2.6.14) is possible because of the uniform integrability given by Condition 2.3.

It is left to prove Inequality (2.2.10). We have, lim inf

N →∞ V N,ϕ - (x) = lim inf N →∞ lim inf T →∞ 1 T E   T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a) • y ϕ,a j,k X N,ϕ (t) N dt   ≥ E   lim inf N →∞ lim inf T →∞ 1 T T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a) • y ϕ,a j,k X N,ϕ (t) N dt   ,
where the inequality holds because of Fatou's Lemma. So it would be enough to prove that lim inf

N →∞ lim inf T →∞ 1 T T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a)y ϕ,a j,k ( X N,ϕ (t) N )dt ≥ v * , (2.6.15)
almost surely.

Consider a fixed realization ω of the process. We first assume that the LHS in (2.6.15) is finite. We then obtain that lim inf

N →∞ lim inf T →∞ 1 T T 0 y ϕ,a j,k X N,ϕ (t) N 1 (D k (t)=d) dt = lim inf N →∞ E 1 (D k =d) y ϕ,a j,k X N,ϕ N (2.6.16) = lim Ni→∞ E 1 (D k =d) y ϕ,a j,k X Ni,ϕ N i = E lim Ni→∞ 1 (D k =d) y ϕ,a j,k X Ni,ϕ N i = φ k (d)y ϕ,a j,k , (2.6.17)
with N i the subsequence corresponding to the liminf sequence and such that X N,ϕ N converges in distribution. In the third step we used that X N,ϕ /N is uniformly integrable and in the fourth step we used (2.6.12) (this equation holds for any weakly converging subsequence of X N,ϕ N ). As a consequence we obtain that lim inf

N →∞ lim inf T →∞ 1 T T 0 K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a)y ϕ,a j,k ( X N,ϕ (t) N )dt = K k=1 J k j=1 1 a=0 C (D k (t)) k (j, a) lim inf N →∞ lim inf T →∞ 1 T T 0 y ϕ,a j,k ( X N,ϕ (t) N )dt = K k=1 J k j=1 1 a=0 d∈Z C d k (j, a)φ k (d)y ϕ,a j,k = K k=1 J k j=1 1 a=0 C k (j, a)y ϕ,a j,k ≥ v * ,
where the last inequality holds because y is a feasible solution of the (LP) problem.

In particular, the above shows that v * < ∞, since we assumed in Section 2.1 that there exists a policy for which the LHS in (2.6.15) is finite.

Assume now that the LHS of (2.6.15) is infinite. Then inequality (2.6.15) follows directly, since v * < ∞.

This concludes the proof. 2

Proof of Lemma 2.6: We consider four possible cases:

(1) If α -(i,l)∈S ϕ k (j) x i,l < 0, then by definition (2.3.1) we have y prio,1 j,k

( x) = 0.
If as well α -(i,l)∈S ϕ k (j) z i,l < 0, then the LHS of (2.2.5) equals zero, hence (2.2.5) holds. If instead α -(i,l)∈S ϕ k (j) z i,l ≥ 0, then by definition (2.3.1),

|y prio,1 j,k ( x) -y prio,1 j,k ( z)| = min   α - (i,l)∈S prio k (j) z i,l , z j,k    ≤ α - (i,l)∈S prio k (j) z i,l < (i,l)∈S prio k (j) (z i,l -x i,l ) ≤ K k=1 J k sup i,l |x i,l -z i,l |.
In the remaining three cases, we can now assume that for both u = x, z, it holds that

  α - (i,l)∈S prio k (j) u i,l    ≥ 0. (2) If x j,k ≤ α -(i,l)∈S ϕ k (j) x i,l and z j,k ≤ α -(i,l)∈S prio k (j) z i,l , then we obtain directly the result |y prio,1 j,k ( x) -y prio,1 j,k ( z)| = |x j,k -z j,k | ≤ sup i,l |x i,l -z i,l |. (3) If x j,k ≤ α -(i,l)∈S prio k (j) x i,l and z j,k ≥ α -(i,l)∈S prio k (j) z i,l , then |y prio,1 j,k ( x) -y prio,1 j,k ( z)| = x j,k -α + (i,l)∈S prio k (j) z i,l .
(2.6.18)

If, in addition,

x j,k > α -(i,l)∈S prio k (j) z i,l , then since x j,k ≤ α -(i,l)∈S prio k (j) x i,l , we have |y prio,1 j,k ( x) -y prio,1 j,k ( z)| = x j,k -α + (i,l)∈S prio k (j) z i,l ≤ (i,l)∈S prio k (j) (z i,l -x i,l ) ≤ K k=1 J k sup i,l |x i,l -z i,l |, since K k=1 J k is the number of states (i, l) bandits can be in. Instead, if x j,k ≤ α -(i,l)∈S prio k (j) z i,l , then |y prio,1 j,k ( x) -y prio,1 j,k ( z)| = α - (i,l)∈S prio k (j) z i,l -x j,k ≤ z j,k -x j,k ≤ sup i,l |x i,l -z i,l |. (4) If x j,k ≥ α -(i,l)∈S prio k (j) x i,l and z j,k ≥ α -(i,l)∈S prio k (j) z i,l , then |y prio,1 j,k ( x) -y prio,1 j,k ( z)| = (i,l)∈S prio k (j) (z i,l -x i,l ) ≤ K k=1 J k sup i,l |x i,l -z i,l |. Setting C = K k=1 J k , we proved (2.2.5). 2
Chapter 3 In this chapter we study an optimisation problem with controllable processes affected by observable environments. We consider a multi-armed restless bandit problem, where each bandit is formed by two processes, a controllable process and an environment. Thus, the state descriptor of the bandits is two-dimensional.

Optimal control with observable environments

The decision maker has full information of the state the controllable process and the environment are in.

We further consider the particular case of queues with abandonments under linear holding costs, where impatient customers can leave the system, regardless of whether they are being served or not. There, the state of the queue is the controllable process, and the arrival rates, service rates, and abandonment rates depend on the state of an exogenous environment process.

In our first main contribution, we consider an arbitrary bandit, and under the assumption that the optimal policy is of threshold type, we provide an algorithm that finds Whittle's index in any state. In the case the environment changes at a slower time scale than the controllable process, we derive an analytical expression for Whittle's index. For the problem of a multi-class abandonment queue, we show that threshold policies are optimal. We prove indexability and obtain closed-form expressions for Whittle's index. These are further simplified in case the environments vary slowly, and when they vary fast. We further propose a heuristic for a multi-class queue without abandonments, derived from the results for the problem with abandonments. By numerical simulations, we assess the suboptimality of Whittle's index policy in a wide variety of scenarios, and the general observation is that, as in the case of standard MARBPs, the suboptimality gap of Whittle's index policy is small. Numerically, we also assess the performance of the averaged Whittle index policy.

The latter was proved to be asymptotically optimal for unobservable environments, see Chapter 2, but we show that it can be far from optimal in the observable setting.

Most of the references in MARBP consider unidimensional bandits, which is a critical assumption in order to establish indexability, and in turn to calculate Whittle's index. On the other hand, literature on multidimensional MARBPs, as considered here, is scarce. The main difficulty lies in establishing indexability, i.e., ordering the states, in a multidimensional space. Important exceptions are [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Anand | A Whittle's index based approach for QoE optimization in wireless networks[END_REF], as we described in Section 1.1.2.

The multi-class abandonment queue has been largely studied in recent literature, see for example the Special Issue in Queuing Systems on queuing systems with abandonments [START_REF]Special Issue on Queueing Systems with Abandonments[END_REF] and the survey [START_REF] Dai | Many-server queues with customer abandonment: A survey of diffusion and fluid approximations[END_REF] in the manyserver settings. In particular, we mention the work of [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF], where the authors formulate the abandonment queue as an MARBP and derive a closed-form expression for Whittle's index. In this chapter, we extend this work by considering the abandonment queue with rates that depend on environments.

The chapter is organised as follows. In Section 3.1 we describe the model. In Section 3.2 we present the relaxation of the original problem and Whittle's index. In Section 3.3 we introduce the threshold policies and, assuming they are optimal, we provide the algorithm to determine Whittle's index. We establish an analytical solution of Whittle's index when the dynamics of the environment are much slower than the controllable process. In Section 3.4 we study the multi-class queue with abandonments. Optimality of threshold policies is proved in Section 3.4.1. In Section 3.4.2 we prove indexability and obtain expressions for Whittle's index. The proofs of the theorems are in Section 3.4.3. In Section 3.5 we derive Whittle's index for a multi-class queue without abandonments living in a Markov-modulated environment. Finally, in Section 3.6 we numerically evaluate the performance of Whittle's index policy. For ease of the reading, many proofs are presented in the appendix.

Model description

We consider a multi-armed restless bandit problem in continuous time. There are N bandits in the system, each bandit is composed by a controllable process and an environment process. The controllable process lives in the state space X = {0, 1, . . .}. A bandit can be kept passive or made active, with the constraint that at most R bandits can be made active at a time, R ∈ N. The transition rates of the controllable process of a bandit depend on whether it is made active or kept passive and on the current state of the environment, as defined below.

The We note that no further assumptions are made on the correlation between different environments. However, in the numerical examples, we focus on the following two special cases:

• Independent environments: The variables (D k (t)) N k=1 are independently distributed. As a consequence, given the action, the evolution of the two-dimensional state of a bandit, (M k (t), D k (t)), is independent of the others. Hence, this setting falls within the classical MARBP with a 2-dimensional state space.

• Common environment: There is only one environment affecting all bandits, that is, D 1 (t) = . . . = D N (t) = D(t). When environment D(t) changes state from d to d , it changes the transition rates of all bandits at once. In this case there is a correlation between bandits, which does not fit in the standard MARBP model.

Let ϕ denote the policy that determines the action taken for each bandit. We assume that policies are Markovian, that is, they can base their decisions only on the current state of the bandits. In particular, this implies that decisions can depend on the state the environments are in. That is, the decision maker can observe the environments.

For a given policy ϕ, let M ϕ k (t) = m ∈ X denote the state of the controllable process of bandit k at time t, k = 1, . . . , N . Note that (M ϕ k (t), D k (t)) describes the two-dimensional state of bandit k. The full description

(M ϕ 1 (t), D 1 (t), . . . , M ϕ N (t), D N (t)) ,
is then a Markov process.

We denote the passive action by a = 0 and the active action by a = 1. We further denote by A ϕ k (t) ∈ {0, 1} the action taken for bandit k at time t under policy ϕ, and A ϕ (t) := (A ϕ 1 (t), . . . , A ϕ N (t)) the actions taken for all the bandits. The constraint can be expressed as

N k=1 A ϕ k (t) ≤ R, ∀t ≥ 0. (3.1.1)
We define the set of feasible policies Φ, as the set of all Markovian policies that satisfy (3.1.1).

When action a is applied to bandit k, it makes a transition from state (m, d) to state (m , d) at rate d,a) denote the cost per unit of time for bandit k when the controllable process is in state m, the environment is in state d and the action taken is a. For any k, we assume that

q k (m |m, d, a). Let C k (m,
C k (m, d, a)
is a convex non-decreasing function in m for any d, a.

The objective of the optimisation problem is to find the policy ϕ that minimises the long-run average holding cost under constraint (3.1.1), i.e., solve:

min ϕ∈Φ lim sup T →∞ 1 T E T 0 N k=1 C k (M ϕ k (t), D k (t), A ϕ k (t))dt . (3.1.2)
Finding a solution for the constrained problem (3.1.2) is PSPACE-hard, hence infeasible, see [START_REF] Gittins | Multi-Armed Bandit Allocation Indices[END_REF][START_REF] Mahajan | Multi-Armed Bandit Problems[END_REF][START_REF] Whittle | Optimal Control, Basics and Beyond[END_REF].

However, we refer to the Lagrangian relaxation method, as we introduced in Section 1.2.4, that allows to obtain efficient index policies for the original problem. In Section 3.2 this is applied to the MARBP with observable environments.

Relaxation and Whittle's index policy

In this section, we introduce the relaxed version of the Markov-modulated multi-armed restless bandit problem. The main idea of this methodology, as proposed by Whittle in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF], is to solve an unconstrained problem obtained via a Lagrangian relaxation approach, instead of solving problem (3.1.2) under constraint (3.1.1). This leads to a significant simplification of the problem, where the multi-dimensional setting can be replaced by a a one-dimensional setting. The solution for the relaxed problem can be then described by the Whittle's index.

We now study the relaxed problem, that is, the constraint on the number of active bandits must be satisfied on average, and not in every decision epoch:

lim sup T →∞ 1 T E T 0 N k=1 A ϕ k (t)dt ≤ R. (3.2.1)
We denote the set of policies satisfying constraint (3.2.1) by Φ REL , and we note that Φ ⊆ Φ REL . We now consider the problem of finding a policy ϕ that minimises (3.1.2) under constraint (3.2.1). We use the Lagrangian multipliers approach to rewrite the following unconstrained version of the relaxed problem:

min ϕ lim sup T →∞ 1 T E T 0 N k=1 C k (M ϕ k (t), D k (t), A ϕ k (t)) -W N k=0 A ϕ k (t) dt . ( 3.2.2)
The Lagrange multiplier W can be viewed as a subsidy for making each bandit passive. The key observation made by Whittle is that problem (3.2.2) can be decomposed in N subproblems, one for each bandit, due to the fact that there is no longer a common constraint. Thus, the solution to (3.2.2) is obtained by combining the solution to N separate optimisation problems, that is,

min ϕ lim sup T →∞ 1 T E T 0 (C k (M ϕ k (t), D k (t), A ϕ k (t)) -W A ϕ k (t)) dt , ( 3.2.3)
for each bandit k. Under ergodicity conditions, we define g ϕ k (W ) as

g ϕ k (W ) := E (C k (M ϕ , D k , A ϕ k )) -W E (A ϕ k ) , (3.2.4)
where M ϕ k , D k , A ϕ k are the respective steady-state variables for a given bandit under policy ϕ. Then, problem (3.2.3) is equivalent to the problem min ϕ g ϕ k (W ). We now introduce the indexability notion. Let P k (W ) ⊂ X × Z denote the set of states (m, d) in which it is optimal to be passive when the subsidy for passivity is

W . A bandit is called indexable if P k (W ) increases in W . Definition 3.1. Bandit k is indexable if W < W implies P k (W ) ⊆ P k (W ).
In other words, if for W = W 0 it is optimal to be passive in state (m, d), it is also optimal to be passive for any value for the subsidy W ≥ W 0 . The Whittle's index in state (m, d) is now defined as follows: it is the smallest value for the subsidy such that it is optimal to be passive in that state.

Definition 3.2. When bandit k is indexable, the Whittle's index in state

(m, d) is defined by W k (m, d) := inf {W : (m, d) ∈ P k (W )}.
We can now give an optimal solution to the relaxed control problem (3.2.2) for a given W . At any moment in time t, make active all bandits whose current Whittle's index exceeds the subsidy for passivity, i.e.,

W k (M k (t), D k (t)) > W .
A standard Lagrangian argument together with the fact that the cost functions C k are convex non-decreasing, gives that there exists a multiplier W such that constraint (3.2.1) is satisfied.

Since the solution to the relaxed optimisation problem will in general not be feasible for the original problem (3.1.2) with constraint (3.1.1), Whittle proposed a heuristic also based on the Whittle's index. We will refer to this policy as Whittle's index policy. Definition 3.3 (Whittle's index policy). At time t, the Whittle's index policy prescribes to make active the R bandits having currently the largest value for their Whittle'

s index W k (M k (t), D k (t)).

Calculation of Whittle's index

In this section we present our main results for the general model. In Section 3.3.1, we provide an algorithm to calculate the Whittle's index, and in Section 3.3.2, we obtain Whittle's index when the environment changes very slowly compared to the state of the controllable process.

Since we focus on the relaxed problem for one bandit (3.2.3), we omit the dependence on k for ease of notation throughout this section.

Threshold policies

We assume throughout the chapter that threshold policies (defined below) are an optimal solution of (3.2.3). This is typically the case in many queueing models. For the case study of an abandonment queue, we prove it to hold in Section 3.4.1. In this section, we further assume the bandit is indexable, as defined in Definition Alternatively, for some problems, an appropriate definition of threshold policy is to activate the bandit if and only if the controllable process is below a threshold. The analysis of both cases is similar, and we choose the former case in our presentation. See [45, Section 3.2] for a case where both types of threshold policies are considered.

In order to obtain Whittle's index, one needs to find the optimal threshold policies for any value of W .

First recall that the average cost (see (3.2.4)) under a threshold policy n is given by

g n (W ) := d∈Z ∞ m=0 C (m, d, a) π n (m, d) -W d∈Z n d m=0 π n (m, d). (3.3.1)
Since we assumed that an optimal solution is of threshold type, the optimal average cost can be written as

g(W ) := min n g n (W ).
In Figure 3.1, the function g(W ) and the functions g n (W ) are plotted. Note that for any n, g n (W ) is a non-increasing linear function in W whose slope is determined by -d∈Z n d m=0 π n (m, d), and g(W ) is a lower envelope of the functions g n (W ). In particular, one observes that the horizontal axis can be split in intervals, where in each interval a different threshold policy is optimal. To find these intervals, note that for W = -∞ the threshold policy n -1 := (-1, -1, . . .) is optimal. Now one can simply look to the first value of the subsidy, Ŵ0 , where a linear function g n (W ) crosses g (-1,-1,...) (W ), and is optimal for W ∈ [ Ŵ0 , Ŵ1 ].

Let n 0 be the corresponding threshold policy of this linear function. Then, one knows that Whittle's index is given by W (m, d) = Ŵ0 , for m = 0, . . . , n 0 d for all d such that n d 0 ≥ 0, since Ŵ0 is the smallest value such that it is optimal to be passive in those states. This happens because threshold policy (-1, -1, . . .) is optimal for W ≤ Ŵ0 and n 0 is optimal for W ∈ [ Ŵ0 , Ŵ1 ], with Ŵ1 still unknown. Similarly, one can now determine Ŵ1 , and find the optimal threshold policy in the point Ŵ1 , and as such, the Whittle index for states (m, d), with n 0 d < m ≤ n 1 d . To formalize the above procedure, we introduce notation for the crossing points of the linear functions g n (W ). We denote by W ( n, n ) := W ∈ R g n (W ) = g n (W ) , the set of multipliers W such that the expected cost under threshold policies n and n is equal. In case the slopes are not equal, i.e., d∈Z

n d m=0 π n (m, d) = d∈Z n d m=0 π n (m, d), the set W ( n, n
) has a unique element, which from (3.3.1) is given by:

W ( n, n ) = d∈Z ∞ m=0 C (m, d, a) π n (m, d) -d∈Z ∞ m=0 C (m, d, a) π n (m, d) d∈Z n d m=0 π n (m, d) -d∈Z n d m=0 π n (m, d) . (3.3.2)
Note that in case there are two threshold policies that, besides (-1, -1, . . .), are optimal in Ŵ0 , g n ( Ŵ0 ) =

g n ( Ŵ0 ), then the one having the steepest slope will be the one that minimises when W = Ŵ0 + ∆, with ∆ small enough, hence, we choose that one in the case of a tie.

In Algorithm 3.4 we summarise the above. Under the assumption of threshold optimality and indexability, the output of Algorithm 3.4 are the threshold policies n that optimizes (3.2.3) for each W , and Whittle's index.

Algorithm 3.4. Define n -1 the vector equal to -1 in every coordinate, that is, under policy n -1 the bandit is active in all environments. Then, for j ≥ 0,

Step j Let

E j = { n : d∈Z n d m=0 π n (m, d) = d∈Z n j-1 d m=0 π n j-1 (m, d) and n d ≥ n j-1 d , ∀d},
and compute

Ŵj = inf n∈Ej W ( n, n j-1 ) (3.3.3) Ŵ0 Ŵ1 Ŵ2 Ŵ3 W g n (W ) (-1, -1, ..) (n 0 1 , n 0 2 , ..) (n 1 1 , n 1 2 , ..) (n 2 1 , n 2 2 , ..) (∞, ∞, ..)
g(W )

Slowly changing environment

In this section, we give an analytical solution of Whittle's index when the environment changes at a much slower time scale than the dynamics of the controllable process of the bandit. We show that in the limit, the Whittle index in state (m, d) coincides with the Whittle index of a bandit that only sees environment d.

Before giving the results, we introduce some notation for a bandit that always sees environment d. That is, the bandit lives in the state space X = {0, 1, . . .} and its transition rates are q(m |m, a) := q(m |m, d, a) for m, m ∈ X and a = 0, 1. Let (p n d ,(d) (m)) d∈Z denote the corresponding steady-state probability under threshold policy n d . We further let W (d) (m) be the Whittle's index in state m of a bandit that always sees environment d.

The different time scales are obtained by scaling the transition rates of the environment by β: βr (dd ) , and taking the limit β → 0. In order to obtain an analytical expression for Whittle's index in the slow regime, we will assume the environment can be in two states, i.e., |Z| = 2. Whether the results extend to |Z| > 2 is left as further research.

When the environment changes state at a much slower time scale than the controllable process, the conditional (on the environment) steady-state behaviour of the bandit is that of a bandit whose environment never changes. This is stated formally below. The proof can be found in Appendix 3.7.1. Lemma 3.6. Assume |Z| = Z < ∞ and let the transitions of the environment be scaled by β, i.e., βr (dd ) . Then it holds that

lim β→0 π n (m, d) = φ(d)p n d ,(d) (m), ∀m ∈ N 0 . (3.3.4)
The following lemma states that in the slow regime, the index value given by Algorithm 3.4 can be found by changing the threshold value in only one of the two environments. For a given β, we denote by n j (β) = (n j 1 (β), n j 2 (β)) the values of n j as defined in Algorithm 3.4. The proof can be found in Appendix 3.7.1.

Lemma 3.7. Let |Z| = 2 and the transitions of the environment be scaled by β, βr (dd ) . Assume (n j 1 , nj 2 ) := lim β→0 (n j 1 (β), n j 2 (β)) exists, for all j, and that the family {M n , β} is uniform integrable, for any threshold policy n. Then,

lim β→0 inf n∈Ej 2 d=1 ∞ m=0 C (m, d, a) π n (m, d) - 2 d=1 ∞ m=0 C (m, d, a) π n j-1 (β) (m, d) 2 d=1 n d m=0 π n (m, d) - 2 d=1 n j-1 d (β) m=0 π n j-1 (β) (m, d) (3.3.5) = min d=1,2 inf n>n j-1 d ∞ m=0 C (m, d, a) p n,(d) (m) - ∞ m=0 C (m, d, a) p nj-1 d ,(d) (m) n m=0 p n,(d) (m) - nj-1 d m=0 p nj-1 d ,(d) (m) (3.3.6) = ∞ m=0 C (m, d 0 , a) p nj d 0 ,(d0) (m) - ∞ m=0 C (m, d 0 , a) p nj-1 d 0 ,(d0) (m) nj d 0 m=0 p nj d 0 ,(d0) (m) - nj-1 d 0 m=0 p nj-1 d 0 ,(d0) (m) , ( 3.3.7)
where d 0 is such that nj d0 = nj-1 d0 (there is at least one such d 0 ).

The following proposition states that in the slow regime the index W (m, d) converges to the index for a fixed environment d, W (d) (m).

Proposition 3.8. Let |Z| = 2 and the transitions of the environment be scaled by β, βr (dd ) . Under the assumptions of Lemma 3.7, we have that for any m, d,

lim β→0 W (m, d) = W (d) (m).
The uniform integrability property needs to be checked case by case. For the abandonment queue, as studied in Section 3.4, we give an alternative proof for the above, which does not require to verify uniform integrability, see Proposition 3.19.

Proof of Proposition 3.8:

The index W (m 0 , d 0 ) is as obtained from the Algorithm 3.4, through the values n j d (β). Since we assume that the limit of n j d (β) exists and lives on N, we have n j d (β) = nj d for β small enough. Hence, we can choose j such that n j-1 d0 (β) < m 0 ≤ n j d0 (β) and we have

lim β→0 W (m 0 , d 0 ) = lim β→0 inf n∈Ej 2 d=1 ∞ m=0 C (m, d, a) π n (m, d) - 2 d=1 ∞ m=0 C (m, d, a) π n j-1 (β) (m, d) 2 d=1 n d m=0 π n (m, d) - 2 d=1 n j-1 d (β) m=0 π n j-1 (β) (m, d) .
For d 0 it holds that nj d0 = nj-1 d0 . Hence, by Lemma 3.7, the latter is equal to

lim β→0 W (m 0 , d 0 ) = inf n>n j-1 d 0 ∞ m=0 C (m, d 0 , a) p n,(d0) (m) - ∞ m=0 C (m, d 0 , a) p nj-1 d 0 ,(d0) (m) n m=0 p n,(d0) (m) - nj-1 d 0 m=0 p nj-1 d 0 ,(d0) (m) . (3.3.8)
The latter is the Whittle index of a bandit that always sees environment d 0 , W (d0) (m 0 ). This follows by applying Algorithm 3.4 to the bandit that always sees environment d 0 . This concludes the proof. 2

Asymptotic optimality of Whittle's index policy

In [START_REF] Weber | On an index policy for restless bandits[END_REF], the authors considered the standard MARBP model (i.e., no environments) and proved that Whittle's index policy is optimal as the number of bandits and the number of active bandits, R, scale proportionally. This results holds for the standard MARBP setting and requires a so-called global attractor property to be satisfied for the corresponding deterministic set of differential equations.

In the case of independently distributed environments, the state (m, d) is a two-dimensional state of a classical bandit. Hence, Whittle's index policy is then also asymptotically optimal. The result does not directly carry over to correlated environments. This is left as future research.

Abandonment queue in a Markovian environment

In this section we study a multi-class queue with abandonments living in an observable environment. There are N classes of jobs. Each class is associated an environment process D k (t) that can be either in state 1 or state 2. For ease of notation, we define r ,d,a) denote the cost per unit of time for holding m class-k jobs in the system when the environment is in state d and action a is taken. We assume that the cost function satisfies

C k (m, d, 0) -C k ((m -1) + , d, 0) ≤ C k (m + 1, d, 1) -C k (m, d, 1) ≤ C k (m + 1, d, 0) -C k (m, d, 0), (3.4.1)
for all m, d, such that m ≥ 0. This property is directly implied, for example, when (i)

C k (m, d, a) = C k (m, d), or when (ii) C k (m, d, a) = C k ((m -a) + , d).
Here, (i) represents holding cost of jobs in the system and case (ii) represents holding costs of jobs waiting for service in the queue.

The objective is to minimize the time-average holding cost, see (3.1.2).

Similar to [START_REF] Larrañaga | Index Policies for multi-class queues with convex holding cost and abandonments[END_REF], we can cast this abandonment model into a Markov-modulated MARBP. There are N bandits, where each bandit represents a class of jobs. The state of bandit k is simply the number of class-k jobs in the system. We then have the following transition rates for bandit k:

q k (m + 1|m, d, a) = λ (d) k and q k ((m -1) + |m, d, a) = mθ (d) k + aµ (d) ,
for m ∈ N 0 , d = 1, 2 and a = 0, 1. Activating a bandit is equivalent to serving this class. At most R < N classes can be served at a time.

In the remainder of this section, we calculate Whittle's index for one class/bandit. In order to use Algorithm 3.4, we first show in Section 3.4.1 that an optimal solution of the relaxed problem is of threshold type.

Then, in Section 3.4.2, we obtain a closed-form expression for Whittle's index in the case of linear holding cost.

Threshold policies

In this section, we prove that an optimal solution of the relaxed problem (3.2.3) for the abandonment model is of threshold type. We henceforth focus on one bandit. For ease of exposition, we remove the subscript k. Proposition 3.9. For each W , there exists an n(W ) = (n 1 (W ), n 2 (W )) such that the threshold policy n(W ) is an optimal solution of the relaxed problem (3.2.3).

Proof:

The value function V (m, d) satisfies the Bellman's optimality equation for average costs [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], which in this case is

(µ (d) + mθ (d) + λ (d) + r (d) )V (m, d) + g = λ (d) V (m + 1, d) + mθ (d) V ((m -1) + , d) + r (d) V (m, 3 -d) (3.4.2) + min C(m, d, 0) -W + µ (d) V (m, d), C(m, d, 1) + µ (d) V ((m -1) + , d) ,
where g is the averaged cost incurred under the optimal policy. Proving optimality of a threshold policy is equivalent to proving that if in state m + 1 (with m ≥ 0) it is optimal to be passive, it is also optimal to be passive in state m. Regarding (3.4.2), we have to show that

C(m + 1, d, 0) -W + µ (d) V (m + 1, d) ≤ C(m + 1, d, 1) + µ (d) V (m, d) implies that C(m, d, 0) -W + µ (d) V (m, d) ≤ C(m, d, 1) + µ (d) V ((m -1) + ,

d).

A sufficient condition to prove this is Property (3.4.1) together with convexity of the value function for each d, m, so 2V (m, d) ≤ V (m + 1, d) + V ((m -1) + , d), which we prove next. In order to prove the convexity of V (m, d), we use the value iteration method. However, this technique needs uniformly bounded transition rates. We therefore consider a truncated space at L and smooth the arrival transitions. We define the value function for the truncated system with parameter L as V L (m, d). In Appendix 3.7.2 we show that V L (m, d) is a convex function, and in Appendix 3.7.2 that sufficient conditions hold in order to apply [14, Theorem 3.1], to state convergence of

V L → V as L → ∞. With these two results, convexity of V is concluded. 2
Below we prove properties on π n (m, d), the steady-state probability of having m jobs in the system and being in environment d under threshold policy n.

Given threshold policy n with n i ≥ 0 for i = 1, 2, we have the following rate conservation property for a given environment.

Lemma 3.10. Under threshold policy n it holds that

λ (d) φ(d) + r (3-d) E M n 1 (D=3-d) = θ (d) + r (d) E M n 1 (D=d) + µ (d) ∞ m=n d +1
π n (m, d), (3.4.3) for d = 1, 2, where M n denotes the random variable with distribution π n .

Proof:

The rate conservation in a stable system is due to the balance between the arrivals and the departures in the long-term process. We refer to [START_REF] Brill | Level crossing methods in stochastic models[END_REF]Section 2.4.7], where the Principle of Set Balance states that almost surely, the number of exits equals the number of entrances as t tends to infinity. We consider that each environment defines a stable subsystem. Then, the mentioned balance is represented in both sides of Equation (3.4.3) for a given environment d. This can be explained as follows. On average, the rate for arrivals under environment d is λ (d) φ(d), the rate for departures due to service is µ (d) ∞ m=n d +1 π n (m, d), and due to abandonments is θ (d) E M n 1 (D=d) . When the environment of the bandit is in state D(t) = d, the subsystem in environment d has all the customers, while the subsystem in environment 3 -d is empty.

When the environment changes state, a batch departure of every customer is done from one subsystem to the other. In this sense, for a fixed environment d, the term r (3-d)

The function

n d m=0 π n (m, d) is non-decreasing in n d , for d = 1, 2.

The function

n d m=0 π n (m, d) is non-increasing in n 3-d , for d = 1, 2.
The first property follows naturally, as increasing the threshold n d implies that one is keeping this class passive in more states, while the drift towards these passive states remains the same. Hence, the probability of being passive increases. If instead n 3-d increases, the states where the bandit is passive in environment d are the same. However, the downward drift in environment 3 -d decreases in some states, which explains that the probability of being passive in environment d decreases, i.e., the second property. The proofs can be found in Appendix 3.7.3.

Whittle's index for linear cost

In this section, we assume linear holding cost, that is, C(m, d, a) = cm, with c ∈ R =0 . We first prove that the abandonment problem is indexable, and then give an expression for Whittle's index. For ease of reading, the proofs of the theorems are in Section 3.4.3.

We introduce the following notation:

W (d) := cµ (d)
θ (3-d) + r (1) + r (2) θ (1) θ (2) + r (1) θ (2) + r (2) θ (1) .

(3.4.4)

The following two conditions are used in order to prove indexability, Theorem 3.14. Numerical simulations however suggest that indexability holds for any set of parameters.

Condition 3.12.

µ (1) ≤ µ (2) and θ (1) ≥ θ (2) . Condition 3.13.

W (2) ≤ cµ (2) θ (2) + r (2) . Theorem 3.14. Assume Conditions 3.12 and 3.13 hold. Then all bandits are indexable.

A closed-form expression for the Whittle's index W (m, d) can now be given. Theorem 3.15. Assume the bandit is indexable, and w.l.o.g., that µ (1) θ (1) + r (1) + r (2) ≤ µ (2) θ (2) + r (1) + r (2) . We define the subsequence (n j ) j≥-1 as follows: n -1 = -1, n 0 = 0, and for j ≥ 1 let

n j := min n>nj-1 W ((n j-1 , 0), (n, 0)).
(3.4.5)

In case there is more than one minimiser, choose the one that minimises -

2 d=1 n d m=0 π (n,0) (m, d). Whittle's index W (m, d) is given by W (m, d) =          0 for m = 0 W ((n j-1 , 0), (n j , 0))
for n j-1 < m ≤ n j , and d = 1

W (2)
for m ≥ 1 and d = 2.

(3.4.6)

Moreover, W (m, 1) ≤ W (1) ≤ W (2) for all m.

If µ (1) θ (1) + r (1) + r (2) = µ (2) θ (2) + r (1) + r (2) , then W (m, 1) = W (1) = W (2) for all m. Remark 3.16. If µ (1) -µ (2) < θ (2) , then the slope of the linear function g (n,0) , -

2 d=1 n d m=0 π (n,0) (m, d),
is a non-increasing sequence in n, as it will be stated in Proposition 3.23. As a consequence, in that case, for each step j in Theorem 3.15, the minimiser n j with the steepest slope is the largest minimiser n.

In the following corollary we consider the particular case where n j = j for all j ≥ -1, or equivalently, the sequence W ((n -1, 0), (n, 0)) is strictly increasing in n. Corollary 3.17. If µ (1) θ (1) + r (1) + r (2) ≤ µ (2) θ (2) + r (1) + r (2) and the sequence (W ((n -1, 0), (n, 0))) n∈N is strictly increasing in n, then Whittle's index W (m, d) is given by (3.4.7).

W (m, d) =          0 for m = 0 W ((m -1, 0), (m, 0)) for d = 1 W (2)
for d = 2 and m ≥ 1.

(3.4.7)

Although we could not prove the non-decreasing property for the crossing points, based on numerical observations we believe this holds whenever W (1) = W (2) .

Remark 3.18. The queuing model with abandonments without an environment has been studied in [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF]. That is, λ (1) = λ (2) = λ, µ (1) = µ (2) = µ and θ (1) = θ (2) = θ. Then, Whittle's index as in Theorem 3.15 equals cµ/θ, which is in agreement with [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF]Section 6.1].

We now scale the transition rates of the environments, to further characterize Whittle's index in the two extreme cases of very slow changing or very fast changing environments. As in Section 3.3.2, β is the scaling parameter and βr (d) is the transition rate of the environment. This proof can be found in Appendix 3.7.4.

Proposition 3.19. Assume the transition rates of the environment are scaled as βr (d) . It holds that

lim β→0 W (m, d) = c µ (d) θ (d) , ∀m, d.
When µ (1) θ (1) + r (1) + r (2) ≤ µ (2) θ (2) + r (1) + r (2) , it holds that

lim β→∞ W (m, d) =            0 for m = 0 lim β→∞ W ((n j-1 , 0), (n j , 0)) for n j-1 < m ≤ n j , and d = 1 c µ (2) θ for d = 2,
where θ := 2 d=1 φ(d)θ (d) .

For the slow regime, we observe that the Whittle Index W (m, d) coincides with that of the Whittle's index when the bandit always sees environment d, given by cµ (d) θ (d) , see [START_REF] Larrañaga | Index Policies for multi-class queues with convex holding cost and abandonments[END_REF]. When the environment changes fast compared to the controllable state of the bandit, the Whittle index remains state dependent. In environment 2, the index simplifies to c µ (2) θ . This index is very similar to (i) c µ θ , which is Whittle's index when there are no environments.

(ii) c µ θ , an index that was proved to be asymptotically optimal in case the environments are unobservable, in Chapter 2.

Hence, we see that when the environment changes very fast, it takes the form of departure rate over the averaged abandonment rate. In case the environment is unobservable, the averaged value is taken in the index.

Proof of Theorems 3.14 and 3.15

In this section, we set out the proofs of Theorems 3.14 and 3.15. In order to do so, we state several lemmas and propositions, whose proofs can be found in Appendix 3.7.5.

Throughout this section, we assume that W (1) ≤ W (2) , or equivalently µ (1) θ (1) +r (1) +r (2) ≤ µ (2) θ (2) +r (1) +r [START_REF] Ahmad | Optimality of myopic sensing in multichannel opportunistic access[END_REF] . We start by rewriting W ( n, n ), the subsidy such that the expected cost under both threshold policies n and n are equal. From (3.3.2), we obtain

W ( n, n ) = c • 2 d=1 ∞ m=0 mπ n (m, d) - 2 d=1 ∞ m=0 mπ n (m, d) 2 d=1 n d m=0 π n (m, d) - 2 d=1 n d m=0 π n (m, d) , (3.4.8)
given that the denominator in (3.4.8) is not equal to 0.

The rate conservation property of Lemma 3.10 allows us to give an alternative expression for W ( n, n ). For that, we define

s d ( n, n ) := n d m=0 π n (m, d) - n d m=0 π n (m, d),
as the difference between the probability of being passive under threshold policies n and n , while the environment is in state d.

Lemma 3.20. It holds that W ( n, n ) = tW (1) + (1 -t)W (2) , (3.4.9)

where t := s 1 ( n, n ) s 1 ( n, n ) + s 2 ( n, n ) .
Consider two policies that are always passive in environment d = 1, i.e., n = (∞, n 2 ) and n = (∞, n 2 ), for any pair n 2 , n 2 . We have that 1), where φ( 1) is the stationary measure of the environment for being in state d = 1. Hence, (2) .

∞ m=0 π (∞,n2) (m, 1) = φ(
s 1 ( n, n ) = ∞ m=0 π (∞,n2) (m, 1) - ∞ m=0 π (∞,n 2 ) (m, 1) = 0, and thus W ((∞, n 2 ), (∞, n 2 )) = W
(3.4.10)

Similarly, we have W ((n 1 , ∞), (n 1 , ∞)) = W (1) . Following this reasoning, we derive properties for the policy that never serves the bandit, i.e., (∞, ∞).

Lemma 3.21. We consider the threshold policy that never serves the bandit, (∞, ∞). For any policy ) , W (2) ]. Furthermore, W ((∞, ∞), n) = W (2) if and only if (1) if and only if n 2 = ∞.

n = (n 1 , n 2 ) it holds that W ((∞, ∞), n) ∈ [W (1
n 1 = ∞ and W ((∞, ∞), n) = W
We can now characterise optimal threshold policies that solve the relaxed optimisation problem for (3. 1. The threshold policy (-1, -1) is an optimal solution of (3.3.1) when W ≤ 0.

When W < 0, it is the unique optimal threshold policy. When W = 0, the optimal threshold policies are (-1, -1), (-1, 0), (0, -1) and (0, 0).

2. Assume Conditions 3.12 and 3.13 hold. For W ∈ 0, W (2) the optimal threshold solutions of (3.3.1) are of the form (n, 0) with n ≥ -1.

The threshold policy (∞, ∞

) is an optimal solution of (3.3.1) when W ≥ W (2) . When W > W (2) , it is the unique optimal threshold policy. When W = W (2) , the optimal threshold policies are of the form

(∞, n) with n ≥ 0.
Proposition 3.23. Assume Condition 3.12 holds. Then the sequence -

2 d=1 n d m=0 π (n,0) (m, d) n∈N ,
which represents the slope of the linear functions (g (n,0) ) n∈N , is a non-increasing sequence.

We can now prove Theorem 3.14.

Proof of Theorem 3.14: By Proposition 3.9, an optimal solution of (3.3.1) is of threshold form. For a given subsidy W , let n d (W ) denote the minimum value for a threshold in environment d such that the threshold policy (n d (W ), ñ3-d ), for some ñ3-d , is optimal.

If n 1 (W ) ≤ n 1 (W + ∆) and n 2 (W ) ≤ n 2 (W + ∆), (3.4.11) We are left to prove that W ((n j , 0), (n j-1 , 0)) ≤ W (1) for every j. To do so, recall from (3.4.9) that W ((n j , 0), (n j-1 , 0)) = W (1) + (1 -t) W (2) -W (1) , with 1 -t := s 2 ((n j , 0), (n j-1 , 0)) s 1 ((n j , 0), (n j-1 , 0)) + s 2 ((n j , 0), (n j-1 , 0))

. From Property 2) in Lemma 3.11 it follows that s 2 ((n j , 0), (n j-1 , 0)) < 0. We state the following property between arbitrary linear functions in R: if two linear functions cross each other in a given W , the one that minimises for W ≥ W is steeper than the one that minimises for W ≤ W . In this case, since g (nj-1,0) (W ) minimises for W ≤ W ((n j , 0), (n j-1 , 0)) and g (nj ,0) (W ) minimises for W ≥ W ((n j , 0), (n j-1 , 0)), g (nj ,0) is steeper than g (nj-1,0) , i.e., s 1 ((n j , 0), (n j-1 , 0))+ s 2 ((n j , 0), (n j-1 , 0)) > 0. Then 1 -t ≤ 0, and as a consequence, W ((n j , 0), (n j-1 , 0)) ≤ W (1) for every j. 2

Multi-class queue in a Markovian environment

In this section we study a queueing model without abandonments with an observable random environment and general holding cost. That is, we consider the model as described in Section 3.4 where now the abandonment rates are set equal to zero. First, we discuss the stability conditions of the model. Secondly, we derive Whittle's index, based on the results obtained in the previous section for an abandonment queue (by letting θ → 0). The latter is used to propose an index policy.

Stability conditions

We first provide the maximum stability conditions, that is the conditions on the parameters such that there exists a policy that makes the system stable. This stability result follows from [START_REF] Stolyar | Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic[END_REF].

Proposition 3.25 (Proposition 1, Section 4, in [START_REF] Stolyar | Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic[END_REF]). Let φ( d) be the probability that bandit k sees environment d k , k = 1, . . . , N . Recall that φ k (d k ) denotes the marginal distribution.

If there exists a policy such that the multi-class queue with environments is stable, then there exists a vector

γ = (γ k d : 1 ≤ k ≤ N, d ∈ Z N ), such that γ k d ≥ 0 and N k=1 γ k d ≤ φ( d), for all k, d, (3.5.1)
and d∈Z λ (d) k φ k (d) ≤ d∈Z N µ (d k ) k γ k d , ∀1 ≤ k ≤ N. (3.5.2)
If there exists a vector γ such that (3.5.1) and

d∈Z λ (d) k φ k (d) < d∈Z N µ (d k ) k γ k d , ∀1 ≤ k ≤ N, (3.5.3)
then there exists a policy that makes the system stable.

MULTI-CLASS QUEUE IN A MARKOVIAN ENVIRONMENT

Proof: For the sake of readability we present a sketch of the proof.

If the system is stable under some policy ϕ, then we consider the process under this policy in a stationary regime, and let γ ϕ γ k d , which by (3.5.3) is larger than its arrival rate. This implies stability. 2

Whittle's index policy

For the multi-class queue without abandonments, one cannot directly apply Algorithm 3.4 in order to get

Whittle's index. The reason for this is as follows. Let us focus on one bandit, and assume µ (1) < µ (2) . Then, we believe that as the subsidy grows from -∞ to ∞, threshold policies of the form (n, 0), n = 1, 2, . . ., will be optimal, and then, for larger W , the threshold policy (∞, 0) is optimal. However, once in environment 1 it is optimal to be passive in all states, when now comparing different threshold values for environment 2, each such threshold will have the same steady-state probability of being passive. Hence, there is no difference in the average obtained subsidy for passivity between threshold policies of the form (∞, n) and (∞, n + n ). This means that no index can be defined for states (m, 2). A similar observation was made for the classical multi-class queue without environments, see [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF]Section 7]. In order to obtain Whittle's index for the multi-class queue with environments, we therefore assume there are abandonments, and then let the abandonment rate scale to zero.

We assume linear holding cost. Let W θ (m, d) be the Whittle's index in the presence of abandonments (as derived in Section 3.4.2), with θ 1 = θ 2 = θ, with θ > 0. It is direct from Theorem 3.15 that if µ (1) < µ (2) , then lim θ→0 θW θ (m, 2) = cµ (2) , for all m ≥ 1.

(3.5.4)

That is, in environment 2, one needs to consider the scaled index. In environment 1, we observed numerically that no scaling was needed in order to obtain a non-trivial limit. In fact, we believe the following to be true:

Conjecture 3.26. lim θ→0 W θ (m, 1) < ∞.
In order to prove this conjecture, one needs to study W ((n j-1 , 0), (n j , 0)), which by (3.4.9) depends on the steady-state distributions. A perturbation approach as presented in [3, Theorem 2], would allow to write the steady state as an expansion in θ. However, the results of [START_REF] Altman | Perturbation analysis for denumerable Markov chains with application to queueing models[END_REF] do not directly apply since there the transition rates are assumed to be uniformly bounded.

We can now define a heuristic for the multi-class queue with a random environment. Let us assume there are N bandits and R can be made active. Define for each bandit k,

1 ≤ k ≤ N , d k such that µ (3-d k ) ≤ µ (d k ) .
In every decision epoch make active the bandits that are currently in their state d k . If there are more than R, choose the R ones having the largest value for c k µ (d k ) . If there are less than R, make also active the bandits currently in state 3 -d k having the largest value for lim θ→0 W θ k (m, 3 -d k ) as defined in Conjecture 3.26.

Numerical evaluation

In this section the performance under Whittle's index policy is compared to the performance of an optimal policy obtained via value iteration. We consider the abandonment model with two classes of users and two states for the environment(s), Z = {1, 2}. The decision epochs occur when there is a change of state, either in the queue length or in the environment. At each decision epoch the decision maker chooses which user to serve, that is, R = 1. We assume linear holding costs that do not depend on the environment or action

taken, i.e., C k (m, d, k) = m.
We plot the relative suboptimality gap in percentage for the different policies. We denote by g ϕ the performance under policy ϕ. Then, the suboptimality gap for policy ϕ is given by 100 * (g ϕ -g OP T )/g OP T , where g OP T is the average cost under an optimal policy. In Section 3.6.1, we generate a large number of parameters and using boxplots we show the suboptimality gaps under different policies. In Section 3.6.2 we focus on one particular set of parameters. In Section 3.6.3, we discuss how much one can gain by observing the state of the environments.

Boxplots

In this section we consider two different models for the environments. The first model is that of one common environment, and the second model is that of independent identically distributed environments. Numerically we calculate the suboptimality gap under Whittle's index policy W (m, d), Whittle's index policy for a fixed environment W (d) (m), and the policy that for each set of parameters chooses at random which bandit to serve in each state. We do this for 200 sets of randomly generated parameters in order to obtain a boxplot. This allows us to plot for each policy the 25th and 75th percentiles, the median value with an horizontal line and the outliers with "+". [START_REF] Brill | Level crossing methods in stochastic models[END_REF], and θ

k = λ ∈ [1, 10], µ (d) k ∈ [1, 20], r (d) k = r (d) ∈ [1,
(d) k = θ ∈ [0.1, 0.5], for k = 1, 2 and d = 1, 2.
We observe that the suboptimality gap of policies W (m, d) and W (d) (m) is very small, both for independent environments as well as for a common environment. The random policy shows worse performance having a median of the suboptimality gap in 18%.

The fact that the policy W (d) (m) performs similar to Whittle's index policy W (m, d) is surprising. The former does not take into account that the environment changes dynamically over time. To show that W (d) (m) is not an efficient policy, we narrow our set of randomly generated parameters. As before, we chose the parameters λ k . However, the departure rates are chosen differently. In environment d = 2, the departure rates are equal for both classes, i.e., µ

(2) 1 = µ (2) 2
= µ, where the value µ is chosen uniformly at random in the interval [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF][START_REF] Brill | Level crossing methods in stochastic models[END_REF]. In environment d = 1, we take µ his high departure rate 27. When the two environments are independent, one visits this state a positive fraction of time and hence profits from the highest departure rate for class 2. If instead the environment for both classes is common, one is never in state (D 1 (t), D 2 (t)) = (2, 1), explaining why Whittle's index policy can have a large suboptimality gap.

We consider three cases for the environment parameters:

• in the first set, both environments D 1 (t), D 2 (t) are identically distributed and their transition rates are given by r • In the second set, the environments are non-identical and their transition rates are given by r (2) 2 = 5/6. Indicated in the plot by "non-identical".

• In the third set, the environments are common with r (1) = 15β and r (2) = 17β, k = 1, 2, with β > 0.

Thus, φ (1) = 17/32 and φ (2) = 15/32. Indicated in the plot by "common".

Note that Condition 3.12 and Condition 3.13, which were needed in order to prove indexability, are not satisfied for the above parameters. However, numerically we observed that for this parameter setting, the system is indexable.

Scaling arrivals

We first study the suboptimality gap as the load in the system changes. We set β = 1. In Figure 3.3 (left) the relative suboptimality gap under Whittle's index policy (denoted by W (m, d)) is plotted as a function of γ. For the independent environment settings, the gap is not larger than 7%, and is 1% when in overload.

However, in a common environment, the gap can be around 25%.

Scaling speed of the environments

We now study the suboptimality gap as the speed of the environments changes.

In

Unobservable environments

In practice, the environment might not be observable due to technical constraints. In this section, we assess the performance degradation in case information on the environment is not available.

In Chapter 2 it was shown that the averaged Whittle index policy is asymptotically optimal when the state of environments is unobservable, as the number of bandits grows large together with the speed of the environment. In particular, from Chapter 2 together with [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF], one obtains that for the abandonment multi-class queue with linear cost, the averaged Whittle index W k (m), is given by We present here boxplots that compare the performance of the averaged Whittle index policy, W (m), to the Whittle index policy, W (m, d), obtained for the observable model. We further include the policy that for each set of parameters chooses at random which bandit to serve in each state. We consider two models for the environment: (i) one common environment for both classes, (ii) independent identically distributed environments.

W k (m) = c k θ k µ k , with θ k := d∈Z φ k (d)θ
We first consider 200 sets of randomly generated parameters. In Figure 3.5 (left) the parameters are chosen uniformly at random such that λ

(d) k = λ ∈ [1, 10], µ (d) k ∈ [1, 20], r (d) k = r (d) ∈ [1, 20], and θ (d)
k ∈ [0.1, 0.5], for k = 1, 2 and d = 1, 2. We observe that the suboptimality gap of policy W (m, d) is very small, with a median of 0% for both the common environment and the independent environments setting.

The suboptimality gaps of policy W (m) are larger, with a median of 7% for the common environment setting and 10% for the independent environments setting. The random policy shows worse performance, where the median of the suboptimality gap is above 20% in both cases.

For Figure 3.5 (right), we narrow our set of randomly generated parameters. In particular, we choose parameters such that the optimal action depends on the state the environment is in. The averaged index policy will not be able to mimic this, since it is a static policy. We fix the parameters such that

W (1) 1 >> W (1) 2 and W (2) 1 << W (2)
2 . Hence, in environment 1 it will be optimal to serve bandit 1 with high probability, and in environment 2 it will be optimal to serve bandit 2 with high probability. In the boxplot of Figure 3.5 (right), we still observe that the median of the suboptimality gap of policy W (m, d) is 0% in both cases, while the median of the suboptimality gap of policy W (m) is 29% for the common environment setting and 22% for the independent environments setting.

In Figure 3.5, we considered that the environment has transition rates of the same order as the main process. In a separate analysis we consider environments whose transition rates are 100 times larger than the transitions rates of the controllable process. We recall that we proved in Chapter 2 that the averaged Whittle's index policy W (m) is optimal in a rapidly varying unobservable environment. In the boxplots of Figure 3.6 the parameters are chosen as in Figure 3.5, except for the rates of the environment, where we take

Appendix

Proof of Lemmas of Section 3.3.2.

Proof of Lemma 3.6:

The measure p n d ,(d) (m) is the stationary distribution of the one-dimensional process with the following rates for m ≥ 0: q(m + 1|m) = λ (d) , and q((m -1) + |m) = mθ (d) + 1 (m>n d ) µ (d) , Let p n d ,(d) (m) be the stationary measure of this process, which satisfies the following balance equations:

λ (d) + mθ (d) + 1 (m>n d ) µ (d) p n d ,(d) (m) (3.7.1) = 1 (m>0) λ (d) p n d ,(d) (m -1) + (m + 1)θ (d) + 1 (m+1>n d ) µ (d) p n d ,(d) (m + 1),
for all m ≥ 0, d.

The balance equations for π n (m, d) are

(λ (d) + mθ (d) + 1 (m>n d ) µ (d) + βr (d) )π n (m, d) (3.7.2) = 1 (m>0) λ (d) π n (m -1, 1) + (m + 1)θ (d) + 1 (m+1>n d ) µ (d) π n (m + 1, d) + d =d βr (dd ) π n (m, d ),
for all m ≥ 0, d. The stationary probability measure that satisfies the balance equations is unique. As Recall that for a given β, n j (β), j = 0, . . . , is the minimisation vector obtained in (3.3.3), and nj = lim β→0 n j (β).

For

n ≥ nj d , define Âj d (n) := ∞ m=0 C (m, d, a) p n,(d) (m) - ∞ m=0 C (m, d, a) p nj d ,(d) (m) Bj d (n) := n m=0 p n,(d) (m) - nj d m=0 p nj d ,(d) (m).
We define the function

f j ( n) := lim β→0 2 d=1 ∞ m=0 C (m, d, a) π n (m, d) - 2 d=1 ∞ m=0 C (m, d, a) π n j (β) (m, d) 2 d=1 n d m=0 π n (m, d) - 2 d=1 n j d (β) m=0 π n j (β) (m, d) , ( 3.7.3)

Proof of Proposition 3.9:

For a given L 1, we truncate the state space at L and we smooth the arrival transitions by

q L (m + 1|m, d, a) := λ (d) 1 - m L + , ( 3.7.9)
for m = 0, 1, . . . , L.

Convexity of V L

We assume 1 = λ (1) + λ (2) + µ (1) + µ (2) + r (1) + r (2) + Lθ (1) + Lθ (2) for the uniformisation constant, without loss of generality. For any d and m = 0, . . . , L, we initialize by defining V L 0 (m, d) = 0 and

V L t+1 (m, d) = 1 - m L λ (d) V L t (min{m + 1, L}, d) + r (d) V L t (m, 3 -d) + mθ (d) V L t ((m -1) + , d) + min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t ((m -1) + , d)} + m L λ (d) V L t (m, d) + (L -m)θ (d) V L t (m, d) + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) V L t (m, d).
We will prove that

2V L t (m, d) ≤ V L t ((m -1) + , d) + V L t (m + 1, d), for 0 ≤ m ≤ L -1, (3.7.10)
for any t, i.e. the convexity of V L .

We first prove by induction in t that V L t (m, d) is non-decreasing in m. Note that V L 0 (m, d) = 0 is nondecreasing by definition, so we assume V L t (m, d) is non-decreasing and we prove that

V L t+1 (m + 1, d) -V L t+1 (m, d) ≥ 0 for 0 ≤ m ≤ L -1. (3.7.11)
We study the inequality splitting in terms according to the parameter that is multiplying. Firstly, we look to the terms multiplied by λ (d) in

V L t+1 (m + 1, d) -V L t+1 (m, d), so we have λ (d) 1 - m + 1 L V L t (min{m + 2, L}, d) + λ (d) m + 1 L V L t (min{m + 1, L}, d) -λ (d) 1 - m L V L t (min{m + 1, L}, d) - m L λ (d) V L t (m, d) = λ (d) 1 - m + 1 L V L t (min{m + 2, L}, d) + m L λ (d) V L t (min{m + 1, L}, d) -λ (d) 1 - m + 1 L V L t (min{m + 1, L}, d) - m L λ (d) V L t (m, d) = λ (d) 1 - m + 1 L (V L t (min{m + 2, L}, d) -V L t (min{m + 1, L}, d)) + m L λ (d) (V L t (min{m + 1, L}, d) -V L t (m, d)) ≥ 0.
The last inequality is due to the inductive hypothesis for V L t (m, d). Let us consider now the terms multiplied by θ (d) :

(m + 1)θ (d) V L t (m, d) + (L -m -1)θ (d) V L t (min{m + 1, L}, d) -mθ (d) V L t ((m -1) + , d) -(L -m)θ (d) V L t (m, d) = mθ (d) V L t (m, d) + (L -m -1)θ (d) V L t (min{m + 1, L}, d) -mθ (d) V L t ((m -1) + , d) -(L -m -1)θ (d) V L t (m, d) ≥ mθ (d) (V L t (m, d) -V L t ((m -1) + , d)) + (L -m -1)θ (d) (V L t (min{m + 1, L}, d) -V L t (m, d)) ≥ 0.
The last inequality holds because of the non-decreasing hypothesis for V L t (m, d). For the terms multiplied by r (d) it is straightforward that

r (d) V L t (m + 1, 3 -d) -r (d) V L t (m, 3 -d) ≥ 0,
because of the inductive hypothesis as well. Equivalently for the dummy transition terms,

(λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) ) (V L t (m + 1, d) -V L t (m, d)) ≥ 0.
Finally, we consider the minimisation terms in

V L t+1 (m + 1, d) -V L t+1 (m, d),
where the inequality is a consequence of the non-decreasing property of V L t (m, d) and C, and the fact that if A ≥ B and A ≥ B , then min{A, A } ≥ min{B, B }:

min{-W + C(min{m + 1, L}, d, 0) + µ (2) V L t (min{m + 1, L}, d), C(min{m + 1, L}, d, 1) + µ (2) V L t (m, d)} ≥ min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t ((m -1) + , d)}.
This concludes the proof of (3.7.11), i.e., V L t is non-decreasing. We consider now equation (3.7.10). Note that for m = 0 the equation reduces to V L t (0, d) ≤ V L t (1, d), which is true for every t and every d, because V L t is non-decreasing in m. Then for 1 ≤ m ≤ L -1, we make an analogous reasoning: we prove it by induction in t and we split the inequalities according to the multiplying parameters. For the initial step V L 0 (m) = 0 the inequality holds, so we assume it holds for V L t (m, d) and we study the inequality (3.7.10) for t + 1. Note that

2V L t+1 (m, d) =2 1 - m L λ (d) V L t (m + 1, d) + 2 m L λ (d) V L t (m, d) (3.7.12) + 2r (d) V L t (m, 3 -d) + 2mθ (d) V L t (m -1, d) + 2(L -m)θ (d) V L t (m, d) + 2 min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t (m -1, d)} + 2 λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) V L t (m, d) The term V L t+1 (m -1, d) + V L t+1 (m + 1, d) equals λ (d) 1 - m -1 L V L t (m, d) + λ (d) 1 - m + 1 L V L t (min {m + 2, L} , d) + λ (d) m -1 L V L t (m -1, d) + λ (d) m + 1 L V L t (m + 1, d) + r (d) V L t (m -1, 3 -d) + r (3-d) V L t (m -1, d) + r (d) V L t (m + 1, 3 -d) + r (3-d) V L t (m + 1, d) + (m -1)θ (d) V L t ((m -2) + , d) + (m + 1)θ (d) V L t (m, d) + (L -m + 1)θ (d) V L t (m -1, d) + (L -m -1)θ (d) V L t (m + 1, d) + min{-W + C(m -1, d, 0) + µ (2) V L t (m -1, d), C(m -1, d, 1) + µ (2) V L t ((m -2) + , d)} + min{-W + C(m + 1, d, 0) + µ (2) V L t (m + 1, d), C(m + 1, d, 1) + µ (2) V L t (m, d)} (3.7.13) + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) V L t (m -1, d) + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) V L t (m + 1, d).
We first compare the two terms multiplied by λ (d) in (3.7.12) to check they are smaller than or equal to the ones multiplied by λ (d) in (3.7.13). First assume 1 ≤ m ≤ L -2. The terms multiplied by λ (d) in (3.7.12)

are 2 1 - m L V L t (m + 1, d) + 2 m L V L t (m, d) = 2 1 - m + 1 L V L t (m + 1, d) + 2 m L V L t (m, d) + 2 L V L t (m, d) ≤ 1 - m + 1 L V L t (m, d) + 1 - m + 1 L V L t (m + 2, d) + 2 m L V L t (m, d) + 2 L V L t (m + 1, d) = 1 - m -1 L V L t (m, d) - 2 L V L t (m, d) + 1 - m + 1 L V L t (m + 2, d) + 2 m L V L t (m, d) + 2 L V L t (m + 1, d) = 1 - m -1 L V L t (m, d) + 1 - m + 1 L V L t (m + 2, d) + 2 m -1 L V L t (m, d) + 2 L V L t (m + 1, d) (3.7.14) Because of convexity, we know that 2 m-1 L V L t (m, d) ≤ m-1 L (V L t (m -1, d) + V L t (m + 1, d))
, hence the third term in (3.7.14) can be bounded, and we obtain:

2 1 - m L V L t (m + 1, d) + 2 m L V L t (m, d) ≤ 1 - m -1 L V L t (m, d) + 1 - m + 1 L V L t (m + 2, d) + m -1 L V L t (m -1, d) + V L t (m + 1, d) + 2 L V L t (m + 1, d) ≤ 1 - m -1 L V L t (m, d) + 1 - m + 1 L V L t (m + 2, d) + m -1 L V L t (m -1, d) + m + 1 L V L t (m + 1, d), (3.7.15)
which is the same as the terms multiplied by λ (d) in (3.7.13). Now assume m = L -1, then inequality

(3.7.10) reduces to 2(1 -2/L)V L t (L -1, d) ≤ (1 -2/L)(V L t (L -2, d) + V L t (L, d))
, which holds because of convexity of V L t . We consider now the terms multiplied by θ (d) . We need to prove

2mV L t (m -1, d) + 2(L -m)V L t (m, d) ≤ (m -1)V L t ((m -2) + , d) + (m + 1)V L t (m, d) + (L -m + 1)V L t (m -1, d) + 2V L t (m -1, d) + (L -m -1)V L t (m + 1, d),
or, equivalently,

2(m -1)V L t (m -1, d) + 2(L -m -1)V L t (m, d) ≤ (m -1)V L t ((m -2) + , d) + (m -1)V L t (m, d) + (L -m -1)V L t (m -1, d) + (L -m -1)V L t (m + 1, d).
This last inequality is obtained from the convexity property for 2V L t (m -1, d) and 2V L t (m, d) on the lhs. For the terms multiplied by r (d) , and the dummy transitions (λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) ), the inequalities to prove are

2r (d) V L t (m, 3 -d) ≤ r (d) V L t (m -1, 3 -d) + r (d) V L t (m + 1, 3 -d) and 2(λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) )V L t (m, d) ≤ (λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) ) (V L t (m -1, d) + V L t (m + 1, d)),
which are a direct consequence of convexity of V L t . We lastly consider the minimisation terms, for which we analyse each possible combination of optimal actions in states m -1 and m + 1. Since at time t, V L t is convex, the optimal actions satisfy the optimality of threshold policies. Denote by a * m ∈ {0, 1} the optimal action in state m, where action 0 (1) is passive (active). Then, since the threshold policy is optimal at time t, (a * m-1 , a * m+1 ) equals (0, 0), (0, 1) or (1, 1). We also use Property (3.4.1), regarding the cost function. For a * = (0, 1) and 1 ≤ m ≤ L -1 we have

2 min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t (m -1, d)} ≤ -W + C(m, d, 0) + µ (2) V L t (m, d) + C(m, d, 1) + µ (2) V L t (m -1, d) ≤ -W + C(m -1, d, 0) + µ (2) V L t (m, d) + C(m + 1, d, 1) + µ (2) V L t (m -1, d) = min{-W + C(m -1, d, 0) + µ (2) V L t (m -1, d), C(m -1, d, 1) + µ (2) V L t ((m -2) + , d)} + min{-W + C(m + 1, d, 0) + µ (2) V L t (m + 1, d), C(m + 1, d, 1) + µ (2) V L t (m, d)},
where in the last equality the value for the minimums are given by the optimal action a * = (0, 1).

For a * = (0, 0), we use convexity of C and V L t :

2 min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t (m -1, d)} = -2W + 2C(m, d, 0) + 2µ (2) V L t (m, d) ≤ -2W + C(m -1, d, 0) + C(m + 1, d, 0) + µ (2) V L t (m -1, d) + µ (2) V L t (m + 1, d) = min{-W + C(m -1, d, 0) + µ (2) V L t (m -1, d), C(m -1, d, 1) + µ (2) V L t ((m -2) + , d)} min{-W + C(m + 1, d, 0) + µ (2) V L t (m + 1, d), C(m + 1, d, 1) + µ (2) V L t (m, d)}.
Equivalently for a * = (1, 1), we make use of convexity properties:

2 min{-W + C(m, d, 0) + µ (2) V L t (m, d), C(m, d, 1) + µ (2) V L t (m -1, d)} = 2C(m, d, 1) + 2µ (2) V L t (m -1, d) ≤ C(m -1, d, 1) + C(m + 1, d, 1) + µ (2) V L t ((m -2) + , d) + µ (2) V L t (m, d) = min{-W + C(m -1, d, 0) + µ (2) V L t (m -1, d), C(m -1, d, 1) + µ (2) V L t ((m -2) + , d)} min{-W + C(m + 1, d, 0) + µ (2) V L t (m + 1, d), C(m + 1, d, 1) + µ (2) V L t (m, d)}.
This finishes the proof of (3.7.10) for t + 1, hence function V L t is convex. By [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF]Chapter 9.4] it follows that V L t (•) -tg → V L as t → ∞, where g is the averaged cost incurred under the optimal policy. Hence, convexity of V L t implies convexity of V L . 2

Hypothesis needed for [14, Theorem

In this section, we verify that V L → V as L → ∞. In particular, we verify that the sufficient conditions as stated in [14, Theorem 3.1] hold.

For ease of notation, we introduce q L ((m , d )|(m, d), a) as the transition rate of the truncated process from state (m, d) to state (m , d ), when action a is applied. That is,

q L ((m + 1, d)|(m, d), a) = λ (d) 1 - m L + , q L (((m -1) + , d)|(m, d), a) = mθ (d) + aµ (d) , and q L ((m, 3 -d)|(m, d), a) = r (d) , for m ∈ N 0 , d = 1, 2 and a = 0, 1.
In order to state the sufficient conditions of [14, Theorem 3.1], we need the following definition.

Definition 3.27. A function f : X × Z → R + is a moment function if there exists an increasing sequence of finite sets

(E n ) n∈N ⊂ X × Z such that lim n→∞ E n = X × Z and inf {f (m, d) : (m, d) / ∈ E n } → ∞ as n → ∞.
The conditions, as stated in [14, Theorem 3.1], are:

1. There exists a function f : We take the function f (m, d) = e m with > 0. We define the sets E n = {(0, 1), (0, 2), . . . , (n, 1), (n, 2)} for each n, which are finite, lim n→∞ E n = X × Z and inf {f (m, d) : (m, d) / ∈ E n } → ∞ as n → ∞. Condition 1 can be reduced to show that there exists > 0, M > 0 and a constant α > 0 such that

X × Z → R + , constants α, β > 0 and M > 0 such that (m ,d )∈X ×Z q L ((m , d )|(m, d), a) f (m , d ) ≤ -αf (m, d) + β1 {m<M } (m, d), for all m, d, ϕ, L.
(m ,d )∈X ×Z q L ((m , d )|(m, d), a) f (m , d ) ≤ -αf (m, d), for d = 1, 2 and m > M , that is, λ (d) 1 - m L + e (m+1) + (mθ (d) + aµ (d) )e (m-1) + r (d) e m λ (d) 1 - m L + + mθ (d) + aµ (d) + r (d) e m ≤ -αe m ,
for d = 1, 2 and m > M , where a is the action taken in state (m, d) under policy ϕ. The inequality can be rewritten as

λ (d) 1 - m L + (e -1) + (mθ (d) + aµ (d) )(e --1) ≤ -α, (3.7.16)
Note that, since 1 -

m L + is decreasing in m, there exists a constant C such that λ (d) 1 - m L + (e -1) < C.
For the other term, since (e --1) < 0, there exists an M such that for m > M , (mθ (d) + aµ (d) )(e --1) < -C. Then there exists α > 0 such that inequality (3. Without loss of generality, we assume that the increasing term is n 1 . Then, for a given (n 1 , n 2 ), we will show that

n1 m=0 π (n1,n2) (m, 1) ≤ n1+1 m=0 π (n1+1,n2) (m, 1).
The idea of the proof relies on using the comparison result 9.3.2 in [19, Chapter 9], for both processes given by the threshold policies (n 1 , n 2 ) and (n 1 + 1, n 2 ). For that, we define the following cost function:

C n (m, d, a) :=    1 if d = 1 and m ≤ n 1 0 otherwise.
In other words, C n (m, d, a) = 1 if and only if the state of the environment is 1 and the process is in a passive state for policy n. We also define the resulting expected reward per unit time,

G n := n1 m=0
π n (m, 1).

The remainder of the proof consists in showing As a consequence and after (3.7.18), we get the following relation:

G (n1,n2) ≤ G (n1+1,n2) . ( 3
G (n1,n2) ≤ G (n1,n2),L + K 1 H(L) ≤ G (n1+1,n2),L + K 1 H(L) ≤ G (n1+1,n2) + K 2 H(L) + K 1 H(L) .
Since this holds for every L, and H(L) → ∞ when L → ∞, we conclude (3.7.17) and the proof is done. 2

Proof of Lemma 3.28.

To simplify notation, since (n 1 , n 2 ) and L are fixed in the lemma, we will write V t for V (n1,n2),L t and H for H(L). The inequality to prove is

V t (m, d) -V t (m + 1, d) ≤ 1 µ (1) , ∀ 0 ≤ m ≤ L -1, d = 1, 2.
We initialize with k = 0, V 0 (m, d) = 0 for every (m, d), and for k = 1,

V 1 (m, d) =    1/H if d = 1 and m ≤ n 1 0 otherwise. As a consequence, sup (m,d) |V 1 (m, d) -V 1 (m + 1, d)| = 1 H ≤ 1
µ (1) .

We assume now V t (m, d)-V t (m+1, d) ≤ 1 µ (1) for every (m, d), and we prove it for V t+1 (m, d)-V t+1 (m+1, d). We begin with the state (n 1 , 1), where we have (1) V t (n 1 -1, 1) + r (1) V t (n 1 , 2) + λ (1) V t (n 1 + 1, 1)

V t+1 (n 1 , 1) = 1 H + 1 H n 1 θ
+ H -n 1 θ (1) -r (1) -λ (1) V t (n 1 , 1) , V t+1 (n 1 + 1, 1) = 1 H (n 1 + 1)θ (1) + µ (1) V t (n 1 , 1) + r (1) V t (n 1 + 1, 2) + λ (1) V t (n 1 + 2, 1)

+ H -(n 1 + 1)θ (1) -µ (1) -r (1) -λ (1) V t (n 1 + 1, 1) .

Then, the following equation holds, and we apply the inductive hypothesis

V t+1 (n 1 , 1) -V t+1 (n 1 + 1, 1) = 1 H + 1 H n 1 θ (1) (V t (n 1 -1, 1) -V t (n 1 , 1)) + r (1) (V t (n 1 , 2) -V t (n 1 + 1, 2))
+ λ (1) (V t (n 1 + 1, 1) -V t (n 1 + 2, 1)) -θ (1) + µ (1)

(V t (n 1 , 1) -V t (n 1 + 1, 1)) + H -n 1 θ (1) -r (1) -λ (1) (V t (n 1 , 1) -V t (n 1 + 1, 1)) = 1 H + 1 H n 1 θ (1) (V t (n 1 -1, 1) -V t (n 1 , 1)) + r (1) (V t (n 1 , 2) -V t (n 1 + 1, 2)) + λ (1) (V t (n 1 + 1, 1) -V t (n 1 + 2, 1)) + H -n 1 θ (1)
-θ (1) -µ (1) -r (1) -λ (1)

(V t (n 1 , 1) -V t (n 1 + 1, 1)) ≤ 1 H + 1 H n 1 θ (1)
1 µ (1) + r (1) 1 µ (1) + λ (1) 1 µ (1) + H -n 1 θ (1) -θ (1) -µ (1) -r (1) -λ (1) 1 µ (1) = H -θ (1) Hµ (1) ≤ 1 µ (1) .

For states (m, d) = (n 1 , 1), C n (m, d, a) = C n (m + 1, d, a), which makes the inequality easier to check.

Again, using similar algebraic calculations, we can conclude that V t+1 (m, d) -V t+1 (m + 1, d) ≤ 1/µ (1) and the Lemma is proved. 2

Proof of Property 2) in Lemma 3.11:

We compare again the processes (n 1 , n 2 ) with (n 1 + 1, n 2 ). In this case we have to prove

n2 m=0 π (n1,n2) (m, 2) ≥ n2 m=0 π (n1+1,n2) (m, 2).
We denote by M (n1,n2) (t) and M (n1+1,n2) (t) the controllable processes of the bandit, under policies (n 1 , n 2 ) and (n 1 + 1, n 2 ) respectively, with initial state given by the stationary measure. Note that their distribution is given by π n : for a given m ∈ X ,

P(M n (t) = m) = π n (m, 1) + π n (m, 2).
A simple coupling argument shows that M (n1,n2) (t) ≤ st M (n1+1,n2) (t), since they have the same rates in every state except for (n 1 + 1, 1), where M (n1+1,n2) (t) does not serve and, as a consequence, it has a lower death rate. Furthermore, the previous statement is true when looking to the second environment, i.e.,

M (n1,n2) (t)1 (D(t)=2) ≤ st M (n1+1,n2) (t)1 (D(t)=2
) . This inequality implies that for any n ∈ X ,

n m=0 π (n1,n2) (m, 2) = P M (n1,n2) (t) ≤ n, D(t) = 2 ≥ P M (n1+1,n2) (t) ≤ n, D(t) = 2 = n m=0 π (n1+1,n2) (m, 2).
If we take n = n 2 , the Proposition is proved. 2

Proof of Proposition 3.19:

Slow regime. We assume without loss of generality µ (1) θ (1) + r (1) + r (2) ≤ µ (2) θ (2) + r (1) + r (2) . Note that d) for both d = 1, 2. Together with Theorem 3.15, it is direct that lim β→0 W (m, 2) = c µ (2) θ (2) for m ≥ 0. For d = 1, recall from Lemma 3.20 that W ((n j-1 , 0), (n j , 0)) can be written as a function of s 1 ((n j-1 , 0), (n j , 0)) and s 2 ((n j-1 , 0), (n j , 0)). For any j ≥ 0, s 2 ((n j-1 , 0), (n j , 0)) = π (nj-1,0) (0, 2) -π (nj ,0) (0, 2). From Lemma Then, following from (3.4.9), lim β→0 W ((n j-1 , 0), (n j , 0)) = W (1) = c µ (1) θ (1) , which concludes the proof for the slow regime.

lim β→0 W (d) = c µ (d) θ (
Fast regime. Since φ(d) = r (3-d) r (1) + r (2) and θ = 2 d=1 φ(d)θ (d) , we can write lim β→∞ W (d) = lim β→∞ cµ (d) β(r (1) + r (2) ) + θ (3-d) β(r (1) θ (2) + r (2) θ (1) ) + θ (1) θ (2) = lim β→∞ cµ (d) 1 + θ (3-d) β(r (1) +r (2) ) β(r (1) θ (2) +r (2) θ (1) ) β(r (1) +r (2) )

+ θ (1) θ (2) β(r (1) +r (2) )

= lim β→∞ cµ (d) 1 + θ (3-d) β(r (1) +r (2) )

(φ(2)θ (2) + φ(1)θ (1) ) + θ (1) θ (2) β(r (1) +r (2) )

= c µ (d) θ , which gives the value of the index for d = 2.

Proof of results in Section 3.4.3.

Proof of Lemma 3.20: expression for W ( n, n ).

Since

n d m=0 π n (m, d) + ∞ m=n d +1 π n (m, d) = φ(d), Lemma 3.10 for n states λ (d) φ(d) + r (3-d) ∞ m=0 mπ n (m, 3 -d) = (θ (d) + r (d) ) ∞ m=0 mπ n (m, d) + µ (d) φ(d) -µ (d) n d m=0 π n (m, d),
or, equivalently,

∞ m=0 mπ n (m, d) = λ (d) φ(d) + r (3-d) ∞ m=0 mπ n (m, 3 -d) -µ (d) φ(d) + µ (d) n d m=0 π n (m, d) 1 θ (d) + r (d) ,
for d = 1, 2. After some algebra, we can solve these two equations in ∞ m=0 mπ n (m, 1) and ∞ m=0 mπ n (m, 2), and then we obtain (2) + θ (2) r (1) + θ (1) r (2) , (3.7.22) for d = 1, 2. In the numerator in (3.4.8), the terms can be regrouped per environment, i.e.

∞ m=0 mπ n (m, d) = λ (d) -µ (d) φ(d) θ (3-d) + r (3-d) + λ 3-d -µ (3-d) φ(3 -d)r (3-d) +µ (3-d) r (3-d) n 3-d m=0 π n (m, 3 -d) + µ (d) θ (3-d) + r (3-d) n d m=0 π n (m, d) • 1 θ (1) θ
n i m=0 π n (m, i), we obtain ∞ m=0 mπ n (m, d) - ∞ m=0 mπ n (m, d) = µ (d) θ (3-d) + r (3-d) s d ( n, n ) + µ (3-d) r (3-d) s 3-d ( n, n ) θ (1) θ (2) + θ (2)
r (1) + θ (1) r (2) . (3.7.24)

Summing we obtain the following expression for (3.7.23): 1) θ (2) + r (1) + r (2) s 1 ( n, n ) + µ (2) θ (1) + r (1) + r (2) s 2 ( n, n ) θ (1) θ (2) + r (1) θ (2) + r (2) θ (1) = s 1 ( n, n )W (1) + s 2 ( n, n )W (2) .

2 d=1 c ∞ m=0 mπ n (m, d) - ∞ m=0 mπ n (m, d) = c • µ (
Since the denominator in (3.4.8) is s 1 ( n, n ) + s 2 ( n, n ), Lemma 3.20 is proved.

2

Proof of Lemma 3.21: comparison to policy (∞, ∞).

Since ni m=0 π n (m, i) ≤ φ(i) for i = 1, 2, it follows that s i ((∞, ∞), n) = ∞ m=0 π (∞,∞) (m, i)- ni m=0 π n (m, i) = φ(i) - ni m=0 π n (m, i) ≥ 0.
This implies that 0 ≤ t ≤ 1 as defined in Lemma 3.20, hence together with (3.4.9), it follows that W ((∞, ∞), n) ∈ [W (1) , W (2) ].

Note that

n1 m=0 π n (m, 1) + ∞ m=n1+1 π n (m, 1) = φ(1) and ∞ m=n1+1 π n (m, 1) > 0 for n 1 < ∞. As a consequence, n1 m=0 π n (m, 1) < φ(1), so s 1 ((∞, ∞), n) = φ(1) - n1 m=0
π n (m, 1) > 0 and t > 0. Equation (3.4.9) can be rewritten as W (2) -t(W (2) -W (1) ), hence W ((∞, ∞), n) < W (2) 1) -φ(1) = 0, and t = 0. In this case, W ((∞, ∞), n) = W (2) . The reasoning for n 2 = ∞ is analogous.

if n 1 < ∞. If n 1 = ∞, s 1 ((∞, ∞), n) = ∞ m=0 π (∞,∞) (m, 1) - ∞ m=0 π (∞,n2) (m, 1) = φ(
2

Proof of Proposition 3.22

In order to prove Point 1, we start with W = 0. The difference between policies (-1, -1), (-1, 0), (0, -1)

and (0, 0) relies on serving or not a queue when it's empty. As a consequence, they have no difference in their dynamics (thus, in their invariant distribution π n ), neither in their expected cost

2 d=1 ∞ m=0 cmπ n (m, d).
From the definition of g n (0) in Equation (3.3.1) we obtain that g (-1,-1) (0) = g (-1,0) (0) = g (0,-1) (0) = g (0,0) (0). Furthermore, if either n 1 > 0, or n 2 > 0, or both of them are larger than 0, then the expected costs satisfy

2 d=1 ∞ m=0 cmπ (0,0) (m, d) < 2 d=1
∞ m=0 cmπ n (m, d), because the former is active in every non-zero state. Hence, g (0,0) (0) < g n (0) for any n / ∈ {(-1, -1), (-1, 0), (0, -1), (0, 0)}. For W < 0, the proof follows considering the slope of the linear functions g n (W ), which is given by -2 d=1 n d m=0 π n (m, d). For policy (-1, -1) the slope is 0, while -2 d=1 n d m=0 π n (m, d) < 0 for any n = (-1, -1). Together with the fact that in W = 0 policy (-1, -1) minimises, we get that (-1, -1) is the unique optimal threshold policy for W < 0, and the proof of Point 1 is finished.

For the proof of Point 2 we state the following lemma. We present its proof in Appendix 3.7.5. Lemma 3.29. Assume Conditions 3.12 and 3.13 hold. When d = 2 and m ≥ 0, being active is an optimal action for 0 ≤ W < W (2) . When d = 2 and m = 0, being passive is an optimal action for 0 ≤ W .

From Lemma 3.29, for 0 ≤ W < W (2) in environment 2 the optimal action is passive in m = 0 and active in m > 0, then the optimal threshold policy in environment 2 has to be 0. Thus, the optimal solutions are in the set of policies {(n, 0)} -1≤n≤∞ .

Point 3 follows from Lemma 3.21 and a comparison of the linear functions. For any policy n = (n 1 , n 2 ), W ((∞, ∞), n) ≤ W (2) and the slope of its linear function is -

2 d=1 n d m=0 π n (m, d) ≥ -1, since π n is a probability distribution. For the policy (∞, ∞), the slope is - ∞ m=0 π (∞,∞) (m, d) = -1, thus the linear function g (∞,∞) (W )
is the steepest one. It follows that for W ≥ W (2) , (∞, ∞) is an optimal solution of (3.3.1) and it is the only one for W > W (2) . In addition, when W = W (2) , only policies of the form (∞, n) have the same cost g n (W ) as (∞, ∞) (see Lemma 3.21). Hence, when W = W (2) , optimal threshold policies are of the form (∞, n).

Proof of Lemma 3.29.

We want to show the optimal policies in environment d = 2 for 0 ≤ W < W (2) . Recall from (3.4.2) that Bellman's optimality equation is given by: (µ (d) + mθ (d)

+ λ (d) + r (d) )V (m, d) + g = cm + λ (d) V (m + 1, d) + mθ (d) V ((m -1) + , d) + r (d) V (m, 3 -d) (3.7.25) + min -W + µ (d) V (m, d), µ (d) V ((m -1) + , d) .
Hence, in state (m, d) passive is an optimal action if and only if

-W + µ (d) V (m, d) ≤ µ (d) V ((m -1) + , d).
Similarly, active is an optimal action if and only if

-W + µ (d) V (m, d) ≥ µ (d) V ((m -1) + , d).
In case m = 0,

-W + µ (d) V (0, d) ≤ µ (d) V (0, d) if and only if W ≥ 0.
In other words, in state 0 the optimal action is passive if and only if W ≥ 0, and both actions are optimal if W = 0.

Let W < W (2) . We will show that

-W + µ (2) V (m, 2) ≥ µ (2) V (m -1, 2), ∀m ≥ 1,
or equivalently, (2) , ∀m ≥ 1.

V (m, 2) -V (m -1, 2) ≥ W/µ
(3.7.26)

Since we will use the value iteration method, we formulate an analogous property for the truncated value function V L , see Lemma 3.30. We truncate the state space at L and smooth the transition rates from state m to state m + 1 as in (3.7.9). That is, we replace the arrival rates λ (d) by

λ (d) 1 - m L + ,
for m = 0, 1, . . . , L. The uniformisation constant is taken as γ := λ (1) + λ (2) + µ (1) + µ (2) + r (1) + r (2) + Lθ (1) + Lθ (2) , (3.7.27) We define the value function V L t (m, d) as follows. For any d and m = 0, . . . , L we initialize by defining V L 0 (m, d) = 0 and (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) V L t (m, d).

V L t+1 (m, d) = cm γ + 1 - m L + λ (d) γ V L t (min {m + 1, L} , d) + r (d) γ V L t (m, 3 -d) + mθ (d) γ V L t ((m -1) + , d) + 1 γ min{-W + µ (d) V L t (m, d), µ (d) V L t ((m -1) + , d)} + min m L , 1 λ (d) γ V L t (m, d) + (L -m)θ (d) γ V L t (m, d) + 1 γ λ
The following lemma states the property needed for V L .

Lemma 3.30. Assume Conditions 3.12 and 3.13 hold. For 0 ≤ W < W (2) there exists an L 0 large enough such that (2) ∀L ≥ L 0 and 1 ≤ m ≤ L.

V L (m, 2) -V L (m -1, 2) ≥ W/µ
(3.7.28)

We can conclude now the proof of Lemma 3.29. From Lemma 3.30 there exists an L 0 such that inequality (3.7.28) holds for all L ≥ L 0 . Since V L → V , as stated in Section 3.7.2, inequality (3.7.26) is proved, which concludes the proof. 2

Proof of Lemma 3.30:

We define the parameters W L, (d) :

W L,(d) := cµ (d)
θ (3-d) + r (1) + r (2) + λ (3-d) /L θ (1) + r (1) + λ (1) L θ (2) + r (2) + λ (2) L -r (1) r (2) .

Note that W L,(d) → W (d) as L → ∞. We further define:

C L,(d) t (m) := V L t (m, d) -V L t (m -1, d), d = 1, 2,
and we will show that there exists an L 0 and t 0 such that for L ≥ L 0 and t ≥ t 0 ,

C L,(2) t (m) ≥ W/µ (2) for 1 ≤ m ≤ L, (3.7.29)
We write C L,(d) t+1 (m) as follows:

C L,(d) t+1 (m) = V L t+1 (m, d) -V L t+1 (m -1, d) (3.7.30) = c γ + 1 - m L + λ (d) γ C L,(d) t (m + 1) + r (d) γ C L,(3-d) t (m) + (m -1)θ (d) γ C L,(d) t (m -1) + 1 γ min -W + µ (d) V t (m, d), µ (d) V t (m -1, d) - 1 γ min -W + µ (d) V t (m -1, d), µ (d) V t ((m -2) + , d) + m -1 L λ (d) γ C L,(d) t (m) + (L -m)θ (d) γ C L,(d) t (m) + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) γ C L,(d) t (m).
We have the following properties for functions C Lemma 3.31. Assume 0 ≤ W < W (2) . Define

t 0 := min t t s.t. µ (d) C L,(d) t (m) ≥ W for a pair (m, d) .
Then there exists an L 1 large enough such that for

L ≥ L 1 , t 0 < ∞ and C L,(d) t (m) = C L,(d) t
is constant in m for all t ≤ t 0 .

From the previous lemma, we have that t 0 is the minimum t such that either µ (1) C L,(1) t ≥ W or µ (2) C L,(2) t ≥ W for L ≥ L 1 . Under Condition 3.12, we will prove that at time t 0 , it holds that µ (2) C L,(2) t0

≥ µ (1) C L,(1) t0

, and hence µ (2) C L,(2) t0

≥ W .

Lemma 3.32. Assume Condition 3.12 holds and let 0 ≤ W < W (2) and L > 0. Then µ (2) C L,(2) t ≥ µ (1) C L,(1) t for t ≤ t 0 .

The previous property allows us to state conditions under which inequality (3.7.29) holds in t = t 0 for all L ≥ L 1 . Note that for t > t 0 , Condition 3.13 will be sufficient to prove that (3.7.29) holds for t ≥ t 0 and for all m.

Lemma 3.33. Assume Condition 3.13 holds and 0 ≤ W < W (2) . Then there exists an L 0 large enough such that for all L ≥ L 0 , C L,( 2) t (m) ≥ W/µ (2) , ∀1 ≤ m ≤ L and t ≥ t 0 .

Lemma 3.33 proves that (3.7.29) holds for 0 ≤ W < W (2) and L ≥ L 0 . Equivalently, (3.7.28) holds and the proof of Lemma 3.30 is finished. 2

We provide now the proofs of Lemmas 3.31, 3.32 and 3.33.

Proof of Lemma 3.31: Since the sequence W L, (2) → W (2) as L → ∞ and W < W (2) , we can take L 1 such that for all L ≥ L 1 W < W L, (2) . The property of C (m) + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) γ C

t+1 (m) = c γ + 1 - m L λ (d) γ C L,(d) t + r (d) γ C L,(3-d) t + (m -1)θ (d) γ C L,(d) t + µ (d) γ C L,(d) t + m -1 L λ (d) γ C L,(d) t + (L -m)θ (d) γ C L,(d) t + λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) γ C L,(d) t = c γ + 1 - 1 L λ (d) γ C L,(d) t + r (d) γ C L,(3-d) t + µ (d) γ C L,(d) t + (L -1)θ (d) γ C L,(d) t
+ λ (3-d) + µ (3-d) + r (3-d) + Lθ (3-d) γ C

L,(d) t . Following from (3.7.31), C L, (1) and C L, (2) are the solutions of the following system of equations. (2) + r (2) γ C L, (1) (3.7.32)

= c γ + γ -θ (d) -r (d) -λ (d) /L γ C L,(d) t + r (d) γ C L,(3-d) t , ( 3
         C L,(1) = c γ + γ -θ (1) -r (1) -λ (1) L γ C L,(1) + r (1) γ C L,(2) C L,(2) = c γ + γ -θ (2) -r (2) -λ (2) L γ C L,
After some algebraic computation, we find that the solutions of this set of equations are C L, (1) = W L, (1) /µ (1) and C L, (2) = W L, (2) /µ (2) . If (2) , which gives a contradiction. Hence, t 0 < ∞.

t 0 = ∞, then lim t→∞ µ (2) C L,(2) t ≤ W < W L,
2

Proof of Lemma 3.32: 1) t

Let ∆ t = µ (2) C L,(2) t -µ (1) C L,(
. Using (3.7.31) and after some computation we get

C L,(1) t+1 = C L,(1) t γ -θ (1) -r (1) -λ (1) L γ + µ (1) r (1) γµ (2) + ∆ t r (1) γ + c ∆ t+1 = µ (1) C L,(1) t γ θ (1) + µ (2) r (2)
µ (1) + r (1) -θ (2) -r (2) µ (1) r (1) µ (2) +∆ t µ (2) (γ -θ (2) -r (2) -λ (2) L ) -µ (1) r (1) γµ (2) + c(µ (2) -µ (1) ) γ .

We show by induction that both C L,(1) t ≥ 0 and ∆ t ≥ 0. For t = 0 it is trivial. Assume it holds for t. Since γ -θ (1) -r (1) λ (1) L > 0, it follows that for C L, [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF] t+1 ≥ 0. For ∆ t+1 we have that c(µ (2) -µ (1) ) γ ≥ 0, because µ (2) -µ (1) ≥ 0 by Condition 3.12. The term multiplying ∆ t is:

µ (2) (γ -θ (2) -r (2) -λ (2) /L) -µ (1) r (1)
γµ (2) ≥ 0, which is non-negative if and only if

µ (2) (γ -θ (2) -r (2) -λ (2) /L) ≥ µ (1)
r (1) .

This holds because µ (2) ≥ µ (1) and (γ -θ (2) -r (2) -λ (2) /L) ≥ r (1) , by definition of γ.

Finally, since µ (1) ≤ µ (2) and θ (2) ≤ θ (1) , we have

θ (2) + r (2) + µ (1) µ (2) r (1) ≤ θ (1) + µ (2)
µ (1) r (2) + r (1) .

Hence ∆ t+1 ≥ 0 and the proof is finished.

Proof of Lemma 3.33:

We show that there is an L 0 such that the following property holds for every t ≥ t 0 , for all L ≥ L 0 and all m ≥ 1:

       C L,(2) t (m) ≥ W µ (2) C L,(1) t (m) ≥ (θ (2) + r (2) + λ (2) /L)W -cµ (2)
r (2) µ (2) .

(3.7.33)

Since from Condition 3.13, W < W (2) ≤ cµ (2) θ (2) + r (2) , there exists an L 2 such that W ≤ cµ (2) θ (2) + r (2) + λ (2) /L , for all L ≥ L 2 , or equivalently, (θ (2) + r (2) + λ (2) /L)W -cµ (2) ≤ 0. On the other hand, it is easy to see by

(m) ≥ (θ (2) +r (2) +λ (2) /L)W -cµ (2)
r (2) µ (2) for all L ≥ L 2 and all t.

In Lemmas 3.31 and 3.32 we proved that C L,( 2) t0

(m) ≥ W µ (2) , holds for L ≥ L 1 and t = t 0 . Then we take L 0 = max (L 1 , L 2 ), we assume inequalities in (3.7.33) hold for t > t 0 , and we prove they are valid for t + 1. For all states (m, 2) we have that active is an optimal action because C L, [START_REF] Ahmad | Optimality of myopic sensing in multichannel opportunistic access[END_REF] t+1 (m) ≥ W/µ (2) . Hence, from (3.7.30):

C L,(2) t+1 (m) = c γ + 1 - m L λ (2) γ C L,(2) t (m + 1) + r (2) γ C L,(1) t (m) + (m -1)θ (2) γ C L,(2) t (m -1) + µ (2) γ C L,(2) t (m -1) + m -1 L λ (d) γ C L,(2) t (m) + (L -m)θ (2) γ C L, (2) t (m)
+ λ (1) + µ (1) + r (1) + Lθ (1) γ C

L,( 2) t (m)

≥ c γ + γ -θ (2) -r (2) -λ (2) /L γ W µ (2) + r (2) γ (θ (2) + r (2) + λ (2) /L)W -cµ (2) r (2) µ (2)
= W µ (2) ,

where in the inequality we used that C

L,(1) t (m) ≥ (θ (2) +r (2) +λ (2) /L)W -cµ (2)
r (2) µ (2) . On the other hand,

C L,(1) t (m) ≥ (θ (2) +r (2) +λ (2) /L)W -cµ (2) r (2) µ (2)
holds for all t as it was proved before. This concludes the proof of both inequalities in (3.7.33) for t ≥ t 0 , and then Lemma 3.33 is proved as well. 2

Proof of Proposition 3.23.

The proof here is similar to the one of Property 1) in Lemma 3.11 in Section 3.7.3, in the sense that we will compare the truncated processes with limited capacity L > n, using the comparison result 9. By applying the inductive hypothesis, we obtain

V t+1 (0, 2) -V t+1 (1, 2) = 1 H + 1 H r (2) (V t (0, 1) -V t (1, 1)) + λ (2) (V t (1, 2) -V t (2, 2)) -θ (2) + µ (2) (V t (0, 2) -V t (1, 2)) + H -r (2) -λ (2) (V t (0, 2) -V t (1, 2)) ≤ 1 H + 1 H r (2) 1 µ (1) + λ (2) 1 µ (1) + H -θ (2) -µ (2) -r (2) -λ (2) 1 µ (1) = H + µ (1) -θ (2) -µ (2)
Hµ (1) .

The inequality

H + µ (1) -θ (2) -µ (2)
Hµ (1) ≤ 1 µ (1) holds if and only if µ (1) -µ (2) < θ (2) . The latter holds from Condition 3.12 and θ (2) > 0.

Similarly, one obtains the same conclusion for states (m, d) = (0, 2). This finishes the inductive step and the Lemma is proved.

2

Proof of Proposition 3.24.

The proof relies on comparing g (n,m) (W ) for an arbitrary policy (n, m) with g (∞,0) (W ) for W ∈ W (1) , W (2) .

In particular, it will be shown that g (∞,0) (W ) ≤ g (n,m) (W ) for W ∈ [W (1) , W (2) ], g (∞,0) (W ) < g (n,m) (W )

for W ∈ (W (1) , W (2) ), and for W = W (2) the equality g (∞,0) (W ) = g (n,m) (W ) holds if and only if n = ∞.

To prove the above, we first consider a threshold policy (n, m) = (∞, m). From Equation (3.4.10), it is direct to see that W ((∞, m), (∞, 0)) = W (2) , hence g (∞,m) (W (2) ) = g (∞,0) (W (2) ). Then, we compare the slopes, recall that -

2 d=1 n d m=0 π n (m, d)
is the slope of g n (W ) for any threshold policy n. In this case, the slope of g

(∞,m) (W ) is -(φ(1) + m k=0 π (∞,m) (k, 2)) and the slope of g (∞,0) (W ) is -(φ(1) + π (∞,0) (0, 2)).
From Property 2) in Lemma 3.11, we know that m k=0 π (∞,m) (k, 2) > π (∞,0) (0, 2). As a consequence, g (∞,m) (W ) is steeper than g (∞,0) (W ), and therefore, for W < W (2) , g (∞,0) (W ) < g (∞,m) (W ). For the if and only if, in case n = ∞, g (n,m) (2) ), and this contradicts Lemma 3.21. We now consider a threshold policy (n, m) with n = ∞. We split the proof in two steps. In the first step, we compare policies (∞, 0) and (n, 0). Then, in the second step we compare policies (n, 0) and (n, m). This will be sufficient to conclude the comparison between policies (∞, 0) and (n, m).

(W (2) ) = g (∞,0) (W (2) ), because if g (n,m) (W (2) ) = g (∞,0) (W (2) ), then g (n,m) (W (2) ) = g (∞,∞) (W
Step 1. In this step we prove that g (∞,0) (W ) < g (n,0) (W ), when W ∈ W (1) , W (2) , and g (∞,0) (W (1) ) ≤ g (n,0) (W (1) ) when W = W (1) . To prove Step 1, we distinguish between three cases, as depicted in Figure 3.7. The cases represent the possible relations between the slopes of the functions g (∞,0) (W ) and g (n,0) (W ).

Case a) -

2 d=1 n d m=0 π (∞,0) (m, d) < - 2 d=1 n d m=0 π (n,0) (m, d).
In this case g (∞,0) (W ) is steeper than g (n,0) (W ). In terms of s 1 and s 2 , - Comparing slopes of functions g (n,0) and g (∞,0) . that W ((∞, 0), (n, 0)) = W (1) + (1 -t) W (2) -W (1) , with t := s 1 ((∞, 0), (n, 0)) s 1 ((∞, 0), (n, 0)) + s 2 ((∞, 0), (n, 0)) .

2 d=1 n d m=0 π (∞,0) (m, d) < - 2 d=1 n d m=0 π (n,0) (m, d) is equivalent to s 1 ((∞, 0), (n, 0)) + s 2 ((∞, 0), (n, 0)) > 0. Recall from (3.4.9) W W (1) W (2) g(W) ( ∞ , ∞ ) (n, 0) (∞ , 0) Case a) W W (1) W (2) g(W) ( ∞ , ∞ ) ( n , 0 ) (∞ , 0) Case b) W (1) W (2) g(W) ( ∞ , ∞ ) (n , 0) (∞ , 0) Case c)
Since s 1 ((∞, 0), (n, 0)) + s 2 ((∞, 0), (n, 0)) > 0 and s 2 ((∞, 0), (n, 0)) = π (∞,0) (0, 2) -π (n,0) (0, 2) ≤ 0 (because of Property 2) in Lemma 3.11), we have that t ≥ 1. Since W (2) -W (1) ≥ 0, W ((∞, 0), (n, 0)) ≤ W (1) .

This, together with the fact that g (∞,0) is steeper, implies that for W > W (1) , g (∞,0) (W ) < g (n,0) (W ) and for W = W (1) , g (∞,0) (W (1) ) ≤ g (n,0) (W (1) ). ) is the steepest linear function. Besides W ((∞, ∞), (n, 0)) < W (2) and W ((∞, ∞), (∞, 0)) = W (2) because of Lemma 3.21. Hence, W ((∞, 0), (n, 0)) > W (2) , and as a consequence, for W ≤ W (2) ,

Case b) -

2 d=1 n d m=0 π (∞,0) (m, d) > - 2 d=1 n d m=0 π (n,0) (m, d). When g (n,0) (W ) is steeper the opposite situation occurs. Note that - 2 d=1 n d m=0 π (∞,∞) (m, d) = -1, hence g (∞,∞)(W
g (∞,0) (W ) < g (n,0) (W ). Case c) - 2 d=1 n d m=0 π (∞,0) (m, d) = - 2 d=1 n d m=0 π (n,0) (m, d).
Hence g (n,0) (W ) and g (∞,0) (W ) are parallel, which means that W ((∞, 0), (n, 0)) is not defined. Since W ((∞, ∞), (n, 0)) < W (2) and W ((∞, ∞), (∞, 0)) = W (2) , we can conclude that g (n,0) (W ) and g (∞,0) (W ) are not the same line, and in particular g (n,0) (W ) > g (∞,0) (W ) for all W .

Step 2. Assume n = ∞, and fix any m. For W ∈ W (1) , W (2) , g (n,0) (W ) ≤ g (n,m) (W ). First note that, from Properties 1) and 2) in Lemma 3.11,

s 2 ((n, m), (n, 0)) = m l=0 π (n,m) (l, 2)-π (n,0) (l, 2) ≥ 0 and s 1 ((n, m), (n, 0)) = n l=0 π (n,m) (l, 1) - n l=0 π (n,0) (l, 1) ≤ 0.
From the fact that s 1 ((n, m), (n, 0)) and s 2 ((n, m), (n, 0)) have opposite signs (or they are equal to 0), and following from Equation (3.4.9), W ((n, m), (n, 0)) can not be in (W (1) , W (2) ). Hence, we are in one of the following cases. If W ((n, m), (n, 0)) ≤ W (1) , then from Equation (3.4.9) we have

s 2 ((n, m), (n, 0)) s 1 ((n, m), (n, 0)) + s 2 ((n, m), (n, 0)) ≤ 0.
Since s 2 ((n, m), (n, 0)) ≥ 0, s 1 ((n, m), (n, 0)) + s 2 ((n, m), (n, 0)) < 0, which means that g (n,0) (W ) is steeper than g (n,m) (W ). This implies that g (n,0) (W ) ≤ g (n,m) (W ) for W ≥ W ((n, m), (n, 0)), hence, in particular for W ≥ W (1) .

If W ((n, m), (n, 0)) ≥ W (2) , the reasoning is analogous. From Equation (3.4.9) we have s 1 ((n, m), (n, 0)) s 1 ((n, m), (n, 0)) + s 2 ((n, m), (n, 0)) ≤ 0, and, as it was stated before, s 1 ((n, m), (n, 0)) ≤ 0. Hence, s 1 ((n, m), (n, 0)) + s 2 ((n, m), (n, 0)) > 0, which means that g (n,m)(W ) is steeper than g (n,0) (W ). As W ((n, m), (n, 0)) ≥ W (2) , for any W ≤ W (2) ,

g (n,0) (W ) ≤ g (n,m) (W ). 2
Chapter 4 In this chapter, we present a model of replication in large distributed storage systems using a stochastic modelling approach. A storage system consists in a set of nodes used to ensure data availability in large scale networks. Each node contains a large number of files as well as copies of those files. The nodes are interconnected in such a way that data blocks can be replicated and reallocated.

Allocation in Large Scale Systems

A relevant problem among these systems is the fact that the nodes break down: it is common to see nodes crashing due to issues like a high level of activity. Addressing this problem in order to ensure that the system continues operating properly is known as fault-tolerance, and in particular we are interested in the reliability feature. Reliability is the property of not losing information whenever there is a failure. A very extended method used for guaranteeing reliability is to store copies of the same file in different nodes [START_REF] Neumann | Probabilistic logics and the synthesis of reliable organisms from unreliable components[END_REF].

Moreover, in order to minimise the probability of losing data, an automatic mechanism of replication works whenever a node breaks down. The mechanism consists in regenerating a new copy of every file that was in that node just before the breakdown, using copies present in other nodes, and reallocating the new copies to different functioning nodes as the system continues working.

Many important systems such as Hadoop Distributed File System (HDFS) [START_REF] Borthakur | HDFS architecture guide[END_REF], Google File System (GFS) [START_REF] Ghemawat | The google file system[END_REF] and Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] use replication mechanisms as the one previously described to ensure data availability. For some references in replication and fault-tolerance in large data stores we also refer to [67, Chapters We study a version of this mechanism, and we focus our attention on the load distribution of each node, that is a key feature among these systems. The load distribution can be studied by representing the process as an urn model, which consists in a set of urns and a set of identical balls jumping across the urns along time. Each ball waits a randomly distributed amount of time and then jumps to another urn, following a 0 1

• • • n • • • f (0) αΨ(π β , 0) f (1) αΨ(π β , 1) αΨ(π β , n -1) f (n) αΨ(π β , n) Figure 4.1: diagram of process (X β (t)).
description of the evolution of (X β (t)), and, in second term, we formally formulate the problem. From this section, we assume that Condition 4.1 and Condition 4.2 are satisfied.

As it was stated for (L N 1 (t)), the process (X β (t)) lives in N 0 and it has two types of transitions. a) when the node breaks down, and b) when the node receives files from the breakdowns of other nodes.

The transitions of type a) are the same as for (L N 1 (t)), thus (X β (t)) makes transitions n → 0 at rate f (n) for all state n ≥ 0.

For the transitions of type b), intuitively, as the total number of nodes N grows large, the reallocation step of a single breakdown does not allocate more than one file to the same node. In other words, for N large enough, and given nodes i, j and a state l,

P Z N ij ( l) ≥ 2 = 0,
where Z N ij ( l) is a binomial random variable with parameters l i and p N ij ( l). As a consequence, the transitions of type b) in (X β (t)) are birth transitions n → n + 1 for all n ≥ 0. We want to determine the rate of these transitions, i.e., the rate at which node 1 receives a file from any of the other nodes. In order to do so, we consider the process in equilibrium.

Let us assume that the process (X β (t)) is ergodic. We denote by π β its stationary measure and X β the random variable distributed by π β . Note that, from the scaling assumption (4.2.1), E(X β ) = β. At equilibrium, the load of an arbitrary node is given by X β , and the rate at which it breaks down is f (X β ).

Therefore, the output flow of files from any node is given by the following parameter α:

α := E X β f (X β ) .
The probability that a file is assigned to a node depends on its current state n, and this is determined by the function Ψ as defined in Condition 4.2. Then, the rate at which a files arrives to node 1 is given by αΨ(π β , n). In summary, provided that all the conditions needed for its existence are satisfied, (X β (t)) is a jump process whose Q-matrix is given by q(n, 0) = f (n) and q(n, n + 1) = αΨ(π β , n), for all n ≥ 0. The evolution of (X β (t)) is represented in Figure 4.1. We can now formulate our problem.

Formulation of the problem

We study the existence of the process (X β (t)). This process exists if there exist a probability measure π β and an α ∈ R + that satisfy the following equations.

π β (n)(αΨ(π β , n) + f (n)) = π β (n -1)αΨ(π β , n -1), for n ≥ 1, (4.2.8) α = n≥0 nf (n)π β (n), ( 4
ν(π β ) = π β in M (N 0 ), where ν is defined for σ ∈ M (N 0 ) as ν(σ) = ν(σ)(n) := E f (X β ) α(σ)Ψ(σ, n) + f (n) n-1 k=0 α(σ)Ψ(σ, k) α(σ)Ψ(σ, k) + f (k) , for n ≥ 0, (4.2.10)
where α(σ) = n≥0 nf (n)σ(n) and we use the convention

j k=i a k = 1 if j < i.
Proof: Following from Equation (4.2.8), for any n ≥ 1, π β (n) satisfies the following equation:

π β (n) = π β (n -1) α(π β )Ψ(π β , n -1) α(π β )Ψ(π β , n) + f (n) .
We deduce inductively from last expression that, for n ≥ 1,

π β (n) = π β (0) α(π β )Ψ(π β , 0) α(π β )Ψ(π β , n) + f (n) n-1 k=1 α(π β )Ψ(π β , k) α(π β )Ψ(π β , k) + f (k) . ( 4

.2.11)

For π β (0), from Relation (4.2.3) on Ψ we have that n≥0 π β (n)Ψ(π β , n) = 1, which can be rewritten as

n≥1 π β (n)Ψ(π β , n) = 1 -π β (0)Ψ(π β , 0). ( 4

.2.12)

Then, we sum both sides of equation (4.2.8) for n ≥ 1, and we get

α(π β ) [1 -π β (0)Ψ(π β , 0)] + E f (X β ) -π β (0)f (0) = α(π β ),
which is equivalent to

π β (0) = E f (X β ) α(π β )Ψ(π β , 0) + f (0) .
This proves the expression for n = 0. Furthermore, following from (4.2.11), we obtain

π β (n) = E f (X β ) α(π β )Ψ(π β , n) + f (n) n-1 k=0 α(π β )Ψ(π β , k) α(π β )Ψ(π β , k) + f (k) , for n ≥ 1,
and the proposition is proved. 2

Main results

In this section we present our results. We assume a linear rate for the breakdowns of the nodes, i.e.,

f (n) = c 1 n, c 1 ∈ R >0 .

The Random Weighted allocation

(x) = c 1 x, for π β (n) = ν(π β )(n) we obtain π β (n) = c 1 βγ αW (n) + c 1 nγ n-1 k=0 αW (k) αW (k)+c 1 kγ , for n ≥ 0, (4.3.1)
where α := c 1 E X RW β 2 and γ := k≥0 W (k)π β (k). Therefore, the proof reduces to show that, under these definitions, there exist unique values α and γ.

We consider the following two equations. Let x 0 := γ/α, then from Equation (4.3.2) we obtain

1 β = c 1 γ αW (0) + n≥1 1 n(n+1) 1- n k=0 αW (k) αW (k)+c 1 kγ , (4.3.2) 1 = n≥0 W (n)c 1 β αW (n)+c 1 nγ n-1 k=0 αW (k) αW (k)+c 1 kγ . ( 4
1 β = c 1 x 0 W (0) + n≥1 1 n(n+1) 1- n k=0 W (k) W (k)+c 1 kx 0 . (4.3.4) Since n k=0 W (k) W (k)+c1kx0
is strictly decreasing as a function of x 0 > 0, the right hand side of Equation (4.3.4) is strictly increasing in x 0 . Furthermore, the limit of the right hand side of Equation (4.3.4) as x 0 → 0 + is 0, and its limit as x 0 → +∞ is +∞. Therefore, for a given β > 0, Equation (4.3.4) has a unique solution x 0 > 0. Then, note that an equivalent formulation of (4. Since for each β > 0 there exists a unique x 0 > 0, from Equation (4.3.5) we deduce that for each β > 0 there exists a unique α > 0. Finally, for each β > 0, there exists a unique γ = x 0 α > 0. We conclude that (X RW β (t)) exists, and its stationary measure is given by (4.3.1). 2 as β grows large. We recall that γ and α are parameters that depend on β, although we omit it in the notation for ease of the reading. Since the normalisation constant can also be written as Z a = n≥0 U a (n), we have that A a (1) = Z a /N δ+1 a , and E φ a 1/(δ+2) X RW β

=

A a (φ) A a [START_REF] Aalto | Whittle index approach to size-aware scheduling with time-varying channels[END_REF] .

We have to prove that the previous expression converges to E φ X RW ∞ as a goes to 0. We prove this in two steps. Firstly we show that, if K>0 is sufficiently large, the sum of terms with the indices greater than KN a in the definition of A a (1) can be made uniformly small with respect to a. Secondly, we prove the convergence of (A a (φ)) when φ has a compact support. .

By definition of N a , the expression aN δ+2 a is converging to 1 as a goes to 0. We assume that a is sufficiently small so that aN δ+2 a is lower bounded by 1/2. We then have One can thus choose K sufficiently large so that the right hand side of the last expression is arbitrarily small, and therefore, all the R K (a) with a in a neighbourhood of 0 are sufficiently small as well. The first step is established.

R K (a) ≤ 1 N a n≥KNa
Assume now that φ has compact support in [0, K] with K∈N, A a (φ) can be written as The constant C in (4.3.7) is the normalisation constant needed for the function to be a density, and it can be computed from the expression of Γ δ+1 δ+2 . The theorem is proved. 2

The Random allocation

In this section we consider the Random allocation policy, where the allocation function Ψ R is given by Equation (4.2.5). It is a particular case of the Random Weighted allocation policy, taking a constant weight function W (n) = K with K > 0, for all n ≥ 0. We denote the studied process as (X R β (t)), and X R β the variable distributed by the stationary measure. The novelty of the section relies on the explicit expression of the generating function of X R β . We assume a breakdown rate given by f (x) = x. Theorem 4.8. For a given β > 0, under the Random allocation policy and with a rate of breakdowns given by f (x) = x, the process (X R β (t)) exists. In other words, there exist π β and α that satisfy Equations (4.2.8) and (4.2.9). Note that the integrating factor h(α, u) = e α(ln(1-u)+u) is decreasing in α, since ln(1 -u) + u ≤ 0 for u ∈ (0, 1). Then the right hand side of the expression is strictly decreasing in α > 0, and it varies between +∞ and 0. Hence, for any β > 0 there exists a unique α > 0 satisfying Equation (4.3.15), and the proof of the existence is ended.

For the generating function we have (1-u) α e αu du , and the proof is ended. 2

E z X R β = π β (0) + n≥1 π β (n)z n = π β (0)+π β (0)
Convergence as β → ∞. We present now the convergence in distribution of X R β as β → ∞. In order to do so, we introduce Proposition 4.9, which is a technical result regarding the growth rate of α(β).

Future work

We outline various lines of research that follow from the works presented in this thesis.

Activation constraint depending on the environment

In Chapters 2 and 3, we considered a unique sample-path constraint on the number of active bandits that does not depend on the state of the environments. We leave for a future work the study of Whittle's index obtained after this relaxation. In particular, we believe that for the observable setting, Whittle's index will not only depend on the state of the bandit (m, d), as we have in Chapter 3, but also on the environment of the other bandits.

In [START_REF] Fu | Restless bandits in action: Resource allocation, competition and reservation[END_REF], a relaxation of an MARBP problem with more than one sample-path constraint is proposed, resulting in multiple Lagrangian multipliers. The authors formulate a related Whittle's index.

Unobservable environments

As it is stated in Table 5.1, it remains as future work to study optimal control for bandits affected by unobservable environments, in cases where the environment does not change relatively fast. In addition to the environment changing fast, another assumption in our analysis was that the number of bandits tends to infinity. Thus, the mathematical analysis of the unobservable case remains largely unexplored.

The problem with unobservable environments can be considered as a MARBP with partially observable states. A reference in Markov Processes with incomplete state information is [START_REF] Åström | Optimal control of Markov processes with incomplete state information[END_REF]. One possibility to get more insights would be to resort to learning algorithms, in particular reinforcement learning (RL). This is

Large-scale storage systems

We propose some extensions for our main result in Chapter 4, Theorem 4.5. As a first extension, we can consider a quadratic rate for the breakdowns of the nodes, instead of a linear rate. A possible approach to solve this problem is to express the solution of the fixed point equation (4.2.10) as the solution of an ODE of second order. A simpler version of this method is already used in the proof of Theorem 4.8, with an ODE of first order.

Another extension is to consider allocation policies that involve a more complex analysis than the Random Weighted policy. In particular, we are interested in the so-called Power of d-Choices policy, where, for allocating a file after a breakdown, the system chooses d nodes at random, and allocates the file to the least loaded node among this subset. We would like to generalise the results in [START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF], where the Power of d-Choices policy is considered for a system with breakdowns at a constant rate. The authors show that in the mean-field regime the process behaves as a non-homogeneous Markov process, and the stationary measure is then derived.

Contents 2 . 1 14 2. 2 16 2. 3 19 2. 4 21 2. 5 23 2. 6

 21142163194215236 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rapidly varying modulated environments . . . . . . . . . . . . . . . . . . . . . . Priority policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Averaged Whittle's index policy . . . . . . . . . . . . . . . . . . . . . . . . . . . Numerical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

( 1 )

 1 k (n) outperforms the averaged Whittle index policy, while the index policy W[START_REF] Ahmad | Optimality of myopic sensing in multichannel opportunistic access[END_REF]

  γ

Contents 3 . 1 38 3. 2 40 3. 3 41 3. 4 45 3. 5 52 3. 6 54 3. 7

 31382403414455526547 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Relaxation and Whittle's index policy . . . . . . . . . . . . . . . . . . . . . . . . Calculation of Whittle's index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abandonment queue in a Markovian environment . . . . . . . . . . . . . . . . Multi-class queue in a Markovian environment . . . . . . . . . . . . . . . . . . Numerical evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

  environments are exogenous Markov processes living in the state space Z = {1, 2, . . .}, whose evolution is independent of the state of the controllable processes or the actions taken. Let D k (t) = d ∈ Z denote the state of the environment of bandit k at time t, k = 1, . . . , N , and r (dd ) k the transition rate of D k (t) from state d to d . We assume the environments D k (t) are positive recurrent. We denote by φ k (d) the stationary probability of environment D k (t) to be in state d.

3. 1 .

 1 Threshold policies are defined through a vector n = (n d : d ∈ Z), where n d ∈ {-1, 0, 1, . . .} ∪ {∞}, for all d. Threshold policy n activates the bandit if and only if the controllable process is above the threshold n d when the state of the environment is d. In other words,A n (m, d) = 1 if m > n d and A n (m, d) = 0 if m ≤ n d .We denote by π n (m, d) the stationary probability of the process M n (t), D(t) to be in state (m, d).

Figure 3 . 1 :Remark 3 . 5 .

 3135 Figure 3.1: Lower envelop g := min n g n . Algorithm 3.4 finds Ŵj for j ≥ 0.

for d = 1 , 2 .

 12 When the class-k environment is in state d, new class-k jobs arrive according to a Poisson process with rate λ (d) k . They require an exponentially distributed amount of service with parameter µ (d) k . A class-k job abandons the system after an exponentially distributed amount of time with parameter θ (d) k . Let C k (m

2 Lemma 3 .

 23 E M n 1 (D=3-d) represents arrivals to the subsystem, and r (d) E M n 1 (D=d) the departures. 11 proves monotonicity properties on n d m=0 π n (m, d). This quantity represents the probability that a class is not being served and observes environment d. Lemma 3.11.

3 . 1 )

 31 as a function of the subsidy W . Proposition 3.22.

  k d be the average fraction of time that the environment is d and bandit k is active. The obtained vector γ ϕ satisfies (3.5.1) by definition. It also satisfies Equation (3.5.2), which can be seen by contradiction. Assume it did not hold, then at least one bandit would grow indeterminately towards infinite with probability 1. If (3.5.1) and (3.5.3) hold for a certain γ, we define the policy ϕ as the policy that, under environment d, makes bandit k active with probability γ k d /φ( d) and with probability 1 -N k=1 γ k d φ( d) does not make active any bandit. Then policy ϕ allocates to bandit k on average a service rate equal to d∈Z N µ (d k ) k

Figure 3 . 2 (

 32 Figure 3.2 (left) considers random sets of parameters chosen as follows: The parameters are chosen uniformly at random such that λ (d)

( 1 ) 1 =Figure 3 . 3 :

 1133 Figure 3.3: Suboptimality gap of Whittle's index policy and the index W (d) (m) as a function of (left) the scaling parameter of arrival rates (γ) and (right) the scaling parameter of the transition rates for the environment (β).

k

  = 17β, k = 1, 2, with β > 0. Thus, φ in the plot by "i.i.d.".

2 Figure 3 . 4 :

 234 Figure 3.4: Whittle's index as a function of the scaling parameter of the transition rates for the environment. (left) state m = 1, (right) state m = 10.

Figure 3 . 3 ,

 33 (right) the suboptimality gap for both policies W (m, d) and W(d) (m) is plotted as a function of the speed of the transitions of the environment (and γ = 1). For the two independent environment settings, we observe that for β around 10 -2 , the performance under Whittle's index policy W (m, d) and the policy W (d) (m) are very similar. Their suboptimality gap is less than 12%. On the other hand, for the common environment, the suboptimality gap under Whittle's index policy is around 23% when the transition rates of the environments are not scaled. Surprisingly, the fixed Whittle index performs rather well for any choice of β.Recall from Proposition 3.8 that Whittle's index W (m, d) converges as β → 0 to W (d) (m). This explains why in Figure3.3, (right) the performance of Whittle's index policy converges towards the fixed Whittle's index policy. Under linear cost, W (d) (m) is equal to cµ (d) k /θ (d) k , for k = 1, 2 and d = 1, 2. In Figure 3.4, we plot W k (1, d), W k (10, d) and the values cµ (d) k /θ (d) k and see the convergence.

kFigure 3 . 5 :

 35 Figure 3.5: Suboptimality gap for unobservable policies with (left) random parameters and (right) constrained parameters.

β 2 Proof

 2 → 0, (3.7.2) is equal to (3.7.1) with p n d ,(d) (m) replaced by lim β→0 π n (m, d). After normalisation, we hence have that lim β→0 π n (m, d) = φ(d)p n d ,(d) (m), for all m ≥ 0.

2 .

 2 (a, L) → q L ((m , d )|(m, d), a) and (a, L) → (m ,d )∈X ×Z q L ((m , d )|(m, d), a)f (m , d ) are continuous functions in a and L for all (m, d) and (m , d ).

7 . 16 ) 2 3

 7162 holds for d = 1, 2 and m > M and Condition 1 is proved. For Condition 2, the continuity of the functions (a, L) → q L ((m , d )|(m, d), a) and (a, L) → (m ,d )∈X ×Z q L ((m , d )|(m, d), a)f (m , d ) in a and L holds by definition of the transition rates.

.7. 17 )

 17 Since the result 9.3.2 in[START_REF] Boucherie | Queueing networks: a fundamental approach[END_REF] Chapter 9] requires a uniformisable process and our abandonment rates grow linearly in n in an infinite state space, we consider a truncated version. Let L be the limited capacity for the truncated version of the process, with L > max {n 1 + 1, n 2 }. We denote by q n,L ((m , d )|(m, d), a) the transition rate of the process from state (m, d) to state (m , d ), when action a is applied, where action a is determined by the threshold policy n.We introduce the uniformisation constant H(L):= max d λ (d) + µ (d) + r (d) + Lθ (d)and the transition probabilities P n,L ((m , d )|(m, d), a) obtained after the standard uniformisation approach [68, P.110] for each step of length H(L). Let V n,L t (m, d) denote the expected cumulative cost over t steps under threshold

3. 6 s 2 (

 62 we can deduce that for any d ∈ Z and any pair of policies n, n such that n d = n d , lim β→0 π n (m, d) = lim β→0 π n (m, d) ∀m ≥ 0(n j-1 , 0), (n j , 0)) = 0.

From ( 3 . 7 .

 37 [START_REF] Buyukkoc | The cµ rule revisited[END_REF], and together with the notation s i ( n, n ) := ni m=0 π n (m, i) -

  being constant in m is trivial for t = 0, since V L 0 (m) = 0 for all m, and thus C L,(d) 0 (m) = 0 as well. For a given t < t 0 we assume C L,(d) t (m) is constant, and we then prove this property for t + 1. Since µ (d) C L,(d) t(m) < W , at time t passive is the optimal action in (3.7.30) for m ≥ 1 and for W ≥ 0 passive is also optimal for m = 0. Hence,

  .7.31) where the last inequality follows from the definition of γ, (3.7.27). Hence, C L,(d) t+1 (m) does not depend on m. To conclude, we show that t 0 = ∞. Since for d = 1, 2, C L,(d) t is increasing in t, let C L,(d) := lim t→∞ C L,(d) t

3 . 2 in [ 19 ,

 3219 Chapter 9]. Here we compare the truncated process under threshold policy (n, 0) with the one under threshold policy (n + 1, 0). For the uniformisation, as we repeat the same structure, H(L), P n,L ((m , d )|(m, d), a) and V n,L t have the same definitions. However, we take as cost function C n (m, d), for a given threshold policy n = (n 1 , n 2 ),

Figure 3 . 7 :

 37 Figure 3.7: Proof of Proposition 3.24. Comparing slopes of functions g (n,0) and g (∞,0) .

Contents 4 . 1 4 . 2 4 . 3 4 . 4

 41424344 Model description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Mean-field limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7 and 8 ]

 8 and[START_REF] Özsu | Principles of distributed database systems[END_REF] Chapter 13].

.3. 3 )Equation ( 4 . 3 . 2 )

 3432 follows from the fact that n≥0 π β (n) = 1, a detailed computation can be found in Appendix 4.4. Equation (4.3.3) follows from the definition of γ and Equation (4.3.1).

Corollary 4 . 6 . 2 c 2 /n δ for n ≥ 1 ,( 4 . 3 . 6 )

 46221436 With the notation of Theorem 4.5, we have lim β→+∞ γ/α = 0.Proof: This result follows from the proof of Theorem 4.5. Recall that γ/α = x 0 , and for each β > 0 there exists a unique x 0 > 0 that satisfies Equation (4.3.4). Furthermore, as β tends to infinity, the lhs of Equation (4.3.4) tends to 0, and the x 0 that solves the equation tends to 0 as well.Convergence as β → ∞ for the case W (n)=c 2 /n δ . For the remainder of the section, we assume a weight function given by with δ, c 2 > 0. In Theorem 4.7 we prove the convergence in distribution of X RW β

Theorem 4 . 7 . 7 )

 477 Let W (n) be defined as in(4.3.6). For the convergence in distribution of the variable X on R + , and Γ is the classical Gamma function.Proof: Following from Equation (4.3.1), we have that the distribution ofX RW β for n ≥ 1 is π β (n) = c 1 βγn δ c 2 α + c 1 γn δ+1nthe notation in order to continue the proof. Let a := c 1 γ/c 2 α, Z a := (c 1 βγ/c 2 α) -1 is the normalisation constant, and U a (n) := expression of the distribution reduces to π β (n) = U a (n)/Z a for all n ≥ 0. Note that from Corollary 4.6, lim β→∞ a = 0. Using this notation, we prove now the convergence in distribution. If φ is a bounded continuous function on R + , define A a (φ) := n≥0 φ a 1/(δ+2) n U a (n) N δ+1 a , with N a := 1 a 1/(δ+2) .

For

8 )

 8 The change of variables in second inequality is n → uN a , and in third inequality is k → xN a .If v>0, we consider the function w →w ln(1+v/w). This function is increasing on R + , following from its derivative, which, with the change of variables p = w w+v , isln(1+v/w) -v w+v = -ln(p)-1+p ≥ 0 for all p∈(0, 1].We fix some b>0 sufficiently small. For a∈(0, b), we have N a ≥ N b , and following from (4.3.8), we get R K (a) ≤

.. 9 ) 2 Finally

 92 As before, the convergence of (aN δ+2 a ) to 1 as a goes to 0 shows that, for a sufficiently small, A a (φ) is in an interval of the type [B η1 a (φ), B η2 a (φ)] where η 2 <1<η 1 and η 1 and η 2 are arbitrarily close to 1, with the definitionWe study the convergence of B η a (φ) as a → 0. We first write the uniform estimation, for 0 ≤ n ≤ KN a ,The elementary inequality | ln(1+x)-x| ≤ x 2 2 , for x∈[0, 1], gives us the uniform estimationN a ln 1+ 1 N a ηu δ+1 = ηu δ+1 + O 1 N a ,for u in some fixed finite interval. Following from (4.3.9), we get , with the uniform estimation of the integral and Lebesgue's Theorem, we get the relation lim )x δ exp -η x δ+2 δ+2 dx, and, therefore, the desired convergence for (A a (φ)).

Furthermore, the generatingα e αzu du 1+α 1 0( 1 2 .

 112 function of the variable X R β has the following expression. -u) α e αu du . (4.3.10)Proof: Following from the definition of Ψ R , and inductively from the balance equations (4.2.8), for n ≥ 1 we haveπ β (n) = π β (0) Since π β (0)is the normalisation constant, it can be expressed asπ β (0) =In this case, the existence and uniqueness of π β reduces to show the existence and uniqueness of α such that Equations (4.3.11) and (4.3.12) are well defined. In order to obtain an expression forE(X n-1 -S n ) = α S 0 -lim n S n = α. to see that f α (x) = x α + f α (x) and f α (0) = 0, hence f α (x) = x 0 u α e x-u du.From Equations (4.3.13) and(4.3.14), and the fact that β = E(X R β ), we obtain thatβ = α 1 + α -α f α (α) ,or, equivalently, after the substitution u → α(1 -u) in the integral in f α (α)u) α e αu du.(4.3.15)

1 0( 1

 11 u) α e αu du, where the second equality follows from Equation (4.3.13) and the third one from the fact that E(X R β ) = β and from Equation (4.3.15). Then, recall the definition of f α (x) in (4.3.14), in (4.3.16) we obtain 1+α -u) α e αu du E z X R β

Proposition 4 . 9 .√ α 1 0( 1 1 0( 1 -u) α e αu du 2 . 2 Theorem 4 . 10 .= 1+αe -s β 1 0( 1 1 0( 1 √ α + √ αe -s β 1 0( 1 √ α + √ α 1 0( 1 2 Remark 4 . 11 .4. 4 Appendix 1

 4911112241011111111241141 Under the Random allocation policy, We rewrite the integral in(4.3.15) as: ln(1-x)≤-x-x 2 /2 for x ∈ (0, 1), obtained from its Taylor polynomial, and Lebesgue's convergence theorem, we get lim α→+∞ -u) α e αu du = u) α e αu du + √ αTaking limit as β → ∞, and from (4.3.17), we obtain lim For the convergence in distribution of the variable X We make the change of variables in the generating function, as given by (4.3.10), to get the Laplace transform of X R β β in the limit:φ β (s) = E e s β X R β -u) α e αe -s β u du 1+α -u) α e αu du = 1 -u) α e αe -s β u du 1 -u) α e αu du . (4.3.18)In a separate analysis, we study the following term: inequality ln(1-x)≤-x-x 2 /2 for x ∈ (0, 1), we getln(1-x) + xe -s β ≤-1 -e -u) α e αe -s β u du ≤ lim β→∞ equality is due to the Taylor expansion of 1-e -s β , and the last one to Proposition 4.9. The inequality is in fact an equality, because of Lebesgue's convergence theorem. Then, following from (4.3.18), we get the convergence of the Laplace transform, The result in Theorem 4.10 can be deduced from Theorem 4.7, taking the limit δ → 0, together with Proposition 4.9. In order to obtain the same expression for the density functions, a change of variables is needed.Calculation of Equation(4.3.2): From Equation (4.3.1) we have that π β (n) = c 1 βγ αW (n) + c 1 nγ n-1 k=0 αW (k) αW (k) + c 1 kγ . The normalisation relation for π β states that n≥0 π β (n) = 1nγ + αW (n) -αW (n) αW (n) + c 1 nγ n-1 k=0 αW (k) αW (k) + c 1 kγ = αW (k)+c 1 kγ .

1 (C

 1 Following the notation of Chapter 3, this was stated in Equation (3.1.1). An alternative approach can be considered, by proposing a sample-path constraint per state of the environments. For given values R d : d ∈ Z N , we consider the following set of constraints:N k=1 A ϕ k (t)1 ( D(t)= d) ≤ R d 1 ( D(t)= d) , ∀t ≥ 0 and ∀ d ∈ Z N , (5.2.1)where D(t) := (D 1 (t), . . . , D N (t)) denotes the state of the environment processes of all the bandits. The relaxed version of constraints (5.2.1) states that the number of active bandits must be satisfied on average, and not in every decision epoch.D(t)= d) dt ≤ R d φ( d) ∀ d ∈ Z N ,where φ( d) is the stationary probability of D(t) to be in state d. The Lagrangian multipliers approach applied for several constraints leads us to consider several multipliers, W d , one for each state d the environments can be in: k (M ϕ k (t), D k (t), A ϕ k (t)) -W d 1 ( D(t)= d) N k=0 A ϕ k (t) dt ∀ d ∈ Z N .

  for details.

	Lemma 2.2. Assume policy ϕ is such that y ϕ,1 j,k (•) is uniformly Lipschitz continuous, i.e.,
	sup
	j,k

Lemma 2.4. Assume Condition 2.3 is satisfied. It then holds that the feasible set of the (LP) problem is non-empty and lim inf

	Condition 2.3. Given a policy ϕ,
	a) the process X N,ϕ N (t) has a unique invariant probability distribution p N,ϕ ∀N .
	b) the family p N,ϕ	N ∈N is tight.
	c) the family p N,ϕ	N ∈N is uniform integrable.
	When bandits have a finite state space (J k < ∞), Condition 2.3 is true whenever X N,ϕ (t) is unichain.

Table 2 .

 2

	γ	1	5	10	25	50	100 500 750 1000 2500 5000
	g B	9.6	9.7	9.4	8.6	7.7	7.0	6.2	6.1	6.0	6.0	5.9
	g W	11.2 10.9 10.2 8.8	7.7	7.0	6.2	6.1	6.0	6.0	5.9
	g d φ(d)W (d)	12.6 11.9 10.7 8.9	7.8	7.1	6.3	6.2	6.1	6.1	6.0
	g W (1)	10.6 10.5 10.1 8.8	7.8	7.1	6.2	6.1	6.1	6.0	6.0
	g W (2)	12.3 12.9	13	12.1 11.1 10.2 9.2	9.1	9.1	9.1	9.0
	Rel(W )	16.2 12.7 8.4	2.4	0.4 0.01 0.03 0.03 0.03 0.03 0.03
	Rel( d φ(d)W (d) ) 30.9 22.6 Rel(W (1) ) 10.5 9	14 6.7	4.2 2.9	1.7 1.3	1.4 0.9	1.7 0.9	1.7 0.9	1.7 0.9	1.7 0.9	1.7 1
	Rel(W (2) )	27.6 33.6 37.5 42.1	44	45	49.2 50.2 50.9 52.1 52.6

1: Results for Example 1.

Table 2 .

 2 Rel(W(2) ) 31.8 49.9 57.7 63.5 63.6 60.1 42.2 37.5 34.5 27.5 24.4

		1	5	10	50	100 500 750 1000 2500 5000 7500 10000 25000
	g B	56.6 45.8 43.2 40.6 39.8 25.7 17.9 14.1	9.0	7.8	7.4	7.3	7.0
	g W	87.4 85.4 84.5 83.0 81.9 43.8 21.0 15.0	9.1	7.8	7.5	7.3	7.0
	Rel(W ) 54.4 86.3	96	105 106 70.2 17.4	6.4	0.8	0.3	0.2	0.1	0.04
					Table 2.2: Results for Example 2.
		γ		1	5	10	25	50	100 500 750 1000 2500 5000
		g B		25.9 17.0 13.2 9.4	7.6	6.3	4.8	4.6	4.4	4.2	4.0
		g W		33.3 21.4 16.7 12.0 9.5	7.8	5.6	5.2	5.0	4.5	4.3
		g d φ(d)W (d)		33.3 21.5 16.8 12.2 9.8	8.1	5.8	5.4	5.2	4.8	4.6
		g W (1)		30.0 19.4 15.2 10.9 8.7	7.2	5.3	5.0	4.8	4.4	4.2
		g W (2)		34.1 25.4 20.8 15.4 12.4 10.1 6.8	6.3	6.0	5.3	5.0
		Rel(W )		28.5 26.2 26.6 26.7 25.7 23.7	16	13.9 12.5	8.8	6.9
	29 15.7 14.6 15.1 15.8 15.6 14.6 10.5 9.2 29 27.9 21.4 19.5 18.2 14.7 Rel( d φ(d)W (d) ) 28.9 26.9 27.8 Rel(W (1) ) 8.4 6.1	13 4.8

3: Results for Example 3.

Example 2: In this example, we chose the parameters such that, when in environment 1, class 1 has a high departure rate and class 2 a low departure rate, while in environment 2, we have the opposite. The values for the parameters are:

  .2.9) where (4.2.8) are the balance equations of (X β (t)), and (4.2.9) is the output flow from an arbitrary node.In Proposition 4.4, we further characterise π β as the solution of a fixed point equation. This characterisation will be used in the proofs of our main results. Assume the process (X β (t)) exists, i.e., there exist π β and α that satisfy Equations (4.2.8) and (4.2.9). Let X β be the random variable distributed by π β . Then π β satisfies the fixed point equation

	Proposition 4.4.

  Let us consider the Random Weighted allocation policy, where the allocation function Ψ RW is given by Equation (4.2.4). For a fixed β, we denote the studied process as defined in Section 4.2.2 by (X RW

	β	(t)). As
	a first step, we prove the process (X RW

β

(t)) exists. Then, we study the convergence in distribution of the process in equilibrium as β tends to infinity. Theorem 4.5. For a given β > 0, under the Random Weighted allocation policy and linear rate of breakdowns, the process (X RW β (t)) exists. In other words, there exist π β and α that satisfy Equations (4.2.8) and (4.2.9).

Proof: Following from Proposition 4.4, we consider ν(σ) as defined in (4.2.10). We study the existence and uniqueness of the solution of the fixed point equation π β = ν(π β ), and of α(π β ), which we will denote α as an abuse of notation. Let X RW β denote the random variable distributed by π β , and recall that E(X RW β ) = β. Since we consider Ψ RW and f

Acknowledgements

like to thank EDSYS for funding my Ph.D., INP and LAAS, for funding the conferences and the research visits, and Yezekael Hayel and Université

with ∆ > 0, then, the bandit is indexable. Equation (3.4.11) will be proved below.

First assume W < 0. Then, by Proposition 3.22, the optimal threshold policy is (-1, -1). In W = 0 it turns to (0, 0), and for W > 0 it is of the form (n, 0). Hence, for W ≤ 0, (3.4.11) holds. Now assume 0 ≤ W < W (2) . If W + ∆ > W (2) , then the inequality (3.4.11) is trivially true. Now assume W + ∆ < W (2) . By Proposition 3.22, it follows that there are n and n such that n(W ) = (n, 0) and n(W +∆) = (n , 0). Since the function g(W ) is a lower envelope, the linear function g (n ,0) (W ) has a steeper slope than the linear function g (n,0) (W ), as it can be seen in Figure 3.1. Furthermore, in Proposition 3. [START_REF] Çinlar | Introduction to Stochastic Processes[END_REF] we proved that the slope of the linear functions g (n,0) (W ) is non-increasing in n. Therefore, n ≤ n , and (3.4.11) holds.

Finally, for W ≥ W (2) , the optimal threshold policy is (∞, ∞), hence n d (W ) = ∞ for both d = 1, 2, and (3.4.11) is trivially true.

2

In order to prove Theorem 3.15, we first show that threshold policy (∞, 0) is an optimal solution of (3.3.1)

when W ∈ W (1) , W (2) .

Proposition 3.24. The threshold policy (∞, 0) is an optimal solution of (3.3.1) when W ∈ W (1) , W (2) . If W ∈ (W (1) , W (2) ), then it is the unique optimal threshold policy. If W = W (2) , then any threshold policy (∞, n) with n ≥ 0 is optimal, and no other threshold policy is.

Using Propositions 3.22 and 3.24 we can prove Theorem 3.15.

Proof of Theorem 3.15: Recall that the Whittle's index of a state (m, d) is the smallest value for the subsidy W such that the optimal threshold policy makes that state passive.

First consider states (0, d). From Proposition 3.22, we have that in state 0 it is optimal to be active when W < 0 and passive if W = 0. Hence, we have that W (0, d) = 0, for both d = 1, 2. Now consider states (m, 2), with m > 0. From Proposition 3.24, we have that for W ∈ (W (1) , W (2) ) the unique optimal threshold policy is (∞, 0). For W ≥ W (2) , the optimal threshold policy is (∞, ∞), since it is the steepest one. Hence, W (2) is the smallest value for the subsidy W such that in state (m, 2) the optimal action is to be passive, that is, W (m, 2) = W (2) for every m ≥ 0. Now consider states of the form (m, 1), with m > 0. Note that for W = 0, in state 0 it is optimal to be passive, and for W ∈ (W (1) , W (2) ) the optimal threshold policy is (∞, 0). As a consequence, and since the bandit is indexable, when 0 ≤ W < W (2) , an optimal threshold policy is of the form (n, 0). Algorithm 3.4 characterises Whittle's index by iteratively defining Ŵj . From Proposition 3.22, we have that for W < 0 the unique optimal threshold policy is n -1 = (-1, -1), and for W = 0 the optimal threshold policies are (-1, -1), (-1, 0), (0, -1) and (0, 0). Hence, Ŵ0 = 0. Furthermore, since the bandit is indexable, for W ≥ 0 it is optimal to be passive in state 0. Therefore, among those four threshold policies, the optimal threshold policy in the interval [0, Ŵ1 ] is n 0 = (0, 0). Then, in W = Ŵ1 the linear function of the following optimal threshold policy (n 1 , 0) crosses the linear function g (0,0) . Inductively, the increasing sequence (n j ) j≥0 , provides the set of minimising policies inside the set {(n, 0)} n≥0 . As a consequence, in order to determine the smallest value of W such that the optimal threshold policy makes a state (m, 1) passive, it is enough to determine the value j such that n j-1 < m ≤ n j . In other words, W (m, 1) = W ((n j-1 , 0), (n j , 0)) for any j and n j-1 < m ≤ n j . k (m). For the latter policy, the median is 4% and the 75th percentile is 15% for the common environment setting (vs. 0% both values for Whittle's index policy), and the median is 3% and the 75th percentile is 9% for the independent environments setting (vs. 0% and 2% for Whittle's index policy).

Particular example

From the above plots, we conclude that even in a common environment, Whittle's index performs rather well. Below we show that this is not always the case. We obtain a set of parameters such that Whittle's index policy has a good performance when the environments are independent, but it performs bad when the environments are common for both bandits.

We choose the following parameters: the arrival rates are λ

and hence independent of the environment. The departure rates are µ

2 , for each environment d. The abandonment rates are θ

2 , for each environment d. These parameters satisfy the following inequalities:

As such, when the environment is in state (D 1 (t), D 2 (t)) = (1, 1), the indices (relation 1) indicate that preference is leaning towards serving class 1. This is surprising, since the departure rate for class 1, , 2000]. We consider 200 sets of parameters for each boxplot. In this case we observe that the suboptimality gap of policy W (m, d) is still small, below 1% in both boxplots and in both settings. The median of the suboptimality gap of policy W (m) for the random parameters (left) is 9% for the common environment setting, and 12% for the independent environments setting, and for the constrained parameters (right) is 24% for the common environment setting, and 20% for the independent environments setting.

We conclude that in both regimes, with normal speed and with fast speed, there is an important loss in performance if we consider an unobservable policy. We obtained medians above 7% when the parameters are chosen at random, and above 20% when the optimal policy depends strongly on the state of the environment.

for n ∈ E j . By Lemma 3.6 and since M n(β) is uniform integrable, we have that f j ( n) is equal to

.

Hence, equivalently, we can write

.

By definition of n(j+1) and since n j+1 (β) = nj+1 for β small enough, f j ( n) is minimized in nj+1 , that is,

In particular, this implies,

)), that is,

, . Hence, by contradiction we proved that the inequality in (3.7.5) is an equality, that is,

Assume without loss of generality that

). We are left to prove that

Let n * 1 be the n such that the infimum is taken on the RHS. Hence, the RHS can equivalently be written as f j (n * 1 , nj 2 ). We prove (3.7.8) by contradiction. That is, assume

, we have contradiction with the fact that f j is minimized in nj+1 . Combining (3.7.4), (3.7.7), and (3.7.8), we conclude the proof. 2

policy n when starting in state (m, d). Then V n,L t satisfies the relation

Let G n L denote the expected reward for the truncated processes, and, using result 9.3.2 in [19, Chapter 9], we will prove that

(3.7.18)

In order to apply result 9.3.2 in [19, Chapter 9], we need to prove that for all states (m, d) and t ≥ 0,

, and

, for any (m , d ). Thus the inequality holds directly. It remains to check the state (m, d) = (n 1 + 1, 1). The only difference in rates between q (n1+1,n2),L and q (n1,n2),L is the transition to state (n 1 , 1). Hence, inequality (3.7.19) simplifies to

or equivalently,

By induction, we can prove the following more general result. For ease of reading, its proof appears in Appendix 3.7.3.

Lemma 3.28.

With this Lemma, the proof for the truncated processes is done and (3.7.18) holds. To generalize this for the original processes with unbounded rates we use the following result from [26, Theorem 3.1]. There exist

So C n (m, d) = 1 in the passive states, regardless the environment. As a result, the reward per unit time is

, which is the term to compare between the truncated processes. We consider the costs C (n,0) , C (n+1,0) and the transition rates q (n,0),L , q (n+1,0),L for the truncated processes under policies (n, 0) and (n + 1, 0), respectively. Then Inequality (3.7.19) has to be proved for all the states where C (n+1,0) and C (n,0) or q (n+1,0),L and q (n,0),L are not the same. This happens in the states that are active under one policy (n, 0) and passive under the other one (n + 1, 0), i.e., in state (n + 1, 1). The inequality to prove reduces to

for t ≥ 0. As before, we prove a more general result, as stated in Lemma 3.34.

Lemma 3.34. Under Condition 3.12, Chapter 9] can be applied, and we obtain

for the truncated processes. Using the same reasoning as in the proof of Property 1) in Lemma 3.11, we obtain that this property holds as well for the original (untruncated) process. 2

Proof of Lemma 3.34.

The proof is similar to the one in Section 3.7.3. To simplify notation, since (n, 0) and L are fixed in the lemma, we will write V t for V (n,0),L t and H for H(L). The proof goes by induction, and the cases of t = 0 and t = 1 are the same as before. We assume (1) for every (m, d). We prove it now for t + 1. We first consider the state (0, 2).

APPENDIX CHAPTER 4. ALLOCATION IN LARGE SCALE SYSTEMS

particular allocation policy, which may be deterministic or randomly distributed. Urn models are frequently used in theoretical computer science to study the efficiency of algorithms, for example, for the allocation of copies of files in large distributed systems [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF][START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF], or the allocation of tasks to processors in large scale computing networks [START_REF] Karthik | Choosing among heterogeneous server clouds[END_REF][START_REF] Maguluri | Stochastic models of load balancing and scheduling in cloud computing clusters[END_REF].

We refer to the urn model studied in [START_REF] Sun | Analysis of large urn models with local mean-field interactions[END_REF], where after an exponentially distributed amount of time all the balls in one urn are reallocated to different urns. Each ball is reallocated to an urn chosen by a random variable, and the random variables used to choose the urns are independent. Under this setting, in [START_REF] Sun | Analysis of large urn models with local mean-field interactions[END_REF] the authors study the local mean-field interactions between urns when the number of urns grows large, and they prove the convergence of the distribution of the load of each urn under certain conditions.

Another relevant work we cite is [START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF], where a model of replication for large storage systems is studied. The authors consider nodes that break down after an exponential distributed amount of time with constant rate, and whenever a breakdown occurs, all the files in that node are reallocated to other nodes. Each file goes to a node chosen at random according to an allocation policy, and the random variables that select the nodes for each file are independent. Different allocation policies are analysed, in particular one that consists in choosing uniformly at random two nodes, and reallocating the file to the least loaded node among them.

This policy is known as the Power of Choice, and it has been largely studied, see [START_REF] Richa | The power of two random choices: A survey of techniques and results[END_REF] for a survey. In [START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF] two limits are considered, in first term the number of nodes grows large, and in second term the average load per node is taken to infinite. Their striking result is that under the Power of Choice policy the distribution of the load of a node has a finite support.

We remark that modelling breakdowns with constant rates, as it is done in [START_REF] Sun | Analysis of a stochastic model of replication in large distributed storage systems: A mean-field approach[END_REF], does not consider that the level of activity of a node directly affects its lifespan. The novelty of our work relies in considering times of failures determined by the amount of data a node handles. The more tasks it has to process, the faster it breaks down. To the best of our knowledge a few works are done under this setting. We refer here to Schechner's work [START_REF] Schechner | A load-sharing model: The linear breakdown rule[END_REF], inspired in Coleman's load-sharing model [START_REF] Coleman | A stochastic process model for mechanical breakdown[END_REF]. The author studies nodes with breakdown rates that are linear in their current charge, but it is not applied in replication mechanisms.

In this chapter we consider the following system. There are files distributed among nodes, where each file remains in its node until the node breaks down. Each node breaks down at a rate that depends on the number of files it has. When this happens, all the files present in the broken node are reallocated, and the node goes back to the state with zero files. For the ease of the tractability of the model we assume that the reallocation step is done at once for all the files in the node and it does not take time.

When a breakdown occurs, each file is allocated following a random variable. The random variables used for the reallocated files are independent and identically distributed, and we will state the model for any arbitrary distribution. For our main results, we will consider the Random Weighted policy, that assigns to each node a weighted probability of receiving a file according to the load it currently has. We will further study the Random policy as a particular case of the Random Weighted policy, where all the nodes have the same weight. In this case we provide a deeper insight.

Under these dynamics, we analyse the evolution of the storage load of a single node in the long term. We consider the case where the total number of nodes and the total number of files grow large. We make the scaling assumption that the average number of files per node converges to a real value, denoted by β. This is known as the mean-field limit. We will not study the convergence to the mean-field limit, but we focus on it, and in particular, on the evolution of the process in the mean-field regime.

We introduce our main results. In our first main contribution, we prove the existence of the process describing the mean-field limit for a fixed β. In this same theorem we prove the existence and uniqueness of the stationary measure of the process. In our second contribution, we let β tend to infinity, and we prove the convergence in distribution of the load in steady state. Finally, for the Random policy we obtain an expression of the generating function of the load in steady state. Our main results are done for the case where the rate of the breakdowns is linear in the number of files each node has.

The chapter is organised as follows. In Section 4.1 the stochastic model and the allocation policies are described for a fixed number of nodes. The mean-field model used to study the large scale system is presented in Section 4.2. Our main results are introduced in Section 4.3. In Section 4.3.1 we consider the Random Weighted policy, and in Section 4.3.2 we state the results for the Random policy.

Model description

We describe the model for a fixed number of nodes. Let N 0 = {0, 1, . . .} denote the set of non-negative integers. We consider a system with N nodes indexed by i = 1, . . . , N , and F N files distributed among the nodes, with F N N . The state of the system is described by a vector l = (l 1 , . . . , l N ) ∈ S N , with

For i = 1, . . . , N , l i is the amount of files in node i.

Let f : N 0 → R + be an increasing function, which determines the rates of the breakdowns of the nodes. If l is the current state of the system, node i waits an exponentially distributed amount time of rate f (l i ) until it fails. For our main results in Section 4.3 we will assume that the rate of the breakdowns is linear, i.e., f (n) = cn, for some c > 0.

When node i breaks down, all the l i files present in the node are reallocated to other nodes at random, and node i goes back to state 0. The reallocation step does not take time and it is done at the same time for all the l i files.

For each reallocated file we consider a random variable that selects the destination node with a probability that depends on the current state of the system l. We assume that the random variables used to select the destination nodes are independent and identically distributed. If the state of the system is l, let p N ij ( l) denote the probability that a given file in node i is reallocated to node j, and P N i ( l) := p N i1 ( l), . . . , p N iN ( l) the probabilities of reallocation from node i to the rest of the nodes. Note that when node i breaks down and the state of the system is l, the reallocation of the files present in node i are l i independent events. Then, if

denotes the number of files of node i allocated to node j, Z N ij ( l) follows a binomial distribution with parameters l i and p N ij ( l). We introduce the notation for the process. The state of the system at time t is denoted by a càdlàg process

is the number of copies on server i at time t. We let Γ N (t) be the empirical distribution of the process, defined as

for any A ⊂ N 0 . Γ N (t)(A) is the fraction of nodes having a number of files in set A at time t.

The evolution of the process L N (t) depends on the times of the breakdowns of the nodes, and the rates of the breakdowns depend themselves on the state of L N (t). As a consequence, a full description of the evolution of L N (t) involves the use of complex non-stationary Poisson processes (see [START_REF] Tijms | Stochastic modelling and analysis: a computational approach[END_REF]Chapter 1.3] for a definition), which we do not address in this chapter. Nevertheless, we describe here the possible transitions of the process L N i (t) for a given i, based on the exponential rates it follows. Fix i ∈ {1, . . . , N }, and consider the process L N i (t) in N 0 . The process has transitions given by two classes of events: a) when node i breaks down, and b) when node i receives files from the breakdowns of other nodes.

a) If at a given time t, the process L N i (t) = l i , node i breaks down at rate f (l i ) and it spreads all its files. In other words, the transition l i → 0 occurs at rate f (l i ).

b) If at a given time t, the whole system is in state L N (t) = l, any of the other nodes m = 1, . . . , N , m = i, may break down an allocate one or more of its l m files to node i. The breakdown of node m occurs at rate f (l m ), and when this happens, Z N mi ( l) files are allocated to node i, where Z N mi ( l) is a binomial random variable with parameters l m and p N mi ( l). Then, the process L N i (t) makes the transition

Allocation policies

For our main results, we will consider two allocation policies, the Random Weighted allocation policy and the Random policy.

For the Random Weighted allocation policy we set a non-increasing weight function W : N 0 → (0, K] for some constant K > 0. Then, for a given node i and state l, we define the probabilities p N ij ( l) as:

defines a probability on the set {1, . . . , N }. The Random policy is a particular case of the Random Weighted policy where W is constant. In other words, for a given node i and state l, the probabilities p N ij ( l) are

if j = i, and p N ii ( l) = 0.

Mean-field limit

The focus of our work is on the mean-field limit of the process, i.e., the regime where N tends to infinity.

We make the scaling assumption that the average number of files per node converges to a value β > 0, i.e.:

We will not study the convergence to the mean-field limit, but the limiting process of the load of a single node in such regime. In Section 4.2.1 we provide the conditions assumed in order to consider the mean-field regime. In Section 4.2.2 we describe the limiting process.

Conditions for convergence

The following condition is regarding the initial state L N (0).

Condition 4.1.

• For all N , the distribution of the vector L N (0) satisfies the following exchangeability relation:

• The sequence of initial distributions ( L N (0)) N ∈N converges to a probability distribution on N 0 .

We describe now the asymptotic behaviour of the probabilities of reallocation P N 1 (•) as N grows large. We define an allocation function Ψ : M (N 0 )×N 0 → R, where M (N 0 ) denotes the set of probability distributions on N 0 . For a given σ ∈ M (N 0 ) and l ∈ N 0 , if the load of the nodes is identically distributed by σ, the probability of allocating a file to a node currently having l files is of the order of Ψ(σ, l)/N , as it is stated in the following condition.

Condition 4.2. The sequence

where Ψ is a non-negative bounded function on

3) is a mass conservation condition: when a node breaks down, every file is reallocated with probability 1.

Proposition 4.3. For the Random Weighted policy, the allocation function Ψ RW is

For the Random policy, the allocation function

Proof: Following from the definition of the allocation probabilities in Equations (4.1.1) and (4.1.2), we show that both functions Ψ RW , Ψ R satisfy Condition 4.2.

In the Random Weighted case, for the expression in Equation (4.2.2) we have

where the last inequality follows from the fact that, for a given l, δ lj (k) = 1 if and only if k = l j . Since the total number of nodes grows large together with the number of files, the limit in N in Equation (4.2.6) equals 0. It is easy to see that Equation (4.2.3) holds for Ψ RW .

In the Random case, in Equation (4.2.2) we have

where for the last inequality we use that 1 N N j=1 δ lj is a probability distribution, and it is evaluated over N 0 . The limit in N in Equation (4.2.7) equals 0. It is straightforward to see that Equation (4.2.3) holds for Ψ R . 2

Limiting process

We introduce now our main problem. We study the existence of the process as the possible limit of (L N 1 (t)) N ∈N as N grows large. This process will be denoted by (X β (t)). We first provide an informal Throughout this thesis we studied resource allocation problems in large-scale stochastic systems. The mathematical framework used was the Markov Decision Processes (MDPs), and, in particular, we focused on a subclass of MDPs known as Multi-armed restless bandits problems (MARBP). We worked on problems with conditions that fluctuate over time. This was modelled considering two types of processes, controllable processes and environments. The current state of the environment determines the value of the parameters of the controllable processes. We differentiated whether the environment can be observed or not, and under both settings we looked for efficient control policies in a long-term average criterion. We further studied a model of large-scale storage systems with files distributed across nodes. After a node breaks down, all the files it had are reallocated to other nodes. We analysed the evolution of the load of a single node.

Our main contributions encompasses a range of results on optimal control and on the performance of allocation policies. For our first problem we considered an MARBP with unobservable environments. We studied the asymptotic regime, as the number of bandits grows large together with speed of the environment.

In Theorem 2.5 we provided sufficient conditions for a policy to be asymptotically optimal, and we defined a set of priority policies that satisfies these. When the technical condition known as indexability holds, an averaged version of Whittle's index is inside the set of priority policies, see Proposition 2.13. The second problem we considered is an MARBP with observable environments. We focused on the relaxed version of the problem, and we proposed Algorithm 3.4 to determine Whittle's index. For the problem of a queue with abandonments we prove that indexability holds in Theorem 3.14, and we derive the Whittle's index in closed-form in Theorem 3.15. In both problems we delivered a numerical evaluation to show the performance of the obtained policies. For the problem of large-scale storage systems, we focused on the mean-field regime as the number of nodes and files grows large. By studying the global balance equations, we proved the existence of the process in the mean-field regime, in Theorem 4.5. We further showed the 103 convergence in distribution of the load in steady state as the average number of files per node tends to infinity, in Theorem 4.7.

Impact of observability

One of the motivations of this thesis was to study the implications of observability or unobservability on Whittle's index. Numerically we analysed this impact in Sections 2.5.5 and 3.6.3. Table 5.1 summarises our main theoretical characterisations in each of the cases.

In the unobservable case, we proved in Proposition 2.13 that the averaged Whittle's index policy is asymptotically optimal in a fast environment as the number of bandits grows large. In the case of queues with abandonments, the averaged Whittle's index reduces to the index µ k /θ k , where µ k is the averaged service rate and θ k is the averaged abandonment rate of bandit k. We leave for future work the problem of optimal control with environments that vary relatively slow or with normal speed. In Section 5.2.2, we present some ideas in this direction.

In the observable case, we considered policies that can depend on the current state of the environment d ∈ Z, and this is reflected in our results. Algorithm 3.4 provides expressions for the Whittle's index in the general setting. In particular, we proved in Proposition 3.8 that when the environment is slow the Whittle's index coincides with the Whittle's index of a bandit that only sees environment d. We denoted this index by W k /θ k . We make the remark that this index remains dependent on state d of the environment, in contrast to the index in the unobservable model, which takes both averaged parameter values.

As a general conclusion, the results for the observable case are more complete than for the unobservable case. We comment further on this in the next section. an area of research that recently received a lot of attention, a full overview can be found in the textbook [START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

Q-learning

We refer here to Q-learning, a technique used to find optimal control for MDPs without specific knowledge of its transition rules. In Q-learning, the expected one-step reward is estimated for each state and action, by repeating many episodes of the process and updating the followed policy according to observations. Such technique can be explored for an MARBP with unobservable environments in order to learn the optimal policy, at least numerically. As the experiment is run several times, under ergodicity assumptions, all the states of the environments are visited. Learning from these transitions allows to obtain an estimation of the evolution of the process.

For a theoretical approach, a reference in this subject is [START_REF] Fu | Towards Q-learning the Whittle Index for Restless Bandits[END_REF]. The authors adapt the Q-learning technique to obtain Whittle's index in a MARBP with unknown transition matrices. They show that the derived policy performs close to the fully-informed Whittle's index policy.

Observable environments: Whittle's index in slow regime

In Proposition 3.8, we proved that, when the environment is slow, Whittle's index coincides with the index of a bandit that only sees a fixed environment d ∈ Z. In the proposition, and in previous results, we used the technical assumption that the environment visits only two states, i.e., |Z| = 2. Although we were not able to extended the result for |Z| > 2, we believe it holds, and it remains as further research.

Observable environments: optimality for correlated environments

In the classical MARBP theory, the bandits are assumed to be independent. In the model in Chapter 3, the bandits are formed by the controllable processes and the environments. When the environments are independent, we can conclude that the bandits are independent, and their state is a two-dimensional state of a classical bandit. This means that the classical MARBP theory applies, and the associated results hold, such as the asymptotic optimality of Whittle's index policy proved in [START_REF] Weber | On an index policy for restless bandits[END_REF].

However, in case the environments are not independent, the previous statement is not true, and some research questions arise.

• A first question to address is how efficient is Whittle's index policy in the MARBP. In Section 3.6.1 we presented a numerical evaluation with random samples to study the performance of Whittle's index policy in such a setting. Our results suggest that it has a good performance. We would like to further study whether Whittle's index policy is asymptotically optimal, as the number of bandits that can be made active grows proportionally to the total number of bandits.

• An alternative line of research follows if we consider a non-relaxed approach to solve the problem. A course of action on this direction would be to study the equilibrium solutions of the linear-programming problem derived from the fluid dynamics of the system, as it is done for the MARBP in [START_REF] Verloop | Asymptotically optimal priority policies for indexable and nonindexable restless bandits[END_REF].