{'fraction_non_alphanumeric': 0.06237996158770807, 'fraction_numerical': 0.01608514724711908, 'mean_word_length': 4.056241149099737, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Zero-sum risk-sensitive continuous-time stochastic games with unbounded payoff and transition rates and Borel spaces

We study a finite-horizon two-person zero-sum risk-sensitive stochastic game for continuous-time Markov chains and Borel state and action spaces, in which payoff rates, transition rates and terminal reward functions are allowed to be unbounded from below and from above and the policies can be history-dependent. Under suitable conditions, we establish the existence of a solution to the corresponding Shapley equation (SE) by an approximation technique. Then, by the SE and the extension of the Dynkin's formula, we prove the existence of a Nash equilibrium and verify that the value of the stochastic game is the unique solution to the SE. Moreover, we develop a value iteration-type algorithm for approaching to the value of the stochastic game. The convergence of the algorithm is proved by a special contraction operator in our risk-sensitive stochastic game. Finally, we demonstrate our main results by two examples.


Introduction
Markov chain is a fundamental model to formulate stochastic dynamic systems. Markov decision process (MDP) is an important methodology to study the performance optimization of stochastic dynamic systems with a single decision-maker [8,21,41]. The classical MDP theory usually focuses on the performance criteria of the discounted or average rewards. However, the risk-aware performance criterion is also important for decision-makers in specific scenarios, such as financial engineering. The risk-sensitive MDP is motivated by the seminal work of Howard and Matheson [31] and attracts continuous attention in the literatures, which involve various risk metrics, such as exponential utility function [19,24], variance [29,47], value at risk (VaR) [30], conditional VaR [6,32], percentile [14,17], and probability metrics [45].
When we further consider stochastic dynamic systems with multiple decision-makers, game theory is a typical framework. For stochastic games (also known as Markov games), Markov model is widely adopted since it has advantages of memoryless property to capture the system dynamics. The study of stochastic games is pioneered by the seminal work of Shapely [42] and can be divided into categories according to two-person or n-person, zerosum or nonzero-sum, discrete-time or continuous-time, static or dynamic, and other criteria.
A two-person zero-sum stochastic game is the mostly studied model since the gains of one player is exactly the loss of the other player. The Shapley equation is the fundamental concept to study the value of a stochastic game and to prove the existence of Nash equilibria [15,38].
Most studies on stochastic games focus on the discounted performance criterion since the associated contract operator is critical to prove the convergence of games. However, as aforementioned, risk-related performance metrics are also important for decision-making in game theory, especially considering the fact that human players are usually risk-averse in terms of gains but risk-seeking in terms of losses, as indicated by the prospect theory [34].
Although the risk-sensitive MDPs have been richly investigated, the study of risk-sensitive stochastic games seems to be relatively limited in the literatures, in which the risk metric is usually of the form of exponential utility function [31,33]. That is, let X be the accumulated discounted rewards, which is a random variable. The targeted risk metric is set as E[e θX ], instead of E[X] in risk-neutral regime, where θ is a risk-sensitive parameter and positive for risk-averse while negative for risk-seeking. With the Taylor expansion of 1 θ ln E[e θX ], we can see that the targeted metric takes into account both E[X] and D[X] simultaneously and is a proper performance metric for risk-aware decision-making problems [7,24].
For risk-sensitive discrete-time stochastic games, Basu and Ghosh study a two-person zero-sum stochastic game on the infinite horizon with discounted and ergodic payoff criteria, where the value of games and equilibria are proved by studying the Hamilton-Jacobi-Bellman-Isaacs (HJBI) equation [3]. They further extend the results to the cases with countable state space [4] and nonzero-sum games [5], respectively. Moreover, Baüerle and Rieder study a two-person zero-sum risk-sensitive discrete-time stochastic game with Borel state and action spaces and bounded rewards, where the existence of equilibria is proved and the value of the game is obtained by solving the Shapley equation under continuity and compactness conditions [7].
When the stochastic game is of continuous-time, Başar studies a class of nonzero-sum risk-sensitive differential games with parameterized nonlinear dynamics and parameterized cost functions, where the sensitivity of the Nash equilibrium is also studied from a viewpoint of optimal control [2]. Başar and his collaborators further extend the risk-sensitive differential game to a scenario with n-person in the model of mean-field, where a Hamilton-Jacobi-Bellman-Fleming equation is utilized to study the value of the game [43]. There are other excellent works on risk-sensitive differential games, just to name a few [9,11,16], where varied forms of HJBI equations are studied to prove the equilibrium of games. For the risksensitive stochastic games with continuous-time Markov chains, Ghosh, Kumarb and Pal [18] study infinite-horizon discounted and ergodic cost risk-sensitive zero-sum stochastic games for countable Markov chains and bounded transition/cost rates, and prove the existence of the value and saddle-point equilibrium in the class of Markov strategies under suitable conditions. For the case of unbounded transition rates, Wei studies a zero-sum game with continuous-time Markov jump processes under the risk-sensitive finite-horizon criterion with bounded costs [44]. However, there is no study about risk-sensitive stochastic games with unbounded payoff rates and general spaces, which is still an open problem as pointed out by [44].
In this paper, we study a two-person zero-sum continuous-time stochastic game with exponential utility function, where the state and action spaces are Borel and the payoff rate, transition rates and terminal reward functions are unbounded. We study this game in the history-dependent policy space. We first establish the corresponding Shapley equation for this game and study the existence of the solution with an approximation technique. Then we further prove the existence of the Nash equilibrium with Markov policies by utilizing the Shapley equation and the extension of the Dynkin's formula. We also verify that the value of the game is the unique solution to the Shapley equation. Moreover, we develop a value iteration-type algorithm to approach to the solution to the Shapley equation, by iteratively solving a series of matrix games with linear programming techniques. Finally, we give two examples to demonstrate the main results of our paper. The main contribution of this paper is that it is the first work to study the risk-sensitive stochastic game with Borel spaces and unbounded transition and payoff rates, which is the most general model compared with the literature work like [7,44] and answers the open problem raised by [44]. Another noteworthy contribution is that an iteration algorithm is developed in this paper to compute the Nash equilibrium of the risk-sensitive stochastic game, which is important while rarely presented in the literature work. We also guarantee the convergence of the iteration algorithm by a special contraction operator in the risk-sensitive stochastic game. Since the contraction operator in our game model is not a one-step contraction operator widely used in discounted MDPs, the convergence proof is not trivial and may shed some light on the computation issues of risk-sensitive stochastic games.
The rest of the paper is organized as follows. In Section 2, we introduce the model formulation of risk-sensitive continuous-time stochastic games (CTSGs). After giving technical preliminaries in Section 3, we derive the main results of this paper in Section 4. In Section 5, we develop a value iteration-type algorithm for solving the value and the Nash equilibrium of the game and prove the convergence. In Section 6, we verify the main results by two examples. Finally, we conclude this paper in Section 7.

The model of stochastic games
Notation: For any Borel space X endowed with the Borel σ-algebra B(X), we will denote by I E the indicator function on any subset E of X, by δ z (dx) the Dirac measure at point z ∈ X, by B 1 (X) the set of all bounded Borel measurable functions u on X with the norm u := sup x∈X |u(x)|, and by P (X) the set of all probability measures on B(X).
The model of two-person zero-sum risk-sensitive stochastic games for continuous-time Markov chains is a five-tuple as below.
consisting of the following elements: (a) a Borel space S, called the state space of the games; (b) Borel spaces A and B for players 1 and 2 respectively, called the action spaces of the players in the games; A(x) and B(x) denote the sets of actions available to players 1 and 2 respectively when the system is at state x ∈ S; (c) a Borel measurable function r(x, a, b) on K, called the payoff rate, where K : the reward rate for player 1 and the cost rate for player 2; (d) transition rates q(dy|x, a, b), a Borel signed measure on B(S) given K, satisfying that q(D|x, a, b) ≥ 0 for all D ∈ B(S) with (x, a, b) ∈ K and x ∈ D, being conservative in the sense of q(S|x, a, b) ≡ 0, and stable in that of where q(x, a, b) := −q({x}|x, a, b) ≥ 0 for any (x, a, b) ∈ K; (e) the real-valued terminal reward function g(x) is measurable on S.
Next, we give an informal description of the evolution of CTSGs with model (2.1).
Roughly speaking, CTSGs evolve as follows: Two players observe states of a system continuously in time. If the system is at state x t at time t, player 1 chooses an action a t ∈ A(x t ) according to a given policy, player 2 chooses an action b t ∈ B(x t ) according to a given policy simultaneously, as a consequence of which, the following happens: (i) An payoff for player 1 takes place at the rate r(x t , a t , b t ); (ii) After a random sojourn time (i.e., the holding time at state x t ), the system jumps to a set D (x t ∈ D) of states with the transition probability q(D|xt,at,bt) q(xt,at,bt) determined by the transition rates q(dy|x t , a t , b t ). The distribution function of the sojourn time is (1 − e − t+δ t q(xs,as,bs)ds ), where δ is the sojourn time at state x t . To formalize what is described above, below we describe the construction of CTSGs under possibly randomized history-dependent policies.
To construct the process of the underlying dynamic game, we introduce some notations: k=0 Ω k , F the Borel σ-algebra on the Borel space Ω. Then, we obtain the measurable space (Ω, F ). For each k ≥ 1, and sample ω : In what follows, the argument ω is always omitted except some special informational statements. Then, we define the state process {x t , t ≥ 0} on (Ω, F ) by Obviously, x t (ω) is right-continuous on [0, ∞). We denote x t− (ω) := lim s→t− x s (ω). Here we have used the convenience that 0 × z = 0 and 0 + z = z for all z ∈ S ∆ := S ∪ {∆}. To precisely define the optimality criterion, we need to introduce the concept of a policy for each player below, which is an equivalent expression of that in [23,25,40].
We denote by Π 1 and Π m 1 the sets of all history-dependent policies π 1 and Markov ones respectively for player 1. The corresponding sets Π 2 and Π m 2 of all history-dependent policies and all Markov policies for player 2 are respectively defined similarly, with B(x) in lieu of For any initial distribution γ on S and pair of policies (π 1 , π 2 ) ∈ Π 1 × Π 2 , as shown by the Ionescu Tulcea theorem (e.g., Proposition 7.45 in [8]), we see that there exists a unique probability measure P π 1 ,π 2 γ (depending on γ and (π 1 , π 2 )) on (Ω, F ). Let E π 1 ,π 2 γ be the corresponding expectation operator. In particular, E π 1 ,π 2 γ and P π 1 ,π 2 γ are respectively written as E π 1 ,π 2 x and P π 1 ,π 2 x when γ is the Dirac measure at an initial state x in S.
Fix any finite horizon T > 0. For each pair of policies (π 1 , π 2 ) ∈ Π 1 × Π 2 and state x ∈ S, we define the T -horizon risk-sensitive value J(π 1 , π 2 , 0, x) of the continuous-time dynamic game by J(π 1 , π 2 , 0, x) := E π 1 ,π 2 γ e θ T 0 A×B r(xt,a,b)π 1 (da|ω,t)π 2 (db|ω,t)dt+θg(x T ) |x 0 = x , (2.5) provided that the integral is well defined, where θ is a constant called the risk-sensitive parameter. In the following arguments, we assume that θ > 0 which indicates a risk-averse preference. For the other case of θ < 0 with risk-seeking preference, the corresponding results can be obtained with r being replaced by −r, and thus the similar arguments are omitted.
As is well known, the functions on S defined as are called the lower value and the upper value of the stochastic game, respectively. It is clear that  . Then a policy π * 1 in Π 1 is said to be optimal for player 1 if Similarly, π * 2 ∈ Π 2 is optimal for player 2 if If π * k ∈ Π k is optimal for player k, k = 1, 2, then (π * 1 , π * 2 ) is called a Nash equilibrium of the game.
The aim of this paper is to give conditions for the existence and the computation of a Nash equilibrium.

Preliminaries
This section provides some preliminary facts for our arguments below. Since the transition rate q(dy|x, a, b) and payoff rate r(x, a, b) are allowed to be unbounded, we next give conditions for the non-explosion of {x t , t ≥ 0} and finiteness of J(π 1 , π 2 , 0, x). Assumption 3.1. There exist a real-valued Borel measurable function V 0 (x) ≥ 1 on S and positive constants ρ 0 , L 0 , M 0 , such that Lemma 3.1. Under Assumption 3.1 (i,ii), for each (π 1 , π 2 ) ∈ Π 1 × Π 2 , x ∈ S, t ≥ 0, the following assertions hold.
Proof. Parts (a) and (b) follow from any reference of [20,23,25,27,40]. We next prove part Using the Jensen inequality with respect to the probability measure dt T on B([0, T ]) and Cauchy-Buniakowsky-Schwarz Inequality, by (2.5) we have On the other hand, we have which, together with (3.1), implies (c 1 ). Similarly, we see that (c 2 ) is also true.
Remark 3.1. It can be seen from the proof, when g(x) = 0 on S and item (iii) in Assumption 3.1 is weaken to |r(x, a, b)| ≤ M 0 + 1 2T θ ln V 0 (x), item (c) in Lemma 3.1 still holds.
Lemma 3.1 gives conditions for the finiteness of J(π 1 , π 2 , t, x) as well as the non-explosion of {x t , t ≥ 0}. In order to deal with the game problem for history-dependent policies, we need the analog of the Ito-Dynkin's formula in [22] for possible non-Markov processes {x t , t ≥ 0} and functions ϕ(ω, t, x) with an additional element ω ∈ Ω. To do so, we recall some concepts.
Next we state the extension of the Dynkin's formula by Lemma 3.2. To do so, we introduce the following conditions and notations.
Assumption 3.2. There exist a real-valued Borel measurable function V 1 (x) ≥ 1 on S, and positive constants ρ 1 , b 1 , and M 1 , such that Assumption 3.2 is used to give a domain for the Dynkin's formula below, and it is obviously satisfied when the transition rates are bounded [19,35,36,46].
Given the V k (k = 0, 1) as in Assumption 3.2 and any Borel set Z, a real-valued function and then where {x t , t ≥ 0} may be not Markovian since policies π 1 and π 2 may depend on histories.

The existence of Nash equilibria
In this section, we prove the existence of a Nash equilibrium and a solution to the following Shapley equation (4.1) for the finite-horizon stochastic game with the risk-sensitive criterion.
The proofs are shown in three steps as follows: 1) consider the case of bounded transition and payoff rates, 2) deal with the case of unbounded transition rates but nonnegative payoff, and 3) study the case of unbounded transition and payoff rates. (iii) For each x ∈ S, the functions r(x, a, b) and The following results are for the case of the bounded transition and bounded payoff rates. (a) There exists a unique ϕ in 2)) satisfying the following Shapley equation for the risk-sensitive criterion of CTSGs on the finite horizon: The value function M(x) exists and is equal to ϕ(0, x) for each x ∈ S, and (π 1 ,π 2 ) is a Nash equilibrium.
The proof is rather long and is therefore presented in Appendix A.
have the same initial state and policies, their initial times t and s are different. Therefore, it is not easy to compare J(π 1 , π 2 , t, x) and J(π 1 , π 2 , s, x).    for each x ∈ S and t ∈ E (ϕ,x) with m L (E c (ϕ,x) ) = 0.
(c) The value function M(x) exists and equals to ϕ(0, x), for any x ∈ S.
The proof is rather long and is therefore presented in Appendix B.
Next, we use Proposition 4.2 to prove our main results by approximation from nonnegative payoff rates to the payoff rates that may be unbounded from above and from below.  for each x ∈ S and t ∈ E (ϕ,x) with m L (E c (ϕ,x) ) = 0.
Proof. We only prove (a) and the Nash Equilibrium policies (π 1 ,π 2 ) since the others can be  For any real-valued Borel measurable function u on K and g on [0, T ] × S , let A×B u(xs,π 1 (da|xs,s)),π 2 (db|xs,s))ds+θg(x T ) |x t = x , (4.8) provided the integral exists. Then, for each n ≥ 1, since k n (x, a, b) ≥ 0 and f n (x) ≥ 0, by for all x ∈ S and t ∈ E (J kn,fn ,x) .
Moreover, since J kn,fn (t, x) = J rn+n,gn+n (t, x) = J rn,gn (t, x)e θ(T −t)n+θn , by (4.9) we derive Since r n (x, a, b) and g n (x) are decreasing in n ≥ 1, and so is the corresponding value functions J rn,gn (t, x). Therefore, the limit ϕ(t, x) := lim n→∞ J rn,gn (t, x) exists for each (t, x) ∈ [0, T ] × S. Then, as the arguments for Proposition 4.2 with ϕ n (t, x) replaced with J rn,gn (t, x) here, from (4.10) and (4.11) we can see that (a) is also true.

Algorithm
Until now, we have established the existence of the value function and Nash equilibria of the risk-sensitive stochastic game. In this section, under the suitable conditions, we prove that the value function and Nash equilibria of the game can be approximated by iteratively solving a series of two-person zero-sum matrix games through a value iteration-type algorithm.
First, we have the following convergence result.
Theorem 5.1. Under Assumption 4.1, suppose that q = sup x∈S q * (x) and r and g are finite.
Let v 0 (t, x) be an arbitrary function in where the operator Γ is defined in Appendix (A.1). Then, we have where ϕ(t, x) is the value function of the stochastic game, same as in Proposition 4.1.
Since the operator Γ is not a one-step contraction operator which is widely used in discounted MDPs, the proof of Theorem 5.1 is not trivial and is a little complicated. We present it in Appendix C.
From Theorem 5.1, we can see the calculation of function v n+1 (t, x) is critical for solving our risk-sensitive stochastic game. Below, we describe the algorithm in a recurrent form. For the current iteration n, we assume that we have the function v n (t, x), where (t, x) ∈ [0, T ]×S.
The purpose is to give a computation procedure to iteratively obtain v n+1 (t, x) converging to the value function of the game.
For any given (t, Then, the stochastic game with the payoff function c(t, x, v n , a, b) can be treated as a matrix game at the current situation. We solve the corresponding two-person zero-sum matrix game through two linear programs as below [1].
max v subject to: where φ is an optimization variable which indicates the mixed policy (probability distribution) of player 1's action selection in the action space A(x). Similarly, we solve the player 2's action selection probability distribution ψ through the following linear program.

(5.7)
We can solve the above linear programs by simplex algorithms and obtain the solutions (φ n (da|x, t), a n (t, x)) and (ψ n (db|x, t), b n (t, x)), respectively. With the classical results of matrix games, we see that a n (t, x) = b n (t, x), which is the value of the matrix game. By (5.5), for any φ ∈ P (A(x)), ψ ∈ P (B(x)), we denote c(s, x, v n , φ, ψ)ds = e θg(x) + T t a n (s, x)ds. (5.8) Therefore, the value of v n+1 (t, x) can be obtained by solving (5.6) or (5.7). We update the value of v n+1 (t, x) for every (t, x) by solving the above linear programs (we only need to solve either (5.6) or (5.7) since their optimal values are equal). We repeat the same computation procedure based on the updated values v n+1 (t, x)'s.
By Theorem 5.1, we have the following value iteration-type Algorithm 1. For the convenience of computation, we assume that A, B are finite. c(s, x, v n ) ij ← θr(x, a i , b j )v n (s, x) + S v n (s, y)q(dy|x, a i , b j ) 10 Solving the game with matrix C(s, x, v n ) 11 a n (s, x) ← sup φ∈P (A(x)) inf ψ∈P (B(x)) φ T C(s, x, v n )ψ 12 (φ n (·|x, s), ψ n (·|x, s)) ← arg sup φ∈P (A(x)) inf ψ∈P (B(x)) φ T C(s, x, v n )ψ ; 17 Output: 18 v n+1 (0, x) and (φ n (·|x, t), ψ n (·|x, t)), (t, x) ∈ [0, T ] × S With Theorem 5.1, we can see that the limit of v n+1 (0, x) (as n → ∞) is the value of the game ϕ(0, x). When the stopping condition (5.2) is satisfied and the algorithm stops, the output policy pair (φ n , ψ n ) is an ε-Nash equilibrium and the output value function v n+1 (0, x) is within ε/2 error bound from the optimal value function ϕ(0, x). The convergence of the algorithm is also guaranteed, since it is proved that the algorithm will stop within a finite number of iterations by Theorem 5.1(a).
If the payoff rates, the transition rates, or the terminal rewards is not bounded, we can solve a series of the stochastic model M + n (B.4) or N n (4.7) by finite approximation technique.

Examples
In this section, we give two examples to illustrate our main results.
Example 6.1. In a system, the state of this system is x t at time t which is continuous in time. The corresponding state space is S := [0, +∞). The system evolves as follows.
If the system is at state x t at time t, two players play the game of scissors, paper, stone.
x ∈ S, scissors are denoted as 1, paper is denoted as 2, and stone is denoted as 3. Denote a t the action player 1 taken and b t the action player 2 taken at time t. The winner receives payoffs at rate α ln(1 + x t ) from the loser, 0 < α ≤ 0.5. If they are tied, both of them receive 0. That is, Next, state x t is assumed to keep invariable for an exponential-distributed random time with parameter λ(x t , a t , b t ) (0 < λ(x, a, b) ≤ L), and then jump to other states with exponentialdistribution exp( 1 xt ). Therefore, the transition rate of state is represented by, for each D ∈ B(S), The terminal reward function is g(x) = √ ln(1+x) 2 . For this zero-sum stochastic game model, player 1 wishes to maximize the risk-sensitive rewards on a given T horizon over all policies and player 2 wishes to minimize the risk-sensitive cost on a given T horizon over all policies.
Under the above conditions, we have the following fact. Proof. Let us first show that Assumption 3.1 holds.

Now we show that Assumption 3.2 holds. A directive calculation gives
There exist a real-valued Borel measurable function V 1 (x) := (1 + x) 2 ≥ 1 on S, and positive constants ρ 1 = 23L, b 1 = 1, and M 1 = 1, such that  To ensure the existence of a Nash equilibrium for the model, we consider the following hypotheses: Under the above conditions, we have the following fact. Proof. Let us first show that Assumption 3.1 holds.
There exist a real-valued Borel measurable function V 0 (x) := 1+x 2 ≥ 1 on S and positive
Remark 6.1. In Example 6.1, the payoff rates r(x, a, b) are allowed to be unbounded from above. In Example 6.2, the payoff rates r(x, a, b), the transition rates q(dy|x, a, b) and the terminal reward g(x) are all unbounded from below and from above.

Conclusion
In this paper we have studied a finite-horizon two-person zero-sum risk-sensitive stochastic game for continuous-time Markov chains with Borel state and action spaces, in which the payoff rates, the transition rates and the terminal rewards are allowed to be unbounded from below and from above and the policies can be history-dependent. This model is a generalization of that in the existing literature [7] with bounded payoff rates and Markov policies. . As a consequence, our results extend the findings in [44] and answer an open question posed there.
The computation of Nash equilibria is of significance and desirable for the practical application of game theory. To the best of our knowledge, our iteration algorithm developed in this paper for computing the value function and Nash equilibria of risk-sensitive stochastic games is a first attempt. We also prove the convergence of the algorithm by a specific contraction operator. The combination of the iteration algorithm with other approximation techniques to handle the issue of large scalability, such as reinforcement learning, deserves further investigation in a regime of so-called multi-agent reinforcement learning [10,37].