Oct, 2023

高效纯探索的双向算法设计

PDF
TL;DR在具有有限备选方案的随机顺序自适应实验中，我们考虑了纯探索问题。利用双变量，我们表征了最优分配的必要和充分条件，并提出了一个信息导向的选择规则。我们证明了，在某些条件下，与信息导向的选择相结合的前二 Thompson 抽样在高斯最优臂标识中是（渐近）最优的。
pure-exploration problemssequential adaptive experimentsranking and selection problemsstrong convergencethompson sampling
发现论文，激发创造
  • 简单贝叶斯算法的最佳臂识别

    本文提出了三种简单直观的贝叶斯算法，旨在通过适应性地分配测量功夫，有效地识别有限选项或设计中的最佳选择，而这些简单算法能够以最佳方式实现这一目标。

    Feb, 2016

  • 最优探索与汤普森抽样同等难度

    该论文提出了一种利用采样和 argmax oracle 来实现指数收敛率的算法，以解决纯探索线性赌博问题，并证明了该算法在实践中与现有的渐近最优方法相当。

    Oct, 2023

  • 阈值赌博机问题的最优算法

    本文提出一种基于启发式算法的无参数算法，用于解决特定的组合纯探索随机赌博机问题，以寻找一组平均值高于给定阈值的摇臂，满足给定精度和一定的时间限制，并证明该算法是情况下的最优解决方案，并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题，并构建了最优策略。

    May, 2016

  • 自适应双探索权衡策略用于异常检测

    本文研究一类基于阈值的异常检测问题，提出双重探索算法，通过构建自适应置信区间和自动平衡各臂探索与阈值探索的权衡，实现更高效的异常检测。实验表明本算法在合成和真实数据集上均表现出色。

    May, 2020

  • 带虚拟协助代理的汤普森抽样

    文章提出了一种基于多臂赌博框架的在线顺序决策支持方法，利用 Thompson 抽样来平衡探索与利用的权衡，提出了两种算法用以解决多臂赌博问题，并在理论上给出了广义下界，通过实验证明了该方法在现实世界的数据集上表现的有效性。

    Sep, 2022

  • 通过解游戏进行非渐近纯探索

    本文提出了一种适用于纯探索问题和赌博机结构的不需完全解决优化问题的优化算法，并获得了对指数族的适应性和有限信心保证。

    Jun, 2019

  • 组合型纯探索的近最优采样算法

    本文研究了随机多臂老虎机的组合纯探索问题，提出了一种新的样本复杂度的下界和一种新的抽样算法，并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外，我们还提出了更通用的问题，并针对其提供了样本复杂度的上下界。

    Jun, 2017

  • 双掷硬币汤普森抽样在对决式多臂老虎机算法中的应用

    该论文通过提出 D-TS 算法，使用 Thompson Sampling 解决了 dueling bandit 问题，该算法适用于一般的 Copeland dueling bandits，其中 Condorcet dueling bandits 是其特例，并在合成和真实数据上进行了模拟，证明了算法的效率。

    Apr, 2016

  • 渐进最优信息导向采样

    介绍了一种基于信息导向采样（IDS）框架的简单高效的针对动作数有限的随机线性赌博机问题的算法，在有限时间内渐近最优，并且几乎是最坏情况下的最优。研究发现 IDS 如何在遗憾和信息之间平衡权衡，并揭示了最近被提出的原始对偶方法和 IDS 算法之间的惊人联系。通过实验表明，IDS 在有限时间内与 UCB 竞争力强，在渐近阶段更优。

    Nov, 2020

  • 信息引导采样的优化学习

    该研究提出了一种新的信息导向采样的方法，它适用于在线优化问题，通过学习部分反馈，决策者需要在探索和利用之间取得平衡。

    Mar, 2014