Multi-Agent Learning with Policy Prediction

By Chongjie Zhang, Victor R. Lesser. 2010

144 citations recorded by the source corpus.

Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based learning algorithm, augmenting the basic gradient ascent approach with policy prediction. We prove that this augmentation results in a stronger notion of convergence than the basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this augmentation, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Unrolled Generative Adversarial Networks (2016, methodology): “In the case of 1-step unrolled optimization this is known to lead to convergence for games in which gradient descent (ascent) fails (Zhang & Lesser, 2010).”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Visualization of Evolutionary and Policy Learning Dynamics One common visualization tool in the multiagent learning literature (especially in games) is a phase portrait that shows a vector field and/or trajectories of particle the depict local changes to the policy under specific update dynamics [64”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Moreover, agents can learn to shape the learning of other agents and thus the nature of the non-stationarity in their environment (Kim et al., 2022; Foerster et al., 2018a,1; Kim et al., 2021a; Letcher et al., 2019; Zhang and Lesser, 2010).”
Learning with Opponent-Learning Awareness (2017, background): “A LOLA learner optimizes its policy by driving the oppo-nent’s best-response policy to maximize its own expected discounted future return, such that in every iteration, , where In contrast to prior works, e.g., Zhang and Lesser (2010), that only predict the opponent’s policy parameter update, LOLA l”
Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments (2017, background): “s) where each episode is one-shot interaction [26–28]. In such games, discovering and converging to a Nash equilibrium strategy is a success for the learning agents. Modeling and exploiting opponents [29, 30] or event their learning processes [31] is advantageous as it improves convergence or helps ”
A survey and critique of multiagent deep reinforcement learning (2018, methodology): “LOLA builds on previous ideas by Zhang and Lesser [264] where the learning agent predicts the opponent’s policy parameter update but only uses it to learn a best response (to the anticipated updated parameters).”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, methodology): “These analyses are common in multiagent learning as they allow visual depiction of the policy changes and how different factors affect the (convergence) behavior [83, 92, 13, 91, 11, 94, 1, 99, 98, 8, 89].”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “ng applications with interacting agents, problems of this form are being studied extensively again. There has also been a shift toward analyzing gradient-based learning rules and convergence analysis [3,15,24,28,43]. The progress analyzing learning dynamics and seeking equilibria in games is promisi”
Towards Understanding Linear Value Decomposition in Cooperative Multi-Agent Q-Learning (2020, background): “Such complex tasks require MARL to learn decentralized policies for agents to jointly optimize a global cumulative reward signal, and post a number of challenges, including multi-agent credit assignment [4–6], non-stationarity [7, 8], and scalability [3, 9].”
Opponent Modeling by Expectation–Maximization and Sequence Prediction in Simplified Poker (2017, unknown): “These opponents are as follows: • OS-MCCFR (without our model) by Lanctot et al. [27]; • PGA-APP (policy gradient ascent with approximate policy prediction), a state-of-the-art, Q-learning-based, reinforcement learning method by Zhang and Lesser [7]; • UCB (upper confidence bounds), a popular adapti”
A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning (2020, background): “Another relevant idea explored by Letcher et al. (2019) is to interpolate between the frameworks of Zhang & Lesser (2010) and Foerster et al. (2018a) in a way that guarantees convergence while inﬂu-encing the opponent’s future policy.”
A Deep Policy Inference Q-Network for Multi-Agent Systems (2017, background): “While approaches for eliminating the need of prior knowledge of the environment have been attempted [2, 22, 24, 36], they are still limited to simple grid-world settings, and are unable to be scaled”
Optimizing for the Future in Non-Stationary MDPs (2020, background): “…in games has been shown to be useful and regret bounds for multi-player games where players can be replaced with some probability p , i.e., the game changes slowly over time, has also been established (Zhang and Lesser, 2010; Mealing and Shapiro, 2013; Foster et al., 2016; Foerster et al., 2018).”
Stable Opponent Shaping in Differentiable Games (2018, methodology): “The main result of Zhang & Lesser (2010) is that LookAhead converges to Nash equilibria in the small class of two-player, two-action bimatrix games.”
Lenient Learning in Independent-Learner Stochastic Cooperative Games (2016, background): “Other approaches, based on gradient descent, also try to converge to Nash Equilibria in self play (Abdallah and Lesser, 2008; Zhang and Lesser, 2010).”
Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning (2019, background): “Zhang and Lesser (2010) assumed that the term ∆ θ 2 is not differentiable with respect to θ 1 and they proved convergence to Nash equilibrium in 2-player 2-action games.”