May, 2013

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

PDF
TL;DR研究在线组合优化问题下的半强化反馈，提出了一种结合 FPL 预测方法和新颖的损失估计程序（称为 Geometric Resampling）的学习算法，并且在能够进行高效离线组合优化的任何决策集合上可以有效实现。假设决策集合的元素可以用至多 m 个非零项的 d 维二进制向量来描述，证明了我们算法的期望遗憾在 T 轮后是 O (m sqrt (dT log d))，并且在全信息设置中也改进了 FPL 的最佳遗憾限制。
online combinatorial optimizationsemi-bandit feedbackfollow-the-perturbed-leadergeometric resamplingregret bounds
发现论文，激发创造
  • 在线非凸学习：跟随扰动领袖是最优的

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

    Mar, 2019

  • 组合半弦臂算法的一阶遗憾上界

    本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。

    Feb, 2015

  • 带有 Bandit 反馈的对抗性马尔可夫决策过程中的随机扰动领袖策略

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

    May, 2022

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

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

    May, 2023

  • 组合赌博机与相对反馈

    本文围绕多项式逻辑选择模型，研究了在线学习中集合选择的组合优化问题及其相关算法，并通过实验验证了理论结果。

    Mar, 2019

  • 跟随扰动领袖进行自适应在线预测

    应用聚合策略进行预测时，需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题；本文基于 Kalai 和 Vempala（2003）的 “Follow the Perturbed Leader”（FPL）算法，在两种不同的专家类别下得出了可调学习速率的损失界限，其中前者的损失界限与迄今为止最佳结果匹配，而后者为新结果。

    Apr, 2005

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

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

    May, 2023

  • 带部分信息的在线学习小损失界

    研究了拥有部分信息反馈的对抗 (非随机) 在线学习问题，在黑盒模型下能够获得如上小损失的概率，而其独特的设计使它在更多应用如半强盗问题和上下文强盗问题中得到有效的应用，并且能够提供一些之前无法获得的最优保证。

    Nov, 2017

  • 组合式预测游戏的极小化策略

    我们研究了在线线性优化问题，探讨了半强盗、强盗和完全反馈三种情况下的极小后悔量，并提出了使用 Bregman 投影技术的梯度下降通用策略以及上下界解决方案，并在最后指出了指数加权平均预测者对于 L∞对手是次优解的问题。

    May, 2011

  • 广义线性臂带问题中的随机探索

    研究广义线性臂选择算法的两种随机算法：GLM-TSL 和 GLM-FPL，并提供了对它们的 $\tilde {O}(d\sqrt {n \log K})$ 遗憾度性能保证，这两种算法在逻辑回归和神经网络算法中表现出色并明显更快。

    Jun, 2019