Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies bayesian persuasion where a farsighted receiver plays in a sequential decision making problem, and considers both full feedback and bandit feedback setting. The authors first proved a negative result that shows it is impossible to be persuasive without the knowledge of the prior. Then a relaxed online learning problem is considered, and the authors proposed algorithms that guarantee sub-linear regret for both the sender and the receiver.

strengths_and_weaknesses: The problem of bayesian persuasion in sequential problem is well-motivated. However, prior works [17, 25] only consider myopic user. This paper is the first to propose algorithms for farsighted receiver in sequential decision making problem, which can be solved in polynomial time.




questions: I'd appreciate it if the authors could help me interpret the result in this paper compared with the negative result for farsighted receiver in MDP in [17]. What is the key difference between the two problem settings that makes the problem in [17] NP hard, while the problem in this paper solvable in polynomial time?

Is the trade-off between the regret of sender and receiver attained by Algorithm 1 optimal for the full feedback setting?
limitations: No.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies Bayesian persuasion between an informed sender and a
receiver in a sequetial decision making (SDM) setting. In contrast to
standard assumptions in the literature, the sender is uninformed of
the prior of the payoff relevant state, whereas the receiver is
farsighted. The paper designs an online-learning algorithm that
attains no-regret for the sender (against the known-prior benchmark)
while being persuasive for the receiver, where the latter criterion is
defined as a low-regret condition. The paper considers both the
full-feedback setting (where the sender observes all the random
realizations in the SDM decision tree, even off-path), and the bandit
feedback setting (where only the random realizations on the traversed
path is observed by the sender). For the full-feedback setting, the
authors provide an algorithm that achieves $\tilde{O}(\sqrt{T})$
regret for both the sender and the receiver. For the bandit-feedback
setting, the regret guarantees are somewhat weaker for both the sender
and the receiver. 
strengths_and_weaknesses: The paper considers an extension of Zu et al (2021) who consider the
problem of learning to persuade a receiver taking a single action at
each time, when prior distribution is unknown. Here, the authors study
this problem in settings where the receiver has to make multiple
sequential decisions at each time period (and the sender makes
multiple recommendations, at each information set of the receiver).
Unlike Zu et al, the recommendations here need not be persuasive (and
the authors show that it may not be possible to achieve this); instead
the authors require that the receiver incurs low regret from following
the sender's recommendations. The authors propose a natural signaling
algorithm that achieves this notion of persuasiveness while at the
same time ensuring that the sender's regret is low.

While the theoretical contribution is solid, the paper does not
motivate the specific applications of their model. In particular, the
model requires that a single sender and a single receiver engage in
repeated sequential decision making (with iid noise) -- it is unclear
to me where such an interaction might arise in an application. One may
motivate the repeated interaction as between a single sender and a
stream of receivers (as in Zu et al), but then the no-regret version
of persuasiveness for the receiver needs justification.

Furthemore, the modeling assumptions about the sender's knowledge are
unclear. For instance, I believe the paper assumes that the sender,
when making a recommendation, observes the specific decision node of
an information set reached by the receiver, but not the realizations
of future randomness. It would be helpful to make this explicit. But
more importantly, in the full-feedback setting, if the sender can
observe the *past* realizations on off-path chance nodes, *and* the
randomness across chance nodes that are not descendant-ancestor pairs
are allowed to be correlated, then observing such *past* realizations
can be beneficial to the sender. 

Relatedly, one would also need to make further assumptions about the
sequence form prior, as current formulation may allow correlations at
chance nodes that are not decendant-ancestor of each other. As
mentioned above, this may be important for the full-feedback setting.
questions: It might be helpful if the authors can motivate the repeated SDM
persuasion problem through an application context. I don't expect an
exact fit, but some examples would help in highlighting the
significance of the problem.

Is there a lower-bound characterization in the full-feedback setting?

Repeating the comment above, in the full-feedback setting, if the
sender can observe the *past* realizations on off-path chance nodes,
*and* the randomness across chance nodes that are not
descendant-ancestor pairs are allowed to be correlated, then observing
such *past* realizations can be beneficial to the sender. Does this
affect the analysis?
limitations: None
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies a Bayesian persuasion problem in a setting in which the sender and receiver do not initially know the distribution/prior over random events, and must learn this distribution over time. The goal is to provide algorithms that are low regret for the receiver in this setting (assuming that the sender follows the recommendation) while guaranteeing that it is low regret for the sender to follow the recommendations of the algorithm.
strengths_and_weaknesses: Strengths:
- The authors consider a novel setting for signaling where the sender and receiver do not know the distribution of state of the world/random events in advance. I think this is an interesting and refreshing contrast from the standard (and often unrealistic) assumption that there is a commonly known prior
- It is nice that the authors consider two types of feedback: a more informative full-feedback setting in which all random events are observed, versus a bandit-style feedback where we only receive information about the arms that we actually pull. 
- The results feel tight and complete: the paper both develops a low regret algorithm for persuasion but also show that the trade-off achieved by their algorithm is essentially tight/cannot be improved for non-trivial regimes of parameters \alpha. 

Weaknesses:
- The writing feels sometimes too formal and technical. I understand the authors want to give proper preliminaries for sequential decision making problems, but the formalism involved in describing SDMs in all their generality is heavy, and how it maps to/what the chance and decision nodes represent in the specific problem at hand only comes up on page 4. I think in this case it is avoidable and the main body of the paper can be written almost entirely in the simpler language of Section 3. Please let me know if I am wrong, but here it seems the SDM language may really only needed when it comes to showing technical results and could be moved to the appendix. 
- Back to the formalism, there are places in the paper where it could really benefit from some English/intuitive descriptions of some of the definitions. E.g., there are two very similar definitions of deviation policies with little explanation of how they differ from each other (I do understand after looking carefully at the definitions that the first one allows for deviations at several points/infosets of the algorithm while the single-point deviation is less general and can only deviate at a single, pre-specified infoset, but given the heavy-handed notations and formalism, this is a bit hard to parse)
- The paper shows that it is sublinear regret for the receiver to follow the algorithms recommendations, showing that it is a good strategy for the receiver. It however is not clear to me that it implies that this is the only good strategy for the receiver, and the regret guarantees for the sender assumer the receiver always follows the recommendation. I think it might be worth highlighting and discussing this point a bit more, and it would be great (though probably out of scope) to have an algorithm for the sender that is robust to any no-regret algorithm the receiver may be using. 

Overall I think this is i) an interesting problem to look at where the sender and receiver do not have prior information about the distribution of “states of the world” and ii) comes with good regret bounds for both the sender and receiver with tight bounds for the sender, and so I believe the technical contribution of the paper warrants acceptance. However, I think clarity can be improved significantly here and the writing is really geared towards experts in sequential decision making and extensive form games and possibly a bit hard to understand otherwise. 
questions: - Could there be other strategies for the receiver that yield similar or better regret, and is the author’s algorithm robust to such a chance in receiver behavior?


limitations: The paper does discuss the limitations of their current regret bounds and how they only seem tight for \alpha < 2/3. The paper does not directly discuss potential harms, but I’m not sure whether the discussion of such harms is particularly relevant in a theory paper about Bayesian persuasion (it might be more suited to a paper that applies these techniques to a problem of practical interest).
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study the problem of Bayesian persuasion (BP) with an unknown prior in the sequential decision making (SDM) problem. The traditional BP problem is as follows: a sender with knowledge of the outcomes of random events commits to a signaling scheme (i.e., a mapping from random states to action recommendations) before observing the outcome of the random event. The sender then signals according to their signaling scheme, and the receiver takes an action based on the signal. In the classic BP setting, the goal of the sender is to design an incentive compatible (persuasive) signaling scheme which maximizes their utility in expectation over the random event prior. In addition to being the first to study BP in the SDM setting, the authors consider the case in which the prior over random events is unknown. Since the prior is unknown to the sender, the authors study an online version of the problem in which a sequence of T receivers arrive one after another.

First, the authors provide an (approximate) characterization of the set of persuasive signaling schemes via a polynomially-sized polytope. They show that using this polytope, the sender can compute the optimal signaling scheme by solving a polynomially-sized linear program when the prior is known. 

When the prior is unknown, the authors show that it is generally impossible to guarantee that a sequence of signaling schemes are persuasive with high probability. Because of this, they focus on the relaxed goal of ensuring that the cumulative receiver regret is sub-linear in the time horizon.

The authors provide a learning algorithm (Algorithm 1) for the full-feedback setting (i.e., the setting in which the sender is able to observe the realized outcome of all possible random events) which guarantees O(\sqrt{T}) sender and receiver regret with high probability. Next, they build on their algorithm for full feedback to provide an algorithm for the bandit feedback setting (Algorithm 2). Under the bandit feedback setting, the sender only observes the terminal node which is reached at the end of the SDM problem. At a high level, the algorithm is split into two phases: an explore phase, which uses a uniform exploration policy to build an unbiased estimator of the prior, and an exploit phase, which uses the "optimism in the face of uncertainty" priniciple to minimize sender regret. Depending on how long the exploration phase runs for, there is a tradeoff between sender and receiver regret. However, the authors show that this tradeoff is tight for a large portion of the tradeoff frontier.
strengths_and_weaknesses: Strengths:
The authors study a novel and mathematically interesting version of the Bayesian persuasion problem and provide a relatively complete set of results. Additionally, the presentation of the results is clear, and the technical details appear to be correct.

Weaknesses: 
The only real weakness I see is the lack of motivation. In the introduction, the authors motivate the general BP problem, but not the specific SDM setting they consider. Therefore, it is hard to gauge the significance of the authors' results. On one hand, if the problem of BP in SDMs can be well-motivated, I believe this paper is certainly worthy of acceptance. On the other hand, if the setting is not a realistic one in which persuasion may occur, the results may be mathematically interesting, but not very significant. For this reason I have given this submission a borderline accept, although I would be more than happy to raise my score if the authors can address my questions listed below.
questions: What are some concrete examples of a situation in which a sender would have knowledge of the outcomes of the chance nodes of a SDM and would want to persuade a sequence of receivers?

Point of confusion: In the BP literature, there is usually an inherent misalignment between sender and receiver objectives. In the traditional BP setting with a known prior, this issue is addressed by using a signaling scheme which maximizes sender utility subject to the constraint that the receiver is incentivized to follow the sender's action recommendations. In this paper, the authors study a relaxed setting in which the sender wants to minimize receiver regret. Intuitively, why is there no tradeoff between sender and receiver regret, when this incentive mismatch between sender and receiver still exists? It feels like there should be some tension between minimizing sender and receiver regret, similar to the tradeoff which arises due to the exploration phase in Algorithm 2.
limitations: The authors adequately address the limitations of their work.
review_title: null

Meta-review: metareview: The reviews are all positive and reviewers agree that the paper studies a novel setting with solid technical contributions.
confidence: Certain
Decision: Accept