Generalized Principal-Agent Problem with a Learning Agent
Authors: Tao Lin
Yiling Chen
Venue: ICLR 2025 Spotlight (2025)
Keywords: principal-agent problems
Bayesian persuasion
no-regret learning
no-swap-regret
Primary area: learning theory
TL;DR: We study generalized principal-agent problem with a learning agent, which not only sharpens previous works on contract design and Stackelberg games but also leads to new results for Bayesian persuasion.

Abstract: Generalized principal-agent problems, including Stackelberg games, contract design, and Bayesian persuasion, are a class of economic problems where an agent best responds to a 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 $\mathrm{Reg}(T)$, then the principal can guarantee utility at least $U^* - \Theta\big(\sqrt{\tfrac{\mathrm{Reg}(T)}{T}}\big)$, where $U^*$ 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 $\mathrm{SReg}(T)$, then the principal cannot obtain utility more than $U^* + O(\frac{\mathrm{SReg(T)}}{T})$. 
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^*$.
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.

Published as a conference paper at ICLR 2025
GENERALIZED PRINCIPAL-AGENT PROBLEM WITH A LEARNING AGENT
Tao Lin, Yiling Chen
John A. Paulson School of Engineering and Applied Sciences Harvard University t1 tlineg ha rvardd.du,,
yilingêseas harvard.edu
ABSTRACT
Generalized principal-agent problems, including Stackelberg games, contract de- sign, and Bayesian persuasion, are class of economic problems where agent best responds to principal's '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 prin- cipal. We reduce this 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"),
one-shot generalized principal-agent problem
then the principal can guarantee utility at least U (v (o)( where U is the principal's optimal utility in the classic model with best-responding agent. (2) If the agent uses contextual no-swap-regret learning algorithms with swap-regret SReg(T), then the principal cannot obtain utility more than U + O (Reg(T)) ). But (3) if the agent uses mean-hased learning algorithms (which can be no-regret but not no-swap-regret) then the principal can sometimes do significantly better than U* These results not only refine previous results in Stackelberg games and contract design, but also lead to new results for Bayesian persuasion with a learn- ing agent and all generalized principal problems where the agent does not have private information.
INTRODUCTION
Classic economic models of principal-agent interactions, including auction design, contract design, and Bayesian persuasion, often assume that the agent able best respond the strategy com- mitted by the principal. For example, in Bayesian persuasion, the agent (receiver) needs to compute the posterior belief about the state the world after receiving some information from the principal (sender) and take 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 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) 1998 Benjamin 2019).
outcome-dependent payment scheme to incentivize the agent to take
In this work, using Bayesian persuasion the main example, we study general principal-agent problems under an alternative behavioral model for the agent: learning. The use of learning as behavioral model dates back early economic literature on learning games (Brown) [951 Fudenberg & Levine 1998) and has been actively studied by computer scientists in recent years (e.g.. Nekipelov al. (2015); Braverman al.) (2018); [Dnng et al. (2019); ; Mansour al. (2022): Cai et al. (2024): Guruganesh et al. (2024)). A learning agent no longer has perfect knowleds of the parameter of the game or the principal's 's strategy. Instead 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 hindsight. This a mild requirement satisfied by many natural learning algorithms (e.g.. e-greedy, MWU, UCB, EXP-3) and can reasonably serve possible behavioral assumption for real-world agents.

---

Published as a conference paper at ICLR 2025
Can the principal achieve better outcome with a learning agent than with a best-responding agent?
Previous works (Deng et al. 2019; Guruganesh et al., 2024) have shown that, in Stackelberg games
and contract design, the leader/principal can obtain utility U o(1) against no-regret learning follower/agent, where U is the Stackelberg value, defined to be the principal's optimal utility in
the classic model with best-responding agent. On the other hand, if the agent does a stronger version of no-regret learning, called no-swap-regret learning (Hart & Mas-Colel] 2000; Blum & Mansour 2007), then the principal cannot obtain utility more than the Stackelberg value U' + o
Interestingly. the conclusion that no-swap-regrel learning can cap the principal's 's utility at U - o
does not hold when the agent has private information, such as in auctions (Braverman et al. 2018)
and Bayesian Stackelberg games (Mansour et al., 2022): the principal can sometimes exploit no- swap-regret learning agent with private information to much better than U 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 + {1)? (2) In cases where the principal's optimal utility against learning agent is bounded by I0 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 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 is utility is bounded around U in all generalized principal-agen problems where the agent does not have private infor- mation 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 unified analytical framework to derive tight bounds on the principal's achievable utility against no-regret or no-swap-regrel learning agent in all generalized principal- agent problems where the agent does not have private information. Specifically, we explicitly char- acterize the (1) difference between the principal's 's utility and U in terms of the agent's 'entss regret.
Result 1 (from Theorems 3.1
Against no-regret learning agent with regret Reg(T") in
T periods, the principal can obtain an average utility of at least U - O(( Reg(T))
Against a no-swap-regres learning agent with swap-regret SReg(T) in T periods, the principal cannot obtain average utility larger than U + +0( ())
Result 2 (from Theorems 3.4
4.2).
Interestingly, the squared root bound U -0(V ((VRR((T) in Result and the linear bound U +
( (Reg(T) in Result 2 are not symmetric. We show that such an asymmetry is intrinsic: there exist
T
cases where the principal cannot achieve better than U O
Reg(T)
utility.
and Result 3 (from Theorem 3.3 and Example There is a Bayesian persuasion instance where, for any strategy of the principal, there is a no-swup-regre learning algorithm for the agent under which the principal's utility most U R(( (R
). The same holds for no-regret algorithms.
Results 1, 2, 3 together characterize the range of utility achievable by the principal against no- swap-regret learning agent: [U- - sarily no-swap-regret algorithms, the upper bound U + O Reg(T)) does not hold:
- e Sitee(T)) T
), U + O SHeg(T)) }]. For no-regret but not neces-
Result 4 (Theorem 3.5p. We construct Bayesian persuasion instance where, against a no-regret but not no-swap-regred learning agent (in particular, mean-hased learning agent), the principal can do significantly better than the Stackelberg value U
In summary, our Results 2, not only refine previous works on playing against learning agents in specific games by characterizing the principal's utility exactly, but also generalize 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.
2

---

Published as a conference paper at ICLR 2025
Some intuition. What is the intuition behind the asymmetry between the worst-case utility U - (Reg(T) and the best-case utility U + (() that the principal can obtain against a no-swap-regret learning agent? At a high level, a no-swap-regret learning agent is approximately best responding to the principal's average strategy over all I periods, with the degree of approxi-
mate best response measured by the average regret SReg(T) 8. However, because no-swap- learning algorithms are randomized, they correspond to randomized approximately best responding strategies of the agent that are worse than the best responding strategy by a margin of expecta- tion. This means that the agent might take Vô-sub-optimal actions with probability v6, which can cause a loss of to the principal's utility with probability vo. So, the principal's 's expected utility can
be decreased to - = U- - - (Reg(T)) in the worst case. On the other hand, when con- sidering the principal's ls best-case utility, we care about the 5-approximately wiwiinatllybeeeeeesonndieee
strategy of the agent that maximizes the principal's 's utility. That strategy turns out to be equivalent to deter-
ministic strategy that gives the principal a utility of at most U* + (6) = U + O (Reg(T) This
explains the asymmetry between the worst-case and best-case bounds.
GENERALIZED PRINCIPAL-AGEN PROBLEM WITH A LEARNING AGENT
This section defines our model, generalized principal-ate 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 (1922;; Gan et al. (2024), is general model that includes auction design, contract design, Stackelberg games, and Bayesian persuasion. While|Myerse (1922) and Gan al. (2024) 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 X' and the agent has a finite action set A. The principal and the agent have utility functions u, v X' x A + I. We assume that u(z, a), v(2, a) are linear in x E X', which is satisfied by all the examples of gener- alized 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 SS) > |A]. A strategy of the principal is a distribution π E (xX x XS) over pairs of decision and signal. When the utility functions u, 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. 2024), namely, the principal chooses a distribution over write principal
S. So, strategy as π = ((T,, #x)hees where π, 2 0 is the probability of signal s E S, Exes T 1, and T, E X. There two variants of generalized principal-agent problems:
signals and unique decision F, associated with each signal
Unconstrained (Myerson
1982): ): there is no restriction on the principal's strategy n
Constrained (Gan et al.) 2024): the principal's strategy has to satisfy constraint
Exes Rg E where C 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 π = {(TT,, xx) ses) then nature draws a signal S accord- ing to the distribution {T& Jees and sends to the agent (note: due to the commitment assump- tion, this equivalent to revealing the pair (s. 2.) to the agent), then the agent takes an action a, arg max,e v(I,, a) that maximizes its utility, and the principal obtains utility u(x,,a,) a,). The principal aims to maximize its expected utility Eg-zl (u(#,, by choosing the strategy π.
2.2 LEARNING AGENT
Now we define the model of generalized principal- problem with learning agent. The game is repeated for 7 rounds. Unlike the static model above, the principal here does not commit. The agent
3

---

Published as a conference paper at ICLR 2025
does not know the strategy n' or the decision x' of the principal at each round. Instead, the agent uses some adaptive algorithm to learn which action to take in response to each possible signal.
Generalized Principal-Agen Problem with a Learning Agent
In each round = I,...,T: 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 p² S - A(A) that maps each possible signal E S to a distribution over actions (s) E A
(2) The principal chooses strategy x' {(*), rsSs, which is distribution signals S and a decision x², E X' associated with each signal.
(3) Nature draws signal
T² and reveals it. The principal makes decision x' = xy... The agent draws action a' ~pp (s*).
The principal and the agent obtain utility u² = u(x",a") and of = v(x', a²). The agent observes some feedback (e.g., (z',, a²) or x²).
We assume that the principal knows the utility functions and has some knowledge about the agent's learning algorithm, and aims to maximize the expected average utility 1E [Σ u(x', u(x")a'))
Agent's learning problem. The agent's 's learning problem can be regarded as a contextual multi- armed bandit problem (Tyler Lu et al.. 2010) where A is the set of arms, and signal s serves as a context that affects the utility of each arm a E A. The agent picks an arm to pull based on the current context sf 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 's decision x' after each round (this is call full-information feedback in the multi-armes bandit literature), or the utility vf = vf(",, a²) obtained that round (this is called bandit feedbuck), or some unbiased estimate of v(=",a²) 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 's learning algorithm is said to satisfy:
contextual no-regret if: there is a function CReg(T) o(T) such that, for any strategy of the principal, for any deviation function d S + A, the regret of the agent not deviating according to d is at most CReg(T)): E[E.= (v(z", dd(s)) - v(I', a²))] S CReg(T).
contextual no-swap-regret if: there is a function CSRog = o(T) such that, for any strategy of the principal, for any deviation function :: S x A - A, the regret of the receiver not deviating according to is at most CSReg(T)): E E (u(x* d(s', aa)) u(x", at))] S CSReg(T), (T)).
We call CReg(T) and 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 (sswaaa)regrre algorithms with ((AAV/|STT) contextual (swap- rregret are known exist under bandit feedback. In fact, they can be easily constructed by running an ordinary no-(swap-)reeeg algorithm for each context independently. See Appendix B for details.
2.3 SPECIAL CASE: BAYESIAN PERSUASION WITH A LEARNING AGENT
We show that Bayesian persuasion (Kamenica & Gentzkow 2011) is a special case of constrained generalized principal-agent problems. We will also show that Bayesian persuasion is in fact equiva- lent to cheap talk (Crawford & Sobel 1982) 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 of states of the world, signal set S, an action set A, prior distribution Po E A(2) over the states, and utility functions u, v : x A + R for the sender and the receiver. When the state is w e Ω and the receiver takes action A, the sender and the receiver obtain utility u(w, a),, v(w, a), respectively.
4

---

Published as a conference paper at ICLR 2025
Both players know Mus but only the sender has access the realized state Ma- The sender commits to some signaling scheme π : S2 - A(S), mapping any state to a probability distribution over signals, to partially reveal information about the state to the receiver. In the classic model, after receiving signal 8 E S, the receiver will form the posterior belief μts E (S2) about the state: (e(W)= )o(w) where x Ewen (o(w)) is the total probability that signal is sent, 7, and take optimal action with respect Maa i.e., 0g arg max Ewen (w( a). The sender aims to find signaling scheme to maximizde its expected utility E Blu(w, 0.)]-
is well--noww (Kamenica & Gentzkow 2011) I) that a signaling scheme т : + (SS) decomposes the prior Hi into a distribution over posteniors whose average is equal to the prior po:
Σ Tsps = no {PO} C,
Σ
nx =1
SES
Equation I is called the Bayes plausibility condition. Conversely, any distribution over posteriors ( satisfying Bayes plausibility Loeg PoJMa n4 can be converted into signaling scheme that sends signal with probability Ps- Thus, we can use a distribution over posteriors ((g)))))) satisfying Bayes plausibility represent signaling scheme. Then, let's equate the posterior belief μss in Bayesian persuasion to the principal's s decision x, in the generalized principal- agent problem, so the principal/sender' decision space becomes X A(2). The Bayes plausibility condition ①1 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/posteri ( (w))(w, a). Suppose the agent takes action a,
I, μ4, is uZ a) = Eu-a, a(w, given signal 8 E S. Then we see that the sender's 's utility of using signaling scheme π in Bayesian persuasion (left) is equal to the principal's utility of using strategy in the generalized principal- agent problem (right):
Ewen M'
Σ Ho(w) Σ Im(sww)u(u,ay = Σ T. Σ [uslw)u(wwaa Em a.) -nstwialeees---Ssst,e Eswn [u( 4)]-
WES
=ES
SES
WEN
sES
Similarly, the agent/receiver's utilities the two problems are equal. The utility functions u(x a), v(2,a) a) are linear in the principal's 's decision E 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:
Persuasion (or Cheap Talk) with Learning Receiver
In each round 1,...,77 T, ,
the following events happen:
(1) Using some algorithm that learns from history, the receiver chooses a strategy p² S ((A) that maps each signal E S to distribution over actions (ss) E A(A).
(2) The sender chooses signaling scheme π' Ω + A(S).
(3) A state of the world wf ~ μo is realized, observed by the sender but not the receiver. The sender sends signal s xt (w"") to the receiver. The receiver draws action a" ~ ps()..
The sender obtains utility u' (u(w"aa) and the receiver obtains utility of v(w", a²)
"The definition utility here, u(w", ((w",a"), o(w", aa), diffferent from the definition which was the expected utility on decision/posterior x", u(x", .a),, u(x", .²). Because we only care about the sender's expected utility and the receiver's 's expected regret, this difference does not matter.
general model,
In the above model, the receiver does not need to know the prior μi or the sender's signaling scheme because his multi-armed bandit learning algorithm does not need such information. This makes the receiver's 's and the sender's 's decisions simultaneous, which corresponds to the cheap talk model (Crawford & Sobel 1982) where the sender does commit to the signaling scheme. So. our "persua- sion with a learning receiver" model is equivalent to "cheap talk with a learning receiver".
REDUCTION FROM LEARNING TO APPROXIMATE BEST RESPONSE
In this section, reduce the generalized principal-agent problem with learning agent to the problem with an tual no-regret learning algorithms, then the principal can obtain average utility that is at least the
agent. We show that, the agent uses contex-
5

---

Published as a conference paper at ICLR 2025
"maxmin" approximate-best-rei best-rspons- objective OBJ (T))) (to be defined below). On the other hand, if the agent does contextual no-swap-regret learning, then the principal cannot do objective OBJ (T)))) 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 OBJ" (T)
better than the "maxmax" ppproxximate-bet--essppooo
3.1 GENERALIZED PRINCIPAL- PROBLEM WITH APPROXIMATE BEST RESPONSE
We first define the generalized principal-agent problem with an approximaatel- -eetee---d------ddiig agent. The classic generalized prineipal-agent problem (Section 2.1) assumes that, after receiv- ing signal 8 E 8 (and observing the principal's ' decision I, E X) the agent will take an optimal action with respect to Zs. This means that the agent uses a strategy p" that best responds to the principal's 's strategy π::
p" (8) E arg max o( a) Vs
p" E arg max P(T, p: AAS)
(2)
aEA
Here, V(T, p) = Eees Te EDEA p(a)s)u(z,. a) denotes the expected utility of the agent when the principal uses strategy и and the agent uses (randomized) strategy p
A(A).
Here, we allow the agent to approximately best respond. Let 5 2 0 be parameter. We define two types d-best-responding strategies for the agent: deterministic and randomized.
A deterministic strategy /:: for each signal E S, the agent takes an action that is 8-optimal for Zg. Denote this set of strategies by Dz(r:::
Ds( = {pr + A v(z,, p(s)) 2 v(z.,d') - 8, Va's E A}.
(3)
A randomized strategy p: for each signals s, the agent can take a randomized action. The expected utility of p is at most 6-worst than the best strategy p".
Rx(x)) {p: ((A) V( p) 2 V(T, p²) --)- 5).
(4)
Equivalently, (s( - ((A) V(T, 2 V(=, 6, Ap 5 -)
Our model of wwwpriiiattll--bb--eeeppooooooet
agent includes, for example, two other models in the Bayesian persuasion literature that also relax the agent's ' Bayesian rationality assumption: the quan- tal response model (proposed by (McKelvey & Palfrey 1995) in normal-fore games and studied by (Feng et al. (2024) in Bayesian persuasion) and a model where the agent makes mistakes in Bayesian update (de Clippel & Zhang 2022). See Appendix C [for details.
Principal's objectives. With an objectives for the principal. The first type is the maximal utility that the principal obtain if the agent approximately best responds in the worst way for the principal: for X e R). define
agent, we will study two types of
OBI (8) sup min U(T,)).
x (EX,(m)
where UTT, p) Eoes T E.E p(als)u(x,, a) is the principal's 's expected utility when the princi- pal uses strategy т and the agent uses strategy p. We used "sup" in (5) because the maximizer does not necessarily exist. OBJ (8) 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 the agent approx- imately best responds in the best way:
OBJ (8) max U(T,)) p).
pEXa(w)
This is a "maxmax" objective that quantifies the maximal extent to which the principal can exploit the agent's irrational behavior.
X Clearly, OBJ (8) OBJ (0) < OBJ (0) < OBJ (8). And we note that OBJ X (0) OB) independent of X and equal to the optimal utility of the principal in the classic generalized principal-agen problem, which denote by U*:
U = OB] = max max
U( p)-
p: best-respouse

---

Published as a conference paper at ICLR 2025
Finally, note that, because Du(at) S Do(T) S RT(T), the chain of inequalities OB.I 1
OBJ (6) S U I OBJ (0) S OBJ R (6) 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 CReg(T). The principal knows CReg(T) but not the exact learning algo- rithm of the agent. By using some fixed strategy x' all T rounds, the principal can obtain an average utility + Ei= a(x',a')] that arbitrarily close to OBJ R (2Reg(2))
To prove Theorem 3.1
we provide lemma (with proof in Appendix E.1 to relate the agent's 's regret and the principal's ss utility in the learning model to those in the static model. We define some nota- tions. Let the principal use some fixed strategy n' and the agent use some learning algorithm. Let Paj= = Pr(a' a 1 = s] be the probability that the agent's 's algorithm chooses action condi- tioning on signal s being sent in round L. Let S - (AA) be a randomized agent strategy that, given signal 8, chooses each action E A with probability p(als) Dis Pal.
Lemma 3.2. When the principal uses fixed strategy ní in all T rounds, the regret of the agent not deviating according d S A is equal to 1 Σ T (o(a', d(s')) v(at, d'))] ((T,d)-Va P),,), and the average utility of the principal + Σ/= u(x', ,a)] is equal to U(T, p).
Proof Theorem 3.7 By Lemma 3.2 and the no-regret condition that the agent's regret
E E (u(x', d(s))) - =00", a²) ) I CRog(T), we have
V(T, - V(T
+ Σ Tu(tt,
(ott,aa))) S CTog(T) vd: A
This means that the agent's randomized strategy p is CReg(T) best-respoose to the principal's fixed signaling scheme æ, E CRegit (T). This holds for any т. In particular, if for any >> 0
the principal uses signaling scheme n= that obtains an objective that is E-close to OBJ sup, min ( UTT,P) p). then the principal obtains an expected utility of, by Lemma 3.2
Σ ula', wi)
U ( 2
min U(TE,p) 2 OBJ (8 (ER
CReg(T) T
in the learning model. Letting 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 OB. (Reg(T) even using adaptive strategies (see Appendix E.2 for the proof):
Theorem 3.3. For any adaptive strategy of the principal, there exists contextual no-regret learning
algorithm for the agent under which the principal's 's average utility is no more than OB. ( There also exists a contextual no-swap-regret learning algorishmm for the agent under which the principal's 's average utility is no more than OBJ R CSReg(T)
(Reg(T))
2T
3.3 AGENT'S NO-SWAP-REGRES LEARNING: UPPER BOUND ON PRINCIPAL'S UTILITY
Theorem 3.4. Against contextual no-swap-regrel learning agent, the principal cannot obtain utility more than F ET u(x",a²) < OBJ" (CSRe3(T) even using adaptive strategies.
The key idea to prove this theorem is to think of the signal s ~ T² from the principal and the action a' (s*t) recommended by the agent's 's learning algorithm together as a joint signal (s',a') a²) from some hypothetical signaling scheme x'. The agent takes the recommended action a', namely using the mapping (s", a²) + a' his strategy, in response T'. A no-swap-regret algorithm guarantees that the agent most T
CSReg(T) worse compared the best-responding strategy d' S x A A.
So, the agent's overall strategy is CSReg(2) -pproximaae best response m'. which limits the
principal's overall utility be most OBJ (CSReg(T) ). See details in Apendix E.3
7

---

Published as a conference paper at ICLR 2025
3.4 AGENT'S MEAN-BASED LEARNING: EXPLOITABLE BY THE PRINCIPAL
Many no-regret (but not no-swap-regred) learning algorithms (e.g., MWU, EXP-3) satisfy the following contextual mean-based property:
Definition 3.1 Braverman et al. (2018). Ler E v(w) ,a) be the sum of historical
utilities of the receiver in the first rounds he takes action when the signal/context is s. An algo-
rithm is called -y-mean-baase based if: whenever 3d' such that 00=((a) < - (a') yT, the probability
that the algorithm chooses action a at round t if the context 8 is Pria' = als² = < 7 with
== o(1).
Theorem 3.5. There exists Bayesian persuasion instance where, as long as the receiver does y-mean- basead learning, the sender can obtain a utility significantly larger than OBJ (7) and U The proof of this theorem Appendix E.4
4 GENERALIZED PRINCIPAL-AGENT PROBLEMS WITH APPROXIMATE BEST RESPONSE
After presenting the reduction from learning to approximate best response, we now study general- ized principal-agent problems with approximate best response. We will show that both the maxmin
objectives OBJ (6), OBJJR(8 (8) and the maxmax objectives OBJ (8). OBJ (5) are close to the optimal principal objective U in the best-response model when the degree 6 of the agent's approx- imate 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 (No Dominated Action). An action dg E A of the agent is weakly dominated if there exists mixed action a' A(A \ {au}) such that v(x, a²) Eawer [u(z, a)] 2 v(z,a0) for all I E X. We assume that the agent has no weakly dominated action.
Claim 1. Assumption implies: there exists a constant > 0 such that, for any agent action a E A, there exists principal decision x E X such that v(x, a) v(x,, a') 2 G for every a' A {a).
The proof of this claim is in Appendix F.1 The constant G 0 in Claim is analogous to the
concept of "inducibility gap" in Stackelberg games (Von Stengel & Zamir 2004 Gan et al. 2023). In fact, Gan et al. (203)) show that, if the inducibility gap G > ö, then the maximin approximate- á in Stackelberg games. Our results will significantly generalize theirs to any generalized principal-agent problem, to randomized agent strategies, and to the maximax objectives OBJ* (6), OBJ (6).
response objective satisfies OBJJP(5)
U
&
To present our results, we need to introduce a few more notions and assumptions. Let diam (X:: II) max .22x || x2ll be the diameter of the space X, where || is some norm. For convenience we assume X' C Rd and use the & nnrmm ||ك||| = Σ |z(ey| or the loo norm || = max |z( For generalized principal-agent problem with constraint Σ.es n,T, E C, let ax be the boundary of X' and let dist(C, 0x)) = min ||c - xz|| be the distance from C to the boundary of X. We assume that C is away from the boundary of X:
Assumption (C is in the interior of X'). dist(C,
0.
Assumption (Bounded and Lipschitz utility). The principal's utility function bounded: [u(z,a) < B, and L-Lipschitz in E X: [u(II, a) - u(I2, a) S L||z| -22l-
Main results. We now present the main results of this section: lower bounds on OBJ* (8) and upper bounds on OBJ* (d) in generalized principal-agent problems without and with constraints. Theorem 4.1 (Without constraint). For an inconstrained generalized principal-agen problem, un- der Assumptions Land 3 for < 8 < G. we have
*BJJ (0) U diiam(X)
8

---

Published as a conference paper at ICLR 2025
(8) 2 U+ -2 2BL ( for 8
diam(X)GL
2B
OBJ (6) & OBJ R (6) & U + di)
Theorem 4.2 (With constraint). For generalized principal-agent problem with the constraint EVEs Tzd E C, under Assumptions and for (0.2)
diam([]] we have
OBJ (8) 2 U - -(diam( + 2B diam(x) dist(c G
OBJ (8) 2 U - 2 22 (diam(X) + 2B diam X (xx) 66.
OBJ < OBJ (8) s U (diam(XX) 2B
diami X)) 5 aist(C,ax)) G.
The expression " diam(
"ist 8" suggests that [it([,,o]] is similar to a "condition number" (Renegar 1994] that quantifies the "stability" of the principal-agent problem against the agent's approximate- best-responding behavior. When dist(C, 0x) is larger (C further away from the boundary of X), the condition number is smaller, the problem is more stable, and the d-best-response objectives
OBJ x (8) and OBJ* (d) are closer to the best-response objective U*
High-level idea: perturbation. The high level idea to prove Theorems and 4.2 is a perturba-
tion argument. Consider proving the upper bounds OBJ" (6) for example. Let (TT, p) be any pair of principal's strategy and agent's d-besttresponding strategy. We perturb the principal's 's strategy æ slightly to be strategy x to which is exactly best-responding (such perturbation is possible due to Assumption[] [). Since p is best-responding to T'. the pair (T', p) cannot give the principal a higher utility than U (which the optimal principal utility under the best-response model). This means that the original pair (x, p) cannot give the principal utility much higher than U" thus implying
an upper bound on OBJ" (6). Extra care is needed when dealing with randomized strategies of the agent. See details in Appendix
The bound ( 2 - is tight. We note that, in Theorems
4.1 and 4.2 the maxmin
objective with randomized agent strategies is bounded by OBJ T (6)
2 U" O(vō). while the
objective with deterministic agent strategies is bounded by OBJ (8) 2 00-0(6)) This is not
because our analysis is not tight. In fact, the squared root bound U @(v8) for OBJR( is
tight. We prove this by giving an example where OBJ*( (8) < U l(v σ). Consider the following classical Bayesian persuasion example:
Example 4.1. There are 2 states Ω (Good, Bad], actions A (a,b), with utility matrices
sender
receiver
a
b
Good
0
Good
1
Bad
Bad
0
The prior probability of Good state is μo < 2. so the receiver takes action b by default. In this example, for 8 < No.
2 OBJ (8) < U 22-22/d + U 2(V8). See Appendix K22 a proof.
APPLICATIONS TO SPECIFIC PRINCIPAL-AGERT PROBLEMS
We apply the general results Section 3 and 4 to derive concrete results for three specific principal- agent problems: Bayesian persuasion, Stackelberg games, and contract design.
Bayesian persuasion. As noted in Section
2 Bayesian persuasion is a generalized principal-agent problem with constraint E.es TT C (oo} where each I, _1, (H,(w)) E X A(12) is a posterior belief. Suppose the principal's utility is bounded: [u(w, a)l < B. Then, the principal's 's utility function u(H,, a) Ewen Mtg (w))(w, a) (L -)-Lipchhitz in μ, (under 41- norm), so Assumption 3 satisfied. Suppose the prior Mo has positive probability for every w E Ω and let Po = min (o(w) > 0. Then, we have the distance
(C, min {llPo All1 1 ((2) (mw) = 0 for some E {Q} 2 Po 0,

---

Published as a conference paper at ICLR 2025
Assumption 2 satisfied. The diameter satisfies diam(Xt; ma ( | H2 2
Finally, we assume Assumption [ (no dominated action for the agent). Then, Theorem bounds on the approximate- upproximate-bes-rrspposs objectives in Bayesian persuasion:
gives
Corollary 5.1 (Bayesian persuasion with approximate best response). For 0 S <.6<%
Gpn
(B) z U - 2B(1 + 2 and OBJ
R (5) 2 U
4B
(1 (1
po ))
po G
OBJ (8) & OBJ R (6) - U 2B(1+ Po E
Further applying Theorem 3.1 and 3.4
we obtain the central result for motivating problem,
persuasion with a learning agent:
Corollary 5.2 (Persuasion with a learning agent), Suppose T is sufficiently large such that
CReg(T)
Gpo and (SR
< _00 then
Gpe
with contextual no-regret learning agent, the principal can obtain utility at least
1 -E u(e aa)] 2 ²OBJR (ReE((T) 2 U 4B
2) Po
CRe
using a fixed signaling schemes in all rounds.
with contextual no-swap-regret learning agent, the principal's obtainable utility is at most
u(x', d')] OBJ CSReg(
I U + +BB(1 + 2 CSReg(T)
Po
even using adaptive signaling schemes.
Result (9) is particularly interesting. First, it shows that the principal cannot exploit no-swap- regret learning agent beyond U + o(1) even if the principal has informational advantage (knowing the state w). Second, this result still holds even if we allow the principal to see the agent's s strategy p² before choosing the signaling scheme n². The principal still cannot exploit the agent this case.
Stackelberg games and contract design. When applied Stackelberg games and contract de- sign, our results show that the principal can obtain U -
CReg(T) T
against a no-regret agent and
no more than U + CSReg(2) against swap-rereet agent. These results refine the U + o(1) and U o(1) bounds in Deng al. (2019); Guruganesh al. (2024). See Appendix D details.
This demonstrates the generality and usefulness of our framework.
DISCUSSION
In summary, work provides explicit characterization of the principal's achievable utility in generalized principal-agent problems with a contextual no-swap-regret learning agent. is an asym-
metric range [U+ O(V CSRte(Ti) U O (S ].
We show that this conclusion holds in all generalized principal-agent problems where the agent does not have private information, in par- ticular including Bayesian persuasion where the principal is privately informed. As we mentioned
in the Introduction, the upper bound U + O( (CSReg(() 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 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 non-stationary, like a Markovian environment (Jain & Perchet (024) adversarial dynamic environment (Camara et al.] 2020 In unknown non-stationary vironments, the benchmark U needs to be redefined, and a joint design both players' learning algorithms might be interesting.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Yiling supported by the National Science Foundation under grant no. IIS-2147187 and by Ama- zon. Tao is supported by Siebel PhD scholarship.

---

Published as a conference paper at ICLR 2025
REFERENCES
Jerry Anunrojwong, Krishnamurthy Iyer, and David Lingenbrink. Persuading Disk-Conscious Agents: A Geometric Approach. Operations Research, pp. 2023.2003,,,33, March 2023. URL http::/pubsonniine inn fnforms. ortmm///rg////////// 1287 222 2438
Eshwar Ram Arunachaleswaradl Natalie Collina, and Jon Schneider. Pareto-Optimal Algorithms for Learning in Games. In Proceedings of the 25th ACM Conference on Economics and Computation, pp. 490 510, New Haven CT USA, July 2024. ACM. URL https: //ddpa://dd... ww...acc...m crg//oi// 10. 09..115/3677855.333
Jean-Y Yves Audibert and Sébastien Bubeck. Regret Bounds and Minimax Policies under Partial Monitoring. Journal of Machine Learning Research, pp. 2785-2836, 2010. URL http://
jmlr. wmi..org/papers/////mm http////aabbeet...ttmmm.
Peter Auer, Nicolò Cesa-Bianchi. Yoav Freund, and Robert E. Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM Journal on Computing, pp. 48-77. January 2002. URL
http://epubs. siam. wwtp://g///ooooooooo 0t00:/00..133/000075519003333330
Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Ceggre-Minimiziig Bayesian Persuasion. In Proceedings of the 22nd ACM Conference Economics and Computa- tion. pp. 128-128, 128, Budapest Hungary, July 2021. ACM. URL httpp:://d/ acm. www.laacc....o....ommoo doi/
10. 1145/ 34 3465446.644..4 3467574]
Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Markov persuasion processes: Learning to persuade from scratch. arXiv preprint arXiv:2402.03077, 2024.
Daniel J Benjamin. Errors in probabilistic reasoning and judgment biases. Handbook of Behavioral Economics: Applications and Foundations 2:69-186, 2019.
Avrim Blum and Yishay Mansour. From External to Internal Regret. Journal of Machine Learning Research, pp. 1307-1324, 2007. /
um07
html
Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Seliberr.SSelligggnggg to No-Regret Buyer. In Proceedings of the 2018 ACM Conference on Economics and Compulation, pp. 523-538, Ithaca
NY USA, June 2018. ACM. URL hattss://dl aww.aacm.ooo.
3219233
George W. Brown. Iterative Solution of Games by Fictitious Play. In Activity Analysis of Production and Allocation. Wiley, New York, 1951.
Linda Cai, S. Matthew Weinberg, Evan Wildenhain, and Shirley Zhang. Selling to Multiple No-Regret Buyers. In Web and Internet Economics, pp. 113-129 Cham, 2024. Springer Nature Switzerland. URL vittps://lime springer com / 10077 978- 118-3-031-4897--
Modibo K. Camara, Jason D. Hartline, and Aleck Johnsen. Mechanisms for a No-Regret Agent: Beyond the Common Prior. In 2020 IEEE 6l Annual Symposium on Foundations Computer Science (FOCS), pp. 259-270, Durham, NC, USA, November 2020. IEFE. URL. https:// leeexplore ieee. org/ http///ccmmmm///11c/ 93319992/
Colin Camerer. Bounded rationality in individual decision making. Experimental economics, 1: 163-183, 1998.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian Persua- sion. In Advances in Neural Information Processing Systems, pp. 16188 16198, Curan Asso- ciates, Inc., 2020. URL https: http:::::ppppppceiiieeeee wwwrips.....ppp..p. hc/p:a/ee///22///1eee ba5451 (1:55d3::911 a 982
pdff
Vincent P. Crawford and Joel Sobel. Strategic Information Transmission. Econometrica. pp- 1431, November 1982. URL hhtps:: hattps://ww. //www. jstor.
crossref
12

---

Published as a conference paper at ICLR 2025
Geoffroy de Clippel and Xu Zhang. Non- Non-Bayesian Persuasion. Journal of Political Economy, pp- October 2022. URL httpps: //Mp:::/www... /ww..
1086/720465
Yuan Deng, Jon Schneider, Learners In Advances in Neural Information Processing Systems. Curran Asso- ciates, Inc., 2019. URL httpss//pppooeeeiggs..eeee.rr newripss httpp//wwws..ccpppee/////////11 49e67 49e6730
Balasubramanian Sivan.
Strategizing against No-regret
pdff
Piotr Dworezak and Alessandro Pavan. Preparing for the Worst but Hoping for the Best; Ro- bust (Bayesian) Persuasion. Econometrica, pp. 2017-2051, 2022. URL sttps://wwnt
Yiding Feng, Wei Tang, and Haifeng Xu. Online Bayesian Recommendation with No Regret. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 818-819, Boul- der CO USA, July 2022. ACM. URL https: pestps://dll. /dl. acm. org/ www./oo..... 111.0...111111
3538327
Yiding Feng, Chien-Ju Ho, and Wei Tang. Rationality-robur information design: Bayesian per- suasion under quantal response. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 501-546. SIAM, 2024.
Drew Fudenberg and David K. Levine. The theory of learning games. MIT Press series on economic learning and social evolution. MIT Press, Cambridge, Mass, 1998.
Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Robust Stackelberg Equilibria. Proceed- ings of the 24th ACM Conference on Economics and Computation, pp. 735 London United Kingdom, July 2023. ACM. URL https://dl. acm. wtt//oi/goooooooo/o////
http/doi/10e /10. 100.00..115558888
3597680
Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Generalized prineipal-agency. Contracts, information, games and beyond. In Proceedings of the 20th Conference on Web and Internet Economics, WINE '24, 2024.
Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasiin Vasileios Vlatakis- Sannkis-Gkaragkoumii. Joshua Ruizhi Wang, and S. Matthew Weinberg. Contracting with Learning Agent. In The eighth Annual Conference on Newral Information Processing Sys- tems, 2024. URL htttge///oppeeeiieeeeeeeffrooooo
Keegan Harris, Nicole Immorlica, Brendan Lucier, and Aleksandrs Slivkins. Algorithmic Per- suasion Through Simulation: Information Design in the Age of Generative AI. arXiv preprint arXiv:2311.18138, 2023.
Sergiu Hart and Andreu Mas-Co.ell. A Simple Adaptive Procedure Leading Correlated Equilib- rium. Econometrica, pp. 1 1127-1150, September 2000.
www.w.wwe............ com/1c.
1111/1468-0263 T 00153
Shinji Ito. A Tight Lower Bound and Efficient Reduction for Swap Regret. In Ad- vances in Neural Information Processing Systems, pp. 18550-18559, Curran Associates, Inc.,
2020. 2Lc24488888881111044441131300220
files/paper/20277 pdf
Atulya Jain Jain and Vianney Perchet. Calibrated Forecasting and Persuasion. In Proceedings the 25th the ACM Conference on Economics and Computatioon, pp- 489-489, New Haven CT USA, July 2024.
4894
ACM. URL pattps://ae acm. httpa//t............11111//////1 367777770866666655553553
Emir Kamenica and Matthew Gentzkow. Bayesian Persuasion. American Economic Review, pp. 2590-2615, October 2011. URL
aeaweb. www.wwwwwww/w////..././////
/t/////i////// /ttp://..rrrroo///..2/////// 1257/aer.
101. 25900
B. H. Korte and Jens Vygen. Combinatorial optimization: theory and algorithms. Algorithms and combinatorics. Springer, Heidelberg: New York, 5th ed edition, 2012.
13

---

Published as a conference paper at ICLR 2025
Svetlana Kosterina. Persuasion with unknown beliefs. Theoretical Economics, pp. 1075 110,, 2022. URL
Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. Strategically-Robust Learning Al- gorithms for Bidding in Prist-Price Auctions. In Proceedings of the 25th ACM Conference Economics and Computation, pp. 893-893, New Haven CT USA, July 2024. ACM. URL httpss:/dd acm. wtt//oi////oooooooooooo 10. 11145166708653 3673514
Tao Lin and Ce Li. Information Design with Unknown Prior. In Proceedings of Innovations in Theoretical Computer Science, 2025.
Yue Lin, Wenhao Li, Hongyuan Zha, and Baoxiang Wang. Information design in multi- re- inforcement learning. Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL WtR.https::// httptttss///pppeeeeieeee http:/rwwwwweeeeeeeeeeeeeeeeeeee forum? httt://oruummsooooyyyttttt d=NyQwBttTnG
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against Learners in Bayesian Games. In Proceedings of Thirty Fifth Conference on Learning Theory, Proceedings of Machine Learning Research, pp. 5221-5252. PMLR, July 2022. URI. https:
7/proceed hgs..... m1 p.esss /v1 78 wwt./mnnnuuuu/mmm 22..arrrr22.2........ html.
Richard D. McKelvey and Thomas R. Palfrre. Quantal Response Equilibria for Normal Form Games. Games and Economic Behavior, pp. 6-38, July 1995. URL
elsevier wwm /ttpe//c...coo/eereeeeee//////33
Roger B Myerson. Optimal coordination mechanisms in generalized principal-agent problems.
Journal of Mathematical Economics, pp. 67-81, June 1982. URL https://Linkinghu.)
alsevier.. com/ http:///eetteeeee//////000033300 /ttpaaaiiaaaaaaaaa0//00400000020
Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. Econometrics for Learning Agents. In Pro-
ceedings of the Sixteenth ACM Conference on Economics and Computation EC '15, pp. 1-18, Portland, Oregon, USA, 2015. ACM Press. URL http:/ //ll://dl... a wtt.aaa......aatitiooo/oo/ cfm? do1d=2764468. 0.1.8.7665222
James Renegar. Some perturbation theory for linear programming. Mathematicaal Programming, pp. 73-91, February 1994. URL htt.: http://link //innk.//nn.... springer. cwm/commoo//...o 10. httmm/00.1007/F01551111111
Aviad Rubinstein and Junyao Zhao. Strategizing against No-Regret Learners in First-Price Auc- tions. In Proceedings of the 25th ACM Conference on Economics and Computation, pp. 894- 921, New Haven CT USA, July 2024. ACM. URL /tt.//ll.aa/ acm. org/doi/11. 07770665.377366
Antoine Scheid, Aymeric Capitaine, Etienne Boursier, Eric Moulines, Michael Jordan, and Alain Oliviero Durmus. Learning to mitigate externalities: the coase theorem with hindsight rationality, In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: Pietps://ol
Tyler Lu, David Pal, and Martin Pal. Contextual Multi-Armed Bandits. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. pp. 485-492, PMLR, March 2010. URL (ttLhttss: http::::://prooeedi.nggo mlr. wttps//ns...........pp.p..... ptwss//9//lllsee
.ttll
Bernhard Von Stengel and Shmuel Zamir. Leadership with commitment to mixed strategies. Tech- nical report, Citeseer, 2004.
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan, and Haifeng Xu. Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 471- 472, Boulder CO USA, July 2022. ACM. URL https:/ /dl......... www.aamm.oorg. wttp/oo//oooooooooooooo 3490486. 353831
Kunhe Yang and Hanrui Zhang. Computational Aspects of Bayesian Persuasion under Approxi- mate Best Response. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
ew net. ott.:eeeeeeeeoroooooooooooooooo.
14

---

Published as a conference paper at ICLR 2025
Gabriel Ziegler. Adversarial bilateral information design. Technical report, 2020.
You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to Persuade the Fly: Robustness Against Ignorance. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 927-928, Budapest Hungary, July 2021, ACM. URL http:://dd..a..rggg//o
1145/346545.. 3467593)
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORKS
Learning agents have been studied in principal-agent problems like auctions (Braverman ct al. 2018
Cai et al., 2024, Rubinstein & Zhao 2024, Kumar al.] 2024). bimatrix Stackelberg games (Deng
et al., 2019: Mansour et al., [022]] Arunachaleswaran et al., 2024), contract design (Guruganesh
et al. 2024 Scheid et al. 2024), and Bayesian persuasion (Lin et al., 2023] Jain & Perchet 2024).
These problems belong to the class of generalized principul-agen/ problems (Myerson] 1982, Gan
jet al., 2024). We thus propose a general framework of generalized principal-agedn problem with a
learning agent, which encompasses several previous models, refines previous results, and provides
new results.
Camara et al. 2020) also propose general framework of principal-agent problems with learning players, but has two key differences with ours: (1) They drop the common prior assumption while still keep it. This assumption allows to compare the principal's '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. (2019) show that the follower's no-swap-regret learning can cap the leader's utility at +*+0(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. (022) 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 (Camara et al.)
2020| Ziegler 2020 Zu et al. 2021 Kosterina 2022 Wu et al.] 2022, Dworczak & Pavan 2022 Harris et al. 2023 Lin & Li 2025) and known utility (Babichenko et al. 2021 Castiglioni et al.
2020 Feng et al.
2022 Bacchiocchi et al., 2024) are relaxed. For the receiver, the receiver may make mistakes in Bayestan updates (de Clippel & Zhang 2022), be risk-conscious wAnunrojwong
ct al.
2023), do quantal response (Feng et al. (024)) or approximate best response (Yang & Zhang Independently and concurrently of us, Jain & Perchet (2024) also study Bayesian persuasion
2024
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 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 '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- -eetely---e---ssddiing agents in Stackelberg games (Gan et al. (203) and Bayesian persuasion ( (Yang& & Zhang, 2024). We focus on the range of payoff that can be obtained by a computationally-unbbe unbounded principal, ignoring the computational aspect considered by Gan et al. (2023); Yang & Zhang (2024). Besides the "maxmin/robust" objec- tive, 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.
B DETAILS ABOUT CONTEXTUAL
ALGORITHMS
Contextual (eo(swap-)reggeee algorithms can be constructed by running an ordinary rregeet
algorithm for each context independently. Since algorithms with O O(VT) (swap-)regret exist under bandit feedback (Audibert & Bubeck 2010 Ito 2020), they lead to algorithms with O(v [STT) contextual (swap- Jregret. This is tormalized by the following proposition:
Proposition B.1. There exist learning algorithms with contextual regres CReg(T) = OOV|AI|SSTTT and contextual waa-reegeet CSReg(T) = O[[A] ((T)). They can be constructed by rumning an ordinary (wwwwwrregre multi-armed bandit algorithm for each context independently.
We prove Proposition B.I in the rest of this section.
16

---

Published as a conference paper at ICLR 2025
Let A be an arbitrary no-regret (no-swap-regret) learning algorithm for multi-armed bandit (MAB) problem with |A| arms. There exist such algorithms with regret O[yT]A] log [A]] (variants of Exp3 (Auer et al. 2002) and even O(VT(AAl) (doubling trick + polyINF (Audibert Bubeck 2010 for any time horizon T' > O. By swap-to-external regret reductions, they can be converted to multi-armed bandit algorithms with swap regret O A [4]
(Blum & Mansour 2007) and
O(IAlvT) (Ito 2020 We then convert A into a contextual no-regret (contextual no-swap-regret) algorithm, in the following way:
Algorithm 1: Convert any MAB algorithm to a contextual MAB algorithm
Input: MAB algortihm A. Arm A. Context set S. Instantiate [S] copies , Ais) of A, and initialize their round number by 6
|is = 0.
for round / = 1.2.... do
Receive context s². Call Ag to obtain an action a'. Play a' and obtain feedback (which includes the reward v' (a'") of action a²). Feed the feedback to Ast. Increase its round number tgt by 1.
end
Proposition B.2. The contextual regret of Algorithm 7 is at most
19]
CT) S max
Σ
(T.)
Ti + ... + Tis T].
8=1
where Reg(T,) is the regret of for time horizon Te. The contextual swap-regret of Algorithm 1 is at most
CSReg max Σ SReg(T.) Ti .....44 Tis = =T]
where SReg(T.) is the swap-regret of for time horizon Te.
When plugging in Reg(T,) = 10.00(1/V/) [T]T.), we obtain CRog (T) < (((SST
When plugging in SReg(T,) = V(IA),T,), we obtain CSReg(T) < (STT).
Proof. The contextual regret of Algorithm !
is
T
CReg(T) = max d-
E
(d v'(a))
t=1
[S|
- Σ -
max
d:S-A
tistms
[s|
max E e'EA
Σ
1=s==s
|S||
Er, [T)g(T))]
where Ts is the number of rounds where s'
[s|
R.g(T))) Ti +...... + Tist = T
< max
When Reg(T.) = O(v A.), by Jensen's inequality we obtain
[s| Σ O(VIAT)) < <(VIAA)VSS
[S]
CReg(T) <
Σ
T.
17

---

Published as a conference paper at ICLR 2025
The argument for contextual swap-regret is similar:
T
CSReg(T)
max d-SAA=A
E
(w (d(s) -
|S|
() - o'(a'))
max
dSXA-A
s=1 1:8
|8|
max E d'AAAA
Σ (((d(d)))''aa)))
f:s==s
|s|
Er. [SReg (T:)
where T3 the number of rounds where s
[s|
(Reg(Ta) t.. +7 = 7]
S max
When SReg(T,) = O(IAIVT) T.). by Jensen's ' inequality we obtain
CSReg(T) S Σ 5
Σ T. = O(IAIVISTT
C EXAMPLE OF APPROXIMATELY BEST RESPONDING AGENTS
Our model of approximately-beee cestinattell-ee---eseeeeee -e----resesddinngg agent (Section 3.1 includes, for example, two other models in the Bayesian persuasion literature that also relax the agent's s Bayesian rationality assump- tion: the quantal response model (proposed by (McKelvey & Palfrey 1995) in normal-form games
and studied by (Feng et al. 2024) in Bayesian persuasion) and model where the agent makes mistakes in Bayesian update de Clippel & Zhang 2022):
Example C.I. Assume that the receiver's utility is in [0, 1]. In Bayesian persuasion, the following receiver strategies are d-best-responding:
Quantal response: given signal S, the agent chooses action A with probability exp(Av((..e) with À > This strategy belongs to R&((T) with 1++og(|A(2)
Eveca ax
Inaccurate belief: given signal E S, the agent forms some posterior μl, that is different yet close the true posterior ps in total variation distance dTv Ma)) S e. The agent picks an optimal action for p'g. This strategy belongs to (TT
Proof. Consider the quantal response model. Let y A))((A Given signal s, with posterior μas
we say an action E A is not 7-optimal for posterior μlg if"
ups, v(Ms, a) 2 7
where o is an optimal action for ua. The probability that the receiver chooses not 7-optimal action is at most:
exp(Au(();a))
exp(Xu(He,a)) exp (- (-Xoo(u..))-ouuu.)e))
olus,
exp( 1
EnEA exp(\u((s;a)) exp(Xu((s, a)))
AA|x*
By union bound, the probability that the receiver chooses any not 7-approxiamtely optimal action is at most $. So, the expected loss of utility of the receiver due to not taking the optimal action is at most
)
1 ā 5 +
log(I ()) +1
(1 (1- .
18

---

Published as a conference paper at ICLR 2025
This means that the quantal response strategy is [og([A[A)+1 best-responding randomized strategy-
Consider inaccurate belief. Given signal s, the receiver has belief ní with total variation distance drv(p's (a) S to the true posterior Mg. For any action E A, the difference of expected utility of action a under beliefs Jl, and js is at most
Euwn [u[ a)] Eusp [u( a)ll S drw Ma) S
So. the optimal action for n², is 25-optimal action for Ma This means that the receiver strategy is deterministic 2e-best-responding strategy.
D ADDITIONAL DETAILS ON APPLICATIONS TO SPECIFIC PRINCIPAL-AGENT PROBLEMS
D.1 STACKELBERG GAMES
In Stackelberg game, the principal (leader), having finite action set B, first commits to mixed strategy x = (I DoeB E (B)), which is a distribution over actions. So the principal's decision space X' is (B). The agent (follower) then takes an action a E A in response to x. The (expected) utilities for the two players are u(x, a) he Zbbju(b, a) and v(x, a) = Eee n ub,ju(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)l < B. Then, the principal's utility function u(2r, a) is bounded in [-B, B] and (L = B)-Lipcchitz in æ. The diameter diam(X)) = max,, Applying the thcorem for unconstrained generalized principal-agent problems (Theorem 4. and the theorems for learning agent (Theorem 3.1 and 3.4), we obtain:
||]] - x2l11 S 2.
Corollary D.1 (Stackelberg game with a learning agent). Suppose T is sufficiently large such that CReg(T) G and CSReg(T) < G, then:
T
with a contextual no-regrer learning
agent.
the
principal (Reg(T) using a fixed strategy T
can obtain utility
1
1 ulxt, ,a)) OBJ R CReg(T)
2 U
AB
VG
in all rounds.
with contextual no-swap-regret learning agent, the principal cannot obtain utility more than E E u(x',a')] s OBJ" (SRRe((T)
E
U
2B CSReg(T) even using adaptive strategies.
T
T
The conclusion that the principal can obtain utility at least U - o(1) against no-regret learning agent and no more than U* o(1) against no-swap-regret agent in Stackelberg games was proved by (Deng et al. 2019). Our Corollary D.I reproduces this conclusion and moreover provides bounds
the o(1) terms, namely, U O(v (Reg(T)) and U O CSR This demonstrates the generality and usefulness of our framework.
D.2 CONTRACT DESIGN
In contract design, there is finite outcome space O= (ri...., where each a monetary reward to the principal. When the agent takes action E A, outcome r; will happen with probability
Pai 2 0. Σd= Pas 1. The principal cannot observe the action taken by the agent but observe the realized outcome. The principal's 's decision space X' is the set of contracts, where a contract (z
[0, +oo is vector that specifies the payment to the agent for each possible outcome. So, the agent takes action under contract x; the principal obtains expected utility
u(x, a) Σ Pri 2(6))
and the agent obtains v(2, a) Ed A= Pai Ca. where c. 2 0 is the cost of action A for the agent. The signal s can (but not necessarily) be an action that the principal recommends the agent to take. The principal's decision space X' C [0, +oo in contract design, however, may be unbounded
19

---

Published as a conference paper at ICLR 2025
and violate the requirement of bounded diameter diam(X)) that 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 < too, so S z(() S P and X' = PI Under this requirement and the as- sumption of bounded reward |ral I R. the principal's utility becomes bounded by [u(z, a)l S E Por (R + P) = R P = B and (L 1)-Lipschitz under fo -norm:
(( a0 a)l Σ - s máx (1(()) T2(i)
Pat = | 1101-221 x21100 (10)
==1
And the diameter of is bounded by (under -norm)
max ||x] Ø22loc 21,22EX'
max
max (1(() x2(0) S P. PM ==1
d
(1I)
Now, we can apply the theorem for unconstrained generalized principal-agent problems (Theo- rem 4.1p and the theorems for learning agent (Theorem 3.1 and Theorem to obtain:
Corollary D.2 (Contract design (with bounded payment) with learning agent). Suppose T is suf- ficiently large such that CReg
PG and CSReg(T) G. then:
2[R+P)
T
with a contextual no-regret learning agent, the principal can obtain utility at least T |E u(x',"")] 2 OBJ CRey(T) 2 U - U--22 2/ 21RPPPP /CReg(T) using a fixed con-
G
T
tract in all rounds.
with contextual a no-swap-regrel learning agent, the principal cannot obtuin utility more than E E u(xt, a²)] S OBJ" (SSRer()) U CSReg(T) even using adaptive contracts.
T
The second remedy is to write contract design as a generalized principal- aggett problem another +oo) |A| be vector recording the expected payment from the principal to the agent for each action a E A:
way. Let (a )aen [0,
d
((a)
(a)
(12)
And let i(a) be the expected reward of action P(a) = Ei=1 Paits. Then, the principal and the agent's utility can be rewritten functions of z and
u( a) -(a)) [()):
a( i())) Ca.
(13)
which are linear (strictly speaking, affine) in ã E X. Assuming bounded reward (a()) < R, we can without loss of generality assume that the expected payment Z(a) is bounded by as well, because otherwise the principal will get negative utility. So, the principal's decision space can be restricted to
X (a 3
[0, +ooj such that (0) Σ Pai for every A] n [0, R714),
(14)
which is convex and has bounded diameter (under loo norm)
(a: S diam || (=)))
(15)
The utility function u(ō a) bounded by 2R and (L -)-Lipshiitz (under Loo norm):
[u(ā1, a) u [22 a) [āx{a)) 22(4)| < max [ā1(a) x2(4)} = | io loo.
(16)
a
Thus, we can apply the theorem for unconstrained generalized principal-agent problems (Theo- rem and the theorems for learning agent (Theorem 3.1 and Theorem 3.4h to obtain:
Corollary D.3 (Contract design with a learning agent). Suppose T is sufficiently large such that CReg(T) G and CSReg(T) < G, then:
2
20

---

Published as a conference paper at ICLR 2025
with contextual no-regret learning agent, the principal obtain utility at least JE + ula', ,a)) OBI (Ree!T) U
4R
(Reg(T) using fixed contract in T
VG
all rounds.
with contextual no-swap-regre learning agent, the principal cannot obtain utility more than | u(xx, & OBJ (CSReg(T)) SU*
CSReg(T) even using adaptive contracts.
Providing the quantitative lower and upper bounds, the above results refine the result in (Guruganesh et al. 2024) that the principal can obtain utility at least U o(1) ) against no-regret learning agent and no more than U o(1) against no-swap-regret agent. This again demonstrates the versatility of our general framework.
MISSING PROOFS FROM SECTION 3
PROOF LEMMA
Since n' π is fixed, we have o5 TT and x Ds. Vs E S. The regret of the receiver not deviating according to d is:
u( d(s')) v(x', ae)))a ΣΣ
T Σ
Puja (v(2e,, (iissooas,, d(s)) v(xg) a))
1=1 +88
aaA
Σ T
Etsp Pale
(1(zs, d(s)) v(212 a))
Σ
1 d(s))
Σ T
plals)u(zz))) ((z,d)-V(m) aEA
Σ
SSS
SES
Here, d is interpreted as an agent strategy that deterministically takes action d(s) for signal 8.
By similar derivation,
that the principal's expected utility is equal to >T Ei Pale u(x,, (TT which proves the
E E u(x', .o)) lemma.
Eoes n, ELEA
E.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 (ot)T_ for the T rounds, where each of is mapping from the history - (s', a".'"" [ (including past signals and actions) to single-round strategy x' for round t. Given any function CSReg(T), let 5 = 2T
CSReg(T) We construct the following algorithm. A
for the agent: at each round t, given history h (-1 = (s', a [=)
If the single-round strategy chosen by the principal at round is equal to n" = chht then the agent plays strategy p² arg min U(= namely, randomized ò-best- responding strategy that minimizes the principal's utility.
If the single-roum round strategy chosen by the principal round then the agent switches to any existing contextual no-swap-regret algorithm with swap regret at most CSReg(T) (see Proposition B.1 for examples of such algorithms).
equal xí o (h'--1),
We show that the agent's algorithm has swap regret at most CSReg(T) matter what strategy the principal uses:
If the principal keeps using strategy namely, each round the principal uses single-round strategy n' = o¹ (h'-1), denoted by {(*{f Less then the agent will respond by strategy p². For any deviation function d: S A A, the expected regret of the agent not deviating according
21

---

Published as a conference paper at ICLR 2025
to d in this round is
Blu(s', d(s', a²)) v(x'' [d]]== RE
Σ
T
Σ p (als)
(o(x d(s.a)) - a))
#ES
acA
E
Σ
pf (als)u((ss (()
Σ
Σ
EES
REA
dES
aEA
Te maxu(1 a) - -E n3 E (((als)((ass
E
SES
sE8
aEA
1 --1
Σ
Te max vis a) V(. |D]
aeA
SES
< E
0
because by definition, p' E Ro((T)) = V(=', 2 Σ
max ( a) a) -6. aEd
SES
Summing over all T rounds, we obtain:
Σ Blu(2' d(s", d(s",a')) - o()', T5 CSReg(T)
2
If the principal does not play according to in any round, then the agent will switch to algorithm with swap regret at most CSReg(T)
so the total swap regret of the agent is most:
2
T5 + CSReg(T) < CSReg(T),
which proves that the agent's 's learning algorithm has swap regret at most CSReg(T).
The principal's average utility, when the principal uses strategy and the agent uses the above no-swap-regret algorithm, is
1
Elu(x' a²)
1
E E
Σ
T Σ
Ep'
('alssu((z(,a)
T
T
t=1
$E8
a
T
E
U(T", :p']
T
[=1
T
1
<
EB
sup
min UTT pERa(=)
because pl E arg U .P) rcRa(m*)
T
1=1
sup
min (ERa(m)
U(T,P)
OBJ
OBJ CSReg(T")
2T
E.3 PROOF OF THEOREM 3.4
Proof. Let pi. = Pr(s' = = = E = >] = =E[T7] be the probability that signal & E S is sent in
be the probability that the agent takes action a conditioning on signal 8 being sent in round f. Let : S x A A be any deviation function for the agent.
round t. Let p%11= = Pr(a' = a =
22

---

Published as a conference paper at ICLR 2025
The utility gain by deviation for the agent is upper bounded by the contextual swap-regret:
CSReg(T)
E
u(xx, d(s", d(s" - e(2' e(z',a'))]
(17)
T
1
Pals E x1| |at [((at,
[o d(s, v(25 a)
T
SES
Pajs (u(B[ry)s' = s).d(s, - o = =s),a)
by linearity of u(:: a)
T
SES
REA
Σ
j= PaPPop
T Σ PéPlos
0/2
(U(Elriss* s), 0)) "E[[s|ss' s) a)
T
Ej=1 PoP
NEA
Ej=1 PePlas a/s
r
ΣT piP F d(ssa)) v
E p P' Σj virui
. )
T
#EA
ΣT 11-1
> 201m Pipa 2lo
Define 2s,a
and Vs.a
X. Then the above is equal
Σラ P.
ΣΣ
Is,a u(Vo,a, a(s,a) v vVo,a; a))
(18)
sESaEA
Σ E.cs Eoca 1. so g is probability distribution over
We note that EsES EaE Is,a A. And note that
T
T
Σ
Blg =]
Is,aVs.a
T
T
5.0ESXA
t=1
1=1
SES
T
1 T
T
[[s
s|x']
[ss = s|zl]
E x
T
T
-T
SES
SES
1
Σ T
T EC
because
In'''es C.
SES
SES
This means that T'' = a(g,.a Vv.a)) (a.a))aa))ssx defines a valid principal strategy with the larger signal space S x A. Then, we note that (18) is the difference between the agent's expected utility under principal strategy n' when responding using strategy d S x A A and using the strategy that maps signal (s, a) to action a. And (88 upper bounded by CSReg(T) by
18 = V(=', V( (s,a) < CSReg(T)
Vd:SxA+A
(19)
In particular, this holds when d the agent's best-responding strategy. This means that the agent strategy (s, a) - a is a (SReg(T) >-best-response to n'. So, the principal's 's expected utility is upper bounded by the utility in the approximate-best-resse
model:
u(x", ad)]
1
ΣΣ
P' P = a)
T
1=1
SES
aEA
ΣΣ
as ((, ( a) S SBBJ
R CSReg T)
T
a
E.4 PROOF OF THEOREM 3.5
The instance has states (A, B). actions (L, M, R), uniform prior (A) = (Bo = 0.5, with the following utility matrices (left for sender's, right for receiver'st s):
23

---

Published as a conference paper at ICLR 2025
u(w,00 a)
M
v(w. a)
L
M
A
0
-2
-2
A
2
B
Claim 2. In this instance, the optimal sender utility U in the classic BP model is and the spproximaate-eet-respowe objective OBJ = 0(r).
Proof. Recall that any signaling scheme decomposes the prior μe into multiple posteriors {ps Jes. a posterior puts probability > 0.5 to state B, then the receiver will take action M, which gives the sender utility s 0; if the posterior μa puts probability action the receiver takes, the sender's expected utility on μ4, cannot be greater than O. So, the sender's s expected utility z under any signaling scheme. An optimal signaling scheme is to reveal no information (keep Ms μo); the receiver takes R and the sender gets utility O.
0.5 to state B, then matter what
This instance satisfies the assumptions of Theorem 4.2 so OBJ (7) S U 0()) = O(7).
Claim 3. By doing the following, the sender can obtain utility ~ 1 - 0(v)) if the receiver is y m-mann-based learning:
in the first T/2 rounds: if the state is A, send signal 1; if the state is B, send
in the remaining T T/2 rounds, switch the scheme: the state is send 2; if state B, send 1.
Proof. In the first 7/2 rounds, the receiver finds that signal corresponds to state so he will take action L with high probability when signal is sent; signal 2 corresponds to B so he will take action M with high probability. In this phase, the sender obtains utility ss 0 per round. At the end this phase, for signal the receiver accumulates utility ? 2 vy for action L. For signal 2, the
receiver accumulates utility 1 1 _ for action M.
In the remaining 2/2 rounds, the following will happen:
For signal 1, the receiver finds that the state is now B. so the utility of action decreases by every time signal is sent. Because the utility of L accumulated in the first phase was x / after / rounds in second phase the utility of L should decrease to below 0, and the receiver will no longer play L (with high probability) at signal 1. The receiver will not play M at signal in most of the second phase either, because there are more A states than B states signal historically. So, the receiver will play action R most times, roughly T. 4 T rounds.
T This gives the sender total utility of ~ (T 7 V7) 2
O(T
For signal 2, the state now A. But the receiver will continue to play action M in most times. This because: has utility 0: L. accumulated s utility in the first phase, and only increases by /7 per round in the second phase, so its accumulated utility is always negative; instead, M has accumulated I utility in the first phase, and decreases by I every time signal 2 is sent in the second phase, so its utility positive until near the end. So, the receiver will play M. This gives the sender utility 0.
Summing up, the sender obtains total utility (T) these two phases, which is (( > 0 per round in average.
The above two claims together prove the theorem.
24

---

Published as a conference paper at ICLR 2025
F MISSING PROOFS FROM SECTION 4
F.1 PROOF OF CLAIM
no G > 0 satisfies the claim, then there must exist an ag E A such that for all x E A, v(00, 14)
v(a', p) v 0 for some a' E EA\ {ao). Namely,
max min {u(s, ao) - v(x, a') So. #eX a'E))(a))
Then, by the minimax theorem, we have
min max (o(2, au) - v(z a')} a'E FE
max =E d'Ed((aa}
min
{u(x, ao) v(2, s 0.
This means that do is weakly dominated by some mixed action a' E EA(A) {aa)), violating As- sumption T
F.2 PROOF OF EXAMPLE
We use the probability E [o, 1] the Good state to represent a belief (so the probability Bad state is 1 - p)).
First, the sender's optimal utility when the receiver exactly best responds is 2/4p:
U
240
This is achieved by decomposing the prior 1Ag into two posteriors Pa = and μs with proba- bility 2/4 and 1 - 2p0 respectively, with the receiver taking action a under posterior Pa and under pbb.
Then, consider any signaling scheme of the sender, т {(T,) Ms) which is a decomposition of the prior μi into |S] posteriors μa E [0. 1] such that E.es TTll, = μo. Let p S ((A) be randomized strategy of the receiver, where p(a]s) (and p(b]s)) denotes the probability that the receiver takes action a (and b) under signal 8. The sender's expected utility under and is:
U(T, p) = Σ Te[p(a|s) + p(b(s)
Σ Tap(a)s).
(20)
SES
SES
The receiver's 's utility when taking action posterior μe is ue 1 (1 Uo) (-1) = 2/1 1. So, the receiver's expected utility under π and is
V p) = Σ n. [p(als) (2H, - 1) + p(bls) 0] Σ TTa(ass))22us - 1).
(21)
SES
SES
Clearly, the receiver's best response p² take action a with certainty if and only us 1. with expected utility
V(T,p')= =
Σ T (2 - 1).
(22)
sppp>
To find (6) sup, min U p). we fix any and solve the inner optimization prob- lem (minimizing the sender's utility) regarding p:
min P
U p) > Tsp(als)
SES
s.t. P RI(T)
=
82 -
Σ (2pu -1) s...4
Σ T,p(als)(2 1)- SES
Without loss of generality, we can assume that the solution p satisfies p(als) O whenever Ms Y (if p(als) > for some ns < 1. then making p(als) to be O can decrease the objective
25

---

Published as a conference paper at ICLR 2025
Exes Tap(a]s) while still satisfying the constraint). So, the optimization problem can be simplified
to:
(( = Σ Tep(a|s)
min
s.L.
z
Σ
To (2 - - - Σ 8:11
Tep(a - 1)
Σ
Te (2 - 1)(1 p(als)),
p(als) E [0,1], Vs S: po 3 2
We note that this is a fractional knapsack linear program, which has a greedy solution (e.g., (Korte & Vygen 2012)): sort the signals with μıs > 1 in increasing order of 2/1, (equivalently, increasing order of ua)): label those signals by .,..., n; find the first position k for which Σ (2 1) > 8:
== min {j: Σ T2p2 - 1) > }}};
then, an optimal solution p is given by:
p(als) =
for 8 = 1,..., 1; for $ = k; for
p(a(k) = 6- Et= n. (2 p(als)= =1
Nh (2pk-1)
1,..., 73.
The objective value (sender's expected utility) of the above solution p is
P(T = Σ Tsp(a|s)
8
Σ No (2 - 11) + Σ
B
Th
n
x (2 - 1)
= k++
8
k-1
To (2 1)
2phh
2/1r
s=k
Since the signaling scheme π must satisfy EVES aalls = 140, we have
Σ
P0
Tslls
Talli
Ralts +
#E8
10
s=
Tallao
na
So,
110
Σ
k
Tafaa
8
T (2p, 1)
U(T,p) <
+
14k
2/48
2/1x: 1
4g
8
k-1 1
2/4
U1
2
2p
==1
Since 2p--1
H. Pk
S O for any & S
1, we get
244h -I
(2p, 1)ps
U(T p) <
140
8
f(wx).
14
2/4x -
26

---

Published as a conference paper at ICLR 2025
We find the maximal value of f
5
Take its derivative:
Mx
2pa
((()))
140
26
[VV2 2/Po)uu vPlo [[v2ō 2/uo))u vPl.
PE
(2pk
1)
1E(2/4 -122
which has two roots
VP 225+2
and
vp E (2 when 0 < 5 < m. So, [(x) is V/20-V26
increasing in 12 VPn
2 f is maximized and decreasing in / 11. Since M4
2/ 22
2//60 /28"
VP.
This implies
2/H0- V26
U(T, S 2 /28
Mu
12/11/ v25)
8 VP. 2/100
2/10 - 2/ 2pnd
V/o
v25
This holds for any л. So, (B)R(6) sup, min U(T p) S U 2udd + 5 U ((v8).
F.3 PROOF OF THEOREMS 4.1 AND 4.2
Lower bounds OBJ and upper bounds OBJ (8). First, prove the lower bounds
on (B) and the upper bounds on OBJ (6) in Theorems 4.1 and 4.2, given by the following
two lemmas:
Lemma F.1. In unconstrained generalized principal-agent problem, d
OBJ 2 U
With the constraint EoES TTT, E C, (B) 2 U (diam( (X) + 2B
diam
dist(C,ax)]
G.
Lemma F.2. In an unconstrained generalized principal-agent problem, OBJ" (6) 1 U L
With the constraint Eees Ty C,, OBJ R (8) U (diam(X)) 2B dist (xx G-
diam (X)
The proofs of Lemmas and F.2 are similar and given in Appendix F4 and The main idea to prove Lemma F2 is the following. Let (H, be any pair of principal 's strategy and agent's d- best-responding strategy. We perturb the principal's strategy slightly to be strategy x' for which p is exactly best-responding (such a perturbation is possible due to Assumption [ Since is best- responding to n², the pair (T', p) cannot give the principal higher utility than U (which is the optimal principal utility under the best-response model). This means that the original pair (T,
cannot give the principal utility much higher than U* implying an upper bound on OBJ" (6).
D Upper bounds OBJ (8) imply upper bounds OBJ (8). Then, because OBJ (8) S
OBJ R (0), we immediately obtain the upper bounds on OBJ (8) in the two theorems.
Lower bounds for OB.J (d) imply lower bounds for OB.J (8) Finally, show that the lower bounds for OBJJP(o) (0) imply the lower bounds for OB.J (8), using the following lemma:
Lemma F3. For any 8 > 0, A 0, OBJR (8) > OB. P (A) 286
A
The proof of this lemma in Appendix F.6
Using Lemma F.3 with A
2BG8 diamt
and the lower bound for (B) in Lemma F.I for the
unconstrained case, we obtain:
OBJ (8) 2 (B) - 288 2 U diam ( 2B5 = U 2
2BL diam
which gives the lower bound for OBJ in Theorem 4.1
27

---

Published as a conference paper at ICLR 2025
Using Lemma F.3 with A
2BG8 and the lower bound for (A) in
Ldiam(X)+25 diam(x)
(isx(C.8.))
Lemma F. for the constrained case, we obtain:
OBJ R (6) 2 OBJ (B)
2B4
A 2 U (diam( + 2B diam( (x)
dist 2
2B6
-A
- 22 2B (diam(X)L + 2B diam(2')
(i.t) )o.
This proves the lower bound for OBJR(6) in Theorem 4.2
F.4 PROOF OF LEMMA
Let (x,, p) be pair of principal strategy and agent strategy that achieves the optimal principal utility with an beattl-bbestresponnde agent, namely, (TT, p) = U Without loss of generality p can be assumed to be deterministic, p S + A. The strategy consists of pairs (a)a) that satisfy
Σ SES
No po C.
(23)
and the action a = p(s) is optimal for the agent with respect to Is.. We will construct another principal strategy n' such that, even if the agent chooses the worst ô-best-resoondin strategy n', the principal can still obtain utility arbitrarily close to U - -Ldiamm (X;; (1) + 2B diam(
(C,a)) G
To construct a' we do the following: For each signal E S, with corresponding action = p(s), by Claim I there exists E X' such that u(ee a) (V a') 2 G for any a' # a. Let = & + E [0. 1] for arbitrarily small 0, and let é, be the convex combination of x, and Up(s) with weights 1 0, 0:
x. (1 0)x,, + 0yp(s)-
(24)
We note that p(s) is the agent's optimal action for H. and moreover it is better than any other action a' o a by more than d:
v( u(āe, a') = (1-0){ [
u( a) v(Fe, d')
+ 0 v(Mas a) - v(Va a')l
20 because p(a) is optimal for xt,
2G by our choice of yta
2 20+ AG > G= 8.
(25)
Let yí be the convex combination of {ā.)Es with weights (Tx)a
n'
(26)
SES
Note that μ' might not satisfy the constraint yt E C. So, we want to find another vector z E X and a coefficient 17 [0, 1] such that
n)- + 72 EC
(27)
(If μe already satisfies u' E C. then let 1) 0.) To do this, we consider the ray starting from μ²
pointing towards uo: {e' + t(p0 - w²) Z 0}. Let = be the intersection of the ray with the boundary of X::
x n¹ + + -p'),
t' arg max ft 2 0 n² + t(po 12) x).
Then, rearranging = = nو + 1" (Po n²),
we get
(= n¹) = 14 pl
(1- + 14 CC,
which satisfies (7 with 7 F.
We then give an upper bound on 1) = 1.
Claim 4. c
di) dist(C.a.t
8.
Proof. On the one hand,
||10
μ'll =
Σ Tg Σ TØē. = =11 = n. Ty)()((s) -xz)]l
SES
SES
SES
< 0
T. Up(s)) - 2z|1 < Σ
n diam(X)) = 0. ddiam(X)).
*ES
#ES
28

---

Published as a conference paper at ICLR 2025
On the other hand, because jr' and Mo jl' are in the same direction, we have
|| n'1 = ||2 -oll + A0 μ 2 || paol 2 dist(C, ax)
because Mo is in C and is on the boundary of X. Therefore,
11 || = ||=-p/ S
diam 0. dixt(C,ax))
D
The convex combinations 27 26 define new principal strategy n' with S|++1 signals, consisting
of ã. with probability (1 7) and with probability 7, satisfying Eees(1 g) + 7/
No E C. Consider the agent's s worst (for the principal) 5-best-responding strategies p/ to n':
p' E arg min ('T'' p).
rEPo(rr)
note that pG...) must be equal to p()) for each & S. This is because a = p(s) strictly better than any other action a' # a by margin of 5 (25 so is the only 6-optimal action for E..
Then, the principal's expected utility under T'' and p' is
U p')
26
77)
Σ SES
T. ( . 0 (i+)) + nu(z,
2 (1 11) La p(s)) - -nB
AES
2 (1 11) Σ
Ne (T(((())))s)) -
[ Fo
) nB
SES
=110()p(>) -2, =Adlam))))
2 (1 --- (TT p) - IAdiam(()) BB
2 UU, p) LOdiam (X) -21BB
2 U(T,, p) LOdiam(A') - 2B diam(()) 0
(Claim 4
dix)(C,0x)
UTT p) (Ldiam(X') +2B
diam (X)
) +))
(ist(C
U (Ldiam 2B dist
diam(2))
O()).
So, we conclude that
(6) = sup min U p) 2 min pEDa())
U(T',P)
pEDa(x')
U pd) U
(Ldiam(XX 2B diam(X) XX)
distic.0x) 2/ O(s).
Letting + 0 finishes the proof for the case with the constraint >.es R, E.C.
The case without Eees RTI, E C. is proved by letting in the above argument.
F.5 PROOF OF LEMMA F22
Let æ a principal strategy and p RT(T)) a r-best-responding randomized strategy of the agent. The principal strategy π consists of pairs {(T,,, Jes) with
Σ T. C. SES
(28)
At signal s, the agent takes action with probability p(als). Let 8s,a be the "suboptimality" of action a with respect to Vg;
8saa max (') u(x: d'EA
(29)
By Claim for action there exists yo E X' such that v(ya, a) - v(ya, a') 2 G' for any d' + Let 0,.a and 0z.a:
G4dsa [0, 1] and let H..a be the convex combination of x, and ya with weights 0 0,.a
Fs.a (1 0s,a)ar, + 0s.ala-
(30)
29

---

Published as a conference paper at ICLR 2025
Claim 5. We have two useful claims regarding Hs.a and S
(1) a is an optimal action for the agent with respect to Fs v(Taa, u) - v(Ts.n d') 2 0, Va' E
A.
(2) Exes EnEA Tap(a|s)0an S &..
Proof. (1) For any & a, by the definition of asaa and 0s,a.
For
a) v(Txaa;a)
(1 0s.aa [u a) v(srs a')] 0z,a [u(ya, a) v(ya: a')]
2 (1 02 (-daal + O2 = G+oma
G (-da,a) (-78,a--0aa
+
Bon G 0.
Gtdaa
(2) By the condition that p is a d-best-response to n, we have
N max p S
V(T, - - = Σ #ES
Ta
max d'Ed
d')}
Σ p(al)))((ss)))
aEA
= ΣΣ Σ Tsp(a|s) max { (u(Iz, a') u( v( = ΣΣ
Top(als)os.a
a'En
sESaEA
sESaEA
So, E.Es Eaes {sp(als)0s = EeEs Laes msp(als)
bea G48,aa
S Eoes EaEA Tsp(als) co S
G.
We let yl be the convex combination of {Es,a ba,ESA with weights
Σ
Tap(als)t.a.
(31)
s,aESxA
Note that μí might not satisfy the constraint y E C. So, we want to find another vector 2 E X and coefficient 17 [0, such that
(1 n) + CC
(32)
(f μl already satisfies μí E C, then let 7 = 0.) To do this, we consider the ray pointing from p² to Mot {u' + t(yo - n²) & 2 0}. Let z be the intersection of the ray with the boundary of X::
= == nl + 1- (10 n²);
l" = arg max (1 2 0 n + UNo n²) E X)
Then, rearranging = n¹ + 1s (wo n²), we get
(2 n1) ) μt μl' =
(1 (1- + _ +
4o EC,
which satisfies
32 with F-
We then give an upper bound on r) = 1.
diam(X') Claim 6. 7 (,,,) G-
Proof. On the one hand,
I|40 μ'll = Σ
ΣΣ
Tap(a|s)itanl 1 -
Tep(als)0s,.144 - -xa)l
SES
REAREA
SES aE
TTp(als) 20,a 1|1a x ΣΣ
Claim 5
diam(X) 6
A
SES A
On the other hand, because 2 - 1u' and Po n are in the same direction, we have
||2 - n'|l = ||=-~0o) + I n' 2 || moll 2 dist(C, 8x)
because Mu is in C and z is on the boundary of X. Therefore, 77 A 2 R
dlam(X)) 6
dist(C,82]
30

---

Published as a conference paper at ICLR 2025
define new principal strategy n' (with |S] |A] + signals) consisting of εs.a with probability (1 7)) T s) and with probability 7. Consider the following deterministic agent strategy p' in response to T': for æs.as take action p' (Āx,a) a; for take any action that is optimal for z. We note that p' is a best-response to n', pf E Ro(TT') because, according to Claim 5] is optimal action with respect to Hs.a-
The convex combinations 32
31
Then, consider the principal's 's utility under and p':
U
31
(1 7)
Tap(als)u(Taaa d (Fsja)) + nu(z, #ES a
Σ
Σ
(1
Taplals)u(ūs,as4 - nB
BES a
Tep(als) ((( -
[ 2z
) - nB
sE8 a
=110,,a (va =x 20lllS0nddiamt
2 (1 - (T, - Ldiam(X)
ΣΣ
Tap(als)0.. - nB
SESREA
(Claim 5
UT p) (diam(()) -
(Claim U( p) (Ldiam + 2B
diam(X)) dist(C. G
Rearranging, U( p) S U + (Ldiam(X)) 2B diam(X)) for any pair (T,, p) that satisfies p E (T( And recall that p E Ro(T'). So, we conclude that
dist(C &. Note that this argument holds
OBJ R (6) = max max U(T I max max U p²) + (Ldiam (X; (1) 2B pERa(T)
diam(()
dix)
p'ERO(m)
U (Ldiam(X; (1) + 2B diam
dist(C,ox)
This proves the case with the constraint E.es NgZS C.C
The case without Exes TTI E C is proved by letting = in the above argument.
F.6 PROOF OF LEMMA
Let Ax(=) fa e A u(x, a) a') A, Va' E A} be the set of A A-optimal actions of the agent in response to principal decision E X. The proof of Lemma F.3 uses another lemma that relates the principal utility under a randomized b-bbes-responding agent strategy p E R&(TT) and that under an agent strategy p' that only randomizes over As (1.).
Lemma F.4. Let ग = {(Te, x.)}.Es be principal strategy and E Ra(TT) be a randomized 5-best- response to π. For any A 0, there exists an agent strategy pl s ((A((x))) that randomizes over A-optimal actions only for each Ie, such that the principal's 's utility under pl and satisfies:
[U ((T S 2
Proof. Let m U(I,, a) be the agent's optimal action for x,, Let As (I.) A AA\As be the set actions that are not A-optimal for F.. By the definition that E R5(TT) is a 5-best- response to π, have
8
(())))a))
Σ ((aal))((ss.a)
SE8
aEA
Σ Ws
Σ
p(als)(
r ((xxs - v(Es,a)
Σ
p(als) u(xss - r(Ess a)
SES
(z.)
20
AEA
>4
20 A
Σ T
p(als)
SES
AEAA(RA)
A
AA (x,) (s)
SES
31

---

Published as a conference paper at ICLR 2025
Rearranging,
Σ T As (is) (
88 S
(33)
#ES
Then, we consider the randomized strategy of that, for each s, chooses each action E As (xxz) with the conditional probability that p chooses given a As(2s)
p(a s)
p'(a p(As (I,) 8)
The sender's utility under p' is:
p(a s) (As(
U(F,P')= = E T
E aEAa(s,)
u (F
The sender's utility under p is
p) = Σ Te Σ
p(als)u(I,,,)
+ Σ T Σ
p s)u(xz, a)
SES
aE)a(*.)
SES aEAx(x.)
Taking the difference between the two utilities, we get
(T, p') U(T p)
1
Σ
p(a p(als)u(ss;.)
Σ T
Σ
p(a (s)u(ss)a)) a)
7s ((Aa(1)))
AEAa(z.)
(Z.
p(A (x.)
Σ
N8
((AA(x))
Σ p(als)u(zs,a)
+
Σ Ta
Σ
pla s)u(zona)
SES
(a))(m.)
sES
dEAA(R.)
p(As p(As((.))
Σ p(als) B +
Σ T SES
p(a s) B
(TA
SES
(F))(F.)
(z.) 5) ((AA(T.)
B
(5) ((AA(T)) + B B Topl (Aso(AAaaa (x,) ( (s)
SES
SES
A8 2B8
2B
(Ap(As(x.)
A
SES
This proves the lemma.
We now prove Lemma F3
Proof of Lemma
F.3
Consider the objective OBJ (6) sup, min U(T, p). By
Lemma F4 for any (T.P) there exists an agent strategy p' + A(As (z.)) that only random- izes over A -opptiall actions such that p') (TT p) < A
288 Because minimizing over ((Aaxx.) is equivalent to minimizing over As(xs) which corresponds to deterministic A-best- responding strategies, we get:
(B.I((8) = sup min U(r,p) 2 sup min pERa(T)
((A UTT,P')) - 2B6
A
min U(TT, p¹) - 2B8
sup
OBJ (A) A
2B5
32


Reviews:
[{"review_id": "zDCpipfo7C", "reviewer": "Reviewer_f1Rw", "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.", "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)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper introduces a novel problem along with a generic solution framework. I like its results derived from a clean reductions approach.\n- The paper provides the reader's sufficient knowledge about the general principal-agent problem from Gan et al. (2024).\n- The paper provides many well-sketched intuitions to help us understand its proofs.", "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. \n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EGOCsFCTKp", "reviewer": "Reviewer_H3BR", "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.", "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?\n\n- How can the fixed policy $\\pi_t$ in the statement of Theorem 3.1 be computed?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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\n- The results on the achievable utility when the agent plays a $\\delta$-suboptimal best response according to a randomized strategy are interesting and novel", "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.\n  \n- Similarly, in Stackelberg games with a small inducibility gap, the proposed analysis does not hold.\n\n- 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?\n\n- 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.\n\n- Typo: Line 981 “Sectin”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1lwURI4mUg", "reviewer": "Reviewer_QEC8", "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.", "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.\n\n- 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 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.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QVn52qaqO5", "reviewer": "Reviewer_687t", "summary": "This paper proposes a general method to reduce the repeated principal-agent games to one-shot approximate best-response on principal-agent games.\n\nThe setup is very close from the Bayesian Persuasion  one [Kamenica and Gentzkow, 2011].\nThe principal does not have commitment power but as in the Bayesian Persuasion setup, they can disclose information so to influence the agent’s behavior.\nThen, 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:\n$$V(\\pi, d) - V(\\pi, \\rho) \\leq CReg(T)/T,$$\nwhich 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.\n\nI 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.", "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):\n\n\t- 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.\n\n\t- Principal-Agent Reward Shaping in MDPs, that studies principal-agent interactions on a MDP and formulates it as an  optimization problem.\n\n\t- 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..\n\nOne 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?\n\nFinally, 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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "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.\n\nOne 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.\n\nThe paper is well written and clear, which makes it pleasant to read.", "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.\n\nI 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.\n\nRegret 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?\n\n**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.\n\nBelow, I copied the model of the paper « Online Bayesian Persuasion », that is part of the references:\n\n« 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\n\nI 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.\n\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)