A New Formalism, Method and Open Issues for Zero-Shot Coordination

Johannes Treutleinto,vector,equal
Michael Dennischai
Caspar Oesterheldduke
Jakob Foersterto,vector,face

toDepartment of Computer Science, University of Toronto, Toronto, Canada
vectorVector Institute, Toronto, Canada
dukeDepartment of Computer Science, Duke University, Durham, USA
faceFacebook AI Research, USA
chaiDepartment of Electrical Engineering and Computer Science, University of California, Berkeley, USA

Johannes<EMAIL_ADDRESS>
Multi-agent reinforcement learning, zero-shot coordination, Dec-POMDP isomorphism

*Part of the work was done as an intern at the Center for Human-Compatible AI, University of California, Berkeley

In many coordination problems, independently reasoning humans are able to discover mutually compatible policies. In contrast, independently trained self-play policies are often mutually incompatible.
Zero-shot coordination (ZSC) has recently been proposed as a new frontier in multi-agent reinforcement learning to address this fundamental issue.
Prior work approaches the ZSC problem by assuming players can agree on a shared learning algorithm but not on labels for actions and observations, and proposes other-play as an optimal solution.
However, until now, this “label-free” problem has only been informally defined.
We formalize this setting as the label-free coordination (LFC) problem by
defining the label-free coordination game.  We show that other-play is not an optimal solution to the LFC problem as it fails to consistently break ties between incompatible maximizers of the other-play objective.  We introduce an extension of the algorithm, other-play with tie-breaking, and prove that it is optimal in the LFC problem and an equilibrium in the LFC game. Since arbitrary tie-breaking is precisely what the ZSC setting aims to prevent, we conclude that the LFC problem does not reflect the aims of ZSC. To address this, we introduce an alternative informal operationalization of ZSC as a starting point for future work.

§ INTRODUCTION

In multi-agent reinforcement learning (MARL), variations of the
self-play (SP) regime [][]tesauro1994td have been successful in producing superhuman policies for two-player zero-sum games such as chess, go, and poker campbell2002deep,silver2017mastering,brown2018superhuman. SP leads to policies that are highly adapted to each other and thus often appear artifical.
This is not a problem in two-player zero-sum games as all optimal policies are interchangeable nash1951non, at least when considering optimal opponents.

In fully cooperative MARL, however, such arbitrary conventions can be undesirable, as they fail when paired with agents that were not present during SP training. For instance, consider a situation in which robots must avoid collisions, by either swerving right or left or slowing down to avoid the other robot. Here, robots trained via SP would randomly learn to swerve either left or right and thus crash half the time at test time when paired in cross-play (XP) with agents from independent training runs. Similarly, the arbitrary conventions learned by agents, e.g., in the card-game Hanabi, can prevent successful human-AI coordination [][]foerster2019bayesian,carroll2019utility.

Rewards in the lever coordination game. Levers with equal rewards cannot be distinguished without labels.

This shortcoming of SP in fully cooperative problems motivates the study of the zero-shot coordination (ZSC) problem, which hu2020other operationalize as finding a general-purpose learning algorithm that allows independently trained agents to coordinate successfully at test time. The independent training is a proxy for the independent decision making that humans have to undertake when solving coordination tasks, while the ability to agree on an algorithm corresponds to having a common high-level approach for solving these problems.

More specifically, hu2020other assume that players only agree on a learning algorithm, but without sharing labels for observations, actions, and states in the environment. As an example, consider the lever coordination game in Figure <ref>. There are two agents, each having the choice between \(10\) different levers. If both agents choose the same lever, they receive rewards as specified in Figure <ref>. There is \(1\) lever with a reward of \(0.9\) and \(9\) levers with reward \(1\). If agents pull different levers, the reward is \(0\). Here, the SP algorithm will learn a joint policy wherein  one lever of the nine with a reward of \(1\) is played by both agents, but such a policy cannot be coordinated on without labels for levers.

hu2020other suggest the other-play (OP) algorithm as a solution and give an informal optimality proof. The idea behind the algorithm is that it learns policies that are robust to permutations by symmetries of a given problem. For example, in the lever coordination game, the actions leading to a reward of \(1\) are all symmetric, so a randomly permuted policy will pick them with equal probability. In contrast, the lever leading to a payoff of \(0.9\) does not have symmetric counterparts, so it is possible to consistently choose that lever. hu2020other show that in Hanabi, OP improves performance over SP when playing with real humans, showing the benefits of ZSC to human-AI coordination. However, hu2020other do not formalize the “no labels” assumption, but rely on an intuitive notion in their proof. Moreover, hu2020other's proof relies implicitly on the assumption that the  OP algorithm's objective has a unique maximizer.

Illustration of the LFC problem. A learning algorithm trains agents independently in a randomly chosen LFC game. The use of different controllers by red and blue agents symbolizes that, while the agents can separately coordinate on policies during train time, they do not know the labels used by agents of the other color and cannot coordinate with them before test time.

The first goal of this paper is a formalization of hu2020other's problem setting and a theoretical analysis of OP (Section <ref>). To do so, we introduce label-free coordination (LFC) games and define the label-free coordination problem as finding an optimal algorithm to recommend to players in a random LFC game (Section <ref>). The formalization provides a rigorous optimality criterion that can be used to compare OP to other algorithms theoretically and to discuss whether hu2020other's formulation is aligned with the goal of human-AI coordination. After introducing a generalized version of the OP algorithm (Section <ref>), we show that OP can be suboptimal in the LFC problem, as hu2020other's assumption of a unique maximizer is not always fulfilled (Section <ref>).
Our findings suggest that the 8 point gap between the SP and XP scores for the vanilla version of OP in Hanabi hu2020other may be due to fundamental problem with the algorithm instead of an optimization issue.

Second, we fix this shortcoming by introducing an extension of the algorithm, OP with tie-breaking, in which players use a tie-breaking function to consistently break ties between different OP-optimal policies (Section <ref>). We prove that this extension is an optimal solution to the LFC problem and that all players using the algorithm is a Nash equilibrium of any LFC game.

Third, we verify our results experimentally in two toy examples (Section <ref>). Our examples are stylized coordination problems that abstractly model real-world coordination problems.

Fourth, we argue that the operationalization of the ZSC problem by hu2020other does not reflect ZSC's aims, and we suggest a new operationalization as a starting point for future work (Section <ref>). Despite the “no labels” assumption, an optimal algorithm for the problem implements arbitrary tie-breaks. While there may be some settings where it is feasible to pre-coordinate on a tie-breaking function, in general, arbitrary tie-breaking is precisely what the ZSC setting aims to prevent. This shows that algorithmic advances towards hu2020other problem formulation are misaligned with the overarching goals of ZSC. We propose an improved informal operationalization in which players are allowed to coordinate only on high-level ideas for a learning algorithm but are prohibited from sharing implementation details such as random seeds, parameters, or code. We leave it to future work to refine and address this revised definition of ZSC.

To save space, we give informal statements and explanations of our theoretical results in the main text. A rigorous treatment of all results, including formal statements and proofs, can be found in the appendix. Our two main results are stated and proven in Appendices <ref> and <ref>.

§ RELATED WORK

Game theory A closely related problem to ZSC is the equilibrium selection problem in game theory [see][]harsanyi1988general, which arises when there are different equilibria in a game. The ZSC problem arises when there is an equilibrium selection problem between different optimal policies in a fully cooperative game. Equilibrium selection problems can introduce the additional difficulty that players can have different preferences over the equilibria.

[Harsanyi & Selten, 1988] ([Harsanyi & Selten, 1988]; see [Harsanyi, 1975], [Harsanyi, 1975]) introduce a general solution to the equilibrium selection problem in the framework of standard-form games, and herings2003equilibrium have adapted it to stochastic games. One property of this solution is invariance to isomorphisms between games, which, like the LFC problem, is based on the idea that a solution should not depend on arbitrary labels [][ch. 3.4]harsanyi1988general. A difference to our setting is that we are interested in practical algorithms that can be run on large-scale games, for which computing harsanyi1988general's solution would be infeasible [cf.][]goldberg2013complexity,herings2002computation. Another difference is that standard-form games have less structure than Dec-POMDPs. We explicate this and compare our approaches in more detail in Appendix <ref>.

Another game-theoretic approach to coordination problems is based on exogenous information about agents' options. For instance, consider the famous problem “you lost your friend in New
York City, where are you going to meet?” schelling1980strategy,mehta1994nature. Here, additional meaning is attached to each option, independent of dynamics and rewards of the problem, which allows for picking a unique option. Agents might also be able to choose options based on social conventions and norms, such as which side of the street to drive on lewis2008convention.
In this work, we instead restrict our attention to coordination-problem solutions based only on endogenous information present in the abstract structure of the problem. In many settings, conventions need to be introduced and adapted to within an episode at test time, rather than coordinating them beforehand, e.g., via joint training.

Coordination without joint training Some work looks at coordination problems in settings that do not assume  agents are trained together. For instance,
boutilier1999sequential introduces a dynamic programming algorithm for fully observable, fully cooperative stochastic games, where no prior coordination between agents is possible.
Agents randomize between different optimal actions in a given state until they succeed on coordinating on an optimal joint action.
goldman2007learning consider the Dec-POMDP setting with a cheap-talk channel in which agents cannot pre-coordinate on strategies. They introduce an algorithm in which agents learn to interpret each others' messages and use them to communicate observations and to suggest actions to coordinate on. The idea behind ZSC is to learn joint policies that implement similarly robust strategies as the above approaches, without having to explicitly specify such behavior.

Another related approach is ad-hoc teamwork, wherein the goal is to train an agent to perform well in expectation when subbed into a randomly chosen team of agents stone2010ad,barrett2011empirical,barrett2015cooperating. Ultimately, this amounts to learning a best response to a distribution over team members. However, the team members’ policies may themselves be ill-suited for coordination, e.g., if they are obtained via SP. ZSC instead assumes that all agents are optimized for being able to coordinate well, in the absence of pre-established conventions (even though, as mentioned above, optimal ZSC policies in many settings introduce conventions within an episode). It can thus find entirely different equilibria, ones that achieve good performance and can be consistently coordinated upon without SP training. As an example, consider the lever coordination game from the introduction. Optimal ad-hoc agents, trained as a best response to a population of SP agents would learn to uniformly randomize between the levers with a payoff of 1.0, while an optimal policy for ZSC always plays the unique lever with a payoff of 0.9.

Alternatively, an agent may be trained using data about other agents' behavior in order to learn a compatible strategy offline lerer2019learning,tucker2020adversarially. This again differs from ZSC in that it is concerned with learning a best response instead of optimizing all agents to find non-arbitrary equilibria. Similarly, human-AI coordination can be improved by training agents as a best response to a human model carroll2019utility. Human-AI coordination is also an aim of ZSC, but we try to uncover general principles behind a human-like learning algorithm instead of learning problem-specific policies from human models.

§ BACKGROUND

We consider decentralized partially observable Markov decision problems (Dec-POMDPs) nair2003taming,oliehoek2016concise.
A (finite-horizon) Dec-POMDP \(\DecP\) is a tuple of

a set of agents $\mathcal{N}=\{1,\dots,N\}$ where \(N\in\mathbb{N}\), a finite set of states $\StateSet$, a set of joint actions \(\ActionSet:=\prod_{i\in \PlayerSet}\ActionSet_{i}\), where $\ActionSet_{i}$ is a finite set of actions for agent $i\in\PlayerSet$, a transition probability kernel $P\colon\StateSet\times\ActionSet\rightarrow\Delta(\StateSet)$, where $\Delta(\StateSet)$ denotes the
set of probability distributions over $\StateSet$, a reward function $\RewardFunction\colon\StateSet\times\ActionSet\rightarrow\mathbb{R}$, a set of joint observations \(\ObservationSet:=\prod_{i\in \PlayerSet}\ObservationSet_{i}\), where $\ObservationSet_{i}$ is a finite set of observations for agent $i\in\PlayerSet$, an observation probability kernel $O\colon\StateSet\times\ActionSet\rightarrow\Delta(\ObservationSet)$, an initial state distribution $b_{0}\in\Delta(\StateSet)$, and a horizon $\Tmax\in\mathbb{N}_0$.
We write \(\ActionSet^\DecP,\ActionSet^\DecPSecond\), etc. to indicate which Dec-POMDP \(\DecP\), \(\DecPSecond\), etc. a set or function belongs to.

In a Dec-POMDP, at time step \(1\leq t\leq \Tmax\), the environment is in a state \(\StateRV_t\), agent \(i\in\PlayerSet\) receives observations \(\ObservationRV_{i,t}\) via \((\ObservationRV_{j,t})_{j\in\PlayerSet}\sim O(\cdot\mid\StateRV_{t},\ActionRV_{t-1})\) and
chooses an action \(\ActionRV_{i,t}\sim \Policy_i(\cdot\mid \AOHistoryRV_{i,t})\) according to a local policy \(\Policy_i\in\PolicySet_i\), where \(\AOHistoryRV_{i,t}:=(\ActionRV_{i,0},\ObservationRV_{i,1},\dotsc,\ActionRV_{i,t-1},\ObservationRV_{i,t})\) is a random variable for agent \(i\)'s action-observation history at step \(t\), with values \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}:=\left(\ActionSet_{i}\times\ObservationSet_{i}\right)^t\).[In a slight abuse of notation, we use \(\ObservationRV\) for both observation probabilities and observation random variable.]
Agents receive a joint reward \(\RewardRV_t:=\RewardFunction(\StateRV_t,\ActionRV_t)\) and the environment transitions into a state \(\StateRV_{t+1}\sim P(\cdot\mid \StateRV_t,\ActionRV_t)\). The initial state is \(\StateRV_0\sim b_0\). We define the set of entire histories, containing tuples of all states, actions, rewards and observations until step \(\Tmax\) as \(\HistorySet\) and denote \(\HistoryRV\) as a random variable for the entire history.

Denote \(\Prob_\Policy\) for a probability measure on a space with the random variables defined above, where agents follow the (joint) policy \(\Policy\in\PolicySet:=\prod_{i\in\PlayerSet}\PolicySet_i\), and let \(\E_\Policy\) be the expectation with respect to that measure. Given a Dec-POMDP \(\DecP\),

the self-play (SP) objective \(J^\DecP\colon \PolicySet^\DecP\rightarrow\mathbb{R}\) of \(\DecP\) is defined via
\(J^{\DecP}(\Policy):=\E_{\Policy}\left[\sum_{t=0}^{\Tmax}R_{t}\right]\)
for \(\Policy\in\PolicySet^\DecP\). Here, \(J^\DecP(\Policy)\) is called the expected return of the joint policy $\Policy$.

Zero-shot coordination and other-play As explicated in the lever coordination problem, there can be different, incompatible SP-optimal joint policies. A SP algorithm tries to maximize the SP objective and will in general randomly learn any one of these policies. When two such independently trained joint policies \(\Policy^{(1)},\Policy^{(2)}\) are matched, this can yield bad XP values \(J(\Policy_1^{(1)},\Policy_2^{(2)})\).

To address this shortcoming, hu2020other introduce the ZSC problem. In spirit, the problem is to find a general-purpose learning algorithm for fully cooperative environments to train agents that are able to robustly coordinate with their teammates. It is assumed that teammates have also been optimized for ZSC, using a common high-level approach. However, arbitrarily co-adapting agents' policies, e.g., through joint training, is disallowed. hu2020other operationalize this as the problem of recommending one learning algorithm to players in a fully cooperative game. Each player trains a joint policy using the algorithm and discards all but one agent. The resulting agents from all players are then evaluated in XP over one episode. hu2020other assume players are able to coordinate on a common learning algorithm, but that they are unable to coordinate the learned policies based on common labels for the Dec-POMDP.

hu2020other propose the OP algorithm as a method for this setting. The algorithm's main idea is to train a joint policy to achieve high expected return when each local policy is randomly permuted to break symmetries in different ways. The hope is that this results in a unique joint policy, at the cost of a potentially suboptimal expected return. Informally, one can consider equivalence mappings \(\EquivMapping\in\EquivSet\), which are maps that can be applied to actions, observations, and states, such that applying the map leaves the problem dynamics unchanged. Equivalence mappings can also be applied to a local policy \(\Policy_i\) to get a new policy \(\EquivMapping(\Policy_i)\). The OP objective \(J_\OP\) can then be defined via \(J_\OP(\Policy):=\E_{\EquivMapping\sim \U(\EquivSet)}[J(\EquivMapping(\Policy_1),\EquivMapping(\Policy_2))]\)
for a joint policy \(\Policy\in\PolicySet\),
where \(\U(\EquivSet)\) is a uniform distribution over \(\EquivSet\).[This is not hu2020other's original definition, but it is equivalent, by hu2020other's Proposition 2. The version presented here is the one we will generalize later.]
hu2020other's definitions
do not apply to Dec-POMDPs in which agents have different action or observation sets, and they do not account for symmetries between agents. We will formally define a more general version of OP in Section <ref>.

[][]hu2020other provide an informal proof that both players using OP is an optimal equilibrium in the fully cooperative game described above. Using an appropriate formalization, we show in the next section that this is in general not correct. Contrary to hu2020other's implicit assumption, there can be multiple, incompatible maximizers of the OP objective.

§ FORMALISM AND ANALYSIS OF OP

§.§ Dec-POMDP isomorphisms

To formalize the no-labels assumption, we introduce isomorphisms between Dec-POMDPs, which formalize the intuition that two Dec-POMDPs may represent the same problem using different labels. Our definition is a trivial generalization of kang2012exploiting's  automorphisms over partially observable stochastic games (POSGs)  to the concept of an isomorphism, but restricted to fully cooperative problems. Analogous definitions of isomorphisms between games have been introduced before in different frameworks (e.g., [Harsanyi & Selten, 1988], [Harsanyi & Selten, 1988], ch. 3.4; [Peleg et al., 1999], [Peleg et al., 1999]).

Let \(\DecP,\DecPSecond\) be two Dec-POMDPs. Consider a tuple of bijective maps
\(\Isom:=(\Isom_{N},\Isom_{S},(\Isom_{A_i})_{i\in\PlayerSet},(\Isom_{O_i})_{i\in\PlayerSet}),\) where

_N      𝒩^→^

_S      ^→^

∀i∈     _A_i      _i^→^__N(i)

∀i ∈     _O_i      _i^→__N(i)^.

think about the following again

Define a map \(\Isom_A\colon\ActionSet^\DecP\rightarrow\ActionSet^\DecPSecond\) via

\begin{equation}\Isom_A(\Action):=\left(\Isom_{A_{\Isom^{-1}_N(i)}}\Action_{\Isom^{-1}_N(i)}\right)_{i\in\PlayerSet^\DecPSecond},\end{equation}

for \(\Action\in\ActionSet^\DecP\),
and \(\Isom_O\) analogously for observations \(\Observation\in\ObservationSet^\DecP\). That is, in the joint action \(\Isom_A(\Action)\in\ActionSet^\DecPSecond\), agent \(j=\Isom_N(i)\in\PlayerSet^\DecPSecond\) (where \(i\in\PlayerSet^\DecP\)) plays action \(\Isom_{A_i}(a_i)\in\ActionSet_j^\DecPSecond\).

Let $\DecP,\DecPSecond$ be Dec-POMDPs such that both have the same horizon \({\Tmax^\DecP=\Tmax^\DecPSecond}\), and let \(\Isom\) be a tuple of bijective maps as defined in Equations (<ref>)–(<ref>). Then \(\Isom\) is an isomorphism from \(\DecP\) to \(\DecPSecond\) if
for any \(\Action\in\ActionSet^\DecP\), \(s,s'\in\StateSet^\DecP\), and \(o\in\ObservationSet^\DecP\),

\begin{align}
P^\DecP(s'\mid s,a) &= P^\DecPSecond(f_{S}(s')\mid f_{S}(s),f_A(a))\label{eq:2}\\
O^\DecP(o\mid s,a) &= O^\DecPSecond(f_{O}(o)\mid f_{S}(s),f_A(a))\label{eq:3}\\
\RewardFunction^\DecP(s,a) &= \RewardFunction^\DecPSecond(f_{S}(s),f_A(a))\label{eq:4}\\
b^\DecP_{0}(s) &= b_{0}^\DecPSecond(f_{S}(s)).
\end{align}

We denote \(\Iso(\DecP,\DecPSecond)\) for the set of isomorphisms from \(\DecP\) to \(\DecPSecond\). If that set is non-empty, \(\DecP\) and \(\DecPSecond\) are called isomorphic.

In the following, we adopt the convention to write \(fa\) instead of \(f_A(a)\) and \(f\Action_i\) instead of \(f_{A_i}\Action_i\), and we do the same for observations and states. We can also write \(f\AOHistory_{i,t}\) for \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\), which is defined as the element-wise application of \(f\). Letting \(\Isom \Reward := \Reward\) for rewards, we can also define \(\Isom\History\) for entire histories \(\History\in\HistorySet\). One can show that this action of isomorphisms can be inverted by \(\Isom^{-1}\) (see Appendix <ref>).

A policy \(\Policy\in\PolicySet^\DecP\) can be transformed by an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) into a policy for \(\DecPSecond\).
We call this operation the pushforward, analogously, for instance, to the construction of pushforward measures, as precomposition of \(\Policy\) with \(\Isom^{-1}\) “pushes” the policy from one Dec-POMDP to another. The definition is analogous to that of applications of symmetries to policies in hu2020other.

Let $\DecP,\DecPSecond$ be isomorphic Dec-POMDPs, let \(\Isom\in\Iso(\DecP,\DecPSecond)\), and let \(\Policy\in\PolicySet^\DecP\).
Then we define the pushforward \(\Isom^*\Policy\in\PolicySet^\DecPSecond\) of \(\Policy\) by \(\Isom\) via

\[
(\Isom^{*}\Policy)_{j}(\Action_{j}\mid\AOHistory_{j,t}):=\Policy_{\Isom^{-1} j}(f^{-1}\Action_{j}\mid f^{-1}\AOHistory_{j,t})
\]

for all \(j\in\mathcal{N}^\DecPSecond,a_j\in\ActionSet_j^\DecPSecond,t\in\{0,\dotsc,\Tmax\},\) and \(\AOHistory_{j,t}\in\AOHistorySet_{j,t}^\DecPSecond\). That is, in the joint policy \(\Isom^*\Policy\), agent \(j\in\PlayerSet^\DecPSecond\) gets assigned the local policy \(\Policy_i\) of agent \(i:=\Isom^{-1}j\in\PlayerSet^\DecP\), precomposed with \(\Isom^{-1}\).

We show in Appendix <ref> that \(\Policy\) and \(\Isom^*\Policy\) lead to the same expected return in their respective Dec-POMDPs.

For an example of an isomorphism and a pushforward policy, consider the two-stage lever game, a stylized coordination problem like the lever coordination game, but with two rounds instead of one. We will use the example in Section <ref> to show that OP is not optimal in the LFC problem.

[Two-stage lever game]

Consider the following variant of the lever coordination game, denoted by \(\DecP\). The problem has two agents,  \(\PlayerSet=\{1,2\}\), and rounds (\(\Tmax=1\)). Each round, each agent pulls a lever, \(\mathcal{A}_1=\mathcal{A}_2=\{1,2\}\). If both agents choose the same lever, the reward is \(1\), otherwise \(-1\). There are two observations, \(\ObservationSet_1=\ObservationSet_2=\{1,2\}\), and one state. In the second round (\(t=1\)), agents observe each other's previous action, so \(\ObservationRV_{i,1}=\ActionRV_{-i,0}\) for \(i=1,2\).

(init) ;
[ text centered] (t1)
\(\Action\)     \(\RewardFunction^\DecP(\State,\Action)\)

(1,1)      1

(1,2)     -1

(2,1)      -1

(2,2)     1
[right=of t1, text centered] (t2)

\(\Action\)     \(\RewardFunction^\DecPSecond(\State,\Action)\)

(1,1)      -1

(1,2)     1

(2,1)      1

(2,2)     -1

[draw, -latex'] (t1) to node [midway,above] \(\Isom^{-1}\) (t2);

Reward function \(\RewardFunction^\DecP\) in the two-stage lever game and reward function \(\RewardFunction^\DecPSecond=\RewardFunction^\DecP\circ\Isom^{-1}\) in an isomorphic problem.

Now consider an isomorphic problem \(\DecPSecond\) in which the labels for the actions of the second agent have been switched. A possible isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) is one consisting of identity maps, except for \(\Isom_{A_2}\), which switches the two actions of player \(2\). We give tables of rewards for both the original and the isomorphic problem in Figure <ref>. Applying \(\Isom^*\) to any policy \(\Policy\in\PolicySet^\DecP\) creates an equivalent policy \(\Isom^*\Policy\) for the Dec-POMDP \(\DecPSecond\), in which the actions of agent 2 in \(\DecP\) are replaced by the corresponding actions in \(\DecPSecond\).

§.§ The LFC game and problem

We begin by defining LFC games, which we then use to define the LFC problem. We formalize an LFC game as a fully cooperative game between principals whose strategies are learning algorithms, as defined below. The LFC game is defined for a specific “ground truth” problem \(\DecP\). The game's players, called principals, are the same as the agents in \(\DecP\). Each principal observes a randomly relabeled but isomorphic Dec-POMDP and trains a joint policy on that problem using a learning algorithm. The policies are then pushed back to \(\DecP\) and evaluated in XP.

For a set of Dec-POMDPs \(\DecPSetSecond\), let \(\Delta(\PolicySet^\DecP)\) be a set of probability measures over \(\PolicySet^\DecP\) for \(\DecP\in\DecPSetSecond\). A learning algorithm for \(\DecPSetSecond\) is then defined as a map \(\LA\) that takes in Dec-POMDPs \(\DecPSecond\in\DecPSetSecond\) and outputs distributions
\(\LA(\DecP)\in\Delta(\PolicySet^\DecP)\), and \(\LASet^\DecPSetSecond\) is defined as the set of learning algorithms for \(\DecPSetSecond\). For \(\Distr\in\Delta(\PolicySet^\DecP)\) and an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\), define the pushforward distribution \(\Isom^*\Distr:=\Distr \circ (\Isom^*)^{-1}\in\Delta(\PolicySet^\DecPSecond)\).

Now fix a Dec-POMDP \(\DecP\). For a given Dec-POMDP, we can create infinitely many different isomorphic problems, as we can use any set of labels, such as natural or real numbers, to define the problem. To describe the process of randomly sampling an isomorphic version of \(\DecP\), then, we restrict ourselves to a specific subset \(\DecPSet\) of isomorphic Dec-POMDPs in which the sets of states, actions, etc. are of the form \(\{1,2,\dotsc,k-1,k\}\subseteq\mathbb{N}\). \(\DecPSet\) is defined as the set of all relabeled Dec-POMDPs, i.e., all problems that are isomorphic to \(\DecP\) and have this canonical form (for a rigorous definition, see Appendix <ref>). One can interpret sampling from this set as principals coordinating on a canonical way to represent Dec-POMDPs, but each implementing the problem independently.

The Label-free coordination (LFC) game for \(\DecP\) is defined as a game \(\Gamma^\DecP\) where the set of players (here called principals) is \(\PlayerSet^\DecP\), the set of strategies is \(\LASet^\DecPSet\), and the common payoff for the strategy profile \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecP\) is

\begin{multline}U^\DecP(\LAProfile):=
\E_{\DecP_i\sim \U(\DecPSet),\,\Isom_i\sim\U(\Iso(\DecP_i,\DecP)),\,i\in\PlayerSet}\Big[\\
\E_{\Policy^{(j)}\sim\Isom_j^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\Big[

where \(\mathcal{U}(\DecPSet)\) is a uniform distribution over \(\DecPSet\).

We show in Appendix <ref> that the LFC games for two isomorphic Dec-POMDPs are equivalent, up to a potential permutation of the principals.

Turning to the LFC problem, the goal is to find a general learning algorithm to recommend to principals in any LFC game (see Figure <ref>). We hence formalize the problem here for a distribution over LFC games; however, since this does not change our theoretical analysis, we will only consider LFC problems for single LFC games afterwards. Let a set \(\DecPSetSecond\) of Dec-POMDPs be given, and denote \(\overline{\DecPSetSecond}:=\bigcup_{\DecPSecond\in\DecPSetSecond}\DecPSet^\DecPSecond\) where \(\DecPSet^\DecPSecond\) is the set of all relabeled problems of \(\DecPSecond\). The LFC problem for \(\DecPSetSecond\) is then defined as the problem of finding one learning algorithm \(\LA\in\LASet^{\overline{\DecPSetSecond}}\) to be used by principals in a randomly drawn game \(\Gamma^\DecPSecond\) for \(\DecPSecond\sim\U(\DecPSetSecond)\).

We define the Label-free coordination (LFC) problem for \(\DecPSetSecond\) as the optimization problem

\begin{equation}\max_{\LA\in\Sigma^{\overline{\DecPSetSecond}}}U^\DecPSetSecond(\LA)\end{equation}

where \(U^\DecPSetSecond(\LA):=\E_{\DecPSecond\sim\U(\DecPSetSecond)}\left[U^\DecPSecond(\LA,\dotsc,\LA)\right]\)
\(\LA\in\LASet^{\overline{\DecPSetSecond}}\). If \(\DecPSetSecond=\{\DecPSecond\}\), we refer to this as the LFC problem for \(\DecPSecond\) and write \(U^\DecPSecond(\LA):=U^{\{\DecPSecond\}}(\LA)=U^\DecPSecond(\LA,\dotsc,\LA)\).

§.§ Generalization of OP

Two-stage lever game

Asymmetric lever game

Heatmaps indicating XP values between policies from independent training runs. OP is on the left and OP with tie-breaking on the right, in which ties were broken between 32 different seeds. Each value has been averaged over 2048 episodes.

Here, we introduce a generalized version of the OP algorithm by hu2020other. It is based on Dec-POMDP automorphisms, which are isomorphisms $\Auto\in \Aut(\DecP):=\Iso(D,D)$ and can be thought of as representing symmetries of the problem. Our definition of an automorphism is equivalent to that of kang2012exploiting in the POSG framework[It is a straightforward consequence of kang2012exploiting's results that the problem of finding Dec-POMDP automorphisms is graph isomorphism–complete.] and is a generalization of hu2020other's equivalence mappings. Unlike the latter, automorphisms are defined for agents with potentially different action and observation sets, they can consist of different permutations for different agents, and they can incorporate permutations of the agents themselves.

As an example, consider an automorphism \(\Auto\in\Aut(\DecP)\) in the two-stage lever game. \(\Auto\) is an automorphism if precomposition with \(\Auto^{-1}\) does not change the reward function, observation probability kernel, etc. For instance, note that players are symmetric, so \(\Auto_N\) can be either the identity or it can switch both agents. In the latter case, applying \(\Auto^{-1}\) to joint actions switches the two players' actions, which does not have an effect on the relevant functions.

To define the OP objective, we use the pushforward by automorphisms, which is by definition a self-map on the set of joint policies \(\PolicySet^\DecP\). Similarly to equivalence mappings, we can randomly permute agents' local policies by different automorphisms, but we have to take into account potential permutations of agents. To that end, for a profile of automorphisms \(\AutProfile\in\Aut(\DecP)^\PlayerSet\), we define the joint policy \(\AutProfile^*\Policy:=\hat{\Policy}\), where the local policy \(\hat{\Policy}_i\) of agent \(i\in\PlayerSet\) is given by
\(\hat{\Policy}_i:= (\AutProfile^*_i\Policy)_i=
\Policy_{\AutProfile_i^{-1}i}(\AutProfile_i^{-1}\cdot\mid \AutProfile_i^{-1}\cdot)\).

For a Dec-POMDP \(\DecP\) and joint policy \(\Policy\in\PolicySet^\DecP\), define

\begin{equation}
J^{D}_\OP\colon \Policy\mapsto\E_{\AutProfile\sim \U(\Aut(D)^\mathcal{N})}\left[J^{D}(\AutProfile^*\Policy)
\right].\end{equation}

We say that \(J^\DecP_\OP\) is the other-play (OP) objective of \(\DecP\), and \(J^\DecP_\OP(\Policy)\) is the OP value of \(\Policy\in\PolicySet^\DecP\).
Given a set of Dec-POMDPs \(\DecPSetSecond\), we define an OP learning algorithm as any learning algorithm \(\LA^\OP\in\Sigma^\DecPSetSecond\) such that \(\E_{\Policy\sim\LA^\OP(\DecP)}[J_\OP^\DecP(\Policy)]=\max_{\Policy\in\PolicySet^\DecP}J^\DecP_\OP(\Policy)\) for all \(\DecP\in\DecPSetSecond\).

hu2020other show that their objective can be maximized in practice by considering a modified Dec-POMDP and applying any learning algorithm for Dec-POMDPs [e.g.,][]sunehag2018value to that problem. We show in Appendix <ref> that this does not work for our objective, as optimal policies may need to be stochastic, while in Dec-POMDPs there always exist optimal deterministic policies [][sec. 2.4.4]oliehoek2008optimal. However, we can still apply a vanilla policy gradient method (see Appendix <ref>).

§.§ OP is not optimal in the LFC problem

An OP learning algorithm may learn different, potentially incompatible OP-optimal policies in independent training runs. Hence, if the algorithm does not only learn compatible policies, it can be suboptimal in the LFC problem.

To see this, consider the two-stage lever game. In a simple game with one round, such as the lever coordination game, applying symmetries helps avoid arbitrary coordination on one lever. However, this changes in a game with two rounds. Since symmetries are not applied independently to the rounds, but they always apply to the whole episode, agents are able to coordinate in the second round if they coordinated by chance in the first round. This is advantageous for getting a higher return, but unfortunately, there are two different ways to coordinate in the second round.

Consider the two policies \(\Policy^R\) and \(\Policy^S\). In both policies, agents randomize uniformly between both levers in the first round. They also both randomize in the second round if coordination was unsuccessful in the first one. If coordination in the first round was successful, there are two different strategies: in \(\Policy^R\), both agents repeat their respective actions from round one. In \(\Policy^S\), both agents switch to the action they did not play in round one, which is unique, given there are only two levers. We show in Appendix <ref> that these policies are both optimal under OP.

Now suppose one agent chooses a local policy from \(\Policy^R\) and the other chooses a local policy from \(\Policy^S\). It is clear that this will yield a suboptimal expected return compared with \(\Policy^R\) or \(\Policy^S\) as agents will always fail to coordinate in the second round if they coordinated in the first round. Thus, in the LFC problem for the two-stage lever game, if a learning algorithm is not concentrated on only one of \(\Policy^S\) or \(\Policy^R\), but instead learns both policies (or potentially equivalent policies in relabeled problems), then that algorithm is suboptimal. We hence have the following result:

Any learning algorithm that learns both \(\Policy^R\) and \(\Policy^S\) in the two-stage lever game is an OP learning algorithm, but it is not optimal in the LFC problem for that game.

To save space, I usually title my appendix sections, “Proof of such and such”, plus I mention in the introduction that formal details and proofs are given in the appendix and then I omit the “Proof see appendix such and such” lines, because these take significant space. Only semi-relatedly, I like using the restatable environment for repeating results in the appendix, see <https://tex.stackexchange.com/questions/51286/recalling-a-theorem>. (Though because you here give informal versions of results in the main text it's not as clear that this is useful.)

§ OP WITH TIE-BREAKING

To fix OP's shortcoming outlined above, we introduce OP with tie-breaking, which is based on the notion of a tie-breaking function that uniquely ranks the different OP-optimal policies in a given problem and thus allows for consistently choosing among them. A tie-breaking function could, for instance, compare the two incompatible policies, \(\Policy^R\) and \(\Policy^S\), in the two-stage lever game and choose the one under which actions are more highly correlated, which is \(\Policy^R\). A tie-breaking function has to satisfy certain conditions, e.g., it always must have a unique maximizer, and it must choose equivalent policies in isomorphic Dec-POMDPs. We define OP with tie-breaking as an algorithm that chooses an OP-optimal policy that maximizes a tie-breaking function (see Appendix <ref>). We then have the following result:

OP with tie-breaking is optimal in the LFC problem, and all principals using the algorithm is a Nash equilibrium of any LFC game.
In particular, the optimal value in the LFC problem for any Dec-POMDP \(\DecP\) is equal to the OP value of any OP-optimal policy, i.e.,
\(\max_{\LA\in\LASet^\DecPSet}U^{\DecP}(\LA)=\max_{\Policy}J_\OP^\DecP(\Policy)\).

In practice, we can implement OP with tie-breaking by sampling, for a given Dec-POMDP \(\DecP\), \(K\in\mathbb{N}\) policies using an OP algorithm \(\LA^\OP\) and choosing the policy with the highest tie-breaking value. To compute tie-breaking values, we use a neural network, randomly initialized using a fixed random seed, to map histories deterministically to real numbers. We call these numbers “hash values” in analogy to the hash functions used in many areas of computer science to assign unique keys. The joint policy's tie-breaking value is then calculated as the expected hash value of histories under that policy. A few additional operations (randomly permuting policies, computing normal forms of histories, and summing over agent permutations) are required to ensure this works independently of labels.

Concretely, the tie-breaking function is computed as a Monte Carlo estimate of

\begin{equation}\label{eq:tie-breaking-function}
\frac{1}{N!}\sum_{\Isom_N\in\mathrm{Bij}(\PlayerSet)}\E_{\AutProfile\sim\U(\Aut(\DecP)^\PlayerSet)}\left[\E_{\AutProfile^*\Policy}\left[\Hash(\Isom_N(\iota(\HistoryRV)))\right]\right],
\end{equation}

where \(\Hash\) is the neural network, \(\mathrm{Bij}(\PlayerSet)\) is the set of permutations of \(\PlayerSet\), \(\iota(\History)\) is a normal form of the history \(\History\), and for \(\iota(\History):=(\State_0,(\Action_{i,0})_{i\in\PlayerSet},\Reward_0,\dotsc)\), we define
\(\Isom_N(\iota(\History)):=(\State_0,(\Action_{\Isom_N^{-1}i,0})_{i\in\PlayerSet},\Reward_0,\dotsc)\). The normal form \(\iota(\History)\) is computed by replacing the first occurrence of each state, action, or observation in \(\History\) by a \(0\), the second occurrence by a \(1\), and so on, and repeating the number if an element repeats itself in the history. Together with the summation over permutations of agents, this achieves that
\(\iota(\History)\) does not depend on particular labels for agents, states, etc. Moreover, consistent tie-breaking is only possible between policies that are randomly permuted by applications of \(\AutProfile\).
We prove in Appendix <ref> that, using a suitable random function \(\Hash\), a modification of the tie-breaking function described here satisfies our formal requirements almost surely.

Two-stage lever game

Asymmetric lever game

Plot of average off-diagonal XP value of the tie-breaking method, using different numbers of seeds for tie-breaking (using one seed is equivalent to OP and represents the baseline). The dashed orange line indicates the theoretical optimum. The shaded area indicates standard deviations across 20 different seeds used for the hash function.

§ EXPERIMENTS

MARL training and XP evaluation
We use a vanilla policy gradient algorithm ([Nguyen et al., 2017], [Nguyen et al., 2017]; [Williams, 1992], [Williams, 1992]) to train recurrent neural network policies on the OP objective. We use a randomly initialized feedforward neural network as a hash function and implement a tie-breaking function as described in Section <ref>. To implement OP with tie-breaking and study the dependency of its performance on the number of policies used for tie-breaking, we apply the tie-breaking function to \(K\) learned policies and choose the one with maximal value, for \(K\in\{2,4,8,16,32\}\).

To evaluate a given learning algorithm \(\LA\), we simplify the objective of the LFC problem. Instead of using relabeled Dec-POMDPs, we evaluate policies from independent training runs on the same Dec-POMDP, permuted by random automorphisms. That is, we estimate

\begin{multline}
\E_{\Policy^{(i)}\sim\LA(\DecP),\,i=1,2}
\Big[
\E_{\AutProfile_i\sim \U(\Aut(\DecP)),\,i=1,2}\Big[
\\
\end{multline}

by computing average off-diagonal XP values between independently trained, permuted policies. We believe that this is a realistic estimate of the objective, as the distributions over policies produced by our learning algorithms should not depend on the used labels (see Appendix <ref>).

In both examples, we train 320 policies using different random seeds, and partition them into 10 sets of 32 policies, where the 32 policies can be used for tie-breaking and each set corresponds to one run to be used for computing XP values. We apply OP with tie-breaking using 20 different random seeds for the hash function to explore to what degree the quality of the tie-breaking function depends on the random initialization of the hash network. Additional experimental details and results are described in Appendix <ref>. Code for our experiments can be found at <https://github.com/johannestreutlein/op-tie-breaking>.

Rewards in the asymmetric lever game, for \(t=0,1\) on the left, and for \(t=2\) on the right.

\(a_{2,1}\)     \(a_{2,2}\)     \(a_{2,3}\)

\(a_{1,1}\)    \(1\)     \(-1\)     \(-1\)

\(a_{1,2}\)   \(-1\)      \(1\)     \(-1\)

\(a_{1,3}\)     \(-1\)     \(-1\)     \(-1\)

\(a_{2,1}\)     \(a_{2,2}\)     \(a_{2,3}\)

\(a_{1,1}\)     \(0\)     \(0\)     \(0\)

\(a_{1,2}\)       \(0\)     \(0\)     \(0\)

\(a_{1,3}\)      \(1\)     \(1\)     \(1\)

Environments As environments, we implement the two-stage lever game introduced in Example <ref>, as well as the asymmetric lever game. In the asymmetric lever game, there are two agents \(i=1,2\), which can pull one of three levers \(\{a_{i,1},a_{i,2},a_{i,3}\}\). There are three states \(\{0,1,2\}\) representing three rounds of this game (i.e., \(P(s+1\mid s,a)=1\) for \(s\in\{0,1\}\) and \(\Tmax=2\)). As before, both agents observe the previous action of the other agent, so \(O_{-i,t}=A_{i,t-1}\) for \(i=1,2\), \(t=1,2\). The reward function is given in Table <ref>. The first agent has an extra task in the third round, which makes the agents asymmetric. We choose this example since, unlike the two-stage lever game, it is one where no OP-optimal policy is an intuitively sensible solution to ZSC.

Results All learned policies are close to optimal under the OP objective. In the two-stage lever game, both OP-optimal policies are learned equally well, while there is one dominant policy in the asymmetric lever game. In XP evaluation, OP with tie-breaking outperforms OP, achieving close to optimal XP values in both games.

We display XP matrices, which indicate XP values for any matching of two agents from 10 independent runs, in Figure <ref>. OP learns incompatible policies in different training runs, whereas policies chosen by OP with tie-breaking appear to be compatible. Average off-diagonal XP values for different numbers of policies used for tie-breaking are plotted in Figure <ref>. Here, using only one policy for tie-breaking is equivalent to OP, as there is only one policy to choose from.

We divide the policies into classes of policies with a high mutual XP score and show a histogram of the tie-breaking values for each class in Figure <ref>.

Two-stage lever game

Asymmetric lever game

Histogram of the tie-breaking values of the learned policies, categorized into classes with mutually high XP values.

§ OPEN ISSUES

Tie-breaking may be a feasible solution in some coordination problems. For instance, if a central authority can recommend an arbitrary tie-breaking function to all principals, using OP with tie-breaking may provide an easy way to coordinate over a range of different problems, even if joint training is impossible and common labels for problems are unavailable. Moreover, there could be tie-breaking functions based on natural biases that are shared between all principals, such as a simplicity bias. In the two-stage lever game, such a bias could be used to justify the strategy in which agents both repeat their action if they succeeded in coordinating in the first round.

However, our work shows that the current operationalization of ZSC needs to be revised. This is because OP with tie-breaking, an optimal solution to the LFC problem, is ultimately unsatisfactory as a solution to ZSC. First, OP with tie-breaking allows for arbitrary tie-breaking functions. This goes against the spirit of the ZSC problem, which prohibits arbitrary co-adaptation of policies and allows only tie-breaking functions based on plausible, non-arbitrary meta conventions, such as repeating actions that have previously been coordinated on.

Second, sometimes there may be no plausible tie-breaking function; instead, an entirely different policy should be learned. For instance, in the asymmetric lever game, OP-optimal policies choose one agent to switch to a different lever if coordination failed in the first round. But this choice of agent appears arbitrary. Hence, it would be preferable to learn a policy that randomizes if the players could not coordinate in the first round, similar to the policies in the two-stage lever game. Since such a policy is not learned by OP, no appropriate policy can be chosen by OP with tie-breaking. In fact, no optimal solution to the LFC problem would be to able learn this policy, as doing so would lead to lower performance under the LFC problem's objective.

Our results imply that an operationalization of ZSC should preclude principals from sharing not only labels but also any other implementation details. This suggests the following improved setting: principals coordinate on high-level ideas for learning algorithms, but they cannot coordinate on specific implementation details, such as random seeds, parameters, or code. Each principal then implements their algorithm independently and trains an agent on a given randomly sampled environment. As prior coordination between principals is restricted and the algorithm must work in a range of environments, it can only rely on general high-level principles for coordination, not on arbitrary tie-breaking.

Unfortunately, the question of what counts as an implementation detail versus a high-level idea for an algorithm is vague, and thus, unlike the LFC problem, this operationalization does not have a straightforward formalization. Nevertheless, it better suits ZSC's spirit and thus serves as an improved problem setting. We leave it to future work to address and refine this new operationalization.

§ CONCLUSION AND FUTURE WORK

We formalized  hu2020other's operationalization of ZSC as the LFC problem, showed that OP is not optimal in the problem, and introduced an extension, OP with tie-breaking, that is optimal. We supported our theoretical results experimentally in two toy examples.
Lastly, based on our findings, we concluded that the LFC problem is misaligned with ZSC's aims and suggested a revised intuitive operationalization of ZSC.

More work is required to devise formalisms and algorithms that suit this revised operationalization. One avenue may be different symmetry concepts [e.g.,][]harsanyi1988general,neumann1947theory,nash1951non,peleg1999canonical,Casajus2001 using weaker notions of equivalence. Unfortunately, as we show in Appendix <ref>, considering Dec-POMDPs as standard-form games and applying symmetries in that formalism leads to too little possible coordination between agents. This raises the question whether there is a “Goldilocks” concept obviating the need for tie-breaks while allowing for maximal coordination.

§ ACKNOWLEDGEMENTS

We are grateful to Leon Lang and Lennart Stern for help with proofs and writing, and Christian Schroeder de Witt for assistance with the PyMARL code repository. Johannes Treutlein would like to thank his readers Prof. Gitta Kutyniok and Prof. Reinhold Schneider at Technical University of Berlin, where he submitted a version of this paper as a BSc thesis. During his work on this paper, Johannes Treutlein was supported by Open Philanthropy, the Berkeley Existential Risk Initiative, and the Center on Long-Term Risk. Caspar Oesterheld is thankful for support by the National Science Foundation under Award IIS-1814056.

[Alon & Spencer, 2016]
Alon, N. and Spencer, J. H.
The probabilistic method.
John Wiley & Sons, Hoboken, NJ, 4th edition, 2016.

[Barrett & Stone, 2015]
Barrett, S. and Stone, P.
Cooperating with unknown teammates in complex domains: A robot soccer
case study of ad hoc teamwork.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 29, 2015.

[Barrett et al., 2011]
Barrett, S., Stone, P., and Kraus, S.
Empirical evaluation of ad hoc teamwork in the pursuit domain.
In AAMAS, pp.  567–574, 2011.

[Boutilier, 1999]
Boutilier, C.
Sequential optimality and coordination in multiagent systems.
In Proceedings of the 16th International Joint Conference on
Artificial Intelligence - Volume 1, pp.  478–485, 1999.

[Brown & Sandholm, 2018]
Brown, N. and Sandholm, T.
Superhuman AI for heads-up no-limit poker: Libratus beats top
Science, 3590 (6374):0 418–424, 2018.

[Campbell et al., 2002]
Campbell, M., Hoane Jr, A. J., and Hsu, F.-h.
Deep Blue.
Artificial Intelligence, 1340 (1-2):0 57–83,

[Carroll et al., 2019]
Carroll, M., Shah, R., Ho, M. K., Griffiths, T., Seshia, S., Abbeel, P., and
Dragan, A.
On the utility of learning about humans for human-AI coordination.
In Advances in Neural Information Processing Systems,
volume 32, 2019.

[Casajus, 2001]
Casajus, A.
Weak isomorphisms of extensive games.
In Focal Points in Framed Games: Breaking the Symmetry, pp.  55–90. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.

[Emmons et al., 2021]
Emmons, S., Oesterheld, C., Critch, A., Conitzer, V., and Russell, S.
Symmetry, equilibria, and robustness in common-payoff games.
In 3rd Games, Agents, and Incentives Workshop (GAIW 2021). Held
as part of the Workshops at the 20th International Conference on Autonomous
Agents and Multiagent Systems., May 2021.

[Foerster et al., 2018]
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S.
Counterfactual multi-agent policy gradients.
In AAAI Conference on Artificial Intelligence, 2018.

[Foerster et al., 2019]
Foerster, J., Song, F., Hughes, E., Burch, N., Dunning, I., Whiteson, S.,
Botvinick, M., and Bowling, M.
Bayesian action decoder for deep multi-agent reinforcement
In Proceedings of the 36th International Conference on Machine
Learning, volume 97 of Proceedings of Machine Learning Research, pp.   1942–1951, 2019.

[Gibbons, 1992]
Gibbons, R. S.
Game theory for applied economists.
Princeton University Press, Princeton, NJ, 1992.

[Glicksberg, 1952]
Glicksberg, I. L.
A further generalization of the Kakutani fixed point theorem, with
application to Nash equilibrium points.
Proceedings of the American Mathematical Society, 30
(1):0 170–174, 1952.

[Goldberg et al., 2013]
Goldberg, P. W., Papadimitriou, C. H., and Savani, R.
The complexity of the homotopy method, equilibrium selection, and
Lemke-Howson solutions.
ACM Transactions on Economics and Computation, 10
(2):0 1–25, 2013.

[Goldman et al., 2007]
Goldman, C. V., Allen, M., and Zilberstein, S.
Learning to communicate in a decentralized environment.
Autonomous Agents and Multi-Agent Systems, 150
(1):0 47–90, 2007.

[Harsanyi, 1975]
Harsanyi, J. C.
The tracing procedure: a Bayesian approach to defining a solution
for n-person noncooperative games.
International Journal of Game Theory, 40 (2):0
61–94, 1975.

[Harsanyi & Selten, 1988]
Harsanyi, J. C. and Selten, R.
A general theory of equilibrium selection in games.
The MIT Press, Cambridge, MA, 1988.

[Herings & Peeters, 2003]
Herings, P. J.-J. and Peeters, R. J.
Equilibrium selection in stochastic games.
International Game Theory Review, 50 (4):0
307–326, 2003.

[Herings & Van Den Elzen, 2002]
Herings, P. J.-J. and Van Den Elzen, A.
Computation of the Nash equilibrium selected by the tracing
procedure in n-person games.
Games and Economic Behavior, 380 (1):0
89–117, 2002.

[Hu et al., 2020]
Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J.
“Other-play” for zero-shot coordination.
In Proceedings of the 37th International Conference on Machine
Learning, volume 119 of Proceedings of Machine Learning Research,
pp.  4399–4410, 2020.

[Kang & Kim, 2012]
Kang, B. K. and Kim, K.-E.
Exploiting symmetries for single-and multi-agent partially observable
stochastic domains.
Artificial Intelligence, 182:0 32–57, 2012.

[Kuhn, 1953]
Kuhn, H. W.
Extensive games and the problem of information.
In Contributions to the Theory of Games: Volume II, volume 28
of Annals of Mathematics Studies, pp.  193–216. Princeton University
Press, Princeton, NJ, 1953.

[Lerer & Peysakhovich, 2019]
Lerer, A. and Peysakhovich, A.
Learning existing social conventions via observationally augmented
In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics,
and Society, pp.  107–114, 2019.

[Lewis, 2008]
Lewis, D.
Convention: A philosophical study.
John Wiley & Sons, New York, NY, 2008.

[Maschler et al., 2013]
Maschler, M., Solan, E., and Zamir, S.
Behavior strategies and Kuhn's theorem.
In Game Theory, pp.  219–250. Cambridge University Press,
Cambridge, UK, 2013.

[Mehta et al., 1994]
Mehta, J., Starmer, C., and Sugden, R.
The nature of salience: An experimental investigation of pure
coordination games.
The American Economic Review, 840 (3):0
658–673, 1994.

[Mnih et al., 2016]
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T.,
Silver, D., and Kavukcuoglu, K.
Asynchronous methods for deep reinforcement learning.
In Proceedings of The 33rd International Conference on Machine
Learning, volume 48 of Proceedings of Machine Learning Research, pp.   1928–1937, 2016.

[Nair et al., 2003]
Nair, R., Tambe, M., Yokoo, M., Pynadath, D., and Marsella, S.
Taming decentralized POMDPs: Towards efficient policy computation
for multiagent settings.
In IJCAI'03: Proceedings of the 18th International Joint
Conference on Artificial intelligence, pp.  705–711, 2003.

[Nash, 1951]
Nash, J. F.
Non-cooperative games.
Annals of Mathematics, 540 (2):0 286–295,

[Nguyen et al., 2017]
Nguyen, D. T., Kumar, A., and Lau, H. C.
Policy gradient with value function approximation for collective
multiagent planning.
In Advances in Neural Information Processing Systems,
volume 30, 2017.

[Oliehoek et al., 2006]
Oliehoek, F., Vlassis, N., et al.
Dec-POMDPs and extensive form games: equivalence of models and
IAS technical report IAS-UVA-06-02, University of Amsterdam,
Intelligent Systems Lab, Amsterdam, The Netherlands, 2006.

[Oliehoek et al., 2008]
Oliehoek, F. A., Spaan, M. T., and Vlassis, N.
Optimal and approximate Q-value functions for decentralized
Journal of Artificial Intelligence Research, 32:0
289–353, 2008.

[Oliehoek et al., 2016]
Oliehoek, F. A., Amato, C., et al.
A concise introduction to decentralized POMDPs.
Springer, 2016.

[Osborne & Rubinstein, 1994]
Osborne, M. J. and Rubinstein, A.
A course in game theory.
MIT Press, Cambridge, MA, 1994.

[Paszke et al., 2019]
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen,
T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E.,
DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L.,
Bai, J., and Chintala, S.
PyTorch: An imperative style, high-performance deep learning
In Advances in Neural Information Processing Systems 32. 2019.

[Pearl, 2009]
Pearl, J.
Causality: Models, Reasoning, and Inference.
Cambridge University Press, New York, NY, 2nd edition, 2009.

[Peleg et al., 1999]
Peleg, B., Rosenmüller, J., and Sudhölter, P.
The canonical extensive form of a game form: Symmetries.
In Alkan, A., Aliprantis, C. D., and Yannelis, N. C. (eds.),
Current Trends in Economics, pp.  367–387. Springer, 1999.

[Rotman, 2012]
Rotman, J. J.
An Introduction to the Theory of Groups.
Springer, New York, NY, 2012.

[Samvelyan et al., 2019]
Samvelyan, M., Rashid, T., de Witt, C. S., Farquhar, G., Nardelli, N., Rudner,
T. G. J., Hung, C.-M., Torr, P. H. S., Foerster, J., and Whiteson, S.
The StarCraft Multi-Agent Challenge.
arXiv preprint arXiv:1902.04043, 2019.

[Schelling, 1980]
Schelling, T. C.
The Strategy of Conflict.
Harvard University Press, Cambridge, MA, 1980.

[Schulman et al., 2017]
Schulman, J., Abbeel, P., and Chen, X.
Equivalence between policy gradients and soft Q-learning.
arXiv preprint arXiv:1704.06440, 2017.

[Silver et al., 2017]
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez,
A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui,
F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D.
Mastering the game of go without human knowledge.
Nature, 5500 (7676):0 354–359, 2017.

[Stone et al., 2010]
Stone, P., Kaminka, G., Kraus, S., and Rosenschein, J.
Ad hoc autonomous agent teams: Collaboration without
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 24, 2010.

[Sunehag et al., 2018]
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg,
M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T.
Value-decomposition networks for cooperative multi-agent learning
based on team reward.
In Proceedings of the 17th International Conference on
Autonomous Agents and MultiAgent Systems, pp.  2085–2087, 2018.

[Sutton & Barto, 2018]
Sutton, R. S. and Barto, A. G.
Reinforcement learning: An introduction.
MIT Press, Cambridge, MA, 2018.

[Tesauro, 1994]
Tesauro, G.
TD-Gammon, a self-teaching backgammon program, achieves
master-level play.
Neural Computation, 60 (2):0 215–219, 1994.

[Tucker et al., 2020]
Tucker, M., Zhou, Y., and Shah, J.
Adversarially guided self-play for adopting social conventions.
arXiv preprint arXiv:2001.05994, 2020.

[von Neumann & Morgenstern, 1947]
von Neumann, J. and Morgenstern, O.
Theory of Games and Economic Behavior.
Princeton University Press, Princeton, NJ, 1947.

[Williams, 1991]
Williams, D.
Probability with Martingales.
Cambridge University Press, Cambridge, UK, 1991.

[Williams, 1992]
Williams, R. J.
Simple statistical gradient-following algorithms for connectionist
reinforcement learning.
Machine Learning, 80 (3-4):0 229–256, 1992.

In Appendix <ref>, we briefly compare our approach to harsanyi1988general. In Appendix <ref>, we provide additional details about our implemented algorithms, cross-play evaluation, and further results. Everything afterwards, starting with Appendix <ref>, is a self-contained rigorous treatment of the results that were informally stated in the paper. The two main theorems are subject of Appendices <ref> and <ref>. In the following, we give a brief outline of Appendices <ref>–<ref>.

In Appendix <ref>, we make rigorous the definition of an LFC game and LFC problem from Section <ref>, and we provide auxiliary results required to prove our main theorems. Among those, we show in Section <ref> that any optimal symmetric profile of learning algorithms in an LFC game is a Nash equilibrium. In addition, in Appendix <ref>, we briefly discuss a condition under which the objective in the LFC problem is equivalent to the formulation used in our experiments as outlined in Section <ref>.

In Appendix <ref>, we provide characterizations of both the OP objective and the payoff in an LFC game, in terms of equivalence classes of policies under random permutations by automorphisms. This notion of equivalence makes it possible to analyze the OP-optimal policies in terms of representatives of equivalence classes that are invariant to automorphisms. We will use our results from this section for the proofs about the LFC problem, and for a proof about the existence of random tie-breaking functions.

In Appendix <ref>, we then turn to stating and proving a rigorous version of Theorem <ref>. To that end, we show that there are two distinct OP-optimal equivalence classes in the two-stage lever game (Appendix <ref>), and then prove that any algorithm that learns both of these is an OP learning algorithm, but not optimal in the LFC problem of that game (Appendix <ref>).

Lastly, in Appendix <ref>, we provide theoretical results about OP with tie-breaking and state and prove a rigorous version of Theorem <ref>. First, we define OP with tie-breaking and discuss to what degree the formal definition is satisfied by our method (Appendix <ref>). Second, we show that OP with tie-breaking is optimal in the LFC problem and that all principals using OP with tie-breaking is an optimal symmetric Nash equilibrium of any LFC game (Appendix <ref>). Third, we prove that a modification of the tie-breaking function introduced in Section <ref> satisfies our formal requirements (Appendix <ref>).

§ LIST OF SYMBOLS

§.§ General mathematical notation

p.15  p.85
\(\mathbb{N}\)     natural numbers excluding \(0\)

\(\mathbb{R}\)     real numbers

\(\mathbb{N}_0\)     \(\mathbb{N}\cup\{0\}\)

\(\PowerSet(\mathcal{X})\)     power set of the set \(\mathcal{X}\)

\(\prod_{i=1}^N \mathcal{X}_i\)     Cartesian product \(\mathcal{X}_1\times\dotsb\times \mathcal{X}_N\) of sets \(\mathcal{X}_1,\dotsc,\mathcal{X}_N\)

\(|\mathcal{X}|\)     cardinality of the set \(\mathcal{X}\)

\(\mathcal{X}\setminus \mathcal{Y}\)      set of elements of \(\mathcal{X}\) that are not in \(\mathcal{Y}\)

\(X:=Y\)     \(X\) is defined as \(Y\)

\(f\circ g\)     composition of two composable functions \(f\) and \(g\)

\(\Proj_i(x)\)     projection on the \(i\)th component of the vector \(x=(x_i)_{i\in\mathcal{X}}\)

\(x_{-i}\)     vector with the \(i\)th component removed, \(x_{-i}:=(x_1,\dotsc,x_{i-1},x_{i+1},\dotsc x_N)\)

\((\tilde{x}_i,x_{-i})\)     vector with \(\tilde{x}_i\) as \(i\)th component, \((\tilde{x}_i,x_{-i}):=(x_1,\dots x_{i-1},\tilde{x}_i,x_{i+1},\dotsc x_N)\)

\(\delta_{ij}\)     Kronecker delta

\(\mathds{1}_\mathcal{X}\)     indicator function of set \(\mathcal{X}\)

\(\Prob\)    probability measure

\(\Delta(\mathcal{X})\)     set of probability mass functions or measures over the set \(\mathcal{X}\)

\(\mathcal{E}_1\otimes\mathcal{E}_2\)     product-\(\sigma\)-Algebra of \(\mathcal{E}_1\) and \(\mathcal{E}_2\)

\(\Mixture_1\otimes\Mixture_2\)     product measure of \(\Mixture_1\) and \(\Mixture_2\)

\(\E[X]\)     expectation of the random variable \(X\)

\(\E_{x\sim \Distr}[f(x)]\)     integral of \(f\) with respect to the measure \(\Distr\)

\(\U(\mathcal{X})\)     uniform distribution over the set \(\mathcal{X}\)

\(\delta_x\)     Dirac measure

\(\Param\)     parameter value

\(\NN\)     neural network

\(\mathcal{L}\)     loss function

§.§ Dec-POMDPs

p.15  p.85
\(\DecP,\DecPSecond,\DecPThird\)     Dec-POMDPs

\(\mathcal{X}^\DecP\)     set belonging to the Dec-POMDP \(\DecP\) (e.g., \(\PolicySet^\DecP\) is the set of policies of \(\DecP\))

\(\PlayerSet\)     set of agents or principals \(\PlayerSet=\{1,\dotsc, N\}\)

\(i\)     agent or principal

\(\StateSet\)     set of states

\(\StateRV_t\)      random variable for the state at step \(t\)

\(\State\)     state

\(\ActionSet\)     set of joint actions

\(\ActionSet_i\)     set of actions of player \(i\)

\(\ActionRV_{i,t}\)     random variable for the action of agent \(i\) at step \(t\)

\(\Action\)     joint action

\(\Action_i\)     action of agent \(i\)

\(\ObservationSet\)     set of observations

\(\ObservationSet_i\)     set of observations of agent \(i\)

\(\ObservationRV_{i,t}\)     random variable for the observation of agent \(i\) at step \(t\)

\(\Observation\)     joint observation

\(\Observation_i\)     observation of agent \(i\)

\(\RewardRV_t\)     random variable for the reward at step \(t\)

\(\Reward\)     reward

\(P(\State'\mid\State,\Action)\)     transition probability

\(O(\Observation\mid\State,\Action)\)     observation probability

\(\RewardFunction(\Action,\State)\)     reward given joint action \(\Action\) and state \(\State\)

\(\Tmax\)     horizon

\(\AOHistorySet\)     set of joint action-observation histories

\(\AOHistorySet_{i,t}\)     set of local action-observation history of agent \(i\) of length \(t\)

\(\AOHistoryRV_{i,t}\)     random variable for action-observation history of agent \(i\) of length \(t\)

\(\AOHistory_{i,t}\)     local action-observation history of agent \(i\) of length \(t\)

\(\HistorySet\)     set of histories

\(\HistoryRV\)     random variable for the history

\(\History\)     history

\(\HistorySet_t\)     set of histories of length \(t\)

\(\HistoryRV_t\)     random variable for the history of length \(t\)

\(\History_t\)     history of length \(t\)

\(\PolicySet\)     set of joint policies

\(\PolicySet_i\)     set of local policies of agent \(i\)

\(\Policy\)     joint policy

\(\Policy_i\)     local policy of agent \(i\)

\(\PolicySet^0\)     set of joint deterministic policies

\(\PolicySet^0_i\)     set of local deterministic policies of agent \(i\)

\((\Omega,\PowerSet(\Omega),\Prob_\Policy)\)     measure space for a Dec-POMDP environment induced by policy \(\Policy\)

\(\E_\Policy\)     expectation with respect to \(\Prob_\Policy\)

\(J^\DecP(\Policy)\)     expected return of policy \(\Policy\) in Dec-POMDP \(\DecP\)

§.§ Label-free coordination and other-play

p.15  p.85
\(\Aut(\DecP)\)     set of automorphisms

\(\Iso(\DecP,\DecPSecond)\)     set of isomorphisms from \(\DecP\) to \(\DecPSecond\)

\(\Sym(\DecP)\)     set of labelings of \(\DecP\)

\(\Isom\)     isomorphism or labeling

\(\Isom^*\DecP\)     relabeled Dec-POMDP

\(\Isom^*\Policy\)     pushforward policy

\(\IsoProfile\)     profile of isomorphisms

\(\Aut(\DecP)\)     set of automorphisms of \(\DecP\)

\(\Auto\)     automorphism

\(\Id\)     identity automorphism

\(\AutProfile\)     profile of automorphisms

\(J^\DecP_\OP(\Policy)\)     other-play value of \(\Policy\) in Dec-POMDP \(\DecP\)

\(\DecPSet,\DecPSetSecond\)     sets of Dec-POMDPs

\(\mathcal{F}_i\)     \(\sigma\)-Algebra over \(\PolicySet_i\)

\(\mathcal{F}\)     product-\(\sigma\)-Algebra over \(\PolicySet\)

\(\Distr\)     distribution over policies

\(\LASet^\DecPSet\)     set of learning algorithms for \(\DecPSet\)

\(\LA\)     learning algorithm

\(\LAProfile\)     profile of learning algorithms

\(U^\DecP(\LAProfile)\)     payoff in the label-free coordination game for \(\DecP\) given strategy profile \(\LAProfile\)

\(U^\DecP(\LA)\)     value of \(\LA\) in the label-free coordination problem for \(\DecP\)

\(\Mixture\)     distribution over policies with independent local policies

\(\PolicyLatent_i\)     latent variable for the policy of agent \(i\)

\(\mathcal{Z}\)     measurable set of policies

\(\Policy^\Mixture\)     policy corresponding to the distribution \(\Mixture\)

\(\Psi(\Policy)\)     policy corresponding to the other-play distribution of \(\Policy\)

\([\Policy]\)     equivalence class of policies

\(\Hash\)     hash function

\(\Tie\)     tie-breaking function

§ COMPARISON TO THE SOLUTION BY HARSANYI & SELTEN

possibly perform experiments

Here, we compare the solution to the equilibrium selection problem provided by harsanyi1988general to our approach. It is unclear how to apply harsanyi1988general's solution to Dec-POMDPs, and this would be an interesting area for future work. However, we can translate Dec-POMDPs into harsanyi1988general's formalism of standard-form games, using similar constructions as the ones for normal-form games and extensive-form games by oliehoek2006dec, and apply harsanyi1988general's solution to such a problem. We can then compare it to OP with tie-breaking as an optimal solution to the LFC problem.

Below, we give an example in which OP with tie-breaking is equivalent to any OP algorithm in theory, as there is only one OP-optimal policy (ignoring differences between policies that do not matter under OP; see Appendix <ref>). We also consider that policy as good solution to ZSC in spirit. However, applying harsanyi1988general's procedure to a corresponding standard-form game leads to a policy in which agents cannot coordinate and which thus leads to a lower payoff. We restrict ourselves to an informal exposition and leave a more rigorous analysis to future work.

Consider a version of the two-stage lever game with 10 instead of 2 levers. As in the two-stage lever game, pulling the same lever gives a reward of \(1\), non-coordination gives a reward of \(-1\), and the game is fully observable. Note that, like in the game with two levers, an OP-optimal policy uniformly randomizes between all levers in the first round. If no coordination was achieved in the first round, then in the second round, an optimal policy randomizes between the two levers that have been played in the first round by both players, similarly to the two-lever variant. There is a difference, however, if players coordinated on one lever in the first round. Clearly, in one optimal policy, players repeat their action from the first round, as was the case in the two-stage lever game. However, unlike in the two-lever case, here, there is no second optimal policy. It is not possible for the players to consistently switch to a different lever, as there are now not one but 9 other levers to choose from. Hence, the only optimal policy is one that chooses the unique lever that was chosen in the first round. This appears to us as a good solution to ZSC in this case.

Now consider a corresponding standard-form game [][ch. 2]harsanyi1988general. It is sufficient for us here to note that in this game, each player \(i=1,2\) is split into agents \(j_{\AOHistory_{i,t}}\) with distinct sets of actions \(\ActionSet_{\AOHistory_{i,t}}\) (corresponding to the 10 levers) for each possible action-observation history \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\) in the corresponding Dec-POMDP.
The payoff for a strategy for all agents of all players is then the expected return that the corresponding policy would receive. Importantly, symmetries as introduced by [][ch. 3.4]harsanyi1988general can permute each of the individual action sets \(\ActionSet_{\AOHistory_{i,t}}\) separately, as long as this does not change the payoffs (there are more rules for how symmetries can permute actions, players, and agents, but these do not matter for us here).
For instance, one symmetry may leave the actions of both players \(i=1,2\) in the first round unchanged, while it may apply one permutation to the action sets \(\ActionSet_{\AOHistory_{i,1}}\) corresponding to action-observation histories \(\AOHistory_{i,1}\in\AOHistorySet_{i,1}\) of all agents of both players in the second round.
Since rewards in the second round do not depend on actions in the first round, and permuting all actions of all second-round agents in the same way does not change the rewards for actions, such a permutation is a symmetry of the game.

As a result, in the first and the second round, all individual actions are symmetric, and, unlike in the corresponding Dec-POMDP, the symmetries for both rounds can be applied independently of each other. Hence, a symmetry-invariant strategy needs to play all actions with equal probability in both rounds. Since harsanyi1988general's solution always chooses a strategy that is invariant to symmetries [][ch. 3.4]harsanyi1988general, it follows that the strategy chosen by their procedure is a uniform distribution. Clearly, this strategy yields a lower return than the OP-optimal policy described above. In particular, since this applies independently of labelings, it follows from Theorem <ref> that the solution must be suboptimal in the associated LFC problem.

A similar argument could be made about cheap-talk: in a standard-form game, players using a symmetry-invariant policy would never be able to use cheap-talk, as they could not learn the meanings of each others' messages over time. Transforming a Dec-POMDP into a standard-form game thus yields too many symmetries, precluding players from coordinating based on the structure of the Dec-POMDP, even if it was possible to uniquely do so. In contrast, OP exhibits in a sense the opposite failure mode in the two-stage lever game, allowing players to coordinate arbitrarily due to too few symmetries between policies.

§ FURTHER EXPERIMENTAL DETAILS

Here, we provide additional details about the experiments outlined in Section <ref>. We describe our implementation of OP (Appendix <ref>), our implementation other OP with tie-breaking (Appendix <ref>), and discuss our cross-play evaluation procedure as well as some further results (Appendix <ref>).

§.§ Other-play implementation

Input:Dec-POMDP \(\DecP\)
Number of training steps \(L\)
Episode batch-size \(K\)
Gradient-based optimizer
Output: Joint policy \(\Policy\in\PolicySet^\DecP\)

Initialize \(\Param\)
\(l=1\) to \(L\)
\(k=1\) to \(K\)
Sample profile of automorphisms \(\AutProfile^{(k)}\sim \U(\Aut(\DecP)^\mathcal{N})\)
Sample history \(\History^{(k)}\sim \Prob^\DecP_{{\AutProfile^{(k)}}^*\Policy_\Param}\)
using joint policy \({\AutProfile^{(k)}}^*\Policy_\Param\)
\(t=1\) to \(\Tmax\)
\(G^{(k)}_t\leftarrow\sum_{t'=t}^\Tmax \Reward^{(k)}_{t'}\)
Compute loss
\(\mathcal{L}(\Param)\leftarrow-\frac{1}{KTN}\sum_{k=1}^K\sum_{t=1}^\Tmax G^{(k)}_t\sum_{i=1}^N\log \Policy_{\theta,{\AutProfile^{(k)}_i}^{-1}i}({\AutProfile^{(k)}_i}^{-1}\Action^{(k)}_{i,t}\mid {\AutProfile_i^{(k)}}^{-1}\AOHistory_{i,t}^{(k)})\)
Update \(\Param\) using \(\nabla_\Param\mathcal{L}(\Param)\) to minimize \(\mathcal{L}\)
Return \(\Policy_\Param\)

Other-play learning algorithm based on vanilla policy gradient

Our implementation of the OP learning algorithm is based on the PyMARL framework samvelyan19smac. We use recurrent neural networks to parameterize the policies of agents and a policy gradient algorithm to train agents' policies. Given that our toy problems are very small, they could also be solved by simple tabular methods. Nevertheless, we choose to employ this framework to demonstrate that our results transfer to state-of-the-art methods, even if the problems do not require them.

PyMARL is based on the PyTorch deep learning framework NEURIPS2019-pytorch. Neural network layers are implemented using the PyTorch module  and the recurrent neural network uses a single , with the input encoding being one layer with ReLU activation functions. Hidden states are transformed into probabilities by a single  layer followed by a softmax. The dimension of the hidden state is \(64\). Agent parameters are optimized using the  module, with a learning rate of \(0.0005\), an alpha of \(0.99\) and epsilon of \(0.00001\). These hyperparameters were all adopted as default values from the PyMARL framework.

Since our generalization of the OP objective requires policies that can randomize, and since it cannot be implemented as the SP objective in a modified Dec-POMDP (see Appendix <ref>), it is not clear how to use multi-agent methods based on value functions [e.g.][]sunehag2018value,foerster2017counterfactual. For this reason, we use a vanilla multi-agent policy gradient algorithm without baseline ([Nguyen et al., 2017], [Nguyen et al., 2017]; [Williams, 1992], [Williams, 1992]; [Sutton & Barto, 2018], [Sutton & Barto, 2018], ch. 13.1), which can easily be applied to our generalization of the OP objective (see Algorithm <ref>).

We use weight sharing, that is, all agents use the same neural network and receive an additional observation specifying their agent-ID. In the two-stage lever game, where agents are symmetric, we omit this agent-ID and thus force the resulting joint policy to be symmetric, \(\Policy_1=\Policy_2\). We can do this as a symmetric policy is optimal under OP in this case (see Theorem <ref>). As a benefit, we do not have to implement permutations of agents for OP. In the asymmetric lever game, since agents are not symmetric, agent-IDs are added to observations as one-hot vectors.

Lastly, we add a penalty for the negative entropy of a policy to the loss-function mnih2016asynchronous,schulman2017equivalence. The entropy of the probability distribution \(\Policy_{\theta,i}(\cdot\mid \AOHistory_{i,t})\) is defined as

\[H(\Policy_{\theta,i}(\cdot\mid \AOHistory_{i,t})):=-\sum_{\Action_i\in\ActionSet_i}\Policy_{\theta,i}(\Action_i\mid \AOHistory_{i,t})\log \Policy_{\theta,i}(\Action_i\mid \AOHistory_{i,t}).\]

The loss-function is then

\begin{equation}\label{eq:100}
\tilde{\mathcal{L}}(\Param)=-\frac{1}{KTN}\sum_{k=1}^K \sum_{t=0}^\Tmax
\left(G_{t}^{(k)}\sum_{i=1}^N\log\Policy_{\Param,i}(\Action_{i,t}^{(k)}\mid \AOHistory^{(k)}_{i,t}) + \alpha\sum_{i\in\PlayerSet}H(\Policy_{\Param,i}(\cdot\mid \AOHistory^{(k)}_{i,t}))\right),
\end{equation}

where \(\alpha\) is a hyperparameter.

We choose \(\alpha=0.5\), as the highest \(\alpha\) at which we still got fast convergence to an approximately optimal policy, after testing \(\alpha=1,0.5,0.1\), and \(0.05\). First, this encourages exploration and avoids a policy prematurely converging to a local minimum. Without this term, a small percentage of the learned policies in the asymmetric lever game converged to suboptimal equilibria. Second, we did this to make sure that agents learn to play a unique uniform distribution where actions do not matter for the OP value of a policy. Since it can be the case that actions do not matter but each choice of distribution still creates a different policy, this helps reduce the number of different policies that are learned, and thus facilitates tie-breaking between the remaining policies. Additionally, in the lever game with asymmetric players, it ensures that one can always infer from a distribution over histories the Dec-POMDP that these histories belong to. It hence suffices to let our hash function depend only on histories (see Appendix <ref>).

Finally, we briefly outline how sampling from a policy \(\Isom^*\Policy\) is implemented, in the two-stage lever game where agents are symmetric and use the same policy network. Actions and observations are encoded as one-hot vectors, i.e., as elements of the canonical basis \(\{e_1,\dotsc,e_k\}\), where \(k\) is the cardinality of the respective set. For a given episode, one profile of automorphisms \(\AutProfile_1,\AutProfile_2\sim\U(\Aut(\DecP))\) is sampled. At time step \(t\), the observation input of the agent \(i\) is \(\AutProfile_i^{-1}(\ObservationRV_{i,t},\ActionRV_{i,t-1})\). Then an action \(\tilde{\ActionRV}_{i,t}\) is sampled from the agent policy, and that action is permuted by applying \(\AutProfile_i\), i.e., \(\ActionRV_{i,t}:=\AutProfile_i\tilde{\ActionRV}_{i,t}\). Otherwise, the Dec-POMDP model proceeds as normal. One can easily see that this results in a history \(\HistoryRV\sim\Prob_{\AutProfile^*\Policy}\).

§.§ Deep tie-breaking

We implement OP with tie-breaking as described in Section <ref> (see Algorithm <ref>).

Input:Dec-POMDP \(\DecPSecond\)
OP learning algorithm \(\LA^\OP\)
Tie-breaking-function \(\chi\)
Number of seeds \(K\)
Output: Joint policy \(\Policy^*\in\PolicySet^\DecPSecond\)
\(k=1\) to \(K\)
Train policy \(\Policy^{(k)}\sim\sigma^\OP(\DecPSecond)\)
Calculate tie-breaking value \(x^{(k)}\leftarrow \chi(\DecPSecond,\Policy^{(k)})\)

\(k_\mathrm{max}\leftarrow\argmax_{k=1}^Kx^{(k)}\)
\(\Policy^*\leftarrow \Policy^{(k_\mathrm{max})}\)
Return \(\Policy^*\)

OP with tie-breaking

Turning to the tie-breaking function, the function is only applied to actions of both agents and to rewards, but not to observations or states. This is because in our problems, states are always the same, and observations are completely determined by actions. The hash network has four hidden layers with ReLu activation functions, a hidden dimension of \(32\), and weights and biases are initialized uniformly in \([-1,1]\). We chose these hyperparameters mostly based on prior considerations, but we did compare neural network depths 2 to 5 and hidden-layer dimensions 8, 16, 32 and 64 to determine hyperparameters for which OP with tie-breaking performed well. To calculate the tie-breaking function, we use 2048 episode samples. See Algorithm <ref> for pseudo code.

Input:Dec-POMDP \(\DecPSecond\)
Policy \(\Policy\in\PolicySet^\DecPSecond\)
Neural network architecture \(\NN_\Hash\)
Random seed \(n\)
Number of episode samples \(K\)
Tie-breaking value \(\chi(\DecPSecond,\Policy)\)
Initialize \(\NN_\Hash\) using random seed \(n\)
\(k=1\) to \(K\)
Sample profile of automorphisms \(\AutProfile^{(k)}\sim\U(\Aut(\DecPSecond)^\PlayerSet)\)
Sample history \(\History^{(k)}\sim\Prob^\DecPSecond_{{\AutProfile^{(k)}}^*\Policy}\)
\(\chi(\DecPSecond,\Policy)\leftarrow \frac{1}{N!K} \sum_{k=1}^K\sum_{\Isom_N\in\mathrm{Bij}(\PlayerSet)}\NN_\Hash(\Isom_N(\iota(\History^{(k)}))\)
Return \(\chi(\DecP,\Policy)\)

Tie-breaking function

§.§ Cross-play evaluation

Recall that, to evaluate algorithms in the LFC problems for our environments, we simplify the objective to

\begin{equation}
\tilde{U}^\DecP(\LA):=
\E_{\Policy^{(i)}\sim\LA(\DecP),\,i=1,2}
\Big[
\E_{\AutProfile_i\sim \U(\Aut(\DecP)),\,i=1,2}\Big[
\\
\end{equation}

We discuss this simplification further in Appendix <ref>.

For each game, we train 320 joint policies in total, using OP with different seeds for network initialization and environmental randomness.  In the two-stage lever game, we train each policy for three million environment steps, and in the variant with asymmetric players for five million steps (see Figure <ref> for learning curves).  The training for both environments took around three days on a MacBook Pro laptop from 2017. We split the 320 policies into 10 sets of 32 policies each.  The policies in each set are used for application of the tie-breaking method, while the 10 different sets represent independent runs which can be used to calculate cross-play values.

Two-stage lever game

Asymmetric lever game

Learning curves for 320 independent training runs of the OP algorithm, with shaded standard deviation.

Given a list of 10 policies \(\Policy^{(1)},\dotsc,\Policy^{(10)}\) produced by independent runs of an algorithm, we estimate the cross-play value \(G_{k,l}\approx\E_{\AutProfile_i\sim \U(\Aut(\DecP)),\,i=1,2}\left[
J((\AutProfile_1^*\Policy^{(k)})_1,(\AutProfile_2^*\Policy^{(l)})_2)\right]\) for any two indices of policies \(k, l\in\{1,\dotsc,10\}\). These values are used to print cross-play matrices (Figure <ref>) The average off-diagonal cross-play value is calculated as \(G:=\frac{1}{10(10-1)}\sum_{k\neq l}G_{k,l}\), where we leave out values on the diagonal because these do not represent cross-play between independent runs. Note that in the two-stage lever game, off-diagonal values can be higher than the optimal OP value. This is because in cross-play, agents can use different joint policies that accidentally work better in cross-play than a symmetric policy. It is counterbalanced in expectation by other entries of the matrix, in which unsuitable agents are matched. We provide in Table <ref> the average off-diagonal cross-play values used to create the graph in Figure <ref>.

Lastly, we categorize policies into classes of mutually compatible policies. To do so, we calculate a cross-play value for each combination of two out of the \(320\) trained joint policies, using \(256\) episodes each. We then dynamically build classes of policies by comparing a policy's expected return to the cross-play value with a policy from a given class, and assigning the policy to that class if the difference between the values is below a threshold of \(0.6\). If no class is compatible with a policy, the method creates a new class containing that policy. In that way, all 320 policies are assigned to a class. In Table <ref> we list the relative sizes of the different classes.

While in the two-stage lever game, both classes are represented approximately equally, a clear majority of policies belongs to one class in the asymmetric lever game. This class corresponds to the strategy in which player 2 switches to a different action upon non-coordination in the first round, and in which both players repeat their action given successful coordination in the first round. The least frequent class was the one in which player 2 switches to a different action upon non-coordination, but where both players switch to a different action if they were successful in the first round. The imbalance of classes in this case could be used to implement a tie-breaking rule that chooses the policy that is learned more often.

We think that a reasonable policy in the two-stage lever game is one in which a player repeats their action upon coordination.  Hence, a tie-breaking function that chooses the “repeat”-policy is preferable.  Interestingly, out of 20 seeds for the hash function, only 4 of the resulting tie-breaking functions gave higher values to that policy.

We used new random seeds for the final experiments that have not been used to improve the method.

Average off-diagonal cross-play value and standard deviation for OP with tie-breaking with \(K=1\), 2, 4, 8, 16, and 32, in the two-stage lever game (TSLG) and asymmetric lever game (ALG).

Problem     1   2   4   8   16   32

TSLG     -0.03 (±0.00)     0.14 (±0.13)     0.48 (±0.06)     0.50 (±0.00)     0.50 (±0.00)     0.50 (±0.00)

ALG       0.90 (±0.00)     1.23 (±0.08)     1.75 (±0.22)     1.90 (±0.16)     1.96 (±0.11)     1.97 (±0.10)

Percentage of policies learned corresponding to different classes of mutually compatible policies, for two-stage lever game (TSLG) and asymmetric lever game (ALG), each time out of 320 seeds for training.

Problem     Class 1     Class 2     Class 3     Class 4

TSLG    50.94%    49.06%    /     /

ALG    43.75%    20.94%    19.38%       15.94%

§ FORMALIZATION OF A LABEL-FREE COORDINATION GAME AND PROBLEM

In this section, we formalize label-free coordination (LFC) games and the LFC problem, and we provide auxiliary results required to prove our main theorems.

In Appendix <ref>, we recall the definition of Dec-POMDPs and introduce some additional notation. In Appendix <ref>, we recall the definition of isomorphisms and automorphisms, provide more comprehensive examples, and prove first lemmas about these concepts. Afterwards, in Appendix <ref>, we discuss the pushforward and prove, among other things, that a pushforward policy has the same expected return as the original policy.  In Appendix <ref>, we show that automorphisms define group actions on joint actions, policies, etc. and introduce the concept of an orbit. In Appendix <ref>, we then introduce Dec-POMDP labels to construct the set of relabeled Dec-POMDPs used to define an LFC game. In Appendix <ref>, we recall the definition of LFC games and of the LFC problem, and we provide different expressions for the payoff in LFC games. We also prove that LFC games for isomorphic Dec-POMDPs are equivalent, up to a permutation of the principals in the game. In Appendix <ref>, we prove that any strategy profile that is optimal among those that respects symmetries between principals is a Nash equilibrium in the game, making use of group actions and orbits. This theorem is needed later to prove that all principals using OP with tie-breaking is a Nash equilibrium. Lastly, in Appendix <ref>, we briefly discuss a condition under which the objective in the LFC problem is equivalent to the formulation without relabeled Dec-POMDPs used in our experiments as outlined in Section <ref>.

§.§ Recapitulation of Dec-POMDPs

Before we turn to isomorphisms and automorphisms, we briefly recapitulate Dec-POMDPs and introduce some additional notation that we will use throughout the following. That is, we also introduce a history of length \(t\), \(\History_t\in\HistorySet_t\), the set of deterministic policies \(\PolicySetDet\) and we define the measure space \((\Omega,\PowerSet(\Omega),\Prob_\Policy)\) corresponding to a Dec-POMDP in which agents follow the joint policy \(\Policy\). We also define the notation \(x_{-i}:=(x_1,\dotsc,x_{i-1},x_{i+1},\dotsc x_N)\) and the projection operator \(\Proj_i(x)=x_i\). Apart from this, the definitions in this section are a more elaborate version of those in Section <ref> of the main text.

To begin, recall the definition of a Dec-POMDP.

A (finite-horizon) Dec-POMDP is a tuple

\[
\DecP=\Big(\PlayerSet,\StateSet,\ActionSet=\prod_{i\in \PlayerSet}\ActionSet_{i},P,\RewardFunction,\ObservationSet=\prod_{i\in \PlayerSet}\ObservationSet_{i},O,b_{0},\Tmax\Big)
\]

* $\mathcal{N}=\{1,\dots,N\}$, \(N\in\mathbb{N}\) is a finite set of agents.

* $\StateSet$ is a finite set of states.

* $\ActionSet_{i}$ is a finite set of actions for player $i\in\PlayerSet$.

* $P\colon\StateSet\times\ActionSet\rightarrow\Delta(\StateSet)$
is the transition probability kernel (where $\Delta(\StateSet)$ denotes the
set of probability mass functions over $\StateSet$).

* $\RewardFunction\colon\StateSet\times\ActionSet\rightarrow\mathbb{R}$ is
the joint reward function.

* $\ObservationSet_{i}$ is a finite set of observations for player $i\in\PlayerSet$.

* $O\colon\StateSet\times\ActionSet\rightarrow\Delta(\ObservationSet)$ is
the observation probability kernel.

* $b_{0}\in\Delta(\StateSet)$ is a distribution over the initial

* $\Tmax\in\mathbb{N}_0$ is the horizon of the problem.

When considering different Dec-POMDPs \(\DecP,\DecPSecond\) at the same time, we write \(\ActionSet^\DecP,\ActionSet^\DecPSecond\), etc., to indicate to which Dec-POMDP the set belongs. Similarly, we do this for transition, observation, and reward functions. We omit the index \(\DecP\) if it is clear which Dec-POMDP is meant.

Given a Dec-POMDP \(\DecP\), define the set of local action-observation histories of length \(t\in\{0,\dotsc,\Tmax\}\) for player
\(i\in\PlayerSet\) as

\[\AOHistorySet_{i,t}:=\left(\ActionSet_{i}\times\ObservationSet_{i}\right)^t,\]

(where \(\left(\ActionSet\times\ObservationSet\right)^0:=\{\emptyset\}\))
and the set of local action-observation histories for player \(i\) as

\[\AOHistorySet_{i}:=\bigcup_{0\leq t\leq \Tmax}\left(\ActionSet_{i}\times\ObservationSet_{i}\right)^t.\]

Moreover, we define the set of histories of length \(t\) as

\[\HistorySet_t:=\StateSet\times\ActionSet\times\RewardFunction(\StateSet\times\ActionSet)\times\left(\StateSet\times\ObservationSet\times\ActionSet\times\RewardFunction(\StateSet\times\ActionSet)\right)^t.\]

and \(\HistorySet:=\HistorySet_\Tmax\) as the set of histories. Histories \(\History\in\HistorySet\) are also called episodes, when one is talking about a particular sample of the stochastic process induced by agents following a policy in the Dec-POMDP, as defined below.

At step \(0\leq t\leq \Tmax\), agent \(i\in\PlayerSet\) chooses a distribution over actions, conditional on a past action-observation history \(\AOHistory_{i,t}\in \AOHistorySet_{i,t}\).

This choice is described by a local (stochastic) policy for player $i$, which is a mapping $\Policy_{i}\colon\AOHistorySet_{i}\rightarrow\Delta(\ActionSet_{i})$. Since actions can be chosen stochastically, a policy and past observations do not imply which past actions have been taken, so policies are also able to condition on past actions (i.e., agents remember their past actions). We write \(\Policy_i(\Action_i\mid\AOHistory_{i,t})\) for the probability of action \(\Action_i\in\ActionSet_i\) given the action-observation history \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\). A (joint stochastic) policy is a tuple $\Policy=(\Policy_{1},\dots,\Policy_{N})$
with a local policy for each player.
We denote $\PolicySet^\DecP$ as the set of joint stochastic policies for a Dec-POMDP $D$, and
$\PolicySet^{D}_{i}$ as the set of local policies for player $i$.
A local deterministic policy for player \(i\in\PlayerSet\) is defined as a

policy $\Policy_{i}$
such that $\Policy_{i}(\cdot \mid\AOHistory_{i,t})$ is concentrated on exactly one action (i.e., there exists \(\Action_i\in\ActionSet_i\) such that \(\Policy_{i}(\Action_i\mid\AOHistory_{i,t})=1\)) for
each $\AOHistory_{i,t}\in\AOHistorySet_{i,t}$.
A joint deterministic policy is defined analogously to joint stochastic policies, and \((\PolicySet^0)^\DecP\) is the set of joint deterministic policies for \(\DecP\).[Normally, a deterministic policy is defined as having values in \(\ActionSet_i\), but we can identify each element $\Action_i\in\ActionSet_{i}$
with a probability mass function in $\Delta(\ActionSet_{i})$ with support $\{\Action_i\}$, so these definitions are interchangeable. Since a deterministic policy outputs only one action for each action-observation history, it there is only one possible action for each observation history \((\Observation_{i,1},\dots,\Observation_{i,t})\), and we could hence write a deterministic policy as a map from observation histories to actions. We omit this here for simplicity.]

A Dec-POMDP \(\DecP\) together with a joint policy \(\Policy\in\PolicySet^\DecP\) specify the stochastic process according to which an episode evolves, yielding a distribution over histories. Formally, we define a discrete probability space \((\Omega,\PowerSet(\Omega),\Prob_\Policy)\) with random variables for states, actions, observations, and rewards at all time steps.

The distributions of these random variables are defined inductively in the following way. First, $S_{0}\sim b_{0}$, that is, the first state is an independent random variable with values in \(\StateSet\) and image distribution \(b_0\). Similarly, the first action of agent \(i\) is distributed according to $A_{i,0}\sim\Policy_{i}(\cdot\mid \emptyset)$ (note that \(\emptyset\in\AOHistorySet_i\) by definition), and the first reward is $R_{0}:=\RewardFunction(S_{0},A_{0})$, where we define \(\ActionRV_0:=(\ActionRV_{i,0})_{i\in\PlayerSet}\).

Now assume there are random variables for all states, actions, and observations until step \(0\leq t\leq\Tmax\) (in the case \(t=0\), there are no observations defined yet). We can summarize them into a random variable for the history of length \(t\) as

\[\HistoryRV_{t}:=(\StateRV_0,\ActionRV_0,(\StateRV_{t'},(\ObservationRV_{i,t'},\ActionRV_{i,t'})_{i\in\PlayerSet},\RewardRV_{t'})_{1\leq t'\leq t})\]

(and we let \(\HistoryRV:=\HistoryRV_\Tmax\)).
At step \(t+1\), a new state \(S_{t+1}\sim P(\cdot\mid S_{t},A_{t})\) and a new joint observation \(O_{t+1}\sim O(\cdot\mid S_{t+1},A_{t})\) are sampled. Note that, in a slight abuse of notation, we use \(\ObservationRV\) for both observation probabilities and observation random variable. We can define a random variable for the action-observation history of agent \(i\) at time \(t+1\) as $\AOHistoryRV_{i,t+1}:=(A_{i,0},O_{i,1},A_{i,1},\dotsc,A_{i,t},O_{i,t+1})$. Conditioning on this action-observation history, agent \(i\) samples an action $A_{i,t+1}\sim\Policy_{i}(\cdot \mid \AOHistoryRV_{i,t+1})$. This yields a new joint action \(\ActionRV_{t+1}\). Finally, the new reward is
$R_{t+1}:=\RewardFunction(S_{t+1},A_{t+1})$, which concludes the definition.

We will sometimes make use of a simplified notation for a tuple excluding a particular player. Let \((x_i)_{i\in\PlayerSet}\) be a vector indexed by agents, with elements \(x_i\in \mathcal{X}_i\) where \(\mathcal{X}_i, i\in\PlayerSet\) are some sets. Then we define \(x_{-j}:=(x_1,\dotsc,x_{j-1},x_{j+1},\dotsc,x_N)\) for \(j\in\PlayerSet\). Moreover, for any \(x'_i\in X_i\), we then write \((x'_i,x_{-i}):=(x_1,\dotsc,x_{i-1},x_i',x_{i+1},\dotsc,x_N)\). We will also sometimes use the projection operator \(\Proj_i(x):=x_i\) to clearly refer to a particular element of \(x\) when \(x\) is a more complicated expression.

Now, given a problem \(\DecP\) and a joint policy \(\Policy\in\PolicySet^\DecP\), the measure \(\Prob_\Policy\) defined above specifies a distribution over rewards \(\RewardRV_0,\dotsc,\RewardRV_\Tmax\). We can use this fact to define the expected return of the policy. To that end, let $\E_{\Policy}:=\E_{\Prob_\Policy}$ denote the expectation with respect to \(\Prob_\Policy\).

Let \(\DecP\) be a Dec-POMDP. Define the self-play (SP) objective \(J^\DecP\colon \PolicySet^\DecP\rightarrow\mathbb{R}\) for \(\DecP\) via

\[J^{\DecP}(\Policy):=\E_{\Policy}\left[\sum_{t=0}^{\Tmax}R_{t}\right]\]

for \(\Policy\in\PolicySet^\DecP\). Here, \(J^\DecP(\Policy)\) is called the expected return of a joint policy $\Policy$.

§.§ Dec-POMDP isomorphisms and automorphisms

Here, we recall the definitions of isomorphisms and automorphisms from Sections <ref> and <ref> and give more comprehensive examples than in the main text. Then we prove some elementary results.

Let \(\DecP,\DecPSecond\) be two Dec-POMDPs. Consider a tuple of bijective maps

\[\Isom:=(\Isom_{N},\Isom_{S},(\Isom_{A_i})_{i\in\PlayerSet},(\Isom_{O_i})_{i\in\PlayerSet}),\]

_N      𝒩^→^

_S      ^→^

∀i∈     _A_i      _i^→^__N(i)

∀i ∈     _O_i      _i^→__N(i)^.

Given a joint action \(\Action\in\ActionSet^\DecP\) and such tuple \(\Isom\), we define
\begin{equation}\label{eq:13appendix}
\Isom_A(\Action):=\left(\Isom_{A_{\Isom^{-1}_N(i)}}\Action_{\Isom^{-1}_N(i)}\right)_{i\in\PlayerSet^\DecPSecond}\in\ActionSet^\DecPSecond,
\end{equation}

and analogously for \(\Observation\in\ObservationSet^\DecP\)

\begin{equation}\label{eq:14appendix}
\Isom_O(\Observation):=\left(\Isom_{O_{\Isom^{-1}_N(i)}}\Observation_{\Isom^{-1}_N(i)}\right)_{i\in\PlayerSet^\DecPSecond}\in\ObservationSet^\DecPSecond.\end{equation}

That is, in the joint action \(\Isom_A(\Action)\in\ActionSet^\DecPSecond\), the agent \(j=\Isom_N(i)\in\PlayerSet^\DecPSecond\) (where \(i\in\PlayerSet^\DecP\)) plays the action \(\Isom_{A_i}(a_i)\in\ActionSet_j^\DecPSecond\).
Note that it is really \(f_A(a)\in\ActionSet^\DecPSecond\), as for any $a\in\ActionSet^\DecP$ and \(j:=f_{N}^{-1}(i)\in \PlayerSet^\DecP\), by definition it is

\[f_{A_{j}}(a_{j})\in\ActionSet^\DecPSecond_{f_{N}(j)}=\ActionSet^\DecPSecond_{f_{N}(f_N^{-1}(i))}=\ActionSet^\DecPSecond_{i}.\]

The analogous holds for observations.

Let $\DecP,\DecPSecond$ be Dec-POMDPs such that both have the same horizon \(\Tmax^\DecP=\Tmax^\DecPSecond\), and let
\[\Isom:=(\Isom_{N},\Isom_{S},(\Isom_{A_i})_{i\in\PlayerSet},(\Isom_{O_i})_{i\in\PlayerSet})\]
be a tuple of bijective maps as defined in equations (<ref>)–(<ref>). Then \(\Isom\) is an isomorphism from \(\DecP\) to \(\DecPSecond\) if
for any \(\Action\in\ActionSet^\DecP\), \(s,s'\in\StateSet^\DecP\) and \(o\in\ObservationSet^\DecP\), it is

\begin{align}
P^\DecP(s'\mid s,a)= & P^\DecPSecond(f_{S}(s')\mid f_{S}(s),f_A(a))\label{eq:2appendix}\\
O^\DecP(o\mid s,a)= & O^\DecPSecond(f_{O}(o)\mid f_{S}(s),f_A(a))\label{eq:3appendix}\\
\RewardFunction^\DecP(s,a)= & \RewardFunction^\DecPSecond(f_{S}(s),f_A(a))\label{eq:4appendix}\\
b^\DecP_{0}(s)= & b_{0}^\DecPSecond(f_{S}(s)).
\end{align}

If such an isomorphism exists, $\DecP$ and $\DecPSecond$ are called isomorphic. We denote $\Iso(D,E)$ for the set of isomorphisms from \(D\) to \(E\).

In a Dec-POMDP, distributions over histories and policies can be ranked by their associated expected return. If a reward function is multiplied with a positive constant \(\alpha\in\mathbb{R}_{>0}\) and shifted by a constant \(\beta\in\mathbb{R}\), then the new reward function \(\RewardFunction':= \alpha\RewardFunction+\beta\) still induces the same ranking. For this reason, one could consider such transformations as part of an isomorphism between two problems. For instance, [][p. 72]harsanyi1988general make it part of their definition of an isomorphism in the framework of standard-form games.
For simplicity, we ignore this complication here and consider only isomorphic problems with reward functions that have the same range.

As in the main text, we write \(fa\) instead of \(f_A(a)\) and \(f\Action_i\) instead of \(f_{A_i}\Action_i\), and we do the same for observations, states, etc. We also write \(f\AOHistory_{i,t}\) for actions of isomorphisms on action-observation histories, which is defined as the element-wise application of \(f\), and letting \(\Isom \Reward := \Reward\) for rewards, we define \(\Isom\History\) for entire histories \(\History\in\HistorySet\).

Now we prove a first basic result about actions of isomorphisms. Note that an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) is a bijective map

\begin{equation}
\label{eq:isomorphisms-is-bijective-map}
\Isom\colon \PlayerSet^\DecP\times\StateSet^\DecP\times\prod_{i\in\PlayerSet^\DecP}\ActionSet^\DecP_i\times\prod_{i\in\PlayerSet^\DecP}\ObservationSet^\DecP_i\rightarrow\PlayerSet^\DecPSecond\times\StateSet^\DecPSecond\times\prod_{i\in\PlayerSet^\DecPSecond}\ActionSet^\DecPSecond_{\Isom i}\times\prod_{i\in\PlayerSet^\DecPSecond}\ObservationSet^\DecPSecond_{\Isom i},
\end{equation}

which can be inverted and composed with other maps. The
following result shows that actions of isomorphisms on joint actions and joint observations are compatible with function composition and with taking inverses of functions. It follows that also the element-wise application to histories and action-observation histories is compatible in this way. In particular, this justifies omitting brackets when applying isomorphisms. We will use this lemma liberally in the following.

Let \(\DecP,\DecPSecond,\DecPThird\) be Dec-POMDPs, \(\Action\in\ActionSet^\DecP,\Observation\in\ObservationSet^\DecP\), let \(\Id\in\Iso(\DecP,\DecP)\) be the identity, and let \(\Isom\in\Iso(\DecP,\DecPSecond)\), \(\IsomSecond\in\Iso(\DecPSecond,\DecPThird)\). Then it is

\(\Id\Action=\Action\) and \(\Id\Observation=\Observation\).

(ii) \(\IsomSecond(\Isom\Action)=(\IsomSecond\circ\Isom)\Action\) and \(\IsomSecond(\Isom\Observation)=(\IsomSecond\circ\Isom)\Observation\).

In particular, actions of isomorphisms \(\Isom\) on joint actions and joint observations can be inverted using \(\Isom^{-1}\).

First, it is $\Id a=(\Id a_{\Id ^{-1}i})_{i\in\mathcal{N}}=\Id $,
and analogously for $o$. Second,

\[
\IsomSecond(\Isom a)=\IsomSecond(\Isom a_{\Isom ^{-1}i})_{i\in\mathcal{N}}=(\IsomSecond(\Isom a_{\Isom ^{-1}\IsomSecond^{-1}i}))_{i\in\mathcal{N}}=(\IsomSecond \Isom a_{(\IsomSecond \Isom )^{-1}i})_{i\in\mathcal{N}}=(\IsomSecond\circ \Isom )a
\]

as function composition is associative and the inverse of $\IsomSecond\circ \Isom$ is
$\Isom^{-1}\circ \IsomSecond^{-1}$.

Next, it follows from the previous that \(\Isom^{-1}(\Isom \Action)= (\Isom^{-1}\circ\Isom)\Action = \Id \Action=\Action\). The analogous holds for \(\Observation\), which concludes the proof.

The following corollary states that the action of \(\Isom\) on histories \(\History_t\in\HistorySet_t\) is bijective. An analogous corollary also hold for action-observation histories.

Let \(\DecP,\DecPSecond\) be isomorphic Dec-POMDPs with isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) and let \(t\in\{0,\dotsc,\Tmax\}\). Then \(\Isom_H\colon \HistorySet_t^\DecP\rightarrow\HistorySet_t^\DecPSecond,\History_t\mapsto\Isom\History_t\) is a bijective map.

Let \(\History_t=(\State_0,\Action_0,\State_1,\Observation_1,\Action_1,\Reward_1,\dotsc,\State_t,\Observation_t,\Action_t,\Reward_t)\in\HistorySet^\DecP_t\).
Define \(\Isom_H\) as above and \(\Isom_H^{-1}\colon \History\mapsto\Isom^{-1}\History\). Then

\begin{multline}\Isom^{-1}(\Isom(\History_t))
\Isom^{-1}((\Isom\State_0,\Isom\Action_0,\Isom\State_1,\Isom\Observation_1,\Isom\Action_1,\Isom\Reward_1,\dotsc,\Isom\State_t,\Isom\Observation_t,\Isom\Action_t,\Isom\Reward_t))
\\
\\
\overset{\text{Lemma~\ref{lemma-action-function-composition-compatible}}}{=}
\end{multline}

Recall the definition of an automorphism, which can be thought of as describing a symmetry of the Dec-POMDP.

An isomorphism $f\in \Iso(D,D)$ from $D$ to itself
is called an automorphism. We define $\Aut(D):=\text{\ensuremath{\Iso(D,D)}}$ as the set
of all automorphisms of $D$.

Now we give an example of an isomorphism and automorphism, using the lever coordination game.

[Lever coordination game]
Consider the lever coordination game introduced in Section <ref>. This can be formalized as a Dec-POMDP \(\DecP\) with only one state, one observation for each agent, and in which \(\Tmax=0\). The agents are \(\PlayerSet=\{1,2\}\) and actions are \(\ActionSet_1=\ActionSet_2=\{1,\dotsc,10\}\). One possible reward function is
\[\RewardFunction(\Action_1,\Action_2,\State)=\delta_{\Action_1,\Action_2}\left(1.0\cdot\mathds{1}_{\{1,\dotsc,9\}}(a_1)+0.9\cdot\mathds{1}_{\{10\}}(a_1)\right),\]

\[\delta_{\Action_1,\Action_2}:=\begin{cases}1&\text{if }\Action_1=\Action_2\\0&\text{otherwise}\end{cases}\]

is the Kronecker delta.

As an isomorphic problem \(\DecPSecond\), consider a problem with the same sets of actions for both players, but where the reward function is defined as

\[\RewardFunction^\DecPSecond(\Action_1,\Action_2,\State)=\delta_{\Action_1,\Action_2}\left(1.0\cdot\mathds{1}_{\{2,\dotsc,10\}}(a_1)+0.9\cdot\mathds{1}_{\{1\}}(a_1)\right)\]

for \(\Action_1\in\ActionSet_1,\Action_2\in\ActionSet_2\) and the trivial state \(\State\).
Note that this is formally a different Dec-POMDP. Nevertheless, we can define an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) in the following way. For \(i=1,2\), define \(\Isom_{A_i}\colon\ActionSet_i\rightarrow\ActionSet_i\) such that \(\Isom_{A_i}(10)=1\) and \(\Isom_{A_i}(1)=10\), and let \(\Isom_{A_1}=\Isom_{A_2}\) be arbitrary otherwise. Let the remaining components of \(\Isom\) be the identity map. Then for any joint action \(\Action\) and the trivial state \(\State\), it is

\begin{multline}
\RewardFunction^\DecPSecond(\Isom \State,\Isom\Action)=\delta_{\Isom\Action_1,\Isom\Action_2}\left(1.0\cdot\mathds{1}_{\{2,\dotsc,10\}}(\Isom a_1)+0.9\cdot\mathds{1}_{\{1\}}(\Isom a_1)\right)
\\

and hence \(\DecP\) and \(\DecPSecond\) are isomorphic (as observation and transition probabilities as well as the initial state distribution are trivial here).

Note that we could have used any two (potentially different) permutations \(\hat{\Isom}_1,\hat{\Isom}_2\) of the two sets \(\ActionSet_1,\ActionSet_2\) and defined a new reward function \(\RewardFunction'(\State,\Action):=\RewardFunction^{\DecP}(\State,\hat{\Isom}_1^{-1}\Action_1,\hat{\Isom}_2^{-1}\Action_2)\). This reward function would then define a new Dec-POMDP \(\DecP'\), and the isomorphism from \(\DecP\) to \(\DecP'\) would be exactly \(\Isom\) defined by \(\Isom_{A_1}=\hat{\Isom}_1,\Isom_{A_2}=\hat{\Isom}_2\) and the identity in the other components, as \(\RewardFunction'(\Isom\State,\Isom\Action)=\RewardFunction^{\DecP}(\State,\Isom_{A_1}\hat{\Isom}_1^{-1}\Action_1,\Isom_{A_2}\hat{\Isom}_2^{-1}\Action_2)=\RewardFunction^{\DecP}(\State,\hat{\Isom}_1\hat{\Isom}_1^{-1}\Action_1,\hat{\Isom}_2\hat{\Isom}_2^{-1}\Action_2)=\RewardFunction^\DecP(\State,\Action)\). We will use this idea in Section <ref> to define relabeled Dec-POMDPs.

Next, consider the automorphisms of the lever coordination game. Note that the agents in this game are symmetric. For instance, we can define \(\Auto\) via \(\Auto_N(1)=2\) and \(\Auto_N(2)=1\), and such that \(\Auto_{A_1}=\Auto_{A_2}=\hat{\Auto}\), where \(\hat{\Auto}\) is any permutation of \(\{1,\dotsc,10\}\) such that \(\hat{\Auto}(10)=10\). Then one can easily check that \(\RewardFunction^\DecP(\Auto\State,\Auto\Action)=\RewardFunction^\DecP(\State,\Action)\) for any joint action \(\Action\) and the state \(\State\).

Next, we introduce the automorphisms of the two-stage lever game (Example <ref>), which we will need later to prove that OP is suboptimal in the corresponding LFC problem.

Recall that in the two-stage lever game, there are two agents, \(\PlayerSet=\{1,2\}\), and the problem has two rounds, so \(\Tmax=1\). Each round, each agent has to pull one of two levers, \(\mathcal{A}_1=\mathcal{A}_2=\{1,2\}\). If both agents choose the same lever, they get a reward of \(1\). Otherwise, the reward is \(-1\). There is again only one state, but there are two observations, \(\ObservationSet_1=\ObservationSet_2=\{1,2\}\). In the second stage (\(t=1\)), each player observes the previous action of the other player, so \(\ObservationRV_{i,1}=\ActionRV_{-i,0}\) for \(i=1,2\). The reward and observation probabilities are given in Table <ref>.

Reward function and observation probabilities in the two-stage lever game (Example <ref>).

Reward function \(\RewardFunction(\State,\Action)\) for each joint action \(\Action\)

\(\Action\)     \(\RewardFunction(\State,\Action)\)

(1,1)      1

(1,2)     -1

(2,1)      -1

(2,2)     1

Observation probabilities \(O(\Observation\mid\State, \Action)\) for joint observations \(\Observation\) and joint actions \(\Action\).

\( \Action\,\backslash\, \Observation\)     (1,1)     (1,2)     (2,1)     (2,2)

(1,1)      1     0     0     0

(1,2)     0     0     1     0

(2,1)      0     1     0     0

(2,2)     0     0     0    1

Using the table for reward function and observation probabilities, we can easily visualize isomorphisms and automorphisms. Consider any isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) where \(\DecPSecond\) is some other Dec-POMDP. Considering, for instance, the reward function, we know that \(\RewardFunction^\DecP(\State,\Action)=\RewardFunction^\DecPSecond(\Isom \State,\Isom\Action)\). This means that if we want to check the value of the reward function of \(\DecPSecond\) when agents choose action \(\Isom\Action\), we can look it up in the table corresponding to \(\RewardFunction^\DecP\) in the row for \(\Action\). So we can visualize an isomorphism by applying \(\Isom_A\) to the index (i.e., first) column of this table, but leaving the other cells unchanged. This creates a new table with the reward function for \(\DecPSecond\), or, equivalently, this new table corresponds to the reward function \(\RewardFunction^\DecP\) precomposed with \(\Isom^{-1}\), i.e., \(\RewardFunction^\DecP(\Isom^{-1}_S\cdot,\Isom^{-1}_A\cdot)=\RewardFunction^\DecPSecond\).
Analogously, we can apply \(\Isom_{O}\) to the header row and \(\Isom_A\) to the index column of the table with observation probabilities, yielding \(O^\DecP(\Isom^{-1}_O\cdot\mid \Isom^{-1}_S\cdot ,\Isom^{-1}_A\cdot)=O^\DecPSecond\).
An automorphism is then simply an isomorphism such that applying it to index column and header of the tables does not change the table, other than permuting rows and columns.

Now let \(\Auto\) be an automorphism. \(\Auto_N\) can either be the identity or it can switch both agents. In either case, it must be \(\Auto_{A_1}=\Auto_{A_2}\), which can also either be the identity or the map that switches the actions. The observation permutation then has to be equal to that of the actions, \(\Auto_{O_1}=\Auto_{O_2}=\Auto_{A_1}\). There is trivially only one option for the state permutation.

Visualization of precomposition of both reward function and observation probability kernel with \(\Auto^{-1}\), by applying \(\Auto\) to the index column and header row of the tables from Table <ref>. Note that apart from a permutation of rows and columns, the tables are identical to the ones in Table <ref>, showing that \(\Auto\) is an automorphism.

Reward function \(\RewardFunction(\Auto^{-1}\State,\Auto^{-1}\Action)\)

\(\Action\)     \(\RewardFunction(\State,\Action)\)

(2,2)      1

(1,2)     -1

(2,1)      -1

(1,1)     1

Observation probabilities \(O(\Auto^{-1}\Observation\mid\Auto^{-1}\State,\Auto^{-1}\Action)\)

\( \Action\,\backslash\, \Observation\)     (2,2)     (1,2)     (2,1)     (1,1)

(2,2)      1     0     0     0

(1,2)     0     0     1     0

(2,1)      0     1     0     0

(1,1)     0     0     0    1

We visualize the application of the automorphism that switches agents as well as actions and thus also observations in Table <ref>. For instance, using the definition of actions of automorphisms on joint actions in Equations (<ref>) and (<ref>), we have \(\Isom_A(1,1)=(\Isom_{A_{\Isom_N 1}}1,\Isom_{A_{\Isom_N 2}}1)=(\Isom_{A_2}1,\Isom_{A_1} 1) = (2,2)\), and \(\Isom_A(1,2)=(\Isom_{A_2}2,\Isom_{A_1}1)=(1,2)\).

Before we turn to applying isomorphisms and automorphisms to policies, we briefly provide two basic results about isomorphisms and the relationship between isomorphisms and automorphisms.

First, we prove that function composition and inversion preserve isomorphisms.

Let \(\DecP,\DecPSecond,\DecPThird\) be Dec-POMDPs and let \(\Isom\in\Iso(\DecP,\DecPSecond)\) and \(\IsomSecond\in\Iso(\DecPSecond,\DecPThird)\). Then \(\Isom^{-1}\in \Iso(\DecPSecond,\DecP)\) and \(\IsomSecond\circ\Isom\in\Iso(\DecP,\DecPThird)\).

Let \(\State,\State'\in\StateSet^\DecP\), \(\Action\in\ActionSet^\DecP\). First, using the definition of an isomorphism and associativity of function composition, it is

\[
P^\DecP(s'\mid s,a)=P^\DecPSecond(fs'\mid fs,fa)=P^\DecPThird(\IsomSecond \Isom s'\mid \IsomSecond\Isom s,\IsomSecond\Isom a)
=P^\DecPThird((\IsomSecond\circ\Isom) s'\mid (\IsomSecond\circ\Isom) s,(\IsomSecond\circ\Isom) a)

An analogous calculation applies to observation probabilities, reward functions and initial state distribution. This shows
that \(\IsomSecond\circ\Isom\in\Iso(\DecP,\DecPThird)\).

Next, let \(\State',\State\in\StateSet^\DecPSecond\). Using Lemma <ref> and the definition of an isomorphism, it is

\[
P^\DecPSecond(s'\mid s,a)=P^\DecPSecond(ff^{-1}s'\mid ff^{-1}s,ff^{-1}a)=P^\DecP(f^{-1}s'\mid f^{-1}s,f^{-1}a)

Again, an analogous calculation applies to observation probabilities and the other relevant functions. This shows
that $f^{-1}\in\Iso(\DecPSecond,\DecP)$.

The next lemma shows that one can decompose isomorphisms into any isomorphism composed with an automorphism. Essentially, an isomorphism is a map from one Dec-POMDP to another, composed with a symmetry of that Dec-POMDP. This will be important later when we apply these concepts to define the LFC problem and show how OP relates to it.

Let \(\DecP,\DecPSecond\) be Dec-POMDPs and \(\Isom,\IsomSecond\in \Iso(\DecP,\DecPSecond)\). Then there exists exactly one \(\Auto\in\Aut(\DecPSecond)\) such that \(\Auto\circ\Isom=\IsomSecond\). Analogously, there exists exactly one \(\Auto\in\Aut(\DecP)\) such that \(\Isom\circ\Auto=\IsomSecond\). In particular, it is

\[\Iso(\DecP,\DecPSecond)=\Isom\circ\Aut(\DecPSecond)=\Aut(\DecP)\circ \Isom,
\]

where \(\Isom\circ\Aut(\DecPSecond):=\{\Isom\circ\Auto\mid\Auto\in\Aut(\DecPSecond)\}\) and \(\Aut(\DecP)\circ \Isom\) is defined analogously.

Existence: By Lemma <ref>, \(\Auto:=\IsomSecond\circ\Isom^{-1}\) is an isomorphism in \(\Iso(\DecPSecond,\DecPSecond)=\Aut(\DecPSecond)\), and it is \(\Auto\circ\Isom=(\IsomSecond\circ\Isom^{-1})\circ\Isom=\IsomSecond\).

Uniqueness: Assume \(\Auto\circ\Isom=\AutoSecond\circ\Isom=\IsomSecond\) for automorphisms \(\Auto,\AutoSecond\in\Aut(\DecPSecond)\). Then it follows that

\[\Auto=\Auto\circ(\Isom\circ\Isom^{-1})=(\Auto\circ\Isom)\circ\Isom^{-1}=(\AutoSecond\circ\Isom)\circ\Isom^{-1}=\AutoSecond.\]

The proof for the second part of the lemma is exactly analogous, but using \(\Auto:=\Isom^{-1}\IsomSecond\).

Turning to the “in particular” statement, the above shows that
\[\Iso(\DecP,\DecPSecond)\subseteq\Isom\circ\Aut(\DecPSecond)\]

\[\Iso(\DecP,\DecPSecond)\subseteq\Aut(\DecP)\circ\Isom.\]

The two inclusions in the other direction follow directly from Lemma <ref>.

§.§ Pushforward policies

Recall the definition of pushforward policies.

Let $\DecP,\DecPSecond$ be isomorphic Dec-POMDPs, let \(\Isom\in\Iso(\DecP,\DecPSecond)\), and let \(\Policy\in\PolicySet^\DecP\).
Then we define the pushforward $\Isom^*\Policy\in\PolicySet^\DecPSecond$ of \(\Policy\) by \(\Isom\) via

\[
(\Isom^{*}\Policy)_{i}(\Action_{i}\mid\AOHistory_{i,t}):=\Policy_{\Isom^{-1} i}(f^{-1}\Action_{i}\mid f^{-1}\AOHistory_{i,t})
\]

for all \(i\in\mathcal{N}^\DecPSecond,a_i\in\ActionSet_i^\DecPSecond,t\in\{0,\dotsc,\Tmax\},\) and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}^\DecPSecond\). That is, in the joint policy \(\Isom^*\Policy\), agent \(j\in\PlayerSet^\DecPSecond\) gets assigned the local policy \(\Policy_i\) of agent \(i:=\Isom^{-1}j\in\PlayerSet^\DecP\), precomposed with \(\Isom^{-1}\).

One can easily see that $f^{*}\Policy$ is a policy for the Dec-POMDP $\DecPSecond$.
Hence, when \(\Isom\) is an automorphism, \(\Isom^*\Policy\) is a policy for the same Dec-POMDP as \(\Policy\).

Like actions of isomorphisms on joint actions and observations, the pushforward is compatible with function composition, and it can be inverted using the inverse map \(\Isom^{-1}\).

Let \(\DecP,\DecPSecond\) and \(\DecPThird\) be Dec-POMDPs. Let \(\Policy\in\PolicySet^\DecP\), \(\Id\in\Aut(\DecP,\DecP)\) be the identity and \(\Isom\in\Iso(\DecP,\DecPSecond)\), \(\IsomSecond\in\Iso(\DecPSecond,\DecPThird)\). Then it is

(i) \(\Id^*\Policy=\Policy\).

(ii) \(\IsomSecond^*(\Isom^*\Policy)=(\IsomSecond\circ\Isom)^*\Policy\).

In particular, the pushforward can be inverted using the inverse map \(\Isom^{-1}\).

First, let \(i\in\PlayerSet^\DecP,\Action_i\in\ActionSet_i^\DecP,t\in\{0,\dotsc,\Tmax\}\), and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}^\DecP\). Then

\[(\Id^*\Policy)_i(\Action_i\mid \AOHistory_{i,t})=\Policy_{\Id i}(\Id \Action_i\mid \Id \AOHistory_{i,t})=\Policy_i(\Action_i\mid\AOHistory_{i,t}),\]

which shows that \(\Id^*\Policy=\Policy\).

Second, let \(i\in\PlayerSet^{\DecPThird},\Action_i\in\ActionSet^{\DecPThird}_i\) and \(\AOHistory_{i,t}\in\AOHistorySet^{\DecPThird}_{i,t}\).
Using Lemma <ref>, it is

\begin{multline}
(\IsomSecond^*(\Isom^*\Policy))_i(\Action_i\mid \AOHistory_{i,t})
(\Isom^*\Policy)_{\IsomSecond^{-1} i}(\IsomSecond^{-1} \Action_i\mid\IsomSecond^{-1}\AOHistory_{i,t})
=\Policy_{\Isom^{-1}(\IsomSecond^{-1} i)}(\Isom^{-1}(\IsomSecond^{-1}\Action_i)\mid\Isom^{-1}(\IsomSecond^{-1}\AOHistory_{i,t}))
\\\overset{\text{Lemma~\ref{lemma-action-function-composition-compatible}}}{=}\Policy_{(\Isom\circ\IsomSecond)^{-1} i}((\IsomSecond\circ\Isom)^{-1}\Action_i\mid(\IsomSecond\circ\Isom)^{-1}\AOHistory_{i,t})
\end{multline}

which proves that \(\IsomSecond^*(\Isom^*\Policy)=(\IsomSecond\circ\Isom)^*\Policy\).

Regarding the invertibility of the pushforward, note that by (ii), it is

\[(f^{-1})^*(f^*\Policy)\overset{\text{(ii)}}{=}(f^{-1}\circ f)^*\Policy=\Policy.\]

This concludes the proof.

One may wonder how pushforward policies and isomorphisms are related. In particular, how is the distribution over histories induced by a pushforward policy related to the distribution induced by the original policy? This question is answered by the following theorem, which we will use throughout this paper. The theorem demonstrates how the isomorphism from \(\DecP\) to \(\DecPSecond\) preserves the structure of the problem. It is similar to [][]kang2012exploiting's Theorem 3, which applies to automorphisms in POSGs and makes a statement about the expected returns of all agents under the pushforward policy. We will provide a result about expected returns as a corollary.

Let \(\DecP,\DecPSecond\) be isomorphic Dec-POMDPs, let \(\Isom\in\Iso(\DecP,\DecPSecond)\), and let \(\Policy\in\PolicySet^\DecP\). Then for any \(\History\in\HistorySet^\DecP\), it is

\[\Prob_{\Policy}(\HistoryRV^\DecP=\History)=\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond =\Isom \History).\]

In particular, for any \(i\in\PlayerSet,t\in\{0,\dotsc,\Tmax\}\) and \(\AOHistory_{i,t}\in\AOHistorySet_i\), it is
\[\Prob_{\Policy}(\AOHistoryRV_{ i,  t}= \AOHistory_{i,t})=\Prob_{\Isom^*\Policy}(\AOHistoryRV_{\Isom i,t}=\Isom\AOHistory_{i,t})

Proof by induction over \(t\in\{0,\dotsc,\Tmax\}\).

To start the induction, let \(\State\in\StateSet^\DecP,\Action\in\ActionSet,\Reward\in\mathbb{R}\) and \(\History_0:=(\State,\Action,\Reward)\in\HistorySet_0^\DecP\). Then it is

\begin{align}
\Prob_\Policy(\HistoryRV_0^\DecP=\History_0)
\\
b_0^\DecPSecond(\Isom\State)\prod_{i\in\PlayerSet^\DecP}\Policy_{\Isom^{-1}\Isom i}(\Isom^{-1}\Isom\Action_i\mid\emptyset)
\delta_{\RewardFunction^\DecPSecond(\Isom\State,\Isom\Action),\Reward}\label{eq:18}
\\
b_0^\DecPSecond(\Isom\State)\prod_{i\in\PlayerSet^\DecP}(\Isom^*\Policy)_{\Isom i}(\Isom\Action_i\mid\emptyset)
\delta_{\RewardFunction^\DecPSecond(\Isom\State,\Isom\Action),\Reward}\label{eq:19}
\\
\delta_{\RewardFunction^\DecPSecond(\Isom\State,\Isom\Action),\Reward}
\\
\Prob_{\Isom^*\Policy}(\HistoryRV_0^\DecPSecond=\Isom\History).\label{eq:20}
\end{align}

Here, in (<ref>), we use the definition of an isomorphism, in (<ref>) we use the definition of the pushforward policy, and in (<ref>) we use the definition of \(\Isom\Action\) from Equation (<ref>).

Next, let \(t>0\) and assume that it is \(\Prob_\Policy(\History^\DecP_{t-1}=\History_{t-1})=\Prob_{\Isom^*\Policy}(\History^\DecPSecond=\Isom\History_{t-1})\) for any \(\History_{t-1}\in\HistorySet_{t-1}\). Let
\[\History_t=(\dotsc,\State_{t-1},\Observation_{t-1},\Action_{t-1},\Reward_{t-1},\State_t,\Observation_t,\Action_t,\Reward_t)\in\HistorySet_t^\DecP\]

arbitrary, define \(\Action_{i,t}\) for \(i\in\PlayerSet\) such that \((\Action_{i,t})_{i\in\PlayerSet^\DecP}=\Action_t\), and define \(\AOHistory_{i,t}\) as the action-observation history  for player \(i\in\PlayerSet^\DecP\) corresponding to \(\History_{t}\).

If \(\Prob_\Policy(\HistoryRV^\DecP_{t-1}=\History_{t-1})=0\), then also \(\Prob_{\Isom^*\Policy}(\HistoryRV_{t-1}^\DecPSecond=\Isom\History_{t-1})=0\), and thus also

\[
\Prob_\Policy(\HistoryRV^\DecP_{t}=\History_{t})=0=\Prob_{\Isom^*\Policy}(\HistoryRV_{t}^\DecPSecond=\Isom\History_{t}).
\]

Thus, assume now that \(\Prob_\Policy(\HistoryRV^\DecP_{t-1}=\History_{t-1})>0\).
Then it is

\begin{align}
\\
&=P^\DecP(\State_t\mid \State_{t-1},\Action_{t-1})O^\DecP(\Observation_{t}\mid \State_{t},\Action_{t-1})
\prod_{i\in\PlayerSet^\DecP}\Policy_i(\Action_{i,t}\mid\AOHistory_{t})\delta_{\RewardFunction^\DecP(\State_t,\Action_t),\Reward}
\\
P^\DecPSecond(\Isom\State_t\mid \Isom\State_{t-1},\Isom\Action_{t-1})O^\DecPSecond(\Isom\Observation_{t}\mid \Isom\State_{t},\Isom\Action_{t-1})\label{eq:15}\\
\prod_{i\in\PlayerSet^\DecP}\Policy_{\Isom^{-1}\Isom i}(\Isom^{-1}\Isom\Action_{i,t}\mid\Isom^{-1}\Isom\AOHistory_{t})\delta_{\RewardFunction^\DecPSecond(\Isom\State_t,\Isom\Action_t),\Reward}
\\
P^\DecPSecond(\Isom\State_t\mid \Isom\State_{t-1},\Isom\Action_{t-1})O^\DecPSecond(\Isom\Observation_{t}\mid \Isom\State_{t},\Isom\Action_{t-1})\label{eq:16}\\
\prod_{i\in\PlayerSet^\DecP}(\Isom^*\Policy)_{\Isom i}(\Isom\Action_{i,t}\mid\Isom\AOHistory_{t})\delta_{\RewardFunction^\DecPSecond(\Isom\State_t,\Isom\Action_t),\Reward}
\\
P^\DecPSecond(\Isom\State_t\mid \Isom\State_{t-1},\Isom\Action_{t-1})O^\DecPSecond(\Isom\Observation_{t}\mid \Isom\State_{t},\Isom\Action_{t-1})
\\
\delta_{\RewardFunction^\DecPSecond(\Isom\State_t,\Isom\Action_t),\Reward}
\\
\Prob_{\Isom^*\Policy}(\StateRV_t^\DecPSecond=\Isom\State_t,\ObservationRV^\DecPSecond_t=\Isom\Observation_t,\ActionRV^\DecPSecond_t=\Isom\Action_t,\RewardRV^\DecPSecond_t=\Reward_t
\mid\HistoryRV^\DecPSecond_{t-1}=\Isom\History_{t-1}).\label{eq:17}
\end{align}

Again, we have used the definitions of isomorphism, pushforward policy, and Equations (<ref>) and (<ref>) in lines (<ref>), (<ref>), and (<ref>), respectively.
Using the inductive hypothesis, it follows that

\begin{align}\label{eq:21}&\Prob_\Policy(\HistoryRV^\DecP_t=\History_t)
\\
& =
\Prob_\Policy(\StateRV_t^\DecP=\State_t,
\ObservationRV^\DecP_t=\Observation_t,
\ActionRV^\DecP_t=\Action_T,
\RewardRV^\DecP_t=\Reward_t
\mid\HistoryRV^\DecP_{t-1}=\History_{t-1})
\Prob_\Policy(\HistoryRV^\DecP_{t-1}=\History_{t-1})
\\
& =\Prob_{\Isom^*\Policy}(\StateRV_t^\DecPSecond=\Isom\State_t,\ObservationRV^\DecPSecond_t=\Isom\Observation_t,\ActionRV^\DecPSecond_t=\Isom\Action_t,\RewardRV^\DecPSecond_t=\Reward_t\mid\HistoryRV^\DecPSecond_{t-1}=\Isom\History_{t-1})
\Prob_\Policy(\HistoryRV^\DecP_{t-1}=\History_{t-1})
\\
& \overset{\text{I.H.}}{=}
\Prob_{\Isom^*\Policy}(\StateRV_t^\DecPSecond=\Isom\State_t,\ObservationRV^\DecPSecond_t=\Isom\Observation_t,\ActionRV^\DecPSecond_t=\Isom\Action_t,\RewardRV^\DecPSecond_t=\Reward_t\mid\HistoryRV^\DecPSecond_{t-1}=\Isom\History_{t-1})
\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond_{t-1}=\Isom\History_{t-1})
\\
& =\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond_t=\Isom\History_t).
\end{align}

This concludes the induction and thus proves that \(\Prob_\Policy(\HistoryRV^\DecP=\History)=\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond=\Isom\History)\) for any history \(\History:=\History_\Tmax\in\HistorySet_\Tmax^\DecP\).

Turning to the “in particular” part of the proposition, let \(i\in\PlayerSet,t\in\{0,\dotsc,\Tmax\}\), and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\). Let \(\History_t\in\HistorySet_t^\DecP\) such that \(\Prob_\Policy(\HistoryRV^\DecP_t=\History_t)>0\) and thus also \(\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond_t=\Isom\History_t)>0\).

First, assume that actions and observations of agent \(i\) in this history equal those in \(\AOHistory_{i,t}\). Then it is \(\{\HistoryRV^\DecP_t=\History_t\}\subseteq \{\AOHistoryRV^\DecP_{i,t}=\AOHistory_{i,t}\}\) and hence \(\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)=1\). Moreover, by Equations (<ref>) and (<ref>), it follows for any \(t'\leq t,\Action_{t'}\in\ActionSet^\DecP\) and \(\Observation_{t'}\in\ObservationSet^\DecP\) that
\(\Proj_{\Isom i}(\Isom \Action_{t'})=\Isom \Action_{i,t'}\) and analogously \(\Proj_{\Isom i}(\Isom \Observation_{t'})=\Isom \Observation_{i,t'}\). Hence, it follows that actions of observations of agent \(\Isom i\) in \(\Isom \History_t\) are equal to those in \(\Isom\AOHistory_{i,t}\), and thus it is \(\{\HistoryRV^\DecPSecond_t=\Isom\History_t\}\subseteq \{\AOHistoryRV^\DecPSecond_{\Isom i,t}=\Isom\AOHistory_{i,t}\}\), which implies \(\Prob_{\Isom^*\Policy}(\AOHistoryRV^\DecPSecond_{\Isom i,t}=\Isom\AOHistory_{i,t}\mid \HistoryRV_{t}=\Isom\History_t)=1\).

If, on the other hand, a history \(\History_t\) disagrees with \(\AOHistory_{i,t}\) in any way, then trivially \(\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)=0\) and thus by same argument as before also \(\Prob_{\Isom^*\Policy}(\AOHistoryRV_{\Isom i,t}=\Isom\AOHistory_{i,t}\mid \HistoryRV_{t}=\Isom\History_t)=0\).

It follows that for any \(\History_t\in\HistorySet^\DecP_t\) such that \(\Prob_\Policy(\HistoryRV^\DecP_t=\History)>0\), it is

\begin{equation}
\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)= \Prob_{\Isom^*\Policy}(\AOHistoryRV^\DecPSecond_{\Isom i,t}=\Isom\AOHistory_{i,t}\mid \HistoryRV_{t}=\Isom\History_t)\label{eq:22},
\end{equation}