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
○ http://jsonlint.com/
○ http://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
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
