Generalized Principal-Agent Problem with a Learning Agent

## Abstract

Abstract Classic principal-agent problems such as Stackelberg games, contract design, and Bayesian persuasion, often assume that the agent is able to best respond to the principal’s committed strategy.
We study repeated generalized principal-agent problems under the assumption that the principal does not have commitment power and the agent uses algorithms to learn to respond to the principal. We reduce this problem to a one-shot generalized principal-agent problem where the agent approximately best responds. Using this reduction, we show that: (1) If the agent uses contextual no-regret learning algorithms with regret Reg ⁢ ( T ) Reg 𝑇 \mathrm{Reg}(T) roman_Reg ( italic_T ) , then the principal can guarantee utility at least U ∗ − Θ ⁢ ( Reg ⁢ ( T ) T ) superscript 𝑈 Θ Reg 𝑇 𝑇 U^{*}-\Theta\big{(}\sqrt{\tfrac{\mathrm{Reg}(T)}{T}}\big{)} italic_U start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT - roman_Θ ( square-root start_ARG divide start_ARG roman_Reg ( italic_T ) end_ARG start_ARG italic_T end_ARG end_ARG ) , where U ∗ superscript 𝑈 U^{*} italic_U start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is the principal’s optimal utility in the classic model with a best-responding agent.
(2) If the agent uses contextual no-swap-regret learning algorithms with swap-regret SReg ⁢ ( T ) SReg 𝑇 \mathrm{SReg}(T) roman_SReg ( italic_T ) , then the principal cannot obtain utility more than U ∗ + O ⁢ ( SReg ⁢ ( T ) T ) superscript 𝑈 𝑂 SReg T 𝑇 U^{*}+O(\frac{\mathrm{SReg(T)}}{T}) italic_U start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT + italic_O ( divide start_ARG roman_SReg ( roman_T ) end_ARG start_ARG italic_T end_ARG ) .
But (3) if the agent uses mean-based learning algorithms (which can be no-regret but not no-swap-regret), then the principal can sometimes do significantly better than U ∗ superscript 𝑈 U^{*} italic_U start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT .
These results not only refine previous results in Stackelberg games and contract design, but also lead to new results for Bayesian persuasion with a learning agent and all generalized principal-agent problems where the agent does not have private information.

## 1 Introduction

Classic economic models of principal-agent interactions, including auction design, contract design, and Bayesian persuasion, often assume that the agent is able to best respond to the strategy committed by the principal.
For example, in Bayesian persuasion, the agent (receiver) needs to compute the posterior belief about the state of the world after receiving some information from the principal (sender) and take an optimal action based on the posterior belief; this requires the receiver accurately knowing the prior of the state as well as the signaling scheme used by the sender.
In contract design, where a principal specifies an outcome-dependent payment scheme to incentivize the agent to take certain actions, the agent has to know the action-dependent outcome distribution in order to best respond to the contract.
Requiring strong rationality assumptions, the best-responding behavior is often observed to be violated in practice (Camerer, ; Benjamin, ).

In this work, using Bayesian persuasion as the main example, we study general principal-agent problems under an alternative behavioral model for the agent: *learning*. The use of learning as a behavioral model dates back to early economic literature on learning in games (Brown, ; Fudenberg and Levine, ) and has been actively studied by computer scientists in recent years (Nekipelov et al., ; Braverman et al., ; Deng et al., ; Mansour et al., ; Cai et al., ; Rubinstein and Zhao, ; Guruganesh et al., ).
A learning agent no longer has perfect knowledge of the parameter of the game or the principal’s strategy. Instead of best responding, which is no longer possible or well-defined, the agent chooses his action based on past interactions with the principal.
We focus on *no-regret* learning, which requires the agent to not suffer a large average regret at the end of repeated interactions with the principal, for not taking the optimal action at hindsight. This is a mild requirement satisfied by many natural learning algorithms (e.g., $\varepsilon$-greedy, MWU, UCB, EXP-3) and can reasonably serve as a possible behavioral assumption for real-world agents.

With a learning agent, can the principal achieve a better outcome than that in the classic model with a best-responding agent?
Previous works on playing against learning agents (Deng et al., ; Guruganesh et al., ) showed that, in Stackelberg games and contract design, the leader/principal can obtain utility $U^{*}-o(1)$ against a no-regret learning follower/agent, where $U^{*}$ is the Stackelberg value, defined to be the principal’s optimal utility in the classic model with a best-responding agent. On the other hand, if the agent does a stronger version of no-regret learning, called no-swap-regret learning (Hart and Mas-Colell, ; Blum and Mansour, ), then the principal cannot obtain utility more than the Stackelberg value $U^{*}+o(1)$.
Interestingly, the conclusion that no-swap-regret learning can cap the principal’s utility at $U^{*}+o(1)$ does not hold when the agent has private information, such as in auctions (Braverman et al., ) and Bayesian Stackelberg games (Mansour et al., ): the principal can sometimes exploit a no-swap-regret learning agent with private information to do much better than $U^{*}$ in those games.

Three natural questions then arise: (1) What is the largest class of principal-agent problems under which the agent’s no-swap-regret learning can cap the principal’s utility at the Stackelberg value $U^{*}+o(1)$? (2) In cases where the principal’s optimal utility against a learning agent is bounded by $[U^{*}-o(1),U^{*}+o(1)]$, what is the exact magnitude of the $o(1)$ terms? (3) Instead of analyzing games like Stackelberg games and contract design separately, can we analyze all principal-agent problems with learning agents in a unified way?

#### Our contributions.

Our work defines a general model of principal-agent problems with a learning agent, answering all questions (1) - (3).
For (1), we show that the principal’s utility is bounded around the Stackelberg value $U^{*}$ in all generalized principal-agent problems where the agent does not have private information but the principal can be privately informed. In particular, this includes complete-information games like Stackelberg games and contract design, as well as Bayesian persuasion where the sender/principal privately observes the state of the world.

For (2) and (3), we provide a unified analytical framework to derive tight bounds on the principal’s achievable utility against a no-regret or no-swap-regret learning agent in all generalized principal-agent problems where the agent does not have private information. Specifically, we explicitly characterize the $o(1)$ difference between the principal’s utility and $U^{*}$ in terms of the agent’s regret.

Result 1 (from Theorems 3.1, 4.2, 4.3).
*
Against a no-regret learning agent with regret $\mathrm{Reg}(T)$ in $T$ periods, the principal can obtain an average utility of at least $U^{*}-O\big{(}\sqrt{\tfrac{\mathrm{Reg}(T)}{T}}\big{)}$. The principal can do this using a fixed strategy in all $T$ periods and only knowing the regret bound of the agent but not the exact learning algorithm.
*

Result 2 (from Theorems 3.4, 4.2, 4.3).
*
Against a no-swap-regret learning agent with swap-regret $\mathrm{SReg}(T)$ in $T$ periods, the principal cannot obtain average utility larger than $U^{*}+O\big{(}\tfrac{\mathrm{SReg}(T)}{T}\big{)}$. This holds even if the principal knows the learning algorithm of the agent and uses time-varying strategies.
*

Interestingly, the squared root bound $U^{*}-O\big{(}\sqrt{\tfrac{\mathrm{Reg}(T)}{T}}\big{)}$ in Result 1 and the linear bound $U^{*}+O\big{(}\tfrac{\mathrm{SReg}(T)}{T}\big{)}$ in Result 2 are not symmetric. We show that such an asymmetry is intrinsic: there exist cases where the principal cannot achieve better than $U^{*}-O\big{(}\sqrt{\tfrac{\mathrm{Reg}(T)}{T}}\big{)}$ utility.

Result 3 (from Theorem 3.3 and Example 4.1). *
There is a Bayesian persuasion instance where, for any strategy of the principal, there is a no-swap-regret learning algorithm for the agent under which the principal’s utility is at most $U^{*}-\Omega\big{(}\sqrt{\tfrac{\mathrm{SReg}(T)}{T}}\big{)}$. The same holds for no-regret algorithms.
*

Results 1, 2, 3 together characterize the range of utility achievable by the principal against a no-swap-regret learning agent: $[U^{*}-\Theta(\sqrt{\frac{\mathrm{SReg}(T)}{T}}),U^{*}+O(\frac{\mathrm{SReg}(T
)}{T})]$.
As $T\to\infty$, the range converges to $U^{*}$, which means that the agent’s no-swap-regret learning behavior is essentially equivalent to best responding behavior.
This justifies the classical economic notion that the equilibria of games are results of repeated interactions between learning players.

However, for no-regret but not necessarily no-swap-regret algorithms, the upper bound result $U^{*}+O(\frac{\mathrm{Reg}(T)}{T})$ does not hold. The repeated interaction between a principal and a no-regret learning agent does not always lead to the Stackelberg equilibrium outcome $U^{*}$:

Result 4 (Theorem 3.5).
*There exists a Bayesian persuasion instance where, against a no-regret but not no-swap-regret learning agent (in particular, mean-based learning agent), the principal can do significantly better than the Stackelberg value $U^{*}$.*

In summary, our Results 1, 2, 3 exactly characterize the principal’s optimal utility in principal-agent problems with a no-swap-regret agent, which not only refines previous works on playing against learning agents in specific games (Stackelberg games and contract design) but also generalizes to all principal-agent problems where the agent does not have private information. In particular, when applied to Bayesian persuasion, our results imply that the sender cannot exploit a no-swap-regret learning receiver even if the sender possesses informational advantage over the receiver.

#### Some intuitions.

As we alluded above, the main intuition behind our first three results is: the agent’s learning behavior is closely related to *approximately best response*. A no-regret learning agent makes sub-optimal decisions with the sub-optimality measured by the regret. When the sub-optimality/regret is small, the principal-agent problem with a no-regret agent (or approximately best responding agent) converges to the problem with an exactly best responding agent. This explains why the principal against a no-regret learning agent can obtain a payoff that is close to the optimal payoff $U^{*}$ against a best responding agent.

However, there are two subtleties behind the above intuition.

First, the intuition that a no-regret learning agent is approximately best responding is true only when the principal uses a *fixed* strategy throughout the interactions with the agent.
If the principal uses *time-varying* strategies, then a no-regret agent is not necessarily approximately best responding to the “average” strategy of the principal across $T$ periods, while a no-swap-regret agent is still approximately best responding. This is because a no-swap-regret algorithm ensures that, whenever the algorithm recommends some action $a^{t}$ at a period $t$, it is almost optimal for the agent to take the recommended action $a^{t}$.
But a no-regret algorithm only ensures the agent to not regret when comparing to taking any *fixed* action in all $T$ periods. The agent could have done better by deviating to different actions given different recommendations from the algorithm. This means that a no-regret agent is not approximately best responding when the principal’s strategy changes over time, which explains why the principal can exploit a no-regret agent sometimes (our Result 4).

Second, what is the reason for the asymmetry between the worst-case utility $U^{*}-\Theta(\sqrt{\frac{\mathrm{SReg}(T)}{T}})$ and the best-case utility $U^{*}+O(\frac{\mathrm{SReg}(T)}{T})$ that the principal can obtain against a no-swap-regret learning agent? Roughly speaking, a no-swap-regret learning agent is approximately best responding to the principal’s average strategy over all $T$ periods, with the degree of approximate best response measured by the average regret $\frac{\mathrm{SReg}(T)}{T}=\delta$. However, because no-swap-regret learning algorithms are randomized(^1^11It is well known that deterministic algorithms cannot satsify the no-regret property (see, e.g., Roughgarden ()).), they correspond to randomized approximately best responding strategies of the agent that are worse than the best responding strategy by a margin of $\delta$ *in expectation*, which means that the agent might take $\sqrt{\delta}$-sub-optimal actions with probability $\sqrt{\delta}$. That can cause a loss of $1$ to the principal’s utility with probability $\sqrt{\delta}$. So, the principal’s expected utility can be decreased to $U^{*}-\sqrt{\delta}=U^{*}-\sqrt{\frac{\mathrm{SReg}(T)}{T}}$ in the worst case. On the other hand, when considering the principal’s best-case utility, we care about the $\delta$-approximately-best-responding strategy of the agent that maximizes the principal’s utility. That strategy turns out to be equivalent to a deterministic strategy that gives the principal a utility of at most $U^{*}+O(\delta)=U^{*}+O(\frac{\mathrm{SReg}(T)}{T})$. This explains the asymmetry between the worst-case and best-case bounds.

#### Structure of the paper.

We define our model of generalized principal-agent problems with a learning agent in Section 2.
Since Bayesian persuasion is the main motivation of our work, we also present the specific model of persuasion with a learning agent in Section 2.3.
We develop our main results in Sections 3 and 4, by first reducing the generalized principal-agent problem with a learning agent to the problem with approximate best response, then characterizing the problem with approximate best response.
Section 6 offers additional discussions.

### 1.1 Related Works

Learning agents have been studied in principal-agent problems like auctions (Braverman et al., ; Cai et al., ; Rubinstein and Zhao, ; Kumar et al., ), bimatrix Stackelberg games (Deng et al., ; Mansour et al., ; Arunachaleswaran et al., ), contract design (Guruganesh et al., ), and Bayesian persuasion (Jain and Perchet, ).
These problems belong to the class of *generalized principal-agent problems* (Myerson, ; Gan et al., ). We thus propose a general framework of generalized principal-agent problem with a learning agent, which encompasses several previous models, refines previous results, and provides new results.

Camara et al. () also propose a general framework of principal-agent problems with learning players, but has two key differences with ours: (1) They drop the common prior assumption while we still keep it. This assumption allows us to compare the principal’s utility in the learning model with the classic model with common prior. (2) Their principal has commitment power, which is reasonable in, e.g., auction design, but less realistic in information design where the principal’s strategy is a signaling scheme. Our principal does not commit.

Deng et al. () show that the follower’s no-swap-regret learning can cap the leader’s utility at $U^{*}+o(1)$ in Stackelberg games. We find that this conclusion holds for all generalized principal-agent problems where the agent does not have private information.
This conclusion does not hold when the agent is privately informed, as shown by
Mansour et al. () in Bayesian Stackelberg games.
We view our work as characterizing the largest class of games under which this conclusion holds.

The literature on information design (Bayesian persuasion) has investigated various relaxations of the strong rationality assumptions in the classic models.
For the sender, known prior (Dworczak and Pavan, ; Camara et al., ; Kosterina, ; Zu et al., ; Ziegler, ; Wu et al., ) and known utility (Babichenko et al., ; Castiglioni et al., ; Feng et al., ) are relaxed.
For the receiver, the receiver may make mistakes in Bayesian updates (de Clippel and Zhang, ), be risk-conscious (Anunrojwong et al., ), do quantal response (Feng et al., ) or approximate best response (Yang and Zhang, ).
Independently and concurrently of us, Jain and Perchet () also study Bayesian persuasion with a learning agent. Their work has a few differences with us: First, their model is a general Bayesian persuasion model with imperfect and non-stationary dynamics for the state of the world. Our model generalizes Bayesian persuasion in another direction (namely, generalized principal-agent problems), while still assuming a perfect and stationary environment. Second, their results are qualitatively similar to our Result 1 and Result 4, while our results are more quantitative and precise. Third, we additionally show that no-swap-regret learning can cap the sender’s utility (Result 2).

As our problem reduces to generalized principal-agent problems with approximate best response, our work is also related to recent works on approximately-best-responding agents in Stackelberg games (Gan et al., ) and Bayesian persuasion (Yang and Zhang, ).
We focus on the range of payoff that can be obtained by a computationally-unbounded principal, ignoring the computational aspect considered by Gan et al. (); Yang and Zhang ().
Besides the “maxmin/robust” objective, we also study the “maxmax” objective where the agent approximately best responds *in favor of* the principal, which is usually not studied in the literature.

## 2 Generalized Principal-Agent Problem with a Learning Agent

This section defines our model, *generalized principal-agent problem with a learning agent*. This model includes Stackelberg games, contract design, and Bayesian persuasion with learning agents.

### 2.1 Generalized Principal-Agent Problem

*Generalized principal-agent problem*, proposed by Myerson (); Gan et al. (), is a general model that includes auction design, contract design, Stackelberg games, and Bayesian persuasion.
While Myerson () and Gan et al. () allow the agent to have private information, our model assumes an agent with no private information.
There are two players in a generalized principal-agent problem: a principal and an agent. The principal has a convex, compact decision space $\mathcal{X}$ and the agent has a finite action set $A$.
The principal and the agent have utility functions $u,v:\mathcal{X}\times A\to{\mathbb{R}}$.
We assume that $u(x,a)$, $v(x,a)$ are linear in $x\in\mathcal{X}$, which is satisfied by all the examples of generalized principal-agent problems we will consider (Bayesian persuasion, Stackelberg games, contract design).
There is a signal/message set $S$. Signals are usually interpreted as recommendations of actions for the agent, where $S=A$, but we allow any signal set of size $|S|\geq|A|$.
A strategy of the principal is a distribution $\pi\in\Delta(\mathcal{X}\times S)$ over pairs of decision and signal. When the utility functions $u,v$ are linear, it is without loss of generality to assume that the principal does not randomize over multiple decisions for one signal (Gan et al., ), namely, the principal chooses a distribution over signals and a unique decision $x_{s}$ associated with each signal $s\in S$.
So, we can write a principal strategy as $\pi=\{(\pi_{s},x_{s})\}_{s\in S}$ where $\pi_{s}\geq 0$ is the probability of signal $s\in S$, $\sum_{s\in S}\pi_{s}=1$, and $x_{s}\in\mathcal{X}$.
There are two variants of generalized principal-agent problems:

- •
*Unconstrained* (Myerson, ): there is no restriction on the principal’s strategy $\pi$.
- •
*Constrained* (Gan et al., ): the principal’s strategy $\pi$ has to satisfy constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$ where $\mathcal{C}\subseteq\mathcal{X}$ is some convex set.

Unconstrained generalized principal-agent problems include contract design and Stackelberg games. Constrained generalized principal-agent problems include Bayesian persuasion (see Section 2.3).

In a one-shot generalized principal-agent problem where the principal has commitment power, the principal first commits to a strategy $\pi=\{(\pi_{s},x_{s})\}_{s\in S}$, then nature draws a signal $s\in S$ according to the distribution $\{\pi_{s}\}_{s\in S}$ and sends $s$ to the agent (note: due to the commitment assumption, this is equivalent to revealing the pair $(s,x_{s})$ to the agent), then the agent takes an action $a_{s}\in\operatorname*{arg\,max}_{a\in A}v(x_{s},a)$ that maximizes its utility (breaking ties in favor of the principal), and the principal obtains utility $u(x_{s},a_{s})$. The principal aims to maximize its expected utility $\mathbb{E}_{s\sim\pi}[u(x_{s},a_{s})]$ by choosing the strategy $\pi$. Denote the maximal expected utility that the principal can obtain by $U^{*}$:

$$ $U^{*}=\max_{\pi}\sum_{s\in S}\pi_{s}\max_{a_{s}\in\operatorname*{arg\,max}_{a \in A}v(x_{s},a)}u(x_{s},a_{s}).$ (1) $$

$U^{*}$ is called the Stackelberg value in the literature.

### 2.2 Learning Agent

Now we define the model of generalized principal-agent problem with a learning agent.
The game is repeated for $T$ rounds.
Unlike the above static model, the principal now does not commit to its strategy $\pi^{t}$ every round.
The agent does not know the strategy $\pi^{t}$ or the decision $x^{t}$ of the principal at each round. Instead, the agent uses some adaptive algorithm to learn from history which action to take in response to each possible signal. We allow the agent’s strategy to be randomized.
{mdframed}[frametitle=Generalized Principal-Agent Problem with a Learning Agent]
In each round $t=1,\ldots,T$:

- (1)
Using some algorithm that learns from history (including signals, actions, and utility feedback in the past, described in details later), the agent chooses a strategy $\rho^{t}:S\to\Delta(A)$ that maps each possible signal $s\in S$ to a distribution over actions $\rho^{t}(s)\in\Delta(A)$.
- (2)
The principal chooses a strategy $\pi^{t}=\{(\pi_{s}^{t},x_{s}^{t})\}_{s\in S}$, which is a distribution over signals $S$ and a decision $x_{s}^{t}\in\mathcal{X}$ associated with each signal.
- (3)
Nature draws signal $s^{t}\sim\pi^{t}$ and reveals it. The principal makes decision $x^{t}=x_{s^{t}}^{t}$. The agent draws action $a^{t}\sim\rho^{t}(s^{t})$.
- (4)
The principal and the agent obtain utility $u^{t}=u(x^{t},a^{t})$ and $v^{t}=v(x^{t},a^{t})$. The agent observes some feedback (e.g., $v^{t}(x^{t},a^{t})$ or $x^{t}$).

Compared with the static model in Section 2.1 where the principal moves before the agent, we flip the order of decision making of the principal and the agent in the learning model: the agent moves first by choosing $\rho^{t}$, then the principal chooses $\pi^{t}$.
This gives the principal an opportunity to “exploit” the agent by choosing a $\pi^{t}$ that best responds to $\rho^{t}$, hence potentially do much better than the Stackelberg value $U^{*}$ where the principal moves first. However, one of our main results (Result 2 in the Introduction) will show that the principal cannot do much better than $U^{*}$ if the agent uses a particular type of learning algorithm, called contextual no-swap-regret algorithm, which we define below.

#### Agent’s learning problem.

The agent’s learning problem can be regarded as a *contextual multi-armed bandit problem* (Tyler Lu et al., ) where $A$ is the set of arms, and a signal $s^{t}\in S$ serves as a context that affects the utility of each arm $a\in A$. The agent picks an arm to pull based on the current context $s^{t}$ and the historical information about each arm under different contexts, adjusting its strategy over time based on the feedback collected after each round.

What feedback can the agent observe after each round? One may assume that the agent sees the principal’s decision $x^{t}$ after each round (this is call *full-information* feedback in the multi-armed bandit literature), or the utility $v^{t}=v(x^{t},a^{t})$ obtained in that round (this is called *bandit feedback*) but not the $x^{t}$, or some unbiased estimate of $v(x^{t},a^{t})$. We do not make specific assumptions on the feedback. All we need is that the feedback is sufficient for the agent to achieve contextual no-regret or contextual no-swap-regret, which are defined below:

###### Definition 2.1 .

The agent’s learning algorithm is said to satisfy:

- •
*contextual no-regret* if: there is a function $\mathrm{CReg}(T)=o(T)$(^2^22A function $f(T)=o(T)$ means $\frac{f(T)}{T}\to 0$ as $T\to+\infty$. So, the average regret $\frac{\mathrm{CReg}(T)}{T}\to 0$.) such that, for any strategy of the principal, for any deviation function $d:S\to A$, the regret of the agent not deviating according to $d$ is at most $\mathrm{CReg}(T)$:
$\mathbb{E}\Big{[}\sum_{t=1}^{T}\big{(}v(x^{t},d(s^{t}))-v(x^{t},a^{t})\big{)}
\Big{]}\leq\mathrm{CReg}(T).$
- •
*contextual no-swap-regret* if: there is a function $\mathrm{CSReg}(T)=o(T)$ such that, for any strategy of the principal, for any deviation function $d:S\times A\to A$, the regret of the receiver not deviating according to $d$ is at most $\mathrm{CSReg}(T)$:
$\mathbb{E}\Big{[}\sum_{t=1}^{T}\big{(}v(x^{t},d(s^{t},a^{t}))-v(x^{t},a^{t})
\big{)}\Big{]}\leq\mathrm{CSReg}(T).$

We call $\mathrm{CReg}(T)$ and $\mathrm{CSReg}(T)$ the *contextual regret* and *contextual swap-regret* of the agent.

Contextual no-regret is implied by contextual no-swap-regret because the latter has a larger set of deviation functions.
Contextual no-(swap-)regret algorithms are known to exist under bandit feedback. In fact, they can be easily constructed by running an ordinary no-(swap-)regret algorithm for each context independently.
Formally:

###### Proposition 2.1 .

There exist learning algorithms with contextual regret $\mathrm{CReg}(T)=O(\sqrt{|A||S|T})$ and contextual swap-regret $\mathrm{CSReg}(T)=O(|A|\sqrt{|S|T})$.
They can be constructed by running an ordinary no-(swap-)regret multi-armed bandit algorithm for each context independently.

See Appendix A for a proof of this Proposition.

###### Definition 2.1 .

###### Proposition 2.1 .

### 2.3 Special Case: Bayesian Persuasion with a Learning Agent

We show that *Bayesian persuasion* (Kamenica and Gentzkow, ) is a special case of constrained generalized principal-agent problems. We will also show that Bayesian persuasion is in fact equivalent to *cheap talk* (Crawford and Sobel, ) under our learning agent model.

#### Bayesian persuasion as a generalized principal-agent problem.

There are two players in Bayesian persuasion: a sender (principal) and a receiver (agent).
There are a finite set $\Omega$ of states of the world, a signal set $S$, an action set $A$, a prior distribution $\mu_{0}\in\Delta(\Omega)$ over the states, and utility functions $u,v:\Omega\times A\to{\mathbb{R}}$ for the sender and the receiver. When the state is $\omega\in\Omega$ and the receiver takes action $a\in A$, the sender and the receiver obtain utility $u(\omega,a)$, $v(\omega,a)$, respectively.
Both players know $\mu_{0}$, but only the sender has access to the realized state $\omega\sim\mu_{0}$.
The sender commits to some signaling scheme $\pi:\Omega\to\Delta(S)$, mapping any state to a probability distribution over signals, to partially reveal information about the state $w$ to the receiver. In the classic model, after receiving a signal $s\in S$, the receiver will form the posterior belief $\mu_{s}\in\Delta(\Omega)$ about the state: $\mu_{s}(\omega)=\frac{\mu_{0}(\omega)\pi(s|\omega)}{\pi_{s}}$, where $\pi_{s}=\sum_{\omega\in\Omega}\mu_{0}(\omega)\pi(s|\omega)$ is the total probability that signal $s$ is sent,
and take an optimal action with respect to $\mu_{s}$, i.e., $a_{s}\in\operatorname*{arg\,max}_{a\in A}\sum_{\omega\in\Omega}\mu_{s}(\omega)
v(\omega,a)$. The sender aims to find a signaling scheme to maximizde its expected utility $\mathbb{E}[u(\omega,a_{s})]$.

It is well-known (Kamenica and Gentzkow, ) that a signaling scheme $\pi:\Omega\to\Delta(S)$ decomposes the prior $\mu_{0}$ into a distribution over posteriors whose average is equal to the prior $\mu_{0}$:

$$ $\displaystyle\sum_{s\in S}\pi_{s}\mu_{s}=\mu_{0}\in\{\mu_{0}\}=:\mathcal{C}, \quad\sum_{s\in S}\pi_{s}=1.$ (2) $$

Equation (2) is called the *Bayes plausibility* condition. Conversely, any distribution over posteriors $\{(p_{s},\mu_{s})\}_{s\in S}$ satisfying Bayes plausibility $\sum_{s\in S}p_{s}\mu_{s}=\mu_{0}$ can be converted into a signaling scheme that sends signal $s$ with probability $p_{s}$.
Thus, we can use a distribution over posteriors $\{(\pi_{s},\mu_{s})\}_{s\in S}$ satisfying Bayes plausibility to represent a signaling scheme. Then, let’s equate the posterior belief $\mu_{s}$ in Bayesian persuasion to the principal’s decision $x_{s}$ in the generalized principal-agent problem, so the principal/sender’s decision space becomes $\mathcal{X}=\Delta(\Omega)$.
The Bayes plausibility condition (2) becomes the constraint in the constrained generalized principal-agent problem.
When the agent/receiver takes action $a$, the principal/sender’s (expected) utility under decision/posterior $x_{s}=\mu_{s}$ is
$u(x_{s},a)=\mathbb{E}_{\omega\sim\mu_{s}}u(\omega,a)=\sum_{\omega\in\Omega}\mu
_{s}(\omega)u(\omega,a)$.
Suppose the agent takes action $a_{s}$ given signal $s\in S$. Then we see that the sender’s utility of using signaling scheme $\pi$ in Bayesian persuasion (left) is equal to the principal’s utility of using strategy $\pi$ in the generalized principal-agent problem (right):

$$ $\displaystyle\sum_{\omega\in\Omega}\mu_{0}(\omega)\sum_{s\in S}\pi(s|\omega)u( \omega,a_{s})=\sum_{s\in S}\pi_{s}\sum_{\omega\in\Omega}\mu_{s}(\omega)u( \omega,a_{s})=\sum_{s\in S}\pi_{s}u(x_{s},a_{s})=\mathbb{E}_{s\sim\pi}[u(x_{s} ,a)].$ $$

Similarly, the agent/receiver’s utilities in the two problems are equal.
The utility functions $u(x,a)$, $v(x,a)$ are linear in the principal’s decision $x\in\mathcal{X}$, satisfying our assumption.

#### Persuasion (or cheap talk) with a learning agent

When specialized to Bayesian persuasion, the generalized principal-agent problem with a learning agent becomes the following:

[frametitle=Persuasion (or Cheap Talk) with a Learning Receiver]
In each round $t=1,\ldots,T$, the following events happen:

- (1)
Using some algorithm that learns from history, the receiver chooses a strategy $\rho^{t}:S\to\Delta(A)$ that maps each signal $s\in S$ to a distribution over actions $\rho^{t}(s)\in\Delta(A)$.
- (2)
The sender chooses a signaling scheme $\pi^{t}:\Omega\to\Delta(S)$.
- (3)
A state of the world $\omega^{t}\sim\mu_{0}$ is realized, observed by the sender but not the receiver. The sender sends signal $s^{t}\sim\pi^{t}(\omega^{t})$ to the receiver. The receiver draws action $a^{t}\sim\rho^{t}(s)$.
- (4)
The sender obtains utility $u^{t}=u(\omega^{t},a^{t})$ and the receiver obtains utility $v^{t}=v(\omega^{t},a^{t})$.(^3^33The definition of utility here, $u(\omega^{t},a^{t}),v(\omega^{t},a^{t})$, is slightly different from the definition in Section 2.2, which was the expected utility on decision/posterior $x^{t}$, $u(x^{t},a^{t}),v(x^{t},a^{t})$. Because we eventually only care about the sender’s utility and the receiver’s regret in expectation, this difference does not matter.)

The receiver does not need to know the prior $\mu_{0}$ if its learning algorithm does not make use of $\mu_{0}$.
And same as the model in Section 2.2, the receiver chooses $\rho^{t}$ without knowing the sender’s signaling scheme $\pi^{t}$, and the sender does not commit.
In the classical *cheap talk* model (Crawford and Sobel, ), the sender does not have commitment power and the two players move simultaneously.
So, under our learning receiver model, cheap talk and Bayesian persuasion are equivalent. Our “persuasion with a learning receiver” model can also be called “cheap talk with a learning receiver”.

## 3 Reduction from Learning to Approximate Best Response

In this section, we reduce the generalized principal-agent problem with a learning agent to the problem with an approximately-best-responding agent.
We show that, if the agent uses contextual no-regret learning algorithms, then the principal can obtain an average utility that is at least the “maxmin” approximate-best-response objective $\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\mathrm{CReg}(T)/T\big{)}$ (to be defined below).
On the other hand, if the agent does contextual no-swap-regret learning, then the principal cannot do better than the “maxmax” approximate-best-response objective $\overline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\mathrm{CSReg}(T)/T\big{)}$.
In addition, if the agent uses some learning algorithms that are no-regret but not no-swap-regret, the principal can sometimes do better than the “maxmax” objective $\overline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\mathrm{CSReg}(T)/T\big{)}$.

### 3.1 Generalized Principal-Agent Problem with Approximate Best Response

We first define the generalized principal-agent problem with an *approximately-best-responding* agent.
The classic generalized principal-agent problem (Section 2.1) assumes that, after receiving a signal $s\in S$ (and observing the principal’s decision $x_{s}\in\mathcal{X}$), the agent will take an optimal action with respect to $x_{s}$. This means that the agent uses a strategy $\rho^{*}$ that *best responds* to the principal’s strategy $\pi$:

$$ $\rho^{*}(s)\in\operatorname*{arg\,max}_{a\in A}v(x_{s},a),~{}~{}\forall s\in S \quad\implies\quad\rho^{*}\in\operatorname*{arg\,max}_{\rho:S\to\Delta(A)}V( \pi,\rho).$ (3) $$

Here, $V(\pi,\rho)=\sum_{s\in S}\pi_{s}\sum_{a\in A}\rho(a|s)v(x_{s},a)$ denotes the expected utility of the agent when the principal uses strategy $\pi$ and the agent uses randomized strategy $\rho:S\to\Delta(A)$.

Here, we allow the agent to *approximately* best respond.
Let $\delta\geq 0$ be a parameter.
We define two types of $\delta$-best-responding strategies for the agent: deterministic and randomized.

- •
A deterministic strategy $\rho$: for each signal $s\in S$, the agent takes an action $a$ that is $\delta$-optimal for $x_{s}$. Denote this set of strategies by $\mathcal{D}_{\delta}(\pi)$:
$\mathcal{D}_{\delta}(\pi)=\big{\{}\rho:S\to A\mid v(x_{s},\rho(s))\geq v(x_{s}
,a^{\prime})-\delta,~{}\forall a^{\prime}\in A\big{\}}.$
(4)
- •
A randomized strategy $\rho$: for each signals $s$, the agent can take a randomized action. The expected utility of $\rho$ is at most $\delta$-worst than the best strategy $\rho^{*}$.
$\mathcal{R}_{\delta}(\pi)=\big{\{}\rho:S\to\Delta(A)\mid V(\pi,\rho)\geq V(\pi
,\rho^{*})-\delta\big{\}}.$
(5)
Equivalently, $\mathcal{R}_{\delta}(\pi)=\big{\{}\rho:S\to\Delta(A)\mid V(\pi,\rho)\geq V(\pi
,\rho^{\prime})-\delta,~{}\forall\rho^{\prime}:S\to A\big{\}}$.

Our model of approximately-best-responding agent includes, for example, two other models in the Bayesian persuasion literature that also relax the agent’s Bayesian rationality assumption:
the quantal response model (proposed by McKelvey and Palfrey () in normal-form games and studied by Feng et al. () in Bayesian persuasion) and a model where the agent makes mistakes in Bayesian update (de Clippel and Zhang, ).

###### Example 3.1 .

Assume that the receiver’s utility is in $[0,1]$.
In Bayesian persuasion, the following strategies of the receiver are $\delta$-best-responding (see Appendix B.1 for a proof):

- •
*Quantal response:* given signal $s\in S$, the agent chooses action $a\in A$ with probability $\frac{\exp(\lambda v(\mu_{s},a))}{\sum_{a^{\prime}\in A}\exp(\lambda v(\mu_{s}
,a^{\prime}))}$, with $\lambda>0$. This strategy belongs to $\mathcal{R}_{\delta}(\pi)$ with $\delta=\frac{1+\log(|A|\lambda)}{\lambda}$.
- •
*Inaccurate belief:* given signal $s\in S$, the agent forms some posterior $\mu_{s}^{\prime}$ that is different yet close to the true posterior $\mu_{s}$ in total variation distance $d_{\mathrm{TV}}(\mu_{s}^{\prime},\mu_{s})\leq\varepsilon$. The agent picks an optimal action for $\mu_{s}^{\prime}$. This strategy belongs to $\mathcal{D}_{2\varepsilon}(\pi)$.

###### Example 3.1 .

#### Principal’s objectives.

With an approximately-best-responding agent, we will study two types of objectives for the principal.
The first type is the maximal utility that the principal can obtain if the agent approximately best responds in the *worst* way for the principal: for $X\in\{\mathcal{D},\mathcal{R}\}$, define

$$ $\underline{\mathrm{OBJ}}^{X}(\delta)=\sup_{\pi}\min_{\rho\in X_{\delta}(\pi)}U (\pi,\rho),$ (6) $$

where $U(\pi,\rho)=\sum_{s\in S}\pi_{s}\sum_{a\in A}\rho(a|s)u(x_{s},a)$ is the principal’s expected utility when the principal uses strategy $\pi$ and the agent uses strategy $\rho$.
We used “$\sup$” in (6) because the maximizer does not necessarily exist.
$\underline{\mathrm{OBJ}}^{X}(\delta)$ is a “maxmin” objective and can be regarded as the objective of a “robust generalized principal-agent problem”.

The second type of objectives is the maximal utility that the principal can obtain if the agent approximately best responds in the *best* way:

$$ $\overline{\mathrm{OBJ}}^{X}(\delta)=\max_{\pi}\max_{\rho\in X_{\delta}(\pi)}U( \pi,\rho).$ (7) $$

This is a “maxmax” objective that quantifies the maximal extent to which the principal can exploit the agent’s irrational behavior.

Clearly, $\underline{\mathrm{OBJ}}^{X}(\delta)\leq\underline{\mathrm{OBJ}}^{X}(0)\leq
\overline{\mathrm{OBJ}}^{X}(0)\leq\overline{\mathrm{OBJ}}^{X}(\delta)$. And we note that $\overline{\mathrm{OBJ}}^{X}(0)=\overline{\mathrm{OBJ}}(0)$ is independent of $X$ and equal to the Stackelberg value $U^{*}$ defined in (1):

$$ $\overline{\mathrm{OBJ}}(0)=\max_{\pi}\max_{\rho:\text{ best-response to $\pi$} }U(\pi,\rho)=U^{*}.$ (8) $$

Finally, we note that, because $\mathcal{D}_{0}(\pi)\subseteq\mathcal{D}_{\delta}(\pi)\subseteq\mathcal{R}_{
\delta}(\pi)$, the chain of inequalities $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\leq\underline{\mathrm{OBJ}}^{
\mathcal{D}}(\delta)\leq U^{*}\leq\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta
)\leq\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ hold.

### 3.2 Agent’s No-Regret Learning: Lower Bound on Principal’s Utility

###### Theorem 3.1 .

Suppose the agent uses a contextual no-regret learning algorithm with a contextual regret upper bounded by $\mathrm{CReg}(T)$. The principal knows $\mathrm{CReg}(T)$ but not the exact algorithm of the agent. By using some fixed strategy $\pi^{t}=\pi$ in all $T$ rounds, the principal can obtain an average utility $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}$ that is arbitrarily close to $\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{T})$.

To prove Theorem 3.1, we provide a lemma to relate the agent’s regret and the principal’s utility in the learning model to those in the static model. We define some notations. Let the principal use some fixed strategy $\pi^{t}=\pi$ and the agent use some learning algorithm. Let $p_{a|s}^{t}=\Pr[a^{t}=a\,|\,s^{t}=s]$ be the probability that the agent’s algorithm chooses action $a$ conditioning on signal $s$ being sent in round $t$.
Let $\rho:S\to\Delta(A)$ be a randomized agent strategy that, given signal $s$, chooses each action $a\in A$ with probability $\rho(a|s)=\tfrac{\sum_{t=1}^{T}p_{a|s}^{t}}{T}$.

###### Lemma 3.2 .

When the principal uses a fixed strategy $\pi^{t}=\pi$ in all $T$ rounds, the regret of the agent not deviating according to $d:S\to A$ is equal to $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}\big{(}v(x^{t},d(s^{t}))-v(x^{t},a^{
t})\big{)}\big{]}=V(\pi,d)-V(\pi,\rho)$,
and the average utility of the principal $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}$ is equal to $U(\pi,\rho)$.

###### Proof.

Since $\pi^{t}=\pi$ is fixed, we have $\pi_{s}^{t}=\pi_{s}$ and $x_{s}^{t}=x_{s}$, $\forall s\in S$.
The regret of the agent not deviating according to $d$ is:

$$ $\displaystyle\frac{1}{T}\mathbb{E}\Big{[}\sum_{t=1}^{T}\Big{(}v(x^{t},d(s^{t}) )-v(x^{t},a^{t})\Big{)}\Big{]}=\frac{1}{T}\sum_{t=1}^{T}\sum_{s\in S}\pi^{t}_{ s}\sum_{a\in A}p_{a|s}^{t}\Big{(}v(x_{s}^{t},d(s))-v(x_{s}^{t},a)\Big{)}$ $\displaystyle~{}~{}=\sum_{s\in S}\pi_{s}\sum_{a\in A}\tfrac{\sum_{t=1}^{T}p_{a |s}^{t}}{T}\Big{(}v(x_{s},d(s))-v(x_{s},a)\Big{)}$ $\displaystyle~{}~{}=\sum_{s\in S}\pi_{s}v(x_{s},d(s))~{}-~{}\sum_{s\in S}\pi_{ s}\sum_{a\in A}\rho(a|s)v(x_{s},a)~{}=~{}V(\pi,d)-V(\pi,\rho).$ $$

Here, $d$ is interpreted as an agent strategy that deterministically takes action $d(s)$ for signal $s$.

By a similar derivation, we see that the principal’s expected utility is equal to $\frac{1}{T}\mathbb{E}\Big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\Big{]}=\sum_{s\in S}
\pi_{s}\sum_{a\in A}\tfrac{\sum_{t=1}^{T}p_{a|s}^{t}}{T}u(x_{s},a)=U(\pi,\rho)$,
which proves the lemma.
∎

###### Proof of Theorem 3.1 .

By Lemma 3.2
and the no-regret condition that the agent’s regret
$\mathbb{E}\big{[}\sum_{t=1}^{T}\big{(}v(x^{t},d(s^{t}))-v(x^{t},a^{t})\big{)}
\big{]}\leq\mathrm{CReg}(T)$, we have

$$ $V(\pi,d)-V(\pi,\rho)\,=\,\frac{1}{T}\mathbb{E}\Big{[}\sum_{t=1}^{T}\Big{(}v(x^ {t},d(s^{t}))-v(x^{t},a^{t})\Big{)}\Big{]}\,\leq\,\frac{\mathrm{CReg}(T)}{T}, \quad\forall d:S\to A.$ $$

This means that the agent’s randomized strategy $\rho$ is a $\delta=\frac{\mathrm{CReg}(T)}{T}$-best-response to the principal’s fixed signaling scheme $\pi$,
$\rho\in\mathcal{R}_{\delta=\frac{\mathrm{CReg}(T)}{T}}(\pi)$.
This holds for any $\pi$. In particular, if for any $\varepsilon>0$ the principal uses a signaling scheme $\pi^{\varepsilon}$ that obtains an objective that is $\varepsilon$-close to $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)=\sup_{\pi}\min_{\rho\in\mathcal
{R}_{\delta}(\pi)}U(\pi,\rho)$, then the principal obtains an expected utility of, by Lemma 3.2,

$$ $\frac{1}{T}\mathbb{E}\Big{[}\sum_{t=1}^{T}u(a^{t},\omega^{t})\Big{]}\,=\,U(\pi ^{\varepsilon},\rho)\,\geq\min_{\rho\in\mathcal{R}_{\delta}(\pi^{\varepsilon}) }U(\pi^{\varepsilon},\rho)\,\geq\,\underline{\mathrm{OBJ}}^{\mathcal{R}}\Big{( }\delta=\frac{\mathrm{CReg}(T)}{T}\Big{)}-\varepsilon$ $$

in the learning model. Letting $\varepsilon\to 0$ proves the theorem.
∎

We then show that the result in Theorem 3.1 is tight: there exist cases where the principal cannot do better than $\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{2T})$ even using adaptive strategies:

###### Theorem 3.3 .

For any adaptive strategy of the principal, there exists a contextual no-regret learning algorithm for the agent under which the principal’s average utility is no more than $\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{2T})$. There also exists a contextual no-swap-regret learning algorithm for the agent under which the principal’s average utility is no more than $\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CSReg}(T)}{2T})$.

See Appendix B.2 for the proof of this Theorem.

###### Theorem 3.1 .

###### Lemma 3.2 .

###### Proof.

###### Proof of Theorem 3.1 .

###### Theorem 3.3 .

### 3.3 Agent’s No-Swap-Regret Learning: Upper Bound on Principal’s Utility

As we mentioned in Section 2.2, the fact that the principal moves after the learning agent in each round gives the principal a possibility to exploit the agent to do better than $U^{*}$.
However, exploiting the agent in a single round may cause the agent to learn a bad strategy for the principal in later rounds.
It turns out that, if the agent’s learning algorithm satisfies the contextual no-swap-regret property, then the principal cannot exploit the agent in the long run. Formally:

###### Theorem 3.4 .

Against a contextual no-swap-regret learning agent, the principal cannot obtain utility more than
$\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\leq\overline{
\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CSReg}(T)}{T}\big{)}$, even if the principal knows the agent’s learning algorithm and chooses $\pi^{t}$ based on $\rho^{t}$.

Before presenting the full proof of this theorem, we give the high level idea of the proof.
The key idea is to think of the signal $s^{t}\sim\pi^{t}$ from the principal and the action $a^{t}\sim\rho^{t}(s^{t})$ recommended by the agent’s learning algorithm together as a joint signal $(s^{t},a^{t})$ from some hypothetical signaling scheme $\pi^{\prime}$. In response to $\pi^{\prime}$, the agent takes the action $a^{t}$ recommended by the algorithm, namely using the mapping $(s^{t},a^{t})\mapsto a^{t}$ as his strategy. A contextual no-swap-regret algorithm guarantees that the agent is at most $\frac{\mathrm{CSReg}(T)}{T}$ worse compared to using the strategy $d^{*}:S\times A\to A$ that best responds to $\pi^{\prime}$. So, the agent’s overall strategy is a $\frac{\mathrm{CSReg}(T)}{T}$-approximate best response to $\pi^{\prime}$. This limits the principal’s overall utility to be at most $\overline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CSReg}(T)}{T}\big{)}$. See details below:

###### Proof.

Let $p_{s}^{t}=\Pr[s^{t}=s]=\mathbb{E}\big{[}\mathbbm{1}[s^{t}=s]\big{]}=\mathbb{E}
[\pi_{s}^{t}]$ be the (unconditional) probability that signal $s\in S$ is sent in round $t$. Let $p_{a|s}^{t}=\Pr[a^{t}=a\,|\,s^{t}=s]$ be the probability that the agent’s algorithm takes action $a$ conditioning on signal $s^{t}=s$ being sent in round $t$.
Let $d:S\times A\to A$ be any deviation function for the agent. The agent’s utility gain by deviation is upper bounded by the contextual swap-regret:

$$ $\displaystyle\frac{\mathrm{CSReg}(T)}{T}\geq\frac{1}{T}\mathbb{E}\Big{[}\sum_{ t=1}^{T}\Big{(}v(x^{t},d(s^{t},a^{t}))-v(x^{t},a^{t})\Big{)}\Big{]}$ (9) $\displaystyle~{}=\frac{1}{T}\sum_{t=1}^{T}\sum_{s\in S}p_{s}^{t}\sum_{a\in A}p _{a|s}^{t}\mathbb{E}_{x^{t}_{s}|s^{t}=s}\Big{[}v(x^{t}_{s},d(s,a))-v(x^{t}_{s} ,a)\Big{]}$ $\displaystyle~{}=\frac{1}{T}\sum_{t=1}^{T}\sum_{s\in S}p_{s}^{t}\sum_{a\in A}p _{a|s}^{t}\Big{(}v(\mathbb{E}[x_{s}^{t}|s^{t}=s],d(s,a))-v(\mathbb{E}[x_{s}^{t }|s^{t}=s],a)\Big{)}\quad\text{by linearity of $v(\cdot,a)$}$ $\displaystyle~{}=\sum_{s\in S}\sum_{a\in A}\frac{\sum_{j=1}^{T}p_{s}^{j}p_{a|s }^{j}}{T}\frac{1}{\sum_{j=1}^{T}p_{s}^{j}p_{a|s}^{j}}\sum_{t=1}^{T}p_{s}^{t}p_ {a|s}^{t}\Big{(}v(\mathbb{E}[x_{s}^{t}|s^{t}=s],d(s,a))-v(\mathbb{E}[x_{s}^{t} |s^{t}=s],a)\Big{)}$ $\displaystyle~{}=\sum_{s\in S}\sum_{a\in A}\frac{\sum_{j=1}^{T}p_{s}^{j}p_{a|s }^{j}}{T}\bigg{[}v\Big{(}\tfrac{\sum_{t=1}^{T}p_{s}^{t}p_{a|s}^{t}\mathbb{E}[x _{s}^{t}|s^{t}=s]}{\sum_{j=1}^{T}p_{s}^{j}p_{a|s}^{j}},d(s,a)\Big{)}-v\Big{(} \tfrac{\sum_{t=1}^{T}p_{s}^{t}p_{a|s}^{t}\mathbb{E}[x_{s}^{t}|s^{t}=s]}{\sum_{ j=1}^{T}p_{s}^{j}p_{a|s}^{j}},a\Big{)}\bigg{]}.$ $$

Define $q_{s,a}=\frac{\sum_{j=1}^{T}p_{s}^{j}p_{a|s}^{j}}{T}$ and $y_{s,a}=\frac{\sum_{t=1}^{T}p_{s}^{t}p_{a|s}^{t}\mathbb{E}[x_{s}^{t}|s^{t}=s]}
{\sum_{j=1}^{T}p_{s}^{j}p_{a|s}^{j}}\in\mathcal{X}$. Then the above is equal to

$$ $\displaystyle=\sum_{s\in S}\sum_{a\in A}q_{s,a}\Big{[}v(y_{s,a},d(s,a))-v(y_{s ,a},a)\Big{]}.$ (10) $$

We note that $\sum_{s\in S}\sum_{a\in A}q_{s,a}=\frac{\sum_{j=1}^{T}\sum_{s\in S}\sum_{a\in A
}p_{s}^{j}p_{a|s}^{j}}{T}=1$, so $q$ is a probability distribution over $S\times A$. And note that

$$ $\displaystyle\sum_{s,a\in S\times A}q_{s,a}y_{s,a}$ $\displaystyle~{}=~{}\sum_{s,a\in S\times A}\frac{1}{T}\sum_{t=1}^{T}p_{s}^{t}p _{a|s}^{t}\mathbb{E}[x_{s}^{t}|s^{t}=s]~{}=~{}\frac{1}{T}\sum_{t=1}^{T}\sum_{s \in S}p_{s}^{t}\mathbb{E}[x_{s}^{t}|s^{t}=s]$ $\displaystyle~{}=~{}\frac{1}{T}\sum_{t=1}^{T}\sum_{s\in S}\mathbb{E}\big{[} \mathbbm{1}[s^{t}=s]x_{s}^{t}\big{]}~{}=~{}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E} \big{[}\sum_{s\in S}\mathbbm{1}[s^{t}=s]x_{s}^{t}\big{]}~{}=~{}\frac{1}{T}\sum _{t=1}^{T}\mathbb{E}\big{[}x^{t}\big{]}$ $\displaystyle~{}=~{}\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\big{[}\sum_{s\in S}\pi ^{t}_{s}x_{s}^{t}\big{]}\in\mathcal{C}\quad\quad\text{because $\sum_{s\in S} \pi_{s}^{t}x_{s}^{t}\in\mathcal{C}$.}$ $$

This means that $\pi^{\prime}=\{(q_{s,a},y_{s,a})\}_{(s,a)\in S\times A}$ defines a valid principal strategy with the larger signal space $S\times A$.(^4^44As long as $|S|\geq|A|$, enlarging the signal space from $S$ to $S\times A$ will not change the optimal objective for the principal, because the optimal strategy of the principal only needs to use $|A|$ signals by the revelation principle.) Then, we note that (10) is the difference between the agent’s expected utility under principal strategy $\pi^{\prime}$ when responding using strategy $d:S\times A\to A$ and using the strategy that maps signal $(s,a)$ to action $a$. And (10) is upper bounded by $\frac{\mathrm{CSReg}(T)}{T}$ by (9):

$$ $\eqref{eq:utility-difference-q-mu}=V(\pi^{\prime},d)-V(\pi^{\prime},(s,a) \mapsto a)\,\leq\,\tfrac{\mathrm{CSReg}(T)}{T},~{}~{}~{}\forall d:S\times A\to A.$ (11) $$

In particular, this holds when $d$ is the agent’s best-responding strategy. This means that the agent strategy $(s,a)\mapsto a$ is a $(\frac{\mathrm{CSReg}(T)}{T})$-best-response to $\pi^{\prime}$. So, the principal’s expected utility is upper bounded by the utility in the approximate-best-response model:

$$ $\displaystyle\frac{1}{T}\mathbb{E}\Big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\Big{]}$ $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\sum_{s\in S}p_{s}^{t}\sum_{a\in A}p_{a |s}^{t}v(\mathbb{E}[x_{s}^{t}|s^{t}=s],a)$ $\displaystyle=\sum_{s\in S}\sum_{a\in A}q_{s,a}u(y_{s,a},a)~{}=~{}U(\pi^{ \prime},(s,a)\to a)~{}\leq~{}\overline{\mathrm{OBJ}}^{\mathcal{R}}\big{(} \tfrac{\mathrm{CSReg}(T)}{T}\big{)}.$ $$

∎

###### Theorem 3.4 .

###### Proof.

### 3.4 Agent’s Mean-Based Learning: Exploitable by the Principal

Many no-regret (but not no-swap-regret) learning algorithms (e.g., MWU, FTPL, EXP-3) satisfy the following *contextual mean-based* property:

###### Definition 3.1 ( Braverman et al. ( 2018 ) ) .

Let $\sigma_{s}^{t}(a)=\sum_{j\in[t]:s^{j}=s}v(\omega^{j},a)$ be the sum of historical utilities of the receiver in the first $t$ rounds if he takes action $a$ when the signal/context is $s$. An algorithm is called *$\gamma$-mean-based* if: whenever $\exists a^{\prime}$ such that $\sigma_{s}^{t-1}(a)<\sigma_{s}^{t-1}(a^{\prime})-\gamma T$,
the probability that the algorithm chooses action $a$ at round $t$ if the context is $s$ is $\Pr[a^{t}=a|s^{t}=s]<\gamma$, with $\gamma=o(1)$.

We show that if the agent uses mean-based learning algorithm, then the principal can indeed exploit the agent, in particular in the Bayesian persuasion setting:

###### Theorem 3.5 .

There exists a Bayesian persuasion instance where, as long as the receiver does $\gamma$-mean-based learning, the sender can obtain a utility significantly larger than $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\gamma)$ and
$U^{*}$.

###### Proof.

The instance has $2$ states (A, B), $3$ actions (L, M, R), uniform prior $\mu_{0}(\rm{A})=\mu_{0}(\rm B)=0.5$, with the following utility matrices (left for sender’s, right for receiver’s):

| $u(\omega,a)$ | L | M | R |  |  |  |  | $v(\omega,a)$ | L | M | R |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| A | 0 0 | $-2$ | $-2$ |  |  |  |  | A | $\sqrt{\gamma}$ | $-1$ | 0 0 |
| B | 0 0 | 0 0 | $2$ |  |  |  |  | B | $-1$ | $1$ | 0 0 |

###### Claim 3.6 .

In this instance, the optimal sender utility $U^{*}$ in the classic BP model is 0 0, and the approximate-best-response objective $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\gamma)=O(\gamma)$.

###### Proof.

Recall that any signaling scheme decomposes the prior $\mu_{0}$ into multiple posteriors $\{\mu_{s}\}_{s\in S}$. If a posterior $\mu_{s}$ puts probability $>0.5$ to state B, then the receiver will take action M, which gives the sender a utility $\leq 0$; if the posterior $\mu_{s}$ puts probability $\leq 0.5$ to state B, then no matter what action the receiver takes, the sender’s expected utility on $\mu_{s}$ cannot be greater than 0 0. So, the sender’s expected utility is $\leq 0$ under any signaling scheme. An optimal signaling scheme is to reveal no information (keep $\mu_{s}=\mu_{0}$); the receiver takes R and the sender gets utility 0 0.

This instance satisfies the assumptions of Theorem 4.3, so $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\gamma)\leq U^{*}+O(\gamma)=O(\gamma)$.
∎

###### Claim 3.7 .

By doing the following, the sender can obtain utility $\approx\frac{1}{2}-O(\sqrt{\gamma})$ if the receiver is $\gamma$-mean-based learning:

- •
in the first $T/2$ rounds: if the state is A, send signal 1; if the state is B, send 2.
- •
in the remaining $T/2$ rounds, switch the scheme: if the state is A, send 2; if state is B, send 1.

###### Proof.

In the first $T/2$ rounds, the receiver finds that signal 1 corresponds to state A so he will take action L with high probability when signal 1 is sent; signal 2 corresponds to B so he will take action M with high probability. In this phase, the sender obtains utility $\approx 0$ per round. At the end of this phase, for signal 1, the receiver accumulates utility $\approx\frac{T}{2}\frac{1}{2}\sqrt{\gamma}=\frac{T}{4}\sqrt{\gamma}$ for action L. For signal 2, the receiver accumulates utility $\approx\frac{T}{2}\frac{1}{2}\cdot 1=\frac{T}{4}$ for action M.

In the remaining $T/2$ rounds, the following will happen:

- •
For signal 1, the receiver finds that the state is now B, so the utility of action L decreases by 1 every time signal 1 is sent. Because the utility of L accumulated in the first phase was $\approx\frac{T}{4}\sqrt{\gamma}$, after $\approx\frac{T}{4}\sqrt{\gamma}$ rounds in second phase the utility of L should decrease to below 0 0, and the receiver will no longer play L (with high probability) at signal 1. The receiver will not play M at signal 1 in most of the second phase either, because there are more A states than B states at signal 1 historically. So, the receiver will play action R most times, roughly $\frac{T}{4}-\frac{T}{4}\sqrt{\gamma}$ rounds. This gives the sender a total utility of $\approx(\frac{T}{4}-\frac{T}{4}\sqrt{\gamma})\cdot 2=\frac{T}{2}-O(T\sqrt{
\gamma})$.
- •
For signal 2, the state is now A. But the receiver will continue to play action M in most times. This because: R has utility 0; L accumulated $\approx-\frac{T}{4}$ utility in the first phase, and only increases by $\sqrt{\gamma}$ per round in the second phase, so its accumulated utility is always negative; instead, M has accumulated $\frac{T}{4}$ utility in the first phase, and decreases by 1 every time signal $2$ is sent in the second phase, so its utility is positive until near the end. So, the receiver will play M. This gives the sender utility 0 0.

Summing up, the sender obtains total utility $\approx\frac{T}{2}-O(T\sqrt{\gamma})$ in these two phases, which is $\frac{1}{2}-O(\sqrt{\gamma})>0$ per round in average.
∎

The above two claims together prove the theorem.
∎

###### Definition 3.1 ( Braverman et al. ( 2018 ) ) .

###### Theorem 3.5 .

###### Proof.

###### Claim 3.6 .

###### Proof.

###### Claim 3.7 .

###### Proof.

## 4 Generalized Principal-Agent Problems with Approximate Best Response

After presenting the reduction from learning to approximate best response, we now study generalized principal-agent problems with approximate best response.
We will show that both the maxmin objectives $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$, $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ and the maxmax objectives $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$, $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ are close to the optimal principal objective $U^{*}$ in the best-response model when the degree $\delta$ of the agent’s approximate best response is small, under some natural assumptions described below.

#### Assumptions and notations.

We make some innocuous assumptions.
First, the agent has no weakly dominated action:

###### Assumption 4.1 (No Dominated Action) .

An action $a_{0}\in A$ of the agent is *weakly dominated* if there exists a mixed action $\alpha^{\prime}\in\Delta(A\setminus\{a_{0}\})$ such that $v(x,\alpha^{\prime})=\mathbb{E}_{a\sim\alpha^{\prime}}[v(x,a)]\geq v(x,a_{0})$ for all $x\in\mathcal{X}$. We assume that the agent has no weakly dominated action.

###### Claim 4.1 .

Assumption 4.1 implies: there exists a constant $G>0$ such that, for any agent action $a\in A$, there exists a principal decision $x\in\mathcal{X}$ such that $v(x,a)-v(x,a^{\prime})\geq G$ for every $a^{\prime}\in A\setminus\{a\}$.

The proof of this claim is in Appendix C.1.
The constant $G>0$ in Claim 4.1 is analogous to the concept of “inducibility gap” in Stackelberg games (Von Stengel and Zamir, ; Gan et al., ).
In fact, Gan et al. () show that, if the inducibility gap $G>\delta$, then the maximin approximate-best-response objective satisfies $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\geq U^{*}-\frac{\delta}{G}$ in Stackelberg games. Our results will significantly generalize theirs to any generalized principal-agent problem, to randomized agent strategies, and to the maximax objectives $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$, $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$.

To present our results, we need to introduce a few more notions and assumptions. Let
$\mathrm{diam}(\mathcal{X};\|\cdot\|)=\max_{x_{1},x_{2}\in\mathcal{X}}\|x_{1}-x
_{2}\|$
be the diameter of the space $\mathcal{X}$, where $\|\cdot\|$ is some norm. For convenience we assume $\mathcal{X}\subseteq{\mathbb{R}}^{d}$ and use the $\ell_{1}$-norm $\|x\|_{1}=\sum_{i=1}^{d}|x_{(i)}|$ or the $\ell_{\infty}$-norm $\|x\|_{\infty}=\max_{i=1}^{d}|x_{(i)}|$.
For a generalized principal-agent problem with constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$, let $\partial\mathcal{X}$ be the boundary of $\mathcal{X}$ and let
$\mathrm{dist}(\mathcal{C},\partial\mathcal{X})=\min_{c\in\mathcal{C},x\in
\partial X}\|c-x\|$
be the distance from $\mathcal{C}$ to the boundary of $\mathcal{X}$. We assume that $\mathcal{C}$ is away from the boundary of $\mathcal{X}$:

###### Assumption 4.2 ( $\mathcal{C}$ is in the interior of $\mathcal{X}$ ) .

$\mathrm{dist}(\mathcal{C},\partial\mathcal{X})>0$.

###### Assumption 4.3 (Bounded and Lipschitz utility) .

The principal’s utility function is bounded: $|u(x,a)|\leq B$, and $L$-Lipschitz in $x\in\mathcal{X}$: $|u(x_{1},a)-u(x_{2},a)|\leq L\|x_{1}-x_{2}\|$.

###### Assumption 4.1 (No Dominated Action) .

###### Claim 4.1 .

###### Assumption 4.2 ( 𝒞 𝒞 \mathcal{C} caligraphic_C is in the interior of 𝒳 𝒳 \mathcal{X} caligraphic_X ) .

###### Assumption 4.3 (Bounded and Lipschitz utility) .

#### Main results.

We now present the main results of this section: lower bounds on $\underline{\mathrm{OBJ}}^{X}(\delta)$ and upper bounds on $\overline{\mathrm{OBJ}}^{X}(\delta)$ in generalized principal-agent problems without and with constraints.

###### Theorem 4.2 (Without constraint) .

For an unconstrained generalized principal-agent problem, under Assumptions 4.1 and 4.3, for $0\leq\delta<G$, we have

- •
$\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\geq\,U^{*}-\mathrm{diam}(
\mathcal{X})L\tfrac{\delta}{G}$.
- •
$\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\,\geq\,U^{*}-2\sqrt{\tfrac{2BL}
{G}\mathrm{diam}(\mathcal{X})\delta}~{}$ for $\delta<\frac{\mathrm{diam}(\mathcal{X})GL}{2B}$.
- •
$\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\leq\,\overline{\mathrm{OBJ}}^{
\mathcal{R}}(\delta)\,\leq\,U^{*}+\mathrm{diam}(\mathcal{X})L\tfrac{\delta}{G}$.

###### Theorem 4.3 (With constraint) .

For a generalized principal-agent problem with the constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$, under Assumptions 4.1, 4.2 and 4.3, for $0\leq\delta<\frac{G\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}{\mathrm{
diam}(\mathcal{X})}$, we have

- •
$\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\geq\,U^{*}-\big{(}\mathrm{
diam}(\mathcal{X})L+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(
\mathcal{C},\partial\mathcal{X})}\big{)}\tfrac{\delta}{G}$.
- •
$\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\,\geq\,U^{*}-2\sqrt{\tfrac{2B}{
G}\big{(}\mathrm{diam}(\mathcal{X})L+2B\tfrac{\mathrm{diam}(\mathcal{X})}{
\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\big{)}\delta}$.
- •
$\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\leq\,\overline{\mathrm{OBJ}}^{
\mathcal{R}}(\delta)\,\leq\,U^{*}+\big{(}\mathrm{diam}(\mathcal{X})L+2B\tfrac{
\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}
\big{)}\tfrac{\delta}{G}$.

The expression “$\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{
X})}\delta$” suggests that $\frac{1}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}$ is similar to a “condition number” (Renegar, ) that quantifies the “stability” of the principal-agent problem against the agent’s approximate-best-responding behavior. When $\mathrm{dist}(\mathcal{C},\partial\mathcal{X})$ is larger ($\mathcal{C}$ is further away from the boundary of $\mathcal{X}$), the condition number is smaller, the problem is more stable, and the $\delta$-best-response objectives $\underline{\mathrm{OBJ}}^{X}(\delta)$ and $\overline{\mathrm{OBJ}}^{X}(\delta)$ are closer to the best-response objective $U^{*}$.

###### Theorem 4.2 (Without constraint) .

###### Theorem 4.3 (With constraint) .

#### High-level idea: perturbation.

The high level idea to prove Theorems 4.2 and 4.3 is a perturbation argument. Consider proving the upper bounds on $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$ for example. Let $(\pi,\rho)$ be any pair of principal’s strategy and agent’s $\delta$-best-responding strategy. We perturb the principal’s strategy $\pi$ slightly to be a strategy $\pi^{\prime}$ such that $\rho$ is *exactly* best-responding to $\pi^{\prime}$ (such a perturbation is possible due to Assumption 4.1). Since $\rho$ is best-responding to $\pi^{\prime}$, the pair $(\pi^{\prime},\rho)$ cannot give the principal a higher utility than $U^{*}$ (which is the optimal principal utility under the best-response model). This means that the original pair $(\pi,\rho)$ cannot give the principal a utility much higher than $U^{*}$, thus implying an upper bound on $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$. Extra care is needed when dealing with randomized strategies of the agent.
See details in Appendix C.3.

#### The bound OBJ ¯ ℛ ⁢ ( δ ) ≥ U ∗ − O ⁢ ( δ ) superscript ¯ OBJ ℛ 𝛿 superscript 𝑈 𝑂 𝛿 \underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\geq U^{*}-O(\sqrt{\delta}) under¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_R end_POSTSUPERSCRIPT ( italic_δ ) ≥ italic_U start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT - italic_O ( square-root start_ARG italic_δ end_ARG ) is tight.

We note that, in Theorems 4.2 and 4.3, the maxmin objective with randomized agent strategies is bounded by $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\geq U^{*}-O(\sqrt{\delta})$, while the objective with deterministic agent strategies is bounded by $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\geq U^{*}-O(\delta)$. This is *not* because our analysis is not tight.
In fact, the squared root bound $U^{*}-\Theta(\sqrt{\delta})$ for $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ is tight.
We prove this by giving an example where $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\leq U^{*}-\Omega(\sqrt{\delta})$.
Consider the following classical Bayesian persuasion example:

###### Example 4.1 .

There are 2 states $\Omega=\{\mathrm{Good},\mathrm{Bad}\}$, 2 actions $A=\{a,b\}$, with the following utility matrices

| sender | $a$ | $b$ |  |  |  | receiver | $a$ | $b$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\mathrm{Good}$ | $1$ | 0 0 |  |  |  | $\mathrm{Good}$ | $1$ | 0 0 |
| $\mathrm{Bad}$ | $1$ | 0 0 |  |  |  | $\mathrm{Bad}$ | $-1$ | 0 0 |

The prior probability of $\mathrm{Good}$ state is $\mu_{0}<\frac{1}{2}$, so the receiver takes action $b$ by default.
In this example, for $\delta<\frac{\mu_{0}}{2}$, $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\leq U^{*}-2\sqrt{2\mu_{0}\delta
}+\delta=U^{*}-\Omega(\sqrt{\delta})$. See Appendix C.2 for a proof.

###### Example 4.1 .

## 5 Applications to Specific Principal-Agent Problems

We apply the general results in Section 3 and 4 to derive concrete results for three specific principal-agent problems: Bayesian persuasion, Stackelberg games, and contract design.

### 5.1 Bayesian Persuasion

As noted in Section 2, Bayesian persuasion is a generalized principal-agent problem with constraint
$\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}=\{\mu_{0}\}$
where each $x_{s}=\mu_{s}=(\mu_{s}(\omega))_{\omega\in\Omega}\in\mathcal{X}=\Delta(\Omega)$ is a posterior belief.
Suppose the principal’s utility is bounded: $|u(\omega,a)|\leq B$. Then, the principal’s utility function
$u(\mu_{s},a)=\sum_{\omega\in\Omega}\mu_{s}(\omega)u(\omega,a)$
is $(L=B)$-Lipschitz in $\mu_{s}$ (under $\ell_{1}$-norm),
so Assumption 4.3 is satisfied.
Suppose the prior $\mu_{0}$ has positive probability for every $\omega\in\Omega$, and let $p_{0}=\min_{\omega\in\Omega}\mu_{0}(\omega)>0$.
Then, we have the distance

$$ $\mathrm{dist}(\mathcal{C},\partial X)=\min\big{\{}\|\mu_{0}-\mu\|_{1}:\mu\in \Delta(\Omega)\text{ s.t. }\mu(\omega)=0\text{ for some $\omega\in\Omega$}\big {\}}\geq p_{0}>0,$ $$

so Assumption 4.2 is satisfied. The diameter satisfies

$$ $\mathrm{diam}(\mathcal{X};\ell_{1})=\max_{\mu_{1},\mu_{2}\in\Delta(\Omega)}\| \mu_{1}-\mu_{2}\|_{1}\leq 2.$ $$

Finally, we assume Assumption 4.1 (no dominated action for the agent).
Then, Theorem 4.3 gives bounds on the approximate-best-response objectives in Bayesian persuasion:

###### Corollary 5.1 (Bayesian persuasion with approximate best response) .

For $0\leq\delta<\frac{Gp_{0}}{2}$,

- •
$\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\geq\,U^{*}-2B(1+\tfrac{2}{p_{
0}})\tfrac{\delta}{G}$.
- •
$\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\,\geq\,U^{*}-4B\sqrt{(1+\tfrac{
2}{p_{0}})\tfrac{\delta}{G}}$.
- •
$\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,\leq\,\overline{\mathrm{OBJ}}^{
\mathcal{R}}(\delta)\,\leq\,U^{*}+2B(1+\tfrac{2}{p_{0}})\tfrac{\delta}{G}$.

Further applying Theorem 3.1 and 3.4, we obtain the central result for our motivating problem, persuasion with a learning agent:

###### Corollary 5.2 (Persuasion with a learning agent) .

Suppose $T$ is sufficiently large such that $\frac{\mathrm{CReg}(T)}{T}<\frac{Gp_{0}}{2}$ and $\frac{\mathrm{CSReg}(T)}{T}<\frac{Gp_{0}}{2}$, then

- •
with a contextual no-regret learning agent, the principal can obtain utility at least
$\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\,\geq\,
\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\tfrac{\mathrm{CReg}(T)}{T}\big{)
}\,\geq\,U^{*}-4B\sqrt{(1+\tfrac{2}{p_{0}})\tfrac{1}{G}}\sqrt{\tfrac{\mathrm{
CReg}(T)}{T}}$
(12)
using a fixed signaling scheme in all rounds.
- •
with a contextual no-swap-regret learning agent, the principal’s obtainable utility is at most
$\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\,\leq\,
\overline{\mathrm{OBJ}}^{\mathcal{D}}\big{(}\tfrac{\mathrm{CSReg}(T)}{T}\big{)
}\,\leq\,U^{*}+2B(1+\tfrac{2}{p_{0}})\tfrac{1}{G}\tfrac{\mathrm{CSReg}(T)}{T}$
(13)
even knowing the receiver’s learning algorithm and using time-varying signaling schemes.

Result (13) is interesting because it shows that the sender cannot exploit a no-swap-regret learning receiver beyond $U^{*}+o(1)$ even if the sender has informational advantage (knowing the state $\omega$) and knows the receiver’s algorithm or strategy $\rho^{t}$ before choosing the signaling scheme. Result (12) is interesting because it shows that the sender can achieve the Bayesian persuasion optimal objective (which is $U^{*}$) in the problem of cheap talk with a learning agent (recall from Section 2.3 that persuasion and cheap talk are equivalent in our model).

###### Corollary 5.1 (Bayesian persuasion with approximate best response) .

###### Corollary 5.2 (Persuasion with a learning agent) .

### 5.2 Stackelberg Games

In a Stackelberg game, the principal (leader), having a finite action set $B$, first commits to a mixed strategy $x=(x_{(b)})_{b\in B}\in\Delta(B)$, which is a distribution over actions. So the principal’s decision space $\mathcal{X}$ is $\Delta(B)$. The agent (follower) then takes an action $a\in A$ in response to $x$. The (expected) utilities for the two players are $u(x,a)=\sum_{b\in B}x_{(b)}u(b,a)$ and $v(x,a)=\sum_{b\in B}x_{(b)}u(b,a)$.
The signal $s$ can (but not necessarily) be an action that the principal recommends the agent to take.

Assume bounded utility $|u(b,a)|\leq B$. Then, the principal’s utility function $u(x,a)$ is bounded in $[-B,B]$ and $(L=B)$-Lipschitz in $x$. The diameter $\mathrm{diam}(\mathcal{X})=\max_{x_{1},x_{2}\in\Delta(B)}\|x_{1}-x_{2}\|_{1}\leq
2$. Applying the theorem for unconstrained generalized principal-agent problems (Theorem 4.2) and the theorems for learning agent (Theorem 3.1 and 3.4), we obtain:

###### Corollary 5.3 (Stackelberg game with a learning agent) .

Suppose $T$ is sufficiently large such that $\frac{\mathrm{CReg}(T)}{T}<G$ and $\frac{\mathrm{CSReg}(T)}{T}<G$, then:

- •
with a contextual no-regret learning agent, the principal can obtain utility $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\geq\underline{
\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{T}\big{)}\geq U^{*}-
\frac{4B}{\sqrt{G}}\sqrt{\frac{\mathrm{CReg}(T)}{T}}$.
- •
with a contextual no-swap-regret learning agent, the principal cannot obtain utility more than $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\leq\overline{
\mathrm{OBJ}}^{\mathcal{D}}\big{(}\frac{\mathrm{CSReg}(T)}{T}\big{)}\leq U^{*}
+\tfrac{2B}{G}\frac{\mathrm{CSReg}(T)}{T}$.

The conclusion that the principal can obtain utility at least $U^{*}-o(1)$ against a no-regret learning agent and no more than $U^{*}+o(1)$ against a no-swap-regret agent in Stackelberg games was proved by Deng et al. (). Our Corollary 5.3 reproduces this conclusion and moreover provides bounds on the $o(1)$ terms, namely, $U^{*}-O(\sqrt{\frac{\mathrm{CReg}(T)}{T}})$ and $U^{*}+O(\frac{\mathrm{CSReg}(T)}{T})$. This demonstrates the generality and usefulness of our framework.

###### Corollary 5.3 (Stackelberg game with a learning agent) .

### 5.3 Contract Design

In contract design, there is a finite outcome space $O=\{r_{1},\ldots,r_{d}\}$ where each $r_{i}\in{\mathbb{R}}$ is a monetary reward to the principal. When the agent takes action $a\in A$, outcome $r_{i}$ will happen with probability $p_{ai}\geq 0$, $\sum_{i=1}^{d}p_{ai}=1$. The principal cannot observe the action taken by the agent but can observe the realized outcome. The principal’s decision space $\mathcal{X}$ is the set of contracts, where a contract $x=(x_{(i)})_{i=1}^{d}\in[0,+\infty]^{d}$ is a vector that specifies the payment to the agent for each possible outcome. So, if the agent takes action $a$ under contract $x$, the principal obtains expected utility

$$ $\displaystyle u(x,a)=\sum_{i=1}^{d}p_{ai}(r_{i}-x_{(i)})$ $$

and the agent obtains $v(x,a)=\sum_{i=1}^{d}p_{ai}x_{(i)}$.
The signal $s$ can (but not necessarily) be an action that the principal recommends the agent to take.
The principal’s decision space $\mathcal{X}\subseteq[0,+\infty]^{d}$ in contract design, however, may be unbounded and violate the requirement of bounded diameter $\mathrm{diam}(\mathcal{X})$ that we need.
We have two remedies for this.

The first remedy is to require the principal’s payment to the agent be upper bounded by some constant $P<+\infty$, so $0\leq x_{(i)}\leq P$ and $\mathcal{X}=[0,P]^{d}$. Under this requirement and the assumption of bounded reward $|r_{i}|\leq R$, the principal’s utility becomes bounded by
$|u(x,a)|\leq\sum_{i=1}^{d}p_{ai}(R+P)=R+P=B$
and $(L=1)$-Lipschitz under $\ell_{\infty}$-norm:

$$ $|u(x_{1},a)-u(x_{2},a)|=\big{|}\sum_{i=1}^{d}p_{ai}(x_{1(i)}-x_{2(i)})\big{|} \leq\max_{i=1}^{d}|x_{1(i)}-x_{2(i)}|\sum_{i=1}^{d}p_{ai}=\|x_{1}-x_{2}\|_{ \infty}.$ $$

And the diameter of $\mathcal{X}$ is bounded by (under $\ell_{\infty}$-norm)

$$ $\mathrm{diam}(\mathcal{X};\ell_{\infty})=\max_{x_{1},x_{2}\in\mathcal{X}}\|x_{ 1}-x_{2}\|_{\infty}=\max_{x_{1},x_{2}\in[0,P]^{d}}\max_{i=1}^{d}|x_{1(i)}-x_{2 (i)}|\leq P.$ $$

Now, we can apply the theorem for unconstrained generalized principal-agent problems (Theorem 4.2) and the theorems for learning agent (Theorem 3.1 and Theorem 3.4) to obtain:

###### Corollary 5.4 (Contract design (with bounded payment) with a learning agent) .

Suppose $T$ is sufficiently large such that $\frac{\mathrm{CReg}(T)}{T}<\frac{PG}{2(R+P)}$ and $\frac{\mathrm{CSReg}(T)}{T}<G$, then:

- •
with a contextual no-regret learning agent, the principal can obtain utility at least $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}$ $\geq\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{T}
\big{)}\geq U^{*}-2\sqrt{\tfrac{2(R+P)P}{G}}\sqrt{\frac{\mathrm{CReg}(T)}{T}}$.
- •
with contextual a no-swap-regret learning agent, the principal cannot obtain utility more than $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\leq\overline{
\mathrm{OBJ}}^{\mathcal{D}}\big{(}\frac{\mathrm{CSReg}(T)}{T}\big{)}\leq U^{*}
+\tfrac{P}{G}\frac{\mathrm{CSReg}(T)}{T}$.

The second remedy is to write contract design as a generalized principal-agent problem in another way. Let $\tilde{x}=(\tilde{x}_{(a)})_{a\in A}\in[0,+\infty]^{|A|}$ be a vector recording the *expected payment* from the principal to the agent for each action $a\in A$:

$$ $\tilde{x}_{(a)}=\sum_{i=1}^{d}p_{ai}x_{(i)}.$ $$

And let $\tilde{r}_{(a)}$ be the expected reward of action $a$, $\tilde{r}_{(a)}=\sum_{i=1}^{d}p_{ai}r_{i}$.
Then, the principal and the agent’s utility can be rewritten as functions of $\tilde{x}$ and $a$:

$$ $u(\tilde{x},a)=\tilde{r}_{(a)}-\tilde{x}_{(a)},\quad\quad v(\tilde{x},a)= \tilde{x}_{(a)},$ $$

which are linear in $\tilde{x}\in\tilde{\mathcal{X}}$. Assuming bounded reward $|\tilde{r}_{(a)}|\leq R$, we can without loss of generality assume that the expected payment $\tilde{x}_{(a)}$ is bounded by $R$ as well, because otherwise the principal will get negative utility. So, the principal’s decision space can be restricted to

$$ $\tilde{\mathcal{X}}=\big{\{}\tilde{x}\mid\text{$\exists$ $x\in[0,+\infty]^{d}$ such that $\tilde{x}_{(a)}=\sum_{i=1}^{d}p_{ai}x_{(i)}$ for every $a\in A$} \big{\}}\,\cap\,[0,R]^{|A|},$ $$

which is convex and has bounded diameter (under $\ell_{\infty}$ norm)

$$ $\mathrm{diam}(\tilde{\mathcal{X}};\ell_{\infty})\leq\mathrm{diam}([0,R]^{|A|}; \ell_{\infty})=R.$ $$

The utility function $u(\tilde{x},a)$ is bounded by $2R$ and $(L=1)$-Lipschitz (under $\ell_{\infty}$ norm):

$$ $|u(\tilde{x}_{1},a)-u(\tilde{x}_{2},a)|=|\tilde{x}_{1(a)}-\tilde{x}_{2(a)}| \leq\max_{a\in A}|\tilde{x}_{1(a)}-\tilde{x}_{2(a)}|=\|\tilde{x}_{1}-\tilde{x} _{2}\|_{\infty}.$ $$

Thus, we can apply the theorem for unconstrained generalized principal-agent problems (Theorem 4.2) and the theorems for learning agent (Theorem 3.1 and Theorem 3.4) to obtain:

###### Corollary 5.5 (Contract design with a learning agent) .

Suppose $T$ is sufficiently large such that $\frac{\mathrm{CReg}(T)}{T}<\frac{G}{2}$ and $\frac{\mathrm{CSReg}(T)}{T}<G$, then:

- •
with a contextual no-regret learning agent, the principal can obtain utility at least $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}$ $\geq\underline{\mathrm{OBJ}}^{\mathcal{R}}\big{(}\frac{\mathrm{CReg}(T)}{T}
\big{)}\geq U^{*}-\tfrac{4R}{\sqrt{G}}\sqrt{\frac{\mathrm{CReg}(T)}{T}}$.
- •
with a contextual no-swap-regret learning agent, the principal cannot obtain utility more than $\frac{1}{T}\mathbb{E}\big{[}\sum_{t=1}^{T}u(x^{t},a^{t})\big{]}\leq\overline{
\mathrm{OBJ}}^{\mathcal{D}}\big{(}\frac{\mathrm{CSReg}(T)}{T}\big{)}\leq U^{*}
+\tfrac{R}{G}\frac{\mathrm{CSReg}(T)}{T}$.

Providing the quantitative lower and upper bounds, the above results refine the result in
Guruganesh et al. () that the principal can obtain utility at least $U^{*}-o(1)$ against a no-regret learning agent and no more than $U^{*}+o(1)$ against a no-swap-regret agent.
This again demonstrates the versatility of our general framework.

###### Corollary 5.4 (Contract design (with bounded payment) with a learning agent) .

###### Corollary 5.5 (Contract design with a learning agent) .

## 6 Discussion

In summary, our work provides an explicit characterization of the principal’s achievable utility in generalized principal-agent problems with a contextual no-swap-regret learning agent. It is an asymmetric range $\big{[}U^{*}-O(\sqrt{\frac{\mathrm{CSReg}(T)}{T}}),U^{*}+O(\frac{\mathrm{CSReg
}(T)}{T})\big{]}$. We show that this conclusion holds in all generalized principal-agent problems where the agent does not have private information, in particular including Bayesian persuasion where the principal is privately informed.
As we mentioned in the Introduction, the upper bound $U^{*}+O(\frac{\mathrm{CSReg}(T)}{T})$ does not hold when the agent has private information or does certain types of no-regret but not no-swap-regret learning. Deriving the exact upper bound in the latter cases is an interesting direction for future work.

Other directions for future work include, for example, relaxing the assumption that the principal has perfect knowledge of the environment – what if both principal and agent are learning players? And what if the environment is non-stationary, like a Markovian environment (Jain and Perchet, ) or an adversarial dynamic environment (Camara et al., )? In unknown or non-stationary environments, the benchmark $U^{*}$ needs to be redefined, and a joint design of both players’ learning algorithms might be interesting.

## Appendix A Details about Contextual No-(Swap-)Regret Algorithms: Proof of Proposition 2.1

Let $\mathcal{A}$ be an arbitrary no-regret (no-swap-regret) learning algorithm for a multi-armed bandit (MAB) problem with $|A|$ arms. There exist such algorithms with regret $O(\sqrt{T|A|\log|A|})$ (variants of Exp3 (Auer et al., )) and even $O(\sqrt{T|A|})$ (doubling trick + polyINF (Audibert and Bubeck, )) for any time horizon $T>0$. By swap-to-external regret reductions, they can be converted to multi-armed bandit algorithms with swap regret $O(\sqrt{T|A|^{3}\log|A|})$ (Blum and Mansour, ) and $O(|A|\sqrt{T})$ (Ito, ). We then convert $\mathcal{A}$ into a contextual no-regret (contextual no-swap-regret) algorithm, in the following way:

Figure: Algorithm 1 Convert any MAB algorithm to a contextual MAB algorithm

###### Proposition A.1 .

The contextual regret of Algorithm 1 is at most

$$ $\displaystyle\mathrm{CReg}(T)\leq\max\Big{\{}\sum_{s=1}^{|S|}\mathrm{Reg}(T_{s })~{}\Big{|}~{}T_{1}+\cdots+T_{|S|}=T\Big{\}},$ $$

where $\mathrm{Reg}(T_{s})$ is the regret of $\mathcal{A}$ for time horizon $T_{s}$.

The contextual swap-regret of Algorithm 1 is at most

$$ $\displaystyle\mathrm{CSReg}(T)\leq\max\Big{\{}\sum_{s=1}^{|S|}\mathrm{SReg}(T_ {s})~{}\Big{|}~{}T_{1}+\cdots+T_{|S|}=T\Big{\}},$ $$

where $\mathrm{SReg}(T_{s})$ is the swap-regret of $\mathcal{A}$ for time horizon $T_{s}$.

When plugging in $\mathrm{Reg}(T_{s})=O(\sqrt{|A|T_{s}})$, we obtain $\mathrm{CReg}(T)\leq O(\sqrt{|A||S|T})$.

When plugging in $\mathrm{SReg}(T_{s})=O(|A|\sqrt{T_{s}})$, we obtain
$\mathrm{CSReg}(T)\leq O(|A|\sqrt{|S|T})$.

###### Proof.

The contextual regret of Algorithm 1 is

$$ $\displaystyle\mathrm{CReg}(T)$ $\displaystyle=\max_{d:S\to A}\mathbb{E}\Big{[}\sum_{t=1}^{T}\big{(}v^{t}(d(s^{ t}))-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle=\max_{d:S\to A}\mathbb{E}\Big{[}\sum_{s=1}^{|S|}\sum_{t:s^{t}=s} \big{(}v^{t}(d(s))-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle\leq\sum_{s=1}^{|S|}\max_{a^{\prime}\in A}\mathbb{E}\Big{[}\sum_{ t:s^{t}=s}\big{(}v^{t}(a^{\prime})-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle\leq\sum_{s=1}^{|S|}\mathbb{E}_{T_{s}}\big{[}\mathrm{Reg}(T_{s}) \big{]}\quad\text{where $T_{s}$ is the number of rounds where $s^{t}=s$}$ $\displaystyle\leq\max\Big{\{}\sum_{s=1}^{|S|}\mathrm{Reg}(T_{s})~{}\Big{|}~{}T _{1}+\cdots+T_{|S|}=T\Big{\}}.$ $$

When $\mathrm{Reg}(T_{s})=O(\sqrt{|A|T_{s}})$, by Jensen’s inequality we obtain

$$ $\displaystyle\mathrm{CReg}(T)$ $\displaystyle\leq\sum_{s=1}^{|S|}O(\sqrt{|A|T_{s}})\leq O(\sqrt{|A|})\sqrt{|S| }\sqrt{\sum_{s=1}^{|S|}T_{s}}=O(\sqrt{|A||S|T}).$ $$

The argument for contextual swap-regret is similar:

$$ $\displaystyle\mathrm{CSReg}(T)$ $\displaystyle=\max_{d:S\times A\to A}\mathbb{E}\Big{[}\sum_{t=1}^{T}\big{(}v^{ t}(d(s^{t},a^{t}))-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle=\max_{d:S\times A\to A}\mathbb{E}\Big{[}\sum_{s=1}^{|S|}\sum_{t: s^{t}=s}\big{(}v^{t}(d(s,a^{t}))-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle\leq\sum_{s=1}^{|S|}\max_{d^{\prime}:A\to A}\mathbb{E}\Big{[}\sum _{t:s^{t}=s}\big{(}v^{t}(d^{\prime}(a^{t}))-v^{t}(a^{t})\big{)}\Big{]}$ $\displaystyle\leq\sum_{s=1}^{|S|}\mathbb{E}_{T_{s}}\big{[}\mathrm{SReg}(T_{s}) \big{]}\quad\text{where $T_{s}$ is the number of rounds where $s^{t}=s$}$ $\displaystyle\leq\max\Big{\{}\sum_{s=1}^{|S|}\mathrm{SReg}(T_{s})~{}\Big{|}~{} T_{1}+\cdots+T_{|S|}=T\Big{\}}.$ $$

When $\mathrm{SReg}(T_{s})=O(|A|\sqrt{T_{s}})$, by Jensen’s inequality we obtain

$$ $\displaystyle\mathrm{CSReg}(T)\leq\sum_{s=1}^{|S|}O(|A|\sqrt{T_{s}})\leq O(|A| )\sqrt{|S|}\sqrt{\sum_{s=1}^{|S|}T_{s}}=O(|A|\sqrt{|S|T}).$ $$

∎

###### Proposition A.1 .

###### Proof.

## Appendix B Missing Proofs from Section 3

### B.1 Proof of Example 3.1

Consider the quantal response model. Let $\gamma=\frac{\log(|A|\lambda)}{\lambda}$. Given signal $s$, with posterior $\mu_{s}$, we say an action $a\in A$ is *not* $\gamma$-optimal for posterior $\mu_{s}$ if

$$ $v(\mu_{s},a^{*}_{s})-v(\mu_{s},a)\geq\gamma$ $$

where $a^{*}_{s}$ is an optimal action for $\mu_{s}$. The probability that the receiver chooses not $\gamma$-optimal action $a$ is at most:

$$ $\displaystyle\frac{\exp(\lambda v(\mu_{s},a))}{\sum_{a\in A}\exp(\lambda v(\mu _{s},a))}\leq\frac{\exp(\lambda v(\mu_{s},a))}{\exp(\lambda v(\mu_{s},a^{*}_{s }))}$ $\displaystyle=\exp\Big{(}-\lambda\big{[}v(\mu_{s},a^{*}_{s})-v(\mu_{s},a)\big{ ]}\Big{)}$ $\displaystyle\leq\exp(-\lambda\gamma)=\frac{1}{|A|\lambda}.$ $$

By a union bound, the probability that the receiver chooses any not $\gamma$-approxiamtely optimal action is at most $\frac{1}{\lambda}$.
So, the expected loss of utility of the receiver due to not taking the optimal action is at most

$$ $\displaystyle(1-\frac{1}{\lambda})\cdot\gamma+\frac{1}{\lambda}\cdot 1\leq \frac{\log(|A|\lambda)+1}{\lambda}$ $$

This means that the quantal response strategy is a $\frac{\log(|A|\lambda)+1}{\lambda}$-best-responding randomized strategy.

Consider inaccurate belief. Given signal $s$, the receiver has belief $\mu_{s}^{\prime}$ with total variation distance $d_{\mathrm{TV}}(\mu_{s}^{\prime},\mu_{s})\leq\varepsilon$ to the true posterior $\mu_{s}$. For any action $a\in A$, the difference of expected utility of action $a$ under beliefs $\mu_{s}^{\prime}$ and $\mu_{s}$ is at most $\varepsilon$:

$$ $\displaystyle\big{|}\mathbb{E}_{\omega\sim\mu_{s}^{\prime}}[v(\omega,a)]- \mathbb{E}_{\omega\sim\mu_{s}}[v(\omega,a)]\big{|}\leq d_{\mathrm{TV}}(\mu_{s} ^{\prime},\mu_{s})\leq\varepsilon.$ $$

So, the optimal action for $\mu_{s}^{\prime}$ is a $2\varepsilon$-optimal action for $\mu_{s}$. This means that the receiver strategy is a deterministic $2\varepsilon$-best-responding strategy.

### B.2 Proof of Theorem 3.3

We prove this theorem for no-swap-regret learning algorithms. The argument for no-regret learning algorithms is analogous.

Fix the principal’s adaptive strategy $\sigma=(\sigma^{t})_{t=1}^{T}$ for the $T$ rounds, where each $\sigma^{t}$ is a mapping from the history $h^{t-1}=(s^{i},a^{i})_{i=1}^{t-1}$ (including past signals and actions) to a single-round strategy $\pi^{t}$ for round $t$. Given any function $\mathrm{CSReg}(T)$, let $\delta=\frac{\mathrm{CSReg}(T)}{2T}$. We construct the following algorithm $\mathcal{A}$ for the agent: at each round $t$, given history $h^{t-1}=(s^{i},a^{i})_{i=1}^{t-1}$,

- •
If the single-round strategy chosen by the principal at round $t$ is equal to $\pi^{t}=\sigma^{t}(h^{t-1})$, then the agent plays a strategy $\rho^{t}\in\operatorname*{arg\,min}_{\rho\in\mathcal{R}_{\delta}(\pi^{t})}U(
\pi^{t},\rho)$, namely, a randomized $\delta$-best-responding strategy that minimizes the principal’s utility.
- •
If the single-round strategy chosen by the principal at round $t$ is not equal to $\pi^{t}=\sigma^{t}(h^{t-1})$, then the agent switches to any existing contextual no-swap-regret algorithm with swap regret at most $\frac{\mathrm{CSReg}(T)}{2}$ (see Proposition 2.1 for examples of such algorithms).

We show that the agent’s algorithm has swap regret at most $\mathrm{CSReg}(T)$ no matter what strategy the principal uses:

- If the principal keeps using strategy $\sigma$, namely, at each round $t$ the principal uses single-round strategy $\pi^{t}=\sigma^{t}(h^{t-1})$, denoted by $\pi^{t}=\{(\pi^{t}_{s},x^{t}_{s})\}_{s\in S}$, then the agent will respond by strategy $\rho^{t}$. For any deviation function $d:S\times A\to A$, the expected regret of the agent not deviating according to $d$ in this round is

$$ $\displaystyle\mathbb{E}[v(x^{t},d(s^{t},a^{t}))-v(x^{t},a^{t})]=\mathbb{E}_{h^ {t-1}}\Big{[}\sum_{s\in S}\pi^{t}_{s}\sum_{a\in A}\rho^{t}(a|s)\Big{(}v(x^{t}_ {s},d(s,a))-v(x^{t}_{s},a)\Big{)}\Big{]}$ $\displaystyle=\mathbb{E}_{h^{t-1}}\Big{[}\sum_{s\in S}\pi^{t}_{s}\sum_{a\in A} \rho^{t}(a|s)v(x^{t}_{s},d(s,a))-\sum_{s\in S}\pi^{t}_{s}\sum_{a\in A}\rho^{t} (a|s)v(x^{t}_{s},a)\Big{]}$ $\displaystyle\leq\mathbb{E}_{h^{t-1}}\Big{[}\sum_{s\in S}\pi_{s}^{t}\max_{a\in A }v(x_{s}^{t},a)-\sum_{s\in S}\pi^{t}_{s}\sum_{a\in A}\rho^{t}(a|s)v(x^{t}_{s}, a)\Big{]}$ $\displaystyle=\mathbb{E}_{h^{t-1}}\Big{[}\sum_{s\in S}\pi_{s}^{t}\max_{a\in A} v(x_{s}^{t},a)-V(\pi^{t},\rho^{t})\Big{]}.$ $$

Since $\rho^{t}\in\mathcal{R}_{\delta}(\pi^{t})$, we have $V(\pi^{t},\rho^{t})\geq\sum_{s\in S}\pi_{s}^{t}\max_{a\in A}v(x_{s}^{t},a)-\delta$, so the above is

$$ $\displaystyle\leq\mathbb{E}_{h^{t-1}}\big{[}\delta\big{]}=\delta.$ $$

Summing over all $T$ rounds, we obtain:

$$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}[v(x^{t},d(s^{t},a^{t}))-v(x^{t},a^{t})] \leq T\delta=\frac{\mathrm{CSReg}(T)}{2}.$ $$

- If the principal does not play according to $\sigma$ in any round, then the agent will switch to an algorithm with swap regret at most $\frac{\mathrm{CSReg}(T)}{2}$, so the total swap regret of the agent is at most:

$$ $\displaystyle T\delta+\frac{\mathrm{CSReg}(T)}{2}\leq\mathrm{CSReg}(T),$ $$

which proves that the agent’s learning algorithm has swap regret at most $\mathrm{CSReg}(T)$.

The principal’s average utility, when the principal uses strategy $\sigma$ and the agent uses the above no-swap-regret algorithm, is

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}[u(x^{t},a^{t})]$ $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{h^{t-1}}\Big{[}\sum_{s\in S }\pi_{s}^{t}\sum_{a\in A}\rho^{t}(a|s)u(x_{s}^{t},a)\Big{]}$ $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{h^{t-1}}\Big{[}U(\pi^{t}, \rho^{t})\Big{]}$ $\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}_{h^{t-1}}\Big{[}\sup_{\pi }\min_{\rho\in\mathcal{R}_{\delta}(\pi)}U(\pi,\rho)\Big{]}\quad~{}~{}\text{ because $\rho^{t}\in\operatorname*{arg\,min}_{\rho\in\mathcal{R}_{\delta}(\pi^ {t})}U(\pi^{t},\rho)$}$ $\displaystyle=\sup_{\pi}\min_{\rho\in\mathcal{R}_{\delta}(\pi)}U(\pi,\rho)$ $\displaystyle=\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ $\displaystyle=\underline{\mathrm{OBJ}}^{\mathcal{R}}\Big{(}\frac{\mathrm{CSReg }(T)}{2T}\Big{)}.$ $$

## Appendix C Missing Proofs from Section 4

### C.1 Proof of Claim 4.1

If no $G>0$ satisfies the claim, then there must exist an $a_{0}\in A$ such that for all $x\in\mathcal{X}$, $v(a_{0},\mu)-v(a^{\prime},\mu)\leq 0$ for some $a^{\prime}\in A\setminus\{a_{0}\}$. Namely,

$$ $\max_{x\in\mathcal{X}}\min_{a^{\prime}\in A\setminus\{a_{0}\}}\big{\{}v(x,a_{0 })-v(x,a^{\prime})\big{\}}\leq 0.$ $$

Then, by the minimax theorem, we have

$$ $\min_{\alpha^{\prime}\in\Delta(A\setminus\{a_{0}\})}\max_{x\in\mathcal{X}}\big {\{}v(x,a_{0})-v(x,\alpha^{\prime})\big{\}}=\max_{x\in\mathcal{X}}\min_{a^{ \prime}\in A\setminus\{a_{0}\}}\big{\{}v(x,a_{0})-v(x,a^{\prime})\big{\}}\leq 0.$ $$

This means that $a_{0}$ is weakly dominated by some mixed action $\alpha^{\prime}\in\Delta(A\setminus\{a_{0}\})$, violating Assumption 4.1.

### C.2 Proof of Example 4.1

We use the probability $\mu\in[0,1]$ of the $\mathrm{Good}$ state to represent a belief (so the probability of $\mathrm{Bad}$ state is $1-\mu$).

First, the sender’s optimal utility when the receiver exactly best responds is $2\mu_{0}$:

$$ $\displaystyle U^{*}=2\mu_{0}.$ $$

This is achieved by decomposing the prior $\mu_{0}$ into two posteriors $\mu_{a}=\frac{1}{2}$ and $\mu_{b}=0$ with probability $2\mu_{0}$ and $1-2\mu_{0}$ respectively, with the receiver taking action $a$ under posterior $\mu_{a}$ and $b$ under $\mu_{b}$.

Then, consider any signaling scheme of the sender, $\pi=\{(\pi_{s},\mu_{s})\}_{s\in S}$, which is a decomposition of the prior $\mu_{0}$ into $|S|$ posteriors $\mu_{s}\in[0,1]$ such that $\sum_{s\in S}\pi_{s}\mu_{s}=\mu_{0}$. Let $\rho:S\to\Delta(A)$ be a randomized strategy of the receiver, where $\rho(a|s)$ (and $\rho(b|s)$) denotes the probability that the receiver takes action $a$ (and $b$) under signal $s$. The sender’s expected utility under $\pi$ and $\rho$ is:

$$ $U(\pi,\rho)=\sum_{s\in S}\pi_{s}\big{[}\rho(a|s)\cdot 1+\rho(b|s)\cdot 0\big{] }=\sum_{s\in S}\pi_{s}\rho(a|s).$ (14) $$

The receiver’s utility when taking action $a$ at posterior $\mu_{s}$ is $\mu_{s}\cdot 1+(1-\mu_{s})\cdot(-1)=2\mu_{s}-1$.
So, the receiver’s expected utility under $\pi$ and $\rho$ is

$$ $V(\pi,\rho)=\sum_{s\in S}\pi_{s}\big{[}\rho(a|s)\cdot(2\mu_{s}-1)+\rho(b|s) \cdot 0\big{]}=\sum_{s\in S}\pi_{s}\rho(a|s)(2\mu_{s}-1).$ (15) $$

Clearly, the receiver’s best response $\rho^{*}$ is to take action $a$ with certainty if and only if $\mu_{s}>\frac{1}{2}$, with expected utility

$$ $V(\pi,\rho^{*})=\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}(2\mu_{s}-1).$ (16) $$

To find $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)=\sup_{\pi}\min_{\rho\in\mathcal
{R}_{\delta}(\pi)}U(\pi,\rho)$, we fix any $\pi$ and solve the inner optimization problem (minimizing the sender’s utility) regarding $\rho$:

$$ $\displaystyle\min_{\rho}$ $\displaystyle U(\pi,\rho)=\sum_{s\in S}\pi_{s}\rho(a|s)$ s.t. $\displaystyle\rho\in\mathcal{R}_{\delta}(\pi)\quad\;\Longleftrightarrow\;\quad\delta$ $\displaystyle\geq V(\pi,\rho^{*})-V(\pi,\rho)$ $\displaystyle=\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}(2\mu_{s}-1)-\sum_{s\in S}\pi _{s}\rho(a|s)(2\mu_{s}-1).$ $$

Without loss of generality, we can assume that the solution $\rho$ satisfies $\rho(a|s)=0$ whenever $\mu_{s}\leq\frac{1}{2}$ (if $\rho(a|s)>0$ for some $\mu_{s}\leq\frac{1}{2}$, then making $\rho(a|s)$ to be 0 0 can decrease the objective $\sum_{s\in S}\pi_{s}\rho(a|s)$ while still satisfying the constraint). So, the optimization problem can be simplified to:

$$ $\displaystyle\min_{\rho}$ $\displaystyle U(\pi,\rho)=\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}\rho(a|s)$ s.t. $\displaystyle\delta\geq\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}(2\mu_{s}-1)-\sum_{s :\mu_{s}>\frac{1}{2}}\pi_{s}\rho(a|s)(2\mu_{s}-1)$ $\displaystyle\quad\quad=\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}(2\mu_{s}-1)(1-\rho (a|s)),$ $\displaystyle\rho(a|s)\in[0,1],~{}~{}~{}\forall s\in S:\mu_{s}>\tfrac{1}{2}.$ $$

We note that this is a fractional knapsack linear program, which has a greedy solution (e.g., (Korte and Vygen, )): sort the signals with $\mu_{s}>\frac{1}{2}$ in increasing order of $2\mu_{s}-1$ (equivalently, increasing order of $\mu_{s}$); label those signals by $s=1,\ldots,n$; find the first position $k$ for which $\sum_{s=1}^{k}\pi_{s}(2\mu_{s}-1)>\delta$:

$$ $k=\min\big{\{}j:\sum_{s=1}^{j}\pi_{s}(2\mu_{s}-1)>\delta\big{\}};$ $$

then, an optimal solution $\rho$ is given by:

$$ $\displaystyle\begin{cases}\rho(a|s)=0&\text{for }s=1,\ldots,k-1;\\ \rho(a|k)=1-\frac{\delta-\sum_{s=1}^{k-1}\pi_{s}(2\mu_{s}-1)}{\pi_{k}(2\mu_{k} -1)}&\text{for }s=k;\\ \rho(a|s)=1&\text{for }s=k+1,\ldots,n.\end{cases}$ $$

The objective value (sender’s expected utility) of the above solution $\rho$ is

$$ $\displaystyle U(\pi,\rho)$ $\displaystyle=\sum_{s:\mu_{s}>\frac{1}{2}}\pi_{s}\rho(a|s)$ $\displaystyle=\pi_{k}\Big{(}1-\frac{\delta-\sum_{s=1}^{k-1}\pi_{s}(2\mu_{s}-1) }{\pi_{k}(2\mu_{k}-1)}\Big{)}+\sum_{s=k+1}^{n}\pi_{s}$ $\displaystyle=\sum_{s=k}^{n}\pi_{s}-\frac{\delta}{2\mu_{k}-1}+\sum_{s=1}^{k-1} \frac{\pi_{s}(2\mu_{s}-1)}{2\mu_{k}-1}.$ $$

Since the signaling scheme $\pi$ must satisfy $\sum_{s\in S}\pi_{s}\mu_{s}=\mu_{0}$, we have

$$ $\displaystyle\mu_{0}=\sum_{s\in S}\pi_{s}\mu_{s}\geq\sum_{s=1}^{n}\pi_{s}\mu_{ s}=\sum_{s=1}^{k-1}\pi_{s}\mu_{s}+\sum_{s=k}^{n}\pi_{s}\mu_{s}\geq\sum_{s=1}^{ k-1}\pi_{s}\mu_{s}+\sum_{s=k}^{n}\pi_{s}\mu_{k}$ $\displaystyle\implies\quad\sum_{s=k}^{n}\pi_{s}\leq\frac{\mu_{0}-\sum_{s=1}^{k -1}\pi_{s}\mu_{s}}{\mu_{k}}.$ $$

So,

$$ $\displaystyle U(\pi,\rho)$ $\displaystyle\leq\frac{\mu_{0}-\sum_{s=1}^{k-1}\pi_{s}\mu_{s}}{\mu_{k}}-\frac{ \delta}{2\mu_{k}-1}+\sum_{s=1}^{k-1}\frac{\pi_{s}(2\mu_{s}-1)}{2\mu_{k}-1}$ $\displaystyle=\frac{\mu_{0}}{\mu_{k}}-\frac{\delta}{2\mu_{k}-1}+\sum_{s=1}^{k- 1}\pi_{s}\Big{(}\frac{2\mu_{s}-1}{2\mu_{k}-1}-\frac{\mu_{s}}{\mu_{k}}\Big{)}.$ $$

Since $\frac{2\mu_{s}-1}{2\mu_{k}-1}-\frac{\mu_{s}}{\mu_{k}}=\frac{\mu_{s}-\mu_{k}}{(
2\mu_{s}-1)\mu_{k}}\leq 0$ for any $s\leq k-1$, we get

$$ $\displaystyle U(\pi,\rho)$ $\displaystyle\leq\frac{\mu_{0}}{\mu_{k}}-\frac{\delta}{2\mu_{k}-1}=f(\mu_{k}).$ $$

We find the maximal value of $f(\mu_{k})=\frac{\mu_{0}}{\mu_{k}}-\frac{\delta}{2\mu_{k}-1}$. Take its derivative:

$$ $\displaystyle f^{\prime}(\mu_{k})$ $\displaystyle=-\frac{\mu_{0}}{\mu_{k}^{2}}+\frac{2\delta}{(2\mu_{k}-1)^{2}}= \frac{\big{[}(\sqrt{2\delta}+2\sqrt{\mu_{0}})\mu_{k}-\sqrt{\mu}_{0}\big{]} \cdot\big{[}(\sqrt{2\delta}-2\sqrt{\mu_{0}})\mu_{k}+\sqrt{\mu}_{0}\big{]}}{\mu _{k}^{2}(2\mu_{k}-1)^{2}},$ $$

which has two roots $\frac{\sqrt{\mu}_{0}}{\sqrt{2\delta}+2\sqrt{\mu_{0}}}<\frac{1}{2}$ and $\frac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta}}\in(\frac{1}{2},1)$ when $0<\delta<\frac{\mu_{0}}{2}$. So, $f(x)$ is increasing in $[\frac{1}{2},\frac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta}})$ and decreasing in $(\frac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta}},1]$. Since $\mu_{k}>\frac{1}{2}$, $f(\mu_{k})$ is maximized at $\mu_{k}=\frac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta}}$. This implies

$$ $\displaystyle U(\pi,\rho)$ $\displaystyle\leq f\big{(}\tfrac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta }}\big{)}=\frac{\mu_{0}}{\sqrt{\mu}_{0}}(2\sqrt{\mu}_{0}-\sqrt{2\delta})-\frac {\delta}{2\frac{\sqrt{\mu}_{0}}{2\sqrt{\mu_{0}}-\sqrt{2\delta}}-1}=2\mu_{0}-2 \sqrt{2\mu_{0}\delta}+\delta.$ $$

This holds for any $\pi$.
So, $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)=\sup_{\pi}\min_{\rho\in\mathcal
{R}_{\delta}(\pi)}U(\pi,\rho)\leq U^{*}-2\sqrt{2\mu_{0}\delta}+\delta=U^{*}-
\Omega(\sqrt{\delta})$.

### C.3 Proof of Theorems 4.2 and 4.3

#### Lower bounds on OBJ ¯ 𝒟 ⁢ ( δ ) superscript ¯ OBJ 𝒟 𝛿 \underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta) under¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_D end_POSTSUPERSCRIPT ( italic_δ ) and upper bounds on OBJ ¯ ℛ ⁢ ( δ ) superscript ¯ OBJ ℛ 𝛿 \overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta) over¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_R end_POSTSUPERSCRIPT ( italic_δ ) .

First, we prove the lower bounds on $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$ and the upper bounds on $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ in Theorems 4.2 and 4.3, given by the following two lemmas:

###### Lemma C.1 .

In an unconstrained generalized principal-agent problem, $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\geq U^{*}-\mathrm{diam}(
\mathcal{X})L\tfrac{\delta}{G}$.

With constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$, $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\geq U^{*}-\big{(}\mathrm{diam}(
\mathcal{X})L+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},
\partial\mathcal{X})}\big{)}\tfrac{\delta}{G}$.

###### Lemma C.2 .

In an unconstrained generalized principal-agent problem, $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\leq U^{*}+\mathrm{diam}(\mathcal
{X})L\tfrac{\delta}{G}$.

With constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$, $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\leq U^{*}+\big{(}\mathrm{diam}(
\mathcal{X})L+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},
\partial\mathcal{X})}\big{)}\tfrac{\delta}{G}$.

The proofs of Lemmas C.1 and C.2 are similar and given in Appendix C.4 and C.5.
The main idea to prove Lemma C.2 is the following. Let $(\pi,\rho)$ be any pair of principal’s strategy and agent’s $\delta$-best-responding strategy. We perturb the principal’s strategy $\pi$ slightly to be a strategy $\pi^{\prime}$ for which $\rho$ is *exactly* best-responding (such a perturbation is possible due to Assumption 4.1). Since $\rho$ is best-responding to $\pi^{\prime}$, the pair $(\pi^{\prime},\rho)$ cannot give the principal a higher utility than $U^{*}$ (which is the optimal principal utility under the best-response model). This means that the original pair $(\pi,\rho)$ cannot give the principal a utility much higher than $U^{*}$, implying an upper bound on $\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$.

###### Lemma C.1 .

###### Lemma C.2 .

#### Upper bounds on OBJ ¯ ℛ ⁢ ( δ ) superscript ¯ OBJ ℛ 𝛿 \overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta) over¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_R end_POSTSUPERSCRIPT ( italic_δ ) imply upper bounds on OBJ ¯ 𝒟 ⁢ ( δ ) superscript ¯ OBJ 𝒟 𝛿 \overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta) over¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_D end_POSTSUPERSCRIPT ( italic_δ ) .

Then, because $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\leq\overline{\mathrm{OBJ}}^{
\mathcal{R}}(\delta)$, we immediately obtain the upper bounds on $\overline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$ in the two theorems.

#### Lower bounds for OBJ ¯ 𝒟 ⁢ ( δ ) superscript ¯ OBJ 𝒟 𝛿 \underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta) under¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_D end_POSTSUPERSCRIPT ( italic_δ ) imply lower bounds for OBJ ¯ ℛ ⁢ ( δ ) superscript ¯ OBJ ℛ 𝛿 \underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta) under¯ start_ARG roman_OBJ end_ARG start_POSTSUPERSCRIPT caligraphic_R end_POSTSUPERSCRIPT ( italic_δ )

Finally, we show that the lower bounds for $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)$ imply the lower bounds for $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$, using the following lemma:

###### Lemma C.3 .

For any $\delta\geq 0,\Delta>0$, $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\geq\underline{\mathrm{OBJ}}^{
\mathcal{D}}(\Delta)-\tfrac{2B\delta}{\Delta}$.

The proof of this lemma is in Appendix C.6.

Using Lemma C.3 with $\Delta=\sqrt{\frac{2BG\delta}{\mathrm{diam}(\mathcal{X})L}}$ and the lower bound for $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\Delta)$ in Lemma C.1 for the unconstrained case, we obtain:

$$ $\displaystyle\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\geq\underline{ \mathrm{OBJ}}^{\mathcal{D}}(\Delta)-\tfrac{2B\delta}{\Delta}$ $\displaystyle\geq U^{*}-\mathrm{diam}(\mathcal{X})L\tfrac{\Delta}{G}-\tfrac{2B \delta}{\Delta}=U^{*}-2\sqrt{\tfrac{2BL}{G}\mathrm{diam}(\mathcal{X})\delta},$ $$

which gives the lower bound for $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ in Theorem 4.2.

Using Lemma C.3 with $\Delta=\sqrt{\frac{2BG\delta}{L\mathrm{diam}(\mathcal{X})+2B\tfrac{\mathrm{
diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}}}$ and the lower bound for $\underline{\mathrm{OBJ}}^{\mathcal{D}}(\Delta)$ in Lemma C.1 for the constrained case, we obtain:

$$ $\displaystyle\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\geq\underline{ \mathrm{OBJ}}^{\mathcal{D}}(\Delta)-\tfrac{2B\delta}{\Delta}$ $\displaystyle\geq U^{*}-\big{(}\mathrm{diam}(\mathcal{X})L+2B\tfrac{\mathrm{ diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\big{)} \tfrac{\Delta}{G}-\tfrac{2B\delta}{\Delta}$ $\displaystyle=U^{*}-2\sqrt{\tfrac{2B}{G}\big{(}\mathrm{diam}(\mathcal{X})L+2B \tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{ X})}\big{)}\delta}.$ $$

This proves the lower bound for $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)$ in Theorem 4.3.

###### Lemma C.3 .

### C.4 Proof of Lemma C.1

Let $(\pi,\rho)$ be a pair of principal strategy and agent strategy that achieves the optimal principal utility with an exactly-best-responding agent, namely, $U(\pi,\rho)=U^{*}$.
Without loss of generality $\rho$ can be assumed to be deterministic, $\rho:S\to A$. The strategy $\pi$ consists of pairs $\{(\pi_{s},x_{s})\}_{s\in S}$ that satisfy

$$ $\sum_{s\in S}\pi_{s}x_{s}=:\mu_{0}\in\mathcal{C},$ (17) $$

and the action $a=\rho(s)$ is optimal for the agent with respect to $x_{s}$. We will construct another principal strategy $\pi^{\prime}$ such that, even if the agent chooses the worst $\delta$-best-responding strategy to $\pi^{\prime}$, the principal can still obtain utility arbitrarily close to $U^{*}-\big{(}L\mathrm{diam}(\mathcal{X};\ell_{1})+2B\tfrac{\mathrm{diam}(
\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\big{)}\tfrac{
\delta}{G}$.

To construct $\pi^{\prime}$ we do the following: For each signal $s\in S$, with corresponding action $a=\rho(s)$, by Claim 4.1 there exists $y_{a}\in\mathcal{X}$ such that $v(y_{a},a)-v(y_{a},a^{\prime})\geq G$ for any $a^{\prime}\neq a$. Let $\theta=\frac{\delta}{G}+\varepsilon\in[0,1]$ for arbitrarily small $\varepsilon>0$, and let $\tilde{x}_{s}$ be the convex combination of $x_{s}$ and $y_{\rho(s)}$ with weights $1-\theta,\theta$:

$$ $\tilde{x}_{s}=(1-\theta)x_{s}+\theta y_{\rho(s)}.$ (18) $$

We note that $a=\rho(s)$ is the agent’s optimal action for $\tilde{x}_{s}$ and moreover it is better than any other action $a^{\prime}\neq a$ by more than $\delta$:

$$ $\displaystyle v(\tilde{x}_{s},a)-v(\tilde{x}_{s},a^{\prime})$ $\displaystyle=(1-\theta)\big{[}\underbrace{v(x_{s},a)~{}-~{}v(x_{s},a^{\prime} )}_{\geq 0\text{ because $a=\rho(s)$ is optimal for $x_{s}$}}\big{]}~{}+~{} \theta\big{[}\underbrace{v(y_{a},a)-v(y_{a},a^{\prime})}_{\geq G\text{ by our choice of $y_{a}$}}\big{]}$ $\displaystyle\geq 0+\theta G>\tfrac{\delta}{G}G=\delta.$ (19) $$

Let $\mu^{\prime}$ be the convex combination of $\{\tilde{x}_{s}\}_{s\in S}$ with weights $\{\pi_{s}\}_{s\in S}$:

$$ $\mu^{\prime}=\sum_{s\in S}\pi_{s}\tilde{x}_{s}.$ (20) $$

Note that $\mu^{\prime}$ might not satisfy the constraint $\mu^{\prime}\in\mathcal{C}$. So, we want to find another vector $z\in\mathcal{X}$ and a coefficient $\eta\in[0,1]$ such that

$$ $(1-\eta)\mu^{\prime}+\eta z\in\mathcal{C}.$ (21) $$

(If $\mu^{\prime}$ already satisfies $\mu^{\prime}\in\mathcal{C}$, then let $\eta=0$.)
To do this, we consider the ray starting from $\mu^{\prime}$ pointing towards $\mu_{0}$: $\{\mu^{\prime}+t(\mu_{0}-\mu^{\prime})\mid t\geq 0\}$. Let $z$ be the intersection of the ray with the boundary of $\mathcal{X}$:

$$ $\displaystyle z=\mu^{\prime}+t^{*}(\mu_{0}-\mu^{\prime}),\quad\quad t^{*}= \operatorname*{arg\,max}\{t\geq 0\mid\mu^{\prime}+t(\mu_{0}-\mu^{\prime})\in \mathcal{X}\}.$ $$

Then, rearranging $z=\mu^{\prime}+t^{*}(\mu_{0}-\mu^{\prime})$, we get

$$ $\displaystyle\tfrac{1}{t^{*}}(z-\mu^{\prime})=\mu_{0}-\mu^{\prime}\quad\; \Longleftrightarrow\;\quad(1-\tfrac{1}{t^{*}})\mu^{\prime}+\tfrac{1}{t^{*}}z= \mu_{0}\in\mathcal{C},$ $$

which satisfies (21) with $\eta=\frac{1}{t^{*}}$. We then give an upper bound on $\eta=\frac{1}{t*}$:

###### Claim C.4 .

$\eta=\tfrac{1}{t^{*}}\leq\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(
\mathcal{C},\partial\mathcal{X})}\theta$.

###### Proof.

On the one hand,

$$ $\displaystyle\|\mu_{0}-\mu^{\prime}\|$ $\displaystyle=\big{\|}\sum_{s\in S}\pi_{s}x_{s}-\sum_{s\in S}\pi_{s}\tilde{x}_ {s}\big{\|}=\big{\|}\sum_{s\in S}\pi_{s}\theta(y_{\rho(s)}-x_{s})\big{\|}$ $\displaystyle\leq\theta\sum_{s\in S}\pi_{s}\big{\|}y_{\rho(s)}-x_{s}\big{\|} \leq\theta\sum_{s\in S}\pi_{s}\cdot\mathrm{diam}(\mathcal{X})=\theta\cdot \mathrm{diam}(\mathcal{X}).$ $$

On the other hand, because $z-\mu^{\prime}$ and $\mu_{0}-\mu^{\prime}$ are in the same direction, we have

$$ $\displaystyle\|z-\mu^{\prime}\|=\|z-\mu_{0}\|+\|\mu_{0}-\mu^{\prime}\|\geq\|z- \mu_{0}\|\geq\mathrm{dist}(\mathcal{C},\partial\mathcal{X})$ $$

because $\mu_{0}$ is in $\mathcal{C}$ and $z$ is on the boundary of $\mathcal{X}$. Therefore, $\eta=\tfrac{1}{t^{*}}=\tfrac{\|\mu_{0}-\mu^{\prime}\|}{\|z-\mu^{\prime}\|}\leq
\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{
X})}\theta$.
∎

The convex combinations (21) (20) define a new principal strategy $\pi^{\prime}$ with $|S|+1$ signals, consisting of $\tilde{x}_{s}$ with probability $(1-\eta)\pi_{s}$ and $z$ with probability $\eta$, satisfying $\sum_{s\in S}(1-\eta)\pi_{s}\tilde{x}_{s}+\eta z=\mu_{0}\in\mathcal{C}$.
Consider the agent’s worst (for the principal) $\delta$-best-responding strategies $\rho^{\prime}$ to $\pi^{\prime}$:

$$ $\rho^{\prime}\in\operatorname*{arg\,min}_{\rho\in\mathcal{D}_{\delta}(\pi^{ \prime})}U(\pi^{\prime},\rho).$ $$

We note that $\rho^{\prime}(\tilde{x}_{s})$ must be equal to $\rho(s)$ for each $s\in S$. This is because $a=\rho(s)$ is strictly better than any other action $a^{\prime}\neq a$ by a margin of $\delta$ (19), so $a$ is the only $\delta$-optimal action for $\tilde{x}_{s}$.

Then, the principal’s expected utility under $\pi^{\prime}$ and $\rho^{\prime}$ is

$$ $\displaystyle U(\pi^{\prime},\rho^{\prime})$ $\displaystyle\stackrel{{\scriptstyle\eqref{eq:convex-combination-prior-2}, \eqref{eq:convex-combination-mu'-2}}}{{=}}(1-\eta)\sum_{s\in S}\pi_{s}u(\tilde {x}_{s},\rho^{\prime}(\tilde{x}_{s}))~{}+~{}\eta u(z,\rho^{\prime}(z))$ $\displaystyle\geq(1-\eta)\sum_{s\in S}\pi_{s}u(\tilde{x}_{s},\rho(s))~{}-~{}\eta B$ $\displaystyle\geq(1-\eta)\sum_{s\in S}\pi_{s}\Big{(}u(x_{s},\rho(s))-L \underbrace{\|\tilde{x}_{s}-x_{s}\|}_{=\|\theta(y_{\rho(s)}-x_{s})\|\leq\theta \mathrm{diam}(\mathcal{X})}\Big{)}~{}-~{}\eta B$ $\displaystyle\geq(1-\eta)U(\pi,\rho)-L\theta\mathrm{diam}(\mathcal{X})-\eta B$ $\displaystyle\geq U(\pi,\rho)-L\theta\mathrm{diam}(\mathcal{X})-2\eta B$ by Claim C.4 $\displaystyle\geq U(\pi,\rho)-L\theta\mathrm{diam}(\mathcal{X})-2B\tfrac{ \mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\theta$ $\displaystyle=U(\pi,\rho)-\big{(}L\mathrm{diam}(\mathcal{X})+2B\tfrac{\mathrm{ diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\big{)}( \tfrac{\delta}{G}+\varepsilon)$ $\displaystyle=U^{*}-\big{(}L\mathrm{diam}(\mathcal{X})+2B\tfrac{\mathrm{diam}( \mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})}\big{)}\tfrac{ \delta}{G}-O(\varepsilon).$ $$

So, we conclude that

$$ $\displaystyle\underline{\mathrm{OBJ}}^{\mathcal{D}}(\delta)\,=\,\sup_{\pi}\min _{\rho\in\mathcal{D}_{\delta}(\pi)}U(\pi,\rho)$ $\displaystyle\,\geq\,\min_{\rho\in\mathcal{D}_{\delta}(\pi^{\prime})}U(\pi^{ \prime},\rho)$ $\displaystyle\,=\,U(\pi^{\prime},\rho^{\prime})\,\geq\,U^{*}-\big{(}L\mathrm{ diam}(\mathcal{X})+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal {C},\partial\mathcal{X})}\big{)}\tfrac{\delta}{G}-O(\varepsilon).$ $$

Letting $\varepsilon\to 0$ finishes the proof for the case with the constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$.

The case without $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$ is proved by letting $\eta=0$ in the above argument.

###### Claim C.4 .

###### Proof.

### C.5 Proof of Lemma C.2

Let $\pi$ be a principal strategy and $\rho\in\mathcal{R}_{\delta}(\pi)$ be a $\delta$-best-responding randomized strategy of the agent. The principal strategy $\pi$ consists of pairs $\{(\pi_{s},x_{s})\}_{s\in S}$ with

$$ $\sum_{s\in S}\pi_{s}x_{s}=:\mu_{0}\in\mathcal{C}.$ (22) $$

At signal $s$, the agent takes action $a$ with probability $\rho(a|s)$.
Let $\delta_{s,a}$ be the “suboptimality” of action $a$ with respect to $x_{s}$:

$$ $\delta_{s,a}=\max_{a^{\prime}\in A}\big{\{}v(x_{s},a^{\prime})-v(x_{s},a)\big{ \}}.$ (23) $$

By Claim 4.1, for action $a$ there exists $y_{a}\in\mathcal{X}$ such that $v(y_{a},a)-v(y_{a},a^{\prime})\geq G$ for any $a^{\prime}\neq a$. Let $\theta_{s,a}=\frac{\delta_{s,a}}{G+\delta_{s,a}}\in[0,1]$ and let $\tilde{x}_{s,a}$ be the convex combination of $x_{s}$ and $y_{a}$ with weights $1-\theta_{s,a}$ and $\theta_{s,a}$:

$$ $\tilde{x}_{s,a}=(1-\theta_{s,a})x_{s}+\theta_{s,a}y_{a}.$ (24) $$

###### Claim C.5 .

We have two useful claims regarding $\tilde{x}_{s,a}$ and $\theta_{s,a}$:

- (1)
$a$ is an optimal action for the agent with respect to $\tilde{x}_{s,a}$: $v(\tilde{x}_{s,a},a)-v(\tilde{x}_{s,a},a^{\prime})\geq 0,\forall a^{\prime}\in
A$.
- (2)
$\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\theta_{s,a}\leq\frac{\delta}{G}$.

###### Proof.

(1) For any $a^{\prime}\neq a$, by the definition of $\tilde{x}_{s,a}$ and $\theta_{s,a}$,

$$ $\displaystyle v(\tilde{x}_{s,a},a)-v(\tilde{x}_{s,a},a^{\prime})$ $\displaystyle~{}=~{}(1-\theta_{s,a})\big{[}v(x_{s},a)-v(x_{s},a^{\prime})\big{ ]}~{}+~{}\theta_{s,a}\big{[}v(y_{a},a)-v(y_{a},a^{\prime})\big{]}$ $\displaystyle~{}\geq~{}(1-\theta_{s,a})(-\delta_{s,a})~{}+~{}\theta_{s,a}G~{}= ~{}\tfrac{G}{G+\delta_{s,a}}(-\delta_{s,a})+\tfrac{\delta_{s,a}}{G+\delta_{s,a }}G~{}=~{}0.$ $$

(2) By the condition that $\rho$ is a $\delta$-best-response to $\pi$, we have

$$ $\displaystyle\delta~{}$ $\displaystyle\geq~{}\max_{\rho^{*}:S\to A}V(\pi,\rho^{*})-V(\pi,\rho)~{}=~{} \sum_{s\in S}\pi_{s}\Big{(}\max_{a^{\prime}\in A}\big{\{}v(x_{s},a^{\prime}) \big{\}}-\sum_{a\in A}\rho(a|s)v(x_{s},a)\Big{)}$ $\displaystyle=~{}\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\max_{a^{\prime}\in A }\big{\{}v(x_{s},a^{\prime})-v(x_{s},a)\big{\}}~{}=~{}\sum_{s\in S}\sum_{a\in A }\pi_{s}\rho(a|s)\delta_{s,a}.$ $$

So, $\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\theta_{s,a}=\sum_{s\in S}\sum_{a\in
A
}\pi_{s}\rho(a|s)\frac{\delta_{s,a}}{G+\delta_{s,a}}\leq\sum_{s\in S}\sum_{a
\in A}\pi_{s}\rho(a|s)\frac{\delta_{s,a}}{G}\leq\frac{\delta}{G}$.
∎

We let $\mu^{\prime}$ be the convex combination of $\{\tilde{x}_{s,a}\}_{s,a\in S\times A}$ with weights $\{\pi_{s}\rho(a|s)\}_{s,a\in S\times A}$:

$$ $\mu^{\prime}=\sum_{s,a\in S\times A}\pi_{s}\rho(a|s)\tilde{x}_{s,a}.$ (25) $$

Note that $\mu^{\prime}$ might not satisfy the constraint $\mu^{\prime}\in\mathcal{C}$. So, we want to find another vector $z\in\mathcal{X}$ and a coefficient $\eta\in[0,1]$ such that

$$ $(1-\eta)\mu^{\prime}+\eta z\in\mathcal{C}.$ (26) $$

(If $\mu^{\prime}$ already satisfies $\mu^{\prime}\in\mathcal{C}$, then let $\eta=0$.)
To do this, we consider the ray pointing from $\mu^{\prime}$ to $\mu_{0}$: $\{\mu^{\prime}+t(\mu_{0}-\mu^{\prime})\mid t\geq 0\}$. Let $z$ be the intersection of the ray with the boundary of $\mathcal{X}$:

$$ $\displaystyle z=\mu^{\prime}+t^{*}(\mu_{0}-\mu^{\prime}),\quad\quad t^{*}= \operatorname*{arg\,max}\{t\geq 0\mid\mu^{\prime}+t(\mu_{0}-\mu^{\prime})\in \mathcal{X}\}.$ $$

Then, rearranging $z=\mu^{\prime}+t^{*}(\mu_{0}-\mu^{\prime})$, we get

$$ $\displaystyle\tfrac{1}{t^{*}}(z-\mu^{\prime})=\mu_{0}-\mu^{\prime}\quad\; \Longleftrightarrow\;\quad(1-\tfrac{1}{t^{*}})\mu^{\prime}+\tfrac{1}{t^{*}}z= \mu_{0}\in\mathcal{C},$ $$

which satisfies (26) with $\eta=\frac{1}{t^{*}}$. We then give an upper bound on $\eta=\frac{1}{t*}$:

###### Claim C.6 .

$\eta=\tfrac{1}{t^{*}}\leq\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(
\mathcal{C},\partial\mathcal{X})}\tfrac{\delta}{G}$.

###### Proof.

On the one hand,

$$ $\displaystyle\|\mu_{0}-\mu^{\prime}\|$ $\displaystyle=\big{\|}\sum_{s\in S}\pi_{s}x_{s}-\sum_{s\in S}\sum_{a\in A}\pi_ {s}\rho(a|s)\tilde{x}_{s,a}\big{\|}=\big{\|}\sum_{s\in S}\sum_{a\in A}\pi_{s} \rho(a|s)\theta_{s,a}(y_{a}-x_{s})\big{\|}$ $\displaystyle\leq\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\theta_{s,a}\big{\| }y_{a}-x_{s}\big{\|}\leq\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\theta_{s,a} \mathrm{diam}(\mathcal{X})\stackrel{{\scriptstyle\text{Claim~{}\ref{claim:two- claims}}}}{{\leq}}\mathrm{diam}(\mathcal{X})\tfrac{\delta}{G}.$ $$

On the other hand, because $z-\mu^{\prime}$ and $\mu_{0}-\mu^{\prime}$ are in the same direction, we have

$$ $\displaystyle\|z-\mu^{\prime}\|=\|z-\mu_{0}\|+\|\mu_{0}-\mu^{\prime}\|\geq\|z- \mu_{0}\|\geq\mathrm{dist}(\mathcal{C},\partial\mathcal{X})$ $$

because $\mu_{0}$ is in $\mathcal{C}$ and $z$ is on the boundary of $\mathcal{X}$. Therefore, $\eta=\tfrac{1}{t^{*}}=\tfrac{\|\mu_{0}-\mu^{\prime}\|}{\|z-\mu^{\prime}\|}\leq
\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{
X})}\tfrac{\delta}{G}$.

∎

The convex combinations (26) (25) define a new principal strategy $\pi^{\prime}$ (with $|S|\times|A|+1$ signals) consisting of $\tilde{x}_{s,a}$ with probability $(1-\eta)\pi_{s}\rho(a|s)$ and $z$ with probability $\eta$. Consider the following deterministic agent strategy $\rho^{\prime}$ in response to $\pi^{\prime}$: for $\tilde{x}_{s,a}$, take action $\rho^{\prime}(\tilde{x}_{s,a})=a$; for $z$, take any action that is optimal for $z$. We note that $\rho^{\prime}$ is a best-response to $\pi^{\prime}$, $\rho^{\prime}\in\mathcal{R}_{0}(\pi^{\prime})$,
because, according to Claim C.5, $a$ is an optimal action with respect to $\tilde{x}_{s,a}$.

Then, consider the principal’s utility under $\pi^{\prime}$ and $\rho^{\prime}$:

$$ $\displaystyle U(\pi^{\prime},\rho^{\prime})$ $\displaystyle\stackrel{{\scriptstyle\eqref{eq:convex-combination-prior},\eqref {eq:convex-combination-mu'}}}{{=}}(1-\eta)\sum_{s\in S}\sum_{a\in A}\pi_{s} \rho(a|s)u(\tilde{x}_{s,a},\rho^{\prime}(\tilde{x}_{s,a}))~{}+~{}\eta u(z,\rho ^{\prime}(z))$ $\displaystyle\geq~{}(1-\eta)\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)u(\tilde {x}_{s,a},a)~{}-~{}\eta B$ $\displaystyle\geq~{}(1-\eta)\sum_{s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\Big{(}u (x_{s},a)-L\underbrace{\|\tilde{x}_{s}-x_{s}\|}_{=\|\theta_{s,a}(y_{a}-x_{s}) \|\leq\theta_{s,a}\mathrm{diam}(\mathcal{X})}\Big{)}~{}-~{}\eta B$ $\displaystyle\geq~{}(1-\eta)U(\pi,\rho)~{}-~{}L\mathrm{diam}(\mathcal{X})\sum_ {s\in S}\sum_{a\in A}\pi_{s}\rho(a|s)\theta_{s,a}~{}-~{}\eta B$ (Claim C.5 ) $\displaystyle\geq~{}U(\pi,\rho)-L\mathrm{diam}(\mathcal{X})\tfrac{\delta}{G}-2\eta B$ (Claim C.6 ) $\displaystyle\geq~{}U(\pi,\rho)-\big{(}L\mathrm{diam}(\mathcal{X})+2B\tfrac{ \mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})} \big{)}\tfrac{\delta}{G}.$ $$

Rearranging, $U(\pi,\rho)\leq U(\pi^{\prime},\rho^{\prime})+\big{(}L\mathrm{diam}(\mathcal{X
})+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial
\mathcal{X})}\big{)}\tfrac{\delta}{G}$. Note that this argument holds for any pair $(\pi,\rho)$ that satisfies $\rho\in\mathcal{R}_{\delta}(\pi)$. And recall that $\rho^{\prime}\in\mathcal{R}_{0}(\pi^{\prime})$. So, we conclude that

$$ $\displaystyle\overline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)~{}=~{}\max_{\pi} \max_{\rho\in\mathcal{R}_{\delta}(\pi)}U(\pi,\rho)$ $\displaystyle~{}\leq~{}\max_{\pi^{\prime}}\max_{\rho^{\prime}\in\mathcal{R}_{0 }(\pi)}U(\pi^{\prime},\rho^{\prime})+\big{(}L\mathrm{diam}(\mathcal{X};\ell_{1 })+2B\tfrac{\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial \mathcal{X})}\big{)}\tfrac{\delta}{G}$ $\displaystyle~{}=~{}U^{*}+\big{(}L\mathrm{diam}(\mathcal{X};\ell_{1})+2B\tfrac {\mathrm{diam}(\mathcal{X})}{\mathrm{dist}(\mathcal{C},\partial\mathcal{X})} \big{)}\tfrac{\delta}{G}.$ $$

This proves the case with the constraint $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$.

The case without $\sum_{s\in S}\pi_{s}x_{s}\in\mathcal{C}$ is proved by letting $\eta=0$ in the above argument.

###### Claim C.5 .

###### Proof.

###### Claim C.6 .

###### Proof.

### C.6 Proof of Lemma C.3

Let $A_{\Delta}(x)=\big{\{}a\in A\mid v(x,a)\geq v(x,a^{\prime})-\Delta,\forall a^{
\prime}\in A\big{\}}$ be the set of $\Delta$-optimal actions of the agent in response to principal decision $x\in\mathcal{X}$.
The proof of Lemma C.3 uses another lemma that relates the principal utility under a randomized $\delta$-best-responding agent strategy $\rho\in\mathcal{R}_{\delta}(\pi)$ and that under an agent strategy $\rho^{\prime}$ that only randomizes over $A_{\Delta}(x_{s})$.

###### Lemma C.7 .

Let $\pi=\{(\pi_{s},x_{s})\}_{s\in S}$ be a principal strategy and $\rho\in\mathcal{R}_{\delta}(\pi)$ be a randomized $\delta$-best-response to $\pi$. For any $\Delta>0$, there exists an agent strategy $\rho^{\prime}:s\mapsto\Delta(A_{\Delta}(x_{s}))$ that randomizes over $\Delta$-optimal actions only for each $x_{s}$, such that the principal’s utility under $\rho^{\prime}$ and $\rho$ satisfies: $\big{|}U(\pi,\rho^{\prime})-U(\pi,\rho)\big{|}\leq\frac{2B\delta}{\Delta}$.

###### Proof.

Let $a^{*}_{s}=\max_{a\in A}v(x_{s},a)$ be the agent’s optimal action for $x_{s}$. Let $\overline{A_{\Delta}(x_{s})}=A\setminus A_{\Delta}(x_{s})$ be the set of actions that are not $\Delta$-optimal for $x_{s}$.
By the definition that $\rho\in\mathcal{R}_{\delta}(\pi)$ is a $\delta$-best-response to $\pi$, we have

$$ $\displaystyle\quad\delta$ $\displaystyle\geq\sum_{s\in S}\pi_{s}\Big{[}v(x_{s},a^{*}_{s})-\sum_{a\in A} \rho(a|s)v(x_{s},a)\Big{]}$ $\displaystyle=\sum_{s\in S}\pi_{s}\Big{(}\sum_{a\in A_{\Delta}(x_{s})}\rho(a|s )\big{[}\underbrace{v(x_{s},a^{*}_{s})-v(x_{s},a)}_{\geq 0}\big{]}+\sum_{a\in \overline{A_{\Delta}(x_{s})}}\rho(a|s)\big{[}\underbrace{v(x_{s},a^{*}_{s})-v( x_{s},a)}_{>\Delta}\big{]}\Big{)}$ $\displaystyle\geq 0+\Delta\sum_{s\in S}\pi_{s}\sum_{a\in\overline{A_{\Delta}(x _{s})}}\rho(a|s)$ $\displaystyle=\Delta\sum_{s\in S}\pi_{s}\rho(\overline{A_{\Delta}(x_{s})}\,|\, s).$ $$

Rearranging,

$$ $\sum_{s\in S}\pi_{s}\rho(\overline{A_{\Delta}(x_{s})}\,|\,s)\leq\frac{\delta}{ \Delta}.$ (27) $$

Then, we consider the randomized strategy $\rho^{\prime}$ that, for each $s$, chooses each action $a\in A_{\Delta}(x_{s})$ with the conditional probability that $\rho$ chooses $a$ given $a\in A_{\Delta}(x_{s})$:

$$ $\displaystyle\rho^{\prime}(a\,|\,s)=\frac{\rho(a\,|\,s)}{\rho(A_{\Delta}(x_{s} )\,|\,s)}.$ $$

The sender’s utility under $\rho^{\prime}$ is:

$$ $\displaystyle U(\pi,\rho^{\prime})=\sum_{s\in S}\pi_{s}\sum_{a\in A_{\Delta}(x _{s})}\frac{\rho(a\,|\,s)}{\rho(A_{\Delta}(x_{s})\,|\,s)}u(x_{s},a).$ $$

The sender’s utility under $\rho$ is

$$ $\displaystyle U(\pi,\rho)=\sum_{s\in S}\pi_{s}\sum_{a\in A_{\Delta}(x_{s})} \rho(a\,|\,s)u(x_{s},a)~{}+~{}\sum_{s\in S}\pi_{s}\sum_{a\in\overline{A_{ \Delta}(x_{s})}}\rho(a\,|\,s)u(x_{s},a)$ $$

Taking the difference between the two utilities, we get

$$ $\displaystyle\big{|}U(\pi,\rho^{\prime})-U(\pi,\rho)\big{|}$ $\displaystyle\leq\Big{|}\sum_{s\in S}\pi_{s}\Big{(}\frac{1}{\rho(A_{\Delta}(x_ {s})\,|\,s)}-1\Big{)}\sum_{a\in A_{\Delta}(x_{s})}\rho(a\,|\,s)u(x_{s},a)\Big{ |}~{}+~{}\Big{|}\sum_{s\in S}\pi_{s}\sum_{a\in\overline{A_{\Delta}(x_{s})}} \rho(a\,|\,s)u(x_{s},a)\Big{|}$ $\displaystyle=\Big{|}\sum_{s\in S}\pi_{s}\frac{1-\rho(A_{\Delta}(x_{s})\,|\,s) }{\rho(A_{\Delta}(x_{s})\,|\,s)}\sum_{a\in A_{\Delta}(x_{s})}\rho(a\,|\,s)u(x_ {s},a)\Big{|}~{}+~{}\Big{|}\sum_{s\in S}\pi_{s}\sum_{a\in\overline{A_{\Delta}( x_{s})}}\rho(a\,|\,s)u(x_{s},a)\Big{|}$ $\displaystyle\leq\sum_{s\in S}\pi_{s}\frac{1-\rho(A_{\Delta}(x_{s})\,|\,s)}{ \rho(A_{\Delta}(x_{s})\,|\,s)}\sum_{a\in A_{\Delta}(x_{s})}\rho(a\,|\,s)\cdot B ~{}+~{}\sum_{s\in S}\pi_{s}\sum_{a\in\overline{A_{\Delta}(\mu_{s})}}\rho(a\,| \,s)\cdot B$ $\displaystyle=B\sum_{s\in S}\pi_{s}\frac{\rho(\overline{A_{\Delta}(x_{s})}\,| \,s)}{\rho(A_{\Delta}(x_{s})\,|\,s)}\rho(A_{\Delta}(x_{s})\,|\,s)~{}+~{}B\sum_ {s\in S}\pi_{s}\rho(\overline{A_{\Delta}(x_{s})}\,|\,s)$ $\displaystyle=2B\sum_{s\in S}\pi_{s}\rho(\overline{A_{\Delta}(x_{s})}\,|\,s) \stackrel{{\scriptstyle\eqref{eq:delta/Delta}}}{{\leq}}\frac{2B\delta}{\Delta}.$ $$

This proves the lemma.
∎

We now prove Lemma C.3.

###### Proof of Lemma C.3 .

Consider the objective $\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)=\sup_{\pi}\min_{\rho\in\mathcal
{R}_{\delta}(\pi)}U(\pi,\rho)$. By Lemma C.7, for any $(\pi,\rho)$ there exists an agent strategy $\rho^{\prime}:s\mapsto\Delta(A_{\Delta}(x_{s}))$ that only randomizes over $\Delta$-optimal actions such that $\big{|}U(\pi,\rho^{\prime})-U(\pi,\rho)\big{|}\leq\frac{2B\delta}{\Delta}$. Because minimizing over $\Delta(A_{\Delta}(x_{s}))$ is equivalent to minimizing over $A_{\Delta}(x_{s})$, which corresponds to deterministic $\Delta$-best-responding strategies, we get:

$$ $\displaystyle\underline{\mathrm{OBJ}}^{\mathcal{R}}(\delta)\,=\,\sup_{\pi}\min _{\rho\in\mathcal{R}_{\delta}(\pi)}U(\pi,\rho)$ $\displaystyle\,\geq\,\sup_{\pi}\min_{\rho^{\prime}:s\mapsto\Delta(A_{\Delta}(x _{s}))}U(\pi,\rho^{\prime})-\tfrac{2B\delta}{\Delta}$ $\displaystyle\,=\,\sup_{\pi}\min_{\rho^{\prime}:s\mapsto A_{\Delta}(x_{s})}U( \pi,\rho^{\prime})-\tfrac{2B\delta}{\Delta}$ $\displaystyle\,=\,\underline{\mathrm{OBJ}}^{\mathcal{D}}(\Delta)-\tfrac{2B \delta}{\Delta}.$ $$

∎

###### Lemma C.7 .

###### Proof.

###### Proof of Lemma C.3 .

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: Why is it necessary in this paper to drop the private information in the generalized principal-agent problem from  Myerson (1982) and Gan et al. (2024)?
soundness: 3
strengths: - The paper introduces a novel problem along with a generic solution framework. I like its results derived from a clean reductions approach.
- The paper provides the reader's sufficient knowledge about the general principal-agent problem from Gan et al. (2024).
- The paper provides many well-sketched intuitions to help us understand its proofs.
summary: The paper considers the principal's adaptive strategy design problem against a non-regret learning agent. The paper shows that the problem can be reduced from against an approximated best response agent.  The key technique is the perturbation argument.
weaknesses: - The writing of the paper can be improved. For example, the paper could use a table to summarize all results and a table for all notations in this paper. While the paper is framed under the general principal-agent problem, it only discusses the Bayesian persuasion problem as its special case. 
- 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 and make the environment non-stationary. I think there is a valid problem to study in theory, but it would be much better if we can derive some practical implication from this paper's results.
- While I find the result of this paper interesting, the technical depth of this paper is relatively shallow and thus I would not recommend higher level of acceptance for this paper.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: - In the statement of Theorem 5, the authors claim: "the sender can obtain a utility significantly larger than $U^*$ ..." Can the authors quantify what "significantly larger" means in the context of this theorem? Is it something proportional to the time horizon $T$? Furthermore, why does the lemma hold only in Bayesian persuasion settings?

- How can the fixed policy $\pi_t$ in the statement of Theorem 3.1 be computed?
soundness: 3
strengths: - The problem studied in the paper represents an interesting contribution to principal-agent problems that mainly focus on models in which the agent does not learn
- The results on the achievable utility when the agent plays a $\delta$-suboptimal best response according to a randomized strategy are interesting and novel
summary: This paper studies "generalized principal-agent problem" in which a learning agent interacts with a principal who lacks commitment power. This setting can be used to describe several economic scenarios, like Stackelberg games and Bayesian persuasion. The paper focuses on the utility that the principal can achieve depending on the learning algorithm adopted by the agent—specifically, whether the agent uses a no-regret or no-swap-regret learning algorithm. The authors provide upper and lower bounds on the principal's achievable utility based on the algorithm played by the agent. To accomplish this, they establish a connection with the $\delta$-robust principal-agent problem, developing results that are of independent interest.
weaknesses: - If my understanding is correct, the assumption that there exists a $p_0 \ge \min \mu_0(\omega)$ limits the applicability of the results in large state instances (since ${1}/{|\Omega|} \ge p_0$), which are well studied in Bayesian persuasion problems. I believe the authors should address this limitation explicitly in the paper and discuss potential extensions.
  
- Similarly, in Stackelberg games with a small inducibility gap, the proposed analysis does not hold.

- The approach to proving Theorem 4.1 (first point) appears somewhat incremental with respect to Gan et al. (2023). Both consider a convex combination (depending on the inducibility gap) of two strategies, where in one strategy the principal’s utility is larger than $G$ when they play specific action compared to all the remaining actions. This is not necessarily a drawback, but it raises questions about the technical novelty of this approach—perhaps related to the shape of the domain?

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

- Typo: Line 981 “Sectin”

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: - I assume that the whole paper assumes the principal knows the agent's payoffs? If so it would be helpful to point that out more explicitly.

- There's also recent work on similar sequential principal-agent problems, which look relevant: Gan et al. (2023), Sequential principal-agent problems with communication: efficient computation and learning. What do you see any implications between your work and theirs?
soundness: 4
strengths: The paper is well-writen and very clear. I enjoy reading it. The topic of playing against a learning agent is very relevant to the theme of ICLR. Extending this line of research from standard normal-form games to generalized principal-agent problems is well motivated and interesting. The paper analyzed different types of no-regret algorithms and the results presented look quite complete. Technically, the results also look solid and are presented rigorously. The authors did a good job in explaining the intuitions behind the results, too.
summary: The paper studies a generalized principal-agent problem where the agent learns to make decisions. The goal is to design the principal's strategy against such an agent. A sequential setting is considered, where the principal and the agent interact over time. The agent uses a no-regret algorithm to determine actions to perform in each time step, based on the past reward yielded by his actions. The paper considers different types of no-regret algorithms, including no-swap-regret and mean-based no-regret algorithms. Utilities the principal can achieve against these algorithms are analyzed, in comparison with the principal's optimal utility in the standard one-shot principal-agent model.
weaknesses: I don't have any major concerns with the paper. One weakness is that Results 1 and 4 seem to largely follow by previous work and looks somewhat incremental. But the other results look sufficiently new and to extend normal-form games studied in previous work to generalized principal-agent problem seems to require a good amount of effort. It would be helpful if the authors can stress a bit more the differences between normal-form games and generalized principal-agent problem, and highlight the additional difficulties for addressing the latter.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: I would say that the paper could be defined as an attempt towards information design with a learning agent and how to manipulate/persuade this agent. To my knowledge, the same kind of issues are becoming explored recently for mechanism design or Markov Decision Processes setups with a learning agent (as Guruganesh et al., 2024 with Contract theory, that you mention):

	- Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality, that studies mechanism design bet-ween a learning principal and a learning agent on a bandit game and how the principal can align the agent’s actions on her preferences.

	- Principal-Agent Reward Shaping in MDPs, that studies principal-agent interactions on a MDP and formulates it as an  optimization problem.

	- Bayesian Incentive-Compatible Bandit Exploration, that studies how a principal could reveal information to incentivize the agent to take some specific actions - they also provide a black-box reduction of the problem to incentive-compatible bandits..

One could say that information design is about trading information while mechanism design is about trading utility. I believe that these references are close from your work and that it could be interesting to discuss them. How could they be related it?

Finally, it is mentioned that « the sender commits to a signaling scheme » and then follows $\pi(s|\omega)$ - 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.
soundness: 3
strengths: I really enjoy the fact that the paper formulates interesting results about a fully abstract game theoretic setup. I think that great applications could be built relying on that.

One might wonder about the relevance of a theoretical paper on principal-agent issues for ICLR. However, the paper’s focus on signaling states and Bayesian perspectives effectively bridges representational learning with economic concepts, making it a strong fit for the conference.

The paper is well written and clear, which makes it pleasant to read.
summary: This paper proposes a general method to reduce the repeated principal-agent games to one-shot approximate best-response on principal-agent games.

The setup is very close from the Bayesian Persuasion  one [Kamenica and Gentzkow, 2011].
The principal does not have commitment power but as in the Bayesian Persuasion setup, they can disclose information so to influence the agent’s behavior.
Then, the problem on a repeated game is reduced to a one-step game with approximately optimal action played by the agent. The reduction is achieved through the fact that a no-regret learning agent is behaving approximately optimally - which can be seen with the following equation:
$$V(\pi, d) - V(\pi, \rho) \leq CReg(T)/T,$$
which makes the agent’s actions a $\delta$-approximate best-response. After this reduction is done, the paper shows that an agent’s appropriate best response makes the principal's utility close from optimality. The proofs are achieved through a nice perturbation argument. The paper finally gives some applications to Bayesian Persuasion, Stackelberg games and Contract design.

I appreciate the fact that extending an online Bayesian Persuasion model, the paper recovers several interesting games and results. Also, the assumptions used are reasonable, which can be a lack in some papers from this kind of literature. As an example, for Theorem 3.1, the principal knows the agent’s regret bound but not the learning algorithm itself, which is a reasonable assumption and could be recovered in real-world scenarios.
weaknesses: **First point:** My main concern is about the relation between the paper and existing results in the computational game-theoretic literature, especially in the link between no-regret and equilibrium.

I enjoy how the paper relates online learning problem between a principal and an agent to one-step games. However, I wonder if the results that are obtained (e.g., a principal's utility arbitrary close from the optimal one, etc) can be described in terms of coarse-approximate or coarse-correlated equilibrium. More discussion on this would be interesting since the paper does not mention any form of equilibrium at all.

Regret minimization of the agents alone is sufficient to ensure convergence to coarse correlated equilibrium in general-sum multiplayer games. This kind of results are given in these lecture notes for instance (https://www.mit.edu/~gfarina/2024/6S890f24_L04_regret/L04.pdf). Is it possible to formulate your setup as a game (for instance by saying that players commit to a strategy that will be more complex and will depend on a revelation of a state of nature) and then apply the equilibrium results to obtain your convergence/approximation rates?

**Second point:** I have a few comments on the setup. According to the authors, it is a general principal-agent game with a learning agent that recovers Bayesian Persuasion among other types of games. To me, this setup is exactly an online version of Bayesian Persuasion canonical setup, adding the fact that the principal also take an action $x_t$ alongside choosing a signal. It is not a huge issue but I think that the authors should not phrase their problem as such a general setup.

Below, I copied the model of the paper « Online Bayesian Persuasion », that is part of the references:

« We consider the following online setting. The sender plays a repeated game in which, at each round $t \in [T]$, she/he commits to a signaling scheme $\phi_t$, observes a state of nature $\theta_t \sim \mu$, and she/he sends signal $s_t\sim \phi^t_{\theta_t}$ to the receiver. Then, a receiver of unknown type updates her/his prior distribution and selects an action $a_t$ maximizing her/his expected reward (in the one-shot interaction at round t). We focus on the problem in which the sequence of receiver’s types $\{k_t:t \in [T]\}$ is selected beforehand by an adversary. After the receiver plays $a_t$, the sender receives a feedback on her/his choice at round t. In the full information feedback setting, the sender observes the receiver’s type $k_t$. Therefore, the sender can compute the expected payoff for any signaling scheme she/he could have chosen other than $\phi_t$. Instead, in the partial information setting, the sender only observes the action $a_t$ played by the receiver at round t. », Castigioni et al., 2020

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 $t$ in this model. I think that this work desserves a more thorough discussion, due to its similarity with your framework. I think that good ideas are brought to the setup but the differences should be highlighted.


I put in the weakness section my main concerns but they should be seen more as questions and I am confident in a satisfying answer to them by the authors.

Meta-review: The paper studies (generalized) principal-agent problems in EconCS (including Bayesian persuasion and contract design) using a no-regret framework. I agree with the authors that the "clean reduction and the generality of the analysis" (which applies to all principal-agent problems) are a clear strength of the paper. Indeed, I find the authors' approach and refinement of existing results on whether agents can be exploited very insightful. While some concerns around contract design were raised, I felt that the authors did a good job at clarifying their position. Overall, I think the papers strengths clearly outweigh the weaknesses, and I recommend acceptance.

Decision: Accept (Spotlight)