CSE 151 Introduction to Artificial Intelligence
Programming Assignment 3

Reinforcement learning in the Grid world take 2

Due date to be specified.

RULES:
- You will be responsible for any updates to the assignment that are posted to the discussion board, so please check it regularly.
- The programs must be written in Matlab
- Programs must be submitted using the turnin procedure by 11:59pm on the due date
- You may work in groups of two or three
- Turn in a writeup and all the source files (see what to turn in below)
- Make sure to comment your code!  This means have comments describing each function as well as comments throughout the code.

In this assignment, you will be building upon your previous architecture of the grid world and experimenting with some other techniques.

Part 1:  Acting in an unknown world
For the first part, you need to implement two different active reinforcement learning methods:  active ADP and Q-learning.  Use the same grid specification from the previous assignment.  You'll need to use your "read_grid" function to read in the world.  Notice that although you as the programmer have access to the real world, for these two algorithms the world is not available to the agent.  I will post a good solution from the previous assignment soon if you don't want to use your own.

a. Implement active ADP algorithm.  pg. 768 and the textbook shows the PASSIVE ADP algorithm.  You need to modify this algorithm to support a changing policy as specified in section 21.3 You'll need to use your value_iteration algorithm as a sub-procedure for this function.  Use the exploration function defined on pg. 774 starting with R+ == 2 and N_e == 5.  

b.  Implement the Q-learning algorithm on pg. 776 using the same exploration function and parameters as in (a).

c.  Provide a "README" file showing examples of each of your programs running and how to run the program.  Unlike before, you may decide exactly how to define the functions.

Part 2:  Experimenting with your algorithms
For the second part of the assignment, you are to experiment with these algorithms and write up a paper in a style appropriate for a conference.  What you should try and do is explain how this algorithms behave, specifically, how do they work with different reward structures?,  different grid worlds (i.e. change the sizes, etc.)?  How does the setting of the exploration rate effect performance?  Which algorithm is better?  Is one better in certain situations? Others?

In doing this make graphs showing the convergence as in 21.7a as well as other graphs and tables you feel are appropriate for analyzing the algorithms.

Write a short paper describing your experiments, including an short abstract summarizing your results, an introduction very briefly describing the algorithms, an "experiments" section, describing how your experiments, a "discussion" section, where you discuss the results, and finally a short "conclusions" section.

The paper should be in good English and should be formatted appropriately for a conference submission.  See http://www-2.cs.cmu.edu/Web/Groups/NIPS/NIPS2001/formatting.html for styles files for word and latex.  In your writing make sure that it is clear and concise.  Make sure that you clearly explain the experiments you did and have clear arguments that are supported by the data obtained from your experiments.

What to turn in:
- A tar file with...
- All of your commented matlab code.
- Your paper in .doc, .ps or .pdf form from part 2.
- A README file with
  - A very brief overview of the code
  - Example runs
  - A separate paragraph by each team member stating:
	what that team member contributed to the project.
	what that team member learned from the project.