【强化学习的数学原理】课程笔记--2(贝尔曼最优公式,值迭代与策略迭代)

目录

贝尔曼最优公式

作用:用于找到最优的 Policy

最优 Policy

如果存在一个 Policy π ∗ \pi^* π,st 对于 ∀ s \forall s s 以及 ∀ π \forall \pi π,都有 v π ∗ ( s ) ≥ v π ( s ) v_{\pi^*}(s) \geq v_{\pi}(s) vπ(s)vπ(s),则称为是最优 Policy

因此最优的 Policy 要保证每一个 state 上的 state value,都优于任一其他的 Policy 在该位置的 state value (Note:State Value 的定义是从当前 state 出发,一条无限长 (实践中足够长就可以)的 trajectory 的总期望得分,且 v π ( s ) = E [ R t + 1 ∣ S t = s ] + γ ∑ s ′ v π ( s ′ ) P ( S t + 1 = s ′ ∣ S t = s ) v_{\pi}(s) = E[R_{t+1}|S_t = s] + \gamma \sum_{s'} v_{\pi}(s') P(S_{t+1}=s'|S_t=s) vπ(s)=E[Rt+1St=s]+γsvπ(s)P(St+1=sSt=s),即当前 state 的 state value 取决于比它短一格的 trajectory 的总期望,其思路有点类似于 CRF 中使用的 Viterbi 算法,找的是全局最优,而不是局部最优)。现在有以下几个问题:

  1. 这样的 π ∗ \pi^* π 是否存在
  2. 这样的 π ∗ \pi^* π 是否唯一
  3. 这样的 π ∗ \pi^* π 是确定的还是有随机性

求解贝尔曼最优公式

首先回忆第一节当中的贝尔曼公式,一般形式:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v π ( s ′ ) ] , ∀ s \begin{aligned} v_{\pi}(s) = \sum_{a} \pi(a|s) [\sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v_{\pi}(s')], \quad \forall s \end{aligned} vπ(s)=aπ(as)[rP(rs,a)r+γsP(ss,a)vπ(s)],s

matrix-form:
v π = r π + γ P π v π v_{\pi} = r_{\pi} + \gamma P_{\pi} v_{\pi} vπ=rπ+γPπvπ
v π = ( I − γ P π ) − 1 r π v_{\pi} = (I-\gamma P_{\pi})^{-1} r_{\pi} vπ=(IγPπ)1rπ
其中 r π ( s i ) = ∑ a π ( a ∣ s i ) ∑ r P ( r ∣ s i , a ) r = E [ R t + 1 ∣ S t = s i ] r_{\pi}(s_i) = \sum_{a} \pi(a|s_i) \sum_{r} P(r|s_i,a)r = E[R_{t+1}|S_t=s_i] rπ(si)=aπ(asi)rP(rsi,a)r=E[Rt+1St=si], P π ( s i ) = ∑ s j P π ( s j ∣ s i ) P_{\pi}(s_i) = \sum_{s_j} P_{\pi}(s_j|s_i) Pπ(si)=sjPπ(sjsi)

找最优的 π ∗ \pi^* π 等价于找到最大的 State Value,即:
v π ∗ = max ⁡ ( ( I − γ P π ) − 1 r π ) , ∀ s , ∀ π ∈ Π v_{\pi^*} = \max ((I-\gamma P_{\pi})^{-1} r_{\pi} ), \forall s, \forall \pi \in \Pi vπ=max((IγPπ)1rπ)s,πΠ
上式等价于:
v π ∗ = max ⁡ ( r π + γ P π v π ∗ ) , ∀ s , ∀ π ∈ Π v_{\pi^*} = \max (r_{\pi} + \gamma P_{\pi} v_{\pi^*}), \forall s, \forall \pi \in \Pi vπ=max(rπ+γPπvπ)s,πΠ
后面我们将 v π ∗ v_{\pi^*} vπ 简记为 v ∗ v^* v,记 f ( v ) = max ⁡ π ( r π + γ P π v ) f(v) = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v) f(v)=πmax(rπ+γPπv)
那么 v ∗ v^* v 即满足 v ∗ = f ( v ∗ ) v^* = f(v^*) v=f(v) 的点。

求解最大 State Value v ∗ v^* v

求解上述 v ∗ = f ( v ∗ ) v^* = f(v^*) v=f(v) 需要引入 压缩映射定理

( X , d ) (X, d) (X,d) 是一个完备度量空间, T : X → X T: X \to X T:XX 是一个压缩映射,即存在一个常数 0 ≤ k < 1 0 \leq k < 1 0k<1,使得对于所有的 x , y ∈ X x, y \in X x,yX,有:
d ( T ( x ) , T ( y ) ) ≤ k ⋅ d ( x , y ) d(T(x), T(y)) \leq k \cdot d(x, y) d(T(x),T(y))kd(x,y)
那么 T T T X X X 中有 唯一 的不动点 x ∗ x^* x,即 T ( x ∗ ) = x ∗ T(x^*) = x^* T(x)=x。并且,对于任意初始点 x 0 ∈ X x_0 \in X x0X,迭代序列 { x n } \{ x_n \} {xn} 定义为:
x n + 1 = T ( x n ) x_{n+1} = T(x_n) xn+1=T(xn)
将收敛于不动点 x ∗ x^* x,即:
lim ⁡ n → ∞ x n = x ∗ \lim_{n \to \infty} x_n = x^* nlimxn=x

因此只要能证明存在一个度量函数 d d d,使得对于所以 v 1 , v 2 v_1, v_2 v1,v2 满足: d ( f ( v 1 ) , f ( v 2 ) ) ≤ k ⋅ d ( v 1 , v 2 ) d(f(v_1), f(v_2)) \leq k\cdot d(v_1, v_2) d(f(v1),f(v2))kd(v1,v2)
就可以证明:

  1. 最大 State Value v ∗ v^* v 存在且唯一
  2. 最大 State Value v ∗ v^* v 可以由 v k + 1 = f ( v k ) v_{k+1}=f(v_k) vk+1=f(vk) 迭代求解

根据 v ∗ v^* v 求解最佳 Policy π ∗ \pi^* π

由于 v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) v_{\pi}(s) = \sum_a \pi(a|s) q_{\pi}(s,a) vπ(s)=aπ(as)qπ(s,a)
其中 q π ( s , a ) q_{\pi}(s,a) qπ(s,a)从 state s 出发,且 take action a 的期望return,那么一定存在一个 a ∗ a^* a,使得:
a ∗ ( s ) = arg max ⁡ a ∈ A q ∗ ( s , a ) a^*(s) = \argmax_{a \in A} q^*(s,a) a(s)=aAargmaxq(s,a)
又由于 ∑ a π ( a ∣ s ) = 1 \sum_{a} \pi(a|s) =1 aπ(as)=1,因此使得 ∑ a π ( a ∣ s ) q π ( s , a ) \sum_a \pi(a|s) q_{\pi}(s,a) aπ(as)qπ(s,a) 取得最大值的 π ∗ \pi^* π 应该形如:
π ∗ ( a ∣ s ) = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) \pi^*(a|s) = \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} π(as)={1,a=a(s)0,a=a(s)
上述最佳 Policy π ∗ \pi^* π 是确定形式的,也称为“贪婪”的。根据上式,需要求解该 π ∗ \pi^* π 只需求解 a ∗ ( s ) , ∀ s a^*(s), \forall s a(s)s,而 a ∗ ( s ) = arg max ⁡ a ∈ A q ∗ ( s , a ) a^*(s) = \argmax_{a \in A} q^*(s,a) a(s)=argmaxaAq(s,a) ,所以只需要解得所有的 q ∗ ( s , a ) q^*(s,a) q(s,a),根据 第一节 的内容:
q ∗ ( s , a ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v ∗ ( s ′ ) q^*(s,a) = \sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v^*(s') q(s,a)=rP(rs,a)r+γsP(ss,a)v(s)

这里 v ∗ v^* v 可以由 v k + 1 = f ( v k ) v_{k+1}=f(v_k) vk+1=f(vk) 迭代求解, P ( r ∣ s , a ) , P ( s ′ ∣ s , a ) P(r|s,a), P(s'|s,a) P(rs,a),P(ss,a) 在前面这些章节中都认为是已知的(后面章节会讨论未知的情形)。因此 q ∗ ( s , a ) q^*(s,a) q(s,a) 也可以求解。由此我们完成了对最佳 Policy π ∗ \pi^* π 的求解。

Note: 最大 State Value v ∗ v^* v 具有唯一性,但是达到这样的 v ∗ v^* v 的 Policy π ∗ \pi^* π 可能并不是唯一的,例如:

上述两个不同的 Policy, 它们的 state value 完全相同,因为在出现 diff 的部分路径上,reward总和相同

一些证明过程

为了说明 f ( v ) = max ⁡ π ( r π + γ P π v ) f(v) = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v) f(v)=maxπ(rπ+γPπv) 是压缩映射,只需要证明:

对任意 v 1 , v 2 v_1, v_2 v1,v2,有:
∣ ∣ f ( v 1 ) − f ( v 2 ) ∣ ∣ ∞ ≤ γ ∣ ∣ v 1 − v 2 ∣ ∣ ∞ ||f(v_1)-f(v_2)||_{\infin} \leq \gamma ||v_1 -v_2 ||_{\infin} ∣∣f(v1)f(v2)γ∣∣v1v2
其中 ∣ ∣ ⋅ ∣ ∣ ∞ ||\cdot||_{\infin} ∣∣ 是 maximum 范数



一些影响 π ∗ \pi^* π 的因素

如何让 π ∗ \pi^* π 不 “绕弯路”

以下为一个简单 grid-word 的两种 Policy,显然前者优于后者,因为后者走了 “冤枉路”,本可以直接到 target state 的,却绕了弯路:

但与直观相违背的是,对于从白格子走到白格子的 action,其 reward 并不需要设为负数,而可以直接设为 0,用 discount rate γ \gamma γ 来对绕弯路的行为做惩罚:
return 1 = 1 + γ 1 + γ 2 1 + . . . = 1 1 − γ return 2 = 0 + γ 0 + γ 2 1 + γ 3 1 + . . . = γ 2 1 − γ \begin{aligned} \text{return}_1 &= 1 + \gamma 1 + \gamma^2 1 + ... = \frac{1}{1-\gamma}\\ \text{return}_2 &= 0 + \gamma 0 + \gamma^2 1 + \gamma^3 1 + ... = \frac{\gamma^2}{1-\gamma} \end{aligned} return1return2=1+γ1+γ21+...=1γ1=0+γ0+γ21+γ31+...=1γγ2
所以 return 2 \text{return}_2 return2 一定小于 return 1 \text{return}_1 return1,且 γ \gamma γ 越小,差距越大。一个直观的理解是:“绕弯路” 虽然不会直接产生惩罚,但是它延后了取得奖励(即到达 target state)的时间,而时间越晚,discount rate γ \gamma γ 对奖励的“打折”越大,因此好的 Policy 会倾向于更快得拿到奖励

γ \gamma γ 的影响

γ \gamma γ 的作用除了刚刚讨论的,在 第一节 中,我们也说过,由于:
discount return = R 0 + γ R 1 + γ 2 R 2 + . . . \begin{aligned} \text{discount return} &= R_0 + \gamma R_1 + \gamma^2 R_2 + ...\ \end{aligned} discount return=R0+γR1+γ2R2+... 
因此, γ \gamma γ更趋于0时,return更受早期的action影响,而当 γ \gamma γ更趋于1时,return更受后期的action的影响。可以看一些例子得到更直观的理解:

  • γ = 0.9 \gamma = 0.9 γ=0.9 时,Policy 会更受后期的action的影响,因此在接近 target state 时,为了尽快的到达,会不惜进入 forbidden state

  • γ = 0.5 \gamma = 0.5 γ=0.5 时,Policy 受后期的action的影响没那么大了,相反当下立即进入 forbidden state 得到的惩罚权重更大了,因此它可能会为了避免进入 forbidden state 而绕弯路

  • γ = 0 \gamma = 0 γ=0 时,Policy 会变得极端 “短时”,因为后面步骤得分的权重归零了,所以在任何 state 中,它都只倾向于走当前步所有可操作的 action 中 reward 最高的,并且不再考虑未来是否能走到 target value

reward 的影响

这里有一个也是比较直观的结论:

如果所有的 reward 都做一个线性变换: r ′ = a r + b , a > 0 r' = a r+ b, a>0 r=ar+ba>0
那么根据新的 reward 找到的 π ′ ∗ \pi'^* π 跟原来的 π ∗ \pi^* π 相同

Proof:一个直观的理解是,由于
π ∗ ( a ∣ s ) = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) \pi^*(a|s) = \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} π(as)={1,a=a(s)0,a=a(s)
那么只要 a ∗ ( s ) a^*(s) a(s) 不变, π ∗ \pi^* π 就不变。而:
a ∗ ( s ) = arg max ⁡ a ∈ A q ∗ ( s , a ) a^*(s) = \argmax_{a \in A} q^*(s,a) a(s)=aAargmaxq(s,a)
因此,只要这个变化不改变 reward 的 相对大小,就不会改变 a ∗ ( s ) a^*(s) a(s)。上述线性变化显然符合这个要求。


值迭代与策略迭代

值迭代

值迭代基本是上面过程的一个总结:

  1. 初始化一个 v 0 v_0 v0
  2. 迭代过程为: 已知 v k → 求解 q k ( s , a ) → π k + 1 ( a ∣ s ) = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) → v k + 1 = max ⁡ a q k ( s , a ) 已知v_k \rightarrow 求解 q_k(s,a) \rightarrow \pi_{k+1}(a|s) = \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} \rightarrow v_{k+1} = \max_a q_k(s,a) 已知vk求解qk(s,a)πk+1(as)={1,a=a(s)0,a=a(s)vk+1=amaxqk(s,a)
    其中 q k ( s , a ) = ∑ r P ( r ∣ s , a ) r + γ ∑ s ′ P ( s ′ ∣ s , a ) v k ( s ′ ) q_k(s,a) = \sum_{r} P(r|s,a)r + \gamma \sum_{s'} P(s'|s,a) v_k(s') qk(s,a)=rP(rs,a)r+γsP(ss,a)vk(s)
  3. ∣ ∣ v k + 1 − v k ∣ ∣ < ϵ ||v_{k+1} -v_k|| < \epsilon ∣∣vk+1vk∣∣<ϵ 时,停止迭代

下面看一个具体的例子加深理解,对于如下 grid-word:

  1. 初始化 v 0 v_0 v0 为全零向量: v 0 ( s 1 ) = v 0 ( s 2 ) = v 0 ( s 3 ) = v 0 ( s 4 ) = 0 v_0(s_1) =v_0(s_2) = v_0(s_3) =v_0(s_4) =0 v0(s1)=v0(s2)=v0(s3)=v0(s4)=0
  2. 根据 q ( s , a ) q(s,a) q(s,a) 的计算式:

    q 0 ( s , a ) q_0(s,a) q0(s,a) 为:

    因此 π 1 \pi_1 π1 为:
    π 1 ( a 5 ∣ s 1 ) = 1 , π 1 ( a 3 ∣ s 2 ) = 1 , π 1 ( a 2 ∣ s 3 ) = 1 , π 1 ( a 5 ∣ s 4 ) = 1 \pi_1(a_5|s_1) = 1, \pi_1(a_3|s_2) = 1, \pi_1(a_2|s_3) = 1, \pi_1(a_5|s_4) = 1 π1(a5s1)=1,π1(a3s2)=1,π1(a2s3)=1,π1(a5s4)=1

\qquad Note, 这里 π 1 ( a 5 ∣ s 1 ) = 1 \pi_1(a_5|s_1) = 1 π1(a5s1)=1 或者 π 1 ( a 3 ∣ s 1 ) = 1 \pi_1(a_3|s_1) = 1 π1(a3s1)=1 均可,随机取一个。 v 1 v_1 v1 的值也随即可得:
v 1 ( s 1 ) = 0 , v 1 ( s 2 ) = 1 , v 1 ( s 3 ) = 1 , v 1 ( s 4 ) = 1 v_1(s_1)=0, v_1(s_2)=1, v_1(s_3)=1, v_1(s_4)=1 v1(s1)=0,v1(s2)=1,v1(s3)=1,v1(s4)=1
π 1 \qquad\pi_1 π1对应的 grid-word 图为:
\qquad
\qquad 显然这还不是最优解, s 1 s_1 s1 的 policy 还有优化空间

  1. 根据上述 v 1 v_1 v1 可以求 q 1 ( s , a ) q_1(s,a) q1(s,a)

    因此 π 2 \pi_2 π2 为:
    π 1 ( a 3 ∣ s 1 ) = 1 , π 1 ( a 3 ∣ s 2 ) = 1 , π 1 ( a 2 ∣ s 3 ) = 1 , π 1 ( a 5 ∣ s 4 ) = 1 \pi_1(a_3|s_1) = 1, \pi_1(a_3|s_2) = 1, \pi_1(a_2|s_3) = 1, \pi_1(a_5|s_4) = 1 π1(a3s1)=1,π1(a3s2)=1,π1(a2s3)=1,π1(a5s4)=1
    v 2 v_2 v2 为:
    v 2 ( s 1 ) = γ , v 2 ( s 2 ) = 1 + γ , v 2 ( s 3 ) = 1 + γ , v 2 ( s 4 ) = 1 + γ v_2(s_1)=\gamma, v_2(s_2)=1+\gamma, v_2(s_3)=1+\gamma, v_2(s_4)=1+\gamma v2(s1)=γ,v2(s2)=1+γ,v2(s3)=1+γ,v2(s4)=1+γ
    此时图为:
    \qquad
    达到最优 Policy。

策略迭代

与值迭代不同,策略迭代是先从初始化策略 π 0 \pi_0 π0 开始的,迭代过程:

已知 π k → ( v π k ( 0 ) → v π k ( 1 ) → . . . → v π k ( ∞ ) = v π k ) → 求解 q π k ( s , a ) → π k + 1 = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) → . . . 已知 \pi_k \rightarrow (v_{\pi_k}^{(0)} \rightarrow v_{\pi_k}^{(1)} \rightarrow ... \rightarrow v_{\pi_k}^{(\infin)} = v_{\pi_k}) \rightarrow 求解 q_{\pi_k}(s,a) \rightarrow \pi_{k+1}= \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} \rightarrow ... 已知πk(vπk(0)vπk(1)...vπk()=vπk)求解qπk(s,a)πk+1={1,a=a(s)0,a=a(s)...
上面跟值迭代相比最主要的不同是 ( v π k ( 0 ) → v π k ( 1 ) → . . . → v π k ( ∞ ) = v π k ) (v_{\pi_k}^{(0)} \rightarrow v_{\pi_k}^{(1)} \rightarrow ... \rightarrow v_{\pi_k}^{(\infin)} = v_{\pi_k}) (vπk(0)vπk(1)...vπk()=vπk),将其展开:
v π k ( 1 ) = r π k + γ P π k v π k ( 0 ) v π k ( 2 ) = r π k + γ P π k v π k ( 1 ) … v π k ( ∞ ) = r π k + γ P π k v π k ( ∞ ) \begin{aligned} v_{\pi_k}^{(1)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(0)}\\ v_{\pi_k}^{(2)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(1)}\\ & \dots \\ v_{\pi_k}^{(\infin)} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}^{(\infin)}\\ \end{aligned} vπk(1)vπk(2)vπk()=rπk+γPπkvπk(0)=rπk+γPπkvπk(1)=rπk+γPπkvπk()

那么首先一个问题是,由于 v v v 不再是通过 v k + 1 = max ⁡ π ( r π + γ P π v k ) v_{k+1} = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_k) vk+1=maxπ(rπ+γPπvk) 来求解了,那么上述策略迭代的有效性要如何保证呢? 保证上述迭代策略的有效性可以分成两个部分:

  1. π k + 1 \pi_{k+1} πk+1 是否总是比 π k \pi_k πk 更好
  2. 上述迭代能否收敛

要证明 π k + 1 \pi_{k+1} πk+1 是否总是比 π k \pi_k πk 更好,只需要证明 v π k + 1 ≥ v π k v_{\pi_{k+1}} \geq v_{\pi_k} vπk+1vπk 总成立

Proof: 由于
v π k = r π k + γ P π k v π k v π k + 1 = r π k + 1 + γ P π k + 1 v π k + 1 \begin{aligned} v_{\pi_k} &= r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}\\ v_{\pi_{k+1}} &= r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}} \end{aligned} vπkvπk+1=rπk+γPπkvπk=rπk+1+γPπk+1vπk+1
由于 π k + 1 = arg max ⁡ π ( r π k + γ P π k v π k ) \pi_{k+1} = \argmax_{\pi} (r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k}) πk+1=argmaxπ(rπk+γPπkvπk) 其中 v π k v_{\pi_k} vπk 是固定值, (该式总成立,因为 π k + 1 = { 1 , a = a ∗ ( s ) 0 , a ≠ a ∗ ( s ) \pi_{k+1}= \begin{cases} 1, \quad a = a^*(s)\\ 0, \quad a \neq a^*(s) \end{cases} πk+1={1,a=a(s)0,a=a(s) 即为该式的贪婪解)
因此 r π k + 1 + γ P π k + 1 v π k ≥ r π k + γ P π k v π k = v π k r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k} \geq r_{\pi_k} + \gamma P_{\pi_k} v_{\pi_k} = v_{\pi_k} rπk+1+γPπk+1vπkrπk+γPπkvπk=vπk
⇒ v π k + 1 − v π k ≥ ( r π k + 1 + γ P π k + 1 v π k + 1 ) − ( r π k + 1 + γ P π k + 1 v π k ) ≥ γ P π k + 1 ( v π k + 1 − v π k ) \Rightarrow v_{\pi_{k+1}} - v_{\pi_k} \geq (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_k}) \geq \gamma P_{\pi_{k+1}} (v_{\pi_{k+1}} - v_{\pi_k}) vπk+1vπk(rπk+1+γPπk+1vπk+1)(rπk+1+γPπk+1vπk)γPπk+1(vπk+1vπk)

⇒ v π k + 1 − v π k ≥ γ P π k + 1 ( v π k + 1 − v π k ) ≥ γ 2 P π k + 1 2 ( v π k + 1 − v π k ) ≥ . . . ≥ lim ⁡ n → ∞ γ n P π k + 1 n ( v π k + 1 − v π k ) \Rightarrow v_{\pi_{k+1}} - v_{\pi_k} \geq \gamma P_{\pi_{k+1}} (v_{\pi_{k+1}} - v_{\pi_k}) \geq \gamma^2 P^2_{\pi_{k+1}} (v_{\pi_{k+1}} - v_{\pi_k}) \geq ... \geq \lim_{n \rightarrow \infin} \gamma^n P^n_{\pi_{k+1}} (v_{\pi_{k+1}} - v_{\pi_k}) vπk+1vπkγPπk+1(vπk+1vπk)γ2Pπk+12(vπk+1vπk)...nlimγnPπk+1n(vπk+1vπk)
其中 0 < γ < 1 0 < \gamma <1 0<γ<1,因此 lim ⁡ n → ∞ γ n = 0 \lim_{n \rightarrow \infin} \gamma^n =0 limnγn=0;而 P π k + 1 P_{\pi_{k+1}} Pπk+1 是随机矩阵,所以 P π k + 1 n P^n_{\pi_{k+1}} Pπk+1n 不会发散。所以 v π k + 1 − v π k ≥ 0 v_{\pi_{k+1}} - v_{\pi_k} \geq 0 vπk+1vπk0


收敛性的证明要依赖我们上面由 压缩映射定理 得到的结论:
v k + 1 = f ( v k ) = max ⁡ π ( r π + γ P π v k ) → v ∗ v_{k+1} = f(v_k) = \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_k) \rightarrow v^* vk+1=f(vk)=πmax(rπ+γPπvk)v
由于 v ∗ = max ⁡ ( ( I − γ P π ) − 1 r π ) , ∀ s , ∀ π ∈ Π v^* = \max ((I-\gamma P_{\pi})^{-1} r_{\pi} ), \forall s, \forall \pi \in \Pi v=max((IγPπ)1rπ)s,πΠ,因此 v π k ≤ v ∗ , ∀ k v_{\pi_k} \leq v^*, \forall k vπkv,k 一定成立。那么我们只需要证明存在上述由 v k + 1 = f ( v k ) v_{k+1} = f(v_k) vk+1=f(vk) 推导的 { v k } \{v_k\} {vk},使得满足: v k ≤ v π k , ∀ k v_{k} \leq v_{\pi_k} , \forall k vkvπk,k
由于 v k ≤ v π k ≤ v ∗ ,而 lim ⁡ k → ∞ v k = v ∗ v_{k} \leq v_{\pi_k} \leq v^*,而 \lim_{k \rightarrow \infin} v_{k} = v^* vkvπkv,而klimvk=v
因此可以证明 lim ⁡ k → ∞ v π k = v ∗ \lim_{k \rightarrow \infin} v_{\pi_k} = v^* klimvπk=v


Proof: 由于 v 0 v_0 v0 是任意初始化的,所以对任意 π 0 \pi_0 π0 总可以找到 v 0 v_0 v0 使得 v π 0 ≥ v 0 v_{\pi_0} \geq v_0 vπ0v0
由归纳法,只需要证明当 v π k ≥ v k v_{\pi_k} \geq v_k vπkvk 时, v π k + 1 ≥ v k + 1 v_{\pi_{k+1}} \geq v_{k+1} vπk+1vk+1 成立。

v π k + 1 − v k + 1 = ( r π k + 1 + γ P π k + 1 v π k + 1 ) − max ⁡ π ( r π + γ P π v k ) ≥ ( r π k + 1 + γ P π k + 1 v π k + 1 ) − max ⁡ π ( r π + γ P π v k ) ( 由上述结论 v π k + 1 ≥ v k ) = ( r π k + 1 + γ P π k + 1 v π k + 1 ) − ( r π k + γ P π k v k ) ( 由于  π k = arg ⁡ max ⁡ π ( r π + γ P π v k ) ) ≥ ( r π k + γ P π k v k ) − ( r π k + γ P π k v k ) ( 由于  π k + 1 = arg ⁡ max ⁡ π ( r π + γ P π v π k ) ) = γ P π k ( v π k − v k ) ≥ 0 \begin{aligned} v_{\pi_{k+1}} - v_{k+1} &= (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_{k})\\ &\geq (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - \max_{\pi}(r_{\pi} + \gamma P_{\pi} v_{k}) \quad(\text{由上述结论} v_{\pi_{k+1}} \geq v_{k} )\\ &= (r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_{\pi_{k+1}}) - (r_{\pi_{k}} + \gamma P_{\pi_{k}} v_{k}) \quad (\text{由于 } \pi_{k} = \arg\max_{\pi} (r_{\pi} + \gamma P_{\pi} v_{k}))\\ &\geq (r_{\pi_{k}} + \gamma P_{\pi_{k}} v_{k}) - (r_{\pi_{k}} + \gamma P_{\pi_{k}} v_{k})\quad (\text{由于 } \pi_{k+1} = \arg\max_{\pi} (r_{\pi} + \gamma P_{\pi} v_{\pi_{k}}))\\ &= \gamma P_{\pi_{k}} (v_{\pi_{k}} - v_{k}) \geq 0\\ \end{aligned} vπk+1vk+1=(rπk+1+γPπk+1vπk+1)πmax(rπ+γPπvk)(rπk+1+γPπk+1vπk+1)πmax(rπ+γPπvk)(由上述结论vπk+1vk)=(rπk+1+γPπk+1vπk+1)(rπk+γPπkvk)(由于 πk=argπmax(rπ+γPπvk))(rπk+γPπkvk)(rπk+γPπkvk)(由于 πk+1=argπmax(rπ+γPπvπk))=γPπk(vπkvk)0
证毕。


值迭代和策略迭代的具体差别

以下是值迭代和策略迭代的对比图:

可以看到,当 v 0 v_0 v0 选取得当,两种策略的 π 1 \pi_1 π1 是相同的,但是从 π 2 \pi_2 π2 开始就不一定了,这是因为,计算 v π 1 v_{\pi_1} vπ1 过程实际是:

值迭代的 v 1 v_1 v1 其实就是策略迭代中的 v π 1 ( 1 ) v_{\pi_1}^{(1)} vπ1(1),所以就大的 iteration 而言,一般策略迭代会在 k k k 更小的时候收敛:

当然这不意味着策略迭代的整体计算量更小,因为它每个大的 iteration 里面,会比值迭代计算更多轮的 Value State

这里当介于两者之间时,称为 截断策略迭代


一个小例子

这个小例子有一点比较有意思:可以看出 Policy 的优化往往是现从靠近 target value 的地方开始的,这个其实也很好理解,根据贝尔曼公式: ⇒ v π ( s ) = E [ G t ∣ S t = s ] = E [ R t + 1 + γ G t + 1 ∣ S t = s ] = E [ R t + 1 ∣ S t = s ] + γ E [ G t + 1 ∣ S t = s ] \begin{aligned} \Rightarrow v_{\pi}(s) &= E[G_t|S_t=s]\\ &= E[R_{t+1} + \gamma G_{t+1}|S_t=s] \\ &= E[R_{t+1}|S_t=s] + \gamma E[G_{t+1}|S_t=s] \end{aligned} vπ(s)=E[GtSt=s]=E[Rt+1+γGt+1St=s]=E[Rt+1St=s]+γE[Gt+1St=s]
其中 E [ G t + 1 ∣ S t = s ] E[G_{t+1}|S_t=s] E[Gt+1St=s] 就是后面路径的 state value,因此要优化当前位置的 state value,一定是先优化后面的 state 的 state value,再逐渐优化远离 target value 的 state


Reference:
1.强化学习的数学原理

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/367818.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

UiPath+Appium实现app自动化测试

一、环境准备工作 1.1 完成appium环境的搭建 参考&#xff1a;pythonappiumpytestallure模拟器(MuMu)自动化测试环境搭建_appium mumu模拟器-CSDN博客 1.2 完成uipath的安装 登录官网&#xff0c;完成注册与软件下载安装。 UiPath业务自动化平台&#xff1a;先进的RPA及自动…

Visual Studio 中的键盘快捷方式

1. Visual Studio 中的键盘快捷方式 1.1. 可打印快捷方式备忘单 1.2. Visual Studio 的常用键盘快捷方式 本部分中的所有快捷方式都将全局应用&#xff08;除非另有指定&#xff09;。 “全局”上下文表示该快捷方式适用于 Visual Studio 中的任何工具窗口。 生成&#xff1…

第十四章 集合(List)

一、集合框架体系 集合&#xff1a; &#xff08;1&#xff09;可以动态保存任意多个对象 &#xff08;2&#xff09;提供了一系列方便的操作对象的方法 二、Collection 1. Collection 接口常用方法 &#xff08;1&#xff09;add&#xff1a;添加单个元素 &#xff08;2…

Cypress测试:7个快速解决问题的调试技巧!

以下为作者观点&#xff1a; 快速编写代码是一项宝贵的技能&#xff0c;但能够有效调试和解决错误和bug&#xff0c;更是一个软件开发人员具有熟练技能的标志。调试是开发过程中的一个关键环节&#xff0c;可以确保软件按预期运行并满足用户需求。 Cypress 调试简介 Cypress …

【Linux】—Xshell、Xftp安装

文章目录 前言一、下载Xshell、Xftp二、安装Xshell三、使用XShell连接Linux服务器四、修改windows的主机映射文件&#xff08;hosts文件&#xff09;五、远程连接hadoop102/hadoop103/hadoop104服务器六、安装Xftp 前言 XShell远程管理工具&#xff0c;可以在Windows界面下来访…

uniapp + vue3 + Script Setup 写法变动 (持续更新)

一、uniapp 应用生命周期&#xff1a; https://uniapp.dcloud.net.cn/tutorial/vue3-composition-api.html 注意&#xff1a; 应用生命周期仅可在App.vue中监听&#xff0c;在其它页面监听无效。 二 、uniapp页面生命周期&#xff1a; https://uniapp.dcloud.net.cn/tutori…

3.js - 色调映射(renderer.toneMapping)

// ts-nocheck// 引入three.js import * as THREE from three// 导入轨道控制器 import { OrbitControls } from three/examples/jsm/controls/OrbitControls// 导入lil.gui import { GUI } from three/examples/jsm/libs/lil-gui.module.min.js// 导入tween import * as TWEEN…

昇思25天学习打卡营第11天|基于MindSpore通过GPT实现情感分类

学AI还能赢奖品&#xff1f;每天30分钟&#xff0c;25天打通AI任督二脉 (qq.com) 基于MindSpore通过GPT实现情感分类 %%capture captured_output # 实验环境已经预装了mindspore2.2.14&#xff0c;如需更换mindspore版本&#xff0c;可更改下面mindspore的版本号 !pip uninsta…

【目标检测】DINO

一、引言 论文&#xff1a; DINO: DETR with Improved DeNoising Anchor Boxes for End-to-End Object Detection 作者&#xff1a; IDEA 代码&#xff1a; DINO 注意&#xff1a; 该算法是在Deformable DETR、DAB-DETR、DN-DETR基础上的改进&#xff0c;在学习该算法前&#…

决策树算法的原理与案例实现

一、绪论 1.1 决策树算法的背景介绍 1.2 研究决策树算法的意义 二、决策树算法原理 2.1 决策树的基本概念 2.2 决策树构建的基本思路 2.2 决策树的构建过程 2.3 决策树的剪枝策略 三、决策树算法的优缺点 3.1 决策树算法的优势 3.2 决策树算法的局限性 3.3 决策树算…

Vue报错:Component name “xxx” should always be multi-word vue/multi-word-component

问题&#xff1a;搭建脚手架时报错&#xff0c;具体错误如下&#xff1a; ERROR in [eslint] E:\personalProject\VueProjects\vueproject2\src\components\Student.vue10:14 error Component name "Student" should always be multi-word vue/multi-word-compon…

【分布式数据仓库Hive】常见问题及解决办法

目录 一、启动hive时发现log4j版本和hadoop的版本有冲突 解决办法&#xff1a;删除hive下高版本的slf4j 二、启动hive报错 Exception in thread "main" java.lang.NoSuchMethodError:com.google.common.base.Preconditions.checkArgument(ZLjava/lang/Object;)V …

Elasticsearch (1):ES基本概念和原理简单介绍

Elasticsearch&#xff08;简称 ES&#xff09;是一款基于 Apache Lucene 的分布式搜索和分析引擎。随着业务的发展&#xff0c;系统中的数据量不断增长&#xff0c;传统的关系型数据库在处理大量模糊查询时效率低下。因此&#xff0c;ES 作为一种高效、灵活和可扩展的全文检索…

分别使用netty和apache.plc4x测试读取modbus协议的设备信号

记录一下常见的工业协议数据读取方法 目录 前言Modbus协议说明Netty 读取测试使用plc4x 读取测试结束语 前言 Modbus 是一种通讯协议&#xff0c;用于在工业控制系统中进行数据通信和控制。Modbus 协议主要分为两种常用的变体&#xff1a;Modbus RTU 和 Modbus TCP/IP Modbus …

嵌入式Linux之Uboot简介和移植

uboot简介 uboot 的全称是 Universal Boot Loader&#xff0c;uboot 是一个遵循 GPL 协议的开源软件&#xff0c;uboot是一个裸机代码&#xff0c;可以看作是一个裸机综合例程。现在的 uboot 已经支持液晶屏、网络、USB 等高级功能。 也就是说&#xff0c;可以在没有系统的情况…

苹果手机收不到短信怎么恢复?90%的人都在这么做

在使用苹果手机的过程中&#xff0c;有时候会遇到无法接收短信的问题。这不仅影响正常的沟通&#xff0c;还可能错过重要的通知和验证码。那么&#xff0c;手机收不到短信怎么恢复呢&#xff1f;别担心&#xff0c;90%的人都在使用这些简单而有效的方法来解决这一问题。 本文将…

Halcon支持向量机

一 支持向量机 1 支持向量机介绍&#xff1a; 支持向量机(Support Vector Machine&#xff0c;SVM)是Corinna Cortes和Vapnik于1995年首先提出的&#xff0c;它在解决小样本、非线性及高维模式识别表现出许多特有的优势。 2 支持向量机原理: 在n维空间中找到一个分类超平面…

14 卡尔曼滤波及代码实现

文章目录 14 卡尔曼滤波及代码实现14.0 基本概念14.1 公式推导14.2 代码实现 14 卡尔曼滤波及代码实现 14.0 基本概念 卡尔曼滤波是一种利用线性系统状态方程&#xff0c;通过系统输入输出观测数据&#xff0c;对系统状态进行最优估计的算法。由于观测数据包括系统中的噪声和…

React Native V0.74 — 稳定版已发布

嗨,React Native开发者们, React Native 世界中令人兴奋的消息是,V0.74刚刚在几天前发布,有超过 1600 次提交。亮点如下: Yoga 3.0New Architecture: Bridgeless by DefaultNew Architecture: Batched onLayout UpdatesYarn 3 for New Projects让我们深入了解每一个新亮点…

移动智能终端数据安全管理方案

随着信息技术的飞速发展&#xff0c;移动设备已成为企业日常运营不可或缺的工具。特别是随着智能手机和平板电脑等移动设备的普及&#xff0c;这些设备存储了大量的个人和敏感数据&#xff0c;如银行信息、电子邮件等。员工通过智能手机和平板电脑访问企业资源&#xff0c;提高…