Dec, 2023

单调随机优化的半强盗学习

PDF
TL;DR通过提供一种具有与最佳近似算法（在已知分布下）相对于平方根的 T 乘以 log T 束缚的通用在线学习算法，在半探测器环境中解决了在一大类 “单调” 随机问题中对于未知分布是否能够获得良好（近似）算法进行学习的问题。我们的框架适用于随机优化的若干基本问题，如先知不等式、潘多拉盒、随机背包、随机匹配和随机次模优化。
stochastic optimizationonline learning algorithmunknown distributionssemi-bandit settingstochastic problems
发现论文，激发创造
  • 在线一位反馈随机线性优化

    本文研究在线随机线性优化的特殊赌徒环境，其中每轮只有一位信息被揭示给学习者。我们假定二元反馈是从对数模型产生的随机变量，并旨在最小化未知线性函数定义的遗憾。为了解决此挑战，我们通过利用观测模型的特定结构开发了一种高效的在线学习算法。

    Sep, 2015

  • 随机优化的购买信息

    本文研究如何以在线学习问题的形式购买信息来帮助随机优化问题，提出了一个 $2$-competitive 算法和一个 $e/(e-1)$-competitive 随机化算法，特别应用于 Min-Sum Set Cover 优化问题。

    Jun, 2023

  • 在随机和对抗半臂匪中的最优解决方案

    开发出新的半强化学习算法，不需要先验信息，可同时在随机环境和对抗环境下获得对数级和平方级的遗憾，并通过在合成数据上的实验证明了其性能的一致性和优越性。

    Jan, 2019

  • 赌博机凸优化问题的最优算法

    本文针对带有随机反馈的在线凸优化问题（称为 bandit convex optimization），通过将椭球法应用于在线学习，给出了第一个 $\tilde {O}(\sqrt {T})$-regret 算法，并引入了离散凸几何中的新工具。

    Mar, 2016

  • 随机组合半赌博机的紧急遗憾上限

    本研究利用 UCB-like 算法解决计算和采样高效的随机组合半贝叶斯在线学习问题，并分析了其 $n$ 步遗憾的上界，这里的遗憾是指最优解和次优解之间的预期回报差距。

    Oct, 2014

  • 在线凸优化的广义方法

    本研究分析了在线凸优化问题在不同情境下的处理方法，并在具有完全适应性对手的在线线性优化算法为在线凸优化算法提供了一个模板，同时将需要完全信息反馈的算法转换为具有相近遗憾界限的半强盗反馈算法。此外，通过对半强盗反馈中使用确定性算法的完全适应性对手和使用随机算法的毫无意识对手进行比较，我们证明了可以在面对不可避免对手时，设计针对完全适应性对手的算法使用仅具有随机半强盗反馈也能获得类似界限。基于此，我们提出了将一阶算法转换为零阶算法，并具有相近遗憾界限的通用元算法框架。我们的框架允许在不同情境下分析在线优化，如全信息反馈、强盗反馈、随机遗憾、对手遗憾和各类非稳定遗憾。利用我们的分析，我们提供了第一个使用线性优化预言机的无投影在线凸优化算法。

    Feb, 2024

  • 有约束的在线两阶段随机优化：具有（和不具有）预测的算法

    我们考虑了一个在线两阶段随机优化问题，有关于 T 个周期的长期约束。我们通过对抗学习算法开发了在线两阶段问题的在线算法，同时，我们的算法的遗憾界可以降低到嵌入对抗式学习算法的遗憾界。基于这个框架，在不同的设置下，我们得到了新的结果。

    Jan, 2024

  • 基于随机贪心学习的非单调随机次模最大化全博弈反馈

    本文研究具有完全机器人反馈和随机奖励的无限制组合多臂武器匪徒问题，提出随机贪心学习算法 (RGL)，证明其对于时间区间 T 和武器数 n，达到 1/2 遗憾上限 Õ(T^(2/3))，并在实验中展示了其对于非次模和次模设置都优于其他全机器人变体。

    Feb, 2023

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

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

    Feb, 2015

  • 一种连续时间的在线优化方法

    研究一种基于连续时间的在线优化策略族，证明其能够达到无遗憾学习。从传统的离散时间角度来看，这种方法可导出大量离散时间算法（包括一些经典遗憾分析算法）的无遗憾性质，并统一了许多经典的遗憾上界，得到了一个无需借助于倍增技巧即可保证 $O (n^{-1/2})$ 遗憾上界的学习策略类。

    Jan, 2014