1 Introduction

The goal of this assignment is to experiment with policy gradient and its variants, including variance reduction methods. Your goals will be to set up policy gradient for both continuous and discrete environments and experiment with variance reduction tricks, including implementing reward-to-go and neural network baselines.

Turn in your report and code for the full homework as described in Problem 2 by September 19, 2018.

2 Review

Recall that the reinforcement learning objective is to learn a that maximizes the objective function:

J() = E(₎ [r()] (1)

where

T

() = p(s₁,a₁,,s_T,a_T) = p(s₁)(a₁|s₁)^Yp(s_t|s_t1,a_t1)(a_t|s_t)

t=2

and

T

r() = r(s₁,a₁,,s_T,a_T) = ^Xr(s_t,a_t).

t=1

The policy gradient approach is to directly take the gradient of this objective:

Z

J() = ()r()d (2)

Z

= () log()r()d. (3)

In practice, the expectation over trajectories can be approximated from a batch of N sampled trajectories:

) (4)

. (5)

Here we see that the policy is a probability distribution over the action space, conditioned on the state. In the agent-environment loop, the agent samples an action a_t from (|s_t) and the environment responds with a reward r(s_t,a_t).

One way to reduce the variance of the policy gradient is to exploit causality: the notion that the policy cannot affect rewards in the past, yielding following the modified objective, where the sum of rewards here is a sample estimate of the Q function, known as the reward-togo:

. (6)

Multiplying a discount factor to the rewards can be interpreted as encouraging the agent to focus on rewards closer in the future, which can also be thought of as a means for reducing variance (because there is more variance possible futures further into the future). We saw in lecture that the discount factor can be incorporated in two ways.

The first way applies the discount on the rewards from full trajectory:

!

(7)

and the second way applies the discount on the reward-to-go:

. (8)

.

We have seen in lecture that subtracting a baseline that is a constant with respect to from the sum of rewards

J() = E(₎ [r() b] (9)

leaves the policy gradient unbiased because

E(₎ [b] = E(₎ [ log() b] = 0.

In this assignment, we will implement a value function V which acts as a state-dependent baseline. The value function is trained to approximate the sum of future rewards starting from a particular state:

T

V(s_t) ^XE [r(s_t0,a_t0)|s_t], (10)

t⁰=t

so the approximate policy gradient now looks like this:

. (11)

Problem 1. State-dependent baseline: In lecture we saw that the policy gradient is unbiased if the baseline is a constant with respect to (Equation 9). The purpose of this problem is to help convince ourselves that subtracting a state-dependent baseline from the return keeps the policy gradient unbiased. For clarity we will use p() instead of (), although they mean the same thing. Using the law of iterated expectations we will show that the policy gradient is still unbiased if the baseline b is function of a state at a particular timestep of (Equation 11). Recall from equation 3 that the policy gradient can be expressed as

E_p(₎ [ logp()r()].

By breaking up p() into dynamics and policy terms, we can discard the dynamics terms, which are not functions of :

.

When we subtract a state dependent baseline b(s_t) (recall equation 11) we get

.

Our goal for this problem is to show that

.

By linearity of expectation we can consider each term in this sum independently, so we can equivalently show that

T

X

E_p(₎ [ log(a_t|s_t)(b(s_t))] = 0. (12)

t=1

• Using the chain rule, we can express p() as a product of the state-action marginal (s_t,a_t) and the probability of the rest of the trajectory conditioned on (s_t,a_t) (which we denote as (/s_t,a_t|s_t,a_t)):

p() = p(s_t,a_t)p(/s_t,a_t|s_t,a_t)

Please show equation 12 by using the law of iterated expectations, breaking E_p(₎ by decoupling the state-action marginal from the rest of the trajectory.

• Alternatively, we can consider the structure of the MDP and express p() as a product of the trajectory distribution up to s_t (which we denote as (s_1:t,a_1:t1)) and the trajectory distribution after s_t conditioned on the first part (which we denote as

(st+1:T,at:T|s1:t,a1:t1)):

p() = p(s1:t,a1:t1)p(st+1:T,at:T|s1:t,a1:t1)

• Explain why, for the inner expectation, conditioning on (s₁,a₁,,a_t1,s_t) is equivalent to conditioning only on s_t.
• Please show equation 12 by using the law of iterated expectations, breaking

E_p(₎ by decoupling trajectory up to s_t from the trajectory after s_t.

Since the policy gradient with respect to can be decoupled as a summation of terms over timesteps t [1,T], because we have shown that the policy gradient is unbiased for each of these terms, the entire policy gradient is also unbiased with respect to a vector of statedependent baselines over the timesteps: [b(s₁),b(s₂),b(s_T)].

3 Code Setup

3.1 Files

The starter code is available here. The only file you need to modify in this homework is train_pg_f18.py. The files logz.py and plots.py are utility files; while you should look at them to understand their functionality, you will not modify them. For the Lunar Lander task, use the provided lunar_lander.py file instead of gym/envs/box2d/lunar_lander.py. After you fill in the appropriate methods, you should be able to just run python train_pg_f18.py with some command line options to perform the experiments. To visualize the results, you can run python plot.py path/to/logdir.

3.2 Overview

The function train_PG is used to perform the actual training for policy gradient. The parameters passed into this function specify the algorithms hyperparameters and environment. The Agent class contains methods that define the computation graph, sample trajectories, estimate returns, and update the parameters of the policy.

At a high level, the dataflow of the code is structured like this:

1. Build a static computation graph in Tensorflow.
2. Set up a Tensorflow session to initialize the parameters of the computation graph. This is the only time you need to set up the session.

Then we will repeat Steps 3 through 5 for N iterations:

3. Sample trajectories by executing the Tensorflow op that samples an action given an observation from the environment. Collect the states, actions, and rewards as numpy variables.
4. Estimate returns in numpy (estimated Q values, baseline predictions, advantages).
5. Update parameters by executing the Tensorflow op that updates the parameters given what you computed in Step 4.

4 Constructing the computation graph

Problem 2. Neural networks: We will now begin to implement a neural network that parametrizes .

• Implement the utility function, build_mlp, which will build a feedforward neural network with fully connected units (Hint: use layers.dense). Test it to make sure that it produces outputs of the expected size and shape. You do not need to include anything in your write-up about this, it will just make your life easier.
• Next, implement the method build_computation_graph. At this point, you only need to implement the parts with the Problem 2 header.
  • Define the placeholder for the advantages in define_placeholders. We have already defined placeholders for the observations and actions. The advantages will correspond to r() in the policy gradient, which may or may not include a subtracted baseline value.
  • Create the symbolic operation policyforwardpass: This outputs the parameters of a distribution (a|s). In this homework, when the distribution is over discrete actions these parameters will be the logits of a categorical distribution, and when the distribution is over continuous actions these parameters will be the mean and the log standard deviation of a multivariate Gaussian distribution. This operation will be an input to Agent.sampleaction and Agent.getlogprob.
  • Create the symbolic operation sampleaction: This produces a Tensorflow op, self.sysampledac that samples an action from (a|s). This operation will be called in Agent.sampletrajectories.
  • Create the symbolic operation getlogprob: Given an action that the agent took in the environment, this computes the log probability of that action under (a|s). This will be used in the loss function.
  • In build_computation_graph implement a loss function (which call use the result from Agent.getlogprob) to whose gradient is

.

5 Implement Policy Gradient

5.1 Implementing the policy gradient loop

Problem 3. Policy Gradient: Recall from lecture that an RL algorithm can viewed as consisting of three parts, which are reflected in the training loop of train_PG:

1. sample_trajectories: Generate samples (e.g. run the policy to collect trajectories consisting of state transitions (s,a,s⁰,r))
2. estimate_return: Estimate the return (e.g. sum together discounted rewards from the trajectories, or learn a model that predicts expected total future discounted reward)
3. update_parameters: Improve the policy (e.g. update the parameters of the policy with policy gradient)

In our implementation, for clarity we will update the parameters of the value function baseline also in the third step (Agent.update_parameters), rather than in the second step (as was described in lecture). You only need to implement the parts with the Problem 3 header.

• Sample trajectories: In sampletrajectories, use the Tensorflow session to call self.sysampledac to sample an action given an observation from the environment.
• Estimate return: We will now implement r() from Equation 1. Please implement the method sum_of_rewards, which will return a sample estimate of the discounted return, for both the full-trajectory (Equation 7) case, where

T r(i) = Xt01r(sit,ait)

t=1

and for the reward-to-go case (Equation 8) where

T r(i) = Xt0tr(sit0,ait0).

t⁰=t

In Agent.estimate_return, normalize the advantages to have a mean of zero and a standard deviation of one. This is a trick for reducing variance.

• Update parameters: In update_parameters use the Tensorflow session to call the update operation self.updateop to update the parameters of the policy. You will need to figure out the inputs to feeddict.

5.2 Experiments

After you have implemented the code, we will run experiments to get a feel for how different settings impact the performance of policy gradient methods.

Problem 4. CartPole: Run the PG algorithm in the discrete CartPole-v0 environment from the command line as follows:

python train_pg_f18.py CartPole-v0 -n 100 -b 1000 -e 3 -dna exp_name sb_no_rtg_dna

python train_pg_f18.py CartPole-v0 -n 100 -b 1000 -e 3 -rtg -dna exp_name sb_rtg_dna

python train_pg_f18.py CartPole-v0 -n 100 -b 1000 -e 3 -rtg exp_name sb_rtg_na

python train_pg_f18.py CartPole-v0 -n 100 -b 5000 -e 3 -dna exp_name lb_no_rtg_dna

python train_pg_f18.py CartPole-v0 -n 100 -b 5000 -e 3 -rtg -dna exp_name lb_rtg_dna

python train_pg_f18.py CartPole-v0 -n 100 -b 5000 -e 3 -rtg exp_name lb_rtg_na

Whats happening there:

• -n : Number of iterations.
• -b : Batch size (number of state-action pairs sampled while acting according to the current policy at each iteration).
• -e : Number of experiments to run with the same configuration. Each experiment will start with a different randomly initialized policy, and have a different stream of random numbers.
• -dna : Flag: if present, sets normalize_advantages to False. Otherwise, by default, normalize_advantages=True.
• -rtg : Flag: if present, sets reward_to_go=True. Otherwise, reward_to_go=False by default.
• exp_name : Name for experiment, which goes into the name for the data directory.

Various other command line arguments will allow you to set batch size, learning rate, network architecture (number of hidden layers and the size of the hidden layersfor CartPole, you can use one hidden layer with 32 units), and more.

Deliverables for report:

• Graph the results of your experiments using the plot.py file we provide. Create two graphs.
  • In the first graph, compare the learning curves (average return at each iteration) for the experiments prefixed with sb_. (The small batch experiments.)
  • In the second graph, compare the learning curves for the experiments prefixed with lb_. (The large batch experiments.)
• Answer the following questions briefly:
  • Which gradient estimator has better performance without advantage-centering the trajectory-centric one, or the one using reward-to-go?
  • Did advantage centering help?
  • Did the batch size make an impact?
• Provide the exact command line configurations you used to run your experiments. (To verify batch size, learning rate, architecture, and so on.)

What to Expect:

• The best configuration of CartPole in both the large and small batch cases converge to a maximum score of 200.

Problem 5. InvertedPendulum: Run experiments in InvertedPendulum-v2 continuous control environment as follows:

python train_pg_f18.py InvertedPendulum-v2 -ep 1000 discount 0.9 -n 100 -e 3-l 2 -s 64 -b <b*> -lr <r*> -rtg exp_name ip_b<b*>_r<r*>

where your task is to find the smallest batch size b* and largest learning rate r* that gets to optimum (maximum score of 1000) in less than 100 iterations. The policy performance may fluctuate around 1000 this is fine. The precision of b* and r* need only be one significant digit.

Deliverables:

• Given the b* and r* you found, provide a learning curve where the policy gets to optimum (maximum score of 1000) in less than 100 iterations. (This may be for a single random seed, or averaged over multiple.)
• Provide the exact command line configurations you used to run your experiments.

6 Implement Neural Network Baselines

For the rest of the assignment we will use reward-to-go.

Problem 6. Neural network baseline: We will now implement a value function as a state-dependent neural network baseline. The sections in the code are marked by Problem 6.

• In build_computation_graph implement V, a neural network that predicts the expected return conditioned on a state. Also implement the loss function to train this network and its update operation self.baselineop.
• In compute_advantage, use the neural network to predict the expected state-conditioned return (use the session to call self.baselineprediction), normalize it to match the statistics of the current batch of reward-to-go, and subtract this value from the reward-to-go to yield an estimate of the advantage. This implements
• In update_parameters, update the parameters of the the neural network baseline by using the Tensorflow session to call self.baselineop. Rescale the target values for the neural network baseline to have a mean of zero and a standard deviation of one.

7 More Complex Tasks

Note: The following tasks would take quite a bit of time to train. Please start early!

Problem 7: LunarLander For this problem, you will use your policy gradient implementation to solve LunarLanderContinuous-v2. Use an episode length of 1000. The purpose of this problem is to help you debug your baseline implementation. Run the following command:

python train_pg_f18.py LunarLanderContinuous-v2 -ep 1000 discount 0.99 -n

100 -e 3 -l 2 -s 64 -b 40000 -lr 0.005 -rtg nn_baseline exp_name ll_b40000_r0.005

Deliverables:

• Plot a learning curve for the above command. You should expect to achieve an average return of around 180.

Problem 8: HalfCheetah For this problem, you will use your policy gradient implementation to solve HalfCheetah-v2. Use an episode length of 150, which is shorter than the default of 1000 for HalfCheetah (which would speed up your training significantly). Search over batch sizes b [10000,30000,50000] and learning rates r [0.005,0.01,0.02] to replace <b> and <r> below:

python train_pg_f18.py HalfCheetah-v2 -ep 150 discount 0.9 -n 100 -e 3 -l 2-s 32 -b <b> -lr <r> -rtg nn_baseline exp_name hc_b<b>_r<r>

Deliverables:

• How did the batch size and learning rate affect the performance?
• Once youve found suitable values of b and r among those choices (lets call them b* and r*), use b* and r* and run the following commands (remember to replace the terms in the angle brackets):

python train_pg_f18.py HalfCheetah-v2 -ep 150 discount 0.95 -n 100 -e 3-l 2 -s 32 -b <b*> -lr <r*> exp_name hc_b<b*>_r<r*> python train_pg_f18.py HalfCheetah-v2 -ep 150 discount 0.95 -n 100 -e 3-l 2 -s 32 -b <b*> -lr <r*> -rtg exp_name hc_b<b*>_r<r*> python train_pg_f18.py HalfCheetah-v2 -ep 150 discount 0.95 -n 100 -e 3-l 2 -s 32 -b <b*> -lr <r*> nn_baseline exp_name hc_b<b*>_r<r*> python train_pg_f18.py HalfCheetah-v2 -ep 150 discount 0.95 -n 100 -e 3-l 2 -s 32 -b <b*> -lr <r*> -rtg nn_baseline exp_name hc_b<b*>_r< r*>

The run with reward-to-go and the baseline should achieve an average score close to 200. Provide a single plot plotting the learning curves for all four runs.

NOTE: In an earlier version of the homework (before 9/13/18) we had the discount as

0.9, in which case the run with reward-to-go and baseline should achieve an average

score close to 150, and there would not be much difference between the runs with reward-to-go (with or without baseline). If you have already done this part with a discount of 0.9, you do not need to redo the problem, but you would then expect the best scoring run to be about 150 rather than 200.

8 Bonus!

Choose any (or all) of the following:

• A serious bottleneck in the learning, for more complex environments, is the sample collection time. In py, we only collect trajectories in a single thread, but this process can be fully parallelized across threads to get a useful speedup. Implement the parallelization and report on the difference in training time.
• Implement GAE- for advantage estimation.^[1] Run experiments in a MuJoCo gym environment to explore whether this speeds up training. (Walker2d-v1 may be good for this.)
• In PG, we collect a batch of data, estimate a single gradient, and then discard the data and move on. Can we potentially accelerate PG by taking multiple gradient descent steps with the same batch of data? Explore this option and report on your results. Set up a fair comparison between single-step PG and multi-step PG on at least one MuJoCo gym environment.

9 Submission

Your report should be a document containing

• Your mathematical response (written in L^ATEX) for Problem 1.
• All graphs requested in Problems 4, 5, 7, and 8.
• Answers to short explanation questions in section 5 and 7.
• All command-line expressions you used to run your experiments.
• (Optionally) Your bonus results (command-line expressions, graphs, and a few sentences that comment on your findings).

Please also submit your modified train_pg_f18.py file. If your code includes additional files, provide a zip file including your train_pg_f18.py and all other files needed to run your code. Please include a README.md with instructions needed to exactly duplicate your results (including command-line expressions).

Turn in your assignment by September 19th 11:59pm on Gradescope. Uploade the zip file with your code to HW2 Code, and upload the PDF of your report to HW2.

[1] https://arxiv.org/abs/1506.02438