Persuading Farsighted Receivers in MDPs: the Power of Honesty
Authors: Martino Bernasconi
Matteo Castiglioni
Alberto Marchesi
Mirco Mutti
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian Persuasion
MPD
information design
signaling

Abstract: Bayesian persuasion studies the problem faced by an informed sender who strategically discloses information to influence the behavior of an uninformed receiver. Recently, a growing attention has been devoted to settings where the sender and the receiver interact sequentially, in which the receiver's decision-making problem is usually modeled as a Markov decision process (MDP). However, the literature focuses on computing optimal information-revelation policies (a.k.a. signaling schemes) under the restrictive assumption that the receiver acts myopically, selecting actions to maximize the one-step utility and disregarding future rewards. This is justified by the fact that, when the receiver is farsighted and thus considers future rewards, finding an optimal Markovian signaling scheme is NP-hard. In this paper, we show that Markovian signaling schemes do not constitute the "right" class of policies. Indeed, differently from most of the MDPs settings, we show that Markovian signaling schemes are not optimal, and general history-dependent signaling schemes should be considered. Moreover, we also show that history-dependent signaling schemes circumvent the negative complexity results affecting Markovian signaling schemes. Formally, we design an algorithm that computes an optimal and $\epsilon$-persuasive history-dependent signaling scheme in time polynomial in ${1}/{\epsilon}$ and in the instance size. The crucial challenge is that general history-dependent signaling schemes cannot be represented in polynomial space. Nevertheless, we introduce a convenient subclass of history-dependent signaling schemes, called promise-form, which are as powerful as general history-dependent ones and efficiently representable. Intuitively, promise-form signaling schemes compactly encode histories in the form of honest promises on future receiver's rewards.

Persuading Farsighted Receivers in MDPs: the Power of Honesty
Martino Bernasconi"
Matteo Castiglioni Politecnico di Milano
Bocconi University
martino. bernasconi Qunibocconi.
matteo. castiglioni eeliooonippiiiiimi ampliii.....
Alberto Marchesi
Mirco Mutti
Politecnico di Milano
Technion atrco.m@teehnion.acc
alberto. mawchesi@polimi........
Abstract
Bayesian persuasion studies the problem faced by informed sender who strate- gically discloses information to influence the behavior of an uninformed receiver. Recently, growing attention has been devoted to settings where the sender and the receiver interact sequentially, in which the receiver's decision-making problem is usually modeled as Markov decision process (MDP). However, previous works focused on computing optimal infornation--evelattor policies (a.k.a. signaling schemes) under the restrictive assumption that the receiver acts myopically, select- ing actions to maximize the one-step reward and disregarding future rewards. This is justified by the fact that, when the receiver is farsighted and thus considers future rewards, finding an optimal Markovian signaling scheme is NP-hard. In this paper, we show that Markovian signaling schemes do not constitute the "right" class of policies. Indeed, differently from most of the MDPs settings, we prove that Marko- vian signaling schemes are not optimal, and general history-dependent signaling schemes should be considered. Moreover, we also show that history-dependent signaling schemes circumvent the negative complexity results affecting Markovian signaling schemes. Formally, design algorithm that computes optimal and e-persuasive hustory-deeendent signaling scheme in time polynomial in 1/e and in the instance size. The erucial challenge is that general dependent signaling schemes cannot be represented polynomial space. Nevertheless, we introduce convenient subclass of history- dependent signaling schemes, called promise-form, which are as powerful as general history-dependent ones and ef- ficiently representable. Intuitively, promise-form signaling schemes compactly encode histories in the form of honest promises on future receiver's rewards.
1 Introduction
Bayesian persuasion [Kamenica and Gentzkow] 2011] is the problem faced by an informed sender who wants to influence the behavior of an uninformed, self-interested receiver through the provision of payoff relevant information. Bayesian persuasion captures many fundamental problems arising in real-world applications, e.g., online advertising (Bro Miltersen and Sheffet 2012). voting [Alonso and
Câmara 2016, Castiglioni et al., 2020a Castiglioni and Gatti] [2021], traffic routing [Bhaskar et al.
2016 Castiglioni et al. [22 recommendation systems MMnsour et al. 2016), security RRaiiovvihh
ct al. 2015 Xu et al. 2016 marketing [Babichenko and Barman 2017 Candogan 2019), medical
research Kolotilin 2015 and financial regulation [Golsstein and Leitner 2018
"Work done while the author was at Politecnico Milano.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Most of the previous works study the classical, one-shot version of the Bayesian persuasion problem. However, in many application scenarios it is natural to assume that the sender and the receiver interact multiple times in a sequential manner. In spite of this, only few very recent works addressed sequential versions of the Bayesian persuasion problem [Wu et al. [022 [errnasconi et al. 2022] Gan et al. 2022a bj. In particular, [Wu et al. [2022] and Gan et al. [202a b) study settings where the sender and the receiver interact sequentially in a Markov decision process (MDP).
In Bayesian persuasion problems in MDPs, at each step of the interaction both the sender and the receiver know the current state of the MDP, and the former has also access to some private observation drawn according to a commonly- -onoooooll-oo,,,,,o- known, state-dependent distribution. The sender commits beforehand to an citormation-rvvllattii randomized action recommendations to the receiver, conditioned on the current (public) state and the sender's 's private observation. Specifically, the sender commits to a persuasive signaling scheme, meaning that the receiver is always incentivized to follow recommendations. At the end of each step, the next state of the MDP and the agents' rewards are determined as function of the current state, the action actually played by the receiver, and the sender's private observation in the current step.
policy, which implemented by means of a signaling scheme that sends
Wu et al. 2022 and Gan et al. 2022a b provide algorithms that compute an optimal (i.e., reward- maximizing) persuasive signaling scheme under the restrictive assumption that the receiver acts myopically, selecting actions to maximize the one-step reward and disregarding future ones. This is justified by the fact that, when the receiver is farsighted and thus considers future rewards, finding an optimal Markovian signaling scheme NP-hard to approximate, as shown by Gan et al. [2022a] for infinit-hhorizn MDPs. An analogous result also holds in finite-horizon MDPs for non-stationary Markovian signaling schemes, as we prove in this work as a preliminary result.
In this paper, we show that Wu et al. [2022) and Gan et al. 2022a b) failed to provide positive results with farsighted receivers since Markovian signaling schemes do not constitute the "right" class of policies to consider. This is in stark contrast with most of the MDPs settings in which Markovian policies are optimal. Indeed, we prove that Markovian signaling schemes are nof optimal, and general signaling schemes should be considered. As a result, we focus on the problem of computing an optimal persuasive distory-dependen signaling scheme. Surprisingly, we show that taking history into account allows to circumvent the negative result affecting Markovian signaling schemes. We do that by providing an approximation scheme that finds an optimal c- e-persuasive (i.e., one approximately incentivizing the receiver to follow action recommendations) history-dependent signaling scheme in time polynomial in 1/c and the size of the problem instance.
The crucial challenge in designing our approximation scheme is that general, history- -eeendt signaling schemes cannot be represented in polynomial space. Our algorithm overcomes such an issue by using a convenient subclass of history-dependent signaling schemes, which we call promise-form signaling schemes. The core idea of such signaling schemes is to compactly encode all the relevant information contained in an history into promise on future receiver's rewards. At each step of the process, a promise-form signaling scheme does not only determines an action recommendation for the receiver, but it also makes promise to them. First, we prove that promise-form signaling schemes are as powerful as general history-dependen ones. Then, we show how an optimal c- c-persuasive promise- form signaling scheme can be computed in polynomial time by means of a recursive procedure. To do that, we rely on a crucial result showing that, for signaling schemes that honestly keep promises made to the receiver, persuasiveness constraints can be expressed as conditions defined locally at each step of the MDP, since the receiver only cares about sender's promises on their future rewards
2 Preliminaries
In this work, study Bayesian persuasion problems where a farsighted receiver takes actions in time-inhomen meeeiihhooggeeuus fini finite- horizon MDP [Puterman| 2014]. Formally, a problem instance is a tuple
(s. 7,, O, (1S (r. R1 hee, {ps hem., {pm (pnhee..8). where:
is a finite set of states, AA is a finite set of receiver's actions available in each state, H= == [1...., H] is a set of time steps with H being the time horizon, θ is finite set of sender's private observations, T r S x A x e + j0, 1] are reward functions for the sender and the receiver, respectively,
'Th complete proofs of all the results in the paper can be found in Appendices C and E

---

Ph : S Ax A(S) is a transition function, AA : : - A()) is a function defining probabilities of sender's private observations at each state, while 3 E (S) is the initial state distribution
We consider the most general setting in which the sender commits to a non-stationary and non- Markovian signaling scheme (henceforth called history-dependent signaling scheme for short). For every step h E H. and state Sn E S reached at that step, a distory-dependeen signaling scheme defines a randomized mapping from sender's private observations action recommendations for the receiver, based on the whole history of states and receiver's s actions observed up to step / Formally, in the following we let Th be the set of all the possible histories up to step h, which defined as
To = (T |T T== (81, (
ah-1 sn) : 8; E ES, 04 E A},
while we let T := TI...... TT....TT be the set of all the possible histories (of any length Then, a history-dependent signaling scheme is defined which define a mapping from sender's ' private observations to probability distributions over action recommendations for every possible history.
set == ( JoET of functions 0, θ (AA),
Algorithm 1 Sender-receiver interaction
The interaction between the sender and the re- ceiver goes as follows (Algorithm [. (i) The sender publicly commits to a history-dependent signaling scheme o= == {or) (TTT (ii) An initial state ~ / is drawn. (iii) At each step h E H. both agents observe the current state 8n S and the sender also gets a private observation On E o drawn according to pi (s)), with the function μl, being known to both the sender and the receiver. (iv) The sender communicates to the receiver an action recommendation an E AA sampled according to or (0n). where Th E Th
1: Sender publicly commits to Φ : (er
2: 81 ~ 3. T1 + (s1), devioted +- False
3: for each step h = -..... H do
4: Sender observes 0₁, (4,
5: if deviated is False then
6:
Sender recommends ag pr. (0%) Receiver plays ū₁ E A else
7:
8:
9:
Receiver plays ōn E
10:
Sender collects reward r an, On)
11:
Receiver collects reward r (A ar. 0%) Next state: 8h+1 ~ (s,, Cn, 0p) Update history: Th+1 Th @ (āp, sh+1)
is the history up to step h. (v) The receiver
12:
plays an action ūn E A. possibly different from
13:
ag. (vi) The sender and the receiver get rewards
14:
if aa # ān then
R 8h, On, 0n) and (*h, an, 0n), respectively.
15:
deviated <- True
(vii) If h = H, the interaction ends, otherwise
the next state $1+1 ~ (sh, ān, 0n) is drawn and the interaction continues to step h + 1 starting from the third point. As customary in the literature (sce, e.g., [Bernasconi et al. (022)) ). we assume that, if the receiver does not follow recommendations at some step h E H by playing an action ag # on, then the sender stops issuing future recommendations to the receiver.
For case of presentation, we introduce the sender's value function V T + R to encode sender's expected rewards by using a history-dependent signaling scheme ó := ( from step h E H onwards, assuming the receiver always follows recommendations. Given history ) E Th up to step h, such a value function is recursively defined as:
T = ($1, ($1,01,...,. 8h-1, 1, 8h)
h (T)
Σ Σ pr, (1)ss)))) REA
(a Sh. 0) + Σ
a, 0)V (
@ (a, (a.5"))
e'ES
Similarly, we introduce the receiver's action-value function V. A Th - IR to encode the receiver's expected rewards by following sender's action recommendations from step h E H onwards. Formally, given a history 7 = (81, .., -h-1, O1-1, $h.) E Th up to step h, the receiver's expected reward by following the recommendation to play a E A is recursively defined as follows:
R.0 (a, = Σ un (0)sn))) GEB
7R 8h,
5h, 0) + Σ En a, (, ( ( S'ES
'In this paper, let A(X) be the set of all the prohability distributions over finite X, with d(x)) denoting the probability assigned to E by a distribution di E ((X). Moreover, given function f - A(Y) with X, Y any two finite sets, for every æ E X we denote by [u](=) the probability that f(x assigns to y E Y. direct signaling schemes which send signals in the form of action recommendations for
'In this work, the receiver. This is w.l.o.g. by well-known revelation principle arguments [Kamenica and Gentzkow 2011].
By simple revelation priniippi-nisnnieeee style argument, we can focus w.Lo.g. signaling schemes which depend on histories that do not include the sequence of private observations observed by the sender.
3

---

where VR Th - IR is such that (T) = EF)=A (a. for every h E H. and T E Th.
Finally, we introduce an additional receiver's value function, denoted by VR S + R. to encode receiver's expected rewards from step h E H onwards after having deviated from recommendations. Formally, for every state E S, such value function is recursively defined as follows:
(s)
(rR(a, s, + En((s'ls, (1) Σ En((B)s) BEE
max aEA
''ES
where the maximum operator encodes the fact that the receiver plays as to maximize future rewards without knowledge of realized sender's private observations after having deviated
By the revelation principle (Kamenica and Gentzkow 2011 it is well known that in order to find an optimal signaling scheme it is possible to focus w.l.o.g. on (direct) history-dependent signaling schemes under which the receiver is always incentivized to follow sender's 's action recommendations. These are called persuasive signaling scheme, and they are formally defined as follows:
Definition (c- (--persuasivenes)). Let 2 O. A history-dependent signaling scheme @ == [(0 ET is said to be e-persuasive if. for every step h E H. history T = ($1, 01,...; 8h-1, (1) E Th. up to step h, and pair of actions a, d' E A. the following holds:
( (r)(sn, d', + Emi(s' sh, d' (d 1) -
v (a. T) E (0 (n)(0)s))0
-c)
BEE
s'eS
Moreover, we say that the signaling scheme is persuasive if the conditions above hold for O. We denote the set of all the persuasive signaling schemes by +.
Whenever the sender commits to an e-persuasive history-dependent signaling scheme, we assume that the receiver always follows the recommendation issued by the sender. Notably, the recommended action is guaranteed provide the receiver expected rewards that at worst e less than those attained by the best possible action.
In conclusion, the goal is to find an optimal signaling scheme for the sender, which is one achieving sender's 's expected reward (from step one) / greater than or equal to OPT, defined as follows:
OPT := max VS.. PE
where we let VS := Σ
B ((s)).
SES
3 History-dependent signaling schemes are necessary
Previous works studying Bayesian persuasion in MDPs [u et al. 2022. Gan et al. 2022a] focus on Markovian signaling schemes, in which the action recommendation at step h only depends on the current state 84 and private observation 0/. Indeed, considering this class of signaling schemes is sufficient to optimize the utility of sender facing a myopic receiver. Here, we show that this is not the case when the receiver is farsighted. In particular, we show that non-stationary Markovian signaling scheme are suboptimal. To do so, we show that there exists an MDP (see Appendix A in which the optimal persuasive signaling scheme is history-dependens signaling scheme can adjust action recommendations depending on the choices available to the receiver in previous steps. Thus, if the receiver had profitable opportunities in the past, the sender must provide larger expected reward to the receiver in order to be persuasive. Otherwise, the sender can aggressively maximize their expected rewards irrespective of receiver's ones. Formally:
Intuitively, an history -eeendet
Theorem 1. There exist instances in which a persuasive history-dependent signaling scheme guar- antees sender's expected rewards strictly greater than that obtained by an optimal persuasive non-stationary Markovian signaling scheme.
Notice that, in all the steps reached after having deviated from recommendations, the receiver does not get any clue about the sender's private information, and, thus, their expected reward only depends on the current state (not on the history). In other words, after deviating the receiver playing new MDP in which, by taking expectations with respect to μ4s, rewards and transition probabilities are defined as Fr a) = Eeco pa ( 0) and pn (s') sss a) Eece M4 (0) s) (s') a, f), respectively, for all E H. E S, a E A, and s' S.
We defer to Appendix the complete description of the instance, together with calculations of the optimal signaling schemes (for each class) and their corresponding value functions.

---

Moreover, we show that optimal non-stationary Markovian signaling schemes are NP-hard to ap- proximate in polynomial time, even when the persuasiveness requirement is relaxed. This further motivates the use of detteryddependent signaling schemes when addressing Bayesian persuasion problems finite-horizon MDPs with a farsighted receiver. Formally, we prove the following:
Theorem 2. There exist two constants a < and > 0 such that computing an e-persuasive non-stationary Markovian signaling that provides the sender with at least a fraction a of the optimal sender's ss expected reward OPT is NP-hard.
4 A sufficient subclass of efficienty-representtbee signaling schemes
Working with history-dependent signaling schemes begets unavoidable computational issues. These are due to the fact that explicitly representing such signaling schemes requires a number of bits growing exponentially in the size of the problem instance, since the number of possible histories is exponential in the time horizon H. In this section, we show how to circumvent such an issue by introducing a convenient subclass of signaling achemes-calles promise- signaling schemes- which are efficiently representable while being as good as history-dependent ones. In particular, main result in this section (Theorem 3) shows that there always exists promise-form signaling scheme which results in sender's 's expected rewards equal to its optimal value OPT.
4.1 Promise-form signaling schemes
A promise-form signaling scheme is defined by a set a == {(h,, Ph gi) of triplets, where:
In - a function defining, for every state s E S, a finite set In S [0, of promises for step h E H. We add the additional requirement that 0 E (s) for all 8 E S, and, for ease of notation, we set + (s) == {0} for every E S and = UnEn UXES (x).
Ph : S I x θ + A (AA) is an action-recommmedattton strategy be employed at step H. where [a]s,, , i, () is the probability of recommending action E AA in state E S when the promise is E (s) and the sender's private observation is O.
yn. S x A I + I is a promise function for step h E H such that, whenever h S H and i E (s). (s, a, s'),'') E In+1(s') represents the promise for step h + 1 if the next state is s' E S and, at the current step h. action a E A is recommended in state s
Intuitively, the rationale behind promise-fone form signaling schemes is that, when reaching state sy E S at step h E H. the sender "promises" a value E J (sn) to the receiver, representing a lower bound on future rewards obtained by following recommendations. Moreover, sender's action recommendations only depend on the current state 8h. E S, the sender's private observation 0, E O, and the current promise Ia (s)). through the distribution (a 4h, 0x). Notice that is always possible to infer the current promise by looking at the history of past states and action recommendations, by "composing" the functions gh for the steps h' < h. This crucially avoids having specify an explicit dependency on the full history of past states and action recommendations.
Notice that a promise-form signaling scheme as defined above does automatically guarantee that the sender honestly keeps their promises. Indeed, in order to ensure that this the case, we need to enforce additional constraints the components of the signaling scheme,
show in Section 4.3
Let us remark that representing promise- form signaling schemes requires number of bits polynomial in the size of the problem instance and in [Z], which is the cardinality of the set of promises. While [z] could be arbitrarily large in general, the algorithm that we will present in the following Section guarantees that [Z] has "small" size, by means of a clever choice of the functions Lp.
4.2 From promise-form to history-dependent signaling schemes
In the following, show how the sender can implement promise-form signaling schemes, proving that they represent a subclass of history-dependent ones.
'Notiee that, in order to completely specify promise-for form signaling scheme := ((1,, pa,, 9b)) Jiew it sufficient to specify the functions you and gb. since the functions 4), can always be inferred by looking at the images of the functions gr. However, we included 4,, in the definition of promise-form signaling schemes since this will considerably ease notation when dealing with them in Sections 5 and
5

---

The sender can implement a promise-form signaling scheme o := {(In, 9h. 9h) hew as follows. After committing to (Line Algorithm| D. at each step h E H. in Line Line Algorithm[|] they select which action-recommendation strategy to use by reconstructing the current promise on the basis of the history Th- Such reconstruction done by recursively "composing" functions gh- for the preceding steps h' < h, by means of the procedure in Algorithm 2wth a and тh as inputs. By letting c E Is (sn. be the continuation value obtained by running Algorithm 2 the action recommendation an in Line i then sampled from yP (sh, 0²). ). Algorithm 2 clearly runs in time polynomial in the instance size, and, thus, the sender can implement a promise-fone signaling scheme efficiently.
In the rest of this section, given a promise-form sig- naling scheme o := {(I,. iph. 9h JiE we denote signaling
Algorithm From histories to promises
by o := [ the scheme induced by a thorough the implementation procedure described above. Formally, for every his-
Require: a == {(h, ihh 9b) (1)))Re nEH.
T == (81, a1........... 8/-1 0/-1- 8%) E Th 1: Initialize 1 + 0 E (51)
tory r (81, 01 ai,..... 8h-1, O/-1, 1, 8h)) E Th up to step h E H. the function of θ + (A4) is defined
2: for each step h = I...., h- do
3: k (sw, aN, 4, 5K+1)
so that of (0) = ( c7 0) for every 0 E O, where E E In (sa) denotes the promise value correspond-
4: return
ing to history т, as computed by Algorithm@ 2 with a and r as inputs. As it is easy to see, implementing the promise-form signaling scheme as described above is equivalent to using o in Algorithm []
Next, we show that the value functions of the sender and the receiver associated with the induced history-dependent signaling scheme d can be efficiently computed by only accessing the components of the promise-form signaling scheme o. In the following, given any a == {(Tn, fh. 9h neH for
every step l E H we introduce the functions DR. A x S x I + R and RR : S x I - I. which are jointly recursively defined so that, for every a E A. E and E (8), it holds:
vr. (1, = Σ
(al DER
A Th (s 0) + Σ pn sss a, 0) (5', (,
''ES
and (8, VR. s.) Similarly, VSS SSII + I is such that, for S, E [s):
(s, V SSS
-E pn (0())))p 0) S ()) aEA
Σ x'ES
pn a, 0 (5', (ss,n((s,,,,,,))))
Then, we can prove the following lemma:
Lemma 1. Given a promise- signaling scheme == [II,, Phi 9h) ( her, for every h E H and
history= T = (81, 01, ai,..., 8p-1. 0h-1, 8%) E TT, up to step h, the following holds:
Vir R.6 (a, 1/R (h.8).)))
Via R. (7) = v (sh: 4) and v.S. V.8. (7) - 1/ (sh:
Intuitively, Lemma establishes that the functions v V and S "correctly" encode the value functions of the sender and the receiver for a promise- form signaling scheme or, when it is implemented according to the procedure described at the beginning of the section.
Finally, given how promise-form signaling scheme a is implemented, in the following we say that is c-persuasive (for some e 2 0) if the induced history-dependent signaling scheme d" is c-persuasive according Definition [ However, using such a definition to check whether a is e-persuasive is clearly computationally inefficient, since it would require working with exponentially-many histories. In Section 4.3 we introduce an easy way to ensure that a promise-form signaling scheme "keeps its promises". and we show that this allows to encode e-persuasiveness constraints in an efficient way.
4.3 The power of honesty
Next, we introduce a particular class of promise-form signaling schemes which always guarantee that the sender honestly (approximately) assures promised rewards to the receiver. We call no-oesst the fromise-form signaling schemes with such a property, which are formally defined as follows:
Definition 2 (vy-honesty). Let 1) 2 O. A promise-form signaling scheme a == {(Tn Phs gh) mn))ee is vy-honest for every step h E H. state s E S, and promise E Is()), the following holds:
ΣΣ (0 AE
(f(ss,,,) 0) + Σ (n(''Is, a, 0) () (3)),)1)))) 26-1) (1)
a'ES

---

Then, we can prove the following result on 17-hnesst promise promise-form signaling schemes:
Lemma 2. Let a == {1h, ihhs 9h) ) heu be a promise-form signaling scheme. If is n-honest, then, for every step h E H and state E S, it holds that R. (s,t) 2 n - h + 1) for all E [s).
Since by Lemma 1 the function y encodes the receiver's value function when is implemented by the sender, Lemma inttuitively establishes that, at each step h E H and state E S, the signaling scheme actually "keeps the promise" of giving at least I (8) future rewards to the receiver, up an error depending on 17. Checking whether a promise-form signaling scheme Ø := {(In, Pho 9h) hen 17-honest or not can be done in time polynomial in the instance size and [
Now, we are ready to prove the following crucial lemma:
Lemma 3. Let a = {(I,, Ph. gh) hEN be an n-honest promise-form signaling scheme such that, for every h E H. s S. L. (s),,, and a. E A. the following constraint is satisfied:
Σ
pn (m((0s)pn(a(sssc lE
(R + Σ
s'ES
Σ D
_ma(0ssppnaabssc.
r 0) [p s'ES
(2)
Then, we can conclude that a is ( persuasive.
Intuitively, Lemma 3 states that for an n--hoest promise-form signaling scheme, the constraint in Equation (2) is equivalent to the one in Definition [ The crucial advantage of Equation ( is that it allows to express persuasiveness conditions as "local" constraints which do nor require recursion.
4.4 Promise-form signaling schemes are sufficient
Finally, by exploiting Lemma 3 we can prove the main result of this section: promise-form signaling schemes represent sufficient subclass of history-dependen ones. Formally:
Theorem 3. There is always persuasive promise-fome signaling scheme a := {(In, (Ph, 9h.) thn
with sender's 's expected reward equal to OPT. More formally, it holds that VS,a" = OPT for the history-dependent signaling scheme d² induced by a.
5 Approximation scheme
Theorem 3 shows that, in order to find an optimal signaling scheme, one can focus on promise-form signaling schemes that have the nice property of being polynomially representable in the instance size and the cardinality [Z] of the set of promises. In this section, we show how to compute an c-persuasive promise-form signaling scheme with sender's expected rewards at least OPT in polynomial time.
We design an algorithm working with sets (s) defined on a suitable grid, whose size can be properly controlled by discretization step d. The algorithm solves recursively-definel optimization problem for each h E H. E S, and & In (s), by starting from step H and proceeding in bottom up fashion.
For every step h E H and state E S, the set (s) of promises is defined as a suitable subset of grid D3 = (k 8 & E NAk < [#/b],, where ô >> 0 a discretization step to be set depending on the desired relaxation of the persuasiveness constraints. This also allows us control the representation size of promise-fom form signaling schemes, as well as the running time of the algorithm. In particular, it holds |D;| = O(1/8) and, thus, [ O(1/5) since I C Dj by definition. In the following, for ease of notation, we let [x]s == minken: kō be the smallest multiple of ō greater than x, while [x]s- max kd is the greatest multiple of 5 smaller than x.
The algorithm keeps track of recursively-compune
values in a set of tables, one for each step. The table at step h H. is encoded by means of function M, S D; - R RURR (-oo). Intuitively, for every E S and E Ds. the entry M i) is related to the expected rewards achieved by the sender when "promising" the receiver expected rewards "approximately equal" to in state s at step h. We also admit the functions MÅ to take value -oo which semantically corresponds to the case in which it is impossible to guarantee the promise to the receiver in state at step h. The entry M c) of
7

---

the table ME at step h is computed recursively by solving problem Ph.s, (MM that we define in the following, where M is the (previously-computed) table at step h 1.
By letting M SS x Dj + R {- be a function encoding a generic table over S x Do. for every step H. state s E S, and promise & (s), we define the value (MM) of the optimization problem Ph,sa (M) as follows:
(M)
max as (K,9) s.t. (x, Vh x(A))(A)
y.AxS=Da
where problem variables are encoded by the functions K. θ - ((A) and q : A S Ds, which represent an oetion-recommendatiie strategy and promise function, respectively 9 function FM as (x. q) of the optimization problem is defined as:
The objective
Fr (He, 9)
EE (n((s))((a()) aEA
(s, + Emnss'ss a, ()M((s a(a.5))) K'ES
which encodes the sender's expected reward when their values for the next step h + are those specified by the table M. We assume that 0 (-20) = -o. Moreover, the set wh is comprised of Ax
the functions K. : O - (AA) and A S > Da that satisfy the following constraints:
EE
aEA (n(0)s)x(a10) (+((s,a,0)+
Σ Epn(s'ss,,00)aaa 26
(4a)
N'ES
E (m(0))))((a1)) () Ipiis/ls, Aee
s'ES
(m(01s))(((o) 0)) Epi(s'ss, 0) (
Va, E A,
(4b)
$EES
where Equation 4ab and Equation (4b) play the role of the honesty and the persuasiveness constraints, respectively. Notice that relaxing the honesty constraint yields larger feasible sets. Formally, for any i .26 /' 2 0 we have that the following holds: V.A. C V/.
If (M. 9) = -oo for all (xx, 9) The we have that IT (M) cc. This intuitively comes from the fact that, if ll,.,..M) oo, then the value promised to the receiver is not realizable.
The optimization problem (M) could be easily cast mixed-integer quadratic program, which are too general to be solved efficiently. Thus, we need apecifically-tailorte procedures to find an approximate solution to it. This discussion is deferred to Section 66| In the following, we assume to have access to an oracle On.e. (M) that provides a suitable approximate solution to (M.),c(M).. In particular, (M.),(M) must satisfy the requirements introduced by the following definition:
Definition (Approximate Oracle). An algorithm Oh,s, is an approximate oracle for Ph, (M) if it returns tuple (1s, q, v) such that [l,.s.(M) S u S Fh, (N. q) and (x. q) wh
hhe Intuitively, we ask that an approximate oracle finds solution (s, in a slightly larger set (-8- The oracle also returns a value v to be inserted into Mf t), where is possibly different from the value Fr.s.M (K, 4) of the objective function. This is needed for technical reasons in order to recover some concavity properties of the functions defining the tables used by the algorithm, which may be lost due to approximations. A complete discussion on this last aspect can be found in Section 6
Equipped with an approximate oracle in Definition 3 we are ready to design approximation scheme that computes an e-persuasive promise-form signaling scheme attaining sender's 's expected reward at least OPT (Algorithm 3). The algorithm iteratively builds each table Mg by filling it with strategies {(J,, Ph; 9h) hee be equal to the
the values u returned by the approximate oracle. Moreover, it sets octioonrecommmndatte 9hi and promise functions Jh. of the signaling scheme functions k, returned by the approximate oracle.
"The optimization problem over functions and q can be rewritten as equivalent program with tabular variables, since the functions and q map discrete sets to discrete sets (or randomization over them).

---

In order to clarify the semantic of the tables Mg built by AlgorithmB] we prove the following pre- liminary result, which states that the sender's s ex- pected rewards for the signaling scheme returned by Algorithm @goorthmm/oonstiuggg constitut an upper bound on the entries of the tables Mr. Formally:
Algorithm 3 Approximation scheme
Require: 8 E (0, 1)
1: M #++1 (s, <- 0 for all E ES
M MH+1 (8,6) +- 00 for E S, E Ds
3:
for h = H. ......14 do
Lemma 4. Let a == (1h, 9h. gh) be re- turned by Algorithm 3 instantiated with any oracle
4:
for 8 E do
5:
In(*) (0)
Oh,s, as in Definition 3 For every h E H. 8 E S,S & E (s), it holds that V.h (s, 2 (s.
6:
for E do
7:
(k,q, + (
Mg(s, + v
Moreover, the entries of the tables Mn built by Algorithm 3 are upper bounds on the sender's ex- pected rewards provided by an optimal promise-
9:
ph(als,4,0 0) + k(al0)
10:
g,(s,a,4,5)) + q(a,s')
11:
if> -00 then [s(s) (t)
form signaling scheme. Formally:
12:
13: return o := {(In, Ph. (h. 9h)
Lemma 5. Let My. In (for h E H) be computed by Algorithm 3 instantiated with any orucle On.aa
as in Definition 3 and let o² = {Tix Phi 9h) neH be an optimal promise-form signaling scheme. For every h E H. E S, and i (s). it holds that [c]ss E In(s) and M9 (s, [c]s) 2 S.."" (s, 1).
By combining Lemma and and Lemma 4 we can promptly state and prove the main result of this section.
Theorem 4. For any c > O, given an approximate oracle as in Definition 3 Algorithm B Binstantiated with 5 = +/2H runs in time polynomial in 1/E and the instance size, while it finds e-persuasive promise-form signaling scheme that guarantees expected reward at least OPT to the sender.
Building a polynomial-time approximate oracle
In the previous section, we described an approxima- tion scheme (Algorithm 3 that works provided it has access to an oracle that approximately solves the problem Pr.e& (M) while satisfying the requirements of Definition 3 In this section, we exploit the spe- eific structure of the problem to design an algorithm implementing such an oracle.
Algorithm 4 Approximate oracle
Require: d E (0, 1), h E H. s E S. E Ds.
M : S x D3 + R
1:
if R (M) is feasible then
2:
(k, 9) + Solution to (M)
V + FN, 7)
4:
q + LÑ
First, we relax the problem (M) into (M), which optimizes the expected value of the sender's rewards over randomizations of promises c EE Dz. Moreover, we define for all s' E S the set Ds(s', M) { E Ds : ( .1) > - as the set of realizable promises, which semantically means that those promises can be realized, conditioned on what is stored in the table M the variables of (.....(M)) are encoded by a function i. : θ -> A(A) and randomized function q: S x - ADss). The objective function is
else
6:
(x, arbitrary
V' 7 00
return (k,,
10 Specifically,
ΣΣ DEA
(O)ss)(((())) (FE(5, 0)+
Σ pn(s'Is,a, 0) Σ q(''la, (l(l,,)))M((''' N'ES
d'EDs(s'
which modifies the objective function FR. (K, q) of (M. by introducing the expectation over the possible promises o' E Ds, which are randomized through q((" s').
To simplify notation, for any set X, table M, and randomized function A : X'x + A(Ds), we denote by Ag X x - cD( quantity related to its average, where co denotes the convex hull of a set. Formally, \z( = EVEDA(S .M) L' >(<'Iz)) for all x E X. Moreover, we denote by Dee : X - D3 its discrete average such that (eeJa(z, 8') [ 8')5 for all E X and
10 Note that set is always not empty when instantiating M- = MM for some lt E H. as it always contains 0 for all s' E S. This can be easily seen from Lemma 5 with = 0.

---

s' E S. Notice that, for ease of notation, we drop the dependence of the operator E from M, as such a dependence is always clear from the context.
By exploiting the notation introduced above, the relaxed optimization problem RA.s. (M) reads as: max Ph 4) s.t. (Ni q2) E M
(M) =
@:AxS
where we relax the functions q to be distributions over Ds, rather than deterministic. Then, we can prove the following:
Lemma 6. The problem (M) can be solved in time polynomial in 1/6 and the instance size.
By relying on a solution (x, q) to s (M). Algorithm Dis an approximate oracle for Ph.,. (M). In particular, when the relaxed problem is feasible, the algorithm returns & and the function q obtained by de-randomizing the randomized function q with its discrete average. Formally:
Theorem 5. For every H. E S. and E Da. Algorittm used for all k' h as approximate oracle On. in Algorithm 3 then it implements an approximate oracle as in Definition
Notice that the value returned by Algorithm 4 is the optimal value of the relaxed problem RA... ( (M). is easy to prove (see the proof of Theorem that the tables built by Algorithm ttthougg Algorithm are encoded by concave functions. This is the key feature that allows to go from randomized solution to its discrete average without loss in sender's expected rewards, and it is the reason why we need to assume that Algorithm is employed at every step in Theorem 5
7 Conclusion
In this paper, we provided a crucial advancement in Bayesian persuasion for sequential decision making, mastering the setting in which farsighted receiver interacts with an MDP, problem that was previously thought to be intractable [Wu et al. 2022 Gan et al., [0]2a|b].
First, we have shown that the class of Markovian signaling schemes, the standard choice in previous works and most MDP settings, do not constitute the "right" class of policies, since finding an optimal signaling
Markovian signaling scheme is NP-hard. Instead, we demonstrated that history-depente schemes allow to both circumvent the negative complexity result affecting Markovian signaling schemes and guarantee higher expected rewards to the sender in general. Specifically, we designed an algorithm find an optimal e-persuasive deeeedded signaling scheme in time polynomial in 1/c and in the instance size. The crucial component of the algorithm is to restrict the optimization convenient subelass of history-dependent signaling schemes, which we call promise-form as they encode the history into a promise of future rewards to the receiver. We showed that promise- form signaling schemes are both efficient to represent and as powerful as the general class of history- dependent signaling schemes. An interesting insight of our analysis reveals that being honest, i.e., keeping promises of future rewards, the key to persuade farsighted receivers in MDPs.
As future work, we will investigate the online learning variant of the problem studied in this paper, as done in [Zu et al.] [202]] Wu et al.) 2022 Bernasconi et al.) [2022]. J. which the transition function is not known. Moreover, it would be interesting to study the problem faced by sender that needs to
persuade a stream of receivers having adversarially-select
types, as done in (Balcan al. 2015
Castiglioni et al. 2020b 2021b Bernasconi et al., 2023
Acknowledgements
This paper supported by FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the -N-RR scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101 120237).
References
Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237:123-134, 04 2000.
10

---

Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 2016.
Yakov Babichenko and Siddharth Barman. Algorithmic aspects of private Bayesian persuasion. In ITCS, 2017.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In EC, 2015.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning to persuade in the dark. In NeurlPS, 2022.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online bayesian persuasion. In JCML, 2023.
Dimitri Bertsekas. Network optimization: continuous and discrete models, volume 8. Athena Scientific, 1998.
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. EC, 2012.
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 NeurlPS, 2020b.
Mattco Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Signaling in Bayesian network congestion games: the subtle power of symmetry. In AAAI, 2021a.
Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online Bayesian persuasion. In ICML, pages 1314-1323, 2021b.
Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential Dacision-making AAAI, 2022a.
Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Sequential decision making with information asymmetry. In CONCUR, 2022b.
Itay Goldstein and Yaron Leitner. Stress tests and information disclosure. Journal of Economic Theory, 177:34669 2018.
Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2615, 2011.
Anton Kolotilin. Experimental design to persuade. Games and Economic Behavior, 90:215-226, 2015.
Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration in Bayesian games. In EC, 2016.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclosure as means to security. In AAMAS, 2015.
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng
Xu. Markov persuasion processes and reinforcement learning. In EC, 2022.

---

Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe, Signaling in Bayesian Stackelberg games. In AAMAS, 2016.
You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade on the fly: Robustness against ignorance. In EC, 2021.
12

---

A History-dependent signaling schemes are necessary
In this section, provide an illustrative MDP instance in which history-depente signaling scheme is required in order to optimally solve Bayesian persuasion problem with farsighted receiver. This instance also proves Theorem [ receiver can achieve expected rewards
The instance depicted in Figure [
is easy check that the
(s0) 5, (x1) 10, (52) 0, (sa) = (s4)
without sender's recommendations. If the sender commits non-stationary Markovian signaling scheme 6" for hER. where d x + (AA), they can achieve an expected reward of SS S V (so) 25 while being persuasive. The latter is obtained by recommending actions deterministically as follows
(32) 01 (53, - ao. (3 01) - do-
Instead, history-dependent signaling scheme oi {Φ+) reT provide the sender with
expected reward of VS = V (so) 30 while being persuasive. This can only be obtained by adapting the action recommendation strategy in state 83 according to whether the receiver passed through state or state $2, as follows:
(s0. (6o) ag.
(o (01) ao:
o (00)22)))) (0n) = ap.
(800 (01) 01,
which makes the recommendation (00.02)
= persuasive as well.
80
a0,
2
81
82
00; 01
a0
a1
, =0
S =0
=10
83
10
94
a02 aD
a.
a1
1
2
2
Oo
01
ao
a0
d1
. =0
220 00
S = 100
20
R -22
R 20
R
R=0
MDP with S = {So. $1, $2, $3) ; A = {aa, a1.. = (0o. 01 H = [1, 2, and 3(so) = 1. The probabilities of the state transitions Ph and the private observations μa are reported on the dashed edges. The reward functions r r for the sender and the receiver, respectively, are reported on the solid edges, when different from For the sake of clarity, the visualization omits some irrelevant information. such private observations in $1, 82, $4 and deterministic transitions.
Figure 1: Visual representation of Bayesian persuasion problem defined
States where action selection is irrelevant omitted for brevity.
13

---

The latter example proves the existence of an MDP instance where schemes are necessary. The reported instance does not require bizarre constructions, and we believe that exploiting history to optimize action recommendations is crucial in practical scenarios as well.
signaling
Intuition of Figure [ In such a scenario, the MDP in Figure | can model a ride-sharing platform, where the drivers act as receivers and the platform is the sender. The platform can recommend routes and matching orders with the drivers, which then share with the platform a portion of the profit originating from the trips. In this example, 83 can be thought as location with high demand that is costly to reach, such as an airport terminal far from the city center. We can further think of the path $1 + S3 driver's trip to the airport while serving order, and $2 83 The platform can then adapt its order matching strategy according to whether the driver suffered empty costs got profit come the airport, such as guaranteeing quick yet cheap match the former, while waiting a more lucrative trip for the latter. This adaptive strategy can only be executed through history-dependent signaling scheme. Instead, Markovian signaling scheme cannot lure driver into coming to the airport without serving an order, with diminishing profits for the platform.
empty trip instead.
B Proofs omitted from Section 3
Theorem 2. There exist two constants a < and > such that computing an e-persuasive non-stationary Markovian signaling that provides the sender with at least fraction of the optimal sender's 's expected reward OPT is NP-hard.
Proof. We reduce from a promise version vertex cover in cubic graphs. In particular, given a cubic graph (V, E), there exists a E (0, 2] such that it is NP-hard to decide whether there exists a vertex cover of size or all the vertex covers have size at least (1 + 7 [Alimonti and Kann 2000
We design an instance such that the set of states S includes so, $1, 82 and $3. Moreover, it includes a state Se for each E, and a state 8, for each v E V. The time horizon is set as H 3. All the transition function and reward are independent from the time step h E [H]. Hence, we will remove the subscript from the notation.
The rewards and transition in the different states are as follows:
In state 8o there is a single state of nature 0g and actions 00.1 and 00,2- The transition 1
while p(se|so: a0 0g) |yl for each E E. The rewards of the receiver in state sq are F ((,,1, So, Oo) = 1 and R (00.2, 80, Oo) 0. The rewards of the sender in state so are ( 80, 0o) 0 and a (10.2, 80, 0n) =
function is such that p( (S, a0,1, 0n)
In state 81, there is single state of nature 0n and a single actions The transition function is p(s (11, (1, 01) = 1, while the rewards of the sender and the receiver in 81 are always O.
In state 82, there a single state of nature 02 and a single actions 02- The transition function ps,,|52, 02, 02) [V for each E V. The sender's and receiver's rewards in 82 are O.
In state 83. there is a single state of nature 0g and a single actions 03. The transition function is such that p( p(83/83. ag, 0g)) 1. The rewards of the sender and the receiver in 83 are always O.
For each e = (v, u) E. in the state s., there a single state of nature Oc, and two actions de." and de,u- The transition function is such that p(8 (8e de, 0z) = 1 and p(su Ge,uy 0g) 1.
The rewards of the sender and the receiver in state 8, are O.
For each a E V in the state su, there are two states of nature 0,, and 0..2. There are three actions 1, dn22, and a,,3. The transition function is such that p(sa Su, a, 0) = 1 for each a and 0. The rewards of the receiver in 8, are R (sp. Qv.1; 0e,1) = 1, (s 02 02.2) = 1, y (su; 0v.3, 02,1) = (sus av,3, (,,2) = and 0 otherwise. The rewards of the sender in s, is 2/2 if the receiver plays aw,3, i.e., (s,, 3, 1,,1) (s,, 0v,3, 0,.2) 1.2 and 0 otherwise.
All nature's states are drawn uniformly the nature's outcome at each node.
Finally, the initial distribution over the states is 3 such that ((so) ((1)) 1
14

---

U1
C1
02
e2
U3
Figure 2: Illustrative instance cubic graph (V, E).
In Figure 2 we have simple instance of cubic graph (undirected graph with degree bounded by 3), and in Figure 3 we have the instance the persuasion MDP built from the cubic graph in Figure
We recall that mon--tationnaa Markovian signaling scheme is defined by set of functions {ør JIE where On S x θ - ((A). However, we use both states 81 and 82 so that takes two steps to arrive in states both when starting from so and when starting from $1. Hence, each state (excluding the sink state 8z) can be reached only with a specific time step h. This allows us to work only with stationary signaling scheme, Le., such that the signals do not depend the time step. Hence, remove the subscript h from the signaling scheme notation.
61
dej
Oeg
d32,93
06.1
G
G
5
Sw1/2 R22
R 1/2
[
[P]
00.2
80
00.1
G
(a) Instance of Bayesian Persuasion in MDP
(b) Gadget G.
Figure 3: Instance of Bayesian persuasion in MDP constructed from the cubic graph (V, E) of Fig- 2 Sender's and receiver's rewards reported only when different from O. Solid lines represents actions (that are reported on the corresponding edges) while dashed lines represents stochastic outcomes (either of the transition model of the prior). For each E V the gadget G,, is re- ported Figure 3b
We will show that there exists a vertex cover size k then there exists a persuasive signaling scheme such that the sender's expected rewards is at least T. while if all the vertex covers have size at least (1 + 7) then all the e-persuasive signaling schemes have sender's expected rewards strictly less than a - where = 10-4,2 and a -h This will conclude
15

---

proof as we could use an algorithm for our problem with approximation factor less or equal to a to distinguish between the two cases of the original problem.
Completeness. Suppose there exists vertex cover V of size k.
Consider the signaling scheme o² such that @ (uo. 0o) 1, (ails), 01) 1, 20 (02(822 02) 1, and 6" (agls;, 0g) 1. Moreover, the definition of vertex cover, for each E there exists vertex de E V such that V/2 E E = (Ve, u). We set Ø" (ac, se: 0e) = 1. Finally, for each v E V*. set 6 (dv.1 su. 0,,1) L, 0" (av,2|su, 2..2) 1, and ø² (av,3]su. 00,1) o" (av,3lss 0v,2) for all u V*
First, we show that the signaling scheme is persuasive. Consider the state The receiver following the recommendations will always reach state E V* and this state will get utility It easy to see that playing action d0.1 the utiliity is 1. Hence, in state the receiver will not deviate. In states 81, 82, and #3, there is only one action available, hence the sigmaling scheme is trivially persuasive in these states. In a state 8c, recommendation they will transition to a state Sy, & E V*, and will get 1, while not following the recommendation they can get at most 1. In all the states 8u, for V*, the receiver gets 1, while deviating can get at most 1. Finally, a state Su, V & V*, the receiver gets 5. while deviating can get at most 1. Hence, the signaling scheme is persuasive.
E, the receiver has incentive to deviate. Indeed, following the
Moreover, the sender's expected rewards for playing according to 6² is if the initial state is sp, as in this state the signaling scheme recommends do22. On the other hand, if the initial state is $1, then a state Su with
V* is reached with probability k/[V| and state 8, with probability 1 - k/VV. Then, it is casy to see that the sender's s expected rewards in reaching a state 8, with V is 0 and 2 otherwise. Thus the total sender's expected rewards of the signaling scheme o² is:
V is reached with
1
A V
3 4
2
4
Soundness. Consider a signaling scheme Φ, and suppose that all the vertex covers have size at least (1 + k)k. We show that the sender's expected rewards strictly less than a <[vl First,
notice that if the sender's expected rewards at least a ( altr) it has to recommend 0022 with probability at least = 3/10, i.e., 6(00,2 (8,, 0u) Z expected rewards is at most
3 Indeed, if this is not the case the sender's
10
3 2 10
11
19
k 4
)
+ 2
+
22
50
2
as it gives most + 2 from 8o when 60,2 is played (which happens with probability less then 3/10) only consider the cases in which Φ(00.2 8o. 0g) 2 3
and 1 from 81- Thus
Then, suppose that for n states Se, E E E, the receiver's expected rewards following the recommen- dations from there on is at most 1 - 6, where 5 = 7/100. Denote with E C E be this set, where [ = and with E = E E. The c-persuasiveness constraint in state so when the recommended
action is 00,2 implies:
(1 mm
6 10. 0o)
(1 11-00 0)+ (1-6)+
(TT)
6(00.2|50, 0o)r S 0o)
as the left hand side is upper bound on the receiver's expected rewards starting from sg. The equation above implies that,
n (1 E
n
8)
+
2
1
E
8²
and by rearranging it:
E
3/1 11
F
n <
23
37/1000
90
16

---

Let V be the set of states Su, U E V, such that the receiver's expected rewards from there on is at least 1 - 8. Notice that for each state Se, with E,, there exists state Su. with V, such that E i.e., covers This implies that V covers E.
Suppose otherwise. Then, the set V is such that [V] (1 7)k and covers at least [E| edges. Hence, there exists super-set of V of size strictly smaller than (1 + k that covers all the edges, reaching a contradiction. This holds as adding vertex for each e = (2, u) E to V, we obtain vertex cover of E.
By contradiction, we show that [V] 2 (1 + 7)k
Then, we show that in all the states most 8. is easy to see that action 03 is recommended with probability at most 2/6 in cach state Su, U E V and the sender collects 2- If this is not the case, the receiver's expected rewards is strictly smaller than 26 + (1 25)1 = 6. This implies that the sender's expected rewards from a state Su. U E V is at most 8. similar argument shows that the sender's expected rewards from a state 8e. e E E, is at most 8.
V the sender's expected rewards from there on is at
We conclude the proof by showing an upper bound the sender's expected rewards. In the following. > [E] Moreover, assume w.l.o.g. that there
will exploit that the graph is cubic and [V] 2 k
are no unconnected vertices, which implies that E 2 2
[ and thus that ls > [V] Hence, the sender's
expected rewards when the initial state is 8o is at most:
1 E
E
1
+ 8
1
+ 6.
2
E
2 2
E
180
Moreover, the sender's expected rewards when the initial state is s1 is at most:
V
V
(1 + 7)k
n
1 (
(1 + 7)
n
V
2
IV
2
IV
1
(1 + 7
1 n
8n
+
2
2
IVI
2 V
[V
(1 7/
1 n 2 V 1 E 2 V
2
2
IVI
1
(1 7))
+
2
2
IV
5
1
(1+7)k
+ 7
2
2
[V]
60
where we used that [V] 2 (1 + > S 7 /| and that | < 3. Thus, since we start from so or $1 with probability 1/2, the sender's expected rewards is at most:
1 +
(1 + 7)
Y
6+
2
180
2
V
60
3
7
8
(1 +
(1+7)A
7k
+
+
4
V
30
2
[V
2/V1
3
Y
8
3/
7k
1
1
4
V
30
2
V
2
W
3
Y
8
(1
3)
7k
4
V
30
2
2
3
A
Y
7
7/
VA
4
V
30
50
2
3
7/
4
150
2
3
7
4
V
150
12
17

---

3
3
4
4
100
7
3
3
3
k
4
100
V
3
100
4
V
where we used that k 2 |V1/6 and 0 = 7/100. This concludes the proof.
C Proofs omitted from Section
Lemma 1. Given a promise-form signaling scheme == [(h, Phh, 9h) heH. for every h E H. and
history T ($1, ($1,01,.... a1,............................. Sh- 01, Sh.) Th. up to step h, the following holds:
Vi R.4 (a, = RR.7 (a. (h,
V/n R. (7) = D (sh: G7, and Vn S (T) =
( G)
(sh,
Proof. The statement can be easily proved by induction on the steps H.
и The base case of the induction is H. By definition of VR. (), for every action and history T = ($1, a1....,
- 1, 0H 8H) E Tu. the following holds:
R (a, Σ AE
pa (0 (a) 0).).
Since by construction (+) = (HH 0) for every E θ we have that:
BR.6
(a,
Σ pn 0) (sH,,,
o
Σ (
IE0
R (x,
Now, take H and assume that the statement holds for + 1. By definition of V R.d (a, r), for every E A and (81, Sh,,11.....
84-1; 04-1, -h-11, 81) E Th it holds:
R (a, Σ un (0)ss)))))())))))) BE8
( ((R(s,a + Σ
(n(('lsn, o) R.0 (r (a,s'))
e'ES
Moreover, for every 8' E S, the relation since (a, s') belongs Th+1. Given how Algorithm 2 is designed, holds:
R. let1 (r (a, 8')) h+1 (8', (e(a)))) holds by induction
G)((,))) (Sh. a, 5').
which, together with (0) (sn,,, e,, 0) for every E O, gives R (a, = VRR. (a, 8h, (4)
Similar inductive arguments show that VSSd" (T) VSS (sn, E for every step h H and history (1.1 E Th up to h, concluding the proof.
(81, 01,,.,..... 8h-1,
Lemma 2. Let a == {(An (hs gh) heH be promise-form signaling scheme. If a is n-honest, then, for every step h E H and state E S, it holds that R (s,t) 2 n(H - h + 1) for all E [s(s).
Proof. We prove the statement by induction.
The base case of the induction is h = H. Since a is n-honest, for every s E S and E In(s):
R (s,
Σ (n ((
t-n-
18

---

Now, take h < H and assume that the statement holds for h + 1. For every E S and E In
(s)
-EEn
mh
a))
aEADER
e'ES
ΣΣ Σ ((lb)))))
(i(s,a,0) +
Em(('ls (0n 7( 11))
aEA6E9
e'ES
2 11 77 ( hi
Σ E aEA BE
Σ Ph(s'ss,a,)) e'ES
= L n(H 1)
where the first inequality holds by induction, the second by n-honesty, while the last equality holds since Eese nn (a]ss) 8) Eves Pn (s'ls, a, 8) = 1. This concludes the proof.
Lemma 3. Let a = ((T,, Ph, 9h) MEE be an n-honest promise-fore signaling scheme such that, for every H. S, (5), and a, A, the following constraint is satisfied:
Na [n(()s)pn((ssss))) (1)(),0,0) + BEB
Σ
Pn(sss 0)9n((,);,,,5)) (p >
Σ
e'ES
[mn(0ssspn(alss.00 ( (1 [pd(s(ssd
Σ
Then, we can conclude that is (nH -persussis
Proof. We recall that, for 2 0, the promise-form signaling scheme a is c-persuasive if the history-
dependent signaling scheme o" := {o7] induced by a is c-persuasive according to Definition
As a consequence, order to prove the statement, we have to show that, for every step h H. history (81, (6,,01,..... 8h-1, 1, 8h) E Th. up step h, and pair of actions a, a' E A, it holds:
R (a, Σ (0 8n (a)))
, (f d',
Epn(s a,
( (6)
BEE
e'ES
By Lemma we have that R (a, = 1..00 (a, sh. G). Moreover, the following holds:
R.00 (alsh: (
Σ un (cl () E 1 ( as,
s'ES
Σ dEB
un (cl0))))
()(s Σ
pn(s'|sn, (gn a, (n 7(H 11))
s'ES
Σ (nl(0)s)pn(alssnncc 6Ee
As d', Σ s'ES
a', d. n(H fi)
where the first inequality holds by Lemma while the second one holds thanks to Equation 2 Finally, the statement is readily proved by noticing that nH h) nH.
Theorem 3. There is always persuasive promise-form signaling scheme ((Tn, (h, Ph, 9b hEN with sender's 's expected reward equal to OPT. More formally, it holds that V&S = OPT for the distory-dependent signaling scheme 6e induced by a.
Proof. The proof works by showing that, given any persuasive history-dependent signaling scheme, one can always build an ho-hotett and persuasive promise-form signaling scheme whose sender's expected reward is at least good. This, together with Lemma clearly proves the statement.
19

---

Given any persuasive history-dependent signaling scheme Φ = {orTrET, we build a promise-form signaling scheme =[(n, Ph. 9h) MeH as follows:
(s)) = {VA | T= ($1, a1 8h-1, 8h-1, ah-1 E Th A sn. = for all h > 1.
(,(8,1;0)) Dra... (0) for all h E H. E. (s): and O, where:
(T)
Th,sa
argmax
(1 1.8h 1.8N))TT My M==AV, (T)= (T)=z
which is guaranteed to exist given how (s(s is defined.
(h, e, (Th, @ (a, s')) for all h E H. ES, Is)s, and s' E S.
As first step, prove that, if Φ is persuasive, then the promise-form signaling scheme that have just built is persuasive as well. This can be easily proved by exploiting Lemma 3
First, we prove that a is an no-hoestt for 17 0. Formally, for every h E H. s E S, and E In(s):
V (Th.o.)
(6)
ΣV
Σ
[n((ls)@ra....all (a|0)
rh (7,s,, 0) ())
(,) @ (a,
(7)
nEA BEG
s'ES
Σ aEADER
Σ
(n( (al0)
r (s( +
Σ (a(6:ls.a.0)n((ssass))
s
ΣΣ aEADEE
(f(s,,,0)) + Σ S'ES
where Equation O6) holds by definition of Tha Equation 7 holds by definition of R. V Equa- tion (8) holds by definition of gn 8'), while Equation (9) holds by definition of (alsa,, 0). This proves that a an ry-honest promise-form signaling scheme, for 7) =
(Ti,a.):
In order to apply Lemma 3 we also need to to prove that satisfies the conditions in Equation (2). By applying definitions, it easy check that, for every h H. S, (s), and E A:
R (a, Than.)
Σ (0l5)) (al0) BEA
( (+8(s,a,0)
Σ sEES
pn(s'ss, a), R @ ((a,s'))
Σ
ph (f|s)) (ald) aR(s, Σ
a, p.llsls.o..0ggns......
AEG
s'ES
Σ (1)ss,))
a)) (
pn ()0ls,,,,)),,ss,,,,,,,))
(10)
e'ES
Moreover, since ó is persuasive we have that, for every h E H. E S. In(s), and a e A:
V (a,,hhan) Then.) h
Σ (0 (a|0)
(s,
Σ
2 @ (a,
#E0
aESS
Mn (0) (al0)
R. (A(s,'' +
#eS
( A (alos)))
Σ
pn(8'ss, (0) (11)
850
E'
20

---

where the last equality holds by definition of pn(als, i, f). Then, by combining Equation 10 and we get that, for every h H. s S. (s),, and a, A:
Equation T
Σ l
pm(0)s)pp(((sss..)
[)( + Em
s'ES
Σ REB
pn. (m((0s)pp(alss,,,,))
( ()) Σ pss 0))
s'E8
which means that satisfies Equation 2 Thus, by Lemma 3 we conclude that is persuasive.
In order conclude the proof, it remains to show that a achieves a sender's expected reward least as good as that obtained by ø. Formally, we prove that V/S.0" (r) 2 V ().(()) for every step E H and history Ta up to h. We will prove such result by induction.
The base case the induction is h = H. For every T = (81, 01 8H-1 11; E TH:
S (T) v ( (TH,en=)))
Σ Σ Hu uu (0)s Or m (a)0)r (s
aE
Σ Σ [n(00sH) (
aEA6EB
VS (SH,
VS.6" H
(T),
where the last equality holds by Lemma I
Now, let take h < H and assume that the statement that we want to prove holds for h + 1. Then,
for every T = (81, a1, 8h-1, ah-1, E Tr, it holds:
S. (T) V.,, (T))
(12)
Σ
Σ
Mn (0)(8)))) ((0)s))@ri.... (al0) r (s) + Σ
pn(''ss, ( @ (a,
aEA BEO
S'ES
Σ
Mn (n(00ss))pn(allssse
( a. + Σ
Pn (8,8'119,, (, O (a,
aEA
(13)
Σ Σ
(1 (s Σ a, oi
aEAA 1E0
s'ES
(14)
ΣΣΣN
Mh (n000s))pn(abssnc300 (i((s, Σ aEA
e'ES
(15)
ΣΣ
Mn (m(00ss)pp((alss.3.00 ri(snn 0) BEADEE
Pi a, 0 (s ag,,s))
s'ES
(16)
S. (sn, S.4 h
(T).
(17)
where Equation 12 holds by definition of Th.ss. for the promise ef E (x))),, Equation (33 holds
by definition of Sh (Sh, (7,0). Equation (14) holds by definition of 7 (ee.......g( .a) together with
the fact that yn (sh, (7,ss) s') h+ (Th.ena + (a, s')), Equation
[5] holds by induction, while
Lemma D proves Equation 16 and Equation [7
21

---

The proof is completed by applying the definition of OPT.
D Proofs omitted from Section 5
Lemma 4. Let a == [I. Ph. 9h) hen be returned by Algorithm instantiated with any oracle
Oh, as in Definition 3 For every h E H. 8 E S, (s),, it holds that V. (s. 2 (s.
Proof. Let = [(h,, Ph,, NEH be the promise-form signaling scheme returned by Algorithm instantiated with an approximate oracle Ru,s,. as Definition and let (K, q, v) t- Oh.s.-66 (AM 1). We prove the statement by induction. The base for h H of the induction holds trivially. Then, and & E (s), assuming the statement holds for h + 1 we have that:
for every < H, s E S,
S.S (8, = Σ Σ
Ma (0 ((())))(((())4400))
r as) +
Σ e'ES
(s (,00 0) ( (8,
LEABEB
(m(00))
()(,,,,0) +
REABE6
e'ES
EE (n(0s))((a(0)
(1((s,a,0)+ Σ
a, (
aEADER
S'ES
F (k.44)
2 Mf(s.))
where the first inequality holds by the the inductive assumption, while the second inequality holds thanks to Definition 3
Lemma S. Let M In (for h E H. be computed by Algorithm instantiated with any oracle Oh.s.. as Definition and let For every h E H. S E S, and i E (s), it holds that [c] E In(s) and Mf [c]s) 2 v/. (s,
{17 iPh Fiheen be an optimal promise-form signaling scheme.
Proof. We prove by induction that (s, [1]s Vg (s, t) for all h E H, S,and E (s). As base for the induction, we consider h H. Notice that MH(s, [4]s) an upper bound on the solution of LH.. 11)++) (this holds by Definition 3). Moreover, k(al0) (ar(sass i, 0) and
a(a,s' s') = 0 is feasible solution to PH.a.LeJo and so (Ri who S wh This readily implies that (s, [(]s) Z S.O (s, since:
(8, [1]))= =
max F FROM (K. (M.a)eV.-6
111
Phi (R, = VH (s,
As for the inductive step, consider any h < H. First, we show that k(al0) = (als,, 0) and ((a, s') (s, a, c, s')l is a feasible solution to (M Then, we show that it gets expected rewards larger than "S,00 (s.
First we prove feasibility of (R, Q). Consider first the constraint of Equation 4a
Σ (O]s))((())
(R(s,,,)) - Σ
BEABEB
s'eS
ΣΣ
())
GEABEB
22

---

ΣΣΣ ( (r)(s,a,0)+ BEADEB
E SEE
a (1995,,,)))(
212 [1]o,
which proves that (R, Q) satisfies the constraint of Equation 4a
Now, let turn our attention to the constraint of Equation (bb):
Σ (n(0)s)((al0) AE
(R(,,,,0) + Σ aalo'),,,,0)i(00
e'ES
Σ
as Emlolsaa0loossssa.ss
AE
a'ES
Σ
(a(0ss))
o, Σ pa(dls,.a
AEO
x'ES
(n(00s)p(((lss.400)
o) +
Σ
Pn(s'ls (n ())
BEO
s'ES
which proves (R. Q) satisfies the constraint of Equation (4b) and thus Ph,c, (1)+1) is feasible, i.e. (R., q) [e]e W.-5.
Now, we prove that it gets expected rewards larger than o*.
Ms(s, [c]6]
max Mi (m.))VV.
Fh,,,Mhr, (R)
ΣΣ
Σ
(((ss)(((a(O) ()) s'ES
BEB OEA
BEB REA
s'ES
ΣΣ Σ
( a))
Σ
Pn(s'ls, a (5,
0E8 REA
S' (5',4)
where we used the induction assumption the second inequality.
In conclusion, for every (s), it holds Vg"(s, (s. Ph,s..d 6 is feasible and thus e E (s)
0, and, thus, Mr ((]6) 2 0, implying that
Theorem 4. For any e > O, given an approximate oracle as in Definition 3 Algorithm with 5 = s/211 runs in time polynomial in 1/c and the instance size, while it finds e-persuasive promise-form signaling scheme that guarantees expected reward at least OPT to the sender.
3 instantiated
Proof. First of all we need to prove that the a returned by Algorithm 3 indeed promise-form signaling scheme. All the properties are trivially satisfied except for i) (r, a, s') E In+1(s') for each s S.a E A, s' E S, and & (s), and ii) 0 E I (s) for each s.
We start proving the first property. Let E S, E A, definition of Algorithm 3 it holds that v > -00 where (k,q, q, v) + O is the solution returned by the call to the oracle. It is easy to see that this implies that Md. Mg (8', g(a, s')) > -00.
S, and E (s). Since & E [s).,, by the
We consider two cases.
23

---

If h = H, then we have by construction that M Ma+1 (s', g((a, > -00 if and only if ça, s') =0. Thus, (s, a, s') = q(a, s') = =0 E H=11
h < H. then we M + (s', g(a. s()) -00 implying that v' -o,, where (N', x') t- )((,'= (M)+)) is the solution returned by the call to the oracle step + By the definition of Algorithm 3 this implies that g(a, s') E In41 Thus, go as 6') g(a, 8') E (s')
Now, we prove the second property. We only need to prove that for all 8 E S we have 0 E (s) but this is easily proved by Lemma 5 instantiated for 1 and = 0. Indeed we have that
Mf 0) 2 yS (s, 0), where we recall that Ms 0) and (K,, v) t Ob.,, (MM). By the definition of Algorithm 3 this implies that 0 [s)).
Then, we prove the persuasiveness. By Lemma we only need to prove that o := {(1r Ph, gb) hen satisfies the constraint of Equation 2 and that are 17-honest for some n. This holds trivially for n 28 as for all E H, E S and E (s) we have by construction that for all h E H, 8 E and
c. In (8), and (Ki 4, 0) + (n,,s,-((M,, (1)+1) we have
(als,,, 0) =(a(f), 0, = g(a,)''))))))))))
and by construction (x, E - This implies that the constraints of Equation (4a) and Equa- tion (4b) are verified and we can apply Lemma which let us conclude that is -2ert)--ersuasive.
We now prove the optimality of the signaling scheme a returned by Algorithm By combining Lemma and Lemma we have that for all E S. H. and & (s)
v (s. [1])) 2 VSS0" (s,
Then:
OPT S VS
= Σ B(s) (()))
#ES
Σ B(s) S.0 (s,
SES
< Σ B(s) (s,
#E$
Σ B(s) S.0" (s,
SES
= vSe
which proves our statement.
E Proofs omitted from Section 6
In this section we prove that the optimization problem RR,s,. admits polynomial time algorithm that finds an exact solution. We rewrite here for clarity the problem (M):
ΣΣ mn (0)s))(((a))) max R: ((A) (A(,)) AEA
(r((s,,,0) + Σ
(s ss s,
S'ES
(EDa(s(,N)
(18a)
s.t. Σ (Ols))(((a)))
(n(0ls)a(al)) (1 (B)s,,,))++
Σ (p((s(ls,,0)) Σ c. ('q((la,ss)) (..((aa)))) 21 (18b)
ac BEE
s'ES
Σ (1(0s))((aa))
En Σ (.9((((,6))) 2
0E8
s'eS
('EDa(si
24

---

Σ (1(()))((()))
(R] pa(ss'ss, bs,ss,,, (0)))t)(())))) s'ES
Ya, A.
(18c)
Even if the optimization problem is defined over functions, clearly can represent the functions and with finite number of variables with linear constraints (to assure that the the function's outputs are distributions). In order handle the quadratic terms of R..ss.(M we define "product" variable Za,e', for every a E A, s' E S, and & Do(s', MM) which is used in place of
Σ
pn (x(())))((())p ()) DEG
in Program 18a and has satisfy the constraint for all A and s' E
pa (s)(cl))) 8EB
(F'.)
For the linear variable we can introduce the non -egnatitev variables $a.0 k(al0) for each 0 θ and E A, that need to satisfy the simplex constraint for all O, i.e. E.iee,..... EnEA Ea,9 By using these variables write the problem LP s... (M):
max ER ER
ΣΣS, (a
ΣΣ
Σ
2a, M('s
(19a)
nEA BE0
''ES aE aE (s),)s
s.t. ΣΣ (n.o +
ΣΣ
E
6. Za.st 20
(19b)
wEABEE
s'ES (ESaEAL'ED((H.N)
Σ (n,0m
Σ
Σ
d. az
DE
s'ES (ED((('))
Σ (01ss)
rAss,,'' 0) Σ (1)
Va,d' E (19c)
BEO
EES
Σ Za, Σ (s)
AA ' (19d)
('EDsee,M))
Σ 5a,0 =1
AO O. (19e)
REA
Since (M) has polynomial number of variable and constraints one can find solution in polynomial time.
The next two lemmas show that one can use LMM.s,(M).. The first shows that any solution to R1,s,, (M) can be used to find a solution to (M,
Lemma 7. Let (1s q) wh be a feasible solution to (n,s,aM) then there exists a feasible solution to I.P (M) with the same value.
Proof. Let (K.,) be a feasible solution to (M). Then define:
Z0,s' =
(n s)(((l))p)ssssll...... () s'), Va A, E S Do(5,
9cB
and
Ea,9 xa)l), Va E A.
Then one can show by direct calculation that the constraints of LP (M) are satisfied and that the objective value of LPh...(M) is (M....M) (which is the value of program (M)). O
The next lemma show a result which "complementary" to the one above.
Lemma 8. Given feasible solution of LPP.s. (M) one can find solution to Rt.s, (M) with at least the same value.
25

---

Proof. Given feasible solution and & to (.M.a.(MM Construct a solution (x., Q) to Rh.a.(MM as follow for each o' Do M), A and E S:
if Σ (a),
Σ an
i(''aa, 8)
OEE otherwise
=1('==0)
and for all and 0 O:
k(a/0) = Ea.a.
Notice that if for a specific h E H, S,'' E S and E A, the constraint of Equation (9d impose that if Eage Mn (0, s) Sa (sssss, a, 8) = then "a,s',' for all z'. This means that in any case the following condition holds:
20,s'
Σ (1 (,)("(),)) nE0
(20)
We now fix any h E H. E S and E DD show that the constraints of Rm,s (M) are satisfied, by using Equation 20) Let us start with the constraint of Equation (18b):
Σ i' 4.A(/aa5))
Σ ph (O1s))n(()())
aR(s,a,)) + Σ (s(
REA BEB
8'ES
VEDs(e',M)
E
Σ (aop)(0)))RR(ssa.00))
ΣΣ Σ
Σ
('Ee,pn(0))))) ()
eEAA 8EB
aEA (D .M) SESS
Σ .EA 868
(0s))
ΣΣ
Σ
L' 2a,'"'
at AEA &ES (F
4,
where the last incquality hold as (2,E) is feasible solution to &P,,,,, This proves that the constraint of Equation (18b) is satisfied.
For Equation (8ec) similarly:
Σ c. (-8(1aas))
Σ
pn (O(s)()((())))
r ,R( E
(p((s(ss,a,0)
s'ES
V'Da(e',M)
Σ (0se)
Σ Σ
Σ
(0).) a, 0)((((a,,
lce
OEG i veDa Daset,MM (ile,,Ms*t M'S
Σ (00 0
Σ
Σ
Σ Za.
OEG
DEDa s'ES
2 Ea.ee (s,, + Enhl''ss ()V
8EB
s'ES
where in the last inequality we used that (2, a feasible solution to LP LP,...(MM. Thus the constraint of Equation (1c)) is verified. This proves that (x, q) is feasible for R, ( (M). Then, by plugging Equation (20p into the objective of RM,,,((M) one directly prove that the values of the two problems is the same.
Now we are ready to prove the main result of this section: Lemma 6. The problem RA.,, (M) can be solved in time polynomial in 1/6 and the instance size.
Proof. Take solution (z,E) LP (M). This be done in polynomial time LP (M) linear program with polynomial many variables and constraints. Then apply to the solution (z, {) the trasformation used in Lemma 8 to obtain feasible solution to R. This gives optimal solution to (M). To prove the last result, assume that there would exists feasible solution (N', 7') (')(( to RR....M (M) such that F ,²) Fr.e, (R, Q), and apply the trasformation defined in Lemma 7 This would find solution (z',6") strictly better then (z, E) which contradicts
the optimality of (2,E) {) for LP (M).
26

---

Theorem 5. For every E H. s E S, and E Ds, if Algoritm used all h' > h as approximate oracle Ow Os, in Algorithm then it implements an approximate oracle as in Definition
Proof. Fix any h E H. 8 E and i E Da. We show that for h+ E and for any distribution E (Ds)) it holds that:
Mg
8, LiEDS(OMM)) (7(1)))) 2 EMEDI(A.M)) ((.,))
(21)
where the table M9 is the one built by Algorithm 3 with oracle of Algorithm
Define ig = EVEDs(s.MR) i. r()). Then for every 1, E Di and d' S L we have that Dh
(M)) Sr.s. (M)),
as it only appears in the RHS of the constraint of the problem (
By construction of Algorithm 3 we have that:
() = an (M
and that by Lemma 7 and Lemma 8 S (1 equal the value of L described by
Equations (19). for each 4. This means that the function i + Sp is concave [Bertsckas 1998, Theorem 5.1].
Thus for every distribution y A(Ds) we have:
Dien, (761 (M (M
Σ 7()) Sha (Mh+ 1DDs
Observe that we cannot apply directly the above concavity property as, for every 8 E S, in Equa- tion 21 are only selecting the components of y such that M -00.
To solve this problem we can, for any distribution y E A(Ds), table M and S. define the new distribution on D5 M) that puts all the mass on the co components of M on O. Formally 7()) (()) for all D D)) and ((0) 7(0) EVEDA (().. Note that with this definition we have lg. = Ee & 7(t) and ELED, M)) 7()0 I ExED.(E,M) an. Combining these inequalities we can conclude that:
(s (EEED( (7()[ss)
= Pr (Ma+1)
> an (M
Σ
7(1) (maa(M)
veDa(a.M))
Σ
7())
(m
vEDa(a.M!)
Σ
7(1) M}(
(x.
where the last inequality follows since it is easy that 2 2 0 and the last equality follows from Lemma 7. This proves Equation (2T)
Now assume that (ts, ②) is a the optimal solution to RR...(MM, 1 Clearly if (1s, Fz) vp h.s then (Is, q) The 2-8- where q -@z]s-
Using the inequality of Equation 21 we can readily perform the following inequalities:
Fh, (15,2)
Σ Σ (013)((((()
DEAGEA
SEES
27

---

2 ΣEUB (n(0)))((a()) (T((5,a 0) + Epi(s (, a)
E
(6
MEBREA
Fh. (N.. 9) h+1
a (Mh+t) 2 ( h+)
and thus Algorithm
4 returns tuple that satisfies the conditions required by Definition
28


Reviews:
[{"review_id": "zubf3JTG9y", "reviewer": "Reviewer_bcaS", "summary": "The paper considers a (finite-horizon) dynamic persuasion problem\nbetween a sender and a receiver, both of whom are long-lived. At each\ntime $t$, there is a publicly-observable state $s_t$ and a\npayoff-relevant quantity $\\theta_t$, which is observed only by the\nsender, and whose distribution depends on the current state (and\nis independent of other quantities). Based on the observation of\n$\\theta_t$ the sender recommends an action to the receiver (which may\nor may not be followed). The publicly-observable state then updates to\n$s_{t+1}$ according to a transition kernel that depends on the current\nstate $s_t$, the quantity $\\theta_t$ and the action chosen by the\nreceiver. Both the sender and the receiver seek to maximize their\ntotal expected payoffs.\n\nPrevious work on this topic, with few exceptions, has focused on\nmyopic receivers, motivated by settings in which the receiver is\nshort-lived. The difference here then is the focus on long-lived,\nfar-sighted receiver. In this setting, the paper first shows (via an\nexample) that the class of Markovian signaling schemes (whose\nrecommendations only depend on the current state $s_t$) is\ninsufficient for optimal persuasion, and the sender can do better\nusing a signaling scheme that takes into account the history of the\nprocess. Due to the computational difficulties in working with general\nhistory-dependent schemes, the paper then considers promise-form\nsignaling schemes, which make recommendations based not only on the\ncurrent state, but also on a (history-dependent) \"promise\", which is a\nguarantee on the receiver's continuation payoffs. Essentially, the\npromise succinctly summarizes the history, thereby reducing the\ncomputational complexity to be polynomial in the size of set of\npromises. The authors show that, upon imposing a honesty condition on\nthe promises across time, the class of promise-form signaling schemes\nsuffice for optimal persuasion. The authors also propose an\napproximation scheme for computing approximately-persuasive\npromise-form signaling schemes with good payoff guarantees, that is\npolynomial in the approximation factor.", "questions": "+ Do the approximation results continue to hold if the relaxation of\n  the persuasiveness constraint is imposed on the conditional\n  expectation?\n\n+ With the current definition of $\\epsilon$-persuasiveness, it may be\n  possible to design mechanisms that achieve payoffs substantially\n  better than $OPT$. Are there any guarantees on how small (or large)\n  this difference can be?", "limitations": "The assumptions are stated clearly. Some discussion of the limitations\ninduced by relaxing the persuasiveness/honesty requirements would be\nhelpful.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The paper considers an interesting variation of the sequential\n  persuasion problem, allowing for far-sighted receivers. This makes\n  the problem substantially more complex. Nevertheless, the paper\n  identifies a class of relatively simple and approximately persuasive\n  signaling schemes that nevertheless achieve optimal payoffs for the\n  sender, and are furthermore computationally tractable.\n\n+ The paper illustrates well the insufficiency of the class of\n  Markovian signaling schemes, and furthermore (adapting existing\n  results) shows that finding a constant-factor approximation within\n  the class of Markovian signaling schemes is NP-hard.\n\n+ The class of promise-form signaling schemes is fairly simple and\n  easy to implement; furthermore, it seems approximately-optimal such\n  schemes can be computed via solving an LP (repeatedly).", "weaknesses": "+ While the class of promise-form signaling schemes is interesting,\n  there is a significant line of work in economics that studies the\n  use of promises in repeated games with incomplete information. The\n  paper does not cite those papers, nor does it place its\n  contributions within that context. A particularly relevant paper in\n  this line is Abreu, Pierce and Stacchetti (Econometrica, 1990),\n  whose results imply the sufficiency of the class of \"promise-form\"\n  strategies for discounted repeated games with imperfect monitoring.\n\n+ Similarly, the paper would benefit from connecting with general\n  literature on repeated games (with or without incomplete\n  information). For instance, the insufficiency of Markov signaling\n  schemes is very much in the same vein as the inefficiency of Markov\n  perfect equilibria in, say, repeated prisoner's dilemma to sustain\n  cooperation. With far-sighted receivers, it is not surprising that\n  Markov signaling schemes are not optimal for the sender. \n\n+ $\\epsilon$-persuasiveness: In the analysis of history-dependent (or\n  promise-form) signaling schemes, the authors relax the\n  persuasiveness requirement to $\\epsilon$-persuasiveness. There is a\n  subtle issue in interpreting this relaxation. To explain, a natural\n  relaxation would be that the receiver's expected continuation payoff\n  from following the recommendation is at most $\\epsilon$ worse than\n  choosing any other action, *after* receiving the recommendation.\n  Specifically, the expectation taken here would be with respect to\n  the posterior belief after receiving the recommendation. However,\n  the condition in Definition 1 requires something different; it\n  states that the receiver's expected payoff from following a\n  recommendation, *multiplied* by the probability of receiving that\n  recommendation, should be at most $\\epsilon$ worse. In particular,\n  there is an extra factor equaling the probability of recommending a\n  particular action.\n\n  While this may seem like a minor technical issue, this has\n  substantial implication on the assumption that the receiver would\n  adopt such a recommendation. For instance, this suggests that as\n  long as the probability of recommending an action is small, the\n  sender can recommend an action that can yield substantially lower\n  continuation payoff for the receiver, and still expect the receiver\n  to accept the recommendation. This seems to be a very strong\n  assumption on the receiver's behavior, that does not align with the\n  assumption that the receivers are (approximately) Bayesian.\n  Moreover, with such a strong assumption, it is no longer clear if\n  $OPT$ is the right benchmark for comparison.\n\n  A potential fix to this issue would be to impose the relaxation on the\n  conditional expectation, i.e., to replace the $\\epsilon$ term in the\n  definition with $\\epsilon \\sum_{\\theta}\n  \\mu_h(\\theta|s_h)\\phi_\\tau(a|\\theta)$. However, it is not clear if\n  the later approximation results continue to apply with this change.\n\n+ Finally, while the paper makes sound and rigorous technical\n  contribution, there is not enough discussion motivating the specific\n  model being studied. For instance, there is no discussion of the\n  motivation behind far-sightedness assumption; the myopic behavior of\n  the receivers in previous work is frequently motivated by assuming a\n  series of short-lived receivers. In particular, are there any\n  specific applications where a single sender and a single receiver\n  interact in the manner studied? (I think this is especially useful\n  given the somewhat complicated form of the signaling scheme\n  proposed.) Some discussion here would benefit the paper by grounding\n  the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the Reviewer for their thoughtful comments and for mentioning pieces of related literature that we will reference and discuss in a final version of the paper. We provide below detailed answers to their questions.\n\n- *“Do the approximation results continue to hold if the relaxation of the persuasiveness constraint is imposed on the conditional expectation?”*\n\nIs the reviewer referring to the fact that the relaxation could be normalized by the probability with which the action is recommended? In this case, we believe that our techniques can be extended without any major difficulties changing the definition of $\\epsilon$-persuasion and modifying the proofs accordingly. Let us know if you need further technical details.\n\n- *“With the current definition of $\\epsilon$-persuasiveness, it may be possible to design mechanisms that achieve payoffs substantially better than $OPT$. Are there any guarantees on how small (or large) this difference can be?”*\n\nIn general this difference can be arbitrarily large. Let us take a simple example with a single node, a single state, and two actions $a_1$ and $a_2$. The first action is $\\epsilon$ better for the receiver with respect to the second one. The sender’s utility is $1$ if the receiver plays $a_2$ and $0$ if the receiver plays $a_1$. The optimal persuasive mechanism recommends $a_1$ and it has sender’s utility $0$. The optimal $\\epsilon$-persuasive mechanism recommends $a_2$ and has sender’s utility $1$.\n\nThis is an edge case. In non-degenerate settings the utility of the optimal persuasive and $\\epsilon$-persuasive mechanisms are close.\n\nMoreover, we want to remark that this is standard in any setting with relaxed IC constraints, like $\\epsilon$-Nash equilibria, $\\epsilon$-Stackelberg, etc."}, {"review_id": "yg6hU9y6Vl", "reviewer": "Reviewer_q53d", "summary": "This paper considers a specific model of information design, where the receiver takes actions on a sequential decision process under a global, unknown natural state $\\theta$. To make the model simple, the work assumes that the sequential decision process to be an MDP with a known model, plus the ability of the receiver to exactly optimize the cumulative reward once a (belief of) $\\theta$ is given. In this case, the signaling scheme represents a (more general) mapping from the natural state and the trajectory up to the current step to a distribution of actions as information revelation. Further, when making decisions the receiver is not allowed to use the posterior distribution/belief of the natural state obtained from previous steps (which means only $\\hat\\theta_h$ is used).\n\nGiven the above assumptions in the model, the work provides a polynomial-time algorithm to obtain an $\\epsilon$-persuasive signaling scheme. This disagrees with the NP-hard-like claims given in previous works. Such disagreement stems from the use of trajectory information and thereafter its simplified version of promise form. The algorithm is natural but quite creative.", "questions": "This conclusion indeed applies to the model-based scenario (meaning that the receiver knows the state set $S$, the observation set $\\Theta$, the state transition distribution $p$, and the observation distribution $\\mu$). However, does this conclusion also apply to the model-free case? This question might not be within the scope of the work, but the conclusion drawn is a bit too broad if such estimation of model is now involved. If this situation is not discussed, the authors should emphasize this important assumption in the abstract and introduction. Specifically, it should be clarified which information the receiver is assumed to know and base their decisions on.\n\nThis assumption represents a strong capability for the receiver. If it does not possess this knowledge, the sender's manipulation could be more powerful, and Markovian signaling schemes might be viable. For instance, if the receiver is unaware of the state and can only observe the sender's signals, and it needs to estimate the state and its transitions based on those signals, does the sender have the opportunity to confuse the receiver's judgments and achieve stronger persuasion? I find the claim \"We consider the most general setting\" in line 85 a bit too strong.\n\nAdditionally, can the revelation principle argument still be applied in a sequential setting? Does recommending only one action for each state achieve the goal of persuading a receiver in an MDP? I could not find any relevant discussion on this. Has the author considered \"future-dependent\" signaling schemes: recommending a set of future actions for each state instead of just one action? Or sending a signal $m$ to encode a set of future actions they wish to recommend? Moreover, in the aforementioned scenario, can the sender confuse multiple states by sending signal $m$? If the revelation principle is abandoned, is a history-dependent signaling scheme still necessary? If there is no discussion on the validity of the revelation principle, this assumption should be prominently emphasized.", "limitations": "See weakness", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The work provides new models of information design in sequential decision problems. The new model no longer possesses theoretical hardness.\n2. The work proposes a new polynomial-time algorithm to find an $\\epsilon$-persuasive signaling scheme.", "weaknesses": "Several limitations persist: 1) MDPs are assumed to be exactly solved. 2) MDP models are known 3) Receiver can't aggregate historical information of the natural state 4) No experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the Reviewer for their positive feedback. We report below detailed answers to their questions, which we hope will make them appreciate our paper even more.\n\n- *“This conclusion indeed applies to the model-based scenario (meaning that the receiver knows the state set $\\mathcal{S}$, the observation set $\\Theta$, the state transition distribution $p$, and the observation distribution $\\mu$). However, does this conclusion also apply to the model-free case? This question might not be within the scope of the work, but the conclusion drawn is a bit too broad if such estimation of model is now involved. If this situation is not discussed, the authors should emphasize this important assumption in the abstract and introduction. Specifically, it should be clarified which information the receiver is assumed to know and base their decisions on.”*\n\nIn this work we assume that everyone knows everything. We agree with the Reviewer that studying the learning problem in this setting is interesting and worth studying. However this imposes some difficulties as, when the model parameters are unknown, the receiver cannot even know if the signaling scheme employed by the sender is persuasive or not. See also response to Reviewer Rxqa for a related discussion.\n\n- *“This assumption represents a strong capability for the receiver. If it does not possess this knowledge, the sender's manipulation could be more powerful, and Markovian signaling schemes might be viable. For instance, if the receiver is unaware of the state and can only observe the sender's signals, and it needs to estimate the state and its transitions based on those signals, does the sender have the opportunity to confuse the receiver's judgments and achieve stronger persuasion? I find the claim \"We consider the most general setting\" in line 85 a bit too strong.”*\n\nIf the receiver does not know the model, it is not clear which is the “right” definition of rationality. We can assume that the receiver “learns” during time but there are too many possible options (do they use confidence bounds? Do they use a regret minimizer? Do they follow the recommendations when they are uncertain or not?). On the other extreme, we can assume that the receiver never learns anything. This is the myopic setting studied in previous works. \n\n- *“Additionally, can the revelation principle argument still be applied in a sequential setting? Does recommending only one action for each state achieve the goal of persuading a receiver in an MDP? I could not find any relevant discussion on this. Has the author considered \"future-dependent\" signaling schemes: recommending a set of future actions for each state instead of just one action? Or sending a signal $m$ to encode a set of future actions they wish to recommend? Moreover, in the aforementioned scenario, can the sender confuse multiple states by sending signal $m$? If the revelation principle is abandoned, is a history-dependent signaling scheme still necessary? If there is no discussion on the validity of the revelation principle, this assumption should be prominently emphasized.”*\n\nWe followed the recent extensive literature of information design (even in sequential settings, e.g. [Wu et al., 2022, Bernasconi et al., 2022, Gan et al., 2022a,b]) in which the signals are single action recommendations, and the revelation principle is more or less assumed to hold. A formal proof of the statement would require a large amount of notation and labor and deviate from the authors’ main focus with this work. Moreover, it would use standard techniques to derive a non-surprising result. However, we will happily underline this choice better in the final version of the paper.\n"}, {"review_id": "LIVnR3hapM", "reviewer": "Reviewer_Rxqa", "summary": "The paper discusses a history-dependent signaling scheme in persuading a farsighted receiver. It first show that it is necessary for the sender to adopt a non-stationary and non-Markovian signaling scheme. Specifically, for every step and state reached at that step, this scheme defines a randomized mapping from the sender's private observations to action recommendations for the receiver, based on the whole history of states and receiver's actions observed up to that step. While such signaling policy could be intractable to describe, the paper provides a crucial simplification, promised-form signaling schemes, that allows the sender to only design finite size signaling scheme with optimal performance. Finally, the paper proposes a PTAS algorithm to determine the optimal promised-form signaling schemes.\n", "questions": "How does the author think of the learning problem under this farsighted setup? Is it also possible to design a no-regret learning algorithm for the sender to learn the optimal promised-form signaling scheme?", "limitations": "n/a", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is very well written! The authors clearly explain the motivation, the model, the results, and the proofs with vivid intuitions, making the technical concepts very easy to follow.\n2. The paper extends the previous work on signaling schemes in MDPs to a more general setting, where the receiver is farsighted. The paper made several important technical and conceptual contributions to this problem, including the necessity of non-stationary and non-Markovian signaling schemes, the simplification to the promised-form signaling schemes, and the PTAS algorithm to determine the optimal promised-form signaling schemes.", "weaknesses": "1. The method is related to the literature of dynamic stackelberg equilibrium. The authors should discuss the relationship between their methods. \n2. I expect the authors to provide some real world applications of their model and methods, e.g., expand on the ride-sharing example in Appendix A.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to hear that the Reviewer finds our paper to be making several important technical and conceptual contributions. We provide below a detailed answer to their question on the learning problem, while we will follow Reviewer’s suggestions to include a discussion of related literature on dynamic Stackelberg equilibrium and to expand the ride-sharing example in a final version of the paper.\n\n- *“How does the author think of the learning problem under this farsighted setup? Is it also possible to design a no-regret learning algorithm for the sender to learn the optimal promised-form signaling scheme?”*\n\nOur main focus with this work was to deal with the known model setting. Recent literature considers the learning problem in sequential BP settings, e.g. [Wu et al., 2022, Bernasconi et al., 2022, Gan et al., 2022a,b]. By extending our interactions model as in the above works we think that the techniques introduced there can also tackle the learning problem in our setting. In particular, we conjecture that an estimation phase that explores uniformly and then commits to an optimal signaling scheme of the estimated model would work. This should lead to an optimal $T^{2/3}$ bound on the regret and constraint violation. We will happily add a brief yet detailed discussion on this point."}, {"review_id": "vsD0O2Etph", "reviewer": "Reviewer_XkbC", "summary": "This paper studied a Bayesian persuasion problem where the sender and receiver act sequentially. \n\nBelow are two main changes in the new problem setting of this work:\n(1) The authors assume that the sender stops providing recommendations to the receiver if the receiver does not follow the recommendation. \n(2) Under this assumption, the authors also consider farsighted receivers as opposed to myopic receivers in previous works. \n\nIn the new setting, the authors showed that the Markovian signaling schemes are not optimal (additionally, finding the optimal Markovian signaling scheme in the previous problem settings in NP-hard), and they instead introduced a new class of promise-form signaling schemes for the new problem setting. The authors also show that the promise-form signaling schemes can be found in polynomial time while guaranteeing the schemes satisfy \\epsilon-persuasive property.", "questions": "1. Can you please provide application scenarios that fit well the new case\n2. Can you please add a discussion on the potential limitations\n3. In all problems that involve strategic manipulations, the potential fairness issues\n4. Why are numerical experiments included in some of the related works, e.g., \"Bayesian Persuasion in Sequential Decision-Making\" but not here in this paper? What are some of the major differences that result in the decision of skipping the numerical experiment part?\n", "limitations": "Not that I can find due to my limited background in this topic.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Clearly listed all key theoretical findings under the assumption that the sender will\n2. A novel class of promise-form signaling schemes is given with approximation algorithms that are relatively practical and can be completed in polynomial time", "weaknesses": "1. Overall a difficult-to-read paper (more difficult than the popular papers the authors cited) due to inadequate description and lack of concrete examples of the problem. Why sequential move in Bayesian persuasion is an important research topic is not highlighted. For a general audience not familiar with Bayesian persuasion, it is hard to tell why the new scenario is important.\n2. Lack of justifications for the critical assumption that the sender will stop providing recommendations. Further justifications are needed to show that it is rational for the sender to prefer to stop recommending over other strategies commonly used like tit-for-tat, etc. If this is the typical case in real-world applications, the authors should also point out that to improve the soundness of this assumption. Since all findings in this paper are based on this assumption, I encourage the authors to put more emphasis on this.\n3. Lack of discussion on the possible limitations \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the Reviewer for providing useful feedback despite being unfamiliar with the topic of the paper. We provide below detailed answers to their questions. Finally, we are sorry to hear that they find the paper to be a difficult read. We will make our best effort to make a final version of the paper accessible to a general audience despite its technical nature.\n\n1. *“Can you please provide application scenarios that fit well the new case”*\n\nDue to space constraints, we deferred an explicative example in Appendix A (lines 436-446). We agree with the Reviewer that a concrete example would help understand the problem at hand and with the additional page provided in the final version of the paper we will include this example in the main body of the paper.\n\n2. *“Can you please add a discussion on the potential limitations”*\n\nAs the Reviewers Rxqa and q53d suggested, we will highlight the fact that our work assumes common knowledge of the environment, and we will discuss how this assumption could be lifted in future works.\n\n3. *“In all problems that involve strategic manipulations, the potential fairness issues”*\n\nResearch on the connection between information design and fairness is still understudied. While we agree with the Reviewer that it would be worth investigating, we feel that this topic falls outside the scope of our work.\n\n4. *“Why are numerical experiments included in some of the related works, e.g., \"Bayesian Persuasion in Sequential Decision-Making\" but not here in this paper? What are some of the major differences that result in the decision of skipping the numerical experiment part?”*\n\nWe think that the main contribution of this work is theoretical as we answer an open question in the literature. We will leave experimental evaluation of our algorithm to future research. Moreover the authors feel that an experimental evaluation of the planning problem would be less interesting compared to the one in [Bayesian Persuasion in Sequential Decision-Making], as we are not currently considering the learning problem."}]

Author rebuttal:
We want to thank the reviewers for their useful feedback and for praising the technical contribution of our work. We will take their suggestions in great consideration to improve the final version of the paper in terms of discussion of additional related works, considered assumptions, and real-world applications.

Before providing detailed replies to reviewers’ questions below, we want to uphold two important choices in our problem formulation. 

While reviewers rightly noted that the known-model assumption is restrictive, we think that solving the planning setting already required to overcome significant technical hurdles, which left no space for additional contributions. Moreover, we believe that the planning problem is a natural preliminary step towards addressing the corresponding learning problem, in which the model is (at least partially) unknown to the agents. The latter problem is a nice direction for future research on this topic.

Finally, we will make an additional effort to explain why the farsighted receiver assumption matters in this setting. First, it complements previous works considering myopic receivers in MDPs, which is sometimes unrealistic in real-world applications, such as ride-sharing platforms where the same driver typically interacts with the platform multiple times. Secondly, it better aligns this line of research on information design in MDP settings with the classical MDP literature, which crucially assumes farsighted decision makers.

Meta-review: I've skimmed the paper, read the reviews and the rebuttals, and discussed the paper with the reviewers and the AC. I think this is a good paper which should be published. 

However, there are two major caveats:

- The notion of $\epsilon$-persuasiveness in the submitted paper is not well-motivated. However, the reviewers are convinced the results carry over to a stronger and well-motivated notion (as per the reviewer-authors discussion). 

- A blatant (but easily fixable) flaw in presentation. What is the receiver's behavioral against $\epsilon$-persuasive policy? The definition (L107) says "exactly rational", whereas the technical developments (e.g., equations in L227-232) are consistent with "follow the policy". 

While it is unusual to allow such substantive changes from the submission to the camera-ready version, we decided to give the authors the benefit of a doubt. I emphasize that **these changes are necessary for the paper to be accepted**
. 

**Minor issue:** The "stopping assumption" (L115-117) states that the receiver stops issuing recommendations once any of them is not followed . The following should be clarified:

- It is not an "assumption" per se, but a design choice, and a fairly reasonable one.

- It is w.l.o.g. under 0-persuasiveness, and therefore does not affect the OPT. However, it might worsen the performance of $\epsilon$-persuasive policies, for all we know.  

- As the main results (Thms 4 and 5) restrict the policy class anyway, this design choice can be interpreted as a part of this restriction.
Decision: Accept (poster)