td_prediction.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# the temporal difference 0 method to find the optimal policy\n",
    "# only policy evaluation, not optimization\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\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",
    "ALPHA = 0.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_action(a, eps=0.1):\n",
    "  # epsilon-soft to ensure all states are visited\n",
    "  p = np.random.random()\n",
    "  if p < (1 - eps):\n",
    "    return a\n",
    "  else:\n",
    "    return np.random.choice(ALL_POSSIBLE_ACTIONS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(grid, policy):\n",
    "  # returns a list of states and corresponding rewards (not returns as in MC)\n",
    "  # start at the designated start state\n",
    "  s = (2, 0)\n",
    "  grid.set_state(s)\n",
    "  states_and_rewards = [(s, 0)] # list of tuples of (state, reward)\n",
    "  while not grid.game_over():\n",
    "    a = policy[s]\n",
    "    a = random_action(a)\n",
    "    r = grid.move(a)\n",
    "    s = grid.current_state()\n",
    "    states_and_rewards.append((s, r))\n",
    "  return states_and_rewards"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rewards:\n---------------------------\n 0.00| 0.00| 0.00| 1.00|\n---------------------------\n 0.00| 0.00| 0.00|-1.00|\n---------------------------\n 0.00| 0.00| 0.00| 0.00|\n"
     ]
    }
   ],
   "source": [
    "grid = standard_grid()\n",
    "\n",
    "# print rewards\n",
    "print(\"rewards:\")\n",
    "print_values(grid.rewards, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  R  |     |\n---------------------------\n  U  |  R  |  R  |  U  |\n"
     ]
    }
   ],
   "source": [
    "# state -> action\n",
    "policy = {\n",
    "  (2, 0): 'U',\n",
    "  (1, 0): 'U',\n",
    "  (0, 0): 'R',\n",
    "  (0, 1): 'R',\n",
    "  (0, 2): 'R',\n",
    "  (1, 2): 'R',\n",
    "  (2, 1): 'R',\n",
    "  (2, 2): 'R',\n",
    "  (2, 3): 'U',\n",
    "}\n",
    "# initial policy\n",
    "print(\"initial policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------------\n 0.00| 0.00| 0.00| 0.00|\n---------------------------\n 0.00| 0.00| 0.00| 0.00|\n---------------------------\n 0.00| 0.00| 0.00| 0.00|\n"
     ]
    }
   ],
   "source": [
    "# initialize V(s) and returns\n",
    "V = {}\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "  V[s] = 0\n",
    "  \n",
    "# initial value for all states in grid\n",
    "print_values(V, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# repeat until convergence\n",
    "for it in range(1000):\n",
    "  # generate an episode using pi\n",
    "  states_and_rewards = play_game(grid, policy)\n",
    "  # the first (s, r) tuple is the state we start in and 0\n",
    "  # (since we don't get a reward) for simply starting the game\n",
    "  # the last (s, r) tuple is the terminal state and the final reward\n",
    "  # the value for the terminal state is by definition 0, so we don't\n",
    "  # care about updating it.\n",
    "  for t in range(len(states_and_rewards) - 1):\n",
    "    s, _ = states_and_rewards[t]\n",
    "    s2, r = states_and_rewards[t+1]\n",
    "    # we will update V(s) AS we experience the episode\n",
    "    V[s] = V[s] + ALPHA*(r + GAMMA*V[s2] - V[s])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "final values:\n---------------------------\n 0.69| 0.77| 0.92| 0.00|\n---------------------------\n 0.63| 0.00|-0.94| 0.00|\n---------------------------\n 0.58|-0.18|-0.47|-0.81|\nfinal policy:\n---------------------------\n  R  |  R  |  R  |     |\n---------------------------\n  U  |     |  R  |     |\n---------------------------\n  U  |  R  |  R  |  U  |\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
}