Modelling Bounded Rationality in Multi-Agent Interactions by Generalized Recursive Reasoning

1 Introduction

In people's decision making, rationality can often be compromised; it can be constrained by either the difficulty of the decision problem or the finite resources available to each individual's mind. In behavioral game theory, instead of assuming people are perfectly rational, bounded rationality [Simon, 1972] serves as the alternative modeling basis by recognizing such cognitive limitations. Keynes Beauty Contest [Keynes, 1936] is one of the most-cited examples prescribe bounded rationality. In the contest, all players are asked to pick one number from 0 to 100, and the player whose guess is closest to 1◁2 of the average number eventually becomes the winner. In this game, if all the players are perfectly rational, the only choice is to guess 0 (the only Nash equilibrium) because each of them could reason as follows: "if all players guess randomly, the average of those guesses would be 50 (level-0), I, therefore, should guess no more than 1◁2 ⇥ 50 = 25 (level-1), and then if the other players think similarly as me, I should guess no more than 1◁2 ⇥ 25 = 13 (level-2) ...". Such levels of recursions can keep developing infinitely until all players guess the equilibrium 0. This theoretical result from the perfect rationality is however inconsistent with the experimental finding in psychology [Coricelli and Nagel, 2009] which suggests that most human players would choose between 13 and 25. In fact, it has been shown that human beings tend to reason only by 1-2 levels of recursions in strategic games [Camerer et al., 2004]. In the Beauty Contest, players' rationality is bounded and their behaviors are sub-optimal. As a result, it would be unwise to guess the Nash equilibrium 0 at all times.

⇤ First two authors contribute equally.

In multi-agent reinforcement learning (MARL), one common assumption is that all agents behave rationally [Albrecht and Stone, 2018] during their interactions. For example, we assume agents' behaviors will converge to Nash equilibrium [Yang et al., 2018a]. However, in practice, it is hard to guarantee that all agents have the same level of sophistication in their abilities of understanding and learning from each other. With the development of MARL methods, agents could face various types of opponents ranging from joint-action learners [Claus and Boutilier, 1998], factorized Q-learners [Zhou et al., 2019], to the complicated theory-of-mind learners [Rabinowitz et al., 2018]. It comes as no surprise that the effectiveness of MARL models decreases when the opponents act irrationally [Shoham et al., 2003]. On the other hand, it is not desirable to design agents that can only tackle opponents that play optimal policies. Justifications can be easily found in modern AI applications including studying population dynamics [Yang et al., 2018b] or video game designs [Peng et al., 2017; Hunicke, 2005]. Therefore, it becomes critical for MARL models to acknowledge different levels of bounded rationality.

In this work, we propose a novel framework - Generalized Recursive Reasoning (GR2) - that recognizes agents' bounded rationality and thus can model their corresponding sub-optimal behaviors. GR2 is inspired by cognitive hierarchy theory [Camerer et al., 2004], assuming that agents could possess different levels of reasoning rationality during interactions. It begins with level-0 (L0 for short) non-strategic thinkers who do not model their opponents. L1 thinkers are more sophisticated than level-0; they believe the opponents are all at L0 and then act correspondingly. With the growth of k, Lk agents think in an increasing order of sophistication and then take the best response to all possible lower-level opponents. We immerse the GR2 framework into MARL through graphical models, and derive the practical GR2 soft actor-critic algorithm. Theoretically, we prove the existence of Perfect Bayesian Equilibrium in GR2 framework, as well as the convergence of GR2 policy gradient methods on twoplayer normal-form games. Our proposed GR2 actor-critic methods are evaluated against multiple strong MARL baselines on Keynes Beauty Contest, normal-form games, and cooperative navigation. Results justify our theoretical findings and the effectiveness of bounded-rationality modeling.

2 RelatedWork

Modeling opponents in a recursive manner can be regarded as a special type of opponent modeling [Albrecht and Stone, 2018]. Recently, studies on Theory of Mind (ToM) [Goldman and others, 2012; Rabinowitz et al., 2018] explicitly model the agent's belief on opponents' mental states in the reinforcement learning (RL) setting. The I-POMDP framework focuses on building the beliefs about opponents' intentions into the planning and making agents act optimally with respect to such predicted intentions [Gmytrasiewicz and Doshi, 2005]. GR2 is different in that it incorporates a hierarchical structure for opponent modeling; it can take into account opponents with different levels of rationality and therefore can conduct nested reasonings about the opponents (e.g. "I believe you believe that I believe ... "). In fact, our method is most related to the probabilistic recursive reasoning (PR2) model [Wen et al., 2019]. PR2 however only explores the level-1 structure and it does not target at modeling bounded rationality. Importantly, PR2 does not consider whether an equilibrium exists in such a sophisticated hierarchical framework at all. In this work, we extend the reasoning level to an arbitrary number, and theoretically prove the existence of equilibrium as well as the convergence of the subsequent learning algorithms.

Decision-making theorists have pointed out that the ability of thinking in a hierarchical manner is one direct consequence of the limitation in decision makers' informationprocessing power; they demonstrate this result by matching real-world behavioral data with the model that trades off between utility maximization against information-processing costs (i.e. an entropy term applied on the policy) [Genewein et al., 2015]. Interestingly, the maximum-entropy framework has also been explored in the RL domain through inference on graphical models [Levine, 2018]; soft Q-learning [Haarnoja et al., 2017] and actor-critic [Haarnoja et al., 2018] methods were developed. Recently, soft learning has been further adapted into the context of MARL [Wei et al., 2018; Tian et al., 2019]. In this work, we bridge the gap by embedding the solution concept of GR2 into MARL, and derive the practical GR2 soft actor-critic algorithm. By recognizing bounded rationality, we expect the GR2 MARL methods to generalize across different types of opponents thereby showing robustness to their sub-optimal behaviors, which we believe is a critical property for modern AI applications.

3 Preliminaries

The Stochastic Game [Shapley, 1953] is a natural framework to describe the n-agent decision-making process; it is typically defined by the tuple ⌦S↪ A1 ↪ ▷ ▷ ▷ ↪ An ↪ r↪ ▷ ▷ ▷ ↪ rn ↪ P↪ γ ↵, where S represents the state space, Ai and ri (s↪ ai ↪ a-i ) denote the action space and reward function of agent i 2 ¶1↪ ▷ ▷ ▷ ↪ n♦, P : S ⇥ A1 ⇥ · · · ⇥ An ! P(S) is the transition probability of the environment, and γ 2 (0↪ 1] a discount factor of the reward over time. We assume agent i chooses an action ai 2 Ai by sampling its policy ⇡i✓i(ai ♣s) with ✓i being a tuneable parameter, and use a-i = (aj )j6=i to represent actions executed by opponents. The trajectory ⌧ i = ⇥(s1↪ ai1 ↪ a-i 1 )↪ ▷ ▷ ▷ ↪ (sT ↪ aiT ↪ a-i T )⇤ of agent i is defined as a collection of state-action triples over a horizon T .

3.1 The Concept of Optimality inMARL

Analogous to standard reinforcement learning (RL), each agent in MARL attempts to determine an optimal policy maximizing its total expected reward. On top of RL, MARL introduces additional complexities to the learning objective because the reward now also depends on the actions executed by opponents. Correspondingly, the value function of the ith agent in a state s is V i (s; ⇡✓) = E⇡✓↪P hPTt=1 γ t-1 ri (st↪ ait ↪ a-i t )i where (ait ↪ a-i t ) ⇠ ⇡✓ = (⇡i✓i ↪ ⇡-i ✓-i) with ⇡✓ denoting the joint policy of all learners. As such, optimal behavior in a multi-agent setting stands for acting in best response to the opponent's policy ⇡-i ✓-i , which can be formally defined as the policy ⇡i⇤ with V i (s; ⇡i⇤ ↪ ⇡-i ✓-i) ≥ V i (s; ⇡i✓i ↪ ⇡-i ✓-i) for all valid ⇡i✓i . If all agents act in best response to others, the game arrives at a Nash equilibrium [Nash and others, 1950].Specifically, if agents execute the policy of the form ⇡i (ai ♣s) = exp(Qi⇡✓ (s↪ai ↪a-i )) Pa0 exp(Qi⇡✓ (s↪a0 ↪a-i )) - a standard type of policy adopted in RL literatures - with Qi⇡✓ (s↪ ai ↪ a-i ) = ri (s↪ ai ↪ a-i )+γEP [V i (s0 ; ⇡✓)] denoting agent i's Q-function and s0 being a successor state, they reach a Nash-Quantal equilibrium [McKelvey and Palfrey, 1995].

3.2 The Graphical Model of MARL

Since GR2 is a probabilistic model, it is instructive to provide a brief review of graphical models for MARL. In singleagent RL, finding the optimal policy can be equivalently transferred into an inference problem on a graphical model [Levine, 2018]. Recently, it has been shown that such equivalence also holds in the multi-agent setting [Wen et al., 2019; Grau-Moya et al., 2018]. To illustrate, we first introduce a binary random variable Oi t 2 ¶0↪ 1♦ (see Fig. 1) that stands for the optimality of agent i's policy at time t, i.e., p (Oi t = 1♣O-i t = 1↪ ⌧ i t ) / exp (ri (st↪ ait ↪ a-i t )), which suggests that given a trajectory ⌧ t i , the probability of being optimal is proportional to the reward. In the fully-cooperative setting, if all agents play optimally, then agents receive the maximum reward that is also the Nash equilibrium; therefore, for agent i, it aims to maximize p(Oi1:T = 1♣O-i 1:T = 1) as this is the probability of obtaining the maximum cumulative reward/best response towards Nash equilibrium. For simplicity, we omit the value for Ot hereafter. As we assume no

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

· · ·

knowledge of the optimal policies ⇡⇤ and the model of the environment P(S), we treat them as latent variables and apply variational inference [Blei et al., 2017] to approximate such objective; using the variational form of ˆ p(⌧ i ♣Oi1:T ↪ O-i 1:T ) =

[ˆ

t=1 ˆ

t )]⇡✓(ait ↪ a-i

To maximize J(⇡✓), a variant of policy iteration called soft learning is applied. For policy evaluation, the Bellman expectation equation now holds on the soft value function V i (s) = E⇡✓ ⇥Qi (st↪ ait ↪ a-i t ) - log(⇡✓(ait ↪ a-i t ♣st))⇤, with the updated Bellman operator T ⇡Qi (st↪ ait ↪ a-i t ) , ri (st↪ ait ↪ a-i t ) +γEP ⇥softQ(st↪ ait ↪ a-i t )⇤▷ Compared to the max operation in the normal Q-learning, soft operator is softQ(s↪ ai ↪ a-i ) = log Pa Pa-i exp (Q(s↪ ai ↪ a-i )) ⇡ maxai ↪a-i Q (s↪ ai ↪ a-i ). Policy improvement however becomes non-trivial because the Q-function now guides the improvement direction for the joint policy rather than for each single agent. Since the exact parameter of the opponent policy is usually unobservable, agent i needs to approximate ⇡-i ✓-i .

4 Generalized Recursive Reasoning

Recursive reasoning is essentially taking an iterative best response to opponents' policies. level-1 thinking is "I

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

<

l

a

t

e

x

i

s

h

1

_

b

6

4

=

"

(

n

u

)

>

/

know you know how I know". We can represent such recursion by ⇡(ai ↪ a-i ♣s) = ⇡i (ai ♣s)⇡-i (a-i ♣s↪ ai ) where ⇡-i (a-i ♣s↪ ai ) stands for the opponent's consideration of agent i's action ai ⇠ ⇡i (ai ♣s). The unobserved opponent conditional policy ⇡-i can be approximated via a best-fit model ⇢-i φ-i parameterized by φ-i . By adopting ⇡✓(ai ↪ a-i ♣s) = ⇡i✓i (ai ♣s)⇢-i φ-i(a-i ♣s↪ ai ) in ˆ p(⌧ i ♣Oi1:T ↪ O-i 1:T ) in maximizing the Eq. 1, we can solve the best-fit opponent policy by

We provide the detailed derivation of Eq. 2 in Appendix A. Eq. 2 suggests that agent i believes his opponent will act in his interest in the cooperative games. Based on the opponent model in Eq. 2, agent i can learn the best response policy by considering all possible opponent agents' actions: Qi (s↪ ai ) = Ra-i ⇢-i φ-i (a-i ♣s↪ ai )Qi (s↪ ai ↪ a-i ) da-i , and then improve its own policy towards the direction of

4.1 Level-k Recursive Reasoning - GR2-L

Our goal is to extend the recursion to the level-k (k ≥ 2) reasoning (see Fig. 1). In brief, each agent operating at level k assumes that other agents are using k - 1 level policies and then acts in best response. We name this approach GR2-L. In practice, the level-k policy can be constructed by integrating over all possible best responses from lower-level policies

| {z } opponents of level k-1 best responds to agent i of level k-2 When the levels of reasoning develop, we could think of the marginal policies ⇡ik-2 (ai ♣s) from lower levels as the prior and the conditional policies ⇡ik (ai ♣s↪ a-i ) as the posterior. From agent i's perspective, it believes that the opponents will take the best response to its own fictitious action aik-2 that are two levels below, i.e., ⇢-i k-1 (a-i k-1 ♣s) = R ⇢-i k-1 (a-i k-1 ♣s↪ aik-2 )⇡ik-2 (aik-2 ♣s) daik-2 , where ⇡ik-2 can be further expanded by recursively using Eq. 4 until meeting ⇡0 that is usually assumed uniformly distributed. Decisions are taken in a sequential manner. As such, a level-k model transforms the multi-agent planning problem into a hierarchy of nested single-agent planning problems.

4.2 Mixture of Hierarchy Recursive Reasoning - GR2-M

So far, a level-k agent assumes all opponents are at level k-1 during the reasoning process. We can further generalize the model to let each agent believe that the opponents can be much less sophisticated and they are distributed over all lower hierarchies ranging from 0 to k - 1 rather than only the level k - 1, and then find the corresponding best response to such mixed types of agents. We name this approach GR2-M.

Since more computational resources are required with increasing k, e.g., human beings show limited amount of working memory (1 - 2 levels on average) in strategic thinkings [Devetag andWarglien, 2003], it is reasonable to restrict the reasoning so that fewer agents are willing to conduct the reasoning beyond k when k grows large. We thus assume that

Assumption 1. With increasing k, level-k agents have an accurate guess about the relative proportion of agents who are doing lower-level thinking than them.

The motivation of such assumption is to ensure that when k is large, there is no benefit for level-k thinkers to reason even harder to higher levels (e.g. level k + 1), as they will almost have the same belief about the proportion of lower level thinkers, and subsequently make similar decisions. In order to meet Assumption 1, we choose to model the distribution of reasoning levels by the Poisson distribution f(k) = e-λ λk k! where λ is the mean. A nice property of Poisson is that f(k)◁f(k-n) is inversely proportional to kn for 1  n < k, which satisfies our need that high-level thinkers should have no incentives to think even harder. We can now mix all k levels' thinkings ¶ˆ⇡ik ♦ into agent's belief about its opponents at lower levels by

where the term Z = Pkn=1 e-λ λn◁n!. In practice, λ can be set as a hyper-parameter, similar to TD-λ [Tesauro, 1995].

Note that GR2-L is a special case of GR2-M. As the mixture in GR2-M is Poisson distributed, we have f(k-1) f(k-2) = λ k-1 ; the model will bias towards the k - 1 level when λ ≫ k.

4.3 Theoretical Guarantee of GR2Methods

Recursive reasoning is essentially to let each agent take the best response to its opponents at different hierarchical levels. A natural question to ask is does the equilibrium ever exist in GR2 settings? If so, will the learning methods ever converge?

Here we demonstrate our theoretical contributions that 1) the dynamic game induced by GR2 has Perfect Bayesian Equilibrium [Levin and Zhang, 2019]; 2) the learning dynamics of policy gradient in GR2 is asymptotically stable in the sense of Lyapunov [Marquez, 2003].

Theorem 1. GR2 strategies extend a norm-form game into extensive-form game, and there exists a Perfect Bayesian Equilibrium (PBE) in that game.

Proof (of sketch). See Appendix C for the full proof. We can extend the level-k reasoning procedures at one state to an extensive-form game with perfect recall. We prove the existence of PBE by showing both the requirements of sequentially rational and consistency are met. ⌅

Theorem2. In two-player normal-form games, if these exist a mixed strategy equilibrium, under mild conditions, the convergence of GR2 policy gradient to the equilibrium is asymptotic stable in the sense of Lyapunov.

Algorithm 1 GR2 Soft Actor-Critic Algorithm

1: Init: λ↪ k and (learning rates). 2: Init: ✓i ↪ φ-i ↪ !i for each agent i. ¯!i !i , Di ;. 3: for each episode do 4: for each step t do 5: Agents take a step according to ⇡i✓i ↪k (s) or ⇡i↪λ ✓i ↪k (s). 6: Add experience (s↪ ai ↪ a-i ↪ ri ↪ s0 ) to Di . 7: for each agent i do 8: Sample a batch ¶(sj ↪ aij ↪ a-i j ↪ rij ↪ s0j )♦Mj=0 ⇠ Di . 9: Roll out policy to level k via GR2-L/M to get ai0 j and record inter-level results (ai0 j↪k ↪ a-i0 j↪k-1 ↪ · · · ). 10: Sample a-i0 j ⇠ ⇢-i φ-i (·♣s0j ↪ ai0 j ). 11: !i !i - Qi ˆr!iJQi(!i )▷ 12: ✓i ✓i - ⇡i ˆr✓i ⇣J⇡ik (✓i ) +J⇡i˜k (✓i )⌘ ▷ 13: φ-i φ-i - ⇢-i ˆrφ-iJ⇢-i(φ-i )▷ 14: end for 15: ¯!i ¯!!i + (1- ¯!)¯!i ▷ 16: end for 17: end for

Proof (of sketch). See Appendix D for the full proof. In the two-player normal-form game, we can treat the policy gradient update as a dynamical system. Through Lyapunov analysis, we first show why the convergence of level-0 method, i.e. independent learning, is not stable. Then we show that the level-k method's convergence is asymptotically stable as it accounts for opponents' steps before updating the policy. ⌅

Proposition 1. In both GR2-L &GR2-Mmodel, if the agents play pure strategies, once level-k agent reaches a Nash Equilibrium, all higher-level agents will follow it too.

Proof. See Appendix E for the full proof.

⌅

Corollary 1. In GR2 setting, higher-level strategies weakly dominate lower-level strategies.

5 Practical Implementations

Computing the recursive reasoning is computationally expensive. Here we first present the GR2 soft actor-critic algorithm with the pseudo-code in Algo. 1, and then introduce the compromises we make to afford the implementation.

5.1 GR2 Soft Actor-Critic

For policy evaluation, each agent rolls out the reasoning policies recursively to level k by either Eq. 4 or Eq. 5, the parameter !i of the joint soft Q-function is then updated via minimizing the soft Bellman residual JQi (!i ) = EDi [ 12 (Qi!i (s↪ ai ↪ a-i ) - ˆQi (s↪ ai ↪ a-i ))2 ] where Di is the replay buffer storing trajectories, and the target ˆQi goes by ˆQi (s↪ ai ↪ a-i ) = ri (s↪ ai ↪ a-i ) + γEs0⇠P[V i (s0 )]. In computing V i (s0 ), since agent i has no access to the exact opponent policy ⇡-i ✓-i , we instead compute the soft Qi (s↪ ai ) by marginalizing the joint Qfunction via the estimated opponent model ⇢-i φ-i by Qi (s↪ ai ) = log R ⇢-i φ-i (a-i ♣s↪ ai ) exp (Qi (s↪ ai ↪ a-i )) da-i ; the value function of the level-k policy ⇡ik (ai ♣s) then comes as V i (s) = Eai⇠⇡ik ⇥Qi (s↪ ai ) - log⇡ik (ai ♣s)⇤ ▷ Note that ⇢-i φ-i at the same time is also conducting recursive reasoning against agent i in the format of Eq. 4 or Eq. 5. From agent i's perspective however, the optimal opponent model ⇢-i still follows Eq. 2 in the multi-agent soft learning setting. We can therefore update φ-i by minimizing the KL, J⇢-i (φi ) = DKL ⇥⇢-i φ-i (a-i ♣s↪ ai )k exp (Qi!i (s↪ ai ↪ a-i ) - Qi!i (s↪ ai )) ⇤▷ We maintain two approximated Q-functions of Qi!i (s↪ ai ↪ a-i ) and Qi!i(s↪ ai ) separately for robust training, and the gradient of φ-i is computed via SVGD [Liu and Wang, 2016].

Table 1: The Converging Equilibrium on Keynes Beauty Contest.

RECURSIVE DEPTH		LEVEL 3	LEVEL 2	LEVEL 1			LEVEL 0
EXP. SETTING	NASH	GR2-L3	GR2-L2	GR2-L1	PR2	DDPG-TOM	MADDPG	DDPG-OM	MASQL	DDPG
p = 0▷7↪ n = 2	0▷0	0▷0	0▷0	0▷0	4▷4	7▷1	10▷6	8▷7	8▷3	18▷6
p = 0▷7↪ n = 10	0▷0	0▷0	0▷1	0▷3	9▷8	13▷2	18▷1	12▷0	8▷7	30▷2
p = 1▷1↪ n = 10	100▷0	99▷0	94▷2	92▷2	64▷0	63▷1	68▷2	61▷7	87▷5	52▷2

Finally, the policy parameter ✓i for agent i can be learned by improving towards what the current Q-function Qi!i (s↪ ai ) suggests, as shown in Eq. 3. By applying the reparameterization trick ai = f✓i(✏; s) with ✏ ⇠ N(0↪ I), we have J⇡ik (✓i ) = Es↪aik ↪✏ [log ⇡i✓i ↪k (f✓i (✏; s)♣s)-Qi!i (s↪ f✓i (✏; s))]▷

Note that as the agents' final decision comes from the best response to all lower levels, we would expect the gradient of @J⇡ik ◁@✓i to be propagated from all higher levels during training.

5.2 Approximated Best Response via Deterministic Policy

As the reasoning process of GR2 methods involve iterated usages of ⇡ik (ai ♣s↪ a-i ) and ⇢-i k (a-i ♣s↪ ai ), should they be stochastic, the cost of integrating possible actions from lowerlevel agents would be unsustainable for large k. Besides, the reasoning process is also affected by the environment where stochastic policies could further amplify the variance. Considering such computational challenges, we approximate by deterministic policies throughout the recursive rollouts, e.g., the mean of a Gaussian policy. However, note that the highestlevel agent policy ⇡ik that interacts with the environment is still stochastic. To mitigate the potential weakness of deterministic policies, we enforce the inter-level policy improvement. The intuition comes from the Corollary 1 that higher-level policies should perform better than lower-level policies against the opponents. To maintain this property, we introduce an auxiliary loss J⇡i˜k (✓i ) in training ⇡i✓i (see Fig. 5 in Appendix

As we later show in Fig. 2a, such auxiliary loss plays a critical role in improving the performance.

5.3 Parameter Sharing across Levels

We further assume parameter sharing for each agent during the recursive rollouts, i.e., ✓k = ✓k+2 for all ⇡i✓k and ⇢-i ✓k . However, note that the policies that agents take at different levels are still different because the inputs in computing highlevel policies depend on integrating different outputs from low-level policies as shown in Eq. 4. In addition, we have the constraint in Eq. 6 that enforces the inter-policy improvement. Finally, in GR2-M setting, we also introduce different mixing weights for each lower-level policy in the hierarchy (see Eq. 5).

6 Experiments

We start the experiments 1 by elaborating how the GR2 model works on Keynes Beauty Contest, and then move onto the normal-form games that have non-trivial equilibria where common MARL methods fail to converge. Finally, we test on the navigation task that requires effective opponent modeling.

We compare the GR2 methods with six types of baselines including Independent Learner via DDPG [Lillicrap et al., 2015], PR2 [Wen et al., 2019], multi-agent soft-Q (MASQL) [Wei et al., 2018], and MADDPG [Lowe et al., 2017]. We also include the opponent modeling [He et al., 2016] by augmenting DDPG with an opponent module (DDPG-OM) that predicts the opponent behaviors in future states, and a theory-of-mind model [Rabinowitz et al., 2018] that captures the dependency of agent's policy on opponents' mental states (DDPG-ToM). We denote k as the highest level of reasoning in GR2-L/M, and adopt k = ¶1↪ 2↪ 3♦↪ λ = 1▷5. All results are reported with 6 random seeds. We leave the detailed hyper-parameter settings and ablation studies in Appendix F due to space limit.

6.1 Keynes Beauty Contest

In a Keynes Beauty Contest (n↪ p), all n agents pick a number between 0 and 100, the winner is the agent whose guess is closest to p times the average number. The reward is set as the absolute difference.

In reality, higher-level thinking helps humans to get close to the Nash equilibrium of Keynes Beauty Contest (see Introduction). To validate if higher level-k model would make multi-agent learning more effective, we vary different p and n values and present the self-play results in Table. 1. We can tell that the GR2-L algorithms can effectively approach the equilibrium while the other baselines struggle to reach it. The only exception is 99▷0 in the case of (p = 1▷1↪ n = 10), which we believe is because of the saturated gradient from the reward.

We argue that the synergy of agents' reaching the equilibria in this game only happens when the learning algorithm is able to make agents acknowledge different levels of rationality. For example, we visualize the step-wise reasoning outcomes of GR2-L3 in Fig. 3. During training, the agent shows ability to respond to his estimation of the opponent's action by guessing a smaller number, e.g., in step 400, 19▷98 < 25▷34 and 17▷62 < 20▷76. Even though the opponent estimation is not accurate yet (20▷76 6= 19▷98 ⇥ 1▷1), the agent performance can still be improved as the recursive level increases, the opponent's guessing number will become smaller, in this case, 20▷76 < 25▷34. Following this logic, both agents finally reach 0. In addition, we find that in (p = 0▷7↪ n = 2), GR2-L1 is soon followed by the other higher-level GR2 models once it reaches the equilibrium; this is in line with the Proposition 1.

1 The experiment code and appendix are available at https://github. com/ying-wen/gr2

To evaluate the robustness of GR2 methods outside the self-play context, we make each GR2 agent play against all the other six baselines by a round-robin style and present the averaged performance in Fig. 2b. GR2-M models outperform all the other models by successfully guessing the right equilibrium, which is expected since GR2-M is by design capable of considering different types of opponents.

Finally, we justify the necessity of adopting the auxiliary loss of Eq. 6 by Fig. 2a. As we simplify the reasoning rollouts by using deterministic policies, we believe adding the auxiliary loss in the objective can effectively mitigate the potential weakness of policy expressiveness and guide the joint Q-function to a better direction to improve the policy ⇡ik .

6.2 Normal-formGames

We further evaluate GR2 methods on two normal-form games: Rotational Game (RG) and Stag Hunt (SH). The reward matrix

SH has two equilibria (S, S) that is Pareto optimal and (P, P) that is deficient.

In RG, we examine the effectiveness that level-k policies can converge to the equilibrium but level-0 methods cannot. We plot the gradient dynamics of RG in Fig. 4a. level-0 policy, represented by independent learners, gets trapped into the looping dynamics that never converges, while GR2-L policies can converge to the center equilibrium, with higher-level policy allowing faster speed. These empirical findings in fact match the theoretical results on different learning dynamics demonstrated in the proof of Theorem 2.

To further evaluate the superiority of level-k models, we present Fig. 4b that compares the average reward on the SH game where two equilibria exist. GR2 models, together with PR2 and DDPG-ToM, can reach the Pareto optima with the maximum reward 4, whereas other models are either fully trapped in the deficient equilibrium or mix in the middle. SH is a coordination game with no dominant strategy; agents choose between self-interest (P, P) and social welfare (S, S). Without knowing the opponent's choice, GR2 has to first anchor the belief that the opponent may choose the social welfare to maximize its reward, and then reinforce this belief by passing it to the higher-level reasonings so that finally the trust between agents can be built. The level-0 methods cannot develop such synergy because they cannot discriminate the self-interest from the social welfare as both equilibria can saturate the value function. On the convergence speed in Fig. 4b, as expected, higher-level models are faster than lower-level methods, and GR2-M models are faster than GR2-L models.

6.3 Cooperative Navigation

We test the GR2 methods in more complexed Particle World environments [Lowe et al., 2017] for the high-dimensional control task of Cooperative Navigation with 2 agents and 2 landmarks. Agents are collectively rewarded based on the proximity of any one of the agents to the closest landmark while penalized for collisions. The comparisons are shown in Fig. 4c where we report the averaged minimax-normalized score. We compare both the self-play performance and the averaged performance of playing with the other 10 baselines one on one. We notice that the GR2 methods achieve critical advantages over traditional baselines in both the scenarios of self-play and playing against others; this is line with the previous findings that GR2 agents are good at managing different levels of opponent rationality (in this case, each opponent may want to go to a different landmark) so that collisions are avoided at maximum. In addition, we can find that all the listed models show better self-play performance than that of playing with the others; intuitively, this is because the opponent modeling is more accurate during self-plays.

7 Conclusion

We have proposed a new solution concept to MARL - generalized recursive reasoning (GR2) - that enables agents to recognize opponents' bounded rationality and their corresponding sub-optimal behaviors. GR2 establishes a reasoning hierarchy among agents, based on which we derive the practical GR2 soft actor-critic algorithm. Importantly, we prove in theory the existence of Perfect Bayesian Equilibrium under GR2 setting as well as the convergence of the policy gradient methods on the two-player normal-form games. A series of experimental results justified the advantages of GR2 methods over strong MARL baselines on modeling different opponents.