class_note.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# David Silver Reinforcement Learning Note\n",
    "\n",
    "## 目录\n",
    "\n",
    "- [Lecture 1 Introduction to Reinforcement Learning](#Lecture-1-Introduction-to-Reinforcement-Learning)\n",
    "- [Lecture 2 Markov Decision Processes](#Lecture-2-Markov-Decision-Processes)\n",
    "- [Lecture 3 Planning by Dynamic Programming](#Lecture-3-Planning-by-Dynamic-Programming)\n",
    "- [Lecture 4 Model Free Prediction](#Lecture-4-Model-Free-Prediction)\n",
    "- [Lecture 5 Model Free Control](#Lecture-5-Model-Free-Control)\n",
    "- [Lecture 6 Value Function Approximation](#Lecture-6-Value-Function-Approximation)\n",
    "- [Lecture 7 Policy Gradient](#Lecture-7-Policy-Gradient)\n",
    "- [Lecture 8 Integrating Learning and Planning](#Lecture-8-Integrating-Learning-and-Planning)\n",
    "- [Lecture 9 Exploration and Exploitation](#Lecture-9-Exploration-and-Exploitation)\n",
    "- [Lecture 10 Classic Games](#Lecture-10-Classic-Games)\n",
    "\n",
    "## 大致介绍\n",
    "\n",
    "介绍下课程推进的逻辑：\n",
    "\n",
    "第一章介绍基础概念，用着重分清楚`Reward`,`value function`和`q function`的区别。\n",
    "\n",
    "第二章介绍MDP，MDP是对环境的一种建模，即state将以一种什么样的方式推进是已知的。重点理解`Bellman Expectation Equation`和`Bellman Optimality Equation`，二者本质上都是递推公式，给动态规划打下基础。\n",
    "\n",
    "第三章介绍如何处理MDP，分为两步：`planning`和`controlling`。`planning`代表如何评估$v_{\\pi}$，`controlling`代表如何根据评估，找到最优的策略$\\pi_*$。解决方案包括`policy iteration`和`value iteration`。\n",
    "\n",
    "第四章介绍环境未知的情况下（model free），如何做planning。有两种方法：`MC（Monte-Carlo）`和`TD（Temporal Difference）`。\n",
    "\n",
    "第五章介绍环境未知的情况下，如何做`controlling`。又根据实验episode的产生，是不是依据目标policy，引出`On-Policy`和`Off-Policy`两种方法。主要的算法有：`On-Policy Monte-Carlo Control`，`On-Policy Sarsa Control`，`Off-Policy Q-learning`。\n",
    "\n",
    "第六章介绍在MDP表格太大的情况下，如何近似价值函数，主要介绍`Q-Learning with Linear Function Approximation`，`Deep-Q Learning（DQN）`。\n",
    "\n",
    "第七章同样针对第六章的情况，但是采用的方法是直接拟合策略函数，引入`Monte-Carlo Policy Gradient (REINFORCE)`，再分析纯policy gradient的问题，引入` Actor-Critic`。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 1 Introduction to Reinforcement Learning\n",
    "\n",
    "**奖励（Reward）**：$R_t$是$t$时刻的奖励。agent的任务是最大化**累积的（cumulative）**奖励。\n",
    "\n",
    "**观察（Observation）**：$O_t$，$t$时刻对环境的观察。\n",
    "\n",
    "**行动（Action）**：$A_t$，$t$时刻采取的行动。\n",
    "\n",
    "**历史（History）**：是一个序列的观察/奖励/行动（某时刻之前的所有时刻）。$H_t = A_1, O_1, R_1, ... A_t, O_t, R_t$。\n",
    "\n",
    "**状态（State）**：通过对历史信息的总结，决定接下来要发生什么。$S_t = f(H_t)$\n",
    "\n",
    "**环境状态（Environment State）**：某个环境的状态，$S_t^e$。\n",
    "\n",
    "**代理环境（Agent State）**：agent内部的环境，$S_t^a$。\n",
    "\n",
    "**马尔科夫状态（Markov state）**：状态$S_t$是马尔科夫状态，如果满足：$P[S_{t+1}|S_t] = P[S_{t+1}| S_1, ..., S_t]$，到这一步可以把**历史**丢掉了，只要每一步的状态即可。\n",
    "\n",
    "**全观测环境（Full observability）**：$O_t = S_t^a = S_t^e$。\n",
    "\n",
    "**部分观测环境（Partial observability）**：$S_t^a ≠ S_t^e$。\n",
    "\n",
    "**Policy**：Policy是agent的行为，是state到action的映射。确定形式：$a=\\pi (s)$；随机形式：$\\pi(a|s)=P[A_t=a|S_t=s]$。\n",
    "\n",
    "**Value**：Value是对未来reward的预测：$v_{\\pi}(s) = E_{\\pi}[R_{t+1}+\\gamma R_{t+2}+\\gamma ^2R_{t+3}+...|S_t=s]$\n",
    "\n",
    "**Model**：Model是对未来环境的预测：$\\textbf{P}$预测下一个state：$\\textbf{P}^a_{ss'}=P[S_{t+1}=s'|S_t=s,A_t=a]$，$\\textbf{R}$预测下一个即时的奖励：$\\textbf{R}_s^a=E[R_{t+1}|S_t=s,A_t=a]$。\n",
    "\n",
    "**Agent 分类**：\n",
    "- model based（model + policy and/or + value function）\n",
    "- model free:\n",
    "    - value based (value function)\n",
    "    - policy based (policy)\n",
    "    - actor critic (policy + value function)\n",
    "    \n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/agent.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 2 Markov Decision Processes\n",
    "\n",
    "**Markov Decision Process（MDP）**：思想：`The future is independent of the past given the present`，即某个时刻，agent所处在的状态，只和它上一个时刻所处的状态相关。是对**环境（实际上是state）**的一种描述。$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,...,S_t]$\n",
    "\n",
    "**状态转移矩阵（State Transition Matrix）**：$\\textbf{P}$其中，$\\textbf{P}_{ss'}=P[S_{t+1}=s'|S_t=s]$。\n",
    "\n",
    "**Markov Process**：由简单到复杂：\n",
    "- 包含$<\\textbf{S}, \\textbf{P}>$，即**状态集合**和**状态转移矩阵**。\n",
    "- MRP：包含$<\\textbf{S}, \\textbf{P}, \\textbf{R}, \\gamma>$，即增加了**奖励函数**和**折扣系数**，$ \\textbf{R}_s = E[\\textbf{R}_{t+1} | S_t = s]$。\n",
    "- 引入$G_t=R_{t+1} + \\gamma R_{t+2} + ... =\\sum^{\\infty}_{k=0}\\gamma^kR_{t+k+1}$，注意Value是期望，G是针对一个sample，$v(s) = E [G_t | S_t = s]$。\n",
    "- MDP:包含$<\\textbf{S}, \\textbf{A}, \\textbf{P}, \\textbf{R}, \\gamma>$，增加了$\\textbf{A}$，是有限的动作集合。$\\textbf{P}_{ss'}^a=P[S_{t+1}=s'|S_t=s,A_t=a]$，$\\textbf{R}_s^a=E[R_{t+1}|S_t=s,A_t=a]$。\n",
    "\n",
    "**episode**：一次实验序列，由一系列`(state, action, reward)`三元组构成。\n",
    "\n",
    "**$G_t$ vs. $v(s)$**：再次注意二者的区分：$G_t$刻画的是针对一个episode，在某一时刻$t$可以获得的长期奖励，这根据你的实验是可以计算出来的，因为你的试验中，每走一步会有一个$R_t$，$G_t=R_{t+1} + \\gamma R_{t+2} + ... =\\sum^{\\infty}_{k=0}\\gamma^kR_{t+k+1}$当然是可以计算的。$v_s$描述的是对某一个状态$s$的评价，我想不想经过这个状态。对状态的评价可以通过我在所有的episode中，只要状态是$s$的，我都计算一个$G_t$，然后把这些$G_t$求平均，就可以拿来评估这个状态的好坏，理论上，求平均应该是求期望。\n",
    "\n",
    "**MRP的Bellman Equation**：\n",
    "- 针对奖赏，有$$v(s) = E[G_t|S_t = s]\\\\=E[R_{t+1}+\\gamma v(S_{t+1})|S_t = s]\\\\=\\textbf{R}_s+\\gamma\\sum_{s'\\in S}\\textbf{P}_{ss'}v(s')$$\n",
    "- 矩阵形式：$v = R + \\gamma Pv$。\n",
    "- 直接求解，时间复杂度是$O(n^3)$。\n",
    "\n",
    "**Policy**：$\\pi$是给定状态之后动作的分布，即$\\pi(a|s)=P[A_t=a|S_t=s]$，policy可以完整地描述agent的行为，policy是独立于时间的。\n",
    "\n",
    "**MDP的state-value函数**：$v_{\\pi}(s)=E[G_t|S_t=s]$，即在状态$s$下，遵从policy-$\\pi$可以带来的长期奖励的期望。\n",
    "\n",
    "**MDP的action-value函数**：$q_{\\pi}(s,a) = E_{\\pi}[G_t|S_t=s, A_t=a]$，即在状态$s$下，采取了动作$a$，然后遵从policy-$\\pi$可以带来的长期奖励的期望。这是我们真正在乎的，我们需要知道哪个action更好！\n",
    "\n",
    "**q vs. v**：简单地说，$q$用来衡量某一个state下，采取某一个特定的action有多好，$v$用来衡量某一个state有多好。\n",
    "\n",
    "**MDP的Bellman Expectation Equation**：\n",
    "- $v_{\\pi}(s)=E_{\\pi}[R_{t+1}+\\gamma v_{\\pi}(S_{t+1})|S_t=s]$\n",
    "- $q_{\\pi}(s,a)=E_{\\pi}[R_{t+1}+\\gamma q_{\\pi}(S_{t+1}, A_{t+1})|S_t=s]$\n",
    "- $v_{\\pi}(s)=\\sum_{a\\in A}\\pi (a|s)q_{\\pi}(s,a)$\n",
    "- $q_{\\pi}(s,a)=\\textbf{R}_s^a+\\gamma\\sum_{s'\\in S}\\textbf{P}_{ss'}^av_{\\pi}(s')$\n",
    "- 最终：$v_{\\pi}(s)=\\sum_{a\\in A}\\pi (a|s)(\\textbf{R}_s^a+\\gamma\\sum_{s'\\in S}\\textbf{P}_{ss'}^av_{\\pi}(s'))$\n",
    "- 最终：$q_{\\pi}(s,a)=\\textbf{R}_s^a+\\gamma\\sum_{s'\\in S}\\textbf{P}_{ss'}^a\\sum_{a'\\in A}\\pi (a'|s')q_{\\pi}(s',a')$\n",
    "\n",
    "**MDP的Bellman Expectation Equation的矩阵形式**：\n",
    "- $v_{\\pi} = \\textbf{R}^{\\pi}+\\gamma\\textbf{P}^{\\pi}v_{\\pi}$\n",
    "\n",
    "**最优化的函数**：\n",
    "- $v_*(s)=\\underset{\\pi}{max}\\;v_{\\pi}(s)$\n",
    "- $q_*(s,a) = \\underset{\\pi}{max}\\;q_{\\pi}(s, a)$\n",
    "\n",
    "**policy的比较**：如果一个policy在所有state下，v都比比另一个policy大，那么可以说这个policy比另一个policy好。即，$\\pi > \\pi',\\;if\\;v_{\\pi}(s)≥v_{\\pi'}(s),\\forall s$\n",
    "\n",
    "**对于所有的MDP，都有**：\n",
    "- 存在最优policy，使得$\\pi_*≥\\pi,\\;\\forall \\pi$；\n",
    "- $v_{\\pi_*} = v_*(s)$；\n",
    "- $q_{\\pi_*}(s,a) = q_*(s,a)$。\n",
    "\n",
    "**假设已经找到$q_*(s,a)$，可以马上获得$\\pi_(a|s)$**：$\\pi_*(a|s)=\\left\\{\\begin{matrix}\n",
    "1\\;\\;if\\; a=\\underset{a\\in A}{argmax}\\;q_*(s,a)\\\\ \n",
    "0\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;otherwise\n",
    "\\end{matrix}\\right.$\n",
    "\n",
    "**Bellman Optimality Equation **：\n",
    "- for $v_*$：$v_*(s)=\\underset{a}{max}\\;q_*(s,a)$\n",
    "- for $q_*$：$q_*(s,a)=\\textbf{R}_s^a+\\gamma\\sum_{s'\\in S}\\textbf{P}_{ss'}^av_*(s')$\n",
    "\n",
    "**解决Bellman Optimality Equation的方法**：\n",
    "- Bellman Optimality Equation是非线性的，不能直接计算；\n",
    "- 迭代求解的方法：\n",
    "    - MDP：\n",
    "        - Value Iteration\n",
    "        - Policy Iteration\n",
    "    - Model Free：\n",
    "        - Q-learning\n",
    "        - Sarsa\n",
    "\n",
    "**Bellman Equation总结**：\n",
    "- Bellman Equation可以理解成某一时刻在某一状态下的value可以拆分成即时奖励和一下一个时刻开始所有可能的状态的价值的期望。\n",
    "- 它本身是一个递推公式，可以设计一个`backup`表格，不断进行更新。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 3 Planning by Dynamic Programming\n",
    "\n",
    "\n",
    "**动态规划（Dynamic Programming）**：\n",
    "- 给定MDP，用于MDP的**planning**；\n",
    "- **prediction**：\n",
    "    - 输入：MDP：$<\\textbf{S}, \\textbf{A}, \\textbf{P}, \\textbf{R}, \\gamma>$和policy：$\\pi$；或者MRP：$<\\textbf{S}, \\textbf{P}^{\\pi}, \\textbf{R}^{\\pi}, \\gamma>$。\n",
    "    - 输出：$v_{\\pi}$的值。\n",
    "- **control**:\n",
    "    - 输入：MDP：$<\\textbf{S}, \\textbf{A}, \\textbf{P}, \\textbf{R}, \\gamma>$。\n",
    "    - 输出：最优化的policy：$\\pi_*$\n",
    "\n",
    "**Iterative Policy Evaluation**：\n",
    "- 评估一个给定的policy：$\\pi$。\n",
    "- 使用Bellman Expectation Equation解决。\n",
    "- 迭代过程：$v_1\\to v_2\\to ...\\to v_{\\pi}$\n",
    "- 使用synchronous backups，在第$k+1$步迭代：\n",
    "    - 对所有的状态$s\\in S$\n",
    "    - 通过$v_k(s')$更新$v_{k+1}(s)$，$v_{k+1}(s) = \\sum_{a\\in A}\\pi(a|s)(R_s^a + \\gamma\\sum_{s'\\in S}P_{ss'}^av_k(s'))$，矩阵形式：$\\textbf{v}^{k+1}=\\textbf{R}^{\\pi}+\\gamma\\textbf{P}^{\\pi}\\textbf{v}^k$，其中$s'$是$s$的后继状态。\n",
    "\n",
    "**Policy Iteration**：\n",
    "- 目标：寻找最优policy：$\\pi_*$。\n",
    "- 给定一个policy：$\\pi$：\n",
    "    - Evaluate这个policy：$v_{\\pi}(s)=E[G_t|S_t=s]=E[R_{t+1}+\\gamma R_{t+2}+...|S_t = s]$\n",
    "    - Improve这个policy：$\\pi'=greedy(v_{\\pi})$\n",
    "- 最终会收敛到$\\pi_*$。\n",
    "\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/policy_evaluation.png)\n",
    "\n",
    "**Value Iteration**：\n",
    "- 目标：寻找最优policy：$\\pi_*$。\n",
    "- 使用Bellman Optimality Equation解决。\n",
    "- 迭代过程：$v_1\\to v_2\\to ...\\to v_*$。\n",
    "- 使用synchronous backups，在第$k+1$步迭代：\n",
    "    - 对所有的状态$s\\in S$\n",
    "    - 通过$v_k(s')$更新$v_{k+1}(s)$，矩阵形式：$\\textbf{v}_{k+1}=\\underset{a \\in A}{max}(\\;\\textbf{R}^a+\\gamma\\textbf{P}^a\\textbf{v}_k)$。这一步叫“one-step lookahead”。\n",
    "- 中间过程没有特定的policy。\n",
    "\n",
    "**Policy Iteration vs. Value Iteration**：\n",
    "- Policy Iteration: $v_1\\to \\pi \\to v_2$\n",
    "- Value Iteration：$v_1\\to v_2$\n",
    "- 中间的$v_i$可能没有对应的policy。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lecture 4 Model Free Prediction\n",
    "\n",
    "**Monte-Carlo 强化学习**：\n",
    "- model free：没有mdp或者reward。\n",
    "- 适用于所有的episode都会结束的情形。\n",
    "\n",
    "**Monte-Carlo Policy Evaluation**：\n",
    "- Goal：使用policy：$\\pi$，从经验序列（episode）：$S_1,A_1,R_2,...,S_k$中学习价值$v_{\\pi}$。\n",
    "- 回顾$v_{\\pi}=E_{\\pi}(s) = E_{\\pi}[G_t|S_t=s]$，Monte-Carlo**使用平均返回值代替期望返回值**。\n",
    "- 有以下两种方法。\n",
    "\n",
    "**First-Vist Monte-Carlo Policy Evaluation**：\n",
    "- 评估某个状态$s$。\n",
    "- 在某一个episode中，第一次发生状态$s$的是时间$t$。\n",
    "- 计数器自增：$N(s) \\leftarrow  N(s)+1$\n",
    "- $S(s)\\leftarrow S(s) + G_t$\n",
    "- 计算价值函数：$V(s) \\leftarrow  S(s)/N(s)$\n",
    "\n",
    "**Every-Visit Monte-Carlo Policy Evaluation**：类似于上面，只不过是每次出现状态$s$，都要纳入计算。\n",
    "\n",
    "**增量计算均值**：$\\mu=\\frac{1}{k}\\sum_{j=1}^kx_j\\\\=\\frac{1}{k}(x_k+(k-1)\\mu_{k-1})\\\\=\\mu_{k-1}+\\frac{1}{k}(x_k-\\mu_{k-1})$\n",
    "\n",
    "**增量式的Monte-Carlo更新**：\n",
    "- 对于每个Episode：$S_1, A_1, R_2, ..., S_T$结束完以后，增量地更新$V(s)$。\n",
    "- $N(S_t) \\leftarrow N(S_t) + 1$\n",
    "- $V(S_t)\\leftarrow V(S_t)+\\frac{1}{N(S_t)}(G_t-V(S_t))$\n",
    "- 可以写成$V(S_t)\\leftarrow V(S_t)+\\alpha (G_t-V(S_t))$\n",
    "\n",
    "**瞬时分差Temporal-Difference Learning**：\n",
    "- model free：没有mdp或者reward。\n",
    "- 适用于不完整的episode的情形，使用bootstrapping（bootstrapping代表更新的时候需要估计期望，而不是使用真的反馈）。\n",
    "- TD通过猜测来更新猜测。\n",
    "\n",
    "**TD**：\n",
    "- Goal：使用policy：$\\pi$，中学习价值$v_{\\pi}$。\n",
    "- 相比MC只是更新的式子不同：$V(S_t)\\leftarrow V(S_t)+\\alpha (R_{t+1}+\\gamma V(S_{t+1})-V(S_t))$\n",
    "- 其中，$R_{t+1} + γV(S_{t+1})$ 被称为`TD target`。\n",
    "- $δ_t = R_{t+1} + γV(S_{t+1}) − V(S_t)$ 称为`TD error`。\n",
    "\n",
    "**MC vs. TD**：\n",
    "- 用通俗的语言描述就是，对于某个state的value更新，MC会把这个state后面所有的state都计算R，用来计算G；而TD只会计算当前下一个状态的R，其他后面的R不算，采用当前估计的value来替代。\n",
    "- MC有高方差，0偏差，对初始值不敏感，使用sample，不使用bootstrapping。\n",
    "- TD往往更高效，且对初始值敏感，使用sample，使用bootstrapping。\n",
    "\n",
    "**n-step TD**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/n_step_td.png)\n",
    "\n",
    "**TD($\\lambda$)**：\n",
    "- Forward-view：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/td_lambda.png)\n",
    "- 每个n-step的$G_t$加权求和，权重：$(1-\\lambda)\\lambda^{n-1}$，$G_t^{\\lambda}=(1-\\lambda)\\sum^{\\infty}_{n=1}{\\lambda}^{n-1}G_t^{n}$\n",
    "- $V(S_t)\\leftarrow V(S_t) + \\alpha(G_t^{\\lambda}-V(S_t))$\n",
    "\n",
    "**Forward-view和Backward-view**：\n",
    "- Forward-view只能计算完整的episodes。\n",
    "- Backward-view可以计算不完整的episodes。\n",
    "- Forward-view提供了理论。\n",
    "- Backward-view提供了机制。\n",
    "- Forward-view倾向于最高频的状态。\n",
    "\n",
    "**Eligibility Traces**：\n",
    "- Eligibility Traces结合了高频的倾向和最近的倾向。\n",
    "- $E_0(s) = 0$\n",
    "- $E_t(s) = \\gamma\\lambda E_{t-1}(s) + \\textbf{1}(S_t=s)$，累加代表了高频倾向；但之前的时刻会衰减代表了最近的倾向。\n",
    "\n",
    "**Backward-view TD($\\lambda$)**：\n",
    "- $\\delta_t=R_{t+1}+\\gamma V(S_{t+1} - V(S_t))$\n",
    "- $V(s)\\leftarrow V(s)+\\alpha \\delta_t E_t(s)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lecture 5 Model Free Control\n",
    "\n",
    "**On-policy learning vs. Off-policy learning**：\n",
    "- on代表在任务中学习，从采样的$\\pi$中学习$\\pi$。（自学）\n",
    "- off代表在某种基础上学习，从采样的$\\mu$中学习$\\pi$。（有人示范）\n",
    "\n",
    "**On-Policy Monte-Carlo Control**：\n",
    "- policy evaluation：Monte-Carlo policy evaluation，$Q≈q_{\\pi}$。\n",
    "- policy improvement：$\\epsilon$-greedy policy improvement\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/mc_policy_iteration.png)\n",
    "\n",
    "**为什么使用Q？**：V的`greedy policy improvement`依赖于MDP，而Q的则不需要。\n",
    "\n",
    "**$\\epsilon$-greedy policy improvement**：\n",
    "- $\\pi(a|s)=\\left\\{\\textbf{}\\begin{matrix}\\epsilon/m+1-\\epsilon\\;\\;\\;if\\;a*=\\underset{a\\in A}{argmax}Q(s,a)\\\\ \\epsilon/m\\;\\;\\;otherwise\\end{matrix}\\right.$\n",
    "- 即，有$\\epsilon$的可能是随机选择。\n",
    "\n",
    "**Greedy in the Limit with Infinite Exploration (GLIE)**：\n",
    "- 希望上面提到的$\\epsilon$是衰减的，即到最后的时候，直接采用贪婪选择。\n",
    "\n",
    "**On-Policy Sarsa Control**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/sarsa_2.png)\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/sarsa.png)\n",
    "- 所谓sarsa即，1.使用$\\epsilon$-greedy，根据$s$，选择$a$；2.获得奖励$r$，和新的状态$s'$；3.再使用$\\epsilon$-greedy，选择$a'$\n",
    "\n",
    "**n-step Sarsa**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/n_step_sarsa.png)\n",
    "\n",
    "**Forward View Sarsa($\\lambda$)**：\n",
    "- $q_t^{\\lambda}=(1-\\lambda)\\sum_{n=1}^{\\infty}\\lambda ^{n-1}q_t^{(n)}$\n",
    "- $Q(S_t, A_t) \\leftarrow Q(S_t, A_t) + \\alpha(q_t^{\\lambda}-Q(S_t, A_t))$\n",
    "\n",
    "**Backward View Sarsa($\\lambda$)**：\n",
    "- $E_0(s, a)= 0$\n",
    "- $E_t(s, a)=\\gamma\\lambda E_{t-1}(s, a)+\\mathbf{1}(S_t=s,A_t=a)$\n",
    "- $\\delta_t = R_{t+1} + \\gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)$\n",
    "- $Q(s, a)\\leftarrow Q(s, a)+\\alpha\\delta_tE_t(s,a)$\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/sarsa_lamda.png)\n",
    "\n",
    "**Off-Policy Learning**：behaviour policy：$\\mu(a|s)$，已知的，可以用来指导的策略。\n",
    "\n",
    "**Importance Sampling for Off-Policy Monte-Carlo**：\n",
    "- 重要性采样（估计期望）：$E_{x\\sim P}[f(X)] = \\sum P(X)f(X) = \\sum Q(x)\\frac{P(X)}{Q(X)}f(X) = E_{X\\sim Q}[\\frac{P(X)}{Q(X)}f(X)]$\n",
    "- $G_t^{\\pi/\\mu} = \\frac{\\pi(A_t|S_t)}{\\mu(A_t|S_t)} \\frac{\\pi(A_t|S_t)}{\\mu(A_t|S_t)} \\frac{\\pi(A_{t+1}|S_{t+1})}{\\mu(A_T|S_T)}G_t$\n",
    "- $V(S_t)\\leftarrow V(S_t) + \\alpha(G_t^{\\pi/\\mu}-V(S_t))$\n",
    "- 弊端：重要性采样将方差提高地非常大。\n",
    "\n",
    "**Q-Learning**：\n",
    "- off-policy。\n",
    "- 不需要重要性采样。\n",
    "- 下一个动作从behaviour policy中选择：$A_{t+1}\\sim \\mu(\\cdot|S_t)$\n",
    "- 备选的动作从target policy中选择：$A'\\sim \\pi(\\cdot|S_t)$，用于下面式子的计算。\n",
    "- 更新$Q(S_t, A_t)\\leftarrow Q(S_t, A_t)+\\alpha(R_{t+1}+\\gamma Q(S_{t+1}, A')-Q(S_t, A_t))$\n",
    "- target policy 是关于$Q(s,a)$的贪婪策略，有$\\pi(S_{t+1}) = \\underset{a'}{argmax}Q(S_{t+1}, a')$\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/q_learning_2.png)\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/q-learning.png)\n",
    "\n",
    "**MDP vs. Model Free**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/dp_td.png)\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/dp_td2.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lecture 6 Value Function Approximation\n",
    "\n",
    "**对于大型的MDP**：\n",
    "- 之前我们通过一张大表，表格上有$V(s)$或者$Q(s,a)$。\n",
    "- 对于大型的MDP问题，表格不再适用，于是可以估计价值函数。\n",
    "- $\\hat v(s, w) \\approx v_{\\pi}(s)$\n",
    "- $\\hat q(s,a,w) \\approx q_{\\pi}(s, a)$\n",
    "- 使用MC或者TD来更新$w$。\n",
    "\n",
    "**Value Function Approximation的种类**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/fun_app.png)\n",
    "\n",
    "**随机梯度下降**：\n",
    "- 先假设有个已知的$v_{\\pi}(S)$\n",
    "- 目标：$J(w) = E_{\\pi}[(v_{\\pi}(S)-\\hat v(S,w))^2]$\n",
    "- 梯度下降：$\\Delta w = -\\frac{1}{2}\\alpha\\triangledown_wJ(w)=\\alpha E_{\\pi}[(v_{\\pi}(S)-\\hat v(S,w))\\triangledown_w \\hat v(S,w)]$\n",
    "- 随机梯度下降只用sample其中一个：$\\Delta w =\\alpha (v_{\\pi}(S)-\\hat v(S,w))\\triangledown_w \\hat v(S,w)$\n",
    "\n",
    "**特征向量（Feature Vector）**：\n",
    "- 用来表示一个state。\n",
    "- $x(S) = \\begin{pmatrix}x_1(S)\\\\ ...\\\\ x_n(S)\\end{pmatrix}$\n",
    "\n",
    "**线性特征组合**：\n",
    "- 用特征的线性组合去表示value function。\n",
    "- $\\hat v(S, w) = x(S)^Tw=\\sum^n_{j=1}x_j(S)w_j$\n",
    "- $\\Delta w = \\alpha(v_{\\pi}(S)-\\hat v(S, w))x(S)$\n",
    "- 也就是 update = 步长×预测误差×特征值\n",
    "\n",
    "**增量预测算法（Incremental Prediction Algorithms）**：\n",
    "- 回到“$v_{\\pi}(S)$是未知的”这个事实。\n",
    "- 我们使用以下的方法，不同的方法使用不同的量去替代$v_{\\pi}(S)$，称为“TD-Target”。\n",
    "- $MC$：使用$G_t$，$\\Delta w = \\alpha(G_t - \\hat v(S_t, w))\\triangledown_w\\hat v(S_t, w)$\n",
    "- $TD(0)$：使用$R_{t+1}+\\gamma \\hat v(S_{t+1}, w)$，$\\Delta w = \\alpha(R_{t+1}+\\gamma \\hat v(S_{t+1}, w) - \\hat v(S_t, w))\\triangledown_w\\hat v(S_t, w)$\n",
    "- $TD(\\lambda)$：使用$G_t^{\\lambda}$，$\\Delta w = \\alpha(G_tt^{\\lambda} - \\hat v(S_t, w))\\triangledown_w\\hat v(S_t, w)$\n",
    "\n",
    "**Action-Value Function Approximation**：和Value Function Approximation类似。\n",
    "\n",
    "**Control with Value Function Approximation**：\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/control_VFA.png)\n",
    "更详细的迭代步骤：\n",
    "- 在每个episode的每一步：\n",
    "    - 使用policy选择下一步的action。\n",
    "    - 使用approximate function计算Q函数，greedy选择让Q最大的state作为后继。\n",
    "    - 使用Q函数计算TD-Target。\n",
    "    - 使用TD-Target，利用梯度下降，更新Q函数。\n",
    "\n",
    "**Batch Reinforcement Learning**：思想：从经验中学习最多的知识，而不仅仅是碰到一个事件，改变一下想法。\n",
    "\n",
    "**Least Squares Prediction**：\n",
    "- 给定近似v函数：$\\hat v(s,w) \\approx v_{\\pi}(s)$\n",
    "- 给定经验数据$D$，由`<state, value>`对构成：$D=\\{<s_1, v_1^{\\pi}>, ..., <s_T, v_T^{\\pi}>\\}$\n",
    "- $LS(w) = \\sum_{t=1}^T(v_t^{\\pi}-\\hat v(s_t, w))^2$\n",
    "\n",
    "**带经验回放的随机梯度下降（Stochastic Gradient Descent with Experience Replay）**：\n",
    "- $\\Delta w = \\alpha(v^{\\pi}-\\hat v(s,w))\\triangledown_w\\hat v(s,w)$\n",
    "- 最终收敛到最小平方差：$w^{\\pi} = \\underset{w}{argmin}LS(w)$\n",
    "\n",
    "**带经验回放的DQN（Experience Replay in Deep Q-Networks）**：\n",
    "- 1.使用$\\epsilon-greedy$在policy中选择动作$a_t$。\n",
    "- 2.保存$(s_t, a_t, r_{t+1}, s_{t+1})$到回放记忆$D$。\n",
    "- 3.从$D$中抽一个mini-batch：$(s, a, r, s')$。\n",
    "- 4.使用老参数$w^-$计算Q-learning target（fixed Q-learning target）。\n",
    "- 5.优化Q-network和Q-learning之间的MSE：$L_i(w) = E_{s, a, r, s' \\sim D_i}[(r + \\gamma \\underset{a'}{max}Q(s', a'; w_i^-))^2]$\n",
    "- 两个Trick：**经验回放Experience Replay**，**fixed Q-learning target**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lecture 7 Policy Gradient\n",
    "\n",
    "**Policy-Based Reinforcement Learning**：\n",
    "- 直接参数化policy：$\\pi_{\\theta}(s,a)=P[a|s, \\theta]$。\n",
    "- 优点：\n",
    "    - 更好的收敛性。\n",
    "    - 在高维空间和连续的动作空间更有效。\n",
    "    - 可以学习随机的policy。\n",
    "- 缺点：\n",
    "    - 通常收敛到局部最优。\n",
    "    - 评估一个policy通常是低效且高方差的。\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/pv.png)\n",
    "\n",
    "**policy的目标函数**：\n",
    "- 目标：给定一个policy：$\\pi_{\\theta}(s, a)$，找到最好的参数：$\\theta$。\n",
    "- episodic 环境：使用**start value**：$J_1(\\theta)=V^{\\pi_{\\theta}}(s_1) = E_{\\pi_{\\theta}}[v_1]$。如果总是从$s_1$开始，最终$v_1$的期望。\n",
    "- continuing 环境：使用**average value**：$J_{av}V(\\theta) = \\sum_sd^{\\pi_{\\theta}}(s)V^{\\pi_{\\theta}}(s)$\n",
    "- 或者：使用**average reward per time-step**：$J_{avR}(\\theta) = \\sum_sd^{\\pi_{\\theta}}(s)\\sum_a\\pi_{\\theta}(s, a)R^a_s$\n",
    "- 其中：$d^{\\pi_{\\theta}}(s)$是**stationary distribution**。\n",
    "\n",
    "**Score Function**：\n",
    "- 这是一个计算的trick。\n",
    "- 假设已经知道梯度：$\\triangledown_{\\theta}\\pi_{\\theta}(s, a)$\n",
    "- Likelihood ratios：$\\triangledown_{\\theta}\\pi_{\\theta}(s, a) = \\pi_{\\theta}(s, a)\\frac{\\triangledown_{\\theta}\\pi_{\\theta}(s, a)}{\\pi_{\\theta}(s, a)} = \\pi_{\\theta}(s, a)\\triangledown_{\\theta}log\\pi_{\\theta}(s, a)$\n",
    "- score function：$\\triangledown_{\\theta}log\\pi_{\\theta}(s, a)$\n",
    "\n",
    "**Softmax Policy**：\n",
    "- 采用某个动作的概率正比于指数的特征权重：$\\pi_{\\theta}(s,a)\\propto e^{\\phi(s,a)^T\\theta}$\n",
    "- score function：$\\triangledown log\\pi_{\\theta}(s,a) = \\phi(s,a) - E_{\\pi_{\\theta}}[\\phi(s,\\cdot)]$\n",
    "- 直觉：某个特征值越大（比均值大的越多），并获得更多的奖励，那我们就应该调整策略更多地执行这种动作。\n",
    "\n",
    "**Gaussian Policy**：\n",
    "- $\\mu(s) = \\phi(s)^T\\theta$\n",
    "- score function：$\\triangledown log\\pi_{\\theta}(s,a) = \\frac{(a-\\mu(s))\\phi(s)}{\\sigma^2}$\n",
    "\n",
    "**One-Step MDPs**：\n",
    "- $r = R_{s,a}$\n",
    "- 在单步MDP下，三种目标函数是等价的：$J(\\theta) = E_{\\pi_{\\theta}}[r]=\\sum_{s\\in S}d(s)\\sum_{a\\in A}\\pi_{\\theta(s, a)R_{s,a}}$\n",
    "- $\\triangledown_{\\theta} J(\\theta) = \\sum_{s\\in S}d(s)\\sum_{a\\in A}\\pi_{\\theta}(s,a)\\triangledown_{\\theta}\\pi_{\\theta}(s, a)R_{s,a} = E_{\\pi_{\\theta}}[\\triangledown_{\\theta}log\\pi_{\\theta}(s, a)r]$\n",
    "\n",
    "**推广到Multi-Step MDPs**：\n",
    "- 用$Q^{\\pi}(s,a)$替代即时奖励$r$。\n",
    "- $\\triangledown_{\\theta} J(\\theta) =  E_{\\pi_{\\theta}}[\\triangledown_{\\theta}log\\pi_{\\theta}(s, a)Q^{\\pi}(s,a)]$\n",
    "\n",
    "**Monte-Carlo Policy Gradient (REINFORCE)**：\n",
    "- 特点：慢，大方差。\n",
    "- 使用$v_t$作为$Q^{\\pi}(s,a)$的无偏估计。\n",
    "![](https://github.com/applenob/rl_learn/raw/master/res/mc_gradient_policy_2.png)\n",
    "\n",
    "**Action-Value Actor-Critic**：\n",
    "- 动机：减少方差\n",
    "- $Q_w(s,a)\\approx Q^{\\pi_{\\theta}}(s,a)$\n",
    "- Critic：更新Action-Value函数的参数$w$。比如线性TD(0)。\n",
    "- Actor：更新策略的参数$\\theta$，使用critic建议的方向。\n",
    "- $\\Delta\\theta = \\alpha\\triangledown_{\\theta}log\\pi_{\\theta}(s,a)Q_w(s,a)$\n",
    "- ![](https://github.com/applenob/rl_learn/raw/master/res/actor-critic.png)\n",
    "\n",
    "**Policy Gradient with Eligibility Traces**：\n",
    "- 前向：$\\Delta\\theta = \\alpha(v_t^{\\lambda} − V_v (st)) \\triangledown_{\\theta}log \\pi_{\\theta}(s_t; a_t)$\n",
    "- 后向（eligibility traces）：\n",
    "    - $\\delta = r_{t+1} + \\gamma V_v(s_{t+1}) - V_v(s_t)$\n",
    "    - $e_{t+1} = \\lambda e_t + \\triangledown_{\\theta}log \\pi_{\\theta}(s,a)$\n",
    "    - $\\Delta\\theta = \\alpha\\delta e_t$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 8 Integrating Learning and Planning\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lecture 9 Exploration and Exploitation\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Lecture 10 Classic Games\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****：\n",
    "\n",
    "****："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done\n"
     ]
    }
   ],
   "source": [
    "print \"done\""
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}