8.1 模型与规划 / Models and Planning
A model of the environment is anything the agent can use to predict how the environment will respond to its actions. Distribution models produce all possible next states and their probabilities. Sample models produce just one possibility, sampled according to the probabilities. Sample models are much easier to obtain.
环境模型是智能体用来预测环境对其动作如何响应的任何东西。分布模型产生所有可能的下一状态及其概率。样本模型只产生一种可能性，按概率采样。样本模型容易获得得多。
Planning is any computational process that takes a model as input and produces or improves a policy. All state-space planning methods share: (1) computing value functions as a key intermediate step, and (2) computing value functions by backup operations applied to simulated experience.
规划是以模型为输入并产生或改进策略的任何计算过程。所有状态空间规划方法共享：(1) 计算价值函数作为关键中间步骤，(2) 通过对模拟经验应用备份操作来计算价值函数。
💡 核心洞察：学习和规划的核心都是通过备份更新操作来估计价值函数。区别在于：规划使用模型生成的模拟经验，而学习使用环境产生的真实经验。
8.2 Dyna：集成规划、行动和学习 / Integrated Planning, Acting, and Learning
Dyna-Q integrates planning, acting, model-learning, and direct RL. Real experience improves the model (model-learning) and directly improves values/policy (direct RL). Planning uses the model to generate simulated experience and applies the same RL algorithm to it.
Dyna-Q集成了规划、行动、模型学习和直接RL。真实经验改进模型（模型学习）并直接改进价值/策略（直接RL）。规划使用模型生成模拟经验，并对其应用相同的RL算法。
表格型Dyna-Q
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
初始化 Q(s,a) 和 Model(s,a)
循环：
(a) S ← 当前状态
(b) A ← ε-贪心(S, Q)
(c) 执行A；观察R, S'
(d) Q(S,A) ← Q(S,A) + α[R + γ max Q(S',a) − Q(S,A)] ← 直接RL
(e) Model(S,A) ← R, S' ← 模型学习
(f) 重复n次： ← 规划
S ← 随机已经验状态, A ← 随机已选动作
R, S' ← Model(S,A)
Q(S,A) ← Q(S,A) + α[R + γ max Q(S',a) − Q(S,A)]
Example 8.1: Dyna Maze. With n=0 (no planning), the agent takes ~25 episodes. With n=50 planning steps per real step, it takes only 3 episodes. Planning builds an extensive policy from simulated experience while the agent is still wandering.
例8.1：Dyna迷宫。n=0（无规划）时需~25个回合。n=50（每实际步50次规划）时只需3个回合。规划在智能体仍在漫游时从模拟经验中构建了广泛的策略。
8.3 模型错误时 / When the Model Is Wrong
Blocking Maze: When a short path is blocked, agents discover the new path relatively quickly. Shortcut Maze: When a shorter path opens, Dyna-Q never discovers it — the model says no shortcut exists, so planning avoids exploring that area.
阻塞迷宫：当短路径被阻塞时，智能体相对较快地发现新路径。捷径迷宫：当更短路径开放时，Dyna-Q从未发现它——模型说捷径不存在，因此规划避免探索该区域。
Dyna-Q+ solves this with an exploration bonus: κ√τ, where τ is the number of time steps since a state-action pair was last tried in real interaction. This encourages testing long-untried actions.
Dyna-Q+通过探索奖励解决此问题：κ√τ，其中τ是自状态-动作对上次在真实交互中尝试以来的时间步数。这鼓励测试长期未尝试的动作。
8.4 优先化扫描 / Prioritized Sweeping
Prioritized sweeping focuses planning by working backward from states whose values have changed. A priority queue maintains state-action pairs whose values would change nontrivially if updated, prioritized by the magnitude of change.
优先化扫描通过从价值已改变的状态向后工作来聚焦规划。优先队列维护若更新则价值会显著变化的状态-动作对，按变化幅度排列优先级。
Result: dramatically increases speed of finding optimal solutions in maze tasks, often by a factor of 5 to 10.
结果：在迷宫任务中极大提高找到最优解的速度，通常快5到10倍。
8.5 期望更新vs样本更新 / Expected vs. Sample Updates
Expected updates consider all possible next states (cost: b computations where b=branching factor). Sample updates consider one sampled next state (cost: 1 computation). For large b, a few sample updates at many pairs dramatically outperform expected updates at a few pairs.
期望更新考虑所有可能的下一状态（代价：b次计算，b=分支因子）。样本更新考虑一个采样的下一状态（代价：1次计算）。对于大的b，在许多对上进行少量样本更新远优于在少量对上进行期望更新。
💡 关键发现：对于中等大的分支因子b，误差在远少于b次样本更新后就急剧下降。样本更新在大状态空间问题上可能优于期望更新。
8.6 轨迹采样 / Trajectory Sampling
Trajectory sampling distributes updates according to the on-policy distribution — simulating trajectories following the current policy and updating encountered state-action pairs. This focuses on relevant states, ignoring irrelevant parts of the state space.
轨迹采样按照on-policy分布分配更新——模拟遵循当前策略的轨迹并更新遇到的状态-动作对。这聚焦于相关状态，忽略状态空间中无关的部分。
Short-term advantage: faster planning by focusing on states near start states. Long-term: may hurt if commonly-visited states already have correct values. Advantage grows with problem size.
短期优势：通过聚焦起始状态附近的状态来加速规划。长期：如果常访问状态已有正确值可能会受损。优势随问题规模增长。
8.8 决策时规划 / Planning at Decision Time
Background planning (e.g., Dyna, DP) gradually improves value functions from simulated experience. Decision-time planning begins and completes after encountering each state, computing the best action through look-ahead search. Values/policies are typically discarded after use.
后台规划（如Dyna、DP）从模拟经验中逐步改进价值函数。决策时规划在遇到每个状态后开始并完成，通过前瞻搜索计算最佳动作。价值/策略通常在使用后被丢弃。
8.11 蒙特卡洛树搜索 / Monte Carlo Tree Search (MCTS)
MCTS is a rollout algorithm enhanced by accumulating value estimates to successively direct simulations toward more highly-rewarding trajectories. Largely responsible for computer Go's rise from weak amateur to grandmaster level.
MCTS是一种增强的rollout算法，通过积累价值估计来连续将模拟引导向更高回报的轨迹。很大程度上推动了计算机围棋从弱业余水平到大师级的飞跃。
Each iteration has four steps: (1) Selection — tree policy traverses to a leaf node; (2) Expansion — add child node(s) via unexplored actions; (3) Simulation — run rollout policy to terminal state; (4) Backup — update action values along the tree path.
每次迭代包含四步：(1) 选择——树策略遍历到叶节点；(2) 扩展——通过未探索动作添加子节点；(3) 模拟——运行rollout策略到终止状态；(4) 备份——更新树路径上的动作价值。
💡 MCTS的优势：(1) 在线增量样本估计；(2) 保存树边动作价值并用RL样本更新；(3) 将MC试验聚焦于高回报轨迹；(4) 增量扩展查找表存储部分动作价值函数。
8.12-13 小结 / Summary
Planning and learning share the same core: estimating value functions via backup operations. They differ only in the source of experience (simulated vs. real). Key dimensions: update size, update distribution (prioritized, trajectory sampling), on-policy vs. off-policy, sample vs. expected updates, background vs. decision-time planning.
规划和学习共享相同核心：通过备份操作估计价值函数。它们仅在经验来源（模拟vs真实）上不同。关键维度：更新大小、更新分布（优先化、轨迹采样）、on-policy vs off-policy、样本vs期望更新、后台vs决策时规划。
核心概念速查 / Key Concepts
| 术语 / Term | 英文 / English | 含义 / Meaning |
|---|
| 分布模型 | Distribution Model | 产生所有可能转移及其概率 |
| 样本模型 | Sample Model | 产生单个采样的转移 |
| Dyna-Q | Dyna-Q | 集成规划、行动、模型学习和直接RL |
| 探索奖励 | Exploration Bonus | κ√τ，鼓励测试长期未尝试的动作 |
| 优先化扫描 | Prioritized Sweeping | 按变化幅度优先级向后传播更新 |
| 轨迹采样 | Trajectory Sampling | 按on-policy分布分配更新 |
| RTDP | Real-time DP | 价值迭代的on-policy轨迹采样版 |
| 决策时规划 | Decision-time Planning | 在遇到状态后即时搜索选择动作 |
| MCTS | Monte Carlo Tree Search | 选择→扩展→模拟→备份的迭代搜索 |
| Rollout | Rollout Algorithm | MC控制应用于当前状态的模拟轨迹 |