# Q-learning

1. Using your favorite search engine, find a simple tutorial on Q-learning. Read the tutorial.

2. Implement Q-learning. Here is some pseudocode for one iteration of Q-learning. Your program will call this in a loop until it converges:
```// Pick an action
Let Q be a table of q-values;
Let i be the current state;
Let ε = 0.05;
if(rand.nextDouble() < ε)
{
// Explore (pick a random action)
action = rand.nextInt(4);
}
else
{
// Exploit (pick the best action)
action = 0;
for(int candidate = 0; candidate < 4; candidate++)
if(Q(i, candidate) > Q(i, action))
action = candidate;
if(Q(i, action) == 0.0)
action = rand.nextInt(4);
}

// Do the action
do_action(action);
Let j be the new state

// Learn from that experience
Apply the equation below to update the Q-table.
a = action.
Q(i,a) refers to the Q-table entry for doing
action "a" in state "i".
Q(j,b) refers to the Q-table entry for doing
action "b" in state "j".
Use 0.1 for αk. (Don't get "αk" mixed up with "a".)
use 0.97 for γ (gamma).
A(j) is the set of four possible actions, {<,>,^,v}.
r(i,a,j) is the reward you obtained when you landed in state j.

// Reset
If j is the goal state, teleport to the start state.
```
Here is the equation that you will implement at the core of your Q-learner: .

3. Implement a simple grid-world. Use dimensions of 20 wide and 10 high. There are 4 possible actions: {left, right, up, down}. Start in one corner. Place a reward in the opposite corner. Place a wall of penalty states with a small hole through which the agent can pass somewhere between the start and goal states. Use some probability that actions will cause unintended behavior. Use Q-learning to learn a policy for solving this problem. (Your Q-table will require 20*10*4=800 elements. Initialize them with zeros, then iteratively apply Q-learning until your Q-table converges to represent a good policy for this game.)

4. Print your policy at periodic intervals to the console while it learns. Use "#" to indicate a penalty state, "G" to indicate a goal, and the characters "<,>,^,v" to indicate left, right, up, and down for the policy in all other states. Example:
```	> > v v v v v v < < # > > > > > > > > G
> v > v v v v v v < # > > > > > > > ^ ^
> > > > > v v v v < # > > > > > ^ ^ ^ ^
> > > > > v v v v < # > > > > > ^ ^ ^ ^
> > > > > > v v v < # > > > > ^ ^ ^ ^ ^
> > > > > > > > v v # > > > ^ ^ ^ ^ ^ ^
> > > > > > > > > > > > > ^ ^ ^ ^ ^ ^ ^
> > > > > > > > > > > > > ^ ^ ^ ^ ^ ^ ^
> > > > > > > > ^ ^ # > > > ^ ^ ^ ^ ^ ^
> > > > > > > > ^ ^ # > > > ^ ^ ^ ^ ^ ^
> > > > > > > > ^ ^ # > > > ^ ^ ^ ^ ^ ^
> > > > > > > ^ ^ < # > > > ^ ^ ^ ^ ^ ^
> > > > > ^ ^ ^ ^ < # > > > ^ ^ ^ ^ ^ ^
> > > > ^ ^ ^ ^ ^ < # > > > ^ ^ ^ ^ ^ ^
S > > ^ ^ ^ ^ ^ ^ < # > > > ^ ^ ^ ^ ^ ^
```

5. If you are taking the graduate scetion of this class, if your program is executed with an optional command-line parameter, "nn", use a neural network to implement your Q-table instead of some other data structure.

You can use the neural network from previous assignments. Some fiddling may be necessary to find a suitable number of layers, and other meta-parameters to get it working. The neural network may require many more iterations for convergence to occur.

I recommend using two inputs {x,y} and 4 outputs {q-left,q-right,q-up,q-down}. Here is an example that makes a neural network with the topology 2->16->4:
```Random rand = new Random(1234567);
NeuralNet nn = new NeuralNet();
nn.init(rand);
```
To refine your neural network, call "trainIncremental(in, out, 0.03)", where "in" is your input vector, "out" is your output vector, and 0.03 is a reasonable learning rate. Remember to train it using values that have been normalized to fall approximately in the range [0,1]. To make a prediction with your neural network, call "forwardProp(in)", and it will return the vector of 4 Q-values for the state you specify.

If you only want to refine one of the 4 q-values, then use the predicted values for the other 3 q-values when you call "trainIncremental". That way, it will only attempt to change the one q-value for which it is making different predictions. So, let Then, instead of doing Q(i,a)=(1-α)*Q(i,a)+α*t, do
```double[] prediction = nn.predict(i);
double[] copy = Vec.copy(prediction);
copy[a] = t;
nn.trainIncremental(i, copy); // This line updates the neural net
```

6. Click on the "Project submission" link on the main class page to submit your archive file. If you have any difficulties with the submission server, please e-mail your submission directly to the grader.