Lecture01:《Introduce to Reinforcement Learning and Value-based Methods》

1. Introduction to RL

1.1 About RL

​ 强化学习有众多的应用，同时也是机器学习的三个分支之一，其他两个为监督学习与非监督学习。强化学习的特点如下所示：

• 没有监督，只有reward信号。
• 反馈很可能是延迟，不是及时的（not instantaneous）
• 处理的是序列数据不是独立同分布的数据（non-idd）
• action会影响收到的数据

1.2 RL Problem

1.2.1 Definition of RL problem

​ RL问题为给定一个状态（state），Agent根据状态（state）做出一个行为（action）$a_t$at​，然后会从环境获得奖励（reward） $r_{t+1}$rt+1​，转移到下一个状态$s_t$st​。RL的目标是最大化累积奖励。而所有的任务都可以描述为最大化的累积奖励。

1.2.2 Inside An RL Agent

​ RL Agent包括以下三个组成部分：

• Policy： agent的行为函数。

• Value function：评价state或者action的好坏。

• Model：环境模型。

1.2.3 Categorizing RL Agents

Classification 1

• Value based

  • No policy
  • Value function

• Policy based

  • Policy
  • No value function

• Actor Critic

  • Policy
  • Value function

Classification 2

• Model free
  • Policy and/or value function
  • No model
• Model based
  • Policy and/or function
  • Model

1.3 Markov Decision Processes

1.3.1 MDP定义

​马尔可夫决策过程正式描述了强化学习的环境，环境是完全可观察的是MDP，大部分RL问题也可以转化为MDP。

​ MDP的状态都具有马尔科夫性，当前状态包含了所有对未来决策的信息。
$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,...,S_t]$P[St+1​∣St​]=P[St+1​∣S1​,...,St​]
​

​ MDP可以定义为$<S,A,P,R,\gamma>$<S,A,P,R,γ>，分别表示状态集合、action集合、状态转化概率、奖励函数、衰减率。

​ Policy是给定一个state，执行action的概率分布表示为$\pi(a|s)=P[A_t=a|S_t=s]$π(a∣s)=P[At​=a∣St​=s]。给定一个MDP和策略$\pi$π，state序列是一个马尔科夫过程$<S,P^{\pi}>$<S,Pπ>，state、reward序列是一个马尔科夫奖励过程$<S,P^{\pi},R^{\pi},\gamma>$<S,Pπ,Rπ,γ>。
$P_{s,s'}^{\pi}=\sum_{a\in A}\pi(a|s)P_{ss'}^a\\ R_s^{\pi}=\sum_{a\in A}\pi(a|s)R_s^a$Ps,s′π​=a∈A∑​π(a∣s)Pss′a​Rsπ​=a∈A∑​π(a∣s)Rsa​
​ value Function分为state-value function $v_{\pi}(s)$vπ​(s) ，表示从状态$s$s开始的执行策略$\pi$π的return期望，与action-value function$q_{\pi}(s,a)$qπ​(s,a)，表示从状态$s$s开始执行行为a的按照策略$\pi$π的return期望，公式如下：
$\begin{aligned} v(s) &=\mathbb{E}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma\left(R_{t+2}+\gamma R_{t+3}+\ldots\right) | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) | S_{t}=s\right] \end{aligned}$v(s)​=E[Gt​∣St​=s]=E[Rt+1​+γRt+2​+γ2Rt+3​+…∣St​=s]=E[Rt+1​+γ(Rt+2​+γRt+3​+…)∣St​=s]=E[Rt+1​+γGt+1​∣St​=s]=E[Rt+1​+γv(St+1​)∣St​=s]​

$\begin{aligned} Q_{\pi}(s, a) &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s, A_{t}=a\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma \mathbb{E}_{a^{\prime} \sim \pi} Q\left(S_{t+1}, a^{\prime}\right) \mid S_{t}=s, A_{t}=a\right] \end{aligned}$Qπ​(s,a)​=Eπ​[Rt+1​+γv(St+1​)∣St​=s,At​=a]=Eπ​[Rt+1​+γEa′∼π​Q(St+1​,a′)∣St​=s,At​=a]​

1.3.2 Bellman Expectation Equations

​ 由上图我们可以得到以下公式：
$v_{\pi}(s)=\sum_{a \in \mathcal{A}} \pi(a | s) q_{\pi}(s, a)\\ q_{\pi}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)\\ v_{\pi}(s)=\sum_{a \in \mathcal{A}} \pi(a | s)\left(\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)\right)\\ q_{\pi}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \sum_{a^{\prime} \in \mathcal{A}} \pi\left(a^{\prime} | s^{\prime}\right) q_{\pi}\left(s^{\prime}, a^{\prime}\right)$vπ​(s)=a∈A∑​π(a∣s)qπ​(s,a)qπ​(s,a)=Rsa​+γs′∈S∑​Pss′a​vπ​(s′)vπ​(s)=a∈A∑​π(a∣s)(Rsa​+γs′∈S∑​Pss′a​vπ​(s′))qπ​(s,a)=Rsa​+γs′∈S∑​Pss′a​a′∈A∑​π(a′∣s′)qπ​(s′,a′)

1.3.3 Bellman Optimality Equations

1.3.3.1 Optimal Value Function

​ 如下公式表示在所有策略下$v(s)、q(s,a)$v(s)、q(s,a)的最大值。
$v_*(s)=\max_\pi v_{\pi}(s)\\ q_*(s,a)=\max_\pi q_{\pi}(s,a)$v∗​(s)=πmax​vπ​(s)q∗​(s,a)=πmax​qπ​(s,a)

1.3.3.2 Optimal Policy

​ 定义：$\pi \geq \pi'$π≥π′ if $v_{\pi}(s)\geq v_{\pi'}(s),\forall s$vπ​(s)≥vπ′​(s),∀s。

​ 定理 对于任何MDP，下面几点成立：

1. 存在一个最优策略，比任何其他策略更好或至少相等；
2. 所有的最优策略有相同的最优价值函数；
3. 所有的最优策略具有相同的行为价值函数；
4. 可以通过最大化最优行为价值函数来找到最优策略。

1.3.3.3 Bellman Optimality Equations

​ 通过推理我们可以得到如下公式：
$v_{*}(s)=\max _{a} q_{*}(s, a)\\ q_{*}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)\\ v_{*}(s)=\max _{a} (\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right))\\ q_{*}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \max _{a^{\prime}} q_{*}\left(s^{\prime}, a^{\prime}\right)$v∗​(s)=amax​q∗​(s,a)q∗​(s,a)=Rsa​+γs′∈S∑​Pss′a​v∗​(s′)v∗​(s)=amax​(Rsa​+γs′∈S∑​Pss′a​v∗​(s′))q∗​(s,a)=Rsa​+γs′∈S∑​Pss′a​a′max​q∗​(s′,a′)
​ 如果我们完全直到环境信息，则问题可以转化为一个规划问题，通过动态规划求解，但大部分时候我们不知道$P、R$P、R，不能直接通过贝尔曼方程求解。

2. Value-based Methods

2.1 Dynamic Programming

2.1.1 什么是DP

​ DP是已知MDP的全部信息，对该MDP进行规划，包括预测（prediction）和控制（control）。预测是由MDP和策略$\pi$π，计算value function $v_{\pi}$vπ​。控制是由MDP计算最优value function $v_*$v∗​和$\pi_*$π∗​。

2.1.2 Policy Evaluation

​ Policy Evaluation：对于给定的策略$\pi$π，计算它的value function，方法是通过iteration of Bellman Expectation backup。迭代公式如下所示：
$v_{k+1}(s)=\sum_{a \in A} \pi(a | s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right)\\ v^{k+1}=R^{\pi}+\gamma P^{\pi}v^k$vk+1​(s)=a∈A∑​π(a∣s)(Rsa​+γs′∈S∑​Pss′a​vk​(s′))vk+1=Rπ+γPπvk

2.1.3 Policy Improvement

​ 依据新的策略$\pi'$π′会得到一个新的价值函数，并产生新的贪婪策略，如此重复循环迭代将最终得到最优价值函数$v^*$v∗ 和最优策略 $\pi^*$π∗。策略在循环迭代中得到更新改善的过程称为策略迭代。

​ 每一步都贪心的进行选择：
$a=\pi(s)\\ \pi^{\prime}(s)=\underset{a \in A}{\operatorname{argmax}} q_{\pi}(s, a)$a=π(s)π′(s)=a∈Aargmax​qπ​(s,a)

​ 假如个体在与环境交互的仅下一步采取该贪婪策略产生的行为，而在后续步骤仍采取基于原策略产生的行为，那么下面的（不）等式成立 。
$q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in A} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s))=v_{\pi}(s)$qπ​(s,π′(s))=a∈Amax​qπ​(s,a)≥qπ​(s,π(s))=vπ​(s)
​ 如果后续状态均使用贪婪策略：
$\begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right)=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} q_{\pi}\left(S_{t+2}, \pi^{\prime}\left(S_{t+2}\right)\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\ldots | S_{t}=s\right]=v_{\pi^{\prime}}(s) \end{aligned}$vπ​(s)​≤qπ​(s,π′(s))=Eπ′​[Rt+1​+γvπ​(St+1​)∣St​=s]≤Eπ′​[Rt+1​+γqπ​(St+1​,π′(St+1​))∣St​=s]≤Eπ′​[Rt+1​+γRt+2​+γ2qπ​(St+2​,π′(St+2​))∣St​=s]≤Eπ′​[Rt+1​+γRt+2​+…∣St​=s]=vπ′​(s)​
​ 如果在某一个迭代周期内，状态价值函数不再改善，即：
$q_{\pi}\left(s, \pi^{\prime}(s)\right)=\max _{a \in A} q_{\pi}(s, a)=q_{\pi}(s, \pi(s))=v_{\pi}(s)$qπ​(s,π′(s))=a∈Amax​qπ​(s,a)=qπ​(s,π(s))=vπ​(s)
​ 那么就满足了贝尔曼最优方程的描述：
$v_{\pi}=\max _{a \in A} q_{\pi}(s, a)$vπ​=a∈Amax​qπ​(s,a)

2.1.4 Value Iteration

​ 一个策略能够获得某状态 s 的最优价值当且仅当该策略也同时获得状态 s 所有可能的后续状态 s′ 的最优价值。一个状态的最优价值可以由其后续状态的最优价值通过前一章所述的贝尔曼最优方程来计算：
$v_{*}(s)=\max _{a \in A}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)\right)$v∗​(s)=a∈Amax​(Rsa​+γs′∈S∑​Pss′a​v∗​(s′))

2.1.5 Contraction Mapping 压缩映射

​ Contraction Mapping 中文可以译为压缩映射或压缩映像。这个概念来自于数学中的泛函分析。内容涉及到不动点理论。不动点和压缩映射常用来解决代数方程，微分方程，积分方程等问题，而且为方程解的存在性、唯一性和迭代算法的收敛性证明提供有力的工具。

​ 定义：设$X$X是度量空间，其度量用$\rho$ρ表示。映射$T:X->X$T:X−>X，若存在$a,0\leq a\le 1$a,0≤a≤1，使得$\rho(Tx,Ty)\leq a\rho(x,y) \forall x,y\in X$ρ(Tx,Ty)≤aρ(x,y)∀x,y∈X

​ ，则称$T$T是$X$X上的一个压缩映射。

​ 若存在$x_0\in X$x0​∈X使得 $Tx_o=x_0$Txo​=x0​，则称$x_0$x0​是$T$T的不动点。

​ **定理1 完备度量空间上的压缩映射具有唯一的不动点。**从度量空间任何一点出发，只要满足压缩映射，压缩映射的序列必定会收敛到唯一的不动点。因此证明一个迭代序列是不是收敛，只要证明该序列所对应的映射是不是压缩映射。

​ 度量我们选为无穷范数：$\|v\|_{\infty}=\max _{s \in S}\|v(s)\|$∥v∥∞​=maxs∈S​∥v(s)∥，从当前值函数到下一个迭代值函数的映射可表示为：$T^{\pi}(v)=R^{\pi}+\gamma P^{\pi} v$Tπ(v)=Rπ+γPπv。

​ 下面，我们证明该映射是一个压缩映射：
$\begin{array}{c} \rho\left(T^{\pi}(u), T^{\pi}(v)\right)=\left\|T^{\pi}(u)-T^{\pi}(v)\right\|_{\infty} \\ =\left\|\left(R^{\pi}+\gamma P^{\pi} u\right)-\left(R^{\pi}+\gamma P^{\pi} v\right)\right\|_{\infty} \\ =\left\|\gamma P^{\pi}(u-v)\right\|_{\infty} \\ \leq\left\|\gamma P^{\pi}\right\| u-v\left\|_{\infty}\right\|_{\infty} \\ \leq \gamma\|u-v\|_{\infty} \end{array}$ρ(Tπ(u),Tπ(v))=∥Tπ(u)−Tπ(v)∥∞​=∥(Rπ+γPπu)−(Rπ+γPπv)∥∞​=∥γPπ(u−v)∥∞​≤∥γPπ∥u−v∥∞​∥∞​≤γ∥u−v∥∞​​
​ 因为$0\leq \gamma \le 1$0≤γ≤1，所以$T^{\pi}(v)$Tπ(v)是一个压缩映射，最终会收敛到一个唯一的确定点。

​ 通过Contraction Mapping可以证明：

• Iterative policy evaluation converges on $v_{\pi}$vπ​
• Policy iteration converges on $v_*$v∗​
• Value iteration converges in $v_*$v∗​

2.1.6 总结DP

​ DP是一个full-width backups的方法，每一个之后的state和action都需要考虑，需要直到MDP的状态转换函数和reward函数，每次迭代复杂度为$O(mn^2)$O(mn2)，其中m表示actions，n表示states。对于大规模的问题，DP方法通常会面临维度爆炸的问题。

2.2 Monte Carlo

2.2.1 MC的性质

​ MC是mode-free的，不知道状态转换和奖励函数，它直接从episodes的历史中学习，而且episodes必须是完整的,所以必须终止。通过大量的采样，使用return的均值来估计value。

2.2.2 Monte-Carlo Policy Evaluation

​ 目标：从遵循策略$\pi$π的episodes历史中学习$v_{\pi}$vπ​。定义return的计算如下所示：
$G_t=R_{t+1}+\gamma R_{t+1}+...+\gamma^{T-1}R_{T}$Gt​=Rt+1​+γRt+1​+...+γT−1RT​
​ $v_{\pi}(s)$vπ​(s)的定义如下：
$v_{\pi}(s)=\mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s\right]$vπ​(s)=Eπ​[Gt​∣St​=s]
​ Monte-Carlo Policy Evaluation是用经验均值回报来来代替期望。

​ 累进更新平均值（incremental mean):
$\begin{aligned} \mu_{k} &=\frac{1}{k} \sum_{j=1}^{k} x_{j} \\ &=\frac{1}{k}\left(x_{k}+\sum_{j=1}^{k-1} x_{j}\right) \\ &=\frac{1}{k}\left(x_{k}+(k-1) \mu_{k-1}\right) \\ &=\mu_{k-1}+\frac{1}{k}\left(x_{k}-\mu_{k-1}\right) \end{aligned}$μk​​=k1​j=1∑k​xj​=k1​(xk​+j=1∑k−1​xj​)=k1​(xk​+(k−1)μk−1​)=μk−1​+k1​(xk​−μk−1​)​
​ 递增式的蒙特卡罗法更新状态价值公式：
$\begin{array}{c} N\left(S_{t}\right) \leftarrow N\left(S_{t}\right)+1 \\ V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\frac{1}{N\left(S_{t}\right)}\left(G_{t}-V\left(S_{t}\right)\right) \end{array}$N(St​)←N(St​)+1V(St​)←V(St​)+N(St​)1​(Gt​−V(St​))​
​ 在一些实时或者无法统计准确状态被访问次数时，可以用一个系数 α 来代替状态计数的倒数，此时公式变为：
$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$V(St​)←V(St​)+α(Gt​−V(St​))

2.2.3 Monte-Carlo Policy Iteration

​ 策略评估已经解决了，但是通过贪心来进行策略提升需要知道MDPs的全部信息，但MC是model-free的，所以提出了$\epsilon-greedy$ϵ−greedy exploration。
$\pi(a | s)=\left\{\begin{array}{ll} \epsilon / m+1-\epsilon & \text { 如果 } a^{*}=\underset{a \in A}{\operatorname{argmax}} Q(s, a) \\ \epsilon / m & \text { 其它情况 } \end{array}\right.$π(a∣s)={ϵ/m+1−ϵϵ/m​ 如果 a∗=a∈Aargmax​Q(s,a) 其它情况 ​
​ 证明：对于任意一个$\epsilon-greedy$ϵ−greedy 策略$\pi$π，根据$q_{\pi}$qπ​提升的$\epsilon-greedy$ϵ−greedy 策略$\pi'$π′，$v_{\pi}' \geq v_{\pi}$vπ′​≥vπ​。
$\begin{aligned} v_{\pi}'(s) &=\sum_{a \in \mathscr{A}} \pi^{\prime}(a \mid s) q_{\pi}(s, a) \\ &=\epsilon / m \sum_{a \in \mathscr{A}} q_{\pi}(s, a)+(1-\epsilon) \max _{a \in \mathscr{A}} q_{\pi}(s, a) \\ & \geq \epsilon / m \sum_{a \in \mathscr{A}} q_{\pi}(s, a)+(1-\epsilon) \sum_{a \in \mathscr{A}} \frac{\pi(a \mid s)-\epsilon / m}{1-\epsilon} q_{\pi}(s, a) \\ &=\sum_{a \in \mathscr{A}} \pi(a \mid s) q_{\pi}(s, a) \\ &=v_{\pi}(s) \end{aligned}$vπ′​(s)​=a∈A∑​π′(a∣s)qπ​(s,a)=ϵ/ma∈A∑​qπ​(s,a)+(1−ϵ)a∈Amax​qπ​(s,a)≥ϵ/ma∈A∑​qπ​(s,a)+(1−ϵ)a∈A∑​1−ϵπ(a∣s)−ϵ/m​qπ​(s,a)=a∈A∑​π(a∣s)qπ​(s,a)=vπ​(s)​
​

​ GLIE(greedy in the Limit with Infinite Exploration) ：它包含两层意思，一是所有的状态行为对会被无限次探索 ；二是另外随着采样趋向无穷多，策略收敛至一个贪婪策略 。如果在使用 ϵ-贪婪策略时，能令 ϵ 随采样次数的无限增加而趋向于 0 就符合 GLIE。

​ 算法流程：

1. 基于给定策略 π，采样第 k 个完整的状态序列

2. 对于该状态序列里出现的每一状态行为对 $(S_t,A_t)$(St​,At​)，更新其计数 N 和行为价值函数 Q

   $\begin{array}{c} N\left(S_{t}, A_{t}\right) \leftarrow N\left(S_{t}, A_{t}\right)+1 \\ Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\frac{1}{N\left(S_{t}, A_{t}\right)}\left(G_{t}-Q\left(S_{t}, A_{t}\right)\right) \end{array}$N(St​,At​)←N(St​,At​)+1Q(St​,At​)←Q(St​,At​)+N(St​,At​)1​(Gt​−Q(St​,At​))​

3. 基于新的行为价值函数 Q 以如下方式改善策略

   $\begin{array}{c} \epsilon \leftarrow 1 / k \\ \pi \leftarrow \epsilon-g \operatorname{reed} y(Q) \end{array}$ϵ←1/kπ←ϵ−greedy(Q)​

2.3 TD learning

2.3.1 TD learning 的性质

​ TD与MC不同在于episodes不需要终止，updates a guess towards a guess。TD has lower variance and higher bias. MC has higher variance and no bias。

2.3.2 MC and TD Policy Evaluation

​ MC的更新公式如下所示，用$G_t$Gt​进行更新：
$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}-V\left(S_{t}\right)\right)$V(St​)←V(St​)+α(Gt​−V(St​))
​

​ TD的更新公式如下所示，采用$R_t+\gamma V(S_{t+1})$Rt​+γV(St+1​)进行更新：
$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$V(St​)←V(St​)+α(Rt+1​+γV(St+1​)−V(St​))
​

​ 其中$R_{t+1}+\gamma V\left(S_{t+1}\right)$Rt+1​+γV(St+1​)称为 TD 目标值 ,$R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)$Rt+1​+γV(St+1​)−V(St​)称为TD 误差。

2.3.3 TD Control: SARSA

​ Sarsa算法：针对一个状态 S，个体通过行为策略产生一个行为 A，执行该行为进而产生一个状态行为对 (S,A)，环境收到个体的行为后会告诉个体即时奖励R 以及后续进入的状态 S’；个体在状态 S’ 时遵循当前的行为策略产生一个新行为 A’，个体此时并不执行该行为，而是通过行为价值函数得到后一个状态行为对 (S’,A’) 的价值，利用这个新的价值和即时奖励 R 来更新前一个状态行为对 (S,A) 的价值。

​

​ 迭代公式：
$Q(S, A) \leftarrow Q(S, A)+\alpha\left(R+\gamma Q\left(S^{\prime}, A^{\prime}\right)-Q(S, A)\right)$Q(S,A)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A))
​

​ Sarsa算法流程：参数 α 是学习速率参数， γ 是衰减因子。

2.4 Off-policy Learning

2.4.1 什么是Off-Policy Learning

​ 前面介绍的MC、TD方法都是on-policy的。借鉴策略学习 (off-policy learning) 中产生指导自身行为的策略$\mu(a|s)$μ(a∣s)与评价策略$\pi(a|s)$π(a∣s)是不同的策略。具体地说，个体通过策略 $\mu(a|s)$μ(a∣s)生成行为与环境发生实际交互，但是在更新这个状态行为对的价值时使用的是目标策略 $\pi(a|s)$π(a∣s)。目标策略$\pi(a|s)$π(a∣s)多数是已经具备一定能力的策略，例如人类已有的经验或其他个体学习到的经验。借鉴策略学习相当于站在目标策略 $\pi(a|s)$π(a∣s)的“肩膀”上学习。

​ 优点：

• Learn from observing humans or other agents
• Reuse experience generated from old policies
• Learn about optimal policy while following exploratory policy
• Learn about multiple policies while following one policy

​ 为什么会有两个策略呢？

为了解决强化学习问题中的exploitation与exploration的平衡，我们可以用一个策略来保持探索性，来获得更多样化的数据，而不断的优化另一个策略（target policy）。

On-policy 会导致策略在学习一个局部最优，因为无法同时保持探索和利用，但是off-policy的面临的问题是如何在一个策略下产生的数据来优化另一个策略。

2.4.2 Importance Sampling

​ 什么是Importance Sampling ：Estimate the expectation of a difference distribution.
$\begin{aligned} \mathbb{E}_{X \sim P}[f(X)] &=\boldsymbol{\sum} P(X) f(X) \\ &=\sum Q(X) \frac{P(X)}{Q(X)} f(X) \\ &=\mathbb{E}_{X \sim Q}\left[\frac{P(X)}{Q(X)} f(X)\right] \end{aligned}$EX∼P​[f(X)]​=∑P(X)f(X)=∑Q(X)Q(X)P(X)​f(X)=EX∼Q​[Q(X)P(X)​f(X)]​

Importance Sampling for Off-Policy MC：

​ 使用根据策略$\mu$μ产生的return来评价策略$\pi$π，根据Importance Sampling公式$G_t$Gt​的计算如下所示。
$G_{t}^{\pi / \mu}=\frac{\pi\left(A_{t} \mid S_{t}\right)}{\mu\left(A_{t} \mid S_{t}\right)} \frac{\pi\left(A_{t+1} S_{t+1}\right)}{\mu\left(A_{t+1} \mid S_{t+1}\right)} \cdots \frac{\pi\left(A_{T} \mid S_{T}\right)}{\mu\left(A_{T} \mid S_{T}\right)} G_{t}$Gtπ/μ​=μ(At​∣St​)π(At​∣St​)​μ(At+1​∣St+1​)π(At+1​St+1​)​⋯μ(AT​∣ST​)π(AT​∣ST​)​Gt​
​ 更新公式如下所示：
$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(G_{t}^{\pi / \mu}-V\left(S_{t}\right)\right)$V(St​)←V(St​)+α(Gtπ/μ​−V(St​))

Importance Sampling for Off-Policy TD

​ 使用根据策略$\mu$μ产生的return来评价策略$\pi$π，根据Importance Sampling 更新公式如下所示。
$V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(\frac{\pi\left(A_{t} | S_{t}\right)}{\mu\left(A_{t} | S_{t}\right)}\left(R_{t+1}+\gamma V\left(S_{t+1}\right)\right)-V\left(S_{t}\right)\right)$V(St​)←V(St​)+α(μ(At​∣St​)π(At​∣St​)​(Rt+1​+γV(St+1​))−V(St​))
​

​ 对于上式，我们可以这样理解：个体处在状态 $S_t$St​ 中，基于行为策略 µ 产生了一个行为 $A_t$At​，执行该行为后进入新的状态 $S_{t+1}$St+1​，借鉴策略学习要做的事情就是，比较借鉴策略和行为策略在状态 $S_t$St​ 下产生同样的行为 $A_t$At​ 的概率的比值，如果这个比值接近 1，说明两个策略在状态 $S_t$St​ 下采取的行为 $A_t$At​ 的概率差不多，此次对于状态 $S_t$St​ 价值的更新同时得到两个策略的支持。如果这一概率比值很小，则表明借鉴策略 π 在状态 $S_t$St​ 下选择 $A_t$At​ 的机会要小一些，此时为了从借鉴策略学习，我们认为这一步状态价值的更新不是很符合借鉴策略，因而在更新时打些折扣。类似的，如果这个概率比值大于 1，说明按照借鉴策略，选择行为 $A_t$At​ 的几率要大于当前行为策略产生 $A_t$At​ 的概率，此时应该对该状态的价值更新就可以大胆些。

2.4.3 Q Learning

​ 借鉴策略 TD 学习中一个典型的行为策略 µ 是基于行为价值函数 Q(s,a)，ϵ-贪婪策略，借鉴策略 π 则是基于 Q(s，a) 的完全贪婪策略，这种学习方法称为 Q 学习 (Q learning)。

​ 因为target policy是贪心策略，所以Q 学习具体的行为价值更新公式：

$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left(R+\gamma \max _{a^{\prime}} Q\left(S_{t+1}, a^{\prime}\right)-Q\left(S_{t}, A_{t}\right)\right)$Q(St​,At​)←Q(St​,At​)+α(R+γa′max​Q(St+1​,a′)−Q(St​,At​))

​

​ 为什么更新公式如上所示？ 根据最优贝尔曼公式可知$q_{*}(s, a)=\mathcal{R}_{s}^{a}+\gamma \sum_{s^{\prime} \in \mathcal{S}} \mathcal{P}_{s s^{\prime}}^{a} \max _{a^{\prime}} q_{*}\left(s^{\prime}, a^{\prime}\right)$q∗​(s,a)=Rsa​+γ∑s′∈S​Pss′a​maxa′​q∗​(s′,a′)，$P_{ss'}^a$Pss′a​不可知，所以不能私用状态转移概率来计算期望，而是使用采样逼近的方式。

​ Q 学习的算法流程 ：

​

​ 为什么会有如下图所示的情况? 因为Sarsa的更新公式如下所示：$Q(S, A) \leftarrow Q(S, A)+\alpha\left(R+\gamma Q\left(S^{\prime}, A^{\prime}\right)-Q(S, A)\right)$Q(S,A)←Q(S,A)+α(R+γQ(S′,A′)−Q(S,A))

​

​ **为什么Q-learning不用重要性采样（importance sampling）？**因为动作状态值是通过1-step更新的,每一步都是执行a得到的，就算A不是通过greedy策略选择的,对Q(S,A)估计的更新也不会受到影响。但如果是n-step更新，如以下公式所示就会有问题，$R_{t+1}$Rt+1​是$a_{t+1}$at+1​使用$\epsilon$ϵ-greedy采样获得的，不是所要优化的greedy策略。
$Q\left(s_{t}, a_{t}\right)=Q\left(s_{t}, a_{t}\right)+\alpha\left[R_{t}+\gamma R_{t+1}+\gamma^{2} \max _{a} Q\left(s_{t+2}, a\right)-Q\left(s_{t}, a_{t}\right)\right]$Q(st​,at​)=Q(st​,at​)+α[Rt​+γRt+1​+γ2amax​Q(st+2​,a)−Q(st​,at​)]

2.5 DQN and its variants (continuous state)

2.5.1 DQN

​ 当问题的规模变大，state和action的数量变多，连续状态的问题。通过参数w的函数来近似状态价值函数和状态行为对价值函数，在MC或者TD算法中通过更新w参数来学习，有以下三种方式：

对于MC学习：

$\begin{array}{c} J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[G_{t}-\hat{V}\left(S_{t}, w\right)\right]^{2} \\ J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[G_{t}-\hat{Q}\left(S_{t}, A_{t}, w\right)\right]^{2} \end{array}$J(w)=2M1​∑t=1M​[Gt​−V^(St​,w)]2J(w)=2M1​∑t=1M​[Gt​−Q^​(St​,At​,w)]2​

对于 TD(0) 和反向认识 TD(λ) 学习 ：

$\begin{array}{c} \left.J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[R_{t}+\gamma \hat{V}\left(S_{t}^{\prime}, w\right)\right)-\hat{V}\left(S_{t}, w\right)\right]^{2} \\ \left.J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[R_{t}+\gamma \hat{Q}\left(S_{t}^{\prime}, A_{t}^{\prime}, w\right)\right)-\hat{Q}\left(S_{t}, A_{t}, w\right)\right]^{2} \end{array}$J(w)=2M1​∑t=1M​[Rt​+γV^(St′​,w))−V^(St​,w)]2J(w)=2M1​∑t=1M​[Rt​+γQ^​(St′​,At′​,w))−Q^​(St​,At​,w)]2​

前向认识 TD(λ) 学习 ：

$\begin{array}{c} J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[G_{t}^{\lambda}-\hat{V}\left(S_{t}, w\right)\right]^{2} \\ J(w)=\frac{1}{2 M} \sum_{t=1}^{M}\left[q_{t}^{\lambda}-\hat{Q}\left(S_{t}, A_{t}, w\right)\right]^{2} \end{array}$J(w)=2M1​∑t=1M​[Gtλ​−V^(St​,w)]2J(w)=2M1​∑t=1M​[qtλ​−Q^​(St​,At​,w)]2​

DQN算法：

​ 首先如果采用online Q-Learning的方式，通过$\epsilon$ϵ-greedy策略采样a，然后观察$(s,a,r,s')$(s,a,r,s′)。再通过$\Delta \mathbf{w}=\alpha\left(r+\gamma \max _{a^{\prime}} \hat{q}\left(s^{\prime}, a^{\prime}, \mathbf{w}\right)-\hat{q}(s, a, \mathbf{w})\right) \nabla_{\mathbf{w}} \hat{q}(s, a, \mathbf{w})$Δw=α(r+γmaxa′​q^​(s′,a′,w)−q^​(s,a,w))∇w​q^​(s,a,w)更新参数，这样会导致序列state有很强的相关性，并且target value 会一直变化。

​ 所以提出了DQN算法，采用了experience replay 和 target network 来解决上述问题，DQN的算法流程如下所示：

2.5.2 Double DQN

​ 如下图所示，其中横轴为训练的steps，纵轴为评估的value值。红色的横线为DQN的true value，可以看出DQN评估的值会大于真实值很多，这是由于DQN的target value是$r+\gamma \max_{a'} Q(s',a';w^-)$r+γmaxa′​Q(s′,a′;w−)，而且$E[max(X_1,X_2)]\geq max(E(X_1),E(X_2))$E[max(X1​,X2​)]≥max(E(X1​),E(X2​))。这样可能会产生问题，所以提出了DDQN。

​

​ DQN中$\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \mathbf{w}^{-}\right)=Q\left(s^{\prime}, \arg \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \mathbf{w}^{-}\right) ; \mathbf{w}^{-}\right)$maxa′​Q(s′,a′;w−)=Q(s′,argmaxa′​Q(s′,a′;w−);w−)，action selected according to$Q(w^-)$Q(w−)，value also from$Q(w^-)$Q(w−)。提出的DDQN，Current network to choose action，Target network to evaluate value。即：$r+\gamma Q\left(s^{\prime}, \underset{a^{\prime}}{\arg \max } Q\left(s^{\prime}, a^{\prime} ; \mathbf{w}\right) ; \mathbf{w}^{-}\right)$r+γQ(s′,a′argmax​Q(s′,a′;w);w−)，算法流程如下图所示。

​

​ 上图中的更新参数是直接$w'=w$w′=w，也可使采用Soft update the target network：$w^-=(1-\alpha)w+\alpha w^-$w−=(1−α)w+αw−。

2.5.3 Dueling DQN

​ Motivation ：It is unnecessary to know the exact value of each action at every step

​ 在Dueling DQN中尝试通过优化神经网络结构来优化算法，一部分是状态价值函数部分$V(S,w,\alpha)$V(S,w,α)，第二部分是优势函数部分$A(S,A,w,\beta)$A(S,A,w,β)，最终状态价值函数可以表示为如下所示的公式，其中w是公共部分的网络参数，$\alpha$α是状态价值函数独有部分的网络参数，$\beta$β是优势函数独有部分的网络参数。Dueling DQN可直接学习哪些状态是有价值的。这个特性非常重要，因为智能体在与环境做互动的过程中，有些状态对应的动作对环境没任何影响。
$Q(S,A,w,\alpha,\beta)=V(S,w,\alpha)+A(S,A,w,\beta)$Q(S,A,w,α,β)=V(S,w,α)+A(S,A,w,β)

​ 由上可以得出：$Q(S,A,w,\alpha,\beta)=V(S,w,\alpha)+A(S,A,w,\beta)$Q(S,A,w,α,β)=V(S,w,α)+A(S,A,w,β)，但这个公式有着不可辨别问题（unidentifiable），就是如果在V中加一个常量，在A中减去一个常量，仍然输出相同的Q值，无法分别是哪个部分的影响，会严重降低网络的性能，所以可以改进为：

$\begin{array}{l} Q(s, a ; \theta, \alpha, \beta)=V(s ; \theta, \beta)+\left(A(s, a ; \theta, \alpha)-\max _{a^{\prime} \in \mathscr{A}} A\left(s, a^{\prime} ; \theta, \alpha\right)\right) \\ Q(s, a ; \theta, \alpha, \beta)=V(s ; \theta, \beta)+\left(A(s, a ; \theta, \alpha)-\frac{1}{|\mathscr{A}|} \sum_{a^{\prime} \in|\mathscr{A}|} A\left(s, a^{\prime} ; \theta, \alpha\right)\right) \end{array}$Q(s,a;θ,α,β)=V(s;θ,β)+(A(s,a;θ,α)−maxa′∈A​A(s,a′;θ,α))Q(s,a;θ,α,β)=V(s;θ,β)+(A(s,a;θ,α)−∣A∣1​∑a′∈∣A∣​A(s,a′;θ,α))​

2.5.4 n-Step DQN

​ n-step 的target是$R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1} R_{t+n}+\gamma^{n} \max _{a} Q\left(S_{t+n}, a ; \theta\right)$Rt+1​+γRt+2​+⋯+γn−1Rt+n​+γnmaxa​Q(St+n​,a;θ)，有着更小的bias，学习更快，但是只有当on-policy学习时才准确。

​ 如何才能off-policy学习：

• 忽略这个问题（在实践中经常有用）
• Dynamically choose N to get only on-policy data（当数据是on-policy并且行为空间小的时候有效）
• 重要性采样

2.5.5 Distributional DQN

​ 暂时无法理解。。。

2.5.6 Prioritized Experience Replay

​ 在抽取经验池中过往经验样本时，采取按优先级抽取的方法。TD误差越高，神经网络权重的更新程度就越大，所以更加TD error进行采样。

​ 采样的公式为$P(i)=\frac{p_i^\alpha}{\sum_k p_k^\alpha}$P(i)=∑k​pkα​piα​​，其中$\alpha$α是决定我们要使用多少 ISweight 的影响, 如果 alpha = 0, 我们就没使用到任何 Importance Sampling.就是uniform random sampling。$p_i$pi​优先级的定义有两种：（1） $p_i=|\delta_i|+\epsilon$pi​=∣δi​∣+ϵ，（2）$p_i=\frac{1}{rank(i)}$pi​=rank(i)1​。

​ 优先重放机制引入了bias，它以一种不受控制的方式改变了这个分布，因此改变收敛结果（即使策略和状态分布是固定的）。我们可以通过引入importance-sample weights来弥补：
$w_{i}=\left(\frac{1}{N} \cdot \frac{1}{P(i)}\right)^{\beta}$wi​=(N1​⋅P(i)1​)β

2.5.7 Rainbow

​ 整合DQN算法中的六种变体，效果显著。

2.5.8 DDPG

​ 深度确定性策略梯度算法是使用深度学习技术、同时基于 Actor-Critic 算法的确定性策略算法。该算法中的 Actor 和 Critic 都使用深度神经网络来建立近似函数。**由于该算法可以直接从Actor 的策略生成确定的行为而不需要依据行为的概率分布进行采样而被称为确定性策略。**该算法在学习阶段通过在确定性的行为基础上增加一个噪声函数而实现在确定性行为周围的小范围内探索。此外，该算法还为 Actor 和 Critic 网络各备份了一套参数用来计算行为价值的期待值以更稳定地提升 Critic 的策略指导水平。使用备份参数的网络称为目标网络，其对应的参数每次更新的幅度很小。另一套参数对应的 Actor 和 Critic 则用来生成实际交互的行为以及计算相应的策略梯度，这一套参数每学习一次就更新一次。这种双参数设置的目的是为了减少因近似数据的引导而发生不收敛的情形。这四个网络具体使用的情景为：

1. Actor 网络：根据当前状态 s0 生成的探索或不探索的具体行为 a0；
2. Target Actor 网络：根据环境给出的后续状态 s1 生成预估价值用到的 a1；
3. Critic 网络：计算状态 s0 和生成的行为 a0 对应的行为价值；
4. Target Critic 网络：根据后续状态 s1,a1 生成用来计算目标价值 y = Q(s0; a0) 的 Q′(s1; a1)；

​ DDPG 算法表现出色，能较为稳定地解决连续行为空间下强化学习问题，其具体流程如下所示。

2.5.9 TD3: Twin Delayed DDPG

​ DQN存在高估值函数的情况，所以提出了TD3，有两个Q-function。

$\begin{array}{l} y_{1}=r+\gamma Q_{\theta_{2}^{\prime}}\left(s^{\prime}, \pi_{\phi_{1}}\left(s^{\prime}\right)\right) \\ y_{2}=r+\gamma Q_{\theta_{1}^{\prime}}\left(s^{\prime}, \pi_{\phi_{2}}\left(s^{\prime}\right)\right) \end{array}$y1​=r+γQθ2′​​(s′,πϕ1​​(s′))y2​=r+γQθ1′​​(s′,πϕ2​​(s′))​
​ TD target为：$y=r+\gamma \min _{i=1,2} Q_{\theta_{i}}\left(s^{\prime}, \mu_{\phi}(s)\right)$y=r+γmini=1,2​Qθi​​(s′,μϕ​(s))。

​ 延迟更新策略：这个方法是在critic进行一定数量的更新后对策略和目标网络进行更新。

​ 随机噪声: 在确定性策略下，目标易受到函数拟合误差带来的影响，从而增大方差，所以可以添加噪声缓解。$a_{\mathrm{clip}}\left(s^{\prime}\right)=\mu_{\phi^{\prime}}\left(s^{\prime}\right)+\operatorname{clip}(\mathscr{N}(0, \sigma),-c,+c)$aclip​(s′)=μϕ′​(s′)+clip(N(0,σ),−c,+c)

​ 最后$y=r+\gamma \min _{i=1,2} Q_{\theta^{(}}\left(s^{\prime}, a_{\mathrm{clip}}\right)$y=r+γmini=1,2​Qθ(​(s′,aclip​)。

2.5.10 Practical Tips for Deep Q Networks

• 首先测试简单的任务，确保实现的正确。

• relay buffers 数量设置的大有利于提高稳定性。

• 需要时间，要耐心

• 从更大的探索exploration$(\epsilon)$(ϵ)开始，然后逐渐减小，对于学习率也是如此。

• DDQN在实践中很有用，简单没有缺点。

• 运行不同的随机数种子，这之间非常不一致。

Reference

[1] 读者常见问题汇总及解答

[2] Bourne强化学习笔记1：用简单例子说明Off-policy的思想与使用方法

[3] 【强化学习】Deep Q Network(DQN)算法详解

[4] [强化学习（十）Double DQN (DDQN)](https://www.cnblogs.com/pinard/p/9778063.html)

[5] RLChina2020 Lecture 视频

[6] RLChina2020 Lecture PPT