The Influence of Memory in Multi-Agent Consensus

• URL: http://arxiv.org/abs/2105.04666v1
• Date: Mon, 10 May 2021 20:59:35 GMT
• Title: The Influence of Memory in Multi-Agent Consensus
• Authors: David Kohan Marzag\~ao, Luciana Basualdo Bonatto, Tiago Madeira, Marcelo Matheus Gauy, Peter McBurney
• Abstract summary: We propose a framework to study what we call emphmemory consensus protocol. We show that the employment of memory allows such processes to always converge, as well as, in some scenarios, such as cycles, converge faster. We provide a theoretical analysis of the probability of each option eventually winning such processes based on the initial opinions expressed by agents.
• Score: 0.8399688944263843
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Multi-agent consensus problems can often be seen as a sequence of autonomous and independent local choices between a finite set of decision options, with each local choice undertaken simultaneously, and with a shared goal of achieving a global consensus state. Being able to estimate probabilities for the different outcomes and to predict how long it takes for a consensus to be formed, if ever, are core issues for such protocols. Little attention has been given to protocols in which agents can remember past or outdated states. In this paper, we propose a framework to study what we call \emph{memory consensus protocol}. We show that the employment of memory allows such processes to always converge, as well as, in some scenarios, such as cycles, converge faster. We provide a theoretical analysis of the probability of each option eventually winning such processes based on the initial opinions expressed by agents. Further, we perform experiments to investigate network topologies in which agents benefit from memory on the expected time needed for consensus.

Related papers

• Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis [55.13545823385091]
  Federated reinforcement learning (FedRL) enables collaborative learning while preserving data privacy by preventing direct data exchange between agents. In real-world applications, each agent may experience slightly different transition dynamics, leading to inherent model mismatches. We show that even moderate levels of information sharing can significantly mitigate environment-specific errors.
  arXiv  Detail & Related papers  (2025-03-21T18:06:28Z)
• Causal Influence in Federated Edge Inference [34.487472866247586]
  In this paper, we consider a setting where heterogeneous agents with connectivity are performing inference using unlabeled streaming data. In order to overcome the uncertainty, agents cooperate with each other by exchanging their local inferences with and through a fusion center. Various scenarios reflecting different agent participation patterns and fusion center policies are investigated.
  arXiv  Detail & Related papers  (2024-05-02T13:06:50Z)
• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  This study focuses on a simplified version of the overarching problem, where each agent collects samples from a real-valued distribution over time to estimate its mean. We introduce two collaborative mean estimation algorithms: one draws inspiration from belief propagation, while the other employs a consensus-based approach.
  arXiv  Detail & Related papers  (2024-02-20T08:30:46Z)
• Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
  Planning under uncertainty can be mathematically formalized using partially observable Markov decision processes (POMDPs) Finding an optimal plan for POMDPs can be computationally expensive and is feasible only for small tasks. We derive a deterministic relationship between a simplified solution that is easier to obtain and the theoretically optimal one.
  arXiv  Detail & Related papers  (2023-10-03T04:40:38Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• A protocol for global multiphase estimation [0.0]
  We devise a global multiphase protocol based on Holevo's estimation theory. We show that in the multiphase strategy there is only a constant quantum advantage with respect to a sequence of independent single-phase estimations.
  arXiv  Detail & Related papers  (2023-01-18T09:14:23Z)
• Multi-agent Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Cooperative Online Learning in Stochastic and Adversarial MDPs [50.62439652257712]
  We study cooperative online learning in and adversarial Markov decision process (MDP) In each episode, $m$ agents interact with an MDP simultaneously and share information in order to minimize their individual regret. We are the first to consider cooperative reinforcement learning (RL) with either non-fresh randomness or in adversarial MDPs.
  arXiv  Detail & Related papers  (2022-01-31T12:32:11Z)
• Improved analytical bounds on delivery times of long-distance entanglement [0.0]
  We provide improved analytical bounds on the average and on the quantiles of the completion time of entanglement distribution protocols. A canonical example of such a protocol is a nested quantum repeater scheme which consists of heralded entanglement generation and entanglement swaps.
  arXiv  Detail & Related papers  (2021-03-21T18:14:56Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.