Policy Based Methods.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# Policy Based Methods\n",
    "\n",
    "\n",
    "- Read the most famous [blog post](http://karpathy.github.io/2016/05/31/rl/) on policy gradient methods.\n",
    "- Implement a policy gradient method to win at Pong in this [Medium post](https://medium.com/@dhruvp/how-to-write-a-neural-network-to-play-pong-from-scratch-956b57d4f6e0).\n",
    "- Many challanging problems can be found in [OpenAI's Request for Research](https://openai.com/blog/requests-for-research-2/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "from IPython.lib.display import YouTubeVideo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Why Policy-Based Methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('ToS8vXGdODE')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Introduction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('mMnhi8yzwKk')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Policy Function Approximation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('v8tGjlc2aG4')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# Black-Box Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Hill Climbing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('5E86a0OyVyI')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('0XzzqIXyax0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "The goal of the agent is to find the value of the policy network weights $\\theta$ that maximizes expected return, which has been denoted by $J$.\n",
    "\n",
    "In the hill climbing algorithm, the values of $\\theta$ are evaluated according to how much return $G$ is collected in a single episode. Note that due to randomness in the environment (and the policy, if it is stochastic), it is highly likely that if we collect a second episode with the same values for $\\theta$, we'll likely get a different value for the return $G$. Because of this, the (sampled) return $G$ is not a perfect estimate for the expected return $J$, but it often turns out to be good enough in practice.\n",
    "\n",
    "## stochastic policy search\n",
    "\n",
    "Despite the fact that we have no idea what that function $J(\\theta)$ looks like, the _hill climbing_ algorithm helps us determine the value of $\\theta$ that maximizes it. There are some improvements we can make to the hill climbing algorithm!\n",
    "\n",
    "We refer to the general class of approaches that find $\\displaystyle\\arg\\max_\\theta J(\\theta)$ through randomly perturbing the most recent best estimate as **stochastic policy search**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('QicxmyE5vTo')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Cross-Entropy Method (CEM)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "YouTubeVideo('2poDljPvY58')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "Other very popular black-box optimization techniques are [evolution strategies](https://blog.openai.com/evolution-strategies). A well-written implementation is [here](https://github.com/alirezamika/evostra). To see how to apply it to an OpenAI Gym (BipedalWalker) environment, check out [this repository](https://github.com/alirezamika/bipedal-es).\n",
    "\n",
    "To see one way to structure the analysis, check out [this blog post](http://kvfrans.com/simple-algoritms-for-solving-cartpole/), along with the [accompanying code](https://github.com/kvfrans/openai-cartpole). For instance, you will likely find that _hill climbing_ is very unstable, where the number of episodes that it takes to solve `CartPole-v0` varies greatly with the random seed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "---\n",
    "\n",
    "## Hill Climbing with Adaptive Noise Scaling\n",
    "\n",
    "We will train hill climbing with adaptive noise scaling with OpenAI Gym's Cartpole environment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Import the Necessary Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "import gym\n",
    "import math\n",
    "import numpy as np\n",
    "from collections import deque\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "import torch\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "from torch.autograd import Variable\n",
    "\n",
    "from pyvirtualdisplay import Display\n",
    "display = Display(visible=0, size=(1400, 900))\n",
    "display.start()\n",
    "\n",
    "is_ipython = 'inline' in plt.get_backend()\n",
    "if is_ipython:\n",
    "    from IPython import display\n",
    "\n",
    "plt.ion()\n",
    "\n",
    "device = torch.device('cuda:0' if torch.cuda.is_available() else 'cpu')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Define the Policy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "env = gym.make('CartPole-v0')\n",
    "print('observation space:', env.observation_space)\n",
    "print('action space:', env.action_space)\n",
    "\n",
    "class Policy():\n",
    "    def __init__(self, s_size=4, a_size=2):\n",
    "        self.w = 1e-4*np.random.rand(s_size, a_size) # weights for simple linear policy: state_space x action_space\n",
    "        \n",
    "    def forward(self, state):\n",
    "        x = np.dot(state, self.w)\n",
    "        return np.exp(x)/sum(np.exp(x))\n",
    "    \n",
    "    def act(self, state):\n",
    "        probs = self.forward(state)\n",
    "        # action = np.random.choice(2, p=probs) # option 1: stochastic policy\n",
    "        action = np.argmax(probs)               # option 2: deterministic policy\n",
    "        return action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Train the Agent with Stochastic Policy Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     5
    ],
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "env.seed(0)\n",
    "np.random.seed(0)\n",
    "\n",
    "policy = Policy()\n",
    "\n",
    "def hill_climbing(n_episodes=1000, max_t=1000, gamma=1.0, print_every=10, noise_scale=1e-2):\n",
    "    '''\n",
    "    Implementation of hill climbing with adaptive noise scaling.\n",
    "        \n",
    "    Params\n",
    "    ======\n",
    "        n_episodes (int): maximum number of training episodes\n",
    "        max_t (int): maximum number of timesteps per episode\n",
    "        gamma (float): discount rate\n",
    "        print_every (int): how often to print average score (over last 100 episodes)\n",
    "        noise_scale (float): standard deviation of additive noise\n",
    "    '''\n",
    "    scores_deque = deque(maxlen=100)\n",
    "    scores = []\n",
    "    best_R = -np.Inf\n",
    "    best_w = policy.w\n",
    "    for i_episode in range(1, n_episodes+1):\n",
    "        rewards = []\n",
    "        state = env.reset()\n",
    "        for t in range(max_t):\n",
    "            action = policy.act(state)\n",
    "            state, reward, done, _ = env.step(action)\n",
    "            rewards.append(reward)\n",
    "            if done:\n",
    "                break \n",
    "        scores_deque.append(sum(rewards))\n",
    "        scores.append(sum(rewards))\n",
    "\n",
    "        discounts = [gamma**i for i in range(len(rewards)+1)]\n",
    "        R = sum([a*b for a,b in zip(discounts, rewards)])\n",
    "\n",
    "        if R >= best_R: # found better weights\n",
    "            best_R = R\n",
    "            best_w = policy.w\n",
    "            noise_scale = max(1e-3, noise_scale / 2)\n",
    "            policy.w += noise_scale * np.random.rand(*policy.w.shape) \n",
    "        else:          # did not find better weights\n",
    "            noise_scale = min(2, noise_scale * 2)\n",
    "            policy.w = best_w + noise_scale * np.random.rand(*policy.w.shape)\n",
    "\n",
    "        if i_episode % print_every == 0:\n",
    "            print('Episode {}\\tAverage Score: {:.2f}'.format(i_episode, np.mean(scores_deque)))\n",
    "        if np.mean(scores_deque)>=195.0:\n",
    "            print('Environment solved in {:d} episodes!\\tAverage Score: {:.2f}'.format(i_episode, np.mean(scores_deque)))\n",
    "            policy.w = best_w\n",
    "            break\n",
    "    return scores\n",
    "\n",
    "scores = hill_climbing()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Plot the Scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111)\n",
    "plt.plot(np.arange(1, len(scores)+1), scores)\n",
    "plt.ylabel('Score')\n",
    "plt.xlabel('Episode #')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Watch a Smart Agent!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     2
    ],
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "state = env.reset()\n",
    "img = plt.imshow(env.render(mode='rgb_array'))\n",
    "for t in range(4000):\n",
    "    action = policy.act(state)\n",
    "    img.set_data(env.render(mode='rgb_array')) \n",
    "    plt.axis('off')\n",
    "    display.display(plt.gcf())\n",
    "    display.clear_output(wait=True)\n",
    "    state, reward, done, _ = env.step(action)\n",
    "    if done:\n",
    "        break "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "---\n",
    "\n",
    "## Cross-Entropy Method\n",
    "\n",
    "We will train a Cross-Entropy Method with OpenAI Gym's MountainCarContinuous environment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Instantiate the Environment and Agent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ENVIRONMENT = 'MountainCarContinuous-v0'\n",
    "MODEL_FILE = './models/cem-mountain-car-continuous.pt'\n",
    "RANDOM_SEED = 101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     10
    ],
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "env = gym.make(ENVIRONMENT)\n",
    "\n",
    "env.seed(RANDOM_SEED)\n",
    "np.random.seed(RANDOM_SEED)\n",
    "\n",
    "print('observation space:', env.observation_space)\n",
    "print('action space:', env.action_space)\n",
    "print('\\t- low:', env.action_space.low)\n",
    "print('\\t- high:', env.action_space.high)\n",
    "\n",
    "class Agent(nn.Module):\n",
    "    def __init__(self, env, h_size=16):\n",
    "        super(Agent, self).__init__()\n",
    "        self.env = env\n",
    "        # state, hidden layer, action sizes\n",
    "        self.s_size = env.observation_space.shape[0]\n",
    "        self.h_size = h_size\n",
    "        self.a_size = env.action_space.shape[0]\n",
    "        # define layers\n",
    "        self.fc1 = nn.Linear(self.s_size, self.h_size)\n",
    "        self.fc2 = nn.Linear(self.h_size, self.a_size)\n",
    "        \n",
    "    def set_weights(self, weights):\n",
    "        s_size = self.s_size\n",
    "        h_size = self.h_size\n",
    "        a_size = self.a_size\n",
    "        # separate the weights for each layer\n",
    "        fc1_end = (s_size*h_size)+h_size\n",
    "        fc1_W = torch.from_numpy(weights[:s_size*h_size].reshape(s_size, h_size))\n",
    "        fc1_b = torch.from_numpy(weights[s_size*h_size:fc1_end])\n",
    "        fc2_W = torch.from_numpy(weights[fc1_end:fc1_end+(h_size*a_size)].reshape(h_size, a_size))\n",
    "        fc2_b = torch.from_numpy(weights[fc1_end+(h_size*a_size):])\n",
    "        # set the weights for each layer\n",
    "        self.fc1.weight.data.copy_(fc1_W.view_as(self.fc1.weight.data))\n",
    "        self.fc1.bias.data.copy_(fc1_b.view_as(self.fc1.bias.data))\n",
    "        self.fc2.weight.data.copy_(fc2_W.view_as(self.fc2.weight.data))\n",
    "        self.fc2.bias.data.copy_(fc2_b.view_as(self.fc2.bias.data))\n",
    "    \n",
    "    def get_weights_dim(self):\n",
    "        return (self.s_size+1)*self.h_size + (self.h_size+1)*self.a_size\n",
    "        \n",
    "    def forward(self, x):\n",
    "        x = F.relu(self.fc1(x))\n",
    "        x = torch.tanh(self.fc2(x))\n",
    "        return x.cpu().data\n",
    "        \n",
    "    def evaluate(self, weights, gamma=1.0, max_t=5000):\n",
    "        self.set_weights(weights)\n",
    "        episode_return = 0.0\n",
    "        state = self.env.reset()\n",
    "        for t in range(max_t):\n",
    "            state = torch.from_numpy(state).float().to(device)\n",
    "            action = self.forward(state)\n",
    "            state, reward, done, _ = self.env.step(action)\n",
    "            episode_return += reward * math.pow(gamma, t)\n",
    "            if done:\n",
    "                break\n",
    "        return episode_return\n",
    "    \n",
    "agent = Agent(env).to(device)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Train the Agent with a Cross-Entropy Method\n",
    "\n",
    "Run the code cell below to train the agent from scratch.  Alternatively, you can skip to the next code cell to load the pre-trained weights from file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     0
    ],
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "def cem(n_iterations=500, max_t=1000, gamma=1.0, print_every=10, pop_size=50, elite_frac=0.2, sigma=0.5):\n",
    "    '''\n",
    "    PyTorch implementation of a cross-entropy method.\n",
    "        \n",
    "    Params\n",
    "    ======\n",
    "        n_iterations (int): maximum number of training iterations\n",
    "        max_t (int): maximum number of timesteps per episode\n",
    "        gamma (float): discount rate\n",
    "        print_every (int): how often to print average score (over last 100 episodes)\n",
    "        pop_size (int): size of population at each iteration\n",
    "        elite_frac (float): percentage of top performers to use in update\n",
    "        sigma (float): standard deviation of additive noise\n",
    "    '''\n",
    "    n_elite=int(pop_size*elite_frac)\n",
    "\n",
    "    scores_deque = deque(maxlen=100)\n",
    "    scores = []\n",
    "    best_weight = sigma*np.random.randn(agent.get_weights_dim())\n",
    "\n",
    "    for i_iteration in range(1, n_iterations+1):\n",
    "        weights_pop = [best_weight + (sigma*np.random.randn(agent.get_weights_dim())) for i in range(pop_size)]\n",
    "        rewards = np.array([agent.evaluate(weights, gamma, max_t) for weights in weights_pop])\n",
    "\n",
    "        elite_idxs = rewards.argsort()[-n_elite:]\n",
    "        elite_weights = [weights_pop[i] for i in elite_idxs]\n",
    "        best_weight = np.array(elite_weights).mean(axis=0)\n",
    "\n",
    "        reward = agent.evaluate(best_weight, gamma=1.0)\n",
    "        scores_deque.append(reward)\n",
    "        scores.append(reward)\n",
    "        \n",
    "        if i_iteration % print_every == 0:\n",
    "            print('Episode {}\\tAverage Score: {:.2f}'.format(i_iteration, np.mean(scores_deque)))\n",
    "\n",
    "        if np.mean(scores_deque)>=90.0:\n",
    "            print('\\nEnvironment solved in {:d} iterations!\\tAverage Score: {:.2f}'.format(i_iteration, np.mean(scores_deque)))\n",
    "            torch.save(agent.state_dict(), MODEL_FILE)\n",
    "            break\n",
    "    return scores\n",
    "\n",
    "scores = cem()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Plot the Scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "fig = plt.figure()\n",
    "ax = fig.add_subplot(111)\n",
    "plt.plot(np.arange(1, len(scores)+1), scores)\n",
    "plt.ylabel('Score')\n",
    "plt.xlabel('Episode #')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Watch a Smart Agent!\n",
    "\n",
    "Load the trained weights from file to watch a smart agent!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [
     5
    ],
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "map_location = (lambda storage, loc: storage.cuda()) if torch.cuda.is_available() else 'cpu'\n",
    "agent.load_state_dict(torch.load(MODEL_FILE, map_location=map_location))\n",
    "\n",
    "state = env.reset()\n",
    "img = plt.imshow(env.render(mode='rgb_array'))\n",
    "while True:\n",
    "    state = torch.from_numpy(state).float().to(device)\n",
    "    with torch.no_grad():\n",
    "        action = agent(state)\n",
    "    img.set_data(env.render(mode='rgb_array')) \n",
    "    plt.axis('off')\n",
    "    display.display(plt.gcf())\n",
    "    display.clear_output(wait=True)\n",
    "    next_state, reward, done, _ = env.step(action)\n",
    "    state = next_state\n",
    "    if done:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "---\n",
    "\n",
    "Next: [Policy Gradient Methods](./Policy%20Gradient%20Methods.ipynb)"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}