AAAIJul, 2020

预测性布莱克韦尔可达性加速游戏求解：联接遗憾匹配与镜像下降

PDF
TL;DR本文提出了预测 Blackwell 可达性算法的概念，基于在线凸优化的后悔最小化算法，得到了针对多次博弈问题的多种算法，并在 18 个经典的零和博弈模型上的实验中取得了优秀的效果。
blackwell approachabilitypredictive algorithmsregret minimizationonline convex optimizationcounterfactual regret minimization
发现论文，激发创造
  • 懊悔匹配 +: 博弈中的 (不) 稳定性和快速收敛

    研究 Regret Matching + 算法及其变体在解决大规模博弈中的应用，提出稳定化的解决方案，成功获取了在正态型博弈中的个体遗憾和社会遗憾的最优解，并在 clairvoyant 在线问题解决方面获得了理想结果。

    May, 2023

  • 黑韦尔可到达性与低遗憾学习是等效的

    本文证明了 Blackwell 可接近性定理在具有向量回报的两人博弈中的等效性，并且提出了计算校准预测的第一个有效算法。

    Nov, 2010

  • 使用乐观在线镜像下降法来减小加权对策后悔

    利用乐观的在线镜像下降算法最小化加权的对策后悔，从而加速收敛并解决博弈问题。

    Apr, 2024

  • 医生对口罩使用的结论：有用但需辩证看待

    本研究提出了一种广义的最好结果算法以及如何通过规范化导向跟随和在线镜像下降算法实现在线学习中的最好结果，将这种算法应用于上下文、图和表马尔科夫决策过程中。

    Feb, 2023

  • 可接近性、遗憾和校准；意义和等效性

    探讨三个标准（Blackwell 可达性，遗憾最小化和校准）如何在不同的顺序决策问题或玩家与自然之间的重复游戏中评估策略，并将其应用于展现一种新的直观算法类，基于简单的几何特性。

    Jan, 2013

  • 诚实面对：零和博弈最优非后悔框架

    本文提出了针对分散式场景中双方零和博弈问题的算法，提供了最佳的诚实遗憾和对抗遗憾率，解决了收敛到游戏价值的对数项的开放问题，并通过乐观的镜像下降算法与鲁棒的乐观镜像下降算法的信号传递方案相结合，实现了最佳结果。

    Feb, 2018

  • 黑韦尔可达性的速率保持减缩

    证明 Abernethy 等人的转化不能保持收敛速度，但可以将任何 approachability 实例紧密转化为 improper phi-regret minimization 实例，在 line 性转换的情况下可以保持收敛速度。

    Jun, 2024

  • 无尺度在线学习

    本文设计并分析了一种不需要任何上限或下限的在线线性优化算法，实现了适应损失向量范数的缩放不变性，并且通过 FTRL 和 MD 元算法实现了最优遗憾，并为无界决策集开发了一种非真空遗憾绑定的自适应算法，并对基于 MD 的无标度算法在无界域上的下限进行了研究。

    Jan, 2016

  • 未知序贯决策问题和游戏的无模型在线学习

    提出了一种适用于黑盒环境的极限情况的后悔最小化算法，通过以前保证仅实现的限制来实现亚线性的后悔率，并将其应用于逼近 Nash 均衡，学习最佳反应以及安全的对手利用等问题。

    Mar, 2021

  • 自适应（非）凸优化的模块化分析：乐观主义、复合目标和变分界限

    本文通过引入新的后悔分解和 Bregman 散度的泛化来对在线学习的两个算法进行分析，得出了较为简洁的结论，提出了对于复合目标的算法，并提供了一种细化的算法族。

    Sep, 2017