约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择

admin 4个月前 (05-28) 科技 38 0

在上一篇博客:DQN(Deep Q-learning)入门教程(一)之强化学习先容中有三个很主要的函数:

  • 计谋:\(\pi(a|s) = P(A_t=a | S_t=s)\)

  • 状态价值函数:\(v_\pi(s)=\mathbb{E}\left[R_{t+1}+\gamma \left(S_{t+1}\right) | S_{t}=s\right]\)

  • 动作价值函数:\(q_{\pi}(s,a) = \mathbb{E}_{\pi}(R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_t=s, A_t=a)\)

两个价值函数划分代表了某个状态的价值,和在状态\(s_t\)下做某个action的价值。而计谋函数就是我们需要举行求解的。由于对于我们来说,一定是希望某个计谋能够获得最大的价值。比如说,你会选择努力学习而不是去网吧,以获得棒棒糖的奖励。

一般来说,对照难去找到一个最优计谋,然则可以通过对照若干差别计谋的优劣来确定一个较好的计谋,也就是局部最优解。

​ ——强化学习(二)马尔科夫决议历程(MDP)

最优计谋

首先,我们知道“好的计谋发生好的价值”,因此计谋的利害可以通过价值的巨细来对照。我们界说最佳的计谋是 \(\pi_*\) ,而我们的目的就是为了寻找这个 \(\pi_*\)

  1. 最优状态价值函数:代表所有计谋下发生的差别状态的状态的价值函数中的最大值

    \[v_{*}(s) = \max_{\pi}v_{\pi}(s) \]

  2. 最优动作价值函数:代表所有计谋下发生众多动作价值函数中的最大值

    \[q_{*}(s,a) = \max_{\pi}q_{\pi}(s,a) \]

    怎么明白这个最优动作(行为)价值函数呢?小我私家以为(若是有错的话,迎接在谈论区留言告诉我)

应该是这样的:

现在我们有一个最好的计谋 \(\pi_*\),它一定能够保证我们获得最好的分数。我们在\(t\)时刻执行的动作是\(a\),然后在接下来的时刻,执行的计谋都是 \(\pi_*\) ,因此\(q_*(s,a)\) 一定是在当前状态\(s\)下能够执行\(a\)能够获得最好的分数了。那么,他有什么寄义呢?它可以代表在当前状态执行\(a\) 动作好欠好。比如说\(q_*(s,a_1) > q_*(s,a_2)\) 则就代表\(a_1\)\(a_2\)好,由于它能够获得更多的奖励分数。

  1. 两个之间的关系:

连系下图,我们可以知道:

\[v_{*}(s) = \max_{\pi}v_{\pi}(s) = \max_{a}q_{*}(s,a) \\ q_{*}(s,a) = \max_{\pi}q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{*}(s') \]

实际上,寻找最优计谋的历程就是寻找最优动作的历程:选取一个\(a\)使得\(q_{\pi}(s,a)\)最大。针对于最优计谋,基于动作价值函数我们可以界说为:

\[\pi_{*}(a|s)= \begin{cases} 1 & {if\;a=\arg\max_{a \in A}q_{*}(s,a)}\\ 0 & {else} \end{cases} \]

最优计谋实例

下图是UCL强化强化学习课程的一个实例,黄色圆圈的最先状态,红色方块的是竣事状态。\(R\)代表reward,每一个状态可以执行的action为红色字体(例如Facebook,Study等等),其中玄色的点分支对应的数字代表执行这个action之后的状态转移概率。

我们设衰减因子:\(\gamma = 1\),由于每一个state都只对应2个action,因此,我们设初始计谋\(\pi(a|s) = 0.5\)。其终点(也就是\(s_5\))没有下一个状态,同时也没有响应的动作,由于我们界说其价值为\(v_5 =0\)

这里复说一下状态价值函数的界说:\(v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s'))\)

  1. 针对于\(v_1\)\(v_1 = 0.5*(-1+v_1) +0.5*(0+v_2)\)
  2. 针对于\(v_2\)\(v_2 = 0.5*(-1+v_1) +0.5*(-2+v_3)\)
  3. 针对于\(v_3\)\(v_3 = 0.5*(-2+v_4) +0.5*(0+v_5)\)
  4. 针对于\(v_4\)\(v_4 = 0.5*(10+v_5) +0.5*(1+0.2*v_2+0.4*v_3+0.4*v_4)\)

解得方程组为:\(v_1=-2.3, v_2=-1.3, v_3=2.7, v_4=7.4\)

上面是我们牢固了计谋\(\pi(a,s) = 0.5\)获得得每一个状态得价值函数,因此上面的到的\(v\)很可能不是最大的价值函数,由于这个计谋不是最好的计谋。

追求最佳计谋就是寻找最佳得动作价值函数,因此我们若是能够获得最优动作价值函数,也就获得了计谋 \(\pi_*\)

照样以上面得谁人例子为例,通过求解每一个action对应得\(q_*(s,a)\)。然后就可以获得最优计谋。(计谋即为\(s_2 \rarr s_3 \rarr s_4 \rarr s_5\)

下图中的9.4应该为8.4

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第1张

求解历程如下所示,历程稍微有点多,实在是欠好使用Latex举行说明,就使用草稿纸举行推导了。

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第2张

上面的部门是我们人为的推导方式 ,电脑一定没有我们这么伶俐,那么对于电脑来说,应该怎么举行推导呢?

求解方式

求解方式有许多种,下面将先容一种最基本的动态计划算法。

动态计划

问题具有下列两个性子时,通常可以思量使用动态计划来求解:

  1. 一个庞大问题的最优解由数个小问题的最优解组成,可以通过寻找子问题的最优解来获得庞大问题的最优解
  2. 子问题在庞大问题内重复泛起,使得子问题的解可以被存储起来重复行使,也就是说子问题之间存在递推关系,通过较小的子问题状态递推出较大的子问题的状态。

而强化学习恰好知足这个。为什么呢?由于bellman方程:

\[\begin{equation} v_\pi(s) =\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) | S_{t}=s\right] \\ v_{\pi}(s)=\sum_{a \in A} \pi(a | s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{\pi}\left(s^{\prime}\right)\right) \end{equation} \]

我们可以将求解每一个状态的价值函数界说为子问题,由于递推的关系,我们可以使用上一此迭代获得的价值函数来更新此时的价值函数。(妙哉!!!)

强化学习有两个基本问题:

  1. 展望(Prediction):对给定计谋(\(\pi\)),奖励(Reward),状态集(S),动作集(A),和状态转化该概率(P),衰减因子(\(\gamma\)),目的是求解基于该计谋的价值函数 \(v_{\pi}\)
  2. 控制(Control):寻找一个最优计谋的历程(实际上就是寻找最优的价值函数)。对给定奖励(Reward),状态集(S),动作集(A),和状态转化该概率(P),衰减因子(\(\gamma\)),求解最优价值函数 \(v_*\) 和最优计谋 \(\pi_*\)

计谋评估求解展望问题

首先,我们来看若何使用动态计划来求解强化学习的展望问题,即求解给定计谋的状态价值函数的问题。这个问题的求解历程我们通常叫做计谋评估(Policy Evaluation)。

计谋评估的基本思路是从随便一个状态价值函数最先,依据给定的计谋,连系贝尔曼期望方程、状态转移概率和奖励同步迭代更新状态价值函数,直至其收敛,获得该计谋下最终的状态价值函数。

—— 强化学习(三)用动态计划(DP)求解

首先假设我们已知第\(k\) 轮的状态价值函数,那么我们就可以获得第\(k+1\)轮的状态价值函数:

\[v_{k+1}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{k}(s')) \]

同时又可以简化为:

\[\begin{equation}\mathbf{v}^{k+1}=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} \mathbf{v}^{k}\end{equation} \]

这里引用Planning by Dynamic Programming中的一个例子:我们有一个4x4的宫格。只有左上和右下的格子是终止格子。该位置的价值牢固为0,个体若是到达终止格子,则住手移动。个体在16宫格其他格的每次移动,获得的即时奖励\(R\)都是-1,若往界限走,则会返回到原来的位置(也就是下一个状态照样原来的地方)。个体只能上下左右移动,每次移动一个位置。衰减因子\(\gamma = 1\)\(P=1\)。给定的计谋是随机计谋,每个偏向的移动概率是\(0.25\)

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第3张

  • K=1时:

    第一行第二个:

    \[\begin{equation}\begin{aligned} v^{(1,2)} &= 0.25[(R +v^{1,0}) + (R +v^{1,1}) + (R +v^{1,2}) + (R +v^{2,1})] \\&= 0.25\times[(-1 + 0) + (-1 + 0) + (-1 + 0) + (-1 + 0)] \\&= -1 \end{aligned}\end{equation} \]

    其他同理,效果如图所示。

  • K=2时:

    第一行第二个:

    \[\begin{equation}\begin{aligned} v^{(1,2)} &= 0.25[(R +v^{1,0}) + (R +v^{1,1}) + (R +v^{1,2}) + (R +v^{2,1})] \\ &= 0.25\times[(-1 + 0) + (-1 + -1) + (-1 + -1) + (-1 + -1)] \\ &= \frac{7}{4} \\ &\approx-1.7 \end{aligned}\end{equation} \]

    然后我们一直这样迭代下去,直到每个格子的价值的转变小于某一个阈值时,我们会住手迭代。

    因此最终的获得效果如下:

    约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第4张

求解的历程并不庞大,固然,若是我们的数据许多的话,那么需要的迭代的次数也会增多。

计谋迭代求解控制问题

针对于第二个控制问题,我们可以基于一种初始化计谋,然后获得状态价值,然后在基于状态价值来实时的调整我们的计谋,这个方式就叫做计谋迭代(Policy Iteration)。历程示意图如下:

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第5张

其中调整的方式是贪心法。个体在某个状态下选择的行为是其能够到达后续所有可能的状态中状态价值最大的谁人状态。算法的流程如下:

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第6张

从算法中来看,实际上需要花费的步骤照样挺多的。先举行价值迭代,然后又举行计谋迭代,然后不符合的话又重复操作,一直迭代到价值和计谋收敛才可以。

价值迭代求解控制问题

上述的计谋迭代另有有一点问题,比如说上述的格子问题,实际上在\(k=3\)的时刻就已经获得最优动作计谋了:

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第7张

为领会决计谋迭代泛起的步骤多的问题,一个特殊的改善就是当计谋评估仅举行一次更新的时刻就住手。也就是说两者的区别如下:

  1. 计谋迭代:计谋更新盘算的是每一个状态\(s\)各个行为\(a\)期望值,然后举行更新旧值,直到\(v - V(s)\)小于某个阈值。然后在从其中选择最好的\(a\)
  2. 价值迭代:直迭代就是用某个行为 \(a\) 获得的最大的状态价值函数,来更新原来的状态价值函数,最后获得\(a\)

算法的流程如下:

约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择 第8张

不外值得注意的是,以上动态计划获得的计谋解\(\pi_*\)纷歧定是全局最优解,只是局部最优解。因此我们还需要使用探索率\(\epsilon\),来跳出局部最优解。

总结

关于最佳计谋的求解方式另有许多,比如说MC方式,时序差分方式等等,然则由于这个系列博客主要是为了快速入门到入土,就不那么详细的讲解了。若是想领会更多可以看看刘建平Pinard的强化学习。

在下一个篇博客中,将先容Q-learning。

参考

  • 强化学习(二)马尔科夫决议历程(MDP)
  • 强化学习(三)用动态计划(DP)求解
  • 强化学习 - 动态计划(Dynamic Programming)
  • Planning by Dynamic Programming
,

Sunbet

Sunbet www.361223.com Sunbet是进入Sunbet(www.sunbet.in)的主力站点。Sunbet开放Sunbet会员开户网址、Sunbet代理开户、Sunbet手机版下载、Sunbet电脑客户端下载等业务。

dafa888体育声明:该文看法仅代表作者自己,与本平台无关。转载请注明:约搏三公开船:DQN(Deep Q-learning)入门教程(二)之最优选择

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:796
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1392
  • 评论总数:427
  • 浏览总数:32073