# Numerical Calculation of Optimal Policy Pairs in Zero-sum Stochastic Games with Varying Discount Factors

Authors: Xiao Wu; Yanqiu Tang
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

In this study, the numerical calculation of optimal policy pairs in two-person zero-sum stochastic games with unbounded reward functions and state-dependent discount factors are studied. First, the expected discount criterion,ε −optimal values, and policy pairs are defined for zero-sum stochastic game model. Then, an iterative algorithm is given and the correctness of the algorithm is verified. At last, an example of inventory system is stated, the numerical simulation is obtained according to the iterative algorithm steps, and the difference between varying discount factors and a constant discount factor is obtained in further discussion.


---

## Body

## 1. Introduction

According to different time parameters and state processes, the research on zero-sum stochastic games can be roughly divided into four categories: (i) discrete-time Markov game, see [1–3], (ii) continuous-time Markov game, see [4, 5], (iii) semi-Markov game, see [6, 7], and (iv) stochastic differential game, see [8, 9]. Discrete-time Markov game is the most basic, and it is very convenient in practical operations such as action selection, as well as in designing algorithms, solving game values and calculating optimal policies, so it has been widely used in the real world. The total reward obtained by the players in the game is generally calculated by the discounted value of the reward in each stage or by the lower limit of the average value of the reward in each stage. Thus, expected discounted reward criteria and expected average reward criteria are two important research directions of stochastic games. In stochastic games, the most studied is the infinite stage expected discount criterion, which considers the expected discount total return of the system in the long-term operation state, and is widely used in some economic and financial models [4, 10].There have been widely studied for the discounted criterion of stochastic games with a constant discount factor, see [4, 6, 11]. In recent years, the interest on the study of discounted stochastic games with a nonconstant discount factor has been increasing both because of their importance in applications and because of the mathematical challenges that their analysis entails. Therefore, it is reasonable to consider the varying discount factors, see, for example, the works of Schall [12], Gonzalez-Hernandez et al. [13, 14], Zhang [15], and Stachurski and Zhang [16] and their references therein.In addition, most of the aforementioned works mainly focus on the existence of optimal values and policies for the stochastic games. However, from a practical point of view, the computations of optimal values and policies are more important. A common method is to transform the stochastic game problem into a linear programming problem, which is used to identify and calculate the optimal stationary policies. For example, Hordijk and Kallenberg [17] used linear programming to find the average optimal strategy of general Markov decision processes (abbreviated as MDPs), Denard and fox [18] obtained the algorithm of linear programming to solve some special cases of nondiscounted semi-Markov decision processes (semi-MDP), and Vrieze [19] gave a linear programming algorithm for nondiscounted stochastic games with finite state and action space. Recently, Yang et al. [9, 20, 21] proposed some new algorithms for optimal control problems, such as a novel adaptive optimal control design method for the constrained control problem in [9], an iterative adaptive dynamic programming (ADP) algorithm for the infinite-horizon optimal control problem in continuous time for nonlinear systems in [20], and λ-policy iteration (λ-PI) for the discrete-time linear quadratic regulation problem in [21].In this study, we mainly discuss the discrete-time Markov games, with finite-state space and countable-action spaces, unbounded reward function, and state-dependent discount factors, give an iterative algorithm, and verify the correctness. Moreover, we illustrate the numerical calculation by an example of inventory system.This study contains three main contributions:(a)
The discount factorsα(i) is a state-dependent measurable function from the state space to [0, 1), which is a generalization of the case of a constant discount factor(b)
For the two-person zero-sum Markov games with finite-state space and state-dependent discount factors, theε-optimal value and policy pairs can be calculated by the iterative algorithm, which lays a solid foundation for the numerical calculation of countable state space or general state space cases(c)
We illustrate the approximation calculation by a discrete-time inventory system and obtain the difference between varying discount factors and a constant discount factor in further discussionThis study is organized as follows. In Section2, we introduce the two-person zero-sum stochastic game model and its expected discount criterion. In Section 3, under suitable conditions, we give the iterative algorithm to calculate the ε-optimal value and policy pairs by the linear programming. In Section 4, we give an example to illustrate the numerical calculation of the ε-optimal value and policy pairs by the iterative algorithm. Finally, in Section 5, we state the difference between varying discount factors and a constant discount factor in further discussion.


## 2. Zero-Sum Stochastic Game Model and Expected Discount Criterion

Consider the two-person zero-sum stochastic game model as the following model:(1)S,A,B,Ai,Bi,q⋅|i,a,b,αi,ri,a,b,where S is a finite-state space with σ-field 2S and A and B represent the action spaces of player 1 and player 2, respectively. They are supposed to be countable spaces with σ fields which are 2A and 2B, respectively. For each state i∈S, Ai⊆A and Bi⊆B are the admissible action sets of player 1 and player 2, respectively, and let(2)K≔i,a,b|i∈S,a∈Ai,b∈Bi,be a measurable subset of S×A×B. q⋅|i,a,b is the transition probability, which is the stochastic kernel on S given K such that, for any i∈S,a∈Ai and b∈Bi, q⋅|i,a,b is the probability measure on K, and for any Γ∈2S, qΓ|i,a,b is the Borel function defined on S. αi is the discount factor, which is a measurable function from S to 0,1. ri,a,b is a measurable function defined on K, which is the reward (or cost) that player 1 gets (or player 2 pays) when the current state of the system is i, player 1 takes action as a and player 2 takes action as b (each player selects actions independently).Definition 1 (see [4, 5, 22]).
(a)
If there is a random kernel sequenceπ1≔πt1,t=0,1,2,… such that(3)πt1Ai|i=1,∀i∈S,then, we callπ1 as a randomized Markov policy of player 1, and the set of all randomized Markov policies of player 1 is denoted by Π1.(b)
The randomized Markov policyπ1≔πt1,t≥0 is said to be stationary if there is a probability measure π1⋅|i∈PAi such that(4)πt1⋅|i=π1⋅|i,∀i∈S,t≥0,and the set of all the stationary policies of player 1 is denoted by Π1s.
Similarly, we can define the randomized Markov policy classΠ2 and the stationary policy class Π2s of player 2, and π1,π2∈Π1×Π2 is said to be the policy pair.
LetH0≔S and Ht≔Kt×S=K×Ht−1. An element of ht∈Ht is a vector in the form of ht=i,a0,b0,…,it−1,at−1,bt−1,it, which is also known as the history of the system up to time t. For any initial state i∈S and each policy pair π1,π2∈Π1×Π2, by Ionescu–Tulcea theorem (see [23]), there exists a unique probability measure Piπ1,π2 and a underlying stochastic process it,at,bt,t≥0 defined on Ω,ℱ such that, for each Γ∈2S, t≥0, ht=i,a0,b0,…,it−1,at−1,bt−1,it∈Ht, it holds that(5)Piπ1,π2it+1∈Γ|ht,at,bt=qΓ|it,at,bt.
Moreover, the expectation operator with respect toPiπ1,π2 is denoted by Eiπ1,π2.
By independence, for the initial statei∈S and any policy pair π1,π2∈Π1×Π2 and for each ht∈Ht,D∈2A and Γ∈2B, it holds that(6)Piπ1,π2at∈D,bt∈Γ|ht=πt1D|htπt2Γ|ht.Definition 2 (see [4, 5, 22]).
(a)
For anyπ1,π2∈Π1×Π2, i∈S, and the discount factor αi∈0,1, the expected discount criteria of player 1 and player 2 are defined as follows:(7)Vαi,π1,π2≔Eiπ1,π2ri0,a0,b0+∑t=1∞∏s=0t−1αisrit,at,bt.(b)
Denote(8)Li≔supπ1∈Π1infπ2∈Π2Vαi,π1,π2,Ui≔infπ2∈Π2supπ1∈Π1Vαi,π1,π2,as the lower and upper value of model (1), respectively. Obviously, for all i∈S, we have Li≤Ui. Furthermore, if Li=Ui, for all i∈S, then we call it as the optimal value of model (1) and denote as Vα∗i.(c)
If the stochastic game (1) has the optimal value Vα∗i, then we call the policy π1∗ as the optimal policy of player 1 if(9)infπ2∈Π2Vαi,π1∗,π2=Vα∗i,∀i∈S.
Similarly, we call the policyπ2∗ as the optimal policy of player 2 if(10)supπ1∈Π1Vαi,π1,π2∗∗=Vα∗i,∀i∈S.
Furthermore, ifπj∗ are the optimal policies of player j (j=1,2), then we call π1∗,π2∗ as the optimal policy pair.
Now, we introduce some notations and terminology. For the finite-state spaceS, PS represents a probability measure on S with a weakly convergent topology. Furthermore, we say that a measurable function ω:S⟶1,∞ is the weight function and call the real-valued function u defined on Sω-bounded if its ω-norm is finite, where ω-norm is given by(11)uω≔supi∈Suiωi.
The Banach space of allω-bounded measurable functions defined on S is denoted as BωS.
In addition, for eachi∈S, ϕ∈PAi, ψ∈PBi, and the function g:K⟶R, let(12)gi,ϕ,ψ≔∑b∈Bi∑a∈Aigi,a,bϕaψb,and then,(13)ri,ϕ,ψ≔∑b∈Bi∑a∈Airi,a,bϕaψb,qΓ|i,ϕ,ψ≔∑b∈Bi∑a∈AiqΓ|i,a,bϕaψb,∀Γ∈2S.
Also, for anyπ1=πt1⋅|i∈Π1 and π2=πt2⋅|i∈Π2, we can define(14)ri,πt1,πt2≔∑b∈Bi∑a∈Airi,a,bπt1a|iπt2b|i,(15)qΓ|i,πt1,πt2≔∑b∈Bi∑a∈AiqΓ|i,a,bπt1a|iπt2b|i,∀Γ∈2S.
Furthermore, (14) and (15) can be denoted, respectively, as ri,π1,π2 and qΓ|i,π1,π2 if π1 and π2 are stationary.


## 3. Iterative Algorithm of Optimal Policy Pairs

In this section, we will give the iterative algorithm of optimal value and policy pairs in two-person zero-sum stochastic games. In order to guarantee the existence of optimal value and policy pairs, we need the following assumptions.Assumption 1 (see [4, 5, 22, 24]).
(a)
There exists a constantα∈0,1 such that supi∈Sαi≤α.(b)
There exist nonnegative constantsβ and γ (with γα<1), and a weight function ωi, such that, for all i,a,b∈K, we have(16)ri,a,b≤βωi,(17)∑j∈Sωjqj|i,a,b≤γωi.(c)
For eachi∈S, Ai and Bi are compact.(d)
For eachi∈S, ri,a,b is continuous on a,b∈Ai×Bi.(e)
For∀i∈S and any bounded measurable function ui on S, ∑j∈Sujqj|i,a,b is continuous on a,b∈Ai×Bi, and so is the weight function ωi.Remark 1.
Assumption1 (a) is obviously true for the case where the discount factor is constant and (b) shows that the reward function ri,a,b can have neither upper nor lower bounds. Assumption 1 (a)-(b) is the so-called “expected growth” conditions (see Assumption 3.1 in [24] and Assumption 1 in [22]) and (c)–(e) is the “continuous-compact” conditions (see [3–5, 11, 22, 24] and their references).
By Theorem1 in [22], we have a direct conclusion as follows.Lemma 1 (see [22]).
Suppose that Assumption1 holds; then,(a)
The optimal valueVα∗ of two-person zero-sum stochastic game in (1) exists and satisfies the following equation:(18)Vα∗i=supϕ∈PAiinfψ∈PBiri,ϕ,ψ+αi∑SVα∗jqj|i,ϕ,ψ,∀i∈S.In addition,Vα∗ is the unique solution of (18) on BωS.(b)
The stationary policy pairπ1∗,π2∗∈Π1s×Π2s is optimal if and only if Vα⋅,π1∗,π2∗ is the solution of (18).Remark 2.
Lemma1 is not only an important theoretical foundation for finding the optimal value and optimal policy pairs but also an important basis of designing iterative algorithms.
Next, we give the iterative algorithm, for which we should give the definition ofε-optimal policies.
LetVα∗ be the optimal value of two-person zero-sum stochastic game in (1); if it holds that(19)Vα⋅,πε1,πε2−Vα∗⋅ω<ε,then we call πε1,πε2∈Π1×Π2 as an ε-optimal policy pair, and Vαε⋅≔Vα⋅,πε1,πε2 is ε-optimal value. Note that the condition in (19) is guaranteed by the proof of Theorem 1; then, the ε-optimal policy pair and optimal value are defined.
In addition, for the initial valueu0i, we define the sequence(20)un+1i≔Tαuni,∀i∈S,n≥1,where the operator Tα is given by(21)Tαui≔supϕ∈PAiinfψ∈PBiri,ϕ,ψ+αi∑Sujqj|i,ϕ,ψ,∀i∈S.
Moreover, for fixedi∈S, let(22)Vni,a,b=ri,a,b+αi∑j∈Sunjqj|i,a,b.
Inspired by [25], we can propose an iterative algorithm to calculate the ε-optimal value and policy pairs as follows.Theorem 1 (iterative algorithm).
Suppose that Assumption1 holds; then, the ε-optimal value and policy pairs can be obtained by the following steps.Step 1: for anyi∈S, give the initial value u0i.Step 2: letn=1; for all i∈S, πn1⋅|i can be given by the original linear programming:(23)maxvv,s.t.v≤∑a∈AiVni,a,bϕa,b∈Bi,∑a∈Aiϕa=1,ϕa≥0,a∈Ai..Then, for alli∈S, πn2⋅|i can be given by the dual linear programming:(24)minzz,s.t.z≥∑b∈BiVni,a,bψb,a∈Ai,∑b∈BiVψbn=1,ψb≥0,b∈Bi..Step 3: regardingVni,a,b as the payment function, by [22], we can obtain(25)un+1i=∑a∈Ai∑b∈BiVni,a,bπn1a|iπn2b|i.Step 4: for sufficiently smallϵ=1−γαε, if un+1−unω<ϵ, the iteration stops and then uni is the ε-optimal value, and πn1⋅|i,πn2⋅|i is an ε-optimal policy pair. Otherwise, let n=n+1, and return to Step 2 to continue.Remark 3.
The iterative algorithm is a combination of value iterative algorithm and linear programming method of matrix game, which is not only different from the value (or policy) iterative algorithm in the existing literature as [17, 18, 22, 23] but also different from the linear programming method in matrix game as [19, 25].
Furthermore, in order to verify the correctness of the above algorithm, we give the following theorem.Theorem 2.
Suppose that Assumption1 holds; then,(a)
For any givenϵ>0, there exists a nonnegative integer:(26)Nϵ=1+logγαϵu1−u0ω1u1≠u0,such thatuNϵ+1−uNϵω<ϵ, where ⌊⋅⌋ is the round down function and 1⋅ denotes the indicator function. That is to say, the iterative converges in step Nϵ.(b)
The policy pairπNϵ1⋅|i,πNϵ2⋅|i obtained from the above iterative algorithm is an ε-optimal policy pair, where ε=ϵ/1−γα.Proof.
By the proof of Lemma1 in [24], we can obtain that Tα is a contraction operator and(27)Tαu−Tαvω≤γαu−vω,∀u,v∈BωS.(a)
By the definition of the sequenceun, for ∀n≥1, we can obtain that(28)un+1−unω=Tαun−Tαun−1ω≤Tαω⋅un−un−1ω≤γαun−un−1ω,which yields that(29)un+1−unω≤γαnu1−u0ω,∀n≥0.For any givenϵ>0, if u1−u0=0, then let Nϵ=0; we have(30)un+1−unω=0<ϵ.Otherwise, ifu1−u0≠0, then let Nϵ=1+⌊logγαϵ/u1−u0ω⌋; we can obtain(31)uNϵ+1−uNϵω≤γαNϵu1−u0ω<ϵ.Thus, we chooseNϵ=1+⌊logγαϵ/u1−u0ω⌋1u1≠u0; then,(32)uNϵ+1−uNϵω<ϵ.(b)
By Theorem1 in [24], we have Vα∗=TαVα∗; then,(33)un+1−Vα∗ω=Tαun−TαVα∗ω≤Tαω⋅un−Vα∗ω≤γαun−Vα∗ω,which yields that(34)un−Vα∗ω≤un+1−unω+un+1−Vα∗ω<ϵ+γαun−Vα∗ω.
Letn=Nϵ; it follows that(35)un−Vα∗ω<ε,where uni is the ε-optimal value for each i∈S. Therefore, πNϵ1⋅|i,πNϵ2⋅|i is an ε-optimal policy pair.


## 4. An Application Example

Example 1.
Consider an inventory system, and its storage level is the state of the system. In each staget=0,1,2,…, the system has only three states i=1,2,3, which represent different storage levels. When the system is in state 1, our warehouse storage is loose; when it is in state 2, our warehouse storage is tight; when it is in state 3, our warehouse storage is relatively loose. When the system is in state i, player 1 starts from ai1,ai2 to choose the supply and player 2 from bi1,bi2 to choose the order quantity, and then, player 1 will get the corresponding reward ri,aik,bik, where i=1,2,3 and k=1,2. In state 1, when we take action a∈a11,a12 and b∈b11,b12, the probability of system transition to state j is qj|1,a,b, j=1,2,3. In addition, we assume that the discount factors are related to the storage levels of the warehouse, denoted as α1=0.9,α2=0.85,andα3=0.95.
These two players are in a state of competition. Player 1 wants to maximize his own reward, while player 2 holds the opposite attitude, that is, to minimize the reward of player 1 (which can also be regarded as the cost of player 2).
From the above description, we can get the model of the two-person zero-sum stochastic game with varying discount factor as follows:S=1,2,3, Ai=ai1,ai2, and Bi=bi1,bi2, i=1,2,3. The transition probability is q⋅|i,a,b, i∈S, a,b∈Ai×Bi. For numerical calculation, we set the model parameter values, as shown in Table 1.
Letωi=1i=1,2,3,α=0.95,β=30,andγ=1; then, Assumption 1 holds. By Lemma 1, there exists an optimal policy pair for the inventory system.
Next, we use the iterative algorithm to find the optimal values and policy pairs of the game. The specific steps are as follows:Step 1: letn=0, u0i=0, for i=1,2,3.Step 2: for alln≥1, a,b∈A1×B1, we can obtain(36)Vn1,a,b=r1,a,b+α1∑y∈Xunyqy|1,a,b.Solving the following original linear programming,(37)maxvv,s.t.v≤Vn1,a11,b11ϕa11+Vn1,a12,b11ϕa12,v≤Vn1,a11,b12ϕa11+Vn1,a12,b12ϕa12,ϕa11+ϕa12=1,ϕa11≥0,ϕa12≥0..The solution of the above linear programming isπn1⋅|1, where(38)πn1a11|1=ϕa11,πn1a12|1=ϕa12.Its dual linear programming is(39)minzz,s.t.z≥Vn1,a11,b11ψb11+Vn1,a11,b12ψb12,z≥Vn1,a12,b11ψb11+Vn1,a12,b12ψb12,ψb11+ψb12=1,ψb11≥0,ψb12≥0..The solution of the above dual linear programming isπn2⋅|1, where(40)πn2b11|1=ψb11,πn2b12|1=ψb12.Then, we have(41)un+11=∑a∈A1∑b∈B1Vn1,a,bπn1a|1πn2b|1.Similarly, we can getπn2⋅|2, where πn2b21|2=ψb21 and πn2b22|2=ψb22, which yields that(42)un+12=∑a∈A2∑b∈B2Vn2,a,bπn1a|2πn2b|2.Also, we can calculate outπn2⋅|3, where πn2b31|3=ψb31 and πn2b32|3=ψb32, which yields that(43)un+13=∑a∈A3∑b∈B3Vn3,a,bπn1a|3πn2b|3.Step 3: letε≔10−4; if un+1i−uni<ε, then the iteration stops. Then, un+1 is ε-optimal value Vα∗ and πn1⋅|i,πn2⋅|i is ε-optimal policy pairs.Finally, by software MATLAB, we can obtain that(1)
Whenn=100, it follows that un+1−un<10−4, and then, the iteration stops; the ε-optimal values are(44)un1=76.1507,un2=74.0752,un3=82.4481.(2)
In state 1, theε-optimal policy pair is that player 1 chooses the action a11 with a probability of 0.68045 and a12 with a probability of 0.31955 and player 2 chooses b11 with a probability of 0.73865 and b12 with a probability of 0.26135.(3)
In state 2, theε-optimal policy pair is that player 1 chooses a21 with a probability of 0.38703 and a22 with a probability of 0.61297 and player 2 chooses b21 with a probability of 0.32584 and b22 with a probability of 0.67416.(4)
In state 3, theε-optimal policy pair is that player 1 chooses the action a32 with probability 1 and player 2 chooses b31 with probability 1.Table 1
The model parameter values.
StateαiActionri,a,bq1||i,a,bq2|i,a,bq3|i,a,bi=10.9a11,b116.50.30.40.3a11,b125.50.30.20.5a12,b117.50.50.30.2a12,b125.50.40.30.3i=20.85a11,b116.50.30.40.3a11,b129.50.40.30.3a12,b118.50.40.20.4a12,b127.50.50.20.3i=30.95a11,b115.50.20.40.4a11,b129.50.50.30.2a12,b117.50.20.50.3a12,b129.50.20.40.4


## 5. Discussion: Comparison between the Constant and Varying Discount Factors

In order to better analyze the case that the varying discount factors and a constant discount factor, we make the following comparison for the game in Example1 about the values of the games and iterations times in Table 2 for the varying discount factors case with α1=0.9,α2=0.85,andα3=0.95, and the constant discount factor case with αi≡0.9,i=1,2,3.Table 2
Theε-optimal values and iterations times for different discount factors.
DiscountfactorαiVαε1Vαε2Vαε3Number of iterationsα1=0.9,α2=0.85,α3=0.9576.150774.075282.4481109αi≡α=0.9,i=1,2,377.122278.511579.7598111The error of two adjacent iterative values and theε-optimal policy pairs are given by Figure 1 for the varying discount factor (with α1=0.9,α2=0.85,α3=0.95) and Figure 2 for the constant discount factor (with αi≡0.9,i=1,2,3. Note that, from the figure of the error of two adjacent iterative values, it can be seen that, in the iterative process, un+1−un exponentially increases and tends to 0 when n≥2, which is consistent with our previous theoretical analysis.Figure 1
The case of varying discount factors withα1=0.9,α2=0.85,andα3=0.95. (a) Error of iterative values. (b) Optimal values. (c) Optimal policy pairs in i=1. (d) Optimal policy pairs in i=2. (e) Optimal policy pairs in i=3.
(a)(b)(c)(d)(e)Figure 2
The case of varying discount factors withαi≡α=0.9,i=1,2,3. (a) Error of iterative values. (b) Optimal values. (c) Optimal policy pairs in i=1. (d) Optimal policy pairs in i=2. (e) Optimal policy pairs in i=3.
(a)(b)(c)(d)(e)From the above analysis, it is concluded that when the discount factors are varying, the game values and iteration times are different from the case of a fixed constant discount factor, and the optimal policy pairs are also different, which shows that the varying discount factors have an impact on the optimal values and policy pairs of the games. Therefore, it is of practical significance to consider the varying discount factor in stochastic games.


## 6. Conclusion

In this study, we are concerned with the numerical calculation of theε-optimal value and policy pairs in two-person zero-sum stochastic games with unbounded reward functions and state-dependent discount factors. For the two-person zero-sum Markov games with finite-state space and state-dependent discount factors, this study gives the iterative algorithm to calculate the ε-optimal value and policy pairs. Future work will discuss the numerical calculation of the ε-optimal value and policy pairs in two-person zero-sum stochastic games in countable state space and even general state space with varying discount factors. For the case of the countable state space, we will try to use the finite approximation technique. For the case of the general state space, we will introduce the concept of quantized policies and use the optimal policies in finite action space to approximate the optimal policies in general state space.



---

*Source: 7474566-2022-05-05.xml*