RL-赵-(七)-不基于模型2-计算Q/ActionValue-TD算法02：Expected Sarsa【Sarsa的变形：将qₜ(sₜ₊₁,aₜ₊₁)改为E[qₜ(sₜ₊₁,A)]】

二、Sarsa变形Expected SarsaExpected Sarsa算法{ q t 1 ( s t , a t ) q t ( s t , a t ) − α t ( s t , a t ) [ q t ( s t , a t ) − ( r t 1 γ E [ q t ( s t 1 , A ) ] ) ] , q t 1 ( s , a ) q t ( s , a ) , ∀ ( s , a ) ≠ ( s t , a t ) , \color{red}{ \begin{cases} q_{t1}(s_t,a_t)q_t(s_t,a_t)-\alpha_t(s_t,a_t)\Big[q_t(s_t,a_t)-(r_{t1}\gamma\mathbb{E}[q_t(s_{t1},A)])\Big],\\[3ex] q_{t1}(s,a)q_t(s,a),\quad\forall(s,a)\neq(s_t,a_t), \end{cases}}⎩⎨⎧​qt1​(st​,at​)qt​(st​,at​)−αt​(st​,at​)[qt​(st​,at​)−(rt1​γE[qt​(st1​,A)])],qt1​(s,a)qt​(s,a),∀(s,a)(st​,at​),​其中E [ q t ( s t 1 , A ) ] ∑ a π t ( a ∣ s t 1 ) q t ( s t 1 , a ) ≐ v t ( s t 1 ) \mathbb{E}[q_t\left(s_{t1},A\right)]\sum_a\pi_t\left(a|s_{t1}\right)q_t\left(s_{t1},a\right)\doteq v_t\left(s_{t1}\right)E[qt​(st1​,A)]∑a​πt​(a∣st1​)qt​(st1​,a)≐vt​(st1​)是策略π t \pi_tπt​下的q t ( s t 1 , A ) q_t\left(s_{t1},A\right)qt​(st1​,A)的expected value。Expected Sarsa与Sarsa的区别是TD target从Sarsa中的r t 1 γ q t ( s t 1 , a t 1 ) r_{t1}\gamma q_t\left(s_{t1},a_{t1}\right)rt1​γqt​(st1​,at1​)变为Expected Sarsa中的r t 1 γ E [ q t ( s t 1 , A ) ] r_{t1}\gamma\mathbb{E}[q_t\left(s_{t1},A\right)]rt1​γE[qt​(st1​,A)]。需要更多的计算但是因为随机变量从( s t , a t , r t 1 , s t 1 , a t 1 ) (s_t,a_t,r_{t1},s_{t1},a_{t1})(st​,at​,rt1​,st1​,at1​)变为( s t , a t , r t 1 , s t 1 ) (s_t,a_t,r_{t1},s_{t1})(st​,at​,rt1​,st1​),减少了随机变量所以减少了estimation variances。Expected Sarsa在解决一个什么样的数学问题呢同样的Expected Sarsa也是在求解一个贝尔曼公式只不过这个贝尔曼公式的形式发生了一些变化。具体来说Expected Sarsa是求解下面等式的一个stochastic approximate algorithmq π ( s , a ) E [ R t 1 γ E A t 1 ∼ π ( S t 1 ) [ q π ( S t 1 , A t 1 ) ] ∣ S t s , A t a ] , ∀ s , a . q_{\pi}(s,a)\mathbb{E}\Big[R_{t1}\gamma\mathbb{E}_{A_{t1}\sim\pi(S_{t1})}[q_{\pi}(S_{t1},A_{t1})]\Big|S_{t}s,A_{t}a\Big],\quad\forall s,a.qπ​(s,a)E[Rt1​γEAt1​∼π(St1​)​[qπ​(St1​,At1​)]​St​s,At​a],∀s,a.上面等式是贝尔曼公式的另一个表达形式q π ( s , a ) E [ R t 1 γ v π ( S t 1 ) ∣ S t s , A t a ] , q_\pi(s,a)\mathbb{E}\Big[R_{t1}\gamma v_\pi(S_{t1})|S_ts,A_ta\Big],qπ​(s,a)E[Rt1​γvπ​(St1​)∣St​s,At​a],刚刚我们介绍了Sarsa 那相比最开始介绍的TD算法大家也看到了Sarsa和TD算法形式基本上是一模一样的唯一有两点区别第一点就是Sarsa是直接来估计action value第二点区别就是我们把Sarsa和policy improvement步骤相结合 这样就得到了一个能够搜索最优策略的算法下面我们再介绍Sarsa的两个变形一个叫Expected Sarsa 一个叫n-step Sarsa相对来说它们的重要性是没有Sarsa那么高的但是我也想放到这里其实我从一个经典的算法出发 然后去做推广改进这个是做研究的一个非常常见的一个思路那大家可以看一下 我怎么样从经典的Sarsa可以得到更多的这样一个算法 那我们下面来看Expected Sarsa这个就是Expected Sarsa的算法 第二个式子还是一样的第一个式子基本上也是一样的唯一区别就是在这个地方 这边是一个expectation这个expectation我写到这里就是对这个a进行求expectation那它写开就是这样一个表达式 那我在st1我有很多个a的选项可以选择 我选择a的概率是这个选择a之后的值是这个 所以根据expectation的定义我们就得到这个 那这时候实际上这个值是什么呢实际上它是对应的在st1的一个state value而不再是一个action value所以相比Sarsa那它的区别就是我这个TD target我从Sarsa里边是这个然后在Expected Sarsa里面变成了这个Sarsa里边需要at1 这里边不再需要at1这是它们的区别 那么相比Sarsa它的计算量要求更大因为我要计算这样一个式子 但因为我这里边去掉了at1我不再需要对at1进行采样所以它涉及到的随机变量的个数减少了那相对来说它的随机性也会减少 那么Expected Sarsa它究竟是在解决一个什么样的数学问题呢我们知道Sarsa它是来求解一个贝尔曼公式Expected Sarsa一样 它也是在求解一个贝尔曼公式只不过这个贝尔曼公式的形式又稍微发生了一些变化这里边的区别就是在刚才其实我们是没有expectation在这边现在是多了一个expectation也就是我要对这里边的At1 我在这就要求expectationSt1是在外边才求expectation然后整个这个expectation实际上就是vπ(St1)也就是St1所对应的state value那这个式子其实大家看起来就很清晰了qπ我从(s,a)出发我的action value等于immediate reward的加上γ再加上这个state value最后外边求一个expectation 所以这个也是一个贝尔曼公式那我们同样地可以把Expected Sarsa应用到我们之前提到的那个网格世界的例子当中然后这里的任务是从这个状态出发然后最后要找到到达目标的这样一个轨迹或者是策略那根据Expected Sarsa所得到最后的策略就是这样如果我们沿着概率比较大的这个方向走确实是能够到达目标的 就能够解决问题同样的因为这里边我只需要找到从这个状态出发到目标的路径其它的这些状态它们的策略可能不是最优的但是这个并不是我们所关心的右边这个图也展示了它在这个过程当中随着逐渐地学习它每一个episode的所收集这个reward的也越来越大同时episode的到达目标的长度所需要的步数也越来越少参考资料【强化学习】强化学习数学基础时序差分方法