Dynamic Regret of Quantized Distributed Online Bandit Optimization in Zero-Sum Games

Area of Science:

• Distributed Optimization
• Game Theory
• Multi-Agent Systems
• Network Science

Background:

• Investigates distributed online optimization in a zero-sum game context.
• Focuses on two distinct, time-varying multi-agent networks.
• Addresses challenges of inter-network communication and information gathering.

Purpose of the Study:

• To design and analyze an algorithm for distributed online optimization in a two-network zero-sum game.
• To guarantee the payoff for each network under complex communication constraints.
• To measure performance using dynamic Nash equilibrium regret.

Main Methods:

• Introduced the Quantized Distributed Online Bandit Optimization in Two-Network (QDOBO-TN) algorithm.
• Incorporated quantized communication and bandit feedback mechanisms.
• Agents transmit quantized information and use one-point estimators with partial cost function feedback.

Main Results:

• Developed QDOBO-TN and a multi-epoch variant to ensure network payoffs.
• Achieved sublinear regret bounds with respect to the iteration count T for both algorithms.
• Validated algorithm effectiveness through extensive simulation experiments.

Conclusions:

• The proposed QDOBO-TN algorithm effectively addresses distributed online optimization in complex two-network zero-sum games.
• The algorithm demonstrates strong performance with sublinear regret, suitable for time-varying and quantized environments.
• Simulation results confirm the practical applicability and efficiency of the developed methods.