Online Bayesian Persuasion Without a Clue
Authors: Francesco Bacchiocchi
Matteo Bollini
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Bayesian Persuasion
Online Learning
Primary area: algorithmic_game_theory

Abstract: We study online Bayesian persuasion problems in which an informed sender repeatedly faces a receiver with the goal of influencing their behavior through the provision of payoff-relevant information. Previous works assume that the sender has knowledge about either the prior distribution over states of nature or receiver's utilities, or both. We relax such unrealistic assumptions by considering settings in which the sender does not know anything about the prior and the receiver. We design an algorithm that achieves sublinear---in the number of rounds T---regret with respect to an optimal signaling scheme, and we also provide a collection of lower bounds showing that the guarantees of such an algorithm are tight. Our algorithm works by searching a suitable space of signaling schemes in order to learn receiver's best responses. To do this, we leverage a non-standard representation of signaling schemes that allows to cleverly overcome the challenge of not knowing anything about the prior over states of nature and receiver's utilities. Finally, our results also allow to derive lower/upper bounds on the sample complexity of learning signaling schemes in a related Bayesian persuasion PAC-learning problem.

Online Bayesian Persuasion Without a Clue
Francesco Bacchiocchi
Matteo Bollini Politecnico Milano matteo. bollini @polimi iooliimi.ii .it
Politecnico di Milano
francesco. facchhoocci@@pol imi.
Matteo Castiglioni
Alberto Marchesi Politecnico Milano
Politecnico di Milano
matteo. wwwestiiiiioiioooommi.o.
alberto. www.meariiiiioo wtthhesspppmmmm....
Nicola Gatti
Politecnico di Milano
cola. wattaaagttp@pppmm.m..mmm
Abstract
We study online Bayesian persuasion problems in which an informed sender repeatedly faces a receiver with the goal of influencing their behavior through the provision of payoff-relevant information. Previous works assume that the sender has knowledge about either the prior distribution over states of nature receiver's s utilities, or both. We relax such unrealistic assumptions by considering settings in which the sender does not know anything about the prior and the receiver. We design algorithm that achieves sublinear-in the number of regret with respect to an optimal signaling scheme, and we also provide a collection of lower bounds showing that the guarantees of such an algorithm are tight. Our algorithm works by searching suitable space of signaling schemes in order to learn receiver's s best responses. To do this, we leverage non-standard representation of signaling schemes that allows to cleverly overcome the challenge of not knowing anything about the prior over states of nature and receiver's utilities. Finally, our results also allow to derive lower/upper bounds the sample complexity of learning signaling schemes in a related Bayesian persuasion PAC-Icarning problem.
1 Introduction
Bayesian persuasion has been introduced by Kamenica and Gentzkow [2011] to model how strategi- cally disclosing information decision makers influences their behavior. Over the last years, has received terrific attention in several fields of science, since it is particularly useful for understanding strategic interactions involving individuals with different levels of information, which are ubiquitous in the real world. As consequence, Bayesian persuasion has been applied in several settings, such online advertising [Emek et al. al.] 2014]] (Badnnidiyuuu et al.) 2018 Bacchiocchi al. 2022 and recommendation systems [Cohen and Mansour] (2019 Mansour et 2022 security [Rabinovich
Agrawal et al. 2023]] voting Alonso and Camara 2016 (Castiglioni et al.
Gattil 2021], traffic routing [Vasserman al. [015 Bhaskar et 2016 Castiglioni et al., 2021a],
al. 2015 Xu et 2016), e-commerce [Bro Miltersen and Sheffet [012 Castiglioni et al. 2022
medical research [Koootiin 2015). and financial regulation [Goldstein and Leitner 2018
In its simplest form, Bayesian persuasion involves sender observing some information about the world, called state of nature, and a receiver who has to take an action. Agents' utilities are misaligned, but they both depend on the state of nature and receiver's action. Thus, sender's goal devise
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

mechanism to (partially) disclose information to the receiver, so as to induce them to take a favorable action. This is accomplished by committing upfront to signaling scheme, encoding a randomized policy that defines how to send informative signals to the receiver based on the observed state.
Classical Bayesian persuasion models (see, e-g., (Dughmi and Xu 2016 2017 Xu 2020) rely on
rather stringent assumptions that considerably limit their applicability in practice. Specifically, they assume that the sender perfectly knows the surrounding environment, including receiver's utilities and the probability distribution from which the state of nature is drawn, called prior. This has motivated a recent shift of attention towards Bayesian persuasion models that incorporate concepts and ideas from online learning. with the goal of relaxing some of such limiting assumptions. However, existing works only partially fulfill this goal. as they still assume some knowledge of either the prior (see,
e.g., [Castiglioni et al. 2020b 2021b
2023 Babichenko et al., 2022. Bernasconi et al. 202.3 ) or
receiver's utilities (see, e.g. Zu et al.
2021 Bernasconi et al.
2022
Wu et al. 2022 Lin and
2025
1.1 Original contributions
We address-foo for the first time the best of our Saaellldee-Bayeeeeee persuasion settings where the sender has no clue about the surrounding environment. In particular, we study the online learming problem faced by a sender who repeatedly interacts with receiver over multiple rounds, without knowing anything about both the prior distribution over states of nature and receiver's s utilities. At each round, the sender commits to signaling scheme, and, then, they observe a state realization and send signal to the receiver based on that. After each round, the sender gets partial feedback, namely, they only observe the best-response action played by the receiver in that round. In such a setting, the goal of the sender is to minimize their regrel, which measures how much utility they lose with respect to committing to an optimal (i.e., miilit-maxximizing
signaling scheme every round.
We provide learning algorithm that achieves regret of the order of Ö(VT), where T is the number of rounds. We also provide lower bounds showing that the regret guarantees attained by our algorithm are tight in T' and in the parameters characterizing the Bayesian persuasion instance, ie., the number of states of nature d and that of receiver's actions n. Our algorithm implements a sophisticated explore- men-ccmmitt scheme, with exploration being performed in a suitable space of signaling schemes so as to learn receiver's 's best responses exactly. This is crucial to attain tight regret guarantees, and it is made possible by employing a nta-standard representation of signaling schemes, which allows to cleverly overcome the challenging lack of knowledge about both the prior and receiver's 's utilities.
Our results also allow us to derive lower/upper bounds on the sample complexity of learning signaling schemes in a related Bayesian persuasion PAC-learning problem, where the goal is to find, with high probability, an approximately-optima signaling scheme in the minimum possible number of rounds.
1.2 Related works
Castiglioni et al. 2020b were the first to introduce online learning problems in Bayesian persuasion scenarios, with the goal of relaxing sender's knowledge about receiver's 's utilities (see also follow-up works [Castiglioni et al. 2021b] 2023 Bernasconi et al. (023)). In their setting, sender's 's uncertainty modeled by means of an adversary selecting receiver's rype each round, with types encoding information about receiver's utilities. However, in such a setting, the sender still needs knowledge about the finite set of possible receiver's types and their associated utilities, as well as about the prior.
parallel research line has focused on relaxing sender's knowledge about the prior. Zu et al. 2021 study online learning consider the sender's 's learning problem of issuing persuasive action recommendations (corresponding to signals in their case), where persuasiveness about correctly incentivizing the receiver actually follow such recommendations. They provide an algorithm that attains sublinear regret while being persuasive at every round with high probability, despite having no knowledge of the prior. /uu et al.) [2022) Gan et al. 22023), Bacchiocchi et al. (2024c) achieve similar results for Bayesian persuasion in episodic Markov decision processes, while Bernasconi et al. [022 in non-Markovian environments. All these works crucially differ from ours, since they strongly rely on the assumption that receiver's utilities are known to the sender, which is needed in order to meet persuasiveness requirements. As a result, the techniques employed in such works are fundamentally different from ours well.
repeated version of Bayesian persuasion. Differently from this paper, they
2

---

Finally, learning receiver's 's best responses exactly (a fundamental component of our algorithm) is
related to learning Stackelberg games [Letchford et al. 2009 Peng et al.) 2019 Bacchiocchi et
2024a]. For more details on these works and other related works, we refer the reader to Appendix A
2 Preliminaries
In Section 2.] we introduce all the needed ingredients of the classical Bayesian persuasion model by Kamenica and Gentzkow (201T), while, in the following Section 2.2. we formally define the
Bayesian persuasion setting faced in the rest of the paper and its related online learning problem.
2.1 Bayesian persuasion
A Bayesian persuasion instance is characterized by finite set θ == {0 1 of d states of nature and a finite set A = {a, )/= of n receiver's s actions. Agents' payoff's are encoded by utility functions u, u²: ④ x A + [0, 1]. with (a) == u(8, a), respectively ug == u (6, a), denoting the payoff of the receiver, respectively the sender, when action a E A is played state 0 E O. The sender observes state of nature drawn from commonly-knowe prior probability distribution μ E int(Ae) ) with (50 E (0, 1] denoting the probability of 0 E O. To disclose information about the realized state, the sender can publicly commit upfront to signaling scheme $ θ - As, which defines a randomized mapping from states of nature to signals being sent to the receiver, for a finite set of signals. For ease of notation, we let dg (0)) be the probability distribution over signals prescribed by á when the the sate of nature is 0 E O, with (s) E [0, 1] denoting the probability of sending signal s E S.
The cender-receiver interaction goes as follows: (1) the sender commits to signaling scheme Φ; (2) the sender observes a state of nature 9 ~ 1 and sends a signal s ~ de to the receiver; (3) the receiver updates their belief over states of nature according to Bayes rule; and (4) the receiver plays best-response action a E A, with sender and receiver getting payoffs ua(a) and ua)a,, respectively. Specifically, an action is best response for the receiver if it maximizes their expected utility given the belief computed in step (3) of the interaction. Formally, given a signaling scheme Φ : e + As and signal E S, we let (s) S A be the set of receivers' best-response actions, where:
(s) = a; E A
Σ BE0
2ode N Σ (o0o Vaz E EA )
(I)
As customary in the literature on Bayesian persuasion (see, e.g., Dughmi and Xu 20166), we assume that, when the receiver has multiple best responses available, they break ties in favor of the sender. In particular, we let a (s) be the best response that is actually played by the receiver when observing signal s E under signaling scheme o with a (s) E arg (aA(s) Eoeo Mo00 (s))(())((()))
The goal of the sender is commit to an optimal signaling scheme, namely, ó ② - As that maximizes sender's ' expected utility, defined as (²)) = Eves Eoco Made (a) (s)). In the following, we let OPT := max u² (Φ) be the optimal value of sender's 's expected utility. Moreover, given additive error 7 (0, 1), we say that signaling scheme is 7-optimal if u² (d()) OPT
2.2 Learning in Bayesian persuasion
We study settings in which the sender repeatedly interacts with the receiver over multiple rounds, with each round involving a one-shot Bayesian persuasion interaction (as described in Section 2.T). We assume that the sender has no knowledge about both the prior μ and receiver's es utility u, and that the only feedback they get after each round is the best-response action played by the receiver.
At each round f [ the sender commits to a signaling scheme Φ; θ + As and observes a state of nature 6' ~ ju. Then, they draw a signal s ~ Φ2.0 and send it to the receiver, who plays a best-response action a' == a (s"). Finally, the sender gets payoff uł = u (a') and observes a feedback consisting in the action a' played by the receiver. The goal of the sender is learn how to maximize their expected utility while repeatedly interacting with the receiver. When the
I GGiven a finite set X, we denote by Ax the set of the probability distributions over X. We denote by in] = (L...., n2 the set of the first N natural numbers.
3

---

sender commits to sequence {őr he of signaling schemes, their performance over the T rounds measured by means of the following notion of cumulative (Stackelberg) regret.
T
Br((óthen)) = = OPT E
u (o))
where the expectation is with respect to the randomness of the algorithm. In the following, for ease of notation, we omit the dependency on {Ør hejz from the cumulative regret, by simply writing Rt- Then, our goal is to design no-regret learning algorithms for the sender, which prescribe a sequence of signaling schemes of that results in the regret Ri growing sublinearly in T, namely Rr = o(T).
Warm-up: A single signal is all you need
In order to design learning algorithm in Section 4 exploit a non-standard representation of signaling schemes, which we introduce in this section. Adopting such a representation is fundamental to be able to learn receiver's best responses without any knowledge of both the prior μe and receiver's utility function u. The crucial observation that motivates its adoption is that receiver's best responses (s) only depend the components of & associated with s 8, namely (o))) for 0 O. Thus, in order to learn them, it is sufficient to learn how a varies function of such components.
The signaling scheme representation introduced this section revolves around the concept of slice. Definition 1 (Slice). Given signaling scheme O As. the slice of with respect signal 8 E S is the d-dimensional vector x E [0, 1]d with components Dg == de for 0 E G.
In the following, we denote by X = [0, 1j4 the set of all the possible slices of signaling schemes. Moreover, we let X be the set of normalized slices, which is simply obtained by restricting slices to lie in the (d - dimeennsiaa simplex. Thus, it holds that x = E [0, 1]d Eece Zg = 1}.
Next, we show that receiver's actions induce particular coverings of the sets A and X', which also depend on both the prior y and receiver's utility u. First, we introduce Hij C R to denote the halfspace of slices under which action a; A is (weakly) better than action aj E A for the receiver.
(mr)
X (as)
X (ai)
(az)
(1,)
Hig = x E Rdd
Exopo (ao(a;)- - AEE
(o0s)-uo(0)) ua())) 20
(0s)
Moreover, we denote by Hij == JHyy the hyperplane constituting the boundary of the halfspace Haj. which we call the separating hyperplane between actions a; and az Then, for every a, E A, introduce the polytopes (a:))) 2 and (as) C X4:
Figure 1: Representation sets X (a:) and X (a:) for instance with d = 2 states of nature and n = 3 receivers' actions.
x²aa):= = =0
His ayEA:araaa
and (a:) = X n
N
His
aaEAAaaaaa;
Clearly, the sets (a;),, respectively X (a;) define a cover of 2 respectively A Intuitively, the set (a;) encompasses all the slices under which action a; is best response for the receiver. The set x² (a,) has the same interpretation, but for normalized slices. Specifically, x E (a,(a,)) is slice of & with respect E S, then a; E (s).. Notice that slice n may belong more for signaling schemes á having
than one polytope XL (a:), when it is the case that [**(s)
We let 8H he the boundary hyperplane of halfspace H C Rd. Notice that H, and H actually refer to the same hyperplane. In this paper, we use both names for ease of presentation.
'In this paper, given polytope P C RR we let V(P) be its set of vertices, while denote by vol (P) its Lehesgue measure in m dimensions. For ease of notation, whenever m Moreover, we int(P) be the interior dimension. In the case of polytopes x (a:). the (d dimdennsion simplex is one of such subspaces.
we simply write vol(P). relative a subspace that fully contains P. and has minimum

---

as slice with respect to s E S In order to denote the best-response action actually played by the receiver under a slice æ E X² we introduce the symbol a(x), where a(x) == a (s) for any & having as slice with respect s E S. Figure depicts an example of the polytopes (a:) and (a,)) in order to help the reader to grasp more intuition about them.
A crucial fact exploited by the learning algorithm developed in Section + is that knowing the separating hyperplanes Hij defining the polytopes (a:) of normalized slices is sufficient to determine optimal signaling scheme. Indeed, the polytopes (a,);) of unnormalized slices can be easily reconstructed by simply removing the normalization constraint Ense To = 1 from X (n:). Furthermore, as we show in Section | (see the proof of Lemma 4 in particular), there alway exits an optimal signaling scheme using at most one slice x E (a) for each receiver's action a E A.
We conclude the section with some remarks that help to better clarify why we need to work with signaling scheme slices in order to design our learning algorithm in Section 4
Why we need slices for learning The coefficients of separating hyperplanes Hij are products between prior probabilities 140 and receiver's utility differences up un(a;) uo(a)) In order to design no-regret learning algorithm, it is fundamental that such coefficients are learned exactly, since even an arbitrarily small approximation error may result in "missing" some receiver's 's best responses, and this may potentially lead to a large loss in sender's ' expected utility (and, in its turn, to large regret). As result, any naive approach that learns the prior and receiver's payoff's separately is deemed to fail, as it would inevitably result in approximate separating hyperplanes being learned. Operating in the space of signaling scheme slices crucially allows to learn separating hyperplanes exactly. As we show in Section[4 4 it makes it possible to directly learn the coefficients of separating hyperplanes without splitting them into products of prior probabilities and receiver's 's utility differences.
Why we need normalized slices One may wonder why we cannot work with (unnormalized) slices in X rather than with normalized ones in X Indeed, we show in Section 4 our procedure to learn separating hyperplanes crucially relies on the fact that we can restrict the search space to a suitable subset of the (d dimeenssiol simplex. This makes it possible to avoid always employing a number of rounds exponential in d, which would lead to non-tight regret guarantees.
Why not working with posteriors In Bayesian persuasion, it is oftentimes useful work in the space of posterior distributions induced by sender's 's signals (see, e.g., [Castiglioni et al. 2020b)). These are the beliefs computed by the receiver according to Bayes rule step (3) of the interaction. Notice that posteriors do not only depend on the signaling scheme é and the sent signal s S, but also on the prior distribution μ., Indeed, the same signaling scheme may induce different posteriors for different prior distributions. Thus, since in our setting the sender has no knowledge of μu, we cannot employ posteriors. Looking at signaling scheme slices crucially allows us to overcome the lack of knowledge of the prior. Indeed, one way of thinking of them is as "prior-free" posterior distributions.
4 Learning to persuade without a clue
In this section, we design our no-regret algorithm (Algorithm Tp. We adopt a sophisticated explore- then-commit approach that exploits the signaling scheme representation based slices introduced in Section 3) Specifically, our algorithm works by first exploring the space X' = X of normalized slices in order to learn satisfactory "approximations" of the polytopes X' X(.))) == X' (a:) exploits them in order to compute suitable approxinately-opimme signaling schemes to be employed in the remaining rounds. Effectively implementing this approach raises considerable challenges.
- Then,
The first challenge is that the algorithm cannot directly "query" a slice æ E X to know action a(z). as it can only commit to -slecifeee signaling schemes. Indeed, even if the algorithm commits to a signaling scheme including the selected slice x E X. the probability that the signal associated with x is sent depends on the (unknown) prior, it is equal to Esce 1028- This probability can be
'Let us remark that, in this paper, we assume that there are no two equivalent receiver's 's actions a; A a, E A such that (a.) ua(a,) for all 0 E O. Thus, slice can belong more than one polytope only if it lies on some separating hyperplane. This assumption is w.l.o.g. g. since it possible account for equivalent actions by introducing at most n additional separating hyperplanes to consider tie breaking in favor of sender. "n the rest of the paper, for ease of notation, we write X' and (a.) instead of x and x (ai).
5

---

arbitrarily small. Thus, in order to observe a(x), the algorithm may need to commit to the signaling scheme for an unreasonably large number of rounds. To circumvent this issue, we show that it is possible to focus on a subset X C X' of normalized slices "inducible" with at least suitably-defined probability e E (0, 1). Such set X, is built by the algorithm in its first phase.
The second challenge that we face is learning the polytopes X. (a:) == ((,)) n X. This is done by means of eeeeoleallyinvoolved procedure that learns the separating hyperplanes Hij needed to identify them. This procedure is an adaptation to Bayesian persuasion settings of an algorithm recently introduced for similar problem in Stackelberg games [Bacchiocchi et al., 2024a].
Finally, the third challenge is how to use the polytopes X. (a,) to compute suitable approximately- optimal signaling schemes to commit to after exploration. We show that this can be done by solving an LP, which, provided that the set X, is carefully constructed, gives signaling schemes with sender's expected utility sufficiently close to that of an optimal signaling scheme.
The pseudocode of our no-regret learning algo- rithm is provided in Algorithm [ In the pseu- docode, we assume that all the sub-procedures have access to the current round counter 6, all the observed states of nature 8², and all the feed- backs a', u, received by the sender Moreover, in Algorithm [and its sub sub-procedures. we use T4 E Ae to denote the prior estimate any round f > 1, which is a vector with compo- nents defined as i4..0 == (t - 1) for 0 O where No, E N denotes the number of times that state of nature t (excluded). Algorithm divided into three phases. In phase 1, the algo- rithm employs the Build- ch- pro- cedure (Algorithm 2 to build a suitable subset
Algorithm 1
Require: TEN N 1: 8
1/T, ( + 1/T
/Brud
2: E +
VT
3: Ti +
12
log (8)
4: 1++
5: X, + Build- SppaarccSSppceTTi. c)
6: R. + Sond-Polytopes(X.... ()
7: while t - T do
observed up to round
8:
Φ < SrmmptteSSggalinn'AP
Ne, Tt)
D can be conceptually
9:
Commit to 6r. observe H', and send 8
Observe feedback at and receive uf;
11:
Compute prior estimate Pi+1
12:
t+
X. S. X of "inducible" normalized slices. Then, in phase 2, the algorithm employs the Polytooyysses procedure (see Algorithm 6 in Appendix E
to find collection of polytopes R = (a) (.) where each RR (a) is either (a) or a suitable
subset of (a) that is sufficient for achieving the desired goals (see Section 4.2 Finally, phase 3
uses the remaining rounds to exploit the knowledge acquired in the preceding two phases. Specifi-
cally, at each t, this phase employs the Compute- -i Signalinniinnnn ing procedure (Algorithm 3 to compute an approximately-opting
signaling scheme, by using R., the set Xx, and the current prior estimate fia.
In the rest of this section, we describe in detail the three phases of Algorithm I bounding the regret attained by each of them. This allows us to prove the following main result about Algorithm
Theorem 1. The regret attained by Algorithm 7 is RT S (n"
We observe that the regret bound in Theorem I has an exponential dependence on the number of states of nature d and the number of receiver's actions n, due to the binomial coefficient. Indeed, when d. respectively n, is constant, the regret bound is of the order of ((nVT)) respectively ((d' Such dependence is tight, as shown by the lower bounds that we provide in Section 5
4.1 Phase 1: Build-Search-Sperr
Given an E (0, 1/0a) and number of rounds Ti, the Build-Search-Space procedure (Algo- rithm 2) computes a subset X. C X' of normalized slices satisfying two crucial properties needed by the learning algorithm attain the desired guarantees. Specifically, the first property is that any slice x E X. can be "induced" with sufficiently high probability by a signaling scheme, while the
'Nticee that, in Algorithm| I the sub-procedures Build-Search-Spere and Find-Polytopes perform some rounds of interaction, and, thus, they update the current round counter t. For ease of presentation, we assume that, whenever > T', their execution immediately stopped (as well the execution of Algorithm I]. "Notice that the regret attained by Algorithm 66 (stated in Theorem complexity of numbers (a.)) Le.. the number of bits required to represent them. We refer the reader to Appendix B for more details about how manage the bit-complexity of numbers in this paper.
depends on B. which is the bit-

---

second one is that, if & Xe, then signaling schemes "induce" such a slice with sufficiently small probability. Intuitively, the first property ensures that is possible to associate any x X, with the action a(x) in a number of rounds of the order of 1/c, while the second property is needed to bound the loss in sender's expected utility due to only considering signaling schemes with slices in X,
Algorithm works by simply observing realized states of nature 0$ for Ti rounds, while commit- ting to any signaling scheme meanwhile. This
Algorithm 2 Build-Search-Space
Require: 6E 1/6),, number of rounds Ti
allows the algorithm build sufficiently accu- rate estimate f of the true prior μ.. Then, the al- gorithm uses such an estimate to build the set X. Specifically, it constructs X, as the set contain- ing all the normalized slices that are "inducible"
1:
θ
+ Ø
2:
while / S T2 do
3:
Commit to any Φ1, observe 8¹, and send s
4: Observe feedback af and receive un
5:
t 1
with probability at least 2e under the estimated
6: Compute prior estimate 7r
prior çt, after filtering out all the states of nature whose estimated probability is not above the 2e threshold (see Lines 10 in Algorithm 2).
7: Ø + P4
8: for E do
9: ji > 2e then Ô - ŌU( (0)
The following lemma formally establishes the two crucial properties that are guaranteed by Algorithm 2 as informally described above.
10: X. t {I E X I Mexe 2 2
11: return X.
1 Lemma 1. Given T1 == 12 log (24/)) and e E (0. 1/6d), Algorithm 2 employs T1 rounds and terminates with set X, C X such that, with probability at least - 5: (i) Loee PoTg 2 e eforr every
slice x E Xg and (ii) Eoee Mazza S for every slice x E XX Xee
To prove Lemma D we employ the multiplicative version of Chernoff bound, so as to show that it possible to distinguish whether prior probabilities μı are above or below suitable thresholds in number of rounds of the order of l/e. Specifically, we show that, after Ti rounds and with probability
at least 1 - 6, the set θ in the definition of X. does not contain states f O with μ4 S while it contains all the states with a sufficiently large μ4g. This immediately proves properties (i) and (ii) in Lemma T Notice that using a multiplicative Chernoff bound is necessary technicality, since standard concentration inequalities would result in a number of needed rounds of the order of 1/e, leading to suboptimal regret bound in the number of rounds T.
For ease of presentation, we introduce the following clean event for phase of Algorithm | This encompasses all the situations in which Algorithm outputs set X, with the desired properties. Definition (Phase clean event). & is the event in which X, meets properties (i)- in Lemma
4.2 Phase 2: Find-Polytopes
Given set X, C X computed by the Seaddd-erch-Spaaeee procedure and ( E (0, as inputs, the Find-Polytopes procedure (Algorithm Gi Appendix E) computes a collection R. == (Re(a))ar of polytopes enjoying suitable properties sufficient to achieve the desired goals.
Ideally, we would like R. (a) = X. (a) for every a E A. However, it is not possible to completely identify the polytopes (a) with vo)() O. Indeed, if vol(X, = O. then (a;) C (a,))) for some other polytope X. (a,) with positive volume. Thus, due to receiver's 's tie breaking, it could be impossible to identify the whole polytope X, (a,). As result, the Find-Polytoper procedure can output polytopes (a) = Xa) only if vol (a)) > O. However, we show that, if vol(XX, (a) = it is sufficient to guarantee that the polytope R. (a) contains a suitable subset (a of the vertices of (a); specifically, those in which the best response actually played by the receiver is a. For every A, such set is formally defined as (a) = {ar (a)( alx)) = a}. Thus, we design Find-Polytoper so that it returns a collection R. = (R. of polytopes such that:
(i) if it holds (a) > 0, then = (a). while (ii) if vol( = O. then (a) is (possible improper) face of X, (a( with Va(a) S R.).).
As a result each polytope R, (a) can be either X, (a) or a face of X. (a), or it can be empty, depending on receiver's tie breaking. In all these cases, it is always guaranteed that V, (a( (a).
To achieve its goal, the Pind-Polytopes procedure works by searching over the space of normalized slices X,, so to learn exactly all the separating hyperplanes Hij characterizing the needed vertices.
7

---

The algorithm does so by using and extending tools that have been developed for related learning problem in Stackelberg games (see [Bacchiocchi et al. 2024a]). Notice that our Bayesian persuasion setting has some distinguishing features that do not allow us to use such tools off the shelf. We refer the reader to Appendix [
for a complete description of the Find-Polytopes procedure.
A crucial component of Find-Polytopes is tool to "query" a normalized slice x E X. in order to obtain the action a(x). This is done by using sub-procedure that we call action-Oracio (see Algorithm 5 in Appendix D. which works by committing to a signaling scheme including slice x until the signal corresponding to such a slice actually sent. Under the clean event &,, the set X, is built in such way that action-Oracle returns the desired action a(x) in number of rounds of the order of 1/c, with high probability. This is made formal by the following lemma.
Lemma 2. Under event El, given any P (0,1) and normalized slice E Xe, if the sender commils to a signaling scheme @ θ - S = {81,82) 823 such that @u(81) ) - va for all E O during log(1/>) rounds, then, with probability at least 1 1-p p. signal 81 is sent at least once.
q q=
Notice that the signaling scheme used to "query" an x E X. only employs two signals: one is associated with slice x, while the other crafted so as to make the signaling scheme well defined.
The following lemma provides the guarantees of Algorithm Appendix E
Lemma 3. Given imputs X, S X and ( E (0, 1) for Algorithm o let L:= B B. + Bj. where B, Be, and By denote the bil-complexity of numbers paug (as), 6, and ft, respectively. Then, under event Er and with at probability at least 1 <. Algorithm 6 outputs a collection R. == =RR (a)]EAA where R. (a) is a (possibly improper) face of Xe(a) such that (a S (d)) in number of rounds T2:
n2
(dFL (d+1) d
)
Tr S Ö
log"
For ease of presentation, we introduce the clean event for phase 2 of Algorithm defined as follows: Definition 3 (Phase clean event). &g is the event in which V. (a( (a.(a) for every a E A.
4.3 Phase 3: Compute Cumpute-Signliing
Given the collection of polytopes R. = and an estimated prior Th E Ag. the Compute-Signall procedure (Algorithm 3 outputs an approximately-opimall signaling scheme by solving an LP (Program in Algorithm
returned by the Hind-Polytopes procedure
Program 2 maximizes an approximated version of sender's expected utility over a suitable space of (partially-specifeed signaling schemes. These are defined by tuples of slices (x*) contain- ing an (unnormalized) slice x E (a) for every receiver's action a A. The objective function being maximized by Program 2 accounts for the sender's ' approximate utility under each of the slices x², where the approximation comes from the esti- mated prior Pr. The intuitive idea exploited by the LP formulation is that, under slice z", the receiver always plays the same action a as best response, since a ((x:)) ) holds by the way in which (a) is constructed by Find-Polyya Find-Polytopes. In particular, each polytope (a) is built so as to include all the unnormalized slices corresponding to the nor- malized slices in the set R. (a). Formally, for every receiver's action a E A, it holds:
Algorithm 3 Compute-Signalinn
Require: R. [R. (a)) Ne, p. Ae 1: Solve Program 2 for x- = (x*:")EE
max Σ Σ
Pr. un (a) s.t. (2)
(x" aEA BEE
x² E (a)
Va A
Σ x <1
AA E
aEA
2: S + ( (8 |
3: for E e do
4: Φo (o((5)) = = +aa
Va E A
(0o(s*) 11 -EEE 2/
5: return
(a) == {a E X x= ax' A (a( E (0, 1]) U (0).
where 0 denotes the vector of all zeros in Rd. We observe that, since the polytopes R. (a) are constructed as the intersection of some halfspaces Hl and Xe, it is possible to easily build polytopes (a,).) by simply removing the normalization constraint Eece Zg = 1. Notice that, if (a) Ø, then (a) {0), which implics that action is never induced as a best response, since x 0.
8

---

After solving Program for an optimal solution x² == (x*:")eE Algorithm 3 employs such a solution to build a signaling scheme ø. This employs signal s" for every action E A, plus an additional signal 8", namely& S = {s*) [ E A). Specifically, the slice of & with respect to 8 set to be equal to x", while its slice with respect to s* set so as to render Φ a valid signaling scheme (i.e., probabilities over signal sum to one for every 0 E )). Notice that this is always possible thanks to the additional constraints EneA z I 1 in Program (2). Moreover, such a slice may belong to X \ x.. Indeed, in instances where there are some (a) falling completely outside X²,. this is fundamental to build a valid signaling scheme. Intuitively, one may think of 8* as incorporating all the "missing" " signals in Φb namely those corresponding to actions a A with (a) outside X.
The following lemma formally states the theoretical guarantees provided by Algorithm
Lemma 4. Civen inputs R. == (Re(a)) Xe, and tee E for Algorithm 3 under events E1 and Eg, the signaling scheme b output by the algorithm is ( + v) -optimal S <EEe Me,e He
In order to provide some intuition on how Lemma is proved, let us assume that each polytope X, (a) is either empty or has volume larger than zero, implying that R. (a) X. (a). In Appendix D we provide the complete formal proof of Lemma 4 working even with zero-measure non-empty polytopes. The first observation the we need is that sender's expected utility under signaling scheme á can be decomposed across its slices, with each slice æ providing a utility of LAEo per (a(x)). The second crucial observation is that there always exists an optimal signaling scheme o² that direct and persuasive, which means that 6* employs only one slice x" for each action a E A, with being a best response for the receiver under x". is possible show that the slices x that also belong to Xe can be used to construct a feasible solution to Program 2 since x E (a)(a) by definition. Thus, restricted to those slices, the signaling scheme computed by Algorithm3aachn Jachievs an approximate sender's ' expected utility that is greater than or equal to the one achieved by o- Moreover, the loss due to dropping the slices that are not X, can bounded thanks to point (ii) in Lemma Finally, it remains to account for the approximation due to using tú instead of the true prior in the objective of Program 2 All the observations above allow to bound sender's expected utility loss as in Lemma
Lower bounds for online Bayesian persuasion
In this section, we present two lower bounds on the regret attainable in the setting faced by Algorithm I| The first lower bound shows that an exponential dependence in the number of states of nature d and the number of receiver's actions n is unavoidable. This shows that one cannot get rid of the binomial coefficient in the regret bound of Algorithm Srrrithmmprrvviiiie provided in Theorem [
Formally:
Theorem 2.
For any sender's algorithm, there exists a Bayesian persuasion instance in which d 2 and the regret Rr suffered by the algorithm is at least (d) or. equivalently, 20(n)
Theorem 2 is proved by constructing collection of Bayesian persuasion instances in which an optimal signaling scheme has to induce the receiver to take an action that a best response only for a unique posterior belief (among those computable by the receiver at step (3) of the interaction). This posterior belief belongs to a set of possible candidates having size exponential in the number of states of nature d. As result, in order to learn such a posterior belief, any algorithm has to commit to number of signaling schemes that is exponential in (and, given how the instances are built, in n).
The second lower bound shows that the regret bound attained by Algorithm i tight in T.
Theorem 3. For any sender's algorithmm, there exists Bayesian persuasion instance in which the regret Ro suffered by the algorithm is at least M( (VVT).
To prove Theorem 3 we construct two Bayesian persuasion instances with θ = (01, 02) such that, in the first instance, 140, is slightly greater than pe,, while the opposite holds in the second instance. Furthermore, the two instances are built so that the sender does not gain any information that helps to distinguish between them by committing to signaling schemes. As a consequence, to make a distinction, the sender can only leverage the information gained by observing the states of nature realized at each round, and this clearly results in the regret being least Ω2 Q(vT))

---

6 The sample complexity of Bayesian persuasion
In this section, show how the no-regret learning algorithm developed in Section can be easily adapted to solve a related Bayesian persuasion PAC-learning problem. Specifically, given an (additive) approximation error 7 E (0, 1) and a probability 7) (0, 1), the goal of such a problem 7-optimal signaling scheme with probability at least - 7), by using the minimum possible number of rounds. This can be also referred as the sample complexity of learning signaling schemes.
learn
As in the minrett-iniiiztioon problem addressed in Section we assume that the sender does not know anything about both the prior distribution μ and receiver utility function u.
We tackle the Bayesian persuasion PAC-learning problem with a suitable adaptation of Algorithm]] 1 provided in Algorithm 4 The first two phases of the algorithm follow the line of Algorithm [ with the pro-
Algorithm PAC-Persuasioonnwoorr
Require: E (0, (0,1)
I: 8 t- n/2, + 7/2, 61 + 7/12nd, t <-
and Hind-Polyyoope cedures being called for suitably-defined parameters e. 6, Tı. and Ç (taking different values with respect to their counterparts in Algorithm[[] []. In particular, the value of e depends on y and is carefully computed so to control the bit-complexity of numbers used in the Find-Polytoper procedure (see Lemma 33) as detailed in Appendix G Finally, in its third phase,
Build-Search-Spe
2: 6 f Compute-Epsilon(S
3: T1 + 2 log (2))
4: X, + Build-Search-Space[[T
R. Find-Polytopes((1, ()
6: Φ f Compute- Siiite--iggaall ing R. Ne, P))
return Φ
the algorithm calls Seppuute-Signaiiii ing to compute a signaling scheme & that can be proved to y-optimal with probability least 1 T).
The most relevant difference between Algorithm 7 and Algorithm is the number of rounds used to build the prior estimate defining X. Specifically, while the latter has employ Ti of the order of 1/- and rely on a multiplicative Chernoff bound to get tight regret guarantees, the former has to use Ti of the order of 1/2² and standard concentration inequalities to get an ((e)-optimal solution. Formally:
Lemma 5. Given Ti = 2 log (24/8) and e E (0, 1), Algorithm 2 employs Ti rounds and outputs X. S X such that, with probability at least 1 - 8: (i) Eoco Haag 2 for every slice x E Xe, (ii) Eoce MoIT S Ge for every slice x E X \ X., and (iii) [Pg uel I cfor every 0 E E.
By Lemma 5 it is possible to show that the event 8d holds. Hence, the probability that a signaling scheme including slice X, actually "induces" such slice is at least and, thus, the results concerning the second phase of Algorithm Tare valid also in this setting. Finally, whenever the events & and &g hold, we can provide upper bound the number of rounds required by Algorithm to compute a y-optimal signaling scheme as desired. Formally:
Theorem 4. Given 7 E (0, 1) and 1 E (0,1), 1), with probability least 1 17, Algorithm 4 outputs 7-optimal signaling scheme in a number of rounds T such that:
T S δ
n
log?
( ( a
d (d+n
d
We conclude by providing two negative results showing that the result above is tight.
Theorem 5. There exist two absolute constants K, X such that no algorithm is guaranteed to return a s-optimal signaling scheme with probability of at least 1 X by employing less than 20()) and 200) rounds, even when the prior distribution js is known to the sender.
Theorem 6. Given E (0, 1/s) and E (0, 1), no algorithm is guaranteed to return y-optimal signaling scheme with probability at least 1 by employing less than 52( 2 (og()))) rounds.
In Appendix H
we also study the case in which the prior μ is known to the sender. In such a case, we show that the sample complexity can be improved by a factor 1/7, which is tight.
Acknowledgments
This work was supported by the Italian MIUR PRIN 2022 Project "Targeted Learning Dynamies: Computing Efficient and Fair Equilibria through No-Regret Algorithms", by the FAIR (Future
10

---

Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR- PE-AI scheme (M4C2. Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AT for Sustainability, No. 101 120237). This work was also partially supported by project SERICS (PF00000014) under the MUR National Recovery and Resilience Plan funded by the European Union NextGenerationEU. Francesco Bacchiocchi was also supported by the G-Research November Grant.
References
Shipra Agrawal, Yiding Feng, and Wei Tang. Dynamic pricing and learning with bayesian persuasion. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 59273-59285, 2023.
Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 2016.
Yakov Babichenko, Inbal Talgam- Cohen, Haifeng Xu, and Konstantin Zabarnyi. Regret-minimizing Bayesian persuasion. Games and Economic Behavior, 136:226-2444 2222, 2022. ISSN 0899-88266
Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Giulia Romano, and Nicola Gatti. Public signaling Bayesian ad auctions. In IJCAI, 2022.
Francesco Bacchiocchi, Matteo Bollini, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. The sample complexity of Stackelberg games. arXiv preprint arXiv:2405.06977, 2024a.
Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning optimal contracts: How to exploit small action spaces. In The Twelfth International Conference on Learning Representations, 2024b.
Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Markov persuasion processes: Learning to persuade from scratch. arXiv preprint arXiv:2402.03077, 2024c.
Ashwinkumar
Badanidiyuru, Kshipra Bhawalkar, and Haifeng Xu. Targeting and signaling in ad auctions. In Proceedings of the Twenty-Ninth Anmual ACM-SIAM Symposium on Discrete Algorithms, 2018.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34:25799-25811, 2021.
Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: Learning to persuade in the dark. In Advances in Neural Information Processing Systems, volume 35, pages 15917-15928, 2022.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovò, and Nicola Gatti. Optimal rates and efficient algorithms for online Bayesian persuasion. In Proceedings of the 40th International Conference on Machine Learning, pages 2164-2183, 2023.
Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy. Hardness results for signaling in bayesian zero-sum and network routing games. In EC, 2016.
Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In EC, 2012.
Modibo K. Camara, Jason D. Hartline, and Aleck Johnsen. Mechanisms for no-regret agent: Beyond the common prior. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 259-2700 2020.
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 to whisper, it's hard to speak loud. In AAAI, 2020a.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. Advances in Neural Information Processing Systems, 33:16188-1 188-16198, 2020b.

---

Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Signaling in Bayesian network congestion games: the subtle power of symmetry. In AAAI, 2021a.
Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online Bayesian persuasion. In Proceedings of the 38th International Conference on Machine Learning, pages 1314-1323, 2021b.
Matteo Castiglioni, Giulia Romano, Alberto Marchesi, and Nicola Gatti. Signaling in posted price auctions. In AAAI, 2022.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Regret minimization in online Bayesian persuasion: Handling adversarial receiver's 's types under full and partial feedback models. Artificial Intelligence, 314:103821, 2023.
Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning upproximately optimal contracts. In Algorithmic Game Theory: 15th International Symposimm, SAGT 2022, page 331-346, 2022.
Lee Cohen and Yishay Mansour. Optimal algorithm for Bayesian incentive-compatible exploration. In EC, 2019.
Shaddin Dughmi and Haifeng Xu, Algorithmic Bayesian persuasion. In STOC, 2016.
Shaddin Dughmi and Haifeng Xu, Algorithmic persuasion with no externalities. In EC, 2017.
Yuval Emek, Michal Feldman, Iftah Gamzu, Renato LaesLeme, and Moshe Tennenholtz. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computation, 2014.
Yiding Feng, Wei Tang, and Haifeng Xu. Online bayesian recommendation with no regret. In Proceedings of the 23rd ACM Conference on Economics and Computation, page 81 818-819, 2022.
Michal Forišek. Approximating rational numbers by fractions. In Fun with Algorithms, pages 156-165. Springer Berlin Heidelberg. 2007.
Jiarui Gan, Rupak Majumdar, Debmalya Mandal, and Goran Radanovic. Sequential principal- agent problems with communication: Efficient computation and learning. arXiv preprint arXiv:2306.03832, 2023.
Itay Goldstein and Yaron Leitner. Stress tests and information disclosure. Journal of Economic Theory, 177:34-69, 2018.
Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated prineipal-agent problems. In Proceedings of the Fifieenth ACM Conference on Economics and Computation, page 359-376, 2014.
Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6): 2590-2611 2011.
Anton Kolotilin. Experimental design to persuade. Games and Economic Behavior, 90:215-226. 2015.
Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learning in dynamic Stackelberg games. arXiv preprint 272.:.220..04488. 2024.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, pages 250-262, 2009.
Tao Lin and Ce Li. Information design with unknown prior, 2025, URL/attps:/arrxxwrrrg. 2410.05533
Yishay Mansour, Alex Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian exploration: Incentivizing exploration in Bayesian games. Operations Research, 70(2): 100:1105--1121 2022.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies to commit to. In AAAI Conference Artificial Intelligence, volume 33, pages 2149-2156, 2019.
12

---

Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclosure means to security. In AAMAS, 2015.
Shoshana Vasserman, Michal Feldman, and Avinatan Hassidim. Implementing the wisdom waze. In IJCII, 2015.
Jibang Wu, Zixuan Zhang. Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. In EC, 2022.
Haifeng Xu. On the tractability of public persuasion with no externalities. In SODA, 2020.
Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. Signaling in Bayesian Stackelberg games. In AAMAS, 2016.
Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. Proceedings of the 24th ACM Conference on Economics and Computation, page 1188, 2023.
You Zu, Krishnamurthy lyer, and Haifeng Xu. Learning to persuade the fly: Robustness against ignorance. In EC, pages 927-928, 2021.
13

---

Appendix
The appendixes are organized as follows:
Appendix
provides a discussion of the previous works most related to ours.
Appendix
presents additional preliminaries.
Appendix
presents the omitted proofs from Section
Appendix
presents the proof of Lemma 4 from Section
4.3
Appendix
provides a description of the results and the procedures employed in phase 2.
Appendix presents the omitted proofs from Section 5
Appendix presents the omitted proofs and some technical details from Section 6
Appendix discusses the PAC-learning problem when the prior known.
A
Additional Related Works
Learning in Bayesian persuasion settings In addition to the works presented in Section 1.2
problem of learning optimal signaling schemes Bayesian persuasion settings has received growing attention over the last few years. Camara et al. 22200] study an adversarial setting where the receiver does not know the prior, and the receiver's behavior aimed at minimizing internal regret. Babichenko al. [2022) consider online Bayesian persuasion setting with binary actions when the prior is known, and the receiver's utility function has some regularities, Feng et al. (2022) study the online Bayesian persuasion problem faced by a platform that observes some relevant information about the state of a product and repeatedly interacts with a population of myopic receivers through a recommendation mechanism. Agrawal al. [2023] design miggeitiiiiiiiaiionn algorithm in advertising setting based on the Bayesian persuasion framework, assuming that the receiver's 's utility function satisfies some regularity conditions.
Online learning in problems with commitment From a technical point of view, our work is related to the problem of learning optimal strategies in Stackelberg games when the leader has knowledge of the follower's utility. Letchford et al. [2009] propose the first algorithm to learn optimal strategies in Stackelberg games. Their algorithm is based require an exponential number of samples, both in the number of leader's ' actions m and in the representation precision L. [Peng et al. (2019) improve the algorithm of Letchford al. [2009]. , while Bacchhocchi et al. 2024a] further improve the approach by Peng et al. [2019] by relaxing some of their assumptions.
initial random sampling that may
Furthermore, our work also related the problem of learning optimal strategies in Stackelberg games where the leader and the follower interaction is modelled by Markov Decision Process. Lauffer et al. [2024) study Stackelberg games with a state that influences the leader's utility and available actions. Bai al. 2021] consider a setting where the leader commits to pure strategy and observes a noisy measurement of their utility.
Finally, our work is also related to online cedenn-action principal- aggent problems, in which principal commits to a contract at each round to induce an agent to take favorable actions. Ho al. 2014 initiated the study by proposing an algorithm that adaptively refines discretization over the space of contracts, framing the model as multi-armed bandit problem where the discretization provides a finite number of arms to play with. Cohen et al. [2022) similarly work in a discretized space but with milder assumptions. Zhu et al. [2023] provide a more general algorithm that works in hidden-actio principal-agent aagett problems with multiple agent types. Finally, Bacchiocchi et al. (2024b) study the same setting and propose an algorithm with smaller regret when the number of agent actions small.
B Additional preliminaries
B.1
Additional preliminaries Bayesian persuasion
In step (3) of the sender-receiver interaction presented Section 2.1 after observing s E S, the receiver performs Bayesian update and infers posterior belief & Ag over the states of nature,
14

---

according to the following equation:
(0(s)
40 E O
Σ Er por Po (s)
Consequently, given signaling scheme ø, equivalently represent it distribution over the
set of posteriors it induces. Formally, we say that & induces 7 Ae + [0, if, for each posterior distribution Ae, we have:
( Σ
(500(()
and
( = 1.
=ESIE"=BEES BEB
(Esupp(>)
Furthermore, we say that distribution over set of posteriors is consistent, i.e., there exists valid signaling scheme inducing 7 if the following holds:
(E) no AO O.
(ESupp(7)
With abuse of notation, we will sometimes refer to consistent distribution over set of posteriors y as a signaling scheme. This justified by the fact that there exists a signaling scheme é inducing such distribution, but are interested only in the distribution over the of posteriors that & induces.
B.2 Additional preliminaries on the representation of numbers
In the following, we assume that all the numbers manipulated by our algorithms rational. Further- more, we assume that rational numbers are represented as fractions, by specifying two integers which encode their numerator and denominator. Given rational number l/c with b, E Z, we denote the number of bits that q occupies in memory, called bit-complexity, as Bg = B, + Be, where B, (B,) the number of bits required to represent the numerator (denomi- nator). For the sake of the presentation, with an abuse of terminology, given vector in Q" D rational numbers represented as fractions, we let its bit-complexity be the maximum bit-complexity among entries.
represented as fraction
Furthermore, we assume that the bit-complexity encoding both the receiver's utility and the prior distribution is bounded. Formally, we denote by B, the bit-complexity of the prior μ4, while assume В,, to be an upper bound to the bit-complexity of each d-dimensional vector ua(a) with 0 O. Moreover, the parameter e computed by our algorithms, while we denote with Bp the bit-complexity of the estimator çi computed by Algorithm
let B := B, + B,, Finally, also denote with B, the bit-complexity of
C Omitted proofs from Section
Lemma Given Ti = 12 log (24/)] and e E (0, 1/6a). Algorithm 2 employs T₃ rounds and terminates with set X. C X such that, with probability at least 8: (i) Edee MoT 2 e for every
slice x E X. and (ii) Eoco Ho 10cfor every slice x E X Xe
Proof. For each 0 E θ we consider two possible cases.
1. If μe then employ the multiplicative Chernoff inequality follows:
IP [ue βel
2 ju
1
< 2E
Time
where Ti E N4 the number of rounds employed estimate pug. As a result, by setting the number of rounds to estimate μ4 equal to T, = [12/clog (2d/5) we get:
1 Poo
5
8
IP
[
2 7/
2d
since pig > e. Then, we get:
μ1
3/0
8
< Nág
-
2
(4)
2
d
15

---

Consequently, with probability of at least 1 8/d the estimator Po is such that te E (w0/2, 3wa/2]. Thus, if ps 6c, then Na 3c > 2c and 0 O. We also notice that there always exits a & E θ such that μe 2 1/a 2 6c, since c E (0, 1/6)). Consequently, with a probability of at least 1 - 6/d, there always exist a E @.
2. If μe then we employ the multiplicative Chernoff inequality follows:
P (To 2 (1 + c) S
21c
with e/ug. Thus, by setting the number of rounds employed estimate μ4 equal to Ti = 12// log (24/6)], , we get:
12 log
2d 5
P (Na 2 Me + 5 exp
2 + H
12c log
2d
(7)
< exp
A6
2
146
8
8
2d
d'
since (/(x+22 2 1/3, for each
1. As result, have:
8 d
P (īo S pg + +E)
Thus, with a probability of at least 1 - 5/d, if μ1 S c, then po S + e, which implies that üg 2e. Furthermore, if μo then No 2e and & θ
Thus, by employing union bound over the set of natures, have that if μs S c, then its correspond- ing estimate Oo falls within the interval [0, 2c] and & Ô, while pe 2 6c, then its corresponding We also notice that,
estimate is such that Po > 2e and E θ, with a probability of least with the same probability, the set θ is always non empty.
Consequently, for each slice X, with respect signal s, the probability of observing can be lower bounded as follows:
Σ
PAg S
Σ PaIa <
Σ paza S
Σ
paIa,
2
AE
#C
#E
OE
where the inequalities above hold because of the definition of X, and observing that each E θ satisfies Equation 4 with probability at least - 8.
Furthermore, for each æ of Xe. the two following conditions hold:
1
Σ pazo I Σ Pazza S 2c and
Σ 0g
Haaa S 6c
Σ .g S 6e,
2
0g0
with probability at least 1 - 5. Thus, by putting the two inequalities above together, for each x E Xx, we have:
Σ
uaxa I 10e,
6
with probability at least - 8, concluding the proof.
Lemma 2. Under event ε\, given any p E (0, 1) and a normalized slice x E Xx. if the sender commits signaling scheme θ - S = (s1, s2) such that @0(s1) 28 for all f θ during q [ log(1/)) rounds, then, with probability at least 1 signal is sent at least once.
16

---

Proof. In the following, we let 7 be the first round in which the sender commits to o. The probability of observing the signal $1 given round - 5 is can be lower bounded as follows:
P s1)=
Σ AE
Maze
where the inequality holds under the event & Thus, each round, the probability of sampling the signal $1 E S is greater or equal to e > 0. Consequently, the probability of never observing the signal
81 q rounds given by:
T+--1 n
P
(8
foi) S (1 (1- S. S
where the last inequality holds by taking
log(p) log(1-> (1
log(1/p) for each E (0, 1).
As result, the probability of observing the signal 81 least once in g rounds is greater equal to:
T+ター1
r+q-1
U
(s' + s1 = -
n
{st + #s1
21 -1-P.
concluding the proof.
Theorem 1. The regret attained by Algorithm iis Ry S (/
Proof. In the following, we let ò = <= = T and [vBrdd") [VT as defined in Algorithm To prove the theorem, we decompose the regret suffered in the three phases Algorithm
Phase 1. We observe that the number of rounds to execute the Sealld-Search-300 procedure (Algorithm ()
is equal to T3 log (1/6) log(d)). Thus, the cumulative regret of Phase can be upper bounded as follows:
R2 S Ō 0= (= log(d) S
VT d d'vnB
) S =ō(v)).
log(d)
This because, at each round, the regret suffered during the execution Algorithm is at most one.
2. Phase 2. Under the event ε,, which holds with probability - 6, Algorithm 6 correctly terminates with probability --c. Ç. Thus, with probability least rounds employed by such algorithm is of the order:
Ç. the number of
n²
(
d n2 d' dB B. Bp)
log"
d
n2 log2 (T)) (d(BBB.) +
(
d (d+1)
d
where the last equality holds because BB = Olog( (2/e) + log(d) + lTg(T)). As a result, by taking the expectation, the regret suffered in Phase 2 by Algorithm can be upper bounded follows:
d
R S
2/26/
BT
d
since, at each round, the regret suffered during the execution of Algorithm
6 is most one.
3. Phase 3. Let be the number of rounds required by Phase and Phase 2 terminate. Under the events & and &g, which hold with probability least - 5 Ç, thanks to Lemma 4 the solution returned by Algorithm 3 at each round > is O(dne + ve) -optimall,, where define 1 = Eoce T. We introduce the following event:
E, {lue Pe.el
V0 θ}
17

---

where we let 6, > 0 be defined as follows:
log (2dT /1)
t>T.
2(t T)
Then, by Hoeffding's inequality and union bound have:
P E 2 1-14.
P
CST
Thus, by setting 1/T, the regret suffered in Phase 3 by Algorithm bounded as follows:
1 can be upper
R
Σ MB
Pi,
+ +0 (deT)
[=7+1
AE9
T
$ d
Σ
+ 00 (dneT)
1=T+1
① (dvT + dncT)
δ (dvT + n dd VBBT)
As result, the regret of Algorithm
is in the order of:
RT S Ô n
d + 8
d VBT + n 2/ d BT =6
=0(n" 2/ d3 (d (d+ (attt( VBT (
concluding the proof.
D Proof of Lemma 4 from Section 4.3
In order to prove Lemma we first consider an auxiliary LP (Program 5ap that works on the vertices of the regions (a). This useful to take into account the polytopes (a with null volume. Indeed, for every action a E AA such that (X, = O, Algorithm 3 takes in input only a face R.(a) (a) of X. (a) such that (a) C VRR. (a)). By working the vertices of the regions (a),
show that the vertices in (a) are sufficient to compute an approximately optimal signaling scheme.
The auxiliary LP that works on the vertices is the following:
max a20
Σ
Ox Σ
(5a)
NEV.
OEE
8.b.
Σ
S
44 e.
(5b)
DEV.
Program 5a takes in input the set of vertices V. = USEA ((x((a),, along with the corresponding
best-responses (a(x))nev, and the exact prior It then optimizes over the non-negative variables 0₂ one for vertex V.. These variables ar act as weights for the corresponding slices x E V.. identifying a non-normalized slice az E P
In the following, show that the value of optimal solution o* to Program 5a at least o* OPT - (((dd)). Then, we prove that the signaling scheme & computed by Algorithm achieves principal's 's expected utility of at least v* minus quantity related to the difference between the estimated prior fa and with the actual prior μ. Thus, by considering that v* 2 OPT O(end), we will be able prove Lemma 4
As first step, we show that is possible decompose each slice X, into a weighted sum the vertices x' E V. without incurring loss in the sender's utility. Thus, generic slice of an optimal signaling scheme can be written as convex combination of slices x' with x' E V.. This property formalized in the following lemma.
18

---

Lemma 6. For every 2 E Ne, there exists distribution a E Av, such that:
Σ
O2
40 E θ.
x'
Furthermore, the following holds:
Σ
paxa (a(x))
Σast
as Ew (a(x')).
DEO
r'EV, 0EG
Proof. Let a a(x). Since E Xe(a), by the Carathéodory theorem, there exists an (v(x(())
such that:
E
Og = Ia v0 O.
x'EV(X
Furthermore:
Σ
Hgzgu = Σ
uo
Σ
ag
ug(a).
OEG
OEG
(o))
Σ
Oige
Moxi ugg (a)
x'EV(X.(a)
AEO
Σ
Olge
Maxi ug ( (zx'))
s' (o)
BE
where the inequality holds because the receiver breaks ties in favor of the sender. Finally, we observe that for each distribution over the set V (X, (a)) for given (a)a), we can always recover a probability distribution supported in Ve, since V (x.(a) C V. by construction.
Thanks to the the result above, in the next lemma (Lemma of Program 5a has value at least 8* 2 OPT 10end. To show this, we begin by observing that there exists set I of slices of the optimal signaling scheme that belong to the search space X. By applying Lemma to each of these slices, we obtain a feasible solution for Program 5a The value of this solution is least the sender's expected utility given by the slices in J. Finally, thanks the properties the search space X,, we can bound the expected sender's utility provided by the slices that lie outside the search space.
prove that optimal solution
Lemma 7. Under the event E,, the optimal solution of Program 5a has value at least o N OPT 10cnd.
Proof. In the following we let the AA for each E be an optimal signaling scheme, where we assume, without loss of generality, such signaling scheme to be direct, meaning that S = A and E (a) for every action A. Furthermore, for each action a E supp(ø), we define:
(b((a)
VO E + and ag Σ Φo(a).
rØ Eoee (a(a)
oce
We observe that each x E X()), indeed we have:
Σ (o =
Σ (ooo(())oo()) 2 (odola)us(a)
Σ Po (a"). BEO
Or BEE
Org AEO
8EB
for every action d' A. We define the subset of actions A' A in way that if a E A', then x²" E X., Le., A' == (a E A xa E X.). Then, we let A" := supp(ø) d) \ A'. Furthermore, for each E A', thanks Lemma there exists distribution aa Av. such that:
Σ x' EV.
19

---

and the following holds:
Σ
Uو (ol) = =Eu
Po
Σ
agrzn
rdb(a).
8EB
650
Σ
Σ
OEG VVEV.
Σ
Σ
MBo 2 x J Ug (a(x'))
(6)
AE E'EV,
We also define a² : V. + R., as follows:
Σ agg
aEA'
for each x' E V. First, we show that a* V. + 12 is feasible solution to LP 5a
Indeed, for each
O E θ it holds:
E aa
Σ
Σ
az
N'EVe
x'EV.
aEA
Σ
Or
aEAl
W'EVe
Σ
agazi
aeA'
Σ
aEA'
Where the equalities above holds thanks to Equation and the definition of a*. Then, we show that the utility achieved by Ve + RT is greater or equal to OPT 10cd. Formally, we have:
Σ a Σ
Σ
Σ GEAr
ag- a
uoo ( (a(x')
x' VVV.
BEE
x'EV,
OEG
Σ Orgn
M00e 2 (a(x')
aEA
s ''EV. BEE
Σ agga
aeAA'
AEG
Σ
Σ
(a)
A' AEA
OPT
Σ
podo(a)u
aeAA" AEe
OPT Σ
e OPT Σ
aeA""
1o0 ug (a)
ae 8EB
ОPT 10end.
Where the first inequality holds thanks to Inequality (6), the second inequality holds since 0ga- S d and the last inequality holds since, for each x g X,, holds Eece uo S 10e, under the event ε, and x & X. for every a E AA". Consequently, a* is a feasible solution to I.P Sa provides, under the event & value of at least OPT 10cnd. As a result, under the event & the optimal solution of LP 5a has value 8* OPT 10cnd, concluding the proof.
Lemma 4. Given inputs R. (a))
(a)) aE Xe. and füe Ae for Algorithm 3 under events E₁ and Ey the signaling scheme è output by the algorithm is O(end v) -optiaal Eoee Pr.e Me
20

---

Proof. We observe that under the events & and E2, the collection R. = (R.(a)leEA is composed of faces (a( of X. (a) (possibly the improper face Xe(a) itself) such that every vertex a E (a) that satisfies a(z) = belongs to (a). The following statements hold under these two events.
As first step, prove that given feasible solution construct feasible solution to Program with the same value. In particular, we consider a solution ip (* AaEAA defined as:
(ag))ev to Program 5a can
JB
Σ
agIo
Va A,0
(v).(0)
We observe that for every A and 0 E θ we can bound 2g follows:
T
Og S
Σ
0g 1
(a).
BEV,
where the last inequality holds due to the constraints of Program 5a belong x
Consequently, the vectors 3
Now we show that Htth belongs to (a) for every a E A. This holds trivially for every action a E AA such that Ex'v, az 0, as To 0 E (a).. Consider instead an action A such that Even((a) azr 0, and let us define the coefficient:
a2
(VE ag!
for every vertex I E Ve(a). One can easily verify that 3rh E (v) Now consider the normalized slice:
N.a Σ
(a).
This slice belongs to R (a) = Ra(),, as it is the weighted sum of the vertices Va(a) S (a) with weights 8 (a) Furthermore, we can rewrite the component T of the solution e as:
Σ
Og.
(VV.(a)
Thus, by considering that Noo E R. (a) and 2 E X4, we have that Toh E Rz(a).
Finally, since is feasible solution for Program 5a
observe that:
Σ S Σ Σ
Og Σ
0g $ 1.
REV.
As result, = (""")
AaEAA is a feasible solution to Program
If the estimator The coincides with the exact prior μu, then direct calculations show that the solution to Program Jachieves the same value of the solution a to Program 5a
follows that, when 74, = μ., the optimal solution of Program has at least the same value of the optimal solution of Program 5a
In order to conclude the proof, we provide a lower bound on the utility of the signaling scheme computed by Algorithm 3 Let Gf be the signaling scheme computed by Algorithm 3 while let
= (Pa) )aEA be the optimal solution to Program 2 Furthermore, we let vi = Fra aaEA be the optimal solution of Program and oF the signaling scheme computed by Algorithm when the prior estimator coincides exactly with the prior itself, i.e., f := Pa =
Since x IPPa E (a) for every a E A, we have that E Ad (a) Breaking ties in favor of the sender, the action aole (sa) is such that:
Σ 6c0
IPaa paai uig t (sa))
Σ
I. posty ug(a).
8C8
Observe that when R. (a)
(Aa(a) = @ and (a) {0), we have _PP.a = 0. Thus, x LP.a does not contribute to
the sender's utility, 5 & ( and _40 (sa) A by definition.
21

---

Then:
" "((t") = -E>
uooo LP (s)ug(a") (s))
sES DEB
>
Σ
Mode (8) (s))
LP
*ES }
BEB
Σ
E
LP
ug (a (5*))
p
aEA
Σ
LP.a (a)
.EAA
1g
LP.a (g((a)
Σ BE8
Peo 10
AEA BE0
E.a (a) pogg
Σ
Too
140
BEABEB
BEE
E.a 10 (a(a) 2
Σ BE
No
140
BEABEB
We recall that the value of 1/ = (x.5a) AaEA is at least the optimal value of Program 5a when f = μr, and such value least 0$ 2 OPT 10end according Lemma 7 Thus, we have that:
u( (O(P))
ΣΣ REA e
E.a Mort ugg (p(aa
Σ no
2
OPT 100nd
Σ ICO
No
140
concluding the proof.
E Omitted proofs and sub-procedures of Phase 2
F.1
Action-Oracle
The goal of the Action-Oracle procedure (Algorithm 5 is to assign the corresponding best-response slice X, received as input. order do so, it repeatedly commits to a signaling scheme such that æ is the slice of s with respect to the signal 81. When the signal 81 is sampled, the procedure returns the best-response a(x).
Algorithm 5 Action-Oracia
Require: 2 E X.
1: (s())) t my and (o(()) + - Ig e e
2: do
3:
Commit to of = o. observe 8;, and send s
4: Observe feedback a'
5: a 4- a'
6: while s¹ + 81
7: return
In the following, for the sake of analysis, we introduce the definition of clean event under which the Action-Oracle procedure always returns the action a(x) E A, as formally stated below.
Definition 4 (Clean event of Action -0racler... We denote E" as the event in which Algorithm correctly returns the follower's best response a(z) whenever executed.
In the proof of Lemma we show that, thanks to Lemma 2 and the definition of X,, it is possible to bound the number rounds required Algorithm 5 to ensure that always returns the best response
a(z) A with high probability.
22

---

E.2 Find-Polytopes
Algorithm Ponyttoes
Require: Search space X, X, parameter (0,
1: (c, (a) Jaec) <- S
2: for all aj E A Co
3: (aça < Find-Face(C, (XL(4))oEcs))
4: R.(ax) (ax) Vag EC
5: return {R, (a)
Algorithm [6] can be divided in two parts. First, by means of Algorithm it computes the polytopes (a) (a) with volume strictly larger than zero. This procedure is based on the algorithm developed by [Bacchiocchi et al. [2024a] for Stackelberg games. The main differences are the usage of ActionnOraaa -onarralle query generic normalized slice, and some technical details account for the shape of the search space X.
In the second part (loop Line Algorithm 6). it finds, for every polytope (a) with null volume, face R, (a) such that V. (a) S (a). Let us remark that (a) could be the improper face X. (a) itself, and it is empty if V. (a
Lemma 3. Given inputs X, C and Ç E (0, 1) for Algorithm 6 let L B B, + Bi, where B, Be, and Bp denote the bit-complextty of numbers pguu (a;). and Pt. respectively. Then, under event E and with at probability at least --C. Algorithm Algorithm outputs a collection R. = (R. (R.(a))aee [a))aEA where R. (a) is (possibly improper) face of (a) such that (a S (a),),, in number of rounds T2:
n2
log (5)
d d (d+n) d )))
T2 S Ō
Proof. In the following we let = B B,
Bp-
As first step, Algorithm 6 invokes the procedure Find-Fully-Die Lenlly--immniionl-RRgiooo on according to Lemma 8 under the event E., with probability least - c/2, Algorithm computes every polytope X. (a) with volume larger than zero by performing at most:
Thus,
C -=ō(mi (F +
(ad")
dd (d+1)
calls to the Action-Orate procedure. Together with these polytopes, it computes the set C A containing the actions such that vol(X(()) 0.
Subsequently, A (oniihmmmmmmppe employs the procedure Find-Face at most n times and, according to Lemma 12 it computes the polytopes R. (a,) for every aj C. Overall, this computation requires:
C₂ = n. d 4+n
calls to the Action- Oracle procedure. Thus, under the event E" and with probability at least 1 C/2, Algorithm 6 correctly computes the polytopes Raça) ) for every action A. Furthermore, the number of calls C' 2 0 to the action-Oracia procedure can be upper bounded as:
C = C1 + C2 < n²
2 ((LLlo(V/)) +
d +
Moreover, by setting p = </2C', and thanks to Lemma 2 with probability of at least - every execution of Action-Oree -racle requires at most N 2 rounds, where N can bounded as follows:
log(1 /p)
20
N N
log
Consequently, since the number of calls to the Action -oroole procedure is equal to C. by employing a union bound, the probability that each one these calls requires N rounds terminate greater than or equal to:
S C0= C
1 C-pp=1
20
23

---

To conclude the proof, we employ union bound over the probability that every execution of Action-Ose -oaalee terminates in at most N rounds, and the probability that Algorithm@@perfomsss C calls to the Action-Oracia procedure. Since the probability that each one of these two events hold least 6/2, with probability at least 1 - C. Algorithm correctly terminates by using number of samples of the order:
C
2C 5
n
log (t)
dLL+ L+ + d
d 1
))
log
S
concluding the proof.
E.3 Bindd-Pully-DDineniionn------
A
7 oFinddFFully--DDmmeiiioonllll
Require: Search space X, X, parameter E (0,
1: < (2(dm))+n)
2: C + Ø
3: while Ea # X. do
4:
ااا + Sample a point from int (X \ (((e(((a)))
5:
aj + Action-Oracle(x""))
6:
U(a,)) tX
7:
B₁ Bit-complexity of af
8:
A d2 d2dd(B,++ d(B,, + BB for all u E V((((a)) do
9:
10:
x +- Ax + (1 A)U
11:
ActionnOracle(s))
12:
a * oj then
13:
Hyp + Find- (ta-Heerppaa((,,ll(aaa.... v, u(a,) + U(a,) Hys
14:
15:
else
16:
restart the for-loop Line Cu
18:
Xe(a,) + U(a,)
return C, (ax
At a high level, Algorithm works by keeping track of a set C C A of closed actions, meaning that the corresponding polytope X, (a) has been completely identified. First, at Line 4 Algorithm samples at random a normalized slice int from the interior of one of the polytopes (a,)) that have not yet been closed and queries it, observing the best-response aj A. Then, it initializes the entire X. as the upper bound (aa,) of the region X, (a,). As a further step, to verify whether the [1 1ne of the vertices of the upper bound (aa). Since the same vertex may belong to the intersection of multiple regions, the Action-Oracia procedure is called upon an opportune convex combination of znt and the vertex u itself (Line 10). If the vertex does not belong to X. (ay),, then
upper bound (aa) coincides with (ay),, Algorithm 7 queries at Line
separating hyperplane can be computed (Line 13) and the upper bound (((a)) ) is updated accordingly. In this way, the upper bound U((a)) is refined by finding new separating hyperplanes until it coincides with the polytope X, (az). Finally, such procedure is iterated for all the receiver's actions a, E AA such that vol(X' (a;)) > O, ensuring that all actions corresponding polytopes with volume larger than zero closed.
We observe that the estimator çú, is updated during the exccution of Algorithm according to the observed states. However, let remark that the search space X. {I E X Loce Paxo 2 does not change during the execution of this procedure.
Lemma 8. Given in input X. C X and Ç E (0, 1), then under the event E" with probability at least
1 c/2 Algorithm 7 computes the collection of polytopes (X. (a,)))aaae with volume larger than zero. and the corresponding set of actions C. Furthermore, it employs at most:
Ö 0n²² & (oloo)))) +
(d (d+n)
d
24

---

calls to the Action-Oracle procedure.
10 with an approach similar the one proposed in Theo- we can prove that, under the event Ex, with probability at least 1 2 (2 n)² + n). Algorithm computes every polytope Xe (a) with volume larger than zero by performing at most:
Proof. Thanks Lemma 9 and Lemma
rem 4.3 by |Bacchiocchi et al. 2222aa
o on22
(oLlog()))) + d (dtn)) d
calls to the action-Oracla procedure. Together with these polytopes, it computes the set C S A containing the actions such that vol(XX(a)) > O.
Furthermore, we observe that C (2(d + n) + n). as defined at Line in Algorithm 7 As
result, under the event 8", with probability least 6/2, the number of calls C1 0 performed by Algorithm 7 to the
procedure can be bounded as follows:
C 2 n² (L (og()))))))+ + d
+ n
concluding the proof.
E,4 Hypeeplpe
Algorithm 8 Find Hind-lapee
Require: aj (,, 0.8
I: x + Sample-Int(U((i)))
2: x² <-
3: if Action-Oracle(z) = a then
4:
-²tV
5: else
6:
1² + ا
7: x <
x,,,,,,, x²)
8: a 2- BB B.)
9: S₁ Ø; Sx= Ø
10: for = 1...do do
11:
f- Sample-Int(Hl nX, 8)
12: rti xi + x+i+x +a(r r²)
13:
- a(r a r²)
14:
if Action-Oracle(x*)) = aj then
S U - (x
16: else
17:
S S u (zti) SS S
18:
Build H₃* by Binary- Seary--Sarchhae (aj, x x²) for d - 1 pairs of linearly-independent points x
S₁, x² E Sx
The goal of the Hypeppaee procedure is to compute a new separating hyperplane H5 between a given region X, (a;) and some other polytope X, (ax). with üj, ag A. To do so, receives as input an upper bound U(aa) of some polytope X, (ay), ), an interior point ii E int()(a;)) vertex E V(l(aa;) that does not belong to X (a,). and a parameter 5 > 0 as required by the Sample-Int Int procedure. As first step, Algorithm samples at random a slice x from the interior of the upper bound ((a,). Subsequently, it performs binary search on the segment between and either or _.l!t, depending on the best response aar) in x. This binary search returns a point x on some new separating hyperplane H₁ (Line 7 As a further step, the algorithm computes two sets of normalized slices, S, C (a,)) and S₁ [ X. (ax). Finally, it performs d - 1 binary searches between different couples of points, one in S, and the other in St. in order to completely identify the separating hyperplane.
Lemma With probability at least - 225 under the event Ed Algorithm returns separating hyperplane H by using Old (B B. + Bp) + d' log(1/5) calls Algorithm
25

---

Proof. We observe that, with the same analysis provided in Lemma 4.7 by Bacchiocchi et al. [2024a]. we can prove that, under the event E", the binary-search procedure described in Algorithm 9 correctly computes a point on separating hyperplane by calling the Action-Orache procedure at most O(d(B, + B)) times.
With the same reasoning applied in Lemma 4.4 and 4.5 by Bacchiocchi et al. [0024a]. we can prove that with probability at least 1 (d) under the event 8 the points xx are linearly independent and do not belong to Hz.. To conclude the proof, we have to show that every x belongs to either (az) or X. (ax). This because, if the previous condition holds, under the event 8*, Algorithm correctly computes new separating hyperplane with probability at least (d + n
To do that, we show that the constant a defined Line ij Algorithm X is such that all the points xt and x either belong to (a,) or X. (ax),, given that x" belongs to the hyperplane between these polytopes. With an argument similar to the one proposed in Bacchiocchi et al. [2024a], the distance between zf and any separating hyperplane can be lower bounded by 2 2-4(8,+41 where Bz is the bit-complexity of z².
Similarly, the distance between x" and the hyperplane Ā = fx E IRd lower bounded as follows:
Ence Poxo 2 2e} can be
d(r H Encê zaAeo + 2E
1
EoEe 12
d2 BB++
where B₁ is the compolxyyy of f.. The inequality follows by observing that the denominator of the fraction above is at most d, while to lower bound the numerator we define the following quantities:
xofe = a and E c= 2 Σ
3
V
OEô
where and are integers numbers, while y and v are natural numbers. Thus, the numerator Eecö ZoPa + 2e| of the fraction defined in Equation 7 can be lower bounded as follows:
av + 2 By
Σ zofio + 2c θ
2 2 BalBB+BB++B.
2
8r
where the last inequality follows from the fact that the bit-complexity of is at most B., while the bit-complexity of 3 cannot exceed 3d( Bg + Bp) as stated by Lemma D.1 of Bacchiocchi et al. 20024a].
Overall, the distance between x and the boundary of the polytope X. n Xaaa)) strictly larger than a == 2 4d(B, + B++ B+B B.)-oog) Thus, every signaling scheme x: and x belongs to X. and either x(az) (ax).
Finally, we observe that the bit-complexity of x is bounded by B, = O(d (B++ (/))) as stated by Lemma 10 Thus, the first binary-search requires O(d(B, + B)) = Odd (llo((//)) calls Oattoon-rraclo where I, = B + B, Ba-
Furthermore, the bit-complexity of x is bounded by O + d d 1/6)) As a result, the bit- complexity of the slices +² and x² is bounded by (d L Loglo((//)), given that the complexyyyxtty of a is (dL). It follows that each binary search between two points in S, and S₃ requires Odd L + d² log(>/6) calls to action-Oracio
Overall, Algorithm X invokes the Action- -araole procedure most O(d L + at log (o6)) times, accounting for the 1 binary searches, concluding the proof.
E.5 Binary-Search
The Binary-Searde procedure performs a binary search on the segment connecting two points, xt xt,0² x2 E X such that x E X, (a;) and x² & (a,) for some aj E A, order to find a point on some separating hyperplane HzK. At each iteration, the binary search queries the middle point of the segment. Depending on the receiver's best-response in such a point, keeps one of the two halves of the segment for the subsequent iteration. The binary search ends when the segment is
26

---

sufficiently small, so that it contains single point with bit-complexity appropriate for a point that lies on both the hyperplane Н₃ and the segment connecting z' and x² Such a point can be found traversing the Been-Brocot-Tree For an efficient implementation, see [ooriek [2007]. Overall, Algorithm 9 performs ( B₂ + B)) calls the Action-Oracle procedure, and returns normalized slice x² with bit-complexity bounded by Odd( 22 + B)), where Bg is the bit-complexity of the points x and x².
Algorithm Binary-Searce
Require: aj. xx , of bit-complexity bounded by some B₂
1: X1 < 0; A2 f-
2: while A2 X1
2 2-6( do
3: À + (A1 + /2) x + x² + X(x² x²)
4: if Action-Oracle(z")
a then
5:
d + x
6: else
7:
A2 + x
8:
A + Stern - Brocot- -rrcottTree(A1,,.. 22, 3d + +B))
9:
Aa (1 A)x²
E.6 Sample-Ing Int
Algorithm 10 Sample-Int
Require: P X. vola-1 > and ò
1: V + d lineealy-indeepeneett vertexes of P L.Ev
2: xx
3: p (d2291 14401.
MM [4//]]
4: y Uniform (f-1.
M-1
0.
112-1)
M
M
5: for all i 1,...,
do
6: Tj +- 2 + Mi/i
7: Id f 1= Vz
The Sample- Int procedure (Algorithm 10 samples random normalized slice from the interior of a given polytope P. We observe that each polytope Algorithm iis required to sample from is defined as the intersection of X, with some separating half-spaces the ones defined in Section procedure provides theoretical guarantees both on the bit hotpleppl of the point x: being sampled and on the probability that such point belongs modified to sample point from a facet of the simplex X' = Au (intuitively, this is equivalent to sample point from A As first step, Algorithm [T] computes normalized slice x in the interior of P (Line 2. Subsequently, it samples randomly vector from suitable grid belonging to the (d - (d-1)--dimee) -)-dimensioonl hypercube with edges of length 2. further step, it sums each component r; of the normalized slice x² with the corresponding component yi of scaled by an opportune factor p, where the constant p is defined to ensure that x belongs to the interior of P.
This
given hyperplane. Furthermore, it can be easily
The theoretical guarantees provided by Algorithm T0 are formalized in the following lemma:
Lemma 10. Given a polytope P C X. : vola-1(P) > defined by separating or boundary hyperplanes, Algorithm 10 computes z E int(P) such that, for every linear space C Rd ; Z H of dimension at most d - I, the probability that x E H is at most ö. Furthermore, the bit-complexiry of x O(d (B + B. + BB) + log(1/)).
Proof. In the following, we prove that belongs to the interior of the polytope P. To do that, we observe that the point x belongs to the interior of P. while, with the same analysis proposed in Lemma 4.8 by Bacchiocchi et al. [2024a]. the distance between x and x can be upper bounded by pn. To ensure that æ belongs int(P) we have show that d(x xr) is smaller than the distance between zz and any hyperplane defining the boundary of P.
27

---

Let us denote with en the h-vertex of the set V, so that V = for, . Furthermore, we define:
for each h [d] and 0 E ④ Since x belongs to int(P), then the distance between x² and any separating hyperplane Hss can be lower bounded as follows:
Loce )) ug(ax))
, Hzk) =
v (a((u(aa)) - u)(a2))2
Eneo Ei v - no (a()))
dv Eees (uo((a)))))))))))))))({{))))(( - u0(a)))
4dB -ad (B+
d²
To prove the last inequality, we observe that the denominator of the fraction above can be upper bounded by d?, To lower bound the nominator, we define:
po(uo(a;) uo(ax)) = 0k0
for each E O. As result, we have:
d aer
Σ Σ
(o)((a() - uv(a)))
Σ
Barn
k=
OEB h=1
Eoco E h= a07g
(oo Bar Ilw Vie)
Ioae 30 II 2/
II B6
11 Vh
2-1dBB (B+B.+Bp)
The first inequality holds because the numerator of the fraction above be lower bounded by one. The denominator can be instead upper bounded observing that the bit-complexity of each 3e is at most 4B while the bit-complexity of each 2/2 most 9d2 (B + B. + Bp), as stated by Lemma
In similar way, we can lower bound the distance between x and Ā {xr E Rd Eose pasa 2 2c).
Eoe Na0g +
d(x ..
V EoEE 712
Eoce Ed -m Goog +
d. A///ge E9cE 112
By. -
d3
To prove the last inequality, we observe that the denominator of the fraction above can be upper bounded by d2, while lower bound the numerator, define:
No No and
P
B
for each E ④. As result, we have:
d
d Nov
Σ
2e
+ 2e
pvh
0EE A=1
005 -=1
28

---

Enco Ei=1 &Noy II Tiseh + 2ap II
p pll 1/.
2 Bp B. -d (B+B.+BB)
Thus, the distance between x and any hyperplane H defining the boundary of d can be lower bounded follows:
d(x²: 111 _22 2-205 2- (B+
2- (B+B.+B
1
d²
We observe that, given the definition of p Line 3 the distance d(x², is strictly smaller than d(x², H), showing that x E int(P).
Furthermore, can prove that the bit-complexity of x is bounded by (dd B. Ba) log)) log(())),
To do so, we observe that the denominator of x is equal to d [I Vh, while the denominator of y: equal to M = [va/a]. As a result, the denominator of every 22 2; + pib, with i E [d - 1). can be written follows:
D=
II vh D,M, h=1
where D, is the denominator of the rational number Similarly, the last component æa can be written with the same denominator. As a result, the bit complexity of æ E [0, 1J can be upper bounded as follows:
B₂ Nog [D]
Olog(d
II Un M))
d II h=
0 log
(B+.BBBB+BB))
log(d220dd (B4B,+Bb)) + log (a(())
d B + Bp) + log )
=0
Finally, with the same analysis performed in Lemma 4.8 by Bacchiocchi et al. 2024a), we can show that the probability that æ belongs to a given hyperplane H is at most ò.
Each vertex u of polytope P C X. vola-1(P) boundary hyperplanes, has bit-complexity most 9d (B B. Br). Furthermore, with bit- complexity of 9d2 (B + B. B²), all the components of the vector identifying a vertex can be written as fractions with the same denominator.
Lemma 11.
0, defined by separating or
Proof. We follow line of reasoning similar to the proof of Lemma D.2 in Bacchiocchi et al. [024aa] Let be vertex of the polytope P. Then such vertex lies the hyperplane H' ensuring that the sum of its components is equal to one. Furthermore, it also belongs to subset of d linearly independent hyperplanes. These can be separating hyperplanes:
Hij Fd
Hazo (uolo(u)aa)))))) uo(a,)) =0]
BEE
with 0; aj A, boundary hyperplanes of the form H, fwr Rdd x; 0}, the hyperplane A = fa E Rd Eoeō figt 2 3 Consequently, there exists a matrix E Guxd and vector b E Qdd such that Av = b.
Suppose that v is not defined by the hyperplane Å = Rd E Moza 2 2c}. Then, each entry of the matrix A is either equal one or the quantity po(us(a) ua(a)) for some and a' E A. Thus, its bit-complexity is bounded by B. Similarly, each entry of the vector is either

---

equal to one zero. With a reasoning similar to the one applied in Bacchiocchi et al. [022aa] the bit-complextyy of is at most (B, + B,).
Suppose instead that is defined also by the hyperplane H, corresponding to the last row of matrix A and the last component of the vector b. This hyperplane can be rewritten
7 To 2 1
E
R
2c
Thus, each element of the last row of either zero or quantity Ro/2e for some 0 E Ô. We observe that Ru/2. 2. is a rational number with numerator bounded by 2B and denominator bounded by B.+1 Thus, we multiply the last row of A and the last component of b by a constant bounded by ((BB+BB+11)) The other rows of A and the corresponding components are multiplied instead by some constants bounded by 2 24dB This way, we obtain equivalent system A'v = b' with integer coefficients.
We define A'()) as the matrix obtained by substituting the j-th column of A' with b. Then, by Cramer's rule, the value of the j-th component of v, can be computed follows:
det dct(AA(1)) det(AA)
Vj [d].
V/
We observe that both determinants integer numbers the entries of both A' and D' are all integers, thus by Hadamard's inequality we have:
(det(A))
II #E|d
Σ jE(d]
d
II 1E(d-1]
(2
(2 Bo
(2dl
JEld
JE|d]
d(22dBy2
d22d(BB+B..1)
[E[d-1]
II sE(d-1]
ààà (24dB)
dB2((BB+B.+1)
d (24d(d-1) (B
s a BgdB B.+1)
With a reasoning similar to Bacchiocchi et al. 2024a], we can show that that the bit-complexity De of the vertex e is bounded by:
D, < 9Bl + 2(d(Bp + B. +1)) < 9d (B + B, + Ba)
Furthermore, this result holds when the denominator of every component vy of the vertex v written with the same denominator det(A'), concluding the proof.
D
30

---

E.7 Find-Face
Algorithm 11 Find-Face
Require: The set of polytopes (a; a.,e, with volume larger than zero, and action aj & C
Compute the minimal H-representation (a)((a;) for every polytope (,,a,) 0g
2: H((a)) + ! Va; EC
3: First f- True
4: for all x x Ua,ec (a;) do
5: <
6: if = 0j then
7:
if First False then H(a,) - (H E M((((a)) aE H, H(a:)) Va, EC
8:
9:
else
10:
H(a,)) t {H M()((a))) x H} Va, EC
11:
First <- False
12:
Firistt = True then
13:
Fe(ag) 0
14:
F((a,) c x((a) n (uEH(a.)) H for any aj such that X. n N (EH((.)) H #
15:
Return Fe()))
Algorithm 11 takes in input the collection of polytopes (a;)) (a;))a.ee a.ec and another action a, É
such that vol(x. 0, and outputs the H-representation of (possibly improper) face of (a,)) that contains all those vertices z E ((x(()))) where a(x) aj- As we will show by means of pair of technical lemmas, the polytope X, (aj) is face of some other polytope X. (ax), with
C. Consequently, Algorithm 11 looks for face of some polytope X. (ax) containing the set vertices V. (a,).
As first step, Algorithm computes, for every action a, C, the set of hyperplanes M(X corresponding to the minimal H-representation of (a.). This set includes every separating hyper- plane His found by Algorithm 7 together with the non-redundant boundary hyperplanes that delimit X. Subsequently, Algorithm I1 iterates over the vertices of the regions with volume larger than zero, which we prove include all the vertices of the region X. (az). While doing so, it builds set of hyperplanes M((;;) S M(X. for every action a; E C. Such a (possibly empty) set includes all and only the hyperplanes (a.)(a)) that contain all the vertices where the action aj has been observed, i.e, a(x) aj.
Finally, at Line 14 Algorithml 11 intersects every region X, (as) with the corresponding hyperplanes in H(,))). obtaining a (possibly empty) face for every polytope Xe (a:), aj C. At least one of these faces is the face the algorithm is looking for, and corresponds the output of Algorithm
The main result concerning Algorithm I is the following:
Lemma 12. Given the collection of polytopes (Na(a:) hasec with volume larger than zero and an another action 0j, then, under the event Ea, Algorithm /1 returns a (possibly improper) face Fe(a;) of X, (a,) such that Vazz) F.(a)). Furthermore, the Algorithm requires ((n(d))) calls to Algorithm 5
In order to prove it, first need to introduce technical lemmas to characterize the relationship between regions with null volume and those with volume larger than zero
Lemma 13. Let a; a E A such that vol(X. (a;)) > and vol(XX((a)) = 0. Then X. (ax) n (a is (possibly improper) face of X. (a,) and (a,a)
Proof. In the following we assume that X. (a:) (X is non-empty, as the empty set an improper face of every polytope.
We prove that X, (ac) (X = = X((a))
X, (a,) n Hij. order do that, we first show that X, (as) n Hij C xax))) (az). Consider normalized slice E X, (as) n Haj- Then we
have thatr (a,)) As this holds for every x E Xa(as) n Hiy follows that X, (a:) O Hy S
(a,) O (a,))
31

---

Similarly, we show that Xl(a,)) S (asa:) n Hij. Take any normalized slice I E X²(a;) n (a,). Then E Hij as belongs to both (a,) and (aj)), thus I E (a) n Haj. This implies that (as) n (aa))))) S (a:) n Hij.
Consequently, we have that (a, (a) = X.(a;) n Hig. With similar argument, we can prove that X. (a;) (a) X.(a,) n Mag. As a result, we have that (a:) ( (e,) = (a,),) Mil X. (a,) Hij.
In order to conclude the proof, we show that (a,),) n [x = x((a,) n Hi = X((a,) n Hig
is face of both (a;) and X,(a)). We observe that (a,),) [ Hy, thus the non-empty region
X. (a.) n Hij is by definition a face of Xe (a.). Similarly, X. (a,)) ) - His thus the non-empty region
(a)) 0 Hij is face of (a,a) (possibly the improper face (a(a itself).
Lemma 14. Let X,(ag) be a polytope such that vol(Xe(a;)) = 0. Then Xz(a)) is a face of some polytope X. (a:) with vol(XX. (a:)) > 0.
Proof. First, we observe that if X. (a;) is empty, then is the improper face of any region (a:):) with (a.)). > O. Thus, in the following, we consider X. (a;) to be non-empty.
As first step, observe that any normalized slice x X. ({a) belongs also some region X. (ax), where a% E A depends on z, such that vol(Xx > 0. Suppose, by contradiction, that (a)) Then a, is best-response in X. (a,) n Hay. i.e., (a,a, n Hij S (a,).. One can easily observe that such a region has positive volume, thus contradicting the hypothesis that (a,)) O.
Now we prove that there exists some (a:) with vol(X,(a,)) > O such that X. S (a.).) If X. (az) is a single normalized slice x, then this trivially holds.
Suppose instead that X. (a;) has dimension least one. Consider a fixed normalized slice 3 int(X.(a,)) where the interior is taken relative to the subspace that contains (a,)) ) and has minimum dimension. There exists a region (a:) with vol(X. > 0 such that 5 E (a,).
We prove that X. (a,) S. X(a.). Suppose, by contradiction, that there exists a normalized slice (aya) such that & X, (a;).. It follows that the line segment 20 intersect the separating hyperplane H:j in some normalized slice ã E co(T, 2) n Hij. Furthermore, since ā * x and E int( (x (a,)), then F int(XX, (a,)). However, if the internal point z belongs the hyperplane Hap and (az) C Hjs then it must be the case that Xe Xa(a) S Haj. This implies that Xe C xa.)))
and thus x E Xe (a.), which contradicts the hypothesis..
Given that there exists some (a,) with vol (a:) > 0 such that X.(a,) S Xa(a),, then X. =
(a(a,) O Xe (a,) is face of (a,) by Lemma 13
Lemma 12. Given the collection of polytopes (a. with volume larger than zero and an another action aj. then, under the event E", Algorithm 77 returns a (possibly improper) face Fela;) of (a,) such that Velag) S F.(a)). Furthermore, the Algorithm requires O(n(azz) calls to Algorithm 5
Proof. In the following, for the sake of notation, given a polytope X, (a) and the a set of hyperplanes H(a), with an abuse of notation we denote with X. H()) the intersection of (a) with every hyperplane in H(a). Formally:
X((a) n H(a)= = (x)a n n H.
(8)
HEM((a)
Suppose that (a,) = 6. Then, one can easily verify that Algorithm following we assume X (az) * (
11 returns D. Thus, in the
Let a; be action selected at Line 14 Algorithm 11 We denote with Fa(a.) the face returned by
Algorithm
= x n H(a)).
We observe that by Lemma 14 there exists an action da E C such that X: a face of X (ax).
Consequently, Algorithm| I queries every vertex E (a,).
32

---

As first step we show that Fe(a:) actually is a face of X. (a;) and contains every vertex of (ag)). Being the non-empty intersection of (a(a;) with some hyperplanes in M(XX(a))), F.(()) is face of X, (a,). One can easily prove by induction that H(a:) includes all and only the hyperplanes within M(X (a:)) containing every vertex in Ve(a,). Thus, Ve(a,) C Fe(a)).
Now we show that (a( is not only a (proper) face of X. (a:) containing the set Pa()), but also a face of Ka(a)) (possibly the improper face X. (a,) itself). We consider the set X. (a (a,)), which is a face of both X. (a;) and Xx (a,) thanks to Lemma 13
Thus, there exists some set of hyperplanes
H (a:) C ((Xe (a:)) such that:
x(()))())((()))) n
(9)
Furthermore, we observe that V.(ay) S Xa(a;) n ((())) Indeed, we have that (a,) S xa(a,) since V. (ay) S (a;) and (aa): face of Xa,),). and V.(a,) S Xa(a) by definition.
We want to prove that H'(a:) S H(a:)) where the set H(a:)) contains all and only the hyperplanes within (a)) that include the whole set Ve(a;) In order do that, suppose, by contradiction, that there exists a vertex x E (ay) such that x E H for some H E H' (a:). Then, æ E X, (a;) n H' (a;) H. However, we proved that Va(ay) (a,) n (az) and X. (as) (a(,)) X((a))
H'' (a:) by definition of H' (a:), reaching a contradiction.
Consequently:
F.(a:) = Xe(as) n =(aa))=
= x((ai)
N H
HEH(a)
( N
H
HEH((a:)
= =x((a)) = =X((ai) n (x());
where we applied Equation & the fact that H'' Ha(a;) H(a,). and Equation 9
Finally, we can show that Fa,), is a face of X. (a,)) We have that F.(a;) is face of (a:) and Fa(a)) C X, (a:) n (az), which is itself face of X. (a:) by Lemma 13 Thus, Fe(a.) is a face of
X. (a,) n (. Furthermore, Lemma 13 states that X. (ax) n (x()) 15 also a face of (a,). This
implies that (a,) is face of face of (a and thus face of (a,) itself.
In order to conclude the proof, we have to prove that at Line 14 Algorithm IT can actually find an action ag such that Fa,),) = X. (a:) n H(a,) is non-empty. Let dg C be such that Xe (a,) is face of X. (a which exists thanks to Lemma 14 as:
Let any vertex in the set Va(ag) and define H" (a,)
H. (ax) = (H E RM (X, x E H}. Then Xe n (ax) = {r). Consequently, H(ax) S Hax), and thus:
Xe(ax) n H((a)) (ex)x) n
0 I
HEH(az)
S xx((x)) n N
H
(EH"((a))
n (ax)
= {x} # 0.
As a result, there is always an action ds E such that (ax) H((a)) + 0.
Finally, we observe that Algorithm TT
executes Algorithm once for every vertex in the set Us,ec (a)),, which has size ((n(tT)).
F Omitted proofs from Section 5
Theorem 2. For any sender's algorithm, there exists a Bayesian persuasion instance in which d + 2 and the regret Ry suffered by the algorithm is at least 201), or, equivalently, 20(m)
33

---

Proof. In the following. for the sake of the presentation, we consider set of instances characterized by an even number d E N of states nature and n + 2 receiver's actions. All the instances share the same uniform prior distribution and the same sender's utility, given by (g(az+1) = 1 for (ad+1). Each instance is parametrized by
all E O and (a) = for all 0 E θ and Va vector p belonging to set y defined as follows:
d
P
p P
(0.1)*
Σ
Pr
Furthermore, we assume that the receiver's utility in each instance Tp is given by:
no, (az) = 6ig Vi,j E [d]. uo, (as+1) f.p. Vi E [d], uo, (dd+2)
Vi E [d].
We show that 6/ == 33p, for each i E [d] is the only posterior inducing the receiver's action ad+1 E A in the instance Ip. since the receiver breaks ties favor of the sender. To prove that, observe that the action 0d+1 is preferred to the action ad+2 only in those posteriors that satisfy the condition Eo. for each [d] with p; = Furthermore, to incentivize the action a2+1 over the set of actions a, with i [d]. the following condition must hold:
No (an-1) =
Σ iE(d/:pi>0
Eo,
2 max Eo,- d
2
se se|d::p
We notice that the last step holds only if Es, - 2/d for each i E [d] such that p. > 0. Consequently, since the number of &o. 0 is equal to d/2, it holds &o. 2/d for each i E [d] such that p; > 0. Thus, the only posterior inducing action ad+1 is equal to co == 3p:-
We also notice that, given p E P, the optimal signaling scheme y defined as 7(5") 1/2 and 7(=") = 1/2, with e A4 I58 expected sender's utility y equal 1/2.
el for each 0 E O. With a simple calculation, we can show that the
We set the time horizon T [IP|/4] to show that any algorithm suffers regret of at least 2(()). This is sufficient to prove the statement. We start by making the following simplifications about the behavior of the algorithm. First, we observe that if the algorithm can choose any posterior (instead of a signaling scheme), then this will only increase the performance of the algorithm. Consequently, we assume that the algorithm chooses a posterior & each round & [T].
Thus, we can apply Yao's minimax principle to show that any deterministic algorithm fails against a distribution over instances. In the following, with E P. Furthermore, we observe that the feedback of any algorithm is actually binary. Thus, it is easy the action is not ad+1, and (ii) it starts to play the optimal posterior when the action is ad+1 since found an optimal posterior.
consider uniform distribution over instances Ip
that an optimal algorithm works follows: (i) it ignores the feedback whenever
This observation useful for showing that any deterministic algorithm does not find a posterior that induces action 02+1 with probability of at least - IPI/(4/P)> 3/4 (since it can choose only [/Pl/4] posteriors among the /Pl possible optimal posteriors). Hence, by Yao's 's minimax principle, for any (randomized) algorithm there exists an instance such that the regret suffered in the T rounds is at least:
3T R 2 42
P
P
2
32
since [x] 2 x 1 2/2, for each x 2 Finally, we notice that [P] concludes the proof.
(.)) = 20(d), which
Theorem 3. For any sender's algorithm, there exists a Bayesian persuasion instance in which the regret Ry suffered by the algorithm is at least 2 (VVT).
Proof. To prove the theorem, we introduce two instances characterized by two states of nature and four receiver's actions. In both the instances the sender's utility is given by us (a1) un ((2) = 0 for
34

---

all A E + while up (as) = 1, 48, (ax) = 0 and up, (a.) = 0 4221 (as) = 1. The receiver's utilities and the prior distributions in the two instances are:
Me, = 2 + e, Hb:
-
Mg. 1 - c, P0z = 2 +e
2
Up (a1) [2+4r)) W02 (a1) [10- 20c)
U (a1) (2-4r)) U12 (a1)
[10+20c)
U2 (a2) (10+)0e)) , u0 (02) (2-1e)
"g (a2) (10-20e)' Ug (a2)
(2+44e
Ug (0z) 3
10 U8, (az) 10
3
Ug (a3) Iō Ugz (az)
3 2
3
10
Up (a4) O, u/ (a4) (2-4c)
U (a4) O, u (a4) (2+4cc
with 6 E (0, 1/s). With a simple calculation, we can show that, in both the two instances, for any signaling scheme á employing a generic set of signals S, the sender receives the following feedback:
1. Vs E S such that σe, (s) > Φ0, (s), then a (s) = a1-
2. Vs E S such that 0 < de, (s) < Φo (s), then a²
3. Vs E S such that de, (s) Φn (s). then a a3-
4. Vs S such that Φo, (s), then a as-
As result, for any signaling scheme the sender may commit to, the resulting feedback in each signal of the signaling scheme is the same. Thus, we assume without loss of generality, that the sender only commits to signaling schemes that maximizes the probability of inducing actions ag or a4. This is because, the sender does not gain any information by committing to one signaling scheme over another, while the signaling schemes that induce these two actions are the only ones that provide the sender with strictly positive expected utility.
Furthermore, thanks to what we have observed before, we can restrict our attention to direct signaling schemes, i.e., those in which the set of signals coincides with the set of actions. Thus, at each round, we assume that the sender commits to a signaling scheme o' of the form:
by (aa) = %/ (a3) = 0f.
86 (as) = 0, 08, 1-
(10)
b6 (a1) 1 - Φi 06 (an) 0,
with oj E [0, 1]. We also notice that, in each round, the optimal signaling scheme in the first instance is the one that induces action d3, meaning of = 1 for each t E [Z']. While the optimal signaling scheme in the second instance at each round is the one that reveals the state of nature to the receiver,
meaning of = 0 for each t E [2'] In such way, the learning task undertaken by the sender reduces to select value of of [o. 1] for each E [T] controlling the probability of inducing action ag over action 04.
In the following, we define Id (P²) as the probability distribution generated by the execution of given algorithm in the first (second) instance and we let E (E²) be the expectation induced by such distribution.
The cumulative regret in the first instance can be written as follows:
T
te- oi (-+c) +c) - (1 (1- Φi) (2-c))
R = E
2
T
2cE
Σ
(1
øi)
/=1
Similarly, in the second instance, the cumulative regret is given by:
T
R2 = 2c1
Σ di
Furthermore, it is easy to check that:
T eT
T
R2. 2 IP
$ ST/2
and
R2 > p2
Σ
T/2
ET.
35

---

By employing the relative entropy identities divergence decomposition we also have that:
KL (PP) 1P2) T KCC (p*,,²) 1²)
2 - 22T'',
64 Te
where we employed the fact that for two Bernoulli distribution it holds
KL((Be(p), Be(g)) _ (p 9)²
q(1 q)
Then, by employing the Bretagnolle Huber inequality we have that,
T + 1p²
))
R +
+ 2I eI
IPl
Σ [=1
o ST/2
Σ d 0o022/2
1=1
Σ ET
exp
(-KL (PL P2))
2
1
2 T exp (-22T 2
By taking V 227 get:
R R2 2 CIVT.
with C1 ==-l/222/ Thus, we have:
2222V VT
R
V
R C1 2
VT,
concluding the proof.
G Details and omitted proofs from Section
6
G.1 Compute-Thresholl procedure
The Compute-Threshol/ procedure takes input real parameter E > 0. Then, it iteratively halves the value of a different parameter e, initially set to one, until it is smaller than or equal to éi. In this way, Algorithm 12 computes parameter E [e1/2, e1] in Ollo()/ee)) rounds with bit complexity B. = (log((/a.)) This technical component is necessary to ensure that the bit- complexity of the parameter is not too large while guarantecing that the solution returned by Algorithm is still 7-optimal with probability at least 1 -77. 7).
Algorithm 12 Compute-Threshold Threshold
Require: E 10,
1: 6- 1
2: while éi do
3: cfe/2
4: Return e
G.2 Omitted proofs from Section 6
Lemma 5. Given Ti = 2 log (24(8) and E (0, Algorithm 2 employs Ti rounds and outputs
X. C X such that, with probubility at least 1 - 8: (i) Eoee M4 for every slice E X., (ii) Epco Hezo S 6e for every slice a E X Xe, and (iii) [āg μel S e for every 0 E θ.
Proof. Thanks to the definition of Ti == [1/2,2 log (24/8)] in Algorithm and employing both a union bound and the Hoeffding bound have:
P (I nel I c) 21 5, 4P E e.
36

---

Consequently, if P H4l I for each & ④ then for each I E Ne, the probability of inducing the slice æ can be lower bounded as follows:
Σ
Poro
Σ
(To eetr S
Σ
pozo
BEE
BE8
6E6
where the above inequalities hold because each x E X₂ satisfies the constraint Eoe@r PoTa Furthermore, if وīg
2 2c.
pel I for each 0 E θ then for each æ & X. the following holds:
Σ poza I c+
(mo- S c Σ Taze I 3c,
(11)
BEE'
MEBr
since, if x & N, it holds
Enger Pawaa S 2e, and,
Σ
pozo I
Σ (no c) + Σ
Pazo + c 3c.
(12)
eger
8ge'
eger
Thus, by combining Inequality (11) and Inequality (2).. we have:
Mg2o 6c,
when x & X. concluding the proof.
Theorem 4. Given 7 E (0, 1) and n E (0, 1), with probability at least 1 - 1), Algorithm ouiputs y-optimal signaling scheme in a number of rounds such that:
T δ
n3
log2
())
()) ((+tt)))))) ()
72
d
Proof. Thanks Lemma with probability least 1 8 = 1 1-1/2 Algorithm 4 correctly completes Phase 1 in Ti = 00/2 log( 1/)) log(d)) rounds. Thus, with probability at least 1 - -/2,, both the event & and the inequalities Tمo pel for each & @ hold.
Consequently, under the event E,. with probability at least partitions the search space X, in at most:
1- 1 1/2, Algorithm correctly
δ n
log² ()) (oFL+(+t)))
(dtnl))
d
d
rounds, stated by Lemma 3 Furthermore, notice that = B B. + Ba. with:
Ba = (log((T)) O (log(1/s) + log(t/n) + log(d)).
As result, with probability at least 1 Algorithm E correctly terminates in a number of rounds N which can be upper bounded follows:
log(d) + n²
(B(BBB))) (3)++B)++ (
( ;
dd+n) (1d ))
S log
log?
Furthermore, we observe that if lioe - Hol S for each f E O then the following holds:
Σ dEE
jo
S
Σ T OE
pel < Σ = =d.
Consequently, thanks to the result provided by Lemma with probability at least 1 77, Algorithm 4 computes 12ncd-optimal solution. Thus, by setting 6 7/12nd and S 61, with probability at least 1 Algorithm computes 7-optimal solution in a number of rounds N bounded by:
n nd
n
(1]
dd B.) + +d ( ))
d (d+n)
N
log
+
log2
22
11
7
n
1
+ B.) + d dd+) ))
log²
d8
22
d
3
8d + d dd+n)) )
log²
where the last equality holds because the bit-complexity of B. = (log((dd/))) concluding the proof.
D
37

---

Theorem 5. There exist two absolute constants À O such that no algorithm is guaranteed to return a k-optimal signaling scheme with probability of at least 1 by employing less than 2 and 20(d) rounds, even when the prior distribution is known to the sender.
we showed that, with probability 9/4, in N [IPl/1] rounds any algorithm does not correctly Identify the posterior inducing action ad+11 This is because, any deterministic algorithm can identify the optimal posterior only in [IP1/4] instances, as observed the proof of Theorem 2
Proof. In the proof of Theorem 2
As result, in the remaining [P| N instances, any deterministic algorithm will receive the same feedback and thus will always output the same posterior after rounds, which will result in the optimal one in only single instance.
Thus, thanks to the Yao's minimax principle, there is no algorithm that is guaranteed to return an optimal solution with probability at least:
P N -1 3 P -
P N [P] N 8
Finally, we observe that OPT = 1/2, while any algorithm that does not induce the posterior Ç' provides an expected utility equal to zero. As result, each x < 1/2 there no algorithm that guaranteed return a solution which k-optimal in [PP|/4] 20(d) rounds with probability at least 3/8.
Theorem 6. Given E (0, 1/) and E (0, 1), algorithm is guaranteed to return y-optimal signaling scheme with probability at least 1 by employing less than 92 (og//o)()/))) rounds.
Proof. To prove the theorem, we consider the same instance and the same definitions introduced in the proof of Theorem 3 In this case, we let P' (IP2) be the probability distribution generated by the execution of given algorithm in the first (second) instance for N [log(1/An//22e" rounds. Furthermore, we introduce the event under which the signaling scheme returned the round N, according to the definition presented in Equation 10, is such that &~V < 1/2. We notice that, if such signaling scheme such that &º < <1/2, then the sender's expected utility in the first instance is smaller equal to 1 1/2, thus being c/ e/2-optimal. At the same time, if N > 1/2 in the second instance, then the solution returned by the algorithm not e/ e/2-optimal.
Thus, by employing the Bretagnolle-Huber inequality we have:
1 pl (E) + P2 (8 2 exp (CK
exp (-22Ne?).
2
since K.C (P1 1P2) < 22 as observed in the proof of Theorem 6 Finally, by employing the definition of N, have:
P P' V p2 (8 n
As result, by setting 2 e, the statement of the lemma holds.
H Sample complexity with known prior
In this section, we discuss the Bayesian persuasion PAC-learning problem when the prior distribution is known to the sender. To tackle the problem, we propose Algorithm [3] The main difference with respect to Algorithm 4 that, this case, we do not need to employ the Weiild-earrc-Spaae procedure, as the prior is already known to the sender. This allows us to compute 7-optimal signaling scheme in only (117)) rounds, instead of O(1/²) rounds as in the case with an unknown prior.
38

---

Algorithm 13 33PAC-PPreuuasiooo-oo--C-C-----
Require: 7/ (0, 1), (0,1), Ae
I: él f 7/10nd
2:
Srppute--Esiiootti
3: θ - {0 [i > ]
4: X. - f Eoc3 Pa 2
5: R. +- Hind-Polytopes(4 (M X, 11)
6: Φ Compute-Signalling Re, Ne,
7: return
In this case, the following theorem holds.
Theorem 7. With probability at least 1 - y, and in Algorithm 2 computes a y-optimal signaling scheme in ① 1²/> (1/n) (do + d( d(()tr)) rounds.
Proof. Since jī = jr, the clean event & holds with probability one. Consequently, thanks to Lemma with probability at least Algorithm 13 correctly partitions the search space A' in at most:
n²
log (V/) ( 1+
( ( (at+t))
d
rounds. with L : B+B. B.+ B2. According to Algorithm 13 we have S. == 7/(10nd). As result,
== O (B + log(nd) + log(1/>)), since Bp < and B. (log(?/(1)) = (llg((nd) + log()/)))
Furthermore, under the event &g, Algorithm computes 10end-optimal solution, guaranteed by Lemma with ç = μ.
Thus, with probability at least Algorithm 13 computes a 7-optimal solution in:
δ n - log² (1/1) ( d d (dtt)))) (1)+)((t)))
rounds, concluding the proof.
We notice that, differently from the case with an unknown prior, is possible to achieve O (log(1/n//>) upper bound with respect to the input parameters 7, >> 0. Finally, we show that such a dependence tight, as shown in the following theorem.
Theorem 8. Given Y, 17 > 0 no algorithm guaranteed return an y-optimal signaling scheme with probability of at least y employing Ω (log(1/nl/z) rounds, even when the prior distribution is known to the sender.
Proof. We consider two instances characterized by states of nature and three receiver's actions.
The two instances share the same prior distribution, defined as μe, = 4ry and μ4; = 1 - 47. both the instances the sender's utility is given by va(a)) 0, už (a2) 1/2 and ui (ag) Furthermore, we assume that the receiver's utility in the two instances are given by:
for all 0 O.
uo (a1) = 1, uz (a1) 1/2 1 nig (a2) 1/2, u82 (a2)
un (a1) 1, us, (a1) ) 1/2
uo (az) 1/2, uæz (az)
Uo, (aa) = 1, ue, (aa) =
uo (aa) = 1/2, us, (ag) = 0
We observe that the only case which the sender receives different feedback in the two instances is when they induce the posterior distribution & := (1, 0). This is because, when the sender induces & in the first instance, the receiver plays the action a3 E A. breaking ties favor of the sender, while in the second instance, the receiver plays the action E A. Such posterior can be induced, in both the two instances, with probability of at most to be consistent with the prior.
We also observe that in the first instance the optimal sender's signaling scheme is such that (()) = 4y and (E2) 1-44 -4, where we let & == (0, 1). Furthermore, the sender's expected utility in is equal to (1 + 42) In the second instance, the optimal sender's ''s signaling scheme
39

---

is such that ((2) 1 1 8y and r(53) 8%, with E3 := (1/2. It is easy to verify that such signaling scheme achieves an expected utility of 1/2.
In the following, we let IPI and Ip2 be the probability measures induced by the interconnection of given algorithm executed in the first and in the second instances, respectively. Furthermore, introduce the event E'y, under which, during the first N rounds, the sender never observes the action a3 A. It easy verify that such an event holds with a probability of at least IP (En) 2 (1-47)
in the first instance. This is because, at each round, the action d3 can be observed with a probability of at most 4y. contrast, since in the second instance the receiver never plays the action ag, it holds (Ex) = 1 2 (1 - 4y)"
Then, by letting y/ (122) be the signaling scheme returned after N rounds in the first (second) instance, we have:
pa (G1) 2 27)
+ F2 (72 (G) 22) 2 P' (1) (5i) 2n, Ex) + pD (1² (E1) S 2y, EN) (E1)
2 pl (1i (51) 27 BN) Pd (Ex) + (12 (5i) S 27 |EN) F2 (En)
2 (I'' (n 2 2> [BN) + 12 (12 (51 - 27 [Bx)) Pp' (En)
pd (EN)
2 (1 - 4y) 2 2m.
(13)
The above result holds observing that, under the event EN, the behaviour of any algorithm working in the first instance coincides with the behaviour of the same algorithm working in the second one, as they receive the same feedback. Furthermore, Inequality 13 holds when N is such that:
log(1/2m) log(2n) 10y
N S
log(1 47)
if y S 1/5.
Finally, we observe that if 7/ (E:) S 2y, then the sender's expected utility in the first instance is of most 1/2 + This is because, for any signaling scheme y/" we have:
1
u u²(x"" S M (E)) 2 (1- (L1) =
2 +7
Thus, if 7f S 2y the the signaling scheme 7 is at most 7-optimal.
Equivalently, if the sender's final signaling scheme 7/2 in the second instance is such that 7/2 (E1) >
2y, then the sender's utility in the second instance is of at most 1/2 7. Thus, if 72 (E1) 2 2n the
the signaling scheme 2/2 most y-optimal. Then, we either have:
Pd (M (61) S 27) 2 or p2 (72" (E.) 2 27) 2 n
showing that if the number of rounds N < 1og(1/2n)/(10)) there exists an instance such that no algorithm guaranteed return 7-optimal signaling scheme with probability greater than equal to
40

---

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

---

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

---

Answer:
[N]]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuii wwwiiicgguie///eeeeeeeeic CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
43

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

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

---

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


Reviews:
[{"review_id": "Q4O6vPb2A8", "reviewer": "Reviewer_UDVm", "summary": "The paper studies online Bayesian persuasion problems in which an informed sender\nrepeatedly faces a receiver with the goal of influencing their behavior through the provision of payoff-relevant information. The paper considers a setting where the sender does not know anything about the prior and the receiver’s utility function. At each round, the sender commits to a signaling scheme, and, then, they observe a state realization and send a signal to the receiver based on that. After each round, the sender gets partial feedback, namely, they only observe the best-response action played by the receiver in that round.\n\nThe main results of this paper are: (1) providing a learning algorithm that achieves $\\tilde{O}(\\sqrt{T})$ regret, and this regret bound has exponential dependence on the number of states $d$ and the number of receiver’s actions $n$; (2) a set of lower bounds showing that such $\\sqrt{T}$-dependency is optimal, and such exponential dependency on $d, n$ is also optimal; (3) extending the no-regret learning algorithm to establish the sample complexity of the Bayesian persuasion PAC-learning problem.", "questions": "It may be nice to present the $\\tilde{O}(n^d \\sqrt{T})$ regret and the $\\tilde{O}(d^n \\sqrt{T})$ regret as the two corollaries of the Theorem 1. \n\nIt is indeed a bit interesting to me that the unknown of both prior and receiver’s utilities make the learning problem significantly challenge: one has to incur $\\sqrt{T}$-regret. Do you have intuitions on  this $\\sqrt{T}$-regret is mainly due to unknown receiver's utilities or the unknown priors? \\\n-- It seems that lower bound $\\sqrt{T}$ in Theorem 3 requires 4 receiver’s actions. Does $\\sqrt{T}$ lower bound also hold if receiver only has binary actions? Do authors feel the regret may be improved (e.g., $\\Theta(\\log T)$ or even $\\Theta(\\log\\log T)$) if one consider only BINARY receiver action? As in the paper \"EC’21-Online bayesian recommendation with no regret\", the authors show that when the sender only does not know the receiver’s utilities, a regret $\\Theta(\\log\\log T)$ by some variant of binary search is attainable but focusing on binary actions. (So I kind of feel your $\\sqrt{T}$-regret may be mainly due to unknown prior of the state realizations)\n\nI would imagine that most of the results still hold even if the receiver has a different unknown prior to the sender (but the stats are still realized from sender's unknown prior), right?", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I truly enjoy reading this work. I think this work significantly contributes to the recent line of research on using regret minimization to study the persuasion with uncertainty over the underlying environments. The results developed in this work are strong and interesting. The presentation of this work is crisp and the paper provides intuitions for the algorithmic challenges and its steps of algorithm design. Overall, I think this work makes a strong addition to the NeurIPS.", "weaknesses": "I don’t have particular concerns about the paper. Maybe one minor point is that the authors may want to include some discussions about the computational efficiency of the designed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the insightful comments. We will adopt them in the final version of the paper and we will better discuss the points suggested by the Reviewer.\n\n> It is indeed a bit interesting to me that the unknown of both prior and receiver’s utilities make the learning problem significantly challenge: one has to incur $\\sqrt{T}$-regret. Do you have intuitions on this $\\sqrt{T}$-regret is mainly due to unknown receiver's utilities or the unknown priors?\n\nThe $\\Omega(\\sqrt{T})$ regret lower bound is a consequence of the sender's lack of knowledge of **both** the receiver's utilities and the prior distribution. \nIndeed, in our setting, it is possible to construct two instances with similar prior distributions and define the receiver's utilities so that the sender gains no information to distinguish between the two instances by committing to any signaling scheme.\nThis is not possible if the utilities are known.\nConsequently, to distinguish between the two instances, the sender can only leverage the information contained in the states of nature sampled at each round and this results in the regret being at least $\\Omega (\\sqrt T)$.\n\n\n> It seems that the lower bound $\\sqrt{T}$ in Theorem 3 requires 4 receiver’s actions. Does the $\\sqrt{T}$ lower bound also hold if the receiver only has binary actions? Do the authors feel the regret may be improved (e.g., $\\Theta(\\log T)$ or even $\\Theta(\\log \\log T)$) if one considers only binary receiver actions? As in the paper \"EC’21—Online Bayesian Recommendation with No Regret,\" the authors show that when the sender only does not know the receiver’s utilities, a regret of $\\Theta(\\log \\log T)$ by some variant of binary search is attainable when focusing on binary actions. (So I kind of feel your $\\sqrt{T}$-regret may be mainly due to the unknown prior of the state realizations).\n\nDeveloping a regret lower bound for instances with binary actions is an interesting research direction that we intend to explore in the future. We leave as an open problem whether it is possible to construct two instances similar to those presented in our lower bound, but with binary receiver actions, and still achieve a $\\Omega(\\sqrt{T})$ regret lower bound or a better upper bound can be achieved. \n\n\n> I would imagine that most of the results still hold even if the receiver has a different unknown prior to the sender (but the stats are still realized from sender's unknown prior), right?\n\nThe Reviewer is right. Our algorithm can also be employed in settings where the receiver has a different prior but the states of nature are sampled from the sender's unknown prior. We will better outline this aspect in the final version of the paper.", "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": "", "extra_scores": {}}, {"review_id": "BMoym5eLGY", "reviewer": "Reviewer_cPaK", "summary": "The paper studies Bayesian persuasion in a learning setting with minimum knowledge about the receiver: neither the receiver's prior nor their utility function is known. In the model, the sender can commit to different signaling strategies and acquire the receiver's optimal response to each signal they send. The paper presents a learning algorithm that achieves regret sublinear in the number of rounds but exponential in the number of states. The authors further show that the exponential dependency on the number of states is inevitable by proving a matching sample complexity.", "questions": "- In algorithm 2, the feedback a^t and u_t^s seem not useful? If so, better to remove this line?\n\n- What would happen if the receiver is not truthful? And since the receiver knows their prior, does it make sense to design a mechanism to directly elicit this prior knowledge?", "limitations": "Nothing is mentioned, but no concern here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper follows a line of work in the literature on Stackelberg games that study how to learn to commit optimally by querying the follower's optimal responses. I find it natural and reasonable to ask the same question in Bayesian persuasion. While the overall approach works similarly by building the follower's (receiver's) best response regions, the paper shows that there are some unique features of the persuasion setting, which require additional techniques. \n\nThe estimation of the prior, in particular, can only be done approximately. The paper nicely handles this aspect in their algorithm. The concept of slice is also novel and interesting (though the naming is somewhat less intuitive). \n\nThe results look very complete, with matching lower and upper regret bounds. The paper is also well-writen and overall clear.", "weaknesses": "- The part below Definition 1 until the end of that page is a little dense and could probably be improved. The notation in this part is also a bit hard to follow. However, this is overall minor. \n\n- Line 296: It might be better to be a bit more specific about the distinguished features here.\n\n- Is there any justification how the receiver gets to know the sender's strategy $\\phi_t$ in each round? How would the results change if the receiver only observes the sender's signal in each round?\n\nTypos: \n\n- Line 51: of much (how much?)\n\n- Line 314: clean event", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the insightful feedbacks and for pointing out some typos. Specifically, we will do our best to improve the part below Definition 1  and the comparison between previous models at Line 296 in the final version of the paper.\n\n> Is there any justification how the receiver gets to know the sender's strategy $\\phi_t$ in each round? How would the results change if the receiver only observes the sender's signal in each round?\n\nThe assumption that the receiver gets to know the sender's signaling scheme (a.k.a. the commitment assumption) is inherent in every Bayesian persuasion model. Moreover, the same assumption is standard in online Bayesian persuasion settings, where the receiver observes the sender's signaling scheme $\\phi_t$ at each round $t \\in [T]$. See, e.g., Castiglioni et al. (2020b) and Zu et al. (2021).\n\nNotice that, by dropping the commitment assumption, one falls in a completely different model, which is commonly referred to as \"cheap talk\" in the economic literature. Indeed, if the receiver only observes a signal $s \\sim \\phi_{t, \\theta_t}$ sampled from the signaling scheme $\\phi_t$  at round $t$, without knowing $\\phi_t$, it is not immediate how to define a best response for the receiver. We believe that addressing online learning problems in such a different setting is a very interesting research direction that is worth addressing in the future. \n\n\n> In algorithm 2, the feedback $a^t$ and $u_t^s$ seem not useful? If so, better to remove this line?\n\nWe agree with the Reviewer, we will omit it from Algorithm 2.\n\n\n> What would happen if the receiver is not truthful? And since the receiver knows their prior, does it make sense to design a mechanism to directly elicit this prior knowledge?\n\nAddressing settings with a non-truthful receiver is an interesting research direction that we intend to explore in the future. This begets considerable challenges that are out the scope of this paper.\n\nDesigning a mechanism in which the sender elicits information from the receiver's knowledge of the prior is certainly an interesting idea. However, since the sender has never access to the receiver's payoffs, it is not clear how the sender could effectively benefit from the receiver's knowledge of the prior. Indeed, receiver's best responses depend on both the unknown prior and receiver's unknown payoffs, which makes it challenging to extract information about the prior only.", "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": "", "extra_scores": {}}, {"review_id": "7NDcu8ZAPa", "reviewer": "Reviewer_YTqh", "summary": "This paper studies repeated Bayesian persuasion where the sender does not know the prior distribution of the state of the world and the receiver's utility (while the receiver knows the prior and their utility and myopically best responds in each period). The authors design online learning algorithm for the sender to achieve sublinear regret $O( binom(d+n, d) n^{3/2} d^3 \\sqrt{BT})$. They also prove lower bounds of $2^{\\Omega(d)}$ and $2^{\\Omega(n)}$. The proposed algorithm, a sophisticated explore-than-commit algorithm, works by searching the space of signaling schemes under a non-standard representation.", "questions": "Can the authors respond to weakness (1)?", "limitations": "**Suggestions:**\n\n(1) Please define the B in algorithm 1 more clearly.\n\n(2) In Appendix A Additional Related Works, in additional to saying what the related works did, please briefly compare those works with your work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) [Significance] This work is a significant improvement over previous works on online learning in Bayesian persuasion where the sender learns either the prior or the receiver's utility. Learning the prior and utility simultaneously seems to be challenging. The authors are able to solve this problem, which is a significant contribution.\n\n(2) [Originality] A key technique in this work is performing high-dimensional binary search in the space of signaling schemes under a non-standard representation. In previous works, signaling schemes were usually represented by distributions over posterior distributions, and the search was performed on the space of posterior distributions. Such a technique does not work when the prior is unknown. This work instead represents signaling schemes by the vector $(\\sigma_\\theta(s))_{\\theta \\in \\Theta}$, the probabilities of sending a signal $s$ under different states $\\theta$. This new representation circumvents the unknown prior issue. So, I think this new representation is an interesting trick and a technical novelty.\n\n(3) [Quality] Non-trivial lower bound results are provided, complementing the upper bounds results.", "weaknesses": "(1) [Quality] The proposed algorithm seems to have an exponential running time in the worst case. Specifically, the number of vertices $\\mathcal V$ of the polytopes seem to be exponential in $d$ or $n$, which leads to an exponential running time. The authors didn't discuss the computational complexity of their algorithm, nor provided a computational-hardness result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the insightful feedbacks. We will also incorporate the two Reviewer's suggestions in the final version of the paper.\n\n> The proposed algorithm seems to have an exponential running time in the worst case. Specifically, the number of vertices $\\mathcal{V}$ of the polytopes seem to be exponential in $d$ or $n$, which leads to an exponential running time. The authors didn't discuss the computational complexity of their algorithm, nor provided a computational-hardness result.\n\nWe thank the Reviewer for giving us the opportunity to better clarify this aspect of our paper. \nThe per-round running time of our algorithm is polynomial in the size of the input when either the number of receiver’s actions $n$ or that of states of nature $d$ is fixed. \nWe agree with the Reviewer on the fact that, if both $n$ and $d$ are not fixed, then the per-round running time may no longer be polynomial in the input size in the worst case.\n\nWe observe that Algorithm 6 can find the H-representation of the polytopes $\\mathcal{X}\\_\\epsilon(a)$ with polynomial per-round running time.\nIn particular, to enumerate the vertices of the upper bounds, it can compute and query a different vertex at each round, without ever storing them all.\nIn the current version, given the H-representation of the polytopes, our algorithm also computes the set of all the vertices $\\mathcal{V}$, and eventually employs this set to instantiate an LP, whose cardinality may be exponential in either $n$ or $d$.\nHowever, it is possible to avoid computing these vertices and solve an equivalent linear program whose size is polynomial in $n$ and $d$. \nThis can be done by employing the H-representation of the polytopes $\\mathcal{X}\\_\\epsilon(a)$ computed by Algorithm 6, and exploiting a slightly different LP. \nThis approach does not require to compute $\\mathcal{V}$, thus achieving a polynomial per-round running time in every phase of the algorithm.\n\t\nThe theoretical analysis with the modified LP is almost straightforward given the results presented in the paper, as it only requires the introduction of some additional technical lemmas about polytopes. \nWe will include this algorithmic approach in the final version of the paper and we are happy to provide additional technical details, if the Reviewer wants to.\n\n\n> (1) Please define the B in algorithm 1 more clearly. (2) In Appendix A Additional Related Works, in additional to saying what the related works did, please briefly compare those works with your work.\n\nWe thank the Reviewer for the suggestions; we will incorporate them into the final version of the paper.", "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": "", "extra_scores": {}}, {"review_id": "zWMZW3FYNM", "reviewer": "Reviewer_yxNt", "summary": "The paper studies online Bayesian persuasion with \"no clue\", i.e., the sender knows nothing about the prior distribution or the receiver's utility function a priori (it is however assumed that there exists a prior distribution and states are drawn iid from it).  The main results are (1) in the online model where the sender tries to learn a good signaling scheme on the fly while not losing too much utility in the process, there is an algorithm that achieves square-root regret, (2) lower bounds showing that the dependency of this regret bound on various parameters are in a sense unavoidable, and (3) in the PAC model, an adapted algorithm that achieves a nontrivial sample complexity bound.", "questions": "(also including detailed comments)\n\nLine 22, \"such as, e.g., ...\": a bit repetitive?\n\nLine 92: superscript missing in the definition of $u_\\theta^s$?\n\nFootnote 1: might as well quickly define int while you are defining $\\Delta$\n\nLine 110: missing \")\"\n\nSec 3: the title was a bit confusing to me, but I think the section as a whole is very helpful for a non-expert reader to develop intuition.  It's also very clearly written.\n\nLine 218: \"sufficiency\"\n\nOverview part of sec 4: my first instinct is that explore-then-commit strategies normally give regret bounds like $O(T^{2/3})$.  This will probably become clear soon, but it might help to quickly discuss why you were able to get square-root regret here.  (My guess is somehow you managed to stay in the \"realizable\" regime where learning up to eps requires only 1/eps rounds.)\n\nSec 6: maybe quickly introduce the setup first (in particular, what is a \"sample\" here)?  Relatedly, it's also interesting that here you get $1/gamma^2$ instead of $1/\\gamma$,", "limitations": "No concerns.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem appears meaningful and technically interesting.  The idea of slices is natural, clean and powerful.  The overall plan is clearly plausible, and yet not obviously viable.  I'm happy to see that the authors were able to make it work, which seems to have involved nontrivial effort.  The bound is reasonably tight.", "weaknesses": "Ideally an instance-optimal bound would be more exciting, but perhaps that's too much to ask for.  I'd also like to see more discussion of the PAC model and the optimality of the bound in that model (if applicable).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the insightful feedbacks and for pointing out some typos. We will incorporate these suggestions and correct the typos in the final version of the paper. \n\n> Overview part of sec 4: my first instinct is that explore-then-commit strategies normally give regret bounds like $O(T^{2/3})$. This will probably become clear soon, but it might help to quickly discuss why you were able to get square-root regret here. (My guess is somehow you managed to stay in the \"realizable\" regime where learning up to eps requires only 1/eps rounds.)\n\nThe Reviewer is right. The main reason we do not incur in a $O(T^{2/3})$ regret is that we can build a space of signaling schemes slices in $O(1 / \\epsilon)$ rounds, such that, for each element, it is possible to associate a receiver's best response in $O(1 / \\epsilon)$ rounds.\nTechnically, this is made possible by employing the multiplicative Chernoff bound, which allows us, with $O(1 / \\epsilon)$ rounds, to distinguish which states $\\theta \\in \\Theta$ have a probability of being observed smaller than $\\epsilon$, i.e., $\\mu_\\theta \\le \\epsilon$.\nIn this way, the \"exploration phase\" of our explore-then-commit approach requires $O(1 / \\epsilon)$ rounds, allowing us to achieve a $\\sqrt{T}$ regret, by suitably choosing $\\epsilon = O(1/\\sqrt{T})$, instead of $O(T^{2/3})$ regret, as it is typically the case in explore-then-commit approaches.\n \t\nFinally, we observe that in our \"commit\" phase, the sender does not commit to a fixed signaling scheme. Instead, they select a different signaling scheme $\\phi_t$ computed by means of Algorithm 3, which receives as input an estimate of the prior distribution $\\widehat \\mu_t$ that is updated at each round.\n\n\n> Sec 6: maybe quickly introduce the setup first (in particular, what is a \"sample\" here)?\n\nWe thank the Reviewer for giving us the opportunity to better clarify the concept of ``sample'' within our framework.\nWe use the term \"sample\" to refer to the feedbeack received by the sender when they commit to a signaling scheme.\nIntuitively, in a PAC-learning problem we do not have a finite time horizon, nor we are interested in the regret. \nInstead, we want to learn a $\\gamma$-optimal solution by using the minimum possible number of samples (or equivalently, rounds), and we are not concerned about the regret accumulated while learning it.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers are positive about the paper. They consider the paper significant in the online Bayesian persuasion literature. They like the paper's concept of slice. And they are happy with the paper's presentation and completeness.
Decision: Accept (spotlight)