MAP Propagation Algorithm: Faster Learning with a Team of Reinforcement Learning Agents
Authors: Stephen Chung
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Hierarchical Reinforcement Learning
Multi-agent Reinforcement Learning
Coagent Network
Backpropagation

Abstract: Nearly all state-of-the-art deep learning algorithms rely on error backpropagation, which is generally regarded as biologically implausible. An alternative way of training an artificial neural network is through treating each unit in the network as a reinforcement learning agent, and thus the network is considered as a team of agents. As such, all units can be trained by REINFORCE, a local learning rule modulated by a global signal that is more consistent with biologically observed forms of synaptic plasticity. Although this learning rule follows the gradient of return in expectation, it suffers from high variance and thus the low speed of learning, rendering it impractical to train deep networks. We therefore propose a novel algorithm called MAP propagation to reduce this variance significantly while retaining the local property of the learning rule. Experiments demonstrated that MAP propagation could solve common reinforcement learning tasks at a similar speed to backpropagation when applied to an actor-critic network. Our work thus allows for the broader application of teams of agents in deep reinforcement learning. 

MAP Propagation Algorithm: Faster Learning with a Team of Reinforcement Learning Agents
Stephen Chung
Department of Computer Science
University of Massachusetts Amherst
Amherst, MA 01003 minghaycchugguuasss edu
Abstract
Nearly all state-of-the-art deep learning algorithms rely on error backpropagation, which is generally regarded as biologically implausible. An alternative way of training an artificial neural network is through treating each unit in the network reinforcement learning agent, and thus the network is considered of agents. As such, all units can be trained by REINFORCE, a local learning rule modulated by global signal that is more consistent with biologically observed forms of synaptic plasticity. Although this learning rule follows the gradient of return in expectation, it suffers from high variance and thus the low speed learning, rendering it impractical to train deep networks. We therefore propose a novel algorithm called MAP propagation reduce this variance significantly while retaining the local property of the learning rule. Experiments demonstrated that MAP propagation could solve common reinforcement learning tasks similar speed to backpropagation when applied to an actor-critic network. Our work thus allows for the broader application of teams of agents in deep reinforcement learning.
team
Introduction
Error backpropagation algorithm (backprop) [1 efficiently computes the gradient of an objective function with respect to parameters, by iterating backward from the last layer of a multi-layer artificial neural network (ANN). However, backprop is generally regarded as being biologically implausible 2 4 6
First, the learning rule given by backprop is non-local, as relies on information other than input and output of neuron-like unit computed in the feedforward phase; while biologically-observe synaptic plasticity depends mostly on local information (e.g. spike-timing- dependent plasticity (STDP) [8) and possibly some global signals (e.g. reward-modulated spike- timing-dependee plasticity (R-STP)) 8 (0)). Second, backprop requires precise coordination between feedforward and feedback connections, because the feedforward value has to be retained until error signals arrive; while it is unclear how a biological system can coordinate an entire network to alternate between feedforward and feedback phases precisely. Third, backprop requires synaptic symmetry in the forward and backward paths, rendering it biologically implausible. Nonetheless, recent work has demonstrated that this symmetry may not be necessary for backprop due to the 'feedback alignment' phenomenon
13.
Alternatively, REINFORCE 14] could be applied to all units in the network to train an ANN as more biologically plausible way learning. It is shown that the learning rule gives an unbiased estimate of the gradient of return [14]. Another interpretation of this relates to viewing each unit as reinforcement learning (RL) agent, with each agent trying to maximize the global reward. Such a team of agents is also known coagent network [15]. However, coagent networks can only solve
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

simple tasks due to the high variance associated with the learning rule and thus the low speed of learning. The high variance stems from the lack of structural credit assignment, i.c. a single scalar reward is used to evaluate the action of all agents in the network.
To address this high variance associated with REINFORCE, we propose novel algorithm that significantly reduces the variance while retaining the local property of the learning rule. We call this newly proposed algorithm maximum posteriori (MAP) propagation. Essentially, MAP propagation replaces the hidden units' values with their MAP estimates conditioned on the action chosen, or equivalently, minimizes the energy function of the network, before applying REINFORCE. We prove that for network with normally distributed hidden units, by minimizing the energy function of the network, the parameter update given by REINFORCE and backprop (with the reparametrization trick) becomes the same, thus establishing a connection between REINFORCE and backprop. Our experiments show that team of agents trained with MAP propagation can learn much faster than REINFORCE, such that the team of agents can solve common RI. tasks at a similar (or higher) speed compared to an ANN trained by backprop, as well as exhibiting sophisticated exploration that differs from an ANN trained by backprop.
The novel MAP propagation algorithm represents a new class of algorithm to train an ANN that is more biologically plausible than backprop and maintains a comparable learning speed to backprop at the same time. Our work also opens the prospect of the broader application of teams of agents, called coagent networks [15], in deep RL.
2 Background and Notation
We consider a Markov Decision Process (MDP) defined by a tuple
R. y, do). where S is finite set of states of an agent's 's environment (although this work can be extended to the infinite state case), AA is a finite set of actions, P S x A x S + [0. 1] is a transition function giving the dynamics of the environment, R S x A + R is reward function, 7 E [0, 1] is discount factor, and dg S - 1] is an initial state distribution. Denoting the state, action, and reward signal at time by St, At, and R, respectively, P(s, a, s') = Pr(S.+1 = s S R(s,a) = E = 8, A, = a). and do(s) = Pr(Sn = s), where P and d, are valid probability mass functions. An episode is sequence of states, actions, and rewards, starting from 0 and continuing until reaching the terminal state. For any learning methods, we can measure its performance as it improves with experience over multiple episodes, which makes up run.
A, a).
Letting G = ΣE= 7tt RRt denote the infinite-horizer discounted return accrued after acting at time t, we interested in finding, or approximating, a policy S x A + [0. 1] such that for any time t 2 0, selecting actions according to x(s, a) = Pr(A, = a S. = s) maximizes the expected return |x]. The value function for policy и is V where for all E S, V (s) = E[G.|S, = s, m). which can be shown to be independent of t for the anfinitehhorizon case we are considering.
Here we restrict attention to policies computed by multi-layer networks consisting of L layers of stochastic units. Let H² E (² denote the activation values of the units in layer 1 at time t and n()) denote the number of units in layer 1. For any t 2 O. we also let H S,, H
A,, and H, = (H. H? .??.... H.-113. We call any elements in H, a hidden layer and H. the output layer. The distribution of H!; conditional on H/-1 is given by my : (R=((-)) x Ra(() - [0, 1). such that for any h² W'), where W is the parameter of layer (. We also denote all parameters of the network as W {W1 W .... 34.. To sample an action A,
t 2 0, Ti (h'-1,,110 nt;; w') = Pr(Ht = A n'|m!
from the network, we iteratively sample H; 77 (H) : W from 1 1 to L.
We say a layer 1 is normally distributed if n, distribution with mean g (H; :''), where g¹ (- + (²)() is differentiable function, and fixed standard deviation dt A common choice of is a linear transformation followed by an activation function; that is, g - ) f(W' -1 where of is a non-linear activation function such as softplus or rectified linear unit (ReLU) and W E (=(()x((-11) We also define the energy function E : (R) (2) x ... x ( + [0, oc) as F();; a) = - log Pr( H, = h.S,, 8, A, = a). which can be shown to be independent of t.
W/) = " of), the normal
2

---

The case we consider here is one in which all the units of the network implement an RL algorithm and share the same reward signal. These networks can therefore be considered as teams of agents (agent here refers to an RI. agent [16]) which have also been called coagent networks [1]]
We denote v..f as the gradient of w.r.t. J, A as the transpose of matrix A, and V (A)(P((A) as the shorthand for V. (Pr(A = a)). For a random variable X with a distribution that de- pends on parameter W and random variable Y, we call h( Y.) the re-parameterization of X by Z conditioned on Y if h(2; W, Y) and X have the same conditional distribution; that is, Pr(h(Z;W: Y) = x|Y = y) Pr(X = x z y; W) for all values of x, y and W, where Z is an independent random variable with distribution that does not depend on parameter W and h is an invertible and differentiable function. In case X has a multi-layer structure. we denote h'(Z; W. Y) as the 1th layer in h(Z; W, Y) and h as the inverse of h. In general, we use the superscript to denote the 1th layer in variable if the variable has multi-layer structure. Also, for all distributions discussed in this paper, the probability mass function is replaced by probability density function if the random variable is continuous.
3 Algorithm
3.1 MAP Propagation
MAP propagation is based on REINFORCE applied to each hidden unit with the same global reinforcement signal. To reduce the variance associated with the learning rule, we note that this variance can be reduced by using the expected parameter update conditioned on the state and the selected action instead. However, this expected parameter update is generally intractable to compute analytically. Therefore, we propose to use the maximum a posteriori (MAP) estimate to approximate the expected parameter update. This makes the resulting learning rule biased but reduces the variance significantly. The details of MAP propagation are as below.
The gradient of return with respect to W' (where I E {1.2..... L} in all discussion below unless stated otherwise) can be estimated by REINFORCE, also known as likelihood ratio estimators:
2
V W E(G,]
(k-0 W log Pr(A.(Ss)..
We can show that the terms in the summation of 1 also equal E| w log ( HT;: W'), which is the REINFORCE learning rule applied each hidden unit with the same global reinforce- ment signal Gy:
Theorem 1. Let the policy be a multi-layer network of stochastic units as defined in Section 2 For any 2 0 and l E (1,,2...,,) L}.
E[G.V Wi log (r(A)S(::)) = E|G, V log (H) HH:: W.)
(2)
The proof is in Appendix B. Note that this theorem is also proved by Williams 14]. This shows that can apply REINFORCE to each unit of the network, and the learning rule still gives an unbiased estimate of the gradient of the return. Therefore, denoting a as the step size, we can update parameters by the following stochastic gradient ascent rule:
W'e W + aG, we log " W²).
However, this learning rule suffers from high variance since a single reward, which results from the exploration of all units, is used to evaluate actions of all units, making the learning rule scale poorly with the number of units in the network. To reduce the variance, we notice that we can replace Vw log m ( Hi;; Wi) in learning rule (3) by E[[ wr log TI (H) ,!I'; W Ar), noting that (see Appendix B. for the details; at the R. R.H.S., the outer expectation is taken over S., A, and G., while the inner expectaion is taken over H!! and H!):
B V Wt log m((!) w = EJG, W[V log (o! HH'; W A.].
(4)
This can reduce variance since the variance associated with the stochastic noise of hidden units is removed in the learning rule (see Appendix B.6 for the proof). The learning rule now becomes:
w/ +- w' + aGG V wi log mi (HL HH's w (S:
(5)
3

---

Since (3) is following gradient of return in expectation, and the expected update value of (3) and
(5) the same, we conclude that (5) is also a valid learning rule as follows the gradient of
return in expectation. However, we note that E w log my H Hi;; W Ar] in (5) is generally
intractable to compute analytically. Instead, we propose to use the MAP estimate to approximate this
term
E wt log TT ",, W A,] ~ Vwi log ( .H::
(6)
where H, h Pr(H, h,]S,,, A²). There are many methods to approximate H,, such as hill-climbing methods. In case of hidden units being continuous, we can approximate H. by running gradient ascent on log Pr( H, [S, A4) as function of He for fixed St and A,, such that H; approaches H₂ H2 can be initialized the value sampled from the network when sampling action A.. To be concrete, before applying learning rule (3) we first run gradient ascent on H, for N steps:
H₂ - H₂ + VVH, log Pr( (rHH,S AA)-
For 1 E (1, (1,2....,A T. 11, this is equivalent to (see Appendix B.4 for the details):
H + H + a(V in log m (H) H V #i log my (H H W))).
(8)
This update rule maximizes the probability of hidden units' value given the state and the action with respect to hidden units' value. Based on the definition of energy functions in Section 2 the update rule of hidden units can also be seen as minimizing the energy function E(H;; S,, A.) 11
After updating H, for N steps by (8) we obtain an estimate of Hr, denoted as H,, and apply the following learning rule to learn the parameters of network:
(9) We call the algorithm that applies REINFORCE after replacing the value of hidden units by their approximated MAP estimate MAP propagation. The pseudo-code of MAP propagation with gradient ascent approximate Hi, can be found in Algorithm I in Appendix A. Note that N recovers the special case of pure REINFORCE.
W + W + aG; V wa log T ( "H; (/:W.)
Similar to actor-critic networks [16, we can also train critic network to estimate the state-value, (T(S)), so G2 in (9) can be replaced by TD error 6, = R, + (V+45)) - V*(S)) and the whole algorithm can be implemented online. To better facilitate temporal credit assignment, we can also use eligibility traces to replace the gradient in (9), using the same idea of actor-critic networks with eligibility trace 16). The pseudo-code of it can be found in Algorithm 2 in Appendix A.
team of agents can trained by MAP propagation to estimate the state-value, such that separate team of agents can fulfill the role of critic network, and the whole actor-critic network can be trained without backprop. A simple way to achieve this is to convert the estimation of state-valus to an RL task, but this conversion is inefficient since the information of optimal actions is lost (the agent only knows a scalar reward but not the target output). Appendix C proposes a new learning rule to train a team of agents estimate the -tauu by MAP propagation efficiently based on the information of optimal actions.
Essentially, MAP propagation is equivalent to applying REINFORCE after minimizing the energy function. As there are many studies on the biological plausibility of REINFORCE, we refer readers to the book of Sutton and Barto [16] for a review and discussion of the connection between REIN- FORCE and neuroscience. The main difference between MAP propagation and REINFORCE the minimization of the energy function given by the update rule (8) This update rule is local as it only depends on the units one layer above and below based on feedforward and feedback connections. There is much evidence that feedback signals in brains alter neural activity 7 [ supporting the use of feedback connections in MAP propagation. The update rule can also be performed in parallel for all layers, removing the need for precise coordination between feedforward and feedback connections as in backprop. However, the update rule requires the feedback weight to be symmetric of the feedforward weight and different values be propagated through feedforward and feedback connections.
MAP propagation fits well into the recently proposed NGRAD hypothesis 7 which hypothesizes that the cortex uses differences in activity states to drive learning. The main idea of NGRAD is that "higher- level activities can nudge lower-level activities towards values that are more consistent with the
We let A
H² St. Hi denote the 1th layer in Hi for 1 E 21, L 1). and A.! -Ht Ac-

---

higher-level activity", which also describes the process of energy minimization in MAP propagation. detailed discussion of the biological plausibility of MAP propagation and its relationship with the NGRAD hypothesis can be found in Appendix F.
3.2 Relationship with Backpropagation
A network of stochastic units cannot be directly trained by backprop. However, assuming that there exists a re-parameterization of H, by Z, conditioned on S,, denoted by h (Ze; W, St). then we can
update parameters using backprop with the re-parameteriiztion trick [99] that is, for I {1,2, ... L}:
W W oG, Ww log (20 S,),,, A,,
(10)
It can be shown that this learning rule follows the gradient of return in expectation (See Appendix B.5 for the proof). Using similar argument in MAP propagation, we can reduce the variance associated with the learning rule by minimizing the energy function before applying the learning rule.
Interestingly, for a network with all hidden layers being normally distributed, when the values of hidden layers are settled to a stationary point of the energy function, the parameter update given by backprop with the reparametrization trick in (T is equivalent to the parameter update given by REINFORCE in 3
Theorem 2. Let the policy be a multi multi-layer network of stochastic units with all hidden layers normally
distributed as defined in Section 2 There exists a re-parameterization of He by 74 conditioned on Se that is independent oft, t, denoted by hZ W, St), such that for any h E (1)(1) x xR x... (I.-1 E (a(1) x (m() (R...)(((I.I)) and a E A. V a.))
{1,2, .... L), S.
and & = h (h;; W, s). then
W log my (id W Vw n. (1 (2;
(11)
The proof is in Appendix B.2. In other words, by nudging the values of units in lower layers towards values that are more consistent with the value of units in the final layer, the parameter update given by REINFORCE becomes the same as backprop with the reparametrization trick. With N - oc and sufficiently small, under the update rule 77. H, will converge to the stationary point of the energy function. Therefore, the parameter update given by MAP propagation converges to the parameter update given by backprop with the reparametrization trick after minimizing the energy function.
Despite the close relationship between MAP propagation and backprop, there are key differences between the two algorithms. Compared to backprop, one major limitation of MAP propagation is that it can only be applied RL tasks. MAP propagation also more computationally expensive than backprop due to the minimization of the energy function in every step. However, MAP propagation can be applied to network of discrete units. Moreover, MAP propagation does not require non-local feedback signals or precise coordination between feedforward and feedback pathways, which makes it more biologically plausible than backprop.
To see that MAP propagation is more computationally expensive than backprop, denote L as the number of layers in the network and N the number of steps in the energy minimization (the inner loop). MAP propagation requires LN layer updates during each step of energy minimization, while backprop requires L layer updates compute the feedback signals (iterating from the top layers). Therefore, MAP propagation takes N times more layer updates than backprop. However, the LN layer updates in MAP propagation can be done in parallel for all layers, so the time complexity for a single step of MAP propagation can be reduced to ( from O(LN) if the update is done in parallel. For backprop, parallel computation of feedback signals is not possible, so the time complexity for a single step of backprop remains (I.).
4 Related Work
Local learning rules based on MAP estimates of latent variables have been proposed in both unsu- pervised and supervised learning tasks. For unsupervised learning tasks, Bengio et al. [5] proposed training a deep generative model by using MAP estimate to infer the value of latent variables, condi- tioned on observed variables; in the same work, they also proposed to learn the feedback weights
We let he s. denote the th layer in h for l E (1,2, L 1). and ht
5

---

such that the constraint of symmetric weight can be removed. This idea can also possibly be applied
to our algorithm. For supervised learning tasks, Whittington and Bogacz [20] proposed training a deep network with local learning rules based on MAP inference and clipping the output value of the network to the target value. In contrast to these works, MAP propagation applies to RI, tasks and
does not require clipping any units' values.
Besides algorithms based on MAP estimates, many biologically plausible alternatives to backprop have been proposed. Biologically plausible learning rules based on reward prediction errors and
attentional feedback have also been studied [2] 22 23]; : but these learning rules mostly require a non-local feedback signal. Moreover, there have been efforts to study local learning rules based on
contrastive divergence or nudging the values of output units towards the target value [24] |5 26). See the work of Lillicrap et al. 7 for a comprchensive review of algorithms that approximate backprop with local learning rules based on the differences in units' values. Contrary to these works, MAP propagation requires neither the temporal difference in units' value nor multiple phases of learning.
Another perspective of training a multi-level network of stochastic units relates viewing each unit as an RL agent, forming a hierarchy of agents. In hierarchical RL, Levy et al. [27] proposed learning a multi-level hierarchy with hindsight actions, which is similar to our idea of replacing the values of hidden layers with the MAP estimates. The special case of a team of agents forming a network to solve a task in a cooperative way was first proposed by Tsetlin 28 and later by Barto [29]. and a comprehensive review can be found in chapter 15.10 of the book of Sutton and Barto 16. Such team of agents recently called coagent networks [15] and theories relating training coagent networks have been studied [I5] 30 31. However, coagent networks learn much slower than an ANN trained by backprop due to the high variance associated with the learning rule. few methods have been proposed to reduce this variance. Thomas [15] proposed to disable exploration of units randomly, but the learning speed is still not comparable to backprop. Chung (32) proposed the Weight Maximization algorithm, which replaces the global reward in the learning rule with new local reward signal, and showed that this change of reward signal can reduce the variance effectively.
In addition, there is a large amount of literature on methods for training a network of stochastic units. review can be found in the work of Weber et al. [33), which includes the re-parametrization trick 34 and REINFORCE (14). They introduced methods to reduce the variance of the estimate, such as baseline and critic. These ideas are orthogonal to the use of MAP estimate to reduce the variance associated with REINFORCE.
Experiments
To test the algorithm, we first consider a single-time-ster MDP that is similar to the multiplexer task (9). This is to test the performance of the algorithm an actor. Then consider a scalar regression task to test the performance of the algorithm as a critic. Finally, we consider some standard RI tasks to test the performance of the algorithm as both an actor and critic.
In the below tasks, all the teams of agents (or coagent networks) have the same architecture: a two-hiddenn-layr network, with the first hidden layer having 64 units, the second hidden layer having 32 units, and the output layer having one unit. All hidden layers are normally distributed with for
T(( ) =
2, and ((x) = log(1 + exp(x)), the softplus function. For the network in multiplexer task and the actor network with discrete output, the output unit's distribution is given by the softmax function on the previous layer, i.c. Ty (H a; w²)= softmaxx (W 1= 11 I/T), where T > is scalar hyperparameter representing the temperature. For the network in the scalar regression task, the critic network and the actor network with continuous output, the output unit's distribution is normally distributed with mean given by linear transformation of the previous layer's 's value and a fixed variance, i.e. n ( (H--1, - W*) = N(W H''11 oz). We used N 20 in MAP propagation. Other hyperparameters and details of experiments can be found in Appendix D.
(W
5.1 Multiplexer Task
We consider a single-time-step MDP that is similar to the k-bit multiplexer task. In our single-time- step MDP, the state is sampled from all possible values of binary vector of size h + 2 with equal probability. The action set is {-1, 1), and give reward of 1 if the action of the agent is the

---

MAP Prop (SU)
Running Average Reward
0.8
Backprop
2.0
MAP Propagation
REINFORCE
REINFORCE with [15]
1.5
0.4
Backprop
1.0
0.5
0.0
3000 4000 5000
8000
Training Step
Training Step
Multiplexer
(b) Scalar Regression
Figure I: Running average rewards over the last 10 episodes in multiplexer task and scalar regression task. Results are averaged over 10 independent runs, and shaded area represents standard deviation over the runs.
500
-100
400
MAP Propagation
Episode Return
-150
Episoda Return
REINFORCE
REINFORCE with [15]
300
Backprap
250
MAP Propagation
REINFORCE REINFORCE with [15]
-300
Backprop
100
150
200
250
300
350
400
450
500
200
400
600
800
1000
Episode
Episode
(a) Acrobot
(b) CartPolc
200
75
100
Episode Return
Epicode Return
0
-25
-100
MAP Propagation
REINFORCE
-75
REINFORCE
-200
Backprap
[15]
-00
Backprop
[15]
500
1000
1500
2000
2500
100
150
200
250
Episode
Episodo
(c) LunarLander
(d) MountainCar
Figure 2: Running average returns over the last 100 episodes in Acrobot, CartPole, LunarLLnnerr and MountainCar. Results are averaged over 10 independent runs, and shaded area represents standard deviation over the runs.

---

Table 1: Average return over all episodes.
Acrobot
CartPole
LunarLander
MountainCar
Mean
Std.
Mean
Std.
Mean
Std.
Mean
Std.
MAP Propagation REINFORCE
-100.29
5.40
459.70
13.89
127.88
24.57
39.45
30.48
-148.42
47.65
47.29
8.22
-62.05
16.16
-35.52
0.65
REINFORCE with [.]
-149.11
33.50
112.58
42.54
-54.61
23.47
-4.65
0.21
Backprop
-106.29
15.00
458.96
9.44
104.92
31.98
4.30
59.28
desired action and -1 otherwise. The desired action is given by the output of a multiplexer, with the input of the multiplexer being the state. We consider here, so the dimension of the state space is 37.
We used Algorithm for training a team of agents by MAP propagation. We consider three baselines: 1. REINFORCE A team of agents trained entirely by REINFORCE; 2. REINFORCE with [15] A team of agents trained entirely by REINFORCE but with the variance reduction method considered by Thomas [3]; 3. Backprop- An ANN with a similar architecture where the output unit is trained by REINFORCE and hidden units are trained by backprop.
The results are shown in Fig | We observe that MAP propagation performs much better than the two REINFORCE baselines. The result suggests that MAP propagation improve the learning speed of REINFORCE significantly, such that its learning speed is comparable to backprop.
5.2 Scalar Regression Task
In the following, we consider scalar regression task, The dimension of input is and follows the standard normal distribution. The target output (a real scalar) is computed by one-hidden-layer ANN with weights chosen randomly. The goal of the task to predict the target output given the input.
For MAP propagation, we used Algorithm and tested two variants. In the first variant that labeled as 'MAP Prop (RL)', we treated the task as single-time-ster MDP with the negative L2 loss as the reward and trained the network using Algorithm 1. the second variant that labeled as 'MAP Prop (SLY', we replaced the learning rule in Algorithm I with the learning rule proposed in Appendix C, which incorporates the value target output. For the baseline, we trained an ANN with a similar architecture by gradient descent on the 1.2 loss.
The results are shown in Fig We observe that if we directly use the negative L2 loss the reward, then the learning speed of MAP propagation is significantly lower than backprop since the information of target output is not incorporated. On the other hand, if we use the learning rule in Appendix C to incorporate the information of target output, then the learning speed of MAP propagation is comparable to backprop. However, the asymptotic performance of MAP propagation is slightly worse than backprop, which is due to the stochastic property of teams of agents. Nonetheless, this may not be a problem when applying MAP propagation train a critic network, since the value function to be estimated is also constantly changing with the policy function.
5.3 Reinforcement Learning Task
In the following, we consider four standard RL. tasks: Acrobot, CartPole, Lunarl-ander and continuous MountainCar in OpenAl's Gym. For MAP propagation, we use the actor-critic network with eligibility traces given by Algorithm 2, and the critic network is trained by the learning rule proposed in Appendix C. We consider three baselines. For the first and second baseline, the actor network is a team of agents trained entirely by REINFORCE. However, since REINFORCE cannot train critic network directly and it is inefficient to convert the state-value estimation task an RL task, we used an ANN with a similar architecture trained by backprop as the critic network. We also used the variance reduction method considered by Thomas [15] in the second baseline. We used eligibility traces in the training of both the actor and the critic network. For the third baseline, we used actor-critic with eligibility traces (episodic) [6] trained by backprop. Both actor and critic networks are ANNs with an architecture similar to the team of agents.
8

---

The average return over ten independent runs is shown in Fig 2 Let G denote the average return of all episodes. The mean and standard deviation of G over the ten runs can be found in Table For all RL tasks, we observe that MAP propagation has a better performance than the baselines in terms of the average return G. The result demonstrates that a team of agents trained with MAP propagation can learn much faster than a team of agents trained with REINFORCE, such that the team of agents can solve common RL tasks at a similar (or higher) speed compared to an ANN trained by backprop.
Although there are other algorithms besides actor-critic networks that can solve RL tasks more efficiently, the present work aims to compare different training methods for hidden units in an actor- critic network. Teams of agents trained by MAP propagation can also be applied to algorithms besides actor-critic networks, such as variants of actor-critic networks like Proximal Policy Optimization (35] and action-value value based methods like Q-Learning [16].
We also notice that MAP Prop performs better than backprop tasks where a high degree of exploration is required. For example, MAP propagation performs slightly worse than backprop on the multiplexer task but much better than backprop on the MountainCar task. This may suggest that teams of agents trained with MAP propagation can have better exploration than an ANN trained with backprop. This is further corroborated by the analysis of agents' behaviors on MountainCar, a task where an agent can easily be stuck in the local optima. For backprop, we found that agents in most of the runs are stuck in early episodes even with the use of entropy regularization [36]. In contrast, a team of agents trained by MAP propagation can reach the goal of the task successfully in all runs. A detailed analysis of this can be found in Appendix E. One possible explanation for the better exploration is that actions of agents in lower layers can be considered as abstract actions, and the exploration of these agents corresponds to exploration beyond the primitive actions.
Future Work and Conclusion
The ability to train teams of agents efficiently leads to many possible future directions. First, the local property of the learning rule points to the possibility of implementing MAP propagation asynchronously, such that it can be implemented efficiently with neuromorphic circuits (37. Second, agents in the team can have different temporal resolution, such that the actions of agents can be extended temporally and become options 38), yielding better exploration and learning behavior.
In conclusion, we propose a new algorithm that reduces the variance associated with REINFORCE and thus significantly increases the learning speed in the training of a team of agents. The proposed algorithm also more biologically plausible than backprop while maintaining a comparable learning speed to backprop. Our work opens the prospect of the broader application of teams of agents in deep RL. Our experiments also suggest a team of agents trained by MAP propagation can have more sophisticated exploration compared to an ANN trained by backprop.
7 Acknowledgment
We would like to thank Andrew G. Barto, who inspired this research and provided valuable insights and comments, as well as Andy K.P. Chan for feedback and discussions.
References
[1] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. Nature, 323(6088):533-536, 1986.
[2] Francis Crick. The recent excitement about neural networks. Nature, 337 1989.
[3] Pietro Mazzoni, Richard A Andersen, and Michael I Jordan. A more biologically plausi- ble learning rule for neural networks. Proceedings of the National Academy of Sciences, 88(10):44334441 1991.
[4] Randall C C'Reellly. Biologically plausible error-driven learning using local activation differ- ences: The generalized recirculation algorithm. Neural computation, 8(5):895-99) 998, 1996.
[5] Yoshua Bengio, Dong-Hyun Lee, Jorg Bornschein, Thomas Mesnard, and Zhouhan Lin, Towards biologically plausible deep learning. preprint arXiv:1502.04155 2015.

---

[6] Demis Hassabis, Dharshan Kumaran, Christopher Summerfield. and Matthew Botvinick. Neuroscience-inspinn artificial intelligence. Neuron, 95(2):245-258, 2017.
[7] Timothy P Lillicrap, Adam Santoro, Luke Marris, Colin Akerman, and Geoffrey Hinton. Backpropagation and the brain. Nature Reviews Neuroscience, 21(6):335-346, 2020.
[8] Wulfram Gerstner, Werner M Kistler, Richard Naud, and Liam Paninski. Neuronal dynamics: From single neurons networks and models of cognition. Cambridge University Press, 2014.
[9] Räzvan Florian. Reinforcement learning through modulation of spike-timing-deeendeell synaptic plasticity. Neural computation, 196)):166-1502, 2007.
[10] Verena Pawlak, Jeffery Wickens, Alfredo Kirkwood, and Jason ND Kerr. Timing is not everything: neuromodulation opens the stdp gate. Frontiers in synaptic neuroscience, 2:146, 2010.
[11] Timothy P Lillicrap, Daniel Cownden, Douglas B Tweed, and Colin J Akerman. Random feedback weights support learning in deep neural networks. arXiv preprint arXiv:1411.0247 2014.
[12] Timothy P Lillierap, Daniel Cownden, Douglas B Tweed, and Colin J Akerman. Random synap- tic feedback weights support error backpropagation for deep learning. Nature communications, 7(1):1-10, 2016.
[13] Qianli Liao, Joel Leibo, and Tomaso Poggio. How important is weight symmetry in back- propagation? In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, page 1837-1844, 2016.
[14] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-22 256,, 1992.
[15] Philip S Thomas. Policy gradient coagent networks. In Advances in Neural Information Processing Systems, pages 1944-1952, 2011.
[16] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[17] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, and F Huang. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
[18] Pieter R Roelfsema and Anthony Holtmaat. Control of synaptic plasticity in deep cortical networks. Nature Reviews Neuroscience, 19(3):166, 2018.
[19] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[20] James CR Whittington and Rafal Bogaez. An approximation of the error backpropagation algo- rithm in a predictive coding network with local hebbian synaptic plasticity. Neural computation, 29(5): 1262, 2017.
[21] Isabella Pozzi, Sander Bohte, and Pieter Roelfsema. Attention-gated brain propagation: How the brain can implement reward-based error backpropagation. Advances in Neural Information Processing Systems, volume 33, 2020.
[22] Pieter R Roelfsema and Arjen Ooyen. Attention-gated reinforcement learning of internal representations for classification. Neural computation, 17(10):117-22144 2005.
[23] Jaldert O Rombouts, Sander M Bohte, and Pieter R Roelfsema. How attention create synaptic tags for the learning of working memories in sequential tasks. PLoS Comput Biol, 1 110))e10044000 2015.
[24] Javier R Movellan. Contrastive hebbian learning in the continuous hopfield model. In Connec- tionist models, pages 10-17. Elsevier, 1991.
10

---

[25] Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-1800, 2002.
[26] Benjamin Scellier and Yoshua Bengio. Equilibrium propagation: Bridging the gap between energy-based models and backpropagation. Frontiers in compulational neuroscience, 11:24, 2017.
[27] Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierar- chies with hindsight. In International Conference Learning Representations, 2019.
[28] Mikhail Lvovich Tsetlin. Automaton theory and modeling of biological systems. Academic Press, 1973.
[29] Andrew G Barto. Learning by statistical cooperation of self-interested neuron-like like computing elements. Human Neurobiology, 4(4):229 256, 1985.
[30] James Kostas, Chris Nota, and Philip Thomas. Asynchronous coagent networks. International Conference Machine Learning, pages 8426-5435 PMLR, 2020.
[31] Philip S Thomas and Andrew G Barto. Conjugate markov decision processes. In International Conference on Machine Learning, pages 137-144, 2011.
[32] Stephen Chung. Learning by competition of self-interested reinforcement learning agents, In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022. To appear.
[33] Théophane Weber, Nicolas Heess, Lars Buesing, and David Silver. Credit assignment techniques in stochastic computation graphs. arXiv preprint arXiv: 1901.01761, 2019.
[34] Diederik Kingma and Max Welling. Efficient gradient-based inference through transformations between bayes nets and neural nets. In International Conference on Machine Learning, pages 1782-1790, 2014.
[35] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal 2017.
policy optimization algorithms. arXiv preprint
[36] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928-1931) 2016.
[37] Giacomo Indiveri, Bernabé Linares-Barranco, Tara Julia Hamilton, André Van Schaik, Ralph Stienne-Cumminge Tobi Delbruck, Shih-Chii Liu, Piotr Dudek, Philipp Häfliger, Sylvie Renaud, al. Neuromorphic silicon neuron circuits. Frontiers in neuroscience, 5:73, 2011.
[38] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 1 112(1- 2):181-2 1999.


Reviews:
[{"review_id": "vdZxpRggpBZ", "reviewer": "Reviewer_pdvp", "summary": "This paper proposes a local learning rule as a biologically plausible alternative to backprop. The core idea is to train each neuron using REINFORCE and mitigate the high variance issue of REINFORCE using their novel MAP propagation algorithm. They also show how a similar method could be used to train a value function for an actor-critic algorithm. And they are able to demonstrate the effectiveness of their method on few tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Introducing a biologically plausible alternative to backprop is a very active research area that would be beneficial in bridging the gap between neuroscience and artificial neural networks. And often the proposed alternatives are sub-optimal and not able to match the performance of backprop. The results presented in this work show that their proposed method is able to reliably work. And the algorithm is relatively easy to implement and does not impose many constraints on the network architecture, hence could be a work that the community can build upon it.\n\nIn the first paragraph of related work, is the main novelty of this work compared to the cited works is the application of MAP propagation to RL as opposed to (un)supervised learning? Would be great to elaborate more.  \n\nWhile the text is well-written and I was able to follow the text, the main text is quite dense. Perhaps some restructuring and rewriting could make the paper more easily readable.\n\nPlease have a brief description of the multiplexer and scalar regression tasks to make the text self-sufficient. \n\nDue to inner loop optimization for each layer, there is added computational complexity. Could you please also have a comparison of the computational complexity of this method vs backprop?\n\nThe appending L:82 mentions that a different learning rate was used for each layer. This will result in an increase in the number of hyper-parameters with layer size. How difficult was it to tune each of these separately? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "adW4dMKCX7R", "reviewer": "Reviewer_LSFF", "summary": "The authors in the paper propose a method to train multi-layer neural networks.\nThe standard back-propagation algorithm aims at computing the influence of the output\nneuron in a step wise chain rule fashion. The alternative proposed in this paper\nis to compute the influence of a mid-layer neuron on the output of the network\nusing REINFORCE algorithm.  The proposal is to treat each neuron as a separate\nlearning agent. The authors main contribution is to implement MAP propagation to\ncontrol variance that comes with REINFORCE algorithm. The initial set of results show\nthat this technique can be comparable to back-propagation in RL settings.", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "I don't see any obvious technical faults in the paper.\n\nMy question to the authors is around the larger goal of this paper.\nI don't see why being close to biological learning,  is so important if the\nonly goal is to achieve lower training error.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations have been addressed. I don't see any direct societal impacts in this paper.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None in my opinion", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "TntFbxWqfb7", "reviewer": "Reviewer_NswB", "summary": "The paper introduces a new synapse-local method for reinforcement learning, that is similar to the REINFORCE algorithm, but reduces the high variance caused by REINFORCE's need to assess many stochastic samples, at the cost of added computation. \n\nIIUC, it does this by 1- making REINFORCE layer-local (Eq 2), 2- Replacing the gradient of probabilities of observed responses  by its expectation given the state and action (which is uncomputable) (Eq 4-5), and 3- Approximating this uncomputable expectation by replacing actual activations with their maximum a posteriori estimate, given the chosen action and observed state. The latter turns out to be computable, with some iterative process.\n\nThe algorithm is also shown to be equivalent, update-wise, to plain backpropagation with the reparametrization trick (this is how I understood Theorem 2 and Eq. 11, but I may be wrong, see below). \n\nVarious experiments show that this method learns faster than REINFORCE and about as fast as backprop with the reparametrization trick, in terms of number of steps (though each step is computationally more intensive).", "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": "I found the paper interesting, though somewhat confusing to me, possibly due to my lack of expertise with the details of the algorithms.\n\nTo my knowledge, the method is novel, and addresses an important limitation of REINFORCE-like algorithms (the high variance and the difficulties this causes for learning). The *relative* biological plausibility (the rule is local to each neuron, though the actual mechanism seems somewhat involved for neurons to perform) is a nice bonus.\n\nThe experiments are well chosen and the results are informative.\n\nThe paper is well-written throughout, though could gain some clarity.\n\nFirst and foremost, it would be *extremely helpful* to provide a very short, intuitive summary of the overall proposal and derivation (similar to the two first paragraphs in the Summary above, but of course more accurate) before going on with the full description, so that the reader would get a general idea of where this is going and why we're doing it before trudging through the whole derivation in section 3.1. \n\nThe introduction mentions what MAP does (lines 41-42 of p. 2) , but not *why*. IIUC, it is so that we need fewer actual samples to estimate the gradients. In fact, the crucial justification for the whole approach seems to that the RHS in Eq. 4 should have lower variance than Eq. 5. It's not quite obvious why, and lines 116-117 in p.3 don't clarify much. The reason for the reduction of variance should be explained a bit better, possibly in an appendix section.\n\nAlso, when the introduction and abstract mention that the proposed approach is equivalent to backpropagation. IIUC, it should be \"backpropagation with the reparametrization trick\". If I am correct, this should be explicitly stated! (And if not, it should be clarified what exactly \"backpropagation\" means here).\n\nA few other things that confused me:\n\n* Eq 11 and Theorem 2 seem to assert that the method is equivalent to backprop with the reparametrization trick. But the experiments seem to show that the method has quite distinct properties, e.g. being better when more exploration is needed. Evidently I am missing something. Could this be clarified?\n\n* For the regression part (p. 4, l. 146), I do not understand what information is \"lost\". The appendix seems to suggest a simple centering and normalization method to address this \"loss\". Again, this could be clarified.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the algorithm, especially its higher computational cost, seem adequately stated (e.g. in last paragraph of section 3.2). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JWfLVHLDqj", "reviewer": "Reviewer_SPS7", "summary": "This work introduces a local learning rule (with a global reward signal). The basic idea is just a neural network with stochastic units and REINFORCE update each layer (that is, the REINFORCE gradient estimate is not backpropogated through the network, each layer computes an update weighted by the reward. This, by itself, is (as recognized in the paper) an old idea.\n\nThey key addition here is an approach to reducing the (prohibitive) variance of this approach by conditioning the update of a particular layer on the state and action (eq 5). This lower-variance update is then approximated by eq 6. One interpretation of this is that the activations of the layer being updated are shifted to be more compatible (lower free energy) with the nearby layers.\n\nThey try this approach on some standard simple RL benchmark tasks and find that it performs comparably to backprop but much better then naive REINFORCE (per layer) or a previous method for reducing variance in this situation.", "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:\nAs the author's recognize, the idea of apply REINFORCE to every unit in a network is old. As far as I know the variance reduction approach used here is novel and the main contribution.\n\nQuality:\n\nThe approach appears technically sound (I did not check the appendix carefully) and the experimental results reasonable, although only on relatively simple tasks.\n\nThe approach introduce here is interesting, because any new learning rule is interesting. But its main claimed benefits are that is more biologically plausible (than backprop) due to the use of only local information and a global reward. For this reason, it seems that other somewhat biological plausible approaches should have also been included as baselines, such as feedback alignment [11-13].\n\nThis submission would also be strengthened by discussing how ``biologically plausible'' this learning method is. For example, (approximately) taking the argmax (eq 8) is done layer-wise rather than unit-wise. Is there a plausible neural mechanisms for this? (I don't know the answer).\n\nClarity:\n\nOverall the paper is well written.\n\nOne minor thing is that in some cases I think it would be helpful to be explicit about what the expectation is taken over.\n\nSignificance:\n\nLearning rules that are competitive (in learning speed) with backprop while using only local information are of interest to the community. Based on the experiment here, this approach appears of interest. The interest to the neuroscience community would depend on how biologically plausible this learning rule is when examined in more detail.\n\nMinor Issues:\n\n$H$ is referred to the as the ``value'' of a layer. It might be clearer to call this the activation of a layer, as ``value'' could mean weight or activation.\n\nI realize that MAP is a common abbreviation, but I still think that it would be ideal to write out the term in full once.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think this paper raises particular concerns.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of biologically plausible learning rules. For this, it looks at a local learning rule that uses REINFORCE to learn local updates for individual neurons. The main contribution is a novel variance reduction scheme for REINFORCE. While there were some fundamental question raised on biologically plausible learning rules (which is an active area of research), the reviewers found this a significant contribution and the paper interesting. As such, I would recommend acceptance of this paper.
Decision: Accept (Poster)