Ariel Waserhole

Jean-Philippe Gayon

Vincent Jost

Linear programming formulations for queueing control problems with action decomposability

Keywords: Continuous-time Markov decision process, Queueing control, Event-based dynamic programming, Linear programming

We consider a special class of continuous-time Markov decision processes (CTMDP) that are action decomposable. An action-Decomposed CTMDP (D-CTMPD) typically models queueing control problems with several types of events. A sub-action and cost is associated to each type of event. The action space is then the Cartesian product of sub-action spaces. We first propose a new and natural Quadratic Programming (QP) formulation for CTMDPs and relate it to more classic Dynamic Programming (DP) and Linear Programming (LP) formulations. Then we focus on D-CTMDPs and introduce the class of decomposed randomized policies that will be shown to be dominant in the class of deterministic policies by a polyhedral argument. With this new class of policies, we are able formulate decomposed QP and LP with a number of variables linear in the number of types of events whereas in its classic version the number of variables grows exponentially. We then show how the decomposed LP formulation can solve a wider class of CTMDP that are quasi decomposable. Indeed it is possible to forbid any combination of subactions by adding (possibly many) constraints in the decomposed LP. We prove that, given a set of linear constraints added to the LP, determining whether there exists a deterministic policy solution is NP-complete. We also exhibit simple constraints that allow to forbid some specific combinations of sub-actions. Finally, a numerical study compares computation times of decomposed and nondecomposed formulations for both LP and DP algorithms.

Introduction

Different approaches exist to solve numerically a Continuous-Time Markov Decision Problem (CT-MDP) that are based on optimality equations (or Bellman equations). The most popular method is the value iteration algorithm which is essentially a backward Dynamic Programming (DP). Another well known approach is to model a CTMDP as a Linear Programming (LP). LP based algorithms are slower than DP based algorithms. However, LP formulations offer the possibility to add very easily linear constraints on steady state probabilities, which is not the case of DP formulations.

1 Good introductions to CTMDPs can be found in the books of [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF], [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] and [START_REF] Guo | Continuous-Time Markov Decision Processes: Theory and Applications[END_REF].

In this paper, we consider a special class of CTMDPs that we call action Decomposed CTMDPs (D-CTMPDs). D-CTMDP typically model queueing control problems with several types of events (demand arrival, service end, failure, etc) and where a sub-action (admission, routing, repairing, etc) and also a cost is associated to each type of event. The class of D-CTMPD is related to the concept of event-based DP, first introduced by [START_REF] Koole | Structural results for the control of queueing systems using event-based dynamic programming[END_REF]. Event-based DP is a systematic approach for deriving monotonicity results of optimal policies for various queueing and resource sharing models. Citing Koole: "Event-based DP deals with event operators, which can be seen as building blocks of the value function. Typically it associates an operator with each basic event in the system, such as an arrival at a queue, a service completion, etc. Event-based DP focuses on the underlying properties of the value and cost functions, and allows us to study many models at the same time." The eventbased DP framework is strongly related to older works (see e.g. [START_REF] Lippman | Applying a new device in the optimization of exponential queuing systems[END_REF]; [START_REF] Weber | Optimal control of service rates in networks of queues[END_REF]).

Apart from the ability to prove structural properties of the optimal policy, the event-based DP framework is also a very natural way to model many queueing control problems. In addition, it allows to reduce drastically the number of actions to be evaluated in the value iteration algorithm. The following example will be used throughout the paper to illustrate our approach and results and will be referred to as the dynamic pricing problem.

Example -Dynamic pricing in a multi-class M/M/1 queue. Consider a single server with n different classes of clients that are price sensitive (see Figure 1). There is a finite buffer of size C for each client class. Clients of class i ∈ I = {1, . . . , n} arrive according to an independent Poisson λ 1 (r 1 ) process with rate λ i (r i ) where r i is a price dynamically chosen in a finite set P of k prices. For clients of class i, the waiting cost per unit of time is b i and the processing time is exponentially distributed with rate µ i . At any time the decision maker has to set the entrance price for each class of clients and to decide which class of clients to serve with the objective to maximize the average reward, in the class of preemptive dynamic policies. This problem has been studied, among other works, by [START_REF] Maglaras | Revenue management for a multiclass single-server queue via a fluid model analysis[END_REF]Maglaras ( ), C ¸il et al. (2011)), and Li and Neely (2012).

λ n (r n ) µ i C
For this example, the state and action spaces have respectively a cardinality of C n + 1 and nk n . However, the action selection process in the value iteration algorithm does not require to evaluate the nk n actions. It is sufficient to evaluate at each iteration only n(k + 1) actions (k possibilities for each class of customer and n possibilities for the class to be served). This property has been used intensively in the literature since the seminal paper of [START_REF] Lippman | Applying a new device in the optimization of exponential queuing systems[END_REF]. In the classic LP formulation of the dynamic pricing problem, that one can find in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF] for instance, the number of variables grows exponentially with the number of possible prices. In this paper, we will show that the LP can be reformulated in a way such that the number of variables grows linearly with the number of possible prices.

Our contributions can be summarized as follows. We first propose a new and natural Quadratic Programming (QP) formulation for CTMDP and relate it to more classic Dynamic Programming (DP) and Linear Programming (LP) formulations. Then, we introduce the class of D-CTMPDs which is probably the largest class of CTMDPs for which the event-based DP approach can be used. We also introduce the class of decomposed randomized policies that will be shown to be dominant among randomized policies. With these new policies, we are able to reformulate the QP and the LP with a number of variables growing linearly with the number of event types. With respect to the decomposed DP, this LP formulation is really simple to write and does not need the uniformization process necessary for the DP formulation which is sometimes source of errors and waste of time. Moreover, it allows to use generic LP related techniques such that sensitivity analysis [START_REF] Filippi | Sensitivity Analysis in Linear Programming[END_REF] or approximate linear programming [START_REF] Dos | Finding Approximate Solutions for Large Scale Linear Programs[END_REF].

Another contribution of the paper is to show how to forbid some actions while preserving the structure of the decomposed LP. If some actions (combinations of sub-actions) are forbidden, the DP cannot be decomposed anymore. In the dynamic pricing example, imagine that we want a low price to be selected for at least one class of customer. In the (non-decomposed) DP formulation, it is easy to add this constraint by removing all actions that does not contain a low price. However, it is not possible to decompose anymore the DP, in our opinion. In the decomposed LP formulation, we show how it is possible to remove this action and other combinations of actions by adding simple linear constraints. We also discuss the generic problem of reducing arbitrarily the action space by adding a set of linear constraints in the decomposed LP. Not surprisingly, this problem is difficult and is not appropriate if many actions are removed arbitrarily. When new constraints are added in the decomposed LP, it is also not clear whether deterministic policies remain dominant or not. We even prove that, given a set of linear constraints added to the LP, determining whether there exists a deterministic policy solution is NP-complete. However, for some simple action reductions, we show that deterministic policies remain dominant. We finally present numerical results comparing LP and DP formulations (decomposed or not).

Before presenting the organization of the paper, we mention briefly some related literature addressing MDP with large state space [START_REF] Bertsekas | Adaptive aggregation methods for infinite horizon dynamic programming[END_REF][START_REF] Tsitsiklis | Feature-based methods for large scale dynamic programming[END_REF] which tries to fight the curse of dimensionality, i.e. the exponential growth of the state space size with some parameter of the problem. Another issue, less tackled, appears when the state space is relatively small but the action space is very large. [START_REF] Hu | An evolutionary random policy search algorithm for solving markov decision processes[END_REF] proposes a randomized search method for solving infinite horizon discounted cost discrete-time MDP for uncountable action spaces.

The rest of the paper is organized as follows. We first address the average cost problem. Section 2 reminds the definition of a CTMDP and formulates it as a QP. We also link the QP formulation with classic LP and DP formulations. In Section 3, we define properly D-CTMDP and show how the DP and LP can be decomposed for this class of problems. Section 4 discusses the problem of reducing the action space by adding valid constraints in the decomposed LP. Section 5 compares numerically computation times of decomposed and non-decomposed formulations for both LP and DP algorithms, for the dynamic pricing problem. Finally, Section 6 explains how our results can be adapted to a discounted cost criterion.

Continuous-Time Markov Decision Processes

In this section, we remind some classic results on CTMDPs that will be useful to present our contributions.

Definition

We slightly adapt the definition of a CTMDP given by [START_REF] Guo | Continuous-Time Markov Decision Processes: Theory and Applications[END_REF]. A CTMDP is a stochastic control problem defined by a 5-tuple S, A, λ s,t (a), h s (a), r s,t (a) with the following components:

• S is a finite set of states;

• A is a finite set of actions, A(s) are the actions available from state s ∈ S;

• λ s,t (a) is the transition rate to go from state s to state t with action a ∈ A(s);

• h s (a) is the reward rate while staying in state s with action a ∈ A(s);

• r s,t (a) is the instant reward to go from state s to state t with action a ∈ A(s). Instant rewards r s,t (a) can be included in the reward rates h s (a) by an easy transformation and reciprocally. Therefore for ease of presentation, we will use the aggregated reward rate hs (a) := h s (a) + t∈S λ s,t (a)r s,t (a).

We first consider the objective of maximizing the average reward over an infinite horizon, the discounted case will be discussed in the Section 6. We restrict our attention to stationary policies which are dominant for this problem [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] and define the following policy classes:

• A (randomized stationary) policy p sets for each state s ∈ S the probability p s (a) to select action a ∈ A(s) with a∈A(s) p s (a) = 1.

• A deterministic policy p sets for each state s one action to select: ∀s ∈ S, ∃a ∈ A(s) such that p s (a) = 1 and ∀b ∈ A(s) \ {a}, p s (b) = 0.

• A strictly randomized policy has at least one state where the action is chosen randomly: ∃s ∈ S, ∃a ∈ A(s) such that 0 < p s (a) < 1.

The best average reward policy p * with gain g * is solution of the following Quadratic Program (QP) together with a vector ̟ * (called "variant pi" or "pomega"). ̟ s is to be interpreted as the stationary distribution of state s ∈ S under policy p.

̟ s = 1, (1c)
̟ s ≥ 0, ( 1d
) a∈A(s) p s (a) = 1, ∀s ∈ S, (1e)
p s (a) ≥ 0. (1f)
QP ( 1) is a natural way to formulate a stationary MDP. It is easy to see that this formulation solves the best average stationary reward policy. First Equations ( 1e) and (1f) define the space of admissible stationnary randomized policies p. Secondly for a given policy p, Equations (1b)-(1d) compute the stationary distribution ̟ of the induced Continuous-Time Markov Chain with gain expressed by Equation (1a).

As we will show in the Section 2.3, the usual LP formulation (4) can be derived directly from QP (1) by simple substitutions of variables. However, in the literature it is classically derived from the linearization of dynamic programming optimality equations given in the following subsection.

Optimality equations

A CTMDP can be transformed into a discrete-time MDP through a uniformization process [START_REF] Lippman | Applying a new device in the optimization of exponential queuing systems[END_REF]. In state s, we uniformize the CTMDP with rate Λ s := t∈S Λ s,t where Λ s,t := max a∈A(s) λ s,t (a). This uniformization rate simplifies greatly the optimality equations and linear programs.

In the rest of the paper, under relatively general conditions (typically for unichain models, see e.g. [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF]) we assume that the optimal average reward g * is independent of the initial state and is the unique solution together with an associated differential reward vector v * that satisfies the Bellman's optimality equations:

g Λ s = T v(s) -v(s), ∀s ∈ S, (2)
with operator T defined as

T v(s) := max a∈A(s) 1 Λ s hs (a) + t∈S λ s,t (a)v(t) + Λ s,t -λ s,t (a) v(s) . (3)
These optimality equations can be used to compute the best MDP policy. For instance, the value iteration algorithm roughly consists in defining a sequence of value function v n+1 = T (v n ) that provides a stationary ǫ-optimal deterministic policy in a number of iterations depending on the desired ǫ.

Linear programming formulation

Since [START_REF] Manne | Linear programming and sequential decisions[END_REF] we know that it is possible to compute the best average reward policy through a LP formulation. From Equations ( 2) and (3), one can show that the optimal average reward g * is the solution of the following program:

g * = min g s. t. g Λ s ≥ T v(s) -v(s), ∀s ∈ S, v(s) ∈ R, g ∈ R.
Linearizing the max function in operator T leads to the following LP formulation and its dual counterpart.

Primal LP

g * = min g s. t. g ≥ hs (a) + t∈S λ s,t (a) v(t) -v(s) , ∀s ∈ S, ∀a ∈ A(s), v(s) ∈ R, g ∈ R.
Dual LP (4)

g * = max
π s (a) = 1, (4c) π s (a) ≥ 0. ( 4d
)
The advantage of the dual formulation is to allow a simple interpretation: variable π s (a) is the average proportion of time spent in state s choosing action a.

A simple way to show that the dual LP (4) solves the best average reward policy is to see that it can be obtained from QP (1) by the following substitutions of variables:

π s (a) = p s (a)̟ s , ∀s ∈ S, ∀a ∈ A(s).
Indeed, any solution (p, ̟) of QP (1) can be mapped into a solution π of dual LP (4) with same expected gain thanks to the following mapping:

(p, ̟) → π = π s (a) = p s (a)̟ s .
For the opposite direction, there exists several "equivalent" mappings preserving the gain. Their differences lie in the decisions taken in unreachable states (̟ s = 0). We exhibit one:

π → (p, ̟) =   p s (a) =    πs(a) ̟s , if ̟ s = 0 1, if ̟ s = 0 and a = a 1 0, otherwise    , ̟ s = a∈A(s) π s (a)   .
Since any solution of QP (1) can be mapped to a solution of dual LP (4) and conversely, in the sequel we overload the word policy as follows:

• We (abusively) call (randomized) policy a solution π of the dual LP (4).

• We say that π is a deterministic policy if it satisfies π s (a) ∈ {0, ̟ s = a∈A(s) π s (a)}, ∀s ∈ S, ∀a ∈ A(s).
3 Action Decomposed Continuous-Time Markov Decision Processes

Definition

An action Decomposed CTMDP (D-CTMDP) is a CTMDP such that:

• In each state s ∈ S, the action space can be written as the Cartesian product of n s ≥ 1 subaction sets: A(s) = A 1 (s) × . . . × A ns (s). An action a ∈ A(s) is then composed by n s sub-actions (a 1 , . . . , a ns ) where a i ∈ A i (s).

• Sub-action a i increases the transition rate from s to t by λ i s,t (a i ), the reward rate by h i s (a i ) and the instant reward rate by r i s,t (a i ).

-The resulting transition rate from s to t is then λ s,t (a) = ns i=1 λ i s,t (a i ).

-The resulting aggregated reward rate in state s when action a is taken is then hs (a) =

ns i=1 hi s (a i ) with hi s (a i ) = h s (a i ) + t∈S λ i s,t (a i )r i s,t (a i ).
D-CTMDPs typically model queueing control problems with several types of events (demand arrival, service end, failure, etc), an action associated to each type of event (admission control, routing, repairing, etc) and also a cost associated to each type of event. Event-based DP, as defined by [START_REF] Koole | Structural results for the control of queueing systems using event-based dynamic programming[END_REF], is included in the class of D-CTMDPs.

For ease of notation, we assume without loss of generality that each state s ∈ S has exactly n s = n independent sub-action sets, with I = {1, • • • , n}, and that each sub-action set A i (s) contains exactly k sub-actions.

We introduce the concept of decomposed policy.

• A (randomized) decomposed policy is a vector p = ((p 1 s , . . . , pn s ), s ∈ S) such that for each state s there is a probability pi s (a i ) to select sub-action

a i ∈ A i (s) with a i ∈A i (s) pi s (a i ) = 1, ∀s ∈ S, ∀i ∈ I. The probability to choose action a = (a 1 , • • • , a n ) in state s is then p s (a) = i∈I pi s (a i ). • A decomposed policy p is said deterministic if ∀s ∈ S, ∀i ∈ I, ∃a i ∈ A i (s) such that pi s (a i ) = 1 and ∀b i ∈ A i (s) \ {a i }, pi s (b i ) = 0.
In other words, p selects one sub-action for each state s and each sub-action set A i .

In the following we will see that decomposed policies are dominant for D-CTMDPs. It is interesting since a decomposed policy p is described in a much more compact way than a classic policy p.

Simply applying the definition, one can check that the best average reward decomposed policy p * is solution of the following quadratic program where ̟s is to be interpreted as the stationary distribution of state s ∈ S.

Decomposed QP (5)

g * = max s∈S i∈I a i ∈A i (s) hi s (a i )p i s (a i )̟ s (5a) s. t. i∈I a i ∈A i (s) t∈S λ i s,t (a i )p i s (a i )̟ s = t∈S i∈I a i ∈A i (t) λ i t,s (a i )p i t (a i )̟ t , ∀s ∈ S, ( 5b
) s∈S ̟s = 1, ( 5c
) ̟s ≥ 0, (5d)
a i ∈A i (s) pi s (a i ) = 1, ∀s ∈ S, ∀i ∈ I, (5e) pi s (a i ) ≥ 0. ( 5f
)
Example -Dynamic pricing in a multi-class M/M/1 queue (D-CTMDP formulation). We continue the example started in the Section 1. This problem can be modeled as a D-CTMDP with state space S = {(s 1 , . . . , s n ) | s i ≤ C, ∀i ∈ I}. In each state s ∈ S, there is n s = (n + 1) sub-actions and an action can be written as a = (r 1 , . . . , r n , d) with r i the price decided to be offered to client class i and d the client class to process. The action space is then A = P n × D with D = {1, . . . , n}. The waiting cost in state (s 1 , . . . , s n ) is independent of the action selected and is worth i h i s i . The reward rate incurred by sub-action r i is λ i (r i )r i . Let the function 1 b equals 1 if boolean expression b is worth true and 0 otherwise. The resulting aggregated reward rate in state s = (s 1 , . . . , s n ) when action a = (r 1 , . . . , r n , d)

is selected is then hs (a) = n i=1 hi s (r i ) with hi s (r i ) = h i s i + 1 s i <C λ i (r i )r i .
For this example, the cardinality of the state space and the action space are respectively |S| = (C+1) n and |A| = k n n.

Optimality equations

Optimality equations for CTMDPs can be rewritten in the context of a D-CTMDPs to take advantage of decomposition properties. Let Λ i s,t = max a i ∈A i (s) λ i s,t (a i ). The uniformization rate is again Λ s = t∈S Λ s,t where Λ s,t , as defined previous section, can be rewritten as follows:

Λ s,t = max a∈A(s) λ s,t (a) = max (a 1 , ..., an) ∈ A 1 (s)×...×An(s) i∈I λ i s,t (a i ) = i∈I max a i ∈A i (s) λ i s,t (a i ) = i∈I Λ i s,t .
Operator T as defined in Equation ( 3) can be rewritten as:

T v(s) = max (a 1 , ..., an) ∈ A 1 (s)×...×An(s) 1 Λ s i∈I hi s (a i ) + t∈S λ i s,t (a i )v(t) + Λ i s,t -λ i s,t (a i ) v(s) . (6)
That we can decompose as:

T v(s) = 1 Λ s i∈I max a i ∈A i (s) hi s (a i ) + t∈S λ i s,t (a i )v(t) + Λ i s,t -λ i s,t (a i ) v(s) . (7)
The value iteration algorithm is much more efficient if T is expressed as in the latter equation. Experimental results presented in Section 5 show it clearly. Indeed computing the maximum requires n k evaluations in Equation ( 6) and nk in Equation ( 7). To the best of our knowledge, this decomposition property of operator T is used in many queueing control problems (see [START_REF] Koole | Structural results for the control of queueing systems using event-based dynamic programming[END_REF] and related papers) but has not been formalized as generally as in this paper.

Example -Dynamic pricing in a multi-class M/M/1 queue (DP approach). We can now write down the optimality equations. We use the following uniformization: let

Λ = i∈I Λ i + ∆ with Λ i = max r i ∈P {λ i (r i )} and ∆ = max i∈I {µ i }.
For a state s = (s 1 , . . . , s n ) and with e i the unitvector of the i th coordinate, the operator T for classic optimality equations can be defined as follows:

T v(s) = max (r 1 ,...,rn,d)∈A i∈I hi (r i ) + 1 s i <C λ i (r i )v(s + e i ) +1 s d >0 µ d v(s -e d ) + Λ - i∈I 1 s i <C λ i (r i ) + ∆ -1 s d >0 µ d v(s) .
Since we are dealing with a D-CTMDP, operator T can also be decomposed as:

T v(s) = 1 Λ   i∈I  h i (r i ) + max r i ∈P s i <C λ i (r i )v(s + e i ) + Λ i -λ i (r i ) v(s)   + max d∈D s d >0 µ d v(s -e d ) + (∆ -µ d )v(s) .

LP formulation

Let πi s (a i ) be interpreted as the average proportion of time spent in state s choosing action a i ∈ A i (s) among all sub-actions A i (s). From decomposed QP (5) we can build the LP (8) formulation with simple substitutions of variable:

πi s (a i ) = πi s (a i )̟ s , ∀s ∈ S, ∀i ∈ I, ∀a i ∈ A i (s).
We obtain that g * is the solution of the following LP formulation:

Decomposed Dual LP (8) g * = max s∈S i∈I a i ∈A i (s) hi s (a i )π i s (a i ) (8a) s. t. i∈I a i ∈A i (s) t∈S λ i s,t (a i )π i s (a i ) = t∈S i∈I a i ∈A i (t) λ i t,s (a i )π i t (a i ), ∀s ∈ S, (8b)
a i ∈A i (s) πi s (a i ) = ̟s , ∀s ∈ S, ∀i ∈ I, ( 8c
) s∈S ̟s = 1, (8d) πi s (a i ) ≥ 0, ̟s ≥ 0. ( 8e
)
The decomposed dual LP formulation (8) has |S|(kn + 1) variables and |S|((k + 1)n + 2) + 1 constraints. It is much less than the classic dual LP formulation (4) that has |S|k n variables and |S|(k n + 1) constraints.

Lemma 1. Any solution (p, ̟) of decomposed QP (1) can be mapped into a solution (π, ̟) of decomposed dual LP (4) with same expected gain thanks to the following mapping:

(p, ̟) → (π, ̟) = πi s (a i ) = πi s (a i )̟ s , ̟ .
For the opposite direction, there exists several "equivalent" mappings preserving the gain. Their differences lie in the decisions taken in unreachable states (̟ s = 0). We exhibit one:

(π, ̟) → (p, ̟) =   pi s (a i ) =    πi s (a i ) ̟s , if ̟s = 0 1, if ̟s = 0 and a i = a 1 0, otherwise    , ̟  .
Since any solution of the decomposed QP (5) can be matched to a solution of decomposed dual LP (8) and conversely (Lemma 1), in the sequel we again overload the word policy as follows:

• We (abusively) call (randomized) decomposed policy a solution (̟,π) of the decomposed dual LP (8).

• We say that (̟,π) is a deterministic policy if it satisfies πi s (a i ) ∈ {0, ̟s }, ∀s ∈ S, ∀i ∈ I, ∀a i ∈ A i (s).
Dualizing the decomposed dual LP (8), we obtain the following primal version:

Decomposed Primal LP (9) g * = min g s. t. m(s, i) ≥ hi s (a i ) + t∈S λ i s,t (a i ) v(t) -v(s) , ∀s ∈ S, ∀i ∈ I, ∀a i ∈ A i (s), g ≥ i∈I m(s, i), ∀s ∈ S, m(s, i) ∈ R, v(s) ∈ R, g ∈ R.
Note that the decomposed primal LP (9) could have also been obtained using the optimality equations ( 7). Indeed, under some general conditions [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF], the optimal average reward g * is independent from the initial state and together with an associated differential cost vector v * it satisfies the optimality equations ( 7). The optimal average reward g * is hence the solution of the following equations:

g * = min g s. t. g Λ s ≥ T v(s) -v(s), ∀s ∈ S.
That can be reformulated using decomposability to have:

g * = max s∈S Λ s T (v(s)) -v(s) = max s∈S i∈I max a i ∈A i (s) hi s (a i ) + t∈S λ i s,t (a i )v(t) + Λ i s,t -λ i s,t (a i ) v(s) -Λ i s v(s) = max s∈S i∈I max a i ∈A i (s) hi s (a i ) + t∈S λ i s,t (a i ) v(t) -v(s) . ( 10
)
The LP (9) can be obtained from Equation (10) using Lemma 3 given in appendix.

Example -Dynamic pricing in a multi-class M/M/1 queue (LP approach). With a = (r 1 , . . . , r n , d) ∈ A, we can now formulate its classic dual LP formulation:

max s∈S a∈A n i=1 hi (r i ) π s (a) s.t. a∈A 1 s d >0 µ d + n i=1 1 s i <C λ i (r i ) π s (a) = a∈A n i=1 1 s i >0 λ i (r i )π s-e i (a) + 1 s d <C µ d π s+e d (a) , ∀s ∈ S, s∈S a∈A π s (a) = 1, πs (a) ≥ 0.
And its decomposed Dual LP formulation:

max s∈S n i=1 hi (r i )π i s (r i ) s.t. = i∈I r i ∈P 1 s i >0 λ i (r i )π i s-e i (r i ) + d∈D 1 s d <C µ d πs+e d (d), ∀s ∈ S, r i ∈P πi s (r i ) = ̟s , ∀s ∈ S, ∀i ∈ I, d∈D πs (d) = ̟s , ∀s ∈ S, s∈S ̟s = 1, πi s (r i ) ≥ 0, πs (d) ≥ 0, ̟s ≥ 0.

Polyhedral results

Seeing the decomposed dual LP (8) as a reformulation of the decomposed QP (5), see Lemma 1, it is clear that it gives a policy maximizing the average reward. However, it doesn't provide any structure of optimal solutions. For this purpose, Lemma 2 gives two mappings linking classic and decomposed policies that are used in Theorem 1 to prove polyhedral results showing the dominance of deterministic policies. This means that the simplex algorithm on the decomposed dual LP (8) will return the best average reward deterministic policy.

Lemma 2. Let a(i) be the i th coordinate of vector a. The following policy mappings preserve the strictly randomized and deterministic properties:

D : p → p =   pi s (a i ) = a∈A(s)/a(i)=a i p s (a)   ; D -1 : p → p = p s (a 1 , . . . , a n ) = i∈I pi s (a i ) . Moreover: (a) D is linear. (b)
The following policy transformations preserve moreover the excepted gain:

1. (p, ̟) → (p, ̟) = (D(p), ̟); 2. π → (π, ̟) = (D(π), ̟s = a∈A(s) π s (a)); 3. (p, ̟) → (p, ̟) = (D -1 (p), ̟); 4. (π, ̟) → (π, ̟) = (D -1 (π), ̟).
Theorem 1. The best decomposed CTMDP average reward policy is solution of the decomposed dual LP (8). Equations (8b)-(8e) describe the convex hull of deterministic policies.

Proof: We call P the polytope defined by constraints (8b)-(8e). From Lemma 1 we know that all policies are in P . To prove that vertices of P are deterministic policies we use the characterization that a vertex of a polytope is the unique optimal solution for some objective.

Assume that (π, ̟) is a strictly randomized decomposed policy, optimal solution with gain g of the decomposed dual LP (8) for some objective ho . From Lemma 2 we know that there exists a strictly randomized non decomposed policy (π, ̟) with same expected gain. Deterministic policies are dominant in non decomposed models, therefore there exists a deterministic policy (π * , ̟ * ) with gain g * ≥ g. From Lemma 2 we can convert (π * , ̟ * ) into a deterministic decomposed policy (π * , ̟ * ) with same expected gain g * = g * ≥ g. Since (π, ̟) is optimal we have then g * = g * which means that (π, ̟) is not the unique optimal solution for objective ho . Therefore a strictly decomposed randomized policy can't be a vertex of the decomposed LP (8) and P is the convex hull of deterministic policies.

Benefits of decomposed LP

First, recall that with the use of action decomposability, decomposed LP (8) allows to have a complexity polynomial in the number of independent sub-action sets: |S|(kn + 1) variables and |S|((k + 1)n + 2) constraints for the dual whereas in the classic it grows exponentially: |S|k n variables and |S|(k n + 1) constraints. In the Section 5 we will see that it has a substantial impact on the computation time.

Secondly, even if the LP ( 8) is slower to solve than DP (7), as shown experimentally in the Section 5, this mathematical programming approach offers some advantages. First, LP formulations can help to characterize the polyhedral structure of discrete optimization problems, see Büyüktahtakin (2011). Secondly, there is in the LP literature generic methods directly applicable such as sensitive analysis, see [START_REF] Filippi | Sensitivity Analysis in Linear Programming[END_REF], or approximate linear programming techniques, see [START_REF] Dos | Finding Approximate Solutions for Large Scale Linear Programs[END_REF]. Another interesting advantage is that the dual LP (8) is really simple to write and does not need the uniformization necessary to the DP (7) which is sometimes source of waste of time and errors.

Finally, a big benefit of the LP formulation is the ability to add extra constraints that are not known possible to consider in the DP. A classic constraint that is known possible to add only in the LP formulation is to restrain the stationary distribution on a subset T ⊂ S of states to be greater than a parameter q, for instance to force a quality of service:

s∈T ̟ s ≥ q.
Nevertheless, we have to be aware that such constraint can enforce strictly randomized policies as optimal solutions. In the next section we discuss constraints that preserve the dominance of deterministic policies.

4 Using decomposed LP to tackle a wider class of large action space MDP

Constraining action space, preserving decomposability

In decomposed models we can lose hand on certain action incompatibilities we had on classic ones:

Example -Dynamic pricing in a multi-class M/M/1 queue (Adding extra constraints). Let say we have two prices high h and low l for the n classes of clients. In a state s we have then the following set of actions: A(s) = P (s) × D(s) where P (s) = n i=1 P i (s) and P i (s) = {h i , l i }. Assume that, for some marketing reasons, there needs to be at least one low price selected. In the non decomposed model, it is easily expressible by a new space of action P ′ (s) = P (s) \ {(h 1 , . . . , h n )} removing the action where all high prices are selected. However, it is not possible to use decomposition anymore with this new action space, even though there is still some structure in the problem.

When reducing the action space event-based DP techniques are inapplicable, but we can use some polyhedral properties of the LP formulation to model this action space reduction. In Theorem 2, we will show that it is possible to reduce the action space of any state s ∈ S to A ′ (s) ⊆ A(s) and to preserve the action decomposability advantage by adding a set of constraints to the decomposed dual LP (8). However, this theorem is not constructive and only proves the existence of such constraints. Moreover, in general the number of constraints necessary to characterize the admissible decomposed policies might be exponential and it would be finally less efficient than considering the non decomposed model (Proposition 1). Nevertheless, in some particular cases, one might be able to intuitively formulate some valid constraints that a decomposed policy should respect as in the following example.

Example -Dynamic pricing in a multi-class M/M/1 queue (Constraining in average). In average we can forbid solutions with all high prices (sub-action h i ) by selecting at most n -1 high prices (Equation (11a)), or at least one low price (sub-action l i , Equation (11b)):

n i=1 pi s (h i ) = n i=1 πi s (h i ) ̟s ≤ n -1, (11a)
or

n i=1 pi s (l i ) = n i=1 πi s (l i ) ̟s ≥ 1. ( 11b
)
These equations constrain the average behaviour of the system. However, together with decomposed dual LP (8) it is not obvious that they provide optimal deterministic policies in general. In Corollary 1, we will provide a state-policy decomposition criteria to verify if a set of constraints correctly models an action space reduction. However, to apply it in general as we will prove in Proposition 2, it involves to solve a co-NP complete problem. Moreover, when trying to formulate valid constraints, we will see in Proposition 3 that it is even NP-complete to check whether or not there exists one feasible deterministic policy (not only the optimal). These results hold in general, in practice Equations (11a) or (11b) correctly models the action space reduction and can be generalized under the general action reduction constraint framework. In Corollary 2 we will prove that we can use several action reduction constraints at the same time (under some assumptions) and always obtain deterministic policies as optimum. In other words, adding such constraints to the decomposed dual LP (8) and using the simplex algorithm to solve it will return an optimal deterministic solution. Next example provides another application of action reduction constraint framework.

Example -Dynamic pricing in a multi-class M/M/1 queue (Another extra constraints). We want now to select exactly n/2 high prices, the number of actions to remove from the original action space is exponential in n:

A ′ (s) = {(a 1 , . . . , a n ) | n i=1 1 a i =l = n/2} = A(s)\{(a 1 , . . . , a n ) | n i=1 1 a i =l = n/2}.
Although, there is a simple way to model this constraint in average with the action reduction constraint framework ensuring the dominance of deterministic policies:

n i=1 pi s (h i ) = n i=1 πi s (h i ) ̟s = n 2 . ( 12
)

State policy decomposition criteria

In the following for each s ∈ S, πs (resp. ps ) represents the matrix of variables πi s (a i ) (resp. pi s (a i )) with i ∈ I and a i ∈ A i (s). The next theorem states that there exists a set of constraints to add to the decomposed dual LP (8) so that it correctly solves the policy within A ′ maximizing the average reward criterion and that the maximum is attained by a deterministic policy.

Theorem 2. For a decomposed CTMDP with a reduced action space A ′ (s) ⊆ A(s), ∀s ∈ S, there exists a set of linear constraint { Bs ps ≤ bs , ∀s ∈ S} that describes the convex hull of deterministic decomposed policies p in A ′ (s). Then { Bs πs ≤ bs ̟s , ∀s ∈ S} together with equations (8b)-(8e) defines the convex hull of decomposed deterministic policies (π, ̟) in A ′ .

Proof: Equations ( 1e) and (1f) of non decomposed QP (1) specify the space of feasible policies p for a classic CTMDP. For each state s ∈ S we can reformulate this space by the convex hull of all feasible deterministic policies: p s ∈ conv{p s | ∃a ∈ A ′ (s) s.t. p s (a) = 1}. We use the mappings D and D -1 defined in Lemma 2. Note that for any linear mapping M and any finite set X, conv(M(X)) = M(conv(X)). D is linear, therefore for each state s ∈ S the convex hull H s of CTMDPs policy with supports in A ′ (s) is mapped into the convex hull Hs of decomposed CTMDPs state policy in A ′ (s):

D(H s ) = Hs ⇔ D conv p s | ∃a ∈ A ′ (s) s.t. p s (a) = 1 = conv D(p s ) | ∃a ∈ A ′ (s) s.t. p s (a) = 1 = conv ps | ∃(a 1 , . . . , a n ) ∈ A ′ (s) s.t. pi s (a i ) = 1 .
Recall (a particular case of) Minkowski-Weyl's theorem: for any finite set of vectors A ′ ⊆ R n there exists a finite set of linear constraints {Bv ≤ b} that describes the convex hull of vectors v in A ′ . Hs is convex hence from Minkowski-Weyl's theorem there exists a matrix Bs and a vector bs such that vectors ps in Hs can be described by the constraints Bs ps ≤ bs . In the decomposed dual QP (5) we can then replace Equations ( 5e) and (5f) that specify the set of feasible D-CTMDP policies by constraints { Bs ps ≤ bs , ∀s ∈ S}. With substitutions of variable, constraints C := { Bs πs ≤ bs ̟s , ∀s ∈ S} are linear in (π s , ̟s ) and can hence be added to the decomposed dual LP (8).

As in Theorem 1, with the characterization that a vertex of a polytope is the unique solution for some objective, we prove now that the vertices of the polytope defined by Equations ( 8b)-(8e) together with constraints C are deterministic policies. Assume (π, ̟) is a strictly randomized decomposed policy of gain g, optimal solution of the decomposed dual LP (8) for some objective h0 together with constraints C. (π, ̟) can be mapped into a strictly randomized non decomposed policy (π, ̟), still respecting C, with same expected gain that is dominated by a deterministic policy (π * , ̟ * ) respecting also C with gain g * ≥ g. (π * , ̟ * ) can be again mapped into a deterministic decomposed policy (π * , ̟ * ) respecting C with same expected gain g * = g * ≥ g. But since (π, ̟) is optimal we have then g * = g * which means that (π, ̟) is not the unique optimal solution for objective h0 . Therefore, a strictly decomposed randomized policy can't be a vertex of the decomposed dual LP (8) together with constraints C.

Corollary 1 (State policy decomposition criteria). If the vertices of the polytope { Bs ps ≤ bs } are {0, 1}vectors for each state s ∈ S, decomposed dual LP (8) together with constraints { Bs πs ≤ bs ̟s , ∀s ∈ S} has a deterministic decomposed policies as optimum solution.

In other words, if in any states s ∈ S, one finds a set of constraints { Bs ps ≤ bs } defining a {0, 1}polytope constraining in average the feasible policies p to be in the reduced action space A ′ (s), then, the state policy decomposition criteria of Corollary 1 says that solving the decomposed dual LP (8) together with constraints { Bs πs ≤ bs ̟s , ∀s ∈ S} will provide an optimal deterministic policy in A ′ .

Complexity and efficiency of action space reduction

We return to our example in the Section 4.1, where we want to use action decomposability on a reduced action space A ′ (s) = D(s) × n i=1 P i (s) \ {(h 1 , . . . , h n )}. Theorem 2 states that there exists a set of constraints to add in the decomposed dual LP (8) such that it will return the best policies within A ′ and that this policy will be deterministic. However, as we show in the next proposition, in general the polyhedral description of a subset of decomposed policies can be less efficient than the non-decomposed ones.

Proposition 1. The number of constraints necessary to describe a subset of decomposed policies can be higher than the number of corresponding non-decomposed policies itself.

Proof: There is a positive constant c such that there exist {0, 1}-polytopes in dimension n with ( cn log n ) n 4 facets [START_REF] Bárány | On 0-1 polytopes with many facets[END_REF], while the number of vertices is less than 2 n . In practice, we saw in our dynamic pricing example that one can formulate valid inequalities. We can apply Corollary 1 to check if the decomposed dual LP (8) together with equations (11b) correctly models the action space reduction. However, to use Corollary 1 we would need to be able to check if these constraints define a polytope with {0, 1}-vector vertices. In general, to determine whether a polyhedron {x ∈ R n : Ax ≤ b} is integral is co-NP-complete [START_REF] Papadimitriou | On recognizing integer polyhedra[END_REF]). In the next proposition we show that it is also co-NP-complete for {0 -1}-polytopes as a direct consequence of [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF].

Proposition 2. Determining whether a polyhedron {x ∈ [0, 1] n : Ax ≤ b} is integral is co-NPcomplete.

Proof:

Let A ′ be a {0 -1}-matrix with precisely two ones in each column. From [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF] we know that the problem of deciding whether the polyedron P defined by the linear system

{A ′ x ≥ 1, x ≥ 0} is integral is co-NP-complete. Note that all vertices v of P respect 0 ≤ v ≤ 1. Therefore, {A ′ x ≥ 1, x ≥ 0} is integral if and only if {A ′ x ≥ 1, 0 ≤ x ≤ 1} is integral.
It means that determining whether the polyedron P defined by the linear system {A ′ x ≥ 1, 0 ≤ x ≤ 1} is integral is co-NP-complete. This is a particular case of determining whether for a general matrix A a polyhedron {x ∈ [0, 1] n : Ax ≤ b} is integral.

As a consequence of Proposition 2, deciding if {B s ps ≤ b s , ∀s ∈ S} defines the convex hull of deterministic policies it contains is co-NP-complete. In fact, it is even NP-complete to determine if it contains a deterministic policy solution at all: Proposition 3. Consider a decomposed CTMDP with extra constraints of the form {B s ps ≤ b s , ∀s ∈ S}. Determining if there exists a feasible deterministic policy solution of this decomposed CTMDP is NP-complete even if |S| = 1.

Proof: We show a reduction to the well known NP-complete problem 3-SAT. We reduce a 3-SAT instance with a set V of n variables and m clauses to a D-CTMDP instance. The system is composed with only one state s, so ̟ s = 1. Each variable v creates an independent sub-action set A v containing two sub-actions representing the two possible states (literal l) of the variable: v and v. We have then A = v∈V A v = v∈V {v, v} . Each clause C generates a constraint: l∈C l ≥ 1. Finally, there exists a deterministic feasible policy for the D-CTMDP instance if and only if the 3-SAT instance is satisfiable.

An interesting generic constraint

Definition 1 (Action reduction constraint). An action reduction constraint (s, R, m, M) constrain in a state s ∈ S to select in average at least m and at most M sub-actions a i out of a set R belonging to different sub-action sets A i (s). Its feasible policies space is defined by the following equation:

m ≤ a i ∈R pi s (a i ) = a i ∈R πi s (a i ) ̟s ≤ M. ( 13
)
Although it is hard in general to find and to prove that a given set of linear equations models correctly a reduced action space, we show in the following corollary, consequence of Corollary 1, that it is nevertheless possible to exhibit some valid constraints.

Corollary 2. Combination of action reduction constraints] For a set of action reduction constraints {(s j , R j , m j , M j ) | j ∈ J}, if no sub-action a i is present in more than one action reduction constraint R j , then the decomposed dual LP (8), together with Equations {(13) | j ∈ J}, preserves the dominance of optimal policies. Moreover, the solution space of this LP is the convex hull of deterministic policies respecting the action reduction constraints. More formally, this sufficient condition can be reformulated as: ∀s ∈ S, j∈J R j is a sub-partition of i∈I A i (s).

Proof: We know that pi s (a i ) = πi s (a i ) ̟s
is the discrete probability to take action a i out of all actions A i (s) in state s. Therefore, in state s, for an action reduction constraint (s, R, m, M), Equation ( 13) reduces the solution space to the decomposed randomized policies that select in average at least m and at most M actions out of the set R: m ≤ a i ∈R pi s (a i ) ≤ M. If no sub-action is present in more than one action reduction constraint, then the matrix { a i ∈R j pi s (a i ), j ∈ J} is totally unimodular and defines therefore a polytope with {0, 1}-vector vertices. Using Corollary 1 we know then that deterministic policies are dominant.

Returning to our dynamic pricing example where we want to have at least one low price selected. From Corollary 2, we know now that adding Equations (11a) or (11b) to LP (8) will return optimal deterministic policies with a simplex solution technique. It is also the case when imposing to have exactly half of the high prices selected with Equations (12).

Numerical experiments

In this section we compare the efficiency of the LP formulation and the dynamic formulation with both the classic and decomposed formulation for the multi-class M/M/1 queue dynamic pricing example detailed in the previous sections. We create instances with n classes of clients and with the set of k prices P = {2i, i ∈ {0, . . . , k -1}}. Clients of class i with price r i ∈ P arrive according to an independent Poisson process with rate λ i (r i ) = (4 -i)(10 -r i ), except for the price 0 which means that we are refusing a client: i.e. λ i (0) = 0. For a client of class i the waiting cost per unit of time is h i = 2 4-i and his processing time is exponentially distributed with rate µ i = 20 -4i.

Algorithms are tested on an Intel core 2 duo 2.4 Ghz processor with 2 GB of RAM. Heuristics are written in JAVA and the LP is solved with Gurobi 4.6. Legend (F-M) has to be read as follows: F∈{C, D} stands for Formulation, C for Classic or D for Decomposed; M∈{VI-ǫ, LP} stands for Method, VI-ǫ for Value Iteration at precision ǫ and LP for Linear Programming.

We compare the computation time of the different algorithms on the same instances. We confront 6 solution methods: the classic and decomposed value iteration algorithms for two values of ǫ: 10 -2 and 10 -5 , and the classic and decomposed dual LP formulation.

First, for both the classic and the decomposed formulation, the value iteration computation time depends on the precision asked: dividing ǫ per 1000 increases roughly the computation time by a factor 2. We also clearly see that the value iteration algorithm is much quicker to solve than the LP formulation.

Secondly benefits of the decomposition appear obvious. When the number of states grows, variations on the queue capacity C (Table 1) or the number of classes n (Table 2) influence less the decomposed formulation. It is even clearer when we increase the number of proposed prices k, indeed as shown in Table 3, the difference of computation time between the classic and the decomposed formulations increases exponentially with k.

Finally, in Table 4 we study a D-CTMDPs with reduced action space. We take decomposable instance with (C=5, n=4, k=4) and study two action space reductions: the case where we forbid to have all high prices selected in a same state (|P ′ | = |P| -1) and the case where we want to select exactly n/2 high prices ((|P ′ | ≈ |P|/2)). Decomposed DP formulation are in this case Non Applicable (NA). Table 4 reports the important benefit in term of computation time of using the decomposed LP formulation.

(C,n,k) C-VI-10 -2 D-VI-10 -2 C-VI-10 -5 D-VI-10

Discounted reward criterion

We extends our results now to the discounted reward criterion, i.e. when future rewards are discounted by factor β ∈]0, 1[. In this section we use a positive scalar α s , s ∈ S which satisfies s∈S α s = 1, any other positive constant would work but when the sum equals to 1 it allows an interpretation as an initial state probability distribution over S.

6.1 Classic CTMDP

λ s,t (a) = max (a 1 , ..., an) ∈ A 1 (s)×...×An(s) i∈I λ i s,t (a i ) = i∈I max a i ∈A i (s) λ i s,t (a i ).
We have then that the optimal expected discounted reward per state v * satisfies the optimality equations:

∀s ∈ S, v(s) = T v(s) , (14)
with the operator T defined ∀s ∈ S as follows:

T v(s) = max a∈A(s) 1 β + Λ s hs (a) + t∈S λ s,t (a)v(t) + Λ s,t -λ s,t (a) v(s) .
To compute the best MDP policy we can use the value iteration algorithm on optimality equations ( 14). It is the same scheme as defined for the average reward criterion in the Section 2.2.

LP formulation

Under some general conditions, the optimality equations ( 14) have a solution and the optimal expected reward per state v * is the vector v with the smallest value s∈S α s v(s) which satisfies:

v(s) ≥ T v(s) , ∀s ∈ S. (15)
We can linearize the max function of operator T in equations ( 15) to formulate the following LP which has for optimal solution v * : We can interpret the dual variables π s (a) as the total discounted joint probability under initial state distributions α s that the system occupies state s ∈ S and chooses action a ∈ A(s). Some other interpretations can be retrieved in [START_REF] Puterman | Markov Decision Processes: Discrete Stochastic Dynamic Programming[END_REF].

Primal LP min s∈S α s v(s) s.t. β + t∈S λ s,t (a) v(s) - t∈S λ s,t (a)v(t) ≥ hs (a), ∀s ∈ S, ∀a ∈ A(s), v (
We could have also constructed the previous dual LP with variable substitutions from the following QP: 6.2 Action Decomposed CTMDP

Optimality equations

To use the action decomposability we rewrite optimality equations ( 14) with an explicit decomposition.

Using the same uniformization as in the classic case we obtain a decomposed operator T : ∀s ∈ S,

T v(s) = max (a 1 , ..., an) ∈ A 1 (s)×...×An(s) n i=1 1 β + Λ s hi s (a i ) + t∈S λ i s,t (a i )v(t) + Λ i s,t -λ i s,t (a i ) v(s) = i=∈I max a i ∈A i (s) 1 β + Λ s hi s (a i ) + t∈S λ i s,t (a i )v(t) + Λ i s,t -λ i s,t (a i ) v(s) .
To compute the best MDP policy we can now use again the value iteration algorithm but with the decomposed operator that is much more efficient. The optimality equations with the decomposed operator also lead to a LP formulation that we formulate in the next section.

LP formulation

Under some general conditions, optimality equations ( 14) with decomposed operator T have a solution and the optimal expected reward per state v * is the vector v with the smallest value s∈S α s v(s) which satisfies:

αv * =
˚ π i s (a i ) ≥ 0, ˚ ̟ s ≥ 0.
Under initial state distributions α, we can interpret ˚ ̟ s as the total discounted joint probability that the system occupies state s ∈ S under initial state distributions α s , and ˚ π i s (a i ) as the total discounted joint probability that the system occupies state s ∈ S and chooses action a i ∈ A i (s). The decomposed dual LP has |S|(kn + 1) variables and |S|((k + 1)n + 2) constraints. It is much less than the classic dual LP that has |S|k n variables and |S|(k n + 1) constraints.

We could have also constructed the previous dual decomposed LP with variable substitutions from the following QP: A From decomposed DP to decomposed LP

The following lemmata help to pass from decomposed optimality DP equations to decomposed LP formulations. For the average reward criterion, using Lemma 3 can build decomposed primal LP (9) from optimality Equations (10). Lemma 3 do the same transformation for the discounted reward criterion.

Lemma 3. For any finite sets S, I, A and any data coefficients γ s,i,a ∈ R with s ∈ S, i ∈ I and a ∈ A, the value Proof: Let g * be an optimal solution of this LP. First it is trivial that g * ≥ max s∈S i∈I m(s, i) and that Moreover we are minimizing g without any other constraints, hence g * = max s∈S i∈I m(s, i) . Secondly for any optimal solution g * , there exists s ′ ∈ S such that i∈I m(s ′ , i) = g * and ∀i ∈ I, m(s ′ , i) = max a∈A {γ s ′ ,i,a }, otherwise there would exist a strictly better solution. Therefore finally g * = max s∈S i∈I max a∈A {γ s,i,a } . Lemma 4. For any finite sets S, I, A, any data coefficients α s , γ s,t,i,a , δ s,i,a , ζ s ∈ R, s, t ∈ S, i ∈ I and a ∈ A, the vector v ∈ R |S| with the smallest value s∈S α s v(s) satisfying 0 ≥ max

g * = max

Figure 1 :

 1 Figure 1: The multi-class M/M/1 queue with dynamic pricing.

  t (a) π s (a) -t∈S a∈A(t) λ t,s (a) π t (a) = α s , ∀s ∈ S, π s (a) ≥ 0.

  t (a) ̟ s p s (a) -t∈S a∈A(t) λ t,s (a) ̟ t p t (a) = α s , ∀s ∈ S, s∈S a∈A(s) p s (a) = 1, ̟ s ≥ 0, p s (a) ≥ 0.

  pi s (a i ) = 1, ∀s ∈ S, ∀i ∈ I, pi s (a i ) ≥ 0, ˚ ̟ s ≥ 0.Remark 1. Theorems 1, 2, Propositions 1, 2, 3, Corollary 1 and 2 are also applicable when considering the discounted reward criterion with the substitution ( π, ̟) → (π, ̟), ( ˚ π, ˚ ̟) → (π, ̟)

  of the following LP:g * = min g s. t. m(s, i) ≥ γ s,i,a , ∀s ∈ S, ∀i ∈ I, ∀a ∈ A, g ≥ i∈I m(s, i), ∀s ∈ S, m(s, i) ∈ R, ∀s ∈ S, ∀i ∈ I, g ∈ R.

Table 1 :

 1 Influence of the queue capacity C on the algorithms computation time (in s.).

	-5 C-LP D-LP

Table 2 :

 2 Influence of the number of classes n on the algorithms computation time (in s.).

	(C,n,k) C-VI-10 -2 D-VI-10 -2 C-VI-10 -5 D-VI-10 -5 C-LP D-LP
	(10,3,2)	2.51	0.45	2.67	0.54	7.1	1.1
	(10,3,3)	6.12	0.55	10.60	0.81	20.4	2.6
	(10,3,4)	18.02	1.05	34.89	1.70	101.8 7.08
	(10,3,5)	37.56	1.2	80.23	2.03	331	9.7

Table 3 :

 3 Influence of the number of prices k on the algorithms computation time (in s.).

	|P ′ |	C-VI-10 -2 D-VI-10 -2 C-VI-10 -5 D-VI-10 -5 C-LP D-LP
	|P| -1	81.2	NA	357.6	NA	503.1 3.15
	|P|/2	45.3	NA	165.5	NA	279.8	3.7

Table 4 :

 4 Computation time (in s.) to solve a CTMDP (C=5, n=4, k=4) with a reduced action space P ′ .

  To write down the optimality equations, in state s we use an unifomization with rate Λ s := t∈S Λ s,t

	6.1.1 Optimality equations
	with:
	Λ s,t := max a∈A(s)

  minWith Lemma 4 (given in appendix) we obtain that v * is the solution of the following LP.

	That we can reformulate:
	min	α s v(s)
		s∈S
	s. t. 0 ≥ max s∈S	T v(s) -v(s)
		≥ max s∈S	(β + Λ s )(T v(s) -v(s))
			n
		≥ max s∈S	i=1	max a i ∈A i (s)	hi s (a i ) +	t∈S	λ i s,t (a i ) v(t) -v(s)	-βv(s) .
	Decomposed Primal LP
	min
	Decomposed Dual LP
	max	˚ π i s (a i ) hi s (a i )
	s∈S i∈I a i ∈A i (s)
	s.t.	˚ π i s (a i ) = ˚ ̟ s ,					∀s ∈ S, ∀i ∈ I,
	β ˚ ̟ s +
				α s v(s)
				s∈S
			s. t. v(s) ≥ T v(s) ,	∀s ∈ S.

s∈S α s v(s) s.t. m(s, i) ≥ hi s (a i ) + t∈S λ i s,t (a i ) v(t) -v(s) , ∀s ∈ S, ∀i ∈ I, ∀a i ∈ A i (s), βv(s) -i∈I m(s, i) ≥ 0, ∀s ∈ S ≤ 0, m(s, i) ∈ R, v(s) ∈ R. a i ∈A i (s) i∈I a i ∈A i (s) t∈S λ i s,t (a i ) ˚ π i s (a i ) -t∈S i∈I a i ∈A i (t) λ i t,s (a i ) ˚ π i t (a i ) = α s , ∀s ∈ S,

  Decomposed QP max s∈S i∈I a i ∈A i (s) hi s (a i )p i s (a i ) ˚ ̟ s s.t. β ˚ ̟ s + i∈I a i ∈A i (s) t∈S λ i s,t (a i )p i s (a i ) ˚ ̟ s -t∈S i∈I a i ∈A i (t) λ i t,s (a i )p i t (a i ) ˚ ̟ t = α s , ∀s ∈ S,

a i ∈A i (s)

  γ s,t,i,a v(s) + δ s,i,a , ∀s ∈ S, ∀i ∈ I, ∀a ∈ A, It is clear that we are minimizing s∈S α s v(s). Now for any vector v we can see that ∀s ∈ S, ∀i ∈ I, m(s, i) ≥ max a∈A t∈S γ s,t,i,a v(s) + δ s,i,a , and we have ∀s ∈ S, i∈I m(s, i) + ζ s v(s) ≤ 0. Therefore any vector v solution must satisfy ∀s ∈ S 0 ≥ i∈I max a∈A t∈S γ s,t,i,a v(s) + δ s,i,a +ζ s v(s) and finally 0 ≥ max s∈S i∈I max a∈A t∈S γ s,t,i,a v(s) + δ s,i,a + ζ s v(s) .

	is the solution of the following LP:
	min	α s v(s)
	s∈S
	s. t. m(s, i) ≥
	0 ≥	m(s, i) + ζ s v(s),	∀s ∈ S,
		i∈I
	m(s, i) ∈ R, v(s) ∈ R.
		s∈S	i∈I	max a∈A	t∈S

γ s,t,i,a v(s) + δ s,i,a + ζ s v(s) t∈S Proof: