Policy-evaluation-Policy-iteration-and-Value-Iteration.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook wants to demonstrate a few things with the grid world example in [this Reinforcement Learning lecture](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/DP.pdf):\n",
    "1. policy evaluation can converge for a random policy\n",
    "2. policy iteration and value iteration arrive at same optimised policy\n",
    "3. early stopping in policy iteration arrive at optimised policy for this example\n",
    "\n",
    "We are setting up the grid world with 2 terminal states: top left corner and bottom right corner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# first let's model the grid world and policy\n",
    "\n",
    "class Environment:\n",
    "    def __init__(self, cells_per_row = 4):\n",
    "        self.discount = 1\n",
    "        self.actions = ['up', 'down', 'left', 'right']\n",
    "        self.grid_size = cells_per_row ** 2\n",
    "        self.states = range(0, self.grid_size)\n",
    "        self._cells_per_row = cells_per_row\n",
    "        \n",
    "    def is_terminal_state(self, state):\n",
    "        return state == 0 or state == self.grid_size - 1\n",
    "\n",
    "    def tick(self, current_state, action):\n",
    "        # get next state, considering boundaries\n",
    "        if self.is_terminal_state(current_state):\n",
    "            return current_state\n",
    "        \n",
    "        if action == 'up':\n",
    "            next_state = current_state - self._cells_per_row\n",
    "            if next_state < 0:\n",
    "                return current_state\n",
    "        elif action == 'down':\n",
    "            next_state = current_state + self._cells_per_row\n",
    "            if next_state >= self.grid_size:\n",
    "                return current_state\n",
    "        elif action == 'left':\n",
    "            if current_state % self._cells_per_row == 0:\n",
    "                return current_state\n",
    "            next_state = current_state - 1\n",
    "        elif action == 'right':\n",
    "            if (current_state+1) % self._cells_per_row == 0:\n",
    "                return current_state\n",
    "            next_state = current_state + 1\n",
    "        \n",
    "        return next_state\n",
    "    \n",
    "    def reward(self, current_state):\n",
    "        if self.is_terminal_state(current_state):\n",
    "            return 0\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        \n",
    "class RandomPolicy:\n",
    "    def __init__(self, environment):\n",
    "        self.environment = environment\n",
    "    \n",
    "    def action(self, current_state):\n",
    "        if self.environment.is_terminal_state(current_state):\n",
    "            return {'stay': 1}\n",
    "        return {e: 1 / len(self.environment.actions) for e in self.environment.actions}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'stay': 1}\n",
      "{'up': 0.25, 'down': 0.25, 'left': 0.25, 'right': 0.25}\n"
     ]
    }
   ],
   "source": [
    "# tests\n",
    "e = Environment()\n",
    "assert(e.tick(0, 'up') == 0)\n",
    "assert(e.tick(0, 'left') == 0)\n",
    "assert(e.tick(8, 'left') == 8)\n",
    "assert(e.tick(11, 'right') == 11)\n",
    "assert(e.tick(14, 'down') == 14)\n",
    "assert(e.tick(5, 'up') == 1)\n",
    "assert(e.tick(5, 'down') == 9)\n",
    "assert(e.tick(5, 'left') == 4)\n",
    "assert(e.tick(5, 'right') == 6)\n",
    "\n",
    "p = RandomPolicy(e)\n",
    "print(p.action(0))\n",
    "print(p.action(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, -14.0, -20.0, -22.0, -14.0, -18.0, -20.0, -20.0, -20.0, -20.0, -18.0, -14.0, -22.0, -20.0, -14.0, 0]\n"
     ]
    }
   ],
   "source": [
    "# 1. policy evaluation should converge\n",
    "e = Environment()\n",
    "p = RandomPolicy(e)\n",
    "\n",
    "\n",
    "def evaluate_policy(policy, iterations):\n",
    "    values = [0] * e.grid_size    \n",
    "    for i in range(iterations):\n",
    "        new_values = [0] * e.grid_size\n",
    "        for state in e.states:\n",
    "            for (action, probability) in policy.action(state).items():\n",
    "                next_state = e.tick(state, action)\n",
    "                next_state_value = values[next_state]\n",
    "                reward = e.reward(state)\n",
    "                new_values[state] += probability * (reward + next_state_value)\n",
    "        values = new_values\n",
    "    return values\n",
    "\n",
    "print([round(e, 0) for e in evaluate_policy(p, 100)]) # this should match values from the slides\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image.png](images/RL-lecture-3/img1.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2. policy iteration using converged values (no early stopping)\n",
    "class GreedyPolicy:\n",
    "    def __init__(self, environment, random_policy_values):\n",
    "        self.environment = environment\n",
    "        self.random_policy_values = random_policy_values\n",
    "    \n",
    "    def action(self, state):\n",
    "        if self.environment.is_terminal_state(state):\n",
    "            return {'stay':1}\n",
    "        else:\n",
    "            # take the action that yield most value increase\n",
    "            choices = {}\n",
    "            for action in self.environment.actions:\n",
    "                next_state = self.environment.tick(state, action)\n",
    "                incremental_value = self.random_policy_values[next_state] - self.random_policy_values[state]\n",
    "                choices[action] = incremental_value\n",
    "            choices_sorted = sorted(choices, key=choices.get, reverse=True)\n",
    "            # cheating here, we know most actions the best policy can take is 2\n",
    "            fst = choices_sorted[0]\n",
    "            snd = choices_sorted[1]\n",
    "            if round(choices[fst], 2) == round(choices[snd], 2):\n",
    "                return {fst: 0.5, snd: 0.5}\n",
    "            return {choices_sorted[0]: 1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'stay': 1}\n",
      "{'left': 1}\n",
      "{'left': 1}\n",
      "{'down': 0.5, 'left': 0.5}\n",
      "{'up': 1}\n",
      "{'left': 0.5, 'up': 0.5}\n",
      "{'down': 0.5, 'left': 0.5}\n",
      "{'down': 1}\n",
      "{'up': 1}\n",
      "{'up': 0.5, 'right': 0.5}\n",
      "{'down': 0.5, 'right': 0.5}\n",
      "{'down': 1}\n",
      "{'up': 0.5, 'right': 0.5}\n",
      "{'right': 1}\n",
      "{'right': 1}\n",
      "{'stay': 1}\n"
     ]
    }
   ],
   "source": [
    "values = evaluate_policy(p, 100)\n",
    "gp = GreedyPolicy(e, values)\n",
    "for s in e.states:\n",
    "    print(gp.action(s)) # this should match with slides"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image.png](images/RL-lecture-3/img2.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'stay': 1}\n",
      "{'left': 1}\n",
      "{'left': 1}\n",
      "{'down': 0.5, 'left': 0.5}\n",
      "{'up': 1}\n",
      "{'up': 0.5, 'left': 0.5}\n",
      "{'down': 0.5, 'left': 0.5}\n",
      "{'down': 1}\n",
      "{'up': 1}\n",
      "{'up': 0.5, 'right': 0.5}\n",
      "{'down': 0.5, 'right': 0.5}\n",
      "{'down': 1}\n",
      "{'up': 0.5, 'right': 0.5}\n",
      "{'right': 1}\n",
      "{'right': 1}\n",
      "{'stay': 1}\n"
     ]
    }
   ],
   "source": [
    "# now what if we stop early in random policy evaluation? \n",
    "# in this example stop after iteration 3 would give you optimised policy\n",
    "values = evaluate_policy(p, 3)\n",
    "gp_earlystopping = GreedyPolicy(e, values)\n",
    "for s in e.states:\n",
    "    print(gp_earlystopping.action(s)) # this should be same policy with previous cell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, -1, -2, -3.0, -1, -2.0, -3.0, -2, -2, -3.0, -2.0, -1, -3.0, -2, -1, 0]\n"
     ]
    }
   ],
   "source": [
    "# let's see what is the value for the final optimised policy\n",
    "print([round(e, 0) for e in evaluate_policy(gp, 100)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=== iteration 0\n",
      "values:  [0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0]\n",
      "known states:  [0, 15, 1, 4, 11, 14]\n",
      "=== iteration 1\n",
      "values:  [0, -1, -2, 0, -1, -2, 0, -2, -2, 0, -2, -1, 0, -2, -1, 0]\n",
      "known states:  [0, 15, 1, 4, 11, 14, 2, 5, 7, 8, 10, 13]\n",
      "=== iteration 2\n",
      "values:  [0, -1, -2, -3, -1, -2, -3, -2, -2, -3, -2, -1, -3, -2, -1, 0]\n",
      "known states:  [0, 15, 1, 4, 11, 14, 2, 5, 7, 8, 10, 13, 3, 6, 9, 12]\n",
      "==========\n",
      "final values\n",
      "[0, -1, -2, -3, -1, -2, -3, -2, -2, -3, -2, -1, -3, -2, -1, 0]\n"
     ]
    }
   ],
   "source": [
    "# 3. value iteration should give same optimised policy, with less iterations\n",
    "e = Environment()\n",
    "values = [0] * e.grid_size\n",
    "known_states = [0, e.grid_size-1]\n",
    "\n",
    "\n",
    "def iteration(values, known_states):\n",
    "    new_values = values.copy()\n",
    "    new_known_states = known_states.copy()\n",
    "    for state in e.states:\n",
    "        if e.is_terminal_state(state) or state in known_states:\n",
    "            continue\n",
    "        v = values[state]\n",
    "        max_reward = float('-inf')\n",
    "        updatable = False\n",
    "        for action in e.actions:\n",
    "            next_state = e.tick(state, action)\n",
    "            if next_state in known_states:\n",
    "                updatable = True\n",
    "                reward = e.reward(state)\n",
    "                next_state_value = values[next_state]\n",
    "                total = reward + e.discount * next_state_value\n",
    "                if total >= max_reward:\n",
    "                    max_reward = total\n",
    "        if updatable:\n",
    "            new_values[state] = max_reward\n",
    "            new_known_states.append(state)\n",
    "    return new_values, new_known_states\n",
    "\n",
    "i = 0\n",
    "while len(known_states) < e.grid_size:\n",
    "    values, known_states = iteration(values, known_states)\n",
    "    print(\"=== iteration\", i)\n",
    "    i += 1\n",
    "    print(\"values: \", values)\n",
    "    print(\"known states: \", known_states)\n",
    "\n",
    "print(\"=\" * 10)\n",
    "print(\"final values\")\n",
    "print(values) # this should match previous cell's result      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.7.1rc1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}