Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion

Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, Nicola Gatti
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:2164-2183, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-bernasconi23a, title = {Optimal Rates and Efficient Algorithms for Online {B}ayesian Persuasion}, author = {Bernasconi, Martino and Castiglioni, Matteo and Celli, Andrea and Marchesi, Alberto and Trov\`{o}, Francesco and Gatti, Nicola}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {2164--2183}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/bernasconi23a/bernasconi23a.pdf}, url = {https://proceedings.mlr.press/v202/bernasconi23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion %A Martino Bernasconi %A Matteo Castiglioni %A Andrea Celli %A Alberto Marchesi %A Francesco Trovò %A Nicola Gatti %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-bernasconi23a %I PMLR %P 2164--2183 %U https://proceedings.mlr.press/v202/bernasconi23a.html %V 202 %X 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.
APA
Bernasconi, M., Castiglioni, M., Celli, A., Marchesi, A., Trovò, F. & Gatti, N.. (2023). Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:2164-2183 Available from https://proceedings.mlr.press/v202/bernasconi23a.html.

Related Material