PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning

Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, Wei Pan

arXiv:1901.09207v2cs.LGcs.AIstat.ML

TL;DR

Multi-agent reinforcement learning needs agents to account for how opponents respond to their possible behaviors, extending recursive reasoning beyond fixed opponent models. The paper introduces PR2, which uses variational Bayes opponent-policy approximations and decentralized algorithms; across increasingly complex tests, its recursive reasoning shows advantages, under stated equilibrium and approximation assumptions.

  • Problem

    Opponent models often handle limited scenarios or fixed opponent types, while multi-agent agents need to reason about opponents’ responses to their own potential behaviors.

  • Method

    PR2 uses variational Bayes to approximate opponents’ conditional policies, then selects best responses and improves decentralized PR2-Q and PR2-Actor-Critic policies.

  • Results

    Across three testing beds with increasing complexity, PR2 results support advantages from recursively reasoning about opponents; PR2-Q and PR2-Actor-Critic converge in self-play when one Nash equilibrium exists.

  • Takeaways & Limitations

    Recursive reasoning provides a supported approach for incorporating conditional opponent modeling into decentralized multi-agent reinforcement learning.

  • Takeaways & Limitations

    The framework requires approximating opponents’ actual conditional policies and assumes fixed dynamics for the variational-inference objective.

Abstract

from arXiv · show

Humans are capable of attributing latent mental contents such as beliefs or intentions to others. The social skill is critical in daily life for reasoning about the potential consequences of others' behaviors so as to plan ahead. It is known that humans use such reasoning ability recursively by considering what others believe about their own beliefs. In this paper, we start from level-$1$ recursion and introduce a probabilistic recursive reasoning (PR2) framework for multi-agent reinforcement learning. Our hypothesis is that it is beneficial for each agent to account for how the opponents would react to its future behaviors. Under the PR2 framework, we adopt variational Bayes methods to approximate the opponents' conditional policies, to which each agent finds the best response and then improve their own policies. We develop decentralized-training-decentralized-execution algorithms, namely PR2-Q and PR2-Actor-Critic, that are proved to converge in the self-play scenarios when there exists one Nash equilibrium. Our methods are tested on both the matrix game and the differential game, which have a non-trivial equilibrium where common gradient-based methods fail to converge. Our experiments show that it is critical to reason about how the opponents believe about what the agent believes. We expect our work to contribute a new idea of modeling the opponents to the multi-agent reinforcement learning community.

1 INTRODUCTION

Recursive reasoning models what agents believe about one another’s beliefs, supporting planning around others’ behavior. PR2 applies this idea to multi-agent deep reinforcement learning by modeling opponents’ conditional policies and reasoning about their reactions.

  • Human social reasoning includes recursive consideration of what others believe about their own beliefs.
  • Traditional opponent modeling often assumes limited scenarios, predefined strategies, or opponents that repeatedly return to the same strategy.
  • Recursive reasoning lets an agent model how an opponent reasons about the modeling agent rather than treating the opponent as a fixed type.
  • PR2 models how opponents would react to an agent’s potential behaviors before selecting the agent’s best response.
  • PR2 uses variational Bayes to model uncertainty in opponents’ conditional policies and develops decentralized-training-decentralized-execution algorithms PR2-Q and PR2-Actor-Critic.

2 RELATED WORK

Prior work models recursive reasoning and opponent behavior in multi-agent settings, but existing approaches face scalability, solvability, or equilibrium-specification limitations. PR2 is presented as accounting for opponents’ reactions without predefining opponent types or the equilibrium.

  • Recursive reasoning: Recursive reasoning has been modeled through game theory, logic-based and graphical approaches, and Theory of Mind methods.The cited approaches include Harsanyi’s game-theoretic work, logic and graphical models, and the Recursive Modeling Method.
  • Recursive reasoning: I-POMDP extends POMDPs with models of other agents, but its solvability becomes limited as recursive models expand.Its added model space allows agents to represent beliefs about what other agents know and believe.
  • Opponent modeling: Traditional opponent modeling captures behavior from history but not how opponents would respond to the agent’s behavior.The paper characterizes this as level-0 recursive reasoning.
  • Probabilistic recursive reasoning: PR2 decouples agent connections by modeling best responses and using agents’ behavior as priors for opponents’ learning.The framework considers potential consequences of opponents’ actions and their subsequent responses.
  • Opponent modeling: PR2-Q and PR2-AC do not require predefined opponent types or prior knowledge of the equilibrium.This distinguishes them from methods such as WoLF models and Nash-Q learning that require stage-game equilibrium information.
  • Multi-agent reinforcement learning: Independent learning can lose convergence guarantees in multi-agent environments, motivating centralized-training approaches such as centralized critics.The passage identifies transferring deep single-agent RL methods to multi-agent settings as challenging.

3 PRELIMINARIES

The preliminaries formalize stochastic games, joint policies, and agent-specific Q-functions. They then explain why non-correlated policy factorization can miss inter-agent reactions and lead to non-convergent cyclic behavior.

  • Stochastic games: An n-agent stochastic game is defined by state, action, reward, transition, initial-state, and discount-factor components.Each agent selects actions from its policy while receiving rewards that depend on joint actions.
  • Policies: Joint policies collect all agents’ policies, while complementary-agent policies represent the actions of agents other than i.Actions are taken simultaneously, and agents seek maximal cumulative reward.
  • Q-functions: Each agent’s Q-function depends on the joint policy because its reward depends on other agents’ actions.Although an agent controls only its own action, the resulting reward is coupled to the actions of the other agents.
  • Policy factorization: A common simplification factorizes the joint policy by assuming conditional independence between agents’ actions.This non-correlated factorization simplifies the algorithm but omits inter-agent connections and subsequent reactions.
  • Policy factorization: 2 agents can be reinforced into a cyclic trajectory that never converges to equilibrium under such simplified modeling.The passage attributes this failure to ignoring how one agent’s action affects another agent’s reaction.
  • Independent learning: Independent learning is distinct from non-correlated policy factorization because it ignores other agents’ behavior entirely.Its probability of taking a gradient step in the correct direction decreases exponentially as the number of agents increases.

4 MULTI-AGENT PROBABILISTIC RECURSIVE REASONING

PR2 models how opponents condition their policies on an agent’s actions, enabling level-1 recursive reasoning while approximating unknown conditional policies through variational inference. The resulting decentralized algorithms use this reasoning for policy-gradient and Q-learning updates, with convergence established under specified self-play conditions.

  • Probabilistic Recursive Reasoning: PR2 captures how opponents believe about what an agent believes by modeling opponents’ conditional policies given the agent’s actions.This establishes the level-1 recursive procedure ai → a−i → ai and lets the agent select a best response across possible opponent reactions.
  • Variational Inference: Because the true opponent conditional policy may be unavailable, PR2 approximates it with a learnable distribution through variational inference.PR2 treats uncertainty in opponent modeling probabilistically; amortized SVGD is used as a computationally efficient sampling method for the approximation.
  • Decentralized PR2 Algorithms: PR2-Q and PR2-Actor-Critic use decentralized training with decentralized execution while sharing environment experiences without requiring other agents’ policy parameters.Agents share states and historical joint actions, while each agent receives rewards privately.
  • Probabilistic Recursive Reasoning Policy Gradient: The recursive policy-gradient update accounts for opponents’ responses when improving the agent’s policy, rather than using only a non-correlated joint-policy factorization.The resulting gradient is guided by the opponent conditional policy and shapes the reward after considering its effect on opponents.
  • Convergence: Under self-play with one equilibrium, the PR2-Q update is implemented through fixed-point iterations resembling value iteration, and its soft value iteration operator is a contraction mapping.The convergence result applies to symmetric games whose unique equilibrium satisfies one of the stated global-optimum or saddle-equilibrium conditions.

5 EXPERIMENTS

Experiments evaluate PR2 methods on matrix games, differential games, and Particle World environments with challenging equilibria. PR2 converges to favorable equilibria and performs strongly against baselines, while showing a specific weakness in physical deception.

  • 5.1 ITERATED MATRIX GAME: In the iterated matrix game, IGA rotates around the equilibrium, whereas PR2 finds the central equilibrium in a fully distributed fashion.The agents have a single Nash equilibrium at (0.5, 0.5), and simultaneous gradient steps fail to converge.
  • 5.2 DIFFERENTIAL GAME: In the Max of Two Quadratic Game, PR2-AC converges to the global equilibrium while other baselines fall into the left local basin.The reward surface has a local maximum 0 at (-5, -5), a global maximum 10 at (5, 5), and a valley between them.
  • 5.2 DIFFERENTIAL GAME: PR2-AC does not require tuning an annealing parameter, unlike MASQL, because each agent acts as a best response to an approximated conditional policy.The response accounts for potential consequences of the opponent’s response.
  • 5.2 DIFFERENTIAL GAME: PR2-AC reaches the global equilibrium through a shortcut out of the local basin, while other algorithms converge to the local equilibrium.This learning-path behavior is reported from comparisons with the exploration trails in the figures.
  • 5.3 PARTICLE WORLD ENVIRONMENTS: In Particle World, PR2-AC performs best in cooperative navigation and beats DDPG, DDPG-OM, and MASQL in competitive settings, except against MADDPG.PR2-AC performs particularly poorly on physical deception because opponents can access its exact policies during testing.

6 CONCLUSION

The paper introduces probabilistic recursive reasoning for decentralized multi-agent reinforcement learning. Its algorithms approximate opponents’ conditional policies, compute best responses, and converge in self-play when there is one Nash equilibrium.

  • 6 CONCLUSION: PR2 models recursive beliefs about opponents using variational Bayes to approximate their conditional policies.Each agent finds a best response to the approximation before improving its own policy.
  • 6 CONCLUSION: PR2-Q and PR2-AC use decentralized training and execution and converge in self-play when there is one Nash equilibrium.The conclusion reports results across three testing beds with increasing complexity.
  • 6 CONCLUSION: The experiments support learning to reason about opponents recursively as an advantage in multi-agent reinforcement learning.The paper proposes future work on alternative approximation methods and coordination tasks.

A DECENTRALIZED MULTI-AGENT PROBABILISTIC RECURSIVE REASONING ALGORITHMS

The algorithms implement decentralized probabilistic recursive reasoning by estimating opponents’ conditional policies, selecting actions through those estimates, and updating critics and actors from replay data. A tabular variant can estimate the conditional policy by counting joint actions.

  • PR2-AC: PR2-AC initializes actor, opponent-policy, critic, target-network, replay-buffer, and exploration-process parameters for each agent.The procedure then iterates over episodes and environment steps.
  • PR2-AC: At each state, PR2-AC selects actions using the recursive opponent policy and stores joint actions, rewards, and next states in replay buffers.The stored tuples support subsequent mini-batch updates.
  • PR2-AC: PR2-AC updates each agent using sampled mini-batches, including the actor through a sampled policy gradient and target-network parameters.The algorithm loops over agents during the update stage.
  • Tabular variant: In small tabular state-action spaces, PR2 estimates ρ_-i(a_-i|s, a_i) by the count ratio C(a_i, a_-i, s)/C(a_i, s).In static games, the method degenerates to Conditional Joint Action Learning.
  • PR2-Q: PR2-Q initializes joint-action Q-functions and updates them through a decentralized multi-agent probabilistic recursive reasoning procedure.The algorithm is identified as Multi-Agent Probabilistic Recursive Reasoning Q-Learning.

B.1 MULTI-AGENT NON-CORRELATED POLICY GRADIENT

The non-correlated policy-gradient formulation applies gradients to an agent’s objective while accounting for the joint policy structure. Its practical context includes centralized critics with replay buffers for off-policy training.

  • B.1 MULTI-AGENT NON-CORRELATED POLICY GRADIENT: The method assumes non-correlated policies and applies the policy-gradient formulation using the Leibniz integral rule and Fubini’s theorem.The resulting formulation is called Multi-Agent Non-correlated Policy Gradient.
  • B.1 MULTI-AGENT NON-CORRELATED POLICY GRADIENT: The policy π_i(a_i) is parameterized by θ_i, and the gradient is applied over η_i.This specifies the parameterization used in the gradient derivation.
  • B.1 MULTI-AGENT NON-CORRELATED POLICY GRADIENT: MADDPG and COMA use replay buffers with centralized critics to support off-policy training from joint-action Q-values.The cited methods introduce batch sampling for the centralized critic.

B.2 MULTI-AGENT RECURSIVE REASONING POLICY GRADIENT

The section derives a recursive multi-agent policy gradient that conditions opponents’ actions on the current agent’s action. Because opponents’ policies may be inaccessible, it approximates them and updates the agent and opponent models through an EM-style procedure.

  • Recursive policy gradient: The recursive policy gradient conditions the opponents’ joint action distribution on agent i’s action, π−i(a−i|s, ai).This differs from an unconditional opponent policy and incorporates how opponents respond to agent i’s action.
  • Opponent policy inference: When opponents’ policies are unavailable, the method infers a parameterized opponent conditional policy to approximate them.The approximation is denoted φ−i(a−i|s, ai) in the decentralized formulation.
  • Decentralized update: The gradient for agent i is scaled by its action-value estimate Q_i while using the inferred opponent conditional policy.The cited derivation identifies Q_i and the opponent model as components of the decentralized gradient.
  • Optimization procedure: The opponent-policy and value-function updates form an expectation-maximization-style learning procedure.The procedure alternates between fixing the opponent model and updating the agent policy and value-related quantities.
  • Training setting: PR2 does not require opponents’ actual private policies, allowing decentralized recursive policy-gradient training in an off-policy fashion from replay-buffer mini-batches.The learned opponent model is used with samples from memory buffer D rather than requiring opponents’ on-policy or target policies.
  • Opponent policy inference: The opponent conditional policy can be obtained by fitting an approximation whose trajectory distribution has high likelihood under observed behavior, using KL-divergence minimization under local-reward access.The local-reward constraint can affect the approximated opponent model.

D SOFT BELLMAN EQUATION AND SOFT VALUE ITERATION

Under specified single-equilibrium conditions in a symmetric game, the PR2 soft value iteration operator is shown to be a contraction mapping. The section relates this result to soft value-iteration reasoning and the uniqueness of equilibrium payoff.

  • Contraction result: Under a symmetric game with one global equilibrium or saddle equilibrium, the PR2 soft value iteration operator is a contraction mapping.The theorem assumes the equilibrium satisfies one of the stated optimality conditions.
  • Soft value iteration: The PR2 soft value-iteration rules are obtained from the preceding optimal Q-function and policy equations.The operator T is then defined correspondingly.
  • Proof basis: For the stated symmetric-game conditions, the equilibrium payoff is unique, supporting the contraction-mapping argument for soft value iteration.The section connects this uniqueness result to the single-agent soft-value-iteration proof strategy.
Loading 1901.09207v2…