三、动态规划
满足条件：最优子结构，重复子问题
bellman递归方程可以用动态规划求解
Vlaue function记录子问题的解
Planning（规划）:
规划: 环境是已知或近似已知的，个体并不与环境发生实际的交互，而是利用其构建的模型进行计算，在此基础上改善其行为策略。
MDP认为已知所有的环境信息，所以可以用动态规划。
预测：求基于当前策略π的价值函数
input: MDP and
π
\pi
π
? MRP
Output: value function
控制：求最优价值函数和最优策略
input : MDP
Output: 最优路径value funtion最大和最优策略
迭代策略评估：
目的：计算给定策略下的状态价值函数。（k表示迭代测试，s’是后续状态，s是当前状态
方法：同步反向迭代，即策略和价值函数同步更新全部状态。在每次迭代过程中，对于第k+1次迭代，所有的状态s的价值用$v_k(s’)
计
算
并
更
新
该
状
态
第
!
[
[
公
式
]
]
(
h
t
t
p
s
:
/
/
w
w
w
.
z
h
i
h
u
.
c
o
m
/
e
q
u
a
t
i
o
n
?
t
e
x
=
k
计算并更新该状态第 ![[公式]](https://www.zhihu.com/equation?tex=k%2B1) 次迭代中使用的价值
计算并更新该状态第![[公式]](https://www.zhihu.com/equation?tex=kv_k(s)
，
中
s
’
是
s
的
后
继
状
态
。
最
终
收
敛
到
，中s’是s的后继状态。最终收敛到
，中s’是s的后继状态。最终收敛到v_{\pi}$。
v
k
+
1
(
s
)
=
∑
a
∈
A
π
(
a
∣
s
)
(
R
s
a
+
γ
∑
s
′
∈
S
P
s
s
′
a
v
k
(
s
′
)
)
v
k
+
1
=
R
π
+
γ
P
π
v
k
v_{k+1}(s)=\sum_{a \in A} \pi(a \mid s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right)\\ \mathbf{v}^{k+1}=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} \mathrm{v}^{k}
vk+1?(s)=a∈A∑?π(a∣s)(Rsa?+γs′∈S∑?Pss′a?vk?(s′))vk+1=Rπ+γPπvk
由策略(e.g.均一随机，贪心策略)计算状态价值，然后采用贪心策略得到最佳策略
k = 1 随机策略
k > 1 采取v更大的值移动
迭代时可以提前停止，不必完全等到收敛才停止
策略迭代：
目的：在当前策略上迭代计算价值函数，再根据价值函数贪婪地更新策略，如此反复多次，最终得到最优策略
π
?
\pi_*
π??和最优状态函数
v
?
v_*
v??。
策略评估evaluation -> 策略提升improvement：
策略提升：基于原来的策略采用贪心算法从而产生新的价值函数，并得到最优价值和最优策略
π
′
=
g
r
e
e
d
y
(
v
π
)
\pi' = greedy(v_{\pi})
π′=greedy(vπ?)
方法：每一步迭代先评估，更新value,然后再采用贪心，找到最优策略
收敛速率独立与初始值和采用的策略？
得到最优值的方式：
不断迭代更新value，直到收敛
提前到达某个点停止：不需要精确算出value，只需要得到最优的价值
价值迭代：
目的：不依赖任何策略，直接通过贝尔曼最优方程从前次迭代的价值函数中计算得到当次迭代的价值函数
（由于使用贝尔曼最优方程进行价值迭代时类似于贪婪地选择了最有行为对应的后续状态 的价值，因而价值迭代其实等效于策略迭代中每迭代一次价值函数就更新一次策略的过程）
bellman最优方程：
v
?
(
s
)
=
max
?
a
∈
A
(
R
s
a
+
γ
∑
s
′
∈
S
P
s
s
′
a
v
?
(
s
′
)
)
v_{*}(s)=\max _{a \in A}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)\right)
v??(s)=a∈Amax?(Rsa?+γs′∈S∑?Pss′a?v??(s′))
更新价值函数公式：
v
k
+
1
(
s
)
=
max
?
a
∈
A
(
R
s
a
+
γ
∑
s
′
∈
S
P
s
s
′
a
v
k
(
s
′
)
)
v_{k+1}(s)=\max _{a \in A}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right)
vk+1?(s)=a∈Amax?(Rsa?+γs′∈S∑?Pss′a?vk?(s′))
考虑两种情形：
- 个体知道环境的动力学特征的情形。
- 个体不知道环境动力学特征的情形。
两者的差别体现在:
前者从终止状态位置由进及远开始计算，每次迭代仅计算相关的状态的价值，而且一次计算即得到最优状态价值，
后者在每次迭代时要更新所有状态的价值。
PS：在价值迭代寻找最优策略的过程中，迭代过程中产生的状态价值函数不一定对应一个策略。
| Problem | Bellman Equation | Algorithm |
|---|
| Prediction | Bellman Expectation Equation | Iterative Policy Evaluation | | Control | Bellman Expectation Equation + Greedy Policy Improvement | Policy Iteration | | Control | Bellman Optimality Equation | Value Iteration |
迭代时间复杂度：
O
(
m
n
2
)
O(mn^2)
O(mn2)
总结：
使用动态规划求解最优策略和最优价值函数，包括2种方法。
策略评估+策略迭代，是基于bellman迭代方程和贪心策略求解价值函数，然后使用贪心更新策略，继续迭代直到收敛。
价值迭代，是基于bellman最优方程直接求解最优价值函数和最优策略，中间不依靠其他策略决策。注意，价值迭代需要对所有状态价值函数进行更新，并且中间状态价值并不对应一定某种策略（通过某种策略可以求的该价值）。
从动态规划本身性质来看，不需要知道各状态转移概率和具体奖励的函数，甚至不需要精确求出具体价值，而是使用采样产生的奖励和状态转移概率（自己设置）。但是由于基于迭代，需要知道所有后续状态的价值函数，所以对于状态数目较多的情况，计算量较大。
|