学习控制未知强单调博弈

Jun, 2024

Learning to Control Unknown Strongly Monotone Games

Siddharth Chandak, Ilai Bistritz, Nicholas Bambos

TL;DR我们提出了一种简单的算法，通过在线调整受控系数来学习将博弈的纳什均衡点转移到符合线性约束，而不需要知道奖励函数或行动集，从而提供具有概率 1 保证的收敛性以满足目标线性约束的纳什均衡集合，并为该算法提供了均方收敛速度为 O (t^{-1/4}) 的界限。我们演示了该算法在全局二次代价优化和资源分配博弈中实现负载平衡的应用场景的模拟结果。

Abstract

Consider $N$ players each with a $d$-dimensional action set. Each of the players' utility functions includes their reward function and a linear term for each dimension, with coefficients that are controlled by the manager. We assume that the game is strongly monotone, so if each player runs gradient descent, the dynamics converge to a unique →

nash equilibrium linear constraints stochastic approximation privacy-preserving global performance

发现论文，激发创造

连续对局中的最小信息学习

通过引入一种随机学习过程 - 阻尼梯度逼近，我们在本文中为具有连续行动集的博弈设计了一种学习过程，它是基于收益的，因此不需要玩家有策略上的认知或关于游戏的知识，我们还证明了在大部分博弈中玩家可以收敛于 Nash 均衡点。

Jun, 2018

通用和随机博弈纳什均衡学习的去中心化策略梯度

研究了一种具有未知转移概率密度函数的一般和随机游戏的纳什平衡学习。介绍一种加权渐近纳什均衡的概念，并提出了两种算法，一种是针对精确伪梯度的，另一种是针对未知伪梯度的。

Oct, 2022

未知独立链 $n$- 人随机博弈中纳什均衡策略的可扩展与独立学习

在一种类别的随机博弈中，利用自治的镜面下降算法通过占用测量和置信区间技术提出了一种学习算法，以构建稳定的 ε-NE 策略集合，并证明了其多项式时间收敛性。

Dec, 2023

动态定价中 n 人马尔可夫博弈的近似纳什均衡学习

本文研究了具有竞争性的马尔可夫游戏中的 Nash 均衡学习，使用了一种新的无模型方法找到近似 Nash 均衡，其中策略 - ε 对应性和状态至 ε- 最小策略是用神经网络表示的。在动态价格领域，可以学习到近似的 Nash 均衡。

Jul, 2022

乐观无悔动力加速

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

Jul, 2018

多人随机博弈中的学习

本文研究多人随机博弈中同时学习的问题，通过生成算法获得相关均衡，包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium，并提供了一些能够多项式时间内解决的特殊情况。

Oct, 2022

策略优化在零和线性二次博弈中可以证明收敛到纳什均衡

研究线性二次游戏中政策优化寻找纳什均衡的全局收敛性，开发了三种投影嵌套 - 梯度方法并给出了满意的收敛性证明和模拟结果，是对零和 Markov 博弈政策优化强化学习算法理论方面的探索。

May, 2019

在线堆叠伯格优化与非线性控制

适应性代理、在线控制、后悔最小化、对抗性干扰、表现性预测是该研究论文的主要关键词，该论文提出了一个统一的算法框架，用于在预测和优化可能的代理响应空间中实现可计算的后悔最小化，同时说明了在各种情况下的的紧界限制以及应用实例。

Jun, 2024

序列零和线性二次动态博弈的策略梯度全局收敛

该研究提出了基于策略梯度的无投影序列算法来处理线性二次动力博弈问题，并证明了如果采用自然梯度下降 / 上升，该算法具有对纳什均衡的全局次线性收敛性；此外，如果领导者采用拟牛顿策略，该算法将具有全局二次收敛性。

Nov, 2019

在线线性二次控制

我们研究了控制具有已知嘈杂动力学和对抗选择二次损失的线性时不变系统的问题，并提出了第一种在这种情况下保证 O（sqrt（T））遗憾的有效在线学习算法。我们的算法依赖于对系统稳态分布的新型 SDP 松弛。与以前提出的松弛相反，我们的 SDP 的可行解都对应于 “强稳定” 策略，这些策略混合到稳定状态的速度呈指数增长。

Jun, 2018