Timezone: »
Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.
Author Information
Dustin Morrill (University of Alberta; Alberta Machine Intelligence Institute)
I'm a Ph.D. candidate at the [University of Alberta](https://www.ualberta.ca/) and the [Alberta Machine Intelligence Institute (Amii)](https://www.amii.ca/), co-supervised by [Professor Michael Bowling](https://webdocs.cs.ualberta.ca/~bowling/) and [Professor Amy Greenwald](http://cs.brown.edu/people/faculty/amy/) of [Brown University](https://www.brown.edu/). I work on multi-agent learning and scaleable, dependable learning algorithms. I'm a coauthor of [DeepStack](https://www.deepstack.ai) and I created [Cepheus](http://poker.srv.ualberta.ca/)'s [public match interface](http://poker-play.srv.ualberta.ca/). I also manage the [Computer Poker Research Group (CPRG) website](http://poker.cs.ualberta.ca/). I completed a B.Sc. and M.Sc. in computing science at the University of Alberta where my M.Sc was supervised by Michael Bowling. As an undergraduate, I worked with the CPRG to create an [open-source web interface to play against poker bots](https://github.com/dmorrill10/acpc_poker_gui_client) and to develop the 1st-place 3-player Kuhn poker entry in the 2014 [Annual Computer Poker Competition (ACPC)](http://www.computerpokercompetition.org/).
Ryan D'Orazio (Université de Montréal)
Marc Lanctot (DeepMind)
James Wright (University of Alberta)
Michael Bowling (University of Alberta)
Amy Greenwald (Brown)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games »
Wed. Jul 21st 04:00 -- 06:00 PM Room Virtual
More from the Same Authors
-
2023 Poster: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games »
Samuel Sokota · Ryan D'Orazio · Chun Kai Ling · David Wu · Zico Kolter · Noam Brown -
2023 Poster: Settling the Reward Hypothesis »
John Martin · Michael Bowling · David Abel · Will Dabney -
2023 Oral: Settling the Reward Hypothesis »
John Martin · Michael Bowling · David Abel · Will Dabney -
2022 Poster: Simplex Neural Population Learning: Any-Mixture Bayes-Optimality in Symmetric Zero-sum Games »
Siqi Liu · Marc Lanctot · Luke Marris · Nicolas Heess -
2022 Spotlight: Simplex Neural Population Learning: Any-Mixture Bayes-Optimality in Symmetric Zero-sum Games »
Siqi Liu · Marc Lanctot · Luke Marris · Nicolas Heess -
2021 Poster: From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization »
Julien Perolat · Remi Munos · Jean-Baptiste Lespiau · Shayegan Omidshafiei · Mark Rowland · Pedro Ortega · Neil Burch · Thomas Anthony · David Balduzzi · Bart De Vylder · Georgios Piliouras · Marc Lanctot · Karl Tuyls -
2021 Spotlight: From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization »
Julien Perolat · Remi Munos · Jean-Baptiste Lespiau · Shayegan Omidshafiei · Mark Rowland · Pedro Ortega · Neil Burch · Thomas Anthony · David Balduzzi · Bart De Vylder · Georgios Piliouras · Marc Lanctot · Karl Tuyls -
2021 Poster: Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers »
Luke Marris · Paul Muller · Marc Lanctot · Karl Tuyls · Thore Graepel -
2021 Spotlight: Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers »
Luke Marris · Paul Muller · Marc Lanctot · Karl Tuyls · Thore Graepel -
2020 Poster: Fast computation of Nash Equilibria in Imperfect Information Games »
Remi Munos · Julien Perolat · Jean-Baptiste Lespiau · Mark Rowland · Bart De Vylder · Marc Lanctot · Finbarr Timbers · Daniel Hennes · Shayegan Omidshafiei · Audrunas Gruslys · Mohammad Gheshlaghi Azar · Edward Lockhart · Karl Tuyls -
2017 Poster: A Laplacian Framework for Option Discovery in Reinforcement Learning »
Marlos C. Machado · Marc Bellemare · Michael Bowling -
2017 Talk: A Laplacian Framework for Option Discovery in Reinforcement Learning »
Marlos C. Machado · Marc Bellemare · Michael Bowling