FTPL
在线学习中的一类算法框架，每轮对累积损失向量施加随机扰动，然后选择使扰动后损失最小的动作，以简洁性和理论保证著称
时间轴 (近 90 天)
论文《Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits》提出了一种新的FTPL策略，在弱可观测图Bandit中实现对抗与随机环境的最佳双方保证，且期望时间复杂度接近线性。
在对抗环境下，论文算法的regret为\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})，其中δ_*是分数弱支配数。
在随机环境下，论文算法的regret为\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)，其中Δ_{\min}是最小次优间隙。
该算法通过条件几何重采样和替代概率的设计，使每次更新只需常数次图操作，从而实现了近线性期望时间，无需显式枚举所有未观测节点。
全部知识事实 (4)
论文《Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits》提出了一种新的FTPL策略，在弱可观测图Bandit中实现对抗与随机环境的最佳双方保证，且期望时间复杂度接近线性。
50%待验证在对抗环境下，论文算法的regret为\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})，其中δ_*是分数弱支配数。
50%待验证在随机环境下，论文算法的regret为\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)，其中Δ_{\min}是最小次优间隙。
50%待验证该算法通过条件几何重采样和替代概率的设计，使每次更新只需常数次图操作，从而实现了近线性期望时间，无需显式枚举所有未观测节点。
50%