蒙特卡洛方法求解强化学习任务——基于试探性出发假设的蒙特卡洛控制
- 目录
- 蒙特卡洛控制与蒙特卡洛预测的区别
- 蒙特卡洛控制的具体迭代过程
- 场景设计
- 常规迭代过程
- 基于广义策略迭代(Generalized Policy Iteration)的迭代过程
- 基于试探性出发假设的蒙特卡洛控制
- 蒙特卡洛控制的合理性证明
- 基于试探性出发假设的蒙特卡洛控制算法
目录
上一节介绍了使用蒙特卡洛方法近似求解状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ(s,a)的优势和缺陷，并基于缺陷提出了试探性出发假设。本节将介绍如何基于试探性出发假设来解决蒙特卡洛控制问题。
蒙特卡洛控制与蒙特卡洛预测的区别
蒙特卡洛控制本质是基于蒙特卡洛方法的策略迭代。实际上，蒙特卡洛评估和蒙特卡洛控制的思路基本相同，它们都是通过对回报(Return)采样的方式对目标 → \to → 策略、价值函数进行更新的目的。主要区别如下：
- 蒙特卡洛预测：在给定策略 π \pi π的条件下，使用蒙特卡洛方法通过采样方式近似求解状态 s s s的状态价值函数 V π ( s ) V_\pi(s) Vπ(s)；
- 蒙特卡洛控制：其本质就是策略迭代。在动态规划部分中介绍过，策略迭代主要包含2个步骤：策略评估(Policy Evaluation,PE)，策略改进(Policy Improvement,PI)。策略评估是在给定策略 π \pi π的条件下，针对状态、动作二元组(s,a)，求解状态-动作价值函数 q π ( s , a ) q_\pi(s,a) qπ(s,a)；策略改进是在已知 q π ( s , a ) q_\pi(s,a) qπ(s,a)的基础上，通过贪心策略更新策略 π \pi π。
蒙特卡洛控制的具体迭代过程
场景设计
常规惯例，重复一遍场景内符号定义：
状态集合
S
\mathcal S
S和动作集合
A
\mathcal A
A定义如下：
S
=
{
s
1
,
s
2
,
.
.
.
,
s
m
}
A
=
{
a
1
,
a
2
,
.
.
.
,
a
n
}
\begin{aligned} \mathcal S & = \{s_1,s_2,...,s_m\} \\ \mathcal A & = \{a_1,a_2,...,a_n\} \\ \end{aligned}
SA={s1,s2,...,sm}={a1,a2,...,an}
我们需要针对
∀
s
∈
S
,
∀
a
∈
A
\forall s \in \mathcal S, \forall a \in \mathcal A
∀s∈S,∀a∈A，获取对应变量的状态-动作价值函数。状态-动作价值函数
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)表示如下：
q
π
(
s
,
a
)
=
(
q
π
(
s
1
,
a
1
)
q
π
(
s
1
,
a
2
)
⋯
q
π
(
s
1
,
a
n
)
q
π
(
s
2
,
a
1
)
q
π
(
s
2
,
a
2
)
⋯
q
π
(
s
2
,
a
n
)
⋮
⋮
⋱
⋮
q
π
(
s
m
,
a
1
)
q
π
(
s
m
,
a
2
)
⋯
q
π
(
s
m
,
a
n
)
)
q_\pi(s,a)= \begin{pmatrix} q_\pi(s_1,a_1) & q_\pi(s_1,a_2) & \cdots & q_\pi(s_1,a_n) \\ q_\pi(s_2,a_1) & q_\pi(s_2,a_2) & \cdots & q_\pi(s_2,a_n) \\ \vdots & \vdots & \ddots & \vdots \\ q_\pi(s_m,a_1) & q_\pi(s_m,a_2) & \cdots\ & q_\pi(s_m,a_n) \\ \end{pmatrix}
qπ(s,a)=⎝⎜⎜⎜⎛qπ(s1,a1)qπ(s2,a1)⋮qπ(sm,a1)qπ(s1,a2)qπ(s2,a2)⋮qπ(sm,a2)⋯⋯⋱⋯ qπ(s1,an)qπ(s2,an)⋮qπ(sm,an)⎠⎟⎟⎟⎞
以
q
π
(
s
1
,
a
1
)
q_\pi(s_1,a_1)
qπ(s1,a1)示例，求解该价值函数过程中，需要从若干情节中采样得到关于
(
s
1
,
a
1
)
(s_1,a_1)
(s1,a1)二元组的
N
N
N个样本。具体表示如下：
q
π
(
s
1
,
a
1
)
=
1
N
∑
i
=
1
N
[
G
t
(
i
)
∣
S
t
=
s
1
,
A
t
=
a
1
]
q_\pi(s_1,a_1) = \frac{1}{N} \sum_{i=1}^N [G_t^{(i)} \mid S_t = s_1,A_t = a_1]
qπ(s1,a1)=N1i=1∑N[Gt(i)∣St=s1,At=a1]
若将所有的状态-动作二元组全部求解完成，可以得到完整的近似解
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)。这里以策略为单位，设定
N
π
N_\pi
Nπ为近似求解
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)过程中从若干情节中采样得到的关于策略
π
\pi
π中所有二元组的样本，具体表示如下：
q
π
(
s
,
a
)
=
1
N
π
∑
i
=
1
N
π
[
G
t
(
i
)
∣
S
t
=
s
,
A
t
=
a
]
q_\pi(s,a) = \frac{1}{N_{\pi}} \sum_{i=1}^{N_{\pi}} [G_t^{(i)} \mid S_t = s,A_t = a]
qπ(s,a)=Nπ1i=1∑Nπ[Gt(i)∣St=s,At=a]
常规迭代过程
常规情况下，具体迭代过程示例如下：
- 初始化策略
π
0
\pi_0
π0，基于策略
π
0
\pi_0
π0使用蒙特卡洛方法近似求解
q
π
0
(
s
,
a
)
q_{\pi_0}(s,a)
qπ0(s,a)(策略评估)；
q π 0 ( s , a ) = 1 N π 0 ∑ i = 1 N π 0 [ G t ( i ) ∣ S t = s , A t = a ] q_{\pi_0}(s,a) = \frac{1}{N_{\pi_0}} \sum_{i=1}^{N_{\pi_0}} [G_t^{(i)} \mid S_t = s,A_t = a] qπ0(s,a)=Nπ01i=1∑Nπ0[Gt(i)∣St=s,At=a] - 基于已求解的
q
π
0
(
s
,
a
)
q_{\pi_0}(s,a)
qπ0(s,a)，通过贪心策略对策略
π
0
\pi_0
π0进行策略改进；
π 1 ( s ) = arg max a q π 0 ( s , a ) = { 1 i f a = arg max a q π 0 ( s , a ) 0 e l s e \begin{aligned} \pi_1(s) &= \mathop{\arg\max}\limits_{a}q_{\pi_{0}}(s,a) \\ &= \left\{ \begin{array}{ll} 1\quad if \quad a= \mathop{\arg\max}\limits_{a}q_{\pi_0}(s,a)\\ 0\quad else \end{array} \right. \end{aligned} π1(s)=aargmaxqπ0(s,a)={1ifa=aargmaxqπ0(s,a)0else - 重复执行上述两个步骤，直到获取最优策略
π
∗
(
s
)
\pi_*(s)
π∗(s)和最优状态-动作价值函数
q
∗
(
s
,
a
)
q_*(s,a)
q∗(s,a)。
π 0 → P o l i c y E v a l u a t i o n q π 0 ( s , a ) → P o l i c y I m p r o v e m e n t π 1 ( s ) → . . . → P o l i c y I m p r o v e m e n t π ∗ ( s ) → P o l i c y E v a l u a t i o n q ∗ ( s , a ) \pi_0 \xrightarrow{Policy Evaluation} q_{\pi_0}(s,a) \xrightarrow{Policy Improvement} \pi_1(s) \xrightarrow{}...\xrightarrow{Policy Improvement}\pi_*(s) \xrightarrow{Policy Evaluation}q_*(s,a) π0PolicyEvaluation qπ0(s,a)PolicyImprovement π1(s) ...PolicyImprovement π∗(s)PolicyEvaluation q∗(s,a)
仔细观察上述流程，在常规方法迭代过程中，每次策略评估都需要采集大量样本来近似求解 q π ( s , a ) q_\pi(s,a) qπ(s,a)，这种方法的效率极低。
基于广义策略迭代(Generalized Policy Iteration)的迭代过程
在动态规划求解强化学习任务——价值迭代一节中,我们介绍了广义策略迭代(Generalized Policy Iteration,GPI)。广义策略迭代中的异步更新方法和增量更新方式可以缩短策略评估过程中的计算时间，提高迭代速度；
具体流程如下：
- 我们在策略评估过程中只走一步——只选择一段情节作为样本而不是整个情节集合；假设该段情节中包含的(状态、动作)二元组并没有包含策略
π
\pi
π中全部的二元组；
常规思路：一段情节只能执行[从状态开始到结束]的其中一种过程，也可能存在其他过程，因此这种假设更加符合真实环境。
并且该情节中产生的二元组集合内部可能存在重复(有的二元组 ( s i , a j ) (s_i,a_j) (si,aj))对应回报样本可能有若干个，有的可能只有一个；
状态转移过程不以智能体主观意志的变化而变化，因此存在一定随机性。 - 在步骤1的条件下,采用增量更新方法更新对应二元组位置的
q
π
(
s
,
a
)
q_\pi(s,a)
qπ(s,a)；
示例：假设在 π k ( s ) \pi_k(s) πk(s)策略的条件下，迭代某一条情节中共获取了2个关于 ( s i , a j ) (s_i,a_j) (si,aj)二元组的回报；
G t ( s i , a j ) ( 1 ) , G t ( s i , a j ) ( 2 ) G_{t(s_i,a_j)}^{(1)},G_{t(s_i,a_j)}^{(2)} Gt(si,aj)(1),Gt(si,aj)(2)
基于上一时刻的 q π k − 1 ( s i , a j ) q_{\pi_{k-1}}(s_i,a_j) qπk−1(si,aj)，更新当前时刻的状态-动作价值函数 q π k ( s i , a j ) q_{\pi_k}(s_i,a_j) qπk(si,aj)：
q π k ( s i , a j ) = q π k − 1 ( s i , a j ) + 1 2 [ ( G t ( s i , a j ) ( 1 ) − q π k − 1 ( s i , a j ) ) + ( G t ( s i , a j ) ( 2 ) − q π k − 1 ( s i , a j ) ) ] q_{\pi_k}(s_i,a_j) =q_{\pi_{k-1}}(s_i,a_j) + \frac{1}{2}[(G_{t(s_i,a_j)}^{(1)} - q_{\pi_{k-1}}(s_i,a_j)) + (G_{t(s_i,a_j)}^{(2)} - q_{\pi_{k-1}}(s_i,a_j))] qπk(si,aj)=qπk−1(si,aj)+21[(Gt(si,aj)(1)−qπk−1(si,aj))+(Gt(si,aj)(2)−qπk−1(si,aj))]
关于 ( s i , a j ) (s_i,a_j) (si,aj)二元组的状态-动作价值函数部分更新结束，同理，将该情节中产生的所有样本全部进行相应更新，最终得到 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a)。 - 由于在步骤1中特意强调没有包含策略 π \pi π中全部的二元组，因此我们实际上并没有完全将 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a)中的所有元素全部更新一遍；但这并不影响我们的迭代过程。这正是广义策略迭代的优势：在常规迭代过程中可能需要极大数量的情节才能迭代一次 → \to → 每次只需要一个情节即可完成本次迭代。
- 我们直接用步骤3中“未完全更新”的结果直接进行策略改进 → \to → 更新下一时刻策略 π k + 1 ( s ) \pi_{k+1}(s) πk+1(s)，从而实现循环过程。
基于试探性出发假设的蒙特卡洛控制
蒙特卡洛控制的合理性证明
上面介绍了针对策略评估迭代过程中使用大量情节作为样本的问题，使用广义策略迭代解决了该问题。我们将目光转移到策略改进部分。策略改进公式如下：
π
k
+
1
(
s
)
=
arg
max
a
q
π
k
(
s
,
a
)
=
{
1
i
f
a
=
arg
max
a
q
π
k
(
s
,
a
)
0
e
l
s
e
\begin{aligned} \pi_{k+1}(s) &= \mathop{\arg\max}\limits_{a}q_{\pi_{k}}(s,a) \\ &= \left\{ \begin{array}{ll} 1\quad if \quad a= \mathop{\arg\max}\limits_{a}q_{\pi_k}(s,a)\\ 0\quad else \end{array} \right. \end{aligned}
πk+1(s)=aargmaxqπk(s,a)={1ifa=aargmaxqπk(s,a)0else
我们如何能够保证策略改进产生的新的策略
π
k
+
1
(
s
)
\pi_{k+1}(s)
πk+1(s)优于
π
k
(
s
)
\pi_{k}(s)
πk(s)？
证明过程如下：
已知：
π
k
+
1
(
s
)
=
arg
max
a
q
π
k
(
s
,
a
)
\pi_{k+1}(s) = \mathop{\arg\max}\limits_{a}q_{\pi_{k}}(s,a)
πk+1(s)=aargmaxqπk(s,a)
则有：
q
π
k
[
s
,
π
k
+
1
(
s
)
]
=
q
π
k
[
s
,
arg
max
a
q
π
k
(
s
,
a
)
]
=
max
a
q
π
k
(
s
,
a
)
\begin{aligned} q_{\pi_k}[s,\pi_{k+1}(s)] &= q_{\pi_k}[s,\mathop{\arg\max}\limits_{a}q_{\pi_{k}}(s,a)] \\ &= \mathop{\max}\limits_{a}q_{\pi_k}(s,a) \end{aligned}
qπk[s,πk+1(s)]=qπk[s,aargmaxqπk(s,a)]=amaxqπk(s,a)
又因为最大值
≥
\geq
≥ 期望值(贝尔曼最优方程一节有介绍)，有：
max
a
q
π
k
(
s
,
a
)
≥
∑
a
π
k
(
a
∣
s
)
q
π
k
(
s
,
a
)
=
V
π
k
(
s
)
\begin{aligned} \mathop{\max}\limits_{a}q_{\pi_k}(s,a) & \geq \sum_{a} \pi_k(a \mid s)q_{\pi_k}(s,a) = V_{\pi_k}(s) \end{aligned}
amaxqπk(s,a)≥a∑πk(a∣s)qπk(s,a)=Vπk(s)
最终整理得：
q
π
k
[
s
,
π
k
+
1
(
s
)
]
≥
V
π
k
(
s
)
q_{\pi_k}[s,\pi_{k+1}(s)] \geq V_{\pi_k}(s)
qπk[s,πk+1(s)]≥Vπk(s)
由策略改进定理可知：
V
k
+
1
(
s
)
≥
V
k
(
s
)
V_{k+1}(s) \geq V_{k}(s)
Vk+1(s)≥Vk(s)
即：策略
π
k
+
1
(
s
)
\pi_{k+1}(s)
πk+1(s)优于策略
π
k
(
s
)
\pi_{k}(s)
πk(s)。
这一证明保证了蒙特卡洛控制算法可以收敛到最优状态-动作价值函数
q
∗
(
s
,
a
)
q_*(s,a)
q∗(s,a)和最优策略
π
∗
\pi_*
π∗。
基于试探性出发假设的蒙特卡洛控制算法
基于试探性出发假设的蒙特卡洛控制算法本质上就是基于广义策略迭代的蒙特卡洛控制(策略迭代)过程。在每一个情节结束后，使用观测到的回报结果进行策略评估，并对上一个状态进行策略改进。
具体算法表示如下：
| 输入 | 待评估的确定策略： π ( a ∣ s ) \pi(a \mid s) π(a∣s) |
|---|---|
| 初始化操作 (Initialization operation) | 1. 对
∀
s
∈
S
,
a
∈
A
(
s
)
\forall s \in \mathcal S,a \in \mathcal A(s)
∀s∈S,a∈A(s),初始化
Q
(
s
,
a
)
∈
R
Q(s,a) \in\mathbb R
Q(s,a)∈R； 2.对 ∀ s ∈ S , a ∈ A ( s ) \forall s \in \mathcal S,a \in \mathcal A(s) ∀s∈S,a∈A(s),状态、动作二元组 ( s , a ) (s,a) (s,a)被统计次数 c o u n t ( s , a ) = 0 count(s,a) = 0 count(s,a)=0 |
| 算法过程 (Algorithmic Process) | 1. repeat 对每一个情节：
k
=
0
,
1
,
2
,
.
.
.
k=0,1,2,...
k=0,1,2,... 2. 以非0概率随机选取初始状态、动作二元组( S 0 , A 0 S_0,A_0 S0,A0) 3. 根据策略 π ( s ) \pi(s) π(s),从初始二元组( S 0 , A 0 S_0,A_0 S0,A0)开始，生成一个情节序列： S 0 , A 0 , R 1 , S 1 , A 1 , R 2 , . . . , S T − 1 , A T − 1 , R T , S T S_0,A_0,R_1,S_1,A_1,R_2,...,S_{T-1},A_{T-1},R_T,S_T S0,A0,R1,S1,A1,R2,...,ST−1,AT−1,RT,ST 4. G ← 0 \gets 0 ←0 5. for 情节中的每一步(时刻) t = T − 1 → 0 t = T - 1 \to 0 t=T−1→0 do： 6. G ← γ G + R t + 1 G \gets\gamma G + R_{t+1} G←γG+Rt+1 7. if ( S t , A t ) ∉ { S 0 , A 0 , S 1 , . . . , S t − 1 , A t − 1 } (S_t,A_t) \notin \{S_0,A_0,S_1,...,S_{t-1},A_{t-1}\} (St,At)∈/{S0,A0,S1,...,St−1,At−1} then 8. c o u n t ( S t , A t ) ← c o u n t ( S t , A t ) + 1 count(S_t,A_t) \gets count(S_t,A_t) + 1 count(St,At)←count(St,At)+1 9. Q ( S t , A t ) ← Q ( S t , A t ) + 1 c o u n t ( S t , A t ) ( G − Q ( S t , A t ) ) Q(S_t,A_t) \gets Q(S_t,A_t) + \frac{1}{count(S_t,A_t)}(G - Q(S_t,A_t)) Q(St,At)←Q(St,At)+count(St,At)1(G−Q(St,At)) 10. end if 11. π ( S t ) ← arg max a Q ( S t , a ) \pi(S_t) \gets \mathop{\arg\max}\limits_{a} Q(S_t,a) π(St)←aargmaxQ(St,a) 12. end for |
| 输出结果 | π ∗ = π \pi_* = \pi π∗=π |
即便可以通过试探性出发假设来弥补无法全部访问到所有状态、动作二元组 的缺陷；
但是更普遍的解决方法是保证智能体能够持续不断地选择所有可能选择的动作。这种方法被称为非试探性出发假设的蒙特卡洛控制方法。该方法分为同轨策略方法和离轨策略方法两种。
下一节将针对试探性出发假设带来的问题，我们将介绍如何使用非试探性出发假设的蒙特卡洛控制方法绕过该假设的严苛条件，来实现对所有有效的状态-动作二元组全部访问的目标。
相关参考：
【强化学习】蒙特卡洛方法-基于试探性出发假设的MC控制
深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著
