Markov Persuasion Processes: Learning to Persuade From Scratch

We thank the Reviewer for the positive evaluation of our work.

Re: "Can the authors explicitly point out the improvement of their paper since the last version? Overall, I believe my technical questions about this paper have been answered again and again, and I have become overall satisfied with their answers, given that many problems cannot be meaningfully addressed under the current framework. I think the authors could have used some of their answers to acknowledge the limitations of this work."

Compared to the initial version of the paper, we have introduced a new lower bound for the full-feedback setting (Theorem 3) and improved the presentation in several areas, for example by highlighting that other works adopt similar assumptions and by adding Figure 1. While the questions raised by the Reviewer are surely interesting, addressing them would require a complete rethinking of our work, as also pointed out by the Reviewer. In summary:

• Within our framework, it is provably not possible to be persuasive in the first rounds, since no information about the environment is available. This challenge has been addressed by other works in similar settings (see, e.g., [Bernasconi et al., 2022, Cacciamani et al., 2023, Gan et al., 2023]) by considering the total violation of persuasiveness, and thus we believe that this is a reasonable approach that deserves to be investigated in MPPs as well.

• Addressing the case in which the receivers are no-regret learners would require completely different approaches, outside the scope of our paper. Nevertheless, we believe that following this research direction would surely be interesting in future works.

• Finally, let us remark that, without sender’s knowledge of receivers’ utilities, introducing robustification/pessimism into signaling schemes is of no help, unless one completely changes our model by introducing additional assumptions.

We are committed to expanding the introduction in the final version of the paper to better clarify the limitations raised by the Reviewer.

We thank the Reviewer for the positive evaluation of our work.

Re: "Can the authors comment on practical applications of their setup and proposed algorithm?"

In the following, we provide a simple illustrative example. Consider a product recommendation platform that suggests items to multiple users. In this setting, the platform acts as the sender, while the users are the receivers who select actions, such as clicking on or purchasing recommended products. The model distinguishes between two types of information: the outcome ($\omega$), which represents the sender’s private knowledge (e.g., product features and availability), and the state ($s$), which captures the dynamic environment (e.g., user browsing history). Outcomes are drawn from a prior distribution and are used by the platform to personalize its suggestions. The state evolves over time based on the user’s action, the previous state, and the realized outcome. Both the sender’s and the receivers’ utilities depend on the chosen action, the current state, and the realized outcome.

We will surely include this discussion in the final version of the paper.

Re: Can the authors comment on the practical efficiency of their algorithm? Some, even if of small-size, computaitonal results would better emphasize the relevance of the work.

Our algorithm requires solving a linear program at each round $t \in [T]$, with a number of variables and constraints that is polynomial in $|X|$, $|A|$, and $|\Omega|$; thus, the per-round update can be solved in polynomial time and the running time depends on the employed solver. Current solvers can solve these kinds of problems efficiently. The main goal of this work is theoretical, but we leave as an interesting direction for future work the evaluation of our algorithms' performance in practice.

Re: "Can the authors comments on the numerics of their algorithm? I am asking about the many linear programming problems that the proposed algorithm solves. Are they well-conditioned or can there be cases (e.g, with small state spaces, symmetric transitions, or almost identical receivers) where the persuasiveness and occupancy constraints become very similar, leading to rank-deficient basis matrices?"

From a theoretical point of view, any linear program can be solved in polynomial time. Clearly, since our model is fully general, these kind of problems could occur. As we mentioned above, we leave to future works the study of more applicative-oriented settings where these kinds of questions have a clearer answer.

We thank the Reviewer for the positive evaluation of our work.

Re: "Can the framework be extended to the case where the learning steps are limited, or where each step incurs a cost?"

For the limited steps case, our algorithm needs to know the time horizon in advance. Differently, the case where the learner incurs an additional cost during the learning dynamic can be addressed by employing standard techniques for constrained Markov decision processes (see, e.g., [1]), assuming that the cost depends on the state-action pair only.

[1] "Constrained Markov decision processes", Altman (1999)

We thank the Reviewer for the positive evaluation of our work.

Re: I learned about MPP while reading this submission. I do not follow what do the states of the MDP represent for any practical situation. Can the authors explain that? Further, what are some practical examples where MPP might be useful?

In the following, we provide a simple illustrative example. Consider a product recommendation platform that suggests items to multiple users. In this setting, the platform acts as the sender, while the users are the receivers who select actions, such as clicking on or purchasing recommended products. The model distinguishes between two types of information: the outcome ($\omega$), which represents the sender’s private knowledge (e.g., product features and availability), and the state ($s$), which captures the dynamic environment (e.g., user browsing history). Outcomes are drawn from a prior distribution and are used by the platform to personalize its suggestions. The state evolves over time based on the user’s action, the previous state, and the realized outcome. Both the sender’s and the receivers’ utilities depend on the chosen action, the current state, and the realized outcome.

We will surely include this discussion in the final version of the paper.

Re: "Why is the assumption that a new receiver observes $a_k$ at each time step important?"

We thank the Reviewer for pointing out this aspect. In Bayesian persuasion problems, it is standard for the receiver to observe the action $a_k$, as this avoids tie-breaking issues among multiple optimal actions. (see, e.g., Kamenica and Gentzkow [2011]).

Re: In their model, the sender/principal commits to a signaling policy throughout the play. This seems to be very restrictive. Very reasonably, I would assume the signal policy is allowed to be adopted as new information is revealed.

We thank the Reviewer for the question. We remark that, in episodic loop-free MDPs---and similarly in episodic loop-free MPPs---updating the policy within an episode does not provide any benefit. This is because the information acquired during the early steps of an episode cannot be leveraged to improve predictions for the later steps within the same episode. Instead, such information only becomes useful in the first steps of the next episode.

Re: A minor comment: In RL terminology, partial feedback (as referred to by the authors) is called bandit feedback in most other papers. While the full feedback (as referred to by the authors) is still weaker (as rightly pointed out in the footnote). My suggestion would be to to call the full feedback as simply partial feedback

We thank the Reviewer for the observation. We will better specify these aspects in the final version of the paper.

Re: In Lines 150-155, the authors argue for a direct and persuasive signal policy for a one-shot Bayesian persuasion framework. The argument is not clear. Further, the actual algorithm 2 does not play a persuasive policy. It is not clear what the structure of the sender's signals is with algorithm 2. What is the significance of playing a persuasive policy?

In classical one-shot Bayesian persuasion, it can be shown that there is no loss of generality in restricting attention to signaling schemes in which the receiver is incentivized to follow the sender’s recommendation. These signaling schemes are called direct (the set of signals coincides with the set of actions) and persuasive (the receiver follows the recommended action).

In our setting, we have no prior knowledge about the receiver at the beginning of the interaction, so we must slightly relax the persuasiveness constraint. Since this relaxation leads to a broader set of signaling schemes, it remains possible to achieve the utility of an optimal persuasive and direct signaling scheme (see, e.g., Kamenica and Gentzkow [2011]).

Re: The MDP structure of MPP induces a POMDP - Partially observable MDP. The authors should include this characterization as well.

The Reviewer is correct: our setup introduces partial observability of the (persuasiveness) cost incurred by the sender. We will clarify this point more explicitly in the final version of the paper.

Re: A lot of information is pushed to the appendix about Problem 2, as solved in Algorithm 2. A summary of the optimization program will be helpful. e.g., what does the objective look like, the main constraints? I am concerned about the computational traceability of the same. If it is tractable, what is the runtime? Further "optimistic exploration" is hidden in the objective of the optimization. Given the details of the main paper is hard to understand how the uncertainty quantification is being done by the use of optimism. Unfortunately, this is one of the biggest weaknesses of the paper."

Regarding Problem 2, we agree with the Reviewer that much of the information is deferred to the appendix. Unfortunately, this is due to the space constraints of the NeurIPS format. In the final version of the paper, we commit to inserting the LP in the main part, due to the extra page available.

The optimization problem (Problem 2) solved at each round by our algorithm is a linear program with a number of variables and constraints polynomial in $|X|$, $|A|$, and $|\Omega|$. As such, it can be solved in time polynomial in these parameters. The actual runtime depends on the specific LP solver used but remains polynomial in the overall input size.