强化学习(2)

动态规划

通过把原问题分解为相对简单的子问题来求解复杂问题

马尔可夫决策过程满足如下两个属性 * 贝尔曼方程具有递归形式 * 价值函数可以保存和重复利用

贝尔曼最优方程如下,其难点是\(v_*\)同时存在于等式左右两边 \[ v_*(s)=max_a(R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av_*(s')) \]

价值迭代的基本思路: 1. 对\(v_∗\)定义一个估计函数\(v\) 2. 将估计函数代入方程右边, 等式左边得到一个新函数\(v′\) 3. \(v′\) 是对 \(v_∗\) 更为准确的估计 4. 将 \(v′\) 代入右式继续上述过程

\[ v'(s)=max_a(R_s^a+\gamma \sum_{s'\in S}P_{ss'}^av(s')) \]

价值迭代算子定义一个以函数作为输入的算子\(\tau\), 对给定的函数\(v_k\)计算新的函数 \(v_{k+1}(s)=[\tau(v_k)](s)\),贝尔曼最优方程写成 \[ v_*(s)=[\tau(v_*)](s)=max_a(R_s^a+\gamma\sum_{s'\in S}P_{ss'}^av_*(s')) \] \(\gamma < 1\) 时, 价值迭代算子是一个收缩算子(\(||\tau(f-g)||_{\infty}<||f-g||\))

确定性策略:价值迭代找到最优策略;随机性策略:机器人在所有位置以相同的概率向左或向右。

策略迭代:

  1. 给定一个初始策略 π1, k = 1
  2. loop
  3. 策略评估: 对当前策略 πk 计算它的价值函数 \(v_{πk}(s) = \mathbb E[R_{t+1} + \gamma R_{t+2} + ...|_St = s,A_t ∼ π_k(St)] =\sum_a π_k(a|s)(R^a_{ss'} + \gamma P^a_{ss′}v_{πk}(s′))\)
  4. 策略提升: 根据 \(v_{πk}\) 提取出新的策略 \(π_{k+1}(s) = argmax_{a\in A}(R^a_s + \gamma \sum_{s′\in S} P^a_{ss′}v_{πk}(s′))\)
  5. k←k+ 1
  6. end loop

价值迭代 vs 策略迭代

价值迭代 1. 只在收敛得到 \(v∗\) 后计算 \(π∗\), 中间过程不产生策略 2. 涉及赋值操作, 计算量小, \(O(|S|^2|A|)\) 3. 迭代次数多

策略迭代 1. 每次迭代开始时给定一个 \(π\), 结束时产生一个新 \(π′\) 2. 求解方程, 计算量大, 矩阵求逆 \(O(|S|^3)\), 策略提升 \(O(|S|^2|A|)\) 3. 迭代次数少

异步动态规划对每个状态单独更新价值函数值, 可以以任意一种顺序选择被更新的状态 只对被选中的状态更新价值, 未选中的保持不变

  1. 就地价值迭代只对整个状态集存储一个价值函数,
  2. 优化动态规划对拥有最大贝尔曼误差的状态更新价值。
  3. 实时动态规划 只考虑与智能体直接相关的状态

策略评估的不足:对模型的依赖\(R,P\)(MDP 问题的模型已知/智能体对环境建模)


蒙特卡洛方法MC

  1. MC 方法直接从经历过的事件中学习
  2. 无模型方法: 不需要 MDP 的转移/奖励函数
  3. 从完整的事件中学习: 没有自举
  4. 基于最简单的思想: 价值 = 平均回报
  5. 运行 MC 方法通常要求: 所有事件都到达终止状态或者事件的时序足够长
  • 目标: 从策略 \(\pi\) 产生的事件中学习 \(v_{\pi}\) \(S_1,A_1,R_2,...,S_k ∼ \pi\)
  • 回忆下回报的定义是所有折扣奖励和 \(G_t = R_{t+1} + \gamma R_{t+2} +···+ \gamma^{T−1}R_t\)
  • 回忆下价值函数的定义是回报的期望 \(v_π(s) = \mathbb E \pi[G_t|S_t = s]\)
  • 蒙特卡洛策略评估方法使用回报的经验均值作为回报的期望

每次经过的 MC 策略评估 * 为了评估状态 s * 对一次事件中每一次经过状态 s 的时刻 t * 计数加一 \(N(s) \leftarrow N(s) + 1\) * 全部回报相加 \(S(s) \leftarrow S(s) +G_t\) * 估计的价值等于回报均值 \(V(s) = S(s)/N(s)\) * 同样当 \(N(s) \rightarrow \infty\) 时, \(V(s) \rightarrow v_π(s)\)

P75 怎么算????

MC可以使用增量计算\(V(S_t)\leftarrow V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))\)


时间差分学习TD

  1. TD 方法直接从智能体经历的事件中学习
  2. 无模型的: 不知道 MDP 问题的转移和奖励函数
  3. 可以从非完整的事件中学习, 借助自举法
  4. 根据一个猜测值更新另一个猜测值

TD学习算法: * 调整价值 \((S_t)\) 向估计的回报 \(R_{t+1} + \gamma V(S_{t+1})\) 逼近 \(V(S_t) \leftarrow V(S_t) + α(R_{t+1} + \gamma V(S_{t+1})−V(S_t))\) * \(R_{t+1} + \gamma V(S_{t+1})\) 称为TD 目标 * \(\delta_t = R_{t+1} + \gamma V(S_{t+1})−V(S_t)\) 称为TD 误差

MC 与 TD 对比 * TD 可以在智能体运行过程中的每一步在线学习; MC 需要完整的事件序列计算出回报后学习 * TD 可以从不完整的事件序列中学习, MC 要求事件达到终止状态或序列足够长 * TD 是 低方差, 有偏差;MC 是 高方差, 零偏差 * TD 能够利用马尔可夫性,因此在马尔可夫环境下更有效; MC 能利用马尔可夫性因此在非马尔可夫环境下更有效(只考虑reward)

P90 AB问题:假如应用MC算法,由于需要完整的episode,因此,只有episode 1 能够用来计算A的状态值,所以显然,V(A) = 0;同时B状态的价值为6/8。而对于TD算法来说,由于状态A的后继有状态B(A->B是100%;B->1是75%),所以状态A的价值是通过状态B的价值来计算的。所以根据上面TD的计算公式,V(A)=V(B) = 6/8

自举法 : 更新时包含一个猜测量;采样法 : 使用采样的数据计算期望 * MC 不使用自举,使用采样 * DP 使用自举,不使用采样 * TD 使用自举,使用采样

\(\lambda -回报\): 每项的权重\((1-\lambda)\lambda^{n-1}\)前向更新 \[ G_t^{\lambda}=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}\\ V(S_t)\leftarrow V(S_t)+\alpha(G_t^{\lambda}-V(S_t)) \]

资格迹:受频率启发;受近因启发(二者结合)更新量与 TD 误差 和资格迹 \(E_t(s)\) 呈正比 后向更新 \[ \delta_t = R_{t+1}+\gamma V(S_{t+1})-V(S_t)\\ V(s)\leftarrow V(s) + \alpha\delta_tE_t(s) \]

TD(1) 大致等价于每次经过的 MC 方法,误差会随在线运行逐步累积,如果价值函数只在事件结束时离线更新, 那么所有的更新量等同于 MC 方法