Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards

2023-06-08 · NeurIPS 2023 11

We study a decentralized multi-agent multi-armed bandit problem in which multiple clients are connected by time dependent random graphs provided by an environment. The reward distributions of each arm vary across clients and rewards are generated independently over time by an environment based on distributions that include both sub-exponential and sub-gaussian distributions. Each client pulls an arm and communicates with neighbors based on the graph provided by the environment. The goal is to minimize the overall regret of the entire system through collaborations. To this end, we introduce a novel algorithmic framework, which first provides robust simulation methods for generating random graphs using rapidly mixing Markov chains or the random graph model, and then combines an averaging-based consensus approach with a newly proposed weighting technique and the upper confidence bound to deliver a UCB-type solution. Our algorithms account for the randomness in the graphs, removing the conventional doubly stochasticity assumption, and only require the knowledge of the number of clients at initialization. We derive optimal instance-dependent regret upper bounds of order $\log{T}$ in both sub-gaussian and sub-exponential environments, and a nearly optimal mean-gap independent regret upper bound of order $\sqrt{T}\log T$ up to a $\log T$ factor. Importantly, our regret bounds hold with high probability and capture graph randomness, whereas prior works consider expected regret under assumptions and require more stringent reward distributions.

📄 PDF Abstract BibTeX arXiv:2306.05579

Code (0)

등록된 구현이 없습니다.

PopSGD: Decentralized Stochastic Gradient Descent in the Population Model

2019-09-25 · Giorgi Nadiradze, Amirmojtaba Sabour, Aditya Sharma, Ilia Markov 외

The population model is a standard way to represent large-scale decentralized distributed systems, in which agents with limited computational power interact in randomly chosen pairs, in order to collectively solve global…

Distributed Optimization Scheduling

Distributed Policy Iteration for Scalable Approximation of Cooperative Multi-Agent Policies

2019-01-25 · Thomy Phan, Kyrill Schmid, Lenz Belzner, Thomas Gabor 외

Decision making in multi-agent systems (MAS) is a great challenge due to enormous state and joint action spaces as well as uncertainty, making centralized control generally infeasible. Decentralized control offers better…

Decision Making Multi-agent Reinforcement Learning Reinforcement Learning

Secure Distributed/Federated Learning: Prediction-Privacy Trade-Off for Multi-Agent System

2022-04-24 · Mohamed Ridha Znaidi, Gaurav Gupta, Paul Bogdan

Decentralized learning is an efficient emerging paradigm for boosting the computing capability of multiple bounded computing agents. In the big data era, performing inference within the distributed and federated learning…

Federated Learning Privacy Preserving

Multi-Agent Trust Region Policy Optimization

2020-10-15 · Hepeng Li, Haibo He

We extend trust region policy optimization (TRPO) to multi-agent reinforcement learning (MARL) problems. We show that the policy update of TRPO can be transformed into a distributed consensus optimization problem for mul…

Multi-agent Reinforcement Learning Privacy Preserving reinforcement-learning Reinforcement Learning (RL)

Multi-Agent Distributed Lifelong Learning for Collective Knowledge Acquisition

2017-09-15 · Mohammad Rostami, Soheil Kolouri, Kyungnam Kim, Eric Eaton

Lifelong machine learning methods acquire knowledge over a series of consecutive tasks, continually building upon their experience. Current lifelong learning algorithms rely upon a single learning agent that has centrali…

Lifelong learning Multi-Task Learning