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 ○ 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