Oct, 2018

将后悔最小化和最佳臂识别融合，应用于 A/B 测试

PDF
TL;DR本文提出了一种在线学习算法，结合了最佳手臂识别和成本最小化两个目标，同时在保持遗憾最小化和最佳手臂识别方面具有保证，并将这些结果扩展到实践者面临的非独立同分布情况，旨在通过提供应用程序来权衡成本和决策时间。
online learningregret minimizationbest arm identificationdelta-pacnon-iid
发现论文，激发创造
  • 优化自适应实验：遗憾最小化和最佳臂识别的统一方法

    本文提出了一个统一的模型，同时考虑了实验内表现和实验后结果，为大规模人群中的最佳表现提供了一个清晰的理论，并揭示了一些新的洞见。

    Feb, 2024

  • 快速和遗憾最优的最佳臂识别：基本限制和低复杂度算法

    通过介绍一种新算法 ROBAI 和其变种，该研究识别并解决了在带有双重目标的多臂赌博机问题中达到最优臂的同时最大化奖励的难题；并对算法的停止时间、样本复杂性以及与经典 UCB 算法相比的性能进行了理论分析和数值实验，揭示出了经典 UCB 算法中的 “过度探索” 现象。

    Sep, 2023

  • 自适应多臂识别

    研究了如何在随机赌博机游戏中选择期望回报最高的 K 个赌臂问题，提出了一种基于概率近似正确算法，并引入了难度参数来量化问题难度。通过研究两种算法的采样复杂度，得出了更优的上界，并证明了该上界在某些情况下是紧的。同时得出了引入难度参数的实例相关算法需要额外的对数因子作为代价的下界。

    Jun, 2017

  • 上下文固定预算的最佳臂识别：具有策略学习的自适应实验设计

    个性化治疗建议、最佳治疗方法鉴定、上下文信息、自适应实验以及策略学习是这篇研究论文的关键词，通过推荐最佳治疗方法的决策策略获得最小的预期简单后悔，同时为政策学习、实验设计和自适应福利最大化提供了新的方法。

    Jan, 2024

  • 多种最佳臂的遗憾问题

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

    Jun, 2020

  • 上下文赌博机的最优 PAC 算法

    本文研究了 $(\epsilon,\delta)-\textit {PAC}$ 场景下的随机赌博机问题，给出了上下界，并提供了一个新的基于 argmax Oracle 的实例最优和计算效率高的算法。

    Jul, 2022

  • 成本感知的最佳臂识别

    该研究针对具有双重对象的最佳臂辨识问题进行了研究。在传统奖励的基础上，每个臂都与成本分布相关联，目标是通过最小的预期成本来辨识出最高奖励的臂。研究提出了一个理论下界和两种算法，以降低计算复杂性和实现近乎最优的性能。通过实验证明了忽视异质性行动成本会导致亚最优解，并且低复杂性算法在广泛的问题范围内提供近乎最优的性能。

    Feb, 2024

  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015

  • 博弈中协作学习的最优遗憾界

    我们研究了在一个通用的协作多智能体多臂老虎机模型中的遗憾最小化问题，在该模型中，每个智能体面临一个有限的臂集，并可以通过一个中央控制器与其他智能体进行通信。该模型中每个智能体的最优臂是具有最大期望混合奖励的臂，其中每个臂的混合奖励是其在所有智能体之间的奖励的加权平均，这使得智能体之间的通信至关重要。尽管在这个协作模型下已知最优臂识别的近似复杂度，但最优遗憾问题仍然是开放的。在这项工作中，我们解决了这个问题，并提出了第一个在这个协作老虎机模型下具有最优遗憾界限的算法。此外，我们还展示了只需要一个小的常数期望通信轮数。

    Dec, 2023

  • 更多适应性算法用于对抗式赌博机

    提出了一种新颖的算法，采用乐观性和适应性技术，结合在线镜像下降框架和特殊的对数障碍正则化器来解决对抗性多臂赌博机问题和组合半赌博问题，并在提高先前工作的同时，取得了多种新的数据依赖性遗憾界。

    Jan, 2018