Learning in Congestion Games with Bandit Feedback
Learning in Congestion Games with Bandit Feedback
复制标题
DOI：
10.48550/arxiv.2206.01880
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Qiwen Cui;Zhihan Xiong;Maryam Fazel;S. Du
中科院分区：
文献类型：
--
作者：
Qiwen Cui;Zhihan Xiong;Maryam Fazel;S. Du
本文研究了拥塞对策中的纳什-后悔最小化问题，这类对策具有良好的理论结构和广泛的现实应用。对于具有(半)强盗反馈的拥塞对策，我们首先提出了一种基于不确定乐观原则的集中式算法，并得到了有限样本保证。然后，我们通过Frank-Wolfe方法和G-最优设计的一种新的组合，提出了一种分散算法。通过利用拥塞博弈的结构，我们证明了两种算法的样本复杂度只与玩家的数量和设施的数量成多项式相关，而不取决于动作集的大小，动作集的大小可以是设施的数量的指数大小。我们进一步定义了一个新的问题类--马尔可夫拥堵博弈，它允许我们对拥塞博弈中的非平稳性进行建模。我们提出了一种求解马尔可夫拥塞对策的集中式算法，其样本复杂度同样只依赖于所有相关问题的参数，而不依赖于动作集的大小。
In this paper, we investigate Nash-regret minimization in congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the optimism in the face of uncertainty principle for congestion games with (semi-)bandit feedback, and obtain finite-sample guarantees. Then we propose a decentralized algorithm via a novel combination of the Frank-Wolfe method and G-optimal design. By exploiting the structure of the congestion game, we show the sample complexity of both algorithms depends only polynomially on the number of players and the number of facilities, but not the size of the action set, which can be exponentially large in terms of the number of facilities. We further define a new problem class, Markov congestion games, which allows us to model the non-stationarity in congestion games. We propose a centralized algorithm for Markov congestion games, whose sample complexity again has only polynomial dependence on all relevant problem parameters, but not the size of the action set.