Generalized Principal-Agent Problem with a Learning Agent

First point: My main concern is about the relation between the paper and existing results in the link between no-regret and equilibrium. .... Is it possible to formulate your setup as a game and then apply the equilibrium results to obtain your convergence/approximation rates.

We note that the existing results on the convergence of no-regret learning to equilibrium do not apply to our problem. The existing results are: when multiple players simultaneously use no-regret learning to play a game repeatedly, they will converge to a coarse correlated equilibrium. However, our problem has only one no-regret learning player -- the agent. The principal is not learning. The principal aims to find the optimal strategy to play against the no-regret learning agent. And the benchmark we are comparing to is the Stackelberg equilibrium (where the principal first commits, the agent then best responds), which is different from coarse correlated equilibrium (which is a simultaneous equilibrium notion). So, our results are not implied by the existing results in convergence of multi-agent no-regret learning.

Second point: To me, this setup is exactly an online version of Bayesian Persuasion canonical setup, .... I agree that it is different from what is proposed in the Generalized Principal-Agent Problem with a Learning Agent setup (page 4 in the paper) but it seems quite close though. The type of the agent in Castiglioni et al. could be represented as the strategy picked by the agent at round in this model. I think that this work deserves a more thorough discussion.

Indeed, our model of persuasion with a learning agent is similar to online Bayesian persuasion. However, there are two key differences between our work and [Castiglioni et al]. The first is the receiver's behavior. In our problem, the receiver does not need to know the environment or the sender's signaling scheme; instead, the receiver uses a learning algorithm to choose actions (and observes feedback after each round). But in [Castiglioni et al], the receiver at each round knows their own utility and the sender's signaling scheme, so the receiver performs Bayesian update after receiving a signal and take the best-responding action. The second difference is in the sender's knowledge. In [Castiglioni et al], the sender does not know the receiver's type (hence not know the receiver's utility function); their work designs an online learning algorithm for the sender to compete against the best fixed signaling scheme in hindsight. In our work, the receiver does not have a private type, the sender knows everything including the receiver's utility function, and the sender's goal is to exploit the learning behavior of the receiver. Given the different setups, the results from the two works are not directly comparable in our opinion.

We don't think the type of the agent in [Castiglioni et al] could be represented as the strategy picked by the agent in our model, because the type in [Castiglioni et al] is adversarially chosen by the nature, while our agent's strategy is picked by the agent's no-regret learning algorithm. Moreover, the type and the strategy affect the principal's utility in completely different ways.

(Question 1) Relation to the references.

Thank for you the references! Despite some high-level similarities with our work, the specific models and results of those works are significantly different from ours. In particular:

• [Scheid et al 2024, Learning to Mitigte Externalities] consider a contract design setting where both the agent and the principal don't know their utility functions and use no-regret algorithms to learn. Unlike them, our principal knows the utility function and does not employ learning algorithms. Another difference is that their principal commits to the contract at each period and the agent's learning algorithm takes into account the committed contract, while our principal does not commit and the agent's algorithm is agnostic to the principal's current strategy. Although commitment is natural in the contract design setting, it is less natural in information design. We are more interested in the information design setting and drop the commitment assumption.

• In [Ben-Porat et al 2024, Principal-Agent Reward Shaping in MDPs], the principal designs the reward function of an MDP played by the agent. Crucially, the agent is assumed to be able to best respond, i.e., computing the best MDP policy, which is different from our learning agent model.

• [Mansour et al, 2015, Bayesian Incentive-Compatible Bandit Exploration] study a problem where the principal, not knowing the mean rewards of different arms/actions, signals a sequence of receivers in an incentive-compatible way (namely, the receivers are willing to follow the recommendations) to learn about the arms. We consider a principal who knows the environment trying to signal the receiver in a possibly non-IC way to maximize the principal itself's utility. Their reduction is to show that any general (possibly non-IC) multi-armed bandit algorithm can be converted to an IC algorithm in their problem, while our reduction is to reduce the problem with a learning agent to the problem with an approximately-best-responding agent.

Given the above differences, we don't see a close connection between our work and theirs. We have added [Scheid et al 2024] to our references because their work also considers a learning agent, similar to ours, despite significant differences in the underlying models.

(Question 2) It is mentioned that « the sender commits to a signaling scheme » and then follows - it is always the case in Bayesian Persuasion. However, if we consider the setup of a game, I do not see why the principal would not deviate from it if this was in their interest. I think that this part of the model should be discussed with regards to real scenarios or motivations.

Thank you for pointing this out! While standard Bayesian persuasion requires the principal to commit to a signaling scheme, our model with a learning agent no longer assumes this. We allow the principal to choose the signaling scheme $\pi^t$ after the receiver chooses the signal-to-action mapping $\rho^t: S \to \Delta(A)$. Our original model had "(1) the sender chooses a signaling scheme $\pi^t$" and "(2) the receiver chooses a strategy $\rho^t$ simultaneously (based only on history, but not the sender's current round strategy $\pi^t$)". This might cause the misunderstanding that the sender commits first. So, we decided to switch (1) and (2) in the presentation of our model. In the newly uploaded PDF, you will see that (1) becomes "the receiver chooses $\rho^t$ according to a learning algorithm", and (2) becomes "the sender chooses a signaling scheme $\pi^t$". Being equivalent to the original model, this new description of our model has a clearer real-world motivation: in practice, people hardly commit to signaling schemes; receivers learn how to interpret the sender's language based on what the sender said in the past; knowing how the receiver interprets the language, the sender will then decide what to say to potentially take advantage of the receiver. Under this motivation, our conclusion that no-swap-regret learning agent can prevent the principal from doing better than $U^*$ is particularly interesting, because it means that, even if the principal can strategize after the agent, the principal cannot do better than the case where the principal commits first.

We thank the reviewer for the appreciation! Regarding the differences between normal-form games and generalized principal-agent problems, two major differences are the presence of signals in the generalized problem, and a general decision space $\mathcal X$ for the principal (compared to the probability simplex over pure actions in normal-form games). The presence of signals requires us to consider contextual no-(swap-)regret algorithms, unlike the normal no-(swap-)regret algorithms in normal-form games in [Deng et al, Strategizing against no-regret learners, NeurIPS'19]. In particular, contextual no-swap-regret learning requires new analysis in the reduction from no-swap-regret learning to approximate best response (Theorem 3.4). The general decision space $\mathcal X$ causes technical difficulty in the sensitivity analysis for approximately best responding agent (proofs of Theorem 4.1 and 4.2).

(Question 1): The principal knows the agent's payoffs?

Yes, we will point this out explicitly.

(Question 2): What do you see any implications between your work and Gan et al (2023), Sequential principal-agent problems with communication: efficient computation and learning.

Thanks for the reference! Although Gan et al (2023)'s sequential principal-agent problems indeed include a large class of principal-agent problems as we do, their learning problem is significantly different from ours. In their work, neither the principal nor the agent knows the environment, and they design a centralized algorithm (that controls both the principal and the agent) to explore the environment so as to find an optimal strategy for the principal. In our problem, only the agent is learning, while the principal knows the environment and aims to exploit the non-best-responding learning agent. Given the different setups, we don't see a direct connection between our and their works.

(Question 1) Can the authors quantify what "significantly larger" means in Theorem 3.5? ... Furthermore, why does the lemma hold only in Bayesian persuasion setting.

In the proof of Theorem 3.5 (Appendix E.4), we have quantitative results: the optimal sender utility in the classic Bayesian persuasion model is $U^* = 0$, while against a $\gamma$-mean-based learning agent, the principal can obtain utility $1/2 - O(\sqrt \gamma)$, averaged over all $T$ rounds. Since $\gamma$ typically converges to $0$ as $T\to\infty$, the principal's average utility approaches $1/2$, which is larger than $U^* = 0$ by a constant.

The result that the principal can exploit a mean-based learning agent not only holds in the Bayesian persuasion setting. Previous works (Deng et al, Strategizing against no-regret learner, NeurIPS'19) showed that, against a mean-based learner, the principal can do significantly better than the Stackeberg value $U^*$ in Stackelberg games. However, it was unclear whether this phenomenon also holds in the Bayesian persuasion setting, where the principal has private information and can send signals. We show that the same phenomenon indeed holds in Bayesian persuasion as well.

(Question 2) How can the fixed policy $\pi_t$ in the statement of Theorem 3.1 be computed.

The construction of the fixed policy $\pi_t$ in Theorem 3.1 is implicitly given in the proof of Theorem 3.1 and the proofs of Theorem 4.1 and 4.2. In the proof of Theorem 3.1, we let $\delta=\frac{CReg(T)}{T}$ be the regret of the agent, and let $\pi_t$ be a strategy $\pi^{\varepsilon, \delta}$ that is robust against $\delta$-best-responding agent: namely, no matter what $\delta$-best-responding strategy is used by the agent, the principal can always guarantee an $\varepsilon$-optimal utility. Then, the construction of $\pi^{\varepsilon, \delta}$ is given in the analysis for $\underline{OBJ}^R(\delta)$ in Theorem 4.1 (for unconstrainted generalized principal-agent problems) and Theorem 4.2 (constrained). The specific construction is involved, so we didn't write it explicitly. At a high level, it is a perturbation idea: First, compute the optimal principal strategy $\pi^*$ assuming a best-responding agent (which can be done by a linear program as shown by previous work), which is not robust because the agent might be indifferent between two actions when $\pi^*$ sends a signal; Then, perturb $\pi^*$ slightly to break indifference, so that the agent strictly prefers one action than another by $\delta$ no matter what signal is sent. Such perturbation will decrease the principal's utility by $O(\sqrt \delta)$, hence $\pi^{\varepsilon, \delta}$ achieves $U^* - O(\sqrt \delta) - \varepsilon$ and $\pi_t$ archives $U^* - O(\sqrt \frac{CReg(T)}{T}) - \varepsilon$.

(Weakness 1 and 2) The limitations regarding $p_0$ and inducibility gap.

We note that the condition on $p_0$ and the inducibility gap are standard regularity conditions in the literature. The condition on $p_0$ is necessary in robust Bayesian persuasion (as shown by Zu et al (2022), Learning to Persuade on the Fly: Robustness Against Ignorance), and the inducibility gap is well-known to be necessary in robust Stackelberg games (like Gan et al (2023), Robust Stackelberg Equilibria). Without these two conditions, the $\delta$-approximately-best-responding strategy of the agent may significantly reduce the principal's utility -- the principal's utility is no longer lower bounded by $U^* - O(\delta)$.

(Weakness 3) The approach to proving Theorem 4.1 (first point) appears somewhat incremental with respect to Gan et al (2023). ... This is not necessarily a drawback, but it raises questions about the technical novelty.

This part of our proof is indeed inspired by Gan et al (2023). But our other results use different techniques. For example, in the second point of Theorem 4.1 and Theorem 4.2, we consider randomized $\delta$-best-responding strategies for the agent, which to our knowledge have not been studied by previous works. To our surprise, randomized strategies turn out to be qualitatively different from deterministic ones: randomized ones have $\underline{OBJ}^R(\delta) = U^* - O(\sqrt \delta)$ while deterministic ones have $\underline{OBJ}^D(\delta) = U^* - O(\delta)$. The proof of this result is inspired by Markov's inequality (see Lemma F.3 and Appendix F.6). We also show that this distinction between randomized and deterministic strategies is unavoidable (Example 4.1), whose proof requires analyzing a maxmin problem where the minimization step is a fractional knapsack problem. The results and techniques regarding randomized agent strategies are new as far as we know.

(Weakness 4) The authors show that their model can be generalized to contract design settings. However, they should more clearly specify that they consider a model without costs, particularly in comparison with prior works.

Thank you for noticing this issue! We have modified our Appendix D.2 to add costs for the agent's actions, which makes it consistent with prior works. All our results remain unchanged. You can see the newly uploaded PDF for details.

(Weakness 1) ... While the paper is framed under the general principal-agent problem, it only discusses the Bayesian persuasion problem as its special case.

While we focused on Bayesian persuasion as an example, our paper also discussed two other special cases of the general principal-agent problem -- Stackelberg games and contract design. We provided a summary in Section 5 and a full discussion in Appendix D due to page limits.

(Weakness 2) The major drawback of this paper is that the problem itself is not well-motivated. A no-regret learning agent would assume a stationary environment, but the principal here can adaptively adjust its strategy.

We note that a no-regret learning agent does not assume a stationary environment. A no-regret algorithm such as Multiplicative Weight ensures that the agent's actual cumulative utility is at most $O(\sqrt{T})$ worse than the cumulative utility of the best fixed action in hindsight (see, e.g., here), even when the environment is non-stationary. Of course, when the environment is non-stationary, the optimal strategy for the agent in hindsight should be a sequence of possibly different actions for all time steps. But it is known that competing against the optimal action sequence is impossible (Example 1.1 of this), so the standard definition of (external) regret for a non-stationary environment considers a fixed action.

Indeed, although is standard in the literature, competing against the best fixed action in hindsight might not seem to be the right choice in a non-stationary environment. But we want to emphasize the contrast between our results for no-swap-regret learning agents and no-regret learning agents, both of which do not compete against the optimal action sequence. We show that when the agent does no-swap-regret learning, the principal cannot exploit the agent even if the principal adjusts its strategy adaptively, while the principal can when the agent only does no-regret learning. We think this is an interesting conceptual contribution of our work.

(Weakness 3) The technical depth of this paper is relatively shallow.

The technique for our Result 1 (the principal can obtain $U^*-O(\sqrt \frac{Reg(T)}{T})$ against a no-regret agent) and Result 2 (the principal cannot obtain more than $U^* + O(\frac{SReg(T)}{T})$ against a no-swap-regret agent) is a reduction to generalized principal-agent problem with approximate best response, combined with a sensitivity analysis for the problem with approximate best response. The clean reduction and the generality of the analysis (which applies to all principal-agent problems) are part of our main technical contributions.

The technique for Result 3 (There exists a no-swap-regret or no-regret learning algorithm under which the principal cannot do better than $U^* - \Omega(\sqrt \frac{SReg(T)}{T})$) is substantial in our opinion. One might initially expect that the principal cannot do better than the linear term $U^* - \Omega(\frac{SReg(T)}{T})$, but we show that the correct answer is the squared-root term $U^* - \Omega(\sqrt \frac{SReg(T)}{T})$. Proving this result requires solving a maxmin problem (Equation (5)): maximize over the principal's strategy, minimize over the agent's $\delta$-best-responding strategy. This maxmin problem is significantly more challenging than the maxmax problem (Equation (6)), requiring solving a fractional knapsack problem in the minimization part, together with a non-trivial analysis of the principal's utility under the solution of the fractional knapsack problem. (Details are in our Proof of Example 4.1, in Appendix F.2.)

(Question) Why is it necessary to drop the private information in the generalized principal-agent problem from Myerson (1982) and Gan et al (2024)?

When the agent has private information, a no-swap-regret learning agent can be exploited by the principal (Lines 57-60 in Introduction). One of the motivations of our work is to identify the condition under which no-swap-regret learning can prevent exploitation by the principal. And we've found that no-private-information is a key condition. Our paper hence focuses only on generalized principal-agent problems where the agent does not have private information.