RL——强化学习与动态规划

前言

动态规划 (Dynamic Programming, DP) 就是先把复杂问题分解为若干的子问题，再通过求解这些子问题来得到原问题的解。这适合解决满足如下两个性质的问题：
最优子结构 (optimal substructure)：一个原问题可以拆分成一个个的小问题，解决这些小问题后能够通过组合小问题的解来得到原问题的最优解。
重叠子问题 (overlapping subproblems)：子问题出现多次，并且子问题的解能被存储起来重复使用。

马尔科夫决策过程正好满足动态规划的这两个要求：贝尔曼方程把问题分解成一个递归的结构来求解子问题，价值函数可以存储并复用它的最佳解。因此我们就可以使用动态规划的方法来求解马尔科夫决策过程的核心问题：预测和控制。

预测 (prediction)：已知一个马尔科夫决策过程 MDP 和一个策略 π，或者是给定一个马尔科夫奖励过程 MRP，求解基于该策略的价值函数 vπ。（评估一个给定的策略）
控制 (control)：已知一个马尔科夫决策过程 MDP，求解最优价值函数 v∗ 和最优策略 π∗。（搜索最佳策略）
这两种问题的区别在于，预测问题是策略已给，我们需要确定它的价值函数是多少，而控制问题是要在没有策略的前提下确定最优的价值函数以及对应的策略。两者之间存在递进关系，在强化学习中，我们通过解决预测问题，进而解决控制问题。

1. 同步动态规划 (Synchronous Dynamic Programming)

同步动态规划算法中，每一次迭代都更新所有状态的价值

2. 异步动态规划 (Asynchronous Dynamic Programming)

在异步动态规划算法中，每一次迭代并不对所有状态的价值进行更新，而是依据一定的原则有选择性地更新部分状态的价值，这种算法能显著节约计算资源，并且只要所有状态能够得到持续的访问更新，那么也能确保算法收敛至最优解。
下面分别介绍比较常用的异步动态规划思想：
原位动态规划 (in-place dynamic programming)：直接利用当前状态的后续状态的价值来更新当前状态的价值。
优先级动态规划 (prioritised sweeping)：对每一个状态进行优先级分级，优先级越高的状态其状态价值优先得到更新。
实时动态规划 (real-time dynamic programming)：直接使用个体与环境交互产生的实际经历来更新状态价值，对于那些个体实际经历过的状态进行价值更新。

3. 动态规划

动态规划算法使用全宽度(full-width)的回溯机制来进行状态价值的更新,也就是说,无论是同步还是异步动态规划,在每一次回溯更新某一个状态的价值时,都要追溯到该状态的所有可能的后续状态,并结合已知的马尔科夫决策过程定义的状态转换矩阵和奖励来更新该状态的价值.这种全宽度的价值更新方式对于状态数在百万级别及以下的中等规模的马尔科夫决策问题还是比较有效的,但是当问题规模继续变大时,动态规划算法将会因贝尔曼维度灾难而无法使用,每一次的状态回溯更新都要消耗非常昂贵的计算资源.为此需要寻找其他有效的算法,这就是后文将要介绍的采样回溯.这类算法的一大特点是不需要知道马尔科夫决策过程的定义,也就是不需要了解状态转移概率矩阵以及奖励函数,而是使用采样产生的奖励和状态转移概率.这类算法通过采样避免了维度灾难,其回溯的计算时间消耗是常数级的.由于这类算法具有非常可观的优势,在解决大规模实际问题时得到了广泛的应用.

  • 动态规划算法是model-based算法，因为需要回溯当前状态的所有后续状态（full-width回溯机制）
  • model-free算法则无法使用动态规划算法（只能使用类似采样回溯等方法）
    • 蒙特卡罗法就是采样回溯法
    • model-free方法一般迭代公式中都包含着学习率超参数（有时候会1/N，用于模拟期望），而model-based算法可以直接获取到真实的概率转移情况，无需学习率超参数
  • TD（temporal difference）则是结合了蒙特卡罗法和动态规划法的方法
    • 类似于蒙特克罗法，需要模拟交互序列
      • 不同于蒙特卡罗法，不需要积累很多交互数据求均值
    • 类似于动态规划算法，求解公式里面使用当前回报和下一时刻的价值预估来更新当前时刻的价值
      • 不同于动态规划算法，不需要知道状态转移矩阵，也不需要full-width回溯
  • Q-learning的学习率为1，且model-based中状态转移矩阵取值为{0,1}时，Q-learning的迭代公式与价值迭代的迭代公式完全一致
    • 直观理解（不一定严谨）：由于Q-learning中，状态转移矩阵未知（下个状态的期望收益不可信），也就不一定是full-width回溯（一次更新所有状态）的，学习时需要增加学习率参数，否则很容易走偏；而model-based的价值迭代（动态规划方案）中，可以知道状态转移矩阵，求得的收益期望是可信的，而且是full-width回溯的，不需要增加学习率超参数（或者学习率为1）
      • 这里full-width的作用是什么呢？如果价值迭代中不是full-width的是否可以收敛呢？理论上是可以的吧【待确定】
      • 无法使用full-width的原因也就是状态转移矩阵未知，但是如果已知状态转移矩阵取值为{0,1}，那么理论上每次执行时都可以认为状态转移矩阵是已知的吧，因为环境返回的数据包含了下一个状态信息，而状态转移矩阵只能取P(S’|S)=1，此时Q-learning更像是一个异步动态规划算法（real-time 动态规划算法）