{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "![Cliffworld](cliff_map.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I'm [David](https://twitter.com/DavidSanwald) a Berlin based student and here I'm trying so build something to make the first steps in RL as easy going as possible.\n", "This is still WIP, I'm thankful for every input and critique. I want to further improve the understandability of the text and extend the pointers to neuroscience. I wrote the code to explain basic RL, not programming. So I decided to go without inheritance, base classes and hardcoded some stuff because it's clearer even though one shouldn't code this way outside a notebook.\n", "\n", "If you're reading this notebook on my blog I strongly recommend trying the interactive version on mybinder.org, which is using a docker container to make it possible to share an interactive notebook. I still can't believe how easy this is and even better it's free to use (:\n", "\n", "Interactive:\n", "http://mybinder.org/repo/davidsanwald/ai-notebook\n", "\n", "Download Notebook:\n", "https://github.com/DavidSanwald/ai-notebook.git" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "#: imports, nothing to see here\n", "import random\n", "from collections import defaultdict, namedtuple\n", "from itertools import product, starmap\n", "\n", "import matplotlib\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import seaborn as sns\n", "from IPython.display import Image, YouTubeVideo\n", "from scipy import stats\n", "%matplotlib inline\n", "sns.set()\n", "states_colors = matplotlib.colors.ListedColormap(\n", " ['#9A9A9A', '#D886BA', '#4D314A', '#6E9183'])\n", "cmap_default = 'Blues'\n", "cpal_default = sns.color_palette((\"Blues_d\"))\n", "\n", "sns.set_style(\"white\")\n", "sns.set_context(\"poster\")\n", "random.seed(1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# A Theory of Everything in 4x12 Squares\n", "## Discovering Reinforcement Learning Without a Math Degree" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAUDBAgICAgICQgICAkICAkJCQgICQkJCQkJCQkJCQgJ\nCQkJChALCQkaCQkJGCEYGiARHx8fCQsgICAgIBAgHyABBQUFCAcIDwkJDxQNDw8UFBUYFxQVFBQV\nFRUVFBQUFBQVFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFBQUFP/AABEIAWgB4AMBIgACEQED\nEQH/xAAdAAACAgMBAQEAAAAAAAAAAAAAAQIDBAUGCAcJ/8QAYxAAAQMBBQIIBwgLCgsGBwAAAQAC\nAxEEBRIhMUFRBhMUImFxgZEHCKGlseTwGDJCUmakweUVI1NiZXKCotHh4hckM0NFY5Kj4/EWNEZU\nVYOEk7LCxCVEc4WVtDVWdZSzw8X/xAAaAQEAAwEBAQAAAAAAAAAAAAAAAQIDBAUG/8QALhEAAgIC\nAgEDBAEEAQUAAAAAAAECEQMSBCExE0FRBRQiMmFxgZGxoSMzQsHR/9oADAMBAAIRAxEAPwDxkhCE\nAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQAh\nCEAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQAhCEAIQhACEIQHqw+J78ovNfr6PcffKLzX6+vVZ\nG+vcmOz6VB1enE8pjxPflF5r9fTPiefKLzX6+vVgRTrQenE8pe49+UXmv19A8T35Rea/X16uogDt\nQenE8o+49+UXmv19HuPflF5r9fXq6iD1IPTieUfce/KI/wDpXr6Pce/KI/8ApXr69XgpeQIPTieU\nvcefKLzX6+geJ58ovNfr69WV6E+9B6cTyl7jwf8AzF5r+sEh4nvyi81+vr1akSg9OJ5T9x78ovNf\nr6Pce/KLzX6+vVZKRQenE8t2bxNsZw/4R0/8qr//AEFku8S2n+Uvmn6xXqe6v4TsK2Ui6sOOMl2e\nfypuEqieQ3eJfT/KTzV9YKp3ia0/yj81fWC9dSlUSldCwQ+DjfIn8nkaXxPMP+UVf/K/X1qLw8Vc\nQ/y9ip+Dqf8AWr2FbDkVxvCF3vlouNjrwUXJyXVnlC1+L1xf8r1/2Gn/AFawT4Cfwp8z9ZXoG9Dm\nVp3hcOSMU+j2cMbXZ8Vb4Cvwr8z9ZT/cJ/CnzP1lfaGBTa3esqN/TifE/wBwr8KfM/WU/wBwn8Kf\nM/WV9qwoolD0onxb9wf8K/M/WUfuEfhX5n6yvtjG1USKFTSI9OJ8Sd4DKfyp8z9ZWZYPF+40kfZb\nDQVryKv/AFQX1yQZrOul9HnqWmCMXKpeCuXGlFteT487xdKfyz8x9bVMni9gfyv8x9aX3p71izOP\nQuqeHGvCOSCl7nwk+AH8LfMvWlF3gDp/K3zL1pfcXKqQrmnCKOmMEfEm+AWv8q/MvWlkWfxenyEB\nt6FxOjRYak9QFqX2ePYvo3gmga4Wt7Q0ztjAixdIOY7aK+LFF+SmeoRtI8sWvxcJoqcZeL2V0xWA\nivfalB3i7PFK3o4YtK2EivV++s17IZdlvtTIIbYIcJlxu+6Bjc+oD9K2163XHaJLHI1rCIZ6c2lM\nIB17QFr6ONef9nD9y17X/k8QyeLs9vvr0c38awEem1KDvF8I1vYj/YdfnS9w3lNZZHus0hime6Ro\nbC0DE0DM17KrX8OLtjdYpi2OMCOhFW4XMpu3qjx46tFlyJWk4+TxgPF5P+l/mPrSXuej/pf5j60v\nZnAG7LPyKN7oWmSUmpkbXEK5AbhRSt/BazvgmGGOzvdPzXu0aKjIKzwY0TLkpSrU8Ze55/C/zH1p\nP3PH4X+Y+tL2pPwVsYa8cU0lsDRi++Ned1rHv+47vssJe6ztcGhpJxUcd9BVHhxr3IXKt/qeMXeL\n1T+V/mXrSQ8Xz8L/ADH1pev+Ed33VBZGWg2dwNoZ9rAJqCW1G3JfNAuecIp0jrwNZFdUfCz4vf4X\n+Y+tKJ8X38L/ADL1pfdnqGFUaR0rFE+FHxf/AMLfMvWkv3Afwt8y9aX3RzUsKzLejE+JxeL1iH/x\nen+w+tJT+L3hA/7XrnSnIfWl94swoG9IKjbRot3BUZKCs+GWfxd8Yr9mKf7DX/q12V3eJ66WNj3c\nIMBcAcP2MxUrpny8L6ddAGKIHa8V6q5r61dtsBFBoMl24+NCWO67PP5eR45VHo8wDxM3FwaOEWbj\n/ov19O0+Jo1okw8JmudGKlhuvD2V5eV6wscxMgw5kZ9gWPObHM91MTpJDQtFcs8yqPjxvwc8c837\n/wCjyNN4oM7bNyn7NimuD7HmtDt/xxZMnia2kR4xfrCcOLByA16v8bXry22mAY4X1Y0xhrS4Uaeg\ndK11+3wYSDHA9wcxrDNTJoPRqVT0o+0f9lvUn8/6JDtQnTrTC889siAE6KXYjuQEcKeHtTQQgEPb\nJCkfIigQCRQ7KJlvT5Uj1+RALNIpgHemgIVSUyfaiiSEBApd6fN+Ml0/SgMu6zz+xbF61Nge0SAk\ngDTMgdWuSz5LVHU1kYKZGrgKHcc+kd67uMrieTznUglKplKm94NCCDXMEZg9R2qmQrsSPPbMK2nI\nrieEL9V2VvORXD38dVd/qRjVzRx14nMrVyBbK8NT1rXvXlZH2fR4l0RYFIhOMKdFRG1FZCRarW66\nJFGCDCm5TAFOlIsUApeMwhhwuBTAzUpmZInXZNGe2Wqg70rEs8tMlc566fVtGHp0yTyqHlNyCFnK\nVmijQNWbd14TQOxxPdG4bWmiw6KTQoUqJqzcycIrY4lxtMpcRhJxHQ6joTsN/wBrhbhjne1uLFSv\nwt+a0wUgVKkRovg2MV6zCbjxIeNxYse2q2V68Lbbao+Klkq3aAAK9dFzoUqpsRon7HUXNw0tlliE\nLCwsHvcQqW9SjbeF1qnjZFIWlrZOMrTMurUV6KrmqqYKb9kPDH4R2p8INpINWRnFh2HRq0/CLhBL\nbZeNfzRQNDAcgtHVMKXIRwxTtI6HhJwkfbILPAWNYIABltNKV6FoAEBSCq3fZaMFFUhEKJCsSoqs\nuVkIY2ppvUyFfC3AMZ1+CPpURVsN9Fjm88AfBFO1Y9tHOHUsyAUbnqTUrHtg53YtZ+DGHklZ34DG\nV1F33m4bSuVmbQNWZZJqgLp42fTpmXIwqas+m8Cb0Y6SQPeGnBRpcdq2NzWVsE0o45j3ysJjOWRr\n+tfKmzdJUm2lwoQ4gjcdFfJkTba9zkXE/sfWLJEWMjZbHse909WZjraoSstgklL3xCBz2Bg24ajR\nfKLVb5XkF0j3EaVcajqTtF7Wl4AdNIQ3Srjl5VzvLXZouFfufVgUZJBScuE7yNOmilTpQ0J1QEe5\nNPsQANyASM0zTcEU6EBGiM1Lv9KDnt7x+hQCKRUiOpLsSwLtUHHKuWW07FTeVrjs8Uk8rhHHExz5\nHn4LWjE49wXlDwp+GS0XjaDHATFYoz9ri+6kfxkueZ3DZTSqEqNnozhvw1sd12YzyPa+lWsDHNIL\n/ikg1GVe4r4Jwr8Pt4PL22dkMIErS0sGI8W0msbsQzJyzG4r4ze98y2h3PdXTmgANyG5tBWi1zHV\nOelSezYpstR9KvDwu3rLM6VlpkjrRuBtAMOdcLcw00PkC114+Ei9p3OEtrlc3GXiOowhz8y4VrQ1\n0PQKaLh6Zgjt7f1K5jSTkCXOoKAbVrHkSiunRlPjxm7as7aDwl3yxgjhtk0QoKiDm7NXZGrt561s\nro8M/CGxyYn299oaKAx2ljHMI0oSG4h2UWr4PXKTGHFoLqjZoOvr9C2VouLlAJDQA1tKnIuI1cah\nZv6i77ZvH6QnHqK/wfUeD3jDWG0BrLbZpbK40BmhImhrTMublI0VroHbF1D75s9tj46zTMmjPwmH\nToI1aeteT7+uiSzmlMjt39KyeBvCm0XdI17HuLa0kixENkb8Ifemn0Lrhzdl32edP6coStdM9D23\nUrBeFi3Fwhs14RCSF+ej4zk9jsqhzVmOWM2dsI0htapFG5TIVLNCDW9nSm5vanhqgApZFDABy2qJ\nU2pEZFGyKMeMZq4hUEFMAqEyzQPiUWkqYBQQotgA5GIIwoAU2KRLEpAqICA1NhRKqkCFABSASxRO\nqYKhRMBNhRYFJVhSCbCiwKQVYCkO1TsKLAphVBSamwomiiQJUgKqNiKBtO1XwxknE7sRCxo1IJWQ\n1w3hawopJjCxLUOes3EDu71i2kc86a7FM2Uguy10dWrGi5pWxjCqns9cwkuuy0X7MQeglUAEKYcn\nqE6DqhAIUmuG3RUstR9jCKIBUgsrKCAQE0KAJOiYRVCBUCEAJ0QEUJ0Qe1CSA2pEqbiqbRK1jXPd\nk1oJJ3ACqA+AeN5w1MMMNywvo60tE9rIOYhaftMZ63tJP4jd68xPca5ldB4SL+deV5222ucTx0rj\nGN0daRNz2cW1q5x+em/6BqobNqohsJ09s1ONhoNfjHtOQGftmk+rgAMgdOr+9bFzaAjLLX8kYaZ/\nfekqjZKiVhrWtGXOfpU7NNyy7mIMjRQmvTmRTvC18wLi34OXoz07FtOD0J44E76ZdeapJ9GsF+SP\ns3Bi7WCCmtRQU0bvp06LZcgZmMO4Z6GmXoClwVj+0gbG5abejetvFZCXV0Gz0+3YvnsmR7M+pxQW\nqPn/AAyuIStwtyc406BnUnoyXx2+LA+CXB8VxHfkvSF9XdI0Oe1r5HEYRQZNB6Nv61wtq4DOlEto\nlqXEVAAyaa5Nrv1qu/h8nXps87ncPfuK7PmvB++JLHaGTRk1xc4Z4XNOrT2L7xcF6xWyJsse0CrT\nq0kbdhXyqTgXIZC1oOFgJJ0FABUk9a7vwYXa+CElwwcZmG9DSQD3kr2Y5FLweHLFKD7OtwlABVoC\nYCuUKgCm0lWkbkwEBUa10ScTuV7tijIaKGqIKI2qQCsaCc1Zxa0jEWU0QFdxafFo4iymiMKtwIDE\noFeAIDArcCA1NSSAYNybY+hWgKTG6KKIsx52AOoFY2EJPFX9qzGsUxiG6MUQhTbZx0rKawKWBW0o\npsYrbODtUuTLJaxTDU0RGzMMWcpiArLwqTWqNETszD4gqQgKzQ1SDU0Q3Ne6EjVSbESKrLtY5o60\n425BNeydujFELkxC7cs1rVMBToRuYTcY3oxvWbhQWKXEjYwXEnVLCs4xpBizcC6kYeFNoWa2MKQj\nG5FAjc+rBCdUA+xWRUMkwAioKaAXagdZTqghCBU6UURROvUgEkQpZoqhJGi4fw6XpyTg/eUhdhc+\nDiGbC587hEGjscexpXbuovifjc25rbrslnyxTWzHQ/FhjcCdfjSsQtBdnk+RlaH2yr9KhDZnyAhr\nS5xya1oLnGppkBmT+hWA6dbge2lB6F9e8C9xhlkZaxTlNttDoI5NXRwxl/GFvxXFzXZ9A3Ll5Gb0\n47HocTjPPPVdHyuS75YXxwyQyxvc8ACSN7DhyrTEBUKVphaxsjC3nOcxwrsFBln0u8hXpDhHcMdo\n/ero8cNDjke9zntfTJ8bjzmvr1bV8n8I/g75JFymy8a+NgBnDnF76En7Y0nOgoK9fQuXFzIzdPpn\nZn+nyxq49o4BzKHTY7sAqF1/g+unj3igxc6gy3urn2D0rkRYwSwDPE2ugrXFhp7dC+s8GvBfEYWS\nutNpikcK/anOYNMvekHRacnLGMabqzDi4ZSlaV0fRrHZhExrQKACmevarTNhzcQ0byadeq4mbgLO\nyvF3latMg60WkU6RhmpXvWgvy6LwgZIXW2dzo2FzS+eSRowjFm1xrSgPevJjijN/t/we0804r9f+\nTvLXwwihfQRSysHvpQwhg/KIoQun4N2+x2+M8U5u/DlUHpFVxHg+tttfYo32mZjnPwlsUkWKkbgQ\nHOla+pNRphdqFjXhcbW2oTxtdZHcYA2WFx4h8gAdhZKAG46HQ0Oi7lw9fa6+DlfIbV+LPoc3BtvP\nGHJ2RpSlK1NAdtfoWsvqztjmAa3C3i2UGlMILKfmhdRdd6tdZWPlObaNJOriBuG3Jcda+EMFutUj\nI2uaYG051OcK5kUOlT5Qt+Inv/Byc1pw78iKYCkAgBep7HkiqmAmAiiJkA7eoSaKwBQkChuwidmZ\nkFv7nuF87cWgrQZVJPQFg3HYzNJHENXkDq3nuX2DgxYWw5AVDGUG8dK9XBjiobS7PN5mdxesXTPl\nttuKSE4SD2ggrBmsxGzYvtV6lrXWeR7Wvbjw1c3nc7ILCtF2WNk0dnMbXvne6V1RowZ06q/Soag/\najlx8rIvPZ8bMKi5lF9kHBiyG0ySGJvFlgDWU5uLOp9CVn4L2IsjBs7TjBq4nMdSzcI/Jv8Affwf\nHA0KBovpwuyxXbC+0SQmYvmcyNrhXC0Ega9XoWbbrksjY7TaGwD7ZZg8MI96SDoNh07lnLGq8mn3\nv8df1PkzWiicLOcOtSMbmuo5padxFFbAOd3+hYJHbfRiBtX9qzmsWLZ/f966zgnc4nL5H+8jplvd\nsHUujj49jLkZFjjbNFxDhqDoohq+gS2AOaTQLn7wsTRsXRk46S6ODFztnTRoAmFkyQtVBYuKfR6M\nexBToqu1IvO9ZPIaKBeFNoWPE81WWArwdlZKiu3R0YzpqpNbl2JW01LBuCyIYyaADXIfQtYR2kVb\nqPZBoUqLpWcHG4BiccdKmmg3BYFpugs+F3roeCSOVcqDdWakNRRZLrM4KtzCNixlGjoUkyotRhQ4\n0SLwsHJI0SJUQAkJBsVoapTshqj6hVFelGQ0zO/20CYC5gCABuCaSARCKKVEEIBIxJ16UigF2eRF\neruTBSohIne2S82+OBI42m64z73k9oIOzEZYcVOnC0L0kQvgnjg3eX2e7LQ0E8TNMx7gMg2VrKAn\npcz0qsvBfF+x5inDa0ppWvWcx20C+xeA+8Q+xMjrR9htErATphtDXPjf/vHkdy+NWsUxk7aU7KV8\nnpXeeAu82MntFncf4UYgCcnbHNp3Li5kbxf0PX+mZNM6Xz0fYXy+/fM+XmEFsNSBjaS73rffHIa7\n1thHjZhIBqMxqMx06hYFsha9oLqlwFGSjMt2Cu9ZV0SEQhrnB72twueBhxEZVAqabF4TPo8ipHx3\n/BtlmvQ5DimyvextK5NmJDQN1HN7l9hs5AjbQ6NH0LXz3ZDI8Oc2paXEdBcamh11HkWdCAKDQLTN\nk3qzkxQULonBrnouP8I10h1jtMgLqksY2hIzmkjhbWmz7Yu3ZGOqiVtu0WiGSCRuOOVmFzalpNTk\nWvbm1wdQg7KA7FXE9ZJl5x2TOI4Z8GXOs8MdkgY18MmIvZzXkBpDcJPOY7FTQ7Stuyyhl3yxTSVA\nLceOmFwwtDy/e7EB/R6VuX3nLY6Mtkc0kbRQWpkeNxAyrMyKoxUpmNc8guQ4Wzm32iKz2eos2Uk0\nlHNxGvNY0OAOKlf6Q3L1+PynF/l4pnHPCqdLthwS4RWiTibDPZy+oxxSveYTLCAcMr3OaQ4DCcx0\nLpL3u1lklZJyUWdjrNHWSNzZYyC97sb3No9urcyB71V3rc7LTZWsawcohi4uItyc2J0kbpGNNQK0\njyzFKnetld7LQ2zxVdGQyCOLnh7jRjKc4k9XlXocKWPNFyXTR4/NhkwtRk7MDpQAtLwKbLycvkfi\nbJLI6IAAAR8Y8NLQMmtLaEDq3reLaXXRxrwJFFJNVAlW9WUUHapZKR0fAhwFpadMLSRXqou4ivVz\nHF7HgAb9q+Y3XMY5KrdOtum5ezx8kXjSfseTy8DeS0dvYZ5bxna18lGw0kyG0HIAbVtLVZHutsM7\nJGl3FvYWvaRhAGtOtcdwNv8Ags8j+OqA8UD25ltKrpXcMrCJG0e5wYx32wtNSToNKqmXJFPrwc7w\nZL6RbYLwtT2SExtAs7nR51HGOccIcMsgtjC549+yIGABvGOcaVI2Bc3dPDGF8LhaJAHGcYQG/wAW\nCCCaKV78MoGQTOgeHyvl5rXNJGEUFT0UCxllikT9vkbqjd3ZhkEkb5LPaMEjn0p72prmOtcvfvDQ\n2a0Ssj4u0tcG56NYR8Eb1reCvCKGIW6SZ1JZmcwAanPIU0zIXGSuqSd5qubLlbpJnZg4i2eyNjfV\n6SWyZ0z2tBwgANyAAWOxuv4pKVnj+1udXUhoG/erRo78VSl0dVJdIxbGOcV9A4JMpZx9+SV8/h2l\ndbctvLY2DYAuzgy8nNz4OUOjqrU/COgrQXjIFO03gTqe5au1zgrpySpHl4cL2MSQVPat7f3BE2ax\ni0mWpo0llPjbAVo4Iy97GjVzg0dZNAum4d3babPZo8dqfKwkN4s5AZLz8/ULPT2qUVdHDJUUiELz\nz0kAWa0LFa2pFFnYaPIHQujD4MsjKbWyjwOgLo+B1lD5wSMmDF27FoLUftufR6F1PAuYMEp2lwHY\nuzi/szl5LaxnZxQM98RqsG9bG0gnJZMdpbTVa68baBlVdPdni18FXBG72SWglzQWxiuelTosiSCC\n1Xk2NjG8XA046AUc7pXOOvWSAvMT8OPI9IWtu6+Z7M9743DE8UcTnr9K5c2T8r9keniwOSv3Np4R\nnQC0NiiY1vFjnkZZnZkuTKvtErnuL3ElzjUneSql5rbbtnpYoKEUiFFmx+9CxKLOiYQBXaKhbYSM\nng+mJKSZWRQVE0gmR2oAokR0JlIuCBAmR0oqglAIFKiaQQkRBXPeEDg9Fel32mxyCvGMqwg4cMje\ndG4HocAuicFAjpQlOmfnTwhhkglkikaQ9jy2RpyLZGEtdlsOqu4FzYbVCWiruMGGmtajbsXceNDd\nbbLwkteEAMtEVntDWjTnxhju3jI5D+UsDwOXIJJjM8ZMOWQzNd+wfqXNyZKGNtnocSDnlVH2mzRO\ncyvGFhp+MK03FX3ewxsDMRccyXaVcSXONNmZU4W+RQLwCvnPJ9XKVoyGmp6VAlKF3d0+3tVXYfbv\nUNGIMm/UtndU+eflWujj37fYdayomiPNLLX0bi+bbghJa0OdTIbyvnNpvaGKF1qtLpX0cKxxRvle\n0uPvcDAXArrJrfiy3ZUWG6yh7sZYA4/CGRLdzqahbLvyRGSijE4EcIbDb3uEMkmJjQXMkjfG9gOl\nQ9o+lbPhzO0Wc2SzPHHTPMVBrCxwPHSvA97RpdTecK2VwXREJAedWtS2utBlXorTyLWXqG8fNhOX\nGvpu98fIvY+nLRyr3PF+qT3UTX2eFrGNYwYWxtDWgbGtADR3AKalRFF6B5DFRJSomEFEaKtwzVxB\nVW1QwhnI1WSybJUFtUgaK8Z0HGy90tVHEohCmUyqiSqkXISIWbkWSEpMFSgBTjJ0Gp2+2imPbJfg\nyDQkNbowZ9J2qUlMLu5ETcIoiU/a3dJC3b6MPcoibkVn3bPQU3LGsreaVBvNKiGRwdlpx2VG2Myg\nZFitkqgvW0s1mSxUZdmlaJGFxIaHCpGoFc6dK3nDfhCy1iKKIO4uIe+dq40ouWTXPkyOSousSu/g\nRQApUTa2pWBsZV2Q1cXnSMYidldgVkALjXeaqtjiQI25D4R3lZUYpQLrh0qRzzfZiSmsh61m3RaS\nxxFdVhNze49JR711VXHkcJbF5w2jR04vAqi1WwvWsEqUki7J57ONcZJk7Q+qwzqpufVQK4skrOyE\naIuCAE01zmyE1tSBvK2Dm84gaNACosuFoLnCuwDp3q+FlBU6nMrpxKkYZWfR/bVBKgx1dRTrVlVg\nQCiXKLkIAqlVCKISFUYjvSojsQDDyptKqKbXbkBaQolNpTdkoB438ZcvtnCh8DaOdgs0DQPg82pB\ny++cfyguw4HXC2xwMjGZABJOtTqtjwk4Jw/ZyW3mpe7G8tcanjXktLzXMfawKdDhsK24jpTJeL9Q\nzXLVex9N9M4+kN35YMbktVb34HLcNK1t6w4h39uVF5yPRkUxWgHatnZ5RQ7a+T2C46RzotvTT9Cz\nbLepD2Choa1cKUbSlAamp29y01+DJs6djc6hW2g83XMad3lWFBaQRUEUWR77PPZ3ZLH3Lo5K/rut\nILuKtskRdmAWMeGmmoFASO1cQ+9b9u6UcpY61wPeA20WdlW4TpiaDVpy2011X1+1WJswIqQ74Lhq\nFRcdhnEjoHta9p2jTPXI9ncvQ42S+mi8pQ17bi18BwB4TyzWR8pY+J4AjAkHwnCpLXauIbX81XNC\nsnw4qNFGtqGgCmVa6dZ8qTcl7eKKij5jmZvVyNrwQISCk4J0VzlI0SVgGqQCWBVVQ1VztFSVALQF\nBzEkVQkSmCkhRYJEhAKAEBASYwlZMLQNFQHlMOPt5FZSoq1ZkOKU38GPxlSHlSc4kAblLmRqZFlG\nSlPFXPaqI5CFYJypclRGrsqaSFYCh7wdiiAqWWosUgVWFMBATFFJgJyCjGG7VlMlaFeCXuQ/4LYI\nw0U3qwfpVbZmptlbn1Fbuaow1ZRZvfK60R1HUqbOQK1WUJBvWSpo0d2Y0b6ZKWJTmY05giqpCps1\n0WqyaEgU6qrdlqABP2ohoJWRFZ9p7lMVbIboVnjxGp0Cy0DoTBzC6V0jnl2d213arXH2CpCm0rmZ\nYfV5f0oT7EkJElRSPsEvboQCISJohHUgCqVarl+G/D66rnaTbLSwS0qLLHSS0uBzH2sHmA73YR0r\nzX4VfDdbr1D7PZa2Cx1oWRSO46Zv8/M0jm/eigzzqtYYZS/gHpfhlw+uq56cstTGSEVbZ4wZZ3DS\nvFs96NczhGS4q7PC9NeQmdZLIyz2cO4uOWeTjLQ805zzEwCOGhO+TQryIbQTXPXXpXQcAuGUl2TE\nlpls8hHGx1o7djYTkH071HK48vSfp/sdPFljWRep4PRbAXOL3Evc4kucakuccySetWuOzVYHBq+7\nJeEQms0zZW6OAyfGfiyMPOY72C2T418jOMk/y8n1sZxa/HwVsKotDcqK9raIcAR1qqJZzV5xgilN\n/wCvVc9aWOYcics/RVdlbrFiqa5H271o7xhAqCOpbQMJmrsN8GM0ca09slvrDfzDlX06Lm4bgtlr\nlwWazSTOJoAKBoLjlV7iGt7aLPPg3vxh59iLRXZaLLlv0mXZj4csncUziy82GJ1KSX9WdXdd4h7s\nvJ392S6ITAMkkG0YW9BdUCi4W6+CV4wkY3xwtrmC4Pd1cyo8q6kkhrWE1p2VO+i6sXClCVvo5M3P\njONRdlFEyCpBOi7zzSAqjNTohoUkkBVBPQpqTm0UAod1KFFlOCWSULMaidFc4bKKIbvShZWnRWOj\nGSQjShZFMKwRjejAlCyICdFYI1cyJu2umXWraMhyRj0UgFaIwmI1GrJtFQCauESYh6U1ZFlVFIBT\nMaYYVFE2QAUwFJsZU2xFNWRZWFKinxalxJ1SmLIAJqbYymIylMWQCkApmMoDSlEpiomE8JQgsAmA\ngJgKAATqd6KJgKR0ME708R3pUTDUHR9JoUoq5pnuUYcyrHOWkIR39iKqCSPcUKm8LZFBG6aaaOGJ\nmbpZnsjjaPvnvIAXxfwl+H2yWUOguprLZNobXI0izRn+bbk60O7m6aq8Mbl4B9W4V8J7DdUPH220\nMgZnhBzkkI+DFG3nPPormvOPhK8PtttWOC7WusEBqOOxA2t4/HbzYPyan75fKOE/CW1XjM+0WqeS\neV+r5HVoNjWtGTGiuQGS0UknSu2HHjHz2ytl1ttckr3Pke6R73FznuJc5zjq4uJqXdKxC5Dyq3Fa\ngkSkSolyRUAy7qvO0WSQTWeaSCRuj43YTTc4e9e2uw1C+q8E/DMRSO8YK7OU2YeWSA6fknsXx9GX\n9y5eRw8eZfkv7+504eVkxfqz1hcHCS77e2tmtUMxpXA1wEja/GifR7e5bazNDjSi8cVbkQcJboc8\nj0HUFdFwe4ZXrC4MivG1CnvQ5/HNrsFJg7Kq8XN9IcX+Mv8AJ6mP6sn+y/wesXXYXZFuR2/QQtdZ\nuDEDrRjkDnU2VIHdVfCLF4Z+EDGgcqiky1fZoK9uBjaLGtnhUv6Un9/cVXXiYLO07dvFEqYfSMr8\nUH9Th72egvCjfjbnu0SWVwgtD54o7NhDa4w4SSENIo4CGOSuzQbVleD/AMJNnvuDC7BDbYweOs9c\nn01lgqauj6MyK55UJ8sz3rabVIZ7VaZ7VKGuAfPI+QtBzLYw4kRtyGQposexWySF4kje+N7H4mPY\n4tc1w0c0tzBX1HB4Xo4tZO2+z53nyjyJ34o9c3mVpZdSvmnBPwuktbDeLSSMhaom5npmjbr1juX0\nG7rys9qbxkE0czd7HB1Ohw1aetcfJxSi+0W4/SoyGJoahcR1iCdEJoBAIATITBQEHFKqHJgZIBvB\nyUdSU0AKSKAKRKKpgICXFGmLYDRACeEp6K6ZAMGisHUokJtcpTIJYSpMCexOlQUIJhuWzNDWjalH\nu8isDe1SBDDTMVOxJo6FbDHU60G8qWLIDLKuaULIR7qdKkwd6k8aZUyzQN6EBg2KQp7elSOZr3Ii\nGymuqAbBmpBlNiVKGmxW55bgrUQ2VtapGOgrlTRSJI/QkDVVBHBmpYBuUqU6c02j0KasmyGAblLA\nNykgJSRFjDaJcX0KbelSpVWpEWyGAUrkmGKWBSDc01RFnblOMZJVRGTVc7JLCFXNK1jXPc4Naxpc\n57iA1rWirnOJ0FAVYV8Y8aThnyKwsu2F9JrcC6ahzZZWmmE7sTxTqjeNqtjhtKiT4j4eOHbr7vJ7\n2OPI7MTHY4zkMOkk5Gx7nCvUGDYvm5nO3P0pWmWpWO5y9BdKkGZOIFVuUIXV7FOTRaJlGVuUCUVy\nUQoYGSiqVE6JQDEoOPt7e2akQEw3XPvShZjTGuntvV/B7+FZWoAcCToQBtqNP7kxF0qTGYdCRUUP\nV+hUnicgnTLnyDGSwktIaQSKVq0GpB0NaqxsqxQ09ftkrGhdONUUbMwSmn0e2ai2TNUmqGrqjIo0\nZIcrrHbpYXiSKR8b26PjcWOHU5pBWK0qQGiv5KH0jgn4U7RCRHbRymL7qAGztHZRsg66HpX1a4b9\nsdvYX2adktKYm5h7a/GY4BwXmCRtM1tOB17y2O2Q2qM5xl1QTzXsLTjY770j0DcuDPw4y/Xpm8Mz\nXns9O0QsW57xitcEdoiNWSCoB1aRk5jh8YGqzKLxpJp0zrTsigBSaEiFUFZTTcgBSBAKRCbNqAgB\noVgaKV9iotCmXZU2BWIaFROuqk1iHAZUQihsCVFNvQnhQIKI2Ir6U6bVNgk3YpNKiApNCmyCxuxM\n9WhSapN1+hLBKMk5a1yUjlkosyPUpkZ137VF9EEoo6gnYFZIBlT2KraVIbgrJkUSoSR0LIjIa3pr\nWu6ixx3KYaaV2K10VaEdfSpDTTVQarHOqeoUCqmSNziMslIDyBR6k3BWTIoZUWqQRRSSSUgM6JAn\nJTipnXcrFWJuR3qzKg1rtUBqFL+5SVOzorcNANFGJqm9cjLlNolbGx8j3BjI2ue9x0a1oLnOPRQF\neFvCzwqfe152q2EnBJIWwsPwIGc2FtNhwAV6S7evTvjLcIzYLkkhY6kt4P5M2moipjtDurAA3/Wr\nxna5Kkrs48ajfySYspVTipSFUylaWVZbZjnr0foUpX6qmzvpiO4E9wqk51XHpOnXmtE+irZaTRo6\nVGii41PQPoRVSCYUgFBpUwrIBRSCAgK6IJBOnUotCsCsgQopNTPt9CArpFSQKbVFqkxXiQybVcym\n1UhWNW0SjJzCoNPYqm7X0eWH4QIHWRl1K8N2j2HSsa0M+G3Zu2FRP5IR9a8BV+HHJY3HmyDHGN0j\nBzwOtgP+7C+vUXmHgheZstshtDfguElNK4Oc9naAf6S9WQiN7WPaate1rmne1wq09xC8rnYbkpr3\nOnFkpUYNFFwyWz4gJGzhcHps29RGromBVbDiAmLOE9Nj1EYA2pBbA2YJCzJox6iMIKSzOSdKBZVK\ngx6iMRNqy+RneE+SHoTVjdGOE6K8WUqXJndCasjZGNTToTqsgWZyDZio1Y2RUDqpAVrqp8nduUuK\ncNhVqYtEdaZUpr1pgFTbC7cpCF25UplrRBo3qRU2xkbExEelTRFog0ZKTXU0UgCgNPSoHQ+gqwuI\nGGuWtFBopVNoy7VYqOicaKbUwKfSiQLGDXb9CAFEbk2VyIU2RRZI0tNK59ClGa7KKsmuak09Oqsm\nRQ3N7kw5IVyJ0GSnhw00zzSwSdQAb02jpUabUyr2Vo7lrKCnek/rUnEdajWuxcpJ5Y8bm+eNvOGy\nB1W2OyjENgmtB4x/9UIV8Bmcu88NF68rva8bRWoltkoYa/xUR4qLs4sMXz+Q6r0q1SRZlMjlCVN6\ni7MKpRkYdSN4PlBCrgkoK/et7y0Jh1CFToQ3c7PqaMvSllTJxUyU9FTGdqm0q6YLmKbSqmqxpWiB\nMBSSQFdEEwmgJgLRIMEJgIViBtQ1RUqhSmGTCm3VQBVgWsWUZc136wsa1OMZDwKtPvm7lkxH9Csf\nFUEUqCMxsI29q0atFPBVYRRzS01aXBzT24XjTcfzQvTXgqt/KLpsrq1dG0wu/wBWeaP92WLy7YGu\nieY9Wlj3xnowuqO8eRfevF9ttbParOT7x7ZQPxi+Nx/q2d4XLyY3hf8ABpB1I+o1TqooC8ezegcE\nNSckpsmiYKlVVhSCWQ0WAoCg1Sqmw1LAap1VYTUWRqWKQKrBUgmxGpMFMKAKdVOwomFIqGJCjYal\nocpAqppUglhRLEKIRVCaLAmoAqVUsihkBMAbkqoqnQJYRuTwjco1TBSxQYW10UmsbuUUwUtAMDdy\nYjahAKWiR8W1MxhAKKqeiA4sKQjGmdEqp1UWiTscYK13Ci3clsNttVacnstomG+scTnt8rQss0XG\n+G22cVwfvI1/hI44QdP4aeKM/muKzxxuSX8ljxPwikrIBXRufW6p9FFpnFZ17y4ppD98adQyHkC1\n7l3TdsMhIotViobqlFCqUKkfwh6q99K+hXTFYxPPHS0juIVGVMlnk2dSmCqmk6DZqVNpVoklzSrG\nlUMKmCtEwZDSpDcqmlWLVAtapAKDPb6VOq1iQxpFAQVdorYgmEgmVUIkwqxqqBVjfYrSLIZkRLMs\n+qwozRbGyZrqxqzKRiWyPDNCNQ0mn4j9R3li+j+Am3CO8BHXK0w2iMdLmPErfzWP71864Qc2eF2x\nkb3EdWB7R2up3Le+D618ntd1zfFtDA78WR/Fv/NcVnmje8P4Jg/DPT6Sr49qBK1fNbI76JlKqg6U\nb0uMG8KNkTTLaoCrxjemHhRuRRaCpBVBwRiU7Imi4lSqqQ5PEmyFFoUgVSHJ4lG5GpdVMFU4lIOT\ncjUtqmCqqp4k2FFzSpgqhpU8SbCi0J1VYcniTcUWKVVUCpVTYiiwFMFVYkwU2JosqmCqqqQKnYii\nyqYVdUwUsUWVRVQJTqliiYTCgCnVTYosQoAphyixR12a+X+M9bhDcDgcjLa4GD8kSSg98YX1Er4J\n45duLbFddmH8daLRKeqCNjAP689yth/dEI8uTFY71fIseQLqZAmqqUbVYh+iuvBDMSY7VjSkgigz\nNQO3b5FkyjIrDkkpQ7nfQVmzNmWxoDabvLvUgd2iqaCf0KbtylElgKk0qpqm0qyZJcwq9ix49fbs\nWQ0LWILGqxqpY7P9asLqLeLILEOCIjUIetvYoRqhCdFVolEQrYyq6K1gUxIZkMHUtnd4061rIlt7\np1qdmZ6BtXbgXZjPwaPhVNWeRtfucY/FY0Od/WH81bWxOwclpqMJ7cRK5i2zcbanHYXu8rifpXQR\nSc+IfFAHcsMctpyfyT4R6ms8wkYyQZh7GvHU4Bw9KnVaLgDa+Ou6zur70GM9bCQPzcK3y+azw0yS\nj8NnpQltFMVEUTTCxLCATATATAQCUghSCAQTQE0AwmCkmgHUpglKiaAYcUwT0pBSagJBx3p4ikE0\nBIOO9GM71FNATDzvUg929VpoCwPKeM71WFJBRMSFS4wqpSCEFgkKlxhVQCkEJos4wp8YVWmAgosE\npTEpVYTU2RSLOOO5MS9CqTSxSO9I6+1eY/HKtmK3XZZx/E2KaYjZ9vmDB/7denD1LyB41du43hFa\nGV/xax2WDtLeUH/3C6cC/IyR8df6VTKryqpguohlQCSQ9sk3KYlDHmWBI0FzQdp9Czp1rsXP6vY/\nQqS8lGZjnAKtpqkKkq9jKIgMBMmiTnAKMYqalTRNl9nrqrXybFU5+EehJpWiFmXZNapyu1SiyCqJ\nWt0gZtkOSnKVXY1Kdbxf4lH5BikQlCpK0ewwIWRZ2VDugKvDkr7rzdTe0+gq8V2Q2TsgrG460fTs\nIVvKRHDO47GFvfWnlp3qq7DzJ29GKnV7elai9rRSFjPjyPxdTAyg7z5FrKekLMjGu0VeXLcWSSr6\n9q09kdQLY2QmoXHhlRoz7v4D7zD4Z7KTzmuEzR964Br6dRDf6S+kUXnXgBfnIrbDMTRmLBKN8T6B\n/dkfyQvRYz00371wfUcdZNvk6uPK418BROiKKVF5xuIBMIonRAACYCKJqAJSohMBAACaAEwgABAC\nkApUQEQFKiYCaASdEJoAQnROiAQTATAQgGEUTATohAgmAnRMBAFFIICYQAEwhNACYSTQAmEJgIDv\nCfai8N+HW1cdwhvl9a0tj4f/ALfDAP8A8S9zN1/Svz/4eWjjrwvGb7reFpk7HzzOHpXZx/cxRzZV\ncunt2qxVyLpXZDKKZ+3SpO1ScEPRFWYlsPkH6VrI/p71n3i7I93esSzUBHtvWcn2UMyMUoOgKTn0\nVbnnYk1tdVKAwCdVe3IJMaq5X1NArEjrU9CyIm5hUxNoslhAFVZBE5XbFU05oLqkoiCvZJn2VOY5\nnpUoBkq5HZrp8RKE4WqVUocgkSrx8EMyok7udSVvWKqNnOabxhfXeVtH5KMzbLHhnkZ8YOHfouZv\nzLimHUGQ95aP+UrrZTSWN+x2H9a5S/ZGmcsyqxvpc53ocFXldQM0+zCicRos+yWjCRULBA61mwxk\n0xUA6dVwQv2NTorI4PbUa7etegvBTfBtl3RhxrJZvtD95DQOLd/QoOtpXnK6nBgOeS+l+Ba+xFb+\nILhgtTTGRXISNq6M/wDEPy10crH6mH+V2WxT1kfbwEwmnRfP0d9iCdE6J0SgJMJ0TAUUBBNOim2I\nlmMZtrSo2HYjaRZQbTaXgrTCdFkWWzcZE+ZpBDNR0VpUd6q5JOn7loY5STaVpFCkE7uLJLQ2BxOb\nammVK6aq20wFj3jMhr3NDqZHCaegKFNNtItPBOEVJrplSaYRRaUYiCkiiYShYkwmAhKIsE6IAUgF\nFECCYCKJgJQGEBOiEoApBKiYCUBoCAmgAJpJpQsEwhOiUDvXuwgu+KCf6Ir9C/O28nlwLzq5+I9Z\nqSfKv0Hv6TDZbU+tMFmndp8WJzvoX5728UjZ+MfIB+ldvHXTM0a5VzKaLSMgt4kMx3JP6kyolTRR\nmtvMnIDfn3ZLDbX29t6yrW44+jZr0pwRA6rJrszLGaBWtbtQKDuUJHq1UWHPIowt2lQa2qyowpRA\n2hNx2VyQT/co1V0SSKss7M1UwLKsrPIrxXYMw5BUEKyUpRBdEvgqTdsUT+lOVQqpbBk2c0KyrQ3T\nrrosOJZ8dHBdGPwZyMwiscZ3Een9a4a824p5nHXjH+RxA8gXdxDmDoJXD3k3DNMN0r/+Kqz5v6oz\niYzMbdM1srPbmEBrxTp/WsFvR7dqtBG3M7gvPi2i5vrCxpGRDgT5Pai21ic6yyQWuPIxytfTpY4O\nHoXL2Qvb71tK7z+pbGzTWkfc6bjUrvhkVdlT2DC8Pa140cA4dThUeQqwBfK/Ahw0mtMn2OtLg5wj\nrZ31FftY50JyFeYKj8Ur64YV42XA4yO1ZU0UAJ4VdxSBEsvTJ9RFVE4xWpGdNfbarRCuetFqks88\nrMg3Hjz1LXc+g8vcufkSeNJ+1nfwcMc7cb7StG8c3I9RWruS9XFjYcJFTznHQ7qb9i3UbMQDhoQC\nOo5haC6bO0TOG1sjqDqcR9Cw5apxkdv02nHJB/H/ANN0W+hYXBC8H8W6HVpY6ozxEYSabtVnTyNY\n0u1DdaadpKxuBsAxNFM3ild2IU17VnypLaOrNPpsGoT3XTr/ANmouNj57wLxiAc5tC1xFG0Ddmxd\nraLSzi5QRUyZtHxecHVO7JcxwE5hdzSOJYGYvv2tw066rcmMq3FwOf5v5H1PlrH/ANKPxRBqlRTb\nGpcWvQ0PA3RUVIBT4sp8WU0G6K6J0VmAowFNBsVhSAU8BTwFNBsVgJ0U8BTwFRoNiNEUU8BTDCp0\nGxABNSwFPAo0GxABOinhKeFNBsV0TU8KeEpqNiATAUsKeFNSdjpeGjy27Lyduu+2GvVZ5F4DvUfa\n4+t//KvevhLcRct8OGy6rdTX/NZV4Pv0UbEOhx8oXXxl+DKo0rlIiooouU2LaJDML29u5JxyPUp2\nkUKqmNGnqUvoqQtrWGOLIA4TU7+caek+RUWcZZew9gk0lzGanUU7f0FTaQ1xO4eU7PboVGUB7gFQ\nMz6UVLir42UQDjZsVmiWijWvt3KQDnVTATonGyualEjjbVZ9nbQKiMLIYVtBAcgUo0ioly1KimfQ\nqTSCseYpwFUb7JM6JZcJ0WHZc6e3Wr5zhc0Z7F1Y30Zs3UbSQABUuIDRvJyA71oeH3Bme67ztljt\nGEvhneMTfeu51Qc9BhIPaF2XBWDjLxu2Fur7fY2AfGc60RBoptzK6nxw7sNm4RPnwnBbLFZ5Wn4J\nezHZ39BIETP6QU8mn1/c5nOpUfA3MJ1NG93dvU4/fDDoEpyXFWkBuQXnOJfYyBacNM1JlsechXt/\nQsLD2nduWQyg6SrqTJs2t0220QyMlimfFIwgtfG4tc0jQgjT+9fcvB14YyAIL2BkAHNtkEYx1yym\nibQO629GR1XwKCozKy4rS5unsNmq0VPyGrPbtxT2a3QttFkmjtETsg+M1oRq1zTzmPzGRocws3kG\nYG01wjaaa0G1eLLk4V3jYnl9lttpsznUxcTI9gfhrh4xoOF4zOtdelRtt9T2iY2q0Wia0WkmvKJZ\nHPe01JoxzjVgqdBQCuSjSJlpK/J7YF2ncuS4f2HiHQ2jDVpBjcaaOHOZ5MX9FfEOAfhev6yHk0T2\n3iHghjLeJJuLOxzZGvEpb0EkaL6peF9XjaLM2K2zwyPeWucyCFkUUbm1PMrikOZIzOytM1531BQ9\nJp/2PT+kRzLkKS7Xv/Q3fBq+oOIfxzw0R+8rQF7dMDanNwPkPQtFDeX295bQtfI4jbk5xLc9uoWt\nhgL48FMvID0rLuizA2hjQK0AGXQMvQvBnllOKg/Y+sx8aGOcsi/8iN+XhI+SOEVDC9uL77Pb0V9C\n6Dg3NMwmQDE1haxoGr31GBo7T+aVon2YvmIHOLXdutAvsHBjgwImRvfmWtBa378irnntOXUtePxn\nkkYc3nQ48LfuamwXQY4mspn7553vdm4q37HHcux5CNyOQjcvooQhGNL2PhcvKyZJOUvLOP8Ascdy\nl9jjuXXCwDcnyEblaolPWmcgLuO5H2PO5dhyEbkchG5RUSfWkcf9jzuT5Ady6/kA3I5CNyVEetI5\nDkB3J8gO5ddyEbkchCiok+tI5HkB3I5Ady6/kA3JchG5KiPWkcjyE7k+QncutFgG5MWEbkqI9eRy\nPITuT5Cdy60WEbkchG5RUSfXkclyEo5Cdy67kI3I5ANyUh68jkuRFHIjuXW8gG5AsA3KNYk+vI5P\nkR3J8iK6v7HjcjkA3JrEevI5zwoilx3z/wDSrdpr/i0lV4Qv/wDif/D9JqvfnDODjrsvGEVPG2C1\nxjQZvs8jRn1leAr9Ocf/AIbfQFnxv0Z60TTqQKRQuiKKsptTc1hWj3jx96fQthMNFhvbUEa5HL+5\nTJFDAspyr8XP9HlQxpcTrvP0JNYNBUZ9avYwt3GvtvWdFEOOMDIKYVZJ3JccRqD3V9irUWLHdOSB\n0foVfKmb+9MWpu9BZfHHXM9qUkpGjTTfRFntbcxv2rKgeDXOtVZJAxGzHqWTHMiSAbFXWmVFdKiG\nZgfUe29ACx2yhWBXBB6bE0juCoQ2Zlg98OhTtT6vrXQrHscoa7PRKeSjjkt4vooz7B4Br1uyy37Y\n7TeBLYmF3EyH+DitMgwQzT/zQxOz2ExuOTCV9+8ajweuvq6OPs8ZfbbtxzwtaKulhcBymBu9xa1r\nh0xAfCXi6y2o1GRovYfikcMrZeNktVgtBM0d3Ms/J7Qc38XLxrRA8/CpxWR3GnwVXNf/AHF7HHmj\n3Z4qtFmLctqx3tpkO9eovGh8ERs00l8WGH96z52qKMf4vMScUoaNIHVHUa7HBedZ7qLTomikto+C\nuzNI1vf0LIs419vbYsiSxkJxwkFZqFF1IbXdCkPIjiyp4DkOr28ivRpsBI26lSs0L5HhjRUk0GgH\naTkBT0KJYa9izLC58b2yNpiANMQBHOaWmoPQfQqtOgpKzvfBDaLE2SVuNnHji2w42kunkdjL+KAN\nGMaxhNTUkuZlqvpdoeadK+A3fxsEsdqi9+yQOrTLGDUggbDn3legODVts142dtojNHUpJHtjf8Jp\nHWvE5+GW23sfRfSeTBRcPczrppheM6OGelAf0LecH7sEbmTFxIaag/GOgFN1VRdl2B+EEgNrn+td\nrwSgMlvsscMIlgidK60zPIpFxUTeLjDNTKZJYuoB2/LlxYNmdnK5mkW7NtwQ4HsYeUzR0c4h0cNB\nlTMOk+M+vcuzEfQsnCgBerBKCpHyPIzTzS2kzG4roRxXQsrCjCrbmGpjCLoT4pZAanhUbjUxuKTE\nSyMKeFNidTH4pHFBZNEUUbjUxuKT4oLIoiibjUxuKT4lZFEUTcUY/FI4oLIonRRuKMfikcUsiidE\n2J1MfikcWsiiKJsKMfigmIlfhRRRsyaKeKCOLV+FGFNhR4ll8ckOa5p4N5OaWn/tXYRQ/wAn7l54\nt/DDjSDyfDQUpxtf/wBYXJoWUcko+Ds9SR0LuEn8z/WfsI/wk/mf6z9hc8hWWafyN2b9/CKv8T+f\n+yq/s9nXivz/AKcK0iFPrz+SN2bV17CtRHT8uv8Ayp/Zk/EHf+palCr6svkbM24vo/c/zv2VIX3/\nADX5/wCytMhT60/kbM27r3adYR/S/ZVLrfGf4j8/9la5Cj1pfJGzM829n3Kn5f6k2XlTRpH5X6lr\n0KfWn8i2bqG/nDWPF+VQ/wDCrHcIa/xP5/7K0KFP3E/knZm6+zg+5fn/ALKbb+p/FfnfsrSIU/c5\nPkjZm7df5+5/nfsqp19vPwfzv1LUoUfcT+RZt230R8D879Syo+EpAzgDqbS79lc8hSuRkXuQdGOF\nDvuXc+n/ACrq+A/hkvG5p2WixcZE5pHGR8eTBOB8GeHBhkFKjeKmhBXzJJW+7yVV/wCisoKXk9fz\neOsyRjo5OCzXte0tex161a5pFHAtN3GraL4fwj8J1jtE8klnuh9lie4ubA63Cbi66tEnJGEt3Zdq\n+YJquPk5Ifq/JHpxOz/w2jz/AHl/X/2KofwwYf8Auh/339kuSQrfd5fn/Q0idUeFzf8ANv63+zRJ\nwtBp+99B913f6tcqhR91k+SdEdQOFY/zbT+d/s1czhkB/wB2r/rf7NcihPucnyNEd7dnhDEL8XIg\n8HJ7HT817dx+01B6VvHeFuyh/GRXO+zPo0Vgt+FpA1xNNkOIr5MmqSzSl5ZeL18H3O5/D3BFNZ5J\n7otVpZA4vEP2X4uOR9HNHGDkDubztmE1a3PJfRbp8cuCyxiOHgoGN6L3zOup+x2ep7zvXkZCpuyZ\nyc/2dnsX3b/yY87/AFan7t/5Med/q1eOUJszPRHsb3b/AMmPO/1aj3cHyY87/Vq8coUbMaI9je7g\n+THnf6tR7uD5Med/q1eOUJsxoj2N7uD5Med/q1Hu4Pkx53+rV45QmzGiPY3u4Pkx53+rU/dw/Jjz\nv9WrxwhNmNEex/dwfJfzv9Wo93B8l/O/1avHCFOzGiPY/u4fkv53+rUe7h+S/nj6tXjhCbMaI9j+\n7g+S/nf6tR7uH5L+ePq1eOEJsxoj2P7uH5L+ePq1Hu4fkv54+rV44Qo2Y0R7I93D8l/PH1aj3cXy\nX88fVq8boTZjVHsj3cXyX88fVqPdxfJfzx9WrxuhNmNEeyPdxfJfzx9Wo93F8l/PH1avG6E2Y0QI\nQhQWBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQh\nCAEIQgBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQhCAEIQgBCEIAQhCA//2Q==\n", "text/html": [ "\n", " \n", " " ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "YouTubeVideo(\"rbsqaJwpu6A\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*A Theory of Everything* was the title of a talk given by Demis Hassabis, neuroscientist and co-founder of DeepMind. DeepMind is an Artificial Intelligence think tank, which has been acquired by Google in 2014.\n", "Hassabis explained that there were only two scientific fields he felt drawn to. The first one is physics obviously dealing with the most fundamental questions one could imagine. Most questions physics is concerned with, like the origin of the universe or the nature of time seem to be way more far reaching than the fugacious existence of the human race or even all biological life altogether.\n", "So why neuroscience? At first glance neuroscience seems to be tied to biological life and everything neuroscience deals with seems to be so short-lived compared to the universal questions of physics.\n", "\n", "Demis Hassabis stated that everything we perceive or reason about is tied to our mind and every question we ask or answer couldn't exist without our mind.\n", "\n", "So the understanding of the nature of intelligence or maybe even being able to create intelligence is essential for understanding of basically everything else.\n", "\n", "To some the impact the coming advances in AI will have on our everyday life, will be even bigger than the changes caused by the ubiquity of computers arisen in the last century. \n", "\n", "Understanding the basics of AI or reinforcement learning could also be about preserving sovereignty and autonomy in a world shaped more and more by the rise of AI technologies.\n", "\n", "To me it's fascinating that the principles behind dazzling results like DeepMind's [Human-level control through Deep Reinforcement Learning](https://deepmind.com/research/dqn/) aren't that so much different from the agent traversing through the small grid shaped world of 4x12 squares built in the rest of this notebook.\n", "\n", "And it's even more exciting that even the most recent results of a 500 million dollar think tank like DeepMind can be implemented and reconstructed by everyone around the world willing to invest a little time.\n", "I think this is unique to the field of AI right know. It would be unthinkable that anyone could reproduce the recent results in chemistry or experimental physics on her own at home." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A Whole World in 4x12 squares\n", "\n", "To take a closer look on RL, the model problem of a [gridworld](https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node65.html) is borrowed from Sutton and Barto, two pioneers of RL.\n", "Here is a plot of this gridworld:\n", "![Cliffworld](cliff_map.png)\n", "The world the agent has to deal with consists of just 4 $\\times$ 12 squares, representing all of its possible **states**. The mechanics of this world are defined by a small number of rules:\n", "\n", "1. The agent begins each episode on the green square in the upper left corner.\n", "2. At each time step the agent can move one step.\n", "3. The agent can't leave the board.\n", "4. There are two ways an episode can end:\n", " 1. The agent reaches the goal state\n", " 2. The agent steps on one of the pink squares. If so, she falls off a cliff.\n", "5. Living means suffering. Thus each time step the agent receives a negative reward of **-1**. If the agent falls off the cliff he gets a penalty of **-100**\n", "\n", "So the basic loop of every agent environment interaction is:\n", "\n", "```\n", "while episode is non terminal: \n", " agent chooses action\n", " environment changes state\n", " agent observes new state and receives reward for new state\n", " REPEAT\n", " \n", "```\n", "\n", "The goal of RL is to find the sequence of action which maximizes the expected return over time.\n", "\n", "As simple as this model may be, it contains all building blocks needed, to describe a wide range of different problems apart from as grid shaped model environment.\n", "Being a framework helping to formalize problems rather than a set of distinct methods it's sometimes more about posing problems to solve in the right manner, than a particular set of methods.\n", "\n", "So what's the gridworld about?\n", "\n", "Because life is cruel there's not much to win in this small gridworld. Every step the agent takes means pain thus the agent wants to end an episode as fast as possible. The only thing worse than taking step after step without finding a way to escape this suffering is to step on one of the cliff tiles, which means falling off a cliff and results in a painful punishment of *-100* and the termination of the current episode.\n", "So in this model world, maximizing the reward (minimizing the negative reward) means finding the shortest path from the start state to the goal in the upper right corner without falling off the cliffs.\n", "\n", "But of course the agent doesn't know any of this at all yet.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next this small gridworld is created. Basically this domain has just two responsibilities:\n", " \n", " 1. Receive the agent's action and change its state in response.\n", " 2. Compute the reward signal for a state.\n", " \n", "Other methods are only for logging states, making sure the agent doesn't make any impossible moves and checking whether an episode terminated or is still running.\n", "\n", "The next cell contains the most important parameters of the cliffworld:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "State = namedtuple('State', ['m', 'n'])\n", "\n", "all_states = [State(0, 0), State(0, 1), State(0, 2), State(0, 3), State(0, 4),\n", " State(0, 5), State(0, 6), State(0, 7), State(0, 8), State(0, 9),\n", " State(0, 10), State(0, 11), State(1, 0), State(1, 1),\n", " State(1, 2), State(1, 3), State(1, 4), State(1, 5), State(1, 6),\n", " State(1, 7), State(1, 8), State(1, 9), State(1, 10),\n", " State(1, 11), State(2, 0), State(2, 1), State(2, 2), State(2, 3),\n", " State(2, 4), State(2, 5), State(2, 6), State(2, 7), State(2, 8),\n", " State(2, 9), State(2, 10), State(2, 11), State(3, 0),\n", " State(3, 1), State(3, 2), State(3, 3), State(3, 4), State(3, 5),\n", " State(3, 6), State(3, 7), State(3, 8), State(3, 9), State(3, 10),\n", " State(3, 11)]\n", "\n", "cliff_states = all_states[1:11]\n", "goal_state = State(m=0, n=11)\n", "start_state = State(m=0, n=0)\n", "\n", "terminal = cliff_states + [goal_state]\n", "dflt_reward = -1\n", "cliff_reward = -100\n", "\n", "moves = {'>': State(0, 1),\n", " 'v': State(1, 0),\n", " '<': State(0, -1),\n", " '^': State(-1, 0)}\n", "\n", "parameters = {'all_states': all_states,\n", " 'cliff_states': cliff_states,\n", " 'goal_state': goal_state,\n", " 'start_state': start_state,\n", " 'terminal': terminal,\n", " 'dflt_reward': dflt_reward,\n", " 'cliff_reward': cliff_reward,\n", " 'moves': moves}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now it's possible to actually plot the map of the cliffworld." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAADUCAYAAACCjWQjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4xLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvAOZPmwAAIABJREFUeJzt3XdYFOfCBfCzS5cmRQRRQdQFxMIS\nG8YCqDGWKPHaGyZqmsYYY/RGE0tMPk0siaBYMVjQaILtRqPGWIJiD7G3aFSKYqEXaft+f3jZ6wqM\nqDuL4Pk9j0/iuzNzZlZmz07ZRSGEECAiIiqDsqJXgIiIXmwsCiIiksSiICIiSSwKIiKSxKIgIiJJ\nLAoiIpLEoiCD2LNnD95//30EBASgcePGaNOmDUaPHo1jx46VmDYoKAidO3fW/j0sLAyenp44ceKE\ndiw5ORkjRoyAr68vXnnlFezYsQMAsGDBArz66qto0qQJxowZI/+GSdi0aRM8PT2xdevWJ047fPhw\neHp6lmu5GRkZ+O6779CjRw/4+vpCrVajR48emDNnDu7fv1/qPNeuXXuqddf3/FS5GVf0ClDVlpmZ\niYkTJ2Lv3r1o2rQp+vXrB0dHRyQmJiI6OhpDhw7FlClTMGzYsDKX0blzZ9StWxceHh7asa+//hoH\nDx7E0KFD4enpCT8/P+zbtw/h4eFo2rQpxo0bB1dXV0NsokHdv38f/fv3x/379xEcHIyBAwcCAM6f\nP49Vq1YhOjoaUVFRqF+/vnae6dOn4/Dhw9i1a9czZS5ZsgTh4eE4ffq0XraBKh8WBclq8uTJ2Lt3\nb6llMHLkSAwePBhff/01GjZsCH9//1KX4eXlBS8vL52xS5cuwd7eHp9//rl2bMuWLQCA0aNHIyAg\nQL8b8oJYtGgR4uPj8fPPP6NJkyY6j/Xo0QNvv/02Zs6cicjISO34H3/8ASMjo2fOPHToEAoLC595\nfqr8eOqJZHPgwAHs3r0bPXr0KPWIwdraGtOnTwcArFmz5qmWXVBQACsrqxJjAEqMVyXHjx+Hg4ND\niZIAAH9/f/j4+OCvv/5CUVFRBawdVVU8oiDZbNu2DQAwaNCgMqfx8/PDL7/8onOq5HFhYWFYuHAh\noqKicPPmTXz22Wfaxzw9PdGyZUudax2DBw8GALz++uvYuXMntm7dqnNEEhwcjAsXLmDLli3w9vbW\njnfr1g0WFhaIjo4GAMTHx2PRokU4ePAg0tLS4OTkhI4dO2L06NGoXr26dr6goCB4eXlBpVJh9erV\nUCqV2gIsTVRUFNatW4f4+Hi4urri3XffLXPax1laWuLy5cvYvn07unfvXuLxdevWwdTUFACQkJCA\njh076jxXY8aMwYcffggA2L59OzZs2ICLFy8iOzsbtra2aNmyJT7++GO4ublp53l0/jfffBOzZ88G\nACQlJSEsLAwxMTFIS0uDs7Mzunbtivfffx/VqlXTzvfPP/9gzpw5OHPmDFJTU+Hk5ITAwECMHj0a\n9vb25d52qjgsCpLN6dOnYWxsXOq730c1bNiw3Mts0aIFvv32W8yaNQtGRkaYOHEiHB0d0adPH/z2\n22/47bff8MEHH8Dd3R0uLi7YuXMnDh48qC2K+/fv4+LFiwCAI0eOaIsiPj4eV69exUcffQQAuHLl\nCgYPHoy8vDz0798f9erVw5kzZ7B27Vrs378fGzZs0HmRO3z4MM6fP4/x48fj9u3baNGiBQ4dOlRi\n/WfNmoXIyEi0bNkSAwcORGJiIr744gsYG5dvVxw0aBDi4uIwfvx4LFmyBAEBAWjRogX8/PxgZWWl\nLQkAsLe3L/FcFb/wr1ixAnPmzEH79u3x0UcfQalU4sSJE9i+fTsuXryIHTt2QKlU4ttvv8WSJUtw\n/fp1zJ49G3Xr1gUAXL9+HQMGDAAA9O/fH87Ozjh9+jRWrFiBw4cPY+3atTA3N0dqaipCQkKgVCox\nZMgQ2Nvb4/z581i3bh1OnTqFn3/+udz/9lSBBJFMmjVrJl599dWnni8wMFB06tRJ+/fQ0FChUqnE\n8ePHy5ymtOmKiopE69atRUhIiHaabdu2CU9PT9G+fXvx7rvvasdXr14tVCqVuHTpkhBCiCFDhghP\nT08RFxenk7F582ahUqnEZ599prMuKpVKxMbG6kwbHR0tVCqV2LJlixBCiGvXrgkvLy/x7rvviqKi\nIu10sbGxQqVSCZVKVa7nJyoqSqjVau08KpVKNGrUSAwfPlz88ccfJaZ//LkqLCwULVu2FP379xca\njUZn2vHjxwuVSiXOnj2rHRsyZIjw9vbWme7tt98WLVq0EImJiTrjW7ZsESqVSixdulQIIcSOHTuE\nSqUSO3bs0Jnu22+/FW+++aZITk4u1zZTxeI1CpKNkZFRhV4EVSqV6NChA06ePInc3FwADy/Menl5\noX379jh+/Lj2XP7+/ftRt25dqFQqpKSk4Pjx42jXrh18fX11lhkcHAx3d3fs3r0bGo1GO16tWjW0\natVKcn327dsHjUaDQYMGQan8365XfG2hvAYNGoQ//vgDc+fORXBwMGrVqoXCwkLExsZi5MiRmDt3\nruT8RkZGiImJwbJly6BQKLTjmZmZMDc3BwDk5OSUOX9aWhoOHTqEVq1awdzcHCkpKdo/bdu2RbVq\n1fDbb78BAJydnQE8vHPq999/R3Z2NgDg008/xaZNm+Dk5FTu7aaKw1NPJBsnJyfcuHED+fn5OqdE\nDCkoKAibN2/GsWPH0KFDB8TGxqJ79+7w9vbGxo0bce7cOTRo0ADHjh3TXttISEiAEAINGjQodZkN\nGjTA9evXkZaWpj39ZGdnp/PiX5r4+HgAgLu7e4nHGjZsiHPnzpV7u6ysrPDGG2/gjTfeAADcuHED\nmzZtwooVK7B8+XJ07dpVsnxMTU1x7Ngx7Ny5E9evX0dCQgJu376tffzREnzczZs3IYTA7t27sXv3\n7lKnSUpKAgCo1WqMGjUKERER+OCDD2BiYgJfX18EBASgd+/evEZRSbAoSDYtWrTAtWvXcOrUKbRo\n0aLM6d577z04Ojriiy++gJmZmV7XoW3btjAzM8PBgwdRq1YtJCcno3Xr1mjUqBGAh9cp7ty5g/z8\nfHTq1AmA9IskAO1RyKPlV57bT4vfvefl5ZW5TCl///03Nm3ahI4dO+KVV17ReczNzQ0ff/wxrK2t\nMWfOHBw7dkyyKCZPnozo6GioVCr4+vritddeg4+PDw4ePIjw8HDJ9Sh+frp164a+ffuWOs2j11wm\nTJiAoUOHYu/evYiNjcXRo0dx/PhxREREYMOGDdrrHvTiYlGQbLp27YoNGzZg/fr1ZRbF2bNnsW/f\nPjRq1EjvJQH875TQoUOHULduXZiYmKB58+awtLREgwYNcOTIEcTHx8POzg5qtRoAUKdOHQAPX5gf\nJ4TA1atXYWNj89S34RbfSXTt2rUSF/Bv3rz5xPkzMjIQERGB9PT0EkVRTKVSAYD2FFJpTpw4gejo\naAQHB2P27Nk6p5/+85//PHE9ateuDQDIz89HmzZtdB4TQuDXX3/VTnPv3j1cvnwZzZs3x8CBAzFw\n4EAUFRUhIiIC8+bNw8aNGzFhwoQnZlLF4jUKko2/vz8CAwOxffv2Uj8nce/ePXzyyScAoL3bSA5B\nQUG4evUqfvnlFzRt2hSWlpba9Tt58iT279+PwMBA7VGBg4MDmjdvjpiYGPz11186y9qyZQtu3ryp\n8xUj5dW5c2eYmJhgxYoV2s98AMDJkydx6tSpJ87v6+sLDw8PbN26FTExMSUe12g0+PHHH2FiYoKg\noCDtuFKp1DlKSktLA/DwFNqjJZGYmIidO3cC0D3CeXx+R0dH7SfhH/+09ubNm/Hxxx9rbzHeunUr\n3nrrLezZs0c7jZGREZo1a6b9f3rx8YiCZDV79my89957+Oqrr/Cf//wHnTp1gq2trfY0SnZ2NsaP\nHy/rJ6mDgoIwY8YM/PXXXzrf/+Tv7481a9bgwYMHOp83AICpU6diyJAhCAkJwYABA+Du7o6zZ89i\n06ZNcHV11Rbc06hVqxbGjh2LefPmYeDAgejZsyfu37+P1atXw97eHikpKZLzK5VKfP/99wgJCcGo\nUaPQoUMH+Pv7w9raGrdv38bOnTvx999/48svv0TNmjW18zk6OuLMmTOIjIyEWq2Gn58fqlevjvDw\ncGRnZ8PV1RXXrl1DdHS09rRYZmamzvxCCISFhaF58+bw9/fHtGnTMHjwYAwdOhQDBgxA/fr1ceHC\nBfz0009wdXXFBx98AAB48803sXbtWkyZMgVnzpyBh4cH7ty5g/Xr18PGxgZ9+vR56ueRDI9FQbKq\nXr06Vq9ejW3btmHLli1Ys2YNUlNTYWtri1dffRUhISFlnkbRl5o1a8LHxwdnz57V+ZqQVq1awdjY\nGMbGxmjbtq3OPJ6enoiOjsbChQvxyy+/ID09Hc7Ozhg+fDjee+892NraPtO6vPPOO3B2dsbKlSsx\nd+5cODo6YsKECThz5gw2b978xPk9PT3x66+/IjIyEjExMQgPD0dOTg7s7OzQvHlzfP3112jatKnO\nPB999BGmTp2qvUvqq6++wooVKzBv3jxERUWhqKgILi4u6N+/P7p3745evXrh0KFD6NKlCwBg1KhR\nuHz5MpYuXYq4uDj4+/vDy8sL0dHRWLRokfb5cXJyQp8+ffD+++9ri8re3h6rV69GeHg4du3ahTt3\n7sDGxgatW7fG6NGjtaf56MWmEEKIil4JIiJ6cfEaBRERSWJREBGRJBYFERFJYlEQEZEkFgUREUli\nURARkSQWBRERSWJREBGRJBYFERFJYlEQEZEkFgUREUliURARkSQWBRERSWJREBGRJBYFERFJYlEQ\nEZEkFgUREUliURARkSQWBRERSWJREBGRJBYFERFJYlEQEZEkFgUREUliURARkSQWBRERSWJREBGR\nJBYFERFJMq7oFZDDR6FfGSRnwdjPAQCXZv1mkDzPzzozj3nMeySvKm8bAPT0626QvG1/bpd8nEcU\nREQkiUVBRESSWBRERCSpSl6jeB5KpRIT+o/AzTtJ+PF36fN20gtSwG14Kzy4lYHkX8+XeFhhYgSH\nV+vB2qsmjK3MUJCWi9TjN5F+KrHEtGZOVnDs0ED7d9e+vri7/2/k382qmDwZssxr2WrHTGtYyb5t\nzKsaeRW+L8ic98WC6Vgd9gNu/H2jxLRPYmRshPlrv8eVc1ewcGboU8//KB5RPEKhUGBI555wrVHz\nORcEuPTwgXlN6zIfd/1XM9i3ckf2P/dxZ88lFGY+gHO3RrBvU09nUlNHS9QZ3BxmNay0Y2ZO1qg7\ntAVMHSwNnydTVurR/+0Ihtg25lWNvArdFwyQV09VD9+snIva9eqUvvwyKJVKjJsxHvVUHk81X5nL\n08tSqgAbSyt8EDwIr3g2fq7lGFmZofYAP9j4uJQ5jbVXTVjWc8DdvZdxZ9dFpP+ViIQNccj6+y4c\nXq0HYysz7bROHVVQKBS4uea4duzm2uNQKIAaQQ0NmufU2VO2rJQj17Xjhtg25lWNvIraFwyV9++3\nP4VCqcBb494uM+Nx9o72mBE+Ex26BpR7nidhUQBo6uGJz4d+AHeX2th9/OAzL8dKVQMe77aBhWt1\n3D90rczpbJrUgqagCGl/JuiMpxy5AaWxEawbOQMAjKqZwtLDEZmXklGYmaedrjD9ATIvJsPSwxEe\n775qkLzcpHRUc7eHRW15swAYdNuYV7nzKmJfMGTenVt3cGjPQfi1eQW2drZ4ktaB/li8ZRm8mnpj\nY8SGJ05fXhVWFEIIZGdnIzc3t6JWQcvF0QmX4q/hm6hlOHw27pmXY1bDGtn/pOB6xGGklXL+sZhF\nLRvk3cmEKNLojD+4lQ4AMK9lo/Pf3KSMEst4cCsDCqUCeXcyDZInCjVQKBRI3n2xym0b85j3Iudd\nOXcFRkZGaNCoYZk5xdwauOOvI3EY2380dm/a+cTpy8ugF7MTExMRGRmJmJgYxMfHQ6N5+OQplUrU\nq1cP/v7+CAkJQe3atQ25Wthz4hCK/rsu9tZPbu2y3D/8D6ARAABjW/NSp1EYK2FkYYrCjNQSj4lC\nDYpyC2BiawEAMLF5uIzCjAclpi1+15Fx7hYKUnNlz0s/lQSrBjWgNCr7vUVl3TbmMe9Fzku5cx8A\n4FTryddOo3/4CYWFhQ+nd3F64vTlZbCi+OuvvzBy5EhUr14dAQEBqF27NiwtH14Qys7ORkJCAvbt\n24fNmzdj5cqVaNq0qaFWTVsSz+2/JSFFafbwKdcUFJW+iMIiKE2Mnjht8Zjiv9PKnpdf+MS8Srtt\nzGPeC5yX9+BheZhbmJV47HHFJaFvBiuK2bNnw8/PD+Hh4TA2Lj120qRJ+OCDDzBr1iysX7/eUKtm\nWArFf/+njFIpbViqf57UTYbMq8rbxjzmVVCeELr/rQgGK4oLFy4gLCyszJIAABMTEwwZMgTjxo3T\ne76JkTHMzXQbuaioCDl5JQ/1nnY5SnNjaB6Ur8lF8Ttz49LfjShNjLSHn8XvLoytTWFkaaqTVzy/\nJk8696ny/nse9fG8R+eXytPHtpU3i3nMA2TcFyooT2lS8tSumfnD15ucrGwAgKmZKapZWepMU1hQ\ngKyMrBLz6ovBisLZ2Rlnz55F+/btJaf7888/YWdnp/d8taoRBnfuqTN2JeEGFm5a89zLce3dDPHr\nTpZrfk1+EYpy82FsXfIw8uE5TRMU/PeHpyDt4YX+Wr10T8O59m6GzIvJAIDCTOmie5o8E2vzUvMA\nwMTG7Il5+ti28mYxj3mAfPtCReUZW5e83uFQ0xEAcC/5HgCg7WvtMW7GxzrTnDlxGlPe+UxyfZ6H\nwYpixIgRmD59Ou7du4fAwEC4ubnB0tISCoUC2dnZiI+Px549e/Djjz9i4sSJes+/eOMaFm2O0hnL\nefD0d1w9upzRbw4GANzZe/mplvHgVgYsalcHlAqd6xrFnzZ9kJSunU4Igeyr95B6/CbqDHxFm2f3\nSl0IIZB7q+RdEs+al346CXYt6pbIAwBzF1ttntK07HOzz7ptALR5j2bpa9uYVzXz5NoXDL3vFeeZ\nu9iU+MS2ykcFjUaDK+cevs7EHT6JL96bojNNVqZ8RxOAAYuiX79+MDU1RWhoKNatWweF9vzdQ0II\nuLi44PPPP8egQYP0np+Rk4WMnOd/MktbTt7tzKdbxrnbsPRwRHV1baSdjNeO27d0g6awCBkXHr5j\nKcrOR86NVFjUro7knRe00xXlFsDaywnZf9+DJrdAb3n5d7NKzTO2NdfJkyqKZ922R+8dl2PbmFc1\n8+TaFwy97xXnWXvX1PlchpOLE9p0ehXHY44jM/3h60zqvVSk3it5J5WcDHp7bHBwMIKDg3Hjxg1c\nv34dWVlZEELA2toabm5ucHd3N+TqVJiMs7dg6+sKp04qmNpXQ96dLFh5OsGqviPu7ruCoqz/7XR3\n915G3aEtUHdoC+1Y3SEtIIoE7pbzSMaQec+aVfwuEYBBto15VSPvRd4X9JE3K+JbFBYUInLBynLl\nyaVCvhTQzc0Nbm5uFRH9wkjcGAfH9g1g7VUTts1cUZCag1u/nEPGmSSd6fKSMxEfdQKOHRpo77nO\nS87E3f1XkJ+S80LmPUuWY/v62vGba4/Lvm3Mqxp5L/q+8Lx5/1y+hlWhkUi8nlDaog1GIURF3nQl\nD/6GO+Yx7+XIq8rbBvA33BERUSXBoiAiIkksCiIiksSiICIiSSwKIiKSxKIgIiJJLAoiIpJUJT9H\nQURE+sMjCiIiklQhX+Eht+XLlxskZ9SoUcxjHvMqMK8qb1tF5JWFRxRERCSJRUFERJJYFEREJIlF\n8RiFQoHevXujXbt2zGMe85hXKbP0nceieIRCoUBAQAAcHByYxzzmMa9SZsmRVyXvenoW1apVQ0BA\nAFxdXZnHPOYxr1JmyZXHIwoA7u7u6NevH2rWrIm4uDjmMY95zKt0WXLm8YgCgJ2dHRITE3H06FFo\nNBqo1WrmMY95zKtUWXLmsSgAnDp1ChqNBgBgZWXFPOYxj3mVLkvOPJ56ArRPLPOYxzzmVdYsOfNY\nFEREJMmgp578/PzKPa1CocDJkyf1lm1kZARTU1OdMY1Gg7y8PL1lMI95zHv58qrythUzaFHMmTMH\nEydOhLGxMYYMGQKFQmGwbA8PDwQEBOiMJSUlYfv27cxjHvOYVymyKiIPMHBRdOzYEcuXL0dISAjs\n7e0xePBgg2UnJCSUeCLz8/OZxzzmMa/SZFVEHlABdz35+flh7NixCA0NRa9evQxyJwAA5ObmIjc3\n1yBZzGMe816evKq8bcUq5PbYkJAQ1KtXDzk5OQYrCiIiejYVUhSmpqbo1KlTRUQTEdFT4gfuHpOV\nlWWw3yrFPOYx7+XJq8zbxs9REBGRJBYFERFJYlEQEZGkp7pGcf78eZw8eRLp6eklHlMoFBg9erTe\nVoyIiF4M5S6KH3/8EV9++WWZXzrFoiAiqprKXRQrVqyAn58fpk6dCjs7O4N+/QYREVWcchfF3bt3\nMWXKFKhUKjnXh4iIXjAKIYQoz4SDBg1C9+7dDfr9TEREVPHKfUTx2Wef4aOPPoKpqSn8/PxgYWFR\nYppatWrpdeWIiKjilbsoTExMAABTp04tc5oLFy48/xrpgaE+/Thq1CjmMY95FZhXlbetIvLKUu6i\nmDZtGrKysjB48GA4OTk994oREVHlUO6iuHDhAr766iv07NlTzvUhIqIXTLk/me3g4MCvBCciegmV\nuyj69++PiIgIZGdny7k+FU6hUKB3795o164d85jHPOZVyix955X71FNaWhouX76Mdu3awdPTE5aW\nljofulMoFFi2bNlzr1BFUigUCAgIgIODA+7evcs85jGPeZUuS468chfF7t27YW1tDQBITk4udcUq\ns2rVqiEgIACurq7MYx7zmFcps+TKK3dR7N27V2+hLxp3d3cEBARAoVAgLi4OarWaecxjHvMqVZac\neRXyG+4ePHgAc3PzUh/TaDTIyMhA9erVDbY+dnZ2SExMxNGjR6HRaGT/x2Qe85j3cuRVlW0zaFFE\nRERg5cqVSElJgbOzM0aOHFniK0HOnDmDAQMGGPTDe6dOndJ+K64h7uxiHvOY93LkVZVtM9gvLoqK\nisL8+fPRpUsXTJ48Ge7u7pg5cyY+/vhjFBYWGmo1SlXWV6czj3nMY15lyZIzz2BHFOvWrcP777+P\nMWPGAACGDh2Kn376CdOnT0dhYSEWLFgApZK/cI+I6EVjsKJISkpC8+bNdcb69u0LMzMzTJo0CVOm\nTMGsWbNkyzcyMoKpqanOmEajQV5eHvOYxzzmVYqsisgDDFgULi4uOH36NFq3bq0z3rNnT6SkpGD2\n7NmwtbVF165dZcn38PBAQECAzlhSUhK2b9/OPOYxj3mVIqsi8gADFkXfvn3x/fffIy8vD507d4aX\nl5f2seHDhyMlJQXLli3D4cOHZclPSEgo8UTm5+fLksU85jHv5cmryttWzGBFERISgqysLERGRiI9\nPR2ff/65zuPjx4+Hg4MD5s2bJ0t+bm4ucnNzZVk285jHvJc3rypvWzGDFYVSqcSHH36IMWPGIDMz\ns9RpQkJC0K1bNxw8eNBQq0VERE9g8NuMFAoFbGxsyny8Ro0aePPNNw24RkREJKVCPpn9IsvKyjLY\nb5ViHvOY9/LkVeZt4wcXiIhIEouCiIgksSiIiEgSi4KIiCSxKIiISBKLgoiIJLEoiIhIkkIIISp6\nJYiI6MXFIwoiIpJUJT+ZbahPP44aNYp5zGNeBeZV5W2riLyy8IiCiIgksSiIiEgSi4KIiCSxKB6j\nUCjQu3dvtGvXjnnMYx7zKmWWvvNYFI9QKBQICAiAg4MD85jHPOZVyiw58qrkXU/Polq1aggICICr\nqyvzmMc85lXKLLnyeEQBwN3dHf369UPNmjURFxfHPOYxj3mVLkvOvBfiiKKoqAhpaWkGOyx7nJ2d\nHRITE3H06FFoNBqo1WrmMY95zKtUWXLmGbQobt26ha1btyI/Px+9evWCm5sbQkNDERERgfz8fDg4\nOGDChAkIDg425Grh1KlT0Gg0AAArKyvmMY95zKt0WXLmGawozp8/j2HDhqGwsBAKhQKRkZEYNWoU\nli1bhqFDh8Lb2xsHDx7EZ599BktLS3Tu3NlQq6Z9YpnHPOYxr7JmyZlnsKL45ptv0Lx5cyxYsABG\nRkaYPHkyQkNDMXr0aIwZMwYA0LNnT1hYWGDx4sUGLQoiIiqbwYri9OnTWLRoEczMzAAAH374IbZt\n24bWrVvrTNelSxds3rxZ7/lGRkYwNTXVGdNoNMjLy9N7FvOYx7yXJ68qb1sxgxWFnZ0d4uPjtX+v\nXbs2xowZAxsbG53p4uPjUaNGDb3ne3h4ICAgQGcsKSkJ27dv13sW85jHvJcnrypvWzGDFcUbb7yB\nOXPm4MGDB+jduzesra21p5wAICcnB7t27cL8+fPRr18/vecnJCSUeCLz8/P1nsM85jHv5cqryttW\nzGBFMWbMGGRkZGDu3Llo1aoVvLy8dB7fuXMnJk+ejC5duugUiL7k5uYiNzdX78tlHvOY93LnVeVt\nK2awojAxMcG0adPwySefwMLCosTj7du3x44dO+Dh4WGoVSIionIw+Afuyrq319HREY6OjgZeGyIi\nepIX4pPZL5KsrCyD/VYp5jGPeS9PXmXeNn7XExERSWJREBGRJBYFERFJYlEQEZEkFgUREUliURAR\nkSQWBRERSVIIIURFrwQREb24eERBRESSWBRERCSJRUFERJJYFEREJIlFQUREklgUREQkiUVBRESS\nWBRERCSJRUFERJJYFEREJIlFQUREklgUADZu3IjXXnsNTZs2Rf/+/REXF2eQ3N9//x1qtVq25RcV\nFeGHH35A165d4evri27dumHt2rWQ6+u98vPz8d133yEwMBC+vr4YNmwYzp07J0tWadldu3bFv//9\nb9kyUlNT4enpWeLP2LFjZcs8fPgw+vbti6ZNmyIwMBChoaEoKirSe87Ro0dL3bbiP4mJiXrPLCoq\nwvLly9G5c2eo1Wr07dsXhw8f1ntOsezsbHz55Zdo06YN1Go1RowYgYsXL+o9p7T9WgiBxYsXIyAg\nAM2aNcNbb72Fq1evypb3qJWJZwWAAAALuElEQVQrV6JXr17PFyJecps3bxZeXl4iLCxM7N+/X4wY\nMUKo1Wpx8+ZNWXNPnjwp1Gq18PX1lS0jNDRUNG7cWISHh4vY2FgRGhoqvL29xbJly2TJmz59ulCr\n1SIqKkrExMSId955R/j5+YmEhARZ8h41b948oVKpxKRJk2TLiI2NFSqVSsTExIi4uDjtn3/++UeW\nvBMnTggfHx8xadIkERsbK5YvXy4aN24swsLC9J6VmZmps01xcXHiyJEjomXLluKtt94SRUVFes9c\nunSp8Pb2FosXLxaHDh0S48ePFz4+PuLcuXN6zxJCiLffflv4+vqKFStWiJiYGDFx4kShVqvF1atX\n9ZZR1n4dFhYmmjRpIlatWiX27Nkj/vWvf4m2bduKjIwMWfKK/frrr6JRo0aiZ8+ez5XzUheFRqMR\ngYGBYurUqdqx/Px8ERQUJGbOnClLZl5enli2bJnw8fERLVq0kK0oioqKhFqtFt99953O+PTp00Xr\n1q31npeRkSF8fHzEypUrtWO5ubmiadOmYtGiRXrPe9S5c+eEr6+vaNWqlaxF8cMPP4g2bdrItvzH\nDRw4ULzzzjs6Y3PmzBFDhgwxSP5XX30lWrVqJe7fvy/L8l9//XXx6aefav9eWFgoOnToIGbMmKH3\nrDNnzgiVSiXWr1+vM96/f38xduzY516+1H6dmZkpfH19xdKlS7VjaWlpQq1W6+wv+sorzpw1a5bw\n9PQULVq0eO6ieKlPPd24cQOJiYkICgrSjpmYmCAgIAAxMTGyZP7xxx9YtmwZJk6ciCFDhsiSAQCZ\nmZkIDg7Ga6+9pjNer149pKSkICcnR695FhYW2LhxI3r37q0dMzY2hkKhQH5+vl6zHlVYWIjJkydj\nxIgRqFmzpmw5AHDp0iV4enrKmlEsJSUFf/75J/r166czPmHCBKxZs0b2/L///htRUVEYN24c7O3t\nZcnIz8+HlZWV9u9GRkawtrZGenq63rOuX78OAGjbtq3OuFqtxsGDB597+VL79alTp5CTk4OOHTtq\nx2xtbdGyZctnfp150uvIhg0bsH37dsyfPx/t27d/poxHvdRFUfzD4+bmpjNep04d3Lx5U5ZzwU2a\nNMHvv/+OYcOGQaFQ6H35xWxtbTF16lQ0atRIZ3zfvn1wdnZGtWrV9JpnbGyMRo0awdbWFhqNBvHx\n8Zg8eTIUCgV69uyp16xHLV++HAUFBXjnnXdkyyh26dIl5ObmYsCAAWjSpAnat2+P5cuXy3LN59Kl\nSxBCoFq1anjvvffQpEkT+Pv7IywsDBqNRu95j/vuu+/g7u5eoqj0afDgwdi6dSsOHz6MzMxMrFq1\nCleuXEG3bt30nuXs7AwAuHXrls54YmIisrKykJaW9lzLl9qvi19n6tSpozNeu3Zt7WP6zAOAzp07\nY8+ePXp7Lo31spRKKisrCwBgaWmpM25paQmNRoPc3Fyddzz6IPe7Xik//fQTYmNj8fnnn8uaEx4e\njrCwMADA2LFj4eHhIUvO1atXsWTJEkRGRsLU1FSWjGIajQZXr16FhYUFJk2aBBcXFxw4cADz589H\nXl4exowZo9e81NRUAMDEiRPRo0cPDB8+HMePH8fixYthZmYmazHGx8dj7969+PLLL6FUyvdecuDA\ngThy5AiGDx+uHRs3bpzOO299adq0Kdzd3TFjxgzMmjULbm5u2LFjBw4cOAAAyM3NRfXq1Z95+VL7\ndVZWFkxNTUv8jFpaWmpfg/SZBwB169Z9puWW5aUuiuJ3go83clnjldm2bdswbdo0dOnSRdZTXgDQ\nqVMntGzZEkePHkV4eDgKCgowbtw4vWZoNBpMmTIFffr0kfXOsWJCCCxZsgS1atXSHoG2bt0aOTk5\nWLFiBUaNGgUzMzO95RUUFAB4eKpk0qRJ2rzU1FQsXrwYI0aMgJGRkd7yHvXTTz/Bxsbm+e+UkSCE\nwIgRI3D16lVMmzYN9evXR2xsLBYtWgQbGxsMHjxYr3mmpqZYuHAhPvnkE/Tp0wfAw9NOI0eOxMKF\nC2Fubq7XvEcJIcp8LaksrzEvdVFYW1sDeHjbnKOjo3Y8JycHSqVS76dnKkpkZCRmz56NoKAgzJ07\nV/YfTi8vLwBAy5YtkZ2djYiICIwePRomJiZ6y1izZg2SkpKwdOlSFBYWaseFECgsLISxsX5/tI2M\njODv719ivF27dvjxxx9x48YNqFQqveUVH+W2a9dOZ7xNmzaIiopCYmKi3t81FtuzZw86deok61Ha\nyZMncfLkSXz//ffo2rUrAKBVq1YoKirCnDlzEBwcXOJI/3k1bNgQ27Ztw61bt1BYWIg6depg4cKF\nUCqV2tcCOVhbWyM/Px8FBQU6+0B2drasufr0Ul+jKH5nGB8frzMeHx+PevXqVZq2lzJ//nzMmjUL\nvXr1QmhoqGw7/927dxEdHV3iUNrb2xv5+fnPfQ74cXv27EFycjJatmwJHx8f+Pj44OLFi9iyZQt8\nfHyQkJCg17zk5GRs2LABKSkpOuN5eXkAADs7O73mFZdA8ZFFseJSlOtnMykpCVevXi1xE4S+3b59\nGwDg6+urM/7KK68gNzdX75/byM3NxZYtW5CcnAwXFxft9YJLly6hYcOGen9j8Sg3NzcIIUr8TCYk\nJKBevXqy5erTS10U7u7ucHFxwZ49e7RjBQUF2L9/f6nvHiubVatWYenSpRg2bBhmz54t686QkZGB\nyZMnY9euXTrjhw4dgoODAxwcHPSaN2PGDPz88886f9zd3REYGIiff/4ZTk5Oes3Lz8/H1KlTsW3b\nNp3xXbt2wd3dHTVq1NBrXoMGDVCzZk3s3LlTZ/zAgQNwcnKCq6urXvOKnT59GsDDc/pycnd3BwD8\n+eefOuOnTp2CsbGx9uKzvhgbG2P69OnYsWOHdiw+Ph4HDhxAYGCgXrMep1arYWZmpvM6k56ejmPH\njlWa15mX+tSTQqHAqFGjMHPmTNja2sLPzw9r165FamqqzgW2yujOnTuYO3cuVCoVunfvjlOnTuk8\n3rhxY70WR/369dGlSxd88803KCgoQJ06dbB7925s3boV//d//6f3i6KlXSA3NzdH9erV0aRJE71m\nAQ/vWOnRowcWLFgAhUKB+vXrY+fOndi9ezcWLVqk9zylUonx48dj0qRJmDZtGl5//XXExsZi8+bN\nmD59umwXma9cuQI7Ozu9HyE9rnHjxggICMCMGTOQlpaG+vXr49ixY1ixYgWGDRsGGxsbveaZmJig\nT58+WLJkCezt7WFlZYW5c+fC3t5e9n3d0tISQ4YMwYIFC6BUKuHu7o4lS5bAysoKffv2lTVbX17q\nogAe3qKXl5eH1atXIzIyEt7e3oiIiChxK1tlc/DgQeTn5+Py5cvo379/iccPHz6s9/vjv/nmGyxc\nuBDLli3DnTt30KBBAyxYsACvv/66XnMqytdff43w8HCsWrUKd+/eRf369REWFibLXToAEBwcDGNj\nYyxduhSbNm2Ci4sLZsyYUeq/p77cv39f7y/SZVmwYAG+//57LFmyBOnp6XBzc8OUKVMwYMAAWfIm\nTJgAhUKBOXPmIC8vD61bt8bEiRNlL0UAGD9+PJRKJVauXImcnByo1WrMnj270lyjUAg5bgInIqIq\n46W+RkFERE/GoiAiIkksCiIiksSiICIiSSwKIiKSxKIgIiJJLAoiIpLEoiAiIkksCiIikvTSf4UH\nkZyCgoLQsWNHODs7Y/369bh9+zZq166NkSNHan8vAtGLjl/hQSSjoKAgZGVloXbt2nj77bdhZWWF\n5cuX48SJE9i4cSOaNWtW0atI9EQ8oiCSWUFBAVatWqX9Arj69eujU6dO2L17N4uCKgVeoyCSmbe3\nt863hBb/Lons7OyKWiWip8KiIJKZhYWFzt+Lf5eERqOpiNUhemosCiIiksSiICIiSSwKIiKSxKIg\nIiJJ/BwFERFJ4hEFERFJYlEQEZEkFgUREUliURARkSQWBRERSWJREBGRJBYFERFJYlEQEZEkFgUR\nEUn6f+RYVjW3lLnrAAAAAElFTkSuQmCC\n", "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "rewards = np.full((4,12), -1, dtype='int64')\n", "color = np.zeros((4,12))\n", "for x in all_states:\n", " if x == start_state:\n", " rewards[x] = -1\n", " color[x] = 4\n", " if x == goal_state:\n", " rewards[x] = -1\n", " color[x] = 2\n", " if x in cliff_states:\n", " rewards[x] = -100\n", " color[x] = 1\n", "\n", "ax = sns.heatmap(color, cmap=states_colors, annot=rewards, cbar=False, square=True, linewidths=1, fmt='' )\n", "ax.set_title('Cliffworld States\\n')\n", "ax.set(ylabel='m', xlabel='n')\n", "plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class CliffWorld:\n", " \"\"\"Cliffworld domain for RL.\n", "\n", " A simple domain with 4 x 12 = 48 possible discrete states.\n", " Originally from Sutton and Barto:\n", " http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node65.html\n", "\n", " Args:\n", "\n", " Specified in the dictionary above because this class is not\n", " intended for use outside this notebook.\n", "\n", "\n", " \"\"\"\n", "\n", " def __init__(self, *initial_data, **kwargs):\n", " for dictionary in initial_data:\n", " for key in dictionary:\n", " setattr(self, key, dictionary[key])\n", " for key in kwargs:\n", " setattr(self, key, kwargs[key])\n", " self.record_list = []\n", " self.position = [self.start_state]\n", " self.log_dict = {}\n", " self.reward_sum = 0\n", "\n", " def newstate(self, state, action):\n", " \"\"\"Computes the newstate.\n", "\n", " Takes a state and an action from the agent and computes its next position.\n", "\n", " Args:\n", " state: a tuple (m, n) representing the coordinates of the current state\n", " action: index of an action\n", "\n", " Returns:\n", " newstate: a tuple (m, n) representing the coordinates of the new position\n", "\n", " \"\"\"\n", " move = moves[action]\n", " newstate = State(state.m + move.m, state.n + move.n)\n", " self.position.append(newstate)\n", " return newstate\n", "\n", " def reward(self, state):\n", " \"\"\"Computes the reward signal for a given state.\n", "\n", " Takes a state and checks if it's a cliff or just a normal state.\n", "\n", " Args:\n", " state: a named tuple (m, n) \n", " representing the coordinates of the current state.\n", "\n", " Returns:\n", " reward: a scalar value. -100 for a cliff state, -1 otherwise.\n", "\n", " \"\"\"\n", " if state in self.cliff_states:\n", " reward = self.cliff_reward\n", " else:\n", " reward = self.dflt_reward\n", " self.reward_sum += reward\n", " return reward\n", "\n", " def is_terminal(self, state):\n", " \"\"\"Checks if state is terminal.\n", "\n", " If the agent reached its goal or fell off a cliff the episode ends.\n", " Otherwise it will continue.\n", "\n", " Args:\n", " state: namedtuple, State(m, n), representing position.\n", "\n", " Returns:\n", " True if state is terminal, False otherwise.\n", "\n", " \"\"\"\n", " if state in self.terminal:\n", " self.log_stuff(state)\n", " return True\n", " else:\n", " return False\n", "\n", " def log_stuff(self, state):\n", " \"\"\"Log things for analysis.\n", "\n", " You can safely ignore this.\n", " I will refactor this as a mixin or use a decorator instead later.\n", "\n", " \"\"\"\n", " self.position.append(state)\n", " self.log_dict['visited_states'] = self.position[:]\n", " self.log_dict['reward'] = self.reward_sum\n", " self.record_list.append(self.log_dict)\n", " self.log_dict = {}\n", " self.position = [self.start_state]\n", " self.log_dict = {}\n", " self.reward_sum = 0\n", " pass\n", "\n", " def valid_actions(self, state):\n", " \"\"\"Compute valid actions for given state.\n", "\n", " It's unimportant for understanding RL. Just ignore.\n", "\n", " \"\"\"\n", "\n", " valid_actions = []\n", " if (state.m + moves['>'].m, state.n + moves['>'].n) in self.all_states:\n", " valid_actions.append('>')\n", " if (state.m + moves['v'].m, state.n + moves['v'].n) in self.all_states:\n", " valid_actions.append('v')\n", " if (state.m + moves['<'].m, state.n + moves['<'].n) in self.all_states:\n", " valid_actions.append('<')\n", " if (state.m + moves['^'].m, state.n + moves['^'].n) in self.all_states:\n", " valid_actions.append('^')\n", " return valid_actions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A good way to understand how environment and agent interact is to write a simple agent which just chooses actions at random.\n", "Even though the agent does not learn anything at all, the interface to the environment will be the same for the Q-learning agent following next.\n", "\n", "The agent needs only 2 methods. One chooses and executes an action in the environment, the other one learns from the reward following this action and the resulting new state.\n", "Of course the learning method of the random agent doesn't do anything at all." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class RandomAgent:\n", " \"\"\"Just choosing actions at random. Learns nothing.\n", "\n", " We write this for the purpose of understanding the interface between\n", " agent and domain we later use for the real RL-agent.\n", "\n", " \"\"\"\n", "\n", " def __init__(self):\n", " self.reward_sum = 0\n", " pass\n", "\n", " def act(self, state, valid_actions):\n", " \"\"\"Take state and valid actions for that state. Return action.\"\"\"\n", " action = random.choice(valid_actions)\n", " return action\n", "\n", " def learn(self, state, action, newstate, reward):\n", " \"\"\"Never learns anything. Basically like the AFD.\"\"\"\n", " self.reward_sum += reward\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now this random agent and the Cliffworld domain class are instantiated. Their loop of interaction is exactly the same as the loop described above." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#: Just some agent randomly roaming through a \n", "#: gridlike domain with 4x12 discrete states.\n", "#: Occasionally jumping off cliffs.\n", "#: Hey, it's still a better lovestory than Twilight.\n", "\n", "random_agent = RandomAgent() #: Instantiate an agent object\n", "domain = CliffWorld(parameters) #: Create our small world\n", "\n", "def run_episode(domain, agent):\n", " state = domain.start_state\n", " while not domain.is_terminal(state):\n", " valid_actions = domain.valid_actions(state) #: Get a list of allowed moves for the current state.\n", " action = agent.act(state, valid_actions) #: Take the current state as input and compute an action.\n", " newstate = domain.newstate(state, action) #: Take the action and compute the changed state.\n", " reward = domain.reward(newstate) #: Compute reward.\n", " agent.learn(state, action, newstate, reward)#: Learn.\n", " state = newstate #: Newstate becomes the current state for next iteration.\n", " pass\n", "\n", "run_episode(domain, random_agent)\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "agent_position_log = domain.record_list[-1]['visited_states']\n", "\n", "agent_path = np.empty((4, 12), dtype=str)\n", "\n", "for state_visited in agent_position_log:\n", " if state_visited in terminal:\n", " agent_path[state_visited] = 'X'\n", " else:\n", " agent_path[state_visited] = 'O'\n", "\n", "ax = plt.axes()\n", "ax.set_title('Path of random agent\\n')\n", "figure = sns.heatmap(color,\n", " annot = agent_path,\n", " fmt = '',\n", " ax=ax,\n", " cbar=False,\n", " linewidth = 1,\n", " cmap = states_colors,\n", " square=True)\n", "figure.set(xlabel='n', ylabel='m')\n", "sns.plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Clearly just acting randomly doesn't get the agent very far or even worse, sooner or later he dies by falling off a cliff when he steps on one of the pink tiles representing terminal states.\n", "So there has to be another way.\n", "\n", "Not only reinforcement learning but learning in general utilizes just two main principles (or combinations of it).\n", "\n", "#### Model based methods\n", "\n", "Learning a model means using experience to estimate the actual mechanics of an environment. This means being able to plan, to know the possible consequences of a decision before it's executed.\n", "\n", "An important advantage of this approach is that its use of the available data/experience is very efficient. The biggest downside is that planning in general is computationally quite expensive. \n", "Model based approaches could be favourable for applications like robotics where it's difficult to collect large amounts of data but the slowness of the robot's actions leaves enough time for the necessary computations to use the model to plan a sequence of actions and its consequences.\n", "\n", "#### Value based methods\n", "\n", "The approach explored in the following is fundamentally different from using a model. Value based learning means to use experience to estimate a function which assignes a value to every possible state action pair telling the learner how good this pairing is in terms of maximizing the long term return of rewards. Even though later models of biological learning (like the work by [Rescola and Wagner](http://www.scholarpedia.org/article/Rescorla-Wagner_model)) are even closer to value based algorithms used today even classical conditioning, first discovered by Ivan Pavlov in his famous [dog experiment](https://en.wikipedia.org/wiki/Ivan_Pavlov) where a dog begins to relate some conditioned stimulus (the ringing of a bell) to a following unconditioned stimulus (food) is surprisingly similar to the Q-learning algorithm implemented in the following.\n", "\n", "## The concept of a value function\n", "\n", "The goal is to find a sequence of actions which maximizes the expected return of rewards in the gridworld. \n", "So maybe it is enough to learn from experience how \"good\" it is to take some action in a particular state.\n", "If it's possible to learn a function which expresses this by assigning a value to every state action pair it's possible to just take the highest valued action in every state and finally find the goal.\n", "\n", "But how?\n", "\n", "For every action the agent receives a reward. Sometimes there's a discount on this reward, so that that reward on the next step is favorable to a reward in the distant future.\n", "At time step $t$ the return $G_t$ is the sum of all future rewards from that time step on\n", "\n", "$$G_{t} = r_{t+1}+r_{t+2}+r_{t+3}+\\dots +r_{n}$$\n", "\n", "In the discounted case, rewards get multiplied with some $\\gamma<0$ raised to the power of the number of time steps this reward is away from the next reward. So if a reward is $k$ time steps aways it's discounted by $\\gamma^{k-1}$:\n", "\n", "$$ G_{t} = r_{t+1}+ \\gamma r_{t+2}+ \\gamma^2 r_{t+3}+ \\dots = \\sum_{k=0}^{\\infty}\\gamma^k r_{t+k+1} $$\n", "\n", "Because the future is unknown, the return has to be expressed in a different way. It is possible to understand the return as the sum of just two parts:\n", "\n", "$$G_{t}= r_{t+1} + \\gamma G_{t+1}$$\n", "\n", "The return at time stept $t$ is the immediate reward on the next time step $r_{t+1}$ plus the discounted return from this time step on.\n", "\n", "This can be used to introduce a function, $Q(s,a)$ , which assigns some value to every possible action in each state which tells the agent how good this action is in terms of maximizing the return $G_{t}$.\n", "\n", "The Q function can be split in the same manner as the return $G_{t}$. The maximum value for taking some action $a$ in state $t$ is the sum of the reward for taking that action and the maximum (discounted) value for taking the optimal action on the next time step. \n", "\n", "$$Q(s_t,a_t)= r_{t+1} + \\gamma max_{a_{t+1}} Q(s_{t+1}, a_{t+1})$$\n", "\n", "The agent has to learn $Q(s, a)$ which maps all state action pairs to a value which has to be as close as possible to the *true* value of a state action pair. If a good estimate of the true Q-values is known, the agent just has to take the highest valued action in every state.\n", "This leads to the learning rule of the Q-learning algorithm (the use of capital letters indicates actual tabular values):\n", "\n", "$$Q(S_{t}A_{t})\\gets Q(S_{t}A_{t})+\\alpha[R_{t+1}+\\gamma \\max_{A}Q(S_{t+1},A)-Q(S_{t},A_{t})]$$\n", "\n", "The agent has some estimate of the value of taking action $A_t$ in state $S_t$. Now he executes this action and receives the reward $R_{t+1}$ in return. And because of the definition above $Q(s_t,a_t)$ can be updated with the new information. The direction of the update is determined by the immediate reward the agent receives plus the (discounted) difference between the maximum of the estimate $Q(S_{t+1})$ of the state we now reached times some small step size parameter $\\alpha$.\n", "\n", "A simple intuition for this:\n", "\n", "Because the value of a state action pair $Q(S_t,A_t)$ can be estimated as the reward $R_{t+1}$ for taking that action plus the estimated value $Q(S_{t+1},A_{t+1})$ for taking the best action on the next time step, we can update our estimate of $Q(S_t,A_t)$ when we receive the actual reward $R_{t+1}$ on the next time step.\n", "\n", "If you think you'll need 60 minutes for the way from your home to your workplace but you get in a traffic jam after 10 minutes you already know you'll be late and can call your boss before actually arriving. \n", "The closer you get to your workplace, the smaller your updates to your estimated arrival will get.\n", "If you're at the first floor but notice the elevator isn't working that day, having to take the stairs does not change the time you estimated for the way from home to work anymore.\n", "\n", "This part is also called $[R_{t+1}+\\gamma \\max_{a}Q(S_{t+1},a)-Q(S_{t},A_{t})]$ or the temporal difference error.\n", "Actually this TD-error could also be called *surprise*. It's an expressions of the difference between an actual experience and the expectation preceding this experience. The intuition that the amount of surprise and learning are closely related is indeed congruent to some results of neuroscientific [research](http://link.springer.com/article/10.3758/BF03196058).\n", "\n", "Updating expectations by the difference to actual experience results in the following algorithm:\n", "\n", "```\n", "initialize values Q[states, actions] arbitrarily (as zero)\n", "begin at start state S\n", " while episode non terminal:\n", " execute action A with highest Q\n", " observe reward R' and newstate S'\n", " Q[S, A] = Q[S', A']+ alpha * [R'+ gamma max_a[Q[S', A'] - Q[S, A]]\n", " S = S'\n", " \n", "```\n", "\n", "Because the agent doesn't know anything yet, all Q-values are initialized as zero. For the cliffworld this could be an array with the size $possible\\, states \\times actions$. For the gridworld the array would consist of $(4 \\times 12) \\times 4$ tiles because the agent can go *left*, *right*, *up* or *down*.\n", "Often the number of possible states isn't known beforehand, so Python's *defaultdict* keyed by a nested tuple in the form (action (row-index, colum-index)) could be used instead of an array. Whenever there's no existing value for a state/action-key the dictionary returns 0.\n", "\n", "There's one more thing to know and that's $\\epsilon-greedy$ action selection.\n", "If someone exploits just the knowledge he already possesses and never tries anything new, he also won't be able to discover or *learn* anything new.\n", "So the agent selects her actions $\\epsilon-greedy$: In a proportion of $1-\\epsilon$ times he doesn't select the action with the highest value and just chooses one at random instead. The value of $\\epsilon$ is decreased over time as the experience grows.\n", "\n", "I think it often wouldn't be a bad idea if we all **increased** our personal $\\epsilon$ and just dared to try something new from time to time (:\n", "\n", "\n", "The python manifestation of the Q-learning agent:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class QAgent:\n", " \"\"\"Q-Learning agent.\n", "\n", " A value based, off-policy RL-agent.\n", " Uses defaultdict to return 0 for unknown state/action pairs.\n", " This has the same purpose as initializing all unknown states to zero.\n", "\n", "\n", " Args:\n", " epsilon: Parameter for epsilon-greedy action selection.\n", " epsilon_modifier: scalar value between 0 and 1,\n", " decay factor for epsilon\n", " alpha: Learning rate or stepsize. Usually <<1\n", " gamma: discount of future rewards <=1\n", "\n", " Attrs:\n", " Q: Python defaultdict with defaultvalue 0 containing\n", " the Q-values for state action pairs.\n", " Keyed by a nested state action tuple.\n", " Example:\n", " {\n", " (State(m=0, n=0), '>'): -99.94360791266038,\n", " (State(m=0, n=0), 'v'): -1.1111111111107184,\n", " (State(m=1, n=0), '>'): -1.111111111107987,\n", " (State(m=1, n=0), 'v'): -1.1111111111079839,\n", " (State(m=1, n=0), '^'): -1.111111111108079\n", " }\n", " A: Defaultdict keyed by state tuple, values\n", " are keys of executed actions. Is used to determine\n", " whether an action in a state took place in the past.\n", " If there's no memory len(A[state]) == 0\n", "\n", "\n", " \"\"\"\n", "\n", " def __init__(self, alpha, epsilon, gamma):\n", " self.epsilon = epsilon\n", " self.alpha = alpha\n", " self.gamma = gamma\n", " self.Q = defaultdict(int)\n", " self.A = defaultdict(set)\n", " self.td_list = []\n", "\n", " def act(self, state, valid_actions):\n", " \"\"\"Choose action.\n", "\n", " Take state tuple and valid actions and choose action.\n", " Action can either be random or greedy to ensure exploration.\n", " Probability of selecting random actions depends on epsilon.\n", " Smaller epsilon means less randomness.\n", "\n", " Args:\n", " state: state tuple (n,m) describes current position.\n", " valid_actions: list of indices of valid actions for a state.\n", "\n", " Returns:\n", " action: Index of selected action.\n", " Can either be chosen at random or greedily.\n", "\n", " \"\"\"\n", " if random.random() > self.epsilon:\n", " action = self.act_greedy(state, valid_actions)\n", " else:\n", " action = self.act_random(valid_actions)\n", " return action\n", "\n", " def learn(self, state, action, newstate, reward):\n", " \"\"\"Compute update of Q-function.\n", "\n", " Update Q-values when reaching new state and receiving reward.\n", " New value equals to the old value + the computed td-error times\n", " the stepsize parameter alpha.\n", " Also adds the executed action to A, to keep track of all state\n", " action pairs.\n", "\n", "\n", " Args:\n", " state: namedtuple (m, n) the state of the last timestep.\n", " action: index of executed action at the last timestep.\n", " newstate: current state reached after executing action.\n", " reward: scalar value received for reaching newstate.\n", "\n", "\n", " Returns:\n", " pass\n", "\n", " \"\"\"\n", " self.Q[state, action] = (self.Q[state, action] + self.alpha *\n", " (self.td(state, action, newstate, reward)))\n", " self.A[state].add(action)\n", " pass\n", "\n", " def act_random(self, valid_actions):\n", " \"\"\"Choose index of action from valid actions at random.\n", "\n", " Called either if epsilon greedy policy returns random\n", " or if there's no previous knowledge of action values for\n", " a state.\n", "\n", " Args:\n", " valid: List of indices of valid actions for a state.\n", "\n", " Returns:\n", " action: Index of selected action.\n", " Can either be chosen at random or greedy.\n", "\n", " \"\"\"\n", " random_action = random.choice(valid_actions)\n", " return random_action\n", "\n", " def act_greedy(self, state, valid_actions):\n", " \"\"\"Choose action with the highest Q-value.\n", "\n", " First checks whether the agent previously has executed any actions at all\n", " in the current state. If not it calls the random act_random method.\n", "\n", " Args:\n", " valid_actions: List of indices of valid actions for a state.\n", " state: namedtuple, State(n, m),\n", " representing coordinates of the current state.\n", "\n", " Returns:\n", " chosen_action: Index of selected action.\n", " Can either be chosen at random or greedy.\n", "\n", " \"\"\"\n", " if len(self.A[state]) == 0:\n", " chosen_action = self.act_random(valid_actions)\n", " else:\n", " q_s = {actions: self.Q[state, actions]\n", " for actions in self.A[state]}\n", " chosen_action = max(q_s, key=q_s.get)\n", " return chosen_action\n", "\n", " def td(self, state, action, newstate, reward):\n", " \"\"\"Compute td error to update value dict\n", "\n", " First checks wether the agent previously as executed any actions at all in\n", " the current state. If not the maximum Q-value for that state defaults to 0.\n", " It fetches Q-values for all previously exectued actions in newstate tracked in A.\n", " Next computes the key of the largest Q-value and queris the fetches Q-values.\n", " Finally computes the td error for the learning update.\n", "\n", " Args:\n", " state: state of the last timestep.\n", " action: index of selected action in that state\n", " newstate: state the agent just reached.\n", " reward: scalar value\n", "\n", " Returns:\n", " td: td error. You know, cocaine, baby.\n", "\n", " \"\"\"\n", " if len(self.A[newstate]) == 0:\n", " max_qval = 0\n", " else:\n", " q_vals = {actions: self.Q[newstate, actions]\n", " for actions in self.A[newstate]}\n", " max_qval_key = max(q_vals, key=q_vals.get)\n", " max_qval = q_vals[max_qval_key]\n", " td = reward + self.gamma * max_qval - self.Q[state, action]\n", " self.td_list.append(td)\n", " return td" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "The only thing missing to finally test our Q-Agent is a function to conduct multiple episodes.\n", "As the agent progresses, the amount of exploration by acting randomly is gradually reduced on each episode by modifying epsilon with a decay parameter. For evaluation purposes in the last episode the the agent exploits the learned value function without any exploration." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def run_experiment(domain, agent, epsilon_decay, n_episodes):\n", " for i in range(n_episodes):\n", " agent.epsilon *= epsilon_decay\n", " run_episode(domain, agent)\n", " print('Setting epsilon paramter to zero',\n", " 'to prevent random actions and evaluate learned policy.\\n')\n", " agent.epsilon = 0\n", " run_episode(domain, agent)\n", " last_reward = domain.record_list[-1]['reward']\n", " print('Trained for {0} episodes.\\n' \n", " '\\nGained reward of {1} points in the last episode.'.format(n_episodes, last_reward)) \n", " pass\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "epsilon = 0.9\n", "epsilon_decay = 0.99\n", "gamma = 0.9\n", "alpha = 0.25\n", "n_episodes = 500" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "q_agent = QAgent(alpha, epsilon, gamma)\n", "domain = CliffWorld(parameters)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "run_experiment(domain, q_agent, epsilon_decay, n_episodes)\n", "\n", "logged_data = domain.record_list\n", "Q_table = q_agent.Q\n", "A_table = q_agent.A\n", "td = q_agent.td_list" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "action_array = np.empty((4,12), dtype=str)\n", "value_array = np.empty((4,12), dtype=float)\n", "for state in domain.all_states:\n", " if len(A_table[state])==0:\n", " chosen_action = 'c'\n", " else:\n", " q_s = {actions: Q_table[state, actions] \n", " for actions in A_table[state]}\n", " chosen_action = max(q_s, key=q_s.get)\n", " max_qval = q_s[chosen_action]\n", " action_array[state] = chosen_action\n", " value_array[state] = max_qval\n", " action_array[(0,11)] = 'g'\n", " \n", "\n", " \n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following code visualizes what the agent has learned:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "figure = sns.heatmap(value_array, annot = action_array, fmt= '', square=True, cbar=False, cmap= cmap_default)\n", "ax = plt.axes()\n", "ax.set_title('Final Q-function and resulting policy\\n')\n", "figure.set(xlabel='n', ylabel='m')\n", "sns.plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is the final path of the agent. By tweaking some of the parameters it's easy to find a combination which converges to the shortest path (:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "agent_position_log = domain.record_list[-1]['visited_states']\n", "\n", "agent_path = np.empty((4, 12), dtype=str)\n", "\n", "for state_visited in agent_position_log:\n", " if state_visited in terminal:\n", " agent_path[state_visited] = 'X'\n", " else:\n", " agent_path[state_visited] = 'O'\n", "\n", "ax = plt.axes()\n", "ax.set_title('Path Q-agent final episode \\n')\n", "figure = sns.heatmap(color,\n", " annot=agent_path,\n", " fmt='',\n", " ax=ax,\n", " cbar=False,\n", " linewidth=1,\n", " cmap=states_colors,\n", " square=True)\n", "figure.set(xlabel='n', ylabel='m')\n", "sns.plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "points = [i['reward'] for i in logged_data]\n", "figure = sns.tsplot(points, color= cpal_default)\n", "figure.set(xlabel='n episodes', ylabel='reward per episode')\n", "sns.despine()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "figure = sns.tsplot(td, color= cpal_default)\n", "figure.set(xlabel='n steps', ylabel=\"amount of 'surprise' per step\")\n", "sns.despine()" ] } ], "metadata": { "anaconda-cloud": {}, "hide_input": false, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.3" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false } }, "nbformat": 4, "nbformat_minor": 1 }