具有马尔可夫奖励的组合多臂赌博机问题
考虑带 Markov 奖励的经典多臂赌博机问题,玩一只手臂时,其状态会按 Markov 方式更改,不玩时保持冻结。玩一只手臂时,玩家会获得与状态相关的奖励,每只手臂的状态转移概率未知。我们证明在手臂的状态转移概率满足一定条件下,基于样本均值的指数策略能够在总试验次数上实现对数遗憾,同时也证明了在具有休息的 Markov 赌博机模型下,样本均值指数策略不会降低最优性。此外,对比 Anantharam 的指数策略和 UCB,我们发现通过选择一个小的探索参数 UCB 可以比 Anantharam 的指数策略拥有更小的遗憾。
Jul, 2010
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本研究探讨了组合多臂赌博的后悔下界,并证明了在所有光滑奖励函数下,这种下界都是合理的,并且根据 Merlis 和 Mannor(2019)提出的 Gini 加权平滑度参数确定单调奖励函数的下界。
Feb, 2020
此篇研究考虑了一个名为不安定多臂赌博机问题的模型,提出了一种探索和利用并行局部的策略,使得在一定的系统参数有限制时,能够获得对数级次的回报,而在缺乏关于系统的任何信息时,能够获得接近对数水平的回报。同时,也将问题扩展到了多个分布式参与者共享资源的情况,并得出相应结果。结果对于各种动态系统和通信网络以及金融投资的自适应学习都有应用。
Nov, 2010
提出了两种多用户多臂赌博机算法框架,分别适用于随机环境和对抗环境下无协调频谱访问问题。算法可在不知道用户数量的情况下,通过估计和分配两个阶段实现高概率下的常数系统累积失误和次线性系统累积失误,并能够处理用户数量随时间改变的动态问题。
Jul, 2018
研究了去中心化多智能体多臂赌博问题,使用随机图来优化整个系统的综合悔恨度,引入了新的算法框架,其中包含加权技巧和上置信边界方法,算法具有较好的鲁棒性,并且考虑了图随机性,同时给出了不同命题下的悔恨度的上限。
Jun, 2023
本文针对认知无线电网络中的多个次级用户争取多个信道的机会问题,提出去中心化多臂赌博问题,并设计出一种去中心化的在线学习策略,以达到尽可能降低总体期望回报与所有用户回归之间的差距。其中,分别考虑了优先级排序和公平访问策略。
Apr, 2011
该研究提出了一种适用于无贝叶斯假设的多臂老虎机问题求解方法,该方法可以在非贝叶斯假设且马尔可夫链参数未知时,通过元策略学习最优策略,并在未知动态信道的机会式频谱访问问题中取得了接近对数级的损失值,是该问题领域内的首个实现此类结果。
Nov, 2010