04 - Lesson - Reinforcement Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ab8f3cf9",
   "metadata": {},
   "source": [
    "# Reinforcement Learning\n",
    "### Goal of lesson\n",
    "- Understand how Reinforcement Learning works\n",
    "- Learn about Agent and Environment\n",
    "- How it iterates and gets rewards based on action\n",
    "- How to continuously learn new things\n",
    "- Create own Reinforcement Learning from scratch"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d35fbb8a",
   "metadata": {},
   "source": [
    "### Reinforcement Learning simply explained\n",
    "- Given a set of rewards or punishments, learn what actions to take in the future\n",
    "- The second large group of Machine Learning\n",
    "\n",
    "### Environment\n",
    "<img src='img/reinforcement-learning.png' width=600 align='left'>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3a2e4b9",
   "metadata": {},
   "source": [
    "### Agent\n",
    "- The environment gives the agent a state\n",
    "- The agent action\n",
    "- The environment gives a state and reward (or punishment)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8fdfd07c",
   "metadata": {},
   "source": [
    "This is how robots are taught how to walk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "354b6d3d",
   "metadata": {},
   "source": [
    "### Markov Decision Process\n",
    "- Model for decision-making, representing states, actions, and their rewards\n",
    "- Set of states $S$\n",
    "- Set of actions $Actions(s)$\n",
    "- Transition model $P(s'|s, a)$\n",
    "- Reward function $R(s, a, s')$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6dd5d87",
   "metadata": {},
   "source": [
    "### Q-learning (one model)\n",
    "- Method for learning a function $Q(s, a)$, estimate of the value of performing action $a$ in state $s$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "680bac6f",
   "metadata": {},
   "source": [
    "### Q-learning\n",
    "- Start with $Q(s, a) = 0$ for all $s, a$\n",
    "- Update $Q$ when we take an action\n",
    "- $Q(s, a) = Q(s, a) + \\alpha($reward$ + \\gamma\\max(s', a') - Q(s, a)) = (1 - \\alpha)Q(s, a) + \\alpha($reward$ + \\gamma\\max(s', a'))$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee6fd748",
   "metadata": {},
   "source": [
    "### $\\epsilon$-Greedy Decision Making\n",
    "**Explore vs Exploit**\n",
    "- With propability $\\epsilon$ take a random move\n",
    "- Otherwise, take action $a$ with maximum $Q(s, a)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68af4493",
   "metadata": {},
   "source": [
    "### Simple task\n",
    "<img src='img/field.png' width=600 align='left'>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a21ad79d",
   "metadata": {},
   "source": [
    "- Starts at a random point\n",
    "- Move left or right\n",
    "- Avoid the red box\n",
    "- Find the green box"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6faaee68",
   "metadata": {},
   "source": [
    "![Field](img/field-3.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99174cc2",
   "metadata": {},
   "source": [
    "> #### Programming Notes:\n",
    "> - Libraries used\n",
    ">     - [**numpy**](http://numpy.org) - scientific computing with Python ([Lecture on NumPy](https://youtu.be/BpzpU8_j0-c))\n",
    ">     - [**random**](https://docs.python.org/3/library/random.html) - pseudo-random generators\n",
    "> - Functionality and concepts used\n",
    ">     - **Object-Oriented Programming (OOP)**: [Lecture on Object Oriented Programming](https://youtu.be/hbO9xo6RfDM)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "734cd18d",
   "metadata": {},
   "source": [
    "> ### Resources\n",
    "> #### What if there are more states?\n",
    "> - [Reinforcement Learning from Scratch](https://youtu.be/y4LEVVE2mV8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7870e85d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "ccf8519d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Field:\n",
    "    def __init__(self):\n",
    "        self.states = [-1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]\n",
    "        self.state = random.randrange(0, len(self.states))\n",
    "        \n",
    "    def done(self):\n",
    "        if self.states[self.state] != 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    # action: 0 => left\n",
    "    # action: 1 => right\n",
    "    def get_possible_actions(self):\n",
    "        actions = [0, 1]\n",
    "        if self.state == 0:\n",
    "            actions.remove(0)\n",
    "        if self.state == len(self.states) - 1:\n",
    "            actions.remove(1)\n",
    "        return actions\n",
    "\n",
    "    def update_next_state(self, action):\n",
    "        if action == 0:\n",
    "            if self.state == 0:\n",
    "                return self.state, -10\n",
    "            self.state -= 1\n",
    "        if action == 1:\n",
    "            if self.state == len(self.states) - 1:\n",
    "                return self.state, -10\n",
    "            self.state += 1\n",
    "        \n",
    "        reward = self.states[self.state]\n",
    "        return self.state, reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "e783005a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, False, [0, 1])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "field = Field()\n",
    "field.state, field.done(), field.get_possible_actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "60582208",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, False, [0])"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "field.update_next_state(1)\n",
    "field.state, field.done(), field.get_possible_actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "925599cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(10, -10)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "field.update_next_state(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "ff6f91fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "field = Field()\n",
    "q_table = np.zeros((len(field.states), 2))\n",
    "\n",
    "alpha = .5\n",
    "epsilon = .5\n",
    "gamma = .5\n",
    "\n",
    "for _ in range(10000):\n",
    "    field = Field()\n",
    "    while not field.done():\n",
    "        actions = field.get_possible_actions()\n",
    "        if random.uniform(0, 1) < epsilon:\n",
    "            action = random.choice(actions)\n",
    "        else:\n",
    "            action = np.argmax(q_table[field.state])\n",
    "            \n",
    "        cur_state = field.state\n",
    "        next_state, reward = field.update_next_state(action)\n",
    "        \n",
    "        q_table[cur_state, action] = (1 - alpha)*q_table[cur_state, action] + alpha*(reward + gamma*np.max(q_table[next_state]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "a0610bbc",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.      ,  0.      ],\n",
       "       [-1.      ,  0.03125 ],\n",
       "       [ 0.015625,  0.0625  ],\n",
       "       [ 0.03125 ,  0.125   ],\n",
       "       [ 0.0625  ,  0.25    ],\n",
       "       [ 0.125   ,  0.5     ],\n",
       "       [ 0.25    ,  1.      ],\n",
       "       [ 0.      ,  0.      ],\n",
       "       [ 1.      ,  0.25    ],\n",
       "       [ 0.5     ,  0.125   ],\n",
       "       [ 0.25    ,  0.      ]])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de865118",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}