强化学习(二)

最优策略

由上一节我们已经知道，在确定环境后，一个给定的策略$\pi$确定值函数$v$和$q$，所以我们将贝尔曼方程表示为 $v_{\pi}(s)=\sum\limits_{a \in A}\pi(a|s)\cdot q_{\pi}(s,a) \tag{1.1}$ $q_{\pi}(s,a)=r_s^a+\gamma\cdot\sum\limits_{s' \in S}P(s_{t+1}=s'|s_t=s,a_t=a)\cdot v_{\pi}(s') \tag{1.2}$

记$\Pi$为所有策略的集合，下面先定义$\Pi$和$v$值函数上的偏序。

$\pi \geq \pi^{‘}$当且仅当对$\forall s \in S$,有$v_{\pi}(s) \ge v_{\pi^{‘}}(s)$

同理$\Pi$和$q$值函数上的偏序定义为

$\pi \geq \pi^{‘}$当且仅当对$\forall s \in S,a \in A$,有$q_{\pi}(s,a) \ge q_{\pi^{‘}}(s,a)$

记$\pi_{*}$为最优策略，则 $\pi_{*}=argmax_{\pi}[v_{\pi}(s)] \tag{1.3}$

记 $q_{*}(s,a)=max_{\pi}[q_{\pi}(s,a)] \tag{1.4}$ $v_{*}(s)=max_{\pi}[v_{\pi}(s)] \tag{1.5}$

由(1.2)和(1.3)，当$\pi = \pi_{*}$时，$q$函数也取到最优值。

最优值函数贝尔方程

由上述结论和(1.1)，(1.2)我们会有 $v_{*}(s)=\sum\limits_{a \in A}\pi(a|s)\cdot q_{*}(s,a) \tag{2.1}$ $q_{*}(s,a)=r_s^a+\gamma\cdot\sum\limits_{s' \in S}P(s_{t+1}=s'|s_t=s,a_t=a)\cdot v_{*}(s') \tag{2.2}$

由2.1，如果我们给定最优行为值函数$q_{*}$,有

$$\pi_{*}(a|s)=1 \quad if \quad a = argmax_{a}[q_{*}(s,a)]$$ $$\pi_{*}(a|s)=0 \quad ohterwise \tag{2.3}$$

但是我们还要说明此时的策略$\pi_{*}$能保证$q$取到$q_{*}$

。

由2.1和2.2我们有 $q_{*}(s,a)=r_s^a+\gamma\cdot\sum\limits_{s' \in S}P(s_{t+1}=s'|s_t=s,a_t=a)\cdot (\sum\limits_{a' \in A}\pi(a'|s')\cdot q_{*}(s',a')) \tag{2.4}$

我们要验证给定$q_{*}$我们(2.3)确定的策略可以使$q$取到$q_{*}$,由(2.4)，取我们的策略时，右边是可以取到最大值的，而右边是等同于左边的。这表明我们的$q$取到了最大值。

后续~

• Previous
  HackerRank Problem minm-loss
• Next
  HackerRank Problem Points on a Rectangle