3-Temporal difference/TD0_state value prediction.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "ACTION_SPACE = ('U', 'D', 'L', 'R')\n",
    "class Grid:  # Environment\n",
    "\n",
    "    def __init__(self,rows,cols,start):\n",
    "        self.rows = rows\n",
    "        self.cols = cols\n",
    "        self.i = start[0]\n",
    "        self.j = start[1]\n",
    "\n",
    "    def set(self, rewards, actions):\n",
    "\n",
    "        self.rewards = rewards\n",
    "        self.actions = actions\n",
    "\n",
    "    def set_state(self, s):\n",
    "        self.i = s[0]\n",
    "        self.j = s[1]\n",
    "\n",
    "    def current_state(self):\n",
    "        return (self.i, self.j)\n",
    "\n",
    "    def is_terminal(self, s):\n",
    "        return s not in self.actions\n",
    "    \n",
    "    def move(self, action):\n",
    "    # check if legal move first\n",
    "        if action in self.actions[(self.i, self.j)]:\n",
    "            if action == 'U':\n",
    "                self.i -= 1\n",
    "            elif action == 'D':\n",
    "                self.i += 1\n",
    "            elif action == 'R':\n",
    "                self.j += 1\n",
    "            elif action == 'L':\n",
    "                self.j -= 1\n",
    "        return self.rewards.get((self.i, self.j), 0)\n",
    "\n",
    "    def game_over(self):\n",
    "        # returns true if game is over, else false\n",
    "        # true if we are in a state where no actions are possible\n",
    "        return (self.i, self.j) not in self.actions\n",
    "\n",
    "    def all_states(self):\n",
    "        return set(self.actions.keys()) | set(self.rewards.keys())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def standard_grid():\n",
    "\n",
    "  # .  .  .  1\n",
    "  # .  x  . -1\n",
    "  # s  .  .  .\n",
    "\n",
    "    grid = Grid(3, 4, (2, 0))\n",
    "    rewards = {(0, 3): 1, (1, 3): -1}\n",
    "    actions = {\n",
    "        (0, 0): ('D', 'R'),\n",
    "        (0, 1): ('L', 'R'),\n",
    "        (0, 2): ('L', 'D', 'R'),\n",
    "        (1, 0): ('U', 'D'),\n",
    "        (1, 2): ('U', 'D', 'R'),\n",
    "        (2, 0): ('U', 'R'),\n",
    "        (2, 1): ('L', 'R'),\n",
    "        (2, 2): ('L', 'R', 'U'),\n",
    "        (2, 3): ('L', 'U'),\n",
    "        }\n",
    "    grid.set(rewards, actions)\n",
    "    return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_values(V, g):\n",
    "    for i in range(g.rows):\n",
    "        print(\"---------------------------\")\n",
    "        for j in range(g.cols):\n",
    "            v = V.get((i, j), 0)\n",
    "            if v >= 0:\n",
    "                print(\" %.2f|\" % v, end=\"\")\n",
    "            else:\n",
    "                print(\"%.2f|\" % v, end=\"\")  \n",
    "        print(\"\")\n",
    "\n",
    "\n",
    "def print_policy(P, g):\n",
    "    for i in range(g.rows):\n",
    "        print(\"---------------------------\")\n",
    "        for j in range(g.cols):\n",
    "            a = P.get((i, j), \" \")\n",
    "            print(\"  %s  |\" % a, end=\"\")\n",
    "        print(\"\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "SMALL_ENOUGH = 1e-3\n",
    "GAMMA = 0.9\n",
    "ALPHA = 0.1\n",
    "ALL_POSSIBLE_ACTIONS = ('U', 'D', 'L', 'R')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def take_action(policy,state, eps=0.1):\n",
    "    a = policy[state]\n",
    "    if np.random.random() < (1 - eps):\n",
    "        return a\n",
    "    else:\n",
    "        return np.random.choice(ALL_POSSIBLE_ACTIONS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play_game(grid, policy):\n",
    "    state = (2, 0)\n",
    "    grid.set_state(state)\n",
    "    states_and_rewards = [(state, 0)] # list of tuples of (state, reward)\n",
    "    while not grid.game_over():\n",
    "        a = take_action(policy,state,0.1)\n",
    "        reward = grid.move(a)\n",
    "        next_state = grid.current_state()\n",
    "        states_and_rewards.append((next_state, reward))\n",
    "        \n",
    "    return states_and_rewards\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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",
      "values:\n",
      "---------------------------\n",
      " 0.01| 0.05| 0.32| 0.00|\n",
      "---------------------------\n",
      " 0.01| 0.00| 0.18| 0.00|\n",
      "---------------------------\n",
      " 0.01| 0.03| 0.09|-0.83|\n",
      "policy:\n",
      "---------------------------\n",
      "  R  |  R  |  R  |     |\n",
      "---------------------------\n",
      "  U  |     |  R  |     |\n",
      "---------------------------\n",
      "  U  |  R  |  R  |  U  |\n"
     ]
    }
   ],
   "source": [
    "grid = standard_grid()\n",
    "\n",
    "# print rewards\n",
    "print(\"rewards:\")\n",
    "print_values(grid.rewards, grid)\n",
    "\n",
    "# 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",
    "\n",
    "# initialize V(s) and returns\n",
    "V = {}\n",
    "states = grid.all_states()\n",
    "for s in states:\n",
    "    V[s] = 0\n",
    "\n",
    "# repeat until convergence\n",
    "for index in range(20000):\n",
    "    # generate an episode using pi\n",
    "    states_and_rewards = play_game(grid, policy)\n",
    "    for t in range(len(states_and_rewards) - 1):\n",
    "        state, _ = states_and_rewards[t]\n",
    "        next_state, reward = states_and_rewards[t+1]\n",
    "        # we will update V(s) AS we experience the episode\n",
    "        V[state] = V[state] + ALPHA*(reward + GAMMA*V[next_state] - V[state])\n",
    "\n",
    "print(\"values:\")\n",
    "print_values(V, grid)\n",
    "print(\"policy:\")\n",
    "print_policy(policy, grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}