Aug, 2022

概率触发臂或独立臂组合半匪徒问题的无关批量大小的后悔界限

PDF
TL;DR本研究探讨组合良带 (Bandits) 的算法，针对其大小批次 (K) 对后悔束缚的依赖性进行优化，发现一种可替代平滑性条件的新型触发概率和方差调节 (TPVM) 条件，进行后悔分析并提出基于置信区间和方差的 BCUCB-T 算法，将大小批次 (K) 的项降低至对数级别，并在非触发 CMAB 中将其完全去除。实验结果表明，我们的算法在不同领域具有优越的性能。
combinatorial semi-banditsregret boundprobabilistically triggered armsvariance modulated conditionregret analysis
发现论文，激发创造
  • 概率触发手臂组合半赌博算法的遗憾上界优化及应用

    该论文研究具有概率触发臂的组合多臂赌博机 (CMAB-T) 和半弱馈反的问题，将触发概率调制 (TPM) 条件引入 CMAB-T 框架中以达到更好的遗憾界限，并发现许多应用程序如影响最大化赌博机和组合级联赌博机满足 TPM 条件。此外，本文提供了下限结果，表明这种条件对于消除 $1/p^*$ 因子是至关重要的。

    Mar, 2017

  • 具上下文的组合赌博机、概率挑战的手臂

    本文针对情境组合赌博问题，提出了一种具有触发概率和方差自适应的算法，并给出了相应的遗憾界。在合成和真实世界数据集上的实验结果表明算法的优越性。

    Mar, 2023

  • 组合多臂老虎机问题的批量独立遗憾界

    针对组合多臂赌博机问题中的非线性奖励函数和批处理选择，引入一种新的平滑度标准 —— 基尼加权平滑度，证明了现有算法中的线性后悔量与批大小的关系可以被该平滑度参数取代，并在概率最大覆盖问题中获得了明显的精度提高。

    May, 2019

  • 组合多臂老虎机及其对概率触发臂的扩展

    该研究提出了一种通用的组合多臂赌博问题框架，将未知分布的基础臂组成超级臂进行玩耍，进一步探讨了更多可能基于已激发臂的结果触发概率的扩展，旨在通过在线学习算法实现最小化（α，β）- 逼近遗憾。

    Jul, 2014

  • 应用于逐步强化学习和其他领域的组合多元多臂赌博机

    引入一种新的组合多臂赌博梳理 (CMAB) 框架，具有多维和概率触发的臂 (CMAB-MT)，其中每个臂的结果是一个 d 维多维随机变量，反馈遵循普通臂触发过程。

    Jun, 2024

  • 具有一般奖励函数的组合多臂赌博机

    本文研究了随机组合多臂赌博机框架，提出了一种名为 SDCB 的新算法，该算法估计底层随机变量的分布和它们的随机显著性置信区间，并证明了 SDCB 可以实现 O (logT) 的分布相关遗憾和 $ ilde {O}(√T)$ 的分布无关遗憾，并将所得结果应用于 $K$-MAX 问题。

    Oct, 2016

  • 基于数据驱动的上界置信度在重尾赌博机上的近优遗憾

    本文提出了一种分布无关、数据驱动的上置信界（UCB）算法，结合最近发展的重新抽样中位数法（RMM）方法，对称奖励分布的研究中生成近乎最优的后悔边界，即使是重尾分布。

    Jun, 2024

  • 组合半臂老虎机的汤普森抽样

    本文研究了 Thompson 采样方法在随机组合多臂赌博机框架中的应用，分析了多种算法的累积遗憾，并给出了上限界以及其他算法之间的比较结果。

    Mar, 2018

  • 组合半臂老虎机的汤普森抽样的统计效率

    本文研究了采用半智能反馈的随机组合多臂赌博机问题。研究中提出了解决对于两种不同分布情况下是否存在效率最优、渐进遗憾最小算法的问题。通过分别采用 Beta 先验和高斯先验对 Combinatorial Thompson Sampling 策略进行了分析，进而找到了这两种分布情况下的算法解决方案，从而得出计算效率上优于 Efficient Sampling for Combinatorial Bandit 策略的结论。

    Jun, 2020

  • 随机组合半赌博机的紧急遗憾上限

    本研究利用 UCB-like 算法解决计算和采样高效的随机组合半贝叶斯在线学习问题，并分析了其 $n$ 步遗憾的上界，这里的遗憾是指最优解和次优解之间的预期回报差距。

    Oct, 2014