Multi-Player Bandits With No Collisions

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=J-H8ka4Zhfc


Duration: 40:34
436 views
4

Mark Sellke (Stanford)
https://simons.berkeley.edu/talks/multi-player-bandits-no-collisions
Multi-Agent Reinforcement Learning and Bandit Learning

In the stochastic multi-player bandit problem, m(greater than)1 players cooperate to maximize their total reward on a set of K(greater than)m bandit arms. However the players cannot communicate online and are penalized (e.g. receive no reward) if they collide by pulling the same arm at the same time. This problem was introduced in the context of wireless radio communication and serves as a natural model for decentralized online decision-making. There have been many results for different versions of this model. Most rely on a small number of collisions in order to implicitly communicate. However it was later realized that nearly-optimal T^{1/2} regret is possible with no collisions (and hence no communication) at all. I will discuss this construction, as well as our recent characterization of the Pareto optimal trade-offs for gap dependent regret without communication. Based on collaborations with Sebastien Bubeck, Thomas Budzinski, and Allen Liu.



Other Videos By Simons Institute for the Theory of Computing


2022-05-26Fully Homomorphic Encryption, 10 Years Later: Definitions and Open Problems
2022-05-26Max-Flow and Friends, In Almost Linear Time
2022-05-25Modeling Conflict in Social Media
2022-05-25Welcome
2022-05-11Black Holes and the Quantum-Extended Church-Turing Thesis | Quantum Colloquium
2022-05-06The Role of Conventions in Adaptive Human-AI Interaction
2022-05-06Learning Decentralized Policies in Multiagent Systems: How to Learn Efficiently and ...
2022-05-06No-Regret Learning in Extensive-Form Games
2022-05-06Learning and Equilibrium Refinements
2022-05-05Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
2022-05-05Multi-Player Bandits With No Collisions
2022-05-05What Does Machine Learning Offer Game Theory (And Vice Versa)?
2022-05-05Variants and Invariants in No-Regret Algorithms
2022-05-05When Is Offline Two-Player Zero-Sum Markov Game Solvable?
2022-05-05General Game-Theoretic Multiagent Reinforcement Learning
2022-05-05Kernelized Multiplicative Weights for 0/1-Polyhedral Games:...
2022-05-04Multi-Agent Reinforcement Learning Towards Zero-Shot Communication
2022-05-04Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning
2022-05-04Independent Learning in Stochastic Games
2022-05-04On Rewards in Multi-Agent Systems
2022-05-04Learning Automata as Building Blocks for MARL


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Multi-Agent Reinforcement Learning and Bandit Learning
Mark Sellke