# Policy Evaluation in Decentralized POMDPs
with Belief Sharing

Mert Kayaalp, Fatima Ghadieh, and Ali H. Sayed M. Kayaalp and A. H. Sayed are
with Adaptive Systems Laboratory, École Polytechnique Fédérale de Lausanne
(EPFL), Switzerland. F. Ghadieh is with American University of Beirut,
Lebanon. Part of her work was performed while she was a student intern at the
Adaptive Systems Laboratory, EPFL. Corresponding author: M. Kayaalp. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Most works on multi-agent reinforcement learning focus on scenarios where the
state of the environment is fully observable. In this work, we consider a
cooperative policy evaluation task in which agents are not assumed to observe
the environment state directly. Instead, agents can only have access to noisy
observations and to belief vectors. It is well-known that finding global
posterior distributions under multi-agent settings is generally NP-hard. As a
remedy, we propose a fully decentralized belief forming strategy that relies
on individual updates and on localized interactions over a communication
network. In addition to the exchange of the beliefs, agents exploit the
communication network by exchanging value function parameter estimates as
well. We analytically show that the proposed strategy allows information to
diffuse over the network, which in turn allows the agents’ parameters to have
a bounded difference with a centralized baseline. A multi-sensor target
tracking application is considered in the simulations.

###### Index Terms:

multi-agent reinforcement learning, distributed state estimation, partially
observable Markov decision process, belief state, value function learning

##  I Introduction

Multi-agent reinforcement learning (MARL) [1, 2] is a useful paradigm for
determining optimal policies in sequential decision making tasks involving a
group of agents. MARL has been applied successfully in several contexts,
including sensor networks [3, 4], team robotics [5], and video games [6, 7].
MARL owes this success in part to recent developments in better function
approximators such as deep neural networks [8].

Many works on MARL focus on the case where agents can directly observe the
global state of the environment. However, in many scenarios, agents can only
receive partial information about the state. The decentralized partially
observable Markov decision process (Dec-POMDP) framework [9] is applicable to
these types of situations. However, a large body of MARL work assumes that
Dec-POMDPs observe data that are deterministic and known functions of the
underlying state, which is not the case in general. Consider, for example,
robots that receive noisy observations from their sensors. The underlying
observation model is stochastic in this case.

Under stochastic observation models, one common strategy is to keep track of
the posterior distribution (belief) over the set of states, which is known to
be a sufficient statistic of the history of the system [10, 11]. For single
agents, this posterior distribution can be obtained at each iteration with the
optimal Bayesian filtering recursion [12]. Unfortunately, for multi-agent
systems, forming this global posterior belief requires aggregation of all data
from across all agents in general. The agents can form it in a distributed
manner only when they have access to the private information from other agents
in the network. And even when agents have access to this level of global
knowledge, the computational complexity of forming the global posterior
distribution is known to be NP-hard [13] in addition to its large memory
requirements. Moreover, obtaining beliefs necessitates significant knowledge
about the underlying model of the environment, which is generally not
available in practice.

Therefore, instead of forming beliefs, most MARL algorithms [14, 15, 16]
resort to a model-free and end-to-end approach where agents try to
simultaneously learn a policy and an embedding of the history that can replace
the beliefs (e.g., recurrent neural networks (RNNs)). Nevertheless, recent
empirical works suggest that this model-free approach can be sub-optimal when
the underlying signals of the environment are too weak to train a model such
as RNN [17, 18]. Moreover, RNNs (or alternative machine learning models) are
usually treated as black boxes. In other words, these algorithms lack model
interpretability, which is critical for trustworthy systems (see [19]).
Furthermore, even though end-to-end approaches have shown remarkable
performance empirically, they are still based on heuristics and lack
theoretical guarantees on their performance. Compared to modular approaches,
they are inefficient in terms of adaptability and generalization to similar
tasks.

As an alternative, there is a recent interest towards improving belief-based
MARL approaches [20, 21, 22]. These works have focused on emulating
conventional beliefs with generative models, or with models learned from
action/observation trajectories (in a supervised fashion). In this paper, we
also examine belief-based strategies for MARL. In particular, we are
interested in the multi-agent policy evaluation problem. Our work complements
[20, 21, 22] in the sense that we assume that agents are already capable of
forming _local_ beliefs with sufficient model knowledge or with generative
models. Our focus is on the challenge of approximating the _global_ Bayesian
posterior in a _distributed_ manner.

Contributions.

  * •

We consider a Dec-POMDP framework in which agents only know their local
observations, actions, and rewards but they are allowed to communicate with
their immediate neighbors over a graph. In the proposed strategy (Algorithm
2), agents exchange both their belief and value function estimates.

  * •

We show in Theorem 1 that by exchanging beliefs, agents keep a bounded
disagreement with the global posterior distribution, which requires fusing all
observations and actions. Also, exchanging value function parameters enables
agents to cluster around the network centroid for sufficiently small learning
rates (Theorem 2). Furthermore, we prove that the network centroid attains a
bounded difference with a strategy that requires centralized training (Theorem
3).

  * •

By means of simulations, we confirm that agents attain a small mean-square
distance from the network centroid. Moreover, the squared Bellman error (SBE)
averaged over the network is shown to be comparable to the SBE of the
centralized strategy.

Paper Organization. In Sec. II, we present additional related work. In Sec.
III, for ease of exposition and introducing notation, we describe the problem
in single-agent setting. In Sec. IV, we propose algorithms for multi-agent
policy evaluation. Sec. V includes the theoretical results, and Sec. VI
includes numerical simulations.

##  II Other Related Work

Our proposed strategy is based on temporal-difference (TD) learning [23, 24],
and makes use of function approximation. TD-learning for POMDPs are considered
in [25, 26], and function approximations are incorporated in [27, 28], albeit
in single-agent setting. Main contribution of the present work is to the
networked multi-agent setting.

A plethora of work studies decentralized policy evaluation over networks [29,
30, 31, 32, 33, 34, 35, 36, 37]. Distributed versions of the TD-learning with
linear function approximations are considered in [35, 36, 37]. However, these
works assume that either the global state, or a deterministic function of it,
is available to all agents. They overlook the stochastic nature of
observations that takes place in many real-world applications. Also in
deterministic setting, the works [38, 39] examine distributed linear quadratic
control task when agents can observe local states only. In particular, [39]
proposes a cooperative strategy for tracking the global state that exploits
networked communication between agents. However, in this strategy, global
state estimation at each iteration is independent of the previous estimations.
It ignores the correlation between consecutive states. Furthermore,
communication between the agents is utilized only for global state estimation,
and not utilized for local Q-function estimate sharing. In contrast, in the
present work, $(i)$ observations are stochastic, $(ii)$ agents take advantage
of the transition model of the state, and $(iii)$ they exchange value function
parameters with their neighbors as well.

For constructing local beliefs that approximate the global Bayesian posterior,
we extend the diffusion HMM strategy (DHS) [40, 41]. This algorithm requires
only one round of communication per state change, as opposed to other
strategies [42, 43] that require multiple rounds of communication until
network consensus at each iteration. Also, in contrast to other distributed
Bayesian filtering algorithms [44], it does not combine likelihoods of data
from different time instants. Instead, likelihoods are combined with _time-
adjusted_ beliefs. These properties make DHS communication efficient and
successful in tracking highly dynamic state transitions. Note that [40, 41]
deal with state estimation task only, and there are no rewards or actions in
their setting. Therefore, we make proper modifications to the algorithm in the
sequel.

In addition to these, the analysis in the current work is related to
literature on the distributed optimization over networks [45, 46, 47, 48]. In
particular, we adopt the two-step approach from [49, 50, 51]. In the first
step, these works establish that agents cluster around the network centroid,
and then, they show that this centroid converges to a neighborhood of the
optimal solution, under constant learning rates. However, their focus is on
optimization and supervised learning rather than reinforcement learning, which
creates non-trivial distinctions in the analysis.

Notation. Random variables are denoted in bold. For $K$ vectors
$w_{1},w_{2},\dots,w_{K}\in\mathbb{R}^{M}$ of dimension $M\times 1$ each, and
for arbitrary matrices $\\{A,B\\}$, the notation
$\text{col}\\{w_{k}\\}_{k=1}^{K}$ and $\text{diag}{\\{A,B\\}}$ stand for

$\text{col}\\{w_{k}\\}_{k=1}^{K}=\begin{bmatrix}w_{1}\\\ w_{2}\\\ \vdots\\\
w_{K}\end{bmatrix},\quad\text{diag}{\\{A,B\\}}=\begin{bmatrix}A&0\\\
0&B\end{bmatrix}.$ (1)

The all-ones vector of dimension $K$ is denoted by $\mathds{1}_{K}$. The
symbol $\otimes$ represents the Kronecker product. The Kullback-Leibler
divergence [52] between two distributions $\mu_{1},\mu_{2}$ is denoted by
$D_{\textup{KL}}(\mu_{1}||\mu_{2})$. We use the notation “proportional to”,
i.e., $\propto$, whenever the LHS of the expression is the normalized version
of the RHS. For example, for $s\in\mathcal{S}$ and function $f$:

$\displaystyle\mu(s)\propto
f(s)\Longleftrightarrow\mu(s)=\frac{f(s)}{\sum_{s^{\prime}\in\mathcal{S}}f(s^{\prime})}.$
(2)

##  III Preliminaries

In this work, we are interested in multi-agent policy evaluation under
partially observable stochastic environments. For clarity of the exposition
and to motivate the notation, we briefly review the procedure of single-agent
policy evaluation under both fully and partially observable states.

###  III-A Fully-Observable Case

For modeling a learning agent under fully observable and dynamic environments,
the traditional setting is a finite Markov Decision Process (MDP). An MDP is
defined by the quintuple $(\mathcal{S},\mathcal{A},\mathbb{T},\bm{r},\gamma)$,
where $\mathcal{S}$ is a set of states with cardinality $|\mathcal{S}|=S$,
$\mathcal{A}$ is a set of actions, $\mathbb{T}$ is a transition model where
$\mathbb{T}(s^{\prime}|a,s)$ denotes the probability of transitioning from
$s\in\mathcal{S}$ to $s^{\prime}\in\mathcal{S}$ when the agent executes action
$a\in\mathcal{A}$, $\bm{r}(s,a,s^{\prime})$ denotes the reward the agent
receives when it executes action $a$ and the environment transitions from
state $s$ to $s^{\prime}$, and $\gamma\in[0,1)$ is a discount factor that
determines the importance given to immediate rewards $(\gamma\to 0)$ or the
total reward $(\gamma\to 1)$.

The goal of policy evaluation is to learn the value function $V^{\pi}(s)$ of a
target policy $\pi(a|s)$, where the value function is the expected return if
the agent starts from state $s$ and follows policy $\pi$, namely,

$V^{\pi}(s)=\mathbb{E}\Big{[}\sum_{i=0}^{\infty}\gamma^{i}\bm{r}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})|\bm{s}_{0}=s\Big{]},$
(3)

where $\bm{s}_{i}$ is the state at time $i$ and $\bm{a}_{i}$ is the action
chosen by the agent according to the policy,
$\bm{a}_{i}\sim\pi(a|\bm{s}_{i})$. In many applications, the state space is
too large (or infinite), which makes it impractical to keep track of the value
function for all states. Therefore, function approximations are used to reduce
the dimension of the problem. For instance, linear approximations, which are
the focus of the theoretical analysis of this work, correspond to using a
parameter $w^{\circ}~{}\in~{}\mathbb{R}^{M}$ to approximate
$V^{\pi}(s)\approx\phi(s)^{\operatorname{\mathsf{T}}}w^{\circ}$, where
$\phi:\mathcal{S}\to\mathbb{R}^{M}$ is a _pre-defined_ feature mapping for
representing state $s$.

A standard stochastic approximation algorithm to learn $w^{\circ}$ from data
is TD-learning [23, 19] such as the TD(0) strategy [53] and variations
thereof. If we denote the value function estimate at $w\in\mathbb{R}^{M}$ by
$\widehat{V}(s,w)\triangleq\phi(s)^{\operatorname{\mathsf{T}}}w$, then, under
this strategy, the agent first computes the TD-error $\bm{\delta}_{i}$ at time
$i$ by using the observed transition tuple
$(\bm{s}_{i},\bm{r}_{i},\bm{s}_{i+1})$:

$\bm{\delta}_{i}=\bm{r}_{i}+\gamma\widehat{V}(\bm{s}_{i+1},\bm{w}_{i})-\widehat{V}(\bm{s}_{i},\bm{w}_{i}),$
(4)

where $\bm{r}_{i}\triangleq\bm{r}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})$ is the
instantaneous reward at time $i$. Subsequently, the agent uses this error to
update the current parameter estimate $\bm{w}_{i}$ to

$\bm{w}_{i+1}=\bm{w}_{i}+\alpha\bm{\delta}_{i}\nabla_{w}\widehat{V}(\bm{s}_{i},\bm{w}_{i}),$
(5)

where $\alpha>0$ is the learning rate, and

$\displaystyle\nabla_{w}\widehat{V}(\bm{s}_{i},\bm{w}_{i})=\phi(\bm{s}_{i})$
(6)

for the linear function approximation case. This algorithm can be viewed as a
“stochastic gradient algorithm” where the effective stochastic gradient is
$\bm{g}_{i}\triangleq-\bm{\delta}_{i}\phi(\bm{s}_{i})$. In this work, we
consider an $\ell_{2}$-regularized version of the algorithm, which changes the
update step (5) to

$\displaystyle\bm{w}_{i+1}=(1-2\rho\alpha)\bm{w}_{i}+\alpha\bm{\delta}_{i}\nabla_{w}\widehat{V}(\bm{s}_{i},\bm{w}_{i}),$
(7)

where $\rho>0$ is a constant hyper-parameter. As opposed to supervised
learning, regularization is rather under-explored in reinforcement learning,
with notable exceptions in [54, 55]. However, recent work [56, 57] suggests
that regularization can increase generalization and sample-efficiency in
function approximation with over-parameterized models.

###  III-B Partially-Observable Case

In many applications, the agent does not directly observe the state
$\bm{s}_{i}$. For instance, a robot may receive noisy and partially
informative observations from its sensors about the environment. The
observation $\bm{\xi}_{i}$ that the agent receives at time $i$ is generally
assumed to be distributed according to some likelihood function linking it to
the unobservable state, say, $\bm{\xi}_{i}\sim L(\xi|\bm{s}_{i})$, which is
conditioned on $\bm{s}_{i}$. In these scenarios, the agent will need to
estimate the latent state first from the observations. To do so, the agent
will need to learn a probability vector $\bm{\mu}_{i}\in\mathcal{M}(S)$ over
the set of states $\mathcal{S}$, which is called the _belief_ vector [10, 19].
Here, $\mathcal{M}(S)$ denotes the $S$-dimensional probability simplex, and
the entry $\bm{\mu}_{i}(s)\in[0,1]$ of the belief vector quantifies the
confidence the agent has about state $s$ being the true state at time $i$. The
value of $\bm{\mu}_{i}(s)$ corresponds to the posterior probability of $s$
conditioned on the action-observation history (a.k.a. trajectory):

$\boldsymbol{\mathcal{F}}_{i}\triangleq\\{\bm{\xi}_{i},\bm{a}_{i-1},\bm{\xi}_{i-1},\dots\\},$
(8)

which means:

$\bm{\mu}_{i}(s)\triangleq\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i}).$
(9)

This posterior satisfies the following temporal recursion [10, 19, 12]:

$\bm{\mu}_{i}(s)\propto L(\bm{\xi}_{i}|s)\bm{\eta}_{i}(s),$ (10)

where $\bm{\eta}_{i}(s)$ is the time-adjusted prior defined by

$\bm{\eta}_{i}(s)\\!\triangleq\\!\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i-1}^{a})\\!=\\!\\!\\!\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}(s|s^{\prime},\bm{a}_{i-1})\bm{\mu}_{i-1}(s^{\prime}).$
(11)

Here, $\boldsymbol{\mathcal{F}}_{i-1}^{a}$ is the collection of past
observations and actions, i.e.,

$\boldsymbol{\mathcal{F}}_{i-1}^{a}\triangleq\\{\bm{a}_{i-1},\bm{\xi}_{i-1},\bm{a}_{i-2},\dots\\},$
(12)

where it is important to notice that
$\boldsymbol{\mathcal{F}}_{i}=\\{\bm{\xi}_{i}\\}\cup\boldsymbol{\mathcal{F}}_{i-1}^{a}$.
If beliefs are used as substitutes for hidden states, then partially-
observable MDPs (POMDPs) can be treated as _continuous_ MDPs, since beliefs
are continuous even if the number of states is finite. In this way, the policy
evaluation problem would correspond to evaluating $V^{\pi}(\mu)$ where the
value function is now defined as the expected return when the agent starts
from the belief state $\mu$ and follows the policy $\pi(a|\mu)$, namely [10,
19]:

$V^{\pi}(\mu)=\mathbb{E}\Big{[}\sum_{i=0}^{\infty}\gamma^{i}\bm{r}_{i}|\bm{\mu}_{0}=\mu\Big{]}.$
(13)

Observe that, in contrast to the fully-observable case, the agent now chooses
action $\bm{a}_{i}$ according to the policy
$\bm{a}_{i}~{}\sim~{}\pi(a|\bm{\mu}_{i})$, which is conditioned on the belief
vector.

Algorithm (4)–(7) can be adjusted for POMDPs by using the belief vectors
$(\bm{\mu}_{i},\bm{\eta}_{i+1})$ instead of the states
$(\bm{s}_{i},\bm{s}_{i+1})$. Thus, we let

$\bm{\delta}_{i}=\bm{r}_{i}+\gamma\widehat{V}(\bm{\eta}_{i+1},\bm{w}_{i})-\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}),$
(14)

and

$\bm{w}_{i+1}=(1-2\rho\alpha)\bm{w}_{i}+\alpha\bm{\delta}_{i}\nabla_{w}\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}),$
(15)

where the approximations $\widehat{V}(\mu,w)$ are computed by using the
feature vectors $\phi(\mu)$, now dependent on $\mu$, to evaluate
$\widehat{V}(\mu,w)~{}\triangleq~{}\phi(\mu)^{\operatorname{\mathsf{T}}}w$.
Note that from now on $\phi:\mathcal{M}(S)\to\mathbb{R}^{M}$ is a different
feature mapping that represents $\mu$ instead of $s$, and agents’ goal is to
learn $w^{\circ}$ that satisfies
$V^{\pi}(\mu)~{}\approx~{}\phi~{}(\mu)^{\operatorname{\mathsf{T}}}~{}w^{\circ}$.

Observe from (10)–(11) that in order for the agent to update the belief
vectors $(\bm{\mu}_{i},\bm{\eta}_{i+1})$, it needs to know the transition
model $\mathbb{T}$ and the likelihood functions $L(\bm{\xi}_{i}|s)$ for each
state. However, the agent does not need to know the underlying reward model
$\bm{r}$. It can use instantaneous reward samples $\bm{r}_{i}$ to run the
algorithm. In this sense, the algorithm is a mixture of model-based and model-
free reinforcement learning. Motivation for this approach is at least two-
fold. First, in some applications, learning the transition and observation
models from data is inherently easier than learning the reward function. This
is because the reward function can depend on some latent characteristics of
the environment or some human expert, which may be challenging to estimate.
Second, the agent can still run (14)–(15) even if beliefs are not formed
through (10)–(11), but estimated by some other approach, as in [20, 21, 22].

##  IV Multi-Agent Policy Evaluation

We now consider a set $\mathcal{K}$ of $K$ cooperative agents that aim to
evaluate the average value function under a joint policy
$\pi=\\{\pi_{k}\\}_{k=1}^{K}$ that consists of individual policies $\pi_{k}$.
The framework we consider is a _decentralized_ POMDP (Dec-POMDP) [9], which is
defined by the sextuple
$(\mathcal{S},\mathcal{A}_{k},\mathcal{O}_{k},\mathbb{T},\bm{r}_{k},\gamma)$.
Here, the set of states $\mathcal{S}$ and the transition model $\mathbb{T}$
are common to all agents, where the notation $\mathbb{T}(s|s^{\prime},a)$ now
specifies the probability that the environment transitions from $s^{\prime}$
to $s$ when the agents execute the joint action $a=\\{a_{k}\\}_{k=1}^{K}$. The
individual action $a_{k}$ of each agent $k$ takes values from the set
$\mathcal{A}_{k}$, and $\bm{r}_{k}(s,a,s^{\prime})$ is the _local_ reward $k$
gets when the agents execute the collection of actions $a$ and the environment
transitions from $s$ to $s^{\prime}$. Note that this setting covers general
teamwork scenarios where the local reward of an individual agent can be
dependent on all actions, and not only on its own actions. Specifically, it
covers the scenarios that all agents observe the same reward, i.e.,
$\bm{r}_{k}(s,a,s^{\prime})=\bm{r}(s,a,s^{\prime}),\forall k\in\mathcal{K}$.
Remember that agents receive instantaneous rewards as they progress through
the POMDP, and they are not required to know the joint action $a$ from all
agents. Moreover, $\mathcal{O}_{k}$ is a set of _private_ observations. At
each time instant $i$, agent $k$ receives observation
$\bm{\xi}_{k,i}\in\mathcal{O}_{k}$ emitted by state $\bm{s}_{i}$, and assumed
to be distributed according to the local _marginal_ likelihood
$L_{k}(\xi_{k}|\bm{s}_{i})$.

Similar to the single-agent case, Dec-POMDPs can be treated as multi-agent
belief MDPs by replacing the hidden states with joint centralized beliefs
defined by [9, Chap. 2]

$\bm{\mu}_{i}(s)\triangleq\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i})\propto
L(\bm{\xi}_{i}|s)\bm{\eta}_{i}(s).$ (16)

Here, $\boldsymbol{\mathcal{F}}_{i}$ denotes the history of all observations
and past actions from across all agents until time $i$, where in the
definition (8), $\bm{\xi}_{i}\triangleq\\{\bm{\xi}_{k,i}\\}_{k=1}^{K}$ is now
the aggregate of the observations from across the network, and $\bm{a}_{i-1}$
is a tuple aggregating actions from all agents at time $i-1$. Moreover, under
spatial independence, the joint likelihood $L(\bm{\xi}_{i}|s)$ appearing in
(16) is given by

$L(\bm{\xi}_{i}|s)=\prod_{k=1}^{K}L_{k}(\bm{\xi}_{k,i}|s).$ (17)

In a manner similar to the single-agent case, the belief $\bm{\eta}_{i}(s)$ is
the time-adjusted prior conditioned on $\boldsymbol{\mathcal{F}}_{i-1}^{a}$
(12):

$\bm{\eta}_{i}(s)\\!\triangleq\\!\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i-1}^{a})\\!=\\!\\!\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}(s|s^{\prime},\bm{a}_{i-1})\bm{\mu}_{i-1}(s^{\prime}).$
(18)

The goal of policy evaluation is to learn the _team_ value function, which is
the expected average reward of all agents starting from some belief state
$\mu$, i.e.,

$V^{\pi}(\mu)=\mathbb{E}\Big{[}\sum_{i=0}^{\infty}\gamma^{i}\Big{(}\frac{1}{K}\sum_{k=1}^{K}\bm{r}_{k,i}\Big{)}\Big{|}\bm{\mu}_{0}=\mu\Big{]},$
(19)

where $\bm{r}_{k,i}$ denotes the instantaneous local reward agent $k$ gets at
time $i$.

There is one major inconvenience with this approach. In order to compute the
joint belief (16), it is necessary to fuse all observations and actions from
across the agents in a central location. This is possible in settings where
there exists a fusion center. However, many applications rely solely on
localized processing. In the following, we discuss and compare two strategies
for multi-agent reinforcement learning under partial observations: $(i)$ a
centralized strategy, $(ii)$ and a fully decentralized strategy.

###  IV-A Centralized Strategy

In the fully centralized strategy, the state estimation and policy evaluation
phases are centralized and, hence, the setting is equivalent to a single-agent
POMDP, already discussed in Sec. III-B, using the joint likelihood
$L(\bm{\xi}_{i}|s)$ and the average reward $\bm{r}_{i}\triangleq
K^{-1}\sum_{k=1}^{K}\bm{r}_{k,i}$. The fusion center computes the joint belief
(16), and agents take actions based on this joint belief, i.e.,
$\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{i})$. The fusion center then computes
the centralized TD-error:

$\bm{\delta}_{i}=\bm{r}_{i}+\gamma\widehat{V}(\bm{\eta}_{i+1},\bm{w}_{i})-\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}),$
(20)

and updates the estimate to

$\bm{w}_{i+1}=(1-2\rho\alpha)\bm{w}_{i}+\alpha\bm{\delta}_{i}\nabla_{w}\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}).$
(21)

This construction is listed under Algorithm 1.

Algorithm 1 Centralized policy evaluation under POMDPs

1:set initial prior $\eta_{0}(s)>0$, $\forall s\in\mathcal{S}$

2:initialize $w_{0}$

3:while $i\geq 0$ do

4: each agent $k$ observes $\bm{\xi}_{k,i}$

5: collect all observations
$\bm{\xi}_{i}\triangleq\\{\bm{\xi}_{k,i}\\}_{k=1}^{K}$ and evaluate
$\bm{\mu}_{i}(s)\propto L(\bm{\xi}_{i}|s)\bm{\eta}_{i}(s)$ (22)

6: for each agent $k\in\mathcal{K}$ do

7: Take action $\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{i})$

8: Get reward $\bm{r}_{k,i}=\bm{r}_{k}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})$

9: end for

10: then, evolve
$\bm{\eta}_{i+1}(s)=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}(s|s^{\prime},\bm{a}_{i})\bm{\mu}_{i}(s^{\prime})$
(23)

11: average the rewards $\bm{r}_{i}=\frac{1}{K}\sum_{k=1}^{K}\bm{r}_{k,i}$

12: update the model:

13:
$\bm{\delta}_{i}=\bm{r}_{i}+\gamma\widehat{V}(\bm{\eta}_{i+1},\bm{w}_{i})-\widehat{V}(\bm{\mu}_{i},\bm{w}_{i})$
(24)
$\bm{w}_{i+1}=(1-2\rho\alpha)\bm{w}_{i}+\alpha\bm{\delta}_{i}\nabla_{w}\widehat{V}(\bm{\mu}_{i},\bm{w}_{i})$
(25)

14:end while

###  IV-B Decentralized Strategy

The centralized strategy is disadvantageous in the sense that $(i)$ failure of
the fusion center results in failure of the system; $(ii)$ there can be
communication bottlenecks at the fusion center; $(iii)$ and agents can be
spatially distributed to begin with. Therefore, in this section, we propose a
fully decentralized strategy for policy evaluation where agents communicate
with their immediate neighbors only.

####  IV-B1 Decentralized Network Model

We refer to Fig. 1 and assume that the graph is strongly connected [45], which
means that paths exist connecting any pair of agents $(\ell,k)$ in both
directions, and in addition, there exists at least one agent in the graph that
does not discard its own information (i.e., $c_{kk}>0$ for at least one agent
$k$). Under this assumption, the combination matrix $C=[c_{\ell k}]$, where
entry $c_{\ell k}\geq 0$ scales the information agent $k$ receives from agent
$\ell$, becomes primitive. If two agents are not connected by an edge then
$c_{\ell k}=0$. We assume $C$ is symmetric and doubly-stochastic, meaning that

$\sum_{\ell=1}^{K}c_{\ell k}=1,\quad c_{\ell k}=c_{k\ell},$ (26)

or in matrix notation:

$C\mathds{1}_{K}=\mathds{1}_{K},\quad C=C^{\operatorname{\mathsf{T}}}.$ (27)

Figure 1: An illustration of a network model.

####  IV-B2 Local Belief Formation

In the fully decentralized strategy, the agents cannot form the joint belief
(16) since they do not have access to the observations and actions of all
other agents. They, however, can construct local beliefs. To do so, we will
extend the diffusion HMM strategy (DHS) from [40] and [41], which is
originally designed for hidden Markov models, to the current POMDP setting.

In DHS, the global belief vectors $\\{\bm{\mu}_{i},\bm{\eta}_{i}\\}$ are
replaced by local belief vectors $\\{\bm{\mu}_{k,i},\bm{\eta}_{k,i}\\}$, and
the latter are updated by using local observations and by relying solely on
interactions with the immediate neighbors. The original DHS algorithm is
designed for actionless partially observable Markov chains, and each agent can
use the same global transition model. However, in POMDPs, transition of the
global state depends on the joint action, and the agents cannot perform a
_centralized_ time-adjustment step as in (23) since they do not know the
actions of all agents in the network.

Therefore, one strategy is to use a transition model that is obtained by
marginalizing over actions that are unknown to agent $k$. More specifically,
let $a_{{\cal N}_{k}}\in\mathcal{A}_{{\cal N}_{k}}$ denote a tuple of actions
taken by the set of neighbors of agent $k$ (which we are denoting by ${\cal
N}_{k}$). These actions can be assumed to be known by agent $k$ if, for
instance, agents share their actions with their neighbors. Let $a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal N}_{k}}^{c}$ denote the remaining actions by
all other agents in the network, so that $a=a_{{\cal N}_{k}}\cup a_{{\cal
N}_{k}}^{c}$. Then, each agent can use the following _local_ transition model
approximation:

$\mathbb{T}^{\pi}_{k}(s|s^{\prime},a_{{\cal
N}_{k}})\propto\\!\\!\\!\\!\\!\\!\\!\\!\sum_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\\!\mathbb{T}(s|s^{\prime},a_{{\cal
N}_{k}},a_{{\cal N}_{k}}^{c})\pi(a_{{\cal N}_{k}},a_{{\cal
N}_{k}}^{c}|s^{\prime})$ (28)

in lieu of $\mathbb{T}(s|s^{\prime},a)$, to time-adjust its local belief:

$\displaystyle\bm{\eta}_{k,i}(s)=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}^{\pi}_{k}(s|s^{\prime},\bm{a}_{{\cal
N}_{k},i-1})\bm{\mu}_{k,i-1}(s^{\prime}),$ (29)

where $\bm{a}_{{\cal N}_{k},i-1}$ is the tuple of actions taken by the
neighbors of agent $k$ at time instant $i-1$. Moreover, in (28), the notation
$\pi(a|s)$ is now a shorthand for $\pi(a|\mu)$ when

$\mu=[0\dots 1\dots 0]^{\operatorname{\mathsf{T}}},$ (30)

i.e., when the belief attains value 1 for state $s$ and is 0 otherwise. Note
that this construction leads to a richer scenario compared to [40, 41], with
transition models that are different across the agents. The rest of the
algorithm is the same as the DHS strategy. Following (29), and based on the
personal observation $\bm{\xi}_{k,i}$, each agent $k$ forms an _intermediate_
belief using a $\beta$-scaled Bayesian update of the form:

$\displaystyle\bm{\psi}_{k,i}(s)\propto(L_{k}(\bm{\xi}_{k,i}|s))^{\beta}\bm{\eta}_{k,i}(s),$
(31)

where $\beta>0$. Finally, agents in the neighborhood of $k$ share their
intermediate beliefs, which allows agent $k$ to update its belief using the
weighted geometric average expression:

$\displaystyle\bm{\mu}_{k,i}(s)\propto\prod_{\ell\in\mathcal{N}_{k}}\big{(}\bm{\psi}_{\ell,i}(s)\big{)}^{c_{\ell
k}}.$ (32)

This procedure of repeated updating and exchanging of beliefs allows
information to diffuse over the network.

####  IV-B3 Diffusion Policy Evaluation

Using its local belief vectors, each agent $k$ computes a local TD error:

$\bm{\delta}_{k,i}=\bm{r}_{k,i}+\gamma\widehat{V}(\bm{\eta}_{k,i+1},\bm{w}_{k,i})-\widehat{V}(\bm{\mu}_{k,i},\bm{w}_{k,i}),$
(33)

where $\bm{r}_{k,i}=\bm{r}_{k}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})$ is also a
function of the local beliefs since each agent $k$ now executes the action
$\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{k,i})$. Subsequently, each agent $k$
forms an intermediate parameter estimate denoted by

$\bm{z}_{k,i+1}=(1-2\rho\alpha)\bm{w}_{k,i}+\alpha\bm{\delta}_{k,i}\nabla_{w}\widehat{V}(\bm{\mu}_{k,i},\bm{w}_{k,i}).$
(34)

After receiving the intermediate estimates from its neighbors, agent $k$
updates $\bm{w}_{k,i}$ to

$\bm{w}_{k,i+1}=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell k}\bm{z}_{\ell,i+1}.$
(35)

The local adaptation step (34) followed by the combination step (35) are
reminiscent of diffusion strategies for distributed learning [45, 19]. Observe
that there are actually two combination steps involved in diffusion policy
evaluation: the belief combination (32) with geometric averaging (GA), and the
parameter combination (35) with arithmetic averaging (AA). These choices of
fusion rules are supported by recent results in the literature [58, 59] that
promote the use of GA for probability density functions and AA for point
estimates. The listing of the proposed diffusion policy evaluation strategy
for POMDPs appears in Algorithm 2.

Algorithm 2 Diffusion policy evaluation under POMDPs

1:set initial priors $\eta_{k,0}(s)>0$, $\forall s\in\mathcal{S}$ and $\forall
k\in\mathcal{K}$

2:choose $\beta>0$

3:initialize $w_{k,0}$ for $\forall k\in\mathcal{K}$

4:while $i\geq 0$ do

5: each agent $k$ observes $\bm{\xi}_{k,i}$

6: for each agent $k\in\mathcal{K}$ and $s\in\mathcal{S}$ adapt and combine
$\displaystyle\bm{\psi}_{k,i}(s)\propto(L_{k}(\bm{\xi}_{k,i}|s))^{\beta}\bm{\eta}_{k,i}(s)$
(36)
$\bm{\mu}_{k,i}(s)\propto\prod_{\ell\in\mathcal{N}_{k}}\big{(}\bm{\psi}_{\ell,i}(s)\big{)}^{c_{\ell
k}}$ (37)

7: end for

8: for each agent $k\in\mathcal{K}$ do

9: Take action $\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{k,i})$

10: Get reward $\bm{r}_{k,i}=\bm{r}_{k}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})$

11: end for

12: for each agent $k\in\mathcal{K}$ evolve

13: Compute $\mathbb{T}^{\pi}_{k}(s|s^{\prime},\bm{a}_{{\cal N}_{k},i})$ using
(28), and
$\bm{\eta}_{k,i+1}(s)=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}^{\pi}_{k}(s|s^{\prime},\bm{a}_{{\cal
N}_{k},i})\bm{\mu}_{k,i}(s^{\prime})$ (38)

14: end for

15: for each agent $k\in\mathcal{K}$ update locally
$\bm{\delta}_{k,i}=\bm{r}_{k,i}+\gamma\widehat{V}(\bm{\eta}_{k,i+1},\bm{w}_{k,i})-\widehat{V}(\bm{\mu}_{k,i},\bm{w}_{k,i})$
(39)
$\bm{z}_{k,i+1}=(1-2\rho\alpha)\bm{w}_{k,i}+\alpha\bm{\delta}_{k,i}\nabla_{w}\widehat{V}(\bm{\mu}_{k,i},\bm{w}_{k,i})$
(40)

16: end for

17: for each agent $k\in\mathcal{K}$ combine
$\bm{w}_{k,i+1}=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell k}\bm{z}_{\ell,i+1}$ (41)

18: end for

19:end while

Note that the proposed algorithm is advantageous in terms of privacy; since
$(i)$ communicating beliefs allows information diffusion without explicitly
sharing raw observational data, and $(ii)$ exchanging value parameters allows
agents learn the cumulative reward across network without explicitly sharing
local rewards.

##  V Main Results

In this section, we analyze the performance of the decentralized strategy in
Algorithm 2. In particular, we first show in Sec. V-B that the value function
parameters $\\{\bm{w}_{k,i}\\}$ of the agents cluster around the network
centroid. Then, in Sec. V-C, we show that this network centroid has a bounded
difference from the parameter of a baseline strategy (which will be presented
in Algorithm 3). Our analysis relies on bounding the disagreement between the
joint centralized belief $\bm{\mu}_{i}$ and the local estimate
$\bm{\mu}_{k,i}$, which is presented next.

###  V-A Belief Disagreement

In a manner similar to [41], we introduce the following risk functions in
order to assess the disagreement between the local beliefs formed via
(36)–(38) with the joint centralized beliefs formed via (22)–(23):

$\displaystyle J_{k,i}$
$\displaystyle\triangleq\mathbb{E}_{\mathcal{F}_{i}}D_{\textup{KL}}(\bm{\mu}_{i}||\bm{\mu}_{k,i}),$
(42)

and

$\displaystyle\widetilde{J}_{k,i}$
$\displaystyle\triangleq\mathbb{E}_{\mathcal{F}_{i-1}^{a}}D_{\textup{KL}}(\bm{\eta}_{i}||\bm{\eta}_{k,i}).$
(43)

The risks in (42) and (43) measure the disagreement after and before the joint
observation $\bm{\xi}_{i}$, respectively. Remember that [41] considers a naive
state estimation setting rather than a POMDP. Specifically, in their setting,
the transition model does not depend on actions, and it is assumed that every
agent knows the global transition model accurately. In comparison, in the
current work, each agent uses a local approximation for the global transition
model based on (28). Therefore, we need to make some non-trivial adjustments
to the belief disagreement analysis. We begin with adjusting the assumptions
from [41] to our model.

####  V-A1 Modeling Conditions

  * •

Likelihood functions: Each observation has bounded information about the true
state. More formally,

$D_{\textup{KL}}(L_{k}(\xi|s)||L_{k}(\xi|s^{\prime}))<\infty$ (44)

which ensures that likelihoods for each state pair ($s$, $s^{\prime}$) share
the same support, and in addition to this,

$\displaystyle\big{|}\log L_{k}(\xi|s)\big{|}\leq B$ (45)

over its support for each state $s\in\mathcal{S}$ and agent $k\in\mathcal{K}$.

  * •

Transition model: The Markov chain induced by any joint action
$a\in\mathcal{A}$ is _irreducible_ and _aperiodic_. Since the number of states
is finite, this assumption implies that the transition model
$\mathbb{T}(s|s^{\prime},a)$ is ergodic [60, Chap. 2]. Like [41], we focus on
the important class of _geometrically_ ergodic models, which additionally
satisfy the relation $\kappa(\mathbb{T}^{a})\leq\kappa(\mathbb{T})$ for some
constant $\kappa(\mathbb{T})<1$. Here, $\kappa(\mathbb{T}^{a})$ is the
Dobrushin coefficient [12, Chap. 2] defined by:

$\displaystyle\kappa(\mathbb{T}^{a})\triangleq\sup_{s^{\prime},s^{\prime\prime}\in\mathcal{S}}\frac{1}{2}\sum_{s\in\mathcal{S}}\big{|}T_{ss^{\prime}}^{a}-T_{ss^{\prime\prime}}^{a}\big{|},$
(46)

where $T_{ss^{\prime}}^{a}\triangleq\mathbb{T}(s|s^{\prime},a)$ is a generic
entry of the $S\times S$ transition matrix $T^{a}$. Due to space limitations,
we refer the reader to [12, Chap. 2] for a comprehensive discussion on the
Dobrushin coefficient $\kappa(\mathbb{T}^{a})$. In short,
$\kappa(\mathbb{T}^{a})$ quantifies how fast the transition model forgets its
initial conditions. Namely, as $\kappa(\mathbb{T}^{a})\to 0$, past conditions
are forgotten faster. Instances of geometrically ergodic transition models
include transition matrices with all positive elements, or that satisfy the
minorization condition in [12, Theorem 2.7.4]. In addition to this condition
from [40, 41], we have an additional assumption on the transition model to
regulate the disagreement stemming from the local transition model estimates:

######  Assumption 1 (Transition model disagreement).

If the aggregate action $a=a_{k}\cup a_{k}^{c}$ is modified from using $a_{k}$
by agent $k$ to using $a_{k}^{\prime}$, then, for each agent $k$,

$D_{\textup{KL}}\Big{(}\mathbb{T}(s|s^{\prime},a_{k},a_{k}^{c})\big{|}\big{|}\mathbb{T}(s|s^{\prime},a_{k}^{\prime},a_{k}^{c})\Big{)}<\infty,$
(47)

which ensures that transition models induced from different actions share the
same support. Moreover, we assume that over the shared support,

$\Bigg{|}\log\frac{\mathbb{T}(s|s^{\prime},a_{k},a_{k}^{c})}{\mathbb{T}(s|s^{\prime},a_{k}^{\prime},a_{k}^{c})}\Bigg{|}\leq\tau.$
(48)

$\hfill\blacksquare$

####  V-A2 Difference with Centralized Strategy

The following result provides upper bounds on the disagreement measures in
(42)–(43).

######  Theorem 1 (Bounds on belief disagreement).

For each agent $k$, the belief disagreement risks (42) and (43) are bounded
after sufficient iterations, namely, as $i\to\infty$,

$\displaystyle J_{k,i}\leq\frac{2\sqrt{K}\beta\lambda
B}{1-\kappa(\mathbb{T})}+\frac{(K-d_{\textup{min}})\>\tau}{1-\kappa(\mathbb{T})}$
(49)

and

$\displaystyle\widetilde{J}_{k,i}\leq\frac{2\kappa(\mathbb{T})\sqrt{K}\beta\lambda
B}{1-\kappa(\mathbb{T})}+\frac{(K-d_{\textup{min}})\>\tau}{1-\kappa(\mathbb{T})}$
(50)

where $d_{\textup{min}}$ is the minimum degree over the graph, i.e., minimum
number of neighbors any agent over the network possesses, and
$\lambda\triangleq\max\\{|1-\frac{K}{\beta}|,\lambda_{2}\\}$ where
$\lambda_{2}<1$ is the mixing rate (second largest modulus eigenvalue) of $C$
.

Proof. See Appendix VII-A. $\hfill\blacksquare$

In Theorem 1, the first terms in both bounds are equivalent to the bounds
obtained in [41]. However, the terms proportional to
$(K-d_{\textup{min}})\tau$ are new, and they arise from the fact that agents
do not observe the joint actions and hence only have a local estimate of the
transition model. Nevertheless, the bounds get smaller with increasing network
connectivity, i.e., as $\lambda_{2}\to 0$ and $d_{\textup{min}}\to K$, which
shows the benefit of cooperation. In particular, if $\beta=K$ and the network
is fully connected ($\lambda_{2}=0,d_{\textup{min}}=K$), then the bounds are
equal to $0$. In other words, local beliefs match the centralized belief in
this situation.

We use Theorem 1 in the performance analysis of the diffusion policy
evaluation. To that regard, we first present the following consequence of
Theorem 1, which provides a bound in terms of disagreement norms.

######  Corollary 1 (Bounds on disagreement norms).

Theorem 1 implies that, as $i\to\infty$,

$\mathbb{E}\big{\|}\bm{\mu}_{i}-\bm{\mu}_{k,i}\big{\|}\leq B_{\textup{TV}}$
(51)

and

$\mathbb{E}\big{\|}\bm{\eta}_{i}-\bm{\eta}_{k,i}\big{\|}\leq\widetilde{B}_{\textup{TV}},$
(52)

where we introduce the constants

$B_{\textup{TV}}\triangleq
2\Bigg{(}1-\exp\Big{\\{}-\frac{2\sqrt{K}\beta\lambda
B+(K-d_{\textup{min}})\>\tau}{1-\kappa(\mathbb{T})}\Big{\\}}\Bigg{)}^{1/2}$
(53)

and

$\widetilde{B}_{\textup{TV}}\triangleq
2\Bigg{(}1-\exp\Big{\\{}-\frac{2\kappa(\mathbb{T})\sqrt{K}\beta\lambda
B+(K-d_{\textup{min}})\tau}{1-\kappa(\mathbb{T})}\Big{\\}}\Bigg{)}^{1/2}$ (54)

Proof. See Appendix VII-B. $\hfill\blacksquare$

###  V-B Network Disagreement

In this section, we study the variation of agent parameters from the network
centroid. To that end, let us incorporate the linear approximation
$\widehat{V}(\mu,w)=\phi(\mu)^{\operatorname{\mathsf{T}}}w$ into the TD-error
expression (39) to obtain the following relation:

$\displaystyle\bm{\delta}_{k,i}=\bm{r}_{k,i}+\gamma\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}\bm{w}_{k,i}-\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}\bm{w}_{k,i}.$
(55)

Since $\nabla_{w}\widehat{V}(\mu,w)=\phi(\mu)$ for the linear case, it follows
that

$\displaystyle\bm{z}_{k,i+1}=\Big{(}(1-2\rho\alpha)I-\alpha\bm{H}_{k,i}\Big{)}\bm{w}_{k,i}+\alpha\bm{d}_{k,i},$
(56)

where

$\bm{H}_{k,i}\triangleq\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\gamma\phi(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}},$
(57)

and

$\bm{d}_{k,i}\triangleq\bm{r}_{k,i}\phi(\bm{\mu}_{k,i}).$ (58)

To proceed, we introduce the following regularity assumption on the feature
vector.

######  Assumption 2 (Feature vector).

The feature mapping $\phi(\mu)$ is bounded and Lipschitz continuous in the
domain of the $S$-dimensional probability simplex. Namely, for any vectors
$\mu_{1},\mu_{2}\in\mathcal{M}(S)$,

$\|\phi(\mu_{1})-\phi(\mu_{2})\|\leq
L_{\phi}\|\mu_{1}-\mu_{2}\|,\quad\|\phi(\mu_{1})\|\leq B_{\phi}.$ (59)

$\hfill\blacksquare$

######  Lemma 1 (Belief feature difference).

For each agent $k\in\mathcal{K}$, the belief feature matrix $\bm{H}_{k,i}$ in
(57) has bounded expected difference in relation to the centralized belief
feature matrix $\bm{H}_{i}^{\star}$, defined below, i.e.,

$\mathbb{E}\|\bm{H}_{k,i}-\bm{H}_{i}^{\star}\|\leq
2B_{\phi}L_{\phi}B_{\textup{TV}}(1+\gamma),$ (60)

where

$\displaystyle\bm{H}_{i}^{\star}\triangleq\phi(\bm{\mu}_{i})\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}-\gamma\phi(\bm{\mu}_{i})\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}.$
(61)

Proof. See Appendix VII-C. $\hfill\blacksquare$

We also assume that all rewards are non-negative and uniformly bounded, i.e.,
$0\leq\bm{r}_{k,i}\leq R_{\textup{max}}$ for each agent $k\in\mathcal{K}$, and
all time instants $i$. Now, we proceed to study the network disagreement. To
that end, we define the network centroid as

$\bm{w}_{c,i}\triangleq\frac{1}{K}\sum_{k=1}^{K}\bm{w}_{k,i},$ (62)

which is an average of the parameters of all agents. The following result
shows that the agents cluster around this network centroid after sufficient
iterations.

######  Theorem 2 (Network agreement).

The average distance to the network centroid is bounded for $\rho>\gamma
B_{\phi}L_{\phi}/\sqrt{2}$ after sufficient number of iterations. In
particular, if $\rho\geq 0.75\gamma B_{\phi}L_{\phi}$, then

$\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\|\bm{w}_{k,i}-\bm{w}_{c,i}\|\leq\frac{\alpha\lambda_{2}\epsilon}{(1-\lambda_{2})}+O(\alpha^{2})$
(63)

where $\epsilon>0$ is a constant defined by

$\epsilon\triangleq
R_{\textup{max}}B_{\phi}\Big{(}\frac{2B_{\textup{TV}}(1+\gamma)}{0.08\gamma}+1\Big{)}.$
(64)

Proof. See Appendix VII-D. $\hfill\blacksquare$

Theorem 2 states that the parameter estimates by the agents cluster around the
network centroid within mean $\ell_{2}$-distance on the order of
$O(\alpha\lambda_{2})$ in the limit as $i\rightarrow\infty$. This result
confirms that agents can get arbitrarily close to each other by setting the
learning rate $\alpha$ sufficiently small. Besides, dense networks have in
general small $\lambda_{2}$, which results in a small disagreement within the
network.

###  V-C Performance of Diffusion Policy Evaluation

We can therefore use the network centroid as a proxy for all agents to show
that the disagreement between the fully decentralized strategy of Alg. 2 and a
baseline strategy that requires a central processor during training is
bounded. We start by describing this baseline strategy and explain why it is a
more suitable baseline compared to using the fully centralized strategy Alg.
1.

In some applications, even though agents are supposed to work in a
decentralized fashion once implemented in the field, they can nevertheless
rely on central processing during the training phase in order to learn the
best policy. In the literature, this paradigm is referred to as _centralized
training for decentralized execution_ [16, 61]. For our problem, the crucial
point is that during training the centralized processor can form beliefs based
on all observations, but it should keep in mind that agents will execute their
actions based on _local_ beliefs once implemented. Therefore, in the baseline
strategy, actions and rewards are based on local beliefs as in (36)–(38),
whereas parameter updates are based on the centralized posterior as in
(22)–(23). Algorithm 3 lists this baseline procedure. Notice that the
algorithm consists of both local belief construction (see (65), (66), and
(68)) and centralized belief construction (see (67) and (69)). The former is
used for action execution $\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{k,i})$,
while the latter is used for value function parameter updates in (70)–(71).

Algorithm 3 Centralized evaluation for decentralized execution

1:set initial priors $\eta_{k,0}(s)>0,\eta_{0}(s)>0$, for $\forall
s\in\mathcal{S}$ and $\forall k\in\mathcal{K}$

2:choose $\beta>0$

3:initialize $w_{0}^{\star}$

4:while $i\geq 0$ do

5: each agent $k$ observes $\bm{\xi}_{k,i}$

6: for each agent $k\in\mathcal{K}$ and $s\in\mathcal{S}$ adapt and combine
$\displaystyle\bm{\psi}_{k,i}(s)\propto(L_{k}(\bm{\xi}_{k,i}|s))^{\beta}\bm{\eta}_{k,i}(s)$
(65)
$\bm{\mu}_{k,i}(s)\propto\prod_{\ell\in\mathcal{N}_{k}}\big{(}\bm{\psi}_{\ell,i}(s)\big{)}^{a_{\ell
k}}$ (66)

7: end for

8: to form centralized belief with joint observation
$\bm{\xi}_{i}\triangleq\\{\bm{\xi}_{k,i}\\}_{k=1}^{K}$, adapt
$\bm{\mu}_{i}(s)\propto L(\bm{\xi}_{i}|s)\bm{\eta}_{i}(s)$ (67)

9: for each agent $k\in\mathcal{K}$ do

10: Take action $\bm{a}_{k,i}\sim\pi_{k}(a_{k}|\bm{\mu}_{k,i})$

11: Get reward $\bm{r}_{k,i}=\bm{r}_{k}(\bm{s}_{i},\bm{a}_{i},\bm{s}_{i+1})$

12: end for

13: average the rewards
$\bm{r}_{i}^{\star}=\frac{1}{K}\sum_{k=1}^{K}\bm{r}_{k,i}$

14: for each agent $k\in\mathcal{K}$ evolve

15: Compute $\mathbb{T}^{\pi}_{k}(s|s^{\prime},\bm{a}_{{\cal N}_{k},i})$ using
(28), and
$\bm{\eta}_{k,i+1}(s)=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}^{\pi}_{k}(s|s^{\prime},\bm{a}_{{\cal
N}_{k},i})\bm{\mu}_{k,i}(s^{\prime})$ (68)

16: end for

17: evolve the centralized belief
$\bm{\eta}_{i+1}(s)=\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}(s|s^{\prime},\bm{a}_{i})\bm{\mu}_{i}(s^{\prime})$
(69)

18: update value function parameter
$\bm{\delta}_{i}^{\star}=\bm{r}_{i}^{\star}+\gamma\widehat{V}(\bm{\eta}_{i+1},\bm{w}_{i}^{\star})-\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}^{\star})$
(70)
$\bm{w}_{i+1}^{\star}=(1-2\rho\alpha)\bm{w}_{i}^{\star}+\alpha\bm{\delta}_{i}^{\star}\nabla_{w}\widehat{V}(\bm{\mu}_{i},\bm{w}_{i}^{\star})$
(71)

19:end while

In the fully centralized strategy of Alg. 1, the actions by the agents and the
subsequent rewards are based on the centralized belief. Therefore, the target
value function that Alg. 1 aims to learn corresponds to the average cumulative
reward obtained under centralized execution. In comparison, the target value
functions that Algs. 2 and 3 try to learn are the same and they correspond to
the average cumulative reward under decentralized execution. While trying to
learn the same parameter $w^{\circ}$, the baseline strategy can utilize
centralized processing, but the diffusion strategy is fully decentralized.
Nonetheless, the following result illustrates that the expected disagreement
between the baseline strategy and the fully decentralized strategy remains
bounded.

######  Theorem 3 (Disagreement with the baseline solution).

The expected distance between the baseline strategy and the network centroid
is bounded after sufficient iterations for $\rho>\gamma
B_{\phi}L_{\phi}/\sqrt{2}$. In particular, if $\rho\geq 0.75\gamma
B_{\phi}L_{\phi}$, then

$\displaystyle\mathbb{E}\|\bm{w}_{i}^{\star}-\bm{w}_{c,i}\|\leq\frac{B_{\textup{TV}}R_{\textup{max}}\epsilon^{\prime}}{0.08\gamma
B_{\phi}L_{\phi}},$ (72)

where $\epsilon^{\prime}>0$ is a constant defined by

$\epsilon^{\prime}\triangleq\frac{2B_{\phi}(1+\gamma)}{0.08\gamma}+L_{\phi}.$
(73)

Proof. See Appendix VII-E. $\hfill\blacksquare$

Theorem 3 implies that the disagreement between the network centroid, around
which agents cluster, and the baseline strategy is on the order of
$B_{\textup{TV}}$. This means that if the local beliefs are similar to the
centralized belief, agents get closer to the baseline parameter. In this
regard, from the definition (53) of $B_{\textup{TV}}$, it can be observed that
$B_{\textup{TV}}$ gets smaller with increasing network connectivity (i.e.,
decreasing $\lambda_{2}$), as $\beta\to K$. In fact, it is equal to zero for
fully-connected networks with the choice of $\beta=K$ and $c_{\ell k}=1/K$.
Therefore, by changing $\beta$ and $c_{\ell k}$, the fully decentralized
strategy can match the value function estimates of a centralized training
strategy that can gather all observations and actions in a fusion center. In
the next section, by means of numerical simulations, we further compare the
value function estimate accuracies of all Algorithms 1, 2 and 3 by using
squared Bellman error (SBE).

##  VI Simulation Results

For numerical simulations, we consider a multi-agent target localization
application. The implementation is available online111github.com/asl-
epfl/DecPOMDP_Policy_Evaluation_w-Belief_Sharing. We use a set of $K=8$ agents
and a moving target in a $10\times 10$ two-dimensional grid world environment.
The locations of the agents are fixed and their coordinates are randomly
assigned at the beginning of the simulation. The goal of the agents is to
cooperatively evaluate a given policy for hitting the target. Agents cannot
observe the location (i.e., state) of the target accurately, but instead
receive noisy observations based on how far they are from the real location of
the target. The target is moving according to some pre-defined transition
model that takes the actions (i.e., hits) of agents into account.
Specifically, the target is trying to evade the hits of agents.

A possible scenario for this setting is a network of sensors and an intruder
(e.g., a spy drone) — see Fig. 2. The sensors try to localize the intruder
based on noisy measurements and belief exchanges. Moreover, in order to
disrupt the communication between the intruder and its owner, each sensor
sends a narrow sector jamming beam towards its target location estimate.
However, the intruder is capable of detecting energy abnormalities and
determines its next location by favoring distant locations from the jamming
signals. We now describe the setting in more detail.

(a) Initial positions at the beginning of an iteration.

(b) Agents receive noisy observations and incorporate them into their beliefs.

(c) Agents exchange beliefs with their immediate neighbors.

(d) Agents take actions based on the beliefs. The target relocates based on
the actions.

(e) Agents update and exchange value function parameters.

(f) The legend. Image credit for agent, target, and action: freepik.com

Figure 2: Experimental scenario. For visual purposes, the procedure is shown
for only one agent. In fact, all agents execute the same procedure
simultaneously.

Combination matrix: The entries of the combination matrix are set such that
they are inversely proportional to the $\ell_{1}$-distance between the agents.
That is to say, the further the agents are from each other, the smaller the
value of the weight that is assigned to the edge connecting them. Weights
smaller than some threshold are set to 0, which implies that agents that are
too far from each other do not need to communicate. The resulting
communication topology graph is illustrated in Fig. 3(a).

(a) Communication topology.

(b) Agreement error over time.

(c) SBE over time (running window of size 20) for CC (Alg. 1), Diffusion (Alg.
2), CD (Alg. 3).

Figure 3:

Transition model: The target is moving between cells in a grid (i.e., states)
randomly. The probability of a cell being the next location of the target
depends on the current location of the target and the location of the agents’
hits. Namely, each state in the grid is assigned a score based on its
$\ell_{1}$-distance to the current location of the target and to the average
location of the agents’ hits — see Table I. For example, observe from Table I
that the cells that are in the proximity of the target’s current location and
also far away from the agents’ strikes are given the highest score. These
scores are normalized to yield a probabilistic transition kernel.

| initial position
---|---
|  $\bm{\ell}_{\textbf{1}}$-distance |  $\leq 4$ |  $>4$
average location of agents’ hits |  $<4$ |  10 |  5
|  $\geq 4$ |  100 |  50
TABLE I: The table of scores used in the transition model. Each candidate
state for next state (location) of the target gets a score based on the
initial position of the target and the average action of agents.

Likelihood function: Agents cannot observe where the target is. They can only
receive noisy observations. Each agent gets a more accurate observation of the
target’s position if the target is in close proximity to the agent. Otherwise,
the larger the distance between the agent and the target, the higher the noise
level. Depending on how close the target is to the agent, and in order to
construct the likelihood function, we first assign scores to each cell in the
grid that reflect how probable it is to find the target in that cell — see
Table II. Following that, the scores are normalized in order to yield a
distribution function. For instance, if the target lies at an
$\ell_{1}$-distance that is less than 3 grid squares from the location of the
agent, the actual position of the target gets a likelihood score of 400, cells
within an $\ell_{1}$ distance of 2 grid squares from the agent get a
likelihood score of 200, and cells within an $\ell_{1}$ distance of 4 grid
squares from the agents get a score of 30.

| real location of target
---|---
|  $\bm{\ell}_{\textbf{1}}$-distance |  $=0$ |  $<3$ |  $<5$ |  $<7$ |  $<9$ |  $\geq 9$
location of agent |  $<3$ |  400 |  200 |  30 |  1 |  1 |  1
|  $\leq 6$ |  200 |  180 |  100 |  1 |  1 |  1
|  $>6$ |  25 |  25 |  25 |  25 |  4 |  1
TABLE II: The table of scores used in the likelihood function model. Each
state, when observed, gets a score that determines the likelihood of the
presence of the target within the state, based on the position of the target
and the average action of agents.

Reward function: The reward function in the environment is such that an agent
receives a reward of 1 if the agent is able to hit the position of the target.
The agent also receives a reward of 0.2 if the $\ell_{1}$-distance between the
predicted location and the actual location of the target is less than 3 grid
units. Otherwise, it gets 0 reward. Agents do not know the reward model, and
use the instantaneous rewards instead.

Policy: We fix the policy that the agents evaluate as the maximum a-posteriori
policy. Namely, agents detect (hit) a location if it corresponds to the
maximum entry in their belief vector.

We use the belief vectors as the features directly, i.e., $\phi$ is an
identity transformation. We set $\alpha=0.1$, $\rho=0.0001$, and $\beta=K=8$,
and average over 3 different realizations for all cases. In Fig. 3(b), the
average mean-square distance to the network centroid, i.e.,

$\text{Agreement
error}\triangleq\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\|\bm{w}_{k,i}-\bm{w}_{c,i}\|^{2},$
(74)

is plotted over time for the fully decentralized strategy. Confirming Theorem
2, it can be seen that agreement error rapidly decreases and converges to a
small value.

In Fig. 3(c), we plot the evolution of the average squared Bellman error (SBE)
in the log domain, where the SBE expression is given by:

$\text{SBE}\triangleq\frac{1}{K}\sum_{k=1}^{K}\bm{\delta}_{k,i}^{2},$ (75)

and similarly for the centralized cases. It measures the network average of
instantaneous TD-errors. It can be seen that all approaches converge, and in
particular, diffusion strategy (Alg. 2) yields a comparable performance with
CD (Alg. 3). This observation is in line with Theorem 3, which states that the
disagreement between the fully decentralized strategy and the baseline
centralized training for decentralized execution strategy is bounded. Notice
also that CC (Alg. 1) results in a higher SBE compared to the diffusion and
CD, despite being a fully centralized strategy. This is because, CC evaluates
a different policy, namely, the centralized execution policy. Therefore, as
argued in Sec.V-C, the SBE of CC is not a suitable baseline for the diffusion
strategy.

##  VII Concluding Remarks

In this paper, we proposed a policy evaluation algorithm for Dec-POMDPs over
networks. We carried out a rigorous analysis that established: $(i)$ the
beliefs formed with local information and interactions have a bounded
disagreement with the global posterior distribution, $(ii)$ agents’ value
function parameters cluster around the network centroid, and $(iii)$ the
decentralized training can match the performance of the centralized training
with appropriate parameters and increasing network connectivity.

There are two limitations of the current work that can be addressed in future
work. First, we assume that agents know the local likelihood and transition
models accurately. One possible question is if agents have approximation
errors for the models, how would these affect the analytical results. Second,
an implication of Theorem 3 is that there is necessity for regularization
$(\rho>0)$. We leave the question of whether one can get bounds that does not
require this, possibly with more assumptions on the model, to future work.

## Appendix

###  VII-A Proof of Theorem 1

We can rewrite the risk function as

$\displaystyle J_{k,i}$
$\displaystyle=\mathbb{E}_{\mathcal{F}_{i}}D_{\textup{KL}}(\bm{\mu}_{i}||\bm{\mu}_{k,i})$
$\displaystyle=\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\sum_{s\in\mathcal{S}}\bm{\mu}_{i}(s)\log\frac{\bm{\mu}_{i}(s)}{\bm{\mu}_{k,i}(s)}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\sum_{s\in\mathcal{S}}\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i})\log\frac{\bm{\mu}_{i}(s)}{\bm{\mu}_{k,i}(s)}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\mathbb{E}_{s_{i}|\mathcal{F}_{i}}\Big{(}\log\frac{\bm{\mu}_{i}(\bm{s}_{i})}{\bm{\mu}_{k,i}(\bm{s}_{i})}\Big{)}\Big{]}$
$\displaystyle=\mathbb{E}_{\mathcal{F}_{i},s_{i}}\Big{[}\log\frac{\bm{\mu}_{i}(\bm{s}_{i})}{\bm{\mu}_{k,i}(\bm{s}_{i})}\Big{]},$
(76)

where $(a)$ follows from definition (9), $(b)$ follows from the definition of
conditional expectation with respect to $\bm{s}_{i}$ given
$\boldsymbol{\mathcal{F}}_{i}$. Merging the diffusion adaptation step (36) and
the combination step (37) together yields the following form:

$\bm{\mu}_{k,i}(s)\propto\prod_{\ell\in\mathcal{N}_{k}}(L_{\ell}(\bm{\xi}_{\ell,i}|s))^{\beta
c_{\ell k}}(\bm{\eta}_{\ell,i}(s))^{c_{\ell k}},$ (77)

which, combined with the update equation (22) for the centralized solution,
results in:

$\displaystyle\log$
$\displaystyle\frac{\bm{\mu}_{i}(s)}{\bm{\mu}_{k,i}(s)}=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\Big{(}\log\frac{L(\bm{\xi}_{i}|s)}{(L_{\ell}(\bm{\xi}_{\ell,i}|s))^{\beta}}+\log\frac{\bm{\eta}_{i}(s)}{\bm{\eta}_{\ell,i}(s)}\Big{)}$
$\displaystyle+\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\\!\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell
k}}\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(\bm{\eta}_{\ell,i}(s^{\prime}))^{c_{\ell
k}}\Big{)}$ $\displaystyle\qquad-\log\bm{m}_{i}(\bm{\xi}_{i}).$ (78)

Here, we have introduced the marginal distribution of new observation given
the past observations and actions:

$\displaystyle\bm{m}_{i}(\xi_{i})\triangleq\mathbb{P}(\bm{\xi}_{i}=\xi_{i}|\boldsymbol{\mathcal{F}}_{i-1}^{a})$
$\displaystyle=\sum_{s\in\mathcal{S}}\mathbb{P}(\bm{\xi}_{i}=\xi_{i},\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i-1}^{a})$
$\displaystyle=\sum_{s\in\mathcal{S}}L(\xi_{i}|s)\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i-1}^{a})$
$\displaystyle=\sum_{s\in\mathcal{S}}L(\xi_{i}|s)\bm{\eta}_{i}(s).$ (79)

First, observe that the expectation of the log-likelihood ratio terms in
(VII-A) satisfies:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}c_{\ell k}$
$\displaystyle\mathbb{E}_{\xi_{i},s_{i}}\Big{[}\log\frac{L(\bm{\xi}_{i}|\bm{s}_{i})}{(L_{\ell}(\bm{\xi}_{\ell,i}|\bm{s}_{i}))^{\beta}}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{\xi_{i},s_{i}}\Big{[}\sum_{\ell=1}^{K}\log
L_{\ell}(\bm{\xi}_{\ell,i}|\bm{s}_{i})\Big{]}$
$\displaystyle\qquad-\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\xi_{\ell,i},s_{i}}\Big{[}\beta\log
L_{\ell}(\bm{\xi}_{\ell,i}|\bm{s}_{i})\Big{]}$
$\displaystyle=\mathbb{E}_{\xi_{i},s_{i}}\Big{[}\sum_{\ell=1}^{K}(1-\beta
c_{\ell k})\log L_{\ell}(\bm{\xi}_{\ell,i}|\bm{s}_{i})\Big{]}$ (80)

where in $(a)$ we used the spatial independency of the observations. Second,
the expectation of the time-adjusted terms in (VII-A) can be rewritten as:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i},s_{i}}\Big{[}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i},s_{i}}\Big{[}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}+\log\frac{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{]}$
$\displaystyle=\\!\\!\sum_{\ell\in\mathcal{N}_{k}}\\!\\!c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}\mathbb{E}_{\xi_{i}|\mathcal{F}_{i-1}^{a},s_{i}}\Big{(}\\!\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}+\log\frac{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{)}\\!\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}+\log\frac{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{]}$
(81)

where in $(a)$ we define the agent-specific distribution:

$\widetilde{\bm{\eta}}_{\ell,i}(s)\triangleq\sum_{s^{\prime}\in\mathcal{S}}\mathbb{T}(s|s^{\prime},\bm{a}_{i-1})\bm{\mu}_{\ell,i-1}(s^{\prime}),$
(82)

and $(b)$ follows from the fact that the arguments are deterministic given the
current state and the history of actions and observations. The first term of
(VII-A) can be written as a KL-divergence because of the following:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}\Big{]}$
$\displaystyle\qquad=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\Big{[}\mathbb{E}_{s_{i}|\mathcal{F}_{i-1}^{a}}\Big{(}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}\Big{)}\Big{]}$
$\displaystyle\qquad=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\Big{[}\sum_{s\in\mathcal{S}}\mathbb{P}(\bm{s}_{i}=s|\boldsymbol{\mathcal{F}}_{i-1}^{a})\log\frac{\bm{\eta}_{i}(s)}{\widetilde{\bm{\eta}}_{\ell,i}(s)}\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle\eqref{eq:ck_cent}}}{{=}}\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\Big{[}\sum_{s\in\mathcal{S}}\bm{\eta}_{i}(s)\log\frac{\bm{\eta}_{i}(s)}{\widetilde{\bm{\eta}}_{\ell,i}(s)}\Big{]}$
$\displaystyle\qquad=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\Big{[}D_{\textup{KL}}(\bm{\eta}_{i}||\widetilde{\bm{\eta}}_{\ell,i})\Big{]}.$
(83)

This expected KL-divergence can be bounded by using the strong-data processing
inequality [62]:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}$ $\displaystyle c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\Big{[}D_{\textup{KL}}(\bm{\eta}_{i}||\widetilde{\bm{\eta}}_{\ell,i})\Big{]}$
$\displaystyle\leq\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\kappa(\mathbb{T})\underbrace{\mathbb{E}_{\mathcal{F}_{i-1}}\Big{[}D_{\textup{KL}}(\bm{\mu}_{i-1}||\bm{\mu}_{\ell,i-1})\Big{]}}_{J_{\ell,i-1}}.$
(84)

The second term of (VII-A) arises due to transition model disagreement with
the centralized belief. To bound it, we first introduce the LogSumExp function
$f$ with vector arguments $\nu\in\mathbb{R}^{S}$:

$\displaystyle f(\nu)\triangleq\log\sum_{s\in\mathcal{S}}\exp\\{\nu(s)\\}.$
(85)

Its gradient is given by

$\nabla_{\nu}f(\nu)\triangleq\text{col}\Big{\\{}\frac{\partial
f(\nu)}{\partial\nu(s)}\Big{\\}}_{s\in\mathcal{S}}=\text{col}\Big{\\{}\frac{\exp\\{\nu(s)\\}}{\sum_{s^{\prime}}\exp\\{\nu(s^{\prime})\\}}\Big{\\}}_{s\in\mathcal{S}}.$
(86)

Observe that if we define the vectors

$\widetilde{\bm{\nu}}_{\ell,i}\triangleq\text{col}\Big{\\{}\log\big{(}\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})\bm{\mu}_{\ell,i-1}(s)\big{)}\Big{\\}}_{s\in\mathcal{S}}$
(87)

and

$\bm{\nu}_{\ell,i}\triangleq\text{col}\Big{\\{}\log\big{(}\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})\bm{\mu}_{\ell,i-1}(s)\big{)}\Big{\\}}_{s\in\mathcal{S}},$ (88)

then, we can rewrite the second expression of (VII-A) as follows:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}\log\frac{\widetilde{\bm{\eta}}_{\ell,i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{]}$
$\displaystyle\qquad=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}f(\widetilde{\bm{\nu}}_{\ell,i})-f(\bm{\nu}_{\ell,i})\Big{]}.$
(89)

Applying mean value theorem to this difference yields

$\displaystyle\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}f(\widetilde{\bm{\nu}}_{\ell,i})-f(\bm{\nu}_{\ell,i})\Big{]}$
$\displaystyle=\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\bigg{[}(\nabla_{\nu}f(\overline{\bm{\nu}}_{\ell,i}))^{\operatorname{\mathsf{T}}}\cdot(\widetilde{\bm{\nu}}_{\ell,i}-\bm{\nu}_{\ell,i})\bigg{]}$
$\displaystyle\quad\stackrel{{\scriptstyle\eqref{eq:logsumexp_grad_def_1}}}{{=}}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\bigg{[}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}^{\operatorname{\mathsf{T}}}_{s\in\mathcal{S}}\cdot(\widetilde{\bm{\nu}}_{\ell,i}-\bm{\nu}_{\ell,i})\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:tilde_nu_def},\eqref{eq:nu_def}}}{{=}}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\bigg{[}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}^{\operatorname{\mathsf{T}}}_{s\in\mathcal{S}}$
$\displaystyle\qquad\qquad\qquad\cdot\text{col}\Big{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})}\Big{\\}}_{s\in\mathcal{S}}\bigg{]}$ (90)

for some $\overline{\bm{\nu}}_{\ell,i}$ between
$\widetilde{\bm{\nu}}_{\ell,i}$ and $\bm{\nu}_{\ell,i}$. The term in (90) is
bounded as follows:

$\displaystyle\Bigg{|}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\bigg{[}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}^{\operatorname{\mathsf{T}}}_{s\in\mathcal{S}}$
$\displaystyle\qquad\qquad\qquad\cdot\text{col}\Big{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})}\Big{\\}}_{s\in\mathcal{S}}\bigg{]}\Bigg{|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Bigg{|}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}^{\operatorname{\mathsf{T}}}_{s\in\mathcal{S}}$
$\displaystyle\qquad\qquad\qquad\cdot\text{col}\Big{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})}\Big{\\}}_{s\in\mathcal{S}}\Bigg{|}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Bigg{[}\Big{\|}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}_{s\in\mathcal{S}}\Big{\|}_{1}$
$\displaystyle\qquad\qquad\qquad\cdot\Big{\|}\text{col}\Big{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})}\Big{\\}}_{s\in\mathcal{S}}\Big{\|}_{\infty}\Bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\mathbb{E}_{s_{i},a_{i-1}}\Bigg{\|}\text{col}\Big{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{\ell}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{\ell},i-1})}\Big{\\}}_{s\in\mathcal{S}}\Bigg{\|}_{\infty}$ (91)

where $(a)$ follows from the Jensen’s inequality, $(b)$ follows from the
Hölder’s inequality, and $(c)$ follows from the fact that

$\displaystyle\Bigg{\|}\text{col}\Big{\\{}\frac{\exp\\{\overline{\bm{\nu}}_{\ell,i}(s)\\}}{\sum_{s^{\prime}\in\mathcal{S}}\exp\\{\overline{\bm{\nu}}_{\ell,i}(s^{\prime})\\}}\Big{\\}}\Bigg{\|}_{1}=1.$
(92)

Observe that we can rewrite, for any $a_{{\cal N}_{k}}\in\mathcal{A}_{{\cal
N}_{k}}$:

$\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})=\\!\\!\\!\\!\\!\\!\\!\\!\sum_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\\!\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})\frac{\pi(a_{{\cal
N}_{k}},a_{{\cal N}_{k}}^{c}|s^{\prime})}{\sum_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal N}_{k}}^{c}}\\!\\!\\!\pi(a_{{\cal
N}_{k}},\widetilde{a}_{{\cal N}_{k}}^{c}|s^{\prime})}$ (93)

because it is obvious that

$\sum_{a_{{\cal N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\frac{\pi(a_{{\cal N}_{k}},a_{{\cal
N}_{k}}^{c}|s^{\prime})}{\sum_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal N}_{k}}^{c}}\\!\\!\\!\pi(a_{{\cal
N}_{k}},\widetilde{a}_{{\cal N}_{k}}^{c}|s^{\prime})}=1.$ (94)

Accordingly, the transition probability ratio in (91) becomes:

$\displaystyle\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{k}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1})}$ $\displaystyle=\\!\\!\frac{\sum\limits_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1},\bm{a}_{{\cal N}_{k},i-1}^{c})\cfrac{\pi(\bm{a}_{{\cal
N}_{k},i-1},a_{{\cal N}_{k}}^{c}|s)}{\sum\limits_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\pi(\bm{a}_{{\cal
N}_{k},i-1},\widetilde{a}_{{\cal N}_{k}}^{c}|s)}}{\sum\limits_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1},a_{{\cal N}_{k}}^{c})\cfrac{\pi(\bm{a}_{{\cal N}_{k},i-1},a_{{\cal
N}_{k}}^{c}|s)}{\sum\limits_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\pi(\bm{a}_{{\cal
N}_{k},i-1},\widetilde{a}_{{\cal N}_{k}}^{c}|s)}}$ (95)

where we have decomposed $\bm{a}_{i-1}=\bm{a}_{{\cal
N}_{k},i-1}\cup\bm{a}_{{\cal N}_{k},i-1}^{c}$. The logarithm of this ratio can
be expressed as:

$\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{k}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1})}=f(\widetilde{\bm{\upsilon}}_{k,i})-f(\bm{\upsilon}_{k,i}),$ (96)

with the definitions:

$\displaystyle\widetilde{\bm{\upsilon}}_{k,i}\triangleq\text{col}\Bigg{\\{}\log\Bigg{(}\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1},\bm{a}_{{\cal N}_{k},i-1}^{c})$
$\displaystyle\qquad\qquad\times\cfrac{\pi(\bm{a}_{{\cal N}_{k},i-1},a_{{\cal
N}_{k}}^{c}|s)}{\sum\limits_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\pi(\bm{a}_{{\cal
N}_{k},i-1},\widetilde{a}_{{\cal N}_{k}}^{c}|s)}\Bigg{)}\Bigg{\\}}_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal N}_{k}}^{c}},$ (97)
$\displaystyle\bm{\upsilon}_{k,i}\triangleq\text{col}\Bigg{\\{}\log\Bigg{(}\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1},a_{{\cal N}_{k}}^{c})$
$\displaystyle\qquad\qquad\times\cfrac{\pi(\bm{a}_{{\cal N}_{k},i-1},a_{{\cal
N}_{k}}^{c}|s)}{\sum\limits_{\widetilde{a}_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\\!\pi(\bm{a}_{{\cal
N}_{k},i-1},\widetilde{a}_{{\cal N}_{k}}^{c}|s)}\Bigg{)}\Bigg{\\}}_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal N}_{k}}^{c}},$ (98)

and in terms of the LogSumExp function $f$:

$f(\upsilon)\triangleq\log\\!\\!\\!\\!\\!\sum_{a_{{\cal
N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\\!\\!\\!\\!\\!\exp\\{\upsilon(a_{{\cal N}_{k}}^{c})\\}.$ (99)

for any vector $\upsilon\in\mathbb{R}^{|\mathcal{A}_{{\cal N}_{k}}^{c}|}$.
Following the same steps in (90) and (91), if we apply mean value theorem and
Hölder’s inequality to (96), we get:

$\displaystyle\Bigg{|}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{i-1})}{\mathbb{T}^{\pi}_{k}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1})}\Bigg{|}$
$\displaystyle\leq\Bigg{\|}\text{col}\Bigg{\\{}\log\frac{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal
N}_{k},i-1},\bm{a}_{{\cal
N}_{k},i-1}^{c})}{\mathbb{T}(\bm{s}_{i}|s,\bm{a}_{{\cal N}_{k},i-1},a_{{\cal
N}_{k}}^{c})}\Bigg{\\}}_{a_{{\cal N}_{k}}^{c}\in\mathcal{A}_{{\cal
N}_{k}}^{c}}\Bigg{\|}_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}(K-|\mathcal{N}_{k}|)\>\tau$
$\displaystyle\leq(K-d_{\textup{min}})\>\tau$ (100)

where $(a)$ follows from Assumption 1 and the fact that
$|\mathcal{N}_{k}^{c}|=K-|\mathcal{N}_{k}|$. If we combine (84), (89), and
(100), the expectation of the time-adjusted terms in (VII-A) can be bounded
as:

$\displaystyle\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\mathbb{E}_{\mathcal{F}_{i-1}^{a},s_{i}}\Big{[}\log\frac{\bm{\eta}_{i}(\bm{s}_{i})}{\bm{\eta}_{\ell,i}(\bm{s}_{i})}\Big{]}$
$\displaystyle\qquad\quad\leq(K-d_{\textup{min}})\>\tau+\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\kappa(\mathbb{T})J_{\ell,i-1}$ (101)

Next, we bound the expectation of the remaining normalization terms in
(VII-A), which follows similar steps to what was done in [41]:

$\displaystyle\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\\!\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell
k}}\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(\bm{\eta}_{\ell,i}(s^{\prime}))^{c_{\ell
k}}\Big{)}\Bigg{]}$
$\displaystyle\quad-\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\log\bm{m}_{i}(\bm{\xi}_{i})\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\\!\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell k}}\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad-\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\log\bm{m}_{i}(\bm{\xi}_{i})\Big{]}$
$\displaystyle\qquad=\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\\!\\!\prod_{\ell\in\mathcal{N}_{k}}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell k}}\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad-\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad+\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad-\mathbb{E}_{\mathcal{F}_{i}}\Big{[}\log\bm{m}_{i}(\bm{\xi}_{i})\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle(b)}}{{\leq}}\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell k}}\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad-\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$ (102)

where $(a)$ follows from the arithmetic-geometric mean inequality, $(b)$
follows from:

$\displaystyle-\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\frac{\bm{m}_{i}(\bm{\xi}_{i})}{\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}}\Bigg{]}$
$\displaystyle\qquad\qquad=-\mathbb{E}_{\mathcal{F}_{i-1}^{a}}\mathbb{E}_{\xi_{i}|\mathcal{F}_{i-1}^{a}}\Bigg{[}\log\frac{\bm{m}_{i}(\bm{\xi}_{i})}{\bm{m}_{i}^{\dagger}(\bm{\xi}_{i})}\Bigg{]}$
$\displaystyle\qquad\qquad=-\mathbb{E}_{\mathcal{F}_{i-1}^{a}}D_{\textup{KL}}(\bm{m}_{i}(\bm{\xi}_{i})||\bm{m}_{i}^{\dagger}(\bm{\xi}_{i}))$
$\displaystyle\qquad\qquad\leq 0$ (103)

where we use the definition:

$\displaystyle\bm{m}_{i}^{\dagger}(\bm{\xi}_{i})\triangleq\sum_{s^{\prime}\in\mathcal{S}}\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)},$ (104)

which is a density (or mass function if observations are discrete) since:

$\displaystyle\int_{\xi_{i}}\bm{m}_{i}^{\dagger}(\xi_{i})d\xi_{i}$
$\displaystyle=\int_{\xi_{i}}\sum_{s^{\prime}\in\mathcal{S}}\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}d\xi_{i}$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}}\Big{[}\underbrace{\int_{\xi_{i}}\prod_{\ell=1}^{K}L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})d\xi_{i}}_{1}\sum_{\ell=1}^{K}c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{]}$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}}\Big{[}\sum_{\ell=1}^{K}c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{]}$
$\displaystyle=\sum_{\ell=1}^{K}c_{\ell
k}\Big{[}\sum_{s^{\prime}\in\mathcal{S}}\bm{\eta}_{\ell,i}(s^{\prime})\Big{]}=1.$
(105)

Notice that the expression in (102) can be rewritten as

$\displaystyle\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell k}}\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle\qquad-\mathbb{E}_{\mathcal{F}_{i}}\Bigg{[}\log\sum_{s^{\prime}\in\mathcal{S}}\\!\\!\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\mathcal{F}_{i}}\Big{[}f(\bm{\vartheta}_{k,i})\Big{]}-\mathbb{E}_{\mathcal{F}_{i}}\Big{[}f(\widetilde{\bm{\vartheta}}_{k,i})\Big{]},$
(106)

if we use the LogSumExp function $f$ from (85) and use the definitions:

$\bm{\vartheta}_{k,i}\triangleq\text{col}\Bigg{\\{}\log\Big{(}\prod_{\ell=1}^{K}\\!(L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime}))^{\beta
c_{\ell k}}\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{\\}}_{s^{\prime}\in\mathcal{S}}$
(107)

and

$\widetilde{\bm{\vartheta}}_{k,i}\triangleq\text{col}\Bigg{\\{}\log\Big{(}\prod_{\ell=1}^{K}\\!L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\\!\sum_{\ell\in\mathcal{N}_{k}}\\!c_{\ell
k}\bm{\eta}_{\ell,i}(s^{\prime})\Big{)}\Bigg{\\}}_{s^{\prime}\in\mathcal{S}}.$
(108)

Following the steps in (90) and (91), this difference can be bounded as:

$\displaystyle\mathbb{E}_{\mathcal{F}_{i}}\Big{[}f(\bm{\vartheta}_{k,i})\Big{]}-\mathbb{E}_{\mathcal{F}_{i}}\Big{[}f(\widetilde{\bm{\vartheta}}_{k,i})\Big{]}$
$\displaystyle\leq\mathbb{E}_{\xi_{i}}\Bigg{\|}\text{col}\Big{\\{}\sum_{\ell=1}^{K}(\beta
c_{\ell k}-1)\log
L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\Big{\\}}_{s^{\prime}\in\mathcal{S}}\Bigg{\|}_{\infty}.$
(109)

Moreover, by assumptions on the graph topology (27) and on the likelihood
functions (45), this expression can be further bounded as [41]:

$\displaystyle\Bigg{\|}\text{col}\Big{\\{}\sum_{\ell=1}^{K}(\beta c_{\ell
k}-1)\log
L_{\ell}(\bm{\xi}_{\ell,i}|s^{\prime})\Big{\\}}_{s^{\prime}\in\mathcal{S}}\Bigg{\|}_{\infty}\leq\sqrt{K}\beta\lambda
B$ (110)

Subsequently, if we insert the bounds (80), (VII-A), and (110) to (VII-A), we
arrive at the bound on the risk function:

$\displaystyle J_{k,i}$
$\displaystyle\leq\mathbb{E}_{\xi_{i},s_{i}}\Big{[}\sum_{\ell=1}^{K}(1-\beta
c_{\ell k})\log L_{\ell}(\bm{\xi}_{\ell,i}|\bm{s}_{i})\Big{]}$
$\displaystyle\quad+\kappa(\mathbb{T})\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}{J_{\ell,i-1}}+\sqrt{K}\beta\lambda B+(K-d_{\textup{min}})\>\tau$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:normalization_term_bound_small}}}{{\leq}}\kappa(\mathbb{T})\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}{J_{\ell,i-1}}+2\sqrt{K}\beta\lambda B+(K-d_{\textup{min}})\>\tau.$ (111)

Expanding this recursion over time yields:

$\displaystyle J_{k,i}$ $\displaystyle\leq(2\sqrt{K}\beta\lambda
B+(K-d_{\textup{min}})\>\tau)\sum_{j=0}^{i-1}(\kappa(\mathbb{T}))^{j}$
$\displaystyle\qquad+(\kappa(\mathbb{T}))^{i}\sum_{\ell=1}^{K}[C^{i}]_{\ell
k}J_{\ell,0}$
$\displaystyle=\frac{1-(\kappa(\mathbb{T}))^{i}}{1-\kappa(\mathbb{T})}(2\sqrt{K}\beta\lambda
B+(K-d_{\textup{min}})\>\tau)$
$\displaystyle\qquad+(\kappa(\mathbb{T}))^{i}\sum_{\ell=1}^{K}[C^{i}]_{\ell
k}J_{\ell,0},$ (112)

which implies that if $\kappa(\mathbb{T})<1$, the risk function is bounded as
$i\to\infty$:

$\displaystyle\limsup_{i\rightarrow\infty}J_{k,i}\leq\frac{2\sqrt{K}\beta\lambda
B+(K-d_{\textup{min}})\>\tau}{1-\kappa(\mathbb{T})}.$ (113)

By (VII-A), this also implies that

$\displaystyle\limsup_{i\rightarrow\infty}\widetilde{J}_{k,i}$
$\displaystyle\leq(K-d_{\textup{min}})\tau+\kappa(\mathbb{T})\limsup_{i\rightarrow\infty}J_{k,i}$
$\displaystyle\leq\frac{(K-d_{\textup{min}})\tau}{1-\kappa(\mathbb{T})}+\kappa(\mathbb{T})\frac{2\sqrt{K}\beta\lambda
B}{1-\kappa(\mathbb{T})}.$ (114)

###  VII-B Proof of Corollary 1

In view of the Bretagnolle-Huber inequality [63], it holds that

$\sum_{s\in\mathcal{S}}\big{|}\bm{\mu}_{i}(s)-\bm{\mu}_{k,i}(s)\big{|}\leq
2\big{(}1-\exp\\{-D_{\textup{KL}}(\bm{\mu}_{i}||\bm{\mu}_{k,i})\\}\big{)}^{\frac{1}{2}}.$
(115)

If we take the expectation of both sides, we get:

$\displaystyle\mathbb{E}\Big{[}\\!\\!\sum_{s\in\mathcal{S}}\\!\big{|}\bm{\mu}_{i}(s)-\bm{\mu}_{k,i}(s)\big{|}\Big{]}\\!\\!$
$\displaystyle\leq
2\mathbb{E}\big{(}1-\exp\\{-D_{\textup{KL}}(\bm{\mu}_{i}||\bm{\mu}_{k,i})\\}\big{)}^{\frac{1}{2}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2\big{(}1-\mathbb{E}\exp\\{-D_{\textup{KL}}(\bm{\mu}_{i}||\bm{\mu}_{k,i})\\}\big{)}^{\frac{1}{2}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2\big{(}1-\exp\\{-J_{k,i}\\}\big{)}^{\frac{1}{2}},$
(116)

where $(a)$ and $(b)$ follow from Jensen’s inequality. Together with Theorem
1, this implies that

$\mathbb{E}\big{\|}\bm{\mu}_{i}-\bm{\mu}_{k,i}\big{\|}_{1}\leq
B_{\textup{TV}},$ (117)

where we use the definition (53). Furthermore, on account of the fact that
$\ell_{2}$ norm is no greater than $\ell_{1}$ norm in $\mathbb{R}^{S}$, it is
also true that

$\mathbb{E}\big{\|}\bm{\mu}_{i}-\bm{\mu}_{k,i}\big{\|}\leq B_{\textup{TV}}.$
(118)

With similar arguments, it can be shown that

$\mathbb{E}\big{\|}\bm{\eta}_{i}-\bm{\eta}_{k,i}\big{\|}\leq\widetilde{B}_{\textup{TV}},$
(119)

where we use the definition (54).

###  VII-C Proof of Lemma 1

Inserting the definitions (57) and (61), the expected difference can be
expanded as

$\displaystyle\mathbb{E}\|\bm{H}_{k,i}-\bm{H}_{i}^{\star}\|\\!$
$\displaystyle=\mathbb{E}\Big{\|}\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\gamma\phi(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}$
$\displaystyle\qquad-\phi(\bm{\mu}_{i})\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}+\gamma\phi(\bm{\mu}_{i})\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\leq\mathbb{E}\Big{\|}\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle+\\!\gamma\mathbb{E}\Big{\|}\phi(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}\Big{\|},$
(120)

where the last step follows from the triangle inequality. Here, the first term
can be bounded as

$\displaystyle\Big{\|}\phi($
$\displaystyle\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\quad\leq\Big{\|}\phi(\bm{\mu}_{k,i})(\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}})\Big{\|}$
$\displaystyle\qquad+\Big{\|}(\phi(\bm{\mu}_{k,i})-\phi(\bm{\mu}_{i}))\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\quad\leq\big{\|}\phi(\bm{\mu}_{k,i})\big{\|}\big{\|}\phi(\bm{\mu}_{k,i})-\phi(\bm{\mu}_{i})\big{\|}$
$\displaystyle\qquad+\big{\|}\phi(\bm{\mu}_{k,i})-\phi(\bm{\mu}_{i})\big{\|}\big{\|}\phi(\bm{\mu}_{i})\big{\|}$
$\displaystyle\quad\stackrel{{\scriptstyle(a)}}{{\leq}}B_{\phi}L_{\phi}\|\bm{\mu}_{k,i}-\bm{\mu}_{i}\|+B_{\phi}L_{\phi}\|\bm{\mu}_{k,i}-\bm{\mu}_{i}\|,$
(121)

where $(a)$ follows from Assumption 2. Taking expectations and using (51) and
(VII-C), it follows that

$\mathbb{E}\Big{\|}\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})\phi(\bm{\mu}_{i})^{\operatorname{\mathsf{T}}}\Big{\|}\leq
2B_{\phi}L_{\phi}B_{\textup{TV}}.$ (122)

Similarly, the second term in (VII-C) can be bounded as

$\displaystyle\Big{\|}\phi$
$\displaystyle(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}-\phi(\bm{\mu}_{i})\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\leq\Big{\|}\phi(\bm{\mu}_{k,i})(\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}-\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}})\Big{\|}$
$\displaystyle\quad+\Big{\|}(\phi(\bm{\mu}_{k,i})-\phi(\bm{\mu}_{i}))\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\leq\big{\|}\phi(\bm{\mu}_{k,i})\big{\|}\big{\|}\phi(\bm{\eta}_{k,i+1})-\phi(\bm{\eta}_{i+1})\big{\|}$
$\displaystyle\quad+\big{\|}\phi(\bm{\mu}_{k,i})-\phi(\bm{\mu}_{i})\big{\|}\big{\|}\phi(\bm{\eta}_{i+1})\big{\|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}B_{\phi}L_{\phi}\|\bm{\eta}_{k,i+1}-\bm{\eta}_{i+1}\|+B_{\phi}L_{\phi}\|\bm{\mu}_{k,i}-\bm{\mu}_{i}\|$
(123)

where $(a)$ follows from Assumption 2. Using (51) and (52) we get:

$\displaystyle\mathbb{E}\Big{\|}\phi(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}$
$\displaystyle-\phi(\bm{\mu}_{i})\phi(\bm{\eta}_{i+1})^{\operatorname{\mathsf{T}}}\Big{\|}$
$\displaystyle\leq
B_{\phi}L_{\phi}(B_{\textup{TV}}+\widetilde{B}_{\textup{TV}}).$ (124)

Combining (122) and (VII-C) in addition to the fact that
$\widetilde{B}_{\textup{TV}}~{}\leq~{}B_{\textup{TV}}$ (since
$\kappa(\mathbb{T})<1$) yields:

$\mathbb{E}\|\bm{H}_{k,i}-\bm{H}_{i}^{\star}\|\leq
2B_{\phi}L_{\phi}B_{\textup{TV}}(1+\gamma).$ (125)

###  VII-D Proof of Theorem 2

For compactness of notation, it is useful to introduce the following
quantities, which collect variables from across all agents:

$\displaystyle\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}$
$\displaystyle\triangleq\mathrm{col}\left\\{\bm{w}_{1,i},\ldots,\bm{w}_{K,i}\right\\}$
(126) $\displaystyle\mathcal{C}$ $\displaystyle\triangleq C\otimes I_{M}$
(127) $\displaystyle\bm{\mathcal{H}}_{i}$
$\displaystyle\triangleq\mathrm{diag}\left\\{\bm{H}_{k,i}\right\\}_{k=1}^{K}$
(128) $\displaystyle\bm{\mathcal{H}}_{i}^{\star}$ $\displaystyle\triangleq
I_{K}\otimes\bm{H}_{i}^{\star}$ (129) $\displaystyle\bm{d}_{i}$
$\displaystyle\triangleq\mathrm{col}\left\\{\bm{d}_{k,i}\right\\}_{k=1}^{K}$
(130)

Then, the equations (39)–(41) can be written as:

$\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}=\mathcal{C}^{\operatorname{\mathsf{T}}}\Big{(}\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{)}.$
(131)

Moreover, we can define the following $K$-times extended centroid vector:

$\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}\triangleq\mathds{1}_{K}\otimes\bm{w}_{c,i}=\left(\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}.$ (132)

If we decompose $\bm{\mathcal{H}}_{i}$ into its centralized component
$\bm{\mathcal{H}}_{i}^{\star}$ and the respective disagreement matrix
$\bm{\Delta}_{i}\triangleq\bm{\mathcal{H}}_{i}-\bm{\mathcal{H}}_{i}^{\star}$,
we obtain:

$\displaystyle\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}$
$\displaystyle=\left(\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\right)\Big{(}\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{)}$
$\displaystyle=\left(\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\right)$
$\displaystyle\qquad\Big{(}\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}-\alpha\bm{\Delta}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{)}$
$\displaystyle=\left(\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\right)$
$\displaystyle\qquad\Big{(}\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\right)(\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i})-\alpha\bm{\Delta}_{i}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{)},$
(133)

where the last step follows from the fact that

$\displaystyle\mathcal{C}^{\operatorname{\mathsf{T}}}\big{(}I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\big{)}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}$
$\displaystyle\quad=\Big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{)}\big{(}I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\big{)}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}.$
(134)

Furthermore, taking the norms of both sides in (VII-D) leads to

$\displaystyle\Big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\Big{\|}$
$\displaystyle\leq\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}$
$\displaystyle\qquad\Big{\|}\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\right)(\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i})-\alpha\bm{\Delta}_{i}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{\|}$
$\displaystyle\leq\\!\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}\left\|I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\right\|\\!\|\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}\|$
$\displaystyle+\alpha\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}\Big{(}\|\bm{\Delta}_{i}\|\|\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\|+\|\bm{d}_{i}\|\Big{)}.$
(135)

Since the combination matrix $C$ is a primitive stochastic matrix and
symmetric, it follows that [45]:

$\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}-\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}=\lambda_{2}<1.$ (136)

Moreover, we know from Lemma 1 that

$\mathbb{E}\|\bm{\Delta}_{i}\|\leq
2B_{\phi}L_{\phi}B_{\textup{TV}}(1+\gamma).$ (137)

Additionally, in Appendix VII-F, we establish (138)–(141) which hold for any
realization (with probability one). From (2), note that:

$\big{\|}I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\big{\|}<1$ (138)

whenever $\rho>\gamma L_{\phi}B_{\phi}/\sqrt{2}$. Specifically, if $\rho\geq
0.75\gamma L_{\phi}B_{\phi}$, then

$\big{\|}I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\big{\|}\leq(1-0.08\alpha\gamma
L_{\phi}B_{\phi}).$ (139)

In addition, we show in Lemma 2 that

$\displaystyle\left\|\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\right\|\leq\frac{\sqrt{K}R_{\textup{max}}}{0.08\gamma
L_{\phi}}$ (140)

and in expression (165) that

$\|\bm{d}_{i}\|\leq\sqrt{K}R_{\textup{max}}B_{\phi}.$ (141)

Inserting these results into (VII-D) yields the following norm recursion:

$\displaystyle\mathbb{E}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\big{\|}$
$\displaystyle\leq\lambda_{2}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})\mathbb{E}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}\big{\|}+\alpha\lambda_{2}\sqrt{K}\epsilon.$
(142)

Let us define the constant
$\widetilde{\lambda}_{2}\triangleq\lambda_{2}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})$. Iterating (VII-D) over time, we arrive at

$\displaystyle\mathbb{E}\left\|\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\right\|$
$\displaystyle\qquad\leq\>\widetilde{\lambda}_{2}^{i+1}\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|+\alpha\lambda_{2}\sqrt{K}\epsilon\sum_{j=1}^{i+1}\widetilde{\lambda}_{2}^{i+1-j}$
$\displaystyle\qquad\leq\>\widetilde{\lambda}_{2}^{i+1}\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|+\alpha\lambda_{2}\sqrt{K}\epsilon\frac{1}{1-\widetilde{\lambda}_{2}}$
$\displaystyle\qquad\stackrel{{\scriptstyle(a)}}{{\leq}}\>\alpha\lambda_{2}\sqrt{K}\epsilon\frac{1}{1-\widetilde{\lambda}_{2}}+O(\alpha^{2})$
(143)

where $(a)$ holds whenever:

$\displaystyle\widetilde{\lambda}_{2}^{i}\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|\leq
c\alpha^{2}$ $\displaystyle\Longleftrightarrow
i\log\widetilde{\lambda}_{2}\leq 2\log\alpha+\log
c-\log\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|$
$\displaystyle\Longleftrightarrow
i\geq\frac{2\log\alpha}{\log\widetilde{\lambda}_{2}}+O(1)=O(\log\alpha)=o(1/\alpha),$
(144)

where $c$ is an arbitrary constant.

###  VII-E Proof of Theorem 3

We begin by rewriting the baseline strategy recursion (70)–(71) in the form:

$\displaystyle\bm{w}_{i+1}^{\star}=\left((1-2\rho\alpha)I-\alpha\bm{H}_{i}^{\star}\right)\bm{w}_{i}^{\star}+\alpha\bm{d}_{i}^{\star},$
(145)

where $\bm{H}_{i}^{\star}$ is defined in (61), and

$\bm{d}_{i}^{\star}\triangleq\Big{(}\frac{1}{K}\sum_{k=1}^{K}\bm{r}_{k,i}\Big{)}\phi(\bm{\mu}_{i}).$
(146)

We introduce the $K$-times extended versions of the vectors:

$\bm{\mathcal{D}}_{i}^{\star}\triangleq\mathds{1}_{K}\otimes\bm{d}_{i}^{\star},\quad\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}^{\star}=\mathds{1}_{K}\otimes\bm{w}_{i}^{\star}.$
(147)

Then, the baseline recursion (145) transforms into

$\displaystyle\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}^{\star}=\left((1-2\rho\alpha)I-\alpha\bm{\mathcal{H}}_{i}^{\star}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}^{\star}+\alpha\bm{\mathcal{D}}_{i}^{\star}.$
(148)

It follows from the extended network centroid definition (132) and (148) that

$\displaystyle\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}$
$\displaystyle=\left(I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\right)(\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i})$
$\displaystyle\quad-\alpha\big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\big{)}\bm{\Delta}_{i}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\big{)}(\bm{\mathcal{D}}_{i}^{\star}-\bm{d}_{i}).$ (149)

where we used the facts that

$\displaystyle\Big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{)}\bm{\mathcal{D}}_{i}^{\star}=\bm{\mathcal{D}}_{i}^{\star},$ (150)

and

$\Big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{)}\bm{\mathcal{H}}_{i}^{\star}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}=\bm{\mathcal{H}}_{i}^{\star}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}.$
(151)

Next, if we define the following average agent disagreement relative to the
baseline term

$\widetilde{\bm{d}}_{i}\triangleq\frac{1}{K}\sum_{k=1}^{K}(\bm{d}_{i}^{\star}-\bm{d}_{k,i}),$
(152)

it holds that

$\widetilde{\bm{\mathcal{D}}}_{i}\triangleq\mathds{1}_{K}\otimes\widetilde{\bm{d}}_{i}=\Big{(}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{)}(\bm{\mathcal{D}}_{i}^{\star}-\bm{d}_{i}).$ (153)

Subsequently, taking the norm of both sides in (VII-E) and applying the
triangle inequality, we get

$\displaystyle\Big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\Big{\|}$
$\displaystyle\quad\leq\Big{\|}I(1-2\alpha\rho)-\alpha\bm{\mathcal{H}}_{i}^{\star}\Big{\|}\Big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}\Big{\|}$
$\displaystyle\qquad+\alpha\Big{\|}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}\big{\|}\bm{\Delta}_{i}\big{\|}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\big{\|}+\alpha\big{\|}\widetilde{\bm{\mathcal{D}}}_{i}\big{\|}.$
(154)

First, observe that

$\displaystyle\Big{\|}\frac{1}{K}\mathds{1}_{K}\mathds{1}_{K}^{\operatorname{\mathsf{T}}}\otimes
I\Big{\|}=1.$ (155)

Moreover, from Assumption 2 and Corollary 1, it holds that

$\displaystyle\mathbb{E}\big{\|}\widetilde{\bm{d}}_{i}\big{\|}$
$\displaystyle=\mathbb{E}\Big{\|}\frac{1}{K}\sum_{k=1}^{K}\bm{r}_{k,i}(\phi(\bm{\mu}_{i})-\phi(\bm{\mu}_{k,i}))\Big{\|}$
$\displaystyle\leq R_{\textup{max}}L_{\phi}B_{\textup{TV}},$ (156)

and accordingly,

$\mathbb{E}\big{\|}\widetilde{\bm{\mathcal{D}}}_{i}\big{\|}\leq\sqrt{K}R_{\textup{max}}L_{\phi}B_{\textup{TV}}.$
(157)

By using the same bounds (138)–(141) from Appendix VII-D for the other terms
(which are established in Lemma 1, Lemma 2, (2), and (165)), we arrive at the
recursion:

$\displaystyle\mathbb{E}\Big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\Big{\|}$
$\displaystyle\qquad\leq(1-0.08\alpha\gamma
B_{\phi}L_{\phi})\mathbb{E}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i}\big{\|}+\alpha\sqrt{K}\epsilon^{\star},$
(158)

where

$\epsilon^{\star}\triangleq
R_{\textup{max}}B_{\textup{TV}}\Big{(}\frac{2B_{\phi}(1+\gamma)}{0.08\gamma}+L_{\phi}\Big{)}.$
(159)

Iterating over time, we get:

$\displaystyle\mathbb{E}\Big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}^{\star}-\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{c,i+1}\Big{\|}$
$\displaystyle\quad\leq\>(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}^{\star}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|$
$\displaystyle\qquad+\alpha\sqrt{K}\epsilon^{\star}\sum_{j=1}^{i+1}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1-j}$ $\displaystyle\quad\leq\>(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\|\operatorname{{\scriptstyle\mathcal{W}}}_{0}^{\star}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\|+\frac{\sqrt{K}\epsilon^{\star}}{0.08\gamma
B_{\phi}L_{\phi}}$
$\displaystyle\quad\stackrel{{\scriptstyle(a)}}{{\leq}}\>\frac{\sqrt{K}\epsilon^{\star}}{0.08\gamma
B_{\phi}L_{\phi}}+o(1)$ (160)

where $(a)$ holds whenever

$\displaystyle(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\big{\|}\operatorname{{\scriptstyle\mathcal{W}}}_{0}^{\star}-\operatorname{{\scriptstyle\mathcal{W}}}_{c,0}\big{\|}=o(1)$
$\displaystyle\qquad\Longleftrightarrow i\log(1-0.08\alpha\gamma
B_{\phi}L_{\phi})=o(1)$ $\displaystyle\qquad\Longleftrightarrow
i\geq\frac{o(1)}{\log(1-0.08\alpha\gamma B_{\phi}L_{\phi})}\geq
o\left(\frac{1}{\alpha\gamma B_{\phi}L_{\phi}}\right).$ (161)

###  VII-F Auxiliary Results

In the following lemma, we prove that the value function parameters are
bounded in norm.

######  Lemma 2 (Bounded parameters).

For each agent $k\in\mathcal{K}$, the iterate $\bm{w}_{k,i}$ is bounded in
norm if $\rho>\gamma B_{\phi}L_{\phi}/\sqrt{2}$, with probability one. In
particular, if $\rho\geq 0.75\gamma B_{\phi}L_{\phi}$, then

$\displaystyle\left\|\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\right\|\leq\frac{\sqrt{K}R_{\textup{max}}}{0.08\gamma
L_{\phi}}$ (162)

after $i\geq i_{0}=o\left(1/(\alpha\gamma B_{\phi}L_{\phi})\right)$
iterations.

Proof. Taking the norms of both sides of (131) yields:

$\displaystyle\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}\big{\|}$
$\displaystyle=\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}\big{(}\left((1-2\alpha\rho)I-\alpha\bm{\mathcal{H}}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\big{)}\Big{\|}$
$\displaystyle\leq\Big{\|}\mathcal{C}^{\operatorname{\mathsf{T}}}\Big{\|}\Big{\|}\left((1-2\alpha\rho)I-\alpha\bm{\mathcal{H}}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{\|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\Big{\|}\left((1-2\alpha\rho)I-\alpha\bm{\mathcal{H}}_{i}\right)\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}+\alpha\bm{d}_{i}\Big{\|}$
$\displaystyle\leq\big{\|}(1-2\alpha\rho)I-\alpha\bm{\mathcal{H}}_{i}\big{\|}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\big{\|}+\alpha\big{\|}\bm{d}_{i}\big{\|}$
(163)

where $(a)$ follows from the fact that the singular values of doubly-
stochastic matrices are equal to one. Note that

$\displaystyle\big{\|}(1-2\alpha\rho)I-\alpha\bm{\mathcal{H}}_{k,i}\big{\|}$
$\displaystyle=\big{\|}(1-2\alpha\rho)I-\alpha\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}+\alpha\gamma\phi(\bm{\mu}_{k,i})\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}\big{\|}$
$\displaystyle=\big{\|}(1-2\alpha\rho)I-\alpha(1-\gamma)\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}$
$\displaystyle\qquad\qquad-\alpha\gamma\phi(\bm{\mu}_{k,i})\big{(}\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}\big{)}\big{\|}$
$\displaystyle\leq\big{\|}(1-2\alpha\rho)I-\alpha(1-\gamma)\phi(\bm{\mu}_{k,i})\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}\big{\|}$
$\displaystyle\qquad\qquad+\alpha\gamma\|\phi(\bm{\mu}_{k,i})\|\big{\|}\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}\big{\|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}(1-2\alpha\rho)+\alpha\gamma\|\phi(\bm{\mu}_{k,i})\|\big{\|}\phi(\bm{\mu}_{k,i})^{\operatorname{\mathsf{T}}}-\phi(\bm{\eta}_{k,i+1})^{\operatorname{\mathsf{T}}}\big{\|}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}(1-2\alpha\rho)+\alpha\gamma
B_{\phi}L_{\phi}\big{\|}\bm{\mu}_{k,i}-\bm{\eta}_{k,i+1}\big{\|}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}(1-2\alpha\rho)+\alpha\gamma
B_{\phi}L_{\phi}\sqrt{2}$ (164)

where $(a)$ follows from the equality of spectral norm and maximum eigenvalue
for symmetric matrices, $(b)$ follows from Assumption 2, and $(c)$ follows
from the fact that the mean-square distance cannot exceed 2 over the
probability simplex. The upper bound in (2) is smaller than 1 whenever
$\rho>\gamma B_{\phi}L_{\phi}/\sqrt{2}$. Moreover,

$\displaystyle\big{\|}\bm{d}_{k,i}\big{\|}=\big{\|}\bm{r}_{k,i}\phi(\bm{\mu}_{k,i})\big{\|}\leq
R_{\textup{max}}B_{\phi}.$ (165)

As a result, if $\rho\geq 0.75\gamma B_{\phi}L_{\phi}$, we get:

$\displaystyle\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}\big{\|}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:rho_norm_bound}}}{{\leq}}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\big{\|}+\alpha\big{\|}\bm{d}_{i}\big{\|}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:dki_bound}}}{{\leq}}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i}\big{\|}+\alpha\sqrt{K}R_{\textup{max}}B_{\phi}.$
(166)

Iterating this recursion starting from $i=0$ results in

$\displaystyle\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{i+1}\big{\|}$
$\displaystyle\leq\alpha\sqrt{K}R_{\textup{max}}B_{\phi}\sum_{j=1}^{i+1}(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1-j}$ $\displaystyle\qquad+(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\big{\|}\operatorname{{\scriptstyle\mathcal{W}}}_{0}\big{\|}$
$\displaystyle\leq\frac{\sqrt{K}R_{\textup{max}}}{0.08\gamma
L_{\phi}}+(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\big{\|}\operatorname{{\boldsymbol{\scriptstyle\mathcal{W}}}}_{0}\big{\|}$
$\displaystyle=\frac{\sqrt{K}R_{\textup{max}}}{0.08\gamma L_{\phi}}+o(1),$
(167)

where the last step holds whenever

$\displaystyle(1-0.08\alpha\gamma
B_{\phi}L_{\phi})^{i+1}\big{\|}\operatorname{{\scriptstyle\mathcal{W}}}_{0}\big{\|}=o(1)$
$\displaystyle\qquad\Longleftrightarrow i\log(1-0.08\alpha\gamma
B_{\phi}L_{\phi})=o(1)$ $\displaystyle\qquad\Longleftrightarrow
i\geq\frac{o(1)}{\log(1-0.08\alpha\gamma B_{\phi}L_{\phi})}\geq
o\left(\frac{1}{\alpha\gamma B_{\phi}L_{\phi}}\right).$ (168)

$\hfill\blacksquare$

## Acknowledgments

The authors would like to thank Visa Koivunen for useful discussions on Dec-
POMDPs and their applications in sensing.

## References

  * [1] L. Busoniu, R. Babuska, and B. De Schutter, “A comprehensive survey of multiagent reinforcement learning,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 38, no. 2, pp. 156–172, 2008.
  * [2] K. Zhang, Z. Yang, and T. Başar, “Multi-agent reinforcement learning: A selective overview of theories and algorithms,” _Handbook of Reinforcement Learning and Control_ , pp. 321–384, 2021.
  * [3] J. W. Huang, Q. Zhu, V. Krishnamurthy, and T. Basar, “Distributed correlated Q-learning for dynamic transmission control of sensor networks,” in _Proc. IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2010, pp. 1982–1985.
  * [4] J. Lunden, S. R. Kulkarni, V. Koivunen, and H. V. Poor, “Multiagent reinforcement learning based spectrum sensing policies for cognitive radio networks,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 7, no. 5, pp. 858–868, 2013.
  * [5] S. Bhattacharya, S. Kailas, S. Badyal, S. Gil, and D. Bertsekas, “Multiagent rollout and policy iteration for POMDP with application to multi-robot repair problems,” in _Proc. Conference on Robot Learning_. PMLR, 2021, pp. 1814–1828.
  * [6] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, _et al._ , “Grandmaster level in StarCraft II using multi-agent reinforcement learning,” _Nature_ , vol. 575, no. 7782, pp. 350–354, 2019.
  * [7] M. Samvelyan, T. Rashid, C. Schroeder de Witt, G. Farquhar, N. Nardelli, T. G. J. Rudner, C.-M. Hung, P. H. S. Torr, J. Foerster, and S. Whiteson, “The starcraft multi-agent challenge,” in _Proc. International Conference on Autonomous Agents and MultiAgent Systems_ , ser. AAMAS ’19, 2019, p. 2186–2188.
  * [8] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _Nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [9] F. A. Oliehoek and C. Amato, _A Concise Introduction to Decentralized POMDPs_. Springer, 2016.
  * [10] E. J. Sondik, “The optimal control of partially observable Markov processes over the infinite horizon: Discounted costs,” _Operations Research_ , vol. 26, no. 2, pp. 282–304, 1978.
  * [11] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” _Artificial Intelligence_ , vol. 101, no. 1, pp. 99–134, 1998.
  * [12] V. Krishnamurthy, _Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing_. Cambridge University Press, 2016.
  * [13] J. Hazla, A. Jadbabaie, E. Mossel, and M. A. Rahimian, “Bayesian decision making in groups is hard,” _Operations Research_ , vol. 69, no. 2, pp. 632–654, 2021.
  * [14] S. Omidshafiei, J. Pazis, C. Amato, J. P. How, and J. Vian, “Deep decentralized multi-task multi-agent reinforcement learning under partial observability,” in _Proc. International Conference on Machine Learning_. PMLR, 2017, pp. 2681–2690.
  * [15] J. K. Gupta, M. Egorov, and M. Kochenderfer, “Cooperative multi-agent control using deep reinforcement learning,” in _Proc. AAMAS_ , 2017, pp. 66–83.
  * [16] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual multi-agent policy gradients,” in _Proc. AAAI Conference on Artificial Intelligence_ , 2018, pp. 2974–2982.
  * [17] P. Moreno, J. Humplik, G. Papamakarios, B. A. Pires, L. Buesing, N. Heess, and T. Weber, “Neural belief states for partially observed domains,” in _NeurIPS Workshop on Reinforcement Learning under Partial Observability_ , 2018, pp. 1–5.
  * [18] K. Gregor, G. Papamakarios, F. Besse, L. Buesing, and T. Weber, “Temporal difference variational auto-encoder,” in _Proc. International Conference on Learning Representations_ , 2019, pp. 1–17. [Online]. Available: https://openreview.net/forum?id=S1x4ghC9tQ
  * [19] A. H. Sayed, _Inference and Learning from Data_. Cambridge University Press, 2022, 3 vols.
  * [20] P. Moreno, E. Hughes, K. R. McKee, B. A. Pires, and T. Weber, “Neural recursive belief states in multi-agent reinforcement learning,” _arXiv:2102.02274_ , 2021.
  * [21] D. Muglich, L. M. Zintgraf, C. A. S. De Witt, S. Whiteson, and J. Foerster, “Generalized beliefs for cooperative AI,” in _Proc. International Conference on Machine Learning_ , vol. 162, Jul 2022, pp. 16 062–16 082.
  * [22] W. Mao, K. Zhang, E. Miehling, and T. Basar, “Information state embedding in partially observable cooperative multi-agent reinforcement learning,” in _Proc. IEEE CDC_ , 2020, pp. 6124–6131.
  * [23] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. MIT Press, 2018.
  * [24] J. Tsitsiklis and B. Van Roy, “Analysis of temporal-difference learning with function approximation,” _Advances in Neural Information Processing Systems_ , vol. 9, 1996.
  * [25] S. P. Singh, T. Jaakkola, and M. I. Jordan, “Learning without state-estimation in partially observable Markovian decision processes,” in _Proc. Machine Learning_ , 1994, pp. 284–292.
  * [26] A. Rodriguez, R. Parr, and D. Koller, “Reinforcement learning using approximate belief states,” in _Advances in Neural Information Processing Systems_ , vol. 12. MIT Press, 1999.
  * [27] H. Kimura, K. Miyazaki, and S. Kobayashi, “Reinforcement learning in POMDPs with function approximation,” in _Proc. ICML_ , vol. 97, 1997, pp. 152–160.
  * [28] Q. Cai, Z. Yang, and Z. Wang, “Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency,” in _Proc. International Conference on Machine Learning_ , 2022, pp. 2485–2522.
  * [29] S. Kar, J. M. F. Moura, and H. V. Poor, “${{\cal Q}{\cal D}}$-learning: A collaborative distributed strategy for multi-agent reinforcement learning through ${\rm consensus}+{\rm innovations}$,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 7, pp. 1848–1862, 2013.
  * [30] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar, “Fully decentralized multi-agent reinforcement learning with networked agents,” in _Proc. International Conference on Machine Learning_. PMLR, 2018, pp. 5872–5881.
  * [31] L. Cassano, K. Yuan, and A. H. Sayed, “Multiagent fully decentralized value function learning with linear convergence rates,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 4, pp. 1497–1512, 2021.
  * [32] S. V. Macua, I. Davies, A. Tukiainen, and E. M. De Cote, “Fully distributed actor-critic architecture for multitask deep reinforcement learning,” _The Knowledge Engineering Review_ , vol. 36, pp. 1–30, 2021.
  * [33] X. Sha, J. Zhang, K. You, K. Zhang, and T. Başar, “Fully asynchronous policy evaluation in distributed reinforcement learning over networks,” _Automatica_ , vol. 136, p. 110092, 2022.
  * [34] Y. Lin, G. Qu, L. Huang, and A. Wierman, “Multi-agent reinforcement learning in stochastic networked systems,” in _Advances in Neural Information Processing Systems_ , vol. 34, 2021, pp. 7825–7837.
  * [35] G. Wang, S. Lu, G. Giannakis, G. Tesauro, and J. Sun, “Decentralized TD tracking with linear function approximation and its finite-time analysis,” in _Advances in Neural Information Processing Systems_ , 2020, pp. 13 762–13 772.
  * [36] J. Sun, G. Wang, G. B. Giannakis, Q. Yang, and Z. Yang, “Finite-time analysis of decentralized temporal-difference learning with linear function approximation,” in _Proc. International Conference on Artificial Intelligence and Statistics_ , 2020, pp. 4485–4495.
  * [37] Q. Lin and Q. Ling, “Decentralized TD(0) with gradient tracking,” _IEEE Signal Processing Letters_ , vol. 28, pp. 723–727, 2021.
  * [38] Y. Li, Y. Tang, R. Zhang, and N. Li, “Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach,” _IEEE Transactions on Automatic Control_ , pp. 6429–6444, 2021\.
  * [39] H. Wang, S. Lin, H. Jafarkhani, and J. Zhang, “Distributed Q-learning with state tracking for multi-agent networked control,” in _Proc. International Conference on Autonomous Agents and Multi-Agent Systems_ , 2021, pp. 1692–1694.
  * [40] M. Kayaalp, V. Bordignon, S. Vlaski, and A. H. Sayed, “Hidden Markov modeling over graphs,” in _Proc. IEEE Data Science and Learning Workshop (DSLW)_ , 2022, pp. 1–6.
  * [41] M. Kayaalp, V. Bordignon, S. Vlaski, V. Matta, and A. H. Sayed, “Distributed Bayesian learning of dynamic states,” _arXiv:2212.02565_ , 2022.
  * [42] O. Hlinka, O. Slučiak, F. Hlawatsch, P. M. Djurić, and M. Rupp, “Likelihood consensus and its application to distributed particle filtering,” _IEEE Transactions on Signal Processing_ , vol. 60, no. 8, pp. 4334–4349, 2012.
  * [43] G. Battistelli and L. Chisci, “Kullback–Leibler average, consensus on probability densities, and distributed state estimation with guaranteed stability,” _Automatica_ , vol. 50, no. 3, pp. 707–718, 2014.
  * [44] S. Bandyopadhyay and S. Chung, “Distributed Bayesian filtering using logarithmic opinion pool for dynamic sensor networks,” _Automatica_ , vol. 97, pp. 7–17, 2018.
  * [45] A. H. Sayed, “Adaptation, learning, and optimization over networks,” _Foundations and Trends in Machine Learning_ , vol. 7, no. 4-5, pp. 311–801, July 2014.
  * [46] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 1, pp. 48–61, 2009.
  * [47] A. G. Dimakis, S. Kar, J. M. Moura, M. G. Rabbat, and A. Scaglione, “Gossip algorithms for distributed signal processing,” _Proc. IEEE_ , vol. 98, no. 11, pp. 1847–1864, 2010.
  * [48] P. Di Lorenzo and G. Scutari, “Next: In-network nonconvex optimization,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 2, no. 2, pp. 120–136, 2016.
  * [49] J. Chen and A. H. Sayed, “On the learning behavior of adaptive networks—part I: Transient analysis,” _IEEE Transactions on Information Theory_ , vol. 61, no. 6, pp. 3487–3517, 2015.
  * [50] ——, “On the learning behavior of adaptive networks—part II: Performance analysis,” _IEEE Transactions on Information Theory_ , vol. 61, no. 6, pp. 3518–3548, 2015.
  * [51] M. Kayaalp, S. Vlaski, and A. H. Sayed, “Dif-MAML: Decentralized multi-agent meta-learning,” _IEEE Open Journal of Signal Processing_ , vol. 3, pp. 71–93, 2022.
  * [52] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_ , 2nd ed. Cambridge University Press, 2011.
  * [53] R. S. Sutton, “Learning to predict by the methods of temporal differences,” _Machine Learning_ , vol. 3, no. 1, pp. 9–44, 1988.
  * [54] J. Z. Kolter and A. Y. Ng, “Regularization and feature selection in least-squares temporal difference learning,” in _Proc. International Conference on Machine Learning_ , 2009, pp. 521–528.
  * [55] M. W. Hoffman, A. Lazaric, M. Ghavamzadeh, and R. Munos, “Regularized least squares temporal difference learning with nested $\ell_{2}$ and $\ell_{1}$ penalization,” in _Proc. European Workshop on Reinforcement Learning_. Springer, 2011, pp. 102–114.
  * [56] J. Farebrother, M. C. Machado, and M. Bowling, “Generalization and regularization in DQN,” _arXiv:1810.00123_ , 2018.
  * [57] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman, “Quantifying generalization in reinforcement learning,” in _Proc. International Conference on Machine Learning_ , vol. 97, 09–15 Jun 2019, pp. 1282–1289.
  * [58] T. Li, H. Fan, J. García, and J. M. Corchado, “Second-order statistics analysis and comparison between arithmetic and geometric average fusion: Application to multi-sensor target tracking,” _Information Fusion_ , vol. 51, pp. 233–243, 2019.
  * [59] M. Kayaalp, Y. Inan, E. Telatar, and A. H. Sayed, “On the arithmetic and geometric fusion of beliefs for distributed inference,” _arXiv:2204.13741_ , April 2022.
  * [60] S. I. Resnick, _Adventures in Stochastic Processes_. Birkhäuser, 2002.
  * [61] E. Jorge, M. Kågebäck, F. D. Johansson, and E. Gustavsson, “Learning to play guess who? and inventing a grounded language as a consequence,” _arXiv:1611.03218_ , 2016.
  * [62] Y. Polyanskiy and Y. Wu, “Strong data-processing inequalities for channels and Bayesian networks,” in _Convexity and Concentration_. New York, NY: Springer New York, 2017, pp. 211–249.
  * [63] J. Bretagnolle and C. Huber, “Estimation des densités : Risque minimax,” in _Séminaire de Probabilités XII_ , C. Dellacherie, P. A. Meyer, and M. Weil, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1978, pp. 342–363.