Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Introduction

Reinforcement learning (RL) has been a fundamental driver of numerous recent advances in Artificial Intelligence (AI) that range from super-human performance in competitive game-playing and strategic decision-making in multiple tasks to robotics, autonomous-driving and cyber-physical systems . A core ingredient for the success of single-agent RL systems, which are typically modelled as Markov Decision Processes (MDPs), is the existence of stationary deterministic optimal policies . This allows the design of efficient algorithms that provably converge towards such policies . However, in practice, a majority of the above systems involve multi-agent interactions. In such cases, despite the notable empirical advancements, there is a lack of understanding of the theoretical convergence guarantees of existing multi-agent reinforcement learning (MARL) algorithms.

The main challenge when transitioning from single to multi-agent RL settings is the computation of Nash policies. A Nash policy for $n>1$ agents is defined to be a profile of policies $(\pi_{1}^{*},...,\pi_{n}^{*})$ so that by fixing the stationary policies of all agents but $i$, $\pi_{i}^{*}$ is an optimal policy for the resulting single-agent MDP and this is true for all $1\leq i\leq n$ Analogue of Nash equilibrium notion. (see Definition 1). Note that in multi-agent settings, Nash policies may not be unique in principle.

A common approach for computing Nash policies in MDPs is the use of policy gradient methods. There has been significant progress in the analysis of policy gradient methods during the last couple of years, notably including the works of (and references therein), but it has mainly concerned the single-agent case: the convergence properties of policy gradient in MARL remain poorly understood. Existing steps towards a theory for multi-agent settings involve the papers of who show convergence of independent policy gradient to the optimal policy for two-agent zero-sum stochastic games, of who improve the result of using optimistic policy gradient and of who study extensions of Natural Policy Gradient using function approximation. It is worth noting that the positive results of and depend on the fact that two-agent stochastic zero-sum games satisfy the “min-max equals max-min” property (even though the value-function landscape may not be convex-concave, which implies that Von Neumann’s celebrated minimax theorem may not be applicable).

While the previous works enhance our understanding in competitive interactions, i.e., interactions in which gains can only come at the expense of others, MARL in cooperative settings remains largely under-explored and constitutes one of the current frontiers in AI research . Based on the above, our work is motivated by the following natural question:

Can we get (provable) convergence guarantees for multi-agent RL settings in which cooperation is desirable?

To address this question, we define and study a class of $n$-agent MDPs that naturally generalize normal form potential games , called Markov Potential Games (MPGs). In words, a multi-agent MDP is a MPG as long as there exists a (state-dependent) real-valued potential function $\Phi$ so that if an agent $i$ changes their policy (and the rest of the agents keep their policy unchanged), the difference in agent $i$’s value/utility, $V^{i}$, is captured by the difference in the value of $\Phi$ (see Definition 2). Weighted and ordinal MPGs are defined similar to their normal form counterparts (see Remark 1).

Under our definition, we answer the above motivating question in the affirmative. In particular, we show that if every agent $i$ independently runs (with simultaneous updates) policy gradient on his utility/value $V^{i}$, then, after $O(1/\epsilon^{2})$ iterations, the system will reach an $\epsilon$-approximate Nash policy (see informal Theorem 1.1 and formal Theorem 4.5). Moreover, for the finite sample analogue, i.e., if every agent $i$ independently runs (with simultaneous updates) stochastic policy gradient, we show that the system will reach an $\epsilon$-approximate Nash policy after $O(1/\epsilon^{6})$ iterations.

Along the way, we prove several properties about the structure of MPGs and their Nash policies (see Theorem 1.2 and Section 3). In sum, our results can be summarized in the following two Theorems.

Consider a MPG with $n$ agents and let $\epsilon>0$. Suppose that each agent $i$ runs independent policy gradient using direct parameterization on their policy and that the updates are simultaneous. Then, the learning dynamics reach an $\epsilon$-Nash policy after $\mathcal{O}(1/\epsilon^{2})$ iterations. If instead, each agent $i$ runs stochastic policy gradient using greedy parameterization (see (4)) on his policy and that the updates are simultaneous, then the learning dynamics reach an $\epsilon$-Nash policy after $\mathcal{O}(1/\epsilon^{6})$ iterations.

This result holds trivially for weighted MPGs and asymptotically also for ordinal MPGs, see Remark 5.

The following facts are true for MPGs with $n$-agents:

There always exists a Nash policy profile $(\pi_{1}^{*},\dots,\pi_{n}^{*})$ so that $\pi_{i}^{*}$ is deterministic for each agent $i$ (see Theorem 3.1).

We can construct MDPs for which each state is a (normal-form) potential game but which are not MPGs. This can be true regardless of whether the whole MDP is competitive or cooperative in nature (see Examples 1 and 2, respectively). On the opposite side, we can construct MDPs that are MPGs but which include states that are purely competitive (i.e., zero-sum games), see Example 3.

We provide sufficient conditions so that a MDP is a MPG. These include cases where each state is a (normal-form) potential game and the transition probabilities are not affected by agents actions or the reward functions satisfy certain regularity conditions between different states (see conditions C1 and C2 in Proposition 3.2).

Technical Overview.

The first challenge in the proof of Theorem 1.1 is that multi-agent settings (MPGs) do not satisfy the gradient dominance property, which is an important part in the proof of convergence of policy gradient in single-agent settings . In particular, different Nash policies may yield different value to each agent and as a result, there is not a properly defined notion of value in MPGs (in contrast to zero-sum stochastic games ). On the positive side, we show that agent-wise (i.e., after fixing the policy of all agents but $i$), the value function, $V^{i}$, satisfies the gradient dominance property along the direction of $\pi_{i}$ (policy of agent $i$). This can be leveraged to show that every (approximate) stationary point (Definition 4) of the potential function $\Phi$ is an (approximate) Nash policy (Lemma 4.2). As a result, convergence to an approximate Nash policy is established by first showing that $\Phi$ is smooth and then by applying Projected Gradient Ascent (PGA) on $\Phi$. This step uses the rather well-known fact that (PGA) converges to $\epsilon$-stationary points in $O(1/\epsilon^{2})$ iterations for smooth functions. As a result, by applying PGA on the potential $\Phi$, one gets an approximate Nash policy. Our convergence result then follows by showing that PGA on the potential function, $\Phi$, generates the same dynamics as if each agent $i$ runs independent PGA on their value function, $V^{i}$.

In the case that agents do not have access to exact gradients, we derive a similar result for finite samples. In this case, we apply Projected Stochastic Gradient Ascent (PSGA) on $\Phi$ which (as was the case for PGA) can be shown to be the same as when agents apply PSGA independently on their individual value functions. The key is to get an unbiased sample for the gradient of the value functions and prove that it has bounded variance (in terms of the parameters of the MPG). This comes from the discount factor, $\gamma$; in this case, $1-\gamma$ can be interpreted as the probability to terminate the MDP at a particular state (and $\gamma$ to continue). This can be used to show that a trajectory of the MDP is an unbiased sample for the gradient of the value functions. To guarantee that the estimate has bounded variance, we apply the approach of which requires that agents perform PSGA with $\alpha$-greedy exploration (see (4)). The main idea is that this parameterization stays away from the boundary of the simplex throughout its trajectory.

Concerning our structural results, the main technical challenge is the dependence of state-transitions (in addition to agents’ rewards) on agents’ actions. Our work in this part is mainly concerned with showing that the class of MPGs can be significantly larger than state based potential games but also that even simple coordination games may fail to satisfy the (exact) MPG property. Finally, concerning the existence of a deterministic Nash policies, the main challenge is (as in Theorem 1.1) the lack of a (unique) value in general multi-agent settings. As we show in the proof of Theorem 3.1, this issue can be still handled within the class of MPGs by constructing single-agent deviations (to deterministic optimal policies) which keep the value of the potential constant (at its global maximum). This process (which leads to a deterministic Nash policy profile) depends critically on the MPG property and does not generalize to arbitrary MARL settings.

Other works on MPGs.

There are only a few papers in the recent literature that define and analyze MARL settings under the term Markov Potential Games using slight different definitions (see ). These papers mainly focus on state-based potential MDPs (i.e., MDPs in which every state is a potential game) and require rather restrictive additional conditions, such as equality or monotonicity of the state-based potential functions, to address the computational challenge of finding Nash policies.The relation of these conditions to the current work is discussed in more detail in Proposition 3.2 and Remark 2. Our current results demonstrate the efficiency of simultaneous policy gradient as a to powerful method to find Nash policies even without additional restrictive assumptions on the state-based potential functions. Moreover, as mentioned in Theorem 1.2, the current definition also encompasses MDPs that are not necessarily potential at each state. To the best of our knowledge, the only (cooperative) MPGs that have been successfully addressed prior to this work, are the ones in which all agents receive the same value/utility and which constitute a subclass of the MPG setting considered in this paper.

Preliminaries

The following notation is standard and largely follows and . We consider a setting with $n$ agents who repeatedly select actions in a shared Markov Decision Process (MDP). The goal of each agent is to maximize their respective value function. Formally, a MDP is defined as a tuple $\mathcal{G}=(\mathcal{S},\mathcal{N},\{\mathcal{A}_{i},R_{i}\}_{i\in\mathcal{N}},P,\gamma,\rho)$, where

$\mathcal{S}$ is a finite state space of size $S=|\mathcal{S}|$. We will write $\Delta(\mathcal{S})$ to denote the set of all probability distributions over the set $\mathcal{S}$.

$\mathcal{N}=\{1,2,\dots,n\}$ is the set of the $n\geq 2$ agents in the game.

$\mathcal{A}_{i}$ is a finite action space for agent $i\in\mathcal{N}$ with generic element $a_{i}\in\mathcal{A}_{i}$. Using common conventions, we will write $\mathcal{A}=\prod_{i\in\mathcal{N}}\mathcal{A}_{i}$ and $\mathcal{A}_{-i}=\prod_{j\neq i}\mathcal{A}_{j}$ to denote the joint action spaces of all agents and of all agents other than $i$ with generic elements $\mathbf{a}=(a_{i})_{i\in\mathcal{N}}$ and $\mathbf{a_{-i}}=(a_{j})_{i\neq j\in\mathcal{N}}$, respectively. According to this notation, we have that $\mathbf{a}=(a_{i},\mathbf{a_{-i}})$. We will write $X=|\mathcal{X}|$ and $\Delta(\mathcal{X})$ to denote the size of any set $\mathcal{X}\in\{\mathcal{A}_{i},\mathcal{A}_{-i},\mathcal{A}\}$ and the space of all probability distributions over $\mathcal{X}$, respectively.

$R_{i}:\mathcal{S}\times\mathcal{A}\to$ is the individual reward function of agent $i\in\mathcal{N}$, i.e., $R_{i}(s,a_{i},\mathbf{a}_{-i})$ is the instantaneous reward of agent $i$ when agent $i$ takes action $a_{i}$ and all other agents take actions $\mathbf{a}_{-i}$ at state $s\in\mathcal{S}$.

$P$ is the transition probability function, for which $P(s^{\prime}\mid s,\mathbf{a})$ is the probability of transitioning from $s$ to $s^{\prime}$ when $\mathbf{a}\in\mathcal{A}$ is the action profile chosen by the agents.

$\gamma$ is a discount factor for future rewards of the MDP, shared by all agents.

$\rho\in\Delta(\mathcal{S})$ is the distribution for the initial state at time $t=0$.

Whenever time is relevant, we will index the above terms with $t$. In particular, at each time step $t\geq 0$, all agents observe the state $s_{t}\in\mathcal{S}$, select actions $\mathbf{a}_{t}=(a_{i,t},\mathbf{a}_{-i,t})$, receive rewards $r_{i,t}:=R_{i}(s_{t},\mathbf{a}_{t}),i\in\mathcal{N}$ and transition to the next state $s_{t+1}\sim P(\cdot\mid s_{t},\mathbf{a}_{t})$. We will write $\tau=(s_{t},\mathbf{a}_{t},\mathbf{r}_{t})_{t\geq 0}$ to denote the trajectories of the system, where $\mathbf{r}_{t}:=(r_{i,t}),i\in\mathcal{N}$.

Policies and Value Functions.

Nash Policies.

The solution concept that will be focusing on is the Nash Policy. Formally:

A joint policy, $\pi^{*}=(\pi_{i}^{*})_{i\in\mathcal{N}}\in\Pi$, is a Nash policy if for each agent $i\in\mathcal{N}$ it holds that

i.e., if the policy, $\pi_{i}^{*}$, of each agent $i\in\mathcal{N}$ maximizes agent $i$’s value function for each starting state $s\in\mathcal{S}$ given the policies, $\pi^{*}_{-i}=(\pi^{*}_{j})_{j\neq i}$, of all other agents $j\neq i\in\mathcal{N}$. Similarly, a joint policy $\pi^{*}=(\pi_{i}^{*})_{i\in\mathcal{N}}$ is an $\epsilon$-Nash policy if there exists an $\epsilon>0$ so that for each agent $i$

We note that the definition of Nash policy is the same if $s\sim\rho$ (random starting state).

Markov Potential Games.

We are ready to define the class of MDPs that we will focus on for the rest of the paper, i.e., Markov Potential Games.

Similar to normal-form games, one may also define more general notions of MPGs, such as ordinal or weighted Markov Potential Games. Specifically, if for all agents $i\in\mathcal{N}$, all states $s\in\mathcal{S}$ and all policies $\pi_{i},\pi_{i}^{\prime}\in\Pi_{i},\pi_{-i}\in\Pi_{-i}$, the function $\Phi_{s},s\in\mathcal{S}$ satisfies

then the MDP, $\mathcal{G}$, is called an Ordinal Markov Potential Game (OMPG). If there exist positive constants $w_{i}>0,i\in\mathcal{N}$ so that

then $\mathcal{G}$ is called a Weighted Markov Potential Game (WMPG).

Similarly to normal-form games, such classes are naturally motivated also in the setting of multi-agent MDPs. As Example 2 in Section B.1 shows, even simple potential-like settings, i.e., settings in which coordination is desirable for all agents, may fail to be exact MPGs (but may still be ordinal or weighted MPGs) due to the dependence of both the rewards and the transitions on agents’ decisions. From our current perspective, ordinal and weighted MPGs (as defined in Remark 1) remain relevant, since as we argue, policy gradient still converges to Nash policies in these classes of games (see Remark 5).

Independent Policy Gradient and Direct Parameterization

We assume that all agents update their policies independently according to the projected gradient ascent (PGA) or policy gradient algorithm on their policies. Independence here refers to the fact that (PGA) requires only local information (each agent’s own rewards, actions and view of the environment) to form the updates, i.e., to estimate that agent’s policy gradients. Such protocols are naturally motivated and particularly suitable for distributed AI settings in which all information about the interacting agents, the type of interaction and the agent’s actions (policies) is encoded in the environment of each agent.In practice, even though every agent treats their environment as fixed, the environment changes as other agents update their policies. This is what makes the analysis of such protocols particularly challenging in full generality. It also highlights the importance of studying classes of games (MDPs) in which convergence of independent learning protocols can be obtained such as zero-sum stochastic games or MPGs as we do in this paper.

for each agent $i\in\mathcal{N}$, where $P_{\Delta(\mathcal{A}_{i})^{S}}$ is the projection onto $\Delta(\mathcal{A}_{i})^{S}$ in the Euclidean norm. We also assume that all players $i\in\mathcal{N}$ use direct policy parameterizations, i.e.,

with $x_{i,s,a}\geq 0$ for all $s\in\mathcal{S},a\in\mathcal{A}_{i}$ and $\sum_{a\in\mathcal{A}_{i}}x_{i,s,a}=1$ for all $s\in\mathcal{S}$. This parameterization is complete in the sense that any stochastic policy can be represented in this class .

In practice, agents use projected stochastic gradient ascent (PSGA), according to which, the actual gradient, $\nabla_{\pi_{i}}V_{\rho}^{i}(\pi^{(t)})$, is replaced by an estimate thereof that is calculated from a randomly selected (yet finite) sample of trajectories of the MDP. This estimate, $\hat{\nabla}_{\pi_{i}}^{(t)}$ may be derived from a single or a batch of observations which in expectation behave as the actual gradient. We choose the estimate of the gradient of $V^{i}_{\rho}$ to be

where $s_{0}^{t}\sim\rho$, and $R^{(T,t)}_{i}=\sum_{k=0}^{T}r^{k}_{i,t}$ is the sum of rewards of agent $i$ for a batch of time horizon $T$ along the trajectory generated by the stochastic gradient ascent algorithm at its $t$-th iterate (recall that the discount factor, $\gamma$, functions as the probability to continue at each step, so $T$ is sampled from a geometric distribution).

The direct parameterization is not sufficient to ensure that the variance of the gradient estimator is bounded (as policies approach the boundary). In this case, we will require that each agent $i\in\mathcal{N}$ uses instead direct parameterization with $\alpha$-greedy exploration as follows

where $\alpha$ is the exploration parameter for all agents. Under $\alpha$-greedy exploration, it can be shown that (3) is unbiased and has bounded variance (see Lemma 4.6). The form of PSGA is

Structural Properties of Markov Potential Games

The first question that we examine, is whether MPGs possess a deterministic Nash policy profile, as is the case in normal-form potential games . In Theorem 3.1, we show that this important property indeed carries over (which settles part (a) of informal Theorem 1.2).

Let $\mathcal{G}$ be a Markov Potential Game (MPG). Then, there exists a Nash policy $\pi^{*}\in\Delta(\mathcal{A})^{S}$ which is deterministic, i.e., for each agent $i\in\mathcal{N}$ and each state $s\in\mathcal{S}$, there exists an action $a_{i}\in\mathcal{A}_{i}$ so that $\pi_{i}^{*}(a_{i}\mid s)=1$.

The proof of Theorem 3.1 (which is deferred to Appendix B) exploits the fact that we can iteratively reduce the non-deterministic components of an arbitrary Nash policy profile that corresponds to a global maximizer of the potential and still retain the Nash profile property at all times. At each iteration, we isolate an agent $i\in\mathcal{N}$, and find a deterministic (optimal) policy for that agent in the (single-agent) MDP in which the policies of all other agents but $i$ remain fixed. The important observation is that the resulting profile is again a global maximizer of the potential and hence, a Nash policy profile. This argument critically relies on the MPG structure and does not seem directly generalizable to MDPs that do not satisfy Definition 2.

Sufficient Conditions for MPGs.

We next turn to the question of which types of games are captured by Definition 2. It is tempting to think that MDPs which are potential at every state (meaning that the immediate rewards at every state are captured by a (normal-form) potential game at that state) are trivially MPGs. As we show in Examples 1 and 2, this intuition fails in the most straightforward way: we can construct simple MDPs that are potential at every state but which are purely competitive (do not possess a deterministic Nash policy) overall (Example 1) or which are cooperative in nature overall but which do not possess an exact potential function (Example 2).

Consider the two-agent, two-state, and two actions per state MDP, $\mathcal{G}=\left(\mathcal{S}=\{0,1\},\mathcal{N}=\{A,B\},(\mathcal{A}_{i}=\{0,1\},R_{i})_{i\in\mathcal{N}},P,\rho\right)$ in Figure 2. At state ($1$), agent A always receives $+2$ () and agent B always receives ($+2$) regardless of the actions they choose. That is, the reward functions for both states are constant, which implies that both states are potential games. The transitions are determinstic and are given by

where $\oplus$ denotes the xor operator or equivalently, addition modulo $2$, i.e., $1\oplus 1=0$. The MDP $\mathcal{G}$ is illustrated in Figure 2.

To show that $\mathcal{G}$ is not a MPG, it suffices to show that it cannot have a deterministic Nash policy as should be the case according to Theorem 3.1. To obtain a contradiction, assume that agent $A$ is using a deterministic action $a_{A}^{0}\in\{0,1\}$ at state . Then, agent $B$, who prefers to move to state $1$, will optimize their utility by choosing the action $a^{0}_{B}\in\{0,1\}$ that yields $a^{0}_{A}\oplus a_{B}^{0}=1$. In other words, given any deterministic action of agent $A$ at state , agent $B$ can choose an action that always moves the sequence of play to state $1$. Thus, such an action cannot be optimal for agent $A$ which implies that the MDP $\mathcal{G}$ does not have a deterministic Nash policy profile as claimed.

Intuitively, the two agents in Example 1 play a game of matching pennies in terms of the actions that they choose (since they prefer playing in opposing states). Thus, competition arises due to the opposing preferences of the agents over states even though the immediate rewards at each states are determined by normal form potential games.

Example 2 shows that a state-based potential game may fail to be a MPG even if agents have similar preferences over states. In that case, the reason is that one cannot find an exact potential function due to the dependence of the transitions on agents’ actions. However, in the case of Example 2, it is straightforward to show that the game is an ordinal potential game, cf. Remark 2.

Consider the two-agent, two-state MDP, $\mathcal{G}=(\mathcal{S}=\{0,1\},\mathcal{N}=\{A,B\},\{\mathcal{A}_{i},$ $R_{i}\}_{i\in\mathcal{N}},P,\rho)$ in Figure 2. At state $s_{0}$, each agent has two actions, $\mathcal{A}_{i}=\{0,1\}$, whereas at state $s_{1}$, each agent has a single action. The transitions and instantaneous rewards, $(R_{A}(s,\mathbf{a}),R_{B}(s,\mathbf{a})),s=0,1,\mathbf{a}=(a^{s}_{A},a^{s}_{B})$ of this MDP are shown in Figure 2. If the action profile $\mathbf{a}=(a^{0}_{A},a^{0}_{B})=(0,0)$ is selected at state $s_{0}$, then the play remains there, otherwise the play transitions to state $s_{1}$ and remains there forever.

where $p,q\in$ are the probabilities with which agents $A$ and $B$ respectively select their action at state $s_{0}$. This expression clearly indicates the complexity that emerges in MPGs versus static games. Namely, the first term of the value function is a common term (same for both agents) that can conveniently become part of a potential function. However, the second term is a mixture of a common term (denominator) and a term that is different for each agent (numerator). The reason is that the policy of each agent determines the time that the agents spend at each state and thus, it does not (generally) allow for an agent independent term (as required by the definition of a potential game). However, this game is clearly a potential-like game in which agents have common interests. This motivates to look at the notion of ordinal or weighted MPGs. Note that (by a straightforward calculation) this game is an ordinal MPG for the potential function $\Phi_{s}=\phi_{s}$ for $s=0,1$.

Based on the intuition from the previous Examples, we formulate the following sufficient conditions in Proposition 3.2 which ensure that a state based potential game (i.e., a game that is potential at every state) is also a MPG according to Definition 2 (cf. Theorem 1.2 part (c)).

Consider a MDP $\mathcal{G}$ in which every state $s\in\mathcal{S}$ is a potential game, i.e., the immediate rewards $R(s,\mathbf{a})=(R_{i}(s,\mathbf{a}))_{i\in\mathcal{N}}$ for each state $s\in\mathcal{S}$ are captured by the utilities of a (normal-form) potential game with potential function $\phi_{s}$. Additionally, assume that one of the following conditions holds

Agent-Independent Transitions: $P(s^{\prime}\mid s,\mathbf{a})$ does not depend on $\mathbf{a}$, that is, $P(s^{\prime}\mid s,\mathbf{a})=P(s^{\prime}\mid s)$ is just a function of the present state for all states $s,s^{\prime}\in\mathcal{S}$.

If either C1 or C2 are true, then $\mathcal{G}$ is a MPG.

As the rest of the proofs of Section 3, the proof of Proposition 3.2 is provided in Appendix B. The following remarks are due.

Condition C1 can also be viewed as a special case of condition C2. However, due to its simplicity, it is more instructive to state C1 separately. Condition C2 (or variations of it) are already present in existing studies of potential-like MDPs . Example 2 shows that such conditions are restrictive, in the sense that they do not capture very simple MDPs that intuitively have a potential-like (cooperative) structure. This motivates the study of ordinal or weighted potential games as natural models to capture such cases. As we show, our convergence results about independent policy gradient naturally extend to these classes as well (see Remark 5).

The previous discussion focuses on games that are potential at every state as natural candidates to generalize the notion of normal-form games to state games. This leaves an important question unanswered: are there games which are not potential at every state but which are captured by the our current definition of MPGs? Example 3 answers this question in the affirmative. Together with Example 1, this settles the claim in Theorem 1.2, part (b).

At state $s_{0}$, agents’ rewards, $(R_{1}(s_{0},\mathbf{a}),R_{2}(s_{0},\mathbf{a}))$ form a constant sum (equivalent to zero-sum) game. The agents’ actions at $s_{0}$ induce a deterministic transition to a state $s_{ab}$ with $a,b\in\{H,T\}$ in which the only available actions are precisely the chosen actions at $s_{0}$. Each agent’s instantaneous reward at this state is the reward of the other agent at $s_{0}$ (scaled by $1/\gamma$). The MDP then transitions deterministically to state $s_{1}$ which is a potential game with rewards $(R_{1}(s_{1},\mathbf{a}),R_{2}(s_{1},\mathbf{a}))$. After the agents select their actions at $s_{1}$, there is an exogenous given probability, $p_{0}$, according to which the play transitions to state $s=0$. Otherwise it remains at $s_{1}$.

While the game at state $s=0$ is not a potential game, the combined states in the dotted rectangle of Figure 3 do form a potential game, with potential function equal to the sum of the agent’s payoffs at $s_{0}$ (the rewards of both agents are equal for every pass of the play through the states in the dotted rectangle). Thus, it is not hard to see that both value functions are of the form

for $s\in\{s_{0},s_{1}\}$ and $i=\{1,2\}$, where $c_{1}\left(s\right),c_{2}\left(s\right)>0$ are appropriate constants that depend only the state $s\in\{s_{0},s_{1}\}$ and not on the agents. Since the game at $s_{1}$ is a potential game, with potential function given by a $2\times 2$ matrix $\phi_{1}$, it is immediate to see that

is a potential function so that $\mathcal{G}$ satisfies the definition of an MPG.

Convergence of Policy Gradient in Markov Potential Games

The current section presents the proof of convergence of (projected) policy gradient to approximate Nash policies in Markov Potential Games (MPGs). We analyze the cases of both infinite and finite samples using direct and $\alpha$-greedy parameterizations, respectively.

Before we proceed with the formal statements and proofs of this section, we provide the commonly used definition of distribution mismatch coefficient applied to our setting.

Let $\mu$ be any distribution in $\Delta(\mathcal{S})$ and let $\mathcal{O}$ be the set of policies $\pi\in\Delta(\mathcal{A})^{S}$. We call

the distribution mismatch coefficient, where $d^{\pi}_{\mu}$ is the discounted state distribution (17).

The first auxiliary Lemma has to do with the projection operator that is used on top of the independent policy gradient, so that the policy vector $\pi^{(t)}_{i}$ remains a probability distribution for all agents $i\in\mathcal{N}$ (see (PGA)). It is not hard to show (due to separability) that the projection operator being applied independently for each agent $i$ on $\Delta(\mathcal{A}_{i})^{S}$ is the same as jointly applying projection on $\Delta(\mathcal{A})^{S}$. This is the statement of Lemma 4.1.

Let $\pi:=(\pi_{1},...,\pi_{n})$ be the policy profile for all agents and let

be a gradient step on the potential function for a step-size $\alpha>0$. Then, it holds that

The main implication of Lemma 4.1 along with the equality of the derivatives between value functions and the potential function in MPGs, i.e., $\nabla_{\pi_{i}}V_{s}^{i}(\pi)=\nabla_{\pi_{i}}\Phi(\pi)$ for all $i\in\mathcal{N}$ (see property P2 in Proposition B.1), is that running independent (PGA) on each agent’s value function is equivalent to running (PGA) on the potential function $\Phi$. In turn, Lemma 4.2 suggests that as long as policy gradient reaches a point $\pi^{(t)}$ with small gradient along the directions in $\Delta(\mathcal{A})^{S}$, it must be the case that $\pi^{(t)}$ is an approximate Nash policy. Together with Lemma 4.1, this will be sufficient to prove convergence of (PGA).

To proceed, we need the formal definition of a stationary point for the potential function $\Phi$ which is given below.

A policy profile $\pi:=(\pi_{1},...,\pi_{n})\in\Delta(\mathcal{A})^{S}$ is called $\epsilon$-stationary for $\Phi$ w.r.t distribution $\mu$ as long as

In words, the function $\Phi(\pi)$ cannot increase in value by more than $\epsilon$ along every possible local direction $\delta=(\delta_{1},\dots,\delta_{n})$ that is feasible (namely $\pi+\delta$ is also a policy profile).

Let $\epsilon\geq 0$, and let $\pi$ be an $\epsilon$-stationary point of $\Phi$ (see Definition 4). Then, it holds that $\pi$ is a $\frac{\sqrt{S}D\epsilon}{1-\gamma}$-Nash policy.

To prove Lemma 4.2, we will need the Gradient Domination property that has been shown to hold in single-agent MDPs . This is presented in Lemma 4.3.

Let $\mathcal{G}$ be a MPG with potential function $\Phi$, fix any agent $i\in\mathcal{N}$, and let $\pi=(\pi_{i},\pi_{-i})\in\Delta(\mathcal{A})^{S}$ be a policy. Let $\pi_{i}^{*}$ be an optimal policy for agent $i$ in the single agent MDP in which the rest of the agents are fixed to choose $\pi_{-i}.$ Then, for the policy $\pi^{*}=(\pi^{*}_{i},\pi_{-i})\in\Delta(\mathcal{A})^{S}$ that differs from $\pi$ only in the policy component of agent $i$, it holds that

for any distributions $\mu,\rho\in\Delta(\mathcal{S})$.

Intuitively, Lemma 4.3 implies that there is a best response structure in the agents’ updates that we can exploit to show convergence of (projected) policy gradient to a Nash policy profile. In particular, given a fixed policy profile of all agents other than $i$, the decision of agent $i$ is equivalent to the decision of that agent in a single MDP. Thus, the following inequality (which stems directly from the gradient domination property in the single MDP)

implies that any stationary point of $V_{s}^{i}$ (w.r.t the variables $x_{i,s,a}$ of agent’s $i$ policy with the rest of the variables being fixed) is an optimal policy for $i$, i.e., a best response given the policies of all other agents.

Lemma 4.3 also suggests that there is an important difference in the Gradient Domination Property between (multi-agent) MPGs and single agent MDPs (cf. Lemma 4.1 in ). Specifically, for MPGs, the value (of each agent) at different Nash policies may not be uniqueThis is in contrast to single-agent MDPs for which the agent has a unique optimal value even though their optimal policy may not necessarily be unique. which implies that the gradient domination property, as stated in Lemma 4.3, will only be enough to guarantee convergence to one of the optimal (stationary) points of $\Phi$ (and not necessarily to the absolute maximum of $\Phi$). Having all these in mind, we can now prove Lemma 4.2.

Fix agent $i$ and suppose that $i$ deviates to an optimal policy $\pi^{*}_{i}$ (w.r.t the corresponding single agent MDP). Since $\pi$ is $\epsilon$-stationary it holds that (Definition 4)

Thus, with $\pi^{*}=(\pi^{*}_{i},\pi_{-i})$, Lemma 4.3 implies that

Thus, using the definition of the potential function (cf. Definition 2), we obtain that

Since the choice of $i$ was arbitrary, we conclude that $\pi$ is an $\frac{\sqrt{S}D\epsilon}{1-\gamma}$-approximate Nash policy. ∎

The last critical step before we proceed to the formal statement and proof of Theorem 1.1 is that the potential function $\Phi$ is smooth. This fact is used in the analysis of both (PGA) and its stochastic counterpart (PSGA).

Let $A_{\max}:=\max_{i\in\mathcal{N}}|\mathcal{A}_{i}|$ (the maximum number of actions for some agent). Then, for any initial state $s_{0}\in\mathcal{S}$ (and hence for every distribution $\mu\in\Delta(\mathcal{S})$ on states) it holds that

i.e., $\Phi_{\mu}(\pi)$ is $\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$-smooth.

Importantly, $A_{\max}:=\max_{i\in\mathcal{N}}|\mathcal{A}_{i}|$, i.e., the maximum number of actions for some agent, scales linearly in the number of agents.

Exact gradients case.

We are now ready to prove Theorem 1.1 (restated formally), following standard arguments about (PGA). Recall that the global maximum among all values/utilities of agents must be at most one.

Let $\mathcal{G}$ be a MPG and consider an arbitrary initial state. Let also $A_{\max}=\max_{i}|\mathcal{A}_{i}|$, and set the number of iterations to be $T=\frac{16n\gamma D^{2}SA_{\max}\Phi_{\max}}{(1-\gamma)^{5}\epsilon^{2}}$ and the learning rate (step-size) to be $\eta=\frac{(1-\gamma)^{3}}{2n\gamma A_{\max}}$. If the agents run independent projected policy gradient (PGA) starting from arbitrarily initialized policies, then there exists a $t\in\{1,\dots,T\}$ such that $\pi^{(t)}$ is an $\epsilon$-approximate Nash policy.

The first step is to show that $\Phi$ is a $\beta$-smooth function, in particular, that $\nabla_{\pi}\Phi$ is $\beta$-Lipschitz with $\beta=\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$ as established in Lemma 4.4. Then, a standard ascent lemma for Gradient Ascent (see Lemma D.1 from ) implies that for any $\beta$-smooth function $f$ it holds that $f(x^{\prime})-f(x)\geq\frac{1}{2\beta}\left\|x^{\prime}-x\right\|^{2}_{2}$ where $x^{\prime}$ is the next iterate of (PGA). Applied to our setting, this gives

Thus, if the number of iterates, $T$, is $\frac{16n\gamma D^{2}SA_{\max}}{(1-\gamma)^{5}\epsilon^{2}}$, then there must exist a $1\leq t\leq T$ so that $\left\|\pi^{(t+1)}-\pi^{(t)}\right\|_{2}\leq\frac{\epsilon(1-\gamma)}{2D\sqrt{S}}$. Using a standard approximation property (see Lemma D.2), we then conclude that $\pi^{(t+1)}$ will be a $\frac{\epsilon(1-\gamma)}{D\sqrt{S}}$-stationary point for the potential function $\Phi$. Hence, by Lemma 4.2, it follows that $\pi^{(t+1)}$ is an $\epsilon$-Nash policy and the proof is complete. ∎

Finite sample case.

In the case of finite samples, we analyze (PSGA) on the value $V^{i}$ of each agent $i$ which (as was the case for PGA) can be shown to be the same as applying projected gradient ascent on $\Phi$. The key is to get an estimate of the gradient of $\Phi$ (3) at every iterate. Note that $1-\gamma$ now captures the probability for the MDP to terminate after each round (and it does not play the role of a discounted factor since we consider finite length trajectories). Lemma 4.6 argues that the estimator of equation (3) is both unbiased and bounded.

It holds that $\hat{\nabla}_{\pi_{i}}^{(t)}$ is an unbiased estimator of $\nabla_{\pi_{i}}\Phi$ for all $i\in\mathcal{N}$, that is

Moreover, for all agents $i\in\mathcal{N}$, it holds that

It is straightforward from Lemma D.4 and the equality of the partial derivatives between the value functions and the potential, i.e., $\nabla_{\pi_{i}}\Phi_{\mu}=\nabla_{\pi_{i}}V^{i}_{\mu}$ for all $i\in\mathcal{N}$ (see property P2 in Proposition B.1). ∎

We now state and prove part (b) of Theorem 1.1.

Let $\mathcal{G}$ be a MPG and consider an arbitrary initial state. Let $A_{\max}=\max_{i}|\mathcal{A}_{i}|$, and set the number of iterations to be $T=\frac{48(1-\gamma)A_{\max}\Phi_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}}$ and the learning rate (step-size) to be $\eta=\frac{\epsilon^{4}(1-\gamma)^{3}\gamma}{48nD^{2}A^{2}_{\max}S}$. If the agents run projected stochastic policy gradient (PSGA) starting from arbitrarily initialized policies and using $\alpha$-greedy parametrization with $\alpha=\epsilon^{2}$, then there exists a $t\in\{1,\dots,T\}$ such that in expectation, $\pi^{(t)}$ is an $\epsilon$-approximate Nash policy.

Let $\delta_{t}=\hat{\nabla}_{\pi}^{(t)}-\nabla_{\pi}\Phi_{\mu}(\pi^{(t)})$ and set $\lambda=\frac{(1-\gamma)^{3}}{2n\gamma A_{\max}}$ (the inverse of the smooth parameter in 4.4). Moreover, we set $y^{(t+1)}=P_{\Delta(\mathcal{A})^{S}}(\pi^{(t)}+\eta\nabla_{\pi}\Phi(\pi^{(t)}))$ ($y^{(t+1)}$ captures the next iterate of the projected (deterministic) gradient ascent).

We follow the analysis of Projected Stochastic Gradient Ascent for non-convex smooth-functions (see , Theorem 2.1) that makes use of the Moreau envelope. Let

(definition of Moreau envelope for our objective $\Phi$). From the definition of $\phi$ and a standard property of projection we get

Using the definition of Moreau envelope and the fact that $\Phi$ is $\frac{1}{\lambda}$-smooth (Lemma 4.4, after the parametrization, the smoothness parameter does not increase) we conclude that

Adding telescopically (11), dividing by $T$ and because w.l.o.g $-\Phi\in$, we get that

Let $t*$ be the time index that minimizes the above. We show the following inequality (which provides a lower bound on the RHS of (12):

Observe that by $\frac{1}{\lambda}$-smoothness of $\Phi_{\mu}$ we get that $H(x):=-\Phi_{\mu}(x)+\frac{1}{\lambda}\left\|x-\pi^{(t*)}\right\|_{2}^{2}$ is $\frac{1}{\lambda}$-strong convex and moreover $y^{(t+1)}$ is the minimizer of $H$. Therefore we get that

By taking expectation of terms above, (13) follows. Combining (12) with (13) we conclude that

To get an $\epsilon$-Nash policy, we have to bound $\left\|y^{(t*+1)}-\pi^{(t*)}\right\|_{2}\leq\frac{\epsilon(1-\gamma)}{2D\sqrt{S}(2+\sqrt{nA_{max}})}$ and choose $\alpha=\epsilon^{2}$ in the greedy parametrization. This is true because of Lemma D.3 Lemma 4.2. Hence, we need to choose $\eta,T$ so that

We conclude that $\eta$ can be chosen to be $\frac{\epsilon^{4}(1-\gamma)^{3}\gamma}{48nD^{2}A^{2}_{\max}S}$ and $T$ to be $\frac{48(1-\gamma)A_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}}.$ ∎

Using Markov’s inequality, it is immediate to show that the statement of Theorem 4.7 holds with high probability. Namely, if we set the number of iterations to be $T=\frac{48(1-\gamma)A_{\max}D^{4}S^{2}}{\epsilon^{6}\gamma^{3}\delta^{4}}$ and the learning rate (step-size) to be $\eta=\frac{\epsilon^{4}(1-\gamma)^{3}\gamma\delta^{2}}{48nD^{2}A^{2}_{\max}S}$, where $\delta\in(0,1)$, then with probability $1-\delta$ there exists a $t\in\{1,\dots,T\}$ such that $\pi^{(t)}$ is an $\epsilon$-approximate Nash policy. However, this is a weaker than desired statement, since, optimally, the running time should be logarithmic in $1/\delta$, (and not polynomial as above) . Proving such a statement though requires bounds on the higher moments of the gradient estimator (to apply martingale arguments and concentration inequalities with exponential bounds) which we could not derive using current techniques (cf. Lemma 2 in ). Such a bound would be possible if we sample multiple trajectories and take the average (per iteration).

We conclude this section by giving a remark on Weighted and Ordinal MPGs (cf. Definition in 1). It is rather straightforward to see that our results carry over for weighted MPGs. The only difference in the running time of (PGA) is to account for the weights (which are just multiplicative constants).

In contrast, the extension to ordinal MPGs is not immediate and the reason is that we cannot prove any bound on the smoothness of $\Phi$ in that case (i.e., we cannot generalize Lemma 4.4). Therefore, we cannot have rates of convergence of policy gradient. Nevertheless, it is quite straightforward that (PGA) converges asymptotically to critical points (in bounded domains) for differentiable functions. Therefore as long as $\Phi$ is differentiable, it is guaranteed that asymptotically (PGA) will converge to a critical point of $\Phi$. By Lemma 4.2, this point will be a Nash policy.

Experiments: Congestion Games

We next study the performance of the policy gradient algorithm in a general class of MDPs that are congestion games at every state, .

We consider a MDP in which every state is a congestion game (cf. ). In the current experiment, there are $N=8$ agents, $A_{i}=4$ facilities (resources or locations) that the agents can select from and $S=2$ states: a safe state and a distancing state. In both states, all agents prefer to be in the same facility with as many other agents as possible (follow the crowd) . In particular, the reward of each agent for being at facility $k$ is equal to a predefined positive weight $w_{k}^{\text{safe}}$ times the number of agents at $k=A,B,C,D$. The weights satisfy $w_{A}^{\text{safe}}<w_{B}^{\text{safe}}<w_{C}^{\text{safe}}<w_{D}^{\text{safe}}$, i.e., facility $D$ is the most preferable by all agents. However, if more than $4=N/2$ agents find themselves in the same facility, then the game transitions to the distancing state. At the distancing state, the reward structure is the same for all agents, but reward of each agent is reduced by a constant amount, $c$, where $c>0$ is a (considerably large) constant. (We also treat the case in which $c$ is different for each facility in Appendix E). To return to the safe state, the agents need to achieve maximum distribution over the facilities, i.e., no more than $2=N/4$ agents may be in the same facility. We consider deterministic transitions, however, the results are quantitatively equivalent also when these transitions occur with some probability (see Appendix E). The MDP is illustrated in the upper left panel of Figure 4.

Paremeters:

We perform episodic updates with $T=20$ steps. At each iteration, we estimate the Q-functions, the value function, the discounted visitation distributions and, hence, the policy gradients using the average of mini-batches of size $20$. We use $\gamma=0.99$. For the presented plots, we use a common learning rate $\eta=0.0001$ (upper panels) or randomly generated learning rates (different for each agent) in $[.00005,.0005]$ (lower panels) in Figure 4. Note that these learning rates are (several orders of magnitude) larger than the theoretical guarantee, $\eta=\frac{(1-\gamma)^{3}}{2\gamma A_{\max}n}\approx 1e-08$, of Theorem 4.5. Experiments (not presented here) with even larger learning rates (e.g., $\eta=0.001$) did not lead (consistently) to convergence.

Results:

The lower left panel of Figure 4 shows that the agents learn the expected Nash profile in both states in all runs (this is common for both the fixed and the random learning rates). At the safe state, the agents distribute themselves equally among the two most preferable facilities (C and D). This leads to a maximum utility and avoids a transition to the distancing (bad) state. At the distancing state, the agents learn the unique distribution (2 agents per facility) that leads them back to the safe state. Importantly, this (Nash) policy profile to which policy gradient converges to is deterministic in line with Theorem 4.5. The panels in the middle and right columns depict the L1-accuracy in the policy space at each iteration which is defined as the average distance between the current policy and the final policy of all $8$ agents, i.e., $\text{L1-accuracy}=\frac{1}{N}\sum_{i\in\mathcal{N}}|\pi_{i}-\pi_{i}^{\text{final}}|=\frac{1}{N}\sum_{i\in\mathcal{N}}\sum_{s}\sum_{a}|\pi_{i}(a\mid s)-\pi_{i}^{\text{final}}(a\mid s)|.$ The results are qualitatively equivalent in both cases (common and non-common learning rates). However, due to the larger step-sizes used by some agents, the algorithm becomes more responsive and exhibits faster convergence in the non-common case.

Further Discussion and Conclusions

In this paper, we have presented a number of positive results (both structural and algorithmic) about the performance of independent policy gradient ascent in Markov potential games. Specifically, deterministic Nash policies always exist and independent policy gradient is guaranteed to converge (polynomially fast in the approximation error) to a Nash policy profile even in the case of finite samples. Given these positive results, a number of interesting open questions emerge.

Price of (Markov) Anarchy. Price of Anarchy (PoA) is a classic notion in normal form games that captures the inefficiency due to the lack of a central authority that would coordinate all agents to implement the social optimum outcome. Formally, it is defined as the ratio of the social cost of the worst Nash equilibrium divided by the cost of the social optimum. PoA has been studied extensively in many classes of games including several classes of potential games for which tight PoA bounds exist (e.g. congestion games ). It would be interesting to explore to what extent this type of analysis can be generalized to Markov Potential Games as well as more general classes of Markov Games.

Stability of Deterministic Policies. When it comes to online learning in normal form potential games, it is sometimes possible to prove that the dynamics do not converge to an arbitrary Nash equilibrium, but, in fact, that most initial conditions converge to a deterministic (sometimes referred to also as pure) Nash equilibrium . To produce such equilibrium selection results, standard Lyapunov arguments do not suffice and one needs to apply more advanced techniques such as the Center-Stable-Manifold theorem which would be a fascinating direction for future work in MPGs.

Other Algorithmic Approaches: Softmax Parametrization & Natural Policy Gradient. In , the authors show asymptotic convergence to the global optimum to single-agent MDP in the tabular setting with exact gradients for the softmax policy parameterization. Moreover, polynomial convergence rate is shown when additional KL-based entropy regularizer is used, as well as dimension-free convergence to optimum when Natural Policy Gradient is applied. Extending such algorithmic techniques to the case of multi-agent MPGs is a natural direction for future work.

Global Convergence in other Multi-Agent Markov Games. Recently, there has been intense interest in understanding convergence to Nash policies for different classes of learning dynamics in Markov zero-sum games . Our approach moves in orthogonal direction focusing on MPGs and establishing strong convergence results in these games. A natural open question is whether and under what conditions can we prove strong convergence guarantees in more general classes of Markov games, possibly by combining tools and techniques from both lines of work.

Regularities beyond Equilibration in Multi-Agent Markov Games. Given the complexities of such multi-agent settings, it is highly unlikely to expect practical algorithms which can always guarantee convergence to equilibrium. This is already the case even for the more restricted setting of normal-form games . Nevertheless, strong guarantees can be shown via, e.g., existence of cyclic/recurrent orbits, invariant functions or strong social welfare guarantees . Whether such results can be extended to Multi-Agent Markov Games is a stimulating direction for future work.

Acknowledgements

This project is supported in part by NRF2019-NRF-ANR095 ALIAS grant, grant PIE-SGP-AI-2018-01, NRF 2018 Fellowship NRF-NRFF2018-07, AME Programmatic Fund (Grant No. A20H6b0151) from the Agency for Science, Technology and Research (A*STAR) and the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: AISG2-RP-2020-016).

References

Appendix A Additional Notation and Definitions: Section 2

We first provide some additional notation and definitions that will be used in the proofs.

Discounted State Distribution.

It will be useful to define the discounted state visitation distribution $d_{s_{0}}^{\pi}(s)$ for $s\in\mathcal{S}$ that is induced by a (joint) policy $\pi$ as

Appendix B Omitted Materials: Section 3

Let $\mathcal{G}=(\mathcal{S},\mathcal{N},\mathcal{A}=\{\mathcal{A}_{i}\}_{i\in\mathcal{N}},P,R,\rho)$ be a Markov Potential Game (MPG) with potential $\Phi_{s}$, for $s\in S$. Then, for the value function $V_{s}^{i},s\in\mathcal{S}$ of each agent $i\in\mathcal{N}$, the following hold

Equality of Derivatives: the partial derivatives of agent $i$’s value function $V^{i}_{s}$ coincide with the partial derivatives of the potential $\Phi_{s}$ that correspond to agent $i$’s parameters, i.e.,

To obtain P1, consider any 3 arbitrary policies for agent $i$, notated by $\pi_{i},\pi_{i}^{\prime},\pi_{i}^{\prime\prime}\in\Delta(\mathcal{A}_{i})^{S}$. Then, by the definition of MPGs, we have that

for every starting state $s\in\mathcal{S}$. This implies that we can write $V^{i}_{s}(\pi_{i},\pi_{-i})$ as both

Thus, we have that $-\Phi_{s}(\pi_{i}^{\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime},\pi_{-i})=-\Phi_{s}(\pi_{i}^{\prime\prime},\pi_{-i})+V^{i}_{s}(\pi_{i}^{\prime\prime},\pi_{-i})$ for any arbitrary pair of policies $\pi_{i}^{\prime}$ and $\pi_{i}^{\prime\prime}$ for agent $i$, implying that agent $i$’s policy has no impact on these terms. Accordingly, we can express them as

where $U^{i}_{s}(\pi_{-i})$ is a function that does not depend on the policy of agent $i$. Thus, we can express the utility function of any agent $i$ in a MPG as

as claimed. To obtain P2, we use P1 for a vector $x_{i}$ parameterizing $\pi_{i}$, and obtain that

for any coordinate $x_{i,a}$ with $a\in A_{i}$ of $x_{i}$, from which we can see that our claim is true. ∎

Note that P1 serves as a characterization of MPGs. Namely, a multi-agent MDP is a MPG if and only if the value function of each agent $i\in\mathcal{N}$ can be decomposed in a term that is common for all players (potential function) and in a term that may be different for each agent $i\in\mathcal{N}$ but which depends only on the actions of all agents other than $i$. This property carries over from normal form (single state) potential games. Also note that both properties, P1 and P2, hold for any (differentiable for P2) policy parameterization and not only for the direct one that we use here.

Let $\Phi$ be the potential function of $\mathcal{G}$. Since the space $\Delta(\mathcal{A})^{S}=\Delta(\mathcal{A}_{1})^{S}\times...\times\Delta(\mathcal{A}_{n})^{S}$ is compact and $\Phi$ is continuous, $\Phi$ has a global maximum $\Phi_{\max}$. Let $(\pi_{1}^{*},...,\pi_{n}^{*})$ denote a global maximizer, i.e., a joint policy profile at which $\Phi_{\max}$ is attained. By the Definitions of MPGs and Nash policies, this implies, in particular, that $(\pi_{1}^{*},...,\pi_{n}^{*})$ is a Nash policy, since

The proof is constructive and proceeds by finding the potential function, $\Phi_{s},s\in\mathcal{S}$ in both cases, C1-C2. Since the individual rewards of the agents at each state $s\in\mathcal{S}$ are captured by a potential function $\phi_{s}$, then for the reward, $R_{i}(s,\mathbf{a})$ of each agent $i$ at the action profile $\mathbf{a}$, it holds that

If the transitions do not depend on the action of the players, we have that $\tau\sim P$, where $P$ is an exogenously given distribution function (state-wise). In this case, we have that

Under the assumptions of condition C2, we will show that again

is a potential function for $G$ and that the same decomposition as in condition C1 of the value function of agent $i$ in a common and a dummy term applies. To see this, let $\pi_{i},\pi_{i}^{\prime}\in\Pi_{i}$ be two policies of agent $i$ and let $\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})$ where $\pi_{-i}$ is the fixed policy of all agents other than $i$. Then, using (B), we have that

Using the intermediate value theorem, there exists a policy $\xi_{i}$ which is a convex combination of $\pi_{i},\pi_{i}^{\prime}$ such that

Since $\pi_{i},\pi_{i}^{\prime}$ correspond to probability distributions at every state $s\in\mathcal{S}$, their difference is equal to (state-wise). In turn, the displayed condition in C2 implies that

which is enough to ensure that the dot product in the previous equation is equal to and the claim follows.

Summing up, in both cases, C1-C2, $\mathcal{G}$ is an MPG as claimed. ∎

Note that the proof of the (trivial) case in which the instantaneous rewards of all agents $i\in\mathcal{N}$ are equal at each state $s\in\mathcal{S}$ (cf. Remark 2) is similar. In this case, it is immediate to see that the instantaneous rewards are precisely given by the potential function at that state, i.e., it holds that $R_{i}(s,\mathbf{a})=\phi_{s}(\mathbf{a})$ for all $i\in\mathcal{N}$ and all $s\in\mathcal{S}$. In this case, it holds that $u_{s}^{i}(\mathbf{a}_{-i})\equiv 0$ for all $i\in\mathcal{N}$ and all $s\in\mathcal{S}$ and hence,

is a potential function for $G$, and the dummy terms are all equal to , i.e., $U_{s}^{i}(\pi_{-i})\equiv 0$.

At each state, $s\in\{0,1\}$, the agents’ payoffs, $(R_{s}^{1},R_{s}^{2})$, form a potential game (at that state), and are given as follows

In this MDP, agents need only to select an action at state $s_{0}$. Thus, we will denote a policy, $\pi_{1}$, of agent $1$ by $\pi_{1}=(p,1-p)$ where $p\in$ is the probability with which agent $A$ selects action at state $s_{0}$. Similarly, we will denote a policy, $\pi_{2}$, of agent $B$ by $\pi_{2}=(q,1-q)$ where $q\in$ is the probability with which agent $B$ selects action at state $s_{0}$. Moreover, we will slightly abuse notation and write

We also assume that the horizon is infinite and there is a discount factor $\gamma\in[0,1)$. Accordingly, we can calculate the value functions $V_{0}^{i}(\pi_{1},\pi_{2})$ of agents $i=A,B$ starting from state $s_{0}$ as follows,

Next, we use the Performance Difference Lemma (Lemma 3.2 by ) to determine the difference in the value between two different policies. We will do this for agent $1$ (the calculation is similar for agent $2$: we use here $1$ for agent 1 and 2 for agent $B$). For a policy $\pi=(\pi_{1},\pi_{2})$, we have at state $s_{0}$ that

At state $s_{1}$, there is only one available action for each agent which yields a payoff of . Thus,

Moreover, concerning the discounted visitation distribution, we have that

and $d^{\pi}_{0}(s_{1})=1-d^{\pi}_{0}(s_{0})=\frac{\gamma(1-pq)}{1-\gamma pq}$. Thus, using all the above, we have that

which shows that our initial calculations conform with the outcome specified by the Performance Difference Lemma.

Finally, a direct calculation shows that $\Phi_{s}=\phi_{s}$ for $s=0,1$ is a valid potential function for which the MDP is an ordinal MPG.

At state $s_{0}$, we consider the game with action sets $A_{1}(s_{0})=A_{2}(s_{0})=\{H,T\}$ and (instantaneous) payoffs

where $a_{1}$ denotes the action of agent $1$ and $a_{2}$ the action of agent $2$ (agent $1$ selects rows and agent $2$ selects columns in both matrices). This is a constant sum game (equivalent to zero-sum) and hence, it is not an (ordinal) potential game. Apart from the instantaneous rewards, agents’ actions at $s_{0}$ induce a deterministic transition to a state in which the only available actions to the agents are precisely the actions that they chose at state $s_{0}$ and their instantaneous rewards at this state are the rewards of the other agent at $s_{0}$. In particular, there are four possible transitions to states $s_{ab}$ with $a,b\in\{H,T\}$, with action sets and instantaneous rewards given by

for agents 1 and 2, respectively. Note that the visitation probability of this states is equal to the visitation probability of state $s_{0}$. After visiting one of these states, the MDP transitions to state $s_{1}$ which is a potential game, with potential function given by

As mentioned above, the game in state $s_{0}$ does not admit a potential function. However, the joined rewards $RJ_{1},RJ_{2}$ of agents $1$ and $2$ which result from selecting an action profile $(a,b)\in{H,T}^{2}$ at $s_{0}$ and then traversing both $s_{0}$ and the ensuing $s_{ab}$ (part included in the dotted rectangle in Figure 3), do admit a potential function. The potential function in this case is the sum of agents’ rewards and is given by

Let $\pi_{1}=(\mathbf{x}_{0},\mathbf{x}_{1})$ denote a policy of agent $1$. Here $\mathbf{x}_{0}=(x_{0},1-x_{0})$, where $x_{0}\in$ is the probability with which agent $1$ chooses action $H$ at state $s_{0}$. Similarly, $\mathbf{x}_{1}=(x_{1},1-x_{1})$ where $x_{1}\in$ is the probability with which agent $1$ chooses action $L$ at state $s_{1}$. At states $s_{ab},a,b\in\{H,T\}^{2}$, agents only have one action to choose from, so this choice is eliminated from their policy representation. Similarly, we represent a policy of agent $2$ by $\pi_{2}=\left(\mathbf{y}_{0},\mathbf{y}_{1}\right)$ with $y_{0},y_{1}\in$. Let also

In the general case, $p_{0}$, i.e., the transition probability from $s_{1}$ to $s_{0}$, may depend on the actions of the agents or it may be completely exogenous (i.e., constant with respect to agents’ actions). If we write

to denote the probability of transitioning from state $s_{1}$ to state $s_{0}$ given that the agents chose actions $a_{1},a_{2}\in\{L,R\}$ at state $s_{1}$, then we can write $p_{0}$ as

Using this notation, we can now proceed to compute the value function of each state of the MDP in Figure 3. Since the value of states $s_{a,b},a,b\in{H,T}^{2}$ is equal to a constant reward plus the value of state $s_{1}$ (discounted by $\gamma$), it suffices to calculate the value for states $s_{0}$ and $s_{1}$. We have that

This is a system of $2$ equations in the $2$ unknown quantities, $V_{0}^{1}\left(\pi_{1},\pi_{2}\right)$ and $V_{1}^{1}\left(\pi_{1},\pi_{2}\right)$. Solving for these two quantities, yields the unique solution

In the case that $p_{0}$ is a constant with respect to $\pi_{1},\pi_{2}$, then both value functions are of the form

where $c_{1}\left(s\right),c_{2}\left(s\right)>0$ are appropriate constants that depend only the state $s\in\{s_{0},s_{1}\}$ and on agents $1,2$. Since the game at $s_{1}$ is a potential game, with potential function given by a $2\times 2$ matrix $\Phi_{1}$, it is immediate to infer that

However, if $p_{0}$ depends on the actual policies of agents $1$ and $2$, cf. equation (19), then it is not immediate to determine a potential (or even to decide whether a (exact) potential exists or not).

Several elements of Example 3 have been selected in the sake of simplicity and are not necessary for the main takeaway, i.e., that there are MDP that are not potential at some states but which are MPGs. First, the transitions from $s_{0}$ to the states $s_{ab}$ need not be deterministic. To see this, let $q\in(0,1)$ and assume that if the agents select actions $H,T$ is $s_{0}$, then the process transitions with probability $q$ to a state $s_{HT}$ with rewards $(-1,1)/q\gamma$ and with probability $(1-q)$ to a state $s^{\prime}_{HT}$ with rewards $(1,-1)/(1-q)\gamma$. The rest remains the same. Accordingly, the expected reward for agent $1$ after $(H,T)$ has been selected in $s_{0}$ is the same as in the current format.

Second, the construction with states $s_{0}$ and $s_{ab},(a,b)\in{H,T}^{2}$ is not the only one that leads to such an example. Another very common instance occurs in the case of aliasing between $s_{0}$ and states $s_{ab}$, i.e., when the agents cannot tell these states apart. The intuition which carries over from the currently presented example is that the roles of the agents are essentially reversed between the two states but the agents do not know (from the observable features) in which state they are. Thus, any valid policy, selects the same action in both states leading to the same situation as in the presented example.

Finally, if the horizon is finite, then the instantaneous rewards in states $s_{ab}$ still work if we eliminate the scaling factor (here $\gamma$). Thus, the construction works in both episodic and continuing settings.

Appendix C Omitted Materials: Section 4

To prove Lemma 4.3, we will use a multi-agent version of the Performance Difference Lemma (cf. for a single agent and for two agents).

Consider an n-agent MDP $\mathcal{G}$ and fix an agent $i\in\mathcal{N}$. Then, for any policies $\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})\in\Pi$ and any distribution $\rho\in\Delta(S)$, it holds that

where $\mathbf{a}_{-i}\sim\pi_{-i}(\cdot\mid s)$ denotes the action profile of all agents other than $i$ that is drawn from the product distribution induced by their policies $\pi_{-i}=(\pi_{j})_{j\neq i\in\mathcal{N}}\in\Pi_{-i}$.

For any initial state $s\in\mathcal{S}$ and joint policies $\pi=(\pi_{i},\pi_{-i}),\pi^{\prime}=(\pi^{\prime}_{i},\pi_{-i})\in\Pi$, it holds that

Taking expectation over the states $s\in\mathcal{S}$ with respect to the distribution $\rho\in\Delta(\mathcal{S})$ yields the result. ∎

Fix an agent $i\in\mathcal{N}$ and let $\pi=(\pi_{i},\pi_{-i}),\pi^{*}=(\pi_{i}^{*},\pi_{-i})\in\Pi=\Delta(\mathcal{A})^{S}$. By the definition of MPGs (cf. Definition 2), it holds that

Thus, using the multi-agent version of the Performance Difference Lemma (cf. Lemma C.1), we have for any distribution $\mu\in\Delta(\mathcal{S})$ that

Thus, for any $\pi^{\prime}_{i}\in\Pi_{i}$ and any state $s\in\mathcal{S}$, it holds that

since $V^{i}_{s}(\pi)$ does not depend on $a_{i}$. Substituting back in the last inequality of the previous calculations, we obtain that

where we used the policy gradient theorem () under the assumption of direct policy parameterization (cf. equation (2)). We can further upper bound the last expression by using that $d^{\pi}_{\mu}(s)\geq(1-\gamma)\mu(s)$ which follows immediately from the definition of the discounted visitation distribution $d^{\pi}_{\mu}(s)$ for any initial state distribution $\mu$. Finally, property P2 of Proposition B.1, implies that $\nabla_{\pi_{i}}V^{i}_{\rho}(\pi)=\nabla_{\pi_{i}}\Phi_{\rho}(\pi)$ (making crucial use of the MPG structure). Putting these together, we have that

It suffices to show that the maximum eigenvalue in absolute value of the Hessian of $\Phi$ is at most $\frac{2n\gamma A_{\max}}{(1-\gamma)^{3}}$, i.e., that

We first prove the following intermediate claim.

Consider the symmetric block matrix $C$ with $n\times n$ matrices so that $\left\|C_{ij}\right\|_{2}\leq L$. Then, it holds that $\left\|C\right\|_{2}\leq nL$, i.e., if all block submatrices have spectral norm at most $L$, then $C$ has spectral norm at most $nL$.

We will prove the claim by induction on $n$. For $n=2$ we need to show that

if $\left\|C_{11}\right\|_{2},\left\|C_{12}\right\|_{2},\left\|C_{21}\right\|_{2},\left\|C_{22}\right\|_{2}\leq L.$ Define matrix $W$ to be

where $I$ is the identity matrix (of appropriate size). If we show that $W$ is positive semi-definite, then it follows that $W$ has only non-negative eigenvalues, which, in turn, implies that the spectral norm of $C$ is at most $2L$. To see this, set

$W_{1}$ is positive semi-definite as a block diagonal matrix with diagonal blocks positive semi-definite matrices. Moreover, by Schur complement we get that $W_{2}$ is positive semi-definite as long as $L\cdot I$ is positive semi-definite and $L\cdot I-\frac{1}{L}\cdot C_{12}C_{21}$ is positive semidefinite. By assumption, we have that

which implies that $L\cdot I-\frac{1}{L}\cdot C_{12}C_{21}$ has non-negative eigenvalues. Thus, $W_{2}$ is positive semi-definite. We conclude that $W_{1}+W_{2}$ is positive semi-definite (sum of positive semi-definite matrices is positive semi-definite) and the claim follows.

For the induction step, suppose that the claim holds for an $n=k-1\geq 2$. To establish that it also holds for $k$, we need to show that

as long as $\left\|C_{ij}\right\|_{2}\leq L$ for all $i,j$. Let $W=kL\cdot I-C$. To show that $W$ is positive semi-definite consider

By induction, it follows that $W_{2}$ is positive semi-definite. We need to show that the same holds for $W_{1}$. By Schur complement we obain that $W_{1}$ is positive semi-definite if and only if $kL\cdot I-C_{11}-\frac{1}{L}\sum_{i=2}^{k}C_{1i}C_{i1}$ is positive semi-definite. It follows that