Korean, Edit

第 26 章动态规划

高级类别：【算法】【算法与机器学习索引】(https://jb243.github.io/pages/1278)

概述

⑴ 词源

①贝尔曼（1950年代）开创了动态规划的系统研究。

② 动态规划 = 随着时间的推移进行规划

③ 国防部长敌视数学研究。

④ 贝尔曼寻求一个令人印象深刻的名字以避免对抗。

⑵ 代表性事例

① 示例 1. 用于比较两个文件的 Unix diff

② 示例2. Viterbi 用于隐马尔可夫模型

③ 实施例3. Smith-Waterman进行基因序列比对

④ 示例4. 【最短路径算法】(https://jb243.github.io/pages/61)：Dijkstra 和 Floyd 算法

⑤ 示例 5. 用于网络中最短路径路由的 Bellman-Ford

⑥ 示例 4. 用于解析上下文无关语法的 Cocke-Kasami-Younger

Q1。

考虑一个有根二叉树网络。每个内部节点 x 有两个子节点，分别表示为 x(lhs) 和 x(rhs)。从 x 移动到其子节点 x(a) 的成本为 l_a，其中 a ∈ {lhs,rhs}。对于每个节点 x，令 L_x 为从 x 到叶节点的任何路径的最小成本。对于每个叶节点 y，定义 L_y = 0。表明对于任何内部节点 x，以下内容成立：

S1。

请参阅此链接。应用这一点，开发了最短路径算法（例如 Dijkstra 算法、Floyd 算法）。 （[参考]（https://jb243.github.io/pages/61））

Q2。

投资者拥有一只基金。它在零时刻价值 x 英镑，并且本金无法提取。该基金在 T 年内每年按利率 r × 100% 支付利息。在时间 t，投资者消耗_t比例的利息，并将其余部分重新投资于基金。为了最大化总消费，投资者应该做出什么选择？

S2。

请参阅此链接。

x_t+1 = x_t + rx_t(1 - a_t)

W_T-1(x_T-1) = rx_T-1

W_T-2(x_T-2) = max_0≤aT-2≤1 {rx_T-2a_T-2 + W_T-1(x_T-1)} = max_0≤aT-2≤1 {rx_T-2a_T-2 + r(x_T-2 + rx_T-2(1-a_T-2))} = 2rx_T-2

W_T-s(x_T-s) = rx_T-s max_0≤aT-s≤1 {(1+r)ρ_T-s+1 + (1 - rρ_T-s+1)a_T-s}

最佳的政策是首先储蓄所有收入，然后，一旦达到某个阈值，就转而消费全部收入。

Q3。

你想卖一辆车。每次 (t = 0, …, T-1)，您选择一个价格 p_t，然后顾客就会来看车。顾客以价格 p 购买汽车的概率为 D(p)。如果汽车在时间 T 之前尚未售出，则会以固定价格 W_T 出售，其中 W_T < 1。最大化销售汽车的预期奖励，并找到 D(p) = max(1 - p, 0) 时最佳奖励的递归（动态规划/贝尔曼方程）。

S3。请参阅此链接。预期奖励 R_t = max_p {pD(p) + (1 - D(p))R_t+1} = max_p {p(1-p) + pR_t+1}。 Rt 在 t = 0 且 p_t = (R_t+1 + 1) / 2 时不增加。

Q4。

你拥有一条昂贵的鱼。每天都会向您提供鱼的价格 X，其中 X 具有概率密度函数 f(x)。您可以接受或拒绝该要约。鱼在那天死亡的概率为 1−p。找出使出售鱼的预期利润最大化的政策。

S4。

请参阅此链接。该系统表现出时不变的特性。因此，贝尔曼方程如下：

其中 a 是常数。因此，最优策略为：如果x≥a，则买入；否则，拒绝它。在这里，我们可以得到下面的定点方程

LHS 固定为零，但 RHS 在 a 上不增加，因此定点是唯一的。

Q5。

一个赌徒有 i 英镑，想要达到 N 英镑。在每次游戏中，赌徒可以下注任何整数 j，其中 1 ≤ j ≤ i。赌徒赢的概率为 p，输的概率为 q = 1−p；如果他们赢了，他们就会增加 j 英镑，如果他们输了，他们就会损失 j 英镑。当赌徒的财富达到 0 或 N 时，游戏结束。假设 p > 1/2，则认为赌徒每次赌博 1 英镑始终是最佳的。

S5。

请参阅此链接。

请注意，R(i) = (1 - (q/p)ⁱ) / (1 - (q/p)^N) 是 R(i) = pR(i-1) + qR(i+1)、R(0) = 0、R(N) = 1 的解。给定的问题更复杂，但最终我们得到 V(x) = R(x)。直观上，如果允许无限时间，最优策略是投资最小单位以降低风险。

函数形式可以通过假设指数函数的线性和来获得。假设 R₁、R₂ 是 R(i) = pR(i-1) + qR(i+1) 的解。那么，两个函数之差 R₁ - R₂ 也满足方程。该方程类似于几何中的内分点，因此我们知道考虑到变量和方程的数量，在整数网格点中 R₁ - R₂ 始终为零。如果我们增加整数网格点的数量，我们知道对于给定区间内的所有点，R₁ - R₂ 等于 0。

Q6。令 X_k 表示给定股票在第 k 天的价格，并假设 X_k+1 = X_k + W_k, k = 0, 1, 2, …，其中 W₀, W₁, W₂, … 是具有给定分布 P 的独立同分布 (i.i.d.) 随机变量，具有有限的分布均值，并且也独立于初始价格 X₀。假设你有一个以固定价格 K 购买一股股票的选择权。你有 N 天的时间来行使这个选择权。您不必执行该期权，但如果您在某一天 k 当价格为 x 时执行该期权，您的利润将为 x - K。您最多可以执行该期权一次。然后，确定使您的预期利润最大化的策略。

A6。

请参阅此链接。在任何时间点，如果您以价格 x 行使期权，则回报为 x - K。因此，随机动态程序为：

我们证明了价值函数的以下性质： (i) V_t(x) ≥ V_t+1(x), ∀x, (ii) V_t(x) - x 在 x 中递减。请注意，对于 t = N，V_N(x) ≥ 0。因此，V_N-1(x) = max(x - K, 𝔼_WN-1[V_N(x + W_N-1)]) ≥ max(x-K, 0) = V_N(x)。假设第 (i) 部分的断言对于 t+1 成立，即 V_t+1(x) ≥ V_t+2(x), ∀x。为了完成 (i) 的证明，我们必须证明 V_t(x) ≥ V_t+1(x), ∀x。由于归纳假设，我们得到

关于 (ii) 的证明，该断言对于 t = N 成立，因为 V_N(x) - x = max(x - K, 0) - x = max(-K, -x) 其在 x 中递减。假设 (ii) 的断言对于 t+1 成立，即 V_t+1(x) - x 在 x 中递减。为了完成 (ii) 的证明，我们必须证明 V_t(x) - x 在 x 中递减。

根据归纳假设，对于每个固定的 w，V_t+1(x + w) - (x + w) 在 x 中递减。由于上式右侧是此类函数的非负线性组合，因此可以得出 ∫[V_t+1(x + w) - (x + w)]P(dw) 在 x 上递减。因此，上式右侧的 x 递减，因此 V_t(x) - x 的 x 递减。 (ii) 的证明已完成。

考虑无关点的方程：-K = 𝔼_W[V_t+1(x + W)] - x。价值函数的性质 (ii) 意味着无差异方程至多有一个解。定义 p_t := 无差异方程的唯一解（如果存在）；否则为+∞。值函数的性质 (i) 意味着 V_t(x) ≥ V_t+1(x)，因此 𝔼[V_t] ≥ 𝔼[V_t+1]，这意味着 p_t ≤ p_t-1 （序列递减）。最后，显然 p_N = K。最后，从 (1) 和 (2) 可以看出，最优策略是当且仅当当前价格 x ≥ p_t 时在 t 时刻执行期权。

Q7。您拥有执行价格为 p 的看涨期权。这意味着您可以以价格 p 购买一股；如果 t 时刻的股价为 X_t，那么您的行权利润为 X_t − p。该期权必须在时间 T 之前行使。股票价格 X_t 遵循 X_t+1 = X_t + ε_t，其中 εt 是具有相同分布和有限均值的独立随机冲击。证明存在递减序列 {a_t}_0≤t≤T，使得当 X_s ≥ a_s 在时间 s 发生时，执行该选项是最佳的。

A7。

请参阅此链接。 W_t(x) 可以被证明是 t 的减函数。还可以证明W_t(x) - x 是x 的减函数。直观上，x越大，预期利润越高，因此人们倾向于执行该期权。因此我们可以证明，在第 m 天，当 x ≥ a_s 时行使该期权是最佳的。此外，从动态规划和W_t(x)在m中的单调行为，我们可以很容易地证明a₀≥a₁≥…≥a_N。直观上，t越小（即越早，剩余时间越多），基本预期利润就越高，因此与其匆忙行使期权，不如策略性地等待。

Q8。

某类星际粒子的探测周期为N天（N固定）。科学家可能会在任何一天寻找这种类型的粒子，或者可能呆在家里。当粒子数为x时，检测到它的概率为p(x)，检测到1个以上的概率为零。概率 p(·) 是 x 的已知非减函数。检测到的一个粒子价值一个单位，一天的搜索成本为 c 个单位 (0 < c < 1)。如果科学家呆在家里，他/她不会承担任何费用，也不会获得任何奖励。假设：

(A1) 科学家已知任意一天的粒子数量 x。

(A2) 当科学家成功时，粒子数量减少 1；否则从一天到第二天都不会改变。

目标是确定检测策略，以最大限度地提高科学家在检测期间的预期回报。

A8。

请参阅此链接。设V_t(x)为时间为t、粒子数为x时的值函数。然后我们得到

V_t(x) = max(Q_t(x, 搜索), Q_t(x, 停留)) = max( -c + p(x)(1 + V_t+1(x-1)) + (1 - p(x)) V_t+1(x), V_t+1(x) ), t = 1、···、N</中心>
V_t(x) 在 t 中减小，在 x 中增大。因此，在任何给定时间 t，搜索的动机随着 x 的增长而变得更强，并且可以证明在 t 天，仅当 x ≥ x_t\* 时进行搜索才是最佳的。如果我们定义“stay”当且仅当 Q_k(x,stay) < Q_k(x,search)，那么我们得到 x₁\* = ··· = x_n\*)。因为这可以在任何给定时间点显示，并且相同的论点通过对称性成立。也就是说，对于所有 x ≤ x_N\*，可以证明 x_N-1\* = x_N\* 和 V_N-1(x) = V_N(x)，并且通过对称性，直观地可以看出这一归纳假设得到保留。相反，如果我们定义“stay”当且仅当 Q_k(x,stay) ≤ Q_k(x,search)，那么我们就得到 x₁\* ≥ ··· ≥ x_n\*，因为“stay”是弱首选。

## Q9。 最佳停止问题是具有两个动作的马尔可夫决策过程：a = 0 表示“停止”，a = 1 表示“继续”。有两种类型的成本：c(x, a = 0) = k(x) 表示停止成本，c(x, a = 1) = c(x) 表示继续成本。这定义了一个停止问题。假设时间范围是有限的，贝尔曼方程为
C_t(x) = min{k(x), c(x) + 𝔼[C_t-1(X)]}
边界条件 C(0) = 0, C₀(x) = k(x) 。 ## A9。 请参阅此[链接](https://www.youtube.com/watch?v=5F37qbwvJps&list=PLGboZ4litMr_TOwUANH-s-uFnczzy2uuW&index=15)。假设成本函数在 x 上递增。那么价值函数 C_t(x) 在 x 中增加，在剩余时间 t 中减少。因此，最优策略是阈值类型的：在剩余 t 个周期的情况下，存在一个数字 x_t* ​，当且仅当 x ≥ x_t* 时，最优停止。此外，在 x_t* ≤ x_t+1* 的意义上，阈值在 t 中是单调的，因此剩余时间越多，连续性就越有吸引力，并且仅当 x 值较大时才停止。

## Q10。 （秘书问题）假设您收到按顺序排列的 n 个报价。查看报价后，您必须决定是接受并终止流程还是拒绝。一旦被拒绝，该报价就会丢失。假设您随时知道当前报价与之前报价相比的相对排名。确定当所有 n! 时最大化选择最佳报价的概率的策略。假定报价的排序具有相同的可能性。 ## A10。 令 V_k 为观察第 k^th 个报价之前的最佳成功概率，X_k 为给定 k 个报价的相对排名（越高越好），Q(x, a), a ∈ 𝒜 = {accept,reject} 为状态-动作值函数。那么，我们有

请注意，在第 n^th 个报价时，我们已经知道报价的确切排名，因此最终条件如下：V_n(x) = 𝟙{x = n}。从贝尔曼方程中，我们可以得到以下确定性最优策略：

请注意，成功概率收敛于 1/e。

## A10-2。 令第 m 个报价为最佳报价的概率为 p(m) = m/n，并令在拒绝第 m 个报价后，最佳报价仍位于前面的概率为 L(m) = 1 - m/n。定义 V(m) = max{p(m), L(m)}。随着 m 的增加，p(m) 增加，而 L(m) 减少。因此，最佳策略是首先继续拒绝报价，然后在某一点之后，接受迄今为止观察到的所有报价中最好的第一个报价。

## Q11。 您在街道上寻找停车位；每个空间都是空闲的，概率为 p = 1−q。在到达某个空间之前，您无法判断该空间是否空闲。一旦到达某个空间，您必须决定停止或继续。从位置 s（即距目的地 s 格）开始，停止的成本为 s。在没有停车的情况下经过目的地的成本是 D。 ## A11。请参阅此[链接](https://www.youtube.com/watch?v=EEuZgZ1f-V4&list=PLGboZ4litMr_TOwUANH-s-uFnczzy2uuW&index=17)。令 V_s 为距目的地位置的值函数，则我们有以下贝尔曼方程：
V_s = (1-q) max{s, V_s-1} + qV_s-1, V₀ = qD
正如在给定的问题中，无论成本随着接近目的地而减少（左）还是相反地增加（右），最优策略如下：当且仅当 s ≤ s* 时停止

由于我们总是在接近目的地时停止，因此我们最终会求解 V_s\* = (1−q)s + qV_s−1\* 并且在这种情况下 V_s\*​ 可以写成一个简洁的封闭形式（参见齐次和特定的解决方案）：当且仅当 s ≤ V_s\* = s - (q/p) + (qD + q/p) 时停止q^s

## Q12。 考虑在离散时间 t = 0, 1, 2, … 中演化的马尔可夫链 (M.C.)，状态空间 X = S = {1, 2, …}。转移概率由矩阵 {P(j ㅣ i)} 给出，其中 i, j = 1, 2, ...。在每个时刻 t = 0, 1, 2,… ，决策者可以完美观察马尔可夫链的当前状态 X_t。每次观察都会产生成本 C.在某个时刻t，决策者可能会选择停止观察马尔可夫链的演化。如果他们在时间 t 停止，他们会收到奖励 r(X_t)。特别是，如果 X_t​ = i，则 r(X_t) = r(i)。奖励 r(X_t) 是最终的，因为一旦决策者在时间 t 停止，决策就是最终的，不会产生进一步的成本或奖励。决策者必须在时间 T 之前做出最终停止决策。目标是选择一个策略 g := (g₀, g₁, …, g_T−1) 最大化 J^g = 𝔼^g[−c(τ(g)+1) + r(X_τ(g))]，其中τ(g) 表示决策者在策略 g 下停止的（随机）时间。对于每个策略 g，我们有 0 ≤ τ(g) ≤ T。确定最优策略。 ## A12。 动态程序可以表述如下：
> V_T(i) = r(i) > V_t(i) = max{r(i), -c + Σ_j P(i, j)V_t+1(j)}, t = 0 ~ T-1
由此我们得到 V_t(i) ≥ V_t+1(i)。直观上，如果t时刻的奖励足够大，就可以立即停下来做出决定；否则，人们应该等待并瞄准下一次转变。由于时间 t 越早，价值函数就增加，为了最大化奖励而等待转换的动机就会变得更强。因此，时间 t 处的停止集 S_t := {i ∈ X : V_t(x) = r(i)} 是时间 (t+1) 处停止集 S_t+1 的子集；即 S_t ⊂ S_t+1。假设时间 (T-1) 的停止集 S_T-1 具有闭包性质，即对于所有 (i, j)，使得 i ∈ S_T-1 且 j ∉ S_T-1，我们有 P(j ㅣ i) = 0。在这种情况下，S_T-1 的大小大大减小，归纳起来我们得到S_t ⊃ S_t+1 ⊃ ··· ⊃ S_T-1。因此，t时刻的最优策略是“stop iff i ∈ S_t”，在闭包性质下，它变成“stop iff i ∈ S_t = S_T-1”。

## Q13。一个人想卖掉她的房子。每天早上都会有报价。假设连续的报价是独立的，并且报价为 x_j，概率为 p_j , j = 1, 2, ...。 。 。 , n，其中 x_j , j = 1, 2, . 。 。 , n, 是非负标量。任何未立即接受的报价都不会丢失，但可以在以后的任何日期接受。房屋未售出的每一天都会产生维护费用 c。 N天内有出售房子的最后期限。目标是最大化房屋售价减去维护成本。 ## A13。 我们可以找到合适的信息状态 z_t = max{x₁, ···, x_t}。那么我们就有了如下的动态程序：
Q_k(z, 卖出) = z Q_k(z, 剩余) = -c + 𝔼^g[V_k+1(z_k+1) ㅣ z_k = z] = -c + Σ_j p_j V_k+1(max{z, x_j}) V_n(z) = z V_k(z) = max{Q_k(z, 卖出), Q_k(z, 保留)}
我们可以求出V_t(z)≥V_t+1(z)，V_t(z)≥V_t(z-1)，即动态规划中V_t(z)的凸性。最优策略是当且仅当 z ≥ r_t 时卖出。如果“remain iff Q_k(z, keep) < Q_k(z, sell)”，我们得到 r₁ = ··· = r_n，因为我们可以在一个步骤中显示它，并且它通过对称性适用于其他时间步骤。如果“remain iff Q_k(z,remain)≤Q_k(z,sell)”，我们得到 r₁≥…≥r_n，因为“remain”是首选。

## Q14。 一个对象位于 n 个可能位置之一。物体位于位置 i 的概率为 p_i（p_i 为先验概率，p_i > 0，Σp_i = 1）。在位置 i 进行搜索的成本为 c_i，c_i > 0，如果该对象存在于该位置，则发现该对象的概率为 α_i，i = 1, 2,...。 。 。 , n.确定以最小成本发现对象的策略。 **提示：** 证明如果 (π₁(t), π₂(t), ..., π_n(t)) 是时间 t 的信息状态，t = 1,2,...，则最优策略是搜索具有最大值 α_iπ_i(t) / c_i, i = 1, 2, . 。 。 , n. ## A14。 信息状态可以定义为后验概率ℙ(结果ㅣ先验)。


## Q15。 在抛硬币游戏中，个人的赔率为 3 比 1，只要出现反面，她就获胜。然而，她怀疑硬币是有偏差的，并且对于每次抛掷出现正面的概率 p，具有 CDF F(p) 和 pdf f(p) 的先验概率分布。最多允许掷 T 枚硬币。个人的目标是根据迄今为止的游戏结果来决定是否继续或停止参与游戏的政策，以最大化她的收入。 ## A15。 信息状态可以定义为后验概率ℙ(结果ㅣ先验)。 对于一般信息状态，

对于具体的信息状态，


## Q16。（顺序二元假设检验）考虑一个二元状态 H ∈ {0, 1}，先验概率为 ℙ(H = 0) = p。在每次 t = 0, 1, …, T 时，决策者选择以下操作之一： (10 停止并声明决策 u ∈ {0, 1}，或 (2) 继续（产生成本 (C)）并获得观测值 Y_t。如果声明不正确，则会产生惩罚 K。 > **a.** 写出在时间 (t = T) 时的终值函数 V_T(π)。 > **b.** 写出 V_t(π) 的贝尔曼方程，其中 0 ≤ t ≤ T-1。 > **c.** 设f₀(y)和f₁(y)分别表示H = 0和H = 1下Y的概率质量函数。观察 y 后推导信念更新规则 π_t+1 = 𝒯(π_t, y)。 > **d.** 以积分形式表达选择“继续”的条件预期成本，𝔼[V_t+1(π_t+1) ㅣ π_t = π]。 > **e.** 通过数学归纳法表明，对于所有 t，函数 V_t(π) 在 π 上是凹的。 > **f.** 假设 V_t(π) 是凹的，表明最优策略由两个阈值 ρ_t^1,\* ≤ ρ_t^0,\* 表征。写下确定这些阈值的方程。 > **g.**（无限视野定点）令 T → ∞。写出时不变值函数 V(π) 所满足的定点方程。 > **h.** 假设 T = 1（即当前时间 t = 0，只有一次观察机会），K = 1，C = 0.1，观察值取离散值 y ∈ {a, b}，似然度 f₀(a) = 0.7，f₁(a) = 0.3，f₀(b) = 0.3， f₁(b) = 0.7。给定初始信念 π = ℙ(H = 0) = 0.45，确定继续还是停止是最佳选择。 ## A16。 **a.** V_T(π) = min((1 - π)K, πK) **b.** V_t(π) = min((1 - π)K, πK, C + 𝔼[V_t+1(π_t+1) ㅣ π_t = π]) **c.** π_t+1 = f₀(y)π_t / (f₀(y)π_t + f₁(y)(1 - π_t)) = 𝒯(π_t, y) **d.** 𝔼[V_t+1(π_t+1) ㅣ π] = ∫ V_t+1(𝒯(π, y)) p(y ㅣ π) dy = ∫ V_t+1(𝒯(π, y)) (πf₀(y) + (1-π)f₁(y)) dy **e.** 如果 V_t+1(π) 通过归纳法是凹的，我们可以将其表示为 inf_iεℐ {α_iπ + β_i}，从而得到 𝔼[V_t+1(π_t+1) ㅣ π] = ∫ inf_i {α_i 𝒯(π,y) + β_i} p(y ㅣ π) dy = ∫ inf_i { α_if₀(y)π + β_i (f₀(y)π + f₁(y)(1 - π)) } dy → 凹 **f.**

**g.** 然后，阈值也收敛到时不变常数。 **h.** 如果计算的话，最佳选择是继续 (≈ 0.371) < 停止 (0.45)。

## Q17。（具有不可数控制的有限状态 MDP）有 N 个人，名为 i = 1, 2, 3, ..., N。人 i 被分配一个编号 X_i，其中 X₁、X₂、...、X_N 是独立同分布且在 [0,1] 上均匀分布。你的任务是通过以下问题和答案序列找到数字最大的人（不是数字本身）。你选择一个数字α₁，并询问“谁的数字比α₁大？”。告诉你答案，即编号在 α₁ 以上的人。然后你选择另一个数字α₂并询问“谁的数字比α₂大？”你会被告知答案。然后您选择另一个数字 α₃ 等等。然后回答以下问题： (i) 你应该如何选择数字 α₁, α₂, ... 以便你能找到数字最大且预期问题最少的人？ 提示：设 V(n) 为 n 人时的最小预期问题数。使用动态规划编写 V(n) 的递归关系。重要的是，请注意，响应将缩小所有剩余人数（您将考虑的）的值范围，但由于数字均匀分布在 [0,1] 中，通过平移和缩放，可以将问题转换回 [0,1] 中的值。 (ii) 当 N = 2 时，显式求出 V(1) 和 V(2)，以及 α₁、α₂、...。 ## A17。 考虑以下受控马尔可夫链模型。马尔可夫链具有状态空间 {1, 2, 3, ..., N}，其中 N 是初始人数。动作空间U是区间[0,1]。该状态是完全观察到的，也就是说，在阶段 k，我们完全知道回答了问题“你的数字是否大于 α_i？”的人数 n 。对于 i = 1, 2, ..., k。对于任何控制动作 α ∈ [0,1]，转移概率矩阵为

当 n > 1 时，瞬时成本为 C(n α) = 1，α ∈ [0,1]。初始状态为 N。目标是以最小预期成本（即最少预期问题数）达到状态 1。如果当前状态为 n，则令 V(n) := 最小问题数。那么 V(1) = 0 并且 n > 1

上述方程可以递归求解。从贝尔曼方程开始，然后计算 V(n)（n = 2, 3, ..., N）。例如

我们注意到固定 α 给出

因此，我们可以通过求解来找到最小化器

得出 α₂\* = 0.5 和 V(2) = 2。请注意，我们确实期望 α 的函数最小化为 ve V_α(2)。要获得 V(3)，请使用 V(2) = 2，将 V(3) 表示为 α ∈ [0,1] 的函数，并相对于 α 最小化该函数。我们有

然后，我们得到

这也是最小化寻找α的目标。因此，

在数值上，我们得到 α₃\* = 0.6537 和 V(3) = 2.1651。从这些例子中可以清楚地看出，您所要做的就是求解贝尔曼方程，得到 n = 1, 2, 3, ..., N，假设剩余人数所在的区间为 [0,1]。当 [0,1] 中有 n 个人时（n = 2, 3, ..., N）确定最佳动作 α_n\* ∈ [0,1] 后，如果还没有找到最高值的智能体，则在 [c_k, d_k] 有 n 个人时 k、α_k 时刻的最佳动作 (0 ≤ c_k < d_k ≤ 1, n = 2, 3, ..., N) 通过关系找到

发生这种情况是因为，在每个问题之后，剩下的人都有独立分布的数字，并且在一个区间内均匀分布，该区间取决于之前问题的选择和相应的答案。同样，可以将值转换和重新缩放到 [0,1] 范围内。由此可见，对于 N = 2，我们得到二分搜索 - 每当两个代理响应处于同一间隔时，我们的下一个查询将使用该间隔的中点，并且间隔始终是二元间隔，即形式为 [2^-k/t, 2^-(k-1)/t]，其中 k = 1, 2, ..., t 或 [0, 2^-1/t] 在时间步 t+1（t > 0）。

## Q18。 （部分观察马尔可夫决策过程）价值$r的宝藏位于泻湖中的概率为p。每次打捞公司潜水寻找宝藏时，如果宝藏确实存在，那么它找到宝藏的概率为 β。令 c（0 < c < r）为一次潜水的成本，并假设 rβ > c。鉴于打捞公司最多可以尝试 N 次潜水，请确定使预期利润最大化的“搜索”策略。回答以下问题： (i) 将优化问题表述为不完全观察/信息的问题。 (ii) 找到一个信息状态并写出该信息状态的演化方程。 (iii) 写出动态规划最优方程。 ## A18。 (一) 设 X_t = (Z_t, θ_t)^T，其中 Z_t ∈ {0, 1}，θ_t ∈ {0,1} 为状态。

对于所有 t，观测值均为 Y_t = Z_t。动作空间 u ∈ {0,1} 其中

瞬时利润 C(Z_t, θ_t, u_t) 为

转移概率矩阵是

其中 z, θ, θ' ∈ {0,1} 且 δ(·,·) 是克罗内克三角洲，即

矩阵 P_0z(u,θ) 由下式给出： P₀₁(u = 1, θ = 1) = β, P₀₀(u = 1, θ = 1) = 1 - β, P₀₀(u = 1, θ = 0) = 1, P₀₁(u = 1, θ = 0) = 0，P₀₀(u = 0, θ) = 1 且 P₀₁(u = 0, θ) = 0。请注意，我们在第一次观察到 Z_t = 1 且 t ≤ N 时停止。目标是在上述约束条件下最大化预期利润。 (二) 信息状态为 π_t = ℙ(θ_tㅣ 之前的搜索没有找到宝藏)。我们将 π₀ 设置为 θ = 1 的先验概率。然后，使用贝叶斯规则，我们发现对于 t ≥ 0，

(三) 动态规划给出如下： ∀π ∈ [0,1]，


## Q19。 （杆切割问题）给定长度为 4 的杆和杆件的价格，切割杆最有利可图的方式是什么？ | **长度** | 1 | 2 | 3 | 4 | | --- | --- | --- | --- | --- | | **价格** | 1 | 4 | 6 | 7 | ## A19。 我们将变量定义如下： * x_k ：第k次切割后的剩余长度 * u_k : 在 k 阶段切割的杆件的长度 * r_k(x_k, u_k) : 第 k 根杆件的价格 * 系统方程：x_k+1 = x_k - u_k for x_k ≥ u_k 下面是逆向求解问题（动态规划）。

下面是向前解决问题。由于存在冗余，因此这是一个低效的解决方案。

在每种方法中，最有利可图的是将四长条分成两块以获得最终价格 8。

## Q20。 （投注游戏）你有2美元，必须玩3次游戏。每场比赛，获胜的几率为 0.4，您下注的金额将翻倍；失败的几率为 0.6，您将输掉您下注的金额。您只能下注整数美元金额。找到一份能让您最终获得 4 美元或更多的机会最大化的保单。 ## A20。 动态规划公式 > ○ 第 i 阶段：第 i 场比赛 (i = 0, 1, 2, 3) > ○ 第 i 阶段的状态：x_i = 游戏 i 开始时可用的金钱 > ○ 第 i 阶段的行动：u_i = 下注金额（必须是整数） > ○ 第 i 阶段的奖励：当 i = 0, 1, 2 时，r_i(x_i) = 0。当 i = 3 时，如果 x₃ ≥ 4，则 r₃(x₃) = 1；如果 x₃ < 4，则为 0。 > ○ 目标：V₀\*(x₀ = 2) = max_μk 𝔼[Σ_{k=0 到 3} r_k(x_k) ㅣ x₀ = 2] 贝尔曼方程 > ○ V_k\*(x_k) = max_u 𝔼[V_k+1\*(x_k+1)] = max_u(V_k+1\*(x_k + u) × 0.4 + V_k+1\*(x_k - u) × 0.6) 第 3 阶段的计算：

第 2 阶段的计算：

第一阶段的计算：

第0阶段的计算：

最优策略：2块钱下注一次。
--- _输入：2025.11.21 00:36_