Mar, 2024

序列多臂赌博机中的奖励样本传输

PDF
TL;DR在该研究中，我们考虑了一个顺序随机多臂赌博问题，在多个回合中，代理与赌博机进行交互。臂的奖励分布在一个回合中保持不变，但在不同回合中可能发生变化。我们提出了一种基于 UCB 算法的方法，用于传输来自先前回合的奖励样本，并改善所有回合中的累积遗憾表现。我们对该算法进行了遗憾分析和实证结果，结果显示与无传输的标准 UCB 算法相比有明显的改进。
sequential stochastic multi-armed banditepisodesreward distributionucb algorithmcumulative regret performance
发现论文，激发创造
  • 有限模型的多臂赌博机中的连续转移

    本文着重研究在线学习中的顺序迁移问题，尤其是在多臂赌博机框架中，引入了一种基于矩阵方法的赌博算法，推导出了它的遗憾界。

    Jul, 2013

  • 去中心化协作随机赌博机

    本文研究了多臂赌博机问题在网络上的去中心化协作，采用加速一致性过程来计算所有智能体对每个臂的平均奖励，该算法采用上置信区间来决策，能够达到更好的回归界，同时不需要过多的底层网络信息。

    Oct, 2018

  • 具有马尔可夫回报的多臂赌博机问题的在线算法

    考虑带 Markov 奖励的经典多臂赌博机问题，玩一只手臂时，其状态会按 Markov 方式更改，不玩时保持冻结。玩一只手臂时，玩家会获得与状态相关的奖励，每只手臂的状态转移概率未知。我们证明在手臂的状态转移概率满足一定条件下，基于样本均值的指数策略能够在总试验次数上实现对数遗憾，同时也证明了在具有休息的 Markov 赌博机模型下，样本均值指数策略不会降低最优性。此外，对比 Anantharam 的指数策略和 UCB，我们发现通过选择一个小的探索参数 UCB 可以比 Anantharam 的指数策略拥有更小的遗憾。

    Jul, 2010

  • 奖励漂移下的多臂赌博机激励探索

    本文研究了多臂赌博机问题中的激励探索方法，分析了偏差反馈对于 UCB 算法、E - 贪心算法以及汤普森抽样算法表现的影响。结果表明这些算法在偏差反馈下产生了 $log (T)$ 的遗憾和补偿，在激励探索方面是有效的。

    Nov, 2019

  • 阻断赌徒

    考虑到重复使用某些选项可能是不可取的或不可行的，本文提出了一种新颖的随机多臂赌博机设置，并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法，但它设计了一种贪婪算法和一种基于 UCB 的算法，具有一定的优异性。

    Jul, 2019

  • 关于突发性和缓慢变化的多臂赌博问题

    LM-DSEE 与 SW-UCB# 两种算法解决了非稳态随机多臂赌博问题，在突变和缓慢变化的环境下，这些算法在时间上的预期总遗憾被控制在时间的子线性函数上。

    Feb, 2018

  • 区域多臂赌博机

    本文研究了一种多臂赌博机问题变体，其中每个机械臂的期望奖励是未知参数的函数，并且将机械臂分成不同的组，我们提出了一种有效的算法 UCB-g 来解决该问题，并证明该算法最优性，并针对非静态环境提出了扩展算法 SW-UCB-g。

    Feb, 2018

  • 具有相关臂的多臂赌博机

    针对多臂赌博机框架中奖励之间相互关联的情况，我们提出了一种统一的方法来优化这种关联并基于这种情况推广经典赌博算法，其中 C-UCB 是上置信边界算法的相关版本。我们证明了算法的正确性，并通过 MovieLens 和 Goodreads 数据集的实验验证了该算法与经典的赌博算法相比的显著改进。

    Nov, 2019

  • 优化置信区间上界算法：改进有限臂赌博机的遗憾

    提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法，同时具有最优问题依赖性遗憾和最坏情况遗憾。

    Jul, 2015

  • 非平稳赌博机问题的置信上限策略

    本文考虑了分布保持不变，但在未知时间发生改变的非稳态赌徒问题，研究了两种算法：折扣上限置信区间和滑动窗口上限置信区间，并通过 Hoeffding 不等式得到了后者的上界，对不优的赌博机被玩的次数期望进行了上界估计并证明了存在性突然性改变时的遗憾下界，证明了折扣上限置信区间和滑动窗口上限置信区间的匹配下界一致性。

    May, 2008