Partially Observable Discrete-time Discounted Markov Games with General Utility

Risk-sensitive optimization problems wherein one tries to optimize the expectation of the exponential of the accumulated cost/reward, are widely studied in stochastic optimal control literature. One of the primary reasons for the popularity of this criterion is that unlike risk-neutral optimization criterion, here the risk preference of the controllers are taken into account. Risk-sensitive control problems have been widely studied in literature for both Markov as well as semi-Markov processes. Risk-sensitive control problems for discrete-time Markov chains has been studied in [2, 7, 11, 13, 22, 25], for continuous-time Markov chains in [19, 20, 21, 27, 29] and for semi-Markov processes in [6, 10, 23]. There is also a good amout of literature on risk-sensitive games, both zero-sum and non-zero sum, see [1, 4, 5, 9, 18, 28]. But, in all the above cited literature it is assumed that the state process is completely observable. However, in practice it may be the case that complete information about the state is unavailable to the controller for taking decisions, which makes the study of optimization problems with partial observation quite natural. Risk-sensitive control problems for discrete-time Markov chains with partial observation has been studied in [3, 12, 24]. Although, there has been work on partially observable risk-neutral games [15, 16, 17, 26], but to the best of our knowledge there has been no work on risk-sensitive games with partial observation. Thus, this work seems to be the first work on partially observable risk-sensitive games. In this paper we consider risk-sensitive zero-sum games with partial observation and general utility function, and thus the exponential utility is a special case of our model. Like in the risk-neutral case here also we convert the partially observable game into an equivalent completely observable game. But the difference with the risk-neutral case is that here we need to keep track of the accumulated cost as well. Since in the considered model the reward/cost function is assumed to be dependant on the unobservable component, so we need to consider the joint conditional distribution of the unobservable state component and the accumulated reward/cost.

The rest of the paper is organized a follows. In Section 2, we describe our game model. Section 3 deals with finite horizon problem. Finally in Section 4 we investigate the infinite horizon problem as a limit of finite horizon problem.

The partially observable risk-sensitive zero-sum Markov game model that we are interested in can be represented by the tuple

$\displaystyle(X,Y,A,B,\{A(x)\subset A,B(x)\subset B,x\in X\},C(x,y,a,b),Q),$

(1)

where each individual component has the following interpretation.

• •

  $X,Y$ are the Borel spaces, X represents the observable state space and Y is the non-observable space.

• •

  The Borel spaces $A$ and $B$ are the action sets for player 1 and 2 respectively. And for each $x\in X$, $A(x)\subset A$, $B(x)\subset B$ are Borel subsets denoting the set of all admissible actions in state $x\in X$ for player 1 and 2 respectively.

• •

  Define $\mathbb{K}=\{(x,a,b):x\in X,a\in A(x),b\in B(x)\}$ to be the set of admissible state-action pairs, which is assumed to be a measurable subset of $X\times A\times B$. Then $C:\mathbb{K}\times Y\to\mathbb{R}$ is the immediate reward function for player 1 and immediate cost function for player 2 respectively.

• •

  For each $(x,y,a,b)\in\mathbb{K}\times Y$, the mapping $Q(B|x,y,a,b)$ is the transition probability that the next pair is in $B\in\mathcal{B}(X\times Y)$, where $\mathcal{B}(X\times Y)$ is the collection of all Borel subsets of $X\times Y$, given the current state is $(x,y)$ and actions $(a,b)\in A(x)\times B(x)$ are chosen by the players.

Also we have the discount factor $\beta\in(0,1)$. In what follows, we assume that the transition kernel $Q$ has a measurable density $q$ with respect to some $\sigma$-finite measures $\lambda$ and $\nu$, i.e.,

$\displaystyle Q(B|x,y,a,b)=\int_{B}q(x^{{}^{\prime}},y^{{}^{\prime}}|x,y,a,b)\lambda(dx^{{}^{\prime}})\nu(dy^{{}^{\prime}}),\hskip 14.22636ptB\in\mathcal{B}(X\times Y).$

(2)

We also introduce the marginal transition kernel density by

$\displaystyle q^{X}(x^{{}^{\prime}}|x,y,a,b):=\int_{Y}q(x^{{}^{\prime}},y^{{}^{\prime}}|x,y,a,b)\nu(dy^{{}^{\prime}}).$

We assume that the distribution $Q_{0}$ of $Y_{0}$, the initial (unobservable) state is known to the players. The risk-sensitive partially observed zero sum game evolves in the following way:

• •

  At the $0$th decision epoch, based on the initial observation $x_{0}$, the players choose actions $a_{0}\in A(x_{0})$ and $b_{0}\in B(x_{0})$ simultaneously and independent of each other.

• •

  As a consequence of these chosen actions player 1 gets a reward $C(x_{0},y_{0},a_{0},b_{0})$ and player 2 incurs a cost $C(x_{0},y_{0},a_{0},b_{0})$, where $y_{0}$ is the initial unobservable state. Note that the reward/cost depends on the unobservable component as well and therefore is itself unobservable.

• •

  At the next time epoch the system moves to the next state $(x_{1},y_{1})$ according to the transition law $Q(.|x_{0},y_{0},a_{0},b_{0})$. If the observable state at time 1 is $x_{1}$, then based on this observation, the previous observation $x_{0}$ and the previous pair of actions $(a_{0},b_{0})$, players 1 and 2 choose actions $a_{1}\in A(x_{1})$ and $b_{1}\in B(x_{1})$ respectively. This yields a reward $C(x_{1},y_{1},a_{1},b_{1})$ for player 1 and a cost $C(x_{1},y_{1},a_{1},b_{1})$ for player 2. Now the sequence of events as described above repeats itself.

Let $\mathcal{H}_{n}$ be the admissible observable history available upto time n, i.e., $\mathcal{H}_{0}=X$ and for $n\geq 1$, $\mathcal{H}_{n}=\mathcal{H}_{n-1}\times A\times B\times X$. Thus a typical element of $\mathcal{H}_{n}$ is given by $h_{n}=(x_{0},a_{0},b_{0},x_{1},a_{1},b_{1},\ldots,x_{n-1},a_{n-1},b_{n-1},x_{n})$, where for each $n$, $x_{n}$ represents the observable state at the $nth$ decision epoch, $a_{n}$ is the action chosen by player 1 at the $nth$ decision epoch and $b_{n}$ is the action chosen by player 2 at the $nth$ decision epoch. We endow these spaces with the Borel sigma-algebra. Next we introduce the concept of decision rules and policies.

For a fixed policy $\pi=(f_{0},f_{1},...)$ and $\sigma=(g_{0},g_{1},...)$, fixed (observable) initial state $x\in X$, the initial distribution $Q_{0}$ together with the transition kernel $Q$, we obtain by a theorem of Ionescu Tulcea a probability measure $\mathbb{P}^{\pi\sigma}_{xy}$ on $(X\times Y)^{\infty}$ endowed with the product $\sigma$-algebra. More precisely $\mathbb{P}^{\pi\sigma}_{xy}$ is the probability measure under policy $(\pi,\sigma)$ given $X_{0}=x$ and $Y_{0}=y$. On this probability space, for $\omega=(x_{0},y_{0},x_{1},y_{1},\ldots,x_{n},y_{n},\ldots)$ we define the random variables $X_{n}$ and $Y_{n}$ via the canonical projections:

$$X_{n}(\omega)=x_{n},\quad Y_{n}(\omega)=y_{n}.$$

The action sequence for player 1 is given by $\{A_{n}\}$ and that of player 2 given by $\{B_{n}\}$. Under the policies, $\pi=(f_{0},f_{1},...)$ and $\sigma=(g_{0},g_{1},...)$, the distribution of $A_{n}$ is given by $f_{n}(X_{0},A_{0},B_{0},\ldots,X_{n})$ and the distribution of $B_{n}$ is given by $g_{n}(X_{0},A_{0},B_{0},\ldots,X_{n})$.

In this section we look into the $N$ stage optimization problem. For defining the optimality criterion, consider a utility function $U:\mathbb{R}_{+}\rightarrow\mathbb{R}$ which is assumed to be continuous and strictly increasing. The discounted cost/reward generated over N stages is given by:

$\displaystyle C_{N}=\sum_{k=0}^{N-1}\beta^{k}C(X_{k},Y_{k},A_{k},B_{k}).$

(3)

For a fixed initial observable state $x$ and given policies $\pi$ and $\sigma$, the optimization criterion that we are interested in is given by:

$\displaystyle J_{N\pi\sigma}(x):=\int_{Y}\mathbb{E}^{\pi\sigma}_{xy}[U(C_{N})]Q_{0}(dy).$

(4)

Here player 1 tries to maximize $J_{N\pi\sigma}(x)$ over all policies $\pi$, for each $\sigma$. Analogously, player 2 tries to minimize $J_{N\pi\sigma}(x)$ over all policies $\sigma$, for each $\pi$. This leads to the following definitions of optimal policies and value of the game.

Note that if both the players have optimal strategies then the partially observed game has a value. Our aim is to show that the game model under consideration has a value and also there exists a saddle point equilibrium. Towards that end, we assume that the following assumptions are in force throughout the paper.

In literature partially observable risk-neutral games are treated by first converting it to an equivalent completely observable game. Following that approach, in this risk-sensitive approach also we first convert our partially observed game problem into a complete observed game problem. We show the existence of the value function and optimal strategies in case of the equivalent completely observable model and then revert back to our partially observed model.

Now in the unobserved model, the state $y$ and the cost accumulated so far cannot be observed because it depends on $y$. Thus we need to estimate them. For that we consider the following set of probability measures on $Y\times\mathbb{R}_{+}$:

$P_{b}(Y\times\mathbb{R}_{+})$:={$\mu$ is a probability measure on the Borel $\sigma$- algebra $\mathcal{B}(Y\times\mathbb{R}_{+})$ such that there exists a constant $K=K(\mu)>0$ with $\mu(Y\times[0,K])=1$}.

The elements of the above set will essay the role of the conditional distribution of the hidden state component and accumulated cost. The precise interpretation will be seen in Theorem 1. In order to estimate the unobserved state component and accumulated cost we define the following updating operator $\Phi:X\times A\times B\times X\times P_{b}(Y\times\mathbb{R}_{+})\times\mathbb{R}_{+}\rightarrow P_{b}(Y\times\mathbb{R}_{+})$ given by

$\displaystyle\Phi(x,a,b,x^{{}^{\prime}},\mu,z)(B):=\frac{\int_{Y}\int_{\mathbb{R}_{+}}\big{(}\int_{B}q(x^{{}^{\prime}},y^{{}^{\prime}}|x,y,a,b)\nu(dy^{{}^{\prime}})\delta_{s+zC(x,y,a,b)}(ds^{{}^{\prime}})\big{)}\mu(dy,ds)}{\int_{Y}q^{X}(x^{{}^{\prime}}|x,y,a,b)\mu^{Y}(dy)},$

(5)

where $B\in\mathcal{B}(Y\times\mathbb{R}_{+})$ and $\mu^{Y}(dy)=\mu(dy,\mathbb{R}_{+})$ is the Y-marginal distribution of $\mu$. Going forward we will also use the notation $\mu^{s}(ds):=\mu(Y,ds)$, which will denote the S-marginal. We define the updating operator only when the denominator is positive. For $h_{n}=(x_{0},a_{0},b_{0},.....,x_{n})$ and $B\in\mathcal{B}(Y\times\mathbb{R}_{+})$ we now define the sequence of probability measures

		$\displaystyle\mu_{0}(B|h_{0}):=(Q_{0}\times\delta_{0})(B),$
		$\displaystyle\mu_{n+1}(B|h_{n},a,b,x^{{}^{\prime}})=\Phi(x_{n},a,b,x^{{}^{\prime}},\mu_{n}(.|h_{n}),\beta^{n})(B).$		(6)

The next theorem provides the interpretation of the above defined sequence of probability measures $(\mu_{n})$ as the sequence of conditional distributions. For that purpose we first define the sequence of random variables:

$\displaystyle S_{0}:=0,\hskip 5.69046ptS_{n}:=\sum_{k=0}^{n-1}\beta^{k}C(X_{k},Y_{k},A_{k},B_{k}),\hskip 5.69046ptn\in\mathbb{N}$

We then have the following result which generalizes Theorem 1 of [3] to the game setting.

Now we again look at the optimization problem (4). Motivated by the previous result we define for $x\in X$, $\mu\in P_{b}(Y\times\mathbb{R}_{+})$, $z\in(0,1]$ and $n=1,2,....,N$:

$\displaystyle V_{n\pi\sigma}(x,\mu,z):=\int_{Y}\int_{\mathbb{R}_{+}}\mathbb{E}^{\pi\sigma}_{xy}\bigg{[}U\big{(}s+z\sum_{k=0}^{n-1}\beta^{k}C(X_{k},Y_{k},A_{k},B_{k})\big{)}\bigg{]}\mu(dy,ds).$

(8)

We solve our optimization problem by using a state augmentation technique. For that purpose we define, for a probability measure $\mu\in P(Y)$:

$\displaystyle Q^{X}(B|x,\mu,a,b):=\int_{B}\int_{Y}q^{X}(x^{{}^{\prime}}|x,y,a,b)\mu(dy)\lambda(dx^{{}^{\prime}}),\hskip 14.22636ptB\in\mathcal{B}(X).$

We now consider the completely observable model with new state space $E=X\times P_{b}(Y\times\mathbb{R}_{+})\times(0,1]$. The action spaces for player 1 and player 2 are same as the partially observable model. One stage cost/reward is $0$ and the terminal cost/reward function is $V_{0}(x,\mu,z):=\int_{Y}\int_{\mathbb{R}_{+}}U(s)\mu(dy,ds)$. Since for all $\mu\in P_{b}(Y\times\mathbb{R}_{+})$ the support of $\mu$ in the s-component is bounded, the expectation is well defined. The transition law for the new model is given by $\tilde{Q}(.|x,\mu,z,a,b)$, which for $(x,\mu,z,a,b)\in E\times A\times B$, and a Borel measurable subset $B\in E$ is defined by

$\displaystyle\tilde{Q}(B|x,\mu,z,a,b):=\int_{X}1_{B}\big{(}(x^{{}^{\prime}},\Phi(x,a,b,x^{{}^{\prime}},\mu,z),\beta z)\big{)}Q^{X}(dx^{{}^{\prime}}|x,\mu^{Y},a,b).$

The decision rules for player 1 in the newly defined model are given by measurable mappings $f:E\rightarrow P(A)$ such that $f(x,\mu,z)(A(x))=1$. Similarly, the decision rules for player 2 are given by measurable mappings $g:E\rightarrow P(B)$ such that $g(x,\mu,z)(B(x))=1$. We denote by $F_{1}$ the set of all decision rules for player 1 and $F_{2}$ denotes the same for player 2. For player 1, we denote by $\Pi_{1}^{M}$ the set of all Markov policies $\pi=(f_{0},f_{1},...)$ with $f_{n}\in F_{1}$ for all $n\geq 0$. $\Pi_{2}^{M}$ represents the same for player 2.

Let $\mathcal{C}(E)=\{v:E\to\mathbb{R},\,v\,\,\textup{is continuous and }\,\,v\geq V_{0}\}$. Note that we consider the topology of weak convergence on $P_{b}(Y\times\mathbb{R}_{+})$. For $v\in\mathcal{C}(E)$, $(\zeta,\eta)\in P(A(x))\times P(B(x))$ and $(f,g)\in F_{1}\times F_{2}$, we consider the following operators:

$\displaystyle(T_{fg}v)(x,\mu,z):=\int_{B}\int_{A}\int_{X}v\big{(}x^{{}^{\prime}},\Phi(x,a,b,x^{{}^{\prime}},\mu,z),\beta z\big{)}Q^{X}(dx^{{}^{\prime}}|x,\mu^{Y},a,b)f(x,\mu,z)(da)g(x,\mu,z)(db)$

$\displaystyle(Lv)(x,\mu,z,\zeta,\eta):=\int_{B}\int_{A}\int_{X}v\big{(}x^{{}^{\prime}},\Phi(x,a,b,x^{{}^{\prime}},\mu,z),\beta z\big{)}Q^{X}(dx^{{}^{\prime}}|x,\mu^{Y},a,b)\zeta(da)\eta(db).$

$\displaystyle Tv(x,\mu,z):=\inf_{g}\sup_{f}T_{fg}v=\inf_{\zeta}\sup_{\eta}(Lv)(x,\mu,z,\zeta,\eta),\hskip 8.5359pt(x,\mu,z)\in E.$

(9)

Next we have the following theorem: