value_iteration_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "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",
    "# Value iteration\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": 2,
   "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": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial policy:\n---------------------------\n  L  |  R  |  U  |     |\n---------------------------\n  R  |     |  R  |     |\n---------------------------\n  L  |  D  |  L  |  R  |\n"
     ]
    }
   ],
   "source": [
    "# initial policy\n",
    "print(\"initial policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{(0, 1): 0.6480416555116223, (1, 2): 0.3043939946313847, (0, 0): 0.21688443480796993, (2, 3): 0.11019090057107994, (2, 0): 0.3080950288365729, (1, 3): 0, (1, 0): 0.41151492529041844, (2, 2): 0.9966689006263028, (0, 3): 0, (0, 2): 0.4927628279203332, (2, 1): 0.09850054446829104}\n---------------------------\n 0.22| 0.65| 0.49| 0.00|\n---------------------------\n 0.41| 0.00| 0.30| 0.00|\n---------------------------\n 0.31| 0.10| 1.00| 0.11|\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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this section is different from policy iteration\n",
    "# repeat until convergence\n",
    "# V[s] = max[a]{ sum[s',r] { p(s',r|s,a)[r + gamma*V[s']] } }\n",
    "iteration=0\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",
    "  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",
    "      new_v = float('-inf')\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 > new_v:\n",
    "          new_v = v\n",
    "      V[s] = new_v\n",
    "      biggest_change = max(biggest_change, np.abs(old_v - V[s]))\n",
    "\n",
    "  if biggest_change < SMALL_ENOUGH:\n",
    "    break\n",
    "\n",
    "# find a policy that leads to optimal value function\n",
    "for s in policy.keys():\n",
    "  best_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",
    "      best_a = a\n",
    "  policy[s] = best_a\n",
    "\n",
    "# our goal here is to verify that we get the same answer as with policy iteration\n",
    "print(\"values:\")\n",
    "print_values(V, grid)\n",
    "print(\"policy:\")\n",
    "print_policy(policy, grid)"
   ]
  }
 ],
 "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
}