# Optimal Rates and Efficient Algorithms for Online Bayesian Persuasion

arXiv: https://arxiv.org/abs/2303.01296 · HTML: https://mlsanity.com/paper/2303.01296/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2023.

## Built on by (most cited first, 16 of 16)

- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Efficient Model-agnostic Alignment via Bayesian Persuasion](https://mlsanity.com/paper/2405.18718/) (2024)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [Contractual Reinforcement Learning: Pulling Arms with Invisible Hands](https://mlsanity.com/paper/2407.01458/) (2024)
- [Algorithmic Persuasion Through Simulation](https://mlsanity.com/paper/2311.18138/) (2023)
- [Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals](https://mlsanity.com/paper/2505.23124/) (2025)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Learning in Bayesian Stackelberg Games With Unknown Follower's Types](https://mlsanity.com/paper/2602.00771/) (2026)
- [Make an Offer They Can't Refuse: Grounding Bayesian Persuasion in Real-World Dialogues without Pre-Commitment](https://mlsanity.com/paper/2510.13387/) (2025)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)
- [Meta-Learning for Repeated Bayesian Persuasion](https://mlsanity.com/paper/2603.20408/) (2026)
- [Learning to Persuade Privately Informed Receivers](https://mlsanity.com/paper/2607.28342/) (2026)

## Abstract (arXiv)

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 tilde O(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 tilde O(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 multi-receiver scenario when type reporting is allowed.