本文主要是介绍▶《强化学习的数学原理》(2024春)_西湖大学赵世钰 Ch2 贝尔曼公式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
PPT 截取有用信息。 课程网站做习题。总体 MOOC 过一遍
- 1、学堂在线 视频 + 习题
- 2、相应章节 过电子书 复习 GitHub界面链接
- 3、总体 MOOC 过一遍
学堂在线 课程页面链接
中国大学MOOC 课程页面链接
B 站 视频链接
PPT和书籍下载网址: 【github链接】
onedrive链接:
【书】
【课程PPT】
文章目录
- 计算 return
- 方法一: 根据定义
- 方法二: 根据状态间回报的依赖关系
- State value 状态值 v π ( s ) v_\pi(s) vπ(s)
- 贝尔曼公式 推导
- 如何写出 Bellman 方程并逐步计算状态值
- 求解 贝尔曼方程
- Action value 动作值 q π ( s , a ) q_\pi(s, a) qπ(s,a)
——————
回报 return: 沿着 轨迹 获得的 奖励 折扣和。
可用于 评估策略
计算 return 的值,来评估以下 3 个策略
3 种策略的区别在于第一格。 策略 1 是往下走,策略 2 是 往右走,策略 3 往下 和 往右的概率 分别为 50%。其它格相同。
计算 return
方法一: 根据定义
r e t u r n 3 \rm return_3 return3 实际是 状态值。
方法二: 根据状态间回报的依赖关系
v i v_i vi: 从 s i s_i si 出发获得的回报
例:
推导:
v 1 = r 1 + γ r 2 + γ 2 r 3 + . . . = r 1 + γ ( r 2 + γ r 3 + . . . ) = r 1 + γ v 2 v_1=r_1+\gamma r_2 + {\gamma}^2r_3+...=r_1 +\gamma(r_2+\gamma r_3+...)=r_1+\gamma v_2 v1=r1+γr2+γ2r3+...=r1+γ(r2+γr3+...)=r1+γv2
v 2 = r 2 + γ r 3 + γ 2 r 4 + . . . = r 2 + γ ( r 3 + γ r 4 + . . . ) = r 2 + γ v 3 v_2=r_2+\gamma r_3 + {\gamma}^2r_4+...=r_2 +\gamma(r_3+\gamma r_4+...)=r_2+\gamma v_3 v2=r2+γr3+γ2r4+...=r2+γ(r3+γr4+...)=r2+γv3
v 3 = r 3 + γ r 4 + γ 2 r 1 + . . . = r 3 + γ ( r 4 + γ r 1 + . . . ) = r 3 + γ v 4 v_3=r_3+\gamma r_4 + {\gamma}^2r_1+...=r_3 +\gamma(r_4+\gamma r_1+...)=r_3+\gamma v_4 v3=r3+γr4+γ2r1+...=r3+γ(r4+γr1+...)=r3+γv4
v 4 = r 4 + γ r 1 + γ 2 r 2 + . . . = r 4 + γ ( r 1 + γ r 2 + . . . ) = r 4 + γ v 1 v_4=r_4+\gamma r_1 + {\gamma}^2r_2+...=r_4 +\gamma(r_1+\gamma r_2+...)=r_4+\gamma v_1 v4=r4+γr1+γ2r2+...=r4+γ(r1+γr2+...)=r4+γv1写成矩阵形式
[ v 1 v 2 v 3 v 4 ] = [ r 1 r 2 r 3 r 4 ] + γ [ v 2 v 3 v 4 v 1 ] = [ r 1 r 2 r 3 r 4 ] + γ [ 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 ] [ v 1 v 2 v 3 v 4 ] v = r + γ P v \begin{align*} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ \end{bmatrix} &= \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \\ \end{bmatrix} + \gamma\begin{bmatrix} v_2 \\ v_3 \\ v_4 \\ v_1 \end{bmatrix}\\ &= \begin{bmatrix} r_1 \\ r_2 \\ r_3 \\ r_4 \\ \end{bmatrix} + \gamma\begin{bmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} v_1\\ v_2 \\ v_3 \\ v_4 \\ \end{bmatrix}\\ \mathbf{v}&=\mathbf{r}+\gamma\mathbf{P}\mathbf{v} \end{align*} v1v2v3v4 v= r1r2r3r4 +γ v2v3v4v1 = r1r2r3r4 +γ 0001100001000010 v1v2v3v4 =r+γPv
Bellman 方程的核心思想:从一种状态出发所获得的收益依赖于从其他状态出发所获得的收益。
从不同状态出发得到的 return , 依赖于 从其它状态 出发得到的 return。
Bootstrapping: 从自己出发不断迭代
State value 状态值 v π ( s ) v_\pi(s) vπ(s)
P2 状态值
G t G_t Gt 的期望【期望值/均值】
状态值函数 / 状态值
: v π ( s ) = E [ G t ∣ S t = s ] v_\pi(s)=\mathbb{E}[G_t|S_t=s] vπ(s)=E[Gt∣St=s]
状态值 v π ( s ) v_\pi(s) vπ(s) 取决于 状态 s s s 和 策略 π \pi π, 和 时间 t t t 无关。
多步 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},... StAtRt+1,St+1At+1Rt+2,St+2At+2Rt+3,...
折扣回报:
G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + . . . G_t=R_{t+1}+\gamma R_{t+2}+{\gamma}^2R_{t+3}+... Gt=Rt+1+γRt+2+γ2Rt+3+...
- γ ∈ [ 0 , 1 ) \gamma \in [0, 1) γ∈[0,1) 为折扣率
return VS state value
return: 针对 单个 trajectory
state value: 多个 trajectory 的 return 的平均值
- 从 某个状态 出发,有可能得到多个 trajectory,此时得到的值可能不一样。
- 当 从 某个状态出发,仅存在一条 trajectory,此时两者相同
贝尔曼公式 推导
P3 贝尔曼公式 推导
贝尔曼公式 描述了 不同状态 的 state value 之间的关系。
对于某个 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},... StAtRt+1,St+1At+1Rt+2,St+2At+2Rt+3,...
折扣回报:
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}^2R_{t+3}+...\\ &= R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...)\\ &=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
状态值
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[Gt∣St=s]=E[Rt+1+γGt+1∣St=s]=E[Rt+1∣St=s]+γE[Gt+1∣St=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+1∣St=s]=a∑π(a∣s)E[Rt+1∣St=s,At=a]=a∑π(a∣s)r∑p(r∣s,a)r
未来奖励 【延迟奖励】均值
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^{\prime}}\mathbb{E}[G_{t+1}|S_t=s, S_{t+1}=s^{\prime}]p(s^{\prime}|s)\\ &=\sum_{s^{\prime}}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime}]p(s^{\prime}|s)\\ &= \sum_{s^{\prime}} v_\pi (s^{\prime})p(s^{\prime}|s)\\ &= \sum_{s^{\prime}} v_\pi (s^{\prime})\sum_ap(s^{\prime}|s, a)\pi(a|s)\end{align*} E[Gt+1∣St=s]=s′∑E[Gt+1∣St=s,St+1=s′]p(s′∣s)=s′∑E[Gt+1∣St+1=s′]p(s′∣s)=s′∑vπ(s′)p(s′∣s)=s′∑vπ(s′)a∑p(s′∣s,a)π(a∣s)
表征状态值 之间关系 的 贝尔曼公式:
——————————————
PDF 补充:
贝尔曼公式:
v π ( s ) = ∑ a π ( a ∣ s ) [ ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) ] v_\pi(s)=\sum\limits_{a}\pi(a|s)\Big[\sum\limits_{r}p(r|s,a)r + \gamma \sum\limits_{s^\prime}p(s^\prime|s,a)v_\pi(s^\prime)\Big] vπ(s)=a∑π(a∣s)[r∑p(r∣s,a)r+γs′∑p(s′∣s,a)vπ(s′)]
贝尔曼公式 的 另两种等效写法:
等效 写法一:
p ( s ′ ∣ s , a ) = ∑ r p ( s ′ , r ∣ s , a ) p(s^\prime|s, a)=\sum\limits_{r}p(s^\prime,r|s, a)~~~~ p(s′∣s,a)=r∑p(s′,r∣s,a) 后续是否 进入 某个状态 取决于 回报p ( r ∣ s , a ) = ∑ s ′ p ( s ′ , r ∣ s , a ) p(r|s, a)=\sum\limits_{s^\prime}p(s^\prime,r|s, a)~~~~ p(r∣s,a)=s′∑p(s′,r∣s,a) 获得 某个回报 的概率 取决于 后续状态
v π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ ∑ r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] ) v_\pi(s)=\sum\limits_a\pi(a|s)\textcolor{blue}{\sum\limits_{s^\prime}\sum\limits_rp(s^\prime,r|s, a)}[r+\gamma v_\pi(s^\prime)]) vπ(s)=a∑π(a∣s)s′∑r∑p(s′,r∣s,a)[r+γvπ(s′)])
等效 写法二 : 某些问题的 回报 r r r 仅取决于 下一状态 s ′ s^\prime s′
v π ( s ) = ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) [ r ( s ′ ) + γ v π ( s ′ ) ] v_\pi(s)=\sum\limits_a\pi(a|s)\sum\limits_{s^\prime}p(s^\prime|s,a)[r(s^\prime)+\gamma v_\pi(s^\prime)] vπ(s)=a∑π(a∣s)s′∑p(s′∣s,a)[r(s′)+γvπ(s′)]
——————————————
2.5 示例:确定 相应的贝尔曼方程
如何写出 Bellman 方程并逐步计算状态值
如何写出 Bellman 方程并逐步计算状态值。
示例 2:
上一个 示例采取的策略 计算得到的 v π ( s 1 ) v_\pi(s_1) vπ(s1) 比当前 这个示例 大, 因为 上一个 示例直接往下走, 当前这个示例 有 50% 的 概率 会 往 右走,进入 禁区。
P4 贝尔曼公式的 矩阵 和 向量 形式
状态值
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 + γ ∑ a π ( a ∣ s ) ∑ s ′ p ( s ′ ∣ s , a ) v π ( s ′ ) = r π ( s ) + γ ∑ s ′ p π ( s ′ ∣ s ) v π ( 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_a \pi(a|s)\sum_{s^{\prime}} p(s^{\prime}|s, a)v_\pi (s^{\prime})\\ &= r_\pi(s)+\gamma\sum_{s^{\prime}}p_\pi(s^{\prime}|s)v_\pi(s^{\prime})\end{align*} vπ(s)=E[Rt+1∣St=s]+γE[Gt+1∣St=s]=a∑π(a∣s)r∑p(r∣s,a)r+γa∑π(a∣s)s′∑p(s′∣s,a)vπ(s′)=rπ(s)+γs′∑pπ(s′∣s)vπ(s′)
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)+γsj∑pπ(sj∣si)vπ(sj)
v π = r π + γ P π v π \bm v_\pi=\bm{r}_\pi+\gamma \bm P_\pi \bm v_\pi vπ=rπ+γPπvπ
状态转移矩阵:
求解 贝尔曼方程
求解 贝尔曼方程 是进行策略评估的 重要步骤。
证明: v k v_k vk 最终 收敛到 v π v_\pi vπ
归纳法
定义 误差 Δ k = v k − v π \Delta_k = v_k-v_\pi Δk=vk−vπ, 只需证明 Δ k → 0 \Delta_k\to0 Δk→0
将用到的等式
1、贝尔曼公式 v π = r π + γ P π v π v_\pi = r_\pi + \gamma P_\pi v_\pi vπ=rπ+γPπvπ
2、 v k + 1 = Δ k + 1 + v π v_{k + 1} =\Delta_{k +1}+v_\pi vk+1=Δk+1+vπ
3、 v k = Δ k + v π v_k=\Delta_k+v_\pi vk=Δk+vπ
————————
v k + 1 = r π + γ P π v k v_{k + 1} = r_\pi + \gamma P_\pi v_k vk+1=rπ+γPπvk
——> Δ k + 1 + v π = r π + γ P π ( Δ k + v π ) \Delta_{k +1}+v_\pi=r_\pi+\gamma P_\pi(\Delta_k+v_\pi) Δk+1+vπ=rπ+γPπ(Δk+vπ)
——> Δ k + 1 = − v π + r π + γ P π Δ k + γ P π v π = γ P π Δ k \Delta_{k +1}= -v_\pi+r_\pi+\gamma P_\pi\Delta_k+\gamma P_\pi v_\pi =\gamma P_\pi\Delta_k Δk+1=−vπ+rπ+γPπΔk+γPπvπ=γPπΔk
迭代递推
Δ k + 1 = γ P π Δ k = γ 2 P π 2 Δ k − 1 = γ 3 P π 3 Δ k − 2 = . . . = γ k + 1 P π k + 1 Δ 0 \Delta_{k +1}=\gamma P_\pi\Delta_k=\gamma^2 P_\pi^2\Delta_{k-1}=\gamma^3 P_\pi^3\Delta_{k-2}=...=\gamma ^{k+1}P_\pi^{k+1}\Delta_0 Δk+1=γPπΔk=γ2Pπ2Δk−1=γ3Pπ3Δk−2=...=γk+1Pπk+1Δ0
Action value 动作值 q π ( s , a ) q_\pi(s, a) qπ(s,a)
P5 Action value: 选哪个 action
State value VS Action value
State value
:从 某个状态 出发 获得 的平均回报。 v π ( s ) v_\pi(s) vπ(s)
Action value
: 从某个状态出发,进行动作后的平均回报。 q π ( s , a ) q_\pi(s, a) qπ(s,a)
动作值 = 即时奖励的均值 + 未来奖励的均值。
先计算 state values, 再计算 action values 。
在没有模型的情况下,通过数据直接计算 action values。
状态值 和 回报的关系: 状态值是 agent 从该状态出发所能获得的收益的平均值。
状态值 和 动作值的关系: 一方面,状态值是 该状态的 动作值的平均值。另一方面,动作值 依赖于 agent 在采取动作后可能过渡到的下一个状态的状态值。
v π ( s ) = ∑ a π ( a ∣ s ) q π ( s , a ) v_\pi(s)=\sum\limits_a\pi(a|s)q_\pi(s, a) vπ(s)=a∑π(a∣s)qπ(s,a)
用 动作值 的贝尔曼方程
q π ( s , a ) = ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) ∑ a ′ ∈ A ( s ′ ) π ( a ′ ∣ s ′ ) q π ( s ′ , a ′ ) q_\pi(s, a)=\sum\limits_rp(r|s, a)r+\gamma\sum\limits_{s^\prime}p(s^{\prime}|s,a)\sum\limits_{a^\prime \in\cal A(s^\prime)}\pi(a^\prime|s^\prime)q_\pi(s^\prime,a^\prime) qπ(s,a)=r∑p(r∣s,a)r+γs′∑p(s′∣s,a)a′∈A(s′)∑π(a′∣s′)qπ(s′,a′)
—————————————————————————————————
习题笔记:
- State value:折扣回报的期望值。
- 状态值 v π ( s ) v_\pi(s) vπ(s) 和
策略
、状态有关。不是 动作。 - 贝尔曼方程 描述了所有状态值之间的关系。
- 每一个状态都对应一个贝尔曼方程。
- 动作值(action value) q π ( s , a ) q_\pi(s, a) qπ(s,a) 和动作、状态和策略有关。
这篇关于▶《强化学习的数学原理》(2024春)_西湖大学赵世钰 Ch2 贝尔曼公式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!