(5) Neural Networks - Reinforcement learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6e10624e",
   "metadata": {},
   "source": [
    "## Neural Networks: \n",
    "\n",
    "from https://pad.gwdg.de/s/Machine_Learning_For_Physicists_2021#\n",
    "\n",
    "- Reinforcement learning: \n",
    "    - Model-free (REINFORCE)\n",
    "    - Policy gradient\n",
    "    - Reward baseline\n",
    "    - Q-learning"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c626ccb1",
   "metadata": {},
   "source": [
    "## Reinforcement learning\n",
    "\n",
    "\n",
    "                   observation\n",
    "              --------------------(ENVIRONMENT)   Fully observed vs. partially observed 'state' of the environment\n",
    "              |                       ^\n",
    "              v                       |\n",
    "            (AGENT) -------------------\n",
    "                         action\n",
    "\n",
    "    Agent may be: self-driving car, robot -> observes inmediate environment & moves. \n",
    "\n",
    "- The net tries out things\n",
    "- Train a net to produce actions based on rare rewards instead of being told the correct action. \n",
    "\n",
    "**Challenge**: the correct action is unknown -> **NO SUPERVISED LEARNING**; reward will be rare (or decided only at end). We could use the final reward to define a cost function, but we cannot know how the environment reacts to a proposed chage of the actions that were taken (UNLESS we have a model of environment). \n",
    "\n",
    "        \n",
    "**RL BASIC SETTING**:\n",
    "\n",
    "Take an observation which indicates that the environment is on a certain state (partial or full information about the state) -> we want to map this into an action that will be performed next ->  Policy (strategy) = state + action; \n",
    "\n",
    "\n",
    "    [       RL-AGENT       ]       [RL - ENVIRONMENT]\n",
    "    ------------------------       ------------------\n",
    "    | - Action             |   ->  |                |\n",
    "    | Policy: state-action |       |                |\n",
    "    | -Observation         |   <-  |                |\n",
    "    ________________________       __________________\n",
    "    \n",
    "e.g., robot game: pick boxes as quick as possible\n",
    "\n",
    "        State  = position x,y\n",
    "        Action = move (direction)\n",
    "        Reward - whenever it picks a box, reward = 1, otherwise = 0 or even negative (if we want to penalize)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "749f0bcb",
   "metadata": {},
   "source": [
    "#### MODEL-FREE GENERAL REINFORCEMENT LEARNING TECHNIQUE\n",
    "\n",
    "**> REINFORCE: Policy gradient**: use probabilistic action choice. If the reward at the end turns out to be high, make **all** the actions in this sequence **more likely** (otherwise, do the opposite). This also reinforces 'bad' actions, but since they occur more likely in trajectories with low reward, the net effect will still be to suppress them. \n",
    "\n",
    "*Policy*: probability distribution -> probability to pick action $a_t$ given an observed state $s_t$ at time $t$; $\\theta$ parameters of the NN. \n",
    "\n",
    "\\begin{equation}\n",
    "\\pi_\\theta(a_t | s_t)\n",
    "\\end{equation}\n",
    "\n",
    "Given a state, s -> $x$ robot, $o$ are the boxes\n",
    "\n",
    "                                    [S]\n",
    "                                    ______________________\n",
    "                                    |  o        o    o o | \n",
    "                                    |        o           |\n",
    "                                    |  o                 |\n",
    "                                    |   o         o      |\n",
    "                                    | oo     o    X      |\n",
    "                                    ______________________\n",
    "                                    \n",
    "                                    \n",
    "                                    \n",
    "Action, a: $\\qquad\\qquad$$\\pi$ \n",
    "\n",
    "      down       0.1\n",
    "      up         0.6\n",
    "      left       0.2\n",
    "      right      0.1\n",
    "\n",
    "Environment: makes (possibly stochastic) transition to a new state s' and possibly gives a reward r. \n",
    "\n",
    "*Transition function*: probability of the environment to go into different state, s', given the actual state, s, and the taken action, a;  $P(s'|s,a)$. \n",
    "\n",
    "*Probability for having a certain trajectory of actions and states:* product over time-steps\n",
    "\n",
    "\\begin{equation}\n",
    "P_\\theta(\\tau)=\\prod_t P(s_{t+1}|s_t,a_t)\\pi_\\theta(a_t | s_t)\n",
    "\\end{equation}\n",
    "\n",
    "* Trajectory: \n",
    "    - $\\tau=(a,s)$\n",
    "    - $a=a_0, a_1, a_2,..$\n",
    "    - $s=s_1, s_2,...$ ($s_0$ is fixed)\n",
    "    \n",
    "Expected overall reward (='return'), sum over all actions at all times and over all states at all times >0; $R(\\tau)$, return for this sequence (sum over individual rewards r for all times)\n",
    "\n",
    "\\begin{equation}\n",
    "\\bar{R}= E\\{R\\} = \\sum_\\tau P_\\theta(\\tau)R(\\tau) = \\sum_{a_0, a_1,...,s_1,s_2,...} P_\\theta(\\tau)R(\\tau)\n",
    "\\end{equation}\n",
    "\n",
    "Try to maximize expected return by changing parameters of policy: gradient of a product -> gradient of the various factors and all these different possibilities.\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}=?\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}=\\sum_t\\sum_\\tau R(\\tau)\\frac{\\partial\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\\frac{1}{\\pi_\\theta(a_t | s_t)}\\prod_{t'}P(s_{t'+1}|s_{t'},a_{t'})\\pi_\\theta(a_{t'} | s_{t'})\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}= \\sum_t\\sum_\\tau R(\\tau)\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\\prod_{t'}P(s_{t'+1}|s_{t'},a_{t'})\\pi_\\theta(a_{t'} | s_{t'}) \n",
    "\\end{equation}\n",
    "\n",
    "**> Main formula of policy gradient method:**\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}= \\sum_t E\\left(R\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\\right)\n",
    "\\end{equation}\n",
    "\n",
    "(1) Run a lot of trajectories\n",
    "\n",
    "(2) For **each** trajectory calculate the return, R\n",
    "\n",
    "(3) Look at which actions $a_t$ and states $s_t$ we went through for **each** particular trajectories \n",
    "\n",
    "(4) Calculate the probability of taking the action $a_t$ given the state $s_t$ for each of the time-steps of a **given** trajectory \n",
    "\n",
    "(5) Calculate its logarithmic derivative\n",
    "\n",
    "(6) Sum this overall times\n",
    "\n",
    "(7) Average overall trajectories\n",
    "\n",
    "Stochastic gradient descent: where E(...) is approximated via the value for one trajectory (or a batch). \n",
    "\n",
    "\\begin{equation}\n",
    "\\Delta\\theta=\\eta\\frac{\\partial\\bar{R}}{\\partial \\theta}\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "**> Physical meaning:**\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}= \\sum_t E\\left(R\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\\right)\n",
    "\\end{equation}\n",
    "\n",
    "Taking the derivative of the probability $\\pi_\\theta$ means I'm changing the parameters in the direction in which this probability will get **larger**; I can interpret a step in this direction as a step into the direction in which the parameters make my probability larger, $\\pi_\\theta(a_t | s_t)$. \n",
    "\n",
    "**One particular trajectory is defined by the sequence of all states and actions** <- how can I make the probability for one step **inside** the sequence larger? Since we're summing overall times -> how can I make **on average** all the probabilities larger? \n",
    "\n",
    "    - Take a trajectory\n",
    "    - Calculate its return\n",
    "    - Let me make all the probabilities of all the actions that I really took more probable\n",
    "    - All the probabilities depend on the return:\n",
    "\\begin{equation}\n",
    "R\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\n",
    "\\end{equation}\n",
    "\n",
    "Increase the probability of all action choices in the given sequence, depending on size of return $R$. Even if $R>0$ always, due to normalization of probabilities this will tend to suppress the action choices in sequences with lower-than-average returns.\n",
    "\n",
    "For a given parameter $\\theta_k$; gradient of the probability of a given trajectory $P_\\theta(\\tau)$, being $\\tau$ the trajectory (only the policy $\\pi_\\theta(a_t | s_t)$ depends on the parameters $\\theta_k$):\n",
    "\n",
    "\\begin{equation}\n",
    "G_k=\\frac{\\partial ln P_\\theta(\\tau)}{\\partial \\theta_k}=\\sum_t\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta_k}\n",
    "\\end{equation}\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta_k}= E(RG_k)\n",
    "\\end{equation}\n",
    "\n",
    "**> Policy gradient: reward baseline**\n",
    "\n",
    "Fluctuations of estimate for return gradient can be huge -> things improve if one subtracts a constant baseline from the return:\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial\\bar{R}}{\\partial \\theta}= \\sum_t E\\left((R-b)\\frac{\\partial ln\\pi_\\theta(a_t | s_t)}{\\partial \\theta}\\right)=E((R-b)G)\n",
    "\\end{equation}\n",
    "\\begin{equation}\n",
    "E((R-b)G) = (R-b)E(G) \\qquad \\rightarrow \\qquad E(G_k)=\\sum_\\tau P_\\theta(\\tau)\\frac{\\partial ln P_\\theta(\\tau)}{\\partial \\theta_k}=\\frac{\\partial}{\\partial \\theta_k}\\sum_\\tau P_\\theta(\\tau)= \\frac{\\partial}{\\partial \\theta_k}\\cdot 1 = 0\n",
    "\\end{equation}\n",
    "\n",
    "However, the variance of the fluctuating random variable $(R-b)G$ is different and can be smaller (depending on $b$). \n",
    "\n",
    "**Optimal baseline:** $k$ refers to the parameters $\\theta_k$\n",
    "\n",
    "\\begin{equation}\n",
    "X_k=(R-b_k)G_k \\qquad \\qquad Var(X_k)=E(X_k^2)-E(X_k)^2 = min \\qquad \\qquad \\frac{\\partial Var(X_k)}{\\partial b_k}=0\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "b_k=\\frac{E(G_k^2 R)}{E(G_k^2)} \\qquad \\qquad G_k=\\frac{\\partial ln P_\\theta(\\tau)}{\\partial \\theta_k}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\Delta\\theta_k=-\\eta E(G_k(R-b_k))\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10ea683e",
   "metadata": {},
   "source": [
    "##### RL: random walk\n",
    "\n",
    "The probability to go up is determined by the policy, and where the return is given by the final position (strategy: always go up) -> the policy doesn't depend on the current state.\n",
    "\n",
    "> Policy:\n",
    "\\begin{equation}\n",
    "\\pi_\\theta(up)=\\frac{1}{1+e^{-\\theta}}\n",
    "\\end{equation}\n",
    "Return:\n",
    "\\begin{equation}\n",
    "R=x(T)\n",
    "\\end{equation}\n",
    "\n",
    "RL update: $a_t$ up or down\n",
    "\\begin{equation}\n",
    "\\Delta\\theta = \\eta \\sum_t\\left<R\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta}\\right>\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta} = \\pm e^{-\\theta}\\pi_\\theta(a_t)=\\pm(1-\\pi_\\theta(a_t))\n",
    "\\end{equation}\n",
    "\n",
    "(+ for up, - for down)\n",
    "\n",
    "\\begin{equation}\n",
    "up \\qquad \\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta} = \\ 1-\\pi_\\theta(up) \\qquad \\qquad down\\qquad \\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta} = -\\pi_\\theta(up)\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_t\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta} = N_{up}-N\\pi_\\theta(up)\n",
    "\\end{equation}\n",
    "\n",
    "$N_{up}$ number of **up-steps**, $N$ number of time-steps. \n",
    "\n",
    "Return:\n",
    "\\begin{equation}\n",
    "R=x(T)=N_{up}-N_{down}=2N_{up}-N\n",
    "\\end{equation}\n",
    "\n",
    "RL update: $a_t$ up or down\n",
    "\\begin{equation}\n",
    "\\Delta\\theta = \\eta \\sum_t\\left<R\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta}\\right>\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\left<R\\sum_t\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta}\\right>=\\left<(N_{up} - N/2)(N_{up}-\\bar{N}_{up})\\right> \n",
    "\\end{equation}\n",
    "\n",
    "Initially, when $\\pi_\\theta(up)=1/2$: \n",
    "\\begin{equation}\n",
    "\\Delta\\theta = 2\\eta \\left<(N_{up} - N/2)^2\\right> = 2\\eta Var(N_{up})=\\eta N/2 >0 \\qquad Binomial\\quad distribution\n",
    "\\end{equation}\n",
    "\n",
    "In general: \n",
    "\n",
    "\\begin{equation}\n",
    "\\left<R\\sum_t\\frac{\\partial ln\\pi_\\theta(a_t)}{\\partial \\theta}\\right>=2N\\pi_\\theta(up)(1-\\pi_\\theta(up))\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a08baba",
   "metadata": {},
   "source": [
    "##### RL: Walker target (Keras)\n",
    "\n",
    "Robot that can change its position: steps are 0 (stays) or 1 (moves). \n",
    "    \n",
    "    There's a specific target-site -> reward is +1 for each time it remains on the target site; \n",
    "                                      return is the number of time steps on target. \n",
    "\n",
    "Stage of NN:\n",
    "\n",
    "    output = action probabilities (softmax to guarantee the normalization)\n",
    "\n",
    "> Policy $\\pi_\\theta(a|s)$\n",
    "\n",
    "        a=0 (stay),     a=1 (move)\n",
    "        \n",
    "        input = s = are we on target? (0/1)\n",
    "\n",
    "Steps to obtain *one trajectory*: \n",
    "\n",
    "    (1) Execute action, record new state\n",
    "    (2) Apply NN to state thus obtain action probabilities\n",
    "    (3) From probabilities, obtain action for next step\n",
    "    (4) -> (1) repeat\n",
    "\n",
    "Steps *for each trajectory*: \n",
    "\n",
    "    (1) Do one trajectory (batch of trajectories) [Previous - Steps to obtain one trajectory]\n",
    "    (2) Obtain overall sum of rewards (=return) for each trajectory\n",
    "    (3) Apply policy gradient training (enhance proabilities for all actions in a high-return trajectory)\n",
    "    (4) -> (1) repeat\n",
    "    \n",
    "**Categorical cross-entropy trick:**\n",
    "\n",
    "input = state, s\n",
    "\n",
    "output = action, a, probabilities (softmax) - $\\pi_\\theta(a|s)$\n",
    "\n",
    "                        a=0       a=1      a=2\n",
    "                         o         o        o\n",
    "                         |         |        |\n",
    "                         ...(connections)...\n",
    "                            |           |\n",
    "                            o           o\n",
    "                            input = state\n",
    " \n",
    "Categorical cross-entropy: distribution from net ($\\pi_\\theta(a|s)$), desired distribution ($P(a)$).\n",
    "\n",
    "\\begin{equation}\n",
    "C=-\\sum_aP(a)ln\\pi_\\theta(a|s) \n",
    "\\end{equation}\n",
    "\n",
    "Set $P(a) = R$ for $a=action$ that was taken and $P(a)=0$ for all other actions $a$. \n",
    "\n",
    "\\begin{equation}\n",
    "\\Delta\\theta=-\\eta\\frac{\\partial C}{\\partial \\theta}\\qquad implements\\quad policy\\quad gradient\n",
    "\\end{equation}\n",
    "\n",
    "- Encountered N states (during repeated runs)\n",
    "- After setting categorical cross-entropy as a cost function, implement policy gradient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e35fb23",
   "metadata": {},
   "outputs": [],
   "source": [
    "# POLICY GRADIENT ON KERAS:\n",
    "net.train_on_batch(observed_inputs,desired_outputs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4176058b",
   "metadata": {},
   "source": [
    "Where:\n",
    "\n",
    "    observed_inputs -> array N x state-size\n",
    "    desired_outputs -> array N x number of actions\n",
    "    \n",
    "The desired output is the distribution $P(a)$, which was set $P(a) = R$ for $a=action$ that was taken and $P(a)=0$ for all other actions $a$\n",
    ">**desired_outputs(j,a)=R** for the state $j$ if action $a$ was taken during a run that gave overall return $R$. \n",
    "\n",
    ">**Walker target .py @ 22:40 - 44:00 https://www.fau.tv/clip/id/11621**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39edde58",
   "metadata": {},
   "source": [
    "### Q-learning:\n",
    "\n",
    "An alternative to the policy gradient approach; introduce a quality function $Q$ that predicts the future reward for a given state $s$ and a given action $a$.\n",
    "\n",
    "**Deterministic policy:** just select the action with the largest Q!\n",
    "\n",
    "- Value function -> function of the states (how valuable is to be in a particular position).\n",
    "- Quality function -> function of the state but also the action: Q(s,a). Predicts the future reward for a given state $s$ and a given action $a$:\n",
    "\n",
    "\\begin{equation}\n",
    "Q(s_t,a_t)=E(R_t|s_t,a_t)\n",
    "\\end{equation}\n",
    "\n",
    "*assuming future steps to follow the policy*. Discounted future reward: \n",
    "\\begin{equation}\n",
    "R_t=\\sum_{t'=t}^Tr_{t'}\\gamma^{t'-t}\n",
    "\\end{equation}\n",
    "\n",
    "Reward at time step $t$: $r_t$, depends on state and action at time $t$\n",
    "\n",
    "Discount factor: $0<\\gamma\\leq 1$, learning somewhat easier for smaller factor (short memory times)\n",
    "\n",
    "Value of state: $V(s)=max_aQ(s,a)$\n",
    "\n",
    "Update rule: **Bellmann equation**\n",
    "\n",
    "\\begin{equation}\n",
    "Q(s_t,a_t)=E(r_t+\\gamma max_aQ(s_{t+1},a)|s_t,a_t)\n",
    "\\end{equation}\n",
    "\n",
    "*expected value of the next reward $r_t$ + the discounting $\\gamma$ times the quality function already evaluated for the next timestep and maximized overall actions*. \n",
    "\n",
    "We don't know $Q$ -> *update rule*\n",
    "\\begin{equation}\n",
    "Q^{new}(s_t,a_t)=Q^{old}(s_t,a_t)+ \\alpha(r_t+\\gamma max_aQ^{old}(s_{t+1},a)-Q^{old}(s_t,a))\n",
    "\\end{equation}\n",
    "\n",
    "where $(r_t+\\gamma max_aQ^{old}(s_{t+1},a)-Q^{old}(s_t,a)) <1$ is the small update factor; will be $0$ once we have converged to the correct $Q$. If we use a NN to calculate $Q$, it will be trained to yield the new value in each step. \n",
    "\n",
    "Initially, $Q$ is arbitrary: bad to follow this $Q$ all the time -> introduce probability $\\epsilon$ of random action (**exploration**, $\\epsilon$-greedy):\n",
    "\n",
    "                         Follow Q - exploitation\n",
    "        Do something random (new) - exploration\n",
    "        Reduce randomness later. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}