.. role:: python(code) :language: python .. index:: reinforcement learning; environment reinforcement learning; game reinforcement learning; magic tram reinforcement learning; swamp isle reinforcement learning; learning rate reinforcement learning; temporal difference environment learning rate temporal difference .. `Environment in reinforcement learning ` `Reinforcement learning algorithms ` `Reinforcement leaning magic tram ` `Reinforcement leaning swamp isle ` .. _`sec:rl_examples`: Examples -------- Environment ^^^^^^^^^^^ Before implementing the reinforcement learning algorithm, it is very useful to implement the *real* world from which episodes will be sampled. This environment will be based on a **known** MDP, and its job is to yield on demand random episodes which respect asymptotically the MDP (transitions and rewards). The goal of this entire section is to implement, test the reinforcement learning algorithms and show that they enable to learn from the interactions with the environment. Depending on the learning algorithm, either the MDP itself is estimated, or the qualities of a policy, or the optimum policy. .. literalinclude:: ../../../../src/ai/reinforcement/environment_types.py :name: environment_types :linenos: :caption: src .. admonition:: Exercise (intermediate) Implement and test :python:`EnvironmentFromMDP`. .. _`ex:rl_environment`: .. collapse:: Correction .. literalinclude:: ../../../../src/ai/reinforcement/environment_from_mdp.py :pyobject: EnvironmentFromMDP :name: environment_from_MDP :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_environment_from_mdp.py :name: test_environment_from_MDP :linenos: :caption: tests Game ^^^^ .. admonition:: Exercise (difficult) For the four following questions, use a :python:`RandomPolicy`. 1. Implement and test the model based Monte-Carlo algorithm. Add a :python:`export_to_MDPMapping` method. 2. Implement and test the model free Monte-Carlo algorithm. 3. Implement and test the Sarsa algorithm. 4. Implement and test the Q-learning algorithm. .. collapse:: Hints The four algorithms work iteratively: the estimation is incrementally improved. The easiest way is to loop a certain amount of times over all discovered states, each time generate an episode and use it with one of the algorithm. Obviously, it would be even better have a convergence check: either for every estimated transition, or quality. This step is not implemented in the correction. These algorithms are not easy to test because of the randomness from the environment sampling. However, if the :python:`environment` is an input parameter of the function, it is a prime example of a dependency injection. It allows to feed a tweaked environment which behaves the same, but which is not random. For example: .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: DummyGameEnvironment :name: DummyGameEnvironment :linenos: :caption: tests This environment will always produce the same episode. .. collapse:: Hints 1. Maintain the number of times a :python:`(state, action, next_state)` and a :python:`(state, action)` has been encountered. The ratio between the two is the estimation of a transition. Use the class :python:`StateActionNextStateMetric` in a :python:`defaultdict`. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: StateActionNextStateMetric :name: StateActionNextStateMetric :linenos: :caption: src Do not forget to update your knowledge of the existing states. An approximation of the true transitions is expected. .. collapse:: Hints 2. Maintain the number of times :python:`(state, action)` has been encountered because it will be the :math:`N` in the convex combination. Use reversed full episode and maintain the qualities for every :python:`(state, action)`. Going in reverse, allows to easily calculate the discounted utility: :math:`u_t=r+\gamma u_{t+1}`. If you update the quality :python:`(state, action)` for every frame, it will automatically keep the first encounter of every :python:`(state, action)` of the episode. It ease much easier to first obtain the :python:`utilities` for every :python:`(state, action)` of the episode, and then perform the convex combination to update the qualities. An approximation of the **random policy** qualities are expected. .. collapse:: Hints 3. This the hardest of the four to implement because you need a pick view of the next action. However, a frame is :python:`state, action, reward, next_state`. At a current frame, you do not have the next action. A possibility is to loop by hand with a :python:`while` loop, calling :python:`next` on the episode iterator. This way you can manage to constantly have access to a frame and its successor. However, pay attention if the next state is an end state or not. An approximation of the **random policy** qualities are expected. .. collapse:: Hints 4. Similar to the previous one, but easier. You no longer need the next action, just the next optimal action from the next state. Do not forget to update the optimal policy mapping right after the convex combination update. An approximation of the **optimal policy** qualities are expected. .. _`ex:rl_algo`: .. collapse:: Correction 1. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: model_based_Monte_Carlo :name: model_based_Monte_Carlo :linenos: :caption: src .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: export_to_MDPMapping :name: export_to_MDPMapping :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: test_model_based_Monte_Carlo_dummy :name: test_model_based_Monte_Carlo_dummy :linenos: :caption: tests 2. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: model_free_Monte_Carlo :name: model_free_Monte_Carlo :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: test_model_free_Monte_Carlo_dummy :name: test_model_free_Monte_Carlo_dummy :linenos: :caption: tests 3. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: sarsa :name: sarsa :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: test_sarsa_dummy :name: test_sarsa_dummy :linenos: :caption: tests 4. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: qlearning :name: qlearning :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: test_qlearning_dummy :name: test_qlearning_dummy :linenos: :caption: tests Magic tram ^^^^^^^^^^ .. admonition:: Exercise (easy) Use the four previous algorithms on the magic tram problem. 1. Model based MC, comment on the result. 2. Model free MC and Sarsa, why don't we find the same qualities as the correction of the magic tram MDP exercise? 3. Qlearning, do we retrieve the optimal policy of the magic tram MDP exercise? Use this policy mapping in Model free MC and Sarsa to confirm that you find a satisfying estimation of the qualities of the magic tram MDP exercise. .. _`ex:rl_tram`: .. collapse:: Correction For :python:`nb_episodes_per_state` of 100_000 and a fail probability of 0.2. 1. The MDP and the fail probability are correctly estimated, the variance of the estimations between runs decreases when the :python:`nb_episodes_per_state` increases. .. code-block:: python {2: {'tram': {2: (0.20043060556168696, -2.0), 4: (0.799569394438313, -2.0)}, 'walk': {3: (1.0, -1.0)}}, 3: {'tram': {3: (0.19742429996892588, -2.0), 6: (0.8025757000310741, -2.0)}, 'walk': {4: (1.0, -1.0)}}, 4: {'tram': {4: (0.20133871320884553, -2.0), 8: (0.7986612867911544, -2.0)}, 'walk': {5: (1.0, -1.0)}}, 5: {'tram': {5: (0.2012801210754909, -2.0), 10: (0.7987198789245091, -2.0)}, 'walk': {6: (1.0, -1.0)}}, 6: {'tram': {6: (0.20070165624923997, -2.0), 12: (0.79929834375076, -2.0)}, 'walk': {7: (1.0, -1.0)}}, 7: {'walk': {8: (1.0, -1.0)}}, 8: {'walk': {9: (1.0, -1.0)}}, 9: {'walk': {10: (1.0, -1.0)}}, 10: {'walk': {11: (1.0, -1.0)}}, 11: {'walk': {12: (1.0, -1.0)}}, 12: {'walk': {13: (1.0, -1.0)}}, 13: {}} 2. The magic tram MDP correction gave the qualities of the optimal policy (value iteration algorithm). Here, the random policy is used. The two matches when the two policies are equivalent: when the only choice is to walk. .. code-block:: python {(2, 'tram'): -9.654715245560729, (2, 'walk'): -9.118302645579085, (3, 'tram'): -7.970203666250092, (3, 'walk'): -8.238426328292135, (4, 'tram'): -7.4482404985182455, (4, 'walk'): -7.0281073940240875, (5, 'tram'): -5.600584493424383, (5, 'walk'): -6.443788333294008, (6, 'tram'): -3.896297797594899, (6, 'walk'): -6.999999999999999, (7, 'walk'): -6.0, (8, 'walk'): -4.999999999999999, (9, 'walk'): -4.0, (10, 'walk'): -3.0, (11, 'walk'): -2.0, (12, 'walk'): -1.0} {(2, 'tram'): -9.481134252634465, (2, 'walk'): -8.877060965638796, (3, 'tram'): -7.858008074723888, (3, 'walk'): -8.09721124858775, (4, 'tram'): -7.409247009049843, (4, 'walk'): -6.930076577752609, (5, 'tram'): -5.580370812949426, (5, 'walk'): -6.380390930193599, (6, 'tram'): -3.8683076395406277, (6, 'walk'): -6.9511901596126995, (7, 'walk'): -5.98235136847001, (8, 'walk'): -4.994789408530305, (9, 'walk'): -3.998836675565334, (10, 'walk'): -2.9998236749092415, (11, 'walk'): -1.9999872676343076, (12, 'walk'): -1.0} 3. Yes. Using the optimum policy from Qlearning in Sarsa or Model free MC allows to retrieve the qualities from the magic tram MDP correction. .. code-block:: python {2: 'walk', 3: 'tram', 4: 'walk', 5: 'walk', 6: 'tram', 7: 'walk', 8: 'walk', 9: 'walk', 10: 'walk', 11: 'walk', 12: 'walk'} {(2, 'walk'): -7.0063599999999475, (3, 'tram'): -6.000875004375021, (6, 'tram'): -3.5002433349554973, (12, 'walk'): -1.0} {(2, 'walk'): -6.983584610287968, (3, 'tram'): -5.997740461664008, (6, 'tram'): -3.504182096707191, (12, 'walk'): -1.0} .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: reinforcement_learning_magic_tram :name: reinforcement_learning_magic_tram :linenos: :caption: src Swamp isle ^^^^^^^^^^ Rearranging the Q-learning equation, one gets: .. math:: :label: eq:rl_quality_modelfree_qlearning_bis \hat Q_{\textrm{opt}}^{(N+1)}(s, a) = \underbrace{\hat Q_{\textrm{opt}}^{(N)}(s, a)}_{\textrm{current}} + \underbrace{\alpha}_{\textrm{learning rate}} \left[ \underbrace{\left( r + \max_{a'} \gamma Q_{\textrm{opt}}^{(N)}(s', a') \right)}_{\textrm{target}} - \underbrace{\hat Q_{\textrm{opt}}^{(N)}(s, a)}_{\textrm{current}} \right] This form is a classical form of iterative correction where the current value is updated proportionally to the difference between the better / target value and the current value. In this context, it is sometimes referred as **temporal difference**. In the original equation, a strict convex combination is equivalent to :math:`\alpha= \cfrac{1}{N+1}`. However, the next exercise will illustrate that this rapidly decreasing learning rate is not efficient. .. admonition:: Exercise (intermediate) 1. Implement and test the epsilon greedy algorithm (with defaulting to a random strategy when a state is not present in the strategy mapping). 2. Modify and test the qlearning algorithm in order to mutate continuously the exploration policy to the estimated optimum policy. Use the epsilon greedy policy for exploration, initialize its mapping with a non optimal policy. Comment on the results. 3. Improve the qlearning algorithm by using a fixed learning rate. Comment on the results. .. _`ex:rl_swamp`: .. collapse:: Correction 1. The simplest experiment is to start with a failure probability of 0. This way the result should be identical to the state model and MDP exercises. Doin 2. Since the policy mapping is mutated along, there is no need to return a policy mapping at the end, the optimal policy is in the policy mapping of the policy. The counter (state, action) is no longer required because the learning rate is fixed. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: EpsilonGreedyPolicy :name: EpsilonGreedyPolicy :linenos: :caption: src .. literalinclude:: ../../../../tests/ai/reinforcement/test_reinforcement.py :pyobject: test_epsilon_greedy :name: test_epsilon_greedy :linenos: :caption: tests Even using a number of episodes per state very large (100_000 or even more), leads to very disappointing results: the qualities close to the destination are pretty well estimated, however, the qualities close to the starting position do not seen to converge. The problem with the decreasing learning rate is that the states close to the starting position are updated multiple times using very poor target values. The learning rate drops for these states, and later when target improves (from the destination), the corrections are too small. Using a random order for state traversal does not help to propagate the knowledge faster. With the fixed learning rate, the convergence is dramatically improved. .. code-block:: python {((0, 0), 'E'): -12.677577227122406, ((0, 0), 'S'): -12.667075392250679, ((0, 1), 'E'): -31.68226743698947, ((0, 1), 'S'): -31.66799828086022, ((0, 1), 'W'): -12.670359811413386, ((0, 2), 'E'): -40.9997934415334, ((0, 2), 'S'): -40.999834420809556, ((0, 2), 'W'): -31.67645420617531, ((0, 3), 'S'): -20.999992192948962, ((0, 3), 'W'): -50.681523379327565, ((1, 0), 'E'): -31.66673091925328, ((1, 0), 'N'): -12.66885326879473, ((1, 0), 'S'): -12.6661214455744, ((1, 1), 'E'): -40.9998103493078, ((1, 1), 'N'): -31.675785937100066, ((1, 1), 'S'): -31.66929228245872, ((1, 1), 'W'): -31.66414897696369, ((1, 2), 'E'): -21.000000000000004, ((1, 2), 'N'): -50.686172012334524, ((1, 2), 'S'): -39.999926341212834, ((1, 2), 'W'): -50.6678345317146, ((1, 3), 'N'): -21.999897582486756, ((1, 3), 'S'): -1.0, ((1, 3), 'W'): -21.999850806709116, ((2, 0), 'E'): -12.66813474888183, ((2, 0), 'N'): -12.667260215082385, ((2, 1), 'E'): -20.999777113079706, ((2, 1), 'N'): -31.66945779221507, ((2, 1), 'W'): -12.668045310032248, ((2, 2), 'E'): -19.999999999999993, ((2, 2), 'N'): -40.999794234146705, ((2, 2), 'W'): -31.667637590668363} {(0, 0): 'S', (0, 1): 'W', (0, 2): 'W', (0, 3): 'S', (1, 0): 'S', (1, 1): 'W', (1, 2): 'E', (1, 3): 'S', (2, 0): 'N', (2, 1): 'W', (2, 2): 'E'} {((0, 0), 'E'): -25.99999999999998, ((0, 0), 'S'): -23.999999999999982, ((0, 1), 'E'): -41.99999999999996, ((0, 1), 'S'): -41.99999999999996, ((0, 1), 'W'): -24.999999999999982, ((0, 2), 'E'): -40.99999999999997, ((0, 2), 'S'): -40.99999999999997, ((0, 2), 'W'): -44.99999999999999, ((0, 3), 'S'): -20.999999999999993, ((0, 3), 'W'): -60.99999999999998, ((1, 0), 'E'): -41.99999999999996, ((1, 0), 'N'): -24.999999999999982, ((1, 0), 'S'): -22.999999999999986, ((1, 1), 'E'): -40.99999999999997, ((1, 1), 'N'): -44.99999999999999, ((1, 1), 'S'): -40.99999999999997, ((1, 1), 'W'): -42.99999999999997, ((1, 2), 'E'): -20.999999999999993, ((1, 2), 'N'): -60.99999999999998, ((1, 2), 'S'): -39.999999999999986, ((1, 2), 'W'): -60.99999999999998, ((1, 3), 'N'): -21.99999999999999, ((1, 3), 'S'): -0.9999999999999998, ((1, 3), 'W'): -21.99999999999999, ((2, 0), 'E'): -21.99999999999999, ((2, 0), 'N'): -23.999999999999982, ((2, 1), 'E'): -20.999999999999993, ((2, 1), 'N'): -41.99999999999996, ((2, 1), 'W'): -22.999999999999986, ((2, 2), 'E'): -19.999999999999993, ((2, 2), 'N'): -40.99999999999997, ((2, 2), 'W'): -40.99999999999997} {(0, 0): 'S', (0, 1): 'W', (0, 2): 'S', (0, 3): 'S', (1, 0): 'S', (1, 1): 'S', (1, 2): 'E', (1, 3): 'S', (2, 0): 'E', (2, 1): 'E', (2, 2): 'E'} 3. .. literalinclude:: ../../../../src/ai/reinforcement/reinforcement.py :pyobject: qlearning_with_update :name: qlearning_with_update :linenos: :caption: src