Jun, 2024

多臂赌博机优化中的满意度探索

PDF
TL;DR基于满足性的探索概念，我们考虑了强化学习中满足性探索问题。我们提出了 SELECT 算法模板，通过低下界置信区间检验实现了广泛的满意后悔常数。通过与学习预言机合作，SELECT 不仅在可实现情况下找到潜在的满足性臂，还在不可实现情况下保证标准的后悔率，我们通过数值实验验证了 SELECT 在多种优化设置中的性能。
satisficing explorationbandit optimizationselectsatisficing regretlearning oracle
发现论文，激发创造
  • 时间敏感型赌博机学习中的满足性搜索

    这篇论文研究了一种名为 satisficing Thompson sampling 的算法，以探讨在时间敏感情况下，学习接近最佳行动而又需要更少信息的方法，在线性和无限臂赌博机上表现更卓越，同时还讲述了满足理论失真的概念与满足行动选择之间的关系。

    Mar, 2018

  • 时间敏感型贝叶斯优化多臂赌博机学习

    该文研究了在具有时间偏好的情况下的强化学习中，使用折扣累计损失代替累计损失，使用改进的 Thompson 抽样算法得到较强的解决方案。

    Apr, 2017

  • 多臂赌博机的宽容遗憾

    本文提出了一种忽略一定程度下最优性差距的 Bandit 算法，并以其为基础，设计优化算法 Thompson Sampling (ε-TS)。研究结果表明，该算法能够在一定程度上避免过度探索问题，并在保证性能的前提下，提高计算效率。

    Aug, 2020

  • 探索不再：非随机赌博机的改进高概率遗憾界限

    本文提出了基于 Implicit eXploration 的损失估计策略，可以在不需要不必要的探索成分的情况下，实现高概率遗憾界，取得了多臂赌博问题方面的改进结果。

    Jun, 2015

  • 多标准多臂老虎机的有约束遗憾最小化

    本研究提出一种叫做 Con-LCB 的算法，针对多维度、可能存在冲突评估指标的情况下，通过样本估算较优的 “主要” 指标，并且在满足 “次要” 指标的约束条件下，优化该主要指标，同时保证该算法的普适性和最优性，且在金融组合优化等应用领域也具有意义。

    Jun, 2020

  • 安全线性随机赌博机

    本文介绍了一个安全的线性随机挑战模型，其中学习器在每一阶段都需要选择一个预期奖励不小于预先确定的（安全）阈值的臂，以高概率。我们假设学习器最初掌握的是一个已知为安全但不一定最优的臂的知识。基于此假设，介绍了一种学习算法，它将已知的安全臂与探索性臂系统地结合起来，以便随时间安全地扩展安全臂集，同时促进后续阶段的安全贪婪利用。除了确保在每个播放阶段满足安全约束之外，所提出的算法还表现出一种预期的遗憾，在播放 T 个阶段后不超过 O（sqrt（T）log（T））

    Nov, 2019

  • 阈值型赌博机带有最优聚合遗憾

    本文提出了 LSA 算法，用于解决阈值赌博机问题，证明了该算法在实例方面渐近最优，通过多种不同情况下的实证结果证明其优于现有算法的表现。

    May, 2019

  • 算法选择作为带无限损失的赌博机问题

    本文提出一种将算法选择表示为部分信息的赌博问题的简单框架，并将现有的求解器适应于该游戏，证明了其期望遗憾的边界，该算法选择技术的也适用于此。

    Jul, 2008

  • 多种最佳臂的遗憾问题

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

    Jun, 2020

  • 单模臂：遗憾下限和最优算法

    研究了随机多臂老虎机问题，通过一个单峰函数来表示不完全有序的臂的期望奖励。对于离散和连续臂的情况，分别提出了 OSUB 和 UCB 算法，并得到了渐进的上下界和提高性能的实验结果。

    May, 2014