Distributed online bandit tracking for Nash equilibrium under partial-decision information setting  

作　　者：FENG ZhangCheng XU WenYing CAO JinDe YANG ShaoFu RUTKOWSKI Leszek 

机构地区：[1]Jiangsu Provincial Key Laboratory of Networked Collective Intelligence,School of Mathematics,Southeast University,Nanjing 211189,China [2]Frontiers Science Center for Mobile Information Communication and Security,Nanjing 210096,China [3]School of Computer Science and Engineering,Southeast University,Nanjing 211189,China [4]The Systems Research Institute of the Polish Academy of Sciences,Warsaw 01-447,Poland [5]AGH University of Science and Technology,Krakow 30-059,Poland

出　　处：《Science China(Technological Sciences)》2023年第11期3129-3138,共10页中国科学（技术科学英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.62173087,62176056,and 61833005);the Fundamental Research Funds for the Central Universities;in part by the Alexander von Humboldt Foundation of Germany;supported by Zhi Shan Youth Scholar Program from Southeast University;by Young Elite Scientists Sponsorship Program by CAST(Grant No.2021QNRC001)。

摘　　要：This paper is concerned with a Nash equilibrium(NE)tracking issue in online games with bandit feedback,where cost functions vary with time and agents only have access to the values of these functions at two points during each round.A partial-decision information setting is considered,in which agents have only access to the decisions of their neighbors.The primary objective of this paper is to develop a distributed online NE tracking algorithm that ensures sublinear growth of regret with respect to the total round T,under both the bandit feedback and partial-decision information setting.By utilizing a two-point estimator together with the leader-following consensus method,a new distributed online NE tracking algorithm is established with the estimated gradient and local estimated decisions based on the projection gradient-descent method.Moreover,sufficient conditions are derived to guarantee an improved upper bound of dynamic regret compared to existing bandit algorithms.Finally,a simulation example is presented to demonstrate the effectiveness of the proposed algorithm.

关 键 词：online game bandit feedback partial-decision two-point gradient estimator 

分 类 号：O225[理学—运筹学与控制论]