Research map / Bandits and online learning / Online convex optimization and games
Online Bayesian Persuasion Without a Clue
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an explore-then-commit algorithm for online Bayesian persuasion where the sender knows neither the prior nor the receiver's utilities, using signaling-scheme slices to learn receiver best-response regions exactly, achieving Õ(√T) regret with matching lower bounds.
Problem
Online Bayesian persuasion where the sender knows neither the prior over states nor the receiver's utilities, observing only the receiver's best-response action each round.
Approach
Represent signaling schemes by per-signal "slices" (prior-free vectors of probabilities over states), which lets the sender learn separating hyperplanes between receiver best-response regions exactly without splitting prior and utilities; combine a prior-estimation phase, an exact-learning search phase borrowed from Stackelberg games, and an LP-based commit phase.
Key results
- Regret of Õ(binom(d+n, d) n^{3/2} d^3 sqrt(BT)) for the proposed algorithm, sublinear in T.
- Lower bounds show the dependence on number of states d and actions n is tight.
- Sample complexity bounds derived for a related Bayesian persuasion PAC-learning problem.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use slice-based explore-then-commit learning without prior or receiver-utility knowledge | Online Bayesian persuasion · Online Bayesian persuasion | regret: R_T \le \widetilde{\mathcal{O}}\big( \binom{d+n}{d} n^{\nicefrac{3}{2}} d^3 \sqrt {BT} \big) | Helped |
Limitations
- Regret bound scales as binom(d+n,d), exponential in the number of states and actions in general
- Dependence on bit-complexity B of the instance
- Requires exact rational arithmetic for learning separating hyperplanes
Experimental setup
Metrics: cumulative Stackelberg regret
Builds on: Stackelberg learning with unknown follower utilities Bayesian persuasion (Kamenica and Gentzkow)
Closest papers by meaning
- Markov Persuasion Processes: Learning to Persuade From Scratch (NeurIPS 2025 · similarity 0.91)
- Computational Aspects of Bayesian Persuasion under Approximate Best Response (NeurIPS 2024 · similarity 0.91)
- Persuasive Prediction via Decision Calibration (NeurIPS 2026 · similarity 0.91)
- Bayesian Persuasion with Externalities: Exploiting Agent Types (AAAI 2025 · similarity 0.89)
- Learning to Persuade a Biased Receiver (NeurIPS 2026 · similarity 0.89)
- Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.