# Assignment 5

Assigned: Thu Oct 7, 2004
Due: Tue Oct 19, 2004

In this assignment, you must program a simple simulated environment and construct a reinforcement learning agent that discovers the optimal (shortest) path through the environment to reach a goal. The agent's environment will look like:

Each cell in this grid is a state in the environment. The cell labeled "I" is the initial state of the agent. The cell labeled "G" is the goal state of the agent. The black cells are barriers--states that are inaccessible to the agent. At each time step, the agent may move one cell to the left, right, up, or down. The environment does not wrap around. Thus, if the agent is in the lower left corner and tries to move down, it will remain in the same cell. Likewise, if the agent is in the initial state and tries to move up (into a barrier), it will remain in the same cell.

You should implement a Q learning algorithm that selects moves for the agent. The algorithm should perform exploration by choosing the action with the maximum Q value 95% of the time, and choosing one of the remaining three actions at random the remaining 5% of the time.

The simulation runs until the agent reaches the goal state. The reward at the goal is 0, but at every other state is -1 (because it takes energy for the agent to move). Because this simulation has a finite running time, you do not need to use a discounting factor, i.e., you can set the discounting parameter γ (gamma) to one.  Because the environment is deterministic, you can set the averaging constant--denoted by the greek letter α (alpha) in the text and ξ (xi) in my notes--to one as well (i.e., the new Q estimate replaces the old Q estimate).

## Write up

Your write up should include the following:
• a graph showing number of steps required to reach the goal as a function of learning trials (one "trial" is one run of the agent through the environment until it reaches the goal). When you make your graph, it will be very noisy if you plot each learning trial separately. Thus, you may want to plot average number of steps over 10-trials blocks.
• a figure showing the policy of your agent. The policy can be summarized by making an array of cells corresponding to the states of the environment, and indicating the direction (up, down, left, right) that the agent is most likely to move if it is in that state.
• a figure showing the utility function. The utility function can be summarized by making an array of cells corresponding to the states of the environment, and indicating the maximum Q value associated with a state in the corresponding cell. The utility function thus indicates the number of steps to the goal assuming the optimal action according to the Q table is chosen.
• In addition to running the simulation with an exploration rate of 5%, try 1% and also 20%. Plot the learning curves for these different exploration rates. You should find that the lower exploration rates lead to slower learning but higher asymptotic performance.