强化学习-基础

Oct 12, 2019 · 强化学习  ·
分享到:

强化基础

分类

  • Valued-based / policy-based / A3C=A+C
  • Model based / Model free
  • 回合更新（蒙特卡洛） / 时间差分（步更新）
  • On-policy / off-policy
  • 稳态和非稳态
  • 全部可观测MDP / 部分可观测

DRL：本质把DNN作为一个actor。

强化学习基础模型马尔可夫决策

MDP-->动态规划（策略迭代，值迭代）

状态价值函数与行为价值函数

在给定策略\(\pi\)下，状态转移概率与即时收获期望（这两项其实都是概率平均即期望）： \[ P_{s,s'}^{\pi}=\sum_{a\in A}\pi(a|s)P_{s,s'}^a \tag{1} \] \[ R_{s}^{\pi} = \sum_{a\in A}\pi(a|s)R_s^a\tag{2} \] 其中，\(\pi(a|s)\)表示给定策略\(\pi\)下，在状态\(s\)时，选用动作\(a\)的概率。\(P_{s,s'}^a\)表示在状态\(s\)时，选用动作\(a\)后，转移到目标状态\(s'\)的概率。

状态价值函数：表示从状态\(s\)开始，遵循当前策略\(pi\)时所获得的收获的期望，即\(v_\pi (s) = E[G_t | S_t = s]\)

行为价值函数(状态行为对价值函数)：遵循当前策略\(pi\)时，对当前状态\(s\)执行某一具体行为\(a\)，所能获得的收获的期望，即\(q_\pi(s,a) = E[G_t | S_t = s, A_t = a]\)

Bellman方程递推公式

我们根据定义可以推到出现在具体状态\(s\)与下一可能状态\(S_{t+1}\)的关系。注意\(S_{t+1}\)是一个随机变量，是\(t+1\)时刻状态的随机变量。 \[ \begin{aligned} v(s) &= E[G_t | S_t = s]\\ &=E[R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + \dotsb | S_t = s]\\ &=E[R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \dotsb)| S_t = s]\\ &=E[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &=E[R_{t+1} + \gamma v(S_{t+1}) | S_t =s] \end{aligned}\tag{3} \] 其中，\(E[v(S_{t+1})|S_t = s]\)表示此时状态为s时，\(t+1\)时刻状态价值函数的期望。简而言之，我们有 \[ v_\pi(s) = E[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]\tag{4} \] 同理可得： \[ q_\pi(s,a) = E[R_{t+1} + \gamma q_\pi(S_{t+1},A_{t+1}) | S_t = s, A_t = a ]\tag{5} \] 由于行为是连接状态转换的桥梁，一个行为的价值与状态的价值关系紧密，我们可以用下式来表达 \[ v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)\tag{6} \] 状态的价值是相关行为价值的概率加权平均。类似的，一个行为价值可以用该行为所能到达的后续状态的价值概率加权平均来表达： \[ q_\pi(s,a) = \underbrace{R_s^a}_{即时回报}+\underbrace{\gamma\sum_{s'\in S}P_{s,s'}^a v_\pi(s')}_{下一步状态价值的期望}\tag{7} \] 联立\((6)(7)\)两式，可以得到如下两递推公式： \[ v_\pi(s)=\sum_{a\in A}\pi(a|s)\big(R_s^a+\gamma\sum_{s'\in S}P_{s,s'}^a v_\pi(s')\big)\tag{8} \] \[ q_\pi(s,a) = R_s^a+\gamma\sum_{s'\in S}P_{s,s'}^a \big(\sum_{a\in A}\pi(a'|s')q_\pi(s',a')\big)\tag{9} \] 这两个地推公式的迭代（策略迭代，价值迭代）就可以得出收敛的价值函数。

策略迭代：根据公式\((8)\)迭代更新状态价值，通过贪婪法迭代获得策略。最终能够收敛（压缩映射定理证明）

值迭代：根据公式\(v_*(s)=\max\limits_{a\in A}(R_s^a + \gamma \sum\limits_{s'\in S}P_{s,s'}^a v_*(s'))\)，逐步迭代更新。

不基于模型的预测(\(V(s)\))

蒙特卡洛方法 MC；时间差分 TD；动态规划DP

蒙特卡洛价值更新

MC法更新：基础是累进更新平均值。在这种方法中，我们只需要直到上次状态值和此次新加入的值。 \[ \begin{aligned} \mu_k &= \frac{1}{k}\sum_{j=1}^k x_j\\ &=\frac{1}{k}(x_k+\sum_{j=1}^{k-1} x_j)\\ &=\frac{1}{k}(x_k+(k-1)\mu_{k-1})\\ &=u_{k-1}+\frac{1}{k}(x_k-\mu_{k-1}) \end{aligned} \] 具体到蒙特卡洛法更新状态价值就是： \[ N(S_t)\leftarrow N(S_t)+1\\ V(S_t)\leftarrow \underbrace{V(S_t)}_{\mu_{k-1}}+\frac{1}{\underbrace{N(S_t)}_{k}}(\underbrace{G_t}_{x_k}-\underbrace{V(S_t)}_{\mu_{k-1}})\tag{10} \] 在一些实时或者无法准确统计状态被访问次数时，可以用一个系数\(\alpha\)来代替状态计数的倒数\(\frac{1}{N(S_t)}\)，此时公式\((10)\)可以简化为： \[ \color{red}{\star V(S_t) \leftarrow V(S_t) + \alpha(G_t-V(S_t))}\tag{11} \] 公式\((11)\)是以后所有更新公式的一个基础。

时间差分价值更新

TD法更新：MC法更新中，\(G_t=R_{t+1}+\gamma R_{t+2} + \dotsb + \gamma^{T-1} R_{t+T}\)是一个完整的episode。而TD方法是用不完整的轨迹序列完成更新，是使用bootstrapping的方法。 \[ V(S_t) \leftarrow V(S_t) + \alpha(\underbrace{\underbrace{R_{t+1}+\gamma V(S_{t+1}}_{TD目标值\rightarrow G_t})-V(S_t)}_{TD误差})\tag{12} \] 其中\(G_t\approx R_{t+1}+\gamma V(S_{t+1})\)，如果\(V(S_{t+1})\)是真实值，那么\(G_t\)就是无偏估计，但实际上\(V(S_{t+1})\)是采样累进更新来的，所以TD法的更新可能会有偏差。

TD-n更新：TD法本质上用了下一步的即时收获和状态价值。我们可以使用n步来预测。 \[ G_t^{(n)}= R_{t+1}+\gamma R_{t+2} + \dotsb + \gamma^{n-1} R_{t+n}+\gamma^n V(S_{t+n})\\ V(S_t) \leftarrow V(S_t) + \alpha(G_t^{(n)}-V(S_t))\tag{13} \] 当\(n=1\)时，即为TD法更新，当\(n=T or\infty\)时，即为MC法。

TD(λ)更新：在TD-n中，n是一个离散的超参数，为了能够简化计算并综合考虑所有步数n的影响，我们引入了一个带λ的加权求和方法。 \[ G_t^{(\lambda)}= (1-\lambda)\sum_{n=1}^{T-t-1}\lambda^{n-1}G_t^{(n)} + \lambda^{T-t-1}G_t^{T-t}\\ \approx (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}(T\rightarrow\infty) \\ V(S_t) \leftarrow V(S_t) + \alpha(G_t^{(\lambda)}-V(S_t))\tag{14} \]

他们之间的关系可以参考笔记《强化学习之 DP、MC、TD》

不基于模型的控制(\(Q(s,a)\))

从已知模型的、基于全宽度采样的动态规划学习转至模型未知、基于采样的蒙特卡洛或时序差分学习进行控制是朝着高效解决中等规模实际问题的一个突破。

不基于模型的控制无法得知整体的状态价值和状态转移概率，因此我们需要脚踏实地，从当前状态的行为状态价值对出发。因此，在不基于模型的控制中，行为价值函数很重要。

即我们现在更关注\(Q(s,a)\)而非\(V(s)\)。

On-policy VS Off-policy

  • 行为策略：指导个体和环境进行实际交互的策略
  • 目标策略：评价状态价值、行为价值或者待优化的策略
  • 如果\(行为策略 == 目标策略\rightarrow on-policy\)（现时策略、同策略）
  • 如果\(行为策略 \neq 目标策略\rightarrow off-policy\)（借鉴策略、异策略）

在off-policy下，产生行为序列的策略和评价状态价值的策略时两个策略。

ε-greedy策略

假设我们在状态\(s\)有\(m\)个可以选择的动作。 \[ \pi(a|s) = \begin{cases} \varepsilon/m + 1- \varepsilon, a^\ast = \argmax_{a\in A} Q(s,a)\\ \varepsilon/m, Others \end{cases}\tag{15} \] 可以证明，ε-greedy方法可以提升原有的策略\(\pi\)。

On-policy 蒙特卡洛（MC）控制

on-policy MC 控制 = MC+ε-greedy方法

  1. 初始化一系列状态价值\(Q(S_0,A_0)\)，ε-greedy策略选择动作
  2. 依照策略和环境交互，得到一组（或几组）轨迹，根据MC更新方法（公式\((10),(11)\)），更新状态价值。
  • 需要注意，区别于公式(10)现在更新的不是\(V(S_t)\),而是 \[\color{red}{Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{1}{N(S_t,A_t)}(G_t-Q(S_t,A_t))}\tag{16}\]
  1. 回到步骤1

公式(16)也是接下来工作的基础。注意，并不需要每次交互都要更新状态价值，可以多跑几组数据来更新状态价值。但是实际中，我们通常仅得到一个完整状态序列就进行一次策略迭代以加速更新。

GLIE定理(Greedy in the Limit with Infinite Exploration)：

  1. 所有状态行为对会被无数次探索：\(\lim\limits_{k\rightarrow \infty} N_k(s,a)=\infty\)
  2. 随着采样次数趋近于无穷，策略最终收敛至一个贪婪策略:\(\lim\limits_{k\rightarrow \infty}\pi_k(a|s) = 1(a = \argmax\limits_{a'\in A}Q_k(s,a'))\)

那么MC控制能够收敛到最优的状态行为价值函数，即\(Q_k(s,a)\xrightarrow{k\rightarrow\infty} q^\ast(s,a)\)

显然，当我们无限采样且使ε-greedy策略中，ε=1/k，其中k是完整的采样次数。这个策略就满足GLIE定理。

On-policy TD control —— SARSA,SARSA(\(\lambda\))

TD(0)更新的SARSA

在每一个采样序列中，每一个时间步，在状态\(S\)下采取一个行为\(A\)到达状态\(S'\)后，都要更新状态行为对\((S,A)\)的价值\(Q(S,A)\)，交互过程和评价过程都使用ε-greedy策略（on-policy）。

关键——行为价值函数更新过程： \[ Q(S,A)\leftarrow Q(S,A)+\alpha(R+\gamma Q(S',A')-Q(S,A))\tag{17} \] sarsa

算法的收敛性。当行为策略满足GLIE定理，且学习率\(\alpha\)满足 \[\sum_{t=1}^\infty \alpha_t=\infty, \text{and} \sum_{t=1}^\infty \alpha_t^2<\infty\] SARSA算法将收敛至最优策略和最优价值函数。

TD(\(\lambda\))更新的SARSA(\(\lambda\))

和TD-n法更新价值函数一样，我们可以定义n步Q收获 \[ q_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\dotsb+\gamma^{n-1} R_{t+n}+\gamma^nQ(S_t,A_t) \] 类似的，我们根据n步Q收获可以定义SARSA(n)的行为价值更新函数： \[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha(q_t^{(n)}-Q(S_t,A_t))\tag{18-1} \] 和TD(n)一样，\(n\)是一个需要条件的超参数，为了计算的方便，我们模仿\(TD(\lambda)\)的加权方式给\(q^{(n)}_t\)进行加权求和,结合所有n步Q收获： \[ q_t^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1} q_t^{(n)} \] 我们可以用\(q_t^\lambda\)代替公式\((18)\)中的\(q_t^{(n)}\)。这就是SARSA\((\lambda)\)的夹着更新公式。 \[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha(q_t^{\lambda}-Q(S_t,A_t))\tag{18-2} \]

但是，迭代一次Q值，需要完整的一次episode。为了解决这个问题，引入效用迹的概念，实现增量更新。效用迹针对的状态行为对。 \[ E_0(s,a)=0(初始化为0)\\ E_t(s,a)=\gamma\lambda E_{t-1}(s,a)+\mathbf{1}(S_t=s,A_t=a),\gamma,\lambda\in[0,1]\tag{19} \] 其中，\(\mathbf{1}\)是判别函数，成立为1，不成立为0。它体现的是一个结果与某一个状态行为对的因果关系，与得到该结果最近的状态行为对，以及那些在此之前频繁发生的状态行为对得到这个结果的影响最大。引入效用迹后，Q值的更新公式为： \[ \delta_t = R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_{t},A_{t})\\ Q(s,a)\leftarrow Q(s,a)+\alpha\delta_t E_t(s,a)\tag{20} \] 可以证明在\(\lambda\in(0,1)\)时，公式(20)与公式(18-2)是等效的（一个是前向认识，一个是反向认识），但是公式(20)中的数据学习完即可丢弃，在线学习更有效。

sarsa_lambda.png

sarsa_lambda.png

这里要提及一下的是\(E(s,a)\)在每浏览完一个状态序列后需要重新置0，这体现了效用迹仅在一个状态序列中发挥作用；其次要提及的是算法更新\(Q\)和\(E\)的时候针对的不是某个状态序列里的\(Q\)或\(E\)，而是针对个体掌握的整个状态空间和行为空间产生的\(Q\)和\(E\)。

为什么Off-policy MC control不好

根据重要性采样，在off-policy MC更新下，收获函数应为 \[ G_t^{\pi/\mu}=\underbrace{\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})}\dotsb\frac{\pi(A_T|S_T)}{\mu(A_T|S_T)}}_{方差被放的很大}G_t\\ V(S_t) = V(S_t)+\alpha(G_t^{\pi/\mu}-V(S_t))\tag{21} \] 其中，\(\mu(a|s)\)是行为策略，\(\pi(a|s)\)是目标策略。但是\(G_t^{\pi/\mu}\)的方差会特别大，使得估计偏差大到无法使用，且\(\mu(a|s)=0\)时无法使用。因此基于蒙特卡洛的借鉴策略学习目前认为仅有理论上的研究价值，在实际中用处不大。

Off-policy TD control —— Q-learning

相较于off-policy MC更新中多个步骤的概率商相乘，TD更新只用修正一次概率，方差还是可以接受的。 \[ G_t^{\pi/\mu}=\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}G_t \]

Q-learning是一个典型的off-policy TD控制方案。行为策略\(µ\)是基于行为价值函数\(Q(s,a)\)ϵ-贪婪策略，借鉴策略\(π\)则是基于\(Q(s，a)\)的完全贪婪策略。需要指出，Q-learning没有用到重要性采样。Q-learning的价值更新公式如下： \[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha({\color{red}R_{t+1}+\gamma Q(S_{t+1},A')}-Q(S_t,A_t))\tag{22} \] 注意：红色部分的TD目标是基于借鉴策略\(π\)（贪婪策略）产生的行为\(A’\)得到的\(Q\)值。而每次的交互使用的是策略\(\mu\)（ϵ-贪婪策略），状态\(S_t\)依据\(\mu\)得到行为\(A_t\)并朝着\(S_{t+1}\)前进。

由于\(A'\)是根据贪婪策略选出来的，所以公式（22）可以简化为： \[ Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha({\color{red}R_{t+1}+\gamma \max_{a'}Q(S_{t+1},a')}-Q(S_t,A_t))\tag{23} \]

Q-learning

Q-learning

TD与DP的关系

DP与TD关系1 DP与TD关系2

特点

  1. explore and exploit
  2. Delayed reward
  3. Time critical(时间处理实现)
  4. Agent actor稳定提升