DDP

    Differential Dynamic Programming
iLQR

    iterative Linear Quadratic Regulator
IBR

    Iterative Best Response
MMELQGames

    Multimodal Maximum Entropy Linear Quadratic GAMES
MELQGames

    Maximum Entropy Linear Quadratic GAMES
GNEP

    Generalized Nash Equilibrium Problem
GNE

    Generalized Nash Equilibrium
POMDP

    Partially Observable Markov Decision Process
MaxEnt

    Maximum Entropy
MCMC

    Markov chain Monte Carlo
VI

    Variational Inference
LICQ

    Linear Independent Constraint Qualification
SOSC

    Second-order Sufficient Optimality Condition

# Multimodal Maximum Entropy Dynamic Games

Oswin So1, Kyle Stachowicz and Evangelos A. Theodorou Toyota Research
Institute provided funds to support this work. Autonomous Control and Decision
Systems Lab
Georgia Institute of Technology, Atlanta, Georgia
1Correspondence to<EMAIL_ADDRESS>
###### Abstract

Environments with multi-agent interactions often result a rich set of
modalities of behavior between agents due to the inherent suboptimality of
decision making processes when agents settle for satisfactory decisions.
However, existing algorithms for solving these dynamic games are strictly
unimodal and fail to capture the intricate multimodal behaviors of the agents.
In this paper, we propose MMELQGames (Multimodal Maximum-Entropy Linear
Quadratic Games), a novel constrained multimodal maximum entropy formulation
of the Differential Dynamic Programming algorithm for solving generalized Nash
equilibria. By formulating the problem as a certain dynamic game with
incomplete and asymmetric information where agents are uncertain about the
cost and dynamics of the game itself, the proposed method is able to reason
about multiple local generalized Nash equilibria, enforce constraints with the
Augmented Lagrangian framework and also perform Bayesian inference on the
latent mode from past observations. We assess the efficacy of the proposed
algorithm on two illustrative examples: multi-agent collision avoidance and
autonomous racing. In particular, we show that only MMELQGames is able to
effectively block a rear vehicle when given a speed disadvantage and the rear
vehicle can overtake from multiple positions.

##  I Introduction

Planning in multi-agent scenarios is a challenging task – actions taken by any
robot cannot be considered in isolation and must take the response from other
agents into account. Classical approaches to tackling this problem adopt a
predict-then-plan architecture, where the actions of other agents are assumed
to be independent of the ego-agent’s actions. However, this assumption breaks
down in the context of multi-agent games such as racing, surveillance or
autonomous driving where agents may have conflicting interests and it is
advantageous to manipulate the behavior of other agents.

Recent works have introduced game-theoretic formulations to address this
problem [4, 12, 16, 20, 28, 32, 33]. By assuming that agents act rationally,
the optimal actions of other agents can be predicted by solving for the Nash
equilibria of the non-cooperative game assuming that the true objectives of
other agents are known. However, in practice humans face cognitive limitations
and seek decisions that are satisfactory but often suboptimal, a phenomenon
described by the concept of “bounded rationality” [29].

This disconnect is often modeled using the the Maximum Entropy (MaxEnt)
framework which models actions of agents as being stochastic in nature. MaxEnt
has been successfully applied to diverse areas including inverse reinforcement
learning [20, 37], forecasting [9], and biology [6]. In particular, Mehr et
al. [20] propose a game-theoretic maximum entropy algorithm for finding nash
equilibria policies to dynamic games via an extension of the iLQGames method
[12].

Overtake Above

Overtake Below

Figure 1:  Two-agent autonomous racing scenario where the rear agent (green)
has a higher maximum velocity than the lead agent (blue). Different
highlighted colors representing different planned modes. The planned
trajectory for the ego agent is shown as a thin blue line. The lead agent is
able to reason about and correctly infer the different modes that the rear
agent could take. Furthermore, when the ego agent is uncertain about which
mode the rear agent will choose, it hedges against both possibilities by
planning a path down the middle.

However, these methods consider only a single local minimum. As a result, the
resulting policies are unimodal and fail to capture the multimodal nature of
solutions under the MaxEnt framework. In the presence of multiple local
minima, the true maximum-entropy policy will be multimodal, with one mode
corresponding to each local minimum. However, computing expectations over
multimodal policies in multi-agent settings quickly leads to combinatorial
explosion and is computationally intractable when solving for multimodal Nash
equilibria.

By considering a novel MaxEnt dynamic game with incomplete information and
information asymmetry, we convert the previous challenge into that of solving
a POMDP for the ego agent where the discrete latent variable corresponds to
different local generalized MaxEnt Nash equilibria found by running a
constrained version of Maximum Entropy Linear Quadratic GAMES (MELQGames) in
parallel. This approach further allows for Bayesian inference over the
discrete latet variable by considering past observations of controls from non-
ego agents.

The main contributions of our work are threefold:

  * •

We propose the constrained MaxEnt dynamic game setting to handle bounded
rationality in decison making under inequality constraints and extend
MELQGames to solve generalized Nash equilibrium.

  * •

We consider a novel MaxEnt dynamic game with incomplete and asymmetric
information. We provide a a computationally efficient solution that allows for
Bayesian inference of the latent mode when the underlying control policies are
multimodal in nature.

  * •

We showcase the benefits of the proposed algorithm in simulation, including an
autonomous racing example. The results demonstrate the superiority of
Multimodal Maximum Entropy Linear Quadratic GAMES (MMELQGames) against other
game theoretic formulations in terms of successfully predicting agents
behavior in dynamic settings.

##  II Problem Setup

In this section, we introduce the constrained MaxEnt dynamic game and the
corresponding Generalized Nash Equilibrium Problem (GNEP).

###  II-A Discrete Dynamic Games and Generalized Nash Equilibria

We consider a discrete dynamic game with $N$ players with joint controls
${\bm{u}}_{t}=[u_{t}^{1},\dots,u_{t}^{N}]=[u^{i}_{t},{{\bm{u}}}^{\neg
i}_{t}]\in\mathbb{R}^{n_{\bm{u}}}$, where $u^{i}_{t}$ denotes the control
input of player $i$ and we use ${{\bm{u}}}^{\neg i}_{t}$ to denote the
controls excluding the $i$th agent. We denote
${\bm{x}}_{t}\in\mathbb{R}^{n_{\bm{x}}}$ the joint state of the system at
timestep $t$ which evolves under the discrete-time dynamics

${\bm{x}}_{t+1}=f({\bm{x}}_{t},u^{1}_{t},\dots,u^{N}_{t})=f({\bm{x}}_{t},{\bm{u}}_{t}).$
(1)

Each agent’s objective is to minimize a corresponding cost function $J^{i}$ in
finite-horizon $T$ with running cost $l^{i}$ and terminal cost $\Phi^{i}$,
where ${\bf U}=[{\bm{u}}_{1},\dots,{\bm{u}}_{T-1}]$ denotes a trajectory

$J^{i}({\bf
U})=\Phi^{i}({\bm{x}}_{T})+\sum_{t=1}^{T-1}l^{i}({\bm{x}}_{t},{\bm{u}}_{t}).$
(2)

The goal of agent $i$ is to choose controls $U^{i}$ that optimize $J^{i}$
while respecting inequality constraints $h^{i}$:

$\displaystyle\min_{u^{i}}\quad J^{i}({\bf U}),\qquad\textrm{s.t.}\quad
h^{i}({\bf U})\leq 0.$ (3)

Note that both the objective function and the constraints are a function of
$U^{i}$ and ${{\bf U}}^{\neg i}$. Due to the presence of constraints $h^{i}$
which may couple agent $i$’s feasible control set to other agent’s controls
${{\bf U}}^{\neg i}$, (3) is a GNEP [10]. Let

$\mathcal{U}^{i}({{\bf U}}^{\neg i})=\\{U^{i}|h^{i}({\bf U})\leq 0\\},$ (4)

denote the feasible control set for agent $i$ given the controls of other
agents ${{\bf U}}^{\neg i}$. Solving an (open loop) GNEP amounts to finding
controls ${\bf U}^{*}$ such that for each agent $i$,

$J^{i}(U^{i*},{\bf U}^{\neg i*})\leq J^{i}(U^{i},{\bf U}^{\neg
i*}),\quad\forall\,U^{i}\in\mathcal{U}^{i}({{\bf U}}^{\neg i}).$ (5)

However, since solving for the global GNEP is in general intractable, we
instead look for local GNEP where (5) is satisfied for all $U^{i}$ within a
local neighborhood of the optimal ${\bf U}^{*}$.

###  II-B Maximum Entropy Dynamic Games

Although the (global) Nash equilibria is a powerful concept, achieving Nash
equilibria requires the assumption that all cost functions are known exactly
and that each agent acts rationally by solving the GNEP exactly. However,
often times we only have an approximation of the cost function for the non-ego
agents and other agents may only act with approximate solutions of the GNEP.
To take these stochasticities into account, we take a relaxed control approach
and consider a stochastic control policy $\pi^{i}(u^{i}|{\bm{x}})$ with the
same deterministic dynamics as in (1). Let
$\mathbb{E}_{{p}}{\left[\cdot\right]}$ denote the expectation with respect to
a distribution $p$. We introduce an entropy term to the original objective (2)
and consider the expected cost under all agent’s policies $\pi^{i}$:

$J^{i}(\pi^{i})=\mathbb{E}_{{\pi}}{\left[\Phi^{i}({\bm{x}}_{T})+\sum_{t=1}^{T-1}\left(l^{i}({\bm{x}}_{t},{\bm{u}}_{t})-\alpha
H[\pi^{i}(\cdot|{\bm{x}}_{t})]\right)\right]},$ (6)

where $\alpha>0$ is a temperature term and $H[\pi]$ is the Shannon entropy of
$\pi$ defined as

$H[\pi]=-\mathbb{E}_{{\pi}}{\left[\log\pi\right]}=-\int\pi(u)\log\pi(u)\mathop{}\mathrm{d}u.$
(7)

The resulting GNEP is then formulated similarly to the deterministic case,
except that we only require that the constraints $h^{i}$ hold for the mean
controls:

$\displaystyle\min_{\pi^{i}}$ $\displaystyle J^{i}({\bf
U}),\qquad\textrm{s.t.}\quad h^{i}(\mathbb{E}_{{\pi}}{\left[{\bf
U}\right]})\leq 0.$ (8)

With (8), the task is now to find a stochastic policy $\pi^{i*}$ such that the
following holds for all $\pi^{i}$ within a neighborhood of $\pi^{i*}$:

$J^{i}(\pi^{i*},\pi^{\neg i*})\leq J^{i}(\pi^{i},\pi^{\neg
i*}),\quad\pi^{i}\in\Pi(\pi^{\neg i*}),$ (9)

where $\Pi(\pi^{\neg
i*})\coloneqq\\{\pi^{i}|h^{i}(\mathbb{E}_{{\pi}}{\left[{\bf U}\right]})\leq
0\\}$.

##  III Algorithms for Solving Maximum Entropy Dynamic Games

In this section, we now derive algorithms for solving the MaxEnt Dynamics
Games introduced in the previous section.

###  III-A Unconstrained Dynamic Programming

We first consider the unconstrained case for simplicity. Defining the value
function for agent $i$ given the policies of other agents ${\pi}^{\neg i}$ to
be

$V^{i}({\bm{x}})=\inf_{{\pi}^{i}}\left\\{J^{i}({\bm{x}},{\pi}^{i},{\pi}^{\neg
i})\right\\},$ (10)

applying dynamic programming results in Bellman’s equation:

$V^{i}({\bm{x}})=\inf_{\pi^{i}}\Big{\\{}\mathbb{E}_{{\pi}}{\left[l^{i}({\bm{x}},{\bm{u}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}})\right]}-\alpha
H[\pi^{i}(\cdot|{\bm{x}})]\Big{\\}}.$ (11)

In (11) and below we omit the time index $t$ for nonterminal times for
simplicity and use ${V^{i}}^{\prime}(f({\bm{x}},{\bm{u}}))$ to denote the
value function for agent $i$ at the next timestep.

It is well known that the optimal policy ${\pi}^{i*}$ that solves the infimum
in (11) is the Gibbs distribution [34, 15]

${\pi}^{i*}(u^{i}|{\bm{x}})=\frac{1}{Z^{i}}\exp\Big{(}-\frac{1}{\alpha}\mathbb{E}_{{{\pi}^{\neg
i}}}{\left[{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}}))+l^{i}({\bm{x}},{\bm{u}})\right]}\Big{)},$
(12)

where $Z^{i}$ denotes the partition function

$Z^{i}\coloneqq\int\exp\Big{(}-\frac{1}{\alpha}\mathbb{E}_{{{\pi}^{\neg
i}}}{\left[{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}}))+l^{i}({\bm{x}},{\bm{u}})\right]}\Big{)}\mathop{}\mathrm{d}u^{i}.$
(13)

Although we have obtained a closed-form expression for ${\pi}^{i*}$ in (12),
it is defined in terms of ${\pi}^{\neg i}$ which is unknown. Hence, unlike the
optimal control case, we must solve a system of equations for each agent to
find ${\pi}^{i*}$ and ${\pi}^{\neg i*}$.

###  III-B Unconstrained MELQGames

In this section, we propose using DDP to solve for Nash Equilibria of MaxEnt
dynamic games and derive the unconstrained MELQGames algorithm similar to
iLQGames in [12]. For notational simplicity, we will drop the second-order
approximation of the dynamics as in iterative Linear Quadratic Regulator
(iLQR) in our description of Differential Dynamic Programming (DDP). The
dropped second-order dynamics terms can easily be added back in the
derivations below. We refer readers to [19, 17, 12] for a detailed overview of
the vanilla DDP, iLQR and iLQGames algorithms.

The DDP algorithm consists of a forward pass and a backward pass. The forward
pass simulates the dynamics forward in time obtaining a set of nominal state
and control trajectories $(\bar{{\bm{x}}}_{0:T},\bar{{\bm{u}}}_{0:T-1})$,
while the backward pass solves the Bellman equation with a 2nd order
approximation of the costs and dynamics equations around the nominal
trajectories. The boundary conditions for the value functions $V^{i}$ for each
agent are obtained by performing a 2nd order Taylor expansion of the terminal
costs $\Phi^{i}$:

$\displaystyle V^{i}_{{\bm{x}}{\bm{x}},T}$
$\displaystyle=\Phi^{i}_{{\bm{x}}{\bm{x}}},$ $\displaystyle
V^{i}_{{\bm{x}},T}$ $\displaystyle=\Phi_{{\bm{x}}}^{i},$ $\displaystyle
V_{T}=$ $\displaystyle=\Phi^{i},$ (14)

where we follow the notation in DDP literature by denoting partial derivatives
via subscripts.

Additionally, we perform a quadratic approximation of the costs and linear
approximation of the dynamics around a nominal trajectory $(\bar{{\bf
X}},\bar{{\bf U}})$ , where ${\bf X}=[{\bm{x}}_{0},\dots,{\bm{x}}_{T}]$
denotes a trajectory of states

$\displaystyle l^{i}({\bm{x}},{\bm{u}})$ $\displaystyle\approx
l^{i}+\begin{bmatrix}l^{i}_{\bm{x}}\\\
l^{i}_{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}+\frac{1}{2}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}l^{i}_{{\bm{x}}{\bm{x}}}&l^{i}_{{\bm{x}}{\bm{u}}}\\\
l^{i}_{{\bm{u}}{\bm{x}}}&l^{i}_{{\bm{u}}{\bm{u}}}\end{bmatrix}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix},$ $\displaystyle f({\bm{x}},{\bm{u}})$
$\displaystyle\approx f+f_{\bm{x}}\delta{\bm{x}}+f_{\bm{u}}\delta{\bm{u}},$
(15)

where we have defined $\delta{\bm{x}}={\bm{x}}-\bar{{\bm{x}}}$ and
$\delta{\bm{u}}={\bm{u}}-\bar{{\bm{u}}}$.

Let $Q^{i}$ denote the terms inside the expectation in Bellman’s equation (11)

$Q^{i}({\bm{x}},{\bm{u}})\coloneqq
l^{i}({\bm{x}},{\bm{u}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}})).$ (16)

Then, $Q^{i}$ for the approximated system is quadratic:

$\displaystyle Q^{i}({\bm{x}},{\bm{u}})=\bar{V}^{i}+\delta Q^{i},$ (17)
$\displaystyle\delta Q^{i}\coloneqq\begin{bmatrix}Q^{i}_{\bm{x}}\\\
Q^{i}_{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}+\frac{1}{2}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}Q^{i}_{{\bm{x}}{\bm{x}}}&Q^{i}_{{\bm{x}}{\bm{u}}}\\\
Q^{i}_{{\bm{u}}{\bm{x}}}&Q^{i}_{{\bm{u}}{\bm{u}}}\end{bmatrix}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}.$ (18)

with $\bar{V}^{i}\coloneqq
l^{i}(\bar{{\bm{x}}},\bar{{\bm{u}}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}}))$.
The derivation and full expressions for the partial derivatives of $Q^{i}$ are
included in Appendix A. Performing a change of variables
$\delta{\bm{u}}={\bm{u}}-\bar{{\bm{u}}}$ on ${\pi}^{i}$ and taking out terms
that not functions of $\delta{u^{i}}$, the infimum in the Bellman equation
(11) simplifies to

$\displaystyle\inf_{{\pi}^{i}}\int{\pi}^{i}(\delta{u^{i}})\bigg{\\{}\Big{(}Q_{u^{i}}^{i}+Q_{u^{i}{\bm{x}}}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\mathbb{E}_{{{\pi}^{\neg i}}}{\left[\delta{{\bm{u}}^{\neg
i}}\right]}\Big{)}^{\mathrm{T}}\delta{u^{i}}$
$\displaystyle\qquad+\frac{1}{2}\delta{u^{i}}^{\mathrm{T}}Q_{u^{i}u^{i}}^{i}\delta{u^{i}}+\alpha\log{\pi}^{i}(\delta{u^{i}})\bigg{\\}}\mathop{}\mathrm{d}\delta{u^{i}},$
(19)

Since the expression above is now quadratic in $\delta{u^{i}}$ for each agent
$i$, the coupled systems of equations can be solved as shown in the following
lemma.

######  Lemma 1 (Optimal MELQGames Policy).

The optimal policy ${\pi}^{i*}$ (in the Nash equilibria sense) which solves
(19) for each agent $i$ has the form

$\pi^{i*}={Z^{i}}^{-1}\exp\Big{(}-\frac{\alpha}{2}(\delta{u^{i}}-\delta{u^{i*}})^{\mathrm{T}}Q_{u^{i}u^{i}}^{i}(\delta{u^{i}}-\delta{u^{i*}})\Big{)},$
(20)

where $\delta{u^{i*}}$ is the solution to the following system of equations

$0=\hat{Q}_{{\bm{u}}{\bm{u}}}{\delta{\bm{u}}^{*}}+Q_{{\bm{u}}{\bm{x}}}\delta{\bm{x}}+Q_{{\bm{u}}},\quad{\delta{\bm{u}}^{*}}={\bm{k}}+{\bf
K}\delta{\bm{x}},$ (21)

and the matrix $\hat{Q}_{{\bm{u}}{\bm{u}}}\in\mathbb{R}^{n_{\bm{u}}\times
n_{\bm{u}}}$ is obtained by vertically stacking the row vectors
$Q^{i}_{u^{i}{\bm{u}}}$ for each $i\in\\{1,\dots,N\\}$:

$(\hat{Q}_{{\bm{u}}{\bm{u}}})^{\mathrm{T}}\coloneqq\begin{bmatrix}(Q^{1}_{u^{1}{\bm{u}}})^{\mathrm{T}}&\ldots&(Q^{N}_{u^{N}{\bm{u}}})^{\mathrm{T}}\end{bmatrix}^{\mathrm{T}}.$
(22)

We defer the proof of Lemma 1 to the appendix in Appendix B. Note that the
optimal policy $\pi^{i*}$ is Gaussian distribution with mean $\delta{u^{i*}}$
and covariance matrix $\Sigma^{i}=\alpha({Q_{u^{i}u^{i}}^{i}})^{-1}$, where
$\delta{u^{i*}}$ has the same expression as in the iLQGames case.
Additionally, as $\alpha\to 0$, $\pi^{i*}$ converges to the delta distribution
centered on $\delta{u^{i}}^{*}$.

Figure 2:  Sampled trajectories from the stochastic policy obtained from
solving the MaxEnt Nash equilibria (20) for a single agent. The covariance of
the MaxEnt policy reflects the curvature of the cost landscape with a tighter
distribution of position in the middle than at the ends.

Information from the value function is incorporated in the policy in both the
mean and the covariance as the covariance is higher along eigenvectors of
${Q_{u^{i}u^{i}}^{i}}$ which have small eigenvalues. Fig. 2 illustrates
sampled trajectories from the optimal MaxEnt Nash equilibria for a single
agent with triple integrator dynamics. The trajectories have a tighter
distribution in the middle where the cost function, shown in the contour plot,
has a much higher curvature. Also, the terminal quadratic cost is higher along
the direction of the x-axis, causing the trajectories near the target (yellow
star) to have a lower variance along the x-axis.

We next substitute equation (20) from Lemma 1 into the Bellman equation (19)
to derive the update equations for the value function, shown in the following
lemma.

######  Lemma 2 (MELQGames Value Function Update).

Suppose the infimum in the Bellman equation (11) is solved with policy
$\pi^{i*}$ with mean $\delta{\bm{u}}={\bm{k}}+{\bf K}\delta{\bm{x}}$ according
to Lemma 1. Then, the value function using for agent $i$ has the form

$\displaystyle V^{i}({\bm{x}})$
$\displaystyle=\mathbb{E}_{{\delta{\bm{u}}\sim\tilde{\pi}}}{\left[l^{i}({\bm{x}},{\bm{u}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}})\right]}-\alpha
H[\tilde{\pi}^{i}],$ (23)
$\displaystyle=\Big{(}V^{i}+V_{H}^{i}\Big{)}+{V_{\bm{x}}^{i}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}V_{{\bm{x}}{\bm{x}}}^{i}\delta{\bm{x}},$
(24)

where the terms $V^{i}$, $V_{H}^{i}$, $V_{x}^{i}$ and $V_{xx}^{i}$ have the
form

$\displaystyle V^{i}$
$\displaystyle=\bar{V}^{i}+Q_{u}^{i}{\bm{k}}+\frac{1}{2}{\bm{k}}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\bm{k}},$
(25) $\displaystyle\begin{split}V_{H}^{i}&=\frac{\alpha}{2}\Big{(}\log\lvert
Q_{u^{i}u^{i}}^{i}\rvert-n_{u^{i}}\log(2\pi\alpha)\Big{)}\\\
&\quad+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right],\end{split}$
(26) $\displaystyle V_{\bm{x}}^{i}$ $\displaystyle=Q_{\bm{x}}^{i}+{\bf
K}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\bm{k}}+{\bf
K}^{\mathrm{T}}Q_{\bm{u}}^{i}+Q_{{\bm{x}}{\bm{u}}}^{i}{\bm{k}},$ (27)
$\displaystyle V_{{\bm{x}}{\bm{x}}}^{i}$
$\displaystyle=Q_{{\bm{x}}{\bm{x}}}^{i}+{\bf
K}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\bf K}+{\bf
K}^{\mathrm{T}}Q_{{\bm{u}}{\bm{x}}}^{i}+Q_{{\bm{x}}{\bm{u}}}^{i}{\bf K}.$ (28)

Again, we defer the proof of Lemma 2 to the appendix in Appendix C.

Note that the update rules for $V^{i},V^{i}_{\bm{x}}$ and
$V^{i}_{{\bm{x}}{\bm{x}}}$ are exactly the same as in iLQGames [12], with the
only difference being the addition of the $V^{i}_{H}$ term resulting from the
maximum entropy term. This term only depends on ${Q_{u^{i}u^{i}}^{i}}$ and
approaches $0$ as $\alpha\to 0$. Since we take ${Q_{u^{i}u^{i}}^{i}}$ to be
constant during each iteration of MELQGames, $V^{i}_{H}$ is not a function of
${\bm{x}}$. Consequently, the backward pass of MELQGames can be performed by
additionally computing $V_{H}^{i}$ and $\Sigma^{i}$ in the backward pass of
iLQGames. Also, note that unlike the optimal control case where we can
simplify the value function update (25)–(28) by substituting the definition of
${\bm{k}}$ and ${\bf K}$ to cancel out terms, this does not hold in the
dynamic games case. This is because $Q_{{\bm{u}}{\bm{u}}}^{i}$ (Hessian of
$Q^{i}$) does not equal to $\hat{Q}_{{\bm{u}}{\bm{u}}}$ (stacked rows of
$Q_{u^{i}{\bm{u}}}^{i}$) in general.

###  III-C Constrained MELQGames via Augmented Lagrangian

To incorporate constraints, we use the augmented Lagrangian framework similar
to the approach in ALGames [4], except we choose to use the DDP style
unconstrained optimizer as opposed to Newton’s method. Let us denote by
$\mathcal{L}^{i}$ the augmented Lagrangian for agent $i$. Then,

$\mathcal{L}_{A}^{i}(\pi,\lambda;\rho)=J^{i}(\pi)+\frac{\rho}{2}\sum_{j}\max\bigg{(}0,(h^{i})_{j}(\mathbb{E}{\left[{\bf
U}\right]})+\frac{\lambda^{i}_{j}}{\rho}\bigg{)}^{2}.$ (29)

where $\rho>0$ denotes the penalty parameter and $\lambda^{i}_{j}>0$ denotes
the Lagrange multiplier corresponding to the $j$th constraint $(h^{i})_{j}$
for agent $i$. Since each agent may in general have a different number of
constraints, the Lagrange multipliers are specific to each agent’s
constraints.

If the optimal Lagrange multipliers $\lambda^{i*}_{j}$ were known, then for a
sufficiently large value of $\rho$ the minimizer of the augmented Lagrangian
$\mathcal{L}_{A}^{i}$ would be a local minimum of the constrained problem [21,
25]. To update the dual parameters $\lambda^{i}_{j}$, we perform the following
dual-ascent step

$(\lambda^{i}_{j})^{+}\leftarrow\max(0,\lambda^{i}_{j}+\rho(h^{i})_{j}(\mathbb{E}{\left[{\bf
U}\right]}).$ (30)

where we use the $+$ to denote the new $\lambda$. Intuitively, the above
update can be seen as an approximation to the optimal Lagrange multipliers
$\lambda^{i*}_{j}$. Let $\mathcal{I}_{A}$ denote the set of active
constraints, and suppose that the Lagrange multipliers for all inactive
constraints are zero such that

$j\not\in\mathcal{I}_{A}\implies(h^{i})_{j}+\frac{\lambda^{i}_{j}}{\rho}<0.$
(31)

Then, if $\pi$ is a minimizer of $\mathcal{L}_{A}^{i}$ then

$0=\nabla_{u^{i}}\mathcal{L}_{A}^{i}=\nabla_{u^{i}}J^{i}+\sum_{j\in\mathcal{I}_{A}}\big{[}\rho(h^{i})_{j}+\lambda^{i}_{j}\big{]}\nabla_{u^{i}}(h^{i})_{j},$
(32)

and hence $(\lambda^{i}_{j})^{+}=\rho(h^{i})_{j}+\lambda^{i}_{j}$ is a good
approximation to the Lagrange multiplier of the original constrained problem.
To maintain dual feasibility of the Lagrange multipliers, we project them by
taking the positive part.

Alternatively, the Augmented Lagrangian method can be viewed as projected
steepest ascent applied to the dual problem of (5) where $\rho$ plays the role
of the step size in (30). Indeed, convergence rate results for Augmented
Lagrangian methods show that under suitable conditions (ex. Linear Independent
Constraint Qualification (LICQ) and Second-order Sufficient Optimality
Condition (SOSC) are satisfied at the local minima), the Lagrange multipliers
converge linearly [21, 25] with rate

$\frac{\lVert(\lambda^{i}_{j})^{+}-\lambda^{i*}_{j}\rVert}{\lVert\lambda^{i}_{j}-\lambda^{i*}_{j}\rVert}\leq\frac{M}{\rho},$
(33)

for some constant $M$. Hence, larger values of $\rho$ should theoretically
result in faster convergence of the Lagrange multipliers. However, values of
$\rho$ that are too large may make the unconstrained problem ill-conditioned
and slow down convergence [21, 25]. Hence, Augmented Lagrangian methods
usually advocate for increasing $\rho$ by some factor $\gamma>0$ if a
sufficient decrease condition on some feasibilty metric such as

$\mathcal{V}\coloneqq\left\lVert\min\left\\{-(h^{i})_{j},\frac{\lambda^{i}_{j}}{\rho}\right\\}\right\rVert,$
(34)

has not been met [2].

The constrained MELQGames algorithm consists of an iterative scheme where we
alternate approximately solving the (unconstrained) Nash equilibria for cost
functions $\mathcal{L}_{A}^{i}$ and updating the Lagrange multipliers
$\lambda^{i}_{j}$ with (30). If the metric $\mathcal{V}$ has not decreased by
more than some $\tau\in(0,1)$ since the last dual update, we increase $\rho$.

We now show in the following lemma that if the augmented Lagrangian MELQGames
converges, the solution is a local GNEP.

######  Lemma 3.

Suppose that the augmented Lagrangian MELQGames converges to a tuple
$(\pi^{*},\lambda^{i}_{j},\rho)$ for some $\rho>0$ which satisfies dual
feasibility of $\lambda$, LICQ and SOSC. Then, $\pi^{*}$ is a Generalized Nash
Equilibrium (GNE) for (5).

We defer the proof of Lemma 3 to Appendix D.

##  IV Extensions to Modeling Multimodality

The vast majority of existing works that investigate game theoretic multi-
agent interactions consider unimodal behaviors [4, 11, 12, 20, 31, 36].
However, this may not be enough when the true value function is not unimodal,
a common situation that can arise from nonconvex dynamics, cost functions or
constraints. In this section, we first outline a computational challenge for
tackling the problem of multimodality in dynamic games. We then propose a
computationally efficient multimodal extension to MELQGames by reformulating
the problem as an incomplete information games with information asymmetry and
show how our formulation can additionally be used for Bayesian inference of
the latent mode.

In this paper, we focus our attention on multi-agent interactions where
multimodality is induced by uncertainty about multimodal behavior of non-ego
agents despite having unimodal best-responses. We leave extensions to
situations where the ego agent has a multimodal best-response by considering
approaches such as compositionality [30] as future work.

One of the biggest challenges for handling multimodality with multiple agents
is that computational costs can quickly become unfeasible due to the
combinatorial explosion when accounting for the interactions between all
agents. To see this, consider a game with $N$ agents where each agent has a
policy with $A$ different modes. Evaluating the Nash equilibrium requires
evaluating the expectation over all policies for all timesteps
$t=0,\dots,T-1$, resulting in a total of $O(T\,A^{N})$ evaluations of the cost
function and dynamics. This combinatorial explosion is computationally
intractable for any kind of realtime planning.

###  IV-A Multimodal Dynamic Games via Information Asymmetry

We now propose a method for tackling the challenges mentioned above. To start,
we refine our problem setup and identify one agent as the “ego” agent. Given
that many applications for planning have the goal of controlling an agent,
this is not an unreasonable assumption. From hereon after, we denote the ego
agent with index $1$ and use ${\neg 1}$ to refer to non-ego agents.

Consider a set of $A$ different local (generalized) Nash equilibria with
$\\{({\bf X}^{a},{\bf U}^{a})\\}_{a=1}^{A}$ and let $a\in\\{1,\dots,A\\}$ be a
discrete latent random variable that determines the nominal trajectory around
which the cost functions and dynamics are approximated. We now consider an
extension of the maximum entropy dynamic game (8), where all agents except for
the ego agent have full knowledge of the value of $a$ and are playing the
corresponding optimal policy $\pi^{a}$. However, the non-ego agents
incorrectly believes that the ego agent knows what the true mode is. This is
now a dynamic game with incomplete information since the ego agent only has a
belief of what the true game is but does not know what the true dynamics nor
cost are. However, since the non-ego agents know what the true mode is, their
actions act as a signal for the ego agent and allow the ego-agent to update
its belief using this information.

In the theory of games with incomplete information, a state of the world
$\omega$ fully defines a possibility of the true cost function and dynamics of
the game [18]. Uncertainty over the true state of the world $\omega_{*}$
implies uncertainty over what game is being played. Let $Y$ be a finite set
containing all possible states of the worlds and $p_{i}:Y\to\Delta(Y)$ be the
belief of each agent mapping each state of the world $\omega\in Y$ to a
probability distribution over $Y$.

For our problem, let $\omega_{a,s}$ and $\omega_{a,m}$ for $a=1,\dots,A$
denote different states of the world such that when
$\omega_{*}\in\big{\\{}\omega_{a,s},\,\omega_{a,m}\big{\\}}$, the true cost
and dynamics that correspond to the approximated costs and dynamics around the
local (generalized) Nash equilibrium
$(\bar{{\bm{x}}}^{a},\bar{{\bm{u}}}^{a})$. The “$s$” and “$m$” here can be
taken to mean “single” and “multi”. We now define our set $Y$ as

$Y\coloneqq\\{\omega_{1,s},\dots,\omega_{A,s},\omega_{1,m},\dots,\omega_{A,m}\\}.$
(35)

Let $\mathbbm{1}$ denote the indicator function and $p_{a}$ denote the ego
agent’s prior over the modes $a$ with support on the set
$\\{\omega_{a,m}\\}_{a=1}^{A}$. We define the beliefs of the ego agent $p_{1}$
and non-ego agents $p_{{\neg 1}}$ as

$\displaystyle p_{1}(\omega)$
$\displaystyle=\begin{dcases}\mathbbm{1}_{\omega_{a,s}}(\omega),&\omega=\omega_{a,s},\;a\in\\{1,\dots,A\\}\\\
p_{a}(\omega),&\omega=\omega_{a,m},\;a\in\\{1,\dots,A\\}\end{dcases},$ (36)
$\displaystyle p_{{\neg 1}}(\omega)$
$\displaystyle=\begin{dcases}\mathbbm{1}_{\omega_{a,s}}(\omega),&\omega=\omega_{a,s},\;a\in\\{1,\dots,A\\}\\\
\mathbbm{1}_{\omega_{a,s}}(\omega),&\omega=\omega_{a,m},\;a\in\\{1,\dots,A\\}\end{dcases},$
(37)

To give intuition to the above game setup, note that each mode $a$ is
associated with two world states: $\omega_{a,s}$ and $\omega_{a,m}$. When the
true state $\omega_{*}$ is at $\omega_{a,s}$, all agents correctly believe
that the state is $\omega_{a,u}$. However, when $\omega_{*}=\omega_{a,m}$, the
non-ego agents incorrectly believe that the true state is $\omega_{a,s}$ while
the ego agent correctly believes that the true state lies is in the set
$\\{\omega_{a,m}\\}$ but is unsure which is the correct one.

With the above setup, we can use tools from game theory to gain intuition into
the belief-structure of this game, namely what each agent believes is true,
what each agent believes other agents believe is true and so on [18].

######  Definition 1 (Belief Operator).

Let $B_{i}$ denote the belief operator such that for any event $A\subseteq Y$

$B_{i}A\coloneqq\\{\omega\in Y:p_{i}(A|\omega)=1\\},$ (38)

and the conditional belief $p_{i}(A|\omega)$ is defined as

$p_{i}(A|\omega)\coloneqq\mathbb{E}_{{p_{i}(\omega)}}{\left[\mathbbm{1}_{A}\right]}.$
(39)

In other words, $\omega\in B_{i}A$ means that at $\omega$, event $A$ obtains
according to agent $i$’s belief in the sense that at least one of $\omega\in
A$ corresponds to the true state. We next define the concept of common belief
[18]:

######  Definition 2 (Common Belief).

Let $A\subseteq Y$ be an event and $\omega\in Y$. The event $A$ is common
belief at state $\omega$ if every agent believes that $A$ obtains, every agent
believes that every agent believes that $A$ obtains, and so on. In other
words, for every finite sequence $i_{1},\dots,i_{L}$ of agents:

$\omega\in B_{i_{1}}\dots B_{i_{L}}A,$ (40)

In particular, the event $Y$ is common belief among the agents, i.e., each
agent knows that the true world state $\omega$ must be an element of $Y$.

Using Definition 1 and Definition 2, we now precisely define the key property
of the dynamic game — it is common knowledge that the non-ego agents believes
that the ego agent knows the mode.

######  Lemma 4.

Let $E=\\{\omega_{a,s}\\}_{a=1}^{A}$ denote the event that the ego agent knows
the correct mode with probability 1. Then, for all $i\not=1$, $\omega\in
B_{i}E$, i.e. all non-ego agents believe that the ego agent knows the mode
perfectly. Furthermore, it is common belief that $B_{i}E_{a}$ for all
$i\not=1$. In particular, the ego agent (correctly) believes that all non-ego
agents (incorrectly) believes that it knows the correct mode.

We delegate the proof of Lemma 4 to Appendix E. Furthermore, we refer the
interested reader to Maschler et al. [18] for more information on belief
spaces and games with incomplete information. The above lemma shows how this
choice of information asymmetry simplifies computation. Namely, since each
non-ego agent believes that the ego-agent knows the mode perfectly, each non-
ego agent’s control will exactly be the Nash-equilibria control in the
unimodal case.

Finally, we introduce the concept of a (local) Bayesian Nash equilibrium. This
is a generalization of the classical (generalized) Nash equilibrium to the
incomplete information case, where the expectation of an agent’s cost with
respect to its own belief is used [18]:

######  Definition 3 (Bayesian Nash equilibrium).

A policy $\pi^{*}$ is a Bayesian Nash equilibrium if, for all agents $i$,

$\mathbb{E}_{{p_{i}}}{\left[J^{i}(\pi^{i*},\pi^{\neg
i*})\right]}\leq\mathbb{E}_{{p_{i}}}{\left[J^{i}(\pi^{i},\pi^{\neg
i*})\right]},\quad\pi^{i}\in\Pi(\pi^{\neg i*}),$ (41)

where the expectation is taken with respect to agent $i$’s belief of the world
state $\omega_{*}\in Y$.

As a result, when $\omega_{*}=\omega_{a,s}$, since all agents know the mode
$a$, the optimal $\pi^{*}$ simply corresponds to the optimal policy $\pi^{a}$
for the generalized Nash equilibrium found previously. When
$\omega_{*}=\omega_{a,m}$, the non-ego agents believe that the true state is
still $\omega_{a,s}$ and hence the optimal policy is still $\pi^{\neg i,a}$.
On the other hand, for $\omega_{*}=\omega_{a,m}$, although the ego-agent is
uncertain about the true value of $a$, it knows via Lemma 4 that the non-ego
agents will play $\pi^{\neg i,a}$. Furthermore, the controls of the non-ego
agents $u^{\neg i}$ give information about what the true value of $a$ is.
Hence, the problem of computing the Bayesian Nash equilibrium $\pi^{i*}$
reduces to the problem of solving a Partially Observable Markov Decision
Process (POMDP) where the belief space is over the latent variable $a$ and the
observations ${\bm{o}}$ are the observed controls of the non-ego agents. The
conditional dependencies for the POMDP are shown in the graphical model in
Fig. 3.

Figure 3:  Graphical model of the POMDP for the ego agent with corresponding
value function (42). The state ${\bm{x}}_{t}$ and non-ego agent controls
${\bm{u}}_{t}^{{\neg 1}}$ are observed variables, while the computed set of
non-ego policies $\pi_{t}^{{\neg 1},a}$ is dependent on the partially
observable discrete latent mode $a$. The latent mode $a$ also affects the true
cost function $l^{1,a}_{t}$ and the dynamics for the next state
${\bm{x}}_{t+1}$.

By using the standard belief-space approach to solve the POMDP, the Bellman
equation takes the form

$V^{1}({\bm{x}},{\bm{b}}_{t})=\inf_{\pi^{1}}\mathbb{E}_{\pi}\bigg{[}\mathbb{E}_{{\bm{b}}_{t}}l^{1,a}({\bm{x}},{\bm{u}})+\mathbb{E}_{\pi^{{\neg
1}}}{V^{1}}^{\prime}\big{(}f({\bm{x}},{\bm{u}}),{\bm{b}}_{t+1}\big{)}\bigg{]},$
(42)

where ${\bm{b}}_{t+1}$ refers to the updated belief for the next timestep via
Bayesian filtering:

${\bm{b}}_{t+1}(a)\propto\pi^{{\neg 1}}({\bm{u}}^{{\neg
1}}|a)\,{\bm{b}}_{t}(a).$ (43)

While solving for general POMDPs is computationally untractable [23], there
exist computationally efficient methods for solving POMDPs over discrete
latent spaces by using a DDP-based approach [24]. However, to simplify the
implementation and presentation of this work, we choose to bypass the problem
of solving the full POMDP by making the following assumption.

######  Assumption 1.

The ego agent will be informed of the true mode $a$ after one timestep at
$t=1$.

With this assumption, the value functions for $t\geq 1$ are known and
correspond to the value functions $V^{1,a}$ for each mode $a$ of the found
local Nash equilibrium. Hence, the Bellman equation at $t=0$ reads

$\displaystyle\begin{split}V^{1}&=\inf_{\pi^{1}}\mathbb{E}_{{\bm{b}}_{0},\pi}\bigg{[}l^{1,a}({\bm{x}},{\bm{u}})+{V^{1,a}}^{\prime}\big{(}f({\bm{x}},{\bm{u}})\big{)}\bigg{]}-\alpha
H[\pi^{1}],\end{split}$
$\displaystyle\begin{split}&=\inf_{\pi^{1}}\bigg{\\{}\mathbb{E}_{\pi^{i}}\Big{[}\frac{1}{2}{u^{1}}^{\mathrm{T}}\tilde{Q}_{u^{1}u^{1}}^{1}u^{1}+\left(\tilde{Q}_{u^{1}}^{1}+\tilde{Q}_{u^{1}}^{1}{\bm{x}}\right)^{\mathrm{T}}u^{i}\Big{]}\\\
&\qquad\qquad+c-\alpha H[\pi^{1}]\bigg{\\}},\end{split}$ (44)

where ${\bm{b}}_{0}\in\Delta(Y)$ denotes the ego agent’s prior belief of the
true mode, $c$ encapsulates all terms that are constant with respect to
$u^{1}$, and

$\displaystyle\tilde{Q}_{u^{1}u^{1}}^{1}$
$\displaystyle\coloneqq\mathbb{E}_{{{\bm{b}}_{0}}}{\left[Q_{u^{1}u^{1}}^{1,a}\right]},\qquad\tilde{Q}_{u^{1}{\bm{x}}}^{1}\coloneqq\mathbb{E}_{{{\bm{b}}_{0}}}{\left[Q_{u^{1}{\bm{x}}}^{1,a}\right]},$
(45) $\displaystyle\tilde{Q}_{u^{1}}^{1}$
$\displaystyle\coloneqq\mathbb{E}_{{{\bm{b}}_{0}}}{\left[Q_{u^{1}}^{1,a}-Q_{u^{1}u^{1}}^{1,a}\bar{u}^{1,a}-Q_{u^{1}{\bm{x}}}^{1,a}\bar{{\bm{x}}}^{a}\right]}.$
(46)

Consequently, the optimal policy $\pi^{1}$ corresponds to the Gibbs
distribution and is solved in the same way as in MELQGames Lemma 1.

Choices of the prior distribution:  There are many valid choices for the prior
distribution on the modes ${\bm{b}}_{0}$. If no prior information on the non-
ego agents is known, one choice is to choose ${\bm{b}}_{0}$ as the maximum
entropy distribution that minimizes the sum of the value functions for each
agent:

${\bm{b}}_{0}(a)=\inf_{p}\mathbb{E}_{{a\sim
p}}{\left[\sum_{i=1}^{N}V^{i,a}({\bm{x}}_{0})\right]}-\alpha H[p].$ (47)

With this prior, modes that result in lower costs for all agents will have
higher probabilities over modes that have high costs for all agents. However,
in the context of planning for an ego agent, this may favor local minima which
are bad for the ego agent when better alternatives exist.

Figure 4: Schematic diagram of the proposed MPC MMELQGames algorithm presented
in (1) and (3).

Alternatively, we can bias the selection of modes to ones which are favorable
to the ego-agent by choosing ${\bm{b}}_{0}$ as the maximum entropy
distribution that minimizes the sum of the ego agent’s value functions

${\bm{b}}_{0}(a)=p(a|{\bm{x}}_{0})=\inf_{p}\mathbb{E}_{{a\sim
p}}{\left[V^{1,a}({\bm{x}}_{0})\right]}-\alpha H[p].$ (48)

###  IV-B Latent Mode Bayesian Inference via MaxEnt

In a MPC context, we can improve on our choices of the prior since the
controls of the non-ego agents from previous timesteps act as signals for the
true mode $a$. By observing them, the ego agent can form a more accurate
estimate of ${\bm{b}}_{0}$. For simplicity, we assume that the observations of
non-ego agent’s controls are noiseless, though this can be generalized to the
noisy case in a Bayesian fashion by incorporating an observation model.
Suppose that the controls $\hat{{\bm{u}}}^{{\neg
1}}\coloneqq{\bm{u}}_{-k:-1}^{{\neg 1}}$ and optimal policies $\\{\pi^{{\neg
1},a}\\}_{a=1}^{A}$ for all non-ego agents from the past $k$ timesteps are
known. Then, the posterior on those previous controls can be used for our
estimate of ${\bm{b}}_{0}$:

${\bm{b}}_{0}(a)\coloneqq p(a|\hat{{\bm{u}}}^{{\neg 1}})\propto
p(a)\prod_{t=-k}^{-1}p({\bm{u}}_{t}^{{\neg 1}}|a),$ (49)

where $p(a)$ is chosen to be the prior (48) from the previous subsection that
biases towards modes that are favorable to the ego-agent. With this choice of
prior, modes which describe the controls of non-ego agents and are beneficial
to the ego-agent will have high probability.

When computing the posterior in (49), it is assumed that all of the controls
in $\hat{{\bm{u}}}^{{\neg 1}}$ correspond to the same mode $a$. While one
could simply use all of the collected observations to compute the posterior,
this choice is invalid in the case that non-ego agents switch to a different
mode somewhere in the middle of the collected observations. To solve this
issue, we can make the less restrictive assumption that only the last $k$
controls from non-ego agents correspond to the same mode.

##  V Game Theoretic Model Predictive Control

In this section, we summarize the MMELQGames algorithm which combines the
solution to the information asymmetric game setup described in Section IV-A
with the latent mode Bayesian inference in Section IV-B and propose a receding
horizon game-theoretic planner that can reason about and infer multiple
hypothesis in Algorithm 1, Algorithm 2, Algorithm 3 and summarized in Fig. 4.
Algorithm 1 can be summarized as first solving for a set of local Nash
equilibrium in Algorithm 2, then using the solutions as inputs to solve a
POMDP for the ego agent with uncertainty over the mode in Algorithm 3.

Algorithm 1 MMELQGames

1:Initialize $\\{\pi\\}_{a=1}^{\tilde{A}}$ with random policy.

2:Initialize buffer of non-ego control observations $\mathcal{U}$.

3:repeat

4: $\\{({\bf X}^{a},\pi^{a})\\}_{a=1}^{\tilde{A}}\leftarrow\textrm{ Find
Modes}$

5: $\pi^{1}\leftarrow\textrm{ Solve Ego Agent POMDP}$

6: Execute $\pi^{1}$ by sampling or taking the mean control

7: Observe non-ego controls ${\bm{u}}^{{\neg 1}}$ and add to $\mathcal{U}$

8: Shift $\pi$ by one timestep for warmstarting next iteration

Algorithm 2 Find Modes

1:Number of modes $A$, Number of iterations $K$, control estimates
$\\{\bar{{\bm{u}}}^{a}\\}_{a=1}^{A}$, Penalty parameter $\rho$, Feasibility
progress $\tau>0$, Penalty increase $\gamma>0$, Thresholds $\epsilon>0$

2:Initialize $\lambda^{i}_{j}=0,\mathcal{V}^{a}_{0}=\infty,\rho^{a}=1$

3:Compute nominal mean trajectory $\\{\bar{{\bf X}}^{a}\\}$ using
$\\{\bar{{\bf U}}^{a}\\}$.

4:for $k=1$ to $K$ do

5: for $a=1$ to $A$ in parallel do

6: $\pi^{i,a*},V^{i,a}_{x},V^{i,a}_{xx}\leftarrow$ Backward pass (20),
(25)–(28)

7: end for

8: for $a=1$ to $A$ in parallel do

9: $(\bar{{\bf X}}^{a},\bar{{\bf U}}^{a})\leftarrow$ Line Search on
$\max_{i}\lVert J^{i}_{u^{i}}\rVert$

10: end for

11: Compute $\mathcal{V}^{i}_{k}$ using (34)

12: if $\max_{i}\lVert J^{i}_{u^{i}}\rVert\leq\epsilon$ then $\triangleright$
Unconstrained Converged

13: if $\mathcal{V}^{a}_{k}\leq\epsilon$ then $\triangleright$ Constraints
Converged

14: Save $(\bar{{\bf X}}^{a},\bar{{\bf
U}}^{a},\pi^{u,a*},V_{x}^{i,a},V_{xx}^{i,a})$ and reinitialize mode $a$ by
sampling from $\pi$.

15: end if

16: if $\mathcal{V}^{a}_{k}>\tau\mathcal{V}^{a}_{k-1}$ then $\triangleright$
Insufficient Decrease

17: $\rho^{a}\leftarrow\gamma\rho^{a}$

18: end if

19: end if

20:end for

21:$\\{\bar{{\bf U}}^{a}\\}_{a=1}^{\tilde{A}}\leftarrow\textrm{ Cluster
}\\{\bar{{\bf U}}^{a}\\}$

Algorithm 3 Solve Ego Agent POMDP

1:Observed controls from past $k$ timesteps ${\bm{u}}_{-k:-1}^{{\neg 1}}$,
Value functions $V^{i,a}$, Optimal Policies $\\{\pi^{{\neg
1},a}\\}_{a=1}^{\tilde{A}}$ for non-ego agents

2:$p(a)\leftarrow$ Compute prior with (47) or (48)

3:${\bm{b}}_{0}\leftarrow$ Compute initial belief with (49)

4:$\pi^{1}\leftarrow$ Solve full (42) or approximate (IV-A) POMDP

Algorithm 2 starts by first finding a set of modes that each solve the local
maximum entropy generalized Nash equilibrium problem (8). Moreover, to obtain
the optimal policies for the non-ego agents from previous timesteps, we solve
starting from the earliest timestep which we wish to condition our posterior
computation (49) on, warm-starting this computation from the previous
iteration’s solution if available. To solve for each mode, we use the
MELQGames algorithm. More specifically, we first compute the nominal state
trajectories $\\{\bar{{\bm{x}}}^{a}\\}_{a=1}^{A}$ as well as derivatives of
the cost functions $l^{i}$ and dynamics $f$ along
$(\bar{{\bm{x}}}^{a},\bar{{\bm{u}}}^{a})$ for each mode. Then, we solve for
the backward pass by computing the optimal policy (20) and updating the value
function (24) for each timestep starting from the terminal time $T$. Finally,
we update the nominal controls using a line search on the maximum of the norm
$\max_{i}\lVert J^{i}_{u^{i}}\rVert$. We exploit the fact that each local Nash
equilibrium can be computed independent by solving for $A$ local generalized
Nash equilibrium in parallel, where $A$ is chosen to be the number of cores
available for parallel processing on the CPU. This iteration of backward and
forward pass continues for each mode until this norm is smaller than some
threshold $\epsilon$, upon which it is saved into a set of converged modes
before being reinitialized from the current $\pi$. After the maximum number of
iterations has been reached, we perform clustering via k-means to remove
potential duplicate modes before returning the reduced set
$\\{(\bar{{\bm{x}}}^{a},\bar{{\bm{u}}}^{a})_{a=1}^{\tilde{A}}\\}$ of unique
Nash equilibrium.

Then, in Algorithm 3, we use the ego agent’s value function, optimal policies
for the non-ego agents $\pi^{\neg i,a}$ and observed controls from non-ego
agents to perform Bayesian inference on the mode $a$ to compute our belief
prior ${\bm{b}}_{0}$ via (49). Consequently, we use ${\bm{b}}_{0}$ and
$\pi^{\neg i,a}$ to solve the POMDP (42) and obtain the optimal policy
$\pi^{1,*}$. This can be done by either solving the full POMDP (42) using the
method from [24] or by solving the approximated one-step POMDP (IV-A).

Finally, we either execute a random sample from $\pi^{1,*}$ or use the mean
control before repeating the algorithm again in a receding horizon fashion.

##  VI Connections to Related Works

###  VI-A Game-Theoretic Planning

There are two main approaches to solving for game-theoretic equilibria:
Iterative Best Response (IBR)-based and direct methods.

IBR-based methods:  IBR-based methods rely on either the Jacobi decomposition
or Gauss-Seidel decomposition to decompose the problem of finding first-order
stationary points into separate optimal control problems for each agent [3,
36]. These methods optimize the controls for one agent while keeping the
controls for other agents fixed, repeating this process iteratively until
convergence. By holding controls, IBR assumes that
$\frac{\partial{{\bm{u}}}^{\neg i}_{t+1}}{\partial
u^{i}_{t}}=\frac{\partial{{\bm{u}}}^{\neg
i}_{t+1}}{\partial{\bm{x}}_{t+1}}\frac{\partial{\bm{x}}_{t+1}}{\partial
u^{i}_{t}}=0$. As a result, IBR lacks the term below key to describing inter-
agent behavior arising from asymmetric inter-agent coupling terms:

$\frac{\partial J^{i}}{\partial u^{i}_{t}}=\frac{\partial
J^{i}}{\partial{\bm{x}}_{t+2}}\cdot\left(\frac{\partial{\bm{x}}_{t+2}}{\partial{{\bm{u}}}^{\neg
i}_{t+1}}\frac{\partial{{\bm{u}}}^{\neg
i}_{t+1}}{\partial{\bm{x}}_{t}}\frac{\partial{\bm{x}}_{t}}{\partial
u^{i}_{t}}+\dots\right).$ (50)

To remedy this, approaches from [31, 32, 33] propose the SE-IBR algorithm
which extends IBR by accounting for some of missing information using the
sensitivity nformation from the Lagrange multipliers of active constraints.
However, their approach relies on a particular structure of the cost function.
Additionally, the convergence of IBR-based methods is not well understood [10]
and can potentially require many trajectory optimization iterations before
convergence.

Direct methods:  Direct methods solve for the coupled system of equations
resulting from the first-order stationary conditions directly. Examples
include methods based on Newton’s method [7, 8, 4] and DDP [12, 28]. The
proposed MMELQGames algorithm falls under the category of DDP-based methods as
it solves a quadratic approximation of the dynamic game during each timestep.
However, unlike previous methods, our method focuses on the constrained MaxEnt
version of the game and also incoporates multimodality via a novel formulation
of an incomplete information with information asymmetry.

###  VI-B Multimodal Planning

There are relatively few works that explore the concept of multimodality
within the context of dynamic games. This idea is explored in [16], but
requires the multimodality to be known a priori and explicitly encoded into
the model. One series of works [13, 14, 27] approach this problem by training
a generative model offline conditioned on a discrete latent variable to learn
the trajectories of other agents. While this approach does take multimodality
into account, it is not done in a game-theoretic context.

The work in this paper is most similar to [24], which also solves a POMDP with
a discrete latent variable. However, in their work, the discrete latent
variable must be prespecified while the multimodality is discovered in this
work. Also, their work only looks at optimality for a single agent while in
our work we focus on solving for generalized Nash equilibria, with the POMDP
being only one piece of the algorithm.

###  VI-C Bayesian Inference and Laplace Approximation

The maximum entropy term transforms the difficulty of each agent’s
optimization problem into that of sampling from the optimal $\pi^{i}$ and
computing the normalization term $Z^{i}$, a challenge shared by many
techniques for Bayesian inference. Some popular techniques for tackling
Bayesian inference include Markov chain Monte Carlo (MCMC) and Variational
Inference (VI) [1, 26], though these methods are usually much slower and are
computationally intractable for planning on real time. We do note however a
series of works [22, 35] which successfully apply variational inference via
sampling-based optimization. Laplace Approximation [5] is an approximation
framework for Bayesian inference by finding a Gaussian approximation to a
probability density function MELQGames can be viewed as applying the Laplace
Approximation to ${\pi}^{i}_{t}$ at each timestep $t$.

##  VII Experiments

In this section, we compare the proposed MMELQGames algorithm against the IBR
and MELQGames algorithms on two examples which illustrate the capabilities of
MMELQGames in recovering a rich set of multi-agent interactions. The reader is
encouraged to view the videos included in the supplementary material which
showcase the behavior of MMELQGames compared to MELQGames and IBR.

Figure 5:  Comparison of realizations of the stochastic policy obtained from
MELQGames (left) and MMELQGames (right). For MMELQGames, the mode $a$ is
sampled using the prior from (47).

Figure 6: MMELQGames for the three agents case, where the algorithm is able to
find both Nash equilibria. The left plot shows the planned mean policies for
each mode. The square denotes the initial position for each agent, with lines
indicating that positions are from the same timestep. The right plot shows
realizations of the stochastic policy. Again, the prior from (47) is used for
sampling the mode $a$.

Overtake Above

Overtake Below

IBR

iLQGames

MMELQGames

Figure 7: Comparison of the trajectories resulting from running IBR (top),
iLQGames (middle) and MMELQGames (bottom) in MPC for the lead (blue) agent.
IBR is used for the rear (green) agent in all cases. We test on the case where
the rear agent tries to overtake above (left) and below (right) the lead
agent. Colored circles are added every fifth timestep to indicate the position
of each agent. Black circles indicating the radius of each agent denote the
timestep where the agents are closest to each other.

###  VII-A Multi-agent collision avoidance

We begin with a simple collision avoidance game between agents with unicycle
dynamics to highlight the multimodality of our algorithm. Each agent’s
objective function composes of a quadratic task and a soft cost for colliding
with other agents. As there is no ego agent in this example, we assume that
the ego agent knows the mode $a$ from the start and choose the prior for $a$
to be of the form (47). The results are shown in Fig. 5. While Mehr et al.
[20] claims that the stochastic policy from MELQGames is able to result in
multimodal behaviors, our results show that this is not the case. Since the
mean control from MELQGames is equivalent to the linear feedback controller
from iLQR, the resulting behavior should also result in a “tube” around the
mean trajectory, which is indeed what we see on the top row of Fig. 5. On the
other hand, the MMELQGames algorithm is able to properly handle the
multimodality of this example and sucessfully find both local Nash equilibria
of the game.

(a) iLQGames

(b) MMELQGames

Figure 8:  Snapshot of iLQGames (left) and MMELQGames (right) at three
timesteps after the rear agent starts turning towards the bottom mode. The ego
agent’s planned trajectory is shown as a solid blue line, with the predicted
trajectories of the non-ego agent shown as a dashed line. iLQGames incorrectly
predicts that the rear agent will overtake from the top due to the algorithm
being stuck in a local minima, while MMELQGames is able to successfully infer
that the mode has changed. For MMELQGames, the different colors indicate the
different modes.

###  VII-B Game Theoretic Autonomous Racing

We next consider a two-agent racing scenario where the lead vehicle has index
$i=1$ and the rear vehicle has index $i=2$. The objective of each agent is to
maximize the difference between its own progress $s^{i}$ and the progress of
the other agent $s^{\neg i}$ (first term) under quadratic control cost (second
term), subject to the following

$\displaystyle\min_{u^{i}}$ $\displaystyle\quad(s^{\neg
i}-s^{i})+\sum_{t=1}^{T-1}\frac{1}{2}{u^{i}_{t}}^{\mathrm{T}}Ru^{i}_{t},$ (51)
s.t. $\displaystyle\quad h^{i}_{\textrm{track}}({\bf X},{\bf U})\leq 0,$ (52)
$\displaystyle\quad\mathbbm{1}_{s^{i}<s^{\neg
i}}h^{i}_{\textrm{collision}}({\bf X})\leq 0,$ (53) $\displaystyle\quad
h^{i}_{\textrm{velocity}}({\bf X})\leq 0.$ (54)

where each vehicle is modeled as a unicycle with linear and angular
accelerations as controls.

To make the problem interesting, the lead vehicle has a lower maximum velocity
than the rear vehicle to allow the rear vehicle the opportunity to overtake.
To maintain the lead, the lead vehicle must block the rear vehicle from
overtaking its position. Furthermore, to more closely model racing in real
life, the collision constraint is asymmetric with the burden of respecting the
constraint placed solely on the rear vehicle. We compare a MPC version of the
IBR, iLQGames and MMELQGames algorithms for the lead vehicle by planning in a
receding horizon fashion. Note that MELQGames is equivalent to iLQGames if the
mean controls are used instead of sampling from the stochastic policy. In all
cases, the rear agent solves for its controls using IBR. The width of the
track means that the rear agent can choose to overtake the lead vehicle by
going either above or below resulting in multimodality. We test both modes in
our experiments, with the results for MMELQGames shown in Fig. 1 and a
comparison of the algorithms shown in Fig. 7.

As expected, IBR is unable to take into account the asymmetric coupling
effects between the agents. Although the solution it does find is a local GNE,
it is one which is disadvantageous for the lead agent and results in the lead
agent being overtaken by the rear agent in both modes. iLQGames is able to
converge to the advantageous local GNE for the first mode and successfully
finish the race ahead of the rear agent. However, the nature of the method
means that it is only able to keep track of one of the two modes, resulting in
the method failing to block the rear agent when the rear agent overtakes via
the bottom. Finally, the multimodal nature of MMELQGames means that it is able
to keep track of both local Nash equilibria at the same time. By using the
history of the rear agent’s control, the lead agent is able to infer whether
rear agent is trying to overtake from the top or the bottom and then execute
the corresponding control.

We also note that since MELQGames is a local method, it is prone to becoming
stuck in local minima. From Fig. 8, even though the rear agent is clearly
trying to overtake via the bottom mode, the warmstart for iLQGames means that
it still predicts the rear agent will overtake from the top. On the other
hand, the multimodality of MMELQGames means that it can keep track of multiple
hypothesis at the same time and hence is able to infer the correct mode using
the algorithm described in Section IV-B and respond accordingly.

##  VIII Conclusion

In this paper, we have proposed a constrained MaxEnt dynamic game formulation
and presented an algorithm that can solve for multiple modes of the
corresponding GNE. We demonstrate its advantages over existing unimodal
algorithms in the examples of multi-agent collision avoidance and autonomous
racing.

While we have explored the use of constraints on the mean control in our
formulation, it may be interesting to look at different ways of including
constraints in the MaxEnt dynamic game formulation such as via chance
constraints or constraints that hold almost-surely.

Finally, though our algorithm identifies multimodal behavior by exploring the
state space, we do not provide any guarantees for how thorough this
exploration is or whether there are additional modes which have not been
discovered. Quantifying this via uncertainty quantification tools such as
Gaussian Processes can provide more structured methods of discovering
different modalities in multi-agent interactions.

## Acknowledgments

## References

  * Andrieu et al. [2003] Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael I Jordan.  An introduction to mcmc for machine learning.  _Machine learning_ , 50(1):5–43, 2003.
  * Birgin and Martínez [2014] Ernesto G Birgin and José Mario Martínez.  _Practical augmented Lagrangian methods for constrained optimization_.  SIAM, 2014.
  * Britzelmeier et al. [2019] Andreas Britzelmeier, Axel Dreves, and Matthias Gerdts.  Numerical solution of potential games arising in the control of cooperative automatic vehicles.  In _2019 Proceedings of the Conference on Control and its Applications_ , pages 38–45. SIAM, 2019.
  * Cleac’h et al. [2019] Simon Le Cleac’h, Mac Schwager, and Zachary Manchester.  Algames: A fast solver for constrained dynamic games.  _arXiv preprint arXiv:1910.09713_ , 2019.
  * Daxberger et al. [2021] Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig.  Laplace redux - effortless bayesian deep learning.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=gDcaUj4Myhn.
  * De Martino and De Martino [2018] Andrea De Martino and Daniele De Martino.  An introduction to the maximum entropy approach and its application to inference problems in biology.  _Heliyon_ , 4(4):e00596, 2018.
  * Di and Lamperski [2019] Bolei Di and Andrew Lamperski.  Newton’s method and differential dynamic programming for unconstrained nonlinear dynamic games.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pages 4073–4078. IEEE, 2019.
  * Di and Lamperski [2020] Bolei Di and Andrew Lamperski.  First-order algorithms for constrained nonlinear dynamic games.  _arXiv preprint arXiv:2001.01826_ , 2020.
  * Evans and Prokopenko [2021] Benjamin Patrick Evans and Mikhail Prokopenko.  A maximum entropy model of bounded rational decision-making with prior beliefs and market feedback.  _Entropy_ , 23(6):669, 2021.
  * Facchinei and Kanzow [2010] Francisco Facchinei and Christian Kanzow.  Generalized nash equilibrium problems.  _Annals of Operations Research_ , 175(1):177–211, 2010.
  * Fonseca-Morales and Hernández-Lerma [2018] Alejandra Fonseca-Morales and Onésimo Hernández-Lerma.  Potential differential games.  _Dynamic Games and Applications_ , 8(2):254–279, 2018.
  * Fridovich-Keil et al. [2020] David Fridovich-Keil, Ellis Ratner, Lasse Peters, Anca D Dragan, and Claire J Tomlin.  Efficient iterative linear-quadratic approximations for nonlinear multi-player general-sum differential games.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 1475–1481. IEEE, 2020.
  * Ivanovic and Pavone [2019] Boris Ivanovic and Marco Pavone.  The trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2375–2384, 2019.
  * Ivanovic et al. [2018] Boris Ivanovic, Edward Schmerling, Karen Leung, and Marco Pavone.  Generative modeling of multimodal multi-human behavior.  In _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 3088–3095. IEEE, 2018.
  * Kim and Yang [2020] Jeongho Kim and Insoon Yang.  Hamilton-jacobi-bellman equations for maximum entropy optimal control.  _arXiv preprint arXiv:2009.13097_ , 2020.
  * Laine et al. [2021] Forrest Laine, David Fridovich-Keil, Chih-Yuan Chiu, and Claire Tomlin.  Multi-hypothesis interactions in game-theoretic motion planning.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 8016–8023. IEEE, 2021.
  * Li and Todorov [2004] Weiwei Li and Emanuel Todorov.  Iterative linear quadratic regulator design for nonlinear biological movement systems.  In _ICINCO (1)_ , pages 222–229. Citeseer, 2004.
  * Maschler et al. [2013] Michael Maschler, Eilon Solan, and Shmuel Zamir.  Game theory (translated from the hebrew by ziv hellman and edited by mike borns).  _Cambridge University Press, Cambridge, pp. xxvi_ , 979:4, 2013.
  * Mayne [1966] David Mayne.  A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems.  _International Journal of Control_ , 3(1):85–95, 1966.
  * Mehr et al. [2021] Negar Mehr, Mingyu Wang, and Mac Schwager.  Maximum-entropy multi-agent dynamic games: Forward and inverse solutions.  _arXiv preprint arXiv:2110.01027_ , 2021.
  * Nocedal and Wright [2006] Jorge Nocedal and Stephen Wright.  _Numerical optimization_.  Springer Science & Business Media, 2006.
  * Okada and Taniguchi [2020] Masashi Okada and Tadahiro Taniguchi.  Variational inference mpc for bayesian model-based reinforcement learning.  In _Conference on Robot Learning_ , pages 258–272. PMLR, 2020.
  * Papadimitriou and Tsitsiklis [1987] Christos H Papadimitriou and John N Tsitsiklis.  The complexity of markov decision processes.  _Mathematics of operations research_ , 12(3):441–450, 1987.
  * Qiu et al. [2020] Dicong Qiu, Yibiao Zhao, and Chris L Baker.  Latent belief space motion planning under cost, dynamics, and intent uncertainty.  In _Proceedings of Robotics: Science and Systems (RSS)_ , 2020.
  * Ruszczynski [2011] Andrzej Ruszczynski.  _Nonlinear optimization_.  Princeton university press, 2011.
  * Salimans et al. [2015] Tim Salimans, Diederik Kingma, and Max Welling.  Markov chain monte carlo and variational inference: Bridging the gap.  In _International Conference on Machine Learning_ , pages 1218–1226. PMLR, 2015.
  * Schmerling et al. [2018] Edward Schmerling, Karen Leung, Wolf Vollprecht, and Marco Pavone.  Multimodal probabilistic model-based planning for human-robot interaction.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 3399–3406. IEEE, 2018.
  * Schwarting et al. [2021] Wilko Schwarting, Alyssa Pierson, Sertac Karaman, and Daniela Rus.  Stochastic dynamic games in belief space.  _IEEE Transactions on Robotics_ , 2021.
  * Simon [1972] Herbert A Simon.  Theories of bounded rationality.  _Decision and organization_ , 1(1):161–176, 1972\.
  * So et al. [2021] Oswin So, Ziyi Wang, and Evangelos A Theodorou.  Maximum entropy differential dynamic programming.  _arXiv preprint arXiv:2110.06451_ , 2021.
  * Spica et al. [2020] Riccardo Spica, Eric Cristofalo, Zijian Wang, Eduardo Montijano, and Mac Schwager.  A real-time game theoretic planner for autonomous two-player drone racing.  _IEEE Transactions on Robotics_ , 36(5):1389–1403, 2020.
  * Wang et al. [2019] Zijian Wang, Riccardo Spica, and Mac Schwager.  Game theoretic motion planning for multi-robot racing.  In _Distributed Autonomous Robotic Systems_ , pages 225–238. Springer, 2019.
  * Wang et al. [2020] Zijian Wang, Tim Taubner, and Mac Schwager.  Multi-agent sensitivity enhanced iterative best response: A real-time game theoretic planner for drone racing in 3d environments.  _Robotics and Autonomous Systems_ , 125:103410, 2020.
  * Wang et al. [2021a] Ziyi Wang, Oswin So, Jason Gibson, Bogdan Vlahov, Manan Gandhi, Guan-Horng Liu, and Evangelos Theodorou.  Variational Inference MPC using Tsallis Divergence.  In _Proceedings of Robotics: Science and Systems_ , Virtual, July 2021a.  doi: 10.15607/RSS.2021.XVII.073.
  * Wang et al. [2021b] Ziyi Wang, Oswin So, Jason Gibson, Bogdan Vlahov, Manan S Gandhi, Guan-Horng Liu, and Evangelos A Theodorou.  Variational inference mpc using tsallis divergence.  In _Proceedings of Robotics: Science and Systems_ , Virtual, July 2021b.  doi: 10.15607/RSS.2021.XVII.073.  URL http://www.roboticsproceedings.org/rss17/p073.html.
  * Williams et al. [2017] Grady Williams, Brian Goldfain, Paul Drews, James M Rehg, and Evangelos A Theodorou.  Autonomous racing with autorally vehicles and differential games.  _arXiv preprint arXiv:1707.04540_ , 2017.
  * Ziebart et al. [2008] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al.  Maximum entropy inverse reinforcement learning.  2008\.

##  Appendix A Expression for Partial Derivatives of $Q^{i}$

Let $Q^{i}$ denote the terms inside the expectation in Bellman’s equation
(11):

$Q^{i}({\bm{x}},{\bm{u}})\coloneqq
l^{i}({\bm{x}},{\bm{u}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}})).$ (A.55)

Suppose that the value function at the next timestep ${V^{i}}^{\prime}$ is
quadratic with form

${V^{i}}^{\prime}({\bm{x}})=(\bar{V}^{i})^{\prime}+(V^{i})^{\prime}_{x}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}(V^{i})^{\prime}_{xx}\delta{\bm{x}}$
(A.56)

Using a quadratic approximation of the costs and linear approximation of the
dynamics (15) then yields

$\displaystyle Q^{i}({\bm{x}},{\bm{u}})$ $\displaystyle\approx
l^{i}(\bar{{\bm{x}}},\bar{{\bm{u}}})+\begin{bmatrix}l^{i}_{x}\\\
l^{i}_{u}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}+\frac{1}{2}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}l^{i}_{xx}&l^{i}_{xu}\\\
l^{i}_{ux}&l^{i}_{uu}\end{bmatrix}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}$ (A.57)
$\displaystyle\quad+\Big{(}f(\bar{{\bm{x}}},\bar{{\bm{u}}})+f_{x}\delta{\bm{x}}+f_{u}\delta{\bm{u}}\Big{)}^{\mathrm{T}}\Big{(}(\bar{V}^{i})^{\prime}+(V^{i})^{\prime}_{x}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}(V^{i})^{\prime}_{xx}\delta{\bm{x}}\Big{)}\Big{(}f(\bar{{\bm{x}}},\bar{{\bm{u}}})+f_{x}\delta{\bm{x}}+f_{u}\delta{\bm{u}}\Big{)}.$
(A.58)

Expanding and collecting terms then results in

$\displaystyle\begin{aligned}
Q^{i}({\bm{x}},{\bm{u}})&\approx\bar{V}^{i}+\delta Q^{i},\\\
\bar{V}^{i}&\coloneqq
l^{i}(\bar{{\bm{x}}},\bar{{\bm{u}}})+(\bar{V}^{i})^{\prime}(f({\bm{x}},{\bm{u}})),\end{aligned}$
(A.59) $\displaystyle\delta Q^{i}\coloneqq\begin{bmatrix}Q^{i}_{x}\\\
Q^{i}_{u}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}+\frac{1}{2}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}^{\mathrm{T}}\begin{bmatrix}Q^{i}_{xx}&Q^{i}_{xu}\\\
Q^{i}_{ux}&Q^{i}_{uu}\end{bmatrix}\begin{bmatrix}\delta{\bm{x}}\\\
\delta{\bm{u}}\end{bmatrix}.$ (A.60)

where the partial derivatives of $Q^{i}$ are as follows:

$\displaystyle Q^{i}_{x}$
$\displaystyle=l^{i}_{x}+f_{x}^{\mathrm{T}}(V^{i})^{\prime}_{x}$ (A.61)
$\displaystyle Q^{i}_{u}$
$\displaystyle=l^{i}_{u}+f_{u}^{\mathrm{T}}(V^{i})^{\prime}_{x}$ (A.62)
$\displaystyle Q^{i}_{xx}$
$\displaystyle=l^{i}_{xx}+f_{x}^{\mathrm{T}}(V^{i})^{\prime}_{xx}f_{x}$ (A.63)
$\displaystyle Q^{i}_{ux}$
$\displaystyle=l^{i}_{ux}+f_{u}^{\mathrm{T}}(V^{i})^{\prime}_{xx}f_{x}$ (A.64)
$\displaystyle Q^{i}_{uu}$
$\displaystyle=l^{i}_{uu}+f_{u}^{\mathrm{T}}(V^{i})^{\prime}_{xx}f_{u}$ (A.65)

##  Appendix B Proof of Lemma 1

We restate the theorem below for convenience.

######  Lemma 1 (Optimal MELQGames Policy).

The optimal policy ${\pi}^{i*}$ which solves (19) for each agent $i$ has the
form

$\pi^{i*}={Z^{i}}^{-1}\exp\Big{(}-\frac{\alpha}{2}(\delta{u^{i}}-\delta{u^{i*}})^{\mathrm{T}}Q_{u^{i}u^{i}}^{i}(\delta{u^{i}}-\delta{u^{i*}})\Big{)}$
(B.66)

where ${\delta{\bm{u}}^{*}}$ is the solution to the following system of
equations

$0=\hat{Q}_{uu}{\delta{\bm{u}}^{*}}+Q_{ux}\delta{\bm{x}}+Q_{u}=k+K\delta{\bm{x}}$
(B.67)

and the matrix $\hat{Q}_{uu}\in\mathbb{R}^{n_{\bm{u}}\times n_{\bm{u}}}$ is
obtained by vertically stacking the row vectors $Q^{i}_{u^{i}{\bm{u}}}$ for
each $i\in\\{1,\dots,N\\}$:

$\hat{Q}_{uu}\coloneqq\begin{bmatrix}Q^{1}_{u^{1}{\bm{u}}}\\\ \vdots\\\
Q^{N}_{u^{N}{\bm{u}}}\end{bmatrix}$ (B.68)

###### Proof.

The optimal policy for agent $i$ in (19) is the Gibbs distribution

$\pi^{i*}(\delta{u^{i}})\propto\exp\left(-\frac{1}{\alpha}\left[\Big{(}Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\mathbb{E}{\left[\delta{{\bm{u}}^{\neg
i}}\right]}\Big{)}^{\mathrm{T}}\delta{u^{i}}+\frac{1}{2}\delta{u^{i}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i}}\right]\right).$
(B.69)

Since the expression inside the exponential function is quadratic in
$\delta{u^{i}}$ with the negative definite quadratic term
$-\frac{1}{2\alpha}{Q_{u^{i}u^{i}}^{i}}$, the optimal policy $\pi^{i*}$ is
multivariate Gaussian with covariance matrix
$\Sigma=\alpha({Q_{u^{i}u^{i}}^{i}})^{-1}$. To find the mean of $\pi^{i*}$, we
complete the square to obtain

$\Big{(}Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\mathbb{E}{\left[\delta{{\bm{u}}^{\neg
i}}\right]}\Big{)}^{\mathrm{T}}\delta{u^{i}}+\frac{1}{2}\delta{u^{i}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}=\frac{1}{2}(\delta{u^{i}}-\delta{u^{i*}})^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}(\delta{u^{i}}-\delta{u^{i*}})-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}$
(B.70)

where the mean $\delta{u^{i*}}=\mathbb{E}{\left[\delta{u^{i}}\right]}$ is
defined as

$\delta{u^{i*}}\coloneqq-({Q_{u^{i}u^{i}}^{i}})^{-1}(Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}})$ (B.71)

where we have used $\delta{{\bm{u}}^{\neg
i*}}\coloneqq\mathbb{E}{\left[\delta{{\bm{u}}^{\neg i}}\right]}$ to denote the
mean control of the other agents. If $\delta{{\bm{u}}^{\neg i*}}$ were known
(ex. in the IBR case where $\delta{{\bm{u}}^{\neg i*}}$ is held fixed), then
$\delta{u^{i*}}$ can be solved from (B.71) alone. However, in this case,
$\delta{{\bm{u}}^{\neg i*}}$ is not known. However, by rearranging (B.71) we
obtain

$\displaystyle 0$
$\displaystyle={Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}+Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}}$ (B.72)
$\displaystyle=Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q^{i}_{u^{i}{\bm{u}}}{\delta{\bm{u}}^{*}},$
(B.73)

which provides $n_{u^{i}}$ equations in the unknown variable
${\delta{\bm{u}}^{*}}\in\mathbb{R}^{n_{{\bm{u}}}}$. Hence, by considering
(B.73) for all agents, we obtain the following linear equation for
${\delta{\bm{u}}^{*}}$:

$\hat{Q}_{uu}{\delta{\bm{u}}^{*}}+Q_{ux}\delta{\bm{x}}+Q_{u}=0$ (B.74)

with $\hat{Q}_{uu}$ defined as the stacked matrix of $Q_{u^{i}{\bm{u}}}$ for
all agents:

$\hat{Q}_{uu}\coloneqq\begin{bmatrix}Q^{1}_{u^{1}{\bm{u}}}\\\ \vdots\\\
Q^{N}_{u^{N}{\bm{u}}}\end{bmatrix}$ (B.75)

∎

##  Appendix C Proof of Lemma 2

To simplify the proof, we first begin with the following technical lemma.

######  Lemma 5.

Suppose that ${\delta{\bm{u}}^{*}}$ satisfies (21). Then,

$\displaystyle\Big{(}Q_{u^{\neg i}}^{i}+Q_{u^{\neg
i}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg
i*}}-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}=\Big{(}{Q_{{\bm{u}}}^{i}}+Q_{{\bm{u}}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}{\delta{\bm{u}}^{*}}+\frac{1}{2}{\delta{\bm{u}}^{*}}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\delta{\bm{u}}^{*}}$
(C.76)

###### Proof.

Since $\delta u$ satisfies (21), it must thus satisfy (B.72). Hence,

$-{Q_{u^{i}u^{i}}^{i}}\delta{u^{i}}=Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}}$ (C.77)

Splitting $-\frac{1}{2}$ into $\frac{1}{2}-1$, using the above identity then
simplifying:

$\displaystyle\phantom{{}={}}\Big{(}Q_{u^{\neg i}}^{i}+Q_{u^{\neg
i}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg
i*}}-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}$
(C.78) $\displaystyle=\Big{(}Q_{u^{\neg i}}^{i}+Q_{u^{\neg
i}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}-\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i}}$
(C.79) $\displaystyle=\Big{(}Q_{u^{\neg i}}^{i}+Q_{u^{\neg
i}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}+\delta{u^{i*}}^{\mathrm{T}}(Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}})$ (C.80)
$\displaystyle=\Big{(}{Q_{{\bm{u}}}^{i}}+Q_{{\bm{u}}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}{\delta{\bm{u}}^{*}}+\frac{1}{2}{\delta{\bm{u}}^{*}}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\delta{\bm{u}}^{*}}$
(C.81)

∎

We now restate Lemma 2 below for convenience.

######  Lemma 2 (MELQGames Value Function Update).

Suppose the infimum in the Bellman equation (11) is solved with policy
$\pi^{i*}$ with mean ${\delta{\bm{u}}^{*}}={\bm{k}}+{\bf K}\delta{\bm{x}}$
according to Lemma 1. Then, the value function using $\delta\tilde{{\bm{u}}}$
for agent $i$ has the form

$\displaystyle V^{i}({\bm{x}})$
$\displaystyle=\mathbb{E}_{{\delta{\bm{u}}\sim\tilde{\pi}}}{\left[l^{i}({\bm{x}},{\bm{u}})+{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}})\right]}-\alpha
H[\tilde{\pi}^{i}]$ (C.82)
$\displaystyle=\Big{(}V^{i}+V_{H}^{i}\Big{)}+{V_{x}^{i}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}V_{xx}^{i}\delta{\bm{x}},$
(C.83)

where the terms $V^{i}$, $V_{H}^{i}$, $V_{x}^{i}$ and $V_{xx}^{i}$ have the
form

$\displaystyle V^{i}$
$\displaystyle=\bar{V}^{i}+Q_{u}^{i}{\bm{k}}+\frac{1}{2}{\bm{k}}^{\mathrm{T}}Q_{uu}^{i}{\bm{k}}$
(C.84) $\displaystyle\begin{split}V_{H}^{i}&=\frac{\alpha}{2}\Big{(}\log\lvert
Q_{u^{i}u^{i}}^{i}\rvert-n_{u}\log(2\pi\alpha)\Big{)}\\\
&\quad+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\end{split}$
(C.85) $\displaystyle V_{x}^{i}$ $\displaystyle=Q_{x}^{i}+{\bf
K}^{\mathrm{T}}Q_{uu}^{i}{\bm{k}}+{\bf
K}^{\mathrm{T}}Q_{u}^{i}+Q_{xu}^{i}{\bm{k}}$ (C.86) $\displaystyle V_{xx}^{i}$
$\displaystyle=Q_{xx}^{i}+{\bf K}^{\mathrm{T}}Q_{uu}^{i}{\bf K}+{\bf
K}^{\mathrm{T}}Q_{ux}^{i}+Q_{xu}^{i}{\bf K}$ (C.87)

###### Proof.

Let $\mathcal{I}^{i}$ denote the following integral.

$\mathcal{I}^{i}\coloneqq\int\exp\left(-\frac{1}{\alpha}\left[Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\mathbb{E}{\left[\delta{{\bm{u}}^{\neg
i}}\right]}\Big{)}^{\mathrm{T}}\delta{u^{i}}\\\
+\frac{1}{2}\delta{u^{i}}^{\mathrm{T}}Q_{u^{i}u^{i}}^{i}\delta{u^{i}}\right]\right)\mathop{}\mathrm{d}\delta{u^{i}}$
(C.88)

Then, completing the square as in (B.70) and simplifying, we obtain

$\displaystyle\mathcal{I}^{i}$
$\displaystyle=\exp\left(-\frac{1}{\alpha}\left[-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}\right]\right)\int\exp\left(-\frac{1}{\alpha}\left[\frac{1}{2}(\delta{u^{i}}-\delta{u^{i*}})^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}(\delta{u^{i}}-\delta{u^{i*}})\right]\right)\mathop{}\mathrm{d}\delta{u^{i}}$
(C.89)
$\displaystyle=\exp\left(-\frac{1}{\alpha}\left[-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}\right]\right)\Big{(}2\pi\Big{)}^{\frac{n_{u}}{2}}\,\Big{(}\left\lvert\alpha({Q_{u^{i}u^{i}}^{i}})^{-1})\right\rvert\Big{)}^{\frac{1}{2}}$
(C.90)
$\displaystyle=\exp\left(-\frac{1}{\alpha}\left[-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}\right]\right)\frac{\Big{(}2\pi\alpha\Big{)}^{\frac{n_{u}}{2}}}{\left\lvert{Q_{u^{i}u^{i}}^{i}}\right\rvert^{\frac{1}{2}}}$
(C.91)
$\displaystyle=\exp\left(-\frac{1}{\alpha}\left[-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}+\frac{\alpha}{2}\Big{(}\ln\lvert{Q_{u^{i}u^{i}}^{i}}\rvert-
n_{u^{i}}\ln(2\pi\alpha)\Big{)}\right]\right)$ (C.92)

Then, the partition function $Z^{i}$ (13) takes the form

$\displaystyle Z^{i}$
$\displaystyle=\int\exp\Big{(}-\frac{1}{\alpha}\mathbb{E}_{{{{\bm{u}}}^{\neg
i}}}{\left[{V^{i}}^{\prime}(f({\bm{x}},{\bm{u}}))+l^{i}({\bm{x}},{\bm{u}})\right]}\Big{)}\mathop{}\mathrm{d}u^{i}$
(C.93)
$\displaystyle\begin{split}&=\exp\bigg{(}-\frac{1}{\alpha}\Big{[}\bar{V}^{i}+{Q^{i}_{{\bm{x}}}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}Q^{i}_{{\bm{x}}{\bm{x}}}\delta{\bm{x}}+\Big{(}Q^{i}_{{{\bm{u}}}^{\neg
i}}+Q^{i}_{{{\bm{u}}}^{\neg
i}{\bm{x}}}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}}\\\
&\qquad\qquad+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\Big{]}\bigg{)}\\\
&\quad\int\exp\Big{(}-\frac{1}{\alpha}\left[\Big{(}Q_{u^{i}}^{i}+Q_{u^{i}x}^{i}\delta{\bm{x}}+Q_{u^{i}u^{\neg
i}}^{i}\mathbb{E}{\left[\delta{{\bm{u}}^{\neg
i}}\right]}\Big{)}^{\mathrm{T}}\delta{u^{i}}+\frac{1}{2}\delta{u^{i}}^{\mathrm{T}}Q_{u^{i}u^{i}}^{i}\delta{u^{i}}\right]\Big{)}\mathop{}\mathrm{d}\delta{u^{i}}\\\
\end{split}$ (C.94)
$\displaystyle\begin{split}&=\exp\bigg{(}-\frac{1}{\alpha}\Big{[}\bar{V}^{i}+{Q^{i}_{{\bm{x}}}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}Q^{i}_{{\bm{x}}{\bm{x}}}\delta{\bm{x}}+\Big{(}Q^{i}_{{{\bm{u}}}^{\neg
i}}+Q^{i}_{{{\bm{u}}}^{\neg
i}{\bm{x}}}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}}\\\
&\qquad\qquad+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\Big{]}\bigg{)}\;\mathcal{I}\end{split}$
(C.95) $\displaystyle=\exp\left(-\frac{1}{\alpha}V^{i}({\bm{x}})\right)$
(C.96)

where the trace term comes from taking the expectation of the quadratic term
in $\delta{{\bm{u}}^{\neg i}}$ and

$\begin{split}V^{i}({\bm{x}})&=(\bar{V}^{i})^{\prime}+{Q^{i}_{{\bm{x}}}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}Q^{i}_{{\bm{x}}{\bm{x}}}\delta{\bm{x}}+\Big{(}Q^{i}_{{{\bm{u}}}^{\neg
i}}+Q^{i}_{{{\bm{u}}}^{\neg
i}{\bm{x}}}\delta{\bm{x}}\Big{)}^{\mathrm{T}}\delta{{\bm{u}}^{\neg
i*}}+\frac{1}{2}\delta{{\bm{u}}^{\neg i*}}^{\mathrm{T}}Q_{u^{\neg i}u^{\neg
i}}^{i}\delta{{\bm{u}}^{\neg i*}}\\\
&\qquad-\frac{1}{2}\delta{u^{i*}}^{\mathrm{T}}{Q_{u^{i}u^{i}}^{i}}\delta{u^{i*}}+\frac{\alpha}{2}\Big{(}\ln\lvert{Q_{u^{i}u^{i}}^{i}}\rvert-
n_{u^{i}}\ln(2\pi\alpha)\Big{)}+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\end{split}$
(C.97)

Applying Lemma 5, using the definition of ${\delta{\bm{u}}^{*}}$ and
collecting terms then yields

$\displaystyle\begin{split}V^{i}({\bm{x}})&=(\bar{V}^{i})^{\prime}+{Q^{i}_{{\bm{x}}}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}Q^{i}_{{\bm{x}}{\bm{x}}}\delta{\bm{x}}+\Big{(}{Q_{{\bm{u}}}^{i}}+Q_{{\bm{u}}{\bm{x}}}^{i}\delta{\bm{x}}\Big{)}^{\mathrm{T}}{\delta{\bm{u}}^{*}}\\\
&\qquad+\frac{1}{2}{\delta{\bm{u}}^{*}}^{\mathrm{T}}Q_{{\bm{u}}{\bm{u}}}^{i}{\delta{\bm{u}}^{*}}+\frac{\alpha}{2}\Big{(}\ln\lvert{Q_{u^{i}u^{i}}^{i}}\rvert-
n_{u^{i}}\ln(2\pi\alpha)\Big{)}+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\end{split}$
(C.98)
$\displaystyle=\Big{(}V^{i}+V_{H}^{i}\Big{)}+{V_{x}^{i}}^{\mathrm{T}}\delta{\bm{x}}+\frac{1}{2}\delta{\bm{x}}^{\mathrm{T}}V_{xx}^{i}\delta{\bm{x}}$
(C.99)

where

$\displaystyle V^{i}$
$\displaystyle=\bar{V}^{i}+Q_{u}^{i}{\bm{k}}+\frac{1}{2}{\bm{k}}^{\mathrm{T}}Q_{uu}^{i}{\bm{k}}$
(C.100)
$\displaystyle\begin{split}V_{H}^{i}&=\frac{\alpha}{2}\Big{(}\log\lvert
Q_{u^{i}u^{i}}^{i}\rvert-n_{u}\log(2\pi\alpha)\Big{)}\\\
&\quad+\alpha\sum_{j=1,j\not=i}^{N}\mathrm{tr}\left[(Q^{j}_{u^{j},u^{j}})^{-1}Q^{i}_{u^{j},u^{j}}\right]\end{split}$
(C.101) $\displaystyle V_{x}^{i}$ $\displaystyle=Q_{x}^{i}+{\bf
K}^{\mathrm{T}}Q_{uu}^{i}{\bm{k}}+{\bf
K}^{\mathrm{T}}Q_{u}^{i}+Q_{xu}^{i}{\bm{k}}$ (C.102) $\displaystyle
V_{xx}^{i}$ $\displaystyle=Q_{xx}^{i}+{\bf K}^{\mathrm{T}}Q_{uu}^{i}{\bf
K}+{\bf K}^{\mathrm{T}}Q_{ux}^{i}+Q_{xu}^{i}{\bf K}$ (C.103)

∎

##  Appendix D Proof of Lemma 3

We restate Lemma 3 below for convenience.

######  Lemma 3.

Suppose that the augmented Lagrangian MELQGames converges to a tuple
$(\pi^{*},\lambda^{i}_{j},\rho)$ for some $\rho>0$ which satisfies dual
feasibility of $\lambda$, LICQ and SOSC. Then, $\pi^{*}$ is a GNE for (5).

###### Proof.

Since the solution satisfies LICQ, SOSC and $\lambda>0$, each ${\pi}^{i*}$ is
a local minima for its corresponding constrained optimal control problem (5).
Thus, there does not exist any feasible control $\pi\in\Pi({\pi}^{\neg i*})$
within a neighborhood of ${\pi}^{i*}$ that can achieve a lower cost. Hence,
$\pi^{*}$ satisfies (9) and is a GNE. ∎

##  Appendix E Proof of Lemma 4

Before proving Lemma 4, we first introduce the following theorem from Maschler
et al. [18] which presents a sufficient condition for an event $A$ to be
common belief among the players at a particular state of the world $\omega$:

######  Theorem 1.

Let $N$ denote the number of agents in the game, $\omega\in Y$ be a state of
the world and $A\subseteq Y$ be an event satisfying the following two
conditions:

$\displaystyle p_{i}(A|\omega)$ $\displaystyle=1,\quad\forall
i\in\\{1,\dots,N\\}$ (E.104) $\displaystyle p_{i}(A|\omega^{\prime})$
$\displaystyle=1,\quad\forall i\in\\{1,\dots,N\\},\;\forall\omega^{\prime}\in
A$ (E.105)

Then, $A$ is common belief among the agents at $\omega$.

Using Theorem 1, we can now prove (4), which we restate below for convenience.

######  Lemma 4.

Let $E=\\{\omega_{a,s}\\}_{a=1}^{A}$ denote the event that the ego agent knows
the correct mode with probability 1. Then, for all $i\not=1$, $\omega\in
B_{i}E$, i.e. all non-ego agents believe that the ego agent knows the mode
perfectly. Furthermore, it is common belief that $B_{i}E_{a}$ for all
$i\not=1$. In particular, the ego agent (correctly) believes that all non-ego
agents (incorrectly) believes that it knows the correct mode.

###### Proof.

First, note that at $\omega\in E$, all agents, including the ego agent, know
the true mode. Using the definition of the belief operator $B_{i}$ (38), we
have that for $i\not=1$:

$B_{i}E=\\{\omega\in Y|p_{i}(E|\omega)=1\\}=Y.$ (E.106)

In other words, non-ego agent $i$ believes that $E$ will attains no matter
what the true world state $\omega_{*}$ is. Since $p_{i}(Y|\omega)=1$ for any
$\omega\in Y$, $B_{i}E=Y$ is thus common belief among the agents at all world
states. Hence, by the definition of common belief, we have that

$B_{1}B_{i}E=B_{1}Y=Y$ (E.107)

i.e., the ego agent believes that the non-ego agents believe it knows the true
mode. On the other hand, we have that

$\displaystyle B_{1}E$ $\displaystyle=\\{\omega\in Y|p_{1}(E|\omega)=1\\}=E,$
(E.108) $\displaystyle B_{1}E^{\complement}$ $\displaystyle=\\{\omega\in
Y|p_{1}(E^{\complement}|\omega)=1\\}=E^{\complement}.$ (E.109)

where $E^{\complement}$ denotes the complement of $E$ in $Y$. In other words,
when $\omega\in E^{\complement}$, the ego agent (correctly) believes that it
does not know the true mode while simultaneously knowing that the non-ego
agents (incorrectly) believe that it knows the true mode. ∎

  *[MaxEnt]: Maximum Entropy
  *[MELQGames]: Maximum Entropy Linear Quadratic GAMES
  *[MMELQGames]: Multimodal Maximum Entropy Linear Quadratic GAMES
  *[GNEP]: Generalized Nash Equilibrium Problem
  *[iLQR]: iterative Linear Quadratic Regulator
  *[DDP]: Differential Dynamic Programming
  *[LICQ]: Linear Independent Constraint Qualification
  *[SOSC]: Second-order Sufficient Optimality Condition
  *[GNE]: Generalized Nash Equilibrium
  *[POMDP]: Partially Observable Markov Decision Process
  *[IBR]: Iterative Best Response
  *[MCMC]: Markov chain Monte Carlo
  *[VI]: Variational Inference