Nam Hoang

Nguyen

Abdel Lisser
email: abdel.lisser@centralesupelec.fr

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

Random games under normal mean-variance mixture distributed independent linear joint chance constraints

Keywords: Chance-constrained game, Normal mean-variance mixture, Nash equilibrium 2000 MSC: 90C15, 90C25, 90C59

In this paper, we study an 𝑛 player game where the payoffs as well as the strategy sets are defined using random variables. The payoff function of each player is defined using expected value function and his/her strategy set is defined using a linear joint chance constraint. The random constraint vectors defining the joint chance constraint are independent and follow normal mean-variance mixture distributions. For each player, we reformulate the joint chance constraint in order to prove the existence of a Nash equilibrium using the Kakutani fixed-point theorem under mild assumptions. We illustrate our theoretical results by considering a game between two competing firms in financial market.

Introduction

In 1950, Nash [START_REF] Jr | Equilibrium points in n-person games[END_REF] showed that there exists a mixed strategy equilibrium point in any finite strategic game, which is called Nash equilibrium nowadays. In [START_REF] Jr | Equilibrium points in n-person games[END_REF], the players' payoffs and strategy sets are deterministic, which are not suitable in real life applications. We can deal with the randomness in the players' payoffs in at least two different ways. First, the expectation value of the random payoffs of the players [START_REF] Ravat | On the characterization of solution sets of smooth and nonsmooth convex stochastic Nash games[END_REF] often used for risk neutral games. Second, the risk measure CVaR [START_REF] Kannan | Addressing supply-side risk in uncertain power markets: stochastic Nash models, scalable algorithms and error analysis[END_REF] and the chance constraint optimization framework [START_REF] Vikas | Existence of Nash equilibrium for chance-constrained games[END_REF]Singh and Lisser, 2018) used as an alternative payoff criterion. A natural way to deal with random constraints in the strategy sets is to replace them with chance constraints which is quite popular in real life applications, e.g., risk constraints in portfolio optimization [START_REF] Ji | Risk-budgeting multi-portfolio optimization with portfolio and marginal risk constraints[END_REF], resource constraints in stochastic shortest path problem [START_REF] Cheng | A second-order cone programming approach for linear programs with joint probabilistic constraints[END_REF], renewable energy aggregators in the local market [START_REF] Li | A risk-averse energy sharing market game for renewable energy microgrid aggregators[END_REF]. The games involving chance constraint either in payoffs or in strategy sets are called chance-constrained games (CCGs). Several studies exist in the literature on chance-constrained games, e.g., [START_REF] Vikas | Existence of Nash equilibrium for chance-constrained games[END_REF] showed the existence of Nash equilibrium for the case where the payoff vector is elliptically distributed. Also, (Singh and Lisser, 2018) showed the equivalence between Nash equilibrium of a CCG and the global optimal solution of a mathematical program. The CCGs where strategy sets are defined using individual/joint chance constraint have been widely studied in the literature [START_REF] Peng | General sum games with joint chance constraints[END_REF][START_REF] Peng | Chance-constrained games with mixture distributions[END_REF][START_REF] Vikas | A second-order cone programming formulation for two player zero-sum games with chance constraints[END_REF]Singh et al., 2021;[START_REF] Hoang | Random games under elliptically distributed dependent joint chance constraints[END_REF].

To the best of our knowledge, the random constraint vectors in the CCGs are often assumed to be elliptically distributed or follow a mixture of elliptical distributions. These families include many known distributions, e.g., Normal distributions, t-distributions, Laplace distributions, Kotz-type distributions, Pearson distributions. However, it is interesting to consider different distributions for the constraint vectors since these families of distributions are not suitable for some practical situations. In power system scheduling problems, both wind power forecast errors and load forecasting errors can be better fitted by generalized hyperbolic (GH) distributions [START_REF] Hodge | Comparison of wind power and load forecasting error distributions[END_REF], which are neither elliptically distributed nor a mixture of elliptical distributions. This family belongs to a more general family of distributions, namely normal mean-variance mixture, which is often used to model many financial applications [START_REF] Eberlein | The generalized hyperbolic model: Financial derivatives and risk measures[END_REF][START_REF] Bauer | Value at risk using hyperbolic distributions[END_REF][START_REF] Todorov | Handbook of Heavy Tailed Distributions in Finance: Handbooks in Finance[END_REF][START_REF] Rostislav | Em-based maximum likelihood parameter estimation for multivariate generalized hyperbolic distributions with fixed 𝜆[END_REF]. In this paper, we study an 𝑛 player CCG where the players' payoffs are defined using the expectation value and the strategy set of each player is defined by a joint chance constraint. We assume that the random constraint vectors are independent and follow normal mean-variance mixture distributions which generalize the family of GH distributions [START_REF] Barndorff-Nielsen | Normal variance-mean mixtures and z distributions[END_REF]. We derive a new reformulation of the joint chance constraint and show that there exists a Nash equilibrium under mild assumptions, by proving the convexity of the feasible strategy set of each player. In [START_REF] Hoang | Convexity conditions for normal mean-variance mixture distribution in joint probabilistic constraints[END_REF], the authors give some sufficient conditions under which joint chance constraint is convex when the constraint vectors are independent and follow normal mean-variance mixture distribution. In this paper, we relax those conditions and provide a lower bound on the probability level vector for which the joint chance constraint is convex. As an application of these games we study a competition between two firms in a financial market and compute its Nash equilibria using a best response algorithm.

The remainder of this paper is organized as follows. In Section 2, we introduce the game model and some basic concepts used in the paper. In Section 3, we show the existence of a Nash equilibrium. In section 4, we illustrate our theoretical results using a game between two firms from a financial market. We conclude the paper in Section 5.

The Game Model and Basic Concepts

Game Model

In this section, we define a chance-constrained game model. Let 𝐻 = {1, 2, .., 𝑛} be the set of players and 𝑆 𝑖 be the strategy set of player 𝑖 ∈ 𝐻 which is assumed to be a non-empty, convex and compact subset of R 𝑑 𝑖 . The set 𝑆 = 𝑛 𝑖=1 𝑆 𝑖 is called the set of strategy profiles of the game. For any player 𝑖 ∈ 𝐻, a strategy profile 𝑥 = (𝑥 1 , 𝑥 2 , . . . , 𝑥 𝑛 ) ∈ 𝑆 can be written as (𝑥 𝑖 , 𝑥 -𝑖 ), where 𝑥 𝑖 ∈ 𝑆 𝑖 and 𝑥 -𝑖 ∈ 𝑆 -𝑖 . Here, 𝑆 -𝑖 denote the set of vectors of strategies of all players, except player 𝑖. We consider the case where the strategies of each player 𝑖 further satisfy the following joint chance constraint

P(𝑉 𝑖 𝑥 𝑖 ≤ 𝐷 𝑖 ) ≥ 𝛼 𝑖 , (1)
where 𝛼 𝑖 is a real number defined in [0, 1], 𝐷 𝑖 = (𝐷 𝑖,1 , . . . , 𝐷 𝑖,𝐾 𝑖 ) ⊤ ∈ R 𝐾 𝑖 is a real vector and 𝑉 𝑖 = [𝑉 𝑖,1 , . . . , 𝑉 𝑖,𝐾 𝑖 ] ⊤ is a 𝐾 𝑖 × 𝑑 𝑖 random matrix, 𝑉 𝑖,𝑘 is the 𝑘 th row of 𝑉 𝑖 and ⊤ denotes the transposition. Let 𝐽 𝑖 = {1, 2, . . . , 𝐾 𝑖 } be the index set of 𝑖 th player's constraints. Then, for any 𝑖 ∈ 𝐻, the feasible strategy set 𝑆 𝑖 𝛼 𝑖 of player 𝑖 is the set of all 𝑥 𝑖 ∈ 𝑆 𝑖 such that 𝑥 𝑖 satisfies the chance constraint (1). We assume that for each 𝑖 ∈ 𝐻, 𝑆 𝑖 𝛼 𝑖 is a non-empty set. Let 𝛼 = (𝛼 𝑖 ) 𝑖 ∈ 𝐻 and 𝑆 𝛼 = 𝑛 𝑖=1 𝑆 𝑖 𝛼 𝑖 be the set of all feasible strategy profiles. For each feasible strategy profile 𝑥 ∈ 𝑆 𝛼 , we assume that player 𝑖 gains a random payoff given by 𝑘 𝑖 (𝑥, 𝜁), where 𝜁 is an 𝑚-dimensional random vector. We define the payoff function of player 𝑖 by taking the expected value of the random payoff given by

𝑝 𝑖 (𝑥) = E[𝑘 𝑖 (𝑥, 𝜁)], ∀ 𝑥 ∈ 𝑆 𝛼 .
The tuple (𝑆 𝑖 𝛼 𝑖 , 𝑝 𝑖 ) 𝑖 ∈ 𝐻 is called a CCG. We assume that the CCG is of complete information, i.e., the vector 𝛼, the payoff function 𝑝 𝑖 and the feasible strategy set 𝑆 𝑖 𝛼 𝑖 for all 𝑖 ∈ 𝐻, are known to all the players. Nash equilibrium is commonly used stability notion for non-cooperative games. For the CCG, a strategy profile 𝑧 * is said to be a Nash equilibrium at given confidence level vector 𝛼 if for any player 𝑖 ∈ 𝐻, the following inequality holds

𝑝 𝑖 (𝑧 𝑖 * , 𝑧 -𝑖 * ) ≥ 𝑝 𝑖 (𝑥 𝑖 , 𝑧 -𝑖 * ), ∀ 𝑥 𝑖 ∈ 𝑆 𝑖 𝛼 𝑖 .
The proof of the existence of a Nash equilibrium for a non-cooperative game is mostly done in the literature using fixed point theorems. In this paper, we use the Kakutani fixed-point theorem, which requires the payoff function of each player 𝑖 to be a continuous function with respect to the strategies of all the players and a concave function with respect to their strategies, where the strategies of other players are fixed, for any player 𝑖 ∈ 𝐻. [START_REF] Peng | Chance-constrained games with mixture distributions[END_REF] show that under the following assumption, the abovementioned properties hold.

Assumption 1. For each player 𝑖 ∈ 𝐻, the following conditions hold: (i) 𝑘 𝑖 (•, 𝑥 -𝑖 , 𝜁) is concave of 𝑥 𝑖 , for every

(𝑥 -𝑖 , 𝜁) ∈ 𝑆 -𝑖 × R 𝑚 , (ii) 𝑘 𝑖 (•) is continuous, (iii) 𝑝 𝑖 (𝑥) < ∞, for every 𝑥 ∈ 𝑆.

Basic Concepts

In this section, we present some basic definitions, which are useful in the paper.

Definition 1. The function 𝑓 : R → R, is said to be an 𝑟-decreasing function for some real number 𝑟 ∈ R, if 𝑓 is continuous on (0, +∞) and there exists some strictly positive real number 𝑡 * such that the function 𝑡 ↦ → 𝑡 𝑟 𝑓 (𝑡) is strictly decreasing on (𝑡 * , +∞).

Definition 2. Let 𝑄 be a convex subset of R 𝑠 and 𝑓 : 𝑄 → (0, +∞). For a real number 𝑟 ∈ (-∞, +∞), 𝑓 is said to be 𝑟-concave on 𝑄 if for any 𝑥, 𝑦 ∈ 𝑄 and 𝛼 ∈ [0, 1],

𝑓 (𝛼𝑥 + (1 -𝛼)𝑦) ≥ [𝛼 𝑓 (𝑥) 𝑟 + (1 -𝛼) 𝑓 (𝑦) 𝑟 ] 1 𝑟 , if 𝑟 ≠ 0, 𝑓 (𝛼𝑥 + (1 -𝛼)𝑦) ≥ 𝑓 (𝑥) 𝛼 𝑓 (𝑦)
𝑈 d = 𝜇 + 𝛾𝑊 + √ 𝑊Σ 1 2 𝑍,
where: (i) 𝑍 is an 𝑛-dimension standard Gaussian distribution with mean vector 𝜇 𝑍 = 0 and covariance matrix Σ 𝑍 = I 𝑛 , where I 𝑛 is the 𝑛 × 𝑛 identity matrix.

(ii) 𝑊 is a positive random variable with a density function independent of 𝑍.

(iii) Σ ∈ R 𝑛×𝑛 is an 𝑛 × 𝑛 positive definite matrix and Σ 1 2 ∈ R 𝑛×𝑛 is an 𝑛 × 𝑛 matrix such that Σ 1 2 (Σ 1
2 ) ⊤ = Σ. (iv) 𝜇 and 𝛾 are 𝑛-dimensional real vectors and d = implies that the both sides have the same distribution.

Normal mean-variance mixture distribution can be used to model chance-constraints due to its flexibility, robustness, scalability, optimization capabilities, and simulation abilities [START_REF] Naderi | Robust mixture regression modeling based on the normal mean-variance mixture distributions[END_REF][START_REF] Lee | On mean and/or variance mixtures of normal distributions[END_REF]. In the following section, we study the existence of a Nash equilibrium of the CCG where the random constraint vectors follow normal mean-variance mixture distributions.

Existence of Nash Equilibrium

For each player 𝑖 ∈ 𝐻, we assume that the row vectors of 𝑉 𝑖 follow normal mean-variance mixture distributions, i.e., 𝑉 𝑖,𝑘 ∼ NMVM(𝜇 𝑖,𝑘 , 𝛾 𝑖,𝑘 , Σ 𝑖,𝑘 , 𝑊 𝑖,𝑘 ) for all 𝑘 ∈ 𝐽 𝑖 . Moreover, the row vectors {𝑉 𝑖,𝑘 | 𝑘 ∈ 𝐽 𝑖 } are mutually independent and the support of 𝑊 𝑖,𝑘 is an open interval (𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ), where 0 < 𝑤 𝑖,𝑘

l ≤ 𝑤 𝑖,𝑘 u < ∞. Let S𝑖 𝛼 𝑖 = 𝑆 𝑖 𝛼 𝑖 \ {0}, then for 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 , let 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) = -(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 √ 𝑊 𝑖,𝑘 + 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ 𝑊 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 , 𝜉 𝑖,𝑘 (𝑥 𝑖 ) = 𝑍 ⊤ ((Σ 𝑖,𝑘 ) 1 2 ) ⊤ 𝑥 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 , (2)
where 𝑍 refers to Definition 3. It is well known that 𝜉 𝑖,𝑘 (𝑥 𝑖 ) follows 1-dimensional standard Gaussian distribution [START_REF] Fang | Symmetric multivariate and related distributions[END_REF], for any 𝑖 ∈ 𝐻 and 𝑘 ∈ 𝐽 𝑖 . Using the independence of the row vectors 𝑉 𝑖,𝑘 , the constraint (1) can be written as 𝑘 ∈ 𝐽 𝑖 P (𝑉 𝑖,𝑘 ) ⊤ 𝑥 𝑖 ≤ 𝐷 𝑖,𝑘 ≥ 𝛼 𝑖 , which implies that

𝑘 ∈ 𝐽 𝑖 P 𝑊 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + √ 𝑊 𝑖,𝑘 𝑍 ⊤ ((Σ 𝑖,𝑘 ) 1 2 ) ⊤ 𝑥 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ≤ 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ≥ 𝛼 𝑖 . (3)
Using the notations in (2), we rewrite (3) as follows

𝑘 ∈ 𝐽 𝑖 P 𝜉 𝑖,𝑘 (𝑥 𝑖 ) ≤ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≥ 𝛼 𝑖 . (4)
Using the independence between 𝑉 𝑖,𝑘 , the constraint (4) can be reformulated as

𝑘 ∈ 𝐽 𝑖 E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≥ 𝛼 𝑖 , (5)
or equivalently

∑ 𝑘 ∈ 𝐽 𝑖 log E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≥ log(𝛼 𝑖 ), (6)
where Φ be the cumulative distribution function of an 1-dimensional standard Gaussian distribution. The main idea for the proof of the existence of Nash equilibrium is based on the Kakutani fixed-point theorem, which requires the convexity of the feasible strategy set 𝑆 𝑖 𝛼 𝑖 . We show that there exists a real number 𝛼 𝑖 , 𝑗 = 1, 2, 3, are given by

𝛼 (1) 𝑖 = max 𝑘 ∈ 𝐽 𝑖 Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u . 𝛼 (2) 𝑖 = max 𝑘 ∈ 𝐽 𝑖 Φ 4 √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l . 𝛼 (3) 𝑖 = max 𝑘 ∈ 𝐽 𝑖 Φ √ 3𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l ,
where || • || 2 denotes the Euclidean norm and 𝜆 𝑖,𝑘,min is the smallest eigenvalue of the positive definite matrix Σ 𝑖,𝑘 .

Lemma 1. Let Assumption 2 hold. Assume that 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 , for all 𝑖 ∈ 𝐻. Then, 𝐷 𝑖,𝑘 > (𝜇 𝑖,𝑘 ) ⊤ 𝑥 𝑖 , for all 𝑖 ∈ 𝐻 and 𝑘 ∈ 𝐽 𝑖 .

Proof. For each 𝑖 ∈ 𝐻, let 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 . Since E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ∈ [0, 1] and 𝛼 𝑖 > 𝛼 (1) 𝑖 , for any 𝑘 ∈ 𝐽 𝑖 , the constraint (5) implies that

E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) > 𝛼 (1)
𝑖 . It follows from the definition of 𝑔 𝑖,𝑘 in (2) that

E 𝑊 𝑖,𝑘 Φ -(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 √ 𝑊 𝑖,𝑘 + 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ 𝑊 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 > 𝛼 (1) 𝑖 . (7)
Due to the following three inequalities

(i) |(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 | ≤ ||𝑥 𝑖 || 2 ||𝛾 𝑖,𝑘 || 2 , (ii) √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ≥ √ 𝜆 𝑖,𝑘,min ||𝑥 𝑖 || 2 , (iii) √ 𝑊 𝑖,𝑘 ≤ √ 𝑤 𝑖,𝑘 u , (8)
we deduce that

-(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 √ 𝑊 𝑖,𝑘 ≤ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u . (9)
From ( 7) and ( 9), by applying the increasing monotonicity of Φ, we get

E 𝑊 𝑖,𝑘 Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ 𝑊 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 > 𝛼 (1) 𝑖 .
It is clear from the definition of 𝛼 (1)

𝑖

in Assumption 2 that the following condition holds

𝛼 (1) 𝑖 ≥ Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u ,
which in turn implies that

E 𝑊 𝑖,𝑘 Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ 𝑊 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 > Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u . ( 10
)
If 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 ≤ 0, using the increasing monotonicity of Φ and (10), we get

E 𝑊 𝑖,𝑘 Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u > Φ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u , which gives a contradiction. Therefore, 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 > 0. □ Lemma 2. For 𝑖 ∈ 𝐻, let 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 . Then, for any 𝑘 ∈ 𝐽 𝑖 and 𝑧 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ],
we have

E 𝑊 𝑖,𝑘        Φ √ 𝑧 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        ≥ 𝛼 𝑖 . Proof. For 𝑖 ∈ 𝐻 and 𝑘 ∈ 𝐽 𝑖 , let 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 and 𝑧 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ]. It is clear from the definition of 𝑔 𝑖,𝑘 in (2) that the following condition holds for any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ] 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) = √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 𝑧 𝑖,𝑘 -𝑊 𝑖,𝑘 √ 𝑊 𝑖,𝑘
.

By applying the inequalites (i) -(iii) of ( 8) and the fact that |𝑧 𝑖,𝑘 -𝑊 𝑖,𝑘 | ≤ 𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l , we deduce the following inequality

(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 𝑧 𝑖,𝑘 -𝑊 𝑖,𝑘 √ 𝑊 𝑖,𝑘 ≤ ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l which in turn implies that 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≤ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l , ∀ 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ]. (11)
Taking the expectation value E 𝑊 𝑖,𝑘 (Φ(•)) on both sides of (11), we get

E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≤ E 𝑊 𝑖,𝑘        Φ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l       
.

Since E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ∈ [0, 1], for any 𝑘 ∈ 𝐽 𝑖 , the constraint (5) implies that

E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ≥ 𝛼 𝑖 ,
which in turn implies that

E 𝑊 𝑖,𝑘        Φ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        ≥ 𝛼 𝑖 . □ Lemma 3. Let Assumption 2 hold. Then, for all 𝑖 ∈ 𝐻 Conv( S𝑖 𝛼 𝑖 ) ⊂ 𝑘 ∈ 𝐽 𝑖 Ω 𝑖,𝑘 ,
where Conv represents the convex hull and

Ω 𝑖,𝑘 =                      𝑥 𝑖 ∈ 𝑆 𝑖 -(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 √ 𝑊 𝑖,𝑘 + 𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 √ 𝑊 𝑖,𝑘 ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min 1 √ 𝑤 𝑖,𝑘 l > 4 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 , ∀ 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ].                      , ( 12
) Proof. For 𝑖 ∈ 𝐻, let 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 . It follows from Lemma 2 that for any 𝑧 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ] E 𝑊 𝑖,𝑘        Φ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        ≥ 𝛼 𝑖 . (13)
Since 𝛼 𝑖 > 𝛼 (2) 𝑖 , the constraint (13) implies that

E 𝑊 𝑖,𝑘        Φ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        > 𝛼 (2) 𝑖 .
It follows from the definition of 𝛼 (2)

𝑖

in Assumption 2 that the following condition holds

𝛼 (2) 𝑖 ≥ Φ        4 √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        .
which in turn implies that

E 𝑊 𝑖,𝑘        Φ √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        > Φ        4 √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        . ( 14
)
If 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) ≤ 0, the constraint ( 14) implies that

Φ ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l > Φ        4 √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l       
, which derives a contradiction due to the increasing monotonicity of Φ. Therefore, 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) > 0. Then, the following inequality holds for any

𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ] √ 𝑧 𝑖,𝑘 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) ≤ √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ). ( 15
)
It follows from ( 14) and ( 15) that

Φ √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 𝑖,𝑘 ) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l > Φ        4 √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        . ( 16
)
By applying the increasing monotonicity of Φ, ( 16) is equivalent to the following inequality 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑧 Proof.

For 𝑥 𝑖 ∈ 𝑄 𝑖 and 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], let 𝑓 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) = 1 (𝑔 𝑖,𝑘 ( 𝑥 𝑖 ,𝑊 𝑖,𝑘 )) 2 . It follows from the definition of 𝑔 𝑖,𝑘 in (2) that 𝑓 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) = ((𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ).𝑀 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) -1 , where 𝑀 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) = 𝑊 𝑖,𝑘 [(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 ] 2 + 1 𝑊 𝑖,𝑘 [𝐷 𝑖,𝑘 -(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 ] 2 + 2[(𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 ] [(𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷 𝑖,𝑘 ].
In order to simplify the notation, for the rest of the proof, we write 𝑀 𝑖,𝑘 (resp. 𝑓 𝑖,𝑘 ) instead of 𝑀 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) (resp.

𝑓 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 )). It is clear that the (-2)concavity of 𝑔 𝑖,𝑘 is equivalent to the convexity of 𝑓 𝑖,𝑘 on 𝑄 𝑖 . In order to prove the convexity of 𝑓 𝑖,𝑘 , we prove that the Hessian matrix of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 is positive semidefinite on 𝑄 𝑖 , for any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ]. Let ∇ 𝑥 𝑖 𝑓 𝑖,𝑘 be the gradient vector of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 and 𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 be the Hessian matrix of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 . Let ℎ(𝑥 𝑖 ) = (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 . The gradient vector of ℎ is given as follows

∇ 𝑥 𝑖 ℎ(𝑥 𝑖 ) = 2Σ 𝑖,𝑘 𝑥 𝑖 ,
and the gradient vector of 𝑀 𝑖,𝑘 with respect to 𝑥 𝑖 is given as follows

∇ 𝑥 𝑖 𝑀 𝑖,𝑘 = 2[𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + (𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷 𝑖,𝑘 ]. 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 .
Since 𝑓 𝑖,𝑘 = ℎ(𝑥 𝑖 ).𝑀 -1 𝑖,𝑘 , the gradient vector of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 can be written as follows

∇ 𝑥 𝑖 𝑓 𝑖,𝑘 = ∇ 𝑥 𝑖 ℎ(𝑥 𝑖 ).𝑀 -1 𝑖,𝑘 + ℎ(𝑥 𝑖 ).∇ 𝑥 𝑖 (𝑀 -1 𝑖,𝑘 ).
We can write 𝑀 -1 𝑖,𝑘 = 𝑢 • 𝑀 𝑖,𝑘 , where 𝑢(𝑥) = 1 𝑥 . By the chain rule of composite function in calculus, the gradient vector of 𝑀 -1 𝑖,𝑘 is given by

∇ 𝑥 𝑖 (𝑀 -1 𝑖,𝑘 ) = 𝑢 ′ (𝑀 𝑖,𝑘 ).∇ 𝑥 𝑖 𝑀 𝑖,𝑘 = -1 𝑀 2 𝑖,𝑘 .2[𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + (𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷 𝑖,𝑘 ]. 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ,
which in turn implies that, for any

(𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ∈ 𝑄 𝑖 × [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ] ∇ 𝑥 𝑖 𝑓 𝑖,𝑘 = 2𝑀 -1 𝑖,𝑘 Σ 𝑖,𝑘 𝑥 𝑖 -2𝑀 -2 𝑖,𝑘 .ℎ(𝑥 𝑖 ).[𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + (𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷 𝑖,𝑘 ]. 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 . (19)
Note that the Hessian matrix of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 can be written equivalently as follows

𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 = ∇ 𝑥 𝑖 ∇ 𝑥 𝑖 𝑓 𝑖,𝑘 ⊤ .
Then, it suffices to derive the term on the right of ( 19) by 𝑥 𝑖 . Let 𝑣(𝑥) = 1 𝑥 2 , 𝑟 (𝑥 𝑖 ) = Σ 𝑖,𝑘 𝑥 𝑖 , 𝑠(𝑥 𝑖 ) = 𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + (𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷 𝑖,𝑘 , then the gradient vector of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 is given by

∇ 𝑥 𝑖 𝑓 𝑖,𝑘 = 2.𝑀 -1 𝑖,𝑘 .𝑟 (𝑥 𝑖 ) -2.𝑣 • 𝑀 𝑖,𝑘 .ℎ(𝑥 𝑖 ).𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 . (20)
Using (20), we get the Hessian matrix as

𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 =2.∇ 𝑥 𝑖 (𝑀 -1 𝑖,𝑘 ).[𝑟 (𝑥 𝑖 )] ⊤ + 2.𝑀 -1 𝑖,𝑘 .∇ 𝑥 𝑖 𝑟 (𝑥 𝑖 ) -2.𝑣 • 𝑀 𝑖,𝑘 .ℎ(𝑥 𝑖 ).∇ 𝑥 𝑖 𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ -2.∇ 𝑥 𝑖 (𝑣 • 𝑀 𝑖,𝑘 ).ℎ(𝑥 𝑖 ).𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ -2.𝑣 • 𝑀 𝑖,𝑘 ∇ 𝑥 𝑖 ℎ(𝑥 𝑖 ).𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ =𝐴 + 𝐵 + 𝐶 + 𝐷 + 𝐸,
where

𝐴 = 2.∇ 𝑥 𝑖 (𝑀 -1 𝑖,𝑘 ).[𝑟 (𝑥 𝑖 )] ⊤ , 𝐵 = 2.𝑀 -1 𝑖,𝑘 .∇ 𝑥 𝑖 𝑟 (𝑥 𝑖 ), 𝐶 = -2.𝑣 • 𝑀 𝑖,𝑘 .ℎ(𝑥 𝑖 ).∇ 𝑥 𝑖 𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ , 𝐷 = -2.∇ 𝑥 𝑖 (𝑣 • 𝑀 𝑖,𝑘 ).ℎ(𝑥 𝑖 ).𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ , 𝐸 = -2.𝑣 • 𝑀 𝑖,𝑘 .∇ 𝑥 𝑖 ℎ(𝑥 𝑖 ).𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ .
We can verify that the following equations hold

(i) ∇ 𝑥 𝑖 (𝑀 -1 𝑖,𝑘 ) = -1 𝑀 2 𝑖,𝑘 .2𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 , ∇ 𝑥 𝑖 𝑟 (𝑥 𝑖 ) = Σ 𝑖,𝑘 , (ii) ∇ 𝑥 𝑖 𝑠(𝑥 𝑖 ) = 𝑊 𝑖,𝑘 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 , ∇ 𝑥 𝑖 ℎ(𝑥 𝑖 ) = 2Σ 𝑖,𝑘 𝑥 𝑖 (iii) ∇ 𝑥 𝑖 (𝑣 • 𝑀 𝑖,𝑘 ) = 𝑣 ′ (𝑀 𝑖,𝑘 ).∇ 𝑥 𝑖 𝑀 𝑖,𝑘 = -2 𝑀 3 𝑖,𝑘
.2[𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ 𝛾 𝑖,𝑘 + (𝑥 𝑖 ) ⊤ 𝜇 𝑖,𝑘 -𝐷

⊤

. Therefore, the Hessian matrix of 𝑓 𝑖,𝑘 with respect to 𝑥 𝑖 can be rewritten as

𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 =𝐴 + 𝐵 + 𝐶 + 𝐷 + 𝐸 = -4𝑠(𝑥 𝑖 ) 𝑀 2 𝑖,𝑘 1 𝑊 𝑖,𝑘 Σ 𝑖,𝑘 𝑥 𝑖 (𝜇 𝑖,𝑘 ) ⊤ + 1 𝑊 𝑖,𝑘 𝜇 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 + Σ 𝑖,𝑘 𝑥 𝑖 (𝛾 𝑖,𝑘 ) ⊤ + 𝛾 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 + 2 𝑀 𝑖,𝑘 Σ 𝑖,𝑘 + 6ℎ(𝑥 𝑖 ) 𝑀 2 𝑖,𝑘
𝑊 𝑖,𝑘 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 . 𝛾

-2𝑠(𝑥 𝑖 ) 1 𝑊 𝑖,𝑘 Σ 𝑖,𝑘 𝑥 𝑖 (𝜇 𝑖,𝑘 ) ⊤ + 1 𝑊 𝑖,𝑘 𝜇 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 + Σ 𝑖,𝑘 𝑥 𝑖 (𝛾 𝑖,𝑘 ) ⊤ + 𝛾 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 . (21)
We prove that the quadratic form of 𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 at 𝑧 𝑖 ∈ R 𝑑 𝑖 is positive, for any 𝑧 𝑖 ∈ R 𝑑 𝑖 and (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ∈ 𝑄 𝑖 × [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], i.e.,

(𝑧 𝑖 ) ⊤ 𝐻 𝑥 𝑓 𝑖,𝑘 𝑧 𝑖 ≥ 0. ( 22
)
In fact, by taking the quadratic from of (21) at 𝑧 𝑖 , we have

(𝑧 𝑖 ) ⊤ (𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 = 𝑀 𝑖,𝑘 (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 + 3ℎ(𝑥 𝑖 ) √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝛾 𝑖,𝑘 ) + 1 √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝜇 𝑖,𝑘 ) 2 -4𝑠(𝑥 𝑖 ) ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ) (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 . ( 23
)
Note that the following inequalities hold

(i) -4𝑠(𝑥 𝑖 ) ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ) (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 ≥ -4|𝑠(𝑥 𝑖 )|.|(𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 |. (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 , (ii) |(𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 | ≤ √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 , (iii) (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 ≤ (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 , (24)
where (i) and (iii) are trivial. In order to prove (ii), let 𝑒 1 = (𝑧 𝑖 ) ⊤ (Σ 𝑖,𝑘 ) 1 2 , 𝑒 2 = (𝑥 𝑖 ) ⊤ (Σ 𝑖,𝑘 ) 1 2 , then by Cauchy-Schwarz inequality, (ii) is rewritten as

|𝑒 1 (𝑒 2 ) ⊤ | ≤ ∥𝑒 1 ∥ 2 ∥𝑒 2 ∥ 2 .
It follows from (i) -(iii) of ( 24) that

-4𝑠(𝑥 𝑖 ) ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ) (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 ≥ -4|𝑠(𝑥 𝑖 )|. √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 . (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 . ( 25
)
Then, from ( 23) and ( 25), we get

(𝑧 𝑖 ) ⊤ (𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 ≥ 𝑀 𝑖,𝑘 (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 + 3ℎ(𝑥 𝑖 ) √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝛾 𝑖,𝑘 ) + 1 √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝜇 𝑖,𝑘 ) 2 -4 𝑠(𝑥 𝑖 ) √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 + 1 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 . Note that |𝑠(𝑥 𝑖 )| = √ 𝑊 𝑖,𝑘 𝑀 𝑖,𝑘 and 3ℎ(𝑥 𝑖 ) √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝛾 𝑖,𝑘 ) + 1 √ 𝑊 𝑖,𝑘 ((𝑧 𝑖 ) ⊤ 𝜇 𝑖,𝑘 ) 2 ≥ 0, which in turn implies that (𝑧 𝑖 ) ⊤ (𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 ≥ 𝑀 𝑖,𝑘 (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 -4 √ 𝑀 𝑖,𝑘 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 √ (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 √ 𝑊 𝑖,𝑘 |(𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 | + 1 √ 𝑊 𝑖,𝑘 |(𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 | . ( 26
)
Assume that 𝑧 𝑖 ≠ 0. Dividing both sides of ( 26) by ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 ) ((𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ), we have

(𝑧 𝑖 ) ⊤ ( 𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 ) ((𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ) ≥ 𝑀 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 -4 √ 𝑀 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 √ 𝑊 𝑖,𝑘 (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 + 1 √ 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 . ( 27
)
Note that 𝑀 𝑖,𝑘 ( 𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 = [𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 )] 2 . Since 𝑥 𝑖 ∈ 𝑄 𝑖 and 𝑄 𝑖 is a subset of 𝑘 ∈ 𝐽 𝑖 Ω 𝑖,𝑘 , then 𝑥 𝑖 ∈ Ω 𝑖,𝑘 , for any 𝑘 ∈ 𝐽 𝑖 . Then, for any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], it follows from the definition of Ω 𝑖,𝑘 in (12) that 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) > 0.

Therefore, we can write √ 𝑀 𝑖,𝑘 ( 𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 = 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) and ( 27) is equivalent to the following inequality

(𝑧 𝑖 ) ⊤ ( 𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 ((𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 ) [(𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ] ≥ 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) 2 -4𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) √ 𝑊 𝑖,𝑘 (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 + 1 √ 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 .
It is easy to see that the following inequalities hold

(i) (𝛾 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 ≤ ||𝛾 𝑖,𝑘 || 2 .||𝑧 𝑖 || 2 √ 𝜆 𝑖,𝑘,min .||𝑧 𝑖 || 2 = ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min , (ii) (𝜇 𝑖,𝑘 ) ⊤ 𝑧 𝑖 √ (𝑧 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑧 𝑖 ≤ ||𝜇 𝑖,𝑘 || 2 .||𝑧 𝑖 || 2 √ 𝜆 𝑖,𝑘,min .||𝑧 𝑖 || 2 = ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min , (iii) √ 𝑊 𝑖,𝑘 ≤ √ 𝑤 𝑖,𝑘 u , 1 √ 𝑊 𝑖,𝑘 ≤ 1 √ 𝑤 𝑖,𝑘 l , which in turn implies that √ 𝑊 𝑖,𝑘 (𝛾 𝑖,𝑘 ) ⊤ 𝑧 √ 𝑧 ⊤ Σ 𝑖,𝑘 𝑧 + 1 √ 𝑊 𝑖,𝑘 (𝜇 𝑖,𝑘 ) ⊤ 𝑧 √ 𝑧 ⊤ Σ 𝑖,𝑘 𝑧 ≤ ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min 1 √ 𝑤 𝑖,𝑘 l . ( 28
)
Then, from ( 27) and ( 28), we get

𝑧 ⊤ ( 𝑀 𝑖,𝑘 ) 2 2 .𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 (𝑧 ⊤ Σ 𝑖,𝑘 𝑧) [(𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 𝑥 𝑖 ] ≥ [𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 )] 2 -4𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) ||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 u + ||𝜇 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min 1 √ 𝑤 𝑖,𝑘 l . ( 29
)
Since 𝑥 𝑖 ∈ Ω 𝑖,𝑘 , for any 𝑘 ∈ 𝐽 𝑖 , the term on the right-hand side of ( 29) is positive, which implies that (𝑧 𝑖 ) ⊤ 𝐻 𝑥 𝑖 𝑓 𝑖,𝑘 𝑧 𝑖 ≥ 0. □

Using the abovementioned lemmas, we prove the following convexity result.

Lemma 5. Let Assumption 2 hold. Then, 𝑆 𝑖 𝛼 𝑖 is a convex set, for all 𝑖 ∈ 𝐻. Proof. Let 𝛼 𝑖 ∈ (𝛼 * 𝑖 , 1], 𝜆 ∈ (0, 1) and 𝑦 1 , 𝑦 2 ∈ 𝑆 𝑖 𝛼 𝑖 . We will show that 𝜆𝑦 1 + (1 -𝜆)𝑦 2 ∈ 𝑆 𝑖 𝛼 𝑖 . Consider 4 cases as follows Case 1: Let 𝑦 1 = 0 or 𝑦 2 = 0. Without loss of generality, we assume that 𝑦 2 = 0. Since 𝑦 0 = 0 ∈ 𝑆 𝑖 𝛼 𝑖 , then P(0 ≤ 𝐷 𝑖 ) ≥ 𝛼 𝑖 . Since 𝛼 𝑖 > 0 and 𝐷 𝑖 is a real vector, we have that 𝐷 𝑖 ≥ 0, which implies that

P(𝑉 𝑖 𝜆𝑦 1 ≤ 𝐷 𝑖 ) ≥ P(𝑉 𝑖 𝑦 1 ≤ 𝐷 𝑖 ) ≥ 𝛼 𝑖 . Therefore, 𝜆𝑦 1 + (1 -𝜆)𝑦 2 ∈ 𝑆 𝑖 𝛼 𝑖 . Case 2: Let 𝑦 1 ≠ 0, 𝑦 2 ≠ 0 and 𝜆𝑦 1 + (1 -𝜆)𝑦 2 = 0. In this case, 𝑦 2 = -𝜆 1-𝜆 𝑦 1 ∈ S𝑖 𝛼 𝑖 and 𝑦 1 ∈ S𝑖 𝛼 𝑖 . It follows from Lemma 1 that (𝜇 𝑖,𝑘 ) ⊤ 𝑦 1 > 𝜆 -1 𝜆 𝐷 𝑖,𝑘 , (𝜇 𝑖,𝑘 ) ⊤ 𝑦 1 < 𝐷 𝑖,𝑘 , ∀ 𝑘 ∈ 𝐽 𝑖 .
This implies that 𝐷 𝑖,𝑘 ≥ 0 for all 𝑘 ∈ 𝐽 𝑖 . Hence,

𝜆𝑦 1 + (1 -𝜆)𝑦 2 = 0 ∈ 𝑆 𝑖 𝛼 𝑖 . Case 3: Let 𝑦 1 ≠ 0, 𝑦 2 ≠ 0 and 0 ∈ Seg(𝑦 1 , 𝑦 2 ), where Seg(𝑦 1 , 𝑦 2 ) = {𝑦 1 + 𝑙 (𝑦 2 -𝑦 1 ), 0 ≤ 𝑙 ≤ 1} .
Then, for any point 𝑥 ∈ Seg(𝑦 1 , 𝑦 2 ), either 𝑥 ∈ Seg(𝑦 1 , 0) or 𝑥 ∈ Seg(0, 𝑦 2 ). It follows from Case 1 that Seg(𝑦 1 , 0) and Seg(0, 𝑦 2 ) are subset of 𝑆 𝑖 𝛼 𝑖 . Therefore,

𝜆𝑦 1 + (1 -𝜆)𝑦 2 ∈ 𝑆 𝑖 𝛼 𝑖 for all 𝜆 ∈ [0, 1]. Case 4: Let 𝑦 1 ≠ 0, 𝑦 2 ≠ 0 such that 0 ∉ Seg(𝑦 1 , 𝑦 2 ). It is clear that Seg(𝑦 1 , 𝑦 2 ) ⊂ Conv( S𝑖 𝛼 𝑖 ).
From Lemmas 3 and 4, 𝑔 𝑖,𝑘 (•, 𝑊 𝑖,𝑘 ) is defined and (-2)-concave on Seg(𝑦 1 , 𝑦 2 ), for all 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], which implies that

𝑔 𝑖,𝑘 (𝜆𝑦 1 + (1 -𝜆)𝑦 2 , 𝑊 𝑖,𝑘 ) ≥ 𝜆(𝑔 𝑖,𝑘 (𝑦 1 ), 𝑊 𝑖,𝑘 ) -2 + (1 -𝜆) (𝑔 𝑖,𝑘 (𝑦 2 ), 𝑊 𝑖,𝑘 ) -2 -1 2 . ( 30
)
Since, 𝑦 1 ∈ S𝑖 𝛼 𝑖 and 𝛼 𝑖 > 𝛼 (3) 𝑖 , using Lemma 2, for any 𝑧 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], the following condition holds

E 𝑊 𝑖,𝑘        Φ √ 𝑧 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        > 𝛼 (3) 𝑖 .
Moreover, it follows from the definition of 𝛼 (3)

𝑖

in Assumption 2 that

𝛼 (3) 𝑖 ≥ Φ √ 3𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l ,
which in turn implies that

E 𝑊 𝑖,𝑘        Φ √ 𝑧 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l        > Φ √ 3𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l . (31)
If 𝑔 𝑖,𝑘 (𝑧 1 , 𝑧) ≤ 0, (31) implies that

Φ ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l > Φ √ 3𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l ,
which gives a contradiction by the increasing monotonicity of Φ. Therefore, 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧) ≥ 0. For any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], we have

√ 𝑧 √ 𝑊 𝑖,𝑘 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧) ≤ √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧). (32)
From ( 31) and ( 32), for any 𝑧 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], we get

Φ √ 𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l 𝑔 𝑖,𝑘 (𝑦 1 , 𝑧) + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l > Φ √ 3𝑤 𝑖,𝑘 u √ 𝑤 𝑖,𝑘 l + ||𝛾 𝑖,𝑘 || 2 (𝑤 𝑖,𝑘 u -𝑤 𝑖,𝑘 l ) √ 𝜆 𝑖,𝑘,min √ 𝑤 𝑖,𝑘 l , which in turn implies that 0 < 𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 ) -2 < 1 3 , ∀ 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ].
Similarly,

0 < 𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 ) -2 < 1 3 , ∀ 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ].
By applying the non-decreasing function Φ(•) on both side of (30), we can write

Φ 𝑔 𝑖,𝑘 𝜆𝑦 1 + (1 -𝜆)𝑦 2 , 𝑊 𝑖,𝑘 ≥ Φ 𝜆(𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 )) -2 + (1 -𝜆) (𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 )) -2 -1 2 , ∀ 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ]. (33)
Since, Φ(•) is the cumulative distribution function of a standard Normal distribution, it follows from Proposition 4.1 of [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF] that Φ(•) has 𝑟-decreasing density, for any 𝑟 > 0 and 𝑡 * = √ 𝑟, where 𝑡 * refers to Definition 1. By choosing 𝑟 = 3, it follows from Lemma 3.1 of [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF], the function

𝑡 ↦ → Φ 𝑡 -1 2 is concave on (0, 1
3 ). Therefore, for any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], we obtain

Φ 𝜆(𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 )) -2 + (1 -𝜆) (𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 )) -2 -1 2 ≥ 𝜆 Φ 𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 ) + (1 -𝜆) Φ 𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 ) . (34)
For any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ], it follows from ( 33) and (34) that

Φ 𝑔 𝑖,𝑘 (𝜆𝑦 1 + (1 -𝜆)𝑦 2 , 𝑊 𝑖,𝑘 ) ≥ 𝜆 Φ 𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 ) + (1 -𝜆) Φ 𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 ) , (35)
which implies that Φ 𝑔 𝑖,𝑘 (•, 𝑊 𝑖,𝑘 ) is a concave function on Seg(𝑦 1 , 𝑦 2 ), for any 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ]. By taking the expectation value E 𝑊 𝑖,𝑘 on both sides of (35), we deduce that

E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝜆𝑦 1 + (1 -𝜆)𝑦 2 , 𝑊 𝑖,𝑘 ) ≥ 𝜆 E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑦 1 , 𝑊 𝑖,𝑘 + (1 -𝜆) E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (𝑦 2 , 𝑊 𝑖,𝑘 (36)
which in turn implies that the function E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (•, 𝑊 𝑖,𝑘 ) is a concave function on Seg(𝑦 1 , 𝑦 2 ). It follows from the discussion in Definition 2.1 of [START_REF] Henrion | Convexity of chance constraints with independent random variables[END_REF] that log-concavity is a weaker property than concavity.

Therefore, E 𝑊 𝑖,𝑘 Φ 𝑔 𝑖,𝑘 (•, 𝑊 𝑖,𝑘 ) is also a log-concave function on Seg(𝑦 1 , 𝑦 2 ). Then, 𝜆𝑦 1 + (1 -𝜆)𝑦 2 ∈ 𝑆 𝑖 𝛼 𝑖 . □ The convexity of 𝑆 𝑖 𝛼 𝑖 under normal mean-variance mixture distribution was shown in Theorem 2.3 of (Nguyen and Lisser, 2021) when 𝑥 𝑖 satisfy certain conditions (e.g. condition 3 and 4 of Theorem 2.3 (Nguyen and Lisser, 2021)). In the numerical section of (Nguyen and Lisser, 2021), it is shown that these assumptions hold under some strict conditions, e.g., 𝐷 𝑖,𝑘 ≥ 𝑁 × 𝑑 𝑖 , for any 𝑖 ∈ 𝐻, 𝑘 ∈ 𝐽 𝑖 , where 𝑑 𝑖 is the dimension of 𝑥 𝑖 and 𝑁 is a large number (𝑁 ≥ 200 in general). In Lemma 5, we relax the strong conditions on 𝑥 𝑖 used in Theorem 2.3 of [START_REF] Hoang | Convexity conditions for normal mean-variance mixture distribution in joint probabilistic constraints[END_REF]

𝑖

tends to Φ( √ 3). Therefore, the best possible value of the lower bound on probability level is around 0.96. The earlier work [START_REF] Hoang | Convexity conditions for normal mean-variance mixture distribution in joint probabilistic constraints[END_REF] does not give any theoretical lower bound of 𝛼 𝑖 . The authors presented few examples where the lower bound can go up to 0.99. In practice, a high probability level value (≥ 0.95) for the chance constraints is desirable as it ensures the reliability of the solution. In the next section, we consider a competition between two financial firms whose loss vectors follow normal mean-variance mixture distributions for which 𝛼 * 𝑖 = 0.96, i.e., it attains the best possible theoretical lower bound. The closeness of 𝑆 𝑖 𝛼 𝑖 is a consequence of Proposition 3.1 in [START_REF] Römisch | Stability analysis for stochastic programs[END_REF]. Since 𝑆 𝑖 𝛼 𝑖 is a subset of 𝑆 𝑖 , which is a compact set, we deduce that 𝑆 𝑖 𝛼 𝑖 is a compact set. We show that there exists a Nash equilibrium of the CCG by the following theorem.

Theorem 1. Consider an 𝑛-player CCG defined in Section 1, where 1. Assumptions 1 and 2 hold.

2. For each 𝑖 ∈ 𝐻, we assume that 𝑉 𝑖,𝑘 ∼ 𝑁 𝑀𝑉 𝑀 (𝜇 𝑖,𝑘 , 𝛾 𝑖,𝑘 , Σ 𝑖,𝑘 , 𝑊 𝑖,𝑘 ) and the vectors 𝑉 𝑖,𝑘 are mutually independent, 𝑘 ∈ 𝐽 𝑖 .

Then, there exists a Nash equilibrium of the CCG for any 𝛼 ∈ (𝛼 [START_REF] Ky | Applications of a theorem concerning sets with convex sections[END_REF]. □

Competition of two firms in financial market

We consider a competition model of two firms in a same financial market. Let 𝐽 = {1, . . . , 𝐾 } be the set of portfolios and A 𝑘 be the set of assets in portfolio 𝑘, for 𝑘 ∈ 𝐽. We assume that both firms invest in the same set of portfolios from 𝐽 and the portfolios are pairwise disjoint. Each firm 𝑖 invests its money in the assets. Let 𝑥 𝑖 𝑘 𝑗 be the amount of money that firm 𝑖 invests in asset 𝑗 of portfolio 𝑘. Let 𝑥 𝑖 𝑘 = 𝑥 𝑖 𝑘 𝑗 𝑗 ∈ A 𝑘 be the investment vector of firm 𝑖 in portfolio 𝑘 and 𝑥 𝑖 = 𝑥 𝑖 𝑘 𝑘 ∈ 𝐽 be the strategy vector of firm 𝑖. The strategy set of firm 𝑖 (or the set of investments) is defined as

𝑆 𝑖 =      𝑥 𝑖 | ∑ 𝑗 ∈ A 𝑘 , 𝑘 ∈ 𝐽 𝑥 𝑖 𝑘 𝑗 ≤ 𝐵 𝑖 , 𝑥 𝑖 𝑘 𝑗 ≥ 𝜖 𝑖 𝑘 𝑗 , for any 𝑘 ∈ 𝐽, 𝑗 ∈ A 𝑘     
, where 𝐵 𝑖 is the budget of firm 𝑖 and 𝜖 𝑖 𝑘 𝑗 > 0 is the minimal amount firm 𝑖 must invest in asset 𝑗 of portfolio 𝑘. It is clear that 𝑆 𝑖 is a convex and compact set with strictly positive components, for any 𝑖 = 1, 2. The vector (𝑥 1 , 𝑥

) ⊤ 𝐿 𝑖 𝑘 ≤ 𝐷 𝑖 𝑘 , 𝑘 ∈ 𝐽 ≥ 𝛼 𝑖 , ∀ 𝑖 = 1, 2.
Hence, the feasible strategy set of firm 𝑖 is defined as

𝑆 𝑖 𝛼 𝑖 = 𝑥 𝑖 ∈ 𝑆 𝑖 | P (𝑥 𝑖 𝑘 ) ⊤ 𝐿 𝑖 𝑘 ≤ 𝐷 𝑖 𝑘 , 𝑘 ∈ 𝐽 ≥ 𝛼 𝑖
We assume that for any 𝑖 = 1, 2 and 𝑘 ∈ 𝐽, the random loss vector 𝐿 𝑖 𝑘 follows a normal mean-variance mixture distribution. Let 𝑅 𝑖 𝑘 = -𝐿 𝑖 𝑘 be the random return vector of firm 𝑖 from portfolio 𝑘. We consider the case where each firm wants to minimize their transaction cost which is incurred due to trades from multiple firms. The transaction cost of a firm usually also depends on the investment of other firms [START_REF] Lampariello | Equilibrium selection for multi-portfolio optimization[END_REF]. Therefore, for a given strategy profile (𝑥 1 , 𝑥 2 ), we consider the quadratic transaction cost as follows

TC 𝑖 (𝑥 1 , 𝑥 2 ) = ∑ 𝑘 ∈ 𝐽 (𝑥 1 𝑘 + 𝑥 2 𝑘 ) ⊤ Ω 𝑖 𝑘 (𝑥 1 𝑘 + 𝑥 2 𝑘 ),
where TC 𝑖 (𝑥 1 , 𝑥 2 ) is the transaction cost of firm 𝑖 at strategy profile (𝑥 1 , 𝑥 2 ), the positive semidefinite matrix Ω 𝑖 𝑘 represents the market impact of portfolio 𝑘 on firm 𝑖 whose entry at position (𝑟, 𝑠) is the impact of the liquidity of asset 𝑟 on the liquidity of asset 𝑠. The same formulation of transaction cost has been considered in [START_REF] Lampariello | Equilibrium selection for multi-portfolio optimization[END_REF]. The payoff function of firm 𝑖 is defined as follows

𝑢 𝑖 (𝑥 1 , 𝑥 2 ) = ∑ 𝑘 ∈ 𝐽 E(𝑅 𝑖 𝑘 ) ⊤ 𝑥 𝑖 𝑘 -TC 𝑖 (𝑥 1 , 𝑥 2 ),
where 𝑘 ∈ 𝐽 E(𝑅 𝑖 𝑘 ) ⊤ 𝑥 𝑖 𝑘 is the expected return of firm 𝑖 at strategy profile (𝑥 1 , 𝑥 2 ). It is clear that the payoff function of firm 𝑖 is a continuous function of the strategy profile and concave with respect to its strategy vector, for every fixed strategy vector of the other firm.

In our case study, we consider two firms with three portfolios where each portfolio consists of three assets, i.e, 𝐽 = {1, 2, 3} and A 𝑘 = {1, 2, 3}, for any 𝑘 ∈ 𝐽. We assume that the random loss vectors follow normal mean-variance mixture distributions, i.e., for any 𝑖 = 1, 2 and 𝑘 ∈ 𝐽, 𝐿 𝑖 𝑘 ∼ NMVM(𝜇 𝑖,𝑘 , 𝛾 𝑖,𝑘 , Σ 𝑖,𝑘 , 𝑊 𝑖,𝑘 ), where 𝜇 𝑖,𝑘 is an 3 × 1 vector taken on [-0.35, 0] 3 and 𝛾 𝑖,𝑘 is a 3 × 1 vectors taken on [0, 0.02] 3 . Σ 𝑖,𝑘 is a 3 × 3 positive definite matrix with all eigen values belong to [5,10] and high values on the main diagonal and it is given by

Σ 𝑖,𝑘 = 𝐴𝐴 ⊤ 3 × max (1, 𝜆 max ) + 𝛽 × 𝐼 3 ,
where 𝐴 is a 3 × 3 random matrix whose all the entries are real numbers in [0, 1], 𝜆 max is the largest eigenvalue of the semidefinite positive matrix 𝐴𝐴 ⊤ 3 , 𝛽 is a real number taken on [5, 9] and 𝐼 3 is 3 × 3 identity matrix. We take negative values of location parameters 𝜇 𝑖,𝑘 and high values on the main diagonal of covariance matrix Σ 𝑖,𝑘 because the firms gain positive return in expectation if they decide to invest but they have to make risky decision. 𝑊 𝑖,𝑘 follows The numerical results below are performed using Python 3.8.8 on an Intel Core i5-1135G7, Processor 2.4 GHz (8M Cache, up to 4.2 GHz), RAM 16G, 512G SSD. We compute a Nash equilibrium using the well-known best response algorithm. The algorithm converges to a Nash equilibrium point (𝑥 1 * , 𝑥 2 * ) given by 𝑥 1 * = [(0.48, 0.51, 0.63), (0.47, 0.31, 0.55), (0.67, 0.25, 0.4)] ,

𝑥 2 * = [(0.52, 0.31, 0.73), (0.57, 0.54, 0.57), (0.47, 0.55, 0.3)] ,

Figure 1 shows that best response algorithm converges after few iterations.

Conclusion

We show that there exists a Nash equilibrium of an 𝑛 player CCG when the random constraint vectors of the joint chance constraint are independent and follow normal mean-variance mixture distributions. The convexity of joint chance constraint, which is crucial for the existence of Nash equilibrium, does not require two strong conditions used in an earlier work [START_REF] Hoang | Convexity conditions for normal mean-variance mixture distribution in joint probabilistic constraints[END_REF]. It only needs a theoretical lower bound on the probability level which is defined in terms of the parameter of the normal mean-variance mixture distribution.

Figure 1 :

 1 Figure 1: Convergence of payoffs to a Nash equilibrium.

  1-𝛼 , otherwise.

	Definition 3. An 𝑛-dimensional random vector 𝑈 follows a normal mean-variance mixture distribution with parameters
	(𝜇, 𝛾, Σ, 𝑊), i.e., 𝑈 ∼ NMVM(𝜇, 𝛾, Σ, 𝑊), if we have the following representation:

  Let Assumption 2 hold. Then, for any convex subset 𝑄 𝑖 of 𝑘 ∈ 𝐽 𝑖 Ω 𝑖,𝑘 such that 0 ∉ 𝑄 𝑖 , 𝑔 𝑖,𝑘 (𝑥 𝑖 , 𝑊 𝑖,𝑘 ) is defined and (-2)-concave with respect to 𝑥 𝑖 on 𝑄 𝑖 , for all 𝑖 ∈ 𝐻, 𝑘 ∈ 𝐽 𝑖 and 𝑊 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ].

	𝑖,𝑘 ) > 4	||𝛾 𝑖,𝑘 || 2 √ 𝜆 𝑖,𝑘,min	√	𝑤 𝑖,𝑘 u +	||𝜇 𝑖,𝑘 || 2 𝜆 𝑖,𝑘,min √ √	l 𝑤 𝑖,𝑘	.	(17)
	Conv S𝑖 𝛼 𝑖 ⊂

Since (17) holds for any 𝑧 𝑖,𝑘 ∈ [𝑤 𝑖,𝑘 l , 𝑤 𝑖,𝑘 u ] and 𝑥 𝑖 ∈ S𝑖 𝛼 𝑖 , we get

S𝑖 𝛼 𝑖 ⊂ 𝑘 ∈ 𝐽 𝑖 Ω 𝑖,𝑘 .

(18)

Note that Ω 𝑖,𝑘 is a convex set. Then, by taking the convex hull on both side of (18), 𝑘 ∈ 𝐽 𝑖 Ω 𝑖,𝑘 .

□

Lemma 4.

  𝑖,𝑘 ]. 𝛾 𝑖,𝑘 + 𝑊 𝑖,𝑘 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 . 𝛾 𝑖,𝑘 +

											𝜇 𝑖,𝑘
											𝑊 𝑖,𝑘
	=	-2 𝑀 3	.2𝑠(𝑥 𝑖 ). 𝛾 𝑖,𝑘 +	𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ,
			𝑖,𝑘
	which in turn imply that
	𝐴 =	-4𝑠(𝑥 𝑖 ) 𝑀 2 𝑖,𝑘	𝛾 𝑖,𝑘 +	𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 (𝑥 𝑖 ) ⊤ Σ 𝑖,𝑘 , 𝐵 =	2 𝑀 𝑖,𝑘	Σ 𝑖,𝑘 , 𝐶 =	𝑖,𝑘 -2ℎ(𝑥 𝑖 ) 𝑀 2	𝜇 𝑖,𝑘 𝑊 𝑖,𝑘	⊤	,
	𝐷 =		8ℎ(𝑥 𝑖 )𝑠 2 (𝑥 𝑖 ) 𝑀 3	𝛾 𝑖,𝑘 +	𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 𝛾 𝑖,𝑘 +	𝜇 𝑖,𝑘 𝑊 𝑖,𝑘	⊤	, 𝐸 =	-4𝑠(𝑥 𝑖 ) 𝑀 2
				𝑖,𝑘							𝑖,𝑘

.

Σ 𝑖,𝑘 𝑥 𝑖 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘 ⊤ . Note that 𝑠 2 (𝑥 𝑖 ) = 𝑊 𝑖,𝑘 𝑀 𝑖,𝑘 . Then, 𝐷 = 8ℎ( 𝑥 𝑖 ) 𝑀 2 𝑖,𝑘

. 𝑊 𝑖,𝑘 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 . 𝛾 𝑖,𝑘 + 𝜇 𝑖,𝑘 𝑊 𝑖,𝑘

  and give the lower bound 𝛼 * 𝑖 , defined in Assumption 2, on the probability level 𝛼 𝑖 for which 𝑆 𝑖 𝛼 𝑖 is a convex set. The lower bound 𝛼 * 𝑖 can be calculated using the parameters of normal mean-variance mixture distribution. If we set ||𝛾 𝑖,𝑘 || 2 and ||𝜇 𝑖,𝑘 || 2 small compared to √ 𝜆 𝑖,𝑘,min (which is relevant as shown in Section 4 due to high value of eigenvalue of covariance matrix to model risky decision) and 𝑤 𝑖,𝑘 u ≈ 𝑤 𝑖,𝑘 l , the lower bound of 𝛼 *

	Φ	√	3 ≈ 0.958 because 𝛼 (1) 𝑖	and 𝛼 (2) 𝑖	tend to Φ(0) and 𝛼 (3)	𝑖 tends to

  Given 𝛼 ∈ (𝛼 * 1 , 1] × . . . × (𝛼 * 𝑛 , 1], and subject to Assumption 1, the payoff function 𝑝 𝑖 (𝑥 𝑖 , 𝑥 -𝑖 ) is concave in terms of 𝑥 𝑖 for any 𝑥 -𝑖 ∈ 𝑆 -𝑖 and continuous with respect to 𝑥. By applying Lemma 5, it can be deduced that the feasible strategy set 𝑆 𝑖 𝛼 𝑖 , where 𝑖 ∈ 𝐻, is a convex set for all 𝛼 𝑖 ∈ (𝛼 * 𝑖 , 1]. Additionally, each 𝑆 𝑖 𝛼 𝑖 is a compact set. As a consequence, the existence of a Nash equilibrium in the context of the CCG follows from Theorem 4 presented in

* 1 , 1] × . . . × (𝛼 * 𝑛 , 1], where 𝛼 * 𝑖 𝑖 ∈ 𝐻 refers to Assumption 2. Proof.

  2 ) ∈ 𝑆 1 × 𝑆 2 represents a strategy profile (or an investment profile) of both firms. Let 𝐿 𝑖 𝑘 = 𝐿 𝑖 𝑘 𝑗 𝑗 ∈ A 𝑘 be a random loss vector of firm 𝑖 from portfolio 𝑘. Then, for a given investment vector 𝑥 𝑖 𝑘 , the random loss incurred by firm 𝑖 from portfolio 𝑘 is (𝐿 𝑖 𝑘 ) ⊤ 𝑥 𝑖 𝑘 . Let 𝐷 𝑖 𝑘 be the maximal loss level of firm 𝑖 from portfolio 𝑘 and firm 𝑖 wants to keep its random loss below this level at probability level 𝛼 𝑖 , i.e.,

	P (𝑥 𝑖 𝑘

Acknowledgments

This research was supported by French government under the France 2030 program, reference ANR-11-IDEX-0003 within the OI H-Code.

Data availability statement

No data was used for the research described in the article.


domain: info math

text:
Nam Hoang

Nguyen

Abdel Lisser
email: abdel.lisser@centralesupelec.fr

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

Distributionally robust chance-constrained Markov decision processes with random payoff

Keywords: Markov decision process, Distributionally robust chance constraints, Second-order cone programming, Copositive optimization, Mix-integer second-order cone programming, Biconvex optimization

A Markov Decision Process (MDP) is a framework used for decision-making. In an MDP problem, the decision maker's goal is to maximize the expected discounted value of future rewards while navigating through different states controlled by a Markov chain. In this paper, we focus on the case where the transition probabilities vector is deterministic, while the reward vector is uncertain and follow a partially known distribution. We employ a distributionally robust chance constraints approach to model the MDP. This approach entails the construction of potential distributions of reward vector, characterized by moments or statistical metrics. We explore two situations for these uncertainty sets: one where the reward vector has a real support and another where it is constrained to be nonnegative. In the case of a real support, we demonstrate that solving the distributionally robust chance-constrained Markov decision process is mathematically equivalent to a second-order cone programming problem for moments and ϕ-divergence uncertainty sets. For Wasserstein distance uncertainty sets, it becomes a mixed-integer second-order cone programming problem. In contrast, when dealing with nonnegative reward vector, the equivalent optimization problems are different. Moments-based uncertainty sets lead to a copositive optimization problem, while Wasserstein distance-based uncertainty sets result in a biconvex optimization problem. To illustrate the practical application of these 1 methods, we examine a machine replacement problem and present results conducted on randomly generated instances to showcase the effectiveness of our proposed methods.

Introduction

An MDP serves as a foundational framework for decision-making in modeling the dynamic of a randomized system that changes as time progresses under the influence of a managed Markov chain. We assume that the system comprises a finite set of states. At the initial time step, designated as t = 0, the system commences from an initial state s 0 , drawn from a finite state space S, in accordance with a predetermined initial distribution ϱ. Subsequently, a decision maker selects an action, denoted as a 0 , from the set of feasible actions at state s 0 , represented as A(s 0 ). This choice of action yields a reward, denoted as R(s 0 , a 0 ). Following this, at t = 1, the system does a transition to a new state, s 1 , with a probability p(s 0 , a 0 , s 1 ). This process perpetuates indefinitely into the future.

The decisions made at each time step, t, whether deterministic or stochastic, may depend on the historical record available up to that point, denoted as h t . This historical record, h t , encompasses information regarding the observed states and actions up to time t, represented as h t = (s 0 , . . . , a t-1 , s t ). We denote the set of all histories at time t as H t . A decision rule at time t, denoted as f t , is characterized by f t (h t ) ∈ ℘(A(s t )), where ℘(A(s t )) is the set of all probability measures over the action set A(s t ).

A sequence of decision rules contingent upon history, referred to as a historydependent policy, is symbolized as f h = (f 0 , f 1 , . . .). A policy is stationary if there is a single decision policy, represented as f , such that f = f t for any t. In this context, we informally denote a stationary policy as f and stipulate f = (f (s))s ∈ S, with f (s) ∈ ℘(A(s)) for every state s ∈ S. Under a stationary policy f , at each state s, the decision maker selects an action a with a probability determined by f (s, a).

We designate the set of all stationary policies as P O S . A stationary policy f ∈ P O S , combined with an initial distribution ϱ, gives rise to a probability distribution P f ϱ governing the trajectories of states and actions. The expectation value associated with this probability measure is denominated as E f ϱ . The expected discounted reward with a discount factor α ∈ (0, 1) is defined as [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Puterman | Markov Decision Processes[END_REF]

V α (ϱ, f ) = (1 -α)E f ϱ ∞ t=0 α t R(X t , A t ) . (1)
Here, we introduce the notations X t and A t to represent the state and action at time t. When the running rewards and the transition probabilities are stationary, we can restrict to stationary policies without loss of optimality [START_REF] Altman | Constrained Markov Decision Processes[END_REF][START_REF] Puterman | Markov Decision Processes[END_REF]. It follows from Theorem 3.2 of [START_REF] Altman | Constrained Markov Decision Processes[END_REF] that a stationary optimal policy of the MDP problem can be obtained by solving following linear programming problem max χ∈Qα(ϱ)

χ T R, (2)
where R = (R(s, a)) s∈S,a∈A(s) is a running reward vector and T denotes the transposition. The set Q α (ϱ) is defined as

Q α (ϱ) = χ ∈ R |W| (s,a)∈W
χ(s, a) -αp(s, a, s ′ ) + δ(s ′ , s) = (1 -α)ϱ(s ′ ), s ′ ∈ S, χ(s, a) ≥ 0, ∀ s ∈ S, a ∈ A(s) , where δ(s ′ , s) is the Kronecker delta and W = {(s, a) | s ∈ S, a ∈ A(s)}. When χ * stands as an optimal solution to (2), the stationary optimal policy f * can be formulated as follows

f * (s, a) = χ * (s, a)
a∈A(s) χ * (s, a)

, ∀ s ∈ S, a ∈ A(s),

This formulation holds true as long as the denominator is non-zero. If not, we arbitrarily select f * (s) from the set of probability distributions over A(s) [START_REF] Altman | Constrained Markov Decision Processes[END_REF]. In practical applications, the parameters of the MDP model, R(•) and p(•), are typically not known in advance. Instead, they are estimated based on historical data. However, this process introduces inaccuracies into the optimal policies [START_REF] Mannor | Bias and variance approximation in value function estimates[END_REF]. Consequently, addressing this uncertainty has been an important point in the study of robust MDPs. In these robust MDPs, we focus on scenarios where either the transition probabilities or the rewards are assumed to belong to predefined uncertainty sets, as discussed in the literature [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] Varagapriya | Constrained Markov decision processes with uncertain costs[END_REF][START_REF] White | Markov decision processes with imprecise transition probabilities[END_REF][START_REF] Wiesemann | Robust Markov decision processes[END_REF]. However, Delage and Mannor [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF] made a significant observation that the robust MDP often results in overly conservative policies.

To address this issue, they introduced the concept of a chance-constrained Markov Decision Process (CCMDP) in their work, wherein the controller seeks to achieve an expected discounted reward with a certain level of confidence. In their research [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF], they delved into two distinct cases, random transition probabilities random rewards are studied independently. They stated that a CCMDP can be effectively reformulated as an SOCP problem if the reward vector follows a multivariate Gaussian distribution and the transition probabilities are known. However, in situation where the transition probabilities follow a Dirichlet distribution while the reward vector is known, solving the CCMDP problem is computationally challenging, necessitating the use of approximation methods to obtain optimal policies. In a related development, Varagapriya et al. [START_REF] Varagapriya | Joint chance-constrained Markov decision processes[END_REF] examined a CMDP problem with a joint chance constraint. In this scenario, the running cost vectors are treated as random vectors, while the transition probabilities are known. They proposed lower and upper bounds for the CMDP problem, assuming that the cost vectors follow multivariate elliptical distributions and that the dependence between constraints is governed by an Archimedean copula.

In numerous practical scenarios, we often encounter situations where we possess only partial information about the underlying distribution, typically derived from historical data. In such cases, a distributionally robust approach serves as a tool to model uncertainties. This methodology has found extensive application in modeling uncertainties in various optimization and game-related problems [START_REF] Jiang | Data-driven chance constrained stochastic program[END_REF][START_REF] Liu | Distributionally robust chance constrained geometric optimization[END_REF][START_REF] Singh | Distributionally robust chance-constrained games: Existence and characterization of Nash equilibrium[END_REF].

There are two methods for constructing an uncertainty set. The first method relies on partial information regarding the moments of the true distribution, while the second method employs statistical distances to measure the difference between the true distribution and a nominal distribution. Moments-based uncertainty sets make specific assumptions about the first two moments of the distribution [START_REF] Cheng | Distributionally robust stochastic knapsack problem[END_REF][START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF][START_REF] Popescu | Robust mean-covariance solutions for stochastic optimization[END_REF]. On the other hand, statistical distance-based uncertainty sets encompass all distributions lying within a small-radius ball centered at the nominal distribution. This nominal distribution is often a Gaussian distribution or an empirical distribution [START_REF] Esfahani | Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations[END_REF][START_REF] Jiang | Data-driven chance constrained stochastic program[END_REF]. To quantify the distance between distributions, either a ϕ-divergence [START_REF] Ben-Tal | Robust solutions of optimization problems affected by uncertain probabilities[END_REF][START_REF] Jiang | Data-driven chance constrained stochastic program[END_REF] or the Wasserstein distance metric is commonly employed [START_REF] Esfahani | Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations[END_REF][START_REF] Gao | Distributionally robust stochastic optimization with Wasserstein distance[END_REF][START_REF] Zhao | Data-driven risk-averse stochastic optimization with Wasserstein metric[END_REF].

We consider an infinite horizon MDP with a discounted reward criterion, as introduced in Section 1. In this setting, the reward vector is characterized as a random vector, while the transition probabilities are assumed to be known. The distribution of the reward vector is not entirely known and assumed to belong to a predefined uncertainty set. Our primary objective is to formulate the problem of random discounted rewards while incorporating a distributionally robust chance constraint. This constraint is designed to ensure that a given policy maximizes the reward with a specified level of confidence. This particular class of MDPs is referred to as a distributionally robust chance-constrained Markov Decision Process (DRCCMDP). The random reward vector has either a full support or a nonnegative support. Our primary contributions are as follows.

1. We consider three types of moments based uncertainty sets based on the full/partial information on the first two moments of the random reward vector. For the case of full support and nonnegative support, a DRCCMDP problem is equivalent to an SOCP problem and a copositive optimization problem, respectively. 2. We consider four different types of ϕ-divergences to construct statistical distance based uncertainty sets. We show that a DRCCMDP problem is equivalent to an SOCP problem when the nominal distribution is a normal distribution. 3. We consider the nominal distribution to be an empirical distribution when statistical distance based uncertainty set is defined with Wasserstein distance metric. For the case of full support and nonnegative support, we show that a DRCCMDP problem is equivalent to a mixed integer second-order cone programming (MISOCP) problem and a biconvex optimization problem, respectively.

The structure of the paper is as follows. In Section 2, we present the definition of a DRCCMDP under a discounted reward criterion. Section 3 contains a DRCCMDP under moments based uncertainty sets and their equivalent reformulations for the case of full and nonnegative supports. A DRCCMDP under statistical distance based uncertainty sets defined using ϕ-divergence distance metric and Wasserstein distance metric and their equivalent reformulations are presented in Section 4. We present numerical results in Section 5 and conclude the paper in Section 6.

The model

We consider an infinite horizon MDP defined in Section 1 where the transition probabilities are exactly known and the running reward vector is a random vector defined on a probability space (Ω, F, P) which is denoted as R. Therefore, for each realization ω ∈ Ω, R(s, a, ω) represents a real valued reward received at state s when an action a is taken. We assume that the random vector R does not vary with time. Since R is a random vector, for a given policy f h and initial distribution ϱ, the expected discounted reward defined by (1) becomes a random variable. The controller wants to maximize the discounted reward which can be achieved with at least a specified confidence level (1 -ϵ), where ϵ ∈ (0, 1). This leads to the following CCMDP problem

sup y∈R, f h ∈F HD y s.t. P V α (s, f h ) ≥ y ≥ 1 -ϵ. (3)
Since the transition probabilities are exactly known and random reward vector does not depend on time, we can represent the CCMDP problem (3) equivalently in terms of decision vector (y, χ) as follows sup y

s.t. (i) P χ T R ≥ y ≥ 1 -ϵ, (ii) χ ∈ Q α (ϱ). (4)
If then vector R follows a multivariate normal distribution, the optimization problem (4) is equivalent to an SOCP problem [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF]. The above result can be generalized for elliptically symmetric distributions because the linear chance constraint (i) present in (4) is equivalent to a second order cone constraint [START_REF] Henrion | Structural properties of linear probabilistic constraints[END_REF]. Nevertheless, in most of practical scenarios, we are confronted with limited information about the true probability distributions at hand. To address this, we use the distributionally robust optimization approach, where the distribution of R falls within an uncertainty set. This formulation leads us to the subsequent problem, namely the Distributionally Robust Chance-Constrained Markov Decision Process (DRCCMDP) problem sup y s.t. (i) inf

F ∈D P F χ T R ≥ y ≥ 1 -ϵ, (ii) χ ∈ Q α (ϱ), ( 5
)
where F is the distribution of R and D is a given uncertainty set. Note that P F (χ T R ≤ y -θ) ≤ P F (χ T R < y) ≤ P F (χ T R ≤ y) for every θ > 0. Therefore, we can replace sup F ∈D P F χ T R < y by sup F ∈D P F χ T R ≤ y . Then, the problem ( 5) is equivalent to the following problem sup y s.t. (i) sup

F ∈D P F χ T R ≤ y ≤ ϵ, (ii) χ ∈ Q α (ϱ). (6)
In the following sections, we study different types of uncertainty sets of R which are defined using i) partial information of moments of R, ii) ϕ-divergence distance, and iii) Wasserstein distance. For each uncertainty set, we consider the cases of full and nonnegative supports of R. We derive equivalent reformulations of DRCCMDP problem (5) (or (6) equivalently) for each uncertainty set.

Uncertainty sets based on moments

Let µ ∈ R |K| be the mean vector and Σ ≻ 0 be a |K| × |K| positive definite matrix. We consider 3 types of moments based uncertainty sets of the distribution of R defined as follows:

1. Known mean and known covariance uncertainty set: The uncertainty set of the distribution of R in this case is defined by

D 1 (φ, µ, Σ) =      F ∈ M + E(1 { R∈φ} ) = 1, E( R) = µ, E[( R -µ)( R -µ) T ] = Σ.      , (7)
2. Known mean and unknown covariance uncertainty set: The uncertainty set of the distribution of R in this case is defined by

D 2 (φ, µ, Σ, δ 0 ) =      F ∈ M + E(1 { R∈φ} ) = 1, E( R) = µ, E[( R -µ)( R -µ) T ] ⪯ δ 0 Σ.      , (8)
3. Unknown mean and unknown covariance uncertainty set: The uncertainty set of the distribution of R in this case is defined by

D 3 (φ, µ, Σ, δ 1 , δ 2 ) =      F ∈ M + E(1 { R∈φ} ) = 1, [E( R) -µ] T Σ -1 [E( R) -µ] ≤ δ 1 , E[( R -µ)( R -µ) T ] ⪯ δ 2 Σ.      , (9)
where φ ⊂ R |W| is the support of R which we assume to be a convex set, M + is the set of all probability measures on R |W| with Borel σ-algebra, δ 1 ≥ 0, δ 2 , δ 0 ≥ 1, µ ∈ RI(φ); RI(φ) denotes the relative interior of φ. The notation C ⪯ D implies that D -C is a positive semidefinite matrix and 1 {•} denotes the indicator function.

DRCCMDP with moments based uncertainty sets under full support

We consider the case when the random vector R has full support, i.e., φ = R |W| . We show that the DRCCMDP problem is equivalent to an SOCP problem. Theorem 1. Consider the DRCCMDP problem [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF] where the distribution of R belongs to the uncertainty sets defined by ( 7), ( 8), [START_REF] Ghaoui | Worst-case value-at-risk and robust portfolio optimization: A conic programming approach[END_REF], and the support φ = R |W| . Then, the DRCCMDP ( 5) can be reformulated equivalently as the following SOCP problem max y

s.t. (i) µ T χ -κ∥Σ 1 2 χ∥ 2 ≥ y, (ii) χ ∈ Q α (ϱ), (10)
where || • || 2 denotes the Euclidean norm and κ is a real number whose value for each uncertainty set is given in Table 1.

Table 1 Value of κ for moments based uncertainty set

Uncertainty set D = D 1 (φ, µ, Σ) D = D 2 (φ, µ, Σ, δ 0 ) D = D 3 (φ, µ, Σ, δ 1 , δ 2 ) κ 1-ϵ ϵ (1-ϵ)δ0 ϵ (1-ϵ)δ2 ϵ + √ δ 1
Proof. The proof follows from the fact that for each uncertainty set the distributionally robust chance constraint (i) of ( 5) is equivalent to a second-order cone constraint. The uncertainty set [START_REF] Esfahani | Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations[END_REF] has been widely studied in the literature [START_REF] Calafiore | On distributionally robust chance-constrained linear programs[END_REF][START_REF] Ghaoui | Worst-case value-at-risk and robust portfolio optimization: A conic programming approach[END_REF]. For the uncertainty sets ( 8) and ( 9), it can be proved using similar arguments used in Lemma 3.1 and Lemma 3.2 of [START_REF] Nguyen | Zero-sum games with distributionally robust chance constraints[END_REF] which are based on the one-sided Chebyshev inequality [START_REF] Liu | Distributionally robust chance constrained geometric optimization[END_REF].

DRCCMDP with moments based uncertainty sets under nonnegative support

We consider the case where the support of the random vector R is a nonnegative orthant of |W|-dimensional Euclidean space, i.e., φ = R |W| + . We show that the DRCCMDP problem ( 6) is equivalent to a copositive optimization problem. Theorem 2. Consider a DRCCMDP problem (6) with φ = R |W| + . Then, the following results hold.

1. If the uncertainty set is defined by [START_REF] Esfahani | Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations[END_REF], the DRCCMDP problem (6) is equivalent to the following copositive optimization problem max y

s.t. (i) -t -Q • Σ -qT µ ≤ sϵ, (ii) -Q -1 2 q + Qµ -1 2 qT + µ T Q -t -µ T Qµ ∈ COP |W|+1 , (iii) -Q -1 2 q + Qµ + χ -1 2 qT + µ T Q + χ T -t -µ T Qµ -s -y ∈ COP |W|+1 , (iv) Q ∈ S |W| , s ≥ 0, χ ∈ Q α (ϱ). ( 11
)
2. If the uncertainty set is defined by (8), the DRCCMDP problem (6) is equivalent to the following copositive optimization problem max y

s.t. (i) -t -µ T q -µ T Qµ + δ 0 Σ • Q ≤ sϵ, (ii) Q -1 2 q -Qµ -1 2 qT -µ T Q -t ∈ COP |W|+1 , (iii) Q 1 2 (-q + χ) -Qµ 1 2 (-q + χ) T -µ T Q -t -s -y ∈ COP |W|+1 , (iv) Q ∈ S |W| + , s ≥ 0, χ ∈ Q α (ϱ). ( 12
)
3. If the uncertainty set is defined by (9), the DRCCMDP problem (6) is equivalent to the following copositive optimization problem max y

s.t. (i) r + t ≤ sϵ, (ii)
Q 1 2 q 1 2 qT r ∈ COP |W|+1 , (iii) t ≥ (δ 2 Σ + µχ T ) • Q + χ T q + δ 1 ||Σ 1 2 (q + 2 Qµ)|| 2 , (iv)
Q 1 2 (q + χ) 1 2 (q + χ) T r -s -y ∈ COP |W|+1 , (v) Q ∈ S |W| + , s ≥ 0, χ ∈ Q α (ϱ), ( 13
)
where

COP |W|+1 = M ∈ S |W|+1 | x T M x ≥ 0, ∀ x ∈ R |W|+1 +
, S n is the set of all real symmetric matrix of size n×n, S n + is the set of positive semidefinite matrices of size n × n, • denotes the Frobenius inner product and denotes a block matrix (or a partitioned matrix).

In order to prove the first result of Theorem 2, we need the following lemma. Lemma 1. Consider an optimization problem

sup F ∈D1(φ,µ,Σ) P F (χ T R ≤ y), (14)
where

φ = R |W| + .
If the feasible set of ( 14) is non-empty, the dual of ( 14) is given by

inf -t -Q • Σ -q T µ s.t. (i) 1 {χ T ξ≤y} + q T ξ + ξ T Qξ -2ξ T Qµ + µ T Qµ + t ≤ 0, ∀ ξ ∈ R |W| + , (ii) Q ∈ S |W| ,
such that strong duality holds.

Proof. The proof is given in Appendix A.

Proof of Theorem 2. 1. Let the distribution of R belongs to the uncertainty set D 1 (ϕ, µ, Σ). Using Lemma 1, the optimization problem ( 6) is equivalent to the following problem sup y

s.t. (i) -t -Q • Σ -q T µ ≤ ϵ, (ii) q T ξ + ξ T Qξ -2ξ T Qµ + µ T Qµ + t ≤ 0, ∀ ξ ∈ R |W| + , (iii) 1 + q T ξ + ξ T Qξ -2ξ T Qµ + µ T Qµ + t ≤ 0, ∀ ξ ∈ R |W| + , χ T ξ ≤ y, (iv) Q ∈ S |W| , χ ∈ Q α (ϱ). ( 15
)
The constraint (ii) of ( 15) is equivalent to:

(ξ T , 1)U (ξ T , 1) T ≥ 0, ∀ ξ ∈ R |W| + , where U ∈ S |W|+1 such that U = -Q -1 2 q + Qµ -1 2 q T + µ T Q -t -µ T Qµ .
Here, (ξ T , 1) denotes the row vector of size 1 × (|W| + 1) with the last component equals 1 and the first |W| components are the components of ξ. The above inequality can be rewritten as

x T U x ≥ 0, ∀ x ∈ R |W|+1 + , ||x|| 2 = 1.
Using Proposition 5.1 in [START_REF] Hiriart-Urruty | A variational approach to copositive matrices[END_REF], we deduce that the constraint (ii) of ( 15) is equivalent to U ∈ COP |W|+1 . The constraint (iii) of ( 15) is equivalent to:

-1 + (ξ T , 1)U (ξ T , 1) T ≥ 0, ∀ ξ ∈ R |W| + , χ T ξ ≤ y. ( 16
) Define,        s P = min ξ∈R |W| + max λ≥0 L(λ, ξ, U, χ, y). s D = max λ≥0 min ξ∈R |W| + L(λ, ξ, U, χ, y). ( 17
)
where L(λ, ξ, U, χ, y) = -1 + (ξ T , 1)U (ξ T , 1) T + λ(χ T ξ -y). In [START_REF] Cheng | Distributionally robust stochastic knapsack problem[END_REF], the authors use the Sion's minimax theorem [START_REF] Sion | On general minimax theorems[END_REF] to interchange the minimum and the maximum. However, since φ is not compact, we cannot apply the Sion's minimax theorem directly in this case. We show that φ can be restricted to a compact set without loss of optimality. For a given U and χ, we have

s P ≤ max λ≥0 L(λ, 0, U, χ, y) = max λ≥0 (-t -µ T Qµ -λy -1) = -t -µ T Qµ -1 < ∞ (18)
Therefore, using the min-max inequality

s D ≤ s P < ∞. Let U i = U + 1 2 i I |W|+1 and χ i = χ + 1 2 i 1,
for every i ∈ N, where I |W|+1 denotes the identity matrix of size |W| + 1, 1 denotes the vector with all components equal to 1. It is clear from the construction that χ i > 0 componentwise. Since, L is a continuous function w.r.t U and χ, we have

L(λ, ξ, U i , χ i , y) i→∞ ---→ L(λ, ξ, U, χ, y), ∀ ξ ∈ R |W| + , λ ≥ 0.
Since, the min and max operators preserve the continuity, we have

min ξ∈R |W| + max λ≥0 L(λ, ξ, U i , χ i , y) i→∞ ---→ min ξ∈R |W| + max λ≥0 L(λ, ξ, U, χ, y). max λ≥0 min ξ∈R |W| + L(λ, ξ, U i , χ i , y) i→∞ ---→ max λ≥0 min ξ∈R |W| + L(λ, ξ, U, χ, y).
This implies that, if s P = s D holds for any U i , χ i , i ∈ N, it also holds for U, χ. For an arbitrary U i and χ i , let the the optimal solutions of minimax and maximin problems defined by ( 17) are (ξ P , λ P ) and (ξ D , λ D ), respectively. We prove that ξ P and ξ D are bounded, i.e., there exists Υ P > 0 and Υ D > 0 depending on U i , χ i and y such that ||ξ P || 2 ≤ Υ P and ||ξ D || 2 ≤ Υ D . It is clear that λ P = 0 and χ T i ξ P -y ≤ 0. Hence, we have

s P = -1 + (ξ T P , 1)U i (ξ T P , 1) T , = -1 + (ξ T P , 1)U (ξ T P , 1) T + 1 2 i ||ξ P || 2 2 + 1 2 i .
From constraint (ii) of ( 15), it follows that (ξ T P , 1)U (ξ T P , 1) T ≥ 0. Therefore, if ||ξ P || 2 → ∞, s P → ∞. Therefore, ||ξ P || 2 is bounded by some real number Υ P > 0 which depends on U i , χ i and y. As ξ ∈ R |W| + and χ i > 0, componentwise, we have

lim inf ||ξ||2→∞ λ(ξ)(χ T i ξ -y) ≥ 0,
for any λ(ξ) ≥ 0. Then,

s D = -1 + (ξ T D , 1)U i (ξ T D , 1) T + λ D (χ T i ξ D -y), = -1 + (ξ T D , 1)U (ξ T D , 1) T + 1 2 i ||ξ D || 2 2 + 1 2 i + λ D (χ T i ξ D -y).
It is clear that L(λ, ξ, U i , χ i , y).

Note that the set ξ | ξ ∈ R |W| + , ||ξ|| 2 ≤ Υ is compact. Therefore, from Sion's min- imax theorem s P = s D for every U i , χ i , i ∈ N. For any ξ such that χ T ξ > y, it is easy to see that max λ≥0 L(λ, ξ, U, χ, y) = ∞
The condition s P < ∞ gives χ T ξ ≤ y and λ = 0 which in turn implies that

s P = min χ T ξ≤y L(0, ξ, U, χ, y) ≥ 0.
Therefore, ( 16) is equivalent to s D ≥ 0. Then, there exists a sequence of nonnegative numbers λ j ≥ 0 and a decreasing sequence of positive numbers θ j > 0, such that θ j → 0 as j → ∞, for which the following condition holds

-1 + (ξ T , 1)U (ξ T , 1) T + λ j (χ T ξ -y) ≥ -θ j , ∀ ξ ∈ R |W| + , j ∈ N, λ j ≥ 0, ∀ j ∈ N. ( 19
)
For each j ∈ N, define

F ea(θ j ) = {(U, χ, y, λ) | -1 + (ξ T , 1)U (ξ T , 1) T + λ(χ T ξ -y) ≥ -θ j , λ ≥ 0}.
The feasible region defined by ( 19) is equivalent to j∈N F ea(θ j ). For any i < j, F ea(θ j ) ⊂ F ea(θ i ). Therefore, F ea(θ j ) ↓ i∈N F ea(θ i ) as j → ∞. The feasible set F ea(θ j ) as j → ∞ is given by

(ξ T , 1)Z(ξ T , 1) T ≥ 0, ∀ ξ ∈ R |W| + , λ ≥ 0, ( 20
)
where

Z ∈ S |W|+1 and Z = -Q -1 2 q + Qµ + λχ -1 2 q T + µ T Q + λχ T -t -µ T Qµ -1 -λy
. Using similar arguments as above, the constraint ( 20) is equivalent to

Z ∈ COP |W|+1 , λ ≥ 0. ( 21
)
This implies that the constraint (iii) of ( 15) is equivalent to [START_REF] Puterman | Markov Decision Processes[END_REF]. Hence, DRCCMDP problem ( 6) is equivalent to the following optimization problem max y

s.t. (i) -t -Q • Σ -q T µ ≤ ϵ, (ii) -Q -1 2 q + Qµ -1 2 q T + µ T Q -t -µ T Qµ ∈ COP |W|+1 , (iii) -Q -1 2 q + Qµ + λχ -1 2 q T + µ T Q + λχ T -t -µ T Qµ -1 -λy ∈ COP |W|+1 , (iv) Q ∈ S |W| , λ ≥ 0, χ ∈ Q α (ϱ). ( 22
)
If λ = 0 is an optimal solution of ( 22), it is clear that either [START_REF] Shapiro | On duality theory of conic linear problems[END_REF] is infeasible or its optimal value is ∞, which leads to contradiction. Then, we can restrict to λ > 0.

Let t = t λ , Q = Q λ , q = q λ , s = 1 λ , we deduce that ( 6) is equivalent to (11). 2. Let the distribution of R belongs to the uncertainty set D 2 (φ, µ, Σ, δ 0 ). From Theorem 3.4 [START_REF] Cheng | Distributionally robust stochastic knapsack problem[END_REF], the dual of the optimization problem sup

F ∈D P F χ T R ≤ y can be written as inf (-t -µ T q -µ T Qµ + δ 0 Σ • Q) s.t. (i) 1 {χ T ξ≤y} + t + q T ξ -ξ T Qξ + 2µ T Qξ ≤ 0, ∀ ξ ∈ R |W| + , (ii) Q ∈ S |W| + ,
and the strong duality holds. We follow the same arguments used for the case of the uncertainty set D 1 (φ, µ, Σ). 3. If the distribution of R belongs to the uncertainty set D 3 (φ, µ, Σ, δ 1 , δ 2 ), using Lemma 1 of [START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF] the dual of the problem sup F ∈D P F χ T R ≤ y is given by inf (r + t)

s.t. (i) r ≥ 1 {χ T ξ≤y} -ξ T Qξ -ξ T q, ∀ ξ ∈ R |W| + , (ii) t ≥ (δ 2 Σ + µχ T ) • Q + χ T q + δ 1 ||Σ 1 2 (q + 2Qµ)|| 2 , (iii) Q ∈ S |W| + ,
and strong duality holds. Again, the rest of the proof follows using similar arguments used in the case of D 1 (φ, µ, Σ).

Remark 1. The optimization problems (11)-( 13) are similar as they have the same objective function and same copositive constraints of the form A ∈ COP n , for some n. To the best of our knowledge, there is no commercial solver, which can solve optimization problems with copositive constraints. We propose relaxing the copositive constraints by an SDP constraint and a linear constraint, i.e., A ≻ 0 and A ≥ 0, componentwise. It is clear that these two cases are special cases of the copositive constraint, that leads to an outer approximation of the copositive problem (lower bound).

4 Uncertainty sets based on statistical distance 4.1 Uncertainty set with ϕ -divergence distance

We consider an uncertainty set defined using statistical distance metric called ϕdivergence. In such uncertainty set, a nominal distribution is known to the decision maker relied on the available estimated data. The decision maker thinks that the true distribution of R belongs to a ball of radius θ ϕ and centered at a nominal distribution ν and the distance between the true distribution and ν is given by a ϕ-divergence. We show that the DRCCMDP problem ( 5) is equivalent to an SOCP problem for various ϕ-divergences. Definition 1. The ϕ-divergence distance between two probability measures ν 1 and ν 2 with densities f ν1 and f ν2 , respectively, and full support R |W| is given by

I ϕ (ν 1 , ν 2 ) = R |W| ϕ f ν1 (ξ) f ν2 (ξ) f ν2 (ξ)dξ.
For different choices of ϕ, we refer to [START_REF] Ben-Tal | Robust solutions of optimization problems affected by uncertain probabilities[END_REF] and [START_REF] Pardo | Statistical Inference Based on Divergence Measures[END_REF]. Let ν ∈ M + be a nominal distribution with a density function f ν . The uncertainty set of the distribution of R based on ϕ-divergence is defined by

D 4 (ν, θ ϕ ) = F ∈ M + | I ϕ (F, ν) ≤ θ ϕ , (23)
where θ ϕ > 0. Definition 2. A function ϕ * : R → R ∪ ∞ is the conjugate of ϕ, where

ϕ * (r) = sup t≥0 {rt -ϕ(t)} , ∀ r ∈ R. Lemma 2. Consider an optimization problem inf F ∈D4(ν,θ ϕ ) P F (χ T R ≥ y). (24)
Then, the dual problem of (24) is given by

sup λ>0,β∈R β -λθ ϕ -λϕ * -1 + β λ P ν (O) -λϕ * β λ (1 -P ν (O)) ,
where O = ξ ∈ R |W| | χ T ξ ≥ y , such that the strong duality holds.

Proof. We rewrite the primal problem (24) as a following semi-infinite programming problem

v P = inf F ≥0 R |W| 1 O (ξ)F (ξ)dξ s.t. (i) R |W| f ν (ξ)ϕ F (ξ) f ν (ξ) dξ ≤ θ ϕ , (ii) R |W| F (ξ)dξ = 1. ( 25
)
The dual problem of ( 25) is given by

v D = sup λ≥0,β∈R β -λθ ϕ + inf F (ξ)≥0 R |W| 1 O (ξ)F (ξ) -βF (ξ) + λf ν (ξ)ϕ F (ξ) f ν (ξ) dξ ,
where λ is the dual variable of the constraint (i) of ( 25) and β is the dual variable of the constraint (ii) of ( 25). Since θ ϕ > 0, the Slater's condition holds which implies that the strong duality holds, i.e., v P = v D . The rest of the proof follows from Theorem 1 of [START_REF] Jiang | Data-driven chance constrained stochastic program[END_REF].

We study 4 cases of ϕ-divergences whose conjugates are given in Table 2. Using

ϕ(u), u ≥ 0 ϕ * (v) Kullback-Leibler u log(u) -u + 1. e v -1 Variation distance |u -1|. -1, v ≤ -1, v, -1 ≤ v ≤ 1, ∞, v > 1. Modified χ 2 -distance (u -1) 2 . -1, v ≤ -2, v + v 2 4 , v > -2.
Hellinger distance

( √ u -1) 2 . v 1-v , v < 1, ∞, v ≥ 1.
Lemma 2, the following result holds. Theorem 3. Consider the DRCCMDP problem (5), where the uncertainty set is defined by [START_REF] Singh | Distributionally robust chance-constrained games: Existence and characterization of Nash equilibrium[END_REF] for the ϕ-divergences listed in Table 3. If the reference distribution ν is a normal distribution with mean vector µ ν and positive definite covariance matrix Σ ν , the DRCCMDP problem (5) is equivalent to the following SOCP problem max y

s.t. (i) χ T µ ν -Φ (-1) [f (θ ϕ , ϵ)]∥Σ 1 2 ν χ∥ 2 ≥ y, (ii) χ ∈ Q α (ϱ), ( 26
)
where Φ (-1) is the quantile of the standard normal distribution and the values of θ ϕ , ϵ and f (θ ϕ , ϵ) for different choices of divergences are given in Table 3.

Table 3 The function f for selected ϕ-divergences

Divergence f (θ ϕ , ϵ) θ ϕ , ϵ K-L inf x∈(0,1) e -θ ϕ x 1-ϵ -1 x-1 θ ϕ > 0, 0 < ϵ < 1 Variation 1 -ϵ + θ ϕ 2 θ ϕ > 0, 0 < ϵ < 1 Modified χ 2 1 -ϵ + θ 2 ϕ +4θ ϕ (ϵ-ϵ 2 )-(1-2ϵ)θ ϕ 2θ ϕ +2 θ ϕ > 0, 0 < ϵ < 1 2 Hellinger -B+ √ ∆ 2 , where B = -(2 -(2 -θ ϕ ) 2 )ϵ - (2-θ ϕ ) 2 2 , C = (2-θ ϕ ) 2 4 -ϵ 2 , ∆ = B 2 -4C = (2 -θ ϕ ) 2 4 -(2 -θ ϕ ) 2 ϵ(1 -ϵ). 0 < θ ϕ < 2 - √ 2, 0 < ϵ < 1
Proof. Using Lemma 2, we prove that the constraint (i) of ( 5) is equivalent to the following constraint

P ν (χ T R ≥ y) ≥ f (θ ϕ , ϵ). ( 27
)
Since ν is a normal distribution with mean vector µ ν and covariance matrix Σ ν , it is well known that ( 27) is equivalent to the constraint (i) of ( 26). The Hellinger distance case proof is given in [START_REF] Nguyen | Distributionally robust chance-constrained zero-sum games with moments based and statistical based uncertainty sets[END_REF], where the Kullback-Leibler, Variation distance and Modified χ 2 -distance ones follow from Propositions 2, 3 and 4 of [START_REF] Jiang | Data-driven chance constrained stochastic program[END_REF].

Uncertainty set with Wasserstein distance

We consider an uncertainty set defined using statistical distance metric called Wasserstein distance. We show that the DRCCMDP problem ( 6) is tractable if the reference distribution ν follows a discrete distribution whose scenarios are taken from historical data. We refer to Villani [START_REF] Villani | Optimal Transport[END_REF][START_REF] Villani | Topics in Optimal Transportation[END_REF] for more details of the Wasserstein distance metric.

Let φ be a closed, convex subset of R |W| and p ∈ [1, ∞). Let B(φ) denotes the Borel σ-algebra on φ. Let P(φ) be the set of all probability measures defined on B(φ) and P p (φ) denote the subset of P(φ) with finite p-moment and it is defined as

P p (φ) = µ ∈ P(φ) | ξ∈φ ||ξ -ξ 0 || p 2 µ(dξ) < ∞ for some ξ 0 ∈ φ .
It follows from the triangle inequality that the above definition of P p (φ) does not depend on ξ 0 . Definition 3 (Wasserstein distance). The Wasserstein distance W p (µ, ν) between ν 1 , ν 2 ∈ P p (φ) is defined by

W p (ν 1 , ν 2 ) = inf ϱ∈Pν 1 ,ν 2 (φ×φ) φ×φ ||x -z|| p 2 ϱ(dx, dz) 1 p
, where P ν1,ν2 (φ × φ) denotes the set of all probability measures defined on B(φ × φ) such that the marginal laws are ν 1 and ν 2 .

The uncertainty set using Wasserstein distance is defined by

D 5 (φ, ν, p, θ W ) = {F ∈ P p (φ) | W p (F, ν) ≤ θ W } , (28)
where ν ∈ P p (φ) and θ W > 0. Lemma 3. Consider an optimization problem sup

F ∈D5(φ,ν,p,θ W ) P F (χ T R ≤ y). ( 29
)
Then, the dual problem of ( 29) is given by

inf λ≥0 λθ p W - φ inf z∈φ λ||x -z|| p 2 -1 {χ T z≤y} ν(dx) , (30)
such that the strong duality holds and the optimal values of the primal and the dual problems are finite.

Proof. Let Ξ be a Polish space with metric d, P(Ξ) be the set of Borel probability measures on Ξ, ν ∈ P(Ξ) and Ψ ∈ L 1 (ν), where L 1 (ν) represents the L 1 space of ν -measurable functions. It follows from Theorem 1 of [START_REF] Gao | Distributionally robust stochastic optimization with Wasserstein distance[END_REF] that the following strong duality holds sup

µ∈P(Ξ) Ξ Ψ(ξ)µ(dξ) | W p (µ, ν) ≤ θ W = inf λ∈R,λ≥0 λθ p W - Ξ inf ξ∈Ξ [λd p (ξ, ζ) -Ψ(ξ)] ν(dζ) < ∞, (31)
provided the growth factor given by Definition 4 of [START_REF] Gao | Distributionally robust stochastic optimization with Wasserstein distance[END_REF] is finite. We apply this result in our case by choosing Ξ = φ, d as an Euclidean metric and Ψ(ξ) = 1 {χ T ξ≤y} for all ξ ∈ φ. For this choice of Ψ(ξ), it is easy to see from Definition 4 of [START_REF] Gao | Distributionally robust stochastic optimization with Wasserstein distance[END_REF] that the growth factor is zero. Since ξ ∈ φ | χ T ξ ≤ y is a closed set, it is a Borel measurable set. Hence, it is clear that Ψ ∈ L 1 (ν) for all ν ∈ P(φ). Then, (31) reduces to sup

F ∈D5(φ,ν,p,θ W ) P F χ T R ≤ y = inf λ≥0 λθ p W - φ inf ξ∈φ λ||ζ -ξ|| p 2 -1 {χ T ξ≤y} ν(dζ) .
We consider the case when p = 1 and ν is a data-driven reference distribution, i.e., it is a discrete distribution with H scenarios ξ1 , . . . , ξH , where ξi ∈ φ, for every i = 1, . . . , H. Using Lemma 3, we propose a deterministic reformulation of the DRCCMDP problem [START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF]. Lemma 4. If the distribution of R belongs to the uncertainty set defined by (28), the DRCCMDP ( 6) can be reformulated equivalently as the following deterministic problem sup y

s.t. (i) θ W - 1 H H i=1 g i ≤ lϵ, (ii) inf z∈φ,χ T z≤y || ξi -z|| 2 ≥ l + g i , ∀ i = 1, . . . , H, (iii) l > 0, χ ∈ Q α (ϱ), g i ≤ 0, ∀ i = 1, . . . , H. (32)
Proof. Using Lemma 3, since ν is a discrete distribution with H scenarios ξ1 , ..., ξ H , the constraint (i) of ( 6) can be equivalently written as

λθ W - 1 H H i=1 inf z∈φ λ|| ξi -z|| 2 -1 {χ T z≤y} ≤ ϵ, λ ≥ 0.
By introducing auxiliary variables t i , i = 1, ..., H, the above constraint can be rewritten as

(i) λθ W -1 H H i=1 t i ≤ ϵ, λ ≥ 0 (ii) inf z∈φ λ|| ξi -z|| 2 -1 {χ T z≤y} ≥ t i , ∀ i = 1, . . . , H. (33)
The constraint (ii) of ( 33) is equivalent to the following two constraints

(i) inf z∈φ λ|| ξi -z|| 2 ≥ t i , ∀ i = 1, . . . , H, (ii) inf z∈φ,χ T z≤y λ|| ξi -z|| 2 -1 ≥ t i , ∀ i = 1, . . . , H. (34)
Since λ ≥ 0, inf z∈φ λ|| ξi -z|| 2 = 0. Then, the constraint (i) of (34) is equivalent to t i ≤ 0, for every i = 1, . . . , H. Moreover, if λ = 0, from the constraint (ii) of (34), t i ≤ -1, for every i = 1, . . . , H, which in turn implies -1 H H i=1 t i ≥ 1. This violates the constraint (i) of (33). Hence, λ > 0. Let l = 1 λ and g i = ti λ , for every i = 1, . . . , H. Therefore, the constraint (i) of ( 6) is equivalent to the following constraints

     (i) θ W -1 H H i=1 g i ≤ lϵ, (ii) inf z∈φ,χ T z≤y || ξi -z|| 2 ≥ l + g i , ∀ i = 1, . . . , H, (iii) l > 0, g i ≤ 0, ∀ i = 1, . . . , H. (35)
This implies that the DRCCMDP ( 6) is equivalent to [START_REF] Zhao | Data-driven risk-averse stochastic optimization with Wasserstein metric[END_REF].

The constraint (ii) of (32) includes inf term which makes it difficult to solve the problem directly. We show that the optimization problem ( 32) is equivalent to a MIS-OCP problem and a biconvex optimization problem for the case of full support and nonnegative support, respectively.

DRCCMDP under Wasserstein distance based uncertainty

set with full support Theorem 4. Consider the DRCCMDP problem (6). We assume that the distribution of R belongs to the uncertainty set defined by (28) and φ = R |W| . Then, the DRCCMDP problem (6) is equivalent to the following MISOCP max y

s.t. (i) βθ W - 1 H H i=1 b i ≤ tϵ, (ii) M η i ≥ b i + t, ∀ i = 1, . . . , H, (iii) M (1 -η i ) + χ T ξi -y ≥ b i + t, ∀ i = 1, . . . , H, (iv) η i ∈ {0, 1} , ∀ i = 1, . . . , H, (v) ||χ|| 2 ≤ β, t ≥ 0, β > 0, χ ∈ Q α (ϱ), b i ≤ 0, ∀ i = 1, . . . , H. (36)
Proof. The proof follows from Theorem 2 [START_REF] Xie | On distributionally robust chance constrained programs with wasserstein distance[END_REF].

DRCCMDP under

The dual problem of (37) is given by

max λ i (χ T ξi -y) -ζ T i ξi s.t. ||ζ i -λ i χ|| 2 ≤ 1, ζ i ∈ R |W| + , λ i ≥ 0,
such that the strong duality holds.

Proof. The proof is given in Appendix B. Theorem 5. Consider the DRCCMDP problem [START_REF] Delage | Distributionally robust optimization under moment uncertainty with application to data-driven problems[END_REF]. We assume that the distribution of R belongs to the uncertainty set defined by (28) and φ = R |W| + . Then, the DRCCMDP ( 6) is equivalent to the following biconvex optimization problem

max y s.t. (i) θ W - 1 H H i=1 g i ≤ lϵ, (ii) λ i (χ T ξi -y) -ζ T i ξi ≥ l + g i , ∀ i = 1, . . . , H, (iii) ||ζ i -λ i χ|| 2 ≤ 1, ∀ i = 1, . . . , H, (iv) λ i ≥ 0, ζ i ∈ R |W| + , l > 0, g i ≤ 0, χ ∈ Q α (ϱ), ∀ i = 1, . . . , H. (38)
Proof. The proof follows directly from Lemma 4 and Lemma 5.

Machine replacement problem

In this section, we address a machine replacement problem which involves a factory machine with a lifespan of N years. At each stage, maintenance is scheduled for the machine , and the factory owner must decide whether to repair it or leave it unrepaired.

If repaired, the machine might function as a new one, while not repairing it reduces its remaining lifespan by one year. Repairing the machine incurs a maintenance cost, which can be modeled as an MDP problem with the machine's lifespan representing the states of the underlying Markov chain, resulting in a total of N + 1 states. The initial state corresponds to a new machine, and at each state, there are two actions: i) "repair" and ii) "do not repair". The transition probabilities of the Markov chain corresponding to each action, are detailed in Figure 5. The maintenance cost for each state-action pair is uncertain and realized after the decision is decided. For every stateaction pair (s, a), the maintenance cost is defined as ĉ(s, a) = K + Ẑ(s, a), with K representing a fixed cost and Ẑ(s, a) representing a random variable for the variable cost. Additionally, the machine generates revenue L(s, a) for each state-action pair (s, a) and the profit for each (s, a) ∈ W is given by

R(s, a) = L(s, a) -K -Ẑ(s, a). (39)
The factory owner aims to maximize the expected discounted profit. We assume that the factory owner possesses a finite number of identical machines, all of which are modeled using the same Markov chain. Consequently, we calculate the optimal repair policy for a single machine, and this identical repair policy can be applied to all other machines in the fleet.

Fig. 1 Machine replacement with 10 states and 2 actions: "repair" (with continuous lines) and "no repair" (with dotted lines)

We compare the performance of DRCCMDP for each uncertainty set with the CCMDP model ( 4) where the distribution of R is assumed to be a normal distribution. In our numerical experiments, we consider a set of 10 states, ϵ = 0.15, the discount parameter α = 0.8 and the initial distribution of states ϱ to be uniformly distributed. For the above instance, |W| = 20 and R is a 20 × 1 random vector with mean vector µ given by µ(s, a) = L(s, a) -K -µ Ẑ (s, a),

where µ Ẑ is the mean vector of the random cost vector Ẑ. We take K = 10, the function L and the mean cost µ Ẑ corresponding to each state-action pair are summarized in Table 4. The covariance matrix Σ of R is randomly generated using the following formula

Σ = AA T 20 + D 20 , (41)
K-U δ 0 = 0.9 U-U δ 1 = δ 2 = 1 ϕ-divergence θ ϕ = 0.01 Wasserstein θ W = 0.01 H = 1000
set, we take the nominal distribution ν as a normal distribution with mean µ ν = µ and covariance matrix Σ ν = Σ where µ and Σ are defined by ( 40) and (41), respectively. For Wasserstein distance based uncertainty set, we take the number of observations H = 1000. The scenarios ( ξi ) H i=1 are randomly generated by taking ξi = Bx + µ ν , where x is a standard normal vector, µ ν is defined by (40) and B is the Cholesky factorization of Σ ν defined by (41). We summarize the other parameters in Table 5.

We compute an optimal policy of the CCMDP problem (4), where R follows a normal distribution with mean vector and covariance matrix defined by ( 40) and (41), Kullbach-Leibler (1-q,q)

Policies CCMDP Normal (1-q,q) Full support K-K (1-q,q) Full support K-U (1-q,q) Full support U-U (1-q,q) Modified χ 2 (1-q,q) variation (1-q,q) 1 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 2 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 3 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 4 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 5 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 6 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 7 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 8 (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) 9 ( 1
Hellinger (1-q,q)

Full support Wasserstein (1-q,q) by solving an equivalent SOCP problem [START_REF] Delage | Percentile optimization for Markov decision processes with parameter uncertainty[END_REF]. The optimal policies of the DRCCMDP problem for all the uncertainty sets are computed by solving the proposed equivalent optimization problems. We present the optimal policies of CCMDP and DRCCMDP with full support and nonnegative support in Tables 6 and7, where q is the probability of "repair" and 1 -q is the probability of "no repair". It is clear from Tables 6 and7 that the optimal repair policy corresponding to all the uncertainty sets for first eight states is same. At state 9 the probability of repair is greater than the probability of do not repair for moments based uncertainty sets whereas for statistical distance based uncertainty sets the probability of repair is less than the probability of do not repair. By comparing the optimal discounted reward of all uncertainty models with the CCMDP model, it is easy to see that the statistical distance based uncertainty sets give better optimal policy as compared to moments based uncertainty sets and the nonnegative support uncertainty sets give better optimal policy as compared to full support uncertainty sets. At the last state, the optimal policy is to choose repair action with a very high probability for all the uncertainty sets. We conduct a time analysis by examining the number of states within the range of 1000 to 10000 for all uncertainty sets. All the parameters are taken similar to the case of 10 states. The results are presented in Figure 5 which shows that the CPU time is almost always the same to solve SOCP [START_REF] Henrion | Structural properties of linear probabilistic constraints[END_REF] with κ = 1-ϵ ϵ and the MISOCP (36) while additional CPU time is required to solve the SDP + LP relaxations of the copositive optimization problem [START_REF] Hiriart-Urruty | A variational approach to copositive matrices[END_REF] and the biconvex optimization problem (38).

Nonnegative K-K (1-q,q) Nonnegative K-U (1-q,q) Nonnegative U-U (1-q,q) Nonnegative Wasserstein (1-q,q) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (1, 0) (0.

Conclusions

We consider a DRCCMDP problem under various uncertainty sets. We propose equivalent SOCP, MISOCP, copositive optimization problem and biconvex optimization problem, depending on the choice of the uncertainty set, for the DRCCMDP problem. All these optimization problems except biconvex optimization problems and copositive optimization problems can be solved efficiently using known optimization solvers. We perform numerical experiments, using the optimization solvers in python, on a machine replacement problem using randomly generated data. The numerical experiments are performed on the DRCCMDP problem up to 10000 states and it is very clear from our time analysis that these problems can be solved very efficiently.

(iii) µ ≤ φ RdF (R) ≤ µ + x j .

(45)

The dual problem of (45) is given by

v j D (µ, Σ) = inf -t -Q • Σ + (r -h) T µ + r T x j s.t. (i) 1 {χ T ξ≤y} + (h -r) T ξ + ξ T Qξ -2ξ T Qµ + µ T Qµ + t ≤ 0, ∀ ξ ∈ R |W| + , (ii) h, r ∈ R |W| + , Q ∈ S |W| , (46)
where t, Q, r and h are the dual variables of the constraint (i), (ii) and (iii) of (45), respectively. The vector (t, Q, h, r) such that t = t * j , Q = Q * j , h = max(0, q * j ), r = r * j is a feasible solution of (46). Hence,

v j D (µ, Σ) ≤ -t * j -Q * j • Σ -q * T j µ + r * T j x j , ∀ j ∈ N. ( 47
)
Since the feasibility set of ( 14) is non-empty, there exists a nonnegative distribution F * such that E(F * ) = µ and Cov(F * ) = Σ. Let F j be a distribution with support φ j := ξ ∥ ξ ∈ R W + , ξ ≥ xj 2 , componentwise , defined by

F * (ξ) = F j (ξ + x j 2 ), ∀ ξ ∈ R W + .
It is clear that F j is a feasible solution of (45) and φ j ⊂ RI(φ). Hence, F j belongs to the relative interior of the distributional uncertainty set which implies that strong duality holds, i.e., v j P (µ, Σ) = v j D (µ, Σ) for all j ∈ N. Since the objective function of (45) is a continuous function of F and x j → 0 as j → ∞, then v j P (µ, Σ) → v P (µ, Σ) as j → ∞. Therefore, it is sufficient to prove that v j D (µ, Σ) → v D (µ, Σ) as j → ∞. It is clear that the feasible sets of ( 46) and ( 43) are equivalent and objective function of (46) has additional positive term. Therefore, v j D (µ, Σ) ≥ v D (µ, Σ), ∀ j ∈ N.

(48)

Using (44), (47) and (48) and the fact that r * T j x j → 0 as j → ∞, we have v j D (µ, Σ) → v D (µ, Σ) as j → ∞.

It is easy to see that J(λ i , ζ i , β) = -∞ if β ̸ = 1 and it implies that the dual objective function value is -∞. By using the strong duality of a primal-dual pair of SOCPs, the objective function value of primal problem is -∞, i.e., inf z∈R |W| + ,χ T z≤y || ξi -z|| 2 = -∞ which is a contradiction. Therefore, β = 1 and using a change of variable z 1 = ξi -z, we have

J(λ i , ζ i , 1) = min z1∈R |W| ||z 1 || 2 + (ζ i -λ i χ) T z 1 + λ i (χ T ξi -y) -ζ T i ξi .
The above minimization problem is unbounded unless ||ζ i -λ i χ|| 2 ≤ 1 and it leads to the following dual problem of (49).

max λ i (χ T ξi -y) -ζ T i ξi s.t. ||ζ i -λ i χ|| 2 ≤ 1, λ i ≥ 0, ζ i ∈ R |W| + . (51)

Wasserstein distance based uncertainty set with nonnegative support Lemma 5 .

 5 Let φ = R |W| + and consider an optimization problem inf z∈φ,χ T z≤y || ξi -z|| 2 .

where A is a 20 ×

 20 20 random matrix whose all the entries are real numbers belonging to [0, 1], and D 20 is a 20 × 20 diagonal matrix with D 20 (10, 10) = 4, D 20 (20, 20) = 9, D 20 (i, i) = 1, for every i ̸ = 10, 20 and all other entries equal to zero. We use the above µ and Σ for all the moments based uncertainty sets. For ϕ-divergence based uncertainty

Fig. 2

 2 Fig. 2 CPU time (in seconds) to solve SOCP (10) with κ = 1-ϵ ϵ , MISOCP (36), copositive optimization problem (11) and biconvex optimization problem (38) with different number of states.

  that: L = sup β<λ,λ>0 λ 2 (λ-β)(λ-β+1) P ν (O) -β 2 λ-β -λθ ϕ . Let η = λ -β.Then, we can write B Proof of Lemma 5

  1 2 i ||ξ D || 2 2 → ∞ and the other terms are lower bounded by some nonnegative number. Therefore, s D → ∞ when ||ξ D || 2 → ∞. Hence, ||ξ D || 2 is bounded by some real number Υ D > 0 which depends on U i , χ i and y. Let Υ = max(Υ P , Υ D ). Then, (17) is equivalent to

	s P =	ξ∈R	min |W| + ,||ξ||2≤Υ	max λ≥0	L(λ, ξ, U i , χ i , y).
	s D = max λ≥0	min |W| ξ∈R + ,||ξ||2≤Υ

Table 2

 2 List of selected ϕ-divergences with their conjugate

	Divergence

Table 4

 4 Random cost Ẑ and Revenue L

	State(s)	Action(a) "Repair" µ Ẑ (s, 1)	"Do not repair" µ Ẑ (s, 2)	"Repair" L(s, 1)	"Do not repair" L(s, 2)
		1	10.1	0	30	29.9
		2	10.2	0	30	29.8
		3	10.3	0	30	29.7
		4	10.4	0	30	29.6
		5	10.5	0	30	29.5
		6	10.6	0	30	29.4
		7	10.7	0	30	29.3
		8	10.8	0	30	29.2
		9	10.9	0	30	29.1
	10	11	5	30	29.0

Table 5

 5 Other parameters

Table 6

 6 Optimal policies of CCMDP and DRCCMDP with full and nonnegative supports

	State(s)

Table 7

 7 Optimal policies of CCMDP and DRCCMDP with full and nonnegative supports (continued)

		, 0)	(0.36, 0.64)	(0.36, 0.64)	(0.3, 0.7)	(0.73, 0.27)	(0.95, 0.05)
	10	(0.1, 0.9)	(0.09, 0.91)	(0.09, 0.91)	(0.09, 0.91)	(0.1, 0.9)	(0.1, 0.9)
	Optimal discounted reward	89.3	74	74	71.9	84.2	88.1

  The optimization problem inf z∈R |W| + ,χ T z≤y || ξi -z|| 2 can be reformulated as following SOCP problem min ts.t. χ T z ≤ y, t ≥ || ξi -z|| 2 , z ∈ R (t, χ, z, λ i , β, ζ i ), where L(t, z, λ i , β, ζ i ) = t+λ i (χ T z-y)-ζ T i z+β(|| ξi -z|| 2 -t).The inner minimization problem can be written asJ(λ i , ζ i , β) = min t∈R,z∈R |W| t(1 -β) + β|| ξi -z|| 2 + λ i χ T z -ζ T i z -λ i y .

	The Lagrangian dual problem of (49) is given by
	max	min
	λi≥0,ζi∈R	|W| + ,β≥0	t∈R,z∈R |W|
			|W| + .	(49)

L

Acknowledgement

This research was supported by the French government under the France 2030 program, reference ANR-11-IDEX-0003 within the OI H-Code.

Compliance with Ethical Standards

The authors have no relevant financial or non-financial interests to disclose.

A Proof of Lemma 1

Consider the optimization problem

where C + is the set of all positive measures on R |W| + . The dual problem of (42) is given by

where t, q, and Q are the dual variables associated with the constraints (i), (ii) and (iii) of (42), respectively. In Theorem 3.4 of [START_REF] Cheng | Distributionally robust stochastic knapsack problem[END_REF], under the assumption µ ∈ RI(φ), the authors show that the Dirac distribution δ µ lies in the relative interior of the distributional uncertainty set which implies that the weaker condition of Proposition 3.4 of [START_REF] Shapiro | On duality theory of conic linear problems[END_REF] holds. However, it is not trivial to find a strictly feasible point inside our distributional uncertainty set. Let (t * j , Q * j , q * j ) j∈N be a sequence of feasible solutions of (43) such that

For each j ∈ N, let r * j = max(0, q * j ) -q * j , where max(0, q * j ) denotes a |W|-dimensional vector with i th component equal to the maximum value between 0 and the i th component of q * j , for every i = 1, . . . , |W|. Let ϵ j be a strictly positive decreasing sequence such that ϵ j r * j → 0 componentwise and ϵ j → 0, when j → ∞. Let x j = ϵ j 1, where 1 denotes the vector with all components equal to 1. Then, r * T j x j → 0 as j → ∞. For each j ∈ N, consider the following conic optimization problem v j P (µ, Σ) = sup