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

Oct, 2023

Nash Regret Guarantees for Linear Bandits

Ayush Sawarni, Soumybrata Pal, Siddharth Barman

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

Abstract

We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening -- referred to as nash regret -- is defined as the difference between the

stochastic linear bandits nash regret fairness guarantee algorithm regret upper bound

发现论文，激发创造

公平多智体社会福利优化的无懊悔学习

在线多智能体 NSW（Nash 社会福利）最大化问题中，我们提出了一种完全回答 NSW 作为目标的无悔公平学习是否可能的算法，并且在不同设置下得到了相应的后悔界限。

May, 2024

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

研究线性随机赌博机的噪声模型，介绍一种基于加权最小二乘估计的算法，能够最小化后悔度，通过几何论证独立于噪声模型，能够紧密控制每个时间步骤的期望后悔度为 O (1/t)，从而导致了累积后悔度的对数缩放。

Feb, 2024

线性参数化赌博机

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

Dec, 2008

对数贝叶斯遗憾界

研究提出了贝叶斯奖励机制的有限时间对数遗憾度的边界及其应用，并发现了这些权重实际上可以加强已知的上界。

Jun, 2023

合作非随机多臂老虎机中的个体遗憾

研究通过交换信息在底层网络上通信的代理，以优化共同的非随机多臂赌博问题中各自的遗憾。我们推导出遗憾最小化算法，其中保证每个代理 v 的期望遗憾都是（1+K/|N (v)|)^T 的平方根量级。

Jul, 2019

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

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

May, 2017

无范数偏见的线性赌博机

本文提出了两种不需要先验知识的新算法，一种针对较小的变动武器集，另一种针对固定武器集，其悔恨界仅仅受到次要影响。

May, 2022

高斯过程赌博机的最优顺序简单后悔

研究了高斯过程二元组和连续性优化问题之间的联系，建立了稳健分布，使用分步方式获得最终收敛结果并得到了一系列引理。

Aug, 2021

探索先行，利用随后：强盗问题中后悔的真实形状

本文研究多臂老虎机问题的遗憾下界，并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明，在初始阶段遗憾几乎线性增长，并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质，并去除了所有不必要的复杂性。

Feb, 2016

线性参数赌博机的近似极小极大后悔

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

Mar, 2019