近似动态规划 ADP 学习指南

这份网页把课程 Chapter 6 的内容整理成可检索、可打印、可按模块复习的学习材料。核心主线是：保留 DP 的“当前优化 + 未来价值”结构，但用更便宜的近似替换完整 cost-to-go 函数。

Cost-to-go approximationCECOLFC / POLFCLimited LookaheadAggregationRolloutMPCDiscretization

0. 本章知识地图

一句话总括：ADP 不是抛弃 DP，而是在 DP 方程中把最难计算的未来最优 cost-to-go 函数 J 换成可计算的近似 ˜J，再做有限步的在线优化。
起点

DP 为什么失败

维数灾难、建模灾难、实时约束、不完全信息问题的 belief state 爆炸。

核心

˜J 从哪里来

确定性近似、启发式策略成本、聚合问题成本、参数化函数、仿真估计。

执行

如何选控制

one-step / multi-step lookahead，计算候选控制的 Q-factor，执行第一步并滚动重复。

本章方法之间的关系

完整 DP 方程
替换 J 为 ˜J
有限前瞻
Rollout / MPC
聚合 / 参数化 / 仿真
补充：ADP 也可能指 Abstract Dynamic Programming

课程第一页手写注释提到，ADP 有时也指 Abstract Dynamic Programming。这个含义强调 DP 背后的抽象映射性质，尤其是 Monotonicity 与 Contraction。这些性质决定了很多 DP 理论与算法结构，使具体问题细节变成次要因素。本网页的主线仍按 Chapter 6 的 Approximate Dynamic Programming 展开。

1. 为什么需要近似动态规划？

1.1 DP 的三类实践困难

Curse of dimensionality

  • 状态变量、控制变量、扰动变量增加时，计算和存储指数增长。
  • 组合问题中状态或部分解数量快速爆炸。
  • 不完全信息问题通常要把 conditional distribution / belief 当状态，维度更高。

Curse of modeling

  • 数学模型可能难以建立。
  • 仿真模型可能昂贵或只能近似。
  • 模型误差会直接影响 DP 解的有效性。

Real-time constraints

  • 问题数据可能临近控制时才给出。
  • 系统运行过程中数据会变化，需要 online replanning。
  • 完整 DP 求解时间无法满足实时控制。

1.2 维数灾难的数量级

若状态空间、控制空间、扰动空间都是欧式空间并做网格离散化，每个维度取 d 个点，状态维度 n，控制维度 m，扰动维度 r，阶段数 N，则：

状态网格数：d^n 每个状态比较控制：d^m 每个控制计算期望：d^r 总计算量：至少 O(N d^n)，常可达 O(N d^(n+m+r))
学习重点：ADP 的目标不是“精确求最优”，而是在可接受时间内得到足够好的 suboptimal control。课程中的 CEC、OLFC、limited lookahead、rollout、aggregation 都是在这个目标下出现的。

2. Cost-to-go Function Approximation

2.1 精确 DP 到 ADP 的基本替换

标准 DP 在每个状态下最小化“当前成本 + 未来最优成本”。ADP 的基本做法是把未来最优成本 J_{k+1} 替换成近似函数 ˜J_{k+1}。

精确 DP： J_k(x_k) = min_{u_k ∈ U_k(x_k)} E[ g_k(x_k,u_k,w_k) + J_{k+1}( f_k(x_k,u_k,w_k) ) ] ADP / one-step lookahead 策略： μ_k(x_k) ∈ argmin_{u_k ∈ U_k(x_k)} E[ g_k(x_k,u_k,w_k) + ˜J_{k+1}( f_k(x_k,u_k,w_k) ) ]

2.2 ˜J 的三类计算方式

方式含义适合场景主要风险
Off-line approximation控制开始前，为所有 k 计算整个 ˜J 函数。状态空间较小，或可提前训练模型。存储压力大，问题数据变化时复用困难。
On-line approximation当前状态 x_k 已知后，只计算相关 next states 的 ˜J 值。实时控制；只关心当前需要比较的候选控制。每步计算可能仍然重。
Simulation-based methods用 Monte Carlo simulation 估计未来成本。模型复杂、大规模问题、没有解析 cost-to-go。仿真方差会影响 argmin。
贯穿全章的问题：你选择怎样的 ˜J，通常比前瞻多看一步更重要。坏的终端近似会误导 lookahead；好的启发式或聚合近似可以显著提高策略质量。

3. Certainty Equivalent Control (CEC)

3.1 CEC 核心思想

CEC 把随机最优控制问题替换成确定性最优控制问题：在每个时刻 k，把未来不确定量固定为某些“典型值”，解确定性问题，并只执行求得控制序列中的第一项。

当前 x_k 或估计 x̄_k(I_k)
固定未来 w_i 为 w̄_i
解确定性最优控制
执行第一项 u_k
下一时刻重算
在线 CEC：给定 x_k，固定 w_i = w̄_i, i ≥ k，求 minimize g_N(x_N) + Σ_{i=k}^{N-1} g_i(x_i,u_i,w̄_i) subject to x_{i+1}=f_i(x_i,u_i,w̄_i), u_i∈U_i 然后执行最优序列的第一项 u_k。

3.2 等价离线反馈实现

另一种实现方式是先对“所有随机量都被典型值替换”的确定性问题做 DP，得到确定性最优反馈控制器 {μ_0^d,…,μ_{N−1}^d}，实际运行时用 μ_k^d(x_k)。若是不完全信息问题，则使用估计状态 x̄_k(I_k)。

确定性反馈问题： minimize g_N(x_N) + Σ_{k=0}^{N-1} g_k(x_k, μ_k(x_k), w̄_k) subject to x_{k+1}=f_k(x_k, μ_k(x_k), w̄_k), μ_k(x_k)∈U_k CEC 实际控制：u_k = μ_k^d(x_k) 或 u_k = μ_k^d(x̄_k(I_k))

3.3 CEC with Heuristics

即便确定性问题比随机 DP 简单，它仍可能很难精确求解。此时可用 heuristic 求后续阶段成本，再对第一步控制做优化：

选择 u_k： min_{u_k∈U_k(x_k)} g_k(x_k,u_k,w̄_k) + H_{k+1}( f_k(x_k,u_k,w̄_k) ) H_{k+1}: 从 next state 开始，按启发式执行剩余阶段得到的成本。
  • H 不一定需要闭式表达；可以从 next state 向前模拟启发式并累积成本。
  • 若控制集合连续，常需要先离散化候选控制。
  • 这已经体现了 ADP 的核心：当前一步精细优化，未来用近似 cost-to-go。

3.4 Partially Stochastic CEC

Partially stochastic CEC 不固定所有随机性，而是只固定一部分，剩余部分仍按随机模型处理。重要特例是：把不完全状态信息问题当作完美状态信息问题，用估计状态 x̄_k(I_k) 当作真实状态。

Slotted Aloha 例子

完美状态信息版本容易；困难在 backlog 不可直接观测。自然策略是根据历史成功、空闲、碰撞估计 backlog。

μ̃_k(I_k)=min{1, 1/x̄_k(I_k)}

有限状态不完全观测系统

先解对应的完美状态信息问题；运行中用 Viterbi 等方法估计当前状态，再代入完美信息策略。

CEC 的局限：LQ 问题中 CEC 可与最优策略一致，但一般问题里 CEC 可能严格差于最优 open-loop controller，因为它可能忽略分布信息和信息价值。

3.1 Adaptive Control：未知参数下的 CEC 扩展

未知参数的状态增广

若系统含未知参数 θ，可以把 θ 当作不变的状态分量，使问题落入不完全信息框架。

原系统：x_{k+1}=f_k(x_k,u_k,w_k,θ) 增广状态：X_k=(x_k,y_k), y_k=θ, y_{k+1}=y_k 若固定 θ 可求最优策略 μ_k(I_k,θ)，则 CEC 使用估计 θ̂_k： μ_k(I_k)=μ_k(I_k,θ̂_k)

Caution, Probing, Dual Control

概念含义直觉
Caution由于系统参数不确定，控制动作要保守。|u| 小，状态不易失控。
Probing主动激励系统以获取更多识别信息。|u| 大，观测的 signal-to-noise ratio 更高。
Dual control当前控制既影响当前成本，也影响未来信息质量。控制目标与识别目标之间的权衡。

Two-phase control 与 Identifiability

Two-phase control 先做参数识别，再用估计参数做控制。它的问题是：识别阶段的信息不能即时改善控制；何时切换阶段也不明确；更严重的是，控制律可能让参数不可辨识。

例：x_{k+1}=a x_k + b u_k + w_k，a,b 未知。 若识别阶段使用反馈 u_k=γ x_k，则闭环为： x_{k+1}=(a+bγ)x_k+w_k。 因此最多只能识别 a+bγ，无法分别识别 a 和 b。
修正思路作用代价
加入已知输入 δ_k闭环变为 x_{k+1}=(a+bγ)x_k+bδ_k+w_k，可识别更多结构。输入序列需 persistently exciting。
引入一单位反馈延迟控制用 x_{k-1} 而非 x_k，改变闭环结构以区分参数。系统响应变慢。

4. Open-Loop Feedback Control (OLFC)

4.1 OLFC 的思想

不完全信息问题中，额外观测能改善性能，但把所有未来观测都纳入 DP 会很难。OLFC 的折中是：当前利用新观测更新 belief；但在未来优化中，忽略未来观测，只求一个开环控制序列。

当前信息 I_k
更新 P(x_k|I_k)
开环优化未来控制序列
执行第一项
下一时刻再反馈更新

4.2 性能关系

策略当前测量未来测量性能直觉
Open-loop policy不使用不使用完全提前定好控制序列。
OLFC使用忽略每步根据新观测重新开环优化，因此通常不差于 open-loop。
CEC常用估计/典型值忽略或部分使用没有 OLFC 那样的 open-loop 性能保证。

4.3 POLFC：Partially Open-Loop Feedback Control

POLFC 只忽略最难处理的一部分未来信息，保留可处理的信息。它介于完整 feedback 与 OLFC 之间。

库存例子：每次新的 demand forecast 到来时，基于当前 forecast 计算最优 (s,S) 策略；新 forecast 出现后，放弃旧策略并重新计算。这样比完全忽略未来信息更灵活。

5. Limited Lookahead Policies

Limited lookahead 截断完整 horizon，只向前看 ℓ 步，在末端用近似终端 cost-to-go ˜J 补上未来。

当前 x_k
向前展开 ℓ 步
终端放 ˜J
执行第一步
滚动重复

5.1 One-step Lookahead (1SL)

μ_k(x_k) ∈ argmin_{u_k∈U_k(x_k)} E[ g_k(x_k,u_k,w_k) + ˜J_{k+1}(f_k(x_k,u_k,w_k)) ] 其中：˜J_N = g_N，且 ˜J_{k+1} 是对 J_{k+1} 的近似。
  • 如果 ˜J 容易计算且 minimization 不难，1SL 可在线执行。
  • 可以用子集 Ū_k(x_k) 替代全部 U_k(x_k)，只搜索 most promising controls。
  • CEC with heuristics、rollout、MPC 都可看作 1SL/limited lookahead 的特例。

5.2 Two-step / ℓ-step Lookahead

Two-step lookahead 在下一步又嵌入一次 1SL，相当于解一个 2-step DP 子问题。ℓ-step lookahead 继续展开 ℓ 层，然后在终端用 ˜J。

计算爆炸：前瞻深度增加时，计算量随分支数呈树状增长；扰动取值多、控制空间连续时尤为严重。

5.3 Control subset

μ_k(x_k) ∈ argmin_{u_k∈Ū_k(x_k)} E[g_k(x_k,u_k,w_k)+˜J_{k+1}(f_k(x_k,u_k,w_k))] 其中 Ū_k(x_k) ⊂ U_k(x_k)。

这是一种计算—性能 trade-off：在线决策更快，但可能错过真正最优控制。

5.1 1SL 的性能界

基本上界

令 J_k^{1SL}(x_k) 为采用 1SL 策略后的实际 cost-to-go，并定义：

ˆJ_k(x_k)=min_{u_k∈U_k(x_k)} E[g_k(x_k,u_k,w_k)+˜J_{k+1}(f_k(x_k,u_k,w_k))]

若对所有 (x_k,k) 都有：

ˆJ_k(x_k) ≤ ˜J_k(x_k)，且 ˆJ_N=g_N

则可以推出：

J_k^{1SL}(x_k) ≤ ˆJ_k(x_k) ≤ ˜J_k(x_k)
直觉：如果 1SL 通过当前优化得到的“当前成本 + 近似未来成本”不超过原来的近似 ˜J，那么实际执行 1SL 的成本也受 ˜J 控制。

带 δ 误差的版本

若 1SL 只满足： E[g_k(x_k,μ_k(x_k),w_k)+˜J_{k+1}(f_k(x_k,μ_k(x_k),w_k))] ≤ ˜J_k(x_k)+δ_k 则： J_k^π(x_k) ≤ ˜J_k(x_k)+δ_k+δ_{k+1}+...+δ_{N-1}

δ_k 可解释为 approximation error、候选控制子集限制、数值优化误差等。

三个重要特例

特例˜J 来源结论
Rollout某个 base heuristic 的 cost-to-go H。1SL 改进 H，因此 rollout 不差于基策略。
Multiple heuristics多个 heuristic cost-to-go 的最小值。不差于这些 heuristic 中最好的一个。
CEC bound典型扰动下的确定性最优值。在 Jensen/凹性条件下可得到有利界。

5.2 有限前瞻的计算问题

有限前瞻的计算瓶颈有两个：第一，如何得到 ˜J；第二，如何求当前 minimization。

情形计算方法说明
离散控制集合枚举候选控制并比较 lookahead cost。直接但可能候选数很大。
连续控制集合转化为 nonlinear programming。可用连续优化工具。
多阶段前瞻也可形成 NLP 或随机规划问题。变量数随扰动分支增长。
若控制维度为 m，扰动有 r 个可能取值，ℓ-stage perfect-state lookahead 可形成约 m(1+r^{ℓ-1}) 维 nonlinear programming 问题。

Two-stage stochastic programming 视角

第一阶段选 u_0，成本 g_0(u_0)。 随机事件 w_j 发生，概率 p_j。 观察 w_j 后选 recourse decision u_1^j。 目标：min g_0(u_0)+Σ_{j=1}^r p_j g_1(u_1^j,w_j) 约束：u_0∈U_0, u_1^j∈U_1(u_0,w_j)

这个表达展示了 limited lookahead 与 stochastic programming 的联系：未来在观察扰动后做的决策变成每个 scenario 下的 recourse variables。

6. 如何构造 ˜J：三条主路线

路线做法典型例子
Problem approximation用相关但更简单的问题的 cost 替代 J。确定化、分解、简化约束或动态。
Parametric approximation选择函数族 ˜J(x,r)，再训练参数 r。feature-based linear architecture、neural networks。
Rollout approach用某个 suboptimal policy 的 cost-to-go 作为 ˜J。启发式策略 + 1SL policy improvement。

6.1 Problem Approximation

  • 把不确定量换成 nominal values，或用 limited simulation 简化期望。
  • 简化困难约束或动态。
  • 把耦合的大问题强制分解成较小子问题。

多车辆路径收集价值例子

原问题：m 辆车在图上移动，每个节点有 value，第一次经过节点的车获得该 value，目标最大化总收集价值，并满足初末时间、时间窗等约束。单车辆版本通常容易得多，所以 1SL 中可先枚举当前所有车辆动作，再在 resulting states 用“逐车优化路线”估计 value-to-go。

6.2 Flexible Manufacturing：约束近似与分解

当动态和成本对部件类型大致解耦，而耦合主要来自生产能力约束 U(α_k) 时，可以用内外 hypercube 近似约束集，让问题按部件类型分解。

Q(α_k) ⊂ U(α_k) ⊂ Ũ(α_k) Ũ(α_k) = { u_i | 0 ≤ u_i ≤ B_i(α_k) }

6.1 Aggregation：用聚合系统近似原系统

Aggregation 通过构造较小的 aggregate system 来近似原系统。它是一种线性 feature-based architecture。

原状态 i
disaggregation q_{si}
聚合状态 s
聚合转移/成本
aggregation φ 或 w
近似原 J

主要元素

  • 引入聚合状态 S_1,…,S_m，作为 aggregate system 的状态。
  • 定义 aggregate transition probabilities 和 costs。
  • 用 aggregation / disaggregation probabilities 连接原状态与聚合状态。
  • 求解 aggregate problem，用聚合状态的 optimal costs 线性组合近似原状态的 cost。
概率定义解释
Disaggregation probability q_{si}从聚合状态 s 代表到原状态 i 的概率，Σ_i q_{si}=1。原状态 i 在多大程度上代表聚合状态 s。
Aggregation probability w_{jt} / φ_{xj}从原状态 j 或 x 关联到聚合状态 t 或 S_j 的概率，Σ_t w_{jt}=1。原状态属于某聚合状态的 membership。

Hard aggregation 与代表性子集

类型特点近似形式
Hard aggregation聚合状态是原状态空间的 partition，每个原状态只属于一个聚合状态。分段常数近似。
Representative subsets聚合状态是互不相交的代表性子集；原状态可对多个子集有 membership。˜J(x)=Σ_j φ_{xj} r_j。
Soft aggregation允许状态以不同程度属于多个聚合状态。边界处更平滑。

Coarse Grid Approximation

在连续或密网格状态空间中，选少量代表点 S={x^1,…,x^M}，用几何权重表示任意状态，并只在代表点上求解。

x ≈ Σ_m w_m(x) x^m, Σ_m w_m(x)=1 ˜J_k(x)=Σ_m w_m(x) J_k(x^m)

6.2 Parametric Cost-to-Go Approximation

参数化近似使用一个函数族 ˜J(x,r)，其中 r=(r_1,…,r_m) 是可调权重。调整 r 会改变近似函数形状，使其尽量接近真实最优 cost-to-go。

˜J(x,r), r=(r_1,…,r_m) 目标：选择 architecture + 训练 r，使 ˜J(x,r) ≈ J*(x)
关键问题含义
Architecture 选择选择 ˜J 对 x 和 r 的函数形式，线性或非线性。
Weight training用启发式、仿真、最小二乘或系统算法调参。
Problem insightfeatures 的设计高度依赖对问题结构的理解。

Feature-based Linear Architecture

φ(x)=(φ_1(x),…,φ_m(x)) ˜J(x,r)=φ(x)' r = Σ_{j=1}^m φ_j(x) r_j
  • “线性/非线性”指 ˜J 对参数 r 的依赖方式。
  • 线性结构易训练，非线性结构如 neural networks 表达能力更强。
  • 好的 features 应尽量编码 cost-to-go 中主要的非线性。
  • 也可按状态空间分区构造 local features，在各自区域外为 0。

Computer Chess 例子

棋类程序无法搜索完整博弈树，因此常用有限步 lookahead，再用 position evaluator 估计终端局面分数。特征包括 material balance、mobility、safety 等。权重常近似线性组合，训练可能包含人工 trial-and-error。

7. Rollout Algorithms

7.1 定义：1SL + base policy cost-to-go

当 ˜J_k 是某个 heuristic / base policy 的 cost-to-go 时，one-step lookahead 策略就是 rollout。

Base policy π^B={μ_0^B,…,μ_{N-1}^B} H_k(x_k)=从 (x_k,k) 开始执行 π^B 的 cost-to-go Rollout： μ_k^R(x_k) ∈ argmin_{u_k} E[g_k(x_k,u_k,w_k)+H_{k+1}(f_k(x_k,u_k,w_k))]

7.2 Q-factor 计算流程

Q_k(x_k,u_k)=E[g_k(x_k,u_k,w_k)+H_{k+1}(f_k(x_k,u_k,w_k))] 选择 μ_k^R(x_k) ∈ argmin_{u_k} Q_k(x_k,u_k)。
候选 u_k
计算/模拟 next state
运行 base policy
得到 H_{k+1}
比较 Q-factor

Quiz Problem

N 个问题，答对问题 i 的概率为 p_i，奖励为 v_i，第一次答错即终止。若无额外约束，最优 index policy 是按以下指标递减排序：

Index_i = p_i v_i / (1-p_i)

若加入最多回答数、time windows、sequence-dependent rewards、precedence constraints，index policy 不一定最优。Rollout 可用 index policy 作为 base policy，对当前候选问题逐一试探，剩余问题按 index policy 估值。

7.1 Rollout 的 Cost Improvement Property

若 base heuristic 是 DP 意义上的 policy，则 rollout 的 cost-to-go 不大于 base policy。

目标：J_k^R(x_k) ≤ H_k(x_k) 对所有 x_k,k。 终端：J_N^R(x_N)=H_N(x_N)=g_N(x_N)。 归纳假设：J_{k+1}^R(x_{k+1})≤H_{k+1}(x_{k+1})。 对 rollout 控制 μ_k^R 与 base 控制 μ_k^B： J_k^R(x_k) = E[g_k(x_k,μ_k^R,w_k)+J_{k+1}^R(f_k(x_k,μ_k^R,w_k))] ≤ E[g_k(x_k,μ_k^R,w_k)+H_{k+1}(f_k(x_k,μ_k^R,w_k))] ≤ E[g_k(x_k,μ_k^B,w_k)+H_{k+1}(f_k(x_k,μ_k^B,w_k))] = H_k(x_k)。
  • 第一不等式来自归纳假设。
  • 第二不等式来自 rollout 对 Q-factor 的最小化选择。
  • 最后等式是 H_k 与 base policy 的定义。
易错点：离散确定性问题中，一个 heuristic algorithm 未必构成 DP 意义上的 policy。如果同一 state 下它因历史不同而选择不同控制，cost improvement property 可能失效。可通过 sequential consistency / sequential improvement，或 fortified rollout 恢复改进性质。

7.2 Rollout 在离散确定性问题中的例子

离散优化的树/最短路表示

任何离散优化问题都可分阶段构造 partial solution。树的叶子对应 feasible solutions。若有一个能完成 partial solution 的 heuristic，就可用 rollout 改进它。

Traveling Salesman Problem

逐步添加城市形成 tour。Rollout 对候选下一城市做 lookahead，并用启发式完成剩余 tour。确定性问题无需昂贵 stochastic simulation。

Breakthrough Problem

二叉树每条弧 free 或 blocked，目标找 free path。Greedy 优先右分支；rollout 用更多计算评估后续，理论上可用 O(N) 倍计算换 O(N) 倍找到 free path 的概率。

One-dimensional Walk

每步左/右一单位，N 步后终点 i 的成本为 g(i)。基策略“总向右”只让 rollout 找右侧局部最小；比较“总向右/总向左”的基策略可让 rollout 找全局最小。

Rolling Horizon with Rollout

计算 base heuristic cost-to-go 时，可以只看有限 rolling horizon。由于 base heuristic 本身是 suboptimal，horizon 不一定越长越好；材料中的 stopping problem 展示了较短视野反而可能更好。

核心启示：Rollout 不是魔法。基策略越能覆盖合理候选行为，rollout 的改进空间越大；但若未来估值由坏 heuristic 主导，有限视野反而可能减少误导。

7.3 随机 Rollout：Monte Carlo 与 Q-factor Approximation

三类 Q-factor 计算

情形Q-factor 计算特点
确定性问题对每个候选 u 运行一次 base policy。简单，适合组合优化。
随机 + Monte Carlo在线模拟多条轨迹估计 Q。受仿真方差影响；实时约束强。
随机 + 近似 Q用 CEC、scenario、features/least squares 近似 H 或 Q。更快但引入近似误差。

Monte Carlo 的关键问题

  • 目标往往不是精确估计每个 Q，而是可靠判断哪个候选控制更好。
  • 仿真误差可能改变 argmin。
  • 若候选间误差正相关，可用共同随机数或 cost-difference samples 降低比较方差。

Q-factor approximation

方法做法
Certainty-equivalence Q把剩余扰动固定为典型值，计算 base policy 轨迹成本。
Scenario approximation用多条 nominal disturbance sequences 加权平均。
Least-squares architecture在有限 state-time pairs 上计算 H 值，再拟合 H_k(x,r)。
结构约束例如已知 H≥0，则拟合后取 max{0,H}。

8. Model Predictive Control (MPC) 是 Rollout 特例

MPC 是有限前瞻控制的重要形式。在线性确定性系统中，它可解释为带稳定启发式的 rollout。

系统：x_{k+1}=A x_k + B u_k 阶段成本：x_k'Qx_k + u_k'Ru_k 约束：x_k∈X, u_k∈U(x_k)
  • 假设任意 x_0∈X 可在 m 步内被可行控制带到 0，即 x_m=0。
  • MPC 在当前状态 x_k 解 m-step optimal control，并约束 x_{k+m}=0。
  • 得到序列 u_k*,…,u_{k+m-1}* 后，只执行第一项 u_k*。
  • 下一时刻在新状态重新求解。
  • MPC 是 rollout：其 base heuristic 来自 m−1 step 的最优控制问题。
  • 若 base heuristic 稳定，则 rollout/MPC 也稳定。

9. Discretization：连续时间、状态、控制的近似

9.1 一般离散化问题

  • 若 time、state space 或 control space 连续，通常需要离散化。
  • Consistency 要求：网格变细时，离散问题的 cost-to-go 应收敛到原问题。
  • 离散化可能改变控制约束或可达集，尤其在连续时间问题中。

9.2 连续时间离散化陷阱：Convexification effect

例：ẋ(t)=u(t), u(t)∈{-1,1} 连续时间中，通过快速切换控制，时间 δ 后的可达位移可覆盖 [-δ,δ]。 若朴素离散化为 x(t+δ)=x(t)+δu(t), u(t)∈{-1,1}， 则只允许到达 x(t)±δ，错误缩小了可达集。

9.3 Space Discretization / Aggregation

给定有限网格 S̄⊂S，问题是 f(x,u,w) 可能不在 S̄ 中。解决方法是把任意状态表示为网格点凸组合，再用概率投影回网格。

x = Σ_{x_i∈S̄} φ_i(x) x_i, φ_i(x)≥0, Σ_i φ_i(x)=1 Reduced system： 从 x_i 按原系统到 x=f(x_i,u,w)，再以概率 φ_j(x) 跳到 x_j∈S̄。 原问题近似 cost： ˜J_k(x)=Σ_{x_i∈S̄} φ_i(x) J_k(x_i)
有趣观察：即使原问题是 deterministic，reduced problem 也通常是 stochastic，因为投影回网格是概率化的。该思想也可用于有限状态 POMDP 的 belief simplex 离散化。

10. Other Suboptimal Approaches

方法核心思想对应现代术语直觉
Fitted Value Iteration用 ˜J_k(x_k,r_k) 近似 J_k，并选择 r_k 最小化某种 DP equation error。从终端 ˜J_N=g_N 开始向后递推。Value function fitting。
Direct approximation of control policies先在代表状态 x^i 上求近似最优控制 μ̂_k(x^i)，再拟合参数化策略 μ̃_k(x,s)。Supervised policy fitting / imitation-style fitting。
Approximation in policy space不近似 J，直接参数化策略 μ̃_k(x,s)，在参数空间最小化总体 cost，可用 random search。Direct policy search。
重要结论：价值函数近似不是唯一道路。ADP 既可以近似 J，也可以直接近似 policy，或者在策略参数空间中搜索。

11. 横向对比与复习清单

11.1 主要方法对比

方法近似对象优势局限
CEC随机量 → 典型值；J 来自确定性问题。简单、工程成熟、存储低。忽略分布与信息价值；不保证优于 open-loop。
OLFC / POLFC忽略全部/部分未来测量。OLFC 至少优于纯 open-loop；POLFC 更灵活。需 belief 计算，仍可能复杂。
Limited lookahead截断 horizon + terminal ˜J。通用、在线可控。前瞻长时计算爆炸。
Aggregation小聚合系统 cost 近似原 J。降维明显、可解释。聚合设计依赖经验。
Parametric ˜J函数族 ˜J(x,r)。可扩展到大状态空间。architecture 与 training 关键。
Rolloutbase policy cost-to-go。有 policy improvement 性质。Q-factor 计算可能昂贵，heuristic 必须适合作为 policy。

11.2 复习检查清单

  • 能解释维数灾难中 O(N d^(n+m+r)) 的来源。
  • 能写出 1SL 的 argmin 公式，并说明 ˜J 的作用。
  • 能区分 CEC、OLFC、POLFC：谁固定随机量，谁忽略未来测量，谁保留部分未来信息。
  • 能说明 CEC 的优势与局限，以及 partially stochastic CEC 的典型用途。
  • 能解释未知参数下 caution、probing、dual control 的含义。
  • 能说明 two-phase control 的 identifiability 问题。
  • 能陈述 1SL 性能界及 δ 误差累积形式。
  • 能证明 rollout 的 cost improvement property。
  • 能解释 aggregation / disaggregation probabilities，以及 hard vs soft aggregation。
  • 能写出 feature-based linear architecture：˜J(x,r)=Σ_j φ_j(x)r_j。
  • 能解释 Quiz problem 的 index policy 与 rollout 改进。
  • 能说明 discretization 的 consistency 与 continuous-time convexification pitfall。

11.3 最后记忆框架

ADP 的统一句式：“我无法精确计算完整 DP 的 J，所以我用某种便宜方法构造 ˜J；然后用 one-step 或 limited-step lookahead 做当前决策；若 ˜J 来自 base policy，就得到 rollout，并有 policy improvement。”