组合半匪难度分析及Thompson抽样策略与贪心算法的应用
使用贝叶斯方法的随机算法Thompson Sampling在多臂赌博问题中表现显著,本文提供了一种新的悔恨分析方法,同时证明了该算法在期望后悔上的问题特定界限和问题独立界限,方法简单且可适用于更广泛的contestual bandits设置。
Sep, 2012
本文研究了一种序贯子集选择问题,并提出了一种基于 Thompson Sampling 算法的适用于多项式逻辑模型选择模型的求解方法,能够在绝大多数情况下获得接近最优水平的收益,并在数字实验中取得有趣的实验结果。
Jun, 2017
本文研究了随机多臂老虎机的组合纯探索问题,提出了一种新的样本复杂度的下界和一种新的抽样算法,并用于凸优化的分离与优化等价和近似 Pareto 曲线等技术改进了多个普遍应用的组合约束条件的纯探索问题的已有方法。此外,我们还提出了更通用的问题,并针对其提供了样本复杂度的上下界。
Jun, 2017
研究了在半盲反馈条件下,组合多臂赌博问题中,具有概率触发武器的组合汤普森抽样的遗憾,并在基准武器预期的连续Lipschitz情况下得出了CTS的遗憾界。
Sep, 2018
本研究通过引入Hadamard矩阵,提出了一种通用的CSAR算法用于解决top-k组合赌博问题,针对完全赌博反馈,该算法仅观察奖励总和,在两个变体的算法中,第一个最小化样本复杂性,第二个最小化遗憾,并证明了样本复杂度的下限,该复杂度对于$k=O(1)$来说是紧的。最后,通过实验证明该算法优于其他方法。
May, 2019
本文研究了采用半智能反馈的随机组合多臂赌博机问题。研究中提出了解决对于两种不同分布情况下是否存在效率最优、渐进遗憾最小算法的问题。通过分别采用Beta先验和高斯先验对 Combinatorial Thompson Sampling 策略进行了分析,进而找到了这两种分布情况下的算法解决方案,从而得出计算效率上优于 Efficient Sampling for Combinatorial Bandit 策略的结论。
Jun, 2020
本文研究一种多臂赌博机问题,其中每个臂的质量是在奖励分布的某个水平alpha上通过条件风险价值(CVaR)来测量。我们引入了一种新的CVaR赌博机定理的Thompson Sampling方法,尤其适用于基于物理资源的问题。我们在理论上提供了它们CVaR损失的最小化性能的可行性分析,实验结果表明这些策略是第一个在CVaR赌博机中实现渐近最优性的,并匹配了此设置的相应渐近下限。
Dec, 2020