# Discounting the Past††thanks: This work is supported by the National Science
Foundation grant 2009022 and by a CU Boulder Research and Innovation Office
grant.

Taylor Dohmen and Ashutosh Trivedi  University of Colorado, Boulder, USA

###### Abstract

Stochastic games with discounted payoff, introduced by Shapley, model
adversarial interactions in stochastic environments where two players try to
optimize a discounted sum of rewards. In this model, long-term weights are
geometrically attenuated based on the delay in their occurrence. We propose a
temporally dual notion—called past-discounting—where agents have geometrically
decaying memory of the rewards encountered during a play of the game. We study
objective functions based on past-discounted weight sequences and examine the
corresponding stochastic games with liminf, discounted, and mean payoffs. For
objectives specified as the limit inferior of past-discounted reward
sequences, we show that positional determinacy fails and that optimal
strategies may require unbounded memory. To overcome this obstacle, we study
an approximate windowed objective based on the idea of using sliding windows
of finite length to examine infinite plays. On the other hand, for objectives
specified as the discounted and average limits of past-discounted reward
sequences we establish determinacy in mixed stationary strategies in the
setting of concurrent stochastic games and show how the values of these games
may be computed via reductions to standard discounted and mean-payoff games.

##  1 Introduction

_Time preference_ refers to the tendency of rational agents to place a higher
value on the _desirable outcomes_ received at an earlier time as compared to a
later time. This phenomenon is often codified as discounted payoff in
mathematical models from diverse disciplines such as economics and game
theory, control theory, and reinforcement learning. It stands to reason, then,
that for _undesirable outcomes_ the time preference of rational agents may be
dual: a tendency to regret less the undesirable outcomes experienced in the
distant past compared to those encountered recently. We study a temporally
dual notion of “future” discounting as _past-discounting_ and optimization and
games over such preferences.

Two-player zero-sum stochastic games provide a natural model for adversarial
interactions between rational agents with competing objectives in uncertain
settings. Beginning with an initial configuration of an arena, these games
proceed in discrete time, and at each step the players—named Min and
Max—concurrently choose (stochastically) from a set of state-dependent
actions. Based on their choices, a scalar weight is determined with the
interpretation that this quantity represents a “payment” from Min to Max.
Given the current state and the players’ action pair, a probabilistic
transition function determines the next state and the process repeats
infinitely. The goal of Max is to maximize a given objective—typically
specified as some functional into the real numbers—defined on infinite
sequences of payments $x=\left\langle x_{n}\right\rangle_{n\geq 0}$, while the
goal of Min is the opposite. The most popular objectives are the limit payoff,
the discounted payoffs, which are well-defined for discount factors
$\lambda\in[0,1)$, and the mean payoff:

$\displaystyle L(x)$ $\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}x_{n}$ (Limit Payoff) $\displaystyle
D_{\lambda}(x)$ $\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\lim_{n\to\infty}\sum^{n}_{k=0}\lambda^{k}x_{k},$ (Discounted
Payoff) $\displaystyle M(x)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}\frac{1}{n+1}\sum^{n}_{k=0}x_{k}.$ (Mean
Payoff)

The discount factor $\lambda$ can be interpreted as the complement of a
probability $(1-\lambda)$ that the game will halt at any given point in time.
At time $k$, the quantity transferred to Max from Min is scaled by the
probability that the game continues: $\lambda^{k}$. The players are interested
in optimizing, in expectation, the total accumulated reward before
termination. For an infinite sequence $x=\left\langle
x_{n}\right\rangle_{n\geq 0}$, the discounted sum $(1-\lambda)D_{\lambda}(x)$
may be viewed as a weighted average—a convex combination, in fact—in which
elements occurring earlier in the sequence are weighted more heavily. On the
other hand, when agents prefer long-run rewards over initial rewards, a more
traditional average—the mean payoff objective—is employed. In this case, each
element contributes equally to the total, and transient elements become less
significant as time progresses.

Shapley, in his seminal work [36], showed that stochastic games played on
finite arenas with discounted objectives are determined in stationary
strategies. In other words, there are optimal strategies for both players that
need only consider the current state of play. Bewley and Kohlberg showed that
stochastic games with mean payoff objective are also determined in stationary
strategies [6] and related the discounted and mean payoff objectives
asymptotically [5].

#### Discounting the Past.

Using Shapley’s discounting as a conceptual basis, we study _past-discounting_
as a temporally dual notion. For a finite sequence of weights $\left\langle
x_{0},x_{1},\ldots,x_{n}\right\rangle$, the past-discounted sum with discount
factor $\gamma\in[0,1)$, is defined by the formula
$\sum^{n}_{k=0}\gamma^{n-k}x_{k}$, and was introduced by Alur, et al. [3].

To motivate the idea of past-discounting, consider a setting where the weights
in a stochastic game arena characterize the performance of an agent. Under
such an interpretation, rewards obtained by the agent at each stage represent
the immediate response to their actions from the environment. In this sense,
the total sum of a finite sequence of rewards encountered by the agent
provides a quantification of their reputation over that period of time. This
sum may be thought of as a performance evaluation of the agent done by an
evaluator considering each past action with equal significance. In contrast,
the past-discounted sum of the finite sequence represents an evaluation of the
agent in which actions taken more recently are given greater significance.
Here, the discount factor $\gamma$ can be seen as a parameter encoding the
evaluator’s preference for recent performance compared to performances
occurring long ago. If we suppose the cause of this preference to be that the
evaluator has imperfect memory that worsens over time, then $\gamma$ may
represent the rate at which the evaluator forgets or forgives.

If, for instance, the agent is a politician, the reward incurred at each step
could correspond to their popularity rating, and the past-discounted sum of
these ratings would then be their (weighted) average popularity, placing more
significance on recent ratings. In this scenario, the past-discounted
evaluation is more relevant than the total sum evaluation, since favorability
of a politician depends on the public’s recollection of their past actions,
which tends to decay with time. More generally, past-discounting makes sense
whenever the agent in question can learn and adapt and the evaluator either
has a time-decaying memory or a time-decaying perception of significance.

We propose the extension of this notion to infinite weight sequences. Perhaps
the most straightforward way to define the past-discounted objective for an
infinite sequence $\left\langle x_{n}\right\rangle_{n\geq 0}$ of payoffs is to
consider the limit $\lim_{n\to\infty}\sum^{n}_{k=0}\gamma^{n-k}x_{k}$ of the
past-discounted sums of finite prefixes of increasing length. Even for bounded
sequences, however, this summation may fail to converge. As an example
consider the bounded infinite sequence $\left\langle
1,2,1,2,1,2,\ldots\right\rangle$. The past-discounted sum for every even step
$k=2n$ is given as

$2\cdot\frac{1-(\gamma^{2})^{n}}{1-\gamma^{2}}+\gamma\cdot\frac{1-(\gamma^{2})^{n}}{1-\gamma^{2}},$

while, for every odd step $k=2n+1$, we have

$\frac{1-(\gamma^{2})^{n}}{1-\gamma^{2}}+2\gamma\cdot\frac{1-(\gamma^{2})^{n}}{1-\gamma^{2}}.$

Hence, every even subsequence converges to $\frac{2+\gamma}{1-\gamma^{2}}$,
while the odd subsequences converge to $\frac{1+2\gamma}{1-\gamma^{2}}$, and
the limit of the sequence as whole does not exist.

In light this observation, $\lim_{n\to\infty}\sum^{n}_{k=0}\gamma^{n-k}x_{k}$
is ill-posed and does not define a function from bounded sequences to scalars.
Instead, we study the following variants which are well defined over any
bounded weight sequence $x=\left\langle x_{n}\right\rangle_{n\geq 0}$.

$\displaystyle P_{\gamma}(x)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}\sum^{n}_{k=0}\gamma^{n-k}x_{k}$ (Past-
Discounted Payoff) $\displaystyle D_{\lambda}P_{\gamma}(x)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\lim_{n\to\infty}\sum_{k=0}^{n}\lambda^{k}\sum_{i=0}^{k}\gamma^{k-i}x_{i}$
(Discounted Past-Discounted Payoff) $\displaystyle MP_{\gamma}(x)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}\frac{1}{n+1}\sum_{k=0}^{n}\sum_{i=0}^{k}\gamma^{k-i}x_{i}$
(Mean Past-Discounted Payoff)

The latter two objectives correspond to the Abelian and Cesàro summations of
the past-discounted weights.

#### Past-Discounted Payoff (Example).

Consider the bounded infinite sequence $x=(3,4,5)^{\omega}$ and the
corresponding sequence of past-discounted sums:

$P_{\gamma}(x)=\left\langle
3,(3\gamma+4),(3\gamma^{2}+4\gamma+5),(3\gamma^{3}+4\gamma^{2}+5\gamma+3),(3\gamma^{4}+4\gamma^{3}+5\gamma^{2}+3\gamma+4),\ldots\right\rangle.$

It is easy to see that the sequence $P_{\gamma}(x)$ does not converge.
However, the subsequence containing every third element ($k=3n$) converges to
$\frac{3+5\gamma+4\gamma^{2}}{1-\gamma^{3}}$. Likewise, the subsequence with
$k=3n+1$ converges to $\frac{4+3\gamma+5\gamma^{2}}{1-\gamma^{3}}$ and the
subsequence with $k=3n+2$ converges to
$\frac{5+4\gamma+3\gamma^{2}}{1-\gamma^{3}}$.

#### Discounted Past-Discounted Payoff (Example).

Consider the $\lambda$-discounted sum of sequence $P_{\gamma}(x)$:

$\displaystyle D_{\lambda}P_{\gamma}(x)$
$\displaystyle={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\lambda(3\gamma{+}4})+{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\lambda^{2}(3\gamma^{2}{+}4\gamma{+}5})+{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\lambda^{3}(3\gamma^{3}{+}4\gamma^{2}{+}5\gamma{+}3)}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\lambda^{4}(3\gamma^{4}{+}4\gamma^{3}{+}5\gamma^{2}{+}3\gamma+4)}+\ldots$
$\displaystyle=({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}{+}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}3\gamma\lambda}{+}{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}3\gamma^{2}\lambda^{2}}{+}\ldots)+({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4\lambda}{+}{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}4\lambda^{2}\gamma}{+}{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}4\lambda^{3}\gamma^{2}}{+}\ldots)+({\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}5\lambda^{2}}{+}{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}5\lambda^{3}\gamma}{+}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\lambda^{5}\gamma^{2}}{+}\ldots)$
$\displaystyle\qquad+({\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}3\lambda^{3}}{+}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}3\gamma\lambda^{4}}{+}3\gamma^{2}\lambda^{5}{+}\ldots)+\ldots$
$\displaystyle=3(1{+}\gamma\lambda{+}\gamma^{2}\lambda^{2}{+}\ldots)+4\lambda(1{+}\lambda\gamma{+}\lambda^{2}\gamma^{2}{+}\ldots)+5\lambda^{2}(1{+}\lambda\gamma{+}\lambda^{2}\gamma^{2}{+}\ldots)$
$\displaystyle\qquad+3\lambda^{3}(1{+}\gamma\lambda{+}\gamma^{2}\lambda^{2}{+}\ldots)+\ldots$
$\displaystyle=\frac{3+4\lambda+5\lambda^{2}+3\lambda^{3}+\ldots}{(1-\gamma\lambda)}$
$\displaystyle=\frac{3+4\lambda+5\lambda^{2}}{(1-\gamma\lambda)(1-\lambda^{3})}.$

Notice that the discounted past-discounted sum is equal to to the discounted
sum but with weights scaled by a factor $\frac{1}{1-\gamma\lambda}$. We show
that this is not a mere coincidence, and prove that this equality holds also
for Markov chains and stochastic games. In doing so, we reduce the problem of
solving games with discounted past-discounted payoff to standard discounted
games.

#### Mean Past-Discounted Payoff (Example).

Finally, consider the mean payoff of the past-discounted sequence defined as
the $\liminf$ of the following sequence:

$\displaystyle\left\langle
3,\frac{3\gamma+4}{2},\frac{3\gamma^{2}+4\gamma+5}{3},\frac{3\gamma^{3}+4\gamma^{2}+5\gamma+3}{4},\frac{3\gamma^{4}+4\gamma^{3}+5\gamma^{2}+3\gamma+4}{5},\ldots\right\rangle.$

Based on the classical Tauberian results, we may be tempted to conjecture that
that mean past-discounted payoff $MP_{\gamma}(x)$ equals
$\lim_{\lambda\uparrow 1}(1-\lambda)D_{\lambda}P_{\gamma}(x)$, i.e.

$\displaystyle MP_{\gamma}(x)=\lim_{\lambda\uparrow
1}(1-\lambda)\frac{3+4\lambda+5\lambda^{2}}{(1-\gamma\lambda)(1-\lambda^{3})}=\lim_{\lambda\uparrow
1}\frac{3+4\lambda+5\lambda^{2}}{(1-\gamma\lambda)(1+\lambda+\lambda^{2})}=\frac{3+4+5}{3(1-\gamma)}$

Indeed, we show that this conjecture holds. Moreover, we show that to compute
the value of mean past-discounted payoff in a stochastic game, it suffices to
scale the weights by a factor of $\frac{1}{1-\gamma}$ to compute the optimal
value for the mean past-discounted games.

Contributions. In summary, the contributions of this paper are itemized below.

Past-Discounted Payoff.

We study the properties of past-discounted payoffs and show that while they
are prefix-independent, they are not submixing (in the sense of [26]). Hence,
their positionality does not follow from well known results. We prove that
past-discounted games are indeed not positionally determined and establish
that optimal strategies for past-discounted games may require unbounded
memory. We consider an approximation method, formulated in terms of sliding
windows of finite length over the infinite sequence of rewards, following the
work of [18, 19, 7], called window past-discounted payoffs and show how to
compute their values.

Discounted Past-Discounted Payoff.

We provide a reduction from the values for concurrent stochastic discounted
past-discounted games to those for standard concurrent stochastic discounted
games. As a result, the computational and strategic complexity are equivalent
for these games.

Mean Past-Discounted Payoff.

We provide a reduction from the values of concurrent stochastic mean past-
discounted games to those of concurrent stochastic mean payoff games.
Computational and strategic complexity are therefore equivalent for these
games. We prove a Tauberian theorem which asymptotically relates the values of
discounted past-discounted games and mean past-discounted games on concurrent
stochastic arenas.

##  2 Preliminaries

Let $X^{*}$ be the set of all finite words and $X^{\omega}$ be the set of all
countably infinite words over a finite set $X$. A discrete probability
distribution over a (possibly infinite) set $X$ is a function $d:X\to[0,1]$
such that $\sum_{x\in X}d(x)=1$ and the support
$\mathsf{supp}(d)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\left\\{x\in X:d(x)>0\right\\}$ of $d$ is countable. Let
$\mathsf{dist}(X)$ denote the set of all discrete distributions over $X$. A
distribution $d$ is a _point distribution_ if $d(x)=1$ for some $x\in X$.

We consider two-player zero-sum games on finite stochastic game arenas (SGAs)
between two players—player Min and player Max—who concurrently choose their
actions to move a token along the edges of a graph. The next state is
determined by a probabilistic transition function based on the current state
and the players’ selected actions.

A _stochastic game arena_ (SGA) $G$ is a tuple
$(S,A_{\textnormal{Min}},A_{\textnormal{Max}},w,p)$ where:

  * •

$S$ is a finite set of states,

  * •

$A_{\textnormal{Min}}$ and $A_{\textnormal{Max}}$ are finite sets of actions
for players Min and Max;

  * •

$w:S\times A_{\textnormal{Min}}\times A_{\textnormal{Max}}\to\mathbb{R}$ is a
weight function, and

  * •

$p:S\times A_{\textnormal{Min}}\times A_{\textnormal{Max}}\to\mathsf{dist}(S)$
is a probabilistic transition function.

We write $A_{\textnormal{Min}}(s)\subseteq A_{\textnormal{Min}}$ and
$A_{\textnormal{Max}}(s)\subseteq A_{\textnormal{Max}}$ for the set of actions
available to players Min and Max, respectively, at the state $s\in S$. For
states $s,s^{\prime}\in S$ and actions $(a,b)\in A_{\textnormal{Min}}(s)\times
A_{\textnormal{Max}}(s)$, we write $p(s^{\prime}|s,a,b)$ for
$p(s,a,b)(s^{\prime})$. An SGA is said to be _deterministic_ when $p(\cdot\mid
s,a,b)$ is a point distribution, for all possible states and action pairs. An
SGA is a _perfect-information_ or _turn-based_ arena if, for all $s\in S$, at
least one of the sets $A_{\textnormal{Min}}(s)$ and $A_{\textnormal{Max}}(s)$
is a singleton. If an SGA is not turn-based it is called _concurrent_. An SGA
where one of the players has only a single choice of action from every state
is called a _one-player arena_ , otherwise it is considered to be _two-
player_. One-player stochastic arenas are equivalent to Markov decision
processes, and one-player deterministic arenas are equivalent to weighted
directed graphs.

A _play_ on $G$ is an infinite sequence
$\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}\in(S\times
A_{\textnormal{Min}}\times A_{\textnormal{Max}})^{\omega}$ such that
$p(s_{k+1}\mid s_{k},a_{k},b_{k})>0$ for all $k\geq 0$. A finite play is a
sequence in $S\times((A_{\textnormal{Min}}\times A_{\textnormal{Max}})\times
S)^{*}$. Let $\pi|^{n}_{k}$ represent the length $n-k$ contiguous subsequence
of $\pi$, starting at $(s_{k},a_{k},b_{k})$ and ending at
$(s_{n},a_{n},b_{n})$. Denote by $\mathsf{last}(\pi)$ the final tuple
comprising the finite play $\pi$. We write $\mathsf{Plays}^{G}$ and
$\mathsf{fPlays}^{G}$, respectively, for the set of all plays and finite plays
on the SGA $G$ and $\mathsf{Plays}{}^{G}(s)$ and $\mathsf{fPlays}^{G}(s)$ for
the respective subsets of these for which $s$ in the initial state.

Starting from an initial state $s\in S$ of an SGA $G$, players Min and Max
produce an infinite run by concurrently choosing state-dependent actions, and
then moving to a successor state determined by the transition function. A
strategy of player Min in $G$ is a function
$\nu\colon\mathsf{fPlays}^{G}\times S\to\mathsf{dist}(A_{\textnormal{Min}})$
such that, for all plays $\pi\in\mathsf{fPlays}^{G}$, we have that
$\mathsf{supp}(\nu(\pi,s))\subseteq A_{\textnormal{Min}}(s)$. A strategy
$\chi$ of player Max is defined analogously. A strategy is _pure_ if its image
is is a point distribution wherever it is defined; otherwise, it is _mixed_.
We say that a strategy $\sigma$ is _stationary_ if
$\sigma(\pi,s)=\sigma(\pi^{\prime},s)$, for any plays $\pi$ and
$\pi^{\prime}$. Strategies that are not stationary are called _history
dependent_. A strategy is _positional_ if it is pure and stationary. Let
$\Sigma_{\textnormal{Min}}$ and $\Sigma_{\textnormal{Max}}$ be the sets of all
strategies for the players. If the arena is not clear from context, we write
$\Sigma_{\textnormal{Min}}^{G}$ and $\Sigma_{\textnormal{Max}}^{G}$.

For an SGA $G$, a state $s$ of $G$, and strategy pair
$(\nu,\chi)\in\Sigma_{\textnormal{Min}}{\times}\Sigma_{\textnormal{Max}}$, let
$\mathsf{Plays}^{\nu,\chi}(s)$ (resp. $\mathsf{fPlays}^{\nu,\chi}(s)$) denote
the set of infinite (resp. finite) plays in which player Min and Max play
according to $\nu$ and $\chi$, respectively. Given a finite play
$\pi\in\mathsf{fPlays}^{\nu,\chi}(s)$, a basic cylinder set
$\mathsf{cyl}(\pi)$ is the set of infinite plays in
$\mathsf{Plays}^{\nu,\chi}(s)$ for which $\pi$ is a prefix. Using standard
results from probability theory one can construct a probability space
$(\mathsf{Plays}^{\nu,\chi}(s),\mathcal{F}^{\nu,\chi}(s),\Pr^{\nu,\chi}_{s})$
where $\mathcal{F}^{\nu,\chi}(s)$ is the smallest $\sigma$-algebra generated
by the basic cylinder sets and
$\Pr^{\nu,\chi}_{s}:\mathcal{F}^{\nu,\chi}(s)\to[0,1]$ is a unique probability
measure such that a finite play
$\pi=\left\langle(s_{k},a_{k},b_{k})\right\rangle^{n}_{k=0}$ has probability
$\Pr^{\nu,\chi}_{s}(\pi)=\prod_{k=0}^{n}p(s_{k+1}\mid
s_{k},a_{k},b_{k})\cdot\nu\left(\pi|^{k-1}_{0},s_{k}\right)(a_{k})\cdot\chi\left(\pi|^{k-1}_{0},s_{k}\right)(b_{k})$.

A real-valued random variable $f:\mathsf{Plays}\to\mathbb{R}$, otherwise known
as an _objective function_ or synonymously a _payoff function_ determines the
optimization objective of a particular game. The expression
$\mathbb{E}^{\nu,\chi}_{s}(f)$ denotes the expectation of $f$ with respect to
$\Pr^{\nu,\chi}_{s}$. Given a payoff function $f:Plays\to\mathbb{R}$ and an
SGA $G$, the pair $(G,f)$ fully specifies a game in which the goal of Max is
to maximize the expected value of $f$ over $G$, while the goal of Min is the
opposite. For every state $s\in S$, define the _upper value_
$\overline{\mathsf{Val}}\left(f,s\right)$ as the minimum payoff player Min can
ensure irrespective of player Max’s strategy. Symmetrically, the _lower value_
$\underline{\mathsf{Val}}\left(f,s\right)$ of a state $s\in S$ is the maximum
payoff player Max can ensure irrespective of player Min’s strategy.
Symbolically,

$\displaystyle\overline{\mathsf{Val}}\left(f,s\right)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\inf_{\nu\in\Sigma_{\textnormal{Min}}}\sup_{\chi\in\Sigma_{\textnormal{Max}}}\mathbb{E}^{\nu,\chi}_{s}(f)\quad\text{
and
}\quad\underline{\mathsf{Val}}\left(f,s\right)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\sup_{\chi\in\Sigma_{\textnormal{Max}}}\inf_{\nu\in\Sigma_{\textnormal{Min}}}\mathbb{E}^{\nu,\chi}_{s}(f).$

The inequality
$\underline{\mathsf{Val}}\left(f,s\right)\leq\overline{\mathsf{Val}}\left(f,s\right)$
holds for all two-player zero-sum stochastic games. A game is _determined_
when, for every state $s\in S$, the lower value and upper value are equal. In
this case, we say that the value of the game exists with
$\mathsf{Val}\left(f,s\right)=\underline{\mathsf{Val}}\left(f,s\right)=\overline{\mathsf{Val}}\left(f,s\right)$
for every $s\in S$. If it is not clear from context, we write
$\mathsf{Val}_{G}$ to specify the arena over which the value is taken. For
strategies $\nu\in\Sigma_{\textnormal{Min}}$ and
$\chi\in\Sigma_{\textnormal{Max}}$ of players Min and Max, we define their
values as

$\mathsf{Val}^{\nu}(f,s)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\sup_{\chi\in\Sigma_{\textnormal{Max}}}\mathbb{E}^{\nu,\chi}_{s}(f)\qquad\textnormal{
and }\qquad\mathsf{Val}^{\chi}(f,s)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\inf_{\nu\in\Sigma_{\textnormal{Min}}}\mathbb{E}^{\nu,\chi}_{s}(f).$

A strategy $\nu_{\sharp}$ of player Min is called _optimal_ if
$\mathsf{Val}^{\nu_{\sharp}}(f,s)=\mathsf{Val}\left(f,s\right)$. Likewise, a
strategy $\chi_{\sharp}$ of player Max is optimal if
$\mathsf{Val}^{\chi_{\sharp}}(f,s)=\mathsf{Val}\left(f,s\right)$. We say that
a game is _positionally determined_ if both players have positional optimal
strategies. Likewise, a game is determined in stationary strategies when both
players have optimal stationary strategies.

######  Definition 1.

For an SGA $G$, the following payoffs of player Min to player Max have been
considered extensively in literature (See, for example [23]).

Limit Payoff.

The limit payoff $L:\mathsf{Plays}\to\mathbb{R}$ of a play is defined as
follows:

$L\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq
0}\mapsto\liminf_{n\to\infty}w(s_{n},a_{n},b_{n}).$

Discounted Payoff.

The $\lambda$-discounted payoff $D_{\lambda}:\mathsf{Plays}\to\mathbb{R}$ of a
play, for a given discount factor $\lambda\in[0,1)$, is defined as follows:

$D_{\lambda}\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq
0}\mapsto\lim_{n\to\infty}\sum_{k=0}^{n}\lambda^{k}w(s_{k},a_{k},b_{k}).$

Mean Payoff.

The mean payoff $M:Plays\to\mathbb{R}$ of a play is given by the long-run
average-sum of the weight sequence of the play:

$M\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq
0}\mapsto\liminf_{n\to\infty}\frac{1}{n+1}\sum_{k=0}^{n}w(s_{k},a_{k},b_{k}).$

We refer to SGAs with the limit payoff objective as _stochastic liminf games_
, to SGAs with a discounted payoff objective as _stochastic discounted games_
, and to SGAs with the mean payoff objective as _stochastic mean payoff
games_.

To each game $(G,f)$, there is an associated decision problem called the
_threshold problem_ or, alternatively, the _value problem_ , which is defined
relative to a rational number $t\in\mathbb{Q}$ and an initial state $s$ in the
arena. The threshold problem asks whether the value of the game from state $s$
is bounded below by $t$; that is, to decide if
$\mathsf{Val}\left(f,s\right)\geq t$. When referring to the computational
complexity of various classes of games or of solving various classes of games,
we mean the complexity of deciding the value problem.

The next theorem recalls state of the art results on strategic and
computational complexity of stochastic games with liminf and limsup payoff.

######  Theorem 1 (Limit Games).

All liminf games and limsup games are determined [29, 30]. Liminf games and
limsup games over one-player deterministic arenas, one-player stochastic
arenas, and two-player deterministic arenas are in PTIME [11, 16]. Liminf
games and limsup games over turn-based two-player stochastic arenas are in
$\textnormal{UP}{}\cap\textnormal{coUP}{}$ [25]. Over any type of non-
concurrent arena, liminf games and limsup games are positionally determined
[11, 16].

The following theorem summarizes state of the art results on strategic and
computational complexity of stochastic games with discounted and mean payoff.

######  Theorem 2 (Discounted and Mean Payoff Games).

Stochastic discounted games [36] and stochastic mean payoff games [6] are
determined in mixed stationary strategies. Both are positionally determined
for turn-based game arenas [28, 23]. Stochastic discounted games are in FIXP
and are SQRT-SUM-hard [22]. Stochastic mean payoff games are in EXPTIME and
are PTIME-hard [15]. For turn-based SGAs, both types of games are in
$\textnormal{UP}\cap\textnormal{coUP}$ [10].

Stochastic mean payoff games are intimately connected to stochastic discounted
games, as evidenced by the subsequent Tauberian theorem.

######  Theorem 3 (Blackwell Optimality[5]).

As $\lambda$ tends to $1$ from below, the following equation holds for every
state $s$:

$\mathsf{Val}\left(M,s\right)=\lim_{\lambda\uparrow
1}(1-\lambda)\mathsf{Val}\left(D_{\lambda},s\right).$

Moreover, when $\lambda$ is close to 1, strategies optimal for $D_{\lambda}$
are optimal for $M$.

##  3 Past-Discounted Games

######  Definition 2 (Past-Discounted Payoffs).

Let $G=(S,A_{\textnormal{Min}},A_{\textnormal{Max}},w,p)$ be an SGA,
$\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$ be an infinite
play with weights $\left\langle w_{n}\right\rangle_{n\geq 0}=\left\langle
w(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$, and $\gamma\in[0,1)$ be a
discount factor. For every $n\in\mathbb{N}$ the $n$-step past-discounted
objective is given by the following equation.

$P^{n}_{\gamma}(\pi)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\sum^{n}_{k=0}\gamma^{n-k}w_{k}$ (Finite Past-Discounted Payoff)

The lower and upper past-discounted objectives are characterized,
respectively, by the following equations.

$\displaystyle\underline{P}_{\gamma}(\pi)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}P^{n}_{\gamma}(\pi)=\liminf_{n\to\infty}\sum^{n}_{k=0}\gamma^{n-k}w_{k}$
(Lower Past-Discounted Payoff) $\displaystyle\overline{P}_{\gamma}(\pi)$
$\displaystyle\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\limsup_{n\to\infty}P^{n}_{\gamma}(\pi)=\limsup_{n\to\infty}\sum^{n}_{k=0}\gamma^{n-k}w_{k}$
(Upper Past-Discounted Payoff)

Since the lower and upper past-discounted payoffs can mutually simulate each
other (by negating the sequences of finite-step past-discounted payoffs), we
present our results in terms of the lower past-discounted payoff and simply
refer to it as the past-discounted payoff written as $P_{\gamma}$. This is
without loss of generality and our results apply to the upper past-discounted
payoff as well.

###  3.1 Properties of the Past-Discounted Payoff

In [26] Gimbert provides a convenient sufficient condition on objectives that
ensures positional determinacy in some situations. If an objective function is
both prefix-independent and submixing, as defined below, then there are
optimal positional strategies for the objective over stochastic one-player
arenas.

######  Definition 3.

Suppose that $f$ is an arbitrary objective function and that $x=\left\langle
x_{n}\right\rangle_{n\in\mathbb{N}}$ and $y=\left\langle
y_{n}\right\rangle_{n\in\mathbb{N}}$ are infinite sequences of finite words
over the finite set of possible weights $W$, ie. $x_{n},y_{n}\in W^{*}$ for
all $n$. Define the shuffle of these sequences as $x\shuffle y=\left\langle
x_{1},y_{1},x_{2},y_{2},\ldots\right\rangle$. The objective $f$ is

  * •

_prefix-independent_ if $f(uv)=f(v)$, for any sequences $u\in W^{*}$ and $v\in
W^{\omega}$,

  * •

_submixing_ if $f(x\shuffle y)\leq\max\left\\{f(x),f(y)\right\\}$.

######  Proposition 1.

The past-discounted payoffs are prefix-independent.

###### Proof.

Suppose that $x=\left\langle x_{0},\ldots,x_{m}\right\rangle$ a finite
sequence of weights, $y=\left\langle y_{n}\right\rangle_{n\geq 0}$ is an
infinite sequence of weights, and let $xy=\left\langle
x_{0},\ldots,x_{m},y_{1},y_{2},\ldots\right\rangle$ be the infinite sequence
created by prepending $x$ to $y$. For any $n$ greater than $m$, the $n$-step
finite past-discounted payoff on $xy$ may be written as

$P^{n}_{\gamma}(xy)=\sum^{n}_{k=m}\gamma^{n-k}y_{k-m}+\sum^{m}_{k=0}\gamma^{n-k}x_{k},$

by separating the portions of the summation concerning elements from $x$ and
$y$. Manipulating the summation indices, we may rewrite this equation as

$P^{n}_{\gamma}(xy)=\sum^{n-m}_{k=0}\gamma^{n-m-k}y_{k}+\sum^{m}_{k=0}\gamma^{n-k}x_{k}.$

Factoring $\gamma^{n-m}$ from the summation of $x$ elements yields the
equality
$\sum^{m}_{k=0}\gamma^{n-k}x_{k}=\gamma^{n-m}\sum^{m}_{k=0}\gamma^{m-k}x_{k}$,
and this implies the equation

$P^{n}_{\gamma}(xy)=P^{n-m}_{\gamma}(y)+\gamma^{n-m}P^{m}_{\gamma}(x).$

Since $m$ is fixed and finite,
$\liminf_{n\to\infty}\gamma^{n-m}P^{m}_{\gamma}(x)=0$. Taking the limit
inferior of both sides of this equation yields that
$P_{\gamma}(xy)=P_{\gamma}(y)$, and thus we conclude that $P_{\gamma}$ is
prefix-independent. ∎

######  Proposition 2.

The past-discounted payoffs are not submixing.

###### Proof.

Consider the sequence $z=\left\langle 200,2,100,1\right\rangle^{\omega}$ as
the shuffle of the sequences $x=\left\langle
2,1,200,100\right\rangle^{\omega}$ and $y=\left\langle
200,100,2,1\right\rangle^{\omega}$, which is valid since $z$ can be produced
as an interleaving of the elements of $x$ and $y$ that preserves the relative
ordering of the terms from each, as illustrated below.

20021001200210012120010012100200

Because these sequences are periodic, we get that $P_{\gamma}(z)$ is equal to

$\min\left\\{\frac{200\gamma^{3}+2\gamma^{2}+100\gamma+1}{1-\gamma^{4}},\frac{\gamma^{3}+200\gamma^{2}+2\gamma+100}{1-\gamma^{4}},\frac{100\gamma^{3}+\gamma^{2}+200\gamma+2}{1-\gamma^{4}},\frac{2\gamma^{3}+100\gamma^{2}+\gamma+200}{1-\gamma^{4}}\right\\},$

and $P_{\gamma}(x)=P_{\gamma}(y)$ are equal to

$\min\left\\{\frac{2\gamma^{3}+\gamma^{2}+200\gamma+100}{1-\gamma^{4}},\frac{100\gamma^{3}+2\gamma^{2}+\gamma+200}{1-\gamma^{4}},\frac{200\gamma^{3}+100\gamma^{2}+2\gamma+1}{1-\gamma^{4}},\frac{\gamma^{3}+200\gamma^{2}+100\gamma+2}{1-\gamma^{4}}\right\\}.$

Setting $\gamma=\frac{1}{10}$, these expressions evaluate approximately to
$P_{\gamma}(z)\approx 11.2211$ and $P_{\gamma}(x)=P_{\gamma}(y)\approx
2.4002$. Therefore
$P_{\gamma}(z)>\max\left\\{P_{\gamma}(x),P_{\gamma}(y)\right\\}$, establishing
that $P_{\gamma}(z)$ is not submixing for every discount factor. ∎

$0$$0.2$$0.4$$0.6$$0.8$$1$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$\gamma$$\max\left\\{P_{\gamma}(x),P_{\gamma}(y)\right\\}$$P_{\gamma}(z)$

In fact, the sequences $x,y,z$ from the proof of Proposition 2 provide a
counterexample to submixing of $P_{\gamma}$, for all discount factors in the
unit interval, other than those very close to 1. This is illustrated by the
figure to the right, which displays, using the sequences from the proof of
Proposition 2, $\max\left\\{P_{\gamma}(x),P_{\gamma}(y)\right\\}$ in red and
$P_{\gamma}(z)$ in blue, for each possible discount factor $\gamma\in[0,1)$.

Our next result settles the matter of positional determinacy for past-
discounted games by establishing that optimal strategies may require unbounded
memory in even the simplest of contexts: games on one-player deterministic
arenas.

$s_{0}$$s_{1}$$a$$4$$a$$-2$$b$$-1$ Figure 1: SGA where optimal strategies for
$P_{\gamma}$ require unbounded memory.

######  Theorem 4.

Past-discounted games are not determined in stationary strategies and optimal
strategies may require unbounded memory.

###### Proof.

We proceed by exhibiting a one-player deterministic arena on which the optimal
strategy, at any point in time, depends upon the entire history of play.
Without loss of generality, we fix the single player in this context as Min
whose goal is to minimize the past-discounted payoff. Consider the one-player
deterministic arena shown in Figure 1 on which there are exactly two
positional strategies. One strategy chooses action $a$ from state $s_{1}$
while the other selects action $b$. These strategies generate plays $\pi_{a}$
and $\pi_{b}$, respectively, with values

$P_{\gamma}(\pi_{a})=\min\left\\{\frac{4-2\gamma}{1-\gamma^{2}},\frac{-2+4\gamma}{1-\gamma^{2}}\right\\}\qquad\textnormal{
and }\qquad P_{\gamma}(\pi_{b})=\frac{-1}{1-\gamma}$

If $\gamma=\frac{1}{2}$, then
$P_{\gamma}(\pi_{a})=\fpeval{min((4-2*0.5)/(1-0.5*0.5),(-2+4*0.5)/(1-0.5*0.5))}$
and $P_{\gamma}(\pi_{b})=-2$. A play $\pi_{\sharp}$ can achieve a better
value, namely $P_{\gamma}(\pi_{\sharp})=-2-\frac{\gamma}{1-\gamma}=-3$, if it
is consistent with a strategy that chooses action $a$ from state $s_{1}$
infinitely often and also eventually selects $n$ consecutive $b$ actions, for
every $n\geq 0$. Any strategy satisfying these conditions generates a play
$\pi_{\sharp}$ with weight sequence $\left\langle w_{n}\right\rangle_{n\geq
0}$ where, for every $n\in\mathbb{N}$, there exists $m\in\mathbb{N}$ with
$n\leq m$, such that $w_{m}=-2$ and $w_{m-k}=-1$, for $1\leq k\leq n$. As a
result, it holds that

$P^{m}_{\gamma}(\pi_{\sharp})=-2-\frac{\gamma(1-\gamma^{n})}{1-\gamma}+\gamma^{n+1}P^{m-n}_{\gamma}(\pi_{\sharp}),$

and we get that $P_{\gamma}(\pi_{\sharp})=-2-\frac{\gamma}{1-\gamma}=-3$ in
the limit when $\gamma=\frac{1}{2}$.

Since a strategy generating $\pi_{\sharp}$ must choose distinct actions from
the same state at various points in the game, it cannot be positional. Because
mixed stationary strategies are weighted combinations of positional
strategies, their expected values fall between those of the positional
strategies, and thus do not achieve better values. Therefore past-discounted
games are not determined in stationary strategies, even on one-player
deterministic arenas. Since all other types of arenas under consideration
generalize this type, it follows that past-discounted games are not determined
in stationary strategies over any type of arena. Moreover, an optimal strategy
must be able to generate all optimal $n$-step subsequences have been achieved
thus far in order to determine the number of times action $b$ should be pumped
the next time the player is in state $s_{1}$. Therefore, we conclude that
there is no optimal strategy with finitely bounded memory. ∎

###  3.2 Window Past-Discounted Games

We now introduce window past-discounted games as a means to approximate the
values of past-discounted games. This payoff is based on the sequence of
finite past-discounted sums of fixed length and considers only the last $\ell$
elements of the play at any given point. The value of $\ell$ is considered as
the _window length_.

######  Definition 4.

Let $G=(S,A_{\textnormal{Min}},A_{\textnormal{Max}},w,p)$ be an SGA,
$\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$ be an infinite
play with weight sequence $\left\langle w_{n}\right\rangle_{n\geq
0}=\left\langle w(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$, and
$\ell\in\mathbb{N}$ be a window length. The window-past discounted payoff is
characterized by the following equation.

$W_{\ell}P_{\gamma}(\pi)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}P_{\gamma}^{\ell}(\pi|^{\infty}_{n-\ell})=\liminf_{n\to\infty}\sum^{n}_{k=\max(0,n-\ell)}\gamma^{n-k}w_{k}$
(Window Past-Discounted Payoff)

The following proposition formalizes the relationship between past-discounted
payoffs, window past-discounted payoffs, and the liminf payoff.

######  Proposition 3.

We have the following equalities.

  1. 1.

$\lim_{\ell\to\infty}W_{\ell}P_{\gamma}=P_{\gamma}$.

  2. 2.

If $\ell=0$, then $W_{\ell}P_{\gamma}=L$.

Our next result establishes determinacy of window past-discounted games by
characterizing their values in terms of the values of certain liminf games.

######  Theorem 5.

Window past-discounted games are determined. For any window past-discounted
game $(G,W_{\ell}P_{\gamma})$, there is a liminf game $(H,L)$ such that, for
every state $s$ in $G$, there exists a state $s^{\prime}$ in $H$ where

$\mathsf{Val}_{G}(W_{\ell}P_{\gamma},s)=\mathsf{Val}_{H}(L,s^{\prime}).$

###### Proof.

We construct an arena $H$ for a liminf game $(H,L)$ as the product
$H=G\times\mathcal{M}^{\ell}$, where
$\mathcal{M}^{\ell}=(\Sigma,Q,q_{0},\delta)$ is a deterministic finite
automaton such that

  * •

$\Sigma=S\times A_{\textnormal{Min}}\times A_{\textnormal{Max}}$,

  * •

$Q=\left\\{q_{0}\right\\}\cup\left\\{\pi\in\mathsf{fPlays}^{G}:|\pi|\leq\ell\right\\}$,

  * •

$\delta(q_{0},sab)=sab$,

  * •

$\delta(s_{0}a_{0}b_{0}\ldots
s_{k-1}a_{k-1}b_{k-1},sab)=\begin{cases}s_{0}a_{0}b_{0}\ldots
s_{k-1}a_{k-1}b_{k-1}sab&\textnormal{if }k<\ell,\\\ s_{1}a_{1}b_{1}\ldots
s_{k-1}a_{k-1}b_{k-1}sab&\textnormal{if }k=\ell.\end{cases}$

More precisely,
$H=G\times\mathcal{M}^{\ell}=(S^{\ell},A^{\ell}_{\textnormal{Min}},A^{\ell}_{\textnormal{Max}},w^{\ell},p^{\ell})$
where

  * •

$S^{\ell}=\left\\{(s,q)\in S\times Q:q=q_{0}\textnormal{ or
}\mathsf{last}(q)=s_{k}a_{k}b_{k}\textnormal{ and }p(s\mid
s_{k},a_{k},b_{k})>0\right\\}$,

  * •

$A^{\ell}_{\textnormal{Min}}(s,q)=A_{\textnormal{Min}}(s)$ and
$A^{\ell}_{\textnormal{Max}}(s,q)=A_{\textnormal{Max}}(s)$,

  * •

$w^{\ell}((s,s_{0}a_{0}b_{0}\ldots
s_{k-1}a_{k-1}b_{k-1}),a,b)=w(s,a,b)+\sum^{k-1}_{i=0}\gamma^{k-i}w(s_{i},a_{i},b_{i})$,

  * •

$p^{\ell}((s^{\prime},q^{\prime})\mid(s,q),a,b)=\begin{cases}p(s^{\prime}\mid
s,a,b)&\textnormal{if }\delta(q,sab)=q^{\prime},\\\
0&\textnormal{otherwise}.\end{cases}$

The number of states in $H$ is on the order of $|S^{\ell}|=O(|S|2^{\ell})$.

Claim: for every strategy pair $\nu,\chi$ over $G$ there is a strategy pair
$\iota,\alpha$ over $H$ such that
${E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})={E}^{\iota,\alpha}_{(s,q_{0})}(L)$,
for all states $s$ in $G$.

Consider $\pi\in\mathsf{Plays}^{G}$ and the finite play

$\pi|^{n}_{0}=\left\langle(s_{0},a_{0},b_{0}),\ldots,(s_{\ell},a_{\ell},b_{\ell}),\ldots,(s_{n-\ell},a_{n-\ell},b_{n-\ell}),\ldots,(s_{n},a_{n},b_{n})\right\rangle.$

We know from the construction above that, for every $1\leq k\leq\ell$, there
exists a state $(s_{k},\pi|^{k-1}_{0})=(s_{k},s_{0}a_{0}b_{0}\ldots
s_{k-1}a_{k-1}b_{k-1})$ in $H$ and for $k=0$ we can associate the state
$(s_{0},q_{0})$ in $H$. Likewise, for every $\ell<k\leq n$, there exists a
state $(s_{k},\pi|^{k}_{k-\ell})$ in $H$. From the definition of the
transition function $\delta$ of $\mathcal{M}^{\ell}$ and the state set
$S^{\ell}$ of $H$, it follows that $\pi|^{n}_{0}\in\mathsf{fPlays}^{G}$
implies the existence of $\varpi|^{n}_{0}\in\mathsf{fPlays}^{H}$, where

$\displaystyle\varpi|^{n}_{0}=$
$\displaystyle\Big{\langle}((s_{0},q_{0}),a_{0},b_{0}),((s_{1},\pi|^{0}_{0}),a_{1},b_{1}),\ldots,((s_{\ell},\pi|^{\ell-1}_{0}),a_{\ell},b_{\ell}),\ldots$
$\displaystyle\qquad\ldots,((s_{n-\ell},\pi|^{n-\ell-1}_{n-2\ell-1}),a_{n-\ell},b_{n-\ell}),\ldots,((s_{n},\pi|^{n-1}_{n-\ell-1}),a_{n},b_{n})\Big{\rangle}.$

If $\pi|^{n}_{0}\in\mathsf{fPlays}^{\nu,\chi}$ for arbitrary strategies
$\nu,\chi$, then it follows from the definition of $\Pr^{\nu,\chi}_{s_{0}}$
that

$\Pr^{\nu,\chi}_{s_{0}}(\pi|^{n}_{0})=\prod^{n}_{k=1}p(s_{k}\mid
s_{k-1},a_{k-1},b_{k-1})\cdot\nu\left(\pi|^{k-1}_{0},s_{k}\right)(a_{k})\cdot\chi\left(\pi|^{k-1}_{0},s_{k}\right)(b_{k}).$

Likewise, if $\varpi|^{n}_{0}\in\mathsf{fPlays}^{\iota,\alpha}$ for arbitrary
strategies $\iota,\alpha$, then we have that

$\Pr^{\iota,\alpha}_{(s_{0},q_{0})}(\varpi|^{n}_{0})=\prod^{n}_{k=1}p^{\ell}\left((s_{k},q_{k})\mid(s_{k-1},q_{k-1}),a_{k-1},b_{k-1}\right)\cdot\iota\left(\varpi|^{k-1}_{0},(s_{k},q_{k})\right)(a_{k})\cdot\alpha\left(\varpi|^{k-1}_{0},(s_{k},q_{k})\right)(b_{k}).$

By definition of the probabilistic transition function $p^{\ell}$ of $H$, we
have the equality

$p(s_{k}\mid
s_{k-1},a_{k-1},b_{k-1})=p^{\ell}\left((s_{k},q_{k})\mid(s_{k-1},q_{k-1}),a_{k-1},b_{k-1}\right).$

Therefore,
$\Pr^{\nu,\chi}_{s_{0}}(\pi|^{n}_{0})=\Pr^{\iota,\alpha}_{(s_{0},q_{0})}(\varpi|^{n}_{0})$,
for all $n\in\mathbb{N}$, precisely when

$\displaystyle\nu(\pi|^{n}_{0},s)$
$\displaystyle=\iota\left(\varpi|^{n}_{0},\left(s,\pi|^{n-1}_{\max(0,n-1-\ell)}\right)\right),$
(1) $\displaystyle\chi(\pi|^{n}_{0},s)$
$\displaystyle=\alpha\left(\varpi|^{n}_{0},\left(s,\pi|^{n-1}_{\max(0,n-1-\ell)}\right)\right)$

hold for all $n\in\mathbb{N}$. These equations facilitate translation between
arbitrary strategy pairs over arenas $G$ and $H$, and so there indeed exist
strategies in $H$ for any strategies in $G$, and vice versa, that induce
equivalent probability measures. In combination with the definition of
$w^{\ell}$, this implies the equality of expectations for the strategies
$\nu,\chi$ on $G$ with that for the strategies $\iota,\alpha$ on $H$. To see
why, expand out the definition of ${E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})$ to
get the following.

${E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})={E}^{\nu,\chi}_{s}\left(\liminf_{n\to\infty}\sum^{n}_{k=\max(0,n-\ell)}\gamma^{n-k}w(s_{k},a_{k},b_{k})\right)$

Expanding the definition of ${E}^{\iota,\alpha}_{(s,q_{0})}(L)$ yields an
almost identical result.

${E}^{\iota,\alpha}_{(s,q_{0})}(L)={E}^{\iota,\alpha}_{(s,q_{0})}\left(\liminf_{n\to\infty}w^{\ell}(s_{k},a_{k},b_{k})\right)={E}^{\iota,\alpha}_{(s,q_{0})}\left(\liminf_{n\to\infty}\sum^{n}_{k=\max(0,n-\ell)}\gamma^{n-k}w(s_{k},a_{k},b_{k})\right)$

Because of the equivalence we have established between the probability
measures $\Pr^{\nu,\chi}_{s}$ and $\Pr^{\iota,\alpha}_{(s,q_{0})}$, assuming
that $\nu,\iota$ and $\chi,\alpha$ satisfy eq. 1, it follows that these
expectations are equivalent as well:

${E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})={E}^{\iota,\alpha}_{(s,q_{0})}(L).$

Since we have proven the above claim and established, in eq. 1, a bijection
between strategy pairs that preserves expectation, we know that111See Appendix
A for further details.

Furthermore, we know liminf games are determined, allowing us to infer that

$\inf_{\nu}\sup_{\chi}{E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})=\sup_{\chi}\inf_{\nu}{E}^{\nu,\chi}_{s}(W_{\ell}P_{\gamma})=\mathsf{Val}_{H}(L,(s,q_{0})),$

from which it follows that window past-discounted games are determined with

$\mathsf{Val}_{G}(W_{\ell}P_{\gamma},s)=\mathsf{Val}_{H}(L,(s,q_{0})).$

∎

From Theorems 5 and 1 we obtain the following corollary on the strategic and
computational complexity of window past-discounted games.

######  Corollary 1 (Complexity of Window Past-Discounted Games).

  1. 1.

For any window past-discounted game over a turn-based arena, both players have
pure optimal strategies requiring $O(\ell)$ memory.

  2. 2.

Window past-discounted games are in EXPTIME over stochastic one-player arenas
and deterministic turn-based two-player arenas. For fixed window length, these
games are in PTIME.

  3. 3.

Turn-based stochastic window past-discounted games are in
$\textnormal{NEXPTIME}{}\cap\textnormal{coNEXPTIME}{}$, and are in
$\textnormal{UP}\cap\textnormal{coUP}$ for fixed window length.

######  Remark 1.

Algorithmic aspects of liminf games and limsup games over concurrent two-
player arenas have not been extensively studied as far as we know (cf. Section
4.7 of [12]). As a result, strategic complexity and computational complexity
of the these games on concurrent arenas is unknown. Resolving these questions
would also provide complexity bounds for window past-discounted games over
concurrent arenas.

##  4 Discounted Past-Discounted Games

######  Definition 5.

Let $G=(S,A_{\textnormal{Min}},A_{\textnormal{Max}},w,p)$ be an SGA,
$\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$ be an infinite
play with weight sequence $\left\langle w_{n}\right\rangle_{n\geq
0}=\left\langle w(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$, and
$\lambda,\gamma\in[0,1)$ be discount factors. The discounted past-discounted
payoff is characterized by the following equation.

$D_{\lambda}P_{\gamma}(\pi)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\lim_{n\to\infty}\sum^{n}_{k=0}\lambda^{k}P^{k}_{\gamma}(\pi)=\lim_{n\to\infty}\sum_{k=0}^{n}\lambda^{k}\sum_{i=0}^{k}\gamma^{k-i}w_{i}$
(Discounted Past-Discounted Payoff)

We now show that discounted past-discounted games are determined in stationary
strategies by reducing the problem to computing optimal strategies for a
standard discounted game on the same arena. Our primary tool in showing the
reduction is a classical theorem from real analysis (see [35], for instance).

######  Theorem 6 (Mertens’ Theorem).

Let $a=\left\langle a_{n}\right\rangle_{n\geq 0}$ and $b=\left\langle
b_{n}\right\rangle_{n\geq 0}$ be two sequences, and let $c=\left\langle
c_{n}\right\rangle_{n\geq 0}$ be the Cauchy product
$c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k}$ of $a$ and $b$. If
$\lim_{n\to\infty}\sum_{k=0}^{n}a_{k}=A$ and
$\lim_{n\to\infty}\sum_{k=0}^{n}b_{k}=B$ and at least one of the sequences
$\left\langle\sum_{k=0}^{n}a_{k}\right\rangle_{n\geq 0}$ and
$\left\langle\sum_{k=0}^{n}a_{k}\right\rangle_{n\geq 0}$ converges absolutely,
then the limit of the Cauchy product exists such that
$\lim_{n\to\infty}\sum_{n=0}^{N}c_{n}=AB$.

######  Theorem 7.

Given a state $s$ of some SGA and discount factors $\gamma,\lambda\in[0,1)$,
it holds that

$\mathsf{Val}\left(D_{\lambda}P_{\gamma},s\right)=\frac{1}{1-\gamma\lambda}\mathsf{Val}\left(D_{\lambda},s\right).$

###### Proof.

To prove this theorem, it suffices to show that
$\mathbb{E}^{\nu,\chi}_{s}(D_{\lambda}P_{\gamma})=\frac{1}{1-\gamma\lambda}\mathbb{E}^{\nu,\chi}_{s}(D_{\lambda})$
holds for any pair of strategies
$(\nu,\chi)\in\Sigma_{\textnormal{Min}}\times\Sigma_{\textnormal{Max}}$ and
consistent play $\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$.
In turn, this reduces to proving the equation
$D_{\lambda}P_{\gamma}(\pi)=\frac{1}{1-\gamma\lambda}D_{\lambda}(\pi)$. This
can be done by observing the following sequence of equalities, in which
$w_{k}=w(s_{k},a_{k},b_{k})$:

$\displaystyle D_{\lambda}P_{\gamma}(\pi)$
$\displaystyle=\lim_{n\to\infty}\sum_{k=0}^{n}\lambda^{k}\sum_{i=0}^{k}\gamma^{k-i}w_{i}$
(2)
$\displaystyle=\lim_{n\to\infty}\sum_{k=0}^{n}\sum_{i=0}^{k}\lambda^{k}\gamma^{k-i}w_{i}$
(3)
$\displaystyle=\lim_{n\to\infty}\sum_{k=0}^{n}\sum_{i=0}^{k}(\gamma\lambda)^{k-i}\lambda^{i}w_{i}$
(4)
$\displaystyle=\left(\lim_{n\to\infty}\sum_{k=0}^{n}(\gamma\lambda)^{k}\right)\left(\lim_{n\to\infty}\sum_{k=0}^{n}\lambda^{k}w_{k}\right)$
(5) $\displaystyle=\frac{D_{\lambda}(\pi)}{1-\gamma\lambda}.$ (6)

The equality (2) is from the definition of $D_{\lambda}P_{\gamma}$. Equalities
(3) and (4) follow from basic algebra. The equality (5) follows from Mertens’
theorem, since
$\left\langle\sum_{i=0}^{k}(\gamma\lambda)^{k-i}\lambda^{i}w_{i}\right\rangle_{k\geq
0}$ is the Cauchy product of
$\left\langle(\gamma\lambda)^{k}\right\rangle_{k\geq 0}$ and
$\left\langle\lambda^{k}w_{k}\right\rangle_{k\geq 0}$. Step (6) is a
consequence of the definition of geometric series and $D_{\lambda}$. ∎

######  Corollary 2.

For discounted past-discounted stochastic games:

  1. 1.

the value is determined in mixed stationary strategies over concurrent arenas;

  2. 2.

the value is determined in positional strategies over turn-based arenas;

  3. 3.

the complexity of the value problem is equivalent to that of discounted games.

##  5 Mean Past-Discounted Games

######  Definition 6.

Let $G=(S,A_{\textnormal{Min}},A_{\textnormal{Max}},w,p)$ be an SGA,
$\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$ be an infinite
play with weight sequence $\left\langle w_{n}\right\rangle_{n\geq
0}=\left\langle w(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$, and
$\gamma\in[0,1)$ be a discount factor. The mean past-discounted payoff is
characterized by the following equation.

$MP_{\gamma}(\pi)\stackrel{{\scriptstyle\mbox{\rm{\tiny
def}}}}{{=}}\liminf_{n\to\infty}\frac{1}{n+1}\sum^{n}_{k=0}P^{k}_{\gamma}(\pi)=\liminf_{n\to\infty}\frac{1}{n+1}\sum_{k=0}^{n}\sum_{i=0}^{k}\gamma^{k-i}w_{i}$
(Mean Past-Discounted Payoff)

Taking a similar approach to Section 4, we show that mean past-discounted
games are determined in stationary strategies. The proof, however, uses
alternate techniques, as Mertens’ theorem fails to apply.

######  Theorem 8.

Given a state $s$ of some SGA and discount factor $\gamma\in[0,1)$ it holds
that

$\mathsf{Val}\left(MP_{\gamma},s\right)=\frac{1}{1-\gamma}\mathsf{Val}\left(M,s\right).$

###### Proof.

To prove this theorem, it suffices to show that
$\mathbb{E}^{\nu,\chi}_{s}(MP_{\gamma})=\frac{1}{1-\gamma}\mathbb{E}^{\nu,\chi}_{s}(M)$
for every pair of strategies
$(\nu,\chi)\in\Sigma_{\textnormal{Min}}\times\Sigma_{\textnormal{Max}}$ and
consistent play $\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$.
This amounts to establishing the equation
$MP_{\gamma}(\pi)=\frac{1}{1-\gamma}M(\pi)$, which is shown in the following
sequence of equalities, where $w_{k}=w(s_{k},a_{k},b_{k})$:

$\displaystyle MP_{\gamma}(\pi)$
$\displaystyle=\liminf_{n\to\infty}\frac{1}{n+1}\sum_{k=0}^{n}\sum_{i=0}^{k}\gamma^{k-i}w_{i}$
(7)
$\displaystyle=\liminf_{n\to\infty}\sum^{n}_{k=0}\frac{w_{k}(1-\gamma^{n+1-k})}{(n+1)(1-\gamma)}$
(8)
$\displaystyle=\liminf_{n\to\infty}\left(\sum^{n}_{k=0}\frac{w_{k}}{(n+1)(1-\gamma)}-\sum^{n}_{k=0}\frac{\gamma^{n+1-k}w_{k}}{(n+1)(1-\gamma)}\right)$
(9)
$\displaystyle=\liminf_{n\to\infty}\sum^{n}_{k=0}\frac{w_{k}}{(n+1)(1-\gamma)}$
(10) $\displaystyle=\frac{M(\pi)}{1-\gamma}.$ (11)

The first and the last equalities, (7) and (11), follow from definition of the
payoff functions $MP_{\gamma}$ and $M$. The equality (8) is justified by the
proof of Lemma 1. Going from (8) to (9) is done via basic algebra. The
equality (10) follows from Lemma 2 and the super-additivity of $\liminf$: for
infinite sequences $\left\langle a_{n}\right\rangle_{n\geq 0}$ and
$\left\langle b_{n}\right\rangle_{n\geq 0}$ the inequality
$\liminf_{n\to\infty}(a_{n}+b_{n})\geq\liminf_{n\to\infty}a_{n}+\liminf_{n\to\infty}b_{n}$
holds, and if either sequence converges, then
$\liminf_{n\to\infty}(a_{n}+b_{n})=\liminf_{n\to\infty}a_{n}+\liminf_{n\to\infty}b_{n}$.
∎

######  Lemma 1.

For every play $\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$
and prefix of length $n\geq 0$

$\frac{1}{n+1}\sum_{k=0}^{n}\sum_{i=0}^{k}\gamma^{k-i}w(s_{i},a_{i},b_{i})=\sum^{n}_{k=0}\frac{w(s_{k},a_{k},b_{k})(1-\gamma^{n+1-k})}{(n+1)(1-\gamma)}.$

###### Proof.

We proceed by induction on $n$. (see Appendix B) ∎

######  Lemma 2.

For every play $\pi=\left\langle(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}$
the following equation holds:

$\liminf_{n\to\infty}\sum^{n}_{k=0}\frac{\gamma^{n+1-k}w(s_{k},a_{k},b_{k})}{(n+1)(1-\gamma)}=0.$

###### Proof.

See Appendix C. ∎

######  Corollary 3.

For mean past-discounted stochastic games:

  1. 1.

the value is determined in mixed stationary strategies over concurrent arenas;

  2. 2.

the value is determined in positional strategies over turn-based arenas;

  3. 3.

the complexity of the value problem is equivalent to games with mean payoff.

The results from section 4, along with classical results for discounted and
mean-payoff games allow us to extend the Tauberian theorem of [5] and relate
asymptotically the values of discounted past-discounted games with the values
of mean past-discounted games.

######  Theorem 9 (Tauberian Theorem).

$\mathsf{Val}\left(MP_{\gamma},s\right)=\lim_{\lambda\uparrow
1}(1-\gamma)\mathsf{Val}\left(D_{\lambda}P_{\gamma},s\right)$

###### Proof.

By Theorem 7, we obtain the equation

$\lim_{\lambda\uparrow
1}(1-\gamma)\mathsf{Val}\left(D_{\lambda}P_{\gamma},s\right)=\lim_{\lambda\uparrow
1}(1-\lambda)\frac{\mathsf{Val}\left(D_{\lambda},s\right)}{1-\gamma\lambda}.$

Applying Theorem 3 to the right-hand side of this equation leads to the
following:

$\lim_{\lambda\uparrow
1}(1-\gamma)\mathsf{Val}\left(D_{\lambda}P_{\gamma},s\right)=\frac{\mathsf{Val}\left(M,s\right)}{1-\gamma}.$

Finally, applying Theorem 8 yields the desired equivalence:

$\lim_{\lambda\uparrow
1}(1-\gamma)\mathsf{Val}\left(D_{\lambda}P_{\gamma},s\right)=\mathsf{Val}\left(MP_{\gamma},s\right).$

∎

##  6 Conclusion

The discounted and mean-payoff objectives have played central roles in the
theory of stochastic games. A multitude of deep results exist connecting these
objectives [5, 6, 32, 4, 17, 14, 38, 39, 40] in addition to an extensive body
of work on algorithms for solving these games and their complexity [24, 33,
34, 15, 22, 13].

Past discounted sums for finite sequences were studied in the context of
optimization [3] and are closely related to exponential recency weighted
average, a technique used in nonstationary multi-armed bandit problems [37] to
estimate the average reward of different actions by giving more weight to
recent outcomes. However, to the best of our knowledge, past-discounting has
not been formally studied as a payoff function for stochastic games until the
present work.

Discounted objectives have found significant applications in areas of program
verification and synthesis [20, 8]. Relatively recently—although the idea of
past operators is quite old [27]—a number of classical formalisms including
temporal logics such as LTL and CTL and the modal $\mu$-calculus have been
extended with past-tense operators and with discounted quantitative semantics
[21, 1, 2]. A particularly significant result [31] around LTL with classical
boolean semantics is that, while LTL with past operators is no more expressive
than standard LTL, it is exponentially more succinct. It remains open whether
this type of relationship holds for other logics and their extensions by past
operators when interpreted with discounted quantitative semantics [2].

Regret minimization [9] is a popular criterion in the setting of online
learning where a decision-maker chooses her actions so as to minimize the
average regret—the difference between the realized reward and the reward that
could have been achieved. We posit that imperfect decision makers may view
their regret in a past-discounted sense, since a suboptimal action in the
recent past tends to cause more regret than an equally suboptimal action in
the distant past. We hope that the results of this work spur further interest
in developing foundations of past-discounted characterizations of regret in
online learning and optimization.

## References

  * Almagor et al. [2014] Shaull Almagor, Udi Boker, and Orna Kupferman.  Discounting in LTL.  In _Tools and Algorithms for the Construction and Analysis of Systems, TACAS_ , volume 8413 of _LNCS_ , pages 424–439. Springer, 2014\.  URL https://doi.org/10.1007/978-3-642-54862-8_37.
  * Almagor et al. [2016] Shaull Almagor, Udi Boker, and Orna Kupferman.  Formally reasoning about quality.  _J. ACM_ , 63(3):24:1–24:56, 2016.  URL https://doi.org/10.1145/2875421.
  * Alur et al. [2012] Rajeev Alur, Loris D’Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan.  Regular functions, cost register automata, and generalized min-cost problems, 2012.
  * Andersson and Miltersen [2009] Daniel Andersson and Peter Bro Miltersen.  The complexity of solving stochastic games on graphs.  In _Algorithms and Computation ISAAC_ , volume 5878 of _LNCS_ , pages 112–121. Springer, 2009.  URL https://doi.org/10.1007/978-3-642-10631-6_13.
  * Bewley and Kohlberg [1976] Truman Bewley and Elon Kohlberg.  The asymptotic theory of stochastic games.  _Mathematics of Operations Research_ , 1(3):197–208, 1976.
  * Bewley and Kohlberg [1978] Truman Bewley and Elon Kohlberg.  On stochastic games with stationary optimal strategies.  _Mathematics of Operations Research_ , 3(2):104–125, 1978.  ISSN 0364765X, 15265471.  URL http://www.jstor.org/stable/3689337.
  * Bordais et al. [2019] Benjamin Bordais, Shibashis Guha, and Jean-François Raskin.  Expected window mean-payoff.  In _39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS_ , volume 150 of _LIPIcs_ , pages 32:1–32:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL https://doi.org/10.4230/LIPIcs.FSTTCS.2019.32.
  * Cerný et al. [2011] Pavol Cerný, Krishnendu Chatterjee, Thomas A. Henzinger, Arjun Radhakrishna, and Rohit Singh.  Quantitative synthesis for concurrent programs.  In _Computer Aided Verification CAV_ , volume 6806 of _Lecture Notes in Computer Science_ , pages 243–259. Springer, 2011.  URL https://doi.org/10.1007/978-3-642-22110-1_20.
  * Cesa-Bianchi and Lugosi [2006] Nicolò Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge University Press, 2006.  ISBN 978-0-521-84108-5.  URL https://doi.org/10.1017/CBO9780511546921.
  * Chatterjee and Fijalkow [2011] Krishnendu Chatterjee and Nathanaël Fijalkow.  A reduction from parity games to simple stochastic games.  In _Proceedings of Second International Symposium on Games, Automata, Logics and Formal Verification, GandALF_ , volume 54 of _EPTCS_ , pages 74–86, 2011.  URL https://doi.org/10.4204/EPTCS.54.6.
  * Chatterjee and Henzinger [2007] Krishnendu Chatterjee and Thomas A. Henzinger.  Probabilistic systems with limsup and liminf objectives.  In _Infinity in Logic and Computation, International Conference, ILC_ , volume 5489 of _Lecture Notes in Computer Science_ , pages 32–45. Springer, 2007.  URL https://doi.org/10.1007/978-3-642-03092-5_4.
  * Chatterjee and Henzinger [2008] Krishnendu Chatterjee and Thomas A. Henzinger.  Value iteration.  In _25 Years of Model Checking - History, Achievements, Perspectives_ , volume 5000 of _Lecture Notes in Computer Science_ , pages 107–138. Springer, 2008.  URL https://doi.org/10.1007/978-3-540-69850-0_7.
  * Chatterjee and Ibsen-Jensen [2015] Krishnendu Chatterjee and Rasmus Ibsen-Jensen.  Qualitative analysis of concurrent mean-payoff games.  _Inf. Comput._ , 242:2–24, 2015.  URL https://doi.org/10.1016/j.ic.2015.03.009.
  * Chatterjee and Majumdar [2012] Krishnendu Chatterjee and Rupak Majumdar.  Discounting and averaging in games across time scales.  _Int. J. Found. Comput. Sci._ , 23(3):609–625, 2012.  URL https://doi.org/10.1142/S0129054112400308.
  * Chatterjee et al. [2008] Krishnendu Chatterjee, Rupak Majumdar, and Thomas A. Henzinger.  Stochastic limit-average games are in EXPTIME.  _Int. J. Game Theory_ , 37(2):219–234, 2008.  URL https://doi.org/10.1007/s00182-007-0110-5.
  * Chatterjee et al. [2009] Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger.  A survey of stochastic games with limsup and liminf objectives.  In _Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP_ , volume 5556 of _Lecture Notes in Computer Science_ , pages 1–15. Springer, 2009.  URL https://doi.org/10.1007/978-3-642-02930-1_1.
  * Chatterjee et al. [2011] Krishnendu Chatterjee, Laurent Doyen, and Rohit Singh.  On memoryless quantitative objectives.  In _Fundamentals of Computation Theory FCT_ , volume 6914 of _Lecture Notes in Computer Science_ , pages 148–159. Springer, 2011.  URL https://doi.org/10.1007/978-3-642-22953-4_13.
  * Chatterjee et al. [2013] Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin.  Looking at mean-payoff and total-payoff through windows.  In _Automated Technology for Verification and Analysis - 11th International Symposium, ATVA_ , volume 8172 of _Lecture Notes in Computer Science_ , pages 118–132. Springer, 2013.  URL https://doi.org/10.1007/978-3-319-02444-8_10.
  * Chatterjee et al. [2015] Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin.  Looking at mean-payoff and total-payoff through windows.  _Inf. Comput._ , 242:25–52, 2015.  URL https://doi.org/10.1016/j.ic.2015.03.010.
  * de Alfaro et al. [2003] Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar.  Discounting the future in systems theory.  In _Automata, Languages and Programming ICALP_ , volume 2719 of _LNCS_ , pages 1022–1037. Springer, 2003.  URL https://doi.org/10.1007/3-540-45061-0_79.
  * de Alfaro et al. [2005] Luca de Alfaro, Marco Faella, Thomas A. Henzinger, Rupak Majumdar, and Mariëlle Stoelinga.  Model checking discounted temporal properties.  _Theor. Comput. Sci._ , 345(1):139–170, 2005\.  URL https://doi.org/10.1016/j.tcs.2005.07.033.
  * Etessami and Yannakakis [2010] Kousha Etessami and Mihalis Yannakakis.  On the complexity of nash equilibria and other fixed points.  _SIAM J. Comput._ , 39(6):2531–2597, 2010.  URL https://doi.org/10.1137/080720826.
  * Filar and Vrieze [1996] Jerzy Filar and Koos Vrieze.  _Competitive Markov Decision Processes_.  Springer-Verlag, Berlin, Heidelberg, 1996.  ISBN 0387948058.
  * Filar and Schultz [1986] Jerzy A. Filar and Todd A. Schultz.  Nonlinear programming and stationary strategies in stochastic games.  _Math. Program._ , 34(2):243–247, 1986.  URL https://doi.org/10.1007/BF01580590.
  * Gawlitza and Seidl [2009] Thomas Gawlitza and Helmut Seidl.  Games through nested fixpoints.  In _Computer Aided Verification, 21st International Conference, CAV_ , volume 5643 of _Lecture Notes in Computer Science_ , pages 291–305. Springer, 2009.  URL https://doi.org/10.1007/978-3-642-02658-4_24.
  * Gimbert [2007] Hugo Gimbert.  Pure stationary optimal strategies in markov decision processes.  In _STACS, 24th Annual Symposium on Theoretical Aspects of Computer Science_ , volume 4393 of _Lecture Notes in Computer Science_ , pages 200–211. Springer, 2007.  URL https://doi.org/10.1007/978-3-540-70918-3_18.
  * Lichtenstein et al. [1985] Orna Lichtenstein, Amir Pnueli, and Lenore D. Zuck.  The glory of the past.  In _Logics of Programs, Conference_ , volume 193 of _LNCS_ , pages 196–218. Springer, 1985.  URL https://doi.org/10.1007/3-540-15648-8_16.
  * Liggett and Lippman [1969] T. M. Liggett and S. A. Lippman.  Short notes: Stochastic games with perfect information and time average payoff.  _SIAM Review_ , 11(4):604–607, 1969.
  * Maitra and Sudderth [1992] A Maitra and William Sudderth.  An operator solution of stochastic games.  _Israel Journal of Mathematics_ , 78(1):33–49, 1992.
  * Maitra and Sudderth [2012] Ashok P Maitra and William D Sudderth.  _Discrete gambling and stochastic games_ , volume 32.  Springer Science & Business Media, 2012.
  * Markey [2003] Nicolas Markey.  Temporal logic with past is exponentially more succinct, concurrency column.  _Bull. EATCS_ , 79:122–128, 2003.
  * Mertens and Neyman [1981] J.F. Mertens and Abraham Neyman.  Stochastic games.  _International Journal of Game Theory_ , 10(2):53–66, 1981.
  * Raghavan and Filar [1991] T. E. S. Raghavan and Jerzy A. Filar.  Algorithms for stochastic games - A survey.  _ZOR Methods Model. Oper. Res._ , 35(6):437–472, 1991.  URL https://doi.org/10.1007/BF01415989.
  * Raghavan and Syed [2003] T. E. S. Raghavan and Zamir Syed.  A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information.  _Math. Program._ , 95(3):513–532, 2003.  URL https://doi.org/10.1007/s10107-002-0312-3.
  * Rudin [1964] Walter Rudin.  _Principles of mathematical analysis_ , volume 3.  McGraw-hill New York, 1964.
  * Shapley [1953] L. S. Shapley.  Stochastic games.  _Proceedings of the National Academy of Sciences_ , 39(10):1095–1100, 1953.  ISSN 0027-8424.  URL https://www.pnas.org/content/39/10/1095.
  * Sutton and Barto [1998] Richard S. Sutton and Andrew G. Barto.  _Reinforcement learning - an introduction_.  Adaptive computation and machine learning. MIT Press, 1998.  ISBN 978-0-262-19398-6.  URL https://www.worldcat.org/oclc/37293240.
  * Ziliotto [2016a] Bruno Ziliotto.  A tauberian theorem for nonexpansive operators and applications to zero-sum stochastic games.  _Mathematics of Operations Research_ , 41(4):1522–1534, 2016a.  URL https://doi.org/10.1287/moor.2016.0788.
  * Ziliotto [2016b] Bruno Ziliotto.  General limit value in zero-sum stochastic games.  _Int. J. Game Theory_ , 45(1-2):353–374, 2016b.  URL https://doi.org/10.1007/s00182-015-0509-3.
  * Ziliotto [2018] Bruno Ziliotto.  Tauberian theorems for general iterations of operators: Applications to zero-sum stochastic games.  _Games Econ. Behav._ , 108:486–503, 2018.  URL https://doi.org/10.1016/j.geb.2018.01.009.

##  Appendix A Additional Details from the Proof of Theorem 5

Define
$h:\Sigma^{G}_{\textnormal{Min}}\cup\Sigma_{\textnormal{Max}}^{G}\to\Sigma^{H}_{\textnormal{Min}}\cup\Sigma_{\textnormal{Max}}^{H}$
and
$g:\Sigma^{H}_{\textnormal{Min}}\cup\Sigma_{\textnormal{Max}}^{H}\to\Sigma^{G}_{\textnormal{Min}}\cup\Sigma_{\textnormal{Max}}^{G}$
as the functions satisfying the following equations, for
$\sigma\in\Sigma^{G}_{\textnormal{Min}}\cup\Sigma^{G}_{\textnormal{Max}}$ and
$\varsigma\in\Sigma^{H}_{\textnormal{Min}}\cup\Sigma^{H}_{\textnormal{Max}}$,
corresponding to eq. 1.

$\displaystyle\sigma(\pi|^{n}_{0},s)$
$\displaystyle=h(\sigma)\left(\varpi|^{n}_{0},\left(s,\pi|^{n-1}_{\max(0,n-1-\ell)}\right)\right)$
$\displaystyle g(\varsigma)(\pi|^{n}_{0},s)$
$\displaystyle=\varsigma\left(\varpi|^{n}_{0},\left(s,\pi|^{n-1}_{\max(0,n-1-\ell)}\right)\right)$

Let $h(\Sigma^{G}_{\textnormal{Min}}),h(\Sigma^{G}_{\textnormal{Max}})$ be the
the image of $h$ on all strategies for the players over $G$, and let
$g(\Sigma^{H}_{\textnormal{Min}}),g(\Sigma^{H}_{\textnormal{Max}})$ be the
image of $g$ on all strategies of the players over $H$.

For every $\nu\in\Sigma_{\textnormal{Min}}^{G}$ there exists
$h(\nu)\in\Sigma_{\textnormal{Min}}^{H}$ and for every
$\chi\in\Sigma_{\textnormal{Max}}^{G}$ there exists
$h(\chi)\in\Sigma_{\textnormal{Max}}^{H}$ such that:

Symmetrically, we have

Lines (12) and (15) follow from the arguments given in the main body of the
proof of Theorem 5. Because of the fact that $h$ is bijective, we have that
$h(\Sigma^{G}_{\textnormal{Min}})=\Sigma^{H}_{\textnormal{Min}}$, for Min, and
likewise for Max, mutatis mutandis. This provides justification for obtaining
(14) from (13) and for obtaining (17) from (16) in the above derivations.

For every $\nu\in\Sigma_{\textnormal{Min}}^{H}$ there exist
$g(\nu)\in\Sigma_{\textnormal{Min}}^{G}$ and for every
$\chi\in\Sigma_{\textnormal{Max}}^{H}$ there exists an
$g(\chi)\in\Sigma_{\textnormal{Max}}^{G}$ such that:

Symmetrically, we have

Lines (18) and (21) follow from the arguments given in the main body of the
proof of Theorem 5. Because of the fact that $g$ is bijective, we have that
$\Sigma^{G}_{\textnormal{Min}}=g(\Sigma^{H}_{\textnormal{Min}})$, and likewise
for Max, mutatis mutandis. This provides justification for obtaining (22) from
(23) and for obtaining (27) from (26) in the above derivations.

##  Appendix B Proof of Lemma 1

For ease of notation, let $w_{k}=w(s_{k},a_{k},b_{k})$.

#### Base case:

Lemma 1 holds for $n=0$.

Let $n=0$, then

$\frac{1}{n+1}\sum_{k=0}^{n}\left(\sum_{i=0}^{k}\gamma^{k-i}w_{i}\right)=w_{0}=\sum^{n}_{k=0}\frac{w_{k}(1-\gamma^{n+1-k})}{(n+1)(1-\gamma)}.$

#### Inductive case:

If Lemma 1 holds for $n-1$, then it also holds for $n$.

Firstly, observe the following derivation:

$\displaystyle\frac{1}{n+1}\sum_{k=0}^{n}\left(\sum_{i=0}^{k}\gamma^{k-i}w_{i}\right)$
$\displaystyle=\sum^{n}_{k=0}\frac{1}{n+1}\sum^{k}_{i=0}\gamma^{k-i}w_{i}$
$\displaystyle=\left(\sum^{n-1}_{k=0}\frac{1}{n+1}\sum^{k}_{i=0}\gamma^{k-i}w_{k}\right)+\frac{1}{n+1}\sum^{n}_{k=0}\gamma^{n-k}w_{k}$
$\displaystyle=\frac{n}{n+1}\left(\sum^{n-1}_{k=0}\frac{1}{n}\sum^{k}_{i=0}\gamma^{k-i}w_{k}\right)+\frac{1}{n+1}\sum^{n}_{k=0}\gamma^{n-k}w_{k}$

Notice that the expression within the parentheses matches exactly the left-
hand side of Lemma 1 for $n-1$. By the inductive hypothesis, we may rewrite
this as follows:

$\frac{1}{n+1}\sum_{k=0}^{n}\left(\sum_{i=0}^{k}\gamma^{k-i}w_{i}\right)=\left(\frac{n}{n+1}\sum^{n-1}_{k=0}\frac{w_{k}(1-\gamma^{n-k})}{n(1-\gamma)}\right)+\left(\frac{1}{n+1}\sum^{n}_{k=0}w_{k}\gamma^{n-k}\right).$

On the right-hand side, the $n$ terms in the left summand cancel, and
factoring $(1-\gamma)$ out of the denominator leaves

$\left(\frac{1}{1-\gamma}\sum^{n-1}_{k=0}\frac{w_{k}(1-\gamma^{n-k})}{n+1}\right)+\left(\sum^{n}_{k=0}\frac{w_{k}\gamma^{n-k}}{n+1}\right).$

Now, factoring again by $\frac{1}{1-\gamma}$ and by $\frac{1}{n+1}$ yields

$\frac{\left(\sum\limits^{n-1}_{k=0}w_{k}(1-\gamma^{n-k})\right)+\left(\sum\limits^{n}_{k=0}w_{k}\gamma^{n-k}(1-\gamma)\right)}{(n+1)(1-\gamma)}.$

Multiplying the terms within the summations in the numerator, we get the
following expression:

$\frac{\left(\sum\limits^{n-1}_{k=0}w_{k}-w_{k}\gamma^{n-k}\right)+\left(\sum\limits^{n}_{k=0}w_{k}\gamma^{n-k}-w_{k}\gamma^{n+1-k}\right)}{(n+1)(1-\gamma)}.$

Taking advantage of additive cancelation in the numerator, we obtain

$\frac{\left(\sum\limits^{n-1}_{k=0}w_{k}\right)+w_{n}-\left(\sum\limits^{n}_{k=0}w_{k}\gamma^{n+1-k}\right)}{(n+1)(1-\gamma)}.$

With some simple regrouping of terms, the above may be rewritten as

$\frac{\sum\limits^{n}_{k=0}w_{k}-\sum\limits^{n}_{k=0}w_{k}\gamma^{n+1-k}}{(n+1)(1-\gamma)},$

and subsequently

$\frac{\sum\limits^{n}_{k=0}w_{k}(1-\gamma^{n+1-k})}{(n+1)(1-\gamma)}.$

Finally, by the linearity of summation, we obtain the desired equality:

$\frac{1}{n+1}\sum_{k=0}^{n}\left(\sum_{i=0}^{k}\gamma^{k-i}w_{i}\right)=\sum^{n}_{k=0}\frac{w_{k}(1-\gamma^{n+1-k})}{(n+1)(1-\gamma)}.$

∎

##  Appendix C Proof of Lemma 2

By assumption the sequence $w(\pi)=\left\langle
w(s_{n},a_{n},b_{n})\right\rangle_{n\geq 0}=\left\langle
w_{n}\right\rangle_{n\geq 0}$ is bounded, and so the values $\overline{w}=\sup
w(\pi)$ and $\underline{w}=\inf w(\pi)$ are well-defined as greatest and least
scalar values occurring anywhere in $w(\pi)$. The following derivation shows
that $\sum^{n}_{k=0}\frac{w_{k}\gamma^{n+1-k}}{(n+1)(1-\gamma)}$ is bounded
above by zero.

$\displaystyle\lim_{n\to\infty}\sum^{n}_{k=0}\frac{\overline{w}\gamma^{n+1-k}}{(n+1)(1-\gamma)}$
$\displaystyle=\frac{1}{1-\gamma}\lim_{n\to\infty}\left(\frac{1}{(n+1)(1-\gamma)}\sum^{n}_{k=0}\overline{w}\gamma^{n+1-k}\right)$
$\displaystyle=\frac{1}{1-\gamma}\lim_{n\to\infty}\left(\left(\frac{1}{n+1}\right)\left(\frac{\overline{w}(1-\gamma^{n+1})}{1-\gamma}\right)\right)$
$\displaystyle=\frac{1}{1-\gamma}\lim_{n\to\infty}\left(\frac{1}{n+1}\right)\lim_{n\to\infty}\left(\frac{\overline{w}(1-\gamma^{n+1})}{1-\gamma}\right)$
$\displaystyle=\frac{1}{1-\gamma}\cdot 0\cdot\frac{\overline{w}}{1-\gamma}=0$

Similarly, we may obtain an identical equation using $\inf w(\pi)$:

$\lim_{n\to\infty}\sum^{n}_{k=0}\frac{\underline{w}\gamma^{n+1-k}}{(n+1)(1-\gamma)}=0$

showing that $\sum^{n}_{k=0}\frac{w_{k}\gamma^{n+1-k}}{(n+1)(1-\gamma)}$ is
bounded below by zero as well. Since this sequence is bounded on both sides by
zero, it must converge to zero. ∎