Learning Rationalizable Equilibria in Multiplayer Games
Authors: Yuanhao Wang
Dingwen Kong
Yu Bai
Chi Jin
Venue: ICLR 2023 poster (2023)
Keywords: Game Theory
Online Learning
Rationalizability

Abstract: A natural goal in multi-agent learning is to learn \emph{rationalizable} behavior, where players learn to avoid any Iteratively Dominated Action (IDA). However, standard no-regret based equilibria-finding algorithms could take exponential samples to find such rationalizable strategies. In this paper, we first propose a simple yet sample-efficient algorithm for finding a rationalizable action profile in multi-player general-sum games under bandit feedback, which substantially improves over the results of Wu et al. We further develop algorithms with the first efficient guarantees for learning rationalizable Coarse Correlated Equilibria (CCE) and Correlated Equilibria (CE). Our algorithms incorporate several novel techniques to guarantee the elimination of IDA and no (swap-)regret simultaneously, including a correlated exploration scheme and adaptive learning rates, which may be of independent interest. We complement our results with a sample complexity lower bound showing the sharpness of our guarantees.

Published as a conference paper at ICLR 2023
LEARNING RATIONALIZABLE EQUILIBRIA IN MULTIPLAYER GAMES
Yuanhao Wang"!, Dingwen Kong",, Yu Bai Chi Jin' Princeton University, *Peking University, SSalesforce Research yuanhad@princetonn. edu, dingwenk@pku. edu, en yu yu.bal@salesforee com, chij@princeton.edl edu
ABSTRACT
A natural goal in multi-agent learning is to learn rationalizable behavior, where players learn to avoid any Iteratively Dominated Action (IDA). However, standard no-regret based equilibria-fnding algorithms could take exponential samples find such rationalizable strategies. In this paper, we first propose simple yet sample-efficient algorithm for finding a rationalizable action profile in multi-player general-sum games under bandit feedback, which substantially improves over the results of Wu et al. (2021). We further develop algorithms with the first efficient guarantees for learning rationalizable Coarse Correlated Equilibria (CCE) and Correlated Equilibria (CE). Our algorithms incorporate several novel techniques to guarantee the climination of IDA and no (swap-)regret simultaneously. including a correlated exploration scheme and adaptive learning rates, which may be of independent interest. We complement our results with a sample complexity lower bound showing the sharpness of our guarantees.
INTRODUCTION
A common objective in multi-agent learning is to find various equilibria, such as Nash equilibria (NE), correlated equilibria (CE) and coarse correlated equilibria (CCE). Generally speaking, a player in equilibrium lacks incentive to deviate assuming conformity of other players to the same equilibrium. Equilibrium learning has been extensively studied in the literature of game theory and online learning, and no-regret based learners can provably learn approximate CE and CCE with both computational and statistical efficiency (Stoltz, 2005;
& Lugosi, 2006).
However, not all equilibria created equal. As shown by Viossat & Zapechelnyuk (2013), CCE can be entirely supported on dominated actions-actions that are worse off than some other strategy in all cireumstances--ve which rational agents should apparently never play. Approximate CE also suffers from similar problem. As shown by Wu et al. (2021. Theorem 1). there are examples where an e-CE always plays iteratively dominated actions actions that would be eliminated when iteratively deleting strictly dominated actions-unled no-regret algorithms are indeed prone finding such seemingly undesirable solutions (Wu et al., 2021). The intrinsic reason behind this is that CCE and approximate CE may not be rationalizable, and existing algorithms can indeed fail to find rationalizable solutions.
is exponentially small. It is also shown that standard
Different from equilibria notions, rationalizability (Bernheim, 1984; Pearce, 1984) looks at the game from the perspective of a single player without knowledge of the actual strategies of other players, and only assumes common knowledge of their rationality. A rationalizable strategy will avoid strictly dominated actions, and assuming other players have also climinated their dominated actions, iteratively avoid strictly dominated actions in the subgame. Rationalizability is central solution concept in game theory (Osborne & Rubinstein, 1994) and has found applications in auctions (Battigalli & Siniscalchi, 2003) and mechanism design (Bergemann et al., 2011).
If an (approximate) equilibrium only employs rationalizable actions, it would prevent irrational behavior such playing dominated actions. Such equilibria arguably more reasonable than
"qqual contribution.

---

Published as a conference paper at ICLR 2023
unrationalizable ones, and constitute stronger solution concept. This motivates us consider the following open question:
Can we efficiently learn equilibria that are also rationalizable?
Despite its fundamental role in multi-agent reasoning, rationalizability is rarely studied from learning perspective until recently, with Wu et al. (2021) giving the first algorithm for learning rationalizable strategies from bandit feedback. However, the problem of learning rationalizable CE and CCE remains a challenging open problem. Due to the existence of unrationalizable equilibria, running standard CE or CCE learners will not guarantee rationalizable solutions. On the other hand, one cannot hope to first identify all rationalizable actions and then find an equilibrium on the subgame, since even determining whether an action is rationalizable requires exponentially many samples (see Proposition 2). Therefore, achieving rati rationalizability and approximate equilibria simultaneously is nontrivial and presents new algorithmic challenges.
In this work, address the challenges above and give positive answer to main question. Our contributions can be summarized as follows:
As a first step, we provide simple yet sample-efficient algorithm for identifying a A- rationalizable action profile under bandit feedback, using only O ( samples in normal- form games with N players, actions per player and a minimum elimination length L. This greatly improves the result of Wu et al. (2021) and is tight up to logarithmic factors when L O().
Using the above algorithm as subroutine, develop exponential weights based algorithms that can provably find A A-rationalizable c-CCE using Ô LNA
A2 NA) samples, and A A-rationalizable min("", ATT samples. To the best of our knowledge, these are the first
e-CE using Ô LNA
N
x
guarantees for learning rationalizable approximate CCE and CE.
We also provide reduction schemes that find A-rationalizable <-CCE/CE using black-box algorithms for e-CCE/CE. Despite having slightly worse rates, these algorithms can directly leverage the progress in equilibria finding, which may be of independent interest.
1.1 RELATED WORK
Rationalizability and iterative dominance elimination. Rationalizability (Bernheim, 1984; Pearce, 1984) a notion that captures rational reasoning in games and relaxes Nash Equilibrium. Rationaliz- ability is closely related to the iterative elimination of dominated actions, which has been focus of game theory research since the 1950s (Luce & Raiffa, 1957). It can be shown that an action rationalizable if and only if it survives iterative elimination of strictly dominated actions (Pearce, 1984). There is also experimental evidence supporting iterative climination of dominated strategies model of human reasoning (Camerer, 2011).
Equilibria learning in games. There a rich literature on applying online learning algorithms to learning equilibria in games. It is well-known that if all agents have no-regret, the resulting empirical average would be an e-CCE (Young, 2004), while all agents have no swap-regret, the resulting empirical average would be e-CE (Hart & Mas-Colell, 2000; Cesa-Bianchi & Lugosi, 2006). Later work continuing this line of research include those with faster convergence rates (Syrgkanis et al., 2015; Chen & Peng, 2020; Daskalakis al., 2021), last-iterate convergence guarantees (Daskalakis & Panageas, 2018; Wei et al., 2020), and extension to extensive-form games (Celli et al., 2020; Bai al., 2022b;a; Song et al., 2022) and Markov games (Song et al., 2021: Jin al., 2021).
Computational and learning aspect of rationalizability. Despite its conceptual importance, ratio- nalizability and iterative dominance elimination are not well studied from computational or learning perspective. For iterative strict dominance elimination in two-player games, Knuth et al. (1988) provided cubic-time algorithm and proved that the problem is P-complete. The weak dominance version of the problem is proven to be NP-complete by Conitzer & Sandholm (2005).
An action is A A-rationalizable if survives iterative elimination of A-dominated actions; c.f. Definition 1. Throoghoou this paper, we use suppress logarithmic factors in N, A, Tr, A. 1, and
For this equivalence to hold, we need to allow dominance by mixed strategies, and correlated beliefs when there are more than two players. These conditions are met the setting of this work.
2

---

Published as a conference paper at ICLR 2023
Hofbauer & Weibull (1996) showed that in class of learning dynamies which includes replicator dynamics - the continuous time variant of Follow-The-Reee Sthe-Reeularzied-Leeee strictly dominated actions vanish over time, while Mertikopoulos & Moustakas (2010) proved similar results for stochastic replicator dynamics; however, neither work provides finite-time guarantees. Co- hen et al. (2017) proved that Hedge eliminates dominated actions in finite time, but did not extend their results to the more challenging case of iteratively dominated actions.
(FTRL), all iteratively
The most related work in literature is the work on learning rationalizable actions by Wu et al. (2021), who proposed the Exp3-DH algorithm to find a strategy mostly supported on rationalizable actions with a polynomial rate. Our Algorithm I accomplishes the same task with a faster rate, while our Algorithms 2 & 3 deal with the more challenging problems of finding e-CE/CCE that are also rationalizable. Although Exp3-DH is based on no-regret algorithm, it does not enjoy regret or weighted regret guarantees and thus does not provably find rationalizable equilibria.
2 PRELIMINARY
An N- N-player normal-form game involves N players whose action space are denoted by A = Ai X AN. and is defined by utility functions u1,-. uu A + [0, 1]. Let A max |Ail denote the maximum number of actions per player, z; denote a mixed strategy of the i-th player (i.e., distribution over A.) and x= denote a (correlated) mixed strategy of the other players (i.e., a distribution over A,)) A₂). We further denote un (11 x-1) == Bac-ama-rsonn Uz(ai, a-i.. We use ASS) denote distribution over the set S.
Learning from bandit feedback We consider the bandit feedback setting where in each round, each player i E [N] chooses an action a E A,, and then observes a random feedback U, E [0. 1] such that E[U; 02, 02, a, = u,(a,, 02 .. an).
2.1 RATIONALIZABILITY
An action a E A; is said to be rationalizable could be the best response to some (possibly correlated) belief of other players' strategies, assuming that they are also rational. In other words, the set of rationalizable actions is obtained by iteratively removing actions that could never be a best response. For finite normal-form games, this is in fact equivalent to the iterative elimination of strictly dominated actions (Osborne & Rubinstein, 1994, Lemma 60.1).
Definition (A Rationalizabilityy) Define
E1 = U fa E A₁ : 3x E A(A)), Va-s; u,(a,a-)) ui a..) A},
which is the set of A-dominated actions for all players. Further define
Es = Ua A: 2x E A(A)), Va
s.t. s.t. a a Ei-1 0, (a,uaa, S 11(1, - }},
which is the set of actions that would be eliminated by the 1-th round. Define L inf Ei+1 Ei} as the minimum elimination length, and Et, as the set of A-iteratively dominated actions (A-IDAs). Actions in A \ Er, are said to be A-rationalizable.
Notice that E1 C ... Ez EL+I. Here A plays similar role as the reward gap for best arm identification in stochastic multi- armed bandits. We will henceforth use A-rationalizability and survival of L. rounds of iterative dominance elimination (IDE) interchangeably" Since one cannot eliminate all the actions of a player, [E, 2 N, which further implies I. S N(A - 1) < NA.
2.2 EQUILIBRIA IN GAMES
We consider three common learning objectives, namely Nash Equilibrium (NE), Correlated Equilib- rium (CE) and Coarse Correlated Equilibrium (CCE).
'See, e.g., the Diamond-In-the-Roughh (DIR) games in Wu et al. (2021, Definition 2) for a concrete example of iterative dominance climination.
'eere we slightly abuse the notation and use A to refer to both the gap and the probability simplex.
A Aternatively one can also define A-rationalizability by the iterative elimination of actions that are never A best response, which mathematically cquivalent Definition (see Appendix A.
3

---

This negative result motivates action profile sample-efficiently Formally, we say action profile (ai...., aN) is rationalizable for all E [N], a, a rationalizable action. This is arguably one of the most fundamental tasks Published as a conference paper at ICLR 2023
Definition 2 (Nash Equilibrium). A strategy profile (#1.-.. ,NN) is an e-Nash equilibrium if u,(2,, 2 =i(a e, Va E A,, Vi E [N].
Definition 3 (Correlated Equilibrium). A correlated strategy II A(A) is an e-correlated equilib- rium if E [N], VΦ: A, + A.
LEAA a-:);;a))u;a;;;; a-1) EEA, Ma a (a))aa(())(()))))) a-i) Definition 4 (Coarse Correlated Equilibrium). A correlated strategy II E ((A) is an E-CCE if Vi [N], Va' E A,
EaEAAs--EA.. a(a,,a a-1) En. EAna-iEA- [a; a-:)u, a_.))) -
When = 0, the above definitions give exact Nash equilibrium, correlated equilibrium, and coarse correlated equilibrium, respectively. It is well known that e-NE are e-CE, and e-CE are e-CCE. Furthermore, we call an e-CCE/CE that only plays A-rationalizable actions a.s. a A-rationalizable C-CCE/CE.
2.3 CONNECTION BETWEEN EQUILIBRIA AND RATIONALIZABILITY
It is known that all actions in the support of exact CE rationalizable (Osborne & Rubinstein, 1994, Lemma 56.2). However, one can easily construct an exact CCE that is supported on dominated (hence, unrationalizable) actions (see e.g. Viossat Zapecheinyuk (2013, Fig. 3)). One might be tempted to suggest that running CE solver immediately finds a CE (and hence CCE) that is also rationalizable. However, the connection between CE and rationalizability becomes quite different when it comes to approximate equilibria, which are inevitable in the presence of noise. As shown by Wu et (2021, Theorem 1), an e-CE can be entirely supported on iteratively dominated action, unless = (22-A). In other words, rationalizability is not guaranteed by running approximate CE solver unless with an extremely high accuracy. Therefore, finding e-CE and CCE that are simuitaneously rationalizable remains challenging open problem.
Since NE a subset of CE, actions in the support of an (exact) NE would also be rationalizable. show that any e-Nash equilibrium is
Unlike approximate CE, for < poly(A, A, 1/N, 1/A)), still mostly supported on rationalizable actions.
Proposition 1. xf (si,... ... .xx) ) is 6-Nash with ZINTA Vi, Prawa; (a E Fr.] < 2he -
Therefore, for two-player zero-sum games, it is possible to run an approximate NE solver and automatically find rationalizable e-NE. However, this method will induce a rather slow rate?, and we will provide a much more efficient algorithm for finding rationalizable e-NE in Section 4.
3 LEARNING RATIONALIZABLE ACTION PROFILES
In order to learn a rationalizable CE/CCE, one might suggest identifying the set of all rationalizable actions, and then learn CE CCE on this subgame. Unfortunately, shown by Proposition 2, even the simpler problem of deciding whether one single action rationalizable is statistically hard.
Proposition 2. For A 0.1, any algorithm that correctly decides whether an action is A- rationalizable with 0.9 probability needs (2AN- samples.
consider an easier task: can we at least find one rationalizable
regarding rationalizability. For mixed-strategy dominance solvable games (Alon et al., 2021), the unique rationalizable action profile will be the unique NE and also the unique CE of the game. Therefore this easier task per se is still of practical importance.
In this section we answer this question in the affirmative. We provide sample-effccient algorithm which finds a rationalizable action profile using only Ô (LNA) samples. This algorithm will also serve an important subroutine for algorithms finding rationalizable CCE/CE in the later sections.
For two-player zero-sum games, the marginals of any CCE is NE NE can be found efficiently. This is true for general games, where finding NE computationally hard and takes (2(2") samples.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Iterative Best Response
1: Initialization: choose a; ()) ....... 1,..., do
A, arbitrarily for all i E [M]
2: for 111,
3: for E [N] do
4: For all a E Ai, play (a, _-= 1) for M times, compute player i's average payoff i (a, ")
5: Set di f arg AA 0; ala
// Computing the empirical best response
return (a) (1) ,N (
(L)
6:
The intuition behind this algorithm is simple: if an action profile a_; can survive rounds of IDE, then its best response a; (i.e,, arg ma U4(a,
a-))) can survive at least I [+ rounds of IDE, since the action a, can only be eliminated after some actions in a-; are eliminated. Concretely, we start (0)) (0) ax. ). In each round / E [L], we compute the (empirical) from an arbitrary action profile (a) ,...,ay
best response of a (1-1) for each E [N], and use those best responses to construct a new action profile (a ..... ( By constructing iterative best responses, we will end up with an action profile that can survive L rounds of IDE, which means surviving any number of rounds of IDE according to the definition of L. The full algorithm is presented in Algorithm 1, for which we have the following theoretical guarantee.
Theorem 3. With M = [116616 [161u(LNA/5) with probability 6, Algorithm returns an action profile
that is A-rationalizable using a total of Ō LNA
samples.
A
Wu et (2021) provide the first polynomial sample complexity results for finding rationalizable action profiles. They prove that the Exp3-DH algorithm is able to find distribution with 1 - fraction supported on A-rationalizable actions using Ō
L و A samples under bandit feedback CA
Compared to their result, our sample complexity bound Ô D(LAN (LNA) on all problem parameters, and our algorithm will output distribution that is fully supported on rationalizable actions (thus has no dependence on ().
has more favorable dependence
We further complement Theorem with sample complexity lower bound showing that the linear dependency on N and A are optimal. This lower bound suggests that the Ô LNA) upper bound is tight up to logarithmic factors when L = O(1), and we conjecture that this is true for general L.
Theorem Evenfor games with L < 2, any algorithm that returns a A A-rationalizable action profile with 0.9 probability needs Ω (NA) samples.
Conjecture 5. The minimax optimal sample complexity for finding A-rationalizable action profile e LNA for games with minimum elimination length L.
LEARNING RATIONALIZABLE COARSE CORRELATED EQUILIBRIA (CCE)
In this section we introduce our algorithm for efficiently learning rationalizable CCEs. The high-level idea is no-regret Hedge-style algorithms for every player, while constraining the strategy inside the rationalizable region. Our algorithm motivated by the fact that the probability of playing a dominated action will decay exponentially
time in the Hedge algorithm for adversarial bandit under full information feedback (Cohen et al., 2017). The full algorithm description provided in Algorithm 2, and here explain several key components in our algorithm design.
Correlated Exploration Scheme. In the bandit feedback setting, standard exponential weights algorithms such EXP3.IX require importance sampling and biased estimators derive high- probability regret bound (Neu, 2015). However, such bias could cause a dominating strategy to lose its advantage. In our algorithm we adopt a correlated exploration scheme, which essentially simulates full information feedback by bandit feedback using N A samples. Specifically, at every time step t,
Wu al. (2021)'s result allows tradc-off between variables via different choice of algorithmic parameters.
However, a 5-1 A factor is unavoidable regardless of choice of parameters.
5

---

Published as a conference paper at ICLR 2023
Algorithm 2 Hedge for Rationalizable e-CCE
1: (4i: ,(y) < Algorithm 1
2: For all i E [N], initialize e." f- 11:-1... a,
3: for = 1,
do
4: for = 1, 1,.,, .N do
5: For all E Ai, play (a, ( for Mr times, compute player i's average payoff u. (a)
6: Set ()) exp Fh Σi= us (())
7: For all t. E [7] and E [N], eliminate all actions in of with probability smaller than then renormalize the vector to simplex as 0.0)
8: output: (E/- 00 10))
the players take turn to enumerate their action set, while the other players fix their strategies according to Hedge. For i E [N] and I. 2 2, we denote 0.0) the strategy computed using Hedge for player in round i. Joint strategy (a, d is played to estimate player i's payoff u ( (a). important to note that such correlated scheme does not require any communication between the players the players can schedule the whole process before the game starts.
Rationalizable Initialization and Variance Reduction. We Algorithm 1, which learns rationalizable action profile, to give the strategy for the first round. By carefully preserving the disadvantage of any iteratively dominated action, keep the iterates inside the rationalizable region throughout the whole learning process. To ensure this for every iterate with high probability, minibatch is used to reduce the variance of the estimator.
Clipping. In the final step, we clip all actions with small probabilities, so that iteratively dominated actions do not appear the output. The threshold is small enough to not affect the e-CCE guarantee.
4.1 THEORETICAL GUARANTEE
In Algorithm 2, we choose parameters in the following manner:
max
In
4mm(/p)
M, =
(4 and min(e.A) 8AN
(I)
A
Note that our learning rate can be bigger than the standard learning rate in FTRL algorithms when t is small. The purpose is to guarantee the rationalizability of the iterates from the beginning of the learning process. As will be shown in the proof, this larger learning rate will not hurt the final rate. We now state the theoretical guarantee for Algorithm 2.
Theorem With parameters chosen as in Eq.(1), after Ō 1- 36, the output strategy of Algorithm 2 is A-rationalizable CCE,Thee total sample complexity is
28 + +) rounds, with probability
Ô LNA +
Remark 7. Due our lower bound (Theorem 4), an ((NA) term unavoidable since learning rationalizable action profile is an easier lask than learning rationalizable CCE. Based on our Conjecture 5, the additional L dependency is also likely to inevitable. On the other hand, learning an c-CCE alone only requires O (1) samples, where as in our bound we have a larger Ō NA, The extra N factor explores at time. Removing this N factor might require more sophisticated exploration methods and utility estimators, which we leave as future work.
22 term.
consequence our correlated exploration scheme in which only one player
Remark 8. Evoking Algorithm/ 1 requires knowledge of L, which may not be available in practice. In that case, an estimate L' may be used in its stead. If L' 2 L (for instance when L' A), we can recover the current rationalizability guarantee, albeit with larger sample complexity scaling with L'. If < L, we can still guarantee that the output policy avoids actions in Ers, which are, informally speaking, actions that would be eliminated with T, levely of reasoning.

---

Published as a conference paper at ICLR 2023
4.1.1 OVERVIEW OF THE ANALYSIS
We give an overview of our analysis of Algorithm below. The full proof is deferred Appendix C.
Step I: Ensure rationalizability. We will first show that rationalizability is preserved at each iterate, i.., actions in Er, will be played with low probability across all iterates. Formally, Lemma 9. With probability at least 26. for all E (T) and all E [N), a, E A, EL, we have ( (a.) p-
Here is defined in (1). Lemma 9 guarantees that, after the clipping in Line of Algorithm 2, the output correlated strategy be A A-rationalizable.
We proceed to explain the main idea for proving Lemma 9. A key observation is that the set of rationalizable actions, U A \ FL, is closed under hest response- for the i-th player, as long as the other players continue to play actions in Uj EE, actions in A,NE, will suffer from excess losses each round in an exponential weights style algorithm. Concretely, for any a_; E (Ili A,) Er and any iteratively dominated action E A, n EL, there always exists E (AA,) such that (z( a-i) Z uz(a;; a-i) A.
With our choice of p Eq. (1), if other players choose their actions from A AE with probability 1 PAN, we can still guarantee an excess loss of (AA) It follows that
Σi=1 (z.) - u,") (a:) 2 l((t)) Sampling Noise.
However, this excess loss be obscured by the noise from bandit feedback when / is small. Note that it is crucial that the statement of Lemma 9 holds for all t due to the inductive nature of the proof.
As solution, we use minibatch of size M, = Ô (T A 1) in the t-th round to reduce the variance of
the payoff estimator v The noise term can now be upper-bounded bounded with Azuma- Hoeff-ng by
Sampling Noise < (v E Mi
s O(tA),
Combining this with our choice of the learning rate gives
Te Σ ( u
> 1.
(2)
By the update rule of the Hedge algorithm, this implies that 0: (((+1) complete the proof of Lemma via induction
(a;) S p. which enables us to
Step 2: Combine with no-regret guarantees, Next, we prove that the output strategy is an e-CCE.
For player E [N], the regret is defined Regret maxx5e((A) Σ (u, (t) 0 (( We can
obtain the following regret bound by standard analysis of FTRL. with changing learning rates.
Lemma 10. For all E [N], Regrety- =Ō (
Here the additive 1/A term is the result of our larger Ö(A-'e-1) learning rate for small t. follows from Lemma that T ( )e) suffices to guarantee that the correlated strategy
+ ( 0 is an (e/2)-CCE. Since pN A = O(e), the clipping step only minorly affects the CCE guarantee and the clipped strategy Σn 1= ) is an e-CCE.
4.2 APPLICATION TO LEARNING RATIONALIZABLE NASH EQUILIBRIUM
Algorithm 2 can also be applied to two-player zero-sum games learn rationalizable e-NE efficiently. Note that in two-player zero-sum games, the marginal distribution of an e-CCE is guaranteed be a 2c-Nash (see, e.g., Proposition 9 in Bai al. (2020).. Hence direct application of Algorithm 2 to a zero-sum game gives the following sample complexity bound. Corollary 11. In two-player zero-sum game, the sample complexity for finding A-rationalizable e-Nash with Algorithm 2 is θ + A).
This result improves over direct application of Proposition 1, which gives Ō ( + () sample
complexity and produces an e-Nash that could still take unrationalizable actions with positive probability.
7

---

Published as a conference paper at ICLR 2023
Algorithm 3 Adaptive Hedge for Rationalizable e-CE
1: (ai. ,ayy) k- Algori thm
2: For all i E [N], initialize 0!!) + (1 (A:p) = atl pl
3: for = 1, ..... do
4: for = 1, ,, do
5: For all A, play (a, ( for M, times, compute player i's average payoff u! (a)
6: For all E Ai, set 0 (-1) exp (vÊ, E'= us (10
7: Find 0!!+2) E ((A)) such that (() EoEa, 0 (abb)(
8: For all L E [7] and i E [N] eliminate all actions in 0.50) with probability smaller than p, then renormalize the vector to simplex as 0!()
EE 8 0 /T
9: output:
LEARNING RATIONALIZABLE CORRELATED EQUILIBRIUM
In order to extend our results on c-CCE c-CE, a natural approach would be augmenting Algorithm with the celebrated Blum-Mansour reduction (Blum & Mansour, 2007) from swap-regret to external regret. In this reduction, one maintains A instances of a no-regret algorithm {Algi.-.. Alga): J. In iteration I, the player would stack the recommendations of the A algorithms as a matrix, denoted by g(t) E AAxAA and compute its eigenvector g(() the randomized strategy in round t. After observing the actual payoff vector u (+), it will pass the weighted payoff vector (a)u(() to algorithm Alg for each a. In this section, we focus on a fixed player i, and omit the subscript when it's clear from the context.
Applying this reduction to Algorithm directly, however, would fail to preserve rationalizability since the weighted loss vector g(t) (a) admit smaller utility gap g(0) (a) Specifically, consider an action b dominated by mixed strategy x. In the payoff estimate of instance a,
Σt= (a) (ulr (x)) AAΣ (a) V ME 2 0,
(3)
which means that we cannot guarantee the elimination of IDAs every round as in Eq (2).
In Algorithm 3, we address this by making Σt= (()) play the role as t, tracking the progress of each no-regret instance separately. In time step I, we will compute the average payoff vector (1) based on (*) samples; then as in the Blum- Mansour reduction, we will update the A instances of Hedge with weighted payoffs g(t) (f) and will use the eigenvector of as the strategy for the next round. The key detail here is our choice of parameters, which adapts to the past strategies {0(=) )=
max A (a)
648 (a)
(a)
78, max { A
(lm(1/p)
A In
P
minfr.a). SAN
(4)
Compared to Eq (1), we are essentially replacing t with an adaptive E (a). We can now improve (3) to
((=))(0)) (b) (x)) 2 2 V
(a)) M
R -- (a).
(5)
This together with our choice of r/ allows us to ensure the rationalizability of every iterate. The full algorithm is presented in Algorithm 3.
We proceed to our theoretical guarantee for Algorithm 3. The analysis framework is largely similar
to that of Algorithm 2. Hoeffding inequality, while swap-regret analysis of the algorithm proves that the average (clipped) strategy indeed an e-CE. The full proof deferred to Appendix D.
Our choice of M( is sufficient to ensure A r-rationalizability via Azuma-
Theorem 12. With parameters in Eq. (4), after T = Ō + A) rounds, with probubility 36, the outpui strategy of Algorithm 3 is a A-rationalizable e-CE The total sample complexity is
δ
LNA
N
A
8

---

Published as a conference paper at ICLR 2023
Algorithm 4 Rationalizable e-CCE via Black-box Reduction
1: (aj, axy) <- Algorithm
2: For all i E [N], initialize A + {
2........ 3: for 1, do
4: Find an e'-CCE II with black-box algorithm O the sub-game I Vi E [N].a, a E As, evaluate uz uz(a/, II_;) for M times and compute average ú, II:;)
5:
6:
for E [N] do
7:
Let a f- arg aaA. 0s (1,
// Computing the empirical best response
A t A U
8:
9: if A = A (1+1) for all allie [N] then
return II
Compared to Theorem 6, our second term has an additional A factor, which quite reasonable considering that algorithms for learning e-CE take Ō(A2E= samples, also A-times larger than the e-CCE rate.
REDUCTION-BASED ALGORITTMSS
While Algorithm 2 and make use of one specific no-regret algorithm, namely Hedge (Exponential Weights), in this section, we show that arbitrary algorithms for finding CCE/CE can be augmented to find rationalizable CCE/CE. The sample complexity obtained via this reduction is comparable with those of Algorithm 2 and 3 when L ( A), but slightly worse when L < N V. Moreover, this black-box approach would enable us to derive algorithms for rationalizable equilibria with more desirable qualities, such last-iterate convergence, when using equilibria-finde algorithms with these properties.
Suppose that use this algorithm in the following "support expansion" manner. We start with a subgame rationalizable actions, which be identified efficiently with Algorithm 1, and call O to find an e-CCE II for the subgame. Next, we check for each i E [NV if the best response to II_; is contained in A₁. not, this means that the subgame's e-CCE may not be an e-CCE for the full game; this case, the best response to II;; would be rationalizable action that we can safely include into the action set. On the other hand, if the best response falls in A, for all i, we can conclude that II also an e-CCE for the original game. The details are given by Algorithm 4, and our main theoretical guarantee is the following.
given a black-box algorithm O that finds c-CCE in arbitrary games. We can then
only
Theorem 13. Algorithm 4 outputs A-rationalizable e- e-CCE with high probability. using at most
N calls to the black-box box CCE algorithm and Ō
N²
additional samples.
Using similar algorithmic techniques, we can develop a reduction scheme for rationalizable c-CE. The detailed description for this algorithm is deferred to Appendix E. Here only state its main theoretical guarantee.
Theorem 14. There exists an algorithm that oulputs A-rationalizable e- e-CE with high probability.
using at most N calls to black-box CE algorithm and Ō N2 A²
min(f+
additional samples.
CONCLUSION
In this paper, we consider two tasks: (1) learning rationalizable action profiles; (2) learning rationaliz- able equilibria. For task 1, we propose conceptually simple algorithm whose sample complexity is significantly better than prior work (Wu et al., 2021). For task 2, we develop the first provably efficient algorithms for learning e-CE and e-CCE that are also rationalizable. Our algorithms are computationally efficient, enjoy sample complexity that scales polynomially with the number of players and are able to avoid iteratively dominated actions completely. Our results rely on several new techniques which might be of independent interests to the community. There remains gap between our sample complexity upper bounds and the available lower bounds for both tasks, closing which is important future research problem.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This work is supported by Office of Naval Research N00014-22-1-2553 Dingwen Kong is partially supported by the elite undergraduate training program of School of Mathematical Sciences Peking University.
REFERENCES
Noga Alon, Kirill Rudov, and Leeat Yariv. Dominance solvability in random games. arXiv preprint arXiv:2105. 10743, 2021.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu. Efficient Ø-regret minimization in extensive-form games via online mirror descent. arXiv preprint arXiv:2205. 2022a.
Yu Bai, Chi Jin, Song Mei, and Tiancheng Yu. Near-optimal learning of extensive-form games with imperfect information. arXiv preprint arXiv:2202.0/752, 2022b.
Pierpaolo Battigalli and Marciano Siniscalchi. Rationalizable bidding in first-price auctions. Games and Economic Behavior, 45(1):38-72, 2003.
Dirk Bergemann, Stephen Morris, and Olivier Tercieux. Rationalizable implementation. Journal of Economic Theory, 146(3):1233-1274 2011.
Douglas Bernheim. Rationalizable strategic behavior. Econometrica: Journal of the Econometric Society, pp. 1007-1028, 1984.
Olivier Binette. A note reverse pinsker inequalities. IEEE Transactions Information Theory, (5(7):409444099 2019.
Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Colin F Camerer. Behavioral game theory: Experiments in strategic interaction. Princeton university press, 2011.
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. Advances in Neural Information Processing Systems, 33: 7722-7732, 2020.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances in Neural Information Processing Systems, 33: 33:18990-18999 2020.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Hedging under uncertainty: Regret
minimization meets exponentially fast convergence. In International Symposium on Algorithmic Game Theory, pp. 252-263. Springer, 2017.
Vincent Conitzer and Tuomas Sandholm. Complexity of (iterated) dominance. Proceedings of the 6th ACM Conference Electronic Commerce, pp. 88-97, 2005.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv: 2018.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-27616, 2021.
Sergiu Hart and Andreu Mas-ColelL. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6875):117711150) 2000.
10

---

Published as a conference paper at ICLR 2023
Josef Hofbauer and Jörgen W Weibull. Evolutionary selection against dominated strategies. Journal of economic theory, 71(2):558-577 1996.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.1455: 2021.
Donald Knuth, Christos Papadimitriou, and John Tsitsikiis. note on strategy elimination in bimatrix games. Operations Research Letters, 7(3):133-107, 1988.
R.D. Luce and H. Raiffa. Games and decisions:
introductions and critical survey. Wiley, 1957.
Panayotis Mertikopoulos and Aris L Moustakas. The emergence of rational behavior in the presence of stochastic perturbations. The Annals of Applied Probubility,
2010.
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Francesco Orabona. A modern introduction online learning. arXiv preprint arXiv: 1rXiv:19/2.132111 2019.
Martin Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
David G Pearce. Rationalizable strategic behavior and the problem of perfection. Econometrica: Journal of the Econometric Society, pp. 1029-1050, 1984.
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with large number of players cample-effiientty arXiv preprint arXiv:2110.04/50 2021.
Ziang Song, Song Mei, and Yu Bai. Sample-efficient learning of correlated equilibria extensive- form games. arXiv preprint 2iiv:2205.00223. 2022.
Gilles Stoltz. Incomplete information and internal regret in prediction of individual sequences. Phl) thesis, Université Paris Sud-Paris X1, 2005.
Vasilis Syrgkanis. Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning games. Advances in Neural Information Processing Systems, 28, 2015.
Yannick Viossat and Andriy Zapechelnyuk. No-regret dynamics and fictitious play. Journal of Economic Theory, 148(2):825-442 2013.
Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained aaddle-point optimization. arXiv preprint axXiv:2006.095/7, 2020.
Jibang Wu, Haifeng Xu, and Fan Yao. Multi-agent learning for iterative dominance climination: Formal barriers and new algorithms. arXiv preprint arXiv:2111.05486, 2021.
H. Peyton Young. Strategic Learning and Limils. Oxford University Press, 11 2004. ISBN 9780199269181.

---

Published as a conference paper at ICLR 2023
A FURTHER DETAILS ON RATIONALIZABILLTY
A.1 EQUIVALENCE SWVER-BEST-RESPOSEER AND STRICT DOMINANCE
It is known that for finite normal form games, rationalizable actions are given by iterated elimination of never-best-respeee
actions, which is in fact equivalent to the iterative elimination of strictly dominated actions (Osbore & Rubinstein, 1994, Lemma 60. 1). Here, for completeness, a proof that the iterative elimination of of actions that are never A-best-response gives the same definition as Definition 1. Notice that it suffices to show that for every subgame, the set of never A best response actions and the set of A-dominated actions are the same.
include
Proposition A.1. Suppose that an action E Ai is never A-best response, i.c. VII.; All A.), Bu E ((A)) such that
Us (a, II-)) S ui (u, II.1) A.
Then is also A-dominated, i.e. Bu A(A)), VII A A All A,)
u: (a, I1-+) S uj (u, 11_1) A.
Proof. That is never A-best response is equivalent to
min max {ur (a, II,)) (u. II_1) $ A.
Ih_1
That is A-doinnated is equivalent to
max min {ue (a, I1;) u4 (u, II_)) S A. I1_1
Equivalence immediately follows from Neumman's minimax theorem.
A.2 PROOF OF PROPOSITION 1
Proof. We prove this inductively with the following hypothesis:
Σ x7(a) 1aa Fa) S 21e
z [N].
REA:
Base case: By the definition c-NE, E [N], Va E A(Ai),
ul(i, x2.) (u(2'x='e))
Note that äf E1 Ar. Fr E ((As) such that Va-i.
u(@āaa.)) & uz a_)) -A A.
Therefore if we choose
x' that is if we play the dominating strategy instead of the dominated action in 2 then
Σ 1/a (aje + E1 Filai(a) x(a),
aEA:
a.A:
un<x' 2 (,(x)
Σ
x((a) 1aa Egj.
acA:
follows that
Σ
=)((a) 1/a Ei] < c A
12

---

Published as a conference paper at ICLR 2023
Induction step:
By the induction hypothesis, Vi E [N],
2/e
Σ aEA.
(a) - E Eg] -
A
Now consider
EnEs, 11 1a Eij 27 (a)ea EnEA, 1/a E Eij 2z (a)
e [N]
which supported on actions on Eg. The induction hypothesis implies [ Therefore vi e [N]. Va A,,
x; S Gle/A.
[i(a, - us (a, xi, 6.Vle
A
Now ä E (F4+1 BB) n Ab, since T-, supported Fg, Fr A(A,) such that u=(ā,T_i) (
It follows that
12Nle
A
u,(ā, up (2, A
S (x(2,x')))
A
Using the same arguments in the base case,
2x
Σ gEA.
(a) 1aa E Est1 \ Eij S
S A
A
12Nl
A
follows that Vi E [N].
2(1 1)c
Σ xa)a) 1la Eit1l acA:
The statement is thus proved via induction on I.
B FIND ONE RATIONALIZABLE ACTION PROFILE
B.1 PROOF OF PROPOSITION 2
Proof. Consider the following N-player game denoted by Go with action set [A]:
us (-) = 0 uN (aw) A laa 1].
(1 (1SiSN-1) 1)
Specifically, a payoff with mean is realized by a skewed Rademacher random variable with 1+u probability on +1 and 1ب" on -1. In game Go. clearly for player N, the action 1 is A-dominated. However, consider the following game, denoted by Ga- (where a" E -1]
2
ui (-) = 0,
< 1) (an 1)
uN (aN) A, UN (1,a-))= = 24 1 = a*).
can be seen that in game Ga-, for player N, the action is not dominated or iteratively strictly dominated. Therefore, suppose that an algorithm O is able to determine whether an action is rationalizable (i.e. not iteratively strictly dominated) with 0.9 accuracy, then its output needs to be False with least 0.9 probability game Go. but True with least 0.9 probability in game G... By Pinsker's 's inequality.
KL(O(G)))IO(G.)) 2 2 0.8² > 1,
where we used (G) to denote the trajectory generated by running algorithm O on game G. Mean- while, notice that Go and G.- is different only when the first N players play a". Denote
13

---

survive at least I rounds of IDE. Recall that a!" is the Published as a conference paper at ICLR 2023
the number of times where the first N 1 players play a" by rt(a). Using the chain rule of Kivdieer,,,ee,
2A
KL(O(G)))OOGG=))) s Eo [n(a")]- KT.
Ber
Ber
2
(a)
x Ec. In(a
(2A)²
T-24
(6) $ 1o, [n((a)]
Here (a) follows from reverse Pinsker's inequality (see e.g. Binette (2019)), while (b) uses the fact
that A < 0.1. This means that for any a" E [AAI"
1
EG. [n(a")]
10
It follows that the expected number of samples when running O on Go is least
AN-
EGD
Σ n(aa)
2
101
N'E[A|N-1
B.2 PROOF THEOREM 3
Proof. We first present the concentration bound. For / E inequality we have that with probability at least 1 LNA
[L]. E [N]. and E A., by Hoeffding's
(In(AN1/8)
A
(a,a, a d (a a -
S
I
M
4
Therefore by union bound have that with probability at least E Ai,
6, for all E [L]. [N] and
A
uu(a, ") ún -1 S
4
We condition this event for the rest of the proof.
We use induction on to prove that for E U {0]. (a ..... ( can survive at least rounds of IDE. The base case for / directly holds. Now assume that the case for 1,2,.... | holds and consider the case of l.
For any [N], show that a ( empirical best response, i.e.
arg max (a, 1--
eEA.
For any mixed strategy vi E ((A.), we have that u:(a!)
(0 u, (2 a (-11)
20, (a a
(1-1)
i (x ( (111)- (1,,
(n(a (00a) i,(a a -(-1))]- ( - ús ((1,,aa-11)) (1-1)))
A
A
20
Since actions in (l-1) can survive least rounds of A-IDE, d cannot be A-dominated by on; in rounds ... Since x; be arbitrarily chosen, a!" can survive at least rounds of A-IDE. We can now ensure that the output (a (L) (L) survives L rounds of AIIDE, which is equivalent to
A rratiioalizabblity (see Definition 1).
The total number of samples used is
LNA
LNA
2
14

---

Published as a conference paper at ICLR 2023
B.3 PROOF OF THEOREM 4
Proof. Without loss of generality, assume that A < 0.1. Consider the following instance where
A AN [A]:
us (a:)) A 1 [a; 1], [a; = uy(as a-1) = A 1a; +] 2A 1 a
(1 j)
(a-
(a
Denote this instance by Ga Additionally, define the following instance Go:
u.(a,)
l[a = 1].
e E [ND
As before, payoff with expectation is realized as random variable with distribution 2Ber ( - can seen that the only difference between Go and Gj.a lies in uy (a, (1) By the KL- divergence chain rule, for any algorithm O,
KL (O(G)) O(G,,)) - 1022 E6. [n(a, = aa,a, (1)
where n(a, a, a-j = (1) denotes the number of times the action profile (a, 1 1N1 is played. Note that in Go. the only action profile surviving two rounds of A-IDE is (1, 1), while in Gjaa- the only rationalizable action profile is (1, I,.. ,1). To guarantee 0.9 accuracy, by
Pinsker's inequality.
(O((G))) -
It follows that Vj [N], 1,
EG, [n(aj a, a. = 2
1 1012
Thus the total expected sample complexity is at least
N(A - 1)
Σ
Eg. [n(a, = a, a. =
104
0> [
C
OMITTED PROOFS IN SECTION 4
We start our analysis by bounding the sampling noise. For player [N], action as E Acs and E [7], we denote the sampling noise as
(a:) := u. (a:) -a)) 0!7))-
We have the following lemma. Lemma C.1. Let 22 denote the event that for all t E [T], i E [N), and a; E A..
Σ cl (a:) 2
IAATT ()) Σ
M
7=1
Then Pr[[1] 2 6.
Proof. Note that Et ( By Azuma-Hoefiding inequality, with probability at least 1 ANT for a fixed [N), [T].
can be written as the sum of Σ M, mean-zero bounded terms.
a, E Ai
1
(a.) $2 In(ANT/0) Σ M
(6)
M
union bound over E [N] 1 [T). 04 E A, proves the statement.
15

---

Published as a conference paper at ICLR 2023
Lemma C.2.
With probability at least
26, for all E [T] and all E [N], E E.n,
(a.) S.
Proof. We condition on the event Q2 defined in Lemma C.I and the success Algorithm 1. We prove the claim by induction in t. The base case for i = 1 holds directly by initialization. Now we assume the case for 1, .,...... ., holds and consider the case of 1.
Consider fixed player i E [N] and iteratively dominated action E A, O Ez. By definition there exists a mixed strategy x; such that for all a_; n Er, 0,
Uz a-+) 2 ui(ac, a-i) A.
Therefore for r E [t]. by the induction hypothesis for T.
Ue (z 2 2 ua Q(7)) + (1 -(1-ANp) A ANp
2 u4(a;; 147) A/2
(7)
Consequently,
Σ u1 (T) (x;) u, (a.))
(2; 017) - us(a;, ((=))(² - 4 In(ANT/0)
(By (6)
M,
==1
14
1
In(ANT/8)
(By (7))
2
M
4
Therefore by our choice of learning rate,
((tt)) (a:) S exp
-1h: Σ
u (x.) u (a:))
T=1
4ln(1/p)
At = p.
S exp
Al
Therefore
(++1) SP
as desired.
Now we turn to the e-CCE guarantee. For player i E [V], recall that the regret is defined as
Regret
max (EA(A.)
(u
)!"))
Lemma C.3. The regret can be bounded as
Regret S o (VInA T In(1/p)
Proof. Note that apart from the choice of ((1), we are exactly running FTRL with learning rates
4lm(1/))
Vin In A/t.
Ti = max
At
16

---

Published as a conference paper at ICLR 2023
which are monotonically decreasing. Therefore following the standard analysis of FTRL (see, e.g.. Orabona (2019, Corollary 7.9)), we have
T
T
max (EA(A.)
u
(+)
,
2+
In A
11
2
1=1
t=1
T
InA
4lm(1/p) At
< + Vin A
2
1=1
=0 (o
In(1/p) ln
A
However, this form of regret cannot directly imply approximate CCE, We define the following expected version regret
Regret
max OE (EA(A.)
Σ (usl, ( ( -(0))
The next lemma bound the difference between these two types of regret
Lemma C.4. The following event 92 holds with probability at least 1 8: for all i E [N]
Regreth* - Regrett/ So
Proof. We denote
2 fei, e,, e|A.1)
Therefore we have
Regret 4. Regreti
(us(-, (60)),0-000
Σ (u (1)
0!99)
max (EA(A:)
max
(EA(A,
(, g( 1,,0 /
(u 8.13)
max #
max AEE.
T
(ui(, ( )0 0050) Σ
(ut 10000- 0!00)
max 8E
1=1
(u 0(4) ui 0 (00))
(8)
0e0;
Note that (u.(, 0l4) u o(t) is a bounded martingale difference sequence. By Azuma- Hoeffding's inequality, for a fixed A O, with probability at least AN.
Σ (ui(- - 00000000000 o00) s so (V(T-In(NAA))
Thus complete the proof by union bound.
Proof of Theorem 6. We condition on event Ω defined Lemma C. event 92 defined in Lemma C.4, and the success Algorithm 1.
Coarse Correlated Equilibria. By Lemma C.3 and Lemma C.4 we know that for all i E [N].
Regret 1.* 50 ( (vnnA.7 AT In(1/p) In
VT-
A
17

---

Published as a conference paper at ICLR 2023
Therefore choosing
[m(NA/6)
In (NVAAco))
T T=
62
Ae
will guarantee that Regrety ** is at most eT/2 for all E [M] In this case the average strategy
E @N ) would be an (E/2)-CCE.
Finally, in the clipping step,
1000) 0 |1 I 2pA S TN for all i E [N]. E (T). Thus for all t E [T].
we have 81== 0
( S 1. which further implies
11 /T
$ 4
Therefore the output strategy
EE 8 ((00) //T is an e-CCE.
Rationalizability By Lemma C.2, a EL n A., 0 (a) S p for all [T]. follows that
(a) 0, i.e., the action would not be the support in the output strategy II = (E 0 )TT
Sample complexity. The total number of full-information queries
64 In (MNNT/))
Σ t=1
Mr S T
A
t=1
<T +
A
1
1
=
+
2
The total sample complexity for CCE learning would then
T
NA 2
NA
NA
M== Ō
+
A
Finally consider the cost of finding one IDE-surviving action profile (Ō claimed rate.
LNA
and we get the
A
D OMITTED PROOFS IN SECTION
Similar to the CCE case we first bound the sampling noise. For action a; As, and [T], we denote the sampling noise as
(())))=;((aa)) ussas, -u:((a 0'7)--
In the CE case, we are interested in the weighted sum of noise Et (a:))87))))) (b:)) which is bounded the following lemma.
Lemma D.1. The following event Gly holds with probability at least 8: for all t E [T] ie [N]. and a E A.
(a)))
(b)))
S
Proof. Note that E'= e(T)) (a, (())) can be written as the sum of E'= MM mean-zero bounded terms. Precisely, there are M/ terms bounded by (b.) By the Azuma-Hoeffding inequality, we
M
18

---

Published as a conference paper at ICLR 2023
have that with probability at least 1
6
A2NT
Σ <)
(a)
22
In(ANT/O /6)
Σ MT
Mi
(b)))
(b.))2
In(ANT/0 /5) Σ
=2
Mi
4
() (b:) Σ
0f20 (bx)
4
5=1
A
(ba)
4 r=1
Therefore by a union bound we complete the proof.
Lemma D.2. With probability at least for all t E [T], all E [N], and all a; E A EL,
0,01 (a.) Sp
Proof. We condition on the event S2 defined in Lemma D.1 and the success of Algorithm 1. We prove the claim by induction in t. The base case for t = 1 holds directly by initialization. Now we assume the case for 1, 2,... , holds and consider the case of ++ 1.
Consider fixed player E [N), an iteratively dominated action a; A O Er. and expert b, By definition there exists a mixed strategy z; such that for all a_; n Ez = 0,
us (= a) 2 ui(a;, a-;) + A
Therefore for T E [t), by induction hypothesis we have
Ue (1i, 0(7) 2 uz (a; ( + (1 A1p)ND) A ANp
2 ui(a;; 037) + A/2
Thus we have
Σ (u, (7) (xx) u,
( (a:)) 0.77 (b:)
Σ (Z,, 8(7)) uai 0(7)) (b.) 4
A Σ (b))
r=1
(f (b:)
A
(ba)
2 T=1
4 r=1
(b.)
By our choice of learning rate,
8 g(t+1)) 1) (aglbe) S
(b,)
(z)) - (xx))
1
T=1
4 4mn(1/p)
A A
( = p.
S eexp
A 1 11 (b)
4
t=1
Therefore we conclude
(lt+))(a)== = Σ 0(++1)) (agbb))) (ba) Sp
D,EA:
19

---

Published as a conference paper at ICLR 2023
Now turn to the e-CE guarantee. For player E [N] recall that the swap-regret is defined as
T
SwapRegret ==
Σ ()))()(())
u4)) (1)
A: A:
bEA:
Lemma D.3. For all i E [N], the swap-regret can be bounded as
(VAln(A)T + Alu(NAT/So))
SwapRegret =
A
Proof. For i E [N], recall that the regret for an expert b E A, is defined as
Regret max oEA.
Σ of
Since (a) EbEA, 0.01 (alb)) (6) for all and all > 1,
Σ
Regret
i.b
Σ
0 (b) (ab)
ΣΣ
0// (b),
max anEd:
BEA:
heA,
BEA;
T
T
(t) (b) (9 (+(b)
Σ
Σ
0.0h (116))/0 u.
max
PEA. A
t=1
t=l
IDEA:
T
T
2
max Σ A
Σ
0 (b)u 12 (o(b)
Σ
(1)
(1)
- 1 12 SwapRegret - 1.
BEA.
now suffices to control the regret of each individual expert. For expert b, we are essentially rumning FTRL with learning rates
4m((1/) A (b)
VAln A
nZ. = max
Vt
which are clearly monotonically decreasing. Therefore using standard analysis of FTRL (see, e.g., Orabona (2019, Corollary 7.9)).
i.b Regret
InA n
Σ
Th 0 (b)2
T In A
Aln A
4ln(1/v)
(00
Σ (b)
t
A
Σ (1)
Thn
T
Aln A
4ln(1/p)
T
+
(b)
( In
A
A
[=1
Here we used the fact that vb E Ai, (12)()) 2 p. and
T
8
El
8 (b)
Σh of
ds
Σ
HEL ( (b)
$1+
(())(()
s
In
(00)
T
S 11 + In
Notice that EoEA, 1 Aln I O(v A Aln(A))). Therefore
Σ Regret 50 (VAln(A)T+ + A)))))/)d))))
SwapRegret S 0(11+ +
(8)
RE.A
20

---

Published as a conference paper at ICLR 2023
Similar to the CCE case,, this form of regret not directly imply approximate CE. We define the following expected version regret
sup Σ 0 u. (((:0) u.(:
SwapRegret
The next lemma bound the difference between these two types of regret
Lemma D.4. The following event D2 has probability at least 1 8: for all E [N].
SwapRegret SwapRegrets 0o (V
.AN
8
Proof. Note that
SwapRegret SwapRegrett
1 .u.(.(())) sup diA.
( - uu (11)
sup
AA
Σ o (0 , uu((,(()) - w
I sup
o:A,
Notice that Elu: ( ui (. and that u ( (10
[-1, Therefore, VΦ A A.,
(o= 0 ( us
(1) a bounded martingale difference sequence. By Azuma-
u
Hoeffding inequality, for a fixed @ A, A, with probability 8',
2 8
cs
2
2T In
By setting 8' = A,) we get with probability - 5/N, VΦ A, + Ao
2AA
1 2AT
S
8
Therefore we complete the proof by union bound over i [N].
Proof of Theorem 12. We condition on event Zg defined Lemma D. event Q4 defined in Lemma D.4, and the success Algorithm 1.
Correlated Equilibrium. By Lemma D.3 and Lemma D.4 we know that for all E [N].
SwapRegret 0o (VAlm(A)) +
Aln(N
[AN
+
AT'n
A
8
Therefore choosing
Aln
AN
Aln (NA)
T
Ac
will guarantee that SwapRegret is at most eT/2 2 for all i E [N]. this case the average strategy Er N ( /T would be c/2-CE.
Finally, in the clipping step,
10 (
002
- 2pA < IN for all i [N], t E [T]. Thus for all E [T].
we have 3 g(0)
< 5. which further implics
8
(1)
8
//T
S
6
21

---

Published as a conference paper at ICLR 2023
Therefore the output strategy IT EE & ( an e-CE.
Rationalizability. By Lemma D.2, if a E Ez n A, 0 (a) S for all / E [7]. It follows that
(a) (a) 0, i.e., the action would not be the support in the output strategy II E 0,0
Sample complexity. The total number of queries is
T
0 (b)
Σ [E ==1
Σ
AM & NAT + E
Σ
0,7
KE[M]
BE 1=1
16N
NAT +
(n(T/p)
A
N
2
2
where we used the fact that
T
T
Σ
+ In
(a)
Finally consider the cost of finding one IDE-surviving action profile (Ō A= claimed rate.
and we get the
E DETAILS FOR REDUCTION ALGORIHTMS
In this section, we present the details for the reduction based algorithm for finding rationalizable CE (Algorithm 5) and analysis of both Algorithm 4 and 5.
E. RATIONALIZABLE CCE VIA REDUCTION
We will choose e' min(e.A)
M 1lm(2NA/6)
3
Lemma E.1. With probability 1- 6, throughout the execution of Algorithmn for every t and i E [N].
df E A.
(a,( II.)) un (a/, -.))
Proof. First, observe that during every iterate of before the algorithm returns, the total support size
Σ (4(h) is increased by at least 1. It follows that the algorithm returns before = N A.
By Hoeffding's inequality,
nE
8 N2
[r[ 11.) u, (d4, > e) < 2xxp
2
Applying union bound over t, i and at proves the statement.
Proof of Theorem 13. Correctness. Since Il is an e-CCE in the subgame 11 AA, (1)
E [N],
Va E (1)
u; (a. iT, & 4 (II) +c.
Because arg max, (a II,)) E Vi E N]. Va E A,
My (a, IT+)) < ú; (a, IT :) 6' < max in (a', -T,++ +e
d'EA(0)
max u; (a' Il 2e'
e'EA(")
(II 36 u, [II
22

---

Published as a conference paper at ICLR 2023
Therefore II is e-CCE in the full game.
Moreover, we claim that for any t, A only contains A-rationalizable actions. This true for with high probability due to our initialization. Suppose that this is true for t. Notice that the only way for action de A is be an empirical best response, which means
(a IT 2 (44, IT,;) - é' max (a, TT,) -
2 max u. II,;) 2é'. aEA:
Since c' < A/2, this means that of is the A-best response to A-rationalizable strategy, and is therefore A-rationalizable. Therefore A (1+1) also only contains A-rationalizable actions. Our claim be thus proven via induction, and it follows that the output strategy is also A-rationalizable.
We conclude that the output strategy is A-rationalizable e-CCE with probability 25 (assuming the event in Lemma E.1 as well as the rationalizability of the initialization).
Sample complexity. By Theorem 3, Line needs Ō LNA A
samples. Since the algorithm returns before / NA, the total number of calls to the black-box oracle O is N A. For each I, the number of samples required is
NA min(
NAM Ō
Combining this with the upper bound t, and the cost for Algorithm gives the total sample complexity bound
2
min A,,
E.2 RATIONALIZABLE CE VIA REDUCTION
The algorithm for CE is quite similar to the one for CCE, except now when testing whether subgame e-CE is an actual e-CE, need to use the conditional distribution 1l,a, which is the conditional distribution of the other players' actions given that player i is told to play a, The detailed description is given in Algorithm 5. Similar to the CCE case, will choose e' = min(t.A)
M (6)
Algorithm 5 RRationalizable e-CE via Black-box Reduction
1: (ai. ,dy) + Algorithm
2: For all E [.V], initialize A(") + {at} for all i [N]
3: for t = 1, do
4: Find an cCCE, II, in the sub-game supported on A
5: vi E [A], a, oe E A,, sample u, (a/, II_//a) for M times and compute average á; (a/, 11_ (a:)
6: f E [N] do
7:
for E ( do
8:
Let
de + arg max (a, I|a:/// Computing the empirical best response acA.
9:
(1+1)
{
if A = A 1++1) for all i e [N] then
10:
return IT
Lemma E.2. With probability 1 8, throughout the execution of Algorithm 4, for every and [N].
d' E A 0, E A,
[ū [á,(a', [T us (a/s M|ss) <
23

---

Published as a conference paper at ICLR 2023
Proof. First, observe that during every iterate of before the algorithm returns, the total support size Σ (A is increased by at least 1. follows that the algorithm returns before N A.
By Hoeffding's inequality,
no
6 N
Pr [1 Ma,;) u, (d,, II]a:] c1 S exp
Applying union bound over I, i, ai and of proves the statement.
Proof. Note that with high probability, the empirical estimates Ú are most c/4 away from the true value U. Since of is the empirical best response, we have
U, U,(4 11;a;) 2 arg max (a, (1(a)) -
acA;
Note that aa is supported on actions that can survive any rounds of e-IDE. Therefore it serves as certificate that df will never be e-eliminated as well.
Lemma E.3. The returned strategy II is an e-CE with probability 1 1 6.
Proof. When the algorithm terminates, for all i [N].
Σ
Il;(;))
max á:(a, [T);)) max ús(a, M(a.) 0. aEA:
aEA!")
G.E.4
Therefore
Σ
[l(a:))
max u, (1 I1|a;) max uaa mla)) s 26'.
acA:;
aEA!")
C,EA!
Since is an c-CE in the reduced game,
(max ua(a, Maas) us(as, ma:)) Sc. (aEa())
Σ (1,(:))
Summing the two inequalities above gives
Σ Ia(a:))
(max ui (; Mlas)) - u.(ai, ([a))))) < 3E', aEAt
arEA!
which proves the statement.
Lemma E.4, For any t, A only contains A-rationalizable actions with probability 25.
Proof. We prove this inductively. This is true for = with probability 1- due to our initialization.
Suppose that this is true for t. Notice that the only way for an action of E A (t++1) is to be an empirical best response, which means for some a;
ua(d,, Illa)) z â,(dl, I1las) é' 2 max & (a, 11[a;) - aeA:
max (a, 11 2 aeA:
Since d' A/2, this means that of is the A-best response to A-rationalizable strategy, and is therefore A-rationalizable. Therefore A (++1) also only contains A-rationalizable actions. Our claim be thus proven via induction, and it follows that the output strategy is also A-rationalizable. I
24

---

Published as a conference paper at ICLR 2023
Proof of Theorem 14. Correctness. By Lemma E.3 and E.4, the output strategy is a A-rationalizable e-CE with probability 1 25 (assuming that the event in Lemma E.2 holds and the rationalizability of the initialization).
Sample complexity. The total sample complexity
LNA
A min A,
+NAXNAM==
+
A²
25


Reviews:
[{"review_id": "oQnKHCDlH1", "reviewer": "Reviewer_TWWs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents algorithms for computing approximately rationalizable correlated equilibria (CE) and coarse correlated equilibria (CCE) in general games. Although these bounds are not shown to be optimal (except of the case where strategies are rationalizable after a constant number of iterated elimination rounds) they are significantly improved over the recent work of Wu et al. Finally the paper provides reduction schemes that find approximately-rationalizable epsilon-CCE/CE using black-box algorithms for epsilon-CE/CCE.", "summary_of_the_review": "A theoretical paper that makes progress on the subject of rationalizability in equilibria. The motivation/applications are somewhat lacking.", "strength_and_weaknesses": "Strengths\n1) The paper makes recent progress on a paper about learning in games\n2) The writing is relatively clear\n\nWeaknesses\n1) The motivation behind finding rationalizable CCE does not seem to be particularly strong. Why is so important for the players to converge to a rationalizable CE/CCE? The proposed algorithms are rather unnatural and although can be used to compute CCE do not provide no-regret guarantees themselves. Hence, one would need a very strong justification of why this specific class of equilibria are particularly desirable. Also, if \"natural\" learning algorithms like Hedge and variants do not reproduce iteratively rationalizable CCE fast isn't this an indication that maybe iterative rationalizability is not a \"natural\" property?\n2) The algorithms are rather impractical to use and result in significant blow-ups e.g. the sampling complexity grows linearly in the number of agents whereas without it there is no dependence on the number of agents.\n3) There are no proposed interesting practical applications of this idea (also no experimental section)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "WuhXi_ueAOf", "reviewer": "Reviewer_xdmb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies learnability of (coarse) correlated and Nash equilibria supported on rationalizable actions in unknown multiplayer normal-form games. After introducing the relevant concepts, the authors derive the first main result: a probabilistic bandit algorithm that identifies a rationalizable action profile using a number of samples inversely quadratic in an elimination reward gap and linear in the number of players (N), maximum number of actions (A), and a minimum number of iterations to eliminate dominated actions. This result serves as a stepping stone to the next two algorithms, finding rationalizable correlated and coarse correlated equilibria with sample complexities extending the action-profile-algorithm with additional (at most quadratic) terms. As a side-product, the authors obtain also a sample complexity of finding rationalizable Nash equilibria in two-player zero-sum games. The last main result consists of two algorithms capable of “rationalizing” an arbitrary black-box algorithm for computing correlated or coarse correlated equilibrium using N*A calls to the black-box and a number of additional samples at most quadratic (in case of coarse correlation) or cubic (in case of standard correlation) in the game’s parameters. ", "summary_of_the_review": "A technically solid paper that may benefit from a more detailed discussion on the consequences of (ir)rationalizability, but otherwise deserves publication, in my opinion. \n\n", "strength_and_weaknesses": "I find this work very well written in terms of both quality of prose and the overall exposition. All notions the authors introduce are well described, and the notation is clear and easily comprehensible. The paper also competently explains how the presented work fits into the literature on the topic. The theory seems solid, I briefly went through the proofs in the appendix and as far as I can tell, they apper to be correct. I especially liked the black-box techniques the authors present. \n\nWhat I am missing a bit in the main text is some more in-depth analysis of the motivation that would highlight the importance of this work, perhaps some illustrative examples … something along the lines of showing what could actually happen in practice if not rationalizable (C)CEa are adopted? What is a possible degradation in terms of utility? I assume I may find some analysis in the cited works, but I can’t shake the feeling of being slightly uncertain of how important this problem truly is.\n\nMy other concern relates to the potential uses of the derived sample complexities and how to estimate them in practice. If I understand this work correctly, the authors work in the bandit setting when the underlying game is unknown. While N and A are given, and delta could be chosen, how could the “L” be computed in the bandit case, given that you need it to run Algorithm 1 (line 2)? Even if the original utilities are fully observable, how difficult is it to compute “L”? If I am not wrong, this definition of strict dominance is with respect to mixed strategies, so calculating “L” corresponds to iteratively resolve the linear programs from the original work by Vincent Conitzer. How difficult is it in contrast to the algorithms presented in this paper? Or is “L” not supposed to be computed in practice? If yes, are there some reasonable bounds on “L” that would allow us to estimate the expected solution quality given some supply of samples?\n\nFinally, just a few nits:\n(i) The introduction presents the sample complexities without explaining at all what delta is.\n(ii) The delta symbol is then further used both as the “reward gap” in the definition of rationalizability and to denote distributions over some set … Is there some connection between the two that would justify the use of the same notation that I am missing?\n(iii) FTRL remains undefined on page 2, I assume this is the follow-the-regularized-leader.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QzVB7CLp82v", "reviewer": "Reviewer_ta5R", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of designing no-regret learning algorithms that provably converge to Coarse Correlated Equilibria (CCEs) and Correlated Equilibria (CEs) that avoid playing actions that are non-rationalizable, i.e., they do not survive iterative elimination od dominated actions. The paper focuses on normal-form games with stochastic payoffs, under the bandit feedback model. First, it provides an algorithm that can be used to learn any rationalizable action profile. Then, it uses such an algorithm as a subroutine to design sample-efficient no-regret learning algorithms for CCEs and CEs. The paper provides two variants of such algorithms: one is based on a modification of the Hedge algorithm, while the other works by using any standard no-regret algorithms as a subroutine, at the expense of achieving \"slightly\" worse regret bounds. The paper also provides a lower bound showing that the sample complexity of the first variant of the algorithms is optimal with respect to the number of players and the number of actions. ", "summary_of_the_review": "I think that this is a good paper, even tough the topic addressed by it is rather narrow. My only concerns are about the novelty of the technical results.", "strength_and_weaknesses": "STRENGTHS\n\n1) The paper studies an interesting problem that is largely overlooked in the literature. While most of the papers focus on learning equilibria in games, with the goal of finding AN (approximate) equilibrium, I believe that focusing on how to learn equilibria with desirable properties is a crucial property for operationalizing equilibrium-learning algorithms in practice.\n\n2) The paper is well written and fairly easy to follow. As far as I am concerned, the technical results are sound.\n\nWEAKNESSES\n\n1) The paper addresses a very specific topic that could be interesting only for a very narrow parto of the ICLR community.\n\n2) The technical tools used to prove the results seem quite standard, or perhaps the authors did not stress sufficiently the technical novelty of their results. \n\nMINOR ISSUES\n\n1) The conditioning inside the expectation at the beginning of Section 2 is not clear.\n2) The notation u_i(x_i,x_{-i)) and u_i(x_i,x_{-I}) has not been formally introduced.\n3) It is not clear how to set L in the algorithms, do you always have to set it to be equal to its maximum value N x A?\n4) The notation with \\theta inside Algorithms 2 and 3 is not clear, I had to re-read them several times in order to grasp the meaning. I think it is better to introduce it in the main text, together with a short description in words.\n5) I would add formal definitions of \\Delta-rationalizable \\epsilon-CE and \\epsilon-CCE.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "23JmVSD2G5", "reviewer": "Reviewer_eq1u", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides an algorithm for learning the rationalizable action profiles for multi-agent games with bandit feedback, based on which another algorithm for learning the approximate rationalizable CE and CCE. Both algorithms are computationally efficient and have been proven to improve significantly compared to prior work in terms of sample complexity.", "summary_of_the_review": "I feel like this is a good paper with novel ideas and solid proof. It considers a critical problem of finding rationalizable equilibria and brings sample-efficient algorithms with theoretical guarantees for multi-agent general-sum games under bandit feedback.\n\n================================\n\nThe authors addressed all my questions, and I tend to keep my original score.", "strength_and_weaknesses": "**Strength:**\n- The authors have proposed a set of algorithms that solves the problem of learning rationalizable equilibrium, which is an important and interesting task.\n- The sample complexity of the proposed method for finding rationalizable action profiles improves significantly compared to the existing Exp3-DH algorithm, and a corresponding lower bound is provided, which shows the near optimality of the algorithm under $L=O(1)$.\n- The paper offers a framework to handle the task of finding rationalizable equilibria by augmenting arbitrary existing algorithms that find the equilibria. Even though there is a slight sacrifice in sample complexity, such a framework can be useful when combined with equilibria-finding algorithms of different properties.\n\n**Weakness:**\n- The matching lower bounds for the learning algorithms on CE and CCE are still missing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster