Policy Regret in Repeated Games
The notion of policy regret in online learning is a well defined performance measure for the common scenario of adaptive adversaries, which more traditional quantities such as external regret do not take into account. We revisit the notion of policy regret and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play that achieves a favorable regret with respect to one definition must do poorly with respect to the other. We then focus on the game-theoretic setting where the adversary is a self-interested agent. In that setting, we show that external regret and policy regret are not in conflict and, in fact, that a wide class of algorithms can ensure a favorable regret with respect to both definitions, so long as the adversary is also using such an algorithm. We also show that the sequence of play of no-policy regret algorithms converges to a policy equilibrium, a new notion of equilibrium that we introduce. Relating this back to external regret, we show that coarse correlated equilibria, which no-external regret players converge to, are a strict subset of policy equilibria. Thus, in game-theoretic settings, every sequence of play with no external regret also admits no policy regret, but the converse does not hold.
The paper proposes a definition of bounded-memory policy regret, then defines a corresponding equilibrium concept for two-player games, and proves results on (i) convergence (in a non-standard sense) of no-policy-regret strategies to policy equilibria, and (ii) relating policy equilibria to coarse correlated equilibria.  The ideas presented in the paper are clearly motivated: a notion of regret which captures adaptive reaction of the adversary is useful to study. The technical results are also interesting in the context of learning in games.  I found the paper hard to read, however, due to presentation issues. The definitions are often preceded by ambiguous statements. For example: - In the paragraph "Algorithm of the player" line 180: Alg_t is defined as a Alg_t: (A_1 \times A_2)^t \to \Delta A_1, but then redefined as a function from A_2^t \to \Delta A_1 in the full information case, and finally as a distribution over such functions in the bandit setting. In Definition 3.3, the second definition seems to be used. In the same definition, "a possibly random algorithm" is not clearly defined, since the randomness can refer either to randomization over the action set, or to randomization over functions f_t. Line 194: what is meant by "simulating the play of players"? It is possible the reader could guess a definition of \mu, but it would be much better to give a rigorous and unambiguous definition (e.g. in terms of a distribution of an appropriate Markov chain). This entire section should be replaced with an unambiguous mathematical description of the game setting. - In Section 4, the discussion leading to the main definition (Definition 4.5) often involves imprecise statements, e.g. "under reasonable play from all parties" (line 229), "The player believes their opponent might be" (line 231). \epsilon is undefined on line 237. - When switching between distributions over the action set A and the joint policy set F, the presentation can be improved. I believe it would be better to start by defining the equilibrium concept (Definition 4.5) then discuss its interpretation. - \tilde \sigma_a and \tilde \sigma_b (line 336) are not clearly defined.  Besides presentation, several points require discussion and justification: 1) Modifying the definition of policy regret (Definition 3.1): overloading existing definitions has serious drawbacks. In this case it is even harder to justify, since the whole point of defining policy regret is to take into account the adaptivity of the adversary (a point that the paper highlighted several times). The sequence of plays in the proposed definition simply does not reflect a fixed action policy. 2) Justification of the new equilibrium concept (policy equilibrium). Policy equilibrium compares stationary distribution of Markov chains. This needs careful justification and interpretation. For example, do the players care about their stationary distributions because the game is played infinitely often? Why is this a better equilibrium concept than existing concepts for repeated games? How does it generalize to n players? The proposed concept only applies in a context of repeated play (unlike other concepts mentioned in the paper, e.g., Nash equilibria and correlated equilibria). It should be related and compared to other equilibrium concepts of repeated games. 3) The non-uniquess of stationary distributions also raises some issues (the ability of the players to select these distributions). The comment following Definition 4.5 ignores the issue by referring to "the stationary distribution", omitting that there may be more than one.  ================= Thank you for your responses and clarifications, in particular regarding Definition 3.1, this addresses one of my concerns. I agree that Definition 4.5 does not rely on the uniqueness of the stationary distribution, but the point is rather the motivation of this new equilibrium concept: when there are multiple stationary distributions, the play could converge to a different stationary distribution than the one satisfying the guarantees, and this is problematic. As raised during discussion with other reviewers, a better justification could be that one can ensure uniqueness of the stationary distribution at a relatively small cost, by mixing in a uniform distribution. A more careful discussion should be included in the revision.