Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning

To provide a formal foundation for the study of sequential information design, we introduce the Markov persuasion process (MPP), where a sender, with informational advantage, seeks to persuade a stream of myopic receivers to take actions that maximize the sender’s cumulative utility in a finite-horizon Markovian environment with varying prior and utility functions. We need to address a key challenge regarding the planning problem in MPPs; specifically, how to find persuasive signaling policies that are also optimized for the sender’s long-term objective. Moreover, in face of the uncertainty for both the environment and receivers, there is a dilemma that the optimal policy based on estimated prior is not necessarily persuasive and thus cannot induce the desired trajectory, whereas a full information revelation policy is always persuasive but usually leads to suboptimal cumulative utility. So the reinforcement learning algorithm in MPPs has to ensure optimality under the premise of robust persuasiveness. This makes our algorithm design non-trivial and regret analysis highly challenging.

We show how to surmount these analysis and design challenges, and present a no-regret learning algorithm, which we refer to as Optimism-Pessimism Principle for Persuasion Process (OP4), that provably achieves a $\widetilde{O}\big{(}\sqrt{d_{\phi}^{2}d_{\psi}^{3}H^{4}T}\big{)}$ regret with high probability, where $d_{\phi},d_{\psi}$ are dimensions of the feature spaces, $H$ is the horizon length in each episode, $T$ is the number of episodes, and $\widetilde{O}(\cdot)$ hides logarithmic factors as well as problem-dependent parameters. To establish this result, in Section 3.3 we start by constructing a modified formulation of the Bellman equation that can efficiently determine the optimal (resp. $\epsilon$-optimal) policy with finite (resp. infinite) states and outcomes. Section 4.2 then considers the learning problem, in particular the design of the OP4 that adopts both the optimistic principle in utility estimation to incentivize exploration and the pessimism principle in prior estimation to prevent a detrimental equilibrium for the receiver. In Sections 4.3 and 4.4, we showcase OP4 in the tabular MPPs and contextual Bayesian persuasion problem, respectively, both of which are practical special cases of MPPs. In Section 5, we then generalize these positive results to MPPs with large outcome and state spaces via linear function approximation and generalized linear models.

In summary, our contributions are threefold. At the conceptual level, we identify the need for sequential information design in real-world problems and accordingly formulate a novel model, the MPP, to capture the misaligned incentives between the (sequential) decision makers and information possessors. At the methodological level, our key insight is a new algorithmic principle—optimism to encourage exploration and pessimism to induce robust equilibrium behavior. Finally, at the technical level, we develop a novel regret decomposition tailored to this combination of optimism and pessimism in the design of online learning algorithms. The fact that the combined optimism-pessimism concept can still lead to $O(\sqrt{T})$ regret for strategic setups was not clear before our new regret decomposition lemma. We expect this design principle and our proof techniques can be useful for other strategic learning problems.

Our work is built on the foundation of information design and reinforcement learning. We refer the readers to Section 2.1 and 2.2 for background and formal introductions. Here we focus on the technical and modeling comparisons with related work from dynamic Bayesian persuasion and efficient reinforcement learning.

Dynamic Bayesian persuasion. Starting from seminal work by Kamenica and Gentzkow [26], the study of Bayesian persuasion looks at the design problem to influence an uninformed decision maker through strategic information revelation. Many variants of this model have been studied, with applications in security, advertising, finance, etc. [44, 54, 21, 6]. More recently, several dynamic Bayesian persuasion frameworks have been proposed to model the long-term interest of the sender. Many papers [16, 45, 17, 29] consider the setting where the sender observes the evolving states of a Markov chain, seeks to influence the receiver’s belief of the state through signaling and thereby persuade him to take certain actions. In contrast to our setting, at each round, the receiver’s action has no influence on the evolution of the Markov process and thus can only maximizes his utility on his belief of current state, given all the historical signals received from the sender. In Ely [16], Farhadi and Teneketzis [17], the Markov chain has two states (one is absorbing): the receiver is interested in detecting the jump to the absorbing state, whereas the sender seeks to prolong the time to detection of such a jump. Renault et al. [45] shows a greedy disclosure policy that ignores its influence to the future utility can be optimal in Markov chain with special utility functions. Lehrer and Shaiderman [29] characterize optimal strategies under different discount factors as well as the optimal values the sender could achieve. Closer to our model is that of Gan et al. [19]—we both assume the Markov environment with state transition influenced by receiver’s action, as well as a separate persuasion state drawn from a prior independent of receiver’s action. However, Gan et al. [19] focus on the planning problem for the infinite-horizon MDP, solving sender’s optimal signaling policy when the environment is known in cases when the receiver is myoptic or far-sighted. In particular, it is shown as NP-hard to approximate an optimal policy against a far-sighted receiver, which also justifies our interest on the myoptic receiver. Another closely related work [61] studies the learning problem in repeated persuasion setting (without Markov state transition) between a stream of myopic receivers and a sender without initial knowledge of the prior. It introduces the notion of regret as well as the robustness principle to this learning problem that we adopt and generalize to our model.

Bayesian Incentive-Compatible Bandit Exploration. Our work is also loosely related to a seminal result by Mansour et al. [35], who model the misaligned incentives between a system (i.e., sender) and a stream of myopic agents (i.e., receivers). Mansour et al. [35] shows that using information asymmetry, the system can create intrinsic incentives for agents to follow its recommendations. In this problem, the sender’s objective is limited to the social welfare, i.e, the cumulative utility of all agents, whereas we make no assumption on the sender’s utility function and thus her long-term objective. Besides our model is designed to capture more general situations where each receiver could have different priors and utility functions, and the environment might be Markovian with dynamics under the influence of the receivers’ actions.

Efficient Reinforcement Learning. Reinforcement learning has seen its successful applications in various domains, such as robotics, finance and dialogue systems [27, 58, 30]. Along with the empirical success, we have seen a growing quest to establish provably efficient RL methods. Classical sample efficiency results focus on tabular environments with small, finite state spaces [2, 39, 4, 12, 47, 24, 46]. Notably, through the design principle, known as optimism in the face of uncertainty [28], an RL algorithm would provably incur a $\Omega(\sqrt{|{\mathcal{S}}||\mathcal{A}|T})$ regret under the tabular setting, where ${\mathcal{S}}$ and $\mathcal{A}$ are the state and action spaces respectively [24, 4]. More recently, there have been advances in RL with function approximation, especially the linear case. Jin et al. [25] proposed an efficient algorithm for a setting where the transition kernel and the utility function are both linear functions with respect to a feature mapping: $\phi:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{d}$. A similar assumption has been studied for different settings and has led to sample efficiency results [55, 14, 38, 57, 22]. Moreover, other general function approximations have been studied in parallel, including generalized linear function approximation [52], linear mixture MDPs based on a ternary feature mapping [3, 60, 9, 59], kernel approximation [56] as well as models based on the low Bellman rank assumption [23, 11]. We make use of these function approximation techniques to model our conditional prior, and we show how to integrate the persuasion structure into these efficient reinforcement learning frameworks, thereby obtaining sample efficient result for large-scale MPPs.

Classic information design [26] considers the persuasion problem between a single sender (she) and receiver (he). The receiver is the only actor, and looks to take an action $a\in\mathcal{A}$ which results in receiver utility $u(\omega,a)$ and sender utility $v(\omega,a)$. Here $\omega\in\Omega$ is the realized outcome of certain environment uncertainty, which is drawn from a prior distribution $\mu\in\Delta(\Omega)$, and $\mathcal{A}$ is a finite set of available actions for the receiver. While $u,v:\Omega\times\mathcal{A}\to[0,1]$ and the prior distribution $\mu$ are all common knowledge, the sender possesses an informational advantage and can privately observe the realized outcome $\omega$. The persuasion problem studies how the sender can selectively reveal her private information about $\omega$ to influence the receiver’s decisions and ultimately maximize her own expected utility $v$.

To model the sender’s strategic revelation of information, it is standard to use a signaling scheme, which essentially specifies the conditional distribution of a random variable (namely the signal), given the outcome $\omega$. Before the realization of the outcome, the sender commits to such a signaling scheme. Given the realized outcome, the sender samples a signal from the conditional distribution according to the signaling scheme and reveals it to the receiver. Upon receiving this signal, the receiver infers a posterior belief about the outcome via Bayes’ theorem (based on the correlation between the signal and outcome $\omega$ as promised by the signaling scheme) and then chooses an action $a$ that maximizes the expected utility.

A standard revelation-principle-style argument shows that it is without loss of generality to focus on direct and persuasive signaling schemes [26]. A scheme is direct if each signal corresponds to an action recommendation to the receiver, and is persuasive if the recommended action indeed maximizes the receiver’s a posteriori expected utility. More formally, in a direct signaling scheme , $\pi=(\pi(a|\omega):\omega\in\Omega,a\in\mathcal{A})$, $\pi(a|\omega)$ denotes the probability of recommending action $a$ given realized outcome $\omega$. Upon receiving an action recommendation $a$, the receiver computes a posterior belief for $\omega$: $\Pr(\omega|a)=\frac{\mu(\omega)\pi(a|\omega)}{\sum_{\omega^{\prime}}\mu(\omega^{\prime})\pi(a|\omega^{\prime})}$. Thus, the action recommendation $a$ is persuasive if and only if $a$ maximizes the expected utility w.r.t. the posterior belief about $\omega$; i.e., $\sum_{\omega}\Pr(\omega|a)\cdot u(\omega,a)\geq\sum_{\omega}\Pr(\omega|a)\cdot u(\omega,a^{\prime})$ for any $a^{\prime}\in\mathcal{A}$. Equivalently, we define persuasiveness as

Let $\mathcal{P}=\{\pi:\pi(\cdot|\omega)\in\Delta(\mathcal{A})\text{ for each }\omega\in\Omega\}$ denote the set of all signaling schemes. To emphasize that the definition of persuasiveness depends on the prior $\mu$, we denote the set of persuasive schemes on prior $\mu$ by

Given a persuasive signaling scheme $\pi\in\operatorname{Pers}(\mu)$, it is in the receiver’s best interest to take the recommended action and thus the sender’s expected utility becomes $V(\mu,\pi)\coloneqq\sum_{\omega\in\Omega}\sum_{a\in\mathcal{A}}\mu(\omega)\pi(a|\omega)v(\omega,a).$

Therefore, given full knowledge of the persuasion instance, the sender can solve for an optimal persuasive signaling scheme that maximizes her expected utility through the following linear program (LP) which searches for a persuasive signaling scheme that maximizes $V(\mu,\pi)$ (see, e.g., [15] for details):

The Markov decision process (MDP) [41, 48] is a classic mathematical framework for the sequential decision making problem. In this work, we focus on the model of episodic MDP. Specifically, at the beginning of the episode, the environment has an initial state $s_{1}$ (possibly picked by an adversary). Then, at each step $h\geq 1$, the agent takes some action $a_{h}\in\mathcal{A}$ to interact with environment at state $s_{h}\in{\mathcal{S}}$. The state $s_{h}$ obeys a Markov property and thus captures all relevant information in the history $\{s_{i}\}_{i<h}$. Accordingly, the agent receives the utility $v_{h}(s_{h},a_{h})\in[0,1]$ and the system evolves to the state of the next step $s_{h+1}\sim P_{h}(\cdot|s_{h},a_{h})$. Such a process terminates after $h=H$, where $H$ is also known as the horizon length. Here, $\mathcal{A}$ is a finite set of available actions for the agent, ${\mathcal{S}}$ is the (possibly infinite) set of MDP states. The utility function $v_{h}:{\mathcal{S}}\times\mathcal{A}\to[0,1]$ and transition kernel $P_{h}:{\mathcal{S}}\times\mathcal{A}\to\Delta({\mathcal{S}})$ may vary at each step. A policy of the agent $\pi_{h}:{\mathcal{S}}\to\Delta(\mathcal{A})$ characterizes her decision making process at step $h$—after observing the state $s$, the agent takes action $a$ with probability $\pi_{h}(a|s)$.

In an episodic MDP with $H$ steps, under policy $\bm{\pi}=\{\pi_{h}\}_{h\in[H]}$, we define the value function as the expected value of cumulative utilities starting from an arbitrary state,

Here $\mathbb{E}_{P,\bm{\pi}}$ means that the expectation is taken with respect to the trajectory $\{s_{h},a_{h}\}_{h\in[H]}$, which is generated by policy $\bm{\pi}$ on the transition model $P=\{P_{h}\}_{h\in[H]}$. Similarly, we define the action-value function as the expected value of cumulative utilities starting from an arbitrary state-action pair,

The optimal policy is defined as $\bm{\pi}^{*}\coloneqq\arg\max_{\bm{\pi}}V_{h}^{\bm{\pi}}(s_{1})$, which maximizes the (expected) cumulative utility. Since the agent’s action affects both immediate utility and next states that influences its future utility, it thus demands careful planning to maximize total utility. Notably, $\bm{\pi}^{*}$ can solved by dynamic programming based on the Bellman equation [7]. Specifically, with $V_{H+1}^{*}(s)=0$ and for each $h$ from $H$ to $1$, iteratively update $Q_{h}^{*}(s,a)=v_{h}(s,a)+\mathbb{E}_{s^{\prime}\sim P(\cdot|s,a)}V_{h+1}^{*}(s^{\prime},a),~{}V_{h}^{*}(s)=\max_{a\in\mathcal{A}}Q_{h}^{*}(s,a),$ and determine the optimal policy $\bm{\pi}^{*}$ as the greedy policy with respect to $\{Q_{h}^{*}\}_{h\in[H]}$.

In online reinforcement learning, the agent has no prior knowledge of the environment, namely, $\{v_{h},P_{h}\}_{h\in[H]}$, but aims to learn the optimal policy by interacting with the environment for $T$ episodes. For each $t\in[T]$, at the beginning of the $t$-th episode, after observing the initial state $s_{1}^{t}$, the agent chooses a policy $\bm{\pi}^{t}$ based on the observations before $t$-th episode. The discrepancy between $V^{\bm{\pi}^{t}}_{1}(s_{1}^{t})$ and $V^{*}_{1}(s_{1}^{t})$ serves as the suboptimality of the agent at the $t$-th episode. The performance of the online learning algorithm is measured by the expected regret, $\operatorname{Reg}(T)\coloneqq\sum_{t=1}^{T}[V^{*}_{1}(s_{1}^{t})-V^{\bm{\pi}^{t}}_{1}(s_{1}^{t})].$

We start by abstracting the sequential information design problem instances in Section 1 into MPPs. Taking as an example recommendation platform for ad keywords, we view the platform as the sender, the advertisers as the receivers. The advertisers decide the actions $a\in\mathcal{A}$ such as whether to accept the recommended keyword. To better reflect the nature of reality, we model two types of information for MPPs, outcome and state. We use the notion of outcome $\omega\in\Omega$ to characterize the sender’s private information in face of each receiver, such as the features of searchers for some keyword. The outcome follows a prior distribution such as the general demographics of Internet users on the platform. The platform can thus leverage such fine-grained knowledge on keyword features, matching with the specific ad features of each advertiser, to persuade the advertisers to take a recommendation of keywords. Meanwhile, we use the notion of state $s\in{\mathcal{S}}$ to characterize the Markovian state of the environment, e.g., the availability of ad keyword slots. The state is affected by the receiver’s action, as the availability changes after some keywords get brought.¹¹1Similarly, we can view the online shopping platform as the sender who persuades a stream of receivers (supplier, consumer) to take certain action, whether to take an offer or make a purchase. In this case, sender can privately observe the outcomes such as the consumer sentiments on some random products based on the search and click logs, whereas the states are product reviews, sales or shipping time commonly known to the public and affected by the actions of both supply and demand sides. In case of rider-sharing, outcome represents the fine-grained knowledge of currently active rider types that are privately known to the platform and generally stochastic in accordance to some user demographics, whereas the state captures the general driver supply or rider demand at locations that is affected by the drivers’ decisions. Naturally, both sender’s and receiver’s utility are determined by the receiver’s action $a$ jointly with the state of environment $s$ and realized outcome $\omega$, i.e., $u,v:{\mathcal{S}}\times\Omega\times\mathcal{A}\to[0,1]$. Meanwhile, as these applications could serve thousands or millions of receivers every day, to reduce the complexity of our model we assume each receiver appears only once and thus will myopically maximizes his utility at that particular step, whereas the sender is a system planner who aim to maximizes her long-term accumulated expected utility.

More specifically, an MPP is built on top of a standard episodic MDP with state space ${\mathcal{S}}$, action space $\mathcal{A}$, and transition kernel $P$. In this paper, we restrict our attention to finite-horizon (i.e., episodic) MPPs with $H$ steps denoted by $[H]=\{1,\cdots,H\}$, and leave the study of infinite-horizon MPPs as an interesting future direction. At a high level, there are two major differences between MPPs and MDPs. First, in a MPP, the planner cannot directly take an action but instead can leverage its information advantage and “persuade” a receiver to take a desired action $a_{h}$ at each step $h\in[H]$. Second, in an MPP, the state transition is affected not only by the current action $a_{h}$ and state $s_{h}$, but also by the realized outcome $\omega_{h}$ of Nature’s probability distribution. Specifically, the state transition kernel at step $h$ is denoted as $P_{h}(s_{h+1}|s_{h},\omega_{h},a_{h})$. To capture the sender’s persuasion of a receiver to take actions at step $h$, we assume that a fresh receiver arrives at time $h$ with a prior $\mu_{h}$ over the outcome $\omega_{h}$. The planner, who is the sender here, can observe the realized outcome $\omega_{h}$ and would like to strategically reveal information about $\omega_{h}$ in order to persuade the receiver to take a certain action $a_{h}$.

Differing from classical single-shot information design, the immediate utility functions $u_{h},v_{h}$ for the receiver and sender vary not only at each step $h$ but also additionally depend on the commonly observed state $s_{h}$ of the environment. We assume the receiver to have full knowledge of his utility $u_{h}$ and prior $\mu_{h}$ at each step $h$, and would take the recommended action $a_{h}$ if and only if $a_{h}$ maximizes his expected utility under the posterior for $\omega_{h}$.²²2This assumption is not essential but just for technical rigor. Because even if receivers have limited knowledge or computational power to accurately determine the utility-maximizing actions, the sender should have sufficient ethical or legal reasons to comply with the persuasive constraints in practice. And the receivers would only take the recommendation if the platform has good reputation (i.e., persuasive with high probability).

Formally, an MPP with a horizon length $H$ proceeds as follows at each step $h\in[H]$:

1. A fresh receiver with prior distribution $\mu_{h}\in\Delta(\Omega)$ and utility $u_{h}:{\mathcal{S}}\times\Omega\times\mathcal{A}\to[0,1]$ arrives. 2. The sender commits to a persuasive signaling policy $\pi_{h}:{\mathcal{S}}\to\mathcal{P}$, which is public knowledge. 3. After observing the realized state $s_{h}$ and outcome $\omega_{h}$, the sender accordingly recommends the receiver to take an action $a_{h}\sim\pi_{h}(\cdot|s_{h},\omega_{h})$. 4. Given the recommended action $a_{h}$, the receiver takes an action $a^{\prime}_{h}$, receives utility $u_{h}(s_{h},\omega_{h},a^{\prime}_{h})$ and then leaves the system. Meanwhile, the sender receives utility $v_{h}(s_{h},\omega_{h},a^{\prime}_{h})$. 5. The next state $s_{h+1}\sim P_{h}(\cdot|s_{h},\omega_{h},a^{\prime}_{h})$ is generated according to $P_{h}:{\mathcal{S}}\times\Omega\times\mathcal{A}\to\Delta({\mathcal{S}})$, the state transition kernel at the $h$-th step.

Here we coin the notion of a signaling policy $\pi_{h}$ as a mapping from state to a signaling scheme at the $h$-th step. It captures a possibly multi-step procedure in which the sender commits to a signaling scheme after observing the realized state and then samples a signal after observing the realized outcome. For notational convenience, we denote $\pi(a|s,\omega)$ as the probability of recommending action $a$ given state $s$ and realized outcome $\omega$. We can also generalize the notion of persuasiveness from classic information design to MPPs. Specifically, we define $\operatorname{Pers}(\mu,u)$ as the persuasive set that contains all signaling policies that are persuasive to the receiver with utility $u$ and prior $\mu$ for all possible state $s\in{\mathcal{S}}$:

Recall that $\mathcal{P}$ consists of all mappings from $\Omega$ to $\Delta(\mathcal{A})$. As such, the sender’s persuasive signaling scheme $\pi_{h}\in\operatorname{Pers}(\mu_{h},u_{h})$ is essentially a stochastic policy as defined in standard MDPs—$\pi_{h}$ maps a state $s_{h}$ to a stochastic action $a_{h}$—except that here the probability of suggesting action $a_{h}$ by policy $\pi_{h}$ depends additionally on the realized outcome $\omega_{h}$ that is only known to the sender.

We say $\bm{\pi}\coloneqq\{\pi_{h}\}_{h\in[H]}$ is a feasible policy of the MPP if $\pi_{h}\in\operatorname{Pers}(\mu_{h},u_{h}),\forall h\in[H]$, because the state transition trajectory would otherwise be infeasible if the receiver is not guaranteed to take the recommended action, i.e., $a^{\prime}_{h}\neq a_{h}$. We denote the set of all feasible policies as $\mathcal{P}^{H}\coloneqq\prod_{h\in[H]}\operatorname{Pers}(\mu_{h},u_{h})$.

To provide a broadly useful modeling concept, we also study a generalized setting of the Markov Persuasion Process with contextual prior and a possibly large space of states, outcomes and contexts.

In order to maximize the sender’s utility, we study the optimal policy in MPPs, in analogy to that of standard MDPs. We start by considering the value of any feasible policy $\bm{\pi}$. For each step $h\in[H]$, we define the value function for the sender $V_{h}^{\pi}:{\mathcal{S}}\to\mathbb{R}$ as the expected value of cumulative utilities under $\bm{\pi}$ when starting from an arbitrary state at the $h$-th step. That is, for any $s\in{\mathcal{S}},h\in[H]$, we define

where the expectation $\mathbb{E}_{P,\mu,\pi}$ is taken with respect to the randomness of the trajectory (i.e., randomness of state transition), realized outcome and the stochasticity of $\bm{\pi}$. Accordingly, we define the $Q$-function (action-value function) $Q_{h}^{\pi}:{\mathcal{S}}\times\Omega\times\mathcal{A}\to\mathbb{R}$ which gives the expected value of cumulative utilities when starting from an arbitrary state-action pair at the $h$-step following the signaling policy $\bm{\pi}$, that is,

By definition, $Q_{h}(\cdot,\cdot,\cdot),V_{h}(\cdot)\in[0,h]$, since $v_{h}(\cdot,\cdot,\cdot)\in[0,1]$. To simplify notation, for any $Q$-function $Q_{h}$ and any distributions $\mu_{h}$ and $\pi_{h}$ over $\Omega$ and $\mathcal{A}$, we additionally denote

Using this notation, the Bellman equation associated with signaling policy $\bm{\pi}$ becomes

which holds for all $s\in\mathcal{S},\omega\in\Omega,a\in\mathcal{A}$. Similarly, the Bellman optimality equation is

We remark that the above equations implicitly assume the context $C=\{c_{h}\}_{h\in[H]}$ (and thus the priors) are determined in advance. To emphasize the values’ dependence on context which will be useful for the analysis of later learning algorithms, we extend the notation to $V^{\pi}_{h}(s;C),Q_{h}^{\pi}(s,\omega,a;C)$ to specify that the value (resp. Q) function is estimated based on which prior $\mu$ conditioned on which sequence of context $C$.

We consider the episodic reinforcement learning problem in finite-horizon MPPs. Different from the full knowledge setting in Section 3.3, the transition kernel, the sender’s utility function and the outcome prior at each step of the episode, $\{P_{h},v_{h},\mu_{h}\}_{h\in[H]}$, are all unknown. The sender has to learn the optimal signaling policy by interacting with the environment as well as a stream of receivers in $T$ number of episodes. For each $t\in[T]=\{1,\cdots,T\}$, at the beginning of $t$-th episode, given the data $\{(c_{h}^{\tau},s_{h}^{\tau},\omega_{h}^{\tau},a_{h}^{\tau},v_{h}^{\tau})\}_{h\in[H],\tau\in[t-1]}$, the adversary picks the context sequence $\{c_{h}^{t}\}_{h\in[H]}$ as well as the initial state $s_{1}^{t}$, and the agent accordingly chooses a signaling policy $\bm{\pi}^{t}=\{\pi_{h}^{t}\}_{h\in[H]}$. Here $v_{h}^{\tau}$ is the utility collected by the sender at step $h$ of episode $\tau$.

The learning task in MPPs involves two intertwined challenges: (1) How to persuade the receiver to take desired actions under unknown $\mu_{h}$? (2) Which action to persuade the receiver to take in order to explore the underlying environment? For the first challenge, due to having finite data, it is impossible to perfectly recover $\mu_{h}$. We can only hope to construct an approximately accurate estimator of $\mu_{h}$. To guard against potentially detrimental equilibrium behavior of the receivers due to the prior estimation error, we propose to adopt the pessimism principle. Specifically, before each episode, we conduct uncertainty quantification for the estimator of the prior distributions, which enables us to construct a confidence region containing the true prior with high probability. Then we propose to find the signaling policy within a pessimistic candidate set—signaling policies that are simultaneously persuasive with respect to all prior distributions in the confidence region. When the confidence region is valid, such a pessimism principle ensures that the executed signaling policy is always persuasive with respect to the true prior. Furthermore, to address the second challenge, we adopt the celebrated principle of optimism in the face of uncertainty [28], which has played a key role in the online RL literature. The main idea of this principle is that, the uncertainty of the $Q$-function estimates essentially reflects our uncertainty about the underlying model. By adding the uncertainty as a bonus function, we encourage actions with high uncertainty to be recommended and thus taken by the receiver when persuasiveness is satisfied. We then fuse the two principles into the OP4 algorithm in Algorithm 1.

We first consider MPPs in tabular setting with finite states and outcomes, as described in Section 3.1. In this case, the prior on outcomes at each step degenerates to an unknown but fixed discrete distribution independent of context. As linear parameterization is not required for discrete probability distribution, the algorithm can simply update the empirical estimation of $\mu_{h}^{t}$ through counting. Similarly, the transition kernel $P_{h}^{*}$ is estimated through the occurrence of observed samples, and we uses this estimated transition to compute the $Q$-function $\widehat{Q}_{h}^{t}$ from the observed utility and estimated value function in the next step, according to the Bellman equation. To be specific, for each $s\in{\mathcal{S}},\omega\in\Omega,a\in\mathcal{A}$, $\mu_{h}^{t}$ and $\widehat{Q}_{h}^{t}$ are estimated through the following equations:

where $N_{t,h}(\omega)=\sum_{\tau\in[t-1]}\mathbb{I}(\omega_{h}^{\tau}=\omega)$ and $N_{t,h}(s,\omega,a)=\sum_{\tau\in[t-1]}\mathbb{I}(s_{h}^{\tau}=s,\omega_{h}^{t}=\omega,a_{h}^{t}=a)$ respectively count the effective number of samples that the sender has observed arriving at $\omega$, or the combination $\{s,\omega,a\}$), and $\lambda>0$ is a constant for regularization.

In our learning algorithm, we determine the radius of confidence region $\mathcal{B}_{h}^{t}$ for $\mu_{h}^{t}$ according to confidence bound $\epsilon_{h}^{t}=O(\sqrt{\log(HT)/t})$. Moreover, we add a UCB bonus term of form $\rho/\sqrt{N_{t,h}(s,\omega,a)}$ to $\widehat{Q}_{h}^{t}$ to obtain the optimistic $Q$-function $Q_{h}^{t}$. Then, it selects a robustly persuasive signaling scheme that maximizes an optimistic estimation of $Q$-function with respect to the current prior estimation $\mu_{h}^{t}$. Finally, it makes an action recommendation $a_{h}^{t}$ using this signaling scheme, given the state and outcome realization $\{s_{h}^{t},\omega_{h}^{t}\}$.

To obtain the regret of OP4, we have to consider the regret arising from different procedures. Formal decomposition of the regret is described in Lemma 6.1. Separately, we upper bound errors incurred from estimating $Q$-function (Lemma 6.2), the randomness of of choosing the outcome, action and next state (Lemma A.5) as well as estimating the prior of outcome and choosing a persuasive signaling scheme that is robustly persuasive for a subset of priors (Lemmas 6.3 and 6.4). As the two warm-up models are special cases of the general MPP, the proof of the above properties follows from that of the general MPP setting in Section 6, and thus is omitted here.

We now move to another special case with $H=1$, such that the MPP problem reduces to a contextual-bandit-like problem, where transitions no longer exist. Given a context $c$ and a persuasive signaling policy $\pi$, the value function is simply the sender’s expected utility for any $s\in{\mathcal{S}}$,

The sender’s optimal expected utility is defined as $V^{*}(s;c)\coloneqq\max_{\pi\in\operatorname{Pers}(\mu(\cdot|c),u)}V^{\pi}(s;c).$

Meanwhile, we consider the general setting where outcome $\omega$ is a continuous random variable that subjects to a generalized linear model. To be specific, the prior $\mu$ is conditioned on the context $c$ with the mean value $f(\phi(c)^{\top}\theta)$. For the prior $\mu$ and link function $f$, we assume the smoothness of the prior and the bounded derivatives of the link function:

It is natural to assume a Lipschitz property of the distribution in Assumption 4.2. For instance, Gaussian distributions and uniform distributions satisfy this property. Assumption 4.3 is standard in the literature [18, 52, 32]. Two example link functions are the identity map $f(z)=z$ and the logistic map $f(z)=1/(1+e^{-z})$ with bounded $z$. It is easy to verify that both maps satisfy this assumption.

Different from the tabular setting, we are now unable to use the counting-based estimator to keep track of the distribution of the possibly infinite states and outcomes. Instead, we resort to function approximation techniques and estimate the linear parameters $\theta^{*}$ and $\gamma^{*}$. In each episode, OP4 respectively updates the estimation and confidence region of $\theta^{t}$ and $\gamma^{t}$, with which it can determine the outcome prior under pessimism and sender’s utility under optimism. To be specific, the update of $\theta^{t}$ solves a constrained least-squares problem and the update of $q^{t}$ solves precisely a regularized one:

We then estimate the prior by setting $\mu^{t}(\cdot|c)$ to the distribution of $f\big{(}\phi(c)^{\top}\theta^{t}\big{)}+z$ and estimate the sender’s utility by setting $v^{t}(\cdot,\cdot,\cdot)=\psi(\cdot,\cdot,\cdot)^{\top}\gamma^{t}$. On one hand, to encourage exploration, OP4 adds the UCB bonus term of form $\rho\left\|\psi(\cdot,\cdot,\cdot)\right\|_{(\Gamma^{t})^{-1}}$ to the $Q$-function, where $\Gamma^{t}=\lambda I_{d_{\psi}}+\sum_{\tau\in[t]}\psi(s^{\tau},\omega^{\tau},a^{\tau})\psi(s^{\tau},\omega^{\tau},a^{\tau})^{\top}$ is the Gram matrix of the regularized least-squares problem and $\rho$ is equivalent to a scalar. This is a common technique for linear bandits. On the other hand, OP4 determines the confidence region of $\theta^{t}$ with radius $\beta$, and ensures that signaling scheme is robustly persuasive for any possible (worst case) prior induced by linear parameters $\theta$ in this region. Combining optimism and pessimism, OP4 picks the signaling scheme among the robust persuasive set that maximizes the sender’s optimistic utility.

Since we estimate the prior by computing an estimator $\theta^{t}$, we evaluate the persuasiveness of OP4 through the probability that $\theta^{*}$ lies in the confidence region centered at $\theta^{t}$ with the radius $\beta=O(\sqrt{d_{\phi}\log(T)})$ in weighted norm. Due to the smoothness of the prior and the assumption of link function, the error of the estimated prior is bounded by the product of $\beta$ and the weighted norm of feature vector $\|\phi(c^{t})\|_{\Sigma^{t}}=O(1/\sqrt{t})$, which yields the same conclusion for $\epsilon^{t}$ in the tabular MPP case. Also compared to Li et al. [31], we do not require any regularity for $\Sigma^{t}$, since we add a constant matrix $\Phi^{2}I$ to the Gram matrix $\Sigma^{t}$. This ensures that $\Sigma^{t}$ is always lower bounded by the constant $\Phi^{2}>0$. The proof of the persuasiveness and sublinear regret of contextual bandit can be viewed as a direct reduction of the MPP case when the total step $H=1$. We decompose the regret in the same way as that in Lemma 6.1 for MPPs and then estimate the upper bound for each item to measure the regret loss.

In order to prove the sublinear regret for OP4, we construct a novel regret decomposition tailored to MPPs. Our proof starts from decomposing the regret into several terms, each of which indicates the regret loss either from estimation or from the randomness of trajectories. Next, we evaluate each term and then add them together to conclude the upper bound of the regret of OP4. For simplicity of presentation, denote $\widetilde{V}_{h}^{t}(\cdot;C)=\big{\langle}Q_{h}^{t},\mu_{h}^{*}\otimes\pi_{h}^{t}\big{\rangle}_{\Omega\times\mathcal{A}}(\cdot;C)$ as the expectation of $Q_{h}^{t}$ with respect to the ground-truth prior $\mu_{h}^{*}$ and signaling scheme $\pi_{h}^{t}$ at the $h$-th step. Then we can define the temporal-difference (TD) error as