Search

The field of multi-agent reinforcement learning (MARL) has made considerable progress towards controlling challenging multi-agent systems by employing various learning methods. Numerous of these approaches focus on empirical and algorithmic aspects of the MARL problems and lack a rigorous theoretical foundation. Graphon mean field games (GMFGs) on the other hand provide a scalable and mathematically well-founded approach to learning problems that involve a large number of connected agents. In standard GMFGs, the connections between agents are undirected, unweighted and invariant over time. Our paper introduces colored digraphon mean field games (CDMFGs) which allow for weighted and directed links between agents that are also adaptive over time. Thus, CDMFGs are able to model more complex connections than standard GMFGs. Besides a rigorous theoretical analysis including both existence and convergence guarantees, we provide a learning scheme and illustrate our findings with an epidemics model and a model of the systemic risk in financial markets.

Inspired by the path coordination problem arising from robo-taxis, warehouse management, and mixed-vehicle routing problems, we model a group of heterogeneous players responding to stochastic demands as a congestion game under Markov decision process dynamics. Players share a common state-action space but have unique transition dynamics, and each player's unique cost is a {function} of the joint state-action probability distribution. For a class of player cost functions, we formulate the player-specific optimization problem, prove the equivalence between the Nash equilibrium and the solution of a potential minimization problem, and derive dynamic programming approaches to solve the Nash equilibrium. We apply this game to model multi-agent path coordination and introduce congestion-based cost functions that enable players to complete individual tasks while avoiding congestion with their opponents. Finally, we present a learning algorithm for finding the Nash equilibrium that has linear complexity in the number of players. We demonstrate our game model on a multi-robot warehouse \change{path coordination problem}, in which robots autonomously retrieve and deliver packages while avoiding congested paths., 6 pages, 4 figures

We consider linear-quadratic-Gaussian (LQG) network games in which agents have quadratic payoffs that depend on their individual and neighbors' actions, and an unknown payoff-relevant state. An information designer determines the fidelity of information revealed to the agents about the payoff state to maximize the social welfare. Prior results show that full information disclosure is optimal under certain assumptions on the payoffs, i.e., it is beneficial for the average individual. In this paper, we provide conditions based on the strength of the dependence of payoffs on neighbors' actions, i.e., competition, under which a rational agent is expected to benefit, i.e., receive higher payoffs, from full information disclosure. We find that all agents benefit from information disclosure for the star network structure when the game is symmetric and submodular or supermodular. We also identify that the central agent benefits more than a peripheral agent from full information disclosure unless the competition is strong and the number of peripheral agents is small enough. Despite the fact that all agents expect to benefit from information disclosure ex-ante, a central agent can be worse-off from information disclosure in many realizations of the payoff state under strong competition, indicating that a risk-averse central agent can prefer uninformative signals ex-ante., 6 pages, 4 figures

In this paper, we propose Push-SAGA, a decentralized stochastic first-order method for finite-sum minimization over a directed network of nodes. Push-SAGA combines node-level variance reduction to remove the uncertainty caused by stochastic gradients, network-level gradient tracking to address the distributed nature of the data, and push-sum consensus to tackle the challenge of directed communication links. We show that Push-SAGA achieves linear convergence to the exact solution for smooth and strongly convex problems and is thus the first linearly-convergent stochastic algorithm over arbitrary strongly connected directed graphs. We also characterize the regimes in which Push-SAGA achieves a linear speed-up compared to its centralized counterpart and achieves a network-independent convergence rate. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments on strongly convex and non-convex problems.

We introduce a new decentralized observation condition which we call "at least one can tell" (OCT) and which attempts to capture the idea that for any possible behavior that a system can generate, at least one decentralized observation agent can tell whether that behavior was "good" or "bad", for given formal specifications of "good" and "bad". We provide several equivalent formulations of the OCT condition, and we relate it to (and show that it is different from) previously introduced joint observability. In fact, contrary to joint observability which is undecidable, we show that the OCT condition is decidable. We also show that when the condition holds, finite-state decentralized observers exist.

In this letter, we consider the problem of privacy preservation in the static average consensus problem. This problem normally is solved by proposing privacy preservation augmentations for the popular first order Laplacian-based algorithm. These mechanisms however come with computational overhead, may need coordination among the agents to choose their parameters and also alter the transient response of the algorithm. In this letter, we show that an alternative iterative algorithm that is proposed in the literature in the context of dynamic average consensus problem has intrinsic privacy preservation and can be used as a privacy preserving algorithm that yields the same performance behavior as the well-known Laplacian consensus algorithm but without the overheads that come with the existing privacy preservation methods.

This paper proposes online algorithms for dynamic matching markets in power distribution systems, which at any real-time operation instance decides about matching -- or delaying the supply of -- flexible loads with available renewable generation with the objective of maximizing the social welfare of the exchange in the system. More specifically, two online matching algorithms are proposed for the following generation-load scenarios: (i) when the mean of renewable generation is greater than the mean of the flexible load, and (ii) when the condition (i) is reversed. With the intuition that the performance of such algorithms degrades with increasing randomness of the supply and demand, two properties are proposed for assessing the performance of the algorithms. First property is convergence to optimality (CO) as the underlying randomness of renewable generation and customer loads goes to zero. The second property is deviation from optimality, is measured as a function of the standard deviation of the underlying randomness of renewable generation and customer loads. The algorithm proposed for the first scenario is shown to satisfy CO and a deviation from optimal that varies linearly with the variation in the standard deviation. But the same algorithm is shown to not satisfy CO for the second scenario. We then show that the algorithm proposed for the second scenario satisfies CO and a deviation from optimal that varies linearly with the variation in standard deviation plus an offset.

We design a distributed algorithm for learning Nash equilibria over time-varying communication networks in a partial-decision information scenario, where each agent can access its own cost function and local feasible set, but can only observe the actions of some neighbors. Our algorithm is based on projected pseudo-gradient dynamics, augmented with consensual terms. Under strong monotonicity and Lipschitz continuity of the game mapping, we provide a very simple proof of linear convergence, based on a contractivity property of the iterates. Compared to similar solutions proposed in literature, we also allow for a time-varying communication and derive tighter bounds on the step sizes that ensure convergence. In fact, in our numerical simulations, our algorithm outperforms the existing gradient-based methods, when the step sizes are set to their theoretical upper bounds. Finally, to relax the assumptions on the network structure, we propose a different pseudo-gradient algorithm, which is guaranteed to converge on time-varying balanced directed graphs.

In future autonomous systems, wireless multi-hop communication is key to enable collaboration among distributed agents at low cost and high flexibility. When many agents need to transmit information over the same wireless network, communication becomes a shared and contested resource. Event-triggered and self-triggered control account for this by transmitting data only when needed, enabling significant energy savings. However, a solution that brings those benefits to multi-hop networks and can reallocate freed up bandwidth to additional agents or data sources is still missing. To fill this gap, we propose control-guided communication, a novel co-design approach for distributed self-triggered control over wireless multi-hop networks. The control system informs the communication system of its transmission demands ahead of time, and the communication system allocates resources accordingly. Experiments on a cyber-physical testbed show that multiple cart-poles can be synchronized over wireless, while serving other traffic when resources are available, or saving energy. These experiments are the first to demonstrate and evaluate distributed self-triggered control over low-power multi-hop wireless networks at update rates of tens of milliseconds., Comment: Accepted final version to appear in: IEEE Control Systems Letters

The distributed dual ascent is an established algorithm to solve strongly convex multi-agent optimization problems with separable cost functions, in the presence of coupling constraints. In this letter, we study its asynchronous counterpart. Specifically, we assume that each agent only relies on the outdated information received from some neighbors. Differently from the existing randomized and dual block-coordinate schemes, we show convergence under heterogeneous delays, communication and update frequencies. Consequently, our asynchronous dual ascent algorithm can be implemented without requiring any coordination between the agents.