有限时间内动态赌博机渐近最优指数策略
提出了 “Streaming Bandits” 框架,该框架为不安宁的多臂赌博机问题,其中异构臂可以在有限寿命后进入和离开系统。该框架自然地解决了卫生干预计划问题,同时提供了一个新颖而高效的算法来计算 Whittle 索引解。
Mar, 2021
本文研究了在 Whittle 渐近制度下,针对具有多个拉动次数的有限时间不安定老虎机问题的指数政策和流体优先政策等解法,并在数字实验中证明了流体优先策略的较优性。
Jul, 2021
通过拉格朗日松弛和 Whittle 指数策略,本研究针对有限状态的多臂赌博机问题提出了一种解决方案,并使用值迭代算法验证了单臂赌博机的可指数性,讨论了在线掷骰策略和算法的计算复杂性,并通过数值实验证明,指数策略和掷骰策略优于短视策略。
Apr, 2023
我们提出了一种新的策略,该策略通过维护两个动态武器子集来解决离散时间无限视界平均奖励不安定强盗问题,其中一个子集具有近乎最优的状态分布并根据最优局部控制例程采取行动;另一个子集被驱向最优状态分布并逐渐合并到第一个子集中。我们证明了我们的策略在满足周期性 - 单链、非退化性和局部稳定性等温和假设的情况下在 N 臂问题中是渐进最优的,并且具有 O (exp (-C N)) 的最优性差距。我们的策略是首个在上述易于验证的假设集下实现指数渐近最优性的方法,而先前的工作要么需要强全局吸引子假设,要么仅实现了 O (1/sqrt (N)) 的最优性差距。我们进一步讨论了在显著减弱假设的基础上面临的基本障碍。特别地,我们通过证明一个下界,证明了局部稳定性对于指数渐近最优性是必要的。
May, 2024
我们研究了离散时间无限远平均回报的不安静赌博机问题,提出了一种新的策略类别,旨在将逐渐增大的一部分臂带向最优分布。我们证明了在 N 臂问题中,如果单臂松弛问题是单连通和非周期的,我们的策略是渐近最优的,具有 O (1/√N) 的最优性差距。与目前大多数关注索引或优先级策略,依靠统一全球吸引子属性(UGAP)以保证收敛到最优解的已有工作,或者最近开发的基于模拟的策略不同,我们的方法不需要同步假设(SA)。
Feb, 2024
讨论了一种无法使用贪心指数算法求解的 Feedback MAB 问题,开发出了一种新颖并且通用的双重算法技术,可为不少于 1+epsilon 的解提供 2+epsilon 的近似值,这个技术同样适用于其他不特定的喧闹强盗问题和 POMDP。
Nov, 2007
本文研究的是带有多动作的有限时间不安定多臂赌博机问题,提出了一种可行的指数策略 Occupancy-Measured-Reward Index Policy 以及一种学习算法 R (MA)^2B-UCB,相比现有算法在遗憾和运算量等方面表现更佳。
Sep, 2021
本论文探讨了不安定多臂赌博机的规划问题,提出了一种基于均场方法的规划算法来获得近似最优策略。通过实验分析,该算法在实际应用中表现优异且无需外部超参数。
Oct, 2022
本文研究在资源受限条件下随机过程的干预规划问题,并提出了一种解决异构工人的多工人多臂不懈赌博机问题的方法。通过开发基于指标的调度策略和 Whittle 指数的多工人扩展,实现公平性和高收益的干预计划。最后的实验结果表明,该方法在公平性方面表现优异,而在奖励积累方面只有轻微的牺牲。
Mar, 2023
本文研究了多类不定期赌徒的渐近最优控制问题,并提出了一类优先级策略,证明了在全局吸引子属性和技术条件下其是渐近最优的。我们将流体缩放技术与线性规划结果相结合,证明了当赌徒可索引时,Whittle 的索引策略包含在我们的一类优先级策略中。我们总结提出一些结论,包括关于如何选择来自渐近最优策略类的优先级策略等方面。
Sep, 2016