Online Bayesian Persuasion Without a Clue

We thank the Reviewer for the insightful feedbacks and for pointing out some typos. We will incorporate these suggestions and correct the typos in the final version of the paper.

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

The Reviewer is right. The main reason we do not incur in a $O(T^{2/3})$ regret is that we can build a space of signaling schemes slices in $O(1 / \epsilon)$ rounds, such that, for each element, it is possible to associate a receiver's best response in $O(1 / \epsilon)$ rounds. Technically, this is made possible by employing the multiplicative Chernoff bound, which allows us, with $O(1 / \epsilon)$ rounds, to distinguish which states $\theta \in \Theta$ have a probability of being observed smaller than $\epsilon$, i.e., $\mu_\theta \le \epsilon$. In this way, the "exploration phase" of our explore-then-commit approach requires $O(1 / \epsilon)$ rounds, allowing us to achieve a $\sqrt{T}$ regret, by suitably choosing $\epsilon = O(1/\sqrt{T})$, instead of $O(T^{2/3})$ regret, as it is typically the case in explore-then-commit approaches.

Finally, we observe that in our "commit" phase, the sender does not commit to a fixed signaling scheme. Instead, they select a different signaling scheme $\phi_t$ computed by means of Algorithm 3, which receives as input an estimate of the prior distribution $\widehat \mu_t$ that is updated at each round.

Sec 6: maybe quickly introduce the setup first (in particular, what is a "sample" here)?

We thank the Reviewer for giving us the opportunity to better clarify the concept of ``sample'' within our framework. We use the term "sample" to refer to the feedbeack received by the sender when they commit to a signaling scheme. Intuitively, in a PAC-learning problem we do not have a finite time horizon, nor we are interested in the regret. Instead, we want to learn a $\gamma$-optimal solution by using the minimum possible number of samples (or equivalently, rounds), and we are not concerned about the regret accumulated while learning it.

We thank the Reviewer for the insightful feedbacks. We will also incorporate the two Reviewer's suggestions in the final version of the paper.

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.

We thank the Reviewer for giving us the opportunity to better clarify this aspect of our paper. The per-round running time of our algorithm is polynomial in the size of the input when either the number of receiver’s actions $n$ or that of states of nature $d$ is fixed. We agree with the Reviewer on the fact that, if both $n$ and $d$ are not fixed, then the per-round running time may no longer be polynomial in the input size in the worst case.

We observe that Algorithm 6 can find the H-representation of the polytopes $\mathcal{X}\_\epsilon(a)$ with polynomial per-round running time. In particular, to enumerate the vertices of the upper bounds, it can compute and query a different vertex at each round, without ever storing them all. In the current version, given the H-representation of the polytopes, our algorithm also computes the set of all the vertices $\mathcal{V}$, and eventually employs this set to instantiate an LP, whose cardinality may be exponential in either $n$ or $d$. However, it is possible to avoid computing these vertices and solve an equivalent linear program whose size is polynomial in $n$ and $d$. This can be done by employing the H-representation of the polytopes $\mathcal{X}\_\epsilon(a)$ computed by Algorithm 6, and exploiting a slightly different LP. This approach does not require to compute $\mathcal{V}$, thus achieving a polynomial per-round running time in every phase of the algorithm.

The theoretical analysis with the modified LP is almost straightforward given the results presented in the paper, as it only requires the introduction of some additional technical lemmas about polytopes. We will include this algorithmic approach in the final version of the paper and we are happy to provide additional technical details, if the Reviewer wants to.

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

We thank the Reviewer for the suggestions; we will incorporate them into the final version of the paper.

We thank the Reviewer for the insightful comments. We will adopt them in the final version of the paper and we will better discuss the points suggested by the Reviewer.

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?

The $\Omega(\sqrt{T})$ regret lower bound is a consequence of the sender's lack of knowledge of both the receiver's utilities and the prior distribution. Indeed, in our setting, it is possible to construct two instances with similar prior distributions and define the receiver's utilities so that the sender gains no information to distinguish between the two instances by committing to any signaling scheme. This is not possible if the utilities are known. Consequently, to distinguish between the two instances, the sender can only leverage the information contained in the states of nature sampled at each round and this results in the regret being at least $\Omega (\sqrt T)$.

It seems that the lower bound $\sqrt{T}$ in Theorem 3 requires 4 receiver’s actions. Does the $\sqrt{T}$ lower bound also hold if the receiver only has binary actions? Do the authors feel the regret may be improved (e.g., $\Theta(\log T)$ or even $\Theta(\log \log T)$) if one considers only binary receiver actions? As in the paper "EC’21—Online Bayesian Recommendation with No Regret," the authors show that when the sender only does not know the receiver’s utilities, a regret of $\Theta(\log \log T)$ by some variant of binary search is attainable when focusing on binary actions. (So I kind of feel your $\sqrt{T}$-regret may be mainly due to the unknown prior of the state realizations).

Developing a regret lower bound for instances with binary actions is an interesting research direction that we intend to explore in the future. We leave as an open problem whether it is possible to construct two instances similar to those presented in our lower bound, but with binary receiver actions, and still achieve a $\Omega(\sqrt{T})$ regret lower bound or a better upper bound can be achieved.

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?

The Reviewer is right. Our algorithm can also be employed in settings where the receiver has a different prior but the states of nature are sampled from the sender's unknown prior. We will better outline this aspect in the final version of the paper.

We thank the Reviewer for the insightful feedbacks and for pointing out some typos. Specifically, we will do our best to improve the part below Definition 1 and the comparison between previous models at Line 296 in the final version of the paper.

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?

The assumption that the receiver gets to know the sender's signaling scheme (a.k.a. the commitment assumption) is inherent in every Bayesian persuasion model. Moreover, the same assumption is standard in online Bayesian persuasion settings, where the receiver observes the sender's signaling scheme $\phi_t$ at each round $t \in [T]$. See, e.g., Castiglioni et al. (2020b) and Zu et al. (2021).

Notice that, by dropping the commitment assumption, one falls in a completely different model, which is commonly referred to as "cheap talk" in the economic literature. Indeed, if the receiver only observes a signal $s \sim \phi_{t, \theta_t}$ sampled from the signaling scheme $\phi_t$ at round $t$, without knowing $\phi_t$, it is not immediate how to define a best response for the receiver. We believe that addressing online learning problems in such a different setting is a very interesting research direction that is worth addressing in the future.

In algorithm 2, the feedback $a^t$ and $u_t^s$ seem not useful? If so, better to remove this line?

We agree with the Reviewer, we will omit it from Algorithm 2.

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?

Addressing settings with a non-truthful receiver is an interesting research direction that we intend to explore in the future. This begets considerable challenges that are out the scope of this paper.

Designing a mechanism in which the sender elicits information from the receiver's knowledge of the prior is certainly an interesting idea. However, since the sender has never access to the receiver's payoffs, it is not clear how the sender could effectively benefit from the receiver's knowledge of the prior. Indeed, receiver's best responses depend on both the unknown prior and receiver's unknown payoffs, which makes it challenging to extract information about the prior only.