Global and Local Convergence Analysis of a Bandit Learning Algorithm in Merely Coherent Games
Global and Local Convergence Analysis of a Bandit Learning Algorithm in Merely Coherent Games
复制标题
DOI：
10.1109/ojcsys.2023.3316071
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yuanhanqing Huang;Jianghai Hu
中科院分区：
文献类型：
--
作者：
Yuanhanqing Huang;Jianghai Hu
非合作博弈作为捕获自利玩家之间互动的强大框架，在建模广泛的实际场景中具有广泛的适用性，从电源管理到自动驾驶车辆的路径规划。尽管大多数现有的解决算法都假设一阶信息的可用性或目标和其他人行动概况的全部知识，但在某些情况下，玩家所能获得的唯一信息是实现的目标函数值。在本文中，我们设计了一种集成了乐观镜像下降方案和多点伪梯度估计的强盗在线学习算法。我们进一步证明，如果所研究的博弈是全局连贯的，则生成的实际游戏序列会收敛到一个临界点，而无需诉诸额外的Tikhonov正则化项或额外的范数条件。我们还讨论了所提出的强盗学习算法在局部仅相干博弈中的收敛性。最后，我们通过两个二人极大极小问题和一个认知无线电带宽分配博弈来说明该算法的有效性。
Non-cooperative games serve as a powerful framework for capturing the interactions among self-interested players and have broad applicability in modeling a wide range of practical scenarios, ranging from power management to path planning of self-driving vehicles. Although most existing solution algorithms assume the availability of first-order information or full knowledge of the objectives and others' action profiles, there are situations where the only accessible information at players' disposal is the realized objective function values. In this article, we devise a bandit online learning algorithm that integrates the optimistic mirror descent scheme and multi-point pseudo-gradient estimates. We further prove that the generated actual sequence of play converges a.s. to a critical point if the game under study is globally merely coherent, without resorting to extra Tikhonov regularization terms or additional norm conditions. We also discuss the convergence properties of the proposed bandit learning algorithm in locally merely coherent games. Finally, we illustrate the validity of the proposed algorithm via two two-player minimax problems and a cognitive radio bandwidth allocation game.