book/reinforce/value/q-learning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Q Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a Q function?\n",
    "\n",
    "A Q function is a more complicated version of a value function. In RL, a value function $ v(s) $ tries to approximate all the future rewards a state $ s $ will get. A Q function basically does the same thing, but with a twist.\n",
    "\n",
    "Remember that in RL, state transition happens when an agent, standing in a state $ s^1 $, takes an action $ a $, and ends up in another state $ s^2 $? We notice that instead of directly approximating the value of $ s^2 $, which is $ v(s^2) $, we could use a **Q function**, which takes $ s^1 $ and $ a $ as parameters, and define the q function $ Q(s^1, a) = v(s^2) $ given that $ (s^1, a) \\rightarrow s^2 $.\n",
    "\n",
    "So, compare to value function $ v(s) $ that takes in a state $ s $ as input and outputs a scalar, a Q function $ Q(s) $ that takes in $ s $ as input will output a vector of possible rewards corresponding to possible states we will end up in after taking each possible actions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How are Q functions better?\n",
    "\n",
    "Q functions are better when the number of possible actions are pre-determined, and when we can generate a batch of values faster than we can generate them one-by-one. Because we already know all the possible actions, we could generate a vector faster than a value function, which has to take in the next states one-by-one, which takes precious computational time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q learning in simple terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{warning}\n",
    "Incoming math!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Q-learning, we often make use of an algorithm called $ \\epsilon $-greedy. What the algorithm does is that given an epsilon that's in the range $ [0,1] $, $ \\epsilon $ is the probability that we randomly select an action, or else we greedily choose the best value of all possible actions.\n",
    "\n",
    "Remember that the Q function $ Q(s) $ outputs the future rewards associated with each state that this action can transition to? Suppose that our Q function is accurate enough, $ \\arg_a \\max Q(s) $ is the best action to take in all possible actions.\n",
    "\n",
    "Imagine that we are in a state $ s^1 $, after taking the action $ \\arg_a \\max Q(s) $, we arrive at the state $ s^2 $. If our Q function is accurate, then we have\n",
    "\n",
    "$$\n",
    "Q(s^1, a) = \\gamma R_a + \\arg_a \\max Q(s^2)\n",
    "$$\n",
    "\n",
    "because of the RL equation that\n",
    "\n",
    "$$\n",
    "G_t = \\gamma R_a + G_{t+1}\n",
    "$$\n",
    "\n",
    "So the update rules are easy. We want to update\n",
    "\n",
    "$$\n",
    "Q(s^1, a)\n",
    "$$\n",
    "\n",
    "to be as close to \n",
    "\n",
    "$$\n",
    "\\gamma R_a + \\arg_a \\max Q(s^2)\n",
    "$$\n",
    "\n",
    "as possible (but not vice versa! The reason is a little big complicated. See Sutton and Barto's Intro to RL book).\n",
    "\n",
    "Then we have the update rule:\n",
    "\n",
    "$$\n",
    "Q(s^1, a) = Q(s^1, a) - \\eta \\nabla L(Q(s^1, a), \\gamma R_a + \\arg_a \\max Q(s^2))\n",
    "$$\n",
    "\n",
    "where $ L $ is the loss function."
   ]
  }
 ],
 "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}