Fictitious play in zero-sum stochastic games

Introduction

A common justification for Nash equilibrium is that it arises from the learning dynamics of myopic players taking greedy best response actions. This perspective has been investigated for various classes of strategic-form games (also referred to as one-shot or normal-form games) mostly focusing on best-response type dynamics (including fictitious play) . Nevertheless study of learning dynamics in the context of stochastic games has been limited.

Stochastic games were introduced by to model interactions among multiple players in a multi-state dynamic environment. Players’ actions determine not only the payoffs at the current state, stage payoffs, but also the transition probability to the next state, and hence the continuation payoffs. The decision problem of a player thus involves trading off current stage payoff for estimated continuation payoffs while forming predictions on the opponent’s strategy. This dynamic trade-off makes the analysis of learning in stochastic games potentially challenging.

In this paper, we present a novel variant of fictitious play combining classical fictitious play with $Q$-learning for stochastic games and analyze its convergence properties in two-player zero-sum stochastic games. Each player forms a belief on the opponent’s (stationary) mixed strategy and her own $Q$-function, which corresponds to her continuation payoff given the opponent’s strategy. Players play a greedy best response strategy in an auxiliary game with player payoffs given by the sum of the stage payoffs and estimated continuation payoffs. At each stage of the game over the infinite horizon, the players update their beliefs on the opponent strategy from the observation of the other player’s action. The update of the $Q$-function is then constructed as the maximum payoff that can be attained in the auxiliary game over all possible actions (given beliefs on opponent play and $Q$-function).

A key property of our learning dynamics is that the beliefs on opponent strategy and $Q$-functions are updated simultaneously though the update of the latter is at a slower timescale than the former. This is consistent with the literature on evolutionary game theory, e.g., see and also the closely related recent paper , which we discuss below.

We show that beliefs on the opponent strategy converge to a (stationary) Nash equilibrium of zero-sum stochastic games under the assumption that each state is visited infinitely often in both the model-based case and model-free case. In the model-free case, players do not know their own payoff functions and the underlying state transition probabilities, however, each player can still observe her realized stage payoff and the current state of the game, as in the reinforcement learning literature. Similarly, beliefs on $Q$-functions converge to the $Q$-functions associated with the equilibrium strategies in both cases.

The fictitious play dynamics presented here reduce to the classical fictitious play when there is only one state and inherit the following features of the classical fictitious play: $i)$ The dynamics do not require knowledge of the underlying game’s type and is not specific to any specific class of games. $ii)$ Following this scheme, players attain the best performance against an opponent following an asymptotically stationary strategy. $iii)$ If the dynamics converge, it must converge to an equilibrium of the underlying game.

As a first challenge, we note that even though the players play best response strategies in the auxiliary games associated with each state, the players do not necessarily play the same auxiliary game repeatedly because their payoff matrices, i.e., $Q$-functions, are time-varying and depend on the play at other states. Since these auxiliary game are not time-invariant, the convergence results for fictitious play or best response dynamics in zero-sum strategic-form games with repeated play, e.g., , are not directly applicable to zero-sum stochastic games. We remove this dependency by approximating the discrete-time update via a differential inclusion (specific to each state) at the timescale of the beliefs on strategies as if the beliefs on $Q$-functions are time-invariant. To this end, we interpret an appropriate affine interpolation of the discrete-time update as a perturbed solution to a certain differential inclusion and characterize its limit set via a Lyapunov function argument, as shown by .

As a second challenge, we note that when the players do not share a common belief about the $Q$-function, their individual beliefs do not necessarily sum to zero due to the independent updates. Hence, the auxiliary games are non-zero-sum in general. This is problematic since it is well-known that fictitious play (or any uncoupled learning dynamic that does not incorporate the opponent’s objective) cannot converge to an equilibrium in every class of non-zero-sum games . To address this challenge, we exploit the structure of the stochastic game and construct a new Lyapunov function for both zero-sum and non-zero-sum games.

For zero-sum games, our Lyapunov function reduces to the Lyapunov function presented by for continuous-time best response dynamics in zero-sum strategic-form games. For non-zero sum games, this new Lyapunov function enables us to characterize the limit set of the beliefs on strategies in terms of how much the sum of beliefs on $Q$-functions deviates from zero. We exploit this characterization via the asynchronous stochastic approximation methods, provided by , to show that the beliefs on $Q$-functions sum to zero asymptotically (although they do not necessarily sum to zero in finite time). We emphasize that the zero-sum structure of stage-payoffs of the underlying stochastic game is crucial for this result to hold.

2 Related Works

Our paper is most closely related to the recent paper which presents and studies a continuous-time best-response dynamics for zero-sum stochastic games. They consider dynamics where each player selects a mixed strategy in an auxiliary game and updates her strategy in the direction of her best response to opponent’s current mixed strategy in the auxiliary game. A single continuation payoff (common among the players) is updated at a slower speed representing the time average of the auxiliary game payoffs up to time $t$. The common update ensures that the auxiliary game is always zero-sum. This allows building on the convergence analysis provided by since two-timescale learning enables the mixed strategies to track an equilibrium associated with the estimates of the continuation-payoffs. In , the authors generalized the convergence result in (that extends the convergence result in to continuous-time dynamics) to settings with asymptotically negligible (tracking) error, thus establishing convergence of their dynamics in zero-sum stochastic games.

Their dynamics involve updating mixed strategies at every state at every time. Hence, the authors study also an alternative update rule by considering a continuous-time embedding of the actual play of the stochastic game where game transitions according to a controlled continuous-time Markov chain. Our paper instead considers dynamics where each player follows a best response pure action in the auxiliary game (without any specific tie-breaking rule) while updating her $Q$-function using her belief on the opponent strategy and her current $Q$-function estimate. Therefore, estimates of $Q$-functions do not necessarily sum to zero leading to an auxiliary game that is not necessarily zero-sum. Furthermore players update their beliefs on opponent strategy only for the current state within the course of stochastic game without need for such a continuous-time embedding.

Other related papers include , , and . In , the author presented and studied the minimax-value iteration in zero-sum stochastic games, which can be viewed as a generalization of value iteration in Markov decision problems to zero-sum stochastic game settings by replacing the optimization with the minimax-value of the auxiliary zero-sum game. showed that the minimax-value iteration converges to a unique point, establishing existence of a stationary equilibrium in zero-sum stochastic games. The minimax value iteration necessitates computation of the minimax-value of the auxiliary game at each stage. This can be done by solving a collection of linear programs (LPs), one per state at each iteration which can be computationally demanding.

To mitigate the need to solve LPs at each iteration, in , the authors presented and studied a fictitious play like discrete-time update rule to find an equilibrium in zero-sum stochastic games without solving LPs. This update rule involves each player playing a best-response in an auxiliary game with a common continuation payoff as in , which preserves the zero-sum nature of the auxiliary game. However, unlike , in , the players update the continuation payoff using the payoff estimate of one of the players, which simplifies the analysis, but is not a natural update process. The dynamics reduce to fictitious play applied to a convergent sequence of zero-sum strategic-form games for each state.

For time-averaged stochastic games, in , the authors focused on a special class with two players, two states and two actions (per state), and provided an example in which the fictitious play presented does not necessarily converge to a stationary equilibrium. This is in contrast with results for two-player two-action strategic-form games, where fictitious play is known to converge to an equilibrium with a certain tie-breaking rule (see ), or when the game has the “diagonal property” for any tie-breaking rule (see ).

Our paper is also related to a number of papers on multi-agent reinforcement learning, e.g., see the survey in and the references therein. Particularly noteworthy is which presented a model-free version of ’s minimax-value iteration via a Q-learning-type algorithm, called Minimax-Q. Similar to Shapley’s minimax value iteration, Minimax-Q assumes a zero-sum structure and therefore is specific to zero-sum games.

Alternative to Minimax-Q, in , the author presented a fictitious-play-like dynamics, called Hyper-Q, which applies beyond zero-sum games. Hyper-Q has dynamics similar to ours, however, evolves over a single timescale without any convergence guarantee in any specific class of stochastic games. On the other hand, in , the author presented an actor-critic-type learning algorithm that is also not specific to zero-sum games. Contrary to Hyper-Q, there players do not seek to learn opponent strategies based on actions taken. He showed that a certain (weighted) empirical distribution of the joint actions taken converges to the set of (a modified version of) generalized Nash equilibria in stochastic games provided that each state-action pair is visited infinitely often and frequently enough. This is a weaker sense of convergence compared to our result although it is for stochastic games beyond zero-sum.

Other than the papers reviewed above, there are also several other multi-player reinforcement learning algorithms that are shown to have good convergence properties in stochastic games with respect to certain performance measures provided that every player follows rules which at times may not align with their best interests. For example, in and more recently , the authors focused on scenarios where players play in a coordinated manner a finite-horizon-version of a zero-sum stochastic game within repeated episodes, referred to as episodic reinforcement learning, even though player payoffs are defined over infinite horizon. In another line of work, in and , the authors presented and studied algorithms that update policies only at certain time instances while keeping them fixed in between –even when players may have incentive to change their actions– in order to create a stationary environment for learning the underlying model or estimating the associated $Q$-functions.

3 Organization

The rest of the paper is organized as follows. In Sections 2 and 3, we model stochastic games and our fictitious play scheme, respectively. We present the assumptions and the convergence results in Section 4. We provide preliminary information on a convergence result on asynchronous discrete-time iterations that we use in the proof of the convergence results in Section 5. The proofs of the main convergence results in the model-based and model-free settings are provided, respectively, in Section 6 and Section 7. In Section 8, we provide an illustrative example. We conclude the paper with some remarks in Section 9.

Stochastic Games

Consider two players that interact with each other by taking actions in a dynamic environment over an infinite horizon with discrete time $k=0,1,\ldots$. The players collect a stage payoff depending on their actions and the current state of the environment, which also determines the next state. A two-player zero-sum stochastic game is a tuple $\langle S,A,r,p,\gamma\rangle$ constructed as follows.

Let $S$ be a set of finitely many states.

Let $A^{i}$ be the set of finitely many actions that player $i$ can take at any state $s\in S$.This can be generalized to the case where action spaces depend on state straightforwardly. Furthermore, $A:=A^{1}\times A^{2}$ denotes the set of action profiles $a=(a^{1},a^{2})$ for $a^{i}\in A^{i}$, $i=1,2$.

Let $\gamma\in(0,1)$ denote a discount factor that affects the importance of future stage payoffs.

We focus on stationary (Markov) strategies, meaning that at each stage each player plays a mixed action that depends only on the current state (and not for example on time). This does not cause any loss of generality due to the existence result in . More specifically, for each $i=1,2$, we denote by $\pi^{i}(s,a^{i})\in$ the probability that player $i$ takes action $a^{i}$ at state $s$ and the stationary strategy of player $i$ by $\pi^{i}$. Let us also denote the strategy profile by $\pi:=\{\pi^{1},\pi^{2}\}$. Correspondingly, $a_{k}=(a_{k}^{1},a_{k}^{2})$ is the action profile at stage $k$.

We define the expected utility of player $i$ under the strategy profile $\pi$ as the expected discounted sum of stage payoffs

where $\{s_{k}\sim p(\cdot|s_{k-1},a_{k-1})\}_{k>0}$ and $\{a_{k}\sim\pi(s_{k},\cdot)\}_{k\geq 0}$ are stochastic processes, respectively, representing the state and the action profile at each stage $k$ and the expectation is taken with respect to all randomness induced by the initial state distribution $s_{0}\sim p_{o}\in\Delta(S)$, the state transition kernel and strategy profile $\pi$.For a set $X$, we denote the probability simplex by $\Delta(X)$.

At each stage of a stochastic game, the action profile determines the current stage-payoff and the stage-payoffs that will be received in future stages by determining the next state (since stage-payoffs also depend on the state). Correspondingly, if player $i$ knew that the opponent $-i$ is playing according to the stationary strategy $\pi^{-i}$, then the value of the action profile $a\in A$ at current state $s$, denoted by $Q^{i}(s,a)$ (and known as $Q$-function), would satisfy the following fixed-point equation

which corresponds to the maximum value player $i$ would get in the associated auxiliary stage-game. Note that the dependence of $Q^{i}$ and $v^{i}$ on $\pi^{-i}$ is implicit in (3) and (4) for notational convenience.

We also note that in two-player zero-sum stochastic games, there may exist multiple stationary equilibria in two-player zero-sum stochastic games. However, the $Q$-functions and value functions associated with any stationary equilibrium are all the same . We denote them, respectively, by $(Q_{*}^{1},Q^{2}_{*})$ and $(v_{*}^{1},v_{*}^{2})$.

Though a stochastic game can be viewed as a collection of such auxiliary stage-games that are being played repeatedly and asynchronously, the opponent’s strategy and the $Q$-function are not readily available to the players. Furthermore, these auxiliary stage-games are not necessarily stationary. However, as in the classical fictitious play, the players can form beliefs on them based on the empirical play as if they are stationary. Given this observation, in the following section, we introduce fictitious-play-type learning dynamics that combines the classical fictitious play with the $Q$-learning for stochastic games.

Fictitious Play in Stochastic Games

We consider scenarios where players follow fictitious play dynamics in which they not only form beliefs on the opponent’s strategy but also on the $Q$-function based on the history of the play. They take the greedy best action in the associated auxiliary stage-game conditioned on their beliefs. We emphasize that the players do not know the opponent’s objective. In other words, they do not possess the knowledge that the underlying game is zero-sum.

In the following, we describe the learning dynamics for the typical player $1$ in both model-based and model-free settings. The dynamics for the typical opponent player $2$ is a mirror of it.

Let $s\in S$ denote the current state at stage $k\geq 0$. Player $1$ and simultaneously player $2$ take their greedy best response actions $a_{k}^{1}\in A^{1}$ and $a_{k}^{2}\in A^{2}$. For example, player $1$ can take any action satisfying

according to arbitrary tie-breaking rules. Without loss of generality, we consider pure actions as degenerate mixed strategies giving probability one to the associated action, i.e., $A^{i}\subset\Delta(A^{i})$. The players can observe the opponent’s action. Hence, player $1$ updates her belief on player $2$’s strategy at the current state $s$ according to

where $\alpha_{\#s}\in(0,1]$ is a step-size specific to $\#s$, representing the number of times that $s$ gets visited until (and including) stage $k$.

Furthermore, player $1$ updates her belief on her own $Q$-function only for the current state $s$. The update of $\hat{Q}_{k}^{1}(s)$ is given by

and again $\beta_{\#s}\in(0,1]$ is a step-size specific to $\#s$.

Player $1$ does not update her beliefs associated with other states, i.e., $\hat{\pi}_{k+1}^{2}(s^{\prime})=\hat{\pi}_{k}^{2}(s^{\prime})$ and $\hat{Q}_{k+1}^{1}(s^{\prime})=\hat{Q}_{k}^{1}(s^{\prime})$ if $s^{\prime}\neq s$, i.e., if $s^{\prime}$ is not the current state. A description of the dynamics is tabulated in Table 1.

Note that given the definition of $\hat{v}_{k}^{i}(s)$ in (8), we do not necessarily have $\hat{v}_{k}^{1}(s)+\hat{v}_{k}^{2}(s)=0$ for all $s\in S$. Moreover, when $\hat{v}_{k}^{1}(s)+\hat{v}_{k}^{2}(s)\neq 0$ for some $s\in S$, then by (7), we do not necessarily have $\hat{Q}_{k+1}^{1}(s)+\hat{Q}_{k+1}^{2}(s)$ equal to the zero matrix for all $s\in S$. Therefore, the auxiliary stage-games need not be zero-sum in this learning dynamics.

Alternatively, consider the scenario where player $1$ and player $2$ update their beliefs on $Q$-functions as in (7) but with

In the scenarios where the auxiliary stage-games remain always zero-sum, the convergence analysis is a direct application of the two-timescale stochastic approximation theory built on the convergence result for fictitious play in zero-sum strategic-form games (with repeated play) provided by and the convergence result for the minimax value iteration provided by . However, this is not the case when players follow an uncoupled learning dynamics, such as our two-timescale fictitious play, and its convergence analysis necessitates development of new technical tools specific to the structure of stochastic games rather than resorting directly to the two-timescale stochastic approximation theory.

2 Fictitious Play for the Model-free Setting

Next we consider the scenarios where players do not know their own stage payoff function and the transition probabilities. They can still observe their current stage payoff (realized), current state (visited), and the current action (taken by the opponent). Given the beliefs on $Q$-functions, the players take the actions according to (5) while they may also take some random action with some small probability $\epsilon>0$ to experiment stochastic state transitions, as in . For example, player $1$ can take action

where $a_{*}^{1}$ is a greedy best response satisfying (5) while $u^{1}\sim\mathcal{U}(A^{1})$ with $\mathcal{U}(\cdot)$ denoting the uniform distribution over the associated set. We focus on this basic exploration strategy as a proof of concept. The players can also resort to more sophisticated strategies to speed up their exploration, e.g., see .

Players still update their beliefs on opponent strategy according to (6). However since player $1$ and player $2$ cannot update their beliefs on $Q$-functions as in (7) without knowing state transition probabilities, they instead follow a $Q$-learning-type of update described as follows.

where $\hat{v}_{k}^{i}$ is as described in (8). Note that here $\beta_{\#(s,a)}\in(0,1]$ is a step-size specific to $\#(s,a)$ representing the number of times state-action pair $(s,a)$ occurs until (and including) stage $k$. Note also that player $1$ does not update $\hat{Q}_{k}^{1}$ associated with other state-action pairs, i.e., $\hat{Q}_{k+1}^{1}(s^{\prime},a^{\prime})=\hat{Q}_{k}^{1}(s^{\prime},a^{\prime})$ if $(s^{\prime},a^{\prime})\neq(s,a)$, i.e., if either $s^{\prime}$ is not the current state or $a^{\prime}$ is not the current action profile. A description of the model-free dynamics is tabulated in Table 2. Note that $\hat{Q}_{k-1}^{i}(s_{k-1},a_{k-1})$ gets updated after $s_{k}$ is observed. Therefore, the updates of beliefs take place at different orders in Tables 1 and 2.

Main Result

In this paper, we focus on whether the beliefs formed on the opponent’s strategies and $Q$-functions converge to a stationary equilibrium and the corresponding $Q$-functions in zero-sum stochastic games, or not. The answer is affirmative for both model-based and model-free settings under certain assumptions provided below precisely.

Each state is visited infinitely often with probability one.

Players update their beliefs associated with a state only when that state is visited. This assumption ensures that players have sufficient time to revise and improve their beliefs. Furthermore, it holds, if the stochastic game is irreducible, e.g., transition probabilities between any pair of states are positive for any joint action as in .

The step sizes $\{\alpha_{c}\in(0,1]\}_{c=0}^{\infty}$ and $\{\beta_{c}\in(0,1]\}_{c=0}^{\infty}$ satisfy $\sum_{c=0}^{\infty}\alpha_{c}=\infty,\,\sum_{c=0}^{\infty}\beta_{c}=\infty$, and $\lim_{c\rightarrow\infty}\alpha_{c}=\lim_{c\rightarrow\infty}\beta_{c}=0$. The beliefs on $Q$-functions are updated at a slower timescale compared to the timescale in which the beliefs on strategies are updated, i.e., $\lim_{c\rightarrow\infty}\frac{\beta_{c}}{\alpha_{c}}=0.$

Now we are ready to present the convergence results specific to zero-sum stochastic games.

Suppose that Sections 4 and 4 hold. When both players follow the fictitious play dynamics described in Table 1, i.e., (5)-(7), the beliefs on strategies and $Q$-functions, respectively, converge to a stationary equilibrium and the corresponding $Q$-functions in zero-sum stochastic games almost surely. In other words, for some stationary equilibrium $\pi_{*}=(\pi^{1}_{*},\pi^{2}_{*})$, we have $(\hat{\pi}_{k}^{1},\hat{\pi}_{k}^{2})\rightarrow(\pi^{1}_{*},\pi^{2}_{*})$ and $(\hat{Q}_{k}^{1},\hat{Q}_{k}^{2})\rightarrow(Q^{1}_{*},Q^{2}_{*})$, as $k\rightarrow\infty$, with probability $1$.

The following corollary to Theorem 4.1 characterizes the convergence properties of the dynamics in two-player general-sum stochastic games in terms of how much the stage-payoffs deviate from the zero-sum structure. Particularly, it shows convergence of the dynamics to a near equilibrium in near zero-sum stochastic games.

Suppose that Sections 4 and 4 hold and both players follow the fictitious play dynamics described in Table 1, i.e., (5)-(7). Then, in two-player general-sum stochastic games, we have

for all $(s,a)$ and $d:=\max_{(s,a)}|r^{1}(s,a)+r^{2}(s,a)|$.

In the model-free setting, players can update only a single entry of the belief on $Q$-function corresponding to the current action profile. This strengthens the coupling across states and makes the dynamics difficult to track. Furthermore, the players can only observe the realization of the state transitions, which introduces stochastic approximation errors in the learning dynamics. Hence, we make the following assumption to limit the impact of the coupling and the stochastic approximation errors.

The step sizes satisfy $\sum_{c=0}^{\infty}\alpha_{c}^{2}<\infty$ and $\sum_{c=0}^{\infty}\beta_{c}^{2}<\infty$. The sequence $\{\beta_{c}\}_{c\geq 0}$ is monotonically decreasing. We have $\lim_{c\rightarrow\infty}\frac{\beta_{\lfloor mc\rfloor}}{\alpha_{c}}=0$ for any $m\in(0,1]$.

The first part of Section 4 ensures that the stochastic approximation terms are square integrable Martingale difference sequences conditioned on the history. On the other hand, the second part of Section 4 ensures that $\beta_{\#(s,a)}/\alpha_{\#s}$ gets arbitrarily small asymptotically even though $\#(s,a)$ increases more slowly than $\#s$. We also emphasize that Sections 4 and 4 are properties of step sizes and do not impose further conditions on zero-sum stochastic games for which the results hold. For example, the step sizes given by $\alpha_{c}=(c+1)^{-\rho_{\alpha}}$ and $\beta_{c}=(c+1)^{-\rho_{\beta}}$, where $1/2<\rho_{\alpha}<\rho_{\beta}\leq 1$, satisfy Sections 4 and 4.

The following theorem characterizes the convergence properties of fictitious play for the model-free setting.

Suppose that Sections 4, 4, and 4 hold. When both players follow the fictitious play dynamics described in Table 2, i.e., (10), (6), and (11), the beliefs on strategies and $Q$-functions converge to a near equilibrium and the equilibrium $Q$-functions with an approximation level linear in the exploration probability $\epsilon>0$, almost surely. More explicitly, we have

with probability $1$, where $D=\frac{1}{1-\gamma}\sum_{i}\max_{(s,a)}|r^{i}(s,a)|$.

Note that if the players decrease their exploration probability at a suitable rate, the learning dynamics for the model-free case can also converge to an exact equilibrium of the stochastic game, e.g., see [14, Section 5]. Note also that the analysis can be generalized to the case with independent random perturbations of stage-payoffs (with compact support) straightforwardly, as shown in the extended version [24, Section 6.3].

We provide the proofs of Theorems 4.1 and 4.3 in Sections 6 and 7, respectively.

In the following section, we provide a theorem characterizing the convergence properties of asynchronous discrete-time iterations to be used in the proofs of Theorems 4.1 and 4.3.

On the Convergence of Asynchronous Discrete-time Iterations

The following theorem follows from a slight modification of the result in [30, Theorem 3] to address the impact of error terms that are asymptotically bounded (or negligible as a special case).

Consider a sequence of vectors $\{y_{k}\}_{k=0}^{\infty}$ such that the $n$th entry, denoted by $y_{k}[n]$, satisfies the following upper and lower bounds:

a scalar discount factor $\gamma\in(0,1)$,

the step size $\beta_{n,k}\in$ satisfies $\sum_{k=0}^{\infty}\beta_{n,k}=\infty$, $\lim_{k\rightarrow\infty}\beta_{n,k}=0$ for each $n$ with probability $1$,The condition that $\sum_{k=0}^{\infty}\beta_{n,k}=\infty$ for each $n$ implies that the non-negative $\beta_{n,k}$ is positive infinitely many times as $k\rightarrow\infty$ (and therefore, each entry of the vector gets updated infinitely often).

Suppose that $\|y_{k}\|_{\infty}\leq T$ for all $k$. Then we have

with probability $1$, provided that either $\omega_{n,k}=0$ for all $n,k$ or $\sum_{k=0}^{\infty}\beta_{n,k}^{2}<\infty$ for each $n$ with probability $1$.

Step $i)$ Since $\gamma\in(0,1)$, fix some $\varepsilon>0$ such that $\gamma+2\varepsilon<1$. By (16) and $\|y_{k}\|_{\infty}\leq D$ for all $k$, there exists $k^{0}$ and $D^{0}$ such that

for all $k\geq k^{0}$. We define a sequence $\{D^{t}\}_{t=0}^{\infty}$, initialized by $D^{0}$ and evolving according to

Since $\gamma+2\varepsilon\in(0,1)$, we have $\lim_{t\rightarrow\infty}D^{t}=0$.

Step $ii)$ Suppose that for some $t>0$, there exists $k^{t}$ such that the following holds:

for all $k\geq k^{t}$. Our goal is to show that there exists $k^{t+1}\geq k^{t}$ such that

Let us start by restraining the error terms $\underline{\epsilon}_{k},\overline{\epsilon}_{k}$ and $\omega_{n,k}$ via the auxiliary sequences $\{Y_{k}^{t}\}_{k=k^{t}}^{\infty}$ and $\{W_{k}^{t}\}_{k=k^{t}}^{\infty}$ defined by the following recursions:

respectively. The following lemma highlights the role of these two auxiliary sequences.

By definitions (22) and (23), we already have the inequality (24) for $k=k^{t}$. Now suppose that the inequality (24) holds for some $k>k^{t}$. Then by the upper bound on $y_{k+1}[n]$, as described in (15a), and the assumption (20), we have

while by the lower bound on $y_{k+1}[n]$, as described in (15b), and (20), we have

The convergence properties of $Y_{k}^{t}[n]$ and $W_{k}^{t}[n]$ are well-known when $\{\beta_{n,k}\}$ satisfies certain conditions. For example the term $\left[(\gamma+\varepsilon)D^{t}+\frac{c}{1-\gamma}\right]$ in the recursion of $Y_{k}^{t}[n]$, (22), is fixed for all $k>k^{t}$. Therefore, $Y_{k}^{t}[n]$ evolves as a convex combination of the previous iterate and this fixed term, and gets closer and closer to the fixed term since $\sum_{k=0}^{\infty}\beta_{n,k}=\infty$. On the other hand $\{W_{k}^{t}[n]\}$ corresponds to the classical stochastic gradient algorithm for minimizing a quadratic cost function, whose convergence is well-established if the step sizes also satisfy $\sum_{k=0}^{\infty}\beta_{n,k}^{2}<\infty$, e.g., see . Therefore we have

with probability $1$. Therefore, there exists $k^{t+1}\geq k^{t}$ such that $|Y_{k}^{t}[n]+W_{k}^{t}[n]|\leq(\gamma+2\varepsilon)D^{t}+\frac{c}{1-\gamma}$, almost surely, and $|\overline{\epsilon}_{k}|\leq\varepsilon D^{t+1}+c$ and $|\underline{\epsilon}_{k}|\leq\varepsilon D^{t+1}+c$. We obtain (21) since $D^{t+1}=(\gamma+2\varepsilon)D^{t}$. By induction, (20) holds for all $t$, and the fact that $D^{t}\rightarrow 0$ as $t\rightarrow\infty$ yields (17).

Proof of Theorem 4.1: Convergence for the Model-based Setting

We divide the proof into three main steps: $i)$ We first decouple the dynamics across states over the fast timescale. $ii)$ We next zoom into the local dynamics specific to each state and characterize their limit set via a novel Lyapunov function argument addressing the deviation of auxiliary stage-games from zero-sum structure in two-player zero-sum stochastic games. $iii)$ We then zoom out to global dynamics across every state over the slow timescale and show that the beliefs on $Q$-functions sum to zero asymptotically, and then show that estimates of continuation payoffs track the minimax values associated with the beliefs on $Q$-functions. Finally, we show that the beliefs on $Q$-functions converge to the unique $Q$-functions of an equilibrium of the underlying zero-sum stochastic game.

We can now delve into the technical details.We omit the qualification “with probability $1$” since we have already discarded the suitable set of measure zero, where Section 4 does not hold.

Let $s_{k}$ denote the current state at stage $k$. Based on (6), we can write the updates of the beliefs on strategies for state $s\in S$ as

2 Step ii)ii) Zooming into the local dynamics at the fast timescale

It is instructive to examine the continuous-time best response dynamics in zero-sum strategic-form games. For a fixed (absolutely continuous) solution to (29), e.g., $(\boldsymbol{\pi}^{1}(t),\boldsymbol{\pi}^{2}(t))$, [10, Section 4] showed that

Our goal here is to modify $V_{H}(\boldsymbol{\pi}^{1}(t),\boldsymbol{\pi}^{2}(t))$ to general-sum settings for which the possibility that

poses a challenge as can be seen in (34). Hence as a candidate Lyapunov function, instead we propose

It is also instructive to note that the set $\{x:V(x)=0\}$ is not necessarily the set of equilibria for the continuous-time best response dynamics, (29). However, validity of this candidate function implies that for any solution to the best-response dynamics (29), the sum

The following lemma shows that $V(\cdot)$ is indeed a Lyapunov function.

where the strict inequality follows since $\lambda>1$. Therefore, the absolutely continuous $L(t)$ is strictly decreasing whenever $L(t)\geq 0$.

Lemma 6.1 and the stochastic differential inclusion yield that

and the limit set of the Lyapunov function $\{x:V(x)=0\}$ is given by

In the following step, we characterize the convergence properties of the beliefs on $Q$-functions by using (42).

3 Step iii)iii) Zooming out to the global dynamics at the slow timescale

We will first show that the sum of the payoff matrices in the auxiliary games, i.e.,

converges to zero based on the limit set characterization (42), and then we will use this result to show that $\hat{v}_{k}^{i}(s)$ tracks the saddle point associated with $\hat{Q}_{k}^{i}(s)$, denoted by

By definition of the Lyapunov function (37), we can write (42) as

where we define the sum $\bar{v}_{k}(s):=\hat{v}_{k}^{1}(s)+\hat{v}_{k}^{2}(s)$. This implies that the sum $\bar{v}_{k}(s)$ is less than or equal to $\lambda\|\bar{Q}_{k}(s)\|_{\max}$ in the limit. On the other hand, we can bound $\bar{v}_{k}(s)$ from below by $-\lambda\|\bar{Q}_{k}(s)\|_{\max}$ as follows:

since $\lambda>1$. Combining (45) and (46), we obtain

where $\overline{\epsilon}_{k}(s)$ is an asymptotically negligible error for each $s\in S$. Based on (47) and Theorem 5.1 , the following lemma exploits the fact that $r_{s}^{1}(a)+r_{s}^{2}(a)=0$ for all $(s,a)$, and shows that the auxiliary games become zero-sum in the limit even though they are not necessarily zero-sum in finite time.

$\|\bar{Q}_{k}(s)\|_{\max}\rightarrow 0$ as $k\rightarrow\infty$ for each $s$.

The proof follows from $i)$ writing the sum $\bar{Q}_{k}$ in a recursive form based on the updates of $(\hat{Q}_{k}^{1},\hat{Q}_{k}^{2})$ and then $ii)$ showing that this recursion satisfies the conditions listed in Theorem 5.1 .

Step $a)$ Based on the fact that $r^{1}(s,a)+r^{2}(s,a)=0$ for all $(s,a)$, the update of the beliefs on $Q$-functions, as described in (7), yields that

Step $b)$ Based on (47) and (48), we can bound $\bar{Q}_{k+1}(s,a)$ as follows

Since the maximum norm of $\bar{Q}_{k}(s)$ converges to zero by Lemma 6.3, the upper bound on $\bar{v}_{k}$, as described in (47), implies

Based on (50) and Lemma 6.3, the following lemma shows that estimates of continuation payoffs track the minimax values associated with the beliefs on $Q$-functions.

Set $i=1$. Then, the stationary-point inequality says that

Since $\bar{Q}_{k}(s)=\hat{Q}_{k}^{1}(s)+\hat{Q}_{k}^{2}(s)$, the right-hand side is bounded from below by

Since $\bar{v}_{k}(s)=\hat{v}_{k}^{1}(s)+\hat{v}_{k}^{2}(s)$, the left-hand side goes to zero by Lemma 6.3 and (50). By symmetry, the result can be generalized to $i=2$, which completes the proof.

Next we introduce the Shapley operator $\mathcal{T}^{i}$ for each $i=1,2$, where

showed that the Shapley operators have contraction property, i.e.,

At stage $k$ and state $s\in S$, the update of beliefs on $Q$-functions, e.g., (7), can be written as

$|\hat{Q}_{k}^{i}(s,a)-Q_{*}^{i}(s,a)|\rightarrow 0$ as $k\rightarrow\infty$, for each $(i,s,a)$.

Denote $\widetilde{Q}_{k}^{i}:=\hat{Q}_{k}^{i}-Q^{i}_{*}$. If we subtract the fixed point $Q_{*}^{i}(s,a)$ from both hand side at (57), we obtain

since $\mathcal{T}^{i}Q_{*}^{i}=Q_{*}^{i}$. Correspondingly, (55) yields that

4 Proof of Corollary 4.2

The proof follows similar lines with the proof of Theorem 4.1 except the last step. For example, we now have

by Theorem 5.1. Correspondingly, (47) yields that

since $\lambda<1/\gamma$ by its definition. Invoking Theorem 5.1 again completes the proof.

Proof of Theorem 4.3: Convergence for the Model-free Setting

The proof of Theorem 4.3 follows similar lines with the proof of Theorem 4.1. However, we face additional challenges such as the players update the beliefs on the $Q$-functions only for the current state and joint action pair, and they explore by taking any action randomly since they do not know their payoff functions and state transition probabilities. In the following, we focus on how to address these challenges.

Step $i)$ Decoupling the dynamics at the fast timescale. Similar to (27), the update of the belief on $Q$-function at stage $k$ could be written as

where $s_{k},s_{k+1}$ denote the current and next states, and $a_{k}$ denotes the current action profile. The beliefs on the $Q$-functions remain bounded also in the model-free setting. Particularly, for each $s\in S$, we have

If $|A^{1}|\times|A^{2}|=1$, then $\#(s,a)=\#s$ and the result follows from Section 4 since the iterates are bounded. Suppose $|A^{1}|\times|A^{2}|>1$. Then, (64) yields that

Therefore, the error term is asymptotically negligible if we have

for arbitrary $\tau>0$ based on the Borel-Cantelli Lemma.

Next, we will formulate an upper bound on . The exploration with probability $\epsilon>0$ ensures that the probability that the joint action $a$ occurs is bounded from below by $\underline{p}:=\epsilon^{2}/(|A^{1}||A^{2}|)>0$ and from above by $\overline{p}:=1-\underline{p}$ since there exists $a^{\prime}\neq a$ (by $|A^{1}|\times|A^{2}|>1$) and the minimum probability that $a^{\prime}$ occurs is also $\underline{p}$. Therefore, we can bound from above by

Since $\{\beta_{c}\}_{c\geq 0}$ is monotonically decreasing, we have

This can also be interpreted as for any given $m$, there exists $C$ such that for all $c\geq C$, the ratio $\beta_{l}/\alpha_{c}$ can be larger than $\tau$ only if $l<mc$, or equivalently,

because $H(\cdot)$ is a continuous function taking values between zero ($H(0)=H(1)=0$) and one ($H(1/2)=1$), and $(1-\underline{p})\in(0,1)$. Then, we obtain , for all $c\geq C$, where $\xi\in(0,1)$. Therefore, we have

for any $\tau$. This completes the proof.

Step $ii)$ Zooming into the local dynamics at the fast timescale. Lemma 7.1 enables us to decouple dynamics across states as in Section 6. Given that player $i$ takes $a_{k}^{i}$, (10) yields that the update of $\hat{\pi}_{k}^{i}$ can be written as

where the stochastic approximation error induced by the fixed-probability exploration is given by

due to the exploration and $\bar{u}^{i}:=\frac{1}{|A^{i}|}\mathbf{1}$, for $i=1,2$. To address this, we modify the Lyapunov function (37) as follows:

Step $iii)$ Zooming out to the global dynamics at the slow timescale. Let us select the arbitrary $\lambda>1$ such that $\lambda(1-\epsilon)<1$ in addition that $\lambda\gamma<1$. By (78), as a counterpart of (47), we have

but with an error term satisfying $\limsup_{k\rightarrow\infty}|\overline{\epsilon}_{k}(s)|\leq\lambda\epsilon(D^{1}+D^{2})$ (and $D^{i}$ is as described in (64)) for each $s\in S$. Furthermore, we need to consider stochastic approximation error terms induced by sampling the underlying state transition probabilities, which is given by

for each $i=1,2$, and it is a square integrable Martingale difference sequence by its definition. Note that the sum of approximation errors $\bar{\omega}_{k}:=\omega_{k}^{1}+\omega_{k}^{2}$ is also a square integrable Martingale difference sequence. Then, the proof follows after some algebra similar to the ones in Step $iii)$ in the proof of Theorem 4.1.

Based on (79) and (80), the evolution of $\bar{Q}_{s,k}$ satisfies

On the other hand, the inequalities (79) (81) yield that

since $\lambda<1/\gamma$ by its definition. Therefore, integrating (81) and (82) into (53), we obtain

Based on the definition of the Shapley operator (54), the evolution of $\widetilde{Q}_{k}^{i}(s,a)=\hat{Q}_{k}^{i}(s,a)-Q_{*}^{i}(s,a)$ can be written as

due to the tracking result (83).Independent zero-mean compact support random perturbations on the stage-payoffs will again not constitute a technical challenge here because we can incorporate them to the stochastic approximation error. Following the lines in Lemma 6.7, we can again resort to Theorem 5.1 based on the contraction property of the Shapley operator and obtain (14) because

Furthermore, based on (56) and (83), (86) yields that

Finally, to characterize the convergence properties of the beliefs on the opponent strategies, we will first make explicit the dependence of $Q$-function and value function, respectively, as described in (3) and (4), on the opponent strategy. For example, they are now denoted by $Q^{i}(s,a\,|\,\pi^{-i})$ and $v^{i}(s\,|\,\pi^{-i})$ with slight abuse of notation given that the opponent plays according to $\pi^{-i}$. Furthermore, we pick player $1$ as the typical player. For all $s$ and $k$, we have

where the last line follows from the triangle inequality after we add and subtract $Q_{*}^{1}(s)$. We have already characterized the convergence properties of the second term on the right-hand side in (86). On the other hand, the definitions of $Q^{1}(s,a\,|\,\hat{\pi}_{k}^{2})$ and $Q_{*}^{1}(s)$ yield that

On the other hand, by the definition of the equilibrium value function, we have

By the limit characterizations (86) and (87), and the symmetry across players, we obtain

This is important because for any $\pi^{1}$, we have

since $v_{*}^{1}(s)+v_{*}^{2}(s)=0$ for all $s$. Combined with (92), this completes the proof of Theorem 4.3.

An Illustrative Example

In this section, we examine our fictitious play dynamics numerically in a zero-sum stochastic game whose configuration is selected arbitrarily. For example, there are $3$ states, players have $4$ actions per state, and the discount factor $\gamma=0.8$. State transition probabilities and stage payoffs are chosen randomly in a way that players can have preferences over the states so that they would face the trade-off between current stage payoff and the continuation payoffs. We set the step sizes as $\alpha_{c}=1/(1+c)^{0.51}$ and $\beta_{c}=1/(1+c)$ such that they would satisfy both Sections 4 and 4. Furthermore in the model-free setting, players take a random action with probability $0.02$ in order to learn the unknown state transition probabilities associated with each action.

Concluding Remarks

We presented fictitious play dynamics for stochastic games and analyzed its convergence properties in zero-sum games. In the dynamics presented, players form a belief not only on opponent (stationary) strategy but also on the associated $Q$-functions and update them based on the actions taken by the opponent. The update of beliefs on $Q$-functions evolves at a slower timescale compared to the evolution of beliefs on strategies.

In order to show the convergence of the dynamics, we first approximated the dynamics via a certain differential inclusion at the timescale of the fast update and formulated a novel Lyapunov function for it in order to characterize the limiting behavior of the fast update. Then we used this characterization accompanied with certain contraction arguments at the timescale of the slow update in order to show the almost sure convergence of the dynamics. In particular, we showed that beliefs on strategies and $Q$-functions, respectively, converge to a stationary equilibrium and the corresponding $Q$-functions in the model-based and model-free settings provided that each state is visited infinitely often.

Some of the future research directions include the analyses of this framework $(i)$ in other classes of games, e.g., identical-interest games or zero-sum games with more than two players; $(ii)$ without the conditions on visiting each state infinitely-often, e.g., in terms of self-confirming equilibrium, as studied in for learning in extensive-form game; $(iii)$ with function approximation to address computational challenge due to large state and action spaces; and $(iv)$ with non-asymptotic convergence guarantees.

References