本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.
本节我们将介绍强化学习中的值迭代求解方法.
2.1.1 算法步骤
在1.5节我们介绍了通过迭代可以求贝尔曼最优公式的最优解, 这个方法就叫值迭代:
v k + 1 = max π ∈ Π ( r π + γ P π v k ) , k = 0 , 1 , 2 , … v_{k+1}=\max _{\pi \in \Pi}\left(r_\pi+\gamma P_\pi v_k\right), \quad k=0,1,2, \ldots vk+1=π∈Πmax(rπ+γPπvk),k=0,1,2,…
当迭代数 k → ∞ k \rightarrow \infty k→∞时, v k , π k v_k,\pi_k vk,πk会收敛到最优值. 它的算法步骤为:
2.1.1.1 更新策略 π \pi π
基于当前 v k , π k v_k,\pi_k vk,πk, 求最优化问题: 使得上式状态值最大的最优策略 π \pi π, 并将其更新给 π k + 1 \pi_{k+1} πk+1
π k + 1 = arg max π ( r π + γ P π v k ) , \pi_{k+1}=\arg \max _\pi\left(r_\pi+\gamma P_\pi v_k\right), πk+1=argπmax(rπ+γPπvk),
式子中的矩阵展开可以写为:
π k + 1 ( s ) = arg max π ∑ a π ( a ∣ s ) ( ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v k ( s ′ ) ) ⏟ q k ( s , a ) , s ∈ S . \pi_{k+1}(s)=\arg \max _\pi \sum_a \pi(a \mid s) \underbrace{\left(\sum_r p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_k\left(s^{\prime}\right)\right)}_{q_k(s, a)}, \\ \quad s \in \mathcal{S} . πk+1(s)=argπmaxa∑π(a∣s)qk(s,a) (r∑p(r∣s,a)r+γs′∑p(s′∣s,a)vk(s′)),s∈S.
1.5节我们介绍过了, 最优解是一个确定贪婪策略, 即只有最佳动作的选择概率是1:
π k + 1 ( a ∣ s ) = { 1 , a = a k ∗ ( s ) 0 , a ≠ a k ∗ ( s ) \pi_{k+1}(a \mid s)= \begin{cases}1, & a=a_k^*(s) \\ 0, & a \neq a_k^*(s)\end{cases} πk+1(a∣s)={1,0,a=ak∗(s)a=ak∗(s)
其中动作 a k ∗ ( s ) a_k^*(s) ak∗(s)是最优解: a k ∗ ( s ) = arg max a q k ( s , a ) a_k^*(s)=\arg \max _a q_k(s, a) ak∗(s)=argmaxaqk(s,a)
2.1.1.2 更新值 v v v
得到新的策略 π k + 1 \pi_{k+1} πk+1之后, 更新新的值 v k + 1 v_{k+1} vk+1即可:
v k + 1 = r π k + 1 + γ P π k + 1 v k , v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}} v_k, vk+1=rπk+1+γPπk+1vk,
式子展开可以写成:
v k + 1 ( s ) = ∑ a π k + 1 ( a ∣ s ) ( ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v k ( s ′ ) ) ⏟ q k ( s , a ) , s ∈ S . v_{k+1}(s)=\sum_a \pi_{k+1}(a \mid s) \underbrace{\left(\sum_r p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_k\left(s^{\prime}\right)\right)}_{q_k(s, a)}, \\ s \in \mathcal{S} . vk+1(s)=a∑πk+1(a∣s)qk(s,a) (r∑p(r∣s,a)r+γs′∑p(s′∣s,a)vk(s′)),s∈S.
因为最优策略 π k + 1 \pi_{k+1} πk+1是一个贪婪策略, 所以上式实际上就是最大的动作值 q k ( s , a ) q_k(s, a) qk(s,a), 即:
v k + 1 ( s ) = max a q k ( s , a ) . v_{k+1}(s)=\max _a q_k(s, a) . vk+1(s)=amaxqk(s,a).
2.1.1.3 伪代码
- 输入: 所有的 p ( r ∣ s , a ) , p ( s ′ ∣ s , a ) p(r \mid s, a), p\left(s^{\prime} \mid s, a\right) p(r∣s,a),p(s′∣s,a)都是已知的, 状态值初始解 v 0 v_0 v0
- 输出: 贝尔曼最优公式的最优解: v ∗ , π ∗ v^*,\pi^* v∗,π∗
- 迭代终止条件: ∥ v k − v k − 1 ∥ < e p s i l o n \left\|v_k-v_{k-1}\right\|<epsilon ∥vk−vk−1∥<epsilon, e p s i l o n epsilon epsilon是一个极小值超参数
-
For every state
s
∈
S
, do
\text { For every state } s \in \mathcal{S} \text {, do }
For every state s∈S, do
-
For every action
a
∈
A
(
s
)
, do
\text { For every action } a \in \mathcal{A}(s) \text {, do }
For every action a∈A(s), do
- 计算 q-value: q k ( s , a ) = ∑ r p ( r ∣ s , a ) r + γ ∑ s ′ p ( s ′ ∣ s , a ) v k ( s ′ ) \text { q-value: } q_k(s, a)=\sum_r p(r \mid s, a) r+\gamma \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) v_k\left(s^{\prime}\right) q-value: qk(s,a)=∑rp(r∣s,a)r+γ∑s′p(s′∣s,a)vk(s′)
- 找到最优解 a k ∗ ( s ) = arg max a q k ( s , a ) a_k^*(s)=\arg \max _a q_k(s, a) ak∗(s)=argmaxaqk(s,a), 即使得动作值最大的动作
- 更新策略: π k + 1 ( a ∣ s ) = { 1 , a = a k ( s ) 0 , a ≠ a k ( s ) \pi_{k+1}(a \mid s)= \begin{cases}1, & a=a_k^(s) \\ 0, & a \neq a_k^(s)\end{cases} πk+1(a∣s)={1,0,a=ak(s)a=ak(s)
- 更新值: v k + 1 ( s ) = max a q k ( s , a ) v_{k+1}(s)=\max _a q_k(s, a) vk+1(s)=maxaqk(s,a)
-
For every action
a
∈
A
(
s
)
, do
\text { For every action } a \in \mathcal{A}(s) \text {, do }
For every action a∈A(s), do
2.1.2 例子
仿真世界如图所示, 奖励设计如下:
- 抵达禁止格或边界的奖励是-1: r boundary = r forbidden = − 1 r_{\text {boundary }}=r_{\text {forbidden }}=-1 rboundary =rforbidden =−1
- 抵达终点的奖励是1: r target = 1 r_{\text {target }}=1 rtarget =1
- γ = 0.9 \gamma=0.9 γ=0.9
- 其他行为奖励是0
根据这个奖励设计, 该仿真场景中的每个状态和动作的动作值计算公式如下:
首先初始化 v 0 ( s 1 ) = v 0 ( s 2 ) = v 0 ( s 3 ) = v 0 ( s 4 ) = 0 v_0\left(s_1\right)=v_0\left(s_2\right)=v_0\left(s_3\right)=v_0\left(s_4\right)=0 v0(s1)=v0(s2)=v0(s3)=v0(s4)=0, 然后我们开始值迭代算法:
2.1.2.1 k=0
我们计算出了所有状态和动作组合的动作值:
每个状态都选择动作值结果最大的作为最优动作, 更新所有状态的最优策略:
π 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\left(a_5 \mid s_1\right)=1, \quad \pi_1\left(a_3 \mid s_2\right)=1, \quad \pi_1\left(a_2 \mid s_3\right)=1, \quad \pi_1\left(a_5 \mid s_4\right)=1 π1(a5∣s1)=1,π1(a3∣s2)=1,π1(a2∣s3)=1,π1(a5∣s4)=1
接着更新所有状态的状态值
v 1 ( s 1 ) = 0 , v 1 ( s 2 ) = 1 , v 1 ( s 3 ) = 1 , v 1 ( s 4 ) = 1 v_1\left(s_1\right)=0, \quad v_1\left(s_2\right)=1, \quad v_1\left(s_3\right)=1, \quad v_1\left(s_4\right)=1 v1(s1)=0,v1(s2)=1,v1(s3)=1,v1(s4)=1
最后计算 ∥ v 1 − v 0 ∥ = 3 \left\|v_1-v_{0}\right\|=\sqrt3 ∥v1−v0∥=3, 继续迭代
2.1.2.2 k=1
计算出了所有状态和动作组合的动作值:
每个状态都选择动作值结果最大的作为最优动作, 更新所有状态的最优策略:
π 2 ( a 3 ∣ s 1 ) = 1 , π 2 ( a 3 ∣ s 2 ) = 1 , π 2 ( a 2 ∣ s 3 ) = 1 , π 2 ( a 5 ∣ s 4 ) = 1 \pi_2\left(a_3 \mid s_1\right)=1, \quad \pi_2\left(a_3 \mid s_2\right)=1, \quad \pi_2\left(a_2 \mid s_3\right)=1, \quad \pi_2\left(a_5 \mid s_4\right)=1 π2(a3∣s1)=1,π2(a3∣s2)=1,π2(a2∣s3)=1,π2(a5∣s4)=1
接着更新所有状态的状态值
v 2 ( s 1 ) = γ 1 , v 2 ( s 2 ) = 1 + γ 1 , v 2 ( s 3 ) = 1 + γ 1 , v 2 ( s 4 ) = 1 + γ 1. v_2\left(s_1\right)=\gamma 1, \quad v_2\left(s_2\right)=1+\gamma 1, \quad v_2\left(s_3\right)=1+\gamma 1, \quad v_2\left(s_4\right)=1+\gamma 1 . v2(s1)=γ1,v2(s2)=1+γ1,v2(s3)=1+γ1,v2(s4)=1+γ1.
最后计算 ∥ v 2 − v 1 ∥ = 2 γ \left\|v_2-v_{1}\right\|=2\gamma ∥v2−v1∥=2γ, 继续迭代
2.1.2.3 k=2
计算出了所有状态和动作组合的动作值:
q-table a 1 a 2 a 3 a 4 a 5 s 1 − 1 + γ 2 − 1 + γ ( 1 + γ ) 0 + γ ( 1 + γ ) − 1 + γ 2 0 + γ 2 s 2 − 1 + γ ( 1 + γ ) − 1 + γ ( 1 + γ ) 1 + γ ( 1 + γ ) 0 + γ 2 − 1 + γ ( 1 + γ ) s 3 0 + γ 2 1 + γ ( 1 + γ ) − 1 + γ ( 1 + γ ) − 1 + γ ( 1 + γ ) 0 + γ ( 1 + γ ) s 4 − 1 + γ ( 1 + γ ) − 1 + γ ( 1 + γ ) − 1 + γ ( 1 + γ ) 0 + γ ( 1 + γ ) 1 + γ ( 1 + γ ) \begin{array}{c|l|l|l|l|l}\hline \text { q-table } & a_1 & a_2 & a_3 & a_4 & a_5 \\\hline s_1 & -1+\gamma^2 & -1+\gamma(1+\gamma) & 0+\gamma(1+\gamma) & -1+\gamma^2 & 0+\gamma^2 \\\hline s_2 & -1+\gamma(1+\gamma) & -1+\gamma(1+\gamma) & 1+\gamma(1+\gamma) & 0+\gamma^2 & -1+\gamma(1+\gamma) \\\hline s_3 & 0+\gamma^2 & 1+\gamma(1+\gamma) & -1+\gamma(1+\gamma) & -1+\gamma(1+\gamma) & 0+\gamma(1+\gamma) \\\hline s_4 & -1+\gamma(1+\gamma) & -1+\gamma(1+\gamma) & -1+\gamma(1+\gamma) & 0+\gamma(1+\gamma) & 1+\gamma(1+\gamma) \\\hline\end{array} q-table s1s2s3s4a1−1+γ2−1+γ(1+γ)0+γ2−1+γ(1+γ)a2−1+γ(1+γ)−1+γ(1+γ)1+γ(1+γ)−1+γ(1+γ)a30+γ(1+γ)1+γ(1+γ)−1+γ(1+γ)−1+γ(1+γ)a4−1+γ20+γ2−1+γ(1+γ)0+γ(1+γ)a50+γ2−1+γ(1+γ)0+γ(1+γ)1+γ(1+γ)
每个状态都选择动作值结果最大的作为最优动作, 更新所有状态的最优策略:
π 3 ( a 3 ∣ s 1 ) = 1 , π 3 ( a 3 ∣ s 2 ) = 1 , π 3 ( a 2 ∣ s 3 ) = 1 , π 3 ( a 5 ∣ s 4 ) = 1 \pi_3\left(a_3 \mid s_1\right)=1, \quad \pi_3\left(a_3 \mid s_2\right)=1, \quad \pi_3\left(a_2 \mid s_3\right)=1, \quad \pi_3\left(a_5 \mid s_4\right)=1 π3(a3∣s1)=1,π3(a3∣s2)=1,π3(a2∣s3)=1,π3(a5∣s4)=1
接着更新所有状态的状态值
v 3 ( s 1 ) = 1.71 , v 3 ( s 2 ) = 2.71 , v 3 ( s 3 ) = 2.71 , v 3 ( s 4 ) = 2.71 v_3\left(s_1\right)=1.71, \quad v_3\left(s_2\right)=2.71, \quad v_3\left(s_3\right)=2.71, \quad v_3\left(s_4\right)=2.71 v3(s1)=1.71,v3(s2)=2.71,v3(s3)=2.71,v3(s4)=2.71
最后计算 ∥ v 3 − v 2 ∥ = 1.62 \left\|v_3-v_{2}\right\|=1.62 ∥v3−v2∥=1.62, 继续迭代
2.1.2.4 k=3,4
前面过程类似的, 最优策略没有变, 最后 ∥ v 4 − v 3 ∥ = 0.586 , ∥ v 5 − v 4 ∥ = . . . \left\|v_4-v_{3}\right\|=0.586, \left\|v_5-v_{4}\right\|=... ∥v4−v3∥=0.586,∥v5−v4∥=...
说明已经收敛. 这个例子笔者有个问题, 就是值迭代中即使最优策略已经不变了, 状态值是在变化的, 但是还需要几次循环才能达到收敛条件. 那么当迭代中最优策略已经不变了, 是否可以作为终止迭代的条件, 如果不可以是因为什么呢?待后续学习过程中解答.
推荐阅读
- 端到端理论与实战
- 动手学轨迹预测
- 动手学运动规划
- 动手学行为决策
- 强化学习入门笔记
