Specification-Guided Learning of Nash Equilibria with High Social Welfare
Reinforcement learning has been shown to be an effective strategy for
automatically training policies for challenging control problems. Focusing on
non-cooperative multi-agent systems, we propose a novel reinforcement learning
framework for training joint policies that form a Nash equilibrium. In our
approach, rather than providing low-level reward functions, the user provides
high-level specifications that encode the objective of each agent. Then, guided
by the structure of the specifications, our algorithm searches over policies to
identify one that provably forms an $\epsilon$-Nash equilibrium (with high
probability). Importantly, it prioritizes policies in a way that maximizes
social welfare across all agents. Our empirical evaluation demonstrates that
our algorithm computes equilibrium policies with high social welfare, whereas
state-of-the-art baselines either fail to compute Nash equilibria or compute
ones with comparatively lower social welfare.