rl_book.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ch 1. Elements of Reinforcement Learning\n",
    "\n",
    "### Policy\n",
    "* A **policy** defines the agent's **way of behaving** at a **given time**.\n",
    "* A policy is a **mapping** from perceived **states** of the environment to **actions** to be taken when in those states.\n",
    "  - E.g., a simple function, a lookup table, or a search process. \n",
    "* The policy is the core of an agent (it alone is sufficient to determine behavior).\n",
    "* Policies may be **stochastic**, specifying probabilities for each action.\n",
    "\n",
    "### Reward signal\n",
    "* On each time step, the environment sends to the agent a single number, called the **reward**.\n",
    "* A reward signal defines the **goal** of a RL problem. \n",
    "* The agent's sole objective is to **maximize the total reward** it receives over the long run.\n",
    "* The **reward signal**, thus, defines what are the good and bad events for the agent.\n",
    "* In general, reward signals may be stochastic functions of the state of the environment and the actions taken.\n",
    "\n",
    "### Value function\n",
    "* A **value function** specifies what is good in the **long run**, whereas the **reward** signal indicates what is good in an **immediate sense**.\n",
    "* The **value of a state** is the **total amount of reward** an agent can expect to accumulate over the future, starting from that state.\n",
    "* It is values with which we are most concerned when making and evaluating decisions (action choices are made based on value judgments).\n",
    "  - We seek actions that bring about states of highest value, not highest reward.\n",
    "\n",
    "### Model\n",
    "* A **model** is something that mimics the **behavior of the environment** that allows inferences to be made about how the environment will behave.\n",
    "  - E.g., given a state and action, the model might predict the resultant next state and next reward.\n",
    "* Models are used for **planning**, by which we mean any way of deciding on a course of action by considering possible future situations before they are actually experienced.\n",
    "* Methods for solving RL problems that use models and planning are called **model-based** methods, as opposed to simpler **model-free** methods that are explicitly **trial-and-error** learners (viewed as almost the opposite of planning)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Part I: Tabular Solution Methods\n",
    "Here the **state and action spaces** are **small** enough for the approximate **value functions** to be represented as arrays, or **tables**. In this case, the methods can often find **exact solutions**, that is, they can often find exactly the **optimal value function** and the **optimal policy**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ch 2. Multi-armed Bandits\n",
    "* The most important feature distinguishing RL from other types of learning is that it uses training information that **evaluates** the actions taken rather than **instructs** by giving correct actions. \n",
    "  - Purely **evaluative** feedback indicates how good the action taken was, but not whether it was the best or the worst action possible.\n",
    "  - Purely **instructive** feedback indicates the correct action to take, independently of the action actually taken (this kind of feedback is the basis of supervised learning).\n",
    "  - These two kinds of feedbacks (in their pure forms) are quite distinct: evaluative feedback depends entirely on the action taken, whereas instructive feedback is independent of the action taken."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### k-armed Bandit Problem\n",
    "* You are faced repeatedly with a choice among **k different options (actions)**.\n",
    "* After each choice you receive a numerical **reward** chosen from a stationary probability distribution that depends on the action you selected.\n",
    "* Your **objective** is to **maximize the expected total reward** over some time period (e.g., over 1000 action selections), or **time steps**.\n",
    "* Each action has an **expected or mean reward** given that that action is selected (it's called the **value of that action**).\n",
    "* If we denote the action selected on time step $t$ as $A_t$, and the corresponding reward as $R_t$, then the value of an arbitrary action $a$, denoted $q_{*}(a)$, is the expected reward given that a is selected:\n",
    "$$\n",
    "q_{*}(a) = \\mathbb{E}[R_t | A_t=a]\n",
    "$$\n",
    "* If you knew the value of each action, then it would be trivial to solve the k-armed bandit problem: you would always select the action with highest value. \n",
    "* If we do not know the action values with certainty, we need to use the **estimated value of action** a at time step $t$, denoted by $Q_t(a)$. We would like $Q_t(a)$ to be close to $q_{*}(a)$.\n",
    "* **Greedy actions**: any action whose estimated value is greatest at any time step\n",
    "* **Exploiting**: if we select one of the **greedy actions**, then we say that we are exploiting our current knowledge of the values of the actions.\n",
    "* **Exploring**: if we select one of the **non-greedy actions**, then we say we are exploring, because this enables us to improve our estimate of the non-greedy action's value.\n",
    "* **Exploitation** is the right thing to do to maximize the expected reward on the **one step**, but **exploration** may produce the greater total reward in the **long run**. \n",
    "* Because it is not possible both to explore and to exploit with any single action selection, one often refers to the **conflict** between exploration and exploitation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Action-value Methods\n",
    "* We collectively call **action-value methods** to **estimate the values of actions** and use the estimates to make **action selection** decisions.\n",
    "* The **true value of an action** is the **mean reward** when that action is selected. One natural way to estimate this is by averaging the rewards actually received (it's called the **sample-average** method for estimating action values):\n",
    "$$\n",
    "Q_t(a) = \\frac{\\text{sum of rewards when }a\\text{ taken prior to }t}{\\text{number of times }a\\text{ taken prior to }t} = \\frac{\\sum_{i=1}^{t-1}R_i\\cdot\\mathbb{1}_{A_i=a}}{\\sum_{i=1}^{t-1}\\mathbb{1}_{A_i=a}}\n",
    "$$\n",
    "  - As the denominator goes to **infinity**, by the law of large numbers, $Q_t(a)$ converges to $q_*(a)$.\n",
    "* The **greedy action selection** method can be written as below:\n",
    "$$\n",
    "A_t = \\arg\\max_aQ_t(a)\n",
    "$$\n",
    "* **$\\varepsilon$-greedy methods**: behave greedily most of the time, but every once in a while (with small probability), select **randomly** from among all the actions with equal probability, independently of the action-value estimates. \n",
    "  - An advantage of these methods is that, in the limit as the number of steps increases, every action will be sampled an infinite number of times, thus ensuring that all the $Q_t(a)$ converge to $q_*(a)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Incremental Implementation\n",
    "* The above action-value methods estimate action values as sample averages of **observed rewards**.\n",
    "* Let $R_i$ denotes the **reward** received after the $i$th selection of this action, and $Q_n$ denotes the **estimate of its action-value** after it has been selected $n-1$ times:\n",
    "$$\n",
    "Q_n = \\frac{R_1 + R_2 + \\cdots + R_{n-1}}{n-1}\n",
    "$$\n",
    "* The obvious implementation would be to maintain a record of all the rewards and then perform this computation whenever the estimated value was needed. \n",
    "* How these averages can be computed with **constant memory** and **constant per-time-step computation**?\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "Q_{n+1} ={} & \\frac{1}{n}\\sum_{i=1}^nR_i\\\\\n",
    "={} & \\frac{1}{n}(R_n + \\sum_{i=1}^{n-1}R_i)\\\\\n",
    "={} & \\frac{1}{n}(R_n + (n-1)\\frac{1}{n-1}\\sum_{i=1}^{n-1}R_i)\\\\\n",
    "={} & \\frac{1}{n}(R_n + (n-1)Q_n)\\\\\n",
    "={} & Q_n + \\frac{1}{n}(R_n - Q_n)\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* The general form\n",
    "$$\n",
    "NewEstimate \\leftarrow OldEstimate + StepSize\\cdot[Target - OldEstimate]\n",
    "$$\n",
    "* $[Target - OldEstimate]$ is and **error** in the estimate.\n",
    "<img src=\"rl_figs/rl_simple_bandit.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nonstationary Problem\n",
    "* The averaging methods discussed so far are appropriate for **stationary bandit problems**, that is, for bandit problems in which the **reward probabilities do not change over time**.\n",
    "* In nonstationary cases it makes sense to **give more weight to recent rewards** than to long-past rewards.\n",
    "* One of the most popular ways of doing this is to use a **constant step-size parameter**.\n",
    "\n",
    "$$\n",
    "Q_{n+1} = Q_n + \\alpha(R_n - Q_n)\n",
    "$$\n",
    "\n",
    "* where the step-size parameter $\\alpha \\in (0, 1]$ is constant.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "Q_{n+1} ={} & \\alpha(R_n - Q_n)\\\\\n",
    "={} & \\cdots\\\\\n",
    "={} & (1 - \\alpha)^nQ_1 + \\sum_{i=1}^n \\alpha(1 - \\alpha)^{n-i}R_i\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "* We call this a weighted average because the sum of the weights is $(1 - \\alpha)^n + \\sum_{i=1}^n \\alpha(1 - \\alpha)^{n-i} = 1$.\n",
    "* The quantity $1 - \\alpha$ is less than 1, and thus the weight given to $R_i$ decreases as the number of intervening rewards increases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Ch 3. Finite Markov Decision Processes\n",
    "* Finite Markov Decision Processes (MDP) are a classical formalization of sequential decision making, where actions influence not just immediate rewards, but also **subsequent situations**, or **states**, and through those future rewards.\n",
    "* Thus, MDPs involve **delayed reward** and the need to tradeoff immediate and delayed reward.\n",
    "* Whereas in **bandit problems** we estimated the value $q_*(a)$ of each action $a$, in **MDPs** we estimate the value $q_*(s, a)$ of each action $a$ in each state $s$, or we estimate the value $v_*(s)$ of each state given optimal action selections.\n",
    "* These **state-dependent quantities** are essential to accurately assigning credit for **long-term** consequences to individual action selections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Agent–Environment Interface\n",
    "* MDPs are meant to be a straightforward framing of the problem of **learning from interaction** to achieve a goal.\n",
    "* The **learner and decision maker** is called the **agent**. \n",
    "* The thing an agent interacts with (comprising everything outside the agent) is called the **environment**.\n",
    "* These interact **continually**, the agent selecting actions and the environment responding to these actions and presenting new situations to the agent.\n",
    "<img src=\"rl_figs/rl_agent_env.png\" width=\"400\">\n",
    "* The agent and environment interact at each of a sequence of discrete time steps, $t = 0, 1, 2, 3, \\cdots$. \n",
    "  - At each time step $t$, the agent receives some **representation of the environment's state**, $S_t \\in \\mathcal{S}$, and on that basis selects an **action**, $A_t \\in \\mathcal{A}(s)$.\n",
    "  - One time step later, in part as a consequence of its action, the agent receives a **numerical reward**, $R_{t+1} \\in \\mathcal{R} \\subset \\mathbb{R}$, and finds itself in a new state, $S_{t+1}$.\n",
    "  - The MDP and agent together thereby give rise to a sequence or **trajectory** that begins like this: $S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \\cdots$.\n",
    "  \n",
    "  \n",
    "* In a **finite** MDP, the sets of states, actions, and rewards ($\\mathcal{S}$, $\\mathcal{A}$, and $\\mathcal{R}$) all have a **finite number of elements**.\n",
    "  - In this case, the random variables $R_t$ and $S_t$ have well defined discrete probability distributions dependent only on the **preceding state and action**. \n",
    "  - That is, for particular values of these random variables, $s' \\in \\mathcal{S}$ and $r \\in \\mathcal{R}$, there is a probability of those values occurring at time $t$, given particular values of the preceding state and action (for all $s',s \\in \\mathcal{S}$, $r \\in \\mathcal{R}$, and $a \\in \\mathcal{A}(s)$):\n",
    "$$\n",
    "p(s',r|s,a) = Pr\\{S_t=s',R_t=r|S_{t-1}=s,A_{t-1}=a\\}\n",
    "$$\n",
    "* The function $p$ defines the **dynamics** of the MDP: $p:\\mathcal{S} \\times \\mathcal{R} \\times \\mathcal{S} \\times \\mathcal{A} \\rightarrow [0, 1]$.\n",
    "* **State-transition** probabilities: $p:\\mathcal{S} \\times \\mathcal{S} \\times \\mathcal{A} \\rightarrow [0, 1]$.\n",
    "$$\n",
    "p(s'|s,a) = Pr\\{S_t=s'|S_{t-1}=s,A_{t-1}=a\\} = \\sum_{r \\in \\mathcal{R}}p(s',r|s,a)\n",
    "$$\n",
    "* **State-action** pairs: $r: \\mathcal{S} \\times \\mathcal{A} \\rightarrow \\mathbb{R}$.\n",
    "$$\n",
    "r(s,a) = \\mathbb{E}[R_t|S_{t-1}=s,A_{t-1}=a\\} = \\sum_{r \\in \\mathcal{R}}r\\sum_{s' \\in \\mathcal{S}}p(s',r|s,a)\n",
    "$$\n",
    "* **State-action-next-state** pairs: $r: \\mathcal{S} \\times \\mathcal{A} \\times \\mathcal{S} \\rightarrow \\mathbb{R}$.\n",
    "$$\n",
    "r(s,a,s') = \\mathbb{E}[R_t|S_{t-1}=s,A_{t-1}=a,S_t=s'\\} = \\sum_{r \\in \\mathcal{R}}r\\frac{p(s',r|s,a)}{p(s'|s,a)}\n",
    "$$\n",
    "\n",
    "\n",
    "* In a **Markov decision process**, the probabilities given by $p$ completely characterize the **environment's dynamics**. \n",
    "  - That is, the probability of each possible value for $S_t$ and $R_t$ depends only on the **immediately preceding state and action**, $S_{t-1}$ and $A_{t-1}$.\n",
    "  - This is best viewed a **restriction** not on the decision process, but on the **state**. \n",
    "  - The state must include information about all aspects of the past agent-environment interaction that make a difference for the future. \n",
    "  - If it does, then the state is said to have the **Markov property**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Goals, Rewards, Returns and Episodes\n",
    "* In RL, the purpose or **goal** of the agent is formalized in terms of a special signal, called the **reward**, passing from the environment to the agent. \n",
    "  - At each time step, the reward is a **simple number**, $R_t \\in \\mathbb{R}$.\n",
    "* Informally, the agent's goal is to **maximize** the total amount of reward it receives.\n",
    "  - This means maximizing not immediate reward, but **cumulative reward** in the **long run**.\n",
    "  \n",
    "#### Episodic tasks\n",
    "* If the sequence of rewards received after time step $t$ is denoted $R_{t+1}$, $R_{t+2}$, $R_{t+3}$, $\\cdots$, then what precise aspect of this sequence do we wish to maximize?\n",
    "* In general, we seek to maximize the **expected return**, denoted $G_t$, which is defined as some specific function of the reward sequence.\n",
    "* The **return** is the function of **future rewards** that the agent seeks to maximize (in expected value).\n",
    "* In the simplest case the **return** is the **sum of the rewards** ($T$ is a final time step):\n",
    "$$\n",
    "G_t = R_{t+1} + R_{t+2} + R_{t+3} + \\cdots + R_T\n",
    "$$\n",
    "* The above approach makes sense where there is a natural notion of **final time step**, e.g., $T$.\n",
    "* That is, when the agent-environment interaction breaks naturally into subsequences, called **episodes**.\n",
    "* Each episode ends in a special state, called the **terminal state**, followed by a reset to a standard starting state or to a sample from a standard distribution of starting states.\n",
    "* Even if you think of episodes as ending in different ways, such as winning and losing a game, the next episode begins **independently** of how the previous one ended. \n",
    "* Thus, the episodes can all be considered to end in the **same terminal state**, with different rewards for the different outcomes. \n",
    "* Tasks with episodes of this kind are called **episodic tasks**.\n",
    "\n",
    "#### Continuing tasks\n",
    "* In many cases the agent-environment interaction does not break into episodes, but goes on **continually without limit**.\n",
    "* The above formulation is problematic for continuing tasks because the final time step would be $T = \\infty$, and the return, which is what we are trying to maximize, could itself easily be infinite.\n",
    "* A concept that we need here is that of **discounting**.\n",
    "* According to the discounting approach, the agent tries to select actions so that the **sum of the discounted rewards** it receives over the future is maximized. \n",
    "* In particular, it chooses $A_t$ to maximize the expected **discounted return** ($0 \\le \\gamma \\le 1$ is called the **discount rate**):\n",
    "$$\n",
    "G_t = R_{t+1} + \\gamma R_{t+2} + \\gamma^2 R_{t+3} + \\cdots = \\sum_{k=0}^{\\infty} \\gamma^k R_{t+k+1}\n",
    "$$\n",
    "* It can also be written as\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "G_t ={} & R_{t+1} + \\gamma R_{t+2} + \\gamma^2 R_{t+3} + \\gamma^3 R_{t+4} + \\cdots\\\\\n",
    "={} & R_{t+1} + \\gamma (R_{t+2} + \\gamma R_{t+3} + \\gamma^1 R_{t+4} + \\cdots)\\\\\n",
    "={} & R_{t+1} + \\gamma G_{t+1}\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* Although the return of the following formula is a sum of an infinite number of terms, it is still finite if the reward is non-zero and constant ($\\gamma < 1$). For example, if the reward is a constant +1 ($R = +1$), then the return is:\n",
    "$$\n",
    "G_t = \\sum_{k=0}^{\\infty} \\gamma^k = \\frac{1}{1-\\gamma}\n",
    "$$\n",
    "\n",
    "#### Unified notation for episodic and continuing tasks\n",
    "* The **return** is defined as a sum over a **finite number** of terms in **episodic tasks**, and as a sum over an **infinite number** of terms in **continuous tasks**.\n",
    "* These two can be **unified** by considering episode termination to be the entering of a special **absorbing state** that transitions only to itself and that generates only rewards of zero.\n",
    "\n",
    "<img src=\"rl_figs/rl_absorbing_state.png\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policies and Value Functions\n",
    "* Almost all RL algorithms involve estimating **value functions**: functions of **states** (or of **state-action** pairs) that estimate **how good** it is for the agent to **be in a given state** (or how good it is to **perform a given action in a given state**).\n",
    "* The notion of \"how good\" here is defined in terms of **future rewards** that can be expected, or, to be precise, in terms of expected return. \n",
    "* The **rewards** the agent can expect to receive in the future **depend on what actions** it will take. Accordingly, **value functions** are defined with respect to **particular ways of acting**, called **policies**.\n",
    "* Formally, a **policy** is a mapping from **states** to probabilities of selecting each possible **action**.\n",
    "* If the agent is following policy $\\pi$ at time $t$, then $\\pi(a|s)$ is the probability that $A_t=a$, if $S_t=s$.\n",
    "\n",
    "#### State-value function\n",
    "* The **value function** of a state $s$ under a policy $\\pi$, denoted $v_{\\pi}(s)$, is the **expected return** when starting in $s$ and following $\\pi$ thereafter. For MDPs, we can define $v_{\\pi}$ formally by:\n",
    "$$\n",
    "v_{\\pi}(s) = \\mathbb{E}_{\\pi}[G_t|S_t=s] = \\mathbb{E}_{\\pi}[\\sum_{k=0}^{\\infty} \\gamma^k R_{t+k+1}|S_t=s]\\text{, for all } s \\in \\mathcal{S}\n",
    "$$\n",
    "* We call the function $v_\\pi$ the **state-value function for policy $\\pi$**.\n",
    "* Note that the **value** of the **terminal state**, if any, is always **zero**.\n",
    "\n",
    "\n",
    "#### Action-value function\n",
    "* Similarly, we define the **value** of **taking action a in state** $s$ under a policy $\\pi$, denoted $q_{\\pi}(s, a)$, as the **expected return** starting from $s$, taking the action $a$, and thereafter following policy $\\pi$:\n",
    "$$\n",
    "q_{\\pi}(s, a) = \\mathbb{E}_{\\pi}[G_t|S_t=s,A_t=a] = \\mathbb{E}_{\\pi}[\\sum_{k=0}^{\\infty} \\gamma^k R_{t+k+1}|S_t=s,A_t=a]\n",
    "$$\n",
    "* We call the function $q_\\pi$ the **action-value function for policy $\\pi$**.\n",
    "\n",
    "#### Estimating value functions\n",
    "* The value functions $v_{\\pi}$ and $q_{\\pi}$ can be **estimated** from experience. \n",
    "  - For example, if an agent follows policy ${\\pi}$ and maintains an **average** (for each **state** encountered) of the actual **returns** that have followed that state, then the average will converge to the **state's value**, $v_{\\pi}(s)$, as the number of times that state is encountered approaches infinity.\n",
    "  - If separate averages are kept for **each action** taken in **each state**, then these averages will similarly converge to the **action values**, $q_{\\pi}(s, a)$.\n",
    "* We call estimation methods of this kind **Monte Carlo methods** because they involve **averaging over many random samples** of actual returns.\n",
    "* If there are very **many states**, then it may **not be practical** to keep **separate averages** for each state individually.\n",
    "  - Instead, the agent would have to maintain $v_{\\pi}$ and $q_{\\pi}$ as **parameterized functions** (with fewer parameters than states) and adjust the parameters to better match the observed returns.\n",
    "  \n",
    "  \n",
    "#### Bellman equation\n",
    "* A fundamental property of **value functions** used throughout RL is that they satisfy **recursive relationships**. \n",
    "* For any policy $\\pi$ and any state $s$, the following consistency condition holds between the value of $s$ and the value of its possible successor states:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_{\\pi}(s) ={} & \\mathbb{E}_{\\pi}[G_t|S_t=s]\\\\\n",
    "={} & \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma G_{t+1}|S_t=s]\\\\\n",
    "={} & \\sum_a \\pi(a|s)\\sum_{s',r}p(s',r|s,a)[r + \\gamma\\mathbb{E}_{\\pi}[G_{t+1}|S_{t+1}=s']]\\\\\n",
    "={} & \\sum_a \\pi(a|s)\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_{\\pi}(s')]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* This equation is the **Bellman equation** for $v_{\\pi}$, which expresses a relationship between the **value of a state** and the **values of its successor states**.\n",
    "* Here is the **backup diagram** for $v_{\\pi}$. The Bellman equation averages over all the possibilities, weighting each by its probability of occurring.\n",
    "<img src=\"rl_figs/rl_backup_diag.png\" width=\"250\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimal Policies and Optimal Value Functions\n",
    "* Solving a RL task means, roughly, **finding a policy** that achieves a lot of reward over the long run. \n",
    "* For **finite MDPs**, we can precisely define an optimal policy in the following way. \n",
    "  - Value functions define a partial ordering over policies. \n",
    "  - A policy $\\pi$ is defined to be **better than or equal** to a policy $\\pi'$, if its **expected return** is **greater than or equal** to that of $\\pi'$ for all states ($\\pi \\ge \\pi'$, if and only if $v_{\\pi}(s) \\ge v_{\\pi'}(s)$ for all $s \\in \\mathcal{S}$).\n",
    "* **Optimal policy**: there is always at least one policy that is better than or equal to all other policies. There may be more than one, we denote all the optimal policies by $\\pi_*$.\n",
    "* All optimal policies share the same **state-value function**, called the **optimal state-value function**, denoted $v_*$:\n",
    "$$\n",
    "v_*(s) = \\max_{\\pi}v_{\\pi}(s),\\text{ for all }s \\in \\mathcal{S}\n",
    "$$\n",
    "\n",
    "* Optimal policies also share the same **optimal action-value function**, denoted $q_*$, defined as:\n",
    "$$\n",
    "q_*(s,a) = \\max_{\\pi}q_{\\pi}(s,a),\\text{ for all }s \\in \\mathcal{S}\\text{ and }a \\in \\mathcal{A}\n",
    "$$\n",
    "* We can write $q_*$ in terms of $v_*$ as follows:\n",
    "$$\n",
    "q_*(s,a) = \\mathbb{E}[R_{t+1} + \\gamma v_*(S_{t+1})|S_t=s,A_t=a]\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Ch 4. Dynamic Programming\n",
    "\n",
    "* The term **dynamic programming (DP)** refers to a collection of algorithms that can be used to compute **optimal policies** given a **perfect model of the environment** as a **Markov decision process (MDP)**.\n",
    "* The rest of the methods presented in this book can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model of the environment.\n",
    "* We usually assume that the environment is a **finite MDP**.\n",
    "  - Its state, action, and reward sets, $S$, $A$, and $R$, are finite\n",
    "  - Its dynamics are given by a set of probabilities $p(s',r|s,a)$, for all $s \\in S$, $a \\in A(s)$, $r \\in R$, and $s' \\in S^+$ ($S^+$ is $S$ plus a terminal state if the problem is episodic).\n",
    "* DP ideas can also be applied to problems with **continuous state and action spaces**, exact solutions are possible only in special cases.\n",
    "  - A common way of obtaining approximate solutions for tasks with continuous states and actions is to **quantize the state and action spaces** and then apply finite-state DP methods.\n",
    "* The key idea of DP (and of RL generally), is the use of **value functions** to organize and structure the search for **good policies**.\n",
    "* As discussed before, we can obtain **optimal policies** once we have found the optimal **value functions**, $v_*(s)$ or $q_*(s, a)$, which satisfy the **Bellman optimality equations**.\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_*(s) ={} & \\max_{a}\\mathbb{E}[R_{t+1} + \\gamma v_*(S_{t+1})|S_t=s,A_t=a]\\\\\n",
    "={} & \\max_{a}\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_*(s')]\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "q_*(s,a) ={} & \\mathbb{E}[R_{t+1} + \\gamma \\max_{a'}q_*(S_{t+1}, a')|S_t=s,A_t=a]\\\\\n",
    "={} & \\sum_{s',r}p(s',r|s,a)[r + \\gamma \\max_{a'}q_*(s', a')]\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "### Policy Evaluation (Prediction)\n",
    "* **Policy evaluation** refers to the computation of the **state-value function** $v_\\pi$ for a given **policy** $\\pi$.\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_{\\pi}(s) ={} & \\mathbb{E}_{\\pi}[G_t|S_t=s]\\\\\n",
    "={} & \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma G_{t+1}|S_t=s]\\\\\n",
    "={} & \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma v_{\\pi}(S_{t+1})|S_t=s]\\\\\n",
    "={} & \\sum_a \\pi(a|s)\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_{\\pi}(s')]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* The existence and uniqueness of $v_\\pi$ are guaranteed as long as either $\\gamma < 1$ or eventual termination is guaranteed from all states under the policy $\\pi$.\n",
    "* Although its solution is a straightforward, iterative solution methods are most suitable.\n",
    "  - Consider a sequence of **approximate value functions** $v_0, v_1, v_2, \\cdots$, each mapping $\\mathcal{S}^+$ to $\\mathbb{R}$ (the real numbers).\n",
    "  - The initial approximation, $v_0$ is chosen arbitrarily, and each successive approximation is obtained by using the **Bellman equation** for $v_\\pi$ as an update rule:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_{k+1}(s) ={} & \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma v_{k}(S_{t+1})|S_t=s]\\\\\n",
    "={} & \\sum_a \\pi(a|s)\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_{k}(s')]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* **Iterative policy evaluation**: the sequence $\\{v_k\\}$ can be shown in general to converge to $v_{\\pi}$ as $k \\rightarrow \\infty$ under the same conditions.\n",
    "* To produce each successive approximation ($v_{k+1}$ from $v_k$), **iterative policy evaluation** applies the same **operation** to each state $s$:\n",
    "  - It replaces the old value of $s$ with a new value obtained from the old values of the successor states of $s$, and the expected immediate rewards, along all the one-step transitions possible under the policy being evaluated.\n",
    "  - We call this kind of operation an **expected update**.\n",
    "<img src=\"rl_figs/rl_policy_eval.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy Improvement\n",
    "* **Policy improvement** refers to the computation of an **improved policy** given the **value function** for that **policy**.\n",
    "* Our reason for computing the **value function for a policy** is to help find **better policies**.\n",
    "* Suppose we have determined the value function $v_\\pi$ for an arbitrary deterministic policy $\\pi$.\n",
    "  - For some state $s$ we would like to know whether or not we should change the policy to deterministically choose an action $a \\neq \\pi(s)$.\n",
    "  - We know how good it is to follow the current policy from $s$ (i.e., $v_\\pi(s)$), but would it be better or worse to change to the new policy?\n",
    "  - One way to answer this question is to consider selecting $a$ in $s$ and thereafter following the existing policy $\\pi$.\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "q_{\\pi}(s, a) ={} & \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma v_{\\pi}(S_{t+1})|S_t=s,A_t=a]\\\\\n",
    "={} & \\sum_a \\pi(a|s)\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_{\\pi}(s')]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "  - If the above equation is greater than $v_{\\pi}(s)$, then it means that it is better to select $a$ once in $s$ and thereafter follow $\\pi$ all the time.\n",
    "* **Policy improvement**: Let $\\pi$ and $\\pi'$ be any pair of deterministic policies such that, for all $s \\in S$, $q_{\\pi}(s, \\pi'(s)) \\ge v_{\\pi}(s)$. Then the policy $\\pi'$ must be as good as, or better than, $\\pi$. That is, it must obtain greater or equal expected return from all states $s \\in S$, $v_{\\pi'}(s) \\ge v_{\\pi}(s)$.\n",
    "* The process of making a **new policy** that **improves** on an **original policy**, by making it greedy with respect to the value function of the original policy, is called **policy improvement**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Policy Iteration\n",
    "* Once a policy, $\\pi$, has been improved using $v_\\pi$ to yield a better policy, $\\pi'$, we can then compute $v_\\pi'$ and improve it again to yield an even better $v_\\pi''$.\n",
    "  - We thus obtain a **sequence** of monotonically improving policies and value functions:\n",
    "<img src=\"rl_figs/rl_policy_iter2.png\" width=\"500\">\n",
    "  - $E$ denotes a **policy evaluation**, and $I$ denotes a **policy improvement**.\n",
    "* Each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). \n",
    "* Because a finite MDP has only a finite number of policies, this process must converge to an optimal policy and optimal value function in a finite number of iterations.\n",
    "<img src=\"rl_figs/rl_policy_iter.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Value Iteration\n",
    "* One **drawback** to **policy iteration** is that each of its iterations involves **policy evaluation**.\n",
    "  - Each **policy evaluation** may itself be a protracted iterative computation requiring **multiple sweeps** through the state set.\n",
    "  - If **policy evaluation** is done **iteratively**, then convergence exactly to $v_{\\pi}$ occurs only in the limit.\n",
    "* The **policy evaluation** step of **policy iteration** can be truncated in several ways without losing the convergence guarantees of policy iteration. \n",
    "* One important special case is when **policy evaluation** is stopped after **just one sweep** (one update of each state). This algorithm is called **value iteration**.\n",
    "* The **value iteration** can be written as a simple update operation that combines the policy improvement and truncated policy evaluation steps:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_{k+1}(s) ={} & \\mathbb{E}_a[R_{t+1} + \\gamma v_{k}(S_{t+1})|S_t=s,A_t=a]\\\\\n",
    "={} & \\max_a\\sum_{s',r}p(s',r|s,a)[r + \\gamma v_{k}(s')]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "<img src=\"rl_figs/rl_value_iter.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generalized Policy Iteration\n",
    "* **Policy iteration** consists of two simultaneous, interacting processes:\n",
    "  1. **Policy-evaluation**: makes the **value function** consistent with the **current policy**.\n",
    "  2. **Policy-improvement**: makes the **policy greedy** with respect to the **current value function**.\n",
    "<img src=\"rl_figs/rl_gpi.png\" width=\"170\">\n",
    "* In **policy iteration**, these two processes alternate, each completing before the other begins, but this is **not necessary**. \n",
    "* In **value iteration** only a single iteration of policy evaluation is performed in between each policy improvement.\n",
    "* **Generalized Policy Iteration (GPI)** refers to the general idea of letting **policy-evaluation** and **policy-improvement** processes interact, independent of the granularity and other details of the two processes.\n",
    "* Almost all RL methods are well described as GPI, i.e., all have identifiable **policies** and **value functions**, with the policy always being improved with respect to the value function and the value function always being driven toward the value function for the policy (as suggested by the above diagram).\n",
    "* If both the **evaluation** process and the **improvement** process stabilize (i.e., no longer produce changes), then the value function and policy must be **optimal**.\n",
    "  - The value function stabilizes only when it is consistent with the current policy, and the policy stabilizes only when it is greedy with respect to the current value function.\n",
    "  - Thus, both processes stabilize only when a policy has been found that is greedy with respect to its own evaluation function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Ch 5. Monte Carlo Methods\n",
    "* Our first learning methods for **estimating value functions** and **discovering optimal policies**.\n",
    "* Unlike DP, here we do not assume **complete knowledge of the environment**.\n",
    "* **Monte Carlo (MC)** methods require only **experience**, i.e., sample sequences of states, actions, and rewards from **actual** or **simulated** interaction with an environment.\n",
    "  - Learning from **actual experience** is striking because it requires **no prior knowledge** of the environment's dynamics, yet can still attain optimal behavior. \n",
    "  - Learning from **simulated experience** requires a **model**, however the model needs **only generate sample transitions**, not the complete probability distributions of all possible transitions that is required for dynamic programming (DP). \n",
    "* To ensure that **well-defined returns** are available, here we define MC methods only for **episodic tasks**.\n",
    "  - An experience is divided into episodes.\n",
    "  - All episodes eventually terminate no matter what actions are selected.\n",
    "  - Only on the completion of an episode the value estimates and policies are changed.\n",
    "* MC methods can thus be incremental in an **episode-by-episode sense**, but not in a step-by-step (online) sense.\n",
    "* MC methods sample and average returns for each state-action pair much like the **bandit** methods.\n",
    "  - The main difference is that now there are **multiple states**, each acting like a different bandit problem.\n",
    "  - That is, the return after taking an action in one state depends on the actions taken in later states in the same episode. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Monte Carlo Prediction\n",
    "* We consider MC methods for learning the **state-value function** for a **given policy**, i.e., $v_{\\pi}(s)$.\n",
    "* Recall that the **value of a state** is the **expected return** (expected cumulative future discounted reward) starting from that state.\n",
    "* One way to estimate it from **experience** is to **average** the **returns** observed after visits to that **state**. This idea underlies all **MC methods**.\n",
    "* Each occurrence of state s in an episode is called a **visit** to $s$.\n",
    "  - A state $s$ may be visited multiple times in the same episode.\n",
    "* We call the first time a state $s$ is visited in an episode the **first visit** to $s$. \n",
    "* The **first-visit MC** method estimates $v_{\\pi}(s)$ as the average of the returns following **first visits** to $s$.\n",
    "* The **every-visit MC** method averages the returns following **all visits** to $s$.\n",
    "* First-visit MC is shown in procedural form in the box. Every-visit MC would be the same except without the check for $S_t$ having occurred earlier in the episode.\n",
    "* Both first-visit MC and every-visit MC converge to $v_{\\pi}(s)$ as the number of visits (or first visits) to $s$ goes to infinity.\n",
    "<img src=\"rl_figs/rl_first_visit_mc.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Monte Carlo Estimation of Action Values\n",
    "* If a **model is not available**, then it is useful to estimate **action-values** rather than **state-values**.\n",
    "* **With a model**, **state-values** alone are **sufficient** to determine a **policy**.\n",
    "  - One simply looks ahead **one step** and chooses whichever **action** leads to the best combination of **reward** and **next state** (as in DP).\n",
    "* **Without a model**, state-values alone are **not sufficient**.\n",
    "  - One must explicitly **estimate** the **value of each action** in order for the values to be useful in suggesting a policy.\n",
    "  - One of goals for MC methods is to estimate $q_*$ (to achieve this, we consider the **policy evaluation** problem for **action-values**).\n",
    "* The **policy evaluation** problem for **action-values** is to estimate $q_{\\pi}(s, a)$, i.e., the expected return when starting in state $s$, taking action $a$, and thereafter following policy $\\pi$.\n",
    "* A state-action pair $(s, a)$ is said to be **visited** in **an episode**, if ever the state $s$ is visited and action $a$ is taken in it.\n",
    "* The **first-visit MC** method averages the returns following the first time in each episode that the state was visited and the action was selected.\n",
    "* The **every-visit MC** method estimates the value of a state-action pair as the average of the returns that have followed all the visits to it. \n",
    "* The only **complication** is that many state-action pairs **may never be visited**.\n",
    "  - This is a serious problem because the purpose of learning action values is to help in choosing among the actions available in each state.\n",
    "  - To compare alternatives we need to estimate the value of all the actions from each state, not just the one we currently favor.\n",
    "  - This is the general problem of maintaining exploration, as discussed in the k-armed bandit problem.\n",
    "* For **policy evaluation** to work for **action-values**, we must assure **continual exploration**.\n",
    "  - The episodes start in a state-action pair, and that every pair has a **non-zero probability** of being selected as the start.\n",
    "  - This assumption is called **exploring starts**.\n",
    "  - An alternative approach to assuring that all state-action pairs are encountered is to consider only policies that are stochastic with a non-zero probability of selecting all actions in each state."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Monte Carlo Control\n",
    "* How MC estimation can **approximate optimal policies**?\n",
    "* The overall idea is to proceed according to the idea of generalized policy iteration (GPI).\n",
    "  - In GPI one maintains both an **approximate policy** and an **approximate value function**.\n",
    "<img src=\"rl_figs/rl_gpi_action.png\" width=\"200\">\n",
    "<img src=\"rl_figs/rl_policy_iter3.png\" width=\"500\">\n",
    "\n",
    "* $E$ denotes a **complete policy evaluation**, and $I$ denotes a **complete policy improvement**.\n",
    "* **Policy evaluation** is done exactly as described in DP.\n",
    "* **Policy improvement** is done by making the policy greedy with respect to the current value function.\n",
    "  - In this case we have an **action-value function**, and therefore **no model is needed** to construct the greedy policy. \n",
    "  - For any action-value function $q$, the corresponding greedy policy is the one that, for each $s \\in S$, deterministically chooses an action with maximal action-value: $\\pi(s) = \\arg\\max_a q(s, a)$.\n",
    "* For the moment, we assume that we observe an **infinite number of episodes** and the episodes are generated with **exploring starts**.\n",
    "* Here, we made two unlikely assumptions to obtain the guarantee of convergence for the MC method.\n",
    "  1. The episodes have **exploring starts**.\n",
    "  2. The **policy evaluation** could be done with an **infinite number of episodes**.\n",
    "* To obtain a practical algorithm we will have to remove both assumptions.\n",
    "* There are two ways to solve the second assumption (inifinite number of episodes):\n",
    "  1. To hold firm to the idea of approximating $q_{\\pi_k}$ in each policy evaluation.\n",
    "  2. To give up trying to complete policy evaluation before returning to policy improvement. On each evaluation step we move the value function **toward** $q_{\\pi_k}$, but we do not expect to actually get close except over many steps. One extreme form of the idea is **value iteration**, in which only one iteration of iterative policy evaluation is performed between each step of policy improvement. \n",
    "* A complete algorithm of **Monte Carlo with Exploring Starts (ES)** is given below.\n",
    "<img src=\"rl_figs/rl_mc_es.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Monte Carlo Control without Exploring Starts\n",
    "* How can we avoid the unlikely assumption of **exploring starts**?\n",
    "* The only general way to ensure that **all actions are selected** infinitely often is for the agent to **continue to select them**.\n",
    "* There are two approaches to ensuring this: **on-policy** methods and **off-policy** methods\n",
    "* **On-policy** methods attempt to evaluate or improve the **policy that is used to make decisions**.\n",
    "* **Off-policy** methods evaluate or improve a **policy different from that used to generate the data**.\n",
    "* The **MC ES** method is an example of an **on-policy** method. \n",
    "* In **on-policy** methods the policy is generally **soft**, meaning that $\\pi(a|s) > 0$ for all $s \\in S$ and all $a \\in A(s)$, but **gradually** shifted closer and closer to a **deterministic optimal policy**.\n",
    "* The on-policy method in this section uses **$\\varepsilon$-greedy policies**: most of the time they choose an **action** that has **maximal estimated action-value**, but with **probability $\\varepsilon$** they instead select an action at **random**.\n",
    "  - The probability of selection of **non-greedy actions**: $\\frac{\\varepsilon}{|A(s)|}$\n",
    "  - The probability of selection of **greedy actions**: $1 - \\varepsilon + \\frac{\\varepsilon}{|A(s)|}$\n",
    "* The **$\\varepsilon$-soft policies** are the policies for which $\\pi(a|s) \\ge \\frac{\\varepsilon}{|A(s)|}$, for all states and actions, for some $\\epsilon > 0$. \n",
    "  - The $\\varepsilon$-greedy policies are examples of $\\varepsilon$-soft policies.\n",
    "* The overall idea of **on-policy** MC control is that of GPI.\n",
    "  - As in **MC ES**, we use **first-visit** MC methods to **estimate the action-value** function for the current policy.\n",
    "  - Without the assumption of **exploring starts**, however, we cannot simply improve the policy by making it greedy with respect to the current value function, because that would **prevent further exploration** of non-greedy actions. \n",
    "  - Fortunately, GPI does not require that the policy be taken all the way to a greedy policy, only that it be moved toward a greedy policy. In our on-policy method we will move it only to an $\\varepsilon$-greedy policy.\n",
    "<img src=\"rl_figs/rl_onpolicy_mc.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Off-policy Prediction via Importance Sampling\n",
    "* How can control methods learn about the **optimal policy** while behaving according to an **exploratory policy**?\n",
    "  - The **on-policy** approach in the preceding section learns action values not for the optimal policy, but for a near-optimal policy that still explores.\n",
    "* A more straightforward approach is to use **two policies**:\n",
    "  - The **target policy**: a policy that **is learned** about and that becomes the **optimal policy**.\n",
    "  - The **behavior policy**: a policy that **is exploratory** and is used to **generate behavior**.\n",
    "* In this case we say that learning is from data **off** the target policy, and the overall process is termed **off-policy** learning.\n",
    "- **On-policy** methods are generally simpler, and **off-policy** methods are often of greater variance and are slower to converge, but on the other hand are more powerful and general.\n",
    "* In this section we study off-policy methods by considering the **prediction problem**, in which both **target and behavior policies are fixed**.\n",
    "  - $\\pi$ is the **target policy**, and $b$ is the **behavior policy**, and both policies are considered fixed and given.\n",
    "  -  We want to **estimate the expected returns** under the **target policy**, but all we have are **returns** $G_t$ due to the **behavior policy**.\n",
    "  - We want to estimate $v_{\\pi}$ or $q_{\\pi}$, but all we have are episodes following another policy $b$, where\n",
    "$b \\neq \\pi$.\n",
    "* In order to use episodes from $b$ to estimate values for $\\pi$, we require that every action taken under $\\pi$ is also taken, at least occasionally, under $b$, i.e., $\\pi(a|s) > 0$ implies $b(a|s) > 0$: this is called the **assumption of coverage**.\n",
    "* It follows from coverage that $b$ must be **stochastic** in states where it is not identical to $\\pi$, and the target policy $\\pi$, on the other hand, may be **deterministic**.\n",
    "  - In control, the **target policy** is typically the **deterministic greedy policy** (deterministic optimal policy) w.r.t. the current estimate of the action-value function. \n",
    "  - The **behavior policy** remains **stochastic and more exploratory**, e.g., $\\varepsilon$-greedy policy.\n",
    "  - Here, we consider the prediction problem, in which $\\pi$ is **unchanging and given**.\n",
    "\n",
    "#### Important Sampling\n",
    "* Almost all **off-policy** methods utilize **importance sampling**, a general technique for **estimating expected values** under **one distribution given samples from another**.\n",
    "* We apply importance sampling to off-policy learning by **weighting returns** according to the **relative probability of their trajectories** occurring under the **target and behavior policies**, called the **importance-sampling ratio**. \n",
    "* Given a starting state $S_t$, the **probability of the subsequent state–action trajectory**, $A_t, S_{t+1}, A_{t+1}, \\cdots, S_T$, occurring under any policy $\\pi$ is\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "Pr\\{A_t, S_{t+1}, A_{t+1}, \\cdots, S_T | S_t, A_t:T \\sim \\pi\\} ={} & \\pi(A_t|S_t)p(S_{t+1}|S_t,A_t)\\pi(A_{t+1}|S_{t+1})\\cdots p(S_T|S_{T-1},A_{T-1})\\\\\n",
    "={} & \\prod_{k=t}^{T-1}\\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "  - $p$ is the **state-transition probability** function.\n",
    "* The **relative probability of the trajectory** under the **target and behavior policies** (i.e., the **importance-sampling ratio**) is:\n",
    "$$\n",
    "\\rho_{t:T-1} = \\frac{\\prod_{k=t}^{T-1}\\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)}{\\prod_{k=t}^{T-1}b(A_k|S_k)p(S_{k+1}|S_k,A_k)} = \\frac{\\prod_{k=t}^{T-1}\\pi(A_k|S_k)}{\\prod_{k=t}^{T-1}b(A_k|S_k)}\n",
    "$$\n",
    "  - The **trajectory probabilities** depend on the **MDP's transition probabilities** (which are generally unknown), but they appear identical here, and thus cancel.\n",
    "\n",
    "#### Calculating the average returns from a batch of observed episodes following policy $b$ to estimate $v_{\\pi}(s)$\n",
    "* Recall that we wish to **estimate the expected returns** under the **target policy** $\\pi$, but all we have are **returns** $G_t$ due to the **behavior policy** $b$. \n",
    "  - These returns have the wrong expectation $\\mathbb{E}[G_t|S_t=s] = v_b(s)$ and so cannot be averaged to obtain $v_{\\pi}$. This is where **importance sampling** comes in.\n",
    "  - The ratio $\\rho_{t:T-1}$ transforms the **returns** to have the right expected value: $\\mathbb{E}[\\rho_{t:T-1}G_t|S_t=s] = v_{\\pi}(s)$\n",
    "* Here, we assume that the number time steps **increases** across episode boundaries (e.g., if the first episode of the **batch** ends in a terminal state at time 100, then the next episode begins at time $t = 101$).\n",
    "* $\\mathcal{T}(s)$: the set of **all time steps** in which state $s$ is visited.\n",
    "* $T(t)$: the first time of termination following time $t$.\n",
    "* $G_t$: the return after $t$ up through $T(t)$.\n",
    "* $\\{G_t\\}_{t \\in \\mathcal{T}(s)}$: the returns that pertain to state $s$.\n",
    "* $\\{\\rho_{t:T(t)-1}\\}_{t \\in \\mathcal{T}(s)}$: the corresponding importance-sampling ratios.\n",
    "* **Ordinary importance sampling**: when importance sampling is done as a simple average:\n",
    "$$\n",
    "V(s) = \\frac{\\sum_{t \\in \\mathcal{T}(s)}\\rho_{t:T(t)-1}G_t}{|\\mathcal{T}(s)|}\n",
    "$$\n",
    "* **Weighted importance sampling**: when a weighted average is used:\n",
    "$$\n",
    "V(s) = \\frac{\\sum_{t \\in \\mathcal{T}(s)}\\rho_{t:T(t)-1}G_t}{\\sum_{t \\in \\mathcal{T}(s)}\\rho_{t:T(t)-1}}\n",
    "$$\n",
    "\n",
    "#### Incremental implementation\n",
    "* Suppose we have a **sequence of returns** $G_1, G_2, \\cdots, G_{n-1}$, all starting in the **same state**, and each with a corresponding **random weight** $W_i$ (e.g., $W_i = \\rho_{t_i:T(t_i)-1}$).\n",
    "* We wish to form the estimate $V_n$, and keep it up-to-date as we obtain a single additional return $G_n$:\n",
    "$$\n",
    "V_n = \\frac{\\sum_{k=1}^{n-1}W_kG_k}{\\sum_{k=1}^{n-1}W_k}, n \\ge 2\n",
    "$$\n",
    "\n",
    "* In addition to keeping track of $V_n$, we must maintain for **each state** the cumulative sum $C_n$ of the **weights** given to the **first $n$ returns** ($C_0 = 0$):\n",
    "$$\n",
    "C_{n+1} = C_n + W_{n+1}\n",
    "$$\n",
    "\n",
    "* The update rule for $V_n$ is:\n",
    "$$\n",
    "V_{n+1} = V_n + \\frac{W_n}{C_n}[G_n - V_n], n \\ge 1\n",
    "$$\n",
    "\n",
    "* Below is a complete episode-by-episode incremental algorithm for MC policy evaluation.\n",
    "<img src=\"rl_figs/rl_offpolicy_mc.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Off-policy Monte Carlo Control\n",
    "* Now, lets present **off-policy MC control** methods.\n",
    "* Recall that an advantage of this separating target and behavior policies is that the **target policy** may be **deterministic** (e.g., greedy), while the **behavior policy** can continue to **sample all possible actions**.\n",
    "* Off-policy methods follow the **behavior policy**, while learning about and improving the **target policy**.\n",
    "  - These techniques require that the behavior policy has a **non-zero probability** of selecting **all actions** that might be selected by the target policy (**coverage**).\n",
    "  - To **explore all possibilities**, we require that the **behavior policy** be **soft** (i.e., that it select all actions in all states with non-zero probability).\n",
    "* The following box shows an **off-policy MC control** method (based on GPI and weighted importance sampling) for estimating $\\pi_*$ and $q_*$.\n",
    "* The **target policy** $\\pi \\approx \\pi_*$ is the greedy policy with respect to $Q$, which is an estimate of $q_{\\pi}$. \n",
    "* The **behavior policy** $b$ can be anything, but in order to assure convergence of $\\pi$ to the optimal policy, an infinite number of returns must be obtained for each pair of state and action (this can be assured by choosing $b$ to be $\\varepsilon$-soft).\n",
    "<img src=\"rl_figs/rl_offpolicy_mc_control.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Ch 6. Temporal-Difference Learning\n",
    "* **Temporal-Difference (TD)** learning is a combination of **Monte Carlo (MC)** and **Dynamic Programming (DP)** ideas.\n",
    "  - Like **MC**, TD methods can **learn directly from raw experience without a model** of the environment's dynamics.\n",
    "  - Like **DP**, TD methods update **estimates based in part on other learned estimates, without waiting for a final outcome** (they **bootstrap**)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Temporal-Difference Prediction\n",
    "* Both TD and MC methods use **experience** to solve the **prediction** problem.\n",
    "  - Given some experience following a **policy** $\\pi$, both methods update their **estimate** $V$ of $v_{\\pi}$ for the non-terminal states $S_t$ occurring in that experience.\n",
    "  \n",
    "* **MC** methods must **wait until the end of the episode** to estimate $V(S_t)$ (only then is $G_t$ **known**):\n",
    "$$\n",
    "V(S_t) \\leftarrow V(S_t) + \\alpha[G_t - V(S_t)]\n",
    "$$\n",
    "  - $G_t$ is the **actual return** following time $t$.\n",
    "  - $\\alpha$ is a constant **step-size** parameter.\n",
    "  - This MC method is called **constant-$\\alpha$** MC.\n",
    "  \n",
    "* **TD** methods need to **wait only until the next time step**, and at time $t+1$ they can estimate $V(S_t)$:\n",
    "$$\n",
    "V(S_t) \\leftarrow V(S_t) + \\alpha[R_{t+1} + \\gamma V(S_{t+1}) - V(S_t)]\n",
    "$$\n",
    "  - $R_{t+1}$ is the observed reward at time $t+1$.\n",
    "  - $V(S_{t+1})$ is the value estimate at time $t+1$.\n",
    "  - This TD method is called **TD(0)** or **one-step TD**.\n",
    "\n",
    "* The **target** for the **MC update** is $G_t$, whereas the **target** for the **TD update** is $R_{t+1} + V(S_{t+1})$.\n",
    "\n",
    "* Because **TD(0)** bases its update in part on an **existing estimate**, we say that it is a **bootstrapping** method, like DP.\n",
    "\n",
    "* We know that\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "v_{\\pi}(s) ={} & \\mathbb{E}_{\\pi}[G_t | S_t=s]\\\\\n",
    "={} & \\mathbb{E}_{\\pi}[R_{t+1}+\\gamma G_{t+1} | S_t=s]\\\\\n",
    "={} & \\mathbb{E}_{\\pi}[R_{t+1}+\\gamma v_{\\pi}(S_{t+1}) | S_t=s]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "* **MC** methods use an estimate of $\\mathbb{E}_{\\pi}[G_t | S_t=s]$ as a **target**, whereas **DP** methods use an estimate of $\\mathbb{E}_{\\pi}[R_{t+1}+\\gamma v_{\\pi}(S_{t+1})|S_t=s]$ as a **target**.\n",
    "  - The **MC target** is an **estimate**, because the expected value in $\\mathbb{E}_{\\pi}[G_t | S_t=s]$ is not known (a **sample return** is used in place of the real expected return).\n",
    "  - The **DP target** is an **estimate**, because $v_{\\pi}(S_{t+1})$ is not known and the current estimate, $V(S_{t+1})$, is used instead.\n",
    "  - The **TD target** is an **estimate** for both reasons: it samples the expected values in $\\mathbb{E}_{\\pi}[R_{t+1}+\\gamma v_{\\pi}(S_{t+1})|S_t=s]$ and it uses the current estimate $V$ instead of the true $v_{\\pi}$.\n",
    "  \n",
    "* We refer to **TD** and **MC** updates as **sample updates** because they involve looking ahead to a **sample successor** state (or state-action pair), using the **value of the successor** and the **reward along the way** to compute a backed-up value, and then **updating the value** of the original state (or state-action pair) accordingly. \n",
    "\n",
    "* **Sample updates** differ from the **expected updates** of **DP** methods in that they are based on a **single sample successor** rather than on a **complete distribution** of all possible successors.\n",
    "  \n",
    "* The boxes below specifies **DP** and **CM** evaluation (prediction) process, as well as **TD(0)** completely in procedural form.\n",
    "<img src=\"rl_figs/rl_policy_eval.png\" width=\"700\">\n",
    "<img src=\"rl_figs/rl_first_visit_mc.png\" width=\"700\">\n",
    "<img src=\"rl_figs/rl_td0.png\" width=\"700\"><br>\n",
    "\n",
    "* **TD** methods have an advantage over **DP** methods in that they do **not require a model** of the environment, of its reward and next-state probability distributions. An advantage of **TD** methods over **MC** methods is that they are naturally implemented in an online, fully **incremental fashion**.\n",
    "\n",
    "* The quantity in brackets in the TD(0) update (i.e., $V(S_t) \\leftarrow V(S_t) + \\alpha[R_{t+1} + \\gamma V(S_{t+1}) - V(S_t)]$) is called the **TD error**:\n",
    "$$\n",
    "\\delta_t = R_{t+1} + \\gamma V(S_{t+1}) - V(S_t)\n",
    "$$\n",
    "\n",
    "* The **TD error** at each time is the **error in the estimate** made at that time, which depends on the **next state** and **next reward** (thus $\\delta_t$, the error in $V(S_t)$, is available at time $t+1$).\n",
    "\n",
    "* The **MC error** can be written as a sum of **TD errors**:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "G_t - V(S_t) ={} & R_{t+1}+\\gamma G_{t+1} - V(S_t) + \\gamma V(S_{t+1}) - \\gamma V(S_{t+1})\\\\\n",
    "={} & \\delta_t + \\gamma(G_{t+1} - V(S_{t+1}))\\\\\n",
    "={} & \\delta_t + \\gamma\\delta_{t+1} + \\gamma^2(G_{t+2} - V(S_{t+2}))\\\\\n",
    "={} & \\delta_t + \\gamma\\delta_{t+1} + \\gamma^2\\delta_{t+2} + \\cdots + \\gamma^{T-t-1}\\delta_{T-1} + \\gamma^{T-t}(G_T - V(S_T))\\\\\n",
    "={} & \\delta_t + \\gamma\\delta_{t+1} + \\gamma^2\\delta_{t+2} + \\cdots + \\gamma^{T-t-1}\\delta_{T-1} + \\gamma^{T-t}(0 - 0)\\\\\n",
    "={} & \\sum_{k=t}^{T-1}\\gamma^{k-t}\\delta_k\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sarsa: On-policy TD Control\n",
    "* We turn now to the use of **TD prediction** methods for the **control problem**.\n",
    "\n",
    "* As usual, we follow the pattern of **generalized policy iteration (GPI)**, only this time using **TD** methods for the **evaluation or prediction** part. \n",
    "\n",
    "* As with MC methods, we face the need to trade of **exploration and exploitation**, and again approaches fall into two main classes of **on-policy and off-policy**.\n",
    "\n",
    "* The first step is to learn an **action-value function** rather than a state-value function. In particular, for an **on-policy** method we must **estimate** $q_{\\pi}(s, a)$ for the current **behavior policy** $\\pi$ and for all **states** $s$ and **actions** $a$. \n",
    "\n",
    "* Recall that an **episode** consists of an alternating **sequence of states and state-action** pairs:\n",
    "<img src=\"rl_figs/rl_sarsa.png\" width=\"500\"><br>\n",
    "\n",
    "* We consider transitions from **state-action pair to state-action pair**, and learn the **values of state-action** pairs.\n",
    "$$\n",
    "Q(S_t, A_t) \\leftarrow Q(S_t, A_t) + \\alpha[R_{t+1} + \\gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]\n",
    "$$\n",
    "\n",
    "* This **update** is done after every transition from a non-terminal state $S_t$. If $S_{t+1}$ is **terminal**, then $Q(S_{t+1}, A_{t+1})$ is defined as **zero**. \n",
    "\n",
    "* This rule uses every element of the **quintuple of events**, $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$, that make up a transition from one **state-action pair to the next**. \n",
    "\n",
    "* This quintuple $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$ gives rise to the name **Sarsa**\n",
    "\n",
    "* To design an **on-policy control** algorithm based on the **Sarsa** prediction method, we continually estimate $q_{\\pi}$ for the **behavior policy** $\\pi$, and at the same time change $\\pi$ toward greediness with respect to $q_{\\pi}$.\n",
    "\n",
    "* Sarsa **converges** with probability 1 to an **optimal policy and action-value function** as long as **all state-action** pairs are **visited an infinite** number of times and the **policy** converges in the limit to the **greedy** policy (e.g., with $\\varepsilon$-greedy policies by setting $\\varepsilon = 1/t$).\n",
    "\n",
    "* The general form of the Sarsa control algorithm is given in the box on the next page.\n",
    "<img src=\"rl_figs/rl_sarsa_estimate.png\" width=\"700\"><br>\n",
    "\n",
    "* **Expected sarsa** is just like **Q-learning** (explained below) except that instead of the **maximum over next state-action pairs** it uses the expected value, taking into account **how likely each action is under the current policy**.\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "Q(S_t, A_t) \\leftarrow{} & Q(S_t, A_t) + \\alpha[R_{t+1} + \\gamma\\mathbb{E}[Q(S_{t+1}, A_{t+1}) | S+{t+1}] - Q(S_t, A_t)]\\\\\n",
    "\\leftarrow{} & Q(S_t, A_t) + \\alpha[R_{t+1} + \\gamma\\sum_a\\pi(a | S_{t+1})Q(S_{t+1}, a) - Q(S_t, A_t)]\\\\\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q-learning: Off-Policy TD Control\n",
    "* An **off-policy TD control** algorithm known as **Q-learning**:\n",
    "$$\n",
    "Q(S_t, A_t) \\leftarrow Q(S_t, A_t) + \\alpha[R_{t+1} + \\gamma\\max_aQ(S_{t+1}, a) - Q(S_t, A_t)]\n",
    "$$\n",
    "\n",
    "* The **learned action-value function**, $Q$, directly approximates $q_*$, the **optimal action-value function**, independent of the policy being followed. \n",
    "\n",
    "* All that is required for correct **convergence** is that all pairs continue to be updated (this is a minimal requirement to **find optimal behavior**).\n",
    "  - Under this assumption and a variant of the usual stochastic approximation conditions on the sequence of step-size parameters, $Q$ has been shown to converge with probability 1 to $q_*$.\n",
    "  \n",
    "* The **Q-learning** algorithm is shown below in procedural form.\n",
    "\n",
    "<img src=\"rl_figs/rl_qlearning.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximization Bias and Double Learning\n",
    "* All the **control algorithms** that we have discussed so far involve **maximization** in the construction of their **target policies**.\n",
    "  - In **Q-learning** the **target policy** is the **greedy policy** given the current action values, which is defined with a **max**.\n",
    "  - In **Sarsa** the **policy** is often **$\\varepsilon$-greedy**, which also involves a **maximization** operation. \n",
    "  \n",
    "* In these algorithms, a **maximum over estimated values** is used implicitly as an **estimate of the maximum value**, which can lead to a significant **positive bias**. \n",
    "  - To see why, consider a **single state** $s$, where there are **many actions** $a$ whose **true values**, $q(s, a)$, are all **zero**, but whose **estimated values**, $Q(s, a)$, are **uncertain** (distributed some above and some below zero).\n",
    "  - The **maximum of the true values is zero**, but the **maximum of the estimates is positive**, a positive bias. We call this **maximization bias**.\n",
    "  \n",
    "* One way to view the **maximization bias** problem is that it is due to using the **same samples** both to determine the **maximizing action** and to **estimate its value**.\n",
    "\n",
    "* Suppose we divided the samples in **two sets** and used them to **learn two independent estimates**, call them $Q_1(a)$ and $Q_2(a)$, each an **estimate of the true value** $q(a)$, for all $a \\in A$.\n",
    "  - We could then use one estimate, say $Q_1$, to determine the **maximizing action** $A^* = \\arg\\max_a Q_1(a)$, and the other, $Q_2$, to provide the **estimate of its value**, $Q_2(A^*) = Q_2(\\arg\\max_a Q_1(a))$.\n",
    "  - This estimate will then be **unbiased** in the sense that $\\mathbb{E}[Q_2(A^*)] = q(A^*)$. \n",
    "  \n",
    "* We can repeat the process with the role of the **two estimates reversed** to yield a second unbiased estimate $Q_1(\\arg\\max_a Q_2(a))$. This is the idea of **double learning**. \n",
    "\n",
    "* Although we learn **two estimates**, only **one estimate** is updated on each play.\n",
    "\n",
    "* Double learning doubles the memory requirements, but does not increase the amount of computation per step.\n",
    "\n",
    "* The double learning algorithm analogous to Q-learning, called **Double Q-learning**, divides the time steps in two, perhaps by **flipping a coin on each step**.\n",
    "  - If the **coin comes up heads**, the update is\n",
    "$$\n",
    "Q_1(S_t, A_t) \\leftarrow Q_1(S_t, A_t) + \\alpha[R_{t+1} + \\gamma Q_2(S_{t+1}, \\arg\\max_a Q_1(S_{t+1}, a)) - Q_1(S_t, A_t)]\n",
    "$$\n",
    "  - If the **coin comes up tails**, then the **same update** is done with $Q_1$ and $Q_2$ switched, so that $Q_2$ is updated. \n",
    "  - The **two approximate value functions** are treated completely **symmetrically**.\n",
    "  - The **behavior policy** can use both action-value estimates. \n",
    "  \n",
    "<img src=\"rl_figs/rl_double_qlearning.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Ch 7. n-step Bootstrapping\n",
    "* Here, we unify the **Monte Carlo (MC)** methods and the **one-step temporal-difference (TD)** methods.\n",
    "\n",
    "* To do so, we present **n-step TD** methods that generalize both methods, such that they span a spectrum with **MC** methods at one end and **one-step TD** methods at the other. The best methods are\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### n-step TD Prediction\n",
    "* What is the **space of methods** lying between **MC and TD** methods? \n",
    "  - Consider estimating $v_{\\pi}$ from **sample episodes** generated using $\\pi$.\n",
    "  - **MC** methods perform an **update** for each **state** based on the **entire** sequence of **observed rewards** from that state until the end of the episode.\n",
    "  - **One-step TD** methods perform an **update** for each **state** based on just the **one next reward** (**bootstrapping** from the value of the state one step later as a proxy for the remaining rewards).\n",
    "  \n",
    "* An **intermediate** method, then, would perform an **update** based on an **intermediate number of rewards**: more than one, but less than all of them until termination.\n",
    "  - E.g., a **two-step** update would be based on the first two rewards and the estimated value of the state two steps later.\n",
    "  \n",
    "<img src=\"rl_figs/rl_nstep_td.png\" width=\"500\"><br>\n",
    "\n",
    "* The methods that use **n-step updates** are still **TD methods** because they still change an **earlier estimate** based on **how it differs from a later estimate**.\n",
    "  - Now the later estimate is not one-step later, but **n-steps** later.\n",
    "  \n",
    "* Methods in which the TD extends over n-steps are called **n-step TD** methods.\n",
    "\n",
    "* Consider the update of the **estimated value of state** $S_t$ as a result of the **state-reward** sequence, $S_t, R_{t+1}, S_{t+1}, R_{t+2}, \\cdots, R_T, S_T$ (omitting the actions). \n",
    "  - In **MC** updates the estimate of $v_{\\pi}(S_t)$ is updated in the direction of the **complete return**:\n",
    "$$\n",
    "G_t = R_{t+1} + \\gamma R_{t+2} + \\gamma^2 R_{t+3} + \\cdots + \\gamma^{T-t-1}R_T\n",
    "$$\n",
    "  - $T$ is the last time step of the episode.\n",
    "  \n",
    "* We call this quantity the **target of the update**.\n",
    "  - In **MC** updates the target is the **return**.\n",
    "  - In **one-step TD** updates the target is the **first reward plus the discounted estimated value of the next state**, which we call the **one-step return**: $G_{t:t+1} = R_{t+1} + \\gamma V_t(S_{t+1})$.\n",
    "  - $V_t : \\mathcal{S} \\rightarrow \\mathbb{R}$ is the **estimate** of $v_{\\pi}$ at time $t$.\n",
    "  - $G_{t:t+1}$ is a **truncated return** for time $t$ using rewards up until time $t+1$.\n",
    "  - E.g., the target for a **two-step update** is the **two-step return**: $G_{t:t+2} = R_{t+1} + \\gamma R_{t+2} + \\gamma^2 V_{t+1}(S_{t+2})$.\n",
    "\n",
    "* The target for an arbitrary **n-step update** is the **n-step return**:\n",
    "$$\n",
    "G_{t:t+n} = R_{t+1} + \\gamma R_{t+2} + \\cdots + \\gamma^{n-1} R_{t+n} + \\gamma^n V_{t+n-1}(S_{t+n})\n",
    "$$\n",
    "\n",
    "* If $t+n \\ge T$ (if the n-step return extends to or beyond termination), then all the missing terms are taken as zero: $G_{t:t+n} = G_t$ if $t+n \\ge T$.\n",
    "\n",
    "* The natural **state-value** learning algorithm for using n-step returns is:\n",
    "$$\n",
    "V_{t+n}(S_t) = V_{t+n-1}(S_t) + \\alpha[G_{t:t+n} - V_{t+n-1}(S_t)]\n",
    "$$\n",
    "  - The values of **all other states** remain unchanged: $V_{t+n}(s) = V_{t+n-1}(s)$, for all $s \\ne S_t$.\n",
    "  \n",
    "* We call this algorithm **n-step TD**. Note that no changes at all are made during the first $n-1$ steps of each episode. \n",
    "\n",
    "* An important property of n-step returns is that their **expectation** is guaranteed to be a **better estimate** of $v_{\\pi}$ than $V_{t+n-1}$ is, in a worst-state sense. \n",
    "  - That is, the **worst error** of the **expected n-step return** is guaranteed to be less than or equal to $\\gamma^n$ times the worst error under $V_{t+n-1}$\n",
    "$$\n",
    "\\max_s|\\mathbb{E}_{\\pi}[G_{t:t+n} | S_t=s] - v_{\\pi}(s)| \\le \\gamma^n \\max_s|V_{t+n-1} - v_{\\pi}(s)|\n",
    "$$\n",
    "  - This is called the **error reduction property** of n-step returns.\n",
    "\n",
    "<img src=\"rl_figs/rl_nstep_td_estimate.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## n-step Sarsa\n",
    "* How can n-step methods be used not just for prediction, but for **control**? \n",
    "* Here, we combine **n-step methods** with **Sarsa** to produce an **on-policy TD control** method. \n",
    "* We call the n-step version of Sarsa as **n-step Sarsa**, and the original version as **one-step Sarsa** or **Sarsa(0)**.\n",
    "* The main idea is to simply switch states for actions (**state-action pairs**) and then use an $\\varepsilon$-**greedy** policy. \n",
    "\n",
    "* The backup diagrams for n-step Sarsa, like those of n-step TD, are strings of alternating states and actions, except that the Sarsa ones all start and end with an **action rather a state**.\n",
    "<img src=\"rl_figs/rl_nstep_sarsa.png\" width=\"500\"><br>\n",
    "\n",
    "* We redefine **n-step returns (update targets)** in terms of **estimated action values**:\n",
    "$$\n",
    "G_{t:t+n} = R_{t+1} + \\gamma R_{t+2} + \\cdots + \\gamma^{n-1}R_{t+n} + \\gamma^nQ_{t+n-1}(S_{t+n}, A_{t+n}), n \\ge 1, 0 \\le t \\le T-n\n",
    "$$\n",
    "$$\n",
    "G_{t:t+n} = G_t, \\mbox{if } t + n \\ge T\n",
    "$$\n",
    "\n",
    "* The natural algorithm is then:\n",
    "$$\n",
    "Q_{t+n}(S_t, A_t) = Q_{t+n-1}(S_t, A_t) + \\alpha[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)], 0 \\le t \\le T\n",
    "$$\n",
    "  - while the values of all other states remain unchanged: $Q_{t+n}(s, a) = Q_{t+n-1}(s, a)$, for all $s, a$ such that $s \\neq S_t$ or $a \\neq A_t$. This is the algorithm we call **n-step Sarsa**.\n",
    "  \n",
    "<img src=\"rl_figs/rl_nstep_sarsa_estimate.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## n-step Off-policy Learning\n",
    "* Recall that **off-policy learning** is learning the **value function** for one policy, $\\pi$ (called **greedy policy**), while following another policy, $b$ (called **exploratory policy**).\n",
    "* In order to use the data from $b$ we must take into account the **difference between the two policies**, using their **relative probability of taking the actions that were taken**.\n",
    "* In n-step methods, **returns** are constructed over **n steps**, so we are interested in the relative **probability of just those n actions**. \n",
    "  - For example, to make a simple off-policy version of **n-step TD**, the update for time $t$ (actually made at time $t+n$) can simply be weighted $\\pi_{t:t+n-1}$.\n",
    "$$\n",
    "V_{t+n}(S_t) = V_{t+n-1}(S_t) + \\alpha\\rho_{t:t+n-1}[G_{t:t+n} - V_{t+n-1}(S_t)], 0 \\le < t < T\n",
    "$$\n",
    "* $\\rho_{t:t+n-1}$, called the **importance sampling ratio**, is the **relative probability** under the **two policies of taking the n actions** from $A_t$ to $A_{t+n-1}$:\n",
    "$$\n",
    "\\rho_{t:h} = \\prod_{k=t}^{min(h, T-1)}\\frac{\\pi(A_k|S_k)}{b(A_k|S_k)}\n",
    "$$\n",
    "* If an actions **never be taken** by $\\pi$, then the n-step return should be given zero weight and be totally ignored. \n",
    "* If an action is taken that $\\pi$ would take with much **greater probability** than $b$ does, then this will **increase the weight** that would otherwise be given to the return. \n",
    "  - This makes sense because that action is **characteristic** of $\\pi$ (and therefore we want to learn about it), but is **selected only rarely** by $b$ and thus rarely appears in the data.\n",
    "  - To make up for this we have to **over-weight** it, when it does occur.\n",
    "* Note that if the **two policies are actually the same** (the **on-policy** case) then the importance sampling ratio is always 1. \n",
    "* A simple off-policy form:\n",
    "$$\n",
    "Q_{t+n}(S_t, A_t) = Q_{t+n-1}(S_t, A_t) + \\alpha\\rho_{t+1:t+n}[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)], 0 \\le < t < T\n",
    "$$\n",
    "* The importance sampling ratio here **starts and ends one step later** than for n-step TD, because here we are updating a **state-action pair**.\n",
    "* Pseudocode for the full algorithm is shown in the box below.\n",
    "<img src=\"rl_figs/rl_nstep_sarsa_offpolicy.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Part II: Approximate Solution Methods\n",
    "* In many of the tasks to which we would like to apply RL the **state space** is **combinatorial and enormous**, and we cannot expect to find an **optimal policy** or the **optimal value** function even in the limit of **infinite time and data**.\n",
    "* Here, our goal is to find a **good approximate solution** using **limited computational resources**.\n",
    "* To do so, we need to combine RL methods with existing **generalization** methods. \n",
    "* The kind of **generalization** we require is often called **function approximation**, because it takes examples from a desired function (e.g., a value function) and attempts to generalize from them to construct an approximation of the entire function.\n",
    "* **Function approximation** is an instance of **supervised learning**.\n",
    "* RL with function approximation involves a number of new issues that do not normally arise in conventional supervised learning, such as **nonstationarity**, **bootstrapping**, and **delayed targets**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Ch. 9 - On-policy Prediction with Approximation\n",
    "* Let's start with estimating the **state-value** function from **on-policy** data, that is, in approximating $v_{\\pi}$ from experience generated using a known policy $\\pi$.\n",
    "* The **approximate value function** is represented not as a table, but as a **parameterized functional** form with weight vector $\\mathbf{w} \\in \\mathbb{R}^d$.\n",
    "* $\\hat{v}(s,\\mathbf{w}) \\sim v_{\\pi}(s)$ shows he **approximate value of state** $s$ given weight vector $\\mathbf{w}$.\n",
    "  - E.g., $\\hat{v}$ might be a linear function or a multi-layer NN in features of the state, with $\\mathbf{w}$ the vector of feature weights or connection weights, respectively.\n",
    "* Typically, the number of weights (the dimensionality of $\\mathbf{w}$) is much less than the number of states.\n",
    "* Extending RL to function approximation makes it applicable to partially observable problems, in which the full state is not available to the agent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Value-function Approximation\n",
    "* All of the prediction methods covered in this book have been described as **updates** to an **estimated value function** that shift its **value at particular states** toward a **backed-up value** or **update target**, for that **state**.\n",
    "* We refer to an **individual update** by the notation $s \\longmapsto u$, where $s$ is the **state updated** and $u$ is the **update target** that $s$'s estimated value is shifted toward. The update $s \\longmapsto u$ means that the **estimated value** for state $s$ should be more like the update target $u$.\n",
    "  - MC update: $S_t \\longmapsto G_t$\n",
    "  - TD(0) update: $S_t \\longmapsto R_{t+1} + \\gamma\\hat{v}(S_{t+1}, \\mathbf{w}_t)$\n",
    "  - n-step TD update: $S_t \\longmapsto G_{t:t+n}$\n",
    "  - DP update: $S_t \\longmapsto \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma\\hat{v}(S_{t+1}, \\mathbf{w}_t) | S_t=s]$\n",
    "* We interpret **each update** as specifying an example of the desired **input-output** behavior of the **value function**. \n",
    "* In Part I, the actual update has been trivial: the table entry for $s$'s estimated value has simply been shifted a fraction of the way toward $u$, and the estimated values of all other states were left unchanged.\n",
    "* Now we permit arbitrarily complex and sophisticated methods to **implement the update**, and updating at $s$ generalizes so that the **estimated values of many other states are changed** as well.\n",
    "* ML methods that learn to **mimic input-output examples** in this way are called **supervised learning** methods, and when the outputs are numbers, like $u$, the process is often called **function approximation**. \n",
    "* **Function approximation** methods receive $s \\longmapsto u$ of **each update** as a training example. We then interpret the approximate function they produce as an **estimated value function**.\n",
    "  - We can use any method for supervised learning, such as ANN, decision trees, and various kinds of multivariate regression. \n",
    "* However, in RL, it is important that learning be able to occur **online**, while the agent interacts with its environment or with a model of its environment. Moreover, it requires function approximation methods able to handle **nonstationary target functions** (target functions that change over time).\n",
    "  - For example, in control methods based on GPI we often seek to learn $q_{\\pi}$ while $\\pi$ changes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Prediction Objective\n",
    "* In the **tabular case**, the **learned values at each state** are **decoupled** (i.e., an update at one state affcted no other), but with genuine **approximation**, an update at one state affcts many others, and it is not possible to get the values of all states exactly correct. \n",
    "* We can say **which states** we **care most** about, and a **state distribution** $\\mu(s) \\ge 0, \\sum\\mu(s) = 1$, representing how much we care about the **error in each state** $s$. \n",
    "  - Often $\\mu(s)$ is chosen to be the **fraction of time spent** in $s$.\n",
    "  - Under **on-policy** training this is called the **on-policy distribution**.\n",
    "* The **error in a state** $s$ is the square of the dfference between the approximate value $\\hat{v}(s, \\mathbf{w})$ and the true value $v_{\\pi}(s)$. Weighting this over the state space by $\\mu$, we obtain the **Mean Squared Value Error**, denoted $\\overline{\\rm VE}$.\n",
    "$$\n",
    "\\overline{\\rm VE}(\\mathbf{w}) = \\sum_{s \\in \\mathcal{S}}\\mu(s)[v_{\\pi}(s) - \\hat{v}(s, \\mathbf{w})]^2\n",
    "$$\n",
    "* Remember that our **ultimate purpose** is to find a **better policy**, however the best value function for this purpose is not necessarily the best for minimizing $\\overline{\\rm VE}$, but for now, we will focus on $\\overline{\\rm VE}$.\n",
    "* In the rest of this chapter we focus on **function approximation** methods based on **gradient** principles, and on linear **gradient-descent** methods in particular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stochastic-gradient and Semi-gradient Methods\n",
    "* In **gradient-descent** methods, the **weight vector** is a column vector with a fixed number of real valued components, $\\mathbf{w} = (w_1, w_2, \\cdots, w_d)^\\top$, and the approximate value function $\\hat{v}(s,\\mathbf{w})$ is a differentiable function of $\\mathbf{w}$ for all $s \\in \\mathcal{S}$.\n",
    "* $\\mathbf{w}_t$ is the weight vector at different step ($\\mathbf{w}$ is updated at each of a series of discrete time steps, $t = 0, 1, 2, 3, \\cdots$).\n",
    "* Let's assume that, on each step, we observe a new example $S_t \\longmapsto v_{\\pi}(S_t)$ consisting of a state $S_t$ and its true value under the policy. \n",
    "* We assume that **states appear in examples** with the **same distribution** $\\mu$, over which we are trying to minimize the $\\overline{\\rm VE}$.\n",
    "* A good strategy in this case is to try to **minimize error on the observed examples**, using **Stochastic gradient-descent (SGD)**:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\mathbf{w}_{t+1} ={} & \\mathbf{w}_t - \\frac{1}{2}\\alpha\\nabla[v_{\\pi}(S_t) - \\hat{v}(S_t, \\mathbf{w}_t)]^2\\\\\n",
    "={} & \\mathbf{w}_t + \\alpha[v_{\\pi}(S_t) - \\hat{v}(S_t, \\mathbf{w}_t)]\\nabla\\hat{v}(S_t, \\mathbf{w}_t)\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* Assume the target output $U_t$ of the $t$th training example $S_t \\longmapsto U_t$, is not the true value $v_{\\pi}(S_t)$, but some, possibly random, approximation to it. In these cases we can approximate the update by substituting $U_t$ in place of $v_{\\pi}(S_t)$. This yields the following **general SGD method for state-value prediction**:\n",
    "$$\n",
    "\\mathbf{w}_{t+1} = \\mathbf{w}_t + \\alpha[U_t - \\hat{v}(S_t, \\mathbf{w}_t)]\\nabla\\hat{v}(S_t, \\mathbf{w}_t)\n",
    "$$\n",
    "* Assume the **states in the examples** are the states generated by interaction with the **environment** using policy $\\pi$. Because the **true value of a state** is the **expected value of the return following it**, the MC target $U_t = G_t$ is an **unbiased estimate** of $v_{\\pi}(S_t)$. With this choice, the general SGD method converges to a **locally optimal approximation** to $v_{\\pi}(S_t)$.\n",
    "* The gradient-descent version of **MC state-value prediction** is **guaranteed** to find a **locally optimal\n",
    "solution**.\n",
    "<img src=\"rl_figs/rl_gradient_mc.png\" width=\"700\">\n",
    "\n",
    "* One does not obtain the same guarantees if a **bootstrapping** estimate of $v_{\\pi}(S_t)$ (such as n-step returns $G_{t:t+n}$ or the DP) is used as the target $U_t$, because they will be **biased** and that they will not produce a true gradient-descent method. \n",
    "* Bootstrapping methods take into account the **effect of changing the weight vector** $\\mathbf{w}_t$ on the **estimate**, but ignore its effect on the **target**. Since they include only a part of the gradient, we call them **semi-gradient** methods.\n",
    "* Although **semi-gradient** (bootstrapping) methods **do not converge** as robustly as gradient methods, they do converge reliably in important cases (such as the linear case), and also they typically enable **significantly faster learning**. Moreover since they do not need to wait until the end of an episode, they can be used on continuing problems.\n",
    "* Complete pseudocode for the semi-gradient method is given in the box below.\n",
    "<img src=\"rl_figs/rl_semi_gradient.png\" width=\"700\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Methods\n",
    "* One important special case of **function approximation** is when the approximate function $\\hat{v}(·,\\mathbf{w})$ is a **linear function of the weight vector** $\\mathbf{w}$.\n",
    "* Corresponding to **every state** $s$, there is a real-valued vector $\\mathbf{x}(s) = (x_1(s), x_2(s), \\cdots, x_d(s))^\\top$, with the same number of components as $\\mathbf{w}$.\n",
    "* Linear methods approximate **state-value function** by the inner product between $\\mathbf{w}$ and $\\mathbf{x}(s)$:\n",
    "$$\n",
    "\\hat{v}(s, \\mathbf{w}) = \\mathbf{w}^\\top\\mathbf{x}(s) = \\sum_{i=1}^d w_ix_i(s)\n",
    "$$\n",
    "* In this case the **approximate value function** is said to be **linear**, and the vector $\\mathbf{x}(s)$ is called a **feature vector** representing state $s$.\n",
    "* Each component $x_i(s)$ of $\\mathbf{x}(s)$ is the value of a function $x_i: S \\rightarrow \\mathbb{R}$. We think of a **feature** as the entirety of one of these functions, and we call its value for a state $s$ a **feature** of $s$.\n",
    "* The gradient of the approximate value function with respect to w in this case is $\\nabla\\hat{v}(s,\\mathbf{w}) = \\mathbf{x}(s)$.\n",
    "* Thus, in the linear case the general SGD update reduces to a particularly simple form:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{aligned}\n",
    "\\mathbf{w}_{t+1} ={} & \\mathbf{w}_t + \\alpha[U_t - \\hat{v}(S_t, \\mathbf{w}_t)]\\nabla\\hat{v}(S_t, \\mathbf{w}_t)\\\\\n",
    "={} & \\mathbf{w}_t + \\alpha[U_t - \\hat{v}(S_t, \\mathbf{w}_t)]\\mathbf{x}(S_t)\n",
    "\\end{aligned}\n",
    "\\end{equation}\n",
    "$$\n",
    "* Pseudocode of the semi-gradient n-step TD algorithm is given in the box below.\n",
    "<img src=\"rl_figs/rl_nstep_semi_gradient.png\" width=\"700\">\n",
    "<br>\n",
    "* The key equation of this algorithm is\n",
    "$\n",
    "\\mathbf{w}_{t+n} = \\mathbf{w}_{t+n-1} + \\alpha[G_{t:t+n} - \\hat{v}(S_t, \\mathbf{w}_{t+n-1})]\\nabla\\hat{v}(S_t, \\mathbf{w}_{t+n-1}), 0 \\le t < T\n",
    "$\n",
    "* where the n-step return is generalized to:\n",
    "$\n",
    "G_{t:t+n} = R_{t+1} + \\gamma R_{t+2} + \\cdots + \\gamma^{n-1}R_{t+n} + \\gamma^n \\hat{v}(S_{t+n} + \\mathbf{w}_{t+n-1}), 0 \\le t < T\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Ch 10. On-policy Control with Approximation\n",
    "* Here, we restrict attention to the control problem of on-policy case, with parametric approximation of the **action-value** function $\\hat{q}(s, a, \\mathbf{w}) \\approx q_*(s, a)$, where $\\mathbf{w} \\in \\mathbb{R}^d$ is a finite-dimensional weight vector.\n",
    "* Here, we focus on **semi-gradient Sarsa algorithm**, the natural extension of **semi-gradient TD(0)** to action values and to on-policy control."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}