Online Bayesian Persuasion Without a Clue

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.

Strengths

The problem appears meaningful and technically interesting. The idea of slices is natural, clean and powerful. The overall plan is clearly plausible, and yet not obviously viable. I'm happy to see that the authors were able to make it work, which seems to have involved nontrivial effort. The bound is reasonably tight.

Weaknesses

Ideally an instance-optimal bound would be more exciting, but perhaps that's too much to ask for. I'd also like to see more discussion of the PAC model and the optimality of the bound in that model (if applicable).

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$,

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

No concerns.

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.

Strengths

(1) [Significance] This work is a significant improvement over previous works on online learning in Bayesian persuasion where the sender learns either the prior or the receiver's utility. Learning the prior and utility simultaneously seems to be challenging. The authors are able to solve this problem, which is a significant contribution. (2) [Originality] A key technique in this work is performing high-dimensional binary search in the space of signaling schemes under a non-standard representation. In previous works, signaling schemes were usually represented by distributions over posterior distributions, and the search was performed on the space of posterior distributions. Such a technique does not work when the prior is unknown. This work instead represents signaling schemes by the vector $(\sigma_\theta(s))_{\theta \in \Theta}$, the probabilities of sending a signal $s$ under different states $\theta$. This new representation circumvents the unknown prior issue. So, I think this new representation is an interesting trick and a technical novelty. (3) [Quality] Non-trivial lower bound results are provided, complementing the upper bounds results.

Weaknesses

(1) [Quality] The proposed algorithm seems to have an exponential running time in the worst case. Specifically, the number of vertices $\mathcal V$ of the polytopes seem to be exponential in $d$ or $n$, which leads to an exponential running time. The authors didn't discuss the computational complexity of their algorithm, nor provided a computational-hardness result.

Questions

Can the authors respond to weakness (1)?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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.

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.

Strengths

The paper follows a line of work in the literature on Stackelberg games that study how to learn to commit optimally by querying the follower's optimal responses. I find it natural and reasonable to ask the same question in Bayesian persuasion. While the overall approach works similarly by building the follower's (receiver's) best response regions, the paper shows that there are some unique features of the persuasion setting, which require additional techniques. The estimation of the prior, in particular, can only be done approximately. The paper nicely handles this aspect in their algorithm. The concept of slice is also novel and interesting (though the naming is somewhat less intuitive). The results look very complete, with matching lower and upper regret bounds. The paper is also well-writen and overall clear.

Weaknesses

- The part below Definition 1 until the end of that page is a little dense and could probably be improved. The notation in this part is also a bit hard to follow. However, this is overall minor. - 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

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

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Nothing is mentioned, but no concern here.

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.

Strengths

I truly enjoy reading this work. I think this work significantly contributes to the recent line of research on using regret minimization to study the persuasion with uncertainty over the underlying environments. The results developed in this work are strong and interesting. The presentation of this work is crisp and the paper provides intuitions for the algorithmic challenges and its steps of algorithm design. Overall, I think this work makes a strong addition to the NeurIPS.

Weaknesses

I don’t have particular concerns about the paper. Maybe one minor point is that the authors may want to include some discussions about the computational efficiency of the designed algorithm.

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?

Rating

8

Confidence

5

Soundness

4

Presentation

4

Contribution

4

Limitations

N/A

Happy with authors' response

I am happy with the authors' response and raise rating to 7. Indeed, adding discussion on the computational complexity might further strengthen the paper.