Source-linked AI summary
Bi-level Actor-Critic for Multi-agent Coordination
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, Jun Wang
TL;DR
MARL methods may converge to arbitrary Nash equilibria, leaving equilibrium selection uncertain. This paper formulates bi-level reinforcement learning for finding Stackelberg equilibria and proposes a bi-level actor-critic method. It reports convergence to Stackelberg equilibria in matrix games and an asymmetric solution in a highway-merge environment.
Problem
MARL approaches may converge to an arbitrary Nash equilibrium when multiple equilibria exist, leaving the equilibrium-selection problem unresolved.
Source: Introduction · p. 1, Stackelberg Equilibrium vs. Nash… · p. 3Method
The paper formulates model-free, multi-state Stackelberg-equilibrium learning as bi-level reinforcement learning and proposes a bi-level actor-critic method trained centrally and executed decentrally.
Source: Introduction · p. 1, Conclusion · p. 7Results
The algorithm converged to Stackelberg equilibria in matrix games and found an asymmetric solution in a highway-merge environment.
Source: Conclusion · p. 7, Discussion of convergence of Bi-AC · p. 10Takeaways & Limitations
The paper presents Stackelberg equilibrium as a learning objective that can provide greater certainty than arbitrary Nash-equilibrium selection and may be Pareto superior in cooperative settings.
Source: Introduction · p. 1, Stackelberg Equilibrium vs. Nash… · p. 3Assumption 3 is strong and may not hold even at the start of training; the bi-level Bellman equation is necessary but not sufficient for a BiRL solution, so other convergent points may exist.
Source: Convergence and Limitation · p. 4
Abstract
from arXiv · showhide
Coordination is one of the essential problems in multi-agent systems. Typically multi-agent reinforcement learning (MARL) methods treat agents equally and the goal is to solve the Markov game to an arbitrary Nash equilibrium (NE) when multiple equilibra exist, thus lacking a solution for NE selection. In this paper, we treat agents \emph{unequally} and consider Stackelberg equilibrium as a potentially better convergence point than Nash equilibrium in terms of Pareto superiority, especially in cooperative environments. Under Markov games, we formally define the bi-level reinforcement learning problem in finding Stackelberg equilibrium. We propose a novel bi-level actor-critic learning method that allows agents to have different knowledge base (thus intelligent), while their actions still can be executed simultaneously and distributedly. The convergence proof is given, while the resulting learning algorithm is tested against the state of the arts. We found that the proposed bi-level actor-critic algorithm successfully converged to the Stackelberg equilibria in matrix games and find an asymmetric solution in a highway merge environment.
Introduction
Multi-agent reinforcement learning methods can converge to an arbitrary Nash equilibrium, leaving equilibrium selection uncertain. The paper instead makes Stackelberg equilibrium the learning objective and proposes a bi-level actor-critic algorithm for learning it in unknown, multi-state environments.
Introduction
- Existing model-free approaches train agents centrally to reach a Nash equilibrium but cannot guarantee which equilibrium they reach, creating uncertainty and possible sub-optimality.The paper frames this as a coordination or Nash-equilibrium selection problem.Source: Introduction · p. 1
- In cooperative games the Stackelberg equilibrium is Pareto optimal, and the paper reports it is likely Pareto superior to the average Nash equilibrium in games with high cooperation.The introduction also describes a non-cooperative example where the Stackelberg equilibrium is Pareto superior to any Nash equilibrium.Source: Introduction · p. 1, Table 1 · p. 2
- The proposed bi-level actor-critic method learns Stackelberg equilibrium in unknown, multi-state environments and is trained centrally before distributed execution.The reported experiments demonstrate efficiency and outperforming state-of-the-art algorithms.Source: Introduction · pp. 1–2
Preliminaries
The preliminaries define the Markov-game setting, situate the method among MARL equilibrium-learning approaches, and relate bi-level optimization to Stackelberg games.
Markov Game
- A Markov game specifies states, agents’ action spaces, transitions, rewards, and a discount factor; agents act simultaneously according to policies and seek to maximize discounted cumulative reward.The paper also uses MARL as another name for Markov games.Source: Markov Game · p. 2
Related MARL Solutions
- Minimax-Q targets worst-case values in zero-sum games, while Nash-Q seeks Nash-equilibrium values; the paper’s bi-level method instead targets Stackelberg equilibrium and generalizes minimax to general-sum games.The paper distinguishes its generalization from Nash-Q’s different direction of generalization.Source: Related MARL Solutions · p. 2
Bi-level Optimization
- In the paper’s two-player asymmetric Markov game, the follower observes the leader’s actions; the resulting bi-level optimization is equivalent to a Stackelberg game, whose solution is a Stackelberg equilibrium.The upper- and lower-level optimizers correspond to the leader and follower, respectively.Source: Bi-level Optimization · p. 2
Bi-level Reinforcement Learning
The paper formulates BiRL as a multi-state, model-free Stackelberg game and develops learning methods to find Stackelberg equilibria. It argues that these equilibria can offer a more certain and higher-payoff coordination target than the average Nash equilibrium in cooperative settings.
Problem Formulation
- BiRL extends Stackelberg games to sequential discounted rewards and unknown objectives learned through model-free interaction.The formulation connects each agent’s policy to a bi-level optimizer and its cumulative reward to that optimizer’s objective.Source: Problem Formulation · p. 2
Stackelberg Equilibrium vs. Nash equilibrium
- In high-cooperation games, both agents achieve higher payoffs at the SE than at the average NE, and Nash-equilibrium counts rise with cooperation.The authors argue the SE may be Pareto superior in coordination problems, especially in highly cooperative games.Source: Stackelberg Equilibrium vs. Nash… · p. 3
Bi-level Tabular Q-learning
- Bi-level tabular Q-learning updates Q-values using the bi-level Bellman equation, with Stackelberg payoffs defining the state-value targets.In the illustrated cooperative game, joint policies ending at 20 are Stackelberg equilibria, while those ending at 10 or 20 are Nash equilibria.Source: Bi-level Tabular Q-learning · p. 3, Figure 1 · p. 3
Bi-level Actor-Critic
- Bi-AC pairs a follower actor with a leader Q-learner, supports centralized training and decentralized execution, and extends naturally to multiple levels.In execution, the leader and follower use their trained models to achieve Stackelberg equilibria distributively.Source: Bi-level Actor-Critic · p. 4
Convergence and Limitation
- The convergence argument uses a Cauchy-sequence proof under stated assumptions, but the authors call one assumption strong and note the Bellman condition is necessary, not sufficient.Consequently, convergent points other than BiRL solutions may exist.Source: Convergence and Limitation · p. 4
Related Work
Prior coordination work addresses equilibrium selection through social conventions and optimistic learning, while communication and opponent modeling offer other coordination approaches. BiRL extends Stackelberg and bi-level methods to multi-state, model-free learning and differs from earlier Stackelberg-Q work in its scope and motivation.
Related Work
- Social conventions break ties by ordering agents and actions, while optimistic-expectation methods target cooperative equilibria but do not extend to general-sum games.The passage also notes that BiRL is compatible with social conventions because agents share knowledge of the Stackelberg equilibrium.Source: Related Work · p. 5
- Communication methods exchange information through centralized networks or bidirectional RNNs, whereas opponent-modeling approaches use decentralized training and BiRL uses centralized training.Examples include CommNet and BicNet for communication, and ROMMEO and recursive reasoning for opponent modeling.Source: Related Work · p. 5
- BiRL formulates a multi-state, model-free leader-follower problem, extending bi-level optimization in both dimensions.Earlier approaches include stateless model-based evolutionary methods, stateless model-free leader-follower problems, and multi-state model-based Stackelberg games under a linear-quadratic assumption.Source: Related Work · p. 5
- AQL solves a Stackelberg equilibrium at each update, but Bi-AC also supports multi-level or continuous actions and targets symmetric coordination rather than asymmetric problems.Other Stackelberg approaches cited for asymmetric problems include Bully and DeDOL.Source: Related Work · p. 5
Experiment
The paper evaluates Bi-AC in three coordination environments against state-of-the-art MARL algorithms.
Experiment
- The experiments compare Bi-AC with state-of-the-art MARL algorithms in three coordination environments.Source: Experiment · p. 5
Algorithms
The experimental section describes shared model and exploration settings, then introduces the tested algorithms and reports selected training visuals. Bi-AC uses DQN critics, while the baselines include decentralized and centralized training methods.
Algorithms
- All algorithms use 1,000 initial steps of full action exploration, followed by decaying epsilon-greedy exploration and three-layer ReLU networks.Critics use replay buffers and target networks; Gumbel-Softmax is used for actor functions when applicable.Source: Algorithms · p. 5
Bi-AC
- The implemented Bi-AC variant models both critics with DQN.Source: Bi-AC · p. 5
I-DQN
- I-DQN treats other agents as part of the environment and, if it converges, converges to a Nash equilibrium.The passage says I-DQN is not guaranteed to converge.Source: I-DQN · p. 5
MADDPG
- MADDPG is tested as a centralized-training, decentralized-execution baseline, and TD3 is described as addressing function-approximation error in MADDPG.The paper characterizes TD3 as a state-of-the-art MARL algorithm.Source: MADDPG · p. 5
Hysteretic-DQN
- Hysteretic-DQN uses a smaller learning rate for updates that reduce Q-values, emphasizing positive experiences; Figure 4 depicts Bi-AC convergence in Escape.Source: Hysteretic-DQN · p. 5, Figure 4 · p. 6
Lenient-DQN
- Lenient-DQN combines DQNs with leniency to increase the likelihood of reaching a global optimum in fully cooperative environments requiring implicit coordination.Source: Lenient-DQN · p. 6
Matrix Game
In the Escape and Maintain matrix games, Bi-AC reaches the intended Stackelberg solutions more often than the reported baselines. The section also identifies the traffic-merge result table and its treatment of crashes.
Matrix Game
- The Escape setup tests convergence to C-Z against suboptimal A-X, which a Nash learner may reach unless C-Z is explored sufficiently.Source: Matrix Game · p. 6
- The tabular Bi-AC version was also run to confirm the Escape result.Source: Matrix Game · p. 6
- Table 4 reports the rate at which the main-lane car goes first; its two rate columns may sum to less than 100% because of crashes, and Figure 6 illustrates the merge environment.Source: Table 4 · p. 7, Figure 6 · p. 7
- Bi-AC converged to the Pareto-optimal A-X point in every Maintain trial, while baselines never converged to the optimum.The section contrasts A-X, a Stackelberg equilibrium but not a Nash equilibrium, with the points expected from Nash learners.Source: Matrix Game · pp. 6–7, Table 3 · p. 6