无性能损失的批量顺序减半算法
简要摘要:本文研究小批量策略下随机赌博机问题的后悔,提出一种简单策略并证明合理情况下批量数量很小即可达到极小极大后悔度界限,同时推导得到低转换成本下的最优随机赌博机策略。
May, 2015
研究了多臂赌博机中的最佳臂辨识问题,提出了一个基于顺序淘汰算法的通用框架,并基于采样机制和每轮淘汰臂数量提出了性能评估指标,设计了一种按剩余臂数的非线性函数划分预算的算法,能够在纯探索场景下获得改进的理论保证和实验性能。
Sep, 2016
我们研究了线性环境中上下文臂中的顺序批处理学习问题,其中决策者被限制将个体分成(至多)固定数量的批处理,并且只能在批处理结束时观察批处理内的个体的结果。我们研究了问题的两种设置:一种是上下文是任意生成的,另一种是上下文是从某个分布中 iid 抽取的。在每个环境下,我们确定了遗憾下界,并提供了一个算法,其遗憾上界几乎与下界相匹配。
Apr, 2020
研究了多臂赌博问题中的探索和利用问题,并提出了一种基于非均匀采样策略的算法,用于解决带有分段稳定随机赌博问题的情况,并实现了对于超宽带通道选择的模拟测试。
May, 2012
研究表明,采用经验贝叶斯收缩方法对赌博学习中的奖励估计进行优化,并基于窗口累积输入估计平滑的奖励估计,以应对延迟反馈和非稳态奖励导致的不完全知识问题,并通过数量模拟验证了该提案的优越性,可以在速度和稳定性之间取得平衡,为人类 - 有回路的顺序优化提供便利。
Jun, 2021
本文提出一种基于启发式算法的无参数算法,用于解决特定的组合纯探索随机赌博机问题,以寻找一组平均值高于给定阈值的摇臂,满足给定精度和一定的时间限制,并证明该算法是情况下的最优解决方案,并提供了相应的上下界。本文是首个针对纯探索设置的固定预算问题,并构建了最优策略。
May, 2016
考虑到重复使用某些选项可能是不可取的或不可行的,本文提出了一种新颖的随机多臂赌博机设置,并通过映射到 PINWHEEL 调度问题证明了问题的优化累积奖励不允许有伪多项式时间算法,但它设计了一种贪婪算法和一种基于 UCB 的算法,具有一定的优异性。
Jul, 2019
本文研究了一类常见的序贯决策问题 —— 批处理问题,提出了一种结合神经网络和乐观性的算法 BatchNeuralUCB,用于解决探索利用平衡及限制批数量的问题,并在理论上证明了其有效性,在合成和真实数据集上进行了验证。
Feb, 2021