强化学习——策略学习

Posted on

强化学习——策略学习

给定策略\(\pi\)，状态估值函数的贝尔曼方程： \[v_{\pi}(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_{\pi}(s') \Big], \quad \text{for all} \; s \in S\]

状态估值函数的贝尔曼最优性方程： \[\begin{align} v_*(s) &= \max_a E \Big[ R_{t+1} + \gamma v_*(S_{t+1}) \Big| S_t=s,A_t=a \Big] \nonumber \\ &= \max_a \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_*(s') \Big] \nonumber \end{align}\]

1. 动态规划方法

给定策略下状态估值函数的更新规则： \[v_{\pi}(s) = \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_{\pi}(s') \Big], \quad \text{for all} \; s \in S\] 上式为策略迭代的基础。

最优状态估值函数的更新规则： \[\begin{align} v_*(s) &= \max_a E \Big[ R_{t+1} + \gamma v_*(S_{t+1}) \Big| S_t=s,A_t=a \Big] \nonumber \\ &= \max_a \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_*(s') \Big] \nonumber \end{align}\] 上式是估值迭代的基础。

注意：上述两个公式中的等号表示“赋值”，不是贝尔曼方程中的“相等”。

1.1. 策略估值

给定策略\(\pi\)，该策略下的状态估值函数满足 \[v_{\pi}(s) \doteq \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_{\pi}(s') \Big]\]

假如环境\(p(s',r|s,a)\)已知，状态估值函数的求解方式有：

  • 求解线性方程组（计算开销大）；
  • 寻找不动点——迭代策略估值。

1.2. 迭代策略估值

迭代策略估值的更新规则： \[\begin{align} v_{k+1}(s) & \doteq E_{\pi} \Big[ R_{t+1} + \gamma v_k(S_{t+1}) \Big| S_t=s \Big] \nonumber \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s',r|s,a) \Big[ r+\gamma v_k (s') \Big] \nonumber \end{align}\] 也被称为“期望更新”。

Tip：状态\(s\)新一轮的估值是基于\(s\)所有可能的下一状态\(s'\)的期望计算得到的。

1.3. 迭代策略估值的实现

两种实现方式： * 同步更新：两个数组存放“新”和“旧”的状态估值； * 异步更新：收敛速度快一些，今早利用了新信息（只存放一个数组）。

迭代策略估值示例：

从上述示例中可以看出到\(k=3\)时其对应的贪心策略已经收敛，但是状态估值函数还没收敛。强化学习的目的是寻找最优策略，遍历所有的策略并计算其估值函数来寻找最优策略的计算量过大，所以提出策略提升的方法。

1.4. 策略提升

策略估值的目标是为了寻找更优的策略（策略提升）：

  • 策略\(\pi\)到估值函数\(v\)。

策略提升：

  • 根据当前策略的估值函数，寻找更优的策略（如果存在），逐步寻找到最优策略；
    • 根据策略\(\pi\)的估值函数\(v\)到更优策略\(\pi'\)；
  • 提升方法：
    • 给定一个确定策略\(\pi\)，在状态\(s\)下选择行动\(a\)，后续按照策略\(\pi\)进行所得的估值\(q_{\pi}(s,a)\)是否高于完全按照策略\(\pi\)得到的估值\(v_{\pi}(s)\)： \[\begin{align} q_{\pi}(s,a) & \doteq E \Big[ R_{t+1} + \gamma v_{\pi} (S_{t+1}) \Big| S_t=s,A_t=a \Big] \nonumber \\ &= \sum_{s',r} p(s',r|s,a) \Big[ r + \gamma v_{\pi} (s') \Big] \nonumber \end{align}\]

策略提升定理：
对于两个确定式策略\(\pi\)和\(\pi'\)，如果对于所有状态\(s\)均满足 \[q_{\pi}(s,\pi'(s)) \geqslant v_{\pi}(s)\] 则策略\(\pi'\)优于策略\(\pi\)，即 \[v_{\pi'}(s) \geqslant v_{\pi}(s)\]

给定策略\(\pi\)，按照贪心方式得到更优策略\(\pi'\)： \[\begin{align} \pi'(s) & \doteq \mathop{\arg \max}_a q_{\pi}(s,a) \nonumber \\ &= \mathop{\arg \max}_a E \Big[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) \Big|S_t=s,A_t=a \Big] \nonumber \\ &= \mathop{\arg \max}_a \sum_{s',r} p(s',r|s,a) \Big[ r + \gamma v_{\pi}(s') \Big] \nonumber \end{align}\]

对于策略\(\pi'\)，进行策略估值： \[\begin{align} v_{\pi'}(s) &= \max_a E \Big[ R_{t+1} + \gamma v_{\pi'}(s_{t+1}) \Big| S_t=s, A_t=a \Big] \nonumber \\ &= \max_a \sum_{s',r} p(s',r|s,a) \Big[ r+ \gamma v_{\pi'} (s') \Big] \nonumber \end{align}\]

1.5. 策略迭代

分析：策略迭代过程中，策略估值需要多次扫描更新状态估值，精确估计当前策略的状态估值耗费了大量计算时间，是否可以在不精确的状态估值下，进行策略提升。

1.6. 估值迭代

从初始策略\(v_0\)开始，进行估值迭代，找到最优状态估值\(v_*\)，进而根据\(v_*\)按照贪心方式得到最优策略\(\pi_*\)：

1.7. 广义策略迭代

迭代进行两个阶段：

  • 策略估值：让新的估值和当前的策略保持一致；
  • 策略提升：根据当前估值，得到相应的贪心策略。

1.8 动态规划小结

  • 动态规划方法只不过是把贝尔曼方程转变为更新规则；
    • 四个贝尔曼方程对应着四个更新规则（\(v_{\pi},v_*,q_{\pi},q_*\)）；
  • 动态规划方法是一种“自举”（bootstrapping）方法；
  • 优势：动态规划方法计算效率高；
  • 缺点：动态规划方法需要知道关于环境的完整模型。

2. 蒙特卡洛方法

2.1. 动机

  • 动态规划方法需要知道关于环境的完整模型；
  • 大部分情况下没有关于环境的完整模型，或模型过于复杂。

蒙特卡洛方法：

  • 从真实或者模拟的经验（experience）中计算状态（行动）估值函数；
  • 不需要关于环境的完整模型。

2.2. 蒙特卡洛方法

状态估值：从某个状态\(s\)出发，使用当前策略\(\pi\)通过蒙特卡洛模拟的方式生成多个episode，使用这些episode的平均回报值近似状态估值函数\(v_{\pi}(s)\)。

收敛速度大约为：\(\frac{1}{\sqrt{n}}\)（\(n\)表示蒙特卡洛模拟次数）。

2.3. 优势

  • 直接根据真实经验或模拟经验计算状态估值函数；
  • 不同状态的估值在计算时是独立的。

2.4. 基于蒙特卡洛方法的策略迭代

  • 在完整的环境模型未知时，仅有状态估值\(v_{\pi}(s)\)无法得出策略\(\pi\)；
  • 大多数情况下，直接使用蒙特卡洛方法计算行为估值函数\(q_{\pi}(s,a)\)，进而采用贪心方法得到策略\(\pi\)。

2.5. 面临的问题

问题：部分“状态-行为”在蒙特卡洛模拟中可能不出现。

解决：Exploring Start：每个“状态-行为”对都以一定的概率作为蒙特卡洛模拟的起始点。

2.6. 摒弃Exploring Start

  1. On-policy方法：
    • 在每个状态\(s\)下保持对所有行为\(A(s)\)进行探索的可能性（\(\varepsilon\)贪心）：
      • 以\(1- \varepsilon + \frac{\varepsilon}{A(s)}\)选择贪心行为，以\(\frac{\varepsilon}{A(s)}\)的概率选择任意非贪心行为；
    • 缺点：最终得到的最优策略仅仅是\(\varepsilon\)最优策略（\(\varepsilon\)-soft policy）。
  2. Off-policy方法：
    • 使用两个策略：目标策略\(\pi\)和行为策略\(b\)；
    • 目标策略是待优化的策略，以贪心方式进行；
    • 探索策略保证在每个状态下对所有行为进行探索的可能性。

2.7. On-policy蒙特卡洛方法

On-policy方式部分放弃了最优性来换取对策略的探索：

2.8. Off-policy蒙特卡洛方法

保证寻找最优策略，在优化目标策略\(\pi\)时，用行为策略\(b\)进行策略探索：

  • 行为策略需要确保对行为的覆盖度（coverage）；
    • 对于所有\(\pi(a|s)>0\)，需要有\(b(a|s)>0\)；
  • 缺点：方差比较大，收敛慢；
  • 行为策略的选择影响收敛速度和方差；
    • 通过重要度采样方式对蒙特卡洛模拟结果进行加权。

2.9. 小结

  • 从经验中学习，不需要知道完整的环境模型；
  • 适用于环境模型未知或者环境模型复杂的情形；
  • 收敛性由大数定理保证；
  • On-policy和Off-policy两种实现；
    • 平衡exploitation和exploration。

3. 时序差分方法

非平稳情形下的蒙特卡洛方法（恒定步长）： \[V(S_t) \gets V(S_t) + \alpha [G_t - V(S_t)]\] 其中\(G_t\)表示第\(t\)轮蒙特卡洛模拟的回报，\(V(S_t)\)表示第\(t\)轮对状态\(S_t\)的估值。

时序差分方法（Temporal Difference：TD）： \[V(S_t) \gets V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]\]

不需要根据完整的episode计算\(G_t\)，只需要模拟几步（此处为1步）之后更新状态估值。

3.1. 实现

一步时序差分方法\(TD(0)\)的实现

3.2. 分析

时序差分方法是强化学习中最核心的策略学习方法。

  • TD和蒙特卡洛方法的联系和区别：
    • 联系：都是从经验中学习；
      • 非平稳情形下的蒙特卡洛方法是TD的特例；
    • 区别：蒙特卡洛方法需要episode完整的信息，TD只需要episode的部分信息；
  • TD和动态规划方法的联系和区别：
    • 联系：TD和动态规划方法都采用自举的方法；
    • 区别：动态规划方法依赖于完整的环境模型进行估计，TD依赖于经验进行估计。

时序差分方法是“learn a guess from a guess”。

时序差分方法的收敛性并没有理论证明，只是经验收敛。

3.3. 基于时序差分方法的On-policy策略优化

Sarsa：估计行为估值函数

3.4. 基于时序差分方法的Off-policy策略优化

Q-Learning（Watkins，1989）：

On-policy和Off-policy的区别：

  • On-policy：优化和探索的为同一函数；
  • Off-policy：优化和探索的为不同函数。

3.5. 小结

  • 一种在线的从经验中进行策略学习的方法；
  • 一般直接学习行为估值函数完成策略学习；
  • 适用于状态和行为空间比较小的问题。

动态规划/蒙特卡洛/时序差分对比：

4. 参数近似方法

当状态空间或行为空间比较大时，采用表格方式存放状态估值或行为估值不可行。需要对状态估值或行为估值进行参数化近似（parameterized approximation）。

4.1. 参数化近似方法

参数化的函数形式：

  • 广义线性模型
    • 参数是特征的权重
  • 决策树
    • 参数是叶子节点的取值，和树节点分裂的阈值
  • 神经网络
    • 每层的连接圈中

一般要求：参数个数要小于状态（或状态-行为）的个数。

4.2. 参数学习

训练样本形式：

  • 动态规划方法：\(s \rightarrowtail E_{\pi}[R_{t+1} + \gamma \hat{v}(S_{t+1},\pmb{w_t})|S_t=s]\)；
  • 蒙特卡洛方法：\(S_t \rightarrowtail G_t\)；
  • 时序差分方法：\(S_t \rightarrowtail R_{t+1} + \gamma \hat{v} (S_{t+1},\pmb{w}_t)\)；

适合强化学习参数学习的监督学习方法：

  • 能够进行在线训练，应对目标函数的不平稳或训练样本标注的不平稳；
  • 不能依赖于对训练样本的多次扫描。

4.3. 损失函数

平均平方估值误差（Mean Squared Value Error）： \[\overline{VE}(\pmb{w}) \doteq \sum_{s \in S} \mu(s) [v_{\pi}(s) - \hat{v}(s,\pmb{w})]^2 \]

\(\mu(s)\)刻画状态\(s\)的重要程度（如状态被访问到的次数）。

4.4. 模型训练

随机梯度下降（SGD）： \[\begin{align} \pmb{w}_{t+1} & \doteq \pmb{w}_t - \frac{1}{2} \alpha \nabla[v_{\pi}(S_t) - \hat{v}(S_t,\pmb{w}_t)]^2 \nonumber \\ & = \pmb{w}_t + \alpha [v_{\pi} (S_t) - \hat{v}(S_t,\pmb{w}_t)] \nabla \hat{v}(S_t,\pmb{w}_t) \nonumber \end{align}\]

\(\alpha\)是学习步长。

当目标值\(v_{\pi}(S_t)\)观测不到、只观测到其近似值\(U_t\)时 \[\pmb{w}_{t+1} \doteq \pmb{w}_t + \alpha [U_t - \hat{v}(S_t,\pmb{w}_t)] \nabla \hat{v}(S_t,\pmb{w}_t)\]

示例：

4.5. “半”随机梯度下降

在“自举”式观测值情况下：

  • 以时序差分方法TD(0)为例，此时的观测值为 \[U_t \doteq R_{t+1} + \gamma \hat{v}(S_{t+1},\pmb{w})\] 此时观测值也是关于参数\(\pmb{w}\)的函数。

半随机梯度不保障收敛，在线性函数下收敛性尚好。

4.6. 参数近似Q

半梯度Sarsa：一种On-policy的TD(0)；

  • 目标： \[\hat{q}(s,a,\pmb{w}) \approx q_*(s,a)\]
  • 参数学习过程： \[\begin{align} \pmb{w}_{t+1} & \doteq \pmb{w}_t + \alpha [U_t - \hat{q}(S_t,A_t,\pmb{w}_t)] \nabla \hat{q} (S_t,A_t,\pmb{w}_t) \nonumber \\ &= \pmb{w}_t + \alpha [R_{t+1} + \gamma \hat{q} (S_{t+1},A_{t+1},\pmb{w}_t) - \hat{q} (S_t,A_t,\pmb{w}_t)] \nabla \hat{q} (S_t,A_t,\pmb{w}_t) \nonumber \end{align}\]

4.7. 策略梯度

  • 策略梯度（policy gradient） \[\pi(a|s,\pmb{\theta}) = Pr\{A_t=a|S_t=s, \theta_t=\theta \}\]
  • 一般情况下目标函数\(J(\pmb{\theta)}\)定义为策略的表现性能
    • 采用随机梯度上升法进行优化 \[\pmb{\theta}_{t+1} = \pmb{\theta}_t + \alpha \widehat{\nabla j(\pmb{\theta}_t)} \]
  • Actor-Critic方法
    • 同时学习参数化的状态估值函数\(v(s,w)\)和策略\(\pi(a|s,\pmb{\theta})\)