上一节介绍了优先级遍历算法(反向聚焦)，本节将从规划执行时机的角度对算法进行解析。
在介绍后台规划之前，回顾一下动态规划算法的迭代过程：
动态规划算法如下表所示：
| 算法 | 基于随机MDP的状态价值函数 V π ( s ) V_\pi(s) Vπ(s)策略迭代算法 |
|---|---|
| 输入 (Input) | 初始策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)，动态特性函数 P P P，奖赏函数 r r r，折扣系数 γ \gamma γ |
| 初始化操作 (Initialization operation) | 1. 对
∀
s
∈
S
\forall s \in \mathcal S
∀s∈S，初始化状态价值函数
V
π
(
s
)
V_\pi(s)
Vπ(s)； 2. 阈值 θ \theta θ设置为一个较小的实数值； |
| 策略评估 (Policy Evaluation) | 1. repeat 对每一轮策略评估
τ
=
0
,
1
,
2
,
⋯
\tau=0,1,2,\cdots
τ=0,1,2,⋯ 2. d e l t a ← 0 delta \gets 0 delta←0 3. for 每个状态 s s s do： 4. v ← V π ( s ) v \gets V_\pi(s) v←Vπ(s) 5. V π ( s ) ← ∑ a ∈ A ( s ) π ( a ∣ s ) ∑ s ′ , r P ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] V_\pi(s) \gets \sum_{a \in \mathcal A(s)} \pi(a \mid s) \sum_{s',r}P(s',r \mid s,a)[r +\gamma V_\pi(s')] Vπ(s)←∑a∈A(s)π(a∣s)∑s′,rP(s′,r∣s,a)[r+γVπ(s′)] 6. d e l t a ← max ( d a l t a , ∣ v − V π ( s ) ∣ ) delta \gets \max(dalta,\mid v -V_\pi(s) \mid) delta←max(dalta,∣v−Vπ(s)∣) 7. end for 8. until d e l t a < θ delta < \theta delta<θ |
| 策略改进 (Policy Improvment) | 1. policy_stable = True 2. for 每个状态 s s s do： 3. old_policy ← π ( a ∣ s ) \gets \pi(a \mid s) ←π(a∣s) 4. Q ( s , a ) = ∑ s ′ , r P ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] Q(s,a) = \sum_{s',r}P(s',r \mid s,a)[r +\gamma V_\pi(s')] Q(s,a)=∑s′,rP(s′,r∣s,a)[r+γVπ(s′)] 5. max_action ← arg max a Q ( s , a ) \gets \mathop{\arg\max}\limits_{a} Q(s,a) ←aargmaxQ(s,a) max_count ← c o u n t ( max ( Q ( s , a ) ) ) \gets count(\max(Q(s,a))) ←count(max(Q(s,a))) 6. for 每个状态-动作对 ( s , a ′ ) (s,a') (s,a′) do： 7. if a ′ = = a' == a′== max_action then 8. π ( a ′ ∣ s ) = 1 / \pi(a'\mid s) = 1 / π(a′∣s)=1/(max_count) 9. else 9. π ( a ∣ s ) = 0 \pi(a\mid s) = 0 π(a∣s)=0 10. end if 11. end for 12. if old_policy ≠ π ( a ∣ s ) \neq \pi(a \mid s) =π(a∣s) then 13. policy_stable ← \gets ← False 14.end for 15.until policy_stable = True |
| 输出结果 | v ∗ = V , π ∗ = π v_* =V,\pi_* = \pi v∗=V,π∗=π |
我们重新观察策略迭代的整个执行过程，在策略评估(Policy Evaluation)部分，它通过模拟模型
P
(
s
′
,
r
∣
s
,
a
)
P(s',r \mid s,a)
P(s′,r∣s,a)产生所有可能发生的模拟经验；并根据模拟经验更新状态价值函数
V
π
(
s
)
V_\pi(s)
Vπ(s)；
V
π
(
s
)
=
∑
a
∈
A
(
s
)
π
(
a
∣
s
)
∑
s
′
,
r
P
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
(
s
′
)
]
V_\pi(s) = \sum_{a \in \mathcal A(s)} \pi(a \mid s) \sum_{s',r} P(s',r \mid s,a)[r + \gamma V_\pi(s')]
Vπ(s)=a∈A(s)∑π(a∣s)s′,r∑P(s′,r∣s,a)[r+γVπ(s′)]
总而言之，动态规划的策略评估过程关注的是当前状态
s
s
s；
在策略改进部分，它生成策略的关键点在于对状态集合
S
\mathcal S
S中的所有状态(包含当前状态
s
s
s 自身) 进行关注：
Q
(
s
,
a
)
=
∑
s
′
,
r
P
(
s
′
,
r
∣
s
,
a
)
[
r
+
γ
V
π
(
s
′
)
]
=
P
(
s
i
′
,
r
i
∣
s
,
a
)
[
r
i
+
γ
V
π
(
s
i
′
)
]
(
s
i
′
∈
S
)
想要得到上述的
Q
(
s
,
a
)
Q(s,a)
Q(s,a)结果，需要知道当前状态-动作对的所有模拟样本，这些样本同样需要从样本模型中产生：
r(s,a)表示奖励函数。
{
(
s
,
a
,
s
i
′
,
r
i
)
}
∣
s
i
′
∈
S
,
r
i
∈
r
(
s
,
a
)
\{(s,a,s'_i,r_i)\}|_{s'_i \in \mathcal S,r_i \in r(s,a)}
{(s,a,si′,ri)}∣si′∈S,ri∈r(s,a)
至此，我们发现，基于动态规划的策略迭代不仅关注当前状态，并且还在‘后台’处理多个状态的规划方法；
和上述思路相同的还有 D y n a − Q Dyna-Q Dyna−Q算法。 D y n a − Q Dyna-Q Dyna−Q在学习过程中的关键点表示如下：
可以看出， D y n a − Q Dyna-Q Dyna−Q的学习过程同样也是仅关注当前状态 s s s自身的情况；
继续观察规划过程：相比于动态规划， D y n a − Q Dyna-Q Dyna−Q的规划过程只是随机抽取 n n n组状态-动作对，并且可能存在无效的状态-动作对。但这并不影响 D y n a − Q Dyna-Q Dyna−Q不仅关注当前状态，并且还关注其他状态的思想。
我们称上述求解强化学习任务的思想为 后台规划。
这种思想更侧重于‘当前状态利用全局信息(其他随机状态甚至是所有状态)’给出当前动作，而不是仅靠当前状态自身。
无论是策略改进中遍历所有状态查找最优‘状态-动作价值函数’Q(s,a)还是Dyna-Q中随机选择状态-动作对(s,a)更新Q-Table都是一个道理。
观察后台规划的思想，我们可能产生这样一种思维逻辑：
当遇到某状态
s
s
s时，可能只是有一个模糊的策略方向，但是不管三七二十一，先按照当前策略把动作给选了，后面策略优化的部分再慢慢地让后台去做。
D
y
n
a
−
Q
Dyna-Q
Dyna−Q就表现得很明显了，学习过程先通过真实模型把真实样本先更新进
Q
−
T
a
b
l
e
Q-Table
Q−Table中，后续规划过程中的随机抽样再将
Q
−
T
a
b
l
e
Q-Table
Q−Table慢慢完善好。
决策时规划就和后台规划的 思维逻辑的侧重点 存在明显区别：
当遇到某状态
s
s
s时，先不着急选择动作，而是先将策略规划到当前最优，再通过该策略选择动作。
决策时规划思想衍生的一种经典逻辑：
仅知道当前状态 s s s,对于 s s s的每一个可选动作 a ∈ A ( s ) a \in \mathcal A(s) a∈A(s)；
通过样本模型
M
o
d
e
l
Model
Model得到下一时刻的状态价值函数；
以动作
a
1
a_1
a1为例:执行动作
a
1
a_1
a1后,可能得到
m
m
m个‘下一状态’
s
i
′
(
i
=
1
,
2
,
.
.
.
,
m
)
s'_i(i=1,2,...,m)
si′(i=1,2,...,m)，即
m
m
m个模拟样本。
{
(
s
,
a
1
,
s
i
′
,
r
i
)
}
∣
(
i
=
1
,
2
,
⋯
,
m
)
\{(s,a_1,s'_i,r_i)\}|_{(i=1,2,\cdots,m)}
{(s,a1,si′,ri)}∣(i=1,2,⋯,m)
每一个‘下一状态’
s
i
′
s'_i
si′都对应一个‘状态价值函数’
V
(
s
i
′
)
(
i
=
1
,
2
,
⋯
,
m
)
V(s'_i)(i=1,2,\cdots,m)
V(si′)(i=1,2,⋯,m)
a
1
a_1
a1的‘状态-动作价值函数'
Q
(
s
,
a
1
)
Q(s,a_1)
Q(s,a1)可以表示为:
Q
(
s
,
a
1
)
=
∑
i
=
1
m
P
(
s
i
′
,
r
i
∣
s
,
a
)
[
r
i
+
γ
V
(
s
i
′
)
]
Q(s,a_1) = \sum_{i=1}^m P(s'_i,r_i \mid s,a)[r_i + \gamma V(s'_i)]
Q(s,a1)=i=1∑mP(si′,ri∣s,a)[ri+γV(si′)]
以此类推，可以计算动作集合
A
(
s
)
\mathcal A(s)
A(s)中所有动作的状态-动作价值函数,得到一个集合：
{
Q
(
s
,
a
i
)
}
∣
a
i
∈
A
(
s
)
\{Q(s,a_i)\}|_{a_i \in \mathcal A(s)}
{Q(s,ai)}∣ai∈A(s)
从中选择一个最优
Q
(
s
,
a
i
)
Q(s,a_i)
Q(s,ai)对应的动作作为最优动作：
a
^
=
arg
max
a
i
{
Q
(
s
,
a
i
)
∣
a
i
∈
A
(
s
)
}
\hat a = \mathop{\arg\max}\limits_{a_i}\{Q(s,a_i)|_{a_i \in \mathcal A(s)}\}
a^=aiargmax{Q(s,ai)∣ai∈A(s)}
上述逻辑只是执行一次转移过程的逻辑(单步前瞻(one-step-ahead))，实际上甚至可以基于某条轨迹执行多次状态转移来考量和选择动作，但无论是哪种逻辑，决策时规划选择出的动作一定是当前状态下相对局部最优的动作。
这种规划并不一定仅执行一次状态转移(例如动态规划方法)，甚至会执行一条‘轨迹’。即被选择的动作会综合考量后续‘若干次状态转移’后的影响力。
假设某状态通过某种价值函数和策略已经得到得到一个 局部最优动作，在执行该动作后，我们可以 丢弃上述更新过程中的中间结果(策略、价值函数)。
原因在于状态空间很大的情况下，智能体很难在短时间重回同一个状态。
对于这句话的理解:
1. 以象棋为例，象棋自身就是‘决策时规划’的典型例子，换成我方下棋时，智能体可以停下来思考，不急于马上做出下棋动作;相反，执行完该动作后，一般情况下不会出现悔棋操作，自然不会像后台规划一样出现‘后置优化策略的情况’。
2. 言归正传，虽然‘象棋规则本身’是无法变化的，如马走日，象飞田。但无论我方还是对方，执行一次下棋动作后，环境都会发生变化。例如在某一步中跳了一次马，20步之后又想准备跳马时，此时虽然跳马的规则没变，但20步之后的环境(局势)发生很大变化，要向哪里跳收益最大，使用20步之前的策略可能并不是很有效了。
我们如何实现决策时规划这种选择的动作可以前瞻若干个状态转移过程 的要求？下一节将介绍——启发式搜索方法。
相关参考：
8.8 决策时规划
【强化学习】规划与学习-决策时规划
深度强化学习原理、算法与PyTorch实战——刘全、黄志刚编著