Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence^††thanks: An earlier version of this work containing preliminary results was presented at the 2023 IEEE Conference on Decision and Control.

The remainder of the paper is organized as follows. In Section 2, we present the model of stochastic games. Related work is surveyed in Section 3. In Section 4, we present the unsynchronized decentralized Q-learning algorithm and we state our main result, Theorem 4.1, on high probability guarantees for equilibrium in weakly acyclic stochastic games. The proof of Theorem 4.1 is outlined in Section 5. The details of the proof of Theorem 4.1 are presented in Section 6. The results of a simulation study are presented in Section 7, and the final section concludes. A glossary of notation is provided in Appendix A.

We now introduce weakly acyclic games, an important subclass of games that will be the main focus of this paper.

The multi-state formulation above was stated in [1], though weakly acyclic games had previously been studied in stateless games [38]. An important special case is that of stochastic teams, where $c^{i}=c^{j}$ and $\gamma^{i}=\gamma^{j}$ for any players $i,j\in\mathcal{N}$, and the interests of all agents are perfectly aligned. Markov potential games with finitely many states constitute another special case of weakly acyclic games [28, 16, 39].

In the stochastic game $\mathcal{G}$, when player $i$’s counterplayers use a stationary policy $\bm{\pi}^{-i}\in\bm{\Pi}^{-i}_{S}$, player $i$ faces an environment that is equivalent to a single-agent MDP. The MDP in question depends on the policy $\bm{\pi}^{-i}$ as well as the game $\mathcal{G}$, and (stationary Markov) optimal policies for this MDP are equivalent to 0-best-responses to $\bm{\pi}^{-i}$ in the game $\mathcal{G}$.

Player $i$’s best-responses to a policy $\bm{\pi}^{-i}\in\bm{\Pi}^{-i}_{S}$ can be characterized using an appropriately defined Q-function, $Q^{*i}_{\bm{\pi}^{-i}}:\mathbb{X}\times\mathbb{A}^{i}\to\mathbb{R}$.²²2We use the terms Q-function and (state-) action-value function interchangeably. The function $Q^{*i}_{\bm{\pi}^{-i}}$ can be defined by a fixed point equation of a Bellman operator, but here we give an equivalent definition in terms of the optimal policy of the corresponding MDP:

for all $(x,a^{i})\in\mathbb{X}\times\mathbb{A}^{i},$ where $\bm{\pi}^{*}=(\pi^{*i},\bm{\pi}^{-i})$ and $\pi^{*i}\in{\rm BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Pi^{i}_{SD}.$

The set $\widehat{{\rm BR}}^{i}_{\epsilon}(Q^{i})$ is the set of stationary deterministic policies that are $\epsilon$-greedy with respect to $Q^{i}$. The function $Q^{i}$ plays the role of an action-value function, and for $Q^{i}=Q^{*i}_{\bm{\pi}^{-i}}$, we have $\widehat{{\rm BR}}^{i}_{0}(Q^{*i}_{\bm{\pi}^{-i}})={\rm BR}^{i}_{0}(\bm{\pi}^{-i})\cap\Pi^{i}_{SD}$.

When the remaining players follow a stationary policy, player $i$ can use Q-learning to estimate its action-values, which can then be used to estimate a 0-best-response policy. In the following sections, we observe that the situation is more complicated when the remaining players employ learning algorithms that adapt to feedback and revise their action selection probabilities over time.

In decentralized MARL settings, where agents have minimal information about strategic interactions with other players, one natural and commonly studied approach to algorithm design is to treat each agent’s game environment as a separate single-agent RL environment. Indeed, when the remaining players use a stationary policy $\bm{\pi}^{-i}\in\bm{\Pi}^{-i}_{S}$, then player $i$ truly does face a strategic environment equivalent to an MDP, and can approach its learning task with single-agent Q-learning.

Picking some $\widehat{Q}^{i}_{0}\in\mathbb{R}^{\mathbb{X}\times\mathbb{A}^{i}}$ to serve as an initial estimate of its optimal Q-function, player $i$ would iteratively apply the following update rule:

where $\alpha_{t}=\alpha_{t}(x_{t},a^{i}_{t})$ is a random (that is, history-dependent) learning rate that depends on the state-action pair $(x_{t},a^{i}_{t})$ and $\widehat{Q}^{i}_{t+1}(x,a)=\widehat{Q}^{i}_{t}(x,a)$ for all $(x,a)\not=(x_{t},a^{i}_{t})$.

If the learning rate $\alpha_{t}(x_{t},a^{i}_{t})$ is decreased at an appropriate rate in the number of visits to the state-action pair $(x_{t},a^{i}_{t})$, and if every state-action pair is visited infinitely often, then one has $\widehat{Q}^{i}_{t}\to Q^{*i}_{\bm{\pi}^{-i}}$ almost surely [35]. We recall that $Q^{*i}_{\bm{\pi}^{-i}}$ was defined in Section 2 as the optimal Q-function for player $i$ when playing against the stationary policy $\bm{\pi}^{-i}$.

In order to asymptotically respond (nearly) optimally to the policy of its counterparts, player $i$ must exploit the information carried by its learning iterates. Since one must balance this exploitation with persistent exploration, a standard approach in algorithm design is to periodically revise an agent’s policy—either after every system interaction or less frequently—in a manner that places higher probability on actions with better action values. A widely used device for balancing exploration and exploitation is Boltzmann action selection, wherein

where $\tau_{t}>0$ is a temperature parameter that is typically taken to decrease to 0 as $t\to\infty$, and player $i$’s Q-factor estimates $\widehat{Q}^{i}_{t}$ are constructed from the local history $h^{i}_{t}$ observed by player $i$.

Boltzmann action selection is not the only feasible alternative for balancing the trade-off between exploration and exploitation in this context; several other greedy in the limit with infinite exploration (GLIE) mechanisms may also be used to the same effect [33].

In the preceding equations, one observes that ${\rm Pr}(a^{i}_{t}=\cdot\,|h^{i}_{t})$ is simply an alternative representation of the policy actually followed by player $i$. Since player $i$’s Q-factor estimates and other relevant parameters (e.g. the temperature sequence) change with time, any adaptive learning algorithm that exploits learned iterates will be non-stationary. If other players use analogous learning algorithms and exploit their own learned information, then other players will also follow non-stationary policies. In symbols, this is to say that $\bm{\pi}^{-i}\notin\bm{\Pi}^{-i}_{S}$. In this case, the strategic environment defined by the non-stationary policy $\bm{\pi}^{-i}$ is not generally equivalent to an MDP, and there is no guarantee that the Q-factor estimates given by (3) will converge to some meaningful quantity, if they are to converge at all.

Provable non-convergence of Q-iterates obtained by single-agent Q-learning in small, stateless games has been established [17]. Similar non-convergence had been previously been observed empirically in stochastic games [4, 34]. Thus, some modification is needed in order to employ algorithms based on Q-learning in multi-agent settings. Modifications may involve changes to how and when Q-factor updates are performed or may involve changes to how and when action selection probabilities are updated.

As described in the previous section, myopic algorithms that repeatedly change an agent’s policy during the course of interaction can be effective in single-agent settings, when an agent faces a stationary environment. By contrast, when all agents employ such algorithms in a multi-agent system, each agent faces a non-stationary environment and the same convergence guarantees need not apply. In addition to the previously described non-convergence of Q-factors, provable non-convergence of policies under particular learning algorithms has also been observed in various settings, [8, 26, 27].

With the understanding that some modification of single-agent RL algorithms is needed to address the challenge of non-stationarity in MARL, several multi-agent algorithms have been proposed that use multiple timescales. The key feature of the multi-timescale approach is that certain iterates—whether policy parameters, Q-factor estimates, or otherwise—are updated slowly relative to other iterates. In effect, this allows one to analyze the rapidly changing iterates as though the slowly changing iterates were held fixed, artificially mimicking stationarity.

Some works have studied MARL algorithms in which a subset of agents update their policies slowly while the remaining agents update their policy parameters quickly. A two-timescale policy gradient algorithm was studied for two-player, zero-sum games in [6], where a performance guarantee was proven for the minimizing player. Other works, including [29], have empirically studied MARL algorithms in which the agents alternate between updating their policies slowly and quickly according to some commonly accepted schedule.

A second type of multi-timescale algorithm updates various policy-relevant parameters quickly relative to value function estimates, which are updated relatively slowly. This approach can be found in [30, 31] and [32]. This can be contrasted with a third type of multi-timescale algorithm, in which policies are updated relatively slowly while value functions are updated relatively quickly. For a recent example of this, see [23].

A third type of algorithm that retains the same essential quality of multiple timescale algorithms is the regret testing approach, outlined in the next subsection.

In the MARL algorithms surveyed above, the agents update all relevant parameters after each system interaction, and the multi-timescale analysis is implemented by controlling the magnitude of these every-step updates via step-size constraints. An alternative approach is to update certain iterates after each system interaction while updating other iterates infrequently, with many system interactions between updates. Such is the approach taken by works in the tradition of regret testing, pioneered by Foster and Young in [9], which presented an algorithm for stateless games. This approach was later studied by [10] and [24] among others in the context of stateless repeated games, where impressive convergence guarantees were proven. The strong results of [10] and [24] in stateless games were enabled to a significant extent by the absence of state dynamics, which would otherwise complicate value estimation and policy evaluation in multi-state games.

In [1], the regret testing paradigm of Foster and Young was modified for multi-state stochastic games, where one must account for both the immediate cost of an action and also the cost-to-go, which depends on the evolution of the state variable. The decentralized Q-learning algorithm of [1] instructs agents to agree on an increasing sequence of policy update times, $(t_{k})_{k\geq 0}$, and to fix one’s policy within the intervals $[t_{k},t_{k+1})$, called the $k^{th}$ exploration phase.³³3Although the terminology of exploration phases first appeared in [1], the exploration phase approach was pioneered by [9]. In so doing, the joint policy process is fixed over each exploration phase, and within each exploration phase, each agent faces a Markov decision problem (MDP). Each agent then runs a standard Q-learning algorithm within the $k^{th}$ exploration phase, and updates its policy in light of its Q-factors at the end of the $k^{th}$ exploration phase. Since each agent faces an MDP, one can analyze the learning iterates using single-agent learning theory. Provided the exploration phase lengths $T_{k}:=t_{k+1}-t_{k}$ are sufficiently long, the probability of correctly recovering one’s Q-function (defined with respect to the policies of the other agents and elaborated in the coming sections) can be made arbitrarily close to 1.

In many of the papers on regret testers, the proofs of convergence to equilibrium share the same core elements, which can be summarized as follows. First, one defines an equilibrium event. (In the fully synchronized regime described above, this equilibrium event is usually the event that the joint policy of the $k^{th}$ exploration phase is an equilibrium.) Second, one uniformly lower bounds the probability of transiting from non-equilibrium to equilibrium in a fixed number of steps. Third, one shows that the probability of remaining at equilibrium once at equilibrium can be made arbitrarily large relative to the aforementioned lower bound. Fourth and finally, one obtains a high probability guarantee of equilibrium by analyzing the ratio of entry and exit probabilities to equilibrium policies (see, for instance, [9, Lemma 2]).

In effect, the exploration phase technique decouples learning from adaptation, and allows for separate analysis of learning iterates and policy dynamics. This allows for approximation arguments to be used, in which the dynamics of the policy process resemble those of an idealized process where players obtain noise-free learning iterates for use in their policy updates. This has lead to a series of theoretical contributions in MARL that make use of the exploration phase technique, including [36] and [37].

One natural criticism of the exploration phase technique described above is its reliance on synchronization of policy updating. In the description above, agents agree on the policy update times $\{t_{k}\}_{k\geq 0}$ exactly, and no agent ever updates its policy in the interval $(t_{k},t_{k+1}-1]$. Indeed, the mathematically convenient assumption of synchronization is made in various works in the regret testing tradition, including [9, 10] and [24]. This can be justified in some settings, but is demanding decentralized settings where parameters are selected locally by each player or in distributed settings where parameter choices are communicated over noisy channels and are likely to differ across agents.

To relax the synchronization assumption of regret testers, one allows each player $i$ to select its own exploration phase times $(t^{i}_{k})_{k\geq 0}$. Player $i$ then has the opportunity to revise its policies at each time in $(t^{i}_{k})_{k\geq 0}$. We observe that an update time for player $i$ may fall within an exploration phase for some other player $j$. That is, $t^{j}_{m}<t^{i}_{k}<t^{j}_{m+1}$ for two players $i,j$ and exploration phase indices $k$ and $m$. In this case, the environment faced by player $j$ during its $m^{th}$ exploration phase is non-stationary, having been disrupted (at least) by player $i$’s changing policies.

Intuitively, unsynchronized policy updating may be problematic for regret testers because the action-value estimates of a given player depend on historical data from that player’s most recent exploration phase, which in turn depends on the (time-varying) joint policies used during this period. As such, if other players change their policies during an individual’s exploration phase, the individual receives feedback from different sources, and its learning iterates may not approximate any quantity relevant to the prevailing environment at the time of the individual’s policy update. These changes of policy during an exploration phase constitute potential disruptions of a player’s learning, and analysis of the overall joint policy process is difficult when players do not reliably learn accurate action-values.

In this unsynchronized regime, learning and adaptation are not decoupled, as agents do not face stationary MDPs during each of their exploration phases. In particular, it is not guaranteed that a given player’s Q-factors will converge. Consequently, it is not clear that the second and (especially) the third steps of the standard line of proof described above can be reproduced in the unsynchronized setting.

In [24], a heuristic argument suggested that the use of inertia in policy updating may allow one to relax the assumption of perfect synchronization in regret testing algorithms for stateless repeated games. This argument offers a promising starting point, but also has two potential gaps. The first unresolved aspect pertains to the ratio of entry and exit probabilities. The heuristic argument correctly states that one can use inertia to both (i) lower bound the probability of transiting to equilibrium from out of equilibrium, and (ii) make the probability of remaining at equilibrium arbitrarily close to 1. However, the analysis of the overall joint policy process depends on the ratio of these entry and exit probabilities, which depends on the choice of inertia parameter and may be somewhat challenging to analyze.

A second unresolved aspect has to do with the learning routine and how quickly errors are corrected. Here, the specific learning rate used in each agent’s Q-learning algorithm plays an important role. Existing regret testing algorithms employ a decreasing learning rate, so as to ensure the convergence of learning iterates within a synchronized exploration phase. In the unsynchronized regime, however, agents learn against time-varying environments. If an agent uses a decreasing learning rate, it gives relatively high weight to outdated data that are no longer representative of its current environment. As such, it may take a long, uninterrupted stretch of learning against the prevailing environment to correct the outdated learning. The time required will depend on how much the learning rate parameters have been reduced, and these considerations must be quantified explicitly in the analysis. This point is somewhat subtle, and may pose a challenge if one attempts to use decreasing learning rates in the unsynchronized regime.

In this paper, we formalize the heuristic argument of [24] and show that it is effectively correct, with minor caveats. To rectify the unaddressed aspects mentioned above, we modify the Q-learning protocol to use a constant learning rate and conduct a somewhat involved analysis of the resulting behaviour. We focus on weakly acyclic games and best-response-based policy updating routines, but the analysis from this setting can be used to study other policy update routines and classes of games, including $\epsilon$-satisficing policy update dynamics such as those described in [37].

In order to state our main result, Theorem 4.1, we now impose some assumptions on the underlying game $\mathcal{G}$, on the algorithmic parameters, and on the mutual independence of certain randomized subroutines appearing in the algorithm.

In words, Theorem 4.1 says the following: if the relative frequency of policy update times of different players is controlled by some ratio $R$, if players use sufficiently small learning rates $\bm{\alpha}$, and if the lower bound $T$ on each player’s exploration phase length is sufficiently long relative to both the learning rates $\bm{\alpha}$ as well as the ratio parameter $R$, then play will be driven to equilibrium with high probability.

As we will see, the interdependence of the various parameters—$R,\bm{\alpha},$ and $T$—is significant in the analysis to follow.

The proof of Theorem 4.1 involves three major steps. First, we introduce a sequence of equilibrium events, $\{B_{k}\}_{k\geq 0}$, defined in terms of a suitably defined sequence of time intervals $\{[\tau^{\min}_{k},\tau^{\max}_{k}]\}_{k\geq 0}$, to be elaborated in the sequel. For $k\geq 0$, we put

In words, $B_{k}$ is the event in which the baseline policy did not change during the interval $[\tau^{\min}_{k},\tau^{\max}_{k}]$ and moreover the baseline policy was an equilibrium during this time.

Second, for a particular integer $L<\infty$ (defined in the text preceding Lemma 6.8), we argue in Lemma 6.8 that we can control and lower bound the probability of remaining at the equilibrium event for $L$ steps: that is, ${\rm Pr}(B_{k+L}|B_{k})$ can be made arbitrarily large by suitable selection of algorithm parameters. The proof of Lemma 6.8 uses convergence properties of Q-learning iterates (Lemma 6.3) and requires careful arguments about conditional probabilities, since conditioning on the event $B_{k}$ carries confounding information about the state-action trajectory from both before and after time $\tau^{\min}_{k}$ and precludes simple analysis that disconnects the future evolution of Q-learning estimates from the history of the system before time $\tau^{\min}_{k}$. Consequently, the analysis is somewhat delicate, and is worded in terms of primitive random variables, which offers a path around the confounding effect of conditioning on $B_{k}$.

Third, we argue in Lemma 6.10 that the probability of driving play to this equilibrium event in $L$ time steps can be lower bounded by a positive constant. After this is achieved, one can then explicitly lower bound ${\rm Pr}(B_{k+mL})$ for suitably large $m$, as in [1] and [37].

We begin by defining several objects that will be needed for the various lemmas to follow. The notation in this section builds on that of Section 4.1.3. For ease of reference, we have included a glossary of notation in Table 2, Table 3, and Table 4 of Appendix A.

Recall that in Section 4.1.3, we motivated the use of primitive random variables for describing the algorithmic randomness of Algorithm 1. The primitive random variables described earlier included $\{\tilde{u}^{i}_{t},\tilde{\rho}^{i}_{t}\}_{t\geq 0}$, which appeared in randomized action selection, and $\{\tilde{\lambda}^{i}_{k},\tilde{\pi}^{i}_{k}\}_{k\geq 0}$, which appeared in randomized policy updated. We also recall that $\tilde{\pi}^{i}_{k}$ was previously a random sample from a particular policy subset $B^{i}\subseteq\Pi^{i}_{SD}$, which was defined using player $i$’s Q-factor iterates. In this section, it will be helpful to further isolate the role of algorithmic randomness, and therefore we will also consider random samples from all non-empty subsets of $\Pi^{i}_{SD}$. For the latter purpose and for each $i\in\mathcal{N}$, we arbitrarily order non-empty subsets of $\Pi^{i}_{SD}$ as $B^{i,1},\dots,B^{i,m_{i}}$, where $m_{i}=|2^{\Pi^{i}_{SD}}\setminus\{\varnothing\}|$.

• •

  $\omega^{i}_{t}:=(\tilde{\rho}^{i}_{t},\tilde{u}^{i}_{t},\tilde{\lambda}^{i}_{t},\tilde{\pi}^{i}_{t}(B^{i,1}),\dots,\tilde{\pi}^{i}_{t}(B^{i,m_{i}})),$ for all $i\in\mathcal{N}$. We define $\mathfrak{S}^{i}$ to be the set in which the random quantity $\omega^{i}_{t}$ takes its values. That is,

  $$\mathfrak{S}^{i}:=[0,1]\times\mathbb{A}^{i}\times[0,1]\times B^{i,1}\times\cdots\times B^{i,m_{i}},\quad\forall i\in\mathcal{N}.$$

• In plain terms, $\omega^{i}_{t}$ consists of random samples of each of the quantities needed for player $i$ to execute the randomized subroutines in Algorithm 1 at a given time $t$.

• •

  $\bm{\omega}_{t}:=(W_{t},\omega^{1}_{t},\dots,\omega^{N}_{t})$, where $\{W_{t}\}_{t\geq 0}$ is the $[0,1]$-valued independent and identically distributed (i.i.d.) noise process driving state transitions that was introduced in §4.1.3.

• For each $t$, $\bm{\omega}_{t}$ is a collection of the randomized quantities described in $\omega^{i}_{t}$ along with the random noise that drives state transitions. Of note, the information contained in $\bm{\omega}_{t}$ is sufficient for recovering the subsequent state $x_{t+1}$, the current joint action $\mathbf{a}_{t}$, and the subsequent joint policy $\bm{\phi}_{t+1}$.

• •

  $\bm{\varpi}_{t{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+}}:=(\bm{\omega}_{t},\bm{\omega}_{t+1},\dots)$. This quantity describes all random samples required to fully describe the future of the state-action trajectory and thus of Q-factors.

• •

  $\widehat{\textbf{Q}}_{t}:=(\widehat{Q}^{1}_{t},\dots,\widehat{Q}^{N}_{t})$.

• •

  $\mathbf{h}_{t}$ $:=(x_{0},\bm{\phi}_{0},\widehat{\textbf{Q}}_{0},\dots,x_{t},\bm{\phi}_{t},\widehat{\textbf{Q}}_{t})$. This quantity describes the states, joint policies, and Q-factors up to and including time $t$.

• •

  $\mathbf{H}_{t}$ $:=\left(\mathbb{X}\times\bm{\Pi}_{SD}\times\mathbb{R}^{\mathbb{X}\times\mathbb{A}^{1}}\times\dots\times\mathbb{R}^{\mathbb{X}\times\mathbb{A}^{N}}\right)^{t+1}$.

• •

  $\mathbf{H}_{t,\rm eq}$ $:=\{\mathbf{h}_{t}\in\mathbf{H}_{t}:\bm{\phi}_{t}\in\bm{\Pi}^{0{\rm\text{-}eq}}_{SD}\}$. This set consists of those $t$-histories for which the final joint policy $\bm{\phi}_{t}$ is an equilibrium.

We note that $\omega^{i}_{t}$ is a random quantity taking values in $\mathfrak{S}^{i}$, while $\bm{\omega}_{t}$ is a random quantity taking values in $[0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}$. For each $t\geq 0$, a realization of the random quantity $\bm{\varpi}_{t+}$ is a sequence with entries in $[0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}$.

When every player uses Algorithm 1 to play the game and each player’s randomization mechanism is governed by the primitive random variables of §4.1.3, we have that the sample path of play—including realizations of the state process $\{x_{t}\}_{t\geq 0}$, the action processes $\{a^{i}_{t}\}_{t\geq 0}$ for each agent $i\in\mathcal{N}$, the baseline joint policy process $\{\bm{\phi}_{t}\}_{t\geq 0}$, and the Q-factor estimates $\{\widehat{Q}^{i}_{t}\}_{t\geq 0}$—are deterministic functions of any given prefix history $\mathbf{h}_{s}\in\mathbf{H}_{s}$ and its corresponding continuation, $\bm{\varpi}_{s+}\in\left([0,1]\times\mathfrak{S}^{1}\times\cdots\times\mathfrak{S}^{N}\right)^{\infty}$, where $s\in\mathbb{Z}_{\geq 0}$. With this in mind, for $i\in\mathcal{N}$ and $t\geq 0$, we define mappings $\mathcal{Q}^{i}_{t}$ and $\Phi_{t}$ such that

Next, for any $s,t\geq 0$ and any $i\in\mathcal{N}$, we introduce a function $\bar{Q}^{i}_{t+s}(\mathbf{h}_{t},\bm{\varpi}_{t+})$ that reports the hypothetical Q-factors player $i$ would have obtained if the baseline policies had been frozen at time $t$. That is, the history up to time $t$ is given by $\mathbf{h}_{t}$, the primitive random variables from $t$ onward are given by $\bm{\varpi}_{t+}$, and we obtain the hypothetical ($\bm{\varpi}_{t+}$-measurable) continuation trajectory $(\bar{x}_{t},\bar{\mathbf{a}}_{t},\dots,\bar{x}_{t+s},\bar{\mathbf{a}}_{t+s})$, as $\bar{x}_{t}:=x_{t}$,