# Critic Algorithms using Cooperative Networks

Debangshu Banerjee  Kavita Wagh

###### Abstract

An algorithm is proposed for policy evaluation in Markov Decision Processes
which gives good empirical results with respect to convergence rates. The
algorithm tracks the Projected Bellman Error and is implemented as a true
gradient based algorithm. In this respect this algorithm differs from
TD($\lambda$) class of algorithms. This algorithm tracks the Projected Bellman
Algorithm and is therefore different from the class of residual algorithms.
Further the convergence of this algorithm is empirically much faster than GTD2
class of algorithms which aim at tracking the Projected Bellman Error. We
implemented proposed algorithm in DQN and DDPG framework and found that our
algorithm achieves comparable results in both of these experiments.

##  1 Introduction

While most reinforcement learning algorithms aim at minimizing the Mean
Squared Bellman Error, in function approximation it makes more sense to track
the Projected Bellman Error. This is because with function approximation the
true optimal of the Bellman Equation might not be representable by the
function class. An example would be the true solution not being within the
range space of the design matrix when using linear architectures. In such a
scenario, one looks at the projected optimal solution onto the range space of
the design matrix. This projected optimal solution is the fixed point solution
of the Bellman Equation.

##  2 Problem Setup

Let $(\mathcal{X,U,P,R,\pi})$ denote a Markov Decision Problem, where states
can take values in a state space $\mathcal{X}$. Corresponding to a state
$x\in\mathcal{X}$, we can take an action $u\in\mathcal{U}$, corresponding to
which we get a reward $r\in\mathcal{R}$. The actions can be taken according to
a strategy or a policy $\mu:\mathcal{X}\to\mathcal{U}$, where corresponding to
each state we take an action as mentioned by the policy $\mu$.

The planning problem or the evaluation problem corresponds to evaluating the
goodness of a policy $\mu$. Described formally, being at a state $i$, the
evaluation of the goodness of the state while following a strategy $\mu$ is
the cumulative expected reward earned

$J_{\mu}(i)=\mathbf{E}_{\mu}[\sum_{t=0}^{\infty}g(i_{t},i_{t+1})|i_{0}=i]$

These expectations can be computed as Monte Carlo runs on simulations and can
be updated online as a type of Robbins Munro Equation.

From this perspective, let $(i_{0},i_{1},i_{2},...)$ be a sequence of states
as observed while following a policy $\mu$. At any state $i_{k}$ we can
compute the cost-to-go $J_{\mu}(i_{k})$ as follows :

$J_{\mu}(i_{k})=\mathbf{E}[\sum_{t=0}^{\infty}g(i_{k+t},i_{k+t+1})]$
$=\mathbf{E}[g(i_{k},i_{k+1})+J_{\mu}(i_{k+1})]$
$=(1-\lambda)\mathbf{E}[\sum_{l=0}^{\infty}\lambda^{l}(\sum_{n=0}^{l}g(i_{k+n},i_{k+n+1})+J_{\mu}(i_{k+l+1}))]$

, where $\lambda$ is a parameter or eligibility trace between $(0,1)$ which
weights the $l-step$ rewards.

$=\mathbf{E}[\sum_{l=k}^{\infty}\lambda^{l-k}d_{l}]+J_{\mu}(i_{k})$

, where $d_{l}=g(i_{l},i_{l+1}+J_{\mu}(i_{l+1})-J_{\mu}(i_{l})$

The Robbins Munro stochastic approximation algorithm for the above equations
becomes

$J(i_{k}):=J(i_{k})+\gamma\sum_{l=k}^{\infty}\lambda^{l-k}d_{l}$

This form of update is what is known as a look-up table approach, since we
need to keep a separate entry for each states’ cost to go, and update every
entry as the simulation proceeds.

In contrast when it comes to function approximation, we approximate
$J_{\mu}(i)$ by $\tilde{J}(i,r)$ where $r$ is a learnable parameter.

We solve the following minimization problem for instance in the stochastic
shortest path problem, where $N$ is a stopping time :

$\min_{r}\sum_{k=0}^{N-1}[\sum_{t=k}^{N-1}g(i_{t},i_{t+1})-\tilde{J}(i_{k},r)]^{2}$

Gradient descent gives us the following update

$r:=r-\gamma\sum_{k=0}^{N-1}\nabla\tilde{J}(i_{k},r)(\tilde{J}(i_{k},r)-\sum_{t=k}^{N-1}g(i_{t},i_{t+1}))$
$=r+\gamma\sum_{k=0}^{N-1}\nabla\tilde{J}(i_{k},r)(\sum_{t=k}^{N-1}d_{t})$

By allowing for eligibility trace $\lambda$, the update is

$r:=r+\gamma\sum_{k=0}^{N-1}\nabla\tilde{J}(i_{k},r)(\sum_{t=k}^{N-1}d_{t}\lambda^{t-k})$

And for discounted problems as

$r:=r+\gamma\sum_{k=0}^{\infty}\nabla\tilde{J}(i_{k},r)(\sum_{t=k}^{\infty}d_{t}(\alpha\lambda)^{t-k})$

This can be algabraically rearranged so that we can perform the updates in an
online fashion

$r:=r+\gamma d_{k}\sum_{t=0}^{k}(\alpha\lambda)^{k-t}\nabla\tilde{J}(i_{t},r)$

For linear architectures, $\tilde{J}(i,r)=\phi(i)^{T}r$, where $\phi(i)$ is a
design vector, whose dimension $k<<|\mathcal{X}|$, the above update is

$r_{t+1}=r_{t}+\gamma_{t}d_{t}\sum_{k=0}^{t}(\alpha\lambda)^{t-k}\phi(i_{k})$

It is known the above update, under mild conditions, converge to the fixed
point solution of

$\Pi T^{\lambda}(\Phi r^{*})=\Phi r^{*}$

where
$T^{\lambda}J(i)=(1-\lambda)\mathbf{E}[\sum_{l=0}^{\infty}\lambda^{l}(\sum_{n=0}^{l}g(i_{n},i_{n+1})+J_{\mu}(i_{l+1}))|i_{0}=i]$
is the Bellman Operator,
$\Pi=\Phi(\Phi^{T}D\Phi)^{-1}\Phi^{T}D$ is the projection operator on the
range space of $\Phi$,
$\Phi$ is the design matrix $s.t.\tilde{J}(r)=\Phi r$ and
$\Phi\in\mathbf{R}^{|\mathcal{X}|\times k}$ and
$D=diag\\{\pi(i),\pi(j)..\\}$,
$D\in\mathbf{R}^{|\mathcal{X}|\times|\mathcal{X}|}$ where $\pi$ is the steady
state distribution of the Markov Decision Process.

Based on the above equation one has the following Value Iteration update

$J:=\Pi T^{\lambda}(\Phi r)$

Though, these algorithms have strong convergence results, a fundamental
problem that so exists is that these are not true gradient based methods. To
illustrate note that for $\lambda=0$, get the familiar TD(0) update:

$r_{t+1}=r_{t}+\gamma_{t}d_{t}\phi(i_{t})=r_{t}+\gamma_{t}(g(i_{t},i_{t+1})+\phi(i_{t+1})^{T}r_{t}-\phi(i_{t})^{T}r_{t})\phi(i_{t})$

A true gradient descent algorithm based on the the following objective
function for a 1-step Bellman Error

$\min_{r}||\tilde{J}(i,r)-T\tilde{J}(i,r))||_{D}^{2}$

where
$T\tilde{J}(i,r))=\mathbf{E}_{\mu}[g(i_{t},i_{t+1})+\tilde{J}(i_{t+1},r)|i_{t}=i]$,
gives the following update

$r_{t+1}=r_{t}+\gamma_{t}(g(i_{t},i_{t+1})+\phi(i_{t+1})^{T}r_{t}-\phi(i_{t})^{T}r_{t})(\phi(i_{t})-\phi(i_{t+1}))$

The other issue is, it seems more intuitive to look at the following objective
function

$\min_{r}||\tilde{J}(i,r)-\Pi T\tilde{J}(i,r))||_{D}^{2},$

where $\Pi$, $T\tilde{J}(i,r))$ are as defined before. We shall call this the
Mean Square Projected Bellman Error.

###  2.1 Derivation

We aim at minimizing the following objective function

$\min||\Pi TJ-J||_{D}^{2}$

where $\Pi=\Phi(\Phi^{T}D\Phi)^{-1}\Phi^{T}D$ is the projection operator on
the range space of $\Phi$
$TJ(i)=\mathbf{E}_{\mu}[g(i,j)+J(j)]$ is the 1-step Bellman Operator and
$J=\Phi r$ where $r\in\mathbf{R}^{k}$

This objective function was introduced by Sutton et al and is known as the
Mean Squared Projected Bellman Error.

A rough idea that we propose here would be to modify the following algorithm

Input $J_{k}$
Output $J^{*}$

repeat

while $\delta$ tolerance do

compute $\Pi TJ_{k}$

end while

$J_{k+1}\leftarrow\Pi TJ_{k}$

until $||\Pi TJ_{k}-J_{k}||_{D}^{2}<\epsilon$

which is not truly gradient based because of

$J_{k+1}\leftarrow\Pi TJ_{k}$

to

while $\delta$ tolerance do

$\min_{J_{k+1}}||\Pi TJ_{k}-J_{k+1}||_{D}^{2}$

end while

Notice that by definition of the projection operator $\Pi$ we can write $\Pi
TJ_{k}=\Phi r_{k+1}$ where

$r_{k+1}=\operatorname*{arg\,min}_{r}||TJ_{k}-\Phi r||_{D}^{2}$

where $TJ_{k}(i)=\mathbf{E}_{\mu}[g(i,j)+J_{k}(j)]$ is the one step Bellman
Error for $k^{th}$ estimate of $J$ and
$J_{k}=\Phi x_{k}$ for some $x_{k}\in\mathbf{R}^{k}$

To compute $r_{k+1}$, a gradient descent would result in the following update

$r:=r+\beta(g_{ij}+\phi(j)^{T}x_{k}-\phi(i)^{T}r)\phi(i)$

With this updated value of $r_{k+1}$ we solve the next minimation problem
$\min_{J_{k}}||\Phi r_{k+1}-J_{k}||_{D}^{2}$

$=\min_{x_{k}}||\Phi r_{k+1}-\Phi x_{k}||_{D}^{2}$

A gradient descent would result in the following update

$x_{k}:=x_{k}-\gamma(\phi(i)^{T}r_{k+1}-\phi(i)^{T}x_{k})\phi(i)$

The resulting algorithm thus becomes,

numbered 1 Coordinate Descent TD(0)

Input A trajectory of states simulated according to policy $\mu$,
$r_{0},x_{0}$
Output $J^{*}=\Phi r^{*}=\Phi x^{*}$

for each state transition $(i,j)$ with reward $g_{ij}$ do

while $\delta$ tolerance do

compute $r:=r+\beta(g_{ij}+\phi(j)^{T}x_{k}-\phi(i)^{T}r)\phi(i)$

end while

$r_{k+1}\leftarrow r$

while $\delta$ tolerance do

$x:=x-\gamma(\phi(i)^{T}r_{k+1}-\phi(i)^{T}x)\phi(i)$

end while

$x_{k+1}\leftarrow x$

end for

###  2.2 A sketch of convergence analysis

Let us say that we have an $x_{k}$ at the begining of some iteration. Let us
look at the first update equation :

$r:=r+\beta(g_{ij}+\phi(j)^{T}x_{k}-\phi(i)^{T}r)\phi(i)$

This algorithm convergence $r\to r_{k+1}$ s.t

$\Pi T\Phi x_{k}=\Phi r_{k+1}$

With this $r_{k+1}$ fixed we consider the next update equation

$x_{k}:=x_{k}-\gamma(\phi(i)^{T}r_{k+1}-\phi(i)^{T}x_{k})\phi(i)$

This update converges $x_{k}\to r_{k+1}$ s.t. $x_{k+1}=r_{k+1}$

We use this value in the first update to get $r_{k+2}$ s.t

$\Pi T\Phi x_{k+1}=\Pi T\Phi r_{k+1}=\Phi r_{k+2}$

Thus we see that running these two updates gives us a sequence
$\\{r_{k})_{k>0}$ which satisfies the following updates

$\Pi T\Phi r_{k}=\Phi r_{k+1}\forall k=1,2,..$

This last equation is known to converge.

###  2.3 Implementation Details and Extensions to Non-linear Function
approximations and control problems

For implementations sake we have used the following schema, where each
gradient update step is performed sequentially, without waiting for $\delta$
convergence.

numbered 2 Alternating Coordinate Descent for TD(0)

Input A trajectory of states simulated according to policy $\mu$,
$r_{0},x_{0}$
Output $J^{*}=\Phi r^{*}=\Phi x^{*}$

for each state transition $(i,j)$ with reward $g_{ij}$ do

$r_{k+1}=r_{k}+\beta(g_{ij}++\phi(j)^{T}x_{k}-\phi(i)^{T}r_{k})\phi(i)$

$x_{k+1}=x_{k}-\gamma(\phi(i)^{T}r_{k+1}-\phi(i)^{T}x_{k})\phi(i)$

end for

For non-linear function approximations, say $J(i)=\tilde{J}(i,r)$ where $r$ is
a learnable parameter, we have used the following schema

numbered 3 Alternating Coordinate Descent for TD(0)

Input A trajectory of states simulated according to policy $\mu$,
$r_{0},x_{0}$
Output $J^{*}=\tilde{J}(r^{*})=\tilde{J}(x^{*})$

for each state transition $(i,j)$ with reward $g_{ij}$ do

$r_{k+1}=$ one step update of
$\min_{r_{k}}\\{g_{ij}+\tilde{J}(j,x_{k})-\tilde{J}(i,r_{k})\\}^{2}$ using
your favourite optimizer.

$x_{k+1}=$ one step update of
$\min_{x_{k}}\\{\tilde{J}(i,r_{k+1})-\tilde{J}(i,x_{k})\\}^{2}$ using your
favourite optimizer.

end for

This has suggested the following critic network design.

####  2.3.1 Implementation as a deep neural network

Let us say we have the following transition $(i,g_{i,j},j)$

We can implement this algorithm by the designing a cooperative neural network.
It represents a cooperation in the sense that the output of each network
reinforces the parameters of the other network.

$\phi(i)$$J_{r}(i)$$r$$\phi(i)$$J_{x}(i)$$x$$TJ_{x}(i)$

Here $TJ_{x}(i)=g_{i,j}+J_{x}(j)$.

The box over $TJ_{x}(i)$ and $J_{r}(i)$ represents the error which is
backpropagated over the left hand network.

The box over $J_{r}(i)$ and $J_{x}(i)$ represents the error that is
backpropagated over the right hand side network.

####  2.3.2 Control Problems using Q- factors

For control problems we have the following Q-factor alternative algorithm,
where each $Q(i,u)=\tilde{Q}(i,u,r)$ where $r$ is a learnable parameter and
$i\in\mathcal{X}$ and $u\in\mathcal{U}$

numbered 4 Alternating Coordinate Descent for Q-Learning

Input An initial state $i_{0}$ $r_{0},x_{0}$
Output $Q^{*}=\tilde{Q}(r^{*})=\tilde{Q}(x^{*})$

for current state $i$ do

choose $u$ as $\max_{u}\tilde{Q}(i,u,r_{k})$ with probability $\epsilon$ or
choose a random action

Based on action $u$ observe next state $j$ and reward $g_{ij}$

$r_{k+1}=$ one step update of
$\min_{r_{k}}\\{g_{ij}+\max_{v}\tilde{Q}(j,v,x_{k})-\tilde{Q}(i,u,r_{k})\\}^{2}$
using your favourite optimizer.

$x_{k+1}=$ one step update of
$\min_{x_{k}}\\{\tilde{Q}(i,u,r_{k+1})-\tilde{Q}(i,u,x_{k})\\}^{2}$ using your
favourite optimizer.

update current state as $j$

end for

####  2.3.3 Control Problems using Actor-Critic

Since our algorithm is itself a critic network in essence, it can be used with
any other actor network in conjunction to solve control problems.

We shall see more of these in the experimant section.

##  3 A simple example

Let us consider the following problem. A Markov Chain that has 3 states $A$,
$B$ and $C$. The transition probabilities are as marked.

ABC$\frac{1}{2}$$\frac{1}{2}$$1$$1$

The each transiotion has $0$ reward except for the self transition at $B$ and
$C$ which are $1$. We choose the invariant distribution of $\pi=[0,0.8,0.2]$
respectively for states $A,B$ and $C$.

We have a simple state-feature representation $\phi(A)=\epsilon$, $\phi(B)=-1$
and $\phi(C)=1$ where $\epsilon$ is a small positive numbers to ensure we
don’t run into zero gradient estimates.

We first plot the objective function

$||TJ_{\theta}-J_{\theta}||_{D}^{2}$

, which is used for gradient based algorithms w.r.t the tunable paramater
$\theta$

Figure 1: MSBE

Figure 2: MSPBE

Figure 3: TD(0) with $\theta_{0}=5$

Figure 4: TD(0) $\theta_{0}=-5$

Figure 5: MSPBE gradient
based algorithm

Figure 6: MSPBE for
GTD2 algorithm

Figure 7: MSPBE for THIS algorithm

Let us compare this with the MSPBE objective function

$||\Pi TJ_{\theta}-J_{\theta}||_{D}^{2}$

We see that the MSPBE error (Figure 7) is less than the MSBE (Figure 7).

Let us now look at how the $TD(\lambda)$ performs. The $TD(\lambda)$ is known
to track the MSPBE. The $TD(\lambda)$ algorithm also has the fastest
convergence rates compared to gradient based methods.

We plot the $MSPBE$ of the $TD(0)$ algorithm with the updates of the tunable
parameter $\theta$.

We first show the result when the initial point of $\theta_{0}=5.0$ (Figure 7)
From the $MSPBE$ graph we see that it would converge to a suboptimal solution
of $0.5$

The learning rate has been kept fixed at $0.001$, instead of using decreasing
step size. This results in some noise but we ignore that, as the point is made
clear that a local minima of $0.5$ is reached.

We are also confirmed that while start at initial values of $\theta_{0}=-5.0$
we reach the global minima of $0$ (Figure 7).

Again a bit of overshoot is visible because of the randomness in the
simulation and using constant step sizes.

We now look at the gradient based algorithms which aim at tracking

$||TJ_{\theta}-J_{\theta}||_{D}^{2}$

.

We plot $||TJ_{\theta}-J_{\theta}||_{D}^{2}$ vs $\theta$. The results are also
confirmed by looking at $MSBE$ plot. We start with 3 different starting
positions of $\theta_{0}$ : $-5,1$ and $5$ (Figure 8).

(a) $\theta_{0}=-5$

(b) $\theta_{0}=1$

(c) $\theta_{0}=5$

Figure 8: Gradient Based Algorithms

That the gradient based algorithms are slower is confirmed by having taken
learning rates $0.01$, $10$ times that of $TD$ algorithms.

The $MSBE$ optimal $\theta$ is also optimal for the $MSPBE$, however this may
not be true as illustrated in Figure 7. This figure tracks the $MSPBE$ with
changing $\theta$ while using gradient based algorithms. We see that for
negative values of $\theta$ the $MSPBE$ is $0$ which is consistent with the
$MSPBE$ plot for negative values of $\theta$. However, for positive values of
$\theta$ the local optima should be at $0.5$ whereas as shown in the figure,
the gradient based algorithm tracks the $MSPBE$ at $1$.

Thus the gradient based algorithms do not track the $MSPBE$. Let us look at
the GTD2 algorithm which does track the $MSPBE$ (Figure 7).

However GTD2 has quite slow convergence. The leaning rate has been fixed to
$100$ which is $10000$ times that of gradient based algorithms.

We now see that the proposed algorithm not only tracks the $MSPBE$ (Figure 7)
but the learning rate chosen is $0.1$, which is $1000$ times as less than GTD2
based algorithm.

The derivation also shows that this can be implemented very easily since it is
a gradient based algorithm by itself.

##  4 Experiments

To analyze the effects of the proposed network update rule we carried out the
experiments in two different existing frameworks:Deep Q-Network(DQN)[2] and
Deep Deterministic Policy Gradient(DDPG)[1]. We are using these existing
frameworks because we aim to investigate the impact of proposed update rule in
different existing settings111Implementation code in available at
https://github.com/kavitawagh/RLProject.git. DQN and DDPG are the benchmark
algorithms in discrete action space and continuous action space setting,
respectively.

In the following sections we explain how have we implemented the proposed
update rule in DQN and DDPG framework and we also present the results of our
experiments.

###  4.1 DQN

For MDPs having discrete action space, DQN is the non-linear approximation of
Q-function implemented using neural networks. The state $s$ is the input to
Q-Network and for each action $a$ in the action space, Q-Network outputs the
Q-value $Q(S,a)$. Greedy policy is used to select single Q-value out of all
outputs of the Q-Network, where Q-value selected is $\max_{a}Q(s,a)$.

Non-linear function approximation is known to be unstable or even diverge when
used to approximate Q-value function. One of the reason for the instability is
the correlation between Q-value $Q(s,a)$ and target Q-value
$\\{reward+\gamma*\max_{a^{\prime}}Q(s^{\prime},a^{\prime})\\}$ when same
network is used to predict Q-values and target Q-values. Hence in DQN
framework, target Q-values are predicted by different Q-Network whose weight
parameters are updated periodically. DQN also uses a replay buffer for
training the Q-Network with a batch of transitions. Every time an agent takes
some action in environment, the state transition tuple
$(current\\_state,action,reward,next\\_state)$ is stored in the replay buffer.
In the network training step, a random batch of transition tuples is sampled
from replay buffer and used in network optimization. Figure 9 presents the
original DQN algorithm.

Figure 9: Original DQN Algorithm[2]

####  4.1.1 Modification in algorithm

Figure 10 shows pseudo-flowchart for DQN algorithm along with the proposed
update rule. The blocks in black border indicate the processing steps that
belongs to original DQN algorithm and we are using as it is in modified
algorithm. The shapes in blue indicate the processing steps in the original
DQN algorithm those we have replaced with our processing steps highlighted
with green color. The names in circles indicate the relation between our
implementation and the network architecture proposed in Section 2.3.1.

In every environment step, we sample a batch of transitions from the replay
buffer. Feeding $next\\_state$ to target Q-network we get $target\\_QValue$.
The Bellman operator is applied using $target\\_QValue$ to get the target $y$
to optimize the main Q-network. Main Q-network is then optimized by minimizing
the mean square error(MSE) loss between its prediction and $y$. In original
DQN algorithm, before optimizing the main Q-network, the weights of target
Q-network are set equal to the weights of main Q-network and then main
Q-network is optimized. While in our modification, instead of just copying the
weights, we take an optimization step on target Q-network.

Figure 10: Implementation of proposed update rule in DQN framework

####  4.1.2 Environment

We trained our Q-Network for OpenAI Gym CartPole environment. Cart-Pole is the
classical reinforcement learning problem where the aim is to balance the pole
upright on the cart by moving the cart left or right. State is represented by
a list of observations [cart position, cart velocity, pole angle, pole
velocity at the tip]. Actions include pushing the cart left or right. Reward
is +1 for every step taken by the agent, including the termination step.
Episode terminates if pole angle is more than $\pm 12^{\circ}$ or the
accumulated reward is equal to 200.

####  4.1.3 Results

We trained the Q-Network using original DQN algorithm and DQN algorithm with
proposed update rule. Figure 11 shows the plot of actual training reward
against the episode numbers. We can see that the results of proposed update
rule are comparable to that of the original DQN algorithm. After achieving the
highest, the reward goes to zero in some episodes. This is possible because of
the stochastic nature of the problem and the behaviour policy being used. We
are using epsilon-greedy policy where minimum epsilon value is 0.1, that is
agent can take random action with probability 0.1.

(a) Original DQN algorithm

(b) DQN algorithm with proposed update rule

Figure 11: Plot of training reward against episodes using DQN for CartPole
environment

###  4.2 DDPG

DDPG is actor-critic algorithm based on deterministic policy gradient for the
problems having continuous action space. It uses the non-linear approximation
of critic which models the Q-value function and actor which models the
deterministic policy $\mu$. Critic network predicts the Q-value $Q(s,a)$ given
the state $s$ and action $a$ as input. Actor network predicts the action
$\mu(s)$ given state $s$ as the input.

Based on the current network parameters, actor network predict action. Using
this predicted action, critic network predicts the Q-value. This Q-value is
used as feedback for actor saying how good or bad the action predicted by
actor is. The key concept that DDPG based on is the form of the deterministic
policy gradient. The gradient of the state-value function $J(.)$ w.r.t to
actor network parameter have a nice implementable form involving the gradient
of Q-value function and the gradient of policy(actor) network w.r.t network
parameters. Optimizing the actor network with the gradient-ascent step in the
direction of policy gradient guarantees to asymptotically converge into
optimal optimal policy. Formally, policy gradient is given by,

$\nabla_{\theta}J=\nabla_{a}Q(s,a)|_{a=\mu(s)}\nabla_{\theta}\mu(s)$

where $J$ is the state-value function,
$Q(.,.)$ is the Q-value function(critic network),
$\mu$ is the deterministic policy(actor network with parameters $\theta$)
Figure 12 presents the original DDPG algorithm.

Figure 12: Original DDPG Algorithm[1]

####  4.2.1 Modification in algorithm

Figure 13 shows pseudo-flowchart for DDPG algorithm along with the proposed
update rule. The blocks in black border indicate the processing steps that
belongs to original DDPG algorithm and we are using as it is in modified
algorithm. The shapes in blue indicate the processing steps in the original
DDPG algorithm those we have replaced with our processing steps highlighted
with green color. The names in circles indicate the relation between our
implementation and the network architecture proposed in Section 2.3.1.

There are two actor networks: main actor and target actor; and two critic
networks: main critic and target critic. The predictions of main networks are
actually used to select action for the agent while target networks are used to
calculate Bellman operator. First, a batch of transitions
($current\\_state,action,reward,next\\_state$) is sampled from the replay
buffer. Feeding $next\\_state$ as input to target actor, we get
$target\\_action$. This $target\\_action$ with $next\\_state$ in target critic
gives $target\\_QValue$. Then we calculate Bellman operator value $y$ which is
used as target to optimize the main critic network. In original DDPG
algorithm, the weights of the both target models are updated using soft update
rule. In our modification, we replace the weight update step for target critic
by an optimization step.

Figure 13: Implementation of proposed update rule in DDPG framework

####  4.2.2 Environment

We trained our actor-critic network on OpenAI Gym BipedalWalker-v3
environment. BipedalWalker is a robot with a LIDAR system and two legs having
four joints, two in each leg. The goal is to train the robot to walk as fast
as possible on the simple terrain(with no obstacles). The environment state
contains the LIDAR sensor measurements, joint positions, velocity, etc. The
action is to apply the torques on four joints. The torque for any joint is
value in [-1, 1] and this makes it continuous action space problem. The +1
reward is given for moving one step forward, total 300+ points up to the far
end. If the robot falls, it gets -100 reward.

####  4.2.3 Results

We trained the actor-critic using original DDPG algorithm and DDPG algorithm
with proposed update rule. Figure 14 shows the plots for actual training. The
no. of steps the robot is able to balance on its legs is larger in modified
DDPG than that in the original DDPG (Figure 14(a)). After visualizing the
training episodes we came to know that agent in original DDPG is trying to
move forward without taking the proper balanced pose first, and was falling
immediately. While agent in modified DDPG first tries to take a balanced pose
before trying to move forward. Since no. of steps the agent is alive is
different for every episode we show the average reward per episode in Figure
14(b). This figure indicates that the modified DDPG explores more than the
original DDPG. Figure 14(c) shows the Q-value plot for both the algorithms.

The positive reward(Figure 14(d)) and negative reward(Figure 14(e)) both are
higher in magnitude for modified DDPG. This is because we are plotting the
total positive and negative rewards accumulated in an episode and since the
modified DDPG survives for more no. of time steps it is obvious that it
accumulates more reward in both positive and negative direction. In Figure
14(f) the critic loss in modified DDPG is always smaller than critic loss in
original DDPG.

(a) No. of steps before robot falls down

(b) Avg reward per episode

(c) Q-Value

(d) Per episode accumulated
positive reward

(e) Per episode accumulated
negative reward

(f) Critic loss

Figure 14: Training results for BipedalWalker environment using DDPG

##  5 Conclusion

In our project, we came up with the new update rule for critic networks, in
which we use and optimize two critic networks. We implemented the proposed
update with DQN and DDPG algorithm on CartPole and BipedalWalker environments,
respectively. Results of experiments showed that proposed update gives
comparable results for both the algorithms. In future we aim to implement
proposed update rule for other RL algorithms like TRPO, proximal policy, etc
and analyze its performance. We also aim to prove rigorously the convergence
of proposed update rule.

## References

  * Lillicrap et al. [2016] T. Lillicrap, J. Hunt, A. Pritzel, and N. Heess.  Continuous control with deep reinforcemenr learning.  _ICLR_ , 2016.
  * Mnih et al. [2015] V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, and A. Graves.  Human-level control through deep reinforcement learning.  _Nature_ , 2015.