track1_part2_experience_replay.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2 : Dyna-Q and Experience replay"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The paper by Lin et. al. [1], addresses the issue of sluggish leaning by the reinforcement learning (RL) frameworks. The primary frameworks in question are *adaptive heuristic critic* (AHC) and *Q-learning*. To speed up these two frameworks the paper proposes three extensions to these algorithms. In total they implement and compare 8 different frameworks:\n",
    " - Vanilla: AHCON and QCON\n",
    " - Experience Replay: AHCON-R and QCON-R\n",
    " - Action modeling (inspired by Dyna architechture by Sutton et. al.[2]) : AHCON-M and QCON-M\n",
    " - Teaching: AHCON-T and QCON-T\n",
    " \n",
    " In this report we will be comparing the QCON-R and QCON-M with the vanilla Dyna-Q framework proposed in [2] and as implemented earlier in this report. We choose QCON-R and QCON-M since the these use are based on estimating action-value function $Q(S,A)$ just like the Dyna-Q framework, even though how they achieve this is very diffrent compared to Dyna-Q Each of these methods also have it's own implementation of storing and reusing historical experiences of the agent. Hence it's most reasonable to compare these with Dyna-Q."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tabular Dyna-Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Initialize $Q(s, a)$ and $Model(s, a)$ for all $s \\in S$ and $a \\in A(s)$ \n",
    "- Loop forever or until $S \\in S(terminal)$:\n",
    "  - $S \\leftarrow state_{current}$\n",
    "  - $A \\leftarrow \\epsilon - greedy(S,Q)$\n",
    "  - $\\acute{S}, R \\leftarrow environment(S,A)$\n",
    "  - $Q(S,A) \\leftarrow Q(S,A) + \\alpha[ R + \\gamma\\ max_{a}(Q(\\acute{S}, a)) − Q(S,A)]$\n",
    "  - $model(S,A) \\leftarrow R,\\acute{S} $\n",
    "  - Loop repeat $n$ times:\n",
    "      - $S \\leftarrow$ random previously observed state\n",
    "      - $A \\leftarrow$ random action previously taken in $S$\n",
    "      - $R,\\acute{S} \\leftarrow model(S,A) $\n",
    "      - $Q(S,A) \\leftarrow Q(S,A) + \\alpha[ R + \\gamma\\ max_{a}(\\ Q(\\acute{S}, a)\\ ) − Q(S,A)]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the framework presented by Sutton et. al. [2]. We implement this earlier in this report on two test *dynamic maze game worlds*. The idea behind the framework is to unify the *learning* and *planning* arms of the RL Learning. These are also known as *model free* and *model based* reinforcement learning. The following two approches (QCON-M and QCON-R) also address this unification. The general idea of the unification among all the three algorithms is the same: \n",
    "\n",
    "1. Get real world experience\n",
    "2. Learning: Update value function\n",
    "3. Simulate experiences from History\n",
    "4. Update value function using these simulated experiences\n",
    "5. Repeat\n",
    "\n",
    "The key between Dyna-Q and others is how they implement the step 2, 3 and 4. The action selection here also differs from the other two algorithms where they use a softmax function over the q-value (or utility function as the paper calls it). Here we use a simple $\\epsilon-greedy$ algorithm. For learning we implement the tabular version of Q-learning algorithm as our learning function. As for history, it is stored by maintaining a oracle. In particular we maintain a lookup table of the form:\n",
    "\n",
    "$model(S, A) = (\\acute{S}, R)$\n",
    "\n",
    "The model is first initialised such that\n",
    "\n",
    "$model(S, a) = (S, 0), a \\in A$\n",
    "\n",
    "And at each step the lookup table is deterministicall updated to reflect the latest experience. This way we lose the past observations experienced at by taking action $A$ while in state $S$. This oracle is then used to randomly generate simulated experiences. These are chosen only from the experiences which have to been experienced in the real world in the past. We then use these experiences to further update the value function (Q-learning update in our case). We do this since it is usually very expensive to collect real world data than to generate simulations. This way we can bootstrap our learning on past data with little cost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QCON-M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Initialize $Q(s, a)$ and $Model(s, a)$ for all $s \\in S$ and $a \\in A(s)$ \n",
    "- Loop forever or until $S \\in S(terminal)$:\n",
    "  1. $S \\leftarrow state_{current}$\n",
    "  2. $A \\leftarrow softmax(S,Q_{net})$\n",
    "  3. $\\acute{S}, R \\leftarrow environment(S,A)$\n",
    "  4. $\\Delta Q \\leftarrow [R + \\gamma\\ Q_{net}(\\acute{S},A)] - Q_{net}(S,A)$\n",
    "  5. update $Q_{net}$ by progating $\\Delta Q$ through the network\n",
    "  6. $model(S,A) \\leftarrow R,\\acute{S} $\n",
    "  7. Loop repeat $n$ times:\n",
    "      - $S \\leftarrow$ random previously observed state $S$ from $model \\ s.t. \\ softmax(S_{current},Q)_{S} \\ge threshold$\n",
    "      - $A \\leftarrow$ random action previously taken in $S$\n",
    "      - $R,\\acute{S} \\leftarrow model(S,A) $\n",
    "      - $\\Delta Q \\leftarrow [R + \\gamma\\ Q_{net}(\\acute{S},A)] - Q_{net}(S,A)$\n",
    "      - update $Q_{net}$ by progating $\\Delta Q$ through the network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QCON-M is inspired by the Dyna-Q architechture, explained above, with some differences. Apart from the previously mentioned action selection (policy) main difference is that the action-value function here is estimated by using a neural network instead of the tabular Q-learning update. Because of this, the method of simulating past experiences defers from Dyna-Q. Since a Q-value update in the nueral network would affect the network as a whole, we do not want a experiences of a comparatively bad policy (experienced in the past) to affect the current value, induced by the current policy. This problem does not arise in the case of tabular updates since we do the update only for a particular pair of state and action. Hence only those experiences from the past are replayed which also occur under the current policy of the algorithm, **given the current state**. This is another subtle difference of this framework from the Dyna-Q presented above, where simulations are chosen starting from any random state. Since the value-network, given a state $S$ and action $A$ produces a probability distribution over the the next possible states $\\acute{S}$, the paper uses a threshold over these probabilities for selecting past experiences. Model updates are carried out in the exact same way as in the case of Dyna-Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QCON-R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Initialize $Q(s, a)$ and $Model(s, a)$ for all $s \\in S$ and $a \\in A(s)$ \n",
    "- Loop forever or until $S \\in S(terminal)$:\n",
    "  1. $S \\leftarrow state_{current}$\n",
    "  2. $A \\leftarrow softmax(S,Q)$\n",
    "  3. $\\acute{S}, R \\leftarrow environment(S,A)$\n",
    "  4. $\\Delta Q \\leftarrow [R + \\gamma\\ Q_{net}(\\acute{S},A)] - Q_{net}(S,A)$\n",
    "  5. update $Q_{net}$ by progating $\\Delta Q$ through the network\n",
    "  6. $H_t \\leftarrow (S, A, R,\\acute{S}) $\n",
    "  7. Loop repeat $n$ times:\n",
    "      - $S \\leftarrow$ random previously observed state $S$ from $H \\ s.t. \\ softmax(S_{current},Q)_{S} \\ge threshold$\n",
    "      - $A \\leftarrow$ random action previously taken in $S$\n",
    "      - $R,\\acute{S} \\leftarrow model(S,A) $\n",
    "      - $\\Delta Q \\leftarrow [R + \\gamma\\ Q_{net}(\\acute{S},A)] - Q_{net}(S,A)$\n",
    "      - update $Q_{net}$ by progating $\\Delta Q$ through the network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QCON-R is similar to the QCON-M since the mechanism of value network and action selection remains the same. But the this framework does not maintain a model of past experiences. Instead it simply records all of the history occured till now. But similar to QCON-M, only those past experiences which satisfy the current policy are selected for simulation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "1. Lin, L.J., 1992. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4), pp.293-321.\n",
    "2. Sutton, R.S. and Barto, A.G., 1998. Reinforcement learning: An introduction (Vol. 1, No. 1). Cambridge: MIT press."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}