Urtzi Ayesta

Manu K Gupta
email: manu.gupta@ms.iitr.ac.in

Ina Maria Verloop

On the computation of Whittle's Index for Markovian restless bandits

Keywords:

The multi-armed restless bandit framework allows to model a wide variety of decision-making problems in areas as diverse as industrial engineering, computer communication, operations research, financial engineering, communication networks etc. In a seminal work, Whittle developed a methodology to derive well-performing (Whittle's) index policies that are obtained by solving a relaxed version of the original problem. However, the computation of Whittle's index itself is a difficult problem and hence researchers focused on calculating Whittle's index numerically or with a problem dependent approach.

In our main contribution we derive an analytical expression for Whittle's index for any Markovian bandit with both finite and infinite transition rates. We derive sufficient conditions for the optimal solution of the relaxed problem to be of threshold type, and obtain conditions for the bandit to be indexable, a property assuring the existence of Whittle's index. Our solution approach provides a unifying expression for Whittle's index, which we highlight by retrieving known indices from literature as particular cases. The applicability of finite rates is illustrated with the machine repairmen problem, and that of infinite rates by an example of communication networks where transmission rates react instantaneously to packet losses.

Introduction

Markov Decision Processes (MDPs) provide a mathematical framework for sequential decision making where outcomes are random. Formally, an MDP is a sequential stochastic control process, where a decision maker aims at minimizing its long term cost. The basic setup is as follows, at each time step, a state dependent cost is accrued, the decision maker chooses an action among the available ones, and the process randomly moves to a new state. Due to their broad applicability, MDPs are found in many areas, including artificial intelligence, economics, and operations research.

An MDP can be solved via dynamic programming, however, this is a computationally intractable task for realistic model sizes. As a result, classes of MDPs that are analytically tractable have received a lot of attention. One such class is the Multi-Armed Bandit Problem (MABP) framework. In an MABP, there are multiple concurrent projects or bandits. The decision maker knows the states of all bandits and the cost in every state, and aims at minimizing the average cost. At every decision epoch, the decision maker needs to select one bandit, the state of this selected bandit evolves stochastically, while the states of all other bandits remain frozen. In a ground-breaking result, Gittins showed that the optimal policy that solves an MABP is an index rule, nowadays referred to as Gittins' index policy [START_REF] Gittins | Multi-armed bandit allocation indices[END_REF]. Thus, for each bandit, one calculates Gittins' index, which depends only on its own current state and stochastic evolution. The optimal policy activates the bandit with highest current index in each decision epoch.

The Restless Multi-Armed Bandit Problem (RMABP), introduced in [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF], is a more general class of problems, in which the states of non-selected bandits also evolve randomly. That is, in contrast with an MABP, here the non-selected bandits do not remain frozen. RMABPs have become extremely popular over the years, and have been applied in many contexts, including inventory routing, machine maintenance, health-care systems, outsourcing warranty repair, etc. RMABPs can not be solved analytically, except for some toy examples. Whittle developed a methodology to obtain heuristics by solving a relaxed version of the RMABP. The obtained heuristics, nowadays known as Whittle's index policy, rely on calculating Whittle's index for each of the bandits, and activating in every decision epoch the bandit with highest Whittle's index. It has been reported on numerous instances that Whittle's index policy provides strikingly good performance, and it has been shown to be asymptotically optimal as the number of bandits grows large.

Fundamental questions regarding Whittle's index policy concern their existence and their complexity in computation. To prove existence, one needs to establish a technical property known as indexability. Computing Whittle's index might be involved, and in practice the indices are computed on a problem-to-problem basis (see more in Section 1.1), either numerically or analytically.

An important feature of the present paper is that -in addition to actions that yield finite transition rates -we allow for actions that induce infinite rates, which in the literature is often referred as impulsive controls. In contrast with finite rates that yield transition after an exponentially distributed random time, an impulse control induces an instantaneous transition. Impulsive controls have historically received less attention than the continuous control case. However, they do appear naturally in several application domains such as epidemiology, reliability theory, inventory control, and congestion control in communication networks. We refer the interested reader to [START_REF] Dufour | Impulsive control for continuous-time markov decision processes: A linear programming approach[END_REF] for a brief survey on MDPs with impulsive control. In order to calculate Whittle's index in the case of infinite rates, we reformulate the problem with impulse cost to a problem with only cost per unit of time. A similar approach has been exploited in the past in the analysis of continuous time MDPs with impulsive controls, see for example [START_REF] Piunovskiy | On reducing a constrained gradual-impulsive control problem for a jump markov model to a model with gradual control only[END_REF] for the case of a constrained MDP.

In this paper, we focus on the average performance criterion (as presented in the original paper by Whittle). We allow both finite and infinite rates at which a bandit changes state. In Section 2 we present the model and explain how a problem with infinite rates can be reformulated as an equivalent problem with only finite rates. In Section 3 we present a general algorithm that, although computationally demanding, determines whether the problem is indexable and calculates the index for any RMABP with multi-dimensional state space. For a one-dimensional bandit, we then derive sufficient conditions for a problem to be indexable and for the optimal solution to a RMABP to be of threshold type. In Section 4, we show our main result that if threshold policies are optimal and if a certain monotonicity condition holds, Whittle's index can be expressed as a function of the steady-state distribution. In Sections 5 and 6, we apply our unifying characterization to several problems considered in the literature to show that they are indexable, that threshold policies are optimal, and finally to retrieve Whittle's index as a direct application of our unifying analytical expression. In particular, in Section 6.1 we consider the problem of transmitting data over the Internet, as an example of important application in which impulse controls arise naturally, see [START_REF] Avrachenkov | Impulsive control for g-aimd dynamics with relaxed and hard constraints[END_REF].

Related literature

A classical reference for MDPs is Puterman [2014], and a comprehensive coverage for MABP and RMABP is given in [START_REF] Gittins | Multi-armed bandit allocation indices[END_REF]. Book length treatments of restless bandits can be found in [START_REF] Jacko | Dynamic priority allocation in restless bandit models[END_REF] and [START_REF] Ruiz-Hernandez | Indexable restless bandits: Index policies for some families of stochastic scheduling and dynamic allocation problems[END_REF]. A discussion on the nearly-optimal performance of Whittle's index is given in Niño-Mora [2007], and asymptotic optimality of Whittle's index as the number of bandits grows is shown in Weber and [START_REF] Richard | On an index policy for restless bandits[END_REF], Verloop [2016]. Further restless bandit formulation has been used in diverse domains (see [START_REF] James | Developing effective service policies for multiclass queues with abandonment: asymptotic optimality and approximate policy improvement[END_REF], [START_REF] Abbou | Group maintenance: A restless bandits approach[END_REF]).

For average cost criterion and with a countable state space, [START_REF] Niño-Mora | Restless bandit marginal productivity indices, diminishing returns, and optimal control of make-toorder/make-to-stock M/G/1 queues[END_REF] gives sufficient conditions for an RMABP to be indexable and provides an analytical expression (same as ours) for the Whittle index. One of the conditions consists in showing that the so-called marginal workloads are strictly positive for any set of states. This ensures that optimal policies are of threshold type. Instead, in this paper, we provide an algorithm that does not require threshold optimality, as might be of interest when a bandit lives in a multi-dimensional state space and threshold optimality might be impossible to establish. In addition, in the case when threshold optimality can be established independently, we show that a weaker assumption on the marginal workloads is sufficient for the results to hold.

Even though Whittle's seminal work introduced Whittle's index within the context of average cost criterion, a large body of work has focused on tackling an RMABP under the total discounted cost criterion. For the discounted cost criterion and finite state space, Niño-Mora [2007] provides a thorough analysis and efficient algorithms (based on linear programming) to establish indexability and to give an expression for Whittle's Index. The same approach was undertaken to obtain the Whittle's index for a general RMABP in [START_REF] Niño-Mora | Restless bandit marginal productivity indices, diminishing returns, and optimal control of make-toorder/make-to-stock M/G/1 queues[END_REF].

As explained in the introduction, the analytical computation of the index has mostly been carried out on a problemto-problem basis. The main idea to calculate them is to sweep the state space, by recursively identifying and calculating the states with higher Whittle's indices. This can be done by iterative schemes as for example in Borkar and Pattathil [2017] for a processor sharing queue, Borkar et al. [2017b] in a problem of cloud computing, Borkar et al. [2017a] for a scheduling problem in a wireless setting, and [START_REF] Pattathil | Distributed server allocation for content delivery networks[END_REF] in the context of content delivery networks. And in some particular cases analytically, see for example [START_REF] Tanik Argon | Dynamic routing of customers with general delay costs in a multiserver queuing system[END_REF] for a load balancing problem with dedicated arrivals, [START_REF] Opp | Outsourcing warranty repairs: Dynamic allocation[END_REF] for outsourcing warranty repairs, [START_REF] Ayer | Prioritizing Hepatitis C treatment in US prisons[END_REF] for Hepatitis C Treatment in US Prisons, and [START_REF] Larrañaga | Dynamic control of birth-and-death restless bandits: application to resource-allocation problems[END_REF] for restless bandits that are of birth and death type. Another popular approach in the literature to calculate the index for the average cost criterion has been to calculate first the index for the discounted case, and then let the discounting factor tend to one. This is the approach undertaken in e.g. [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF] for the machine repairman problem, [START_REF] Ps Ansell | Whittle's index policy for a multi-class queueing system with convex holding costs[END_REF] for a multi-class queue with convex holding costs, and Nino-Mora [2002] for a queue with admission control. A feature that renders the discounted problem more amenable is that the dynamic programming equation of the MDP has only one unknown, the value function, whereas for the average cost criterion, the dynamic programming equation has two unknowns, one being the value function and the other one the average performance [START_REF] Martin L Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]).

In this paper, we take a direct approach and work directly with the average cost criterion. This will allow us to obtain a unifying framework to write an analytical expression for the Whittle's index. As we will explain in Sections 5 and 6, all applications mentioned above for which Whittle's index was found are particular instances of our unifying approach. Note that this includes the examples for which Whittle's index was so far only calculated by iterative numerical scheme.

The large majority of the literature on Whittle index has focused on problems without impulsive control. A notable exception is [START_REF] Ford | On the dynamic allocation of assets subject to failure[END_REF] which studies the dynamic allocation of assets under a total cost criteria. In order to derive Whittle's index, [START_REF] Ford | On the dynamic allocation of assets subject to failure[END_REF] first invokes results from [START_REF] Dufour | Impulsive control for continuous-time markov decision processes[END_REF] in order to reformulate the problem in which impulse controls are replaced by actions that do not lead to an immediate transition.

Model description

We consider an RMABP with K ongoing projects or bandits. At any moment in time, bandit k, k = 1, ..., K, is in a certain state n k ∈ N d , with d ∈ N + . Decision epochs are defined as the moments when one of the bandits changes its state. At each decision epoch, the controller decides for each bandit to either make the bandit passive, action a = 0, or to make the bandit active, action a = 1. The latter needs to be done such that some constraint on the number of bandits that are activated is satisfied, as will be discussed below.

Throughout this paper, we consider bandits that are modeled as a continuous-time Markov chain, that is, when bandit k is in state n k , it changes the state after an exponentially distributed amount of time. Transition rates for bandit k, which can either be finite or infinite, depend only on the bandits' state n k and the action chosen for this bandit. Let I k (n k , a) be an indicator function for the event of an infinite (impulse) transition for bandit k at state n k under action a, i.e., I k (n k , a) := 1 if state changes instantaneously, 0 otherwise.

If I k (n k , a) = 1, let p a k (n k , m k ) be the probability of making an immediate transition to state m k from state n k . If I k (n k , a) = 0, let q a k (n k , m k ) be the finite transition rate of going from state n k to m k under action a ∈ {0, 1}. Note that the state of a bandit can evolve both when being active and passive, and this does not depend on the states/actions of other bandits. Hence, given the action taken, the dynamics of each bandit is independent of the others.

A policy φ decides which bandits are made active. Because of the Markovian property, we focus on policies which base their decision only on the current states of the bandits. For policy φ, N φ k (t) denotes the state of bandit k at time t, and N φ (t) = (N φ 1 (t), . . . , N φ K (t)). Let S φ k ( N φ (t)) ∈ {0, 1} represent whether or not bandit k is made active at time t, that is, it equals 1 if the bandit is activated, and 0 otherwise.

For bandit k, let f k (n k , a) be a function of state n k and action a and assume it is bounded by a polynomial in n k . Further assume that if

I k (n k , a) = 1, then f k (n k , a) = 0. A policy φ is called feasible if it satisfies the following constraint: K k=1 f k (N φ k (t), S φ k ( N (t))) ≤ M, (1)
where M is some given constant. That is, (1) gives a constraint on the number of activated/passive bandits resulting in finite transition rates. We denote by U the set of policies that satisfy the constraint (1) and make the system ergodic. We assume that such a policy exists, hence U is non-empty.

Since

f k (n k , a) = 0 if I k (n k , a) = 1
, it is obvious that there is no constraint on the number of impulses at a given time t (we refer to Remark 2.1 for a discussion on the control of impulses). For non-impulsive control, setting

f k (N φ k , S φ k ( N )) = S φ k ( N ), the constraint (1) reduces to K k=1 S φ k ( N ) ≤ M ,
that is, at most M out of K bandits can be made active. This is a slight variation of the classical restless bandit problem, where exactly M bandits need to be activated at any time t 1 . Another interesting function is when f k (N φ k , S φ k ( N )) represents the expected capacity occupation (volume), in which case the constraint (1) reduces to the family of sample-path knapsack capacity allocation constraints as recently explored in [START_REF] Jacko | Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic[END_REF], [START_REF] Graczová | Generalized restless bandits and the knapsack problem for perishable inventories[END_REF]. Let C k (n k , a) denote the cost per unit of time when bandit k is in state n k and is either passive (a = 0) or active (a = 1). Let L ∞ k (n k , m k , a) be the lump-sum cost when bandit k under action a immediately changes state from n k to m k . We assume that both C k (n k , a) and L ∞ k (n k , m k , a) can be bounded by a polynomial in n k and m k . Instead of a lump-sum cost L ∞ k (n k , m k , a), we will work with C ∞,φ k ( n, a), which is defined as the cost per unit of time due to impulse transitions when policy φ is implemented, we are in state n and action a is taken. This is given by

C ∞,φ k ( n, a) := ñk m k q a k (n k , ñk ) × I k (ñ k , S φ k ( M k ( n, ñk ))) ×p S φ k ( M k ( n,ñ k )) k (ñ k , m k ) × L ∞ k (ñ k , m k , S φ k ( M k ( n, ñk )) ,
where M k ( n, ñk ) equals the state n in which the kth component of n is replaced by ñk . This can be seen as follows. The cost per unit of time due to impulse transitions consists of the transition rate at which you go to an impulse situation, times its corresponding lump-sum cost. Regarding the first, we have such a transition for some bandit k, which has a transition to some state ñk , hence the new state is M k ( n, ñk ), in which it experiences an impulse. Hence, it concerns a transition rate q a k (n k , ñk ) if and only if

I k (ñ k , S φ k ( M k ( n, ñk ))) = 1
. Now, regarding the corresponding lump-sum cost, this cost depends on the state m k where bandit k ends up after the impulse. That is, we need to multiply probability p

S φ k ( M k ( n,ñ k )) k (ñ k , m k ) with the corresponding lump-sum cost L ∞ k (ñ k , m k , S φ k ( M k ( n, ñk )
). The objective is to find a policy φ ∈ U that minimizes the long-run average cost:

C φ := lim sup T →∞ K k=1 1 T E T 0 C k (N φ k (t), S φ k ( N φ (t))) + C ∞,φ k ( N φ (t), S φ k ( N φ (t)))dt . (2)
The first term is a contribution from holding cost per unit of time and the second term corresponds to the lump-sum cost due to impulses.

Remark 2.1. There is no sample-path constraint on the impulse control, that is, on the number of impulses allowed at each moment in time, as this will be by default satisfied for any policy (see ( 1)). Instead, in order to control the number of impulses in the system, one can set the lump-sum cost for infinite transitions, L ∞ k (n, m, a), appropriately. Another method would be to include a constraint on the time-average number of impulses. The later is beyond the scope of the paper, as this would imply deriving an index-based heuristic that satisfies a time-average constraint, and, to the best of our knowledge, no index heuristics have been proposed for such settings.

Lagrangian Relaxation and Whittle's index policy

Finding a policy that minimizes the long run average cost (2) under constraint (1) is intractable in general. In fact, it is shown in [START_REF] Papadimitriou | The complexity of optimal queuing network control[END_REF] that the restless bandit problems are PSPACE complete, which is much stronger evidence of intractability than NP-hardness. Following [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF], a very fruitful approach has been to study the relaxed problem in which the constraint (1) is replaced by its time-averaged version, that is, lim sup

T →∞ 1 T E T 0 K k=1 f k (N φ k (t), S φ k ( N φ (t)))dt ≤ M. (3)
Let U REL be the set of stationary policies φ that satisfy (3) and for which the Markov chain is ergodic. Note that the set of policies that make the relaxed problem ergodic includes U, i.e., the set of ergodic policies for the original problem. The objective of the relaxed problem is hence to determine a policy that solves (2) under constraint (3). An optimal policy for the relaxed problem then serves as a heuristic for the original optimization problem.

Using the Lagrangian approach, we write the relaxed problem as the following unconstrained problem: find a policy φ that minimizes C φ (W ) := lim sup

T →∞ 1 T E T 0 K k=1 C k (N φ k (t), S φ k ( N φ (t))) + C ∞,φ k ( N φ (t), S φ k ( N φ (t))) -W K k=1 f k (N φ k (t), S φ k ( N φ (t))) -M ) dt , ( 4
)
where W is the Lagrange multiplier. The latter can be decomposed into K subproblems, one for each bandit k, that is, minimize

C φ k := lim sup T →∞ 1 T E T 0 C k (N φ k (t), S φ k (N φ k (t))) + C ∞,φ k (N φ k (t), S φ k (N φ k (t))) -W f k (N φ k (t), S φ k (N φ k (t))) dt . (5)
With slight abuse of notation, in the above equation, we replaced N φ (t) by N φ k (t). We can do so since the stochastic evolution of bandits are independent across each other. Hence, the optimal action for a given bandit (when there is no longer a common constraint on the number of activated bandits) does not depend on the state of other bandits. In other words, in the decomposition, for a given bandit k, the optimal action only depends on its own state.

The solution to ( 4) is obtained by combining the solution to the K separate optimization problems (5). Under a stationarity assumption, we can invoke ergodicity to show that ( 5) is equivalent to minimizing

E(C k (N φ k , S φ k (N φ k ))) + E(C ∞,φ k (N φ k , S φ k (N φ k ))) -W E(f k (N φ k , S φ k (N φ k ))), (6)
where N φ k is distributed as the stationary distribution of the state of bandit k under policy φ.

If f k (N φ k , S φ k (N φ k )) = 1 -S φ k (N φ k )
, the Lagrange multiplier W can be interpreted as subsidy for passivity. For ease of notation, we denote the total expected cost of bandit k under policy φ by

E(T k (N φ k , S φ k (N φ k ))) := E(C k (N φ k , S φ k (N φ k ))) + E(C ∞,φ k (N φ k , S φ k (N φ k ))).

Indexability and Whittle's Index

Indexability is a property that allows us to develop a heuristic for the original problem. This property imposes that as the Lagrange multiplier, W , increases, the collection of states in which the optimal action is passive increases.

Definition 3.1. A bandit is indexable if the set of states in which passive is an optimal action in (6) (denoted by

D k (W )) increases in W , that is, W < W ⇒ D k (W ) ⊆ D k (W ).
Note that in case the set of states D k (W ) is decreasing in W , one can simply switch the role of active and passive for bandit k, and the bandit would be indexable. If the RMABP is indexable, Whittle's index in state N k is defined as follows: Definition 3.2. When a bandit is indexable, Whittle's index in state n k is defined as the smallest value for the subsidy such that an optimal policy for ( 6) is indifferent of the action in state n k . Whittle's index is denoted by W k (n k ).

Given that the indexability property holds, [START_REF] Whittle | Restless bandits: Activity allocation in a changing world[END_REF] established that the solution to the relaxed control problem (4) will be to activate all bandits that are in a state n k such that their Whittle's index exceeds the Lagrange multiplier, i.e., W k (n k ) > W . This optimal solution to the relaxed problem might be infeasible for the original model where the constraint (1) has to be satisfied at each decision epoch. Hence, we have the following index-based heuristic for the original problem with the general resource constraint (1). Definition 3.3 (Index-based policy). Assume at time t we are in state N (t) = n. The index-based heuristic will activate bandits in a greedy manner: activate the bandit with the highest non-negative Whittle's index, W k (n k ), until either the constraint is met or there are no more bandits with non-negative index to activate.

In our definition of the index-based policy, bandits with a negative Whittle's index are not activated. This is a straight consequence of the relaxed optimization problem: when the Whittle's index is negative in state m, i.e.,

W k (m) < 0, bandit k in state m is made active only if W < W k (m). Since W k (m) < 0, the bandit is activated only if a cost W is paid for being passive. In case f k (N φ k , S φ k ( N φ k )) = S φ k (N φ k )
, this definition reduces to the Whittle's index policy as studied in classical RMABPs. In that setting, the sample-path constraint (1) can also have a strict equality sign, in which case one can simply adapt the index-based policy by activating the M bandits with the highest indices, even though these indices can be negative. We further note that in case the function f k (•, •) represents the expected capacity occupation, the index-based rule as defined above has been numerically shown to perform well in [START_REF] Graczová | Generalized restless bandits and the knapsack problem for perishable inventories[END_REF].

Remark 3.4. In the case of a single bandit, i.e., K = 1, with no sample-path constraint on activation, the index-based policy provides an optimal solution to the original problem. One can choose a uniformly-bounded constraint function f (n, a) in such a way that the bandit is indexable. When W = 0, the objectives of the original and the relaxed problem are the same. Hence, the index-based policy (activate the bandit whenever it is in a state n with W (n) > 0) results in an optimal solution for the original problem for the single bandit. In Section 6 this is discussed for a content delivery network.

Expression of Whittle's index

In this section we present an algorithm, which checks for indexability, and, if indexable, calculates Whittle's index. This algorithm is computationally expensive. In section 4, we show how this algorithm simplifies in the case some structural results can be shown for the relaxed problem. Since the action set (binary actions) is finite for each state, we can restrict our focus to deterministic stationary policies, see [Puterman, 2014, Theorem 11.4.8].

Let X U ⊂ N d be the set consisting of all states bandit k can be in. For a given subset X ⊂ X U , let policy X refer to the policy that keeps the bandit passive in all states x ∈ X. We denote the empty set by ε.

Algorithm 1 Indexability check and Whittle's index computations Require: X U , f k (.), T k (.) Initialization: Define X 0 as the union of sets that equals arg inf

X⊂X U E(f k (N X k , S X k (N X k ))
). Define X 0 as the union of sets that equals arg sup

X⊂X U E(f k (N X k , S X k (N X k ))). Step j: Compute W j = inf X⊂X U E(T k (N X k , S X k (N X k ))) -E(T Xj-1 k (N Xj-1 k , S Xj-1 k (N Xj-1 k ))) E(f k (N X k , S X k (N X k ))) -E(f k (N Xj-1 k , S Xj-1 k (N Xj-1 k ))) , j ≥ 1.
where the infimum is taken over all those X ⊂ X U such that the denominator is non-zero.

Step j 1 : If the infimum is not attained in any finite set, go to step j . Otherwise, let X j denote the collection of sets that reaches the infimum. Define X j as the union of all sets arg max

Y ∈Xj E(f k (N Y k , S Y k (N Y k ))).
Step j 2 : If X j-1 ⊂ X j , set W k (x) := W j for all states x ∈ X j \X j-1 . Else, the system is not indexable and stop.

Step j 3 : If X j = X U , then the system is indexable and stop. Otherwise go to step j + 1.

Step j : Compute

W j = sup X⊂X U E(T k (N X k , S X k (N X k ))) -E(T X j -1 k (N X j -1 k , S X j -1 k (N X j -1 k ))) E(f k (N X k , S X k (N X k ))) -E(f k (N X j -1 k , S X j -1 k (N X j -1 k ))) , j ≥ 1.
where the supremum is taken over all those X ⊂ X U such that the denominator is non-zero.

Step j 1 : If the supremum is not attained in any finite set, Whittle's index is not found. Otherwise, let X j denote the collection of sets that reaches the infimum. Define X j as the union of all sets arg min

Y ∈X j E(f k (N Y k , S Y k (N Y k ))).
Step j 2 : If X j -1 ⊂ X j , set W k (x) := W j for all states x ∈ X j \X j -1 , Else, the system is not indexable and stop.

Step j 3 : If X j = X U then the system is indexable, and stop. Otherwise go to step j + 1.

Algorithm 1 can be explained as follows. In the relaxed subproblem, the objective is to find a policy for bandit k that minimizes (6). Note that ( 6) is a linear function in W . Hence, when comparing two policies φ 1 and φ 2 , defined by their sets of passive states X (φ1) and X (φ2) , respectively, for which the slopes of (6) are not equal, there is a value for the subsidy, W 1,2 , for which the costs (6) under both policies are equal. This is given by

W 1,2 := E(T k (N X (φ 1 ) k , S X (φ 1 ) k (N X (φ 1 ) k ))) -E(T k (N X (φ 2 ) k , S (φ2) k (N (φ2) k ))) E(f k (N X (φ 1 ) k , S X (φ 1 ) k (N X (φ 1 ) k ))) -E(f k (N (φ2) k , S (φ2) k (N (φ2) k )))
.

When calculating the indices, one needs to find the policies (and their corresponding passive sets) that minimize (6) for each W . As a first step, one can start by searching for the optimal policy when W = -∞ (the set of passive states corresponding to this optimal policy is denoted by X 0 ) and when W = ∞ (corresponding policy denoted by X 0 ). Recursively, one can find the switching point W where the optimal passive set changes. That is, in Step j, given it is known that the policy described by the passive set X j-1 is optimal when W j-2 < W ≤ W j-1 , find the crossing point where another policy becomes optimal. Such a crossing point is denoted by W j and the corresponding optimal passive set by X j . Now, if X j-1 ⊂ X j , for all j, this implies indexability and the index for any state in X j \X j-1 is given by W j . A mathematical proof of Algorithm 1 would follow according to similar steps as in [START_REF] Glazebrook | Index policies for the admission control and routing of impatient customers to heterogeneous service stations[END_REF], where an algorithm is developed for finding Whittle's index in the context of admission control and routing of impatient customers.

Remark 3.5. In order to numerically run this algorithm one would need X U to have finite cardinality, in order to find the infimum/supremum in step j and j . Hence, when |X U | = ∞, numerical computation through the algorithm would only provide an approximation for Whittle's index, since one would need to limit the search in the inf/sup over a finite number of subsets X.

If instead |X U | < ∞, the algorithm provides Whittle's index, if indexable. The computational complexity of the

algorithm is O |X U | 4 2 |X U | .
This can be seen by noting that (i) the number of possible subsets Remark 3.6. Since we consider the average cost criterion, the calculations in step j and j in Algorithm 1 are feasible provided the steady-state distributions are known. If instead we had considered the total discounted cost criterion, the latter would depend on the initial state and transient behavior, and hence the calculation as done in Algorithm 1 is not possible.

X ⊂ X U is 2 |X U | , (
Remark 3.7. In Algorithm 1, an indexability check is included. Note that in case indexability had been proved independently, the algorithm would simplify, as one can replace in step j the "inf X⊂X U " by "inf X:Xj-1⊂X⊂X U ", and similarly in step j . In addition, in Algorithm 1 structural properties of the optimal solution of the relaxed optimization problem are not taken into account. In Section 4 we will describe how a structural property (threshold optimality) can help in the calculation of the index.

Threshold policies

For certain one-dimensional problems, it can be established that the structure of the optimal solution of problem ( 6) is of threshold type. That is, there is a threshold function n k (W ) such that when bandit k is in a state m k ≤ n k (W ), then action a is optimal, and otherwise action a is optimal, a, a ∈ {0, 1} and a = a . We let policy φ = n denote a threshold policy with threshold n, and we refer to it as 0-1 type if a = 0 and a = 1, and 1-0 type if a = 1 and a = 0. In general it can be hard to verify whether an optimal solution is of threshold type. In this section we provide sufficient conditions for threshold optimality and show how Algorithm 1 simplifies.

The following result characterizes sufficient conditions on the transition rates q a k (•, •) and the jump probabilities p a k (•, •) such that a threshold policy solves problem (6). For example, condition (i) can be interpreted as follows. If there are no upward jumps under the active action or under an impulse control, and there can be an upward jump of at most one under the passive action, then 0-1 type of threshold policies are optimal. The proof can be found in the Appendix.

Proposition 1. Assume N k (t) ∈ N If one of the following conditions holds, (i) q 1 k (N, N + i) = 0, ∀ i ≥ 1, q 0 k (N, N + i) = 0, ∀ i ≥ 2, and p a k (N, N + i) = 0, ∀ i ≥ 1, a = 0, 1, (ii) q 0 k (N, N -i) = 0, ∀ i ≥ 1, q 1 k (N, N -i) = 0, ∀ i ≥ 2, and p a k (N, N -i) = 0, ∀ i ≥ 1, a = 0, 1,
then there exists an n k ∈ {-1, 0, 1, ...} such that a 0-1 type of threshold policy with threshold n k , optimally solves problem (6). Alternatively, if one of the following conditions holds,

(iii) q 1 k (N, N -i) = 0, ∀ i ≥ 1, q 0 k (N, N -i) = 0, ∀ i ≥ 2 and p a k (N, N -i) = 0, ∀ i ≥ 1, a = 0, 1, (iv) q 0 k (N, N + i) = 0, ∀ i ≥ 1, q 1 k (N, N + i) = 0, ∀ i ≥ 2, and p a k (N, N + i) = 0, ∀ i ≥ 1, a = 0, 1,
then, there exists an n k ∈ {-1, 0, 1, ...} such that a 1-0 type of threshold policy with threshold n k , optimally solves problem (6).

Optimality of a threshold policy for the relaxed optimization problem has been proved for several RMABPs, several examples can be found in [Gittins et al., 2011, Section 6.5]. All applications as presented in this paper, fit the sufficient conditions, and hence have the threshold structure. We further note that there are models where the optimality of threshold policies has been established, but whose model parameters do not fall within the conditions of Proposition 1, see for example [START_REF] Ps Ansell | Whittle's index policy for a multi-class queueing system with convex holding costs[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 | Efficient content delivery in the presence of impatient jobs[END_REF].

When an optimal solution for problem ( 6) is of threshold type, we have the following sufficient condition for indexability. For the proof we refer to the Appendix.

Proposition 2. If an optimal solution of ( 6) is of threshold type, and

E(f k (N n k , S n k (N n k ))
) is non-negative and strictly increasing in n, then problem (6) is indexable.

Remark 4.1 (Algorithm 1 with threshold-based policies.). Algorithm 1 simplifies in case it is known beforehand that (i) threshold policies are optimal for the relaxed problem, and (ii) the bandit is indexable. If it is known that 0-1 type of threshold policies are optimal and that the problem is indexable, from Remark 3.7, one can restrict the search in Step j and Step j to sets X of the form {m ≤ n} where n > n j-1 , and initialization step reduces to finding

n 0 = arg inf n∈N E(f k (N n k , S n k (N n k ))) and X 0 = {m ≤ n 0 }. Similar for X 0 .
When threshold policies are optimal, the computational complexity of Algorithm 1 reduces from

O |X U | 4 2 |X U | to O |X U | 5
(the latter is the computational complexity of Algorithm 1 as obtained in Remark 3.5). This follows since the infimum/supremum is taken over sets of the form {m ≤ n}, of which there are |X U |, as opposed to 2 |X U | subsets in the general setting.

In case the monotonic nature of the function

E(T n k (N n k , S n k (N n k ))) -E(T n-1 k (N n-1 k , S n-1 k (N n-1 k ))) E(f k (N n k , S n k (N n k ))) -E(f k (N n-1 k , S n-1 k (N n-1 k ))) (7)
can be proven, the computation of Whittle's index further simplifies:

Proposition 3. Assume an optimal solution of ( 6) is of threshold type and bandit k is indexable. If (7) is a monotone function in n, then Whittle's index W k (n) is given by ( 7). Further, it follows that Whittle's index is non-decreasing if 0-1 type of threshold policies are optimal and is nonincreasing if 1-0 type of threshold policies are optimal.

To illustrate our unifying framework, in the next two sections, we briefly present a few specific applications when the evolution of the bandit is driven by a Markov chain with finite and infinite transition rates. Full details are given in the Appendices.

Applications: finite transition rates

There exists a large set of papers that calculate the Whittle's index for RMABPs with finite transition rates and time-average performance objective, see Section 1.1 for further references. We consider one such application (machine repairman problem) to illustrate the applicability of our results. We however emphasize that all indices as derived in previous literature, can be derived directly from our unifying framework.

Machine repairman problem

We consider the classical machine repairman problem with M non-identical machines and R repairmen, where R ≤ M. Any number of repairmen may be active at any decision epoch, but no more than one may work on any individual machine at a time. [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF] modeled the machine repairman problem as an RMABP in discrete time and obtained Whittle's index for the average-cost criterion by first considering the discounted-cost criterion and then letting the discounting factor tend to one. In this section, we describe the machine repairman model as an RMABP in continuous time, and allow state dependent transition rates with a general cost function. We use Proposition 3 to derive Whittle's index for the average-cost criterion, and as special cases retrieve the indices of [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF]. This generalizes the model in [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF], where the analysis was restricted to constant cost structure (for model 2) and state-independent transition rates.

The state of the system at epoch t is an M-dimensional vector X(t) = {X 1 (t), X 2 (t), ..., X M (t)}, where X k (t) is the state of machine k ≤ M, and X k (t) ∈ {0, 1, . . .}. The machine state measures the degree of deterioration and is assumed to evolve independently of the states of the other machines. When one of the R repairmen is working on machine k, it makes a transition from state n k to the pristine state 0 at repair rate r k (n k ). If instead machine k is unattended, its state deteriorates from state n k to state n k + 1 after an exponential amount of time with deterioration rate λ k (n k ). In addition, if machine k in state n k is unattended, it experiences a catastrophic breakdown at rate ψ k (n k ), after which the machine is replaced by a new machine at a considerable lump-sum cost L b k (n k ). Let L r k (n k ) be the lump-sum cost of using the repairman in state n k , where typically

L b k (n k ) >> L r k (n k ). Let C d k (n k
) denote the per unit cost of deterioration for an unattended machine k in state n k . The objective is to deploy the repairmen in order to minimize the total long-run average cost.

This problem can be cast in the RMABP framework as follows. Each machine is a bandit. At each decision epoch, at most R bandits/machines can be activated ( repairman is sent to it). A bandit is active (a = 1) if a repairman is deployed to this machine, and passive (a = 0) otherwise. The machine repairman problem is hence characterized by the following transition rates:

q 1 k (n k , 0) = r k (n k ), q 0 k (n k , 0) = ψ k (n k ) and q 0 k (n k , n k + 1) = λ k (n k ), ( 8
)
and the cost functions under action a = 0 and a = 1 are given by,

C k (n k , 0) = ψ k (n k )L b k (n k ) + C d k (n k ), C k (n k , 1) = r k (n k )L r k (n k ). We set f k (N φ k , S φ k ( N )) = S φ k ( N ), so that the constraint M k=1 f k (N φ k , S φ k ( N )) = M k=1 S φ k ( N ) ≤ R
, ensures that at most R repairmen are active at a time.

The transition rates (8) satisfy the sufficient conditions as presented in Proposition 1, hence an optimal policy of the relaxed optimization problem ( 5) is of threshold type with 0-1 structure. Further,

E(f k (N n k k , S n k k (N n k k ))) = n k m=0 π n k k (m), with π n k k (m)
as the stationary probability of being in state m under threshold n k . In addition, it can be verified that

n k m=0 π n k k (m) is strictly increasing in n k if r k (n k ) ≤ r k (n k + 1) for all n k (see Appendix B.
2). Thus, the indexability follows from Proposition 2. Together with Proposition 3, we obtain the following closed-form expression for Whittle's index. We refer to Appendix B.3 for the proof.

Proposition 4. Assume r k (n) ≤ r k (n + 1), ∀ n and r k (1) > 0. It holds that bandit k is indexable. Consider

(C Sum (n) + L r k (n + 1)P n ) P Sum (n -1) + Pn-1 r k (n) -(C Sum (n -1) + L r k (n)P n-1 ) P Sum (n) + Pn r k (n+1) Pn-1 r k (n) n i=0 Pi λ k (i) -Pn r k (n+1) n-1 i=0 Pi λ k (i) , ( 9
)
where P 0 := 1,

P i := i j=1 p k (j), p k (j) := λ k (j) λ k (j)+ψ k (j) , P Sum (n) := n i=0 Pi λ k (i) and C Sum (n) := n i=1 (P i-1 -P i )L b k (i) + PiC d k (i) λ k (i) .
If (9) is monotone in n, then Whittle's index is given by (9).

For the parameter settings such that ( 9) is monotone, the Whittle's index is given by ( 9), for the others, the index can be computed by Algorithm 1.

For specific choices of the parameters, Whittle's indices were previously obtained in [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF]. We now show how they follow directly from ( 9). In the first model considered in [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF], there are no catastrophic breakdowns, only deterioration costs are considered, repair rates and repair cost are state-independent. That is, r k

(n) = r k , ψ k (n) = 0, L b k (n) = 0, L r k (n) = L r k , ∀ n.
In that case, (9) reduces to

W k (n) = r k n-1 i=0 C d k (n) -C d k (i) λ k (i) + C d k (n) -r k L r k r k , ( 10
)
which is indeed monotone if C d k (n) is an increasing sequence in n (see Appendix B.4 for details). Recall that we consider a continuous-time model, while [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF] consider discrete time set-up. In particular, in the discrete-time model, a machine is repaired in one time slot. Setting r k = 1 (so that in our model the expected time to repair a machine equals 1) and interpreting 1/λ k (n) as the expected time a machine (not under repair) spends in state n, Equation (10) matches the index as derived in [Glazebrook et al., 2005, Corollary 1].

In the second model considered in [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF], there is no deterioration cost, but there is a lump-sum cost for catastrophic breakdowns. All lump-sum costs and repair rates are state independent. That is, r k

(n) = r k , C d k (n) = 0, L r k (n) = R k , L b k (n) = B k , ∀ n. Now, (9) reduces to W k (n) = B k 1-p k (n) r k -p k (n) λ k (n) + n i=0 Pi λ k (i) -p k (n) n-1 i=0 Pi λ k (i) 1 r k n i=0 Pi λ k (i) -p k (n) n-1 i=0 Pi λ k (i) -R k , (11)
which is indeed monotone if ψ k (n) is an increasing sequence in n (see Appendix B.5 for details).

In the discrete-time model of [START_REF] Glazebrook | Index policies for the maintenance of a collection of machines by a set of repairmen[END_REF], it is assumed that the time it takes to change state is equal to 1. Setting 1 r k = 1 and

1 λ k (n)+ψ k (n) = 1 ∀ n, (
so that in the continuous-time model the expected time to change state equals 1) we retrieve

W k (n) = B k T (n) -p(n) T (n -1) -p(n) T (n) -p(n) T (n -1) -R k , (12)
where T (n) := n i=0 Pi λ k (i) can be interpreted as the expected duration to either reach state n or that a catastrophic breakdown occurs, when starting in state 0. As such, we retrieve the Whittle's index as obtained in [Glazebrook et al., 2005, Corollary 2] for the discrete-time case.

Applications: infinite transition rates

To the best of our knowledge, the calculation for Whittle's index has not been earlier explored for impulse control, that is, infinite transition rates, under the average cost criteria. In this section, we illustrate the applicability of our expression for Whittle's index in problems with impulsive control by considering examples in the areas of congestion control in Transmission Control Protocol (TCP) and scheduling in content delivery network.

Congestion control of TCP flows

We consider the following congestion control model for a simple version of TCP, which is the algorithm that regulates the congestion on the Internet. There are K flows trying to deliver packets to their destination via a bottleneck router with buffer size B. We assume that flow k has implemented an additive-increase/multiplicative-decrease (AIMD) mechanism as in TCP. The congestion window of each flow is adapted according to received acknowledgements. For each positive acknowledgement (ACK), the congestion window is increased by the reciprocal of its current value, which approximately corresponds to an increase by one packet during a round-trip-time (RTT) without lost packets. We model this with Poisson arrivals of packets for flow k with arrival rate λ k , which correspond to the time period of one RTT. For each negative acknowledgement (NACK), the congestion window is immediately decreased using the formula, congestion window = max{ γ k × congestion window , 1}, where 0 ≤ γ k < 1 is the multiplicative decrease factor and the function . denotes the floor function. Whenever the bottleneck router is full, a controller decides which flow will receive a NACK in order to maximize the average reward. We take reward as the generalized α-fairness function R

k (n) = (1+n) (1-α) -1 1-α if α = 1, log(n + 1) if α = 1.
The above reward is earned if the controller admits the packet to the router (a = 1 or ACK), and 0 otherwise (a = 0 or NACK). The parameterized family of the above generalized α-fair reward aims at maximizing the router's total aggregated utility. Note that the parameter α permits to recover a wide variety of utilities such as max-min, maximum throughput and proportional fairness (see [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF], [START_REF] Altman | Generalized α-fair resource allocation in wireless networks[END_REF]). We model the above scenario as an RMABP where each flow represents a bandit and the state of the bandit k, n k , represents the number of outstanding packets. The parameters of bandit k are:

I k (n k , 0) = 1 and p 0 k (n k , max{ γ k .n k , 1}) = 1, I k (n k , 1) = 0 and q 1 k (n k , n k + 1) = λ k ,

Content delivery network

In this section, we adopt the basic model of a content delivery network, as explored in [START_REF] Larrañaga | Efficient content delivery in the presence of impatient jobs[END_REF]. Our primary focus is to illustrate the optimality of Whittle's index policy for a single-armed bandit (Remark 3.4) with impulse control. In a content delivery network, the bulk of traffic (e.g. software updates, video content etc.) is delay tolerant. Hence, requests can be delayed and grouped, so as to be transmitted in a multi-cast mode through the network. The challenge is to balance the gains of grouping requests in order to save transmission capacity against the risk of not meeting the deadline of one or more jobs. We assume that all the jobs instantaneously depart upon receiving the service.

Let the state n denote the number of waiting requests. Let jobs arrive according to a Poisson process with a state dependent rate λ(n). For each request, after a state dependent exponential expiration time with rate θ(n)/n, the request abandons the system (deadline is passed). Upon activation of the server, all waiting requests are cleared instantaneously. The objective is to minimize the long-run average cost incurred by the waiting jobs, by abandonments, as well as the set-up cost paid upon activation of the server.

Let C h (n) be the state-dependent cost per unit of time that n requests are held in the queue. Let L a (n) be the state-dependent penalty ( lump-sum cost) for a job abandoning the queue, which may depend on the action a chosen. Let L ∞ s (n) be the set-up cost ( lump-sum cost) of clearing the batch of size n. We can model this as a single armed restless bandit, where action a = 1 (a = 0) stands for serving (not serving) all the waiting requests. We drop the subscript k since there is only one bandit. We have the following transitions: I(n, 0) = 0 and q 0 (n, n + 1) = λ(n), q 0 (n, n -1) = θ(n), I(n, 1) = 1 and p 1 (n, 0) = 1.

We further set f (N φ , S φ ( N )) = -1 {N φ ∈M φ } , where M φ = {m ∈ {0, 1, 2, ...} : S φ (m) = 0, S φ (m + 1) = 1}, in order to find an optimal activation policy (see Remark 3.4). Note that we need the function f (.) to depend on policy φ, different to what was assumed in Section 2. We did so in order to find a constraint function f for which it holds that E(f (N n , S n (N n ))) is strictly increasing. Taking for example f (n, a) = 1 -a, would result in E(f (N n , S n (N n ))) = 1, since when looking to the time-average, one is always passive. It can be checked that all results of this paper (and their proofs) hold true for this given choice of function f (N φ , S φ ( N )) = -1 {N φ ∈M φ } .

An optimal policy of the relaxed optimization problem ( 6) is of threshold type with 0-1 structure. The latter follows directly from Proposition 1. In addition, it can be verified that, if λ(n) is non-decreasing, then E(f (N n , S n ( N ))) = -π n (n) is strictly increasing in n, see Appendix D. Thus, the indexability follows from Proposition 2. From Proposition 3, we obtain an analytical expression for Whittle's index (see Appendix D for details). Lemma 6.2. Assume λ(n) is non-decreasing. Consider

n-1 i=1 C(i)(π n (i) -π n-1 (i)) + C(n)π n (n) + L ∞ s (n + 1)λ(n)π n (n) -L ∞ s (n)λ(n -1)π n-1 (n -1) π n-1 (n -1) -π n (n) , (14)
where 14) is non-decreasing in n, then Whittle's index is given by ( 14).

C(n) = nC h (n) + θ(n)L a (n). If (
We conclude that an optimal policy in the content delivery problem is to activate the bandit/queue whenever the numerator of ( 14) is non-negative. This follows directly from Remark 3.4.

If the rates and costs are state-independent, i.e., λ(n

) = λ, θ(n) = iθ, C h (n) = C h , L a (n) = L a and L ∞ s (n) = L ∞
s , ∀ n, the optimal policy simplifies to activating whenever C E(N n ) -E(N n-1 ) -λL ∞ s (π n-1 (n -1)-π n (n)) ≥ 0, with C = C h + θL a . This coincides with the results obtained in [Larrañaga et al., 2015, Proposition 3].

Conclusions

In the main contribution of this work, we derive an analytical expression for Whittle's index under the average-cost criterion when each bandit evolves as a continuous-time Markov chain with possible impulse control. The Whittle's index is given in a compact expression, which makes the implementation of the index heuristic easier. We show that with this general formula, we can retrieve Whittle's index for many application, that were previously derived in the literature on a case-by-case basis.

A.2 Proof of Proposition 2

Proof. We will focus on 0-1 type of threshold policies throughout the proof. The case of threshold policies of type 1-0 can be proven similarly. Since an optimal solution of problem ( 6) is of threshold type for a given subsidy W , the optimal average cost will be g(W ) := min n g (n) (W ) where

g (n) (W ) = E(T (N n , S n (N n ))) -W E(f (N n , S n (N n ))).
We denote the minimizer of g(W ) by n(W ). Note that the function g(W ) is a envelope of affine non-increasing functions of W due to the non-negative nature of E(f (•)). It thus follows that g(W ) is a concave non-increasing function.

It follows that the right derivative of g(W ) in W is given by -E(f (N n(W ) , S n(W ) (N n(W ) ))). Since g(W ) is concave in W , the right derivative is non-increasing in W . Together with the fact E(f (N n , S n (N n ))) is strictly increasing in n, it hence follows that n(W ) is non-decreasing in W . Since an optimal policy is of 0-1 threshold type, the set of states where it is optimal to be passive can be written as D(W ) = {m : m ≤ n(W )}. Since n(W ) is non-decreasing, by definition this implies that bandit k is indexable.

A.3 Proof of Proposition 3

We will focus on 0-1 type of threshold policies throughout the proof. Let W (n) be the value for subsidy such that the average cost under threshold policy n is equal to that under threshold policy n -1. By using (6), we have

E(T (N n , S n (N n ))) -W (n)E(f (N n , S n (N n ))) = E(T (N n-1 , S n-1 (N n-1 ))) -W (n)E(f (N n-1 , S n-1 (N n-1 ))). Hence, W (n) is given by, E(T n (N n , S n (N n ))) -E(T n-1 (N n-1 , S n-1 (N n-1 ))) E(f (N n , S n (N n ))) -E(f (N n-1 , S n-1 (N n-1 )))
, which is the same as (7). Since W (n) is monotone, it can be verified by exploiting threshold optimality that g(

W (n)) = g (n) ( W (n)) = g (n-1) ( W (n)). Similarly, g( W (n -1)) = g (n-1) ( W (n -1)) = g (n-2) ( W (n -1))
. Further, monotonicity of W (n) implies the following two possibilities:

1. Non-decreasing nature, i.e., W (n -1) ≤ W (n)

2. Non-increasing nature, i.e., W (n -1) ≥ W (n)

But W (n -1) ≥ W (n) results in a contradiction from indexability and 0-1 type of threshold optimality. Thus, W (n) has to be non-decreasing, i.e., W (n -1) ≤ W (n). It follows from indexability and 0-1 type of threshold optimality that for all W ≤ W (n), the set of states where it is optimal to be passive, D(W ), satisfies D(W ) ⊆ {m : m ≤ n -1}. Again from indexability in a similar way, D(W ) ⊇ {m : m ≤ n -1} for all W ≥ W (n -1). Thus, for W (n -1) ≤ W ≤ W (n), {m : m ≤ n -1} ⊆ D(W ) ⊆ {m : m ≤ n -1} which implies that threshold policy n -1 is optimal for all W (n -1) ≤ W ≤ W (n) and hence g(W ) = g (n-1) (W ) for W (n -1) ≤ W ≤ W (n). Hence, W (n) is the smallest value of the subsidy such that activating the bandit in state n becomes optimal, that is, Whittle's index is given by W (n) = W (n).

B Machine repairman problem

In this section, we provide the details to obtain the stationary distribution, prove indexability and derive Whittle's index for two specific models of the machine repairman problem of Section 5.

B.1 Stationary distribution

In this section, we determine the stationary distribution under a 0-1 type of threshold policy n. Thus, action a = 0 is taken in states 0, 1, 2, • • • , n and action a = 1 in states n + 1, n + 2, ... The transition diagram for the evolution of Markov chain is shown in Figure 2. The balance equations for the stationary distribution under the threshold policy n are given by π n (m) = 1, one obtains

λ(0)π n (0) = ψ(1)π n (1) + ψ(2)π n (2) + • • • + ψ(n)π n (n) + r(n + 1)π n (n + 1), ( 15
) λ(m)π n (m) = (λ(m + 1) + ψ(m + 1))π n (m + 1) for m = 0, 1, 2, ..., n -1, λ(n)π n (n) = r(n + 1)π n (n + 1). 0 1 2 n n + 1 λ(0) λ(1) λ(2) λ(n -1) λ(n) b(1) r(n + 1) b(2) b(n)
π n k k (m k ) = P m k λ k (m k ) n k i=0 Pi λ k (i) + Pn k r k (n k +1) ∀ m k = 0, 1, 2, ...n k , π n k k (n k + 1) = P n k r k (n k + 1) n k i=0 Pi λ k (i) + Pn k r k (n k +1) , (16)
π n k k (m k ) = 0 ∀ m k = n k + 2, • • • where P i = i j=1 p k (j) and p k (j) = λ k (j)
λ k (j)+ψ k (j) ; P 0 = 1.

B.2 Indexability

Lemma B.1. Machine k is indexable if the repair rates are non-decreasing in their state, i.e., r k (n) ≤ r k (n + 1) ∀ n, and r k (1) > 0. In particular, all machines are indexable for state-independent repair rates.

Proof. From Proposition 3, it follows that machine k is indexable if

E(f k (N n k , S n k (N n k ))
) is strictly increasing in n. Recall that f k (n, a) = 1 {a=0} . Under the 0-1 type of threshold structure policy, with threshold n, we have

E(f k (N n k , S n k (N n k ))) = n m=0 π n k (m). Thus, machine k is indexable if n m=0 π n k (m) is strictly increasing in n. Since π n k (m) = 0 for m > n + 1, this is equivalent to proving that π n k (n + 1
) is strictly decreasing in n. From Equation ( 16) and some algebra, we obtain that

π n k (n + 1) -π n-1 k (n) = λ k (n)(r k (n)-r k (n+1))-ψ k (n)r k (n+1) λ k (n)+ψ k (n) n-1 i=0 Pi λ k (i) -r k (n + 1) Pn λ k (n) r k (n)r k (n + 1) n i=0 Pi λ k (i) + Pn r k (n+1) n+1 i=0 Pi λ k (i) + Pn+1 r k (n+2)
.

Note that the denominator is strictly positive. Since r k (n) is non-decreasing and r k (1) > 0, the numerator is strictly negative. That is, the result follows.

B.3 Whittle's index: Proof of Proposition 4

Since a 0-1 type of threshold policy is optimal, using Proposition 3, the Whittle index is given by Equation ( 7), i.e.,

W k (n) = E(C k (N n k , S n k (N n k ))) -E(C k (N n-1 k , S n-1 k (N n-1 k ))) n m=0 π n k (m) - n-1 m=0 π n-1 k (m) , (17)
if ( 17) is non-decreasing. The expected cost under threshold policy n in the nominator is given by λ k (j)+ψ k (j) ; P 0 = 1. After some algebra, we obtain that ( 17) simplifies to the one stated in Proposition 4.

E(C k (N n k , S n k (N n k ))) =

B.4 Model 1: Deterioration cost per unit

We consider now a particular case when there are no breakdowns. Thus, ψ k (n k ) = 0 and L b k (n k ) = 0. This simplifies since p k (j) = 1 and P i = 1, and hence the expression in Proposition 4 simplyfies to

n i=1 C d k (i) λ k (i) + L r k (n + 1) n-1 i=0 1 λ k (i) + 1 r k (n) - n-1 i=1 C d k (i) λ k (i) + L r k (n) n i=0 1 λ k (i) + 1 r k (n+1) 1 r k (n) n i=0 1 λ k (i) - 1 r k (n+1) n-1 i=0 1 λ k (i)
.

(18)

If in addition r k (n) = r k for all n, we obtain (after some algebra) from Equation (18) that

W k (n) = r k n-1 i=0 C d k (n) -C d k (i) λ k (i) + C d k (n) -r k L r k r k . (19)
In addition,

W k (n) -W k (n + 1) = r k (C d k (n) -C d k (n + 1)) n i=0 1 λ k (i) + 1 r k ,
which is negative when the C d k (n) is non-decreasing.

B.5 Model 2: lump-sum cost for breakdown

Here, we assume that

C d k (n k ) = 0, r k (n) = r k (n + 1) = r k , L r k (n) = R k , L b k (n) = B k ∀ n
, and ψ k (n) is an increasing sequence. From Proposition 4, Whittle's index simplifies to (9). Hence, W k (n) -W k (n + 1) simplifies to:

W k (n) -W k (n + 1) = r k B k Pn r k + n i=0 Pi λ k (i) 1 ψ(n+1) -1 ψ(n) (1 -p k (n)) n i=0 Pi λ k (i) + p k (n)Pn λ k (n) (1 -p k (n + 1)) n+1 i=0 Pi λ k (i) + p k (n+1)Pn+1 λ k (n+1)
, which is negative under the increasing breakdown rates assumption.

C Congestion control in TCP

In Section 6.1 we described a TCP model, where multiple users (flows) are trying to transmit packets through a bottleneck router as shown in Figure 3.

C.1 Stationary distribution

Under a 1-0 type threshold policy n, action a = 1 is taken in states 0, 1, 2, • • • , n and action a = 0 in states n+1, n+2, ... When action a = 0 is taken at state n + 1, the state instantaneously changes to S := max{ γ.(n + 1) , 1}. Figure 4 shows the rates and its stationary distribution is given by π n (m) = 0; m = 0, 1, 2, ..., S -1, π n (m) = 1 n -S + 1 ; m = S, S + 1, ..., n. C.2 Expression of Whittle's index: Proof of Lemma 6.1

Since 1-0 type of threshold policies are optimal, using Proposition 3, the Whittle index is given by

W k (n) = E(T n k (N n k , S n k (N n k ))) -E(T n-1 k (N n-1 k , S n-1 k (N n-1 k ))) E(f k (N n k , S n k (N n k ))) -E(f k (N n-1 k , S n-1 k (N n-1 k ))) , (21)
which together with the normalization condition n i=0

π n (i) = 1 results in the following stationary distribution:

π n (m) = π n (n)λ(n) λ(m) 1 + n-m i=1
p(m + 1, m + i) ∀ m = 0, 1, 2, ...n -1,

π n (n) = 1 + n-1 k=0 λ(n) λ(k) 1 + n-k i=1 p(k + 1, k + i) -1 , (25)
π n (m) = 0 ∀ m = n + 1, • • • , (26)
where p(k + 1, k + i) = θ(k + 1)θ(k + 2)...θ(k + i) λ(k + 1)λ(k + 2)...λ(k + i) ∀ i ≥ 1.

The summation term in denominator of ( 25) is strictly increasing in n if λ(n) is non-decreasing. Thus, π n (n) will be strictly decreasing in n under non-decreasing assumption on λ(n).

D.2 Whittle's index: Proof of Lemma 6.2

The expected cost under threshold policy n is given by

E(T n (N n , S n (N n ))) = n i=1 (iC h (i) + θ(i)L a (i))π n (i) + λ(n)L ∞ s (n + 1)π n (n).
Similarly, for the threshold policy n -1

E(T n-1 (N n-1 , S n-1 (N n-1 ))) = n-1 i=1 (iC h (i) + θ(i)L a (i))π n-1 (i) + λ(n -1)L ∞ s (n)π n-1 (n -1).
From Proposition 3, we get the expression as stated in Lemma 6.2.

  ii) the computation of the steady-state distribution is O |X U | 3 3 (using Gauss elimination, see Bolch et al. [2006] ), (iii) finding the infimum or supremum requires 2 |X U | comparisons, and (iv) the number of steps in the algorithm is of the order O(|X U |).

  ), which is a function of n, the number of outstanding packets of flow k: R (α)

Figure 2 :

 2 Figure 2: Transition diagram under the threshold policy n for machine repairman problem

  for the stationary distribution as derived in Appendix B.1, we obtain that the denominator of (j) and p k (j) = λ k (j)

Figure 3 :

 3 Figure 3: A bottleneck router in TCP with multiple flows [Avrachenkov et al., 2013].

Figure 4 :

 4 Figure 4: Transition diagram under the threshold policy 'n' for TCP congestion control problem We then obtain

This can be shown by introducing so-called dummy bandits with zero cost and fixed state, see Verloop[2016].

Acknowledgement

We would like to thank Zhang Yi and Alexey Piunovskiy for helpful discussions on optimal impulse control.

This research is partially supported by the French Agence Nationale de la Recherche (ANR) through the project ANR-15-CE25-0004 (ANR JCJC RACON) and by ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02.

where action a = 1 (a = 0) stands for sending ACK (NACK). We set f k (N φ k , S φ k ( N )) = N φ k S φ k ( N ), which ensures that all flows that receive an ACK can send their outstanding packets through the bottleneck router with buffer size B, k (n). It follows from Proposition 1 that an optimal policy of the relaxed optimization problem ( 6) is of threshold type with 1-0 structure. It can be verified that

) is strictly increasing in n k (see Appendix C.1 for details), so that indexability follows from Proposition 2. Together with Proposition 3, the following result characterizes a closed form expression for Whittle's index (see Appendix C.2 for details).

with S = max{ γ k .(n + 1) , 1}. If (13) is monotone in n, then Whittle's index is given by (13).

We could not prove the monotonic nature of (13). However, we observe numerically that this indeed is the case for a wide set of parameter settings. If monotonicity of Whittle's index cannot be established, the index can be computed using Algorithm 1.

The index-based policy (Definition 3.3) would be as follows: activate/ACK all flows with highest Whittle's indices until the buffer is filled. All other flows receive a NACK. Since a NACK implies a multiplicative decrease, it is obvious that if the buffer is full, under the index policy only the flow with the smallest index value (13) will receive a NACK.

The paper [START_REF] Avrachenkov | Congestion control of TCP flows in internet routers by means of index policy[END_REF] studied as well the congestion control problem as a multi-armed restless bandit framework. This work however assumes discrete time, and as such, no infinite transition rates could be considered. In addition, for their analysis, they require a bound on the number of outstanding packets per flow. [START_REF] Avrachenkov | Congestion control of TCP flows in internet routers by means of index policy[END_REF] numerically verify for indexability and obtain Whittle's indices in closed form only in the case of at most three outstanding packets per flow. Our approach considerably simplifies the analysis, allows to prove indexability and provides an analytical expression for Whittle's index.

In Figure 1 we compare the time required to calculate the Whittle index of a TCP flow on a desktop. Namely, we compare the time required by running (i) Algorithm 1 over all possible subsets (see Remark 3.5), (ii) Algorithm 1 over threshold-based subsets (see Remark 4.1), and (iii) calculating Equation ( 13). The curves clearly illustrate that running Algorithm 1 (even in the case of threshold based subsets) quickly becomes computationally demanding, even for problems of relatively small size.

A Proof of Propositions

In this section we provide the proofs of different propositions. For ease of notation, we removed the subscript k from all the proofs in this section.

A.1 Proof of Proposition 1

Proof. Since U REL is non-empty, there exists a stationary optimal policy φ * that optimally solves the subproblem (6) for a bandit. Define n * = min{m ∈ {0, 1, ...} : S φ * (m) = 1}. This implies S φ * (m) = 0 ∀ m < n * and S φ * (n * ) = 1. From the structure on the transition rates and jump probabilities in (i) Proposition 1, we have q 1 k (N,

, and p a k (N, N + i) = 0, ∀ i ≥ 1, a = 0, 1. The above transition structure ensures that all the states m > n * are transient. Hence π φ * (m) = 0 ∀ m > n * . Thus, the following holds under the optimal policy φ * :

and lump-sum cost under the optimal policy φ * is given by:

From Markov chain theory, the average number of times state y is visited in the next decision epoch under action a given the current state x can be written as:

1 a {Xn=x, Xn+1=y} = π(x)q a (x, y).

Given that the parameters satisfy (i) of Proposition 1, the lump-sum cost can equivalently be written as;

In the above expected lump-sum cost, the first term is the contribution in cost due to transition from states 0, 1, 2, • • • , n * -1 and the second term is that for the transition from state n * . Additionally, it exploits the fact that π φ * (m) = 0 ∀ m > n * . It follows from the expressions of the above expected costs that the long run average cost under the optimal policy φ * ,

is the same as the long run average cost under a 0-1 type threshold policy with threshold n * ,

Thus, a 0-1 type of threshold policy with threshold n * is optimal when (i) is satisfied. The alternate rates (ii) can be proven to result in 0-1 type threshold optimality along the similar lines by considering the set max{m ∈ {0, 1, ...} :

if Equation ( 21) is non-increasing in n.

We have

Together with (20) and Equation ( 21), results in the Whittle index as stated in Lemma 6.1.

D Content delivery network

We consider here the content delivery network as described in Section 6.2, see also

(λ(k) + θ(k))π n (k) = λ(k -1)π n (k -1) + θ(k + 1)π n (k + 1) for k = 1, 2, ..., n -1, ( 23)