最佳选择躲避:关于多臂老虎机的纯探索的近最优多遍流式下限
本文解决了多臂赌博机模型 (single-pass MABs) 中的 regret minimization 问题,并设计出一些具有不同 memory 复杂度的算法分别达到了不同的最优 regret 上界,并且通过实验取得了较好的效果。
Jun, 2023
本文研究了纯探索问题中具有无限多臂的赌博机问题,针对固定置信和固定预算两种情形,提出了两种算法,分别以最小的期望和固定样本复杂度为目标,最终准确选择一个高质量臂,使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$,并给出了理论证明。
Jun, 2023
在 $P$ 次流式模型中研究随机多臂赌博机问题,通过设计一种算法,给出了关于 $m,n$ 和 $P$ 的最优遗憾度量的完整刻画,同时提出了一个上界和下界,结果在 $n$ 和 $P$ 方面具有紧密性。
May, 2024
研究了多臂赌博机中的最佳臂辨识问题,提出了一个基于顺序淘汰算法的通用框架,并基于采样机制和每轮淘汰臂数量提出了性能评估指标,设计了一种按剩余臂数的非线性函数划分预算的算法,能够在纯探索场景下获得改进的理论保证和实验性能。
Sep, 2016
本文提出了一种在随机模型下割臀膜机制下的多臂老虎机问题的差分隐私算法,其分别对应具体分布相关和分布无关两种后悔下界,并给出最优算法上界和良好的本地模型表现。
Jun, 2021
本研究提出的隐私保护算法在解决随机多臂赌博机问题时,相比之前的成果取得了较大的进展。算法可以保证最优遗憾率 O (Ɛ−1+logT), 通过实验证实了理论界和实践界之间的一致性。
Nov, 2015
研究多臂赌博机在 $k$ 个协作玩家中进行探索,以确定最佳手臂,结果表明协作与沟通可以实现更快的学习速度,最佳方案是 $k$ 倍的学习性能加速,且通信量只有 $log (1/ε)$。
Nov, 2013
该论文考虑了纯探索问题回报序列的低秩结构,提出了一种分离设置的探索策略,并通过利用奖励向量的核信息,提供了高效算法,同时展示了多臂赌博机问题下纯探索的上下界。
Jun, 2023
研究一种插值两种不同信息观察方式的在线决策问题,称为 $\mathbf {m}$-MAB。施加 $\mathbf {m}$-MAB 的紧凑极小后悔界,并为其纯探索版本 $\mathbf {m}$-BAI 设计了最佳 PAC 算法。本文还将 $\mathbf {m}$-MAB 的上限和下限扩展到了更一般的带有图反馈的情景下,并得出了在几个反馈图族中获得紧凑极小后悔界的结果。
Jul, 2023