V-Learning: Simple, Efficient, Decentralized Algorithm for Multiagent RL
summary
Claim: a new algorithm V-learning lets each agent run the same single-agent procedure independently and provably finds Nash equilibria (two-player zero-sum) and CE/CCE (multiplayer general-sum) with sample complexity that depends on max_i A_i rather than the joint-action product. Key tools: incremental updates to V-values (no Q-tensor), per-state adversarial-bandit subroutines (e.g. follow-the-regularized-leader) to produce policies, and optimism bonuses. Result is theoretical: polynomial in S, H and 1/ε (no exponential agent dependence); experiments are not shown.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:48Problems
- 3:53cursive multiagents
- 5:07centralized vs decentralized
- 6:55characterization
- 9:14markup games
- 11:55policy value
- 13:57setting
- 16:25learning
- 23:25Single Engine Reinforcement
- 25:55Challenges
- 26:38Normal Form Games
- 28:52adversarial bandit
- 30:55duality gap
- 38:41no regret learning
- 50:14converge