本文提出了两种学习算法:Combinatorial Linear Thompson Sampling (CombLinTS) 和 Combinatorial Linear UCB (CombLinUCB) 来解决大规模组合半强盗问题,并证明它们是计算和统计上高效的。
Jun, 2014
本文研究了在线组合优化问题中的半盲反馈,提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率,在部分反馈方案中首次实现了此类保证,并在组合设置中首次实现了此类保证。
Feb, 2015
提出了组合级联赌博算法,对分布随机的约束问题解决一类非线性奖励函数部分可观测性问题,提供了一种基于 UCB 算法的求解方法,并论证了与时间复杂度无关的期望损失界限和时间关联的损失上限。在两个真实世界的网络路径问题测试中,算法表现良好,说明该算法对于模型假设违反的情况同样稳健有效,这个设置还需要提出新的学习算法。
Jul, 2015
提出了 probably anytime-safe stochastic combinatorial semi-bandits 问题及其改善风险的算法 PASCombUCB,可应用于推荐系统和交通运输领域等代理人在单个时间步内选择多个项目并希望在整个时间范围内控制风险的情境。
Jan, 2023
本文研究了随机和对抗性组合多臂赌博问题。在随机情况下,我们提出了一种特定问题的遗憾下限,并讨论了其与决策空间维数的比例关系。我们提出了 ESCB 算法,该算法能有效地利用问题的结构,并对其遗憾进行了有限时间分析。ESCB 具有比现有算法更好的性能保证,并在实践中显着优于这些算法。在对抗性情况下,我们提出了 CombEXP 算法,其遗憾比比现有最先进算法相同,但对于某些组合问题具有较低的计算复杂度。
本研究探讨组合良带 (Bandits) 的算法,针对其大小批次 (K) 对后悔束缚的依赖性进行优化,发现一种可替代平滑性条件的新型触发概率和方差调节 (TPVM) 条件,进行后悔分析并提出基于置信区间和方差的 BCUCB-T 算法,将大小批次 (K) 的项降低至对数级别,并在非触发 CMAB 中将其完全去除。实验结果表明,我们的算法在不同领域具有优越的性能。
Aug, 2022
开发出新的半强化学习算法,不需要先验信息,可同时在随机环境和对抗环境下获得对数级和平方级的遗憾,并通过在合成数据上的实验证明了其性能的一致性和优越性。
Jan, 2019
本研究探讨了组合多臂赌博的后悔下界,并证明了在所有光滑奖励函数下,这种下界都是合理的,并且根据 Merlis 和 Mannor(2019)提出的 Gini 加权平滑度参数确定单调奖励函数的下界。
Feb, 2020
提出了一种基于 UCB 并具有适当的置信参数平衡风险和过度乐观代价的随机有限臂老虎机算法,同时具有最优问题依赖性遗憾和最坏情况遗憾。
本研究探讨具有因果关系奖励的分段稳定组合半强盗问题,在我们的非稳态环境中,基本臂的分布变化,奖励之间的因果关系,或者二者同时改变了奖励生成过程。我们提出的算法在复杂环境中具备优越的应用性能。
Jul, 2023