policy_iteration_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rewards:\n---------------------------\n-0.10|-0.10|-0.10| 1.00|\n---------------------------\n-0.10| 0.00|-0.10|-1.00|\n---------------------------\n-0.10|-0.10|-0.10|-0.10|\n"
     ]
    }
   ],
   "source": [
    "# Adapted from: https://github.com/lazyprogrammer/machine_learning_examples/tree/master/rl\n",
    "import numpy as np\n",
    "from gridWorldGame import standard_grid, negative_grid,print_values, print_policy\n",
    "\n",
    "SMALL_ENOUGH = 1e-3\n",
    "GAMMA = 0.9\n",
    "ALL_POSSIBLE_ACTIONS = ('U', 'D', 'L', 'R')\n",
    "# this grid gives you a reward of -0.1\n",
    "# to find a shorter path to the goal, use negative grid\n",
    "grid = negative_grid()\n",
    "print(\"rewards:\")\n",
    "print_values(grid.rewards, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# state -> action\n",
    "# choose an action and update randomly \n",
    "policy = {}\n",
    "for s in grid.actions.keys():\n",
    "  policy[s] = np.random.choice(ALL_POSSIBLE_ACTIONS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial policy:\n---------------------------\n  U  |  R  |  U  |     |\n---------------------------\n  U  |     |  D  |     |\n---------------------------\n  R  |  R  |  D  |  U  |\n"
     ]
    }
   ],
   "source": [
    "# initial policy\n",
    "print(\"initial policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): 0.48749319742265496, (1, 2): 0.43718927627766524, (0, 0): 0.5684833222359104, (2, 3): 0.1956657169276732, (2, 0): 0.4047423989785204, (1, 3): 0, (1, 0): 0.37995839505003837, (2, 2): 0.5256129770323059, (0, 3): 0, (0, 2): 0.031259508017021376, (2, 1): 0.04153421356916698}\n---------------------------\n 0.57| 0.49| 0.03| 0.00|\n---------------------------\n 0.38| 0.00| 0.44| 0.00|\n---------------------------\n 0.40| 0.04| 0.53| 0.20|\n"
     ]
    }
   ],
   "source": [
    "# initialize V(s) - value function\n",
    "V = {}\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "  # V[s] = 0\n",
    "  if s in grid.actions:\n",
    "    V[s] = np.random.random()\n",
    "  else:\n",
    "    # terminal state\n",
    "    V[s] = 0\n",
    "\n",
    "# initial value for all states in grid\n",
    "print(V)\n",
    "print_values(V, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "values 1: \n---------------------------\n 0.57| 0.49| 0.03| 0.00|\n---------------------------\n 0.38| 0.00| 0.44| 0.00|\n---------------------------\n 0.40| 0.04| 0.53| 0.20|\npolicy 1: \n---------------------------\n  U  |  R  |  U  |     |\n---------------------------\n  U  |     |  D  |     |\n---------------------------\n  R  |  R  |  D  |  U  |\nvalues 2: \n---------------------------\n-0.99|-0.99|-0.99| 0.00|\n---------------------------\n-0.99| 0.00|-0.99| 0.00|\n---------------------------\n-0.99|-0.99|-0.99|-1.00|\npolicy 2: \n---------------------------\n  U  |  L  |  R  |     |\n---------------------------\n  U  |     |  D  |     |\n---------------------------\n  R  |  U  |  U  |  L  |\nvalues 3: \n---------------------------\n-0.99|-0.99| 1.00| 0.00|\n---------------------------\n-0.99| 0.00|-1.00| 0.00|\n---------------------------\n-0.99|-0.99|-1.00|-1.00|\npolicy 3: \n---------------------------\n  U  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  R  |  U  |  L  |  D  |\nvalues 4: \n---------------------------\n-1.00| 0.80| 1.00| 0.00|\n---------------------------\n-1.00| 0.00| 0.80| 0.00|\n---------------------------\n-1.00|-1.00|-1.00|-1.00|\npolicy 4: \n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  R  |  U  |  U  |  L  |\nvalues 5: \n---------------------------\n 0.62| 0.80| 1.00| 0.00|\n---------------------------\n 0.46| 0.00| 0.80| 0.00|\n---------------------------\n-1.00|-1.00| 0.62| 0.46|\npolicy 5: \n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  R  |  U  |  L  |\n"
     ]
    }
   ],
   "source": [
    "iteration=0\n",
    "# repeat until convergence\n",
    "# when policy does not change, it will finish\n",
    "while True:\n",
    "  iteration+=1\n",
    "  print(\"values %d: \" % iteration)\n",
    "  print_values(V, grid)\n",
    "  print(\"policy %d: \" % iteration)\n",
    "  print_policy(policy, grid)\n",
    "\n",
    "  # policy evaluation step\n",
    "  while True:\n",
    "    biggest_change = 0\n",
    "    for s in states:\n",
    "      old_v = V[s]\n",
    "\n",
    "      # V(s) only has value if it's not a terminal state\n",
    "      if s in policy:\n",
    "        a = policy[s]\n",
    "        grid.set_state(s)\n",
    "        r = grid.move(a) #reward\n",
    "        V[s] = r + GAMMA * V[grid.current_state()]\n",
    "        biggest_change = max(biggest_change, np.abs(old_v - V[s]))\n",
    "\n",
    "    if biggest_change < SMALL_ENOUGH:\n",
    "      break\n",
    "\n",
    "  # policy improvement step\n",
    "  is_policy_converged = True\n",
    "  for s in states:\n",
    "    if s in policy:\n",
    "      old_a = policy[s]\n",
    "      new_a = None\n",
    "      best_value = float('-inf')\n",
    "      # loop through all possible actions to find the best current action\n",
    "      for a in ALL_POSSIBLE_ACTIONS:\n",
    "        grid.set_state(s)\n",
    "        r = grid.move(a)\n",
    "        v = r + GAMMA * V[grid.current_state()]\n",
    "        if v > best_value:\n",
    "          best_value = v\n",
    "          new_a = a\n",
    "      policy[s] = new_a\n",
    "      if new_a != old_a:\n",
    "        is_policy_converged = False\n",
    "\n",
    "  if is_policy_converged:\n",
    "    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.62| 0.80| 1.00| 0.00|\n---------------------------\n 0.46| 0.00| 0.80| 0.00|\n---------------------------\n 0.31| 0.46| 0.62| 0.46|\nfinal policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  U  |     |\n---------------------------\n  U  |  R  |  U  |  L  |\n"
     ]
    }
   ],
   "source": [
    "print(\"final values:\")\n",
    "print_values(V, grid)\n",
    "print(\"final policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    ""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2.0
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}