Mar, 2024

在范数空间中的随机 Halpern 迭代及其在强化学习中的应用

PDF
TL;DR我们分析了具有方差减小的随机 Halpern 迭代的 Oracle 复杂度，目标是在规范有限维度空间中逼近非扩张和收缩算子的不动点。我们证明，如果底层随机 Oracle 的方差有一致上界，我们的方法展现出 O (ε^{-5}) 的总 Oracle 复杂度，改进了针对随机 Krasnoselskii-Mann 迭代的最新速率。同样，我们建立了一个 Ω(ε^{-3}) 的下界，适用于广泛范围的算法，包括所有的平均迭代，甚至采用小批量训练。利用我们方法的适当修改，我们推导出在算子为 γ 收缩的情况下的 O (ε^{-2}(1-γ)^{-3}) 复杂度上界。作为应用，我们提出了用于平均奖励和折扣奖励马尔可夫决策过程的新的同步算法。特别地，对于平均奖励问题，我们的方法改进了已知的最佳样本复杂度。
oracle complexitystochastic halpern iterationvariance reductionnonexpansive operatorscontractive operators
发现论文，激发创造
  • 有限和单调包含的方差减少哈尔彭迭代

    应用机器学习方法解决针对敌对鲁棒性或多主体环境产生的博弈均衡问题，提出了基于有限和结构的方法。使用方差缩减技术改进了经典的 Halpern 迭代，通过在求和中的组分算子上引入可比较的 cocoercive 或 Lipschitz 连续单调性，取得了性能改进。所提出的方法具有可验证的退出准则，并且在最后迭代次数和（可计算的）操作符范数残差方面提供了保证。其 oracle 复杂性为 $𝜃(𝑛+√𝑛𝐿𝜖^{-1})$，相较于现有方法提升了多达√𝑛倍，将方差缩减引入到通用有限和单调包含问题和具体问题中，如算子范数残差是最优性度量的凸 - 凹优化，创造了一项新的成果。进一步论证表明，在单调 Lipschitz 设置中，除去多项式对数因子，这种复杂性是无法被改进的，即提供的结果几乎是最优的。

    Oct, 2023

  • 方差降低的保守策略迭代

    本文研究了将强化学习转化为一系列关于策略空间的经验风险最小化问题的样本复杂度问题。本文提出的共产主义政策迭代的方差递减变种可以将从 O（ε^-4）到 O（ε^-3）的功能局部最优解的样本复杂度改进。在状态覆盖和政策完整性的假设下，该算法在采样 O（ε^-2）次后享有 ε- 全局最优性，这改善了以前已经建立的 O（ε^-3）样本要求。

    Dec, 2022

  • 具有方差缩减的随机变分不等式外推法

    我们提出了一种超梯度方法，它具有远离零的步长，适用于仅需要伪单调性的随机变分不等式。我们提供了收敛性和复杂性分析，其可允许无界可行集，无界算子，或不均匀的预测方差，并且不需要任何规则化。

    Mar, 2017

  • 不精确的 Halpern 迭代在分布鲁棒优化中的应用

    通过选择适当的不精确度容限，我们的结果放宽了文献中采用的不精确条件，同时具有相同的竞争性收敛性能，从而研究了解决单调包含问题的 Halpern 迭代的不精确变体，并进行广泛的收敛性分析。我们还演示了如何将该方法应用于两类数据驱动的 Wasserstein 分布鲁棒优化问题的求解，这些问题可以转换为凸凹极小极大优化问题。我们强调了该方法在具有随机一阶方法的分布鲁棒学习中执行不精确计算的能力。

    Feb, 2024

  • 非扩张映射 Halpern 迭代的渐近正则性率

    本文利用数学逻辑学的证明论技巧获得了关于非扩张映射 Halpern 迭代的新的有效结果，给出了在赋范空间中非空凸集的非扩张自映射的 Halpern 迭代的渐近正则性的有效速率，这是证明挖掘项目中的又一个案例研究，该项目涉及从（表面上）无效的证明中提取有效一致边界。

    Oct, 2007

  • 近最优无参数单调包含和变分不等式有限强解的哈尔普恩迭代

    基于 Halpern 迭代的潜能函数收敛证明，我们利用非扩张映射、单调 Lipschitz 算子和近端映射之间的联系，得到了解决单调包含问题的近乎最优无参方法，同时转化为解决变分不等式问题、拟凸 - 凹极小极大优化问题的近乎最优保证，并在分析中提供了一系列的算法降低证明复杂度。

    Feb, 2020

  • 通用效用的强化学习：更简单的方差缩减和大状态行动空间

    我们提出了一种更简单的单循环，无参数归一化策略梯度算法，用于解决具有一般效用的强化学习问题，其中包括约束强化学习，纯探索以及从演示中学习等问题，同时通过线性函数逼近解决大状态 - 动作空间的设置，并展示了简单的策略梯度法的样本复杂度。

    Jun, 2023

  • 截断方差减小的值迭代

    我们提供了一种更快的随机算法，用于在具有有限状态动作对、有界奖励和折扣因子的折扣马尔可夫决策过程中计算 ε- 最优策略。我们通过在采样设置和离线设置中提供不同的时间算法，进一步优化了之前的最先进技术。我们的方法基于先前的随机方差减少值迭代方法，通过引入新的方差减少采样过程并优化其迭代进展，能够在没有模型的情况下实现，并在模型自由和基于模型方法之间填补了样本复杂性差距。

    May, 2024

  • 随机方差减少的哈密顿蒙特卡洛方法

    本文提出了一种快速的随机 Hamilton Monte Carlo 方法，用于从一个光滑而强烈对数凹的分布中进行采样。通过梯度复杂度来衡量算法的性能，实验结果表明，该算法在采样效率上跑赢了现有的 HMC 和 Stochastic Gradient HMC 方法。

    Feb, 2018

  • 无限时间平均回报马尔可夫决策过程的方差减少政策梯度方法

    基于政策梯度的两种方法在无限时间平均奖励马尔可夫决策过程中引入了一般参数化。第一种方法采用隐式梯度传输进行方差降低，确保了预期后悔度为 $\tilde {\mathcal {O}}(T^{3/5})$ 数量级。第二种方法以 Hessian-based 技术为基础，确保了预期后悔度为 $\tilde {\mathcal {O}}(\sqrt {T})$ 数量级。这些结果显著提高了该问题的最新研究成果，其后悔度达到了 $\tilde {\mathcal {O}}(T^{3/4})$ 数量级。

    Apr, 2024