Research map / Bandits and online learning / Online convex optimization and games
Markov Persuasion Processes: Learning to Persuade From Scratch
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.
Introduces a learning algorithm (OPPS) for Markov persuasion processes where the sender knows nothing about the environment, achieving sublinear regret and violation under full and partial feedback, with a matching lower bound for partial feedback.
Problem
Learning optimal sequential information disclosure (signaling) policies in Markov persuasion processes when the sender knows nothing about transitions, priors, or stochastic rewards of sender and myopic receivers, while keeping receivers persuaded.
Approach
Optimistic linear-programming policy search over occupancy measures, with optimism applied to both sender rewards and incentive-compatibility constraints; under partial feedback, an initial exploration phase of length N|X||Omega||A| visits each triplet to estimate persuasiveness, trading off regret T^alpha against violation T^(1-alpha/2).
Key results
- Under full feedback, OPPS attains regret and violation of order tilde-O(sqrt T).
- Under partial feedback, OPPS attains regret tilde-O(T^alpha) and violation tilde-O(T^(1-alpha/2)) for alpha in [1/2,1].
- A lower bound shows no algorithm can simultaneously achieve R_T=o(T^alpha) and V_T=o(T^(1-alpha/2)), so the trade-off is tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OPPS with full feedback | Markov persuasion processes · MPP, full feedback | regret: R_T \leq \widetilde{\mathcal{O}}\left(L^2|X|\sqrt{T|A||\Omega|\ln \left(\frac{1}{\delta}\right)}\right) | Helped |
| Use OPPS with full feedback | Markov persuasion processes · MPP, full feedback | cumulative violation: V_T \leq \widetilde{\mathcal{O}}\left(L^2|X|\sqrt{T|A||\Omega|\ln \left(\frac{1}{\delta}\right)}\right) | Helped |
| Add an exploration phase that considers each state-outcome-action triplet N times while optimistically accounting for persuasiveness constraints | OPPS under partial feedback · MPP, partial feedback | regret: R_T \leq \widetilde{\mathcal{O}}(T^\alpha) | Mixed |
| Add an exploration phase that considers each state-outcome-action triplet N times while optimistically accounting for persuasiveness constraints | OPPS under partial feedback · MPP, partial feedback | cumulative violation: V_T \leq \widetilde{\mathcal{O}}(T^{1-\nicefrac{\alpha}{2}}) | Mixed |
| Increase exploration through the parameter α | OPPS under partial feedback · MPP, partial feedback | regret: R_T \leq \widetilde{\mathcal{O}}(T^\alpha); V_T \leq \widetilde{\mathcal{O}}(T^{1-\nicefrac{\alpha}{2}}) | Mixed |
| Increase exploration through the parameter α | OPPS under partial feedback · MPP, partial feedback | cumulative violation: R_T \leq \widetilde{\mathcal{O}}(T^\alpha); V_T \leq \widetilde{\mathcal{O}}(T^{1-\nicefrac{\alpha}{2}}) | Mixed |
Surprising findings
- Sublinear regret while being persuasive at every episode with high probability is impossible when the sender does not know receivers' rewards.
Limitations
- Results are theoretical; no empirical experiments are reported in the provided text.
- Violation rather than strict persuasiveness is guaranteed; persuasiveness holds only approximately.
- Assumes loop-free episodic MPP with finite state, action, and outcome sets.
Experimental setup
Metrics: cumulative regret R_T cumulative violation V_T
Baselines: Optimal offline signaling policy via LP (OPT) Prior MPP learning work (Castiglioni et al.)
Builds on: Markov persuasion processes UCRL-style optimism in constrained MDPs occupancy measure LP formulation of MDPs
Closest papers by meaning
- Online Bayesian Persuasion Without a Clue (NeurIPS 2024 · similarity 0.91)
- Persuasive Prediction via Decision Calibration (NeurIPS 2026 · similarity 0.90)
- Learning to Persuade a Biased Receiver (NeurIPS 2026 · similarity 0.88)
- Computational Aspects of Bayesian Persuasion under Approximate Best Response (NeurIPS 2024 · similarity 0.88)
- Bayesian Persuasion with Externalities: Exploiting Agent Types (AAAI 2025 · similarity 0.87)
- 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.