条件最优停止：一种时间不一致的优化

更一般地，集合B可以是时间相关的。当σ=∞. 但一般来说，定义τ的预期收益的条件取决于τ本身，因此它不能简化为经典的停止问题。2.1均衡以下示例说明优化问题（2.1）是时间不一致的，因为今天的最优停止策略在将来可能不是最优的；也就是说，如果她用一个有条件的标准重新考虑未来的战略，她可能会反驳她以前的决定。示例2.2。考虑一个具有Ohm = {uu，ud，du，dd}如图1所示，其中u代表向上，d代表向下。每个边上的条件概率为1/2，每个节点上的数字表示结果。相关域包括除dd以外的所有状态；i、 例如，虚线表示域中的ex-it。由于该模型中只有五个不同的停止时间，once可以轻松计算所有可能的支付，并观察到（2.1）的唯一优化器是停止时间τpre，其中τpre（uu）=τpre（ud）=1，τpre（du）=τpre（dd）=2。也就是说，图1：示例2.2的二叉树。如果我们在第一步中向上移动，最好在t=1处停止，否则att=2。获得的收益用实心点表示，相关值为Vpre=10·+2·=。接下来，考虑一个年龄nt的类似优化问题，该年龄nt有条件地在t=1的下降状态下开始求解问题。该代理只有两种选择，要么立即停止支付3，要么等待到地平线并获得2的预期奖励（因为预期的条件是留在域内）。因此，该代理倾向于停止，这与τpre不一致。

总之，如果第一代理解决了（2.1）问题，并使用自然条件标准重新考虑了自己在下降状态下t=1的策略，她将推翻之前的决定。在本文的其余部分中，我们将重点讨论[29]意义上的一个未承诺的复杂代理（参见[24]，了解最近一篇研究其他方法的论文）。她在不同的时候都会想到自己的“未来自我”，并指出其他代理人会在后续决策被视为给定时优化他们的选择。因此，我们寻求一种未来自己不会超越的政策。策略是一组二元决策（停止或继续），每个时间和状态对应一个决策，而均衡是一种没有发现任何代理偏离的策略。在将其形式化之前，让我们观察一下，每个代理都面临着不限制空事件的约束。也就是说，如果继续将导致在下一步中退出域的概率为1，则任何代理都将被迫停止。因此，问题具有（随机）有效时间范围：=T∧ inf{0≤ t<t:P（Dt+1 | Ft）=0}。下面将[18，22]的基本概念适用于我们的条件停止问题（而不是非指数折扣），并将其扩展到非马尔可夫环境。定义2.3。stoppin g策略是{0，1}值的适应过程θ=（θt）t∈T、 我们将θT（ω）=1解释为（T，ω）选择停止的代理，而θT（ω）=0解释为继续。我们还引入了连续停止时间tθ=inf{s>t：θs=1}；这是一个决定继续的时间t代理由θ引起的停止时间。

停止策略θ称为容许ifP（Ltθ t<t时σ| Ft）>0，t时θt=1≥ Te。我们用Θ表示所有可容许停止策略的集合。可容许性意味着t<tE的每个time-t代理都有一个明确的连续值jt（θ）=E[GLtθ{Ltθσ} | Ft]P（Ltθ σ| Ft），t<Te。当然，他会将Jt（θ）与她的停止值gt进行比较，并选择较大的值，或者如果它们相等，则她是不变的。（t=TEA的代理被强制停止，因此没有要做出的决定。θtfort>TEI的值不重要，仅针对特定的情况设置为1。）如果我们从θ开始∈ Θ和所有代理同时根据该偏好更新其选择，同时使用不变代理坚持其先前存在的决策的约定，我们得到更新的停止策略Φ（θ）t=1如果t<Teand Gt>Jt（θ），θtif t<Teand Gt=Jt（θ），0如果t<Teand Gt<Jt（θ），1如果t≥ Te。定义2.4。如果Φ（θ）=θ，则允许的停止策略θ是均衡（停止策略）。这一概念对应于子博弈的完美纳什均衡：如果未来代理人的选择被视为给定的，则每个代理人的行为都是最优的。示例2.5。考虑示例2.2的设置。在任何可容许停止策略中，time-2代理都必须因时间范围而停止。然后，两个time-1代理都倾向于停止，因为它们的停止值（10和3）超过了预期的连续值（3和2）。根据这些决定，time-0代理的预期连续值为（10+3）/2，超过了停止值2。很容易得出，唯一的均衡停止策略由θ=0，θ给出≡ 1和θ≡ 1、time-0代理的诱导停止时间为τ≡ 1.

这与示例2.2中预先提交的最佳停止时间τpreo不同，相关预期回报（10+3）/2小于预先提交的价值函数Vpre。在马尔可夫链环境中，停止策略的自然子集也是马尔可夫形式。用σ（Y）表示由随机变量Y生成的σ-场，其形式化如下。定义2.6。考虑示例2.1中的马尔可夫设置。停止策略θ∈ 如果θtisσ（Xt，1Dt）-可测量所有t∈ T、 如果θ是容许的，这等价于可测子集的存在 X使得θt=1{Xt∈Rt}∪Dct。请注意，这种平衡实际上是通过Dt的路径依赖性，但这是与我们对可容许性的一般定义相一致的最小路径依赖量。在马尔可夫环境中，可以假设所有出口状态（B之外的状态）都是吸收的，而不损失一般性。那么，我们有dt={Xt∈ B} 我们可以要求θtis（a.s.）σ（Xt）-可测量。3有限水平平衡在本节中，我们讨论T<∞.在经典的最优停止问题中，时间t agent的值函数和最优决策完全由时间t+1时agent的值函数决定。这一事实是动态规划的反向递归和斯内尔包络理论的核心。然而，在手头的问题中，计算连续值Jt（θ）时的条件事件取决于许多未来自我的决定，而不仅仅是t+1时的决定。这建议引入一个额外的过程来跟踪条件反射事件的概率，给出所有未来自我的最高政策；我们称之为生存过程，因为它与生存概率有关。

在下面的定理3.1中，我们提供了一个向后递归来构造平衡；其Jt（θ）的递推公式类似于经典情况，即t+1时的值过程的条件期望，但现在该期望是在使用标准化生存过程asa密度获得的新度量下计算的。就像经典的最优停止一样，当代理不变时，会出现一种类型的非唯一性；也就是说，当stopping和continuationvalue恰好相等时：Jt（θ）=Gt。因此，构建均衡的算法必然伴随着特定的选择。下面所述的理论使用了早期停止偏好，这意味着不变量代理选择停止，并产生了与该偏好的唯一平衡。在经典设置中，这与Snellenvelope第一次碰到障碍物相对应。一般来说，停止偏好是一个具有二进制值的自适应过程，在不变性的情况下为每个（t，ω）定义选择。对于每个这样的偏好，可以编写一个类似于定理3.1的算法，它提供了该偏好的唯一平衡。相反，每一个有限水平平衡都是这样产生的。定理3.1。让T<∞ 回想一下，Gt= 在Dct上。定义valueprocess（Vt）t≤生存过程（St）t≤下面是助教。设置VT=GT和ST=1DT。对于t=t- 1.0，设置JT=E[St+1Vt+1 | Ft]E[St+1 | Ft]如果t<Te，Vt=Gt，如果t<t且Gt，则St=1≥ Jt，Vt=Jt，St=E[St+1 | Ft]如果t<Teand Gt<Jt，Vt=Gt，St=1Dtif t≥ Te。那么θ：=1{Gt≥Vt}是偏好提前停止的唯一平衡。在第6节中，我们将（V，S）称为Snell对，并讨论它与Snell信封的连接。还将提供一个包括最终地平线情况在内的概括。

尽管如此，我们还是选择在本节中对有限层进行基本和独立的处理。定理3.1的证明。我们在下面的引理3.2中表明θ是可容许的，并且Jt与θ的延拓值Jt（θ）一致。一旦确定，θ的定义表明θ=1{Gt≥Vt}=（如果t<Teand Gt<Jt（θ），则为0，否则为1，因此θ是具有提前停止偏好的均衡停止策略。另一方面，在TEAN的边界条件和一个反向感应流下，我们可以看到至多有一个这样的平衡。引理3.2。在定理3.1的设置中，θ是可容许的，且Jt=Jt（θ），t<Te，E[St+1 | Ft]=P（Ltθ σ| Ft），t<Te，（3.1），对于t≤ 我们没有=P（Ltθ Dt上的σ| Ft）∩ {θt=0}，1在Dt上∩ {θt=1}，Dct上为0。证据我们首先检查θ是否允许。实际上，对于t，我们有θt=1≥ Te，如果t<Te，则反向归纳表明P（Ltθ σ| Ft）>0。接下来，我们证明了St的公式。最后两种情况从定义上看是清楚的。因此，我们重点显示St=P（Ltθ Dt上的σ| Ft）∩ {θt=0}。对于t≥ θt=1，因此无需证明。对于t<Teweargue，通过感应。事实上，使用归纳假设获得下面的（a），St=E[St+1 | Ft]（a）=EDt+1{θt+1=0}P（Lt+1θ σ| Ft+1）+1Dt+1{θt+1=1}·1+1Dct+1·0英尺（b） =E[P（Ltθ σ| Ft+1）| Ft]=P（Ltθ σ| Ft），其中（b）保持正上方（Ltθ σ| Ft+1）=P（Lt+1θ σ| Ft+1）在Dt+1上∩ {θt+1=0}，1在Dt+1上∩ {θt+1=1}，Dct+1上的0。（3.2）在最后一个恒等式中，第一种情况成立，因为θt+1=0意味着Ltθ和Lt+1θ一致。第二种情况成立，因为θt+1=1意味着Ltθ=t+1和t+1<Dt+1上的σ。最后，在Dct+1上，我们有σ≤ t+1≤ Ltθ。我们注意到，（3.1）是作为上述第一次展示的一部分获得的。

它仍然表明jt（θ）≡E[GLtθ{Ltθσ} | Ft]P（Ltθ σ| Ft）=E【St+1Vt+1 | Ft】E【St+1 | Ft】≡ Jt，t<Te。由于分母为非零且符合（3.1），因此必须显示[GLtθ{Ltθσ} | Ft]=E[St+1Vt+1 | Ft]，t<t.（3.3）的确，（3.3）对于t是明确的≥ 这意味着P（Ltθ σ) = 0. t=t也很清楚- 1、对于t<Te∧ （T- 1） 我们用反向归纳法进行论证。我们首先观察到，通过下面（3.2）的类似论点，GLtθ{Ltθσ}=GLt+1θ{Lt+1θσ} 在Dt+1上∩ {θt+1=0}，Vt+1=St+1Vt+1on Dt+1∩ {θt+1=1}，0=St+1Vt+1 on Dct+1。（3.4）在集合Dt+1上∩ {θt+1=0}发生在（3.4）的第一种情况下，我们有[GLt+1θ{Lt+1θσ} | Ft+1]=E[St+2Vt+2 | Ft+1]=St+1Jt+1=St+1Vt+1，其中三个等式分别来自归纳假设、Jt+1和St+1的定义以及Jt+1=Vt+1 on{θt+1=0}。因此，我们可以取（3.4）中的条件期望，并得到恒等式E[GLtθ{Ltθσ} | Ft+1]=St+1Vt+1适用于所有地方。该塔的财产产生了索赔（3.3），证明是完整的。推论3.3。在示例2.1的马尔可夫设置中，T<∞, 存在一个偏好提前停车的独特均衡，该均衡是马尔可夫均衡。证据我们观察到，GT和Vtin定理3.1对于所有t都是σ（Xt，1Dt）-可测量的，然后θt也是可测量的。可以注意到，在上述结果中，停止偏好很重要：通过指定路径依赖的停止偏好并将奖励函数GT设为常数，很容易构造非马尔可夫平衡的示例。4有限期均衡：存在性以下结果表明，在包含具有可数状态空间的马尔可夫链的情况下，存在有限期均衡。定理4.1。假设Ftis a.s.对所有∈ T和thatlimt→∞Gt=克∞a、 s。

此外，假设P( t型∈ T：Gt≥ 0）>0且存在c>1，使得（ctGt）t≥0从上方一致有界。（4.1）则存在平衡。在陈述证据之前，让我们对假设进行评论。备注4.2。（a） 条件（4.1）特别涵盖了具有次指数增长的支付函数的贴现问题。考虑示例2.1的马尔可夫链设置，其中有一个有界且非负的支付函数g（t，x）和一个贴现因子δ∈ (0, 1). 然后设置gt=t的δtg（t，Xt）∈ T（和G∞= 0），我们发现（4.1）满足anyc∈ (1, δ-1).（b） 下面定理4.1的证明有三个步骤。限制停止策略θ的构造及其最优性条件的验证根本不需要（4.1）。后者用于确保θ是可容许的。还有许多其他情况下，可接受性保持不变，包括无折扣，可根据具体情况确定，例如具有有限状态空间和齐次报酬gt=g（Xt）的马尔可夫链的情况。条件（4.1）仅仅是编写简单而公平的一般结果的一种方法。当然，σ=∞ a、 s始终是p（τ）的有效条件 σ） 6=0，对于任何停止时间τ。（c） 类似地，在许多情况下，可以直接从G的附加结构看出Ltθ<∞ a、 s.适用于所有t∈ T、 在这种情况下，G∞I相关。（d） 另一方面，如果没有一些假设，就不能保证存在。例如，如果Te=∞ 域内，但P（σ<∞) = 1（参见下面的示例5.1，p>0），严格增加的奖励G导致不存在，因为停止对于任何代理都是不可取的，但θ除外≡ 不允许使用0。定理4.1的证明。对于t<∞, 设Atbe为生成Ft的原子的（可数）集合。

给定n≥ 1，考虑一个时间范围为n且let（θnt）为0的修正问题≤t型≤nbe运用定理3.1和Payoff（Gt）t得出的均衡停止政策≤n、 我们还设置θnt≡ 1因为我们称σ-场为离散的，如果它是由Ohm. 在具有可数状态空间的马尔可夫链的情况下，可以定义FTA，即样本路径在时间t.t之前生成的σ场≥ n、 注意，每个θntis是一个二进制序列（θnt（a））a∈在因此，通过对角线过程，我们可以找到一个子序列（再次表示为θn），该子序列在以下意义上收敛到停止策略θ：给定t<∞ 和A∈ 在，我们有θnt（A）=θt（A）f或所有足够大的n。如果没有有效的层位，则∧ n=t因此θnforn的容许性≥ 1表示t的θt=1≥ Te。为了证明θ是可容许的和平衡的，我们对∈ T和A∈ F并检查该州的可接受性和最佳条件。为便于记法，我们假设t=0，A=Ohm （一般情况下，仅通过编写条件期望和概率来区分）。为了进一步简化符号，我们设置τ=Lθ，τn=Lθn。θntoθ的收敛意味着τn→ τa.s.更准确地说，这种收敛在{τ<∞}, 得出1{τn<σ<∞}→{τ<σ<∞}a、 此外，{τ σ} = {τ < σ < ∞} ∪ {σ = ∞}, 其中，并集是不相交的，τn也是如此。因此{τnσ}→ 1{τσ} a.s.（4.2）可采性。我们必须确保P（τ σ) 6= 0. 考虑到（4.2），它会表现出一种可达状态，其中所有大n都会停止，因为这意味着P（τ σ） =limnP（τn σ) > 0.

事实上，在（4.1）之前，我们可以发现≥ 0和A∈ Atwith A DTGT（A）≥ 0和CTGT（A）≥csups≥0，A′∈As，A′DscsGs（A′）≥ sups公司≥t+1，A′∈As，A′DSC-1Gs（A′）和henceGt（A）≥ Gs（A′）表示所有s>t，A′∈ 用A′表示 Ds。这表明，对于位于（t，A）的代理，无论将来自己做什么，停止都是最优的。特别是，对于所有n，θnt（A）=1≥ t和τ≤ t<A上的σ。因此，P（τ σ) ≥ P（A）>0。最优性。证明连续值在固定初始状态下收敛；i、 e.，Jn：=J（θn）→ J： =J（θ）。一旦确定，如果θ=0，那么θn=0表示n大，因此G≤ Jn公司→ j表明θ=0是最优的，θ=1也是如此。看到jn=E[Gτn{τnσ} ]P（τn σ)→E[Gτ{τσ} ]P（τ σ） =J，注意分母在可容许性和P（τn）方面不为零 σ) →P（τσ） 根据（4.2）。鉴于τn→ τa.s.我们有Gτn→ Gτa.s.{τ<∞}.我们假设Gn→ G∞a、 在美国，这种趋同无处不在。也可以使用E[supt≤T | Gt | 1Dt]<∞ 和（4.2），分子的收敛遵循支配收敛。推论4.3。在定理4.1的条件下考虑马尔可夫设置（例2.1）。然后存在马尔可夫平衡。证据我们重新讨论定理4.1的证明。每个有限视界问题都是马尔可夫问题，因此推论3.3表明θ是马尔可夫问题。由于θtwa被构造为θnt的逐点极限，因此它也是σ（Xt，1Dt）-可测的。我们将在例5.3中看到，在时间均匀的环境中，这一推论无法得到改进：但平衡可能与时间有关。5有限层平衡：示例5.1非唯一性和非马尔可夫平衡以下示例表明，在有限层情况下，可能存在多个平衡。