Online Bayesian Persuasion Without a Clue

Authors: francesco  bacchiocchi
matteo  bollini
matteo  castiglioni
alberto  marchesi
nicola  gatti
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:52:47

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.

Main paper: 
 introduction: 
 Bayesian persuasion has been introduced by Kamenica and Gentzkow [2011] to model how strategically disclosing information to decision makers influences their behavior. Over the last years, it has received a 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 a consequence, Bayesian persuasion has been applied in several settings, such as online advertising [Emek et al., 2014 , Badanidiyuru et al., 2018 , Bacchiocchi et al., 2022 , Agrawal et al., 2023] , voting [Alonso and Câmara, 2016 , Castiglioni et al., 2020a , Castiglioni and Gatti, 2021] , traffic routing [Vasserman et al., 2015 , Bhaskar et al., 2016 , Castiglioni et al., 2021a] , recommendation systems [Cohen and Mansour, 2019, Mansour et al., 2022] , security [Rabinovich et al., 2015 , Xu et al., 2016 ], e-commerce [Bro Miltersen and Sheffet, 2012, Castiglioni et al., 2022] medical research [Kolotilin, 2015] , and financial regulation [Goldstein and Leitner, 2018] .In its simplest form, Bayesian persuasion involves a 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 is to devise a 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 a 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., 2023] ) or receiver's utilities (see, e.g., [Zu et al., 2021 , Bernasconi et al., 2022 , Wu et al., 2022] ).We address-for the first time to the best of our knowledge-Bayesian persuasion settings where the sender has no clue about the surrounding environment. In particular, we study the online learning problem faced by a sender who repeatedly interacts with a receiver over multiple rounds, without knowing anything about both the prior distribution over states of nature and receiver's utilities. 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. In such a setting, the goal of the sender is to minimize their regret, which measures how much utility they lose with respect to committing to an optimal (i.e., utility-maximizing) signaling scheme in every round.We provide a learning algorithm that achieves regret of the order of O( √ T ), 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, i.e., the number of states of nature d and that of receiver's actions n. Our algorithm implements a sophisticated explorethen-commit scheme, with exploration being performed in a suitable space of signaling schemes so as to learn receiver's best responses exactly. This is crucial to attain tight regret guarantees, and it is made possible by employing a non-standard representation of signaling schemes, which allows to cleverly overcome the challenging lack of knowledge about both the prior and receiver'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-optimal 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 utilities (see also follow-up works [Castiglioni et al., 2021b , 2023 , Bernasconi et al., 2023] ). In their setting, sender's uncertainty is modeled by means of an adversary selecting a receiver's type at 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.A parallel research line has focused on relaxing sender's knowledge about the prior. Zu et al. [2021] study online learning in a repeated version of Bayesian persuasion. Differently from this paper, they consider the sender's learning problem of issuing persuasive action recommendations (corresponding to signals in their case), where persuasiveness is about correctly incentivizing the receiver to 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. Wu et al. [2022] , Gan et al. [2023] , Bacchiocchi et al. [2024c] achieve similar results for Bayesian persuasion in episodic Markov decision processes, while Bernasconi et al. [2022] 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 as well.Finally, learning receiver's best responses exactly (a fundamental component of our algorithm) is related to learning in Stackelberg games [Letchford et al., 2009 , Peng et al., 2019 , Bacchiocchi et al., 2024a] . For more details on these works and other related works, we refer the reader to Appendix A. 
preliminaries: 
 In Section 2.1, we introduce all the needed ingredients of the classical Bayesian persuasion model by Kamenica and Gentzkow [2011] , 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.A Bayesian persuasion instance is characterized by a finite set Θ := {θ i } d i=1 of d states of nature and a finite set A := {a i } n i=1 of n receiver's actions. Agents' payoffs are encoded by utility functions u, u s : Θ × A → [0, 1], with u θ (a) := u(θ, a), respectively u s θ (a) := u s (θ, a), denoting the payoff of the receiver, respectively the sender, when action a ∈ A is played in state θ ∈ Θ. The sender observes a state of nature drawn from a commonly-known prior probability distribution µ ∈ int(∆ Θ ),1 with µ θ ∈ (0, 1] denoting the probability of θ ∈ Θ. To disclose information about the realized state, the sender can publicly commit upfront to a signaling scheme φ : Θ → ∆ S , which defines a randomized mapping from states of nature to signals being sent to the receiver, for a finite set S of signals. For ease of notation, we let φ θ := φ(θ) be the probability distribution over signals prescribed by φ when the the sate of nature is θ ∈ Θ, with φ θ (s) ∈ [0, 1] denoting the probability of sending signal s ∈ S.The sender-receiver interaction goes as follows: (1) the sender commits to a signaling scheme φ;(2) the sender observes a state of nature θ ∼ µ and sends a signal s ∼ φ θ to the receiver; (3) the receiver updates their belief over states of nature according to Bayes rule; and (4) the receiver plays a best-response action a ∈ A, with sender and receiver getting payoffs u θ (a) and u s θ (a), respectively. Specifically, an action is a 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 φ : Θ → ∆ S and a signal s ∈ S, we let A φ (s) ⊆ A be the set of receivers' best-response actions, where: A φ (s) := a i ∈ A | θ∈Θ µ θ φ θ (s)u θ (a i ) ≥ θ∈Θ µ θ φ θ (s)u θ (a j ) ∀a j ∈ A .(1)As customary in the literature on Bayesian persuasion (see, e.g., [Dughmi and Xu, 2016] ), 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 ∈ S under signaling scheme φ, with a φ (s) ∈ arg max a∈A φ (s) θ∈Θ µ θ φ θ (s)u s θ (a). The goal of the sender is to commit to an optimal signaling scheme, namely, a φ : Θ → ∆ S that maximizes sender's expected utility, defined as u s (φ) := s∈S θ∈Θ µ θ φ θ (s)u s θ (a φ (s)). In the following, we let OPT := max φ u s (φ) be the optimal value of sender's expected utility. Moreover, given an additive error γ ∈ (0, 1), we say that a signaling scheme φ is γ-optimal if u s (φ) ≥ OPT -γ.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.1). We assume that the sender has no knowledge about both the prior µ and receiver's utility u, and that the only feedback they get after each round is the best-response action played by the receiver.At each round t ∈ [T ], 2 the sender commits to a signaling scheme φ t : Θ → ∆ S and observes a state of nature θ t ∼ µ. Then, they draw a signal s t ∼ φ t,θ t and send it to the receiver, who plays a best-response action a t := a φt (s t ). Finally, the sender gets payoff u s t := u s θ t (a t ) and observes a feedback consisting in the action a t played by the receiver. The goal of the sender is to learn how to maximize their expected utility while repeatedly interacting with the receiver. When the sender commits to a sequence {φ t } t∈[T ] of signaling schemes, their performance over the T rounds is measured by means of the following notion of cumulative (Stackelberg) regret:R T ({φ t } t∈[T ] ) := T • OPT -E T t=1 u s (φ t ) ,where the expectation is with respect to the randomness of the algorithm. In the following, for ease of notation, we omit the dependency on {φ t } t∈[T ] from the cumulative regret, by simply writing R T . Then, our goal is to design no-regret learning algorithms for the sender, which prescribe a sequence of signaling schemes φ t that results in the regret R T growing sublinearly in T , namely R T = o(T ). 
warm-up: a single signal is all you need: 
 In order to design our learning algorithm in Section 4, we 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 µ and receiver's utility function u. The crucial observation that motivates its adoption is that receiver's best responses a φ (s) only depend on the components of φ associated with s ∈ S, namely φ θ (s) for θ ∈ Θ. Thus, in order to learn them, it is sufficient to learn how a φ (s) varies as a function of such components.The signaling scheme representation introduced in this section revolves around the concept of slice. Definition 1 (Slice). Given a signaling scheme φ : Θ → ∆ S , the slice of φ with respect to signal s ∈ S is the d-dimensional vector x ∈ [0, 1] d with components x θ := φ θ (s) for θ ∈ Θ.In the following, we denote by X := [0, 1] d 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 -1)-dimensional simplex. Thus, it holds thatX := x ∈ [0, 1] d | θ∈Θ x θ = 1 . X (a1) X (a2) X (a3) x θ1 x θ2 1 1 X ( a 1 ) X ( a 2 ) X ( a 3 )Figure 1 : Representation of sets X (a i ) and X (a i ) for an instance with d = 2 states of nature and n = 3 receivers' actions.Next, we show that receiver's actions induce particular coverings of the sets X and X , which also depend on both the prior µ and receiver's utility u. First, we introduce H ij ⊆ R d to denote the halfspace of slices under which action a i ∈ A is (weakly) better than action a j ∈ A for the receiver.H ij := x ∈ R d | θ∈Θ x θ µ θ u θ (a i ) -u θ (a j ) ≥ 0 .Moreover, we denote by H ij := ∂H ij the hyperplane constituting the boundary of the halfspace H ij , which we call the separating hyperplane between actions a i and a j .3 Then, for every a i ∈ A, we introduce the polytopes X (a i ) ⊆ X and X (a i ) ⊆ X :X (a i ) := X ∩ aj ∈A:ai =aj H ij and X (a i ) := X ∩ aj ∈A:ai =aj H ij .Clearly, the sets X (a i ), respectively X (a i ), define a cover of X , respectively X . 4 Intuitively, the set X (a i ) encompasses all the slices under which action a i is a best response for the receiver. The set X (a i ) has the same interpretation, but for normalized slices. Specifically, if x ∈ X (a i ) is a slice of φ with respect to s ∈ S, then a i ∈ A φ (s). Notice that a slice x ∈ X may belong to more than one polytope X (a i ), when it is the case that |A φ (s)| > 1 for signaling schemes φ having x as slice with respect to s ∈ S. 5 In order to denote the best-response action actually played by the receiver under a slice x ∈ X , we introduce the symbol a(x), where a(x) := a φ (s) for any φ having x as slice with respect to s ∈ S. Figure 1 depicts an example of the polytopes X (a i ) and X (a i ) in order to help the reader to grasp more intuition about them.A crucial fact exploited by the learning algorithm developed in Section 4 is that knowing the separating hyperplanes H ij defining the polytopes X (a i ) of normalized slices is sufficient to determine an optimal signaling scheme. Indeed, the polytopes X (a i ) of unnormalized slices can be easily reconstructed by simply removing the normalization constraint θ∈Θ x θ = 1 from X (a i ).Furthermore, as we show in Section 4 (see the proof of Lemma 4 in particular), there alway exits an optimal signaling scheme using at most one slice x a ∈ X (a) for each receiver's action a ∈ 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 H ij are products between prior probabilities µ θ and receiver's utility differences u θ (a i ) -u θ (a j ). In order to design a 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 best responses, and this may potentially lead to a large loss in sender's expected utility (and, in its turn, to large regret). As a result, any naïve approach that learns the prior and receiver's payoffs 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 us to learn separating hyperplanes exactly. As we show in Section 4, it makes it possible to directly learn the coefficients of separating hyperplanes without splitting them into products of prior probabilities and receiver'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, as 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 -1)-dimensional 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 to work in the space of posterior distributions induced by sender's signals (see, e.g., [Castiglioni et al., 2020b] ). These are the beliefs computed by the receiver according to Bayes rule at 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 µ, 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. 
learning to persuade without a clue: 
 In this section, we design our no-regret algorithm (Algorithm 1). We adopt a sophisticated explorethen-commit approach that exploits the signaling scheme representation based on 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 (a i ) := X (a i ).6 Then, it exploits them in order to compute suitable approximately-optimal signaling schemes to be employed in the remaining rounds. Effectively implementing this approach raises considerable challenges.The first challenge is that the algorithm cannot directly "query" a slice x ∈ X to know action a(x), as it can only commit to fully-specified signaling schemes. Indeed, even if the algorithm commits to a signaling scheme including the selected slice x ∈ X , the probability that the signal associated with x is sent depends on the (unknown) prior, as it is equal to θ∈Θ µ θ x θ . This probability can be 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 ⊆ X of normalized slices "inducible" with at least a suitably-defined probability ∈ (0, 1). Such a set X is built by the algorithm in its first phase.The second challenge that we face is learning the polytopes X (a i ) := X (a i ) ∩ X . This is done by means of a technically-involved procedure that learns the separating hyperplanes H ij needed to identify them. This procedure is an adaptation to Bayesian persuasion settings of an algorithm recently introduced for a similar problem in Stackelberg games [Bacchiocchi et al., 2024a] .Finally, the third challenge is how to use the polytopes X (a i ) to compute suitable approximatelyoptimal 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.Algorithm 1 Learn-to-Persuade-w/o-Clue Require:T ∈ N 1: δ ← 1 /T , ζ ← 1 /T 2: ← √ Bnd 4 √ T 3: T 1 ← 12 log 2d δ 4: t ← 1 5: X ← Build-Search-Space(T 1 , ) 6: R ← Find-Polytopes(X , ζ) 7: while t ≤ T do 8: φ t ← Compute-Signaling(R , X , µ t ) 9:Commit to φ t , observe θ t , and send s t 10:Observe feedback a t and receive u s t 11:Compute prior estimate µ t+1 12:t ← t + 1The pseudocode of our no-regret learning algorithm is provided in Algorithm 1. In the pseudocode, we assume that all the sub-procedures have access to the current round counter t, all the observed states of nature θ t , and all the feedbacks a t , u s t received by the sender.7 Moreover, in Algorithm 1 and its sub-procedures, we use µ t ∈ ∆ Θ to denote the prior estimate at any round t > 1, which is a vector with components defined as µ t,θ := N t,θ /(t -1) for θ ∈ Θ, where N t,θ ∈ N denotes the number of times that state of nature θ is observed up to round t (excluded). Algorithm 1 can be conceptually divided into three phases. In phase 1, the algorithm employs the Build-Search-Space procedure (Algorithm 2) to build a suitable subset X ⊆ X of "inducible" normalized slices. Then, in phase 2, the algorithm employs the Find-Polytopes procedure (see Algorithm 6 in Appendix E) to find a collection of polytopes R := {R (a)} a∈A , where each R (a) is either X (a) or a suitable subset of X (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. Specifically, at each t, this phase employs the Compute-Signaling procedure (Algorithm 3) to compute an approximately-optimal signaling scheme, by using R , the set X , and the current prior estimate µ t .In the rest of this section, we describe in detail the three phases of Algorithm 1, bounding the regret attained by each of them. This allows us to prove the following main result about Algorithm 1. 8Theorem 1. The regret attained by Algorithm 1 isR T ≤ O d+n d n 3 /2 d 3 √ BT .We observe that the regret bound in Theorem 1 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 O(n d √ T ), respectively O(d n √ T ). Such a dependence is tight, as shown by the lower bounds that we provide in Section 5.Given an ∈ (0, 1 /6d) and a number of rounds T 1 , the Build-Search-Space procedure (Algorithm 2) computes a subset X ⊆ X of normalized slices satisfying two crucial properties needed by the learning algorithm to attain the desired guarantees. Specifically, the first property is that any slice x ∈ X can be "induced" with sufficiently high probability by a signaling scheme, while the second one is that, if x / ∈ X , then signaling schemes "induce" such a slice with sufficiently small probability. Intuitively, the first property ensures that it is possible to associate any x ∈ X with the action a(x) in a number of rounds of the order of 1 / , 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 2 Build-Search-Space Require: ∈ (0, 1 /6d), number of rounds T 1 1: Θ ← ∅ 2: while t ≤ T 1 do 3:Commit to any φ t , observe θ t , and send s t 4:Observe feedback a t and receive u s t 5:t ← t + 1 6: Compute prior estimate µ t 7: µ ← µ t 8: for θ ∈ Θ do 9: if µ θ > 2 then Θ ← Θ ∪ {θ} 10: X ← x ∈ X | θ∈ Θ µ θ x θ ≥ 2 11: return XAlgorithm 2 works by simply observing realized states of nature θ t for T 1 rounds, while committing to any signaling scheme meanwhile. This allows the algorithm to build a sufficiently accurate estimate µ of the true prior µ. Then, the algorithm uses such an estimate to build the set X . Specifically, it constructs X as the set containing all the normalized slices that are "inducible" with probability at least 2 under the estimated prior µ, after filtering out all the states of nature whose estimated probability is not above the 2 threshold (see Lines 8-10 in Algorithm 2).The following lemma formally establishes the two crucial properties that are guaranteed by Algorithm 2, as informally described above. Lemma 1. Given T 1 := 12 log ( 2d /δ) and ∈ (0, 1 /6d), Algorithm 2 employs T 1 rounds and terminates with a set X ⊆ X such that, with probability at least 1 -δ: (i) θ∈Θ µ θ x θ ≥ for every slice x ∈ X and (ii) θ∈Θ µ θ x θ ≤ 10 for every slice x ∈ X \ X .To prove Lemma 1, we employ the multiplicative version of Chernoff bound, so as to show that it is possible to distinguish whether prior probabilities µ θ are above or below suitable thresholds in a number of rounds of the order of 1 / . Specifically, we show that, after T 1 rounds and with probability at least 1 -δ, the set Θ in the definition of X does not contain states θ ∈ Θ with µ θ ≤ , while it contains all the states with a sufficiently large µ θ . This immediately proves properties (i) and (ii) in Lemma 1. Notice that using a multiplicative Chernoff bound is a necessary technicality, since standard concentration inequalities would result in a number of needed rounds of the order of 1 / 2 , leading to a suboptimal regret bound in the number of rounds T .For ease of presentation, we introduce the following clean event for phase 1 of Algorithm 1. This encompasses all the situations in which Algorithm 2 outputs a set X with the desired properties. Definition 2 (Phase 1 clean event). E 1 is the event in which X meets properties (i)-(ii) in Lemma 1.Given a set X ⊆ X computed by the Build-Search-Space procedure and ζ ∈ (0, 1) as inputs, the Find-Polytopes procedure (Algorithm 6 in Appendix E) computes a collection R := {R (a)} a∈A of polytopes enjoying suitable properties sufficient to achieve the desired goals.Ideally, we would like R (a) = X (a) for every a ∈ A. However, it is not possible to completely identify the polytopes X (a) with vol(X (a)) = 0. Indeed, if vol(X (a i )) = 0, then X (a i ) ⊆ X (a j ) for some other polytope X (a j ) with positive volume. Thus, due to receiver's tie breaking, it could be impossible to identify the whole polytope X (a i ). As a result, the Find-Polytopes procedure can output polytopes R (a) = X (a) only if vol(X (a)) > 0. However, we show that, if vol(X (a)) = 0, it is sufficient to guarantee that the polytope R (a) contains a suitable subset V (a) of the vertices of X (a); specifically, those in which the best response actually played by the receiver is a. For every a ∈ A, such a set is formally defined as V (a) := {x ∈ V (X (a)) | a(x) = a}. Thus, we design Find-Polytopes so that it returns a collection R := {R (a)} a∈A of polytopes such that:(i) if it holds vol(X (a)) > 0, then R (a) = X (a), while (ii) if vol(X (a)) = 0, then R (a) is a (possible improper) face of X (a) with V (a) ⊆ R (a).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) ⊆ R (a).To achieve its goal, the Find-Polytopes procedure works by searching over the space of normalized slices X , so as to learn exactly all the separating hyperplanes H ij characterizing the needed vertices.The algorithm does so by using and extending tools that have been developed for a 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 E for a complete description of the Find-Polytopes procedure.A crucial component of Find-Polytopes is a tool to "query" a normalized slice x ∈ X in order to obtain the action a(x). This is done by using a sub-procedure that we call Action-Oracle (see Algorithm 5 in Appendix E), which works by committing to a signaling scheme including slice x until the signal corresponding to such a slice is actually sent. Under the clean event E 1 , the set X is built in such a way that Action-Oracle returns the desired action a(x) in a number of rounds of the order of 1 / , with high probability. This is made formal by the following lemma. Lemma 2. Under event E 1 , given any ρ ∈ (0, 1) and a normalized slice x ∈ X , if the sender commits to a signaling scheme φ : Θ → S := {s 1 , s 2 } such that φ θ (s 1 ) = x θ for all θ ∈ Θ during q := 1 log( 1 /ρ) rounds, then, with probability at least 1 -ρ, signal s 1 is sent at least once.Notice that the signaling scheme used to "query" an x ∈ 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 6 in Appendix E. Lemma 3. Given inputs X ⊆ X and ζ ∈ (0, 1) for Algorithm 6, let L := B + B + B μ, where B, B , and B µ denote the bit-complexity of numbers µ θ u θ (a i ), , and µ, respectively. Then, under event E 1 and with at probability at least 1 -ζ, Algorithm 6 outputs a collection R := {R (a)} a∈A , where R (a) is a (possibly improper) face of X (a) such that V (a) ⊆ X (a), in a number of rounds T 2 :T 2 ≤ O n 2 log 2 1 ζ d 7 L + d + n d .For ease of presentation, we introduce the clean event for phase 2 of Algorithm 1, defined as follows: Definition 3 (Phase 2 clean event). E 2 is the event in which V (a) ⊆ R (a) for every a ∈ A.Given the collection of polytopes R := {R (a)} a∈A returned by the Find-Polytopes procedure and an estimated prior µ t ∈ ∆ Θ , the Compute-Signaling procedure (Algorithm 3) outputs an approximately-optimal signaling scheme by solving an LP (Program (2) in Algorithm 3). 2) maximizes an approximated version of sender's expected utility over a suitable space of (partially-specified) signaling schemes. These are defined by tuples of slices (x a ) a∈A containing an (unnormalized) slice x a ∈ R (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 a , where the approximation comes from the estimated prior µ t . The intuitive idea exploited by the LP formulation is that, under slice x a , the receiver always plays the same action a as best response, since a(x a ) = a holds by the way in which R (a) is constructed by Find-Polytopes. In particular, each polytope R (a) is built so as to include all the unnormalized slices corresponding to the normalized slices in the set R (a). Formally, for every receiver's action a ∈ A, it holds:Algorithm 3 Compute-Signaling Require: R := {R (a)} a∈A , X , µ t ∈ ∆ Θ 1: Solve Program (2) for x := (x ,a ) a∈A : max (x a ) a∈A a∈A θ∈Θ µ t,θ x a θ u s θ (a) s.t. (2) x a ∈ R (a) ∀a ∈ A a∈A x a θ ≤ 1 ∀θ ∈ Θ 2: S ← {s } ∪ {s a | a ∈ A} 3: for θ ∈ Θ do 4: φ θ ← φ θ (s a ) = x ,a θ ∀a ∈ A φ θ (s ) = 1 -a∈A x ,a θ 5: return φ Program (R (a) := x ∈ X | x = αx ∧ x ∈ R (a) ∧ α ∈ [0, 1] ∪ {0},where 0 denotes the vector of all zeros in R d . We observe that, since the polytopes R (a) are constructed as the intersection of some halfspaces H ij and X , it is possible to easily build polytopes R (a i ) by simply removing the normalization constraint θ∈Θ x θ = 1. Notice that, if R (a) = ∅, then R (a) = {0}, which implies that action a is never induced as a best response, since x a = 0.After solving Program (2) for an optimal solution x := (x ,a ) a∈A , Algorithm 3 employs such a solution to build a signaling scheme φ. This employs a signal s a for every action a ∈ A, plus an additional signal s , namely S := {s } ∪ {s a | a ∈ A}. Specifically, the slice of φ with respect to s a is set to be equal to x a , while its slice with respect to s is set so as to render φ a valid signaling scheme (i.e., probabilities over signal sum to one for every θ ∈ Θ). Notice that this is always possible thanks to the additional constraints a∈A x a θ ≤ 1 in Program (2). Moreover, such a slice may belong to X \ X . Indeed, in instances where there are some X (a) falling completely outside X , this is fundamental to build a valid signaling scheme. Intuitively, one may think of s as incorporating all the "missing" signals in φ, namely those corresponding to actions a ∈ A with X (a) outside X .The following lemma formally states the theoretical guarantees provided by Algorithm 3.Lemma 4. Given inputs R := {R (a)} a∈A , X , and µ t ∈ ∆ Θ for Algorithm 3, under events E 1 and E 2 , the signaling scheme φ output by the algorithm is O( nd + ν)-optimal for ν ≤ θ∈Θ µ t,θ -µ θ .In order to provide some intuition on how Lemma 4 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 a signaling scheme φ can be decomposed across its slices, with each slice x providing a utility of θ∈Θ µ θ x θ u s θ (a(x)). The second crucial observation is that there always exists an optimal signaling scheme φ that is direct and persuasive, which means that φ employs only one slice x a for each action a ∈ A, with a being a best response for the receiver under x a . It is possible to show that the slices x a that also belong to X can be used to construct a feasible solution to Program 2, since x a ∈ R (a) by definition. Thus, restricted to those slices, the signaling scheme φ computed by Algorithm 3 achieves an approximate sender's expected utility that is greater than or equal to the one achieved by φ . Moreover, the loss due to dropping the slices that are not in X can be bounded thanks to point (ii) in Lemma 1. 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 4. 
lower bounds for online bayesian persuasion: 
 In this section, we present two lower bounds on the regret attainable in the setting faced by Algorithm 1. 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 1 provided in Theorem 1. Formally: Theorem 2. For any sender's algorithm, there exists a Bayesian persuasion instance in which n = d + 2 and the regret R T suffered by the algorithm is at least 2 Ω(d) , or, equivalently, 2 Ω(n) .Theorem 2 is proved by constructing a collection of Bayesian persuasion instances in which an optimal signaling scheme has to induce the receiver to take an action that is 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 a result, in order to learn such a posterior belief, any algorithm has to commit to a number of signaling schemes that is exponential in d (and, given how the instances are built, in n).The second lower bound shows that the regret bound attained by Algorithm 1 is tight in T .Theorem 3. For any sender's algorithm, there exists a Bayesian persuasion instance in which the regret R T suffered by the algorithm is at least Ω( √ T ).To prove Theorem 3, we construct two Bayesian persuasion instances with Θ = {θ 1 , θ 2 } such that, in the first instance, µ θ1 is slightly greater than µ θ2 , 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 at least Ω( √ T ). 
the sample complexity of bayesian persuasion: 
 In this section, we show how the no-regret learning algorithm developed in Section 4 can be easily adapted to solve a related Bayesian persuasion PAC-learning problem. Specifically, given an (additive) approximation error γ ∈ (0, 1) and a probability η ∈ (0, 1), the goal of such a problem is to learn a γ-optimal signaling scheme with probability at least 1 -η, by using the minimum possible number of rounds. This can be also referred to as the sample complexity of learning signaling schemes.As in the regret-minimization problem addressed in Section 4, we assume that the sender does not know anything about both the prior distribution µ and receiver's utility function u.Algorithm 4 PAC-Persuasion-w/o-Clue Require: γ ∈ (0, 1), η ∈ (0, 1)1: δ ← η /2, ζ ← η /2, 1 ← γ /12nd, t ← 1 2: ← Compute-Epsilon( 1 ) 3: T 1 ← 1 2 2 log 2d δ 4: X ← Build-Search-Space(T 1 , ) 5: R ← Find-Polytopes(X , ζ) 6: φ ← Compute-Signaling(R , X , µ) 7: return φ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 1, with the Build-Search-Space and Find-Polytopes procedures being called for suitably-defined parameters , δ, T 1 , and ζ (taking different values with respect to their counterparts in Algorithm 1). In particular, the value of depends on γ and is carefully computed so as to control the bit-complexity of numbers used in the Find-Polytopes procedure (see Lemma 3), as detailed in Appendix G. Finally, in its third phase, the algorithm calls Compute-Signaling to compute a signaling scheme φ that can be proved to γ-optimal with probability at least 1 -η.The most relevant difference between Algorithm 4 and Algorithm 1 is the number of rounds used to build the prior estimate defining X . Specifically, while the latter has to employ T 1 of the order of 1 / and rely on a multiplicative Chernoff bound to get tight regret guarantees, the former has to use T 1 of the order of 1 / 2 and standard concentration inequalities to get an O( )-optimal solution. Formally: Lemma 5. Given T 1 := 1 2 2 log ( 2d /δ) and ∈ (0, 1), Algorithm 2 employs T 1 rounds and outputs X ⊆ X such that, with probability at least 1 -δ: (i) θ∈Θ µ θ x θ ≥ for every slice x ∈ X , (ii) θ∈Θ µ θ x θ ≤ 6 for every slice x ∈ X \ X , and (iii) | µ θ -µ θ | ≤ for every θ ∈ Θ.By Lemma 5, it is possible to show that the event E 1 holds. Hence, the probability that a signaling scheme including a slice x ∈ X actually "induces" such a slice is at least , and, thus, the results concerning the second phase of Algorithm 1 are valid also in this setting. Finally, whenever the events E 1 and E 2 hold, we can provide an upper bound on the number of rounds required by Algorithm 4 to compute a γ-optimal signaling scheme as desired. Formally: Theorem 4. Given γ ∈ (0, 1) and η ∈ (0, 1), with probability at least 1 -η, Algorithm 4 outputs a γ-optimal signaling scheme in a number of rounds T such that:T ≤ O n 3 γ 2 log 2 1 η d 8 B + 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 κ, λ > 0 such that no algorithm is guaranteed to return a κ-optimal signaling scheme with probability of at least 1 -λ by employing less than 2 Ω(n) and 2 Ω(d) rounds, even when the prior distribution µ is known to the sender.Theorem 6. Given γ ∈ (0, 1 /8) and η ∈ (0, 1), no algorithm is guaranteed to return a γ-optimal signaling scheme with probability at least 1 -η by employing less than Ω 1 γ 2 log( 1 /η) 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 /γ, which is tight. Learning in Bayesian persuasion settings In addition to the works presented in Section 1.2, the problem of learning optimal signaling schemes in Bayesian persuasion settings has received growing attention over the last few years. Camara et al.[2020] study an adversarial setting where the receiver does not know the prior, and the receiver's behavior is aimed at minimizing internal regret. Babichenko et al. [2022] consider an 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 et al. [2023] design a regret-minimization algorithm in an advertising setting based on the Bayesian persuasion framework, assuming that the receiver'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 no 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 on an initial random sampling that may 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 et al. [2009] , while Bacchiocchi et al. [2024a] further improve the approach by Peng et al. [2019] by relaxing some of their assumptions.Furthermore, our work is also related to the problem of learning optimal strategies in Stackelberg games where the leader and the follower interaction is modelled by a Markov Decision Process. Lauffer et al. [2024] study Stackelberg games with a state that influences the leader's utility and available actions. Bai et al. [2021] consider a setting where the leader commits to a pure strategy and observes a noisy measurement of their utility.Finally, our work is also related to online hidden-action principal-agent problems, in which a principal commits to a contract at each round to induce an agent to take favorable actions. Ho et al. [2014] initiated the study by proposing an algorithm that adaptively refines a discretization over the space of contracts, framing the model as a 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-action principal-agent 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 is small.In step (3) of the sender-receiver interaction presented in Section 2.1, after observing s ∈ S, the receiver performs a Bayesian update and infers a posterior belief ξ s ∈ ∆ Θ over the states of nature, according to the following equation:EQUATIONConsequently, given a signaling scheme φ, we can equivalently represent it as a distribution over the set of posteriors it induces. Formally, we say that φ induces γ : ∆ Θ → [0, 1] if, for each posterior distribution ξ ∈ ∆ Θ , we have:γ(ξ) = s∈S:ξ s =ξ θ∈Θ µ θ φ θ (s) and ξ∈supp(γ) γ(ξ) = 1.Furthermore, we say that a distribution over a set of posteriors γ is consistent, i.e., there exists a valid signaling scheme φ inducing γ if the following holds:ξ∈supp(γ) γ(ξ)ξ θ = µ θ ∀θ ∈ Θ.With an abuse of notation, we will sometimes refer to a consistent distribution over a set of posteriors γ as a signaling scheme. This is justified by the fact that there exists a signaling scheme φ inducing such distribution, but we are interested only in the distribution over the set of posteriors that φ induces.In the following, we assume that all the numbers manipulated by our algorithms are rational. Furthermore, we assume that rational numbers are represented as fractions, by specifying two integers which encode their numerator and denominator. Given a rational number q ∈ Q represented as a fraction b /c with b, c ∈ Z, we denote the number of bits that q occupies in memory, called bit-complexity, asB q := B b + B c , where B b (B c) is the number of bits required to represent the numerator (denominator). For the sake of the presentation, with an abuse of terminology, given a vector in Q D of D rational numbers represented as fractions, we let its bit-complexity be the maximum bit-complexity among its entries.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 µ, while we assume B u to be an upper bound to the bit-complexity of each d-dimensional vector u θ (a) with θ ∈ Θ. Moreover, we let B := B µ + B u . Finally, we also denote with B the bit-complexity of the parameter computed by our algorithms, while we denote with B µ the bit-complexity of the estimator µ computed by Algorithm 2.Lemma 1. Given T 1 := 12 log ( 2d /δ) and ∈ (0, 1 /6d), Algorithm 2 employs T 1 rounds and terminates with a set X ⊆ X such that, with probability at least 1 -δ: (i) θ∈Θ µ θ x θ ≥ for every slice x ∈ X and (ii) θ∈Θ µ θ x θ ≤ 10 for every slice x ∈ X \ X .Proof. For each θ ∈ Θ we consider two possible cases.1. If µ θ > , then we employ the multiplicative Chernoff inequality as follows:P |µ θ -µ θ | ≥ 1 2 µ θ ≤ 2e -T 1 µ θ 12 ,where T 1 ∈ N + is the number of rounds employed to estimate µ θ . As a result, by setting the number of rounds to estimate µ θ equal to T 1 = 12 / log ( 2d /δ) we get:P |µ θ -µ θ | ≥ 1 2 µ θ ≤ 2 δ 2d µ θ ≤ δ d ,since µ θ > . Then, we get:EQUATIONConsequently, with a probability of at least 1 -δ/d the estimator µ θ is such that µ θ ∈ [ µ θ/2, 3µ θ/2]. Thus, if µ θ ≥ 6 , then µ θ ≥ 3 > 2 and θ ∈ Θ. We also notice that there always exits a θ ∈ Θ such that µ θ ≥ 1 /d ≥ 6 , since ∈ (0, 1 /6d). Consequently, with a probability of at least 1 -δ/d, there always exist a θ ∈ Θ.2. If µ θ ≤ , then we employ the multiplicative Chernoff inequality as follows:P ( µ θ ≥ (1 + c)µ θ ) ≤ e -c 2 T 1 µ θ 2+c, with c = /µ θ . Thus, by setting the number of rounds employed to estimate µ θ equal to T 1 = 12 / log ( 2d /δ) , we get:P ( µ θ ≥ µ θ + ) ≤ exp   - 2 µ 2 θ 12 log 2d δ µ θ 2 + µ θ   ≤ exp - 12 µ θ log 2d δ 2 + µ θ ≤ δ 2d 4 ≤ δ d , since x/(x + 2) ≥ 1/3, for each x ≥ 1.As a result, we have:P ( µ θ ≤ µ θ + ) ≥ 1 - δ d .Thus, with a probability of at least1 -δ/d, if µ θ ≤ , then µ θ ≤ µ θ + , which implies that µ θ ≤ 2 . Furthermore, if µ θ ≤ , then µ θ ≤ 2 and θ ∈ Θ.Thus, by employing a union bound over the set of natures, we have that if µ θ ≤ , then its corresponding estimate µ θ falls within the interval [0, 2 ] and θ ∈ Θ, while if µ θ ≥ 6 , then its corresponding estimate is such that µ θ > 2 and θ ∈ Θ, with a probability of at least 1 -δ. We also notice that, with the same probability, the set Θ is always non empty.Consequently, for each slice x ∈ X with respect to a signal s, the probability of observing s can be lower bounded as follows:≤ 1 2 θ∈ Θ µ θ x θ ≤ 3 4 θ∈ Θ µ θ x θ ≤ θ∈ Θ µ θ x θ ≤ θ∈Θ µ θ x θ ,where the inequalities above hold because of the definition of X and observing that each θ ∈ Θ satisfies Equation 4 with probability at least 1 -δ.Furthermore, for each x ∈ X , the two following conditions hold:1 2 θ∈ Θ µ θ x θ ≤ θ∈ Θ µ θ x θ ≤ 2 and θ ∈ Θ µ θ x θ ≤ 6 θ ∈ Θ x θ ≤ 6 ,with probability at least 1 -δ. Thus, by putting the two inequalities above together, for each x ∈ X , we have:θ∈Θ µ θ x θ ≤ 10 ,with probability at least 1 -δ, concluding the proof.Lemma 2. Under event E 1 , given any ρ ∈ (0, 1) and a normalized slice x ∈ X , if the sender commits to a signaling scheme φ : Θ → S := {s 1 , s 2 } such that φ θ (s 1 ) = x θ for all θ ∈ Θ during q := 1 log( 1 /ρ) rounds, then, with probability at least 1 -ρ, signal s 1 is sent at least once.Proof. In the following, we let τ be the first round in which the sender commits to φ. The probability of observing the signal s 1 at a given round t ≥ τ is can be lower bounded as follows:P s t = s 1 = θ∈Θ µ θ x θ ≥ ,where the inequality holds under the event E 1 . Thus, at each round, the probability of sampling the signal s 1 ∈ S is greater or equal to > 0. Consequently, the probability of never observing the signal s 1 ∈ S in q rounds is given by:P τ +q-1 t=τ {s t = s 1 } ≤ (1 -) q ≤ ρ,where the last inequality holds by taking q = log(ρ) log(1-) ≤ log(1/ρ) , for each ∈ (0, 1). As a result, the probability of observing the signal s 1 at least once in q rounds is greater or equal to:P τ +q-1 t=τ {s t = s 1 } = 1 -P τ +q-1 t=τ {s t = s 1 } ≥ 1 -ρ, concluding the proof. Theorem 1. The regret attained by Algorithm 1 is R T ≤ O d+n d n 3 /2 d 3 √ BT .Proof. In the following, we letδ = ζ = 1 T and = √ Bnd 4 √ T, as defined in Algorithm 1. To prove the theorem, we decompose the regret suffered in the three phases of Algorithm 1:1. Phase 1. We observe that the number of rounds to execute the Build-Search-Space procedure (Algorithm 2) is equal toT 1 = O ( 1 / log ( 1 /δ) log(d)). Thus, the cumulative regret of Phase 1 can be upper bounded as follows:R 1 T ≤ O 1 log(T ) log(d) ≤ O √ T d 4 √ nB log(d) ≤ O √ T .This is because, at each round, the regret suffered during the execution of Algorithm 2 is at most one.2. Phase 2. Under the event E 1 , which holds with probability 1 -δ, Algorithm 6 correctly terminates with probability 1 -ζ. Thus, with probability at least 1 -δ -ζ, the number of rounds employed by such algorithm is of the order:T 2 ≤ O n 2 log 2 1 ζ d 7 (B + B + B µ ) + d + n d = O n 2 log 2 (T ) d 7 (B + B ) + d + n d ,where the last equality holds because B µ = O(log( 1 / ) + log(d) + log(T )). As a result, by taking the expectation, the regret suffered in Phase 2 by Algorithm 1 can be upper bounded as follows:R 2 T ≤ O n 3 /2 d 3 d + n d √ BT ,since, at each round, the regret suffered during the execution of Algorithm 6 is at most one.3. Phase 3. Let τ be the number of rounds required by Phase 1 and Phase 2 to terminate. Under the events E 1 and E 2 , which hold with probability at least 1 -δ -ζ, thanks to Lemma 4, the solution returned by Algorithm 3 at each round t > τ is O(dn + ν t )-optimal, where we define ν t = θ∈Θ µ θ -µ t,θ . We introduce the following event:E t = {|µ θ -µ t,θ | ≤ t ∀θ ∈ Θ} ,where we let t > 0 be defined as follows:t = log (2dT /ι) 2(t -τ ) , t > τ.Then, by Hoeffding's inequality and a union bound we have:P t>τ E t ≥ 1 -ι.Thus, by setting ι = 1/T , the regret suffered in Phase 3 by Algorithm 1 can be upper bounded as follows:R 3 T ≤ T t=τ +1 θ∈Θ µ θ -µ t,θ + O (d T ) ≤ d T t=τ +1 t + O (dn T ) ≤ O d √ T + dn T = O d √ T + n 3 /2 d 5 √ BT .As a result, the regret of Algorithm 1 is in the order of:R T ≤ O n 3 /2 d 3 d + n d √ BT + n 3 /2 d 5 √ BT = O n 3 /2 d 3 d + n d √ BT ,concluding the proof.In order to prove Lemma 4, we first consider an auxiliary LP (Program 5a) that works on the vertices of the regions X (a). This is useful to take into account the polytopes X (a) with null volume. Indeed, for every action a ∈ A such that vol(X (a)) = 0, Algorithm 3 takes in input only a face R (a) of X (a) such that V (a) ⊆ V (R (a)). By working on the vertices of the regions X (a), we can show that the vertices in V (a) are sufficient to compute an approximately optimal signaling scheme.The auxiliary LP that works on the vertices is the following:EQUATION)Program 5a takes in input the set of vertices V := a∈A V (X (a)), along with the corresponding best-responses (a(x)) x∈V and the exact prior µ. It then optimizes over the non-negative variables α x ≥ 0, one for vertex x ∈ V . These variables α x act as weights for the corresponding slices x ∈ V , identifying a non-normalized slice α x x ∈ X .In the following, we show that the value of an optimal solution v to Program 5a is at least v ≥ OPT -O( nd). Then, we prove that the signaling scheme φ computed by Algorithm 3 achieves a principal's expected utility of at least v minus a quantity related to the difference between the estimated prior µ t and with the actual prior µ. Thus, by considering that v ≥ OPT -O( nd), we will be able to prove Lemma 4.As a first step, we show that it is possible to decompose each slice x ∈ X into a weighted sum of the vertices x ∈ V without incurring a loss in the sender's utility. Thus, a generic slice x of an optimal signaling scheme can be written as a convex combination of slices x with x ∈ V . This property is formalized in the following lemma.Lemma 6. For every x ∈ X , there exists a distribution α ∈ ∆ V such that:x θ = x ∈V α x x θ ∀θ ∈ Θ.Furthermore, the following holds:θ∈Θ µ θ x θ u s θ (a(x)) ≤ x ∈V α x θ∈Θ µ θ x θ u s θ (a(x )).Proof. Let a := a(x). Since x ∈ X (a), by the Carathéodory theorem, there exists an α ∈ ∆ V (X (a)) such that:x ∈V (X (a))α x x θ = x θ ∀θ ∈ Θ.Furthermore:θ∈Θ µ θ x θ u s θ (a) = θ∈Θ µ θ   x ∈V (X (a)) α x x θ   u s θ (a). = x ∈V (X (a)) α x θ∈Θ µ θ x θ u s θ (a) ≤ x ∈V (X (a)) α x θ∈Θ µ θ x θ u s θ (a(x ))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 a given X (a), we can always recover a probability distribution supported in V , since V (X (a)) ⊆ V by construction.Thanks to the the result above, in the next lemma (Lemma 7) we prove that an optimal solution of Program 5a has value at least v ≥ OPT -10 nd. To show this, we begin by observing that there exists a set J of slices of the optimal signaling scheme that belong to the search space X . By applying Lemma 6 to each of these slices, we obtain a feasible solution for Program 5a. The value of this solution is at least the sender's expected utility given by the slices in J . Finally, thanks to the properties of the search space X , we can bound the expected sender's utility provided by the slices that lie outside the search space. Lemma 7. Under the event E 1 , the optimal solution of Program 5a has value at least v ≥ OPT -10 nd.Proof. In the following we let φ θ ∈ ∆ A for each θ ∈ Θ be an optimal signaling scheme, where we assume, without loss of generality, such a signaling scheme to be direct, meaning that S = A and a ∈ A φ (a) for every action a ∈ A. Furthermore, for each action a ∈ supp(φ), we define:x a θ = φ θ (a) θ∈Θ φ θ (a) ∀θ ∈ Θ and α x a = θ∈Θ φ θ (a).We observe that each x a ∈ X (a), indeed we have:θ∈Θ µ θ x θ u θ (a) = 1 α x a θ∈Θ µ θ φ θ (a)u θ (a) ≥ 1 α x a θ∈Θ µ θ φ θ (a)u θ (a ) = θ∈Θ µ θ x θ u θ (a ).for every action a ∈ A. We define the subset of actions A ⊆ A in a way that if a ∈ A , then x a ∈ X , i.e., A := {a ∈ A | x a ∈ X }. Then, we let A := supp(φ) \ A . Furthermore, for each a ∈ A , thanks to Lemma 6, there exists a distribution α a ∈ ∆ V such that:x a θ = x ∈V α a x x θ ,and the following holds:EQUATIONWe also define α : V → R + as follows:α x = a∈A α a x α x a ,for each x ∈ V . First, we show that α : V → R + is a feasible solution to LP 5a. Indeed, for each θ ∈ Θ, it holds:x ∈V α x x θ = x ∈V a∈A α a x α x a x θ = a∈A α x a x ∈V α a x x θProof. We observe that under the events E 1 and E 2 , the collection R = {R (a)} a∈A is composed of faces R (a) of X (a) (possibly the improper face X (a) itself) such that every vertex x ∈ V (X (a)) that satisfies a(x) = a belongs to R (a). The following statements hold under these two events.As a first step, we prove that given a feasible solution α = (α x ) x∈V to Program 5a, one can construct a feasible solution ϕ to Program 2 with the same value. In particular, we consider a solution ϕ = ( x a ) a∈A defined as:x a θ := x∈V (a) α x x θ ∀a ∈ A, θ ∈ Θ.We observe that for every a ∈ A and θ ∈ Θ we can bound x a θ as follows:0 ≤ x a θ = x∈V (a) α x x θ ≤ x∈V α x x θ ≤ 1,where the last inequality holds due to the constraints of Program 5a. Consequently, the vectors x a belong to X . Now we show that x a belongs to R (a) for every a ∈ A. This holds trivially for every action a ∈ A such that x ∈V (a) α x = 0, as x a = 0 ∈ R (a). Consider instead an action a ∈ A such thatx ∈V (a) α x > 0, and let us define the coefficient:β a x := α x x ∈V (a) α x ,for every vertex x ∈ V (a). One can easily verify that β a ∈ ∆ V (a) . Now consider the normalized slice:x N,a :=x∈V (a) β a x x.This slice belongs to R (a) := R (a), as it is the weighted sum of the vertices V (a) ⊆ V (R (a)) with weights β a ∈ ∆ V (a) . Furthermore, we can rewrite the component x a of the solution φ as:x a = x N,a x∈V (a) α x .Thus, by considering that x N,a ∈ R (a) and x a ∈ X , we have that x a ∈ R (a).Finally, since α is a feasible solution for Program 5a, we can observe that:a∈A x a θ = a∈A x∈V (a) α x x = x∈V α x x ≤ 1.As a result, ϕ = ( x a ) a∈A is a feasible solution to Program 2.If the estimator µ t coincides with the exact prior µ, then direct calculations show that the solution ϕ to Program 2 achieves the same value of the solution α to Program 5a.It follows that, when µ t = µ, the optimal solution of Program 2 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 φ LP be the signaling scheme computed by Algorithm 3, while let Ψ = (x LP,a ) a∈A be the optimal solution to Program 2. Furthermore, we let ψ = (x E,a ) a∈A be the optimal solution of Program 2 and φ E the signaling scheme computed by Algorithm 3 when the prior estimator coincides exactly with the prior itself, i.e., µ := µ t = µ.µ θ -µ θ ≥ OPT -10 nd -2 θ∈Θ µ θ -µ θ ,concluding the proof.The goal of the Action-Oracle procedure (Algorithm 5) is to assign the corresponding best-response to a slice x ∈ X received as input. In order to do so, it repeatedly commits to a signaling scheme φ such that x is the slice of φ with respect to the signal s 1 . When the signal s 1 is sampled, the procedure returns the best-response a(x).Require: x ∈ X 1: φ θ (s 1 ) ← x θ and φ θ (s 2 ) ← 1 -x θ ∀θ ∈ Θ 2: do 3:Commit to φ t = φ, observe θ t , and send s tObserve feedback a t 5:a ← a t 6: while s t = s 1 7: return a In the following, for the sake of analysis, we introduce the definition of a clean event under which the Action-Oracle procedure always returns the action a(x) ∈ A, as formally stated below. Definition 4 (Clean event of Action-Oracle). We denote E a as the event in which Algorithm 5 correctly returns the follower's best response a(x) whenever executed.In the proof of Lemma 3 we show that, thanks to Lemma 2 and the definition of X , it is possible to bound the number of rounds required to Algorithm 5 to ensure that it always returns the best response a(x) ∈ A with high probability.Algorithm 6 Find-Polytopes Require: Search space X ⊆ X , parameter ζ ∈ (0, 1)1: (C, {X (a)} a∈C ) ← Find-Fully-Dimensional-Regions(X , ζ) 2: for all a j ∈ A \ C do 3:R (a j ) ← Find-Face(C, {X (a)} a∈C , a j ) 4: R (a k ) ← X (a k ) ∀a k ∈ C 5: return {R (a)} a∈A .Algorithm 6 can be divided in two parts. First, by means of Algorithm 7, it computes the polytopes R (a) = X (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 Action-Oracle to query a generic normalized slice, and some technical details to account for the shape of the search space X .In the second part (loop at Line 2 Algorithm 6), it finds, for every polytope X (a) with null volume, a face R (a) such that V (a) ⊆ R (a). Let us remark that R (a) could be the improper face X (a) itself, and it is empty if V (a) = ∅. Lemma 3. Given inputs X ⊆ X and ζ ∈ (0, 1) for Algorithm 6, let L := B + B + B μ, where B, B , and B µ denote the bit-complexity of numbers µ θ u θ (a i ), , and µ, respectively. Then, under event E 1 and with at probability at least 1 -ζ, Algorithm 6 outputs a collection R := {R (a)} a∈A , where R (a) is a (possibly improper) face of X (a) such that V (a) ⊆ X (a), in a number of rounds T 2 :T 2 ≤ O n 2 log 2 1 ζ d 7 L + d + n d .Proof. In the following we letL = B + B + B µ .As a first step, Algorithm 6 invokes the procedure Find-Fully-Dimensional-Regions. Thus, according to Lemma 8, under the event E a , with probability at least 1 -ζ /2, Algorithm 6 computes every polytope X (a) with volume larger than zero by performing at most:C 1 = O n 2 d 7 L log( 1 /ζ) + d + n d .calls to the Action-Oracle procedure. Together with these polytopes, it computes the set C ⊆ A containing the actions a such that vol(X (a)) > 0.Subsequently, Algorithm 6 employs the procedure Find-Face at most n times and, according to Lemma 12, it computes the polytopes R (a j ) for every a j / ∈ C. Overall, this computation requires:C 2 = n 2 d + n dcalls to the Action-Oracle procedure. Thus, under the event E a and with probability at least 1 -ζ /2, Algorithm 6 correctly computes the polytopes R (a j ) for every action a j ∈ A. Furthermore, the number of calls C ≥ 0 to the Action-Oracle procedure can be upper bounded as:C := C 1 + C 2 ≤ O n 2 d 7 L log( 1 /ζ) + d + n d .Moreover, by setting ρ = ζ/2C, and thanks to Lemma 2, with a probability of at least 1 -ρ, every execution of Action-Oracle requires at most N ≥ 0 rounds, where N can be bounded as follows:N ≤ O log(1/ρ) = O 1 log 2C ζ .Consequently, since the number of calls to the Action-Oracle procedure is equal to C, by employing a union bound, the probability that each one of these calls requires N rounds to terminate is greater than or equal to:1 -Cρ = 1 - ζ 2C C = 1 - ζ 2 .To conclude the proof, we employ an union bound over the probability that every execution of Action-Oracle terminates in at most N rounds, and the probability that Algorithm 6 performs C calls to the Action-Oracle procedure. Since the probability that each one of these two events hold is at least 1 -ζ /2, with probability at least 1 -ζ, Algorithm 6 correctly terminates by using a number of samples of the order:O C log 2C ζ ≤ O n 2 log 2 1 ζ d 7 L + d + n d ,concluding the proof.Algorithm 7 Find-Fully-Dimensional-Regions Require: Search space X ⊆ X , parameter δ ∈ (0, 1)1: δ ← ζ /2n 2 (2(d+n)+n) 2: C ← ∅ 3: while aj ∈C U(a j ) = X do 4:x int ← Sample a point from int X \ a k ∈C U(a k ) 5:a j ← Action-Oracle(x int ) 6:U(a j ) ← X 7:B x ← Bit-complexity of x int 8: λ ← d2 -d(Bx+4(B+B +B µ ))-1 9:for all v ∈ V (U(a j )) do 10:x ← λx int + (1 -λ)v 11: a ← Action-Oracle(x) 12:if a = a j then 13:H jk ← Find-Hyperplane(a j , U(a j ), x int , v, δ)14:U(a j ) ← U(a j ) ∩ H jk 15:else 16:restart the for-loop at Line 9 17:C ← C ∪ {a j } 18:X (a j ) ← U(a j ) 19: return C, {X (a j )} aj ∈C At a high level, Algorithm 7 works by keeping track of a set C ⊆ A of closed actions, meaning that the corresponding polytope X (a) has been completely identified. First, at Line 4, Algorithm 7 samples at random a normalized slice x int from the interior of one of the polytopes X (a j ) that have not yet been closed and queries it, observing the best-response a j ∈ A. Then, it initializes the entire X as the upper bound U(a j ) of the region X (a j ). As a further step, to verify whether the upper bound U(a j ) coincides with X (a j ), Algorithm 7 queries at Line 11 one of the vertices of the upper bound U(a j ). Since the same vertex may belong to the intersection of multiple regions, the Action-Oracle procedure is called upon an opportune convex combination of x int and the vertex v itself (Line 10). If the vertex does not belong to X (a j ), then a new separating hyperplane can be computed (Line 13) and the upper bound U(a j ) is updated accordingly. In this way, the upper bound U(a j ) is refined by finding new separating hyperplanes until it coincides with the polytope X (a j ). Finally, such a procedure is iterated for all the receiver's actions a j ∈ A such that vol(X (a j )) > 0, ensuring that all actions corresponding to polytopes with volume larger than zero are closed.We observe that the estimator µ t is updated during the execution of Algorithm 7 according to the observed states. However, let us remark that the search space X = x ∈ X | θ∈ Θ µ θ x θ ≥ 2 does not change during the execution of this procedure. Lemma 8. Given in input X ⊆ X and ζ ∈ (0, 1), then under the event E a with probability at least 1 -ζ /2 Algorithm 7 computes the collection of polytopes {X (a j )} aj ∈C with volume larger than zero, and the corresponding set of actions C. Furthermore, it employs at most:O n 2 d 7 L log( 1 /ζ) + d + n dcalls to the Action-Oracle procedure.Proof. Thanks to Lemma 9 and Lemma 10, with an approach similar to the one proposed in Theorem 4.3 by Bacchiocchi et al. [2024a] , we can prove that, under the event E a , with probability at least 1 -δn 2 (2(d + n) 2 + n), Algorithm 7 computes every polytope X (a) with volume larger than zero by performing at most:O n 2 d 7 L log( 1 /δ) + d + n d calls to the Action-Oracle procedure. Together with these polytopes, it computes the set C ⊆ A containing the actions a such that vol(X (a)) > 0.Furthermore, we observe that ζ = 2δn 2 (2(d + n) + n), as defined at Line 1 in Algorithm 7. As a result, under the event E a , with probability at least 1 -ζ /2, the number of calls C 1 ≥ 0 performed by Algorithm 7 to the Action-Oracle procedure can be bounded as follows:C 1 ≤ O n 2 d 7 L log( 1 /ζ) + d + n d ,concluding the proof.Algorithm 8 Find-Hyperplane Require: a j , U(a j ),x int , v, δ 1: x ← Sample-Int(U(a j ), δ) 2: x 1 ← x 3: if Action-Oracle(x) = a j then 4:x 2 ← v 5: else 6:x 2 ← x int 7: x • ← Binary-Search(a j , x 1 , x 2 ) 8: α ← 2 -4d(Bx+B+B µ +B ) /d 9: S j ← ∅; S k ← ∅ 10: for i = 1 . . . d do 11:x ← Sample-Int(H i ∩ X , δ) 12:x +i ← x • + α(x -x • ) 13: x -i ← x • -α(x -x • ) 14:if Action-Oracle(x +i ) = a j then 15:S j ← S j ∪ {x +i } ∧ S k ← S k ∪ {x -i } 16: else 17: S k ← S k ∪ {x +i } ∧ S j ← S j ∪ {x -i } 18: Build H jk by Binary-Search(a j , x 1 , x 2 ) for d -1 pairs of linearly-independent points x 1 ∈ S j , x 2 ∈ S kThe goal of the Find-Hyperplane procedure is to compute a new separating hyperplane H jk between a given region X (a j ) and some other polytope X (a k ), with a j , a k ∈ A. To do so, it receives as input an upper bound U(a j ) of some polytope X (a j ), an interior point x int ∈ int(U(a j )), a vertex v ∈ V(U(a j )) that does not belong to X (a j ), and a parameter δ > 0 as required by the Sample-Int procedure. As a first step, Algorithm 8 samples at random a slice x from the interior of the upper bound U(a j ). Subsequently, it performs a binary search on the segment between x and either v or x int , depending on the best response a(x) in x. This binary search returns a point x • on some new separating hyperplane H jk (Line 7). As a further step, the algorithm computes two sets of normalized slices, S j ⊆ X (a j ) and S k ⊆ X (a k ). Finally, it performs d -1 binary searches between different couples of points, one in S j and the other in S k , in order to completely identify the separating hyperplane. Lemma 9. With probability at least 1-(d+n) 2 δ, under the event E a Algorithm 8 returns a separating hyperplane H jk by using O(d 7 (B + B + B µ ) + d 4 log( 1 /δ)) calls to Algorithm 5.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 a , the binary-search procedure described in Algorithm 9 correctly computes a point on a separating hyperplane by calling the Action-Oracle procedure at most O(d(B x + B)) times.With the same reasoning applied in Lemma 4.4 and 4.5 by Bacchiocchi et al. [2024a] , we can prove that with probability at least 1 -(d + n) 2 δ, under the event E a , the points x +i are linearly independent and do not belong to H jk . To conclude the proof, we have to show that every x +i belongs to either X (a j ) or X (a k ). This is because, if the previous condition holds, under the event E a , Algorithm 8 correctly computes a new separating hyperplane with probability at least 1 -(d + n) 2 δ.To do that, we show that the constant α defined at Line 8 in Algorithm 8 is such that all the points x +i and x -i either belong to X (a j ) or X (a k ), 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 x i and any separating hyperplane can be lower bounded by Bx+4B) , where B x is the bit-complexity of x • .2 -d(Similarly, the distance between x • and the hyperplaneH = {x ∈ R d | θ∈ Θ µ θ x θ ≥ 2} can be lower bounded as follows:EQUATION)where B µ is the bit-complexity of µ. 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:θ∈ Θ x θ µ θ = α β and = γ ν ,where α and β are integers numbers, while γ and ν are natural numbers. Thus, the numerator θ∈ Θ x θ µ θ + 2 of the fraction defined in Equation 7 can be lower bounded as follows:θ∈ Θ x θ µ θ + 2 = αν + 2βγ βν ≥ 1 βν ≥ 2 -3d(Bx+B µ +B ) ,where the last inequality follows from the fact that the bit-complexity of ν is at most B , while the bit-complexity of β cannot exceed 3d(B x + B µ ) as stated by Lemma D.1 of Bacchiocchi et al. [2024a] .Overall, the distance between x • and the boundary of the polytope X (a j ) ∩ X (a k ) is strictly larger than α := 2 -4d(Bx+B+B µ +B )-log 2 (d) . Thus, every signaling scheme x +i and x -i belongs to X and either X (a j ) or X (a k ).Finally, we observe that the bit-complexity of x is bounded by B x = O(d 3 (B +B +B µ )+log( 1 /δ)),The Binary-Search procedure performs a binary search on the segment connecting two points, x 1 , x 2 ∈ X such that x 1 ∈ X (a j ) and x 2 / ∈ X (a j ) for some a j ∈ A, in order to find a point x • on some separating hyperplane H jk . At each iteration, the binary search queries the middle point of the segment. Depending on the receiver's best-response in such a point, it keeps one of the two halves of the segment for the subsequent iteration. The binary search ends when the segment is sufficiently small, so that it contains a single point with a bit-complexity appropriate for a point that lies on both the hyperplane H jk and the segment connecting x 1 and x 2 . Such a point can be found traversing the Stern-Brocot-Tree. For an efficient implementation, see Forišek [2007] . Overall, Algorithm 9 performs O(d(B x + B)) calls to the Action-Oracle procedure, and returns a normalized slice x • with bit-complexity bounded by O(d(B x + B)), where B x is the bit-complexity of the points x 1 and x 2 .Algorithm 9 Binary-Search Require: a j , x 1 , x 2 of bit-complexity bounded by someB x > 0 1: λ 1 ← 0; λ 2 ← 1 2: while |λ 2 -λ 1 | ≥ 2 -6d(5Bx+8B) do 3: λ ← (λ 1 + λ 2 )/2; x • ← x 1 + λ(x 2 -x 1 ) 4:if Action-Oracle(x • ) = a j then 5:λ 1 ← λ 6: else 7: λ 2 ← λ 8: λ ← Stern-Brocot-Tree(λ 1 , λ 2 , 3d(5B x + 8B)) 9: x • ← λx 1 + (1 -λ)x 2 E.6 Sample-Int Algorithm 10 Sample-Int Require: P ⊆ X : vol d-1 (P) > 0, and δ 1: V ← d linearly-independent vertexes of P 2: x ← 1 d v∈V v 3: ρ ← d 3 2 9d 3 L+4dL -1 ; M ← √ d /δ 4: y ∼ Uniform({-1, -M -1M , . . . , 0, . . . , M -1 M , 1} d-1 ) 5: for all i ∈ 1, . . . , d -1 do 6:x i ← x i + ρy i 7: x d ← 1 - d-1 i=1 x iThe Sample-Int procedure (Algorithm 10) samples at random a normalized slice from the interior of a given polytope P. We observe that each polytope Algorithm 7 is required to sample from is defined as the intersection of X with some separating half-spaces as the ones defined in Section 3. This procedure provides theoretical guarantees both on the bit-complexity of the point x being sampled and on the probability that such a point belongs to a given hyperplane. Furthermore, it can be easily modified to sample a point from a facet of the simplex X = ∆ d (intuitively, this is equivalent to sample a point from ∆ d-1 ). As a first step, Algorithm 10 computes a normalized slice x in the interior of P (Line 2). Subsequently, it samples randomly a vector y from a suitable grid belonging to the (d -1)-dimensional hypercube with edges of length 2. As a further step, it sums each component x i of the normalized slice x with the corresponding component y i of y, scaled by an opportune factor ρ, where the constant ρ is defined to ensure that x belongs to the interior of P.The theoretical guarantees provided by Algorithm 10 are formalized in the following lemma: Lemma 10. Given a polytope P ⊆ X : vol d-1 (P) > 0 defined by separating or boundary hyperplanes, Algorithm 10 computes x ∈ int(P) such that, for every linear space H ⊂ R d : P ⊆ H of dimension at most d -1, the probability that x ∈ H is at most δ. Furthermore, the bit-complexity ofx is O(d 3 (B + B + B µ ) + log( 1 /δ)).Proof. In the following, we prove that x 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 ρn. To ensure that x belongs to int(P), we have to show that d(x , x) is smaller than the distance between x and any hyperplane defining the boundary of P.Let us denote with v h the h-vertex of the set V, so that V = {v 1 , v 2 , . . . , v d }. Furthermore, we define:v h θ := γ h θ ν h for each h ∈ [d]and θ ∈ Θ. Since x belongs to int(P), then the distance between x and any separating hyperplane H jk can be lower bounded as follows:d(x , H jk ) = θ∈Θ x θ µ θ (u θ (a j ) -u θ (a k )) θ∈Θ µ 2 θ (u θ (a j ) -u θ (a k )) 2 = θ∈Θ d h=1 v h θ µ θ (u θ (a j ) -u θ (a k )) d θ∈Θ µ 2 θ (u θ (a j ) -u θ (a k )) 2 ≥ 1 d 2 2 -4dB-9d 3 (B+B +B µ ) .To prove the last inequality, we observe that the denominator of the fraction above can be upper bounded by d 2 . To lower bound the nominator, we define:µ θ (u θ (a j ) -u θ (a k )) := α θ β θ for each θ ∈ Θ.As a result, we have:θ∈Θ d h=1 v h θ µ θ (u θ (a j ) -u θ (a k )) = θ∈Θ d h=1 α θ γ h θ β θ ν h = θ∈Θ d h=1 α θ γ h θ θ =θ β θ h =h ν h θ∈Θ β θ d h=1 ν h ≥ θ∈Θ β θ d h=1 ν h -1 ≥ 2 -4dB-9d 3 (B+B +B µ ) .The first inequality holds because the numerator of the fraction above can be lower bounded by one. The denominator can be instead upper bounded observing that the bit-complexity of each β θ is at most 4B while the bit-complexity of each ν h is at most 9d 2 (B + B + B µ ), as stated by Lemma 11.In a similar way, we can lower bound the distance between x andH := {x ∈ R d | θ∈ Θ µ θ x θ ≥ 2 }. d(x , H) = θ∈ Θ µ θ x θ + 2 θ∈ Θ µ 2 = θ∈ Θ d h=1 µ θ v h θ + 2 d θ∈ Θ μ2 ≥ 1 d 2 2 -B µ -B -9d 3 (B+B +B µ ) .To prove the last inequality, we observe that the denominator of the fraction above can be upper bounded by d 2 , while to lower bound the numerator, we define:μθ := N θ p and = α βfor each θ ∈ Θ. As a result, we have:θ∈ Θ d h=1 µ θ v h θ + 2 = θ∈ Θ d h=1 N θ γ h θ pν h + 2 = θ∈ Θ d h=1 βN θ γ h θ h =h ν h + 2αp d h=1 ν h p d h=1 ν h β ≥ 2 -B µ -B -9d 3 (B+B +B µ )Thus, the distance between x and any hyperplane H defining the boundary of P can be lower bounded as follows:d(x , H) ≥ 1 d 2 2 -9d 3 (B+B +B µ )-4dB-B µ -B ≥ 1 d 2 2 -10d 3 (B+B +B µ ) .We observe that, given the definition of ρ at Line 3, the distance d(x , x) is strictly smaller than d(x , H), showing that x ∈ int(P).Furthermore, we can prove that the bit-complexity of x is bounded byO(d 3 (B +B +B µ )+log( 1 /δ)).To do so, we observe that the denominator of x is equal to d d h=1 ν h , while the denominator of y i is equal to M = √ d /δ . As a result, the denominator of everyx i = x • i + ρy i , with i ∈ [d -1], can be written as follows:D = d d h=1 ν h D ρ M,where D ρ is the denominator of the rational number ρ. Similarly, the last component x d can be written with the same denominator. As a result, the bit complexity of x ∈ [0, 1] d can be upper bounded as follows:B x ≤ 2 log(D) = O(log(d d h=1 ν h D ρ M )) = O log d h=1 2 9d 2 (B+B +B µ ) + log(d2 10d 3 (B+B +B µ ) ) + log( √ d /δ) = O d 3 (B + B + B µ ) + log 1 δ .Finally, with the same analysis performed in Lemma 4.8 by Bacchiocchi et al. [2024a] , we can show that the probability that x belongs to a given hyperplane H is at most δ.Lemma 11. Each vertex v of a polytope P ⊆ X : vol d-1 (P) > 0, defined by separating or boundary hyperplanes, has bit-complexity at most 9d 2 (B + B + B µ ). Furthermore, with a bitcomplexity of 9d 2 (B + B + B µ ), all the components of the vector v identifying a vertex can be written as fractions with the same denominator.Proof. We follow a line of reasoning similar to the proof of Lemma D.2 in Bacchiocchi et al. [2024a] .Let v be a vertex of the polytope P. Then such a vertex lies on the hyperplane H ensuring that the sum of its components is equal to one. Furthermore, it also belongs to a subset of d -1 linearly independent hyperplanes. These can be separating hyperplanes:H ij = x ∈ R d | θ∈Θ µ θ x θ (u θ (a i ) -u θ (a j )) = 0with a i , a j ∈ A, boundary hyperplanes of the formH i = {x ∈ R d | x i > 0}, or the hyperplane H := x ∈ R d | θ∈ Θ µ θ x θ ≥ 2 . Consequently, there exists a matrix A ∈ Q d×d and a vector b ∈ Q d such that Av = b.Suppose that v is not defined by the hyperplaneH := x ∈ R d | θ∈Θ µ θ x θ ≥ 2 .Then, each entry of the matrix A is either equal to one or the quantity µ θ (u θ (a) -u θ (a ) for some θ ∈ Θ and a, a ∈ A. Thus, its bit-complexity is bounded by B. Similarly, each entry of the vector b is either equal to one or zero. With a reasoning similar to the one applied in Bacchiocchi et al. [2024a] , the bit-complexity of v is at most 9d 2 (B µ + B u ).Suppose instead that v is defined also by the hyperplane H, corresponding to the last row of the matrix A and the last component of the vector b. This hyperplane can be rewritten as:H =    x ∈ R d | θ∈ Θ µ θ 2 x θ ≥ 1    .Thus, each element of the last row of A is either zero or the quantity µ θ/2 for some θ ∈ Θ. We observe that µ θ/2 is a rational number with numerator bounded by 2 B µ +B and denominator bounded by 2 B µ +B +1 . Thus, we multiply the last row of A and the last component of b by a constant bounded by 2 d(B µ +B +1) . The other rows of A and the corresponding components of b are multiplied instead by some constants bounded by 2 4dB . This way, we obtain an equivalent system A v = b with integer coefficients.We define A (j) 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 j can be computed as follows:v j = det(A (j)) det(A ) ∀j ∈ [d].We observe that both determinants are integer numbers as the entries of both A and are all integers, thus by Hadamard's inequality we have:| det(A )| ≤ i∈[d] j∈[d] a ji 2 ≤   i∈[d-1] j∈[d] (2 4dB ) 2   j∈[d] (2 d(B µ +B +1) ) 2 =   i∈[d-1] d(2 4dB ) 2   d2 2d(B µ +B +1) =   i∈[d-1] d 1 2 (2 4dB )   d 1 2 2 d(B µ +B +1) = d d 2 (2 4d(d-1)B )2 d(B µ +B +1) ≤ d d 2 (2 4d 2 B )2 d(B µ +B +1)With a reasoning similar to Bacchiocchi et al. [2024a] , we can show that that the bit-complexity D v of the vertex v is bounded by:D v ≤ 9Bd 2 + 2(d(B µ + B + 1)) ≤ 9d 2 (B + B + B µ )Furthermore, this result holds when the denominator of every component v j of the vertex v is written with the same denominator det(A ), concluding the proof.Algorithm 11 Find-Face Require: The set of polytopes {X (a i )} ai∈C , with volume larger than zero, and action a j / ∈ C 1: Compute the minimal H-representation M(X (a i )) for every polytope X (a i ),a i ∈ C 2: H(a i ) ← ∅ ∀a i ∈ C 3: First ← True 4: for all x ∈ ai∈C V (X (a i )) do 5: a ← Action-Oracle(x) 6: if a = a j then 7: if First = False then 8: H(a i ) ← {H ∈ M(X (a i )) | x ∈ H, H ∈ H(a i )} ∀a i ∈ C 9: else 10: H(a i ) ← {H ∈ M(X (a i )) | x ∈ H} ∀a i ∈ C 11: First ← False 12: if First = True then 13:F (a j ) ← ∅ 14: F (a j ) ← X (a i ) ∩ H∈H(ai) H for any a i such that X (a i ) ∩ H∈H(ai) H = ∅ 15: Return F (a j ) Algorithm 11 takes in input the collection of polytopes {X (a i )} ai∈C and another action a j / ∈ C such that vol(X (a j )) = 0, and outputs the H-representation of a (possibly improper) face of X (a j ) that contains all those vertices x ∈ V (X (a j )) where a(x) = a j . As we will show by means of a pair of technical lemmas, the polytope X (a j ) is a face of some other polytope X (a k ), with a k ∈ C. Consequently, Algorithm 11 looks for a face of some polytope X (a k ) containing the set of vertices V (a j ).As a first step, Algorithm 11 computes, for every action a i ∈ C, the set of hyperplanes M(X (a i )) corresponding to the minimal H-representation of X (a i ). This set includes every separating hyperplane H ik found by Algorithm 7, together with the non-redundant boundary hyperplanes that delimit X . Subsequently, Algorithm 11 iterates over the vertices of the regions with volume larger than zero, which we prove to include all the vertices of the region X (a j ). While doing so, it builds a set of hyperplanes H(a i ) ⊆ M(X (a i )) for every action a i ∈ C. Such a (possibly empty) set includes all and only the hyperplanes in M(X (a i )) that contain all the vertices where the action a j has been observed, i.e, a(x) = a j . Finally, at Line 14 Algorithm 11 intersects every region X (a i ) with the corresponding hyperplanes in H(a i ), obtaining a (possibly empty) face for every polytope X (a i ), a i ∈ C. At least one of these faces is the face the algorithm is looking for, and corresponds to the output of Algorithm 11.The main result concerning Algorithm 11 is the following: Lemma 12. Given the collection of polytopes {X (a i )} ai∈C with volume larger than zero and an another action a j , then, under the event E a , Algorithm 11 returns a (possibly improper) face F (a j ) of X (a j ) such that V (a j ) ⊆ F (a j ). Furthermore, the Algorithm requires O(n d+n d ) calls to Algorithm 5.In order to prove it, we first need to introduce two technical lemmas to characterize the relationship between regions with null volume and those with volume larger than zero. Lemma 13. Let a i , a j ∈ A such that vol(X (a i )) > 0 and vol(X (a j )) = 0. Then X (a i ) ∩ X (a j ) is a (possibly improper) face of X (a i ) and X (a j ).Proof. In the following we assume that X (a i )∩X (a j ) is non-empty, as the empty set is an improper face of every polytope.We prove that X (a i ) ∩ X (a j ) = X (a i ) ∩ H ij = X (a j ) ∩ H ij . In order to do that, we first show that X (a i ) ∩ H ij ⊆ X (a i ) ∩ X (a j ). Consider a normalized slice x ∈ X (a i ) ∩ H ij . Then we have thatx ∈ X (a j ). As this holds for every x ∈ X (ai ) ∩ H ij , it follows that X (a i ) ∩ H ij ⊆ X (a i ) ∩ X (a j ).As a first step we show that F (a i ) actually is a face of X (a i ) and contains every vertex of V (a j ). Being the non-empty intersection of X (a i ) with some hyperplanes in M(X (a i )), F (a i ) is a face of X (a i ). One can easily prove by induction that H(a i ) includes all and only the hyperplanes within M(X (a i )) containing every vertex in V (a j ). Thus, V (a j ) ⊆ F (a i ). Now we show that F (a i ) is not only a (proper) face of X (a i ) containing the set V (a j ), but also a face of X (a j ) (possibly the improper face X (a j ) itself). We consider the set X (a i ) ∩ X (a j ), which is a face of both X (a i ) and X (a j ) thanks to Lemma 13. Thus, there exists some set of hyperplanes H (a i ) ⊂ M(X (a i )) such that:EQUATIONFurthermore, we observe that V (a j ) ⊆ X (a i ) ∩ X (a j ). Indeed, we have that V (a j ) ⊆ X (a i ) since V (a j ) ⊆ F (a i ) and F (a i ) is a face of X (a i ), and V (a j ) ⊆ X (a j ) by definition.We want to prove that H (a i ) ⊆ H(a i ), where the set H(a i ) contains all and only the hyperplanes within M(X (a i )) that include the whole set V (a j ). In order to do that, suppose, by contradiction, that there exists a vertex x ∈ V (a j ) such that x / ∈ H for some H ∈ H (a i ). Then, x / ∈ X (a i ) ∩ H (a i ) ⊆ H. However, we proved that V (a j ) ⊆ X (a i ) ∩ X (a j ) and X (a i ) ∩ X (a j ) = X (a i ) ∩ H (a i ) by definition of H (a i ), reaching a contradiction. Consequently:F (a i ) := X (a i ) ∩ H(a i ) = X (a i ) ∩ H∈H(ai) H ⊆ X (a i ) ∩ H∈H (ai) H = X (a i ) ∩ H (a i ) = X (a i ) ∩ X (a j ),where we applied Equation 8, the fact that H (a i ) ⊆ H(a i ), and Equation 9.Finally, we can show that F (a i ) is a face of X (a j ). We have that F (a i ) is a face of X (a i ) and F (a i ) ⊆ X (a i ) ∩ X (a j ), which is itself a face of X (a i ) by Lemma 13. Thus, F (a i ) is a face of X (a i ) ∩ X (a j ). Furthermore, Lemma 13 states that X (a i ) ∩ X (a j ) is also a face of X (a j ). This implies that F (a i ) is a face of a face of X (a j ), and thus a face of X (a j ) itself.In order to conclude the proof, we have to prove that at Line 14 Algorithm 11 can actually find an action a i such that F (a i ) = X (a i ) ∩ H(a i ) is non-empty. Let a k ∈ C be such that X (a j ) is a face of X (a k ), which exists thanks to Lemma 14. Let x be any vertex in the set V (a j ) and define H (a j ) as:H (a k ) := {H ∈ R H (X (a k )) | x ∈ H}.Then X (a k ) ∩ H (a k ) = {x}. Consequently, H(a k ) ⊆ H (a k ), and thus:X (a k ) ∩ H(a k ) = X (a k ) ∩ H∈H(a k ) H ⊆ X (a k ) ∩ H∈H (a k ) H = X (a k ) ∩ H (a k ) = {x} = ∅.As a result, there is always an action a k ∈ C such that X (a k ) ∩ H(a k ) = ∅.Finally, we observe that Algorithm 11 executes Algorithm 5 once for every vertex in the set ai∈C V (X (a i )), which has size O(n d+n d ).F Omitted proofs from Section 5Theorem 2. For any sender's algorithm, there exists a Bayesian persuasion instance in which n = d + 2 and the regret R T suffered by the algorithm is at least 2 Ω(d) , or, equivalently, 2 Ω(n) .Proof. In the following, for the sake of the presentation, we consider a set of instances characterized by an even number d ∈ N + of states of nature and n = d + 2 receiver's actions. All the instances share the same uniform prior distribution and the same sender's utility, given by u s θ (a d+1 ) = 1 for all θ ∈ Θ, and u s θ (a) = 0 for all θ ∈ Θ and ∀a ∈ A \ {a d+1 }. Each instance is parametrized by a vector p belonging to a set P defined as follows:P := p ∈ {0, 1} d | d i=1 p i = d 2 .Furthermore, we assume that the receiver's utility in each instance I p is given by:Ip    u θi (a j ) = δ ij ∀i, j ∈ [d], u θi (a d+1 ) = 2 d p i ∀i ∈ [d], u θi (a d+2 ) = 2 d ∀i ∈ [d].We show that ξ θi := 2 d p i for each i ∈ [d] is the only posterior inducing the receiver's action a d+1 ∈ A in the instance I p , since the receiver breaks ties in favor of the sender. To prove that, we observe that the action a d+1 is preferred to the action a d+2 only in those posteriors that satisfy the condition ξ θi = 0 for each i ∈ [d] with p i = 0. Furthermore, to incentivize the action a d+1 over the set of actions a i with i ∈ [d], the following condition must hold:i∈[d]:pi>0 ξ θi u θi (a n+1 ) = 2 d i∈[d]:pi>0 ξ θi = 2 d ≥ max i∈[d]:pi>0 ξ θi .We notice that the last step holds only ifξ θi ≤ 2/d for each i ∈ [d] such that p i > 0. Consequently, since the number of ξ θi > 0 is equal to d/2, it holds ξ θi = 2/d for each i ∈ [d] such that p i > 0.Thus, the only posterior inducing action a d+1 is equal to ξ θi := 2 d p i . We also notice that, given p ∈ P, the optimal signaling scheme γ is defined as γ(ξ ) = 1 /2 and γ(ξ ) = 1 /2, with ξ θ = µ θ -1 2 ξ θ for each θ ∈ Θ. With a simple calculation, we can show that the expected sender's utility in γ is equal to 1 /2.We set the time horizon T = |P| /4 to show that any algorithm suffers regret of at least 2 Ω(d) . 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 ξ t at each round t ∈ [T ].Thus, we can apply Yao's minimax principle to show that any deterministic algorithm fails against a distribution over instances. In the following, we consider a uniform distribution over instances I p with p ∈ P. Furthermore, we observe that the feedback of any algorithm is actually binary. Thus, it is easy to see that an optimal algorithm works as follows: (i) it ignores the feedback whenever the action is not a d+1 , and (ii) it starts to play the optimal posterior when the action is a d+1 since it found an optimal posterior. This observation is useful for showing that any deterministic algorithm does not find a posterior that induces action a d+1 with a probability of at least 1 -|P| /(4|P|) = 3 /4 (since it can choose only |P| /4 posteriors among the |P| possible optimal posteriors). Hence, by Yao's minimax principle, for any (randomized) algorithm there exists an instance such that the regret suffered in the T rounds is at least: d) , which concludes the proof.R T ≥ 3 4 T 2 ≥ 1 4 |P| 4 ≥ |P| 32 , since x ≥ x -1 ≥ x/2, for each x ≥ 2. Finally, we notice that |P| = d d /2 = 2 Ω(Theorem 3. For any sender's algorithm, there exists a Bayesian persuasion instance in which the regret R T suffered by the algorithm is at least Ω( √ T ).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 θ (a 1 ) = u s θ (a 2 ) = 0 for u 2 θ1 (a 4 ) = 0, u 2 θ2 (a 4 ) = 1 (2+4 )with ∈ (0, 1 /4). 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. ∀s ∈ S such that φ θ1 (s) > φ θ2 (s), then a φ (s) = a 1 .2. ∀s ∈ S such that 0 < φ θ1 (s) < φ θ2 (s), then a φ (s) = a 2 .3. ∀s ∈ S such that φ θ1 (s) = φ θ2 (s), then a φ (s) = a 3 .4. ∀s ∈ S such that 0 = φ θ1 (s), then a φ (s) = a 4 .As a 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 a 3 or a 4 . 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 φ t of the form:EQUATIONwith φ t 1 ∈ [0, 1]. We also notice that, in each round, the optimal signaling scheme in the first instance is the one that induces action a 3 , meaning φ t 1 = 1 for each t ∈ [T ]. 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 φ t 1 = 0 for each t ∈ [T ]. In such a way, the learning task undertaken by the sender reduces to select a value of φ t 1 ∈ [0, 1] for each t ∈ [T ] controlling the probability of inducing action a 3 over action a 4 .In the following, we define P 1 (P 2 ) as the probability distribution generated by the execution of a given algorithm in the first (second) instance and we let E 1 (E 2 ) be the expectation induced by such a distribution.The cumulative regret in the first instance can be written as follows:R 1 T = E 1 T t=1 1 2 + -φ t 1 1 2 + -1 -φ t 1 1 2 - = 2 E T t=1 1 -φ t 1 .Similarly, in the second instance, the cumulative regret is given by:R 2 T = 2 E T t=1 φ t 1 .Furthermore, it is easy to check that:R 1 T ≥ P 1 T t=1 φ 1 t ≤ T /2 T and R 2 T ≥ P 2 T t=1 φ 1 t ≥ T /2 T.By employing the relative entropy identities divergence decomposition we also have that:KL P 1 , P 2 = T • KL µ 1 , µ 2 ≤ 64 3 T 2 ≤ 22T 2 ,where we employed the fact that for two Bernoulli distribution it holds KL(Be(p), Be(q)) ≤ (p -q) 2 q(1 -q) .Then, by employing the Bretagnolle-Huber inequality we have that,R 1 T + R 2 T ≥ T P 1 T t=1 φ 1 t ≤ T /2 + P 2 T t=1 φ 1 t ≥ T /2 ≥ 1 2 T exp -KL P 1 , P 2 ≥ 1 2 T exp -22T 2 . By taking = 1 22T we get: R 1 T + R 2 T ≥ C 1 √ T .with C 1 = e -1 /(2 √ 22) Thus, we have:R 1 T ≥ C 1 2 √ T ∨ R 2 T ≥ C 1 2 √ T ,concluding the proof.G Details and omitted proofs from Section 6G.1 Compute-Threshold procedureThe Compute-Threshold procedure takes as input a real parameter 1 > 0. Then, it iteratively halves the value of a different parameter , initially set to one, until it is smaller than or equal to 1 . In this way, Algorithm 12 computes a parameter ∈ [ 1 /2, 1 ] in O(log( 1 / 1)) rounds with bit complexity B = O(log( 1 / 1)). This technical component is necessary to ensure that the bitcomplexity of the parameter is not too large while guaranteeing that the solution returned by Algorithm 4 is still γ-optimal with probability at least 1 -η.Algorithm 12 Compute-Threshold Require: 1 ∈ (0, 1)1: ← 1 2: while ≥ 1 do 3:← /2 4: Return G.2 Omitted proofs from Section 6 Lemma 5. Given T 1 := 1 2 2 log ( 2d /δ) and ∈ (0, 1), Algorithm 2 employs T 1 rounds and outputs X ⊆ X such that, with probability at least 1 -δ: (i) θ∈Θ µ θ x θ ≥ for every slice x ∈ X , (ii) θ∈Θ µ θ x θ ≤ 6 for every slice x ∈ X \ X , and (iii) | µ θ -µ θ | ≤ for every θ ∈ Θ.Proof. Thanks to the definition of T 1 := 1 /2 2 log ( 2d /δ) in Algorithm 4 and employing both a union bound and the Hoeffding bound we have:P (| µ θ -µ θ | ≤ ) ≥ 1 -δ, ∀θ ∈ Θ.Thus, by combining Inequality (11) and Inequality (12), we have: θ∈Θ µ θ x θ ≤ 6 , when x ∈ X , concluding the proof.Theorem 4. Given γ ∈ (0, 1) and η ∈ (0, 1), with probability at least 1 -η, Algorithm 4 outputs a γ-optimal signaling scheme in a number of rounds T such that:T ≤ O n 3 γ 2 log 2 1 η d 8 B + d d + n d .Proof. Thanks to Lemma 5, with probability at least 1-δ = 1 -η /2 Algorithm 4 correctly completes Phase 1 in T 1 = O( 1 / 2 log( 1 /η) log(d))rounds. Thus, with probability at least 1 -η /2, both the event E 1 and the inequalities | µ θ -µ θ | ≤ for each θ ∈ Θ hold.Consequently, under the event E 1 , with probability at least 1 -ζ = 1 -η /2, Algorithm 4 correctly partitions the search space X in at most: As a result, with probability at least 1 -η, Algorithm 4 correctly terminates in a number of rounds N which can be upper bounded as follows:O n 2 log 2 1 η d 7 L + d + n d rounds,N ≤ O 1 2 log 1 η log(d) + n 2 log 2 1 η d 7 (B + B ) + d + n d .Furthermore, we observe that if | µ θ -µ θ | ≤ for each θ ∈ Θ, then the following holds:θ∈Θ µ θ -µ θ ≤ θ∈Θ | µ θ -µ θ | ≤ θ∈Θ = d.Consequently, thanks to the result provided by Lemma 4, with probability at least 1 -η, Algorithm 4 computes a 12n d-optimal solution. Thus, by setting 1 := γ /12nd and ≤ 1 , with probability at least 1 -η Algorithm 4 computes a γ-optimal solution in a number of rounds N bounded by:N ≤ O n 2 d 2 γ 2 log 1 η + n 3 γ log 2 1 η d 8 (B + B ) + d d + n d = O n 3 γ 2 log 2 1 η d 8 (B + B ) + d d + n d = O n 3 γ 2 log 2 1 η d 8 B + d d + n d ,where the last equality holds because the bit-complexity of is B = O(log( nd /γ)), concluding the proof.Theorem 5. There exist two absolute constants κ, λ > 0 such that no algorithm is guaranteed to return a κ-optimal signaling scheme with probability of at least 1 -λ by employing less than 2 Ω(n) and 2 Ω(d) rounds, even when the prior distribution µ is known to the sender.Proof. In the proof of Theorem 2 we showed that, with probability 3 /4, in N = |P| /4 rounds any algorithm does not correctly identify the posterior inducing action a d+1 . This is because, any deterministic algorithm can identify the optimal posterior only in |P| /4 instances, as observed in the proof of Theorem 2.As a result, in the remaining |P| -N instances, any deterministic algorithm will receive the same feedback and thus will always output the same posterior after N rounds, which will result in the optimal one in only a 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:3 4 |P| -N -1 |P| -N ≥ 3 8 |P| -N |P| -N = 3 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 a result, for each κ < 1 /2 there is no algorithm that is guaranteed to return a solution which is κ-optimal in |P|/4 = 2 Ω(d) rounds with probability at least 3 /8. Theorem 6. Given γ ∈ (0, 1 /8) and η ∈ (0, 1), no algorithm is guaranteed to return a γ-optimal signaling scheme with probability at least 1 -η by employing less than Ω 1 γ 2 log( 1 /η) 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 1 (P 2 ) be the probability distribution generated by the execution of a given algorithm in the first (second) instance for N = log(1/4η) /22 2 rounds. Furthermore, we introduce the event E, under which the signaling scheme returned at the round N , according to the definition presented in Equation 10, is such that φ N ≤ 1/2. We notice that, if such signaling scheme is such that φ N < 1/2, then the sender's expected utility in the first instance is smaller or equal to 1/2, thus being /2-optimal. At the same time, if φ N ≥ 1/2 in the second instance, then the solution returned by the algorithm is not /2-optimal.Thus, by employing the Bretagnolle-Huber inequality we have:P 1 (E) + P 2 E C ≥ 1 2 exp -KL P 1 , P 2 ≥ 1 2 exp -22N 2 ,since KL P 1 , P 2 ≤ 22N 2 , as observed in the proof of Theorem 6. Finally, by employing the definition of N , we have:P 1 (E) ≥ η ∨ P 2 E C ≥ η.As a result, by setting 2γ = , the statement of the lemma holds.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 13. The main difference with respect to Algorithm 4 is that, in this case, we do not need to employ the Build-Search-Space procedure, as the prior is already known to the sender. This allows us to compute a γ-optimal signaling scheme in only O( 1 /γ) rounds, instead of O( 1 /γ 2 ) rounds as in the case with an unknown prior.Algorithm 13 PAC-Persuasion-w/o-Clue-Known Require: η ∈ (0, 1), γ ∈ (0, 1), µ ∈ ∆ Θ 1: 1 ← γ /10nd 2: ← Compute-Epsilon( 1 ), µ ← µ 3: Θ ← {θ ∈ Θ | µ θ > 2 } 4: X ← x ∈ X | θ∈ Θ µ θ x θ ≥ 2 5: R ← Find-Polytopes(X , η) 6: φ ← Compute-Signaling(R , X , µ) 7: return φIn this case, the following theorem holds. Theorem 7. With probability at least 1 -η and in Algorithm 2 computes a γ-optimal signaling scheme in O n 3 /γ log 2 ( 1 /η) d 8 B + d d+n d rounds.Proof. Since µ = µ, the clean event E 1 holds with probability one. Consequently, thanks to Lemma 3, with probability at least 1 -η, Algorithm 13 correctly partitions the search space X in at most: Furthermore, under the event E 2 , Algorithm 13 computes a 10 nd-optimal solution, as guaranteed by Lemma 4, with µ = µ.Thus, with probability at least 1 -η, Algorithm 13 computes a γ-optimal solution in: We notice that, differently from the case with an unknown prior, it is possible to achieve a O ( log(1/η) /γ) upper bound with respect to the input parameters γ, η > 0. Finally, we show that such a dependence is tight, as shown in the following theorem. Theorem 8. Given γ, η > 0 no algorithm is guaranteed to return an γ-optimal signaling scheme with probability of at least 1 -η employing Ω ( log(1/η) /γ) rounds, even when the prior distribution is known to the sender.• 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: The paper does not include experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The paper conforms with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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?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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.Given a finite set X, we denote by ∆X the set of all the probability distributions over X.We denote by [n] := {1, . . . , n} the set of the first n ∈ N natural numbers.We let ∂H be the boundary hyperplane of halfspace H ⊆ R d . Notice that Hij and Hji actually refer to the same hyperplane. In this paper, we use both names for ease of presentation.In this paper, given a polytope P ⊆ R D , we let V (P) be its set of vertices, while we denote by volm(P) its Lebesgue measure in m dimensions. For ease of notation, whenever m = D -1, we simply write vol(P). Moreover, we let int(P) be the interior of P relative to a subspace that fully contains P and has minimum dimension. In the case of polytopes X (ai), the (d -1)-dimensional simplex is one of such subspaces.Let us remark that, in this paper, we assume that there are no two equivalent receiver's actions ai = aj ∈ A such that u θ (ai) = u θ (aj) for all θ ∈ Θ. Thus, a slice can belong to more than one polytope only if it lies on some separating hyperplane. This assumption is w.l.o.g. since it is possible to account for equivalent actions by introducing at most n additional separating hyperplanes to consider tie breaking in favor of the sender.In the rest of the paper, for ease of notation, we write X and X (ai) instead of X and X (ai).Notice that, in Algorithm 1, the sub-procedures Build-Search-Space 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 > T , their execution is immediately stopped (as well as the execution of Algorithm 1).Notice that the regret attained by Algorithm 6 (stated in Theorem 1) depends on B, which is the bitcomplexity of numbers µ θ u θ (ai), i.e., the number of bits required to represent them. We refer the reader to Appendix E for more details about how we manage the bit-complexity of numbers in this paper.Observe that when R (a) = ∅ and R (a) = {0}, we have x LP,a = 0. Thus, x LP,a does not contribute to the sender's utility, s a / ∈ supp(φ LP ) and A φ LP (s a ) = A by definition. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_summary: The paper studies 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. 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.

The 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.
strength_weakness: strength_weakness: 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.
questions: 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. 

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? \
-- 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)

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?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 

- Line 296: It might be better to be a bit more specific about the distinguished features here.

- 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?

Typos: 

- Line 51: of much (how much?)

- Line 314: clean event
questions: questions: - In algorithm 2, the feedback a^t and u_t^s seem not useful? If so, better to remove this line?

- 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: limitations: Nothing is mentioned, but no concern here.
paper_summary: paper_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.
strength_weakness: strength_weakness: (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.
questions: questions: Can the authors respond to weakness (1)?
limitations: limitations: **Suggestions:**

(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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).
questions: questions: (also including detailed comments)

Line 22, "such as, e.g., ...": a bit repetitive?

Line 92: superscript missing in the definition of $u_\theta^s$?

Footnote 1: might as well quickly define int while you are defining $\Delta$

Line 110: missing ")"

Sec 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.

Line 218: "sufficiency"

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.)

Sec 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: limitations: No concerns.

Comments: title: Happy with authors' response
comment: Thank you for your helpful response.  I don't have further questions.
Thank you for your responses!
I am happy with the authors' response and raise rating to 7.  Indeed, adding discussion on the computational complexity might further strengthen the paper.