and hence

\begin{align}\Prob_{\Policy}(\AOHistoryRV_{ i,  t}= \AOHistory_{i,t})
\sum_{\History_t\in\HistorySet^\DecP_t}
\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)\Prob_\Policy(\HistoryRV^\DecP_t=\History_t)
\\&\overset{(\ref{eq:21})}{=}
\sum_{\History_t\in\HistorySet^\DecP_t}
\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)\Prob_{\Isom^*\Policy}(\HistoryRV^\DecP_t=\Isom\History_t)
\\&\overset{(\ref{eq:22})}{=}
\sum_{\History_t\in\HistorySet^\DecP_t}
\Prob_{\Isom^*\Policy}(\AOHistoryRV_{\Isom i,t}=\Isom\AOHistory_{i,t}\mid \HistoryRV_{t}=\Isom\History_t)
\Prob_{\Isom^*\Policy}(\HistoryRV^\DecP_t=\Isom\History_t)
\\&=
\sum_{\History_t\in\Isom^{-1}\left(\HistorySet^\DecP_t\right)}
\Prob_{\Isom^*\Policy}(\AOHistoryRV_{\Isom i,t}=\Isom\AOHistory_{i,t}\mid \HistoryRV_{t}=\History_t)
\Prob_{\Isom^*\Policy}(\HistoryRV^\DecP_t=\History_t)
\\&=\Prob_{\Isom^*\Policy}(\AOHistoryRV_{\Isom i,t}=\Isom\AOHistory_{i,t})\label{eq:23}.
\end{align}

In line (<ref>), we have used that, by Corollary <ref>, \(\Isom\) is a bijective map when applied to histories, and thus \(\Isom^{-1}\left(\HistorySet^\DecP_t\right)=\HistorySet^\DecPSecond_t\).
This concludes the proof.

It is an immediate corollary that the expected return of a policy is not changed by the pushforward.

Let \(\DecP,\DecPSecond\) be Dec-POMDPs, let \(\Isom\in\Iso(\DecP,\DecPSecond)\), and let \(\Policy\in\PolicySet^\DecP\). Then

\[J^{\DecP}(\Policy)=J^\DecPSecond(\Isom^*\Policy).\]

Corollary <ref> and Theorem <ref>, it is

\begin{multline}
\Prob_\Policy(\Isom\left(\HistoryRV^\DecP\right)=\History^\DecPSecond)
\overset{\text{Corollary~\ref{corollary-action-isomorphism-is-bijective-histories}}}{=}
\Prob_\Policy(\HistoryRV^\DecP=\Isom^{-1}\History^\DecPSecond)
\\
\overset{\text{Theorem~\ref{lem-pull-back-isomorphism-compatibility}}}{=}
\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond = \Isom(\Isom^{-1}\History^\DecPSecond))
=\Prob_{\Isom^*\Policy}(\HistoryRV^\DecPSecond = \History^\DecPSecond)
\end{multline}

for any history \(\History^\DecPSecond\in\HistorySet^\DecPSecond\).
This shows that the random variable \(\Isom\left(\HistoryRV^\DecP\right)\) has the same image distribution under \(\Prob_\Policy\) as the variable \(\HistoryRV^\DecPSecond\) under \(\Prob_{\Isom^*\Policy}\). In particular, this means that for any \(t=0,\dotsc,\Tmax\), the variables \(\Isom(\RewardRV_t^\DecP)=\RewardRV^\DecP_t\) and \(\RewardRV^\DecPSecond_t\) have the same distribution in the respective probability spaces (*).
Using the definition of the expected return, it follows that

\begin{equation}J^{\DecP}(\Policy)=\E_{\Policy}\left[\sum_{t=0}^\Tmax \RewardRV^\DecP_t\right]
\overset{\text{(*)}}{=}
\E_{\Isom^*\Policy}\left[\sum_{t=0}^\Tmax
\RewardRV^\DecPSecond_t\right]=J^\DecPSecond(\Isom^*\Policy).\end{equation}

§.§ Relation to group theory

The study of symmetries is a focus of group theory, and the concepts introduced above hence correspond to group-theoretic notions. For instance, as we show below, \(\Aut(\DecP)\) is a group, and its elements do act on the elements of a Dec-POMDP in the sense of group actions. We discuss this here as we will need these results later, in the discussion of symmetric profiles of learning algorithms in Appendix <ref>, as well as in the discussion of random tie-breaking functions in Appendix <ref>. For a reference on the group-theoretic concepts discussed here, see [][ch. 3]rotman2012introduction.

We begin by showing that \(\Aut(\DecP)\) is a group.

Let \(\DecP\) be a Dec-POMDP. Then
\((\Aut(\DecP),\circ)\) is a group, where \(\circ\) is the function composition.

First, we show that the binary operation
\[
\circ\colon \Aut(\DecP)\times\Aut(\DecP)\rightarrow\Aut(\DecP),(\Auto,\AutoSecond)\mapsto\Auto\circ\AutoSecond\]

is well-defined.
By Equation <ref>, an automorphism \(\Auto\in\Aut(\DecP)\) is a bijective self-map, so we can compose any two automorphisms \(\Auto,\AutoSecond\in\Aut(\DecP)\). Moreover, by Lemma <ref>, for any \(\Auto\in\Aut(\DecP),\AutoSecond\in\Aut(\DecP)\), we also have \(\AutoSecond\circ\Auto\in\Iso(\DecP,\DecP)=\Aut(\DecP)\). This shows that \(\Aut(\DecP)\) is closed under function composition.

Second, note that \(\circ\) is an associative operation as function composition is associative. Moreover, for the identity map \(\Id\), it is \(\Id\circ \Auto=\Auto\) for any \(\Auto\in\Aut(\DecP)\), so \(\Aut(\DecP)\) has a neutral element. Lastly, by Lemma <ref>, it is also \(\Auto^{-1}\in \Aut(\DecP)\), and since \(\Auto^{-1}\circ\Auto=\Id\), this implies that \(\Auto\) has an inverse in \(\Aut(\DecP)\). This concludes the proof.

Next, we turn to group actions, which formalize the idea that elements of groups can be applied to sets. In the case of symmetry groups, this connects the abstract group elements with their role as transformation of an underlying set. For instance, consider the set \(X\) of the vertices of an equilateral triangle in \(\mathbb{R}^2\) and the cyclic group \(\faktor{\mathbb{Z}}{3\mathbb{Z}}\). Each element of \(\faktor{\mathbb{Z}}{3\mathbb{Z}}\) can be regarded as a rotation of the vertices of the triangle, mapping one vertex to another.

Let \((G,\cdot)\) be a group with identity \(\Id\) and let \(X\) be any set.
A group action is defined as a map \(\alpha\colon G\times X\rightarrow X\) such that

(i) Identity: \(\alpha(\Id,x)=x\) for any \(x\in X\)

(ii) Compatibility: \(\alpha(f, \alpha(g,x)) = \alpha(f\cdot g,x)\) for any \(f,g\in G\), \(x\in X\).

It is common to write \(\Auto x:=\alpha(\Auto,x)\) for \(\Auto\in G\), \(x\in X\), if it is clear which group action is referred to.

We have already proven these two properties for isomorphisms and both their actions on joint actions and observations, as well as the pushforward of policies, in Lemma <ref> and Lemma <ref>, respectively. Hence, it follows that also \(\Aut(\DecP)\) acts on these sets in the sense of group actions.

Let \(\DecP\) be a Dec-POMDP.
The actions of \(\Aut(\DecP)\) on \(\ActionSet\) and \(\ObservationSet\), defined as \(\alpha_A\colon (\Auto,\Action)\mapsto\Auto_A(\Action)\) respectively \(\alpha_O\colon (\Auto,\Observation)\mapsto\Auto_O(\Observation)\) as in Equations <ref> and <ref> are group actions. Similarly, the pushforward of policies by automorphisms \((\Auto,\Policy)\mapsto\Auto^*\Policy\) as defined in Definition <ref> is an action of \(\Aut(\DecP)\) on \(\PolicySet^\DecP\).

This follows directly from Lemma <ref> and Lemma <ref>.

Of course, automorphisms also act on states and agents, and one can also easily see that they act on histories and action-observation histories.

Some further results immediately follow from this, such as the fact that \(\PlayerSet\) decomposes into equivalence classes of orbits under \(\Aut(\DecP)\).
The orbit of agent \(i\) is defined as the set of all agents \(j\) that can be obtained from \(i\) by applying automorphisms.

Let \(\DecP\) be a Dec-POMDP and assume that \(\Aut(\DecP)\) acts on the set \(X\). Then for \(x\in X\), the set

\[\Aut(\DecP)x:=\{\Auto x\mid\Auto\in\Aut(\DecP)\}\]

is called the orbit of \(x\) under \(\Aut(\DecP)\).

For instance, for \(i\in\PlayerSet\), the set
\(\Aut(\DecP)i:=\{\Auto i\mid\Auto\in\Aut(\DecP)\}\)
is the orbit of agent \(i\) under \(\Aut(\DecP)\). It is a standard result from group theory that orbits form a partition \(\{\Aut(\DecP)i\mid i\in\PlayerSet\}\subseteq\PowerSet(\PlayerSet)\) of the set. This follows from the fact that since group actions have an identity and are invertible, belonging to the same orbit is an equivalence relation. For example, in the case of the triangle in \(\mathbb{R}^2\), all the vertices in \(V\) can be reached from any other vertex by rotations, so they all belong to the same orbit. In general, though, the orbits may form any other partition of the set.

§.§ Dec-POMDP labelings and relabeled Dec-POMDPs

In the following, assume that a Dec-POMDP \(\DecP\) is given. Here, we want to define a set of isomorphic Dec-POMDPs \(\DecPSet\) as described in Section <ref>, in which the sets of states, actions, etc. are of the form \(\{1,2,\dotsc,k-1,k\}\subseteq\mathbb{N},k\in\mathbb{N}\). This set can then be used to define the LFC game for \(\DecP\) in a way that does not depend on labels.

We begin by defining a labeling of \(\DecP\). A labeling \(\Isom\) is a special Dec-POMDP isomorphism from \(\DecP\) to another, relabeled Dec-POMDP, that can be constructed using \(\Isom\).

A Dec-POMDP labeling is a tuple of bijective maps

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

_N      →{1,…,||}

_S      →{1,…,||}

∀i∈     _A_i      _i→{1,…,|_i|}

∀i ∈     _O_i      _i→{1,…,|_i|}.

We denote \(\Sym(\DecP)\) for the set of labelings of \(\DecP\).

Note that if \(X\) is some set, then \(\Sym(X)\) usually denotes the symmetric group of \(X\). The symmetric group is the set of permutations of \(X\), together with the operation of function composition. We use the same notation, as \(\Sym(\DecP)\) can be understood of as containing all the permutations of the different sets that \(\DecP\) consists of, with the caveat that we first map those sets to subsets of the first \(k\) natural numbers. This is done for simplification, especially regarding the treatment of the individual action and observation sets of different agents.

Next, we introduce the pushforward Dec-POMDP \(\Isom^*\DecP\) for a labeling \(\Isom\in\Sym(\DecP)\). This is a Dec-POMDP that is isomorphic to \(\DecP\), with isomorphism \(\Isom\). In the following, we let \(\Isom\in\Sym(\DecP)\) act on joint actions, observations, etc., in the same way as before for isomorphisms. For instance, for \(\Action\in\ActionSet\), it is \(\Isom\Action:=(\Isom_{A_{\Isom_N^{-1}(i)}}(\Action_{\Isom_N^{-1}(i)}))_{i\in \{1,\dotsc,|\PlayerSet|\}}\). The compatibility of these actions with function composition and function inversion trivially still hold.

Let $f\in\Sym(D)$. Let \(N\in\mathbb{N}\) such that \(\{1,\dotsc,N\}=\PlayerSet\). The pushforward of \(\DecP\) by \(\Isom\), called a relabeled Dec-POMDP, is the Dec-POMDP

\[
\]

* \(\hat{\PlayerSet}:=\{1,\dotsc,N\}=\PlayerSet\).

* \(\hat{\StateSet}:=\{1,\dotsc,|\StateSet|\}\).

* $\hat{\ActionSet}_{i}:=\{1,\dotsc,|\ActionSet_{\Isom^{-1}i}|\}$ for \(i\in \hat{\PlayerSet}\).

* $\hat{P}(s'\mid s,a):=P(\Isom^{-1}s'\mid \Isom^{-1}s,\Isom^{-1}a)$ for \(s',s\in\hat{\StateSet},\Action\in\hat{\ActionSet}\).

* $\hat{\RewardFunction}(s,a):=\RewardFunction(f^{-1}s,f^{-1}a)$ for  \(\State\in\hat{\StateSet},\Action\in\hat{\ActionSet}\).

* $\hat{\ObservationSet}_{i}:=\{1,\dotsc,|\ObservationSet_{\Isom^{-1}i}|\}$ for \(i\in \hat{\PlayerSet}\).

* $\hat{O}(o\mid s,a):=O(\Isom^{-1}o\mid \Isom^{-1}s,\Isom^{-1}a)$ for \(\Observation\in\hat{\ObservationSet},\State\in\hat{\StateSet},\Action\in\hat{\ActionSet}\).

* $\hat{b}_{0}(s):=b_{0}(f^{-1}s)$ for \(\State\in\hat{\StateSet}\).

* \(\hat{\Tmax}:=\Tmax\).

First, we have to check that this is well-defined, e.g., that \(\Isom^{-1}\Action\in\ActionSet\) for any \(\Action\in\hat{\ActionSet}\). For states, it is clear from the definition of \(\Sym(\DecP)\) that \(\Isom^{-1}(\hat{\StateSet})=\Isom^{-1}(\{1,\dotsc,|\StateSet|\})=\StateSet\). Moreover, the same applies to agents, i.e., \(\Isom^{-1}i\in \PlayerSet\) for any \(i\in\{1,\dotsc,|\PlayerSet|\}\). This leaves joint actions and observations.

For $\hat{\ActionSet},\hat{\ObservationSet}$ as defined above, it is $\Isom^{-1}(\hat{\ActionSet})=\ActionSet$
and $\Isom^{-1}(\hat{\ObservationSet})=\ObservationSet$.

Let $\hat{a}\in\hat{\ActionSet}$. Then for any \(i\in \hat{\PlayerSet}\), we can define \(j\in\PlayerSet\) and \(\Action_{j}\in\ActionSet_{j}\) such that \(\Isom j = i\) and \(\Isom \Action_j = \hat{\Action}_i\).

\[\Isom^{-1}\hat{a}=
(\Isom^{-1} \hat{\Action}_{\Isom j}))_{j\in \PlayerSet}
( \Isom^{-1}\Isom\Action_{j}))_{j\in\PlayerSet}

The same argument works for $\hat{o}\in\hat{\ObservationSet}$.

Importantly, it can be \(\Isom^*\DecP\neq\DecP\) for a labeling \(\Isom\in\Sym(\DecP)\).
Nevertheless, it is easy to see from the definitions that \(\Isom^*\DecP\) is actually isomorphic to \(\DecP\), with isomorphism \(\Isom\). This also implies that it is \(\Isom^*\DecP=\DecP\) if and only if \(\Isom\) is an automorphism.

For any \(\Isom\in \Sym(\DecP)\), it is \(\Isom\in\Iso(\DecP,\Isom^*\DecP)\).

This follows directly from the definition of an isomorphism, together with Lemma <ref>. For instance, considering transition probabilities, it is

\[P(s'\mid s,a)=P(\Isom^{-1}\Isom s'\mid \Isom^{-1}\Isom s, \Isom^{-1}\Isom a)=\hat{P}(\Isom s'\mid \Isom s \mid \Isom a)
\]

for any \(s',s\in\StateSet,\Action\in\ActionSet\). Similar calculations apply to all the other relevant functions.

It follows as a corollary that \(\Isom^*\Policy\) is a policy for the Dec-POMDP \(\Isom^*\DecP\), where \(\Policy\in\PolicySet^\DecP,\Isom\in\Sym(\DecP)\). Note also that the results in Lemma <ref> still apply to the pushforward by labelings.

Let \(\Isom\in\Sym(\DecP)\) and \(\Policy\in\PolicySet^\DecP\). Then \(\Isom^*\Policy\in\PolicySet^{\Isom^*\DecP}\).

Follows from the definition of \(\Isom^*\Policy\) and Lemma <ref>.

Lastly, we provide some further useful results about labelings. First, the set \(\Sym(\DecP)\) already contains all the isomorphisms in \(\Iso(\DecP,\Isom^*\DecP)\).
We will need this result later to relate results about isomorphisms and automorphisms to the relabeled Dec-POMDPs used in an LFC game.

Let \(\Isom\in\Sym(\DecP)\). Then

\[\Iso(\DecP,\Isom^*\DecP)=\{\IsomSecond\in\Sym(\DecP)\mid \IsomSecond^*\DecP=\Isom^*\DecP\}\]

“\(\supseteq\)”: for any \(\IsomSecond\in\Sym(\DecP)\) such that \(\IsomSecond^*\DecP=\Isom^*\DecP\), it is also \(\Iso(\DecP,\IsomSecond^*\DecP)=\Iso(\DecP,\Isom^*\DecP)\), and thus it follows from Lemma <ref> that \(\IsomSecond\in \Iso(\DecP,\IsomSecond^*\DecP)=\Iso(\DecP,\Isom^*\DecP)\).

“\(\subseteq\)”: Let \(\IsomHat\in \Iso(\DecP,\Isom^*\DecP)\). Note that the set of agents, states, and the individual action and observation sets in \(\Isom^*\DecP\) are all of the form \(\{1,\dotsc,k\}\) where \(k\in\mathbb{N}\) depends on the respective set. Now consider, for instance, the map \(\IsomHat_{A_i}\) for \(i\in\PlayerSet\). Then by the definition of an isomorphism, \(\IsomHat_{A_i}\) is a bijective map, and its domain and codomain are \(\ActionSet_i\) and \(\{1,\dotsc,k\}\) for some \(k\in\mathbb{N}\). Moreover, since \(\IsomHat_{A_i}\) is bijective, it must be \(k=|\ActionSet_i|\). Mutatis mutandis, the same applies to all of the other maps that are part of the tuple \(\IsomHat\). Hence, \(\IsomHat\) satisfies the definition of a Dec-POMDP labeling, so \(\IsomHat\in\Sym(\DecP)\).

Next, it follows that \(\IsomHat\in\Iso(\DecP,\IsomHat^*\DecP)\) by Lemma <ref>, and thus \(\Id=\IsomHat\circ\IsomHat^{-1}\in \Iso(\Isom^*\DecP,\IsomHat^*\DecP)\) by the assumption and Lemma <ref>. Hence, using the definition of an isomorphism, it follows that also \(\Isom^*\DecP=\IsomHat^*\DecP\). This shows that

\[\IsomHat\in\{\IsomSecond\in\Sym(\DecP)\mid \IsomSecond^*\DecP=\Isom^*\DecP\},\]

which concludes the proof.

Second, we show that labelings and pushforward are compatible with composition with isomorphisms.

Let \(\DecP,\DecPSecond\) be isomorphic Dec-POMDPs with \(\Isom\in\Iso(\DecP,\DecPSecond)\). Then

\[\Sym(\DecP)=\Sym(\DecPSecond)\circ \Isom.\]

Moreover, it is \(\IsomSecond^*\DecPSecond=(\IsomSecond\circ\Isom)^*\DecP\) for any \(\IsomSecond\in\Sym(\DecPSecond)\).

First, let \(\IsomSecond\in\Sym(\DecP)\) and define \(\IsomHat:=\IsomSecond\circ\Isom^{-1}\). Note that \(\IsomHat\) has as components bijective maps with a domain and codomain that satisfies the definition of a labeling of \(\DecPSecond\). Hence, \(\IsomHat\in\Sym(\DecPSecond)\). Next, let \(\IsomSecond\in\Sym(\DecPSecond)\). Then similarly, \(\IsomSecond\circ\Isom\) fulfills the requirements for a labeling in \(\Sym(\DecP)\).

To prove the second statement, let again \(\IsomSecond\in\Sym(\DecPSecond)\). Note that since \(\DecP\) and \(\DecPSecond\) are isomorphic, they must have the same set of players and sets of states with the same cardinalities. Now let \(i\in\PlayerSet^\DecP\). Using the definition of an isomorphism and of a labeling, it is then

\[\ActionSet^{\IsomSecond^*\DecPSecond}_i=\{1,\dotsc,|\ActionSet_{\IsomSecond^{-1}i}^\DecPSecond|\}
=\{1,\dotsc,|\ActionSet_{\Isom^{-1}(\IsomSecond^{-1}i)}^\DecP|\}=\{1,\dotsc,|\ActionSet_{(\IsomSecond\circ\Isom)^{-1}i}^\DecP|\}= \ActionSet^{(\IsomSecond\circ\Isom)^*\DecP}_i.\]

A similar argument applies to the sets \(\ObservationSet_i\) for \(i\in\PlayerSet\). Finally, let \(\State,\State'\in\StateSet^{\IsomSecond^*\DecPSecond},\Action\in\ActionSet^{\IsomSecond^*\DecPSecond}\). Using again the definition of an isomorphism and a labeling, it follows that

\begin{multline}P^{\IsomSecond^*\DecPSecond}(\State'\mid\State,\Action)
= P^\DecPSecond(\IsomSecond^{-1}\State'\mid\IsomSecond^{-1}\State,\IsomSecond^{-1}\Action)
\\
= P^\DecP(\Isom^{-1}\IsomSecond^{-1}\State'\mid\Isom^{-1}\IsomSecond^{-1}\State,\Isom^{-1}\IsomSecond^{-1}\Action)

Again, an analogous argument applies to the observation probability kernel and reward function, as well as the initial state distribution.
This concludes the proof.

§.§ The label-free coordination game and problem

Here, we recall the definitions of an LFC game and of the LFC problem. To begin, we define a measure space of policies and recall the definition of a learning algorithm. For any Dec-POMDP \(\DecP\), let \(\Delta(\PolicySet^\DecP)\) be the set of measures on the space \((\PolicySet^\DecP,\mathcal{F}^\DecP)\) where \(\mathcal{F}^\DecP:=\otimes_{i\in\PlayerSet}\mathcal{F}^\DecP_i\) is a product \(\sigma\)-Algebra and \(\mathcal{F}_i^\DecP\subseteq\PowerSet(\PolicySet_i^\DecP)\) are \(\sigma\)-Algebras that make the random variables and sets discussed in this paper measurable. For instance, for \(i\in\PlayerSet\), this could be the Borel \(\sigma\)-Algebra with respect to the standard topology on \(\PolicySet_i^\DecP\) that comes from regarding \(\PolicySet_i^\DecP\) as a subset of \([0,1]^{\ActionSet^\DecP_i\times\AOHistorySet^\DecP_i}\). Although we do not investigate this here, all the relevant functions and sets should be measurable in that sense.

Let \(\DecPSet\) be a finite set of Dec-POMDPs. A learning algorithm for \(\DecPSet\) is a map
\[\LA\colon \DecPSet\rightarrow \bigcup_{D\in\mathcal{D}}\Delta(\PolicySet^\DecP)\]

such that \(\LA(D)\in\Delta(\PolicySet^D)\) for all \(D\in\mathcal{D}\). We write \(\LASet^\mathcal{D}\) for the set of learning algorithms for \(\mathcal{D}\).

Note that this definition is general enough so as to include planning algorithms that construct a policy directly from the environment dynamics, instead of incrementally updating a policy from experience. Nevertheless, here, we imagine that \(\LA(\DecP)\) is a policy that was trained by an RL algorithm, using a simulator of \(\DecP\). Note also that a learning algorithm can learn different joint policies in different training runs, which we formalize as outputting a measure over joint policies.

Similarly to the case of policies, for a distribution \(\Distr\in\Delta(\PolicySet^\DecP)\) and an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\), we can define a pushforward distribution \(\Isom^*\Distr:=\Distr \circ (\Isom^*)^{-1}\in\Delta(\PolicySet^\DecPSecond)\), which is the image measure of \(\Distr\) under \(\Isom^*\). It is apparent that for two isomorphisms \(\Isom\in\Iso(\DecP,\DecPSecond),\IsomSecond\in\Iso(\DecPSecond,\DecPThird)\), it is \(\IsomSecond^*(\Isom^*\Distr)=(\IsomSecond\circ\Isom)^*\Distr\).

In the following, for some distributions \(\Distr^{(i)}\in\Delta(\PolicySet^\DecP)\) for \(i\in\PlayerSet\) and bounded measurable function \(\eta\colon \PolicySet^\DecP\times\dotsb\times\PolicySet^\DecP\rightarrow\mathbb{R}\), we will use the notational shorthands

\[\E_{\Policy^{(i)}\sim\Distr^{(i)},\,i\in\PlayerSet}
\left[\eta(\Policy^{(1)},\dotsc,\Policy^{(N)})\right]
\left[\eta(\Policy^{(1)},\dotsc,\Policy^{(N)})\right]\right]\dots\right]
\]

\[\E_{\Policy^{(i)}\sim\Distr^{(i)}}
\left[
\eta(\Policy^{(1)},\dotsc,\Policy^{(N)})\right]:=\int_{\PolicySet^\DecP}\eta(\Policy^{(1)},\dotsc,\Policy^{(N)})\mathrm{d}\Distr^{(i)}(\Policy^{(i)}).\]

Note that by Fubini's theorem [see][ch. 8]williams1991probability, it is

\[\E_{\Policy^{(i)}\sim\Distr^{(i)},\,i\in\PlayerSet}
\left[\eta(\Policy^{(1)},\dotsc,\Policy^{(N)})\right]
\]

Now we define the LFC game for a Dec-POMDP.

Let \(\DecP\) be a Dec-POMDP and define \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\). The label-free coordination (LFC) game for \(\DecP\) is defined as a tuple \(\Gamma^\DecP:=(\PlayerSet^\DecP,(\LASet^\DecPSet)_{i\in\PlayerSet},(U^{\DecP})_{i\in\PlayerSet})\) where

* \(\PlayerSet^\DecP\) is the set of players, called principals.

* \(\LASet^\DecPSet\) is the set of strategies for all principals \(i\in\PlayerSet^\DecP\).

* the common payoff for the strategy profile \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecP\) is

\begin{equation}U^\DecP(\LAProfile):=
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\Big[\E_{\Isom_j\sim\U(\Iso(\DecP_j,\DecP)),\,j\in\PlayerSet}\Big[\\
\E_{\Policy^{(k)}\sim\Isom_k^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\Big[

where \(\mathcal{U}(\DecPSet)\) is a uniform distribution over \(\DecPSet\) and \(\U(\Iso(\DecP_j,\DecP))\) a uniform distribution over \(\Iso(\DecP_j,\DecP)\).

Note that set of strategies \(\LASet^\DecP\) is continuous. The game \(\Gamma^\DecP\) could hence be considered a continuous game, which is a generalization of the concept of a normal-form game to continuous strategy spaces [see][]glicksberg1952generalization. In continuous games, it is usually assumed that the set of strategies is compact and that the payoffs are continuous functions, which we believe does apply in our case.

Moreover, we believe that there is some other normal-form game with finite strategy space such that the mixed strategies in that game correspond to the set of strategies \(\LASet^\DecPSet\) in \(\Gamma^\DecP\) [for a reference on these concepts from game theory, see][]osborne1994course,gibbons1992game. In particular, one can see that the set of strategies \(\LASet^\DecPSet\) is already convex.

We do not need any further characterization of an LFC game in the following, so we do not investigate issues such as compactness or convexity of the set of strategies. The formalism at hand was chosen primarily to work well with an intuitive formulation of the LFC problem and to suit our discussion of the OP algorithm.

Next, to recall the definition of the LFC problem, let any set \(\DecPSetSecond\) of Dec-POMDPs be given, and denote \(\overline{\DecPSetSecond}:=\bigcup_{\DecP\in\DecPSetSecond}\DecPSet^\DecP\) where \(\DecPSet^\DecP:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\) is the set of all relabeled problems of \(\DecP\). 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^\DecP\) for \(\DecP\sim\U(\DecPSetSecond)\).

Let \(\DecPSetSecond\) be any set of Dec-POMDPs.
Define the objective \(U^\DecPSetSecond\colon \LASet^{\overline{\DecPSetSecond}}\rightarrow\mathbb{R}\) via

\begin{equation}
\end{equation}

\(\LA\in\LASet^{\overline{\DecPSetSecond}}\). Then 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}

and we call \(U^\DecPSetSecond(\LA)\) the value of \(\LA\) in the LFC problem for \(\DecPSetSecond\).

If \(\DecPSetSecond=\{\DecP\}\), we write \(U^\DecP:=U^{\{\DecP\}}\) in a slight abuse of notation and refer to this as the LFC problem for \(\DecPSecond\).

The aim of the LFC problem is to find a general learning algorithm to recommended to principals in any LFC game. For this reason, we defined the problem here for a distribution over LFC games. However, a learning algorithm is optimal in the problem for a set of Dec-POMDPs if and only if it is optimal in the problem for each Dec-POMDP in that set. That is because, as one can easily see, the sets \(\DecPSet^\DecP,\DecPSet^\DecPSecond\) do never overlap for two non-isomorphic Dec-POMDPs \(\DecP,\DecPSecond\), and we will show in Corollary <ref> that the LFC problems for two isomorphic Dec-POMDPs are identical. So to evaluate a learning algorithm in the LFC problem for a set of Dec-POMDPs, we can decompose the set into equivalence classes of isomorphic Dec-POMDPs and evaluate the learning algorithm separately for each of these classes. In the following, we will thus simplify our analysis and restrict ourselves entirely to problems defined for single Dec-POMDPs. Note that the objective in the LFC problem is then simply

\begin{equation}U^\DecP(\LA)=U^{\{\DecP\}}(\LA)=\E_{\DecPSecond\sim\U(\{\DecP\})}\left[U^\DecPSecond(\LA,\dotsc,\LA)\right]=U^\DecP(\LA,\dotsc,\LA).
\end{equation}

If we then prove, e.g., that a learning algorithm is optimal in any such problem, it follows that it is also optimal for the problem defined for any set of Dec-POMDPs.

Now we will provide two different expressions of the payoff in an LFC game. To that end, let \(\DecP\) be a Dec-POMDP and define \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\). First, we provide an expression in terms of labelings.

Let \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\).

\begin{equation}
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\end{equation}

It follows from Lemma <ref> that it is \(\Sym(\DecP)=\bigcup_{\DecPSecond\in\DecPSet}\Iso(\DecP,\DecPSecond)\), where one can easily see that the union is disjoint (i). Moreover, it follows from Lemma <ref> that \(|\Iso(\DecP,\DecPSecond)|=|\Iso(\DecP,\DecPThird)|\) for any Dec-POMDPs \(\DecPSecond,\DecPThird\in\DecPSet\), so there exists \(M\in\mathbb{N}\) such that \(M=|\Iso(\DecP,\DecPSecond)|\) for any \(\DecPSecond\in\DecPSet\), and from (i) it follows that \(|\Sym(\DecPSecond)|=|\DecPSet||M|\) (ii).

Next, by Lemma <ref>, for any \(\Isom\in\Iso(\DecP,\DecP_j)\), it is \(\Isom^{-1}\in \Iso(\DecP_j,\DecP)\) for any \(\Isom\in\Iso(\DecP_j,\DecP)\). In addition, by the same Lemma, for \(\Isom\in\Iso(\DecP_j,\DecP)\), it is \(\Isom=(\Isom^{-1})^{-1}\) and \(\Isom^{-1}\in \Iso(\DecP,\DecP_j)\) and thus \(\Isom\in\{\IsomSecond^{-1}\mid\IsomSecond\in\Iso(\DecP,\DecP_j)\}\). Hence, it is

\begin{equation}
\label{eq:507}
\{\IsomSecond\mid\IsomSecond\in\Iso(\DecP_j,\DecP)\}=\{\IsomSecond^{-1}\mid\IsomSecond\in\Iso(\DecP,\DecP_j)\}.\end{equation}

Using the above, it follows that

\begin{align}&U^{\DecPSet}(\LAProfile_1,\dotsc,\LAProfile_N)\label{eq:36c}
\\
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\IsoProfile_j\sim\Iso(\DecP_j,\DecP), \,j\in\PlayerSet}\left[
\E_{\Policy^{(k)}\sim\SymProfile_k^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\left[
\\
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\IsoProfile_j\in\Iso(\DecP,\DecP_j),\,j\in\PlayerSet}\left[
\E_{\Policy^{(k)}\sim(\IsoProfile_k^{-1})^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\left[
%\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
%    M^{-1}\prod_{j\in\PlayerSet}\sum_{\IsoProfile_j\in\Iso(\DecP_j,\DecP)}\left[
%    \E_{\Policy^{(k)}\sim\SymProfile_k^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
%    \left[
%\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
%    M^{-1}\prod_{j\in\PlayerSet}\sum_{\IsoProfile_j\in\Iso(\DecP,\DecP_j)}\left[
%    \E_{\Policy^{(k)}\sim(\IsoProfile_k^{-1})^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
%    \left[
%%    (M\cdot |\DecPSet|)^{-1}\sum_{\SymProfile_j\in\Sym(\DecP), \,j\in\PlayerSet}\left[
%    \E_{\Policy^{(k)}\sim(\SymProfile_k^{-1})*\LAProfile_k(\SymProfile_i^*\DecP),\,k\in\mathcal{N}}
%    \left[
%    (|\Sym(\DecP)|\cdot|\PlayerSet|)^{-1}\sum_{\SymProfile_j\in\Sym(\DecP), \,j\in\PlayerSet}\left[
%    \E_{\Policy^{(k)}\sim(\SymProfile_k^{-1})^*\LAProfile_k(\SymProfile_i^*\DecP),\,k\in\mathcal{N}}
%    \left[
\\
\E_{\SymProfile_i\sim \U(\Sym(\DecPSecond)),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim(\SymProfile_j^{-1})^*\LAProfile_j(\SymProfile_j^*\DecP),\,j\in\mathcal{N}}
\left[
\\
&=\E_{\SymProfile\sim \U(\Sym(\DecPSecond)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\end{align}

This concludes the proof.

Second, we can prove a useful decomposition of the payoff in an LFC game into isomorphisms and automorphisms. We can already see here the connection to the OP objective (we will recall the OP objective in Appendix <ref>). Recall the projection operator, \(\Proj_i(x):=x_i\) for \(x=(x_i)_{i\in\PlayerSet}\).

Let \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\).
For any \(\DecPSecond,\DecPThird\in\DecPSet\), choose \(\Isom_{\DecPSecond,\DecPThird}\in\Iso(\DecPSecond,\DecPThird)\) arbitrarily. Then

\begin{align}
% \\ &=\label{eq:36a}
%   \E_{\DecP_i\sim \U(\DecPSet),\SymProfile_i\sim \U(\Iso(\DecP,\DecP_i)),\,i\in\PlayerSet}\left[
%   \E_{\Policy^{(j)}\sim(\SymProfile_j^{-1})^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
%   \left[
%       J^\DecP((\Policy^{(k)}_k)_{k\in\PlayerSet})\right]\right]
\\ &=\label{eq:36b}
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
\E_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\left[
\end{align}

Let \(i\in\PlayerSet,\DecP_i\in\DecPSet\). We know from Lemma <ref> that for any \(\Isom\in \Iso(\DecP_i,\DecP)\) there is a unique \(\Auto\in\Aut(\DecP)\) such that \(\Isom=\Auto\circ\Isom_{\DecP_i,\DecP}\). Also, for the pushforward measure, it is \((\Auto\circ\Isom_{\DecP_i,\DecP})^*\LAProfile_i(\DecP_i)=\Auto^*\Isom_{\DecP_i,\DecP}^*\LAProfile_i(\DecP_i)\) for any \(\Auto\in\Aut(\DecP)\). Using this, it follows that

\begin{align}&\label{eq:36e}
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\IsoProfile_j\sim\U(\Iso(\DecP_j,\DecP)), \,j\in\PlayerSet}\left[
\E_{\Policy^{(k)}\sim\SymProfile_k^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\left[
\\
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\AutProfile\sim\U(\Aut(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(k)}\sim\AutProfile_k^*\Isom_{\DecP_k,\DecP}^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\left[
\\
\E_{\DecP_i\sim \U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(k)}\sim\Isom_{\DecP_k,\DecP}^*\LAProfile_k(\DecP_k),\,k\in\mathcal{N}}
\left[
\E_{\AutProfile\sim\U(\Aut(\DecP)^\PlayerSet)}\left[
\end{align}

where we have used a change of variables for pushforward measures in the last line.

Finally, we can show that the payoff in an LFC game is equal for isomorphic Dec-POMDPs, up to a possible permutation of principals. Intuitively, this means that the game does not depend on labels for the problem.

Let \(\DecP,\DecPSecond\) be isomorphic and \(\Isom\in\Iso(\DecP,\DecPSecond)\) arbitrary. Define
\(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\) and \(\DecPSetSecond:=\{\Isom^*\DecPSecond\mid\Isom\in\Sym(\DecPSecond)\}\).
Then \(\DecPSet=\DecPSetSecond\),
and for any profile of algorithms \(\LAProfile=(\LAProfile_1,\dotsc,\LAProfile_N)\in\Sigma^\DecPSet\), it is

\[U^{\DecP}(\LAProfile_1,\dotsc,\LAProfile_N)
\]

First, note that by Lemma <ref>, it is

\begin{multline}\DecPSetSecond=\{\IsomSecond^*\DecPSecond\mid\IsomSecond\in\Sym(\DecPSecond)\}\overset{\text{Lemma~\ref{d-sym-closed-under-labeling}}}{=}
\{(\IsomSecond\circ\Isom)^*\DecP\mid\IsomSecond\in\Sym(\DecPSecond)\}
\\=
\{\IsomHat^*\DecP\mid\IsomHat\in\Sym(\DecPSecond)\circ\Isom\}\overset{\text{Lemma~\ref{d-sym-closed-under-labeling}}}{=}\{\IsomHat^*\DecP\mid\IsomHat\in\Sym(\DecP)\}=\DecPSet.\end{multline}

Now let \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\) arbitrary.
Then, using the expression of \(U^\DecP\) from Lemma <ref>, it is

\begin{align}&U^{\DecP}(\LAProfile_{1},\dotsc,\LAProfile_N)
\\&=
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\label{eq:25-1}
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\label{eq:25-2}
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\label{eq:25-3}
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim\Isom^*(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\label{eq:25-4}
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim((\SymProfile_i\circ \Isom^{-1})^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\label{eq:25-41}
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim((\SymProfile_i\circ \Isom^{-1})^{-1})^*\LAProfile_i((\SymProfile_i\circ\Isom^{-1})^*\DecPSecond),\,i\in\mathcal{N}}
\left[
\label{eq:25-5}
\\
\E_{\SymProfile\sim \U(\Sym(\DecPSecond)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecPSecond),\,i\in\mathcal{N}}
\left[
\label{eq:25-6}
\\
\E_{\SymProfile\sim \U(\Sym(\DecPSecond)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_{\Isom^{-1}i}^{-1})^*\LAProfile_{\Isom^{-1}i}(\SymProfile_{\Isom^{-1}i}^*\DecPSecond),\,i\in\mathcal{N}}
\left[
\label{eq:25-7}
\\
\E_{\SymProfile\sim \U(\Sym(\DecPSecond)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_{i}^{-1})^*\LAProfile_{ \Isom^{-1}i}(\SymProfile_{i}^*\DecPSecond),\,i\in\PlayerSet}
\left[
\label{eq:25-8}
\\&=U^{\DecPSecond}(\LAProfile_{\Isom^{-1}1},\dotsc,\LAProfile_{\Isom^{-1}N}).
\end{align}

Here, in (<ref>), we use Theorem <ref>; in (<ref>) and (<ref>), we use the definition of the pushforward policy; in (<ref>), we apply a change of variables for pushforward measures, applied to each of the measures \((\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP)\) separately; in (<ref>), we use the associativity of the pushforward measure as well as the fact that \((\SymProfile_i\circ \Isom^{-1})^{-1}=\Isom\circ\IsoProfile_i^{-1}\); in (<ref>) and in (<ref>), we use the second respectively first part of Lemma <ref>; in (<ref>), we again use a change of variables for pushforward measures, this time applied to the joint measure \(\otimes_{i\in\PlayerSet}(\SymProfile_i^{-1})^*\LAProfile_i(\SymProfile_i^*\DecP)\); and in (<ref>) we use the symmetry of the set \(\Sym(\DecPSecond)^\PlayerSet\) with respect to player permutations, concluding the proof.

First, this result implies that the LFC problems for two isomorphic problems are identical.

Let \(\DecP,\DecPSecond\) be two isomorphic Dec-POMDPs and let \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\) and \(\DecPSetSecond:=\{\Isom^*\DecPSecond\mid\Isom\in\Sym(\DecPSecond)\}\). Then \(\DecPSet=\DecPSetSecond\) and \(U^\DecP(\LA)= U^\DecPSecond(\LA)\) for any \(\LA\in\LASet^{\DecPSet}=\LASet^\DecPSetSecond\).

By Theorem <ref>, we have \(\DecPSet=\DecPSetSecond\).
Now let \(\LA\in\LASet^\DecPSet=\LASet^\DecPSetSecond\).
Then again by Theorem <ref>, it is

\[U^\DecP(\LA)
=U^\DecP(\LA,\dotsc,\LA) \overset{\text{Theorem~\ref{zero-shot-coordination-game-invariant-to-isomorphism}}}{=} U^\DecPSecond(\LA,\dotsc,\LA)=U^\DecPSecond(\LA).\]

Second, the theorem shows that symmetries between the agents in a Dec-POMDP are also symmetries between principals in \(\Gamma^\DecP\).

Let \(\DecP\) be a Dec-POMDP. Then it is

\[U^{\DecP}(\LA_1,\dotsc,\LA_N)
\]

for any \(\Auto\in\Aut(\DecP)\).

This follows from Theorem <ref>, using that \(\Aut(\DecP)=\Iso(\DecP,\DecP)\).

§.§ Optimal symmetric strategy profiles

Above, we have shown that the payoff in an LFC game is invariant with respect to symmetries of the agents in \(\DecP\). Similarly to the case of Dec-POMDPs and their symmetries, we can also apply the concept of symmetry to profiles of learning algorithms. We can then ask whether a profile of learning algorithms is invariant to symmetries of the principals, in which case we say that the profile is symmetric. In the following, we will show that optimal profiles among the ones that are symmetric are Nash equilibria of an LFC game. Since we will show in Appendix <ref> that a profile in which all principals choose OP with tie-breaking is an optimal symmetric profile, it will result as a corollary that all principals using OP with tie-breaking is a Nash equilibrium of the game.

To begin, we define symmetric principals and profiles of learning algorithms. In the following, let again \(\DecP\) be a Dec-POMDP and \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\).

We say that two principals \(i,j\in\PlayerSet\) are symmetric if there exists an automorphism \(\Auto\in\Aut(\DecP)\) such that \(i=\Auto j\). A profile of learning algorithms \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecP\) is called symmetric if it is \(\LA_i=\LA_{\Auto^{-1}i}\) for any automorphism \(\Auto\in\Aut(\DecP)\) and principal \(i\in\PlayerSet\).

An optimal symmetric profile is then defined as a symmetric profile \(\LAProfile\) such that for all other symmetric profiles \(\tilde{\LAProfile}\), it is \(U^\DecP(\LAProfile)\geq U^\DecP(\tilde{\LAProfile})\). Note that if there are non-symmetric principals in \(\PlayerSet\), then for a single learning algorithm \(\LA\in\LASet^\DecPSet\), the property that \(\LA,\dotsc,\LA\) is an optimal symmetric profile in the LFC game for \(\DecP\) is stronger than the property that the algorithm \(\LA\) is optimal in the LFC problem for \(\DecP\). The latter only requires that \(U^{\DecP}(\LA,\dotsc,\LA)\geq U^\DecP(\LA',\dotsc,\LA')\) for all \(\LA'\in\LASet^\DecPSet\), while \(\LA,\dotsc,\LA\) being an optimal symmetric profile means that \(U^\DecP(\LA,\dotsc,\LA)\geq U^\DecP(\LAProfile_1,\dotsc,\LAProfile_N)\) for all symmetric profiles \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\), where a profile could potentially include different learning algorithms for non-symmetric principals.

For a simple characterization of symmetric profiles, consider the orbit \(\Aut(\DecP)i\) of a principal \(i\in\PlayerSet\), as defined in Appendix <ref>. Clearly, saying that a profile is symmetric can equivalently be expressed as saying that all principals from the same orbit are assigned the same learning algorithm.

A profile \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecP\) is symmetric if and only if it is \(\LAProfile_i=\LAProfile_j\) for any two symmetric principals \(i,j\in\PlayerSet\).

This can be easily seen from the definition of the orbit and the properties of actions of automorphisms on agents and principals.

Lastly, we define a Nash equilibrium of an LFC game.

A profile of learning algorithms \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\) is a Nash equilibrium of the LFC game for \(D\) if, for any principal \(i\in\PlayerSet\) and learning algorithm \(\LAProfile_i'\in\LASet^\DecPSet\), it is

\[
U^\DecP(\LAProfile)\geq U^\DecP(\LAProfile_i,\LAProfile_{-i}).
\]

Now we show that any optimal symmetric profile is a Nash equilibrium. An analogous result for normal-form games was proven in emmons2021symmetry. Our proof closely follows that proof, adapted to our setting.

Any optimal symmetric strategy profile in an LFC game is a Nash equilibrium.

In the following, fix a Dec-POMDP \(\DecP\) and let \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\). Let \(U:=U^\DecP\).
Let \(\LAProfile_1,\dots,\LAProfile_N\) be an optimal symmetric strategy profile. Towards a contradiction, assume that \(\LAProfile\) is not a Nash equilibrium, i.e., that there is \(i\in\PlayerSet\) and \(\tilde{\LAProfile}_i\in\LASet^\DecPSet\) such that \(U(\tilde{\LAProfile}_i,\LAProfile_{-i})>U(\LAProfile)\). We show that then there is another symmetric strategy profile \(\hat{\LAProfile}\) that achieves a higher payoff than \(\LAProfile\), \(U(\hat{\LAProfile})>U(\LAProfile)\), contradicting the assumption that \(\LAProfile\) was optimal among the symmetric profiles.

To that end, for arbitrary \(p\in(0,1]\) define the profile \(\hat{\LAProfile}_j:=p \tilde{\LAProfile}_i + (1-p)\LAProfile_i\) for any \(j\in\Aut(\DecP)i\) and \(\hat{\LAProfile}_j:=\LAProfile_j\) for \(j\in\PlayerSet\setminus\Aut(\DecP)i\). Note that, since we jointly change all learning algorithms in one orbit \(\Aut(\DecP)i\), the remaining profile \(\hat{\LAProfile}\) is symmetric by Lemma <ref>. Next, let \(K:=|\Aut(\DecP)i|\), choose Dec-POMDPs \(\DecP_1,\dotsc,\DecP_N\in\DecPSet\), and measurable sets \(\mathcal{Z}_1,\dotsc,\mathcal{Z}_N\subseteq\PolicySet^\DecP\). Then it is

\begin{align}
\\
\prod_{l\in\Aut(\DecP)i}\left(p\tilde{\LAProfile}_i(\DecP_l)(\mathcal{Z}_l) + (1-p)\LAProfile_i(\DecP_l)(\mathcal{Z}_l)\right)
\\\nonumber
&= (1-p)^K\prod_{j\in\PlayerSet}\LAProfile_j(\DecP_j)(\mathcal{Z}_j)
\\
\nonumber
&\quad\quad+\sum_{j\in\Aut(\DecP)i}p(1-p)^{K-1}\tilde{\LAProfile}_i(\DecP_j)(\mathcal{Z}_j)\prod_{l\in\PlayerSet\setminus\{ j\}}\LAProfile_l(\DecP_l)(\mathcal{Z}_l)
\\&\quad\quad+
\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}\Mixture^{j,k,\DecP_j}\left(\prod_{j\in\PlayerSet}\mathcal{Z}_j\right)
\\
\nonumber
&= (1-p)^K\otimes_{j\in\PlayerSet}\LAProfile_j(\DecP_j)\left(\prod_{j\in\PlayerSet}\mathcal{Z}_j\right)
\\
\nonumber
&\quad\quad+\sum_{j\in\Aut(\DecP)i}p(1-p)^{K-1}\left(\tilde{\LAProfile}_i(\DecP_j)\otimes_{l\in\PlayerSet\setminus\{ j\}}\LAProfile_l(\DecP_l)\right)\left(\prod_{j\in\PlayerSet}\mathcal{Z}_j\right)
\\&\quad\quad+\label{eq:84}
\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}\Mixture^{j,k,\DecP_j}\left(\prod_{j\in\PlayerSet}\mathcal{Z}_j\right)
\end{align}

where \(\Mixture^{k,\DecP_1,\dotsc,\DecP_N}\) is some measure (not necessarily a probability measure) on the space \(\PolicySet^\DecP\times\dotsb\times\PolicySet^\DecP\) that depends on \(k\) and \(\DecP_1,\dotsc,\DecP_N\), but not on \(p\).
This tells us that we can also decompose the integral with respect to the measure \(\otimes_{j\in\PlayerSet}\hat{\LAProfile}(\DecP_j)\) as in (<ref>). It follows that

\begin{align}&U(\hat{\LAProfile}_1,\dotsc,\hat{\LAProfile}_N)\label{eq:85aa}
\\&=\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(j)}\sim(\SymProfile_j^{-1})^*\hat{\LAProfile}_j(\SymProfile_j^*\DecP),\,j\in\mathcal{N}}
\left[
\\
=\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(j)}\sim\hat{\LAProfile}_j(\SymProfile_j^*\DecP),\,j\in\mathcal{N}}
\left[
%&=\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\Big[
%    \int
\\
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\Big[
\E_{\Policy^{(j)}\sim\LAProfile_j(\SymProfile_j^*\DecP),\,j\in\mathcal{N}}
\left[
\right]
\\\nonumber
\E_{\Policy^{(m)}\sim\LAProfile_m(\SymProfile_m^*\DecP),\,m\in\mathcal{N}\setminus j}
\left[
\E_{\Policy^{(j)}\sim\tilde{\LAProfile}_i(\SymProfile_j^*\DecP)}
\left[
\right]\right]
\\
\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}
\int
\left(\Policy^{(1)},\dotsc,\Policy^{(N)}\right)
\Big]
\\
\sum_{j\in\Aut(\DecP)i}p(1-p)^{K-1}U(\LAProfile_1,\dotsc,\LAProfile_{j-1},\tilde{\LAProfile}_i,\LAProfile_{j+1},\dotsc,\LAProfile_N)
\\\displaybreak
\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k
\\
\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k
\end{align}

for some constants \(C_k\in\mathbb{R}\) for \(k=2,\dotsc,K\), and where we write \(B(k=0,p)\) to denote the probability that a binomial distribution with \(K\) trials and success chance \(p\) has \(0\) successful trials (and \(B(k=1,p)\) analogously). Here, in (<ref>), we use a change of variables for pushforward measures, separately for each measure \(\hat{\LAProfile}_j(\SymProfile_j^*\DecP)\); in (<ref>), we use the linearity of the expectation; and in (<ref>) we use that \(U\) and \(\LAProfile\) are both invariant to symmetries between principals, and thus for \(\Auto\in\Aut(\DecP)\) with \(\Auto^{-1}j=i\), it is

\begin{multline}
\\

Now note that if we can show that

\[(1-B(m=0,p))U(\LAProfile)<B(m=1,p)U(\tilde{\LAProfile}_i,\LAProfile_{-i})+\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k,\]

then it would also follow that

\begin{multline}
\overset{\text{(\ref{eq:85aa})--(\ref{eq:85b})}}{=}
\\
\end{multline}

Thus, this would show that \(\hat{\LAProfile}\) is a symmetric profile with higher payoff than \(\LAProfile\), proving the required contradiction.

In the following, we show the equivalent condition

\[U(\LAProfile)<\frac{B(1,p)}{B(m>0,p)}U(\tilde{\LAProfile}_i,\LAProfile_{-i})+\frac{\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k}

where \(B(m>0,p)=\sum_{k=1}^KB(m=k,p)=1-B(m=0,p)\).
To that end, note that since \(U(\LAProfile)<U(\tilde{\LAProfile}_i,\LAProfile_{-i})\) by assumption, we can choose some small \(\epsilon>0\) such that still

\[U(\LAProfile)<U(\tilde{\LAProfile}_i,\LAProfile_{-i}) - \epsilon.\]

Moreover, note that \(B(m>0,p)\)
is a polynomial in \(p\), and the degree of its nonzero term with lowest degree is \(1\). Similarly, for \(\sum_{k=2,\dotsc,K}p^{K-k}(1-p)^2C_k\), that lowest degree is \(2\).
Hence, it is

\[\frac{\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k}{B(m>0,p)}=
\frac{\sum_{k=2,\dotsc,K}p^{k-1}(1-p)^{K-k}C_k}{C+Q(p)}\]

for some constant \(C\neq 0\) and polynomial \(Q\) in \(p\), and it follows that

\[\lim_{p\rightarrow 0}\frac{\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k}{B(m>0,p)}
\lim_{p\rightarrow 0}\frac{\sum_{k=2,\dotsc,K}p^{k-1}(1-p)^{K-k}C_k}{C+Q(p)}=0.\]

With the same argument, it is also \(\lim_{p\rightarrow0}\frac{B(m>1,p)}{B(m>0,p)}=0\) and thus

\[\lim_{p\rightarrow0}\frac{B(m=1,p)}{B(m>0,p)}
1 - \lim_{p\rightarrow0}\frac{B(m>1,p)}{B(m>0,p)}=1.\]

Hence, we can find some \(p>0\) that is small enough such that both
\[\frac{\sum_{k=2,\dotsc,K}p^k(1-p)^{K-k}C_k}{B(m>0,p)}<\frac{\epsilon}{2}\]

\[1+\frac{\epsilon}{2|U(\tilde{\LAProfile}_i,\LAProfile_{-i})|}>\frac{B(m=1,p)}{B(m>0,p)}>1-\frac{\epsilon}{2|U(\tilde{\LAProfile}_i,\LAProfile_{-i})|}.\]

It follows that

\begin{multline}
U(\LAProfile)<U(\tilde{\LAProfile}_i,\LAProfile_{-i}) - \epsilon
\right)
\\
\end{multline}

which is what we wanted to show. This concludes the proof.

§.§ Evaluating equivariant learning algorithms

In the following, let \(\DecP\) be a Dec-POMDP and define \(\DecPSet:=\{\Isom^*\DecP\mid\Isom\in\Sym(\DecP)\}\).
In the special case in which a learning algorithm is in a sense independent from the used labels, we can find a simpler form of the algorithm's value in the LFC problem for \(\DecP\). To do so, we define the notion of an equivariant learning algorithm.

Let \(\LA\in\LASet^\DecPSet\). Then \(\LA\) is called equivariant if for any two labelings \(\Isom,\IsomSecond\in\Sym(\DecP)\), it is

\[(\Isom^{-1})^*\LA(\Isom^*\DecP)=(\IsomSecond^{-1})^*\LA(\IsomSecond^*\DecP).\]

We believe that a learning algorithm implemented via neural networks and one-hot encodings, as used in our experiments, should be equivariant. To see this, note that by a symmetry argument, the distribution over functions corresponding to a randomly initialized neural network is invariant with respect to coordinate permutations. Assume that actions, observations, and agents of a given problem are implemented as one-hot vectors, i.e., elements of a canonical basis \(\{e_1,\dotsc,e_k\}\in\mathbb{R}^k\) where \(k\in\mathbb{N}\) is the cardinality of the respective set. Then the distribution over randomly initialized neural network policies will also not depend on particular assignments of actions, etc., to one-hot vectors. We conjecture that, if the used optimizer is equivariant with respect to coordinate permutations (i.e., if the parameter dimensions are permuted, then the prescribed updates to the parameters are equally permuted), then the resulting learning algorithm is equivariant. We leave a rigorous exploration of this issue to future work.

An equivariant algorithm can be evaluated in the LFC problem for \(\DecP\) by evaluating its cross-play value in any Dec-POMDP
\(\DecPSecond\in\DecPSet\). The resulting policies can be permuted by random automorphisms or they can be evaluated as they are.

Let \(\LA\in\LASet^\DecPSet\) be equivariant. Then for any \(\Isom\in\Sym(\DecP)\) and \(\DecPSecond=\Isom^*\DecP\in \DecPSet\), it is

\begin{align}U^\DecP(\LA)&=
\E_{\Policy^{(i)}\sim\LA(\DecPSecond),\,i\in\mathcal{N}}\left[\E_{\AutProfile\in\U(\Aut(\DecPSecond)^\PlayerSet)}
\left[
\\
\E_{\Policy^{(i)}\sim\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\end{align}

First, let \(\Isom\in\Sym(\DecP)\) and \(\DecPSecond:=\Isom^*\DecP\). Using the expression of the payoff in the LFC game for \(\DecP\) from Lemma <ref>, it is

\begin{align}
\E_{\SymProfile\sim \U(\Sym(\DecP)^\PlayerSet)}\left[
\E_{\Policy^{(i)}\sim(\SymProfile_i^{-1})^*\LA(\SymProfile_i^*\DecP),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:102a}
\E_{\Policy^{(i)}\sim(\Isom^{-1})^*\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:102c}
\E_{\Policy^{(i)}\sim\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:102b}
\E_{\Policy^{(i)}\sim\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\end{align}

where we use equivariance in (<ref>), a change of variables for pushforward measures in (<ref>), and Theorem <ref> in (<ref>).

Second, by Lemma <ref>, it is \(\Iso(\DecP,\DecPSecond)\subseteq\Sym(\DecP)\). Thus, using
Lemma <ref>, it is \(\Aut(\DecPSecond)\circ\Isom=\Iso(\DecP,\DecPSecond)\subseteq\Sym(\DecP)\).
Hence, it follows that

\begin{align}
\E_{\Policy^{(i)}\sim(\Isom^{-1})^*\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:101a}
\E_{\AutProfile\sim \U(\Aut(\DecPSecond)^\PlayerSet}\left[
\E_{\Policy^{(i)}\sim(\Isom^{-1}\circ\AutProfile_i)^*\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:101b}
\E_{\AutProfile\sim \U(\Aut(\DecPSecond)^\PlayerSet}\left[
\E_{\Policy^{(i)}\sim\AutProfile_i^*\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\\&=\label{eq:101c}
\E_{\AutProfile\sim \U(\Aut(\DecPSecond)^\PlayerSet}\left[
\E_{\Policy^{(i)}\sim\LA(\DecPSecond),\,i\in\mathcal{N}}
\left[
\end{align}

where we again use equivariance in (<ref>), a change of variables and Theorem <ref> in (<ref>), and another change of variables in (<ref>).
This concludes the proof.

If a learning algorithm is equivariant, we can use either of the expressions above to evaluate it in the LFC problem. One may choose the first expression, i.e., apply random automorphisms to policies, since this transformation maps different policies that are equivalent under OP to a unique automorphism-invariant policy and thus reduces the variance of the cross-play values across different samples \(\Policy\sim\LA(\DecP)\). We will introduce these notions of equivalence and automorphism-invariant policies in Appendix <ref>.

Note that an equivariant learning algorithm is not necessarily one that performs well in the LFC problem. For instance, a SP algorithm may be equivariant. However, if an algorithm is equivariant and it does well in cross-play, then the preceding shows that it will also do well in the LFC problem.

§ CHARACTERIZATION OF OTHER-PLAY AND OF LABEL-FREE COORDINATION GAMES

In this section, we define for a given policy \(\Policy\) a policy \(\Psi(\Policy)\) that corresponds to agents choosing local policies that are randomly permuted by automorphisms, and that is itself invariant to pushforward by automorphisms. We then use this self-map on policies \(\Psi\), called the symmetrizer, to characterize both the OP objective and the payoff in an LFC game. This characterization helps us to analyze the OP-optimal policies in the two-stage lever game in Appendix <ref>, and it allows us to prove a stronger result, showing that any OP algorithm that is not concentrated on only one equivalence class in the two-stage lever game is suboptimal in the corresponding LFC problem. We also use this notion of equivalence classes of policies to define OP with tie-breaking in Appendix <ref>, which allows us to then show that random tie-breaking functions exist.

In the following, in Appendix <ref>, we recall the definition of our generalization of OP, and we define policies that are invariant to automorphism. Afterwards, in Appendix <ref>, we introduce the concept of a policy corresponding to a distribution over policies. In Appendix <ref>, we introduce the other-play distribution, in which each agent's local policy is chosen as pushforward by a random automorphism, and we define the symmetrizer. Using these concepts, in Appendix <ref>, we give a new expression for both the OP objective and the payoff in an LFC game. The OP objective can be understood of as transforming a policy into one that is invariant to automorphisms, and evaluating that policy in SP. Finally, in Appendix <ref>, we show that our generalized OP objective can in general not be understood of as the SP objective in a modified Dec-POMDP.

§.§ Generalization of other-play

In the following, fix a Dec-POMDP \(\DecP\). Recall that for a profile of automorphisms \(\AutProfile\in\Aut(\DecP)^\PlayerSet\) and a joint policy \(\Policy\in\PolicySet^\DecP\), we define the joint policy \(\AutProfile^*\Policy:=\hat{\Policy}\), where the local policy \(\hat{\Policy}_i\) of agent \(i\in\PlayerSet\) is given by the local policy of agent \(i\) in the pushforward policy \(\AutProfile^*_i\Policy\). That is, for \(i\in\PlayerSet\), we define

\[\hat{\Policy}_i:= \Proj_i(\AutProfile^*_i\Policy)=
\Policy_{\AutProfile_i^{-1}i}(\AutProfile_i^{-1}\cdot\mid \AutProfile_i^{-1}\cdot).\]

Using this, we define the OP objective as the expected return of a policy that is randomly permuted by such profiles of automorphisms.

Define \(J_\OP^\DecP\colon\PolicySet^\DecP\rightarrow\mathbb{R}\) via

\begin{equation}
J^{D}_\OP(\Policy):=\E_{\AutProfile\sim \U(\Aut(D)^\mathcal{N})}\left[J^{D}(\AutProfile^*\Policy)
\right]\label{eq:1appendix}
\end{equation}

for \(\Policy\in\PolicySet^\DecP\),
where \(\U(\Aut(D)^\mathcal{N})\) is a uniform distribution over \(\Aut(D)^\mathcal{N}\). 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\).

It is clear that this objective always admits a maximum. For instance, we can consider \(\PolicySet^\DecP\) as a subset of \(\prod_{i\in\PlayerSet}[0,1]^{\ActionSet_i\times\AOHistorySet_i}\) with its standard topology. As \(\PolicySet^\DecP\) is a Cartesian product of simplices, it is a compact subset of this space. Moreover, one can check that the objective \(J^\DecP(\Policy)\) is continuous in the policy \(\Policy\), and that for \(\AutProfile\in\Aut(\DecP)^\PlayerSet\), the map \(\Policy\mapsto\AutProfile^*\Policy\) is continuous as well. Thus, also \(J_\OP^\DecP(\Policy)\) is continuous in \(\Policy\), as it is a finite linear combination of continuous functions. By the extreme value theorem, it follows that the function always attains a maximum.

Next, recall our formal definition of an OP learning algorithm as any algorithm that achieves an optimal OP value in expectation.

Let \(\DecPSet\) be a finite set of Dec-POMDPs. A learning algorithm \(\sigma\in\Sigma^\DecPSet\) is called an OP learning algorithm if for any \(\DecP\in\DecPSet\), it is

\[\E_{\Policy\sim\sigma^\OP(\DecP)}[J^\DecP_\OP(\Policy)]=\max_{\Policy\in\PolicySet^\DecP}J^\DecP_\OP(\Policy).\]

Now fix again a Dec-POMDP \(\DecP\) and consider the notion of invariance to automorphism.

A policy \(\Policy\in\PolicySet\) is called invariant to automorphism if \(f^*\Policy=\Policy\) for any \(f\in\Aut(\DecP)\).

Clearly, if a policy is invariant to automorphism, then it has the same OP value and expected return.

Let \(\Policy\in\PolicySet\) be invariant to automorphism. Then

\[J_\OP(\Policy)=J(\Policy).\]

It is

\begin{multline}J_\OP(\Policy)=
\E_{\AutProfile\sim \U(\Aut(D)^\mathcal{N})}\left[J(\AutProfile^*\Policy)
\right]
=\E_{\AutProfile\sim \U(\Aut(D)^\mathcal{N})}\left[J((\Proj_i(\AutProfile_i^*\Policy))_{i\in\PlayerSet})
\right]
\\\overset{\text{(*)}}{=}\E_{\AutProfile\sim \U(\Aut(D)^\mathcal{N})}\left[J((\Proj_i(\Policy))_{i\in\PlayerSet})
\right]

where we have used invariance to automorphism in (*).

In the following, we will show that if a policy \(\Policy\) is not already invariant to automorphism, then one can understand the OP objective as first transforming the policy into a policy \(\Psi(\Policy)\) that is invariant to automorphism by applying the symmetrizer \(\Psi\), and then evaluating the expected return of that policy. In that way, the OP objective ensures that policies cannot make use of arbitrary symmetry-breaking.

§.§ Policies corresponding to distributions over policies

In this section, let some Dec-POMDP \(\DecP\) be fixed. As a first step towards defining the symmetrizer \(\Psi\), we will define policies corresponding to distributions over policies for general distributions. Afterwards, we will turn to the particular policy \(\Psi(\Policy)\) that corresponds to the OP distribution of \(\Policy\).

Recall that we introduced the set of distributions over policies as \(\Delta(\PolicySet)\), the set of measures on the space \((\PolicySet,\mathcal{F})\). Let \(\Distr\in\Delta(\PolicySet)\). For a given distribution \(\Distr\in\Delta(\PolicySet)\) and agent \(i\in\PlayerSet\), the marginal distribution \(\Distr_i\) is defined as \(\Distr_i(\mathcal{Z}_i):=\Distr(\Proj_i^{-1}(\mathcal{Z}_i))\) for any measurable set of local policies \(\mathcal{Z}_i\subseteq\PolicySet_i\).
We say that \(\Distr\) has independent local policies, if \(\Distr=\otimes_i\Distr_i\), i.e., \(\Distr\) decomposes into independent marginal distributions over local policies for each agent. We denote such distributions by \(\Mixture\).

Now let \(\Mixture\in\Delta(\PolicySet)\) be a distribution with independent local policies. We want to construct a policy \(\Policy^\Mixture\) that represents each agent sampling a local policy \(\Policy_i\sim\Mixture_i\) in the beginning of an episode, and then choosing actions according to that policy until the end of the episode. This policy should be equivalent to \(\Mixture\) in the sense that it should yield the same expected return as \(\Mixture\), where we define the expected return of \(\Mixture\) as

\begin{equation}
\label{expected-return-mixture}
\end{equation}

The statement that such a policy exists is analogous and more general than a result by kuhn1953contributions, which says that in an extensive-form game, given some conditions on the game, for every mixed strategy there is an equivalent behavior strategy. Kuhn's theorem is relevant to Dec-POMDPs since there is a correspondence between Dec-POMDPs and extensive-form games oliehoek2006dec. For Dec-POMDPs, the analogous result states that for every distribution over deterministic policies, there is an equivalent stochastic policy.

We cannot directly apply Kuhn's theorem here, as we require a result for distributions over stochastic policies instead of deterministic policies. This is because such a result fits better with our remaining setup—for instance, the domain of the OP objective is the set of stochastic policies, and learning algorithms are defined as distributions over stochastic policies. Nevertheless, our proof is based on similar ideas as, for instance, the proof of Kuhn's theorem in maschler_solan_zamir_2013, after translating between the different formal frameworks of extensive-form games and Dec-POMDPs.

Maybe in the following you can say again that more specifically $\Omega$ is the set of complete histories. (Right?)
\(\Omega\) is just any set on which all of the random variables are defined, but indeed one could just define \(\Omega:=\HistorySet\)  and that would work. If you think this is better, I could explicitly define it that way.

To define a policy \(\Policy^\Mixture\) that is equivalent to \(\Mixture\), we begin by defining a new measure space \((\PolicySet\times\Omega,\mathcal{F}\otimes\PowerSet(\Omega))\), which is the product space of the space of policies \((\PolicySet,\mathcal{F})\) with the Dec-POMDP environment \((\Omega,\PowerSet(\Omega))\). On this space, for a given distribution \(\Mixture\), we define a probability measure \(\Prob_{\Mixture}\) which represents the procedure outlined above, i.e., in which a policy \(\Policy\) is chosen according to \(\Mixture\), and then samples in \(\Omega\) are distributed according to \(\Prob_\Policy\). Formally, we define \(\Prob_\Mixture\) as the unique measure such that

\begin{equation}\label{defn-semidirect-product}
\Prob_\Mixture(\mathcal{Z}\times \mathcal{Q}):=\E_{\Policy\sim\Mixture}\left[\mathds{1}_{\mathcal{Z}}\Prob_\Policy(\mathcal{Q})\right]
\footnote{\(\Prob_\Mixture\) is the semidirect product of \(\Mixture\) with the Markov kernel \(\kappa(\cdot\mid \Policy):=\Prob_\Policy(\cdot)\).}
\end{equation}

for any measurable sets \(\mathcal{Z}\subseteq\PolicySet\) and \(\mathcal{Q}\subseteq\Omega\).
Note that the product sets \(\mathcal{Z}\times\mathcal{Q}\) for measurable \(\mathcal{Z}\subseteq\PolicySet\) and \(\mathcal{Q}\subseteq\Omega\) are a \(\pi\)-system and generate the product \(\sigma\)-Algebra \(\mathcal{F}\otimes\PowerSet(\Omega)\). Hence, by Carathéodory's extension theorem, there is a unique measure satisfying this definition [see][ch. 1]williams1991probability.

On this new product space \(\PolicySet\times\Omega\), define the random variable \(\PolicyLatent\) as the projection onto \(\PolicySet\). We can define histories \(\HistoryRV\) and all other random variables defined on the space \((\Omega,\PowerSet(\Omega))\) by composing them with the projection onto \(\Omega\) (for notational convenience, we denote these random variables using the same symbols in both spaces).

Note that the conditional probability of a particular trajectory \(\History\) given the policy \(\PolicyLatent\) is just the probability of that history under \(\Prob_\PolicyLatent\), that is,

\begin{equation}\label{conditional-probability-mixture}
\Prob_\Mixture(\HistoryRV=\History\mid \PolicyLatent)=\Prob_\PolicyLatent(\HistoryRV=\History)
\end{equation}

for any \(\History\in\HistorySet\).
Here, the conditional probability is a random variable, defined via the conditional expectation

\[\Prob_\Mixture(\HistoryRV=\History\mid\PolicyLatent):=\E_\Mixture\left[\mathds{1}_{\HistoryRV=\History}\mid  \PolicyLatent\right].\]

Intuitively, for a given sample \((\Policy,\omega)\), the value of that random variable is the best estimate of the probability of \(\{\HistoryRV=\History\}\) given \(\PolicyLatent=\Policy\), ignoring \(\omega\). As, in general, \(\{\PolicyLatent=\Policy\}\) may have zero probability, it is impossible to define the conditional probability \(\Prob(\HistoryRV=\History\mid\PolicyLatent=\Policy)\) via \(\Prob(\HistoryRV=\History\mid\PolicyLatent=\PolicyLatent):=\frac{\Prob(\HistoryRV=\History,\PolicyLatent=\Policy)}{\Prob(\PolicyLatent=\Policy)}\). It is still possible to define the conditional expectation \(\E_\Mixture\left[\mathds{1}_{\HistoryRV=\History}\mid  \PolicyLatent\right]\), though.

Here, we briefly give the definition of the conditional expectation and show that (<ref>) is correct. For a reference on conditional expectations, refer to [][ch. 9]williams1991probability. Applied to our setup, the conditional expectation of \(\mathds{1}_{\HistoryRV=\History}\) given \(\PolicyLatent\) is any random variable (which can be shown to be almost surely unique), denoted by \(\E_\Mixture\left[\mathds{1}_{\HistoryRV=\History}\mid  \PolicyLatent\right]\), that is measurable with respect to
\[\sigma(\PolicyLatent):=\{\PolicyLatent^{-1}(\mathcal{Z})\mid \mathcal{Z}\in\mathcal{F}\}=\{\mathcal{Z}\times\Omega\mid\mathcal{Z}\in\mathcal{F}\}\]

such that

\begin{equation}\label{eq:46}\E_{\Mixture}\left[\mathds{1}_{\mathcal{X}}\E_\Mixture\left[\mathds{1}_{\HistoryRV=\History} \mid \PolicyLatent\right]\right]

for all \(\mathcal{X}\in\sigma(\PolicyLatent)\). The fact that the random variable is measurable with respect to \(\sigma(\PolicyLatent)\) can be equivalently expressed as saying that it can be written as a function of \(\PolicyLatent\). Moreover, Equation <ref> says that the conditional expectation should represent correct averages of the random variable \(\mathds{1}_{\HistoryRV=\History}\) over the level-sets in \(\sigma(\PolicyLatent)\).

To show that (<ref>) is correct, let \(\mathcal{X}\in\sigma(\PolicyLatent)\) arbitrary.
Since \(\mathcal{X}\) is of the form \(\mathcal{Z}\times\Omega\), and \(\{\HistoryRV=\History\}=\PolicySet\times\mathcal{Q}\) for some \(\mathcal{Q}\subseteq\Omega\), it is \((\mathcal{Z}\times\Omega)\cap\{\HistoryRV=\History\}=\mathcal{Z}\times\mathcal{Q}\).
Using Equation <ref>, it follows that

\begin{multline}
\E_\Mixture\left[\mathds{1}_{\mathcal{X}}\Prob_\PolicyLatent(\HistoryRV=\History)\right]
\E_\Mixture\left[\mathds{1}_{\mathcal{Z}\times\Omega}\Prob_\PolicyLatent(\mathcal{Q})\right]
=\E_{\Policy\sim \Mixture}\left[\mathds{1}_{\mathcal{Z}}(\Policy)\Prob_\Policy(\mathcal{Q})\right]
\\
\overset{(\ref{defn-semidirect-product})}{=}
\Prob_\Mixture(\mathcal{Z}\times \mathcal{Q})
\end{multline}

Hence, letting \(\E_\Mixture[\mathds{1}_{\HistoryRV=\History}\mid \PolicyLatent]:=\Prob_\PolicyLatent(\HistoryRV=\History)\) satisfies condition (<ref>). \(\Prob_\PolicyLatent(\HistoryRV=\History)\) is also \(\sigma(\PolicyLatent)\)-measurable, since it is just a function of \(\PolicyLatent\).

We will repeatedly make use of (<ref>) in the following, together with the tower property, which, applied to our case, says that

\begin{equation}\label{eq:equation-tower-prop-z}\Prob_\Mixture(\HistoryRV=\History)=\E_\Mixture\left[\Prob_\Mixture\left(\HistoryRV=\History\mid\PolicyLatent\right)\right]
\overset{(\ref{conditional-probability-mixture})}{=}
\E_\Mixture\left[\Prob_\PolicyLatent\left(\HistoryRV=\History\right)\right]
\end{equation}

for any history \(\History\in\HistorySet\) [see][ch. 9.7]williams1991probability.

Using the measure space defined above, we now define a local policy \(\Policy_i^{\Mixture_i}\) for an agent \(i\in\PlayerSet\), corresponding to a distribution \(\Mixture_i\in\Delta(\PolicySet_i)\). For an action \(\Action_i\in\ActionSet_i\) and an action-observation history \( \AOHistory_{i,t}\in\AOHistorySet_{i,t}\), we define \(\Policy_i^{\Mixture_i}(a_i\mid \AOHistory_{i,t})\) as the probability that agent \(i\), who follows a policy that is sampled from \(\Mixture_i\), plays action \(\Action_i\), conditional on $\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\}$.

Let \(i\in\PlayerSet\) and let \(\Mixture_i\in\Delta(\PolicySet_i)\) be a distribution over local policies of agent \(i\). We define the local policy \(\Policy_i^{\Mixture_i}\) corresponding to \(\Mixture_i\) in the following way. For \(\Action_i\in\ActionSet_i\), \(t\in\{0,\dotsc,\Tmax\}\) and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\), let

\begin{equation}
\Policy^{\Mixture_i}_i(a_i\mid \AOHistory_{i,t})
:= \Prob_{\Mixture_i\otimes\Mixture_{-i}}(\ActionRV_{i,t}=a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}),\end{equation}

where \(\Mixture_{-i}\) is any distribution over \(\PolicySet_{-i}\) with independent local policies such that
\[\Prob_{\Mixture_i\otimes\Mixture_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0.\]
If no such distribution exists, we let \(\Policy^\Mixture_i(a_i\mid \AOHistory_{i,t}):=\frac{1}{|\ActionSet_i|}\).

Note that if \(\Prob_{\Mixture_i\otimes\Mixture_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})=0\) for all the distributions \(\Mixture_{-i}\in\Delta(\PolicySet_{-i})\) over opponent policies, then agent \(i\)'s action-observation history \(\AOHistory_{i,t}\) is almost never reached, independent of the other agents' policies. In that case, we can define the policy arbitrarily and this will never matter for the distribution over histories under \(\Prob_{\Mixture_i\otimes\Mixture_{-i}}\), and as we will see, neither for the distribution under \(\Prob_{\Policy_i^{\Mixture_i},\Policy_{-i}}\) for arbitrary \(\Policy_{-i}\).

First, we need to make sure that \(\Policy_i^{\Mixture_i}\) is well-defined, i.e., it does not depend on the chosen distribution \(\Mixture_{-i}\). Unfortunately, the proof for the following Lemma is somewhat technical.

Let \(i\in\PlayerSet\), \(\Mixture_i\in\Delta(\PolicySet_i)\), \(t\in\{0,\dotsc,\Tmax\}\), \(\AOHistory_{i,t}\in\AOHistorySet_i\), and \(\Action_i\in\ActionSet_i\). Let \(\Mixture_{-i},\Mixture'_{-i}\in\Delta(\PolicySet_{-i})\) be any two distributions with independent local policies such that \(\Prob_{\Mixture_i\otimes\Mixture_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\) and \(\Prob_{\Mixture_i\otimes\Mixture'_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\). Then it is

\[\Prob_{\Mixture_i\otimes\Mixture_{-i}}(\ActionRV_{i,t}=a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t})
=\Prob_{\Mixture_i\otimes\Mixture'_{-i}}(\ActionRV_{i,t}=a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}).\]

In the following, let \(i\in\PlayerSet, t\in\{0,\dotsc,\Tmax\}\) be fixed.
Our goal is to find an expression for the distribution of \(\PolicyLatent_i\) given \(\AOHistoryRV_{i,t}\) that only depends on \(\Mixture_i\). If we can do that, we can also show that the probability of a particular action chosen by an agent is independent of the distributions over other agents' policies. To begin, we analyze the joint distribution of \(\PolicyLatent_i\) and \(\AOHistoryRV_{i,t}\) for an arbitrary distribution \(\Mixture\in\Delta(\PolicySet)\) with independent local policies. Note that by assumption, the \(Z_j\) are independent for \(j\in\PlayerSet\) under \(\Mixture\).
We now show that conditioning on \(\AOHistoryRV_{i,t}\) still leaves \(Z_i\) independent from \(Z_{-i}\).

[draw, circle, text centered, inner sep=0pt,minimum size=1cm] (z) $Z_i$;

[draw, circle, below=of z, text centered,fill=black!20, inner sep=0pt,minimum size=1cm] (a10) $A_{i,0}$;
[below=of a10, text centered, inner sep=0pt,minimum size=1cm] (dots1) $\dots$;

[draw, circle, right=of a10, text centered,fill=black!20, inner sep=0pt,minimum size=1cm] (o11) $O_{i,1}$;
[below=of o11, text centered, inner sep=0pt,minimum size=1cm] (dots2) $\dots$;

[draw, circle, right=of o11, text centered,fill=black!20, inner sep=0pt,minimum size=1cm] (a11) $A_{i,1}$;
[below=of a11, text centered, inner sep=0pt,minimum size=1cm] (dots3) $\dots$;

[draw, circle, right=of a11, text centered,fill=black!20, inner sep=0pt,minimum size=1cm] (o12) $O_{i,2}$;
[circle, below=of o12, text centered, inner sep=0pt,minimum size=1cm] (dots4) $\dots$;

[draw, circle, right=of o12, text centered, inner sep=0pt,minimum size=1cm] (a12) $A_{i,2}$;
[circle, below=of a12, text centered, inner sep=0pt,minimum size=1cm] (dots5) $\dots$;
[circle, right=of a12, text centered, inner sep=0pt,minimum size=1cm] (dots6) $\dots$;

[magenta, very thick](z) to [out=0, in=120] (a11);
[magenta, very thick](a11)–(o12);
[magenta, very thick](o12)–(dots4);
[teal, very thick] (z) to [out=15,in=120]  (a12);
[teal, very thick] (a12) – (dots5);

z a10;
[-> ] (z) to [out=0,in=120]  (a11);
[-> ] (z) to [out=15,in=120]  (a12);
[-> ] (z) to [out=30,in=120]  (dots6);

[-> ] (a10) –  (o11);
[-> ] (a10) –  (dots1);

[-> ] (o11) –  (a11);
[-> ] (dots2) –  (o11);

[-> ] (a11) –  (o12);
[-> ] (a11) –  (dots3);

[-> ] (dots4) –  (o12);
[-> ] (o12) –  (a12);
[-> ] (a12) – (dots5);
[-> ] (a12) – (dots6);

[-> ] (a10) to [out=30,in=150] (a11);
[-> ] (a10) to [out=30,in=140] (a12);
[-> ] (a11) to [out=30,in=160] (a12);

Part of a Bayesian graph of the random variables on the space \(\PolicySet\times\Omega\). Here, the gray-marked nodes are part of the action-observation history \(\AOHistoryRV_{i,2}\). Conditional on \(\AOHistoryRV_{i,2}\), there is an unblocked path, marked in teal, from \(Z_i\) to \(A_{i,2}\) and to nodes below \(A_{i,2}\) not displayed here, making them \(d\)-connected and thus dependent. The path marked in a lighter magenta, on the other hand, is blocked, illustrating that the part of the graph below \(O_{i,2}\) may be independent of \(Z_i\).

To see this, one can consider a Bayesian graph of the random variables on the space \(\PolicySet\times\Omega\). For a reference on Bayesian graphs and the concepts discussed below, refer to [][ch. 1.2]Pearl2009-bb. In Figure <ref>, we have displayed a part of this Bayesian graph with nodes for the agent \(i\), indicating left-out parts of the graph with dots. The arrows in the graph illustrate the dependence relationships between the different variables: if there is an arrow from one node to another, this means that the other node depends on that node. Nodes belonging to the action-observation history \(\AOHistoryRV_{i,2}\) of agent \(i\) are marked in gray.

Given such a Bayesian graph, the \(d\)-separation criterion tells us which variables are dependent after conditioning on a set \(\mathcal{V}\) of variables. The criterion specifies valid, “unblocked” paths in the graph, depending on the graph structure and the nodes that are being conditioned on. The \(d\)-separation criterion says that two variables are dependent conditional on the variables in \(\mathcal{V}\) if and only if there is an unblocked path in the graph between them; the variables are then said to be \(d\)-connected. If there is no path, then the variables are \(d\)-separated.

An unblocked path can contain a chain \(X\rightarrow W\rightarrow Y\) or a fork \(X\leftarrow W\rightarrow Y\) if \(W\) is not being conditioned on. If it contains a collider \(X\rightarrow W\leftarrow Y\), on the other hand, i.e., the two incident edges to \(W\) in the path are both directed towards the node, then the path is blocked, unless \(W\) or a descendant of \(W\) in the graph is in \(\mathcal{V}\). For instance, the path that is marked in a lighter magenta in Figure <ref> is blocked—the path cannot go from \(Z_i\) over \(\ActionRV_{i,1}\) to \(\ObservationRV_{i,2}\). An unblocked path is marked in teal.

changed the following a bit
Using the \(d\)-separation criterion, one can tell that \(Z_i\) may be \(d\)-separated from left-out parts of the graph in Figure <ref> indicated by the dots below \(\ActionRV_{i,0}\), for instance, but that it is \(d\)-connected to some variables in the part below \(\ActionRV_{i,2}\). We do not work this out here completely, but once considering the entire graph, one can see that there is no unblocked path from \(Z_i\) to the \(Z_{-i}\), because such a path would inevitably have to traverse a collider that is not being conditioned on and that has no descendants that are being conditioned on (for instance, the observations of all other agents are colliders that connect the \(Z_{-i}\) with \(Z_i\)). Generalizing from the example of \(\AOHistory_{i,2}\), we can conclude that \(Z_i\) and \(Z_{-i}\) are independent given \(\AOHistoryRV_{i,t}\).

Now let \(\mathcal{Z}_j\subseteq \PolicySet_j\) be measurable sets for \(j\in\PlayerSet\), and let \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\) arbitrary. Then, using the above, it follows that

\begin{align}
&\E_{\Policy_{-i}\sim\Mixture_{-i}}[\mathds{1}_{\Policy_{-i}\in \mathcal{Z}_{-i}}\E_{\PolicyLatent_i\sim\mu_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]]
\\\label{eq:27b}
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i,\AOHistoryRV_{i,t}=\AOHistory_{i,t},\PolicyLatent_{-i}\in \mathcal{Z}_{-i})
\\
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t},\PolicyLatent_{-i}\in C_{-i})
\Prob_{\Mixture}(\AOHistoryRV_{i,t}=\AOHistory_{i,t},\PolicyLatent_{-i}\in \mathcal{Z}_{-i})
\\
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})
\Prob_{\Mixture}(\AOHistoryRV_{i,t}=\AOHistory_{i,t},\PolicyLatent_{-i}\in \mathcal{Z}_{-i})
\\\label{eq:27c}
\E_{\Policy_{-i}\sim\Mixture_{-i}}[\mathds{1}_{\Policy_{-i}\in \mathcal{Z}_{-i}}\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\E_{\Policy_i\sim\mu_i}[\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]],
\end{align}

where we use the argument about conditional independence in (<ref>) and the definition of \(\Prob_\Mixture\) from Equation <ref> in (<ref>) and (<ref>).

Since the sets \(\mathcal{Z}_{j}\) for \(j\in\PlayerSet\setminus\{i\}\) were arbitrary, it follows that \(\Mixture_{-i}\)-almost surely, it is
\begin{multline}\label{equation-marginals-are-equal-1}\E_{\Policy_i\sim\mu_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\\=
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})].\end{multline}

Moreover, since \(\Mixture\) was arbitrary, Equation <ref> holds for any distribution with independent local policies. If we divide by the term \(\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]\), this becomes

\begin{equation}\label{eq:200}
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})
=\frac{\E_{\Policy_i\sim\mu_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]}{
\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]},\end{equation}

which gives us a formula for the distribution of \(\PolicyLatent_i\) given \(\AOHistoryRV_{i,t}\) under the measure \(\Prob_\Mixture\) that is independent of the distributions \(\Mixture_{-i}\). But to be able to do so, we have to find a value for \(\PolicyLatent_{-i}\) such that \(\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,Z_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]\) is nonzero under \(\Mixture\).

Now let \(\Mixture_i\in\Delta(\PolicySet_i)\) and let \(\Mixture_{-i},\Mixture'_{-i}\in\Delta(\PolicySet_{-i})\) be any two distributions with independent local policies such that \(\Prob_{\Mixture_i\otimes\Mixture_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\) and \(\Prob_{\Mixture_i\otimes\Mixture'_{-i}}( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\). Define \(\Mixture_i':=\Mixture_i\), \(\Mixture:=\Mixture_i\otimes\Mixture_{-i}\), and \(\Mixture':=\Mixture_i\otimes\Mixture'_{-i}\).
Our goal is to show that

\[\Prob_{\Mixture}(\ActionRV_{i,t}=a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t})
=\Prob_{\Mixture'}(\ActionRV_{i,t}=a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}).\]

To that end, we define a third distribution \(\MixtureHat:=\otimes_{j\in\PlayerSet}(\frac{1}{2}\Mixture_j+\frac{1}{2}\Mixture_j')\). Apparently, it is then \(\Mixture_i=\MixtureHat_i=\Mixture'_i\) and also \(\MixtureHat\) has independent local policies.
We now prove separately for \(\Mixture\) and \(\Mixture'\) that the distribution of \(\PolicyLatent_i\) given \(\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\}\) under \(\Mixture\) respectively \(\Mixture'\) is equal to the one under \(\MixtureHat\). To do so, we use that \(\Mixture\) and \(\Mixture'\) are absolutely continuous with respect to \(\MixtureHat\) to find desired values for \(\PolicyLatent_{-i}\) such that we can apply Equation <ref>.

First, let \(\mathcal{Z}_i\in\PolicySet_i\) be an arbitrary measurable set. Using Equation <ref>, we can find measurable sets \(\mathcal{Z}_{-i},\hat{\mathcal{Z}}_{-i}\subseteq\PolicySet_{-i}\) such that \(\Mixture_{-i}(\mathcal{Z}_{-i})=1=\MixtureHat_{-i}(\hat{\mathcal{Z}}_{-i})\), and such that

\begin{multline}\label{eq:28a}\E_{\Policy_i\sim\mu_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\\=
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})].\end{multline}

for any \(\Policy_{-i}\in \mathcal{Z}_{-i}\)

\begin{multline}\label{eq:28b}\E_{\Policy_i\sim\MixtureHat_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,\PolicyHat_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\\=
\Prob_{\hat{\Mixture}}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,\PolicyHat_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})].\end{multline}

for any \(\PolicyHat_{-i}\in \hat{\mathcal{Z}}_{-i}\).

Next, it follows that \(\Prob_\Mixture(\{Z_{-i}\in \mathcal{Z}_{-i}\}\cap\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\})>0\),
which by definition of \(\MixtureHat\) implies
\(\Prob_{\MixtureHat}(\{Z_{-i}\in \mathcal{Z}_{-i}\}\cap\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\})>0\)
and thus by definition of \(\hat{\mathcal{Z}}_{-i}\) also \(\Prob_{\MixtureHat}(\{Z_{-i}\in \mathcal{Z}_{-i}\cap\hat{\mathcal{Z}}_{-i}\}\cap\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\})>0\). Since

\begin{multline}\Prob_{\MixtureHat}(\{Z_{-i}\in \mathcal{Z}_{-i}\cap\hat{\mathcal{Z}}_{-i}\}\cap\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\})
\\

there must be
\(\Policy_{-i}\in \Proj_{\PolicySet_{-i}}(\{Z_{-i}\in \mathcal{Z}_{-i}\cap\hat{\mathcal{Z}}_{-i}\}\cap\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\})\)
such that

\[\E_{\Policy_i\sim\MixtureHat_i}[\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]>0.\]

Lastly, using that \(\MixtureHat_i=\Mixture_i\), it follows that

\begin{equation}\E_{\Policy_i\sim\Mixture_i}[\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]

Hence, we can use Equations <ref> and <ref> to conclude that

\begin{align}
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})
\E_{\Policy_i\sim\mu_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\E_{\Policy_i\sim\mu_i}[\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\\
\E_{\Policy_i\sim\MixtureHat_i}[\mathds{1}_{\Policy_i\in \mathcal{Z}_i}\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\E_{\Policy_i\sim\MixtureHat_i}[\Prob_{\Policy_i,\Policy_{-i}}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})]
\\
\Prob_{\MixtureHat}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t}).
\end{align}

Now note that one can make an exactly analogous argument for \(\Mixture'\) and \(\MixtureHat\), potentially using a different \(\Policy_{-i}\). Hence, it follows that

\begin{equation}\label{equation-marginals-are-equal-2}
\Prob_{\Mixture}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})=\Prob_{\MixtureHat}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})=\Prob_{\Mixture'}(Z_i\in \mathcal{Z}_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t}).
\end{equation}

Since \(\mathcal{Z}_i\in\PolicySet_i\) was arbitrary, it follows that the distribution of \(Z_i\) given \(\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\}\) is equal under \(\Prob_\Mixture\) and \(\Prob_{\Mixture'}\).

To conclude the proof, we can use this to show that also the distribution of actions under \(\Prob_\Mixture\) and \(\Prob_{\Mixture'}\) are equal, conditional on \(\{\AOHistoryRV_{i,t}=\AOHistory_{i,t}\}\). For \(\Action_i\in\ActionSet_i\), it is

\begin{align}
\label{eq:32a}
\Prob_{\Mixture}(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t})
&=\E_{\Mixture}\left[\Prob_\Mixture(\ActionRV_{i,t}=\Action_i\mid\PolicyLatent, \AOHistoryRV_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\\label{eq:32c}
&=\E_{\Mixture}\left[\Prob_\PolicyLatent(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\&=\E_{\Mixture}\left[\PolicyLatent_i(\Action_i\mid \AOHistory_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\
\E_{\Mixture'}\left[\PolicyLatent_i(\Action_i\mid \AOHistory_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\&=\E_{\Mixture'}\left[\Prob_\PolicyLatent(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\
\label{eq:32d}
&=\E_{\Mixture'}\left[\Prob_{\Mixture'}(\ActionRV_{i,t}=\Action_i\mid \PolicyLatent,\AOHistoryRV_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}\right]
\\
\label{eq:32b}
&=\Prob_{\Mixture'}(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}),
\end{align}

where we have used the tower property in (<ref>) and (<ref>), and Equation <ref> in (<ref>) and (<ref>). This is what we wanted to show.

In the following, we write \(\Policy^\Mixture:=(\Policy_i^{\Mixture_i})_{i\in\PlayerSet}\) for the joint policy corresponding to a distribution \(\Mixture\) with independent local policies.
Our next goal is to prove that the distribution over histories is the same under \(\Prob_{\Policy^\Mixture}\) as under \(\Prob_{\Mixture}\).

Consider any distribution \(\Mixture\in\Delta(\PolicySet)\) with independent local policies. Let \(\Policy^\Mixture\) be the joint policy corresponding to \(\Mixture\), as defined above. Then the history \(\HistoryRV\) has the same distribution under \(\Prob_\Mixture\) as under \(\Prob_{\Policy^\Mixture}\). In particular,
it is \(J^D(\Mixture)=J^D(\Policy^\Mixture)\).

Fix a distribution \(\Mixture\in\Delta(\PolicySet)\) with independent local policies. We show by induction that for all \(t\in\{0,\dotsc,\Tmax\}\), it is \(\Prob_\Mixture(\HistoryRV_t=\History_t)=\Prob_{\Policy^\Mixture}(\HistoryRV_t=\History_t)\) for any \(\History_t\in\HistorySet_t\).

First, note that by Definition <ref>, for any \(i\in\PlayerSet,\Action_i\in\ActionSet_i, t\in\{0,\dotsc,h\}\), and \(\AOHistory_{i,t}\in\AOHistorySet_i\) such that \(\Prob_\Mixture( \AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\), it is

\begin{equation}\label{eq:5}\Prob_{\Policy^\Mixture}(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t})=\Policy^{\Mixture_i}_i(a_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}) =
\Prob_\Mixture(\ActionRV_{i,t}=\Action_i\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}).
\end{equation}

In particular, this holds for \(t=0\), in which case it is \(\AOHistoryRV_{i,0}=\emptyset\) for \(i\in\PlayerSet\). Hence, for \(\Action\in\ActionSet, \State\in\StateSet\), it is

\begin{multline}\Prob_\Mixture(\StateRV_0=\State,\ActionRV_0=\Action)
%\overset{\text{(i)}}{=}\E_\Mixture[\Prob_\Mixture(\StateRV_0=\State,\ActionRV_{0}=\Action\mid Z)]
\overset{(\ref{eq:equation-tower-prop-z})}{=}
\E_\Mixture[\Prob_Z(\StateRV_0=\State,\ActionRV_{0}=\Action)]
\\
\overset{\text{(i)}}{=}b_0(\State)\E_\Mixture[\Prob_Z(\ActionRV_0=\Action)]
b_0(\State)\E_\Mixture[\prod_{i\in\PlayerSet}Z_i(\ActionRV_{i,0}\mid \emptyset)]
\overset{\text{(ii)}}{=}b_0(\State)\prod_{i\in\PlayerSet}\E_\Mixture[Z_i(\Action_{i}\mid \emptyset)]
\\
\overset{\text{(\ref{eq:equation-tower-prop-z})}}{=}
\overset{(\ref{eq:5})}{=}
\\
\end{multline}

Here, we also use
(i) the fact that that the initial state distribution does not depend on the policy, and (ii) the fact that \(\Mixture\) has independent local policies and thus also the \(Z_i\) are independent in the probability space \(\Prob_\Mixture\).

Next, assume that \(0\leq t-1\leq \Tmax\) and \(\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})=\Prob_{\Policy^\Mixture}(\HistoryRV_{t-1}=\History_{t-1})\) for any \(\History_{t-1}\in\HistorySet_{t-1}\). Let \(\History_{t-1}=(\State_0,\Action_0,\Reward_0,\State_1,\dotsc,\Reward_{t-1})\in\HistorySet_{t-1}\) arbitrary such that
\(\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})=\Prob_{\Policy^\Mixture}(\HistoryRV_{t-1}=\History_{t-1})>0\). As in the proof of Lemma <ref>, it follows from considering the \(d\)-separation criterion on a Bayesian graph of the random variables defined on \(\PolicySet\times\Omega\) that conditioning on \(\HistoryRV_{t-1}\) does not make the \(Z_i\) dependent [see][ch. 1.2]Pearl2009-bb. The same criterion also says that, after conditioning on \(A_{i,t-1}\) and \(\AOHistoryRV_{i,t-1}\), one cannot gain additional information about \(Z_i\) from the other components of \(\HistoryRV_{t-1}\) or from \(\ObservationRV_{i,t}\) (that is, \(A_{i,t-1}\) and \(\AOHistoryRV_{i,t-1}\) \(d\)-separate \(Z_i\) from the rest of the history).
Using this in (<ref>), it follows for arbitrary \(\State_t,\Observation_t,\Action_t,\Reward_t\) that

\begin{align}\label{eq:26c}
&\Prob_\Mixture(\StateRV_t=\State_t,\ObservationRV_t=\Observation_t,\ActionRV_t=\Action_t,\RewardRV_t=\Reward_t\mid \HistoryRV_{t-1}=\History_{t-1})
\\
&=\E_\Mixture[\Prob_\Mixture(\StateRV_t=\State_t,\ObservationRV_t=\Observation_t,\ActionRV_t=\Action_t,\RewardRV_t=\Reward_t\mid \HistoryRV_{t-1},Z)\mid \HistoryRV_{t-1}=\History_{t-1}]
\\
=\E_\Mixture[P(\State_t\mid \State_{t-1},\Action_{t-1})O(\Observation_t\mid \State_t,\Action_{t-1})\prod_{i\in\PlayerSet}Z_i(\Action_{i,t}\mid\AOHistory_{i,t})\mathds{1}_{\RewardFunction(\State,\Action)=\Reward}\mid \HistoryRV_{t-1}=\History_{t-1}]
\\
\nonumber
P(\State_t\mid \State_{t-1},\Action_{t-1})O(\Observation_t\mid \State,\Action_{t-1})
\\\label{eq:26a}
&\quad\prod_{i\in\PlayerSet}\E_\Mixture[Z_i(\Action_{i,t}\mid \AOHistory_{i,t})\mid \ActionRV_{i,t-1}=\Action_{i,t-1}, \AOHistoryRV_{i,t-1}=\AOHistory_{i,t-1}]\mathds{1}_{\RewardFunction(\State_t,\Action_t)=\Reward_t}
\\
&=P(\State_t\mid \State_{t-1},\Action_{t-1})O(\Observation_t\mid \State,\Action_{t-1})\prod_{i\in\PlayerSet}\Prob_\Mixture(\ActionRV_{i,t}=\Action_{i,t}\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\mathds{1}_{\RewardFunction(\State_t,\Action_t)=\Reward_t}
\\\label{eq:26b}
&=P(\State_t\mid \State_{t-1},\Action_{t-1})O(\Observation_t\mid \State,\Action_{t-1})\prod_{i\in\PlayerSet}\Prob_{\Policy^\Mixture}(\ActionRV_{i,t}=\Action_{i,t}\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})\mathds{1}_{\RewardFunction(\State_t,\Action_t)=\Reward_t}
\\
&= \Prob_{\Policy^\Mixture}(\StateRV_t=\State_t,\ObservationRV_t=\Observation_t,\ActionRV_t=\Action_t,\RewardRV_t=\Reward_t\mid \HistoryRV_{t-1}=\History_{t-1}).\label{eq:26d}
\end{align}

In (<ref>), we again use Equation <ref>, which is possible since  \(\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})>0\) implies that also \(\Prob_\Mixture( \AOHistoryRV_{i,t-1}=\AOHistory_{i,t-1})>0\), where \(\AOHistory_{i,t-1}\) is defined as the projection of \(\History_{t-1}\) onto \(\AOHistorySet_{i,t-1}\).

To conclude the inductive step, let \(\History_t\in\HistorySet_t\) and choose \(\History_{t-1}\) as the projection of \(\History_t\) onto \(\HistorySet_{t-1}\). If
\[\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})=\Prob_{\Policy^\Mixture}(\HistoryRV_{t-1}=\History_{t-1})=0,\]

necessarily also \(\Prob_\Mixture(\HistoryRV_{t}=\History_{t})=\Prob_{\Policy^\Mixture}(\HistoryRV_{t}=\History_{t})=0\) and there is nothing more to show. Assume now that this is not the case. Using the inductive hypothesis and Equations (<ref>)–(<ref>) in (*), it then follows that

\begin{multline}\Prob_\Mixture( \HistoryRV_{t}=\History_t)
=\Prob_\Mixture( \HistoryRV_{t}=\History_t\mid \HistoryRV_{t-1}=\History_{t-1})\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})
\\=\Prob_{\Mixture}(\StateRV_t=\State_t,\ObservationRV_t=\Observation_t,\ActionRV_t=\Action_t,\RewardRV_t=\Reward_t\mid \HistoryRV_{t-1}=\History_{t-1})\Prob_\Mixture(\HistoryRV_{t-1}=\History_{t-1})
\\\overset{\text{(*)}}{=}\Prob_{\Policy^\Mixture}(\StateRV_t=\State_t,\ObservationRV_t=\Observation_t,\ActionRV_t=\Action_t,\RewardRV_t=\Reward_t\mid \HistoryRV_{t-1}=\History_{t-1})\Prob_{\Policy^\Mixture}(\HistoryRV_{t-1}=\History_{t-1})
\\=\Prob_{\Policy^\Mixture}( \HistoryRV_{t}=\History_t).
\end{multline}

This concludes the induction. In particular, it follows that
\[\Prob_\Mixture(\HistoryRV_\Tmax=\History_\Tmax)=\Prob_{\Policy^\Mixture}(\HistoryRV_\Tmax=\History_\Tmax).\]
Hence, \(\HistoryRV=\HistoryRV_\Tmax\) has the same distribution under both \(\Prob_\Mixture\) and \(\Prob_{\Policy^\Mixture}\).

Turning to the “in particular” statement, we can use the tower property (i) and Equation <ref> (ii) to follow that

\begin{multline}J(\Policy^\Mixture)=\E_{\Policy^\Mixture}[\sum_{t=1}^hR_t]=\E_\Mixture[\sum_{t=1}^hR_t]
\\
\overset{\text{(i)}}{=}\E_\Mixture\left[\E_\Mixture\left[\sum_{t=1}^hR_t\,\middle\vert\, Z\right]\right]
\overset{\text{(ii)}}{=}\E_\Mixture\left[\E_Z\left[\sum_{t=1}^hR_t\right]\right]
\\
=\E_{\Policy\sim \Mixture}[J(\Policy)]
\end{multline}

Before we turn to the OP distribution, we prove another useful Lemma, stating that the mapping from distributions to corresponding joint policies and the pushforward by isomorphisms commute. That is, the policy corresponding to the pushforward of a distribution and the pushforward of the policy corresponding to that distribution are the same.

Let \(\DecP,\DecPSecond\) be isomorphic Dec-POMDPs with isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\). Let \(\Policy\in\PolicySet^\DecP\) and let \(\Mixture\in \Delta(\PolicySet^\DecP)\) be any distribution with independent local policies. Then

\[\Isom^*\Policy^\Mixture=\Policy^{\Isom^*\Mixture}.\]

First, we have to find an expression for the marginal distributions \((\Isom^*\Mixture)_i\) and prove that \(\Isom^*\Mixture\) is a distribution with independent local policies. To that end, consider measurable sets \(\mathcal{Z}_i\subseteq\PolicySet^\DecPSecond_i\) for \(i\in\PlayerSet^\DecPSecond\) and define \(\mathcal{Z}:=\prod_{i\in\PlayerSet^\DecPSecond}\mathcal{Z}_i\). In the following, we adopt the notation \(\Policy_i\circ\Isom:= \Policy_i(\Isom\cdot\mid\Isom\cdot)\) and \(\mathcal{Z}_i\circ \Isom:= \{\Policy_i\circ\Isom\mid\Policy_i\in\mathcal{Z}_i\}\). Note that

\begin{multline}\label{eq:29}(\Isom^*)^{-1}(\mathcal{Z})
=\{\Policy\mid \Isom^*\Policy\in\mathcal{Z}\}
=\{\Policy\mid \forall i\in\PlayerSet^\DecPSecond\colon \Policy_{\Isom^{-1}i}\circ\Isom^{-1}\in\mathcal{Z}_i)\}
\\
=\{\Policy\mid \forall j\in\PlayerSet^\DecP\colon \Policy_{j}\in\mathcal{Z}_{\Isom j}\circ\Isom\}
=\prod_{j\in\PlayerSet^\DecP}\mathcal{Z}_{\Isom j}\circ\Isom.
\end{multline}

Hence, using in (i) that \(\Mixture\) has independent local policies, it follows that

\begin{multline}\label{eq:30}(\Isom^*\Mixture)(\mathcal{Z})
\overset{(\ref{eq:29})}{=}\Mixture(\prod_{j\in\PlayerSet^\DecP}\mathcal{Z}_{\Isom j}\circ \Isom)
\overset{\text{(i)}}{=}\prod_{j\in\PlayerSet^\DecP}\Mixture_j(\mathcal{Z}_{\Isom j}\circ \Isom)
=\prod_{i\in\PlayerSet^\DecPSecond}\Mixture_{\Isom^{-1}i}(\mathcal{Z}_{i}\circ \Isom).
\end{multline}

Now let \(i\in\PlayerSet^\DecPSecond\) arbitrary. With the choice of \(\hat{\mathcal{Z}}_i:=\mathcal{Z}_i\) and \(\hat{\mathcal{Z}}_k:=\PolicySet_k^\DecPSecond\) for all \(k\in\PlayerSet^\DecPSecond\setminus\{i\}\), it is

\begin{multline}\label{eq:70}(\Isom^*\Mixture)_i(\mathcal{Z}_i)
\\
\overset{(\ref{eq:30})}{=}
\prod_{k\in\PlayerSet^\DecPSecond}\Mixture_{\Isom^{-1}k}(\hat{\mathcal{Z}}_{k}\circ \Isom)
=\Mixture_{\Isom^{-1}i}(\mathcal{Z}_{i}\circ \Isom)

\(\Mixture_{\Isom^{-1}k}(\hat{\mathcal{Z}}_{k}\circ \Isom)=\Mixture_{\Isom^{-1}k}(\PolicySet_{ k}\circ\Isom)=\Mixture_{\Isom^{-1}k}(\PolicySet_{\Isom^{-1} k})=1\)
for any \(k\in\PlayerSet^\DecPSecond\setminus\{i\}\).

Since \(i\) was arbitrary, this shows that \(\Isom^*\Mixture(\mathcal{Z})=\prod_{i\in\PlayerSet^\DecPSecond}(\Isom^*\Mixture)_i(\mathcal{Z}_i)\).
Since the sets \(\mathcal{Z}_i\) were arbitrary and the Cartesian products of these sets are a \(\pi\)-system and generate the product \(\sigma\)-Algebra \(\mathcal{F}\), this shows that \(\Isom^*\Mixture\) has independent local policies.

Next, let \(i\in\PlayerSet^\DecPSecond\), \(t\in\{0,\dotsc,\Tmax\}\) and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}^\DecPSecond\). Note that \(\Proj_i(\Isom^*\Policy^\Mixture)=\Policy_{\Isom^{-1}i}^{\Mixture_{\Isom^{-1}i}}\circ\Isom^{-1}\) and
\(
\Proj_i(\Policy^{\Isom^*\Mixture})

Hence, it remains to prove that \(\Policy_{\Isom^{-1}i}^{\Mixture_{\Isom^{-1}i}}\circ \Isom^{-1}=\Policy_i^{(\Isom^*\Mixture)_i}\).

To that end, let \(j\in\PlayerSet^\DecP\) such that \(\Isom j= i\). By Theorem <ref>, it is

\begin{equation}
\label{equation-histories-pullbacks}
\Prob_{\Policy}(\AOHistoryRV_{j,  t} =\Isom^{-1} \AOHistory_{i,t})
\Prob_{\Isom^*\Policy}(\AOHistoryRV_{ i,t}=\AOHistory_{i,t})
\end{equation}

for any \(\Policy\in \PolicySet^\DecP\). Letting, \(\Mixture_{-j}\in\Delta(\PolicySet_{-j}^\DecP)\) with independent local policies arbitrary and defining \(\Mixture:=\Mixture_{i}\otimes\Mixture_{-i}\), this means that also

\begin{multline}
\label{eq:31}
\Prob_\Mixture(\AOHistoryRV_{ j,  t} =\Isom^{-1} \AOHistory_{i,t})
\overset{\text{(ii)}}{=}\E_\Mixture\left[
\Prob_\PolicyLatent(\AOHistoryRV_{ j,  t} = \Isom^{-1}\AOHistory_{i,t})
\right]
\Prob_{\Isom^*\PolicyLatent}(\AOHistoryRV_{ i,  t} = \AOHistory_{i,t})
\right]
\\
\Prob_{\PolicyLatent}(\AOHistoryRV_{i,  t} = \AOHistory_{i,t})
\right]
\overset{\text{(ii)}}{=}\Prob_{\Isom^*\Mixture}(\AOHistoryRV_{ i,  t} = \AOHistory_{i,t}),
\end{multline}

where we use Equation <ref> in (ii).
Since \(\Isom^*\) is a bijection on the space of policies, it is

\[\{\Isom^*(\Mixture_j\otimes\Mixture_{-j})\mid \Mixture_{-j}\in\Delta(\PolicySet_{-j}^\DecP)\}=\{(\Isom^*\Mixture)_i\otimes\MixtureHat_{-i}\mid\MixtureHat_{-i}\in\Delta(\PolicySet_{-i}^\DecPSecond)\}.\]

Hence, (<ref>) implies that there is some \(\Mixture_{-j}\in\Delta(\PolicySet_{-j}^\DecP)\) with independent local policies such that \(\Prob_{\Mixture_j\otimes\Mixture_{-j}}(\AOHistoryRV_{j,  t} =\Isom^{-1} \AOHistory_{i,t})>0\) if and only if there is \(\MixtureHat_{-i}\in\Delta(\PolicySet_{-i}^\DecPSecond)\) with independent local policies such that \(\Prob_{(\Isom^*\Mixture)_i\otimes \MixtureHat_{-i}}(\AOHistoryRV_{i,  t} =\AOHistory_{i,t})>0\).

Using this fact, it suffices to distinguish the two cases where such a distribution does exist and where it does not exist. First, assume that it does not exist. Then by Definition <ref>, both \(\Policy_{j}^{\Mixture_j}(\cdot\mid \Isom^{-1} \AOHistory_{i,t})\) and \(\Policy_i^{(\Isom^*\Mixture)_i}(\cdot\mid\AOHistory_{i,t})\) are uniform distributions. Since \(\Isom^{-1}\) is a bijection on \(\ActionSet_i^\DecPSecond\), also \(\Policy_{j}^{\Mixture_{j}}(\Isom^{-1}\cdot \mid \Isom^{-1}\AOHistory_{i,t})\) is a uniform distribution, and hence

\[\Policy_{j}^{\Mixture_{j}}(\Isom^{-1}\cdot \mid \Isom^{-1}\AOHistory_{i,t})=\Policy_i^{(\Isom^*\Mixture)_i}(\cdot\mid \AOHistory_{i,t}).
\]

Second, consider the case in which a distribution \(\Mixture_{-j}\in\Delta(\PolicySet_{-j}^\DecP)\) with independent local policies exists such that

\[\Prob_{\Mixture_j\otimes\Mixture_{-j}}(\AOHistoryRV_{j,  t} =\Isom^{-1} \AOHistory_{i,t})>0,\]

and define \(\Mixture:=\Mixture_j\otimes\Mixture_{-j}\).

Then for \(\Action_i\in\ActionSet^\DecPSecond_i\), it is

\begin{align}
\label{eq:33a}
\Policy^{\Mixture_j}_{j}(\Isom^{-1} \Action_i\mid \Isom^{-1}\AOHistory_{i,t})
&= \Prob_\Mixture(\ActionRV_{j,t}=\Isom^{-1} \Action_i\mid \AOHistoryRV_{j,t}=\Isom^{-1}\AOHistory_{i,t})
\\
&= \E_\Mixture[\Prob_{\Mixture}(\ActionRV_{j,t}=\Isom^{-1} a_i\mid\AOHistoryRV_{j, t},Z)\mid \AOHistoryRV_{ j,t}=\Isom^{-1}\AOHistory_{i,t}]
\\&= \E_\Mixture[Z_{j}(\Isom^{-1} \Action_i\mid\Isom^{-1}\AOHistory_{i,t})\mid
\AOHistoryRV_{j,t}=\Isom^{-1}\AOHistory_{i,t}]
\\
&=\frac{\int_{\PolicySet^\DecP}\int_{\Omega}(\Isom^*Z)_{i}( \Action_i\mid\AOHistory_{i,t})\mathds{1}_{\AOHistoryRV_{ j,t}={\Isom^{-1}}\AOHistory_{i,t}}\mathrm{d}\Prob_{Z}\mathrm{d}\Mixture
\int_{\PolicySet^\DecP}\int_{\Omega}\mathds{1}_{\AOHistoryRV_{j,t}={\Isom^{-1}}\AOHistory_{i,t}}
\mathrm{d}\Prob_{Z}\mathrm{d}\Mixture
\\
\frac{\int_{\PolicySet^\DecP}(\Isom^*Z)_{ i}( \Action_i\mid\AOHistory_{i,t})\Prob_Z({\AOHistoryRV_{ j,t}={\Isom^{-1}}\AOHistory_{i,t}})\mathrm{d}\Mixture
\int_{\PolicySet^\DecP}\Prob_Z(\AOHistoryRV_{j,t}={\Isom^{-1}}\AOHistory_{i,t})\mathrm{d}\Mixture
\\
\frac{\int_{\PolicySet^\DecP}(\Isom^*Z)_{ i}( \Action_i\mid\AOHistory_{i,t})\Prob_{\Isom^*Z}({\AOHistoryRV_{i,t}=\AOHistory_{i,t}})\mathrm{d}\Mixture
\int_{\PolicySet^\DecP}\Prob_{\Isom^*Z}(\AOHistoryRV_{ i,t}=\AOHistory_{i,t})\mathrm{d}\Mixture
\\
\frac{\int_{\PolicySet^\DecPSecond}Z_{i}( \Action_i\mid\AOHistory_{i,t})\Prob_{Z}({\AOHistoryRV_{i,t}=\AOHistory_{i,t}})\mathrm{d}\Mixture\circ(\Isom^*)^{-1}
\int_{\PolicySet^\DecPSecond}\Prob_{Z}(\AOHistoryRV_{ i,t}=\AOHistory_{i,t})\mathrm{d}\Mixture\circ(\Isom^*)^{-1}
\\
= \E_{\Isom^*\Mixture}[Z_{i}( \Action_i\mid\AOHistory_{i,t})\mid \AOHistoryRV_{ i,t}=\AOHistory_{i,t}]
\\
&= \Prob_{\Isom^*\Mixture}(\ActionRV_{i,t}= \Action_i\mid \AOHistoryRV_{ i,t}=\AOHistory_{i,t})
\\\label{eq:33c}
&=\Policy_i^{(\Isom^*\Mixture)_i}(a_i\mid \AOHistory_{i,t}),
\end{align}

where we have used Definition <ref> in (<ref>) and (<ref>), and Theorem <ref> in (<ref>).
This concludes the second case and thus the proof.

note to myself: I could include a bit more explanation here, e.g. using "Equation <ref> and the tower property" etc. But not super important. low prio

§.§ The other-play distribution and the symmetrizer

Using the idea of a policy corresponding to a distributions over policies introduced above, we can now define a policy corresponding to the distribution over policies used in the OP objective. In the following, fix again a Dec-POMDP \(\DecP\).

Let \(\Policy\in\PolicySet\). We define the OP distribution of \(\Policy\)
as the distribution
\begin{equation}
\label{equation-other-play-mixture}
\Mixture:=|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\delta_{\AutProfile^*\Policy},
\end{equation}

where \(\delta\) is the Dirac measure, i.e., for any measurable set \(\mathcal{Z}\subseteq\PolicySet\), it is

\[\delta_{\AutProfile^*\Policy}(\mathcal{Z})=
\begin{cases}1&\text{if }\AutProfile^*\Policy\in \mathcal{Z}
\\
0&\text{ otherwise.}
\end{cases}
\]

Intuitively, agent \(i\) chooses one of the automorphisms \(\AutProfile_i\in\Aut(\DecP)\)
uniformly at random in the beginning of an episode and then follows the local policy \(\Proj_i(\AutProfile_i^*\Policy)\).
It can easily be shown that this distribution has independent local policies.

Let \(\Policy\in\PolicySet\) and let \(\Mixture\) be the OP distribution of \(\Policy\). Then \(\Mixture\) has independent local policies.

Let \(\mathcal{Z}_i\subseteq\PolicySet_i\) measurable for \(i\in\PlayerSet\) and let \(\mathcal{Z}:=\prod_{i\in\PlayerSet}\mathcal{Z}_i\). Note that for any \(i\in\PlayerSet\) and \(\AutProfile\in\Aut(\DecP)^\PlayerSet\), it is

\begin{equation}\label{eq:300}
\delta_{\AutProfile^*\Policy}(\Proj_i^{-1}(\mathcal{Z}_i))=\prod_{j\in\PlayerSet\setminus\{i\}}\delta_{\Proj_j(\AutProfile^*_j\Policy)}(\PolicySet_j)\delta_{\Proj_i(\AutProfile^*_i\Policy)}(\mathcal{Z}_i)=\delta_{\Proj_i(\AutProfile^*_i\Policy)}(\mathcal{Z}_i).\end{equation}

Hence, it follows that

\begin{multline}
\Mixture(\mathcal{Z})
\\
\\
\overset{(\ref{eq:300})}{=}
\prod_{i\in\PlayerSet}|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\delta_{\AutProfile^*\Policy}(\Proj_i^{-1}(\mathcal{Z}_i))

This shows that \(\Mixture=\otimes_{i\in\PlayerSet}\Mixture_i\).

Using the OP distribution of a policy, we can define the symmetrizer \(\Psi^\DecP\) for \(\DecP\), which maps a policy \(\Policy\) to a policy \(\Psi^\DecP(\Policy)\) that corresponds to the OP distribution of \(\Policy\). If it is clear which Dec-POMDP is considered, we also write \(\Psi(\Policy)\).

We define the symmetrizer for the Dec-POMDP \(\DecP\) as the map \(\Psi^\DecP\colon\PolicySet^\DecP\rightarrow\PolicySet^\DecP\) such that for any policy \(\Policy\in\PolicySet\) and OP distribution
\(\Mixture\) of \(\Policy\), it is

\[\Psi^\DecP(\Policy):=\Policy^\Mixture.\]

It is clear that if a policy is already invariant to automorphism, then \(\Policy_i=\Psi_i(\Policy)\) for \(i\in\PlayerSet\), excluding action-observation histories that can never be reached under \(\Policy_i\). We formulate a slightly weaker proposition below, which is easier to prove.

Let \(\Policy\in\PolicySet\) be invariant to automorphism, and assume that, for all \(t\in\{0,\dotsc,\Tmax\}\) and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\), it is \(\Prob_\Policy(\AOHistoryRV_{i,t}=\AOHistory_{i,t})>0\). Then it is \(\Psi(\Policy)=\Policy\).

Let \(\Mixture\) be the OP distribution of \(\Policy\). Since \(\Policy\) is invariant to automorphism, it is

\[\Mixture=|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\delta_{\AutProfile^*\Policy}=\delta_{\Policy}.\]

Now let \(i\in\PlayerSet\), \(t\in\{0,\dotsc,\Tmax\}\), \(\Action_i\in\ActionSet_i\) and \(\AOHistory_{i,t}\in\AOHistorySet_{i,t}\) arbitrary.
Using Equation <ref>, it follows that

\[\Prob_{\delta_\Policy}(\AOHistoryRV_{i,t}=\AOHistory_{i,t})
\overset{(\ref{eq:equation-tower-prop-z})}{=}
\E_{\delta_\Policy}\left[\Prob_Z(\AOHistoryRV_{i,t}=\AOHistory_{i,t})\right]

\begin{multline}
\label{eq:40}
\Prob_{\delta_\Policy}(\ActionRV_{i,t}=\Action_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})
\overset{(\ref{eq:equation-tower-prop-z})}{=}
\E_{\delta_\Policy}\left[
\Prob_Z(\ActionRV_{i,t}=\Action_i\mid\AOHistoryRV_{i,t})\mid \AOHistoryRV_{i,t}=\AOHistory_{i,t}
\right]
\\
\end{multline}

Hence, we can apply Definition <ref> and conclude that

\begin{multline}\Psi_i(\Policy)(\Action_i\mid\AOHistory_{i,t})=\Policy^{\Mixture_i}_i(\Action_i\mid\AOHistory_{i,t})
\overset{\text{Definition~\ref{policy-mixture}}}{=}\Prob_{\delta_\Policy}(\ActionRV_{i,t}=\Action_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})
\\\overset{(\ref{eq:40})}{=}\Prob_{\Policy}(\ActionRV_{i,t}=\Action_i\mid\AOHistoryRV_{i,t}=\AOHistory_{i,t})=\Policy_i(\Action_i\mid\AOHistory_{i,t}).\end{multline}

It will be helpful to refer to policies as equivalent if they have the same image under \(\Psi\).

Let \(\Policy,\Policy'\in\PolicySet^\DecP\). We say that \(\Policy\) and \(\Policy'\) are equivalent, denoted as \(\Policy\equiv_\DecP\Policy\), if \(\Psi^\DecP(\Policy)=\Psi^\DecP(\Policy')\). Moreover, we write \([\Policy]:=\{\Policy'\mid \Policy'\equiv_D\Policy\}\) for the equivalence class of \(\Policy\).

It is clear that \(\equiv_\DecP\) is an equivalence relation, since it is induced by the function \(\Psi^\DecP\). It follows that under \(\equiv_\DecP\), \(\PolicySet^\DecP\) decomposes into a partition of equivalence classes, denoted by \(\faktor{\PolicySet^\DecP}{\equiv_\DecP}\).

Applying Lemma <ref> to the symmetrizer in particular, we can show that it commutes with isomorphisms, and that the policy \(\Psi(\Policy)\) is invariant to automorphism.

Let \(\Isom\in\Iso(\DecP,\DecPSecond)\) and \(\Policy\in\PolicySet^\DecP\). Then it is

\[\Isom^*\Psi^\DecP(\Policy)=\Psi^{\DecPSecond}(\Isom^*\Policy).\]

If \(\DecPSecond=\DecP\), then

\[\Isom^*\Psi^\DecP(\Policy)=\Psi^{\DecP}(\Policy),\]

i.e., \(\Psi^\DecP(\Policy)\) is invariant to automorphism.

Let \(\Mixture\) be the other-play distribution of \(\Policy\) and \(\MixtureHat\) the other-play distribution corresponding to \(\Isom^*\Policy\).
Then, using the associativity of function composition and pushforward proven in Lemma <ref>, and using the “in particular” part of Lemma <ref>, it follows that

\begin{multline}\label{equation-image-measure-pull-back}
\MixtureHat
\\
\overset{\text{Lemma~\ref{decompose-isomorphisms}}}{=}
\\
|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\delta_{\AutProfile^*\Policy}\circ (\Isom^*)^{-1}
=\Mixture\circ (\Isom^*)^{-1}.
\end{multline}

Thus, using Lemma <ref>, it is
\begin{equation}\label{equation-psi-isom-commute}
\Isom^*\Psi^\DecP(\Policy)
\overset{\text{Lemma~\ref{lemma-isomorphism-mixture-commute}}}{=}
\Policy^{\Isom^*\Mixture}
\overset{(\ref{equation-image-measure-pull-back})}{=}
\Policy^{\MixtureHat}
\end{equation}

Finally, assume \(\DecPSecond=\DecP\). Then \(\Isom\) is an automorphism and \(\Aut(\DecPSecond)=\Aut(\DecP)=\Aut(\DecP)\circ\Isom\) by Lemma <ref>. Hence,

\begin{multline}\label{equation-image-measure-pull-back-auto}
\Mixture\circ (\Isom^*)^{-1}
|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\delta_{\AutProfile^*\Policy}\circ (\Isom^*)^{-1}
\\
\\
\overset{\text{Lemma~\ref{decompose-isomorphisms}}}{=}
\end{multline}

By (<ref>), it follows that

\[\Isom^*\Psi^\DecP(\Policy)
\overset{(\ref{equation-psi-isom-commute})}{=}
\Policy^{\Mixture\circ(\Isom^*)^{-1}}
\overset{(\ref{equation-image-measure-pull-back-auto})}{=}
\Policy^\Mixture=\Psi^\DecP(\Policy),
\]

which concludes the proof.

A direct corollary is that we can define the pushforward purely in terms of equivalence classes of policies. This will also be useful later.

Let \(\DecP,\DecPSecond\) be isomorphic Dec-POMDPs with \(\Isom\in\Iso(\DecP,\DecPSecond)\). Let \([\Policy]\in\faktor{\PolicySet^\DecP}{\equiv_\DecP}\). We define the pushforward equivalence class \(\Isom^*[\Policy]\in\faktor{\PolicySet_{\DecPSecond}}{\equiv_{\DecPSecond}}\) via

\[f^*[\Policy]:=[f^*\Policy].\]

The following corollary show that this is well-defined, that the pushforward of an equivalence class does not depend on the particular chosen isomorphism, and that it is compatible with function composition.

(i) The pushforward of an equivalence class is well-defined, i.e., for any \(\Policy,\Policy'\in\PolicySet^\DecP\) such that \(\Policy\equiv_\DecP\Policy'\), it is \([\Isom^*\Policy]=[\Isom^*\Policy']\).

(ii)Any two isomorphisms \(\Isom,\Isom'\in\Iso(\DecP,\DecPSecond)\) induce the same pushforward.

(iii)Analogous results to those in Lemma <ref> apply to the pushforward of equivalence classes.

First, let \(\Policy\equiv_\DecP\Policy'\in\PolicySet^\DecP\) and \(\Isom\in\Iso(\DecP,\DecPSecond)\) arbitrary. Then, using Corollary <ref> and the definition of \(\equiv_\DecP\), it is

\[\Psi^{\DecPSecond}(\Isom^*\Policy)=\Isom^*\Psi^\DecP(\Policy)=\Isom^*\Psi^\DecP(\Policy')=\Psi^{\DecPSecond}(\Isom^*\Policy').\]

Thus, \([\Isom^*\Policy]=[\Isom^*\Policy']\), which proves the first part.

Second, let \(\Isom,\IsomSecond\in \Iso(\DecP,\DecPSecond)\) and \(\Policy\in\PolicySet^\DecP\) arbitrary. By Lemma <ref>, there then exists \(\Auto\in\Aut(\DecPSecond)\) such that \(\IsomSecond=\Auto\circ\Isom\). Hence, using the second and first part of Corollary <ref> and Lemma <ref>, it is

\begin{equation}
\label{eq:340}\Psi^{\DecPSecond}(\Isom^*\Policy)
\overset{\text{Corollary~\ref{corollary-psi-isom-commute}}}{=}
\Auto^*\Psi^{\DecPSecond}(\Isom^*\Policy)
\overset{\text{Corollary~\ref{corollary-psi-isom-commute}}}{=}
\Psi^{\DecPSecond}(\Auto^*(\Isom^*\Policy))
\overset{\text{Lemma~\ref{lemma-pull-back-function-composition-compatible}}}{=}
\Psi^{\DecPSecond}((\Auto\circ\Isom)^*\Policy)

Finally, it follows that

\[\Isom^*[\Policy]=[\Isom^*\Policy]\overset{\ref{eq:340}}{=}[\IsomSecond^*\Policy]=\IsomSecond^*[\Policy],
\]

which concludes the second part.

The third part follows directly from Lemma <ref> by using the definition of the pushforward of equivalence classes.

In the following, we say that two equivalence classes \([\Policy],[\Policy']\) for \(\Policy\in\PolicySet^\DecP,\Policy'\in\PolicySet^\DecPSecond\) correspond to each other if there exists an isomorphism \(\Isom\in\Iso(\DecP,\DecPSecond)\) such that \(\Isom^*[\Policy]=[\Policy']\). In that case, in a slight abuse of the terms, we also say that \(\Policy\) and \(\Policy'\) are equivalent, extending the equivalence between policies defined above to policies for different Dec-POMDPs. Using Corollary <ref>, one can see that two policies \(\Policy,\Policy'\in\PolicySet^\DecP\) are equivalent in the sense that \([\Policy]=[\Policy']\) if and only if there exists an isomorphism \(\Isom\in\Iso(\DecP,\DecP)\) such that \(\Isom^*[\Policy]=[\Policy']\), so this extended notion is equivalent to the old one for two policies  \(\Policy,\Policy'\in\PolicySet^\DecP\). We continue to reserve the notation \([\Policy]\) and \(\equiv\) for policies from the same Dec-POMDP.

§.§ Main characterizations

Having defined the symmetrizer \(\Psi\), we can now characterize the OP objective as transforming a policy \(\Policy\) into an invariant policy \(\Psi(\Policy)\) and evaluating the expected return of that policy.
This means that we can “pass to the quotient” and consider the OP objective as a map \(\tilde{J}_\OP\) of equivalence classes, \(\tilde{J}_\OP([\Policy]):=J_\OP(\Policy)\) for \([\Policy]\in\faktor{\PolicySet}{\equiv}\), using the equivalence relation on policies introduced above. The result is essentially a rigorous version of hu2020other's Proposition 1 in our setup. It will help us later to analyze the OP-optimal policies in a given example, as it implies that we can restrict ourselves to considering representatives \(\Psi(\Policy)\) of equivalence classes.

Let \(\DecP\) be a Dec-POMDP, let \(\Policy\in\PolicySet^\DecP\), and let \(\Psi\) be the symmetrizer for \(\DecP\). Then \(\Psi(\Policy)\) is invariant to automorphism, and it is

\begin{equation}\label{eq:350}
\end{equation}

In particular, we can consider the OP objective as a function of equivalence classes \([\Policy]\in\faktor{\PolicySet^\DecP}{\equiv_\DecP}\), and if there exists an optimal policy for the OP objective, then there also exists an optimal policy that is invariant to automorphism.

In the following, fix a Dec-POMDP \(\DecP\).
Let \(\Policy\in\PolicySet\) and let \(\Mixture\) be the OP distribution of \(\Policy\), such that \(\Psi(\Policy)=\Policy^\Mixture\). Then by the second part of Corollary <ref>, \(\Psi(\Policy)\) is invariant to automorphism.

Moreover, using Proposition <ref>, it is

\begin{multline}\label{eq:34}
J_\OP(\Policy)=\E_{\AutProfile\sim \U(\Aut(\DecP)^\PlayerSet)}\left[J(\AutProfile^*\Policy)
\right]
\\=
\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}|\Aut(\DecP)|^{-N}\int_{\Policy'\in\PolicySet}J(\Policy')
\mathrm{d}\left(\delta_{\AutProfile^*\Policy}\right)
\\
\int_{\Policy'\in\PolicySet}J(\Policy')\mathrm{d}\left(\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}|\Aut(\DecP)|^{-N}\delta_{\AutProfile^*\Policy}\right)
\\
\overset{(\ref{equation-other-play-mixture})}{=}
\int_{\Policy'\in\PolicySet}J(\Policy')\mathrm{d}\Mixture
\overset{(\ref{expected-return-mixture})}{=}J(
\Mixture)
\overset{\text{Proposition~\ref{mixture-lemma}}}{=}
\end{multline}

which proves Equation <ref>.

Turning to the “in particular” statement, let \(\Policy'\equiv\Policy\) for a second policy \(\Policy'\in\PolicySet\).
By Definition <ref>, this means that \(\Psi(\Policy')=\Psi(\Policy)\).
Hence, by Equation <ref>, it follows that \(J_\OP(\Policy)=J_\OP(\Policy')\), which shows that the function \(\tilde{J}_{\OP}\colon\faktor{\PolicySet}{\equiv}\rightarrow\mathbb{R},[\Policy]\mapsto J_\OP(\Policy)\) is well-defined.

Lastly, assume that there is \(\Policy\in\argmax_{\Policy'\in\PolicySet}J_\OP(\Policy')\) (see Remark <ref> regarding the existence of such a policy). Then by Equation <ref>, it is also \(\Psi(\Policy)\in\argmax_{\Policy'\in\PolicySet}J_\OP(\Policy')\), so \(\Psi(\Policy)\) is an OP-optimal policy that is invariant to automorphism.

As a corollary, we can show that isomorphisms do not affect the OP value of a policy (we already know this about SP from Corollary <ref>). In the following, we define \(\PolicySet_\OP^\DecP:=\argmax_{\Policy\in\PolicySet^\DecP}J^\DecP_\OP(\Policy)\) for a Dec-POMDP \(\DecP\).

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

\[J_\OP^{\DecP}(\Policy)=J_\OP^\DecPSecond(\Isom^*\Policy).\]

In particular, if \(\Policy\in\PolicySet_\OP^\DecP\), then also \(\Isom^*\Policy\in\PolicySet_\OP^{\DecPSecond}\).

Using Theorem <ref>, Corollary <ref>, and Corollary <ref>, it is

\begin{multline}\label{eq:35}
\overset{\text{Theorem~\ref{thm-op-mixture}}}{=}
\overset{\text{Corollary~\ref{corollary-psi-isom-commute}}}{=}
\\
\overset{\text{Corollary~\ref{cor-sp-invariant-to-pullback}}}{=}
\overset{\text{Theorem~\ref{thm-op-mixture}}}{=}
\end{multline}

Turning to the “in particular” statement, assume that \(\Policy\in\PolicySet^\DecP_\OP\). By Lemma <ref>, it is \(\Isom^{-1}\in\Iso(\DecPSecond,\DecP)\). Hence, for any \(\PolicyTilde\in\PolicySet^{\DecPSecond}\), it follows from the preceding that

\begin{equation}
\leq J^{\DecP}_\OP(\Policy)=J^{\DecPSecond}_\OP(\Isom^*\Policy).
\end{equation}

This shows that \(\Isom^*\Policy\in \PolicySet^{\DecPSecond}_\OP\).

Finally, we turn to the connection between OP and the payoff in an LFC game.
The following result will be helpful in both showing the inadequacy of OP and in proving that OP with tie-breaking is optimal. It shows that equivalent policies in \([\Policy]\in\faktor{\PolicySet}{\equiv}\) are all compatible when played against each other by different principals in the LFC game. The proof is based on Lemma <ref> and Proposition <ref>.

Let \(\DecP\) be a Dec-POMDP, let \(\Psi\) be the symmetrizer for \(\DecP\), and define \(\DecPSet:=\{\Isom^*\DecP\mid \Isom\in\Sym(\DecP)\}\).
Let \(\LAProfile_1,\dotsc,\LAProfile_N\in\LASet^\DecPSet\).
For any \(\DecPSecond\in\DecPSet\), choose \(\Isom_{\DecP,\DecPSecond}\in\Iso(\DecP,\DecPSecond)\) arbitrarily. Then it is

\begin{equation}
U^\DecP(\LAProfile)=\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
J^\DecP \left(\left(\Psi_k(\Policy^{(k)})\right)_{k\in\PlayerSet}\right)
\right]
\right].
\end{equation}

First, consider arbitrary joint policies \(\Policy^{(1)},\dots,\Policy^{(N)}\in\PolicySet^\DecP\) and let \(\Mixture^{(i)}\) be the OP distribution of \(\Policy^{(i)}\), so that \(\Policy^{\Mixture^{(i)}}=\Psi(\Policy^{(i)})\) for \(i\in\PlayerSet\). Define the distribution

\begin{equation}\label{eq:37}
\MixtureHat(\Policy^{(1)},\dotsc,\Policy^{(N)}):=|\Aut(\DecP)|^{-N}\sum_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\otimes_{i\in\PlayerSet}\delta_{\Proj_i(\AutProfile_i^*\Policy^{(i)})}
\end{equation}

as a function of \(\Policy^{(1)},\dotsc,\Policy^{(N)}\).
It can easily be seen that \(\MixtureHat_(\Policy^{(1)},\dotsc,\Policy^{(N)})\in \Delta(\PolicySet^\DecP)\) and that it has independent local policies. Moreover, \(\MixtureHat(\Policy^{(1)},\dotsc,\Policy^{(N)})_i=\Mixture^{(i)}_i\), i.e., the marginal distribution for agent \(i\in\PlayerSet\) is equal in \(\MixtureHat(\Policy^{(1)},\dotsc,\Policy^{(N)})\) and \(\Mixture^{(i)}\). Hence, also the corresponding local policies are identical, that is,

\begin{equation}\label{equation-mixture-hat-equal-psi}
\Policy_i^{\MixtureHat(\Policy^{(1)},\dotsc,\Policy^{(N)})_i}
\end{equation}

for \(i\in\PlayerSet\).

It follows that

\begin{align}\label{eq:36}
\\\label{eq:38a}
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
\E_{\AutProfile\in\Aut(\DecP)^\PlayerSet}\left[
\\
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\Bigg[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\Bigg[
\\&\quad\quad
\int_{\Policy\in\PolicySet^\DecP}
\right)\Bigg]\Bigg]
\\
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\Bigg[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\Bigg[
\\&\quad\quad\int_{\Policy\in\PolicySet^\DecP}
\right)\Bigg]\Bigg]
\\
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[\int_{\Policy\in\PolicySet^\DecP}
\\
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
\\\label{eq:38b}
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
\\
\E_{\DecP_i\sim U(\DecPSet),\,i\in\PlayerSet}\left[
\E_{\Policy^{(j)}\sim\Isom_{\DecP_j,\DecP}^*\LAProfile_j(\DecP_j),\,j\in\mathcal{N}}
\left[
\end{align}

where we have used
Lemma <ref> in (<ref>) and Proposition <ref> in (<ref>).
This concludes the proof.
note to self: I could change the way I explain this equation a bit, maybe add lemma etc to the equation signs. not super important

Based on this result, the LFC game for \(\DecP\) can be understood in the following way. Principal \(i\in\PlayerSet\) observes a randomly relabeled problem \(\DecP_i\in\DecPSet\) and trains a joint policy  \(\Policy^{(i)}\sim\LAProfile_i(\DecP_i)\) on this problem. The resulting policy \(\Policy^{(i)}\) is then translated back into a policy \(\Isom_{\DecP_i,\DecP}^*\Policy^{(i)}\) for the original problem, using any isomorphism \(\Isom_{\DecP_i,\DecP}\in\Iso(\DecP_i,\DecP)\). Finally, this joint policy is made invariant to automorphism by applying the symmetrizer, and agent \(i\) in the original problem \(\DecP\) is assigned the local policy \(\Psi_i(\Isom_{\DecP_i,\DecP}^*\Policy^{(i)})\).

§.§ Other-play is not self-play in a different Dec-POMDP

hu2020other show that the OP objective \(\tilde{J}^\DecP_\OP\) introduced by them can be understood of as the SP objective in a special Dec-POMDP. That is, for every Dec-POMDP \(\DecP\), there is a second Dec-POMDP \(\DecPSecond\) with \(\PolicySet^\DecPSecond=\PolicySet^\DecP\) such that for any \(\Policy\in\PolicySet^\DecP\), it is \(\tilde{J}^\DecP_\OP(\Policy)=\max_{\Policy'\in\PolicySet^\DecP}\tilde{J}^\DecP_\OP(\Policy')\) if and only if \(J^\DecPSecond(\Policy)=\max_{\Policy'\in\PolicySet^\DecPSecond}J^\DecPSecond(\Policy')\).
Interestingly, when including player permutations, this is not the case anymore. We will prove this here, using the characterization of OP from the last section.

Intuitively, if agents are symmetric, then under OP, they will always act according to the same local policy in the environment. In some Dec-POMDPs, this means that it is optimal for the agents to randomize their actions, to end up with different actions some of the time. For instance, consider the following game:

There are two players with two actions \(\ActionSet_i:=\{\Action_{i,1},\Action_{i,2}\}\) for \(i=1,2\) each, and an episode lasts only one step, making this a simple normal-form game. Rewards for each joint action are displayed in Table <ref>.

Rewards for each joint action in Example <ref>.

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

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

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

This example demonstrates that sometimes there does not exist a deterministic policy that is optimal under the OP objective.

In Example <ref>, for any deterministic policy \(\Policy\), it is \(J_\OP(\Policy)<\max_{\Policy'\in\PolicySet^\DecP}J_\OP(\Policy')\).

Let \(R\in\mathbb{R}^{2,2}\) denote a matrix containing rewards as in Table <ref>.

First, note that in this game, players are symmetric, but actions are not. Moreover, there are no observations and only one state. Hence, \(\Aut(\DecP)=\{\Auto,\Id\}\) where \(\Auto_N1=2,\Auto_N2=1\) and \(\Id\) is the identity.

Now consider any deterministic policy \(\Policy=(\Policy_1,\Policy_2)\), corresponding to two vectors of action-probabilities

\[x,y\in \left\{\begin{bmatrix}1\\0\end{bmatrix},\begin{bmatrix}0\\1\end{bmatrix}\right\}\]

for the two players. Due to the symmetry of both players, the OP distribution \(\Mixture\) of \(\Policy\) assigns each policy \(\Policy_1,\Policy_2\) to either player with probability \(\frac{1}{2}\), so in \(\Psi(\Policy)=\Policy^\Mixture\), both players play the distribution \(z:=\frac{1}{2}x + \frac{1}{2}y\) and receive a reward of

\[J^\OP(\Policy)\overset{\text{Theorem~\ref{thm-op-mixture}}}{=}J(\Psi(\Policy))=z^\top R z.\]

It follows by the definition of \(x,y\) that

\[z\in \left\{\begin{bmatrix}1\\0\end{bmatrix},\begin{bmatrix}0\\1\end{bmatrix},\begin{bmatrix}\frac{1}{2}\\\frac{1}{2}\end{bmatrix}\right\}.\]

Clearly, then \(z^\top Rz\) is maximized at \(z=[\frac{1}{2},\frac{1}{2}]^\top\), yielding a reward of

\begin{equation}\label{eq:510}
J^\OP(\Policy)=z^\top R z=\frac{1}{8}.
\end{equation}

Next, define \(x=[\frac{4}{7},\frac{3}{7}]^\top\) and let \(\Policy^*\) be a policy such that \(\Policy^*_1=\Policy^*_2\) and the two action-probabilities of both local policies are given by the vector \(x\). Note that since \(\Auto^*\Policy^*=(\Policy^*_{\Auto i})_{i=1,2}=\Policy^*\), it follows from the above that \(\Policy^*\) is invariant to automorphism.

It follows by Proposition <ref> that we can evaluate the OP value of \(\Policy^*\) by evaluating its expected return. That is,

\begin{equation}J^\OP(\Policy^*)\overset{\text{Proposition~\ref{prop-invariant-policy-self-play-value-equals-other-play-value}}}{=}J(\Policy^*)=x^\top R  x=-\frac{1}{2}\left(\frac{4}{7}\right)^2+2\frac{4}{7}\frac{3}{7} -1\left(\frac{3}{7}\right)^2=\frac{1}{7}.\end{equation}

It follows that

\begin{equation}
J_\OP(\Policy)\overset{(\ref{eq:510})}{=}\frac{1}{8}<\frac{1}{7}=J^\OP(\Policy^*)\leq \max_{\Policy'\in\PolicySet^\DecP}J_\OP(\Policy'),
\end{equation}

which concludes the proof.

The fact that there is no deterministic optimal policy in Example <ref> is in conflict with a canonical result about Dec-POMDPs.

In every Dec-POMDP \(\DecP\), there is a deterministic policy \(\Policy\in(\PolicySet^0)^\DecP\) such that \(J^\DecP(\Policy)=\max_{\Policy'\in\PolicySet^\DecP}J^\DecP(\Policy')\).

As a result, we can prove the following.

There exists a Dec-POMDP \(\DecP\) such that for any other Dec-POMDP \(\DecPSecond\) with \(\PolicySet^\DecPSecond=\PolicySet^\DecP\), there exists a policy \(\Policy\in\PolicySet^\DecPSecond\) that is optimal for the SP objective of \(\DecPSecond\), but not optimal for the OP objective of \(\DecP\).

Let \(\DecP\) be the Dec-POMDP as described in Example <ref>. Assume, towards a contradiction, that there exists a Dec-POMDP \(\DecPSecond\) with \(\PolicySet^\DecPSecond=\PolicySet^\DecP\) such that any optimal policy in that Dec-POMDP is optimal under the OP objective of \(\DecP\). Then by Theorem <ref>, there exists a deterministic policy \(\Policy\in(\PolicySet^0)^\DecPSecond\) such that \(J^\DecPSecond(\Policy)\) is maximal. Hence, by the assumption, also \(J^\DecP_\OP(\Policy)\) is maximized. But by Lemma <ref>, it must be \(\max_{\PolicyTilde\in\PolicySet^\DecP}J^\DecP_\OP(\PolicyTilde)>J^\DecP_\OP(\Policy)\). This is a contradiction, which means that \(\DecP\) is an example of a Dec-POMDP that has the desired properties.

This shows that to optimize the OP objective, we have to directly consider that objective and we cannot simply apply an RL algorithm to a different Dec-POMDP. Also, the fact that we need stochastic policies means that it is not immediately clear how to apply a Bellman equation to the objective.

§ OTHER-PLAY IS NOT OPTIMAL IN THE LABEL-FREE COORDINATION PROBLEM

In this section, our goal is to prove a rigorous version of Theorem <ref> from the main text.

Recall that in Appendix <ref>, we introduced the symmetrizer \(\Psi\colon\PolicySet\rightarrow\PolicySet\), which maps a joint policy \(\Policy\) to the policy corresponding to agents following randomly permuted local policies \((\AutProfile_i^*\Policy)_i\) where \(\AutProfile_i\sim\U(\Aut(\DecP))\). This represents the random permutations employed in the OP objective, and hence by Theorem <ref>, it is \(J_\OP(\Policy)=J(\Psi(\Policy))\), i.e., the OP value of \(\Policy\) is equal to the SP value of \(\Psi(\Policy)\). Moreover, we defined the equivalence classes \([\Policy]=\Psi^{-1}(\{\Psi(\Policy)\})\) of policies that get mapped to the same policy under \(\Psi\).

As defined in Appendix <ref>, an OP learning algorithm is any learning algorithm such that the policies that it learns achieve optimal OP value in expectation. In particular, it can be a learning algorithm that learns different policies in different training runs, as long as it chooses OP-optimal policies with probability \(1\).
As we have seen in Theorem <ref>, in an LFC game, it does not matter which policy from an equivalence class \([\Policy]\) is chosen. Unfortunately, though, there can also be different OP-optimal policies that are not equivalent. In this case, if an OP learning algorithm is not concentrated on only compatible policies, it is not optimal in the corresponding LFC problem.