Markov Persuasion Processes: Learning to Persuade From Scratch

## Abstract

Abstract In Bayesian persuasion , an informed sender strategically discloses information to a receiver so as to persuade them to undertake desirable actions.
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.

## 1 Introduction

*Bayesian persuasion* (Kamenica and Gentzkow, ) studies how an informed sender should strategically disclose information to influence the behavior of an interested receiver.
Bayesian persuasion has received a growing attention over the last years, since it captures several fundamental problems arising in real-world applications, such as, *e.g.*,
online advertising (Bro Miltersen and Sheffet, ; Emek et al., ; Badanidiyuru et al., ; Castiglioni et al., ; Bacchiocchi et al., ),
voting (Cheng et al., ; Alonso and Câmara, ; Castiglioni et al., ; Castiglioni and Gatti, ),
traffic routing (Vasserman et al., ; Bhaskar et al., ; Castiglioni et al., ), recommendation systems (Mansour et al., ),
security (Rabinovich et al., ; Xu et al., ), marketing (Babichenko and Barman, ; Candogan, ),
clinical trials (Kolotilin, ),
and financial regulation (Goldstein and Leitner, ).

The vast majority of works on Bayesian persuasion focuses on *one-shot* interactions, where information disclosure is performed in a single step.
Despite the fact that real-world problems are usually *sequential*, there are only few exceptions that consider multi-step information disclosure (Wu et al., ; Gan et al., ; Bernasconi et al., , ).
In particular, Wu et al. () initiated the study of *Markov persuasion processes* (MPPs), which model scenarios where a sender sequentially faces a stream of *myopic* receivers in an unknown Markovian environment.
In each state of the environment, the sender privately observes some information—encoded in an outcome stochastically determined according to a prior distribution—and faces a *new* receiver, who is then called to take an action.
The outcome and receiver’s action jointly determine agents’ rewards and the next state.
In an MPP, sender’s goal is to (partially) disclose information at each state so as to persuade the receivers to take actions that maximize *long-term* sender’s expected rewards.

MPPs find application in several real-world settings, such as e-commerce and recommendation systems (Wu et al., ).
For example, an MPP can model the problem faced by an online streaming platform recommending movies to its users.
Indeed, the platform has an informational advantage over users (*e.g.*, it has access to views statistics), and it exploits available information to induce users to watch suggested movies, so as to maximize views.
Nevertheless, the MPPs studied by Wu et al. () suffer from several issues that prevent them from being fully operational in practice.
In particular, they make the rather strong assumption that the *sender has perfect knowledge of receiver’s rewards*.
This is unreasonable in real-world applications.
For instance, in the online streaming platform example described above, such an assumption requires that the platform knows everything about users’ (private) preferences over movies.

We considerably relax the assumptions of Wu et al. (), by addressing MPPs where the *sender does not know anything about the environment*.
We consider settings in which the sender has no knowledge about transitions, prior distributions over outcomes, sender’s stochastic rewards, and receivers’ ones.
Thus, they have to learn all these quantities simultaneously by repeatedly interacting with the MPP.

### 1.1 Original Contributions

Ideally, our goal is to design learning algorithms which attain *regret* sublinear in the number of episodes $T$, while being *persuasive*.
The regret is the difference between sender’s rewards cumulated over the episodes and what would have been obtained by always using an optimal information-disclosure policy, while persuasiveness ensures that the receivers are correctly incentivized to take the desired actions.

Learning in MPPs without knowledge of receivers’ rewards begets considerable additional challenges compared to the case addressed by Wu et al. ().
Indeed, the latter design a sublinear-regret algorithm which is persuasive at every episode with high probability, while we show that this is *not* attainable in our setting.
Intuitively, this is due to the fact that, since the sender does *not* know receivers’ rewards, some episodes must be devoted to learn how to “approximately” satisfy persuasiveness requirements.
As a consequence, in this work we look for algorithms which attain sublinear regret while ensuring that the cumulative *violation* of persuasiveness grows sublinearly in $T$.(^1^11Ensuring sublinear violation has already been addressed in settings related to MPPs (see, *e.g.*, (Bernasconi et al., )), as it is the most reasonable and natural requirement one may think of in all cases in which persuasiveness cannot be achieved.)

As a warm-up, we start studying a *full* feedback case where, after each episode, the sender observes the reward associated with every possible action in all the state-outcome pairs encountered during the episode.
We propose an algorithm, called Optimistic Persuasive Policy Search (OPPS), which uses information-disclosure policies computed by being *optimistic* with respect to both sender’s expected rewards and persuasiveness requirements.
We show that, under full feedback, OPPS attains $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and violation.
Then, we switch to the *partial* feedback case, where the sender only observes the rewards for the state-outcome-action triplets actually visited during the episode.
We extend the OPPS algorithm to this setting, by adding a preliminary *exploration* phase having the goal of gathering as much feedback as possible about persuasiveness.
After that, the algorithm switches to an optimistic approach over information-disclosure policies that are “approximately” persuasive.
We prove that OPPS with partial feedback attains $\widetilde{\mathcal{O}}(T^{\alpha})$ regret and $\widetilde{\mathcal{O}}(T^{1-\nicefrac{{\alpha}}{{2}}})$ violation, where $\alpha\in[\nicefrac{{1}}{{2}},1]$ is a parameter controlling the amount of exploration.
Finally, we provide a lower bound showing that the trade-off between regret and violation achieved by means of OPPS is tight.

### 1.2 Related Works

#### Sequential Bayesian Persuasion

The work that is most related to ours is (Wu et al., ), which introduces MPPs.
Specifically, Wu et al. () study settings where the sender knows everything about receivers’ rewards, with the only elements unknown to them being their rewards, transition probabilities, and prior distributions over outcomes.
Moreover, they also assume that the receivers know everything they need about the environment, so as to select a best-response action, and that all rewards are deterministic.
In contrast, we consider MPP settings in which sender and receivers have no knowledge of the environment, including their rewards, which we assume to be stochastic.
Moreover, Wu et al. () obtain a regret bound of the order of $\widetilde{\mathcal{O}}(\sqrt{T}/D)$, where $D$ is a parameter related to receivers’ rewards.
Notice that such a dependence is particularly unpleasant, as $D$ may be exponentially large in instances in which there are some receivers’ actions that are best responses only for a “small” space of information-disclosure policies.
Other works related to ours are (Gan et al., ), which studies a Bayesian persuasion problem where a sender sequentially interacts with a myopic receiver in a multi-state environment, and (Bernasconi et al., ), which addresses MPPs with a farsighted receiver.
These two works considerably depart from ours, as they both assume that the sender knows everything about the environment, including transitions, priors, and rewards.
Thus, they are *not* concerned with learning problems, but with the problem of computing optimal information-disclosure policies.
Finally, (Bernasconi et al., ) studies settings where a sender faces a farsighted receiver in a sequential environment with a tree structure, addressing the case in which the only elements unknown to the sender are the prior distributions over outcomes, while rewards are deterministic and known.
The tree structure considerably eases the learning task, as it allows to express sender’s expected rewards linearly in variables defining information-disclosure policies.
Intuitively, this allows to factor the uncertainty about transitions in the rewards at the leaves of the tree.

Our work is also related to learning in one-shot Bayesian persuasion settings played repeatedly (Castiglioni et al., , ; Zu et al., ; Bernasconi et al., ), and works study online learning in *Markov decision processes* (MDPs) (see, *e.g.*, (Auer et al., ; Even-Dar et al., ; Neu et al., ; Rosenberg and Mansour, ; Jin et al., )), in particular those on MDPs with constraints (see, *e.g.*, (Wei et al., ; Zheng and Ratliff, ; Efroni et al., ; Qiu et al., ; Germano et al., )).

See Appendix A for more details on related works.

## 2 Preliminaries

### 2.1 Bayesian Persuasion

The classical *Bayesian persuasion* framework introduced by Kamenica and Gentzkow () models a *one-shot* interaction between a *sender* and a *receiver*.
The latter has to take an action $a$ from a finite set $A$, while the former privately observes an outcome $\omega$ sampled from a finite set $\Omega$ according to a prior distribution $\mu\in\Delta(\Omega)$, which is *known to both* the sender and the receiver.(^2^22In this work, we denote by $\Delta(X)$ the set of all the probability distributions having set $X$ as support.)
The rewards of both agents depend on the receiver’s action and the realized outcome, as defined by the functions $r_{S},r_{R}:\Omega\times A\to[0,1]$, where $r_{R}(\omega,a)$ and $r_{S}(\omega,a)$ denote the rewards of the sender and the receiver, respectively, when the outcome is $\omega\in\Omega$ and action $a\in A$ is played.
The sender can strategically disclose information about the outcome to the receiver, by *publicly committing to* a signaling scheme $\phi$, which is a randomized mapping from outcomes to signals being sent to the receiver.
Formally, $\phi:\Omega\to\Delta(\mathcal{S})$, where $\mathcal{S}$ denotes a suitable finite set of signals.
For ease of notation, we let $\phi(\cdot|\omega)\in\Delta(\mathcal{S})$ be the probability distribution over signals employed by the sender when the realized outcome is $\omega\in\Omega$, with $\phi(s|\omega)$ being the probability of sending signal $s\in\mathcal{S}$.

The sender-receiver interaction goes on as follows: (i) the sender publicly commits to a signaling scheme $\phi$; (ii) the sender observes the realized outcome $\omega\sim\mu$ and draws a signal $s\sim\phi(\cdot|\omega)$; and (iii) the receiver observes the signal $s$ and plays an action.
Specifically, after observing $s$ under a signaling scheme $\phi$, the receiver infers a *posterior* distribution over outcomes and plays a *best-response* action $b^{\phi}(s)\in A$ according to such distribution.
Formally:

$$ $b^{\phi}(s)\in\operatorname*{arg\,max}_{a\in A}\,\sum_{\omega\in\Omega}\mu( \omega)\phi(s|\omega)r_{R}(\omega,a),$ $$

where the expression being maximized encodes the (unnormalized) expected reward of the receiver.
As it is customary in the literature Kamenica and Gentzkow (), we assume that the receiver breaks ties in favor of the sender, by selecting a best response maximizing sender’s expected reward when multiple best responses are available.

The goal of the sender is to commit to a signaling scheme $\phi$ that maximizes their expected reward, which is computed as follows: $\sum_{\omega\in\Omega}\mu(\omega)\sum_{s\in\mathcal{S}}\phi(s|\omega)r_{S}(
\omega,b^{\phi}(s))$.

### 2.2 Markov Persuasion Processes

A *Markov persuasion process* (MPP) (Wu et al., ) generalizes the one-shot Bayesian persuasion framework by Kamenica and Gentzkow () to settings in which the sender sequentially interacts with multiple receivers in a *Markov decision process* (MDP).
In an MPP, the sender faces a stream of *myopic* receivers who take actions by only accounting for their immediate rewards, thus disregarding future ones.

Formally, an (*episodic*) MPP is defined by means of a tuple $M:=\left(X,A,\Omega,\mu,P,\{r_{S,t}\}_{t=1}^{T},\{r_{R,t}\}_{t=1}^{T}\right)$, where:

- •
$T$ is the number of episodes.(^3^33In this work, a specific episode is denoted by $t\in[T]$, where $[a\ldots b]$ is the set of all integers from $a$ to $b$ and $[b]:=[1\ldots b]$.)
- •
$X$, $A$, and $\Omega$ are finite sets of sates, actions, and outcomes, respectively.
- •
$\mu:X\to\Delta(\Omega)$ is a prior function defining a probability distribution over outcomes at each state. For ease of notation, we let $\mu(\omega|x)$ be the probability with which outcome $\omega\in\Omega$ is sampled in state $x\in X$.
- •
$P:X\times\Omega\times A\to\Delta(X)$ is a transition function. For ease of notation, we let $P(x^{\prime}|x,\omega,a)$ be the probability of moving from $x\in X$ to $x^{\prime}\in X$ by taking action $a\in A$, when the outcome sampled in state $x$ is $\omega\in\Omega$.
- •
$\{r_{S,t}\}_{t=1}^{T}$ is a sequence specifying a sender’s reward function $r_{S,t}:X\times\Omega\times A\to[0,1]$ at each episode $t$. Given $x\in X$, $\omega\in\Omega$, and $a\in A$, each $r_{S,t}(x,\omega,a)$ for $t\in[T]$ is sampled independently from a distribution $\nu_{S}(x,\omega,a)\in\Delta([0,1])$ with mean $r_{S}(x,\omega,a)$.
- •
$\{r_{R,t}\}_{t=1}^{T}$ is a sequence defining a receivers’ reward function $r_{R,t}:X\times\Omega\times A\to[0,1]$ at each episode $t$. Given $x\in X$, $\omega\in\Omega$, and $a\in A$, each $r_{R,t}(x,\omega,a)$ for $t\in[T]$ is sampled independently from a distribution $\nu_{R}(x,\omega,a)\in\Delta([0,1])$ with mean $r_{R}(x,\omega,a)$.(^4^44Notice that, while (Wu et al., ) considers MPPs in which the rewards are *deterministic* and do *not* change across episodes, in this work we address the more general case in which the rewards are *stochastic* and sampled at each episode independently.)

For ease of presentation, we focus w.l.o.g. on episodic MPPs enjoying the *loop-free* property, as customary in the online learning in MDPs literature (Rosenberg and Mansour, ).
In a loop-free MPP, states are partitioned into $L+1$ layers $X_{0},\dots,X_{L}$ such that $X_{0}:=\{x_{0}\}$ and $X_{L}:=\{x_{L}\}$, with $x_{0}$ being the initial state of the episode and $x_{L}$ being the final one, in which the episode ends.
Moreover, by letting $\mathcal{K}:=[0\ldots L-1]$ for ease of notation, $P(x^{\prime}|x,\omega,a)>0$ only when $x^{\prime}\in X_{k+1}$ and $x\in X_{k}$ for some $k\in\mathcal{K}$.(^5^55Notice that the loop-free property is w.l.o.g. since any episodic MPP with finite horizon $H$ that is *not* loop-free can be cast into a loop-free one by suitably duplicating states for $H$ times, *i.e.*, a state $x\in X$ is mapped to a set of new states $(x,k)$ with $k\in[H]$.)

At each episode of an episodic MPP, the sender publicly commits to a *signaling policy* $\phi:X\times\Omega\to\Delta(\mathcal{S})$, which defines a probability distribution over a finite set $\mathcal{S}$ of signals for the receivers for every state $x\in X$ and outcome $\omega\in\Omega$.
For ease of notation, we denote by $\phi(\cdot|x,\omega)\in\Delta(\mathcal{S})$ such probability distributions, with $\phi(s|x,\omega)$ being the probability of sending a signal $s\in\mathcal{S}$ in state $x$ when the realized outcome is $\omega$.
Similarly to one-shot Bayesian persuasion, a myopic receiver acting at state $x\in X$ and receiving signal $s\in\mathcal{S}$ infers a posterior distribution over outcomes and plays a best-response action.
We denote by $b^{\phi}(s,x)\in A$ the best response played by such a receiver under the signaling policy $\phi$ (assuming ties are broken in favor of the sender).

As customary in Bayesian persuasion settings (see, *e.g.*, (Kamenica and Gentzkow, ; Arieli and Babichenko, )), a revelation-principle-style argument allows to focus w.l.o.g. on signaling policies that are direct and persuasive.
Formally, a signaling policy is *direct* if the set of signals coincides with the set of actions, namely $\mathcal{S}=A$.
Intuitively, in such a case, signals should be interpreted as action recommendations for the receivers.
Moreover, a direct signaling policy is said to be *persuasive* if it incentivizes the receivers to follow recommendations issued by the sender.
Formally, $\phi:X\times\Omega\to\Delta(A)$ is persuasive if the following holds for every state $x\in X$ and action recommendation $a\in A$:

$$ $\sum_{\omega\in\Omega}\mu(\omega|x)\phi(a|x,\omega)\big{(}r_{R}(x,\omega,a)-r_ {R}(x,\omega,b^{\phi}(a,x))\big{)}\geq 0.$ $$

Intuitively, the inequality above states that a receiver acting at state $x$ is better off following the sender’s recommendation to play action $a$, since by doing so they get an (unnormalized) expected reward greater than or equal to what they would obtain by playing a best-response action $b^{\phi}(a,x)$.

Figure: Algorithm 1 Sender-Receivers Interaction at $t\in[T]$

The interaction between the sender and the stream of receivers at episode $t\in[T]$ is described in Algorithm 1.
Let us remark that sender and receivers do *not* know anything about the transition function $P$, the prior function $\mu$, and the rewards $r_{S,t}(x,\omega,a),r_{R,t}(x,\omega,a)$ (including their distributions).(^6^66Notice that, since receivers do *not* know anything about their rewards, Algorithm 1 assumes that they always play recommended actions. This is w.l.o.g. thanks to the fact that our learning algorithms guarantee that the per-round violation of persuasiveness constraints goes to zero as the number of episodes grows. Thus, it is in the receivers’ best interest to stick to recommendations.)
At the end of each episode, the sender gets to know the triplets $(x_{k},\omega_{k},a_{k})$—for all $k\in\mathcal{K}$—that are *visited* during the episode, and an additional *feedback* about rewards.
In this work, we consider two types of feedback.
The first one—called *full* feedback—encompasses all agents’ rewards for the pairs $(x_{k},\omega_{k})$ visited during the episode, *i.e.*, the rewards for all the triplets $(x_{k},\omega_{k},a)$ for $a\in A$.
The second type—called *partial* feedback—only consists in agents’ rewards for the visited triplets $(x_{k},\omega_{k},a_{k})$.(^7^77Notice that, in this work we use the adjective *full* to refer to a type of feedback that is *not* the most informative one. Indeed, a full feedback according to the classical terminology used in online learning (Cesa-Bianchi and Lugosi, ; Orabona, ) would encompass agents’ rewards for all the possible triplets $(x,\omega,a)$, while full feedback in our terminology only consists in the rewards for the triplets with $x=x_{k}$ and $\omega=\omega_{k}$ for some $k\in\mathcal{K}$.)

## 3 The Learning Problem

In this section, we formally introduce the learning problem tackled in the rest of the paper.
First, in Section 3.1, we extend the notion of occupancy measure to MPPs.
Then, in Section 3.2, we formally introduce learning objectives.
Finally, in Section 3.3, we provide some preliminary elements needed by our algorithms, developed in Sections 4 and 5.

For reasons of space, the complete proofs of all our results are provided in Appendixes D and E.

### 3.1 Occupancy Measures in MPPs

Next, we extend the well-known notion of *occupancy measure* of an MDP (Rosenberg and Mansour, ) to MPPs.
Given a transition function $P$, a signaling policy $\phi$, and a prior function $\mu$, the occupancy measure induced by $P$, $\phi$, and $\mu$ is a vector $q^{P,\phi,\mu}\in[0,1]^{|X\times\Omega\times A\times X|}$ whose entries are specified as follows.
For every $x\in X_{k}$, $\omega\in\Omega$, $a\in A$, and $x^{\prime}\in X_{k+1}$ with $k\in\mathcal{K}$, it holds:

$$ $q^{P,\phi,\mu}(x,\omega,a,x^{\prime}):=\mathbb{P}\Big{(}(x_{k},\omega_{k},a_{k },x_{k+1})=(x,\omega,a,x^{\prime})\mid P,\phi,\mu\Big{)},$ $$

which is the probability that the next state is $x^{\prime}$ after playing action $a$ in state $x$ when the realized outcome is $\omega$, under transition function $P$, signaling policy $\phi$, and prior function $\mu$.
Moreover, for ease of notation, we let:

$$ $\displaystyle q^{P,\phi,\mu}(x,\omega,a)$ $\displaystyle:=\sum_{x^{\prime}\in X_{k+1}}q^{P,\phi,\mu}(x,\omega,a,x^{\prime }),$ $\displaystyle q^{P,\phi,\mu}(x,\omega)$ $\displaystyle:=\sum_{a\in A}q^{P,\phi,\mu}(x,\omega,a),$ $\displaystyle q^{P,\phi,\mu}(x)$ $\displaystyle:=\sum_{\omega\in\Omega}q^{P,\phi,\mu}(x,\omega).$ $$

The following lemma characterizes the set of *valid* occupancy measures and it is a generalization to the MPP setting of a similar lemma by Rosenberg and Mansour ().

###### Lemma 1 .

A vector $q\in[0,1]^{|X\times\Omega\times A\times X|}$ is a valid occupancy measure of an MPP if and only if it holds:

$$ $\begin{cases}$\displaystyle \leavevmode\hbox to11.37pt{\vbox to11.37pt{ \pgfpicture\makeatletter\raise-2.46436pt\hbox{\hskip 5.68657pt\lower-5.68657pt \hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor} {rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{1}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}} \,\,\, \sum\limits_{x \in X_{k}}\sum\limits_ {\omega\in\Omega}\sum\limits_{a\in A}\sum\limits_{x^{\prime} \in X_{k+1}} q(x, \omega, a,x^{\prime})=1 \quad\,\,\, \hfill\forall k \in\mathcal{K} $ \ignorespaces\\ $\displaystyle \leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture \makeatletter\raise-2.46436pt\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to 0. 0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0 }\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0 }{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont \hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{2}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}} \,\,\, \sum\limits_{x^{\prime}\in X_{k-1}} \sum\limits_{\omega\in\Omega} \sum\limits_{a\in A}q(x^{\prime},\omega,a,x) = q (x) \hfill$\ignorespaces\\ $\displaystyle\hfill\forall k \in[1 \ldots L-1], \forall x \in X_{k} $ \ignorespaces\\ \leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\raise-2.46 436pt\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to 0.0pt{\pgfsys@beginscope \pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{3}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\,\,\,P^{q}=P\\ \leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\raise-2.46 436pt\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to 0.0pt{\pgfsys@beginscope \pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{4}}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\,\,\,\mu^{q}=\mu,\end{cases}$ $$

where $P$ is the transition function of the MPP and $\mu$ its prior function, while $P^{q}$ and $\mu^{q}$ are the transition and prior functions, respectively, induced by $q$ (see definitions below).

As it is the case in standard MDPs, a valid occupancy measure $q\in[0,1]^{|X\times\Omega\times A\times X|}$ induces a transition function $P^{q}$ and a signaling policy $\phi^{q}$, defined as follows:

$$ $P^{q}(x^{\prime}|x,\omega,a):=\frac{q(x,\omega,a,x^{\prime})}{q(x,\omega,a)}, \,\,\,\,\,\,\,\ \phi^{q}(a|x,\omega):=\frac{q(x,\omega,a)}{q(x,\omega)}.$ $$

Thus, using valid occupancy measures is *equivalent* to using signaling policies.
Moreover, in an MPP, a valid occupancy measure also induces a prior function $\mu^{q}$ defined so that:

$$ $\mu^{q}(\omega|x):=\frac{q(x,\omega)}{q(x)}.$ $$

In the following, we denote by $\mathcal{Q}\subseteq[0,1]^{|X\times\Omega\times A\times X|}$ the set of all the valid occupancy measures of an MPP.

###### Lemma 1 .

### 3.2 Learning Objectives

Our goal is to design learning algorithms for the sender in an episodic MPP.
In particular, we would like algorithms that prescribe sequences of signaling policies $\phi_{t}$ which maximize sender’s cumulative reward over the $T$ episodes, while at the same time guaranteeing that the violation of persuasiveness constraints is bounded.
Notice that, differently from Wu et al. (), we do *not* aim at designing learning algorithms whose policies $\phi_{t}$ are persuasive at every $t$ with high probability, since this is unattainable in our setting in which the sender does *not* know anything about receivers’ rewards (as implied by our Theorem 5 in Section 5).
Thus, in this paper we pursue a different objective, which we formally describe in the following.

#### Baseline

First, we introduce the baseline used to evaluate sender’s performances.
This is defined as the value of the optimization problem faced by the sender in the *offline* version of the MPP.
Such a problem is concerned with expectations of the stochastic quantities in the episodic MPP.
By exploiting occupancy measures, the problem can be formulated as the following linear program:

$$ $\displaystyle\max_{q\in\mathcal{Q}}$ $\displaystyle\quad\sum_{x\in X}\sum_{\omega\in\Omega}\sum_{a\in A}q(x,\omega,a )r_{S}(x,\omega,a)\quad\text{s.t.}\quad\phantom{a}$ (1a) $\displaystyle\sum_{\omega\in\Omega}q(x,\omega,a)\Big{(}r_{R}(x,\omega,a)-r_{R} (x,\omega,a^{\prime})\Big{)}\geq 0$ $\displaystyle\hfill\forall x\in X,\forall\omega\in\Omega,\forall a\in A, \forall a^{\prime}\neq a\in A.$ (1b) $$

Intuitively, Problem (3.2) computes an occupancy measure (or, equivalently, signaling policy) maximizing sender’s expected reward subject to persuasiveness constraints.
By letting $r_{S}\in[0,1]^{|X\times\Omega\times A|}$ be the vector whose entries are the mean values $r_{S}(x,\omega,a)$ of sender’s rewards, our baseline is defined as $\textsc{OPT}:=r_{S}^{\top}q^{*}$, where $q^{*}\in\mathcal{Q}$ is an optimal solution to Problem (3.2).
In the following, we also denote by $\phi^{*}$ an optimal signaling policy, namely $\phi^{*}:=\phi^{q^{*}}$.

#### Metrics

We evaluate the performances of learning algorithms by means of two distinct metrics.
The first one is the *(cumulative) regret* $R_{T}$, which accounts for the difference between the cumulative sender’s expected reward obtained by always playing $\phi^{*}$ and that achieved by using the signaling policies $\phi_{t}$ prescribed by the algorithm.
Formally:

$$ $R_{T}:=T\cdot\textsc{OPT}-\sum_{t\in[T]}r_{S}^{\top}q_{t}=\sum_{t\in[T]}r_{S}^ {\top}\big{(}q^{*}-q_{t}\big{)},$ $$

where we let $q_{t}:=q^{P,\phi_{t},\mu}$ be the occupancy induced by $\phi_{t}$.
The second metric used to evaluate learning algorithms is the *(cumulative) violation* $V_{T}$, which is formally defined as:

$$ $\displaystyle V_{T}:=\sum_{t\in[T]}\sum_{x\in X}\sum_{\omega\in\Omega}\sum_{a \in A}q_{t}(x,\omega,a)\big{(}r_{R}(x,\omega,b^{\phi}(a,x))-r_{R}(x,\omega,a) \big{)}.$ $$

Intuitively, $V_{T}$ encodes the overall expected loss in persuasiveness incurred by the algorithm over the $T$ episodes.

In the rest of the paper, our goal is to develop learning algorithms that prescribe signaling policies $\phi_{t}$ which guaranteeing that both $R_{T}$ and $V_{T}$ grow sublinearly in the number of episodes $T$, namely $R_{T}=o(T)$ and $V_{T}=o(T)$.

### 3.3 Confidence Bounds

Before delving in algorithm design, we introduce estimators and confidence bounds for the stochastic quantities involved in an MPP, namely, transitions, priors, sender’s rewards, and receivers’ ones.
As we show in the following sections, these are extensively used by our learning algorithms.

In the following, we let $N_{t}(x,\omega,a,x^{\prime})\in\mathbb{N}$ be the number of episodes up to episode $t\in[T]$ (this excluded) in which the tuple $(x,\omega,a,x^{\prime})$ is visited.
Formally, it holds $N_{t}(x,\omega,a,x^{\prime}):=\sum_{\tau\in[t-1]}\mathbbm{1}_{\tau}\{x,\omega,
a,x^{\prime}\}$, where the indicator function is equal to $1$ if and only if the tuple is visited at episode $\tau$.
Similarly, with a slight abuse of notation, we define the counters $N_{t}(x,\omega,a,)$, $N_{t}(x,\omega)$, and $N_{t}(x)$, in terms of their respective indicator functions $\mathbbm{1}_{\tau}\{x,\omega,a\}$, $\mathbbm{1}_{\tau}\{x,\omega\}$, and $\mathbbm{1}_{\tau}\{x\}$, which are equal to $1$ if and only if $(x,\omega,a)$, $(x,\omega)$, and $x$, respectively, are visited at $\tau$.

Next, we define the estimators employed by our algorithms.
At the beginning of episode $t\in[T]$, the estimated probability of going from $x\in X$ to $x^{\prime}\in X$ by playing $a\in A$, when the outcome realized in state $x$ is $\omega\in\Omega$, is as follows:

$$ $\overline{P}_{t}\left(x^{\prime}|x,\omega,a\right):=\frac{N_{t}(x,\omega,a,x^{ \prime})}{\max\left\{1,N_{t}(x,\omega,a)\right\}}.$ $$

Moreover, for every $x\in X$ and $\omega\in\Omega$, the estimated probability of sampling outcome $\omega$ from the prior distribution at state $x$ is computed as follows:

$$ $\overline{\mu}_{t}(\omega|x):=\frac{N_{t}(x,\omega)}{\max\{1,N_{t}(x)\}}.$ $$

Finally, for every $x\in X$, $\omega\in\Omega$, and $a\in A$, the estimated sender’s and receivers’ rewards are defined as follows:

$$ $\overline{r}_{S,t}(x,\omega,a):=\frac{\sum_{\tau\in[t-1]}r_{S,\tau}(x,\omega,a )\mathbbm{1}_{\tau}\{x,\omega,a\}}{{\max\{1,N_{t}(x,\omega,a)\}}}\,\,\,\,\,\, \ \overline{r}_{R,t}(x,\omega,a):=\frac{\sum_{\tau\in[t-1]}r_{R,\tau}(x,\omega ,a)\mathbbm{1}_{\tau}\{x,\omega,a\}}{\max\{1,N_{t}(x,\omega,a)\}}.$ $$

For reasons of space, we refer to Appendix B for the definitions of the confidence bounds employed by our algorithms.
For the transition function $P$, at each episode $t\in[T]$, for every $x\in X$, $\omega\in\Omega$, and $a\in A$, we provide a confidence bound $\epsilon_{t}(x,\omega,a)$ for the probability distribution over next states associated with the triplet $(x,\omega,a)$, where the distance between distributions is expressed in $\|\cdot\|_{1}$-norm (see Lemma 4).
Similarly, we provide a confidence bound $\zeta_{t}(x)$ in terms of $\|\cdot\|_{1}$-norm for the prior distribution $\mu(x)$ at each state $x\in X$ (see Lemma 5).
Moreover, for every $x\in X$, $\omega\in\Omega$, and $a\in A$, we provide confidence bounds $\xi_{S,t}(x,\omega,a)$ and $\xi_{R,t}(x,\omega,a)$ for sender’s and receivers’ rewards, respectively, associated with the triplet $(x,\omega,a)$ (see Lemmas 6 and 7 for the full feedback case, while Lemmas 8 and 9 for the partial feedback one).

In conclusion, for ease of presentation, for a confidence parameter $\delta\in(0,1)$, we refer to the event in which all the confidence bounds hold—called *clean event*—as $\mathcal{E}(\delta)$.
By combining all the lemmas in Appendix B, $\mathcal{E}(\delta)$ holds with probability at least $1-4\delta$ (by applying a union bound).

## 4 The Full Feedback Case

We first address settings with full feedback, as a warm up step towards the analysis of those with partial feedback.

### 4.1 The OPPS Algorithm with Full Feedback

We propose an algorithm called Optimisitc Persuasive Policy Search (OPPS).
At each episode, the algorithm solves a variation of the offline optimization problem (Problem (3.2)), called Opt-Opt, which is obtained by substituting mean values with upper/lower confidence bounds.
In particular, Opt-Opt is *optimistic* with respect to *both* sender’s rewards and persuasiveness constraints satisfaction.
For reasons of space, we defer the extensive definition of Opt-Opt to Problem (C) in Appendix C.
Crucially, by using occupancy measures, Opt-Opt can be formulated as a *linear program*, and, thus, it can be solved efficiently.
Notice that, since confidence bounds for $P$ and $\mu$ are expressed in terms of $||\cdot||_{1}$-norm, in order to formulate Opt-Opt as a linear program we need to introduce some additional variables and linear constraints, as described in detail in Appendix C.

Figure: Algorithm 2 Optimistic Persuasive Policy Search *(full)*

Algorithm 2 provides the pseudocode of OPPS with *full* feedback.
At each $t\in[T]$, the algorithm first updates all the estimators and confidence bounds according to the feedback received in previous episodes (Line 4).
Then, it commits to the signaling policy $\phi_{t}$ induced by an optimal solution $\widehat{q}_{t}$ to Opt-Opt, computed in Line 5.
Notice that, the occupancy measure $q_{t}$ resulting from committing to $\phi_{t}$ (and used in the definitions of $R_{T}$ and $V_{T}$) is in general different from $\widehat{q}_{t}$, as the former is defined in terms of the true (and unknown) transition and prior functions, namely $P$ and $\mu$.

### 4.2 Algorithm Analysis with Full Feedback

Next, we prove the guarantees of OPPS with *full* feedback.

The first crucial component that we need for our analysis is the following lemma, which shows that Opt-Opt admits a feasible solution at every episode with high probability.

###### Lemma 2 .

For any $\delta\in(0,1)$, under the clean event $\mathcal{E}(\delta)$, Opt-Opt admits a feasible solution for every $t\in[T]$.

Intuitively, Lemma 2 is proved by showing (a) that Problem 3.2 always admits a feasible solution, which is the occupancy measure $q^{\diamond}$ induced by the signaling policy that fully reveals outcomes to the receiver, and (b) that $q^{\diamond}$ is a feasible solution to Opt-Opt at every episode, under $\mathcal{E}(\delta)$.
Notice that point (b) holds thanks to the fact that Opt-Opt optimistically accounts for persuasiveness constraints satisfaction, by using suitable upper/lower confidence bounds.

The second crucial component of our analysis is a relation between the occupancy measures $\widehat{q}_{t}$ computed by the OPPS algorithm and the occupancy measures $q_{t}$ that actually result from committing to $\phi_{t}$ under the true transitions and priors.
This is formally stated by the following lemma.

###### Lemma 3 .

For $\delta\in(0,1)$, under the clean event $\mathcal{E}(\delta)$, with probability at least $1-2\delta$:

$$ $\sum_{t\in[T]}\|q_{t}-\widehat{q}_{t}\|_{1}\leq\mathcal{O}\left(L^{2}|X|\sqrt{ T|A||\Omega|\ln\left(\nicefrac{{T|X||\Omega||A|}}{{\delta}}\right)}\right).$ $$

Intuitively, Lemma 3 is proved by an inductive argument that relates the uncertainty associated with both the transition and the prior functions to the $\|\cdot\|_{1}$-norm difference between $q_{t}$ and $\widehat{q}_{t}$ cumulated over the episodes.

Lemmas 2 and 3 pave the way to our two main theorems for the full feedback setting.
The first theorem bounds the regret $R_{T}$ achieved by OPPS, while the second one bounds its cumulative violation $V_{T}$.
Formally:

###### Theorem 1 .

Given any $\delta\in(0,1)$, with probability at least $1-7\delta$, Algorithm 2 attains regret:

$$ $R_{T}\leq\widetilde{\mathcal{O}}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac {1}{\delta}\right)}\right).$ $$

###### Theorem 2 .

Given any $\delta\in(0,1)$, with probability at least $1-7\delta$, Algorithm 2 attains cumulative violation:

$$ $V_{T}\leq\widetilde{\mathcal{O}}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac {1}{\delta}\right)}\right).$ $$

In conclusion, in the *full* feedback case, the OPPS algorithm attains regret and violation growing as $\widetilde{\mathcal{O}}(\sqrt{T})$.
Intuitively, this is made effective by the fact that all the estimators concentrate at a $\widetilde{\mathcal{O}}(1/\sqrt{T})$ rate.
As shown in the following section, achieving such regret and violation bounds is *not* possible anymore under *partial* feedback.

###### Lemma 2 .

###### Lemma 3 .

###### Theorem 1 .

###### Theorem 2 .

## 5 The Partial Feedback Case

In this section, we switch the attention to partial feedback.

The crucial aspect that makes the case of partial feedback more challenging than the one of full feedback is that, after committing to a signaling policy $\phi_{t}$, the sender does *not* observe sufficient feedback about the persuasiveness of $\phi_{t}$.
This makes achieving sublinear violation in the partial feedback case much harder than in the full feedback case.
In order to overcome such a challenge, some episodes of learning must be devoted to the estimation of the quantities involved in persuasiveness constraints.
This is necessary to build a suitable approximation of such constraints to be exploited in the remaining episodes, in which an optimistic approach similar to that employed with full feedback must be adopted to control the regret.
As a result, there is a trade-off between regret and violation that is determined by the amount of exploration performed.
In the rest of this section, we design an algorithm that is able to optimally control such a trade-off.

### 5.1 The OPPS Algorithm with Partial Feedback

We extend the OPPS algorithm introduced in Section 4 to deal with the *partial* feedback case.
The idea behind the new algorithm is to split episodes into two phases.
The *first* one is an exploration phase with the goal of building a sufficiently-good approximation of persuasiveness constraints, so as to achieve sublinear violation.
Such a phase lasts for the first $N|X||\Omega||A|$ episodes, where $N:=\left\lceil T^{\alpha}\right\rceil$ and $\alpha\in[0,1]$ is a parameter controlling the length of the two phases, given as input to the algorithm.
The *second* phase is instead devoted to achieving sublinear regret, and it follows the same steps of OPPS with full feedback (Algorithm 2).

The first phase of the algorithm works by considering each triplet $(x,\omega,a)\in X\times\Omega\times A$ for $N$ episode.
When $(x,\omega,a)$ is considered at episode $t\in[T]$, the algorithm commits to a signaling scheme induced by an occupancy measure $\widehat{q}_{t}$ that maximizes the probability $\sum_{x^{\prime}\in X}q(x,\omega,a,x^{\prime})$ of visiting such a triplet, while at the same time satisfying all the constraints of the Opt-Opt problem.
Crucially, such a procedure does *not* guarantee that every triplet is visited $N$ times.
Indeed, there might be triplets $(x,\omega,a)$ that are visited with very low probability.
This can be the case either when transitions and priors place very low probability on $(x,\omega)$ or when action $a$ is associated with very low receivers’ rewards, and, thus, it must be recommended with very low probability in order to satisfy the optimistic persuasiveness constraints defined in the Opt-Opt problem.

Figure: Algorithm 3 Optimistic Persuasive Policy Search *(partial)*

Algorithm 3 provides the pseudocode of OPPS with *partial* feedback.
Notice that the variables $C(x,\omega,a)$ (initialized in Line 4 and updated in Line 10) are counters used to keep track of how many times each triplet $(x,\omega,a)$ is considered during the first phase, namely when $t\leq N|X||\Omega||A|$.
Moreover, the algorithm ensures that every triplet si considered exactly $N$ times during the first phase, by selecting them accordingly as in Line 8.
Let us also observe that Algorithm 3 updates all the estimators and bounds (by using partial feedback) and selects the signaling policy $\phi_{t}$ as done by Algorithm 2.
The main difference with respect to Algorithm 2 is that the occupancy measure $\widehat{q}_{t}$ used to define $\phi_{t}$ is computed in a different way during the first (exploration) phase of the algorithm (see Line 9).

### 5.2 Algorithm Analysis with Partial Feedback

In the following, we prove the guarantees attained by OPPS with *partial* feedback.
We start by stating the following result on the regret attained by the algorithm.

###### Theorem 3 .

Given any $\delta\in(0,1)$, with probability at least $1-7\delta$, Algorithm 3 attains regret:

$$ $R_{T}\leq\widetilde{\mathcal{O}}\left(NL|X||\Omega||A|+L^{2}|X|\sqrt{T|A|| \Omega|\ln\left(\frac{1}{\delta}\right)}\right).$ $$

In order to prove Theorem 3, we split the analysis into two cases: one targets exploration episodes in the first phase of the algorithm, while the other is concerned with the subsequent (exploitation) phase.
In the first $N$ episodes in which the OPPS algorithm explores without being driven by the Opt-Opt objective, the algorithm incurs in linear regret.
Instead, in the second phase, OPPS employs an optimistic approach, since the algorithm is driven by the objective of the Opt-Opt problem.
Thus, in the second phase, the algorithm attains regret sublinear in $T$.
The two cases combined give the regret bound in Theorem 3.

In the following, we state the result on the violations attained by the OPPS algorithm under *partial* feedback.

###### Theorem 4 .

Given any $\delta\in(0,1)$, with probability at least $1-9\delta$, Algorithm 3 attains cumulative violation:

$$ $V_{T}\leq\widetilde{\mathcal{O}}\left(\rho\left(|A|\frac{T}{\sqrt{N}}+|A|\sqrt {N}+L^{2}\sqrt{T}\right)\right),$ $$

where $\rho:=(|X||\Omega||A|)^{3/2}\sqrt{\ln\left(\nicefrac{{1}}{{\delta}}\right)}.$

Proving Theorem 4 requires a non-trivial analysis.
The result follows by showing that uniformly exploring over feasible solutions to the Opt-Opt problem leads to a violation bound of the order of $\mathcal{O}(\sqrt{N})$ during the exploration phase.
Intuitively, this follows by upper bounding the occupancy of each triplet $(x,\omega,a)$ with an occupancy of a previous (exploration) episode relative to the best response of the follower in state $x$ upon receiving recommendation $a$.

Theorems 3 and 4 establish the trade-off between regret and violation achieved by the OPPS algorithm.
Indeed, by recalling the definition of $N$ (see Line 2 in Algorithm 3), it is easy to see that the algorithm attains $R_{T}\leq\widetilde{\mathcal{O}}(T^{\alpha})$ and $V_{T}\leq\widetilde{\mathcal{O}}(T^{1-\nicefrac{{\alpha}}{{2}}})$, where $\alpha\in[\nicefrac{{1}}{{2}},1]$ is the parameter controlling the trade-off, given as input to the algorithm.

###### Theorem 3 .

###### Theorem 4 .

### 5.3 Lower Bound

We conclude the section by showing that the regret and violation bounds attained by the OPPS algorithm are tight for any choice of $\alpha\in[\nicefrac{{1}}{{2}},1]$.
We do so by devising a lower bound matching these bounds (Theorem 5).
Its main idea is to consider two instances of episodic MPP involving a receiver with two actions $a_{1},a_{2}$ such that only $a_{1}$ provides positive reward to the sender.
In one instance, receiver’s rewards by playing $a_{1}$ are higher than those obtained by taking $a_{2}$, while in the second instance the opposite holds.
As a result, recommending action $a_{1}$ results in low regret in the first instance and high violation in the second one, while recommending action $a_{2}$ results in low violation in the second instance and high regret in the first one.
This leads to the trade-off formally stated by the following theorem.

###### Theorem 5 .

Given $\alpha\in[1/2,1]$, there is no learning algorithm achieving both $R_{T}=o(T^{\alpha})$ and $V_{T}=o(T^{1-\nicefrac{{\alpha}}{{2}}})$ with probability at least $1-\delta$, for any $\delta\in(0,1)$.

Theorem 5 shows that the bounds in Theorems 3 and 4 are tight for any $\alpha\in[\nicefrac{{1}}{{2}},1]$.
Moreover, it also proves that it is impossible to achieve sublinear regret while being persuasive at every episode with high probability, when the sender has no information about the receivers.

Notice that, in our MPP setting with partial feedback, we deal with a trade-off between regret and violation that is similar to the one faced by Bernasconi et al. () in related settings.
Differently from them, we are able to achieve an optimal trade-off for any $\alpha\in[\nicefrac{{1}}{{2}},1]$.
Indeed, Bernasconi et al. () only obtain optimality for $\alpha\in[\nicefrac{{1}}{{2}},\nicefrac{{2}}{{3}}]$, leaving as an open problem matching the lower bound for the other values of the parameter $\alpha$.
Crucially, we are able to achieve trade-off optimality by using a clever exploration method.
Indeed, when considering a triplet $(x,\omega,a)$ in the first phase, the OPPS algorithm does *not* simply commits to a signaling policy that maximizes the probability of visiting such a triplet, but it rather does so while also *optimistically* accounting for persuasiveness constraints.
This allows to reduce the violation cumulated during the first phase, thus achieving trade-off optimality.

###### Theorem 5 .

## Appendix

The appendix is organized as follows:

- •
In Appendix A we report additional related works concerning the online learning in Markov decision processes and online Bayesian persuasion literatures.
- •
In Appendix B we describe the estimators and the confidence bounds related to the stochastic quantities of the Markov persuasive processes.
- •
In Appendix C we report the per-round optimization problem performed by the algorithms we present.
- •
In Appendix D we report the omitted proofs related to the *full-feedback* setting.
- •
In Appendix E we report the omitted proofs related to the *partial-feedback* setting.

## Appendix A Additional Related Works

#### Online learning in Constrained MDPs

Our paper is also related to the problem of designing no-regret algorithms in online constrained Markov decision processes. The literature on online learning in Markov decision processes is extensive (see, *e.g.*, Auer et al. (); Even-Dar et al. (); Neu et al. () for fundamental works on the topic). In such settings, two types of feedback are usually investigated. The full-information feedback setting (Rosenberg and Mansour, ), in which the entire reward function is observed after the learner’s choice and the partial feedback setting (Jin et al., ), where the learner only observes the reward gained during the episode. Over the last decade, there has been significant attention to the field of online Markov decision processes in presence of constraints. The majority of previous works on this topic have focused on settings where constraints are stochastically sampled from a fixed distribution (see, *e.g.*, Zheng and Ratliff ()). Wei et al. () deal with adversarial reward and stochastic constraints, assuming known transition probabilities and full information feedback.
Efroni et al. () propose two approaches to address the exploration-exploitation dilemma in episodic constrained MDPs. These approaches guarantee sublinear regret and constraint violation when transition probabilities, rewards, and constraints are unknown and stochastic, and the feedback is partial.
Qiu et al. () provide a primal-dual approach based on optimism in the face of uncertainty. This work shows the effectiveness of such an approach when dealing with episodic constrained MDPs with adversarial rewards and stochastic constraints, achieving both sublinear regret and constraint violation with full-information feedback. Finally, Germano et al. () propose a best-of-both-worlds algorithm in constrained Markov decision processes with full information feedback. While the previous works are related to ours, the aforementioned techniques cannot be easily generalized to our setting as they are not designed to properly handle the presence of outcomes and IC constraints.

#### Online Bayesian Persuasion

It is also worth citing some works that study learning problems in which a one-shot Bayesian persuasion setting is played repeatedly (Castiglioni et al., , ; Zu et al., ; Bernasconi et al., ).
These works considerably depart from ours, since they do *not* consider any kind of sequential structure in the sender-receiver interaction at each episode.

## Appendix B Confidence Bounds

In this section, we further describe the estimators and confidence bounds for the stochastic quantities involved in an episodic MPP, namely, transitions, priors, sender’s rewards, and receivers’ ones.

### B.1 Transition Probabilities

First, we introduce confidence bounds for transition probabilities $P(x^{\prime}|x,\omega,a)$, by generalizing those introduced by Rosenberg and Mansour () for MDPs to MPPs.
In the following, we let $N_{t}(x,\omega,a)$, respectively $N_{t}(x,\omega,a,x^{\prime})$, be the counter specifying the number of episodes up to episode $t\in[T]$ (excluded) in which the triplet $(x,\omega,a)$, respectively the tuple $(x,\omega,a,x^{\prime})$, is visited.
Then, the estimated probability of going from $x\in X$ to $x^{\prime}\in X$ by playing action $a\in A$, when the outcome realized in state $x$ is $\omega\in\Omega$, is defined as follows:

$$ $\overline{P}_{t}\left(x^{\prime}|x,\omega,a\right):=\frac{N_{t}(x,\omega,a,x^{ \prime})}{\max\left\{1,N_{t}(x,\omega,a)\right\}}.$ $$

For any $\delta\in(0,1)$, the confidence set at episode $t\in[T]$ for the transition function $P$ is $\mathcal{P}_{t}:=\bigcap_{(x,\omega,a)\in X\times\Omega\times A}\mathcal{P}_{t
}^{x,\omega,a}$, where $\mathcal{P}_{t}^{x,\omega,a}$ is a set of transition functions defined as:

$$ $\mathcal{P}_{t}^{x,\omega,a}:=\Big{\{}\widehat{P}:\left\|\widehat{P}(\cdot|x, \omega,a)-\overline{P}_{t}(\cdot|x,\omega,a)\right\|_{1}\leq\epsilon_{t}(x, \omega,a)\Big{\}},$ $$

where $\widehat{P}(\cdot|x,\omega,a)$ and $\overline{P}_{t}(\cdot|x,\omega,a)$ are vectors whose entries are the values $\widehat{P}(x^{\prime}|x,\omega,a)$ and $\overline{P}_{t}(x^{\prime}|x,\omega,a)$, respectively, while $\epsilon_{t}(x,\omega,a)$ is a confidence bound defined as:

$$ $\epsilon_{t}(x,\omega,a):=\sqrt{\frac{2|X_{k(x)+1}|\ln\left(\nicefrac{{T|X|| \Omega||A|}}{{\delta}}\right)}{\max\left\{1,N_{t}(x,\omega,a)\right\}}}.$ $$

The following lemma formally proves that $\mathcal{P}_{t}$ is a suitable confidence set for the transition function of an MPP.

###### Lemma 4 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following condition holds for every $x\in X$, $\omega\in\Omega$, $a\in A$, and $t\in[T]$ jointly:

$$ $\left\|P(\cdot|x,\omega,a)-\overline{P}_{t}(\cdot|x,\omega,a)\right\|_{1}\leq \epsilon_{t}(x,\omega,a).$ $$

Lemma 4 can be easily proven by applying the same analysis as presented in (Auer et al., ) and employing a union bound over all $x$, $\omega$, $a$, and $t$..

###### Lemma 4 .

### B.2 Prior Distributions

Next, we introduce confidence bounds for prior distributions.
For every state $x\in X$, we define $\overline{\mu}_{t}(\cdot|x)\in\Delta(\Omega)$ as the estimator of the prior distribution at $x$ built by using observations up to episode $t\in[T]$ (this excluded).
Formally, the entries of vector $\overline{\mu}_{t}(\cdot|x)$ are such that, for every $\omega\in\Omega$:

$$ $\overline{\mu}_{t}(\omega|x):=\frac{\sum_{\tau\in[t-1]}\mathbbm{1}_{\tau}\{x, \omega\}}{\max\{1,N_{t}(x)\}},$ $$

where $N_{t}(x)$ is the number of visits to state $x$ up to episode $t$ (excluded), while $\mathbbm{1}_{\tau}\{x,\omega\}$ is an indicator function equal to $1$ if and only if the pair $(x,\omega)$ is visited at episode $\tau$.

The following lemma provides confidence bounds for priors.

###### Lemma 5 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following holds for all $x\in X$ and $t\in[T]$ jointly:

$$ $\left\|\mu(\cdot|x)-\overline{\mu}_{t}(\cdot|x)\right\|_{1}\leq\zeta_{t}(x),$ $$

where we let $\zeta_{t}(x):=\sqrt{\frac{2|\Omega|\ln(\nicefrac{{T|X|}}{{\delta}})}{\max\{1,N
_{t}(x)\}}}$.

Lemma 5 follows by applying Bernstein’s inequality and a union bound over all states and episodes.

###### Lemma 5 .

### B.3 Sender’s and Receivers’ Rewards

Finally, we introduce estimators for rewards.
In the following, present the results related to sender’s rewards and receiver’s rewards under full and partial feedback.
For every $x\in X$, $\omega\in\Omega$, and $a\in A$, the estimated sender’s and receivers’ rewards built with observations up to episode $t\in[T]$ (this excluded) are defined as follows:

$$ $\displaystyle\overline{r}_{S,t}(x,\omega,a)$ $\displaystyle:=\frac{\sum_{\tau\in[t-1]}r_{S,\tau}(x,\omega,a)\mathbbm{1}_{ \tau}\{x,\omega,a\}}{{\max\{1,N_{t}(x,\omega,a)\}}},$ $\displaystyle\overline{r}_{R,t}(x,\omega,a)$ $\displaystyle:=\frac{\sum_{\tau\in[t-1]}r_{R,\tau}(x,\omega,a)\mathbbm{1}_{ \tau}\{x,\omega,a\}}{\max\{1,N_{t}(x,\omega,a)\}},$ $$

where $\mathbbm{1}_{\tau}\{x,\omega,a\}$ is an indicator function equal to $1$ if and only if the triplet $(x,\omega,a)$ is visited during episode $\tau$.

The following lemma provides confidence bounds for sender’s rewards, when *full* feedback is available.

###### Lemma 6 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following condition holds for every $x\in X$, $\omega\in\Omega$, $a\in A$, and $t\in[T]$ jointly:

$$ $\big{|}r_{S}(x,\omega,a)-\overline{r}_{S,t}(x,\omega,a)\big{|}\leq\xi_{S,t}(x, \omega,a),$ $$

where $\xi_{S,t}(x,\omega,a):=\min\left\{1,\sqrt{\frac{\ln(\nicefrac{{3T|X||\Omega|}}
{{\delta}})}{\max\{1,N_{t}(x,\omega)\}}}\right\}$.

Lemma 6 follows by applying Hoeffding’s inequality and a union bound over all $x$, $\omega$ and $t$.

The following lemma provides confidence bounds for receiver’s rewards, when *full* feedback is available.

###### Lemma 7 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following condition holds for every $x\in X$, $\omega\in\Omega$, $a\in A$, and $t\in[T]$ jointly:

$$ $\big{|}r_{R}(x,\omega,a)-\overline{r}_{R,t}(x,\omega,a)\big{|}\leq\xi_{R,t}(x, \omega,a),$ $$

where $\xi_{R,t}(x,\omega,a):=\min\left\{1,\sqrt{\frac{\ln(\nicefrac{{3T|X||\Omega|}}
{{\delta}})}{\max\{1,N_{t}(x,\omega)\}}}\right\}$.

Lemma 7 follows by applying Hoeffding’s inequality and a union bound over all $x$, $\omega$ and $t$.

The following lemma provides confidence bounds for sender’s rewards, when only *partial* feedback is available.

###### Lemma 8 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following condition holds for every $x\in X$, $\omega\in\Omega$, $a\in A$, and $t\in[T]$ jointly:

$$ $\big{|}r_{S}(x,\omega,a)-\overline{r}_{S,t}(x,\omega,a)\big{|}\leq\xi_{S,t}(x, \omega,a),$ $$

where $\xi_{S,t}(x,\omega,a):=\min\left\{1,\sqrt{\frac{\ln(\nicefrac{{3T|X||\Omega||A
|}}{{\delta}})}{\max\{1,N_{t}(x,\omega,a)\}}}\right\}$.

Lemma 8 follows by applying Hoeffding’s inequality and a union bound over all $x$, $\omega$, $a$, and $t$.

Finally, the following lemma provides confidence bounds for receiver’s rewards, when only *partial* feedback is available.

###### Lemma 9 .

Given any $\delta\in(0,1)$, with probability at least $1-\delta$, the following condition holds for every $x\in X$, $\omega\in\Omega$, $a\in A$, and $t\in[T]$ jointly:

$$ $\big{|}r_{R}(x,\omega,a)-\overline{r}_{R,t}(x,\omega,a)\big{|}\leq\xi_{R,t}(x, \omega,a),$ $$

where $\xi_{R,t}(x,\omega,a):=\min\left\{1,\sqrt{\frac{\ln(\nicefrac{{3T|X||\Omega||A
|}}{{\delta}})}{\max\{1,N_{t}(x,\omega,a)\}}}\right\}$.

Lemma 9 follows by applying Hoeffding’s inequality and a union bound over all $x$, $\omega$, $a$, and $t$.

###### Lemma 6 .

###### Lemma 7 .

###### Lemma 8 .

###### Lemma 9 .

## Appendix C Optimistic optimization problem

In the following section we describe the linear program solved by Algorithm 2 and Algorithm 3, namely Opt-Opt. Intuitively, Opt-Opt is the optimistic version of Program (3.2), since the objective is guided by the optimism and the confidence bounds of the estimated parameters are chosen to make constraints easier to be satisfied. Notice that the confidence bounds on the transitions and the prior are applied to the $\|\cdot\|_{1}$ differences between the empirical and the real mean of the distributions. Thus, in order to insert the aforementioned confidence bounds in a LP-formulation, the related constraints must be linearized by means of additional optimization variables.

The linear program solved by Algorithm 2 and Algorithm 3 is the following.

$$ $\displaystyle\max_{q,\zeta,\epsilon}$ $\displaystyle\quad\sum_{x\in X_{k}}\sum_{\omega\in\Omega}\sum_{a\in A}\sum_{x^ {\prime}\in X_{k+1}}q(x,\omega,a,x^{\prime})\big{(}\overline{r}_{S,t}(x,\omega ,a)+\xi_{S,t}(x,\omega,a)\big{)}\quad\text{s.t.}\hskip 110.96556pt\phantom{ \text{s.t.}}$ (2a) $\displaystyle\sum_{x\in X_{k}}\sum_{\omega\in\Omega}\sum_{a\in A}\sum_{x^{ \prime}\in X_{k+1}}q(x,\omega,a,x^{\prime})=1\hfill\forall k\in[0\dots L-1]$ (2b) $\displaystyle\sum_{x^{\prime}\in X_{k-1}}\sum_{\omega\in\Omega}\sum_{a\in A}q( x^{\prime},\omega,a,x)=\sum_{\omega\in\Omega}\sum_{a\in A}\sum_{x^{\prime}\in X _{k+1}}q(x,\omega,a,x^{\prime})\hfill\forall k\in[0\dots L-1],\forall x\in X_{k}$ (2c) $\displaystyle q(x,\omega,a,x^{\prime})-\overline{P}_{t}(x^{\prime}|x,\omega,a) \sum_{x^{\prime\prime}\in X_{k+1}}q(x,\omega,a,x^{\prime\prime})\leq\epsilon(x ,\omega,a,x^{\prime})$ $\displaystyle\hfill\forall k\in[0\ldots L-1],\forall(x,\omega,a,x^{\prime})\in X _{k}\times\Omega\times A\times X_{k+1}$ (2d) $\displaystyle\overline{P}_{t}(x^{\prime}|x,a,\omega)\sum_{x^{\prime\prime}\in X _{k+1}}q(x,\omega,a,x^{\prime\prime})-q(x,\omega,a,x^{\prime})\leq\epsilon(x, \omega,a,x^{\prime})$ $\displaystyle\hfill\forall k\in[0\ldots L-1],\forall(x,\omega,a,x^{\prime})\in X _{k}\times\Omega\times A\times X_{k+1}$ (2e) $\displaystyle\sum_{x^{\prime}\in X_{k+1}}\epsilon(x,\omega,a,x^{\prime})\leq \epsilon_{t}(x,\omega,a)\sum_{x^{\prime}\in X_{k+1}}q(x,\omega,a,x^{\prime}) \hfill\forall k\in[0\ldots L-1],\forall(x,\omega,a)\in X_{k}\times\Omega\times A$ (2f) $\displaystyle q(x,\omega)-\overline{\mu}_{t}(\omega|x)\sum_{\omega^{\prime}\in \Omega}q(x,\omega^{\prime})\leq\zeta(x,\omega)\hfill\forall k\in[0\dots L-1], \forall(x,\omega)\in X_{k}\times\Omega$ (2g) $\displaystyle\overline{\mu}_{t}(\omega|x)\sum_{\omega^{\prime}\in\Omega}q(x, \omega^{\prime})-q(x,\omega)\leq\zeta(x,\omega)\hfill\forall k\in[0\dots L-1], \forall(x,\omega)\in X_{k}\times\Omega$ (2h) $\displaystyle\sum_{\omega\in\Omega}\zeta(x,\omega)\leq\zeta_{t}(x)\sum_{\omega \in\Omega}q(x,\omega),\hfill\forall k\in[0\dots L-1],\forall x\in X_{k}$ (2i) $\displaystyle\sum_{\omega\in\Omega}\sum_{x^{\prime}\in X_{k+1}}q(x,\omega,a,x^ {\prime})\big{(}\overline{r}_{R,t}(x,\omega,a)+\xi_{R,t}(x,\omega,a)-\overline {r}_{R,t}(x,\omega,a^{\prime})+\xi_{R,t}(x,\omega,a^{\prime})\big{)}\geq 0$ $\displaystyle\hfill\forall k\in[0\dots L-1],\forall(x,a)\in X_{k}\times A, \forall a^{\prime}\in A$ (2j) $\displaystyle q(x,\omega,a,x^{\prime})\geq 0\hfill\forall k\in[0\dots L-1], \forall(x,a,x^{\prime})\in X_{k}\times\Omega\times A\times X_{k+1},$ (2k) $$

where Objective (2a) maximizes the upper confidence bound of the sender reward, Constraint (2b) ensures that the occupancy measure sums to $1$ for every layer, Constraint (2c) is the flow constraint, Constraint (2d) is related to the confidence interval on the transition functions, Constraint (2e) is still related to the confidence bounds on the transition function, Constraint (2f) allows to write linearly the constraints related to the transition functions even if the interval holds for the $\|\cdot\|_{1}$,
Constraint (2g) is related to the confidence interval on the outcomes, Constraint (2h) is still related to the confidence bounds on the outcomes, Constraint (2i) allows to write linearly the constraints related to the outcomes even if the interval holds for the $\|\cdot\|_{1}$,
Constraint (2j) is the optimistic constraint for the Incentive Compatibility (IC) property and, finally, Constraint (2k) ensures that the occupancy are greater than zero.

See 2

###### Proof.

First we notice that under the clean event $\mathcal{E}(\delta)$ the true transition function $P$ and the prior $\mu$ are included in the their confidence interval; thus, they are available in the constrained space defined by Opt-Opt. Then, we focus on the incentive compatibility constraints. Referring as $q^{\diamond}$ to an incentive compatible occupancy measure, under $\mathcal{E}(\delta)$, we have that:

$$ $\displaystyle\sum_{\omega\in\Omega,x^{\prime}\in X_{k+1}}q^{\diamond}(x,\omega ,a,x^{\prime})\left(\overline{r}_{R,t}(x,\omega,a)+\xi_{R,t}(x,\omega,a)- \overline{r}_{R,t}(x,\omega,\bar{a})+\xi_{R,t}(x,\omega,\overline{a})\right)\geq$ $\displaystyle\sum_{\omega\in\Omega,x^{\prime}\in X_{k+1}}q^{\diamond}(x,\omega ,a,x^{\prime})\left(r_{R}(x,\omega,a)-r_{R}(x,\omega,\bar{a})\right)\geq 0,$ $$

for any $k\in[L-1],(x,a)\in X_{k}\times A,\forall\bar{a}\in A$. As a result, if $q^{\diamond}$ is incentive compatible, it belongs to the optimistic decision space, which concludes the proof.
∎

###### Proof.

## Appendix D Full feedback

In this section we report the omitted proof related to Algorithm 2. Notice that the bound on the transition function estimations still hold when the feedback is partial.

### D.1 Transition functions

We start by showing that the estimated occupancy measures which encompass the information related to the outcomes and the transitions concentrate with respect to the true occupancy measures.

See 3

###### Proof.

We start noticing that, for any $(x,\omega,a)\in X\times\Omega\times A$, we have:

$$ $\displaystyle\sum_{x^{\prime}\in X_{k(x)+1}}$ $\displaystyle|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a,x^{\prime})-q^{P,\phi_{t}, \mu}(x,\omega,a,x^{\prime})|$ $\displaystyle=\sum_{x^{\prime}\in X_{k(x)+1}}\left|q^{P_{t},\phi_{t},\mu_{t}}( x,\omega,a)P_{t}(x^{\prime}|x,\omega,a)-q^{P,\phi_{t},\mu}(x,\omega,a)P(x^{ \prime}|x,\omega,a)\right|$ $\displaystyle\leq\sum_{x^{\prime}\in X_{k(x)+1}}\left|q^{P_{t},\phi_{t},\mu_{t }}(x,\omega,a)P_{t}(x^{\prime}|x,\omega,a)-q^{P,\phi_{t},\mu}(x,\omega,a)P_{t} (x^{\prime}|x,\omega,a)\right|$ $\displaystyle\ \ \ +\sum_{x^{\prime}\in X_{k(x)+1}}\left|q^{P,\phi_{t},\mu}(x, \omega,a)P_{t}(x^{\prime}|x,\omega,a)-q^{P,\phi_{t},\mu}(x,\omega,a)P(x^{ \prime}|x,\omega,a)\right|$ $\displaystyle=\sum_{x^{\prime}\in X_{k(x)+1}}\left|q^{P_{t},\phi_{t},\mu_{t}}( x,\omega,a)-q^{P,\phi_{t},\mu}(x,\omega,a)\right|P_{t}(x^{\prime}|x,\omega,a)$ $\displaystyle\ \ \ +\sum_{x^{\prime}\in X_{k(x)+1}}q^{P,\phi_{t},\mu}(x,\omega ,a)\left|P_{t}(x^{\prime}|x,\omega,a)-P(x^{\prime}|x,\omega,a)\right|$ $\displaystyle=\left|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a)-q^{P,\phi_{t},\mu}( x,\omega,a)\right|+q^{P,\phi_{t},\mu}(x,\omega,a)\|P_{t}(\cdot|x,\omega,a)-P( \cdot|x,\omega,a)\|_{1}.$ $$

Thus, summing over $t\in[T]$ and $(x,\omega,a)\in X\times\Omega\times A$ we obtain:

$$ $\displaystyle\sum_{t\in[T]}\|q_{t}-\widehat{q}_{t}\|_{1}\leq\sum_{t\in[T]}\sum _{x\in X,\omega\in\Omega,a\in A}$ $\displaystyle\Big{(}\left|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a)-q^{P,\phi_{t} ,\mu}(x,\omega,a)\right|$ $\displaystyle+q^{P,\phi_{t},\mu}(x,\omega,a)\|P_{t}(\cdot|x,\omega,a)-P(\cdot| x,\omega,a)\|_{1}\Big{)}.$ $$

Next, we focus on the first part of the equation, noticing that:

$$ $\displaystyle\left|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a)-q^{P,\phi_{t},\mu}(x ,\omega,a)\right|\leq\left|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a)-q^{P_{t}, \phi_{t},\mu}(x,\omega,a)\right|+\left|q^{P_{t},\phi_{t},\mu}(x,\omega,a)-q^{P ,\phi_{t},\mu}(x,\omega,a)\right|$ $$

###### Proof.

#### Bound on | q P t , ϕ t , μ t ⁢ ( x , ω , a ) − q P t , ϕ t , μ ⁢ ( x , ω , a ) | superscript 𝑞 subscript 𝑃 𝑡 subscript italic-ϕ 𝑡 subscript 𝜇 𝑡 𝑥 𝜔 𝑎 superscript 𝑞 subscript 𝑃 𝑡 subscript italic-ϕ 𝑡 𝜇 𝑥 𝜔 𝑎 \left|q^{P_{t},\phi_{t},\mu_{t}}(x,\omega,a)-q^{P_{t},\phi_{t},\mu}(x,\omega,a%
)\right| | italic_q start_POSTSUPERSCRIPT italic_P start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_ϕ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT end_POSTSUPERSCRIPT ( italic_x , italic_ω , italic_a ) - italic_q start_POSTSUPERSCRIPT italic_P start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_ϕ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ end_POSTSUPERSCRIPT ( italic_x , italic_ω , italic_a ) |

We bound this term by induction. At the first layer we have:

$$ $\displaystyle\sum_{x_{0}\in X_{0}}\sum_{\omega_{0}\in\Omega}\sum_{a_{0}\in A}$ $\displaystyle\left|q^{P_{t},\phi_{t},\mu_{t}}(x_{0},\omega_{0},a_{0})-q^{P_{t} ,\phi_{t},\mu}(x_{0},\omega_{0},a_{0})\right|$ $\displaystyle=\sum_{\omega_{0}\in\Omega}\sum_{a_{0}\in A}\left|\mu_{t}(x_{0}, \omega_{0})\phi_{t}(a_{0}|x_{0},\omega_{0})-\mu(x_{0},\omega_{0})\phi_{t}(a_{0 }|x_{0},\omega_{0})\right|$ $\displaystyle\leq\sum_{\omega_{0}\in\Omega}\left|\mu_{t}(x_{0},\omega_{0})-\mu (x_{0},\omega_{0})\right|$ $\displaystyle=q^{P_{t},\phi_{t},\mu}(x_{0})\sum_{\omega_{0}\in\Omega}\left|\mu _{t}(x_{0},\omega_{0})-\mu(x_{0},\omega_{0})\right|.$ $$

observing that $X_{0}=\{x_{0}\}$. Now we show that, if the result holds for $x_{k-1}$, it holds for $x_{k}$, as follows,

$$ $\displaystyle\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}\sum_{a_{k}\in A} \left|q^{P_{t},\phi_{t},\mu_{t}}(x_{k},\omega_{k},a_{k})-q^{P_{t},\phi_{t},\mu }(x_{k},\omega_{k},a_{k})\right|$ $\displaystyle=\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_{k- 1}\in A}\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}\sum_{a_{k}\in A}|q^{P_ {t},\phi_{t},\mu_{t}}(x_{k-1},\omega_{k-1},a_{k-1})P_{t}(x_{k}|x_{k-1},\omega_ {k-1},a_{k-1})\mu_{t}(x_{k},\omega_{k})+$ $\displaystyle\mkern 250.0mu-q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1 })P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu(x_{k},\omega_{k})|\phi_{t}(a_{k }|x_{k},\omega_{k})$ $\displaystyle=\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_{k- 1}\in A}\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}|q^{P_{t},\phi_{t},\mu_ {t}}(x_{k-1},\omega_{k-1},a_{k-1})P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu _{t}(x_{k},\omega_{k})+$ $\displaystyle\mkern 300.0mu-q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1 })P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu(x_{k},\omega_{k})|$ $\displaystyle\leq\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_ {k-1}\in A}\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}|q^{P_{t},\phi_{t}, \mu_{t}}(x_{k-1},\omega_{k-1},a_{k-1})P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1} )\mu_{t}(x_{k},\omega_{k})+$ $\displaystyle\mkern 300.0mu-q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1 })P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu_{t}(x_{k},\omega_{k})|+$ $\displaystyle\quad+\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{ a_{k-1}\in A}\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}|q^{P_{t},\phi_{t} ,\mu}(x_{k-1},\omega_{k-1},a_{k-1})P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1}) \mu_{t}(x_{k},\omega_{k})+$ $\displaystyle\mkern 300.0mu-q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1 })P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu(x_{k},\omega_{k})|$ $\displaystyle\leq\sum_{x_{k-1}\in X_{k-1}k}\sum_{\omega_{k-1}\in\Omega}\sum_{a _{k-1}\in A}\left|q^{P_{t},\phi_{t},\mu_{t}}(x_{k-1},\omega_{k-1},a_{k-1})-q^{ P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})\right|$ $\displaystyle\mkern 300.0mu+\sum_{x_{k}\in X_{k}}q^{P_{t},\phi_{t},\mu}(x_{k}) \sum_{\omega_{k}\in\Omega}\left|\mu_{t}(x_{k},\omega_{k})-\mu(x_{k},\omega_{k} )\right|.$ $$

Thus, by induction hypothesis, it follows,

$$ $\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}\sum_{a_{k}\in A}\left|q^{P_{t} ,\phi_{t},\mu_{t}}(x_{k},\omega_{k},a_{k})-q^{P_{t},\phi_{t},\mu}(x_{k},\omega _{k},a_{k})\right|\leq\sum_{s=0}^{k}\sum_{x_{s}\in X_{s}}q^{P_{t},\phi_{t},\mu }(x_{s})\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}.$ $$

#### Bound on | q P t , ϕ t , μ ⁢ ( x , ω , a ) − q P , ϕ t , μ ⁢ ( x , ω , a ) | superscript 𝑞 subscript 𝑃 𝑡 subscript italic-ϕ 𝑡 𝜇 𝑥 𝜔 𝑎 superscript 𝑞 𝑃 subscript italic-ϕ 𝑡 𝜇 𝑥 𝜔 𝑎 \left|q^{P_{t},\phi_{t},\mu}(x,\omega,a)-q^{P,\phi_{t},\mu}(x,\omega,a)\right| | italic_q start_POSTSUPERSCRIPT italic_P start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_ϕ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ end_POSTSUPERSCRIPT ( italic_x , italic_ω , italic_a ) - italic_q start_POSTSUPERSCRIPT italic_P , italic_ϕ start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT , italic_μ end_POSTSUPERSCRIPT ( italic_x , italic_ω , italic_a ) |

To bound this term, we proceed again by induction. Thus, we notice that:

$$ $\displaystyle\sum_{x_{1}\in X_{1}}\sum_{\omega_{1}\in\Omega}\sum_{a_{1}\in A}| q^{P_{t},\phi_{t},\mu}(x_{1},\omega_{1},a_{1})-q^{P,\phi_{t},\mu}(x_{1},\omega _{1},a_{1})|$ $\displaystyle=\sum_{\omega_{0}\in\Omega}\sum_{a_{0}\in A}\sum_{x_{1}\in X_{1}} \sum_{\omega_{1}\in\Omega}\sum_{a_{1}\in A}|\mu(x_{0},\omega_{0})\phi_{t}(a_{0 }|x_{0},\omega_{0})P_{t}(x_{1}|x_{0},\omega_{0},a_{0})\mu(x_{1},\omega_{1}) \phi_{t}(a_{1}|x_{1},\omega_{1})$ $\displaystyle\mkern 300.0mu-\mu(x_{0},\omega_{0})\phi_{t}(a_{0}|x_{0},\omega_{ 0})P(x_{1}|x_{0},\omega_{0},a_{0})\mu(x_{1},\omega_{1})\phi_{t}(a_{1}|x_{1}, \omega_{1})|$ $\displaystyle=\sum_{\omega_{0}\in\Omega}\sum_{a_{0}\in A}\mu(x_{0},\omega_{0}) \phi_{t}(a_{0}|x_{0},\omega_{0})\sum_{x_{1}\in X_{1}}|P_{t}(x_{1}|x_{0},\omega _{0},a_{0})-P(x_{1}|x_{0},\omega_{0},a_{0})|\sum_{\omega_{1}\in\Omega}\sum_{a_ {1}\in A}\mu(x_{1},\omega_{1})\phi_{t}(a_{1}|x_{1},\omega_{1})|$ $\displaystyle\leq\sum_{\omega_{0}\in\Omega}\sum_{a_{0}\in A}q^{P,\phi_{t},\mu} (x_{0},\omega_{0},a_{0})\|P_{t}(\cdot|x_{0},\omega_{0},a_{0})-P(\cdot|x_{0}, \omega_{0},a_{0})\|_{1}.$ $$

Now, we proceed with the induction step,

$$ $\displaystyle\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}\sum_{a_{k}\in A}| q^{P_{t},\phi_{t},\mu}(x_{k},\omega_{k},a_{k})-q^{P,\phi_{t},\mu}(x_{k},\omega _{k},a_{k})|$ $\displaystyle=\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_{k- 1}\in A}\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}\sum_{a_{k}\in A}|q^{P_ {t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})P_{t}(x_{k}|x_{k-1},\omega_{k-1 },a_{k-1})\mu(x_{k},\omega_{k})\phi_{t}(a_{k}|x_{k},\omega_{k})$ $\displaystyle\mkern 300.0mu-q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})P( x_{k}|x_{k-1},\omega_{k-1},a_{k-1})\mu(x_{k},\omega_{k})\phi_{t}(a_{k}|x_{k}, \omega_{k})|$ $\displaystyle=\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_{k- 1}\in A}\sum_{x_{k}\in X_{k}}|q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k -1})P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})$ $\displaystyle\mkern 300.0mu-q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})P( x_{k}|x_{k-1},\omega_{k-1},a_{k-1})|$ $\displaystyle\leq\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_ {k-1}\in A}\sum_{x_{k}\in X_{k}}|q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a _{k-1})P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})$ $\displaystyle\mkern 300.0mu-q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})P_ {t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})|$ $\displaystyle+\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_{k- 1}\in A}\sum_{x_{k}\in X_{k}}|q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1}) P_{t}(x_{k}|x_{k-1},\omega_{k-1},a_{k-1})$ $\displaystyle\mkern 300.0mu-q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})P( x_{k}|x_{k-1},\omega_{k-1},a_{k-1})|$ $\displaystyle\leq\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in\Omega}\sum_{a_ {k-1}\in A}|q^{P_{t},\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})-q^{P,\phi_{t} ,\mu}(x_{k-1},\omega_{k-1},a_{k-1})|$ $\displaystyle\mkern 100.0mu+\sum_{x_{k-1}\in X_{k-1}}\sum_{\omega_{k-1}\in \Omega}\sum_{a_{k-1}\in A}q^{P,\phi_{t},\mu}(x_{k-1},\omega_{k-1},a_{k-1})\|P_ {t}(\cdot|x_{k-1},\omega_{k-1},a_{k-1})-P(\cdot|x_{k-1},\omega_{k-1},a_{k-1}) \|_{1}.$ $$

Thus by induction hypothesis we obtain,

$$ $\displaystyle\sum_{x_{k}\in X_{k}}\sum_{\omega_{k}\in\Omega}$ $\displaystyle\sum_{a_{k}\in A}|q^{P_{t},\phi_{t},\mu}(x_{k},\omega_{k},a_{k})- q^{P,\phi_{t},\mu}(x_{k},\omega_{k},a_{k})|$ $\displaystyle\leq\sum_{s=0}^{k-1}\sum_{x_{s}\in X_{s}}\sum_{\omega_{s}\in \Omega}\sum_{a_{s}\in A}q^{P,\phi_{t},\mu}(x_{s},\omega_{s},a_{s})\|P_{t}( \cdot|x_{s},\omega_{s},a_{s})-P(\cdot|x_{s},\omega_{s},a_{s})\|_{1}.$ $$

Returning to the quantity of interest we have:

$$ $\displaystyle\sum_{t\in[T]}\|q_{t}-\widehat{q}_{t}\|_{1}$ $\displaystyle\leq 2\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k-1}\sum_{x_{s} \in X_{s}}\sum_{\omega_{s}\in\Omega}\sum_{a_{s}\in A}q^{P,\phi_{t},\mu}(x_{s}, \omega_{s},a_{s})\|P_{t}(\cdot|x_{s},\omega_{s},a_{s})+$ $\displaystyle\mkern 100.0mu-P(\cdot|x_{s},\omega_{s},a_{s})\|_{1}+\sum_{t\in[T ]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_{s}}q^{P_{t},\phi_{t},\mu}(x_ {s})\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}.$ (3) $$

We proceed bounding the first term in Inequality (3). Fixing a layer $k\in[0,\dots,L-1]$, employing Azuma-Hoeffding inequality and noticing that $\|P_{t}(\cdot|x_{k},\omega_{k},a_{k})-P(\cdot|x_{k},\omega_{k},a_{k})\|_{1}\leq
2$, we have, with probability $1-2\delta$:

$$ $\displaystyle\sum_{t\in[T]}$ $\displaystyle\sum_{s=0}^{k-1}\sum_{x_{s}\in X_{s}}\sum_{\omega_{s}\in\Omega} \sum_{a_{s}\in A}q^{P,\phi_{t},\mu}(x_{s},\omega_{s},a_{s})\|P_{t}(\cdot|x_{s} ,\omega_{s},a_{s})-P(\cdot|x_{s},\omega_{s},a_{s})\|_{1}$ $\displaystyle\leq\sum_{s=0}^{k-1}\sum_{t\in[T]}\sum_{x_{s}\in X_{s}}\sum_{ \omega_{s}\in\Omega}\sum_{a_{s}\in A}\sqrt{\frac{2|X_{k(x_{s})+1}|\ln\left( \frac{T|X||\Omega||A|}{\delta}\right)}{\max\left\{1,N_{t}(x_{s},\omega_{s},a_{ s})\right\}}}\mathbbm{1}_{t}\{x_{s},a_{s},\omega_{s}\}+\sum_{s=0}^{k-1}2|X_{s} |\sqrt{2T\ln\left(\frac{L}{\delta}\right)}$ $\displaystyle\leq\sum_{s=0}^{k-1}\sqrt{2T|X_{s}||X_{s+1}|A||\Omega|\ln\left( \frac{T|X||\Omega||A|}{\delta}\right)}+\sum_{s=0}^{k-1}2|X_{s}|\sqrt{2T\ln \left(\frac{L}{\delta}\right)}$ $\displaystyle\leq|X|\sqrt{2T|A||\Omega|\ln\left(\frac{T|X||\Omega||A|}{\delta} \right)}+2|X|\sqrt{2T\ln\left(\frac{L}{\delta}\right)}.$ $$

Finally summing over $L$, we have, with probability at least $1-2\delta$ (which derives from a union bound between Azuma-Hoeffding inequality and the bound on the transitions):

$$ $\displaystyle\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k-1}\sum_{x_{s}\in X_{s }}\sum_{\omega_{s}\in\Omega}\sum_{a_{s}\in A}$ $\displaystyle q^{P,\phi_{t},\mu}(x_{s},\omega_{s},a_{s})\|P_{t}(\cdot|x_{s}, \omega_{s},a_{s})-P(\cdot|x_{s},\omega_{s},a_{s})\|_{1}$ $\displaystyle\leq L|X|\sqrt{2T|A||\Omega|\ln\left(\frac{T|X||\Omega||A|}{ \delta}\right)}+2L|X|\sqrt{2T\ln\left(\frac{L}{\delta}\right)}.$ $$

To bound the remaining term in Inequality (3), we proceed as follows,

$$ $\displaystyle\sum_{t\in[T]}\sum_{k=0}^{L-1}$ $\displaystyle\sum_{s=0}^{k}\sum_{x_{s}\in X_{s}}q^{P_{t},\phi_{t},\mu}(x_{s}) \|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}$ $\displaystyle\leq\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_ {s}}q^{P,\phi_{t},\mu}(x_{s})\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}+$ $\displaystyle\mkern 200.0mu+\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{ x_{s}\in X_{s}}\left(q^{P_{t},\phi_{t},\mu}(x_{s})-q^{P,\phi_{t},\mu}(x_{s}) \right)\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}$ $\displaystyle\leq\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_ {s}}q^{P,\phi_{t},\mu}(x_{s})\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}+ \sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_{s}}2\left(q^{P_{ t},\phi_{t},\mu}(x_{s})-q^{P,\phi_{t},\mu}(x_{s})\right)$ $\displaystyle\leq\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_ {s}}q^{P,\phi_{t},\mu}(x_{s})\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}+$ $\displaystyle\mkern 200.0mu+\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{ x_{s}\in X_{s}}\sum_{\omega_{s}\in\Omega}\sum_{a_{s}\in A}2\left|q^{P_{t},\phi _{t},\mu}(x_{s},\omega_{s},a_{s})-q^{P,\phi_{t},\mu}(x_{s},\omega_{s},a_{s}) \right|.$ $$

The second term is bounded by the previous analysis paying an additional $L$ factor, while, to bound the first terms we apply the Azuma-Hoeffding inequality and proceed as follows:

$$ $\displaystyle\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_{s}} q^{P,\phi_{t},\mu}(x_{s})\sum_{\omega_{s}\in\Omega}|\mu_{t}(x_{s},\omega_{s})- \mu(x_{s},\omega_{s})|$ $\displaystyle\leq\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_ {s}}\mathbbm{1}_{t}\{x_{s}\}\|\mu_{t}(\cdot|x_{s})-\mu(\cdot|x_{s})\|_{1}+2L|X |\sqrt{2T\ln\left(\frac{L}{\delta}\right)}$ $\displaystyle\leq\sum_{t\in[T]}\sum_{k=0}^{L-1}\sum_{s=0}^{k}\sum_{x_{s}\in X_ {s}}\mathbbm{1}_{t}\{x_{s}\}\sqrt{\frac{2|\Omega|\ln(T|X|/\delta)}{\max\{1,N_{ t}(x_{s})\}}}+2L|X|\sqrt{2T\ln\left(\frac{L}{\delta}\right)}$ $\displaystyle\leq 2L\sqrt{2L|X||\Omega|T\ln\left(\frac{T|X|}{\delta}\right)}+2 L|X|\sqrt{2T\ln\left(\frac{L}{\delta}\right)},$ $$

with probability at least $1-2\delta$, given the union bound over the Azuma-Hoeffding and the bound on the outcomes.
Finally, with a union bound between the bound on the transitions and the outcomes (which are both encompassed by the clean event) and the Azuma-Hoeffding inequalities, with probability at least $1-4\delta$, we have:

$$ $\displaystyle\sum_{t\in[T]}\|q_{t}-\widehat{q}_{t}\|_{1}$ $\displaystyle\leq\mathcal{O}\Bigg{(}L\sqrt{L|X||\Omega|T\ln\left(\frac{T|X|}{ \delta}\right)}+L|X|\sqrt{T\ln\left(\frac{L}{\delta}\right)}+$ $\displaystyle\mkern 200.0mu+L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X|| \Omega||A|}{\delta}\right)}+L^{2}|X|\sqrt{T\ln\left(\frac{L}{\delta}\right)} \Bigg{)}$ $\displaystyle\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X ||\Omega||A|}{\delta}\right)}\right),$ $$

which concludes the proof.
∎

### D.2 Regret

In the following section we show that Algorithm 2 attains $\tilde{\mathcal{O}}(\sqrt{T})$ regret. This is done showing that the confidence intervals over transitions, outcomes and sender reward concentrate at a rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$.

See 1

###### Proof.

We notice that the regret can be decomposed as follows:

$$ $\displaystyle R_{T}=\sum_{t\in[T]}r_{S}^{\top}(q^{*}-q_{t})=\sum_{t\in[T]}r_{S }^{\top}(q^{*}-\widehat{q}_{t})+\sum_{t\in[T]}r_{S}^{\top}(\widehat{q}_{t}-q_{ t}).$ $$

The second term is bounded by Hölder inequality and applying Lemma 3. To bound the first term we notice that, under the clean event, and by definition of the linear program solved by Algorithm 2, it holds:

$$ $\displaystyle(r_{S}+2\xi_{S,t})^{\top}\widehat{q}_{t}\geq(\overline{r}_{S,t}+ \xi_{S,t})^{\top}\widehat{q}_{t}\geq(\overline{r}_{S,t}+\xi_{S,t})^{\top}q^{*} \geq r_{S}^{\top}q^{*}.$ $$

Thus, we have,

$$ $\displaystyle\sum_{t\in[T]}r_{S}^{\top}(q^{*}-\widehat{q}_{t})\leq 2\sum_{t\in [T]}\xi_{S,t}^{\top}\widehat{q}_{t}=2\sum_{t\in[T]}\xi_{S,t}^{\top}q_{t}+2\sum _{t\in[T]}\xi_{S,t}^{\top}(\widehat{q}_{t}-q_{t}).$ $$

The second term is bounded by Hölder inequality and applying Lemma 3, which holds under the clean event, with probability at least $1-2\delta$. To bound the first term we employ Lemma 10 which holds under the clean event, with probability at least $1-\delta$, and a union bound, which concludes the proof. ∎

###### Proof.

### D.3 Violations

In the following section we show that Algorithm 2 attains $\tilde{\mathcal{O}}(\sqrt{T})$ violations. This is possible since, in the *full-feedback* setting, the incentive compatibility constraints collapse to standard linear constraints.

See 2

###### Proof.

In the proof, we compactly denote the receivers’ best response in a given state-action pair $(x,a)\in X\times A$ at time $t\in[T]$ as $b^{t}(a,x)\coloneqq b^{\phi^{\widehat{q}_{t}}}(a,x)$. Furthermore, by employing the definition of the linear program and summing over $(x,\omega,a)$, for any episode $t$, under the clean event, it holds:

$$ $\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a)\left(\overline {r}_{R,t}(x,\omega,a)+\xi_{R,t}(x,\omega,a)-\overline{r}_{R,t}(x,\omega,b^{t}( a,x))+\xi_{R,t}(x,\omega,b^{t}(a,x))\right)\geq 0,$ $$

which, in turn, implies that:

$$ $\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a)\left(r_{R}(x, \omega,a)+2\xi_{R,t}(x,\omega,a)-r_{R}(x,\omega,b^{t}(a,x))+2\xi_{R,t}(x, \omega,b^{t}(a,x))\right)\geq 0.$ $$

Thus, noticing that, in the *full-feedback* setting, we have $\xi_{R,t}(x,\omega,a)=\xi_{R,t}(x,\omega,b^{t}(a,x))$, we obtain:

$$ $\displaystyle\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a) \left(r_{R}(x,\omega,b^{t}(a,x))-r_{R}(x,\omega,a)\right)$ $\displaystyle\leq 4\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x, \omega,a)\xi_{R,t}(x,\omega,a)$ $\displaystyle\leq 4\sum_{x\in X,\omega\in\Omega}\widehat{q}_{t}(x,\omega)\xi_{ R,t}(x,\omega),$ $$

where $\xi_{R,t}(x,\omega)=\sqrt{\frac{\ln(3T|X||\Omega|/\delta)}{\max\{1,N_{t}(x,
\omega)\}}}$.
Now we combine the previous equations to bound the first term of the last inequality as follows:

$$ $\displaystyle\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}$ $\displaystyle\widehat{q}_{t}(x,\omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R} (x,\omega,a)\right)\leq 4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}\widehat{q }_{t}(x,\omega)\xi_{R,t}(x,\omega)$ $\displaystyle=4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}q_{t}(x,\omega)\xi_{ R,t}(x,\omega)+4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}(\widehat{q}_{t}(x, \omega)-q_{t}(x,\omega))\xi_{R,t}(x,\omega)$ $\displaystyle\leq 4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}q_{t}(x,\omega) \xi_{R,t}(x,\omega)+\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{ T|X||\Omega||A|}{\delta}\right)}\right)$ (4) $\displaystyle=4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}\mathbbm{1}_{t}\{x, \omega\}\xi_{R,t}(x,\omega)+4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}(q_{t} (x,\omega)-\mathbbm{1}_{t}\{x,\omega\})$ $\displaystyle\mkern 300.0mu+\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln \left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)$ $\displaystyle=4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}\mathbbm{1}_{t}(x, \omega)\xi_{R,t}(x,\omega)+4\sum_{t\in[T]}\sum_{x\in X}(q_{t}(x)-\mathbbm{1}_{ t}(x))$ $\displaystyle\mkern 300.0mu+\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln \left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)$ $\displaystyle\leq 4\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega}\mathbbm{1}_{t}( x,\omega)\xi_{R,t}(x,\omega)+4|X|\sqrt{2T\ln\frac{X}{\delta}}$ $\displaystyle\mkern 300.0mu+\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln \left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)$ (5) $\displaystyle\leq\sqrt{9L|X||\Omega|T\ln\frac{3T|X||\Omega|}{\delta}}+{O}\left (L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)$ (6) $\displaystyle\leq{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega ||A|}{\delta}\right)}\right),$ $$

where Inequality (4) holds by Hölder inequality and Lemma 3, which holds under the clean event, with probability at least $1-2\delta$, Inequality (5) follows by Azuma-Hoeffding and
Inequality (6) by Cauchy-Schwarz inequality and observing that $1+\sum_{t\in[T]}\frac{1}{\sqrt{t}}\leq 3\sqrt{T}$.
Finally, returning to the quantity of interest, we bound the cumulative violations as follows:

$$ $\displaystyle V_{T}$ $\displaystyle:=\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}q_{t}(x, \omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R}(x,\omega,a)\right)$ $\displaystyle=\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t }(x,\omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R}(x,\omega,a)\right)$ $\displaystyle\mkern 200.0mu+\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A} (q_{t}(x,\omega,a)-\widehat{q}_{t}(x,\omega,a))\left(r_{R}(x,\omega,b^{t}(a,x) )-r_{R}(x,\omega,a)\right)$ $\displaystyle\leq\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q} _{t}(x,\omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R}(x,\omega,a)\right)+\sum _{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}|q_{t}(x,\omega,a)-\widehat{q}_{ t}(x,\omega,a)|$ $\displaystyle\leq\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q} _{t}(x,\omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R}(x,\omega,a)\right)+{O} \left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega||A|}{\delta}\right) }\right)$ $\displaystyle\leq{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega ||A|}{\delta}\right)}\right),$ $$

where the last steps hold by Hölder inequality, Lemma 3 and the previous bound on the estimated occupancy measure. The final result holds with probability at least $1-7\delta$ employing a union bound over the clean event, which holds with probability at least $1-4\delta$, the Azuma-Hoeffding inequality used above, which holds with probability at least $1-\delta$ and Lemma 3, which, under the clean event, holds with probability at least $1-2\delta$. ∎

###### Proof.

## Appendix E Partial feedback

### E.1 Regret

###### Lemma 10 .

Under the event $\mathcal{E}(\delta)$, with probability at least $1-\delta$, it holds:

$$ $\sum_{t\in[T]}\xi_{S,t}^{\top}q_{t}\leq\mathcal{O}\left(\sqrt{L|X||\Omega||A|T \ln\left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)\quad\text{and}\quad\sum _{t\in[T]}\xi_{R,t}^{\top}q_{t}\leq\mathcal{O}\left(\sqrt{L|X||\Omega||A|T\ln \left(\frac{T|X||\Omega||A|}{\delta}\right)}\right)$ $$

###### Proof.

We bound the quantity of interest as follows:

$$ $\displaystyle\sum_{t\in[T]}\xi_{S,t}^{\top}q_{t}$ $\displaystyle\leq\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\xi_{S,t}(x ,\omega,a)\mathbbm{1}_{t}\{x,\omega,a\}+L\sqrt{2T\ln\frac{1}{\delta}}$ (7) $\displaystyle=\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\sqrt{\frac{ \ln(3T|X||\Omega||A|/\delta)}{\max\left\{1,N_{t}(x,\omega,a)\right\}}}\mathbbm {1}_{t}\{x,\omega,a\}+L\sqrt{2T\ln\frac{1}{\delta}}$ $\displaystyle\leq\sqrt{9\ln\left(\frac{3T|X||\Omega||A|}{\delta}\right)}\sum_{ x\in X,\omega\in\Omega,a\in A}\sqrt{N_{T}(x,\omega,a)}+L\sqrt{2T\ln\frac{1}{ \delta}}$ (8) $\displaystyle\leq\sqrt{9\ln\left(\frac{3T|X||\Omega||A|}{\delta}\right)}\sqrt{ |X||\Omega||A|\sum_{x\in X,\omega\in\Omega,a\in A}N_{T}(x,\omega,a)}+L\sqrt{2T \ln\frac{1}{\delta}}$ (9) $\displaystyle\leq\sqrt{9L|X||\Omega||A|T\ln\left(\frac{3T|X||\Omega||A|}{ \delta}\right)}+L\sqrt{2T\ln\frac{1}{\delta}},$ (10) $$

where Inequality (7) holds by the Azuma-Hoeffding inequality with probability $1-\delta$, Inequality (8) follows by observing that $1+\sum_{t\in[T]}\frac{1}{\sqrt{t}}\leq 3\sqrt{T}$, Inequality (9) follows from the Cauchy-Schwarz inequality, and Inequality (10) holds, noticing that $\sum_{x\in X,\omega\in\Omega,a\in A}N_{T}(x,\omega,a)\leq LT$. With the same analysis, we can prove that the same upper bound holds for $\sum_{t\in[T]}\xi_{R,t}^{\top}q_{t}\,$, concluding the proof.
∎

See 3

###### Proof.

As a first step, we decompose the sender’s regret as follows:

$$ $\displaystyle R_{T}$ $\displaystyle=\sum_{t\in[T]}r_{S}^{\top}(q^{*}-q_{t})$ $\displaystyle=\sum_{t\in[T]}r_{S}^{\top}(q^{*}-\widehat{q}_{t})+\sum_{t\in[T]} r_{S}^{\top}(\widehat{q}_{t}-q_{t})$ $\displaystyle\leq\sum_{t\in[T]}r_{S}^{\top}(q^{*}-\widehat{q}_{t})+\mathcal{O} \left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega||A|}{\delta}\right) }\right).$ (11) $$

We observe that the last inequality holds under the event $\mathcal{E}(\delta)$, with a probability of at least $1-2\delta$, and it is derived by applying the Hölder inequality and employing Lemma 3. To bound the first term in Equation (11), we notice that under $\mathcal{E}(\delta)$, we have:

$$ $\displaystyle(r_{S}+2\xi_{S,t})^{\top}\widehat{q}_{t}\geq(\overline{r}_{S,t}+ \xi_{S,t})^{\top}\widehat{q}_{t}\geq(\overline{r}_{S,t}+\xi_{S,t})^{\top}q^{*} \geq r_{S}^{\top}q^{*},$ $$

for each $t>N|X||\Omega||A|$ because of the optimality of $\widehat{q}_{t}$. Thus, rearranging the latter chain of inequalities we have:

$$ $\displaystyle\sum_{t\in[T]}r_{S}^{\top}(q^{*}-\,\widehat{q}_{t})$ $\displaystyle=\sum_{t\leq N|X||\Omega||A|}r_{S}^{\top}(q^{*}-\widehat{q}_{t})+ \sum_{t>N|X||\Omega||A|}r_{S}^{\top}(q^{*}-\widehat{q}_{t})$ $\displaystyle\leq NL|X||\Omega||A|+2\left(\sum_{t\in[T]}\xi_{S,t}^{\top}( \widehat{q}_{t}-q_{t})+\sum_{t\in[T]}\xi_{S,t}^{\top}q_{t}\right)$ $\displaystyle\leq NL|X||\Omega||A|+\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega| \ln\left(\frac{T|X||\Omega||A|}{\delta}\right)}\right).$ $$

In the first inequality above, we employ the fact that the support of each reward function belongs to $[0,1]$, while in the second inequality, we make use of Lemma 3, the Hölder inequality, and Lemma 10, which hold with a probability of at least $1-3\delta$. Substituting the latter inequality into Equation (11), we obtain:

$$ $R_{T}\leq\mathcal{O}\left(NL|X||\Omega||A|+L^{2}|X|\sqrt{T|A||\Omega|\ln\left( \frac{T|X||\Omega||A|}{\delta}\right)}\right).$ $$

Finally, we observe that the previous upper bound holds with probability at least $1-7\delta$. This follows by employing a union bound and observing that $\mathcal{E}(\delta)$ holds with a probability at least $1-4\delta$, which concludes the proof.
∎

###### Lemma 10 .

###### Proof.

###### Proof.

### E.2 Violations

In the following we denote the receivers’ best response in a given action $a\in A$ and state $x\in X$ as $b^{t}(a,x)\coloneqq b^{\phi^{\widehat{q}_{t}}}(a,x)$.

###### Lemma 11 .

Under the event $\mathcal{E}(\delta)$ the following holds:

$$ $V_{T}\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega ||A|}{\delta}\right)}\right)+\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A }q_{t}(x,\omega,a)\xi_{R,t}(x,\omega,b^{t}(a,x)),$ $$

with probability at least $1-3\delta$.

###### Proof.

As a first step, we observe that by employing the definition of $\xi_{R,t}$ and noticing that $\widehat{q}_{t}$ is a feasible solution to LP (C) for each $t\in[T]$ under the event $\mathcal{E}(\delta)$, we have:

$$ $\displaystyle\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a) \left(r_{R}(x,\omega,a)+2\xi_{R,t}(x,\omega,a)-r_{R}(x,\omega,b^{t}(a,x))+2\xi _{R,t}(x,\omega,b^{t}(a,x))\right)$ $\displaystyle\geq$ $\displaystyle\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a) \left(\overline{r}_{R,t}(x,\omega,a)+\xi_{R,t}(x,\omega,a)-\overline{r}_{R,t}( x,\omega,b^{t}(a,x))+\xi_{R,t}(x,\omega,b^{t}(a,x))\right)$ $\displaystyle\geq 0.$ $$

Then, rearranging the above inequality we get:

$$ $\displaystyle\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x,\omega,a)$ $\displaystyle\left(r_{R,t}(x,\omega,b^{t}(a,x))-r_{R,t}(x,\omega,a)\right)$ $\displaystyle\leq 2\sum_{x\in X,\omega\in\Omega,a\in A}\widehat{q}_{t}(x, \omega,a)\left(\xi_{R,t}(x,\omega,a)+\xi_{R,t}(x,\omega,b^{t}(a,x))\right).$ (12) $$

Furthermore, we can decompose the receivers’ violations as follows:

$$ $\displaystyle V_{T}$ $\displaystyle=\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A}\left(q_{t}(x, \omega,a)\pm\widehat{q}_{t}(x,\omega,a)\right)\left(r_{R}(x,\omega,b^{t}(a,x)) -r_{R}(x,\omega,a)\right)$ $\displaystyle\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X ||\Omega||A|}{\delta}\right)}\right)+\sum_{t\in[T]}\sum_{x\in X,\omega\in \Omega,a\in A}\widehat{q}_{t}(x,\omega,a)\left(r_{R}(x,\omega,b^{t}(a,x))-r_{R }(x,\omega,a)\right)$ $\displaystyle\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X ||\Omega||A|}{\delta}\right)}\right)+$ $\displaystyle\hskip 71.13188pt\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A }\left(\widehat{q}_{t}(x,\omega,a)\pm q_{t}(x,\omega,a)\right)\left(\xi_{R,t}( x,\omega,a)+\xi_{R,t}(x,\omega,b^{t}(a,x))\right)$ $\displaystyle\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X ||\Omega||A|}{\delta}\right)}\right)+\sum_{t\in[T]}\sum_{x\in X,\omega\in \Omega,a\in A}q_{t}(x,\omega,a)\left(2\xi_{R,t}(x,\omega,a)+2\xi_{R,t}(x, \omega,b^{t}(a,x))\right)$ $\displaystyle\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X ||\Omega||A|}{\delta}\right)}\right)+2\sum_{t\in[T]}\sum_{x\in X,\omega\in \Omega,a\in A}q_{t}(x,\omega,a)\xi_{R,t}(x,\omega,b^{t}(a,x)),$ $$

where the first and third inequalities hold by Lemma 3, the second inequality is a consequence of Inequality (E.2), and the third inequality follows by means of Lemma 10, which holds with a probability of at least $1-\delta$. Therefore, employing a union bound over the events of Lemma 3 and Lemma 10, the previous result holds with probability at least $1-3\delta$, under the clean event.
∎

See 4

###### Proof.

As a preliminary observation, we notice that Algorithm 3 is divided into $N$ epochs of length $\ell=|X||\Omega||A|$, where in each epoch, Algorithm 3 maximizes the probability of visiting each triplet $(x,\omega,a)$. In the following, we define $t_{j}(x,\omega,a)\in[T]$ as the round in which Algorithm 3 maximizes the occupancy of the triplet $(x,\omega,a)$ in the epoch $j\in[N-1]$. Formally:

$$ $t_{j}(x,\omega,a)\coloneqq\{t\in[\,j\ell+1,\dots,(j+1)\ell\,]\,\ |\,\, \textnormal{$\sum_{x^{\prime}\in X}q(x,\omega,a,x^{\prime})$ is the objective function of Program~{}\eqref{prob:double_opt} }\}$ $$

Furthermore, for each occupancy measure $q_{t}$ with $t\in[T]$, the following holds:

$$ $q_{t}(x,\omega,a)=q(x,\omega,b^{t}(a,x))\leq q_{t_{j}(x,\omega,b^{t}(a,x))}(x, \omega,b^{t}(a,x))$ (13) $$

for each $j\in[N-1]$ where $q\in\mathcal{Q}$ is an occupancy measure that satisfies the IC constraints of the offline optimization problem (see Program (3.2)). The first equality above follows by observing that there always exists an occupancy that satisfies the IC constraints that recommends action $b^{t}(a,x)\in A$ instead of $a\in A$ in the state $x\in X$ with the same probability of $q_{t}$. The inequality, on the other hand, follows by observing that the space of occupancy measures satisfying the IC constraint of the offline optimization problem (3.2) is always a subset of the feasibility set of Program (C).
Furthermore, by Lemma 11 we have that:

$$ $V_{T}\leq\mathcal{O}\left(L^{2}|X|\sqrt{T|A||\Omega|\ln\left(\frac{T|X||\Omega ||A|}{\delta}\right)}\right)+\sum_{t\in[T]}\sum_{x\in X,\omega\in\Omega,a\in A }q_{t}(x,\omega,a)\xi_{R,t}(x,\omega,b^{t}(a,x)),$ $$

We focus on bounding the second term in the inequality above in the first $N\ell$ rounds of Algorithm 3. Thus, with probability at least $1-\delta$ we have:

$$ $\displaystyle\sum_{t\leq N\ell}\sum_{x\in X,\omega\in\Omega,a\in A}q_{t}(x, \omega,a)\xi_{R,t}(x,\omega,b^{t}(a,x))$ $\displaystyle\leq\sum_{t=1}^{\ell}\sum_{x\in X,\omega\in\Omega,a\in A}q_{t}(x, \omega,a)\xi_{R,t}(x,\omega,b^{t}(a,x))+\sum_{t=\ell+1}^{N\ell}\sum_{x\in X, \omega\in\Omega,a\in A}q_{t}(x,\omega,a)\left(\xi_{R,t}(x,\omega,b^{t}(a,x))\right)$ $\displaystyle\leq L|X||\Omega||A|+\sum_{x\in X,\omega\in\Omega,a\in A}\left( \sum_{j=1}^{N-1}\sum_{t=j\ell}^{(j+1)\ell}q_{t}(x,\omega,a)\xi_{R,t}(x,\omega, b^{t}(a,x))\right)$ (14) $\displaystyle\leq L|X||\Omega||A|+\sum_{x\in X,\omega\in\Omega,a\in A}\left[ \sum_{a^{\prime}\in A}\left(\sum_{j=1}^{N-1}\sum_{t=j\ell}^{(j+1)\ell}q_{t}(x, \omega,a^{\prime})\left(\xi_{R,t}(x,\omega,a^{\prime})\mathbbm{1}\{b^{t}(a,x)= a^{\prime}\}\right)\right)\right]$ $\displaystyle\leq L|X||\Omega||A|+\sum_{x\in X,\omega\in\Omega,a\in A}\left[ \sum_{a^{\prime}\in A}\left(\sum_{j=1}^{N-1}q_{t_{j}(x,\omega,a^{\prime})}(x, \omega,a^{\prime})\sum_{t=j\ell}^{(j+1)\ell}\left(\xi_{R,t}(x,\omega,a^{\prime })\mathbbm{1}\{b^{t}(a,x)=a^{\prime}\}\right)\right)\right]$ (15) $\displaystyle\leq L|X||\Omega||A|+\sum_{x\in X,\omega\in\Omega,a\in A}\left[ \sum_{a^{\prime}\in A}\left(\sum_{j=1}^{N-1}q_{t_{j}(x,\omega,a^{\prime})}(x, \omega,a^{\prime})\sum_{t=j\ell}^{(j+1)\ell}\xi_{R,t}(x,\omega,a^{\prime}) \right)\right]$ (16) $\displaystyle\leq L|X||\Omega||A|+\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{ \delta}\right)}\sum_{x\in X,\omega\in\Omega,a\in A}\left[\sum_{a^{\prime}\in A }\left(\sum_{j=1}^{N-1}q_{t_{j}(x,\omega,a^{\prime})}(x,\omega,a^{\prime})\sum _{t=j\ell}^{(j+1)\ell}\frac{1}{\sqrt{\max\{1,N_{t}(x,\omega,a^{\prime})}\}} \right)\right]$ $\displaystyle\leq L|X||\Omega||A|+\ell\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{ \delta}\right)}\sum_{x\in X,\omega\in\Omega,a\in A}\left[\sum_{a^{\prime}\in A }\left(\sum_{j=1}^{N-1}\frac{q_{t_{j}(x,\omega,a^{\prime})}(x,\omega,a^{\prime })}{\sqrt{\max\{1,N_{j}(x,\omega,a^{\prime})}\}}\right)\right]$ (17) $\displaystyle\leq L|X||\Omega||A|+\ell\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{ \delta}\right)}\,\,\cdot$ $\displaystyle\mkern 200.0mu\cdot\Bigg{(}\sum_{x\in X,\omega\in\Omega,a\in A} \left[\sum_{a^{\prime}\in A}\left(\sum_{j=1}^{N-1}\frac{\mathbbm{1}_{t_{j}(x, \omega,a^{\prime})}(x,\omega,a^{\prime})}{\sqrt{\max\{1,N_{j}(x,\omega,a^{ \prime})}\}}\right)\right]+L|A|\sqrt{2N\ln\frac{1}{\delta}}\Bigg{)}$ (18) $\displaystyle\leq L|X||\Omega||A|+3\ell\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{ \delta}\right)}\left(\sum_{x\in X,\omega\in\Omega,a\in A}\left[\sum_{a^{\prime }\in A}\sqrt{\sum_{i=1}^{N}\mathbbm{1}_{t_{i}(x,\omega,a^{\prime})}}\right]+L| A|\sqrt{2N\ln\frac{1}{\delta}}\right)$ $\displaystyle\leq L|X||\Omega||A|+3\ell\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{ \delta}\right)}\left(\sum_{x\in X,\omega\in\Omega,a\in A}\left[\sum_{a^{\prime }\in A}\sqrt{N_{N\ell}(x,\omega,a^{\prime})}\right]+L|A|\sqrt{2N\ln\frac{1}{ \delta}}\right)$ (19) $\displaystyle\leq L|X||\Omega||A|+3\ell|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A |}{\delta}\right)}\left(\sum_{x\in X,\omega\in\Omega,a^{\prime}\in A}\sqrt{N_{ N\ell}(x,\omega,a^{\prime})}+L\sqrt{2N\ln\frac{1}{\delta}}\right)$ $\displaystyle\leq L|X||\Omega||A|+3\ell|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A |}{\delta}\right)}\left(\sqrt{LN\ell}+L\sqrt{2N\ln\frac{1}{\delta}}\right),$ (20) $$

where we let $N_{j}(x,\omega,a)=\sum_{i\leq j}\mathbbm{1}_{t_{i}(x,\omega,a)}(x,\omega,a)$ for the the sake of simplicity. Furthermore, we notice that Inequality (14) follows observing that $\xi_{r,t}(x,\omega,a)\leq 1$ for each $(x,\omega,a)\in X\times\Omega\times A$ and $t\in[T]$, and because the occupancy defines a probability distribution over each layer $k\in[0,\dots,L]$. Inequality (15) holds thanks to Inequality (13). Inequality (16) follows because each indicator function takes value of at most one. Inequality (17) follows by observing that the number of times that the triplet $(x,\omega,a^{\prime})$ is visited overall is always greater or equal to the the number of times such a triplet has been visited during the rounds in which Algorithm 3 maximizes the exploration of that triplet. Inequality (18) holds with probability at least $1-\delta$ and follows from the Azuma-Hoeffding inequality, and Inequality (20) holds, noticing that $\sum_{x\in X,\omega\in\Omega,a\in A}N_{T}(x,\omega,a)\leq LN\ell$ and employing the Cauchy-Schwarz inequality.
We focus on bounding the cumulative violations suffered in the remaining $T-N\ell$ rounds of Algorithm 3. With probability at least $1-\delta$ the following holds:

$$ $\displaystyle\sum_{t>N\ell}$ $\displaystyle\sum_{x\in X,\omega\in\Omega,a\in A}q_{t}(x,\omega,a)\xi_{R,t}(x, \omega,b^{t}(a,x))$ $\displaystyle\leq\sum_{x\in X,\omega\in\Omega,a\in A}\left(\sum_{a^{\prime}\in A }\sum_{t>N\ell}q_{t}(x,\omega,a^{\prime})\xi_{R,t}(x,\omega,a^{\prime}) \mathbbm{1}_{t}\{b^{t}(a,x)=a^{\prime}\}\right)$ $\displaystyle\leq\sum_{x\in X,\omega\in\Omega,a\in A}\sqrt{\ln\left(\frac{2T|X ||\Omega||A|}{\delta}\right)}\sum_{a^{\prime}\in A}q_{t_{N}(x,\omega,a^{\prime })}(x,\omega,a^{\prime})\sum_{t>N\ell}{\frac{1}{\sqrt{\max\{1,N_{t}(x,\omega,a ^{\prime})\}}}}$ (21) $\displaystyle\leq|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{\delta}\right)}\sum _{x\in X,\omega\in\Omega,a\in A}q_{t_{N}(x,\omega,a)}(x,\omega,a)\sum_{t>N\ell }{\frac{1}{\sqrt{\max\{1,N_{N\ell}(x,\omega,a)\}}}}$ $\displaystyle\leq|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{\delta}\right)}\sum _{x\in X,\omega\in\Omega,a\in A}q_{t_{N}(x,\omega,a)}(x,\omega,a){\frac{\left( T-N\ell\right)}{\sqrt{\max\{1,N_{N\ell}(x,\omega,a)\}}}}$ $\displaystyle\leq|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{\delta}\right)}\sum _{x\in X,\omega\in\Omega,a\in A}\frac{N_{N\ell}(x,\omega,a)+L\sqrt{2N\ln\frac{ 1}{\delta}}}{N}{\frac{\left(T-N\ell\right)}{\sqrt{\max\{1,N_{N\ell}(x,\omega,a )\}}}}$ (22) $\displaystyle\leq|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{\delta}\right)} \frac{T}{N}\left(\sqrt{LN\ell}+L\ell\sqrt{2N\ln\frac{1}{\delta}}\right)$ (23) $\displaystyle\leq 2|A|\sqrt{\ln\left(\frac{2T|X||\Omega||A|}{\delta}\right)} \frac{T}{\sqrt{N}}L\ell\sqrt{2\ln\frac{1}{\delta}}.$ (24) $$

Inequality (21) holds thanks to Inequality (13) and observing that the indicator function takes value of at most one. Inequality (23) holds, noticing that $\sum_{x\in X,\omega\in\Omega,a\in A}N_{T}(x,\omega,a)\leq LN\ell$ and employing the Cauchy-Schwarz inequality. Inequality (22) holds with probability at least $1-\delta$ and follows by employing the Azuma-Hoeffding and observing the following:

$$ $N_{N\ell}(x,\omega,a)\geq\sum_{k=1}^{N}\mathbbm{1}_{t_{k}}(x,\omega,a)\geq\sum _{k=1}^{N}q_{t_{k}}(x,\omega,a)-L\sqrt{2N\ln\frac{1}{\delta}}\geq Nq_{t_{N}(x, \omega,a)}(x,\omega,a)-L\sqrt{2N\ln\frac{1}{\delta}},$ $$

which can be written as follows:

$$ $\frac{N_{N\ell}(x,\omega,a)+L\sqrt{2N\ln\frac{1}{\delta}}}{N}\geq q_{t_{N}(x, \omega,a)}(x,\omega,a).$ $$

Finally, thanks to Lemma 11 and employing Inequality (20) and Inequality (23) we get:

$$ $V_{T}\leq\widetilde{\mathcal{O}}\left(\rho\left(|A|\frac{T}{\sqrt{N}}+|A|\sqrt {N}+L^{2}\sqrt{T}\right)\right).$ $$

With $\rho:=(|X||\Omega||A|)^{3/2}\sqrt{\ln\left(\nicefrac{{1}}{{\delta}}\right)}$, such a result holds with a probability of at least $1-9\delta$, employing a union bound and observing that $\mathcal{E}(\delta)$ holds with a probability of at least $1-4\delta$, Lemma 11 holds with a probability of at least $1-3\delta$, and both Inequality (20) and Inequality (23) hold with a probability of at least $1-\delta$.
∎

###### Lemma 11 .

###### Proof.

###### Proof.

### E.3 Lower bound

See 5

###### Proof.

We consider two instances with a single possible outcome and a single state. In the following, we omit the dependence on the sender and receiver utility from these parameters. We assume that the sender’s utility in the first instance is a deterministic function given by $r^{1}_{S}(a_{1})=1$ and $r^{1}_{S}(a_{2})=0$, while the receiver’s utility is given by $r^{2}_{R}(a_{1})\sim\text{Be}(1/2+\epsilon)$ and $r^{2}_{R}(a_{2})\sim\text{Be}(1/2)$. Meanwhile, the sender’s utility in the second instance is $r^{2}_{S}(a_{1})=1$ and $r^{1}_{S}(a_{2})=0$, while the follower’s utility is equal to $r^{2}_{R}(a_{1})\sim\text{Be}(1/2+\epsilon)$ and $r^{2}_{R}(a_{2})\sim\text{Be}(1/2+2\epsilon)$, for some $\epsilon\in(0,1/2)$. Thus, the sender’s regret in the first instance is given by:

$$ $R_{T}^{1}=\sum_{t=1}^{T}\phi^{t}(a_{2}),$ $$

since the optimal signaling scheme is the one that always recommends action $a_{1}\in\mathcal{A}$ in the first instance. In the following, we define $\mathbb{P}^{1}\left(\text{respectively, }\mathbb{P}^{2}\right)$ as the probability measure induced by recommending, at each round, signaling schemes according to some algorithm in the first (respectively, second) instance. Then, we bound the probability that the regret in the first instance is larger than a constant $C\in\mathbb{N}$ as follows:

$$ $\mathbb{P}^{1}\left(R_{T}^{1}\leq C\right)=\mathbb{P}^{1}\left(\sum_{t=1}^{T} \phi^{t}(a_{2})\leq C\right)\geq 1-\eta,$ (25) $$

for some $\eta\in(0,1)$. Furthermore, by Pinsker’s inequality and Equation (25) the following holds.

$$ $\mathbb{P}^{2}\left(\sum_{t=1}^{T}\phi^{t}(a_{2})\leq C\right)\geq 1-\eta- \sqrt{D_{KL}(\mathbb{P}^{1},\mathbb{P}^{2})},$ (26) $$

where we denote with $D_{KL}(\cdot,\cdot)$ the Kullback-Leibler divergence between two probability measure. By means of the well known divergence decomposition, we have:

$$ $D_{KL}(\mathbb{P}^{1},\mathbb{P}^{2})\leq\ \mathbb{E}^{1}\left[\sum_{t=1}^{T} \phi^{t}(a_{2})\right]D_{KL}(\text{Be}(1/2+2\epsilon),\text{Be}(1/2))\leq 16 \epsilon^{2}\mathbb{E}^{1}\left[\sum_{t=1}^{T}\phi^{t}(a_{2})\right],$ (27) $$

where in the latter inequality we used the well known property ensuring that $D_{KL}(\text{Be}(p),\text{Be}(q))\leq\frac{(p-q)^{2}}{q(1-q)}$. Then, by reverse Markov inequality and Equation (25) we get:

$$ $\mathbb{E}^{1}\left[\sum_{t=1}^{T}\phi^{t}(a_{2})\right]\leq\mathbb{P}^{1} \left(\sum_{t=1}^{T}\phi^{t}(a_{2})\geq C\right)(T-C)+C\leq\eta(T-C)+C,$ $$

Furthermore, by means of the latter inequality and Equation (27) we have:

$$ $\mathbb{P}^{2}\left(\sum_{t=1}^{T}\phi^{t}(a_{2})\leq C\right)\geq 1-\eta- \sqrt{16\epsilon^{2}(\eta(T-C)+C)}$ $$

We now consider the receiver’s violations in the second instance which can be computed as follows:

$$ $V_{T}^{2}=\sum_{t=1}^{T}\phi^{t}(a_{1})\left(\overline{r}_{R}^{2}(a_{2})- \overline{r}_{R}^{2}(a_{1})\right)=\epsilon\sum_{t=1}^{T}\phi^{t}(a_{1}).$ $$

Then, by means of Equation (26) we get:

$$ $\displaystyle\mathbb{P}^{2}\left(V_{T}^{2}\geq\epsilon T\right)$ $\displaystyle\geq\mathbb{P}^{2}\left(V_{T}^{2}\geq\epsilon(T-C)\right)$ $\displaystyle=\mathbb{P}^{2}\left(\epsilon\sum_{t=1}^{T}\phi^{t}(a_{1})\geq \epsilon(T-C)\right)$ $\displaystyle=\mathbb{P}^{2}\left(T-\sum_{t=1}^{T}\phi^{t}(a_{2})\geq T-C\right)$ $\displaystyle=\mathbb{P}^{2}\left(\sum_{t=1}^{T}\phi^{t}(a_{2})\leq C\right) \geq 1-\eta-\sqrt{16\epsilon^{2}(\eta(T-C)+C)}.$ $$

Finally, by setting $C=\frac{T^{\alpha}}{2}$ and $\epsilon=\frac{T^{-\alpha/2}}{16}$ and $\eta=\frac{T^{\alpha-1}}{2}$ we get:

$$ $\displaystyle\mathbb{P}^{1}\left(R_{T}^{1}\leq C\right)$ $\displaystyle\geq 1-\eta$ $\displaystyle\mathbb{P}^{1}\left(R_{T}^{1}\leq\frac{T^{\alpha}}{2}\right)$ $\displaystyle\geq 1-\frac{T^{\alpha-1}}{2}\geq\frac{1}{2},$ $$

since $\alpha\in[1/2,1]$. Then, the latter result implies that:

$$ $\displaystyle\mathbb{P}^{2}\left(V_{T}^{2}\geq\epsilon T\right)$ $\displaystyle\geq 1-\eta-\sqrt{16\epsilon^{2}(\eta(T-C)+C)}$ $\displaystyle\geq 1-\frac{T^{\alpha-1}}{2}-\sqrt{\frac{T^{-\alpha}}{16}\left( \frac{T^{\alpha}}{2}+\frac{T^{\alpha}}{2}\right)}\geq\frac{1}{4},$ $$

which concludes the proof.
∎

###### Proof.

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. What is the trade-off between reward regret and constraint violation for the full feedback setting?

2. What is the time-complexity of Opt-Opt problem (2)?

3. Can you generalize your results beyond tabular MDP?
soundness: 3
strengths: The authors consider an interesting extension of MPP when the sender is unware of the receiver's rewards and must learn them over time. The algorithms and the main ideas are explained clearly in the paper. It's also interesting to see that the authors provide a trade-off between the reward regret and the violation of persuasion constraints.
summary: This paper considers learning in a Markov persuasion process (MPP) where the learner cannot take actions directly, and must persuade a receiver to take the intended action. The focus is on the setting where the learner is not aware of the receiver's reward function and must guarantee that both the regret in total reward and violation of persuasion constraints is sublinear in $T$. The authors consider two settings -- (a) full feedback setting where the learner observes the rewards for all the actions at a time-step, and (b) partial feedback setting where the learner observes rewards only for the chosen action.

The authors propose an optimistic planning based algorithm which finds persuasive policy by being optimistic according to sender's rewards and receiver's persuasion constraints. For the full feedback setting the reward regret and violation of constraints is $O(\sqrt{T})$, whereas for the partial feedback setting there is a trade-off between regret in reward and violation of constraints.
weaknesses: 1. The authors claim that it is impossible to satisfy persuasive constraints at all rounds. However, the negative result is provided only for the partial feedback setting, and I wonder if one can avoid the negative result for the full feedback setting. If so, it makes more sense to study a version of MPP where the constraints are satisfied with high probability. In general, I favour the guarantee of high probability persuasion compared to providing only upper bound on the total amount of violation. Since we cannot make any assumption about receiver's preferences, it is not clear whether the receivers will still follow the sender's recommendation.

2. The proposed algorithms and the proof techniques are very similar to prior work (in particular Bernasconi et. al. 2022 or Gan et. al. 2024). All these works propose explore then exploit (based on optimistic planning) algorithm for persuasion problems. So the authors need to clarify what are the technical difficulties in the analysis in this paper.

3. It is not clear that the optimistic planning problem can be solved efficiently i.e. poly(|X|, |A|, L) time.

4. Finally, the authors consider only tabular MDPs. The original paper on MPP did consider more general MDPs and without such extensions, it is not clear whether the result generalizes.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: * I am not an expert in this topic, but from what I gathered, the setup in the paper resembles a general-sum game, is that correct? If so, could it be also extended to model a zero-sum game in which it may not be in the receivers' best interest to follow the sender? 

* In line 383:
> ...the sender does not observe sufficient feedback about the persuasiveness of $\phi_t$.
  * Could the authors comment on what are the necessary feedback to infer about the persuasiveness and why the information about only the agents' rewards for the visited triplets are not enough?
soundness: 2
strengths: The paper considers a natural extension of the existing MPP studies by relaxing the assumption of full knowledge about the environment and the players. The problem formulation as well as the objectives of the learning problem are clearly described. Mathematical proofs are also provided that highlight the effectiveness of the proposed algorithm.
summary: This paper studies the Markovian Persuasion Processes (MPPs), a repeated version of Bayesian persuasion, by relaxing the common assumption that the sender knows receivers’ rewards. Unlike previous works, the authors use the setting in which the senders have no knowledge about transitions, prior distributions over outcomes, sender’s stochastic rewards, and receivers’ ones. Removing this requirement allows for capturing real-world problems, for e.g.,  online streaming platforms recommending movies to its users. The authors propose a learning algorithm, Optimistic Persuasive Policy Search (OPPS) for the sender with partial feedback and prove that its regret with respect to an optimal information-disclosure policy grows sublinearly in the number of episodes.
weaknesses: I think the major weakness of this paper is the missing case study. While the authors highlight “practical/real-world application” as the key motivation behind studying this variation of MPP, they fail to provide an example (or a simple toy case). I think the paper would benefit from a case study as it would also help readers to understand the problem better.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: **Question:**

(Q1) How is your work different from the constrained MDP works you cited?  What's the additional contribution? 

(Q2) Can you provide a lower bound that includes the parameters of the environment? 


**Suggestions:**

- Typo: Line 428: "si" -> "is".
soundness: 3
strengths: (S1) This paper provides a relatively complete picture for the online MPP problem, providing upper and lower bounds on the sender's regret and the receiver's violation that are tight in terms of $T$. 

(S2) Compared to previous works in online MPP that all assume that sender has some type of knowledge of the environment, this work makes no such assumption.  This is a significant conceptual contribution.
summary: This paper studies the online learning version of Markov Persuasion Process (MPP). An MPP involves a sender and a receiver interacting for $L$ time steps, where at each time step with state $x_k$ commonly observed by both players, the sender sees an additional outcome $\omega_k \sim \mu(x_k)$ (only observed by the sender) and sends a signal (action recommendation) to the receiver according to some signaling scheme, then the receiver takes an action that affects the rewards of both players and the state transition. The authors assume that the sender does not know any information about the environment (the prior $\mu$, the transition matrix, the receiver's reward, and their own reward).  Repeating this MPP $T$ times, the sender aims to learn the environment and the optimal signaling scheme over time.  The main results include:
- With full feedback (which includes the realized rewards of all actions at each round), the authors design a learning algorithm that achieves $O(L^2|X| \sqrt{T |A||\Omega| \ln(1/\delta)})$ regret for the sender, and $O(L^2 |X| \sqrt{T |A| |\Omega| \ln(1/\delta)})$ violation of the persuasiveness constraint (i.e., the regret for the receiver if the receiver follows the action recommendation.)
- With partial feedback (which includes the reward of the taken action only), the authors design a learning algorithm with $O(T^\alpha)$ regret for the sender and $O(T^{1-\alpha/2})$ violation for the receiver, where $\alpha\in[1/2, 1]$. 
- A lower bound showing that no learning algorithm can achieve regret $o(T^{\alpha})$ and violation $o(T^{1-\alpha/2})$.
weaknesses: (W1) Although this paper provides a relatively complete picture for the online MPP problem, most of the techniques are standard and directly come from previous works. The upper bound techniques come from the constrained Markov Decision Process (MDP) literature, e.g., [Germano et al, 2023](https://arxiv.org/pdf/2304.14326), as the authors mentioned. The MPP problem is basically a constrained MDP with linear objective and linear constraint (maximizing the sender's expected reward subject to persuasiveness constraint), for which the constrained MDP literature already provides satisfactory solutions. 

The lower bound is basically the same as previous paper [Bernasconi et al (2022)](https://proceedings.neurips.cc/paper_files/paper/2022/file/6604fbf7548524576c9ee2e30b0d5122-Paper-Conference.pdf), except that previous bound only works for $\alpha \in[1/2, 2/3]$ while this paper improves to $\alpha \in [1/2, 1]$.  

(W2) Although the regret bounds in this work are tight in $T$, there is still a large gap between the upper and lower bounds in terms of other parameters $L, |X|, |\Omega|, |A|$.  The lower bound does not contain those parameters, while the upper bound have polynomial dependency on them.  In the full information setting for example, an upper bound in the form of $O(parameter * \sqrt{T})$ is typical in the online learning literature (in particular, it can be easily derived from the previous constrained MDP techniques), and a lower bound like $\Omega(\sqrt{T})$ is also expected.  Since this work aims to give a complete picture for the online MPP problem, I think it is important to characterize the tight dependency of the regret on parameters other than $T$ as well. Moreover, given that there are already several previous works on online Bayesian persuasion and MPP (like Wu et al (2022)), only characterizing the regret dependency on $T$ does not seem to be a large enough contribution to the existing literature.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Is the regret bound of the algorithm in the full feedback setting tight?
soundness: 3
strengths: 1. The paper removes the assumption in the previous related paper that the sender knows everything about the environment. Given their result that it is impossible to achieve sublinear regret while being persuasive at every episode with high probability, it's reasonable to turn to the goal that the violation of persuasiveness is sublinear in T. Overall, the question studied by this paper is well motivated and their desiderata are reasonable.

2. The paper provides a solid theoretical analysis. The authors achieve tight results for the partial feedback setting.
summary: This paper studies the Markov persuasion process (MPP) in which the sender does not know the environment, i.e., the transition, prior, and reward functions. They consider two types of feedback: full feedback and partial feedback. Full feedback means that the sender can observe all agents' rewards for the realized state and outcome in every round, but partial feedback means that the sender can only observe agents' rewards for the realized state, outcome, and action in every round.

The authors design algorithms for both kinds of feedback that achieve sublinear regret and violation of persuasiveness. Furthermore, the algorithm for the partial feedback has a matching lower bound.
weaknesses: 1. The setting of this paper is similar to the setting of [1]. To be specific, in this paper, the authors consider MDP with persuasiveness as the stochastic long-term constraint because the receiver's reward function is drawn from some distribution. In [1], the authors consider MDP with constraint matrices, which can be stochastic or adversarial. As a consequence, these two papers share a similar upper-bound technique that maintains estimators and confidence bounds of the environment and uses them to update the occupancy measure. The similarity makes me cast doubt on the novelty and technical contribution of this paper. I think the authors should clarify the difference between these two papers.

2. While the result is tight in the partial feedback setting, it is not shown in the paper whether the result is tight in the full feedback setting. I think the lower bound in the full feedback setting should be included for the completeness of this paper.

3. For the proposed algorithm: (1)the computational complexity can be another issue that may prevent MPPs from being used in practice because large linear programming needs to be solved at every round; (2) the intuition of the algorithms should be explained more for better understanding. 

4. There is a typo on page 8:  "every triple \si" not "si".

[1]. Jacopo Germano, Francesco Emanuele Stradi, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. A best-of-both-worlds algorithm for constrained MDPs with long-term constraints.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: Do you agree with my comparison with [1]? For (A) and (B), do you agree with my reduction? For (C), could you elaborate on whether you believe this difference is significant? Is my understanding of (D) correct?

I would also be curious to hear if the authors have any response to my concerns about the model.
soundness: 3
strengths: I think this is a nice paper. It’s well-written, the model seems mostly reasonable, the results are satisfying, and there are some interesting technical ideas. Without considering prior work, I would probably lean towards acceptance.
summary: In Bayesian persuasion, a sender sends information to a receiver with the goal of persuading them to take particular actions, while the receiver is aware of the sender’s incentive and has their own goals, and thus may deviate from the recommended action. Typically one designs a “persuasive” communication scheme, meaning it is always in the receiver’s best interest to follow the recommendation. Usually, this occurs in a single-round setting.

The present submission studies Markov Persuasion Processes (MPPs), which essentially combine MDPs with Bayesian persuasion. Specifically, the sender instead interacts with T different receivers sequentially, and actions on previous time steps affect the current state. This paper assumes the sender starts with no information and must learn everything on the fly (transition function, sender reward function, receiver reward function). The goal is then regret which is sublinear in T. This paper also requires the cumulative violation of the persuasiveness constraint to be sublinear in T.

The authors provide algorithms which achieve both of those goals (regret sublinear in T and persuasiveness violation sublinear in T), in both a “full feedback” setting and a “partial feedback” setting. They also provide a matching lower bound.
weaknesses: Unfortunately, I have some serious concerns about the lack of novelty when compared to [1], which previously studied no-regret learning in MPPs. From my reading, the authors articulate four differences between the present submission and [1]:

A. [1] assumed that the receiver’s reward function is known to the sender, while the present submission does not. This is the primary difference emphasized by the authors.

B. [1] assumed rewards are deterministic, while the present submission allows rewards to be stochastic

C. [1] assumed the reward function is fixed, while the reward function to vary across episodes, but assumes that the reward function for each episode is sampled iid

D. [1] assumed that receivers know everything about the environment in order to compute a best-response, while the present submission does not.

I commend the authors for providing a clear discussion of the technical differences between their work and [1]; this made my job as a reviewer much easier. Unfortunately, none of (A) - (D) seem especially significant to me. I discuss each in turn.

_(A) and (B)_.
I argue that typically in RL theory, most of the technical difficulty comes from learning the transition function, and knowing the reward function doesn’t help much. The distinction between stochastic and deterministic rewards is also typically not significant. To semi-formalize this, I argue below that for {0,1} rewards, any no-regret algorithm for MDPs with known deterministic rewards can also solve MDPs with unknown stochastic rewards. 

This reduction breaks down for more general rewards than {0,1}, but I think the conceptual takeaway still holds: that most of the difficulty comes from learning the transition function. Also note that {0,1} rewards are sufficient for most RL lower bounds [2].

Beyond the technical connections, [1] also provide a conceptual justification for known rewards: “The receiver’s utility is known to the sender because the pricing rules are usually transparent, some are even set by the platform. For example, a rider-sharing platform usually sets per hour or mile payment rules for the drivers.” I think this is a reasonable argument, although it certainly doesn’t apply to all applications.

_(C)_.
I would guess that since the reward function for each episode is iid, their average quickly converges to the mean, such that this does not add much difficulty. However, I may be wrong, and I could imagine this component adding some novelty to the paper.

_(D)_.
If I understand correctly, the present submission instead assumes that the receiver always plays the action recommended by the sender and does not play a best response at all. The authors then show that the cumulative violation of the persuasiveness constraint is sublinear in T. I think this approach is reasonable: as the authors note, it is impossible to be immediately persuasive when the sender starts out with no information about the receiver. However, I don’t think this is a strength over [1]: this model seems easier in some ways and harder in some ways than [1]’s assumption of perfect best response.

Beyond the comparison with [1], I also have some concerns about the model. I’m unsure whether there exist natural applications which both involve Bayesian persuasion and MDP-style dynamics. The authors cite movie recommender systems as a motivating example, but what do the states represent? Receivers would be users, right? If I understand correctly, the sender interacts with a new receiver on every time step, so how does one user affect the state of a different user? It also seems like users’ incentives are pretty aligned with the recommendation system (they want to watch movies that they like), so it seems unlikely for users to engage in reasoning like “the system is recommending me movie A which isn’t what I want to watch but it does give me information about which movie I should actually watch”.

Even if the authors agree with everything above (and I am open to disagreement), I don’t think the paper has zero novelty, but I think the novelty is too low for ICLR.

References
1. Wu et al (2022) https://arxiv.org/pdf/2202.10678
2. Osband and Van Roy (2016) https://arxiv.org/pdf/1608.02732

_Reduction sketch_:
Consider an MDP M with unknown rewards in {0,1} and suppose we have a no-regret algorithm for MDPs with known rewards. Define a new MDP M’ with the original state space plus 2|A||S| additional states, each labeled (s,a,r): one new state for each possible state-action-reward combination. If the agent takes action a in an original state s, we add an intermediate time step where the agent transitions to some state (s,a,r), where r = r(s,a) is chosen stochastically. Regardless of the action taken in state (s,a,r), the agent receives reward r and transitions according to P(s,a) (i.e., how they would have transitioned in M). Basically, every time step in M becomes two time steps in M’, during which the agent obtains the same expected reward. Then E[agent reward in M after T steps] = E[agent reward in M’ after 2T steps]. This means that to solve M, we can simply run our no-regret algorithm on M’ and ignore the actions it takes on even time steps (that is, in (s,a,r) states).

Meta-review: The reviewers acknowledged that the paper investigates an interesting problem setting in sequential Bayesian persuasion where a sender has limited information about the receiver and provides a thorough theoretical analysis for this setting. However, the reviewers pointed out several weaknesses and shared common concerns related to the limited novelty w.r.t. the prior work. We want to thank the authors for their detailed responses. Based on the raised concerns and follow-up discussions, unfortunately, the final decision is a rejection. Nevertheless, the reviewers have provided detailed and constructive feedback. We hope the authors can incorporate this feedback when preparing future revisions of the paper.

Decision: Reject