Bayesian persuasion studies how an informed sender should influence beliefs of rational receivers who 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 Õ(T1/2) regret bound in the case in which the sender faces a single receiver and has partial feedback, improving over the best previously-known bound of Õ(T4/5). Then, we provide the first no-regret guarantees for the multi-receiver setting under partial feedback. Finally, we show how to design no-regret algorithms with polynomial per-iteration running time by exploiting type reporting, thereby circumventing known intractability results on online Bayesian persuasion. We provide efficient algorithms guaranteeing a O(T1/2) regret upper bound both in the single- and the multi-receiver scenario when type reporting is allowed.

Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion

Bernasconi Martino;Castiglioni Matteo;Marchesi Alberto;Trovo Francesco;Gatti Nicola
2023-01-01

Abstract

Bayesian persuasion studies how an informed sender should influence beliefs of rational receivers who 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 Õ(T1/2) regret bound in the case in which the sender faces a single receiver and has partial feedback, improving over the best previously-known bound of Õ(T4/5). Then, we provide the first no-regret guarantees for the multi-receiver setting under partial feedback. Finally, we show how to design no-regret algorithms with polynomial per-iteration running time by exploiting type reporting, thereby circumventing known intractability results on online Bayesian persuasion. We provide efficient algorithms guaranteeing a O(T1/2) regret upper bound both in the single- and the multi-receiver scenario when type reporting is allowed.
2023
Proceedings of Machine Learning Research
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1260585
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact