  No-regret learners seek to minimize the difference between the loss they
cumulated through the actions they played, and the loss they would have
cumulated in hindsight had they consistently modified their behavior according
to some strategy transformation function. The size of the set of
transformations considered by the learner determines a natural notion of
rationality. As the set of transformations each learner considers grows, the
strategies played by the learners recover more complex game-theoretic
equilibria, including correlated equilibria in normal-form games and
extensive-form correlated equilibria in extensive-form games. At the extreme, a
no-swap-regret agent is one that minimizes regret against the set of all
functions from the set of strategies to itself. While it is known that the
no-swap-regret condition can be attained efficiently in nonsequential
(normal-form) games, understanding what is the strongest notion of rationality
that can be attained efficiently in the worst case in sequential
(extensive-form) games is a longstanding open problem. In this paper we provide
a positive result, by showing that it is possible, in any sequential game, to
retain polynomial-time (in the game tree size) iterations while achieving
sublinear regret with respect to all linear transformations of the mixed
strategy space, a notion called no-linear-swap regret. This notion of hindsight
rationality is as strong as no-swap-regret in nonsequential games, and stronger
than no-trigger-regret in sequential games -- thereby proving the existence of
a subset of extensive-form correlated equilibria robust to linear deviations,
which we call linear-deviation correlated equilibria, that can be approached
efficiently.
