最大 - 最小分组赌博机 | BriefGPT

AAAINov, 2021

最大 - 最小分组赌博机

Max-Min Grouped Bandits

Zhenlin Wang, Jonathan Scarlett

TL;DR介绍了一种多臂赌博机问题，称为最大最小分组赌博机问题，其中将赌臂分组，并旨在找到最差赌臂平均回报最高的组；提出两种基于连续淘汰和鲁棒优化的算法，并导出保证找到最优或接近最优组的样本数的上界，以及一个独立于算法的下界。探讨了各种相关情况下上下限的紧度以及导出统一紧限的困难。

Abstract

In this paper, we introduce a multi-armed bandit problem termed max-min grouped bandits, in which the arms are arranged in possibly-overlapping groups, and the goal is to find the group whose worst arm has the highest mean reward. This problem is of interest in applications such as rec

multi-armed bandit problem max-min grouped bandits successive elimination algorithm robust optimization resource allocation

发现论文，激发创造

MaxGap Bandit：适应性算法用于近似排名

本文研究自适应地从 K 个分布（臂）中抽样，以确定任意两个相邻均值之间的最大差距，即最大间隙赌博机问题。作者提出消除与 UCB 风格的算法，并证明了它们是极小化的最优解。实验结果表明，UCB 风格的算法需要的样本数量比非自适应抽样少 6-8 倍。

Jun, 2019

多种最佳臂的遗憾问题

本篇论文旨在应对多臂赌博机问题中存在多个最优 / 近似最优机械臂的后悔最小化问题，通过提出自适应算法来自动适应问题的难度，并在理论和实验方面展现了该算法的优越性。

Jun, 2020

组合多臂赌博机的紧密下界

本研究探讨了组合多臂赌博的后悔下界，并证明了在所有光滑奖励函数下，这种下界都是合理的，并且根据 Merlis 和 Mannor（2019）提出的 Gini 加权平滑度参数确定单调奖励函数的下界。

Feb, 2020

针对玩家武器平均值不同时的多人老虎机实用算法

本论文针对多人随机多臂老虎机问题中，玩家无法通信且产生碰撞时得分为零的情形。解决了不同玩家可能具有不同的均值的异质设置，并提出了一种新的有效算法，结合了强制碰撞的隐式通信和匹配消除的思路。并给出了有限时间分析，证明了该算法的次线性极大遗憾界，解决了 NeurIPS2018 的一个开放性问题。

Feb, 2019

协作多智体异构多臂赌博机

研究多人合作多智能体赌博问题，提出一种新的多人合作环境，并利用分散式演算法促进代理之间的合作，推导每个代理的累积遗憾度和群体的遗憾度上下限，并证明了该算法的近似最优行为。

May, 2023

分散式随机多人多臂行走赌博机

提出了一种解决多人多臂赌博机问题的分布式算法，利用上置信区间和分布式优化技术，解决了现实世界应用中玩家仅能访问动态局部子集的问题，并获得了接近最优的后悔率。

Dec, 2022

保守型赌徒

研究一种新颖的多臂赌博问题，旨在解决公司在探索最大化收益新策略的同时，保持其收益在固定时间内持续增长的挑战。通过提出自然而又新颖的策略来维护限制，我们在随机和对抗设置下分析了限制维护的代价。

Feb, 2016

具有协变量的非参数贝叶斯赌博机

本文对一类赌博机问题进行了研究，提出了一种新算法，结合非参数统计和传统赌博机算法方法，在最大化累积预期收益的目标下，取得了与理论下界相同的性能，同时具有良好的适应性。

Mar, 2010

重新审视 Woodroofe 的单臂匪徒问题

研究了采样分布依赖于一个参数和一个协变量的两个总体的顺序采样问题，并在极小极大的背景下发展了速率最优策略，哪里遗憾以及从较劣的总体进行采样的速率可以是有限的或随着时间变化而以不同的速率增长，这取决于协变量分布的 “本地” 特性。

Sep, 2009

聚类多智能体线性赌博

研究了多智能体线性随机赌博问题的特定情况，称为聚类的多智能体线性赌博。提出了一种新颖的算法，在多个智能体之间有效合作以加快整体优化问题。通过在合成数据和真实数据上与最先进的算法进行经验评估，理论分析了后悔最小化问题和聚类质量，证明了我们方法的有效性：我们的算法显著改善了后悔最小化，并成功恢复了真实的聚类划分。

Sep, 2023