Timezone: »

Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion
Martino Bernasconi · Matteo Castiglioni · Andrea Celli · Alberto Marchesi · Francesco Trovò · Nicola Gatti

Thu Jul 27 01:30 PM -- 03:00 PM (PDT) @ Exhibit Hall 1 #439
Bayesian persuasion studies how an informed sender should influence beliefs of rational receivers that take decisions through Bayesian updating of a common prior. We focus on the online Bayesian persuasion framework, in which the sender repeatedly faces one or more receivers with unknown and adversarially selected types. First, we show how to obtain a tight $\tilde O(T^{1/2})$ regret bound in the case in which the sender faces a single receiver and has bandit feedback, improving over the best previously known bound of $\tilde O(T^{4/5})$. Then, we provide the first no-regret guarantees for the multi-receiver setting under bandit feedback. Finally, we show how to design no-regret algorithms with polynomial per-iteration running time by exploiting type reporting, thereby circumventing known complexity results on online Bayesian persuasion. We provide efficient algorithms guaranteeing a $O(T^{1/2})$ regret upper bound both in the single- and multi-receiver scenario when type reporting is allowed.

Author Information

Martino Bernasconi (Politecnico di Milano)
Matteo Castiglioni (Politecnico di Milano)
Andrea Celli (Bocconi University)
Alberto Marchesi (Politecnico di Milano)
Francesco Trovò (Politecnico di Milano)
Nicola Gatti (Politecnico di Milano)

More from the Same Authors