In Bayesian persuasion, an informed sender strategically discloses
information to a receiver so as to persuade them to undertake desirable
actions. Recently, a growing attention has been devoted to settings in which
sender and receivers interact sequentially. Recently, Markov persuasion
processes (MPPs) have been introduced to capture sequential scenarios where a
sender faces a stream of myopic receivers in a Markovian environment. The MPPs
studied so far in the literature suffer from issues that prevent them from
being fully operational in practice, e.g., they assume that the sender knows
receivers' rewards. We fix such issues by addressing MPPs where the sender has
no knowledge about the environment. We design a learning algorithm for the
sender, working with partial feedback. We prove that its regret with respect to
an optimal information-disclosure policy grows sublinearly in the number of
episodes, as it is the case for the loss in persuasiveness cumulated while
learning. Moreover, we provide a lower bound for our setting matching the
guarantees of our algorithm.

Bayesian persuasion and learning algorithms are used to address Markov persuasion processes where the sender has no prior knowledge, ensuring sublinear growth of regret in the number of episodes and matching the guarantees of the algorithm.

马尔可夫说服流程：从零开始学习说服

Markov Persuasion Processes: Learning to Persuade from Scratch

In today's economy, it becomes important for Internet platforms to consider
the sequential information design problem to align its long term interest with
incentives of the gig service providers. This paper proposes a novel model of
sequential information design, namely the Markov persuasion processes (MPPs),
where a sender, with informational advantage, seeks to persuade a stream of
myopic receivers to take actions that maximizes the sender's cumulative
utilities in a finite horizon Markovian environment with varying prior and
utility functions. Planning in MPPs thus faces the unique challenge in finding
a signaling policy that is simultaneously persuasive to the myopic receivers
and inducing the optimal long-term cumulative utilities of the sender.
Nevertheless, in the population level where the model is known, it turns out
that we can efficiently determine the optimal (resp. $\epsilon$-optimal) policy
with finite (resp. infinite) states and outcomes, through a modified
formulation of the Bellman equation.
Our main technical contribution is to study the MPP under the online
reinforcement learning (RL) setting, where the goal is to learn the optimal
signaling policy by interacting with with the underlying MPP, without the
knowledge of the sender's utility functions, prior distributions, and the
Markov transition kernels. We design a provably efficient no-regret learning
algorithm, the Optimism-Pessimism Principle for Persuasion Process (OP4), which
features a novel combination of both optimism and pessimism principles. Our
algorithm enjoys sample efficiency by achieving a sublinear $\sqrt{T}$-regret
upper bound. Furthermore, both our algorithm and theory can be applied to MPPs
with large space of outcomes and states via function approximation, and we
showcase such a success under the linear setting.

本文提出了一种新的序列信息设计模型 —— 马尔科夫说服过程（MPP），并在在线强化学习环境下设计了一种有效的无后悔策略学习算法（OP4），该算法可高效地确定具有有限或无限状态和结果的优化策略，提高发件人的效用。