Lab 1 - Problem 3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro_1",
     "locked": false,
     "solution": false
    }
   },
   "source": [
    "# Lab 1: Markov Decision Processes - Problem 3\n",
    "\n",
    "\n",
    "## Lab Instructions\n",
    "All your answers should be written in this notebook.  You shouldn't need to write or modify any other files.\n",
    "\n",
    "**You should execute every block of code to not miss any dependency.**\n",
    "\n",
    "*This project was developed by Peter Chen, Rocky Duan, Pieter Abbeel for the Berkeley Deep RL Bootcamp, August 2017. Bootcamp website with slides and lecture videos: https://sites.google.com/view/deep-rl-bootcamp/. It is adapted from CS188 project materials: http://ai.berkeley.edu/project_overview.html.*\n",
    "\n",
    "--------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np, numpy.random as nr, gym\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "np.set_printoptions(precision=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 3: Sampling-based Tabular Q-Learning\n",
    "\n",
    "So far we have implemented Value Iteration and Policy Iteration, both of which require access to an MDP's dynamics model. This requirement can sometimes be restrictive - for example, if the environment is given as a blackbox physics simulator, then we won't be able to read off the whole transition model.\n",
    "\n",
    "We can however use sampling-based Q-Learning to learn from this type of environments. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this exercise, we will learn to control a Crawler robot. Let's first try some completely random actions to see how the robot moves and familiarize ourselves with Gym environment interface again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "We can inspect the observation space and action space of this Gym Environment\n",
      "-----------------------------------------------------------------------------\n",
      "Action space: Discrete(4)\n",
      "It's a discrete space with 4 actions to take\n",
      "Each action corresponds to increasing/decreasing the angle of one of the joints\n",
      "We can also sample from this action space: 0\n",
      "Another action sample: 3\n",
      "Another action sample: 1\n",
      "Observation space: Tuple(Discrete(9), Discrete(13)) , which means it's a 9x13 grid.\n",
      "It's the discretized version of the robot's two joint angles\n"
     ]
    }
   ],
   "source": [
    "from crawler_env import CrawlingRobotEnv\n",
    "\n",
    "env = CrawlingRobotEnv()\n",
    "\n",
    "print(\"We can inspect the observation space and action space of this Gym Environment\")\n",
    "print(\"-----------------------------------------------------------------------------\")\n",
    "print(\"Action space:\", env.action_space)\n",
    "print(\"It's a discrete space with %i actions to take\" % env.action_space.n)\n",
    "print(\"Each action corresponds to increasing/decreasing the angle of one of the joints\")\n",
    "print(\"We can also sample from this action space:\", env.action_space.sample())\n",
    "print(\"Another action sample:\", env.action_space.sample())\n",
    "print(\"Another action sample:\", env.action_space.sample())\n",
    "print(\"Observation space:\", env.observation_space, \", which means it's a 9x13 grid.\")\n",
    "print(\"It's the discretized version of the robot's two joint angles\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "env = CrawlingRobotEnv(\n",
    "    render=True, # turn render mode on to visualize random motion\n",
    ")\n",
    "\n",
    "# standard procedure for interfacing with a Gym environment\n",
    "cur_state = env.reset() # reset environment and get initial state\n",
    "ret = 0.\n",
    "done = False\n",
    "i = 0\n",
    "while not done:\n",
    "    action = env.action_space.sample() # sample an action randomly\n",
    "    next_state, reward, done, info = env.step(action)\n",
    "    ret += reward\n",
    "    cur_state = next_state\n",
    "    i += 1\n",
    "    if i == 1500:\n",
    "        break # for the purpose of this visualization, let's only run for 1500 steps\n",
    "        # also note the GUI won't close automatically"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# you can close the visualization GUI with the following method \n",
    "env.close_gui()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You will see the random controller can sometimes make progress but it won't get very far. Let's implement Tabular Q-Learning with $\\epsilon$-greedy exploration to find a better policy piece by piece.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Q-values for state (0, 0): [ 0.  0.  0.  0.] which is a list of Q values for each action\n",
      "As such, the Q value of taking action 3 in state (1,2), i.e. Q((1,2), 3), can be accessed by q_vals[(1,2)][3]: 0.0\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "import random\n",
    "\n",
    "# dictionary that maps from state, s, to a numpy array of Q values [Q(s, a_1), Q(s, a_2) ... Q(s, a_n)]\n",
    "#   and everything is initialized to 0.\n",
    "q_vals = defaultdict(lambda: np.array([0. for _ in range(env.action_space.n)]))\n",
    "\n",
    "print(\"Q-values for state (0, 0): %s\" % q_vals[(0, 0)], \"which is a list of Q values for each action\")\n",
    "print(\"As such, the Q value of taking action 3 in state (1,2), i.e. Q((1,2), 3), can be accessed by q_vals[(1,2)][3]:\", q_vals[(1,2)][3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test1 passed\n",
      "Test2 passed\n"
     ]
    }
   ],
   "source": [
    "def eps_greedy(q_vals, eps, state):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "        q_vals: q value tables\n",
    "        eps: epsilon\n",
    "        state: current state\n",
    "    Outputs:\n",
    "        random action with probability of eps; argmax Q(s, .) with probability of (1-eps)\n",
    "    \"\"\"\n",
    "    # you might want to use random.random() to implement random exploration\n",
    "    #   number of actions can be read off from len(q_vals[state])\n",
    "    import random\n",
    "    # YOUR CODE HERE\n",
    "    actions = q_vals[state]\n",
    "    if random.random() > eps:\n",
    "        return np.argmax(actions)\n",
    "    i = random.randint(0,len(actions)-1)\n",
    "    return i\n",
    "    \n",
    "\n",
    "# test 1\n",
    "dummy_q = defaultdict(lambda: np.array([0. for _ in range(env.action_space.n)]))\n",
    "test_state = (0, 0)\n",
    "dummy_q[test_state][0] = 10.\n",
    "trials = 100000\n",
    "sampled_actions = [\n",
    "    int(eps_greedy(dummy_q, 0.3, test_state))\n",
    "    for _ in range(trials)\n",
    "]\n",
    "freq = np.sum(np.array(sampled_actions) == 0) / trials\n",
    "tgt_freq = 0.3 / env.action_space.n + 0.7\n",
    "if np.isclose(freq, tgt_freq, atol=1e-2):\n",
    "    print(\"Test1 passed\")\n",
    "else:\n",
    "    print(\"Test1: Expected to select 0 with frequency %.2f but got %.2f\" % (tgt_freq, freq))\n",
    "    \n",
    "# test 2\n",
    "dummy_q = defaultdict(lambda: np.array([0. for _ in range(env.action_space.n)]))\n",
    "test_state = (0, 0)\n",
    "dummy_q[test_state][2] = 10.\n",
    "trials = 100000\n",
    "sampled_actions = [\n",
    "    int(eps_greedy(dummy_q, 0.5, test_state))\n",
    "    for _ in range(trials)\n",
    "]\n",
    "freq = np.sum(np.array(sampled_actions) == 2) / trials\n",
    "tgt_freq = 0.5 / env.action_space.n + 0.5\n",
    "if np.isclose(freq, tgt_freq, atol=1e-2):\n",
    "    print(\"Test2 passed\")\n",
    "else:\n",
    "    print(\"Test2: Expected to select 2 with frequency %.2f but got %.2f\" % (tgt_freq, freq))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we will implement Q learning update. After we observe a transition $s, a, s', r$,\n",
    "\n",
    "$$\\textrm{target}(s') = R(s,a,s') + \\gamma \\max_{a'} Q_{\\theta_k}(s',a')$$\n",
    "\n",
    "\n",
    "$$Q_{k+1}(s,a) \\leftarrow (1-\\alpha) Q_k(s,a) + \\alpha \\left[ \\textrm{target}(s') \\right]$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test passed\n"
     ]
    }
   ],
   "source": [
    "def q_learning_update(gamma, alpha, q_vals, cur_state, action, next_state, reward):\n",
    "    \"\"\"\n",
    "    Inputs:\n",
    "        gamma: discount factor\n",
    "        alpha: learning rate\n",
    "        q_vals: q value table\n",
    "        cur_state: current state\n",
    "        action: action taken in current state\n",
    "        next_state: next state results from taking `action` in `cur_state`\n",
    "        reward: reward received from this transition\n",
    "    \n",
    "    Performs in-place update of q_vals table to implement one step of Q-learning\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    target = reward + gamma*np.max(q_vals[next_state])\n",
    "    q_vals[cur_state][action] -= alpha*(q_vals[cur_state][action] - target)\n",
    "\n",
    "\n",
    "# testing your q_learning_update implementation\n",
    "dummy_q = q_vals.copy()\n",
    "test_state = (0, 0)\n",
    "test_next_state = (0, 1)\n",
    "dummy_q[test_state][0] = 10.\n",
    "dummy_q[test_next_state][1] = 10.\n",
    "q_learning_update(0.9, 0.1, dummy_q, test_state, 0, test_next_state, 1.1)\n",
    "tgt = 10.01\n",
    "if np.isclose(dummy_q[test_state][0], tgt,):\n",
    "    print(\"Test passed\")\n",
    "else:\n",
    "    print(\"Q(test_state, 0) is expected to be %.2f but got %.2f\" % (tgt, dummy_q[test_state][0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Itr 0 # Average speed: 0.05\n",
      "Itr 50000 # Average speed: 3.28\n",
      "Itr 100000 # Average speed: 3.37\n",
      "Itr 150000 # Average speed: 3.37\n",
      "Itr 200000 # Average speed: 3.37\n",
      "Itr 250000 # Average speed: 3.37\n"
     ]
    }
   ],
   "source": [
    "# now with the main components tested, we can put everything together to create a complete q learning agent\n",
    "\n",
    "env = CrawlingRobotEnv() \n",
    "q_vals = defaultdict(lambda: np.array([0. for _ in range(env.action_space.n)]))\n",
    "gamma = 0.9\n",
    "alpha = 0.1\n",
    "eps = 0.5\n",
    "cur_state = env.reset()\n",
    "\n",
    "def greedy_eval():\n",
    "    \"\"\"evaluate greedy policy w.r.t current q_vals\"\"\"\n",
    "    test_env = CrawlingRobotEnv(horizon=np.inf)\n",
    "    prev_state = test_env.reset()\n",
    "    ret = 0.\n",
    "    done = False\n",
    "    H = 100\n",
    "    for i in range(H):\n",
    "        action = np.argmax(q_vals[prev_state])\n",
    "        state, reward, done, info = test_env.step(action)\n",
    "        ret += reward\n",
    "        prev_state = state\n",
    "    return ret / H\n",
    "\n",
    "for itr in range(300000):\n",
    "    # YOUR CODE HERE\n",
    "    # Hint: use eps_greedy & q_learning_update\n",
    "    action = eps_greedy(q_vals, eps, cur_state)\n",
    "    next_state, reward, done, info = env.step(action)\n",
    "    q_learning_update(gamma, alpha, q_vals, cur_state, action, next_state, reward)\n",
    "    \n",
    "    cur_state = next_state\n",
    "    \n",
    "    if itr % 50000 == 0: # evaluation\n",
    "        print(\"Itr %i # Average speed: %.2f\" % (itr, greedy_eval()))\n",
    "    \n",
    "# at the end of learning your crawler should reach a speed of >= 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After the learning is successful, we can visualize the learned robot controller. Remember we learn this just from interacting with the environment instead of peeking into the dynamics model!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "env = CrawlingRobotEnv(render=True, horizon=500)\n",
    "prev_state = env.reset()\n",
    "ret = 0.\n",
    "done = False\n",
    "while not done:\n",
    "    action = np.argmax(q_vals[prev_state])\n",
    "    state, reward, done, info = env.step(action)\n",
    "    ret += reward\n",
    "    prev_state = state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# you can close the visualization GUI with the following method \n",
    "env.close_gui()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python [default]",
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}