Markov Persuasion Processes: Learning to Persuade From Scratch

We agree with the Reviewer's comparison between our work and [1]. Here, we provide a detailed answer to each point.

(A) and (B). I argue that typically in RL theory, most of the technical difficulty comes from learning the transition function, and knowing the reward function doesn’t help much. The distinction between stochastic and deterministic rewards is also typically not significant. To semi-formalize this, I argue below that for {0,1} rewards, any no-regret algorithm for MDPs with known deterministic rewards can also solve MDPs with unknown stochastic rewards. This reduction breaks down for more general rewards than {0,1}, but I think the conceptual takeaway still holds: that most of the difficulty comes from learning the transition function. Also note that {0,1} rewards are sufficient for most RL lower bounds [2].

We agree with the Reviewer’s arguments. However, we would like to point out that the main challenges tackled in our paper do not stem from rewards being stochastic, but rather on the fact that both the transitions and the receiver’s utility functions are unknown, as the Reviewer noticed, and the particular type of feedback received by the learner in our setting. Notice that the knowledge of the receiver’s utility is crucial in our framework to achieve the desired incentive compatibility. In this work, we decided to work with stochastic rewards rather than simplifying to deterministic ones since notation was not excessively cluttering.

(C). I would guess that since the reward function for each episode is iid, their average quickly converges to the mean, such that this does not add much difficulty. However, I may be wrong, and I could imagine this component adding some novelty to the paper.

The Reviewer is right, stuff converges quickly so it is easy to achieve a $O(T^{2/3})$ regret/violation bound. The main challenge in our setting is how to guarantee a $O(T^{\alpha})$ regret and $O(T^{1 - \alpha/2})$ violation, for each $\alpha \in [1/2, 1]$. Indeed, this was still an open problem in similar settings. Notice that Bernasconi et. al. (2022) achieve such guarantees only when $\alpha \in [1/2, 2/3]$. Furthermore, the incentive compatibility constraints introduce partial observability in the feedback that the sender receives regarding the constraints at each round. This requires different approaches compared to those used in traditional constrained Markov decision processes.

(D). If I understand correctly, the present submission instead assumes that the receiver always plays the action recommended by the sender and does not play a best response at all. The authors then show that the cumulative violation of the persuasiveness constraint is sublinear in T. I think this approach is reasonable: as the authors note, it is impossible to be immediately persuasive when the sender starts out with no information about the receiver. However, I don’t think this is a strength over [1]: this model seems easier in some ways and harder in some ways than [1]’s assumption of perfect best response.

The reviewer is right, the two are different models and present different challenges. While we attempt to relax some of the assumptions in [1], such as the fact that the utility of the receivers are unknown, at the same time we assume that the receivers follow the recommended actions.

Beyond the comparison with [1], I also have some concerns about the model. I’m unsure whether there exist natural applications which both involve Bayesian persuasion and MDP-style dynamics. The authors cite movie recommender systems as a motivating example, but what do the states represent? Receivers would be users, right? If I understand correctly, the sender interacts with a new receiver on every time step, so how does one user affect the state of a different user? It also seems like users’ incentives are pretty aligned with the recommendation system (they want to watch movies that they like), so it seems unlikely for users to engage in reasoning like “the system is recommending me movie A which isn’t what I want to watch but it does give me information about which movie I should actually watch”.

The main real-world applications of these models are presented in the papers that first introduced them, see, e.g., Section 1 in (Wu et al. 2022). We did not report these examples in our work either due to lack of space.

The setting of this paper is similar to the setting of [1]. To be specific, in this paper, the authors consider MDP with persuasiveness as the stochastic long-term constraint because the receiver's reward function is drawn from some distribution. In [1], the authors consider MDP with constraint matrices, which can be stochastic or adversarial. As a consequence, these two papers share a similar upper-bound technique that maintains estimators and confidence bounds of the environment and uses them to update the occupancy measure. The similarity makes me cast doubt on the novelty and technical contribution of this paper. I think the authors should clarify the difference between these two papers.

We agree with the Reviewer that both papers use the occupancy measure tool. However, aside from this similarity, the two papers are very different. We outline the main differences below.

• The algorithm in [1] requires full feedback and does not work under partial feedback, while our main contribution addresses the partial feedback case. Furthermore, even the full-feedback case considered in [1] is much stronger than the one considered in this paper. Specifically, [1] assumes observing the loss of all the possible triplets $(x, \omega, a)$ at the end of the episode, whereas we assume observing only the triplets visited during the episode.

• From a technical point of view the two are also unrelated. Indeed, the IC constraints cannot be handled using the technique from [1]. This is because, in our case, the constraints depend on the difference between the action recommended by the sender, $a$, and another action, $a'$, which is the best response. However, the sender receives feedback only on the receiver's utility for action $a$ and does not observe anything regarding the utility in $a'$. This introduces partial observability in the IC constraints, which cannot be addressed with the techniques from [1], as mentioned by the Reviewer.

For the proposed algorithm: (1) the computational complexity can be another issue that may prevent MPPs from being used in practice because large linear programming needs to be solved at every round; (2) the intuition of the algorithms should be explained more for better understanding.

(1) Linear programs can generally be solved efficiently. However, designing more efficient algorithms represents an interesting future direction. (2) We did our best to give any possible intuitions about the algorithms presented in our work. If there is a specific point in the algorithms that is not clear, please let us know.

Is the regret bound of the algorithm in the full feedback setting tight?

We refer the Reviewer to the updated version of the paper, where we present the lower-bound for the full-feedback case (see Theorem 6), showing that our result is tight.

I think the major weakness of this paper is the missing case study. While the authors highlight “practical/real-world application” as the key motivation behind studying this variation of MPP, they fail to provide an example (or a simple toy case). I think the paper would benefit from a case study as it would also help readers to understand the problem better.

We agree with the Reviewer, we simply did not add a real-world example due to space constraints. However, the main real-world applications of these models are presented in the papers that first introduced them, see, e.g., Section 1 in (Wu et al. 2022).

I am not an expert in this topic, but from what I gathered, the setup in the paper resembles a general-sum game, is that correct? If so, could it be also extended to model a zero-sum game in which it may not be in the receivers' best interest to follow the sender?

We believe that our model is quite different from general-sum games, and that the game-theoretic model closest to ours is represented by Stackelberg games. Indeed, while in general-sum games the two agents may play simultaneously, our framework includes a commitment stage, which is not present in general-sum or zero-sum games.

In line 383: ...the sender does not observe sufficient feedback about the persuasiveness of $\phi_t$. Could the authors comment on what are the necessary feedback to infer about the persuasiveness and why the information about only the agents' rewards for the visited triplets are not enough?

To be perfectly persuasive, the sender should know exactly both the prior distribution and the receiver's utility function. While in our paper the sender just observes samples from the probability distributions that define these quantities.

Although this paper provides a relatively complete picture for the online MPP problem, most of the techniques are standard and directly come from previous works. The upper bound techniques come from the constrained Markov Decision Process (MDP) literature, e.g., Germano et al, 2023, as the authors mentioned. The MPP problem is basically a constrained MDP with linear objective and linear constraint (maximizing the sender's expected reward subject to persuasiveness constraint), for which the constrained MDP literature already provides satisfactory solutions.

The results in Germano et al. (2023) are developed for a feedback that is much stronger than what we refer as full-feedback in our work. Precisely, in Germano et al. (2023), the learner observes the rewards and constraints sample for every path. Thus, their techniques cannot be employed in our work. Furthermore, the IC constraints cannot be handled using the technique from Germano et al. (2023), or any other CMDP algorithm. Indeed, in our setting, the constraints depend on the difference between the action recommended by the sender, $a$, and another action, $a'$, which is the best response. However, the sender receives feedback only on the receiver's utility for action $a$ and does not observe anything regarding the utility in $a'$. This introduces partial observability in the IC constraints, which cannot be addressed with the techniques from Germano et al. (2023), or any other CMDP algorithm as mentioned by the Reviewer.

Although the regret bounds in this work are tight in $T$, there is still a large gap between the upper and lower bounds in terms of other parameters $L, |X|, |\Omega|, |A|$. The lower bound does not contain those parameters, while the upper bound have polynomial dependency on them. In the full information setting for example, an upper bound in the form of $O(parameter * \sqrt{T})$ is typical in the online learning literature (in particular, it can be easily derived from the previous constrained MDP techniques), and a lower bound like $\Omega(\sqrt{T})$ is also expected. Since this work aims to give a complete picture for the online MPP problem, I think it is important to characterize the tight dependency of the regret on parameters other than $T$ as well. Moreover, given that there are already several previous works on online Bayesian persuasion and MPP (like Wu et al (2022)), only characterizing the regret dependency on $T$ does not seem to be a large enough contribution to the existing literature.

The main goal of our work was to both relax some of the limiting assumptions made by Wu et al. (2022), such as the assumption that the sender knows the receivers’ utility function, and design an algorithm that guarantees $O(T^{\alpha})$ regret and $O(T^{1 - \alpha/2})$ violation for each $\alpha \in [1/2, 1]$. Both of these were open problems, which we address in our paper. Understanding the tightness of our algorithm with respect to all its parameters is an interesting future direction, but we believe it was not the primary point to be addressed.

How is your work different from the constrained MDP works you cited? What's the additional contribution?

Please refer to previous questions.

Can you provide a lower bound that includes the parameters of the environment?

It is an interesting direction that we want to explore in the future. At the moment, we don’t actually know if these constants are tight or not.

Thank the authors for the response!

Now I agree that this work is different from the CMDP literature. It might be worthwhile to compare this work with the CMDP literature more explicitly in Appendix A. However, I still have other concerns:

• Regarding the tightness of lower bound, the authors say that "it was not the primary point to be addressed", and the main goal of this work was to "both relax the limiting assumptions made by Wu et al. (2022), such as the assumption that the sender knows the receivers’ utility function, and design an algorithm that guarantees $O(T^\alpha)$ regret and $O(T^{1-\alpha/2})$ violation for each $\alpha \in [1/2, 1]$". However, this main goal seems a bit incremental. As reviewer AiNi mentioned, a more explicit comparison with Wu et al (2022) might be needed for readers to see the novelty of this work. And the trade-off between $O(T^\alpha)$ regret and $O(T^{1-\alpha/2})$ violation has been noticed by Bernasconi et al (2022) [Sequential information design: Learning to persuade in the dark]. Although the present work improves previous work by extending the analysis from $\alpha\in[1/2, 2/3]$ to $\alpha\in[1/2, 1]$, this contribution still seems too incremental.

I read other reviews and agree with two other concerns about this work:

• One is the lack of real-world motivation for MPP (raised by both w5p2 and AiNi).

• The other is AiNi's comment (D) "The present submission assumes that the receiver always plays the action recommended by the sender and does not play a best response at all. The authors then show that the cumulative violation of the persuasiveness constraint is sublinear in T. I think this approach is reasonable: as the authors note, it is impossible to be immediately persuasive when the sender starts out with no information about the receiver. However, I don’t think this is a strength over [1]: this model seems easier in some ways and harder in some ways than [1]’s assumption of perfect best response." This seems to be a limitation of this work, because there is no guarantee that the receiver will actually follow the action recommendation if the recommendation is only approximately persuasive.

The authors claim that it is impossible to satisfy persuasive constraints at all rounds. However, the negative result is provided only for the partial feedback setting, and I wonder if one can avoid the negative result for the full feedback setting. If so, it makes more sense to study a version of MPP where the constraints are satisfied with high probability. In general, I favour the guarantee of high probability persuasion compared to providing only upper bound on the total amount of violation. Since we cannot make any assumption about receiver's preferences, it is not clear whether the receivers will still follow the sender's recommendation.

We thank the Reviewer for the opportunity to properly tackle this aspect. In our setting, it is not possible to guarantee zero violations with high probability if the goal is to design a no-regret algorithm, even when full-feedback is available. We updated the paper, proving this lower bound for the full-feedback setting (see Theorem 6). Please refer to the updated version of the paper for the formal proof.

The proposed algorithms and the proof techniques are very similar to prior work (in particular Bernasconi et. al. 2022 or Gan et. al. 2024). All these works propose explore then exploit (based on optimistic planning) algorithm for persuasion problems. So the authors need to clarify what are the technical difficulties in the analysis in this paper.

Approaches such as explore and commit are well known in the literature. In our setting, the main challenge is how to guarantee a $O(T^{\alpha})$ regret and $O(T^{1 - \alpha/2})$ violation, for every $\alpha \in [1/2, 1]$. Indeed, Bernasconi et. al. (2022) achieve such guarantees only when $\alpha \in [1/2, 2/3]$, while Gan et. al. (2024) when $\alpha = 2/3$. On the contrary, our work is the only one to completely close the gap between upper and lower bound. This result is attainable by employing a different kind of exploration phase w.r.t. Bernasconi et. al. (2022) and Gan et. al. (2024), that is, we continuously shrink the decision space before the beginning of the exploitation phase. We believe that this is a remarkable contribution of our approach.

Furthermore, while we agree with the Reviewer that our algorithmic approach is similar to existing ones, we emphasize that our technical analysis significantly differs from the one pointed out by the Reviewer. Specifically:

• Bernasconi et al. (2022) do not need to address the uncertainty associated with the transition model (note that they do not work in a Markovian setting) and the receiver's utility function.

• Gan et al. (2024) employs an exploration procedure adopted from Jin et al. (2020). However, this exploration procedure does not guarantee to achieve a tight $O(T^{\alpha})$ regret and $O(T^{1 - \alpha/2})$ violation, for every $\alpha \in [1/2, 1]$. To do so, we need to maximize the probability of visiting each triplet $(x, \omega, a)$ for $N$ times during the initial phase, in order to continue shrinking the decision space during the commitment phase.

What is the trade-off between reward regret and constraint violation for the full feedback setting?

As specified in the answer above, the $O(\sqrt{T})$ regret/violation bound is tight even in the full feedback case. Please refer to the updated version of the paper.

What is the time-complexity of Opt-Opt problem (2)?

Problem (2) (Opt-Opt) is a linear program, so it can be solved efficiently in $\textnormal{poly}(|X|, |A|, L)$ time.

Can you generalize your results beyond tabular MDP?

Extending the results to general MDPs is an interesting future direction. We conjecture that, with some work, our approach can be generalized to achieve an $O(T^{2/3})$ regret and violation bound in general MDPs. However, achieving $O(T^{\alpha})$ regret and $O(T^{1 - \alpha/2})$ violation, when $\alpha \in [1/2, 1]$, as done in our paper for the tabular case, would require new ideas and a different approach.

[Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870– 4879. PMLR, 2020.]