Nov, 2020

Restless-UCB，在线不安定赌博机的高效低复杂度算法

PDF
TL;DR提出了一种名为 Restless-UCB 的在线学习策略来解决在线探索期望最大化问题，在 Restless-UCB 中，利用前期的探索来做出更好地决策，证明了期望最大化问题在合理的标准下得到了可行的上界，相较于现有算法，使用一种新的对于状态转移进行利用的方法来消除在泊松极限中出现的指数因子，同时也能用于优化现有算法。
restless banditmarkov chainlearning policyregret upper boundexploitation
发现论文，激发创造
  • 不静态赌博机问题的近似算法

    讨论了一种无法使用贪心指数算法求解的 Feedback MAB 问题，开发出了一种新颖并且通用的双重算法技术，可为不少于 1+epsilon 的解提供 2+epsilon 的近似值，这个技术同样适用于其他不特定的喧闹强盗问题和 POMDP。

    Nov, 2007

  • 不安定线性赌臂机

    基于线性赌博问题的更一般的表述考虑了随时间的依赖性，提出了一个近似算法 LinMix-UCB，该算法在依赖性较强的情况下能够控制误差并保证次线性后悔。

    May, 2024

  • 关于不安分马尔科夫赌博机的遗憾界限

    本文介绍了一种算法来解决不安分的马尔科夫赌臂问题，并证明了基于指数的策略在这个问题中一定是次优的。该算法可以在不需要假设马尔可夫链除了不可约的任何情况下，经过 T 步后实现相对于知道所有赌臂分布的最佳策略的 O (√T) 的悔恨。

    Sep, 2012

  • 乐观 Whittle 指数策略：动态赌博机的在线学习

    该研究提出了一种基于 Whittle 指数策略的在线学习算法 UCWhittle，使用上限置信度方法学习转移动力学来解决具有未知状态转移的 RMAB 问题，该算法在三个不同领域均表现出比现有在线学习算法更好的性能。

    May, 2022

  • 休息和不休息赌博机的在线学习

    本文研究了涉及休息和不休息的多臂赌博机和多次游戏的在线学习问题，在每个时间步骤，用户可以玩 M 支手臂，其目标是决定每一步要播放哪些 K 支手臂，以在一系列试验中最大化其长期奖励，尤其与机会式频谱接入（OSA）的应用相关。

    Feb, 2011

  • 在不断变化的世界中学习：具有未知动态的不安定多臂赌博机

    此篇研究考虑了一个名为不安定多臂赌博机问题的模型，提出了一种探索和利用并行局部的策略，使得在一定的系统参数有限制时，能够获得对数级次的回报，而在缺乏关于系统的任何信息时，能够获得接近对数水平的回报。同时，也将问题扩展到了多个分布式参与者共享资源的情况，并得出相应结果。结果对于各种动态系统和通信网络以及金融投资的自适应学习都有应用。

    Nov, 2010

  • 可证明高效的对抗性不安静多臂赌博机强化学习：未知转换和赌博机反馈

    通过使用一种创新的偏置对抗性奖励估计器和低复杂度指标策略，我们开发了一种新颖的强化学习算法来解决具有未知转换函数和敌对奖励的周期性不安定性多臂赌博机问题，以最大化总的敌对奖励，并确保在每个决策阶段满足瞬时激活约束条件，我们的算法在我们所考虑的具有挑战性的设置中保证了约根号 T 的遗憾界，这在我们的所知范围内是首次实现的。

    May, 2024

  • 有限时段不静态多臂多动作赌博机的强化学习

    本文研究的是带有多动作的有限时间不安定多臂赌博机问题，提出了一种可行的指数策略 Occupancy-Measured-Reward Index Policy 以及一种学习算法 R (MA)^2B-UCB，相比现有算法在遗憾和运算量等方面表现更佳。

    Sep, 2021

  • 成本感知级联赌博算法

    本文提出了一种成本感知的级联赌博模型，研究其应用在在线和离线环境下的表现，并介绍了一种新的成本感知级联上置信区间算法以解决在线环境下的问题。

    May, 2018

  • 非平稳线性赌臂问题的简单解法

    本文研究了非平稳线性臂问题，提出了一种基于重启策略的算法以平衡利用和探索，并证明了该算法的动态遗憾值，同时还解决了现有算法中的严重技术缺陷问题。

    Mar, 2021