Description
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
- http://jsonlint.com/
○ http://www.charactercountonline.com/
- Test your MDP locally with the provided tester to ensure you meet the submission requirements.
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 } ] } ] } ] } |
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:
