多阶段系统的分布式无悔学习与端到端强化学习反馈
该研究考虑了单人和多人多臂老虎机模型的学习问题,提出了两种可分散策略,即 E³ (立方) 和 E³-TS,它们显示出预期遗憾增长的上限为 O (log^(1+ε) T),并解决了分散的在线学习所产生的附加成本问题。
May, 2015
该论文介绍了一个用于在线组合优化和有限带反馈的联邦学习框架,该框架将任何具有复杂度为 O (psi/epsilon^beta)(其中省略了对数计算,psi 是一个函数,beta 是常数)的离线单代理(alpha-epsilon)逼近算法转化为具有 m 个通信代理和 alpha 遗憾度的在线多代理算法,并保证了与时间跨度 T 的次线性增长,且随着通信代理数量的增加而线性加速。此外,该算法还具有高效的通信特性,只需要亚线性数量的通信轮次,通过将该框架成功应用于在线随机子模块最大化,并实现了第一个单代理和多代理设置的结果,以及恢复了专门的单代理理论保证。我们还通过对随机数据摘要问题的实证验证来展示所提出的框架的有效性,即使在单代理场景中也是如此。
May, 2024
研究具有多个代理通过通信网络合作的新的非随机联邦多臂老虎机问题,其中危害的损失是由特指所有代理的每个时间步长和每个代理的每个手臂的损失的笨拙对手分配的。对于任何联邦老虎机算法,根据不同的设置提供遗憾下限,当代理有完整信息反馈或老虎机反馈时。在老虎机反馈设置下,提出一种接近最优的联邦老虎机算法 FEDEXP3,证明 FEDEXP3 可以保证不交换代理之间选择的手臂编号或损失序列的情况下得到次线性遗憾。还提供我们算法的数值评估以验证我们的理论结果,并证明其在合成和现实世界数据集上的有效性。
Jan, 2023
本文研究了协作在线学习的方法,特别关注于使用多臂老虎机游戏对社交网络中的一组代理进行协作的情况,并对其使用的不同算法进行了遗憾分析。我们发现,单个代理学习策略的自然扩展在网络设置下表现不佳,我们提出了一类策略,并证明其在网络环境中容易遭受大量遗憾。同时,我们也提出了基于网络结构的学习算法,并在拥有不同拓扑结构的网络上进行了实验。
Feb, 2016
本文提出一种在线学习算法 BanditQ,基于队列理论和在线学习相结合,实现公平在线预测,并在信息完整的情况下,达到目标约束,同时实现 $O (T^{3/4})$ 的损失率。
Apr, 2023
本文研究了具有未知转换和拥有无限制延迟反馈的分集式马尔可夫决策过程的在线学习,表现出基于策略优化的新算法,在完全信息反馈下实现了接近最优的高概率后悔情况,同时也是第一个考虑具有延迟反馈的 MDP 的后悔最小化设置。
Dec, 2020
通过建立离散选择模型与在线学习和多臂赌博算法领域之间的联系,本文的两个主要贡献是提供了一类算法的次线性遗憾界,包括 Exp3 算法作为特例,并引入了一类新的对抗多臂赌博算法,借鉴了 Wen (2001) 首次提出的广义嵌套逻辑模型,这些算法能够通过封闭形式的采样分布概率实现高度的模型调优灵活性。为了演示我们算法的实际实施,我们进行了数值实验,重点关注随机赌博的情况。
Oct, 2023
对于带有延迟反馈的对抗性多臂赌博问题,我们设计了一种改进的 EXP3 算法 MUD-EXP3 来处理多用户延迟反馈,同时提出了一种自适应算法 AMUD-EXP3,这两种算法在实验中被证明是正确且有效的,并给出了关于遗憾的理论分析。
Oct, 2023
本文考虑在延迟反馈下的敌对多臂老虎机问题,并分析了一些通过仅使用决策时可用的信息 (关于损失和延迟) 来调整步长的 Exp3 算法变体,从而获得适应观察到的 (而不是最坏情况下的) 延迟和 / 或损失序列的遗憾保证。最后,我们介绍了 AdaGrad 风格的版本的算法,该算法通过观察到的 (延迟的) 损失进行适应,而不仅仅是适应于累积延迟 (该算法要求先验上限)。
Oct, 2020