ml-finance-python
python scripts for finance machine learning
git clone https://9o.is/git/ml-finance-python.git
02_gridworld_q_learning.ipynb
(20783B)
1 {
2 "cells": [
3 {
4 "cell_type": "markdown",
5 "metadata": {},
6 "source": [
7 "# Q-Learning in the GridWorld environment"
8 ]
9 },
10 {
11 "cell_type": "markdown",
12 "metadata": {},
13 "source": [
14 "Q-learning was an early RL breakthrough when it was developed by Chris Watkins for his [PhD thesis](http://www.cs.rhul.ac.uk/~chrisw/thesis.html) in 1989. It introduces incremental dynamic programming to control an MDP without knowing or modeling the transition and reward matrices that we used for value and policy iteration in the previous section. A convergence proof followed three years later by [Watkins and Dayan](http://www.gatsby.ucl.ac.uk/~dayan/papers/wd92.html).\n",
15 "\n",
16 "Q-learning directly optimizes the action-value function, q, to approximate q*. The learning proceeds off-policy, that is, the algorithm does not need to select actions based on the policy that's implied by the value function alone. However, convergence requires that all state-action pairs continue to be updated throughout the training process. A straightforward way to ensure this is by using an ε-greedy policy."
17 ]
18 },
19 {
20 "cell_type": "markdown",
21 "metadata": {},
22 "source": [
23 "The Q-learning algorithm keeps improving a state-action value function after random initialization for a given number of episodes. At each time step, it chooses an action based on an ε-greedy policy, and uses a learning rate, α, to update the value function, as follows:"
24 ]
25 },
26 {
27 "cell_type": "markdown",
28 "metadata": {},
29 "source": [
30 "$$Q(S_t, A_t)\\leftarrow Q(S_t, A_t) + \\alpha\\left[R_{t_1}+\\gamma \\max_a Q(S_{t+1},,a) − Q(S_t, A_t)\\right]$$"
31 ]
32 },
33 {
34 "cell_type": "markdown",
35 "metadata": {},
36 "source": [
37 "Note that the algorithm does not compute expected values because it does know the transition probabilities. It learns the Q function from the rewards produced by the ε-greedy policy and its current estimate of the value function for the next state.\n",
38 "\n",
39 "The use of the estimated value function to improve this estimate is called bootstrapping. The Q-learning algorithm is part of the TD learning algorithms. TD learning does not wait until receiving the final reward for an episode. Instead, it updates its estimates using the values of intermediate states that are closer to the final reward. In this case, the intermediate state is one time step ahead."
40 ]
41 },
42 {
43 "cell_type": "markdown",
44 "metadata": {},
45 "source": [
46 "The notebook demonstrates how to build a Q-learning agent using the 3 x 4 grid of states from the Dynamic Programmimg [example](01_gridworld_dynamic_programming.ipynb)."
47 ]
48 },
49 {
50 "cell_type": "markdown",
51 "metadata": {},
52 "source": [
53 "## Imports & Settings"
54 ]
55 },
56 {
57 "cell_type": "code",
58 "execution_count": 1,
59 "metadata": {},
60 "outputs": [],
61 "source": [
62 "%matplotlib inline\n",
63 "\n",
64 "from pathlib import Path\n",
65 "from time import process_time\n",
66 "import numpy as np\n",
67 "import pandas as pd\n",
68 "from mdptoolbox import mdp\n",
69 "from itertools import product\n",
70 "import gym"
71 ]
72 },
73 {
74 "cell_type": "markdown",
75 "metadata": {},
76 "source": [
77 "## Set up Gridworld"
78 ]
79 },
80 {
81 "cell_type": "markdown",
82 "metadata": {},
83 "source": [
84 "We first create our small gridworld as in the Dynamic Programmimg [example](01_gridworld_dynamic_programming.ipynb)."
85 ]
86 },
87 {
88 "cell_type": "markdown",
89 "metadata": {},
90 "source": [
91 "### States, Actions and Rewards"
92 ]
93 },
94 {
95 "cell_type": "code",
96 "execution_count": 2,
97 "metadata": {},
98 "outputs": [],
99 "source": [
100 "grid_size = (3, 4)\n",
101 "blocked_cell = (1, 1)\n",
102 "baseline_reward = -0.02\n",
103 "absorbing_cells = {(0, 3): 1, (1, 3): -1}"
104 ]
105 },
106 {
107 "cell_type": "code",
108 "execution_count": 3,
109 "metadata": {},
110 "outputs": [],
111 "source": [
112 "actions = ['L', 'U', 'R', 'D']\n",
113 "num_actions = len(actions)\n",
114 "probs = [.1, .8, .1, 0]"
115 ]
116 },
117 {
118 "cell_type": "code",
119 "execution_count": 4,
120 "metadata": {},
121 "outputs": [],
122 "source": [
123 "to_1d = lambda x: np.ravel_multi_index(x, grid_size)\n",
124 "to_2d = lambda x: np.unravel_index(x, grid_size)"
125 ]
126 },
127 {
128 "cell_type": "code",
129 "execution_count": 5,
130 "metadata": {},
131 "outputs": [],
132 "source": [
133 "num_states = np.product(grid_size)\n",
134 "cells = list(np.ndindex(grid_size))\n",
135 "states = list(range(len(cells)))"
136 ]
137 },
138 {
139 "cell_type": "code",
140 "execution_count": 6,
141 "metadata": {},
142 "outputs": [],
143 "source": [
144 "cell_state = dict(zip(cells, states))\n",
145 "state_cell= dict(zip(states, cells))"
146 ]
147 },
148 {
149 "cell_type": "code",
150 "execution_count": 7,
151 "metadata": {},
152 "outputs": [],
153 "source": [
154 "absorbing_states = {to_1d(s):r for s, r in absorbing_cells.items()}\n",
155 "blocked_state = to_1d(blocked_cell)"
156 ]
157 },
158 {
159 "cell_type": "code",
160 "execution_count": 8,
161 "metadata": {},
162 "outputs": [],
163 "source": [
164 "state_rewards = np.full(num_states, baseline_reward)\n",
165 "state_rewards[blocked_state] = 0\n",
166 "for state, reward in absorbing_states.items():\n",
167 " state_rewards[state] = reward"
168 ]
169 },
170 {
171 "cell_type": "code",
172 "execution_count": 9,
173 "metadata": {},
174 "outputs": [],
175 "source": [
176 "action_outcomes = {}\n",
177 "for i, action in enumerate(actions):\n",
178 " probs_ = dict(zip([actions[j % 4] for j in range(i, num_actions + i)], probs))\n",
179 " action_outcomes[actions[(i + 1) % 4]] = probs_"
180 ]
181 },
182 {
183 "cell_type": "code",
184 "execution_count": 10,
185 "metadata": {},
186 "outputs": [
187 {
188 "data": {
189 "text/plain": [
190 "{'U': {'L': 0.1, 'U': 0.8, 'R': 0.1, 'D': 0},\n",
191 " 'R': {'U': 0.1, 'R': 0.8, 'D': 0.1, 'L': 0},\n",
192 " 'D': {'R': 0.1, 'D': 0.8, 'L': 0.1, 'U': 0},\n",
193 " 'L': {'D': 0.1, 'L': 0.8, 'U': 0.1, 'R': 0}}"
194 ]
195 },
196 "execution_count": 10,
197 "metadata": {},
198 "output_type": "execute_result"
199 }
200 ],
201 "source": [
202 "action_outcomes"
203 ]
204 },
205 {
206 "cell_type": "markdown",
207 "metadata": {},
208 "source": [
209 "### Transition Matrix"
210 ]
211 },
212 {
213 "cell_type": "code",
214 "execution_count": 11,
215 "metadata": {},
216 "outputs": [],
217 "source": [
218 "def get_new_cell(state, move):\n",
219 " cell = to_2d(state)\n",
220 " if actions[move] == 'U':\n",
221 " return cell[0] - 1, cell[1]\n",
222 " elif actions[move] == 'D':\n",
223 " return cell[0] + 1, cell[1]\n",
224 " elif actions[move] == 'R':\n",
225 " return cell[0], cell[1] + 1\n",
226 " elif actions[move] == 'L':\n",
227 " return cell[0], cell[1] - 1"
228 ]
229 },
230 {
231 "cell_type": "code",
232 "execution_count": 12,
233 "metadata": {},
234 "outputs": [
235 {
236 "data": {
237 "text/plain": [
238 "array([-0.02, -0.02, -0.02, 1. , -0.02, 0. , -0.02, -1. , -0.02,\n",
239 " -0.02, -0.02, -0.02])"
240 ]
241 },
242 "execution_count": 12,
243 "metadata": {},
244 "output_type": "execute_result"
245 }
246 ],
247 "source": [
248 "state_rewards"
249 ]
250 },
251 {
252 "cell_type": "code",
253 "execution_count": 13,
254 "metadata": {},
255 "outputs": [],
256 "source": [
257 "def update_transitions_and_rewards(state, action, outcome):\n",
258 " if state in absorbing_states.keys() or state == blocked_state:\n",
259 " transitions[action, state, state] = 1\n",
260 " else:\n",
261 " new_cell = get_new_cell(state, outcome)\n",
262 " p = action_outcomes[actions[action]][actions[outcome]]\n",
263 " if new_cell not in cells or new_cell == blocked_cell:\n",
264 " transitions[action, state, state] += p\n",
265 " rewards[action, state, state] = baseline_reward\n",
266 " else:\n",
267 " new_state= to_1d(new_cell)\n",
268 " transitions[action, state, new_state] = p\n",
269 " rewards[action, state, new_state] = state_rewards[new_state]"
270 ]
271 },
272 {
273 "cell_type": "code",
274 "execution_count": 14,
275 "metadata": {},
276 "outputs": [],
277 "source": [
278 "rewards = np.zeros(shape=(num_actions, num_states, num_states))\n",
279 "transitions = np.zeros((num_actions, num_states, num_states))\n",
280 "actions_ = list(range(num_actions))\n",
281 "for action, outcome, state in product(actions_, actions_, states):\n",
282 " update_transitions_and_rewards(state, action, outcome)"
283 ]
284 },
285 {
286 "cell_type": "code",
287 "execution_count": 15,
288 "metadata": {},
289 "outputs": [
290 {
291 "data": {
292 "text/plain": [
293 "((4, 12, 12), (4, 12, 12))"
294 ]
295 },
296 "execution_count": 15,
297 "metadata": {},
298 "output_type": "execute_result"
299 }
300 ],
301 "source": [
302 "rewards.shape, transitions.shape"
303 ]
304 },
305 {
306 "cell_type": "markdown",
307 "metadata": {},
308 "source": [
309 "## Q-Learning"
310 ]
311 },
312 {
313 "cell_type": "markdown",
314 "metadata": {},
315 "source": [
316 " We will train the agent for 2,500 episodes, use a learning rate of α= 0.1, and an ε=0.05 for the ε-greedy policy "
317 ]
318 },
319 {
320 "cell_type": "code",
321 "execution_count": 20,
322 "metadata": {},
323 "outputs": [],
324 "source": [
325 "max_episodes = 2500\n",
326 "alpha = .1\n",
327 "epsilon = .05\n",
328 "gamma = .99"
329 ]
330 },
331 {
332 "cell_type": "markdown",
333 "metadata": {},
334 "source": [
335 "Then, we will randomly initialize the state-action value function as a NumPy array with the dimensions of [number of states and number of actions]:"
336 ]
337 },
338 {
339 "cell_type": "code",
340 "execution_count": 21,
341 "metadata": {},
342 "outputs": [],
343 "source": [
344 "Q = np.random.rand(num_states, num_actions)\n",
345 "skip_states = list(absorbing_states.keys())+[blocked_state]\n",
346 "Q[skip_states] = 0"
347 ]
348 },
349 {
350 "cell_type": "markdown",
351 "metadata": {},
352 "source": [
353 "The algorithm generates 2,500 episodes that start at a random location and proceed according to the ε-greedy policy until termination, updating the value function according to the Q-learning rule:"
354 ]
355 },
356 {
357 "cell_type": "code",
358 "execution_count": 19,
359 "metadata": {},
360 "outputs": [
361 {
362 "data": {
363 "text/plain": [
364 "0.5974638589999994"
365 ]
366 },
367 "execution_count": 19,
368 "metadata": {},
369 "output_type": "execute_result"
370 }
371 ],
372 "source": [
373 "start = process_time()\n",
374 "for episode in range(max_episodes):\n",
375 " state = np.random.choice([s for s in states if s not in skip_states])\n",
376 " while not state in absorbing_states.keys():\n",
377 " if np.random.rand() < epsilon:\n",
378 " action = np.random.choice(num_actions)\n",
379 " else:\n",
380 " action = np.argmax(Q[state])\n",
381 " next_state = np.random.choice(states, p=transitions[action, state])\n",
382 " reward = rewards[action, state, next_state]\n",
383 " Q[state, action] += alpha * (reward + gamma * np.max(Q[next_state])-Q[state, action])\n",
384 " state = next_state\n",
385 "process_time() - start"
386 ]
387 },
388 {
389 "cell_type": "markdown",
390 "metadata": {},
391 "source": [
392 "The episodes take 0.6 seconds and converge to a value function fairly close to the result of the value iteration example from the previous section."
393 ]
394 },
395 {
396 "cell_type": "code",
397 "execution_count": 20,
398 "metadata": {},
399 "outputs": [
400 {
401 "data": {
402 "text/html": [
403 "<div>\n",
404 "<style scoped>\n",
405 " .dataframe tbody tr th:only-of-type {\n",
406 " vertical-align: middle;\n",
407 " }\n",
408 "\n",
409 " .dataframe tbody tr th {\n",
410 " vertical-align: top;\n",
411 " }\n",
412 "\n",
413 " .dataframe thead th {\n",
414 " text-align: right;\n",
415 " }\n",
416 "</style>\n",
417 "<table border=\"1\" class=\"dataframe\">\n",
418 " <thead>\n",
419 " <tr style=\"text-align: right;\">\n",
420 " <th></th>\n",
421 " <th>0</th>\n",
422 " <th>1</th>\n",
423 " <th>2</th>\n",
424 " <th>3</th>\n",
425 " </tr>\n",
426 " </thead>\n",
427 " <tbody>\n",
428 " <tr>\n",
429 " <th>0</th>\n",
430 " <td>R</td>\n",
431 " <td>R</td>\n",
432 " <td>R</td>\n",
433 " <td>L</td>\n",
434 " </tr>\n",
435 " <tr>\n",
436 " <th>1</th>\n",
437 " <td>U</td>\n",
438 " <td>L</td>\n",
439 " <td>L</td>\n",
440 " <td>L</td>\n",
441 " </tr>\n",
442 " <tr>\n",
443 " <th>2</th>\n",
444 " <td>U</td>\n",
445 " <td>L</td>\n",
446 " <td>L</td>\n",
447 " <td>D</td>\n",
448 " </tr>\n",
449 " </tbody>\n",
450 "</table>\n",
451 "</div>"
452 ],
453 "text/plain": [
454 " 0 1 2 3\n",
455 "0 R R R L\n",
456 "1 U L L L\n",
457 "2 U L L D"
458 ]
459 },
460 "execution_count": 20,
461 "metadata": {},
462 "output_type": "execute_result"
463 }
464 ],
465 "source": [
466 "pd.DataFrame(np.argmax(Q, 1).reshape(grid_size)).replace(dict(enumerate(actions)))"
467 ]
468 },
469 {
470 "cell_type": "code",
471 "execution_count": 21,
472 "metadata": {},
473 "outputs": [
474 {
475 "data": {
476 "text/html": [
477 "<div>\n",
478 "<style scoped>\n",
479 " .dataframe tbody tr th:only-of-type {\n",
480 " vertical-align: middle;\n",
481 " }\n",
482 "\n",
483 " .dataframe tbody tr th {\n",
484 " vertical-align: top;\n",
485 " }\n",
486 "\n",
487 " .dataframe thead th {\n",
488 " text-align: right;\n",
489 " }\n",
490 "</style>\n",
491 "<table border=\"1\" class=\"dataframe\">\n",
492 " <thead>\n",
493 " <tr style=\"text-align: right;\">\n",
494 " <th></th>\n",
495 " <th>0</th>\n",
496 " <th>1</th>\n",
497 " <th>2</th>\n",
498 " <th>3</th>\n",
499 " </tr>\n",
500 " </thead>\n",
501 " <tbody>\n",
502 " <tr>\n",
503 " <th>0</th>\n",
504 " <td>0.858871</td>\n",
505 " <td>0.922653</td>\n",
506 " <td>0.986901</td>\n",
507 " <td>0.000000</td>\n",
508 " </tr>\n",
509 " <tr>\n",
510 " <th>1</th>\n",
511 " <td>0.834113</td>\n",
512 " <td>0.000000</td>\n",
513 " <td>0.717010</td>\n",
514 " <td>0.000000</td>\n",
515 " </tr>\n",
516 " <tr>\n",
517 " <th>2</th>\n",
518 " <td>0.800174</td>\n",
519 " <td>0.763851</td>\n",
520 " <td>0.730269</td>\n",
521 " <td>0.571109</td>\n",
522 " </tr>\n",
523 " </tbody>\n",
524 "</table>\n",
525 "</div>"
526 ],
527 "text/plain": [
528 " 0 1 2 3\n",
529 "0 0.858871 0.922653 0.986901 0.000000\n",
530 "1 0.834113 0.000000 0.717010 0.000000\n",
531 "2 0.800174 0.763851 0.730269 0.571109"
532 ]
533 },
534 "execution_count": 21,
535 "metadata": {},
536 "output_type": "execute_result"
537 }
538 ],
539 "source": [
540 "pd.DataFrame(np.max(Q, 1).reshape(grid_size))"
541 ]
542 },
543 {
544 "cell_type": "markdown",
545 "metadata": {},
546 "source": [
547 "## PyMDPToolbox"
548 ]
549 },
550 {
551 "cell_type": "markdown",
552 "metadata": {},
553 "source": [
554 "### Q Learning"
555 ]
556 },
557 {
558 "cell_type": "code",
559 "execution_count": 17,
560 "metadata": {},
561 "outputs": [
562 {
563 "data": {
564 "text/plain": [
565 "'Time: 10.5962'"
566 ]
567 },
568 "execution_count": 17,
569 "metadata": {},
570 "output_type": "execute_result"
571 }
572 ],
573 "source": [
574 "start = process_time()\n",
575 "ql = mdp.QLearning(transitions=transitions,\n",
576 " reward=rewards,\n",
577 " discount=gamma,\n",
578 " n_iter=int(1e6))\n",
579 "\n",
580 "ql.run()\n",
581 "f'Time: {process_time()-start:.4f}'"
582 ]
583 },
584 {
585 "cell_type": "code",
586 "execution_count": 18,
587 "metadata": {},
588 "outputs": [
589 {
590 "data": {
591 "text/html": [
592 "<div>\n",
593 "<style scoped>\n",
594 " .dataframe tbody tr th:only-of-type {\n",
595 " vertical-align: middle;\n",
596 " }\n",
597 "\n",
598 " .dataframe tbody tr th {\n",
599 " vertical-align: top;\n",
600 " }\n",
601 "\n",
602 " .dataframe thead th {\n",
603 " text-align: right;\n",
604 " }\n",
605 "</style>\n",
606 "<table border=\"1\" class=\"dataframe\">\n",
607 " <thead>\n",
608 " <tr style=\"text-align: right;\">\n",
609 " <th></th>\n",
610 " <th>0</th>\n",
611 " <th>1</th>\n",
612 " <th>2</th>\n",
613 " <th>3</th>\n",
614 " </tr>\n",
615 " </thead>\n",
616 " <tbody>\n",
617 " <tr>\n",
618 " <th>0</th>\n",
619 " <td>R</td>\n",
620 " <td>R</td>\n",
621 " <td>R</td>\n",
622 " <td>L</td>\n",
623 " </tr>\n",
624 " <tr>\n",
625 " <th>1</th>\n",
626 " <td>U</td>\n",
627 " <td>L</td>\n",
628 " <td>U</td>\n",
629 " <td>L</td>\n",
630 " </tr>\n",
631 " <tr>\n",
632 " <th>2</th>\n",
633 " <td>R</td>\n",
634 " <td>R</td>\n",
635 " <td>U</td>\n",
636 " <td>L</td>\n",
637 " </tr>\n",
638 " </tbody>\n",
639 "</table>\n",
640 "</div>"
641 ],
642 "text/plain": [
643 " 0 1 2 3\n",
644 "0 R R R L\n",
645 "1 U L U L\n",
646 "2 R R U L"
647 ]
648 },
649 "execution_count": 18,
650 "metadata": {},
651 "output_type": "execute_result"
652 }
653 ],
654 "source": [
655 "policy = np.asarray([actions[i] for i in ql.policy])\n",
656 "pd.DataFrame(policy.reshape(grid_size))"
657 ]
658 },
659 {
660 "cell_type": "code",
661 "execution_count": 19,
662 "metadata": {},
663 "outputs": [
664 {
665 "data": {
666 "text/html": [
667 "<div>\n",
668 "<style scoped>\n",
669 " .dataframe tbody tr th:only-of-type {\n",
670 " vertical-align: middle;\n",
671 " }\n",
672 "\n",
673 " .dataframe tbody tr th {\n",
674 " vertical-align: top;\n",
675 " }\n",
676 "\n",
677 " .dataframe thead th {\n",
678 " text-align: right;\n",
679 " }\n",
680 "</style>\n",
681 "<table border=\"1\" class=\"dataframe\">\n",
682 " <thead>\n",
683 " <tr style=\"text-align: right;\">\n",
684 " <th></th>\n",
685 " <th>0</th>\n",
686 " <th>1</th>\n",
687 " <th>2</th>\n",
688 " <th>3</th>\n",
689 " </tr>\n",
690 " </thead>\n",
691 " <tbody>\n",
692 " <tr>\n",
693 " <th>0</th>\n",
694 " <td>0.768113</td>\n",
695 " <td>0.918608</td>\n",
696 " <td>0.967810</td>\n",
697 " <td>0.000000</td>\n",
698 " </tr>\n",
699 " <tr>\n",
700 " <th>1</th>\n",
701 " <td>0.499035</td>\n",
702 " <td>0.000000</td>\n",
703 " <td>0.737283</td>\n",
704 " <td>0.000000</td>\n",
705 " </tr>\n",
706 " <tr>\n",
707 " <th>2</th>\n",
708 " <td>0.226344</td>\n",
709 " <td>0.499552</td>\n",
710 " <td>0.616478</td>\n",
711 " <td>0.269537</td>\n",
712 " </tr>\n",
713 " </tbody>\n",
714 "</table>\n",
715 "</div>"
716 ],
717 "text/plain": [
718 " 0 1 2 3\n",
719 "0 0.768113 0.918608 0.967810 0.000000\n",
720 "1 0.499035 0.000000 0.737283 0.000000\n",
721 "2 0.226344 0.499552 0.616478 0.269537"
722 ]
723 },
724 "execution_count": 19,
725 "metadata": {},
726 "output_type": "execute_result"
727 }
728 ],
729 "source": [
730 "value = np.asarray(ql.V).reshape(grid_size)\n",
731 "pd.DataFrame(value)"
732 ]
733 },
734 {
735 "cell_type": "code",
736 "execution_count": null,
737 "metadata": {},
738 "outputs": [],
739 "source": []
740 }
741 ],
742 "metadata": {
743 "kernelspec": {
744 "display_name": "Python 3",
745 "language": "python",
746 "name": "python3"
747 },
748 "language_info": {
749 "codemirror_mode": {
750 "name": "ipython",
751 "version": 3
752 },
753 "file_extension": ".py",
754 "mimetype": "text/x-python",
755 "name": "python",
756 "nbconvert_exporter": "python",
757 "pygments_lexer": "ipython3",
758 "version": "3.6.8"
759 },
760 "toc": {
761 "base_numbering": 1,
762 "nav_menu": {},
763 "number_sections": true,
764 "sideBar": true,
765 "skip_h1_title": true,
766 "title_cell": "Table of Contents",
767 "title_sidebar": "Contents",
768 "toc_cell": false,
769 "toc_position": {},
770 "toc_section_display": true,
771 "toc_window_display": true
772 }
773 },
774 "nbformat": 4,
775 "nbformat_minor": 2
776 }