Sequential Information Design: Learning to Persuade in the Dark
Authors: Martino Bernasconi
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Francesco Trovò
Venue: NeurIPS 2022 Accept (2022)

Abstract: We study a repeated information design problem faced by an informed sender who tries to influence the behavior of a self-interested receiver. We consider settings where the receiver faces a sequential decision making (SDM) problem. At each round, the sender observes the realizations of random events in the SDM problem. This begets the challenge of how to incrementally disclose such information to the receiver to persuade them to follow (desirable) action recommendations. We study the case in which the sender does not know random events probabilities, and, thus, they have to gradually learn them while persuading the receiver. Our goal is to design online learning algorithms that are no-regret for the sender, while at the same time being persuasive for the receiver. We start by providing a non-trivial polytopal approximation of the set of sender's persuasive information structures. This is crucial to design efficient learning algorithms. Next, we prove a negative result: no learning algorithm can be persuasive. Thus, we relax persuasiveness requirements by focusing on algorithms that guarantee that the receiver's regret in following recommendations grows sub-linearly. In the full-feedback setting---where the sender observes all random events realizations---, we provide an algorithm with $\tilde{O}(\sqrt{T})$ regret for both the sender and the receiver. Instead, in the bandit-feedback setting---where the sender only observes the realizations of random events actually occurring in the SDM problem---, we design an algorithm that, given an $\alpha \in [1/2, 1]$ as input, ensures $\tilde{O}({T^\alpha})$ and $\tilde{O}( T^{\max \{ \alpha, 1-\frac{\alpha}{2} \} })$ regrets for the sender and the receiver, respectively. This result is complemented by a lower bound showing that such a regrets trade-off is essentially tight.

Sequential Information Design: Learning to Persuade in the Dark
Martino Bernasconi" Politecnico di Milano
Matteo Castiglioni
Alberto Marchesi
Politecnico di Milano
Politecnico di Milano
Nicola Gatti" Politecnico di Milano
Francesco Trovò' Politecnico Milano
Abstract
We study repeated information design problem faced by informed sender who tries to influence the behavior of a self- oeff-interested receiver. We consider settings where the receiver faces sequential decision making (SDM) problem. At each round, the sender observes the realizations of random events in the SDM problem. This begets the challenge of how to incrementally disclose such information the receiver to persuade them to follow (desirable) action recommendations, We study the case which the sender does not know random events probabilities, and, thus, they have to gradually learn them while persuading the receiver. We start by providing a non-trivial polytopal approximation of the set sender's persuasive information structures. This is crucial to design efficient learning algorithms. Next, we prove a negative result: no learning algorithm can be persuasive. Thus, we relax persuasiveness requirements by focusing algorithms that guarantee that the receiver's regret in following recommendations grows sub-linearly. In the full-feedback setting- where the sender observes all random events realizations we provide algorithm with Ö(VT) regret for both the sender and the receiver. setting- where the sender only observes the realiza- design al- [1/2, 1] input, ensures Ó(T*) and O(Tmax (a.1- 9)
Instead, in the tions of random events actually occurring in the SDM problem gorithm that, given regrets, for the sender and the receiver respectively. This result is complemented by lower bound showing that such regrets trade-off is essentially tight.
Introduction
Bayesian persuasion [Kamenica and Gentzkow 2011 (a.k.a. information design) is the problem faced by an informed sender who wants to influence the hehavior of self-interested receiver via the provision of payoff-relevant information. This captures the problem of "who gets to know what", which is fundamental in all economic interactions. Thus, Bayesian persuasion is ubiquitous in real- world problems, such as, e.g., online advertising [Bro Miltersen and Sheffel 2012], voting Alonso
and Camaral 2016 Castiglioni et al. 2020a Castiglioni and Gatti] 2021
traffic routing Bhaskar
al. 2016 Castiglioni
[202 al. security Rabinovich al. 2015 Xu al. 2016 and
marketing Baaichenko and Barman 2017 Candogan 2019].
We study Bayesian persuasion in settings where the receiver plays in sequential decision making (SDM) problem. An SDM problem is characterized by a tree structure made by: decision nodes, where the receiver takes actions, and chance nodes, in which partially observable random events occur. The sender perfectly observes the realizations of random events, and their goal is to incrementally disclose
EEmail: martimo haaarttoobeemmssooodnccccmattttt wtw.aattttootssiiiiiiii.to. wtw.pttt.maaccciiiiiiiii.e nicola, gat.ioaaeaaiiiffaeesooolllllollo .trovo) @ (ppoimi.it
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the acquired information to induce the receiver towards desirable outcomes for the sender. This is not an easy feat when the sender and the receiver have different utilities. In order to do so, the sender commits to a signaling scheme specifying a probability distribution over action recommendations for the receiver at each decision node. Specifically, the sender commits to persuasive signaling scheme, meaning that the receiver is incentivized to follow recommendations. We consider the case of a farsighted receiver, meaning that they take into account all the possible future events when deciding whether to deviate or not from recommendations at each decision node.
With some notable exceptions (such as, e.g.. [Z et al., 202T)) ) Bayesian persuasion models in the literature make the stringent assumption that both the sender and the receiver know the prior, which, in our setting, is defined by the probabilities associated with random events in the SDM problem. We relax such an assumption by considering an online learning framework in which the sender, without any knowledge of the prior, repeatedly interacts with the receiver to gradually learn the prior while still being persuasive.
concrete example of a setting that fits our model is that of navigation app sending route recommen- dations to a driver. The app (sender) gets to know information about traffic congestion sequentially, since it might change over time, especially for long routes. Moreover, at any point in time, the app can send recommendations to the driver (receiver), who in turn has to take decisions on which routes to choose sequentially. The app and the driver might have different utilities. For example, the app may want to maximize overall traffic congestion, while the driver has to minimize their travel time. Moreover, the receiver interacts with the app multiple times and, thus, the application must provide good recommendations to the receiver, otherwise they would switch to another navigation app.
Original contributions. Our goal is to design online learning algorithms that are no-regret for the sender, while being persuasive for the receiver. We start by providing non-trivial polytopal approximation of the set of sender's persuasive signaling schemes. This will be crucial in designing efficient (i.e., polynomial-time) learning algorithms, and it also shows how a sender-optimal signaling scheme can be found in polynomial time in the offline version of our problem, which may be of independent interest. Next, we prove negative result: without knowing the prior, no algorithm can be persuasive at each round with high probability. Thus, we relax persuasiveness requirements by focusing on learning algorithms that guarantee that the receiver's regret in following recommendations grows sub- lub-linearly, while guaranteeing the same for sender's ss regret. First, we study the thlfull- full-feedback case, where the sender observes the realizations of all the random events that may potentially happen in the SDM problem. In such a setting, we provide an algorithm with Ö(VT) regret for both the sender and the receiver. Then, we focus on the bandit-feedbat setting, where the sender only observes the realizations of random events on the path in the tree traversed during the SDM problem. In this case, we design an algorithm that achieves Ô(T") sender's regret and Ö(T (o.1 9) receiver's 's regret, for any E [1/2, 1] given as input. The crucial component of the algorithm is non-trivial exploration phase that uniformly explores the tree defining the SDM problem to build suitable estimators of the prior. This is needed since, with bandit feedback, playing signaling scheme may provide insufficient information about its persuasiveness. Finally, we provide a lower bound showing that the regrets trade off achieved by our algorithm is tight for 11/2,//3]
Related works, Some works addressed Bayesian persuasion in Markov decision processes (MDPs). Gan et al. [2022] and Wu et al. [2022) show how to efficiently find a sender-optimal policy when the receiver is myopic (i.e., it only optimizes one-step rewards) in MDPs with infinite and finite horizon, respectively. Moreover, the former assume that the environment known, while the latter do not. These works considerably differ from ours, since we assume farsighted receiver and also model partial observability of random events Another work close to ours is (Zu et al. 2021), which studies a (non-sequential) persuasion problem in which the sender and the receiver do not know the prior and interact online. Zu et al. (022 provide a persuasive learning algorithm, while, in our model, we show that the ignorance of the prior precludes the possibility of committing to persuasive signaling schemes, and, thus, we need to resort to new techniques to circumvent the issue. Another line of research, that uses similar techniques as the one employed in this work, studies learning in SDM problems while satisfying unknown constraints -Beraasconi-de-Lun et al., 2021 Bernasconi et al., 2022 Finally, Celli et al. [2020a] study Bayesian persuasion with multiple receivers interacting in an
Gan et al. 2022 also study model with farsighted receiver, where they show that the problem of finding a sender-optimal policy is NP-hard. Thus, they do not provide any algorithmic result for such model.

---

imperfect intoormatiooooonnn sequential game. Differently from ours, their model adopts a different notion of persuasiveness, known as ex ante persuasiveness, and it assumes that the prior is known. Other works study learning problems in which the sender does not know the receivers' payoffs (but knows the prior); see, e.g., Castiglioni et al. 2020b 2021b 2022
2
Preliminaries
2.1 Sequential decision making problems
An instance of SDM problem is defined by tree structure, utilities, and random events probabilities. The tree structure has a set of nodes H == 2 U Ha U Hee where: 2 contains all the terminal nodes in which the problem ends (corresponding to the leaves of the tree), Ha is the set of decision nodes in which the agent acts, while He is the set of chance nodes where random events occur. Given any non-terminal node h E H. \ Z, we let A(h) be the set of ares outgoing from h. h E Ha. then A(h) is the set of receiver's s actions available at h, while, if h E He. then A(h) encodes the possible outcomes of the random event occurring at h. Furthermore, the utility function u : Z - [0. 1] defines the agent's 's payoff u(z) when the problem ends in terminal node E Z. Finally, each chance node E Hhe is characterized by a probability distribution 14 E A over the possible outcomes of the corresponding random event, with uu (a) denoting the probability of action a E A(A)
In SDM problem, the agent has imperfect information, since they do not perfectly observe the outcomes of random events. Thus, the set of decision nodes Ha is partitioned into information sets (infosets for short), where an infoset I S Hd is subset of decision nodes that are indistinguishable for the agent. We denote the set of infosets as I. For every infoset I E I and pair of nodes h, h' e I, it must be the case that A(h) = A(h') =: A(I), otherwise the agent could distinguish between the two nodes. We assume that the agent has perfect recall, which means that they never forget information once acquired. Formally, this is equivalent assume that, for every infoset I E I, all the paths from the root of the tree to a node h E identify the same ordered sequence of agent's actions.
2.2 Bayesian persuasion in sequential decision making problems
We study Bayesian persuasion in SDM (BPSDM) problems. These extend the Bayesian persuasion framework (Kamenica and Gentzkow 2011 to SDM problems by introducing an exogenous agent that acts as sender by issuing signals to the decision-makinn agent (the receiver) By following the Bayesian persuasion terminology, the probability distributions μ4; for each chance node h are collectively referred to as the prior. Thus, the sender observes the realizations of random events occurring in the SDM problem and can partially disclose information to influence the receiver's behavior. Moreover, the sender has their own utility function defined over terminal nodes, denoted as f: Z [0, 1J. and their goal is to commit to a publicly known signaling scheme that maximizes their utility in expectation with respect to the prior, the signaling scheme, and the receiver's strategy.
Formally, a signaling scheme for the sender defines a probability distribution dn E As(k) at each decision node h E Hd, where 5(h) is a finite set of signals available at h. During the SDM problem, when the receiver reaches node h E Ha belonging an infoset T E I. the sender draws a signal 8 ~ Φb and communicates it to the receiver. Then, based on the history of signals observed from the beginning of the SDM problem (s included), the receiver computes a posterior belief over the nodes belonging to the infoset / and plays so as to maximize their expected utility in the SDM sub-problem that starts from 1, taking into account the just acquired information.
As customary in these settings, a simple evelation-principlee on signaling schemes that are direct and persuasive [Kamenica and Gentzkow 2011 Arieli and Babichenko 2019). In particular, a signaling scheme is direct if signals correspond to action recommendations, namely S(h) A(h) for all h Ha. A direct signaling scheme is persuasive if the receiver is incentivized to follow action recommendations issued by the sender. Moreover, we assume that, if the receiver does not follow action recommendations at some decision node, then the sender stops issuing recommendations at nodes later reached during the SDM problem. This
argument allows us to focus
3 Foor a finite set we denote with Ax the set of probability distributions over X. AAppendix shows that BPSDM reduces to classical Bayesian persuasion when there is sequentiality.
3

---

is without loss of generality. We refer to [Von Stengel and Forges, 2008 Morrill et al. 2021 for discussion on similar problem the field of correlation in sequential games.
2.3 The sequence-form representation
The sequence form is a commonly-used, compact way of representing (mixed) strategies in SDM problems [Koller al. 1996]. In this work, the sequence-fore representation will be employed for receiver's strategies, and to encode the signaling schemes and priors, as we describe in the following.
Receiver's strategies. Given any E H. we let or be the ordered sequence of receiver's actions on the path from the root of the tree to node h. By the perfect recall assumption, given any infoset E I. holds that o, (h) = (,(hh) ) (1) for every pair of nodes h, h E I. Thus, we can identify sequences with infoset-action pairs, with appending action a E A(T) at the end of o, (T), for any infoset I E I. Moreover, Ø denotes the empry sequence. Hence, the receiver's sequences are Σ, {(I,a) I I, A(T)) {2). In the sequence-form representation, mixed strategies are defined by specifying the probability of playing each sequence of actions. Thus, a receiver's 's strategy is represented by vector æ E [0, 1] | where æ[[]] encodes the realization probability of sequence E E,, Furthermore, sequence-form strategy well-defined and only if it satisfies the following linear constraints:
(I, a) encoding the sequence of actions obtained by
x(2) = and al(o(()) EaEA(H) (T)) VI
We denote by Xr the polytope of all receiver's s sequence- sequence-form strategies. We will also need to work with the sets of receiver's strategies the SDM sub-problem that starts from an infoset I I, formally defined as I == far X a
}}.
Signaling schemes. We represent signaling schemes in sequence form by leveraging the fact that the sender can be thought of as perfect-information agent who plays at the decision nodes of the SDM problem, since their actions correspond to recommendations for the receiver. Thus, since sender's infosets correspond to decision nodes, their sequences Σ, {(h, h Ha, a E A(h)) U (Ø}. Then, we denote the polytope of (sequence-form) signaling schemes as & S [0, 1] where each signaling scheme is represented vector & E [0, () satisfying:
and plo,(h) = EneA(h) (b)a))) vh E Ha.
where, similarly to a, (h) for the receiver, (h) denotes the sender's sequence identified by H. We also define 1 n {0, 1) as the set of deterministic signaling schemes, which are those that recommend a single action with probability one at each decision node.
We also encode prior probability distributions μa by means of the sequence form. Indeed, these can be though of elements of fixed strategy played by (fictitious) perfect-information agent that acts at chance nodes. Thus, for such chance agent, we define Eg, Xe, and az(h) as their counterparts previously introduced for the receiver. Moreover, in the following, we denote by μ*' E Xe the (sequence-form prior, recursively defined as follows:
Priors.
n [0] = and μ (h)a)(ha) = (h)a (a(a) Vh E He, Va E A(h).
Ordering of sequences. For the sake of presentation, among sequences. Given two sequences a = (I, a) E Σ, and o' = (J,b) E Σ,, we write a 3 a' (read as a precedes a'), whenever there exists path in the tree connecting node in I node in J, and such a path includes action a. We adopt analogous definitions for sequences in Eg and Σ
introduce partial ordering relation
3 Learning to persuade
In this work, we relax the strong assumption that both the sender and the receiver know the prior μr* by casting the BPSDM problem into online learning framework in which the sender repeatedly interacts with the receiver over a time horizon of length T. At each round f e [T]. the interaction
We refer the reader Appendix B for example of SDM problem and its sets of sequences.

---

[ encoding realizations of random events drawn according to μ²; (ii) the sender and the receiver play an instance of the (one-shot) BPSDM problem (detailed in Section 2.2 in which the sender commits to Φ.. random events at chance nodes are realized as defined by Yr. and the receiver sticks to the recommendations issued by the sender; and (iv) the sender observes a feedback on the realization of random events at chance nodes, which can be of two types: full feedback when the sender observes ye: which specifies the realizations of all the random events at chance nodes that are possibly reachable during the SDM problem; bandit feedback when the sender observes the terminal node 2t E Z reached at the end of the SDM problem. The latter is equivalent to observing the realizations of random events at the chance nodes that are actually reached during the SDM problem, namely ae (z())).
goes as follows (i) the sender commits to a signaling scheme Φ E Φ; (ii) vector y, E f0.1)
By letting 40 (*x")) be the set of persuasive signaling schemes, i.e., such that the receiver is incentivized to following recommendations (a formal definition is provided in Definition 2b the goal of the sender is to select a sequence of signaling schemes, namely ...... Φr, which maximizes their expected utility, while guaranteeing that each signaling scheme Φ, is persuasive, namely o E (
We measure the performance of a sequence $2,..., Oy of signaling schemes by comparing it with an optimal (fixed) persuasive signaling scheme. Formally, given a signaling scheme & E 4, we first define (', μ²),, respectively F(Ø, ju),, as the expected utility achieved by the receiver, respectively the sender, whenever the former follows action recommendations. These can be expressed as linear functions of Φ, which, for any f Ne, are defined as follows:
U(O (1) = Σ [l
F( 1)) = [xbale)loooc
ZEZ
ZEZ
Finally, by letting o² E mngmaxpeto(r F(Ø, μ²) be optimal (fixed) persuasive signaling scheme, the sender' performance over T rounds is measured by the (cumulative) sender's regret:
RT Ene(T] (F(Ø", ,²) -
The goal is to design learning algorithms (for the sender) which select sequences of persuasive signaling schemes such that Ry grows asymptotically sub-linearly in T, namely RT = (T)..
4 On the characterization of persuasive signaling schemes
4.1 A local decomposition of persuasiveness
In this section, we formally introduce the set of persuasive signaling schemes (1²)) as the set of signaling schemes for which the receiver's expected utility by following recommendations is greater than the one provided by an optimal deviation policy (DP) In addition, we show how to decompose any DP into components defined locally at each infoset, which will be crucial in the following Section deviation points in which the DP prescribes to stop following action recommendations; and (ii) the continuation strategies to be adopted after deviating from recommendations.
Intuitively, a DP for the receiver is specified by two elements: (i) set of
We represent deviation points by vectors w E {0, IE which are defined so that w|o] 1 if and only if the DP prescribes to deviate upon observing the sequence of action recommendations o E E,- Moreover, by leveraging the w.l.o.g. assumption that the sender stops issuing recommendations after the receiver deviated from them, we focus on DPs such that each path from the root of the tree to a terminal node involves only one deviation point. As a result, the set of all valid vectors w E (0, 1) |E.!
formally defined as Ω = { E [0,1)1E-] EoeS,
w|o] S 1 Vz 1
We represent the continuation strategies of DPs by introducing the set of continuation strategy profiles, denoted as P == >x==(I_)Exx, X,,-- A continuation strategy profile p E P, with p (Pa )
defines a strategy P. E Xr,r for every receiver's 's sequence a = (I, E Σ, Intuitively, P. is the strategy for the SDM sub-problem starting from infoset / that is used by the receiver after deviating upon observing sequence a E E,. As a result, any pair (w, p) E f2 x P specifies a valid DP; formally:
TThroughout this work, for n E N, we denote with 'r] the set (I...., n). For ease of exposition, all the definitions and results in this section are provided for the prior μ²" It is straightforward to generalize them to the case of a generic μ Xe.
5

---

Definition (Deviation policy). Given a vector w E Ω and a profile p E the (w. p)-DP prescribes to follow sender's recommendations until action a is recommended at infoset for some sequence (T,a) such that w((r 1; from that point on, il prescribes to play according to strategy Pa.
We denote by U μ²)) the receiver's 's expected utility obtained with (w. P)-DP, so that we can state the following formal definition of persuasive signaling schemes.
Definition (Persuasiveness), A signaling scheme & E Q is e- e-persuasive, namely & E (2 if
max (w.p)
U 12)) 11) S.
Moreover, a signaling scheme Φ E & is persuasive, namely & E (u²)), il is O-persuasive.
Intuitively, the above definition states that a signaling scheme is e-persuasive if the receiver's expected utility by following recommendations is at most less than the one obtained by an optimal DP, which is a DP maximizing receiver's 's expected utility.
Our local decomposition of DPs is based on suitably-defined, simple deviation policies, which we call single-point DPs (SPDPs). These are a special case of DPs that stop following sender's action recommendations only when specific single infoset is reached and a particular action is recommended therein. SPDPs are formally defined as follows:
Definition 3 (Single-point deviation strategy). Given receiver's sequence a = a)) E, and receiver's ss strategy Pa E X for the SDM sub-problem starting from infoset I, the (o, Pa) P prescribes follow sender's 's recommendations until action is recommended at infoset I; from that point on, the strategy prescribes to play according to Pa-
We denote by Uo-p, (Φ. 2=)) the receiver's 's expected utility obtained by following an (a, P-)-SDD. decomposition shows that the dif-
The following theorem provides the key result underlying ference between the utility achieved by a (w, DDD and that obtained by following recommendations can be decomposed into the sum over all the sequences o E Σ,. of analogous differences defined for the (a, Pa) PSP-S, where each difference is weighted by w[a].
Theorem 1. Given a signaling scheme &f E ②e and a (w. DD- it holds:
(w-P(p, - EoEx. wlol UUop (0. x²) - U(),
4.2 A polytopal approximation of the set of persuasive signaling schemes
In the following, we show how to exploit Theorem I to provide an approximate characterization of the set ( using polynomially-sizee polytope. First, we state a corollary of Theorem showing that persuasiveness can be bounded by suitably defined SPDPs. Formally
Corollary 1. Given a signaling scheme & E 4 the following holds:
max (w)x)
(") U()
Σ (T.EEE,,,
U (0.) P.EX,
max
1²
we introduce the following definition of e-persuasive polytope (Lemma justifies the term polytope), as the set of signaling schemes for which there no (o., Pa >-PDP that achieves a receiver's utility that exceeds by more than e/ /E,. that of following recommendations. Definition 4 (Persuasive polytope). The e-persuasive polytope is defined as:
By exploiting Corollary 1
Ac(1²) = { E +b
max Up-pp p²) - U( v²) S s Wo E J P.EX,,)
Moreover, we denote by A(μ*) the 0-persuasive polytope.
As we show in the following lemma, Ac(1²)) is an efficiientlyreepreenntaeee polytope.
Lemma 1. The set (e(")) can be described by means of a polynomial number of linear constraints.
$ 'All the proofs are provided in the Appendices GGven any 2 E 1R, we let [a] max(æ, 0).
and

---

The following lemma shows that the e-persuasive polytope is contained in (2(4), and that the set of persuasive signaling schemes is contained in the former. Formally:
Lemma 2. It is always the case that 40 (1²)) A(p²) S. A,(w") S $:
Lemma 2 also implies that the polytope A (1=²) exactly characterizes the set of persuasive signaling schemes + (1²"). Thus, by adding the maximization of the sender's expected utility F(Ø, j4*) on top of the linear constraints describing A(μ*), ), we obtain polynomially-sized linear program for finding an optimal sender's 's signaling scheme in any instance of the BPSDM problem in which Ja is known.
Theorem 2. The BPSDM problem can be solved in polynomial time when the prior p is known.
5 Always being persuasive is impossible: relaxation is needed
In this section, we prove that it is impossible to design an algorithm that returns sequence of persuasive signaling schemes for a generie BPSDM problem.
Theorem 3 (Impossibility of persuasiveness). There exists a constant 7 E (0, such that no algorithu can guarantee to output sequence $1...., ΦT of signaling schemes such that, with probability al least ?,. all the signaling schemes o, are persuasive.
Notice that this result is in contrast with what happens in non- non-sequential Bayesian persuasion (see the work by Zu et al.] (202T), where it is possible to design no-regret algorithms that output sequences of signaling schemes that are guaranteed to be persuasive with high probability. Theorem motivates the introduction of a less restrictive requirement on the signaling schemes. In particular, we look for algorithms that output signaling schemes ......, such that the expected utility loss incurred by the receiver by following recommendations rather than playing optimal DP is small. To capture such a requirement, we introduce the following definition of (cumulative) receiver's 's regret:
Vr = Elety
max (wxp)
(W,P((,, - -Eepry U 11))
Therefore our goal becomes that of designing algorithms guaranteeing that the cumulative receiver's regret grows sub-linearly in T, namely Vr = TT)), while continuing to ensure that Rr o(T).
In Sections 0 and / we design algorithms achieving sub-linear VT and Ry for the learning problem
described in Section The algorithms implement two functions: (i) CILLECTSTRATEGYS which, at each / E [T). draws a signaling scheme 6, E & on the basis of the internal state of the algorithm; and (ii) UPDATE(O:). which modifies the internal state the basis of the observation o, received as feedback. Each algorithm alternates these two functions as the interaction between the sender and the receiver unfolds described in Section 3 Specifically, under full feedback the sender observes y and calls UPDATE(yL) while in the bandit feedback it observes 2t and calls UPDATE(2().
Learning with full feedback
In this section, will discuss the online problem faced by the sender that wants to optimize online its utility F(O, (xr)) while learning the unknown prior f=" We start by providing a learning algorithm (Al (Algorithm[[) working with full feedback, i.e., when the sender observes the realizations of all the possible random events. The main idea of the algorithm is to choose signaling schemes Φ that belong to suitable sets Ag, (Pt) which are designed to be "close" the set 4o (fx of persuasive signaling schemes. At each round t E [T), Algorithm [ defines the desired set as follows. First, maintains an estimate ü. of μ"; formally, it defines a radius such that the event == (1),, 1=" -= S 6, VI E [ holds with probability at least - 5. Second, it defines parameter 3e such that, conditionally to the realization of the event E, the following two conditions hold: (i)
Algorithm Full-foedback algorithm
function SELECTSTRATEGY()
Φ, f arg max F(b. (A.)
$cλ8, (A.)
return do
function UPDATE(Y,)
P441 + Σ 10l/7 Wa E Es.
1og(22(E..//))
6111 +
2t
B.41 <- 2/ le+11
the decision space Ag, (Pt)) contains the optimal signaling scheme o'; (ii) Agp, (4²) contains the
7

---

signaling scheme Φ.. Intuitively, the first condition is needed to have low sender's regret, while the second one yields signaling schemes that are approximately persuasive
The polytopal approximation that we provide in Section 4.2 plays a crucial role in the complexity of Algorithm|| [ Specifically, it allows it to select the desired ot in polynomial time by optimizing over the set As, (42), which can be done efficiently. The use of the set Ag, (7t)) over $9 (7t,) is necessary due to the fact that the latter is not known to admit an efficient representation. Formally:
Theorem 4. Given any E (0, 1), with probability at least 1 - 6, Algorithm guarantees:
PT O (T(Eel/6).. VT ( T (7 (T(2)/65)
Moreover, the algorithm runs in polynomial time.
7 Learning with bandit feedback
In this section, we build on Algorithm M to deal with bandit feedback, i.e. when each round & E [2'] the sender only observes the ter- minal node ,, reached at the end of the SDM
Algorithm 2 Bandit-feedback algorithm
function SBLECTSTRATEGYO: if t S N then a= (h, a) f- migmin Ca(a]
D First Phase
problem. The main difficulties of such a set- ting can be summarized by the following ob- servations. First, the feedback 2, only reveals partial information about the prior, and such information also depends on the selected sig- naling scheme ih. Second, even if the sender plays signaling scheme Φ o for an ar- bitrarily large number of rounds, there is no guarantee that they collect enough information to tell whether & E &. (1*) or not for some > O. Indeed, the persuasiveness of signal- ing scheme depends on all receiver's 's utilities in the SDM problem, and some parts of the tree may not be reached during a sufficiently large number of rounds by committing to Φb. Thus, any algorithm for the bandit-feedbace setting must guarantee suitable level of ex- ploration over the entire tree, so as to keep track of the entity of the violation of persua- siveness constraints.
E, 3 o' t (h)
Choose Φ, E u:: :. =1
else
Second Phase
& c arg max max F(). sEARN (PN) (6C((
return d,
function UPDATE(21):
Build path p. E {0, 1 from (=()
Sample Ti ~ 0, s.t. p. = + o E (T())))
for a E Σg (T.) do
C441lo| <- Colo +1
M[+1lo] ट (e] -=
Cyplol p+(0]
<++1[a] f- V
loxl E
Cit1 + {M [u|o]] Petiloll & 1o
B+1 < 2/
Del [og(4T)
2(141)
We design two-phase algorithm, whose pseudo-code is provided in Algorithm 2 The algorithm takes as input the number N E [T'] of rounds devoted to the first phase guaranteeing the necessary amount of exploration, as detailed in Section 7. During this phase, the SELECTSTRATEGN procedure implements an efficient deterministic uniform exploration policy, which builds an unbiased estimator N of 4=" This allows restrict the space of feasible signaling schemes used in the subsequent phase to those that are approximately persuasive, i.e., those in the set A (. In we discuss the second phase of the the algorithm, composed by the rounds t > N, during
Section 7 which the algorithm focuses on the minimization of sender's regret by exploiting the optimism in face of uncertainty principle. Finally, in Section 7.3 we provide lower bound on the trade-off between sender's ss and receiver's regrets, matching the upper bounds achieved by Algorithm P for a large portion of the trade-off frontier. This result formally motivates the necessity of the uniform exploration which is performed in the first phase of the algorithm.
7.1 Minimizing the receiver's regret
At each round / E [T), the sender observes a terminal node 2, E that uniquely determines a path in the tree defining the SDM problem. We encode such a path by means of vector P, E {0, 1] [Eal
See Lemma and 10 in Appendix F for the formal statements of these properties.
8

---

such that P.(o] = 1 if and only if the chance sequence E Ee lies on the path from the root of the tree to 2t, namely o = o If the sender commits to a signaling scheme Φ D, then is easy to see that, for every parameter Φ; [o,, (1:) [=
(h, a) E E., the element Pr(0] is distributed as Bernoulli of The crucial observation behind the design of our estimator is that, if the sender commits to deterministic signaling schemes T, E II at some round & E (T], then for all the chance sequences a E E. that are compatible with n.. i.e. that can be observed when T. is played, we have that p. is distributed as Bernoulli of parameter μ [o]] Formally, a sequence E E. is compatible with a if there exists a chance node E He and an outcome a E A(h) satisfying (h, a) and т Te(os(()) 1. This observation leads to the following result:
[o].
Lemma 3. For every deterministic signaling scheme т E II, let
(T) {a ah, E E. |a E A(h) A [[oo
Then, during each round S N of Algorithm 2 holds E [p,[o]] = =" every a E (TTe)
Thus, during the first phase, Algorithm 2 builds the desired estimator jo of μ² as follows. At each round < N, after observing the feedback z,, the algorithm samples deterministic signaling scheme ग, E II according to Φ (the one actually selected at 1). so that all the sequences E Eg such that p, [a] = (or, equivalently. 3 oz((e) belong to Σ, (T, Then, for every o E Σ (T:). the algorithm updates the estimator component [o] according to p. [o]. Since the probability of visiting a sequence a E Σe depends on &, (and, thus, can be arbitrarily small), the first N rounds must be carefully used to ensure that each sequence is explored at least N/|E,1 times. To explore a specific sequence a E Ec, we choose signaling scheme Ø, such that a E (TT))) for every deterministic π Φ.. The procedure described above is needed for minimizing the receiver's 's regret, since, in the second phase, the algorithm selects signaling schemes Φ, from Agw ( In particular, as shown by the following lemma, Algorithm 2 guaranteess that the receiver's regret is upper bounded by 28N at each round > N, since it defines éx [a] for each sequence a En so that the event = [o]
"ol I co V(t, o) E [T] x Le} holds with probability at least 1 8/2.
Lemma 4. Under the event ε, Algorithm guarantees that Φ. E AA23y (1*) at each round t > N.
7.2 Minimizing the sender's regret
Algorithm 2 also needs to guarantee small sender's regret. To do so, we would like that o' is valid pick for the algorithm, i.e., it belongs to Asy (ft,). However, differently from the full-feedback setting, stopping exploration after the first N round does not guarantee optimal rates. In order to fix this issue, in the second phase, the algorithm selects & optimistically by maximizing the sender's expected utility F(Ø, (2) over both @ E Agp (px) and μ C,)ō), where (6) is suitably-defined confidence set centered around fh such that {u² E C,())) E, and. thus, it holds with high probability. This guarantees that max F(Ø".. 1)) 2 F(Ø". μ²). Formally:
Lemma 5. If the event E holds, then, for every round > N, holds that &² E Asx (Pt) and max (6) F(Ø", 1.) 2 ()).
Thus, F( 1²) 2 F(o., (..) 2 (a) F( ( 2 F(ø", u²)) holds in the limit, implying that F F(O,,'' converges to F(Ø", ,²") after sufficiently many rounds. Formally:
Theorem 5. Given any E (0, 1) and N [T], Algorithm 2 guarantees:
RT- = O N (N
and Vr = N [ ( COOONNNNNN
T|
Ecl
log
[
log
with probability at least 1 5. Moreover, the algorithm runs in polynomial time.
In contrast to the case with full feedback. the optimization problem solved by Algorithm belongs to the class of bilinear problems, which are NP-hard in general [Hillar and Lim 2013). However, in Theorem 5 we prove that our specific problem can be solved in polynomial time. Furthermore, notice that Theorem 5 takes as input the number N of rounds devoted to the first phase. Given an a 2 1/2, by choosing any N [
we get bounds of At = Õ(T=) and V7 Ö( 9)).
11 The sampling of n. 1l according to d, can be done efficiently by a straightforward modification of the recursive procedure in Farina et al. 2021a b)

---

7.3 The lower bound frontier
We conclude by showing that the trade offs between Vi and Rr
achieved by Algorithm 2 are essentially tight. Previously, we provided an intuition as to why the algorithm needs to uniformly explore the entire tree of the SDM problem. Here, we provide a lower bound that corroborates such a statement. particular, the following theorem shows that, for any a E [1/2, 1]. in order to guarantce a sender's ss regret of the order ( it necessary to suffer a receiver's regret of the order of Q(T 12
Order of 15
Alazzker
Order Rr
Theorem 6. For any a E [1/2, 11, there exists a constant y (0, 1) such that no algorithm guarantees both Rr = oT( and
Figure 1: Trade-off between Rr and Vr in the bandit feedback.
VT o2/2 with probability greater than 7
Figure T shows on the horizontal axis the order of the term in Rr, while, on the vertical axis, it shows the order of the T in Vr. The shaded area over the blue line shows the achievable trade offs, while the marked red line shows the performances proved in Theorem [ Thus, we show that Algorithm 2 matches the lower bound for E [1/2, 2/3]. However, when [2/3, 1J. the guarantees proved Theorem diverge from the ones proved in the lower bound. This is due the N [ component in the receiver's regret that becomes dominant when 2/3. We conjecture that it is possible to reduce this term VN, hence matching the lower bound of Theorem The reason for such a gap between the lower and upper hounds is that, during the first phase, Algorithm 2 utilizes signaling schemes without taking into account their persuasiveness, thus incurring in large receiver's s regret during the first steps. We leave as future work addressing the question of whether it is possible to design exploration strategies by only using parroximaaely-perssasat signaling schemes.
References
Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 106(11): 3590-3605, 2016.
Itai Arieli and Yakov Babichenko. Private bayesian persuasion. Journal of Economic Theory, 182: 185-217, 2019.
Yakov Babichenko and Siddharth Barman. Algorithmic aspects of private Bayesian persuasion. In ITCS, 2017.
Martino Bernasconi, Federico Cacciamani, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Safe learning tree-form sequential decision making: Handling hard and soft constraints. In JCML 2022, volume 162, pages 1854-1873. PMLR, 2022.
Martino Bernasconi-de-LLuce Federico Cacciamani, Simone Fioravanti, Nicola Gatti, Alberto March- esi, and Francesco Trovò. Exploiting opponents under utility constraints sequential games, In NeurlPS 2021, pages 13177-13188, 2021.
Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy. Hardness results for signaling in bayesian zero-sum and network routing games. In EC, pages 479-496, 2016.
Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In EC, pages 234-247, 2012.
Ozan Candogan. Persuasion in networks: Public signals and k-cores. In EC, pages 133-134, 2019.
Matteo Castiglioni and Nicola Gatti. Persuading voters district-based elections. In AAAI, pages 5244-5251, 2021.
Matteo Castiglioni, Andrea Celli, and Nicola Gatti. Persuading voters: It's easy to whisper, it's hard to speak loud. In AAAI, pages 1870-1877, 2020a.
For a < 1/2, simple reduction from standard multi-armed bandit problem provides lower bound of S TT) both sender's regret Hr and receiver's regret Vr.
10

---

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. In NeurlPS, pages 16188-16198, 2020b.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Signaling in Bayesian network congestion games: the subtle power of symmetry. In AAAI, pages 5252-5259, 2021a.
Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online bayesian persuasion. In ICML, volume 139, pages 1314-1325, 2021b.
Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian persuasion meets mechanism design: Going beyond intractability with type reporting. In AAMAS 2022, pages 226-234, Interna- tional Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private bayesian persuasion with sequential games. AAAI, 14(02):1886-188, 886-1893, 2020a.
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. NeurlPS, 33:7722-77322 2020b.
Nicolo Cesa-Biance and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. arXiv preprint arXiv:2104.01520,
2021a.
Gabriele Farina, Robin Schmucker, and Tuomas Sandholm. Bandit linear optimization for sequential decision making and extensive-form games. AAAI, volume 35, pages 5372-5380, 2021b.
J Gan, Majumdar, G Radanovic, and Singla. Bayesian persuasion sequential decision-making. In AAAI, 2022.
Christopher J Hillar and Lek-Heng Lim. Most tensor problems np-hard. Journal of the ACM, 60 (6):1-39, 2013.
Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2615, 2011.
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Efficient computation of equilibria for extensive two-person games. Games and economic behavior, 14(2):247-259, 1996.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Dustin Morrill, Ryan D' D'Orazio, Reca Sarfati, Mare Lanctot, James R Wright, Amy R Greenwald, and Michael Bowling. Hindsight and sequential rationality of correlated play. In AAAI, volume 35, pages 5584-5594, 2021.
Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclosure means to security. In AAMAS, pages 645-653, 2015.
Bernhard Von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4): (000):0002000000 1022, 2008
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. arXiv preprint arXiv:2202.1067. 2022.
Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. Signaling in Bayesian Stackelberg games. In AAMAS, pages 150-158, 2016.
You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning persuade on the fly: Robustness against ignorance. In EC, pages 927-928, 2021.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The setting is based on precise
assumptions. If those assumptions are not met then our techiques are not applicable.
(c) Did you discuss any potential negative societal impacts your work? [N/A] Our work is mailny theoretical and thus the question does not apply.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] While all the main statements are contained in the main paper, all the proof are deferred to the appendix due to space constraints.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "k8zwiV66-Fz", "reviewer": "Reviewer_tcSK", "summary": "The authors study the problem of Bayesian persuasion (BP) with an unknown prior in the sequential decision making (SDM) problem. The traditional BP problem is as follows: a sender with knowledge of the outcomes of random events commits to a signaling scheme (i.e., a mapping from random states to action recommendations) before observing the outcome of the random event. The sender then signals according to their signaling scheme, and the receiver takes an action based on the signal. In the classic BP setting, the goal of the sender is to design an incentive compatible (persuasive) signaling scheme which maximizes their utility in expectation over the random event prior. In addition to being the first to study BP in the SDM setting, the authors consider the case in which the prior over random events is unknown. Since the prior is unknown to the sender, the authors study an online version of the problem in which a sequence of T receivers arrive one after another.\n\nFirst, the authors provide an (approximate) characterization of the set of persuasive signaling schemes via a polynomially-sized polytope. They show that using this polytope, the sender can compute the optimal signaling scheme by solving a polynomially-sized linear program when the prior is known. \n\nWhen the prior is unknown, the authors show that it is generally impossible to guarantee that a sequence of signaling schemes are persuasive with high probability. Because of this, they focus on the relaxed goal of ensuring that the cumulative receiver regret is sub-linear in the time horizon.\n\nThe authors provide a learning algorithm (Algorithm 1) for the full-feedback setting (i.e., the setting in which the sender is able to observe the realized outcome of all possible random events) which guarantees O(\\sqrt{T}) sender and receiver regret with high probability. Next, they build on their algorithm for full feedback to provide an algorithm for the bandit feedback setting (Algorithm 2). Under the bandit feedback setting, the sender only observes the terminal node which is reached at the end of the SDM problem. At a high level, the algorithm is split into two phases: an explore phase, which uses a uniform exploration policy to build an unbiased estimator of the prior, and an exploit phase, which uses the \"optimism in the face of uncertainty\" priniciple to minimize sender regret. Depending on how long the exploration phase runs for, there is a tradeoff between sender and receiver regret. However, the authors show that this tradeoff is tight for a large portion of the tradeoff frontier.", "questions": "What are some concrete examples of a situation in which a sender would have knowledge of the outcomes of the chance nodes of a SDM and would want to persuade a sequence of receivers?\n\nPoint of confusion: In the BP literature, there is usually an inherent misalignment between sender and receiver objectives. In the traditional BP setting with a known prior, this issue is addressed by using a signaling scheme which maximizes sender utility subject to the constraint that the receiver is incentivized to follow the sender's action recommendations. In this paper, the authors study a relaxed setting in which the sender wants to minimize receiver regret. Intuitively, why is there no tradeoff between sender and receiver regret, when this incentive mismatch between sender and receiver still exists? It feels like there should be some tension between minimizing sender and receiver regret, similar to the tradeoff which arises due to the exploration phase in Algorithm 2.", "limitations": "The authors adequately address the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe authors study a novel and mathematically interesting version of the Bayesian persuasion problem and provide a relatively complete set of results. Additionally, the presentation of the results is clear, and the technical details appear to be correct.\n\nWeaknesses: \nThe only real weakness I see is the lack of motivation. In the introduction, the authors motivate the general BP problem, but not the specific SDM setting they consider. Therefore, it is hard to gauge the significance of the authors' results. On one hand, if the problem of BP in SDMs can be well-motivated, I believe this paper is certainly worthy of acceptance. On the other hand, if the setting is not a realistic one in which persuasion may occur, the results may be mathematically interesting, but not very significant. For this reason I have given this submission a borderline accept, although I would be more than happy to raise my score if the authors can address my questions listed below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "efY37RwTJ97", "reviewer": "Reviewer_xoxk", "summary": "The paper studies a Bayesian persuasion problem in a setting in which the sender and receiver do not initially know the distribution/prior over random events, and must learn this distribution over time. The goal is to provide algorithms that are low regret for the receiver in this setting (assuming that the sender follows the recommendation) while guaranteeing that it is low regret for the sender to follow the recommendations of the algorithm.", "questions": "- Could there be other strategies for the receiver that yield similar or better regret, and is the author’s algorithm robust to such a chance in receiver behavior?\n\n", "limitations": "The paper does discuss the limitations of their current regret bounds and how they only seem tight for \\alpha < 2/3. The paper does not directly discuss potential harms, but I’m not sure whether the discussion of such harms is particularly relevant in a theory paper about Bayesian persuasion (it might be more suited to a paper that applies these techniques to a problem of practical interest). ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors consider a novel setting for signaling where the sender and receiver do not know the distribution of state of the world/random events in advance. I think this is an interesting and refreshing contrast from the standard (and often unrealistic) assumption that there is a commonly known prior\n- It is nice that the authors consider two types of feedback: a more informative full-feedback setting in which all random events are observed, versus a bandit-style feedback where we only receive information about the arms that we actually pull. \n- The results feel tight and complete: the paper both develops a low regret algorithm for persuasion but also show that the trade-off achieved by their algorithm is essentially tight/cannot be improved for non-trivial regimes of parameters \\alpha. \n\nWeaknesses:\n- The writing feels sometimes too formal and technical. I understand the authors want to give proper preliminaries for sequential decision making problems, but the formalism involved in describing SDMs in all their generality is heavy, and how it maps to/what the chance and decision nodes represent in the specific problem at hand only comes up on page 4. I think in this case it is avoidable and the main body of the paper can be written almost entirely in the simpler language of Section 3. Please let me know if I am wrong, but here it seems the SDM language may really only needed when it comes to showing technical results and could be moved to the appendix. \n- Back to the formalism, there are places in the paper where it could really benefit from some English/intuitive descriptions of some of the definitions. E.g., there are two very similar definitions of deviation policies with little explanation of how they differ from each other (I do understand after looking carefully at the definitions that the first one allows for deviations at several points/infosets of the algorithm while the single-point deviation is less general and can only deviate at a single, pre-specified infoset, but given the heavy-handed notations and formalism, this is a bit hard to parse)\n- The paper shows that it is sublinear regret for the receiver to follow the algorithms recommendations, showing that it is a good strategy for the receiver. It however is not clear to me that it implies that this is the only good strategy for the receiver, and the regret guarantees for the sender assumer the receiver always follows the recommendation. I think it might be worth highlighting and discussing this point a bit more, and it would be great (though probably out of scope) to have an algorithm for the sender that is robust to any no-regret algorithm the receiver may be using. \n\nOverall I think this is i) an interesting problem to look at where the sender and receiver do not have prior information about the distribution of “states of the world” and ii) comes with good regret bounds for both the sender and receiver with tight bounds for the sender, and so I believe the technical contribution of the paper warrants acceptance. However, I think clarity can be improved significantly here and the writing is really geared towards experts in sequential decision making and extensive form games and possibly a bit hard to understand otherwise. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bZAz91IIyGB", "reviewer": "Reviewer_xRVr", "summary": "The paper studies Bayesian persuasion between an informed sender and a\nreceiver in a sequetial decision making (SDM) setting. In contrast to\nstandard assumptions in the literature, the sender is uninformed of\nthe prior of the payoff relevant state, whereas the receiver is\nfarsighted. The paper designs an online-learning algorithm that\nattains no-regret for the sender (against the known-prior benchmark)\nwhile being persuasive for the receiver, where the latter criterion is\ndefined as a low-regret condition. The paper considers both the\nfull-feedback setting (where the sender observes all the random\nrealizations in the SDM decision tree, even off-path), and the bandit\nfeedback setting (where only the random realizations on the traversed\npath is observed by the sender). For the full-feedback setting, the\nauthors provide an algorithm that achieves $\\tilde{O}(\\sqrt{T})$\nregret for both the sender and the receiver. For the bandit-feedback\nsetting, the regret guarantees are somewhat weaker for both the sender\nand the receiver. ", "questions": "It might be helpful if the authors can motivate the repeated SDM\npersuasion problem through an application context. I don't expect an\nexact fit, but some examples would help in highlighting the\nsignificance of the problem.\n\nIs there a lower-bound characterization in the full-feedback setting?\n\nRepeating the comment above, in the full-feedback setting, if the\nsender can observe the *past* realizations on off-path chance nodes,\n*and* the randomness across chance nodes that are not\ndescendant-ancestor pairs are allowed to be correlated, then observing\nsuch *past* realizations can be beneficial to the sender. Does this\naffect the analysis?", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper considers an extension of Zu et al (2021) who consider the\nproblem of learning to persuade a receiver taking a single action at\neach time, when prior distribution is unknown. Here, the authors study\nthis problem in settings where the receiver has to make multiple\nsequential decisions at each time period (and the sender makes\nmultiple recommendations, at each information set of the receiver).\nUnlike Zu et al, the recommendations here need not be persuasive (and\nthe authors show that it may not be possible to achieve this); instead\nthe authors require that the receiver incurs low regret from following\nthe sender's recommendations. The authors propose a natural signaling\nalgorithm that achieves this notion of persuasiveness while at the\nsame time ensuring that the sender's regret is low.\n\nWhile the theoretical contribution is solid, the paper does not\nmotivate the specific applications of their model. In particular, the\nmodel requires that a single sender and a single receiver engage in\nrepeated sequential decision making (with iid noise) -- it is unclear\nto me where such an interaction might arise in an application. One may\nmotivate the repeated interaction as between a single sender and a\nstream of receivers (as in Zu et al), but then the no-regret version\nof persuasiveness for the receiver needs justification.\n\nFurthemore, the modeling assumptions about the sender's knowledge are\nunclear. For instance, I believe the paper assumes that the sender,\nwhen making a recommendation, observes the specific decision node of\nan information set reached by the receiver, but not the realizations\nof future randomness. It would be helpful to make this explicit. But\nmore importantly, in the full-feedback setting, if the sender can\nobserve the *past* realizations on off-path chance nodes, *and* the\nrandomness across chance nodes that are not descendant-ancestor pairs\nare allowed to be correlated, then observing such *past* realizations\ncan be beneficial to the sender. \n\nRelatedly, one would also need to make further assumptions about the\nsequence form prior, as current formulation may allow correlations at\nchance nodes that are not decendant-ancestor of each other. As\nmentioned above, this may be important for the full-feedback setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3-pAHCGJt75", "reviewer": "Reviewer_aKi3", "summary": "This paper studies bayesian persuasion where a farsighted receiver plays in a sequential decision making problem, and considers both full feedback and bandit feedback setting. The authors first proved a negative result that shows it is impossible to be persuasive without the knowledge of the prior. Then a relaxed online learning problem is considered, and the authors proposed algorithms that guarantee sub-linear regret for both the sender and the receiver.\n", "questions": "I'd appreciate it if the authors could help me interpret the result in this paper compared with the negative result for farsighted receiver in MDP in [17]. What is the key difference between the two problem settings that makes the problem in [17] NP hard, while the problem in this paper solvable in polynomial time?\n\nIs the trade-off between the regret of sender and receiver attained by Algorithm 1 optimal for the full feedback setting?", "limitations": "No.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of bayesian persuasion in sequential problem is well-motivated. However, prior works [17, 25] only consider myopic user. This paper is the first to propose algorithms for farsighted receiver in sequential decision making problem, which can be solved in polynomial time.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept