Stochastic learning in multi-agent optimization: communication and payoff-based approaches

DOI10.1016/J.AUTOMATICA.2018.10.001zbMATH Open1406.93389arXiv1804.04403OpenAlexW2899423435MaRDI QIDQ1716626FDOQ1716626

Authors: Tatiana Tatarenko 

Publication date: 5 February 2019

Published in: Automatica (Search for Journal in Brave)

Abstract: Game theory serves as a powerful tool for distributed optimization in multi-agent systems in different applications. In this paper we consider multi-agent systems that can be modeled by means of potential games whose potential function coincides with a global objective function to be maximized. In this approach, the agents correspond to the strategic decision makers and the optimization problem is equivalent to the problem of learning a potential function maximizer in the designed game. The paper deals with two different information settings in the system. Firstly, we consider systems, where agents have the access to the gradient of their utility functions. However, they do not possess the full information about the joint actions. Thus, to be able to move along the gradient toward a local optimum, they need to exchange the information with their neighbors by means of communication. The second setting refers to a payoff-based approach to learning potential function maximizers. Here, we assume that at each iteration agents can only observe their own played actions and experienced payoffs. In both cases, the paper studies unconstrained non-convex optimization with a differentiable objective function. To develop the corresponding algorithms guaranteeing convergence to a local maximum of the potential function in the game, we utilize the idea of the well-known Robbins-Monro procedure based on the theory of stochastic approximation.

Full work available at URL: https://arxiv.org/abs/1804.04403

Recommendations

• Game-theoretic learning and distributed optimization in memoryless multi-agent system
• Achieving Pareto Optimality Through Distributed Learning
• Game-Theoretic Learning and Distributed Optimization in Memoryless Multi-Agent Systems
• On convergence rates of game theoretic reinforcement learning algorithms
• Distributed optimization with information-constrained population dynamics

zbMATH Keywords

game theorystochastic approximationnon-convex optimizationmulti-agent systemslearning algorithms

Mathematics Subject Classification ID

Noncooperative games (91A10) Agent technology and artificial intelligence (68T42) Stochastic games, stochastic differential games (91A15) Signaling and communication in game theory (91A28) Stochastic learning and adaptive control (93E35) Software, source code, etc. for problems pertaining to systems and control theory (93-04)

Cites Work

• Mathematical analysis II. Transl. from the 4th Russian edition by Roger Cooke
• A class of games possessing pure-strategy Nash equilibria
• Consensus and Cooperation in Networked Multi-Agent Systems
• Potential games
• Title not available (Why is that?)
• Distributed Subgradient Methods for Multi-Agent Optimization
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Lectures on stochastic programming. Modeling and theory.
• Stochastic Approximations and Differential Inclusions, Part II: Applications
• Nonconvergence to unstable points in urn models and stochastic approximations
• Network formation games and the potential function method
• Distributed Optimization Over Time-Varying Directed Graphs
• Distributed coverage games for energy-aware mobile sensor networks
• Performance of a Distributed Stochastic Approximation Algorithm
• Online learning of Nash equilibria in congestion games
• A new continuous action-set learning automaton for function optimization
• Convergent learning algorithms for unknown reward games
• Non-Convex Distributed Optimization

Cited In (4)

• Experiential and Stochastic Learning Algorithms Based on the Probability of a Fuzzy Event and Modified Fuzzy Metric Distance in Intelligent Robotic Part Micro-Assembly
• Game-Theoretic Learning and Distributed Optimization in Memoryless Multi-Agent Systems
• Affine Relaxations of the Best Response Algorithm: Global Convergence in Ratio-Bounded Games
• Game-theoretic learning and distributed optimization in memoryless multi-agent system

This page was built for publication: Stochastic learning in multi-agent optimization: communication and payoff-based approaches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1716626)