非参数上下文臂的最重要变化跟踪
本研究开发了多种高效的上下文推断算法,为非平稳环境提供了有效的解决方案,具有动态适应分布变化的能力,同时通过对各种标准回归进行分析,证明了在时间和空间成本上都能达到最优的效果。
Aug, 2017
基于批处理约束条件的非参数上下文强化学习中,我们提出了批处理连续性排除和动态分箱 (BaSEDB) 算法,实现了最优的后悔值,通过动态地将协变量空间分割成较小的箱子,并将其宽度与批量大小相匹配,强调了静态分箱的次优性以及在完全在线设置中需要几乎恒定次数的策略更新来实现最优的后悔值。
Feb, 2024
探讨 K-armed bandit 问题下的 noisy reward,提出了一种简单实用的算法(kNN-UCB),并得到了紧密的 top-arm identification 和 sublinear regret 边界,并讨论了该算法的全局 intrisinic dimension 和 ambient dimension 的 regret 边界,同时介绍了对于无限武装情境下 bandit 算法的扩展和实验证明了算法在多种任务上的优越性。
Jan, 2018
我们研究了上下文连续性强化学习问题,证明了任何达到次线性静态遗憾的算法都可以扩展到达到次线性动态遗憾,我们提出了一种算法,通过自协调屏障和内点法实现了次线性动态遗憾,并且得出两个关键事实:首先,对于上下文不连续的函数,没有算法可以达到次线性动态遗憾;其次,对于强凸和光滑函数,我们提出的算法达到了最小极大动态遗憾速率的最优值,仅相差对数因子。
Jun, 2024
针对具有连续臂的随机赌博问题,研究解决策略应适应不同环境的问题,针对全局 Lipschitz 平均回报函数的特殊情况,展示在不提前知道 $L$ 或 $T$ 的情况下,最小化后悔损失达到最优阶的能力。
May, 2011
本文研究应用于在线决策中的两臂赌博机问题,其中臂的平均奖励是绝对阶数小于等于 β 的 Hölder 函数。我们展示了该问题平滑和非平滑情况的首个分离,提出了一种策略以 T^(3/5)遗憾为代价。同时,我们为任何整数 β≥1 证明了一个 T^(β+1)/2β+1 的下限,与 β=2 的上限相匹配。
Jan, 2023
研究了多臂赌博机和专家问题在非稳态随机环境下的动态遗憾。通过引入度量整个损失分布在 T 轮过程中的统计方差的新参数 Lambda,研究了这一数量对遗憾的影响。我们考察了 Lambda 与 Gamma(计算分布更改的次数)以及 Lambda 和 V(衡量随时间分布偏离的程度)之间的相互作用。研究发现即使将 Gamma、V 和 Lambda 都限制为常数时,在赌博设置中的遗憾下限仍会随着 T 的增加而增长。另一个重点是在全信息设置中,当 Gamma 和 Lambda 是常数时,可实现恒定的遗憾。同时,在 Lambda 为常数,而 V 为常数时,遗憾仍具有 T^(1/3)的依赖性。我们不仅提出了具有上界保证的算法,而且也证明了它们匹配的下界。
Dec, 2017