通过建立离散选择模型与在线学习和多臂赌博算法领域之间的联系,本文的两个主要贡献是提供了一类算法的次线性遗憾界,包括 Exp3 算法作为特例,并引入了一类新的对抗多臂赌博算法,借鉴了 Wen (2001) 首次提出的广义嵌套逻辑模型,这些算法能够通过封闭形式的采样分布概率实现高度的模型调优灵活性。为了演示我们算法的实际实施,我们进行了数值实验,重点关注随机赌博的情况。
Oct, 2023
针对非平稳环境下的多臂赌博问题,提出了一种基于贝叶斯方法的 Thompson Sampling 变体,对其进行了系统性降低先前观测效果的描述,通过增加贝叶斯采样的功利值提供了最优化算法的乐观版本,并进行了广泛的实证分析和与各种算法的比较研究。
Jul, 2017
本文研究通过基于经验指数的成对比较和数据相关探索奖励的重新采样来计算理论上不完整的手臂分布的 Dirichlet Sampling 算法,表明这些策略的不同变体在手臂分布有界时实现了可证明的最优遗憾保证,并且在半边界分布具有轻微的分位条件时,实现了对数遗憾。此外,我们还表明,通过对一类广泛的无界分布具有鲁棒性的简单调整,代价是比对数想定糟糕一些的渐近遗憾。最后,我们通过合成农业数据上的决策问题展示了 DS 算法的优点。
Nov, 2021
本文主要研究的问题是:如何在样本预算有限的情况下,统一地估计多个分布的平均值。通过采集数量,可以根据它们的方差为已知来设计最优的采样策略,但在更实际的情况下,需要设计自适应采样策略来选择要采样的分布(根据先前观察到的样本)。文章描述了两种策略,根据样本数据以高概率上限置信界为比例,拉动分布并报告相对于最优配置的过度估计误差的有限样本性能分析。我们表明这些分配策略的性能不仅取决于方差还取决于分布的完整形状。
Jul, 2015
本文考察了当奖励分布具有 1+ε 阶矩时的多臂赌博问题,通过定义基于更精细的估计器的采样策略,如截断经验均值、Catoni 的 M - 估计和均值中位数估计器,证明了二阶矩(有限方差)足以获得与次高斯奖励分布同阶的悔恨界。
Sep, 2012
研究了多臂赌博问题中的探索和利用问题,并提出了一种基于非均匀采样策略的算法,用于解决带有分段稳定随机赌博问题的情况,并实现了对于超宽带通道选择的模拟测试。
May, 2012
研究了贝叶斯多臂赌博问题的多臂区间,证明了对于設計最优策略子采样至关重要,提出了一种新型的无偿探索方法,即对奖励分布的尾事件进行无偿探索,使用模拟数据和真实数据测试后发现贪婪算法表现更佳。
Feb, 2020
本文提出了一种新的算法 Discounted Thompson Sampling (DS-TS) with Gaussian priors,用于解决非平稳多臂赌博机问题,并分析了算法在不同情况下的表现和 upper bound of regret。
May, 2023
本文基于组合多臂赌博机,考虑了测试成本,提供了一种新的成本高效的在线决策框架,并通过后验抽样或 BayesUCB 进行探索。我们对该框架进行了严格的理论分析,并提供了多个实验结果,证明了它在实际问题中的适用性。
Aug, 2023
本文在经典赌博机问题的基础上提出了一个多智能体变种,旨在学会对赌臂进行公平分配并利用纳什社会福利来衡量它的公平性,设计了三个多智能体变种的算法并证明其实现了次线性的损失纳什社会福利, 因此可以对合理的互惠性展现出更大的感受。
Jul, 2020