随机重置路径搜索：图路径上的级联Bandit的路径级遗憾

# 随机重置路径搜索：图路径上级联赌博机的路径级遗憾 来源: https://arxiv.org/html/2607.15440 Guni Sharon 计算机科学与工程系 德克萨斯农工大学 大学城，德克萨斯州 77843 guni@tamu\.edu &Wei Zhang 计算机科学与工程系 德克萨斯农工大学 大学城，德克萨斯州 77843 komo@tamu\.edu ###### 摘要 我们提出*随机重置路径搜索*\(SRP\)，这是一个在已知有向图上的回合制学习问题，其中各边具有未知且平稳的成功概率。在每个回合中，智能体承诺遵循一条从源点到目标的路径，执行过程中任何边的失败都会将其重置回源点。SRP 模拟了量子中继网络中的纠缠分发、闪电网络上的支付路由以及不可靠无线 mesh 网络中的投递等场景。我们证明，全局重置结构使得最优策略是开环的，从而将 SRP 置于组合级联赌博机 (CCB) 框架中。我们提出了一种 Log-Dijkstra 元算法，并分别以 UCB (PathUCB) 和汤普森采样 (PathTS) 实例化。我们的主要技术结果是为 PathUCB 导出了一个路径级遗憾界，该界通过每条路径的*路径复杂度*C\(π\) 将遗憾分解到次优路径上，其中 C\(π\) 结合了每条边的前缀可靠性和后缀可靠性。该界与边级 CCB 界互补，并且在具有多项式多个源-目标路径的结构化图上信息量更大。在量子网络、分层 DAG、网格世界和 Erdős-Rényi 域上的实验支持了理论，并表明在所测试的算法中，PathTS 通常达到最佳经验性能。然后我们展示了一个对抗性实例，在该实例上 PathTS 未能收敛——这与乘法奖励问题上组合汤普森采样的一个已知指数级障碍一致。我们推荐 PathTS 作为实际默认选择，同时提醒存在对抗性实例的情况。 ## 1 引言 几个现实世界的网络化决策问题要求智能体遍历一个已知图，其中链路可能不可预测地失败，任何单次失败都会迫使从源点重新开始。例子包括量子中继网络中的纠缠分发 [Wehner et al. (2018)](https://arxiv.org/html/2607.15440#bib.bib28); [Chakraborty et al. (2020)](https://arxiv.org/html/2607.15440#bib.bib36)、闪电网络上的支付路由 [Pickhardt and Richter (2021)](https://arxiv.org/html/2607.15440#bib.bib3) 以及不可靠无线 mesh 网络中的投递 [Talebi et al. (2018)](https://arxiv.org/html/2607.15440#bib.bib20)。链路成功概率未知，必须通过反复交互来学习；智能体的任务是找到最可靠的源-目标路径，同时最小化失败的尝试。我们形式化这类问题为*随机重置路径搜索*\(SRP\)：在每个回合中，智能体选择一条路径 π，逐边尝试遍历，并在第一次失败时重置回源点。目标是关于最可靠路径 π∗=arg⁡maxπ∏e∈πpe 的累积遗憾最小化。SRP 表面类似于随机最短路径 (SSP) 问题，暗示可以使用目标导向的强化学习 [Barto et al. (1993)](https://arxiv.org/html/2607.15440#bib.bib33); [Bonet and Geffner (2003)](https://arxiv.org/html/2607.15440#bib.bib34); [Jafarnia-Jahromi et al. (2023)](https://arxiv.org/html/2607.15440#bib.bib10) 作为候选求解器。我们证明这种框架是不合适的：全局重置结构使得最优策略是*开环*的 (引理1)，将 SSP 的闭环机制简化为组合路径搜索，并将 SRP 置于 Kveton et al. (2015a) 的组合级联赌博机 (CCB) 框架中。我们的贡献是： - •问题约简。SRP 的最优策略是一个开环简单路径 (引理1)，可通过在 log 变换后的边权重上运行 Dijkstra 识别。 - •算法。一种 Log-Dijkstra 元算法 (算法1) 及其 UCB 和汤普森采样实例化 PathUCB 和 PathTS。PathUCB 与 CombCascade [Kveton et al. (2015a)](https://arxiv.org/html/2607.15440#bib.bib24) 密切相关；PathTS 没有 CombCascade 的对应物，并且在我们测试的大多数情况下是推荐的实际选择。 - •路径级遗憾界。定理5 将 PathUCB 的遗憾界为 ∑π∉Ψ∗C\(π\)2ln⁡T/Δ\(π\)，其中每条*路径的*路径复杂度 C\(π\) 编码了每条边的前缀可靠性 (观测概率) 和后缀可靠性 (估计误差的下游影响)。这种分解与边级 CombCascade 界互补，并且在具有许多源-目标路径的结构化图上信息量更大。 - •实证研究。在四个域上的实验验证了理论，并展示了一个对抗性实例，该实例上 PathTS 失败——这符合 Wang and Chen (2018) 对乘法奖励问题上组合汤普森采样的 Ω\(2k∗\) 障碍。 ## 2 问题形式化 我们考虑一个回合制学习环境，其中智能体在一个已知有向图上导航，各边具有未知且平稳的成功概率。 ###### 定义 1\(SRP 环境\)。一个 SRP 环境是一个元组 \(G,vs,vg,P\)，其中 G=\(V,E\) 是一个*已知*有向图，vs≠vg∈V 是*已知*源点和目标节点，而 P=\(pe\)e∈E∈\[0,1\]\|E\| 是一个在区间内的平稳边成功概率向量，对智能体*未知*。一个*有效简单路径*是边序列 π=\(e1,...,ek\)，其中 ei=\(vi−1,vi\)∈E，v0=vs，vk=vg，且无重复节点；我们记 \|π\|=k，并用 Ψ\(vs,vg\) 表示此类路径的集合。我们假设 Ψ\(vs,vg\)≠∅ (目标可达)。 转移动力学和反馈。在回合 t，智能体选择 πt∈Ψ\(vs,vg\) 并顺序遍历。每条边 ei 产生独立结果 Xei∼Bernoulli\(pei\)：成功时智能体前进，失败时该回合终止，并在 vs 开始新回合。智能体观测到结果，直到并包括第一次失败（如果未发生失败，则观测完整路径 \(Xe1,...,Xek\)）。 ###### 假设 1\(非退化边可靠性\)。存在已知常数 pmin\>0，使得对于所有 e∈E，pe∈\pmin,1\)。 目标。π 的*可靠性*为 P\(π\)=∏e∈πpe，目标是确定 π∗=arg⁡maxπ∈Ψ\(vs,vg\)⁡P\(π\)。 (1) 限制为简单路径不失一般性 (引理 [1])。性能由期望累积伪遗憾度量： R\(T\)=E\[∑t=1T\(p∗−P\(πt\)\)\],p∗=maxπ∈Ψ\(vs,vg\)⁡P\(π\)， (2) 其中期望是关于智能体的路径选择 πt。单回合遗憾 r\(πt\)=p∗−P\(πt\) 关于 πt 是确定性的。 ### 2.1 SRP 的结构性质 两个结构性质将 SRP 置于组合赌博机框架中：(1) 最优策略是开环的，(2) 规划简化为最短路径搜索。 ###### 引理 1\(开环最优性\)。在假设 1 下，假设 Ψ\(vs,vg\)≠∅，则 SRP 环境的最优策略等价于一个开环简单路径 π∗∈Ψ\(vs,vg\)。 ###### 证明。任何随机策略的成功概率是其确定性实现的期望，因此不会超过最佳确定性实现的成功概率。因此，考虑确定性策略 μ:V→E 就足够了，这对于有限 MDP 的最优性是充分的 [Puterman (2014)](https://arxiv.org/html/2607.15440#bib.bib43)。固定一个确定性 μ。如果其从 vs 出发的全部成功轨迹未到达 vg，则 P\(μ\)=0，并且 μ 被 Ψ\(vs,vg\) 中的任何路径支配 (该路径通过目标可达性存在，且根据假设 1 具有正可靠性)。否则，μ 诱导一个有限的源-目标行走 γμ=\(e1,...,em\)。由于任何失败都将智能体重置到 vs 且 μ 是平稳的，因此 μ 的单次尝试成功概率等于 γμ 中所有边成功的概率： P\(μ\)=∏i=1mpei。如果 γμ 包含一个环，比如对于某个 i<j 有 vi=vj，则删除该环得到一条更短的行走 γ′，其可靠性严格更高： P\(γ′\)=P\(γμ\)/∏ℓ=i+1jpeℓ>P\(γμ\)，其中严格不等式源于 pe<1 (假设 1)。重复此删除得到一个简单路径 π∈Ψ\(vs,vg\)，且 P\(π\)≥P\(μ\)。因此，每个策略都被某条简单源-目标路径支配。由于 Ψ\(vs,vg\) 有限且非空，存在最大可靠性简单路径 π∗，并且在每个回合开始时承诺采用 π∗ 是一个最优开环策略。 ∎ ###### 引理 2\(约简为最短路径\)。给定已知边概率 P，任何最优路径 π∗∈arg⁡maxπ∈Ψ\(vs,vg\)⁡P\(π\) 是在变换后的边权重 w\(e\)=−log⁡pe 下从 vs 到 vg 的最短路径，可通过 Dijkstra 算法找到 [Dijkstra (1959)](https://arxiv.org/html/2607.15440#bib.bib37)。 ###### 证明。对于任何路径 π，−log⁡P\(π\)=∑e∈π−log⁡pe=∑e∈πw\(e\)。由于 −log 是递减的，最大化 P\(π\) 等价于最小化 ∑e∈πw\(e\)。假设 1 给出 w\(e\)∈\(0,−log⁡pmin\]，因此 Dijkstra 算法可精确求解正权重最短路径问题。 ∎ log 变换在最可靠路径文献中是标准的 [Maheshwari (1974)](https://arxiv.org/html/2607.15440#bib.bib8)；任何精确的最短路径算法都可以替换 Dijkstra 而不影响下面的理论保证。 ## 3 相关工作 ##### 组合级联赌博机。级联赌博机由 Kveton et al. (2015b) 为析取 top-K 推荐引入，并由 Kveton et al. (2015a) 推广到具有合取 (乘积) 奖励的一般可行集，命名为*组合级联赌博机*\(CCB\)。SRP 是以 Ψ\(vs,vg\) 为可行集的 CCB 实例。相关的 CombCascade 算法对每条边的成功概率应用 UCB，并使用支撑我们分析的相同 (−log) 变换，得到了方程 (6) 的边级遗憾界，我们在第 5 节中进行了比较。后续工作将 CCB 扩展到上下文特征 [Li et al. (2016)](https://arxiv.org/html/2607.15440#bib.bib17)、对抗性腐败 [Xie et al. (2025)](https://arxiv.org/html/2607.15440#bib.bib16) 和状态相关的 RL [Du et al. (2024)](https://arxiv.org/html/2607.15440#bib.bib14)；这些扩展在范围上互补，但不能直接应用于 SRP。一个相关的研究线将随机最短路径路由视为具有*可加*边成本的组合赌博机 [Talebi et al. (2018)](https://arxiv.org/html/2607.15440#bib.bib20)；[Zhu and Modiano (2018)](https://arxiv.org/html/2607.15440#bib.bib19)，这与 SRP 的乘积式 ∏epe 奖励形成对比。 ##### 用于级联反馈的汤普森采样。存在两个相关的 TS 分析，但都不能直接覆盖 SRP。Cheung et al. (2019) 证明了 Beta-Bernoulli TS 在析取级联赌博机上的遗憾界，但其分析利用了拟阵结构，该结构不能推广到图路径。Wang & Chen (2018) 在半赌博机 (非级联) 反馈下分析了用于具有非线性奖励的一般 CMAB 的组合 TS，并展示了乘法奖励实例在前导遗憾常数上的 Ω\(2k∗\) 下界，其中 k∗=\|π∗\|。注记 1 讨论了将这些扩展到 SRP 的障碍。 ##### 目标导向的强化学习。随机最短路径 (SSP) 问题 [Cohen et al. (2020)](https://arxiv.org/html/2607.15440#bib.bib13); [Tarbouriech et al. (2021)](https://arxiv.org/html/2607.15440#bib.bib11); [Jafarnia-Jahromi et al. (2023)](https://arxiv.org/html/2607.15440#bib.bib10); [Johnson et al. (2025)](https://arxiv.org/html/2607.15440#bib.bib9) 将动作失败建模为转移到相邻的“滑动”状态，需要闭环策略 μ:V→E，并产生反映这种闭环结构的遗憾界 [Cohen et al. (2020)](https://arxiv.org/html/2607.15440#bib.bib13)。在 SRP 的全局重置动力学下，最优策略是开环的 (引理 1)，将问题置于赌博机而非强化学习领域。因此，现有的 SSP 界和算法 (包括最接近 PathTS 的 Jafarnia-Jahromi et al. (2023) 的后验采样方法) 不能直接适用。 ## 4 SRP 的图搜索方法 我们将学习过程 (列于算法 1) 框架化为一个迭代循环： (1) 估计每条边的可靠性， (2) 通过在 log 变换后的估计值上运行 Dijkstra 选择路径， (3) 尝试遍历该路径， (4) 在观测到的前缀上更新估计量。一个细微之处：UCB 风格的估计量可能通过其置信度奖励超过 1，在 −log 变换下将产生负边权重并使 Dijkstra 无效。因此下面定义的两个实例都将 p^e\(t\) 限制为 ≤1，确保 wt\(e\)≥0 并且 Dijkstra 返回 arg⁡maxπ∈Ψ\(vs,vg\)∏e∈πp^e\(t\)。 算法 1 Log-Dijkstra 元算法 0: 图 G=\(V,E\)，源点 vs，目标 vg，时域 T 1: 初始化所有 e∈E 的估计器状态 2: for t=1,...,T do 3: πt←Dijkstra\(G,wt,vs,vg\)，其中 wt\(e\)=−log⁡p^e\(t\) 4: 遍历 πt，令 K 为第一次失败的索引，或若全部成功则 K=\|πt\|