# Multi-agent Off-policy Actor-Critic Reinforcement Learning for Partially
Observable Environments

Ainur Zhaikhan and Ali H. Sayed A. Zhaikhan and A. H. Sayed are with the
Adaptive Systems Laboratory, École Polytechnique Fédérale de Lausanne (EPFL),
CH-1015, Switzerland. Emails<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract

This study proposes the use of a social learning method to estimate a global
state within a multi-agent off-policy actor-critic algorithm for reinforcement
learning (RL) operating in a partially observable environment. We assume that
the network of agents operates in a fully-decentralized manner, possessing the
capability to exchange variables with their immediate neighbors. The proposed
design methodology is supported by an analysis demonstrating that the
difference between final outcomes, obtained when the global state is fully
observed versus estimated through the social learning method, is
$\varepsilon$-bounded when an appropriate number of iterations of social
learning updates are implemented. Unlike many existing dec-POMDP-based RL
approaches, the proposed algorithm is suitable for model-free multi-agent
reinforcement learning as it does not require knowledge of a transition model.
Furthermore, experimental results illustrate the efficacy of the algorithm and
demonstrate its superiority over the current state-of-the-art methods.

###### Index Terms:

multi-agent, decentralized, off-policy, actor-critic, dec-POMDP

##  I Introduction

Collaborative multi-agent reinforcement learning is a prominent area of
research due to its potential to achieve outcomes that are either
inefficiently achieved or altogether unattainable by individual agents.
However, this collaborative approach introduces its own set of complexities
and constraints. One fundamental challenge is the issue of partial
observability. When multiple agents are deployed across an environment, they
may only have access to limited information, observing only specific portions
of the overall environment.

Most traditional adaptations of single-agent reinforcement learning (RL) to
multi-agent scenarios assume full observability of the state variable and
require joint knowledge among agents. Some MARL algorithms adopt centralized
training and decentralized execution (CTDE) paradigms, such as MADDPG [1],
QMIX [2], and MAVEN [3], or Independent Learning (IL) paradigms [4], which
still involve restrictive assumptions that may not be applicable to complex
scenarios. In CTDE, each agent can access the actions and observations of all
other agents during the learning phase, which are required for updating
variables of interest. However, during the execution phase, the policies
followed by each agent are private and based solely on their local
observations. In Independent Learning, agents ignore the learning of other
agents and treat the effects of other agents as environmental changes,
potentially undermining the stability of the overall model.

The Decentralized Partially Observable Markov Decision Process (Dec-POMDP)
setting, which perfectly describes partially observable MARL scenarios, is
proven to be an NEXP-hard problem and lacks a formal solution. Consequently,
understanding and addressing these partial observability scenarios is crucial
for the practical application of multi-agent reinforcement learning.

In this work, we extend the multi-agent off-policy actor-critic (MAOPAC)
algorithm [5], originally designed for fully observable environments, to
handle partially observable settings. The primary reason for focusing on this
MARL setting is that off-policy learning [6, 7, 8, 9] provides a more general
setting compared to its on-policy counterpart, as it allows the behavioral
policy to differ from the estimated target policy. Moreover, off-policy
algorithms offer the flexibility to adjust agents’ behavior, thereby enhancing
the efficiency of their exploration strategies. Additionally, MAOPAC is an
algorithm with theoretical convergence guarantees. Consequently, by
establishing the convergence of our proposed method in partially observed
environments, we ensure that our results also guarantee convergence to the
optimal solution.

Achieving full decentralization in actor-critic approaches is inherently
challenging because they depend on shared variables for learning [10] and also
suffer from partial state observability. To overcome this challenge, we
propose leveraging social learning strategies [11, 12, 13] to estimate the
global state in a fully decentralized manner. Under these strategies, agents
estimate belief vectors using local observations and then iteratively diffuse
these estimates to their immediate neighbors. Existing works that offer a
fully decentralized solution often rely on neural network implementations
which can be complex and challenging to analyze. Furthermore, unlike many
existing algorithms, the proposed method does not necessitate transition
models for state estimation, thereby classifying it as a model-free
reinforcement learning algorithm. This attribute enhances its convenience and
practicality for real-world applications. The proposed method is supported
with theoretical guarantees. Specifically, we derive conditions for estimating
the global state, ensuring that the ultimate error in the policy parameter
estimation is bounded by $\varepsilon$. We also provide specific insights
tailored to a Boltzmann policy model, providing a more comprehensive
understanding of our proposed framework. Through empirical evaluation and
analysis, we demonstrate the effectiveness and robustness of our approach in
addressing the challenges posed by partially observable multi-agent
environments. Additionally, we benchmark our method against the zero-th order
policy optimization (ZOPO) approach, which, to the best of our knowledge,
stands as the most recent model-free method tailored for partially observable
multi-agent settings. Through experimental validation, we illlustrate the
superiority of our proposed algorithm in terms of performance. Furthermore,
our method offers greater convenience in implementation, thereby presenting a
compelling advantage over existing alternatives.

The organization of the paper is as follows. Section II gives an overview of
the current state of the art. Section III provides preliminary information
relevant to the algorithm. The details of the proposed algorithm are given in
Section IV. Analytical verification of the algorithm is conducted in Section
V, followed by empirical validation in Section VI. Lastly, Section VII
presents the concluding remarks.

##  II State of the art

###  II-A Settings

Multi-agent reinforcement learning within a partially observable environment
presents a complex challenge, often addressed within various settings. One
such scheme is independent learning [4], where agents disregard the influence
of others and interpret their actions as changes in the environment. In the
context of partial observability, this approach actually hides the challenge
posed by partial observability. IL assumes that the joint optimal policy can
be learnt relying solely on local observations. However, this assumption may
be valid only for basic problems, since treating other agents’ behavior as
environment may introduce instability to the underlying Markov Decision
Process (MDP).

An alternative framework that is used in the literature is one that is based
on a centralized training and decentralized execution (CTDE). Under this
setting, agents need global information during the training phase but can rely
solely on local observations for decision-making during execution. Notable
CTDE algorithms include MADPPG [1], Q-mix [2], and MAVEN [3]. Despite being a
more effective framework than IL, CTDE remains restrictive due to its
requirement for joint training.

Coordinated multi-agent RL (CoMARL) proposed in [14], presents a more
sophisticated setting due to considering the mutual influence among agents.
However, even this approach does not entirely meet the demand for completely
decentralized MARL with partial observability. It assumes existence of
independent subgroups capable of determining the global state through
centralized learning within each group. In reality, situations may arise where
observations from all agents are necessary to accurately identify the global
state. In this case, CoMARL basically becomes a centralized solution. In our
method, we delve into the scenario where agents remain decentralized both
during training and decision-making phases while accounting for partial
observability of the global state.

In single-agent scenarios, reinforcement learning with partial observability
is effectively addressed using Partially Observable Markov Decision Processes
(POMDPs). However, its multi- agent extension, known as Dec-POMDP, has been
proven to be Non-deterministic Exponential-time (NEXP) hard. Dec-POMDPs are
inherently difficult to solve, with no formal solution available except for
some approximate methods tailored to specific scenarios. Despite this, Dec-
POMDPs remain widely used in MARL literature as they offer a manageable
environment for modeling and analysis.

###  II-B State estimation in model-based learning

In the approaches given in [15, 16, 17], the probability of global states,
i.e., the belief vectors, are estimated using Bayesian rules. However,
employing Bayesian updates in these contexts necessitates knowledge of
transition models, posing a challenge for model-free reinforcement learning
(RL) problems. Consequently, these approaches are more directly related to
model-based RL or planning schemes, such as dynamic programming, where
complete model information is available [18]. Additionally, the algorithm
proposed in [17] focuses on policy evaluation rather than finding the optimal
policy. In contrast, our proposed method is designed to be model-free,
eliminating the need for a state transition model. It aims not only to
evaluate given policies but also to discover the optimal policy in partially
observable multi-agent environments.

###  II-C State estimation in model-free RL

####  II-C1 Neural Network-based Approaches

Some solutions for model-free MARL with partially observed states are based on
neural network (NN) architectures [19, 20, 21, 22]. Algorithms like those in
[20, 19, 23, 24, 25] are examples of NN-based solutions tailored for single-
agent partially observable problems. Multi-agent extensions are discussed in
[21, 26, 27]. In most NN-based approaches, the primary concept involves using
neural networks to directly map observations to observation-action values.
However, replacing state-action values with observation-action values may not
consistently yield effective results, as the success of the algorithm depends
on how well the chosen model approximates the estimated values. NN-based
solutions are typically considered brute-force methods and do not offer a
suitable environment for analysis. NN-based algorithms mainly compete with
each other in terms of implementation characteristics such as time efficiency
and complexity of NN architectures, relying largely on experimental evidence.
Our focus in this paper is on an analysis-based approaches. Given the
difference in our objectives, we will therefore avoid comparing the proposed
method with NN-based schemes.

####  II-C2 Non-neural-based Approach

A non-NN-based model-free approach has been proposed in [10]. This algorithm
localizes all learning processes by decomposing cumulative reward estimates
using zeroth-order policy optimization (ZOPO). A convergence proof is
provided; however, it is only applicable for on-policy and Monte Carlo-based
learning, such as the Reinforce algorithm. On-policy learning, as described
earlier, is a more restrictive setting than off-policy learning, which is the
focus of our work. Due to being one of the most recent model-free approaches,
we will compare our method with ZOPO in Section VI.

###  II-D Consensus-based solutions

The integration of belief diffusion to address Dec-POMDPs has been explored in
prior studies. The authors in [28, 15] investigate the applicability of
consensus protocols to Dec-POMDP settings, primarily focusing on online
planning. However, this approach has not been thoroughly examined within the
framework of reinforcement learning. These studies predominantly analyze the
algorithm from a consensus protocol standpoint without specific convergence
proofs for reinforcement learning scenarios. Furthermore, the methodologies
proposed in these works are largely heuristic in nature.

The authors in [29] incorporate belief diffusion into some basic reinforcement
learning algorithms such as Q-learning. Our approach integrates belief
diffusion into more advanced RL technique, specifically into the off-policy
multi-agent actor-critic solutions, and provides detailed analysis and
conditions conditions for convergence.

##  III Model Setting

Our setting can be modelled through a Decentralized Partial Observable Markov
decision process (Dec-POMDP) denoted by the tuple
$(\mathcal{K},\mathcal{A}_{\ell},\\{\mathcal{O}_{\ell}\\}_{\ell=1}^{K},\mathcal{S},\\{r_{\ell}\\}_{\ell=1}^{K},\mathcal{P},\\{\mathcal{L}_{\ell}\\}^{K}_{\ell=1})$,
where $\mathcal{K}\triangleq\\{1,2,...,K\\}$ is set of agents,
$\\{\mathcal{A}_{\ell}\\}_{\ell=1}^{K}$ is set of possible actions for agent
$\ell$, $\mathcal{O}$ is a continuous set of observations, and $\mathcal{S}$
is a set of states. Moreover,
$\mathcal{P}:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$ is a transition model
where the value $\mathcal{P}(s^{\prime}|s,a)$ denotes the probability of
transition to state $s^{\prime}\in\mathcal{S}$ from state $s\in\mathcal{S}$
after taking joint action
$a\triangleq\\{a_{\ell}\in\mathcal{A}_{\ell}\\}_{\ell=1}^{K}$. The likelihood
function $\mathcal{L}_{\ell}(\xi|s)$ denotes the probability of observing
$\xi\in\mathcal{O}_{\ell}$ when the true global state is $s\in\mathcal{S}$.
Communication among agents is defined by some fixed graph $G$ where nodes
represent the agents and edges represent communicability of agents.

Next, we introduce some important metrics for reinforcement learning. Let
$r_{\ell,n}\triangleq r_{\ell}(s_{n},a_{\ell,n})$ denote the individual reward
achieved by agent $\ell$ at time $n$ if at global state $s_{n}\in\mathcal{S}$
it chooses action $a_{\ell,n}\in\mathcal{A}$. We denote the reward upper-bound
by $R_{\max}$ and global reward at time $n$ by

$\displaystyle\bar{r}_{n}=\frac{1}{K}\sum\limits_{\ell=1}^{K}r_{\ell,n}$ (1)

Then, under some policy $\pi$, which drives the decisions by the agents, the
state-action value for state and action pair $(s,a)$ is defined as

$\displaystyle Q^{\pi}(s,a)$
$\displaystyle\triangleq\mathbb{E}\left[\sum_{n=0}^{\infty}\gamma^{n}\bar{r}_{n}\mid
s_{0}=s,a_{0}=a\right]$ (2)

where $\gamma$ is a discount factor. Similarly, a state value for the global
state $s$ is defined as

$\displaystyle V^{\pi}(s)$
$\displaystyle\triangleq\mathbb{E}\left[\sum_{n=0}^{\infty}\gamma^{n}\bar{r}_{n}\mid
s_{0}=s\right]$ (3)

Since the proposed algorithm is based on off-policy learning we introduce the
notation for the target and behavioral policies. Let $b_{\ell}:S\times
A\to[0,1]$ denote individual policy of agent $\ell$. Individual target
policies are approximated by local parameterized functions
$\pi_{\ell}(\cdot;\theta_{\ell})$, where $\theta_{\ell}\in\mathbb{R}^{d}$.
Policy functions $\pi_{\ell}$ are assumed to be continuously differentiable
with respect to $\theta_{\ell}$. We assume the individual target policies to
be independent. Therefore, we define the joint target policy as the product of
individual target policies

$\displaystyle\pi=\prod_{\ell=1}^{K}\pi_{\ell}(\cdot;\theta_{\ell}):A\times
S\rightarrow[0,1]$ (4)

Similarly, we define the joint behavioral policy as

$b=\prod_{\ell=1}^{K}b_{\ell}:A\times S\rightarrow[0,1]$ (5)

Off-policy learning relies on corrections, which are implemented using the
importance sampling ratio, defined as:

$\displaystyle\rho_{n}\triangleq\frac{\pi_{n}}{b}=\prod\limits_{\ell=1}^{K}\limits\frac{\pi_{\ell,n}}{b_{\ell}}$
(6)

As indicated by (6), the importance sampling ratio necessitates joint
policies. In the MAOPAC algorithm [5], the importance ratio is estimated in a
decentralized manner at each actor-critic update by iteratively diffusing
individual importance ratios until consensus:

$\displaystyle\rho_{\ell,n}\triangleq\frac{\pi_{\ell,n}}{b_{\ell}}$ (7)

We adopt this assumption in our work as well. In our analysis, we assume that
consensus-based estimation is sufficiently accurate to ignore finite-time
errors in the estimation of the joint $\rho_{n}$.

##  IV Multi-agent Off-Policy Actor-Critic for dec-POMDP

In our study, we extend the multi-agent off-policy actor-critic (MAOPAC)
algorithm described in [5] by considering scenarios where the global state is
not fully observed. We refer to the proposed extended algorithm as MAOPAC-dec-
POMDP. The MAOPAC-dec-POMDP algorithm is based on the repeated alternation of
two main learning phases, as demonstrated in Figure 1. The first phase
involves estimating the global state, while the second phase involves
performing traditional MAOPAC with some adjustments. In the following
subsections, we discuss these two phases in more detail. The complete listing
of our method is presented in Algorithm 1, which will be consistently
referenced throughout our explanation.

###  IV-A Multi-agent off-policy actor-critic learning

The MAOPAC algrotihm belongs to the family of policy gradient methods designed
to concurrently learn the optimal policies (actors) and corresponding state
values (critics). In our study, we assume that each agent has its own estimate
for state values, approximated using the following linear function:

$\displaystyle v_{\omega_{k,n}}\approx\mu_{k,n}^{T}\omega_{k,n}$ (8)

where $\mu_{k,n}$ is a state feature vector and $\omega_{k,n}$ is a parameter
vector, also referred to as the critic parameter, estimated by agent $k$ at
time $n$. Target policies are approximated with some functions
$\pi(\mu_{k,n};\theta_{k,n})$ parametrized by $\theta_{k,n}$:

$\displaystyle\pi_{k,n}\approx\pi(\mu_{k,n};\theta_{k,n})$ (9)

Therefore, the policy parameters $\theta_{k,n}$ will be referred to as  the
actor parameters.

As given in steps (27)-(28) of Algorithm 1, the updates of $\theta_{k,n}$ and
$\omega_{k,n}$ are similar to those of traditional actor-critic algorithms
with the exception of several correction factors: $\rho_{k,n}$, $e_{k,n}$ and
$M^{\theta}_{k,n}$. The importance sampling ratio $\rho_{k,n}$ is essential
for correcting the off-policy nature of learning. Off-policy learning allows
for a disparity between the agent’s behavioral policy and the target policy,
which offers practical advantages over on-policy approaches. Specifically,
when the behavioral policy is related to the estimated target policy, as in
on-policy learning, it may lead to insufficient exploration——a widely
recognized challenge known as the exploration-exploitation trade-off.
Nevertheless, off-policy learning causes instabilities. The correction factor
$\rho_{k,n}$ alone can address these instabilities when dealing with exact
state and policy values. When employing function approximations, as in our
study, additional corrections are required. Therefore, a novel variant of the
actor-critic paradigm, termed emphatic temporal difference learning (ETD), has
been proposed in [30, 31, 5]. This variant ensures stability for linear
approximation models and off-policy learning scenarios. The correction
variables $e_{k,n}$ and $M^{\theta}_{k,n}$ are motivated by ETD. The steps
(21)-(24) involve intermediate calculations necessary for computing $e_{k,n}$
and $M^{\theta}_{k,n}$. Parameters $\lambda,\zeta$ and $\gamma$ are fixed and
fall within the range $(0,1)$. In traditional MAOPAC, $\mu_{k,n}$ can be any
vector with elements that fall within the range $[0,1]$. Therefore, for our
problem, we can treat $\mu_{k,n}$ as a belief vector of size $S$, where the
$i$-th element corresponds to the probability that the current state is $i$.
In the case of full-state observation, as with MAOPAC, all elements of
$\mu_{k,n}$ are zero except for $1$ at the location of the actual state.

###  IV-B State estimation

At each iteration of the critic and actor updates, agents perform state
estimation using using the social learning strategy described by (1)-(1).
Social learning is a form of group learning that identifies the most suitable
hypothesis state from a set $\mathcal{S}$, best explaining the given
observations $\xi_{k,i}\in\mathcal{O}_{k}$. In this work, we use the Adapt-
Then-Combine social learning technique for state estimation [32, 33].

Figure 1: A block diagram illustrating the primary steps of the proposed
algorithm.

At each iteration of MAOPAC learning, we implement an internal loop for
learning the global state. At iteration $n$ of actor-critic updates, all
agents receive a set of individual observations
$\\{\xi_{k,t}^{n}\\}_{t=0}^{T}$, which are dependent on the current unknown
global state of nature, i.e., $s_{n}$. Using their individual likelihood
functions $L_{k}(\xi_{k,n,t}|s)$, the $s$-th elements of the individual belief
vectors $\mu_{k,n}$ are updated as follows:

  1. 1.

Repeat (1) and (1) for $t=0,1,...,T$, $\forall s\in\mathcal{S}$ and $\forall
k\in\mathcal{K}$:

Adapt: $\displaystyle\psi_{k,t}(s)=\frac{L_{k}\left({\xi}_{k,t}^{n}\mid
s\right){\widetilde{\mu}}_{k,t-1}(s)}{\sum_{s^{\prime}\in\mathcal{S}}L_{k}\left(\xi_{k,t}^{n}\mid
s^{\prime}\right)\widetilde{\mu}_{k,t-1}\left(s^{\prime}\right)}$ (10)
Combine:
$\displaystyle\widetilde{\mu}_{k,t}(s)=\frac{\prod_{\ell\in\mathcal{N}_{k}}\left[{\psi}_{\ell,t}(s)\right]^{c_{\ell
k}}}{\sum_{s^{\prime}\in\Theta}\prod_{\ell\in\mathcal{N}_{k}}\left[{\psi}_{\ell,t}(s)\right]^{c_{\ell
k}}}$ (11)

  2. 2.

Assign:

$\displaystyle\mu_{k,n}=\widetilde{\mu}_{k,T}$ (12)

where $c_{\ell,k}$ are the entries of a combination matrix $C$ satisfying
Assumption 1. Actor-critic learning requires knowledge of the current and next
states. Therefore, we also introduce the belief vector $\eta_{k,n}$ the $i$-th
element corresponds to the probability that the next state is $i$. Similar to
updating $\mu_{k,n}$, the next state belief vectors $\eta_{k,n}$ are updated
as follows:

  1. 1.

Repeat (13) and (14) for $t=0,1,...,T$, $\forall s\in\mathcal{S}$ and $\forall
k\in\mathcal{K}$ :
Adapt:

$\displaystyle\psi_{k,t}(s)$
$\displaystyle=\frac{L_{k}\left({\xi}_{k,t}^{n+1}\mid
s\right){\widetilde{\mu}}_{k,t-1}(s)}{\sum\limits_{s^{\prime}\in\mathcal{S}}L_{k}\left(\xi_{k,t}^{n+1}\mid
s^{\prime}\right)\widetilde{\eta}_{k,t-1}\left(s^{\prime}\right)}$ (13)

Combine:

$\displaystyle\widetilde{\eta}_{k,t}(s)$
$\displaystyle=\frac{\prod_{\ell\in\mathcal{N}_{k}}\left[{\psi}_{\ell,t}(s)\right]^{c_{\ell
k}}}{\sum\limits_{s^{\prime}\in\Theta}\prod_{\ell\in\mathcal{N}_{k}}\left[{\psi}_{\ell,t}(s)\right]^{c_{\ell
k}}}$ (14)

  2. 2.

Assign:

$\displaystyle\eta_{k,n}=\widetilde{\eta}_{k,T}$ (15)

Actually, agents are required to estimate both $\mu_{k,n}$ and $\eta_{k,n}$
only during the initial iteration, i.e., for $n=0$. In subsequent iterations,
the next state from the previous iteration is utilized as the current state in
the new iteration, i.e.,

$\displaystyle\mu_{k,n}=\eta_{k,n-1}$ (16)

######  Assumption 1 (Combination matrix).

The combination matrix $C$ assigns non-negative weights to neighboring agents
and is assumed to be doubly-stochastic, i.e., the entries on its columns and
rows sums to $1$:

$\displaystyle\sum\limits_{\ell=1}^{K}c_{\ell,k}$
$\displaystyle=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,k}=1;$ (17)
$\displaystyle\sum\limits_{\ell=1}^{K}c_{k,\ell}$
$\displaystyle=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}=1$ (18)

where the notation ${\cal N}_{k}$ denotes the neighbors of agent $k$.

$\blacksquare$

As demonstrated in [12], under Assumptions 1-3, repeated application of the
updates in (1) and (1) allows agents to almost surely learn the true current
state $s_{n}$:

$\displaystyle\mu_{k,n}\left(s_{n}\right)\stackrel{{\scriptstyle\text{ a.s.
}}}{{\longrightarrow}}1\text{. }$ (19)

The convergence rate of the algorithm is discussed in [11]. Generally, the
belief vectors converge at an exponential rate, which depends on the second-
largest-magnitude eigenvalue of $C$ [13]. Therefore, in Section V, we analyze
the maximum allowable state estimation error to ensure that, by the end of the
MARL run, the estimation of the policy parameter $\theta_{k,n}$ is
$\varepsilon$-optimal. Using the maximum allowed state estimation error, we
can adjust the run time of the inner loop, i.e., the number of iterations in
the state estimation loop.

######  Assumption 2 (Strong connectivity).

The underlying graph topology is assumed to be strongly connected, i.e, there
exists a path with positive combination weights between any two agents in the
network and, moreover, at least one agent $k_{o}$ has a nonzero self loop,
$c_{k_{o}k_{o}}>0$.

$\blacksquare$

######  Assumption 3 (Likelihood function).

For all agents $k\in\mathcal{K}$ and all states $s\in\mathcal{S}$, KL-
divergence between the true model $f_{k}(\xi_{k})$ and the likelihood function
$L_{k}(\xi_{k}|s)$ is finite:

$\displaystyle\operatorname{D}_{k}\left(f\mid\mid
L_{k}\right)\triangleq\mathbb{E}_{f_{k}}\log\frac{f_{k}(\xi)}{L_{k}(\xi\mid
s)}<\infty$ (20)

$\blacksquare$

Initialize parameters: $\lambda\in(0,1)$, $\zeta\in(0,1)$, $\gamma\in(0,1)$,
$\omega_{k,0}(s,a)$, $\rho_{k,0}$,
$\widetilde{\mu}_{k,0}=\frac{1}{S}$,$\eta_{k,0}=\frac{1}{S}$ , $F_{k,0}=0$;

for  _n=0,1,2…._ do

if  _n=0_ then

Each agent $k$ receives observations
$\\{\boldsymbol{\xi}_{k,t}^{0}\\}_{t=0}^{T}$ ;

Each agent $k$ estimates $\mu_{k,0}$ using (1)-(12);

end if

Each agent $k$ takes action $a_{k,n}\sim b_{k}\left(a\|\mu_{k,n}\right)$;

Each agent $k$ receives reward $r_{k,n}$ ;

Each agent $k$ receives observations $\\{\xi_{k,t}^{n+1}\\}_{t=0}^{T}$;

Each agent $k$ estimates $\eta_{k,n}$ using (13)-(15);

Each agent $k$ estimates $\rho_{k,n}$ using (30)-(32);

for  _each agent $k$_ do

$\displaystyle F_{k,n}=1+\gamma\rho_{k,n-1}F_{k,n-1}$ (21) $\displaystyle
M_{k,n}=\lambda+(1-\lambda)F_{k,n}$ (22) $\displaystyle e_{k,n}=\gamma\lambda
e_{k,n-1}+M_{k,n}\mu_{k,n}$ (23) $\displaystyle
M_{k,n}^{\theta}=1+\zeta\gamma\rho_{k,n-1}F_{k,n-1}$ (24)
$\displaystyle\delta_{k,n}=r_{k,n}+\gamma{\omega_{k,n}^{T}}\eta_{k,n}-{\omega_{k,n}^{T}}\mu_{k,n}$
(25)
$\displaystyle\Psi_{k,n}=\frac{\nabla_{\theta}\pi\left(a_{k,n}\mid\mu_{k,n}\right)}{\pi\left(a_{k,n}\mid\mu_{k,n}\right)}$
(26)
$\displaystyle\widetilde{\omega}_{k,n}=\omega_{k,n}+\beta_{n}\rho_{k,n}\delta_{k,n}e_{k,n}$
(27)
$\displaystyle\theta_{k,n+1}=\theta_{k,n}+\beta_{n}\rho_{k,n}M_{k,n}^{\theta}\delta_{k,n}\Psi_{k,n}$
(28)

end for

for  _each agent $k$ _ do

$\omega_{k,n+1}=\sum_{\ell\in\mathcal{N}_{k}}c_{\ell,k}\widetilde{\omega}_{\ell,n}$
(29)

end for

Assign: $\mu_{k,n}=\eta_{k,n}$;

Reset: $\widetilde{\eta}_{k,0}(s)=\frac{1}{S}$ ;

end for

Algorithm 1 MAOPAC-dec-POMDP

###  IV-C Importance sampling ratio

The importance sampling ratio is crucial for correcting off-policy algorithms.
Similar to state estimation, the importance sampling ratio also needs to be
learned in a distributed manner because each agent, due to privacy concerns,
is only aware of its own behavioral and estimated target policies.
Specifically, we introduce the variable $p_{k,n}$ to denote log importance
ratios:

$p_{k,n}\triangleq\log\frac{\pi_{k,n}\left(a|\mu_{k,n}\right)}{b_{k}\left(a|\mu_{k,n}\right)}$
(30)

Next, for $t=0,1,...T_{\rho}$, agents diffuse $p_{k,n}$ as follows:

$\begin{gathered}\widetilde{p}_{k,t}\propto\sum_{\ell\in\mathcal{N}_{k}}c_{\ell
k}\widetilde{p}_{\ell,t}\end{gathered}$ (31)

where $\widetilde{p}_{k,0}=p_{k,n}$. After $T_{\rho}-$iterations, the improved
importance sampling ratios $\rho_{k,n}$ are retrieved as:

$\displaystyle\rho_{k,n}=\exp\left(N_{k}\widetilde{p}_{k,T_{\rho}}\right)$
(32)

For simplicity of analysis, at this stage of the study, we assume that
$T_{\rho}$ is large enough to approximate the individual estimate $\rho_{k,n}$
with the global importance sampling ratio, i.e.,

$\displaystyle\rho_{k,n}\approx\prod\limits_{k^{\prime}\in
K}\frac{\pi(a_{k^{\prime},n}|\mu_{k^{\prime},n};\theta_{k^{\prime},n})}{b_{k^{\prime}}}$
(33)

To align with the original algorithm [5], we introduce Assumption 4 related to
behavior policies, which leads to the following constraint:

$\displaystyle\rho_{n}\leq\frac{1}{b_{{\epsilon}}}$ (34)

######  Assumption 4 (Behavioral policies).

The joint behavioral policy is time-invariant and nonzero, i.e., $b_{n}\geq
b_{\epsilon}>0$. Additionally, for analysis, we require that
$b_{\epsilon}>\gamma$.

$\blacksquare$

The discount factor $\gamma$ is commonly chosen in the range of $0.8-0.9$.
Therefore, Assumption 4 requires that the probability of the chosen action at
time $n$ considerably dominates over other possible actions. A good example is
a deterministic policy where one action whose probability (namely $1$)
considerably dominates over the probabilities of other actions (zeros). The
learning rate at time $n$, denoted by $\beta_{n}$, follows Assumption 5.

######  Assumption 5 (Learning rate).

The learning step size $\beta_{n}$ satisfies

$\displaystyle\sum\limits_{n=0}^{\infty}\beta_{n}=\infty,\quad\quad\sum\limits_{n=0}^{\infty}\beta_{n}^{2}<\infty$
(35)

$\blacksquare$

##  V Theoretical guarantees

For analysis we compare the performance of MAOPAC when the global state is
fully observed against when it is only partially observed. In essence, we
compare the original algorithm MAOPAC and the proposed MAOPAC-dec-POMDP. Let
$\widehat{\mu}_{k,n}$, $\widehat{\rho}_{k,n}$, $\widehat{\omega}_{k,n}$,
$\widehat{\theta}_{k,n}$, $\widehat{F}_{k,n}$, $\widehat{M}_{k,n}$,
$\widehat{e}_{k,n}$, $\widehat{\delta}_{k,n}$, and
$\widehat{M}^{\theta}_{k,n}$ denote the full-observation counterparts of
$\mu_{k,n}$, $\rho_{k,n}$, $\omega_{k,n}$, ${\theta}_{k,n}$, ${F}_{k,n}$,
${M}_{k,n}$, ${e}_{k,n}$, ${\delta}_{k,n}$, and ${M}^{\theta}_{k,n}$,
respectively. These variables undergo the same update processes as their
counterparts, with the distinction that they are privileged with knowledge of
the true global state. For comparison between these two sets we introduce the
error variables

$\displaystyle\Delta\mu_{k,n}\triangleq\widehat{\mu}_{k,n}-\mu_{k,n},\
\Delta\rho_{k,n}\triangleq\widehat{\rho}_{k,n}-\rho_{k,n},$ (36)
$\displaystyle\Delta\omega_{k,n}\triangleq\widehat{\omega}_{k,n}-\omega_{k,n},\
\Delta\theta_{k,n}\triangleq\widehat{\theta}_{k,n}-\theta_{k,n},$ (37)
$\displaystyle\Delta F_{k,n}\triangleq\widehat{F}_{k,n}-F_{k,n},\
\Delta\widehat{\delta}_{k,n}\triangleq\widehat{\delta}_{k,n}-\delta_{k,n}$
(38) $\displaystyle\Delta e_{k,n}\triangleq\widehat{e}_{k,n}-e_{k,n},\ \Delta
M_{k,n}\triangleq\widehat{M}_{k,n}-M_{k,n}$ (39) $\displaystyle\Delta
M_{k,n}^{\theta}\triangleq\widehat{M}_{k,n}^{\theta}-M_{k,n}^{\theta}$ (40)

Additionally, in the analysis of the proposed method, we must employ the
following upper bounds:

$\displaystyle|M^{\theta}_{k,n}|\leq\frac{1-(1-\zeta)\gamma/b_{\epsilon}}{1-\gamma/b_{\epsilon}}\triangleq
B_{M}^{\theta}$ (41)
$\displaystyle\|\omega_{k,n}\|\leq\sum\limits_{i=0}^{n-1}\frac{\beta_{i}\Omega^{n-i}R_{\max}B_{e}\|\omega_{0,\max}\|}{b_{\epsilon}}\triangleq
B_{n}^{\omega}$ (42) $\displaystyle|\delta_{k,n}|\leq
R_{\max}+(1+\gamma)B^{\omega}_{n}\triangleq B_{n}^{\delta}$ (43)
$\displaystyle\|e_{k,n}\|\leq\frac{1}{1-\lambda\gamma}\left(\lambda+\frac{1-\lambda}{1-\gamma/b_{\epsilon}}\right)\triangleq
B_{e}$ (44)

These bounds are derived in the appendix (Lemma 1 \- 4).

The primary objective of the MAOPAC algorithm is to find the policy parameter
$\widetilde{\theta}_{k,n}$ that maximizes the average cumulative reward across
the network. The convergence of MAOPAC to the optimal solution has been
established in [5]. In our analysis, we determine conditions under which the
actor parameter under partial observability, $\theta_{k,n}$, can get
$\varepsilon$-close to the optimal result of MAOPAC. This finding is formally
stated in Theorem 1, whose proof appears in the appendix.

######  Theorem 1 ($\boldsymbol{\epsilon}$-optimality).

Let $\|\cdot\|$ denote the Euclidean norm ($2-$norm) of a vector. Then, under
Assumptions 1-5, for all agents $k$, $\Delta\theta_{k,n}$ is
$\varepsilon$-bounded at time $n$ if $\forall j\leq n$:

$\displaystyle\|\Delta\mu_{\ell,j})\|\leq\min(\widetilde{B}_{1},\widetilde{B}_{2})\text{
and }$ (45)
$\displaystyle\|\Delta\rho_{\ell,j}\|\leq\min(\widetilde{D}_{1},\widetilde{D}_{2},\widetilde{D}_{3})$
(46)

where

$\displaystyle\widetilde{B}_{1}$ $\displaystyle\triangleq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-1}B_{e}^{-1}}{\Phi_{n}\beta_{j}B^{\omega}_{j}\Omega^{n-j}},$
(47) $\displaystyle\widetilde{B}_{2}$
$\displaystyle\triangleq\frac{\varepsilon\beta_{0}^{-1}I_{1}^{-1}}{2\Phi_{n}|M_{k,j}|B_{n}^{\delta}\Omega^{n-I_{1}}(\gamma\lambda)^{I_{1}-j}}$
(48) $\displaystyle\widetilde{D}_{1}$
$\displaystyle\triangleq\frac{\varepsilon
b_{\epsilon}B_{e}^{-1}}{\Phi_{n}\beta_{j}B_{j}^{\delta}\Omega^{n-j}}$ (49)
$\displaystyle\widetilde{D}_{2}$
$\displaystyle\triangleq\left(\frac{b_{\epsilon}}{\gamma}\right)^{I_{2}-j}\frac{\varepsilon
I_{2}^{-2}(1-\lambda)^{-1}\beta_{0}^{-1}}{2\Phi_{n}F_{k,j}B_{n}^{\delta}\Omega^{n-I_{2}}}$
(50) $\displaystyle\widetilde{D}_{3}$
$\displaystyle\triangleq\left(\frac{b_{\epsilon}}{\gamma}\right)^{I_{3}-j}\frac{3\varepsilon
b_{\epsilon}I_{3}^{-2}\zeta^{-1}}{8\beta_{n}\pi^{2}B^{\delta}_{n}F_{k,j}}$
(51) $\displaystyle I_{1}$
$\displaystyle\triangleq\left[\ln\frac{\Omega}{\gamma\lambda}\right]^{-1},\quad
I_{2}\triangleq 2\left[\ln\frac{b_{\epsilon}\Omega}{\gamma}\right]^{-1},$ (52)
$\displaystyle I_{3}$ $\displaystyle\triangleq
2\left[\ln\frac{b_{\epsilon}}{\gamma}\right]^{-1},\quad\Omega\triangleq
1+\frac{\beta_{0}(1+\gamma)B_{e}}{b_{\epsilon}}$ (53) $\displaystyle\Phi_{n}$
$\displaystyle\triangleq 4\beta_{0}(1+\gamma)\pi^{2}B^{\theta}_{M}n^{3},$ (54)

$\blacksquare$

(a) Initial state

(b) Parameter exchanges

(c) Action selection

(d) State transition

Figure 2: Illustration of the agents/target framework: (a) depicts the initial
state, corresponding to the position of a target (green) and the fixed
positions of agents (blue); (b) shows a phase where agents exchange parameters
according to the communication graph: black arrows demonstrate communication
links; (c) illustrates a phase where agents, based on their individual
policies, choose an action, i.e., select the possible location of the target
(cells indicated by the orange arrows); (d) demonstrates the transition of the
target to another state (cell) as a result of the agents’ actions.

Note that over infinite time, $n\to\infty$, the bounds in (45) and (46)
converge to zero, which is a reasonable outcome. State estimation occurs at
every iteration of the actor-critic updates. As a result, each new state
estimation error $\Delta\mu_{k,n}$ contributes to the overall error of the
actor parameter $\Delta\theta_{k,n}$. Therefore, the convergence of the actor
error $\Delta\theta_{k,n}$ necessitates the convergence of $\Delta\mu_{k,n}$
to zero as $n$ approaches infinity. Next, note that the bounds in (45) and
(46) can be computed in real time, highlighting the practical importance of
these bounds. Specifically, an agent undergoing an actor-critic update at time
$j$ needs to determine the maximum allowable state estimation error and use it
to adjust the runtime of the inner state-estimation loop. For this purpose,
they can refer to the bounds in (45) and (46), which require only the current
time $j$ variables and constants, without the need to retain the history of
previous updates.

In addition, we derive Corollary 1 which extends Theorem 1 for a specific
target policy model. We assume the target and behavioral policies follow
Boltzmann distributions parametrized by vectors $\\{\theta_{c,n}\\}_{\forall
c\in\mathcal{A}}$ and $\\{\bar{\theta}_{c,n}\\}_{\forall c\in\mathcal{A}}$,
respectively:

$\displaystyle\pi_{k,n}(a\|\mu_{k,n})$
$\displaystyle=\frac{\exp[\mu_{k,n}^{T}\theta_{a,n}]}{\sum\limits_{c\in\mathcal{A}}\exp[\mu_{k,n}^{T}\theta_{c,n}]}$
(55) $\displaystyle\quad b_{k,n}(a\|\mu_{k,n})$
$\displaystyle=\frac{\exp[\mu_{k,n}^{T}\bar{\theta}_{a,n}]}{\sum\limits_{c\in\mathcal{A}}\exp[\mu_{k,n}^{T}\bar{\theta}_{c,n}]}$
(56)

######  Corollary 1 (Boltzman distributions).

Let the behavioral and target policies be defined according to (55). Then, for
all agents $k\in\mathcal{K}$, the actor parameter estimation error
$\Delta\theta_{k,n}$ is $\varepsilon$-bounded if the state estimation error
$\Delta\mu_{k,n}$ is bounded as

$\displaystyle\|\Delta\mu_{k,n}^{T}\|\leq\min(\widetilde{B}_{1},\widetilde{B}_{2},\widetilde{B}_{3})$
(57)

where $\widetilde{B}_{1}$ and $\widetilde{B}_{2}$ are defined in (47) and
(48), respectively, and

$\displaystyle\widetilde{B}_{3}\triangleq\frac{1}{\|\Theta\|}\ln\left[\frac{\min(\widetilde{D}_{1},\widetilde{D}_{2},\widetilde{D}_{3})+\rho_{k,n}(a)}{\exp[\mu_{k,n}^{T}\Theta]}\right]$
(58)
$\displaystyle\Theta\triangleq\theta_{a}-\bar{\theta}_{a}+\bar{\theta}_{\max}-\theta_{\min}$
(59)
$\displaystyle\theta_{\min}\triangleq\min\limits_{c\in\mathcal{A}}\theta_{c},\quad\bar{\theta}_{\max}\triangleq\max\limits_{c\in\mathcal{A}}\bar{\theta}_{c}$
(60)

$\blacksquare$

The Boltzmann distribution is a common choice for modeling policies in
reinforcement learning. In fact, the impact of the particular policy model is
confined to the concluding steps of the proof for Theorem 1. Consequently, it
is reasonable to conjecture that replicating such an analysis for alternative
distributions would entail minimal additional effort.

It is important to highlight that the behavioral policy in the proposed scheme
is assumed to be time-invariant. While this assumption holds in many cases, it
could pose challenges for certain specially designed behavioral policies. For
instance, in [34], the behavioral policy is crafted to ensure sufficient
exploration of the state space, which may require time-varying characteristics
for optimal performance. Therefore, future study may include a version with
time-variant behavioral policies.

(a) Critic error

(b) Actor error

(c) Critic agreement

(d) MAOPAC-dec-POMDP vs ZOPO

Figure 3: Comparison between MAOPAC and the proposed MAOPAC-dec-POMDP: (a)
shows the difference in critic values computed by MAOPAC and MAOPAC-dec-POMDP
for different numbers of agents: $K=3,K=5$ and $K=7$; (b) shows the difference
in actor values computed by MAOPAC and MAOPAC-dec-POMDP for different numbers
of agents: $K=5,K=7$ and $K=9$ (c) shows the network agreement for different
numbers of agents: $K=3,K=5$ and $K=7$; (d) compares the proposed MAOPAC-dec-
POMDP and ZOPO in terms of cumulative average reward

##  VI Experimental results and Discussions

For experiments we use the grid-based scenario from [35]. It involves $K$
agents (representing radars) with fixed location and one object with changing
location over $h\times h$ grid (see Figure 2). The states of the underlying
POMDP are the cells of the grid. The objective for all agents is to correctly
detect the location of the moving object (i.e., the cell where it is present).
Hence, actions of the POMDP are also cells of the grid. The actions by agents
correspond to which cell in the grid to hit. Agents are rewarded based on the
accuracy of their selections relative the actual location of the object.
Furthermore, the object tries to move away from the most recent hit locations.
In this way, the transition between states is dependent on the actions chosen
by agents.

Figure 3(a) and Figure 3(b) illustrate the absolute difference in estimating
the critic and actor parameters between two scenarios: one where the global
state is only partially observed (MAOPAC-dec-POMDP), and the other where it is
fully observed (MAOPAC). As depicted in these figures, both critic and actor
values for MAOPAC-POMDP closely align with that of MAOPAC. Convergence of
MAOPAC to the optimal policy under full observability has been proven in [5].
Hence, it follows that MAOPAC-POMDP can attain an $\varepsilon$-optimal
solution.

While each agent possesses its own actor parameter $\theta_{k,n}$, the
introduction of the critic parameter $\omega_{k,n}$ serves to model global
state values. Consequently, it is imperative that the critic variables
$\\{\omega_{k,n}\\}_{k=1}^{K}$ across all agents agree with each other. This
requirement is substantiated by Figure 3(c), which depicts the difference
(averaged across all agents) between individual critic parameters
$\omega_{k,n}$ and the network average:

$\displaystyle\bar{\omega}\triangleq\frac{1}{K}\sum_{k=1}^{K}\omega_{k,n}.$
(61)

###  VI-A Comparision between MAOPAC-dec-POMDP and ZOPO

ZOPO (Zeroth-Order Policy Optimization) is an extension of Monte-Carlo-based
policy gradient approaches such as the REINFORCE algorithm. ZOPO does not
require knowledge of the actual gradient of the objective function (expected
reward). Instead, ZOPO approximates it using samples of the objective function
under perturbed parameters.

ZOPO is inherently simple to implement and can be useful when the gradient of
a function is not available. However, it tends to exhibit slow convergence and
high noise levels, as confirmed in Figure 3(d). As previously mentioned, ZOPO
relies on samples of the expected reward to compute estimates, necessitating
multi-step sampling for each new update of the policy parameters.

In contrast, the proposed MAOPAC-dec-POMDP (Multi-Agent Off-Policy Actor-
Critic with Partial Observability) does not require such extensive sampling
but instead relies on an internal loop for state estimation. Therefore, both
algorithms have similar levels of complexity.

Moreover, MAOPAC-dec-POMDP can operate off-policy, which is generally more
advantageous than on-policy solutions. Off-policy methods are more practical,
easier to implement, and broaden the range of potential applications.

##  VII Conclusion

This paper proposes a multi-agent off-policy actor-critic algorithm for
partially observable environments. The key innovation lies in estimating the
global state through social learning to guarantee $b_{\epsilon}-$boundedness
of estimation error. The performance of the resulting algorithm is illustrated
by comparing against state-of-the-art solutions. Currently, the algorithm’s
implementation necessitates a two-time scale learning approach. Future
extensions would focus on streamlining the learning process into a single
time-scale. Additionally, extending the algorithm to accommodate time-variant
behavioral policies opens doors to diverse applications, notably in
exploration problems.

## Acknowledgment

##  Appendix A Proof of Theorem 1

###  A-A Bounds of intermediate variables

######  Lemma 1.

$M_{k,n}$ can be upper-bounded by $B_{M}$ defined as

$\displaystyle
B_{M}\triangleq\lambda+\frac{(1-\lambda)}{1-\gamma/b_{\epsilon}}$ (62)

$\blacksquare$

###### Proof.

From (21) we get

$\displaystyle
F_{k,n}=\sum\limits_{i=0}^{n}\prod_{j=i+1}^{n}\gamma\rho_{i}\stackrel{{\scriptstyle\text{
(a)
}}}{{\leq}}\sum\limits_{i=0}^{n}\prod_{j=i+1}^{n}\frac{\gamma}{b_{\epsilon}}=\frac{1}{1-\frac{\gamma}{b_{\epsilon}}}$
(63)

where in (a) we assumed $\rho_{n}\leq\frac{1}{b_{\epsilon}}$ and (b) is valid
because $\frac{\gamma}{b_{\epsilon}}\leq 1$ by Assumption 4. Therefore, using
the definition of $M_{k,n}$ in (22), we can get the following bound

$\displaystyle
M_{k,n}\leq\lambda+\frac{(1-\lambda)}{1-\gamma/b_{\epsilon}}\triangleq B_{M}$
(64)

∎

######  Lemma 2.

$\|\widehat{e}_{k,n}\|$ and $\|e_{k,n}\|$ can be upper-bounded by $B_{e}$
defined as

$\displaystyle
B_{e}\triangleq\frac{1}{1-\lambda\gamma}\left(\lambda+\frac{1-\lambda}{1-\gamma/b_{\epsilon}}\right)$
(65)

$\blacksquare$

###### Proof.

From the update rule for $e_{k,n}$

$\displaystyle
e_{k,n}=\sum\limits_{i=0}^{n-1}(\gamma\lambda)^{n-1-i}M_{i}\mu_{k,i}$ (66)

Therefore, $\|e_{k,n}\|$ can be bounded as

$\displaystyle\|e_{k,n}\|$
$\displaystyle\leq\sum\limits_{i=0}^{n-1}(\gamma\lambda)^{n-1-i}|M_{k,i}|\|\mu_{k,i}\|$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\sum\limits_{i=0}^{n-1}(\gamma\lambda)^{n-1-i}B_{M}\leq\sum\limits_{i=0}^{\infty}(\gamma\lambda)^{n-1-i}B_{M}$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{=}}\frac{1}{1-\lambda\gamma}\left(\lambda+\frac{1-\lambda}{1-\gamma/b_{\epsilon}}\right)\triangleq
B_{e}$ (67)

where (a) is valid due to $\|\mu_{k,n}\|\leq 1$ and Lemma 1 and (b) is valid
if we choose $\lambda\gamma\leq 1$. Similarly, we can show that

$\displaystyle\|\widehat{e}_{k,n}\|\leq B_{e}$ (68)

∎

######  Lemma 3.

$M^{\theta}_{k,i}$ can be upper-bounded by $B_{M}^{\theta}$ defined as

$\displaystyle
B_{M}^{\theta}\triangleq\frac{1-(1-\zeta)\gamma/b_{\epsilon}}{1-\gamma/b_{\epsilon}}$
(69)

$\blacksquare$

###### Proof.

We start from the update rule of $M^{\theta}_{k,i}$

$\displaystyle M_{k,n}^{\theta}=1+\lambda_{\theta}\gamma\rho_{k,n-1}F_{k,n-1}$
(70)

$F_{k,n}$ can be upper-bounded by

$\displaystyle F_{k,n}$
$\displaystyle=1+\gamma\rho_{n-1}F_{k,n-1}=\sum\limits_{i=0}^{n-1}\prod_{j=i+1}^{n-1}(\gamma\rho_{j})F_{k,0}$
$\displaystyle\stackrel{{\scriptstyle\text{ (a)
}}}{{\leq}}\sum\limits_{i=0}^{n-1}\left(\frac{\gamma}{b_{\epsilon}}\right)^{n-i-1}\leq\sum\limits_{i=0}^{\infty}\left(\frac{\gamma}{b_{\epsilon}}\right)^{i}\stackrel{{\scriptstyle\text{
(b) }}}{{=}}\frac{1}{1-\gamma/b_{\epsilon}}$ (71)

where in (a) we use $\rho_{n}\leq\frac{1}{b_{\epsilon}}$ and $F_{k,0}=1$,
$\forall k\in\mathcal{K}$, and (b) is valid due to Assumption 4.

Using (A-A) and the property $\rho_{n}\leq\frac{1}{b_{\epsilon}}$,
$M_{k,n}^{\theta}$ can be upper-bounded by

$\displaystyle M_{k,n}^{\theta}\leq
1+\frac{\zeta\gamma/b_{\epsilon}}{1-\gamma/b_{\epsilon}}=\frac{1-(1-\zeta)\gamma/b_{\epsilon}}{1-\gamma/b_{\epsilon}}\triangleq
B_{M}^{\theta}$ (72)

Similarly, we can show that

$\displaystyle\widehat{M}_{k,n}^{\theta}\leq B_{M}^{\theta}$ (73)

∎

######  Lemma 4.

For all agents $k\in\mathcal{K}$, $\|\omega_{k,n}\|$ and
$\|\widehat{\omega}_{k,n}\|$ can be upper-bounded by $B_{n}^{\omega}$ defined
as

$\displaystyle
B_{n}^{\omega}\triangleq\sum\limits_{i=0}^{n-1}\Omega^{n-i}\frac{\beta_{i}R_{\max}B_{e}\|\omega_{0,\max}\|}{b_{\epsilon}}$
(74)

$\blacksquare$

###### Proof.

We start from the update for $\omega_{k,n}$ :

$\displaystyle\omega_{k,n}=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\omega_{\ell,n-1}+\beta_{n}\rho_{\ell,n}\delta_{\ell,n}e_{\ell,n}\right)$
(75)

Using the definition of $\delta_{\ell,n}$ and the reward upper-bound
$r_{\ell,n}\leq R_{\max}$, we can upper-bound $\omega_{k,n}$ as

$\displaystyle\|\omega_{k,n}\|$
$\displaystyle\leq\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\|\omega_{\ell,n-1}\|\right.$
$\displaystyle+\|(\gamma\eta_{k,n}-\mu_{k,n})\beta_{n}\rho_{\ell,n}e_{\ell,n}\|\|\omega_{\ell,n-1}\|$
$\displaystyle\left.+\beta_{n}\rho_{\ell,n}R_{\max}|e_{\ell,n}|\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\left(1+(1+\gamma)\frac{\beta_{0}B_{e}}{b_{\epsilon}}\right)\|\omega_{\ell,n-1}\|\right.$
$\displaystyle\left.+\beta_{n}\frac{\beta_{n}R_{\max}B_{e}}{b_{\epsilon}}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{\leq}}\sum\limits_{i=0}^{n-1}\Omega^{n-i}\frac{\beta_{i}R_{\max}B_{e}\|\omega_{0,\max}\|}{b_{\epsilon}}\triangleq
B^{\omega}_{n}$ (76)

where $\|\omega_{\max}\|=\max\limits_{k\in\mathcal{K}}\|\omega_{k,0}\|$, (a)
is valid due to the assumption $\beta_{0}\geq\beta_{n}$ and $\|\mu_{k,n}\|\leq
1$, $\forall n\geq 0$ and (b) is obtained by iteratively applying inequality
(a) and using the definition of $\Omega$. Similarly, we can show that

$\displaystyle\|\widehat{\omega}_{k,n}\|\leq B^{\omega}_{n}$ (77)

∎

######  Lemma 5.

For all agents $k\in\mathcal{K}$, $\|\delta_{k,n}\|$ and
$\|\widehat{\delta}_{k,n}\|$ are upperbounded by $B_{n}^{\delta}$ defined as

$\displaystyle B_{n}^{\delta}\triangleq R_{\max}+(1+\gamma)B^{\omega}_{n}$
(78)

where $B^{\omega}_{n}$ is given in (74).

$\blacksquare$

###### Proof.

We start from the definition of $\delta_{k,n}$

$\displaystyle\delta_{k,n}$
$\displaystyle=r_{k,n}+(\gamma\eta_{k,n}-\mu_{k,n})^{T}\omega_{k,n}$
$\displaystyle\stackrel{{\scriptstyle\text{(a)
}}}{{\leq}}R_{\max}+(1+\gamma)\|\omega_{k,n}\|$
$\displaystyle\stackrel{{\scriptstyle\text{(b)}}}{{\leq}}R_{\max}+(1+\gamma)B_{n}^{\omega}$
(79)

where (a) is due to the assumption $\|\mu_{k,n}\|\leq 1$ and (b) is due to
Lemma 4. Similarly, we can show that

$\displaystyle\widehat{\delta}_{k,n}\leq B_{n}^{\delta}$ (80)

∎

######  Lemma 6.

$\Delta e_{\ell,i}$ can be bounded as

$\displaystyle\|\Delta e_{\ell,i}\|\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}(1+\gamma)}{\beta_{n}\beta_{i}B_{i}^{\delta}\Omega^{n-i}\Phi_{n}}$
(81)

if for all $j\leq i$

$\displaystyle\|\Delta\mu_{k,j}\|$ $\displaystyle\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}(1+\gamma)}{2\beta_{n}(\gamma\lambda)^{i-j}i|M_{k,j}|\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(82) $\displaystyle\Delta\rho_{k,j}$
$\displaystyle\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{i-j}\frac{\varepsilon
b_{\epsilon}\beta_{0}(1-\lambda)^{-1}(1+\gamma)}{2\beta_{n}F_{k,j}i^{2}\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(83)

$\blacksquare$

###### Proof.

We start by extending the definition of $\Delta e_{k,i}$:

$\displaystyle\Delta e_{k,i}$ $\displaystyle=\gamma\lambda\Delta
e_{k,i-1}+\widehat{M}_{k,i}\widehat{\mu}_{k,i}-M_{k,i}\mu_{k,i}$
$\displaystyle=\gamma\lambda\Delta e_{k,i-1}+\Delta
M_{k,n}\widehat{\mu}_{k,i}+M_{k,i}\Delta\mu_{k,i}$
$\displaystyle=\sum_{j=0}^{i}(\gamma\lambda)^{i-j}(\Delta
M_{k,j}\widehat{\mu}_{k,j}+M_{k,j}\Delta\mu_{k,j})$ (84)

Next, we impose the following constraints $\forall j\leq i$:

$\displaystyle\|\Delta M_{k,j}\|$ $\displaystyle\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}(1+\gamma)}{2\beta_{n}(\gamma\lambda)^{i-j}i\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(85) $\displaystyle\|\Delta\mu_{k,j}\|$ $\displaystyle\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}(1+\gamma)}{2\beta_{n}(\gamma\lambda)^{i-j}iM_{k,j}\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(86)

By definition $\Delta M_{k,j}=(1-\lambda)\Delta F_{k,j}$. We can extend
$\Delta F_{k,j}$ as

$\displaystyle\Delta F_{k,j}$
$\displaystyle=\gamma(\widehat{\rho}_{k,j-1}\widehat{F}_{k,j-1}-\rho_{k,j-1}F_{k,j-1})$
$\displaystyle=\gamma(\widehat{\rho}_{k,j-1}\Delta
F_{k,j-1}+\Delta\rho_{k,j-1}F_{k,j-1})$
$\displaystyle=\sum\limits_{t=0}^{j-1}\prod_{z=t+1}^{j-1}(\gamma\rho_{k,z})\gamma\Delta\rho_{k,t}F_{k,t}$
$\displaystyle\leq\sum\limits_{t=0}^{j-1}\left(\frac{\gamma}{b_{\epsilon}}\right)^{j-t-1}\gamma\Delta\rho_{k,t}F_{k,t}$
(87)

where the last inequality is due to $\rho_{k,t}\leq\frac{1}{b_{\epsilon}}$.
Therefore,

$\displaystyle\Delta M_{k,j}$
$\displaystyle=(1-\lambda)\sum\limits_{t=0}^{j-1}\left(\frac{\gamma}{b_{\epsilon}}\right)^{j-t-1}\gamma\Delta\rho_{k,t}F_{k,t}$
$\displaystyle\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}(1+\gamma)}{2\beta_{n}(\gamma\lambda)^{i-j}i\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(88)
$\displaystyle\Delta\rho_{k,t}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{j-t}\frac{\varepsilon
b_{\epsilon}\beta_{0}(1+\gamma)(1-\lambda)^{-1}}{2\beta_{n}F_{k,t}j(\gamma\lambda)^{i-j}i\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(89)

The upper-bound in (89) is minimized if $j=i$. Therefore, the condition can be
generalized $\forall t\leq i$:

$\displaystyle\Delta\rho_{k,t}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{i-t}\frac{\varepsilon
b_{\epsilon}(1+\gamma)\beta_{0}(1-\lambda)^{-1}}{2\beta_{n}F_{k,t}i^{2}\beta_{i}B^{\delta}_{i}\Omega^{n-i}\Phi_{n}}$
(90)

∎

######  Lemma 7.

For all $k\in\mathcal{K}$, the critic error $\Delta\omega_{k,i}$ can be upper-
bounded by

$\displaystyle\Delta\omega_{k,i}\leq\frac{3b_{\epsilon}\varepsilon}{4\beta_{i}(1+\gamma)i^{2}\pi^{2}B^{\theta}_{M}}$
(91)

if $\forall j\leq i$

$\displaystyle\|\Delta\mu_{\ell,j})\|$ $\displaystyle\leq(B_{1},B_{2})\text{
and }\|\Delta\rho_{\ell,j}\|$ $\displaystyle\leq(D_{1},D_{2})$ (92)

where

$\displaystyle B_{1}$ $\displaystyle\triangleq\frac{\varepsilon
b_{\epsilon}}{(1+\gamma)B^{\omega}_{\ell,j}B_{e}\beta_{j}\Omega^{i-j}\Phi_{i}}$
(93) $\displaystyle B_{2}$
$\displaystyle\triangleq\frac{\varepsilon}{2\beta_{0}(\gamma\lambda)^{I_{1}-j}I_{1}|M_{k,j}|B_{i}^{\delta}\Omega^{i-I_{1}}\Phi_{i}}$
(94) $\displaystyle D_{1}$ $\displaystyle\triangleq\frac{\varepsilon
b_{\epsilon}}{B_{e}\beta_{j}B_{j}^{\delta}\Omega^{i-j}\Phi_{i}}$ (95)
$\displaystyle D_{2}$
$\displaystyle\triangleq\left(\frac{b_{\epsilon}}{\gamma}\right)^{I_{2}-j}\frac{\varepsilon(1-\lambda)^{-1}}{2F_{k,j}(I_{2})^{2}\beta_{0}B_{i}^{\delta}\Omega^{i-I_{2}}\Phi_{i}}$
(96) $\displaystyle I_{1}$
$\displaystyle\triangleq\left[\ln\frac{\Omega}{\gamma\lambda}\right]^{-1},\quad
I_{2}\triangleq 2\left[\ln\frac{b_{\epsilon}\Omega}{\gamma}\right]^{-1}$ (97)

$\blacksquare$

###### Proof.

$\displaystyle\Delta\omega_{k,i+1}$
$\displaystyle=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\Delta\omega_{\ell,i}+\beta_{i}\widehat{\delta}_{\ell,i}\widehat{\rho}_{i}\widehat{e}_{i}\right)$
$\displaystyle-\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\beta_{i}\delta_{\ell,i}\rho_{\ell,i}e_{\ell,i}\right)$
$\displaystyle=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{k,\ell}\left(\Delta\omega_{\ell,i-1}+\beta_{i}\Delta\delta_{\ell,i}\widehat{\rho}_{i}\widehat{e}_{i}\right.$
$\displaystyle\left.+\beta_{i}\delta_{\ell,i}\Delta\rho_{\ell,i}\widehat{e}_{i}+\beta_{i}\delta_{\ell,i}\rho_{\ell,i}\Delta
e_{\ell,i}\right)$ (98)

We can express $\Delta\delta_{k,i}$ as

$\displaystyle\|\Delta\delta_{k,i}\|$
$\displaystyle=\|(\gamma\widehat{\eta}_{k,i}-\widehat{\mu}_{k,i})\widehat{\omega}_{k,i}-(\gamma\eta_{k,i}-\mu_{k,i})\omega_{k,i}\|$
$\displaystyle=\|(\gamma\widehat{\eta}_{k,i}-\widehat{\mu}_{k,i})\Delta\omega_{k,i}\|+\|(\gamma\Delta\eta_{k,i}-\Delta\mu_{k,i})\omega_{k,i}\|$
$\displaystyle\leq(1+\gamma)\|\Delta\omega_{k,i}\|+\|(\gamma\Delta\eta_{k,i}-\Delta\mu_{k,i})\|\|\omega_{k,i}\|$
(99)

Therefore, (146) can be modified as

$\displaystyle\|\Delta\omega_{k,i+1}\|=\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,i}\left(\|\Delta\omega_{\ell,i}\|+\beta_{i}|\Delta\delta_{\ell,i}|\widehat{\rho}_{i}\|\widehat{e}_{i}\|\right.$
$\displaystyle\left.+\beta_{i}|\delta_{\ell,i}|\|\Delta
e_{\ell,i}\|\widehat{\rho}_{\ell,i}+\beta_{i}|\delta_{\ell,i}|\|e_{\ell,i}\|\Delta\rho_{\ell,i}\right)$
$\displaystyle\leq\left(1+\beta(1+\gamma)\widehat{\rho}_{i}\|\widehat{e}_{i}\|\right)\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,i}\|\Delta\omega_{\ell,i}\|$
$\displaystyle+\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,i}\left(\beta_{i}|(\gamma\Delta\eta_{\ell,i}-\Delta\mu_{\ell,i})|\|\omega_{\ell,i}\|\widehat{\rho}_{i}\|\widehat{e}_{i}\|\right.$
$\displaystyle\left.+\beta_{i}|\delta_{\ell,i}|\|\Delta
e_{\ell,i}\|\widehat{\rho}_{i}+\beta_{i}\|\delta_{\ell,i}\|\|e_{\ell,i}\|\|\Delta\rho_{\ell,i}\|\right)$
$\displaystyle\leq\left(1+\beta(1+\gamma)\widehat{\rho}_{i}\|\widehat{e}_{i}\|\right)\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,i}\|\Delta\omega_{\ell,i}\|$
$\displaystyle+\sum\limits_{\ell\in\mathcal{N}_{k}}c_{\ell,i}\left(\beta_{i}\|(\gamma\Delta\eta_{\ell,i}-\Delta\mu_{\ell,i})\|\|\omega_{\ell,i}\|\widehat{\rho}_{i}\|\widehat{e}_{i}\|\right.$
$\displaystyle\left.+\beta_{i}\|\delta_{\ell,i}\||\Delta\rho_{\ell,i}|\|\widehat{e}_{i}\|+\beta_{i}|\delta_{\ell,i}|\rho_{\ell,i}\|\Delta
e_{\ell,i}\|\right)$ (100)

Now, we impose the following constraint $\forall\ell\in\mathcal{K}$, $\forall
j\leq i$:

$\displaystyle\left(\beta_{j}\|(\gamma\Delta\eta_{\ell,j}-\Delta\mu_{\ell,j})\|\|\omega_{\ell,j}\|\widehat{\rho}_{\ell,j}\|\widehat{e}_{\ell,j}\|\right.$
$\displaystyle\left.+\beta_{j}|\delta_{\ell,j}|\|\Delta\rho_{\ell,j}\|\|\widehat{e}_{\ell,j}\|+\beta_{j}|\delta_{\ell,j}|\rho_{\ell,j}\|\Delta
e_{\ell,j}\|\right)$ $\displaystyle\leq\frac{3\varepsilon
b_{\epsilon}\Omega^{j-i}}{4\beta_{i}(1+\gamma)\pi^{2}B^{\theta}_{M}i^{3}}$
(101)

Since the left-hand side comprises a summation of three terms, we assert that
each term is constrained to be at most one-third of the value on the right-
hand side. Next, we use these inequalities to explicitly express bounds for
$\|\Delta\mu_{k,j}\|$, $\|\Delta\eta_{\ell,j}\|$, $\|\Delta e_{\ell,j}\|$ and
$\|\Delta\rho_{\ell,j}\|$:

$\displaystyle\|\Delta\eta_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-2}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}\|\omega_{\ell,j}\|\widehat{\rho}_{\ell,j}\|\widehat{e}_{\ell,j}\|\beta_{j}\Omega^{i-j}}$
(102) $\displaystyle\|\Delta\mu_{\ell,j})\|\leq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-2}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}\|{\omega}_{\ell,j}\|\widehat{\rho}_{\ell,j}\|\widehat{e}_{\ell,j}\beta_{j}\Omega^{i-j}}$
(103) $\displaystyle\|\Delta e_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-1}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}\|\widehat{\rho}_{\ell,j}\|\beta_{j}|\delta_{\ell,j}|\Omega^{i-j}}$
(104) $\displaystyle\|\Delta\rho_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-1}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}\|e_{\ell,j}\|\beta_{j}|\delta_{\ell,j}|\Omega^{i-j}}$
(105)

If (102)-(105) are satisfied then (A-A) can be upper-bounded as

$\displaystyle\|\Delta\omega_{k,i+1}\|$
$\displaystyle\leq\sum\limits_{\ell\in\mathcal{N}_{k}}\left[\sum_{j=0}^{i}\prod\limits_{z=j+1}^{i}\frac{3c_{k,\ell}\varepsilon
b_{\epsilon}\left(1+\beta(1+\gamma)\widehat{\rho}_{z}\|\widehat{e}_{z}\|\right)}{8(1+\gamma)\pi^{2}B^{\theta}_{M}i^{3}\Omega^{i-j}}\right]$
$\displaystyle\leq\sum\limits_{\ell\in\mathcal{N}_{k}}\frac{3c_{k,\ell}\varepsilon
b_{\epsilon}(1+\gamma)^{-1}}{4\beta_{i}i^{2}\pi^{2}B^{\theta}_{M}}=\frac{3\varepsilon
b_{\epsilon}(1+\gamma)^{-1}}{4\beta_{i}i^{2}\pi^{2}B^{\theta}_{M}}$ (106)

To make conditions (102)-(105) interpretable we bound some terms in the
expressions using Lemmas 2 and 5 and $\rho_{\ell,j}\leq\frac{1}{b_{\epsilon}}$
(Assumption 4):

$\displaystyle\|\Delta\eta_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}^{2}(1+\gamma)^{-2}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}B^{\omega}_{j}B_{e}\beta_{j}\Omega^{i-j}}$
(107) $\displaystyle\|\Delta\mu_{\ell,j})\|\leq\frac{\varepsilon
b_{\epsilon}^{2}(1+\gamma)^{-2}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}B^{\omega}_{j}B_{e}\beta_{j}\Omega^{i-j}}$
(108) $\displaystyle\|\Delta e_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}^{2}(1+\gamma)^{-1}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}\beta_{j}B_{j}^{\delta}\Omega^{i-j}}$
(109) $\displaystyle\|\Delta\rho_{\ell,j}\|\leq\frac{\varepsilon
b_{\epsilon}(1+\gamma)^{-1}\pi^{-2}}{4\beta_{i}B^{\theta}_{M}i^{3}B_{e}\beta_{j}B_{j}^{\delta}\Omega^{i-j}}$
(110)

Next, using Lemma 6 we express the constraint (109) in terms of the conditions
for $\Delta\rho_{k,i}$ and $\Delta\mu_{k,i}$. Namely, (109) is satisfied if
for all $z\leq j$

$\displaystyle\|\Delta\mu_{k,z}\|\leq\frac{\varepsilon
b_{\epsilon}^{2}\beta_{0}}{2\beta_{i}(\gamma\lambda)^{j-z}j|M_{k,z}|\beta_{j}B^{\delta}_{j}\Omega^{i-j}\Phi_{i}}$
(111)
$\displaystyle\Delta\rho_{k,z}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{j-z}\frac{\varepsilon
b_{\epsilon}(1-\lambda)^{-1}\beta_{0}}{2\beta_{i}F_{k,z}i^{2}\beta_{j}B^{\delta}_{j}\Omega^{i-j}\Phi_{i}}$
(112)

Now, we minimize the upperbounds in (111) and (112) with respect to $j$, so we
can generalize the conditions

$\displaystyle\|\Delta\mu_{k,z}\|\leq\min\limits_{j\leq i}\frac{\varepsilon
b_{\epsilon}\beta_{0}(\gamma\lambda)^{z-j}}{2\beta_{i}j|M_{k,z}|\beta_{j}B_{j}^{\delta}\Omega^{i-j}\Phi_{n}}$
(113)

which is equivalent to solving

$\displaystyle\max\limits_{j\leq i}\
(\gamma\lambda)^{j}j\beta_{j}B_{j}^{\delta}\Omega^{-j}\stackrel{{\scriptstyle\text{(a)}}}{{\leq}}B_{i}^{\delta}\beta_{0}\max\limits_{j\leq
i}\ (\gamma\lambda)^{j}j\Omega^{-j}$ (114)

where in (a), we leverage the property that $B^{\delta}_{j}$ increases with
$j$ (see Lemma 5) and the assumption $\beta_{0}\geq\beta_{j}$ for all $j\geq
0$. Therefore, we seek to solve the optimization problem

$\displaystyle\max\limits_{j\leq i}\
\left(\frac{\gamma\lambda}{\Omega}\right)^{j}j$ (115)

which is maximized if

$\displaystyle j=\left[\ln\frac{\Omega}{\gamma\lambda}\right]^{-1}\triangleq
I_{1}$ (116)

Next, we minimize the upperbound in (112) with respect to $j$

$\displaystyle\min\limits_{j\leq
i}\left(\frac{b_{\epsilon}}{\gamma}\right)^{j-z-1}\frac{\varepsilon
b_{\epsilon}^{2}(1-\lambda)^{-1}\pi^{-2}}{8\beta_{i}\gamma
F_{k,z}j^{2}B^{\theta}_{M}i^{3}\beta_{j}B^{\delta}_{j}\Omega^{i-j}}$ (117)

which is equivalent to solving

$\displaystyle\max\limits_{j\leq
i}\left(\frac{\gamma}{b_{\epsilon}}\right)^{j}j^{2}\Omega^{-j}\beta_{j}B_{j}^{\delta}\leq
B_{i}^{\delta}\beta_{0}\max\limits_{j\leq
i}\left(\frac{\gamma}{b_{\epsilon}\Omega}\right)^{j}j^{2}$ (118)

This is maximized for

$\displaystyle
j=2\left[\ln(\frac{b_{\epsilon}}{\gamma}+\frac{\beta(1+\gamma)B_{e}}{\gamma})\right]^{-1}\triangleq
I_{2}$ (119)

Combining (108), (110)-(112), (116) and (119) we reach (91). ∎

######  Lemma 8.

For all agents $k\in\mathcal{}K$ and $\forall i\leq(n-1)$, it holds that

$\displaystyle\|\Delta\Psi_{k,i}\|\leq\frac{3\varepsilon
b_{\epsilon}}{2\beta_{i}i^{2}\pi^{2}B_{M}^{\theta}B^{\delta}_{i}}$ (120)

$\blacksquare$

###### Proof.

$\displaystyle\|\Delta\Psi_{k,i}(a)\|$
$\displaystyle=\|\Delta\mu_{k,i}-\widehat{\mu}_{k,i}\widehat{\pi}(a|\widehat{\mu}_{k,i})+\mu_{k,i}\pi(a|\mu_{k,i})\|$
$\displaystyle=\|\Delta\mu_{k,i}-\Delta\mu_{k,i}\widehat{\pi}_{k,i}(a\|\widehat{\mu}_{k,i})$
$\displaystyle-\mu_{k,i}\Delta\pi_{k,i}(a\|\mu_{k,i})\|$
$\displaystyle\leq\|\Delta\mu_{k,i}\|+\|\Delta\mu_{k,i}\widehat{\pi}_{k,i}(a\|\widehat{\mu}_{k,i})\|$
$\displaystyle+\|\mu_{k,i}\|\|\Delta\pi_{k,i}(a\|\mu_{k,i})\|$
$\displaystyle\stackrel{{\scriptstyle\text{ (a)
}}}{{\leq}}(2+L)\Delta\mu_{k,i}$ (121)

where in (a) we use Lipschitz continuity of policy functions with respect to
belief vectors. Therefore, we can claim that (120) is satisfied if

$\displaystyle\Delta\mu_{k,i}\leq\frac{3\varepsilon
b_{\epsilon}}{2(2+L)\beta_{i}i^{2}\pi^{2}B_{M}^{\theta}B^{\delta}_{i}}$ (122)

∎

###  A-B Proof of Theorem 1

###### Proof.

$\displaystyle\Delta\theta_{k,n}$
$\displaystyle=\Delta\theta_{k,n-1}+\beta_{n}\widehat{\rho}_{n}\widehat{M}^{\theta}_{n}\widehat{\Psi}_{n}\widehat{\delta}_{k,n}$
$\displaystyle-\beta_{n}\rho_{k,n}M^{\theta}_{k,n}\Psi_{k,n}\delta_{k,n}$
$\displaystyle=\Delta\theta_{k,n-1}+\beta_{n}(\Delta\rho_{k,n}\widehat{M}^{\theta}_{n}\widehat{\Psi}_{n}\widehat{\delta}_{k,n}$
$\displaystyle+\rho_{k,n}\Delta
M^{\theta}_{k,n}\widehat{\Psi}_{k,n}\widehat{\delta}_{k,n}+\rho_{k,n}M^{\theta}_{k,n}\Delta\Psi_{k,n}\widehat{\delta}_{k,n}$
$\displaystyle+\rho_{k,n}M^{\theta}_{k,n}\Psi_{k,n}\Delta\delta_{k,n})$
$\displaystyle=\sum\limits_{i=0}^{n-1}\beta_{i}\left(\Delta\rho_{k,i}\widehat{M}^{\theta}_{i}\widehat{\Psi}_{i}\widehat{\delta}_{k,i}+\rho_{k,i}\Delta
M^{\theta}_{k,i}\widehat{\Psi}_{k,i}\widehat{\delta}_{k,i}\right.$
$\displaystyle\left.+\rho_{k,i}M^{\theta}_{k,i}\Delta\Psi_{k,i}\widehat{\delta}_{k,i}+\rho_{k,i}M^{\theta}_{k,i}\Psi_{k,i}\Delta\delta_{k,i}\right)$
(123)

where, in obtaining the last equality, we repeatedly apply the recursive
formula. We aim to bound (A-B) by $\varepsilon$. Given the well-known series:

$\displaystyle\sum\limits_{i=1}^{\infty}\frac{1}{i^{2}}=\frac{\pi^{2}}{6}$
(124)

we introduce the inequalities:

$\displaystyle\Delta\rho_{k,i}\leq\frac{3}{2\beta_{i}\pi^{2}i^{2}\widehat{M}^{\theta}_{i}\widehat{\Psi}_{i}\widehat{\delta}_{k,i}}$
(125) $\displaystyle\Delta
M^{\theta}_{k,i}\leq\frac{3}{2\beta_{i}\pi^{2}i^{2}\rho_{k,i}\widehat{\Psi}_{k,i}\widehat{\delta}_{k,i}}$
(126)
$\displaystyle\Delta\Psi_{k,i}\leq\frac{3}{2\beta_{i}\pi^{2}i^{2}\rho_{k,i}M^{\theta}_{k,i}\widehat{\delta}_{k,i}}$
(127)
$\displaystyle\Delta\delta_{k,i}\leq\frac{3}{2\beta_{i}\pi^{2}i^{2}\rho_{k,i}M^{\theta}_{k,i}\Psi_{k,i}}$
(128)

Then, substituting (125)-(128) into (A-B), we obtain:

$\displaystyle\Delta\theta_{k,n}$
$\displaystyle\leq\sum\limits_{i=0}^{\infty}\beta_{i}\left(\Delta\rho_{k,i}\widehat{M}^{\theta}_{i}\widehat{\Psi}_{i}\widehat{\delta}_{k,i}\right.$
$\displaystyle+\rho_{k,i}\Delta
M^{\theta}_{k,i}\widehat{\Psi}_{k,i}\widehat{\delta}_{k,i}+\rho_{k,i}M^{\theta}_{k,i}\Delta\Psi_{k,i}\widehat{\delta}_{k,i}$
$\displaystyle\left.+\rho_{k,i}M^{\theta}_{k,i}\Psi_{k,i}\Delta\delta_{k,i}\right)\leq\frac{6}{\pi^{2}}\sum\limits_{i=1}^{\infty}\frac{1}{i^{2}}=\varepsilon$
(129)

We aim to write the conditions in (125)-(128) in terms of conditions for
$\Delta\rho_{k,i}$ and $\Delta\mu_{k,i}$. To this end, we first express
$\Delta\delta_{k,i}$ as

$\displaystyle|\Delta\delta_{k,i}|$
$\displaystyle=|(\gamma\widehat{\eta}_{k,i}-\widehat{\mu}_{k,i})\widehat{\omega}_{k,i}-(\gamma\eta_{k,i}-\mu_{k,i})\omega_{k,i}|$
$\displaystyle=|(\gamma\widehat{\eta}_{k,i}-\widehat{\mu}_{k,i})\Delta\omega_{k,i}+(\gamma\Delta\eta_{k,i}-\Delta\mu_{k,i})\omega_{k,i}|$
$\displaystyle\leq(1+\gamma)\|\Delta\omega_{k,i}\|$
$\displaystyle+\|(\gamma\Delta\eta_{k,i}-\Delta\mu_{k,i})\|\|\omega_{k,i}\|$
(130)

Condition (128) can be split into the following tighter conditions $\forall
i\leq n-1$

$\displaystyle\Delta\omega_{k,i}\leq\frac{3\varepsilon}{4\beta_{i}(1+\gamma)i^{2}\pi^{2}M^{\theta}_{k,i}{\Psi}_{k,i}\rho_{k,i}}$
(131)
$\displaystyle\Delta\mu_{k,i}\leq\frac{3\varepsilon}{4\beta_{i}(1+\gamma)i^{2}\pi^{2}M^{\theta}_{k,i}\Psi_{k,i}\rho_{k,i}\|\omega_{k,i}\|}$
(132)

Note that
$\rho_{k,i},M^{\theta}_{k,i},\widehat{M}^{\theta}_{k,i},\Psi_{k,i},\widehat{\Psi}_{k,i}$,
$\omega_{k,i}$, and $\widehat{\delta}_{i}$ are not known at the beginning of
iteration $i$. To circumvent this issue, we can upperbound these variables and
get tighter conditions than in (125-127) and (131)-(132). The importance
sampling ratio $\rho_{k,i}$ can be upper-bounded by $\frac{1}{b_{\epsilon}}$ .
Using the properties $\|\mu^{b}_{k,n}\|\leq 1$, $\forall b\in\mathcal{A}$ and
$\|\pi(\cdot)\|\leq 1$, we can upper-bound $\Psi_{k,i}$ as

$\displaystyle\|\Psi_{k,i}(a)\|=\|\mu_{k,i}-\mu_{k,i}\pi(a\|\mu_{k,i};\theta_{k,i})\|\leq
1$ (133)

Similarly, we can show that

$\displaystyle\|\widehat{\Psi}_{k,i}\|\leq 1$ (134)

The upper-bounds for $\widehat{\delta}_{i}$, $M^{\theta}_{k,i}$, and
$\widehat{M}^{\theta}_{k,i}$ are given in Lemmas 5 and 3, respectively.
Therefore, the conditions in (125)-(127) and (131)-(132) can be modified as

$\displaystyle\|\Delta\omega_{k,i}\|\leq\frac{3b_{\epsilon}\varepsilon}{4\beta_{i}(1+\gamma)i^{2}\pi^{2}B^{\theta}_{M}}$
(135)
$\displaystyle\|\Delta\mu_{k,i}\|\leq\frac{3b_{\epsilon}\varepsilon}{4\beta_{i}(1+\gamma)i^{2}\pi^{2}B^{\theta}_{M}B_{i}^{\omega}}$
(136) $\displaystyle\|\Delta M^{\theta}_{k,i}\|\leq\frac{3\varepsilon
b_{\epsilon}}{2\beta_{i}i^{2}\pi^{2}B^{\delta}_{i}}$ (137)
$\displaystyle\|\Delta\Psi_{k,i}\|\leq\frac{3\varepsilon
b_{\epsilon}}{2\beta_{i}i^{2}\pi^{2}B_{M}^{\theta}B^{\delta}_{i}}$ (138)
$\displaystyle\|\Delta\rho_{k,i}\|\leq\frac{3\varepsilon}{2\beta_{i}i^{2}\pi^{2}B_{M}^{\theta}B^{\delta}_{i}}$
(139)

According to Lemma 7, (135) is satisfied if $\forall j\leq i\leq n$:

$\displaystyle\Delta\mu_{k,j}\leq\min(B_{1},B_{2})\text{ and
}\Delta\rho_{k,j}\leq\min(D_{1},D_{2})$ (140)

To generalize the results in (140), i.e. to find the conditions which will be
valid for all $j\leq n-1$, we need to minimize the bounds with respect to $i$.
We can easily derive that

$\displaystyle\min\limits_{i\leq
n}B_{1}(i)=B_{1}(n)\triangleq\widetilde{B}_{1}$ (141)
$\displaystyle\min\limits_{i\leq
n}B_{2}(i)=B_{2}(n)\triangleq\widetilde{B}_{2}$ (142)
$\displaystyle\min\limits_{i\leq
n}D_{1}(i)=D_{1}(n)\triangleq\widetilde{D}_{1}$ (143)
$\displaystyle\min\limits_{i\leq
n}D_{2}(i)=D_{2}(n)\triangleq\widetilde{D}_{2}$ (144)

Next, according to Lemma 10, (137) is met if for all $j\leq(i-1)<n$

$\displaystyle\Delta\rho_{k,j}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{i-j-1}\frac{3\varepsilon
b_{\epsilon}^{2}}{8\gamma\zeta\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}F_{k,j}}$
(145)

To find the general condition that will satisfy for all $i<n-1$ we need to
minimize the bound in (145) with respect to $i$. Equivalently, we need to
solve the following maximization problem

$\displaystyle\max\limits_{i\leq
n}\left(\frac{\gamma}{b_{\epsilon}}\right)^{i}i^{2}B_{i}^{\delta}\stackrel{{\scriptstyle\text{
(a) }}}{{\leq}}B_{n}^{\delta}\max\limits_{i\leq
n}\left(\frac{\gamma}{b_{\epsilon}}\right)^{i}i^{2}$ (146)

where (a) is due to the monotonicity of $B^{\delta}_{i}$. The solution for the
last maximization in (146) is

$\displaystyle i^{*}=\frac{2}{\ln\frac{b_{\epsilon}}{\gamma}}\triangleq I_{3}$
(147)

According to Lemma 8, (138) is fulfilled if

$\displaystyle\Delta\mu_{k,i}\leq\frac{3\varepsilon
b_{\epsilon}}{2(2+L)\beta_{n}i^{2}\pi^{2}B_{M}^{\theta}B^{\delta}_{i}}$ (148)

∎

######  Lemma 9.

For all agents $k\in\mathcal{K}$, it holds that

$\|\Delta M_{k,n}\|\triangleq\|\widehat{M}_{k,n}-M_{k,n}\|\leq\varepsilon$
(149)

if $\forall i\leq(n-1)$

$\Delta\rho_{k,i}\leq\frac{6\varepsilon
b_{\epsilon}^{n-i-1}}{\pi^{2}i^{2}\gamma F_{k,i}\gamma^{n-i-1}(1-\lambda)}$
(150)

$\blacksquare$

###### Proof.

$\displaystyle\Delta F_{k,n}$ $\displaystyle=\widehat{F}_{k,n}-F_{k,n}$
$\displaystyle=\gamma(\widehat{\rho}_{k,n-1}\widehat{F}_{k,n-1}-\rho_{k,n-1}F_{k,n-1})$
$\displaystyle=\gamma(\widehat{\rho}_{k,n-1}\Delta
F_{k,n-1}+\Delta\rho_{k,n-1}F_{k,n-1})$
$\displaystyle=\sum\limits_{i=0}^{n-1}\prod_{j=i+1}^{n-1}(\gamma\rho_{k,j})\gamma\Delta\rho_{k,i}F_{k,i}$
$\displaystyle\leq\sum\limits_{i=0}^{n-1}\left(\frac{\gamma}{b_{\epsilon}}\right)^{n-i-1}\gamma\Delta\rho_{k,i}F_{k,i}$
(151)

We know that $\sum\limits_{i=1}^{\infty}\frac{1}{i^{2}}=\frac{\pi^{2}}{6}$. To
bound (A-B) by $\varepsilon$ we can impose the following condition:

$\displaystyle\Delta\rho_{k,i}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{n-i-1}\frac{6\varepsilon}{\gamma
F_{k,i}\pi^{2}i^{2}}$ (152)

We notice that $\Delta M_{k,n}=(1-\lambda)\Delta F$. So, $\Delta M_{k,n}$ is
$\varepsilon$\- bounded if

$\displaystyle\Delta\rho_{k,i}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{n-i-1}\frac{6\varepsilon}{\gamma\pi^{2}i^{2}F_{k,i}(1-\lambda)}$
(153)

then (A-B) is $\varepsilon$\- bounded at time $n$. ∎

######  Lemma 10.

For all agents $k\in\mathcal{K}$

$\displaystyle\Delta M^{\theta}_{k,i}\leq\frac{3\varepsilon
b_{\epsilon}}{4\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}}$ (154)

if for all $j\leq(i-1)$

$\displaystyle\Delta\rho_{k,j}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{i-j-1}\frac{3\gamma\varepsilon
b_{\epsilon}^{2}}{8\gamma\zeta\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}F_{k,j}}$
(155)

$\blacksquare$

###### Proof.

$\displaystyle\Delta M^{\theta}_{k,i}$
$\displaystyle=\lambda^{\theta}\gamma(\widehat{\rho}_{k,i-1}\widehat{F}_{k,i-1}-\rho_{k,i-1}F_{k,i-1})$
$\displaystyle=\lambda^{\theta}\gamma(\Delta\rho_{k,i-1}F_{k,i-1}+\widehat{\rho}_{k,i-1}\Delta
F_{k,i-1})$ $\displaystyle\leq\frac{3\varepsilon
b_{\epsilon}}{4\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}}$ (156)

The last inequality is true if we impose the following constraints

$\displaystyle\Delta\rho_{k,i-1}\leq\frac{3\varepsilon
b_{\epsilon}}{8\zeta\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}F_{k,i-1}}\text{ and }$
(157) $\displaystyle\Delta F_{k,i}\leq\frac{3\varepsilon
b_{\epsilon}^{2}}{8\zeta\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}}$ (158)

where (a) is due to $\rho_{k,t}\leq\frac{1}{b_{\epsilon}}$. Next, we extend
the definition of $\Delta F_{k,i}$:

$\displaystyle\Delta F_{k,i}$ $\displaystyle=\widehat{F}_{k,i}-F_{k,i}$ (159)
$\displaystyle=\gamma(\widehat{\rho}_{k,i-1}\widehat{F}_{k,i-1}-\rho_{k,i-1}F_{k,i-1})$
$\displaystyle=\gamma(\widehat{\rho}_{k,i-1}\Delta
F_{k,i-1}+\Delta\rho_{k,i-1}F_{k,i-1})$
$\displaystyle=\sum\limits_{j=0}^{i-1}\prod_{z=j+1}^{i-1}(\gamma\rho_{k,z})\gamma\Delta\rho_{k,j}F_{k,j}$
$\displaystyle\stackrel{{\scriptstyle\text{ (a)
}}}{{\leq}}\sum\limits_{t=0}^{i-1}\left(\frac{\gamma}{b_{\epsilon}}\right)^{i-j-1}\gamma\Delta\rho_{k,j}F_{k,j}$
(160)

Therefore, the condition in (158) can be replaced with the following tighter
condition $\forall j\leq(i-1)$:

$\displaystyle\Delta\rho_{k,j}\leq\left(\frac{b_{\epsilon}}{\gamma}\right)^{i-j-1}\frac{3\gamma\varepsilon
b_{\epsilon}^{2}}{8\gamma\zeta\beta_{n}i^{2}\pi^{2}B^{\delta}_{i}F_{k,j}}$
(161)

Note that for $j=i-1$ the condition in (161) is more strict than in (157).
Hence, we can assert a generalization that (154) holds true if (161) is
satisfied. ∎

######  Lemma 11.

At time $n$, $\Delta e_{k,n}$ is $\varepsilon$-bounded if $\forall i\leq n-1$:

$\Delta\rho_{k,i}\leq\frac{18\varepsilon
b_{\epsilon}^{n-i-1}}{n^{2}\pi^{4}i^{2}F_{k,t}\gamma^{n-i}(1-\lambda)}$ (162)

and $\forall i\leq n$

$\displaystyle\Delta\mu_{k,i}\leq\frac{3\varepsilon}{\pi^{2}}\frac{1}{i^{2}(\gamma\lambda)^{n-i}\|\|M_{k,i}\|\|}$
(163)

$\blacksquare$

###### Proof.

We start from definition of $\Delta e_{k,n}$

$\displaystyle\Delta e_{k,n}$ $\displaystyle=\gamma\lambda\Delta
e_{k,n-1}+\widehat{M}_{k,n}\widehat{\mu}_{k,n}-M_{k,n}\mu_{k,n}$
$\displaystyle=\gamma\lambda\Delta e_{k,n-1}+\Delta
M_{k,n}\widehat{\mu}_{k,n}+M_{k,n}\Delta\mu_{k,n}$
$\displaystyle\leq\varepsilon$ (164)

Therefore, we have

$\displaystyle\Delta e_{k,n}$
$\displaystyle=\sum_{i=0}^{n}\prod_{j=i+1}^{n}(\gamma\lambda)^{j}(\Delta
M_{k,i}\widehat{\mu}_{k,n}+M_{k,i}\Delta\mu_{k,i})$
$\displaystyle\leq\frac{6\varepsilon}{\pi^{2}}\sum_{i=0}^{n}\frac{1}{i^{2}}\leq\frac{6\varepsilon}{\pi^{2}}\sum_{i=0}^{\infty}\frac{1}{i^{2}}=\varepsilon$
(165)

So, we have that $\Delta e_{k,n}$ is $\varepsilon$-bounded if $\forall i\leq
n$:

$\displaystyle\|\Delta M_{k,i}\|$
$\displaystyle\leq\frac{3\varepsilon}{\pi^{2}}\frac{1}{i^{2}(\gamma\lambda)^{n-i}\|\widehat{\mu}_{k,i}\|}$
$\displaystyle\leq\frac{3\varepsilon}{\pi^{2}}\frac{1}{i^{2}(\gamma\lambda)^{n-i}}$
(166)
$\displaystyle\Delta\mu_{k,i}\leq\frac{3\varepsilon}{\pi^{2}}\frac{1}{i^{2}(\gamma\lambda)^{n-i}M_{k,i}}$
(167)

By Lemma 9, $\Delta M_{k,i}$ is bounded by

$\displaystyle\frac{3\varepsilon}{\pi^{2}}\frac{1}{i^{2}(\gamma\lambda)^{n-i}}$
(168)

if for all $t\leq(i-1)$:

$\displaystyle\Delta\rho_{k,t}$ $\displaystyle\leq\frac{18\varepsilon
b_{\epsilon}^{i-t-1}(1-\lambda)^{-1}}{\pi^{2}i^{2}(\gamma\lambda)^{n-i}\pi^{2}t^{2}\gamma
F_{k,t}\gamma^{i-t-1}}$ (169) $\displaystyle=\frac{18\varepsilon
b_{\epsilon}^{-t-1}(b_{\epsilon}\lambda)^{i}}{\pi^{2}i^{2}(\gamma\lambda)^{n}\pi^{2}t^{2}\gamma
F_{k,t}\gamma^{-t-1}(1-\lambda)}$ (170)

Since $b_{\epsilon}\lambda\leq 1$ the bound in (169) is minimized for $i=n$

$\Delta\rho_{k,t}\leq\frac{18\varepsilon
b_{\epsilon}^{n-t-1}}{n^{2}\pi^{4}t^{2}F_{k,t}\gamma^{n-t}(1-\lambda)}$ (171)

∎

###  A-C Proof of Corollary 1

###### Proof.

We start from the definition of $\widehat{\rho}_{k,n}$:

$\displaystyle\widehat{\rho}_{k,n}(a)$
$\displaystyle=\frac{\pi_{k,n}(a\|\widehat{\mu}_{k,n})}{b_{k,n}(a\|\widehat{\mu}_{k,n})}-\rho_{k,n}(a)$
$\displaystyle=\frac{\exp[\widehat{\mu}_{k,n}^{T}(\theta_{a}-\bar{\theta}_{a})]\sum\limits_{c\in\mathcal{A}}\exp[\widehat{\mu}_{k,n}^{T}\bar{\theta}_{c}]}{\sum\limits_{c\in\mathcal{A}}\exp[\widehat{\mu}_{k,n}^{T}\theta_{c}]}$
$\displaystyle\leq\exp[\widehat{\mu}_{k,n}^{T}(\theta_{a}-\bar{\theta}_{a}+\bar{\theta}_{\max}-\theta_{\min})]$
(172)

Using the definition of $\Delta\rho_{k,n}$ and (172) , we impose the following
constraint to satisfy the condition (46):

$\displaystyle\exp[(\mu_{k,n}+\Delta\mu_{k,n})^{T}(\theta_{a}-\bar{\theta}_{a}+\bar{\theta}_{\max}-\theta_{\min})]$
$\displaystyle\leq\min(\tilde{D}_{1},\widetilde{D}_{2},\widetilde{D}_{3})+\rho_{k,n}(a)$
(173)

Hence, we can set

$\displaystyle\Delta\mu_{k,n}^{T}(\theta_{a}-\bar{\theta}_{a}+\bar{\theta}_{\max}-\theta_{\min})$
$\displaystyle\leq\ln\left[\frac{\min(\widetilde{D}_{1},\widetilde{D}_{2},\widetilde{D}_{3})+\rho_{k,n}(a)}{\exp[\mu_{k,n}^{T}\Theta]}\right]$
(174)

which further leads to the following constraint

$\displaystyle\|\Delta\mu_{k,n}^{T}\|$
$\displaystyle\leq\frac{1}{\|\Theta\|}\ln\left[\frac{\min(\tilde{D}_{1},\widetilde{D}_{2},\widetilde{D}_{3})+\rho_{k,n}(a)}{\exp[\mu_{k,n}^{T}\Theta]}\right]$
$\displaystyle\triangleq\widetilde{B}_{3}$ (175)

Combining (45) with the result in (A-C) we conclude the proof. ∎

## References

  * [1] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in _Advances in International Conference on Neural Information Processing Systems_. Curran Associates Inc., 2017, p. 6382–6393.
  * [2] T. Rashid, M. Samvelyan, C. S. D. Witt, G. Farquhar, J. N. Foerster, and S. Whiteson, “Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning,” 2018. [Online]. Available: https://api.semanticscholar.org/CorpusID:4533648
  * [3] A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson, _MAVEN: Multi-Agent Variational Exploration_. Red Hook, NY, USA: Curran Associates Inc., 2019.
  * [4] C. S. D. Witt, T. Gupta, D. Makoviichuk, V. Makoviychuk, P. H. S. Torr, M. Sun, and S. Whiteson, “Is independent learning all you need in the starcraft multi-agent challenge?” 2020. [Online]. Available: https://api.semanticscholar.org/CorpusID:227054146
  * [5] W. Suttle, Z. Yang, K. Zhang, Z. Wang, T. Başar, and J. Liu, “A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 1549–1554, 2020, 21st IFAC World Congress. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2405896320326562
  * [6] T. Degris, M. White, and R. S. Sutton, “Off-policy actor-critic,” in _Proceedings International Conference on Machine Learning_ , 2012, p. 179–186.
  * [7] M. Chen, C. Xu, V. Gatto, D. Jain, A. Kumar, and E. Chi, “Off-policy actor-critic for recommender systems,” in _Proceedings ACM Conference on Recommender Systems_ , 2022, p. 338–349.
  * [8] W. Zhou, Y. Li, Y. Yang, H. Wang, and T. Hospedales, “Online meta-critic learning for off-policy actor-critic methods,” in _Proceedings Advances in Neural Information Processing Systems_ , vol. 33, 2020, pp. 17 662–17 673.
  * [9] T. Degris, M. White, and R. S. Sutton, “Linear off-policy actor-critic,” 2012. [Online]. Available: https://api.semanticscholar.org/CorpusID:10513082
  * [10] Y. Zhang and M. M. Zavlanos, “Cooperative multiagent reinforcement learning with partial observations,” _IEEE Transactions on Automatic Control_ , vol. 69, no. 2, pp. 968–981, 2024.
  * [11] A. Lalitha, T. Javidi, and A. D. Sarwate, “Social learning and distributed hypothesis testing,” _IEEE Transactions on Information Theory_ , vol. 64, no. 9, pp. 6161–6179, 2018.
  * [12] M. DeGroot, _Optimal Statistical Decisions_ , ser. Wiley Classics Library. Wiley, 2005. [Online]. Available: https://books.google.ch/books?id=dtVieJ245z0C
  * [13] R. A. Horn and C. R. Johnson, _Matrix Analysis_. Cambridge University Press, 1985.
  * [14] C. Zhang and V. Lesser, “Coordinated multi-agent reinforcement learning in networked distributed pomdps,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 25, no. 1, pp. 764–770, Aug. 2011. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/7886
  * [15] M. Peti, F. Petric, and S. Bogdan, “Decentralized coordination of multi-agent systems based on pomdps and consensus for active perception,” _IEEE Access_ , vol. 11, pp. 52 480–52 491, 2023.
  * [16] K. He, B. Banerjee, and P. Doshi, “Cooperative-competitive reinforcement learning with history-dependent rewards,” in _Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems_ , 2021, p. 602–610.
  * [17] M. Kayaalp, F. Ghadieh, and A. H. Sayed, “Policy evaluation in decentralized pomdps with belief sharing,” _IEEE Open Journal of Control Systems_ , vol. 2, pp. 125–145, 2023.
  * [18] F. A. Oliehoek, _Decentralized POMDPs_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 471–503.
  * [19] G. Stamatelis and N. Kalouptsidis, “Active hypothesis testing in unknown environments using recurrent neural networks and model free reinforcement learning,” in _31st European Signal Processing Conference (EUSIPCO)_ , 2023, pp. 1380–1384.
  * [20] B. Liu, H. He, and D. W. Repperger, “Two-time-scale online actor-critic paradigm driven by pomdp,” in _2010 International Conference on Networking, Sensing and Control (ICNSC)_ , 2010, pp. 243–248.
  * [21] S. Duell, S. Udluft, and V. Sterzing, _Solving Partially Observable Reinforcement Learning Problems with Recurrent Neural Networks_ , Berlin, Heidelberg, 2012, pp. 709–733.
  * [22] M. Yang, G. Liu, Z. Zhou, and J. Wang, “Partially observable mean field multi-agent reinforcement learning based on graph attention network for uav swarms,” _Drones_ , vol. 7, no. 7, 2023. [Online]. Available: https://www.mdpi.com/2504-446X/7/7/476
  * [23] B. Eker, E. Ozkucur, C. Mericli, T. Mericli, and H. L. Akin, “A finite horizon dec-pomdp approach to multi-robot task learning,” in _5th International Conference on Application of Information and Communication Technologies (AICT)_ , 2011, pp. 1–5.
  * [24] B. Bakker, “Reinforcement learning with long short-term memory,” in _Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic_ , 2001, p. 1475–1482.
  * [25] T. Phan, F. Ritz, P. Altmann, M. Zorn, J. Nüßlein, M. Kölle, T. Gabor, and C. Linnhoff-Popien, “Attention-based recurrence for multi-agent reinforcement learning under stochastic partial observability,” in _Proceedings of the 40th International Conference on Machine Learning_ , 2023, p. 27840–27853.
  * [26] N. Yang, H. Zhang, and R. Berry, “Partially observable multi-agent deep reinforcement learning for cognitive resource management,” in _IEEE Global Communications Conference_ , 2020, pp. 1–6.
  * [27] Z. Xu, Y. Bai, D. Li, B. Zhang, and G. Fan, “Side: State inference for partially observable cooperative multi-agent reinforcement learning,” in _Proceedings International Conference on Autonomous Agents and Multiagent Systems_ , 2022, p. 1400–1408.
  * [28] W. Zhang, X. Chen, and L. Ma, “Online planning for multi-agent systems with consensus protocol,” in _Proceedings of the 33rd Chinese Control Conference_ , 2014, pp. 1126–1131.
  * [29] W. Zhang, L. Ma, and X. Li, “Multi-agent reinforcement learning based on local communication,” _Cluster Computing_ , vol. 22, no. 6, pp. 15 357–15 366, 2019. [Online]. Available: https://doi.org/10.1007/s10586-018-2597-x
  * [30] H. Yu, “On convergence of emphatic temporal-difference learning,” in _Proceedings of The 28th Conference on Learning Theory_ , vol. 40, 2015, pp. 1724–1751.
  * [31] R. S. Sutton, A. R. Mahmood, and M. White, “An emphatic approach to the problem of off-policy temporal-difference learning,” _J. Mach. Learn. Res._ , vol. 17, no. 1, p. 2603–2631, 2016.
  * [32] V. Bordignon, S. Vlaski, V. Matta, and A. H. Sayed, “Learning from heterogeneous data based on social interactions over graphs,” _IEEE Transactions on Information Theory_ , vol. 69, no. 5, pp. 3347–3371, 2023.
  * [33] V. Bordignon, V. Matta, and A. H. Sayed, “Adaptive social learning,” _IEEE Transactions on Information Theory_ , vol. 67, no. 9, pp. 6053–6081, 2021.
  * [34] A. Zhaikhan and A. H. Sayed, “Graph exploration for effective multiagent q-learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–12, 2024.
  * [35] M. Kayaalp, F. Ghadieh, and A. H. Sayed, “Policy evaluation in decentralized pomdps with belief sharing,” _IEEE Open Journal of Control Systems_ , vol. 2, pp. 125–145, 2023.