Q-Learning - Reinforcement Learning - Solved Example - 1 * Suppose we have 5 rooms in a building connected by doors as shown in the figure below. We'll number each room 0 through 4. The outside of the building can be thought of as one big room (5). Notice that doors 1 and 4 lead into the building from room 5 (outside).Q-Learning - Reinforcement Learning - Solved Example - 1 * We can represent the rooms on a graph, each room as a node, and each door as a link.Q-Learning - Reinforcement Learning - Solved Example - 1 * The goal room is number 5 * The doors that lead immediately to the goal have an instant reward of 100. Other doors not directly connected to the target room have zero reward. + Each arrow contains an instant reward value, as shown below:Q-Learning - Reinforcement Learning - Solved Example - 1 * We can put the state diagram and the instant reward values into the following reward table, "matrix R". The -1's in the table represent null values (i.e.; where there isn't a link between nodes). For example, State 0 cannot go to State 1. Action State O 12 3 4 5 -1-l -l1-1 0 -l al a. at 0 1 100 -1 -1 -l1 0-1 -l -l1 0 0-1 0 -l O 1-1 O 71 100 -1 0-1-1 0 100 Goal State UBRWNHKOQ-Learning - Reinforcement Learning - Solved Example - 1 * Learning rate = 0.8 and the initial state as Room 1. * Initialize matrix Q as a zero matrix: Action 012345 Stte G i 2 a4 4 0 10 0000 lem ae on To oo 008 1 |-l -1 -1 0-11 = R= 2 |[-l-1-1 0-1 -1 = toe ee 3 1 0 0-1 0 -1 4 | 0-1-1 0 -1 100] 41000000 5 |-1 0-1-1 0 100 5jo00000Q-Learning - Reinforcement Learning - Solved Example - 1 * Look at the second row (state 1) of matrix R. + There are two possible actions for the current state 1: go to state 3, or go to state 5. * By random selection, we select to go to 5 as our action. Action Ste 0 1 eae Hl -1-1-1 0 =I -1 -1 a 0 -1 100 -1-1-1 0-1 -l -1 0 0-1 0 -l 0-1-1 0 -1 100 -1 0-1-1 0 100 UbWNHSQ-Learning - Reinforcement Learning - Solved Example - 1 Now let’s imagine what would happen if our agent were in state 5 (next state). Look at the sixth row of the reward matrix R (i.e. state 5). It has 3 possible actions: go to state 1, 4 or 5. Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]} Q(1, 5) = R(1, 5) +Q8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100 + 0.8 * 0 = 100 Action 012345 State 0 12 3 4 5 ofooo00o00 o fel -1 -1 -1 0 -1 llo00000 1 |-1 -1 -1 0 -1 100) = R= 2 |-1-1-1 0-1 -1 Q= 21000000 Bl 0 01 0 1 3j000000 4 | 0-1-1 0 -1 100 41000000 5 |-1 0-1-1 0 100 5jo00000Q-Learning - Reinforcement Learning - Solved Example - 1 Now let’s imagine what would happen if our agent were in state 5. Look at the sixth row of the reward matrix R (i.e. state 5). It has 3 possible actions: go to state 1, 4 or 5. Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)] Q(1, 5) = R(1, 5) + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100+ 0.8 * 0= 100 Action O@iae8s State 0 12 3 4 5 m10 0 0 0 0 0 0 f-l-1-1-1 0 -1 1]0 0 0 0 O1Q0 1 |-1 -1 -1 0 -1 100 2]0 00000 eae o te 3/0 00000 4 ]0-1-1 0 -1 100 are 5 |-1 0-1-1 0 100Q-Learning - Reinforcement Learning - Solved Example - 1 * The next state, 5, now becomes the current state. * Because 5 is the goal state, we've finished one episode. * Our agent’s brain now contains an updated matrix Q as: 012 3 4 5 ofo 00000 s 10 0 0 0 0100 Q=2])000000 3/0 0 0000 40 0 0000 slo 00000Q-Learning - Reinforcement Learning - Solved Example - 1 * For the next episode, we randomly choose the initial state — say 3 (can go to 1, 2 & 4) Action Stte UW 1 224 A -l-l1-1-1 0 -l -1 -1 -1 0 -1 100 -l1 -1 -1 0-1 -l -1 0 0-1 0 -l 0-1-1 0 -1 100 -1 0-1-1 0 100 UBWNRO * Now we imagine that we are in state)1 (next state).Q-Learning - Reinforcement Learning - Solved Example - 1 Now we imagine that we are in state 1 (next state). Look at the second row of reward matrix R (i.e. state 1). It has 2 possible actions: go to state 3 or state 5. Then, we compute the Q value: Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)] Q(3, 1) = R(3, 1) + 0.8 * Max[Q(1, 3), Q(1, 5)] = 0 + 0.8 * Max(0, 100) = 80 an 012345 ste 0 123 4 5 blo 0 0 0 0 0 ioe i1fo 00000 1 1-1-1 0 -1 100 4 R= 2 |1-1-1 0-1 -1 Q= 2]0 0 0 0 0100 3 o 00:0 0 3 |-1 0 0-1 0 -1 alo a a 4] 0-1-1 0 -1 100 5 |-1 0 -1 -1 0 100] 5jo 00000Q-Learning - Reinforcement Learning - Solved Example - 1 * If our agent learns more through o1234 5 . ae will fi o;/ 0 0 0 0 8 9O further episodes, it will finally 1] ogo 0 64 0 109 reach convergence values in Q=2/ 0° 0 0 & 0 oO 3} 0 80 S51 0 80 0 matrix Q like: 4/64 0 0 G4 0 100 5S} 0 80 0 0 80 100] Tracing the best sequences of states is as simple as following the ou sate links with the highest values at each state.