通过鞍点优化实现遗憾最小化
本文提出 Decision-Estimation Coefficient (DEC) 作为强化学习 (Reinforcement Learning, RL) 中无后悔 RL 的必要和充分的复杂度度量,并提出 Explorative DEC (EDEC) 和 Reward-Free DEC (RFDEC) 作为对 DEC 的扩展,设计了针对三个学习目标的新的统一的样本有效算法。
Sep, 2022
提供决策 - 评估系数,作为评估交互式学习复杂度的量,从而实现与样本效率无关的最佳后悔,同时引入了一种新的选择 Estimation-to-Decisions(E2D),使得监督学习的算法适应于在线决策,从而实现了准确的与样本效率无关的学习,在强化学习中,该决策 - 评估系数可以快速恢复现有的大多数困难结果和下限。
Dec, 2021
通过 von Neumann 最小极大定理,我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了,在这种对抗性环境中,最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关:它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释,因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式,我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界,而提供了对抗者的明确最优策略的下界。
Mar, 2009
本文提出了一个多项式时间的遗憾最小化框架,以在所有统计效率计算标准上,用只有 O (p/ε^2) 个设计点实现(1+ε)近似,并与传统算法作比较,本算法实现了 D/E/G 效率最优可行化的(1+ε)近似。
Nov, 2017
本文提出了一种称为 “laminar regret decomposition” 的新框架,该框架扩展了 CFR 算法,并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型,例如:序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明,该框架所开发的算法与 counterfactual regret minimization 相比,在计算纳什均衡时具有可比性,并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外,我们还展示了一种新类型的可伸缩对手利用方法。
Sep, 2018
本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔,探讨了决策者在不同反馈条件下的最优反悔幅度,并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案,获得了半强盗情形的最优界限,同时也证明了在线组合优化基准算法的次优性。
Apr, 2012
简而言之,本文提出了一种针对广义和博弈的、分散、计算高效的算法,其保证所有代理都使用时可以提供次线性遗憾保证,并且不需要代理之间的通信。该算法的主要观察结果是,通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。
Jul, 2022
在在线学习中,优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下,对二阶平滑和强凸函数进行优化的问题;通过提出匹配的上下界,第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法,结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画,从而使算法能够在偏差 - 方差权衡方面达到最优平衡,以及一种用于启动阶段的新的迭代方法,它能够保持无界 Hessian 的性能。
Jun, 2024
本文探讨了与正则化的经验风险线性预测器极小化相伴的一般凸优化问题,并将其重构为凸凹鞍点问题。我们提出了随机原始对偶坐标(SPDC)方法,该方法在随机选择的对偶变量上进行最大化和在原始变量上进行最小化之间交替运算,并通过原始变量的外推步骤以提高收敛速度。我们还开发了 SPDC 方法的小批量版本,以便实现并行计算,并在对偶变量的加权采样概率上进行了扩展,使其比非标准化数据上的均匀采样具有更好的复杂度,理论和经验表明 SPDC 方法与一些最先进的优化方法相比具有可比或更好的性能。
Sep, 2014