# Graph Exploration for Effective Multi-agent Q-Learning

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.

###### Abstract

This paper proposes an exploration technique for multi-agent reinforcement
learning (MARL) with graph-based communication among agents. We assume the
individual rewards received by the agents are independent of the actions by
the other agents, while their policies are coupled. In the proposed framework,
neighbouring agents collaborate to estimate the uncertainty about the state-
action space in order to execute more efficient explorative behaviour.
Different from existing works, the proposed algorithm does not require
counting mechanisms and can be applied to continuous-state environments
without requiring complex conversion techniques. Moreover, the proposed scheme
allows agents to communicate in a fully decentralized manner with minimal
information exchange. And for continuous-state scenarios, each agent needs to
exchange only a single parameter vector. The performance of the algorithm is
verified with theoretical results for discrete-state scenarios and with
experiments for continuous ones.

###### Index Terms:

multi-agent reinforcement learning, continuous state space, parallel MDP,
exploration.

##  I Introduction

In reinforcement learning (RL), agents learn gradually through direct
interaction with the environment. The successful operation of any RL algorithm
is dependent on: i) how efficiently an agent is able to learn from collected
data and ii) how efficiently it explores the design space and collects data.
The former process is known as exploitation, while the latter is known as
exploration [1, 2, 3] and it enables agents to explore the environment in a
guided manner in order to collect informative data about the state, reward,
and transition samples. Devising reliable exploration strategies is an
important goal because they allow agents to avoid being trapped into visiting
a limited number of states and ignoring more rewarding possibilities.
Encouraging agents to explore unseen states is essential for allowing
successful learning in many cases of interest.

Exploration in single agent RL has been intensively studied in the literature
while most existing MARL algorithms omit exploration by assuming it is easily
obtainable through naive noise-based methods [4, 5, 6, 7]. As explained in
[8], such standard “non-deep” exploration techniques often fail in sparse
reward problems. In order to tackle this issue, a couple of MARL algorithms
have considered non-trivial exploration mechanisms [9, 10, 11]. However, some
of these works cannot be directly applied to continuous-state problems [9].
This limitation comes from the fact that the exploration approaches proposed
in these works are based on the counting of state-action visitation, which is
technically feasible only when the state space is discrete and finite. A group
of works [10, 11] has developed exploration solutions for continuous-state
environments, but they often lack theoretical guarantees, and do not
necessarily apply to networked agents or require fully connected networks.

To this end, in this work, we propose a provably efficient exploration
algorithm for multi-agent networks. Our model does not require full
connectedness and assumes graph-based communication among the agents. For
learning and execution, the agents do not need to observe the states and
actions of all other agents nor share knowledge with all of them. This model
respects the privacy of agents and better reflects real word scenarios where
the operation of agents is usually localized.

Moreover, our proposed algorithm does not require a counting mechanism. This
is a useful feature because counting is not feasible for large or continuous
state-spaces, which is the case for many situations of interest. To bypass
this problem, we replace the operation of counting by the procedure of
variance estimation within neighborhoods. In general, the use of estimated
variances as an exploration signal is a known technique in the study of
single-agent RL methods [12, 13]. In this scenario, the agent needs to
generate an ensemble of estimates to estimate uncertainties. Extending the
idea to the multi-agent case allows us to avoid the need for ensemble
estimation at the individual agents. This is because agents can now tap into
information from their immediate neighborhoods, thus reducing the workload for
the agents. The challenge is to verify that by doing so, the resulting
exploration strategy leads to effective learning. Indeed, we verify that the
proposed method is provably efficient in a discrete-state scenarios.

In the literature, to the best of our knowledge, the existing provably
efficient MARL algorithms with exploration are those based on counting [9]
and/or consider centralized architectures where agents communicate with all
other agents[11]. In general, the addition of exploration mechanisms to the
MARL setting introduces some stochastic components into the system’s behavior,
which make the theoretical analysis more demanding. Moreover, a suitable
definition of “sufficient exploration” remains open in the literature. One
common metric for evaluating the exploration ability of a strategy is to show
that it leads to a bounded regret. The regret, by definition, is the expected
reward loss due to following some behavioral policy instead of acting
optimally. Therefore, when the regret is bounded, the behavioral policy is
guaranteed to converge to the optimal one. However, regret-based analysis can
be challenging, especially for scenarios with networked agents. One advantage
of our exploration algorithm is that we can examine its convergence properties
by avoiding regret analysis.

In particular, our algorithm is based on the paradigm of Q-learning, which is
known to converge to the optimal solution under the assumption that all states
and actions are visited infinitely often. In addition, recall that Q-learning
is an off-policy algorithm, where an agent can learn the optimal (or target)
policy based on the samples obtained from following a different policy. Such
decoupling between target and behavioral policies allows us to design
behavioral policies that ensure sufficient exploration during learning.
Therefore, in our work, instead of pursuing a regret analysis, we design and
verify that under the proposed behavioral policy all state and actions are
visited infinitely often.

Our work focuses on a specific scenario of MARL where agents exchange
information to improve decision making but they are not collaborating in their
actions. In practice, this scenario fits search problems where collaboration
is not mandatory for fulfilling the target task. In such problems, it is not
necessary that all agents come close to the target to declare that it was
found. If one of the agents finds the target it can share this knowledge with
others so that other agents can update their policies and, at the next step,
make decisions towards the target. As a contrasting example consider a game
where agents not only need to find the object but also to lift or push it. In
this case, cooperation among agents in terms of actions is required since the
heavy object cannot be moved or lifted unless all agents act simultaneously
and in the same direction. This type of multi-agent problems, where concepts
of joint actions and joint rewards are omitted, are best described within the
parallel MDP setting used in [11, 9]. More details are provided in Sec. III

##  II Related work

A plethora of work, including Independent Learning [14], Multi-Agent DDPG
(MADDPG) [15], Q-mix [4] and VDN [16] have been developed in the literature to
capture nonstationarity of the environment and analyze other complexities in
multi-agent problems [14, 15, 4, 16]. However, these works focus on the
exploitation part of RL problems assuming exploration granted. This assumption
is problematic when the reward function depends only on a small subset of an
exponentially growing state space. When the observed reward samples are not
immediately informative, then effective exploration becomes especially
important. Therefore, in this work, we are interested in sparse reward
environments, which most existing strategies in MARL do not contemplate.

One work that targets specifically sparse reward problems is Coordinated
Multi-Agent Exploration (CMAE) [10]. This work develops a state projection-
based scheme, which allows agents to implement a from-low-to-high search in
the state-space. CMAE considers a more general framework than ours as it
allows rewards to depend on joint actions. However, in comparison, there are
three issues that our work can address. First, CMAE is more suitable for grid-
based environments. Its implementation in continuous-state games is complex
and memory demanding due to the need for additional conversion techniques such
as hash-tables and neural networks. Second, the CMAE framework is limited only
to centralized training and decentralized execution paradigm while our
algorithm operates in a fully decentralized mode. Finally, CMAE is mainly
experimentally validated, with theoretical analysis provided for specific
matrix games; its performance in a more general setting is not guaranteed.

Two recent works that studied exploration in a parallel MDP setting are a
graph extension of the upper-confidence bound (GUCB) [9] and a multi-agent
version of Least-square Value Iteration (MALSVI) [11]. Both algorithms are
designed for an episodic MDP, which is commonly considered in less challenging
scenarios than the one assumed in our model, where we consider a discounted
infinite horizon MDP [17, 18]. As the name implies, GUCB allows graph-based
communication among agents. Due to the exploration bonus [9], which depends on
the structure of the graph and the number of state-action visitations, GUCB
executes a provably efficient exploration. However, similar to the single
agent UCB, GUCB is also limited only for the discrete state case and it
requires counting. In comparison, MALSVI is a multi-agent exploration
algorithm that does not need state counting. However, it does not always allow
agents to communicate in a distributed manner. Under MALSVI, agents learn
independently and at some time instances, when a certain condition is met,
knowledge from all agents is aggregated. In other words, the operation of
MALSVI requires periodical full-connectivity of agents, while our algorithm
allows agents to have graph-structured connectivity. Since GUCB and MALSVI are
the closest to our work in the setting, our simulation results will be
presented in comparison to these two algorithms.

##  III Markov Decision Process (MDP)

As an underlying model, we consider a scenario where $K$ agents are learning
over $K$ identical parallel MDPs. The agents can communicate and exchange
information with their neighbors, as defined by some graph $G$. We let
$\mathcal{E}$ denote the edge set of $G$ and introduce the index set
$\mathcal{K}\triangleq[1,2\ldots K]$. The neighbourhood of an agent $k$ is
defined as
$\mathcal{N}_{k}\triangleq\\{j\in\mathcal{K}:(j,k)\in\mathcal{E}\\}$.

Each of the $K$ MDPs is defined by a $5$-tuple
$(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space,
$\mathcal{R}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is the reward
function, and $\gamma\in(0,1)$ is a reward discount factor useful for
infinite-horizon problems. For analysis purposes, the state and action spaces
are assumed to be discrete. However, in the implementation and computer
simulations, we will illustrate the case in which the state space is
continuous. Moreover, $\mathcal{P}:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$
denotes the transition model, where the value $\mathcal{P}(s^{\prime}|s,a)$
denotes the probability of transitioning from state $s$ to state $s^{\prime}$
after taking action $a$.

Let $\pi(a|s)$ denote an arbitrary policy, which describes the likelihood of
selecting action $a$ at state $s$. Then, the state-action value associated
with an arbitrary pair $(s,a)$ is defined by

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

where the shorthand notation $r_{n}\triangleq r(s_{n},a_{n},s_{n+1})$
represents the reward that results from taking action $a_{n}$ at state
$s_{n}$, both at time $n$, and transitioning to state $s_{n+1}$. For
simplicity of notation, we denote the cardinalities of the respective sets by
the symbols $A\triangleq|\mathcal{A}|$, $S\triangleq|\mathcal{S}|$, and
$N_{k}\triangleq|\mathcal{N}_{k}|$.

###  III-A Single agent Q-learning

The framework proposed in this paper will build upon Q-learning, which is a
popular model-free, online, and off-policy RL scheme [19, 3]. The method is
model-free because its update rule does not depend on using either the
transition or reward functions of the MDP. The method is online because the
update rule depends on the current observations only, without the need for
data accumulation. More specifically, let us assume that at time instant $n$
an agent observes a transition from state $s$ to state $s^{\prime}$ under some
action $a$ and receives the reward $r(s,a,s^{\prime})$. Then, the state-action
value estimates $\widehat{Q}_{n+1}(s,a)$ are updated as follows [19, 3]:

$\displaystyle\widehat{Q}_{n+1}(s,a)=$ $\displaystyle\ \widehat{Q}_{n}(s,a)$
$\displaystyle+\alpha_{n}(s,a)\delta_{n}(s,a)\mathbb{I}(s=s_{n}\text{ and
}a=a_{n}),$ (2)

where $\alpha_{n}(s,a)$ is the learning rate,

$\delta_{n}(s,a)=r_{n}+\gamma\max\limits_{b\in\mathcal{A}}\widehat{Q}_{n}(s^{\prime},b)-\widehat{Q}_{n}(s,a),$

and $\mathbb{I}(\cdot)$ is the indicator function that is defined as

$\mathbb{I}(\mathcal{B})=\begin{cases}1,&\text{if }\mathcal{B}\text{ is
true}\\\ 0,&\text{ otherwise}\end{cases}$

The objective of Q-learning is to use the estimated state-action values in
order to determine an approximate optimal policy $\pi^{\star}$ that maximizes
(1). Although, the objective is to estimate $Q^{\pi^{\star}}$ under the
optimal policy, one of the main features of Q-learning is that data can be
collected under any other policy $\eta$, called a behavioral policy. This off-
policy nature of Q-learning is convenient for developing an exploration
strategy.

Now, most convergence proofs for Q-learning are based on the assumption that
all states and actions are visited infinitely often [20, 21]. In other words,
when the behavioral policies do not guarantee sufficient exploration of the
state-action space, then Q-learning will not necessarily converge. In this
work, we will design a behavioral policy that ensures that all states and
actions are visited infinitely often by leveraging cooperation among networked
agents.

##  IV Exploration Strategy

The proposed multi-agent algorithm will involve a distributed realization of
$K$ Q-learning schemes. Since we will be dealing with operations at multiple
agents, we will now need to attach an agent index $k$ to the main variables,
such as writing $r_{n}\to r_{k,n}$, $\widehat{Q}_{n}\to\widehat{Q}_{k,n}$. We
denote the history of transitions and rewards experienced by agent $k$ up to
time $n+1$ by

$\mathcal{H}_{k,n}\triangleq\left\\{s_{k,i},a_{k,i},r_{k,i}\right\\}_{i=0}^{n}.$
(3)

In the same token, we denote the aggregate history in the neighborhood of
agent $k$ by the notation

$\widetilde{\mathcal{H}}_{k,n}\triangleq\left\\{\mathcal{H}_{\ell,n}\right\\}_{\ell\in\mathcal{N}_{k}}.$
(4)

There is extensive discussion in the literature on the classical trade-off
between exploration and exploitation of the state-action space. However, no
clear measure of “sufficient exploration” exists. One popular measure is to
rely on the use of regret bounds. In this paper, we deviate from this
traditional view and establish “sufficiency” of exploration by relying on the
ability of the behavioral policy to ensure “infinitely often visitations of
all states and actions”. To this end, we will first introduce the design of
the behavioral policy.

The behavioral policy at every agent determines how the actions are selected
by that agent as it traverses the state space. In this work, we model the
behavioral policy at agent $k$ and time $n$ with the following Boltzman
distribution:

$\eta_{k,n}\left(a|s\right)=\frac{\exp\left(\beta_{k,n}(s)\widetilde{Q}_{k,n}(s,a)\right)}{\sum_{b\in\mathcal{A}}\exp\left(\beta_{k,n}(s)\widetilde{Q}_{k,n}(s,b)\right)},$
(5)

where the notation $\widetilde{Q}(s,a)$ refers to an adjusted version of the
estimated $Q$-value, namely,

$\widetilde{Q}(s,a)\triangleq\sigma_{k,n}(s,a)+\widehat{Q}_{k,n}(s,a).$

The bonus term $\sigma_{k,n}(s,a)$ is used to motivate agent $k$ to explore
not only rewarding states, but also states that have been visited less
frequently. Obviously, we want $\sigma_{k,n}$ to be inversely related to the
state-action visitation number: the less the state-action pair $(s,a)$ is
visited, the larger the value of $\sigma_{k,n}$ will be and the more the agent
will be motivated to revisit this location. However, we will require this
feature to be implemented without actual counting.

For this purpose, we will compute $\sigma_{k,n}(s,a)$ as a sample standard
deviation over the Q-value estimates available to agent $k$ from its
neighbours, i.e., $\\{\widehat{Q}_{\ell,n}(s,a),\ \ell\in\mathcal{N}_{k}\\}$.
More formally,

$\displaystyle\sigma_{k,n}^{2}(s,a)$
$\displaystyle\triangleq\frac{1}{N_{k}-1}\sum_{\ell\in\mathcal{N}_{k}}\left(\widehat{Q}_{\ell,n}(s,a)-\overline{Q}_{k,n}(s,a)\right)^{2},$
(6)

where

$\displaystyle\overline{Q}_{k,n}(s,a)$
$\displaystyle\triangleq\frac{1}{N_{k}}\sum\limits_{\ell\in\mathcal{N}_{k}}\widehat{Q}_{\ell,n}(s,a).$

Intuitively, when the state-action pair $(s,a)$ is insufficiently explored by
agent $k$, i.e., the visitation number is small or zero, the state-action
value estimates $\\{\widehat{Q}_{\ell,n},\ \ell\in\mathcal{N}_{k}\\}$ will
poorly agree with each other resulting in a large standard deviation
$\sigma_{k,n}(s,a)$. Repeated visitations drive the state-action values within
the neighborhood closer to each other and, therefore, the bonus term
$\sigma_{k,n}(s,a)$ will become smaller. The form of the exploration bonus in
(6) is inspired from the single-agent case [12].

The parameter $\beta_{k,n}$, which controls the shape of the Boltzman
distribution in (5), is explicitly defined as

$\beta_{k,n}(s)\triangleq\frac{1}{D(s)}\ln\log_{\alpha}\left[\frac{(\sigma_{q})^{2A}(N_{k})^{-A}}{\prod\limits_{b\in\mathcal{A}}\mathbb{E}\left[\sigma_{k,n}^{2}(s,b)|\widetilde{\mathcal{H}}_{k,n}\right]}\right]^{\oplus},$
(7)

where

$\sigma_{q}\triangleq\mathbb{V}(\widehat{Q}_{k,0}),\quad
D(s)\triangleq\max\limits_{a,b\in\mathcal{A}}\left|\widetilde{Q}_{t}\left(s,a\right)-\widetilde{Q}_{t}(s,b)\right|,$
(8)

$0<\alpha\leq 1/4$, and the operator $[\cdot]^{\oplus}$ is defined by:

$[\psi]^{\oplus}=\begin{cases}\psi,&\text{if }\psi\geq\alpha\\\ \alpha,&\text{
otherwise}.\end{cases}$

We remark that in (7) and all further equations, unless otherwise stated, we
will assume statistical operations such as expectation ($\mathbb{E}$),
variance ($\mathbb{V}$), and covariance ($\mathbb{C}\mathrm{ov}$) are, by
default, applied with respect to the initial state-action value estimates
available at the neighbourhood $\mathcal{N}_{k}$, i.e.,
$\left\\{\widehat{Q}_{\ell,0}(s,a),\ell\in\mathcal{N}_{k}\right\\},\forall
s\in\mathcal{S},a\in\mathcal{A}$.

The above choice of $\beta_{k,n}$ allows us to guarantee the convergence of
the proposed algorithm, as will become clear when we discuss Theorem 1. Note
that the behavioral policies of the agents are based solely on local
information from their neighborhoods. This fact and the assumption that
actions are decoupled imply that the exploration process in our algorithm
takes place in a fully decentralized manner.

Due to the expectation operator, we cannot implement (7) in its exact form. To
this end, we use the unbiased approximation:

$\mathbb{E}\left[\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n}\right]\approx\sigma_{k,n}^{2}(s,a)$
(9)

whose accuracy is evaluated in Lemma 1. Therefore, we arrive at the following
listing for the Graph Exploration Algorithm (GEA) under Q-learning.

Initialize $\widehat{Q}_{k,0}(s,a)\sim\mathcal{M}$, $\forall
k\in\mathcal{K},s\in\mathcal{S},a\in{A}$;

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

for  _all $k\in\mathcal{K}$_ do

observe own and neighbours’ states
$\\{s_{\ell,n}\\}_{\ell\in\mathcal{N}_{k}}$;

receive $\widehat{Q}_{\ell,n}(s_{k,n},a_{k,n})$ from $\ell\in\mathcal{N}_{k}$;

compute $\sigma_{k,n}(s_{k,n},a)$, $\forall a\in\mathcal{A}$ using (6);

take action $a_{k,n}\sim\eta_{k,n}\left(a|s_{k,n}\right)$, given by (5);

observe $r_{k,n}$ and $s_{k,n+1}$;

compute
$\delta_{k,n}=r_{k,n}+\max\limits_{b\in\mathcal{A}}\widehat{Q}_{k,n}(s_{k,n+1},b)-\widehat{Q}_{k,n}(s_{k,n},a_{k,n})$;

update
$\widehat{Q}_{k,n+1}(s_{k,n},a_{k,n})=\widehat{Q}_{k,n}(s_{k,n},a_{k,n})+\alpha_{k,n}(s_{k,n},a_{k,n})\delta_{k,n}$;

end for

end for

Algorithm 1 Multi-agent $Q$-learning with cooperative exploration for discrete
state spaces (GEA).

###  IV-A Asymptotic behavior of $\eta_{k,n}$

In the sequel, we provide some well-known characteristics of the Boltzman
distribution that could be useful for further analysis and implementation. For
large $\beta_{k,n}$, the Boltzman distribution is equivalent to the greedy
policy [22], which can be expressed as:

$\lim\limits_{\beta_{k,n}\to\infty}\eta_{k,n}=\arg\max\limits_{a\in\mathcal{A}}\widetilde{Q}_{k,n}(s_{k,n},a)$
(10)

From (7), it can be observed that $\beta_{k,n}$ approaches infinity when the
estimate uncertainties tend to zero. Since the uncertainties are expected to
vanish with the evolution of Q-learning, the limit in (10) can be rewritten
as:

$\eta_{k,\infty}\triangleq\lim\limits_{n\to\infty}\eta_{k,n}=\arg\max\limits_{a\in\mathcal{A}}\lim\limits_{n\to\infty}\widetilde{Q}_{k,n}(s_{k,n},a)$
(11)

In contrast, when $\beta_{k,n}$ is zero, actions are selected uniformly at
random.

##  V Analysis and Discussions

Most exploration algorithms lack theoretical guarantees, and the ones with
theoretical results mainly rely on counting approaches. Theorem 1 states our
first main contribution, where we guarantee convergence to the optimal policy
under the proposed exploration mechanism. First, we list some common
assumptions.

######  Assumption 1 (Learning rate).

Learning step sizes $\alpha_{k,n}(s,a)$, for all states $s\in\mathcal{S}$,
actions $a\in\mathcal{A}$, and agents $k\in\mathcal{K}$, satisfy

$\displaystyle\sum\limits_{n=0}^{\infty}\alpha_{k,n}(s,a)=\infty,\quad\quad\sum\limits_{n=0}^{\infty}\alpha_{k,n}^{2}(s,a)<\infty.$

######  Assumption 2 (Initialization of Q-values).

Q-value estimates for all agents $k\in\mathcal{K}$ are initialized
independently according to some distribution $\mathcal{M}$ with bounded
support, i.e., $Q_{k,0}(s,a)<\infty$, and
$\mathbb{E}\left[Q_{k,0}(s,a)\right]=0$, $s\in\mathcal{S},a\in\mathcal{A}$.

######  Assumption 3 (Transition probability).

For any two subsets $\mathcal{S}_{1}\in\mathcal{S}$ and
$\mathcal{S}_{2}\in\mathcal{S}$, there exist states $s_{1}\in\mathcal{S}_{1}$,
$s_{2}\in\mathcal{S}_{2}$ and action $a\in\mathcal{A}$ such that
$\mathcal{P}(s_{2}|s_{1},a)>0$.

######  Assumption 4 (Rewards).

We assume that rewards are bounded, say, as $r_{\min}\leq
R\left(s,a,s^{\prime}\right)\leq r_{\max},\forall s,s^{\prime}\in\mathcal{S}$
and $\forall a\in\mathcal{A}$.

$\square$

Assumption 3 implies that any state in the MDP can be reached from any other
state in a finite number of transitions. This assumption is required to ensure
that all states are visited infinitely often.

######  Theorem 1 (Convergence to the optimal policy).

Consider a discrete MDP with finite action and state spaces. Under Assumptions
$1$-$4$, and under the exact construction (7) for $\beta_{k,n}(s)$, the graph
exploration algorithm converges to the optimal policy $\pi^{\star}$ that
maximizes (1).

###### Proof.

See Appendix A. In the proof, we extend arguments used for traditional
Q-learning, but omit the common assumption that all states and actions are
visited infinitely often. This is because the argument in the appendix shows
that this property is guaranteed by the proposed exploration policy.

∎

As already mentioned in (9), the implementation of the algorithm replaces the
expectation appearing in (7) by the sample approximation $\sigma_{k,n}^{2}$.
When $\widetilde{H}_{k,n}$ is given, randomness in $\sigma_{k,n}^{2}$ is only
due to the random initialization of the Q-estimates. Therefore, with the
evolution of the Q-learning algorithm, the effect of the random
initializations diminishes bringing the approximation and the exact value
closer to each other. Lemma 1 provides the asymptotic rate of convergence for
the approximation error.

######  Lemma 1 (Assymptotic approximation error).

Let $p_{k}(s,a)$ denote state-action visitation probabilities induced by the
asymptotic behavioral policy $\eta_{k,\infty}(a|s)$ (11), defined in (11).
Also let

$\displaystyle p_{\min}$
$\displaystyle\triangleq\min\limits_{k\in\mathcal{K},s\in\mathcal{S},a\in\mathcal{A}}p_{k}(s,a),$
(12) $\displaystyle p_{\max}$
$\displaystyle\triangleq\max\limits_{k\in\mathcal{K},s\in\mathcal{S},a\in\mathcal{A}}p_{k}(s,a).$
(13)

Then, for all states $s\in\mathcal{S}$, actions $a\in\mathcal{A}$, agents
$k\in\mathcal{K}$ and $n\to\infty$, with at least probability
$(1-p_{\epsilon})$, it holds that

$\Bigl{|}\sigma_{k,n}^{2}-\mathbb{E}\left(\left.\sigma_{k,n}^{2}\right|\widetilde{\mathcal{H}}_{k,n}\right)\Bigr{|}\leq\frac{B^{\prime}N_{k}}{(N_{k}-1)p_{\epsilon}}\left(\frac{1}{n}\right)^{\frac{2p_{\min}}{p_{\max}}\gamma},$
(14)

where $0<B^{\prime}<\infty$.

###### Proof.

See Appendix B. ∎

Note that the bound in (14) depends on the probabilities of visitations
$p_{k}(s,a)$, which are dictated by the behavioral policies
$\eta_{k,\infty}(a|s)$. Since the proposed behavioral policy is designed to
ensure infinitely often visitation of all states and actions it is reasonable
to assume that the $p_{k}(s,a)$ values are strictly positive.

The bound in (14) is asymptotic since a finite-time analysis of standard
Q-learning is in itself a challenging problem [23, 24]. For environments that
are highly sensitive to the approximation error and require that the error on
the left-hand side of ((14)) be well-bounded in finite time, a possible
solution is averaging over multiple realizations. Namely, agents can learn and
share multiple Q-estimates using Q-learning bootstrapping methods[12, 25, 26]
and use these estimates to generate multiple realizations of
$\sigma_{k,n}^{2}$, which, in turn, are averaged to have a better
approximation for
$\mathbb{E}(\sigma_{k,n}^{2}|\widetilde{\mathcal{H}}_{k,n})$. Then, the
approximation error will scale inversely proportional to the number of per
agent Q-estimates, by central limit theorem.

(a) Discrete states

(b) Continuous states

Figure 1: Diagram showing the information exchanged with neighbors of agent
$k$ considering a discrete-state scenario (a) and a continuous-state scenario
(b).

###  V-A Continuous states and function approximation

Until now, all discussions assumed that the state space $\mathcal{S}$ is
countable. However, since the proposed graph exploration algorithm does not
require counting, it is particularly suitable for continuous state spaces as
well. In the sequel, we explain how the implementation of the graph
exploration algorithm changes for continuous-state problems.

For continuous states, a tabular Q-learning is not an option since agents
cannot generally deal with an infinite number of state-action values
corresponding to the infinite number of states. However, we can assume that
there exists a generalization model $Q_{v}$ that can approximate the relation
between any state-actions and their optimal state-action values, i.e.:

$Q^{\pi^{\star}}(s,a)\approx Q_{v}(f(s,a);v^{\star}),$

where $f(s,a)\in\mathbb{R}^{d}$ denotes a feature vector representing the
state-action $(s,a)$ and $v^{\star}$ is some parameter vector for the
approximation function. By learning only $v^{\star}$, the optimal state-action
values can be rebuilt according to $Q_{v}$, for any states and actions, even
if they are continuous.

Therefore, in Q-learning with function approximations, instead of the optimal
Q-values, agents learn the corresponding optimal parameter vectors
$v^{\star}$. The optimal parameter estimates $v_{k,n}$ are updated similar to
(III-A), except that the learning step, in addition, is multiplied by the
gradient of the approximation function:

$v_{k,n+1}=v_{k,n}+\alpha_{k,n}(s_{k,n},a_{k,n})\delta_{k,n}\nabla_{v}Q_{v}(f_{k,n};v_{k,n})$

where for simplicity of notation we let $f_{k,n}\triangleq
f(s_{k,n},a_{k,n})$. These parameters are further shared with neighbours in
order to compute the state-action value estimates using the approximation
$\widehat{Q}_{\ell,n}(s,a)\approx Q_{v}(f(s,a);v_{k})$, which, in turn, are
used to compute exploration policies given in (5).

Apart from allowing continuous states, the use of the approximation model
significantly unloads the communication process among agents. According to (6)
and (7), to compute $\beta_{k,n}(s)$ for the observed state $s_{k,n}$, agent
$k$ needs the estimates
$\\{\widehat{Q}_{\ell,k}(s_{k,n},a)\\}_{a\in\mathcal{A}}$, from all its
neighbours $\ell\in\mathcal{N}_{k}$. Therefore, for discrete states, agent $k$
receives in total $N_{k}A$ estimates. For continuous states, all estimates in
$\\{\widehat{Q}_{\ell,k}(s_{k,n},a)\\}_{a\in\mathcal{A}}$ can be computed
using a single parameter vector $v_{\ell,n}$, which reduces the total number
of received estimates to $N_{k}$. For visual explanation, see the example in
Fig. 1

Moreover, the use of approximations simplify the operational process. For the
discrete-state case, an agent needs to observe the states of all its
neighbours, use the Q-table to look for the estimates corresponding to the
observed states, and send the values to the corresponding neighbours.
Meanwhile, for the continuous-state case, an agent does not technically need
to observe other agents since it can simply broadcast a single parameter
$v_{k,n}$ to everyone nearby.

Initialize parameters $v_{k,0}$, $\forall k\in\mathcal{K}$;

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

for  _all $k\in\mathcal{K}$_ do

Observe own state $\\{s_{i,n}\\}_{i\in\mathcal{N}_{k}}$;

Receive $v_{j,n}$ from all neighbours $j\in\mathcal{N}_{k}$;

compute $\sigma_{k,n}(s_{k,n},a)$, $\forall a\in\mathcal{A}$ using (6) and the
approximation $\widehat{Q}_{k,n}(s,a)\approx Q_{v}(f(s,a);v_{k,n})$;

take action $a_{k,n}\sim\eta_{k,n}\left(a|s_{k,n}\right)$, given in (5);

observe $r_{k,n}$ and $s_{k,n+1}$ ;

compute
$\delta_{k,n}=r_{k,n}+\max\limits_{b\in\mathcal{A}}Q_{v}(f(s_{k,n+1},b);v_{k,n})-Q_{v}(f(s_{k,n},a_{k,n});v_{k,n})$;

update
$v_{k,n+1}=v_{k,n}+\alpha_{k,n}(s_{k,n},a_{k,n})\delta_{k,n}\nabla_{v}Q_{v}(f_{k,n};v_{k,n})$;

end for

end for

Algorithm 2 Multi-agent $Q$-learning with cooperative exploration for
continuous state spaces (GEA)

Finally, it is important that we make the following remark regarding
continuous state-space applications. Continuous state-space analysis is
usually non-tractable due to the use of neural networks. If we decide to focus
on the linear case for the sake of the theoretical analysis, there are
actually not many realistic examples whose environment can be linearly
modelled. Thus, by designing an algorithm based on the discrete state-space
case, while targeting continuous state-space games, we are implicitly assuming
that there is a correlation between discrete and continuous cases. The
algorithm, which converges under a discrete case analysis, should also work
for continuous case if a good approximation model is chosen. The choice of
approximation models and their evaluation is in itself a rich research topic,
which deserves future study. In our work, we focus on providing experimental
results that show the algorithm’s good performance under continuous-state
games.

##  VI Experimental Results

Figure 2: Diagram illustrating the deep sea game for a depth $H=3$ and the
action space $\mathcal{A}=\\{\text{RIGHT},\text{LEFT}\\}$. The arrows and
numerical values above them illustrate the game’s transition model and the
reward function, respectively.

(a) GEA vs GUCB.

(b) GEA vs MALSVI: original size.

(c) GEA vs MALSVI: zoom 1.

(d) GEA vs MALSVI: zoom 2.

Figure 3: Regret values for several implementations, including the proposed
GEA method, the discrete-state algorithm GUCB and the continuous-state
algorithm MALSVI under changing sparsity and discrete states: (a) compares the
proposed GEA and GUCB; (b) compares the proposed GEA and MALSVI including
results for all selected depth values; (c) compares the proposed GEA and
MALSVI zooming into regions where the performance of GEA is visible for
$\operatorname{depth}=12$ and $\operatorname{depth}=14$; (d) compares the
proposed GEA and MALSVI zooming into regions where the performance of GEA is
visible for $\operatorname{depth}=10$ and $\operatorname{depth}=14$.

Performance of the proposed algorithm was tested on the deep sea environment.
Deep sea, illustrated in Fig. 2, is a challenging sparse reward environment
where a positive reward can be achieved with one policy out of $2^{H}$
possible ones, where $H$ is the length of an episode. Moreover, a deep sea
player is deceived with negative rewards for steps taken toward the optimal
path.

Following a common strategy in literature, the performance of the algorithm
was tested based on the regret, which is formally defined in Definition 1. A
bounded regret means that the behavioral policies of all agents can converge
to the optimal one in finite time. The regret value at the convergence time
shows how mistakenly agents have behaved before converging to the optimal
solution. Also, in our simulations, we vary the length of the game $H$ to see
how the algorithm behaves with the changing sparsity. The relation between
sparsity of the environment and $H$ is direct: “the deeper” ($H\uparrow$) the
game is the further the agents start from the most rewarding state and the
more paths with deceiving rewards will appear (sparsity $\uparrow$).

######  Definition 1 (Regret expression).

The regret at time instant $T$, for finite MDP with initial state $s_{k,0}$
for agent $k$, is given by

$\text{Regret}(T)=\frac{1}{K}\sum_{n=1}^{T}\sum_{k=1}^{K}\left(V^{\pi^{\star}}\left(s_{k,0}\right)-V^{\eta_{k,n}}\left(s_{k,0}\right)\right),$
(15)

where $\pi^{*}$ is an optimal policy, which maximizes the expected total
return of the game, $\eta_{k,n}$ is an actual policy followed by an agent at
the $n$-th episode, and, under policy $\pi$, the state value $V^{\pi}(s)$ is
defined as

$\displaystyle
V^{\pi}\left(s\right)\triangleq\mathbb{E}\left(\sum\limits_{n=0}^{\infty}\gamma^{n}r_{n}|s_{0}=s\right).$

$\square$

In our illustrations, for better visualization, we duplicate the results by
zooming over poorly-visible regions. Precisely, Fig 3b is an original-size
figure with regret plots for the proposed GEA and the MALSVI algorithm across
all selected depth values, while Fig. 3c and Fig 3d zoom into regions where
the performance of GEA is visible for specific depth values. In particular,
Fig.3c focuses on the performance of GEA for $\operatorname{depth}=12$ and
$\operatorname{depth}=14$, while Fig.3d focuses on the performance of GEA for
$\operatorname{depth}=10$ and $\operatorname{depth}=14$.

Our algorithm is first compared with the GUCB approach, which is designed for
discrete-state environments only. GUCB is limited for discrete-state cases
only because its exploration bonus depends on the counting of state-action
visitation frequencies:

$b^{\text{\tiny{GUCB}}}_{k,n}(s,a)\triangleq\beta\sqrt{\frac{H^{3}\iota}{w_{k}c_{k,n}(s,a)}}$
(16)

where $\beta>0$ is a constant, $c_{k,n}(s,a)$ denotes the visitation frequency
of state-action $(s,a)$ by agent $k$ before time $n$, $w_{k}$ is a fixed
parameter that depends on the structure of the graph, and $\iota$ is a fixed
parameter that depends on the properties of the MDP. From Fig. 3a, we can see
that GUCB outperforms the proposed GEA algorithm in terms of total regret for
all depth values. This outcome is anticipated, as counting confers an
advantage to algorithms in accurately quantifying the uncertainty associated
with states and actions. However, counting-based approaches limit the states
to be discrete, which reduces the range of applicable problems. Therefore, we
posit that the incurred disadvantage in terms of total regret is a reasonable
compromise for adopting a non-counting-based approach in the proposed
algorithm.

Furthermore, it is imperative to not only assess the point of convergence of
regret, but also the rate of convergence. Specifically, while an approach may
achieve convergence to the optimal solution by exploring various sub-optimal
paths, the time taken to achieve such convergence holds considerable
significance. Given that the proposed bonus exhibits a higher level of
stochasticity in comparison to traditional count-based mechanisms, it may
potentially result in the selection of paths with elevated regret values.
However, in terms of convergence time, our algorithm can be evaluated as
relatively competitive when compared to the GUCB approach.

Our algorithm is also compared with MALSVI, which allows states to be
continuous under the assumption that the model is linear:

$Q^{\pi^{\star}}\approx f^{T}(s,a)v^{\star}.$

MALSVI belongs to a different class of RL algorithms, where, instead of
Q-learning, the Least-Squares Value Iteration (LSVI) method is employed. In
LSVI approaches, optimal state-action values are estimated by solving
iteratively a certain regularized least-squares regression. The exploration
bonus in MALSVI is not directly related to the state-action visitation
frequencies. It is rather designed with intention to overestimate Q-values.
This technique, called optimism in the face of uncertainty, is a common
strategy for bounding the regret analytically. The regret-based analysis in
MALSVI guarantees convergence of the algorithm to the optimal solution but
does not ensure that it will be reached in the most efficient way. That is why
the experimental results illustrated in Fig. 3 show that the proposed scheme
outperforms MALSVI, in terms of the regret. Moreover, as it was mentioned
earlier, the operation of MALSVI requires that all agents are fully connected
at certain instances. In particular, agents individually solve their own local
LSVI and when a certain condition is met they need to synchronize their
results. Thus, MALSVI assumes more restricted network structure compared to
the proposed algorithm.

##  VII Conclusion

To sum up, we propose an MARL exploration strategy that can be used for both
continuous and discrete-state environments. We provide theoretical guarantees
for discrete-state scenarios, and simulation results for the continuous-state
ones. We consider a specific model of multi-agent learning where agents
receive only individual rewards independent from actions of others. Therefore,
the first extension for this work would be to consider MARL scenarios with
joint actions and rewards. Second, one can extend the work by finding better
approximations for the conditional expectation of sample variances. It is also
useful to study the scenario with partially observable states and employ
cooperation of agents for estimation of states as well.

##  Appendix A Proof of Theorem 1

######  Lemma 2.

Under Assumption 2, the variance of $Q_{k,n}(s,a)$, conditioned on the history
$\mathcal{H}_{k,n}$, is bounded as

$\mathbb{V}(Q_{k,n}(s,a)|\mathcal{H}_{k,n})\geq(\alpha)^{2c_{k,n}(s,a)}\sigma_{q}^{2},\
\forall k\in\mathcal{K},$ (17)

where $0<\alpha\leq 1/4$ and $c_{k,n}(s,a)$ is the number of times a state-
action pair $(s,a)$ is visited by agent $k$ by the time $n$.

###### Proof.

Let $\alpha_{i}\triangleq\alpha_{n_{i},k}(s,a)$ denote the step size at time
instant $n_{i}\triangleq n_{i}(s,a,k)$ when agent $k$ visits the state-action
pair $(s,a)$ for the $i$-th time. For compactness, from here on, we
interchangeably use the following notations:

$\displaystyle t\triangleq
c_{k,n}(s,a),\quad\quad\widehat{b}_{k,n}\triangleq\arg\max\limits_{b\in\mathcal{A}}\widehat{Q}_{k,n}(s_{k,n+1},b),$
(18) $\displaystyle x_{k,n}\triangleq(s_{k,n},a_{k,n}),\quad
y_{k,n}\triangleq(s_{k,n},\widehat{b}_{k,n}).$ (19)

The Q-learning update rule in (III-A) leads to

$\displaystyle\widehat{Q}_{k,n}(x_{k,n})=\alpha_{0}^{t}\widehat{Q}_{k,0}(x_{k,n})$
$\displaystyle+\sum_{i=1}^{t}\alpha_{t}^{i}\left(r(x_{k,n_{i}},s_{k,n_{i}+1})+\gamma\widehat{Q}_{k,n}(y_{k,n_{i}})\right),$
(20)

where

$\alpha_{t}^{0}=\prod_{j=1}^{t}\left(1-\alpha_{j}\right),\quad\alpha_{t}^{i}=\alpha_{i}\prod_{j=i+1}^{t}\left(1-\alpha_{j}\right).$
(21)

Therefore, at the next steps, we will lowerbound
$\mathbb{V}(Q_{k,n}(s,a)|\mathcal{H}_{k,n})$ by applying the conditional
variance to the left-hand side of (A). First, using (A) and the variance
property
$\mathbb{V}(X+Y)=\mathbb{V}(X)+\mathbb{V}(Y)+2\operatorname{Cov}(X,Y)$, we
have

$\displaystyle\mathbb{V}\left(Q_{k,n}|\mathcal{H}_{k,n}\right)=\mathbb{V}\left[\alpha_{0}^{t}\widehat{Q}_{k,0}(x_{k,n})\right.$
$\displaystyle\left.\left.+\sum_{i=1}^{t}\alpha_{t}^{i}\left(r(x_{k,n_{i}},s_{k,n_{i}})+\widehat{Q}_{k,n}(y_{k,n_{i}})\right)\right|\mathcal{H}_{k,n}\right]$
$\displaystyle=(\alpha_{0}^{t})^{2}\sigma_{q}^{2}$
$\displaystyle+\sum_{i=1}^{t}(\alpha_{t}^{i})^{2}\mathbb{V}\left.\left(r(x_{k,n_{i}},s_{k,n_{i}})+\gamma^{2}\widehat{Q}_{k,n}(y_{k,n_{i}})\right|\mathcal{H}_{k,n}\right)$
$\displaystyle+2\sum_{i=1}^{t}\alpha_{t}^{i}\gamma\operatorname{Cov}\left.\left(\alpha_{0}^{t}\widehat{Q}_{k,0}(x_{k,n}),\widehat{Q}_{k,n}(y_{k,n_{i}}))\right|\mathcal{H}_{k,n}\right)$
$\displaystyle+2\sum_{i=1}^{t}\alpha_{t}^{i}\operatorname{Cov}\left.\left(\alpha_{0}^{t}\widehat{Q}_{k,0}(x_{k,n}),r(x_{n_{i}},s_{k,n_{i}+1}))\right|\mathcal{H}_{k,n}\right).$
(22)

The second term in (A) is non-negative by definition of the variance. The
third term can be expanded using the definition of covariance and lower-
bounded as follows

$\displaystyle\operatorname{Cov}\left(\left.\widehat{Q}_{k,0}(x_{k,n})\widehat{Q}_{k,n}(y_{k,n_{i}})\right|\mathcal{H}_{k,n}\right)$
$\displaystyle=\mathbb{E}\left(\left.\widehat{Q}_{k,0}(x_{k,n})\widehat{Q}_{k,n}(y_{k,n_{i}})\right|\mathcal{H}_{k,n}\right)$
$\displaystyle-\mathbb{E}\left(\left.\widehat{Q}_{k,0}(x_{k,n})\right|\mathcal{H}_{k,n}\right)\mathbb{E}\left(\left.\widehat{Q}(y_{k,n_{i}})\right|\mathcal{H}_{k,n}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{=}}\mathbb{E}\left(\left.\widehat{Q}_{k,0}(x_{k,n})\widehat{Q}_{k,n}(y_{k,n_{i}})\right|\mathcal{H}_{k,n}\right)\stackrel{{\scriptstyle\text{(b)}}}{{\geq}}0$
(23)

where in (a) we use the assumption $\mathbb{E}(\widehat{Q}_{k,0})=0$
(Assumption 2) and (b) holds by Lemma 3 bellow.

As initialization of Q-values are assumed to be independent from the reward
function, the last term in (A) is zero.

Therefore, expression (A) can be lower bounded by
$(\alpha_{0}^{t}\sigma_{q})^{2}$. ∎

######  Lemma 3.

For all states $s,s^{\prime}\in\mathcal{S}$, all actions
$a,a^{\prime}\in\mathcal{A}$, and all agents $k\in\mathcal{K}$, under
Assumption 2, the following holds

$\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{k,n}(s^{\prime},a^{\prime})\right)\geq
0$ (24)

###### Proof.

We prove the lemma by induction. For $n=0$, $\forall
s,s^{\prime}\in\mathcal{S},\forall a,a^{\prime}\in\mathcal{A}$,

$\displaystyle\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{k,0}(s^{\prime},a^{\prime})\right)$
$\displaystyle=\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)^{2}\right)\mathbbm{1}[(s,a)=(s^{\prime},a^{\prime})]$
$\displaystyle+\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\right)\mathbb{E}\left(\widehat{Q}_{k,0}(s^{\prime},a^{\prime})\right)\mathbbm{1}[(s,a)\neq(s^{\prime},a^{\prime})]$
$\displaystyle=\sigma_{q}^{2}\mathbbm{1}\left[(s,a)=(s^{\prime},a^{\prime})\right]+0\geq
0,$ (25)

where in the last equality we used the assumption
$\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\right)=0$ (Assumption 2). Next, we
assume that (24) holds for $n=i$, i.e.,

$\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{k,i}(s^{\prime},a^{\prime})\right)\geq
0,\\\ \forall s,s^{\prime}\in\mathcal{S},\forall a,a^{\prime}\in\mathcal{A}.$
(26)

Then, for $n=i+1$, we have

$\displaystyle\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{i+1,k}(s,a)\right)\stackrel{{\scriptstyle\text{(a)}}}{{=}}$
$\displaystyle(1-\alpha_{k,i+1}(s^{\prime},a^{\prime}))\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{k,i}(s^{\prime},a^{\prime})\right)$
$\displaystyle+\alpha_{k,i+1}(s^{\prime},a^{\prime})\mathbb{E}\widehat{Q}_{k,0}(s,a)\mathbb{E}r(s^{\prime},a^{\prime},s^{\prime\prime})$
$\displaystyle+\alpha_{k,i+1}(s^{\prime},a^{\prime})\gamma\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\max\limits_{b\in\mathcal{A}}\widehat{Q}_{k,i}(s^{\prime\prime},b)\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(\ref{eq:induction})}}}{{\geq}}\alpha_{k,i+1}(s^{\prime},a^{\prime})\gamma\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\max\limits_{b\in\mathcal{A}}\widehat{Q}_{k,i}(s^{\prime\prime},b)\right)$
$\displaystyle\geq\alpha_{k,i+1}(s^{\prime},a^{\prime})\gamma\mathbb{E}\left(\widehat{Q}_{k,0}(s,a)\widehat{Q}_{k,i}(s^{\prime\prime},b^{\prime\prime})\right)$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{eq:induction}}}}{{\geq}}0$
(27)

where $b^{\prime\prime}\in\mathcal{A}$ and in (a) we use the multi-agent form
of the Q-learning update given in (III-A). ∎

######  Lemma 4.

For all states $s\in\mathcal{S}$, for all actions $a\in\mathcal{A}$ and for
all agents $k\in\mathcal{K}$,

$\mathbb{E}(\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n})\geq\frac{\alpha^{c_{k,n}(s,a)}}{N_{k}}\sigma_{q}^{2},\
\forall k\in\mathcal{K}$ (28)

###### Proof.

From (A) we deduce that, when $\widetilde{\mathcal{H}}_{k,n}$ is given,
$\left\\{\widehat{Q}_{\ell,n}\right\\}_{j\in\mathcal{K}}$ are independent but
not identically distributed random variables. Therefore, using the definition
of expected sample variance for independent random variables, we get

$\displaystyle\mathbb{E}(\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n})=\frac{1}{N_{k}}\sum\limits_{\ell\in\mathcal{N}_{k}}\mathbb{V}\left(\widehat{Q}_{\ell,n}(s,a)\left.\right|\mathcal{H}_{k,n}\right)$
$\displaystyle+\frac{1}{N_{k}-1}\sum\limits_{\ell\in\mathcal{N}_{k}}\left[E(\widehat{Q}_{\ell,n}(s,a)|\mathcal{H}_{\ell,n})\right]^{2}$
$\displaystyle-\frac{1}{N_{k}(N_{k}-1)}\left[\sum\limits_{j\in\mathcal{N}_{k}}\mathbb{E}\left[\left.\widehat{Q}_{\ell,n}(s,a)\right|\mathcal{H}_{\ell,n}\right)\right]^{2}.$
(29)

By Cauchy-Schwartz inequality, we have

$\displaystyle\left[\sum\limits_{j\in\mathcal{N}_{k}}\mathbb{E}\left(\left.\widehat{Q}_{\ell,n}\right|\mathcal{H}_{\ell,n}\right)\right]^{2}\leq
N_{k}\sum\limits_{\ell\in\mathcal{N}_{k}}\left[E(\widehat{Q}_{\ell,n}|\mathcal{H}_{\ell,n})\right]^{2}.$
(30)

Therefore, substituting (30) into (A), we obtain that, $\forall
k\in\mathcal{K}$, $s\in\mathcal{S}$, $a\in\mathcal{A}$:

$\displaystyle\mathbb{E}(\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n})$
$\displaystyle\geq\frac{1}{N_{k}}\sum\limits_{\ell\in\mathcal{N}_{k}}\mathbb{V}\left(\widehat{Q}_{\ell,n}(s,a)\left.\right|\mathcal{H}_{\ell,n}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{(a)}}}{{\geq}}\frac{1}{N_{k}}\sum\limits_{\ell\in\mathcal{N}_{k}}\alpha^{c_{k,n}(s,a)}\sigma_{q}^{2}$
$\displaystyle\geq\frac{\alpha^{c_{k,n}(s,a)}}{N_{k}}\sigma_{q}^{2}$ (31)

where (a) is due to Lemma 2. ∎

###### Proof of Theorem 1.

Update rules of the form (III-A) is known to converge to the optimal Q-values
given that all state-action pairs are visited infinitely often (i.o.) [3, 20].
Therefore, to prove that all agents in the proposed scheme converge to the
optimal Q-values we need to show that the behavioral policies $\eta_{k,n}$
make all agents to visit all state-action pairs i.o.

According to Lemma 4 from [22], all states and actions are visited i.o. if

  1. (i)

Assumption 3 holds

  2. (ii)

The behavioral policy $\eta_{k,n}$ is such that, $\forall
k\in\mathcal{K},\forall s\in\mathcal{S},\forall a\in\mathcal{A}$,

$\sum\limits_{j=0}^{\infty}\eta_{k,m_{j}}(a|s)=\infty,$

where $m_{j}\triangleq m_{j}(s,k)$ is the time instance when the state $s$ is
visited by agent $k$ for the $j$-th time.

Since (i) is taken as an assumption in the theorem, the proof of Theorem 1
requires that we prove that (ii) holds. Recall that our behavioral policy is
given in the Boltzmann distribution form (3), namely,

$\eta_{k,n}\left(a|s\right)=\frac{\exp\left(\widetilde{\beta}_{k,n}(s)\widetilde{Q}_{k,n}(s,a)\right)}{\sum_{b\in\mathcal{A}}\exp\left(\widetilde{\beta}_{k,n}(s)\widetilde{Q}_{k,n}(s,b)\right)}.$
(32)

We first derive the condition for the Boltzman probability density function
with generic $\widetilde{\beta}_{k,n}$ (32) in order to ensure that (ii)
holds. We know that $\sum\limits_{i=1}^{\infty}1/i=\infty$. Due to Assumption
3, the number of visitations of state $s$ by agent $k$, denoted by
$c_{k,n}(s)$, goes to infinity (see proof of Lemma 4 in [22]). Therefore, we
can add the following constraint for the behavioral policy:

$\eta_{k,n}\left(a|s\right)=\frac{\exp\left(\widetilde{\beta}_{k,n}(s)\widetilde{Q}_{k,n}(s,a)\right)}{\sum_{b\in\mathcal{A}}\exp\left(\widetilde{\beta}_{k,n}(s)\widetilde{Q}_{k,n}(s,b)\right)}\geq\frac{C^{\prime}}{c_{k,n}(s)},$
(33)

where $C^{\prime}>0$ is a constant. In the following, using (33) and some
basic algebraic manipulations, we derive the condition for $\beta_{k,n}$ to
satisfy (ii). We can rewrite (33) as

$\displaystyle c_{k,n}(s)$ $\displaystyle\geq C^{\prime}\sum_{b\in
A}e^{\widetilde{\beta}_{k,n}(s)(\widetilde{Q}_{k,n}(s,b)-\widetilde{Q}_{k,n}(s,a))}$
(34)

Next, taking the maximum of the lowerbound and letting $C^{\prime}=A^{-1}$ we
obtain

$\displaystyle c_{k,n}(s)$ $\displaystyle\geq
e^{\widetilde{\beta}_{k,n}(s)D(s)},$

where $D(s)=\max\limits_{a,b}(\widetilde{Q}(s,b)-\widetilde{Q}(s,a))$. Hence,
we get that (ii) is satisfied if $\widetilde{\beta}_{k,n}$ is bounded
according to

$\widetilde{\beta}_{k,n}\leq\frac{\ln c_{k,n}(s)}{D(s)}$ (36)

Next, we show that $\widetilde{\beta}_{k,n}=\beta_{k,n}$, given by (7),
satisfies condition (36). We start with Lemma 4 which gives the lower bound
for $\mathbb{E}(\sigma_{k,n}^{2}|\mathcal{H}_{k,n})$, under Assumption 2:

$\displaystyle\mathbb{E}(\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n})\geq\frac{\alpha^{c_{k,n}(s,a)}\sigma_{q}^{2}}{N_{k}}$
(37)

In the following steps, we perform some algebraic manipulations to (37):

  1. Step 1.

Multiplication to $N_{k}$ and applying $\log_{\alpha}$:

$\displaystyle\log\limits_{\alpha}N_{k}\mathbb{E}(\sigma_{k,n}^{2}|\widetilde{\mathcal{H}}_{k,n})\leq
c_{k,n}(s,a)+\log\limits_{\alpha}\sigma_{q}^{2}$ (38)

  2. Step 2.

Subtracting $\log\limits_{\alpha}\sigma_{q}^{2}$ and summing over all possible
actions:

$\displaystyle\sum\limits_{a\in\mathcal{A}}\log\limits_{\alpha}\frac{N_{k}\mathbb{E}(\sigma_{k,n}^{2}(s,a)|\widetilde{\mathcal{H}}_{k,n})}{\sigma_{q}^{2}}\leq
c_{k,n}(s)$ (39)

where by definition

$c_{k,n}(s)\triangleq\sum\limits_{a\in\mathcal{A}}c_{k,n}(s,a),$ (40)

  3. Step 3.

Applying $\ln$:

$\displaystyle\ln\left(\log_{\alpha}\frac{(\sigma_{q})^{2A}(N_{k})^{-A}}{\prod\limits_{b\in\mathcal{A}}\mathbb{E}\left[\sigma_{k,n}^{2}(s,b)|\widetilde{\mathcal{H}}_{k,n}\right]}\right)\leq\ln
c_{k,n}(s)$ (41)

Finally, dividing both sides of (41) by $D(s)$, we show that, by choosing
$\widetilde{\beta}_{k,n}=\beta_{k,n}$, we satisfy (36) and moreover we satisfy
(ii).

∎

##  Appendix B Proof of Lemma 1

######  Lemma 5 (Asymptotic convergence rate of Q-learning [27]).

Let

$e_{k,n}(s,a)\triangleq\left(\widehat{Q}_{k,n}(s,a)-Q^{*}(s,a)\right).$

Then, for all agents $k\in\mathcal{K}$, all states $s\in\mathcal{S}$, all
actions $a\in\mathcal{A}$ and $n\to\infty$, we have

$\displaystyle
e_{k,n}(s,a)\leq\left(\frac{1}{n}\right)^{\frac{p_{k,\min}}{p_{k,\max}}\gamma}B,$
(42)

where $p_{k}(s,a)$ denotes state-action visitation probabilities induced by
some stationary policy $\eta_{k,\infty}(a|s)$, $B>0$ is some constant,
$p_{k,\max}=\max\limits_{s,a}p_{k}(s,a)$,
$p_{k,\min}=\min\limits_{s,a}p_{k}(s,a)$.

###### Proof.

See [27]. ∎

###### Proof of Lemma 1.

Using Chebyshev’s inequality, we have that for $\epsilon>0$,

$\displaystyle\mathbb{P}\left[\left(\left.|\sigma_{k,n}^{2}-\mathbb{E}(\sigma_{k,n}^{2}|\widetilde{\mathcal{H}}_{k,n})|\geq\epsilon\right)\right|\mathcal{H}_{k,n}\right]\leq\frac{\mathbb{V}(\left.\sigma_{k,n}^{2}\right|\mathcal{H}_{k,n})}{\epsilon^{2}}.$
(43)

When $\widetilde{\mathcal{H}}_{k,n}$ is given, the estimates
$\left\\{\widehat{Q}_{\ell,n}\right\\}_{\ell\in\mathcal{N}_{k}}$ are
independent random variables. Let
$\mathcal{X}_{\ell}\triangleq\left(\widehat{Q}_{\ell,n}-\overline{Q}_{k,n}\right)^{2}$.
Then, computing the variance of the sum, we get

$\displaystyle\mathbb{V}(\left.\sigma_{k,n}^{2}\right|\widetilde{\mathcal{H}}_{k,n})$
$\displaystyle=\frac{\sum\limits_{\ell\in\mathcal{N}_{k}}\mathbb{V}\left(\left.\mathcal{X}_{\ell}\right|\widetilde{\mathcal{H}}_{k,n}\right)}{(N_{k}-1)^{2}}$
$\displaystyle+\sum\limits_{\begin{subarray}{c}\ell,j\in\mathcal{N}_{k}\\\
\ell\neq
j\end{subarray}}\frac{\operatorname{Cov}(\left.\mathcal{X}_{\ell},\mathcal{X}_{j}\right|\widetilde{\mathcal{H}}_{k,n})}{(N_{k}-1)^{2}}$
$\displaystyle\stackrel{{\scriptstyle\textnormal{(a)}}}{{\leq}}\sum\limits_{\ell\in\mathcal{N}_{k}}\frac{\mathbb{E}\left[\left.\left(\mathcal{X}_{\ell}\right)^{2}\right|\widetilde{\mathcal{H}}_{k,n}\right]}{(N_{k}-1)^{2}}$
$\displaystyle+\sum\limits_{\begin{subarray}{c}\ell,j\in\mathcal{N}_{k}\\\
j\neq
i\end{subarray}}\frac{\mathbb{E}\left[\left.\mathcal{X}_{\ell}\mathcal{X}_{j}\right|\widetilde{\mathcal{H}}_{k,n}\right]}{(N_{k}-1)^{2}},$
(44)

where in (a) we used the statistical properties that for any random variable
$X$, $\mathbb{V}X\leq\mathbb{E}X^{2}$ and, for any $Y\geq 0,Z\geq 0$,
$\operatorname{Cov}(Y,Z)\leq\mathbb{E}[YZ]$.

Next, using Lemma 5, we have

$\displaystyle\sqrt{\mathcal{X}_{\ell}}\triangleq|\widehat{Q}_{\ell,n}(s,a)-\overline{Q}_{k,n}(s,a)|$
$\displaystyle\leq|\widehat{Q}_{\ell,n}(s,a)-Q^{*}(s,a)|+|Q^{*}(s,a)-\overline{Q}_{k,n}|$
$\displaystyle\leq\left(\frac{1}{n}\right)^{\frac{p_{k,\min}}{p_{k,\max}}\gamma}B+\frac{1}{N_{k}}\sum\limits_{i\in\mathcal{N}_{k}}\left(\frac{1}{n}\right)^{\frac{p_{k,\min}}{p_{k,\max}}\gamma}B$
$\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{\leq}}\left(\frac{1}{n}\right)^{\frac{p_{\min}}{p_{\max}}\gamma}B,$

where in $(a)$ we use the relation

$\left(\frac{1}{n}\right)^{\frac{p_{k,\min}}{p_{k,\max}}}\leq\left(\frac{1}{n}\right)^{\frac{p_{\min}}{p_{\max}}},\
\forall k\in\mathcal{N}_{k}.$

Substituting (B) into (B), we get

$\displaystyle\mathbb{V}(\left.\sigma_{k,n}^{2}\right|\widetilde{\mathcal{H}}_{k,n})$
$\displaystyle\leq\frac{N_{k}}{(N_{k}-1)^{2}}\left(\frac{1}{n}\right)^{\frac{4p_{\min}}{p_{\max}}\gamma}(B)^{4}$
$\displaystyle+\frac{N_{k}(Nk-1)}{(N_{k}-1)^{2}}\left(\frac{1}{n}\right)^{\frac{4p_{\min}}{p_{\max}}\gamma}(B)^{4},$
$\displaystyle=\frac{N_{k}^{2}}{(N_{k}-1)^{2}}\left(\frac{1}{n}\right)^{\frac{4p_{\min}}{p_{\max}}\gamma}(B)^{4}$
(46)

Finally, substituting (B) into (43) and setting $B^{\prime}\triangleq B^{2}$

$\epsilon=\frac{B^{\prime}N_{k}}{(N_{k}-1)p_{\epsilon}}\left(\frac{1}{n}\right)^{\frac{2p_{\min}}{p_{\max}}\gamma},$

we get the result in (14). ∎

## References

  * [1] P. Ladosz, L. Weng, M. Kim, and H. Oh, “Exploration in deep reinforcement learning: A survey,” _Information Fusion_ , vol. 85, pp. 1–22, 2022.
  * [2] S. Amin, M. Gomrokchi, H. Satija, H. van Hoof, and D. Precup, “A survey of exploration methods in reinforcement learning,” 2021. [Online]. Available: https://arxiv.org/abs/2109.00157
  * [3] A. H. Sayed, _Inference and Learning from Data_. Cambridge University Press, 2022.
  * [4] T. Rashid, M. Samvelyan, C. S. De Witt, G. Farquhar, J. Foerster, and S. Whiteson, “Monotonic value function factorisation for deep multi-agent reinforcement learning,” _The Journal of Machine Learning Research_ , vol. 21, no. 1, jun 2022.
  * [5] T. Rashid, G. Farquhar, B. Peng, and S. Whiteson, “Weighted QMIX: expanding monotonic value function factorisation for deep multi-agent reinforcement learning,” in _Proc. International Conference on Neural Information Processing Systems (NeurIPS)_. Red Hook, NY, USA: Curran Associates Inc., 2020.
  * [6] J. Foerster, N. Nardelli, G. Farquhar, T. Afouras, P. H. S. Torr, P. Kohli, and S. Whiteson, “Stabilising experience replay for deep multi-agent reinforcement learning.” JMLR.org, 2017, p. 1146–1155.
  * [7] Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and J. Wang, “Mean field multi-agent reinforcement learning,” 2018. [Online]. Available: http://arxiv.org/abs/1802.05438
  * [8] L. Cassano and A. H. Sayed, “ISL: optimal policy learning with optimal exploration-exploitation trade-off,” 2019. [Online]. Available: http://arxiv.org/abs/1909.06293
  * [9] J. Lidard, U. Madhushani, and N. E. Leonard, “Provably efficient multi-agent reinforcement learning with fully decentralized communication,” 2021. [Online]. Available: https://arxiv.org/abs/2110.07392
  * [10] I.-J. Liu, U. Jain, R. A. Yeh, and A. Schwing, “Cooperative exploration for multi-agent deep reinforcement learning,” in _Proc. International Conference on Machine Learning (ICML)_ , vol. 139, 18–24 Jul 2021, pp. 6826–6836.
  * [11] A. Dubey and A. Pentland, “Provably efficient cooperative multi-agent reinforcement learning with function approximation,” 2021. [Online]. Available: https://arxiv.org/abs/2103.04972
  * [12] S. Flennerhag, J. X. Wang, P. Sprechmann, F. Visin, A. Galashov, S. Kapturowski, D. L. Borsa, N. Heess, A. Barreto, and R. Pascanu, “Temporal difference uncertainties as a signal for exploration,” 2020. [Online]. Available: https://arxiv.org/abs/2010.02255
  * [13] C. Gehring and D. Precup, “Smart exploration in reinforcement learning using absolute temporal difference errors,” in _Proc. of International Conference on Autonomous Agents and Multi-Agent Systems_. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2013, p. 1037–1044.
  * [14] M. Tan, “Multi-agent reinforcement learning: Independent vs. cooperative agents,” in _Readings in Agents_. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997, pp. 487–494.
  * [15] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in _Proc. International Conference on Neural Information Processing Systems_. Red Hook, NY, USA: Curran Associates Inc., 2017, p. 6382–6393.
  * [16] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. F. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel, “Value-decomposition networks for cooperative multi-agent learning,” 2017. [Online]. Available: http://arxiv.org/abs/1706.05296
  * [17] L. Chen, R. Jain, and H. Luo, “Learning infinite-horizon average-reward Markov decision process with constraints,” in _Proc. International Conference on Machine Learning_ , vol. 162, 17–23 Jul 2022, pp. 3246–3270.
  * [18] Y. Chen, J. He, and Q. Gu, “On the sample complexity of learning infinite-horizon discounted linear kernel MDPs,” in _Proc. International Conference on Machine Learning_ , vol. 162, 17–23 Jul 2022, pp. 3149–3183.
  * [19] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press Cambridge, 1998, vol. 1.
  * [20] C. J. C. H. Watkins and P. Dayan, “Q-learning,” _Machine Learning_ , vol. 8, no. 3, pp. 279–292, 1992.
  * [21] J. N. Tsitsiklis, “Asynchronous stochastic approximation and Q-learning,” _Machine Learning_ , vol. 16, no. 3, pp. 185–202, 1994.
  * [22] S. Singh, T. Jaakkola, M. L. Littman, and C. Szepesvari, “Convergence results for single-step on-policy reinforcement-learning algorithms,” _Machine Learning_ , vol. 38, no. 3, pp. 287–308, 2000.
  * [23] E. Even-Dar and Y. Mansour, “Learning rates for Q-learning,” in _Computational Learning Theory_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 589–604.
  * [24] M. Kearns and S. Singh, “Finite-sample convergence rates for Q-learning and indirect algorithms,” in _Advances in Neural Information Processing Systems_ , vol. 11. MIT Press, 1998.
  * [25] O. Peer, C. Tessler, N. Merlis, and R. Meir, “Ensemble bootstrapping for Q-learning,” 2021. [Online]. Available: https://arxiv.org/abs/2103.00445
  * [26] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy, “Deep exploration via bootstrapped DQN,” in _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, Eds., vol. 29. Curran Associates, Inc., 2016.
  * [27] C. Szepesvári, “The asymptotic convergence-rate of Q-learning,” in _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , M. Jordan, M. Kearns, and S. Solla, Eds., vol. 10. MIT Press, 1997.


#  DESY 08–150 ISSN 0418-9833
September 2008

New relationships between Feynman integrals

O. V. Tarasov

II. Institut für Theoretische Physik, Universität Hamburg,
Luruper Chaussee 149, 22761 Hamburg, Germany On leave of absence from Joint
Institute for Nuclear Research, 141980 Dubna (Moscow Region), Russia.

###### Abstract

New types of relationships between Feynman integrals are presented. It is
shown that Feynman integrals satisfy functional equations connecting integrals
with different values of scalar invariants and masses. A method is proposed
for obtaining such relations. The derivation of functional equations for one-
loop propagator- and vertex - type integrals is given. It is shown that a
propagator - type integral can be written as a sum of two integrals with
modified scalar invariants and one propagator massless. The vertex - type
integral can be written as a sum over vertex integrals with all but one
propagator massless and one external momentum squared equal to zero. It is
demonstrated that the functional equations can be used for the analytic
continuation of Feynman integrals to different kinematic domains.

PACS numbers: 02.30.Gp, 02.30.Ks, 12.20.Ds, 12.38.Bx
Keywords: Feynman integrals, functional equations, Appell hypergeometric
function

##  1 A method for deriving functional equations

Feynman integrals play an important role in making precise perturbative
predictions in quantum field theory. As is well-known, these integrals satisfy
recurrence relations [1]\- [4]. In general such relations connect several
integrals $I_{1,n},...,I_{N,n}$ with $n$ internal lines and integrals with a
lesser number of internal lines. They may be written in the following form

$\sum_{i=1}^{N}Q_{i}(\\{m_{j}\\},\\{s_{q}\\},\nu_{l},d)~{}I_{i,~{}n}=\sum_{\begin{subarray}{c}r<n\\\
k\end{subarray}}R_{k,r}(\\{m_{j}\\},\\{s_{m}\\},\nu_{l},d)~{}I_{k,~{}r},$
(1.1)

where $I_{k,r}$ stands for integrals with $r$ internal lines, arbitrary powers
of propagators $\nu_{j}$ and arbitrary shifts of the space-time dimension $d$
; $\\{s_{q}\\}$ is a set of independent scalar invariants that may be formed
from the external momenta. $Q_{i},~{}R_{k}$ are ratios of polynomials
depending on $\\{s_{r}\\}$, masses $m_{j}$ , $\nu_{l}$ and $d$. On the left-
hand side of (1.1) we combined integrals with $n$ internal lines and on the
right hand side integrals with a lesser number of lines.

The key idea in the derivation of the functional equations is to remove
integrals with the maximal number of lines from the relations (1.1) by an
appropriate choice of scalar invariants $\\{s_{q}\\}$, masses $m_{j}^{2}$,
powers of propagators $\nu_{j}$ and space - time dimension $d$.

In order to obtain functional equations from a given equation (1.1) one should
first solve the polynomial system of equations

$Q_{i}(\\{m_{j}\\},\\{s_{q}\\},\nu_{l},d)=0,~{}~{}~{}~{}~{}~{}~{}~{}i=1,{\ldots},N$
(1.2)

with respect to $\\{s_{q}\\},\\{m_{i}\\},\nu_{l},d$ and then take those
solutions for which not all coefficients in front of integrals on the right-
hand side of Eq.(1.1) are vanishing. In many cases functional equations can be
obtained from (1.1) by choosing only kinematic variables $\\{s_{q}\\}$ and
masses $\\{m_{i}\\}$.

We illustrate the method by considering the derivation of the functional
equations for a one-loop integral depending on $n-1$ independent external
momenta:

$I_{n}^{(d)}(\\{m_{l}^{2}\\};~{}\\{p_{ir}\\})=\int\frac{d^{d}q}{i\pi^{{d}/{2}}}\prod_{j=1}^{n}\frac{1}{[(q-p_{j})^{2}-m_{j}^{2}]^{\nu_{j}}},$
(1.3)

where

$p_{ir}=(p_{i}-p_{r})^{2}.$ (1.4)

Here and below, the usual causal prescription for the propagators is
understood, i.e. $1/[q^{2}-m^{2}]\leftrightarrow 1/[q^{2}-m^{2}+i0]$. Any
relation of the form (1.1) can be used for deriving functional equations. In
this paper we will use the following relation [4], [5]:

$\displaystyle G_{n-1}\nu_{j}{\bf
j^{+}}I^{(d+2)}_{n}(\\{m_{l}^{2}\\};\\{p_{ir}\\})-(\partial_{j}\Delta_{n})I^{(d)}_{n}(\\{m_{l}^{2}\\};\\{p_{ir}\\})$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=\sum_{k=1}^{n}(\partial_{j}\partial_{k}\Delta_{n}){\bf
k^{-}}I^{(d)}_{n}(\\{m_{l}^{2}\\};\\{p_{ir}\\}),$ (1.5)

where the operators ${\bf j^{\pm}}$ etc. shift the indices
$\nu_{j}\to\nu_{j}\pm 1$, $G_{n-1}$ is the Gram determinant

$G_{n-1}=-2^{n}\left|\begin{array}[]{cccc}(p_{1}-p_{n})(p_{1}-p_{n})&(p_{1}-p_{n})(p_{2}-p_{n})&\ldots&(p_{1}-p_{n})(p_{n-1}-p_{n})\\\
(p_{1}-p_{n})(p_{2}-p_{n})&(p_{2}-p_{n})(p_{2}-p_{n})&\ldots&(p_{2}-p_{n})(p_{n-1}-p_{n})\\\
\vdots&\vdots&\ddots&\vdots\\\
(p_{1}-p_{n})(p_{n-1}-p_{n})&(p_{2}-p_{n})(p_{n-1}-p_{n})&\ldots&(p_{n-1}-p_{n})(p_{n-1}-p_{n})\end{array}\right|,$
(1.6)

and $\Delta_{n}$ is the modified Cayley determinant defined as:

$\Delta_{n}=\left|\begin{array}[]{cccc}2m_{1}^{2}{}{}{}{}&~{}~{}~{}~{}m_{1}^{2}+m_{2}^{2}-p_{12}&~{}~{}\ldots{}{}&~{}~{}~{}~{}m_{1}^{2}+m_{n}^{2}-p_{1n}\\\
m_{1}^{2}+m_{2}^{2}-p_{12}{}{}{}&~{}~{}2m_{2}^{2}&~{}~{}\ldots{}{}&~{}~{}~{}~{}m_{2}^{2}+m_{n}^{2}-p_{2n}\\\
\vdots&\vdots&~{}~{}\ddots&\vdots\\\
m_{1}^{2}+m_{n}^{2}-p_{1n}{}{}{}&~{}~{}~{}~{}m_{2}^{2}+m_{n}^{2}-p_{2n}&~{}~{}\ldots{}{}&2m_{n}^{2}\end{array}\right|,$
$\partial_{j}\equiv\frac{\partial}{\partial m_{j}^{2}}.$ (1.7)

We assume that the external momenta are not restricted to some specific
integer dimension and therefore $G_{n-1}$ and $\Delta_{n}$ do not satisfy any
condition specific to a particular value of the space-time dimension.

In the present paper we will consider functional equations only for integrals
$I_{n}^{(d)}$ with the first powers of propagators. Setting all $\nu_{k}=1$ in
Eq. (1.5) yields an equation of the form (1.1) connecting integrals with $n$
and $n-1$ lines. Functional equations for the integral $I_{n-1}^{(d)}$ can be
obtained for each particular $j$ by imposing two conditions:

$G_{n-1}=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\partial_{j}\Delta_{n}=0,$
(1.8)

and solving them by an appropriate choice of scalar invariants $p_{ij}$ and
masses. There are only $n-1$ independent systems of relations of the type
(1.8), because

$\sum_{k=1}^{n}\partial_{k}~{}\Delta_{n}=-G_{n-1}.$ (1.9)

Since $G_{n-1}$ and $\partial_{j}\Delta_{n}$ are nonlinear in $p_{ij}$ and
masses, each system of equations may have several solutions. The number of
functional equations is less than the number of possible solutions. This is
firstly because coefficients in front of integrals on both sides of Eq. (1.1)
are simultaneously zero for some solutions, and secondly, because not all
functional equations are independent.

##  2 Functional equations for the one-loop propagator - type integral

In accordance with our method described in the previous section, functional
equations for the integral $I^{(d)}_{2}$ can be obtained from equation (1.5)
taken at $n=3$, $~{}\nu_{1}=\nu_{2}=\nu_{3}=1$. We will not derive all
possible functional equations, restricting ourselves only to the case $j=1$ in
(1.5):

$\displaystyle G_{2}{\bf
1^{+}}I_{3}^{(d+2)}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12})$
$\displaystyle-$
$\displaystyle(\partial_{1}\Delta_{3})I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12})$
(2.10) $\displaystyle=$ $\displaystyle
2(p_{12}+p_{23}-p_{13})I_{2}^{(d)}(m_{1}^{2},m_{2}^{2};~{}p_{12})$
$\displaystyle+$ $\displaystyle
2(p_{13}+p_{23}-p_{12})I_{2}^{(d)}(m_{1}^{2},m_{3}^{2};~{}p_{13})$
$\displaystyle-$ $\displaystyle
4p_{23}I_{2}^{(d)}(m_{2}^{2},m_{3}^{2};~{}p_{23}),$

where

$\displaystyle
I_{3}^{(d)}(m_{j}^{2},m_{k}^{2},m_{l}^{2};p_{kl},p_{jl},p_{jk})\\!=\\!\int\frac{d^{d}q}{i\pi^{{d}/{2}}}\frac{1}{[(q-p_{j})^{2}\\!-\\!m_{j}^{2}][(q-p_{k})^{2}\\!-\\!m_{k}^{2}][(q-p_{l})^{2}\\!-\\!m_{l}^{2}]},$
$\displaystyle
I_{2}^{(d)}(m_{j}^{2},m_{k}^{2};~{}p_{jk})=\int\frac{d^{d}q}{i\pi^{{d}/{2}}}\frac{1}{[(q-p_{j})^{2}-m_{j}^{2}][(q-p_{k})^{2}-m_{k}^{2}]}.$
(2.11)

In order to remove integrals $I_{3}^{(d)},I_{3}^{(d+2)}$ from this relation
two conditions must be fulfilled:

$\displaystyle G_{2}$ $\displaystyle=$ $\displaystyle
2p_{12}^{2}+2p_{13}^{2}+2p_{23}^{2}-4p_{12}p_{13}-4p_{12}p_{23}-4p_{13}p_{23}=0,$
$\displaystyle\partial_{1}\Delta_{3}$ $\displaystyle=$ $\displaystyle
2p_{23}(p_{13}+p_{12}-p_{23})-4m_{1}^{2}p_{23}$ (2.12)
$\displaystyle~{}~{}+2m_{2}^{2}(p_{23}+p_{13}-p_{12})+2m_{3}^{2}(p_{23}+p_{12}-p_{13})=0.$

One can solve this system of equations with respect to $p_{13}$ and $p_{23}$.
The nontrivial solutions of the system (2.12) are:

$\displaystyle
p_{13}=s_{13}(m_{1}^{2},m_{2}^{2},m_{3}^{2},p_{12})=\frac{\Delta_{12}+2p_{12}(m_{1}^{2}+m_{3}^{2})-(p_{12}+m_{1}^{2}-m_{2}^{2})\lambda}{2p_{12}},$
$\displaystyle
p_{23}=s_{23}(m_{1}^{2},m_{2}^{2},m_{3}^{2},p_{12})=\frac{\Delta_{12}+2p_{12}(m_{2}^{2}+m_{3}^{2})+(p_{12}-m_{1}^{2}+m_{2}^{2})\lambda}{2p_{12}},$
(2.13)

where

$\lambda=\pm\sigma(p_{12}-m_{1}^{2}+m_{2}^{2})~{}\sqrt{\Delta_{12}+4p_{12}m_{3}^{2}},$
(2.14)
$\sigma(x)=\left\\{\begin{array}[]{ll}+1&~{}~{}~{}~{}\textrm{if}~{}~{}~{}~{}x\geq
0\textrm{,}\\\
-1&~{}~{}~{}~{}\textrm{if}~{}~{}~{}~{}x<0\textrm{,}\end{array}\right.$ (2.15)
$\Delta_{ij}=p_{ij}^{2}+m_{i}^{4}+m_{j}^{4}-2p_{ij}m_{i}^{2}-2p_{ij}m_{j}^{2}-2m_{i}^{2}m_{j}^{2}.$
(2.16)

Substituting Eq. (2.13) into Eq. (2.10) yields the following relation:

$\displaystyle I_{2}^{(d)}(m_{1}^{2},m_{2}^{2};~{}p_{12})=$
$\displaystyle\frac{p_{12}+m_{1}^{2}-m_{2}^{2}-\lambda}{2p_{12}}~{}I_{2}^{(d)}(m_{1}^{2},m_{3}^{2};~{}s_{13}(m_{1}^{2},m_{2}^{2},m_{3}^{2},p_{12}))$
$\displaystyle+$
$\displaystyle\frac{p_{12}-m_{1}^{2}+m_{2}^{2}+\lambda}{2p_{12}}~{}I_{2}^{(d)}(m_{2}^{2},m_{3}^{2};~{}s_{23}(m_{1}^{2},m_{2}^{2},m_{3}^{2},p_{12})).$
(2.17)

All arguments of the integral $I_{2}^{(d)}$ on the left - hand side of (2.17)
are arbitrary. At the same time, the last argument in integrals on the right -
hand side satisfy conditions (2.12). The mass $m_{3}$ in the equation is an
arbitrary parameter and can be chosen at will. Setting $m_{3}=0$ in Eqs.
(2.13)-(2.17), yields

$\displaystyle I_{2}^{(d)}(m_{1}^{2},m_{2}^{2};~{}p_{12})$ $\displaystyle=$
$\displaystyle\frac{p_{12}+m^{2}_{1}-m^{2}_{2}-\alpha_{12}}{2p_{12}}~{}I_{2}^{(d)}(m_{1}^{2},0;~{}s_{13})$
(2.18) $\displaystyle+$
$\displaystyle\frac{p_{12}-m^{2}_{1}+m^{2}_{2}+\alpha_{12}}{2p_{12}}~{}I_{2}^{(d)}(0,m_{2}^{2};~{}s_{23}),$

where

$\displaystyle
s_{13}=\frac{\Delta_{12}+2p_{12}m_{1}^{2}-(p_{12}+m_{1}^{2}-m_{2}^{2})\alpha_{12}}{2p_{12}},$
$\displaystyle
s_{23}=\frac{\Delta_{12}+2p_{12}m_{2}^{2}+(p_{12}-m_{1}^{2}+m_{2}^{2})\alpha_{12}}{2p_{12}},$
(2.19)

$\alpha_{12}=\pm\sigma(p_{12}-m_{1}^{2}+m_{2}^{2})~{}\sqrt{\Delta_{12}}~{}.$
(2.20)

The analytic expression for the integral $I_{2}^{(d)}(0,m^{2};~{}p^{2})$ is
[6], [7]:

$I_{2}^{(d)}(0,m^{2};~{}p^{2})=I_{2}^{(d)}(0,m^{2};~{}0)\,{}_{2}F_{1}\\!\\!\left[\begin{array}[]{c}1,2-\frac{d}{2}\,;\\\
\frac{d}{2}\,;\end{array}\frac{p^{2}}{m^{2}}\right],$ (2.21)

where

$I_{2}^{(d)}(0,m^{2};~{}0)=-\Gamma\left(1-\frac{d}{2}\right)m^{d-4}.$ (2.22)

Thus, relations (2.18) and (2.21) give us the analytic result for the integral
$I_{2}^{(d)}$ with arbitrary masses and external momentum squared. Our result
is in agreement with that presented in [7].

Setting $m_{2}^{2}=0$ in equation (2.18), assuming $|p_{12}|>m_{1}^{2}$ and
taking solution (2.19) corresponding to the $+$ sign in formula (2.20) yields

$I_{2}^{(d)}(m_{1}^{2},0;~{}p_{12})=\frac{m_{1}^{2}}{p_{12}}I_{2}^{(d)}\left(m_{1}^{2},0;~{}\frac{m_{1}^{4}}{p_{12}}\right)+\frac{(p_{12}-m_{1}^{2})}{p_{12}}I_{2}^{(d)}\left(0,0;~{}\frac{(p_{12}-m_{1}^{2})^{2}}{p_{12}}\right).$
(2.23)

The first term on the right - hand side is the same integral $I_{2}^{(d)}$ as
on the left - hand side, but with the last argument inverted. The second term
corresponds to the simple integral $I_{2}^{(d)}$ with both propagators
massless:

$I_{2}^{(d)}(0,0;~{}p^{2})=\frac{1}{i\pi^{d/2}}\int\frac{d^{d}k_{1}}{k_{1}^{2}(k_{1}-p)^{2}}=\frac{-\pi^{\frac{3}{2}}~{}(-p^{2})^{\frac{d}{2}-2}}{2^{d-3}\Gamma\left(\frac{d-1}{2}\right)\sin\frac{\pi
d}{2}}.$ (2.24)

Formula (2.23) can be applied to the analytic continuation of the integral
$I_{2}^{(d)}(m_{1}^{2},0;~{}p_{12})$ into the region of large momenta
$|p_{12}|>m_{1}^{2}$. It can also be used for the analytic continuation of the
integrals $I_{2}^{(d)}$ on the right - hand side of (2.18). Therefore, the
relations (2.18) and (2.23) describe the integral $I_{2}^{(d)}$ with arbitrary
masses and momenta in the whole kinematic region.

It is interesting to note that equation (2.23) corresponds to the well-known
formula for the analytic continuation of Gauss’s hypergeometric function
(2.21) (see, for example, Ref.[8]) :

$\,{}_{2}F_{1}\\!\\!\left[\begin{array}[]{c}1,2-\frac{d}{2}\,;\\\
\frac{d}{2}\,;\end{array}z\right]=\frac{1}{z}~{}\,{}_{2}F_{1}\\!\\!\left[\begin{array}[]{c}1,2-\frac{d}{2}\,;\\\
\frac{d}{2}\,;\end{array}\frac{1}{z}\right]+\frac{\Gamma\left(\frac{d}{2}\right)\Gamma\left(\frac{d}{2}-1\right)}{\Gamma(d-2)}(-z)^{\frac{d}{2}-2}\left(1-\frac{1}{z}\right)^{d-3}.$
(2.25)

Indeed, substituting the explicit expressions (2.21), (2.24) into (2.23) and
canceling common factors we obtain relation (2.25) with $z=p_{12}/m_{1}^{2}$.

##  3 Functional equations for the one-loop vertex - type integral

Functional equations for the vertex - type integral $I_{3}^{(d)}$ will be
derived in the same fashion as for the propagator - type integral. Setting
$n=4$, $\nu_{1}={\ldots}=\nu_{4}=1$ and $j=1$ in Eq.(1.5) yields:

$\displaystyle G_{3}~{}{\bf
1^{+}}I_{4}^{(d+2)}(\\{m_{l}^{2}\\};~{}\\{p_{ij}\\})-(\partial_{1}\Delta_{4})I_{4}^{(d)}(\\{m_{l}^{2}\\};~{}\\{p_{ij}\\})=$
(3.26)
$\displaystyle~{}~{}(\partial_{1}^{2}\Delta_{4})~{}I_{3}^{(d)}(m_{2}^{2},m_{3}^{2},m_{4}^{2};~{}p_{34},p_{24},p_{23})$
$\displaystyle+$
$\displaystyle(\partial_{1}\partial_{2}\Delta_{4})~{}I_{3}^{(d)}(m_{1}^{2},m_{3}^{2},m_{4}^{2};~{}p_{34},p_{14},p_{13})$
$\displaystyle+$
$\displaystyle(\partial_{1}\partial_{3}\Delta_{4})~{}I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},m_{4}^{2};~{}p_{24},p_{14},p_{12})$
$\displaystyle+$
$\displaystyle(\partial_{1}\partial_{4}\Delta_{4})~{}I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12}).$

One can obtain a functional equation for
$I_{3}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12})$ with arbitrary
arguments by appropriately choosing the four variables:
$p_{14},p_{24},p_{34}$, $m_{4}^{2}$. To remove the integrals
$I_{4}^{(d)},I_{4}^{(d+2)}$ from (3.26), two conditions should be satisfied

$G_{3}=0,~{}~{}~{}~{}\partial_{1}\Delta_{4}=0.$ (3.27)

This system of equations depends on 10 variables
$p_{12},p_{13},p_{14},p_{23},p_{24},p_{34},$
$m_{1}^{2},m_{2}^{2},m_{3}^{2},m_{4}^{2}$ and it can be solved by excluding,
for example, $p_{14}$ and $p_{34}$. There are four solutions of the system
(3.27) but appropriate expressions are rather long and for this reason they
will not be presented here. Instead we consider simplified situation, namely
we set in Eq. (3.26) from the very beginning $m_{4}^{2}=0$, and impose the
following conditions

$G_{3}=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}\partial_{1}\Delta_{4}=0,~{}~{}~{}~{}~{}~{}~{}~{}~{}\partial_{1}\partial_{2}\Delta_{4}=0.$
(3.28)

This system can be solved by an appropriate choice of $p_{14},p_{34},p_{24}$.
There are several solutions of (3.28), but only for two of them are
coefficients in front of integrals on the right hand side of (3.26) different
from zero. These solutions are

$\displaystyle p_{14}$ $\displaystyle=$ $\displaystyle s_{14}^{(13)},$
$\displaystyle p_{34}$ $\displaystyle=$ $\displaystyle s_{34}^{(13)},$
$\displaystyle p_{24}$ $\displaystyle=$ $\displaystyle
s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12})$ (3.29) $\displaystyle=$
$\displaystyle\frac{(p_{12}+p_{23}-m_{1}^{2}-m_{3}^{2})p_{13}+(p_{12}-p_{23}-m_{1}^{2}+m_{3}^{2})(m_{3}^{2}-m_{1}^{2}+\alpha_{13})}{2p_{13}},$

where

$\displaystyle s_{14}^{(ij)}$ $\displaystyle=$
$\displaystyle\frac{\Delta_{ij}+2m_{i}^{2}p_{ij}-(p_{ij}+m_{i}^{2}-m_{j}^{2})\alpha_{ij}}{2p_{ij}},$
$\displaystyle s_{34}^{(ij)}$ $\displaystyle=$
$\displaystyle\frac{\Delta_{ij}+2m_{j}^{2}p_{ij}+(p_{ij}+m_{j}^{2}-m_{i}^{2})\alpha_{ij}}{2p_{ij}},$
$\displaystyle\alpha_{ij}$ $\displaystyle=$
$\displaystyle\pm\sigma(p_{ij}-m_{i}^{2}+m_{j}^{2})\sqrt{\Delta_{ij}}.$ (3.30)

Substituting (3) into (3.26) leads to the following functional equation:

$\displaystyle
I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12})=$
$\displaystyle~{}~{}\frac{p_{13}+m_{3}^{2}-m_{1}^{2}+\alpha_{13}}{2p_{13}}~{}I_{3}^{(d)}(m_{2}^{2},m_{3}^{2},0;~{}s_{34}^{(13)},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),p_{23})$
$\displaystyle~{}+\frac{p_{13}-m_{3}^{2}+m_{1}^{2}-\alpha_{13}}{2p_{13}}~{}I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},0;~{}s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),s_{14}^{(13)},p_{12}).$
(3.31)

Relation (3.31) means that the integral $I_{3}^{(d)}$ with arbitrary arguments
can always be expressed in terms of integrals with at least one massless
propagator. The only exceptional case, when $p_{12}=p_{13}=p_{23}=0$, is
trivial. In turn, integrals $I_{3}^{(d)}$ with one massless propagator can be
represented as a sum over integrals with two massless propagators. Indeed,
setting $m_{2}^{2}=0$ in Eq. (3.31) yields:

$\displaystyle I_{3}^{(d)}(m_{1}^{2},0,m_{3}^{2};~{}p_{23},p_{13},p_{12})=$
$\displaystyle~{}~{}~{}~{}~{}~{}\frac{p_{13}-m_{1}^{2}+m_{3}^{2}+\alpha_{13}}{2p_{13}}~{}I_{3}^{(d)}(0,m_{3}^{2},0;~{}s_{34}^{(13)},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),p_{23})$
$\displaystyle~{}~{}~{}~{}~{}~{}+\frac{p_{13}+m_{1}^{2}-m_{3}^{2}-\alpha_{13}}{2p_{13}}~{}I_{3}^{(d)}(m_{1}^{2},0,0;~{}s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),s_{14}^{(13)},p_{12}).$
(3.32)

Taking into account the symmetry of the integral $I_{3}^{(d)}$ with respect to
its arguments one can use Eq. (3.32) to express integrals on the right hand
side of (3.31) in terms of integrals with two propagators massless. Thus in
case when external momenta squared are different from zero the following
relation holds:

$\displaystyle
I_{3}^{(d)}(m_{1}^{2},m_{2}^{2},m_{3}^{2};~{}p_{23},p_{13},p_{12})=$
$\displaystyle\frac{(p_{13}+m_{3}^{2}-m_{1}^{2}+\alpha_{13})(p_{23}+m_{3}^{2}-m_{2}^{2}+\alpha_{23})}{4p_{13}p_{23}}$
$\displaystyle\times
I_{3}^{(d)}(m_{3}^{2},0,0;~{}s_{24}(m_{2}^{2},m_{3}^{2},s_{34}^{(13)},p_{23},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12})),s_{34}^{(23)},s_{34}^{(13)})$
$\displaystyle+\frac{(p_{13}+m_{3}^{2}-m_{1}^{2}+\alpha_{13})(p_{23}-m_{3}^{2}+m_{2}^{2}-\alpha_{23})}{4p_{13}p_{23}}$
$\displaystyle\times
I_{3}^{(d)}(m_{2}^{2},0,0;~{}s_{24}(m_{2}^{2},m_{3}^{2},s_{34}^{(13)},p_{23},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12})),s_{14}^{(23)},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}))$
$\displaystyle+\frac{(p_{13}-m_{3}^{2}+m_{1}^{2}-\alpha_{13})(p_{12}+m_{2}^{2}-m_{1}^{2}+\alpha_{12})}{4p_{13}p_{12}}$
$\displaystyle\times
I_{3}^{(d)}(m_{2}^{2},0,0;~{}s_{24}(m_{1}^{2},m_{2}^{2},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),p_{12},s_{14}^{(13)}),s_{34}^{(12)},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}))$
$\displaystyle+\frac{(p_{13}-m_{3}^{2}+m_{1}^{2}-\alpha_{13})(p_{12}-m_{2}^{2}+m_{1}^{2}-\alpha_{12})}{4p_{12}p_{13}}$
$\displaystyle\times
I_{3}^{(d)}(m_{1}^{2},0,0;~{}s_{24}(m_{1}^{2},m_{2}^{2},s_{24}(m_{1}^{2},m_{3}^{2},p_{23},p_{13},p_{12}),p_{12},s_{14}^{(13)}),s_{14}^{(12)},s_{14}^{(13)}).$
(3.33)

There is one further simplification of note. Setting
$m_{1}^{2}=m_{3}^{2}=p_{24}=0$ in Eq. (3.26) from the very beginning and
solving system of equations

$G_{3}=0,~{}~{}~{}~{}~{}~{}\partial_{1}\Delta_{4}=0,$ (3.34)

with respect to $p_{14}$ and $p_{34}$ yields a nontrivial relationship:

$\displaystyle I_{3}^{(d)}(0,m^{2},0;~{}p_{23},p_{13},p_{12})=$
$\displaystyle-\frac{[b(p_{23},p_{12})-(p_{12}+m^{2})\alpha_{123}]m^{2}}{2\Lambda_{3}}~{}I_{3}^{(d)}(m^{2},0,0;~{}\kappa_{14},0,p_{12})$
$\displaystyle-\frac{[b(p_{12},p_{23})+(p_{23}+m^{2})\alpha_{123}]m^{2}}{2\Lambda_{3}}~{}I_{3}^{(d)}(m^{2},0,0;~{}\kappa_{34},0,p_{23})$
$\displaystyle+\frac{\Lambda_{3}-p_{13}(p_{12}p_{23}-m^{4})-m^{2}(p_{12}-p_{23})\alpha_{123}}{2\Lambda_{3}}~{}I_{3}^{(d)}(0,0,0;~{}\kappa_{34},\kappa_{14},p_{13}),$
(3.35)

where

$\displaystyle\kappa_{14}=\frac{a(p_{23},p_{12})+m^{2}b(p_{23},p_{12})\alpha_{123}}{2\Lambda_{3}},$
$\displaystyle\kappa_{34}=\frac{a(p_{12},p_{23})-m^{2}b(p_{12},p_{23})\alpha_{123}}{2\Lambda_{3}},$
(3.36)
$\displaystyle\Lambda_{3}=(m^{4}-p_{12}p_{23})(p_{23}-p_{12})-(p_{12}+m^{2})b(p_{12},p_{23}),$
$\displaystyle
a(p_{12},p_{23})=m^{2}(p_{12}-p_{23})^{2}(p_{23}-m^{2})+[2(m^{2}-p_{23})p_{12}-m^{2}p_{13}](p_{23}+m^{2})p_{13},$
$\displaystyle
b(p_{12},p_{23})=(m^{2}+p_{13}+p_{12}-p_{23})p_{23}+m^{2}(p_{13}-p_{12}),$
$\displaystyle\alpha_{123}=\sigma(b(p_{12},p_{23}))\sqrt{\Delta_{123}},$
$\displaystyle\Delta_{123}=p_{12}^{2}+p_{13}^{2}+p_{23}^{2}-2p_{12}p_{13}-2p_{12}p_{23}-2p_{13}p_{23}.$
(3.37)

Therefore, by using Eq.(3.35) we can represent the integral $I_{3}^{(d)}$ with
arbitrary masses and nonzero kinematic variables as a combination of integrals
with two massless propagators, one momentum squared equal to zero and
integrals with all propagators massless. An analytic result for the integral
$I_{3}^{(d)}$ with all propagators massless is known in terms of ${}_{2}F_{1}$
functions (see Ref. [9]).

Integrals $I_{3}^{(d)}$ with two massless propagators on the right - hand side
of (3.35) can be evaluated analytically. In the kinematic region $|p_{12}|\leq
m^{2}$ and $|p_{13}|\leq m^{2}$ we find

$\displaystyle
I_{3}^{(d)}(0,m^{2},0;~{}0,p_{13},p_{12})=-\frac{I_{2}^{(d)}(0,0;~{}p_{13})}{m^{2}}\,{}_{2}F_{1}\\!\\!\left[\begin{array}[]{c}1,\frac{d-2}{2}\,;\\\
d-2\,;\end{array}\frac{p_{12}-p_{13}}{m^{2}}\right]$ (3.40)
$\displaystyle~{}~{}~{}~{}~{}+\frac{1}{m^{2}}~{}I_{2}^{(d)}(0,m^{2};~{}0)~{}F_{1}\left(1,1,2-\frac{d}{2},\frac{d}{2};\frac{p_{12}-p_{13}}{m^{2}},\frac{p_{12}}{m^{2}}\right),$
(3.41)

where $F_{1}$ is the Appell hypergeometric function [10] which admits a simple
one-fold integral representation:

$F_{1}\left(1,1,2-\frac{d}{2},\frac{d}{2};x,y\right)=\frac{(d-2)}{2}\int_{0}^{1}du\frac{[(1-u)(1-yu)]^{\frac{d}{2}-2}}{(1-xu)}.$
(3.42)

Thus by using (3.41) one can obtain the result for the integral $I_{3}^{(d)}$
in terms of the Appell function $F_{1}$ and Gauss’s hypergeometric function
${}_{2}F_{1}$. This result is in agreement with the result obtained in Ref.
[11] and later in Ref. [12]. At $d=4$ the result for $I_{3}^{(4)}$ in terms of
Appell function $F_{3}$ was obtained in Ref. [13].

The Appell function $F_{1}$ in formula (3.41) has branch points if

$|p_{12}|\geq m^{2},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
or}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}|p_{12}-p_{13}|\geq m^{2}.$ (3.43)

To analytically continue the integral
$I_{3}^{(d)}(0,m^{2},0;~{}0,p_{13},p_{12})$ into regions (3.43) one can use
appropriate functional equations. When $|p_{12}|\geq m^{2}$, the following
functional equation can be applied:

$\displaystyle
I_{3}^{(d)}(0,m^{2},0;~{}0,p_{13},p_{12})=\frac{m^{2}}{p_{12}}~{}I_{3}^{(d)}\left(0,m^{2},0;~{}0,\frac{m^{2}(p_{13}-p_{12}+m^{2})}{p_{12}},\frac{m^{4}}{p_{12}}\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\frac{(p_{12}-m^{2})}{p_{12}}~{}I_{3}^{(d)}\left(0,0,0;~{}\frac{m^{2}(p_{13}-p_{12}+m^{2})}{p_{12}},\frac{(p_{12}-m^{2})^{2}}{p_{12}},p_{13}\right).$
(3.44)

This relation can be derived from Eq. (3.26) with
$m_{1}^{2}=m_{3}^{2}=m_{4}^{2}=p_{23}=0$ and $m_{2}^{2}=m^{2}$ by imposing the
following conditions:

$G_{4}=0,~{}~{}~{}~{}\partial_{1}\Delta_{4}=0,~{}~{}~{}~{}\partial_{1}\partial_{3}\Delta_{4}=0.$
(3.45)

On the right - hand side of the relation (3.44) the last two arguments of the
integral $I_{3}^{(d)}$ in the first term are finite for large $|p_{12}|$.

If $|p_{12}-p_{13}|\geq m^{2}$ and $|p_{12}|\leq m^{2}$, the following
relation can be applied

$\displaystyle
I_{3}^{(d)}(0,m^{2},0;~{}0,p_{13},p_{12})=\frac{p_{12}m^{2}}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}}I_{3}^{(d)}\left(0,m^{2},0;~{}0,\frac{p_{12}^{2}(p_{13}-p_{12}+m^{2})}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}},p_{12}\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}+\frac{p_{12}(p_{13}-p_{12})}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}}~{}I_{3}^{(d)}\left(0,0,0;~{}\frac{m^{2}(p_{13}-p_{12})^{2}}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}},\frac{p_{12}^{2}(p_{13}-p_{12}+m^{2})}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}},p_{13}\right)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}+\frac{m^{2}(p_{13}-p_{12})}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}}I_{3}^{(d)}\left(0,m^{2},0;~{}0,\frac{m^{2}(p_{13}-p_{12})^{2}}{m^{2}p_{13}+p_{12}p_{13}-p_{12}^{2}},0\right).$
(3.46)

This relation can be derived from Eq. (3.26) with
$m_{1}^{2}=m_{3}^{2}=m_{4}^{2}=p_{23}=p_{24}=0$ and $m_{2}^{2}=m^{2}$ by
imposing the following conditions:

$G_{4}=0,~{}~{}~{}~{}\partial_{1}\Delta_{4}=0.$ (3.47)

The penultimate argument of the first integral on the right hand side of
(3.46) is finite for large values of $|p_{13}|\geq m^{2}$ if
$p_{12}\neq-m^{2}$. The second and the third integrals on the right - hand
side of this relation can be expressed in terms of the hypergeometric function
${}_{2}F_{1}$ and their analytic continuation causes no problems.

If both conditions (3.43) hold then the analytic continuation can be done by
applying both (3.44) and (3.46).

##  4 Conclusions

Finally, we summarize what we have accomplished in this paper.

First of all, we formulated the general method for deriving functional
equations for Feynman integrals.

Second, it was shown that integrals with many kinematic arguments can be
reduced to a combination of integrals with simpler kinematics.

Third, we demonstrated that our functional equations can be used for the
analytic continuation of Feynman integrals to all kinematic domains.

In the present paper we considered rather particular cases of functional
equations. The systematic investigation and classification of the proposed
functional equations requires application of the methods of algebraic geometry
and group theory.

A detailed consideration of our functional equations and their application to
the one-loop integrals with four, five and six external legs as well as to
some two- and three- loop Feynman integrals will be presented in future
publications.

##  5 Acknowledgment

I am very thankful to Ronald Reid-Edwards for carefully reading the manuscript
and useful remarks. This work was supported in part from DFG grants DFG
KN365/3 and BMBF 05HT6GUA. Part of this investigation was done during my stay
at the Institut für Theoretische Physik E, RWTH Aachen where I was supported
from the DFG grant Sonderforschungsbereich Transregio 9-03.

## References

  * [1] B. Petersson, J. Math. Phys. 6, (1965) 1955.
  * [2] G. ’t Hooft and M. J. G. Veltman, Nucl. Phys. B 44, (1972) 189.
  * [3] F. V. Tkachov, Phys. Lett. B 100 (1981) 65;
K. G. Chetyrkin and F. V. Tkachov, Nucl. Phys. B 192 (1981) 159.

  * [4] O. V. Tarasov, Phys. Rev. D 54 (1996) 6479 [arXiv:hep-th/9606018].
  * [5] J. Fleischer, F. Jegerlehner and O. V. Tarasov, Nucl. Phys. B 566 (2000) 423 [arXiv:hep-ph/9907327].
  * [6] C. G. Bollini and J. J. Giambiagi, Phys. Lett. B 40 (1972) 566.
  * [7] E. E. Boos and A. I. Davydychev, Theor. Math. Phys. 89, (1991) 1052; Teor. Mat. Fiz. 89, (1991) 56 .
  * [8] A. Erdèly et. al., Higher Transcendental Functions Vol.1, McGraw-Hill, New York, 1953.
  * [9] A. I. Davydychev, Phys. Rev. D 61 (2000) 087701 [arXiv:hep-ph/9910224].
  * [10] P. Appell and J. Kampé de Fériet Fonctions hypergeometriques et hyperspériques, Gauthier Villars, Paris, 1926.
  * [11] J. Fleischer, F. Jegerlehner and O. V. Tarasov, Nucl. Phys. B 672, (2003) 303, [arXiv:hep-ph/0307113].
  * [12] A. I. Davydychev, Nucl. Instrum. Meth. A 559 (2006) 293 [arXiv:hep-th/0509233].
  * [13] L. G. Cabral-Rosetti and M. A. Sanchis-Lozano, J. Comput. Appl. Math. 115 (2000) 93 [arXiv:hep-ph/9809213].