Decentralized Q-Learning in Zero-sum Markov Games

Introduction

Reinforcement learning (RL) has achieved tremendous successes recently in a wide range of applications, including playing the game of Go (Silver et al., 2017), playing video games (e.g., Atari (Mnih et al., 2015) and Starcraft (Vinyals et al., 2019)), robotics (Lillicrap et al., 2015; Kober et al., 2013), and autonomous driving (Shalev-Shwartz et al., 2016; Sallab et al., 2017). Most of these applications involve multiple decision-makers, where the agents’ rewards and the evolution of the system are affected by the joint behaviors of all agents. This setting naturally leads to the problem of multi-agent RL (MARL). In fact, MARL is arguably one key ingredient of large-scale and reliable autonomy, and is significantly more challenging to analyze than single-agent RL. There has been a surging interest recently in both a deeper theoretical and empirical understanding of MARL; see comprehensive overviews on this topic in Busoniu et al. (2008); Zhang et al. (2021); Hernandez-Leal et al. (2019).

The pioneering work that initiated the sub-area of MARL, where the model of Markov/stochastic games (Shapley, 1953) has been considered as a framework, is Littman (1994). Since then, there has been a plethora of works on MARL in Markov games; see a detailed literature review in the supplementary material. These algorithms can be broadly categorized into two types: centralized/coordinated and decentralized/independent ones. For the former type, it is assumed that there exists a central controller for the agents, who can access the agents joint actions and local observations. With full awareness of the game setup, the central controller coordinates the agents to optimize their own policies, and aims to compute an equilibrium. This centralized paradigm is typically suitable for the scenarios when a simulator of the game is accessible (Silver et al., 2017; Vinyals et al., 2017). Most existing MARL algorithms in Markov games have focused on this paradigm.

Nevertheless, in many practical multi-agent learning scenarios, e.g., multi-robot control (Wang and de Silva, 2008), urban traffic control (Kuyer et al., 2008), as well as economics with rational decision-makers (Fudenberg and Levine, 1998), agents make decentralized decisions without a coordinator. Specifically, agents make updates independently with only local observations of their own payoff and action histories, usually in a myopic fashion. Besides its ubiquity in practice, this decentralized paradigm also has the advantage of being scalable, as each agent only cares about her own policy and/or value functions, and the algorithms complexity do not suffer from the exponential dependence on the number of agents.

Unfortunately, establishing provably convergent decentralized MARL algorithms is well-known to be challenging; see the non-convergent cases (even in the fully cooperative setting) in Tan (1993); Boutilier (1996); Claus and Boutilier (1998), and see Matignon et al. (2012) for more empirical evidences. The key challenge is the non-stationarity of the environment from each agent’s perspective since all agents are adapting their policies simultaneously and independently. In other words, the opponent is not playing according to a stationary strategy. This non-stationarity issue is in fact one of the core issues in (decentralized) MARL (Busoniu et al., 2008; Hernandez-Leal et al., 2017).

Studying when self-interested players can converge to an equilibrium through non-equilibrium adaptation is core question in the related literature of learning in games (Fudenberg and Levine, 1998, 2009). For example, simple and stylized learning dynamics, such as fictitious play, are shown to converge to an equilibrium in certain but important classes of games, e.g., zero-sum (Robinson, 1951; Harris, 1998) and common-interest (Monderer and Shapley, 1996), in repeated play of the same game. However, we cannot generalize these results to decentralized MARL in Markov games (also known as stochastic games, introduced by Shapley (1953)), because agents strategies affect not only the immediate reward, as in the repeated play of the same strategic-form game, but also the rewards that will be received in the future. Therefore, the configuration of the induced stage games are not necessarily stationary in Markov games.

Contributions. In this paper, we present a provably convergent decentralized MARL learning dynamicsTo emphasize the difference from many existing MARL algorithms that focus on the computation of Nash equilibrium, we refer to our update rule as learning dynamics, following the literature of learning in games. for zero-sum discounted Markov games over an infinite horizon with minimal information available to agents. Particularly, each agent only has access to her immediate reward and the current state with perfect recall. They do not have access to the immediate reward the opponent receives. They do not know a model of their reward functions and the underlying state transitions probabilities. They are oblivious to the zero-sum structure of the underlying game. They also do not observe the opponent’s actions. Indeed, they may even be oblivious to the presence of other agents. Learning dynamics with such minimal information is also referred to as being radically uncoupled or value-based in the literature of learning in games (Foster and Young, 2006; Leslie and Collins, 2005).

To address the non-stationarity issue, we advocate a two-timescale adaptation of the individual $Q$-learning, introduced by Leslie and Collins (2005) and originating in Fudenberg and Levine (1998). Particularly, each agent infers the opponent’s strategy indirectly through an estimate of the local $Q$-function (a function of the opponent’s strategy) and simultaneously forms an estimate of the value function to infer the continuation payoff. The slow update of the value function estimate is natural since agents tend to change their strategies faster than their estimates (as observed in the evolutionary game theory literature, e.g., Ely and Yilankaya (2001); Sandholm (2001)), but this also helps weakening the dependence between the configuration of the stage games (specifically the global $Q$-functions) and the strategies. We show the almost sure convergence of the learning dynamics to the Nash equilibrium using the stochastic approximation theory, by developing a novel Lyapunov function and identifying the sufficient conditions precisely later in §3. Our techniques toward addressing these challenges might be of independent interest. We also verify the convergence of the learning dynamics via numerical examples.

To the best of our knowledge, our learning dynamics appears to be one of the first provably convergent decentralized MARL learning dynamics for Markov games that enjoy all the appealing properties below, addressing an important open question in the literature (Pérolat et al., 2018; Daskalakis et al., 2020). In particular, our learning dynamics –

requires only minimal information available to the agents, i.e., it is a radically uncoupled learning dynamic, unlike many other MARL algorithm, e.g., Pérolat et al. (2015); Sidford et al. (2019); Leslie et al. (2020); Sayin et al. (2020); Bai and Jin (2020); Xie et al. (2020); Zhang et al. (2020); Liu et al. (2020); Shah et al. (2020);

requires no coordination or communication between agents during learning. For example, agents always play the (smoothed) best response consistent with their self-interested decision-making, contrary to being coordinated to keep playing the same strategy within certain time intervals as in Arslan and Yuksel (2017) and Wei et al. (2021);

requires no asymmetric update rules and/or stepsizes for the agents unlike existing literature (Vrieze and Tijs, 1982), (Bowling and Veloso, 2002), (Leslie and Collins, 2003), (Daskalakis et al., 2020), (Zhao et al., 2021; Guo et al., 2021). Such an asymmetry implies implicit coordination between agents to decide who follows which update rule or who chooses which stepsize (and correspondingly who reacts fast or slow). Daskalakis et al. (2020) refers to each agent playing a symmetric role in learning as strongly independent learning.

is both rational and convergent, a desired property for MARL (independent of whether it is centralized or decentralized), e.g., see Bowling and Veloso (2001); Busoniu et al. (2008). A MARL algorithm is rational if each agent can converge to best-response, when the opponent plays an (asymptotically) stationary strategy; and it can converge only to an equilibrium when all agents adopt it.

A detailed literature review is deferred to the supplementary material due to space limitations. Of particular relevance are two recent works Tian et al. (2020) and Wei et al. (2021) studied decentralized setting similar to ours. Tian et al. (2020) focused on the exploration aspect for finite-horizon settings, and focused on minimizing a weak notion of regret without providing convergence guarantees under self-play.Note that the same update rule with different stepsize and bonus choices and a certified policy technique, however, can return a non-Markovian approximate Nash equilibrium policy pair in the self-play setting; see Bai et al. (2020) for more details. Wei et al. (2021) presented an optimistic variant of the gradient descent-ascent method that shares similar desired properties with our learning dynamics, with a strong guarantee of last-iterate convergence rates. However, the algorithm is delicately designed and different from the common value/policy-based RL update rules, e.g., $Q$-learning, as in our work. Moreover, to characterize finite-time convergence, in the model-free setting, the agents need to coordinate to interact multiple steps at each iteration of the algorithm, while our learning dynamics is coordination-free with natural update rules. These two works can thus be viewed as orthogonal to ours. After submitting our paper, we became aware of a concurrent and independent work Guo et al. (2021), which also developed a decentralized algorithm for zero-sum Markov games with function approximation and finite-sample guarantees. In contrast to our learning dynamics, the algorithm requires a double-loop update rule, and thus is asymmetric and requires coordination between agents. The assumptions and technical novelties in both works are also fundamentally different. See §A.2 for a detailed comparison.

Organization. The rest of the paper is organized as follows. We describe Markov games and our decentralized $Q$-learning dynamics in §2. In §3, we present the assumptions and the convergence results. In §4, we provide numerical examples. We conclude the paper with some remarks in §5. The supplementary material includes a detailed literature review and the proofs of technical results.

Decentralized Q𝑄Q-learning in Zero-sum Markov Games

This section presents a decentralized $Q$-learning dynamics that does not need access to the opponent’s actions and does not need to know the zero-sum structure of the underlying Markov game. To this end, we first start by providing a formal description of Markov games.

where $\{s_{0}\sim p_{o},s_{k+1}\sim p(\cdot|s_{k},a_{k}^{1},a_{k}^{2}),k\geq 0\}$ is a stochastic process describing the evolution of the state over time and $p_{o}\in\Delta(S)$ is the initial state distribution. The expectation is taken with respect to the initial state, randomness induced by state transitions and mixed strategies.

A strategy profile $(\pi_{*}^{1},\pi_{*}^{2})$ is an $\varepsilon$-Nash equilibrium of the Markov game with $\varepsilon\geq 0$ provided that

A Nash equilibrium is an $\varepsilon$-Nash equilibrium with $\varepsilon=0$. It is known that such a Nash equilibrium exists for discounted Markov games (Fink, 1964; Filar and Vrieze, 2012).

Given a strategy profile $\pi:=(\pi^{1},\pi^{2})$, we define the value function of player $i$ by

as well as the local $Q$-function for player $i$ as

where $-i$ denotes the opponent of player $i$.

By the one-stage deviation principle, we can interpret the interaction between the players at each stage as they are playing an auxiliary stage game, in which the payoff functions are equal to the $Q$-functions, e.g., see Shapley (1953). However, the $Q$-functions, and correspondingly the payoff functions in these auxiliary stage games, change with evolving strategies of the players. Therefore, the plethora of existing results for repeated play of the same strategic-form game (e.g., see the review Fudenberg and Levine (2009)) do not generalize here. To address this challenge, we next introduce our decentralized $Q$-learning dynamics.

In our decentralized $Q$-learning dynamics, minimal information is available to players. In other words, they only have access to the immediate reward received and current state visited with perfect recall. They do not observe the actions taken by the opponent. Correspondingly, they cannot form a belief about the opponent’s strategy based on the empirical play as in fictitious play (Fudenberg and Levine, 1998) or its variant for stochastic games (Sayin et al., 2020). Instead, the players can look for inferring the opponent’s strategy, e.g., by estimating the local $Q$-function since the local $Q$-function contains information about the opponent’s strategy, as illustrated in Figure 1. As seen in Figure 1, however, the local $Q$-function also depends on the global $Q$-function while the global $Q$-function is not necessarily stationary since it depends on the value function, and therefore, depends on the players’ evolving strategies. An estimate of the global $Q$ function which is slowly evolving would make it relatively stationary compared to the strategies. However, the players cannot estimate the global $Q$-function directly since they do not have access to the opponent’s actions. Instead, they estimate the value function while updating it at a slower timescale. The slow update of the value function estimate makes the implicit global $Q$-function relatively stationary compared to the strategies. Therefore, the players can use the local $Q$-function estimate to infer the opponent’s strategy.

Note that the local $Q$-function estimate for different actions would get updated asynchronously via the classical $Q$-learning algorithm since they would be updated only when the associated action is taken, however, the actions are likely to be taken at different frequencies. Instead, here the players update the local $Q$-function estimate via a learning dynamics inspired from the individual $Q$-learning. The individual $Q$-learning, presented by Leslie and Collins (2005) and originating in Fudenberg and Levine (1998), is based on the $Q$-learning with soft-max exploration while the step sizes are normalized with the probability of the actions taken. This normalization ensures that the estimates for every action get updated at the same learning rate in the expectation. We elaborate further on this after we introduce the precise update of the local $Q$-function estimate later in this section.

Each player $i$ keeps track of $\{\hat{q}_{s,k}^{i}\}_{s\in S}$ and $\{\hat{v}_{s,k}^{i}\}_{s\in S}$ estimating, respectively, the local $Q$-function and the value function. Player $i$ updates $\{\hat{q}_{s,k}^{i}\}_{s\in S}$ at a faster timescale than $\{\hat{v}_{s,k}^{i}\}_{s\in S}$. Players also count the number of times each state $s$ is visited (until the current stage), denoted by $\#s$.

We assume players know that the reward function takes values in $[-R,R]$ for some $R\in(0,\infty)$, i.e., $|r_{s}^{i}(a^{1},a^{2})|\leq R$ for all $(i,s,a^{1},a^{2})$. Therefore, player $i$ knows that his local $Q$-function $\|q_{\pi}^{i}(s,\cdot)\|_{\infty}\leq R/(1-\gamma)=:D$ and the value function $|v_{\pi}^{i}(s)|\leq D$ for any strategy profile $\pi$ and $s\in S$. Correspondingly, the players initiate these estimates arbitrarily such that $\|\hat{q}_{s,0}^{i}\|_{\infty}\leq D$ and $|\hat{v}_{s,0}^{i}|\leq D$, for all $s$.

We let player $i$ update his local $Q$-function estimate’s entry associated with the current state and local action pair $(s_{k},a_{k}^{i})$ towards the reward received plus the discounted continuation payoff estimate. To this end, we include $\hat{v}_{s_{k+1},k}^{i}$ as an unbiased estimate of the continuation payoff obtained by looking one stage ahead, as in the classical $Q$-learning introduced by Watkins and Dayan (1992). Due to the one-stage look ahead, the update for the current state and local action can take place just after the game visits the next state. The update of $\hat{q}_{s_{k},k}^{i}$ is given by

where $\bar{\alpha}_{k}^{i}\in(0,1]$ is defined by $\bar{\alpha}_{k}^{i}:=\min\left\{1,\frac{\alpha_{\#s_{k}}}{\overline{\pi}_{k}^{i}[a_{k}^{i}]}\right\}$, with $\{\alpha_{c}\}_{c>0}$ a step size sequence, and $r_{k}^{i}\in[-R,R]$ denotes the immediate reward of player $i$ at stage $k$. There is no update on others, i.e., $\hat{q}_{s,k+1}^{i}[a^{i}]=\hat{q}_{s,k}^{i}[a^{i}]$ for all $(s,a^{i})\neq(s_{k},a_{k}^{i})$. Inspired by the approach in Leslie and Collins (2005), the normalization addresses the asynchronous update of the entries of the local $Q$-function estimate and ensures that every entry of the local $Q$-function estimate is updated at the same rate in expectation. We will show this explicitly in the proof of main theorem in the supplementary material.

Simultaneous to updating the local $Q$-function estimate, player $i$ updates his value function estimate $\hat{v}_{s_{k},k}^{i}$ towards $\overline{\pi}_{k}^{i}\cdot\hat{q}_{s_{k},k}^{i}$ corresponding to the expected value of the current state. However, the player uses a different step size $\{\beta_{c}\}_{c>0}$ and updates $\hat{v}_{s_{k},k}^{i}$ according to

For other states $s\neq s_{k}$, there is no update on the value function estimate, i.e., $\hat{v}_{s,k+1}^{i}=\hat{v}_{s,k}^{i}$. To sum up, player $i$ follows the learning dynamics in Table 1. We emphasize that this dynamic is radically uncoupled since each player’s update rule does not depend on the opponent’s payoffs or actions. In the next section, we study its convergence properties.

Convergence Results

We study whether the value function estimates in the learning dynamics, described in Table 1, converge to an equilibrium value of the zero-sum Markov game. The answer is affirmative under certain conditions provided below precisely. The first assumption (with two parts) is related to the step sizes and the temperature parameter, and not to the properties of the Markov game model.

Assumption 1-i. The sequences $\{\alpha_{c}\in(0,1)\}_{c>0}$ and $\{\beta_{c}\in(0,1)\}_{c>0}$ are non-increasing and satisfy $\sum_{c=1}^{\infty}\alpha_{c}=\infty$, $\sum_{c=1}^{\infty}\beta_{c}=\infty$, and $\lim_{c\rightarrow\infty}\alpha_{c}=\lim_{c\rightarrow\infty}\beta_{c}=0$.

Assumption 3 is a common assumption used in stochastic approximation theory, e.g., see Benaim (1999); Borkar (2008). On the other hand, Assumption 3 imposes further condition on the step sizes than the usual two-timescale learning assumption, e.g., $\lim_{c\rightarrow\infty}\frac{\beta_{c}}{\alpha_{c}}=0$, to address the asynchronous update of the iterates. Particularly, the iterates evolving at fast timescale can lag behind even the iterates evolving at slow timescale due to their asynchronous update. Assumption 3 ensures that this can be tolerated when states are visited at comparable frequencies.

Such learning dynamics is not guaranteed to converge to an equilibrium in every class of zero-sum Markov games. For example, the underlying Markov chain may have an absorbing state such that once the game reaches that state, it stays there forever. Then, the players will not have a chance to improve their estimates for other states. Therefore, in the following, we identify two sets of assumptions (in addition to Assumption 3) imposing increasingly stronger conditions on the underlying game while resulting in different convergence guarantees.

Assumption 2-i. Given any pair of states $(s,s^{\prime})$, there exists at least one sequence of actions such that $s^{\prime}$ is reachable from $s$ with some positive probability within a finite number, $n$, of stages.

Assumption 2-ii. The sequence $\{\tau_{c}\}_{c>0}$ is non-increasing and satisfies $\lim_{c\rightarrow\infty}(\tau_{c+1}-\tau_{c})/\alpha_{c}=0$ and $\lim_{c\rightarrow\infty}\tau_{c}=\epsilon$ for some $\epsilon>0$. The step size $\{\alpha_{c}\}_{c>0}$ satisfies $\sum_{c=1}^{\infty}\alpha_{c}^{2}<\infty$.

In Assumption 3, we do not let the temperature parameter go to zero. Next we let $\lim_{c\rightarrow\infty}\tau_{c}=0$ but make the following assumption, imposing further condition on the underlying game and $\{\alpha_{c}\}_{c>0}$ compared to Assumption 3 to ensure that each state gets visited infinitely often at comparable frequencies and the normalization in the update of the local $Q$-function estimate does not cause an issue since it can be arbitrarily small when $\tau_{c}\rightarrow 0$.

Assumption 2’-i. Given any pair of states $(s,s^{\prime})$ and any infinite sequence of actions, $s^{\prime}$ is reachable from $s$ with some positive probability within a finite number, $n$, of stages.

Assumption 2’-ii. The sequence $\{\tau_{c}\}_{c>0}$ is non-increasing and satisfies $\lim_{c\rightarrow\infty}(\tau_{c+1}-\tau_{c})/\alpha_{c}=0$ and $\lim_{c\rightarrow\infty}\tau_{c}=0$. The step size $\{\alpha_{c}\}_{c>0}$ satisfies $\sum_{c=1}^{\infty}\alpha_{c}^{2-\rho}<\infty$, for some $\rho\in(0,1)$. There exists $C,C^{\prime}\in(0,\infty)$ such that $\alpha_{c}^{\rho}\exp\left(4D/\tau_{c}\right)\leq C^{\prime}$ for all $c\geq C$.

While being stronger than Assumption 3, Assumption 3 is still weaker than those used in Leslie et al. (2020). In Leslie et al. (2020), it is assumed that there is a positive probability of reaching from any state to any other state in one stage for any joint action taken by the players. On the other hand, we say that a Markov game is irreducible if given any pure stationary strategy profile, the states visited form an irreducible Markov chain (Hoffman and Karp, 1966; Brafman and Tennenholtz, 2002). Assumption 3 is akin to the irreducibility assumption for Markov games because the irreducibility assumption implies that there is a positive probability that any state is visited from any state within $|S|$ stages. Furthermore, it reduces to the ergodicity property of Markov decision problems, e.g., see Kearns and Singh (2002), if one of the players has only one action at every state.

As an example, $\alpha_{c}=c^{-\rho_{\alpha}}$ and $\beta_{c}=c^{-\rho_{\beta}}$, where $0.5<\rho_{\alpha}<\rho_{\beta}\leq 1$ satisfies Assumptions 3 and 3. There exists $\rho\in(0,2-1/\rho_{\alpha})$ for the latter since $\rho_{\alpha}\in(0.5,1)$. To satisfy Assumption 3, the players can choose the temperature parameter $\{\tau_{c}\}_{c>0}$ as

with some $\bar{\tau}>0$. On the other hand, to satisfy Assumption 3, they can choose the temperature parameter $\{\tau_{c}^{\prime}\}_{c>0}$ as

Alternative to (11), $\tau_{c}=\max\{\epsilon,\tau_{c}^{\prime}\}$ also satisfies Assumption 3 while having similar nature with (12). We provide the relevant technical details in the supplementary material.

We have the following key properties for the estimate sequence generated by our learning dynamics.

Proposition 1. Since $\bar{\alpha}_{k}^{i}\in(0,1]$ for all $k\geq 0$, $\beta_{c}\in(0,1)$ for all $c>0$, $\|\hat{q}_{s,0}^{i}\|_{\infty}\leq D$ and $|\hat{v}_{s,0}^{i}|\leq D$ for all $(i,s)$, the iterates are bounded, i.e., $\|\hat{q}_{s,k}^{i}\|_{\infty}\leq D$ and $|\hat{v}_{s,k}^{i}|\leq D$ for all $(i,s)$ and $k\geq 0$.

for all $\#s_{k}\geq C_{s_{k}}$ since $\alpha_{\#s_{k}}/\overline{\pi}_{k}^{i}[a_{k}^{i}]\leq|A_{s_{k}}^{i}|\alpha_{\#s_{k}}\exp\left(2D/\tau_{\#s_{k}}\right)\leq 1$ by (7).

Proposition 3. Suppose that either Assumption 3 or Assumption 3 holds. Then, at any stage $k$, there is a fixed positive probability, e.g., $\underline{p}>0$, that the game visits any state $s$ at least once within $n$-stages independent of how players play. Therefore, $\#s\rightarrow\infty$ as $k\rightarrow\infty$ with probability $1$.

Proposition 3 says that defining $\bar{\alpha}_{k}^{i}=\min\{1,\alpha_{\#s_{k}}/\overline{\pi}_{k}^{i}[a_{k}^{i}]\}$ ensures that the iterates remain bounded. On the other hand, Propositions 3 and 3 say that the update of the local $Q$-function estimates reduces to (13) where $\bar{\alpha}_{k}^{i}=\alpha_{\#s_{k}}/\overline{\pi}_{k}^{i}[a_{k}^{i}]$ after a finite number of stages, almost surely. The following theorem characterizes the convergence properties of the $Q$-learning dynamics presented.

Theorem 1. Suppose that both players follow the learning dynamics described in Table 1 and Assumption 3 holds. Let $v_{\pi_{*}}^{i}$ and $Q_{\pi_{*}}^{i}$, as described resp. in (3) and (4), be the unique values associated with some equilibrium profile $\pi_{*}=(\pi_{*}^{1},\pi_{*}^{2})$ of the underlying zero-sum Markov game. Then, the asymptotic behavior of the value function estimates $\{\hat{v}_{s,k}^{i}\}_{k\geq 0}$ is given by

for all $(i,s)\in\{1,2\}\times S$, with probability (w.p.) $1$, where $\xi:=\max_{s^{\prime}\in S}\left\{\log(|A_{s^{\prime}}^{1}||A_{s^{\prime}}^{2}|)\right\}$, and $g(\gamma)=\frac{2+\lambda-\lambda\gamma}{(1-\lambda\gamma)(1-\gamma)}$ with some $\lambda\in(1,1/\gamma)$.

Furthermore, let $\hat{\pi}_{s,k}^{i}$ be the weighted time-average of the smoothed best response updated as

Then, the asymptotic behavior of these weighted averages $\{\hat{\pi}_{k}^{i}\}_{k\geq 0}$ is given by

for all $(i,s)\in\{1,2\}\times S$, w.p. $1$, where h(\gamma)=\big{[}4\gamma\cdot g(\gamma)+2(1+\lambda)/(1-\lambda\gamma)\big{]}/(1-\gamma), i.e., these weighted-average strategies converge to near or exact equilibrium depending on whether Assumption 3 or 3 hold.

A brief sketch of the proof is as follows: We decouple the dynamics specific to a single state from others by addressing the asynchronous update of the local $Q$-function estimate and the diminishing temperature parameter. We then approximate the dynamics specific to a single state via its limiting ordinary differential equation (o.d.e.) as if the iterates evolving at the slow timescale are time-invariant. We present a novel Lyapunov function for the limiting o.d.e. to characterize the limit set of the discrete-time update. This Lyapunov function shows that the game perceived by the agents become zero-sum asymptotically and the local $Q$-function estimates are asymptotically belief-based. Finally, we use this limit set characterization to show the convergence of the dynamics across every state by using asynchronous stochastic approximation methods, e.g., see Tsitsiklis (1994).

The following corollary to Theorem 3 highlights the rationality property of our learning dynamics.

for all $s\in S$, w.p. $1$, where $\xi^{i}:=\max_{s^{\prime}\in S}\left\{\log(|A_{s^{\prime}}^{i}|)\right\}$ and $g(\cdot)$ is as described in Theorem 3.

Furthermore, the asymptotic behavior of the weighted averages $\{\hat{\pi}_{k}^{i}\}_{k\geq 0}$, described in Theorem 3, is given by

for all $s\in S$, w.p. $1$, where $h(\gamma)$ is as described in Theorem 3, i.e., these weighted-average strategies converge to near or exact best-response strategy, depending on whether Assumption 3 or 3 hold.

Simulation Results

All the simulations are executed on a desktop computer equipped with a 3.7 GHz Hexa-Core Intel Core i7-8700K processor with Matlab R2019b. The device also has two 8GB 3000MHz DDR4 memories and a NVIDIA GeForce GTX 1080 8GB GDDR5X graphic card. For illustration, we consider a zero-sum Markov game with $5$ states and $3$ actions at each state, i.e., $S=\{1,2,\cdots,5\}$ and $A_{s}^{i}=\{1,2,3\}$. The discount factor $\gamma=0.6$. The reward functions are chosen randomly in a way that $r^{1}_{s}(a^{1},a^{2})\propto\bar{r}_{s,a^{1},a^{2}}\cdot\exp{(s^{2})}$ for $s\in S$, where $\bar{r}_{s,a^{1},a^{2}}$ is uniformly drawn from $$.$r^{1}_{s}(a^{1},a^{2})$is then normalized by$\max_{s,a^{1},a^{2}}\{r^{1}_{s}(a^{1},a^{2})\}$so that$|r_{s}^{i}(a^{1},a^{2})|\leq R=1$for all$(i,s,a^{1},a^{2})$. For the state transition dynamics$p$, we construct two cases, Case 1 and Case 2 by randomly generating transition probabilities, so that they satisfy Assumptions 3 and 3, respectively. For both cases, we choose$\alpha_{c}=1/c^{0.9}$and$\beta_{c}=1/c$with$\rho_{\alpha}=0.9$,$\rho_{\beta}=1$, and$\rho=0.7$, and set$\tau_{c}$in accordance with (11) and (12), respectively. For Case 1, we choose$\epsilon=2\times 10^{-4}$and$\bar{\tau}=4.5\times 10^{4}$; for Case 2, we choose$\bar{\tau}=0.07$. Note that the different choices of$\bar{\tau}$are due to the different decreasing rates of$\tau_{c}$in (11) and (12), and are chosen to generate aesthetic plots. The simulation results are illustrated in Figure 2, which are generated after$20$ runs of our learning dynamics.

As shown in Figure 2 (a), for Case 1, the value function estimates successfully converge to the neighborhood of the Nash equilibrium values, where the size of the neighborhood is indeed controlled by (14a). For Case 2, it is shown in Figure 2 (b) that the value function estimates converge to the Nash equilibrium, as $\tau\to 0$. These observations have corroborated our theory established in §3. Moreover, it is observed that the variance of the iterates decreases as they converge to the (neighborhood of) Nash equilibrium, implying the almost-sure convergence guarantees we have established.

Besides the illustrative example, we have also tested our learning dynamics on larger scale games, and validated our theory for this case (see Figure 3). See §G for more details of the example.

Concluding Remarks

This paper has studied decentralized multi-agent reinforcement learning in zero-sum Markov games. We have developed a decentralized $Q$-learning dynamics with provable convergence guarantees to the (neighborhoods of the) Nash equilibrium value of the game. Unlike many existing MARL algorithms, our learning dynamics is both rational and convergent, and only based on the payoffs received and the local actions executed by each agent. It also requires neither asymmetric stepsizes/update rules or any coordination for the agents, nor even being aware of the existence of the opponent.

Acknowledgments and Disclosure of Funding

M. O. Sayin was with the Laboratory for Information and Decision Systems at MIT when this paper was submitted. K. Zhang and A. Ozdaglar were supported by DSTA grant 031017-00016. T. Başar was supported in part by ONR MURI Grant N00014-16-1-2710 and in part by AFOSR Grant FA9550-19-1-0353.

References

Appendix A Related Work

We here focus on the related works on MARL with provable convergence guarantees.

Stemming from the seminal work Littman , Markov games have been widely recognized as the benchmark setting for MARL. Littman focused on the zero-sum setting, and developed minimax $Q$-learning algorithm with asymptotic converge guarantees [Szepesvári and Littman, 1999]. However, this algorithm requires each agent to observe the opponent’s action. More importantly, each agent is fully aware of the zero-sum game being played, and solves a linear program to solve a matrix game at each iteration. Subsequently, Bowling and Veloso proposed that a preferable MARL algorithm should be both rational and convergent: a rational algorithm ensures that the iterates converge to the opponent’s best-response if the opponent converges to a stationary policy; while a convergent algorithm ensures convergence to some equilibrium if all the agents apply the learning dynamics. In this sense, minimax $Q$-learning is not rational. In contrast, our learning dynamics is both rational and convergent.

In the same vein as minimax $Q$-learning, with coordination among agents, asymptotic convergence has also been established for other $Q$-learning variants beyond the zero-sum setting [Littman, 2001, Hu and Wellman, 2003, Greenwald et al., 2003]. Borkar has also established the asymptotic convergence of an actor-critic algorithm to a weaker notion of generalized Nash equilibrium. Recently, there is an increasing interest in studying the non-asymptotic performance of MARL in Markov games [Pérolat et al., 2015, Wei et al., 2017, Sidford et al., 2019, Xie et al., 2020, Bai and Jin, 2020, Bai et al., 2020, Zhang et al., 2019, 2020, Shah et al., 2020, Liu et al., 2020, Zhao et al., 2021]. These algorithms are in essence centralized, in that they require either the control of both agents [Pérolat et al., 2015, Sidford et al., 2019, Xie et al., 2020, Bai and Jin, 2020, Bai et al., 2020, Zhang et al., 2019, 2020, Shah et al., 2020, Liu et al., 2020, Zhao et al., 2021], or at least the observation of the opponent’s actions [Wei et al., 2017, Xie et al., 2020].

Two closely related recent papers Leslie et al. and Sayin et al. have presented, respectively, continuous-time best response dynamics and discrete-time fictitious play dynamics that can converge to an equilibrium in zero-sum Markov games. They have established provable convergence by addressing the non-stationarity issue through a two-timescale framework. Though these two-timescale dynamics share a similar flavor with our approach, still, observing the opponent’s mixed strategy (in Leslie et al. ) or actions (in Sayin et al. ) is indispensable in them and plays an important role in their analysis. This is in stark contrast to our dynamics that require minimal information, i.e., being radically uncoupled [Foster and Young, 2006, Leslie and Collins, 2005].

A.2 Decentralized Multi-agent Learning

Decentralized learning is a desired property, and has been studied for matrix games (single-state Markov games) under the framework of no-regret learning [Cesa-Bianchi and Lugosi, 2006, Freund and Schapire, 1999, Mertikopoulos and Zhou, 2019]. Leslie and Collins also proposed individual soft $Q$-learning dynamics for zero-sum matrix games. For general Markov games, however, it is known that blindly applying independent/decentralized $Q$-learning can easily diverge, due to the non-stationarity of the environment [Tan, 1993, Boutilier, 1996, Matignon et al., 2012]. Despite this, the decentralized paradigm has still attracted continuing research interest [Arslan and Yuksel, 2017, Pérolat et al., 2018, Daskalakis et al., 2020, Tian et al., 2020, Wei et al., 2021], since it is much more scalable and natural for agents to implement. Notably, these works are not as decentralized and as general as our learning dynamics.

Specifically, the algorithm in Arslan and Yuksel requires the agents to coordinately explore every multiple iterations (the exploration phase), without changing their policies within each exploration phase, in order to create a stationary environment for each agent. Similar to our work, Pérolat et al. also proposed decentralized and two-timescale algorithms, which, however, is an actor-critic algorithm where the value functions are estimated at a faster timescale (critic step), and the policy is improved at a slower one (actor step). More importantly, the algorithm only applies to Markov games with a “multistage” structure, in which each state can only be visited once. Establishing convergence in general zero-sum Markov games is posted as an open problem in Pérolat et al. . In Daskalakis et al. , the agents have to coordinate to use two-timescale stepsizes in the updates. In contrast, our learning dynamics does not require any coordination among agents, and each agent plays a symmetric role in learning, referred to as strongly independent in Daskalakis et al. . In fact, developing provable guarantees for strongly independent algorithms is considered as an important open question in Daskalakis et al. .

Two recent works Tian et al. , Wei et al. studied the decentralized setting that is closest to ours. Tian et al. focused on the exploration aspect for finite-horizon settings, and considered a weak notion of regret. It is unclear if the learning dynamics converge to any equilibrium when both agents apply itNote that the same update rule with different stepsize and bonus choices and a certified policy technique, however, can return a non-Markovian approximate Nash equilibrium policy pair in the self-play setting, by storing the whole history of the learning process; see Bai et al. for more details.. Contemporaneously, Wei et al. presented an interesting optimistic variant of the gradient descent-ascent method, with a strong guarantee of last-iterate convergence rates, which shares all the desired properties as our learning dynamics. The algorithm is delicately designed and different from the common value/policy-based RL update rules, e.g., $Q$-learning, as in our work. Moreover, to characterize finite-time convergence, in the model-free setting, the agents need to coordinate to interact multiple steps at each iteration of the algorithm, while our learning dynamics is coordination-free with natural update rules. These two works can thus be viewed as orthogonal to ours.

After submitting the first draft of our paper, we were reminded of an independent and concurrent work of Guo et al. , which also studied a decentralized learning setting in zero-sum Markov games. We summarize the substantial differences between the two works as follows.

Motivation: In Guo et al. , being “decentralized” is defined as “each player not knowing the opponent’s action”, to “protect the privacy”, and the goal is to “compute” the Nash equilibrium of the game; in contrast, in our work, in addition to “being oblivious to the opponent’s action”, we also allow no “coordination” among agents, so that each agent can simply run the learning dynamics “individually”, without even being aware of the existence of the opponent. The agents in our setting are considered as self-interested decision-makers, who seek to adapt to the opponent’s play by inferring it from the rewards received without seeing the opponent’s actions. The Nash equilibrium, on the other hand, is the result that “emerge” naturally when both agents follow this self-interested learning dynamics (and we have proved this). Finally, as our learning dynamics are oblivious to the opponent and are adaptive to the opponent, we expect it to converge beyond the zero-sum setting (e.g., the identical-interest setting), which is one of our ongoing research directions. In contrast, the algorithm in Guo et al. is specifically developed for the zero-sum setting. These motivations differ fundamentally from Guo et al. (and thus creates very different technical challenges, as detailed below).

Learning dynamics (Algorithms): The algorithm in Guo et al. , is actor-critic, which is a type of policy-based RL method; the learning dynamics in our work is Q-learning based, which belongs to value-based RL methods. More importantly, the update-rule in Guo et al. , is of “double-loop” form, in the sense that it fixes the iterate of Player 1 while updating Player 2’s policy, so that a “best-response” policy of Player 2 can be obtained. This is an asymmetric update-rule, and requires coordination between agents. In contrast, our learning dynamics are “symmetric”, without such a double-loop coordination, where each agent simply runs her own $Q$-learning dynamics.

Assumptions and results: Guo et al. considers a function approximation setting, and assumes that: 1) the “double-loop” update can be implemented by the agents in the decentralized setting; 2) the concentration (or “Concentrability”) coefficient is finite (Assumption 4.1), for “an arbitrary sequence of policies”; 3) samples are drawn i.i.d. from the stationary state-action distribution; 4) projection of the iterates onto some ball with radius $R$, to ensure the iterates’ stability; and 5) zero approximation error of the Bellman operator (Assumption 4.2). Under these assumptions, non-asymptotic convergence results were established. In contrast, our work considers a fundamental tabular setting, and without making these assumptions (1-4), with instead asymptotic convergence guarantees. With these significantly different assumptions, it is not clear if one paper’s result implies the other’s.

Analysis techniques (Technical novelty): The analyses, as well as the technical novelties in both papers are not comparable. The analysis technique in Guo et al. , is a mirror-descent type of analysis, based on the convergence analysis of policy gradient (and actor-critic) algorithms in single-agent RL. The techniques in our paper, however, are based on stochastic approximation theory, a classic technique in showing the convergence of $Q$-learning. The challenges we need to address (our technical novelties) mainly lie in constructing a Lyapunov function and stability of the iterates, within this non-standard two-timescale stochastic approximation setting, with asynchronous updates. Such challenges would not be encountered in the analysis of Guo et al. , making the technical novelties of the two papers fundamentally different.

Appendix B Examples

In this section, we provide three sets of parameter examples and highlight whether they satisfy Assumptions 3 and 3 or Assumptions 3 and 3. Recall that Assumptions 3 and 3 do not impose conditions on the step sizes nor the temperature parameter.

Example 1. Set the step sizes as $\alpha_{c}=c^{-\rho_{\alpha}}$, $\beta_{c}=c^{-\rho_{\beta}}$, where $1/2<\rho_{\alpha}<\rho_{\beta}\leq 1$ and the temperature parameter as

We claim that $Mc\geq\lambda^{-1/\rho_{\beta}}c^{\rho_{\alpha}/\rho_{\beta}}$ for all $c\geq C(\lambda^{-1})$ because $\lambda^{-1/\rho_{\beta}}c^{\rho_{\alpha}/\rho_{\beta}}\leq Mc$ yields

On the other hand, we have $C(\lambda^{-1})=M_{o}\lambda^{-m}\geq M_{o}\lambda^{-1/(\rho_{\beta}-\rho_{\alpha})}$ for all $\lambda\in(0,1)$ since $m\geq 1/(\rho_{\beta}-\rho_{\alpha})$ by its definition.

Assumption 3 holds since $\{\tau_{c}\}$ monotonically decreases to $\epsilon$ as $c\rightarrow\infty$, and

which goes to zero as $c\rightarrow\infty$ since $\rho_{\alpha}<1$, and $\sum_{c>0}c^{-2\rho_{\alpha}}<\infty$ since $2\rho_{\alpha}>1$. $\square$

Example 2. Set the step sizes as $\alpha_{c}=c^{-\rho_{\alpha}}$, $\beta_{c}=c^{-\rho_{\beta}}$, where $1/2<\rho_{\alpha}<\rho_{\beta}\leq 1$ and the temperature parameter as

for some $\rho\in(0,2-1/\rho_{\alpha})$ and $\bar{\tau}>0$.

In the following, we show that Example B satisfies Assumption 3 and 3. Example B shares the same step sizes with Example B. Therefore, Assumption 3 holds as shown above for Example B. On the other hand, Assumption 3 also holds since $\{\tau_{c}^{\prime}\}$ monotonically decreases to as $c\rightarrow\infty$, and

where the right-hand side goes to zero as $c\rightarrow\infty$, and

which implies that $\alpha_{c}^{\rho}\exp(4D/\tau_{c}^{\prime})\leq C^{\prime}$ for all $c>0$ when $C^{\prime}=\exp(4D/\bar{\tau})$. $\square$

Example 3. Set the step sizes as $\alpha_{c}=c^{-\rho_{\alpha}}$, $\beta_{c}=c^{-\rho_{\beta}}$, where $1/2<\rho_{\alpha}<\rho_{\beta}\leq 1$ and the temperature parameter as $\tau_{c}=\max\{\epsilon,\tau_{c}^{\prime}\}$, where $\tau_{c}^{\prime}$ is as described in (23).

In the following, we show that Example B satisfies Assumption 3 and 3. Example B shares the same step sizes with Example B. Therefore, Assumption 3 holds as shown above for Example B. On the other hand, Assumption 3 also holds since $\{\tau_{c}\}$ monotonically decreases to $\epsilon$ as $c\rightarrow\infty$ (which follows since $\{\tau_{c}^{\prime}\}$ monotonically decreases to as $c\rightarrow\infty$), and we again have the inequality (24) and $\sum_{c>0}c^{-2\rho_{\alpha}}<\infty$ since $2\rho_{\alpha}>1$. $\square$

Appendix C Proofs of Propositions 3-3

Proposition 3. Since $\bar{\alpha}_{k}^{i}\in(0,1]$ for all $k\geq 0$, $\beta_{c}\in(0,1)$ for all $c>0$, $\|\hat{q}_{s,0}^{i}\|_{\infty}\leq D$ and $|\hat{v}_{s,0}^{i}|\leq D$ for all $(i,s)$, the iterates are bounded, e.g., $\|\hat{q}_{s,k}^{i}\|_{\infty}\leq D$ and $|\hat{v}_{s,k}^{i}|\leq D$ for all $(i,s)$ and $k\geq 0$.

Proof: The proof follows from the fact that the initial iterates are picked within the compact set and they continue to remain inside it since they are always updated to a convex combination of two points inside. $\square$

for all $\#s_{k}\geq C_{s_{k}}$ since $\alpha_{\#s_{k}}/\overline{\pi}_{k}^{i}[a_{k}^{i}]\leq|A_{s_{k}}^{i}|\alpha_{\#s_{k}}\exp\left(2D/\tau_{\#s_{k}}\right)\leq 1$ by (7).

Proof: If Assumption 3 holds, then $\alpha_{c}\exp(2D/\tau_{c})\leq\alpha_{c}\exp(2D/\epsilon)$. Since $\alpha_{c}\rightarrow 0$ as $c\rightarrow\infty$ by Assumption 3, there exists such $C_{s}$.

Since $1-\rho/2>0$ and $\alpha_{c}\rightarrow 0$ as $c\rightarrow\infty$, there exists such $C_{s}$. $\square$

Proposition 3. Suppose that either Assumption 3 or Assumption 3 holds. Then, at any stage $k$, there is a fixed positive probability, e.g., $\underline{p}>0$, that the game visits any state $s$ at least once within $n$-stages independent of how players play. Therefore, $\#s\rightarrow\infty$ as $k\rightarrow\infty$ with probability $1$.

Proof: By Borel-Cantelli Lemma, if we have

Next, we can resort to the following inequality [Flum and Grohe, 2006, Lemma 16.19]

where $H_{2}(p):=-p\log(p)-(1-p)\log(1-p)$. Therefore, for $k\geq 2n\lambda$, (32) and (33) yield that

and the right-hand side is convergent since $\xi^{1/n}<1$, which completes the proof. $\square$

Appendix D Preliminary Information on Stochastic Approximation Theory

Here, we present two preliminary results. The former uses a continuous-time approximation to analyze a discrete-time update [Benaim, 1999]. The latter is about characterizing the convergence properties of an asynchronous discrete-time update by exploiting certain bounds on their evolution [Sayin et al., 2020].

The following theorem (follows from [Benaim, 1999, Proposition 4.1 and Corollary 6.6]) characterizes the conditions sufficient to characterize the convergence properties of a discrete-time update:

through its limiting ordinary differential equation (o.d.e.):

The step sizes $\{\lambda_{k}\in\}_{k=0}^{\infty}$ decrease at a suitable rate:

Then the limit set of (36) is contained in the set

D.2 Asynchronous Stochastic Approximation

Theorem 3. Suppose that the evolution of $\{x_{k}\}_{k\geq 0}$ always satisfies the following upper and lower bounds:

where $\gamma\in(0,1)$ is a discount factor, $\|x_{k}\|_{\infty}\leq D$ for all $k\geq 0$ for a fixed $D$, and the specific step sizes satisfy the usual conditions:

for some $c\geq 0$, with probability $1$. Then, we have

Appendix E Convergence Analysis: Proof of Theorem 3

The proof is built on the following observation: The update of the value function estimate, (9), can be written as

where the tracking error $\epsilon_{s,k}^{i}$ is defined by

where $\hat{Q}_{s,k}^{i}\in[-D,D]^{|A_{s}^{i}|\times|A_{s}^{-i}|}$ corresponding to the global $Q$-function is defined by

Denote the unique fixed point of the contraction $T^{i}$ by $\{v_{s,*}^{i}\}_{s\in S}$. Then, we have $v_{s,*}^{i}=T^{i}(\{v_{s^{\prime},*}^{i}\}_{s^{\prime}\in S})[s]$. Therefore, the update (44) can be written as

Based on Proposition 3, Theorem D.2 and (44) yield that the asymptotic behavior of the value function estimates can be characterized as follows:

for all $(i,s)\in\{1,2\}\times S$. The rest of the proof is about characterizing the asymptotic behavior of the tracking error (45) and showing that

It is instructive to discuss why the existing results cannot directly address this tracking error’s asymptotic behavior. For example, there exist several well-established results on convergence properties of learning dynamics in strategic-form games with repeated play for both zero-sum and potential games, e.g., see Fudenberg and Levine . The challenge raises since $\hat{Q}_{s,k}^{i}$ is not time-invariant and it depends on both players’ strategies. On the other hand, the existing results to characterize the convergence properties of the classical (single-agent) $Q$-learning is helpful only to obtain (51) and do not address the tracking error (45). Note that if the players are coordinated to play the equilibrium behavior, e.g., as in Shapley’s value iteration [Shapley, 1953] or Minimax-Q [Littman, 1994], then the tracking error would be zero by the nature of the updates. However, this would imply that the players are coordinated to play the equilibrium since

Players need to know the zero-sum structure of the game,

Players always play the conservative strategy against the worst-case strategy of the opponent and do not attempt to take the best reaction when the opponent is not playing the equilibrium strategy,

Players need to observe the opponent’s actions to be able to compute the global $Q$-function associated with the joint actions.

A two-timescale learning dynamics can address the dependence of the $Q$-function estimate on the strategies and correspondingly address the tracking error. However, there are several challenges especially for radically uncoupled schemes, where players do not observe the opponent’s actions:

The local $Q$-function estimates for different state and local action pairs can get updated at different frequencies, which poses a challenge for the two-timescale framework to decouple the dynamics at fast and slow timescales. Particularly, the normalization of the step size in the update of the local $Q$-function estimate can ensure that the estimate for each local action gets updated at the same rate in the expectation. However, this is not sufficient since estimates for some local actions can lag behind even the iterates evolving on the slow timescale.

The $Q$-function estimates may not necessarily sum to zero in general when the players keep track of it independently, i.e., if there is no central coordinator providing it to them. This is important because uncoupled learning dynamics cannot converge to an equilibrium in every class of games, as shown in Hart and Mas-Colell .

The players can keep track of only local $Q$-function since they cannot observe the opponent’s action. However, there may not even exist an opponent (mixed) strategy that can lead to the local $Q$-function estimate, i.e., they may not be belief-based, whereas this is not the case if players can observe the opponent’s actions to form a belief on the opponent’s strategy.

In the following, we follow a three-step approach to address these challenges:

Decoupling dynamics at the fast timescale by addressing Challenge $i)$.

Zooming into the local dynamics (i.e., learning dynamics specific to a single state) at the fast timescale to address Challenges $ii)$ and $iii)$ via a novel Lyapunov function.

Zooming out to the global dynamics (i.e., learning dynamcis across every state) at the slow timescale to characterize the asymptotic behavior of the tracking error (45).

In the following, we delve into the details of these steps.

Distinct to the radically uncoupled settings, the players can update only the local $Q$-function estimate’s entry specific to the current local action. Although this is an asynchronous update, the normalization makes the evolution of every entry synchronous in the expectation [Leslie and Collins, 2005]. To show this, we introduce the stochastic approximation error:

for all $a^{1}\in A_{s}^{1}$, where $\delta_{k}:=\{\hat{q}_{s,k}^{i},\hat{v}_{s,k}^{i}\}_{(i,s)\in\{1,2\}\times S}$ includes the iterates at stage $k$, and $\omega_{s_{k},k}^{2}[a^{2}]$ for $a^{2}\in A_{s}^{2}$ is defined accordingly. The expectation is explicitly given by

where the auxiliary global $Q$-function estimate is as described in (47). Since the denominator disappears in (54), the stochastic approximation error is also given by

Our goal is to characterize the limit set of this discrete-time update for every state. Like Leslie and Collins , we can resort to stochastic approximation methods to transform the problem into a tractable continuous-time flow. Distinct to Markov games, we cannot characterize the convergence properties of (56) for each state separately. By (47), the update (56) yields that the current state’s local Q-function estimate is coupled with any other state’s value function estimate. For example, fix an arbitrary state $s$ and take a closer look at how the iterates change in-between two consecutive visits to $s$, denoted by $k$ and $k^{\dagger}$. Since the game does not visit state $s$ until $k^{\dagger}$, we have $\hat{q}_{s,k^{\dagger}}^{i}=\hat{q}_{s,k+1}^{i}$ and $\hat{v}_{s,k^{\dagger}}^{i}=\hat{v}_{s,k+1}^{i}$ for $i=1,2$, and $\#_{k^{\dagger}}s=\#_{k}s+1$. In contrast, other states’ value function estimates can change depending on the visits to other states at stages within the interval $(k,k^{\dagger})$. Correspondingly, the iterates and the temperature parameter at $k^{\dagger}$ can be written in terms of the iterates at $k$ in the following compact form:

for all $k\geq\kappa_{s}$, where we define the error terms by

Based on Proposition 3, we can focus on asymptotic convergence properties of (57). Therefore, we are interested in when the convergence properties of (57) can be characterized through the following ordinary differential equation (in which the dynamics for $s$ is decoupled from the dynamics for any other state)

for some $\bar{Q}_{s}^{i}\in[-D,D]^{|A_{s}^{i}|\times|A_{s}^{-i}|}$ for $i\in\{1,2\}$ and $\bar{\tau}>0$. To this end, we can resort to Theorem D.1 by showing that the limiting ordinary differential equation of (59) is given by

where $Q_{s}^{i}[a^{i},a^{-i}](t)=r_{s}^{i}(a^{1},a^{2})+\gamma\sum_{s^{\prime}\in S}p(s^{\prime}|s,a^{1},a^{2})v_{s^{\prime}}^{i}(t)$ for $i=1,2$. Conditions $i$ (and $ii$) in Theorem D.1 are satisfied by Assumption 3 (and Proposition 3). Furthermore, the corresponding vector field is Lipschitz continous since it is continously differentiable by (7) and defined over a compact set by Proposition 3. The following two lemmas show that the conditions $iv$-$v$ listed in Theorem D.1 are also satisfied. The proofs of these technical lemmas are provided in Subsection §E.4.

Lemma 1. Suppose Assumption 3 and either Assumption 3 or 3 hold. Then, the stochastic approximation terms $(\omega_{s,k}^{1},\omega_{s,k}^{2})$ satisfy (39) for all $T>0$, $s\in S$, and $i=1,2$.

Assumption 3 ensures that the denominator in the update of the local $Q$-function estimate is bounded from below by some non-zero term. On the other hand, Assumption 3 restrains the rate at which the denominator gets close to zero while letting $\lim_{c\rightarrow\infty}\tau_{c}=0$.

Lemma 2. Suppose Assumption 3 and either Assumption 3 or 3 hold. Then, the error terms in (57), $\{\varepsilon^{i}_{s,k^{\dagger}}\}_{(i,s)\in\{1,2\}\times S}$ and $(\tau_{\#s+1}-\tau_{\#s})/\alpha_{\#s}$, are asymptotically negligible with probability $1$.

In the following step, we will zoom into (59) and formulate a Lyapunov function to characterize the limit set of not only (59) but also the original discrete-time update (57).Lyapunov function plays an important role to deduce convergence properties of the discrete-time update via the limiting o.d.e. because the convergence of the limiting o.d.e. does not necessarily imply the convergence of the discrete-time update in general (e.g., see Benaim and Borkar ).

E.2 Zooming into local dynamics at the fast timescale

with arbitrary initialization of $q^{i}(0)$ such that $\|q^{i}(0)\|_{\infty}\leq D$, arbitrary matrices $Q^{i}$ such that $\|Q^{i}\|_{\max}\leq D$, and $\tau>0$. The flow (61) resembles to the local $Q$-functions’ evolution in the perturbed best response dynamics:

where $\pi^{i}:[0,\infty)\rightarrow\Delta(A^{i})$. Indeed, they lead to the same trajectory for $(q^{1},q^{2})$ if we have $q^{1}(t)=Q^{1}\pi^{2}(t)$ and $q^{2}(t)=Q^{2}\pi^{1}(t)$. However, there may not always exist a strategy, e.g., $\pi^{2}\in\Delta(A^{2})$, such that $q^{1}(t)=Q^{1}\pi^{2}$. If there exists such a strategy, we say $q^{1}(t)$ is belief-based, and vice versa.

We will examine the flow (61) at a higher-dimensional space to mitigate this issue through

We present the following continous and non-negative function as a candidate Lyapunov function for (63):

where we define $[g(t)]_{+}:=\max\{g(t),0\}$ for a given function $g(\cdot)$, the auxiliary parameter $\lambda\in(1,1/\gamma)$ is arbitrary, and we define

Note that $\zeta\geq 0$ depends on $Q^{1},Q^{2}$, and $\tau$ implicitly, and it is small when the auxiliary game is close to zero-sum and the temperature parameter is close to zero. The arbitrary parameter $\lambda>1$ plays an important role in ensuring that the set $\{(q^{1},q^{2},\pi^{1},\pi^{2}):V(q^{1},q^{2},\pi^{1},\pi^{2})=0\}$ is a global attractor for the flow (63). Furthermore, the condition $\lambda\gamma\in(0,1)$ will play an important role when we zoom out to the global dynamics in Subsection §E.3.

Before validating $V(\cdot)$ as a Lyapunov function, let us highlight its differences from other Lyapunov functions used for the best response dynamics with or without perturbation. For example, Hofbauer and Hopkins provided a Lyapunov function for the perturbed best response dynamics in zero-sum games and showed that such dynamics converge to a Nash distribution for any smooth function and any positive temperature parameter. However, we must consider arbitrary $Q^{1}$ and $Q^{2}$, which implies that $Q^{1}+(Q^{2})^{T}$ may not be a zero matrix in general. In other words, the underlying game is not necessarily zero-sum. Therefore, we need to consider this deviation in our candidate function.

On the other hand, Sayin et al. provided a Lyapunov function for the best response dynamics in games beyond zero-sum and showed that such dynamics converge to a bounded set with diameter depending on its deviation from a zero-sum game. Therefore, our candidate (64) has a similar flavor with the one in Sayin et al. while addressing also the perturbation and the issue induced by not being belief-based. For example, $V(q_{*}^{1},q_{*}^{2},\pi_{*}^{1},\pi_{*}^{2})=0$ implies that

The following lemma shows that the non-negative $V(\cdot)$ is a Lyapunov function for the flow (63) and its proof is provided in Subsection §E.4.

Lemma 3. Consider any trajecttory of (63) and let $x(t):=(q^{1}(t),q^{2}(t),\pi^{1}(t),\pi^{2}(t))$. Then the candidate function $V(\cdot)$, as described in (64), satisfies

$V(x(t^{\prime}))<V(x(t))$ for all $t^{\prime}>t$ if $V(x(t))>0$,

$V(x(t^{\prime}))=0$ for all $t^{\prime}>t$ if $V(x(t))=0$.

Based on Lemma E.2, we can characterize the convergence properties of the discrete-time update (57). There is a sequence of beliefs $\{\hat{\pi}_{s,k}^{j}\in\Delta(A_{s}^{j})\}_{k\geq 0}$ for the sequence $\{\hat{q}_{s,k}^{i}\}_{k\geq 0}$ and it evolves according to

with some arbitrary initialization, and satisfies

where $j\neq i$. Denote $\bar{Q}_{s,k}:=\bar{Q}_{s,k}^{1}+(\bar{Q}_{s,k}^{2})^{T}$. Then, Lemma E.2 yields that

which implies that there exists $\{\overline{e}_{s,k}\geq 0\}_{k\geq 0}$ and $\lim_{k\rightarrow\infty}\overline{e}_{s,k}=0$ such that

In the following, we characterize the convergence properties of the value function estimates based on (71) and (72), respectively, showing that the local $Q$-function estimates are asymptotically belief-based and characterizing an upper bound on the sum of the (perturbed) values.

E.3 Zooming out to global dynamics at the slow timescale

Next, we focus on the evolution of the value function estimates. To this end, we first consider how the sum of the players’ value function estimates specific to state $s$ (denoted by $\bar{v}_{s,k}:=\hat{v}_{s,k}^{1}+\hat{v}_{s,k}^{2}$) evolves:

We can view (73) as the sum $\bar{v}_{s,k}$ moving toward (or tracking) the target $\sum_{i=1,2}\overline{\pi}_{k}^{i}\cdot\hat{q}_{s,k}^{i}$. The target is bounded from above by

by (72). We can also bound the target from below by using the smooth best response definition and (71) as follows:

and it is asymptotically negligible by (71). Since $\hat{\pi}_{s,k}^{i}\in\Delta(A_{s}^{i})$, we obtain

where the last inequality follows since $\lambda>1$ and $\nu_{s}^{i}:\Delta(A_{s}^{i})\rightarrow[0,\log(|A_{s}^{i}|)]$.

Based on the fact that $r_{s}^{1}(a^{1},a^{2})+r_{s}^{2}(a^{1},a^{2})=0$ for all $(a^{1},a^{2})$, we can formulate a bound on $\|\bar{Q}_{s,k}\|_{\max}$ from above in terms of $\{\bar{v}_{s^{\prime},k}\}_{s^{\prime}\in S}$ as follows:

Combining (74), (78), and (79), we obtain

for all $s\in S$ and $k\geq 0$, with some asymptotically negligible error terms $\underline{e}_{s,k}$ and $\overline{e}_{s,k}$. The condition $\lambda\gamma\in(0,1)$ yields that the target in (73) shrinks in absolute value as $k\rightarrow\infty$. Based on (73) and Theorem D.2, we obtain

where $\xi:=\max_{s\in S}\{\log(|A_{s}^{1}||A_{s}^{2}|)\}$ since $\#s\rightarrow\infty$ as $k\rightarrow\infty$ with probability $1$ by Proposition 3. Therefore, the auxiliary games get close to (or become) zero-sum asymptotically like the two-timescale fictitious play in Sayin et al. but with a radically uncoupled scheme.

The next and last step is about characterizing the asymptotic behavior of the tracking error (45):

Particularly, $(a)$ follows from triangle inequality; $(b)$ follows since

by definition of best response and smooth best response and since $\hat{q}_{s,k}^{i}$ is asymptotically belief-based and $\max\{\cdot\}$ is a continuous operator; $(c)$ follows from the fact that

$(d)$ follows from the triangle inequality; $(e)$ follows since we have

where (85) corresponds to the difference between the maximum values player $2$ would get in the scenarios in which it has the payoff matrices $\hat{Q}_{s,k}^{2}$ versus $(-\hat{Q}_{s,k}^{1})$ in an auxiliary strategic-form game, given that the opponent’s play is fixed, and this difference is bounded from above by $\|\hat{Q}_{s,k}^{2}-(-\hat{Q}_{s,k}^{1})\|_{\max}=\|\bar{Q}_{s,k}\|_{\max}$; $(f)$ follows from (79); $(g)$ follows since $\hat{q}_{s,k}^{i}$ is asymptotically belief-based; $(h)$ follows from (83); $(i)$ follows since (E.3) yields that

and finally $(j)$ follows from (81). This completes the first part of the result on the asymptotic behavior of $\{\hat{v}_{s,k}^{i}\}_{k\geq 0}$.

Other quantities can be defined similarly.

where (88) is due to one-step Bellman equation and the zero-sum structure of the underlying game, (89) follows by inserting $\max_{\mu^{i}}\,(\mu^{i})^{T}Q_{\pi_{*}}^{i}(s,\cdot)\hat{\pi}_{s,k}^{-i}$, (90) follows by the fact that

where the last inequality follows from (E.3) and its counterpart by switching the role of $-i$ and $i$ there in. Combined with the definition of $\epsilon$-Nash equilibrium with (E.3)-(96), we complete the proof.

E.4 Proofs of Technical Lemmas E.1-E.2

Lemma E.1. Suppose Assumption 3 and either Assumption 3 or 3 hold. Then, the stochastic approximation terms $(\omega_{s,k}^{1},\omega_{s,k}^{2})$ satisfy (39) for all $T>0$, $s\in S$, and $i=1,2$.

Proof: By (53), the stochastic approximation term $\omega_{s,k}^{1}[a^{1}]$ (and $\omega_{s,k}^{2}$) can be written as

which is a square-integrable Martingale difference sequence since the iterates remain bounded by Proposition 3. Then, the proof follows from the proof of [Benaim, 1999, Proposition 4.2] by substituting the step size $\alpha_{\#s}$ with $\frac{\alpha_{\#s}}{\overline{\pi}_{k}^{i}[a^{i}]}$ and showing that

If Assumption 3 holds, then the analytical form of $\overline{\pi}_{k}^{i}[a^{i}]$, as described in (7), yields that $\overline{\pi}_{k}^{i}[a^{i}]\geq\frac{1}{|A_{s}^{i}|}\exp(-2D/\epsilon)$. Correspondingly, the sum in (100) is bounded from above by

The right-hand side is a convergent sum by Assumption 3.

On the other hand, if Assumption 3 holds, then we no longer have a fixed lower bound on $\overline{\pi}_{k}^{i}[a^{i}]$. Instead, we have $\overline{\pi}_{k}^{i}[a^{i}]\geq\frac{1}{|A_{s}^{i}|}\exp\{-2D/\tau_{\#s}\}$. Correspondingly, the sum in (100) is now bounded from above by

By Assumption 3, we have $\exp(4D/\tau_{c})<C^{\prime}\alpha_{c}^{-\rho}$ for all $c\geq C$. Therefore, we obtain

The right-hand side is a convergent sum by Assumption 3. This completes the proof. $\square$

Lemma E.1. Suppose Assumption 3 and either Assumption 3 or 3 hold. Then, the error terms in (57), $\{\varepsilon^{i}_{s,k^{\dagger}}\}_{(i,s)\in\{1,2\}\times S}$ and $(\tau_{\#s+1}-\tau_{\#s})/\alpha_{\#s}$, are asymptotically negligible with probability $1$.

Proof: The error term $(\tau_{\#s+1}-\tau_{\#s})/\alpha_{\#s}$ is asymptotically negligible with probability $1$ either by Assumption 3 or Assumption 3. On the other hand, the definition of $\varepsilon_{s^{\prime},k^{\dagger}}^{i}$, as described in (58), and the evolution of $\hat{v}_{s^{\prime},k}^{i}$ yield that

Since $\{\beta_{c}\}_{c>0}$ is non-increasing by Assumption 3 and the iterates are bounded by $D$ by Proposition 3, the error term $\varepsilon_{s^{\prime},k^{\dagger}}^{i}$ is bounded from above by

for any $\lambda>0$, then $|\varepsilon_{s^{\prime},k^{\dagger}}^{i}|\rightarrow 0$ as $k\rightarrow\infty$ with probability $1$. To this end, we will focus on the argument of the summation (106). Since $\#_{k}s\leq k$ and $\{\alpha_{c}\}_{c>0}$ is a non-increasing sequence by Assumption 3, we have

Since the argument of the summation on the right-hand side is non-negative, convergence of the following:

where the order of summations is interchanged would imply the convergence of (110). Correspondingly, we will show that (111) is convergent instead.

Partition the time axis into $n$-stage intervals and define $\bar{\#}_{k}^{n}s^{\prime}$ as a counting process that increases by $1$ at the end of an $n$-stage interval if $s^{\prime}$ is visited at least once within the last $n$-stage. More precisely, $\bar{\#}_{k}^{n}s^{\prime}$ is, recursively, given by

By its definition, we have $\bar{\#}_{k}^{n}s^{\prime}\leq\#_{k}s^{\prime}$, and therefore, we obtain

Either Assumption 3 or 3 yield that the probability that state $s^{\prime}$ is visited within an $n$-stage interval is bounded from below, e.g., by some $\underline{p}>0$, for every sequence of actions. Correspondingly, Correspondingly, the probability that $s^{\prime}$ is not visited within the $n$-stage interval is bounded from above by $1-\underline{p}$. Therefore, we can bound the right-hand side of (115) from above by

Assumption 3 yields that for any $M\in(0,1)$, there exists a non-decreasing polynomial function $C_{M}(\cdot)$ such that

For $k\geq n$, (117) can also be written as

Since $M\in(0,1)$ is arbitrary, there exists $M$ such that $2nM<1$, i.e, $M\in(0,1/2n)$. Therefore, we have

for all $k\geq\max\{C_{M}(\kappa/\lambda),n\}$, since $(1-\underline{p})\in[0,1)$. Furthermore, we can set $M\in(0,1/2n)$ such that $2nM<1/2$. Then, we can resort to the following inequality [Flum and Grohe, 2006, Lemma 16.19]

where $H_{2}(p):=-p\log(p)-(1-p)\log(1-p)$. Therefore, for all $k\geq\max\{C_{M}(\kappa/\lambda),n\}$, we obtain

since $(1-\underline{p})\in[0,1)$ and $H_{2}(p)$ is an increasing function for $p\in(0,1/2)$.

We define $\eta_{M}:=(1-\underline{p})^{1-2nM}2^{H_{2}(2nM)}$. Note that for $M=0$, we have $\eta_{0}=(1-\underline{p})2^{H_{2}(0)}=(1-\underline{p})\in[0,1)$. By the continuity of $\eta_{M}$ in $M$, there exists $M\in(0,1/4n)$ such that $\eta_{M}\in(0,1)$. By (115), (116), (119), and (123), we obtain