Strategizing against Learners in Bayesian Games
We study repeated two-player games where one of the players, the learner,
employs a no-regret learning strategy, while the other, the optimizer, is a
rational utility maximizer. We consider general Bayesian games, where the
payoffs of both the optimizer and the learner could depend on the type, which
is drawn from a publicly known distribution, but revealed privately to the
learner. We address the following questions: (a) what is the bare minimum that
the optimizer can guarantee to obtain regardless of the no-regret learning
algorithm employed by the learner? (b) are there learning algorithms that cap
the optimizer payoff at this minimum? (c) can these algorithms be implemented
efficiently? While building this theory of optimizer-learner interactions, we
define a new combinatorial notion of regret called polytope swap regret, that
could be of independent interest in other settings.