Mar, 2024

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

PDF
TL;DR本文研究了在对抗性和随机的 K 臂赌博机中，随机扰动策略（Follow-the-Perturbed-Leader）的最优性。我们建立了对于扰动实现 O (√KT) 遗憾的充分条件，并展示了随机扰动策略在具有特定尾部分布的情况下实现的最佳两者能力。
optimalityfollow-the-perturbed-leaderadversarial banditsstochastic banditsextreme value theory
发现论文，激发创造
  • 带有 Bandit 反馈的对抗性马尔可夫决策过程中的随机扰动领袖策略

    通过研究 Follow-the-Perturbed-Leader 算法在 Adversarial Markov Decision Processes 中的应用，作者发现该算法不仅在有限时间内能够实现近似最优的 regret bound，并且能够有序地处理 Delayed Bandit Feedback 问题，并且进一步提出了第一个无悔学习算法来解决在无限时间内、使用有限的 bandit feedback 和随机转移的情况下解决 AMDPs 问题。

    May, 2022

  • 在线非凸学习：跟随扰动领袖是最优的

    研究基于非凸损失的在线学习问题，证明了经典的 Perturbed Leader 算法在该设置下可达到最佳遗憾率，进一步证明乐观的 FTPL 算法在序列损失可预测时的遗憾界更优。

    Mar, 2019

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

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

    May, 2023

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

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

    Feb, 2023

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

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

    Dec, 2023

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

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

    May, 2023

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

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

    Jun, 2021

  • 一种高效的半强化反馈学习算法

    研究在线组合优化问题下的半强化反馈，提出了一种结合 FPL 预测方法和新颖的损失估计程序（称为 Geometric Resampling）的学习算法，并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述，证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d))，并且在全信息设置中也改进了 FPL 的最佳遗憾限制。

    May, 2013

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

    Follow-The-Regularized-Leader (FTRL) 在在线学习中是一种有效且多功能的方法，调整其学习率的问题被形式化为序贯决策问题，并引入了竞争分析的框架。我们提出的学习率更新规则通过与竞争比率的下限相差一个常数因子来达到上限的目的，对于惩罚项的组成部分进行（近似）单调性的刻画，并针对一些特定环境构建了 BOBW 算法，从而在多臂赌博机、图赌博机、线性赌博机和上下文赌博机等不同设置下取得更紧的后悔界限和更广泛的算法适用性。

    Mar, 2024

  • 在线学习中 FTRL 的简单自适应学习率与 Θ(T^{2/3}) 的最小 max 遗憾及其在最佳两全之间的应用

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

    May, 2024