Lecture 5. Search
搜索问题包含：
- \(S\)：状态空间。
- \(s_{st}\)：初始状态。
- \(\mathrm{Actions}(s)\)：可能的动作集合。
- \(\mathrm{Succ}(s, a)\)：执行动作的后继状态。
- \(\mathrm{Cost}(s, a)\)：非负的执行动作代价（和之前的动作无关？Question）。
- \(\mathrm{IsEnd}(s)\)：目标测试。
解 solution：一个动作序列，将初始状态转换为目标状态。
Tree Search
Uninformed Search
边缘 fringe：进入队列但未被执行的动作序列的集合。
设 \(g(x)\) 表示到状态 \(x\) 的总代价。
Uninformed Cost Search
边缘按 \(g(x)\) 从小到大排序。算法不需要更多的外部信息（类似 ZKP 的 auxiliary input）。
Informed Search
启发式函数 heuristic \(h(x)\) 是到目标状态的估计距离，供搜索时参考。
Greedy Search
边缘按 \(h(x)\) 从小到大排序。
这节课的核心之一是 A* Search 算法：边缘按 \(f(x) = g(x) + h(x)\) 从小到大排序。一些注意点：
- 只有在扩展目标的时候才能停止，而不是发现目标。
- 为了防止较差的路径在考虑 \(g(x) + h(x)\) 时优于较好的路径，\(h(x)\) 不能超过到目标的真实距离 \(h ^ *(x)\)，即 \(h\) 是 可接受的 admissible：\(0\leq h\leq h ^ *\)。
Theorem
对树形搜索，只要 \(h\) 可接受，则 A* 正确。
Proof
假设没有搜到最优解 \(A\)，搜到了 \(B\) 且 \(g(B) > g(A)\)，则最优路径上有一个点 \(x\) 没有扩展。因为代价非负，所以 \(f(x)\leq g(A) < g(B) = f(B)\)，矛盾。第一个不等号是因为 \(h\) 可接受。
Graph Search
A*
树形搜索会忘掉任何历史记忆，在图上表现很差。维护哪些点已经扩张过了（closed set），只扩张没有被扩张的点。
对于 A*，之前正确是因为不优的路径会在某个 \(x\) 停下，扩展更优的路径，但如果最优路径也经过 \(x\)，则因为一个点只扩展一次，会导致错误。
称 \(h\) 是 一致 consistent 的，若对任何 \(x, a\)，
也就是 \(h\) 要满足三角形不等式，使得 \(f\) 不降。这样如果不优的路径扩展了 \(x\)，则最优路径一定不会经过 \(x\)：A* 会按照 \(f\) 从小到大遍历所有状态。
Theorem
对图搜索，只要 \(h\) 一致，则 A* 正确。
- A* 是利用已知启发式信息的最优算法。没有其它一般性的算法能够遍历更少的点并求出最优解。
- \(h\) 一致，则 \(h\) 可接受。
Create Heuristics
A* 的关键在于设计启发式函数。
设计启发函数的常用手段是放松限制（这会使得边权变小，或增加新的边），将复杂问题拆成很多独立的简单子问题：
- 路径规划问题，用欧拉距离。
- 吃豆人问题，用曼哈顿距离（注意：越接近实际代价则效果越好）。
- 八数码问题，数码可以重叠。
原问题的 松弛 relaxation 满足
给定松弛问题 \(P ^ j\)，定义 松弛启发函数 relaxed huristic
Theorem
松弛启发函数是一致的。
Theorem
若 \(h_1, h_2\) 一致，则 \(\max(h_1, h_2)\) 一致。
Path Planning
平面上有一些障碍物，求起点到终点的最短距离。
将平面离散化成网格，只在相邻格点之间连线。如果没有找到，则将有障碍的格子进一步细分。
定义一个算法是 决策完备的 resolution complete，若有路径则能在有限时间内找到，且没有路径则能在有限时间内停止。上面这个算法不满足后者。
- A* smoothing：允许不相邻的两个格点连线，只要中间没有障碍。
- Theta*：gy 的神秘算法，不知道意义何在。
Theorem
若所有障碍都是多边形，则最优路径一定是只经过多边形顶点的折线。
Proof
假设在非多边形顶点处弯曲，则画小圆并连接交点得到更优路径。
Weighted A*
令 \(f = g + \eps h\)，其中 \(\eps > 1\)，则找到的解不超过最优解的 \(\eps\) 倍。时间与正确性的权衡。
Lecture 6. MDPs
马尔科夫决策过程 Markov decision process。
本质上是期望动态规划。
Introduction & Definition
Definition
一个 MDP 包含：
- 状态集合 \(s\in S\)。
- 动作集合 \(a\in A\)。
- 转移函数 \(T(s, a, s')\) 描述了 \(\pr(s'\mid s, a)\)。
- 奖励函数 \(R(s)\)。有时可以是 \(R(s, a)\) 或 \(R(s, a, s')\)。奖励是人类的先验知识，越精确越好。
- 起始状态（分布）。
- 终止状态（可能有）。
MDP 是非确定性的搜索问题。
Assumptions
MDP 有以下假设：
- 转移函数仅和当前状态有关，和历史状态 history independence、时间无关 stationary dynamics。称为 马尔科夫性 Markovian。
- 转移的过程是可观测的 full observability。
- 奖励是关于状态的确定性函数 state-dependent reward。
Solution
MPD 的解决方案是什么？由于随机性，我们可能移动到任何一个状态。
MPD 的解决方案是一组 策略 policy，指定了在每个状态时选择的动作（分布）。
当策略和时间有关时，称为 非平稳策略 non-stationary policy：\(\pi : S\times T\to A\)。\(t\) 是剩余步数而非已经走的步数。
为什么是剩余步数？因为我们只关心接下来的奖励，所以关心还剩多少步。
如果可以无限地执行动作，则策略只和状态有关，称为 平稳策略 stationary policy。容易证明这一点。
Value Function
如何衡量一个策略的好坏？
价值函数 \(V : S\to \R\) 将每个状态映射到实数，表示对应状态的价值。
\(V_\pi(s)\) 表示在策略 \(\pi\) 下状态 \(s\) 的价值。
最常见的定义是 无限时间折扣价值 infinite horizon discounted value：
其中 \(\g\) 称为 折扣因子 discount factor。
价值函数满足一个很重要的方程。
Bellman Equation
\[V_\pi(s) = R(s) + \g \sum_{s'\in S} \pr(s'\mid s, \pi) V_\pi(s'). \]
Optimal Policy
在给定价值函数下的 最优策略 就是其它任何策略的任何状态的价值不高于 \(\pi\) 的对应状态的价值。MDP 的目标是学习最优策略。
设 \(V ^ *\) 是最优策略对应的价值函数，则有
Bellman Optimality Equation
\[V ^ *(s) = R(s) + \g \max_{a\in A}\sum_{s'\in S}\pr(s'\mid s, a)V ^ *(s'). \]且最优策略就是对每个 \(s\) 取到最大值的 \(a\)。
Value Iteration
Algorithm
从任意 \(\hat V\) 开始，用最优方程更新，不断迭代，总能得到最优解。
为什么？一轮迭代可以看成 \(B: V\to V'\)，容易证明 \(B\) 是压缩。
设奖励函数的取值在 \([0, R_\max]\)，则显然 \(V ^ *(s) \leq \fr {R_\max} {1 - \g}\)。由压缩映射的性质，迭代 \(k\) 次之后有
当然，收敛还需要考虑次优策略和最优策略之间的距离（否则可能收敛到更差的策略），很难估计。
何时停止？由压缩映射的性质：
Greedy Solution
得到近似值函数之后，贪心地用 一步前瞻 one-step lookahead
得到策略。设 \(V_\pi\) 为对应值函数，则
证明略。
可以令 \(\eps\) 为我们想要的精度。当 \(\eps\) 足够小的时候，\(\pi\) 就是最优策略。
虽然值迭代算法可以得到最优策略，但其单步和收敛速度都太慢了！
Policy Iteration
在值迭代算法的迭代过程中，很多状态的策略是不变的。
Algorithm
从任意 \(\hat\pi\) 开始，算出 \(V_{\hat \pi}\) 之后用一步前瞻贪心得到新的策略 \(\pi\)。如果策略不变，则停止。
如何算 \(V_{\hat \pi}\)？解线性方程组。
可以证明策略迭代也会收敛到最优策略：如果不是最优策略，则策略一定变化，再证明迭代是压缩。
策略迭代轮数和 \(O(n)\) 差不多（经验之谈），但证明多项式上界仍是开放问题。
解线性方程组算 \(V_{\hat \pi}\) 太慢了，用值迭代算，称为 改良策略迭代 modified policy iteration。
任何用策略算价值，再用价值算策略的方法（和具体怎么算无关，和精度无关）称为 广义策略迭代 generalized policy iteration。
Principle of Optimality
最优性原则指出：任何最优策略都可以分成一步的最优策略和其后继的最优策略。
\(V_\pi(s)\) 最优当且仅当 \(\pi\) 在任何 \(s\) 可达的 \(s'\) 都取到了最优。
Approximations
Asychronous DP
同步 DP 在一轮扫完之后才更新，而异步 DP 按一定顺序更新。如果保证每个状态之后还会被更新，则收敛。
比如 Bellman-Ford 和 SPFA！
一些异步 DP 算法。
- 就地 in-place：只维护值函数数组。
- 优先级 prioritized：先更新 Bellman 误差更大的状态。更新时更新前驱的 Bellman 误差。
- 实时 real-time：不断尝试从起始状态移动，只更新经过的状态。
Sample Backups
对于规模较大的问题，采用 全宽备份 full-width backup（也就是更新）导致每个动作和后继状态都被考虑，代价过高。
采样备份 用采样的奖励和转移代替奖励函数和转移矩阵。这个方法是 模型自由 model-free 的，即不需要关于 MDP 的先验知识。
Approximate DP
状态太多无法存储具体的价值函数？用其它函数拟合价值函数，如线性映射、神经网络等。
拟合值迭代 fitted value iteration：采样要备份的状态 \(\tilde S\)，用更新之后的结果训练新的拟合函数。
Extensions
Infinite MDP
如果空间连续，则用少量的函数和参数拟合 \(V_\pi\)：线性二次型 linear quadratic model, LQR。
如果时间连续，则需要求解偏微分方程：HJB 方程。
Partially Observable MDP
执行动作后只能获得部分关于状态的信息 \(o\) 和奖励 \(R\)，而无法得知具体处于哪个状态。
做法是维护 信念状态 belief state：对给定历史，当前处于每个状态的概率。
Ergodic MDP
常返 ergodic MDP：任何策略导出的 Markov 链都是常返的。
对任意 \(\pi\)，常返 MDP 存在和初始状态无关的平均单步收益
值函数可以用超出平均收益的总和表示（不一定发散，因为平均收益趋于 \(\rho ^ \pi\)）。\(\tilde v_\pi(s)\) 表示从 \(s\) 出发的额外收益
有对应的 Bellman 方程
没太明白 \(t\) 是何意味，应该可以当成 \(t = 0\) 来理解吧。
Lecture 7. Reinforcement Learning I
给定 MDP，但没有转移函数 \(T\) 和奖励函数 \(R\)：我们不知道哪些状态是好的，也不知道每个动作会干嘛。
“没有奖励函数” 其实是指没有衡量 \(R\) 的数学模型，但每次执行动作后可以获得实时奖励，也就是只有做了才知道能获得什么。
被动学习 passive learning 是给定策略，学习每个状态的价值（类比策略评估），通常作为主动学习的一部分。主动学习 active learning 是寻找最优策略。
基于模型 model-based 的 RL 是先学习环境模型（\(T, R\)），再用模型做规划。而 免模型 model-free 的 RL 是直接学习值函数 \(Q(s, a)\) 或策略 \(\pi\)，不显示学习模型。
Passive Learning
给一个策略，希望衡量其价值。
Monte Carlo
免模型。
最简单的一个，就是直接从起点出发沿着策略移动，多次试验取平均。用一个状态的 奖励累计 reward to go 作为其价值的估算。
收敛很慢，且没有好好利用 Bellman 方程。
Adaptive Dynamic Programming (ADP)
基于模型。
Bellman 方程需要知道 \(R\) 和 \(T\)，所以我们也是先根据策略模拟，然后估算转移模型，学习奖励函数，再根据方程算出策略的价值。
算策略的价值需要整个模型和奖励函数，开销较大。
Temporal Difference Learning (TDL)
免模型。
不要尝试学习整个转移模型，而是在每次移动时就利用局部信息计算新的价值。
假设从 \(s\) 转移到 \(s'\)：
其中 \(\a\) 是 学习率 learning rate。当 \(\a\) 取合适的值（累计样本数量的倒数）时，\(V_\pi\) 会收敛到最终的价值。这就是把所有估计取了平均：考虑增量计算数列的平均值。
回顾 Bellman 方程。TD 学习本质上是将转移概率用 “多次采样取期望” 的方式代替。
需要更多训练轮数，但开销很小。
权衡 ADP 和 TD：往 TD 学习（通过真实动作转移）添加用当前学到的模型想象出来的转移，通过控制该转移的比例以选择我们的训练是偏向模型（ADP）还是经验（TD）。当真实试验代价较高时偏向 ADP。
Active Learning
现在连策略都没有了！
被动学习其实是主动学习的一部分：被动学习衡量策略的优秀程度，主动学习则是寻找策略。
Naive Approach
基于模型。
先随机走，走足够长时间之后用学到的转移和奖励做价值迭代或者策略迭代。
正确！但效率太低。
如果在此基础上，用学到的策略执行动作，并不断更新模型？
错误！会困在局部最小值。
利用 exploitation 和 探索 exploration 的权衡：
- 利用是用已知信息最大化奖励。探索是通过执行动作获得更多信息（如转移概率，奖励等）。
- 只利用会陷入局部最优，可能错过全局最优。只探索是不断尝试新东西，但永远学不到如何做出好的决策。
- 区别在于是随机执行动作还是根据已知信息执行动作。
没有足够信息的时候探索，否则利用。
ADP-based
执行动作的时候用 “探索 & 利用” 策略，而非直接根据学到的策略（即 “利用” 策略）。
贪心选动作 \(a\) 尝试最大化：
Q-Function
\[Q(s, a) = R(s, a) + \g \sum_{s'} T(s, a, s') V(s'). \]
在无限探索的情况下贪心 Greedy in the Limit with Infinite Exploration (GLIE)：以一定概率贪心，概率越来越大。
GLIE 1
随机的概率 \(p(t) = \fr 1 t\)，贪心的概率 \(1 - p(t)\)。收敛较慢，通常令 \(p(t)\) 取小常数 \(\eps\)。
GLIE 2
采用 Boltzmann 探索
\[\pr(a\mid s) = \fr {\exp(Q(s, a) / T)} {\sum_{a'} \exp(Q(s, a') / T)}. \]温度 \(T\) 越大则决策越随机，越小则决策越贪心。
模拟退火。
接下来选择策略的方案都是 GLIE。
Optimistic Exploration
认为所有没有尝试过的动作有很高的奖励。
对所有探索次数小于 \(N_e\) 的动作，用 \(\fr {R_{\max}} {1 - \g}\) 估计。准确度随着 \(N_e\) 增加而上升。这等价于以下算法（证明略）：
Rmax [B & T, 2002]
选取 乐观模型 optimistic model 作为初始模型。随后不断用 VI 计算当前模型下新的最优策略，根据策略模拟（每次贪心选最优动作），然后更新模型。
具体地，如果 \(N(s, a) < N_e\)，则令 \(T(s, a, s) = 1\) 且 \(R(s) = R_\max\)。否则用获得的信息计算 \(T(s, a, \cdot)\) 和 \(R(s)\)。
我们的思想是 不要显式地探索：给予探索奖励，在乐观的模型下贪心。
Rmax 是最早被证明具有多项式样本复杂度的 RL 算法：存在 \(N_e\) 使得如果所有 \(N(s, a) \geq N_e\)，则有很大的概率 \(\eps\)-接近最优策略（最多选择多项式数量的价值比最优动作小 \(\eps\) 的动作），称为 Probably Approximately Correct (PAC)。
TD-Based
GLIE 的探索利用策略，结合 TD 的
注意：为了使用 GLIE，我们需要估计模型。需要转移概率才能根据 \(V_\pi\) 计算 \(Q\) 函数。
依然是计算量小，但相较于被动学习的 TD 需要更多空间：算法变成了基于模型的！
Q-Learning
回忆 Q 函数的定义：\(Q(s, a) = R(s, a) + \g \sum_{s'} T(s, a, s') V(s')\)。
与其学习 \(V\)，不如直接学习 \(Q(s, a)\)。对于最优的 Q 函数，策略对应的价值函数满足 \(V(s) = \max_{a'} Q(s, a)\)。于是
Bellman Constraints on Optimal Q-Function
\[Q(s, a) = R(s, a) + \g \sum_{s'} T(s, a, s') \max_{a'} Q(s', a'). \]
所以可以类似 TD 更新
其中执行动作 \((s, a)\) 走到了 \(s'\)。
QL 是 off-policy 的：PPT 上的说法是更新不依赖于下一步动作。执行动作的策略（GLIE）和更新的策略（\(a'\) 贪心取 \(\op{argmax}\)）是不同的。
这样，在采用探索利用策略时就不需要维护模型了！
Theorem
Q-学习在极限情况下以 \(1\) 的概率收敛至最优 Q-函数，若
- 所有动作（状态-动作二元组）被访问无限多次。
- 学习率满足 \(\sum \a_i = \infty\) 但 \(\sum \a_i ^ 2 < \infty\)。
Reverse Updates
对于基于目标的问题，QL 会花费很多轮让奖励反向传播到最开始的 Q-函数，所以我们存储轨迹并反过来更新 reverse update（或者在轨迹上做若干轮更新 trajectory replay）。
State-Action-Reward-State-Action (SARSA)
将 \(\max_{a'} Q(s', a')\) 替换为 \(\eps\)-贪心策略（\(1 - \eps\) 的概率贪心，\(\eps\) 的概率随机），且 我们希望计算给予 \(\eps\)-贪心策略 的最优 Q 函数。
SARSA 是 on-policy 的：PPT 上的说法是更新与实际动作一致。执行动作的策略和更新的策略都是 \(\eps\)-贪心。
Theorem
假设学习率满足同样的条件，则 SARSA 有很大概率收敛到 \(Q_\eps\)，即由 \(\eps\)-贪心给出的最优 Q-函数。
\[Q_\eps(s, a) = R(s, a) + \la \sum_{s'} \pr(s'| s, a) V_\eps(s'). \]其中 \(V_\eps\) 是 \(\eps\)-贪心策略给出的价值函数。
SARSA，或者说 on-policy 算法，更安全一些，它在训练的时候会避免容易导致很高负回报（\(R = -\infty\)）的状态：需要注意到，训练智能体是有代价的！下图中，QL 容易走到悬崖边上，因为在选择下一步时，QL 忽略掉了可能存在的很糟糕的状态。但 SARSA 会远离悬崖。虽然最短路径确实是沿着悬崖走，但是如果是你（或者你的机器人），你会选择 SARSA 还是 QL 呢？
Lecture 8. Reinforcement Learning II
问题规模太大了，既没有足够的空间存储数据，也没有足够的时间进行训练。
怎么办呢？用哈希函数将 \(S\) 映射到较小的状态空间 \(S'\)，然后在 \(S'\) 上训练。可能不满足 Markov 性。
介绍一些其它方法。
Function Approximation
将学到的知识推广到相似的状态上：用较少的参数拟合 \(V\) 和 \(Q\)，从而 “泛化“ 经验。
Linear Approximation
对状态提取一组 特征 \(\{f_i(s)\}_{i = 1} ^ n\)，参数 \(\t\)，线性拟合 权值
使用 TDL 学习参数，如何更新？
Gradient Descent
设 \(E\) 是损失函数，则
\[\t_i \gets \t_i - \a\p {E} {\t_i}. \]
给定状态 \(s\) 和其目标价值 \(v(s)\)，希望最小化
对于线性拟合，有
用 TD 预测 \(R(s) + \g \hat V_\t(s')\) 近似目标价值 \(v(s)\)，得到
和上一节的 TD-based 一样，需要维护模型以执行 GLIE。
QL with Linear Approximation
对动作提取特征 \(\{f_i(s, a)\}_{i = 1} ^ n\)，其它差不多。
更新规则是
其中 \(\a\) 括号内的前面两项表示用 \(\hat Q\) 拟合的目标价值 \(Q(s, a)\)。
此时 QL 有可能发散。
对于非线性近似（如神经网络），将 \(f_i(s, a)\) 改成 \(\p{\hat Q_\t(s, a)} {\t_i}\)（然后干吗？反向传播吗！！）。非线性函数通常存在多个局部最小值，无法保证收敛到全局最优。
Deep Q-Network
DQN 等于 RL 加 DL，在 RL 的大框架下（学习 Q 函数）用 DL 学习特征 \(\t\)。
一些问题：训练数据相关性高导致容易过拟合；策略容易震荡；奖励和价值的尺度未知。
为了优化这些问题，衍生出了无数的想法。
Experience Replay
从转移缓冲区 \(D = \{(s, a, r, s')\}\) 随机选取一小批转移进行训练，降低数据的时序相关性。
Fixed Target Q-Network
以旧参数 \(\t ^ -\) 为目标训练，周期性地更新 \(\t\)，避免震荡。
Reward Range
将奖励裁剪到 \([-1, +1]\)，避免过大的 Q 值和梯度。
DQN Extensions
近似算法都会存在自己的缺陷，所以 AI 工作者们不断提出优化点子。这就是 AI。
Double DQN
DQN 的 过估计偏差 maximization bias 问题：在训练早期，因为 Q 值本身不准确，所以在计算训练目标时，对动作取最大值的行为会导致智能体偏好被高估的动作。
Double DQN 的思想是 分离动作选择和价值估计。
用两个独立的 Q 函数 \(Q_1\) 和 \(Q_2\)，每次随机选择更新哪个 \(Q_i\)。
用 \(Q_i\) 进行动作选择，但用另一个 Q 函数进行价值评估，避免高估状态的价值。
另一种实现方法是用旧的网络进行价值评估。注意和 fixed target 优化不同，后者是用旧的网络同时选择动作和评估价值。
Prioritized Experience Replay
关注更有价值的转移。
转移的 “惊喜程度” 为 DQN 误差（也就是上面那个式子）\(p_i\)，在经验回放的时候按照 \(P(i) \propto p_i ^ \b\) 进行采样。
\(\b\) 决定了优先的程度。当 \(\b = 0\) 时就是随机采样。
Dueling Networks
将 Q 函数分成与动作无关的价值函数 \(V(s; \t)\) 和与动作相关的优势函数 \(A(s, a; \t)\)，用神经网络分别学习。
什么意思呢？\(V\) 是衡量状态本身的好坏，而 \(A\) 是选择不同动作带来的优势。
双重网络将状态和动作进行了一定程度的分离：“背景环境” 和 “关键决策时刻”。当动作对状态的影响较小时，能更快地识别出优秀的动作。
但是 \(Q = A + V\) 并不唯一，所以强制令 \(A\) 的均值为零。
Multi-step Returns
使用 \(n\) 步累计奖励加上第 \(n + 1\) 步的最优估计进行学习。
方差大（依赖更长的轨迹），但偏差小（使用更多真实奖励）。有助于在奖励稀疏的环境加速学习。
Distributed DQN
将学习和执行动作分离。用若干执行器和环境交互，将获得的数据加入回放池。
神经网络从回放池采样并更新网络。
Distributed DQN with Recurrent Experience Replay
用循环神经网络（如 LSTM）处理部分可观测问题，使网络能够记忆历史信息。
Lecture 9. Reinforcement Learning III
DQN 用尽浑身解数尝试拟合最优的 Q 函数，但是想一想，我们真的关心价值吗？学习价值，只是为了获得充分考虑到问题特点的策略。其本质还是策略，而表示策略要容易得多。
上一节用 \(V_\t\) 和 \(Q_\t\) 拟合 \(V ^ \pi\) 和 \(Q ^ \pi\)。现在直接考虑拟合策略
此外，基于价值的 DQN 无法学习具有随机性的策略（除了 \(\eps\)-贪心，但随机性较小），而随机策略可能更优（最简单的例子，石头剪刀布）。
Policy Gradient
Learning Objective
首先明确学习目标，需要衡量一个策略的质量。
对于 分幕 episodic 环境（有明确的起点和终点），可以用累计期望价值
注意
这里的 \(V ^ {\pi_\t}\) 不打折扣，即 \(\g = 1\)。但是连续环境的 \(V ^ {\pi_\t}\) 打折扣，否则会导致值函数发散。
当然你可能会问这里为什么累计期望价值不会是无穷大，问得好，我也有一样的疑问。
一个好的分幕环境应当合理地设置奖励使得最优策略不是在一个正环上来回走而是尽快达到目标，一个好的策略应当保证到达终点的期望时间不是无穷大。
对于 连续 continuing 环境（没有明确的起止，无限进行），可以用平均价值
或 平均每步奖励 average reward per time-step
其中 \(d ^ {\pi_\t}\) 是 \(\pi_\t\) 的 稳态分布 stationary distribution，即每个状态在策略 \(\pi_\t\) 下，时间趋于无穷的遍历次数的比例。
这样就转化成了优化问题：最大化 \(J(\t)\)。本节课主要关心梯度下降（上升）法：
其中 \(\na_\t J(\t)\) 称为 策略梯度 policy gradient
Finite Difference PG
想法非常简单：用离散的情况模拟计算策略梯度，即
简单，但效率低、噪音大，不适用于高维参数空间。
Monte-Carlo PG (REINFORCE)
直接计算策略梯度。
推一下 \(J_1(\t)\) 的式子：
每展开一个 \(\na_\t V ^ {\pi_\t}(s)\)，就会得到加号后面那一堆，加上根据策略 \(\pi_\t\) 走一步到 \(s’\) 的概率乘以 \(\na_\t V ^ {\pi_\t}(s)\)。无限地展开下去，就会得到
其中 \(\eta ^ {\pi_\t}(s)\) 是 \(s\) 的期望经过次数。
当然你可能会问这里为什么 \(\eta\) 不会是无穷大，这一点在上面的 “注意” 中已经解释过了：一个好的策略应当保证到达终点的期望时间不是无穷大。
\(\pi_\t(s, a)\) 被取了梯度，所以如果我们以 \(\pi_\t(s, a)\) 为概率分布进行动作采样从而和环境交互并获得转移，就必须让式子里重新出现 \(\pi_\t(s, a)\)。方法是用 \(\dd x = x \cdot \dd \log x\) 写成
即
Policy Gradient Theorem
\[\na_\t J_1(\t) = \E_{\pi_\t}[\na_\t \log \pi_\t(s, a)\ Q ^ {\pi_\t}(s, a)]. \]在连续环境下（此时有折扣系数 \(\g\)，注意不是连续空间），\(\fr 1 {1 - \g} J_{avV}(\t)\) 和 \(J_{avR}(\t)\) 也等于等号右侧的结果。
推导方法类似，核心步骤是在用 Leibniz 公式的时候，对 \(d ^ {\pi_\t}(s)\) 求梯度的那一项因为 \(\sum_s d ^ {\pi_\t}(s) = 1\) 而消失了。
于是每次以 \(\pi_\t\) 为策略从起点走到终点（在连续环境则是以稳态分布为初始分布采样，随机探索一条足够长的路径），并对每一步 \((s_t, a_t)\) 更新
其中 \(v_t\) 是当前步之后所有奖励的（折扣）和。
为了归一化 \(\pi_\t\) 且方便计算 \(\log \pi_\t\)，对于离散状态的情况，常见的参数化方法是 softmax 归一化
\[\pi_\t(s, a) = \fr {\exp(f(s, a) ^ T \t)} {\sum_{a'} \exp(f(s, a') ^ T \t)}. \]这样不仅有 \(\sum_a \pi_\t(s, a) = 1\)，同时
\[\bal \na_\t \log \pi_\t(s, a) & = \na_\t(f(s, a) ^ T \t) - \na_\t\log\sum_{a} \exp(f(s, a) ^ T\t) \\ & = f(s, a) - \fr {\sum_a \na_\t \exp(f(s, a) ^ T\t)} {\sum_a \exp(f(s, a) ^ T \t)} \\ & = f(s, a) - \fr {\sum_a (\exp(f(s, a) ^ T\t) f(s, a))} {\sum_a \exp(f(s, a) ^ T \t)} \\ & = f(s, a) - \E_{s, \pi_\t}[f(s, a)]. \eal \]对于连续情况，用 Gauss 分布表示状态选择的概率（神秘），有
\[a\sim \mathcal N(\mu(s) = f(s) ^ T\t, \s ^ 2) \implies \na_\t \log \pi_\t(s, a) = \fr {(a - \mu(s))f(s)} {\s ^ 2}. \]
基于策略的 RL，优点是收敛性更好，但是容易收敛至局部最优，且方差较大，学习速度慢。
Actor-Critic
对 MCPG 的优化。
为了降低方差，不要用根据参数 \(\t\) 计算的价值去更新 \(\t\)，而是用一个新的参数。
QAC
加入 评论家 critic \(Q_w(s, a) \approx Q ^ {\pi_\t}(s, a)\)，则
如何更新 \(w\)？这就是线性函数拟合 Q 函数，在第八讲学过了：
Advantage AC
可以减去任何 动作无关 的 基准函数 baseline function \(B(s)\)：
把 \(B(s)\) 提到外面，用梯度的线性性和 \(\sum_a \pi_\t(s, a) = 1\) 即得。
一个比较优秀的基准函数是 \(B(s) = V ^ {\pi_\t}(s)\)，则可以用优势函数重写策略梯度
所以其实评论家应该学习 \(A = Q_w - V_v\)。用两组不同的参数分别学习 \(Q\) 和 \(V\)。
TD-AC
然后会发现学习 \(V\) 的 TD 误差
其实是 \(A ^ {\pi_\t}(s, a)\) 的无偏估计，因为前面两项加起来是 \(Q ^ {\pi_\t}(s, a)\) 的无偏估计。所以
实践中可以用
这样就只要一组参数了。
Bias Analysis
但是我们用 \(Q_w\) 估计 \(Q ^ {\pi_\t}\) 不会出错吗？
可以证明，当 \(\na_w Q_w(s, a) = \na_\t \log \pi_\t(s, a)\) 且最小化均方差 \(\eps = \E_{\pi_\t}[(Q ^ {\pi_\t}(s, a) - Q_w(s, a)) ^ 2]\) 时，估计是精确的：
证明方法是若最小化 \(\eps\) 则 \(\na_w \eps = 0\)，然后展开就行。
如何满足第一个条件？在神经网络最后一层加入相同的关于 \((s, a)\) 的线性特征用于拟合 \(Q_w\) 和 \(\log \pi_\t\)。
最后讲一下 PG 的缺点：需要大量数据（每次需要走完整一条路径且数据只用一次），且对步幅非常敏感。