  Under the uncoupled learning setup, the last-iterate convergence guarantee
towards Nash equilibrium is shown to be impossible in many games. This work
studies the last-iterate convergence guarantee in general games toward
rationalizability, a key solution concept in epistemic game theory that relaxes
the stringent belief assumptions in both Nash and correlated equilibrium. This
learning task naturally generalizes best arm identification problems, due to
the intrinsic connections between rationalizable action profiles and the
elimination of iteratively dominated actions. Despite a seemingly simple task,
our first main result is a surprisingly negative one; that is, a large and
natural class of no regret algorithms, including the entire family of Dual
Averaging algorithms, provably take exponentially many rounds to reach
rationalizability. Moreover, algorithms with the stronger no swap regret also
suffer similar exponential inefficiency. To overcome these barriers, we develop
a new algorithm that adjusts Exp3 with Diminishing Historical rewards (termed
Exp3-DH); Exp3-DH gradually forgets history at carefully tailored rates. We
prove that when all agents run Exp3-DH (a.k.a., self-play in multi-agent
learning), all iteratively dominated actions can be eliminated within
polynomially many rounds. Our experimental results further demonstrate the
efficiency of Exp3-DH, and that state-of-the-art bandit algorithms, even those
developed specifically for learning in games, fail to reach rationalizability
efficiently.
