Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPs
Authors: Thomas Spooner
Nelson Vadori
Sumitra Ganesh
Venue: NeurIPS 2021 Poster (2021)
Keywords: policy
gradients
baselines
reinforcement
learning
traffic
multi-agent

Abstract: Policy gradient methods can solve complex tasks but often fail when the dimensionality of the action-space or objective multiplicity grow very large. This occurs, in part, because the variance on score-based gradient estimators scales quadratically. In this paper, we address this problem through a factor baseline which exploits independence structure encoded in a novel action-target influence network. Factored policy gradients (FPGs), which follow, provide a common framework for analysing key state-of-the-art algorithms, are shown to generalise traditional policy gradients, and yield a principled way of incorporating prior knowledge of a problem domain's generative processes. We provide an analysis of the proposed estimator and identify the conditions under which variance is reduced. The algorithmic aspects of FPGs are discussed, including optimal policy factorisation, as characterised by minimum biclique coverings, and the implications for the bias variance trade-off of incorrectly specifying the network. Finally, we demonstrate the performance advantages of our algorithm on large-scale bandit and traffic intersection problems,  providing a novel contribution to the latter in the form of a spatial approximation.

Factored Policy Gradients: Leveraging Structure for Efficient Learning in MOMDPs
Thomas Spooner
Nelson Vadori
J. P. Morgan Al Research thomas. com
J. P. Morgan Al Research
nelson. vadori w pmorgan. com
Sumitra Ganesh
J. P. Morgan AI Research
sumitra. ganesh com
Abstract
Policy gradient methods solve complex tasks but often fail when the dimension- ality of the action-space or objective multiplicity grow very large. This occurs, in part, because the variance on score-based gradient estimators scales quadratically. In this paper, we address this problem through a factor baseline which exploits in- dependence structure encoded a novel action-target influence network. Factored policy gradients (FPGs), which follow, provide common framework for analysing key state-of-the of-the--rt algorithms, are shown to generalise traditional policy gradients, and yield principled way of incorporating prior knowledge of problem domain's ss generative processes. We provide an analysis of the proposed estimator and iden- tify the conditions under which variance is reduced. The algorithmic aspects of FPGs are discussed, including optimal policy factorisation, as characterised by minimum biclique coverings, and the implications for the bias-vatt variance trade-off incorrectly specifying the network. Finally. we demonstrate the performance advantages of our algorithm on large-scale bandit and traffic intersection problems, providing a novel contribution to the latter in the form of a spatial approximation.
Introduction
Many sequential decision-making problems in the real-world have objectives that can naturally decomposed into set of conditionally independent targets. Control of water reservoirs. energy consumption optimisation, market making, cloud computing allocation, sewage flow systems, and robotics are but few examples (36]. While many optimisation methods have been proposed [25] 34
perhaps most prominently using Lagrangian scalarisation
44 multi-agent learning has emerged
a promising new paradigm for sample-efficient learning 66] In this class of algorithms, the multi-objective learning problem is cast into a centralised, co-operative stochastic game in which co-ordination is achieved through global coupling terms in each agent's objective/reward functions. For example, a grocer who must manage their stock could be decomposed into a collection of sub- agents that each manage single type of produce, but subject global constraint inventory.
This approach has been shown to be very effective in number of domains 20 50 presents both conceptual and technical issues.
30
24 52
but
The transformation of multi-objective Markov decision process (MOMDP) [36 into a stochastic game is non-trivial design challenge. In many cases there is clear delineation between agents in the new system, nor an established way of performing the decomposition. What's 's more, it's unclear in many domains that multi-agent perspective is appropriate, example, the concurrent problems studied by Silver et al. 33 exhibit great levels of homogeneity,
technical trick. For
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

lending themselves to the use of a shared policy which conditions on contextual information. The key challenge that we address in this paper is precisely how to scale these single-agent methods specifically, policy gradients- in a principled way. As we shall see, this study reveals that existing methods in both single- and multi-agent multi-ohjective optimisation can be formulated as special cases of a wider family of algorithms we entitle factored policy gradients. The contributions of this paper are summarised below:
1. We introduce influence networks framework for modelling probabilistic relationships between actions and objectives in an MOMDP, and show how they can be combined with policy factorisation via graph partitioning.
2. We propose new control variate the factor baseline that exploits independence structures within a (factored) influence network, and show how this gives rise to novel class of algorithms which we ascribe the name factored policy gradients.
3. We show that FPGs generalise traditional policy gradient estimators and provide com- mon framework for analysing state-of-the-art algorithms in the literature including action- dependent baselines and counterfactual policy gradients.
4. The variance properties of our family of algorithms are studied, and minimum factorisation is put forward as a principled way of applying FPGs, with theoretical results around the existence and uniqueness of the characterisation.
5. The final contribution is to illustrate the effectiveness of approach over traditional estimators on two high-dimensional benchmark domains.
1.1 Related Work
Policy gradients. Variance reduction techniques in the context of policy gradient methods have been studied for some time. The seminal work of Konda and Tsitsikkis [9] was one of the earliest works that identified the use of a critic as beneficial for learning. Since then, baselines (or, control variates) have received much attention. In [001] Weaver and Tao (53 presented the first formal analysis of their properties, and later Greensmith et al. [33] proved several key results around optimality. More recently, these techniques have been extended to include action-dependent baselines [7] 22 12 57 9
though the source of their apparent success has been questioned by some (49 who suggest that subtle implementation details were the true driver. It has also been shown that one can reduce variance by better accounting for the structure of the action-space, such as bounds 4 10 or more general topological properties 77) The SVRPG approach of Papini et al. [29] also addresses variance concerns in policy gradients by leveraging advances in supervised learning, and the generalised advantage estimator of Schulman et al. (37 has been proposed as method for reducing variance in actor-critic methods with fantastic empirical results; both of these can be combined with baselines and the techniques we present in this work. Factorisation. In related, but distinct line of work, factorisation has been proposed to better leverage the transition structure of MDPs; see e.g. 22 15 44). Indeed, the notion of causality has also been utilised in work by Jonsson and Barto [16. Most recently, Oliehoek et al. (27] presented an elegant framework for harnessing the influence of other agents (from the perspective of self) in multi-agent systems. This approach complementary the work presented in this paper, and more recent extensions have significantly advanced the statc-of-the- art [4] [8] we build upon these principles. There is also a long line of research on "influence diagrams" that is pertinent to this work. While the majority of this effort has been focused on dynamic programming. the ideas are very closely related to ours and indeed we see this work as a natural extension of these concepts 455 Miscellaneous. Causal/ haanal//raphcal modelling has seen past applications in reinforcement learning 11. Indeed, our proposed influence network is related to, but distinct from, the action influence models introduced by Madumal et al. 2 for explainability. There, the intention was to construct policies that can justify actions with respect to the observation space. Here, the intention was to exploit independence structure in MOMDPs for scalability and efficiency.
2 Background
A regular discrete-time Markov decision process (MDP) is tuple M M RS, Po). comprising: a state space S, action space A, and set of rewards R C TR. The dynamics of the MDP are driven by an initial state distribution such that so po(-) and stationary transition kernel where St+1)

---

p(:, st, as) satisfies the Markov property, p(r,, S141 [4,) = p(re, St+1 st, az), for any history h = (so: do, ro. S1....... ............... St. az). Given an MDP, (stochastic) policy, parameterised by 0 E R", is mapping x0 : S x R - (AA) from states and weights to the set of probability measures on A. The conditional probability density of action a is denoted by to [1) P(a E da 8, 0) and we assume throughout that Hh is continuously differentiable with respect to O. For given policy, the return starting from time t is defined the discounted sum of future rewards, G2 = Σ r1+k+1, where y E [0, 1] is the discount rate and T is the terminal time [42]. Value functions express the expected value of returns generated from given state or state-action pair under the MDP's transition
dynamics and policy æ: that is, (8) = P (Ge 8t = s] and (+ (8, a) = (r 8 = 8, a = a). The objective in control is to find policy that maximises Us for all states with non-zero measure under Po, denoted by the Lesbesgue integral J (()) = [uro (so)] = Ss Une (so) dpo (so).
2.1 Policy Search
In this paper, we focus on policy gradient methods which optimise the parameters 0 directly. This achieved, in general, by performing gradient ascent on J (()., for which Sutton et al. 43 derived
V ( = PTo.PTo [( (s, a) b(s)) 2],
(1)
where x = Ve In (o s) is the policy's score vector, Pro (s) [s Ei >'p(s; s =|dss no)
denotes the (improper) discounted-ergode ergodic occupancy measure, and b(s) a state-dependent baseline (or, control variate) (33). Here, p(s; steps under Te. Eqqution Iis convenient for a number reasons: 1. it a score-based estimator [26]; and 2. it falls under the class of stochastic approximation algorithms [.]. This is important as means 2r (s, a) may be replaced by any unbiased quantity, say vp : S x A + R, such that [ a]] qx (s, a), while retaining convergence guarantees. It also implies that optimisation can be performed using stochastic gradient estimates, the standard variant of which defined below.
so. TT) is the probability of transitioning from so - in
Definition 2.1 (VPGs). The vanilla policy gradient estimator for aarget-baslling pair (v/, b) is denoted
g) = [+'s, a) - -b(s)]
(2)
where (0) EsOWTE [g) (s as)
2.2 Factored (Action-Space) MDPs
In this paper, we consider the class of MDPs in which the action-space factors into a product, A = A A; = Ai X ... x An, for some n. This is satisfied trivially when I and Ai = A, but also holds in many common settings, such as A = IR", which factorises n times as X ;- R. This equivalent requiring that actions, having A be a vector space. For example, one could have an action-space of the form A = IR x N such that, for any a E A. a1 and a2 E N. To this end, we introduce the notion of partition maps which will feature throughout the paper.
A, admit "subscript" operation; without necessarily
Definition 2.2 (Partition Map). Define x = - X; and J S [m] with X, X jEJ M, such that a partition map (PM) for pair JJ is a function a X - X, with complement ō X + X R-..
Partition maps are an extension of the canonical projections of the product topology, and are equivalent to the scope operator used by Tian et al. [8). For example, if (a1, 02 ag) = a E A = R denotes a faree-dimensional real action-space, space, then one possible PM is given by (a)) = (a1, ag) with
complement ((a) (az). Note that there should always exist unique inverse operation that recovers the original space; in this case, it would be expressed as (((11.03) (a2)) = (01, 42 03).
3 Influence Networks
Consider an MOMDP with scalarised objective given by
((0) = Ep, (ss = ()00((,,0)(a))
(3)
1=1
3

---

01
al
Q/2
d1
a2
@1
022
1/1
2/2
1/1
1
2/2
1/1
1/2
(a) Fork.
(b) Collider.
(c) Fork/Collider.
(d) Complete.
Figure 1: Influence network prototypes and striontttaretttt junction patterns dependencies between factors a, E A and targets di E v;; and dashed lines partition induced by the minimum factorisation.
33
32
Edges depict
where A E R for all S j S m and each (s, (,, (a)) denotes some target that depends on single partition of the action components. Traditional MDPs can be seen special case in which m 1, and tp 11 = 9n- The vector (s, a) comprises the concatenation of all m targets and each partitioning dictated by the non-empty maps o, (a),, the form of which is intrinsic the MOMDP. For convenience, let us denote the collection of targets comprising 1b(8, s, a.) by
V
{ıt (5s a) = (A, a(s)
(4)
The intuition behind FPGs is derived from the observation that each factor of the action-space only influences a subset of the m targets. Take, for example. Figure Ic which depicts an instance of an influence network between 2-dimensional action vector and 2-dimensional target. The edges suggest that aj affects the value of both th and t/2, whereas only affects lh. This corresponds an objective of the form 1 01) + >2 (s, a). where each goal's domain derives from the edges of the graph. This is formalised in Definition 3.1 below.
Definition 3.1 (Influence Network). bipartite graph G(M, V)) = Iv. E) is said to be the influence network of MDP M and target set V if for IA = [[-A]] and I = []. the presence of an edge, E E, between nodes E LA and E Iv defines causal relationship between the 7th factor of A and the jill target (s, oz (a)).
An influence network can be seen structural equation model 31 in which each vertex in La has single, unique parent which is exogenous and drives the randomness in action sampling, and each vertex in Iy has parents only in the set LA as defined by the set of edges E. The structural equations along each edge ji, E are given by the target functions themselves and the partition maps o; mirror the parents of each node j. Some examples of influence networks are illustrated in Figure 1 see also the appendix. We now define the key concept of influence matrices.
Definition 3.2 (Influence Matrix). Let Kg denote the biadjacency matrix of an influence network G, defined as the LAl x [y] boolean matrix with Ki₃ = + (i.j) E E' for i E LA and j E Ig.
Together, these definitions form a calculus for expressing the relationships between the factors of an action-space and the targets of an objective of the form in Eqquaiin 3) We remark that, from an algorithmic perspective, we are free to choose between two representations: graph- based, partition map-based. The duality between G and K, and the set {az j E Tw }, is intrinsic to our choice of notation and serves as useful correspondence during analysis.
3.1 Policy Factorisation
Influence networks capture the relationships between A and V, but policies are typically defined over groups of actions rather than the individual axes of A. Consider, for example, multi-asset trading problem in which agent must quote buy and sell prices for each of n distinct assets [14] 40) There a natural partitioning between each pair of prices and the sources of profit/loss, and one might therefore define the policy product of bivariate distributions as opposed to full joint, or fully factored model. This choice over policy factorisation relates to the independence assumptions make on the distribution aa for the sake of performance. Indeed, in the majority of the literature, policies are defined using an isotropic distribution (57) since there no domain knowledge motivate more complex covariance structure. We formalise this below.

---

a1
012
43
oi
O
4/o
1/1
2/2
1/1
4/1
222
(a) Original Influence Network. g.
(b) Factored Influence Network, Gy.
Figure 2: Influence network transformation under E-factorisation with (a) = (a1, 02) and
o. aa) (a3). Here, corresponds to a minimum factorisation of the policy; i.c. D"
Definition 3.3 (Policy Factorisation). An n-fold policy factorisation, E = for i [n]], is set of disjoint partition maps that form a complete partitioning over the action space.
The definition above provides means of expressing any joint policy distribution in terms of PMs,
T ())
II T (o (a) (s)
(5)
where of and = |Σ]. This corresponds to a transformation of the underlying influence network where the action vertices are grouped under the policy factors and, for any i, E [n]. i o j. we have mutual independence: of (a) IL oj (a). This is captured in the following concept.
Definition 3.4 (Factored Influence Network). For given influence network G and policy factori- sation Σ, we define a factored influence network, Gr, by replacing LA with Iy,, the set partitioned vertices, and merge the corresponding edges to give Ex. Similarly, denote by Ky; the influence matrix with respect to the E-factorisation.
Factored influence networks ascribe links between the policy factors in Eqqation 5 and the targets Vi E V. They play an important role in Section 4 and provide a refinement Definition 3.1 which allows to design more efficient algorithms. As example, Figuree shows how possible policy factorisation transforms an influence network G into Gr. Note that while the action nodes and edges have been partitioned into policy factors, the fundamental topology with respect the attribution of influence remains unchanged; i.e. no dependencies are lost.
Factored Policy Gradients
Factored policy gradients exploit factored influence networks by attributing each 1 only the policy factors that were probabilistically responsible for generating it; that is, those with a connecting edge in the given Gz. The intuition is that the extraneous targets the objective do not contribute to learning. but do contribute towards variance. For example, it would be counter-intuitive to include vi2 of Figure 26 the update for ग, since it played no generative role. Naturally, by removing these terms from the gradient estimator, we can improve the signal to noise ratio and yield more stable algorithms. This idea can be formulated into set baselines which are defined and validated below.
Definition 4.1 (Factor Baselines). For given Gr. the factor baselines (FBs) defined as
bf (s, o. (a)) = [11 Kx) X (b a));
(6)
for all E [[E]], where o denotes the Hadamard product and 1 is to be taken as an all-ones matrix. Lemma 4.1. FBs are valid control variates if Gz is true to the MDP (i.e, unbiased).
Factor baselines are related to the action-dependent baselines studied by Wu et al. 57 and Tucker al. [49], as well as the methods employed by COMA [9] and DRPGs 3 in multi-agent systems. Note, however, that FBs are distinct in two key ways: 1. they adhere to the structure of the influence network and account not only for policy factorisation, but also the target multiplicity of MOMDPs: and 2. unlike past work, factor baselines were defined using ansatz based on the structure implied by a given Gx; as opposed to explicitly deriving the arg min of the variance, or approximation thereof: see the appendix. This means that, unlike optimal baselines, FBs can be computed efficiently and
5

---

thus yield practical algorithms. Indeed, this very fact is why the state-value function is used so ubiquitously in traditional actor-critic methods as state-dependent control variate despite being sub-optimal. It follows that we can define an analogous family of methods for MOMDPs with zero computational overhead.
Proposition 1 (FPGs). Take a E--factored policy no (als) and [0] x The for target vector 1b(8, a) and multipliers X, the FPG estimator
matrix of scores S(s, a).
gf (x, a) -( a) Ky. X ab(s,a),
is an unbiased estimator of the true policy gradient; i.e. VoJ(0)= = ETo. ( a)).
Proposition [ above shows that the VPG estimator given in Definition 2.1 can be expressed in our calculus as S1A o 1b, where 1 is all-ones matrix and, traditionally. 1o = qx note that one can still include other baselines in Equation 7 such as Ug. In other words, Proposition 7 /ttritlyy generalises the policy gradient theorem [43] and, by virtue of it's unbiasedness, thus retains all convergence guarantees. We also see that both COMA [9] and DRPGs [3] are special cases in which the influence network reflects the separation of agents with Ky square, and often diagonal matrix.
4.1 Variance Analysis
The variance reducing effect of FBs comprises two terms: 1. a quadratic and thus non-negative component which scales with the second moments of bf; and 2. a linear term which scales with the expected values of bf. This is shown the following result.
Proposition 2 (Variance Decomposition). Let 9: denote a gradient estimate for the ith factor of E-factored policy me (Equation Sj. Then. AV, V V[g -Vgg.) satisfies
AV. = az Boy(a) [00)'] + 2,3 [b]]
(8)
where 2; = V aa s). 0; =E Eoy(a> (<z =,) 2 and 3, = [(2, z.) (v + b])]
The first of these two terms is a "free lunch" which removes the targets that are not prohabilistically related to each factor. The linear term, on the other hand, couples the adjusted target with the entries that were removed by the baseline. This suggests that asymmetry and covariance can have regularising effect in VPGs that not present in FPGs - a manifestation of the properties of control variates [26.. Now, if we do not assume that the target functions are bounded, then the linear term in Equation 8 can grow arbitrarily in either direction, but we typically require that rewards are restricted to some compact subset R R to avoid this. Below, we show that if a similar requirement holds for each target function - namely, that infs,A the is well defined for each thy E V - then we can always construct
of mappings that constrain (8) be non-negative without biasing the gradient.
Corollary 4.1 (Non-Negative Variance Reduction). Let rb(s, a) be of the form in Equation 3 If (s)5,,)) a) 2 bb for all (8, a) E S A and j E [m], with [xby] < oc, then there exists a linear translation, th + 1/s
m 1== >ybbi which leaves the grudient unbiased but yields AV; 2 20
Interestingly, numerical experiments pair of continuum armed bandits suggest that this transfor- mation is seldom necessary; see seeuFe 3 As the number of policy factors and targets grow, so too does the potential discrepancy in magnitude between the quadratic and linear terms in Equation g The former starts to dominate even for small [Σ]. This is particularly prevalent when the influence matrix Ks is very sparse and the baselines have wide coverage over V. In other words, applying FBs when the influence network is very dense or even complete will not yield tangible benefits (e.g. in Atari games), but applying them to problem with a rich structure, such as traffic networks, will almost certainly yield a significant net reduction in variance.
Bias- Vass-varee Trade-Off. It is important to note that, in real-world problems, one does not always know the exact structure of the influence network underling an MDP ex ante. This poses a challenge since incorrectly removing edges can introduce bias and thus constrain the space of solutions that can be found by FPGs. Note, however, that this may not always be problem, since small amount
'This inequality can be made strict if either as > 0 or 3, > 0 - where the former equates to having a non-zero trace of the Fisher information matrix and a small > is added the translation.

---

Baadbric lare
Varaace Continattnn Ed
100
Ovakeds 2010
Tila
227
Dimensonolily
Demenstinnity1 1-1
(a) Search bandit: Cost(a) = ||a c|l, with fixed centroid vector c C R".
ReLU bandit: Cost(a) = = >n max (e,a, 0) with fixed sign vector E (-1,1}"
Figure 3: Variance decomposition of action-space dimensionality. Each term was computed using Monte-Carlo estimation with 10
symmetric log scale for bandit problems as function
samples and taking the arithmetic mean across all policy factors.
bias for large reduction in variance can be desirable. Furthermore, one could leverage curriculum learning to train the policy on (presumed) influence networks with increasing connectedness over time. This trade-off between bias and variance is present in many machine learning settings, and depends strongly on the problem at hand; we explore this empirically in in(Section 5.2)
4.2 Minimum Factorisation
For many classes of fully-observable MDPs, any policy factorisation is theoretically viable: we can fully factor the policy such that each action dimension is independent of all others; or, at the other extreme, treat the policy as a full joint distribution over A. This holds because, many classes of (fully-observablee MDPs, there exists least one deterministic optimal policy [55 351 The covariance acts as a driver of exploration, and it's initial value only affects the rate of convergence As result, most research matrix inversion. This poses an interesting question: there an "optimal" policy factorisation, Ig. associated with influence network G? Below offer possible characterisation.
isotropic Gaussian with diagonal covariance to avoid the cost of
Definition 4.2 (Minimum Factorisation). minimum factorisation (MF), Dg. of an influence net- work, G, is the minimum biclique vertex cover, disjoint amongst TA-
that for any Eg, each 0, Σg biclique (i.e. complete bipartite subgraph) of the original influence network g. and that the bipartite dimension is equal to the number of policy factors. For example, one can trivially verify that Figure 2b is an MF of the original graph; see also the reductions in Figure I] In essence, MF describes a complete partitioning over action vertices - so as to define a proper distribution - where each group a biclique with the same set of outgoing edges. The "minimum" qualifier then ensures that the maximum number of nodes are included each of these groups, a property which allows us to prove the following result:
follows from Definition 4.2
Theorem 4.1. The MF Eg always exists and is unique.
Minimum factorisation is a natural construction for the problem domains studied in this paper; see Section 5) It also yields factored policies which, generally, expose the minimum infimum bound on variance for a given influence network. This follows from the fact that an MF yields the greatest freedom to express covariance structure within each of the policy factors whilst also maximising the quadratic term in Eqquatin 8 fact, when each action corresponds to a single unique target, the MF enjoys lower bound on variance that is linear in the number of factors. Finally, we remark that, whilst closely related to vertex covering problems (which are known to be NP-complete [8]., we observed experimentally that finding the MF can be done trivially in polynomial time; see e.g.
Note that this is not true in general: the policy's 's covariance structure impacts the set of reachable solutions in cantially-observan MDPs and stochastic games, for example.
7

---

8.3
FPGs
uniform distribution, ~ U (-5.5) 5) and were held fixed between episodes. The policy as an isotropic Gaussian with fixed covariance, diag(1), and initial location vector μ 0. The influence network specified such that each policy factor, T. for i [n], used reward target (a(a)) - A,(a;) - A((a;), with (a)a) la - Gil, amounting to a collection of n forks (Figure Tal. provided in the VPGs (with (x))
017
Squared Ertor [-] -
VPGs
0.30
VPGs (with (or,a))
0.08
0.05
PGG (wich (66)
0.04
0.02
0.00
0.5
2.0 Treining iteration [10e]
Iterationn [10]]
(a) Convergence of CPGs (with w/o additional state-dependent baseline) compared with VPGs us- ing different basclines. The error bands denote the standard error the mean over 10 random seeds.
(b) Squared error between an and c. during learning for the search bandit with & = n
Figure 4: Performance analysis of CPGs on the search bandit domain.
Table I: Empirical wall-clock estimates for the time-complexity (iterations per second) of VPGs and FPGs, with and without additional baselines. For each algorithm, the mean and sample standard deviation were computed across the 10 random seeds used to generate Figure 4a
Method
Baseline
Mean [it /
Std Dev [it
10534
87
VPGs
M(s)
9885
81
b(s, a)
80
1
9950
157
FPGs
b(s)
9670
126
5 Numerical Experiments
5.1 Search Bandits
Consider an = 1000 dimensional continuum armed bandit with action space in R". and cost e|1
function: Cost(a) = l|a - + ((a), where e E R", 2 and Ç - R2 is a penalty function. This describes search problem in which the agent must locate the centroid subject to an retiionregularisattonn penalty. abstracts away the prediction aspects MDP settings, and allows us to focus only scalability; note that this problem is closely related to the bandit studied by Wu et al. (57] for the same purpose. our experiments, the centroids were initialised with a defined
The parameter vector, μa, updated each time step, and the hyperparameters appendix.
We began by examining the case where À = 0 and the co-ordinate axes were fully decoupled. For VPGs, we note that stability was only possible without baseline an extremely low learning rate was used; see the appendix. Including baseline dramatically improved performance, with the action- detionndeeendentt case, b(s, a), also leading to better asymptotic behaviour at the expense of two orders of magnitude longer train-time according to the wall-clock compared with all other algorithms (VPGs and FPGs); see [Table I] In comparison, FPGs, both with and without a learnt state-dependent baseline, yielded significantly reduced variance, leading faster learning, more consistent convergence and highly robust asymptotic stability.
We then studied the impact of coupling terms in the cost function; i.e. À > 0. For this, we considered
family of penalties taking the form of partially applied norms: (a( = V af with
1 < & n. This set of functions allowed us to vary the penalty attribution across the n factors of
A. Further examples demonstrating the performance advantage of FPGs for & n and & n/2

---

-0.7
-0.6
Gobal Return
59
-0.70
-0.7
-0.23
-0.8
Joint Policy (Giobal)
Factored Policy (Global)
-0.25
-0.9
Factored Policy [Localised]
150
20B
300
400
500
1ocal
Local
Local
Clobal
Training Iteration (-]
Baseline
(a) Convergence of joint/factored policies for the global reward, and using FPGs with the spatial base- line. Each curve depicts the mean value across 5 random seeds with standard error bands.
(b) Performance degradation as a function of the n- level spatial baseline approximation in 2 x 6 grid network. Each point is the average terminal value across seeds and with standard error bands.
Figure 5: Performance analysis of FPGs (with PPO and GAE) on the traffic network domain.
are given in the appendix. In both cases, the improvement due to FB adjustments was found to be non non-negative for every combination learning rate and action space. This confirms that FPGs can indeed handle coupled targets and retains the variance reduction benefits that were explored in Section 4.1 As an illustrative example, consider the case where & n 1 and all but the last action dimension are subject to a penalty. This is particularly challenging setting for VPGs because the magnitude of the combined cost function is much greater than A, (a,). leading to an aliasing the final component of the action vector in the gradient. The result, as exemplified in Figure 4b) was that VPGs favoured reduction of overall error, and was therefore exposed to poor per-dimension performance; hence the increased noise in the on error process. FPGs avoid this effect by attributing gradients directly.
5.2 Traffic Networks
We now consider classic traffic optimisation domain to demonstrate the scalability of our approach to large real-world problems. In particular, we consider variants of the (3 3) grid network benchmark environment originally proposed by Vinitsky et al. [5I] that is provided by the outstanding Flow framework [56] 21 In this setting, the RL agent is challenged with managing a set of traffic lights with the objective of minimising the delay to vehieles travelling in the network; the configuration should be taken as identical unless explicitly stated. This requires a significant level of co-ordination, and indeed multi-agent approaches have shown exemplary performance in this space [51] [54.. However, much as with the search bandit, the probability of aliasing effects increases substantially with the number of tights/intersection;;; i.e. the dimensionality of the action-space. This affects both single- and multi-agent approaches when the global reward used to optimise the policy.
To this end, we propose "baseline" that removes reward terms derived from streets/edges that are not directly connected to a given traffic light. This based on the hypothesis that the local problem is sufficiently isolated from the rest of the system that may still find a opttiall solution; much as with local-form models [27). Of course, this could introduce bias at the cost of variance if we are incorrect (see Section 4. but this turns out to be an effective trade-off as exemplified in Figure 5a In this plot we compare the performance of three policies learnt using PPO 38 and GAE [37 (with additional state-dependent baseline): (1) naïve joint policy over the 9-dimensional action-space trained against the global reward; (2) a shared policy trained on the global reward; and (3) shared policy using the local spatial baseline. In methods 2 and 3, shared policy refers to the of single univariate policy across all nine traffic lights, where only local information and identity variables are provided. The global reward in this case was defined the negative of the mean delay introduced in the system minus a scaled penalty on vehicles at near standstill; see the appendix for more details.
As expected, observe that the FBs improve learning efficiency, but, perhaps surprisingly, also find that the asymptotic behaviour also superior. We posit that this relates to the fact that, with fixed learning rate, stochastic gradient descent cannot distinguish between points within ball of the optimum solution with radius that scales with the variance on the estimator. In other words, significant reductions in variance, likelihood of reaching the true optimal solution by virtue of having much greater precision.
if they introduce small amount of bias, may increase the
Note that the standard errors may slightly underestimate the population level due the low sample size.

---

To better understand this trade-off, we also explored the impact of "expanding" the local baseline in larger system of 6 intersections. With this new baseline we retain reward terms derived from lights up to n edges away in either the east or west directions. The variable n thus provides a dial to directly tweak the bias and variance of the policy gradient estimator (i.e. increasing reduces bias but increases variance). The result, as shown in Figure 5b] suggest that performance decreases monotonically as a function of n. This corroborates the claim in SScciinn 4.1 that introducing some bias in exchange for reduction in variance can be worthwhile trade-off in large problems.
Conclusion
Factored policy gradients derive from the observation that many MOMDPs exhibit redundancy in their reward structure. Here, we have characterised this phenomenon using graphical modelling, and demonstrated that conditional independence between factors of the action-space and the optimisation targets can be exploited. The resulting family of algorithms subsume many existing approaches the literature. Our results in large-scale bandit and concurrent traffic management problems suggest that FPGs are highly suited to real-world problems, and may provide a way of scaling RL to domains that have hitherto remained intractable. What's ' more, FPGs are compatible with other techniques that improve policy gradient performance. For example, they can be extended to use natural gradients by pre-multiplying Equation by the inverse Fisher information matrix [77, and can even use additional baselines to reduce variance even further, as in Section 5.2 In future work we intend to address the following interesting questions: (a) Can we infer/adapt the structure of influence networks? (b) Are there canonical structures within S and K?? (c) What theoretical insights can be derived from more detailed analysis of the variance properties of FPGs? We argue that factored approaches such as FPGs which are complementary to ideas like influence-based abstraction [27 are a promising
direction for practical RL. Addressing some of these questions, we believe, would thus be of great value to the community.
Acknowledgments and Disclosure of Funding
The authors would like to acknowledge colleagues Joshua Lockhart, Jason Long and Rui Silva for their input and suggestions at various key stages of the research. This work was conducted by JPMorgan's 's AI Research group which has no external funding sources; ie. it self-funded project. No sources of financial competing interests (or otherwise) are attributed to this line of research.
Disclaimer This paper was prepared for informational purposes by the Artificial Intelligence Research group JPMorgan Chase Co and its affiliates ('J.P. Morgan"), and is not a product of the Research Department of J.P. Morgan. J.P. Morgan makes no representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This document is not intended as investment research or investment advice, or recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or such person would be unlawful.
2021 JPMorgan Chase Co. All rights reserved.
References
[1] Vivek S Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint, volume 48. Springer, 2009.
[2] Craig Boutilier, Thomas Dean, and Steve Hanks. Planning under uncertainty: Structural assumptions and computational leverage. In Proceedings of the Second European Workshop on Planning, pages 157-171, 1995.
[3] Jacopo Castellini, Sam Devlin, Frans A Oliehoek, and Rahul Savani. Difference Rewards Policy Gradients. In Proc. of AAMAS'21, 2021.
10

---

[4] Po-Wei Chou, Daniel Maturana, and Sebastian Scherer. Improving Stochastic Policy Gradients in Continuous Control with Deep Reinforcement Learning using the Beta Distribution. In Proc. of ICMI,, pages 834-843 843, 2017.
[5] Elena Congeduti, Alexander Mey, and Frans A Olichoek. Loss bounds for approximate influence-basee abstraction. arXiv preprint arXiv:2011.0178. 2020.
[6] Ivana Dusparic and Vinny Cahill. Autonomic Multi Multi-Policy Optimization in Pervasive Systems: Overview and evaluation. TAAS, 7(1):1-25, 2012.
[7] Carson Eisenach, Haichuan Yang. Ji Liu, and Han Liu. Marginal policy gradients: A unified family of estimators for bounded action spaces with applications. In Proc. of ICLR, 2019.
[8] Herbert Fleischner, Egbert Mujuni, Daniel Paulusma, and Stefan Szeider. Covering Graphs with Few Complete Bipartite Subgraphs. Theoretical Computer Science, 2009.
[9] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual Multi-Agent Policy Gradients. In Proc. of AAAI, 2018.
[10] Yasuhiro Fujita and Shin-ichi Maeda. Clipped Action Policy Gradient. In Proc. of ICML, pages 1597-1606, 2018.
[11] Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian Reinforce- ment Learning: A Survey. Foundations and Trends@ in Machine Learning. 8(5-6)3359 483, 2015.
[12] Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the Void: Optimizing control variates for black-box gradient estimation. In Proc. of ICLR, 2018.
[13] Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning. JMLR, 5:1471-1530, 2004.
[14] Olivier Guéant and Iuliia Manziuk. Deep Reinforcement Learning for Market Making in Corporate Bonds: Beating the Curse of Dimensionality. Applied Mathematical Finance, 26(5): 387-452, 2019.
[15] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient Solution Algorithms for Factored MDPs. JMLR, 19:399 468, 2003.
[16] Anderson Jonsson and Andrew Barto. Causal Graph Based Decomposition of Factored MDPs. JMLR, 7(11), 2006.
[17] Sham M Kakade. A Natural Policy Gradient. Proc. of NeurlPS, 14:1531-1538, 2001.
[18] Richard M Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972.
[19] Vijay R Konda and John N Tsitsiklis. Actor-Critic Algorithms. In Proc. of NeurIPS, pages 1008-1014, 2000.
[20] Jae Won Lee and O Jangmin. A Multi-Agent Q-Learning Framework for Optimizing Stock Trading Systems. In Proc. of DEXA, pages 153-162. Springer, 2002.
[21] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. RLlib: Abstractions for Distributed Reinforcement Learning. In Proc. of ICML, pages 3053-3062, 2018
[22] Hao Liu, Yihao Feng Yi Mao, Dengyong Zhou, Jian Peng, and Qiang Liu. Action-Dependent Control Variates for Policy Optimization via Stein Identity. In Proc. of ICLR, 2018.
[23] Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable Reinforcement Learning Through Causal Lens. In Proc. of AAAI, volume 34, pages 2493-2500, 2020.

---

[24] Patrick Mannion, Sam Devlin, Jim Duggan, and Enda Howley. Reward shaping for knowledge- based multi-objective multi-agent reinforcement learning. The Knowledge Engineering Review, 33, 2018.
[25] Shie Mannor and Nahum Shimkin. A Geometric Approach Multi Multi-Criterion Reinforcement Learning. JMLR, 5:325-360, 2004.
[26] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte Carlo Gradient Estimation in Machine Learning. JMLR, 21(132):1-62, 2020.
[27] Frans Olichoek, Stefan Witwicki, and Leslie Kaelbling. Influence-Bass Based Abstraction for Multiagent Systems. In Proc. of AAAI, volume 26, 2012.
[28] Frans Oliehoek, Stefan Witwicki. and Leslie Kaelbling. A sufficient statistic for influence in structured multiagent environments. Journal of Artificial Intelligence Research, 70:789-870, 8700, 2021.
[29] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic Mariance-Reducee Policy Gradient. In Proc. of ICML, pages 4026-4035, 2018.
[30] Yagna Patel. Optimizing Market Making using Multi-Agent Reinforcement Learning. arXiv preprint arXiv: 1812. 10252, 2018.
[31] Judea Pearl. Causality. Cambridge University Press, 2009.
[32] Judea Pearl and Dana Mackenzie. The Book of Why: The New Science of Cause and Effect. Basic Books, 2018.
[33] Jan Peters and Stefan Schaal. Policy Gradient Methods for Robotics. In Proc. of IEEE/RS), pages 2219-2225. IEEE, 2006.
[34] LA Prashanth and Mohammad Ghavamzadeh. for Discounted and Average Reward MDPs. Machine Learning, 105(3):367-417) 2016.
Actor-Critic Algorithms
[35] Martin L Puterman. [MJarkov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[36] Diederik Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. Survey of Multi-Ohjective Sequential Decision-Making. JAIR, 48:67-113, 2013.
[37] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- Dimensional Continuous Control using Generalized Advantage Estimation. arXiv preprint arXiv:/506.0244 2015.
[38] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. arXiv preprint arXiv.1707.06347 2017.
[39] David Silver, Leonard Newnham, David Barker, Suzanne Weller, and Jason McFall. Concurment Reinforcement Learning from Customer Interactions. In Proc. of ICML, pages 924-932, 2013.
[40] Thomas Spooner and Rahul Savani. Robust Market Making via Adversarial Reinforcement Learning. In Proc. IJCAI, pages 4590-4596, 7 2020. Special Track on Al in FinTech.
[41] Miguel Suau, Elena Congeduti, Rolf Starre, Aleksander Czechowski, and Frans A Olichock. Influence-aware memory for deep reinforcement learning. arXiv preprint 2019.
[42] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[43] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. Proc. NeurlPS, pages 1057-1063, 2000.
12

---

[44] Aviv Tamar, Dotan Di Castro, Ron Meir, and Peter Dayan. Integrating a Partial Model into Model Free Reinforcement Learning. JMLR, 13(6), 2012.
[45] Joseph A Tatman and Ross Shachter. Dynamic Programming and Influence Diagrams. IEEE Trunsactions on Systems, Man, and Cybernetics: Systems, 20(2):355-379 1990.
[46] Chen Tessler, Daniel J Mankowitz, and Shie Mannor. Reward Constrained Policy Optimization. In Proc. of ICLR, 2019.
[47] Philip S Thomas and Emma Brunskill. Policy Gradient Methods for Reinforcement Learning with Function Approximation and Action-Dependent Baselines. arXiv preprint S14i::170000644333 2017.
[48] Yi Tian, Jian Qian, and Suvrit Sra. Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes. Proc. of NeurlPS, 33, 2020.
[49] George Tucker, Surya Bhupatiraju, Shixiang Gu, Richard Turner, Zoubin Ghahramani, and Sergey Levine. The Mirage of Action- Deeien-Depnndntt Baselines in Reinforcement Learning. In Proc. of ICML, volume 80, pages 5015-5024, 10-15 Jul 2018.
[50] Kristof Van Moffaert, Tim Brys, Arjun Chandra, Lukas Esterle, Peter R Lewis, and Ann Nowé. A Novel Adaptive Weight Selection Algorithm for Multi-Objective Multi-Agent Reinforcement Learning. In Proc. of IJCN,, pages 2306-2314, 14. IEEE, 2014.
[51] Eugene Vinitsky, Aboudy Kreidich, Luc Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang. and Alexandre Bayen. Benchmarks for reinforcement learning in mixed-autonomy traffic. In Proc. of CoRL, pages 399-409, PMLR, 2018.
[52] Yuandou Wang, Hang Liu, Wanbo Zheng. Yunni Xia, Yawen Li, Peng Chen, Kunyin Guo, and Hong Xie. Multi-Objective Workflow Scheduling with Deep-Q- Seep----eetorr-BBaee Multi-Agent Reinforcement Learning. Access, 7:39974-39982, 2019.
[53] Lex Weaver and Nigel Tao. The Optimal Reward Baseline for Gradient-Based Reinforcement Learning. In Proc. of UAI, pages 538-545, 2001.
[54] Haoran Wei, Xuanzhang Liu, Lena Mashayekhy, and Keith Decker. Mixed-Autonomy Traffic Control with Proximal Policy Optimization. In Proc. of VNC, pages 1-8, 2019.
[55] Marco Wiering and Martijn van Otterlo. Reinforcement Learning: thee-offthe-AAr, volume 12. Springer Science & Business Media, 2012.
[56] Cathy Wu, Aboudy Kreidich, Kanaad Parvate, Eugene Vinitsky, and Alexandre M Bayen. Flow: modular learning framework for autonomy traffic. arXiv preprint urXiv:1710.0546. 2017.
[57] Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance Reduction for Policy Gradient with Action- Dependent Factorized Baselines. In Proc. of ICLR, 2018.
13


Reviews:
[{"review_id": "jjwZghXlA1G", "reviewer": "Reviewer_VuPN", "summary": "This paper studies the problem of policy learning in a factored Markov decision process (MDP). The factorization of the transition probability distribution is graphically described through a set of influence diagrams. The objective function is a linear combination of weighted kernel functions. The authors propose an efficient policy gradient algorithm to learn the optimal policy. Simulation results support the authors’ results.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper considers an interesting problem in policy learning factored MDPs. I haven’t checked the details of the proof, but the proposed algorithm seems reasonable. Since many decision-making problems in the real world where its system dynamics can be naturally decomposed into a set of independent components, the method presented here could have many practical applications across disciplines. \n\nIn simulations, the authors mainly compare against a vanilla policy gradient that does not exploit the underlying factored representation. I am curious how the authors’ method compares against other policy learning algorithms for factored MDPs, e.g., (Guestrin et al., 2003, 2004). Could the authors further elaborate on this?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- This work is mainly theoretical. Its long-term societal impact is unclear to see.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "H5Iv5J3Xvn", "reviewer": "Reviewer_BRAD", "summary": "This paper studies multi objective MDPs with a factorized action space and proposes a new “baseline” for policy gradient related actor-critic sorts of approaches for the class of problems that are of interest to them. They show variance reduction and perform experiments to gauge the power of the proposal. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the face of it, the paper makes contributions that seem quite reasonable to the actor-critic and policy gradient literature for a specific class of MDP problems: those involving factored action space and multiple objectives. I’m sure this class of problem is large enough such that the paper provides useful contributions to the literature. However, I do not have expertise in these subjects and will defer to my co-reviewers to gauge the work in this space. \n\nMy main concern with the paper is that it seems to have a major positioning problem. I have more expertise in graphical models and causality – and the problem with the paper’s positioning is probably why the paper was assigned to me. Unfortunately, the paper has very little to do with causality, even though the authors choose to mention causality to describe their factored model. There seems to be a trend these days where people add the word “causal” to terms. I find the phrase “causal policy gradients” to be unsuitable for their approach for many reasons, but primarily as it seems to imply that it applies to a broader class of problems than it really does. I strongly recommend changing the term and re-positioning the paper. The fact that problems can be factorized as described in the paper and that values could depend on different decision (action) variables is not at all surprising, and there is no need to mention causality (I mention some relevant literature on graphical models later). If the authors disagree, they should feel free to explain their choice of terminology. \n\nDetailed comments:\n\nP1: What are “daemon agents”?\n\nP2: The word “baseline” is used in a few places on this page, but it is not until much later that it becomes clear what this refers to. I suggest the authors modify the introduction to mention actor-critic and other ideas earlier, so that the contributions make sense to a general AI reader.\n\nP3: The description of factorization in the action space was not totally clear as described. What does it mean for actions to be “accessible” in an element-wise fashion? Does it simply mean that the action space is a cross-product of individual action spaces, and that they could individual affect different aspects of reward (like in Figure 1)? A real example would help here, and in other places. \n\nP3: On line 126, psi_1 is mentioned to be equivalent to q – should this be v?\n\nP4: The authors are perhaps not familiar with influence diagrams – these are graphical models for decision problems, including MDPs (including multi-objective one). Their influence network can be represented as an influence diagram, with arcs from decision/action variables to value nodes. The idea of factorization using additive value functions is well known in that literature. Here is an older paper primarily about dynamic problems, but the ideas extend to multi-objective problems too: \nJ. A. Tatman and R. D. Shachter (1990), Dynamic Programming and Influence Diagrams, IEEE Transactions on Systems, Man and Cybernetics 20(2):365-379.\n\nP4: I’m surprised that actions are never allowed to depend on other actions in a policy. What is the reason for this simplification?\n\nP4: The authors mention the market making problem in Section 3.1 as an application. Could they provide more detail? More motivation around the problem setting would help the paper greatly.\n\nP4: It looks like there is a self-reference in Def. 3.3.\n\nP4: “n” seems to be used both for the number of actions in the action space (earlier) but also for the cardinality of Sigma, which can probably be less than “n” in general. There is also an “m” mentioned earlier. Could the authors clarify please? \n\nP5: As mentioned earlier, I find “causal policy gradients” to be an absurd term for the method. I suggest changing the title of Section 4. Perhaps “factored policy gradients” or something like that.\n\nP6: I may have missed something but how can one tell the second term in Equation (8) is asymmetric. Is this inferred from the beta?\n\nP7: There are terms in Def. 4.2 that were not defined. Also – I found most of Section 4.2 hard to parse. Whatever I did understand, I did not find surprising. I was not able to fully appreciate the implications of this section. From what I could tell, the main contributions of the paper are around the variance results in Section 4.1.\n\nP7 and 8: Again, I did not appreciate Section 5.1. Perhaps this is because the example was abstract and did not give me a sense of the implications. How many objectives are involved in this synthetic example?\n\nP8: Example 7 should probably be Example 4a.\n\nP8: Why is “Flow” outstanding?\n\nP9: I find line 355 (“one of the most promising directions …”) an overstatement and not at all backed by the paper. Please remove or rephrase that line.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should clarify that their approach works for a specific sub-class of problems. Other than that, I don't see issues.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't have any specific ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EOT-uRqjr8T", "reviewer": "Reviewer_aQyY", "summary": "This paper proposes a policy gradient algorithm for MOMDPs with large factored action spaces, where the background knowledge on the MOMDP structure is given as an influence network. A new baseline for policy gradients is given that makes use of the MOMDP background knowledge and a factorisation of the RL policy. The paper analyses the favourable variance properties of the resulting policy gradient estimator. Empirical results are provided on a pedagogical bandit example, and a traffic control problem. The latter demonstrates applicability of the method even when the graphical assumptions only hold approximately. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\n+ The paper is the first I've seen to use causal background knowledge in this way to reduce the variance of policy gradient methods. \n+ Graphical causal models have been used before in multi-agent problems (citation 27) but not for use in policy gradient methods on single-policy MOMDPs. \n\n### Quality\n+ I enjoyed the results of section 4.1 and the discussion of a bias-variance tradeoff in practice. \n+ The experiments were thorough in the sense of studying properties of the approach beyond just performance. For example, the bias-variance tradeoff explored in figure 5b. \n- In figure 5a, it does not seem meaningful to plot standard error bars for 5 repeats. Perhaps the min and max across repeats would be more informative. In 5b, with only 5 repeats one could just plot all of the repeats instead of giving the standard error bar. \n- One of the main arguments for this approach in practice over using an action dependent baseline seems to be wall-clock time. Therefore I think including plots of this statistic in the appendix would be very valuable. \n\n### Clarity\n+ In general the writing is easy to follow and the figures ease the exposition well. \n- Citation (56) computes the minimum variance baseline under the assumption that $\\langle z_i, z_j \\rangle =0$ (using the notation of the appendix). The paper nor appendix doesn't go far in explaining why in general settings we would not expect $\\langle z_i, z_j \\rangle =0$ to hold. \n- I think when introducing the action-dependant baseline in the experiments a citation should be put after it for clarity (eg (56)). \n- The paper describes the minimum factorisation approach as \"principled\" (in the main text) and \"theoretically grounded\" (in the appendix). It seems that this is done due to the existance and uniquenesss results. I therefore think the language used is slightly misleading, since it would imply to me that it is somehow the optimal factorisation (for, say, variance reduction) however there does not seem to be a result of this sort. Some discussion of the variance properties is given on line 263, but if there is a formal result regarding this, I think it should be written as such. \n- Line 284 refers to figure 7. However, this is a figure in the appendix. The same is done with figure 9 on line 295. \n- In line 322-324, it was clear to me what methods 1 and 3 were. However it was not clear what method 2 was. Was this the same as the action dependent baseline? \n- Why did the action dependent baseline take two order of magnitude more wall-clock time? This was stated in section 5, but not explained. Was it due to fitting $\\omega$ (notation of appendix) each time to compute the baseline? \n\n### Significance\n+ The method is simple, has nice theoretical results, and solid empirical performance. The use of background knowledge (influence graph) is reasonable and experiments show robustness to the assumptions not holding. Improving sample efficiency of policy gradients is certainly a direction many people are interested in. \n- Traffic control problem is the only non-pedagogical example used for experiments. Demonstrating more general applicability would be nice. Perhaps in other cases it is not so easy to write down an approximate influence graph. \n- The paper assumes that there is a scalarisable additive reward, which in MOMDPs is not true in general without prior knowledge. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was satisfied with the discussion on societal impact in the broader impact statement. I felt that the limitations were transparently presented in the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel causal baseline to reduce the variance in policy gradient methods. All reviewers like the paper and I recommend acceptance. 
Decision: Accept (Poster)