Alain Jean-Marie
email: alain.jean-marie@inria.fr.

Emmanuel Hyon
email: emmanuel.hyon@u-paris10.fr.

Optimal control of admission in service in a queue with impatience and setup costs

Keywords: Scheduling, queuing system, impatience, deadline, optimal control, Markov decision processes Ordonnancement, file d'attente, impatience, échéance, contrôle optimal, processus de décision markovien

We consider a single server queue in continuous time, in which customers must be served before some limit sojourn time of exponential distribution. A customer who is not served before this limit leaves the system: it is impatient. The fact of serving customers and the fact of losing them due to impatience induce costs. The fact of holding them in the queue also induces a constant cost per customer and per unit time. The purpose is to decide when to serve the customers so as to minimize costs. We use a Markov Decision Process with infinite horizon and discounted cost. Since the standard uniformization approach is not applicable here, we introduce a family of approximated uniformizable models, for which we establish the structural properties of the stochastic dynamic programming operator, and we deduce that the optimal policy is of threshold type. The threshold is computed explicitly. We then pass to the limit to show that this threshold policy is also optimal in the original model. A particular care is given to the completeness of the proof. We also illustrate the difficulties involved in the proof with numerical examples.

Introduction

We are interested in this paper in the optimal control of a continuous-time queuing system with impatient customers (or, equivalently said, customers with deadlines). Arrivals follow a Poisson Process and services as well as deadlines follow exponential distributions. The set-up of customer services, the storage of the customers in the queue as well as their departure from the queue due to impatience induce some costs and it has to be decided when to begin the service in order to minimize these costs. At each decision epoch, the controller faces up a trade-off problem between serve/not serve decision and we are interested in this paper to the optimal admission in service policy. We also are motivated to investigate the structural properties satisfied by the optimal policy, and especially the optimality of a special form of structural policies: threshold policies.

Stochastic controlled queuing models, have been largely studied in the literature since their application fields are numerous: networking, resources allocation, inventory control, to quote just a few (see e.g. [START_REF]Markov Decision Processes in Practice[END_REF] and references therein). However, most of these works do not consider impatient customers although the phenomenon of impatience, associated with deadlines or "timeouts", has become a major trend in recent years. For non-controlled queues an overview can be found in [START_REF] Hasenbein | Introduction: queueing systems special issue on queueing systems with abandonments[END_REF]. Models of controlled queues with impatience appear in several fields of engineering: intrinsincally in real-time systems and yield management, but also in communication networks [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF], call centers [START_REF] Down | Dynamic control of a single-server system with abandonments[END_REF], inventory control [START_REF] Baron | Continuous review inventory models for perishable items ordered in batches[END_REF][START_REF] Berk | Analysis of the (Q,r) inventory model for perishables with positive lead times and lost sales[END_REF], big data with volatile data [START_REF] Vakilinia | Analysis and optimization of big-data stream processing[END_REF]. A variety of optimization problems are solved: admission control in a system [START_REF] Ward | Asymptotically optimal admission control with impatient customers[END_REF]; optimal scheduling [START_REF] Bhattacharya | Optimal scheduling with strict deadlines[END_REF] or optimal routing between queues [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF] so as to minimize deadline misses; scheduling in order to minimize long run costs [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF]; inventory control in Make-to-order systems [START_REF] Benjaafar | Optimal control of a production-inventory system with customer impatience[END_REF]; optimal control of the service rates [START_REF] Armony | Sensitivity of optimal capacity to customer impatience in an unobservable M/M/S queue (why you shouldn't shout at the DMV)[END_REF]; admission in service in slotted models [START_REF] Hyon | Scheduling services in a queuing system with impatience and setup costs[END_REF].

From a theoretical point of view, the phenomenon of impatience requires addressing a number of new issues. First, the validity of the Bellman Equation and the existence and the uniqueness of its solution should be proved. Indeed, considering impatience leads to mathematical models with unbounded transition rates. For such models, the standard uniformization method can not be applied and then the usual existence theorems (see Chapter 11 of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]) can no longer be applied. Recent works have considered this problem and new conditions for the validity of the Bellman Equation has been stated e.g. by Guo and Hernandez-Lerma in [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]. Second, when working on the properties of optimal control policies in unbounded models, we are led to approximate them by specific bounded models, to which uniformization can be applied. However the passing of structural results from a bounded model to their generalizations in an unbounded models requires some precise conditions that should be satisfied. Some recent results by Blok and Spieksma ([8] and [START_REF] Blok | Markov Decision Processes in Practice, chapter Structures of Optimal Policies in MDPs with Unbounded Jumps: The State of Our Art[END_REF]) give mathematical foundations and the conditions of validity of this approach.

There is a widespread belief (see [START_REF] Down | Dynamic control of a single-server system with abandonments[END_REF][START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF]) that the impatience phenomenon is not compatible with the technique of propagation of structural properties through the dynamic programming operator, and that it can actually destroy structural properties that are known for some queueing systems. For instance, in the call center problem of [START_REF] Down | Dynamic control of a single-server system with abandonments[END_REF] in which one should schedule two classes of customers, it was quoted that impatience causes the famous µ -c policy rule to become non optimal. Moreover, the "structure" may actually change, depending on the value of the abandonment rate. For instance, in [START_REF] Armony | Sensitivity of optimal capacity to customer impatience in an unobservable M/M/S queue (why you shouldn't shout at the DMV)[END_REF], it is proved that the value function is convex when the abandonment rate is smaller than the service rate; otherwise, the value function seems to be concave according to numerical investigations. A similar situation appears in [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF], where the submodularity of the Bellman operator can be proved only when the departure rate is larger than abandonment rate. This means that techniques of proof may or may not succeed, depending on a subtle parametric discussion. The same kind of difficulties occur in our model as it will be seen.

To further stress the difficulties caused by impatience, we can turn to the field of inventory control with perishable items, which has many similarities with queueing models. Indeed, there are connections between inventory models with perishable items and queues with impatience since some inventory models can be expressed as a queueing model with impatience and since the two types of models give rise to fairly close markovian representations. Furthermore, the families of policies considered in the inventory field are (s, S) and (r, Q) policies which are threshold basestock policies. In this field, the structure of the optimal policy in the presence of impatience remains an open question in many problems as stated in [START_REF] Berk | Analysis of the (Q,r) inventory model for perishables with positive lead times and lost sales[END_REF]. The recent overview on the topic in [START_REF] Karaesmen | Planning Production and Inventories in the Extended Enterprise: A State of the Art Handbook, chapter Managing Perishable and Aging Inventories: Review and Future Research Directions[END_REF] highlights this point and categorizes continuous-time review problems into three main classes: with no orderings cost (i.e. set up cost is null) and positive lead time; with ordering costs and no lead times (i.e. service time is zero); with ordering costs and positive lead times. The last case is the most difficult and with less published results. In summary, up to our knowledge, there are only few papers that prove the optimality of a threshold policy on the queue length (or basestock for inventory problems) in queues with impatience. So finding such a proof of optimality, especially in a system featuring both impatience and ordering costs is a noticeable contribution.

Nevertheless, there are papers in which the optimality of threshold policies has been formally shown, sometimes with partial results. For instance, the admission control in a GI/GI/1 queue under heavy traffic with impatience had been studied in [START_REF] Ward | Asymptotically optimal admission control with impatient customers[END_REF] but only asymptotic results are obtained: under the heavy traffic assumption the asymptotic (as the arrival rate tends to infinity) optimal policy is of threshold type. Also, [START_REF] Weiss | Optimal ordering policies for continuous review perishable inventory models[END_REF] proves the optimality of threshold policies, for an inventory model with ordering costs and no lead times. Similarly, [START_REF] Benjaafar | Optimal control of a production-inventory system with customer impatience[END_REF] considers a Make-to-stock queueing model with impatience when unsatisfied demands are backlogged. In this model, among all the customers in the queue, only backlogged ones are subject to impatience. The control consists of both an admission decision to the system, and an admission decision in service. There are no ordering costs. Threshold policies are shown to be optimal using the propagation of structural properties. The work [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] considers a parametric admission (a customer is admitted with a given probability that must be optimized) in a retrial queue with impatience on retrials and introduces a Smoothed Rate Truncation method in order to work with models with bounded transition rates. The model closest to ours but without impatience is the problem of optimally controlling a batch server in a queue. The discrete time model without impatience has been addressed in [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF] and has been extended for cases with impatience in [START_REF] Hyon | Scheduling services in a queuing system with impatience and setup costs[END_REF] (for a batch size of 1 and deterministic service time). The continuous-time model without impatience has been analyzed in [START_REF] Deb | Optimal control of batch service queues[END_REF][START_REF] Aalto | Optimal control of batch service queues with finite service capacity and linear holding costs[END_REF]. Both papers show that the optimal policy is a threshold policy. A continuous-time model with impatience is studied in [START_REF] Larrañaga | Efficient content delivery in the presence of impatient jobs[END_REF] which assumes that the batch size is infinite (a clearing of the queue occurs at each service decision) and which also shows that the optimal policy is a threshold policy. But extending the techniques developed in these papers is not straightforward.

Contribution and methodology.

In this work we propose a simple queueing model with service control and impatience. This model can be viewed as a generalization of [START_REF] Aalto | Optimal control of batch service queues with finite service capacity and linear holding costs[END_REF][START_REF] Deb | Optimal control of batch service queues[END_REF] with the introduction of impatience, but restricted to service batches of size one. We prove that an optimal control policy is a threshold policy based on the queue length. The proof is based the construction of a Markov Decision Process and on usual ideas about the propagation of well-chosen structural properties of policies and value functions, via a Bellman operator associated to the problem. However, the implementation of this idea faces here several challenges.

The principal issue is that transition rates of the underlying continuous-time Markov chain are unbounded. The standard reduction of the continuous-time MDP to a discrete-time one using uniformization is not possible. Among the consequences, the "natural" Bellman operator of the problem is not guaranteed to have the required properties. In particular, it is not clear it is contractive and that the Bellman equation has a unique solution, or that the Value Iteration algorithm converges.

In order to handle this situation, we follow the approach recommended by Blok and Spieksma [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] and applied successfully to several similar models in [START_REF] Larrañaga | Efficient content delivery in the presence of impatient jobs[END_REF][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]. The idea is to approximate the target model by a sequence of uniformizable models, and use the continuity results established in [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] to deduce properties of the limit model from properties of the approximations. The approximated models are typically truncated models with bounded transition rates, to which the property propagation framework can be applied. As often with truncations, boundary effects may appear that destroy the usually desired properties such as convexity. This effect is countered 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] by the introduction of a smoothed rate truncation. We also use this approach.

Since these technical difficulties are not necessarily explicit in a number of works that deal with impatience in continuous time, we take advantage of this paper to present an in-depth treatment of these technicalities related to unbounded rates. A first step is to adapt the modeling to existing theorems. As it turns out, the strongest mathematical results are presented in a MDP model that does not admit instantaneous costs, whereas our queueing control model does have some. A transformation of models is therefore required. Then it is needed to establish that the solution of the problem is characterized by some Bellman equation. We use results on this question from the work of Guo and Hernandez-Lerma in [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]. Then, it is needed to assess the existence and uniqueness of solutions to this equation, as well as to the ones resulting from approximations. We use results from [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] for this, as well as for obtaining the convergence of the solutions to smoothed and truncated models toward that of the original one. The formal reference to the property propagation framework is taken from [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]. We identify a set of properties that are propagated by the Bellman operator of approximated models and therefore enjoyed by the respective value functions.

The result of the analysis is that, when holding costs are linear, the optimal policy is either to always serve customers, or never serve them. Deciding which of them is optimal is done by comparing the service cost to a combination of the other parameters: loss cost, marginal holding cost, impatience rate and discount rate. Beyond the simplicity of this particular situation, we believe that the techniques presented here will be of a great help to indicate that the propagation of structural properties can also work in more complicated situations. For this purpose, we use a similar approach to both "serve" and "not serve" situations, although results for the second one can be obtained differently.

We also claim that the situation here is not as simple as it looks: we actually demonstrate, through several examples, that simpler, more direct or traditional methods of proof all fail for some reason. This discussion helps understand why each of the technical step is needed.

Organization. This paper is organized as follows: Section 2 deals with the model, while Section 3 study the dynamic control with unbounded rates and Section 4 presents the smoothed rate truncation used here. Section 5 establishes the structural properties propagation while the optimal policy is shown in Section 6 and a methodological discussion is done in part 7. At last, Section 8 concludes this work.

Model

This section is devoted to the presentation of the optimization model. In Section 2.1, we describe the features of the queueing model under study, the way it is controlled and the costs that are incurred. In Section 2.2, we explain how to map these requirements to a continuous-time MDP in the formalism of [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF] or [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF].

The controlled queueing model

We consider a continuous-time controlled queueing model model, in which customers are assumed to arrive according to a Poisson process with a constant intensity Λ. Once they arrived, customers are stored in an infinite buffer in which they wait for to be admitted in one single server to be processed. Let n be number of customers waiting in the queue (excluding service). The service admission decision is made by a controller. Once admitted in service by the controller, the service begins instantly and is not interrupted. The service duration is assumed to follow an exponential distribution of parameter µ.

Customers who wait in the queue are impatient. We assume that customers remain in the queue during a time that has an exponential distribution of parameter α, these durations being independent. In that case, when there are n customers waiting in queue, the rate of impatience is α(n) with α(n) = nα. This means that the next departure due to impatience occurs after a duration exponentially distributed with parameter α(n). 1 On the other hand, customers admitted in service are not impatient any more.

In the system we model, costs have several origins:

• starting a service has an instantaneous cost c B ("B" stands for "batch");

• the departure of a customer due to impatience has an instantaneous cost c L ("L" stands for "leave");

• costs accumulate continuously over time, at a rate h(n) per time unit that depends on n, the number of customers in the queue.

We wish to find a feedback control policy π that minimizes the infinite-horizon expected discounted cost of policy π, defined as follows. For each initial state x,

V π (x) = E π c B ∞ k=0 e -θA k + c L ∞ k=0 e -θL k + ∞ 0 e -θt h(X(t))dt X(0) = x , (1)
where E π stands for the expectation under the distribution of the process induced by policy π, θ > 0 is the discount parameter, {A k } k the sequence of times at which an admission in service is made, {L k } k the sequence of times at which a customer leaves due to impatience, and {X(t)} t is the process representing the number of customers in the waiting room at each instant of time.

The formal model

We now present the formal mapping of the problem we wish to solve into a continuous-time Markov Decision Process model called formal model. This formal model uses more general assumptions than the controlled queueing model requires, and hence contains the controlled queueing problems we consider. It also contains the approximated models which we shall use to handle the difficulty caused by the unbounded transition rates induced by the presence of impatience. Following [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF][START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF], a continuous-time MDP model is described by: the state space and the action spaces, the transitions rates q(y|x, a), from state x to y, given that action a is being applied,2 and the cost c(x, a) that accumulates over time. We proceed with the identification of these elements in our formal model.

It should be noticed that the model used in [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF][START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] involves only running costs, and no instantaneous costs. Therefore we will have to map the instantaneous costs of the controlled queueing model to running costs.

State and action spaces. We denote by x = (n, b) the state of the system. The integer n ∈ N denotes the number of customers which are waiting in the queue (excluding service), while the term b ∈ {0, 1} records the status of the server: 0 when the server is idle and 1 when the server is in use. The state space is denoted by X = N × {0, 1}.

The unique control decision is to admit a customer in service. This is possible only if no customer is already in service, and if some customer is waiting. Accordingly, A x , the set of controls available in state x, is A x = {0, 1} for x = (n, 0), n ∈ N \ {0}, and A x = {0} for x = (0, 0) and x = (n, 1), n ∈ N.

System dynamics. For the sake of generality we assume that the Poisson process of arrivals has a queue-length-dependent intensity. When the number of customers waiting in the queue is n, the arrival intensity is then λ(n). We equally assume that while there are n customers waiting in queue, the rate of impatience is α(n), a general function of n. Then we have: when x = (n, 0) and a = 0 (no admission in service in an idle server):

q(y|x, a) = λ(n) for y = (n + 1, 0) α(n) for y = (n -1, 0) .
When x = (n, 0) and a = 1 (admission in service in an idle server), the actual number of customers in the queue is n -1, so that:

q(y|x, a) =     
λ(n -1) for y = (n, 1) α(n -1) for y = (n -2, 1) µ for y = (n -1, 0) , provided the state y is in X , and 0 otherwise. Finally, when x = (n, 1) (busy server), then necessarily a = 0. The actual number of customers in the queue is n, and:

q(y|x, 0) =      λ(n) for y = (n + 1, 1) α(n) for y = (n -1, 1) µ for y = (n, 0) .
In the analysis, the total rate of events is useful. Let us denote with q(x, a) the total rate from state x when action a is applied. Given the definitions above, we have:

q(x, a) =      λ(n) + α(n) + µ when x = (n, 1), n ≥ 0 λ(n -1) + α(n -1) + µ when x = (n, 0), n ≥ 1 and a = 1 λ(n) + α(n)
when x = (n, 0), n ≥ 0 and a = 0 .

Cost model. According to the specification of the controlled queueing model, costs accumulate in state x = (n, b) at a rate h(n). However, as already mentioned, instantaneous costs do not fit directly in the MDP model. We therefore derive an "equivalent running cost". In order to do this, we switch temporarily to the modeling framework of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF].

Consider the situation where at time T 0 the state is x = (n, b) ∈ X , action a ∈ A x is taken, and the next event occurs at time T 1 . The instantaneous cost is:

C I (x, a) = c B 1 {(a=1)∩(n>0)∩(b=0)} . (2)
Just after the decision, the number of waiting customers is n -a. Therefore, the running cost h(n -a) applies in the interval (T 0 , T 1 ). The duration T 1 -T 0 is exponentially distributed with rate q(x, a) and the probability that the event at time T 1 is a customer leaving due to impatience is α(n -a)/q(x, a). Then, following [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]Chap. 11], 3 the current-value cost incurred between the two events can be expressed as,

C(x, a) = E x C I (x, a) + e -θ(T 1 -T 0 ) c L 1 {impatience at T 1 } + T 1 T 0 e -θ(t-T 0 ) h(n -a)dt x 0 = x ,
and then

C(x, a) = C I (x, a) + c L α(n -a) q(x, a) E x e -θ(T 1 -T 0 ) + h(n -a)E x T 1 T 0 e -θ(t-T 0 ) dt = C I (x, a) + c L α(n -a) q(x, a) q(x, a) q(x, a) + θ + h(n -a) 1 θ - 1 θ E x e -θ(T 1 -T 0 ) = C I (x, a) + c L α(n -a) q(x, a) + θ + h(n -a) q(x, a) + θ .
If our cost model had only running costs with rate c(x, a), this event-to-event cost would evaluate to c(x, a)/(q(x, a) + θ). Therefore, for the modeling framework of [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF][START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] to correspond to our cost structure, we choose as pseudo-running cost the function:

c(x, a) = (q(x, a) + θ)C I (x, a) + c L α(n -a) + h(n -a) .
Define the function k as:

k(n) = c L α(n) + h(n) . (3)
We summarize this description of the model with the following definition.

Definition 1. The formal model is the MDP model with transition rates specified in this paragraph, and cost rates given by the function

c(x, a) = (q(x, a) + θ)C I (x, a) + k(n -a)
where C I (.) is defined in [START_REF] Armony | Sensitivity of optimal capacity to customer impatience in an unobservable M/M/S queue (why you shouldn't shout at the DMV)[END_REF]. Its parameters are c B , µ, k(.) and the rate functions α(.) and λ(.). All these parameters are assumed to be nonnegative.

Optimization via stochastic dynamic programming

In this section, we state the optimization problem for the formal model of Definition 1 and characterize its solution. In Propositions 1 and 2 we state that the value function is the unique solution of some Bellman equation. We state the main result of the paper as Theorem 1. The next sections will be devoted to the proof of this theorem.

The central observation is that our formal model defines transition rates that are not a priori unbounded. It is then not possible to use the "classical" framework as described in, say, Puterman [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF], which involves uniformization to reduce the problem to a discrete-time MDP and then to assert the validity of the Bellman equation and the uniqueness of its fixed point. We apply recent advances in the theory of non-uniformizable MDPs (see [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF][START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) to obtain these results.

Policies and optimization criterion

In the context of unbounded-rate MDPs, one concentrates on the set of Stationary Markov Deterministic Policies. Those policies are characterized by a single, deterministic decision rule which maps the current state to an action and which is applied continuously over time. We denote with F the set of such policies. 4For a given policy π, let V π (x) be the value function, representing the average total discounted cost of policy π when the initial state of the process is x, defined as:

V π (x) = E ∞ 0 e -θt c(X(t), π(t)) dt x 0 = x . (4)
Here, π(t) denotes the action prevailing at time t according to the policy π, given that the decisions prescribed by this policy are applied at the instants where events occur, and θ > 0 is a discount factor. The general objective of optimal control is to find, for every x, a policy π that minimizes the criterion V π (x). Classical results (e.g. [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]) on discounted, infinite-horizon, time-homogeneous Markovian optimal control have shown that, in many cases, policies from set F are globally optimal. However, for continuous-time models that are not uniformizable, which is the case here, this certainty is not known. It is then a practically reasonable objective to consider the optimization problem: find

π * = arg min π∈F V π (x) ,
provided this "min" is attained.

Bellman Equations

The first result is that the optimal value function satisfies a dynamic programming equation (Discounted Cost Optimality Equation, DCOE), generally known as a Bellman equation. Proposition 1. In the formal model, assume that the function λ(•) is bounded, α(•) and k(•) are bounded by polynomials. Then the value function of the problem satisfies the DCOE:

V (n, 0) = min c B + 1 λ(n -1) + α(n -1) + µ + θ k(n -1) + λ(n -1)V (n, 1) + α(n -1)V (n -2, 1) + µV (n -1, 0) , (5)
1 λ(n) + α(n) + θ [k(n) + λ(n)V (n + 1, 0) + α(n)V (n -1, 0)] (6)
for n ≥ 1,

V (0, 0) = 1 λ(0) + θ [k(0) + λ(0)V (1, 0)], (7)
V (n, 1) = 1 λ(n) + α(n) + µ + θ [k(n) + λ(n)V (n + 1, 1) + α(n)V (n -1, 1) + µV (n, 0)] , (8)
for n ≥ 0.

Moreover, the Bellman equations have a unique solution and provide an optimal feedback control:

Proposition 2. Under the assumptions of Proposition 1, the DCOE equations ( 5)-( 8) have a unique solution. In addition, any function γ : X → {0, 1} which realizes the "min" in ( 5)-( 6) is optimal in F .

The proofs of these results are in Appendix A and Appendix B, respectively.

Optimal policy

Our objective for the present paper is to solve the optimization problem described in Section 2.1 by finding explicitly the optimal control in the following special case, called the "base model".

Definition 2 (Base Model). The base model is the model defined in Section 2.2 with:

λ(n) = Λ, α(n) = nα, k(n) = nc Q .
This assumption on k(.) corresponds to the assumption that h

(n) is linear in the controlled queue- ing model of Section 2.1. Indeed, if h(n) = nc H then given the definition (3), k(n) = n(αc L + c H ) is also linear. The correspondence holds with c Q = αc L + c H .
The optimal control follows policies of special form. Define the following policies in F : Definition 3 ("No Service" and "Always Serve" policies). π N S ("no service") is the policy in F that selects a = 0 in every state, i.e. π N S (x) = 0, ∀x ∈ X . π AS ("always serve") is the policy in F that selects a = 1 in every relevant state, i.e. π AS (x) = 1, ∀x = (n, 0), n ≥ 1.

The principal result of the paper states as:

Theorem 1. Consider the Base Model. Then:

a) if c Q < c B (α + θ), then π N S is optimal; b) if c Q > c B (α + θ), then π AS is optimal; c) if c Q = c B (α + θ), then both π AS and π N S are optimal.
The proof of this theorem will be given in Section 6.2. In the next sections, we introduce the concepts needed in the proof: approximated uniformizable models in Section 4 and their structural properties in Section 5.

Smoothed and uniformized models

The main topic of this section is the presentation of approximations of the formal model that are uniformizable. The usual way of defining such approximations involves truncation. As shown by Bhulai, Brooms and Spieksma 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], the addition of smoothing may endow the approximations with more interesting structural properties. We therefore apply their "Smoothed Rate Truncation" (SRT) technique. We introduce in Section 4.1 several sets of assumptions on the model data, then we define in Section 4.2 the transition operators which we will later study in Section 5.

Assumptions

Consider the following assumptions bearing on the formal model of Section 2.2.

Assumption 1 (approximation).

There exists an integer number N ≥ 1, such that:

a) The function α(•) : N → R + is given by α(n) = min(n, N ) α . b) The function λ(•) : N → R + is given by λ(n) = Λ 1 - n N + . (9)
c) The function k(•) : N → R + is given by

k(n) = min(n, N + 1)c Q .
We stress the fact that the uniformized models are used as a mathematical device for obtaining results on the Base Model. As such, we are not interested in their "physical" relevance. In particular, part c) of this assumption does not correspond to the actual costs of the model, as they were identified in Section 2 and Definition 2. What is important is that when N goes to infinity, this model approaches the Base Model, in a sense to be discussed later on.

Definition of operators

We introduce now two operators T (u)

AS and T (u)

N S associated with the specific policies π AS and π N S introduced in Definition 3, as well as the dynamic programming operator T (u) of the problem. If Assumption 1 holds, it is possible to define

Λ := Λ + N α + µ, Λ(n) = Λ -α(n) -λ(n) and for n ≥ 1, c(n) := c B λ(n -1) + α(n -1) + µ + θ Λ + θ . ( 10
)
The rate Λ is the maximal transition rate in the model and Λ(n) is the rate of "dummy transitions" occurring in state n as a result of uniformization. Let V be the space of all functions from X to R. Define the following operators mapping V to V:

Definition 4 (No-Service operator, smoothed and uniformized model). Suppose that Assumption 1 holds. Let

Λ := Λ + N α + µ, Λ(n) = Λ -α(n) -λ(n).
The "no service" operator for the smoothed and uniformized model, T

N S , is defined as, for any V ∈ V:

(T (u) N S V )(n, 0) = 1 Λ + θ [k(n) + α(n)V (n -1, 0) + λ(n)V (n + 1, 0) + Λ(n)V (n, 0)] , (11)
(T (u) N S V )(n, 1) = 1 Λ + θ k(n) + α(n)V (n -1, 1) + λ(n)V (n + 1, 1) + µV (n, 0) + (Λ(n) -µ)V (n, 1) (12)
for n ≥ 0.

Definition 5 (Always-Service operator, smoothed and uniformized model). Suppose that Assumption 1 holds. Let

Λ := Λ + N α + µ, Λ(n) = Λ -α(n) -λ(n)
and let c(n) be defined as in [START_REF]Markov Decision Processes in Practice[END_REF].

The "always service" operator for the smoothed and uniformized model, T

AS , is defined as, for any V ∈ V:

(T (u) AS V )(n, 0) = c(n) + 1 Λ + θ k(n -1) + α(n -1)V (n -2, 1) + λ(n -1)V (n, 1) + µV (n -1, 0) + (Λ(n -1) -µ)V (n, 0) (13)
(T (u) AS V )(0, 0) = 1 Λ + θ [k(0) + λ(0)V (1, 0) + Λ(0)V (0, 0)] (14)
(T

(u) AS V )(n, 1) = 1 Λ + θ k(n) + α(n)V (n -1, 1) + λ(n)V (n + 1, 1) + µV (n, 0) + (Λ(n) -µ)V (n, 1) , (15)
for n ≥ 1 in ( 13) and n ≥ 0 in [START_REF] Hyon | Scheduling services in a queuing system with impatience and setup costs[END_REF].

Observe that when n = 0 in ( 12) or ( 15), the undefined value V (-1, 1) is always multiplied by α(0) = 0. Observe also that (T

(u) AS V )(0, 0) = (T (u) N S V )(0, 0) and (T (u) AS V )(n, 1) = (T (u) N S V )(n, 1) for all n ≥ 1.
Definition 6. Assume Assumption 1 holds. Define the operator T (u) as, for any V ∈ V:

T (u) V = min{T (u) AS V, T (u) N S V }.
The operator T (u) is the dynamic programming operator of the uniformized approximated model. In the sequel, we shall use indifferently the notations (T (u) V )(x) = T (u) V (x) for the value of the function obtained by applying T (u) on function V . Likewise for operators T The value function V (u) of this problem is the unique solution of the Bellman equation:

Bellman equations

T (u) V = V . (16)
In addition, any function γ such that γ(x) = arg min{T

(u) AS V (u) (x), T (u) N S V (u) (x)} is optimal in F .
Proof. The statement is a corollary of Proposition 1 and Proposition 2, given the definitions of T (u)

AS , T (u)

N S and T (u) in Definitions 4-6. These propositions indeed apply since under Assumption 1, and for every fixed N , λ(•), α(•) and k(•) (hence h(•)) are bounded.

Structural properties of smoothed and uniformized models

We now turn to the analysis of structural properties for the uniformized models defined in 4. We define a set of structural properties of value functions in Section 5.1, and we show that these properties propagate through the operators T (u) N S and T (u) AS in 5.2. These results will be exploited in Section 6. For functions V ∈ V, define the following functional: ∆ n : V → V as:

(∆ n V )(n, b) = V (n + 1, b) -V (n, b), (n, b) ∈ X .

Definition of properties

One defines here the following properties for functions V ∈ V.

First of all, we should make it precise that, when we write that a function

f (n) defined from N → R is increasing over a range n ∈ [a 1 ..a 2 ], or, more commonly, for a 1 ≤ n ≤ a 2 , we mean that f (n + 1) ≥ f (n) for a 1 ≤ n < a 2 . Secondly, when we write that a function f (n) defined from N → R is convex over a range n ∈ [a 1 ..a 2 ], or, more commonly, for a 1 ≤ n ≤ a 2 , we mean that f (n + 2) -2f (n + 1) + f (n) ≥ 0 for a 1 ≤ n < a 2 -1. If a 1 ≤ a 2 ≤ a 1 + 1, this requirement is void.
In all situations, writing that a function f has some property over the range [a 1 ..a 2 ] involves the values f (a 1 ), . . . , f (a 2 ) and no other value. Definition 7 (Properties of value functions). Let V ∈ V. Assume Assumption 1 holds for some N . Let Φ := N α. We say that V has property:

Picx if n → ∆ n V (n, 0) is positive and increasing for 0 ≤ n ≤ N ; P1 if a) ∆ n V (n, 0) ≤ c Q /(α + θ + Λ/N ) for all 0 ≤ n ≤ N ; b) ∆ n V (0, 0) ≥ c B P2 if n → (Φ -α(n))∆ n V (n, 0) + α(n -1)∆ n V (n -1, 0) is increasing for 1 ≤ n ≤ N ; P3 if n → λ(n)∆ n V (n + 1, 0) + (Λ -λ(n -1))∆ n V (n, 0) is increasing for 1 ≤ n ≤ N ; P4 if V (n + 1, 0) = V (n, 1) + c B , for all 0 ≤ n ≤ N ; Plin if V satisfies: V (n, 0) = V (n, 1) = c Q α + θ + Λ/N n + Λ θ , ∀ 0 ≤ n ≤ N . (17)
In the remainder of this section, we will show results grouped in three categories:

1. simple implications between the properties of Definition 7, in Section 5.2

propagation of properties by operator T (u)

AS , independently of the fact that it realizes optimality in the dynamic programming equation, in Section 5.4,

propagation of properties by operator T (u)

N S , independently of the fact that it realizes optimality in the dynamic programming equation, in Section 5.5.

Implications and identities for properties

We show now that P2 and P3 are a consequence of Picx.

Lemma 1. Assume that Assumption 1 holds, and let V ∈ V satisfy Picx. Then V satisfies P2 and P3.

The proof uses the following lemma. This lemma is stated in a quite generic way: although all its statements are not used in the remainder, it is useful to realize what features of the functions λ(•) and α(•) are essential in the analysis.

Lemma 2. Let f : N → R be a function which is positive and increasing for a 1 ≤ n ≤ a 2 . Let g: N → R be a positive and convex function, bounded above by G. Let h: N \ {0} → R be the function defined by

h(n) := g(n)f (n) + (G -g(n -1))f (n -1) .
Then h is positive and:

a) h is increasing for a 1 + 1 ≤ n ≤ a 2 . b) If in addition a 1 ≥ 1 and g(a 1 -1) = G, h is increasing for a 1 ≤ n ≤ a 2 . c) If in addition g(a 2 + 1) = 0, h is increasing for a 1 + 1 ≤ n ≤ a 2 + 1.
Proof. For n ≥ 1, we have:

h(n + 1) -h(n) = g(n + 1)f (n + 1) + (G -g(n))f (n) -[g(n)f (n) + (G -g(n -1))f (n -1)] = g(n + 1)(f (n + 1) -f (n)) +(g(n + 1) + G -g(n) -g(n) -G + g(n -1))f (n) +(G -g(n -1))(f (n) -f (n -1)) = g(n + 1) (f (n + 1) -f (n)) (18) +(g(n + 1) -2g(n) + g(n -1)) f (n) +(G -g(n -1)) (f (n) -f (n -1)) . ( 19
)
Since f is increasing on the range a 1 ≤ n ≤ a 2 and g positive, then the first of these three terms is positive for

a 1 ≤ n ≤ a 2 -1 The second one is positive for a 1 + 1 ≤ n ≤ a 2 (or for a 1 ≤ n ≤ a 2 when a 1 ≥ 1)
. Indeed, f is positive and g is convex for any n ∈ N. The third one is positive for [START_REF] Larrañaga | Efficient content delivery in the presence of impatient jobs[END_REF] vanishes when n = a 1 , so the sum remains positive even for n = a 1 . This proves b).

a 1 + 1 ≤ n ≤ a 2 since f is increasing on the range a 1 ≤ n ≤ a 2 , and G -g(n -1) is positive. The increments of h are positive for a 1 + 1 ≤ n ≤ a 2 -1 so the part a) of the lemma is proved. If a 1 ≥ 1 and g(a 1 -1) = G, then
If g(a 2 + 1) = 0, then (18) vanishes when n = a 2 , so the sum remains positive even for n = a 2 . This proves c).

Proof of Lemma 1. For Property P2, let f (n) = ∆ n V (n, 0). This is a positive function, increasing for 0 ≤ n ≤ N since V satisfies Picx. Let also g(n) = Φ -α(n). This function is: a) positive and convex; b) bounded by Φ = N α. Lemma 2 a) applies therefore with

a 1 = 0, a 2 = N and G = Φ, to conclude that n → (Φ -α(n))∆ n V (n, 0) + α(n -1)∆ n V (n -1, 0) is increasing for 1 ≤ n ≤ N ; in other words, P2 holds.
For Property P3, let f (n) = ∆ n V (n + 1, 0). This is a positive function, increasing for 0 ≤ n ≤ N -1. Let also g(n) = λ(n). This function is: a) positive and convex; b) bounded by Λ; c) such that g(N ) = 0. Lemma 2 a) and c) apply therefore with a 1 = 0,

a 2 = N -1 and G = Λ, to conclude that n → λ(n)∆ n V (n + 1, 0) + (Λ -λ(n -1))∆ n V (n, 0) is increasing for 1 ≤ n ≤ N ; in other words, P3 holds.

Identities for difference operators

In this part we give the expressions of ∆ n for the operators

T (u) AS and T (u) N S .
Observe that in the case where P4 holds, the value (T (u) AS V )(n, 0) defined in ( 13) can be rewritten eliminating terms V (m, 1). We formulate this, and other consequences, in the next lemmas.

Lemma 3 (Formula of ∆ n T (u) AS V ). Let Assumption 1 hold. Assume V satisfies P4. Then for all 1 ≤ n ≤ N , ( Λ + θ)T (u) AS V (n, 0) = c B (µ + θ) + (n -1)c Q +α(n -1)V (n -1, 0) + λ(n -1)V (n + 1, 0) +µV (n -1, 0) + (Λ(n -1) -µ) V (n, 0) . ( 20
)
As a consequence, we have, for

∆ n T (u) AS V (n, 0) := (T (u) AS V )(n + 1, 0) -(T (u) AS V )(n, 0) ( Λ + θ)∆ n T (u) AS V (n, 0) = c Q + µ∆ n V (n -1, 0) +λ(n)∆ n V (n + 1, 0) + Λ -λ(n -1) ∆ n V (n, 0) (21) + Φ -α(n) ∆ n V (n, 0) + α(n -1)∆ n V (n -1, 0)
for 1 ≤ n < N , and

( Λ + θ)∆ n T (u) AS V (0, 0) = c B (µ + θ) + Λ∆ n V (1, 0) + Φ∆ n V (0, 0) . ( 22
)
Proof. In Formula (13), we see that the only instances of V (m, 1) are V (n, 1) and V (n -2, 1). Since by P4, V (m, 1) = V (m + 1, 0) -c B for 0 ≤ m ≤ N , we can therefore eliminate them and obtain, for all 1 ≤ n ≤ N :5

( Λ + θ)T (u) AS V (n, 0) = c B (λ(n -1) + α(n -1) + µ + θ) +k(n -1) + α(n -1)(V (n -1, 0) -c B ) +λ(n -1)(V (n + 1, 0) -c B ) + µV (n -1, 0) + (Λ(n -1) -µ)V (n, 0)
which is rearranged into [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF]

remembering that k(n -1) = (n -1)c Q . Next, we express the difference ∆ n T (u) AS V (n, 0) := (T (u) AS V )(n + 1, 0) -(T (u)
AS V )(n, 0), for 1 ≤ n < N . We use [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF] and obtain:

( Λ + θ)∆ n T (u) AS V (n, 0) = c Q + α(n)V (n, 0) + λ(n)V (n + 2, 0) +µV (n, 0) + (Λ(n) -µ)V (n + 1, 0) -[α(n -1)V (n -1, 0) + λ(n -1)V (n + 1, 0) + µV (n -1, 0) + (Λ(n -1) -µ)V (n, 0)] .
We replace Λ(n) by its value Λ + Φ + µ -α(n) -λ(n) to get for all 1 ≤ n < N :

( Λ + θ)∆ n T (u) AS V (n, 0) = c Q + α(n)V (n, 0) + λ(n)V (n + 2, 0) +µV (n, 0) + [Λ + Φ -α(n) -λ(n)]V (n + 1, 0) -α(n -1)V (n -1, 0) + λ(n -1)V (n + 1, 0) + µV (n -1, 0) + [Λ + Φ -α(n -1) -λ(n -1)]V (n, 0) .
Finally, grouping the terms depending on µ, λ and α leads to [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF].

In the case n = 0, we have, from [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF] for n = 1 (observe that N ≥ 1 due to Assumption 1) and ( 14),

( Λ + θ)∆ n T (u) AS V (0, 0) = ( Λ + θ)(T (u) AS V (1, 0) -T (u) AS V (0, 0)) = c B (µ + θ) +α(0)V (0, 0) + λ(0)V (2, 0) + µV (0, 0) + (Λ(0) -µ)V (1, 0) -[k(0) + λ(0)V (1, 0) + Λ(0)V (0, 0)] = c B (µ + θ) + Λ [V (2, 0) -V (1, 0)] + Φ [V (1, 0) -V (0, 0)] .
In the last step of this derivation, we have used the fact that α(0) = 0 and λ(0) = Λ, from Assumption 1, k(0) = 0 and the value Λ(0) = Φ + µ. This expression simplifies into [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF].

We define the difference ∆ q T (u) V which represents the difference between the choice of serving a customer or not serving a customer. For functions V ∈ V and for all n ≥ 0, define the following difference ∆ q T (u) : V → R as:

∆ q T (u) V (n) := (T (u) AS V )(n, 0) -(T (u) N S V )(n, 0). ( 23
)
Properties of this operator are summarized in the following result.

Lemma 4 (Properties of ∆ q T (u) V ). Assume that Assumption 1 holds. The function ∆ q T (u) V defined in (23) has the following properties:

i) ∆ q T (u) V (0) = 0 for every V ∈ V; ii) If V satisfies P4, then for 1 ≤ n ≤ N : ( Λ + θ)∆ q T (u) V (n) = (µ + θ) (c B -∆ n V (n -1, 0)) -c Q + (α + θ) ∆ n V (n -1, 0) + (Λ/N ) ∆ n V (n, 0) . ( 24
)
iii) If V satisfies P4, then for n = N + 1, ∆ q T (u) V (n) is given by:

( Λ + θ)∆ q T (u) V (N + 1) = (µ + θ)c B -c Q -µ∆ n V (N, 0) . ( 25
) iv) If V satisfies Plin, then for 1 ≤ n ≤ N , ( Λ + θ)∆ q T (u) V (n) = c B - c Q α + θ + Λ/N (µ + θ + α(n -1) + λ(n -1)) . ( 26
) Inria Proof. i) The case n = 0 is immediate since T (u)
AS and T (u)

N S have the same value at (n, 0). ii) Since V satisfies P4, Lemma 3 applies and we use [START_REF] Movaghar | Optimal control of parallel queues with impatient customers[END_REF] for T (u) AS V (n, 0) and [START_REF] Deb | Optimal control of batch service queues[END_REF] for

T (u) N S V (n, 0) to obtain, for all 1 ≤ n ≤ N , ( Λ + θ)∆ q T (u) V (n) = c B (µ + θ) + (n -1)c Q +α(n -1)V (n -1, 0) + λ(n -1)V (n + 1, 0) +µV (n -1, 0) + (Λ(n -1) -µ)V (n, 0) -[nc Q + α(n)V (n -1, 0) + λ(n)V (n + 1, 0) + Λ(n)V (n, 0)] = c B (µ + θ) -c Q +[α(n -1) -α(n) + µ] V (n -1, 0) +[Λ(n -1) -µ -Λ(n)] V (n, 0) +[λ(n -1) -λ(n)] V (n + 1, 0) = c B (µ + θ) -c Q +[α(n -1) -α(n) + µ] V (n -1, 0) +[-λ(n -1) -µ + λ(n) + α(n) -α(n -1)] V (n, 0) +[λ(n -1) -λ(n)] V (n + 1, 0) .
We replaced Λ(n) by its value in this last equation. Now we group the terms in α(n -1) -α(n) + µ and these in λ(n -1) -λ(n) to identify the instances of ∆ n . Finally we use the specific forms of α(•) and λ(•) in Assumption 1. In a last step, we add and subtract the term (µ + θ)∆ n V (n -1, 0) to get:

( Λ + θ)∆ q T (u) V (n) = c B (µ + θ) -c Q +(α -µ) (∆ n V )(n -1, 0) +(Λ/N ) (∆ n V )(n, 0) , (27) = c B (µ + θ) -c Q -(µ + θ)∆ n V (n -1, 0) +(α -µ) ∆ n V (n -1, 0) + (µ + θ)∆ n V (n -1, 0) +(Λ/N ) ∆ n V (n, 0) ,
and then the final form [START_REF] Ward | Asymptotically optimal admission control with impatient customers[END_REF].

iii) When n = N + 1, consider Equation [START_REF] Deb | Optimal control of batch service queues[END_REF] and Equation [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]. Since Assumption 1 holds then all the terms in "λ" disappear. Computing the difference, and using the fact that k(N +1)-k(N ) = c Q according to Assumption 1 c), we obtain

( Λ + θ)∆ q T (u) V (N + 1) = c B (µ + θ) -c Q + α(N )(c B + V (N -1, 1) -V (N, 0)) -µ∆ n V (N, 0) . Since V satisfies P4, c B + V (N -1, 1
) -V (N, 0) = 0 and we obtain Equation [START_REF] Weiss | Optimal ordering policies for continuous review perishable inventory models[END_REF].

iv) Going back to the definitions ( 11) and ( 13), we obtain respectively, for any n ≥ 1,

( Λ + θ)T (u) N S V (n, 0) = k(n) + ΛV (n, 0) -α(n)∆ n V (n -1, 0) + λ(n)∆ n V (n, 0) ( Λ + θ)T (u) AS V (n, 0) = k(n -1) + ΛV (n, 0) + α(n -1)(c B + V (n -2, 1) -V (n, 0)) + λ(n -1)(c B + V (n, 1) -V (n, 0)) -µ∆ n V (n -1, 0) + c B (µ + θ).
If V satisfies Plin, that is, [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF], then for all 1 ≤ n ≤ N , V (n, 1) = V (n, 0) and also, for all

0 ≤ n < N , ∆ n V (n, 0) = V (n + 1, 0) -V (n, 1) = ∆ := c Q α + θ + Λ/N . The occurrences of V (m, 1) in ( Λ + θ)T (u) AS V (n, 0) involve only values of m with 1 ≤ m ≤ N . Also, occurrences of ∆ n V (m, 0) involve only values of m with 1 ≤ m < N . Only in ( Λ + θ)T (u)
N S V (n, 0), for n = N , does the value of ∆ n V (N, 0) appear. This value is unknown but is multiplied by λ(N ) = 0 so we can ignore it. In other words, the identity

λ(n)∆ n V (n, 0) = λ(n) c Q α + θ + Λ/N holds for all n, 1 ≤ n ≤ N .
Consequently, for 1 ≤ n ≤ N ,

( Λ + θ)∆ q T (u) V (n) = k(n -1) + α(n -1)(c B -2∆) + λ(n -1)c B -µ∆ + c B (µ + θ) -[k(n) -α(n)∆ + λ(n)∆] = c B (µ + θ + α(n -1) + λ(n -1)) -c Q -∆[µ + λ(n) + 2α(n -1) -α(n)] = c B (µ + θ + α(n -1) + λ(n -1)) -∆(µ + θ + λ(n -1) + α(n -1)) + ∆(α + θ + λ(n -1) -λ(n)) -c Q .
In the last rewriting, we have used the specific properties of α(n) deriving from Assumption 1. The last line cancels out since ∆(α + θ + Λ/N ) = c Q . There remains (26).

Invariant properties for operator T (u) AS

Throughout this section, we shall assume that

c B ≤ c Q α + θ + Λ/N . ( 28
)
The main result of this section is the following:

Proposition 3 (Propagation for T (u)
AS ). Let Assumption 1 and (28) hold. Let V ∈ V be a function which satisfies properties Picx, P1 a), P1 b) and P4. Then T (u) AS V also satisfies these four properties.

We shall decompose the proof in separate lemmas, for each individual propagation.

Lemma 5 (Propagation of P4 for T (u) AS ). Let Assumption 1 and (28) hold. Let V ∈ V be a function which satisfies property P4. Then T (u) AS V also satisfies P4.

Proof. We identify the term T (u) AS V (n, 0) evaluated at n + 1 in (13), and T (u) AS V (n, 1) with [START_REF] Hyon | Scheduling services in a queuing system with impatience and setup costs[END_REF]. We find that for n ≥ 0:

T (u) AS V (n + 1, 0) -T (u) AS V (n, 1) = c(n + 1) + 1 Λ + θ (Λ(n) -µ) [V (n + 1, 0) -V (n, 1)] .
Since V satisfies P4, V (n + 1, 0) = V (n, 1) + c B for all 0 ≤ n ≤ N and it remains:

T (u) AS V (n + 1, 0) -T (u) AS V (n, 1) = c(n + 1) + 1 Λ + θ (Λ(n) -µ)c B = c B ,
for n in the same range. This means that T AS V (n, 0): it should be non negative and increasing in the required intervals.

i) Non negativity. All the terms in the right-hand side of ( 21) and ( 22) are positive, since ∆ n V (n, 0) is positive when 0 ≤ n ≤ N , by Picx.

ii) Monotonicity. In the case N = 1, the monotonicity requirement of ∆ n T (u)

AS V (n, 0) vanishes. We therefore assume N ≥ 2 in the following.

The first line of the right-hand side of ( 21) is an increasing function of n for 1 ≤ n ≤ N , since V satisfies Picx. The second and the third lines are also increasing for 1 ≤ n ≤ N , since V satisfies Picx, and therefore P2 and P3 by Lemma 1.

There remains to prove the increasing of increments at n = 0, that is equivalent to show that

∆ n T (u) AS V (0, 0) ≤ ∆ n T (u) AS V (1, 0). We obtain ∆ n T (u)
AS V (0, 0) from ( 22) and ∆ n T (u) AS V (1, 0) from ( 21) evaluated at n = 1, since we have assumed that V satisfies P4. We obtain therefore, with α(0) = 0, α(1) = α and λ(0) = Λ:

( Λ + θ)(∆ n T (u) AS V (0, 0) -∆ n T (u) AS V (1, 0)) = c B (µ + θ) -c Q -µ∆ n V (0, 0) +Λ∆ n V (1, 0) -λ(1)∆ n V (2, 0) +N α∆ n V (0, 0) -(N α -α)∆ n V (1, 0) .
Adding and subtracting the quantities λ(1)∆ n V (1, 0), α∆ n V (0, 0) and θ∆ n V (0, 0) we have:

( Λ + θ)(∆ n T (u) AS V (0, 0) -∆ n T (u) AS V (1, 0)) = c B (µ + θ) -c Q -µ∆ n V (0, 0) + θ∆ n V (0, 0) -θ∆ n V (0, 0) +Λ∆ n V (1, 0) -λ(1)∆ n V (2, 0) -λ(1)∆ n V (1, 0) + λ(1)∆ n V (1, 0) +N α∆ n V (0, 0) -(N α -α)∆ n V (1, 0) + α∆ n V (0, 0) -α∆ n V (0, 0) = (µ + θ)(c B -∆ n V (0, 0)) -c Q + (Λ -λ(1))∆ n V (1, 0) + (α + θ)∆ n V (0, 0) +λ(1)(∆ n V (1, 0) -∆ n V (2, 0)) +(N α -α)(∆ n V (0, 0) -∆ n V (1, 0)) .
The two last terms in this expression are negative since

∆ n V (n, 0) is increasing for 0 ≤ n ≤ N (the assumption that N ≥ 2 is needed here). By assumption P1 b), c B -∆ n V (0, 0) ≤ 0, then (µ + θ)(c B -∆ n V (0, 0)) is negative. For the remaining terms, observe that Λ -λ(1) = Λ/N and that, by assumption P1 a), ∆ n V (n, 0) ≤ c Q /(α + θ + Λ/N ) for n = 0, 1. Therefore, -c Q + (Λ -λ(1))∆ n V (1, 0) + (α + θ)∆ n V (0, 0) ≤ -c Q + c Q α + θ + Λ/N (α + θ + Λ/N ) = 0.
Summing up, we have shown that

∆ n T (u) AS V (0, 0) -∆ n T (u) AS V (1, 0) ≤ 0, so that ∆ n T (u) AS V (n, 0) is increasing for 0 ≤ n ≤ N .
We have therefore proved the non-negativity and the increasing of increments of T Proof. We proceed with bounding below the terms in [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF], which holds since P4 is assumed. By Assumption P1 b) on V , V (0, 0) ≥ c B . By Assumption Picx (the convexity part),

∆ n V (1, 0) ≥ ∆ n V (0, 0) ≥ c B . Therefore, ( Λ + θ)∆ n T (u) AS V (0, 0) ≥ c B (µ + θ + Λ + Φ) = c B ( Λ + θ) .
We have proved that T

Proof. Expression (21) holds for T (u)

AS for 1 ≤ n ≤ N , since we have assumed P4. We proceed with bounding above the terms in [START_REF] Papadaki | Exploiting structure in adaptative dynamic programming algorithms for a stochastic batch service problem[END_REF]. As a preliminary, observe that the bound

λ(n)∆ n V (n + 1, 0) ≤ c Q α + θ + Λ/N λ(n)
holds for all n ≥ 0. Indeed, it holds for 0 ≤ n < N by P1 a) on V , but also for n ≥ N since, by Assumption 1, λ(n) = 0. In that case, both sides are 0. Then, all multiplying coefficients of ∆ n V in ( 21) being positive, we get, for 1 ≤ n ≤ N ,

( Λ + θ)∆ n T (u) AS V (n, 0) ≤ c Q + c Q α +θ +Λ/N µ + λ(n) + Λ -λ(n -1) +(N -n)α + (n -1)α = c Q α + θ + Λ/N α + θ + Λ/N + µ -Λ/N + Λ + N α -α = c Q α + θ + Λ/N ( Λ + θ) .
In other words, T

AS V satisfies P1 a) restricted to 1 ≤ n ≤ N . There remains to handle the case n = 0. We then turn to [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]. Bounding above, we have

(Λ + Φ + µ + θ)∆ n T (u) AS V (0, 0) = c B (µ + θ) + Λ∆ n V (1, 0) + Φ∆ n V (0, 0) ≤ c B (µ + θ) + (Λ + Φ) c Q α + θ + Λ/N = c B (α + θ + Λ/N ) (µ + θ) + (Λ + Φ)c Q α + θ + Λ/N ≤ c Q (µ + θ) + (Λ + Φ)c Q α + θ + Λ/N . ( 29
)
In the last inequality, we have used (28) which is equivalent to c

B (α+θ+Λ/N ) ≤ c Q . Inequality (29) implies ∆ n T (u) AS V (0, 0) ≤ c Q /(α + θ + Λ/N ), hence the lemma.
We conclude the section with the proof of its main result:

Proof of Proposition 3. Since V satisfies Picx and P1 a), P1 b) and P4, T

AS V satisfies P4 by Lemma 5, Picx by Lemma 6, P1 b) by Lemma 7 and P1 a) by Lemma 8.

Invariant property for operator T (u) N S

Throughout this section, we shall assume that

c B ≥ c Q α + θ + Λ/N . ( 30
)
The next lemma states essentially that, under this condition, the fixed point of operator T

N S V (n, b) = V (n, b) for all 0 ≤ n ≤ N , b ∈ {0, 1}.
Proof. Let us use in this proof the form V (n, 0) = A(n + B), valid for 0 ≤ n ≤ N . Observe that since λ(n) vanishes for n ≥ N by Assumption 1, we have λ(n)V (n + 1, 0) = λ(n)A(n + 1 + B) for every n ∈ N (a "trick" that was used already in the proof of Lemma 8). Also, α(n)V (n -1, 0) = α(n)A(n -1 + B) for all 1 ≤ n ≤ N + 1. From Equation ( 11) we then get

( Λ + θ)T (u) N S V (n, 0) = nc Q + ΛA(n + B) + λ(n)A -α(n)A = nc Q + ΛA(n + B) + θA(n + B) -θA(n + B) + λ(n)A -α(n)A = ( Λ + θ)V (n, 0) + nc Q + A[-θ(n + B) + λ(n) -α(n)] .
Let us replace A, B, λ(n) and α(n) by their values. For 0 ≤ n ≤ N , we get

( Λ + θ)T (u) N S V (n, 0) = ( Λ + θ)V (n, 0) + nc Q + A -θn -Λ + Λ -n Λ N -nα = ( Λ + θ)V (n, 0) + nc Q - nc Q α + θ + Λ/N θ + Λ N + α = ( Λ + θ)V (n, 0)
hence the statement for b = 0. When b = 1, we see from Equation ( 12) that if V (n, 0) = V (n, 1) for 0 ≤ n ≤ N , then the terms multiplied by µ disappear and (12) reduces to [START_REF] Deb | Optimal control of batch service queues[END_REF]. The previous calculation applies and T (u) N S V (n, 1) = V (n, 0), hence the result.

Optimality results

In this section, we collect optimality results for the approximated models and then we apply them to find the optimal policy for the Base Model (Definition 2). To this aim, we use the recent results of [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] allows us to extend the results in truncated model in the Base Model.

Optimality results in the approximated models

In this section, we study and exhibit the optimal policy in approximated models defined by Assumption 1. This is done using the propagation framework presented by Puterman [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF] or Koole [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF]. This framework does not work in the Base Model (as it will be seen in Section 7.1) but when adapted in truncated and smoothed models this framework allows to determine properties of optimal policies. However, the propagation framework proofs usually proceed by showing the submodularity of the operator T (u) since the submodularity induces the monotonicity of the function ∆ q T (u) V (n) and therefore the optimal decision rule. But, in our case it will be shown in Example 4, that the submodularity does not occur and we should refine the study of the sign of ∆ q T (u) V (n).

Before proceedings, we comment briefly on the validity of using a framework from [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF] in the context of the control model of [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF] or [START_REF] Blok | Markov Decision Processes in Practice, chapter Structures of Optimal Policies in MDPs with Unbounded Jumps: The State of Our Art[END_REF]. Indeed, in the former control policies are applied at certain decision epochs and in the latter, they are applied continuously. However, since for finite Markov models it is known that optimal policies (in the sense of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]) can be found in the set of Markov Deterministic Policies (denoted with D M D in [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]), it does not matter whether the policy is seen as applied at some time instant or continuously: as long as the state of the system does not change, the policy does not change. Moreover, structure propagation is essentially concerned with value functions and Bellman operators. As long it has been proved, with either MDP model, that the optimal value function satisfies some Bellman equation, the framework may be used, in line with the roadmap proposed in [START_REF] Blok | Markov Decision Processes in Practice, chapter Structures of Optimal Policies in MDPs with Unbounded Jumps: The State of Our Art[END_REF].

Overview of the propagation framework

We give now a brief recall of the propagation framework. Consider a MDP with discrete state space and bounded rewards, with the expected total discounted cost as optimization criterion. Denote with V the set of value functions. Let d ∈ F be a Markov (feedback) decision rule, let T d be the operator acting on V that computes the one-step value of the policy d with terminal value V ∈ V. Let T = inf d∈F T d be the dynamic programming operator of the problem.

In the following statement, V σ ∈ V is interpreted a set of value functions such that some "structured" properties are satisfied, and D σ is a corresponding set of "structured" decision rules.

Theorem 3 (Theorem 6.11.1 in [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]). Consider a countable-state, discrete-time Markov Decision Problem, with bounded costs, and dynamic programming operator T . Assume that:

1. for each V ∈ V, there exists a deterministic Markov decision rule d such that T V = T d V , and that there exist non-empty sets V σ ⊂ V and D σ ⊂ F such that:

2. V ∈ V σ implies T V ∈ V σ , 3. V ∈ V σ implies there exists a decision rule d such that d ∈ D σ ∩ arg min d T d V , 4. V σ is a closed subset of V under simple convergence.
Then, there exists an optimal stationary policy d * in F with d * ∈ D σ ∩ arg min d T d V .

We will apply this theorem to the approximated models specified by Assumption 1. In this context, the set V σ will typically be defined by some of the properties introduced in Definition 7, and the set D σ will specify which action to take in certain states of X .

We identify the suitable sets and prove that they satisfy the assumptions of Theorem 3 in Section 6.1.3. A technical point is to check that the sets V σ and D σ are not empty. We address this point in 6.1.4. Before this, we establish in Section 6.1.2 a preliminary result that relates the dynamic programming operator T (u) to the operators T Now, we establish formally results about the sign of the difference

∆ q T (u) V (n) = T (u) AS V (n, 0) - (T (u)
N S V )(n, 0) which imply partial optimality results for the approximated models. More precisely, the two following lemmas allows to handle requirement 3 of Theorem 3.

Lemma 10 (Result for small c B ). Let Assumption 1 and (28) hold. Let V ∈ V be a function with properties Picx, P1 a), P1 b) and P4. Then, for 0

≤ n ≤ N + 1 : i) ∆ q T (u) V (n) ≤ 0; ii) T (u) V (n, 0) = T (u)
AS V (n, 0). Proof. i) Since V satisfies P4, Lemma 4 applies. Then ∆ q T (u) V (0) = 0. Further, under Assumption (28) we have Equation ( 24), namely: [START_REF] Ward | Asymptotically optimal admission control with impatient customers[END_REF], these bounds lead to

( Λ + θ)∆ q T (u) V (n) = (µ + θ) (c B -∆ n V (n -1, 0)) -c Q + (α + θ) ∆ n V (n -1, 0) + (Λ/N ) ∆ n V (n, 0) , for 1 ≤ n ≤ N . By Assumption P1 b), we have c B -∆ n V (n -1, 0) ≤ 0. By Picx, we have ∆ n V (n -1, 0) ≤ ∆ n V (n, 0). By P1 a) it follows that ∆ n V (n -1, 0) and ∆ n V (n, 0) are both smaller than c Q /(α + θ + Λ/N ). Used in
( Λ + θ)∆ q T (u) V (n) ≤ 0 for 1 ≤ n ≤ N .
Finally, for n = N + 1 we have Equation ( 25) from which it follows:

( Λ + θ)∆ q T (u) V (N + 1) = c B (µ + θ) -c Q -µ∆ n V (N, 0)
.

By (28), we have c B (µ + θ + Λ/N ) -c Q ≤ 0, hence c B (µ + θ) -c Q ≤ -c B Λ/N ≤ 0. Since ∆ n V (N, 0) ≥ 0 by Picx, then ∆ q T (u) V (N + 1) ≤ 0. This completes the proof of i). ii) From i), ∆ q T (u) V (n) ≤ 0 for 0 ≤ n ≤ N + 1, in other words, T (u) AS V (n, 0) ≤ (T (u) N S V )(n, 0). But according to Definition 6, T (u) V = min{T (u) AS V, T (u) N S V }. We conclude that for 0 ≤ n ≤ N + 1, T (u) V (n, 0) = T (u) AS V (n, 0).
We have the similar result for large c B .

Lemma 11 (Result for large c B ). Let Assumption 1 and Condition (30) hold. Let V be a function satisfying Plin. Then, for 0 ≤ n ≤ N :

i) ∆ q T (u) V (n, 0) ≥ 0 ; ii) T (u) V (n, 0) = T N S V (n, 0) .
Proof. i) According to Lemma 4 i) and iv): for a function V that satisfies Plin then on the one hand, ∆ q T (u) V (0) = 0 and on the other hand, (26) holds, namely, for all 1 ≤ n ≤ N :

( Λ + θ)∆ q T (u) V (n, 0) = µ + θ + λ(n -1) + α(n -1) c B - c Q α + θ + Λ/N .
Under Condition (30), this is the product of two non-negative terms, which proves i).

ii

) From i), ∆ q T (u) V (n) ≥ 0 for 0 ≤ n ≤ N , in other words, T (u) AS V (n, 0) ≥ (T (u) N S V )(n, 0). Since, according to Definition 6, T (u) V = min{T (u) AS V, T (u) N S V }, we conclude that for 0 ≤ n ≤ N , T (u) V (n, 0) = T (u)
N S V (n, 0). This concludes the proof.

Invariant properties for operator T (u)

We now integrate the results for operators T (u)

AS and T (u)

N S to obtain propagation results for operator T (u) . The objective is to ascertain requirement 2 of Theorem 3.

Proposition 4 (Propagation for T (u) for small c B ). Let Assumption 1 and Condition (28) hold. Let V ∈ V be a function which satisfies properties Picx, P1 a), P1 b) and P4. Then T (u) V also satisfies these four properties.

Proof. According to Lemma 10,

T (u) V (n, 0) = T (u)
AS V (n, 0) for all 0 ≤ n ≤ N + 1. On the other hand, we have, by definition,

T (u) AS V (n, 1) = T (u) N S V (n, 1) for all n ≥ 0. Therefore T (u) V (n, 1) = T (u)
AS V (n, 1) for all n ≥ 0, in particular for 0 ≤ n ≤ N + 1.

By Proposition 3, T AS V , they hold for T (u) V .

Proposition 5 (Propagation for T (u) for large c B ). Let Assumption 1 hold, Condition (30) hold and let V ∈ V be a function which satisfies Condition [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF]. Then T (u) V also satisfies Condition [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF].

Proof. According to Lemma 11, T (u) V (n, 0) = T (u)
N S V (n, 0) for all 0 ≤ n ≤ N . On the other hand, we have, by definition,

T (u) N S V (n, 1) = T (u) N S V (n, 1) for all n ≥ 0. Therefore T (u) V (n, 1) = T (u)
N S V (n, 1) for all n ≥ 0, in particular for 0 ≤ n ≤ N .

By Lemma 9, we know that a function V that satisfies [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF] is such that T

N S V also satisfies it. Since T (u) N S V and T (u) V coincide for states (n, 0), 0 ≤ n ≤ N , T (u) satisfies (17).

Initial Value function

The structural propagation framework is based on the propagation of properties through the dynamic programming operator. It works if it is possible to find a function in order to initiate the process. This necessity is present in the requirement that the set of functions V σ be non-empty in Theorem 3.

In this section, we identify a function that indeed satisfies the properties to be propagated, namely, Picx, P1 a), P1 b), and P4 when (28) holds or Equation ( 17) when (30) holds.

Observe that the very usual choice of a null function does not work here: Condition P1 b) coupled with Picx imposes that the function be strictly increasing and convex. Up to our knowledge it is an unusual case. We exhibit now such a function which satisfies all the required properties. We chose a form that covers both cases (28) and (30).

Let us define

χ = (α + θ + Λ N ) c B c Q -1 ,
and let us define V 0 (n, b) for all n ≥ 0:

6 V 0 (n, 0) = c Q α + θ + Λ/N n + max(0, χ) χ Λ θ (31) V 0 (n, 1) = c Q α + θ + Λ/N n + max(0, χ) χ Λ θ + min(χ, 0) . ( 32
)
We now state that the above function satisfies all properties to be propagated, that is:

Lemma 12.
Let Assumption 1 hold. Then: i) If (28) holds, the function V 0 satisfies properties Picx, P1 a), P1 b) and P4.

ii) If (30) holds, the function V 0 satisfies Plin.

Proof. i) When ( 28) holds (small c B ) then χ ≤ 0 and we have, for all 0 ≤ n ≤ N ,

∆ n V 0 (n, 0) = V 0 (n + 1, 0) -V 0 (n, 0) = c Q α + θ + Λ/N .
Then Picx and P1 a) are clearly satisfied, and since c B ≤ c Q α+θ+Λ/N then P1 b) is satisfied as well. We also have

V 0 (n + 1, 0) -V 0 (n, 1) = c Q α + θ + Λ/N (1 + χ) = c B which is P4.
ii) When ( 30) holds (large c B ) then χ ≥ 0 and the definition of V 0 (n, b) corresponds with ( 17) for all 0 ≤ n ≤ N and b ∈ {0, 1}.

Optimal policy for approximate models

We prove now that the optimal policy in approximate models is a threshold policy with a threshold equal to one. Theorem 4. Let Assumption 1 hold. i) If (28) holds, then there exists an optimal feedback policy γ * N such that γ * N (n, 0) = 1 for all 1 ≤ n ≤ N + 1.

ii) If (30) holds, then there exists an optimal feedback policy γ * N such that γ * N (n, 0) = 0 for all 1 ≤ n ≤ N .

Proof. i) We apply Theorem 3 with the sets V σ and D σ defined as:

V σ = {V ∈ V | V satisfies Picx, P1 a), P1 b) and P4} and D σ = {π ∈ F | π(n, 0) = 1, 0 ≤ n ≤ N + 1}.
The set V σ is not empty since it contains V 0 , defined in Section 6.1.4, by virtue of Lemma 12. The assumption 1) of Theorem 3 holds because all A x are finite ([22, Theorem 6.2.10]). That V ∈ V σ implies T (u) V ∈ V σ is guaranteed by Proposition 4. That V ∈ V σ implies the existence of some π ∈ D u with the desired property, is a consequence of Lemma 10. Finally, the closure of V σ under simple convergence is clear, since this set is defined by a finite number of linear constraints.

ii) We now apply Theorem 3 with the sets V σ and D σ defined as:

V σ = {V ∈ V | V satisfies Plin} and D σ = {π ∈ F | π(n, 0) = 0, 0 ≤ n ≤ N }.
The set V σ is clearly not empty. The assumption 1) of Theorem 3 holds as above. That V ∈ V σ implies T (u )V ∈ V σ is guaranteed by Proposition 5. That V ∈ V σ implies the existence of some π ∈ D u with the desired property, is a consequence of Lemma 11. Finally, the closure of V σ under simple convergence is clear.

Optimality in the base model

In this section, we proceed with the proof of Theorem 1. We shall apply Theorem 5.1 of [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF], included as Theorem 8 in Appendix C for the sake of self-containedness. For this, we need to check all parts of Assumption 5.

Proof of Theorem 1. In the context of these results, recall the notation A = N × F for the parameter set: the models X(a) = X(N, π) are parametrized by the truncation parameter N and the stationary deterministic policy π. Select a real number γ ∈ (0, θ), complying with Assumption 5h). 7For every a = (N, π) ∈ A, the induced Markov process X(a) has bounded transition rates so that the transition matrices are conservative. That the Markov chains are stable for all δ derives from the fact that the chain obtained with the "No Service" policy is always stable. Indeed: this chain is a birth-death process with population-dependent birth rates which vanish for populations larger than N . A stochastic comparison argument is then used for other policies. Assumption 5a) therefore holds.

The set A is discrete, because F itself is discrete, since action spaces are finite. Hence A is locally compact: Assumption 5b) holds.

According to their definitions in Section 2.2, the transition rates are either constant, or simple combinations of λ(n) and α(n), themselves continuous functions of n when defined in Assumption 1. Assumption 5c) therefore holds. Similarly with cost functions defined in Definition 1 where the function k(•) is defined (3): Assumption 5f ) also holds.

According to Lemma 15, for every γ the function

V = w ε with w ε (n, b) = e nε and ε ≤ log(1 + γ/Λ), is such that Assumption 5d) holds. Select then V = w ε and W = w ε with 0 < ε < ε ≤ log(1 + γ/Λ). Then W (n, b)/V (n, b
) is unbounded and this implies the existence of a sequence of sets K n as in Assumption 5e), choosing the value θ = γ.

Still according to the definition of the approximated models, we have, for x = (n, b), sup a c x (a) is a polynomial in n, and consequently, sup x,a c x (a)/V (x) < ∞. This checks Assumption 5g).

Finally, the "product property" of Assumption 5i) results from the fact that the approximation of Assumption 1 is "independent" from the stationary deterministic policy d. Indeed, consider a fixed N ∈ N and the family of models {X(N, π); π ∈ F }. Then F can be represented as F = s∈X A x with A x = N × A x , where A x is defined in Section 2.2. The sets A x are finite hence compact. Moreover, for some π ∈ F , consider the rate matrix Q(N, π) obtained by applying the approximation factor N and the control policy π. The product property holds if the row x of this matrix depends only on π(x). But this row is given by the rates defined in Section 2.2 with the functions α(.) and λ(.) specified in Assumption 1. These values clearly depend only on π(x).

All requirements of Assumption 5 are therefore satisfied.

Consider first the case where c Q > c B (α + θ). Then there exists a N 0 ∈ N, N 0 ≥ 1, such that, for all N ≥ N 0 , Condition (28) holds. 8 According to Theorem 4 i), for every such N there is an optimal policy π * N where π * N (n, 0) = 1 for 0 ≤ n ≤ N . Whatever the actual values of π * N (n, 0) for n > N ≥ N 0 , or those of policies π * N for N < N 0 , this sequence of policies has the accumulation point π AS where π AS (n, 0) = 1 for all n ∈ N, is the AS policy introduced in Definition 3. In other words, AS is optimal and Theorem 1 b) is proved.

Assume now that c Q ≤ c B (α + θ). For all N ∈ N, Condition (30) holds. Starting with Theorem 4 ii), the previous reasoning allows to conclude that π N S is optimal. Theorem 1 a) is proved, as well as the statement in Theorem 1 c) that π N S is optimal when c Q = c B (α + θ).

There remains to be proved that π AS is also optimal when c Q = c B (α + θ). To that end, consider the family of MDPs of the Base Model, parametrized by c Q . More precisely, and in order to match the framework of Theorem 8, consider the family of models parametrized by N with c

(N ) Q = c B (α + θ)(1 -1/N )
, all other parameters being unchanged. The conditions of Assumption 5 are satisfied: either they were already checked with the Base Model for features involving only transition rates, or they are straightforward to check for features involving costs. It is then possible to apply again Theorem 8 to conclude that since π AS is optimal for all N ∈ N \ {0}, it is also optimal for N = ∞, that is, when

c Q = c B (α + θ).
We conclude this section with a complement on optimal value functions, also an application of Theorem 8.

Theorem 5. The value function V * of the optimization problem in the Base Model:

i) is increasing, convex, is such that ∆ n V * (0, 0) ≥ c B and ∆ n V * (n, 0) ≤ c Q /(α + θ) for all n ≥ 0; ii) when c Q ≤ c B (α + θ), is given by, for all (n, b) ∈ X : V * (n, b) = V N S (n, b) = c Q α + θ n + Λ θ . (33)
Proof. When c Q ≤ c B (α + θ), Theorem 1 says that γ N S is optimal, so that V * = V N S . That the function defined in (33) is indeed V N S is checked by checking that it is a fixed point of the "no serve" equation, that is (see Proposition 1 and Equation ( 6)): for all n ≥ 0,

V (n, 0) = 1 λ(n) + α(n) + θ [nc Q + λ(n)V (n + 1, 0) + α(n)V (n -1, 0)] .
In addition, under γ N S , V * (n, 0) = V * (n, 1). This proves claim ii).

The function V N S has all properties listed in i)

when c Q ≤ c B (α + θ) since ∆ n V N S (n, 0) = c Q /(α + θ) ≥ c B . When c Q > c B (α + θ)
, we use the approximated models. Theorem 8 i) applies and V * is the limit of a sequence of approximated value functions V N . Each of these has properties Picx, P1 a), P1 b) and P4 according to the proof of Theorem 4. In the limit N → ∞, V * has therefore the properties stated in claim i). 9

Methodological comments

In this section we group a set of observations on the features of the problem solved in the paper. Each observation below details the technical points which make a traditional proof method ineffective.

Intractability of structural properties propagation framework in the Base Model

The classic approach in order to show that the optimal policies are threshold policies uses the framework of propagation of structural properties by the dynamic programming operator, recalled in Section 6.1.1. It needs to find a set of "structured" value functions, V σ , which is invariant under this operator. The usual sets considered involve monotony an/or some form of convexity.

Example 1 exhibits cases in which simple properties like increasingness, convexity or concavity are not conserved during the value iteration procedure, when it uses the "natural" dynamic programming operator defined on the Base Model of Definition 2. This suggests that the structured policy propagation framework is likely to fail for this operator. As shown in Section 5, the operator resulting from smoothing and truncation does propagate convexity. We define V 0 the initial value function. We compute V +1 with respect to V using the Bellman operator defined from equations (5)-( 8) i.e.:

V +1 (0, 0) = 1 Λ + θ [k(0) + ΛV (1, 0)], V +1 (n, 0) = min c B + 1 Λ + (n -1)α + µ + θ k(n -1) + ΛV (n, 1) + (n -1)αV (n -2, 1) + µV (n -1, 0) , 1 Λ + nα + θ [k(n) + ΛV (n + 1, 0) + nαV (n -1, 0)]
for n ≥ 1 and

V +1 (n, 1) = 1 Λ + nα + µ + θ [k(n) + ΛV (n + 1, 1) + nαV (n -1, 1) + µV (n, 0)] ,
for n ≥ 0. Figure 1 represents the functions V for different values of as well as their numerical limit, obtained with Value Iteration until no evolution is observed. This is done for two initial values. For the curves on the left, we choose V 0 (n, 0) = V 0 (n, 1) = 0 for all n ≥ 0. It is observed that the initial function is linear, that the first iterate is concave, that the following iterates are neither concave nor convex, while the limit is convex (Theorem 5). For the curves on the right-hand side, we choose the value function used in the proof of the paper (defined by Equations (31) and (32)). The initial value is increasing convex, then the first iterate is convex but not increasing, that the following iterates are neither increasing nor convex while the limit is increasing convex.

Intractability of sample Path approaches

Due to the simple form of the policy it could be thought that a simpler method such as sample path should be sufficient. Example 2 shows that proving the result of Theorem 1 with the use of sample path arguments is not direct. The counterexample is constructed in the non uniformized case but a similar example can be constructed for the smoothed and uniformized case in the same way.

Example 2 (Sample Path comparison fails). We assume a case in which at the start there is only one single customer in the queue and no service in progress: x 0 = (1, 0). We also assume that the impatience of the customer is such that its departure time is D 0 if it is not served with furthermore D 0 ≤ A 1 where A 1 is the epoch of the next arrival.

If we choose to serve the customer at time 0 then it costs J AS = c B + J A 1 where J A 1 is the cost incurred by the system from time A 1 . Otherwise, if we do not serve the customer then it costs

J N S = c H D 0 0 e -θt dt + c L e -θD 0 + J A 1 .
We have

J N S -J A 1 = c H 1 -e -θD 0 θ + c L e -θD 0 = (1 -e -θD 0 ) c H θ + e -θD 0 c L .
Observe that this is a convex combination, and as D 0 ranges from 0 to ∞, this value can be any number in the interval I := [c L , c H /θ) or I := (c H /θ, c L ], depending on the relative positions of the extremities.

Let us assume that we have parameter values such that AS is optimal. We will now exhibit some trajectories for which it is not optimal to serve the initial customer although always serving is optimal. The condition for AS to be optimal is (Theorem 1):

c B ≤ c B := c H + αc L α + θ = c H θ θ α + θ + c L α α + θ .
This is also a convex combination, so that c B lies in the interval I.

If J N S -J A 1 ≤ J AS -J A 1 = c B
then it is optimal not to serve the customer. Assume in addition that c B > min{c L , c H /θ}. Then if c B ≤ c B ∈ I, c B necessarily belongs to the interior of I. We have argued that that there exists a D 0 such that J N S -J A 1 is anywhere we want in I, in particular smaller than c B . Picking such a D 0 , together with A 1 > D 0 , we have the desired trajectory.

The argument also suggests that the sample path comparison does work when c B ≤ min{c L , c H /θ} since not serving the customer will incur a cost belonging to the interval I.

Submodularity study

This section is dedicated to the study of the submodularity property which is widely used in the proofs of optimality for threshold policies. The study is done differently for the base model and for the smoothed model since the properties of the operators involved are different.

The submodularity referred to here is the one involving the state x = (n, b) and the decision q ∈ {0, 1}. The operator T q on V is defined as the action of decision q on a function V . The analysis of [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF]Section 4.7] relates the super-or submodularity of (q, x) → T q V (x) to the optimality of monotone policies, which are threshold policies in our case. In particular, Lemma 4.7.6 from [START_REF] Puterman | Markov Decision Processes Discrete Stochastic Dynamic Programming[END_REF] implies that if [START_REF] Vakilinia | Analysis and optimization of big-data stream processing[END_REF]) is monotonous in n, then a threshold policy is optimal.

∆ q T V (n, b) = T 1 V (n, b) -T 0 V (n, b) (see also

Details on submodularity in the Base Model

In the Base Model case, Example 3 strongly suggests that the usual structural propagation of submodularity is not verified as soon as impatience is present.

Example 3 (Lack of submodularity, Base Model). We study the difference between the two terms of the min in the Bellman Equation. We hence define, for n ≥ 1, T q V (n, b) by T q V (n, b) = qA + (1 -q)B where A is given by Equation (5) :

A = c B + 1 λ(n-1)+ α(n-1)+µ+θ k(n-1)+λ(n-1)V (n, 1)+α(n-1)V (n-2, 1)+µV (n-1, 0) ,
and B is given by Equation (6):

B = 1 λ(n) + α(n) + θ [k(n) + λ(n)V (n + 1, 0) + α(n)V (n -1, 0)] .
On Figure 2, we can observe the plotting of the difference T 1 V (n, b) -T 0 V (n, b) for two sets of parameters, where V is the function obtained by Value Iteration, see Example 1. It is observed that these ones are decreasing, then increasing from n ≥ 1. This means that the function T q V (n, b) is neither sub-nor supermodular.

Parameters have been chosen such that Λ = 0.5, and θ = 1.5 and such that the costs are c B = 1.0, c L = 2.0 and c H = 2.0. For the left plot we have µ = 2 and α = 1.5 while for the right plot we have µ = 1.5 and α = 2. Computations are done in a finite model of size 100. Example 3 indicates that there exists some cases for which the submodularity does not hold when we use the base model operator: we investigate this issue in the case of smoothed and truncated model. We show that first there exist cases where the submodularity does not hold with the base model operator while it holds for the operator of the approximated model. Then, we show for approximated models that, according to the relative values of the loss rate compared to the service rate, the dynamics of the queueing system is different. Hence, according to the dynamics, the operator can be either submodular or supermodular. This is illustrated on Figure 3.

Example 4. On Figure 3, we plot the function ∆ q T (u) V (n) (on the y-axis) with respect to n (on the x-axis) for different values of α. We choose the parameters such that Inequality (28) is satisfied for all the cases plotted. We fix Λ = 0.5, µ = 2.0, θ = 1. In line with Inequality (28) and Lemma 10, it can be seen that all the functions ∆ q are negative. Furthermore, it can be noticed that according to the sign of α -µ the monotonicity is different. When α -µ ≥ 0, the function ∆ q T (u) V (n) is decreasing then increasing. When α -µ < -Λ/N , ∆ q T (u) V (n) is decreasing, which is equivalent to submodularity of T q V as seen above. When -Λ/N ≤ α -µ < 0, monotonicity may hold or does not hold, as can be seen on Figure 3 b).

Example 4 relativizes the claims made, for example, in [START_REF] Down | Dynamic control of a single-server system with abandonments[END_REF] and [START_REF] Koole | Monotonicity in Markov reward and decision chains: Theory and applications[END_REF] that impatience breaks structural properties. Actually, only submodularity was broken, and there nevertheless exist some structural properties as seen in the previous parts of this work.

At last, it can be noticed that the left plot of Figure 2 corresponds with the third curve of Figure 3 since they have the same parameters µ = 2 and α = 1.5 in input. However, the two curves are obviously different. This illustrates again the structural difference of both dynamic programming operators, which are here applied to the same optimal value function which is their common fixed point.

Study of the change of structural properties

This change in the dynamics according to the sign of α -µ is an intrinsic characteristic of the approximated model as we will show now. Lemma 13. Let Assumption 1 and (28) hold. Let V be the optimal value function of the smoothed and uniformized problem for some value of N . The function ∆ q T (u) V (n) is: i) decreasing between n = 0 and n = 1;

ii) increasing for 1 ≤ n ≤ N when α -µ ≥ 0.

Moreover,

iii) for every real number κ > 0, there exists some N 0 such that for every N ≥ N 0 , if a) α -µ < -Λ/N , and b)

∆ n V (n -1, 0) -∆ n V (n -2, 0) ≥ κ for 2 ≤ n ≤ N , then the function ∆ q T (u) V (n) is decreasing for 1 ≤ n ≤ N .
The limit of the right-hand side when N → ∞ is κ(α -µ) < 0. Therefore, there exists N 0 such that ∀N ≥ N 0 , this right-hand side is strictly negative. Summing up, for every such N , provided assumptions a) and b) hold true,

∆ q T (u) V (n) -∆ q T (u) V (n -1) < 0
for all 2 ≤ n ≤ N , which proves iii).

From a system point of view, the presence of two dynamics can be interpreted but not explained. We first recall that since Assumption (28) holds then it is always more interesting to serve a customer than not to serve it. However, from the curves (as well as monotonicity) several trends can be observed. When the loss rate α is larger than the departure rate µ, then the more customers there are in the queue the less serving them is interesting. Indeed, the absolute value of the difference between T (u)

AS and T (u)

N S decreases. Furthermore, the sign of the difference does not change which means that the optimal decision does not change. Instead, when the loss rate is smaller than the service rate then the more customers there are in the queue the more the service is interesting.

This change of structural properties furthermore illustrates observations that can be made from the literature. In [START_REF] Larrañaga | Asymptotically optimal index policies for an abandonment queue with convex holding cost[END_REF], the authors analyze a slightly different model that also includes impatience in service. It is proved that submodularity holds under the condition that the total departure rate of the server (service rate and impatience in service rate) is larger than the loss rate. Since our rate of impatience in service is null then we have a similar condition. At last, similar changes of dynamics can be found in [START_REF] Armony | Sensitivity of optimal capacity to customer impatience in an unobservable M/M/S queue (why you shouldn't shout at the DMV)[END_REF] which aims at computing the optimal service rate in a queueing model with impatience. Indeed, their cost function is either convex or concave according to the relative values of the reneging rate and the service rate.

Limits of truncated non-smoothed models

We analyze here the boundary effects of truncation and smoothing on the structural properties of the value function. Example 5 seeks to illustrate how truncation breaks structural properties at the boundary while in Example 6 one examines all the possible combinations between truncation smoothing and shows that only the truncated smoothed version of this work preserves structural properties.

For the clarity of this part, wee call "bounded by S" a model in which the state space is finite and in which the maximum number of customers is S. In x = (S, b) we jump toward the same state with a rate λ.

We call "truncated by N " a model in which the rate of the exponential distributions of arrivals or/and departure depends on the state and is null for all x = (n, b) with n ≥ N . The state space can be either finite or infinite, but when the state space is bounded by S, S should be larger than N .

We call "smoothed in N " a model truncated by N in which the rate of the exponential distributions of arrivals or/and departure depends on the state and decreases with respect to the number of customers such that it is equal to 0 in x = (N, b).

We call uniformized a model in which the transition rate is the same whatever the state is.

Example 5 (Effect of the truncation). We consider first the Base model of Definition 2, with parameters α(n) = nα and λ(n) = Λ for all n ≥ 0. The value function of the "no serve" policy in this case is given by (33) in Theorem 5.

Consider now the truncated model in N in which λ(n) = Λ when 0 ≤ n ≤ N and λ(n) = 0 otherwise. In a such model, the fixed point equation of the "no serve" policy becomes:

V (n, 0) =          1 Λ + nα + θ [nc Q + ΛV (n + 1, 0) + nαV (n -1, 0)] for 0 ≤ n ≤ N 1 nα + θ [nc Q + nαV (n -1, 0)] for n > N .
Let V (n, 0) be a function solution of the fixed point equation defined by the two equations just above. Then, we have that V (n, 0) = V (n, 0) for n ≤ N and, when n > N , then it satisfies the recurrence

V (n, 0) = V (n -1, 0) 1 + θ nα -1 + c Q α + θ n -1
.

When n tends to infinity then the function V (n, 0) approaches the linear line of slope c Q /α. This slope is different than c Q /(α + θ) which is the slope of V (n, 0). Moreover, this asymptotic slope c Q /α is steeper than the slope c Q /(α + θ) of V (n, 0) when n ≤ N . On the other hand, at n = N + 1 we have

V (N + 1, 0) -V (N, 0) = (N + 1)c Q -θ V (N, 0) (N + 1)α + θ = c Q α + θ 1 (N + 1)α + θ ((N + 1)(α + θ) -(N θ + Λ)) = c Q α + θ (N + 1)α + θ -Λ (N + 1)α + θ < c Q α + θ = V (N, 0) -V (N -1, 0) .
This shows that V (n, 0) is not convex in N while V (n, 0) is. Therefore we show that the truncation modifies the behavior of the fixed point solution of a Bellman operator and in particular that this may break convexity properties. Example 6. We consider the parameters Λ = 0.5, α = 1.0, µ = 5.0 and θ = 1.5. We also consider c B = 1.0, c L = 2 and c H = 2 (yielding c Q = 4). We used a bounded model since only in bounded models numerical computations can be done. The value of S is chosen to be equal to 75. Our experiments with larger value of S, namely S = 750, S = 7500, S = 10000 produced variations in the value functions smaller than 10 -7 at any state x = (n, 0) with n ≤ N . These variations are sufficiently small for our claim and it seems unnecessary to try to get smaller values of gaps.

We combine truncation, smoothing to build different models. Thus we study the following models:

The extension of our model to more complex (non-linear) holding costs appears to be possible by adapting the tools presented here. The extension to batch sizes larger than 1 as in [START_REF] Aalto | Optimal control of batch service queues with finite service capacity and linear holding costs[END_REF] is not straightforward, since the value function is then not convex in x.

At last, this work can be seen as a step toward an unified treatment of the propagation result for structural properties in case of unbounded rates as suggested in [START_REF] Blok | Markov Decision Processes in Practice, chapter Structures of Optimal Policies in MDPs with Unbounded Jumps: The State of Our Art[END_REF], or for the special cases of models with impatience.

Proof. By assumption, the arrival rate λ(•) is bounded above by some Λ. Also by assumption and from Definition 1, the running cost c(x, a), x = (n, b), is bounded by a polynomial in n. Indeed, c(x, a) ≤ (q(x, a)+θ)c B +k(n-a) ≤ (Λ+max(α(n), α(n-1))+µ+θ)c B +max(k(n), k(n-1)).

Since α(.) and k(.) are bounded by polynomials, c(x, a) ≤ K(n) for some polynomial K, assumed to be increasing without loss of generality.

Consider the queue with constant arrival rate Λ, no admission in service and no impatience (in other words, with α(n) = 0 for all n), and running cost c U (x, a) = K(n). In this queue (labeled with "U "), no departure ever occurs and x U (t) = d x U (0) + Poisson(Λt). By a coupling argument (including the coupling of service times if a customer is in service at t = 0), it is clear that x(t) ≤ st x U (t) and since K(•) is increasing, it follows that V N S ≤ V U . It is sufficient to prove the finiteness of V U . If 0 = T 0 < T 1 < . . . denotes a Poisson process with rate Λ, we have:

V U (x) = E ∞ 0 e -θt K(x u (t)) dt = E ∞ =0 T +1 T e -θt K(x(0) + ) dt = E ∞ =0 K(x(0) + )e -θT 1 -e -θ(T +1 -T ) θ = ∞ =0 K(x(0) + ) Λ Λ + θ 1 Λ + θ .
This quantity is indeed finite for all θ > 0 since K(•) is a polynomial.

We now turn to Assumption 2. The following Lemma is useful for checking this assumption and other ones. In the statement, Q(a) denotes the rate matrix made of rates q(y|x, a), (x, y) ∈ X × X . Lemma 15. For any γ > 0, there exists some ε > 0 such that the function w ε : X → R, defined as w ε (n, b) = e εn , satisfies: Q(a)w ε ≤ γw ε for all a.

Proof. The fact that γ satisfies Q(a)w ε ≤ γw ε is granted if We therefore proceed with the computation of this supremum. Let us start with the case x = (n, 1), in which case A x = {0}. We have (see Section 2. Summing up all three cases, we find that for all a and all x ∈ X ,

Given the values of q((n, b), a) in Section 2.2 and the polynomial growth of α(•), this property also holds. Therefore, Assumption 2 holds, and Theorem 6 applies. This proves Proposition 1.

B Proof of Proposition 2

The proof relies on Theorem 4.2 of [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]. We first state the theorem and the assumptions it relies on. We then apply it to our situation.

Inria

B.1 Theorem and assumptions

We use Theorem 4.2 of [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]. It applies to a collection of parametrized Markov Reward processes {X(a); a ∈ A} on some state space S, whose infinitesimal generator is denoted with Q(a), whose running cost function is denoted with c(x, a) and whose value function is the expected total discounted cost with discount factor α. 10 It holds under the conditions summarized in Assumption 4 below.11 h) (Assumption 4.1 (iii) from [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) the discount factor α is such that α > γ;

i) (Assumption 4.2 from [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) There exist compact metric sets A x , x ∈ S, such that A = x A x and is equipped with the product topology, and for any a, a ∈ A, x ∈ S, such that a x = a x , it holds that (Q(a)) x = (Q(a )) x and c(x, a) = c(x, a ).

If Assumption 4 c) holds, then it is possible to define ∞ (S, V ), the space of V -bounded functions on S. Theorem 7 ([8], Theorem 4.2). Suppose that Assumption 4 holds. Suppose moreover than sup a q(x, a) < ∞ for all x ∈ S. Then the equation αf (i) = inf a∈A(i) c(i, a) + j∈X q(j|i, a)f (j) has a unique solution v α ∈ ∞ (S, V ) and the infimum is a minimum. Every policy a * that achieves the minimum is optimal.

Theorem 2 .

 2 Consider the formal control model of Definition 1 with functions λ(•), α(•) and k(•) satisfying Assumption 1.

Lemma 6 (

 6 Propagation of Picx for T (u) AS ). Let Assumption 1 and (28) hold. Let V ∈ V be a function which satisfies properties Picx and P4. Then T (u) AS V satisfies Picx. Proof. Since V satisfies P4, we can apply (21) and (22) of Lemma 3 for all n ≤ N . Proving that T (u) AS V satisfies Picx amounts to proving two properties on n → ∆ n T (u)

  AS V , hence the statement. Lemma 7 (Propagation of P1 b) for T (u) AS ). Let Assumption 1 and (28) hold. Let V ∈ V be a function which satisfies property Picx, P1 b) and P4. Then T (u) AS V also satisfies P1 b).

Lemma 8 (

 8 Propagation of P1 a) for T (u) AS ). Let Assumption 1 and (28) hold. Let V ∈ V be a function which satisfies properties P1 a) and P4. Then T (u) AS V also satisfies P1 a).

  a linear part for n ≤ N . Lemma 9 (Fixed point property for T (u) N S ). Let Assumption 1 hold, and let V ∈ V be a function that satisfies Plin. Then T (u) N S V also satisfies Plin. In other terms, T (u)

2

 2 Study of the sign of ∆ q T(u)

  AS V has the four properties Picx, P1 a), P1 b) and P4. All properties involve values of the "V " function at (n, b) with 0 ≤ n ≤ N + 1. If they hold for T (u)

Example 1 (

 1 Non convexity of iterations of Value Iteration). Consider the Base Model with the following parameters: Λ = 0.5, µ = 5, α = 1 and θ = 0.1; the costs are c B = 1.0, c L = 2.0 and c H = 2.0. Computations are done in a finite model of size S = 100.

Figure 1 :

 1 Figure 1: Plot of the iterations of the value function

µ -α ≤ 0 Figure 2 : Non submodularity 7 . 3 . 2

 02732 Figure 2: Non submodularity

5 Figure 3 :

 53 Figure 3: Two dynamics when AS is optimal

  a)w ε )(n, b) w ε (n, b) < γ .

  2):(Q(a)w ε )(n, 1) = λ(n)w ε (n + 1, 1) + α(n)w ε (n -1, 1) + µw ε (n, 0)-(λ(n) + α(n) + µ)w ε (n, 1) = e εn λ(n)(e ε -1) + α(n)(e -ε -1) , then (Q(a)w ε )(n, 1) w ε (n, 1) = λ(n)(e ε -1) + α(n)(e -ε -1) ≤ Λ(e ε -1)since λ(n) is bounded, by assumption. Next, consider a state (n, 0) such that a = 0, that is, no service is started. Then,(Q(a)w ε )(n, 0) = λ(n)w ε (n + 1, 0) + α(n)w ε (n -1, 0) -(λ(n) + α(n))w ε (n, 0) = e εn λ(n)(e ε -1) + α(n)(e -ε -1) , then (Q(a)w ε )(n, 0) w ε (n, 0) = λ(n)(e ε -1) + α(n)(e -ε -1) ≤ Λ(e ε -1) .Finally, if a = 1 (and n ≥ 1), then:(Q(a)w ε )(n, 0) = λ(n -1)w ε (n, 1) + α(n -1)w ε (n -2, 1) + µw ε (n -1, 0) -(λ(n -1) + α(n -1) + µ)w ε (n, 0) = e εn α(n -1)(e -2ε -1) + µ(e -ε -1) ,and(Q(a)w ε )(n, 0) w ε (n, 0) = α(n -1)(e -2ε -1) + µ(e -ε -1) ≤ 0.

  a)w ε )(x) w ε (x)≤ Λ(e ε -1)and clearly this can be made smaller than any γ > 0 by a proper choice of ε, namely, ε ≤ log(1+γ/Λ). This proves the statement. As a consequence of Lemma 15, Assumption 2 (a) holds with c 0 = γ and b 0 = 0, where γ can be any non-negative number. The existence of L 0 as in Assumption 2 (b) is granted if sup (n,b) sup a q((n, b), a) w(n, b) < ∞.

Assumption 4 .

 4 a) (Assumption 2.1 from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) For each a ∈ A, X(a) is a minimal, standard, stable Markov process with right-continuous sample paths and with conservative q-matrix Q(a); b) (Assumption 3.1 from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) The set A is a locally compact topological space, i.e. every point in A has a compact neighborhood; c) (Assumption 3.2 (i) from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) the functions a → q xy (a) are continuous for every x, y in S; d) (Assumption 3.2 (ii) from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) there exists a function V and a real number γ such that for all a ∈ A, Q(a)V ≤ γV ; e) (Assumption 3.2 (iii) from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) there exists a function W and a real number θ with, for all a ∈ A, Q(a)W ≤ θW and an increasing sequence of finite sets {K n } with lim n K n = S andlim n→∞ inf{W (x)/V (x); x ∈ K n } = + ∞.f) (Assumption 4.1 (i) from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) the functions a → c(x, a) are continuous for every x in S; g) (Assumption 4.1 (ii) from[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]) there is a finite real constant c V such that sup x,a |c(x, a)|/V (x) ≤ c V (in other words: sup x,a |c(x, a)|/V (x) < ∞);

1 2 . 2 6 3 3 . 1 3 . 3 10 4 12 5

 122631331012 The controlled queueing model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 The formal model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Optimization via stochastic dynamic programming 8 Policies and optimization criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Bellman Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Optimal policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Smoothed and uniformized models 10 4.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Definition of operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Bellman equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Structural properties of smoothed and uniformized models 13 5.1 Definition of properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 Implications and identities for properties . . . . . . . . . . . . . . . . . . . . . . . . 14 5.3 Identities for difference operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.4 Invariant properties for operator T (u) AS . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.5 Invariant property for operator T (u) N S . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6 Optimality results 21 6.1 Optimality results in the approximated models . . . . . . . . . . . . . . . . . . . . . 21 6.1.1 Overview of the propagation framework . . . . . . . . . . . . . . . . . . . . 22 6.1.2 Study of the sign of ∆ q T (u) . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.1.3 Invariant properties for operator T (u) . . . . . . . . . . . . . . . . . . . . . 24 6.1.4 Initial Value function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.1.5 Optimal policy for approximate models . . . . . . . . . . . . . . . . . . . . 25 6.2 Optimality in the base model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7 Methodological comments 27 7.1 Intractability of structural properties propagation framework in the Base Model . . . 27 7.2 Intractability of sample Path approaches . . . . . . . . . . . . . . . . . . . . . . . . 29 7.3 Submodularity study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.3.1 Details on submodularity in the Base Model . . . . . . . . . . . . . . . . . . 30 7.3.2 Details on submodularity in approximated models . . . . . . . . . . . . . . 30 7.3.3 Study of the change of structural properties . . . . . . . . . . . . . . . . . . 31 7.4 Limits of truncated non-smoothed models . . . . . . . . . . . . . . . . . . . . . . . 33 8 Conclusions 35 A Proof of Proposition 1 38 A.1 Theorem and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 A.2 Application to Proposition 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B Proof of Proposition 2 40 B.1 Theorem and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 B.2 Application to Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 C Convergence of models

RR n°9199

Equivalently, the probability of a departure in the next interval of length δt is α(n)δt + o(δt).

In this model, actions are not taken just at the time of transitions, but continuously over time.

Some authors advocate the use of Dynkin's formula here, see e.g.[START_REF] Larrañaga | Efficient content delivery in the presence of impatient jobs[END_REF]. Inria

This is the notation from[START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]; this set is denoted as D in[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF].RR n°9199

The value of V (n -2, 0) in (13) is not defined when n = 1 but is then multiplied by α(0) = 0 in the formulas.RR n°9199

In the case χ = 0, the term max(0, χ)/χ is to be interpreted as 0. Inria

Observe that in the statement Assumption 5, the discount factor is called α.

Namely: N0 = cBΛ/(cQ -cB(α + θ)) .Inria

This limiting argument may be used also in the case cQ ≤ cB(α + θ) with property Plin. RR n°9199

Inria

This parameter a is not to be confused with the individual actions a of the formal model in Section 2.2. The matrix Q(a) is not to be confused with that of Appendix A.

Note that Theorem 4.2 in[START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF] is stated without the explicit Assumption 3.1 op. cit. However, the proof does require Theorem 4.1, which holds under this assumption.RR n°9199

InriaRESEARCH CENTRE SOPHIA ANTIPOLIS -MÉDITERRANÉE 2004 route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Proof. Although this has not been stated explicitly yet, the fact that V satisfies Picx, P1 a), P1 b) and P4 is clear from the proof of Theorem 4, see also the proof of Theorem 5. i) Since ∆ q T (u) V (n) = 0, then i) is a direct consequence of Lemma 10. ii) Since V satisfies P4, we can use Equation ( 27) from the proof of Lemma 4, namely, for 1 ≤ n ≤ N :

When α -µ ≥ 0, then ∆ q T (u) V (n) is the sum of a constant and two functions that are increasing for 1 ≤ n ≤ N . The result is then increasing in the same range, which proves ii). iii) When α -µ < 0 then ∆ q T (u) V (n) is the sum of an increasing function and a decreasing function and the result may be non-monotone. However, the disturbance that results from the smoothing, i.e. the term with Λ/N as factor, may be made small in front of the decreasing term.

To that end, we use the above formula to get, for 2 ≤ n ≤ N ,

We intend to bound the right-hand side by some strictly negative number, which will imply the decreasingness of ∆ q T (u) V . Adding and subtracting

), this becomes:

For (34), we use the assumptions

For (35), we have: on the one hand with P1 a):

and on the other hand, with Picx and P1 b):

In total,

and therefore: For each of these models, we numerically compute the value function and we observe some of their structural properties, namely, monotonicity and convexity, as defined in Section 5.1. The results are compiled in Table 1, in which we also indicate if the value iteration method finds the optimal policy.

Bounded Uniformized Arrival

Monotonicity Convexity Concavity Optimal policy Model 1

Yes

Table 1: Studies of structural Properties for different models

The results presented here show that except for Model 8 (which is the one studied in this work) all the other ones experience border effects for the structural properties. Indeed, in bounded models, border effects are due to the change in the operator in state S: the term in λ(S)V (S +1, 0) is replaced by a term in λ(S)V (S, 0). In truncated models, border effects are due to the change in the operator in state N : the term in λ(N )V (N + 1, 0) disappears. Smoothing allows to reduce the impact of this change in the operator and allows to keep structural properties.

Conclusions

We present here a detailed treatment of a stochastic dynamic control problem with unbounded rates, coming from a queuing model with impatience. It allows us to prove the optimality of a policy that is either Always Serve customers or Never Serve customers. We also give a closed form formula of the value function when the Never Serve policy is optimal.

The results presented here are consistent with these ones of Aalto [START_REF] Aalto | Optimal control of batch service queues with finite service capacity and linear holding costs[END_REF], concerning the problem of admission control in a batch service queue. The model of [START_REF] Aalto | Optimal control of batch service queues with finite service capacity and linear holding costs[END_REF] further allows holding costs in service. When we set these costs to 0, the batch size to 1, and set in our model the impatience rate to 0, our results are the same. Indeed, adopting our notations and setting the batch size to 1, Aalto states that if c H /θ ≤ c B then the No Service policy is optimal and instead, when c H /θ ≥ c B , a queue length threshold policy is optimal. If we replace α by 0 in Theorem 1, we obtain the same condition. Note however that our proof does not cover this limiting case.

A Proof of Proposition 1

The proof is based on Theorem 4.10, p. 60 of Guo and Hernández-Lerma [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]. We first state this theorem and the assumptions it relies on. We next apply it to our situation.

A.1 Theorem and assumptions

According to Remark 4.9, p. 63 op. cit., Theorem 4.10 applies when Assumption 4.12 (p. 64) is satisfied. A second condition to be satisfied is Assumption 2.2 (p. 13).

In the context of the theorem, the state space is denoted with S, the action space available in state i is A i , the cost function is c(i, a) and the transition rates are q(j|i, a). The cost function must be nonnegative, which is the case in our application, see Definition 1. The conditions state as follows.

Assumption 2 (Assumption 2.2. from [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]). There exists a function w : S → R, w ≥ 1, and constants c 0 = 0, b 0 ≥ 0 and L 0 ≥ 0 such that: (a) j q(j|i, a)w(j) ≤ c 0 w(i) + b 0 for all (i, a);

(b) sup a q(i, a) ≤ L 0 w(i) for all i.

Assumption 3 (Assumption 4.12. from [START_REF] Guo | Continuous-Time Markov Decision Processes -Theory and Applications[END_REF]). (a) A i is compact for each i ∈ S.

(b) For all i, j ∈ S, the functions c(i, a) and q(j|i, a) are continuous on A i .

(c) There exists f ∈ F such that V f < ∞, and j q(j|i, a)V f (j) is continuous on A i for all i.

Here, as in Section 3, F is the class of state-feedback stationary controls and V f (j) is the expected cost of control f from initial state j.

Then, the result is:

Theorem 6 ([13], Theorem 4.10). Let Assumptions 2 and 3 hold. Then for all x ∈ S,

and any f ∈ F such that f (x) belongs to the "arg min" in (36) is optimal.

A.2 Application to Proposition 1

We claim that under the assumptions of Proposition 1, Assumptions 2 and 3 are satisfied by the formal model.

Observe first that, thanks to the finiteness of the sets A x , all compactness and continuity requirements of Assumption 3 are indeed satisfied. We just need to check statement (c), that is, the existence of a Markov policy with a finite cost. This is brought by the following Lemma. Recall the definition of the "no service" policy π N S in Definition 3. Lemma 14. Under the assumptions of Proposition 1, the policy π N S yields a finite value V N S .

B.2 Application to Proposition 2

We now check that all conditions of Assumption 4 are satisfied for the family of models defined in Definition 1, parametrized by the Markov (feedback) policy π ∈ F . We therefore set A = F in the application of Theorem 7. This is a discrete set, hence locally compact. Requirement b) is then satisfied. All Markov processes we consider have a finite number of transitions out of each state, with finite rates. Condition a) is therefore satisfied.

As observed earlier, the action space A does satisfy condition i) with A x = {0, 1} or {0}. These sets are discrete and finite so that all compactness and continuity requirements c) and f ) are satisfied.

The existence of a function V as in d), with a constant γ < α as in h), is a consequence of Lemma 15: for every γ, we can chose some ε > 0 and V (n, b) = e εn . The existence of a function W as in e) also derives from this lemma. It suffices to take W (n, b) = e ε n for some ε > ε, and the sets K n can simply be chosen as

With this choice for the function V , the boundedness of c(x, a)/V (x) is a consequence of the polynomial growth assumed on k(•), since V (•) has an exponential growth. Requirement g) is therefore satisfied.

All requirements of Assumption 4 are therefore checked. There remains to check that sup a q(x, a) < ∞ for all x ∈ S. This is so because A x is a finite set for all x.

C Convergence of models

We use Theorem 5.1 from [START_REF] Blok | Countable state Markov decision processes with unbounded jump rates and discounted cost: Optimality equation and approximations[END_REF]. It applies to a collection of parametrized Markov processes {X(N, δ); (N, δ) ∈ N × F }, on some discrete, denumerable state space S, where F is the set of admissible stationary deterministic policies (i.e. feedback policies, see Section 3.1) and N = N \ {0} ∪ {∞}. (i) lim N →∞ v α N = v α ∞ ;

(ii) any limit point of (δ * N ) N ∈N is optimal for X(∞, δ).

In the application of this result, observe that the set N is compact when equipped with the metric:

Therefore, if F is locally compact, then A = N × F is locally compact also, which validates Assumption 5b).