text:
\section{Introduction}

One of the important ideas in the development of algorithms for multiagent
systems (MASs) is the identification of compressed representations
of the information that is relevant for an agent~\cite{Becker03AAMAS,Becker04AAMAS,Varakantham09ICAPS,Petrik09JAIR,Witwicki10AAMAS,Witwicki10ICAPS,Witwicki11AAMAS,Velagapudi11AAMAS,Witwicki11PhD,Witwicki12AAMAS,Oliehoek12AAAI_IBA}.
For instance, when a cook and a waiter collaborate, the waiter might
not need to know all details of how the cook prepares the food; it
may be sufficient if it has an understanding of the time that it will
take.

In this paper we further investigate so-called \emph{influence-based
abstractions, }which aim at decomposing structured MASs into a set
of smaller interacting problems~\cite{Oliehoek12AAAI_IBA}. In particular,
we describe the concept of \emph{influence-based abstraction (IBA)},
which facilitates the abstraction of latent state variables without
sacrificing reward (task performance), in detail. It constructs a
smaller, local model for one of the agents given the policies of the
other agents, which can subsequently be used to compute a best response.
IBA consists of two steps: first, we compute a so-called \emph{influence
point\textemdash }a more abstract representation of how the agents
local problem is affected by other agents and external (i.e., non-local)
parts of the problem\textemdash , second, this influence is used to
construct the smaller \emph{influence-augmented local model (IALM). }

IBA does not only give a new perspective on best-response computations
themselves, but also forms the basis of \emph{influence search }\cite{Becker03AAMAS,Witwicki10ICAPS,Witwicki12AAMAS,Bazinin18GCAI},
which can provide significant speedup for multiagent planning by searching
the space of \emph{joint influences}, which can be much smaller than
the space of joint policies. It also can serve as the basis of providing
guarantees on the quality of heuristic solutions, by considering \emph{optimistic
}influences \cite{Oliehoek15IJCAI}, and form an inspiration for neural
network architectures in deep reinforcement learning, that compute
approximate versions of influence that can improve learning, both
in terms of speed as performance prove a stronger \cite{Suau19ALA}.

This document gives a formal definition of influence that can be used
to perform IBA for general factored partially observable stochastic
games (fPOSGs)~\cite{Hansen04AAAI,Boutilier99JAIR}, and proves that
an IALM constructed using this definition of influence in fact allows
to compute an \emph{exact} best-response. In other words, that this
description of influence is a \emph{sufficient statistic} of the policy
of the other agents in order to predict the optimal value. It extends
our previous paper \cite{Oliehoek12AAAI_IBA} in the following ways:
\begin{enumerate}
\item it provides a complete proof of the claimed exactness of IBA;
\item it elaborates on a number of technical subtleties, such as dealing
with multiple sources of influence, and specifying initial beliefs
in the IALM;
\item it provides an extension of IBA and corresponding proofs to fPOSGs
with intra-stage dependencies, which are critical for the expressiveness
of the formalism (cf. \sect\ref{sec:IBA:def-of-influence:links-sources-destinations});
\item it provides additional illustration and explanation, making the concept
of IBA more accessible.
\end{enumerate}
Additionally, we make a simple (but novel in the context of IBA) observation:
the presence of other agents can be seen as a generalization of single
agent settings, which directly implies that \emph{our formulation
of IBA also provides a sufficient statistic for decision making under
abstraction for a single agent}. While there is a multitude of performance
loss bounds available for abstractions, e.g.\ see \cite{Dearden97AIJ,DeanGL97ModelReductionApproxOptimal,Givan03AIJ,Iyengar05MOR,Li06ISAIM,Petrik14NIPS,Abel16ICML},
these are usually based on\emph{ }assumed\emph{ }quality bounds on
the transition probabilities and rewards of the abstracted model.
In contrast, our work here shows how an abstracted model can preserve
exact transition and reward predictions, by `remembering' appropriate
elements of the local history. In the words of McCallum \cite{McCallum95PhD},
we detail an approach to \emph{perfectly }``uncover {[}...{]} hidden
state'' in abstractions for a large class of structured problems.

As such, the contributions of this paper are of a theoretical nature:
it provides a principled understanding of lossless abstractions in
structured (multiagent) decision problems, it formalizes this, and
extends the scope of applicability. The main technical result is the
proof sufficiency of IBA given in \prettyref{sec:Sufficiency}. The
proof is not only a validation of the theory, it also serves a practical
purpose: it isolates the core technical property that needs to hold
for sufficiency, thus providing 1) insight into \emph{how }abstraction
of state latent factors affects value, 2) a derivation that can be
used to obtain a simplification of influence in simpler cases, and
3) a recipe of how to prove similar results more complex settings.

This paper is organized as follows: First, \prettyref{sec:background}
provides the necessary background by introducing single and multiagent
models for decision making. \prettyref{sec:LFMs-and-best-responses}
introduces the concept of computing best responses (using global value
functions) to the policies of other agents and the concept of `local
form models' which formalizes a desired abstraction for an agent.
Next, in \prettyref{sec:IBA}, we bring these concepts together: we
show how an agent can locally compute a best-response (compute a local
value function) provided it is given an influence point. \prettyref{sec:IBA-with-IS-deps}
extends this description to problems with intra-stage dependencies.
\prettyref{sec:Sufficiency} then presents the main proof of sufficiency
of our influence points, i.e., it shows that they are sufficient to
predict the best-response value without any loss in value. Finally,
\prettyref{sec:conclusions} concludes.

~

\section{Background}

\label{sec:background} Here we concisely provide background on some
of the (both single- and multi-agent) models that we use. The main
purpose is to introduce the notation formally. For an extensive introduction
to \emph{partially observable Markov decision processes (POMDPs)}
we refer to \cite{Kaelbling98AI,Spaan12RLBook}, for an introduction
to multiagent variants see \cite{Seuken08JAAMAS,Oliehoek12RLBook,Oliehoek16Book}.

\subsection{Single-Agent Models: POMDPs }

Partially observable Markov decision processes, or POMDPs, provide
a formal framework for the interaction of an agent with a stochastic,
partially observable environment. That is, it provides an agent with
the capabilities to reason about both action uncertainty, as well
as state uncertainty.

\subsubsection{Model}

A POMDP is a discrete time model, in which the agent selects an action
at every time step or \emph{stage. }It extends the regular \emph{Markov
decision process (MDP) }\cite{Puterman94} to settings in which the
state of the environment cannot be observed.\emph{ }It can be formally
defined as follows.

\begin{definition}[POMDP]\label{def:POMDP}

A \emph{partially observable Markov decision process (POMDP) }is defined
as a tuple $\mathcal{M}^{POMDP}=\left\langle \sS,\aAS{},T,R,\oAS{},O,h,{{b^{0}}}\right\rangle $
with the following components:
\begin{itemize}
\item $\sS$ is a (finite) set of states;
\item $\aAS{}$ is the (finite) set of actions;
\item $T$ is the transition probability function, that specifies $T(s,a,s')=\Pr(s'|s,a)$,
the probability of a next state $s'$ given a current state $s$ and
action $\aA{}$;
\item $R$ is the immediate reward function $R:\sS\times\jaS\times\sS\rightarrow\real$.
With $R(s,\aA{},s')$ we denote the reward specified for a particular
transition $s,a,s'$;
\item $\oAS{}$ is the set of observations;
\item $O$ is the observation probability function, which specifies $O(\aAT{}t,\sT{t+1},\oAT{}{t+1})=\Pr(\oA{}|\aA{},s')$,
the probability of a particular observation $\oA{}$ after $\aA{}$
and resulting state $s'$;
\item $h$ is the horizon of the problem as mentioned above;
\item ${b^{0}}\in\PrS(\mathcal{S})$, is the initial state distribution at time
$t=0$.\footnote{$\PrS(\cdot)$ denotes the set of probability distributions over $(\cdot)$.}
\end{itemize}
\end{definition}

In many cases, the set of states is huge, and states can be thought
of as composed of values assigned to different variables:

\begin{definition}[Factored POMDP]\label{def:fPOMDP}When the state
space is spanned by a set of state variables, or \emph{factors}, we
call the problem a \emph{factored POMDP} \emph{(fPOMDP).}\end{definition}

The merit of such a factored POMDP is that, by making the structure
of the problem (i.e., how different factors influence each other)
explicit, the model can be much more compact. In particular, the initial
state distribution can be compactly represented as a \emph{Bayesian
network}~\cite{Pearl88,Bishop06book,KollerFriedman09}, and the transition
and reward model can be specified compactly using a \emph{two-stage
dynamic Bayesian network (2DBN)}~\cite{Boutilier99JAIR}, and a similar
approach can be taken for the observation model~\cite{Poupart05PHD}.
(An example of a 2DBN will be discussed in Fig.~\ref{fig:house-dbn}
\vpageref{fig:house-dbn}.)

\subsubsection{Beliefs}

In contrast to regular MDPs, in a POMDP the agent cannot observe the
state; it only observes the observations. However, the observations
are not a Markovian signal: i.e., the last observation $\oAT{}{t}$
made by the agent does not provide the same amount of information
(to predict the rewards and the future of the the process) as the
\emph{action-observation history (AOH)}, the entire history of actions
and observations $\aoHistAT{}{t}=\left(\aAT{}0,\oAT{}1,\dots,\aAT{}{t-1},\oAT{}{t}\right)$.
This means that the agent needs to select its actions based on the
history of observations.

Luckily, for a POMDP this history can be summarized compactly as a
\emph{belief, }which is defined as the posterior probability distribution
over states given the history:
\[
b(s)\defas\Pr(s|{b^{0}},\aoHistAT{}{t}).
\]
The belief does not only summarize the history, it does so in a lossless
way. That is, a belief is a \emph{sufficient statistic }for optimal
decision making~\cite{Bertsekas05DPBook_vol1}; it allows an agent
to reach the same performance as an agent that would act optimally
based on the AOH $\aoHistAT{}{t}$.

This belief can be recursively computed, which means that an agent
can update its belief as it interacts with its environment. We write
$b'=BU(b,a,o)$, where $BU(b,a,o)$ is the belief update operator
that, given a previous belief $b$ taken action $\aA{}$ and received
observation $\oA{}$, produces the next belief:
\begin{equation}
BU(b,a,o)(s')=\frac{1}{\Pr(o|b,a)}\Pr(o|a,s')\sum_{s}\Pr(s'|s,a)b(s).\label{eq:POMDP_BU}
\end{equation}
Here, $\Pr(o|b,a)$ is a normalization constant:

\[
\Pr(o|b,a)=\mathbf{E}_{\sT{}\sim\bA{},\sT{\prime}\sim T(\sT{},\aAT{}{},\cdot)}\left[O(\aAT{}{},\sT{\prime},\oAT{}{})\right]=\sum_{s'}\Pr(o|a,s')\sum_{s}\Pr(s'|s,a)b(s).
\]

\subsubsection{Policies \& Value Functions}

In a POMDP, the agent employs a \emph{policy,} $\polA{}$, to interact
with its environment. Such a policy is a (deterministic) mapping from
beliefs to actions. Note that, given the initial belief~${b^{0}}$, such
a policy will specify an action for each observation history.\footnote{This can be seen as follows: for ${b^{0}}$ the policy specifies an action,~$\aAT{}0$,
then given $\oAT{}1$ we can compute $\argsT{\bA{}}{1}$ which we
can use to look up $\aAT{}1$, etc. }

The goal of the decision maker, or agent, in the POMDP is to maximize
the expected (discounted) cumulative reward:
\[
\mathbf{E}\left[\sum_{t=0}^{h-1}\gamma^{t}R(\sT{t},\aAT{}{t},\sT{t+1})|{b^{0}},\polA{}\right],
\]
here
\begin{itemize}
\item $h$ is the horizon, i.e., the number of time steps, or \emph{stages,
}for which we want to plan,
\item the expectation is over sequences of states and observations induced
by the policy $\polA{}$,
\item $\gamma\in[0,1]$ is the discount factor.
\end{itemize}
In this work, we focus on the finite-horizon case, in which it is
typical (but not necessary) to assume $\gamma=1$.

For a finite-horizon POMDP, the optimal value function for stage~$t$
can be expressed as
\[
\QT{t}(\bA{},\aA{})=R(\bA{},\aA{})+\gamma\sum_{o}\Pr(o|b,a)V^{{t+1}}(BU(b,a,o))
\]
where $V^{{t+1}}(\bA{}')=\max_{\aA{}'}\QT{t+1}(\bA{}',\aA{}')$
is the value of acting optimally in the next time step and $R(b,\aA{})$
is the expected immediate reward:
\[
R(b,\aA{})=\mathbf{E}_{\sT{t}\sim\bA{},\sT{t+1}\sim T(\sT{t},\aAT{}t,\cdot)}\left[R(\sT{t},\aAT{}t,\sT{t+1})\right]=\sum_{s}b(s)\sum_{s'}\Pr(s'|s,a)R(s,a,s').
\]

\subsection{Multiagent Models: POSGs}

The POMDP model can be extended to include multiple self-interested
agents as follows.

\begin{definition}[POSG]\label{def:POSG}

A \emph{partially observable stochastic game (POSG) }is defined as
a tuple $\mathcal{M}^{POSG}=\left\langle \agentS,\sS,\jaS,T,\mathcal{R},\joS,O,h,{{b^{0}}}\right\rangle $
with the following components:
\begin{itemize}
\item $\agentS=\{\agentI1,\dots,\agentI\nrA\}$ is the set of \emph{$\nrA$}
agents.
\item $\sS$ is a (finite) set of states.
\item $\jaS=\aAS1\times\dots\aAS\nrA$ is the set of \emph{joint} actions
${\joint{\AC}}=\left\langle \aA 1,\dots,\aA{\nrA}\right\rangle $, with $\aAS i$
the set of individual actions for agent~$i$.
\item $T$ is the transition probability function.
\item $\mathcal{R}=\left\langle \RA 1,\dots\RA{\nrA}\right\rangle $ is
the collection of immediate reward function for each agent. Each $\RA i:\sS\times\jaS\times\sS\rightarrow\real$
maps from states, joint actions and next states to an immediate reward
for that agent.
\item $\joS=\oAS1\times\dots\times\oAS\nrA$ is the set of joint observations,
with $\oAS i$ the set of individual observations for agent~$i$,
\item $O$ is the observation probability function, which specifies $\Pr(\jo|{\joint{\AC}},s')$,
the probability of a particular joint observation $\jo$ after ${\joint{\AC}}$
and resulting state $s'$.
\item $h$ is the horizon of the problem as mentioned above.
\item ${b^{0}}\in\PrS(\mathcal{S})$, is the initial state distribution at time
$t=0$.
\end{itemize}
\end{definition}

Since in a POSG each agent has its own goal, there no longer is a
definition of optimality. Instead it is customary to focus on game-theoretic
solution concepts for POSGs~\cite{Hansen04AAAI}. Such solutions,
e.g., Nash equilibria, typically specify a tuple of policies $\jpol=\left\langle \polA 1,\dots,\polA{\nrA}\right\rangle $,
one for each agent, that are in equilibrium. In general, we will refer
to a tuple of policies $\jpol$ as a \emph{joint policy. }

Of course, it is also possible to consider cooperative teams of agents.
In this case, we align the goals of the agents by giving them the
same reward function:

\begin{definition}[Dec-POMDP]\label{def:Dec-POMDP} A \emph{decentralized
partially observable Markov decision process (Dec-POMDP)} is a POSG
where all agents share the same reward function: $\forall_{i,j}\;R_{i}=R_{j}$.
\end{definition}

Since interests are aligned, in a Dec-POMDP we can speak about optimality.
Moreover, there is guaranteed to be at least one \emph{deterministic
}joint policy that is optimal~\cite{Oliehoek08JAIR}. As was the
case for POMDPs, we can also consider variants of the multiagent models
with factored state spaces. We will refer to these as \emph{factored
POSGs (fPOSGs) }and \emph{factored Dec-POMDPs (fDec-POMDPs)}~\cite{Oliehoek08AAMAS}.\footnote{More recently, researchers have also investigated deterministic and
non-deteterministic versions, called  (factored) qualitative Dec-POMDP~\cite{Brafman13AAAI}.
We will not particularly target this special case in this paper, but
note that ideas of influence search can be exploited in this context
too \cite{Bazinin18GCAI}.}

\begin{figure}
\begin{centering}
{
\psfrag{1}[cc][cc]{1}
\psfrag{2}[cc][cc]{2}
\psfrag{g}[cc][cc]{T}\includegraphics[width=4cm]{figs/gsearch-squares}}
\par\end{centering}
\caption{A possible instantiation of the \<housesearch> problem: 1, 2 represent
the starting locations of the agents, while `T' encodes the possible
locations of the target.}

\label{fig:gsearch}

\end{figure}

As an example, we consider the \<housesearch>  problem \cite{Oliehoek11EUMAS},
in which a team of robots must find a target (say a remote control)
in a house with multiple rooms. This task is representative of an
important class of problems in which a team of agents needs to locate
objects or targets. In \<housesearch> the assumption is that a prior
probability distribution over the location of the target is available
and that the target is stationary or moves in a manner that does not
depend on the strategy used by the searching agents.

\begin{example} The \<housesearch>  environment can be represented
by a graph, as illustrated in Fig.~\ref{fig:gsearch}. At every time-step
each agent can stay in the current room or move to a next one. The
location of an agent~$i$ at time step $t$ is denoted $l_{i}^{t}$
and that of the target is denoted $l_{target}^{t}$. The actions (movements)
of each agent have a specific cost $c_{i}(l_{i},a_{i})$ (e.g., the
energy consumed by navigating to a next room) and can fail; we allow
for stochastic transitions $p(l_{i}'|l_{i},a_{i})$. Also, each robot
might receive a penalty $c_{time}$ for every time step that the target
is not found yet. When a robot is in (or near) the same node as the
target, there is a probability of detecting the target $p(detect_{i}|l_{target},l_{i})$,
 which will be modeled by a boolean state variable `target found'
$\argsT{f}{t}$, which both agents can observe (thus modeling a
communication channel which the agents can only use to inform each
other of detection).When the target is detected, the agents also
receive a reward $r_{detect}$.  Given the prior distribution and
model of target behavior, the goal is to optimize the sum (over time)
of rewards, thus trading off movement cost and probability of detecting
the target as soon as possible. We will focus on the situation where
each agent has its individual rewards (so the POSG setting). In previous
work, the house search problem was treated as a Dec-POMDP by defining
the team reward as the sum of the individual rewards~\cite{Oliehoek11EUMAS}.\end{example}

\begin{figure}[tbh]
\hfill{}\subfloat[With intra-stage connections.]{\begin{centering}
{\input{figs/frag_housesearch_2DBN.tex}\includegraphics[scale=0.4]{figs/housesearch-dia__fPOSG_intrastage}}
\par\end{centering}

\label{fig:house_dbn_intrastage}}\hfill{}\subfloat[Without intra-stage connections.]{\begin{centering}
{\input{figs/frag_housesearch_2DBN.tex}\includegraphics[scale=0.4]{figs/housesearch-dia__fPOSG_no-intrastage}}
\par\end{centering}

\label{fig:house_dbn_no-intra}}\hfill{}

\caption{Factored representation of the \<housesearch> problem. Actions, observations
and rewards of the first agent are in light blue, while those of agent~2
are in dark red. State variables are in black. }

\label{fig:house-dbn}

\end{figure}

Fig.~\ref{fig:house_dbn_intrastage} demonstrates how a 2DBN can be
used to compactly represent the transition, observation and reward
model. For instance, for each state variable at a state $t+1$, the
2DBN shows which other entities (state factors and actions) influence
it. The figure illustrates that most dependencies are \emph{across-stage}
(e.g., $l_{2}^{t}$ influences $l_{2}^{t+1}$) but that it is also
possible to have \emph{intra-stage} \emph{dependencies (ISDs). }For
instance, whether the target will be detected at stage $t+1$ depends
on $l_{2}^{t+1}$ not on $l_{2}^{t}$. The representation of the transition
model is compact since it can be represented as a product of \emph{conditional
probability tables (CPTs)}, each of which are exponential only in
the number of incoming dependencies. So as long as the number of incoming
connections is limited, the transition probabilities can be represented
compactly. Fig.~\ref{fig:house_dbn_intrastage} also shows that this
type of representation can also be employed for observation probabilities,
as well as rewards.

Since ISDs complicate notation and the definitions of influence, we
also consider a version of the problem that has no intra-stage connections,
shown in Fig.~\ref{fig:house_dbn_no-intra}. For rewards and observations,
intra-stage connections are still allowed. (In fact, since the observation
probabilities in the standard POMDP definition depend on the next
state $s'$, there is no way of representing them without intra-stage
connections). Note that this is a slightly different problem than
the problem represented in Fig.~\ref{fig:house_dbn_intrastage}: in
the problem without ISDs the agents have a chance of detecting the
target at stage $t+1$ if they are co-located with the target at
stage $t$, which means that there is a one-step delay incurred
before they receive the reward. This illustrates the fact the ISDs
do allow for a more expressive model, and that therefore developing
theory that support such connections is an important goal.

To facilitate easier exposition, in \sect\ref{sec:IBA} we will first
introduce the concept of influence-based abstraction without ISDs.
These will be considered in \sect\ref{sec:IBA-with-IS-deps}. Before
we can jump to the topic of influence-based abstraction, however,
we will need to discuss decision problems from a local perspective,
in \sect\ref{sec:LFMs-and-best-responses}, which covers problems
with ISDs.

\section{Best Responses \& Local-Form Models }

\label{sec:LFMs-and-best-responses}

In contrast to the typical solutions to POSGs and Dec-POMDPs, which
try and identify a joint policy as the solution, this paper focuses
on computing best-response policies in interactive settings. That
is, given a multiagent model with state uncertainty (either a POSG
or Dec-POMDP) and given some policy for the other agents $\jpolG{\excl i}=\left\langle \polA 1,\dots,\polA{i-1},\polA{i+1},\dots,\polA{\nrA}\right\rangle $,
we want to compute the best response $\polA i^{BR}$ for agent~$i$.
Such best-response computation is obviously important for self-interested
agents (i.e., in POSGs), but is also an important component in many
Dec-POMDP solution methods~\cite{Nair03IJCAI,Nair05AAAI,Kim06AAAISS}.

\begin{figure}
\begin{centering}
\includegraphics[scale=0.5]{figs/models-overview}
\par\end{centering}
\caption{Overview of various models used.}

\label{fig:modelTypes}
\end{figure}

As illustrated in Fig.~\ref{fig:modelTypes}, we will consider a number
of different types of models in this paper. The starting point is
given by the fPOSG or a special case thereof (e.g., a Dec-POMDP).
We refer those models as global-form models (GFMs). For such models,
it is possible to directly compute a best-response by fixing the policies
of the other agents. We refer to the resulting POMDP as a global-form
best-response model (GFBRM); these models will be introduced next.
Subsequently, we will introduce \emph{local-form models (LFMs)} these
models restricts the state factors that each agent primarily cares
about. That is, an agent in an LFM only reasons about a subset of
factors. This will then form the basis for computing best-responses
in such a local model, called \emph{influence-augmented local model
(IALM),} which will be enabled by influence-based abstraction introduced
in \prettyref{sec:IBA}.

\subsection{Global-Form Best-Response Model }

\label{sec:GFBRM}

In this section we define a Global-Form Best-Response Model (GFBRM)
that an agent can use in order to compute a best-response in a general
POSG. We first define this model and then talk about value functions
for this model.\footnote{Our formulation here is closely related to the way best-responses
are computed in DP-JESP~\cite{Nair03IJCAI}: essentially our representation
here is a reformulation that makes explicit the fact that fixing the
policies of other agents leads to a single-agent POMDP model.}

\paragraph{Model}

The basic idea of defining a best-response model is shown in Fig.~\ref{fig:GFBRM}.
By fixing $\jpolG{\excl i}$, the policies of the other agents, all
the choice nodes are turned into random variables that now depend
on the AOHs that those agents observed. So the key construct here
is that the AOH of the other agent(s) is made part of the state of
the best-response model. This can be formalized as follows.
\begin{figure}
\centering{}{\input{figs/frag_brm.tex}\cite{Nair03IJCAI,Nair05AAAI,Kim06AAAISS}\includegraphics[scale=0.4]{figs/global-form-best-response-model_v1}}\caption{A hypothetical global-form best-response model for agent~2, unrolled
over time. The action-observation history (i.e., internal state) of
agent~1 can be interpreted as a state factor in this model. \label{fig:GFBRM}}
\end{figure}

\begin{definition}[Global-Form Best-Response Model]Let $\mathcal{M}^{POSG}=\left\langle \agentS,\sS,\jaS,T,\mathcal{R},\joS,O,h,{{b^{0}}}\right\rangle $
be a (f)POSG and let $\jpolG{\excl i}$ be a profile of policies for
all agents but $i$. A \emph{Global-Form Best-Response Model (GFBRM)
}for agent~$i$ is a POMDP: $\mathcal{M}_{i}^{GFBR}(\mathcal{M}^{POSG},\jpolG{\excl i})=\left\langle \bar{\sS},\aAS{i},\bar{T}_{i},\bar{R}_{i},\oAS{i},\bar{O}_{i},h,\bar{\bA i}{}^{0}\right\rangle $,
where
\begin{itemize}
\item $\bar{\mathcal{S}}$ is the set of augmented states $\sAugAT it=\langle s,\aoHistAT{\excl i}{t}\rangle$
that specify a underlying state of the POSG as well as an AOH history
for all the other agents.
\item $\aAS{i},\oAS{i}$ are the (unmodified) sets of actions and observations
for agent~$i$.
\item The transitions
\begin{eqnarray*}
\bar{T}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t}) & = & \bar{T}(\langle\sT{t+1},\aoHistAT{\excl i}{t+1}\rangle|\langle\sT{t},\aoHistAT{\excl i}{t}\rangle,\aAT i{t})\\
 & = & \bar{T}(\langle\sT{t+1},\left(\aoHistAT{\excl i}{t},\aAT{\excl i}{t},\oAT{\excl i}{t+1}\right)\rangle|\langle\sT{t},\aoHistAT{\excl i}{t}\rangle,\aAT i{t})\\
 & = & \Pr(\oAT{\excl i}{t+1},\sT{t+1},\aAT{\excl i}{t}|\sT{t},\aAT i{t},\aoHistAT{\excl i}{t})\\
 & = & \Pr(\oAT{\excl i}{t+1}|\aAT i{t},\aAT{\excl i}{t},\sT{t+1})\Pr(\sT{t+1}|\sT{t},\aAT i{t},\aAT{\excl i}{t})\Pr(\aAT{\excl i}{t}|\aoHistAT{\excl i}{t})\\
 & = & \left[\sum_{\oAT i{t+1}}O(\joT{t+1}|\jaT{t},\sT{t+1})\right]T(\sT{t+1}|\sT{t},\jaT{t})\polA{\excl i}(\aAT{\excl i}{t}|\aoHistAT{\excl i}{t})
\end{eqnarray*}
with $\polA{\excl i}(\aAT{\excl i}{t}|\aoHistAT{\excl i}{t})=\prod_{j\neq i}\polA j(\aAT j{t}|\aoHistAT j{t})$
the probability of $\aAT{\excl i}{t}$ given $\aoHistAT{\excl i}{t}$
according to $\polA{\excl i}$.
\item The observations
\begin{eqnarray*}
\bar{O}(\oAT i{t+1}|\aAT i{t},\sAugAT i{t+1}) & = & \bar{O}(\oAT i{t+1}|\aAT i{t},\langle\sT{t+1},\left(\aoHistAT{\excl i}{t},\aAT{\excl i}{t},\oAT{\excl i}{t+1}\right)\rangle)\\
 & = & \Pr(\oAT i{t+1}|\aAT i{t},\aAT{\excl i}{t},\sT{t+1},\oAT{\excl i}{t+1})\\
 & = & \frac{\Pr(\oAT i{t+1},\oAT{\excl i}{t+1}|\aAT i{t},\aAT{\excl i}{t},\sT{t+1})}{\Pr(\oAT{\excl i}{t+1}|\aAT i{t},\aAT{\excl i}{t},\sT{t+1})}\\
 & = & \frac{O(\joT{t+1}|\jaT{t},\sT{t+1})}{\sum_{\oAT i{t+1}}O(\joT{t+1}|\jaT{t},\sT{t+1})}
\end{eqnarray*}
\item $\bar{R}_{i}$ is the augmented reward model
\begin{eqnarray*}
\bar{\RA i}(\sAugAT it,\aAT i{t},\sAugAT i{t+1}) & = & \bar{\RA i}(\langle\sT{t},\aoHistAT{\excl i}{t}\rangle,\aAT i{t},\langle\sT{t+1},\aoHistAT{\excl i}{t+1}=\left(\aoHistAT{\excl i}{t},\aAT{\excl i}{t},\oAT{\excl i}{t+1}\right)\rangle)\\
 & = & \RA i(\sT{t},\aAT i{t},\aAT{\excl i}{t},\sT{t+1})
\end{eqnarray*}
Note that $\aAT{\excl i}{t}$ is specified by $\sAugAT i{t+1}$.
\item $h$ is the (unmodified) horizon.
\item $\bar{\bA i}{}^{0}$ is the initial belief\emph{. }
\end{itemize}
\end{definition}

A GFBRM is a POMDP, which means that an agent can track a belief,
which is now a distribution over \emph{augmented states }$\sAugA i=\langle\sT{t},\aoHistAT{\excl i}{t}\rangle$,
as usual. We will refer to such beliefs as \emph{global-form beliefs,
}denoted $\gbA i$. The initial global-form belief follows directly
from the initial belief of the POSG. Since at the first stage, the
history of the other agents is the empty history, it is trivially
constructed from ${b^{0}}$: $\forall_{s}\ \gbA i(\left\langle s,()\right\rangle )={b^{0}}(s).$

Note that the description of the GFBRM depends rather crucially on
the fact that we choose AOHs for the representation of the internal
state of the other agent(s). That is, we assume that the policies
of the other agent(s) are based on their AOHs. While this is a very
general model, other models of other agents with a more limited description
of internal state can be useful too. For such more compact descriptions,
however, it is not always possible to construct a POMDP model with
an independent transition and observation model. Instead, one may
need to replace $\bar{T},\bar{O}$ by a combined `dynamics function'
$\bar{D}$ that specifies $\bar{D}(\sAugAT i{t+1},\oAT i{t+1}|\sAugAT it,\aAT i{t})$.
For more details see \cite{Oliehoek14MSDM}.\footnote{{\renewcommand{\aoHistAT}[2]{I_{#1}^{#2}}Essentially in such a setting
we have that augmented states are tuples of nominal states and internal
states of other agents $\sAugAT it=\langle\sT{t},\aoHistAT{\excl i}{t}\rangle$.
The internal states of the other agent are updated based upon the
taken actions and observations, but do not store those actions and
observations. This means that, in general, $\bar{D}$ is specified
as a marginal:
\begin{multline*}
\bar{D}(\sAugAT i{t+1},\oAT i{t+1}|\sAugAT it,\aAT i{t})=\Pr(\langle\sT{t+1},\aoHistAT{\excl i}{t+1}\rangle,\oAT i{t+1}|\langle\sT{t},\aoHistAT{\excl i}{t}\rangle,\aAT i{t})\\
=\sum_{\aAT{\excl i}{t},\oAT{\excl i}{t+1}}\Pr(\aoHistAT{\excl i}{t+1}|\aoHistAT{\excl i}{t},\aAT{\excl i}{t},\oAT{\excl i}{t+1})O(\joT{t+1}|\jaT{t},\sT{t+1})T(\sT{t+1}|\sT{t},\jaT{t})\polA{\excl i}(\aAT{\excl i}{t}|\aoHistAT{\excl i}{t})
\end{multline*}
and it is not possible to decompose it into a transition and observation
function.}}

\paragraph{Value Function}

Since a GFBRM is just a POMDP, all POMDP theory and solution methods
apply. E.g., the value function is given by:

\begin{equation}
Q_{i}(\gbA i,\aA i)=R_{i}(\gbA i,\aA i)+\gamma\sum_{\oA i}\Pr(\oA i|\gbA i,\aA i)V_{i}(BU(\gbA i,\aA i,\oA i))\label{eq:Q(b,a)__GFBRM}
\end{equation}
where
\begin{align}
R_{i}(\gbA i,\aAT it) & =\mathbf{E}_{\sAugAT it\sim\gbA i,\sAugAT i{t+1}\sim\Aug T_{i}(\sAugAT it,\aAT it,\cdot)}\left[\Aug{R_{i}}(\sAugAT it,\aAT it,\sAugAT i{t+1})\right]\nonumber \\
 & =\sum_{\sT{t}}\sum_{\sT{t+1}}\sum_{\jaG{\excl i}}\Pr(\sT{t+1}|\sT{t},{\joint{\AC}})R_{i}(\sT{t},{\joint{\AC}},\sT{t+1})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t})\gbA i(\sT{t},\aoHistAT{\excl i}{t})\label{eq:R(gfb,a)__GFM}
\end{align}
(see Appendix~\ref{app:GFBRM_reward}) and
\begin{eqnarray}
\negmedspace\negmedspace\negmedspace\negmedspace\Pr(\oAT i{t+1}|\gbA i,\aAT it) & \negmedspace=\negmedspace & \mathbf{E}_{\sAugAT it\sim\gbA i,\sAugAT i{t+1}\sim\Aug T_{i}(\sAugAT it,\aAT it,\cdot)}\left[\Aug O_{i}(\oAT i{t+1}|\aAT it,\sAugAT i{t+1})\right]\nonumber \\
 & \negmedspace=\negmedspace & \sum_{\sT{t}}\sum_{\sT{t+1}}\sum_{\jaG{\excl i}}\sum_{\joGT{\excl i}{t+1}}\Pr(\sT{t+1}|\sT{t},{\joint{\AC}})\Pr(\joT{t+1}|{\joint{\AC}},\sT{t+1})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\gbA i(\sT{t},\aoHistAT{\excl i}{t})\label{eq:P(o|gfb,a)__GFM}
\end{eqnarray}
(see Appendix~\ref{app:GFBRM_observ}.)

Solution of the GFBRM gives the best-response value for agent~$i$:

\begin{equation}
V_{i}(\polA{\excl i})\defas V_{i}(\gbAT i0).\label{eq:V(b0)_JESP}
\end{equation}

\subsection{Local-Form Model }

GFBRMs allow an agent~$i$ to compute a best-response policy against
the fixed policies $\jpolG{\excl i}$ of the other agents. A difficulty
here is that agent~$i$ needs to reason about many state factors
as well as the internal state (the action-observation history) of
the other agents. That is, drawing an analogy to human interactions,
it is like in a simple collaborative task (e.g., carrying a table),
we would need to reason over the inner working of our collaborator's
brain, as well as over the sequence of images that he or she perceives.
Clearly, such an approach is infeasible in general. To make a step
in the direction to overcome this problem, here we introduce \emph{local-form
models (LFMs)} which restrict the set of state factors that each agent
primarily cares about, and eliminates the dependence on the AOH of
other agents.

\paragraph{Local States}

An LFM augments an fPOSG with a function that provides a description
of each agent's \emph{local state}.  Local state descriptions comprise
potentially overlapping subsets of state factors that will allow us
to decompose an agent's best-response computation from the global
state. We start with some definitions.

\begin{definition}[Local state function] The \emph{local state function
}$\LSF:\agentS\rightarrow2^{\sfacS}$ maps from agents to subsets
of state factors $\LSF(\agentI i)$ that are in the agents local state.
\end{definition}

\begin{definition}[Observation-relevant factor]We say that a state
factor $\sfac$ is \emph{observation-relevant} for an agent~$i$,
denoted $\text{ORel}{}_{i}(\sfac)$, if it influences the probability
of the agent's observation. That is, when in the 2DBN there is a link
from $\sfacT t$ to $\oAT i{t}$ (i.e., $\sfac$ is a parent of
$\oAT i{t}$).\end{definition}

\begin{definition}[Reward-relevant Factor]Similarly, a state factor
$\sfac$ is \emph{reward-relevant} for an agent~$i$, $\text{RRel}{}_{i}(\sfac)$
if it influences the agent's rewards, i.e., if $\sfacT t$ or $\sfacT{t+1}$
is a parent of $\RAT{i}{t}$. \end{definition}

We say that a state factor $\sfac$ is \emph{modeled} by an agent~$i$
if it is part of its local state space: $\sfac\in\LSF(\agentI i)$.
We can now define the local-form model.

\begin{definition}[Local-form model] \label{dfn:lfm} A \emph{local-form
POSG,} also referred to as\emph{ local-form model (LFM),} is a pair
$\mathcal{M}^{LFM}=\left\langle \mathcal{M},\LSF\right\rangle $,
where $\mathcal{M}$ is an fPOSG and $\LSF$ is a local state function
such that, for all agents:
\begin{enumerate}
\item All observation-relevant factors are in the local state: $\forall_{\agentI i}\forall_{\sfac}\;\text{ORel}{}_{i}(\sfac)\implies\sfac\in\LSF(\agentI i).$
\item All reward-relevant factors are in the local state: $\forall_{\agentI i}\forall_{\sfac}\;\text{RRel}{}_{i}(\sfac)\implies\sfac\in\LSF(\agentI i).$
\end{enumerate}
\end{definition}

The basic idea behind this definition is that we will abstract away
all the non-modeled factors for the best-response computation. The
requirements on observation- and reward-relevant factors make certain
that the observation probabilities and rewards are still specified
in this abstracted model. Note also that this means that we will
only be able to abstract away (latent) state variables, not observation
variables themselves. We will show that such latent factor abstraction
can, in principle, be performed without loss in value. This certainly
would not be the case for abstracting away observation variables:
in general this would lead to a loss of information and a corresponding
drop in achievable value.

The focus in this text is on computing a best-response for one agent~$i$.
This allows us to divide the set of state factors in ones modeled
by agent~$i$'s local problem (indicated with $\MF$) and ones that
are not modeled (indicated with $\NMF$).\footnote{More generally, from the perspective of agent~$i$, $\LSF$ partitions
the modeled factors $\LSF(i)$ in two sets: a set of \textit{private}
factors that it models but other agents do not, and a set of \textit{mutually-modeled
factors} (MMFs) that are modeled by agent~$i$ as well as some other
agent~$j$. This distinction plays a crucial role in influence search
for TD-POMDPs~\cite{Witwicki10AAMAS}, but is less important for
computing best-responses as considered in this document.} In particular, we will write
\begin{itemize}
\item $\mfI l$ (an instantiation of) a modeled factor (with index l),
\item $\mfA i$ (an instantiation of) all modeled factors of agent~$i$,
\item $\nmfI l$ (an instantiation of) a non-modeled factor (with index
l),
\item $\nmfA i$ (an instantiation of) all non-modeled factors of agent~$i$.
\end{itemize}

\paragraph{Transition probabilities}

In an LFM, the probability of the next local state is the marginal
of the entire state:
\begin{equation}
\Pr(\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})=\sum_{\nmfAT i{t+1}}\Pr(\mfAT i{t+1},\nmfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\label{eq:P_xm_sa}
\end{equation}

In an LFM, just as in a normal fPOSG, the flat transition probabilities
on the right hand side of this equation are given by the product of
the CPTs. However, from the perspective of an agent~$i$ we can now
group these CPTs in three different categories: 1) those corresponding
to modeled factors that are only affected by other factors and actions
that are modeled, 2) those corresponding to modeled factors that are
affected by at least one factor or action of the external problem,
and 3) those corresponding to non-modeled factors. We will refer to
the state factors corresponding to these as:
\begin{enumerate}
\item \emph{Only-locally-affected factors (OLAFs)~}$\mflI k$. These can
have incoming arrows from all modeled factors $\mfAT i{t}$ at the
previous stage, and from all modeled factors $\mfAT i{t+1}$ intra-stage
(but, obviously, excluding $\mflIT k{t+1}$ itself, and respecting
a non-cyclic structure as any 2DBN).
\item \emph{Non-locally-affected factors (NLAFs)}~$\mfnI k$; These can
(also) be affected by any other factor or action, intra-stage or previous
stage.
\item \emph{Non-modeled factors (NMFs)}~$\nmfI k$.
\end{enumerate}
These three types of factors are illustrated in Fig.~\ref{fig:LFM-factor-types},
which shows a hypothetical local-form model. Using the introduced
notation, we can write the transition probabilities as:
\begin{align}
\Pr(\sT{t+1}|\sT{t},\aA i,\jaG{\excl i})= & \left[\Pr(\mflAT i{t+1}|\dots)\Pr(\mfnAT i{t+1}|\dots)\Pr(\nmfAT i{t+1}|\dots)\right]\nonumber \\
= & \Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\nmfAT i{t},\nmfAT i{t+1},\aA i,\jaG{\excl i})\Pr(\nmfAT i{t+1}|\mfAT i{t},\mfAT i{t+1},\nmfAT i{t},\aA i,\jaG{\excl i})\label{eq:P_xxm_sa__LFM_transitionProbs}
\end{align}
with
\begin{itemize}
\item $\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)$ representing
a product of CPTs of OLAFs $\mflI k$:
\begin{equation}
\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)=\prod_{k\in OLAF(i)}\Pr(\mflIT k{t+1}|\mfAT i{t},\mfAT i{t+1},\aA i)\label{eq:LFM:T:OLAFs}
\end{equation}
Note that although such individual factors $\mflIT k{t+1}$ can
have intra-stage dependencies on other OLAFs $\mflIT l{t+1}$ (i.e.,
as the functional form $\Pr(\mflIT k{t+1}|\mfAT i{t},\mfAT i{t+1},\aA i)$
reveals, $\mflIT k{t+1}$ can depend on $\mfAT i{t+1}$ which
can include other OLAFs $\mflIT l{t+1}$), the product term $\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)$
itself can only have intra-stage dependencies on $\mfnAT i{t+1}$;
the intra-stage OLAFs $\mflAT i{t+1}$ will not appear in the conditioning
set (`behind the pipe') as they have all been multiplied in (they
are `before the pipe'). As long as the 2DBN is non-cyclical this
should not present any problems. \footnote{A more explicit way of writing this is as follows. In general the
OLAFs can now depend on some NLAFs $\mfnAIT i{ISD}{t+1}$ that act
as intra-stage dependencies:
\[
\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAIT i{ISD}{t+1},\aAT i{t})\defas\prod_{k\in OLAF(i)}\Pr(\mflIT k{t+1}|\mfAT i{t},\aAT i{t},\mfIT{ISD(k)}{t+1})
\]
with $\mfIT{ISD(k)}{t+1}$ denoting the intra-stage parents of $\mflIT k{t+1}$.
To reduce the notational burden, however, we will use the shorthands
from \eqref{eq:LFM:T:OLAFs}. }
\item $\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\nmfAT i{t},\nmfAT i{t+1},\aA i,\jaG{\excl i})$
the product of NLAF probabilities:
\begin{equation}
\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\nmfAT i{t},\nmfAT i{t+1},\aA i,\jaG{\excl i})=\prod_{k\in NLAF(i)}\Pr(\mfnIT k{t+1}|\mfAT i{t},\mfAT i{t+1},\nmfAT i{t},\nmfAT i{t+1},\aA i,\jaG{\excl i})\label{eq:LFM:T:NLAFs}
\end{equation}
\item $\Pr(\nmfAT i{t+1}|\mfAT i{t},\mfAT i{t+1},\nmfAT i{t},\aA i,\jaG{\excl i})$
the product of probabilities of the NMFs~$\nmfI k$:
\begin{equation}
\Pr(\nmfAT i{t+1}|\mfAT i{t},\mfAT i{t+1},\nmfAT i{t},\aA i,\jaG{\excl i})=\prod_{k\in NMF(i)}\Pr(\nmfIT k{t+1}|\mfAT i{t},\mfAT i{t+1},\nmfAT i{t},\nmfAT i{t+1},\aA i,\jaG{\excl i})\label{eq:LFM:T:NMFs}
\end{equation}
\end{itemize}
\begin{figure}
\hfill{}\subfloat[Illustration of an abstract local-form model for agent~2. Factors
can be divided into non-modeled factors ($\sfacI1$), non-locally-affected
factors ($\sfacI2$, $\sfacI3$), and locally-affected factors ($\sfacI4$).
Also note that $\sfacI4$ is reward-relevant, while $\sfacI2$ and
$\sfacI3$ are observation-relevant factors. ]{\begin{centering}
{\input{figs/frag_brm_2DBN.tex}\includegraphics[scale=0.42]{figs/LFM__LAF-NLAF-NMF}}
\par\end{centering}

\label{fig:LFM-factor-types}}\hfill{}\subfloat[Local-form model for agent~2 in the housesearch problem without intra-strage
dependencies.]{\begin{centering}
{\input{figs/frag_housesearch_2DBN.tex}\includegraphics[scale=0.42]{figs/housesearch-dia__fPOSG_no-intrastage__LFM}}
\par\end{centering}

\label{fig:LFM-housesearch--no-intrastage}}\hfill{}

\caption{Local-form models.}

\end{figure}

\paragraph{Value Function}

An LFM contains an fPOSG and as such best-response values for an agent~$i$
can be computed using the techniques discussed above in \prettyref{sec:GFBRM}.
In particular, we can just ignore the local state function and apply
\eqref{eq:Q(b,a)__GFBRM} with the previously stated definitions of
$R_{i}(\gbA i,\aA i)$ \eqref{eq:R(gfb,a)__GFM} and $\Pr(\oAT i{t+1}|\gbA i,\aA i)$
\eqref{eq:P(o|gfb,a)__GFM}.

Clearly, however, we would like to now rewrite the value function
in a way that represents the local structure imposed by the LFM requirements
and exploits this for computational benefits. The former is possible:
for an LFM, we can indeed derive a expression for $R_{i}(\gbA i,\aA i)$
that is more local (see Appendix~\ref{app:LFM:exp_reward}).
\begin{equation}
R_{i}(\gbA i,\aA i)=\sum_{\mfAT i{t}}\sum_{\mfAT i{t+1}}R_{i}(\mfAT i{t},\aA i,\mfAT i{t+1})\Pr(\mfAT i{t},\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i}),\label{eq:R(gfb,a)__LFM}
\end{equation}
where (remember $\sT{t}=\langle\mfAT i{t},\nmfAT i{t}\rangle$)

\begin{equation}
\Pr(\mfAT i{t},\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i})\defas\sum_{\nmfAT i{t}}\sum_{\jaG{\excl i}}\Pr(\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\gbA i(\sT{t},\aoHistAT{\excl i}{t}).\label{eq:P_xmxm_gfb}
\end{equation}
And, similarly, we can find a new, local, expression for the observation
probability (Appendix~\ref{app:LFM:exp_obs}):

\begin{equation}
\Pr(\oAT i{t+1}|\gbA i,\aA i)=\sum_{\mfAT i{t+1}}\Pr(\oAT i{t+1}|\aA i,\mfAT i{t+1})\Pr(\mfAT i{t+1}|\gbA i,\aA i,\jpolG{\excl i})\label{eq:P(o|gfb,a)__LFM}
\end{equation}
where
\begin{equation}
\Pr(\mfAT i{t+1}|\gbA i,\aA i)\defas\sum_{\sT{t}}\sum_{\jaG{\excl i}}\Pr(\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t}\jpolG{\excl i})\gbA i(\sT{t},\aoHistAT{\excl i}{t}).\label{eq:P_fm__gfb}
\end{equation}
These new definitions of $R_{i}(\gbA i,\aA i),\,\Pr(\oAT i{t+1}|\gbA i,\aA i)$
can be used directly in conjunction with \eqref{eq:Q(b,a)__GFBRM}.

However, even though these definitions \eqref{eq:R(gfb,a)__LFM} and
\eqref{eq:P(o|gfb,a)__LFM} are local, they still depend on the global-form
belief and this must perform summations over full states $\sT{t}$
and histories of other agents $\aoHistAT{\excl i}{t}$ via \eqref{eq:P_xmxm_gfb}
and \eqref{eq:P_fm__gfb}, rendering them intractable for larger problems.
In the next section, we will investigate formulations that are based
on more local beliefs to try and overcome this computational hurdle.

\section{Influence-Based Abstraction }

\label{sec:IBA}

In the previous section we introduced the GFBRM, which could be used
to compute a best response against a fixed policy of other agents.
This model gives a straightforward way of formulating the problem
of computing a best-response. However, it is specified over the global
state and internal state of other agents (i.e., their AOHs), which
means that solving this model is computationally intractable.

To provide a more localized perspective, the local-form POSG defines
for each agent a subset of factors that it should be concerned with.
However, even if the policies of the other agents are fixed, it is
not clear how an agent~$i$ can restrict its reasoning to its local
state $\mfA i$: the non-modeled factors will still affect the local
state transitions. Intuitively, we need to capture the influence that
the non-modeled part of the problem exerts on the modeled part.

In this section, we formalize this intuition. In particular, we treat
an LFM from the perspective of one agent and consider how that agent
is affected by the other agents and can compute a best response against
that `incoming' influence.\footnote{An agent also exerts `outgoing' influence on other agents, but this
is irrelevant for best response computation.  }

In an attempt to avoid notation overload, we first present a formulation
without considering intra-stage connections. The general formulation
that can deal with such connections is given in \sect\ref{sec:IBA-with-IS-deps}.

\subsection{Definition of Influence}

\label{sec:IBA:def-of-influence}

As discussed in \sect\ref{sec:GFBRM}, when the other agents are
following a fixed policy, they can be regarded as part of the environment.
The resulting decision problem can be represented by the complete
unrolled DBN, as illustrated in Fig.~\ref{fig:GFBRM}. In this figure,
a node $\sfacT{t}$ is a different node than $\sfacT{t+1}$ and
an edge at (emerging from) stage~$t$ is a different from the edge
at $t+1$ that corresponds to the same edge in the 2DBN. Given this
uniqueness of nodes and edges, we can define the `influence' as
follows.

\subsubsection{Influence Links, Sources \& Destinations}

\label{sec:IBA:def-of-influence:links-sources-destinations}

Intuitively, the influence of other agents is the effect of those
edges leading into the agent's local problem. We say that every directed
edge from outside the local model (e.g., from an NMF or action of
another agent) to inside the local model (e.g., to an modeled state
factor, observation variable, or reward), is an \emph{influence link}
$\langle\ifsTt,\ifdT{t}\rangle$, where $\ifsTt$ is called
the \emph{influence source} and $\ifdT{t}$ is the \emph{influence
destination}. In this section, we will assume that influence links
traverse a stage of the process (i.e., that the influence source for
a destination $\ifdT{t}$ lies in the stage $t-1$), but since
we will also consider intra-stage influence links at a later point
in this document, to keep notation consistent, we label an entire
influence link with the stage-index of its destination.

For example, let's consider the \<housesearch>  problem's LFM shown
in \prettyref{fig:LFM-housesearch--no-intrastage}. It shows that
the link from $\argsAT{l}{1}{t}$, the location of agent 1, to the
`target found' variable $\argsT{f}{t+1}$ is an influence link,
such that we would write the link as $\left\langle \ifsT{t+1}=\argsAT{l}{1}{t},\ifdT{t+1}=\argsT{f}{t+1}\right\rangle $,
similarly $\left\langle \ifsT{t}=\argsAT{l}{1}{t-1},\ifdT{t}=\argsT{f}{t}\right\rangle $
would denote the influence link in the preceding time step.

Assuming no intra-stage influence links, an influence source $\ifsT{t}$
can be either an action $\aAT j{t-1}$ or non-modeled state factor
$\nmfT{t-1}$. We write $\ifsAT i{t}=\langle\nmfAT u{t-1},\jaGT u{t-1}\rangle$
for an instantiation of all influence sources exerting influence on
agent~$i$ at stage $t$. That is, in the case of multiple influence
links pointing to modeled factors in stage $t$, $\nmfAT u{t-1}$
denotes the (value of) influence sources that are state factors, while
$\jaGT u{t-1}$ corresponds to those influence sources that are
actions. For instance, in our \<housesearch>  example, $\nmfAT u{t-1}=\{\argsAT{l}{1}{t-1}\},$
while $\jaGT u{t-1}=\emptyset$ since there are no actions that
are influence sources. We write $\aoHistGT u{t-1}$ for the AOHs
of those other agents whose action is an influence source (i.e., $\aoHistGT u{t-1}$
and $\jaGT u{t-1}$ involve the same agents) .

In general, an influence destination can be either a (per definition
non-locally-affected) modeled factor $\mfnT{t}$, an observation
variable $\oAT i{t}$, or a local reward node $\argsAT{\R}{i}{t}$.
But Definition~\eqref{dfn:lfm} requires reward- or observation-relevant
factors to be included in the local state; effectively we restrict
ourselves to the setting where the influence destination is an NLAF.
This restriction is without loss in generality: because we will introduce
(in \sect\ref{sec:IBA-with-IS-deps}) the machinery to deal with
\emph{intra-stage }influence links, influences on observations and
rewards can easily be dealt with by introducing a `dummy' NLAF that
acts as a proxy for the observation or reward.\footnote{E.g., to deal with an observation destination, we can transform the
observation $\oA i$ to a state factor $\sfacI{o}$ and introduce
a new observation variable that has a deterministic CPT depending
only on $\sfacI{o}$.} A similar construction can be used to deal with settings where actions
of other agents would directly influence the observations or rewards
of the agent under concern. As such, the capability of dealing with
such intra-stage dependencies is critical for the applicability of
the theory of influence-based abstraction.

\subsubsection{Sufficient Information to Predict Influences: D-Separating Sets}

\label{sec:IBA:def-of-influence:dset}

If agent~$i$ would in advance know the value of its influence sources
at different time steps, it could easily compute its best response
by making use of only this knowledge and its local model. Of course,
this is in general not possible, since the influence sources are random
variables. However, the influence exerted on agent~$i$ can be captured
if we know the probability distribution over their values. That is,
in order to predict the probability of some $\mfnAT i{t+1}$ (i.e.,
an influence destination) agent~$i$ only cares about the following
marginal probability
\begin{equation}
\sum_{\ifsAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\aAT i{t},\ifsAT i{t+1})\Pr(\ifsAT i{t+1}|\ldots),\label{eq:predicting-an-NLAF-via-marginal-prob}
\end{equation}
where the dots ($\ldots$) indicate any information that agent~$i$
needs to predict the probability of the values of the influence sources
as accurately as possible. Moreover, since these probabilities will
be used to plan a best response, correlations between influence sources
and local states are important. This unfortunately means that in general,
we might need to condition $\Pr(\ifsAT i{t+1}|...)$ on the entire
history of actions, observations and and local states.

Fortunately, it turns out that in many cases we can find substantially
more compact representations of the conditional probability of $\ifsAT i{t+1}$,
by making use of the concept of \emph{d-separation} in graphical models
\cite{Bishop06book,KollerFriedman09}. In particular, when two nodes
$A,B$ in a Bayesian network are d-separated given some of subsets
$\dsetA{}$ of evidence nodes, then $A$ and $B$ are conditionally
independent given $\dsetA{}$, which means that $\Pr(A|D,B)=\Pr(A|D)$
and vice versa. Whether nodes are d-separated can be easily checked,
by applying a small set of rules on the graph, for details please
see, e.g., \cite[chapter 8]{Bishop06book}.

Now, we can define the influence as a conditional probability distribution
over $\ifsAT i{t+1}$, given a d-separating set. Specifically, let
$\dsetAT i{t+1}$ be a subset of variables (possibly including state
factors and actions) in the local problem of agent~$i$ at stages
$0,\dots,t$,

\begin{definition}[D-separating set]\label{dfn:d-separating-set-NO-IS}
$\dsetAT i{t+1}$ is a \emph{d-separating set} \emph{for agent~$i$'s
influence at stage $t+1$} if and only if it d-separates $\nmfAT u{t},\aoHistGT u{t}$
from $\mfAT it,\aoHistAT it$. That is, if:
\begin{equation}
\forall_{\nmfAT u{t},\aoHistAT u{t}}\qquad\Pr(\nmfAT u{t},\aoHistAT u{t}|\mfAT it,\aoHistAT it,\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})=\Pr(\nmfAT u{t},\aoHistAT u{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i}).\label{eq:dset-def}
\end{equation}
\end{definition}

This definition implies that remembering more than $\dsetAT i{t+1}$
is not useful for predicting $\nmfAT u{t},\aoHistAT u{t}$ and
hence for predicting $\ifsAT i{t+1}=\langle\nmfAT u{t},\jaGT u{t}\rangle$
(given their policies, the actions of other agents only depend on
their AOHs).

\begin{example}Fig.~\ref{fig:dset-housesearch} illustrates a d-separating
set $\dsetAT i3$ for agent $i=2$ in \<housesearch>. It shows that,
in order to accurately compute the probability of influence source
$\argsAT l12$, agent 2 needs to condition on $\argsT{f}{0:2}$, the
history of the found variable, as well as the histories of the location
of the target $l_{tgt}$ and it own location~$\argsA l2$. This dependence
on the history in general leads to large conditioning sets, but in
many cases the history can be represented more compactly. For instance,
in \<housesearch> the `found' variable can only switch on (not
off) which means that its history $\argsT{f}{0:t}$ can be summarized
compactly. And in cases where the target is static the same holds
for $\argsAT{l}{tgt}{0:t}$. \end{example}

\begin{figure}
\begin{centering}
\input{figs/frag_housesearch_unrolled.tex}\includegraphics[scale=0.4]{figs/housesearch-dia__fPOSG_no-intrastage__unrolled-d-set}
\par\end{centering}
\caption{Illustration of the incoming influence on protagonist agent $i=2$
in \<housesearch> at stage $\protectt=3$. $\argsT f3$ is the
only influence destination, with influence source $\protect\nmfAT u2=\argsAT l12$
(i.e., $\protect\ifsAT i3=\left\langle \argsAT l12\right\rangle $).
The shaded nodes indicate the d-separating set $\protect\dsetAT i3$,
which, in accordance with \eqref{eq:dset-def}, d-separates the influence
source $\argsAT l12$, from agent 2's AOH $\protect\aoHistAT i{\protectt}$
and possibly remaining $\protect\mfAT i{\protectt}$ other local
variables (in this case there are no such variables, but one could
imagine adding a battery life variable for agent 2).}

\label{fig:dset-housesearch}
\end{figure}

\begin{example}Fig.~\ref{fig:dset-rover} shows a similar diagram
for a variant of the \problemName{planetary exploration} domain~\cite{Witwicki10ICAPS}.
Here agent~2 is a mars rover which is tasked with navigating to some
goal. Agent~1 is a satellite which can aid the rover by planning
a path, but this will use up computational resources and battery power
(which it may want to use to support other rovers too, for instance).
In the figure this is illustrated by the fact that the action of agent~1
$\aA 1\in\{NOOP,PLAN\}$ (which now is the influence source) determines
if there is a plan available for agent~2, modeled by a binary variable~$pl$
(which is the influence destination). In this example, the d-separating
set only contains this variable $pl$. Again its history can be compactly
summarized: as having the plan can only turn true, we can just store
how long ago $pl$ was switched to true.

\end{example}

\begin{figure}
\begin{centering}
\input{figs/frag_rover_unrolled.tex}\includegraphics[scale=0.4]{figs/rover-dia__fPOSG_no-intrastage__unrolled-d-set}
\par\end{centering}
\caption{Illustration of the influence experienced by the mars rover (agent
$i=2$) at stage $\protectt=3$ in the \problemName{planetary exploration} domain.
If the satellite (agent 1) computes and transmits a plan (\emph{pl)},
the rover can more effectively navigate from that point onward.}

\label{fig:dset-rover}
\end{figure}

\subsubsection{The Influence Exerted on Agent $i$}

Given the above machinery, we can now state our definition of influence:

\begin{definition}[Incoming Influence] \label{dfn:The-incoming-influence}
The \emph{incoming influence} at stage~$t+1$, denoted $\ifpiAT i{t+1}(\jpolG{\excl i})$,
is a conditional probability distribution over values of the influence
sources:
\begin{equation}
I(\ifsAT i{t+1}|\dsetAT i{t+1})\defas\sum_{\aoHistGT u{t}}\Pr(\jaGT ut|\aoHistGT u{t})\Pr(\nmfAT u{t},\aoHistGT u{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i}).\label{eq:IncomingInfluence__non-isd}
\end{equation}
\end{definition}

Note that, to reduce notational burden we drop arguments that can
be inferred, such as ${b^{0}},\jpolG{\excl i}$. That is, $I(\ifsAT i{t+1}|\dsetAT i{t+1})$
is shorthand for $\ifpiAT i{t+1}(\ifsAT i{t+1}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})$.
In cases where we want to refer to this distribution as a whole, we
will write $\ifpiAT i{t+1}(\jpolG{\excl i})$.

We will also say that this is the influence \emph{exerted }on agent~$i$
at stage $t$\emph{ }or \emph{experienced} by agent~$i$ at stage
$t+1$. So far, these notions coincide, but when we consider intra-stage
connections in the next section, we will discriminate between these
concepts.

Finally, we are in position to specify the complete influence on agent~$i$:

\begin{definition} An \emph{incoming influence point} $\ifpiA{i}(\jpolG{\excl i})$
for agent~$i$, specifies the incoming influences for all stages
$\ifpiA{i}(\jpolG{\excl i})=\left(\ifpiAT i1(\jpolG{\excl i}),\dots,\ifpiAT i{\h}(\jpolG{\excl i})\right)$.
\end{definition}

As we will see in the remainder of this paper, an influence point
contains all the information about the non-modeled part of the problem
that agent~$i$ needs to compute a best response `locally', i.e.,
only using its local model and that influence point. This can bring
computational benefits for instance when there would be changes in
the local model that require repeatedly performing planning, or in
cases where the influence point can be computed easily. This form
of influence-based abstraction, however, is not providing a free lunch~\cite{Wolpert95TR}:
in general computing the incoming influences \eqref{eq:IncomingInfluence__non-isd}
for the different stages comprise a set of challenging inference problems.
However, many special cases of problems have been identified in the
past \cite{Becker03AAMAS,Becker04AAMAS,Varakantham09ICAPS,Petrik09JAIR,Witwicki10AAMAS,Witwicki10ICAPS,Witwicki11AAMAS,Velagapudi11AAMAS,Witwicki11PhD,Witwicki12AAMAS,Oliehoek12AAAI_IBA},
and IBA gives a unified perspective on these. Moreover, it can be
used as tool to identify further special cases that allow for efficient
solution, such as the class of ND-POMDPs discussed in \cite{Oliehoek12AAAI_IBA}.
Given the potential benefits of using influence representations \cite{Witwicki12AAMAS},
such future search for special cases of problems that allow for compact
influence specifications together with the inference algorithms that
efficiently compute these is an important line of research. Our definition
of influence in this section provides the general framework in which
these special cases should be sought.

\subsection{The Influence-Augmented Local Model (IALM)}

Given the above definition of influence, we can now define a smaller
\emph{local} model for our protagonist agent~$i$. The main idea
is that given an incoming influence point, agent~$i$ no longer needs
to reason over the non-modeled part of the problem. Instead, it can
use the influence to compute marginal probabilities as expressed by
\eqref{eq:predicting-an-NLAF-via-marginal-prob}, and this will allow
it to compute an exact best-response.

In this section, we will first investigate a single NLAF and how the
influence on it can be incorporated. Then we move to talk about the
case where multiple variables in the local state $\LSF(\agentI i)$
are non-locally affected. Then we proceed to the formal definition
of the IALM, and how it can be solved.

\subsubsection{Induced CPTs}

In the case of a single influence destination, we can interpret \eqref{eq:predicting-an-NLAF-via-marginal-prob}
as constructing a new `influence-induced' CPT:

\begin{definition}[Induced CPT]Let $\mfnT{t+1}$ be an influence
destination, and $\ifsT{t+1}$ (the instantiation of) the corresponding
influence sources. Given the influence $\ifpiAT i{t+1}(\jpolG{\excl i})$,
and its d-separating set $\dsetAT i{t+1}$, we define the \emph{induced
CPT }for\emph{ }$\mfnT{t+1}$ as the CPT that has probabilities:
\begin{equation}
p_{\ifpiAT i{t+1}}(\mfnT{t+1}|\mfAT i{t},\dsetAT i{t+1},\aA i)=\sum_{\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaG u\right\rangle }\Pr(\mfnT{t+1}|\mfAT i{t},\aA i,\ifsAT i{t+1})I(\ifsAT i{t+1}|\dsetAT i{t+1})\label{eq:induced-CPT}
\end{equation}
\end{definition}

It is important to note that an induced CPT is specified purely in
\emph{local }terms, i.e., making use of variables that are modeled
by our protagonist agent~$i$. Therefore, the basic idea is that
we can now define a smaller \emph{local }model\textemdash which we
will call the \emph{Influence-Augmented Local Model (IALM)}\textemdash by
replacing the CPTs of influence destinations (i.e., NLAFs) by induced
CPTs.

\subsubsection{Dealing With Multiple NLAFs}

However, in case that there are multiple NLAFs, i.e., multiple variables
$\mfnT{t+1}$ in the local state space $\LSF(\agentI i)$ that are
affected nonlocally at the same stage $t+1$, the story is slightly
more involved, since we need to deal with their correlations.

Ideally, we would want to treat induced CPTs in the same way as normal
CPT; that is, we would represent the joint probability of NLAFs as
a the product of induced CPTs:
\begin{equation}
\Pr(\mfnAT i{t+1}|\mfAT i{t},\dsetAT i{t+1},\aA i,\ifpiAT i{t+1})=\prod_{k\in NLAF(i)}p_{\ifpiAT i{t+1}}(\mfnIT k{t+1}|\mfAT i{t},\dsetAT i{t+1},\aA i).\label{eq:P(NLAFS)__product-of-ICPTS}
\end{equation}
However, in general this is not possible since the different $\mfnIT k{t+1}$
are correlated via any common influence sources. That is, in general
the probability is given by:

\begin{equation}
\Pr(\mfnAT i{t+1}|\mfAT i{t},\dsetAT i{t+1},\aA i,\ifpiAT i{t+1})=\sum_{\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaG u\right\rangle }I(\ifsAT i{t+1}|\dsetAT i{t+1})\prod_{k\in NLAF(i)}\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsAT i{t+1})\label{eq:P(NLAFS)__general}
\end{equation}

Of course, in certain cases a factorization as induced CPTs is possible.
The above equations directly make clear when this is the case.

\begin{proposition}

If each NLAF $\mfnIT k{t+1}$ has its own influence sources $\ifsIT k{t+1}$
(and these do not overlap), and if these sources are conditionally
independent given $\dsetAT i{t+1}$:
\[
I(\ifsAT i{t+1}|\dsetAT i{t+1})=\prod_{k\in NLAF(i)}I(\ifsIT k{t+1}|\dsetAT i{t+1}),
\]
then the joint probability of NLAFs factorizes as a the product of
induced CPTs.\end{proposition}

\begin{proof} Under stated conditions, we can rewrite:
\begin{align*}
\eqref{eq:P(NLAFS)__general}= & \sum_{\ifsAT i{t+1}=\left\langle \dots,\ifsIT k{t+1},\dots\right\rangle }I(\ifsAT i{t+1}|\dsetAT i{t+1})\prod_{k\in NLAF(i)}\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsIT k{t+1})\\
= & \sum_{\ifsAT i{t+1}=\left\langle \dots,\ifsIT k{t+1},\dots\right\rangle }\left[\prod_{k\in NLAF(i)}I(\ifsIT k{t+1}|\dsetAT i{t+1})\right]\prod_{k\in NLAF(i)}\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsIT k{t+1})\\
= & \sum_{\ifsAT i{t+1}=\left\langle \dots,\ifsIT k{t+1},\dots\right\rangle }\prod_{k\in NLAF(i)}I(\ifsIT k{t+1}|\dsetAT i{t+1})\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsIT k{t+1})\\
= & \prod_{k\in NLAF(i)}\sum_{\ifsIT k{t+1}}I(\ifsIT k{t+1}|\dsetAT i{t+1})\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsIT k{t+1})=\eqref{eq:P(NLAFS)__product-of-ICPTS}\qedhere
\end{align*}
\end{proof}

\subsubsection{The IALM: A Formal Model to Incorporate Influence}

Here we formally define the IALM, which is a non-stationary POMDP,
since at every stage the influence destinations can be influenced
in a different manner.

\begin{definition}[IALM]

\label{dnf:IALM} Given an LFM, $\mathcal{M}^{LFM}$, and profile
of policies for other agents~$\jpolG{\excl i}$, an \emph{Influence-Augmented
Local Model (IALM) }for agent~$i$ is a POMDP $\mathcal{M}_{i}^{IALM}(\mathcal{M}^{LFM},\jpolG{\excl i})=\left\langle \bar{\sS},\aAS{i},\bar{T}_{i},\bar{R}_{i},\oAS{i},\bar{O}_{i},h,\lbAT i0\right\rangle $,
where
\begin{itemize}
\item $\bar{\mathcal{S}}$ is the set of augmented states $\sAugAT it=\langle\mfAT i{t},\dsetAT i{t+1}\rangle$
that specify an underlying local state of the POSG, as well as the
d-separating set $\dsetAT i{t+1}$ for the next-stage influences.
Note that $\dsetAT i{t+1}$ very typically needs to include certain
state factors for stage~$t$, such that $\mfAT i{t}$ and $\dsetAT i{t+1}$
both will specify such variables. This is no problem, as long as they
specify consistent assignments; we define $\bar{\mathcal{S}}$ to
be the set of states that are consistent.
\item $\aAS{i},\oAS{i}$ are the (unmodified) sets of actions and observations
for agent~$i$.
\item The transition function $\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})$
on which we will elaborate below.
\item The observation function $\bar{O}_{i}(\oAT i{t+1}|\aAT i{t},\sAugAT i{t+1})=O(\oAT i{t+1}|\aAT i{t},\mfAT i{t+1})$,
since agent $i$'s observations only depend on its local state (cf.
\dfn\ref{dfn:lfm}, property 1)
\item The reward function $\bar{\RA i}(\sAugAT it,\aAT i{t},\sAugAT i{t+1})=\RA i(\mfAT i{t},\aAT i{t},\mfAT i{t+1})$,
since agent $i$'s rewards only depend on its local state (cf. \dfn\ref{dfn:lfm},
property 2).
\item $h$ is the unmodified horizon.
\item $\lbAT i0$ is the initial state distribution, which is a \emph{local-form
belief. }It is a distribution over augmented states $\sAugAT i0=\langle\mfAT i0,\dsetAT i1\rangle$.
Since for the first stage $\dsetAT i1$ can only contain elements
from $\mfAT i0$, it can trivially be constructed from a probability
distribution over $\mfAT i0$, and such a distribution can be constructed
from ${b^{0}}$, as we discuss in a bit more detail below.
\end{itemize}
\end{definition}

In defining $\bar{T}_{i}$ and $\lbAT i0$, a few subtleties arise
that we now discuss.

\paragraph{Transition Probabilities }

Clearly, the IALM's transition probabilities should express
\[
\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})\defas\Pr(\langle\mfAT i{t+1},\dsetAT i{t+2}\rangle|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1}).
\]
For such probabilities to be specified, we need some further requirements
on the d-separating sets. In particular, we require that (the instantiation
of) $\dsetAT i{t+2}$ is fully specified by $\mfAT i{t},\aAT i{t},\mfAT i{t+1}$
and $\dsetAT i{t+1}$ such that we can write $\dsetAT i{t+2}$
as some function $d$ of those arguments: $\dsetAT i{t+2}=d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})$.
If this is the case, we can write:
\[
\Pr(\langle\mfAT i{t+1},\dsetAT i{t+2}\rangle|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})=\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\KroD{\dsetAT i{t+2}}{d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})},
\]
where $\KroD{\cdot}{\cdot}$ denotes the Kronecker delta function.

A typical way to fulfill the requirement that $\dsetAT i{t+2}$
is fully specified by $\mfAT i{t},\aAT i{t},\mfAT i{t+1}$ and
$\dsetAT i{t+1}$ is to assume that the d-separating sets for all
stages are chosen as the history of the same subset $\dsetA i\subseteq\LSF(i)$
of modeled features.

\begin{example}Looking at \prettyref{fig:dset-housesearch}, the
d-separating set $\dsetAT 23$ for predicting $\argsT f3$ is given
by the history of the `found', `location of target' and `location
of agent~2' variables. So we can write $\dsetA2=\left\{ f,\argsA l{tgt},\argsA l{2}\right\} $,
and define $\dsetAT 23$ to be its history at stage $t=2$: $\dsetAT 23=\dHistAT 22$.\end{example}

The probabilities $\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t})$
now are factored as the product of the CPTs of the OLAFs and the induced
probabilities for the NLAFs:
\begin{multline}
\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})\defas\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\KroD{\dsetAT i{t+2}}{d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})},\\
=\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i).\label{eq:IALM-T}
\end{multline}
Here the first term is given by \eqref{eq:P(NLAFS)__general} and
the second term is given by \eqref{eq:LFM:T:OLAFs}.\footnote{Note that, even though we have not dealt with intra-stage dependencies
(ISDs) in the description of influences in this section, we refer
back to the term $\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)$
from section 3 which does allow for ISDs from NLAFs to OLAFs. This
will allow us to make only minimal changes to the definition of $\bar{T}_{i}$
when we do deal with ISDs in \sect\ref{sec:IBA-with-IS-deps}.}

\paragraph{Initial Local State Distribution}

\begin{figure}
\input{figs/frag_initial-belief.tex}

\hfill{}\subfloat[The Bayesian network $G^{0}$ representing the initial belief.]{\begin{centering}
\begin{minipage}[b][3.7cm][t]{5cm}%
\begin{center}
\includegraphics[scale=0.4]{figs/initial-belief__b0}
\par\end{center}%
\end{minipage}
\par\end{centering}
}\hfill{}\subfloat[The 2DBN (a conditional Bayesian network) $G^{\rightarrow}$ representing
the transition and observation probabilities.]{\begin{centering}
\begin{minipage}[b][3.7cm][t]{7cm}%
\begin{center}
\includegraphics[scale=0.4]{figs/initial-belief__2DBN}
\par\end{center}%
\end{minipage}
\par\end{centering}
}\hfill{}

\medskip{}

\begin{centering}
\subfloat[The unrolled network $G=\text{unroll}(G^{0},G^{\rightarrow})$. To
convert it to an IALM, the local-form initial belief $\lbAT i0(B^{0})$
and incoming influences $\protect\ifpiAT i{\protectt+1}(A^{t}|B^{0},\dots,B^{\protectt})$
need to be computed via inference. See text for further explanation. ]{\begin{centering}
~~~~~~~\includegraphics[width=10cm]{figs/initial-belief__unrolled}~~~~~~~
\par\end{centering}
}
\par\end{centering}
\caption{Construction of the the IALM.}

\label{fig:initial-belief-local-construction}
\end{figure}

Here we discuss some of the issues involved in defining the initial
belief in the IALM. Note that in a factored models such as fPOSGs,
the initial state distribution ${b^{0}}$ is specified as a Bayesian network
$G^{0}$. Together with the 2DBN, $G^{\rightarrow}$ (which in fact
is a conditional probability distribution), it can form the unrolled
DBN $G=\text{unroll}(G^{0},G^{\rightarrow})$ which specifies the
joint distribution over all the state variables, as is illustrated
in Fig.~\ref{fig:initial-belief-local-construction}. Note that the
figure gives a simplified representation not involving any actions.

Now we will discuss how to specify the initial belief $\lbAT i0(\mfAT i0)$
of the IALM, the basic idea is to simply restrict $G^{0}$ to those
variables in the set $\LSF(i)$ of agent $i$'s local state variables.
However, this can lead to problems when there are arrows in $G^{0}$
pointing from variables not included in $\LSF(i)$ to variables included
in $\LSF(i)$. For instance, in Fig.~\ref{fig:initial-belief-local-construction},
the initial belief is factored: ${b^{0}}(s)=\Pr(A^{0})\Pr(B^{0}|A^{0})$.
The initial local-form belief, however, should only be specified over
$B^{0}$. The solution is to marginalize out the dependencies:
\[
\lbAT i0(B^{0})=\sum_{A^{0}}\Pr(A^{0})\Pr(B^{0}|A^{0}).
\]

This is also gives the general recipe for any other problem: construction
of $\lbAT i0$ from ${b^{0}}$ is a marginal inference task. Certainly,
for certain complex problems this could be intractable, but the hope
is that for many real-world problems the prior ${b^{0}}$ is sufficiently
sparsely structured for this not to be an issue. Also, any of the
vast number of (exact or approximate) inference methods developed
in the last decades can be used~\cite{KollerFriedman09,Boyen+Koller98UAI,Jordan99MLJ,Murphy02PHD,Wainwright08FaT}.

\paragraph{Impact of Correlations of Initial State Factors on The D-separating
Set}

Note that the correlation of the initial state distribution can affect
d-separation and therefore what variables need to be included in the
d-separating set $\dsetAT i{t}$. For instance, if in the above
example there additionally is a state factor $C$, which is not connected
to $A$ or $B$ in the 2DBN $G^{\rightarrow}$, but which is a parent
of $A$ in $G^{0}$, we get the unrolled DBN as shown in Fig.~\ref{fig:initial-belief-influence-on-dset}.

\begin{figure}
\begin{centering}
\input{figs/frag_initial-belief.tex}\includegraphics[width=10cm]{figs/initial-belief-with-C__unrolled}
\par\end{centering}
\caption{Impact of initial belief connectivity on the d-separating set of the
IALM.}

\label{fig:initial-belief-influence-on-dset}
\end{figure}

Now, to define the IALM, we will need to induced probability of $B^{3}$,
which according to \eqref{eq:P(NLAFS)__general} can be written\textbf{
}as
\[
\Pr(B^{3}|\left\langle B^{2},\dsetAT i3\right\rangle ,\ifpiAT i3)=\sum_{A^{2}}I(A^{2}|\dsetAT i3)\Pr(B^{3}|B^{2},A^{2}).
\]
Therefore $\dsetAT i3$ needs to contain any variables that can be
used to better predict $A^{2}$ (more formally, any variables that
d-separate $A^{2}$ from $\aoHistAT i{t}$ and any remaining variables
$x_{i}^{t}$, cf. \dfn\ref{dfn:d-separating-set-NO-IS}). However,
looking at the figure, we see that that means that $C^{0}$ needs
to be included in the d-set.

At the same time, however, we see that we do not need to condition
on the entire history $\vec{C}^{t}$. This may apear counter intuitive,
since observations at later time-steps (e.g, $\oAT i2$) which depend
on $\vec{C}^{t}$ certainly provide information about $A^{2}$. But
this is precisely the point: by including $C^{0}$ in the d-separating
set, it becomes part of the hidden state $\sAugAT i2=\langle\mfAT i2,\dsetAT i3\rangle=\langle\left\langle C^{2}\right\rangle ,\left\langle B^{0},B^{1},B^{2},C^{0}\right\rangle \rangle$,
and the later observations certainly provide information as to what
that hidden state is.

\begin{note}We note that this discussion neatly exemplifies some
different types of structure we can expect to encounter when dealing
with abstraction in structured decision making processes. This is
important also in the area of deep learning where much of the representations
are learned automatically, since no learning methods are effective
without the appropriate inductive biases~\cite{Mitchell80bias,Wolpert96NC}.
For instance, convolutional neural networks are so successful for
image processing because they exploit the fact that there is local
and repeated structure in real-world images. In a similar way, we
are noticing here that certain forms of structure, such as dependence
on certain state factors at stage $t=0$, might be common in sequential
decision processes involving abstraction, since we identify problem
structure which would lead to such dependencies. Recent research provides
preliminary evidence that structure as implied by influence-based
abstraction can be effectively uses to bias deep reinforcement learning
\cite{Suau19ALA}.\end{note}

\subsection{Planning in an IALM}

\label{sec:IBA:planning}

Here we look at how we can reason using an IALM. It turns out that
this is surprisingly simple, since an IALM \emph{is a }(special case
of) POMDP.

\begin{observation}An influence-augmented local model is a POMDP.\begin{proof}This
can simply be verified by comparing \dfn\ref{dnf:IALM} to the definition
of a POMDP (\dfn\ref{def:POMDP}).\end{proof}\end{observation}

This means that belief updates and definition of value functions follow
as usual. For completeness and future reference, we write these out
in detail below.

\subsubsection{Local-form Belief Update}

As implied by \dfn\ref{dnf:IALM}, in an IALM, an agent uses a \emph{local-form
belief}:

\begin{definition}[local-form belief]

A \emph{local-form belief $\lbAT it$ }for an IALM constructed for
agent~$i$ is the posterior probability distribution over augmented
states $\sAugAT i{t}=\langle\mfAT i{t},\dsetAT i{t+1}\rangle$.

\end{definition}

The belief update for such a local-form belief is as in a regular
POMDP, cf. \eqref{eq:POMDP_BU}:
\begin{multline}
BU(\lbA i,\aAT it,\oAT i{t+1})(\sAugAT i{t+1})=\frac{1}{\Pr(\oAT i{t+1}|\lbA i,\aAT it)}\bar{O}_{i}(\oAT i{t+1}|\aAT i{t},\sAugAT i{t+1})\sum_{\sAugAT it}\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})\lbA i(\sAugAT it)=\\
\frac{1}{\Pr(\oAT i{t+1}|\lbA i,\aAT it)}O(\oAT i{t+1}|\aAT i{t},\mfAT i{t+1})\sum_{\mfAT i{t},\dsetAT i{t+1}}\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\KroD{\dsetAT i{t+2}}{d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})}\lbA i(\mfAT i{t},\dsetAT i{t+1})\label{eq:IALM_BU}
\end{multline}
The expected observation probability (the normalization factor) in
this case is given by (see Appendix~\ref{app:IALM:exp_obs})
\begin{eqnarray}
\Pr(\oAT i{t+1}|\lbA i,\aAT it) & = & \mathbf{E}_{\sAugAT it\sim\lbA i,\sAugAT i{t+1}\sim\Aug T(\sAugAT it,\aA i,\cdot)}\left[\Aug O(\oAT i{t+1}|\aAT it,\sAugAT i{t+1})\right]\nonumber \\
 & = & \mathbf{E}_{\left\langle \mfAT i{t},\dsetAT i{t+1}\right\rangle \sim\lbA i,\left\langle \mfAT i{t+1},\dsetAT i{t+2}\right\rangle \sim\Aug T(\left\langle \mfAT i{t},\dsetAT i{t+1}\right\rangle ,\aA i,\cdot)}\left[O(\oAT i{t+1}|\aAT it,\mfAT i{t+1})\right]\nonumber \\
 & = & \sum_{\mfAT i{t+1}}O(\oAT i{t+1}|\aAT it,\mfAT i{t+1})\Pr(\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1}),\label{eq:P(o|lfb,a)}
\end{eqnarray}
with
\begin{equation}
\Pr(\mfAT i{t+1}|\lbA i,\aA i,\ifpiAT i{t+1})\defas\sum_{\mfAT i{t},\dsetAT i{t+1}}\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\lbA i(\mfAT i{t},\dsetAT i{t+1}).\label{eq:P_fm__lb}
\end{equation}

\subsubsection{IALM Value}

Putting everything togetting, we can show that for an IALM, the value
function is similar to the normal POMDP value function:

\begin{proposition}[IALM value function]The value function is given
by

\[
Q_{i}(\lbA i,\aAT it)=\RA i(\lbA i,\aAT it)+\gamma\sum_{\oAT i{t+1}}\Pr(\oAT i{t+1}|\lbA i,\aAT it)V_{i}(BU(\lbA i,\aAT it,\oAT i{t+1})),
\]
\[
V_{i}(\lbA i)=\max_{\aA i}Q_{i}(\lbA i,\aA i),
\]
where

\begin{eqnarray}
\RA i(\lbA i,\aAT it) & = & \mathbf{E}_{\sAugAT it\sim\lbA i,\sAugAT i{t+1}\sim\Aug T(\sAugAT it,\aAT it,\cdot)}\left[\Aug{R_{i}}(\sAugAT it,\aAT it,\sAugAT i{t+1})\right]\nonumber \\
 & = & \sum_{\mfAT i{t}}\sum_{\mfAT i{t+1}}\RA i(\mfAT i{t},\aAT it,\mfAT i{t+1})\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})\label{eq:R(lfb,a)}
\end{eqnarray}
with
\begin{equation}
\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})\defas\sum_{\dsetAT i{t+1}}\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\lbA i(\mfAT i{t},\dsetAT i{t+1}).\label{eq:P_xmxm_lfb}
\end{equation}

\begin{proof} This follows from the value function of regular POMDPs
together with the derivations of $\RA i(\lbA i,\aAT it)$ and $\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})$
in Appendix~\ref{app:IALM:exp_reward}.\end{proof}

\end{proposition}

The solution of the IALM gives the influence-based best-response value,
defined as the value of the initial local-form belief:

\begin{equation}
V_{i}(\ifpiA i(\polA{\excl i}))\defasV{}_{i}(\lbAT i0).\label{eq:V(b0)_inf}
\end{equation}

\section{IBA With Intra-Stage Dependencies}

\label{sec:IBA-with-IS-deps}

In the previous section, we assumed that all influence links span
a time step, but in general intra-stage connections can be useful
to specify a more intuitive model, as for \<housesearch> in Fig.~\ref{fig:house_dbn_intrastage}.
Moreover intra-stage connections enable us to introduce `dummy'
variables, as discussed in \ref{sec:IBA:def-of-influence:links-sources-destinations}.
Without this capability, the restriction of including all observation-relevant
and reward-relevant variables in the local state would limit the applicability
of influence-based abstraction.

This means that we need to be able to deal with intra-stage influence
sources, as illustrated in Fig.~\ref{fig:LFM-factor-types}. Therefore,
this section extends our definition of influence to also be applicable
for models that have such \emph{intra-stage dependencies (ISDs)}.

\subsection{Definition of Influence under ISDs}

\subsubsection{Intra-stage Influence Sources}

In settings with intra-stage dependencies, there is at least one non-modeled
factor $\nmfT{t+1}$ that influences an NLAF $\mfnT{t+1}$.  If
there are multiple such factors, we let $\nmfAT u{t+1}$ denote
them. Therefore, in order to perform IBA in settings with ISDs, we
will need to predict influence sources $\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaGT ut,\nmfAT u{t+1}\right\rangle $.
In order to correctly deal with the intra-stage sources~$\nmfAT u{t+1}$,
we will additionally need to consider those variables that influence
\emph{them}.

\subparagraph{Indirect Sources}

In particular, we use `$v$' as the symbol to denote such `indirect'
or `second order' influences and will write $\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1}$
and $\nmfAT v{t+1}$ for the possible\footnote{Of course, in any given problem not all of these types of variables
are relevant. For instance, if there is no action $\aAT j{t}$ of
another agent~$j$ that would influence an ISD influence source ,
then $\jaGT vt$ can be removed from the equations.} ancestors in the 2DBN of intra-stage sources~$\nmfAT u{t+1}$.
Now, we want to consider the probability of such $\nmfAT u{t+1}$,
and in general it is given by:
\begin{equation}
\Pr(\nmfAT u{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})=\sum_{\nmfAT v{t+1}}\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1}),\label{eq:P(intra-stage-source)}
\end{equation}
with:
\begin{itemize}
\item $\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})$
the product of CPTs of (both direct and indirect) intra-stage sources,
\item $\mfAT v{t}$ are those state factors in at stage $t$ (``in
the left-hand slice of the 2DBN'') that are modeled by agent~$i$,
and are ancestor to an intra-stage influence source of agent~$i$
at stage $t+1$ (``in the right-hand slice of the 2DBN''),
\item $\nmfAT vt$ are those state factors in the left-hand slice of the
2DBN that are not modeled by agent~$i$, but are ancestor to an influence
destination of agent~$i$,
\item $\mfAT v{t+1},$ $\nmfAT v{t+1}$ are the modeled respectively
unmodeled state factors at state $t+1$ that are ancestors to an
intra-stage influence source,
\item $\aAT i{t}$ might directly or indirectly affect an an intra-stage
influence source, in which case it needs to be included in \eqref{eq:P(intra-stage-source)},
\item $\jaGT vt$ are the actions of other agents that somehow are ancestors
of an  intra-stage influence source.
\end{itemize}
We will also write $\aoHistAT v{t}$ for the AOHs of the agents
$v$ that correspond to $\jaGT vt$ (i.e., those agents of which the
action is an ancestor in the 2DBN of an influence destination of agent~$i$).

\subparagraph{All sources}

So far we have introduced notation using $u$ for direct sources and
using $v$ for indirect sources. We will also want to consider the
union of direct and indirect sources, and for these purposes we will
write $w$. For example, we will write $\jaGT wt=\left\langle \jaGT ut,\jaGT vt\right\rangle $
for the actions of agents that either directly or indirectly influence
an influence destination.

\subparagraph{Example}

\begin{figure}
\begin{centering}
\input{figs/frag_housesearch_unrolled.tex}\includegraphics[scale=0.4]{figs/housesearch-dia__fPOSG_intrastage__unrolled}
\par\end{centering}
\caption{Illustration of the influence experienced by protagonist agent $i=2$
in the intra-stage version of \<housesearch> at stage $\protectt=2$.
$\argsT f2$ is the influence destination, with \emph{direct }influence
source $\protect\nmfAT u2=\left\langle \argsAT l12\right\rangle $
(i.e., $\protect\ifsAT i2=\left\langle \argsAT l12\right\rangle $).
Additionally, the figure highlights the \emph{indirect}~influence
sources $\protect\nmfAT v1=\left\langle \argsAT l11\right\rangle $,
$\protect\jaGT vt=\left\langle \protect\aAT 11\right\rangle $ and
$\protect\aoHistGT v1=\left\langle \protect\aoHistAT 11\right\rangle $,
which determine the influence that is exerted at stage $\protectt=1$.
(Note that $\argsAT l11$ in fact is also a \emph{direct }influence
source for the influence \emph{experienced at }stage $\protectt=1$.)}

\label{fig:intra-stage-housesearch_influence-sources}
\end{figure}
Fig.~~\ref{fig:intra-stage-housesearch_influence-sources} illustrates
the direct and indirect influence sources for \<housesearch>. In
order to be able to make accurate predictions of the influence destionation
$\argsT f2$ at stage $t=1$, we should be able to predict $\nmfAT v1=\argsAT l11,\jaGT vt=\aAT 11$
as accurately as possible. Given that we assume access to the policy
of agent~$1$, we can equivalently predict $\nmfAT v1=\left\langle \argsAT l11\right\rangle ,\aoHistGT v1=\left\langle \aAT 11\right\rangle $.

\subsubsection{The D-Separating Set}

We now build on this insight to define the d-separating set in problems
with intra-stage dependencies:

\begin{definition}\label{dfn:d-separating-set--IS}The \emph{d-separating
set for agent $i$}, $\dsetA i$, is a subset of variables (state
factors and/or actions), such that the history of these variables
d-separates $\nmfAT wt,\aoHistAT w{t}$ from $\mfAT i{t},\aoHistAT it$.
I.e., it is defined in such a way that
\begin{equation}
\forall_{\nmfAT wt,\aoHistAT w{t}}\qquad\Pr(\nmfAT wt,\aoHistAT w{t}|\mfAT it,\aoHistAT it,\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})=\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i}).\label{eq:dset-def--intrastage}
\end{equation}

\end{definition}

As before this should be interpreted to mean: $\dsetAT i{t+1}$
d-separates $\nmfAT wt,\aoHistAT w{t}$ from those parts of $\mfAT i{t},\aoHistAT it$
(i.e, of the local model) not contained in $\dsetAT i{t+1}$.

Comparing \dfn\ref{dfn:d-separating-set--IS} with the earlier \dfn\ref{dfn:d-separating-set-NO-IS},
we see they are pleasingly similar; all that changed is that $u$'s
have been replaced with $w$' to now take into account the possiblity
of indirect sources.

\subsubsection{Definition of Influence under ISDs}

With this as background, we are now in position to define the concept
of influence in all its generality:

\begin{definition}[Experienced Influence under ISDs]

\label{dfn:influence} The \emph{influence experienced by agent~$i$
at stage $t+1$} is a conditional probability distribution over
the direct influence sources:
\begin{multline}
I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1})\defas\Pr(\left\langle \nmfAT u{t},\jaGT ut,\nmfAT u{t+1}\right\rangle |\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1},{b^{0}},\jpolG{\excl i})\\
=\sum_{\ifsAT i{t+1}=\left\langle \nmfAT v{t},\jaGT vt,\nmfAT v{t+1}\right\rangle }\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})\sum_{\aoHistAT w{t}}\jpolG w(\jaGT wt|\aoHistAT w{t})\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})\label{eq:definition-of-influence}
\end{multline}
where
\begin{itemize}
\item $u$ denote (direct) influence sources;
\item $v$ denote the `second order' sources;
\item $w$ (as above) denotes the union of $u$ and $v$;
\item $\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})$
is the term necessary the predict the intra-stage sources. It is a
term that consists of the product of CPTs;
\item $\jpolG w(\jaGT wt|\aoHistAT w{t})=\prod_{i\in w}\polA i(\aAT i{t}|\aoHistAT i{t})=\jpolG u(\jaGT ut|\aoHistAT u{t})\jpolG v(\jaGT vt|\aoHistAT v{t})$
is the product of action probabilities according to the policies of
the other agents that are relevant directly (the $u$) or indirectly
for intra-stage sources (the $v$);
\item $\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})=\Pr(\nmfAT ut,\nmfAT vt,\aoHistAT u{t},\aoHistAT v{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})$
predicts the non-modeled factors that are relevant directly (the $u$)
or indirectly for intra-stage sources (the $v$), as well as the histories
for the relevant agents.
\end{itemize}
We use $\ifpiAT i{t+1}(\jpolG{\excl i})$ to denote the conditional
distribution $I(\cdot|\dsetAT i{t+1},\mfAT i{t},\aAT i{t},\mfAT i{t+1})$.
\end{definition}

We make a few observations:
\begin{itemize}
\item The term $\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})$
can be simplified as given by \eqref{eq:P(intra-stage-source)}, but
it is important to keep in mind that this resulting term requires
actual inference and is not the product of CPTs anymore.
\item Note that, in many cases, we will consider other agents that use deterministic
policies, however, we chose to give the more general description that
also allows for stochastic policies. In case of deterministic policies,
the summation over $\jaGT vt$ can be omitted, $\jaGT{v/w}t$ can
be replaced by $\jdrGT{v/w}{t}(\oHistAT{v/w}{t})$, and $\aoHistAT w{t}$
becomes $\oHistAT w{t}$.
\item The dependence of $I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1})$
on $\aAT i{t}$ is only needed when $\aAT i{t}$ is an indirect
source (i.e., it is an ancestor of $\nmfAT u{t+1}\text{ or }\nmfAT v{t+1}$).
\end{itemize}

\subsubsection{Exerted vs. Experienced Influence}

Here we make a reinterpretation of the experienced influence at stage
$t+1$ as the result of the influence exterted at stage $t$ plus
the effect of the intra-stage effects. While this does not fundamentally
change anything about the definition of influence per \dfn\ref{dfn:influence},
it may provide some insight on the nature with which influence manifests
itself in settings with intra-stage connections.

In particular, it is possible to define a distribution, only in terms
of variables at stage $t$, which acts as a sufficient statistic
to predict the intra-stage source. The intuition is that the \emph{experienced
influence,} can be thought of as being induced by the \emph{exerted
influence:}\textbf{ }
\begin{itemize}
\item \textbf{Exerted Influence (at stage~$t$):
\begin{equation}
\Pr(\nmfAT wt,\jaGT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})=\Pr(\nmfAT u{t},\nmfAT vt,\jaGT u{t},\jaGT v{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})=\sum_{\aoHistAT w{t}}\jpolG w(\jaGT w{t}|\aoHistAT w{t})\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})\label{eq:exerted_influence}
\end{equation}
}
\item \textbf{Experienced Influence (at $t+1$):
\begin{multline}
I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1})=\Pr(\nmfAT u{t},\jaGT u{t},\nmfAT u{t+1}|\dsetAT i{t+1},\mfAT v{t},\mfAT v{t+1},{b^{0}},\jpolG{\excl i})\\
=\sum_{\left\langle \nmfAT v{t},\jaGT vt,\nmfAT v{t+1}\right\rangle }\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aAT i{t},\jaGT vt,\mfAT v{t+1})\Pr(\nmfAT wt,\jaGT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})\label{eq:experienced_influence}
\end{multline}
}
\end{itemize}
This last equation \eqref{eq:experienced_influence} clearly demonstrates
how the experienced influence is induced by the exerted influence.
The notion of exerted influence \eqref{eq:exerted_influence} lays
a clear link to IBA in settings without ISDs (cf. Equation \ref{eq:IncomingInfluence__non-isd})
and is conceptually useful since it isolates which information needs
to be retained for each stage $t$. As such, we expect that any
practical implementations for computing the influence by means of
filtering (belief tracking) would use this as the primary quantity
of interest.

\subsection{Influence-Augmented Local Model (IALM)}

Here we define the influence-augmented local model under intra-stage
connections. Looking at \dfn\ref{dnf:IALM}, we can conclude that
the only changes that we need to make involve the transition function
\eqref{eq:IALM-T}, repeated here for convience:

\begin{eqnarray*}
\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t}) & = & \Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\prod_{k\in OLAF(i)}\Pr(\mflIT k{t+1}|\mfAT i{t},\aAT i{t}).
\end{eqnarray*}
with
\[
\eqref{eq:P(NLAFS)__general}=\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})=\sum_{\ifsAT i{t+1}}I(\ifsAT i{t+1}|\dsetAT i{t+1})\prod_{k\in NLAF(i)}\Pr(\mfnIT k{t+1}|\mfAT i{t},\aA i,\ifsAT i{t+1})
\]
the probability of of the NLAFs.

In particular, we need to deal with the fact our definition of influence
\eqref{eq:definition-of-influence} can now be of the more complex
form $I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1})$,
as given by \eqref{eq:experienced_influence}. This means that the
NLAF probability $\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aA i,\ifpiAT i{t+1})$
given by \eqref{eq:P(NLAFS)__general} must be updated to deal with
this new form, and this in turn implies that the definition of $\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})$
per \eqref{eq:IALM-T} needs to be updated too.

Let us start with the former. Like \eqref{eq:LFM:T:NLAFs}, this can
now depend on ISDs from OLAFs $\mflAT i{t+1}$

\noindent
\begin{multline}
\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\mflAT i{t+1},\aA i,\ifpiAT i{t+1})\defas\\
\sum_{\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaG u,\nmfAT u{t+1}\right\rangle }I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aAT i{t},\mfAT v{t+1})\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1}),\label{eq:P(NLAFS)__general-IS}
\end{multline}
with $\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})$
simply the product of CPTs of the NLAFs, as given by \eqref{eq:LFM:T:NLAFs},
but now restricted to only $\nmfAT i{t},\nmfAT i{t+1},\jaG{\excl i}$
that are influence sources.

We are now in the position to define the IALM under intra-stage dependencies:

\begin{definition}[IALM]

\label{dnf:IALM-IS} Given an LFM with intra-stage dependences, $\mathcal{M}^{LFM}$,
and profile of policies for other agents~$\jpolG{\excl i}$, an \emph{Influence-Augmented
Local Model (IALM) }for agent~$i$ is a POMDP $\mathcal{M}_{i}^{IALM}(\mathcal{M}^{LFM},\jpolG{\excl i})=\left\langle \bar{\sS},\aAS{i},\bar{T}_{i},\bar{R}_{i},\oAS{i},\bar{O}_{i},h,\lbAT i0\right\rangle $,
where
\begin{itemize}
\item $\bar{\sS},\aAS{i},\bar{R}_{i},\oAS{i},\bar{O}_{i},h,\lbAT i0$ are
identical to those in \dfn\ref{dnf:IALM},
\item $\bar{T}_{i}$ is the transition function is defined as:
\end{itemize}
\begin{multline}
\bar{T}_{i}(\sAugAT i{t+1}|\sAugAT it,\aAT i{t})\defas\Pr(\mfAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\aAT i{t},\ifpiAT i{t+1})\KroD{\dsetAT i{t+2}}{d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})}\\
=\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\mflAT i{t+1},\aA i,\ifpiAT i{t+1})\Pr(\mflAT i{t+1}|\mfAT i{t},\mfnAT i{t+1},\aA i)\KroD{\dsetAT i{t+2}}{d(\mfAT i{t},\aAT i{t},\mfAT i{t+1},\dsetAT i{t+1})},\label{eq:IALM-T-IS}
\end{multline}
with the first term is given by \eqref{eq:P(NLAFS)__general-IS} and
the second term is given by \eqref{eq:LFM:T:OLAFs}.

\end{definition}

\subsection{Planning in an IALM with ISDs}

\label{sec:ISD:planning}

Since the only modifications that we needed to make to incorporate
ISDs were in the transition function, the conclusions about how to
plan in IALM made in \sect\ref{sec:IBA:planning} remain valid. In
particular, the IALM is still a POMDP, with a well-defined belief-update
function, and value functions. The solution of the IALM still gives
the influence-based best-response value, defined in \eqref{eq:V(b0)_inf}
as the value of the initial local-form belief: $V_{i}(\ifpiA i(\polA{\excl i}))\defasV{}_{i}(\lbAT i0).$

\section{Sufficiency of Influence-Based Abstraction}

\label{sec:Sufficiency}

In this secion, we will show that influence-based abstraction is \emph{completely
lossless. }By that we mean that an IALM constructed according to \dfn\ref{dnf:IALM-IS}
can be used to accurately predict rewards and observations, and thus
to compute an exact, optimal (best-response) value.

The latter is our main result, Theorem~\ref{thm:V_IALM=00003DV_GFBRM},
which shows that the optimal values for the GFBRM and the IALM are
equal, thus establishing that one can use the IALM to plan (or learn)
in without any loss in value. In other words, it proves that the definition
of influence actually constitutes a sufficient statistic for predicting
the optimal value, and thus that resulting IALM actually achieves
a best-response against the policy $\polA{\excl i}$ that generated
the influence $\ifpiA{i}(\polA{\excl i})$.

\begin{theorem}\label{thm:V_IALM=00003DV_GFBRM}For a finite-horizon
POSG, the solution of the IALM for the incoming influence point $\ifpiA{i}(\polA{\excl i})$
associated with any $\polA{\excl i}$ achieves the same value $V_{i}(\ifpiA{i}(\polA{\excl i}))$,
given by \eqref{eq:V(b0)_inf}, as the best-response value $V_{i}(\polA{\excl i})$,
given by \eqref{eq:V(b0)_JESP}, computed against $\polA{\excl i}$
directly:
\begin{equation}
\forall_{\polA{\excl i}}\quad V_{i}(\ifpiA{i}(\polA{\excl i}))=V_{i}(\polA{\excl i}).\label{eq:thm:sufficiency}
\end{equation}
 \end{theorem}

To prove this (in \sect\ref{sec:suff:proof-of-theorem}) we will
show that the immediate reward terms and observation probabilities
are equal (\sect\ref{sec:suff:rewards-and-obs}). In turn, to show
this, we will need to show that transition probabilities are the same
given a local-form belief and a global-form belief, which means that
the local-form belief is a sufficient statistic to predict the next
local state (\sect\ref{sec:suff:local-transitions}). In order to
allow the rewriting to take place, we first show how the global-form
belief can be factorized.

We believe that this proof by itself is useful: it isolates the core
technical property that needs to hold for sufficiency in Lemma~\ref{lem:localTransitionSufficiency_Pxmxm}
in \sect\ref{sec:suff:local-transitions}. In this way it 1) conveys
insight into the nature of how abstraction of state latent factors
affects value, 2) provides a derivation that can be used to obtain
simplifications of the definition of influence (\dfn\ref{dfn:influence})
in simpler cases, and 3) provides a recipe of how to prove similar
results in problems which add even more complexities.

\subsection{Factorization Of Global-Form Belief}

\label{sec:Suffciency:factorization-of-global-form-belief}

In order to prove the equivalence of the GFBRM and the IALM, we will
show that their value functions are the same. In order to do that,
it will be necessary to decompose the global-form belief~$\gbA i$
in components.

To do that, we make use of the insight that, for any $\dsetAT i{t+1}$,
the law of total probability allows us to write
\begin{equation}
\gbA i(\sT{t},\aoHistAT{\excl i}{t})=\sum_{\dsetAT i{t+1}}\bA i(\left\langle \mfAT i{t},\nmfAT it\right\rangle ,\aoHistAT{\excl i}{t},\dsetAT i{t+1})=\sum_{\dsetAT i{t+1}}\bA i(\mfAT i{t},\dsetAT i{t+1})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1}).\label{eq:gfb_factored_Dt}
\end{equation}

\noindent Also, it is important to remember that the belief is \emph{defined}
as
\[
\gbA i(\sT{t},\aoHistAT{\excl i}{t})\defas\Pr(\sT{t},\aoHistAT{\excl i}{t}|\aoHistAT it,{b^{0}},\jpolG{\neq i}),
\]
 which means that in \eqref{eq:gfb_factored_Dt}, the definitions
of the components are
\begin{eqnarray}
\bA i(\mfAT i{t},\dsetAT i{t+1}) & \defas & \Pr(\mfAT i{t},\dsetAT i{t+1}|\aoHistAT it,{b^{0}},\jpolG{\neq i}),\label{eq:b(fi,mi,Di)}\\
\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1}) & \defas & \Pr(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1},\aoHistAT it,{b^{0}},\jpolG{\neq i}).\label{eq:b(fj,oj)}
\end{eqnarray}

These equations further clarify how to think about inclusion of actions
$\aA i$ and observations $\oA i$ inside the d-separating set $\dsetAT i{t+1}$:
the belief \emph{per definition} conditions on the history of actions
and observations, as such these can be included in $\dsetAT i{t+1}$
without further problems. In particular, suppose that $a_{i}^{k}$
is part of d-separating set $\dsetAT i{t+1}$, then this will lead
to $\Pr(\mfAT i{t},\left\langle \dots a_{i}^{k}\dots\right\rangle |\left\langle \dots a_{i}^{k}\dots\right\rangle ,{b^{0}},\jpolG{\neq i})$
in \eqref{eq:b(fj,oj)}. However, the interpretation is simply that
this does not influence the probabilities, since $P(x|x)=1$. Similarly,
it would lead to a term $\Pr(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\left\langle \dots a_{i}^{k}\dots\right\rangle ,\left\langle \dots a_{i}^{k}\dots\right\rangle ,{b^{0}},\jpolG{\neq i})$
in \eqref{eq:b(fj,oj)}. Again, this poses no problem, since $\Pr(y|x,x)=\Pr(y|x)$.
However, let us repeat that we do need all observation relevant state
factors in the local state: otherwise we cannot define the local observation
model $\bar{O}_{i}$ and track the local-form belief $\bA i(\mfAT i{t},\dsetAT i{t+1})$
(cf. \dfn\ref{dfn:lfm} and \dfn\ref{dnf:IALM}).

\subsection{Sufficiency for Prediction Local State Transitions}

\label{sec:suff:local-transitions}

In this section, we show that the influence together with the local-form
belief is sufficient to predict local state transitions. We first
prove the following lemma, that shows that pairwise marginal distributions
over states are the same in the IALM and the GFBRM. This will then
be used in other proofs.

\begin{lemma}

\label{lem:localTransitionSufficiency_Pxmxm}

The joint distribution over current local state and next local state
induced by a local-form belief is identical to that of the global-form
belief:

\[
\forall_{\aoHistAT i{t}}\forall_{\mfAT i{t},\mfAT i{t+1}}\qquad\Pr(\mfAT i{t},\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i})=\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1}),
\]
where $\lbA i,\,\gbA i$ denote the for the local-form and global-form
beliefs induced by $\aoHistAT i{t}$.

\end{lemma} \begin{proof} We assume arbitrary $\aoHistAT i{t},\mfAT i{t},\mfAT i{t+1}$,
and start with the left-hand side, which is given by \eqref{eq:P_xmxm_gfb}:
{\scriptsize
\begin{align}
 & \sum_{\nmfAT i{t}}\sum_{\jaG{\excl i}}\Pr(\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\gbA i(\sT{t},\aoHistAT{\excl i}{t})\nonumber \\
= & \text{\{via \eqref{eq:gfb_factored_Dt}\}}\nonumber \\
 & \sum_{\nmfAT i{t}}\sum_{\jaG{\excl i}}\Pr(\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\left[\sum_{\dsetAT i{t+1}}\bA i(\mfAT i{t},\dsetAT i{t+1})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\right]\\
= & \text{\{via \eqref{eq:P_xm_sa}\}}\nonumber \\
 & \sum_{\nmfAT i{t}}\sum_{\jaG{\excl i}}\left[\sum_{\nmfAT i{t+1}}\Pr(\nmfAT i{t+1},\mfAT i{t+1}|\sT{t},\aA i,\jaG{\excl i})\right]\sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\sum_{\dsetAT i{t+1}}\bA i(\mfAT i{t},\dsetAT i{t+1})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\\
= & \text{\{via \eqref{eq:P_xxm_sa__LFM_transitionProbs}\}}\nonumber \\
 & \sum_{\nmfAT i{t}}\sum_{\jaG{\excl i}}\sum_{\nmfAT i{t+1}}\Pr(\mflAT i{t+1}|\mfAT i{t},\aA i,\mfnAT i{t+1})\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\nmfAT u{t},\nmfAT u{t+1},\jaG u)\Pr(\nmfAT i{t+1}|\mfAT i{t},\nmfAT i{t},\aA i,\jaG{\excl i},\mfAT i{t+1})\nonumber \\
 & \sum_{\aoHistAT{\excl i}{t}}\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\sum_{\dsetAT i{t+1}}\bA i(\mfAT i{t},\dsetAT i{t+1})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\\
= & \text{\{reordering terms\}}\nonumber \\
 & \sum_{\dsetAT i{t+1}}\Pr(\mflAT i{t+1}|\mfAT i{t},\aA i,\mfnAT i{t+1})\bA i(\mfAT i{t},\dsetAT i{t+1})\nonumber \\
 & \left[\sum_{\jaG{\excl i}}\sum_{\aoHistAT{\excl i}{t}}\sum_{\nmfAT i{t}}\sum_{\nmfAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\nmfAT u{t},\nmfAT u{t+1},\jaG u)\Pr(\nmfAT i{t+1}|\mfAT i{t},\nmfAT i{t},\aA i,\jaG{\excl i},\mfAT i{t+1})\Pr(\jaG{\excl i}|\aoHistAT{\excl i}{t},\jpolG{\excl i})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\right]\label{eq:eq-with-bracketed-part}
\end{align}
}

This equation has grouped together all the probabilities that are
affected by the non-local part of the problem in the bracketed part.
The terms before do not depend on the external part at all. We will
now further investigate the externally influence (bracketed) part:

{\scriptsize

\begin{align}
 & \sum_{\jaG{\excl i}}\sum_{\aoHistAT{\excl i}{t}}\sum_{\nmfAT i{t}}\sum_{\nmfAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\Pr(\nmfAT i{t+1}|\mfAT i{t},\nmfAT i{t},\aA i,\jaG{\excl i},\mfAT i{t+1})\jpolG{\excl i}(\jaG{\excl i}|\aoHistAT{\excl i}{t})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\nonumber \\
= & \sum_{\jaG{\excl i}}\sum_{\nmfAT i{t}}\sum_{\nmfAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\Pr(\nmfAT i{t+1}|\mfAT i{t},\nmfAT i{t},\aA i,\jaG{\excl i},\mfAT i{t+1})\sum_{\aoHistAT{\excl i}{t}}\jpolG{\excl i}(\jaG{\excl i}|\aoHistAT{\excl i}{t})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\nonumber \\
= & \text{\{restricting to the intra-stage sources \ensuremath{\nmfAT u{t+1}}and their intra-stage ancestors \ensuremath{\nmfAT v{t+1}}, other factor's probabilities just sum to 1\}}\nonumber \\
 & \sum_{\jaG{\excl i}}\sum_{\nmfAT i{t}}\sum_{\nmfAT u{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\sum_{\nmfAT v{t+1}}\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT i{t},\nmfAT i{t},\aA i,\jaG{\excl i},\mfAT i{t+1})\sum_{\aoHistAT{\excl i}{t}}\jpolG{\excl i}(\jaG{\excl i}|\aoHistAT{\excl i}{t})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\nonumber \\
= & \text{\{restricting to \ensuremath{\jaG v,\mfAT v{t+1}} that actually influence \ensuremath{\ensuremath{\nmfAT u{t+1}}}. I.e.,\,\ensuremath{v}\, denotes other `second order' sources\}}\nonumber \\
 & \sum_{\jaG{\excl i}}\sum_{\nmfAT i{t}}\sum_{\nmfAT u{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\sum_{\nmfAT v{t+1}}\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aA i,\jaG v,\mfAT v{t+1})\sum_{\aoHistAT{\excl i}{t}}\jpolG{\excl i}(\jaG{\excl i}|\aoHistAT{\excl i}{t})\bA i(\nmfAT it,\aoHistAT{\excl i}{t}|\mfAT i{t},\dsetAT i{t+1})\nonumber \\
 & \text{\{cf notes about \ensuremath{\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aA i,\jaG v,\mfAT v{t+1})} \}}\\
= & \text{\{pushing in summations, recall \ensuremath{\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaG u,\nmfAT u{t+1}\right\rangle }\}}\nonumber \\
 & \sum_{\ifsAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\sum_{\jaG v}\sum_{\nmfAT v{t}}\sum_{\nmfAT v{t+1}}\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aA i,\jaG v,\mfAT v{t+1})\sum_{\aoHistAT u{t}}\sum_{\aoHistAT v{t}}\jpolG{u\cup v}(\jaG u,\jaG v|\aoHistAT u{t},\aoHistAT v{t})\bA i(\nmfAT ut,\nmfAT vt,\aoHistAT u{t},\aoHistAT v{t}|\mfAT i{t},\dsetAT i{t+1})\\
= & \text{\{let \ensuremath{w=u\cup v}\}}\nonumber \\
 & \sum_{\ifsAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\sum_{\jaG v}\sum_{\nmfAT v{t}}\sum_{\nmfAT v{t+1}}\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aA i,\jaG v,\mfAT v{t+1})\sum_{\aoHistAT w{t}}\jpolG w(\jaG w|\aoHistAT w{t},\jpolG w)\bA i(\nmfAT wt,\aoHistAT w{t}|\mfAT i{t},\dsetAT i{t+1})\nonumber \\
= & \text{\{since \ensuremath{\bA i(\nmfAT wt,\aoHistAT w{t}|\mfAT i{t},\dsetAT i{t+1})\defas\Pr(\nmfAT wt,\aoHistAT w{t}|\mfAT i{t},\dsetAT i{t+1},\aoHistAT it,{b^{0}},\jpolG{\excl i})\overset{\text{\{def. of d-set \eqref{eq:dset-def--intrastage}}\}}{=}\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i})} \}}\nonumber \\
\nonumber \\
 & \sum_{\ifsAT i{t+1}}\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\ifsAT i{t+1})\sum_{\left\langle \nmfAT v{t},\jaG v,\nmfAT v{t+1}\right\rangle }\Pr(\nmfAT u{t+1},\nmfAT v{t+1}|\mfAT v{t},\nmfAT v{t},\aA i,\jaG v,\mfAT v{t+1})\sum_{\aoHistAT w{t}}\jpolG w(\jaG w|\aoHistAT w{t})\Pr(\nmfAT wt,\aoHistAT w{t}|\dsetAT i{t+1},{b^{0}},\jpolG{\excl i}).\label{eq:ExternalPart_preInfluence}
\end{align}

We can now apply the definition of influence (\dfn\ref{dfn:influence})
to \eqref{eq:ExternalPart_preInfluence}, which yields

\begin{equation}
=\sum_{\ifsAT i{t+1}=\left\langle \nmfAT u{t},\jaG u,\nmfAT u{t+1}\right\rangle }\Pr(\mfnAT i{t+1}|\mfAT i{t},\mflAT i{t+1},\aA i,\nmfAT u{t},\jaG u,\nmfAT u{t+1})I(\ifsAT i{t+1}|\dsetAT i{t+1},\mfAT v{t},\aA i,\mfAT v{t+1}),\label{eq:ExternalPart_postInfluence}
\end{equation}
which is the definition \eqref{eq:P(NLAFS)__general-IS} of $\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\mflAT i{t+1},\aA i,\ifpiAT i{t+1})$.
\textbf{}

Substituting \eqref{eq:ExternalPart_postInfluence} back in \eqref{eq:eq-with-bracketed-part}
we get

\begin{align*}
 & \sum_{\dsetAT i{t+1}}\Pr(\mflAT i{t+1}|\mfAT i{t},\mfAT i{t+1},\mfnAT i{t+1},\aA i)\bA i(\mfAT i{t},\dsetAT i{t+1})\left[\Pr(\mfnAT i{t+1}|\langle\mfAT i{t},\dsetAT i{t+1}\rangle,\mflAT i{t+1},\aA i,\ifpiAT i{t+1})\right]\\
= & \text{\{via \ref{eq:IALM-T-IS} \}}\\
 & \sum_{\dsetAT i{t+1}}\Pr(\mfAT i{t+1}|\mfAT i{t},\dsetAT i{t+1},\aA i,\ifpiAT i{t+1})\bA i(\mfAT i{t},\dsetAT i{t+1})\overset{\text{\{via \eqref{eq:P_xmxm_lfb}\}}}{=}\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1}),
\end{align*}
which concludes the proof.\end{proof}

\begin{lemma}

\label{lem:localTransitionSufficiency_Pxm}

A local-form belief is a sufficient statistic for prediction the next
local state. That is, when $\lbA i,\,\gbA i$ denote the for the local-form
and global-form beliefs induced by the same action-observation history
$\aoHistAT i{t}$, we have that:

\begin{equation}
\forall_{\aoHistAT i{t}}\forall_{\mfAT i{t+1}}\qquad\Pr(\mfAT i{t+1}|\gbA i,\aA i,\jpolG{\excl i})=\Pr(\mfAT i{t+1}|\lbA i,\aA i,\ifpiAT i{t+1}).\label{eq:lem:local_state_prediction_sufficiency}
\end{equation}
\end{lemma}\begin{proof} This follows directly from Lemma~\eqref{lem:localTransitionSufficiency_Pxmxm}:

\[
\Pr(\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})=\sum_{\mfAT i{t}}\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})=\sum_{\mfAT i{t}}\Pr(\mfAT i{t},\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i})=\Pr(\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i}).\qedhere
\]
\end{proof}

\subsection{Sufficiency for Predicting Rewards and Observations}

\label{sec:suff:rewards-and-obs}

Given that we established that local-form beliefs in an IALM are sufficient
to predict local-state transitions, we can now also establish their
sufficiency for predicting rewards and observations.

\begin{lemma}\label{lem:RewardSufficiency} The local-form belief
is a sufficient statistic to predict the immediate reward. That is

\begin{equation}
\forall_{\aoHistA i}\forall_{\aA i}\qquad\RA i(\gbA i,\aA i)=\RA i(\lbA i,\aA i)\label{eq:RewardEquality}
\end{equation}
where $\lbA i,\,\gbA i$ denote the for the local-form and global-form
beliefs induced by $\aoHistA i$. \end{lemma} \begin{proof} Comparing
equations \eqref{eq:R(gfb,a)__LFM} and \eqref{eq:R(lfb,a)}, we see
that this holds if $\Pr(\mfAT i{t},\mfAT i{t+1}|\gbA i,\aAT it,\jpolG{\excl i})=\Pr(\mfAT i{t},\mfAT i{t+1}|\lbA i,\aAT it,\ifpiAT i{t+1})$.
This is precisely what Lemma~\ref{lem:localTransitionSufficiency_Pxmxm}
shows.\end{proof}

\begin{lemma}\label{lem:observation_suficiency} The local-form belief
is a sufficient statistic for predicting the observation. That is:
\begin{equation}
\forall_{\aoHistA i}\forall_{\aA i,\oA i}\qquad\Pr(\oA i|\gbA i,\aA i)=\Pr(\oA i|\lbA i,\aA i),\label{eq:observationEquality}
\end{equation}
where $\lbA i,\,\gbA i$ denote the for the local-form and global-form
beliefs induced by $\aoHistA i$.\end{lemma}\begin{proof} \sloppy Comparing
equations \eqref{eq:P(o|gfb,a)__LFM} and \eqref{eq:P(o|lfb,a)},
we see that equality holds if $\Pr(\mfAT i{t+1}|\gbA i,\aA i,\jpolG{\excl i})=\Pr(\mfAT i{t+1}|\lbA i,\aA i,\ifpiAT i{t+1})$;
this is exactly what Lemma~\ref{lem:localTransitionSufficiency_Pxm}
shows.\end{proof}

\subsection{Proof of Theorem~\ref{thm:V_IALM=00003DV_GFBRM}: Sufficiency for
Predicting Optimal (Best-Response) Value}

\label{sec:suff:proof-of-theorem}

The values in \eqref{eq:thm:sufficiency} are defined as the value
of the initial beliefs, cf. equations \eqref{eq:V(b0)_inf} and \eqref{eq:V(b0)_JESP},
and we will show that these values are equal. The proof is by induction
over the horizon, where the base case is given by the last stage.

\paragraph*{Base Case.}

Assume an arbitrary last-stage AOH, $\aoHistAT i{\h-1}$, and let
$\lbA i,\,\gbA i$ denote the for the local-form and global-form beliefs
induced by it. Their respective values are given by
\[
V{}_{i}(\gbA i)=\max_{\aA i}\RA i(\gbA i,\aA i),
\]
\[
V{}_{i}(\lbA i)=\max_{\aA i}\RA i(\lbA i,\aA i).
\]
So we need to show that the predicted immediate rewards are equal.
This, however, is exactly what Lemma~\ref{lem:RewardSufficiency}
shows.

\paragraph*{Induction Step.}

The induction hypothesis is that, for stage $t+1$,
\[
\forall_{\aoHistAT i{t+1}}\qquadV{}_{i}^{t+1}(\lbAT i{t+1})=V{}_{i}^{t+1}(\gbAT i{t+1}),
\]
where we write $\lbAT i{t+1},\,\gbAT i{t+1}$ are the local-form
and global-form beliefs induced by $\aoHistAT i{t+1}$.

Now we need to prove that $V{}_{i}^{t}(\lbA i)=V{}_{i}^{t}(\gbA i)$,
for all $\aoHistAT i{t}$. We will show this by proving that equality
hold for the Q-values. Assume and arbitrary $\aoHistAT i{t}$, its
Q-values are given by \eqref{eq:Q(b,a)__GFBRM}:

\[
Q_{i}(\gbA i,\aA i)=R_{i}(\gbA i,\aA i)+\gamma\sum_{\oA i}\Pr(\oA i|\gbA i,\aA i)\argsAT{V}{i}{t+1}(BU(\gbA i,\aA i,\oA i))
\]

By the induction hypothesis, we get
\[
Q{}_{i}^{t}(\gbA i,\aA i)=\RA i(\gbA i,\aA i)+\sum_{\oA i}\Pr(\oA i|\gbA i,\aA i)\argsAT{V}{i}{t+1}(BU(\lbA i,\aA i,\oA i)).
\]
(Note that $BU(\gbA i,\aA i,\oA i)$ and $BU(\lbA i,\aA i,\oA i)$
are the local-form and global-form beliefs induced by the same next-stage
history $\aoHistAT i{t+1}=(\aoHistAT i{t},\aA i,\oA i)$, and
hence the induction hypothesis applies.)

So, in order to show that this is equal to
\[
Q{}_{i}^{t}(\lbA i,\aA i)=\RA i(\lbA i,\aA i)+\sum_{\oA i}\Pr(\oA i|\lbA i,\aA i)\argsAT{V}{i}{t+1}(BU(\lbA i,\aA i,\oA i))
\]
we need to show equality for both the immediate rewards, $\RA i(\gbA i,\aA i)=\RA i(\lbA i,\aA i)$,
and the observation probabilities, $\Pr(\oA i|\gbA i,\aA i)=\Pr(\oA i|\lbA i,\aA i)$.
The former was shown in Lemma~\ref{lem:RewardSufficiency} and the
latter was shown in Lemma~\ref{lem:observation_suficiency}. \qed

\section{Conclusion, Discussion and Future Work}

\label{sec:conclusions}

This paper makes a theoretical contribution to the field of decision
making in factored multiagent settings. It defines a formulation of
`influence' that enables an agent to perform, under certain assumptions,
a lossless abstraction of the decision making problem it faces. That
is, we prove that, for a given abstraction in terms of a \emph{local-form
}model, an \emph{influence point} is a sufficient statistic for the
part of the problem that is abstracted away. The local-form model
and influence point together induce what we call an \emph{influence-augmented
local model}:\emph{ }a local model that is sufficient to compute a
best response.

The proof of sufficiency is not only a validation of the theory. It
also serves a practical purpose: it isolates the core technical property
that needs to hold for sufficiency in Lemma~\ref{lem:localTransitionSufficiency_Pxmxm}
in \sect\ref{sec:suff:local-transitions}. In this way it 1) conveys
insight into the nature of how abstraction of state latent factors
affects value, 2) provides a derivation that can be used to obtain
simplifications of the definition of influence (\dfn\ref{dfn:influence})
in simpler cases, and 3) provides a recipe of how to prove similar
results in problems which add even more complexities.

We emphasize that this definition of influence is not a magic bullet:
while the influence-augmented local model is sufficient to compute
a best-response locally, the computation of the required influence
point itself is an intractable inference problem in general. However,
in certain specific cases where this problem \emph{is} feasible it
can enable faster best-response computations and search for multiagent
plans via \emph{influence search }\cite{Witwicki10ICAPS,Witwicki12AAMAS}.
As such, an important direction of future work would investigate how
the definition of influence presented in this paper can support influence
search in more general settings.

Moreover, even in cases where influences are intractable to compute,
the concept forms the basis for principled approximations. For instance,
by being \emph{optimistic} with respect to the influence sources,
one is able to compute upper bounds on the optimal value of Dec-POMDPs
with hundreds of agents, thus leading to firm guarantees on the quality
of heuristic solutions \cite{Oliehoek15IJCAI}. Furthermore, there
is preliminary evidence, in the context of deep reinforcement learning,
that such approximate versions of influence may in some problems improve
learning, both in terms of speed as performance \cite{Suau19ALA}.
As such, a fruitful direction of research is to better understand
such approximate characterization of influence. This document has
provided the foundations for such an exploration.

Finally, we note that even though the discussion in this paper was
based on the more general case of multiagent systems, there is nothing
that stops us from applying IBA in complex systems with just a single
agent. If this can lead to benefits remains to be demonstrated.

\section*{Acknowledgments}

We would like to thank Rolf Starre and Elena Congeduti for their helpful
comments. This paper is the result of research that received funding
from various funding agencies, including AFOSR (MURI), NWO (VENI),
and the European Research Council (ERC) under the European Union's
Horizon 2020 research and innovation programme (grant agreement No.~758824\textemdash INFLUENCE).
\begin{flushright}
\includegraphics[width=2cm]{figs/LOGO_ERC-FLAG_EU}
\par\end{flushright}

redpajama_set_name: RedPajamaArXiv