【RL】Bellman Equation (贝尔曼等式)

Lecture2: Bellman Equation

State value

考虑grid-world的单步过程:
S t → A t R t + 1 , S t + 1 S_t \xrightarrow[]{A_t} R_{t + 1}, S_{t + 1} StAt Rt+1,St+1

  • t t t, t + 1 t + 1 t+1:时间戳
  • S t S_t St:时间 t t t时所处的state
  • A t A_t At:在state S t S_t St时采取的action
  • R t + 1 R_{t + 1} Rt+1:在采取 action A t A_t At 之后获得的reward
  • S t + 1 S_{t + 1} St+1:在采取 action A t A_t At 之后,state S t S_t St转移后的state

通过概率分布对以上变量的动作进行描述:

  • S t → A t S_t \rightarrow A_t StAt π ( A t = a ∣ S t = s ) \pi (A_t = a | S_t = s) π(At=aSt=s)
  • S t , A t → R t + 1 S_t, A_t \rightarrow R_{t + 1} St,AtRt+1 p ( R t + 1 = r ∣ S t = s , A t = a ) p(R_{t + 1} =r | S_t = s, A_t = a) p(Rt+1=rSt=s,At=a)
  • S t , A t → S t + 1 S_t, A_t \rightarrow S_{t + 1} St,AtSt+1 p ( S t + 1 = s ′ ∣ S t = s , A t = a ) p(S_{t + 1} = s' | S_t = s, A_t = a) p(St+1=sSt=s,At=a)

考虑grid-world的多步(multi-step)trajectory:
S t → A t R t + 1 , S t + 1 → A t + 1 R t + 2 , S t + 2 → A t + 2 R t + 3 . . . S_t \xrightarrow[]{A_t} R_{t + 1}, S_{t + 1} \xrightarrow[]{A_{t + 1}} R_{t + 2}, S_{t + 2} \xrightarrow[]{A_{t + 2}} R_{t + 3}... StAt Rt+1,St+1At+1 Rt+2,St+2At+2 Rt+3...
其discounted return为:
G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . G_t = R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + ... Gt=Rt+1+γRt+2+γ2Rt+3+...

  • γ ∈ [ 0 , 1 ) \gamma \in [0, 1) γ[0,1)是折扣率(discount rate)
  • R t + 1 , R t + 2 , . . . R_{t + 1}, R_{t + 2}, ... Rt+1,Rt+2,...是随机变量时, G t G_t Gt也是随机变量

G t G_t Gt的期望(expectation; expected value; mean)被定义为state-value function或state value。
v π ( s ) = E [ G t ∣ S t = s ] v_{\pi}(s) = \mathbb{E}[G_t | S_t = s] vπ(s)=E[GtSt=s]

  • v π ( s ) v_{\pi}(s) vπ(s)是state s s s的函数,是state从 s s s 起始的条件期望。
  • v π ( s ) v_{\pi}(s) vπ(s)基于policy π \pi π,对于不同的policy,state value可能会不同
  • 其代表了一个state的“价值”。 如果state value越大,代表policy就越好,因为可以获得更大的累积奖励(cumulative rewards)。

注意区分state value和return: state value是从某个state开始可以获得的所有可能return的平均值。如果每一个 π ( a ∣ s ) , p ( r ∣ s , a ) , p ( s ′ ∣ s , a ) \pi(a | s), p(r | s, a), p(s' | s, a) π(as),p(rs,a),p(ss,a)是确定的,那么state value和return是相等的。

例:

在这里插入图片描述

计算三个样例的state value:
v π 1 ( s 1 ) = 0 + γ 1 + γ 2 1 + ⋯ = γ ( 1 + γ + γ 2 + ⋯   ) = γ 1 − γ v_{\pi_1}(s_1) = 0 + \gamma 1 + \gamma^21 + \cdots = \gamma(1 + \gamma + \gamma^2 + \cdots) = \frac{\gamma}{1 - \gamma} vπ1(s1)=0+γ1+γ21+=γ(1+γ+γ2+)=1γγ

v π 2 ( s 1 ) = − 1 + γ 1 + γ 2 1 + ⋯ = − 1 + γ ( 1 + γ + γ 2 + ⋯   ) = − 1 + γ 1 − γ v_{\pi_2}(s_1) = -1 + \gamma1 + \gamma^21 + \cdots = -1 + \gamma(1 + \gamma + \gamma^2 + \cdots) = -1 + \frac{\gamma}{1 - \gamma} vπ2(s1)=1+γ1+γ21+=1+γ(1+γ+γ2+)=1+1γγ

v π 3 ( s 1 ) = 0.5 ( − 1 + γ 1 − γ ) + 0.5 ( γ 1 − γ ) = − 0.5 + γ 1 − γ v_{\pi_3}(s_1) = 0.5(-1 + \frac{\gamma}{1 - \gamma}) + 0.5(\frac{\gamma}{1 - \gamma}) = -0.5 + \frac{\gamma}{1 - \gamma} vπ3(s1)=0.5(1+1γγ)+0.5(1γγ)=0.5+1γγ

Bellman equation: Derivation

贝尔曼方程描述了所有state值之间的关系。

考虑一个随机的trajectory:
S t → A t R t + 1 , S t + 1 → A t + 1 R t + 2 , S t + 2 → A t + 2 R t + 3 , … S_t \xrightarrow[]{A_t} R_{t + 1}, S_{t + 1} \xrightarrow[]{A_{t+1}} R_{t + 2}, S_{t + 2} \xrightarrow[]{A_{t+2}} R_{t + 3}, \dots StAt Rt+1,St+1At+1 Rt+2,St+2At+2 Rt+3,
其return G t G_t Gt可以被计算为:
G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + … = R t + 1 + γ ( R t + 2 + γ R t + 3 + …   ) = R t + 1 + γ G t + 1 \begin{align*} G_t &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + \dots\\ &= R_{t + 1} + \gamma(R_{t + 2} + \gamma R_{t + 3} + \dots)\\ &= R_{t + 1} + \gamma G_{t+1} \end{align*} Gt=Rt+1+γRt+2+γ2Rt+3+=Rt+1+γ(Rt+2+γRt+3+)=Rt+1+γGt+1
其state 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{align*} v_{\pi}(s) &= \mathbb{E}[G_t | S_t = s] \\ & = \mathbb{E}[R_{t + 1} + \gamma G_{t + 1} | S_t = s]\\ &= \mathbb{E}[R_{t + 1} | S_t = s] + \gamma \mathbb{E}[G_{t + 1} | S_t = s] \end{align*} vπ(s)=E[GtSt=s]=E[Rt+1+γGt+1St=s]=E[Rt+1St=s]+γE[Gt+1St=s]
对于第一项:
E [ R t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) E [ R t + 1 ∣ S t = s , A t = a ] = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r \begin{align*} \mathbb{E}[R_{t + 1} | S_t = s] &= \sum_a \pi(a | s) \mathbb{E}[R_{t + 1} | S_t = s, A_t = a] \\ & = \sum_a \pi(a | s)\sum_rp(r | s, a)r \end{align*} E[Rt+1St=s]=aπ(as)E[Rt+1St=s,At=a]=aπ(as)rp(rs,a)r
这是瞬时reward的期望。

对于第二项:
E [ G t + 1 ∣ S t = s ] = ∑ s ′ E [ G t + 1 ∣ S t = s , S t + 1 = s ′ ] p ( s ′ ∣ s ) = ∑ s ′ E [ G t + 1 ∣ S t + 1 = s ′ ] p ( s ′ ∣ s ) = ∑ s ′ v π ( s ′ ) p ( s ′ ∣ s ) = ∑ s ′ v π ( s ′ ) ∑ a p ( s ′ ∣ s , a ) π ( a ∣ s ) \begin{align*} \mathbb{E}[G_{t + 1} | S_t = s] &= \sum_{s'} \mathbb{E}[G_{t + 1} | S_t = s, S_{t + 1} = s']p(s' | s)\\ &= \sum_{s'}\mathbb{E}[G_{t + 1} | S_{t + 1} = s']p(s' | s)\\ &= \sum_{s'} v_{\pi}(s')p(s' |s )\\ &= \sum_{s'} v_{\pi}(s') \sum_a p(s' | s, a)\pi(a | s) \end{align*} E[Gt+1St=s]=sE[Gt+1St=s,St+1=s]p(ss)=sE[Gt+1St+1=s]p(ss)=svπ(s)p(ss)=svπ(s)ap(ss,a)π(as)
这是未来reward的期望

因此,可以得到:
v π ( s ) = E [ R t + 1 ∣ S t = s ] + γ E [ G t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ v π ( s ′ ) ∑ a p ( s ′ ∣ s , a ) π ( a ∣ s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] ,        ∀ s ∈ S \begin{align*} v_{\pi}(s) &= \mathbb{E}[R_{t + 1} | S_t = s] + \gamma \mathbb{E}[G_{t + 1} | S_t = s]\\ &= \sum_a \pi(a | s)\sum_rp(r | s, a)r + \gamma \sum_{s'} v_{\pi}(s') \sum_a p(s' | s, a)\pi(a | s) \\ &= \sum_a \pi(a | s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s'}p(s' | s, a) v_{\pi}(s') \right], \;\;\; \forall s \in S \end{align*} vπ(s)=E[Rt+1St=s]+γE[Gt+1St=s]=aπ(as)rp(rs,a)r+γsvπ(s)ap(ss,a)π(as)=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)],sS

  • v π ( s ) v_{\pi}(s) vπ(s) π ( s ′ ) \pi(s') π(s)是需要被计算的state value,可以采用bootstrapping。
  • π ( a ∣ s ) \pi(a | s) π(as)是给定的policy,可以通过策略评估(policy evaluation)进行求解。
  • p ( r ∣ s , a ) p(r | s, a) p(rs,a) p ( s ′ ∣ s , a ) p(s' | s, a) p(ss,a)代表动态模型,分为known和unknown。
  • 上式叫做贝尔曼等式(Bellman equation),其描述了不同state之间state-value function的关系。
  • Bellman equation包含两个部分,瞬时奖励(immediate reward)和未来奖励(future reward)。

例:

对于action:

在这里插入图片描述

若policy为:

在这里插入图片描述

首先写Bellman equation:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_{\pi}(s) = \sum_a \pi(a | s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s'}p(s' | s, a) v_{\pi}(s') \right] vπ(s)=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)]
计算上式各项:

  • π ( a = a 3 ∣ s 1 ) = 1 \pi(a = a_3 | s_1) = 1 π(a=a3s1)=1, π ( a ≠ a 3 ∣ s 1 ) = 0 \pi(a \ne a_3 | s_1) = 0 π(a=a3s1)=0
  • p ( s ′ = s 3 ∣ s 1 , a 3 ) = 1 p(s' = s_3 | s_1, a_3) = 1 p(s=s3s1,a3)=1, p ( s ′ ≠ s 3 ∣ s 1 , a 3 ) = 0 p(s' \ne s_3 | s_1, a_3) = 0 p(s=s3s1,a3)=0
  • p ( r = 0 ∣ s 1 , a 3 = 1 ) p(r = 0 | s_1, a_3 = 1) p(r=0∣s1,a3=1), p ( r ≠ 0 ∣ s 1 , a 3 ) = 0 p(r \ne 0 | s_1, a_3) = 0 p(r=0∣s1,a3)=0

替换进Bellman equation得:
v π ( s 1 ) = 0 + γ v π ( s 3 ) v_{\pi}(s_1) = 0 + \gamma v_{\pi}(s_3) vπ(s1)=0+γvπ(s3)
同样的,可以计算:
v π ( s 1 ) = 0 + γ v π ( s 3 ) v π ( s 2 ) = 1 + γ v π ( s 4 ) v π ( s 3 ) = 1 + γ v π ( s 4 ) v π ( s 4 ) = 1 + γ v π ( s 4 ) v_{\pi}(s_1) = 0 + \gamma v_{\pi}(s_3)\\ v_{\pi}(s_2) = 1 + \gamma v_{\pi}(s_4)\\ v_{\pi}(s_3) = 1 + \gamma v_{\pi}(s_4)\\ v_{\pi}(s_4) = 1 + \gamma v_{\pi}(s_4)\\ vπ(s1)=0+γvπ(s3)vπ(s2)=1+γvπ(s4)vπ(s3)=1+γvπ(s4)vπ(s4)=1+γvπ(s4)
对于上式,可以从后往前计算:
v π ( s 4 ) = 1 1 − γ v π ( s 3 ) = 1 1 − γ v π ( s 2 ) = 1 1 − γ v π ( s 1 ) = γ 1 − γ v_{\pi}(s_4) = \frac{1}{1 - \gamma}\\ v_{\pi}(s_3) = \frac{1}{1 - \gamma}\\ v_{\pi}(s_2) = \frac{1}{1 - \gamma}\\ v_{\pi}(s_1) = \frac{\gamma}{1 - \gamma}\\ vπ(s4)=1γ1vπ(s3)=1γ1vπ(s2)=1γ1vπ(s1)=1γγ
若policy为:

在这里插入图片描述

则:
v π ( s 1 ) = 0.5 [ 0 + γ v π ( s 3 ) ] + 0.5 [ − 1 + γ v π ( s 2 ) ] v π ( s 2 ) = 1 + γ v π ( s 4 ) v π ( s 3 ) = 1 + γ v π ( s 4 ) v π ( s 4 ) = 1 + γ v π ( s 4 ) v_{\pi}(s_1) = 0.5[0 + \gamma v_{\pi}(s_3)] + 0.5[-1 + \gamma v_{\pi}(s_2)] \\ v_{\pi}(s_2) = 1 + \gamma v_{\pi}(s_4)\\ v_{\pi}(s_3) = 1 + \gamma v_{\pi}(s_4)\\ v_{\pi}(s_4) = 1 + \gamma v_{\pi}(s_4)\\ vπ(s1)=0.5[0+γvπ(s3)]+0.5[1+γvπ(s2)]vπ(s2)=1+γvπ(s4)vπ(s3)=1+γvπ(s4)vπ(s4)=1+γvπ(s4)
从后往前算:
v π ( s 4 ) = 1 1 − γ v π ( s 3 ) = 1 1 − γ v π ( s 2 ) = 1 1 − γ v π ( s 1 ) = 0.5 [ 0 + γ v π ( s 3 ) ] + 0.5 [ − 1 + γ v π ( s 2 ) ] = − 0.5 + γ 1 − γ v_{\pi}(s_4) = \frac{1}{1 - \gamma} \\ v_{\pi}(s_3) = \frac{1}{1 - \gamma} \\ v_{\pi}(s_2) = \frac{1}{1 - \gamma} \\ \begin{align*} v_{\pi}(s_1) &= 0.5[0 + \gamma v_{\pi}(s_3)] + 0.5[-1 + \gamma v_{\pi}(s_2)] \\ & = -0.5 + \frac{\gamma}{1 - \gamma} \end{align*} vπ(s4)=1γ1vπ(s3)=1γ1vπ(s2)=1γ1vπ(s1)=0.5[0+γvπ(s3)]+0.5[1+γvπ(s2)]=0.5+1γγ

Bellman equation: Matrix-vector form

对于Bellman equation:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_{\pi}(s) = \sum_a \pi(a | s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s'}p(s' | s, a) v_{\pi}(s') \right] vπ(s)=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)]
通常是未知的 v π ( s ) v_{\pi}(s) vπ(s)伴随着未知的 v π ( s ′ ) v_{\pi}(s') vπ(s),这对于每一个 s ∈ S s \in \mathcal{S} sS都成立。因此,意味着共有 ∣ S ∣ |\mathcal{S}| S个这样的等式。如果将所有的等式,放到一起进行计算,这就构成了Bellman equation的矩阵形式。

将上式展开,写为:
v π ( s ) = r π ( s ) + γ ∑ s ′ p π ( s ′ ∣ s ) v π ( s ′ )            ( 1 ) v_{\pi}(s) = r_{\pi}(s) + \gamma \sum_{s'} p_{\pi}(s' | s)v_{\pi}(s') \;\;\;\;\; (1) vπ(s)=rπ(s)+γspπ(ss)vπ(s)(1)
其中:
r π ( s ) : = ∑ a π ( a ∣ s ) ∑ r p ( r ∣ s , a ) r p π ( s ′ ∣ s ) : = ∑ a π ( a ∣ s ) p ( s ′ ∣ s , a ) r_{\pi}(s) := \sum_a \pi(a | s) \sum_r p(r | s, a)r \\ p_{\pi}(s' | s) := \sum_a \pi(a | s) p(s' | s, a) rπ(s):=aπ(as)rp(rs,a)rpπ(ss):=aπ(as)p(ss,a)
为state s s s添加索引 s i , i = 1 , . . . , n s_i, i = 1, ..., n si,i=1,...,n

对于 s i s_i si,其Bellman equation为:
v π ( s i ) = r π ( s i ) + γ ∑ s j p π ( s j ∣ s i ) v π ( s j ) v_{\pi}(s_i) = r_{\pi}(s_i) + \gamma \sum_{s_j} p_{\pi}(s_j | s_i)v_{\pi}(s_j) vπ(si)=rπ(si)+γsjpπ(sjsi)vπ(sj)
将所有的state写为矩阵形式:
v π = r π + γ P π v π \mathbf{v}_{\pi} = \mathbf{r}_{\pi} + \gamma \mathbf{P}_{\pi} \mathbf{v}_{\pi} vπ=rπ+γPπvπ
其中:

  • v π = [ v π ( s 1 ) , v π ( s 2 ) , . . . , v π ( s n ) ] T ∈ R n \mathbf{v}_{\pi} = [v_{\pi}(s_1), v_{\pi}(s_2), ..., v_{\pi}(s_n)]^T \in \mathbb{R}^n vπ=[vπ(s1),vπ(s2),...,vπ(sn)]TRn
  • r π = [ r π ( s 1 ) , r π ( s 2 ) , . . . , r π ( s n ) ] T ∈ R n \mathbf{r}_{\pi} = [r_{\pi}(s_1), r_{\pi}(s_2), ..., r_{\pi}(s_n)]^T \in \mathbb{R}^n rπ=[rπ(s1),rπ(s2),...,rπ(sn)]TRn
  • P π ∈ R n × n \mathbf{P}_{\pi} \in \mathbb{R}^{n \times n} PπRn×n,其中, [ P π ] = p π ( s j ∣ s i ) [P_{\pi}] = p_{\pi}(s_j | s_i) [Pπ]=pπ(sjsi)是state转移矩阵。

假设有四个state,则上式矩阵形式可以写为:
[ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] = [ r π ( s 1 ) r π ( s 2 ) r π ( s 3 ) r π ( s 4 ) ] + γ [ p π ( s 1 ∣ s 1 ) p π ( s 2 ∣ s 1 ) p π ( s 3 ∣ s 1 ) p π ( s 4 ∣ s 1 ) p π ( s 1 ∣ s 2 ) p π ( s 2 ∣ s 2 ) p π ( s 3 ∣ s 2 ) p π ( s 4 ∣ s 2 ) p π ( s 1 ∣ s 3 ) p π ( s 2 ∣ s 3 ) p π ( s 3 ∣ s 3 ) p π ( s 4 ∣ s 3 ) p π ( s 1 ∣ s 4 ) p π ( s 2 ∣ s 4 ) p π ( s 3 ∣ s 4 ) p π ( s 4 ∣ s 4 ) ] [ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] \begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} = \begin{bmatrix} r_{\pi}(s_1) \\ r_{\pi}(s_2)\\ r_{\pi}(s_3)\\ r_{\pi}(s_4) \end{bmatrix} + \gamma \begin{bmatrix} p_{\pi}(s_1 | s_1) &p_{\pi}(s_2 | s_1) &p_{\pi}(s_3 | s_1) &p_{\pi}(s_4 | s_1)\\ p_{\pi}(s_1 | s_2) &p_{\pi}(s_2 | s_2) &p_{\pi}(s_3 | s_2) &p_{\pi}(s_4 | s_2)\\ p_{\pi}(s_1 | s_3) &p_{\pi}(s_2 | s_3) &p_{\pi}(s_3 | s_3) &p_{\pi}(s_4 | s_3)\\ p_{\pi}(s_1 | s_4) &p_{\pi}(s_2 | s_4) &p_{\pi}(s_3 | s_4) &p_{\pi}(s_4 | s_4) \end{bmatrix} \begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} vπ(s1)vπ(s2)vπ(s3)vπ(s4) = rπ(s1)rπ(s2)rπ(s3)rπ(s4) +γ pπ(s1s1)pπ(s1s2)pπ(s1s3)pπ(s1s4)pπ(s2s1)pπ(s2s2)pπ(s2s3)pπ(s2s4)pπ(s3s1)pπ(s3s2)pπ(s3s3)pπ(s3s4)pπ(s4s1)pπ(s4s2)pπ(s4s3)pπ(s4s4) vπ(s1)vπ(s2)vπ(s3)vπ(s4)
例,对policy1:

在这里插入图片描述

对其求解,得:
[ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] = [ 0 1 1 1 ] + γ [ 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 ] [ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] \begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} = \begin{bmatrix} 0 \\ 1\\ 1\\ 1 \end{bmatrix} + \gamma \begin{bmatrix} 0 &0 &1 &0\\ 0 &0 &0 &1\\ 0 &0 &0 &1\\ 0 &0 &0 &1 \end{bmatrix}\begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} vπ(s1)vπ(s2)vπ(s3)vπ(s4) = 0111 +γ 0000000010000111 vπ(s1)vπ(s2)vπ(s3)vπ(s4)
对policy2:

在这里插入图片描述

对其求解,得:
[ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] = [ 0.5 ( 0 ) + 0.5 ( − 1 ) 1 1 1 ] + γ [ 0 0.5 0.5 0 0 0 0 1 0 0 0 1 0 0 0 1 ] [ v π ( s 1 ) v π ( s 2 ) v π ( s 3 ) v π ( s 4 ) ] \begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} = \begin{bmatrix} 0.5(0) + 0.5(-1) \\ 1\\ 1\\ 1 \end{bmatrix} + \gamma \begin{bmatrix} 0 &0.5 &0.5 &0\\ 0 &0 &0 &1\\ 0 &0 &0 &1\\ 0 &0 &0 &1 \end{bmatrix}\begin{bmatrix} v_{\pi}(s_1) \\ v_{\pi}(s_2)\\ v_{\pi}(s_3)\\ v_{\pi}(s_4) \end{bmatrix} vπ(s1)vπ(s2)vπ(s3)vπ(s4) = 0.5(0)+0.5(1)111 +γ 00000.50000.50000111 vπ(s1)vπ(s2)vπ(s3)vπ(s4)

Bellman equation: Solve the state values

对于矩阵形式的Bellman equation:
v π = r π + γ P π v π \mathbf{v}_{\pi} = \mathbf{r}_{\pi} + \gamma \mathbf{P}_{\pi} \mathbf{v}_{\pi} vπ=rπ+γPπvπ
其closed-form的解为:
v π = ( I − γ P π ) − 1 r π \mathbf{v}_{\pi} = (\mathbf{I} - \gamma \mathbf{P}_{\pi})^{-1} \mathbf{r}_{\pi} vπ=(IγPπ)1rπ
为了避免求矩阵的逆,可以采用迭代法:
v k + 1 = r + γ P π v k v k → v π = ( I − γ P π ) − 1 r π ,        k → ∞ \mathbf{v}_{k + 1} = \mathbf{r} + \gamma \mathbf{P}_{\pi} \mathbf{v}_k \\ \mathbf{v}_k \rightarrow \mathbf{v}_{\pi} = (\mathbf{I} - \gamma \mathbf{P}_{\pi})^{-1} \mathbf{r}_{\pi}, \;\;\; k \rightarrow \infty vk+1=r+γPπvkvkvπ=(IγPπ)1rπ,k
以下是对于一个grid-world,在给定policy下,各个state的state value。

在这里插入图片描述
在这里插入图片描述

可以看到,不同的policy其产生的state value可能是相同的。
在这里插入图片描述
在这里插入图片描述

可以看到,大多数情况下,不同的policy对state value的影响是比较大的,因此,state value是有效评估policy的一个指标。

Action value

state value: agent从某个state开始可以获得的平均return

action value: agent从某个state开始并采取action可以获得的平均return。

通过action value可以知道当前state下,哪个action是更好的。

定义:
q π ( s , a ) = E [ G t ∣ S t = s , A t = a ] q_{\pi}(s, a) = \mathbb{E}[G_t | S_t = s, A_t = a] qπ(s,a)=E[GtSt=s,At=a]

  • q π ( s , a ) q_{\pi}(s, a) qπ(s,a)是state、action对的函数
  • q π ( s , a ) q_{\pi}(s, a) qπ(s,a)依赖于 π \pi π

根据条件期望公式:
E [ G t ∣ S t = s ] = ∑ a E [ G t ∣ S t = s , A t = a ] π ( a ∣ s ) \mathbb{E}[G_t | S_t = s] = \sum_a \mathbb{E}[G_t | S_t = s, A_t = a] \pi (a | s) E[GtSt=s]=aE[GtSt=s,At=a]π(as)
因此,
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a )            ( 2 ) v_{\pi}(s) = \sum_{a} \pi(a | s) q_{\pi}(s, a) \;\;\;\;\; (2) vπ(s)=aπ(as)qπ(s,a)(2)
对于state value:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] = ∑ a π ( a ∣ s ) ⋅ q π ( s , a )            ( 3 ) \begin{align*} v_{\pi}(s) &= \sum_a \pi(a | s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s'}p(s' | s, a) v_{\pi}(s') \right]\\ &=\sum_a \pi(a | s) \cdot q_{\pi}(s, a) \end{align*} \;\;\;\;\; (3) vπ(s)=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)]=aπ(as)qπ(s,a)(3)
比较公式(2)与公式(3),可以得到action-value function:
q π ( s , a ) = ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ )            ( 4 ) q_{\pi}(s, a) = \sum_r p(r | s, a)r + \gamma \sum_{s'} p(s' | s, a) v_{\pi}(s') \;\;\;\;\; (4) qπ(s,a)=rp(rs,a)r+γsp(ss,a)vπ(s)(4)
通过公式(2)和公式(4)可以发现state value和action value可以相互转化。

例:

在这里插入图片描述

求解,得:
q π ( s 1 , a 1 ) = − 1 + γ v π ( s 1 ) q π ( s 1 , a 2 ) = − 1 + γ v π ( s 2 ) q π ( s 1 , a 3 ) = 0 + γ v π ( s 3 ) q π ( s 1 , a 4 ) = − 1 + γ v π ( s 1 ) q π ( s 1 , a 5 ) = 0 + γ v π ( s 1 ) \begin{align*} &q_{\pi}(s_1, a_1) = -1 + \gamma v_{\pi}(s_1)\\ &q_{\pi}(s_1, a_2) = -1 + \gamma v_{\pi}(s_2)\\ &q_{\pi}(s_1, a_3) = 0 + \gamma v_{\pi}(s_3) \\ &q_{\pi}(s_1, a_4) = -1 + \gamma v_{\pi}(s_1) \\ &q_{\pi}(s_1, a_5) = 0 + \gamma v_{\pi}(s_1) \end{align*} qπ(s1,a1)=1+γvπ(s1)qπ(s1,a2)=1+γvπ(s2)qπ(s1,a3)=0+γvπ(s3)qπ(s1,a4)=1+γvπ(s1)qπ(s1,a5)=0+γvπ(s1)

Summary

  • state value: v π ( s ) = E [ G t ∣ S t = s ] v_{\pi}(s) = \mathbb{E}[G_t | S_t = s] vπ(s)=E[GtSt=s]

  • action value: q π ( s , a ) = E [ G t ∣ S t = s , A t = a ] q_{\pi}(s, a) = \mathbb{E}[G_t | S_t = s, A_t = a] qπ(s,a)=E[GtSt=s,At=a]

  • Bellman equation:

    elementwise form
    v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] = ∑ a π ( a ∣ s ) ⋅ q π ( s , a ) \begin{align*} v_{\pi}(s) &= \sum_a \pi(a | s) \left[ \sum_r p(r | s, a)r + \gamma \sum_{s'}p(s' | s, a) v_{\pi}(s') \right]\\ &=\sum_a \pi(a | s) \cdot q_{\pi}(s, a) \end{align*} vπ(s)=aπ(as)[rp(rs,a)r+γsp(ss,a)vπ(s)]=aπ(as)qπ(s,a)
    matrix-vector form
    v π = r π + γ P v π \mathbf{v}_{\pi} = \mathbf{r}_{\pi} + \gamma \mathbf{P} \mathbf{v}_{\pi} vπ=rπ+γPvπ

  • 可以通过闭合形式解和迭代法求Bellman equation




以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ | vector二维数组的初始化与行、列数的获取

如果直接使用vector<int,vector<int> > v;创建二维数组&#xff0c;那么就会得到一个空的容器&#xff0c;这样再通过push_back赋值是非常麻烦的。 初始化二维数组 在此介绍二维数组初始化的一般操作。 首先看一维数组的初始化示例&#xff1a; 定义一个长度为n&a…

拿捏循环链表

目录&#xff1a; 一&#xff1a;单链表&#xff08;不带头单向不循环&#xff09;与循环链表&#xff08;带头双向循环&#xff09;区别 二&#xff1a;循环链表初始化 三&#xff1a;循环链表头插 四&#xff1a;循环链表尾插 五&#xff1a;循环链表头删 六&#xff1…

MessageBox好用吗?

MessageBox作为一种能够对接多系统平台的工具&#xff0c;在数字营销领域具有很大的实用性和价值。它提供了实时的数据同步、个性化的营销策略、用户互动功能等多种功能&#xff0c;可以帮助企业实现更精准、高效的营销活动。具体来说&#xff0c;MessageBox的优点包括&#xf…

Laykefu客服系统后台登录绕过

【产品介绍】 Laykefu 是一款基于workermangatawayworkerthinkphp5搭建的全功能webim客服系统&#xff0c;旨在帮助企业有效管理和提供优质的客户服务 【漏洞介绍】 请求头中Cookie中的”user_name“不为空时即可绕过登录系统后台&#xff0c;恶意攻击者可利用此漏洞获得后台…

基于摄像头的虹膜识别技术

随着苹果公司的指纹识别TouchID的推广流行&#xff0c;三星等公司的积极跟进&#xff0c;生物识别技术正被移动设备厂商所重视。 虹膜是什么&#xff1f; 人的眼睛由巩膜、虹膜、瞳孔三部分构成。巩膜即眼球外围的白色部分&#xff0c;约占总面积的30%&#xff1b;眼睛中心为瞳…

【React】如何使antd禁用状态的表单输入组件响应点击事件?

最近遇到一个需求&#xff0c;需要在<Input.textarea>组件中&#xff0c;设置属性disabled为true&#xff0c;使textarea响应点击事件&#xff0c;但直接绑定onClick并不会在禁用状态下被响应。 解决方法1 之后尝试了很多方法&#xff0c;比如设置csspointer-events:no…

日本失去的三十年:去杠杆用了14年

去年以来&#xff0c;日股在日本央行转鹰预期、基本面改善和一系列监管新规的催化下高歌猛进&#xff0c;日经指数已经逼近90年代资产泡沫时期的高位。今年迄今累计上涨8.51%&#xff0c;领跑全球&#xff0c;“失落的三十年”似乎已经远去。 日本因何走向衰退&#xff1f;“失…

MPLS VPN功能组件(2)

MP-BGP 采用地址族(Address Family)来区分不同的网络层协议,以便正确处理VPN-IPv4路由 传统的BGP-4(RFC1771)只能管理IPv4的路由信息,无法正确处理地址空间重叠的VPN的路由。 为了正确处理VPN路由,VPN使用RFC2858(Multiprotocol Extensions for BGP-4)中规定的MP-BG…

云计算 - 弹性计算技术全解与实践

一、引言 在过去的十年里&#xff0c;云计算从一个前沿概念发展为企业和开发者的必备工具。传统的计算模型通常局限于单一的、物理的位置和有限的资源&#xff0c;而云计算则通过分布式的资源和服务&#xff0c;为计算能力带来了前所未有的"弹性"。 弹性&#xff1a;…

TryHackMe-Vulnerability Capstone练习

本文相关的TryHackMe实验房间链接&#xff1a;TryHackMe | Vulnerability Capstone 先nmap扫一下 接下来我们访问一下 接下来我们searchsploit找一下漏洞 searchsploit Fuel CMS 执行漏洞exp&#xff08;此处使用TryHackMe中的box&#xff09; 如果使用本地机需要下载exp&am…

算法练习-删除二叉搜索树中的节点(思路+流程图+代码)

难度参考 难度&#xff1a;中等 分类&#xff1a;二叉树 难度与分类由我所参与的培训课程提供&#xff0c;但需要注意的是&#xff0c;难度与分类仅供参考。且所在课程未提供测试平台&#xff0c;故实现代码主要为自行测试的那种&#xff0c;以下内容均为个人笔记&#xff0c;旨…

制作离线版element ui文档

链接&#xff1a;https://pan.baidu.com/s/1k5bsCK9WUlZobhFBLItw1g?pwdgeyk 提取码&#xff1a;geyk --来自百度网盘超级会员V4的分享 https://github.com/ElemeFE/element 克隆官方代码 使用nvm切换node版本&#xff0c;推荐使用14.0.0 http://doc.xutongbao.top/doc/#/zh…

Prompt Engineering实战-构建“哄哄模拟器”

目录 一 背景 二 “哄哄模拟器”的Prompt Prompt 的典型构成 三 操作步骤 3.1 创建对话 3.2 游戏测试 一 背景 前几天《AI 大模型全栈工程师》第二节课讲了“Prompt Engineering&#xff0c;提示工程”&#xff0c;里面提到一些prompt相关的技巧&#xff0c;原则&#xf…

浅谈分布式CAP定律、BASE理论

第一节 分布式架构设计理论与Zookeeper环境搭建 1. 分布式架构设计理论 学习Zookeeper之前,我们需要掌握一些分布式系统基础知识&#xff1a;了解分布式系统的概念、原理。 配置管理 域名服务 分布式同步 发布订阅 1. 分布式架构介绍 1.1 什么是分布式 《分布式系统原理和…

构建异步高并发服务器:Netty与Spring Boot的完美结合

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 ChatGPT体验地址 文章目录 前言IONetty1. 引入依赖2. 服务端4. 客户端结果 总结引导类-Bootstarp和ServerBootstrap连接-NioSocketChannel事件组-EventLoopGroup和NioEventLoopGroup 送书…

COMSOL接触(高度非线性)仿真常见报错及解决方法总结

前言 由于COMSOL采用隐式求解器&#xff0c;相较于使用显式求解器的Dyna、Abaqus等软件。要在COMSOL中实现结构接触这一高度非线性问题难度较大&#xff0c;报错时有发生。究其原因&#xff0c;是当物体之间相互接触时&#xff0c;物体受到的应力、运动路径会发生突变&#xff…

LabVIEW高精度微小电容测量

LabVIEW高精度微小电容测量 在电子工程和科研领域&#xff0c;精确测量微小电容值是一项有一定要求的任务&#xff0c;尤其在涉及到高精度和低成本时。设计了一种基于LabVIEW高精度微小电容测量系统&#xff0c;旨在提供一个既经济又高效的解决方案。 该系统的核心在于使用FD…

C语言中的内存函数你知道多少呢?

目录 ​编辑 1. memcpy的使用和模拟实现 1.1函数介绍 ​编辑 1.2函数的使用 1.3模拟实现 2. memmove的使用和模拟实现 2.1函数介绍 2.2函数的使用 2.3模拟实现 3. memset函数的使用 3.1函数介绍 3.2函数的使用 ​编辑 4. memcmp函数的使用 4.1函数介绍 4.2函数…

Python循环语句——range语句

一、引言 在Python编程中&#xff0c;range函数是一个内置函数&#xff0c;用于生成一个不可变的数字序列。它常被用于循环结构&#xff0c;如for循环&#xff0c;来遍历一系列的数字。尽管其使用非常基础&#xff0c;但range的强大之处在于其提供了灵活性&#xff0c;可以创建…

【2024.2.5练习】砍竹子(25分)

题目描述 题目分析 考虑题目是否满足贪心。每次施展魔法会使一段连续的竹子高度变为一半左右的平方根。根据样例&#xff0c;似乎每次让最高的竹子变短就能得到最优解。 假设魔法一次只能对一根竹子使用&#xff0c;永远不出现连续相同高度的竹子&#xff0c;那么显然无论使用…