Learning to Play General-Sum Games Against Multiple Boundedly Rational Agents
We study the problem of training a principal in a multi-agent general-sum game using reinforcement learning (RL). Learning a robust principal policy requires anticipating the worst possible strategic responses of other agents, which is generally NP-hard. However, we show that no-regret dynamics can identify these worst-case responses in poly-time in smooth games. We propose a framework that uses this policy evaluation method for efficiently learning a robust principal policy using RL. This framework can be extended to provide robustness to boundedly rational agents too. Our motivating application is automated mechanism design: we empirically demonstrate our framework learns robust mechanisms in both matrix games and complex spatiotemporal games. In particular, we learn a dynamic tax policy that improves the welfare of a simulated trade-and-barter economy by 15%, even when facing previously unseen boundedly rational RL taxpayers.
Code (1)
Tasks
Decision MakingMulti-agent Reinforcement LearningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability
Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but h…
Towards a taxonomy of learning dynamics in 2 x 2 games
Do boundedly rational players learn to choose equilibrium strategies as they play a game repeatedly? A large literature in behavioral game theory has proposed and experimentally tested various learning algorithms, but a …
Soft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning
Markov games model interactions among multiple players in a stochastic, dynamic environment. Each player in a Markov game maximizes its expected total discounted reward, which depends upon the policies of the other playe…
OpenAI GymCournot duopoly games with isoelastic demands and diseconomies of scale
In this discussion draft, we investigate five different models of duopoly games, where the market is assumed to have an isoelastic demand function. Moreover, quadratic cost functions reflecting decreasing returns to scal…
Biasing MCTS with Features for General Games
This paper proposes using a linear function approximator, rather than a deep neural network (DNN), to bias a Monte Carlo tree search (MCTS) player for general games. This is unlikely to match the potential raw playing st…
Board Games