Apr, 2023

零和游戏的对数遗憾量子学习算法

PDF
TL;DR我们提出了首个在线量子算法，用于零和游戏，可以在 $\tilde O (1)$ 的时间内计算 $m \times n$ 矩阵零和游戏的 $\varepsilon$- 近似纳什均衡，与 $m$，$n$ 的经典算法相比，取得了二次的改进，同时实现了一个快速的量子线性规划求解器。
发现论文，激发创造
  • 零和游戏的量子算法

    提出量子计算的次线性时间的算法，基于 LP 问题和量子 SDP 求解器，用有效的 Gibbs 采样方法计算二人零和游戏的 Nash 均衡点。

    Apr, 2019

  • 量子零和游戏中寻找纳什均衡的二次加速

    通过引入一种新的算法层次结构中的 Optimistic Matrix Multiplicative Weights Update (OMMWU) 算法，本研究在计算量子零和博弈中的 ε-Nash 均衡方面取得了二次速度提升，并为量子游戏理论中的主要议题提供了新的基准。

    Nov, 2023

  • 具有对数最坏情况遗憾的量子强化学习的可证明高效探索

    我们提出了一种新的量子强化学习算法，并证明了对于 tabular MDPs and linear mixture MDPs，该算法的最坏情况后悔度是多项式级别的，是量子 RL 在线探索具有可证明的对数最坏情况后悔度的第一项研究。

    Feb, 2023

  • 改进样本复杂度的学习零和线性二次博弈

    我们提出了一种简化的嵌套零阶算法，通过改进样本复杂度几个数量级，并使用单点零阶估计器，在相同假设下确保了 Γ(E^3) 样本复杂度。

    Sep, 2023

  • 使用后验抽样学习零和随机博弈

    本文提出了后验采样强化学习算法，用于处理无限期零和随机博弈问题，在对手可以采取任意自适应策略的情况下，实现贝叶斯遗憾度的上界，并以平均奖励作为参数进行优化。该算法突破了当前数据的下限，并提高了效率。

    Sep, 2021

  • 在线学习众多量子对象

    通过应用正则化跟随领导算法，在学习正半定矩阵的通用子集和其他量子物体时，证明了一个次线性的遗憾界，并建立了在量子信息理论中有用的各种矩阵分析结果。

    Jun, 2024

  • 一般和式马尔可夫博弈的遗憾最小化和均衡收敛

    简而言之，本文提出了一种针对广义和博弈的、分散、计算高效的算法，其保证所有代理都使用时可以提供次线性遗憾保证，并且不需要代理之间的通信。该算法的主要观察结果是，通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。

    Jul, 2022

  • 具有平均回报目标的随机博弈中的分散式无模型强化学习

    本文介绍了一个针对零和博弈中基于无限目标平均报酬的分散式学习的无模型算法，称为 Decentralized Optimistic Nash Q-Learning (DONQ-learning)，该算法能够获得 $T^{3/4}$ 阶数的高概率次线性遗憾和 $T^{2/3}$ 阶数的次线性期望遗憾。与以往的相关工作相比，该算法具有低计算复杂度和低内存空间要求。

    Jan, 2023

  • 通过熵正则化的策略逼近学习零和随机博弈中的纳什均衡

    通过使用策略近似来减少学习零和随机博弈的纳什均衡的计算成本，我们提出了一种新的 Q-learning 类型算法，该算法使用一系列经过熵正则化的软策略来近似 Q 函数更新期间的纳什策略。我们证明， 在某些条件下，通过更新正则化的 Q 函数，该算法收敛于纳什平衡，并演示了该算法快速适应新环境的能力。提供一种动态超参数调度方案来进一步加快收敛速度。 应用于多个随机游戏的实证结果验证了所提出的算法收敛于纳什平衡，同时展现了比现有算法更快的加速效果。

    Sep, 2020

  • 乐观无悔动力加速

    本论文研究了如何利用在线学习动态算法来求解具有 Nash 均衡约束的凸凹博弈问题，通过引入乐观学习机制使得该方法求解速度得到了显著提升，同时还证明了在强凸平滑函数的情况下该方法的加速收敛性。

    Jul, 2018