Abdel Lisser
email: abdel.lisser@l2s.centralesupelec.fr

Vikram Vikas

Vikas Vikram Singh
email: vikassingh@iitd.ac.in

Varagapriya
email: varagapriyav@gmail.com

V Varagapriya

Joint Chance-Constrained Markov Decision Processes

Keywords: Constrained Markov decision process, Joint chance constraint, Second order cone programming problem, Copula, Elliptical distribution, Queueing problem. 1 Joint Chance-Constrained Markov Decision Processes

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Markov decision process (MDP) is a decision making framework for a stochastic system which evolves over finite/infinite horizon. The system can have a finite or infinite number of states, and at each state, a controller chooses an action from a set of available actions at that state. The system moves from one state to another state according to a controlled Markov chain. At every stage, the system incurs cost whenever a state is visited and an action is taken. The objective is to find a policy which minimizes the expected cost incurred over a period of time. The discounted and average cost criteria are most commonly used in the literature. For a finite state-action MDP with known transition probabilities and running costs, there exists a stationary deterministic optimal policy and it can be obtained by using dynamic programming and Linear programming (LP) based methods [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Bertsekas | Dynamic Programming and Optimal Control, 2nd edn[END_REF][START_REF] Puterman | Markov Decision Process[END_REF]. In many real-life examples, there are more than one running costs incurred at every stage whenever the Markov chain visits a state and an action is taken [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Altman | Asymptotic properties of constrained Markov decision processes[END_REF][START_REF] Archak | Budget optimization for online advertising campaigns with carryover effects[END_REF]. One type of running cost defines an expected cost function which needs to be minimized and other types of running costs define the expected cost functions on which constraints are imposed. This class of MDP is called a constrained Markov decision process (CMDP). When running costs and transition probabilities are stationary and exactly known, there exists a stationary randomized optimal policy for a finite state-action CMDP problem and it can be obtained by solving an equivalent LP problem [START_REF] Altman | Constrained Markov Decision Processes[END_REF].

In practice, the MDP model parameters such as running costs and transition probabilities are not exactly known. They are either learnt with experience or from historical data, thereby leading to errors in the optimal policies [START_REF] Mannor | Bias and variance approximation in value function estimates[END_REF]. The early literature on MDPs with uncertain parameters dates back to the 1970s, where MDPs under uncertain transition probabilities were studied [START_REF] Satia | Markovian decision processes with uncertain transition probabilities[END_REF][START_REF] White | Markov decision processes with imprecise transition probabilities[END_REF]. Previous studies have accounted for the uncertainties in MDPs under a robust optimization framework by considering the worst case realization of the uncertain parameters [START_REF] Iyengar | Robust dynamic programming[END_REF][START_REF] Nilim | Robust control of Markov decision processes with uncertain transition matrices[END_REF][START_REF] Wiesemann | Robust Markov decision processes[END_REF]. Recently, the equivalent reformulations of robust CMDP problem, with uncertain costs and known transition probabilities, for various uncertainty sets are proposed by Varagapriya et al. [START_REF] Varagapriya | Constrained Markov decision processes with uncertain costs[END_REF]. Delage and Mannor [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF] observed that robust optimization problems can give highly conservative optimal solutions. As an alternative approach, they considered an uncertain MDP problem under discounted cost criterion where either running costs or transition probabilities are defined as random variables and proposed a chance constraint programming based formulation. The chance constraint based MDP is equivalent to a second order cone programming (SOCP) problem when the running cost vector follows a normal distribution and transition probabilities are known [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF]. When the prior transition probabilities follow Dirichlet distribution and running costs are known, the uncertain MDP problem becomes intractable and optimal policies can be computed using approximation methods [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF].

To the best of our knowledge, CMDPs where either running costs or transition probabilities are defined using random variables are not considered in the literature. In this paper, we consider a CMDP problem under both discounted and average cost criteria where running cost vectors are random vectors and transition probabilities are known. We use chance constraint programming [START_REF] Charnes | Chance-constrained programming[END_REF][START_REF] Prékopa | Stochastic Programming[END_REF] to model the uncertainties present in the objective function and the constraints of the CMDP problem. For a given policy, the chance constraint based objective function of the CMDP problem gives a minimum long run expected cost which is incurred with at least a given probability level. The random constraints of the CMDP problem is defined as a joint chance constraint which guarantees that the random constraints are jointly satisfied with at least a given probability level. We call this uncertain CMDP as a joint chance-constrained Markov decision process (JCCMDP). In general, the random constraint vectors present in the joint chance constraint can be dependent random vectors. In order to study the dependence structure of random variables, the concept of copula was introduced by Abe Sklar in 1959 [START_REF] Sklar | Fonctions de répartition à n dimensions et leurs marges[END_REF]. We consider the case when running cost vectors follow multivariate elliptically symmetric distribution and dependence among random constraint vectors is driven by a Gumbel-Hougaard copula. The deterministic equivalent of the JCCMDP problem is a non-convex optimization problem. We approximate the latter by proposing two SOCP problems whose optimal values give upper and lower bounds of the optimal value of the JCCMDP problem. As an application, we study the problem of admission and service control in a queueing system and perform numerical experiments by considering various instances of different sizes.

The rest of the paper is organized as follows. Section 2 introduces the definition of a CMDP. Section 3 presents a JCCMDP problem and its SOCP based approximations. Section 4 gives the results of numerical experiments carried out on the queueing control problem. We conclude the paper in Section 5.

Constrained Markov decision processes

We define an infinite horizon CMDP by the following objects [START_REF] Altman | Constrained Markov Decision Processes[END_REF]:

(i) S is a finite set of states whose generic element is denoted by s.

(ii) A is a finite set of actions and A(s) denotes the set of actions available at state s. (iii) K = {(s, a) s ∈ S, a ∈ A(s)} is the set of all state-action pairs; K denotes the cardinality of K. (iv) γ = (γ(s)) s∈S is a probability distribution according to which an initial state is chosen. (v) p ∶ K → ℘(S) is a transition probability function where ℘(S) is the set of probability distributions on S; p(s ′ s, a) is the probability of moving from state s to s ′ when the controller chooses an action a ∈ A(s). (vi) c = c(s, a) (s,a)∈K denotes the running cost vector associated with the objective function, where c(s, a) is the cost incurred at state s when an action a ∈ A(s) is chosen.

(vii) d k = d k (s, a) (s,a)∈K , k = 1, 2, . . . , K, denote the running cost vectors associated with the constraints, where d k (s, a) is the cost incurred at state s when an action a ∈ A(s) is chosen. (viii) (ξ k ) K k=1 are the bounds for the constraints. We consider a discrete-time infinite horizon controlled Markov chain (X t , A t ) ∞ t=0 , where (X t , A t ) denotes the state-action pair at time t. At time t = 0, the state of the Markov chain is s 0 ∈ S according to an initial distribution γ and the controller chooses an action a 0 ∈ A(s 0 ). As a consequence, running costs c(s 0 , a 0 ), d k (s 0 , a 0 ), k = 1, 2, . . . , K, are incurred. The Markov chain moves to state s 1 at time t = 1 with probability p(s 1 s 0 , a 0 ) and the same thing repeats at s 1 and it continues for the infinite horizon. In general, the decision at time t may depend on the history h t = (s 0 , a 0 , s t=0 is called a stationary policy if there exists a decision rule f such that f t = f for all t. We write a stationary policy (f, f, . . . ) by f with abuse of notation, and define f = (f (s)) s∈S such that f (s) ∈ ℘(A(s)) for every s ∈ S. According to a stationary policy f , whenever the Markov chain visits state s, the controller chooses an action from A(s) according to the decision rule f (s). We denote the set of all history dependent and stationary policies by F HD and F S , respectively.

The policy f h and initial distribution γ define a probability measure P f h γ over the state and action trajectories, and E f h γ denotes the expectation operator corresponding to probability measure P f h γ . For a given history dependent policy f h ∈ F HD and an initial distribution γ, the expected discounted costs at a discount factor α ∈ (0, 1) are defined as [START_REF] Altman | Constrained Markov Decision Processes[END_REF]

C α (γ, f h ) = (1 -α) ∞ t=0 α t E f h γ c(X t , A t ) = s∈S a∈A(s) g α (γ, f h ; s, a)c(s, a), D k α (γ, f h ) = (1 -α) ∞ t=0 α t E f h γ d k (X t , A t ) = s∈S a∈A(s) g α (γ, f h ; s, a)d k (s, a), for all k = 1, 2, . . . , K, where (1 -α) is a normalization constant. The set {g α (γ, f h ; s, a)} (s,a)
is the occupation measure defined by

g α (γ, f h ; s, a) = (1 -α) ∞ t=0 α t P f h γ (X t = s, A t = a), ∀ (s, a) ∈ K.
For a given history dependent policy f h and an initial distribution γ, the expected average costs are defined as [1]

C ea (γ, f h ) = lim sup n→∞ 1 n n-1 t=0 E f h γ c(X t , A t ) = s∈S a∈A(s) g ea (γ, f h ; s, a)c(s, a), D k ea (γ, f h ) = lim sup n→∞ 1 n n-1 t=0 E f h γ d k (X t , A t ) = s∈S a∈A(s) g ea (γ, f h ; s, a)d k (s, a), for all k = 1, 2, . . . , K. The set {g ea (γ, f h ; s, a)} (s,a
) is an occupation measure obtained from the accumulation points of {{g n ea (γ, f h ; s, a)} (s,a) } n , where

g n ea (γ, f h ; s, a) = 1 n n-1 t=0 P f h γ (X t = s, A t = a), ∀ (s, a) ∈ K.
The optimal policy of a CMDP problem can be obtained by solving the following optimization problem min

f h ∈F HD C v (γ, f h ) s.t. D k v (γ, f h ) ≤ ξ k , ∀ k = 1, 2, . . . , K, (1)
where v = α and v = ea represent a CMDP problem with discounted cost criterion and average cost criterion, respectively.

Assumption 1. For the CMDP problem with average cost criterion, we assume that the CMDP is unichain, i.e., under any stationary deterministic policy, the Markov chain is aperiodic and irreducible (with possibly some transient states) [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Puterman | Markov Decision Process[END_REF].

It is well known that the CMDP problem (1) for v ∈ {α, ea} can be restricted to the class of stationary policies without loss of optimality when the running costs and transition probabilities are stationary, i.e., they depend only on states and actions but time. This follows from the fact that the set of occupation measures defined with respect to history dependent policies and the set of occupation measures defined with respect to stationary policies are equal (see Theorems 3.1 and 4.1 of [START_REF] Altman | Constrained Markov Decision Processes[END_REF]). Moreover, it follows from Theorems 3.2 and 4.2 of [START_REF] Altman | Constrained Markov Decision Processes[END_REF] that the set of occupation measures defined with respect to stationary policies for the discounted cost criterion is equal to the set Q α (γ), and for the average cost criterion it is equal to the set Q ea (γ). For v ∈ {α, ea}, the set Q v (γ) is defined as

Q v (γ) = ρ ∈ R K (s,a)∈K ρ(s, a) δ(s, s ′ ) -ηp(s ′ s, a) = (1 -η)γ(s ′ ), ∀ s ′ ∈ S, (s,a)∈K ρ(s, a) = 1, ρ(s, a) ≥ 0, ∀ (s, a) ∈ K , where δ(s, s ′ ) is the Kronecker delta and η ∈ (0, 1]. If η < 1, we take it as the discount factor α and Q v (γ) = Q α (γ), while if η = 1, Q v (γ) = Q ea (γ). Therefore, the CMDP problem (1) is equivalent to the LP problem min ρ s∈S a∈A(s) ρ(s, a)c(s, a) s.t. s∈S a∈A(s) ρ(s, a)d k (s, a) ≤ ξ k , ∀ k = 1, 2, . . . , K, ρ ∈ Q v (γ). (2)
If ρ * is an optimal solution of (2), the optimal stationary policy f * of the CMDP problem is defined as f * (s, a) = ρ * (s,a) ∑ a∈A(s) ρ * (s,a) for all s ∈ S, a ∈ A(s), provided the denominator is non-zero if it is zero, we choose f * (s) arbitrarily from ℘(A(s)) .

CMDP under chance constraints

In real-life scenario, the model parameters such as running costs and transition probabilities are subject to errors and are not exactly known. In this paper, we assume that the transition probabilities are stationary and exactly known while the running cost vectors c, d k , k = 1, 2, . . . , K, are random vectors defined on a probability space (Ω, F, P). The uncertainty in running costs is stationary in nature, i.e., the random cost vectors c, d k , k = 1, 2, . . . , K, do not vary with time. For a given

f h ∈ F HD , the costs C v (γ, f h ), D k v (γ, f h ), k = 1, 2, .
. . , K, corresponding to the objective function and the constraints are random variables. We consider the case where the controller is interested in the minimum long run expected cost which is incurred with at least p 0 probability, and the random constraints are jointly satisfied with at least p 1 probability. This leads to the following joint chance constraint programming based formulation of the

CMDP problem min t,f h ∈F HD t s.t. P C v (γ, f h ) ≤ t ≥ p 0 , P D k v (γ, f h ) ≤ ξ k , k = 1, 2, . . . , K ≥ p 1 . (3)
We call (3) a joint chance-constrained Markov decision process (JCCMDP) problem.

Proposition 1. The JCCMDP problem (3) can be restricted to the class of stationary policies without loss of optimality. Moreover, it can be equivalently written using the decision vector (t, ρ) as

min t,ρ t s.t. P (s,a)∈K ρ(s, a)c(s, a) ≤ t ≥ p 0 , P (s,a)∈K ρ(s, a)d k (s, a) ≤ ξ k , k = 1, 2, . . . , K ≥ p 1 , ρ ∈ Q v (γ). (4)
If ρ * is a part of an optimal solution vector of (4), the optimal stationary policy f * of the JCCMDP problem is given by f * (s, a) = ρ * (s,a) ∑ a∈A(s) ρ * (s,a) for all s ∈ S, a ∈ A(s), provided the denominator is non-zero if it is zero, we choose f * (s) arbitrarily from ℘(A(s)) .

Proof The proof follows from the fact that the set of occupation measures for history dependent strategies is the same as Qv(γ) as discussed in Section 2.

We consider the case where the running cost vectors c, d k , k = 1, 2 . . . , K, follow multivariate elliptically symmetric distributions and the dependence among the random constraints present under the joint chance constraint of ( 4) is driven by Gumbel-Hougaard copula. We first review a few definitions and results on copulas and elliptical distributions, which will be used in subsequent analysis.

Preliminaries

Definition 1 (Copula [START_REF] Cheng | Chance constrained 0-1 quadratic programs using copulas[END_REF][START_REF] Jaworski | Copula Theory and Its Applications[END_REF][START_REF] Nelsen | An Introduction to Copulas[END_REF]) A K-dimensional copula, where K ≥ 2, is a distribution function on [0, 1] K such that all its one dimensional marginals follow a uniform distribution on [0, 1].

The relation between the joint distribution of a random vector X = (X 1 , X 2 , . . . , X K ) and a copula is given by the Sklar's theorem [START_REF] Nelsen | An Introduction to Copulas[END_REF].

Theorem 1 (Sklar's theorem [START_REF] Nelsen | An Introduction to Copulas[END_REF]). For a given K-dimensional distribution function Φ and all its one dimensional marginals Φ1 , Φ2 , . . . , ΦK , there exists a copula C that satisfies

Φ(v 1 , v 2 , . . . , v K ) = C Φ1 (v 1 ), Φ2 (v 2 ), . . . , ΦK (v K ) , ∀ v 1 , v 2 , . . . , v K ∈ R.
When all the marginals are continuous, C is unique throughout its domain; else it is unique on ⨉ K i=1 Range Φi .

In this paper, we consider a particular class of copulas, namely, the Gumbel-Hougaard family of copulas, denoted by C θ , defined as [START_REF] Cheng | Chance constrained 0-1 quadratic programs using copulas[END_REF] C

θ (u) = exp ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ - K k=1 -ln(u k ) θ 1 θ ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ , (5)
where

u = (u 1 , u 2 , . . . , u K ) T ∈ [0, 1] K and θ ≥ 1. When θ = 1, C 1 (u) = ∏ K k=1
u k is the product copula. The joint distribution function of a random vector X defined by a product copula implies that the random variables X 1 , X 2 , . . . , X K are independent.

Definition 2 (Elliptical distribution [START_REF] Fang | Symmetric Multivariate and Related Distributions[END_REF]) A K-dimensional random vector X is said to follow a multivariate elliptically symmetric distribution if its characteristic function has the form E(e ib T X

) = e ib T µ ϕ(b T Σb), where µ ∈ R K is the location parameter, the matrix Σ ∈ R K×K is the scale parameter and ϕ is the characteristic generator. We denote it as X ∼ E K (µ, Σ, ϕ).

If X ∼ E K (µ, Σ, ϕ) and the density function of X, denoted by φ exists, then it has the form

φ(x) = 1 det(Σ) g (x -µ) T Σ -1 (x -µ) ,
where the scale matrix Σ is positive definite and the function g is the density generator. In such a case, we also write X ∼ E K (µ, Σ, g). From Theorem 2.16 of [START_REF] Fang | Symmetric Multivariate and Related Distributions[END_REF], a linear combination of the components of an elliptically distributed random vector follows a univariate elliptical distribution. Thus, if

X ∼ E K (µ, Σ, ϕ), for a b ∈ R K , b T X ∼ E 1 (b T µ, b T Σb, ϕ). Moreover, if Σ is a positive defi- nite matrix, then b T X-b T µ Σ 1 2 b 2
is a spherically distributed random variable with characteristic generator ϕ.

Second order cone approximations

The deterministic optimization problem equivalent to the JCCMDP problem (4), under certain conditions on random cost vectors c and d k , is given by the following Proposition 2.

Proposition 2. Under the assumptions that (i) the joint distribution of the random vector (ρ T d 1 , ρ T d 2 , . . . , ρ T d K ) T is defined using the Gumbel-Hougaard family of copulas given by (5), and

(ii) c ∼ E K (µ c , Σ c , ϕ), d k ∼ E K (µ d k , Σ d k , ϕ), k = 1, 2, . . . , K, such that Σ c , Σ d k , k = 1, 2, .
. . , K, are positive definite matrices, the JCCMDP problem (4) is equivalent to the following non-linear programming problem

min t,ρ,(y k ) K k=1 t s.t. ρ T µ c + Φ -1 (p 0 ) Σ 1 2 c ρ 2 ≤ t, ρ T µ d k + Φ -1 (p y 1 θ k 1 ) Σ 1 2 d k ρ 2 ≤ ξ k , ∀ k = 1, 2, . . . , K, K k=1 y k = 1, y k ≥ 0, ∀ k = 1, 2, . . . , K, ρ ∈ Q v (γ), (6)
where p 0 , p 1 ∈ (0.5, 1) and Φ -1 (⋅) is the quantile function of a spherical distribution.

Proof The proof follows from Lemma 2 of [START_REF] Peng | Bounds for probabilistic programming with application to a blend planning problem[END_REF] and Lemma 2.2 of [START_REF] Henrion | Structural properties of linear probabilistic constraints[END_REF].

Remark 1. If K = 1, the optimization problem (6) is an SOCP problem which implies that the JCCMDP problem (4) is equivalent to an SOCP problem.

For K ≥ 2, the optimization problem ( 6) is a non-convex optimization problem. We approximate (6) by two SOCP problems whose optimal values give lower and upper bounds on the optimal value of the JCCMDP problem. Our approximations hold under the following assumption. Assumption 2. For each k = 1, 2, . . . , K, the quantile function Φ -1 (p

y 1 θ k 1 ) is a convex function of y k .
For the spherical distributions listed in Table 1, Assumption 2 holds true. This follows from the fact that Φ -1 (p

y 1 θ k 1 ) is a composition of functions p y 1 θ k 1
and Φ -1 (y k ), where former is a convex function of y k ∈ [0, 1] and latter is nondecreasing and convex function of y k ∈ [p 1 , 1]. The convexity of Φ -1 (y k ) for the probability distributions listed in Table 1 can be verified by checking the following condition

(Φ -1 ) ′′ (y) = -φ ′ (Φ -1 (y)) (φ(Φ -1 (y))) 3 ≥ 0, ∀ y ∈ [p 1 , 1),
where φ(⋅) is the corresponding probability density function. The convexity of Φ -1 (y k ) on [p 1 , 1] holds because it is a continuous function at y k = 1. We

Table 1 List of some spherical distributions.

Probability Distribution Density Function (φ(u))

Normal ce

-u 2 2 Pearson Type VII c 1 + u 2 s -N ; N > 1 2 , s > 0 t c 1 + u 2 m -(1+m) 2 ; m > 0 an integer Cauchy c 1 + u 2 s -1 ; s > 0 Logistic ce -u 2 1+e -u 2 2
Laplace ce -u

The constant c > 0 is the normalization factor that ensures the density function gives 1 on integration.

approximate the functions Φ -1 (p

y 1 θ k
1 ), k = 1, 2, . . . , K, using piecewise tangent and linear approximations to obtain two SOCP problems whose optimal values give the lower and upper bounds for the optimal value of (6).

Lower bound approximation

For every k, we approximate the term Φ -1 (p

y 1 θ k 1 ) in (6) by choosing N tangent points y 1 k < y 2 k < . . . < y N k from the interval (0, 1]
. We denote the Taylor series expansion around the point y i k by Φ -1 (p

y 1 θ k
1 ) i and define it as

Φ -1 (p y 1 θ k 1 ) i = Φ -1 (p y i k 1 θ 1 ) + (y k -y i k ) d dy k Φ -1 (p y i k 1 θ 1 ) = Φ -1 (p y i k 1 θ 1 ) - (y i k ) 1 θ p y i k 1 θ 1 ln(p 1 )
θφ(Φ -1 (p

y i k 1 θ 1
))

+ p y i k 1 θ 1 ln(p 1 )(y i k ) 1 θ -1 y k θφ(Φ -1 (p y i k 1 θ 1
))

= āi k + bi k y k , ∀ i = 1, 2, . . . , N,
where āi k = Φ -1 (p

y i k 1 θ 1 ) - (y i k ) 1 θ p y i k 1 θ 1 ln(p 1 ) θφ(Φ -1 (p y i k 1 θ 1
))

, bi k = p y i k 1 θ 1 ln(p 1 )(y i k ) 1 θ -1 θφ(Φ -1 (p y i k 1 θ 1
))

, and φ(⋅) is the probability density function of the spherical distribution whose cumulative distribution function is Φ(⋅).

Theorem 2. Let Assumption 2 holds. The lower bound for the optimal value of the equivalent JCCMDP problem (6) is given by the optimal value of the following SOCP problem

min t,ρ,(x kj ) K k=1, K j=1 ,(z kj ) K k=1, K j=1 t s.t. ρ T µ c + Φ -1 (p 0 ) Σ 1 2 c ρ 2 ≤ t, ρ T µ d k + Σ 1 2 d k z k 2 ≤ ξ k , ∀ k = 1, 2, . . . , K, z kj ≥ (ā i k ρ j + bi k x kj ), ∀ k = 1, 2, . . . , K, j = 1, 2, . . . , K , i = 1, 2, . . . , N, K k=1 x kj = ρ j , ∀ j = 1, 2, . . . , K , x kj ≥ 0, ∀ k = 1, 2, . . . , K, j = 1, 2, . . . , K , ρ ∈ Q v (γ), (7)
where ρ j is the j-th component of ρ ∈ R K and z k = (z kj ) K j=1 for every k = 1, 2, . . . , K.

Proof It is sufficient to show that for every feasible solution of ( 6) there exists a feasible solution of [START_REF] Cheng | Chance constrained 0-1 quadratic programs using copulas[END_REF]. The proof is similar to Theorem 3.1.1 of [START_REF] Cheng | A second-order cone programming approach for linear programs with joint probabilistic constraints[END_REF]. Suppose the vector t, ρ, (y k ) K k=1 is a feasible solution of [START_REF] Cheng | A second-order cone programming approach for linear programs with joint probabilistic constraints[END_REF]. Under Assumption 2, we obtain

Φ -1 (p y 1 θ k 1 ) ≥ max 1≤i≤N (ā i k + bi k y k ) for all k. Therefore, ρ T µ d k + max 1≤i≤N (ā i k + bi k y k ) Σ 1 2 d k ρ 2 ≤ ξ k , ∀ k = 1, 2, . . . , K. The vectors z k , k = 1, 2, . . . K, where z kj = max 1≤i≤N (ā i k ρ j + bi k y k ρ j ) for all k = 1, 2, . . . , K, j = 1, 2, . . . , K , satisfies ρ T µ d k + Σ 1 2 d k z k 2 ≤ ξ k , ∀ k = 1, 2, . . . , K, z kj ≥ āi k ρ j + bi k y k ρ j , ∀ k = 1, 2, . . . , K, j = 1, 2, . . . , K .
Then, the vector t, ρ, (x kj ) K k=1, K j=1 , (z kj ) K k=1, K j=1 where

x kj = y k ρ j , ∀ k = 1, 2, . . . , K, j = 1, 2, . . . , K ,
is a feasible solution for the problem (7).

Upper bound approximation

For every k, we approximate the term Φ -1 (p 6) by choosing N interpolation points y 1 k < y 2 k < . . . < y N k from the interval (0, 1]. We denote the linear interpolating polynomial passing through the points (y i k , Φ -1 (p

y 1 θ k 1 ) in (
) y i+1 k -y i k , bi k = Φ -1 (p y i+1 k 1 θ 1 ) -Φ -1 (p y i k 1 θ 1 ) y i+1 k -y i k .
Theorem 3. Let Assumption 2 holds. The upper bound for the optimal value of the equivalent JCCMDP problem (6) is given by the optimal value of the following SOCP problem

min t,ρ,(y k ) K k=1 ,(z k ) K k=1 t s.t. ρ T µ c + Φ -1 (p 0 ) Σ 1 2 c ρ 2 ≤ t, ρ T µ d k + z k max 1≤j≤ K (Σ 1 2 d k ) j 2 ≤ ξ k , ∀ k = 1, 2, . . . , K, z k ≥ âi k + bi k y k , ∀ k = 1, 2, . . . , K, i = 1, 2, . . . , N -1, K k=1 y k = 1,
y k ≥ 0, ∀ k = 1, 2, . . . , K, ρ ∈ Q v (γ), (8)
where ρ j is the j-th component of ρ ∈ R K and (Σ

1 2 d k ) j is the j-th column of the matrix Σ 1 2 d k .
Proof It is sufficient to show that for every feasible solution of (8) there exists a feasible solution of (6). Suppose the vector t, ρ, (y k ) K k=1 , (z k ) K k=1 is a feasible solution of [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF]. Under Assumption 2, we obtain Φ -1 (p

y 1 θ k 1 ) ≤ max 1≤i≤N -1 (â i k + bi k y k ) for all k. For an arbitrarily fixed k ∈ {1, 2, . . . , K}, consider Σ 1 2 d k ρ 2 = ρ 1 (Σ 1 2 d k ) 1 + ρ 2 (Σ 1 2 d k ) 2 + . . . + ρ K (Σ 1 2 d k ) K 2 ≤ ρ 1 (Σ 1 2 d k ) 1 2 + ρ 2 (Σ 1 2 d k ) 2 2 + . . . + ρ K (Σ 1 2 d k ) K 2 ≤ max 1≤j≤ K (Σ 1 2 d k ) j 2 .
The first inequality holds by triangular inequality of ⋅ 2 , while the second inequality holds by the last two conditions of the set Qv(γ). Consequently, the following inequality holds true

ρ T µ d k + Φ -1 (p y 1 θ k 1 ) Σ 1 2 d k ρ 2 ≤ ρ T µ d k + max 1≤i≤N -1 (â i k + bi k y k ) max 1≤j≤ K (Σ 1 2 d k ) j 2 ≤ ρ T µ d k + z k max 1≤j≤ K (Σ 1 2 d k ) j 2 .
Therefore,

ρ T µ d k + Φ -1 (p y 1 θ k 1 ) Σ 1 2 d k ρ 2 ≤ ξ k , ∀ k = 1, 2, .
. . , K. Hence, the vector t, ρ, (y k ) K k=1 is a feasible solution for the problem (6).

Queueing control problem

We consider a stochastic version of a discrete-time service and admission control problem in a single queue introduced by Altman (see Chapter 5 of [START_REF] Altman | Constrained Markov Decision Processes[END_REF]).

The system has two controllers, namely, service and admission controllers. We consider them as a single controller because their joint objective is to minimize the expected cost incurred in the long run. The states represent the queue length with buffer size L. Thus, S = {0, 1, . . . , L}, where s = 0 indicates that the queue is empty, while s = L indicates that the queue is full. The action set of the controller is A 1 × A 2 , where A 1 and A 2 are finite sets of probability values. If (a 1 , a 2 ) ∈ A 1 × A 2 , then a 1 and a 2 denote the probabilities with which the controller finishes the service and admits a customer into the system, respectively. We assume that A 1 ⊆ [a 1 min , a 1 max ] and A 2 ⊆ [a 2 min , a 2 max ], where 0 < a 1 min ≤ a 1 max < 1 and 0 ≤ a 2 min ≤ a 2 max < 1. Moreover, when s = L, we assume no admission takes place. The transition probabilities from [START_REF] Altman | Constrained Markov Decision Processes[END_REF] are given by

p(s ′ s, (a 1 , a 2 )) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ a 1 (1 -a 2 ) 1 ≤ s ≤ L -1, s ′ = s -1, a 1 a 2 + (1 -a 1 )(1 -a 2 ) 1 ≤ s ≤ L -1, s ′ = s, (1 -a 1 )a 2 0 ≤ s ≤ L -1, s ′ = s + 1, 1 -(1 -a 1 )a 2 s ′ = s = 0, 1 -a 1 s = L, s ′ = L, a 1 s = L, s ′ = L -1.
If at state s ∈ S, the controller chooses an action (a 1 , a 2 ), it incurs running costs c(s), d 1 (a 1 ) and d 2 (a 2 ). The running cost c(s) is the holding cost incurred due to customers waiting in the queue. Therefore, it only depends on the size of the queue. The holding cost is zero for an empty queue, i.e., c(0) = 0. The running cost d 1 (a 1 ) is a service cost incurred when a customer is served with probability a 1 and d 2 (a 2 ) denotes the cost when a customer is not admitted into the system with (1a 2 ) probability. The service cost d 1 (a 1 ) increases with a 1 and no admission cost d 2 (a 2 ) decreases with a 2 . These costs do not depend on the size of the queue. The controller aims to minimize the expected holding cost in the long run by keeping the long run expected service and admission costs below certain threshold values. Usually the costs in the queueing system are not realized before the decisions are taken. Therefore, the running cost vectors c , d 1 and d 2 are better modelled using random vectors. We assume that they follow normal distribution and denote them as c ∼ N (µ c , Σ c ),

d k ∼ N (µ d k , Σ d k ), k = 1, 2, where c = (c(s)) s∈S , d 1 = (d 1 (a 1 )) a 1 ∈A 1 and d 2 = (d 2 (a 2 )) a 2 ∈A 2 .

Numerical experiments

We perform numerical experiments, using CVX package in MATLAB optimization toolbox, on an Intel(R) 64-bit Core(TM) i5-8250U CPU @ 1.60GHz with 8.0 GB RAM machine. In all the numerical experiments, we fix p 0 , p 1 = 0.95, α = 0.99 and assume γ to be a uniformly distributed vector. We consider the case where the number of states are 10, i.e., L = 9, and the controller finishes the service with probability a 1 = 0.75. The admission controller has two possible actions: 'No Admission (a 2 = 0)' or 'Admission with probability 0.8 (a 2 = 0.8)'. We take c, d 2 to be normally distributed random vectors and d 1 to be fixed, thus K = 1. Hence, from Remark 1, it follows that the JCCMDP problem (4) reduces to an SOCP problem. We take ξ 2 = 9, µ c = (0, 1, 2, . . . , 9) T , the matrix Σ c ∈ R 10×10 with all diagonal values 0.9 and off-diagonal values 0.35, and µ d 2 = 10.0 7.60 , Σ d 2 = 0.80 0.24 0.24 0.61 .

The optimal values of the JCCMDP problem with the above data for discounted and average cost cases are 5.7963 and 6.2296, respectively. Figure 1 shows the optimal probability of not admitting a customer into the queue at various states. For both the cases, we conclude that the optimal probability of 'No Admission' is 1 at the last state. We consider a relatively large system where the action set of the controller is given by A 1 × A 2 = {(0.2, 0.75, 0.9), (0, 0.5, 0.8)}. Thus, K = 2, and we compute the lower bound and upper bound for the optimal value of the JCCMDP problem (4) by solving the SOCP problems ( 7) and (8), respectively. For L = n -1 ( S = n), we take µ c = (0, 1, 2, . . . , n -1) T , the matrix Σ c ∈ R n×n with all diagonal values 0.9 and off-diagonal values 0.35, µ d 1 = (4.32, 9.1875, 10.83)

⎞ ⎟ ⎠

.

The mean vector µ c , where µ c (s) = s, captures the fact that the holding cost increases with s. We take the mean vectors µ d 1 and µ d 2 such that µ d 1 (a 1 ) = 3(1 + a 1 ) 2 and µ d 2 (a 2 ) = 10 -3a 2 . It is motivated from the fact that the service cost increases with a 1 and no admission cost decreases with a 2 . We take ξ 1 = 11.30, ξ 2 = 11.35, the sets of tangent and linear points are {0.01, 0.15, 0.45} and {10 -5 , 10 -3 , 0.15, 1}, respectively, such that the interpolation point y 1 k is sufficiently close to 0. We solve the SOCP problems ( 7) and ( 8) for various values of θ and S . The higher values of θ indicates stronger dependence between the random vectors d 1 (a 1 ) and d 2 (a 2 ) driven by Gumbel-Hougaard copula. The numerical results are summarized in Tables 2 and3 for the case of discounted and average cost criteria, respectively. The lower bound and upper bound for the optimal value of JCCMDP problem is given in column 3 and column 5 of each table, respectively. The computational time to solve [START_REF] Cheng | Chance constrained 0-1 quadratic programs using copulas[END_REF] and ( 8) is given in columns 4 and 6, respectively. The last column of both the Tables represent the gap between the upper and lower bound for the optimal value of the JCCMDP problem (4), where the gap is defined by It is clear from Tables 2 and3 that in most of the cases the gap is very small. Only in a few instances it goes up to 2.15%. This shows that the SOCP problems ( 7) and ( 8) are good approximations of the JCCMDP problem. The time analysis shows that the SOCP problems ( 7) and ( 8) can be solved efficiently.

Conclusion

We consider a CMDP problem with random costs under discounted and average cost criteria. We formulate it as a joint chance-constrained optimization problem where the dependence among the random cost constraint vectors is driven by a Gumbel-Hougaard copula. When the random cost vectors follow multivariate elliptically symmetric distributions, we propose SOCP based approximations which give upper and lower bounds on the optimal value of the JCCMDP problem. We illustrate our results on a queueing control problem by considering various small and large instances. The gap between the upper and lower bounds is very small in most of our experiments which shows the effectiveness of the SOCP approximations. The time analysis shows that both the approximations can be solved efficiently for large instances.

Gap

  1 , a 1 , . . . , s t-1 , a t-1 , s t ) at time t. Let H t be the set of all possible histories at time t. A history dependent decision rule f t at time t is a function f t ∶ H t → ℘(A), where for every h t ∈ H t with final state s t , f t (h t ) ∈ ℘(A(s t )). A sequence of history dependent decision rules f h = (f t ) ∞ t=0 is called a history dependent policy. When each f t in the sequence (f t ) ∞ t=0 depends only on the state at time t, it is called a Markovian policy. A Markovian policy (f t ) ∞

  The solid lines marked with ′ * ′ and ′ o ′ denote the optimal probability of not admitting a customer into the queue for discounted and average cost problems, respectively.

			1
			0.9
		Optimal probability of No admission	0.2 0.3 0.4 0.5 0.6 0.7 0.8
			0.1
			0
			0	1	2	3		4	5	6	7	8	9
								States
	Fig. 1 µ d 2 = (10.00, 8.50, 7.60) T , and
	Σ d 1 =	⎛ ⎜ ⎝ 0.15 0.05 0.10 0.05 0.10 0.15 0.10 0.15 0.40	⎞ ⎟ ⎠	, Σ d 2 =	0.80 0.35 0.24 ⎛ 0.35 0.70 0.20 ⎜ ⎝ 0.24 0.20 0.61

T ,

Table 2

 2 Lower and Upper bounds for Discounted cost case.

	θ	States	Lower Bound (LB)	Upper Bound (UB)	Gap(%)
			Opt.	CPU(s)	Opt.	CPU(s)
		200	47.3240	15.4219	47.3260	10.1875	0.0042
	1	400	131.2503	57.1094	131.3343	23.1094	0.0639
		600	224.7818	142.8438	229.3581	72.2656	2.0358
		800	322.1396	347.7031	329.0680	161.7188	2.1507
		200	47.3247	14.8125	47.3260	5.2500	0.0027
	3	400	131.2513	53.8281	131.2536	23.2500	0.0017
		600	224.7558	142.5938	224.8627	52.2031	0.0475
		800	321.4530	312.4063	323.9796	176.6094	0.7859
		200	47.3250	13.0938	47.3260	5.0313	0.0021
	6	400	131.2518	49.5313	131.2533	19.4688	0.0011
		600	224.7562	140.2188	224.7802	47.6250	0.0106
		800	321.4326	314.4531	322.6907	158.7344	0.3914

Table 3

 3 Lower and Upper bounds for Average cost case.

	θ	States	Lower Bound (LB)	Upper Bound (UB)	Gap(%)
			Opt.	CPU(s)	Opt.	CPU(s)
		200	1.5604	19.3438	1.5607	10.8906	0.0192
	1	400	1.5604	61.9531	1.5607	26.1875	0.0192
		600	1.5604	166.5781	1.5607	64.7344	0.0192
		800	1.5604	340.1719	1.5607	120.9219	0.0192
		200	1.5605	15.5625	1.5607	5.9688	0.0128
	3	400	1.5605	53.3750	1.5607	29.7344	0.0128
		600	1.5605	156.7969	1.5607	71.3594	0.0128
		800	1.5605	287.0469	1.5607	131.2813	0.0128
		200	1.5606	18.2188	1.5607	9.8750	0.0064
	6	400	1.5606	56.7344	1.5607	24.6563	0.0064
		600	1.5606	150.8281	1.5607	61.7656	0.0064
		800	1.5606	276.4063	1.5607	135.9844	0.0064

Acknowledgement

The research of first author was supported by CSIR, India. The research of second and third author was supported by DST/CEFIPRA Project No. IFC/4117/DST-CNRS-5th call/2017-18/2 and CNRS Project No. AR/SB:2018-07-440, respectively.