9 在线规划 Online Planning

:::info 在许多高维问题中，使用离线近似方法难以处理，本章讨论在线规划方法——基于对当前状态的可达状态的推理来查找动作。因为可达状态空间比完整状态空间小很多，所以能显著减少存储和计算需求。
本章将讨论各种能提高在线规划的效率的算法，包括修剪状态空间、采样、沿着更有希望的轨迹进行规划。 :::

1. 滚动规划 Receding Horizon Planning

滚动规划 Receding Horizon Planning：从当前状态规划到一个最大的固定深度，然后，我们从当前状态执行动作，转移到下一个状态，并重新规划。 :::info 本章讨论的在线规划方法都遵循这个滚动规划方案，不同之处在于如何探索不同的动作路线。 ::: 应用滚动规划的挑战之一是确定适当的深度，深度越大，计算量更大。

2. 结合rollout的前向算法 Lookahead with Rollouts

一个简单的在线策略包括对深度的模拟所估计的值进行贪婪的动作，需要一个策略来运行模拟。
rollout策略：通常是随机的，从分布中提取动作。
使用生成模型generative model从分布中生成后续状态。
结合rollout的前向算法进行价值估计，这种方法比原来的rollout策略产生更好的估计，被视为策略迭代算法中使用的策略改进的近似形式（7.4节）。

3. 前向搜索 Forward Search

前向搜索 Forward Search：将所有可能的转移扩展到深度，以确定从初始状态开始采取的最佳动作。这种扩展形成了一个搜索树（search tree），搜索树的最坏情况分支因子为，计算复杂度为，在状态数量和动作数量上呈指数增长。

如果问题需要的规划深度超出了在线计算的能力范围，则可以使用离线得到的价值函数的估计，例如第8章介绍的价值函数近似方法。这种结合在线和离线的方法被称为混合规划hybrid planning。

4. 分支定界 Branch and Bound

分支定界 Branch and Bound：通过对价值函数的边界进行推理来修剪分支，避免前向搜索的指数级计算复杂度。该算法要求已知价值函数的下界和动作价值函数的上界。
分支定界会给出与前向搜索相同的结果，但根据修建分支的多少可能会更高效。在最欢的情况下，分支定界的计算复杂度与前向搜索相同。

5. 稀疏采样 Sparse Sampling

稀疏采样 sparse sampling：用于减少前向搜索和分支定界的分支因子。这样只用考虑下一状态有限数量的样本，而不是对所有可能的下一状态进行分支，显著减少计算量。
如果为搜索树中的每个动作节点提取个样本，计算复杂度为，即与状态空间无关。

6. 蒙特卡罗树搜索 Monte Carlo Tree Search

蒙特卡罗树搜索 Monte Carlo tree search：从当前状态运行个模拟，避免了指数级复杂度。算法更新动作价值函数和特定状态-动作对被选择的次数。从当前状态运行个模拟后，简单地选择使的估计最大化的操作。将搜索引导到搜索空间中有希望的区域。
一个模拟首先遍历探索的最大空间，其中包括我们对和进行估计的状态。遵循探索策略从各种状态中选择动作，一种常见的方法是选择最大化UCB探索启发式的动作：，其中是的总访问次数，是衡量未探索动作价值的探索参数。如果，则奖金定义为无穷大。为分母，则未尝试的操作的探索奖励更高。
？

7. 启发式搜索 Heuristic Search

启发式搜索 heuristic search：对当前状态中的价值函数使用贪婪策略的次模拟。
价值函数初始化为价值函数的上界，称为启发式。当运行模拟时，我们通过前向（lookahead）更新对的估计。运行模拟之后，只需从中选择与相关的贪婪行为。
只要启发式确实是价值函数的上界，就可以保证启发式收敛到最佳效用函数。反之，可能不会收敛到最佳策略，但仍可能收敛到良好的策略。时间复杂度为

8. 标记启发式搜索 Labeled Heuristic Search

标记启发式搜索 labeled heuristic search：是启发式搜索的一种变体。运行带有价值更新的模拟，同时根据它们的价值是否被求解来标记状态。不重新评估价值已收敛的状态。
如果一个状态的效用残差低于阈值，则称已被解决。运行带有价值更新的模拟，知道当前状态被解决。
与前一节的启发式搜索相比，这种标记过程将计算精力集中在状态空间的最重要的区域。
？

9. 开环规划 Open-Loop Planning

本章前面讨论的在线方法和前几章讨论的离线方法都是闭环规划的例子，通常需要在规划过程中考虑未来的状态信息。
开环规划 open-loop planning：可以提供最佳闭环规划的令人满意的近似，同时避免了推理获取未来的信息，大大提高计算效率。有时开环规划方法被称为模型预测控制model predictive control。
开环规划可以表示为深度达的一系列动作，简化为一个优化问题：，其中是执行动作序列时的预期回报。
在高维空间中，闭环规划在计算上是不可行的，但开环规划反之，不考虑未来的信息来达到高效率。