  Hindsight rationality is an approach to playing multi-agent, general-sum
games that prescribes no-regret learning dynamics and describes jointly
rational behavior with mediated equilibria. We explore the space of deviation
types in extensive-form games (EFGs) and discover powerful types that are
efficient to compute in games with moderate lengths. Specifically, we identify
four new types of deviations that subsume previously studied types within a
broader class we call partial sequence deviations. Integrating the idea of time
selection regret minimization into counterfactual regret minimization (CFR), we
introduce the extensive-form regret minimization (EFR) algorithm that is
hindsight rational for a general and natural class of deviations in EFGs. We
provide instantiations and regret bounds for EFR that correspond to each
partial sequence deviation type. In addition, we present a thorough empirical
analysis of EFR's performance with different deviation types in common
benchmark games. As theory suggests, instantiating EFR with stronger deviations
leads to behavior that tends to outperform that of weaker deviations.
