Feb, 2024

多对数级别的极小极大遗憾的线性赌博机

PDF
TL;DR研究线性随机赌博机的噪声模型，介绍一种基于加权最小二乘估计的算法，能够最小化后悔度，通过几何论证独立于噪声模型，能够紧密控制每个时间步骤的期望后悔度为 O (1/t)，从而导致了累积后悔度的对数缩放。
linear stochastic banditsnoise modelminimax regretweighted least-squares estimationcumulative regret
发现论文，激发创造
  • 线性参数赌博机的近似极小极大后悔

    研究了有限动作集的线性上下文强化学习问题，介绍了一种名为 VCL SupLinUCB 的算法，并表明其与最佳下界相匹配，相较于之前的算法分析，节省了两个对数因子。

    Mar, 2019

  • 方差感知稀疏线性赌博机

    本文发展了一种数据稀疏 (稀疏线性斯托剖斯) 的新型算法，该算法使较小的环境维度下研究致命后果的风险得以降低，实现了一种有区别的、具有人造和样本方差适应性的总体安全算法。同时，该研究还探讨了如何在一种 <黑盒> 化的方式下将任何方差算法转化为 sparce linear bandits 算法。

    May, 2022

  • 高维稀疏线性赌博机

    研究高维稀疏特征的随机线性臂模型中，在数据匮乏的情况下，特征向量遵守固定的探测分布，通过探索然后提交算法，得到了 $Ω(n^{2/3})$ 的无维度极小遗憾下界和 $Θ(n^{2/3})$ 的上界。

    Nov, 2020

  • 在线线性优化带赌博式反馈的极小极大政策

    该研究提出了在线线性优化问题的带有 bandit 反馈的算法，并使用 Mirror Descent 算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略，证明了计算上以及最小二乘上的结果优化，为输出结果减少了冗余的符号。

    Feb, 2012

  • 线性赌臂机器人的纳什后悔保证

    在随机线性赌博机的框架中，我们获得了强化的后悔概念的紧密上界。这个强化的后悔概念被称为 Nash 后悔，它被定义为线性赌博机算法累积的预期奖励的几何平均值与（事先未知的）最优解之间的差异。我们开发了一种算法，在有限的臂集和无限的臂集两种情况下，实现了 Nash 后悔的上界。

    Oct, 2023

  • 对于带噪声高斯过程赌博优化的损失下界

    本文考虑如何基于无噪声样本和 Bandit 反馈来顺序优化黑盒函数，提出了一种新的 Gaussian 过程 Bandit 优化算法，并给出了算法无关的简单遗憾和累计遗憾的下界，进一步阐述了随机波动和目标函数的连续性对累计遗憾和简单遗憾的影响。

    May, 2017

  • 结构化随机线性 Bandits

    研究如何在处理具有结构属性的未知参数（例如稀疏、分组稀疏、低秩）的随机线性 Bandit 问题中构建置信椭圆，以达到更紧密的置信度范围和更尖锐的失误边界。

    Jun, 2016

  • 改进后的逻辑回归赌博机算法

    本研究提出了一种针对逻辑回归赌博机的新方法，避免了先前算法中会导致较差实验结果的一种问题，并获得了较紧的后果界限，这种算法不依赖于制定决策时的尺寸。

    Feb, 2020

  • 线性参数化赌博机

    本文研究基于多维随机向量臂收益的赌博机问题，证明了在解决特定问题时使用相应的相位策略可以达到最优的累计遗憾和贝叶斯风险，并提出了针对通用问题的近似最优解。

    Dec, 2008

  • 带有嘈杂赌博反馈对抗对局中的对数遗憾

    本文讨论了一种变种的零和矩阵博弈，在此博弈条件下，我们提出了一种新算法，可以在面对任意对手时实现 “对数级别” 后悔。

    Jun, 2023