Heterogeneous Explore-Exploit Strategies on Multi-Star Networks
- URL: http://arxiv.org/abs/2009.01339v2
- Date: Wed, 2 Dec 2020 01:47:29 GMT
- Title: Heterogeneous Explore-Exploit Strategies on Multi-Star Networks
- Authors: Udari Madhushani and Naomi Leonard
- Abstract summary: We study a class of distributed bandit problems in which agents communicate over a multi-star network.
We propose new heterogeneous explore-exploit strategies using the multi-star as the model irregular network graph.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the benefits of heterogeneity in multi-agent explore-exploit
decision making where the goal of the agents is to maximize cumulative group
reward. To do so we study a class of distributed stochastic bandit problems in
which agents communicate over a multi-star network and make sequential choices
among options in the same uncertain environment. Typically, in multi-agent
bandit problems, agents use homogeneous decision-making strategies. However,
group performance can be improved by incorporating heterogeneity into the
choices agents make, especially when the network graph is irregular, i.e. when
agents have different numbers of neighbors. We design and analyze new
heterogeneous explore-exploit strategies, using the multi-star as the model
irregular network graph. The key idea is to enable center agents to do more
exploring than they would do using the homogeneous strategy, as a means of
providing more useful data to the peripheral agents. In the case all agents
broadcast their reward values and choices to their neighbors with the same
probability, we provide theoretical guarantees that group performance improves
under the proposed heterogeneous strategies as compared to under homogeneous
strategies. We use numerical simulations to illustrate our results and to
validate our theoretical bounds.
Related papers
- Enhancing Heterogeneous Multi-Agent Cooperation in Decentralized MARL via GNN-driven Intrinsic Rewards [1.179778723980276]
Multi-agent Reinforcement Learning (MARL) is emerging as a key framework for sequential decision-making and control tasks.
The deployment of these systems in real-world scenarios often requires decentralized training, a diverse set of agents, and learning from infrequent environmental reward signals.
We propose the CoHet algorithm, which utilizes a novel Graph Neural Network (GNN) based intrinsic motivation to facilitate the learning of heterogeneous agent policies.
arXiv Detail & Related papers (2024-08-12T21:38:40Z) - Combining Diverse Information for Coordinated Action: Stochastic Bandit Algorithms for Heterogeneous Agents [26.075152706845454]
Multi-agent bandits assume that rewards from each arm follow a fixed distribution.
rewards can depend on the sensitivity of each agent to their environment.
We introduce a UCB-style algorithm, Min-Width, which aggregates information from diverse agents.
arXiv Detail & Related papers (2024-08-06T18:56:29Z) - Deep Multi-Agent Reinforcement Learning for Decentralized Active
Hypothesis Testing [11.639503711252663]
We tackle the multi-agent active hypothesis testing (AHT) problem by introducing a novel algorithm rooted in the framework of deep multi-agent reinforcement learning.
We present a comprehensive set of experimental results that effectively showcase the agents' ability to learn collaborative strategies and enhance performance.
arXiv Detail & Related papers (2023-09-14T01:18:04Z) - 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) - 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) - Learning Multi-agent Skills for Tabular Reinforcement Learning using
Factor Graphs [41.17714498464354]
We show that it is possible to directly compute multi-agent options with collaborative exploratory behaviors among the agents.
The proposed algorithm can successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
arXiv Detail & Related papers (2022-01-20T15:33:08Z) - Multi-agent Policy Optimization with Approximatively Synchronous
Advantage Estimation [55.96893934962757]
In multi-agent system, polices of different agents need to be evaluated jointly.
In current methods, value functions or advantage functions use counter-factual joint actions which are evaluated asynchronously.
In this work, we propose the approximatively synchronous advantage estimation.
arXiv Detail & Related papers (2020-12-07T07:29:19Z) - Cooperative Heterogeneous Deep Reinforcement Learning [47.97582814287474]
We present a Cooperative Heterogeneous Deep Reinforcement Learning framework that can learn a policy by integrating the advantages of heterogeneous agents.
Global agents are off-policy agents that can utilize experiences from the other agents.
Local agents are either on-policy agents or population-based evolutionary (EAs) agents that can explore the local area effectively.
arXiv Detail & Related papers (2020-11-02T07:39:09Z) - Randomized Entity-wise Factorization for Multi-Agent Reinforcement
Learning [59.62721526353915]
Multi-agent settings in the real world often involve tasks with varying types and quantities of agents and non-agent entities.
Our method aims to leverage these commonalities by asking the question: What is the expected utility of each agent when only considering a randomly selected sub-group of its observed entities?''
arXiv Detail & Related papers (2020-06-07T18:28:41Z) - Individual specialization in multi-task environments with multiagent
reinforcement learners [0.0]
There is a growing interest in Multi-Agent Reinforcement Learning (MARL) as the first steps towards building general intelligent agents.
Previous results point us towards increased conditions for coordination, efficiency/fairness, and common-pool resource sharing.
We further study coordination in multi-task environments where several rewarding tasks can be performed and thus agents don't necessarily need to perform well in all tasks, but under certain conditions may specialize.
arXiv Detail & Related papers (2019-12-29T15:20:24Z)
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.