Research map / Bandits and online learning / Online convex optimization and games

Learning to Persuade a Biased Receiver

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online decision-making with feedback structure · 0 citations (OpenAlex)

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.

Studies repeated Bayesian persuasion against a receiver whose belief updating is a linear mix of prior and Bayesian posterior with unknown bias; proposes safe-exploration algorithms achieving O(log log T) regret with a matching lower bound.

Problem

A sender repeatedly designs signaling schemes to persuade a receiver whose updating strength (bias alpha) is fixed but unknown, observing only the receiver's actions, and must minimize regret versus a full-information optimum.

Approach

Exploit the asymmetric cost of probing: probes approached from the safe side lose only a local utility gap, while overly aggressive probes lose the persuasion entirely, so interval-refinement with squared step sizes shrinks the bias interval doubly exponentially; generalized to finite state/action spaces via moving polytope IC constraints.

Key results

• Safe Exploration achieves O(log log T) regret in the binary setting, versus O(log T) for binary search.
• A matching Omega(log log T) lower bound holds for any sender strategy in the binary instance, hence for the general setting too.
• General Safe Exploration runs in polynomial time and achieves O(log log T) regret for arbitrary finite state/action spaces with bounded utilities.

Surprising findings

• Binary search, the natural approach, is suboptimal: it incurs Theta(log T) regret, whereas probing from the safe side achieves doubly-logarithmic regret.

Limitations

• Matching O(log T) upper bound for jointly unknown prior and bias in the general case remains open.
• Analysis assumes exact action feedback; noisy or partial feedback is not covered.
• Constants are instance-dependent and may be large; asymptotic bounds are pointwise in the instance.

Experimental setup

Metrics: cumulative regret

Baselines: binary search

Builds on: Kamenica and Gentzkow Bayesian persuasion linear belief distortion model Kleinberg and Leighton posted-price lower bound Yao's principle

Closest papers by meaning

• Persuasive Prediction via Decision Calibration (NeurIPS 2026 · similarity 0.90)
• Online Bayesian Persuasion Without a Clue (NeurIPS 2024 · similarity 0.89)
• Markov Persuasion Processes: Learning to Persuade From Scratch (NeurIPS 2025 · similarity 0.88)
• Computational Aspects of Bayesian Persuasion under Approximate Best Response (NeurIPS 2024 · similarity 0.86)
• Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.85)
• Bayesian Persuasion with Externalities: Exploiting Agent Types (AAAI 2025 · similarity 0.85)