<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# \"Reinforcement Learning\", <NAME>olls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each timestep $t$:\n",
    "- receive observation $x_t$, from the environment\n",
    "- choose action $a_t$\n",
    "- receive reward $r_{t+1}$\n",
    "- see observation $x_{t+1}$\n",
    "\n",
    "state is Markov, ie:\n",
    "$$\n",
    "P(x_{t+1} \\mid x_t) = P(x_{t+1} \\mid x_1, x_2, \\dots, x_t)\n",
    "$$\n",
    "\n",
    "Therefore we can model as a Markov decision process (MDP).\n",
    "\n",
    "Means the state captures all you need to know about the system\n",
    "- in contrast, if the state did not include the cart's velocity, then it wouldn't be Markov"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dont want to choose deterministically, since we want to explore different ways of playing\n",
    "- therefore, choose our actions using a conditional probability distribution $P(a \\mid x)$\n",
    "\n",
    "Must satisfy $P(a_L \\mid x) + P(a_R \\mid x) = 1$ for all observations, ie agent must choose exactly one of $a_L$ or $a_R$.\n",
    "\n",
    "__Definitions:__\n",
    "\n",
    "- $\\pi(a \\mid x; \\theta) = P(a \\mid x; \\theta)$ is the _policy_\n",
    "- $\\tau$ is the _trajectory_: $(x_0, a_0, r_1, x_1, a_1, r_2, \\dots, x_{T-1}, a_{T-1}, r_T, x_T)$\n",
    "- $R_\\tau$ is the _total reward_ of the trajectory: $r_1 + r_2 + \\dots + r_T$\n",
    "- the _expected reward_ for a given policy $\\pi$ is $\\mathbb{E}_\\tau[R_\\tau \\mid \\pi]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cross-entropy method\n",
    "\n",
    "Draw $\\theta$ from a Gaussian distribution, with mean $\\mathbf{\\mu} = \\{ \\mu_1, \\mu_2, \\dots, \\mu_K\\}$, and axis-aligned variance, $\\mathbf{\\sigma} = \\{\\sigma_1, \\sigma_2, \\dots, \\sigma_K\\}$.\n",
    "\n",
    "- draw $N$ samples of $\\theta$\n",
    "- sample reward for each sample\n",
    "- update Gaussian distribution:\n",
    "   - new $\\mu$ is the sample mean of the retained $\\theta$ samples\n",
    "   - new $\\sigma$ is the sample variance of the retained $\\theta$ samples"
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}<commit_msg>reinf learning in pytorch<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# \"Reinforcement Learning\", CG Nicholls$\\def\\E{\\mathbb{E}}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each timestep $t$:\n",
    "- receive observation $x_t$, from the environment\n",
    "- choose action $a_t$\n",
    "- receive reward $r_{t+1}$\n",
    "- see observation $x_{t+1}$\n",
    "\n",
    "state is Markov, ie:\n",
    "$$\n",
    "P(x_{t+1} \\mid x_t) = P(x_{t+1} \\mid x_1, x_2, \\dots, x_t)\n",
    "$$\n",
    "\n",
    "Therefore we can model as a Markov decision process (MDP).\n",
    "\n",
    "Means the state captures all you need to know about the system\n",
    "- in contrast, if the state did not include the cart's velocity, then it wouldn't be Markov"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dont want to choose deterministically, since we want to explore different ways of playing\n",
    "- therefore, choose our actions using a conditional probability distribution $P(a \\mid x)$\n",
    "\n",
    "Must satisfy $P(a_L \\mid x) + P(a_R \\mid x) = 1$ for all observations, ie agent must choose exactly one of $a_L$ or $a_R$.\n",
    "\n",
    "__Definitions:__\n",
    "\n",
    "- $\\pi(a \\mid x; \\theta) = P(a \\mid x; \\theta)$ is the _policy_\n",
    "- $\\tau$ is the _trajectory_: $(x_0, a_0, r_1, x_1, a_1, r_2, \\dots, x_{T-1}, a_{T-1}, r_T, x_T)$\n",
    "- $R_\\tau$ is the _total reward_ of the trajectory: $r_1 + r_2 + \\dots + r_T$\n",
    "- the _expected reward_ for a given policy $\\pi$ is $\\mathbb{E}_\\tau[R_\\tau \\mid \\pi]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cross-entropy method\n",
    "\n",
    "Draw $\\theta$ from a Gaussian distribution, with mean $\\mathbf{\\mu} = \\{ \\mu_1, \\mu_2, \\dots, \\mu_K\\}$, and axis-aligned variance, $\\mathbf{\\sigma} = \\{\\sigma_1, \\sigma_2, \\dots, \\sigma_K\\}$.\n",
    "\n",
    "- draw $N$ samples of $\\theta$\n",
    "- sample reward for each sample\n",
    "- update Gaussian distribution:\n",
    "   - new $\\mu$ is the sample mean of the retained $\\theta$ samples\n",
    "   - new $\\sigma$ is the sample variance of the retained $\\theta$ samples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The policy gradient method\n",
    "\n",
    "Continued to use parametrised policy:\n",
    "\n",
    "$$\n",
    "\\pi(a \\mid x; \\theta)\n",
    "$$\n",
    "\n",
    "- use gradient ascent to optimize $\\theta$ to maximise the expected total reward\n",
    "- at each step, compute $\\nabla_\\theta \\E_\\tau[R_\\tau]$, and then update the parameter vector $\\theta$ by the learning rate, $\\alpha > 0$:\n",
    "\n",
    "$$\n",
    "\\theta \\leftarrow \\theta + \\alpha \\nabla_\\theta \\E_\\tau[R_\\tau]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computing the gradient\n",
    "\n",
    "Expected total reward for following the policy $\\pi(a \\mid x; \\theta)$ is obtained by marginalizing over all possible trajectories $\\tau$:\n",
    "\n",
    "$$\n",
    "\\E_\\tau[R_\\tau \\mid \\pi; \\theta] =\n",
    "\\int_\\tau P(\\tau \\mid \\pi; \\theta)R_\\tau\\, d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take the derivative with respect to $\\theta$:\n",
    "\n",
    "$$\n",
    "\\nabla_\\theta \\E_\\tau[R_\\tau \\mid \\pi; \\theta] =\n",
    "\\nabla_\\theta \\int_\\tau\n",
    "P(\\tau \\mid \\pi; \\theta)R_\\tau \\, d\\tau \\\\\n",
    "= \\int_\\tau \\nabla_\\theta P(\\tau \\mid \\pi; \\theta)R_\\tau \\, d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\int_\\tau \\frac{P(\\tau \\mid \\pi; \\theta)}{P(\\tau \\mid \\pi; \\theta)} \\nabla_\\theta P(\\tau \\mid \\pi; \\theta)R_\\tau \\, d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\E_\\tau \\left[\n",
    "   \\frac{1}{P(\\tau \\mid \\pi; \\theta)} \\nabla_\\theta P(\\tau \\mid \\pi; \\theta)R_\\tau\n",
    "\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\E_\\tau \\left[\n",
    "   \\nabla_\\theta \\log(P(\\tau \\mid \\pi; \\theta))\n",
    "   R_\\tau\n",
    "\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How to compute $\\nabla_\\theta \\E_\\tau[R_\\tau]$?\n",
    "\n",
    "We have:\n",
    "\n",
    "$$\n",
    "\\E_\\tau[R_\\tau] = \\int_\\tau R_\\tau P(\\tau \\mid \\pi;\\theta)\\,d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\nabla_\\theta \\E_\\tau[R_\\tau] = \\nabla_\\theta \\int_\\tau R_\\tau P(\\tau \\mid \\pi; \\theta)\\, d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "=  \\int_\\tau R_\\tau \\nabla_\\theta P(\\tau \\mid \\pi; \\theta)\\, d\\tau\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\E_\\tau \\left[\n",
    "  \\frac{R_\\tau \\nabla_\\theta P(\\tau \\mid \\pi; \\theta)}\n",
    "    {P(\\tau \\mid \\pi; \\theta)}\n",
    "\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\E_\\tau \\left[\n",
    "  R_\\tau \\nabla_\\theta \\log(P(\\tau \\mid \\pi; \\theta))\n",
    "\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute the gradient for a single concrete directory $\\tau = (x_0, a_0, r_1, x_1, \\dots, x_{T-1}, a_{T-1}, r_T, x_T)$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "P(\\tau \\mid x; \\theta)\n",
    "= p(x_0 \\mid \\pi; \\theta) \\,\n",
    "\\prod_{t=0}^{T-1}\n",
    "p(a_t \\mid x_t; \\theta)\\,\n",
    "p(r_t \\mid a_t, x_t)\\,\n",
    "p(x_{t+1} \\mid a_t, x_t)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only terms that depend on $\\theta$ are the action terms, so we have:\n",
    "\n",
    "$$\n",
    "\\nabla_\\theta P(\\tau \\mid x; \\theta)\n",
    "= p(x_0 \\mid \\pi; \\theta) \\,\n",
    "\\prod_{t=0}^{T-1} \\left(\n",
    "    p(r_t \\mid a_t, x_t)\\,\n",
    "    p(x_{t+1} \\mid a_t, x_t)\n",
    "\\right)\n",
    "\\prod_{t=0}^{T-1} \n",
    "    \\nabla_\\theta p(a_t \\mid x_t; \\theta)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\nabla_\\theta \\log P(\\tau \\mid x; \\theta)\n",
    "= \\nabla_\\theta \\log \\left(\n",
    "  p(x_0 \\mid \\pi; \\theta) \\,\n",
    "\\prod_{t=0}^{T-1} \\left(\n",
    "    p(r_t \\mid a_t, x_t)\\,\n",
    "    p(x_{t+1} \\mid a_t, x_t)\n",
    "\\right)\n",
    "\\prod_{t=0}^{T-1} \n",
    "    p(a_t \\mid x_t; \\theta)\n",
    "\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "= \\nabla_\\theta \\left(\n",
    "\\log p(x_0 \\mid \\pi; \\theta)\n",
    "+\n",
    "\\sum_{t=0}^{T-1} \\log\n",
    "    p(r_t \\mid a_t, x_t)\n",
    "+\n",
    "\\sum_{t=0}^{T-1} \\log\n",
    "    p(x_{t+1} \\mid a_t, x_t)\n",
    "+\n",
    "\\sum_{t=0}^{T-1} \\log\n",
    "    p(a_t \\mid x_t; \\theta)\n",
    "\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "=\n",
    "\\sum_{t=0}^{T-1} \\nabla_\\theta \\log\n",
    "    p(a_t \\mid x_t; \\theta)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly the reward for the trajectory is:\n",
    "    \n",
    "$$\n",
    "R_\\tau = \\sum_{t=1}^T r_t\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And so the gradient for this trajectory is:\n",
    "    \n",
    "$$\n",
    "\\hat{g}(\\tau) :=\n",
    "R_\\tau \\nabla_\\theta \\log P(\\tau \\mid \\pi; \\theta )\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "=\n",
    "\\left(\n",
    "    \\sum_{t'=1}^T r_{t'}\n",
    "\\right)\n",
    "\\sum_{t=0}^{T-1} \\nabla_\\theta \\log P(a_t \\mid x_t; \\theta )\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That is:\n",
    "\n",
    "$$\n",
    "\\E_\\tau[\\hat{g}(\\tau) \\mid \\pi; \\theta] =\n",
    "\\nabla_\\theta\n",
    "\\E_\\tau[\n",
    "   R_\\tau \\mid \\pi; \\theta\n",
    "]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are using a neural net to represent the policy, ie to represent $P(a \\mid x; \\theta)$.\n",
    "\n",
    "The gradient $\\nabla_\\theta \\log P(a \\mid x; \\theta)$ can therefore be obtained by back-propping the... well we want to do:\n",
    "\n",
    "$$\n",
    "\\theta \\leftarrow \\theta + \\alpha \\nabla_\\theta \\E_\\tau[R_\\tau]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we want to draw a sample of:\n",
    "\n",
    "$$\n",
    "\\nabla_\\theta \\E_\\tau[R_\\tau]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This sample is $\\hat{g}(\\tau)$, ie:\n",
    "\n",
    "$$\n",
    "\\hat{g}(\\tau) = R_\\tau \\nabla_\\theta \\log P(\\tau \\mid \\pi; \\theta) \\\\\n",
    "= \\left(\n",
    "    \\sum_{t'=1}^T\n",
    "    r_{t'}\n",
    "\\right)\n",
    "\\sum_{t=0}^{T-1}\n",
    "   \\nabla_\\theta \\log P(a_t \\mid x_t; \\theta)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input [1, 0] target 0 a 1 False\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.05\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.55\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.65\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.95\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 1.0\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.95\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.95\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 1.0\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 1.0\n",
      "input [1, 0] target 0 a 0 True\n",
      "input [0, 1] target 1 a 1 True\n",
      "acc 0.9\n"
     ]
    }
   ],
   "source": [
    "import torch\n",
    "from torch import autograd, nn, optim\n",
    "import torch.nn.functional as F\n",
    "\n",
    "\n",
    "class Policy(nn.Module):\n",
    "    def __init__(self, input_size, output_size):\n",
    "        super().__init__()\n",
    "        self.h1 = nn.Linear(input_size, output_size)\n",
    "\n",
    "    def forward(self, x):\n",
    "        x = self.h1(x)\n",
    "        p = F.softmax(x)\n",
    "        a = torch.multinomial(p)\n",
    "#         log_p = torch.log(p[a.data[0]])\n",
    "        return a   # , log_p, p[a.data[0]]\n",
    "\n",
    "torch.manual_seed(123)\n",
    "policy = Policy(2, 2)\n",
    "\n",
    "# let's imagine that if the input is [1, 0], action should be 0\n",
    "# if the input is [0, 1], action should be 1\n",
    "# just something simple for now...\n",
    "# we can do this supervised...\n",
    "training = [\n",
    "    {'input': [1, 0], 'target': 0},\n",
    "    {'input': [0, 1], 'target': 1},\n",
    "]\n",
    "# input = torch.FloatTensor([0.1, 0.1])\n",
    "opt = optim.Adam(params=policy.parameters(), lr=0.1)\n",
    "correct_since_last_print = 0\n",
    "num_epochs = 100\n",
    "print_every = num_epochs // 10\n",
    "for epoch in range(num_epochs):\n",
    "    for ex in training:\n",
    "        policy.zero_grad()\n",
    "        input = torch.FloatTensor(ex['input']).view(1, -1)\n",
    "        target = ex['target']\n",
    "#         a, log_p, p = policy(autograd.Variable(input))\n",
    "        a = policy(autograd.Variable(input))\n",
    "        reward = 0\n",
    "        if a.data[0][0] == target:\n",
    "#             print('a matches target')\n",
    "            reward = 1\n",
    "            correct_since_last_print += 1\n",
    "        if epoch % print_every == 0:\n",
    "            print('input', ex['input'], 'target', target, 'a', a.data[0][0], a.data[0][0] == target)\n",
    "#         log_p.backward(- autograd.Variable(reward))\n",
    "#         a.reinforce(float(reward))\n",
    "        a.reinforce(torch.FloatTensor([[reward]]))\n",
    "#         log_p.backward()\n",
    "        autograd.backward([a], [None])\n",
    "        opt.step()\n",
    "    if epoch % print_every == 0:\n",
    "#         print(list(policy.parameters()))\n",
    "        print('acc', correct_since_last_print / print_every / 2)\n",
    "        correct_since_last_print = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a Variable containing:\n",
      " 1.5000\n",
      "[torch.FloatTensor of size 1]\n",
      "\n",
      "a.grad Variable containing:\n",
      " 1\n",
      "[torch.FloatTensor of size 1]\n",
      "\n",
      "a.grad Variable containing:\n",
      " 0.6667\n",
      "[torch.FloatTensor of size 1]\n",
      "\n",
      "a.grad Variable containing:\n",
      " 0.6667\n",
      " 0.0000\n",
      "[torch.FloatTensor of size 2]\n",
      "\n",
      "a.grad Variable containing:\n",
      " 0.0000\n",
      " 0.4000\n",
      "[torch.FloatTensor of size 2]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import torch\n",
    "from torch import autograd\n",
    "\n",
    "a = autograd.Variable(torch.FloatTensor([1.5]), requires_grad=True)\n",
    "print('a', a)\n",
    "\n",
    "b = a + 1\n",
    "b.backward()\n",
    "print('a.grad', a.grad)\n",
    "\n",
    "a = autograd.Variable(torch.FloatTensor([1.5]), requires_grad=True)\n",
    "b = torch.log(a)\n",
    "b.backward()\n",
    "print('a.grad', a.grad)\n",
    "\n",
    "a = autograd.Variable(torch.FloatTensor([1.5, 2.5]), requires_grad=True)\n",
    "b = torch.log(a[0])\n",
    "b.backward()\n",
    "print('a.grad', a.grad)\n",
    "\n",
    "a = autograd.Variable(torch.FloatTensor([1.5, 2.5]), requires_grad=True)\n",
    "b = torch.log(a[1])\n",
    "b.backward()\n",
    "print('a.grad', a.grad)\n"
   ]
  }
 ],
 "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
{'fraction_non_alphanumeric': 0.257296762491068, 'fraction_numerical': 0.017039520694772714, 'mean_word_length': 1.9521337011195845, 'pattern_counts': {'":': 149, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5993177', 'n_tokens_mistral': 7627, 'n_tokens_neox': 7390, 'n_words': 1672}