Description
CS7642 Homework #1 Finding an Optimal Policy
The game DieN is played in the following way.
Consider a die with N sides (where N is an integer greater than 1) and a nonempty set B of
integers. The rules of the game are:
1. You start with 0 dollars.
2. Roll an N-sided die with a different number from 1 to N printed on each side.
a. If you roll a number not in B, you receive that many dollars. (eg. if you roll the
number 2 and 2 is not in B, then you receive 2 dollars.)
b. If you roll a number in B, then you lose all of your obtained money and the game
ends.
3. After you roll the die (and don’t roll a number in B), you have the option to quit the game.
If you quit, you keep all the money you’ve earned to that point. If you continue to roll, go
back to step 2.
Procedure
● For this problem, determine an optimal policy for playing the game DieN with N sides. You
will be given N and an array B (isBadSide) which indicates which sides are bad. The policy
should depend on your current bankroll.
● What is the expected value of this game if you follow an optimal policy? Answer for the
problems you are given in the Solve for Code tab.
Examples
The following examples can be used to verify your calculation is correct.
● Input: N = 21, isBadSide = {1,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,1,0}, Output: 7.3799
● Input: N = 22, isBadSide = {1,1,1,1,1,1,0,1,0,1,1,0,1,0,1,0,0,1,0,0,1,0}, Output: 6.314
1
● Input: N = 6, isBadSide = {1,1,1,0,0,0}, Output: 2.5833
Resources
The concepts explored in this homework are covered by:
● Lectures
○ Lesson 1: Smoov & Curly’s Bogus Journey
● Readings
○ Littman (1996)(chapters 1-2)
Submission Details
To complete the assignment calculate answers to the specific problems given, and submit
results, at
https://rldm.herokuapp.com
2
CS7642 Homework #2 TD( λ )
Recall that the TD( λ ) estimator for an MDP can be thought of as a weighted combination of the
k-step estimators E for k ≥ 1. k
Consider the MDP described by the following state diagram. (Assume the discount factor is γ = 1.)
Procedure
● Find a value of λ , strictly less than 1, such that the TD estimate for λ equals that of the
TD(1) estimate. Round your answer for λ to three decimal places.
● This HW is designed to help solidify your understanding of the Temporal Difference
algorithms and k-step estimators. You will be given the probability to State 1 and a vector
of rewards {r0, r1, r2, r3, r4, r5, r6}
● You will be given 10 test cases for which you will return the best lambda value for each.
Your answer will be graded to 0.001 precision. You may use any programming language
and libraries you wish.
1
Examples
The following examples can be used to verify your calculation is correct.
● Input: probToState=0.81, valueEstimates={0.0,4.0,25.7,0.0,20.1,12.2,0.0},
rewards={7.9,-5.1,2.5,-7.2,9.0,0.0,1.6}, Output: 0.6226326309908364
● Input: probToState=0.22, valueEstimates={0.0,-5.2,0.0,25.4,10.6,9.2,12.3},
rewards={-2.4,0.8,4.0,2.5,8.6,-6.4,6.1}, Output: 0.49567093118984556
● Input: probToState=0.64, valueEstimates={0.0,4.9,7.8,-2.3,25.5,-10.2,-6.5},
rewards={-2.4,9.6,-7.8,0.1,3.4,-2.1,7.9}, Output: 0.20550275877409016
Resources
The concepts explored in this homework are covered by:
● Lectures
○ Lesson 3: TD and Friends
● Readings
○ Sutton (1988)
Submission Details
To complete the assignment calculate answers to the specific problems given, and submit
results, at
https://rldm.herokuapp.com
2
CS7642 Homework #3 Defeat Policy Iteration
Problem Description Policy iteration (PI) is perhaps the most under appreciated algorithm for solving MDPs. Although each iteration is expensive, it generally requires very few iterations to find an optimal policy. In this problem, you’ll gain an appreciation for how hard it is to get policy iteration to break a sweat. Currently, it is not known whether there is an MDP which requires more than a linear number of PI iterations in the number of states of the MDP. Your goal is to create a 30 state MDP that attains at least 15 iterations of PI before the algorithm terminates. Procedure ● Construct an MDP with at most 30 states and at most 2 actions per state. You may assume the discount factor is 3/4. The MDP may have stochastic transitions. ● Use an editor or a simple program to create a json description of the target MDP that is parseable by the tester. ○ the json created should use double quotes instead of single quotes ○ the entire description must be less than 100,000 characters ● Validate your description ○ https://jsonlint.com/ ○ https://www.charactercountonline.com/ ● Test your MDP locally with the provided tester to ensure you meet the submission requirements. 1 Example The following is an example of the json definition of a simple MDP { “gamma”:0.75, “states”: [ { “id”: 0, “actions”: [ { “id”: 0, “transitions”: [ { “id”: 0, “probability”: 0.5, “reward”: 0, “to”: 0 }, { “id”: 1, “probability”: 0.5, “reward”: 0, “to”: 1 } ] } ] }, { “id”: 1, “actions”: [ { “id”: 0, “transitions”: [ { “id”: 0, “probability”: 1, “reward”: 1, “to”: 1 } ] } ] } ] } 2 Resources The concepts explored in this homework are covered by: ● Lectures ○ Lesson 1: Smoov & Curly’s Bogus Journey ○ Lesson 5: AAA ● Readings ○ Littman (1996)(chapters 1-2) Additionally, a tool to create and test your MDPs can be found here: TBD Submission Details Due Date: Oct 8, 2017 (AOE) Your MDP definition must reach 15 iterations. No partial credit will be given for less that 15 iterations. All solutions that achieve 15 iterations will receive full credit. The top 10 solutions will get an additional 10 points of extra credit for this assignment. You will be ranked by number of iterations (higher, better) and last submission datetime (smaller, better). Go to to see these rankings pseudo-realtime. To complete assignment, submit the description of your MDP to: https://rldm.herokuapp.com Finally, those of you able to obtain more than 31 iterations are eligible for a smiley-face sticker ͳ. Please send a self-addressed, stamped envelope to: Box 1910 Computer Science Department Brown University 3 115 Waterman St. Providence, RI 02912 4
CS7642 Homework #4 Q-Learning
In this homework you will have the complete RL experience. You will work towards implementing
and evaluating the Q-learning algorithm on a simple domain. Q-learning is a fundamental RL
algorithm and has been successfully used to solve a variety of decision-making problems. For this
homework, you will have to think carefully about algorithm implementation, specially exploration
parameters.
The domain you will be tackling is called Taxi (Taxi-v2). It is a discrete MDP which has been used
for RL research in the past. This will also be your first opportunity to become familiar with the
OpenAI Gym environment (https://gym.openai.com/). This is a cool and unique platform where
users can test their RL algorithms over a selection of domains.
The Taxi problem was introduced in Dietterich(2000). It is a grid-based domain where the goal of
the agent is to pick up a passenger at one location and drop them off in another. There are 4
fixed locations, each assigned a different letter. The agent has 6 actions; 4 for movement, 1 for
pickup, and 1 for dropoff. The domain has a discrete state space and deterministic transitions.
Procedure
Implement a basic version of the Q-learning algorithm and use it to solve the taxi domain. The
agent should explore the MDP, collect data to the learn the optimal policy and the optimal
Q-value function. (Be mindful of how you handle terminal states, typically if St is a terminal state,
V(St+1) = 0). Use ? = 0.90. Also, you will see how Epsilon-Greedy strategy can find the optimal
policy despite of finding sub-optimal q-values. Because we are looking for optimal q-values, you
will have to try different exploration strategies.
You can evaluate your agent offline or by uploading your experiment file to the OpenAI server
using a GitHub account. The latter will generate a learning curve (reward/steps vs episodes)
which is indicative of performance. The OpenAI server will indicate if your implementation has
solved the domain, that is, found an optimal policy. Note that all evaluations uploaded to the
OpenAI server are publicly accessible. However, please do not attach your code as a gist
write-up to these evaluation.
1
Examples
Below are the optimal Q values for 5 (state, action) pairs of the Taxi domain.
● Q(462, 4) = -11.374402515
● Q(398, 3) = 4.348907
● Q(253, 0) = -0.5856821173
● Q(377, 1) = 9.683
● Q(83, 5) = -12.8232660372
Resources
The concepts explored in this homework are covered by:
● Lectures
○ Convergence
○ Exploring Exploration
● Readings
○ Asmuth-Littman-Zinkov-2008.pdf
○ littman-1996.pdf (chapters 1-2)
Submission Details
You will be evaluated based on optimality of results. This will be assessed by your algorithm’s
optimal Q-values for 10 specific state-action pairs (remember to use ? = 0.90). You will submit
your results to 10 problems selected for you on the rldm website. The values will be graded on a
0.01 precision threshold.
Optionally, you might want to, with the same implementation, solve the environment under
OpenAI’s criteria. If you accomplish that, you definitely learned something about exploration vs
exploitation, the difference between optimal policy and optimal q-values, and should be proud
about that.
Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial
Intelligence Research, 13, 227–303.
2
CS7642 Project #1 Desperately Seeking Sutton
One aspect of research in reinforcement learning (or any scientific field) is the replication of
previously published results. One benefit of replication is to aid your own understanding of the
results. Another is that it puts you in a good position for being able to extend and compare new
contributions to what is in the existing literature. Replication can be very challenging.
Researchers often find that important parameters needed to replicate results from papers are not
stated in the papers, that the procedures stated in papers have ambiguity, or that there are subtle
errors in the paper. Sometimes obtaining the same pattern of results is not possible.
For this project, you will read Richard Sutton’s 1988 paper Learning to Predict by the Methods of
Temporal Differences. Then you will create an implementation and replication of the results
found in figures 3, 4, and 5. (It might also be informative to compare these results with those in
Chapter 7 of Sutton’s textbook: “Reinforcement Learning: An Introduction”.)
You will present your work via a 2-to-5-page written report. The report should include a
description of the experiment replicated, how the experiment was implemented, and the
outcome of the experiment. You should describe how well the results match the results given in
the paper as well as significant differences. Describe any pitfalls you ran into while trying to
replicate the experiment from the paper (e.g. unclear parameters, contradictory descriptions of
the procedure to follow, results that differ wildly from the published results). What steps did you
take to overcome those pitfalls? What assumptions did you make? And, why these assumptions
are justified?
Procedure
As noted, replicating results can be challenging. Expect some issues along the way and be
prepared to resolve them.
● Read Sutton’s Paper
● Write the code necessary to replicate Sutton’s experiments
○ You will be replicating figures 3, 4, and 5
1
● Create the graphs
○ Replicate figures 3, 4, and 5
○ Graphs of anything else you may think appropriate
● Write a paper describing the experiments and how you replicated them
○ 5 pages maximum — really, you will lose points for longer papers.
○ The paper should include your graphs.
■ And, discussions regarding them
○ Describe the experiments
■ Discuss the implementation
■ Discuss the outcome
■ The generated data
○ Describe your results
■ How do they match
■ How do they differ
○ Describe any problems/pitfalls you encountered
■ How did you overcome them
■ What were your assumptions/justifications for this solution
○ Save this paper in PDF format
● Upload your code to a private Georgia Tech GitHub repository
○ https://github.gatech.edu/
○ – 20 points if you do not submit a link to your code
○ Make a README.md file for your repository
■ Include thorough and detailed instructions on how to run your source code
○ Add all the TA’s to your repository
■ tbail3, jsu46, afeuerstein3, pkolhe3, mmorales34, cserrano7, tzhu71,
aecoffet3, vfelso3
● Create a README.txt with a link to your GitHub repository.
Resources
The concepts explored in this project are covered by:
● Lectures
○ Lesson 4: TD and Friends
● Readings
○ Learning to Predict by the Methods of Temporal Differences
2
Grades will be based on the fidelity of the replication, how well you show you understand the
original paper, and your written report. Late submissions will be accepted with in a day of the due
date with a -20% penalty. Submissions any later than that will receive no credit.
The submission consists of
● Your written report in PDF format
● A README.txt file containing a link to the private GitHub repository containing all code
you created for this project.
To complete assignment submit both your written report and the README.txt to Project #1 under
your Assignments on Canvas::
https://gatech.instructure.com
You may submit the assignment as many times as you wish up to the due date, but, we will only
consider your last submission for grading purposes.
3
CS7642 Project #2 Lunar Lander
For this project, you will be writing an agent to successfully land the “Lunar Lander” that is
implemented in OpenAI gym. You are free to use and extend any type of RL agent discussed in
this class.
Lunar Lander Environment
The problem consists of a 8-dimensional continuous state space and a discrete action space.
There are four discrete actions available: do nothing, fire the left orientation engine, fire the main
engine, fire the right orientation engine. The landing pad is always at coordinates (0,0).
Coordinates consist of the first two numbers in the state vector. The total reward for moving from
the top of the screen to landing pad ranges from 100 – 140 points varying on lander placement on
the pad. If lander moves away from landing pad it is penalized the amount of reward that would
be gained by moving towards the pad. An episode finishes if the lander crashes or comes to rest,
receiving additional -100 or +100 points respectively. Each leg ground contact is worth +10 points.
Firing main engine incurs a -0.3 point penalty for each occurrence. Landing outside of the landing
pad is possible. Fuel is infinite, so, an agent could learn to fly and then land on its first attempt.
The problem is considered solved when achieving a score of 200 points or higher.
Agent Representation
As noted earlier, there are four actions available to your agent:
do nothing, fire the left orientation engine, fire the main engine, fire the right orientation engine
1
Additionally, at each time step, the state is provided to the agent as a 8-tuple:
(x, y, vx, vy, θ, vθ, left-leg, right-leg)
x and y are the x and y-coordinates of the lunar lander’s position. vx and vy are the lunar lander’s
velocity components on the x and y axes. θ is the angle of the lunar lander. vθ is the angular
velocity of the lander. Finally, left-leg and right-leg are binary values to indicate whether the left
leg or right leg of the lunar lander is touching the ground. It should be noted, again, that you are
working in a six dimensional continuous state space with the addition of two more discrete
variables.
Procedure
This problem is more sophisticated than anything you have seen so far in this class. Make sure
you reserve enough time to consider what an appropriate solution might involve and, of course,
enough time to build it.
● Create an agent capable of solving the Lunar Landar problem found in OpenAI gym
○ Upload/maintain your code to in private repo at https://github.gatech.edu
○ Use any RL agent discussed in the class as your inspiration and basis for your
program
● Make a README.md file for your repository
○ Include thorough and detailed instructions on how to run your source code
○ Include the link to your private repo
● Create graphs demonstrating
○ The reward for each training episode while training your agent
○ The reward per trial for 100 trials using your trained agent
○ The effect of hyper-parameters (alpha, lambda, epsilon) on your agent
■ You pick the ranges
■ Be prepared to explain why you chose them
○ Anything else you may think appropriate
● Write a paper describing your agent and the experiments you ran
○ 5 pages maximum — really, you will lose points for longer papers.
○ The paper should include your graphs.
■ And, discussions regarding them
○ Discuss your results
○ Explain the algorithms you selected and why you did
○ Describe any problems/pitfalls you encountered
○ Explain your experiments
2
○ Include a link to your presentation
○ Do not include a link to your code
● Create another README.txt with a link to your code.
Resources
The concepts explored in this project are covered by:
● Lectures
○ Generalization
● Readings
○ Sutton Ch. 9 On-Policy Prediction with Approximation
○ https://incompleteideas.net/sutton/book/bookdraft2017june19.pdf
● Source Code
○ https://github.com/openai/gym
○ https://github.com/openai/gym/blob/master/gym/envs/box2d/lunar_lander.py
● Documentation
○ https://gym.openai.com/docs
● Examples (use for inspiration, you are still required to write your own code)
○ https://gym.openai.com/envs/LunarLander-v2
Submit:
1. Your paper as a pdf (containing your report)
2. A README.txt file (containing a link to your GitHub repository)
via T-Square:
3
Tips
● If you worked on HW4, you most likely checked out an older version of OpenAI gym.
Please remember to update to the latest version for this assignment.
● If you get a Box2D error when running gym.make(‘LunarLander-v2’), you will have to
compile Box2D from source. Please follow these steps:
pip uninstall box2d-py
git clone https://github.com/pybox2d/pybox2d
cd pybox2d/
python setup.py clean
python setup.py build
sudo python setup.py install
Try running Lunar Lander again. Source: https://github.com/openai/gym/issues/100
● Even if you don’t get perfect results or even build an agent that solves the problem you
can still write a solid paper.
4
