mlsanityData to 7 Oct 2026

Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds

arXiv 2301.11802 ↗First posted 27 Jan 2023cs.LG cs.GTcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider a decentralized multiplayer game, played over T rounds, with a leader-follower hierarchy described by a directed acyclic graph. For each round, the graph structure dictates the order of the players and how players observe the actions of one another. By the end of each round, all players receive a joint bandit-reward based on their joint action that is used to update the player strategies towards the goal of minimizing the joint pseudo-regret. We present a learning algorithm inspired by the single-player multi-armed bandit problem and show that it achieves sub-linear joint pseudo-regret in the number of rounds for both adversarial and stochastic bandit rewards. Furthermore, we quantify the cost incurred due to the decentralized nature of our problem compared to the centralized setting.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 39 references that are in the map. First posted on arXiv 27 Jan 2023.

Builds on

24 of 39 references.

References · 24

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2021How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learnedcited by 201
  3. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 189
  4. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  5. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  7. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  8. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  9. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  10. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  11. 2019Strategizing against No-regret Learnerscited by 48
  12. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
12 more
  1. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  2. 2019Multi-Armed Bandits with Correlated Armscited by 33
  3. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  4. 2019Cooperative Online Learning: Keeping your Neighbors Updatedcited by 22
  5. 2020Learning to Play Sequential Games versus Unknown Opponentscited by 18
  6. 2020Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisionscited by 13
  7. 2022No-Regret Learning in Dynamic Stackelberg Gamescited by 12
  8. 2020Competitive Mirror Descentcited by 7
  9. 2022Robust No-Regret Learning in Min-Max Stackelberg Gamescited by 5
  10. 2021Cooperative Online Learning with Feedback Graphscited by 4
  11. 2021Partner-Aware Algorithms in Decentralized Cooperative Bandit Teamscited by 1
  12. 2022Playing against no-regret playerscited by 1

Built on by

Not cited yet.