带多臂的不安匪徒问题:打败中心极限定理
我们提出了一种新的策略,该策略通过维护两个动态武器子集来解决离散时间无限视界平均奖励不安定强盗问题,其中一个子集具有近乎最优的状态分布并根据最优局部控制例程采取行动;另一个子集被驱向最优状态分布并逐渐合并到第一个子集中。我们证明了我们的策略在满足周期性 - 单链、非退化性和局部稳定性等温和假设的情况下在 N 臂问题中是渐进最优的,并且具有 O (exp (-C N)) 的最优性差距。我们的策略是首个在上述易于验证的假设集下实现指数渐近最优性的方法,而先前的工作要么需要强全局吸引子假设,要么仅实现了 O (1/sqrt (N)) 的最优性差距。我们进一步讨论了在显著减弱假设的基础上面临的基本障碍。特别地,我们通过证明一个下界,证明了局部稳定性对于指数渐近最优性是必要的。
May, 2024
本研究提出了一种基于模拟的框架,可以将单臂策略转换成适用于 N 臂问题的策略,并提供了在离散和连续时间框架下的计算上最优结果,且不需要 UGAP 假设。
May, 2023
本文研究了多类不定期赌徒的渐近最优控制问题,并提出了一类优先级策略,证明了在全局吸引子属性和技术条件下其是渐近最优的。我们将流体缩放技术与线性规划结果相结合,证明了当赌徒可索引时,Whittle 的索引策略包含在我们的一类优先级策略中。我们总结提出一些结论,包括关于如何选择来自渐近最优策略类的优先级策略等方面。
Sep, 2016
我们研究了离散时间无限远平均回报的不安静赌博机问题,提出了一种新的策略类别,旨在将逐渐增大的一部分臂带向最优分布。我们证明了在 N 臂问题中,如果单臂松弛问题是单连通和非周期的,我们的策略是渐近最优的,具有 O (1/√N) 的最优性差距。与目前大多数关注索引或优先级策略,依靠统一全球吸引子属性(UGAP)以保证收敛到最优解的已有工作,或者最近开发的基于模拟的策略不同,我们的方法不需要同步假设(SA)。
Feb, 2024
通过拉格朗日松弛和 Whittle 指数策略,本研究针对有限状态的多臂赌博机问题提出了一种解决方案,并使用值迭代算法验证了单臂赌博机的可指数性,讨论了在线掷骰策略和算法的计算复杂性,并通过数值实验证明,指数策略和掷骰策略优于短视策略。
Apr, 2023
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
本文提出了两种渐近最优的算法,基于 Track-and-Stop 方法和博弈论方法,用于寻找多臂赌博机环境中具有一定置信度的最优策略,特别考虑了带有线性约束的情况,并探讨了约束难度对问题的影响。
Jun, 2023
本论文探讨了不安定多臂赌博机的规划问题,提出了一种基于均场方法的规划算法来获得近似最优策略。通过实验分析,该算法在实际应用中表现优异且无需外部超参数。
Oct, 2022