Nov, 2020

渐进最优信息导向采样

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

    本文提出了一种基于信息定向抽样 (IDS) 的信息论贝叶斯遗憾界，在计算上能够高效地实现稀疏 IDS，通过数值实验表明相对于几个基线算法，稀疏 IDS 有明显的遗憾减少。

    May, 2021

  • 信息导向抽样和异方差噪声赌场算法

    本研究通过引入异方差噪声，重新考虑了随机赌博机问题，并提出了一种基于高斯处理模型的叫做 IDS 的新方法，该方法可以减小后悔和信息误差之间的比率，以优化贝叶斯优化算法。

    Jan, 2018

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

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

    Mar, 2014

  • 乐观信息导向抽样

    我们提出了一种新的分析框架，将俄罗斯和范・罗伊（2018 年）的信息导向抽样的贝叶斯理论与 Foster 等人（2021 年）的最坏情况理论基于决策估计系数相结合，通过我们的算法模板 Optimistic Information-Directed Sampling，可以实现与经典贝叶斯 IDS 方法类似的实例相关遗憾保证，但不需要任何贝叶斯假设。我们分析的关键技术创新是引入一种乐观的替代模型来衡量遗憾，并使用它来定义俄罗斯和范・罗伊（2018 年）的信息比率和 Foster 等人（2021 年）的决策估计系数的较少保守版本。

    Feb, 2024

  • 基于信息指导取样的带图反馈随机赌博机算法

    本文旨在解决具有图反馈的随机多臂赌博问题，探讨了 Thompson 采样和基于信息学的采样策略等方案，提出了 Bayesian 遗憾的限制，并通过数值实验证明了新的决策策略的有效性。

    Nov, 2017

  • 线性部分监督的信息引导采样

    该论文提出信息导向抽样方法在带线性奖励结构的随机局部监控中实现了自适应的最坏情况遗憾率，并且针对所有有限博弈分类了最小最大遗憾，IDS 在所有情况下都实现了最优率。

    Feb, 2020

  • 深度强化学习的信息导向探索

    本文提出了一种基于信息导向采样的探索策略，结合分布式强化学习的方法，应对异方差性观测噪声与参数不确定性的挑战，并在 Atari 游戏中展示出比传统策略显著的改进。

    Dec, 2018

  • 针对多种动作的汤普森取样的信息论分析

    本论文提供了一种新的、基于编码的方法，用于证明 Russo 和 Van RoyBayesian 遗憾界制度对先验不确定性的依赖性，其通过熵以及由于动作数量的不断增加，熵可以变得无限大。通过引入率失真的概念，建立了新的界，从而通过信息理论的方法来推导线性选择组失策问题的几乎最优界，并提供了逻辑选择组失策问题的一个界，比以前提供的界显著改善。

    May, 2018

  • 从最优性到鲁棒性：基于狄利克雷采样策略的随机赌博机算法

    本文研究通过基于经验指数的成对比较和数据相关探索奖励的重新采样来计算理论上不完整的手臂分布的 Dirichlet Sampling 算法，表明这些策略的不同变体在手臂分布有界时实现了可证明的最优遗憾保证，并且在半边界分布具有轻微的分位条件时，实现了对数遗憾。此外，我们还表明，通过对一类广泛的无界分布具有鲁棒性的简单调整，代价是比对数想定糟糕一些的渐近遗憾。最后，我们通过合成农业数据上的决策问题展示了 DS 算法的优点。

    Nov, 2021

  • 多智能体强化学习的可证明高效信息导向采样算法

    该研究设计和分析了一组基于信息导向采样（IDS）原则的新型多智能体强化学习（MARL）算法，这些算法受到信息论基础概念的启发，在两人零和马尔可夫博弈和多人一般和博弈等 MARL 环境中被证明具有高样本效率。

    Apr, 2024