(强化学习)- 动态规划寻找最优策略和不基于模型的学习

动态规划寻找最优策略

动态规划问题中一般都有:

  • 重叠的子问题
  • 通过解决子问题可以得到整个问题的解马尔可夫决定过程(MDP)具有上述的两个属性。

预测和控制是规划的两个重要的内容。预测是对给定的策略的评估过程;控制是寻找一个最优策略的过程。

  • 预测:已知一个马尔可夫决策过程 MDP $<S,A,P,R,\gamma>$和一个策略$\pi$,或者是一个马尔可夫奖励过程MRP$<S,P_\pi,R_\pi,\gamma>$,求解基于该策略的价值函数$v_\pi$
  • 控制:已知一个马尔可夫决策过程 MDP $<S,A,P,R,\gamma>$,求最优价值函数$v_*$和最优策略$\pi$

策略评估

计算给定策略下状态价值函数的过程。贝尔曼期望方程给出了如何根据状态转换关系中后续状态$s^{'}$来结算当前状态$s$的价值,在同步迭代法中,使用上一个周期$k$内的后续状态价值来计算当前迭代周期$k+1$内某状态$s$的价值:

$$
\begin{equation}
v_{k+1}(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^av_k(s^{'}))
\end{equation}
$$

假设一个一个4x4的方格网络,只能上下左右移动一次,0和15状态都是终止状态。如果个体打算跳出格子,个体会有100%的几率保持不动。每移动一次,环境给予的回报:-1。简单起见,损失因子$\gamma=1$

由于个体并不清楚整个环境的特征,所以我们的个体需要不断的试探,而且他朝四个方向移动的概率是相等的为$\frac{1}{4}$,这个平均的策略是基于均一的随机策略。在这个策略的指导下,每一个状态的价值是不一样,对于个体来说,他需要经过多次的终止状态之后才能对各个状态的价值有一定的认识,这个人是的过程就是策略评估的过程

详细的计算过程:

  • 在图(b)中:4状态,根据公式:$v_1(s_4)=3\times0.25\times((-1)+1\times(0))+0=-1$,乘以4是因为除了向左的三个方向计算过程相同,向左出去了所以还是以1的概率保持不动,得到的值是$v_0(s_4)=0.0$。
  • 在图(c)中:4状态,$v_2(s_4)=2\times0.25\times(-1+(-1\times1))+0.25\times(-1+1\times(-1))+0.25\times(-1+0)=-1.75\approx-1.7$。第一项是因为向下和向右的计算步骤是一样的。第二项是向左移动,得到的值函数是$v_1(s_4)=-1.0$,也就是保持不动。第三项是向上的得到的价值是0。注意由于我明确了选择的行为,所以转移概率是$P_{ss^{'}}^a=1$。

策略改善

当k=2,4状态的时候,个体可以向上移动以获取最好的回报而不是以随机策略来选择下一个目标。从一个随机的策略中产生一个更好的策略就是策略改善的过程。给定一个策略$\pi$,可以基于这个策略的价值函数$v_\pi$,基于这个价值函数可以得到一个贪婪策略$\pi^{'}=\textrm{greedy}(v_\pi)$。依据这个策略$\pi^{'}$会得到新的价值函数,并产生新的贪婪策略,然后重复迭代最终将得到最优价值函数$v^*$和最优策略$\pi^*$

价值迭代

如果迭代的次数很多而且最终得到的最优策略和中间某次的某个策略相同的话,我们可以减少迭代次数而不影响最终得到的最优策略。

任何一个阶段的最优策略:

  • 这个策略产生的最优行为
  • 该行为到达的后续状态仍然是一个最优策略。之前的贝尔曼方程可以描述这种行为:

$$
\begin{equation}
v^*(s)=\max_a(R_s^a+\gamma\sum_{s^{'}\in S}P_{ss^{'}}^av^*(s^{'}))\\
\label{optimal_state_value_bellman}
\end{equation}
$$

如果能够知道最终的价值和相关的奖励,可以直接计算前一个所有可能的最优价值。以网格中的最短路径作为演示。假设左上角的格子是终止状态,初始的价值是0。在$V=1$的时候全部初始化所有状态值(根据$V=0$的终止状态的价值)

当$V=3$的时候,除了与终止状态相邻的两个状态,其他的状态的价值都将因采用一个行为获得的-1的回报以及前次迭代中$R_s^a=-1$而被更新为-2。当价值出现了-6的时候即$V=7$再次迭代不会出现了变化,于是整个迭代的过程便结束了。

迭代中价值函数的更新公式为:$$v_{k+1}(s)=\max_{a\in A}(R_s^a+\gamma\sum_{s^{'}\in S}v_k(s^{'}))$$

不基于模型的预测

之前记录的是基于动态规划(DP)解决已知的 MDP 过程。不基于模型(model-free)可以解决一个被认为是 MDP 但确不掌握 MDP 具体细节的问题,也就是说个体不需要对环境有认识(例如不需要知道一个运动模型)仅仅通过与环境实际交互来评估一个策略和好坏或者寻找最优价值函数和最优策略。

其中学习的过程就包括了基于完整采样的蒙特卡洛学习、基于不完整采样的时间差分学习和介于二者之间的$\lambda$时间差分学习。

蒙特卡洛强化学习

蒙特卡洛强化学习(Monte-Carlo reinforcement learning,MC学习):指在不清楚MDP状态转移概率的情况下,直接从经历完整的状态序列(episode)来估计状态的真实价值,并认为某状态的价值等于在多个状态序列中以该状态的带的所有收获的平均。

完整的状态序列:从某一个状态开始,个体与环境交互直到终止状态,环境给出终止状态的奖励为止。并不要求从某一个特定的状态开始。

基于特定策略$\pi$的一个 Episode 信息可以表示为一个序列:

$$S_1,A_1,R_2,S_2,\cdots,S_t,A_t,R_{t+1},\cdots,S_k\sim\pi$$

t 时刻状态$S_t$的回报:

$$G_t=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_T$$

其中T为终止时刻。该策略下一状态s的价值:

$$
\begin{equation}
v_\pi(s)=\mathbb{E}_\pi[G_t|S_t=s]
\label{v_pi_mean}
\end{equation}
$$

可以看出,在蒙特卡洛算法苹果策略时,要针对多个包含同一状态的完整状态序列求回报继而求回报的均值。这就有两种方法处理同一个状态出现了多次:

  • 首次访问(first visit): 求该状态第一次出现纳入求均值的计算中
  • 每次访问(every visit)

在求解回报的平均值的过程中,引入了累积平均值(incremental mean):

$$
\begin{aligned}
&\mu_k=\frac{1}{k}\sum^k_{j=1}x_j\\
&=\frac{1}{k}(x_k+\sum_{j=1}^{k-1}x_j)\\
&=\frac{1}{k}(x_k+(k-1)\mu_{k-1})\\
&=\mu_{k-1}+\frac{1}{k}(x_k-\mu_{k-1})
\end{aligned}
$$

如果把$\mu_k$看成$V(S_t)$,$x_k$看成$G_t$,k看成$N(S_t)$,(更新之前时$k-1$时刻)就可以得到:

$$
N(S_t)\gets N(S_t)+1\\
V(S_t)\gets V(S_t)+\frac{1}{N(S_t)}(G_t-V(S_t))
$$

在实时或者无法统计确切状态被访问的次数的时候,可用系数$\alpha$来代替倒数:

$$V(S_t)\gets V(S_t)+\alpha(G_t-V(S_t))$$

根据大数定律,只要$N(s)\rightarrow\infty$,则$V(s)\rightarrow v_\pi(s)$

时间差分强化学习

指从采样得到的不完整的状态序列的学习,该方法通过合理的引导(bootstrapping),先估计某状态在该状态序列完整后可能获得的回报,并利用累积更新平均值的方法得到该状态的价值,再通过不断的采样来持续更新这个价值。

具体的说:

$$V(S_t)\gets V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))$$

其中$R_{t+1}+\gamma V(S_{t+1})$称为TD 目标值。$R_{t+1}+\gamma V(S_{t+1})-V(S_t)$称为TD 误差

引导(bootstrapping):指的是用 TD目标值代替收获$G_t$的过程。

可以看出不管TD学习和MC学习,都不需要之前在动态规划算法中需要知道状态转移概率$P_{ss^{s}}^a$y以及所有的后续状态。他们都使用个体与环境交互产生的状态序列来更新状态的价值。

以驾车回家作为例子。回家会经过三段路程:高速公路、普通公路和附近街区的道路。

  • MC 算法:需要根据既往经验得出的回家时间$G_t=43$。对于所处的每一个状态都不会立即更新这些状态对应的到家的时间估计,仍然为30、35、15、10和3分钟。将这个实际的时间减去到达某个状态已耗时就可以得出仍然需要的时间为43、38、23、13和3分钟。
  • TD 算法:当取车的时候,发现下雨,就根据经验需要耗时35分钟。但是需要立即更新前一个状态,即离开办公室状态为35+5=40(分钟)。同样,当驶离高速公路的时候,根据经验还需要15分钟回家。但是,提前在20分钟的时刻提前下了高速,实际从取车到下高速只花了15分钟,所以前一个状态,即取车下雨的估计耗时为15+15=30(分钟)。

可以看出 TD 算法每转移到一个新的状态就会用实际的所花的时间来更新前一个状态的耗时估计。TD 算法的灵活性可以避免 MC 算法中只要行程结束后才更新各个状态的耗时所带来的无法处理突发情况而不能及地调低不好状态地价值地问题。

MC 算法和 TD 算法在驾车回家例子的比较:

MC 和 TD 的优缺点

性质 MC TD
方差 高,无偏估计 低,有偏估计
收敛性 有很好的收敛性质 TD(0)收敛到$v_\pi(s)$
初始值 不敏感 敏感

例子2

假设有A和B两种状态,模型未知。只涉及状态转换和即时回报,衰减系数为1。下表就是8个完整状态学列的经历,除第一个状态序列发生了状态转移外,其他的7个完整状态序列只有一个状态构成。试计算状态A和B的价值。

  • MC 算法:只有第一个序列包含了A,所以

$$V(A)=G(A)=R_A+\gamma R_B=0$$
状态B的价值,先求状态B在8个序列的回报的平均值,为$\frac{6}{8}$。在使用 MC算法的时候,状态A和B的价值分别为$V(A)=0\textrm{和}V(B)=\frac{6}{8}$。

  • TD 算法:TD 算法在计算状态序列中某状态价值的是应用其后续状态的预估价值来计算的。在表中,B状态作为终止状态。根据$v(s)$的定义和各个状态序列可以求出回报的平均值即$\frac{6}{8}$。状态A由于只存在第一个状态序列中,可以直接使用包含状态B价值的TD目标值来得到状态A的价值,即$R_{t+1}+\gamma V(S_{t+1})=0+1\times\frac{6}{8}=\frac{6}{8}$由于状态A的即时回报为0,在计算上一次的$V(A)$的时候,得到的TD 目标是0,所以在计算转移到状态B的时候,$V(S_t)=0$。所以$V(A)=0+\frac{6}{8}-0=\frac{6}{8}$。

TD 算法在计算价值的时候利用了状态序列中前后状态之间的关系。在这8个状态序列中,A有100%的几率转移到状态B,B有$\frac{1}{4}$的几率得到回报0,$\frac{3}{4}$的几率得到回报1。TD 算法视图构建一个MDP$<S,A,\hat P,\hat R,\gamma>$并是这个 MDP 尽量符合已产生的状态序列。TD 算法首先根据已有的经验估计状态转移的概率:

$$\hat P_{ss^{'}}^a=\frac{1}{N(s,a)}\sum_{k=1}^K\sum_{t=1}^{T_k}1(S_t^k,a_t^k,s_{t+1}^k=s,a,s^{'})$$

同时估计某一个状态的即时回报:

$$\hat R^a_s=\frac{1}{N(s,a)}\sum_{k=1}^K\sum_{t=1}^{T_k}1(s_t^k,a_t^k=s,a)r_t^k$$

最后计算该 MDP 的状态函数:

MC算法依靠完整状态序列的回报得到各个状态对应的收获来计算状态价值,这种算法是以最小化收获与状态价值之间的均方差为目标:

$$\sum_{k=1}^K\sum_{t=1}^{T_k}(G_t^k-V(s_t^k))^2$$

可见MC算法并不依赖于马尔可夫性,不限于马尔可夫性的环境。

DP、MC 和 TD 之间的比较

性质 DP MC TD
是否依赖模型
需要完整状态序列 DP是基于模型计算价值的方法,需要状态S的所有可能转移到的状态$S_{'}$、转移概率$P_{ss^{'}}^a$以及回报$R_s^a$
引导(bootstrapping)数据 使用后续状态的预估价值作来计算当前状态的价值 不使用 同DP
是否采样 不适用 使用个体与环境交互产生的采样状态状态序列计算价值 同MC

  • MC:深度采样学习。一次学习完整的经历,使用实际的收获更新状态预估价值。
  • TD:浅层采样学习。经历不完整,使用后续状态预估价值预估收获再更新当前状态的价值。
  • DP:浅层全宽度(采样)学习。依据模型,全宽度地使用后续状态预估价值来更新当前状态价值。

n步时间差分学习

n-步预测指从状态学列的当前状态$S_t$开始往序列的终止方向观察至状态$S_{t+n-1}$,使用这n个状态产生的即时奖励$R_{t+1},R_{t+2},\cdots,R_{t+n}$的预估价值来计算当前的状态$S_t$的价值。

TD 是 TD(0)的简写,是基于1步预测的。

定义n-步收获为:

$$G_t^{(n)}=R_{t+1}+\gamma R_{t+1}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^nV(S_{t+n})$$

当$n\rightarrow\infty$,$G_t^{(\infty)}=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_T$,记为 MC(MC 学习是基于$\infty$-步预测)。

n-步学习对应的状态价值函数的更新公式:

$$V(S_t)\gets V(S_t)+\alpha(G_t^{(n)}-V(S_t))$$

为了再不增加计算复杂度的情况下,引入参数$\lambda$,任意一个n-步收获权重被设计为$(1-\lambda)\lambda^{n-1}$:

得到公式:

$$G_t^\lambda=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}G_t^{(n)}$$

对应的$\textrm{TD}(\lambda)$被描述为:

$$V(S_t)\gets V(S_t)+\alpha(G_t^{(\lambda)}-V(S_t))$$

$\textrm{TD}(\lambda)$中对于n-收获的权重分配:

可以看到当T时刻终止的时候,后续的未分配的权重全部被终止状态的收获所拥有,保证权重的和为1。

前向认识$\textrm{TD}(\lambda)$

状态价值$V(S_t)$由$G_t^{(\lambda)}$得到,而后者由后续状态价值计算得到。当$\gamma=1$的时候,就与MC 算法相同。这样的$\textrm{TD}(\lambda)$就没什么优势可言了。

反向认识$\textrm{TD}(\lambda)$

首先是效用迹(eligibility traces)。如图,老鼠在连续三次响铃和一次亮灯之后被电击,那么在分析被点击的原因的时候,是响铃的因素重要还是亮灯的因素重要呢?

  • 频率启发式(frequency heurstic):把被电击的原因归结在前几次接受了较多次数的响铃
  • 就近启发式(recency heuristic):归因于最近少数几次状态的影响。

如果给每个状态引入一个数值:效用(eligibility)来表示改状态对后续状态的影响,就能利用上面的两种启发。所有状态的效用值总称为效用迹。定义:

$$
E_0(s)=0\\
E_t(s)=\gamma\lambda E_{t-1}(s)+1(S_t=s)\quad\gamma,\lambda\in[0,1]
$$

当$S_t=s$的时候判别式$S_t=s$为1,否则为0。

某一个状态的可能的轨迹:

很坐标代表时间,横坐标下面的竖线的代表当前的时刻状态为s,纵坐标时效用的值。可以看出当某个状态连续出现,E会在一定的衰减的基础上有一个单位的提高(1),可以认为这个状态对后续状态影响较大,如果之后状态没有什么经历,E值就会逐渐趋向0,表明对后续状态影响越小。E的值可以根据已经经过的状态序列来计算得到,并且在每一个时刻都对每一个状态进行更新。

E值存在饱和现象,有一个瞬时最高上限:

$$E_\textrm{sat}=\frac{1}{1-\lambda\gamma}$$

如果在更新状态价值时把该状态的效用考虑进来:

$$\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)\\
V(s)\gets V(s)+\alpha\delta_tE_t(s)
$$

  • 当$\lambda=0$时,$S_t=s$一直成立,此时的价值更新等同于$\textrm{TD}(0)$算法:

$$V(S_t)\gets V(S_t)+\alpha\delta_t$$

  • 当$\lambda=1$时,每完成一个状态序列后更新状态价值时,其完全等同于MC 学习;当引入了效用迹,可以在每历经一个状态就更新状态的价值
  • 当$\lambda\in(0,1)$时,在每完成一个状态学列后更新价值时,基于前向认识的$\textrm{TD}(\lambda)$与反向认识的$\textrm{TD}(\lambda)$完全等效。

反向认识$\textrm{TD}(\lambda)$:

参考&引用