May, 2024

流式随机多臂赌博机中的记忆 - 遗憾权衡理解

PDF
TL;DR在 $P$ 次流式模型中研究随机多臂赌博机问题，通过设计一种算法，给出了关于 $m，n$ 和 $P$ 的最优遗憾度量的完整刻画，同时提出了一个上界和下界，结果在 $n$ 和 $P$ 方面具有紧密性。
发现论文，激发创造
  • 流式赌博问题的紧凑内存遗憾下界

    这篇论文研究了流式赌博机问题，建立了时间上界、臂数、游戏轮数的算法紧确的最劣后悔下限，并证明了与分析算法复杂度上限的样本复杂性分析问题的关系。

    Jun, 2023

  • 单次遍历流式多臂赌博机的严格遗憾界

    本文解决了多臂赌博机模型 (single-pass MABs) 中的 regret minimization 问题，并设计出一些具有不同 memory 复杂度的算法分别达到了不同的最优 regret 上界，并且通过实验取得了较好的效果。

    Jun, 2023

  • 无限臂老虎机的简单遗憾

    本文针对无穷臂随机赌博机问题，提出一种算法用以最小化简单损失，并扩展到多种情况下，如未知时间跨度等。

    May, 2015

  • 随机多臂赌博机的有限遗憾

    研究解决在已知最优的选择和最小间隔值时如何制定随机化策略，以解决随机多臂赌博问题中可能发生的后悔问题，并探讨了其下界和最优解等问题。

    Feb, 2013

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

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

    Jul, 2019

  • 最佳选择躲避：关于多臂老虎机的纯探索的近最优多遍流式下限

    纯探索、多臂赌博机、多次传递流算法、样本通过折衷、奖励差距

    Sep, 2023

  • 混洗模型下的差分隐私多臂老虎机

    本文提出了一种在随机模型下割臀膜机制下的多臂老虎机问题的差分隐私算法，其分别对应具体分布相关和分布无关两种后悔下界，并给出最优算法上界和良好的本地模型表现。

    Jun, 2021

  • 自适应遗憾在可能的情况下：只需两个查询

    在线优化中，给出了强适应遗憾的准确查询和遗憾最优的贪心算法，同时给出了多臂赌博机和赌博凸优化的最优算法，并通过实证研究表明了在不稳定环境和下游任务中的卓越表现。

    Jan, 2024

  • 计数型赌博机的完整策略遗憾界

    研究了限制对手策略的措施，旨在实现最强版本的策略后悔，即完全策略后悔。提出概念式为 “计票老虎机” 的在线学习算法，并针对该算法提供了一种具有可接受保证的算法，证明了算法的近似最优性。

    Apr, 2022

  • 多种最佳臂的遗憾问题

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

    Jun, 2020