Policy Regret in Repeated Games
  The notion of \emph{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 \emph{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.
