6_Temporal_Difference_Learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Temporal Difference Learning (TD)\n",
    "\n",
    "The Monte Carlo methods introduced in the previous chapter only learn from complete episodes. This is a major problem because it means we're throwing away information, and we can't use those algorithms for MDPs without terminal states.\n",
    "\n",
    "TD methods fix these problems by using bootstrapping, thus combining Monte Carlo with Dynamic Programming. This has the advantage that TD methods can learn online during an episode."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Observable environment\n",
    "\n",
    "This is essentially the same as in the previous chapter. We can only sample from the environment, but don't know all of its dynamics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class ObservableEnvironment:\n",
    "    def get_states(self):\n",
    "        \"\"\"\n",
    "        Return the set of possible states\n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def get_possible_actions(self, state):\n",
    "        \"\"\"\n",
    "        Returns the actions that can be taken from the given state\n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def execute_action(self, state, action):\n",
    "        \"\"\"\n",
    "        Returns the new state and the given reward. This does not have to\n",
    "        be deterministic\n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def is_terminal_state(self, state):\n",
    "        \"\"\"\n",
    "        Returns a boolean indicating whether the state is terminal\n",
    "        \"\"\"\n",
    "        pass\n",
    "    \n",
    "    def sample(self, policy, state):\n",
    "        \"\"\"\n",
    "        Follows the policy until a terminal state is reached.\n",
    "        Returns a list of states, actions, and the rewards they gave\n",
    "        \"\"\"\n",
    "        \n",
    "        result = []\n",
    "                \n",
    "        while not self.is_terminal_state(state):\n",
    "            actions = self.get_possible_actions(state)\n",
    "            ps = [policy[(state, action)] for action in actions]\n",
    "            \n",
    "            action = np.random.choice(actions, p=ps)\n",
    "            \n",
    "            new_state, reward = self.execute_action(state, action)\n",
    "            \n",
    "            result.append((state, action, reward))\n",
    "            state = new_state\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Windy GridWorld\n",
    "\n",
    "This is a standard GridWorld, except that there's also wind pushing the player upwards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "class WindyGridWorld(ObservableEnvironment):\n",
    "    def __init__(self, rewards, wind):\n",
    "        self.rewards = rewards\n",
    "        self.wind = wind\n",
    "        \n",
    "        n, m = rewards.shape\n",
    "        self.states = list(product(range(n), range(m)))\n",
    "        \n",
    "        self.max_down = n - 1\n",
    "        self.max_right = m - 1\n",
    "        \n",
    "        self.UP = \"UP\"\n",
    "        self.DOWN = \"DOWN\"\n",
    "        self.LEFT = \"LEFT\"\n",
    "        self.RIGHT = \"RIGHT\"\n",
    "        \n",
    "        self.ACTIONS = [self.UP, self.DOWN, self.LEFT, self.RIGHT]\n",
    "        \n",
    "    def get_states(self):\n",
    "        return self.states\n",
    "    \n",
    "    def get_possible_actions(self, state):\n",
    "        i, j = state\n",
    "        \n",
    "        actions = []\n",
    "        \n",
    "        if i > 0:\n",
    "            actions.append(self.UP)\n",
    "            \n",
    "        if i < self.max_down:\n",
    "            actions.append(self.DOWN)\n",
    "        \n",
    "        if j > 0:\n",
    "            actions.append(self.LEFT)\n",
    "        \n",
    "        if j < self.max_right:\n",
    "            actions.append(self.RIGHT)\n",
    "            \n",
    "        return actions\n",
    "    \n",
    "    def execute_action(self, state, action):\n",
    "        i, j = state        \n",
    "        \n",
    "        if action == self.UP:\n",
    "            i -= 1\n",
    "            \n",
    "        if action == self.DOWN:\n",
    "            i += 1\n",
    "            \n",
    "        if action == self.LEFT:\n",
    "            j -= 1\n",
    "            \n",
    "        if action == self.RIGHT:\n",
    "            j += 1\n",
    "            \n",
    "        i -= self.wind[j]\n",
    "            \n",
    "        i = max(0, min(i, self.max_down))\n",
    "        j = max(0, min(j, self.max_right))\n",
    "        \n",
    "        return (i, j), self.rewards[(i, j)] - 1\n",
    "    \n",
    "    def is_terminal_state(self, state):\n",
    "        # In this GridWorld we terminate once the reward is reached\n",
    "        \n",
    "        i, j = state\n",
    "        return self.rewards[i, j] > 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some code to visualize the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def draw_policy(agent, n, m):\n",
    "    lookup = {\n",
    "        \"UP\": u\"↑\",\n",
    "        \"DOWN\": u\"↓\",\n",
    "        \"LEFT\": u\"←\",\n",
    "        \"RIGHT\": u\"→\"\n",
    "    }\n",
    "    \n",
    "    result = np.zeros((n, m))\n",
    "    \n",
    "    for i in range(n):\n",
    "        result = \"\"\n",
    "        \n",
    "        for j in range(m):\n",
    "            state = (i, j)\n",
    "            actions = agent.env.get_possible_actions(state)      \n",
    "            num_actions = len(actions)\n",
    "\n",
    "            QA = { possible_action: agent.Q[(state, possible_action)] for possible_action in actions }\n",
    "            best_action = max(QA.items(), key=itemgetter(1))[0]\n",
    "            \n",
    "            result += lookup[best_action]\n",
    "        \n",
    "        print result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll evaluate all algorithms on the following environment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "R = np.array([\n",
    "    [0, 0, 0, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 1, 0],\n",
    "    [0, 0, 0, 0, 0, 0]\n",
    "])\n",
    "\n",
    "wind = [0, 0, 1, 1, 1, 0]\n",
    "\n",
    "env = WindyGridWorld(R, wind)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sarsa\n",
    "\n",
    "SARSA = **S**tate, **A**ction, **R**eward, Next **S**tate, Next **A**ction\n",
    "\n",
    "The value for the current state and action (SA) is updated by measuring the difference between the current guess and the sum of the observed reward (R) and the estimated value of the next state, action pair (SA).\n",
    "\n",
    "This is an on-policy algorithm because we're continually trying to estimate the action values and then always choose an $\\epsilon$-greedy policy according to those action values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from random import choice\n",
    "from operator import itemgetter\n",
    "\n",
    "class SarsaAgent:\n",
    "    def __init__(self, env, discount_factor=1., alpha=.4, epsilon=.05):\n",
    "        self.env = env\n",
    "        self.discount_factor = discount_factor\n",
    "        self.alpha = alpha\n",
    "        self.epsilon = epsilon\n",
    "        \n",
    "        self.Q = {}\n",
    "        self.policy = {}\n",
    "        \n",
    "        for state in env.get_states():\n",
    "            actions = env.get_possible_actions(state)\n",
    "            num_actions = len(actions)\n",
    "            \n",
    "            for action in actions:\n",
    "                self.Q[(state, action)] = 0.\n",
    "                self.policy[(state, action)] = 1. / num_actions\n",
    "    \n",
    "    def learn(self, num_samples, initial_state):\n",
    "        for _ in range(num_samples):\n",
    "            S = initial_state\n",
    "            A = self._choose_action(S)\n",
    "            \n",
    "            while not self.env.is_terminal_state(S):\n",
    "                S, A = self._inner_learn(S, A)\n",
    "                self._update_policy()\n",
    "                \n",
    "    def _inner_learn(self, S, A):\n",
    "        S_next, R = self.env.execute_action(S, A)\n",
    "        A_next = self._choose_action(S_next)\n",
    "\n",
    "        # SA R SA\n",
    "        self.Q[(S, A)] += self.alpha * (R + self.discount_factor * self.Q[(S_next, A_next)] - self.Q[(S, A)])\n",
    "\n",
    "        return S_next, A_next\n",
    "                \n",
    "    def _choose_action(self, S):\n",
    "        actions = self.env.get_possible_actions(S)\n",
    "        \n",
    "        ps = [self.policy[(S, A)] for A in actions]\n",
    "        A = np.random.choice(actions, p=ps)\n",
    "        \n",
    "        return A\n",
    "    \n",
    "    def _update_policy(self):\n",
    "        for state in self.env.get_states():\n",
    "            actions = self.env.get_possible_actions(state)      \n",
    "            num_actions = len(actions)\n",
    "            \n",
    "            best_action = self._find_best_action(state)\n",
    "            \n",
    "            for action in actions:\n",
    "                self.policy[(state, action)] = self.epsilon / num_actions\n",
    "                \n",
    "            self.policy[(state, best_action)] += 1 - self.epsilon\n",
    "            \n",
    "    def _find_best_action(self, state):\n",
    "        QA = { action: self.Q[(state, action)] for action in self.env.get_possible_actions(state) }\n",
    "        return max(QA.items(), key=itemgetter(1))[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "sarsa_agent = SarsaAgent(env)\n",
    "sarsa_agent.learn(num_samples=10000, initial_state=(0, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "→→→→→↓\n",
      "→→→↓↓↓\n",
      "→→→→→←\n"
     ]
    }
   ],
   "source": [
    "draw_policy(sarsa_agent, 3, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By looking at the reward matrix and the configured wind, it's easy to see that this policy is optimal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 0, 0, 0, 0],\n",
       "       [0, 0, 0, 0, 1, 0],\n",
       "       [0, 0, 0, 0, 0, 0]])"
      ]
     },
     "execution_count": 183,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 1, 1, 0]"
      ]
     },
     "execution_count": 228,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wind"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll save this policy as `best_policy` to be able to check how fast the different algorithms find that policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "best_policy = sarsa_agent.policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 258,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def evaluate_agent(RLAgent):\n",
    "    results = []\n",
    "\n",
    "    for _ in range(500):\n",
    "        other_sarsa_agent = RLAgent(env)\n",
    "\n",
    "        i = 0\n",
    "\n",
    "        while other_sarsa_agent.policy != best_policy:\n",
    "            other_sarsa_agent.learn(num_samples=1, initial_state=(0, 0))\n",
    "            i += 1\n",
    "\n",
    "        results.append(i)\n",
    "\n",
    "    return np.mean(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 259,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "181.364"
      ]
     },
     "execution_count": 259,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate_agent(SarsaAgent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q-Learning\n",
    "\n",
    "Q-learning is extremely similar to Sarsa, the only difference is that we use a different second A. In Sarsa we just follow the policy to choose the next action (on-policy). In Q-learning we just the action that's currently considered to be the best, which makes Q-learning an off-policy approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class QLearningAgent(SarsaAgent):\n",
    "    def _inner_learn(self, S, A):\n",
    "        A = self._choose_action(S)\n",
    "        S_next, R = self.env.execute_action(S, A)\n",
    "        \n",
    "        A_best = self._find_best_action(S_next)\n",
    "        self.Q[(S, A)] += self.alpha * (R + self.discount_factor * self.Q[(S_next, A_best)] - self.Q[(S, A)])\n",
    "        \n",
    "        return S_next, A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "q_agent = QLearningAgent(env)\n",
    "q_agent.learn(num_samples=1000, initial_state=(0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, this agent learns the same policy as the Sarsa Agent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "→→→→→↓\n",
      "→→→↓↓↓\n",
      "→→→→→←\n"
     ]
    }
   ],
   "source": [
    "draw_policy(q_agent, 3, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 260,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "381.91800000000001"
      ]
     },
     "execution_count": 260,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate_agent(QLearningAgent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expected Sarsa\n",
    "\n",
    "Again, this is just like Sarsa, except that we replace the second A. This time it's replaced by the expected value over all subsequent S, A pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ExpectedSarsaAgent(SarsaAgent):\n",
    "    def _inner_learn(self, S, A):\n",
    "        S_next, R = self.env.execute_action(S, A)\n",
    "        A_next = self._choose_action(S_next)\n",
    "        \n",
    "        expected_next_value = 0\n",
    "        for action in self.env.get_possible_actions(S_next):\n",
    "            p = self.policy[(S_next, action)]\n",
    "            Q = self.Q[(S_next, action)]\n",
    "            \n",
    "            expected_next_value += p * Q\n",
    "\n",
    "        # SA R E(SA)\n",
    "        self.Q[(S, A)] += self.alpha * (R + self.discount_factor * expected_next_value - self.Q[(S, A)])\n",
    "\n",
    "        return S_next, A_next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "expected_sarsa_agent = QLearningAgent(env)\n",
    "expected_sarsa_agent.learn(num_samples=12000, initial_state=(0, 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We arrive at the same policy, but it actually takes a bit longer than normal Sarsa. This can most probably be improved by choosing a more sensible $\\epsilon$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "→→→→→↓\n",
      "→→→↓↓↓\n",
      "→→→→→←\n"
     ]
    }
   ],
   "source": [
    "draw_policy(expected_sarsa_agent, 3, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 261,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "210.83199999999999"
      ]
     },
     "execution_count": 261,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate_agent(ExpectedSarsaAgent)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}