Zero-Sum Games for Continuous-time Markov decision processes with risk-sensitive average cost criterion

Markov decision processes (MDPs) are widely used for modeling control problems that arise naturally in many real-life problems, for example in queueing models, epidemiology models, birth-death models etc, see [5], [16], [31], [32]. When there is more than one controller (or player) the stochastic control problem is referred to as stochastic game problem. Stochastic dynamic game was first introduced in [33] and has been studied extensively in the literature due to its immense applications; see [3], [6], [10], [11], [15], [34], [37], [38] and the references therein. In this article we consider the risk-sensitive ergodic zero-sum game for continuous-time Markov decision processes (CTMDPs). In zero-sum game, one player is trying to minimize her/his cost and the other player is trying to maximize the same. In literature, the expected average cost criterion is a commonly used optimality criterion in the theory of CTMDPs and has been widely studied under the different sets of optimality conditions; for control problems see, [16], [39] and the references therein; for game problems see [13], [20], [35] and the references therein. In these papers the decision-makers are risk-neutral. However, risk preferences may vary from person to person in the real-world applications. In order to address this concern one of the approaches that is available in the literature is risk-sensitive criterion. In this criterion one investigates the expectation of an exponential of the random quantity. This takes into account the attitude of the controller with respect to risk. The performance of a pair of strategies is measured by risk-sensitive average cost criterion, which in our present case is defined by (2.4), below. The analysis of risk-sensitive control is technically more involved because of the exponential nature of the cost. The risk-sensitive average cost stochastic optimal control problems for CTMDPs were first considered in [9] and have been studied extensively in the literature due to its applications in finance and large deviation theory. Recently, there has been an extensive work on risk-sensitive average cost criterion problems for CTMDPs; see, for example [7], [14], [25], [26], [28] and the references therein. The risk-sensitive stochastic zero-sum games for MDPs have been studied in [[3], [6], [10], [11], [37]] and [[4], [24], [36]] consider the nonzero-sum games for MDPs. In [[3], [6]], the authors study zero-sum risk-sensitive stochastic games for discrete time MDPs with bounded cost. Both of the papers considered first the discounted cost and then ergodic cost. In [6], the authors extended the results of [3] to the general state space case. The zero-sum risk-sensitive average games have been studied in [10] and discounted risk-sensitive zero-sum games were studied in [29] for CTMDPs with bounded cost and transition rates. But this boundedness requirement restricts our domain of application, since in many real-life situations we see that the reward/cost and transition rates are unbounded as for example in queueing, telecommunication and population processes. In [11] and [37], the authors study finite horizon zero-sum risk-sensitive continuous-time stochastic games. In [11], unbounded costs and transition rates are considered while [37] considers unbounded transition but bounded cost. The discounted risk-sensitive zero-sum game for CTMDPs was studied in [12] with unbounded cost and transition rates.

Here we study zero-sum ergodic risk-sensitive stochastic games for CTMDPs having the following features: (a) transition and cost rates may be unbounded (b) state space is countable (c) at any state of the system the space of admissible actions is compact (d) the strategies may be history dependent. To the best of our knowledge, this is the first work which deals with infinite horizon continuous-time zero-sum risk-sensitive stochastic games for ergodic criterion on countable state space for unbounded transition and cost rates. Under a Lyapunov stability condition, we prove the existence of a saddle-point equilibrium in the class of stationary strategies. Using Krein-Rutman theorem, we first prove that the corresponding HJI equation has a unique solution for any finite subset of the state space. Then using the Lyapunov stability condition, we establish the existence of a unique solution for the corresponding HJI equation on the whole state space. Also we give a complete characterization of saddle point equilibrium in terms of the corresponding HJI equation.

The rest of this article is arranged as follows. Section 2 gives the description of the problem and assumptions. We also show in this section that the required risk-sensitive optimality equation (HJI equation) has a solution. In Section 3, we completely characterize all possible saddle point equilibria in the class of stationary Markov strategies. In Section 4, we present an illustrative example.

In this section we introduce the continuous-time zero-sum stochastic game model described by the following elements

where

• •

  $S$, called the state space, is the set of all nonnegative integers.

• •

  $A$ and $B$ are the action sets for players 1 and 2, respectively. The action spaces $A$ and $B$ are assumed to be Borel spaces with the Borel $\sigma$-algebras $\mathcal{B}(A)$ and $\mathcal{B}(B)$, respectively.

• •

  For each $i\in S$, $A(i)\in\mathcal{B}(A)$ and $B(i)\in\mathcal{B}(B)$ denote the sets of admissible actions for players 1 and 2 in state $i$, respectively. Let $K:=\{(i,a,b)|i\in S,a\in A(i),b\in B(i)\}$, which is a Borel subset of $S\times A\times B$. Throughout this paper, we assume that the admissible action spaces $A(i)(\subset A)$ and $B(i)(\subset B)$ are compact for each $i$.

• •

  Given any $(i,a,b)\in K$, the transition rate $q(j|i,a,b)$ is a signed kernel on $S$ such that $q(j|i,a,b)\geq 0$ for all $j,i\in S$ with $j\neq i$. Moreover, we assume that $q(j|i,a,b)$ satisfies the following conservative and stable conditions: for any $i\in S,$

  	$\displaystyle\sum_{j\in S}q(j|i,a,b)=0~{}\text{for all}~{}(a,b)\in A(i)\times B(i)~{}~{}~{}\text{and}$
  	$\displaystyle~{}q^{*}(i):=\sup_{(a,b)\in A(i)\times B(i)}q(i,a,b)<\infty,$		(2.2)

  where $q(i,a,b):=-q(i|i,a,b)\geq 0.$

• •

  Finally, the measurable function $c:K\to\mathbb{R}_{+}$ denotes the cost rate (representing cost for player 2 and payoff for player 1).

The game evolves as follows. The players observe continuously the current state of the system. When the system is in state $i\in S$ at time $t\geq 0$, the players independently choose actions $a_{t}\in A(i)$ and $b_{t}\in B(i)$ according to some strategies, respectively. As a consequence of this, the following happens:

• •

  player 2 pays an immediate cost at rate $c(i,a_{t},b_{t})$ to player 1;

• •

  the system stays in state $i$ for a random time, with rate of leaving $i$ given by $q(i,a_{t},b_{t})$, and then jumps to a new state $j\neq i$ with the probability determined by $\dfrac{q(\cdot|i,a_{t},b_{t})}{q(i,a_{t},b_{t})}$ (see Proposition in [[16], p. 205] for details).

When the state of the system transits to a new state $j$, the above procedure is repeated.

The goal of player 2 is to minimize his/her accumulated cost, whereas player 1 tries to maximize the same with respect to some performance criterion $J(\cdot,\cdot,\cdot,\cdot)$, which in our present case is defined by (2.4), below. Such a model is relevant in worst-case scenarios, e.g., in financial applications when a risk-averse investor is trying to maximize his long-term portfolio gain against the market which, by default, is the minimizer in this case.

To formalize what is described above, below we describe the construction of continuous time Markov decision processes (CTMDPs) under possibly admissible history-dependent strategies. To construct the underlying CTMDPs (as in [[19], [22], [30]]), we introduce some notations: let $S_{\Delta}:=S\cup\{\Delta\}$ (with some $\Delta\notin S$), $\Omega^{0}:=(S\times(0,\infty))^{\infty}$, $\Omega:=\Omega^{0}\cup\{(i_{0},\theta_{1},i_{1},\cdots,\theta_{k},i_{k},\infty,\Delta,\infty,\Delta,\cdots)|i_{l}\in S,\theta_{l}\in(0,\infty),$ for each $0\leq l\leq k,k\geq 0\}$, and let $\mathscr{F}$ be the Borel $\sigma$-algebra on $\Omega$. Then we obtain the measurable space $(\Omega,\mathscr{F})$. For each $k\geq 0$, $\omega:=(i_{0},\theta_{1},i_{1},\cdots,\theta_{k},i_{k},\cdots)\in\Omega,$ define $T_{0}(\omega):=0$, $T_{k}(\omega):=T_{k-1}(\omega)+\theta_{k}$, $T_{\infty}(\omega):=\lim_{k\rightarrow\infty}T_{k}(\omega)$. Using $\{T_{k}\}$, we define the state process $\{\xi_{t}\}_{t\geq 0}$ as

Here, $I_{E}$ denotes the indicator function of a set $E$, and we use the convention that $0+z=:z$ and $0\cdot z=:0$ for all $z\in S_{\Delta}$. The process after $T_{\infty}$ is regarded to be absorbed in the state $\Delta$. Thus, let $q(\cdot|\Delta,a_{\Delta},b_{\Delta}):\equiv 0$, $A_{\Delta}:=A\cup\{a_{\Delta}\}$, $B_{\Delta}:=B\cup\{b_{\Delta}\}$, $A(\Delta):=\{a_{\Delta}\}$, $B(\Delta):=\{b_{\Delta}\}$, $c(\Delta,a,b):\equiv 0$ for all $(a,b)\in A_{\Delta}\times B_{\Delta}$, where $a_{\Delta}$, $b_{\Delta}$ are isolated points. Moreover, let $\mathscr{F}_{t}:=\sigma(\{T_{k}\leq s,\xi_{T_{k}}\in D\}:D\in\mathcal{B}(S),0\leq s\leq t,k\geq 0)$ for all $t\geq 0$, $\mathscr{F}_{s-}=:\bigvee_{0\leq t<s}\mathscr{F}_{t}$, and $\mathscr{P}:=\sigma(\{A\times\{0\},A\in\mathscr{F}_{0}\}\cup\{B\times(s,\infty),B\in\mathscr{F}_{s-}\})$ which denotes the $\sigma$-algebra of predictable sets on $\Omega\times[0,\infty)$ related to $\{\mathscr{F}_{t}\}_{t\geq 0}$.

In order to define the risk sensitive cost criterion, we need to introduce the definition of strategy below.

The set of all admissible history-dependent strategies for player 1 is denoted by $\Pi^{1}$. A strategy $\pi^{1}\in\Pi^{1}$ for player 1, is called a Markov if $\pi^{1}(da|\omega,t)=\pi^{1}(da|\xi_{t-}(w),t)$ for every $w\in\Omega$ and $t\geq 0$, where $\xi_{t-}(w):=\lim_{s\uparrow t}\xi_{s}(w)$. A Markov stragegy $\pi^{1}$ is called a stationary Markov strategy if $\pi^{1}$ does not have explicit dependence on time. We denote by $\Pi^{m}_{1}$ and $\Pi^{s}_{1}$ the family of all Markov strategies and stationary Markov strategies, respectively, for player 1. The sets of all admissible history-dependent strategies $\Pi^{2}$, all Markov strategies $\Pi^{m}_{2}$ and all stationary strategies $\Pi^{s}_{2}$ for player 2 are defined similarly.

For any compact metric space $Y$, let $P(Y)$ denote the space of probability measures on $\mathcal{B}(Y)$ with Prohorov topology. Since for each $i\in S$, $A(i)$ and $B(i)$ are compact sets, $P(A(i))$ and $P(B(i))$ are compact metric spaces. For each $i,j\in S$, $\mu\in P(A(i))$ and $\nu\in P(B(i))$, the associated cost and transition rates are defined, respectively, as follows:

Note that $\pi^{1}\in{\Pi_{1}^{s}}$ can be identified with a map $\pi^{1}:S\to{P}(A)$ such that $\pi^{1}(\cdot|j)\in{P}(A(j))$ for each $j\in S$. Thus, we have $\Pi_{1}^{s}=\displaystyle\Pi_{i\in S}{P}(A(i))$ and $\Pi_{2}^{s}=\displaystyle\Pi_{i\in S}{P}(B(i))$. Therefore by Tychonoff theorem, the sets ${\Pi_{1}^{s}}$ and ${\Pi_{2}^{s}}$ are compact metric spaces. Also, note that under Assumption 2.1 (given below) for any initial state $i\in S$ and any pair of strategies $(\pi^{1},\pi^{2})\in\Pi^{1}\times\Pi^{2}$, Theorem 4.27 in [23] yields the existence of a unique probability measure denoted by $P^{\pi^{1},\pi^{2}}_{i}$ on $(\Omega,\mathscr{F})$. Let $E^{\pi^{1},\pi^{2}}_{i}$ be the expectation operator with respect to $P^{\pi^{1},\pi^{2}}_{i}$. Also, from [[16], pp.13-15], we know that $\{\xi_{t}\}_{t\geq 0}$ is a Markov process under any $(\pi^{1},\pi^{2})\in\Pi^{m}_{1}\times\Pi^{m}_{2}$ (in fact, strong Markov). Now we give the definition of the risk-sensitive average cost criterion for zero-sum continuous-time games. Since the risk-sensitive parameter remains fixed throughout we assume without any loss of generality that the risk-sensitivity coefficient $\theta=1$. For each $i\in S$ and any $(\pi^{1},\pi^{2})\in\Pi^{1}\times\Pi^{2}$, the risk-sensitive ergodic cost criterion is given by

Player 1 tries to maximize the above over his/her admissible strategies whereas player 2 tries to minimize the same. Now we define the lower/upper value of the game. The functions on S defined by $L(i):=\displaystyle\sup_{\pi^{1}\in\Pi^{1}}\inf_{\pi^{2}\in\Pi^{2}}J(i,c,\pi^{1},\pi^{2})$ and $U(i):=\displaystyle\inf_{\pi^{2}\in\Pi^{2}}\sup_{\pi^{1}\in\Pi^{1}}J(i,c,\pi^{1},\pi^{2})$ are called, respectively, the lower value and the upper value of the game. It is easy to see that

Next we list the commonly used notations below:

• •

  For any finite set $\mathcal{D}\subset S$, we define $\mathcal{B}_{\mathcal{D}}=\{f:S\to\mathbb{R}\mid\,\,f(i)=0\,\,\,\forall\,\,i\in\mathcal{D}^{c}\}$ .

• •

  $\mathcal{B}_{\mathcal{D}}^{+}\subset\mathcal{B}_{\mathcal{D}}$ denotes the cone of all nonnegative functions vanishing outside $\mathscr{D}.$

• •

  Given any real-valued function $\mathcal{V}\geq 1$ on $S$, we define a Banach space $(L^{\infty}_{\mathcal{V}},\|\cdot\|^{\infty}_{\mathcal{V}})$ of $\mathcal{V}$-weighted functions by

  $$L^{\infty}_{\mathcal{V}}=\biggl{\{}u:S\rightarrow\mathbb{R}\mid\|u\|^{\infty}_{\mathcal{V}}:=\sup_{i\in S}\frac{|u(i)|}{\mathcal{V}(i)}<\infty\biggr{\}}.$$

• •

  $\|c\|_{\infty}:=\displaystyle\sup_{(i,a,b)\in K}c(i,a,b)$.

• •

  For any function $f\in\mathcal{B}_{\mathcal{D}}$, $\|f\|_{\mathcal{D}}=\max\{|f(i)|:i\in\mathcal{D}\}$.

• •

  For any finite set $\mathscr{B}\subset S$, $\tilde{\tau}(\mathscr{B}):=\inf\{t>0:\xi_{t}\in\mathscr{B}\}$.

Our main goal is to establish the existence of a saddle-point equilibrium among the class of admissible history-dependent strategies. To this end, following [3] and [7], we investigate the HJI equation given by

Here $\rho$ is a scalar and $\psi$ is an appropriate function. The above is clearly an eigenvalue problem related to a nonlinear operator on an appropriate space. By a nonlinear version of Krein-Rutman theorem, we first show that Dirichlet eigenvalue problem associated with the above equation admits a solution in the space of bounded functions. Then by using a suitable limiting argument we show that the above HJI equation admits a principal eigenpair in an appropriate space. Finally exploiting the HJI equation, we completely characterize all possible saddle-point equilibria in the space of stationary Markov strategies. This is a brief outline of our procedure of establishing a saddle point equilibrium. The details now follow.

Since the transition rates (i.e., $q(j|i,a,b)$ ) may be unbounded, to avoid the explosion of the state process $\{\xi_{t},t\geq 0\}$, the following assumption is imposed on the transition rates, which had been widely used in CTMDPs; see, for instance, [[17], [18], [19]] and references therein.

Throughout the rest of this article we are going to assume that Assumption 2.1 holds. Note that if $\sup_{i\in S}q^{*}(i)<\infty$ then Assumption 2.1 holds trivially. In this case we can choose $\tilde{V}$ to be a suitable constant.

Since we are allowing our transition and cost rates to be unbounded, to guarantee the finiteness of $J(i,c,\pi^{1},\pi^{2})$, we need the following Assumption.

We first construct an increasing sequence of finite subsets $\hat{\mathscr{D}}_{n}\subset S$ such that $\displaystyle\cup_{i=0}^{\infty}\hat{\mathscr{D}}_{n}=S$ and $i_{0}\in\hat{\mathscr{D}}_{n}$ for all $n\in\mathbb{N}$. Define $\tau_{n}:=\tau(\hat{\mathscr{D}}_{n}):=\inf\{t\geq 0:\xi_{t}\notin\hat{\mathscr{D}}_{n}\}$, first exit time from $\hat{\mathscr{D}}_{n}$.