Markov Persuasion Processes: Learning to Persuade From Scratch
Authors: Francesco Bacchiocchi
Francesco Emanuele Stradi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: NeurIPS 2025 poster ()
Keywords: Bayesian Persuasion
MPP
Primary area: theory

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 lower bounds for our setting matching the guarantees of our algorithm.

Markov Persuasion Processes: Learning to Persuade From Scratch
Francesco Bacchiocchi*
Francesco Emanuele Stradi'
Politecnico di Milano
Politecnico di Milano
francesco. bacchiocchh1@ollmi...
francescoemanulle stradi stradi@polimii
Matteo Castiglioni
Alberto Marchesi
Politecnico di Milano
Politecnico di Milano
matteo. natteo.castiglioon wwwttaaltitiiiiioeoee iat.ooocaaatiiiiiii@ppii........ it
alberto. mar itt.etto..marcheeip...i.ii..i...
Nicola Gatti
Politecnico di Milano
ni nicola. gatt www.co...aaaappp... gatti@polimi..t
Abstract
In Bayesian persuasion, an informed sender strategically discloses information to receiver as persuade them to undertake desirable actions. Recently, Markov persuasion processes (MPPs) have been introduced to capture sequential scenarios where sender faces a stream of myopic receivers 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 learning algorithm for the sender, working with partial feedback. We prove that its regret with respect to optimal information-disclouuu
Markovian environment.
policy grows sublinearly in the number of episodes, as it is the for the loss in persuasiveness cumulated while learning. Moreover, provide lower bounds for our setting matching the guarantees of our algorithm.
Introduction
Bayesian persuasion [Kamenica and Gentzkow 2011] studies how an informed sender should strategically disclose information to influence the behavior of a self-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 e.g., online advertising [Bro Miltersen and
Sheffet 2012 Emek et al. 2014
Badanidiyuru et al., 2018 Bacchiocchi et al., 2022], voting [Cheng 2 Castiglion al. [222aa] Castiglioni and Gatti 2021 traffic Bhaskar et al. 2016, Castiglion et al. 2021a]. recommendation sys- al. 2022]. security [Rabinovich et al. 2015
al. 2015] and Cámara
routing Vasserman et al. 2015
MMnssurr al.. 2016), e-commerce |Castiglion
Xu et al. a 2016), marketing [Babichenko and Barman [017] Candogan 2019 clinical trials Kolotilin
2015 and financial regulation [Goldstein and Leitner 20188.
Most the works on Bayesian persuasion focus on one-shot interactions, where information dis-
closure is performed "one shot".. Despite real-world problems are usually sequential, there are only
few exceptions that consider multi-step information disclosure [Wu al. 2022 Gan et al. 2022
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Bernasconi et al. 2022 2023b Iyer et al. 2023 Lin et al. 2024]. Specifically, Wu et al. [2022] initiated the study of Markov persuasion processes (MPPs), which model scenarios where sender sequentially faces 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 prior distribution-anl and faces new receiver, who is then called to take an action. The outcome and the receiver's s action jointly determine the agents' rewards and the next state. In an MPP, the goal of the sender goal is to disclose information about the outcome at each state, so as to persuade the receivers to take actions maximizing sender's long-term rewards.
2023
The MPP formalism finds application in several real-world settings, such as e-commerce and rec- ommendation systems [Wu et al. 2022]. For example, an MPP can model the problem faced by an online streaming platform recommending movies to its users. The platform has an informational advantage over users (e.g., has access to views statistics), and it exploits available information to induce users to watch suggested movies, so as to maximize views. The MPPs studied by Wu et al. 2022] rely on some limiting assumptions that prevent them from being fully operational in practice. For instance, they make the assumption that the sender has perfect knowledge of receiver's rewards. In the online streaming platform example, this assumption requires that the platform knows everything about users' (private) preferences over movies, which is unrealistic in practice.
1.1 Original Contributions
We relax the assumptions of Wu et al. [2022]. by addressing MPPs where the sender does not know anything aboul the environment. We consider settings in which they have no knowledge about transitions, prior distributions over outcomes, sender's stochastic rewards, and receivers' ones. Ideally, the goal is to design learning algorithms that are persuasive and attain regret sublinear in the number of episodes of learning T. The regret is the difference between sender's rewards cumulated over the episodes and what would have been obtained by always using an optimal policy. Persuasiveness about ensuring receivers are incentivized to take desired actions. Learning in MPPs without knowledge of receivers' rewards begets considerable additional challenges compared to the case of Wu et al. 2022]. Indeed, the latter design a sublinear- reggreeear--reetteee algorithm that 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 used to learn how to be "approximately" persuasive. As consequence, in this work we look for algorithms that attain sublinear regret while ensuring that the cumulative violation of persuasiveness grows sublinearly in T. This is the most natural requirement in all the cases where persuasiveness cannot be achieved at every episode, and it has already been addressed in related settings (see, e.g.. [Bernascomi al. 2022 Cacciamani al. 2023 Gan al. 2023
As 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-disclsunn policies computed by being optimistic with respect to both sender's expected rewards and persuasiveness requirements. We show that, under full feedback, OPPS attains Ō( ((VT) regret and violation. Then, we switch to the partial feedback case, where the sender only observes the rewards for the Saate-outcome-ee 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 an optimistic approach over infformation-disclloss
policies that are "approximately" persuasive. We prove that OPPS with partial feedback attains ((T)) regret and ((T1-%/2) violation, where E [12,, 1] is parameter controlling the amount of exploration. Finally, we provide lower bound showing that the trade-off between regret and violation achieved by means of OPPS is tight.
1.2 Related Works
We refer to Appendix for for additional related works.
The work most related to ours is [W et al., 2022], studying MPPs where the sender knows everything about receivers' rewards, with the only elements unknown to them being their rewards, transition probabilities, and prior distributions. Moreover, Wu et [2022] also assume that the receivers know everything about the environment, as to sclect a best-response action, and that all rewards are

---

deterministic. In contrast, we consider MPPs in which sender and receivers have no knowledge of the environment, including their rewards. which we assume to be stochastic. Other related works are [Gan et al. 2022]. studying Bayesian persuasion problems where sender sequentially interacts with myopic receiver in a multi-state environment, and [Bernasconi et al. 2023b]. addressing MPPs with 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. Finally, [Bernasconi et al. 2022 studies settings where sender faces a farsighted receiver in a sequential environment with tree structure, addressing the case in which the only elements unknown the sender the prior distributions over outcomes, while rewards are deterministic and known. The tree structure considerably eases learning, as intuitively 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 played repeatedly (Castiglioni
et al., 2020b, 2021b Zu et al.
2021
Bernasconi et al., 2023a], and works on online Markov decision
processes (MDPs) Auer al.
2008
Even-Dar et al. 2009 Neu et al. 2010 Rosenberg and Mansour
2019.
Jin et al.) 2020]. in particular those constrained MDPs [Wei al. 2018 Zheng and Ratliff
2020
Efroni et al. 2020 Qiu et al.
2020 Stradi et al. 2024].
2
Preliminaries
2.1
Bayesian Persuasion
The classical Bayesian persuasion framework introduced by Kamenica and Gentzkow [201]] models one-shot interaction between sender and receiver. The latter has to take action from finite set A, while the former privately observes an outcome w sampled from a finite set Ω according to a prior distribution E A(2), which is known to both the sender and the receiver P The rewards of both agents depend on the receiver's s action and the realized outcome, as defined by the functions TS. Ω x A + [0, 1]. where rr(W,, a) and rs(w,, a) denote the rewards of the sender and the receiver, respectively, when the outcome is W E Q2 and action a E is played. The sender can strategically disclose information about the outcome the receiver, by publicly committing signaling scheme Φ which is a randomized mapping from outcomes to signals being sent to the receiver. Formally, Φ Ω + (SS), where S denotes suitable finite set of signals. For ease of notation, we let ((-lw) E (S) be the probability distribution over signals employed by the sender when the realized outcome is w E Ω with ((s(w) being the probability of sending signal s E S.
The sender-receiver interaction goes as follows: (i) the sender publicly commits to signaling μ and draws signal ~ ((1lw); and (iii) the receiver observes the signal s and plays an action. Specifically, after observing under a signaling scheme d. the receiver infers posterior distribution over outcomes and plays a best-response action (s) E A according to such distribution. Formally, (s) e a), where the expression being maximized encodes the (un- normalized) expected reward of the receiver. As is customary in the literature (see, e.g., [Dughmi and Xu, 2016)), we assume that the receiver breaks ties in favor of the sender, by selecting best response maximizing sender's expected reward when multiple best responses are available.
scheme d; (ii) the sender observes the realized outcome
arg m Ewen (())(()))))
The goal of the sender is to commit to signaling scheme that maximizes their expected reward, which is computed as follows: Ewen ((w) E.es Φ(s (w) (5)).
2.2 Markoy Persuasion Processes
An MPP [Wu et al. faces a stream of receivers in an MDP, with each receiver myopically taking an action maximizing immediate reward. An (episodic) MPP is tuple M == (X, A, μ. P, (T (TR.)T)))
2022) generalizes one-shot Bayesian persuasion to settings where the sender
T' is the number of episodes
X, A. and Q are finite sets of states, actions, and outcomes, respectively.
| X + ((2) is prior function defining probability distribution over outcomes at each state. We let [(wlar be the probability of sampling outcome w Q in state E X.
In this work, we denote by ((X) the set of all the probability distributions having set X as support.
We denote an episode by E [1', where (a... bb is the set of all integers from to and [6] = [L b).
3

---

P:XxΩxA A A(X) is transition function. We let P(z'|az |a, W. a) be the probability of going from x E X to x' X by taking action a E A, when the outcome in state x is w E S2. {rs is a sequence specifying sender's reward function rss." X x Ω x A + [0, 1) at
each episode Given x E X, w E Ω and a E A, each (s, w2, a) for E [7] is sampled
independently from a distribution V's w, a) E A 1J) with mean r's (1r a2.a).
{TR is a sequence defining a receivers' reward function FR. : X x x A + [o, 1] at each episode f. Given E X. W E Ω2 and E A, each r w, a) for t E [T] is sampled independently from a distribution VRR w, a) E { 1J) with mean r TR( 42, a).
We focus w.l.o.g. on loop-free episodic MPPs, as customary in online learning in MDPs (see, e.g., [Rosenberg and Mansour| (019). D. In a loop-free MPP, states are partitioned into + 1 layers X Xo...., Xr, such that Xo == [ } and Xr, == { with 2n being the initial state starting the episode and vT. being the final one, in which the episode ends. Moreover, by letting K. := [0 1. 1]
for ease of notation, P(x'|ar, 42, a) > O only when x' E Xk+1 and E X for some k E K
At each episode of an episodic MPP, the sender commits to a signaling policy o X Ω (SS). which defines a probability distribution over a finite set S of signals for the receivers for every state E X and outcome w Ω. For ease of notation, we denote by o(-lz, w) ASS) such probability distributions, with ((s| ()) being the probability of sending a signal E S in state x when the realized outcome is w. Similarly to one-shot Bayesian persuasion, a myopic receiver acting at state x E X and receiving signal E S infers a posterior distribution over outcomes and plays a best-response action. We denote by (s. x) A the best response played by such receiver under the signaling policy & (assuming ties are broken in favor of the sender).
As customary in Bayesian persuasion (see, e.g., (Arieli and Babichenko, 2019 a revelation-principhl 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 S A. Intu- itively, signals should be interpreted as action recommendations for the receivers. Moreover, a direct signaling policy is said be persuasive if it incentivizes the receivers follow recommendations. Formally, é : X x Ω + A(A) is persuasive if for every state x E X and recommendation a E A,
Σ [[wl=))aaaa w) () (nn(s,,w,)) rn(a, w, bd (a, x))) 0.
Intuitively, the inequality above states that receiver acting at state is better off following sender's 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 best-response action 8o (a. x.).
Algorithm D shows the interaction between sender and receivers at E [2]. Sender and receivers do not know anything about the transition function P. the prior function Jr, and the rewards Ts. (ar, w, rr) w, a) (including their distributions). At the end of each episode, the sender gets to know the triplets (II, WE, for all A E Khthat are visited during the episode, and an addi- tional feedback about rewards. In this work, we consider two types of feedback. The first one calle full feedback encompasses all agents' rewards for the pairs (Ik, wk) visited during the episode, i.e., the rewards for all the triplets (Iy, Wk: a) for a E A. The second type-called partial feedback-onf consists in agents' rewards for the visited triplets (wa, Wk, ag)
Algorithm 1 -Sender-Reeeieen Interaction at t [T]
1: The rewards rs. (Ir w., a), FR. are sampled
2: Sender publicly commits Φz X $ + A(A)
3: The state of the MPP is initialized to 200
4: for k= =0....,;4 L- do
5: Sender observes outcome W. ~ pa(z))
6: Sender draws recommendation az ~ o(((zre,
7:
A new Receiver observes an and plays
8:
The MPP evolves to Tx+1 ~ P(- Wky Wkyas) as)
9:
Sender observes the next state 2441
10:
end for
11: Sender observes, feedback for every hs [0... L 1]:
full - [rs.( We; a), TR. (ITe, Wk, a)Jac
partial + rs, r. Wk: ax), FR.. (XR, Wk: ax)
Notice that Algorithm | assumes that receivers always play recommended actions. This standard in settings where the sender has not enough information to be persuasive at every episode, and
"The leop-free property is w.Loog. since any episodic MPP with finite horizon H that is not loop-free can be cast into a loop-free one by duplicating states H times, i.e., x E X is mapped to new states (I, k) with & [H]. 'In this work we use the adjective full to refer to 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 2006 Orabona 2019 would encompass agents' rewards for all the possible triplets (2, w. a). while full feedback terminology only consists in the rewards for the triplets with 24 and w we for some & K.

---

it motivates why learning algorithms are designed to guarantee that the cumulative violation of persuasiveness grows sublinearly in T, or, equivalendy. that the per-round violation of persuasiveness goes to zero as 7 grows [Bernasconi et al.) 2022 Cacciamani et al. 2023 Gan et al. 2023). Indeed, this ensures that it in the receivers' best interest stick recommendations.
The Learning Problem
In this section, formally introduce the learning problem tackled in the rest of the paper. First, in Section [. we extend the notion of occupancy measure to MPPs. In Section [.22 we formally intro- duce learning objectives. Finally, in Section 3.3 provide some preliminary elements needed by our algorithms, developed in Sections and
The proofs of all our results are in Appendixes D and
3.1 Occupancy Measures in MPPs
Next, extend the well-known notion of occupancy measure of an MDP [Rosenberg and Mansour 2019] to MPPs. Given a transition function P, a signaling policy d. and prior function μ4, the occupancy measure induced by P. Φ. and zi is vector q fe E [0. 10.1] xxxxXxXXXXXXX whose entries are specified as follows. For every XR, Ω a E A, and x' E Xx+1 with & K, holds:
a, x') = P (Ir, Wk, 0rs Fk+1) (x, a, x2) P. 1...
which the probability that the next state is x' after the receiver plays action a in state when the realized outcome is w, under transition function P. signaling policy o, and prior Moreover, we also let q P. (x. w. a) = Ex'ex PP (x, w, a, o,,²). q P.o. (x, w) ΣoEa q Po (x,wwa) and o (z) = Ewen p P. (Ir, w), for the ease of notation.
The following lemma characterizes the set of valid occupancy measures and it is generalization to the MPP setting of a similar lemma by Rosenberg and Mansour (2019].
Lemma 1. A vector q E [0, [||XxXXXXXXX is a valid occupancy measure of an MPP if and only if
i
Σ ΣEΣ E
a(x,w,a,x')= =1 E KK K,
x well aEA
(ii)
Σ ΣΣ E
Eq(a' a(1',,,,,,0 q(x) Ak [1.... 11 E X
F'EX--1 WElLEEd
(tii) ps = and μt =
where P is the transition function of the MPP and its prior function, while p and μº are the transition and functions, respectively, induced by (see definitions below).
As it is the case in standard MDPs, a valid occupancy measure E 00, xXXXXXXXXXXXXX induces a transition function P9 and signaling policy 6º, Moreover, in MPP, valid occupancy measure also induces prior function μa. These are defined as follows:
pa (1 = ((x,w,a,z) (alr,w) = g(x,wa)) a))
= g(z,w) w)
((x,w) 1 (w](r)
g
Thus, using valid occupancy measures is equivalent to using signaling policies, In the following, we denote by @ [0, xXxxXXXXXXXXX the set of all the valid occupancy measures of an MPP.
3.2 Learning Objectives
Our goal is to design learning algorithms for the sender in an episodic MPP. We would like algorithms that prescribe sequences of signaling policies Φ; that maximize sender's cumulative reward over the T episodess while at the same time guaranteeing that the violation of persuasiveness constraints bounded. Notice that, differently from Wu et al. [002)). we not aim at designing learning algorithms whose policies ot are persuasive at every episode /. with high probability, since this is unattainable our setting in which the sender does not know anything about the environment (see Theorem 6). Thus, in this paper pursue different objective, formally described in the following.
5

---

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:
max 4EQ
ΣΣΣ =EX WERGEA
alrs,wa) s.t.
(Ia)
Σ g(2, w. a) (alle,..))- 20 Ve E X E Va Va E Va' # (1b) WEn
Intuitively, Problem ①1 computes an occupancy measure (or, equivalently, signaling policy) maximiz- ing sender's expected reward subject to persuasiveness constraints. By letting rs [0. xxxx1 be the vector whose entries are the mean values rs w, a) of sender's rewards, our baseline is defined as OPT == r where q E Q denotes an optimal solution to Problem (T). In the following, we denote by o² an optimal signaling policy, defined as 6* := 6".
Metries We evaluate the performances of learning algorithms by means of two distinct metrics. The first one is the (cumulative) regrei Rr, which accounts for the difference between the cumulative sender's expected reward obtained by always playing o² and that achieved by using the signaling policies oe prescribed by the algorithm. Formally.
R = T OOP Σ EE(T]
Ts
Σ - TE|T]
where we let 9t == Piócii be the occupancy measure induced by dt. The second metric used to evaluate learning algorithms is the (cumulative) violation Vr, which is formally defined follows:
VT = Σ' LE[T] DEX WER
(,( a) (rn(x,w, x)) - rn(x,,,,
Intuitively, VT encodes the overall expected loss in persuasiveness over the T episodes. Our goal is to develop learning algorithms that prescribe signaling policies Φi guaranteeing that both Ry and Vr grow sublinearly in T. namely Rr = o(T') and VT = o(T).
3.3 Estimators and Confidence Bounds
Before delving in algorithm design, we introduce estimators and confidence bounds for the stochastic quantities involved in MPP, namely, transitions, priors, sender's 's rewards, and receivers' ones. In the following, we let N1 w, a, x²) E N be the number of episodes up to E [T] (this excluded) in which the tuple w, a, x²) is visited. Formally, Ne w. a, a,,²) ) == Ete 1 1-(2x (x, w, o,,²), where the indicator function is if and only if the tuple visited at r. Similarly, we define the counters Ne(a, w. ). Ne(2, w), and (2) in terms of their respective indicators 1, w, a). I, (x, w). and 1, (.), which are equal to 1 if and only if (z,ww, a), (I,w),, w), and x, respectively, are visited at
Next, we define the estimators employed by our algorithms. At the beginning of each episode t E [T], the estimated probability of going from E X to x' X by playing N, (x,,,,,.,r))
A, when the outcome realized state x is w E Ω is equal to Pe (='12,,, w. a) = max(1.Ni Moreover, for every E X and E Ω, the estimated probability of sampling outcome w from the prior probability distribution at state is defined Th, (w]xr) == max(1, (x)) Finally, for every state X, outcome 22 and action a E A. the estimated sender's and receivers' rewards are defined as r. (s, ()) == Σ- vs,- (a.... (2, and (n, == _=e [n.. (2,w,))
N, (2,w)
max(I.NN(
(ax(L..N(
Appendix B formally defines the confidence bounds employed by our algorithms. For the transition function P. at each E [T], for every X, w Ω and a E A. we provide confidence bound (z(2, w. a) for the probability distribution over next states associated with the triplet (I,, w, a). where the distance between distributions is expressed in || || -nom (see Lemma Similarly, we provide confidence bound (xr) in terms of ||. 1l1-norm for the prior μ(z)) at each state x E X (see Lemma 5). Moreover, for every x E X, E Ω and a E A, we provide confidence bounds EsS (2r, w, a) and (R, w. a) for sender's 's and receivers' rewards, respectively, associated with the triplet (z, w, a)

---

(see Lemmas 6 and for the full feedback case, while Lemmas [8 and 9 for the partial feedback one). In conclusion, for ease of presentation, for confidence parameter á (0, 1), we refer to the event in which all the confidence bounds hold-called clean event as ((). By combining all the lemmas in Appendix B {() holds with probability at least 45 (by applying a union bound).
4
The Full Feedback Case
We first address settings with full feedback, as warm-up towards the analysis of partial feedback.
4.1 The OPPS Algorithm With Full Feedback
We propose an algorithm called Optimisite Persuasive Policy Search (DPPS). At each episode, the algorithm solves a variation of the offline optimization problem (Problem (.), called Opt-Opt, obtained by substituting mean values with upper/llwer confidence bounds. Specifically, 0pt-Opt is optimistic with respect to both sender's s rewards and persuasiveness constraints satisfaction. For reasons of space, we defer Opt-Opt to Problem (2) in Appendix C Crucially, by using occupancy measures, Opt-Opt can be formulated as an LP, and, thus, solved efficiently. Notice that, since confidence bounds for P and μ are expressed in terms of 11ll1-noomm in order formulate Opt-Opo as an LP we need some additional variables and linear constraints, as described in detail in Appendix C
Al Algorithm 2 provides the pseudocode of OPPS with full feedback. At each E [T]. the algorithm first updates all the estima- tors and confidence bounds according to the feedback received in previous episodes (Line Then, it commits to the signaling policy di induced by optimal solution
Algorithm Optimistic Persuasive Policy Search (full)
Require: X. A, confidence parameter d (0, 1)
Initialize all estimators to 0 and all bounds to +00
2: for t =,,1,.. 1,
7 do
3: Update all estimators Pe, FR, and bounds
cx: Es, E5, ER, given new observations
q: 4 Solve Opt-Opt (Problem (
To to Opt-Opt, computed in Line Notice that, the occupancy measure qe resulting from committing to de (and used in the definitions of Ry and Vr) is in general dif- ferent from Tt as the former is defined
5:
di + -0:
6:
Run Algorithm[Tby committing &
Observe full feedback from Algorithm
8: end for
terms of the true (and unknown) transition and prior functions, namely P and p.
4.2 Algorithm Analysis With Full Feedback
Next, we prove the guarantees of OPPS wilh feedback. The first crucial component is the following lemma, which shows that Opt-Opt admits feasible solution at every episode with high probability.
Lemma 2. Given 8 E (0, 1), under event {6)) Opt-Opt admits a feasible solution at every E [7].
Intuitively, Lemma is proved by showing (a) that Problem T always admits feasible solution, which is the occupancy measure dº induced by the signaling policy that fully reveals outcomes to the receiver, and (b) that 7 is a feasible solution to Opt-Opt at every episode, under (()). Point (b) holds thanks to the fact that Opt-Opt optimistically accounts for persuasiveness constraints satisfaction, by using suitable upper and lower confidence bounds.
The second crucial component of our analysis is relation between the occupancy measures T computed by the DPPS algorithm and the occupancy measures qi that actually result from committing to o, under the true transitions and priors. This is formally stated by the following lemma.
Lemma 3. Given any 8 (0,1), 1), under the clean event E(6), with probability least 1 28. it holds that EiErry l/ 1 s O (L?IXI In (TIXIRIIA1)))
Intuitively, Lemma 3 is proved by an inductive argument that relates the uncertainty associated with both the transition and the prior functions to the || -orm difference between d and q 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 Rt achieved by OPPS, while the second one bounds its cumulative violation Vr. Formally:
7

---

Theorem 1. Given any å E (0, 1), with probability at least 1 - 76, Algorithm attains regret
Po S Ô (IA]
Theorem 2. Given E (0, 1), with probability at least - 76, Algorithm altains violation Vr S (L (|IXITTTA|| O
In (1/))
In conclusion, in the full feedback case, OPPS attains Rr and VT growing as O(VT). Intuitively, this is made effective by the fact that all the estimators concentrate at a 1/vT rate. As shown next, achieving such regret and violation bounds is possible anymore under partial feedback.
4.3 Lower Bound
We conclude the section by showing that the regret and violation bounds attained by the OPPS algorithm with full feedback are tight. Formally:
Theorem 3. Let å E (0, 1/4). For every algorithm that guarantees Py S (VVT) with probubility at
least - 6, there exists an abxolute constant ub >> and a problem instance which the algorithm must have Vr 2 (2(T) with probability larger than ip.
The Partial Feedback Case
In this section, we switch the attention to partial feedback. The crucial aspect that makes the case of partial feed- back more challenging than the one of full feedback is that, after committing to a signaling policy oi, the sender does not observe sufficient feedback about the persuasiveness of o, This makes achieving sublinear violation in the partial feedhack 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 in-
Algorithm Optimistic Persuasive Policy Search (partial)
Require: X. A. A. (0, 1). a E [0.
1: N + [[r"]
2: Initialize all estimators to 0 and all bounds to too
3: Initialize counter C(x, w, to for all (x, (2,w,,)
for 1,,...., do
5:
estimators P., Fs,, FR, and bounds cc, Sr, Es.e: En.e given new observations
Update
6:
if S | then
7:
(x, a, f- arg mi. x C(r,w,
Solve Opt-Opt with its objective
8:
q + modified as Evex (1,,,,,,
9:
C(r,w,)) + C(x,w,,))
10:
else
volved in persuasiveness constraints.
@o Solve Opt-Opt (Problem Appendix 12:
11:
This is necessary to build a suitable ap-
end
proximation of such constraints be
13:
di
+ 2ft
exploited in the remaining episodes,
14:
Run Algorithm by committing to Φ
which an optimistic approach simi-
15:
Observe partial feedback from Algorithm
lar to that employed with full feedback 16:
end for
must be adopted to control the regret. As result, there 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 able to optimally control such trade-off.
5.1 The OPPS Algorithm With Partial Feedback
We extend the OPPS algorithm introduced in Section to deal with the partial feedback case. The idea behind the new algorithm is split episodes into two phases. The first one an exploration phase with the goal of building a sufficiently-gon
approximation of persuasiveness constraints, so as achieve sublinear violation. Such phase lasts for the first N || episodes, where we let N = [ with E [0, 1] being parameter controlling the length of the two phases, given as input to the algorithm. The second phase instead devoted to achieving sublinear regret, and it follows the same steps of OPPS with full feedback (Algorithm 2). The first phase works by considering each (xr w, a) X algorithm commits to a signaling scheme induced by occupancy measure that maximizes the probability Σ Exex
x A for N' episodes. When (x, w. a) is considered episode / [T), the
x (1,, w, a, x') of visiting such triplet, while at the same time satisfying all the constraints of the Opt-Opt problem. Crucially, such procedure does not guarantee that every triplet

---

is visited N times. Indeed, there might be triplets (a, w, a) that are visited with very low probability. This can be the case when either transitions and priors place very low probability on (z, w) action is associated with very low receivers' rewards, and, thus, it must be recommended with very low probability to satisfy the optimistic persuasiveness constraints defindd in Opt-Opt.
Algorithm 3 provides the pseudocode of OPPS with partial feedback. Notice that the variables C(r, w, a) (initialized in Line 3 and updated Line 9) are counters used to keep track of how many times each triplet (x, w, IS considered during the first phase, namely when S N | Moreover, the algorithm ensures that every triplet is considered exactly N times during the first phase, by selecting them accordingly as in Line 7 Let us also observe that Algorithm 3 updates all the estimators and bounds (by using partial feedback) and selects the signaling policy Φe as done by Algorithm 2 The main difference with respect to Algorithm 2 is that q: used to define o, is computed different way during the first (exploration) phase (see Line 8
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 4. Given any å E (0, 1). with probability at least 1 - 76, Algorithm attains regret
RT < Ö [NL]X||O[IA| + SEIXTTIIIII
(1/6)
In order to prove Theorem 4 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. 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 sublincar in T. The two cases combined give the regret bound provided in Theorem 4 Next, we state the result on the violations attained by OPPS.
Theorem 5, Given any E (0, with probability at least 96, Algorithm 3 atttains cumulative
violation Vr S Ö (1A) T VN +AIVN + +AAVN++ 12VT)) where p = (1X(101111)3 3/2 /in (1/6.
Proving Theorem 5 requires non-trivial analysis. The result follows by showing that uniformly exploring over feasible so- lutions to the Opt-Opt problem leads to violation bound of the order of O(VN) during the exploration phase. Intuitively, this follows by upper bounding the occu- pancy measure in each triplet (I,, w, a) with an occupancy of a previous (exploration) episode, relative to the best response of the follower in state æ upon receiving action recommendation a. Theorems Fnd es- tablish the trade-off between regret and vi- olation achieved by the OPPS algorithm. deed, by recalling the definition of N (see
Lower Bound
Algorithm 3 Hern. al. [2022]
Order of T in Vir
1/2
3/3 Order of T in Rr
Line T in AlgorithmB3) B). it is easy to see that the algorithm attains regret RT < Ö(T") and violation VT < ((T)-%2), where E [2/2, 1] is the parameter controlling the trade-off, given input to the algorithm.
Figure 1: Trade-off between regret and violation achieved by
Algorithm 3 compared with the lower bound in Theorem O
The figure also shows the regret upper bound obtained in related setting by |Bernasconi al. [2022). with the blue area representing the gap that we are able to close in our setting.
5.3 Lower Bound
We conclude the section and the paper by showing that the regret and violation bounds attained by the OPPS algorithm (see Theorems 4 and (5) are tight for any choice of a E [1/2, 1]. We do so by devising lower bound matching these bounds (Theorem 6). Its main idea is to consider two instances of

---

episodic MPP involving receiver with two actions d1, 42 such that only ti provides positive reward the sender. one instance, receiver's rewards by playing ai are higher than those obtained by taking 02, while in the second instance the opposite holds. As a result, recommending action ai results in low regret in the first instance and high violation in the second one, while recommending action d2 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 6. Given a E [1/2, 11, there is no learning algorithm achieving both Rr = =(TT) and V/2 o/22- with probability greater or equal to a fixed constant vb O.
Theorem 6 shows that the bounds in Theorems and 5 are tight for any [/2, 1]. See Figure 1 for a graphical depiction. Theorem 6 also proves that it is impossible to achieve sublinear regret while being persuasive at every episode with high probability, when the sender has information about the receivers. Notice that, in our MPP setting with partial feedback, we deal with trade-off' between regret and violation that is similar to the one faced by Bernasconi et al.. [202]] in related settings, Differently from them, we are able to achieve an optimal trade-off for any a E [1/2, 1]. Indeed, Bernasconi et al. [2022] only obtain optimality for [2/2, leaving as open problem matching the lower bound for the other values of the parameter a (see Figure D]. Crucially, we are able to achieve trade-off optimality by using clever exploration method. Indeed, when considering a triplet (x. a) in the first phase, the OPPS algorithm does not simply commit to a signaling policy that maximizes the probability of visiting such a triplet, but it rather does while also optimistically accounting for persuasiveness constraints. This allows to reduce the violation cumulated during the first phase, thus achieving trade-off optimality.
Acknowledgments
This paper is supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamies: Computing Efficient and Fair Equilibria through No-Regret Algorithms". by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGeenraationFU program within the PNRR- PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of Al for Sustainability, No. 101 100377).
References
Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 2016.
Itai Arieli and Yakov Babichenko. Private bayesian persuasion. Journal of Economic Theory, 182: 185-217, 2019.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008.
Yakov Babichenko and Siddharth Barman. Algorithmic aspects of private Bayesian persuasion. In ITCS, 2017.
Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Giulia Romano, and Nicola Gatti. Public signaling in bayesian ad auctions. In Proceedings of the Thirty-Firsi International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 39-45. ijcai.org, 2022.
Ashwinkumar Badanidiyuru, Kshipra Bhawalkar, and Haifeng Xu. Targeting and signaling in ad auctions. In Proceedings of the Twenty-Ninth Anmual ACM-SIAM Symposium on Discrete Algorithmss, pages 2545-2563, 2018
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning to persuade in the dark. Advances in Neural Information Processing Systems, 35: 15:15517-15925 2022.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online Bayesian persuasion. In Proceedings
10

---

of the 40th International Conference on Machine Learning, volume 202, pages 2116-2183, PMLR, 2023a.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, and Mirco Mutti. Persuading farsighted receivers in MDPs: the power of honesty, In Advances in Neural Information Processing Systems, volume 36, pages 1-13, 2023b.
Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy, Hardness results for signaling in bayesian zero-sum and network routing games. In EC, 2016.
Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In EC, 2012.
Federico Cacciamani, Matteo Castiglioni, and Nicola Gatti. Online mechanism design for information acquisition. In International Conference on Machine Learning, pages 3299-3326. PMLR, 2023.
Ozan Candogan. Persuasion in networks: Public signals and k-cores. In EC, 2019.
Matteo Castiglioni and Nicola Gatti. Persuading voters in district-based elections. In AAAI, 2021.
Matteo Castiglioni, Andrea Celli, and Nicola Gatti. Persuading voters: It's easy whisper, it's hard to speak loud. In AAAI, 2020a.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. In NeurIPS, pages 16188-16198, 2020b.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Signaling in Bayesian network congestion games: the subtle power of symmetry. In AAAI, 2021a.
Mattco Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-rcceiver online Bayesian persuasion. In ICML,, pages 1314-1323, 2021b.
Matteo Castiglioni, Giulia Romano, Alberto Marchesi, and Nicola Gatti. Signaling in posted price auctions. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):4941-444 Jun. 2022.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadehh Li Han, and Shang- Teng. Mixture selection, mechanism design, and signaling. In 56th Annual Symposium Foundations of Computer Science, pages 1426-1445, 2015.
Shaddin Dughmi and Haifeng Xu. Algorithmic bayesian persuasion. In Proceedings of the forty- eighth annual ACM symposium Theory of Computing, pages 412-425, 2016.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-explooitaioon in constrained mdps, 2020.
Yuval Emek, Michal Feldman, Iftah Gamzu, Renato PaesLeme, and Moshe Tennenholtz. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computation, 2014.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe- matics of Operations Research, 34(3):726-736 2009.
Jiarui Gan, Rupak Majumdar, Goran Radanovie, and Adish Singla. Bayesian persuasion sequential decision- decision-making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5025-5033 2022.
Jiarui Gan, Rupak Majumdar, Debmalya Mandal, and Goran Radanovie. Sequential principal-agent problems with communication: Efficient computation and learning. 2023.
Itay Goldstein and Yaron Leitner. Stress tests and information disclosure. Journal of Economic Theory, 177:34-69, 2018.

---

Krishnamurthy lyer, Haifeng Xu, and You Zu. Markov persuasion processes with endogenous agent beliefs. arXiv preprint arXiv:2307.0331/1 2023.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4860-4860 PMLR, 13-18 Jul 2020.
E. Kamenica and M. Gentzkow. Bayesian persuasion. AM ECON REV, 101(6):590022115 2011.
Anton Kolotilin. Experimental design to persuade. Games and Economic Behavior, 90:215-226, 2015.
Yue Lin, Wenhao Li, Hongyuan Zha, and Baoxiang Wang. Information design in multi-agent reinforcement learning. Advances Neural Information Processing Systems, 36, 2024.
Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration in Bayesian games. In EC, 2016.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. Advances in Neural Information Processing Systems, 23, 2010.
Francesco Orabona. A modern introduction to online learning. CoRR, abs/1912.13213,, 2019.
Shuang Qiu, Xiaohan Wei, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. Upper confidence primal-dual reinforcement learning for cmdp with adversarial loss. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15277-15287. Curran Associates, Inc., 2020.
Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclosure means to security. In AAMAS, 2015.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5478-5486. PMLR, 09-15 Jun 2019.
Francesco Emanuele Stradi, Jacopo Germano, Gianmarco Genalti, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online learning in CMDPs: Handling stochastic and adversarial constraints. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 4/st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 46692- 46721. PMLR, 21-27 Jul 2024.
Shoshana Vasserman, Michal Feldman, and Avinatan Hassidim. Implementing the wisdom of waze. In Twenty-Fourde International Joint Conference on Artificial Intelligence, pages 660-666, 2015.
Xiaohan Wei, Hao Yu, and Michael J. Neely, Online learning in weakly coupled markov decision processes: A convergence time study. Proc, ACM Meas. Anal. Comput. Syst., 2(1), apr 2018. doi: 10. 10.1145/3179415.
Jibang Wu, Zixuan Zhang. Zhe Feng, Zhaoran Wang, Zhuoran Yang. Michael I. Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC 22, page 471-472 New York, NY, USA, 2022. Association for Computing Machinery. ISBN 97814 4503915044
doi: 10. (0.11445/4404486.5533333
Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. Signaling in Bayesian Stackelberg games. In AAMAS, 2016.
Liyuan Zheng and Lillian Ratliff. Constrained upper confidence reinforcement learning. In Alexan- dre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 620-629. PMLR, 10-11 Jun 2020.
12

---

You Zu, Krishnamurthy Iyer. and Haifeng Xu. Learning to persuade on the fly: Robustness against ignorance. EC. pages 927-928, 2021.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state all the main contributions made by the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
be expected to generalize other settings.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
All the assumptions are clearly stated in Section 2.1 and Section 2.2
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the theoretical results clearly state their assumptions, while all their proofs are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (lttps://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 7/nips. cc/public/guides: (Codeeuumissioooooooooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does nor include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, thcoe com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, or non-standary components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standarr components.
Please refer to our LLM policy (https: fattps://neuree //tur//ps....... sc/Confferncees/2000 for what should or should be described.
19

---

Appendix
The appendix is organized as follows:
In Appendix A we report the 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 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.
Appendix we report the omitted proofs related to the partial-feedback setting.
A
Related works
Sequential Bayesian persuasion The work that is most related to ours is |w et al. 2022 which introduces MPPs. Specifically, |Wu et al. [022] study settings where the sender knows everything about receivers' rewards, with the only elements unknown 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, as select 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 be stochastic. Moreover, Wu et al. [2022] obtain a regret bound of the order of O(VT/D) D), where is a parameter related to receivers' rewards. Notice that such a dependence is particularly unpleasant, as D may be exponentially large instances in which there are some receivers' actions that are best responses only for a "small" space of information-discloonne 2022), which studies a Bayesian persuasion problem where a sender sequentially interacts with a myopic receiver in multi-state environment, and [Bernasconi et al. 2023b), 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 nor concerned with learning problems, but with the problem of computing optimal information cioommatio-diiclouure policies. Finally, (Bernasconi et al. [2022] studies settings where sender faces a farsighted receiver in a sequential environment with tree structure, addressing the case in which the only elements unknown the sender are the prior distributions over outcomes, while rewards are deterministic and known. The tree structure considerably eases the learning task, as allows to express sender's expected rewards linearly in variables defining information-disclossst policies. Intuitively, this allows to factor the uncertainty about transitions in the rewards at the leaves of the tree.
policies. Other works related to ours are (Gan et al.)
Online Bayesian persuasion It is also worth citing some works that study learning problems in which one-shot Bayesian persuasion setting is played repeatedly (Castiglioni al., (020b] 2021b Zu et al., [2021] Bernasconi et al., [2023a]. These works considerably depart from ours, since they do not consider any kind of sequential structure in the sender-receiver interaction at each episode.
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. [2008). [Even-ar et al. [2009), Neu al. [2010) for fundamental works on the topic). In such settings, two types of feedback are usually investigated. The full- iull-information feedback setting [Rosenberg and Mansour 2019]. in which the entire reward function observed after the learner's choice and the partial feedback setting (Jin et al. 2020). 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 fixed distribution (see, e.g., Zheng and Ratlifi (2020). Wei et al. 2018 deal with adversarial reward and stochastic constraints. assuming known transition probabilities and full information feedback. |Efroni et al. (020) propose two approaches to address the exploration-eepllotatii dilemma in episodic constrained MDPs These approaches guarantee
Online learning in constrained MDPs
20

---

sublinear regret and constraint violation when transition probabilities. rewards, and constraints are unknown and stochastic, and the feedback partial. Qiu et al. [020] provide a primal 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, [Stradi jet al. [2024) propose a best-of-both- sost-o--both-worldd algorithm in constrained Markov decision processes with full information feedback. While the previous works are related to ours, the aforementioned techniques cannot easily generalized to our setting as they are not designed to properly handle the presence of outcomes and IC constraints.
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, introduce confidence bounds for transition probabilities P(xr [20, (,,,,,))) a). by generalizing those introduced by |Rosenberg and Mansour [2019) for MDPs to MPPs. In the following, we let (r, 42, a). respectively (z a,,,w, x'), be the counter specifying the number of episodes up episode E [2] (excluded) in which the triplet (æ, w, a), respectively the tuple (æ,w, a, x'), is visited. Then, the estimated probability of going from
X to x' E X by playing action A, when the outcome realized in state æ is w E Ω is defined as follows:
Ne w. 0, x')
Pe (a'lo, = max {1, (e(x,,,a)) w.a)}
For any ò E (0, 1), the confidence set at episode [T'] for the transition function P is Pe == ((ema))X x Pt p.w.a where p. a of transition functions defined as:
Pew. aamaa_ff. p:: P(1l,,,,)- P,(-,,, m) (((x,,)a))
where P(- w,, a) and Pa(-Ix, w, a) are vectors whose entries are the values Plx'Ia, ui and P,(a'(,,,, a). respectively, while e (x, confidence bound defined as:
2) X In [ (TIX))())))))
(z,
max (1, (1,,w,,)))
The following lemma formally proves that P, is a suitable confidence set for the transition function of MPP.
Lemma 4, Given any 5 E (0, 1). with probability at least 5, the following condition holds for every & E X, Ω A, and E [T] jointly:
|[-(lzz.,.) a) - (,(la,,,,)) a) I c w. a).
Lemma g can be easily proven by applying the same analysis as presented in Auer et al. 2008 and employing union bound over all ar a, and t..
B.2 Prior distributions
Next, introduce confidence bounds for prior distributions. For every state X, define (-1x) E ((2) as the estimator of the prior distribution at x built by using observations up to episode E [T] (this excluded). Formally, the entries of vector (-(())))) are such that, for every Ω:
(w(wx) = Erettn 11 (x,
(1,x
where (2: is the number of visits to state up to episode L (excluded), while 1 1, w) is indicator function equal to 1 if and only the pair (x, w) is visited at episode
The following lemma provides confidence bounds for priors.
21

---

Lemma 5. Given any 8 E 1), with probability at least 1 - 6, the following holds for all X and jointly:
[|x(11>) - (-1+1)))1 & <((x),
where we let (e(x)= =
2 (n(7)x1/s)
max (1))
Lemma follows by applying Bernstein's inequality and union bound over all states and episodes.
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 's rewards under full and partial feedback. For every I E X, w E S2 and E A, the estimated sender's and receivers' rewards built with observations up episode E [2] (this excluded) are defined as follows:
Fs, = Er rs, (z, w, a) (z,
max 1, (2, w, a)}
(R,((Z,wa)) Eree- RR
(3,,wa max 1, No (z, w,)
where (,r w; a} is an indicator function equal to 1 if and only the triplet (æ, (,, visited during episode
The following lemma provides confidence bounds for sender's rewards, when full feedback is available.
Lemma 6. Given any ó E (0,1), with probability at least - 8, the following condition holds for every x E X, It E A, and E [T] jointly:
|rs w, a) - (s,,(x,,,a) S (s,(I,,,a))
where (5,(2,,,a) == min {1,
In(aTIX) 21/6)
max (z,0))
Cemma@folloove by applying Hoeffding's inequality and a union bound over all x, w and t.
The following lemma provides confidence bounds for receiver's rewards, when full feedback is available.
Lemma 7. Given any d E (0, 1), with probability least - ô, the following condition holds for every x E X, w E Ωt E A, and E jointly:
|FR(,, w. a) - FR, w. a) S ER.(,,
where (n, (I,W,, a) = min
In(e2 XIIRI/))
max (1, (I.4))
Lemma 7 follows by applying Hoeffding's inequality and a union bound over æ, w and
The following lemma provides confidence bounds for sender's rewards, when only partial feedback available.
Lemma 8. Given any d E (0, 1), with probability least 8, the following condition holds for every x E X, Ω2 E A, and E jointly:
(rs w,)) a) 75,,(a, (1, a) S (s,
where Es,((z, min {I.
In (n(3T)))((А/))) max (L,
)
Lemma follows by applying Hoeffding's inequality and union bound over all v, w, a, and
Finally, the following lemma provides confidence bounds for receiver's rewards, when only partial feedback is available.
22

---

Lemma 9, Given any ó E (0, 1), with probability at least 6, the following condition holds for every a E X, Q2 E A, and E [T] jointly:
|R( w. a) - -T (2, w. a)) S (R.(I,,,a),
where (n,( == min {1
In(ar x11()11118)
(o..).).
Lemma follows by applying Hoeffding's inequality and a union bound over æ, w, a, and
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 ① since the objective 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 || |/1 differences between the empirical and the real mean of the distributions. Thus, in order insert the aforementioned confidence bounds in L--formulation, the related constraints must be linearized by means of additional optimization variables.
The linear program solved by Algorithm and Algorithm
3is is the following.
max g.
ΣEΣ ΣEΣ Σ WER d'
dl a' ( as))((,w)a)) s.t.
(2a)
TEXi WER
((,,w,,x')) =1
4k: @ L 1] (2b)
ΣΣ ((,'w - Σ ((,
d'EX2-1 WEfl
wERdEAZ'EXe4
Vk Vhe [o..0...L 11, Vr Xx (2c)
((r,w,a,x)) - P,(2'lz,us,a)
Σ (x,,,,,x") S ((x,w,,,x') x" exEX
Wk E [0 ... L 11, (a,,,,, Xx x A X (2d)
P((''1,a,w) Σ
((o,w,axx)) q( q( 0.) (Z.
#"EXx11
Ak E 10 L 11, (1,,,,,) E X1 xx (2e)
(I, S (1
Σ (I,,,,a,")
o' x'EXxt1
e'EXet1
Vk 0. L - (), E X x x (20
w) - -1,(w(z)) Σ a(Ixww)) < ((I,w)
Vk E L 11, E X2 X (2g)
w'En
(x(w(x)
Σ (Z0 w/) ((x,w) S ((1,w)
tk 10... I. 11,V(r,W) E Xx x Ω (2h)
W'El
Σ ((z,w) < (z(z) Σ a(),w),
AA 10... L 11 (2))
wEn
WE
Σ g(z,w,,,')) (F. (R,(Z,,,,))
WER
- -FRi(Z, (RI( 20
Vk E (0 L - 11, E X x V. A (2))
((I,,,,x')2
vk
L - V(,, x Ax X (2k)
23

---

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 (2) is related to the confidence interval on the transition functions, Constraint (2e) is still related to the confidence bounds on the transition function, Constraint (2r) allows to write
linearly the constraints related to the transition functions even if the interval holds for the || 111- 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 || -I. Constraint 2 is the optimistic constraint for the Incentive Compatibility (IC) property and, finally, Constraint 2k ensures that the occupancy greater than zero.
Lemma 2. Civen 8 E (0, 1), under event {()), Opt-Opt admits a feasible solution at every E [T].
First we notice that under the clean event {6) the true transition function P and the prior μ 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 g" to an incentive compatible occupancy measure, under {6), we have that:
Proof.
Σ WER,
(I,, (T), (R, -TR, 4. + (R, Z
Σ wEft EX++1
(',,, - 2 0,
- [R(,,
for any E [L - 1]. (x. Xx x A, Va E A. As a result, if q" is incentive compatible, it belongs to the optimistic decision space, which concludes the proof.
D Full feedback
In this section we report the omitted proof related to Algorithm 2 transition function estimations still hold when the feedback is partial.
Notice that the bound on the
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.
Lemma 3. Given any 5 (0, under the clean event (6)), with probability at least 1 - 25. it holds
that Enemyy ll T11 s o ( (FTXXIX
Proof. We start noticing that, for any (I,w a) E x Ω x A, we have:
Σ
(2,,,,,)
(2,
x'E
Σ
(I,,,
D'EXM()11
Σ
- -
d' d'EX((1)+1
+
Σ
(x)
d'EX
Σ
- R P((
d' d'EXH()+1
Σ
( P (2, -poo:,)))))pppooo.sss
d'EXMOit1
= - ( - ( (x, a) + (2), P(),,,,a))ll
24

---

Thus, summing over t [T] and (z, E X x Q x A we obtain:
Σ 1E(T]
a/
Tell1 S Σ Σ
(I, o (I,
TE(T] =ex
+ (I,,, a))li)
Next, we focus the first part of the equation, noticing that:
la Pebeiee (r,w, a) o Pioeil (z, w. a)l
S l Pi (2, - g w. a)) + ( (r, (.l.a)----eee &fo (x, a)
Bound on layer we have:
(2, We bound this term by induction. At the first
ΣΣ To Eg El EgEA
1 Piobeeti (10, wo, ao) -0 Perorn (I00 wo: ao)l
Σ Σ
wo) - (o)
anER
(Zo. ((xr, wu)l
WoE
- (xo)
Σ
1lee (eo wo) p(zo,
WoER
observing that Xo foo}. Now show that, if the result holds for 24-1, it holds for ax, follows,
ΣΣD Σ
1g Porteott (Irks wk, ax)
q Pi (M wh, ax)
TEEX ALEA
Σ
33
Σ Pooooei (IK- Wk- ak-1)
EE
an
Prodestt (Ik Wk- OK-
(n- ( We- ax- )ula, Mor (ur wTs) wa)
Σ
E Σ
Σ
la Penderste (FC- Wk ax 1)
1E-1EXx-11 Wt- wh-1 E D WIER
q Purte. (F W ag Pa az (1 wk)l
33333 Σ Zt-1 E We-1 Elt 01-1 EA E WiER
1g Prodritt (JX- we- a2-1))
w ak-
q Peitre (IK-1,WE-1, (1 (T
3 Σ
Σ
E Σ
Pro (xx Wk ak-1).
1 Wh wk-1Ef 0g- E E WEER
q Pa 1, Wk- au Po 1, (1 wa)]
Σ 3
l Priteith (Ik 1, Wk 11 Pr.de. (xx - ( ak
Zt-1E Re-1EXx-1kuu--10 Elt
+ Σ (Ps
Σ
[e(( - plx wk)l
ExEX,
wee
Thus, by induction hypothesis, it follows,
ΣΣΣ
Pridente (Ik, Wh, ak) Pribein (Ik, (k)))
X WLER
25

---

q ( - (((1ax))11.
==0 E.
Bound on (1Penei( w, a) Pioee (x, w; a)l
To bound this term, we proceed again by induction.
Thus, notice that:
Σ ΣED
Σ
lg Puiee (Z1, a1) - Pi (11, a1)l
#I EAEEEA
Σ E
Σ3 lu(2n, wb wo) wD) (a (ro wa, oa, (n) wi (11
wIER MeERaEARREEN EX1 WI
- -M(zo, wo wo)de (aol
20, wo, wo) (( to wo, ( wi do wr))
E
uo)o To, wo) WoEfagEA
Σ
Σ
Pr an)
P( 20, wa, ag))
mi
Σ Σ
p( (11,,,1)0(as122,..
W WIERaIEA
Σ
E
q P.de (2o, wo, ao)l Pt (1(1100, wo, ao) P(. wo, ao)llı.
WoES ag
Now, we proceed with the induction step.
ΣEΣ
Peioeil (JR Wk: a&) ạ P. (Kk
#xEX, We Elt aRE
Σ 333333
(1 1, ak-
Th 1 We 1E--EERR-p LEERo--EAaaa 1EA We WEERRAEA
P. 04-
Pibe (2 P /a wk)l
E
EE
Σ E Σ
1 1e- 1
P PP ak-1)
333
1 1e---ERRa--AAz-e- 1EA
Σ
33
Zk-i k- Wk-1 Rk- EA
q P.tr. 1f
ΣEX
Σ
Σ
lg Pertri (1ro)u((Kkk11100 (3 ak-11 10
2h 8h-16 Xx Wi EE OER
Σ Σ
ΣE
Pibr. (Ik-1, We W1 1,
Zt- Zx-1EX 1-1 Wh-1 CE-1EA
(1P(-122-1, -x-1 W6 ax-1)ll1
Thus by induction hypothesis we obtain,
ΣΣ> Σ
la
Potrel (Ix, Wk: ox) - (Ix,
ExEX 4i EEA
k-1
q Pudcest (1e (Ke
P(- Wa, a.)ll
e=0z,ex, a.ER
Returning to the quantity of interest we have:
L-lkl
Σ llg. - Hell 2 Σ MEΣEEY
(oo W., PP We, az)+
EE[T]
(E(T] K= e=0 Z,EX, w.E
26

---

L-1 ΣΣΣΣ Σ
We: a2)1l1 +
g Peobema (I))) (raa)lle((( - p (111x))l11 (3)
1 K= s=0 x.EX.
We proceed bounding the first term in Inequality (3.. Fixing layer &s 10,, 10....,L. L 11. employing
Azuma-Hoeffdinn inequality and noticing that [ [-, Wk, ak) - P(- Wk: an I S 2, we have, with probability 28:
ΣEΣ E [ == 2,E, W.R
E
( Was a.) [ Pc(- We, 0s)
X x1 In TIX]RII
k-1
Σ3ΣΣΣ 1E|T] X,EX, 4, W.ERE
Le Le( (2e ag Wo}
+
Σ
2|
2T In
max {1, a,)}
==0
k-1 +
27
In
2
2I In
8
==0
TIXIAIIA 8
4
| AT| In
2|X
2T In
Finally summing over L, we have, with probability at least 1 26 (which derives from a union bound between Azuma-Hoeffdine inequality and the bound the transitions):
k-
ΣΣΣΣΣΣ
Σ
Proesit (. Was dx)llPP(H(ar War a.) - Wo: as)ll
NE[T] k=0 ==0 X.E.
27 In (TIXI
L
27
To bound the remaining term in Inequality
we proceed as follows,
L-1
Σ ΣΣΣ
Pr.tr H (zx) (2.))11(((z..)) - -+1x.,))
tE[T] k=0 ==0 xx
1-1 k 3Σ Σ
q ( - ((1x:s))1++
(E[T] 1= 8=0 E.
+ΣΣΣ LE|T K= EX,
Σ
(e)) - o (p))))((s)) [(l() - 1((1xx))l1
q Pibct (2)) - ((-1xx))11+
LE|T 0= 0=0 n e
1-1 ΣΣΣ
2 Pg - of ((o))())))
tE|T] K=0 0000xE
q Piol (
- 11-1
AE(T] k=0
0=0 n,x,,
33Σ333 E K= =x..E. a.E.A
2 Pribee (I, Ws, - - Piór (Ix, Wey as)
The second term is bounded by the previous analysis paying an additional factor, while, bound the first terms we apply the Azoff-iogg inequality and proceed as follows:
ΣΣΣ EE(T] xx,,,
Σ
(W)( - 1((x), wa)l
W.ER
27

---

1-1 Ieles)llaa((aa)) (-11a)))1 + | V
ΣΣ E k= 8=0 Ex,,
Σ
Σ
2T in
1- Σ ΣEEΣ TE[T] k=D Ox,EE
2/21 (
77 8
+ +
max (xx))
TIX (88
L
s 2T, 21/X11//711
27 In
with probability least - 2d, given the union bound over the Azuma- and the bound the outcomes. Finally, with a union bound between the bound on the transitions and the outcomes (which both encompassed by the clean event) and the Azuma-Hoefiding inequalities, with probability at least 1 - 46, we have:
11 T 111 S s0 1 L| In 1E|2
[XXI))
T. Tin + X
Σ
(8)
+ +
T T| In
+ LA x
Thn
oo L3 L
5
which concludes the proof.
D.2 Regret
In the following section we show that Algorithm 2 attains Ö(VT) regret. This is done showing that the confidence intervals over transitions, outcomes and sender reward concentrate a rate of OLL/VT).
Theorem 1. Given any 5 E (0, 1), with probability at least 1 - 76, Algorithm attains regret
Rr S Ö (LIIXIVVT|A|[)]]((((
Proof. We notice that the regret can be decomposed follows:
RT Σ 13 4:)
Σ SE[T]
r3(
Te)
+
Σ EE(T)
rs
(ee ge)-
EE|T]
The second term is bounded by Hölder inequality and applying Lemma 3 bound the first term we notice that, under the clean event, and by definition of the linear program solved by Algorithm 2 holds:
(rs + 25s,)) 2 (Fs, + Es..) 2 (Fs.. + Es.) 2 2r.
Thus, have.
Σ 15 [E[T]
②)) 2
L. 2 Σ TE[T]
5 + 2
Σ TE(T)
(5. qc).
AE[T]]
The second term is bounded by Hölder inequality and applying Lemma 3 which holds under the clean event, with probability at least 25. To bound the first term we employ Lemma 10 which holds under the clean event, with probability least 1 - 5, and union bound, which concludes the proof.
D.3 Violations
In the following section we show that Algorithm 2 attains Ô(VT) violations. This is possible since, in the full-feedbuck setting, the incentive compatibility constraints collapse to standard linear constraints.
28

---

Theorem 2. Given E (0, 1), with probability at least - 75, Algorithm attains violation
VT S 5 (TA In (4/)
Proof. In the proof, we compactly denote the receivers' best response in given state-action pair (z, a) E X x at time t E [7] as b' (a, z) = d0h (a, x). Furthermore, by employing the definition of the linear program and summing
(z, a). for any episode t, under the clean event, it holds:
Σ (r,,,,,)) a) (FRo( w, ()) ())
(a 2)) + ER,l w, (a, x))) 2 0,
which, in turn, implies that:
Σ
ae a) (FR(x,,,0)+ 25R.:.,,)222.......... - -ra(,, (,, w(, 2
REX
Thus, noticing that, in the full-feedback setting, have (n, obtain:
(n, ba,
Σ
Cc a) (ra(æ, (a, (r((s,,,)) &
Σ
zEXwEnt,EA
S
Σ
#EXwER
where {R.(I,W)
[n73 X /8)
max(11.N, (z,w))
Now we combine the previous equations to bound the first term of the last inequality as follows:
Σ
Σ
Te(s, a) (rn(æ, (, (x,
AE[T]
=EXWERD,EE
Σ
Σ
Ce ((.,())
[E[T]
mEXwEn
Σ
Σ
Σ Σ (T(x,w) (m)
tE|T wEXwER
KE/2 WERWER
(TIXI181AAI)
< Σ
Σ
gllz (R, +0 |2xX2 T| In
(5)
8
1E[2) #f XWES
Σ
Σ
(E,,W) +4 Σ Σ
(g0(1, 1,(a,w))
tE|T REXwER
1E/21 zEXWER
T
|2 ||
+0 111X
TIA|S In
8
=4 Σ Σ
((I,,) +4 Σ Σ
(g((x) 1c(x))
(E[T] seX,eE
xEX
T
|2
L2 T|A In
8
<4 3 Σ
((Z,w)RR((,, 4|X 2 X
tE[T] REX
T [A)
+0
1.1XXN
TIA
In
(6)
8
1L X
TIXIRAIAI
+0
L x
T| In
(7)
8
29

---

0
L 11X1 II In
where Inequality (5) holds by Hölder inequality and Lemma 3 which holds under the clean event, with probability least 1 26, Inequality (6) follows by Ayuma-Hoeffding and Inequality ( by
inequality and observing that + ExEr vi S 3/T.
Finally, returning to the quantity of interest, we bound the cumulative violations follows:
VT =
Σ
Σ
(r(r, b', rn(,,w,a))
tE|T) REXWERQ,EA
Σ
Σ
(r,,u,
w,, rn(x,,,,))
(E[T] WEE
Σ
E
(0(2,,,a)) (x, a)) (rR(I, b' (TR=))))
TE[T] wEX
E q ((a)) -
E El (e)
rE[T]
Σ tE[T] WEERR,
Σ
ac (Ta(,,,) - - rR(x,,,
+0 L2|X T In TX
1.3 x T1 (TIXIISIIA)
00
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 - 76 employing a union bound over the clean event, which holds with probability at least 46, the Hoeffdin inequality used above, which holds with probability at least 1 and Lemma 3 which, under the clean event, holds with probability at least 25.
D.4 Lower Bound
Theorem 3. Let 8 E (0, 1/4). For every algorithum that guarantees Pe < OVVT) with probability at least 1 8, there exists an absolute constant ub >> O and problem instance in which the algorithm must have Vr ((VT) with probability larger than tb.
Proof. We consider two instances with single possible outcome and a single state. In the following. omit the dependence the sender and receiver utility from these parameters. We assume that the sender's 's utility in the first instance is a deterministic function given by r (3)) = and r (a2) = O, Be(1 /2). Meanwhile, the sender's utility in the second instance is r3(()) = and (a2) = 0, while the follower's 's utility Be(1/2 E) and (a2) Be(1/2 + 2e), for some (0, 1/2). Thus, the
while the receiver's utility is given by (a,) ) Be(1/2 + c) and r (7))
equal to (a))) sender's ' regret in the first instance is given by:
R
Σ 0 (az),
since the optimal signaling scheme is the one that always recommends action aj E A in the first instance. In the following, we define Ipl (respectively, [P²) 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 constant C' as follows:
T (as) SCVT) 21-1
pl SCVT) =P'
=P
Σ
(8)
30

---

for some E (0, 3043/4). Furthermore, by Pinsker's inequality and Equation g the following holds.
p2 Σ (02) S CVT 21-1-
1--タ- (DLL(PI.F P2),
where we denote with (x the Kullback-Leebler divergence between two probability measure. By means of the well known divergence decomposition, have:
(KL(P P2) T (Be(1/2 2e), Be(1/2)) I 16c
(10)
where in the latter inequality used the well known property ensuring that Daz (Be(p), Be(g)) (p-g)² [[-0) Furthermore, by means of the latter inequality and Equation (10) we have:
-
p Σ (az) CVT) 2 21-n 26
We now consider the receiver's violations in the second instance which be computed follows:
V?
(a1) (F2((2) (a))))
= Σ (ar))
Then, by means of Equation
we get:
12 (v e(T CVT)) p2
2 (a)) 2 E(T E CVT)
[=]
p2
T
(02) 2 T T-CTT
T
Σ (02) S CVT) 2 11-1 - V16.PT.
p2
Finally, by setting
16/T we get:
pl Pa(R R4
P S CVT) 2 2-
Then, the latter result implies that:
p2
V 2 ( (T- =p² (VZ 2((VT)) 2 - v16.2T
3
77
which concludes the proof.
E Partial feedback
E.1 Regret
Lemma 10. Under the event E((), with probability at least 1 8, it holds:
[
Σ LE(T)
S. 50
5
(1111118111)
T|
Σ St S 50 2E(T)
31

---

Proof. We bound the quantity of interest as follows:
2 1
9
Σ
(s. + 2T
(11)
[E
[E|2] ZE
Σ Σ
L ( + 4 27
max {1, (x,
[E ZEX WEE
3T X |
91n
Σ
VNr(a, + LV 21 21'In
(12)
X (
91
|2]|
Σ
NT(x, + L1 27
(13)
8
WER
3T X1
T T 27 8'
(14)
8
where Incquality IT holds by the Azuma- Hoeea--oeffdiigg incquality with probability 1 1- Incquality (22 Vi I 3vT, Inequality (13) follows from the Cauchy-Schwand w, (2,,wa,)) LT. With the
follows by observing that + Eie(rr 1
inequality, and Inequality (14) holds, noticing that Exe Nr (2,
same analysis, we can prove that the same upper bound holds for EiE(r) 5h concluding the proof.
Theorem Given any ô (0, with probability least 1 78, Algorithm attains regret
Rr S Ö (NLIXI1O[AII LA /TI (4/)))
Proof.
As a first step, we decompose the sender's regret as follows:
Rr Σ
(9 (q" qc)
LE[T]
Σ
r3(9" - @ + Σ
Ts ( - ②t)
1E[T]
AE[T]
[ A 8
r3 - 9)) +
T| In
(15)
[E[T]
We observe that the last inequality holds under the event E(), with probability of at least 1 28, and it derived by applying the Hölder inequality and employing Lemma To bound the first term in Equation 15). we notice that under {()), we have:
(rs + T
(Fs, + Es.e) Tg 2 (F5. + Es.:) 2 r3g4"
for each /. >> N [||2||||| because of the optimality of qr. Thus, rearranging the latter chain of inequalities we have:
Σ TE[T]
r5(a 7
Σ
rT - -e)+
Σ
r - Tr)
N> dMll
< X +
Σ
T - qe) + Σ S3.9
(rE(T]
:E(T]
S X
|1|XX T| In
T
TXI11
8
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 I0
32

---

which hold with probability of at least 1 36. Substituting the latter inequality into Equation 15 we obtain:
RT SO O NNIX + = T| in [ )
Finally, we observe that the previous upper bound holds with probability at least 1 - 76. This follows by employing union bound and observing that {() holds with a probability least 1 46, which concludes the proof.
E.2
Violations
In the following we denote the receivers' best response in a given action a E A and state x E X as (a, x) = 15th (a,
Lemma 11. Under the event E()) the following holds:
T
V SO T M1
Σ (E|T) #EX
E
al
with probability al least 1 - 36.
Proof. As first step, observe that by employing the definition of εn, and noticing that q is feasible solution to LP
(2) for each t E [T] under the event E(6), we have:
Σ w, (rn(z,w,a) a) (n,( w, a) rn(a, D' x)) + w,, (a, (a, 2 De XWEER,EA
Σ a,lz, a) (FRo(I,w,a) + a + (n, (a,x))) 2 0.
Then, rearranging the above inequality we get:
Σ a, a) (Tna(a,,,b'aaaaa (n, REXWER,EEA
2 Σ (x, a) (ER.(l,, + ER.( ((,
(16)
#e =EX:
Furthermore, we can decompose the receivers' violations follows:
VT Σ
Σ
(al(,,w,)) + d (2,, a)) (ra(I,,, d' (a),x)) (R(x,,,
rE|T] ZEX WESLIEA WEE.L..E
50 1,2 1.1x1
In
Σ Σ
(x,,, w, a) (rn(x,,, (a,))) vn(a,w,a) a))
1E[T
DEX.ERR.EE
(1I11111111
5
17 12IX
in
Σ
Σ
(ā( w. a) + (e w, a)) (EnilI, a) + ('(,
LE[T
DE
TXI
00 L3|X
T| In
Σ
Σ
(w,,w,)) (2ERe( + 2ER w, (a,x)))
xE[T]
33

---

1 LIIX | T|Al|S| In TX )
5o
+ Σ E (, ( b, (a x)) rE[T] zEX,
where the first and third inequalities hold by Lemma the second inequality is a consequence of Inequality (I6), and the third inequality follows by means of Lemma TO which holds with probability of at least 1 8. Therefore, employing a union bound over the events of Lemma and Lemma 10. the previous result holds with probability at least 1 - 35, under the clean event.
Theorem 5, Given any E (0.1) with probability at least 96, Algorithm 3 attains cumulative
violation Vr S SO (IAI VN IAIvN+ + I2VT)) where p = ([X])02]11) (1/6).
Proof. As a preliminary observation, we notice that Algorithm is divided into N epochs of length t= [ where in each epoch, Algorithm 3 maximizes the probability of visiting each triplet (x, w, a). In the following, we define ty (z, w, a) E [T' as the round in which Algorithm maximizes the occupancy of the triplet (z, wi a) the epoch E [N I]. Formally:
a, x') is the objective function of Program by (I, u, a) {t [je+t,.......................... (i+1)E]1 Σ g( a,,,w,,,0
Furthermore, for each occupancy measure with t E [2]. the following holds:
q0(2, w. a) = q(x w, b' (l(a, x)) S 9t, (a.))) w, b, (a,
(17)
for each; [N where g E an occupancy measure that satisfies the IC constraints of the offline optimization problem (see Program (T). The first equality above follows by observing that there always exists an occupancy that satisfies the IC constraints that recommends action D' (a, a)) E A instead of a E A in the state x E X with the same probability of q:. The inequality, on the other hand, follows by observing that the space of occupancy measures satisfying the IC constraint of the offline optimization problem (I) is always a subset of the feasibility set of Program (
Furthermore, by Lemma
have that:
(TIXI[RIAA) 5
V S
1
T| In
Σ
Σ
ae w; En, w, (a,
KE|T]
We focus on bounding the second term in the inequality above in the first N rounds Algorithm Thus, with probability at least å we have:
Σ Σ
4e w, (x, b (a,x))
Σ
Σ
ge w, (,, (a,
t=1
NE Σ
Σ
ge(x, w, a) (ERell,, (a x))x))
t=t+1
< + +
Σ
Σ
Σ
(18)
HE WEX
t=
N-1 (+1))
(x, (ER,lZ, ( )
S [I +
Σ
Σ a'EA
#E W
+11111111
(1+1)e at (2,W,,
('I =d') (19)
Σ
Σ
Σ
=EX
O'EA
1=1
34

---

(++1)
E
Σ
Σ
(x,
(20)
xEX aE
+
(+1))e
Σ
Σ
2t (t
Σ
v /maxf1 1,, Ne(a, w, a')3
=EXWER,EEA
a'EA
t=jé
2T 2 |
$ L| Vin
4e (t, (2,,
Σ
(21)
max (1, Ny w. a.)
DEX,EER,EEA
D'EA
S [[ V/nn
]
(y (I,W,,)))))
Σ
(22)
max 1, NI, w, (()
REX
a'EA
2T 2T(X11
< |1 V In
8
N
+ +LAA 2N In
a'EA
2T 2T
$ [X + 30 Im
8
Σ
Σ
(Neea,
+ LIAI 2
(23)
#EX
La'AA
2T (111111111111
< +| 33/A|| In
Σ
VNNele,Waa") + I
2N
WEX
2T 2
1
< [1X1]Q1/A|++33 + In
VLNE + LL 21
(24)
where we let (2, w. Eis; les(m (I, w, a) for the the sake of simplicity. Furthermore, we notice that Inequality 18 follows observing that Ex, a) S for each (a, w, a) E X A and I E [7), and because the occupancy defines probability distribution over each layer l (O..... L.]. Inequality (19) holds thanks to Inequality
(17). Inequality (20) follows because each indicator function takes value of at most one. Inequality 21 follows by observing that the number of times that the triplet (x, w, a') 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 (22) holds with probability at least 1 - and follows from the Azuma- Hoeffding inequality, and Inequality (24) holds, noticing that E N4 (x, a) < LNE and employing the Cauchy -chwhrZ inequality.
We focus on bounding the cumulative violations suffered in the remaining T Ne rounds of Algorithm 3 With probability at least 1 - 8 the following holds:
Σ
(e w. (), 6' (a, x))
35

---

E
ΣE gr (2, (1 ='}
a'EAtzNE
2T ||
In
Men (I
i>Ne V /max (1,,w,)))) a²)) (25)
=EX,EEDD
a'EA
</Al/ In
2T 2
Σ
1
N> V max Nxe(
zEXwEDD.EA
2T 2
(T-NN)
|4/ in
Σ
(I
max 1, NNe
ZEXWER
NNE(I, a) + LV 2n
(T - NC)
In |A|
(26)
max (1, NNel w)
De WEX
T N
1
SAIV In
VLNE+ + LE
2N In
(27)
2T II 5
S /2/A|1 In
Le
2 In
(28)
Inequality 25 holds thanks to Inequality (17 and observing that the indicator function takes value of
at most one. Inequality (27) holds, noticing that Σzex, a (z, w. a) S LNE and employing
the Cauchy-Schwaar incquality. Inequality (26) holds with probability at least - 8 and follows by employing the Azuma-Hoefiding and observing the following:
NN
Ie (x,
N
Σ k=
Ut (x, w 0) - 1/22N In
3
N ()) - In 8¹
which can be written as follows:
NNe(z, a) L
2N In
(x (I. (I, a).
N Finally, thanks Lemma 11 and employing Inequality and Inequality
27
we get:
Vr = (p (14 (A T
+IAVN +IAVN++ +
With p := [XX II (3/5), such result holds with probability of at least 1 1-98, employing a union bound and observing that (d) holds with probability of at least 1-48, Lemma [] holds with probability of at least 1 36, and both Inequality (24) and Inequality (2)) hold with probability of at least
E.3 Lower bound
Theorem 6. Given E 11,,,1), there is no learning algorithm achieving both Rr = o(T*) and V1 o(T1-"/2) with probability greater or equal to a fixed constant vb > 0.
Proof. We consider two instances with single possible outcome single state. In the following, omit the dependence the sender and receiver utility from these parameters. We assume that the
36

---

sender's utility in the first instance is deterministic function given by (3((1) = and r (a) 0. while the receiver's utility given by (1)(a)) ~ Be(1/2 + c) and r ( Be(1/2). Meanwhile, the sender's utility in the second instance is r (a1) = 1 and rg (a2) = 0, while the follower's utility (12 + 2c), for some 10, Thus, the
equal to (01)
Be(1/2 <) and r (a2)
sender's s regret in the first instance is given by:
T
R== Σ 0 (a2),
since the optimal signaling scheme is the one that always recommends action d1 A in the first instance. In the following, we define Pl (respectively. IP2) 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' N as follows:
Pp' ()) =P
Σ (as(
SC
21-7. n7
2
(29)
for some E 1). Furthermore, by Pinsker's inequality and Equation (2)
the following holds.
T
p2
Σ
o' (az)
sc 2 1- v DKL((FF) (PL P2),
(30)
where we denote with D L (1) the Kullback Kulbbec--Leiblrr divergence between two probability measure. By means of the well known divergence decomposition, we have:
(KL(PI, S E
(02) Σ
T
DKL (Be(1/2 2c). Be(1/2)) I 16
Σ (as) (31)
T
where in the latter inequality we used the well known property ensuring that ( Be(g)) S (p-q)² (1-0)-
Then, by reverse Markov inequality and Equation (29) we get:
T (a2) 2
E
Σ p'
(2))
Σ
Furthermore, by means of the latter inequality and Equation 31 have:
Σ (az) sc) 2 21 (162
p2
We now consider the receiver's violations in the second instance which be computed as follows:
2 (a1) (P2((2) (a))) = Σ (a1).
Then, by means of Equation 30 we get:
p2 V23
ET C)) 22
d'(a1) 2 ETT -0)
1=1
p2
T
④ (02) 2 2T-C
p
8' ('az) s0 21 1 (1660(11--))
Finally, by setting C = T
I and T-0/2 and 17 _ -- we get:
-n-1
P [R) < C) > 1-1
37

---

7
Ta-1
pa
R7
2
2
2
2
2'
since a E [1/2, 11. Then, the latter result implies that:
p2
V/3 2 32
1 T11-122
) 2 1p2
-1--
Ta-1
T
T
2
16
2
2
4'
which concludes the proof.
38


Reviews:
[{"review_id": "S2m2Ksk9uw", "reviewer": "Reviewer_JFBd", "summary": "The paper gives an interesting extension of the so called MPP (Markov Persuasion Process) by introducing the learning component. The paper considers the setting of MPP where both senders and receivers have no knowledge of the (implicit) \"markovian\" environment's transitions and rewards. The paper addresses non-trivial extensions to MPP with a novel solution (specially relating the occupancy measure to the MPP formulation).", "questions": "see weaknesses", "limitations": "Need discussions on: the practical utility of the MPP model; computational traceability of the proposed algorithms", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "S:\n\n1) Extremely well written with a clear model description, especially the first three sections.\n\n2) While the setting is still not practical in the current format, the MPP formulation definitely deserves a good consideration and analysis. Involving learning, this paper could give a reasonable first one.\n\n3) Occupancy measure and signaling policy equivalence is very insightful and may be useful independently.\nW:\n\n1)I learned about MPP while reading this submission. I do not follow what do the states of the MDP represent for any practical situation. Can the authors explain that? Further, what are some practical examples where MPP might be useful?\n\n2)Why is the assumption that a new receiver observes a_k at each time step important?\n\n3)In their model, the sender/principal commits to a signaling policy throughout the play. This seems to be very restrictive. Very reasonably, I would assume the signal policy is allowed to be adopted as new information is revealed.\n\n4)A minor comment: In RL terminology, partial feedback (as referred to by the authors) is called bandit feedback in most other papers. While the full feedback (as referred to by the authors) is still weaker (as rightly pointed out in the footnote). My suggestion would be to to call the full feedback as simply partial feedback\n\n5)In Lines 150-155, the authors argue for a direct and persuasive signal policy for a one-shot Bayesian persuasion framework. The argument is not clear. Further, the actual algorithm 2 does not play a persuasive policy. It is not clear what the structure of the sender's signals is with algorithm 2. What is the significance of playing a persuasive policy?\n\n6)The MDP structure of MPP induces a POMDP - Partially observable MDP. The authors should include this characterization as well.\n\n7)A lot of information is pushed to the appendix about Problem 2, as solved in Algorithm 2. A summary of the optimization program will be helpful. e.g., what does the objective look like, the main constraints? I am concerned about the computational traceability of the same. If it is tractable, what is the runtime? Further \"optimistic exploration\" is hidden in the objective of the optimization. Given the details of the main paper is hard to understand how the uncertainty quantification is being done by the use of optimism. Unfortunately, this is one of the biggest weaknesses of the paper.", "was_revised": true, "final_justification": "raised my score to 5\nI found this paper interesting; perhaps it can lead to multiple research directions in the future.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\nRe: *I learned about MPP while reading this submission. I do not follow what do the states of the MDP represent for any practical situation. Can the authors explain that? Further, what are some practical examples where MPP might be useful?*\n\nIn the following, we provide a simple illustrative example. Consider a product recommendation platform that suggests items to multiple users. In this setting, the platform acts as the sender, while the users are the receivers who select actions, such as clicking on or purchasing recommended products. The model distinguishes between two types of information: the outcome  ($\\omega$), which represents the sender’s private knowledge (e.g., product features and availability), and the state ($s$), which captures the dynamic environment (e.g., user browsing history). Outcomes are drawn from a prior distribution and are used by the platform to personalize its suggestions. The state evolves over time based on the user’s action, the previous state, and the realized outcome. Both the sender’s and the receivers’ utilities depend on the chosen action, the current state, and the realized outcome.\n    \nWe will surely include this discussion in the final version of the paper.\n\nRe: *\"Why is the assumption that a new receiver observes $a_k$ at each time step important?\"*\n\nWe thank the Reviewer for pointing out this aspect. In Bayesian persuasion problems, it is standard for the receiver to observe the action $a_k$, as this avoids tie-breaking issues among multiple optimal actions. (see, e.g., Kamenica and Gentzkow [2011]).\n    \nRe: *In their model, the sender/principal commits to a signaling policy throughout the play. This seems to be very restrictive. Very reasonably, I would assume the signal policy is allowed to be adopted as new information is revealed.*\n    \nWe thank the Reviewer for the question. We remark that, in episodic loop-free MDPs---and similarly in episodic loop-free MPPs---updating the policy within an episode does not provide any benefit. This is because the information acquired during the early steps of an episode cannot be leveraged to improve predictions for the later steps within the same episode. Instead, such information only becomes useful in the first steps of the next episode.\n\nRe: *A minor comment: In RL terminology, partial feedback (as referred to by the authors) is called bandit feedback in most other papers. While the full feedback (as referred to by the authors) is still weaker (as rightly pointed out in the footnote). My suggestion would be to to call the full feedback as simply partial feedback*\n    \nWe thank the Reviewer for the observation. We will better specify these aspects in the final version of the paper.\n    \nRe: *In Lines 150-155, the authors argue for a direct and persuasive signal policy for a one-shot Bayesian persuasion framework. The argument is not clear. Further, the actual algorithm 2 does not play a persuasive policy. It is not clear what the structure of the sender's signals is with algorithm 2. What is the significance of playing a persuasive policy?*\n    \nIn classical one-shot Bayesian persuasion, it can be shown that there is no loss of generality in restricting attention to signaling schemes in which the receiver is incentivized to follow the sender’s recommendation. These signaling schemes are called direct (the set of signals coincides with the set of actions) and persuasive (the receiver follows the recommended action).\n\nIn our setting, we have no prior knowledge about the receiver at the beginning of the interaction, so we must slightly relax the persuasiveness constraint. Since this relaxation leads to a broader set of signaling schemes, it remains possible to achieve the utility of an optimal persuasive and direct signaling scheme (see, e.g., Kamenica and Gentzkow [2011]).\n    \nRe: *The MDP structure of MPP induces a POMDP - Partially observable MDP. The authors should include this characterization as well.*\n\nThe Reviewer is correct: our setup introduces partial observability of the (persuasiveness) cost incurred by the sender. We will clarify this point more explicitly in the final version of the paper.\n\nRe: *A lot of information is pushed to the appendix about Problem 2, as solved in Algorithm 2. A summary of the optimization program will be helpful. e.g., what does the objective look like, the main constraints? I am concerned about the computational traceability of the same. If it is tractable, what is the runtime? Further \"optimistic exploration\" is hidden in the objective of the optimization. Given the details of the main paper is hard to understand how the uncertainty quantification is being done by the use of optimism. Unfortunately, this is one of the biggest weaknesses of the paper.\"*\n\nRegarding Problem 2, we agree with the Reviewer that much of the information is deferred to the appendix. Unfortunately, this is due to the space constraints of the NeurIPS format. In the final version of the paper, we commit to inserting the LP in the main part, due to the extra page available.\n\nThe optimization problem (Problem 2) solved at each round by our algorithm is a linear program with a number of variables and constraints polynomial in $|X|$, $|A|$, and $|\\Omega|$. As such, it can be solved in time polynomial in these parameters. The actual runtime depends on the specific LP solver used but remains polynomial in the overall input size."}, {"review_id": "2yH7JO0ycR", "reviewer": "Reviewer_kwa7", "summary": "This paper considers the problem of solving Markov Bayesian persuasion problems when the sender knows nothing about the game and proposes a learning algorithm that finds the solution with sublinear regret. Moreover, the authors show that the proposed bound is tight.", "questions": "Can the framework be extended to the case where the learning steps are limited, or where each step incurs a cost?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The problem studied in the paper is interesting and practical. No assumption is made about the sender's knowledge about the game. This significantly improve the applicability of the Markov Bayesian persuasion model. The paper is well-written and easy to follow. The proposed method is similar to the bandit algorithms where optimistic actions are taken. I like the idea of the exploration phase in the partial feedback case. Such a phase provides a good enough initial guess but affects the overall regret. The regret can be tuned by controlling the length of the phase. The tightness result is strong, though not surprising. \n\nOverall, I think this is a solid theory paper. The results could also open up new research opportunities for similar problems.", "was_revised": true, "final_justification": "I think the paper provides solid results, and the author response has answered my question in a satisfactory way.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\nRe: *\"Can the framework be extended to the case where the learning steps are limited, or where each step incurs a cost?\"*\n\nFor the limited steps case, our algorithm needs to know the time horizon in advance. Differently, the case where the learner incurs an additional cost during the learning dynamic can be addressed by employing standard techniques for constrained Markov decision processes (see, e.g., [1]), assuming that the cost depends on the state-action pair only. \n\n[1] \"Constrained Markov decision processes\", Altman (1999)"}, {"review_id": "3R5oLOTex6", "reviewer": "Reviewer_ocM5", "summary": "The paper considers the no-regret learning problem in Markov persuasion processes (MPPs), relaxing the assumption of previous work that the agent knows the receiver's utility function. It introduces the Optimistic Persuasive Policy Search (OPPS) algorithm, capable of learning the receiver's utility function from scratch, and provides rigorous regret bounds for the proposed algorithm under both full and partial feedback settings. The paper also provide a lower bound analysis on the optimality of the regret achieved by OPPS.", "questions": "Can the authors explicitly point out the improvement of their paper since the last version?\n\nOverall, I believe my technical questions about this paper have been answered again and again, and I have become overall satisfied with their answers, given that many problems cannot be meaningfully addressed under the current framework. I think the authors could have used some of their answers to acknowledge the limitations of this work.", "limitations": "No, though I see that there is no potential negative societal impact from this theory work, I think the authors could have better acknowledge the limitation of their modeling assumptions or technical results.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength \n\n- The authors consider the RL problem in MPPs, which is an interesting new problem from prior work. The analysis of this paper relies on the techniques of concentration measure, which offers a novel perspective to the studies of MPPs.\n\n- The overall writing of this paper is clear, and it is clear to me how their results can be derived from the technical lemmas and proof sketches outlined in the main body.\n\nWeakness\n\n- I have reviewed earlier versions of this paper at several different venues before. The outcome of this paper has been at the borderline for acceptance and I have not noticed any big change since then. I support the authors' decision for resubmission but I notice there's almost no additional effort made to improve the paper.\n\n- I am not sure if the limitations of this paper have been clearly acknowledged by the authors in Section 2.1 and 2.2.\n\n- The paper measures the learning performance with two quantities, total regret and total violation of persuasiveness. In contrast, [Wu et al. 2022] ensures persuasiveness in high probability and only considers the total regret. I can see the technical reasons behind this choice, but is there any practical motivation for this evaluation metric? Why would the receiver follow the persuasion if the recommendation is not completely incentive-compatible? Are receivers no-regret learners as well so they can tolerate \\sqrt{T} loss? Is it possible to convert any result of \\sqrt{T} in total regret and total violation of persuasiveness into an equivalent regret bound where the persuasiveness is guaranteed with high probability by introducing certain robustification/pessimism design to the signaling scheme? Without these explanations, I am not quite convinced that this learning result in MPPs is meaningful enough.", "was_revised": true, "final_justification": "I have reviewed this paper for several times in different venue. Its reviews were always around the borderline and I think the paper deserves a chance to be finally accepted.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\nRe: *\"Can the authors explicitly point out the improvement of their paper since the last version? Overall, I believe my technical questions about this paper have been answered again and again, and I have become overall satisfied with their answers, given that many problems cannot be meaningfully addressed under the current framework. I think the authors could have used some of their answers to acknowledge the limitations of this work.\"*\n\nCompared to the initial version of the paper, we have introduced a new lower bound for the full-feedback setting (Theorem 3) and improved the presentation in several areas, for example by highlighting that other works adopt similar assumptions and by adding Figure 1. While the questions raised by the Reviewer are surely interesting, addressing them would require a complete rethinking of our work, as also pointed out by the Reviewer. In summary:\n\n- Within our framework, it is provably not possible to be persuasive in the first rounds, since no information about the environment is available. This challenge has been addressed by other works in similar settings (see, e.g., [Bernasconi et al., 2022, Cacciamani et al., 2023, Gan et al., 2023]) by considering the total violation of persuasiveness, and thus we believe that this is a reasonable approach that deserves to be investigated in MPPs as well.\n\n- Addressing the case in which the receivers are no-regret learners would require completely different approaches, outside the scope of our paper. Nevertheless, we believe that following this research direction would surely be interesting in future works.\n\n- Finally, let us remark that, without sender’s knowledge of receivers’ utilities, introducing robustification/pessimism into signaling schemes is of no help, unless one completely changes our model by introducing additional assumptions.\n\nWe are committed to expanding the introduction in the final version of the paper to better clarify the limitations raised by the Reviewer."}, {"review_id": "EprHyuIkbR", "reviewer": "Reviewer_owP8", "summary": "The paper tackles Markov persuasion processes (MPP) where a sender interacts with a sequence of myopic receivers, where the sender must learn how to disclose information optimally without access to the environment’s dynamics or the preferences of he receivers. It proposes a learning algorithm for the sender for the case of partial feedback where the regret (w.r.t. an policy optimal of information disclosure) is sublinear w.r.t. the episodes and also the violations of the persuasiveness constraints remain sublinear. The paper also shows that the sublinear bounds it obtains in the analysis are tight.", "questions": "- Can the authors comment on practical applications of their setup and proposed algorithm?\n\n- Can the authors comment on the practical efficiency of their algorithm? Some, even if of small-size, computaitonal results would better emphasize the relevance of the work.\n\n- Can the authors comments on the numerics of their algorithm? I am asking about the many linear programming problems that the proposed algorithm solves. Are they well-conditioned or can there be cases (e.g, with small state spaces, symmetric transitions, or almost identical receivers) where the persuasiveness and occupancy constraints become very similar, leading to rank-deficient basis matrices?", "limitations": "Yes (there was nothing to report).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written and the relevance of its results clearly explained -- overall, the paper looks rather impressive when it comes to its results. Due to its technical nature, though, most of the paper's results are confined to the appendices,, and not much is done in the actual paper to summarize how the results of its many theorems have been obtained. The paper is also completely theoretical in nature, and lacks any empirical validation. As far as I can see, it's the first learning framework for MPPs where the sender does not know the transition dynamics, the priors, or the utility functions; as such, I think a bit of extra effort should be made in explaining in some detail what applications may benefit from this framework (some applications are mentioned, but only in a very abstract way). Also, if the motivations of the paper are not purely theoretical, some form of empirical validation (which is lacking) should be included.", "was_revised": true, "final_justification": "The authors provided sensible responses to my questions.", "rebuttal": "We thank the Reviewer for the positive evaluation of our work.\n\nRe: *\"Can the authors comment on practical applications of their setup and proposed algorithm?\"*\n\nIn the following, we provide a simple illustrative example. Consider a product recommendation platform that suggests items to multiple users. In this setting, the platform acts as the sender, while the users are the receivers who select actions, such as clicking on or purchasing recommended products. The model distinguishes between two types of information: the outcome ($\\omega$), which represents the sender’s private knowledge (e.g., product features and availability), and the state ($s$), which captures the dynamic environment (e.g., user browsing history). Outcomes are drawn from a prior distribution and are used by the platform to personalize its suggestions. The state evolves over time based on the user’s action, the previous state, and the realized outcome. Both the sender’s and the receivers’ utilities depend on the chosen action, the current state, and the realized outcome.\n    \nWe will surely include this discussion in the final version of the paper.\n\nRe: *Can the authors comment on the practical efficiency of their algorithm? Some, even if of small-size, computaitonal results would better emphasize the relevance of the work.*\n\nOur algorithm requires solving a linear program at each round $t \\in [T]$, with a number of variables and constraints that is polynomial in $|X|$, $|A|$, and $|\\Omega|$; thus, the per-round update can be solved in polynomial time and the running time depends on the employed solver. Current solvers can solve these kinds of problems efficiently. The main goal of this work is theoretical, but we leave as an interesting direction for future work the evaluation of our algorithms' performance in practice.\n\n\n\nRe: *\"Can the authors comments on the numerics of their algorithm? I am asking about the many linear programming problems that the proposed algorithm solves. Are they well-conditioned or can there be cases (e.g, with small state spaces, symmetric transitions, or almost identical receivers) where the persuasiveness and occupancy constraints become very similar, leading to rank-deficient basis matrices?\"*\n\nFrom a theoretical point of view, any linear program can be solved in polynomial time. Clearly, since our model is fully general, these kind of problems could occur. As we mentioned above, we leave to future works the study of more applicative-oriented settings where these kinds of questions have a clearer answer."}]

Author rebuttal:

Meta-review: The paper proposes a novel framework for Markov Persuasion Processes (MPPs) that incorporates a learning component, addressing the practical limitation of a sender having no prior knowledge of the environment's dynamics or receiver's preferences. The core contribution is the Optimistic Persuasive Policy Search (OPPS) algorithm, which achieves sublinear regret and persuasiveness violation guarantees. All reviewers were positive about the paper, acknowledging its well-written nature and the significant originality of the problem setting. The theoretical results, including the tight regret bounds and the insightful equivalence between occupancy measures and signaling policies, were highlighted as major strengths. The authors provided clear and satisfactory rebuttals to all questions, addressing concerns about the practical utility of the MPP model, the restrictiveness of a committed signaling policy, and the computational tractability of the optimization problems. The reviewers' final comments confirmed that their initial questions were fully resolved, with all maintaining or raising their scores to a positive recommendation for acceptance.
Decision: Accept (poster)