动态规划求解强化学习任务——策略评估[迭代解]
- 目录
- 回顾
- 逻辑执行过程
- 算法过程与解析
- 算法过程
- 算法解析
- 实例解析
- 逻辑场景介绍
- 策略评估过程求解
- 异步动态规划法和同步动态规划法；
目录
回顾
上一节中讲到使用解析方式求解最优价值函数,我们对逻辑场景进行简单设计：
设定状态(State)属于离散型随机变量，状态集合
S
\mathcal S
S内部共包含
∣
S
∣
|\mathcal S|
∣S∣个离散状态：
S
=
{
s
1
,
s
2
,
.
.
.
,
s
∣
S
∣
}
=
{
s
i
}
∣
i
=
1
∣
S
∣
\mathcal S = \{s_1,s_2,...,s_{|\mathcal S|}\}=\{s_i\}\vert_{i=1}^{|\mathcal S|}
S={s1,s2,...,s∣S∣}={si}∣i=1∣S∣
设定动作(Action)属于离散型随机变量，动作集合
A
\mathcal A
A内部共包含
∣
A
∣
|\mathcal A|
∣A∣个离散动作,并且任意一个动作在每个状态中均有意义：
A
=
{
a
1
,
a
2
,
a
3
,
.
.
.
,
a
∣
A
∣
}
=
{
a
i
}
∣
i
=
1
∣
A
∣
\mathcal A = \{a_1,a_2,a_3,...,a_{|\mathcal A|}\}=\{a_i\}\vert_{i=1}^{|\mathcal A|}
A={a1,a2,a3,...,a∣A∣}={ai}∣i=1∣A∣
设定奖励(Reward)属于离散型随机变量，奖励集合
R
\mathcal R
R内部共包含
∣
R
∣
|\mathcal R|
∣R∣个离散奖励：
R
=
{
r
1
,
r
2
,
r
3
,
.
.
.
,
r
∣
R
∣
}
=
{
r
i
}
∣
i
=
1
∣
R
∣
\mathcal R = \{r_1,r_2,r_3,...,r_{|\mathcal R|}\}=\{r_i\}\vert_{i=1}^{|\mathcal R|}
R={r1,r2,r3,...,r∣R∣}={ri}∣i=1∣R∣
基于上述逻辑场景，最优价值函数的解析解可以理解成求解由
∣
S
∣
|\mathcal S|
∣S∣个贝尔曼期望期望方程组成的
∣
S
∣
|\mathcal S|
∣S∣元1次方程组:
V
π
(
s
)
=
(
V
π
(
s
1
)
V
π
(
s
2
)
V
π
(
s
3
)
.
.
.
V
π
(
s
∣
S
∣
)
)
=
(
r
π
(
s
1
)
+
γ
∑
j
=
1
∣
S
∣
P
π
(
s
1
,
s
j
)
V
π
(
s
j
)
r
π
(
s
2
)
+
γ
∑
j
=
1
∣
S
∣
P
π
(
s
2
,
s
j
)
V
π
(
s
j
)
r
π
(
s
3
)
+
γ
∑
j
=
1
∣
S
∣
P
π
(
s
3
,
s
j
)
V
π
(
s
j
)
.
.
.
r
π
(
s
∣
S
∣
)
+
γ
∑
j
=
1
∣
S
∣
P
π
(
s
∣
S
∣
,
s
j
)
V
π
(
s
j
)
)
V_\pi(s) = \begin{pmatrix} V_\pi(s_1) \\ V_\pi(s_2) \\ V_\pi(s_3)\\ ...\\ V_\pi(s_{|\mathcal S|}) \end{pmatrix}= \begin{pmatrix} r_\pi(s_1) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_1,s_j)V_\pi(s_j) \\ r_\pi(s_2) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_2,s_j)V_\pi(s_j) \\ r_\pi(s_3) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_3,s_j)V_\pi(s_j)\\ ...\\ r_\pi(s_{|\mathcal S|}) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_{|\mathcal S|},s_j)V_\pi(s_j) \end{pmatrix}
Vπ(s)=⎝⎜⎜⎜⎜⎛Vπ(s1)Vπ(s2)Vπ(s3)...Vπ(s∣S∣)⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎛rπ(s1)+γ∑j=1∣S∣Pπ(s1,sj)Vπ(sj)rπ(s2)+γ∑j=1∣S∣Pπ(s2,sj)Vπ(sj)rπ(s3)+γ∑j=1∣S∣Pπ(s3,sj)Vπ(sj)...rπ(s∣S∣)+γ∑j=1∣S∣Pπ(s∣S∣,sj)Vπ(sj)⎠⎟⎟⎟⎟⎟⎞
算法的时间复杂度 → ∣ S ∣ 3 \to |\mathcal S|^3 →∣S∣3，为了优化时间复杂度，本节我们介绍使用迭代方式求解最优价值函数。
逻辑执行过程
迭代求解的大致思路表示如下：
构造一个关于价值函数的数列，每迭代一次，就将迭代后的价值函数从尾部插入到数列中，并随着迭代次数的增加，数列尾部的结果通过不断更新并最终优化到某个具体结果。
根据之前提到的不动点定理，贝尔曼期望方程完全满足上述逻辑场景中的条件，因为:
- 贝尔曼期望方程中的自变量和函数均是价值函数；
可以将其理解为：我们以之前的价值函数作为媒介/条件，产生一个优于之前价值函数的新的价值函数，我们称这种方法为 自举法(Boostrapping) - 不动点定理是经过数学证明必然收敛的，因此贝尔曼期望方程输出结果随着迭代过程增加 必然收敛 。
结合上面逻辑，使用贝尔曼期望方程对迭代过程进行设计：
V
π
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
(
s
′
)
]
V
k
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
∑
s
′
,
r
p
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
k
−
1
(
s
′
)
]
\begin{aligned} V_\pi(s) & = \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a)[r + \gamma V_\pi(s')] \\ V_k(s) & = \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{k-1}(s')] \\ \end{aligned}
Vπ(s)Vk(s)=a∈A∑π(a∣s)s′,r∑p(s′,r∣s,a)[r+γVπ(s′)]=a∈A∑π(a∣s)s′,r∑p(s′,r∣s,a)[r+γVk−1(s′)]
观察上述两个公式，第一个是贝尔曼期望方程，第二个是基于贝尔曼期望方程修改的迭代公式，相比于期望方程，该公式仅修改了价值函数对应的下标，但是思路发生了很大变化；
策略评估的核心就是给定策略
π
\pi
π,求解最优状态价值函数
V
π
(
s
)
→
V_\pi(s) \to
Vπ(s)→因此我们淡化对策略
π
\pi
π的表示(
π
\pi
π是确定的)，注重对迭代步骤
k
k
k的表示。
- 贝尔曼期望方程中的 V π ( s ′ ) V_\pi(s') Vπ(s′)是 S t = s → S t + 1 = s ′ S_t=s \to S_{t+1}=s' St=s→St+1=s′的价值函数结果，是未来时刻价值函数的信息；
- 迭代公式中的 V k − 1 ( s ′ ) V_{k-1}(s') Vk−1(s′)是过去最新一次策略评估产生的状态价值函数结果。
算法过程与解析
算法过程
以状态价值函数(state-value function)为例，我们构建基于状态价值函数的策略评估算法如下：
| 输入 | 初始策略： π ( a ∣ s ) \pi(a \mid s) π(a∣s),动态特性函数： p ( s ′ , r ∣ s , a ) p(s',r\mid s,a) p(s′,r∣s,a),奖励： r r r,折扣系数： γ \gamma γ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始化操作 (Initialization operation) | 1. 对
∀
s
∈
S
\forall s \in \mathcal S
∀s∈S,初始化状态价值函数：如
V
(
s
)
=
0
V(s) = 0
V(s)=0; 2.设置一个阈值 θ \theta θ,将其设置为很小的实数值，如 θ = 0.01 \theta=0.01 θ=0.01 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 策略评估 (Policy Evaluation) | 1. repeat 对每一轮策略评估：
k
=
1
,
2
,
.
.
.
k=1,2,...
k=1,2,... 2. δ ← 0 \delta \gets 0 δ←0 3. for 每个状态 s s s do： 4. v ← V ( s ) \mathcal v \gets V(s) v←V(s) 5. V ( s ) ← ∑ a ∈ A π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V ( s ′ ) ] V(s) \gets \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a) [r + \gamma V(s')] V(s)←∑a∈Aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γV(s′)] 6. δ ← m a x ( δ , ∣ v − V ( s ) ∣ ) \delta \gets max(\delta, \mid \mathcal v - V(s) \mid) δ←max(δ,∣v−V(s)∣) 7. end for 8. until δ < θ \delta < \theta δ ∣Vk+1(s)−Vinit(s)∣> 人为设置标准 δ → \delta \to δ→ 两次迭代结果有较大差距，需要安排下一次迭代( k = 2 k=2 k=2),直到状态价值函数收敛完成。 实例解析在这里使用刘全，黄志刚老师编著的《深度强化学习 ——原理、算法与pytorch实战》介绍策略评估中使用的确定性环境扫地机器人为例； 逻辑场景介绍确定状态集合
S
\mathcal S
S： 其中0号位置为充电桩，12号位置为障碍物(机器人无法到达12号位置)，19号位置是需要清扫的垃圾
状态集合
S
\mathcal S
S表示如下：
针对不同状态存在不同动作集合。
根据奖励类型，我们确定奖励集合： 策略评估过程求解我们将所有状态的状态价值函数进行初始化 → V i n i t ( s ) \to V_{init}(s) →Vinit(s),初始化结果如下：
设置 δ = 0.0001 \delta = 0.0001 δ=0.0001 ；折扣系数 γ = 0.8 \gamma = 0.8 γ=0.8； 下面执行第一轮策略评估：基于初始化价值函数，将所有的状态对应的第一轮价值函数进行求解；
以此类推，我们最终可以将所有状态进行更新，更新结束后，我们的第一轮策略评估正式结束。结果如下(黄色背景略)：
通过比对第一轮策略评估产生的价值函数和初始状态下价值函数的差距：
|
