V-Learning—A Simple, Efficient, Decentralized Algorithm for Multiagent Reinforcement Learning
提出V学习算法，将对抗性赌博机算法转化为强化学习算法，在马尔可夫博弈中实现去中心化学习，样本复杂度仅与各智能体动作数之和相关，而非联合动作空间指数级增长。
A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms, even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms—V-learning, which provably learns Nash equilibria (in the two-player zero-sum setting), correlated equilibria, and coarse correlated equilibria (in the multiplayer general-sum setting) in a number of samples that only scales with [Formula: see text], where A i is the number of actions for the ith player. This is in sharp contrast to the size of the joint action space, which is [Formula: see text]. V-learning (in its basic form) is a new class of single-agent reinforcement learning (RL) algorithms that convert any adversarial bandit algorithm with suitable regret guarantees into an RL algorithm. Similar to the classical Q-learning algorithm, it performs incremental updates to the value functions. Different from Q-learning, it only maintains the estimates of V-values instead of Q-values. This key difference allows V-learning to achieve the claimed guarantees in the MARL setting by simply letting all agents run V-learning independently. Funding: This work was partially supported by Office of Naval Research Grant N00014-22-1-2253.