⑶ 引理 3. 策略独立性：如果 W_t 独立于 X_0:t-1、U_0:t-1，则 ℙ(x_t+1^g ∈ A ㅣ x_0:t, u_0:t) = ℙ(x_t+1^g ∈ A ㅣ x_t, u_t) = ℙ(f_t(x_t, u_t, w_t) ∈ A ㅣ x_t, u_t) （马尔可夫性质），因此对策略 g 的依赖消失了。

① 在DDS中，如果知道当前状态，就可以立即知道下一个状态，但在SDS中，过去的状态很重要，因此历史的条件概率很重要。

② 即当w_t独立时，系统演化遵循自然规律+纯噪声，因此策略无关；但如果 w_t 取决于策略，则策略会改变噪声分布，因此未来的状态分布取决于策略。

③ 哲学： 从哲学上讲，“政策独立”意味着基于个人价值评估的多元化判断是不可能的，选择受到事实决定的限制。

⑷ 引理 4. 高斯过程 (GP)

①定义：状态过程{X_t}使得其任意有限子集服从联合高斯分布。

② 4-1. 即使每个 X_i 是高斯分布，也不意味着 {X_i}_i∈ℕ 是 GP。

○ 示例： X₂ = X₁ I{ㅣX₁ㅣ ≤ k} + (-X₁) I{ㅣX₁ㅣ > k}，Y = (X₁ + X₂) / 2 不是 GP。

③ 4-2. 对于 X_t+1 = AX_t + BU_t + GW_t，X₀ ~ 𝒩(0, Σ₀), W_t ~ 𝒩(0, Q)，{X_t} 是 GP。

④ 4-3. 根据反馈政策，{X_t} 通常不是 GP。

○ 示例： 如果 U_t := g_t(Y_t) = g_t(X_t) = X_t²，则 X₁ = AX₀ + BX₀² + GW₀，不是高斯分布。

○ 另一方面，在线性高斯 SDS 中，对于一般的开环策略，状态过程 {X_t} 始终是高斯的。

⑤（注）MMSE（最小均方估计量）

⑥（注）正交原理

⑦（注）LMMSE（线性最小均方估计器）

⑧ 如果 X 和 Y 共同为高斯分布，则 LMMSE = MMSE 成立。

⑸ 引理5. 多步预测

① 一般来说， ℙ(x_t+2^g ∈ A ㅣ x_t, u_t, u_t+1) ≠ ℙ(x_t+2^g ∈ A ㅣ x_0:t, u_0:t+1)

» ○ 证明： 让我们考虑 x_t → y_t → u_t → x_t+1 → y_t+1 → u_t+1 → x_t+2。由于与 u_0:t-1 不独立的 u_t+1 = g_t(y_0:t+1, u_0:t) 意味着通过 xt+1 = f(xt, ut, wt) 有关 w_t 的信息，因此对 u_t+1 的条件作用打破了过去的独立性w_t：这里的“过去”表示x_0:t-1，u_0:t-1。

○ 反例1. 在开环控制中，u_t+1 = g_t(u_0:t)成立，因此它不能隐含有关w_t的信息，因此等式成立。

○ 反例2. 当w_t为常数时

○ 反例3. 当u_t被定义为具有马尔可夫性质和无记忆反馈时，例如u_t = μ_t(x_t)：则情况如下 y_t = x_t = u_t

② 开环控制多步预测

③ 查普曼-柯尔莫哥洛夫分解

⑹ 引理 6. 线性高斯状态空间模型

①（注）高斯-马尔可夫过程

○ 条件 1. {X_t} 是高斯过程。

○ 条件2. 马尔可夫性质： P(X_n+1 ∈ A ㅣ X₀,…, X_n) = P(X_n+1 ∈ A ㅣ X_n)

② 系统定义

○ 马尔可夫性质：即使有反馈策略也适用。

○ 多步马尔可夫性质

○ 平均传播

○ 互协方差 Cov(X_t+m, X_t)

○ 协方差传播

③ DALE（离散时间代数李亚普诺夫方程）

○ 如果方阵 A 的所有特征值（包括复数）的绝对值都小于 1，则该矩阵定义为稳定：因为 A^∞ = 0。

○ 若 A 稳定，则 Σ_∞ = lim_t→∞ Σ_t = lim_t→∞ 𝔼[(X_t - 𝔼[X_t])(X_t - 𝔼[X_t])ᵀ] 唯一存在。

○ Σ_∞唯一性证明

○ 备注1. A 的稳定性是充分，但非必要条件。

○ 即使 A 不稳定，Σ_∞ 仍可能唯一存在。

○ 给出了一个简单的例子 Σ₀ = 0, Q = 0，在这种情况下 Σ_k ≡ 0 独立于 A。（首先没有噪声。）

○ 备注 2. Σ_∞ 可能不是严格正定的。

○ 一个简单的例子是 A = O，rank(GQG^T) < n。（噪音并未触及该州的所有方向。）

○ 备注 3. 如果输入扰动 w_k 影响状态向量的所有分量，则 A 的稳定性对于 Σ_k 的收敛是必要的，并且极限协方差 Σ_∞ 将是正定的 → 与可重复性的概念相关。

④ 可达性

○ 定义：在有限时间内能否达到。与可控性和可观测性相关。

○ 定理 1. 以下都是等价的：假设 w ∈ ℝ^s

○ 在条件 3 中，噪声序列 w 应解释为应用于系统的控制输入；由于它们，系统可以在 n 个时间步长内从 0 转向给定状态 x。

○ 定理2. 李亚普诺夫稳定性检验

○ 请注意，在条件 2 中，它是 PD（正定），而不是 PSD（正半定）。

⑺ 引理7. 图论

① 强关联（= 不可约、可传播）

○ 从图中任意节点 i 可以到达任意其他节点 j 的条件。

○ 如果 j 从 j ∀i, j 可达，则马尔可夫链是不可约的。

图 1. “不可约”的示例

图 2. “可简化”示例（状态 3 是接收器）

② 周期：特定节点i的周期是从i返回i的所有路径长度的最大公约数

○ 示例：有两个节点 A、B，通过两条边 A=B 连接，每个节点的周期为 2。

○ 在给定适当的置换矩阵 Q 的情况下，当允许状态重排（例如 Q^TPQ）时，周期为 m 的转移矩阵应具有以下形式。

图 3. 周期为 m 的转移矩阵示例

S₁→S₂→···→S_m→S₁→···有这样一个循环。

③ 非周期：所有节点的周期为1。» ○ 对于不可约马尔可夫链，如果一个状态是非周期的，则所有状态都是非周期的。

○ 示例：如果每个节点都有一条到自身的路径，则它是非周期的。

④ 平稳状态：如果 Pr(x_n ㅣ x_n-1) 与 n 无关，则马尔可夫过程是平稳的（时不变的）。

⑤ 常规

○ 常规 ⊂ 不可缩减

○ 对于某个自然数 k，转移矩阵 M 的幂 M^k 的每个条目都是正数（即非零）。

⑥ 转移矩阵

⑦ 马尔可夫策略：u_t = g_t(x_t)

⑧ 利用马尔可夫过程可以证明热力学第二定律（熵增定律）。

○ 因为可以模拟扩散定律：假设有均匀平稳分布。

○ 相关概念：随机游走

⑨ Perron-Frobenius 定理

○ 定理1. 如果具有转移矩阵P的有限马尔可夫链是强连通的，则恰好存在一个平稳分布q。

○ 平稳分布满足 Pq = q。

○ 示例：如果 P = I（单位矩阵） ε ℝ^2×2，则它是可约的，因此对于所有 x ε [0, 1]，存在无限多个 (x, 1-x) 形式的平稳分布。

○ 定理 2. 如果具有转移矩阵 P 的有限马尔可夫链是强连通且非周期的，则称为 遍历马尔可夫链 并满足：

○ P_ij：从节点 j 转移到节点 i 的概率。 Σ_i P_ij = 1。注意，P_ij 表示下面其他引理中从节点 i 转移到节点 j 的概率。

○ 2-1. 当 k → ∞ 时，P^k 的 (i,j) 项 P_ij(k) 收敛到 q_i：请注意，对于固定 i，无论 j 如何，它都会收敛到相同的值。

○ 2-2. 无论初始状态 x₀ 为何，第 k 状态 x_k 都会随着 k → ∞ 收敛到 q。

○ 示例：如果 P=((0,1),(1,0))，则它是周期性的（周期=2）。因此，存在唯一的平稳分布 π=(0.5,0.5)，但 $\lim_{k\to\infty} p(k)$ 不会收敛到单一极限，而是分裂成两个子序列（例如，$p^{\text{even }k}=(1,0)$ 和 $p^{\text{odd }k}=(0,1)$）。

⑻ 引理 8. 遵循确定性马尔可夫性质的值函数

① 预期成本和转移概率

② 递归和向后迭代：动态规划

○ J_T^g ∈ ℝ^1×1

○ π₀ ε ℝ^1×n：马尔可夫链的初始分布

○ V₀^g ε ℝ^n×1：收集政策 g 下每个状态的预期累积成本的状态价值函数向量» ○ 当 T = ∞ 时，J^g 变为无穷大，无法找到最优策略 g；由此，引入了贝尔曼方程、切萨罗极限概念。

③ 贝尔曼方程：下面主要描述贴现成本问题。

○ （注）时间齐次：{x_t^g}_t≥0 和 {x_t^g}_{t≥τ,∀τεℤ₊} 遵循相同的分布。也意味着严格静止。

○ 条件 1. 时间齐次转变： P_t(j ㅣ i, u) = P(j ㅣ i, u) ∀t

○ 条件 2. 时间同质成本：C_t(x, y) = C(x, y) ∀t

○ 条件 3. 平稳策略：g_t = g ∀t

○ 如果以上都成立，则可以得到下面的定点方程。

○ J^g：成本的现值；一般用于经济领域。

○ 由于 P^g 稳定，所有特征值的绝对值均小于 1，因此 det(I - βP^g) = β det((1/β)I - P^g) ≠ 0

○ V^g ε ℝ^n×1：状态价值函数向量，收集政策 g 下每个状态的预期贴现累积成本

○ P^g ∈ ℝ^n×n：转移矩阵； (i,j) 条目是从 i 转移到 j 的概率。

④ 塞萨罗极限：与长期平均成本问题有关。

⑤ 泊松方程：与平均成本有关。

○ J^g 是独一无二的。

○ L^g：相对值函数。 L^g 不是唯一的（∵ L^g + α1 ∀α ε ℝ 也是泊松方程的一个解）

○ 解的存在性

⑼ 引理 9. 当不是不可约时

① 如果 P^g 不是不可约的，则状态空间 S 分裂为瞬态 T 和一个或多个循环通信类 C₁，…

② 瞬态：仅访问有限次。最终该过程离开瞬态并进入循环状态。

○ 定理： 有限状态马尔可夫链的平稳分布 π^g 将概率 0 分配给所有瞬态。

○ (i) 证明：鸽巢原理。有限性至关重要（并且需要使用）。»> ○ 假设某个暂态i满足Q_i=0。由于循环通信类是一个闭集，因此一旦进程进入循环类，就不会与外部节点发生通信。因此，该假设意味着瞬态 i 对于所有 K 个转换仅转变为瞬态。因此，根据鸽巢原理，K+1 个鸽巢中至少有一个瞬态被访问两次（从开始算起），这会产生完全包含在瞬态集中的有向循环。这个循环是封闭的（在这 K 个步骤中没有边将其留给循环类），因此它形成了一个与给定循环类不相交的封闭通信类。在有限马尔可夫链中，每个封闭的通信类都是循环的；因此，我们产生了第二个循环类，这与唯一性假设相矛盾。因此，假设 Q_i 为假，因此对于每个瞬态 i. Q_i>0

○ (ii) 证明

③循环状态：由于循环通信类是闭集，因此不会与外部节点发生通信。

○ i → j：表示从 i 到 j 存在一条概率为正的路径。

○ i ↔︎ j：表示i → j 且j → i； i 和 j 进行交流。

○ 正循环：返回该状态的平均时间是有限的。

○ 以正循环状态开始的链具有独特的平稳分布。

○ 零循环：返回该状态的平均时间是无限的。不存在平稳分布。

○ 示例： X_n+1 = X_n + ψ_n, X₀ = 0, ℙ(ψ_n = +1) = ℙ(ψ_n = −1) = 0.5 → 返回原点的概率为 1，但期望时间为 Infini。

○ 吸收状态：一旦进入，就永远处于这种状态

④ 例1. 静止状态集F

⑤ 示例2. 有限状态空间

令 S = {0, 1, ···, I}。由于 V^g(0) = 0 且 C(0, g(0)) = 0，我们只能关注 Ś = S \ {0} = {1, ···, I}，即非吸收态。令 Ṽ^g 为 Ś 中状态的值向量，并令 R^g 为 P^g 的子矩阵，用于 Ś 内状态之间的转换。（即，描述链在达到 0 之前如何仅在非吸收状态之间移动的矩阵。）那么这些状态的方程组为 Ṽ^g = c̃ + R^gṼ^g。为了显示Ṽ^g的唯一性，假设有两个解Ṽ₁^g，Ṽ₂^g。设它们的差为 U^g = Ṽ₁^g - Ṽ₂^g；两个方程相减得到 U^g = R^gU^g = ⋯ = (R^g)ⁿU^g = ⋯ = 0 (∵ lim_n→Infini (R^g)ⁿ = 0，无限下降法）⇔ Ṽ₁^g = Ṽ₂^g。因此，在状态 0 为吸收且所有其他状态都可以达到 0 的有限状态空间中，首次通过时间成本方程具有唯一的非负解。

⑥ 例3. 可数无限状态空间

图4. 可数无限状态空间图

独特性并非微不足道。假设解是有界的通常可以显示出唯一性。考虑两个解之差的方程 U^g = R^gU^g。将其连接到图上可得出 U^g(ℓ+1) - U^g(ℓ) = (λ - 1)(U^g(ℓ) - U^g(ℓ-1))。连续差值 Δ(ℓ) = U^g(ℓ+1) - U^g(ℓ) 形成比率为 (λ - 1) 的几何序列。如果 |λ - 1| < 1，这些差异收敛于 0，表明有界解。如果 |λ - 1| ≥ 1，差异可能会发散，这意味着唯一性可能会失败。

⑽ 引理 10. Martingale

① 杜布定理

○ σ(X₁, X₂, ···, X_n)：使 X₁, X₂, ···, X_n 可测量的最小 σ 代数。

○ Doob 定理：σ(X₁, X₂, ···, X_n) 等价于 g(X₁, X₂, ···, X_n) 形式的所有函数的集合。

○ σ 代数越大，可测量的函数就越多；即它包含的信息越多。

② 过滤

○ 按包含顺序递增的 σ 代数集合。

○ 按 ⊆ 排序；如果 ℱ₁ ⊆ ℱ₂，则 ℱ₂ 之后是相对于 ℱ₁ 的。

○ 为了方便起见，令时间索引 t = 0, 1, 2, ⋯；则过滤为 {ℱ_t}_t∈ℤ₊ 并且对于所有 s ≤ t 满足 ℱ_s ⊆ ℱ_t。

○ 直觉：代表信息随着观察的积累而增加的情况。

③ 鞅

○ 条件期望的性质

○ 对于任意随机变量 Y，𝔼[Y ㅣ X₁, ···, X_n] = 𝔼[Y ㅣ σ(X₁, ···, X_n)] 成立。

○ 原因：因为 σ(X₁, ···, X_n) 等价于 X₁, ···, X_n 生成的所有函数的集合。

○ 另外，当 σ(Y) ⊂ σ(Z) 时，𝔼[𝔼[X ㅣ Z] ㅣ Y] = 𝔼[𝔼[X ㅣ Y] ㅣ Z] = 𝔼[X ㅣ Y]成立。

○ Martingale：随机过程 {X_t}_t∈ℤ₊ 适应过滤 {ℱ_t}_t∈ℤ₊ 满足以下所有条件

○ 条件 1. X_t 对于所有 t ∈ ℤ⁺ 是 ℱ_t 可测量的。

○ 如果 s ≤ t ≤ s′ 且 ℱ_s ⊆ ℱ_t ⊆ ℱ_s′，则 X_t ∈ ℱ_t 不是 ℱ_s 可测（由于信息不足），而是ℱ_s′-可测量。

○ 条件 2. 𝔼[ㅣX_tㅣ] 对于所有 t ∈ ℤ₊ 都是有限的。

○ 条件 3. 𝔼[X_t ㅣ ℱ_s] = X_s，几乎可以肯定，对于所有 s ≤ t 且所有 t ∈ ℤ₊

○ 解释： 仅给定时间 s (ℱ_s) 之前的信息，X_t 的最优预测等于 X_s（即，预测被限制为 X_s；𝔼[X_t ㅣ ℱ_s] 是X_t 进入 ℱ_s 可测量随机变量空间（“最佳预测”））。

○ 备注： 仅当根据过去预测未来时才需要鞅性质。特别是，对于 s > t，无论 X_t 是否是鞅（假设可积），我们都有 𝔼[X_t ㅣ ℱ_s] = X_t。»» ○ 对于 s < t，𝔼[X_s ㅣ ℱ_t] = X_s 也成立，因为 X_s 是 ℱ_s 可测的，但由于 ℱ_s ⊆ ℱ_t 信息不足。

○ 注意：i.i.d.过程通常不是鞅（常数过程除外）。

○ 应用：𝔼[U^g(X_t^g) ㅣ X_t-1^g] = U^g(X_t-1^g)

④ 鞅与随机控制理论

⑾ 引理 11. (Fully observed) ― 最优策略

① 问题定义：完美观察下的cost-to-go函数。由于控制输入 {U_t, …, U₁} 可以通过 {X_t, …, X₀} 测量，因此以下公式成立：

② 遵循马尔可夫性质，贝尔曼方程成立。这里，J_t^g，V_t^{g^M}(X_t)是从t到未来的成本。

③ 马尔可夫化定理（马尔可夫政策充分性，还原为马尔可夫政策）

○ 定理： 在有限范围 MDP 中，对于任何一般（可能依赖历史和随机）策略 g，都存在一个行为马尔可夫策略 g^M，使得在相同的初始分布 μ 下，所有 t = 0, …, T−1 和 X_T 的 (X_t, U_t) 联合分布是相同的。因此，性能（成本）J^g = 𝔼^g[Σ_{t=0 to T−1} C_t(X_t, U_t) + C_T(X_T)] 等于 J^{g^M}。因此，在不损失最优性的情况下，人们可以将注意力限制在随机马尔可夫策略上。

○ 证明

④ 比较原理

○ 定理： 通过从目标向后推导并确保贝尔曼不等式在每一步都成立，初始值 V₀ 作为所有可能政策性能的下界。在每个阶段实现平等的一系列行动共同构成了最优政策。因此，可以通过组合局部最优（阶段式）选择来验证或构造最优性。

○ 证明：使用【数学归纳法】(https://www.youtube.com/watch?v=t9RBuyBmFdQ) 向后推导

○ 情况 1. t = T: 由于 J_T^g = 𝔼^g[C_T(X_T^g) ㅣ X_T^g, …, X₁^g, X₀] = C_T(X_T^g) ≥ V_T(X_T^g) (∵ (V1)) 成立，归纳假设仍然成立。

○ 情况 2. 如果归纳假设建立在 ℓ = t+1, …, T 上，则该假设对于 ℓ = t 仍然成立，可以验证如下：

○ 推论

⑤ 哈密尔顿-雅可比-贝尔曼 (HJB) 方程

○ 定理：HJB 适用于有限/可数无限、状态/动作空间。贝尔曼方程的连续时间版本。

○ 定理1的证明已在比较原理中给出，因此以下解释仅与定理2相关。

○ p：某个马尔可夫策略 g^M = {g_t} 是最优的。

○ q: 给定 ∀x, t, g_t(x) ∈ arg inf_uε𝒰 {c_t(x, u) + 𝔼_{W_t}[V_t+1(f_t(x, u, W_t))]} （即实现逐步贝尔曼最小化）

○ 定理 2 (q ⇒ p) 的充分性证明：当每个阶段给出 x_t 时，任何满足下确界的策略都是最优的（∵推论）。那么，u_t应该是当前状态x_t的可测函数，最优策略应该是马尔可夫策略。

○ 定理 2 的必要性证明 (p ⇒ q)：如果一个策略是最优马尔可夫策略，它应该在每个阶段实现下确界 (w.p.1)；否则，我们可以构造一个具有正概率集的更好的策略 g’，这意味着 J(g’) < J(g)。

○ 推论

○ 应用1. 如果1→6的最优路径为1→2→3→6，则根据HJB方程，2→6的最优路径应为2→3→6。

○ 应用 2. 政策评估：下面讨论。

○ 应用3. 由HJB方程得到的V_t(x)称为价值函数。它有效地减少了搜索空间的大小。

○ 应用 4. Q 值（状态-动作值函数）： Q_t(x, u) = C_t(x, u) + 𝔼_{W_t}[V_t+1(f_t(x, u, W_t))], V_t(x) = inf_uε𝒰 Q_t(x, u)

○ 应用5. 对于给定的有限状态/动作空间，inf = min，最优策略是确定性马尔可夫策略。

○ 应用 6. 随机马尔可夫策略下的价值函数：对于 u ~ μ_t(u ㅣ i)，

⑥（注）【布莱克威尔无关信息原则】(https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-35/issue-2/Memoryless-Strategies-in-Finite-Stage-Dynamic-Programming/10.1214/aoms/1177703586.full)» ○ 如果 Y 独立于状态并且不直接出现在奖励中，则 Y 与决策无关：忽略 y 的决策规则总是至少一样好。换句话说，拥有更多信息并不总是更好。

○ 示例： 假设医生必须决定患者的治疗方案。每天早上，医生可以观察患者的健康状况X，此外还知道今天是星期几Y。可用的操作是“治疗”和“不治疗”。如果一周中的某一天与预期奖励（生存概率）和健康状况无关，则仅根据 X 做出决策会产生与同时使用 X 和 Y 相同的预期生存概率。

○ 然而，根据动作空间和可测性等技术假设，该陈述可能需要用ε-最优策略来制定，并且当涉及可数/不可数和可测性陷阱时（例如Borel集的投影可以是非Borel），存在全局近似优势失败的反例。

○ 结论： 在动态规划问题中，可以从数学上证明无记忆策略足以优化预期奖励。

○ 应用： 在有限视野马尔可夫决策问题中，可以轻松证明马尔可夫策略是最优的。（[参考]（https://infostructuralist.wordpress.com/2010/11/08/deadly-ninja-weapons-blackwells-principle-of-irrelevant-information/））

⑿ 引理 12. (Partially observed) ― 信息状态

① {z_t}_t={0,…,T} 满足以下给定的部分观察上下文

○ 背景：历史 H_t := {y₀, …, y_t, u₀, …, u_t-1} 随着时间的推移而增加，其域呈指数增长。（维度的诅咒）

○ 条件 1. 压缩： z_t = ℓ_t(H_t) ∀t

○ 条件 2. 政策/策略独立：z_t+1 = 𝒯_t(z_t, y_t+1, u_t) (■当前状态，■新信息）也就是说，z_t可以使用当前状态和新信息递归更新，而不需要直接引用整个过去的历史。

○ 条件 3. 相对于 g_0:t-1 的独立性：∀t = 0, …, T-1

② 条件 1. z_t = H_t := {y₀, …, y_t, u₀, …, u_t-1}

○ π₀(i) 如下：

③ 候选人 2. 信念状态：z_t = π_t s.t. π_t(i) := ℙ(X_t = i ㅣ H_t) = ℙ(X_t = i ㅣ y_0:t, u_0:t-1) ∀i ∈ S

○ 满足条件 1：时间上的 z_t = ℓ_t(H_t)（压缩）

○ 满足条件2：直接利用贝叶斯法则可以得到满足 π_t+1 = 𝒯_t(π_t, y_t+1, u_t) 的𝒯_t。这是置信状态的更新方程，通常称为非线性滤波器。

○ 满足条件3：使用逆向数学归纳法。

○ 情况 1. t = T-1：所有项都不依赖于 g_0:T-1。

○ 情况 2. 后向归纳法可以建立如下：

○ 贝尔曼信念方程-MDP： 该定理的关键信息是，尽管 MDP 的整体策略空间 𝒢 包含从历史到行动的所有映射，因此非常大，但信念 Π_t 是足够的，因此我们通过将注意力限制在“信念 → 行动”形式的分离策略上，不会失去最优性。

○ 证明

○ 应用1.（单向）分离定理

○ 应用2. 置信空间中的成本函数

○ 应用 3. 与信念状态不同，以下内容依赖于策略，因为它依赖于 g_t-1。

○ 应用 4. 与信念状态不同，以下是依赖于策略的：因为如果不包括 u_t 作为条件 π_t+1 = 𝔼_{u_t ~ p(· ㅣ Y_0:t) [𝒯_t(π_t, y_t+1, u_t)] 成立，因此信息状态转换受策略影响。}

○ 应用 5. 一般来说，P^g(X_t+1 ∈ A ㅣ H_t, u_t) ≠ P^g(X_t+1 ∈ A ㅣ y_t, u_t), H_t = （Y_0:t、U_0:t-1）»> ○ 证明： 假设 t = 1。我们考虑 x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯。给定 H₁ = (y_0:1, u₀)，我们可以通过 y₀ → x₀ 确定 x₀ 的分布。因此，我们可以通过 y₁ → x₁ 和 (x₀, u₀) → x₁ 更准确地确定 x₁ 的分布。之后，我们可以通过x₁、u₁、w₁确定x₂的分布。然而，在右侧，我们只能使用 y₁ → x₁ 以及 u₁ 的有限信息来确定 x₁ 的分布，导致 x₂ 的分布不太准确。因此，双方意见不一。

○ 应用 6. P^g(X_t+1 A ㅣ H_t, u_t) = P^g(X_t+1 A ㅣ y_0:t, u_t)

○ 证明： 让我们考虑 x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯。给定策略 g，在右侧，我们可以分别通过 y₀ → u₀ 和 y₀ → x₀ 确定 u₀ 和 x₀ 的分布。因此，我们可以通过 (x₀, u₀) → x₁ 来确定 x₁ 的分布。现在利用 u_t = g_t(y0:t, u_0:t-1) 和 x_t+1 = f_t(x_t, u_t, w_t) ，我们可以确定所有变量的分布，从而彻底得到 x_t+1 的分布。从左侧看是一样的。

○ 结论： 信息状态 Z_t^g := (Y_0:t^g, U_0:t-1^g) 是 Y_0:t^g 的函数。

○ 应用 7. P(X_t+1 ∈ A ㅣ H_t, u_t) ≠ P(X_t+1 ∈ A ㅣ y_0:t, u_t)

○ 证明： 让我们考虑 x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯。在右侧，我们可以通过 y₀ → x₀ 确定 x₀ 的分布，但只能在策略集的概率上通过 y0 → u0 确定 u₀ 的分布。然而，u₀ 恰好在左侧给出。因此，双方意见不一。我们可以得出结论，P^g(X_t+1 ∈ A ㅣ H_t, u_t) 是策略无关的，而 P^g(X_t+1 ∈ A ㅣ y_0:t, u_t) 是策略依赖的。

⒀ 引理 13. 动态规划

① 如果 V_t(i) = max{r(i), a + bΣ_j∈S ℙ(j ㅣ i) V_t+1(j)} = max{r(i), a + b𝔼[V_t+1(j) ㅣ i]}, V_t(i) ≥ V_t+1(i)成立。

② 如果 V_t(x) = max{-c + p(x)(1 + V_t+1(x-1)) + (1 - p(x))V_t+1(x), V_t+1(x)}, V_N+1(x) = 0，则成立：

○ 时间上的单调性： V_t(x) ≥ V_t+1(x) （证明)

○ x 上的单调性： V_t(x) ≥ V_t(x-1) (证明)

○ 边际值的上限值： 1 ≥ V_t(x) - V_t(x-1) （证明)

○ x 上的凹性不成立： V_t(x) - V_t(x-1) ≤ V_t(x-1) - V_t(x-2) （存在反例）» ○ 边际价值与时间的关系： V_t(x) - V_t(x-1) ≥ V_t+1(x) - V_t+1(x-1) (证明)

○ 阈值的存在： G_t(x) = p(x)(1 - Δ_t+1(x)) 在 x 上是非递减的（证明）

③ 凸面

○ 引理 1. 给定两个凸函数 f₁ 和 f₂，max{f₁, f₂} 也是凸函数。

图 5. 两个凸函数的最大值是凸函数。

○ 引理 2. 两个凸函数之和是凸函数。

○ 引理 3. 如果 V(x) 是非减凸函数，则 V(max{x, a}), ∀a 也是凸凸函数：在几何上很容易理解。

○ 引理 4. 若 L(π) 为凸函数，则 L(π)=sup_i∈I {α_i π + β_i}, α_i, β_i ε ℝ 成立。

○ 以上来自不等式 f(x) ≥ f(x₀) + f’(x₀)(x - x₀);这并不是说该公式适用于任意选择 α_i 和 β_i。

○ 示例：如果 L(π) = π²，则 π² = super_x₀εℝ {2x₀π - x₀²}。

○ 实用点：使用在线性（仿射）表示中保留凸性的变换，可以表明对原始凸函数应用相同的变换也可以保留凸性。示例如下。

⒁ 引理14. (Stochastic policy) DCOE（贴现成本最优方程，无限范围贴现成本贝尔曼方程）

①【Banach不动点定理】(https://jb243.github.io/pages/1827)

○ 定理

○ 设 F 为 Banach 空间。这里，Banach空间是指完全赋范空间，集合“完备”意味着集合中的每个柯西序列都收敛于集合中的某个元素。令 T: F → F 为满足以下关系的变换：ㅣㅣTx - Tyㅣㅣ ≤ βㅣㅣx - yㅣㅣ，∃β ∈ (0,1)，∀x, y ∈ F。则有：

○ 存在唯一不动点 w ∈ F 满足 Tw = w。

○ 对于任意 x ∈ X，lim_n→∞ Tⁿx = w。

○ 这本质上意味着以下内容：

○ 满足上述条件的变换称为收缩。严格来说，它要求sup β(x, y) < 1。

○ T 是连续的，具体来说是 Lipschitz 连续的。

○ 证明

○ 令 x ∈ F, α = ㅣㅣx - Txㅣㅣ。那么，我们有ㅣㅣTⁿx - Tⁿ⁺¹xㅣㅣ ≤ βⁿα。如果我们设置 {x, Tx, T²x, ···} 的柯西序列，我们可以得到： ∀ϵ > 0, ∃N_ϵ s.t。 ∀n, m ≥ N_ϵ, ㅣㅣTⁿx - T^mxㅣㅣ < ϵ。不失一般性，我们可以设置n>m。那么，我们有

»> ○ 因此，我们有 N 服从 αβ^N / (1 - β) < ϵ。由于 F 是 Banach 空间，因此 w 服从 lim_n→∞ Tⁿx = w。由于 T(lim_n→∞ Tⁿx) = Tx = lim_n→∞ Tⁿ⁺¹x = w，所以 w 是一个不动点。如果我们将 w₁、w₂ 设置为 T 的不动点，则有 ㅣㅣw₁ - w₂ㅣㅣ = ㅣㅣTw₁ - Tw₂ㅣㅣ = ⋯ = ㅣㅣTⁿw₁ - Tnw₂ㅣㅣ = ⋯ = 0，因此 w₁ 和 w₂ 相同。

○ 直觉

②贝尔曼算子和收缩定理

○ 定理

○ 令 F 为一组函数，例如 F = {z: S → ℝ}。这里，S = {1, 2, ···, I} 且 z := (z(1), ···, z(I))^T。让我们定义以下范数： ㅣㅣzㅣㅣ = max_i ㅣz(i)ㅣ（即ㅣㅣ·ㅣㅣ_∞）让我们为每个分量定义运算符 T: F → F。然后，对于所有 i ∈ S，我们有 Tz(i) = min_uε𝒰 [C(i, u) + βΣ_jεS ℙ(j ㅣ i, u) z(j)]。那么，T就是收缩映射。

○ 证明

○ 令 ℝ^I 为范数为ㅣㅣ·ㅣㅣ_∞ 的 Banach 空间。若z,y ∈ F，则可证明定理如下：

○ 即使我们用成本最大化的特殊定义替换它，收缩定理在相同的证明结构下仍然成立。

③ 推论

○ ∀i ∈ S, W_∞(i) = min_uε𝒰 C(i, u) + βΣ_jεS ℙ(j ㅣ i, u) W_∞(i) 有 w_∞ 的唯一解。

○ DCOE与几何分布的关系

○ W_∞(i) = inf_gε𝒢 J^g(i) = inf_gε𝒢 𝔼^g[Σ_{t=0 到 ∞} β^tc(x_t, u_t) ㅣ X₀ = i], ∀i ∈ S

○ J^g(i) 和有界的定义

○ W_∞的定义：根据收缩映射的性质，递减序列{W_n}收敛于W_∞。

○ J^g(i) ≥ W_∞（下界）

○ W_∞(i) ≥ inf_g J^g(i)（上界）：可表示为 J(X₀, π*) ≤ Σ_{τ=0 to t-1} β^τ C_τ(X_τ, π_τ*) + β^t𝔼[V_t(X_t, π_t)]。

○ 结论： W_∞(i) = inf_g J^g(i)

○ 最优平稳马尔可夫策略 g*(i) ε argmin_uε𝒢 c(i, u) + βΣ_jεS ℙ(j ㅣ i, u)V_∞(j)

○ ⇔ W_∞ = c^g* + βP^g*w_∞» ○ ⇔ W_∞ = (I - βP^g*)^-1 c^g*

○ 最优算子T定义如下：

○ 根据定义，TZ ≤ T^gZ

○ T^g 和 T 都是 ℓ_∞ 范数上的收缩映射。

○ T^g 和 T 都满足单调性：如果 z ≤ y，则 T^gz ≤ T^gy 且 Tz ≤ Ty

○ 证明1

○ 证明2

○ 若 h, g ∈ 𝒢_SMP，且 T_hW_∞^g ≤ W_∞^g，W_∞^h ≤ W_∞^g 成立： T_hⁿW_∞^g ≤ ⋯ ≤ T_hW_∞^g ≤ W_∞^g；然后，我们可以将n设为无穷大来得到结论。

④ 算法1. 值迭代

○ 通过重复应用贝尔曼最优算子 T 来更新价值函数的方法，即 V_k+1 = TV_k。

○ 由于收缩映射性质，如果 β < 1，则 V_k → V^* 收敛到唯一不动点，并且相对于 V^* 的贪心策略是最优的。

○ 典型的停止标准是ㅣㅣV_k+1 - V_kㅣㅣ_∞ < ε 等。

○ 特点： 优点是计算简单，缺点是需要多次迭代。

⑤ 算法2. 策略迭代

○ 步骤 1. 选择任意平稳马尔可夫策略 g_n ∈ 𝒢_SMP。

○ 步骤 2. 策略评估： 计算 W_∞^g_n = (I - βP^g_n)^-1C^g_n。

○ 步骤3. 停止准则：如果TW_∞^g_n = W_∞^g_n，停止并以g_n为最优策略；否则请转至步骤 4。

○ 步骤4. 策略改进：定义g_n+1如下。

○ 定理： 序列 ({g₀, g₁, g₂, …}) 经过有限多次迭代后达到最优策略。

○ 证明： 当停止条件 W_∞^g_n = TW_∞^g_n 成立时，g_n 已经是最优策略。否则，在步骤 4 中，我们有 T_{g_n+1} W_∞^g_n ≤ W_∞^g_n，并且至少有一个状态是严格不等式的。由于可能的策略数量是有限的（ㅣUㅣ^ㅣSㅣ），并且每一步的成本都会严格改善（至少在一个状态下），因此无法重新审视相同的策略。因此，该算法通过有限多个步骤达到停止条件并产生最优策略。

○ 特点： 它的优点是需要迭代次数少得多，但每次迭代时必须在两个算子之间交替（策略评估（由于逆矩阵计算更昂贵）和策略改进）。

⑥ 算法3. 线性规划

○ 定理

○ 证明

○ 实现： 拉格朗日乘子法，双最优变量。

⒂ 引理15. (Stochastic policy) ACOE（平均成本最优方程，无限范围平均成本贝尔曼方程）

① 概述

○ 对于有限状态空间、有限动作空间和有界成本函数，定义 J^g 如下：

○ 在不可约马尔可夫链中，考虑泊松方程 J^g1 + W^g = C^g + P^gW^g。

○ 如果 W^g 是解，则 W^g + α1 也是任意常数 α 的解，但 W^g 是唯一确定的，直到该可加常数。

○ ACOE 的推导：相对值函数 W_N(i) - W_N(j) 收敛，N → ∞，对应 W(i) - W(j)。

○ 意义1. J* 是最优成本。

○ 意义2. 最优SMP g* 必须满足ACOE。

○ 假设最优策略 g* 给出如下，并假设该等式对于某些状态 i 不成立。

○ 那么矛盾就出现了，因为g*失去了最优性，因此最优的g*必须满足ACOE。

○ 意义3. 我们可以使用策略迭代。

② 算法1. 策略迭代算法

○ 步骤 1. 选择任意策略 g₀ ∈ 𝒢_SMP。

○ 步骤2. 策略评估： 给定g_n，求解以下泊松方程得到(J^g_n, W^g_n)。由于我们有 I 个方程，但有 (I+1) 个未知数（J^g_n、W^g_n(1)、…、W^g_n(I)），我们固定一个分量，例如设 W^g_n(I) = 0)，唯一确定 J^gn1 + W^g_n = C^g_n + 的解P^g_nW^g_n

○ 步骤3. 停止标准： 如果g_n 满足ACOE，则g_n 是最优SMP。否则，请转到步骤 4。 ACOE: J^g_n + W^g_n(i) = min_uε𝒰 {C(i, u) + Σ_jεS P(j ㅣ i, u)W^g_n(j)}, ∀i

○ 步骤4. 策略改进：通过 g_n+1 ε arg min_uε𝒰 {C(i, u) + Σ_jεS P(j ㅣ i, u)W^g_n(j)} 定义新策略 g_n+1 并返回步骤2。

○ 如果 g_n 不满足停止准则，则 J^g_n+1 < J^g_n 成立。

③ 算法2. ACOE和相对值迭代

○ 假设：对于每个 g ∈ 𝒢_SMP，转移矩阵 P^g 是不可约且非周期的。

○ 步骤 1. 选择任意 h₀ ∈ ℝ^I。

○ 步骤 2. 对于任意 k ≥ 1，

○ ∀i ∈ S, λ^k(i) = min_{uε𝒰_{{C(i, u) + Σ_jεS P(j ㅣ i, u)h^k-1(j)}}}

○ μ^k = λ^k(I) 对于某些固定参考状态 I

○ ∀i ∈ S, h^k(i) = λ^k(i) - μ^k

○ 步骤3. 检查收敛性；如果不收敛，则返回步骤2。

○ 那么μ^k收敛到J*，h^k收敛到W（相对值函数）。

④其他算法

○ 线性规划：如果没有最大值条件，由于 ≤ 不等式（这是比取最小值更强的条件），J* 可以下降到 −∞。

○ 逐次逼近

○ Bertsekas 算法

○ Puterman 算法

⑤ MDS（鞅差分序列）

○ 概述： 对于具体样本路径（随机变量），我们要证明 lim inf_N→∞ Ĵ_N^g(ω) 对于每个 g 几乎肯定 (a.s.) 如下，并且 lim_N→∞ Ĵ_N^g*(ω) = J*如（假设 g* 是最优的）

○ 定理 1. 让 {X_k}_kεℕ 适应过滤 {ℱ_k}_kεℕ 并几乎肯定满足 𝔼[X_k+1 ㅣ ℱ_k] = 0。那么 X_k 和 Y_k = Σ_{j=1 到 k} X_j 是 ℱ_k 可测的。

○ 定理2. 鞅稳定性定理（LLN）

○ 定理 3. 对于任意 g ε 𝒢，lim_N→∞ inf (1/N) Σ_{t=0 到 N-1} C(X_t^g, U_t^g) ≥ J* a.s.成立，如果等式成立，则 g* 满足 ACOE。

○ 令 (J*, W) 为 ACOE 的解。定义 Z_k+1 = C(X_k, U_k) - J* + W(X_k+1) - W(X_k) - h(X_k, U_k) 和 h(i, u) = C(i, u) + Σ_j∈S P(j ㅣ i, u)W(j) - J* - W(i) ≥ 0。设 ℱ_k = σ(X₀, X₁^g, ···, X_k^g)。然后，给定 U_k^g = g_k(X₀, X₁^g, ···, X_k^g)，我们得到 𝔼[Z_k+1 ㅣ ℱ_k] = 0如下：

○ 因此 {Z_k}_k∈ℕ 是一个 MDS，并且 Z_k+1 的每一项都是有界的，因此 Z_k+1 相对于 M̃ 有界。因此，

○ 成立，根据 LLN，我们有 lim_N→∞ (1/N)Σ_{k=1 to N} Z_k = 0 a.s.但是

○ 成立且 h(·,·) ≥ 0，因此我们有 lim_N→∞ inf (1/N) Σ_{t=0 到 N-1} C(X_t^g, U_t^g) ≥ J* a.s.

⑥ 定理： 当 β → 1 时，DCOE 问题与 ACOE 问题等价。

○ 上述证明中ㅣW_β(i) - W_β(j)ㅣ < ∞ 的原因。

○ 定理

○ 上限

○ 下限

○ 一般证明

○ 意义 1. 最优策略 g_β* 不一定收敛于最优 ACOE 策略 g*。

○ 显着性 2. Blackwell 最优性：如果相同的策略 g_β* 对于所有 β̂ < β < 1 的 β 都是最优的，那么 g_β* 对于 ACOE 也是最优的。那么，J_β* = ACOE 最优 J* 也成立。

○ 证明1.

○ 证明 2. 在经典的 Blackwell 论证中，您可以通过将两个固定策略 π 和 ν 作为贴现因子函数 f_π,ν(γ) = V_γ^π − V_γ^ν 的函数来比较两个固定策略 π 和 ν。在标准有限 MDP 中，这种差异是 γ 的有理函数，非零有理函数只能有有限多个零。这意味着只有有限多个贴现因子 γ 可以使这两种策略相互关联；超出这些点，它们的排名不能像 γ → 1 那样无限频繁地翻转。因此，对于所有足够接近 1 的 γ，相同的策略仍然是最优的，并且该策略对于平均奖励标准也是最优的；这就是布莱克威尔最优策略。

⒃ 引理 16. 卡尔曼滤波器

① 概述

○ 情况 1. 纯预测问题 (U_t ≡ 0)：卡尔曼滤波器。给定 Y₀,…,Y_t，问题是预测 X₀,…,X_t。

○ 情况 2. 纯控制问题 (Y_t = X_t)：LQR（线性二次调节器）

○ 情况 3. 具有二次成本的部分观测：LQG（线性二次高斯）。

② 回顾：线性高斯过程

③ 情况 1. u_t ≡ 0 或 B_t = 0

○ 步骤 1. 预测

○ 步骤2. 观测预测

○ 步骤3. 数据更新

○ 意义： 从L_t的形式来看，滤波器是确定性的、非线性的。

○ 应用： 卡尔曼滤波器的渐近行为

○ 定义： 在时不变情况下 A_t ≡ A, G_t ≡ G, C_t ≡ C, H_t ≡ H。

○ 背景理论： 在讨论卡尔曼滤波器的渐近行为时出现可观性的原因是，为了构造一个长期稳定的观测器，系统必须至少是可观的，或者更一般地说，满足可观性。如果存在不可观测模式，则无法使用测量来校正该方向的状态分量。特别是，如果这样的模式不稳定（即，其特征值位于单位圆之外），则无法从输出推断其贡献，并且该方向上的估计误差随着时间的推移而无限制地增长。因此，误差协方差 P_k 也沿着该方向发散，因此 Riccati 递归不会收敛到有限极限 P_∞，并且观测器误差无法稳定。因此，为了保证卡尔曼滤波器良好的渐近行为（例如误差协方差的收敛、恒定的稳态卡尔曼增益和稳定的估计），所有不稳定模式都是可观测的，即 (A,C) 对是可观测的，这一点至关重要。

○ “Observable”、“Detectabile”和“reachable”具有相同的含义。

○ ARE(代数 Riccati 方程)

○ 如果 (A,S) 可达，则以下等价： A 稳定。 ⇔ 方程 Σ = AΣA* + SS* 有正定解 Σ。 ⇔ 推论

④ 情况 2. 任意 u_t = g_t(H_t) = g_t(y_0:t, u_0:t-1) 和任意 C_t(x_t, u_t)

○ 结果 1. (y_0:t^g, u_0:t-1^g) 和 y_0:t 是相同的 σ 代数：每个都是彼此的函数

○ (y_0:t^g, u_0:t-1^g) → y_0:t 证明： u₀^g = g₀(y₀^g) = g₀(y₀ + ş₀^g) 和 y₀ = y₀^g - c₀x̄₀^g = y₀^g - C₀𝔼[x₀]。 x̄₁^g = A₀x̄₀^g + B₀u₀^g，所以 ş₁^g = C₁x̄₁^g，导致 y₁ = y₁^g - ş₁^g。所以，我们可以这样构造 y_0:t 。»> ○ y_0:t → (y_0:t^g, u_0:t-1^g) 证明： 让我们考虑 x₀ → y₀ → u₀ → x₁ → y₁ → u₁ → x₂ → ⋯。 ų₀^g = c₀x̄₀^g 已知。 y₀^g = y₀ + ş₀^g 是已知的，u₀^g = g₀(y₀^g) 也是已知的。那么， x̄₁^g = A₀x̄₀^g + B₀u₀^g 是已知的，我们也知道 ş₁^g = c₁x̄₁^g 和 y₁^g = y₁ + ş₁^g。因此，u₁^g = g₁(y_0:1^g, y₀^g) 是已知的。因此，命题可以这样证明。

○ 这与前一个命题相关：P^g(X_t+1 ∈ A ㅣ H_t, u_t) = P^g(X_t+1 ∈ A ㅣ y_0:t, u_t)。

○ 结果 2. π_t = ℙ(x_t^g ㅣ y_0:t^g, u_0:t-1^g) = ℙ(x_t^g ㅣ y_0:t)

○ 结果 3. ℙ(x_t ㅣ y_0:t) (= 卡尔曼滤波器) 足以理解系统。

○ 备注 1. 控制仅影响 x̄_t^g（均值），而不影响 Σ_tㅣt（方差）。

○ 备注 2. 与一般 POMDP 不同，它不需要学习（主动探索）来减少方差。

○ 备注3. 分离原理：卡尔曼滤波器和控制可以分开。

⑤ 动态规划

⑥ 二次成本

○ 假设： C_t(x_t, u_t) = x_t*P_tx_t + u_t*T_tu_t, C_T(x_T) = x_T*P_Tx_T

○ 令 X ~ 𝒩(X̄, Σ) 和 S 为对称矩阵，则有 𝔼[X*SX] = X̄*SX̄ + Tr(SΣ)。

○ LQG问题的解决方案

○ 证明

○ 备注1. 确定性等价控制：最优控制策略中不出现噪声项{w_t}和{v_t}。

○ 备注2. 分离原理：通过卡尔曼滤波器进行前向估计，通过求解LQR问题进行控制动作的后向计算。

○ 备注 3. 如果 Σ_tㅣt ≡ 0，则 s_t ≡ 0。

⑦ 二次成本和ACOE

⒄ 引理 17. MAB（多臂老虎机）

图 6. MAB

① 公式

○ 前提：N 个随机过程 (X_kⁿ)_{k=0,1,…； n=1,2,……}

○ 状态集：S = {1, 2, ···, I} 或可数无限集» ○ 动作集：u_k ∈ {1, 2, ···, N}

○ 转换规则

○ 目标： 我们想要一个最优策略，使得sup_g∈𝒢 𝔼^g[Σ_{k=0 to ∞} β^kR(x_k^u_k)]。

○ 动态规划： W(x¹, x², ···, x^N), xⁱ ∈ S(s^N) = max_{u∈{1, 2, ···, N}} R(x^u) + βΣ_{j=1至 I} P(j ㅣ x^u)W(x¹, x², ···, x^u-1, j, x^u+1, ···, x^N)

② 理念

○ 要使用动态规划求解多臂老虎机 (MAB)，您必须将所有臂的状态视为一个巨大的状态向量 (x₁, x₂, ⋯, x_N)。

○ 随着臂数（N）的增加，状态空间呈指数级增长，使得计算变得不可行。

○ 关键思想： 不要共同考虑所有臂，而是单独分析每个臂，为其分配一个分数（指数），然后选择得分最高的臂。 → 这将复杂的 N 臂问题简化为单臂问题：随机臂与静态臂（“1.5 臂”问题）。

○ 设置： 在您面前，有一台老虎机（随机臂）。在任何时候，您都可以放弃这台机器并退休，以在每个周期（静态臂）永远获得固定奖励（M）（或R*）。

○ 问题： 当随机机处于状态 i 时，退休奖励 M 的多少值使您在“继续赌博”和“立即退休”之间完全无差别？ → 该退休奖励水平是状态 (i) 的 Gittins 指数。

③ 数学定义

○ 最佳停止时间（τ）：你继续玩机器，当状态变得非常不利以至于你认为“最好退休并选择M”时，你就停止。

○ 直觉：它是你在停止之前（退休前）可以获得的总奖励除以所花费的（折扣后）时间。换句话说，它是你在退休前可以提取的单位时间平均折扣的最大奖励。

④ 最优性证明： 交换论证

○ 令 i 为当前 Gittins 指数 (γ) 最高的臂，j 为第二高的臂。

○ 假设（矛盾）策略 g̃ 首先扮演 j。

○ 通过交换顺序（交换参数），我们可以将策略更改为先玩 i，后玩 j，这是最优策略 g，并且总奖励变得大于或等于。这是因为arm i具有较高的“平均奖励率（指数）”，因此在折扣（β）下，当奖励折扣较小时，最好早点做更好的选择。

○ 定义适当的时间间隔（例如 τ_i、τ_j）需要一些额外的代数推导。

> ⑤ 示例1. 假设有N台老虎机，记为M₁, …, M_N。每台老虎机 M_i 的成功概率为 θ_i，失败概率为 1 − θ_i。当我们玩一次时，成功时我们会收到 1 的奖励，失败时会收到 0 的奖励。成功概率 θ₁, …, θ_N 是相互独立的随机变量，取值在 [0, 1] 中，它们的先验分布用 P₁(dθ₁), …, P_N(dθ_N) 表示（我们假设这些分布允许密度）。在每个时间步，我们只能选择并玩 N 台老虎机中的一台。找到最大化的最优策略 E^g[Σ_{t=0 到 ∞} β^t r_t]。

⑥ 示例 2. 我们考虑一个具有 J 个队列（节点）的小型网络。在每个节点 j ∈ {1, …, J}，最初有 n_j 个工作（客户）在排队等待。节点 j 服务单个顾客所需的时间是随机的，其分布具有累积分布函数（CDF）F_j。当客户在节点 j 完成服务时，会发生以下两种情况之一。以概率 q_jℓ，客户移动到另一个节点 ℓ 并加入那里的队列；剩余概率为 1 − Σ_{ℓ=1 到 J} q_jℓ，客户完全离开系统。我们假设每当客户在节点 j 完成服务时，我们获得的奖励 r_j > 0（例如，r_j 可以解释为公司在节点 j 完成一项工作所获得的收入）。系统中只有一台服务器（worker）。因此，每时每刻我们都必须决定“接下来我们应该服务哪个节点的队列？”我们假设没有新客户从外部到达，我们的目标是随着时间的推移最大化总折扣奖励（总折扣收入）。将这种情况视为多臂老虎机（MAB）问题，每个节点 j 对应一个臂。在每个时间步，我们从集合 {1, 2, …, J} 中选择一个操作，并为相应节点队列中的一个客户提供服务。客户接下来去哪里是由该节点的概率 q_jℓ 决定的，因此整体排队状态（每个节点上还有多少客户等）演变为下一个状态。所有节点的联合状态就是强盗问题中的“系统状态”。为了使系统看起来更像一个标准的强盗模型，我们可以添加一个虚构的第（J+1）个节点，代表离开系统的客户的目的地，从而使网络“封闭”。没有实际的服务器分配给这个虚构的节点，因此永远不会选择它作为操作；它只是一个代表离开系统的客户流量的设备。通过这种方式，单个服务器在多个队列中选择在哪里花费时间，每当服务完成时接收奖励，并相应地看到队列状态变化的结构是 MAB 的典型示例。如果根本没有到达，每个队列仅在我们选择提供服务时才会缩小，因此问题是一个相对简单的“休息”强盗（参见 Gittins 策略是最优的）。然而，如果顾客不断从外部到达，那么即使他们没有被选择，队列也会改变状态，这个问题就成为“不安分强盗”的一个例子（参见Gittins索引策略不再是最优的，必须诉诸Whittle索引等概念）。

4。高级主题⑴ 去中心化团队（ref、ref、ref)

⑵ 鲁棒MDP (参考, 参考)

⑶ 约束 MDP (ref, ref)

⑷强盗（[参考]（https://www.semanticscholar.org/paper/A-dynamic-allocation-index-for-the-discounted-Gittins-Jones/d0c564e32058cd8e5d0bf9455538b64d8a0e2df8）， [参考]（https://people.eecs.berkeley.edu/~russell/classes/cs294/s11/readings/Gittins:1979.pdf），[参考]（https://academic.oup.com/jrsssb/article/42/2/143/7027598），参考，参考)

⑸ 不安分的强盗（[参考]（https://www.semanticscholar.org/paper/Restless-bandits%3A-activity-allocation-in-a-changing-Whittle/45196e90c3b265cbcd008af6e1aac97128e525dc），[参考]（https://arxiv.org/abs/2306.00196））

⑹ 强盗和自适应控制（[参考]（https://ui.adsabs.harvard.edu/abs/1987ITAC…32..968A/abstract），[参考]（https://people.eecs.berkeley.edu/~ananth/1987-1989/Pravin/MarkovMultiarmedbandit.pdf），参考)

⑺ 自适应控制（[参考]（https://www.semanticscholar.org/paper/Asymptotically-Efficient-Adaptive-Choice-of-Control-Graves-Lai/59ef34c2ecca183b7d0ff1788b49f2d5ca3e5ab9），参考)

⑻ 系统识别（线性）（ref, 参考)

⑼ 系统识别（受控马尔可夫链）（ref, ref)

⑽ 线性 SDS 中的策略梯度 (ref, ref)

输入：2025.08.26 23:34

5895

第 9 章随机控制理论

1.西格玛代数

2.随机控制理论术语

3。随机控制理论定律

4。高级主题⑴ 去中心化团队（ref、ref、ref)

results matching ""

No results matching ""