Exercise+8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reinforcement Learning Example\n",
    "\n",
    "This notebook will guide you through implementing a gradient policy algorithm in Neon to train an agent to play Pong. You will learn\n",
    "- Using the Autodiff interface to perform automatic differentiation and obtain gradients given an op-tree\n",
    "- Implement a neural network that adjusts its parameters and policies with gradients to get better rewards over time directly from experiences. This model samples the expected action (moving a paddle up/down) from a distribution when no gradients are available and high uncertainty is in place. \n",
    "  \n",
    "\n",
    "## Preamble\n",
    "\n",
    "Reinforcement Learning trains an agent to take actions in an unknown environment based on experiences. Unlike supervised learning, actual labels are not always available, so RL algorithms explores the environment by interacting with actions and receives corresponding feedbacks as positive or negative rewards. \n",
    "\n",
    "In this tutorial, we will train an agent to play Pong with Stochastic Policy Gradients using [OpenAI Gym](https://gym.openai.com/) as the environment and [neon](https://neon.nervanasys.com/index.html/) as our deep learning framework. \n",
    "\n",
    "![Agent interacting with its environment](data/pong_load_trained_model.gif)\n",
    "\n",
    "As described in [Andrei Karpathy's blog](http://karpathy.github.io/2016/05/31/rl/) Policy Gradients has shown to perform better than DQN algorithms by most people including DQN Authors (https://www.youtube.com/watch?v=M8RfOCYIL8k), so we will use it to train the agent. \n",
    "\n",
    "The underlying model is a 2-layer fully connected neural network that receives image frames as inputs, explores rewards given stochastic actions (probability of moving a paddle up/down) in an unknown environment, and updates weights by weigthing rewards with a cumulative discounted rewards. The following picture depicts the main components of this learning system.  \n",
    "\n",
    "![RL algorithm](data/pong_architecture.jpg)\n",
    "\n",
    "\n",
    "## Setup\n",
    "\n",
    "This example works with Python 2.7. \n",
    "\n",
    "Your environment needs to have the following packages installed:\n",
    "- neon v1.9.0\n",
    "- OpenAI Gym for initializing Atari game environments\n",
    "- numpy for random initialization and aritmetic operations\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Model Architecture\n",
    "\n",
    "We will guide you through implementing a policy function parameterized by a neural network. We first import all the needed ingredients: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import gym\n",
    "\n",
    "from neon.backends import gen_backend\n",
    "from neon.backends import Autodiff\n",
    "import random\n",
    "import os"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also set up the backend and define the class containing our network. This consists of two layers 'W1' and 'W2' with values randomly initialized, but trainable with gradient updates. \n",
    "\n",
    "We have included functions implementing the forward and backward propagation steps. The forward step generates a policy given an a visual representation of the environment stored in variable x. The back propagation function updates the layers of the network modulating the loss function values with discounted rewards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "be = gen_backend('cpu', batch_size=128)\n",
    "class Network:\n",
    "    def __init__(self, D = 80*80, H = 200, gamma = 0.99, restore_model=False):\n",
    "        '''\n",
    "        D: number image pixels\n",
    "        H: number of hidden units in first layer of neural network\n",
    "        gamma: discount factor\n",
    "        '''\n",
    "        self.gamma = gamma\n",
    "        self.ll = {}\n",
    "        self.learning_rate = 0.00001\n",
    "\n",
    "        if restore_model and os.path.exists('model_weights.npy'):\n",
    "            self.ll['W1'] = np.load('model_weights.npy').item()['W1']            \n",
    "            self.ll['W2'] = np.load('model_weights.npy').item()['W2']\n",
    "        else:\n",
    "            self.ll['W1'] = be.array(np.random.randn(H,D) / np.sqrt(D)) #be.zeros((H,D))\n",
    "            self.ll['W2'] = be.array(np.random.randn(H,1) / np.sqrt(H)) #be.zeros((H,1))        \n",
    "        self.dW1 = be.array(np.zeros((H, D)))\n",
    "        self.dW2 = be.array(np.zeros((H, 1)))\n",
    "        \n",
    "\n",
    "    # forward propagation\n",
    "    def policy_forward(self, x):\n",
    "        # map visual input to the first hidden layer of a neural network\n",
    "        # a larger number of units will increase the capacity of the network to learn different game states\n",
    "        # different local minima in this context represents different strategies giving the same game output\n",
    "        h = be.dot(self.ll['W1'],  be.array(x))\n",
    "        h = be.sig(h)\n",
    "        dlogp = be.dot(h.transpose(), self.ll['W2'])\n",
    "\n",
    "        #probability op of moving paddle up and hidden state\n",
    "        p = be.sig(dlogp)\n",
    "\n",
    "        p_val = be.empty((1, 1))\n",
    "        h_val = be.empty((200, 1))\n",
    "        p_val[:] = p\n",
    "        h_val[:] = h\n",
    "        return p_val.get(), h_val.get(), p, h\n",
    "\n",
    "    # backward propagation\n",
    "    def policy_backward(self, losses_op, episode_dlogps, episode_rewards):\n",
    "        discounted_rewards = self.discount_rewards(episode_rewards)\n",
    "        # to reduce the variance of the gradient estimator and avoid potential vanishing problems\n",
    "        # when computing gradients: http://www.scholarpedia.org/article/Policy_gradient_methods\n",
    "        discounted_rewards -= np.mean(discounted_rewards)\n",
    "        discounted_rewards /= np.std(discounted_rewards)\n",
    "\n",
    "        episode_dlogps *= discounted_rewards  # to modulate gradients with discount factors\n",
    "        \n",
    "        # compute gradients using neon backend\n",
    "        # Note: gradients are vectors that point in the direction of the greatest\n",
    "        # rate of increase of the loss function. We use them to negatively update\n",
    "        # weight values since we are interested in decreasing loss (error) values\n",
    "        for i in range(len(losses_op)):\n",
    "            ad = Autodiff(op_tree=losses_op[i]*be.array(episode_dlogps[i]), be=be, next_error=None)\n",
    "            # compute gradients and assign them to self.dW2 and self.dW1        \n",
    "            ad.back_prop_grad([self.ll['W2'], self.ll['W1']], [self.dW2, self.dW1])                        \n",
    "            # weights update:\n",
    "            self.ll['W2'][:] = self.ll['W2'].get() - self.learning_rate * self.dW2.get()/len(losses_op)\n",
    "            self.ll['W1'][:] = self.ll['W1'].get() - self.learning_rate * self.dW1.get()/len(losses_op)\n",
    "        return\n",
    "\n",
    "    def sigmoid(self, x): \n",
    "        return 1.0 / (1.0 + np.exp(-x)) # sigmoid \"squashing\" function to interval [0,1]\n",
    "\n",
    "    def get_loss(self, y_fake, up_probability):\n",
    "        loss = y_fake-up_probability\n",
    "        return loss\n",
    "    \n",
    "    # which game_actions lead to winning a game?: given this episodic environment, we assign rewards per time-step assuming\n",
    "    # there is a stationary distribution for a policy within the episode.\n",
    "    #   reward < 0, if agent missed the ball and hence lose the game\n",
    "    #   reward > 0, if agent won the game\n",
    "    #   reward == zero, game in progress\n",
    "    # the agent receives rewards generated by the game and implements discounted reward backwards with exponential\n",
    "    # moving average. More weight is given to earlier rewards. Reset to zero when game ends.\n",
    "    def discount_rewards(self, r):\n",
    "      discounted_r = np.zeros_like(r)\n",
    "      running_add = 0\n",
    "      for t in reversed(range(0, r.size)):\n",
    "        # if reward at index t is nonzero, then there is a positive/negative reward. This also marks a game boundary\n",
    "        # for the sequence of game_actions produced by the agent\n",
    "        if r[t] != 0.0: running_add = 0.0 \n",
    "        # moving average given discount factor gamma, it assigns more weight to recent game actions\n",
    "        running_add = running_add * self.gamma + r[t]\n",
    "        discounted_r[t] = running_add\n",
    "      return discounted_r\n",
    "\n",
    "    # takes a single game frame as input and preprocesses before feeding into model\n",
    "    def prepro(self, I):\n",
    "      \"\"\" prepro 210x160x3 uint8 frame into 6400 (80x80) 1D float vector \"\"\"\n",
    "      I = I[35:195] # crop\n",
    "      I = I[::2,::2,0]              # downsample by factor of 2\n",
    "      I[I == 144] = 0               # erase background (background type 1)\n",
    "      I[I == 109] = 0               # erase background (background type 2)\n",
    "      I[I != 0] = 1                 # everything else (paddles, ball) just set to 1\n",
    "      return I.astype(np.float).ravel() #flattens\n",
    "\n",
    "    # stochastic process to choose an action (moving up) proportional to its\n",
    "    # predicted probability. If the probability of going up is higher than tossing \n",
    "    # a coin, then it's more likely to sample an up action from this stochastic process.\n",
    "    # Probablity of choosing the opposite action is (1-probability_up)\n",
    "    #    action_ == 2, moving up\n",
    "    #    action_ == 3, moving down\n",
    "    def sample_action(self, up_probability):\n",
    "        stochastic_value = np.random.uniform()\n",
    "        action = 2 if stochastic_value < up_probability else 3\n",
    "        return action\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Part of the magic behind reinforcement learning is about the possibility of optimizing objective functions under uncertainty or non-differentiable scenarios considering a stochastic process. In our case, we sample an action from the probability returned by the last layer of a neural network and consider that as a temporary (fake) label. This logic is implemented in the function __sample_action__().  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# stochastic process to choose an action (moving up) proportional to its\n",
    "# predicted probability. If such value is high, it's more\n",
    "# likely to sample an up action from this stochastic process.\n",
    "# Probablity of choosing the opposite action is (1-probability_up)\n",
    "#    action_ == 2, moving up\n",
    "#    action_ == 3, moving down\n",
    "def sample_action(up_probability):\n",
    "    stochastic_value = np.random.uniform()\n",
    "    action = 2 if stochastic_value < up_probability else 3\n",
    "    return action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initialization of variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "render = False               # to visualize agent \n",
    "restore_model = True        # to load a trained model when available\n",
    "\n",
    "random.seed(2017)\n",
    "\n",
    "D = 80 * 80                 # number of pixels in input\n",
    "H = 200                     # number of hidden layer neurons\n",
    "# Game environment\n",
    "env = gym.make(\"Pong-v0\")\n",
    "network = Network(D=D, H=H, restore_model=restore_model)\n",
    "\n",
    "# Each time step, the agent chooses an action, and the environment returns an observation and a reward.\n",
    "# The process gets started by calling reset, which returns an initial observation\n",
    "observation = env.reset()\n",
    "prev_x = None\n",
    "\n",
    "# hidden state, gradient ops, gradient values, rewards\n",
    "hs, losses_op, dlogps, rewards = [],[],[], []\n",
    "running_reward = None       # current reward\n",
    "reward_sum = 0.0            # sum rewards\n",
    "episode_number = 0\n",
    "\n",
    "game_actions = []\n",
    "game_rewards = []\n",
    "game_gradients = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Let's train!\n",
    "\n",
    "Our goal is to train an agent to win Pong against its opponent. An action consists of moving a paddle UP/DOWN, this eventually generates a positive reward (+1) if the trained agent wins a game or negative one (-1) if agent misses the ball.\n",
    "\n",
    "Before knowing the result of a game, the model gets a fake label via the stochastic process explained before. This is like tossing a coin to decide to accept the log probabilities of a neural network. An optimal set of actions will maximize the sum of rewards along the game. An import event is when the agent wins/losses a game. But what caused this outcome?. The algorithm decided to modulate the loss functions of the network with the positive or negative rewards obtained from the environment and assign more weight to earlier actions using a moving average scheme. This logic is implement in function policy_backward() of the Network class.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 0: game finished.\u001b[0;32;40m  (RL wins)\u001b[0m\n",
      "Game duration: 89 steps | Sum rewards: 88.000000 | Sum errors: 42.775948\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 21.791306\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 22.625721\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 22.683254\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 21.699604\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 22.708187\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 21.261644\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 23.007511\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 22.118530\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 44 steps | Sum rewards: -43.000000 | Sum errors: 20.159357\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.197634\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 23.198997\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 23.364492\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 43 steps | Sum rewards: -42.000000 | Sum errors: 21.129848\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 44 steps | Sum rewards: -43.000000 | Sum errors: 21.119947\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 20.951782\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 20.719749\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 22.569389\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 42 steps | Sum rewards: -41.000000 | Sum errors: 19.410311\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 20.925482\n",
      "------------------------------------\n",
      "Episode 0: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.388084\n",
      "------------------------------------\n",
      "-----------------------------------------------\n",
      "Episode 0 has finished, time to backpropagate.\n",
      "Total reward was -817.000000 Running_reward: -817.000000 Mean_loss: 248.791183\n",
      "-----------------------------------------------\n",
      "Episode 1: game finished.\u001b[0;32;40m  (RL wins)\u001b[0m\n",
      "Game duration: 83 steps | Sum rewards: 82.000000 | Sum errors: 41.371777\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 50 steps | Sum rewards: -49.000000 | Sum errors: 22.974409\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 21.172138\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 23.497990\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.871624\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 21.770929\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 23.067375\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 44 steps | Sum rewards: -43.000000 | Sum errors: 20.880787\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 50 steps | Sum rewards: -49.000000 | Sum errors: 23.854548\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 20.937683\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 22.117973\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.821718\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 22.460043\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 21.003675\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 21.019600\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 22.380682\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 20.557810\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.619881\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 22.146914\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 22.322611\n",
      "------------------------------------\n",
      "Episode 1: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 22.090237\n",
      "------------------------------------\n",
      "-----------------------------------------------\n",
      "Episode 1 has finished, time to backpropagate.\n",
      "Total reward was -835.000000 Running_reward: -817.180000 Mean_loss: 271.282959\n",
      "-----------------------------------------------\n",
      "Episode 2: game finished.\u001b[0;32;40m  (RL wins)\u001b[0m\n",
      "Game duration: 86 steps | Sum rewards: 85.000000 | Sum errors: 40.256237\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 22.178978\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 23.367764\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 23.479021\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 52 steps | Sum rewards: -1.000000 | Sum errors: 25.733480\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 23.010454\n",
      "------------------------------------\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 23.102859\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.154385\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 22.764032\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 22.714724\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 46 steps | Sum rewards: -45.000000 | Sum errors: 21.410652\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 22.616955\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 23.451794\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 50 steps | Sum rewards: -49.000000 | Sum errors: 23.393314\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 48 steps | Sum rewards: -47.000000 | Sum errors: 22.415571\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 22.468260\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 47 steps | Sum rewards: -46.000000 | Sum errors: 21.544020\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 21.450779\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 49 steps | Sum rewards: -48.000000 | Sum errors: 22.752731\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 45 steps | Sum rewards: -44.000000 | Sum errors: 21.695646\n",
      "------------------------------------\n",
      "Episode 2: game finished.\u001b[0;31;40m  (RL loses)\u001b[0m\n",
      "Game duration: 50 steps | Sum rewards: -49.000000 | Sum errors: 21.582621\n",
      "------------------------------------\n"
     ]
    }
   ],
   "source": [
    "while True:\n",
    "    cur_x = network.prepro(observation)\n",
    "    x = cur_x - prev_x if prev_x is not None else np.zeros(D)\n",
    "    prev_x = cur_x\n",
    "\n",
    "    up_probability, h_value, p, h = network.policy_forward(x)\n",
    "    action = network.sample_action(up_probability)                              \n",
    "\n",
    "    # assign a fake label, this decreases uncertainty and\n",
    "    # this is one of the beauties of Reinforcement Learning\n",
    "    y_fake = 1 if action == 2 else 0     \n",
    "    \n",
    "    # loss function gets closer to assigned label, the smaller difference\n",
    "    # between probabilities the better\n",
    "    # store gradients: derivative(log(p(x|theta)))       \n",
    "    dlogp = np.abs(y_fake - up_probability)    \n",
    "    # loss value\n",
    "    dlogps.append(dlogp) \n",
    "    # loss op\n",
    "    losses_op.append(be.absolute(y_fake - p))\n",
    "    \n",
    "    if render:\n",
    "        env.render()\n",
    "    \n",
    "    #action: \n",
    "    #    0: no movement\n",
    "    #    1: no movement\n",
    "    #    2: up\n",
    "    #    3: down\n",
    "    #    4: up\n",
    "    #    5: down\n",
    "    observation, reward, done, info = env.step(action)\n",
    "    \n",
    "    # modifying rewards to favor longer games and thus to increase number of\n",
    "    # positive rewards.\n",
    "    reward = 0.0 if reward == 0.0 else reward\n",
    "    reward = 1.0*len(game_rewards) if reward!=0.0 and len(game_rewards)>80 else reward\n",
    "    reward = -1.0*len(game_rewards) if reward!=0.0 and len(game_rewards)<=50 else reward\n",
    "\n",
    "    rewards.append(reward)\n",
    "    reward_sum += reward\n",
    "    \n",
    "    game_actions.append(action)\n",
    "    game_rewards.append(reward)\n",
    "    game_gradients.append(dlogp[0][0])\n",
    "\n",
    "    # end of a game\n",
    "    # Pong has either +1 or -1 as reward when game ends.\n",
    "    if reward != 0:  \n",
    "        message = \"Episode %d: game finished.\" % (episode_number)\n",
    "        if reward < 0:\n",
    "            message += \"\\x1b[0;31;40m  (RL loses)\\x1b[0m\"\n",
    "        elif reward > 0:\n",
    "            message += \"\\x1b[0;32;40m  (RL wins)\\x1b[0m\"\n",
    "        print(message)\n",
    "        print('Game duration: %d steps | Sum rewards: %f | Sum errors: %f' %(len(game_actions), np.sum(game_rewards), np.sum(game_gradients)))\n",
    "        print('------------------------------------')\n",
    "        game_actions = []\n",
    "        game_rewards = []\n",
    "        game_gradients = []\n",
    "        \n",
    "    # to save model\n",
    "    if (episode_number+1)%10==0:\n",
    "        np.save('model_weights.npy', network.ll)\n",
    "        \n",
    "    # end of an episode (minibatch of games)\n",
    "    if done:\n",
    "        episode_number +=1\n",
    "        dlogps = np.vstack(dlogps)\n",
    "        rewards = np.vstack(rewards)\n",
    "        \n",
    "        network.policy_backward(losses_op, dlogps, rewards)\n",
    "        mean_loss = np.sum([x * x for x in dlogps])\n",
    "        running_reward = reward_sum if running_reward is None else running_reward * 0.99 + reward_sum * 0.01\n",
    "        print('-----------------------------------------------')\n",
    "        print('Episode %d has finished, time to backpropagate.' % (episode_number - 1))\n",
    "        print('Total reward was %f Running_reward: %f Mean_loss: %f' % (reward_sum, running_reward, mean_loss))\n",
    "        print('-----------------------------------------------')\n",
    "\n",
    "        # reset game environment\n",
    "        observation = env.reset()  \n",
    "        reward_sum = 0\n",
    "        prev_x = None        \n",
    "        dlogps, rewards = [], []\n",
    "        losses_op = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's going on?\n",
    "\n",
    "## Discounted Rewards\n",
    "\n",
    "Winning or losing a game involves a sequence of actions taken during high uncertainty. The outcome of a game is a luxury event that carries enough information to truly minimizes entropy, but it is very sparse. Think about the ratio of won/lose games during early stages of training, we have quite small number of positive outcomes (won games) since the agent is still learning how to interact in this environment with random weights. \n",
    "\n",
    "Hence a supervised learning approach would not work, it will forget positive examples given the unbalanced nature of this problem. In RL, we can propagate the outcome of a game along its action sequence by considering an exponentially weighted moving average scheme. The idea is that later actions that led to a positive reward would be more important and encouraged, but former rewards would smoothly decrease back in time. Conversely, recent actions that led to a negative reward would be penalized with a large negative value. \n",
    "\n",
    "Consider the figure to illustrate this interesting concept. \n",
    "The first row shows the loss function values during multiple games, note how much uncertainty is present as we use a fake label during the game. \n",
    "Second row shows positive and negative rewards only given at the end of a game. In this example, they are proportional to the duration of a game to increase the number of positive rewards. \n",
    "Third row shows the discounted rewards, note how later rewards are more relevant for positive rewards.\n",
    "Finally, the fourth raw illustrates the new loss\n",
    "\n",
    "![RL algorithm](data/discounted_rewards.png)\n",
    "\n",
    "## Policy Gradients\n",
    "\n",
    "Consider the below visualization to understand the way policy gradients behave in reinforcement learning. We map the weights ('W2') of the neural network to 2D before and after backpropagation takes place and every point is a game. \n",
    "\n",
    "__Left plot:__ The points in green correspond to games won by the agent and thus with positive rewards. The ones in red are games in which the agent lost. Note how unbalanced is this problem as positive rewards are by definition sparse.   \n",
    "\n",
    "__Right plot:__ The arrows represent the gradient for each game towards the direction that increases its expected reward. Since the loss values of the network are weighted by their discounted rewards, the mean of the overall distribution of games has shifted towards the few gradients with positive rewards after parameter updates. Indeed, regions around green points seem to have small updates indicating the preference of a network to keep those weight values. On the contrary, regions around neagtive rewards have large gradients which means backpropagation assigns large updates in seek of better values for maximizing the loss values. This is a slow process and the reason why reinforcement learning algorithms needs lots of training time. \n",
    "\n",
    "Episode 5:\n",
    "![RL algorithm](data/gradient_update-5.png)\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}