CSCI 364: Homework Assignment #3

You can download the assignment instructions by clicking on this link

Instructions for using GitHub for our assignments can be found on the Resources page of the class website, as well as using this link.

Tips

To help speed up your Value Iteration algorithm, it is helpful to keep track of which next states are possible for each (current state, action) pair. For example, in our Game Show Worksheet, each state only had one possible next state when the Quit action is chosen, and only two or three possible next states when the Answer action is chosen, even though there are 12 possible states (Rounds 1-10, Quit with winnings, and Lost). In the wildfire.mdp Wildfire Suppression problem, each (current state, action) pair has non-zero state transition probability to far fewer than the 2304 total possible next states.

To find what next states are possible for each (current state, action) pair, you could loop over all possible next states and only save the ones that have a transition probability of more than 0%. Doing so once for each (current state, action) pair when you parse the MDP file will not take nearly as much time as doing so during every iteration of the while loop in the Value Iteration algorithm.

Then, when you are implementing the while loop of Value Iteration, the third for loop over next possible states only needs to loop over the next states that are possible for the (current state, action) pair [determined by the first two for loops] instead of all states. This should cause each iteration of the while loop to run in a few seconds at most, instead of minutes.

Testing your Code

To help test your code, I've also included a game_show.mdp file in your GitHub repository that encodes the MDP from the Game Show Worksheet, which is small enough that you should be able to hand trace the Value Iteration algorithm. The expected final calculations for this MDP are (using γ = 1.0):