Bayesian Exploration: Incentivizing Exploration in Bayesian Games
  We consider a ubiquitous scenario in the Internet economy when individual
decision-makers (henceforth, agents) both produce and consume information as
they make strategic choices in an uncertain environment. This creates a
three-way tradeoff between exploration (trying out insufficiently explored
alternatives to help others in the future), exploitation (making optimal
decisions given the information discovered by other agents), and incentives of
the agents (who are myopically interested in exploitation, while preferring the
others to explore). We posit a principal who controls the flow of information
from agents that came before, and strives to coordinate the agents towards a
socially optimal balance between exploration and exploitation, not using any
monetary transfers. The goal is to design a recommendation policy for the
principal which respects agents' incentives and minimizes a suitable notion of
regret.
  We extend prior work in this direction to allow the agents to interact with
one another in a shared environment: at each time step, multiple agents arrive
to play a Bayesian game, receive recommendations, choose their actions, receive
their payoffs, and then leave the game forever. The agents now face two sources
of uncertainty: the actions of the other agents and the parameters of the
uncertain game environment.
  Our main contribution is to show that the principal can achieve constant
regret when the utilities are deterministic (where the constant depends on the
prior distribution, but not on the time horizon), and logarithmic regret when
the utilities are stochastic. As a key technical tool, we introduce the concept
of explorable actions, the actions which some incentive-compatible policy can
recommend with non-zero probability. We show how the principal can identify
(and explore) all explorable actions, and use the revealed information to
perform optimally.
