考虑带 Markov 奖励的经典多臂赌博机问题,玩一只手臂时,其状态会按 Markov 方式更改,不玩时保持冻结。玩一只手臂时,玩家会获得与状态相关的奖励,每只手臂的状态转移概率未知。我们证明在手臂的状态转移概率满足一定条件下,基于样本均值的指数策略能够在总试验次数上实现对数遗憾,同时也证明了在具有休息的 Markov 赌博机模型下,样本均值指数策略不会降低最优性。此外,对比 Anantharam 的指数策略和 UCB,我们发现通过选择一个小的探索参数 UCB 可以比 Anantharam 的指数策略拥有更小的遗憾。
Jul, 2010
我们研究了连续状态空间中的不安宁赌博机问题,采用线性高斯动态系统生成的动作向量和状态向量的内积作为奖励,通过一种方法对每个动作的奖励进行预测,该方法通过线性组合先前观察到的奖励来预测每个动作的未来奖励。我们展示了无论先前选择的动作序列如何,可以利用为任何先前选择的动作采样的奖励来预测另一个动作的未来奖励,即 $t-1$ 回合选择的动作 1 的奖励可以用于预测 $t$ 回合的动作 2 的奖励。为此,我们设计了一种修改的卡尔曼滤波器,并提供了在一组线性高斯动态系统上的数值评估。
May, 2024
本文介绍了一种多臂赌博机问题,其中奖励表现出制度切换,提出了一种在线学习算法,并对算法进行了性能检验和分析。
Jan, 2020
本文提出了一种适用于多臂赌博机问题的解决方案,只需要以线性时间复杂度存储未知参数,可以处理一般的掌握参数相关性的问题,并用于对网络中的最大权匹配、最短路径及最小生成树计算问题的解决。
Nov, 2010
本文提出一种考虑了副观测数据的随机赌博机模型,并基于上界置信度 (UCBs) 提供了高效的算法,用于在社交网络中推荐内容,实现了比传统算法更好的效果。
Oct, 2012
本文介绍了一种算法来解决不安分的马尔科夫赌臂问题,并证明了基于指数的策略在这个问题中一定是次优的。该算法可以在不需要假设马尔可夫链除了不可约的任何情况下,经过 T 步后实现相对于知道所有赌臂分布的最佳策略的 O (√T) 的悔恨。
Sep, 2012
此篇研究考虑了一个名为不安定多臂赌博机问题的模型,提出了一种探索和利用并行局部的策略,使得在一定的系统参数有限制时,能够获得对数级次的回报,而在缺乏关于系统的任何信息时,能够获得接近对数水平的回报。同时,也将问题扩展到了多个分布式参与者共享资源的情况,并得出相应结果。结果对于各种动态系统和通信网络以及金融投资的自适应学习都有应用。
本文研究了一种名为 “部分信息” 的在线学习模型,提出了多种算法,通过信息反馈结构的组合特性,给出了紧密的遗憾界限。
Sep, 2014
在顺序决策问题中,我们扩展上下文奖励设置并允许智能体观察功能状态的子集,以同时最大化长期平均收益并在有限时间内保证减少。
Jul, 2023
本文提出了一种解决 “潜在赌徒问题” 的算法,该问题是指机器学习智能体在未知离散潜在状态下知道手臂奖励分布,其主要目标是识别潜在状态。算法基于 UCBs 和 Thompson 采样,并在模型不确定性和规格不准确时具有上下文感知能力。理论分析表明,当潜在状态的数量小于行动数时,我们的算法优于传统的赌徒策略。综合实证研究表明了我们方法的优势。
Jun, 2020