Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints
We study the problem of multi-agent reinforcement learning (MARL) with adaptivity constraints -- a new problem motivated by real-world applications where deployments of new policies are costly and the number of policy updates must be minimized. For two-player zero-sum Markov Games, we design a (policy) elimination based algorithm that achieves a regret of $\widetilde{O}(\sqrt{H^3 S^2 ABK})$, while the batch complexity is only $O(H+\log\log K)$. In the above, $S$ denotes the number of states, $A,B$ are the number of actions for the two players respectively, $H$ is the horizon and $K$ is the number of episodes. Furthermore, we prove a batch complexity lower bound $\Omega(\frac{H}{\log_{A}K}+\log\log K)$ for all algorithms with $\widetilde{O}(\sqrt{K})$ regret bound, which matches our upper bound up to logarithmic factors. As a byproduct, our techniques naturally extend to learning bandit games and reward-free MARL within near optimal batch complexity. To the best of our knowledge, these are the first line of results towards understanding MARL with low adaptivity.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-agent Reinforcement Learningreinforcement-learningSimilar Papers 제목 키워드 기반
Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?
Deep reinforcement learning has achieved many recent successes, but our understanding of its strengths and limitations is hampered by the lack of rich environments in which we can fully characterize optimal behavior, and…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Near-Optimal Reinforcement Learning with Self-Play
This paper considers the problem of designing optimal algorithms for reinforcement learning in two-player zero-sum games. We focus on self-play algorithms which learn the optimal policy by playing against itself without …
Q-Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Approximating Auction Equilibria with Reinforcement Learning
Traditional methods for computing equilibria in auctions become computationally intractable as auction complexity increases, particularly in multi-item and dynamic auctions. This paper introduces a self-play based reinfo…
reinforcement-learningReinforcement LearningLearning Near-Optimal Intrusion Responses Against Dynamic Attackers
We study automated intrusion response and formulate the interaction between an attacker and a defender as an optimal stopping game where attack and defense strategies evolve through reinforcement learning and self-play. …
Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
Multi-agent reinforcement learning (MARL), as a thriving field, explores how multiple agents independently make decisions in a shared dynamic environment. Due to environmental uncertainties, policies in MARL must remain …
Multi-agent Reinforcement Learning