Mar, 2024

Follow-the-Regularized-Leader 竞争比分析及最佳学习率自适应

PDF
TL;DRFollow-The-Regularized-Leader (FTRL) 在在线学习中是一种有效且多功能的方法，调整其学习率的问题被形式化为序贯决策问题，并引入了竞争分析的框架。我们提出的学习率更新规则通过与竞争比率的下限相差一个常数因子来达到上限的目的，对于惩罚项的组成部分进行（近似）单调性的刻画，并针对一些特定环境构建了 BOBW 算法，从而在多臂赌博机、图赌博机、线性赌博机和上下文赌博机等不同设置下取得更紧的后悔界限和更广泛的算法适用性。
follow-the-regularized-leaderftrllearning ratecompetitive analysisregret bound
发现论文，激发创造
  • 在线学习中 FTRL 的简单自适应学习率与 Θ(T^{2/3}) 的最小 max 遗憾及其在最佳两全之间的应用

    通过设计自适应的正则化器和学习率，FTRL 是一个强大的框架，适用于各种在线学习问题。本文提出了一个新的自适应学习率框架来解决具有 Θ(T^{2/3}) 最小最大遗憾的问题，并应用于部分监控和图形赌博两个重要的间接反馈问题。

    May, 2024

  • 稳定性惩罚自适应 Follow-the-regularized-leader：稀疏性，游戏依赖性与双重优势

    研究自适应学习率对于解决实际问题的重要性，在此基础上提出了一个新的自适应学习率 ——Stability-Penalty-Adaptive (SPA)，可以进一步推广 Follow-the-Regularized-Leader (FTRL) 算法。该算法可以带来三种不同类型的自适应性：稀疏性、游戏依赖性和最佳方案等，其中，FTRL 算法常常用于求解棘手的多臂赌博问题，但现有算法假定稀疏性水平事先已知，新提出的学习率框架可以解决其不确定性，同时，该框架还可用于制定部分监督策略，并能同时实现 BOBW 算法和游戏依赖性的 bound。

    May, 2023

  • 广义隐式 Follow-The-Regularized-Leader

    该研究提出了一种新的在线学习算法，即广义隐式 FTRL，该算法扩展了 FTRL 框架的范围，可恢复已知算法，设计新的更新规则，直接改善遗憾的最坏情况的上界。

    May, 2023

  • 组合半匪谷、线性匪谷和 MDP 的非随机延迟反馈的统一分析

    本文提出了 Follow The Regularized Leader (FTRL) 算法并应用于在线学习中，通过分离延迟反馈成本和赌博反馈成本，得出了在三种不同的情况下的新结果，包括组合半赌博、带延迟的对抗 Markov 决策过程以及带权值的线性赌博。我们的新型遗憾分解显示 FTRL 在正则化程序的 Hessian 矩阵上的温和假设下，可在多轮中保持稳定，并为线性赌徒提供了一种有效算法和接近最优的遗憾限制。

    May, 2023

  • 医生对口罩使用的结论：有用但需辩证看待

    本研究提出了一种广义的最好结果算法以及如何通过规范化导向跟随和在线镜像下降算法实现在线学习中的最好结果，将这种算法应用于上下文、图和表马尔科夫决策过程中。

    Feb, 2023

  • 无尺度在线学习

    本文设计并分析了一种不需要任何上限或下限的在线线性优化算法，实现了适应损失向量范数的缩放不变性，并且通过 FTRL 和 MD 元算法实现了最优遗憾，并为无界决策集开发了一种非真空遗憾绑定的自适应算法，并对基于 MD 的无标度算法在无界域上的下限进行了研究。

    Jan, 2016

  • 线性预测中的跟随者和快速收敛：曲线约束集合和其他规律

    研究了在线学习算法中的 Follow the Leader (FTL) 算法，证明在一定条件下即使未必为凸损失函数时，其仍可以表现出与曲率相似的性能，同时可以在保证最坏情况下得到良好的结果。

    Feb, 2017

  • 带有弗雷歇特 - 类型尾部分布的跟随扰动领导者：对抗性赌博机中的最优性和最佳选择之间的折衷

    本文研究了在对抗性和随机的 K 臂赌博机中，随机扰动策略（Follow-the-Perturbed-Leader）的最优性。我们建立了对于扰动实现 O (√KT) 遗憾的充分条件，并展示了随机扰动策略在具有特定尾部分布的情况下实现的最佳两者能力。

    Mar, 2024

  • 最佳选择：具备未知转移的随机与对抗式序列决策问题（MDP）

    研究了通过 T 个 episode 学习马尔可夫决策过程中两全其美的问题，提出了一种新的变换，将方法从已知转移推广到未知转移下，并使得转移估计错误上界为多项式级别。

    Jun, 2021

  • 线性上下文强化学习最佳方案

    该研究探讨了在对抗性破坏下的 K 臂线性上下文赌博问题，并提出了一种在随机和对抗环境下具有理论保证的名为最佳两全（BoBW） RealFTRL 的策略。

    Dec, 2023