近线性时间FTPL算法：弱可观测图Bandit新突破

在线学习中的反馈图（feedback graph）问题，一直是理论机器学习领域的一个有趣分支：智能体在每一轮只能观测到图中部分邻居的损失，而图的结构又决定了信息如何传播。当图是有向且“弱可观测”时，问题变得更加棘手——你甚至不知道哪些动作的损失是可以被观测到的。最近一篇来自arXiv的论文《Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits》提出了一种新的Follow-the-Perturbed-Leader（FTPL）策略，在保持算法简洁性的同时，实现了对抗与随机两种环境下的“最佳双方”保证，并且期望时间复杂度接近线性。

弱可观测图Bandit：背景与挑战

反馈图bandit是经典多臂bandit的推广：每个动作对应图中的一个节点，当选择某个动作后，只能观测到其出邻居（out-neighbor）的损失。若图是有向的，且智能体只能看到实际被观测到的损失，而不知道哪些节点不可观测，则称为“弱可观测”。这种设定在推荐系统、社交网络影响最大化等场景中有实际意义——你只能看到部分反馈，且反馈的可见性依赖于图结构。

以往针对弱可观测图的工作大多关注于极小极大（minimax） regret，其下界为Θ(T^{2/3})。然而，如何设计计算高效的算法，同时保持对随机环境的自适应（即实现log T的regret），一直是个开放问题。FTPL是一类简单而强大的算法框架：在每一轮对累积损失加上扰动，然后选择使扰动后损失最小的动作。但标准的FTPL直接应用于图bandit时，会面临损失估计困难、探索不足等问题。

反馈图bandit（feedback graph bandit） 是多臂bandit的一个推广模型，其中每个动作对应图中的一个节点，智能体选择某个动作后，只能观测到该节点出邻居（out-neighbor）的损失。图的结构决定了信息的传播方式：若图是强连通的，则通过适当策略可以高效地估计所有动作的损失；若图是弱连通的，则信息传播受限。弱可观测（weakly observable） 特指有向图中，智能体只能观测到实际被选动作的出邻居的损失，而无法直接知道哪些节点是不可观测的。这种设定在实际中常见于推荐系统（用户只反馈部分物品的评分）和社交网络影响最大化（信息沿有向边传播）。

极小极大（minimax）regret 是衡量bandit算法性能的标准指标，定义为算法累积损失与最佳固定动作累积损失之差的最大值（对环境最坏情况取上界）。对于弱可观测图bandit，已知的极小极大regret下界为Θ(T^{2/3})，其中T为总轮数。这意味着任何算法在最坏情况下至少产生T^{2/3}量级的regret。然而，在随机环境中（损失独立同分布），通常希望算法能自适应地达到对数regret（即O(log T)），这需要算法能够利用随机性。FTPL（Follow-the-Perturbed-Leader）是一类在线学习算法框架：每轮对累积损失向量加上随机扰动，然后选择使扰动后损失最小的动作。其简洁性和理论保证使其在bandit问题中广受欢迎。

FTPL的新颖损失估计器：强制探索与几何重采样

论文的核心贡献在于设计了一种基于图的损失估计器，使得FTPL能够处理弱可观测性。具体来说，作者结合了三个关键组件：

1. 强制探索（forced exploration）：以一定概率随机选择动作，确保每个节点都有机会被观测，从而避免因图结构导致的估计偏差。
2. 条件几何重采样（conditional geometric resampling）：当某个节点的损失未被观测到时，通过几何分布重采样来估计其期望损失。这种方法在保持无偏性的同时，控制了方差。
3. 带替代概率的自适应学习率（adaptive learning rates with surrogate probabilities）：学习率根据观测到的替代概率动态调整，使得算法在对抗和随机环境下都能自动适应。

这些组件共同作用，使得FTPL在保持简单结构（每轮仅需计算扰动后的线性优化）的同时，获得了理论上的保证。说个细节，损失估计器的设计巧妙地利用了图的结构信息，而不是简单地忽略弱可观测性。

条件几何重采样（conditional geometric resampling） 是一种用于估计未观测损失的技术。在弱可观测图bandit中，由于图结构限制，某些节点的损失可能永远无法被观测到。为了估计这些节点的期望损失，算法采用几何分布进行重采样：以一定概率重复采样直到观测到目标节点的损失，每次采样成功概率依赖于当前图结构和动作选择。条件几何重采样在给定历史信息的条件下进行，确保估计的无偏性，同时通过几何分布的尾部特性控制方差。具体而言，对于每个未观测节点，算法模拟从该节点出发的随机游走，直到到达一个可观测节点，从而构造损失的无偏估计。

替代概率（surrogate probabilities） 是指在损失估计过程中，用于替代真实观测概率的辅助概率。在弱可观测设定下，智能体无法直接知道每个节点被观测到的概率，但可以通过图结构和历史动作估计一个替代概率。自适应学习率根据这些替代概率动态调整：当替代概率较小时（即观测不确定性高），学习率相应减小以控制方差；反之则增大以加速收敛。这种设计使得算法在对抗和随机环境中都能自动适应，无需预先知道环境类型。

理论保证：对抗与随机环境的最佳双方

论文给出了两个主要regret界：

• 对抗环境：regret为\tilde{\mathcal{O}}(δ_^{1/3} T^{2/3})，其中δ_是分数弱支配数（fractional weak domination number），刻画了图的弱可观测性程度。当δ_*较小时，regret接近T^{2/3}，与已知下界匹配。
• 随机环境：regret为\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)，其中Δ_{\min}是最小次优间隙。这表明算法在随机环境下能够实现对数regret，且对δ_*的依赖是线性的。

这些结果首次表明，对于极小极大regret为Θ(T^{2/3})的问题，通过适当设计的自适应学习率和损失估计器，可以在不牺牲FTPL简洁性的前提下获得更精细的保证。与现有工作相比，该算法在计算效率上也有显著提升：期望时间复杂度接近线性，而此前的方法往往需要更高的多项式时间。

分数弱支配数（fractional weak domination number） 是刻画图弱可观测性程度的一个图论参数，记为δ_。直观上，它衡量了为了“支配”图中所有节点（即确保每个节点都能被某些节点的出邻居覆盖）所需的最小分数权重。在弱可观测图bandit中，δ_越小，表示图的结构越有利于信息传播，regret上界也越小。具体地，δ_*定义为最小化∑_{v} x_v（x_v≥0）使得对于每个节点u，存在从其出邻居到u的路径上的节点v满足x_v≥1。这个参数反映了图的连通性和可观测性，是分析regret的关键量。

最佳双方（best-of-both-worlds）保证 是指算法在对抗环境和随机环境下都能达到（接近）最优的性能，而无需预先知道环境类型。在对抗环境下，最优regret为Θ(T^{2/3})；在随机环境下，最优regret为O(log T)。最佳双方算法通过自适应机制（如自适应学习率）自动调整，以同时适应两种环境。本文的FTPL算法通过精心设计的损失估计器和学习率，首次在弱可观测图bandit中实现了这种保证，且计算效率接近线性。

计算效率：近线性时间的实现

FTPL的一个主要优势是每轮只需要解决一个线性优化问题（在扰动后的损失下选择最小损失动作）。然而，在弱可观测图bandit中，损失估计器的计算可能成为瓶颈。论文通过条件几何重采样和替代概率的巧妙设计，使得每次更新只需常数次图操作（如采样和查表），从而实现了近线性期望时间。具体来说，算法不需要显式地枚举所有未观测节点，而是通过概率方法隐式地处理弱可观测性。

这种效率提升对于大规模图上的在线学习至关重要。例如，在社交网络中，节点数可能达到数百万，近线性时间的算法才具备实际可扩展性。尽管论文目前只提供了理论分析，但其算法框架简洁，易于实现，为后续的实证研究奠定了基础。

总结与展望

这篇论文为弱可观测图bandit提供了一个优雅的解决方案：通过新颖的损失估计器，让经典的FTPL算法焕发新生，在保持简单性和高效性的同时，获得了对抗与随机环境下的最佳双方保证。其理论结果揭示了自适应学习率与损失估计器设计之间的深层联系，为未来研究开辟了多个方向，例如将框架推广到更一般的反馈结构、探索在强化学习中的应用，以及进行实验验证。

对于关注在线学习理论、bandit算法以及图结构反馈的研究者来说，这项工作值得仔细阅读。