Expectation in Stochastic Games with Prefix-Independent Objectives

All of our contributions are with regard to quantitative prefix-independent objectives $\phi$ that are bounded (i.e., the image of $\phi$ is bounded between integers $-{\text{W}}_{\phi }$ and ${\text{W}}_{\phi }$) and such that a bound ${\text{den}}_{\phi }$ on the denominators of the optimal expected $\phi$-values of vertices in the game is known. The bound on the image ensures determinacy [35], that is, the players have optimal strategies, and the bound on the denominator of optimal values of vertices discretise the search space. These bounds often exist and are easily derivable for common objectives of interest such as mean payoff.

Our primary contribution is a reduction of the expectation problem for such an objective $\phi$ to linearly many instances of the almost-sure satisfaction problem for threshold Boolean objectives $\{\phi >\lambda \}$ for thresholds $\lambda \in \mathbb{Q}$. Deciding the almost-sure satisfaction of $\{\phi >\lambda \}$ is conceptually simpler than computing the expected value of $\phi$, as in the former, we only need to consider if the measure of the paths that satisfy the objective $\{\phi >\lambda \}$ is equal to one, whereas in the latter, one must take the averages of the measures of the sets of paths $\pi$ weighted with the value $\phi (\pi )$ of the paths. Our technique is generic in the sense that when an algorithm for the almost-sure satisfaction problem for $\{\phi >\lambda \}$ is known, we directly obtain the complexity and a way to solve the expectation problem for $\phi$.

Our reduction builds on the technique introduced in [16] for Boolean prefix-independent objectives and non-trivially extends it to quantitative prefix-independent objectives $\phi$ for which the bounds ${\text{W}}_{\phi }$ and ${\text{den}}_{\phi }$ are known. The expected $\phi$-values of vertices are nondeterministically guessed, and we present a characterisation (Theorem 7, similar to [16, Lemma 8] but with important and subtle differences) to verify the guess. We also explicitly construct strategies for both players that are optimal for the expectation of $\phi$, in terms of almost-sure winning strategies for $\{\phi >\lambda \}$ (proof of Lemma 9). The memory requirement for the constructed optimal strategies is the same as that of the almost-sure winning strategies (Corollary 10).

Our framework gives an alternative approach to solve the expectation problem for well-studied objectives such as expected mean payoff and gives new results for not-as-well-studied objectives such as the window mean-payoff objectives introduced in [12]. As our secondary contribution, we illustrate our technique by applying it to two variants of window mean-payoff objectives: fixed ($\text{FWMP}(\mathrm{\ell })$) and bounded (BWMP) window mean-payoff. Using our reduction, we are able to show that for both of these objectives, the expectation problem is in $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ (Theorem 18 and Theorem 22), a result that was not known before. The $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ upper bound for window mean-payoff objectives matches the special case of simple stochastic games [20, 13], and thus would require a major breakthrough to be improved. The lower bounds on the memory requirements for these objectives carry over from special case of the non-stochastic games [12, 22]. We summarise the complexity results and bounds on the memory requirements for the window mean-payoff objectives in Table 1.

Stochastic games were introduced by Shapley [38] where these games were studied under expectation semantics for discounted-sum objectives. In [14], it was shown that solving stochastic parity games reduces to solving stochastic mean-payoff games. Further, solving stochastic parity games, stochastic mean-payoff games, and simple stochastic games (i.e., stochastic games with reachability objective) are all polynomial-time equivalent [30, 1], and thus, are all in $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ [13]. A sub-exponential (or even quasi-polynomial) time deterministic algorithms for simple stochastic games on graphs with poly-logarithmic treewidth was proposed in [18]. In [29], sufficient conditions on the objective were shown such that optimal deterministic memoryless strategies exist for the players. In [34], value iteration to solve the expectation problem in stochastic games with reachability, safety, total-payoff, and mean-payoff objectives was studied.

Mean-payoff objectives were studied initially in two-player games, without stochasticity [24, 39], and with stochasticity in [28]. Finitary versions were introduced as window mean-payoff objectives [12]. For finitary mean-payoff objectives, the satisfaction problem [6] and the expectation problem [5] were studied in the special case of Markov decision processes (MDPs), which correspond to stochastic games with a trivial adversary. Expected mean payoff, expected discounted payoff, expected total payoff, etc., are widely studied for MDPs [36, 4]. Both the expectation problem [5] and the satisfaction problem [6] for the $\text{FWMP}(\mathrm{\ell })$ objective are in $\mathrm{𝖯𝖳𝖨𝖬𝖤}$, while they are in $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ for the BWMP objective. Ensuring the satisfaction and expectation semantics simultaneously was studied in MDPs for the mean-payoff objective in [17] and for the window mean-payoff objectives in [26]. In both cases, the complexity was shown to be no greater than that of only expectation optimisation.

The satisfaction problem for window mean-payoff objectives has been studied for two-player stochastic games in [22]. While positive and almost-sure satisfaction of $\text{FWMP}(\mathrm{\ell })$ are in $\mathrm{𝖯𝖳𝖨𝖬𝖤}$, it follows from [22] that the problem is in $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ for quantitative satisfaction i.e., with threshold probabilities . Furthermore, the satisfaction problem of BWMP is in $\mathrm{𝖴𝖯}\cap \mathrm{𝖼𝗈𝖴𝖯}$ and thus has the same complexity as that of the special case of MDPs [6].

Due to lack of space, some of the proofs and details have been omitted. A full version of the paper can be found in [21].

A probability distribution over a finite non-empty set $A$ is a function $\mathrm{𝖯𝗋}:A\to [0,1]$ such that ${\sum }_{a\in A}\mathrm{𝖯𝗋}(a)=1$. We denote by $𝒟(A)$ the set of all probability distributions over $A$. For the algorithmic and complexity results, we assume that probabilities are given as rational numbers.

We consider two-player turn-based zero-sum stochastic games (or simply, stochastic games in the sequel). The two players are referred to as $\text{Player}1$ (she/her) and $\text{Player}2$ (he/him). A stochastic game is given by $𝒢=((V,E),(V_1,V_2,V_{\mathrm{◇}}),\mathbb{P},w)$, where:

• $\mathrm{■}$

  $(V,E)$ is a directed graph with a finite set $V$ of vertices and a set $E\subseteq V\times V$ of directed edges such that for all vertices $v\in V$, the set $E(v)=\{v^{\prime }\in V\mid (v,v^{\prime })\in E\}$ of out-neighbours of $v$ is non-empty, i.e., $E(v)\ne \mathrm{\varnothing }$ (no deadlocks).

• $\mathrm{■}$

  $(V_1,V_2,V_{\mathrm{◇}})$ is a partition of $V$. The vertices in $V_1$ belong to $\text{Player}1$, the vertices in $V_2$ belong to $\text{Player}2$, and the vertices in $V_{\mathrm{◇}}$ are called probabilistic vertices;

• $\mathrm{■}$

  $\mathbb{P}:V_{\mathrm{◇}}\to 𝒟(V)$ is a probability function that describes the behaviour of probabilistic vertices in the game. It maps each probabilistic vertex $v\in V_{\mathrm{◇}}$ to a probability distribution $\mathbb{P}(v)$ over the set $E(v)$ of out-neighbours of $v$ such that $\mathbb{P}(v)(v^{\prime })>0$ for all $v^{\prime }\in E(v)$ (i.e., all out-neighbours have non-zero probability);

• $\mathrm{■}$

  $w:E\to \mathbb{Q}$ is a payoff function assigning a rational payoff to every edge in the game.

Stochastic games are played in rounds. The game starts by initially placing a token on some vertex. At the beginning of a round, if the token is on a vertex $v$, and $v\in V_i$ for $i\in \{1,2\}$, then $\text{Player}i$ chooses an out-neighbour $v^{\prime }\in E(v)$; otherwise $v\in V_{\mathrm{◇}}$, and an out-neighbour $v^{\prime }\in E(v)$ is chosen with probability $\mathbb{P}(v)(v^{\prime })$. $\text{Player}1$ receives from $\text{Player}2$ the amount $w(v,v^{\prime })$ given by the payoff function, and the token moves to $v^{\prime }$ for the next round. This continues ad infinitum resulting in an infinite sequence $\pi =v_0{v}_1{v}_2\mathrm{\cdots }\in V^{\omega }$ such that $(v_i,v_{i+1})\in E$ for all $i\ge 0$, called a play. For , we denote by $\pi (i,j)$ the infix $v_i{v}_{i+1}\mathrm{\cdots }{v}_j$ of $\pi$. Its length is $|\pi (i,j)|=j-i$, the number of edges. We denote by $\pi (0,j)$ the finite prefix $v_0{v}_1\mathrm{\cdots }{v}_j$ of $\pi$, and by $\pi (i,\mathrm{\infty })$ the infinite suffix $v_i{v}_{i+1}\mathrm{\dots }$ of $\pi$. We denote by ${\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}$ and ${\mathrm{𝖯𝗋𝖾𝖿𝗌}}_{𝒢}$ the set of all plays and the set of all finite prefixes in $𝒢$ respectively. We denote by $\mathrm{𝖫𝖺𝗌𝗍}(\rho )$ the last vertex of the prefix $\rho \in {\mathrm{𝖯𝗋𝖾𝖿𝗌}}_{𝒢}$. We denote by ${\mathrm{𝖯𝗋𝖾𝖿𝗌}}_{𝒢}^i$ ($i\in \{1,2\}$) the set of all prefixes $\rho$ such that $\mathrm{𝖫𝖺𝗌𝗍}(\rho )\in V_i$.

A stochastic game with $V_{\mathrm{◇}}=\mathrm{\varnothing }$ is a non-stochastic two-player game, a stochastic game with $V_2=\mathrm{\varnothing }$ is a Markov decision process (MDP), and a stochastic game with $V_1=V_2=\mathrm{\varnothing }$ is a Markov chain. Figure 1 shows an example of a stochastic game; $\text{Player}1$ vertices are shown as circles, $\text{Player}2$ vertices as boxes, and probabilistic vertices as diamonds.

Given a stochastic game $𝒢=((V,E),(V_1,V_2,V_{\mathrm{◇}}),\mathbb{P},w)$, a subset $V^{\prime }\subseteq V$ of vertices induces a subgame if $(i)$ every vertex $v^{\prime }\in V^{\prime }$ has an outgoing edge in $V^{\prime }$, that is $E(v^{\prime })\cap V^{\prime }\ne \mathrm{\varnothing }$, and $(ii)$ every probabilistic vertex $v^{\prime }\in V_{\mathrm{◇}}\cap V^{\prime }$ has all outgoing edges in $V^{\prime }$, that is $E(v^{\prime })\subseteq V^{\prime }$. The induced subgame is $((V^{\prime },E^{\prime }),(V_1\cap V^{\prime },V_2\cap V^{\prime },V_{\mathrm{◇}}\cap V^{\prime }),{\mathbb{P}}^{\prime },w^{\prime })$, where $E^{\prime }=E\cap (V^{\prime }\times V^{\prime })$, and ${\mathbb{P}}^{\prime }$ and $w^{\prime }$ are restrictions of $\mathbb{P}$ and $w$ respectively to $(V^{\prime },E^{\prime })$. If $T\subseteq V$ is such that for all $v\in T$, if $v\in V_1\cup V_{\mathrm{◇}}$ then $E(v)\subseteq T$ and if $v\in V_2$ then $E(v)\cap T\ne \mathrm{\varnothing }$, then $T$ induces a subgame, and the subgame is a trap for $\text{Player}1$ in $𝒢$, since $\text{Player}2$ can ensure that if the token reaches $T$, then it never escapes.

A Boolean objective $\psi$ is a Borel-measurable subset of ${\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}$ [35]. A play $\pi \in {\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}$ satisfies an objective $\psi$ if $\pi \in \psi$. In a stochastic game $𝒢$ with objective $\psi$, the objective of $\text{Player}1$ is $\psi$, and since $𝒢$ is a zero-sum game, the objective of $\text{Player}2$ is the complement set $\overline{\psi }={\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}\setminus \psi$. An example of a Boolean objective is reachability, denoted $\text{Reach}(T)$, the set of all plays that visit a vertex in the target set $T\subseteq V$. This is formally defined and more examples of Boolean objectives are given in [21].

A quantitative objective is a Borel-measurable function of the form $\phi :{\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}\to ℝ$. In a stochastic game $𝒢$ with objective $\phi$, the objective of $\text{Player}1$ is $\phi$ and the objective of $\text{Player}2$ is $-\phi$, the negative of $\phi$. Let $\pi =v_0{v}_1{v}_2\mathrm{\cdots }$ be a play. Some common examples of quantitative objectives include the mean-payoff objective $\text{MP}(\pi )={lim\; inf}_{n\to \mathrm{\infty }}\frac{1}{n}{\sum }_{i=0}^{n}w(v_i,v_{i+1})$, and the liminf objective $\text{liminf}(\pi )={lim\; inf}_{n\to \mathrm{\infty }}w(v_n,v_{n+1})$. In this work, we also consider the window mean-payoff objective, which is defined in Section 4. Corresponding to a quantitative objective $\phi$, we define threshold objectives which are Boolean objectives $\psi$ of the form $\{\pi \in {\mathrm{𝖯𝗅𝖺𝗒𝗌}}_{𝒢}\mid \phi (\pi )\bowtie \lambda \}$ for thresholds $\lambda \in ℝ$ and for . We denote this threshold objective succinctly as $\{\phi \bowtie \lambda \}$.

An objective is said to be prefix-independent if it only depends on the suffix of a play. Formally, a Boolean objective $\psi$ is prefix-independent if for all plays $\pi$ and ${\pi }^{\prime }$ with a common suffix (that is, ${\pi }^{\prime }$ can be obtained from $\pi$ by removing and adding a finite prefix), we have that $\pi \in \psi$ if and only if ${\pi }^{\prime }\in \psi$. Similarly, a quantitative objective $\phi$ is prefix-independent if for all plays $\pi$ and ${\pi }^{\prime }$ with a common suffix, we have that $\phi (\pi )=\phi ({\pi }^{\prime })$. Mean payoff and liminf are examples of prefix-independent objectives, whereas reachability and discounted payoff [2] are not.

A (deterministic or pure) strategy¹¹1 We only consider the satisfaction and expectation of Borel-measurable objectives, and deterministic strategies suffice for such objectives [10]. Satisfying two goals simultaneously, e.g., $\mathrm{𝖯𝗋}(\text{Reach}(T_1))>0.5\wedge \mathrm{𝖯𝗋}(\text{Reach}(T_2))>0.5$ requires randomisation and is not allowed by our definition. for Player $i\in \{1,2\}$ in a game $𝒢$ is a function ${\sigma }_i:{\mathrm{𝖯𝗋𝖾𝖿𝗌}}_{𝒢}^i\to V$ that maps prefixes ending in a vertex $v\in V_i$ to a successor of $v$. Strategies can be realised as the output of a (possibly infinite-state) Mealy machine [33]. The memory size of a strategy ${\sigma }_i$ is the smallest number of states a Mealy machine defining ${\sigma }_i$ can have. A strategy ${\sigma }_i$ is memoryless if ${\sigma }_i(\rho )$ only depends on the last element of the prefix $\rho$, that is, for all prefixes $\rho ,{\rho }^{\prime }\in {\mathrm{𝖯𝗋𝖾𝖿𝗌}}_{𝒢}^i$ if $\mathrm{𝖫𝖺𝗌𝗍}(\rho )=\mathrm{𝖫𝖺𝗌𝗍}({\rho }^{\prime })$, then ${\sigma }_i(\rho )={\sigma }_i({\rho }^{\prime })$.

A strategy profile $\sigma =({\sigma }_1,{\sigma }_2)$ is a pair of strategies ${\sigma }_1$ and ${\sigma }_2$ of $\text{Player}1$ and $\text{Player}2$ respectively. A play $\pi =v_0{v}_1\mathrm{\cdots }$ is consistent with a strategy ${\sigma }_i$ of $\text{Player }i$ ($i\in \{1,2\}$) if for all $j\ge 0$ with $v_j\in V_i$, we have $v_{j+1}={\sigma }_i(\pi (0,j))$. A play $\pi$ is an outcome of a profile $\sigma =({\sigma }_1,{\sigma }_2)$ if it is consistent with both ${\sigma }_1$ and ${\sigma }_2$. For a Boolean objective $\psi$, we denote by ${\mathrm{𝖯𝗋}}_{𝒢,v}^{{\sigma }_1,{\sigma }_2}(\psi )$ the probability that an outcome of the profile $({\sigma }_1,{\sigma }_2)$ in $𝒢$ with initial vertex $v$ satisfies $\psi$.

Let $\psi$ be a Boolean objective. A strategy ${\sigma }_1$ of $\text{Player}1$ is winning with probability $p$ from a vertex $v$ in $𝒢$ for objective $\psi$ if ${\mathrm{𝖯𝗋}}_{𝒢,v}^{{\sigma }_1,{\sigma }_2}(\psi )\ge p$ for all strategies ${\sigma }_2$ of $\text{Player}2$. A strategy ${\sigma }_1$ of $\text{Player}1$ is positive winning (resp., almost-sure winning) from $v$ for $\text{Player}1$ in $𝒢$ with objective $\psi$ if ${\mathrm{𝖯𝗋}}_{𝒢,v}^{{\sigma }_1,{\sigma }_2}(\psi )>0$ (resp., ${\mathrm{𝖯𝗋}}_{𝒢,v}^{{\sigma }_1,{\sigma }_2}(\psi )=1$) for all strategies ${\sigma }_2$ of $\text{Player}2$. In the above, if such a strategy ${\sigma }_1$ exists, then the vertex $v$ is said to be positive winning (resp., almost-sure winning) for $\text{Player}1$. If a vertex $v$ is positive winning (resp., almost-sure winning) for $\text{Player}1$, then $\text{Player}1$ is said to play optimally from $v$ if she follows a positive (resp., almost-sure) winning strategy from $v$. We omit analogous definitions for $\text{Player}2$.

Let $\phi$ be a quantitative objective. Given a strategy profile $\sigma =({\sigma }_1,{\sigma }_2)$ and an initial vertex $v$, let ${𝔼}_v^{\sigma }(\phi )$ denote the expected $\phi$-value of the outcome of the strategy profile $\sigma$ from $v$, that is, the expectation of $\phi$ over all plays with initial vertex $v$ under the probability measure ${\mathrm{𝖯𝗋}}_{𝒢,v}^{{\sigma }_1,{\sigma }_2}(\phi )$. We only consider objectives $\phi$ that are Borel-measurable and whose image is bounded. Thus, by determinacy of Blackwell games [35], we have that stochastic games with objective $\phi$ are determined. That is, we have ${sup}_{{\sigma }_1}{inf}_{{\sigma }_2}{𝔼}_v^{\sigma }(\phi )={inf}_{{\sigma }_2}{sup}_{{\sigma }_1}{𝔼}_v^{\sigma }(\phi )$. We call this quantity the expected $\phi$-value of the vertex $v$ and denote it by ${𝔼}_v(\phi )$. We say that $\text{Player}1$ plays optimally from a vertex $v$ if she follows a strategy ${\sigma }_1$ such that for all strategies ${\sigma }_2$ of $\text{Player}2$, the expected $\phi$-value of the outcome is at least ${𝔼}_v(\phi )$. Similarly, $\text{Player}2$ plays optimally if he follows a strategy ${\sigma }_2$ such that for all strategies ${\sigma }_1$ of $\text{Player}1$, the expected $\phi$-value of the outcome is at most ${𝔼}_v(\phi )$. If $\phi$ is a prefix-independent objective, then we have the following relation between the expected $\phi$-value of a vertex $v$ and the expected $\phi$-values of its out-neighbours.

In this paper, we consider the expectation problem for prefix-independent objectives. Our solution in turn uses the almost-sure satisfaction problem. The decision problems are defined as follows.

Given a stochastic game $𝒢$, a quantitative objective $\phi$, a vertex $v$, and a threshold $\lambda \in \mathbb{Q}$, the following decision problems are relevant:

• $\mathrm{■}$

  almost-sure satisfaction problem: Is vertex $v$ almost-sure winning for $\text{Player}1$ for a threshold objective $\{\phi >\lambda \}$?

• $\mathrm{■}$

  expectation problem: Is ${𝔼}_v(\phi )\ge \lambda$? That is, is the expected $\phi$-value of $v$ at least $\lambda$?

The reader is pointed to [2] and [25] for a more comprehensive discussion on the above-mentioned concepts.