Learning to Persuade on the Fly: Robustness Against Ignorance
  We study a repeated persuasion setting between a sender and a receiver, where
at each time $t$, the sender observes a payoff-relevant state drawn
independently and identically from an unknown prior distribution, and shares
state information with the receiver, who then myopically chooses an action. As
in the standard setting, the sender seeks to persuade the receiver into
choosing actions that are aligned with the sender's preference by selectively
sharing information about the state. However, in contrast to the standard
models, the sender does not know the prior, and has to persuade while gradually
learning the prior on the fly.
  We study the sender's learning problem of making persuasive action
recommendations to achieve low regret against the optimal persuasion mechanism
with the knowledge of the prior distribution. Our main positive result is an
algorithm that, with high probability, is persuasive across all rounds and
achieves $O(\sqrt{T\log T})$ regret, where $T$ is the horizon length. The core
philosophy behind the design of our algorithm is to leverage robustness against
the sender's ignorance of the prior. Intuitively, at each time our algorithm
maintains a set of candidate priors, and chooses a persuasion scheme that is
simultaneously persuasive for all of them. To demonstrate the effectiveness of
our algorithm, we further prove that no algorithm can achieve regret better
than $\Omega(\sqrt{T})$, even if the persuasiveness requirements were
significantly relaxed. Therefore, our algorithm achieves optimal regret for the
sender's learning problem up to terms logarithmic in $T$.
