强化学习Chapter4——两个基本优化算法（1）
上一节导出了状态价值函数的贝尔曼方程以及最优状态价值函数：
\[\begin{aligned} V^\pi(s) &=E_{a\sim \pi,s’\sim P}[r(s,a)+\gamma V^\pi(s‘)]\\ &= \sum_{a}\pi(a|s_t)(r(s_t,a)+\gamma \sum_{s'}p(s'|s_t,a)V^\pi(s'))\\ V^*(s)&=\max_a(r(s,a)+\sum_{s'}p(s'|s,a)V^*(s')) \end{aligned} \]之前也讲到，我们的优化目标，是得到最优的状态价值 \(V^*(s)\) 与相应的策略 \(\pi^*\)。结合贝尔曼方程的递归形式，其实容易看出，在给定策略 \(\pi\) 的前提下，可以通过一种类似动归的迭代方法，逼近最优解。本节将依据此思路，提出两个求解 \(V^*\) 以及 \(\pi^*\) 的基本优化方法——策略迭代算法（policy iteration）、价值迭代算法（value iteration）。
O、introduction
根据贝尔曼方程能够导出类似动态规划的迭代方程，因而可以利用动态规划方法来求最优解。然而，在动规视角下，除了自变量外，都应当是确定量，这意味着状态转移函数 \(s_{t+1}=f(s_t,a)\) 和奖励函数 \(r_t=R(s_t,a_t)\) 均已知。换句话说，局部的状态迁移所有信息透明，即第一节框架图中的 Environment 是一个白盒环境。当然这种特点也是该类算法的局限之处，在现实世界中的问题往往没有这么明确的信息。但是，其算法思想依然是理解后续其他强化学习算法的关键所在。
一、策略迭代算法（policy iteration）
策略迭代算法，利用状态价值函数的贝尔曼方程，尽管方程是状态价值的迭代，但本算法的核心却是策略的不断迭代调优。首先假设一个初始策略 \(\pi^0\)，通过贝尔曼方程生成关于这个策略 \(\pi^0\) 的评估，依据评估结果，调优 \(\pi^0\) 到 \(\pi^1\) ，继续生成评估，由此迭代。简单来讲，策略迭代算法包含俩个步骤：策略评估（policy evaluation）、策略提升（或策略调优，policy improvement）。
1、策略评估（policy evaluation）
评估结果是用于调优策略的，那么如何衡量一个策略的优劣呢？自然要谈到期望回报 Return，而要衡量这个 Return 自然要涉及 \(V^\pi\) 或 \(Q^\pi\) 的计算。因而我们期望可以计算获得 \(V^\pi\) 或者其估计值，成为衡量策略 \(\pi\) 的指标。
\[V^\pi(s)=\sum_a\pi(a|s)(r(s,a)+\gamma\sum_{s'}p(s'|s,a)V^\pi(s')) \]关键在于如何利用贝尔曼方程，得出较为准确的 \(V^\pi\) 估计。具体而言，\(V^\pi\) 是有一个初始化值的（譬如初始化为0，即 \(V^\pi_0(s)=0, \forall\ s\)），每次迭代时可以得到一个类似数列递推，此处暂将 \(V^\pi_k\) 简写为 \(V_k\)：
\[V_{k+1}(s)=\sum_a\pi(a|s)(r(s,a)+\gamma\sum_{s'}p(s'|s,a)V_k(s')) \]贝尔曼方程保证了 \(V^\pi\) 是上式的不动点，一个最为简单的想法是，不断迭代上式，得到数列 \(\{V_k\}\) 能够收敛到不动点 \(V^\pi\). 事实上可以证明收敛成立（虽然我现在还不知道咋证，但我先偷偷想想咋证）。在实际应用中，往往迭代到 \(||V_{k+1}-V_k|| < \epsilon\) 就可以终止了。于是，针对一个固定的策略 \(\pi\)，我们能通过迭代的方式解出贝尔曼方程的解 \(V^\pi\)，从而能够将该价值函数作为标准，调优策略 \(\pi\).
2、策略提升（policy improvement）
由最初的思路可知，策略提升的任务是调优策略 \(\pi^k\) ，使 \(k\rightarrow \infin\) 时，\(\pi^k\rightarrow \pi^*\). 而从策略评估可知，状态价值函数，可以作为策略评估的标准，下面给出关于策略优劣更准确的解释，并推出与状态价值函数的关系：
\[\begin{aligned} V^\pi(s)&\le Q^\pi(s,\pi'(s))\\ &=E_{\pi'}[r_t+\gamma V^\pi(S_{t+1})|S_t=s]\\ &\le E_{\pi'}[r_t+\gamma Q^\pi(S_{t+1},\pi'(S_{t+1}))|S_t=s]\\ &=E_{\pi'}[r_t+\gamma r_{t+1} + \gamma^2 V^\pi(S_{t+2})|S_t=s]\\\ &...\\ &\le E_{\pi'}[r_t+\gamma r_{t+1}+\gamma^2 r_{t+2}+\gamma^3r_{t+3}+...|S_t=s]\\ &=V^{\pi'}(s) \end{aligned} \]\[《\ 参考公式》\\ V^\pi(s)=E_{\tau\sim\pi}[R(\tau)|s_0=s]\\ Q^\pi(s,a)=E_{\tau\sim\pi}[R(\tau)|s_0=s,a_0=a]\\ Q^\pi(s,a) = r(s,a) + \gamma V^\pi(s') \\ \]\[\begin{aligned} Q^\pi(s,\pi'(s))&=E_{a\sim\pi'}[Q^\pi(s,a)]\\ &=E_{a\sim\pi'}[r(s,a)+\gamma V^\pi(s')]\\ &=E_{a\sim\pi'}[r(S_t,a)+\gamma V^\pi(S_{t+1})|S_t=s]\\ &=E_{\pi'}[r_t+\gamma V^\pi(S_{t+1})|S_t=s] \end{aligned} \]如果策略 \(\pi'\) 优于 \(\pi\)，当前仅当对所有状态 \(s\)，按照策略 \(\pi'\) 得到的动作都会使 \(V^\pi(s)\) 不减，即 \(Q^\pi(s,\pi'(s))>V^{\pi}(s)\). 从而有：
上述公式表明，只需要使新策略 \(\pi'\) 贪心地选择价值更高的动作，保证 \(Q^\pi(s,\pi'(s)) \ge V^\pi(s)\) ，可以保证 \(V^\pi\) 的单调性。具体而言，策略提升阶段，需要遍历每一个状态，贪心地使新策略选择即时价值最高的动作，就能得到一个不劣于原策略的新策略。同时由于 \(V^\pi\) 有界是显然的，所以根据单调有界定理，\(\{V^{\pi^k}\}\) 收敛，但是问题在于，是否收敛到 \(V^*\) ？答案是肯定的，这一点将单独给出一节进行证明。
二、伪代码
def policy_eval(policy):
"""策略评估"""
while delta > theta:
delta = 0
for s in S:
v = copy(V) # 暂存旧的 V
V(s) = r(s, policy(s)) + gamma * E(s_next) # 迭代新的 V
delta = max(delta, |v - V(s)|)
return V
def policy_impro(old_policy):
"""策略提升"""
for s in S: # 迭代每一个状态
for a in A(s): # 迭代每一个状态对应的所有动作
max_q = max(max_q, Q(s,a))
single_impro(policy, max_q, s, a)
return policy
def policy_inter：
"""策略迭代"""
while True:
policy_eval()
old_policy = copy(policy)
new_policy = policy_impro(policy)
if old_policy == new_policy: break