  The combination of deep reinforcement learning and search at both training
and test time is a powerful paradigm that has led to a number of successes in
single-agent settings and perfect-information games, best exemplified by
AlphaZero. However, prior algorithms of this form cannot cope with
imperfect-information games. This paper presents ReBeL, a general framework for
self-play reinforcement learning and search that provably converges to a Nash
equilibrium in any two-player zero-sum game. In the simpler setting of
perfect-information games, ReBeL reduces to an algorithm similar to AlphaZero.
Results in two different imperfect-information games show ReBeL converges to an
approximate Nash equilibrium. We also show ReBeL achieves superhuman
performance in heads-up no-limit Texas hold'em poker, while using far less
domain knowledge than any prior poker AI.
