Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Authors: Junyan Liu
Arnab Maiti
Artin Tajdini
Kevin Jamieson
Lillian J. Ratliff
Venue: ICML 2025 poster (2025)
Keywords: Principal-agent problem
Incentive design
Regret Minimization
Adversarial
Greedy response
Lipschitz response
Primary area: theory->online_learning_and_bandits

Abstract: We initiate the study of a repeated principal-agent problem over a finite horizon $T$, where a principal sequentially interacts with $K\geq 2$ types of agents arriving in an *adversarial* order. At each round, the principal strategically chooses one of the $N$ arms to incentivize for an arriving agent of *unknown type*.  The agent then chooses an arm based on its own utility and the provided incentive, and the principal receives a corresponding reward. The objective is to minimize regret against the best incentive in hindsight. Without prior knowledge of agent behavior, we show that the problem becomes intractable, leading to linear regret. We analyze two key settings where sublinear regret is achievable. In the first setting, the principal knows the arm each agent type would select greedily for any given incentive. Under this setting, we propose an algorithm that achieves a regret bound of $\mathcal{O}(\min(\sqrt{KT\log N},K\sqrt{T}))$ and provide a matching lower bound up to a $\log K$ factor. In the second setting, an agent's response varies smoothly with the incentive and is governed by a Lipschitz constant $L$. Under this setting, we show that there is an algorithm with a regret bound of $\tilde{\mathcal{O}}((LN)^{1/3}T^{2/3})$ and establish a matching lower bound up to logarithmic factors. Finally, we extend our algorithmic results for both settings by allowing the principal to incentivize multiple arms simultaneously in each round.

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Junyan Liu"!
Arnab Maiti Artin Tajdini"
!
Kevin Jamieson
Lillian J. Ratliff
Abstract
1. Introduction
The repeated principal-agent model captures sequential decision-making scenarios where principal strategically incentivizes agents over multiple rounds to act toward long-term objective. This framework is central to many real-world applications, such as online platforms offering discounts to influence purchasing behavior, insurance com- panies designing contracts without full knowledge of cus- tomers' risk levels, and crowdsourcing platforms structuring payments to ensure high-quality contributions. In these set- tings, the principal cannot directly control agents' actions but influence them by proposing incentives, often under asymmetric information. Typically, asymmetric informa- tion introduces two key challenges, including moral hazard (Bolton & Dewatripont, 2004; Ho et al., 2014; Kaynar Siddiq, 2023) and adverse selection (Scheid et al., 2024b; Dogan al., 2023b;a). In moral hazard settings, the agents' actions cannot be directly observed by the principal, requir- ing incentive design to encourage agents to take actions in favor of the principal's interest. A common example is crowdsourcing where a task requester (principal) cannot di- rectly observe the effort level of workers (agents). Adverse selection, on the other hand, arises when the agents' types or preferences are unknown. For example, in insurance, the insurer (principal) may not know whether customer (agent) is high-risk, complicating the contract design.
We initiate the study of a repeated principal-agent problem over finite horizon T, where a prin- cipal sequentially interacts with K 2 2 types of agents arriving in an adversarial order. At each round, the principal strategically chooses one of the arms to incentivize for an arriving agent of unknown type. The agent then chooses an arm based on its own utility and the provided incentive, and the principal receives correspond- ing reward. The objective is to minimize regret against the best incentive in hindsight. Without prior knowledge of agent behavior, we show that the problem becomes intractable, leading to linear regret. We analyze two key settings where sub- linear regret achievable. In the first setting, the principal knows the arm each agent type would select greedily for any given incentive. Under this setting, we propose algorithm that achieves regret bound of O(min VKT log N, K )T)) and provide a matching lower bound up to log K factor. In the second setting, an agent's 's response varies smoothly with the incentive and is gov- erned by a Lipschitz constant L 2 1. Under this setting, we show that there is an algorithm with a regret bound of ((LN)//33233 and establish a matching lower bound up to logarithmic factors. Finally, we extend our algorithmic results for both settings by allowing the principal to incentivize multiple arms simultaneously in each round.
While repeated principal-agent problems have been exten- sively studied, prior works heavily focus on the scenarios where the principal repeatedly contracts with fixed and unknown type (Scheid et al., 2024b; Dogan al., 2023a;b) a random type of agent drawn stochastically from a fixed underlying distribution (Ho et al., 2014; Gayle & Miller, 2015). However, these two assumptions may not hold in many real-works applications. For example, in online shop- ping, discount ads displayed on a website are visible to all users, and the sequence of users who respond may not fol- low a stochastic pattern. Another example crowdsourcing, where the sequence of crowdworkers who respond to a task could be arbitrary and subject herding behavior through online forums (Horton et al., 2011) I). To capture the uncer- tainty of agent arrivals, we initiate the study of the repeated principal-agent problem with adversarial agent arrivals. To
"Equal contribution 'Paul G. Allen School of Com- puter Science & Engineering, University of Washington, Seattle, USA 'Department of Electrical and Computer En- gineering, University of Washington. Seattle, USA. Corre- spondence Junyan Liu <junyanll @cs. www.swwsiingooo.e.e.. Arnb Maiti <arnabm2@cs washington.cdu>. Artin Tajdini <artin @es. washington..ddu.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
our knowledge, this is the first study that examines this challenge in repeated principal-agent framework.
The interaction unfolds over finite horizon 1 1, ,,..., T, where agents arrive in an adversarial order. In each round t, an agent of type jt E [K] arrives (where jr is un- observed by principal), and the principal simultaneously chooses an incentive vector x, = (ft,,,,..., TT,N) E DD where D S [o, 1] denotes the principal's decision space, The agent then selects an arm Jt), taking Ti and jr into account. The principal observes only the chosen arm a(Me, and receives the following utility: U U(TT, Je) Ca(me.)t)) (T..((T..e))
Apart from agent arrival patterns, the agent response also plays a critical role in incentive design. Consider online shopping platforms where customers only make a purchase when a discount reaches a historical low or falls below their personal threshold. Similarly, crowdworkers in online labor markets often accept tasks only if the payout exceeds minimum expectation. Such behaviors suggest a decision- making process governed by strict thresholds. To model this, we start by considering the greedy response model widely studied in the literature (Ho et al., 2014; Zhu et al., 2022; Dogan et al., 2023b; Scheid et al., 2024b; Ben-Porat et al., 2024), where an agent chooses an action that maximizes their utility, i.e., preference plus incentive. In this model, the agent plays an arm only when the incentive on this arm crosses predefined level.
The objective of principal is to minimize the regret:
T
RT sup E RED
Σ (U U( U(to.i))
Incentive structures. We consider two types of incentives: single-arm incentives and general incentives.
Ideally, we seek an approach that adapts to adversarial agent arrivals without prior knowledge of agent types, that is, how incentives influence the threshold values driving their deci- sions. Unfortunately, we will show that this is intractable, in the sense that no algorithm can compete with the single-best incentive in hindsight without that prior knowledge. Indeed, our lower bound exploits the fact that even a tiny change in incentives can lead to a drastic shift in agent decisions, and consequently, the principal's reward. This non-smooth sensitivity to incentives defics intuition and suggests the need for an alternative model where agent decisions respond more gradually to incentives. For instance. when purchas- ing daily necessities, a small change in discounts should not drastically alter a customer's decision but instead grad- ually influence their likelihood of buying. This distinction motivates the need for a more flexible response model.
Single-am aag incentive: the principal can incentivize at most one arm, meaning the incentive vector has at most one nonzero coordinate. The decision space is
D {ar E 1] [supp(>)]] S 13
General incentive: the principal can incentivize multiple arms, meaning the principal can choose any incentive vector in [0, 1ja.. The The decision space is D [0, 1|
Arm Selection Models We analyze two models for agent decision-making namely, the greedy choice model and the smooth choice model.
Greedy choice model: an agent of type je observes the incentive vector n, and best responds by deterministically choosing the arm
Moreover, the smooth decision model can be viewed as an extension of the greedy model by allowing agents to incor- porate smooth noise into their preferences. For example, if an agent adds i.i.d. Gumbel noise 17' Gumble(O, 1) to their preference vector p²t,, the resulting choice model becomes the Logit discrete choice model which is prevalent in economics literature (Train, 2009); and if an agent adds i..d. Gaussian noise '/ ~ (O, I) to their preference vec- tor n²²,, the resulting choice model becomes Lipschitz (see Appendix E.2).
b(Te..i) E arg max iE[N] p + me.).
Ties are broken arbitrarily but consistently across agent types. We assume that the principal knows the best response function b(,,.), meaning the principal can determine b(T, for any π E DD and j E [K].
Smooth choice model: the agent of type je selects an arm a( Jt) probabilistically based on an unknown distribution that varies smoothly with the incentive vector follows.
1.1. Problem Statement
Assumption 1.1. (Smooth decision model) For any two incentive vectors म, N' E D and any agent type j. the proba- bility distribution of arm selection satisfies:
We study the repeated principal-agent problem, where a principal incentivizes К types of agents to choose arms from the set [N] (1, (1...., N). The principal has a known (vi,.. .N) E [0, 1J Each agent type j E [K] has an associated preference vector μd = (xx E [0. 1
reward vector
N
Σ
Pr(a(T, = - S I.- 1.-1|x T'1bo;
1=1
where 221 is a Lipschitz constant.
2

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Table I: Regret bounds under different agent behaviors and incentive models.
Agent behavior
Incentive type
Upper bound
Lower bound
Unknown, Greedy choice
Single-arm
N/A
(2(T))
Single-arm
Ô (min V KT log (NI,
Q(min KT log( (N), K KVT))
Known, Greedy choice
General
O(K (TKo/loTTTT (KT)
Single-Arm
O (1V3N11372/3
2 (L
Unknown, Smooth
General
o (L (LWNN=3/(WN+)//0222
1.2. Contributions
(approximately) incentive. In the repeated setting (Misra et al., 2005; Misra & Nair, 2011; Ho et al., 2014; Kaynar & Siddiq, 2023; Scheid et al., 2024b; Dogan et al., 2023a; Ben-Porat al., 2024; Wu et al., 2024; Liu & Ratliff, 2024), the principal interacts with agents for multiple rounds, and the goal could be estimating agents' model or maximizing the cumulative profits, which in turn minimize the regret. Our work falls within this line of research. While principal- multi-agen problems have been considered in the one-shot setup (Dütting et al., 2023; Duetting et al., 2025), little known about the multi-agent study in the repeated setting. The known related works (Ho al., 2014; Gayle & Miller, 2015) consider the repeated principal prineipal-multt-ageen problems, but they assume that the arrival of agents follow a fixed underlying distribution, which is often not the case in many real-world scenarios.
All our results are summarized in Table 1. For the greedy response agent and single-arm incentive case, we show that any algorithm without prior knowledge of the agents' behaviors can be forced to ineur linear regret. However, when the agent behaviors are known as priori, that is we know the best response function of each agent but not which agent arrives at each round, we discretize the con- tinuous incentive space and propose a idlluction-based ap- proach that turns the problem into an adversarial linear bandits problem with finite arms. The proposed algorithm achieves a (minn / KT log(KN), K (V))) upper bound. Under this same setting of known types, we provide á (min { (KVT, / /KTllg(()) (og(N)) regret lower bound, im- plying that our upper bound is tight up to logarithmic factors.
For the case of greedy agent and known agents' behaviors, if the principal is allowed to incentive more than one arm simultancously (also known general incentives), we adopt the previous reduction to adversarial linear bandits, but more importantly, introduce a novel discretization, which enables our algorithm to achieve idea behind the discretization is identifying a polytope for the large incentive space such that the extreme point of the polytope is close to the optimal incentive.
The repeated principal-agen aggnt problem has been studied un- der different forms of information asymmetry. The moral hazard setting (Misra al., 2005; Ho et al., 2014; Kaynar & Siddiq, 2023) assumes that the agents' actions are invisible to the principal, while the adverse selection (Ho et al., 2014; Gayle & Miller, 2015) considers cases where agents' pref- erences are unknown to the principal. Additionally, Scheid et al. (2024b;a); Dogan et al. (2023a); Liu & Ratliff (2024) explore settings where the agent's type unknown, but they assume a single agent type in the interaction, avoiding the challenge of multiple agent types responding differently to the same incentive- a key issue in our work. Fiez et al. (2018) study agents with multiple different types that evolve dynamically (as a function of the offered incentives) accord- ing to a controlled Markov chain, and focus their attention on epoch- algorithms that exploit mixing time prop- erties of the controlled Markov chain along with a greedy matching strategy in each epoch.
(T) regree bound. The key
Finally, for the smooth response agent and single-arm in- centive case, we propose an algorithm which achieves a Ö(1//8x1/872/5) regret bound where L 2 1 is a known Lipschitz constant. We further show the tightness of this lower
upper bound as matches our 12L2/3 bound up to logarithmic factors. We also show that for the general incentive case, (U1 regret is achievable.
1.3. Related Work
While our framework shares the principal-agent structure of Harris et al. (2024) and Balcan et al. (2025), it diverges from their contextual Stackelberg models in two key respects. First, their setting, the principal chooses mixed strategy from a probability simplex over a finite action set, whereas in our setting, the principal chooses an incentive vector from the hypercube E [O, 1| In addition, their payoffs of the principal and agent derive from a contextual utility function
The principal-agent model has been extensively studied in both one-shot and repeated settings. In the onc-shot setting (Holmström, 1979; Grossman & Hart, 1992; Carroll, 2015; Dütting et al., 2019; 2022), the principal only interacts with agents once, and the typical objective is to identify the best
We use ()()))()) to suppress poly- poly-logari terms in K, K.
3

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
evaluated under the chosen mixed strategy and observed context. In contrast, in our model each agent of unknown type j selects arm i E [NV to maximize u² Ti and the principal's 's payoff is T. These key differences in action space and reward structure highlight the distinction between our principal-agent model and theirs.
is not always feasible. Consequently, any algorithm incurs Q((T) regret for some A (0.7,0.71], For the formal proof, we refer the reader to Appendix B.
2.2. Lower Bounds for Single-arm Incentive
Consider the greedy choice model, where the principal is restricted to single-arm incentives and has knowledge of the best response function b(:,-). The following theorem
Moreover, similar to the works of Bernasconi et al. (2023) and Balcan al. (2025), our algorithm proceeds by clev- erly reducing the problem an online linear optimization problem.
establishes a tight lower bound on regret, up to logarithmic factors.
Theorem 2.3. Suppose the principal and the agents operate under a greedy choice model with single-arm incentives, and the principal has access to the best response function b(:-)- For any K 3, N 2 3. T 2 poly(K), and any algorithm, there exists an instance of the principal-agent problem such that
2. Lower Bounds for Greedy Choice Model
In this section, we establish the fundamental limits of the principal-agent problem under the single-arm incentive. We first show in Section 2.1 that any algorithm lacking advance knowledge of the agents' behavior can be forced to incur linear regret. Then, in Section 2.2, when the agents' behav- iors are known, we derive a tight lower bound on regret for the greedy choice model, up to logarithmic factors.
Ry = 2 (min (VKTlog(N))))
K K log(K)))
The proof of this theorem is non-trivial, and due to space constraints, we defer it to Appendix C. Here, we outline the key ideas behind our proof.
2.1. Linear Regret for Unknown Agent Behavior
Consider the greedy choice model, but now assume that the principal does not have access to the best response function .(: Under this assumption, we establish linear regret bound for any algorithm, as stated below.
First, consider the case where N S K. We carefully con- struct the reward vector u and the preference vectors μº such that there exists set II (- =(2) ,.... n/ (K -1] of incentive vectors with the property that for any D, there exists some (f) E II satisfying ((r()),) 2 ((T.)) for all j E [K]. Consequently, we can assume that any algorithm selects an incentive exclusively from II in each round.
Theorem 2.1. Suppose the principal and the agents operate under a greedy choice model with single-arm incentives, and the principal does not have access to the best response function .(..)). For any algorithm, there exists an instance of the principal-agen problem with K- agent types and
N arms such that Rr ((T).
Next, we define a probability distribution p(a.e) over the agents, ensuring that in each round, an agent je is drawn from this fixed distribution. We construct p(1.=) such that the expected utility of choosing the incentive vector (!)) is r + 6, while for all other incentive vectors, it remains r, where r E 1/2] is some constant.
To provide intuition for Theorem 2.1, consider the following example:
Example 2.2. The principal's ss reward vector is v (1,0.5, 0). The preference veclors of two agents are n²² = (0.2, 0, 0.2 + A) and y²² = (0.2, 0.2 + O,, where A E [0.7, 0.7]. When a tie occurs, agent 1 favors arm 1, while agent 2 favors arm 2. At each round, agent is selected with probability 0.4, and agent 2 is selected with probability 0.6.
Now, suppose the algorithm selects an incentive vector n( + n(1) only a limited number of times. We construct alternate problem instance by instead using a probability distribution p(i.e), where the agent je is sampled from p(f.e) in each round. This new distribution is chosen so that the expected utility of z(1) remains r + e, while that of (4) increases to r + 2s, and all other incentive vectors continue to yield r.
In Example 2.2, the incentive vector x² = (A,0,0) is uniquely optimal because any deviation from this incen- tive for arm incurs at least a constant regret. Specifically, the expected reward of nT" is 0.6 0.5 + 0.4(1 A)= 2 0.416. In contrast, offering an incentive less than A for arm 1 re- 0.3,
By appropriately choosing e and employing careful KL- divergence-
arguments, we establish that in at least one of these two problem instances, the algorithm incurs regret of ((VKT). While these arguments resemble the standard lower bound analysis for the Multi-Armed Bandit (MAB) problem, a key challenge in our setting is that we must fix the reward vector and preference vectors in
sults in expected reward of at most 0.6-0.5+000 and offering an incentive greater than A yields an expected reward of at most 1 - A < 0.3.
However, the probabilistic selection of agents implics that we must exactly learn A to achieve sub-linear regret, which
4

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
advance, constructing multiple instances solely by varying the probability distributions over the agents.
maximum. Our approach can be suitably modified avoid relying this assumption. For further details, we refer the reader to Appendix D.
For the case when N 2 K, we aim to establish a combina- torial bandit-style lower bound, analogous to the MAB-style lower bound derived for N s K. At a high level, we begin by defining a bijective mapping f that maps the first N - arms a subset of {0, 1)x-2 These N 1 arms each yield reward of roughly 0.5, while the last arm is a special arm with reward of O.
Discretization. To construct a finite single-arm incen- tive set, we begin with an empty set IT. Observe that max]e[N] u4 - nu represents the minimum incentive re- quired to entice agent j to choose arm For each arm E [NV and agent j E [K], we define an incentive vector tho E D such that for all s [N]:
We then construct preference vectors for each agent such
(T' = MaXKe[[] m4 - -12 if ifs=i,
that there exists a set 11 = {xx())x())).. ..... x (N-1)) of in- centive vectors satisfying the following property: for any
0,
otherwise.
t E 'D, there exists some (+) E II such that (1 j) 2 ji for all j E [K]. Also for all i E [N- 1]. (T)); Consequently, we can assume that any algorithm selects an incentive exclusively from II in each round.
For all i E [N] and j E [K]. we add the incentive vector T to II, resulting in [II = O K). The set II has the key property that for any π E D. there exists a vector n' E II such that U( ,3) 2 U( j) for all J E [K].
Next, we define a class of distributions for sampling agents such that the utility function exhibits a linear structure over the vectors in II. Specifically, we ensure that
When N (22*) is exponentially large, we can further refine the discretized set to make it independent of N. In- tuitively, when N is large, some incentive vectors elicit the same response in terms of the selection of their incentivized arms. In such cases, we retain only the most rewarding incentive vector rather than including all equivalent ones in the reduced set.
F (17() .))) ((1))
where ((p) E [0, 1|--2 is a reward vector dependent solely on the preference vectors of the agents and the distribution p from which the agents are sampled in each round. The last arm and two special agents who prefer this arm play a crucial role in ensuring the above equality.
To formalize this, we define mapping h II + {0, 10, such that for any II \ {0} and j E [K], where 0 is the zero-incentive vector (0, 0, ..... 0), we have:
Given this setup, we replicate combinatorial bandit-style lower bound by carefully defining the sample space and computing the corresponding KI.-divergences Ultimately, we establish a lower bound of
(M(=)); = 1, if b( = ()) a(T),
0, otherwise,
Ω min {
{v KT KTT log(())/ (K), K KK/T/lloge lo)
where a(x) == arg max म; denotes the index of the largest coordinate of ा. Observe that if b(TT + a(T) then b(T,)) = b(O,j))
3. Main Results for Greedy Choice Model
Using this mapping, we construct reduced set îî as fol- lows. We initialize îī as an empty set. For each vector s E {0, 1 define
In this section, we present our algorithms for the greedy choice model, assuming access to the agents' best response functions. The key idea behind our algorithm design is to discretize the decision space and reduce the problem to adversarial linear bandits. We first describe our algorithm for the single-arm incentive in Section 3.1, followed by the algorithm for the general incentive in Section 3.2.
11, = (T (0) h(T)) =s.
If |U, = 1, we add the unique E 11, to I1. If I1. > 1, we have ((T.)) j) = sj (Va(z) Ta(=)) + (1 (1-s,) Ub(o.)) for all π E 1I. Thus, we add only one of the maximizers, A = arg max Pa(s) [a(a), to ΠI. We also include the zero-incentive vector 0 in πT. Since [[0, and we select at most one vector per II,, we obtain N s min [2 2* + 1.
3.1. Algorithm for Single-arm Incentive
2k
The proposed algorithm consists of two stages: first discretizing the decision space D (i E [0, 11xd supp(==) < 1} into finite set, and second, reducing the problem to adversarial linear bandits using the discretized set and the best response functions of each agent.
Since î is obtained by removing only suboptimal incentive vectors from II, it retains the key property that for any क e D, there exists ف e Il satisfying (TT'),)) )) Z U(T,)) for all J E [K]. Given this fact, it suffices to focus only on fl for regret minimization.
Tie Breaking. For simplicity of presentation, we assume that in the case of a tic, an agent always prefers the in- centivized arm, and each preference vector has a unique
5

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
A natural approach is to treat each incentive E II as arm, thereby reducing the problem
and second, reducing the problem adversarial linear ban- dits using the discretized set and the best response functions of each agent.
adversarial multi- armed bandit setting. However, this reduction results in regret bound of O / /min| KN, 2* (T) if one, for example, applies the Tsallis- algorithm (Zimmert & Seldin, 2021).
Tie Breaking. To simplify the presentation, let us assume that agents resolve ties in hierarchical manner. Specifically, each agent j has a bijective mapping ʃn : [NV] + [M] and in the event of tie among set of arms I S [M,, agent j selects the arm arg max,ez fi). Other tie- breakki rules can be handled in a similar fashion.
Given the lower bound established in Section 2.2, this raises the question: can we adopt different approach improve the upper bound?
Reduction to Adversarial Linear Bandits. We now im- prove the upper bound by proposing a simple yet effective reduction to the adversarial linear bandits problem. This approach ensures that our upper bound matches the lower bound up to logarithmic factors in K.
Discretization. For the general incentive case, the princi- pal's s decision space is given by D = [0, 1|N The algorithm for this case builds upon the reduction framework employed by the single-arm incentive algorithm but introduces a dif- ferent discretization approach.
We begin by constructing an arm set C RRK For each incentive π E II, we define the corresponding vector 2n E RR
Let [N]] be K Kidimennionnl tuple. Define Pa (л E [0, j) = a, vj E [K]], and let Pa denote the closure of p. If is non-empty, then it forms convex polytope defined by the following set of linear inequalities:
(="); = UT, E
We then add nd to Z. Next, we define the reward vector yt E RK If agent ji arrives in round t, we set
0 ग S
ViE [N].
1, je.
(we)
Md + To, 2 2 + Vie [N] 10,), jE [K].
0, otherwise.
If Po is non-empty, it is an open convex polytope, as some of the inequalities above become strict.
With these definitions, for any π ñi, we observe that U (TT (=T,, w1) Thus, pseudo-regret Rr is equal to the adversarial linear bandit rseudo-regret:
Now, let Σ := for E [N] Po + 0). We define two incentive vectors π and â to be e-close if || a/ E. For E Σ, we construct set of incentive vectors I,, as follows: for each extreme point of P.. we select an g- close vector in Pa and include it in 1Ig. We now claim that [I S K))
T
T
RT = max E 2E2
(2, vt)
-
Σ
(22, ve)
For an adversarial linear bandit problem over decision set X' C IRd with horizon T and rewards bounded in [-1, let RAt RAi (T, X)) denote the pseudo-regret of an algorithm Alg.
First note that any extreme point of Pa is an intersection of N N-linearly independent half- salf-spaces defining this polytope. Now observe that the number of half spaces used to define this polytope
If Alg is the EXP3 algorithm for linear bandits (Lattimore & Szepesvári, 2020), it satisfies
most Poly K). Hence, the number of extreme points is upper bounded by (poly(N, K))* Since each point in II, is associated with exactly one extreme point of P we have , < (poly(N, K))
Ra (A S Oly dl lo)((())))
Since our reduction is an instance of the adversarial linear bandit problem, obtain the following result:
Let II = U II, We claim that for any sequence of agents dE
J1, .efi,......J......... fr, the following inequality holds:
Theorem 3.1. Suppose the principal and the agents operate under a greedy choice model with single-arm incentives, and the principal has access to the best response function b(,,)). Then, there exists an algorithm for this principal- agent problem whose pseudo- regret is upper bounded by
max TENl
U(T,j)))
sup [
Σ U((T jt) 25T.
Consider an incentive vector "t E [0, 11. such that
RI S Ô (min (KTlog(N)) KVT))
T -(m.)))-eTT xE(o.I]
Σ UU
sup
3.2. Algorithm for General Incentive
The proposed algorithm consists of two stages: first, dis- cretizing the decision space D = [0, 1j into finite set,
Let T* E Pa. where o corresponds to the behavior induced by by Since the maximum of linear function over a closed
6

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
polytope is attained at one of its extreme points, there exists an extreme point सt of Pa such that
(2020)). Using the EXP3 algorithm for linear bandits on the reduced arm set Zo. we achieve regret upper bound of O K (VVTloow (TTlg((KT) This leads to the following theorem:
Nas. Toz
No
Uu U st))
Theorem 3.2. Suppose the principal and agents operate under a greedy choice model with general incentives, and the principal has access to the best response function b(c, -)- Then, there exists an algorithm for this principal- agent prob- lem whose pseudo-regret is upper bounded by
Let ग be the vector in IT, that is e-close to म. Now, we have the following:
T
RT SO (OOKVVioon (KVTlog(KT)
Σ U
=
t=1
4. Main Results for Smooth Choice Model
(Ud3e Moos)
[Tos ko,s))
In this section, we present an algorithm for the setting where agent types and their preference model are unknown but assumed to be a smooth function of the incentive vector.
Σ [1032
Tos)) ) Σ |ayy Rozi!
T
4.1. Algorithm for Single- Incentives
Σ (Uos
Toss) )
- xT
The proposed algorithm comprises two stages. First, it dis- cretizes the decision space D = {a E [0, 1| |supp(z)] S }} into a finite set. Second, it runs the adversarial multi- armed bandit algorithm, Tsallis-INF, the discretized set.
(as 1| - $ 11 S E)
T
> sup =E
Σ
((T - 2sT
Discretization. Fix > 0. To construct finite single-arm incentive set, we begin with an empty set II. For all i E [N] and j E [1/E + 1], we define an incentive vector T E D such that for all E [N]:
If we set 7. then it suffices to focus the set of incentive vectors 11 for our regret minimization problem.
Reduction to Adversarial Linear Bandits. We now show a reduction of this problem to an adversarial linear bandit problem. First, we construct a set Z C R as follows: for each ι II, we add RT to 2, where (z"), = (mx,j) J) for
[ ( ( 1) 0,
if i, otherwise.
(T
all j [K]. Next, we define the reward vector y/ E KRK If agent je arrives in round t, we set (y:); 1 if j and (vr); = 0 otherwise. Observe that for any π E II, U(T, jc) (e", gt). Hence, our pseudo-regret Rr is equal
Algorithm and its Regret guarantee. We run Tsa by treating each vector in II as an arm. Let x² E D be the optimal fixed incentive in hindsight against a sequence of agents J2, ... Consider a vector E II such that [ n. S E for some index i E [N]. For any agent j. we have the following:
je
to the adversarial linear bandit :
T Σ
T
RT = max E 2E2
(2. v+)
-
Σ
(Zt, ve)
BIU(x* .,]] - B((U(R))
Σ (Prla(T*, ,5) i) Pr(u(f, = =i]) ve
Using the EXP3 algorithm for linear bandits, we obtain regret upper bound of poly(K, (l) /T for our regret minimization problem. However, this upper bound can be further improved as follows. Let R = {C)]sE(K) k] be the set of all possible reward vectors. Define Zn as the smallest subset of Z such that
+ Pr(a(R, = -) Pr(a(x" (.) = =1]-5t x
Σ (Prla(T",,) ,5)= = 1 - Pr = =6])
1=1
+ (Pr(a(R,5) =] - -rraa .J) = iI) क +
max min max (z 2', w) s 2 Eo VER
1 S T
< 2 8 L+ (Assumption 1.1 and 0 S 0/ न.. < 1)
The regret of our approach is upper bounded as:
By the above inequality, it suffices to focus on Z, for our regret minimization problem. It can be shown that /ol S (6KT)K K (see Chapter 27 of Lattimore & Szepevvári
T
R <
E(U(T,)) U(T.10)
7

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
4.3. Instance-dependent Algorithm for Single-Arm Incentives
( ..) - (.)
Depending on the problem instance, uniformly covering the entire action space- while optimal in the worst case-can be inefficient. The goal is to cover near-optimal regions more densely than others. To achieve this, we leverage zooming algorithms, which are widely used in the Lipschitz bandits literature. These algorithms begin with a uniform discretization and adaptively refine the discretization in re- gions that are more likely to be optimal. Specifically, if the uncertainty about an optimal point being in given re- gion falls below a certain threshold (the zooming rule), that region is discretized more densely.
I 0 Ne 'T +T (2L 1).
Setting & = N2/ + 1) 2//37-1/3, would make the regret bounded by ( + 11/33///3///
Remark: It can be easily shown that without knowing L, any fixed discretization's is regret will scales linearly in L.
4.2. Lower Bound for Single-Arm Incentives
In the following theorem, we show the our regret upper bound is optimal.
Theorem 4.1. For all N,T. and L 2 3, if Assumptiin 1.1 holds for all agents, then we have
We use ADVERSARIAL Slivkins, 2021) with the action set DD and the metric d(m, T') = L|| o'lloo- Assumption 1.1 holds, then the reward function U(, is (2L + 1)-Lipschitz, ensur- ing that these inputs are valid for the algorithm. To adapt to the adversarial setting, the algorithm employs EXP3.P to sample points from active regions and zooms into a re- gion when its confidence interval becomes smaller than a threshold, determined by its diameter, L, and I. The key instant-dependent parameter the adversarial zooming di- mension, for parameter 7 > 0 is defined as:
from (Podimata &
inf sup B[ ( (EV/S AEAl jEJ
where J is the set of agent types, and R is the regret when only agents of type j are selected.
Here we provide high level ideas behind the proof. We refer the reader to Appendix E for the detailed proof. To prove the above theorem, we construct an instance where only a small interval of size e for specific arm yields reward A higher than any other incentive-arm pair. This results a regret of min (A,, min, A A-2 -2), which, with appropriately chosen parameters, establishes the desired bound.
inf (Cover(Ae, B(1l-l S S Ye}, #20
where Ag is the set of all incentives that achieve Ō(E)- optimal reward for the principal in hindsight, and ((Il). =) are (noncentered) norm balls of diameter e. Then, using (Podimata & Slivkins, 202 3.1] for our setting, we would have the following regret bound.
However, proving this bound presents two additional tech- nical challenges, as Assumption 1.1 must hold. Specifi- cally, the reward within the optimal interval should increase smoothly by A and then return to the base reward. Addi- tionally, A must be bounded by O(L '). We define the set of adversarial types as J == {(1,]) i E [N].j j [].
Corollary 4.2. Suppose the principal and agents operate under a smooth choice model (Assumption 1.1), where the choice model has the Adversarial zooming dimension of z. Then, there exists an algorithm for this principal-agent problem whose pseudo-regre is upper bounded by
Then, for all / N 1, have:
B B(x; je)
16N(1-2)) R.
if = i, E [je, (j + 1)d
Pr[a(T, (f.j)) = -1--
16N(1-R:)
if S
Rr S O(T (22)))))))))))))))))))))))) log T.
if m >
gN
For single-incentive setting, the zooming dimension is bounded by 1, since the entire action space can be covered with I(N hypercubes, as shown in the fixed discretiza- tion algorithm. However, for some smooth choice models, the regret bound is improved. For instance, if the reward function induced by an agent's choice model is strictly con- cave, then 2 = }.2 leading to an expected regret of T (see (Podimata & Slivkins, 2021), Section 6).
N-1
Pr[a(T, (1,1)) = NJ 11 Σ
PrIa(T, (,, (i,j)) = (2)
Where bonus term B : 10 c] - R is 4 Lipschitz func- tion with (0) = B(e) = 0. This leads to the optimal in-
je + arg max ((x) centive n", where πj 0
df(=i
if i i'
and only giving incentive in a small region containing nT will give information for optimal solution, and its not possi- ble to distinguish the best region for all agent types without having 2(T2/3) regret.
4.4. Algorithm with General Incentives
For the general incentive case, recall that D = [o, 1] We partition D into eNN equally sized hypercubes and define
8

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
II as the set of center points of these hypercubes. Similar to the single-arm incentive case, we run Tsa by treating each point in II as arm. Setting (2L (22 1/(N+2), we incur the following regret:
award #1844729.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.
RT 2
B(U j.) - (++,))))
+ Σ [lU(=*, ji) UF
References
$ O(VE NT +T- -2T((2+1))
Balcan, M.-F., Bernasconi, M., Castiglioni, M., Celli, A., Harris, K., and Wu, S. Nearly-optimal bandit learn- ing in stackelberg games with side information. arXiv preprint arXiv:2502.0022 2025.
0 (2 M
Similar to the single-incentive setting, using ADVER- SARIALZOOMING will result in regret of ((2L + 1)2/(=+2)/((++)((4+22)) where the zooming dimension 2 upper bounded by N, - hypercubes cover all of decision space.
Ben-Porat, O., Mansour, Y., Moshkovitz, M., and Taitler, Principal-agent reward shaping mdps. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9502-9510, 2024.
Bernasconi, M., Castiglioni, M., Celli, A., Marchesi, A., Trovò, F., and Gatti, N. Optimal rates and efficient algorithms for online bayesian persuasion. In Interna- tional Conference Machine Learning, pp. 2164-2183. PMLR, 2023.
5. Conclusion
In this paper, we initiate the study of the repeated principal- agent problem with adversarial agent arrivals. For the greedy response agent and single-arm incentive case, we establish negative result, proving that any algorithm without prior knowledge of agents' behaviors can be forced to incur linear regret. However, when the agents' behaviors are known, we design an algorithm based on novel reduction to adver- sarial linear bandits, achieving a regret bound that nearly matches the lower bound up to a logarithmic factor. More- over, when the principal is allowed offer general incen- tives, we propose an algorithm that integrates our reduction technique with novel discretization approach, leading to sublinear regret bound. Finally, for the smooth-rest response agent setting, we develop an algorithm whose regret bound aligns with our lower bound up to logarithmic factors.
Bolton, P. and Dewatripont, M. Contract theory. MIT press, 2004.
Carroll, G. Robustness and linear contracts. American Economic Review, 105(2):536-563, 2015.
Chen, K., Huh, S., and Kandasamy, K. Learning to price homogeneous data. arXiv preprint arXiv:2407.0544 05444444 2024.
Dogan, I., Shen, Z.-J. M., and Aswani, A. Estimating and incentivizing imperfect-knowledde agents with hidden rewards. arXiv preprint S...x:230..0671.... 2023a.
Our work opens several interesting directions for future research. A natural extension, inspired by (Scheid et al., 2024b), is to consider setting where the principal observes only noisy rewards, adding an extra layer of uncertainty and requiring reward distribution learning. Another direction is to incorporate purchase quantity into the model, as in (Chen et al., 2024). While our current framework assumes agents purchase a single item per round, real-world scenarios often involve varying purchase quantities.
Dogan, I. Shen, Z.J. M., and Aswani, A.
Re- peated principal-agent games with unobserved agent re- wards and -rofleg-k agents. arXiv preprint wrXiv:2304.07407, 2023b.
Duetting, P., Ezra, T., Feldman, M., and Kesselheim, T. Multi-agent combinatorial contracts. In Proceedings of the 2025 Annual ACM-SIA -SAM Symposium on Discrete Algorithms (SODA), pp. 1857-1891, SIAM, 2025.
ACKNOWLEDGEMENT
This work was supported in part by NSF TRIPODS CCF Award #2023166, Microsoft Grant for Customer Experi- ence Innovation, a Northrop Grumman University Research Award, ONR YIP award # N00014-20-112571, and NSF
Dütting, P., Roughgarden, T., and Talgam-Cohen. I. Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 369-387, 2019.

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Dütting, P., Ezra, T., Feldman, M., and Kesselheim, T. Com- binatorial contracts. In 2021 IEEE 62nd Annual Sympo- sium Foundations of Computer Science (FOCS), pp. 815-826. IEEE, 2022.
Maiti, A., Fan, Z., Jamieson, K., Ratiff, L. J., and Farina, G. Efficient near-optimal algorithm for online shortest paths in directed acyclic graphs with bandit feedback against adaptive adversaries. arXiv preprint arXiv:2504.00461, 2025.
Dütting, P., Ezra, T., Feldman, M., and Kesselheim, T. Multi- agent contracts. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1311-1324, 2023.
Misra, S. and Nair, H. S. A structural model of sales-force compensation dynamics: Estimation and field implemen- tation. Quantitative Marketing and Economics, 9:211- 257, 2011.
Fiez, T., Sekar, S., Zheng, L., and Ratliff, L. J. Combi- natorial bandits for incentivizing agents with dynamic preferences. Proceedings of the Conference on Uncer- tainty in Artificial Intelligence (UAI), 2018.
Misra, S., Coughlan, A. T., and Narasimhan, C. Salesforce compensation: An analytical and empirical examination of the agency theoretic approach. Quantitative Marketing and Economics, 3:5-39, 2005.
Gayle, G.-L. and Miller, R. A. Identifying and testing mod- of managerial compensation. The Review of Economic Studies, 127))1107-11 2015.
Podimata, C. and Slivkins, Adaptive discretization for adversarial lipschitz bandits. In Proceedings of Thirty Fourth Conference Learning Theory, volume 134, pp. 3788-3805, 2021.
Grossman, and Hart, O. D. An analysis of the principal-agent problem. Foundations of Insurance Economics: Readings Economics and Finance, pp. 302 002-340.35 Springer, 1992.
Scheid, A., Capitaine, A., Boursier, E., Moulines, E., Jordan, M. I., and Durmus, A. Learning mitigate externali- ties: the coase theorem with hindsight rationality. arXiv preprint arXiv:2406. 19824, 2024a.
Harris, K., Wu, Z.. and Balcan, M.-F. F. Regret min- imization in stackelberg games with side information. Advances in Neural Information Processing Systems, 37: 12944-12976, 2024.
Scheid, A., Tiapkin, D., Boursier, E., Capitaine, A.. Mhamdi, E. M. E.,, Moulines, É., Jordan, M. I., and Dur- mus, A. Incentivized learning in principal-agent bandit games. arXiv preprint arXivv2403.03811 2024b.
Ho, C.-J., Slivkins, A., and Vaughan, J. W. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-uge agentt problems. In Proceedings of the fifteenth ACM conference on Economics and computatoo, pp. 359-376, 2014.
Train, K. E. Discrete Choice Methods with Simulation. Cambridge University Press, 2 edition, 2009.
Wu, J., Chen, S., Wang, M., Wang. H., and Xu, H. Contrac- tual reinforcement learning: Pulling arms with invisible hands. arXiv preprint arXiv:2407.00 01478, 2024.
Holmström, B. Moral hazard and observability, The Bell journal of economics, pp. 74-91, 1979.
Zhu, B., Bates, S., Yang, Z., Wang, Y., Jiao, J., and Jordan, M. The sample complexity of online contract design. arXiv preprint arXiv:221 1.05732, 2022.
Horton, J. J.. Rand, D. G., and Zeckhauser, R. J. The online laboratory: Conducting experiments in real labor market. Experimental economics, 14:399 425, 2011.
Zimmert, J. and Seldin, Y. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28): 2021.
Kaynar, N. and Siddiq, A. Estimating effects of incentive contracts in online labor platforms. Management Science, 69(4):2106-2126, 2023.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Liu, J. and Ratliff, L. J. Principal-agent bandit games with self-interested and exploratory learning agents. arXiv preprint NXX::24/22.16//5 2024.
Maiti, A., Jamieson, K., and Ratliff, L. J. Logarithmic regret for matrix games against an adversary with noisy bandit feedback. arXiv preprint arXiv:2306. 13233, 2023.
10

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
A. Technical Lemmas
Lemma A.1 (KL-divergence of Bernoulli (Maiti et al. (2023))). Consider ε > 0, < co S 1 such that & S 2.2 Let P and
Q be bernoulli distributions with means Co E and Co + E. Then we have the following:
16E²
and KL(Q, 16E²
()(
CO
Lemma A.2 (Chain Rule (Maiti et al. (2025)).. Let fz 22, Fn) and g .2..... Fn,) be two joint PMFs for tuple of random variables (Xi)ielm). Let the sample space be Qt = {0, 13". Then we have the following:
KL(f.9) = Σ f(w) (L(((())) + Σ
KL w = = w-1))
WEG
i=2
where X-i = (X Xi-1) w-: = (WI, :.:1:..;---1)
B. (T) Lower Bound for unknown behavior of the agents
Let us consider the setting where the principal doesn't know the behavior of the agents. In this case, we show that the principal necessarily incurs a regret of (2(T) under the single arm incentive. Let us choose A E [0.7, 0.71] uniformly at random. Let there be two agent types. Let w/ be the reward vector associated with each agent j E {1, 2]. We define ut = 0.2, un = 0 and un 0.2 + A. We also define u² 0.2, u² 0.2 + A and v.द O. For an incentive of A arm 1, agent 1 breaks the tie in favor of arm 1 and agent 2 breaks the tie in favor of arm 2. The reward vector for the principal is defined as 11 1, 122 0.5 and by O. In each round f, we choose agent 1 with probability 0.4 and agent 2 with probability 0.6. Let this problem instance be denoted as /A- It can be shown that the optimal incentive is to provide an incentive of A to the first arm. Anything more or less will lead to constant expected regret in each round. This rules out the possibility of discretizing the incentive space. With more refined analysis one can indeed show a linear regret.
We now formally show that any algorithm incurs a regret of Q(T)). Consider a problem instance TA where A E [0.7, 0.71). Observe that the expected reward for providing an incentive of A to the first arm is 0.6 0.5 0.4 (1 - A) 2 0.416. Next, observe that the expected reward for providing an incentive less than A to the first arm is at most 0.6 0.5 + 0.4 0 = 0.3. This includes providing incentive to other two arms. Finally, observe that the expected reward for providing an incentive more than A to the first arm is at most 1 A < 0.3. Hence, providing an incentive of A to the first arm is the best fixed incentive.
Next let us fix deterministic algorithm Alg. Let = UAE007,0777 Is. We aim to show that Ey [R(I,)) Q(T)
where R(I,7) is the expected regret of Alg on the instance 1. W.L.o.g let us assume that in each round 6, Alg chooses an incentive vector n, such that (mx); E [0.7, 0.71]. Note that choosing any other type of incentive vector would lead to a constant expected regret in that round.
Now let us analyze the behavior of Alg. Fix a sequence of agents j2.J2..... .......... fr. The behavior of Alg can be abstractly stated as follows. In each round i, it chooses an incentive vector na such that (Tr)) [0.7, 0.71). An arm i, gets chosen by agent jr. This can be considered assigning the arm in to the vector n.. Then based on the agent numbers J1...., .e (not their preference vectors) and arms i,...., 4t Alg chooses T1+1- We say assignment of an arm in to an incentive vector Ti is consistent if one of the following holds:
If 4 = 1, then for all s < t such that n. I n. we have i, = 1.
If 0 = 2, then je and for all s < such that n, 2 Te we have i, > 1.
if i 2, then j: and for all < such that n. Te we have i, 1.
Now consider all possible ways to consistently label the incentive vectors in all rounds. There are only finite number of possibilities for fixed sequence of agents. Moreover, the number of possible sequence of agents is also finite. Hence, only a finite number of incentives in the range [0.7, 0.71] is provided by Alg to the arm 1. Let this set of incentives be S.
Now consider an instance LA such that E (0.7,0.71],,S, Let D be a distribution supported on {1, 2] such that probability of choosing is 0.4 and the probability of choosing is 0.6. Now given a filtration Fr-1, ne gets fixed. Due to the definition of S,

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
we (mt)1 + A. Therefore, have ( ( I 0.3. Hence, have (T,, (TT, E F( s 0.3. Hence we have Σ E()( I 0.37. On the other hand, for the optimal incentive vector H², we have Σ (T" Je)] 2 0.4167. Hence, we have R( T). As 8 is finite, we have ((-UNi((() [R(T,
(K(TT)) T)] ((T). Due Yao's lemma, one can show that any randomized algorithm incurs worst case expected regret of S2(T).
C. Lower bound for Greedy model with Single-arm incentive
In this section, we present the proof of Theorem 2.3. We begin by establishing a lower bound of v KT for all 2 in Appendix C.1. Next, in Appendix C.2, we derive lower bound of / (Ng( log(K) for all N {K, K + 1...., 2 This result further implies a lower bound of ( /T/ hog//oog()) (K) for all N 2 2(K 22/48, By combining
these cases, we obtain general lower bound of Q(min (KKT log( N)/ log( K), K /T/ thereby proving the theorem.
log (og(K))) for all N, K 2 3.
C.1. (V)KT) Minimax Lower Bound
For policy A and instance I, we define the pseudo-regret
T U (mT, (ims)i)))
RAI
sup TH T,/11
EA,
Σ (U(
In the following, we give lower bound for the problem with the single-arm incentive.
Theorem C.1 (minimax lower bound). AK 2 N 2 3,T max 2)", 10(K00KKKK 2)}, policy A, 31, R7 Q(VKT).
Proof. To prove the minimax regret lower bound for adversarial selection of agent type, suffices to prove a lower bound for the stochastic selection of agent type.
Consider any fixed N, K,T T E N such that K 2 3, N 3, and T max max(4(K -2)3, 10,K - 2)}. Fix / 107- As
we assume T > 10(K- - 2), we have 1/10. To avoid clutter, we define
1
vi E ( K- 1-13: 1}: 8
2 3(K 2)
3
One can easily that 8; 117 3) for all i 1.....,-111
We set [0, 1J as V1 2/2 + 5. U2 1. and U/ = 0 for all j 2 3. Each agent type E [K] has reward vector
and for the K th type agent, we set n5 1, and μ = 0 for all j E [N] (3). For yt E [0, 1 We set μ² = -G........ every agent E (2...., K-1,, 1}. consistently breaks the tie by choosing the arm with the smallest index, and at each round the agent type is independently sampled from a distribution, unknown to the principal.
set μ² 3.4 ng = 1 8, and μ³ 0 for all j E [N] {2, 3). Suppose that the agent
The following gives an intuitive setting.
2
1,0,0, ..... 3'
0,0,0 O, ....,, 0
11
1
P2
1 Bz, O, ...., 0, 3'
1
143
0,
Br O, ...,. 0)
12

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
μK-1 0, 3.3' 1 - -x.,,,,.....
μК
We consider class of instances, denoted by I with fixed v, {1s Hiskk and the breaking rule given above, but allow all possible probability distributions over the agent type with p1 1.2 i... the probability of selecting the first type of agent is equal 1.- Let {T, ]=1 ! where æ (0, ......... 0) and for each E , -1,. T. (0. 3,, ... .), i.e. the second coordinate takes the value of 83, which is the minimum cost incentivize i-th type of agent play arm 2, and all others are zero. Then, consider policy set A, which maps from history to II, i.e. at each round, the principal only offers an incentive among II. We only need to lower bound inf AEA suprez R7. since
inf sup RA 2 inf sup RT = inf sup R A
A IEI
AEA IEI
where the equality holds because for all / E I and all A & A. if policy A offers a single-value incentive π & II at a certain round, then one can always alternatively propose an incentive T. = (mr.1...., Tt,K) E (for some i E [K 1]) incurs an instantaneous regret no worse than n.
To prove the above claim, it suffices consider two types single-arm incentive which has positive value on either arm 1 or arm 2. For any single-arm incentive II which has positive value on arm 1, if the value is strictly smaller than 1 1 -8x-x1 then it functions the same as (O...., 0), in the sense that their expected utilities are the same. For any other value larger than or equal to 1 - 3K 1. incentivizing any agent i E [K] to play arm 1 gives utility at most 2+c (1 Bk-1), which is negative. Notice that 2+c 3
3K-1) < 0 can be verified by using
K-2 and T 4(K 2) However, V 107
P1 1 implies that incentive (0, ... 0) yields the expected utility + 6. On the other hand, for any single-arm incentive II which has positive value arm 2, if the value is strictly smaller than - -8k-1, then it again functions the same as (0. (O.....0) 0). If the value is larger than or equal to 2 Bx-1, then there must exist i E [K" 1] such that the expected utility of π. is no worse than that of π.
Now, we construct two instances 1, E I.
Construction of Instance For instance the agent type sampled from distribution p (Pi...., .P......))))))) where
if i 1,
P;
3( K(K
2)
if E K-1), 1},
if K.
We treat each incentive in 11 as an arm, and |II| = K 1. Let r(T;)) be the expected utility of arm (incentive) π; For shorthand, we write r, == r(m:). For instance I, the expected utility vector of arms is denoted by (ri,...,,'k r.,,")-) 1). Each arm follows a Bernoulli-type distribution. Arm corresponds to the incentive (0, 0Q.....) 0) and takes value + with probability p1 2. and takes 0 with equal probability, which implies that its expected utility is
1 2 = VIP1 2 3
é 6
=
Similarly, arm (incentive) IT takes the utility of 2 with probability 1 PK = and takes 0 with remaining probability, because it takes the value of 3 as long as the agent K does not show up at that certain round, and thus the expected utility is T2 1.. Moreover, one can verify that for each arm with i E {3..... ... K 1}. the utility takes value of 1 - n,, = + 8, with probability PK Exe(,... Pz, and takes 0 with remaining probability. Thus the expected utility is
Ti 1 P-PK
Ps (1 (1-T))) --,T) =E(2...,i-1)
Σ
1-2 2
+ 3
3(K - 2)
Thus, arm is uniquely optimal, and the arm gaps for all others are the same, denoted by
A 6'
13

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Construction of Instance I'. Then, we fix an arbitrary policy A E A and construct another instance I' by modifying p in instance / to p'. Let je (2...... K-1) BA,1(T)) where 7j is the number of plays of arm j across T rounds. Then, we set the probability distribution p' = (p1 pk) by considering two cases of z. For shorthand, let
5
) 3(K - 2)
2 2-2
5c
2,e = 6
6
Case 1: 2 3. In this case, we set
i 1,
2
i (2, ................................
K 1} fz 1,2),
3(K-2)
P
l,,6
i
1,
3(K
1
+ 1z,e
i = 2,
3(K-2)
i i= K.
Case 2: =. In this case, we
1, i E {3,
K - k-1,
p/-
3(K
2]
2,,
i = 2,
3(K
2j
12,e
i = K.
Notice that one can make sanity check for all
5c
K K
3(K - 2) 12,0 3(K - 2) 6 3(K - 2)
0,
6
10T
where the last inequality holds due the assumption T (K 2)3. Moreover, - 12, -2,0 Therefore, p' is valid distribution for both cases.
1-5e 0 as 1/10.
In Case with 2 2 3, the expected utility of arm in instance I2 is
(5 +
r/
1 - PK
Σ Pj 12e bz,
rr + 2A.
1E(2
Similarly, in Case 2 with z 2, we also have r- T2 2A. Thus, the expected utility vector in instance l
(ri...., + 24..... ..A.....K-I)). -K-1).
In this case, arm becomes the unique optimal arm. For instances 1,, 12 the utility distribution of each arm i [K-1] -]-(2} remains unchanged, but only the one of arm slightly changes.
Proof of Lower Bound. Let (Di.... DK-1) and (Di.... D be the utility distributions over arm II in instances
1, respectively. For shorthand, if 2, let qa g. and if z (3..... K - 1}. let 4s - Σje (2.......) Pj. We use KL(P,, Q) to denote the KL divergence between two distributions P. Q. We define an event m = { S T and its complement as 8 Then, by a standard lower-bound argument used in MAB, we have
2
TA
R + R
N
(PP (P),((E) ( (F.r(())))))))))
2
TA
>
max PA,((E) - (A.)(1))
2
TA
KL (PA,.IPAA)
1
-
2
2
14

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
where the second inequality uses (A.)(E) (E.) (8.((8) (8) > (Pa,((E) PArr(8)) 2
1 maxe (E) (E)), and the third inequality follow from Pinsker's inequality.
The definition of implies that [T, & T/(K - 2). By the divergence decomposition lemma, we have
1807 A
KI. KI.
EA. (TL v
K
Therefore, have
TA
90T
Re + R2.
2 2
1 A
K
Recall that A = c/6. Finally, as = / 10T we have A = 6 v
K-2 which implies that AV 3607
2 1 Thus, K-2
90T
2.
R RT. = [((KT),
which suffices to give the lower bound.
Bounding KL(D= ). In instances I, 1', arm take the same positive value with probability Oz and d= + 1z,e respectively, and zero with remaining probabilities. We bound
KL(D=|ID)) 9: log
9=
+ (1 qz) log
1 92
qs + l2,e
1 4s
l,,,e
By using the fact that log(1 + x) 2 x - a²² 12222 for any x 2 0, we have
qs -x) = Uz log
Le.e 1
12,4
12
4s log
S
-2
12,6
+ 12,0
9=
2
20=
The second term is bounded by
1 -
1z.6
(1 log
= - -qz)
1
1 9z 12,0
1
9=
1z,e
1z,6
2 1z.e
< (1 9z)
+
1
qu
3
1
qu
12
2
13
12,0 +
2(1
9=)
3
(1
9=) )=)2²
where the second inequality uses series expansion and the fact that Combining both and using A c/6, we have
12.5 I-q.
5c < 1/2 as y= S and < 1/10.
12
12
13
(L(D>IID') - 2(1 9z)
+
2.6
< 562 =
2q
3
(1
)2
Thus, the proof completes.
C.2. Ω (KTlog(N)) (oT)
worst case lower bound
In this section, construct instance with K agents and N arms and establish worst-case lower bound of for all N [K,K +1, 1,.... ..... 2 22/48, This also implies worst-case lower bound of Ω [K log K
Ω (v KTlog N
T
log K
for all > 2(K -2/118
15

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Let Ko == K - 2, and define M ==
log(N-1) Let No = (Mx [o]
M M
+1 Note that log( No - 1) = M log(Ko/M) <
M (og( log(N- - 1), which implies No N.
For simplicity, we assume that both M and Ka are integers. We also assume K 2 1000. Fix an E > 0 to be specified later in the proof.
M
Let d, (i - 1) Ka for all j E [M] Let := M
:= (x E {0,1)Ko Vi E [M] Σ اj=1 E :d:-3 = 1}. Now consider a bijective
mapping / X' + No - 1]. First we define the reward vector for the principal. We have o; = 0.5 + + for each i e [No 1] and 0; == for all E {No, No + ....
Next we define the preference vector μd for agent j [Ko]- For each E X, we define 12 := + if 2 1 and (a), 0 otherwise. We define p'x, 1 and p² == for all E [N] \ [No] Next we define the preference vector μ ,k for the agent K 1. We have = :- + if i No and n.¹ : 0 otherwise. Finally we define the preference vector μ K for the agent K. We have ug ;= 1 if = No and n == 0 otherwise. In case of tie, an agent prefers an arm in [No - 1] over the arm No- Let = {TT) be a set of incentive vectors.
For all x E X. we have T.- - if = ((x and Th = 0 otherwise. Now observe that for any incentive vector π E [0, 11% there always exists a vector x II such that the regret incurred by л" is at most the regret incurred by æ. Hence, we assume that any algorithm chooses one of the incentive vectors from 11. Let us fix one such algorithm, say Alg and assume that Alg is deterministic. Now we show that algorithm Alg incurs regret of 22( / KT log(N)/ ()).. One can easily extend the result to randomized algorithms using Yao's 's lemma.
Let & = {i E {0, 10 Vi E [M] E Id,+J S 13. We define mapping : & x [K] + [0, 1] as follows. First, we define p(x, K) = for any E X. Next, we define p(x, K) 1 ás ||0||| for any x E X. Next for any x E X and j E [Ko]. we have j) = 2Kg Iz W
Ko_
We now describe an input instance I,. where x &. the instance I, in each round an agent j arrives with probability p(x, If then observe that the expected reward of playing an incentive vector n² under the instance Ly is r(x, 2) == Σド= p( 1[2 = 1) = 8 + 4Ko
1 1.1 3 that Th is the optimal incentive vector for the instance I and the expected reward is μ² = 4 be the set of input instances that we analyze our regret on.
M + 2M Eja 1f2, = 1, = 1}. where 2 E X. If x E X, then observe M
+ 5- Let I Uxex I.
At each round t, suppose Alg selects π² E I1. For the instance La with æ E X. the cumulative regret after T rounds, Rs (T), is defined as:
T (T) = T ppp Er,
Ko Σ
T
eT
r(x, 21)
Pr,((t); = 1, 1],
2
2M
j=1
where PI, probability law under the instance I,
Recall that di- (i - 1) M EM RT,(()), where
Ko for all E [M]. For any instance I, with E X, the regret be written R₂
T Ko/M
ET
R
Σ
Σ
Pr((())d = 1, = 1].
2M
2M
j=1
Fix an index i E [M]. Let 2+) = fx E {0, 1) Vj E [M] \ [i) EM Tayts = 1, ΣM Id,+s = 0). For any vector (1) x E 2000, let (d)) denote a vector in X' such that x dd+jj = 1 and x. = for all E [Ko] \ (de + j). We claim that for any
x E (())) there exists a set S. C
Kn M
of size at least Ko such that for each j E Sz, we have (T)),(T) 2 c 3M
M T.
where e is an absolute constant.
Before proving the claim, we first show that if it holds for any index i E [M], then we have Eij (Rx 2
d' VMKTT cd d. (K-22 -
TggN-11
where c' is an absolute constant. As (T) EM Ry (T), it suffices to
log(K-3
16

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
show that E,, Un d' V M
Ko
T for all i E [M.
Fix index E [M]. Now have the following:
Ko/M
E
Σ
(T)
(Ko/M)
TEX(
Σ
Σ
Ras (T)
(Ko/M)Nr =EX( jES,
Kg M
Σ
Σ
T
(Ko/M)Æ
#E jES,
Kn
Ko M
(Ko/M)y
Σ TEXC)
3M
V
T
Ko
Ko
(Ko/M)ad1 M-1
(Ko/M)M
3M
V
M
Ku T
We now prove the claim for a fixed index i E [M] and fixed vector x E x(0,, using the chain rule from Lemma A.2 in our analysis.
For an instance T,0), let fy(a1..... @r) denote the joint PMF over the sequence of binary decisions by the agent in each round under the probability distribution Py Pra,, The sample space is Ω {0, 1 1)" where indicates that the agent selects arm No. and indicates that the agent selects the arm incentivized by Alg. This is valid sample space, as the agent chooses either the arm incentivized by Alg or arm No in each round. Similarly, for the alternate instance Lz, let fo(a aT) denote the joint PMF of the binary decisions under the distribution Fi..
First, observe that the instances [200 and a differ only at agent d; + j. For each w E Ω2 let F1.,. =, Tw denote the sequence of incentive vectors chosen by Alg on w. Conditioning on the outcomes X1 = W1, X2 wa, X,-1 w we have X₁ ~ ((r under instance Ige,, and X, ~ Ber(Po) under instance Iz, where es Po = (2,,)a,yy Define = - (=d)a,;; random variable, and for each Ωt let T, ΣT I (2r,w)dess which is fixed value. Now have the following:
T Σ KL(F/(X/Xx = = --), = =w.)))
kL(Fo.f)) ΣSolw)
(L(f((T),
WER
2=
s
fo(w) Σ (an,
(due to Lemma A.
M
2
Σ folw)TT
M
wEn
? Er, [2]]
M2
where is some absolute constant.
Ka/M E, [T,[T = T. Therefore, there exists a subset Sn C Observe that ΣKa(
Kg of size at least Kg 3M
such that for each
M
j E Sg. we have E,, [T,]]]] <
3MT Fix Kp
MKa, 25ca7
Then for each j E Sg, we have KL fz) <
3TeeT
MKo 25.
Fix an index j E Sr, and let A, denote the event that T₁ S by Pinsker's inequality, we obtain the following:
12MT Ko
By Markov's inequality, we have PI, 2 Then,
KL fz)
Pr (o) (A₂) 2 P1, (A,)
2
17

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
3
3
2
4
V
50
>
2
Using the inequality above, we have Er following:
[T)] S T Py 400
(49) + 12MT
3T I
since Ko/M 2 48. Now we have the
Kg
T
T
Ka/M Σ
R00 (T)
ET
P1,00 [(t)dd+ 1,
d.4s 1]
2M
2M
1=1
T
ET
8
E7
ze [d4 + +1
2M
2M
ET
Er
[Tg]
2M
2M
.00
ET
2M
SM
1
KoT
40
co
Remark: All the calculations and probability expressions in this section are valid for T 2 poly(K).
D. Linear Bandit based approach for Principal-agent problem with single arm incentive.
We make a natural assumption on any agent's tie braking rule. If there is a tie among a set of arms I S [N] and an arm i, E I gets chosen by an agent j. then for tie among set of arms I' C I such that i, I' the agent j again chooses the arm i.. Towards the end of the section we show way to circumvent this assumption. For simplicity of presentation, we also assume that each preference vector has least two coordinates with different values.
First, we discretize the space of incentive vectors D= {ar E [0, 11 |supp(=)] 1) as follows. We initialize an empty set II. For each arm i E [N] and agent j E [K]. let T' be an incentive vector defined by T.. = 0 for * i and (4) = maxxe[N] 1 u!/ We then add th to IT. For all E [N], we define k = (0, 0.........0) 0), noting that this T; incentive vector is already included in II.
2 3 For each i E [N] and j E [K + 1), let 2dd be an incentive vector defined by #35 = 0 for + i and क, = o, + Sr. We then add # to the set 11. We now claim that the following holds for any sequence of agents j1.J2......
Now, we define A = min min "x* (
3/30 and set ET := min { A
max WEI
U (aT
sup TED
(mn 1.
Consider à E D such that Ei= (+t (SuPRED Σ (TT Er. Let i = arg maxie[N] म.. If there exists an index j E [K + 1] such that t: n. 35 then the inequality (3) clearly holds. Otherwise, let j arg max
JE[K+1]
Observe that j(+ = b(#23,50 jt) for all t E [T]. If #/! I *.. then Σt= U ,.) 2 U 2
SuPPED Din U UTT.5e) ET. If #ं. # Z.. then U(fi3.j)) 2 U(f.j.) ET as n. मे # n ET
Hence, _T, (+73), j+) 2 ΣT U(f.it) ET 2 (supteD Σt= U(T,Ji)) Thus, the inequality (3) holds in
this case as well.
The rest of the proof is identical to the main body. Nevertheless, we include it for completeness. Let 0 denote the incentive vector (0,0, O.O.....O) 0). Let us define a mapping h : II + {0, 10 Consider я E II') (0). Let a(T) == arg [a ny. For any j E [K], we have (I(T)); 1 if b(T.j) a(T) otherwise we have (I(T)) = We now construct new
18

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
set π as follows. Consider a vector 8 {0, [0,1]K. Let II == {-T II [0) 1(T)) = s}. If [T.]
then add
the incentive vector in 11, to II. If [ > 1, let ā = arg maX Va(x) - =a(=)) Observe that for any j E [K]. if 8y = then ( = va(a) (#) max (a(x)) [ max (TT.)). On the other hand if 8, = 0. then b( b(TT.))
for any π E II,. Therefore we have [ = ( for any π II,. We now add â to II. We also add 0 to II. We have [i] I min + N, + 1. Now observe that for any sequence of agents Jr we have:
and #b(*s) = [b(TJ)
}
T U(T
T
max nEll
2
sup TED
Σ U(T
-1
(4)
Hence, it suffices to focus the set of incentive vectors IT for our regret minimization problem. Now we show a reduction of this problem to an adversarial linear bandit problem. First we construct set 2 C IRK as follows. For each II, we add =d to 2 where (= = jm for all j E [K]. Next we define the reward vector y/ E RRK If agent je has arrived in round i, we set (we) if j jr and zero otherwise. Now observe that for any π E II. (TT,jE)) (=",, We). Hence, our pseudo-regret Rr is equal to the adversarial linear bandit pseudo-regret:
T (z, Ua) - Σ (Ees vi)
T
RT max IE' =6
Σ
By using EXP3 for linear bandits, we get a regret upper bound of O (min TVKTlog( (NN), KNN), for our regret minimization problem.
Now let us consider the case when the natural assumption does not hold. In that case, we instead on the set of incentive vectors IT for our regret minimization problem. Now we show a reduction of this problem to adversarial linear bandit problem. First, we construct set Z C IR as follows: for each π E I1, we add 2T to Z, where (z*), = (T),j) for all j E [ Next, we define the reward vector y E RKK If agent je arrives in round f, we set (ye) = 1 if = je and (ye); = 0 otherwise. Observe that for any x E II, je (=*, vv).. Hence, our pseudo-regret Ri is equal to the adversarial linear bandit pseudo-regret:
T
Rx max 2E2
Σ
(z, Uc)
Σ (ze: Me)
Using the EXP3 algorithm for linear bandits, we obtain a regret upper bound of O OV KTllgg(N) for our regret minimization problem as | = O(KN). However, this upper bound can further improved as follows. Let R {e, [e]K be the set of all possible reward vectors. Define 2g as the smallest subset of 2 such that
1
max min max (== 2 - - 2E2 e'EZa VER
By the above inequality, it suffices to focus on Zo for our regret minimization problem. It can be shown that |Zol S min(2KN + +N + 1, (6KT)*). Using the EXP3 algorithm for linear bandits on the reduced arm set Zo, we achieve a regret upper bound of O (v (og)), min (K /Tlog (TT())))))
E. Smooth Demand with Unknown Agent Types
E.1. Proof of Theorem 4.1
Proof. We consider the instance were the principal reward of first N - 1 products is equal to 1, and the last product is 0.
We partition [0, 1 incentive for each arm by [c] equal parts, and we propose a class of agent types (A'-) " [K]] were given incentive π, the agent's selection probabilities is defined by Eq. 1-2. The bonus function is defined as B(x) == ايي min(z, z). Consequently, the expected principal reward when agent type A arrives and incentive is offered with nonzero element to arm i would be
N-1 + (1 n. B(T je)
if E [je, (j 1)c]
N-1
I6N
E[((T)] = Σ (1 m) (1,5)
N-1
if E [0, 1 N
I6N
T=1
N-1
otherwise.
16N
19

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
Lemma E.1. For all agent types (8,j), Assumplion 1.1 holds.
For all n, n' where || - = A. let ((T) and (xx) be the indices were incentive is nonzero respectively (if I 0, then ((T) = N 1) 1
Pr(a(T, (i,3))) = 1]- Pr|a(T' (r.0()'((6.))) 1] = - Pr|a(z,(1 [(=)) - Pr(a(T', (i,5)) [(=)]]
+ Pr[a(T, (i.j))) [(=')] Pr(a(m', ( (i.j)) [(=))]
+ Pr[a([ (i.j)) N] Pr|a(a', (i.j)) NN]
1
Pr/a(T, (4,5)) = =[(=)] 16N
+ Pr|aat"', (t,5)) = [(=')] 16N
+ Pr[a((, (i.j)) [(T)] Pr[a( (r'' (i. [(r')]]
d
I 4 max dr 16N x)
A + 4B 4minn A))
(Mean value theorem)
A + (L - 1)4 = LA
Therefore, if an algorithm can't play the good interval incentive of each agent type consistently, the expected regret would
8 (L ////2// For i [N], E [c]. Vi' * i), then "i.j. D.j- for all (i,j) J. So for any algorithm Alg the problem instance (i,j) J, we reduce it to algorithm Alg in stochastic MAB setting instance with A A= A= j') E | E }1- as the arm set. If algorithm Alg offers incentive æ E Dr to agent, and receives reward r(T); then Alg' selects arm (i',j)) and receives reward max B[r(T)] + The where Th ~ 1). So the expected regret of algorithm Alg is lower-bounded by the expected regret of Alg'. For instance (i,j) E J. the expected reward of the reduced MAB problem is bounded by
be {L 1)eT, setting E (L -1) 1)12/3/// 2/3 2/3/2//////// 1/33 the regret would be 1
let D., { [0, 1.11 m; [je, (j + 1)c), n.
(L-1)e
-(
((,)))
16.
16
N-1
otherwise.
Using instance-dependent lower bound for MAB with Gaussian noise ((Lattimore & Szepesvári, 2020), Section 16.2), we have
inf sup Rr 2 inf sup R2 2 3 A a((L 11
Alg jEJ
JEJ
E.2. Equivalence to greedy model with Gaussian noise
Lemma E.2. for an agent of type j arriving at time their preference vector is n³ + +n', where μd is the expected preference vector if agents of type j. and n² ~ NN, 1) is independent noise of the agent, fhenfoo Greedy choice model Assumption I.I holds.
Proof.
Pr(a(mr:J)) =i] = Pr(i" E arg max { ( + Tx, + mt
iE[N]
= Prr[p + + max !i + cal E(
(define : 11/ + me, i)
20

---

Learning to Incentivize in Repeated Principal-Agent Problems with Adversarial Agent Arrivals
/ Prin Cs- =yl Pr( max i
oi + S yldy
N
f 6l - (x))
(II Egp
o ci) ) dy
where and & are PDF and CDF of standard normal distribution respectively. Since Pr(a(Te.Ji)) -*] is everywhere differentiable, and v Pr(a( jt) i*] is bounded over E [0, 1|N, using mean-value theorem, it's also Lipschitz. U
21


Reviews:
[{"review_id": "elQbqIlb8s", "reviewer": "Reviewer_LMoE", "summary": "The paper introduces a repeated principal-agent setting where agents arrive in an adversarial fashion. The principal interacts with agents of unknown types by strategically offering incentives to influence their decisions. The paper proposes algorithms with sublinear regret bounds under two key settings: (1) when the principal knows the best response of each agent type and (2) when agent decisions vary smoothly with incentives. The authors also present matching lower bounds for both settings and extend the results to cases where the principal can incentivize multiple arms simultaneously.\n\n## update after rebuttal\n\nI thank authors for their detailed responses. The paper made reasonable amount of advancement in the existing literature, but I still do not see any noteworthy technical breakthrough here.  Hence, I am keeping my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. We now address their concerns.\n\n**On technical breakthrough:** While we respect the reviewer’s opinion, we believe our work includes notable technical breakthroughs. We develop novel lower bound techniques tailored to the greedy model setting—methods that, to the best of our knowledge, are new and have the potential to extend to other related problems like regret minimization in linear bandits and stackelberg games. Additionally, we develop a new discretization approach and provide a reduction to linear bandits, which together yield near-optimal regret bounds. To the best of our knowledge, this reduction strategy is novel and has not been explored in prior work.\n\n**Real world motivation of the two models:**\n\nWhile we briefly discussed motivating examples in the introduction, we are happy to expand on them here to further clarify the relevance of the two models to real-world scenarios.\n\n*Best response model.* A natural example arises in online shopping, where customers make purchase decisions based on visible discounts (i.e., incentives). Customers often wait until a discount reaches a historical low or crosses a personal threshold before making a purchase (Gunadi & Evangelidis, 2022). Similarly, in online labor markets, crowdworkers frequently accept tasks only if the offered payment exceeds a minimum expected amount (Horton & Chitoni, 2010). These behaviors reflect a threshold-based decision process, motivating our use of the best response model. In this model, the agent plays an arm only when the incentive on that arm exceeds a predefined threshold.\n\n*Smooth response model.* In contrast, consider routine purchases such as daily necessities. Here, small changes in discounts do not lead to abrupt changes in behavior but instead gradually affect the probability of purchase (Bijmolt et al., 2005). A similar pattern is observed in ad click-through behavior, where users’ likelihood of clicking on an ad increases with the attractiveness of the offer—such as a better discount or a more personalized promotion—but does so in a smooth, probabilistic manner rather than through sharp thresholds (Bleier & Eisenbeiss, 2015). These scenarios motivate the need for a more flexible response model in which decisions vary smoothly with the incentive.\n\n*References*:  \n\nGunadi, M. P., & Evangelidis, I. (2022). The impact of historical price information on purchase deferral. Journal of Marketing Research, 59(3), 623–640. \n\nHorton, J. J., & Chilton, L. B. (2010). The labor economics of paid crowdsourcing. In Proceedings of the 11th ACM conference on Electronic commerce (pp. 209-218).\n\nBijmolt, T. H., Van Heerde, H. J., & Pieters, R. G. (2005). New empirical generalizations on the determinants of price elasticity. Journal of marketing research, 42(2), 141-156.\n\nBleier, A., & Eisenbeiss, M. (2015). Personalized online advertising effectiveness: The interplay of what, when, and where. Marketing Science, 34(5), 669-688.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I only read through the proof sketch", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "The adversarial setup is a meaningful addition to the existing literature in repeated principal-agent problem.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The paper begins by formalizing the hard cases for the repeated principal-agent problems in general and then introduces natural conditions where it is possible to design no-regret learning algorithm. Overall, it is a nice complement to the existing literature on repeated principal-agent problem. The paper is overall well-written. That said, I do not see any technical breakthrough here, as the designs and analysis of these algorithms are well-expected.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Can you provide some real-world motivation on the two models you consider?", "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": "PHj1ZlOm0T", "reviewer": "Reviewer_QVD9", "summary": "This paper studies a repeated principal-agent game, where the principal delegates their action to $K$ agents, each choosing from $N$ actions, with agent types ($i_t \\in [K]$) assigned adversarially in each round. First, they show that achieving no-regret requires the principal to have prior knowledge of the agents' behavior—specifically, access to their best response functions—when agents act greedily (maximizing their utility in each round). Under this greedy action model, the paper presents an algorithm with $O(\\min(\\sqrt{KT\\log N}, K\\sqrt{T}))$ regret (in the single-arm incentive case) and proves a matching lower bound up to an $O(\\log K)$ factor. They then extend their results to a smoothed action model, where agents choose arms probabilistically based on an unknown distribution that varies smoothly with the incentive vector (the principal's payout vector for each arm). In this smoothed model and the single-arm incentive case, they provide a no-regret algorithm and a matching lower bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. We now address their concerns.\n\n **On Presentation suggestions:** We thank the reviewer for the helpful suggestions regarding presentation. We will carefully incorporate them to improve clarity and readability in the next version.\n\n\n**Comparison with Harris et al.**\n\nWe thank the reviewer for referring us to the recent NeurIPS paper by Harris et al. (2024) and the follow up concurrent arXiv preprint by Balcan et al. (2025). While these works share similarities with our framework—such as a principal-agent setup (which corresponds to the leader-follower formulation in their paper), with unknown agent types appearing each round—their settings differ in several important ways that prevent them from subsuming our problem:\n\n1. *Action Space*: In our setting, the principal chooses an incentive vector from the hypercube $[0,1]^N$. In contrast, in the work by Harris et al., the leader selects a mixed strategy from a probability simplex defined over a finite set of actions $\\mathcal{A}$.\n\n\n2. *Agent/Follower Rewards*: In our model, if agent $j$ selects arm $i$, they obtain a reward of $\\mu_i^j + \\pi_i$, where $\\pi$ is the incentive vector chosen by the principal. Conversely, in the leader-follower mode of Harris et al., the follower's reward for choosing action $a_f$ is $\\sum_{a_\\ell \\in \\mathcal{A}} x[a_\\ell] u_j(z, a_\\ell, a_f)$, where $x$ is the mixed strategy chosen by the leader and $z$ represents contextual information.\n\n3. *Principal/Leader Rewards*: In our setting, if arm $i$ is chosen, the principal’s reward is $v_i - \\pi_i$. On the other hand, in Harris et al., if the follower chooses action $a_f$, the leader’s reward is $\\sum_{a_\\ell \\in \\mathcal{A}} x[a_\\ell] u(z, a_\\ell, a_f)$, where $x$ is the mixed strategy chosen by the leader and $z$ is contextual information.\n\nThese distinctions—particularly in the action spaces and the reward structures—mean that the Stackelberg game setting of Harris et al. (2024) does not subsume our principal-agent formulation. Nonetheless, we will clarify this comparison in our paper and emphasize that extending our principal-agent framework to a contextual setting, akin to theirs, would be a promising direction for future work.\n\n**On concrete applications of our problem setting:** While we briefly discussed motivating examples in the introduction, we are happy to expand on them here to further clarify how the studied problems apply to real-world scenarios.\n\n*Adversarial arrival of agents.* In practice, agent arrivals often deviate from fixed stochastic patterns due to factors like non-stationarity, strategic behavior, or external influences. For instance, in online shopping, discount ads are shown to all users, but only some choose to act—often in response to timing, personal context, or even social trends. The sequence of users who respond may not follow any stable distribution. Modeling arrivals adversarially allows us to account for such unpredictable and potentially strategic participation without assuming a specific arriving distribution.\n\n*Agent response models.* For additional motivating examples of the best response and smooth response models, please refer to our detailed response to Reviewer LMoE.\n\n**On the case when the principal receives only bandit feedback:**\n\nUnder stochastic bandit feedback, our upper-bound results for single-arm incentives under the greedy model extend naturally to the case where the principal’s rewards are unknown, as follows. We retain the current discretization of the incentive vector space and run Tsallis-INF over these discretized points, incurring a regret of $\\sqrt{KNT}$. However, in contrast to the known principal-reward setting, the dependence on $N$ cannot be improved to achieve a regret bound of $\\min\\left(\\sqrt{KT\\log N}, K\\sqrt{T}\\right)$. This is because an $N$-armed stochastic multi-armed bandit problem can easily be reduced to our principal-agent problem, and it is known that an $N$-armed stochastic multi-armed bandit problem has a regret lower bound of $\\Omega\\left(\\sqrt{NT}\\right)$.", "claims_and_evidence": "This paper is mainly theoretical and its claims are supported by proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I found no specific issues with their proofs, particularly the main upper bounds in Theorem 3.1, Theorem 3.2, and the unnamed no-regret result in Section 4.1.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper contributes to the literature on learning in repeated principal-agent games, particularly in the setting where agent types arrive adversarially, providing near-optimal algorithms for this scenario. Prior works have primarily considered settings where the principal repeatedly contracts with a fixed but unknown agent type (Scheid et al., 2024b; Dogan et al., 2023a,b) or where the agent's type is drawn stochastically from a fixed distribution (Ho et al., 2014; Gayle & Miller, 2015). While some prior settings have advantages—e.g., Scheid et al. study the case where the principal's reward vector is drawn from an unknown distribution, whereas this work assumes a known reward vector—this paper's adversarial arrival model is relatively novel (but not completely new, see the section below) and warrants further study.", "essential_references_not_discussed": "There is a missing prior work, Harris et al. (2024), which studies a very similar problem setting. See the weaknesses section for details.", "other_strengths_and_weaknesses": "**Strengths:**  \n- This paper studies a strong setting in the repeated principal-agent game where the agent's type is chosen adversarially.  \n- It provides a solid negative result, motivating the necessity for the principal to know each agent's best response rule.  \n- For their algorithms, they establish nearly matching lower bounds.  \n\n**Weaknesses:**  \n- (Minor weakness) Lack of concrete applications for the studied problem setting.\n- The setting of this paper appears to be subsumed by that of Harris et al. (2024), which studies a general principal-agent (Stackelberg) game with side information, adversarial agent-type arrivals, and bandit feedback (where the principal observes only the agent's chosen action). While Harris et al. achieve a regret bound of $O(T^{2/3})$ in this setting, worse than that of this work (Note that, a concurrent result by Balcan et al. (2025) improves this to $O(T^{1/2})$), as their setting includes side information, it inherently considers a stronger regret benchmark. Given the similarities in problem formulation, a comprehensive comparison between this work and Harris et al. seems necessary.  \n\n**Reference**  \n- Harris et al. Regret Minimization in Stackelberg Games with Side Information, *NeurIPS* 2024.  \n- Balcan et al. Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information *arXiv:2502.00204* 2025.", "other_comments_or_suggestions": "- Table 1 could include pointers to the corresponding theorem numbers to improve readability.  \n- A proof sketch or illustration of the main idea or strategy in the main text would be very helpful.  \n- Formally stating the regret upper bound for the smoothed case as a theorem would enhance the paper's coherence, readability, and navigability.", "questions_for_authors": "Is it possible to extend the result to the case where the principal's rewards are unknown, but the principal receives only bandit feedback?", "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": "rODjRUKZ9l", "reviewer": "Reviewer_tqFh", "summary": "Building upon the literature on repeated principal-agent games, this paper explores a setup where a principal recommends an action from a bandit instance to an agent and offers a payment so the agent is incentivized to follow the recommendation. Two cases are studied: first when the agent greedily chooses her utility and second, when the agent chooses her action with a smooth choice model. The difference with the state-of-the-art here is that the agent's type varies over type and is unobserved to the principal. To stick with the contract theory terminology, it is a setup with observed action and unknown type (i.e. adverse selection). The adversarial arrival of agents of different types makes it necessary to introduce a new definition of regret and to use a discretization of the incentives' space before linking the problem to adversarial bandits.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. We now address their concerns.\n\n**On instance-dependent Algorithm for the smooth setting:**\n\nFor the smooth setting, after establishing the minimax regret bounds, we directly apply the Zooming algorithm from [1] in Section 4.3 of our paper. The instance-dependent regret bound then follows from Theorem 3.1 in [1], which characterizes the regret in terms of the zooming dimension. We agree that a clearer presentation would benefit the reader; thus, if space permits, we will include a pseudocode outline of the Zooming algorithm along with a precise statement of the associated regret bound, citing Theorem 3.1 of [1] for completeness.\n\n[1] Podimata, C. and Slivkins, A. Adaptive Discretization for Adversarial Lipschitz Bandits. In *Proceedings of the Thirty-Fourth Conference on Learning Theory*, vol. 134, pp. 3788–3805, 2021.\n\n**Comparison with Zhu et al.**\n\nSince both papers consider settings where the agent best responds to the incentive, a key technical challenge in both is that the principal’s utility function is not Lipschitz continuous with respect to the incentive. That is, small changes in incentives can lead to abrupt shifts in agent behavior. However, the approaches for handling this non-smoothness differ significantly. Zhu et al. (2022) identify directions in the incentive space along which the utility function is continuous and construct a discretization based on spherical codes to cover these directions.\n\nIn contrast, our approach leverages structural knowledge of agent behavior: for any given incentive, we know exactly which arm each agent type will choose. This allows for a more tailored discretization strategy. For instance, in the single-arm incentive setting, we enumerate threshold points across agent types and prune the incentive set by retaining only the most rewarding vectors, making the discretization independent of $N$. In the general incentive setting, we again use the knowledge of agents’ best responses to characterize the incentive space as a polytope, and the algorithm only needs to consider the extreme points of that polytope.\n\n**On the Prevalence of the Regret Definition in the literature:**\n\nAs we highlight in the paper, our work initiates a new problem setting that combines elements of the principal-agent framework with adversarially ordered arrivals. In this setting, the regret notion we adopt arises naturally, and closely related definitions have been studied in the context of Stackelberg games. For instance, the following works—one of which was also cited by Reviewer QVD9—explicitly consider this form of regret:\n\n*References*\n1. Harris et al. Regret Minimization in Stackelberg Games with Side Information, NeurIPS 2024.\n2. Balcan, Maria-Florina, et al. Commitment without regrets: Online learning in Stackelberg security games. Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015.\n\nAlthough this exact regret formulation may not have been explored in the contract design literature to our knowledge, we believe it is a natural and principled objective in our setting. As such, it may help inspire new directions in principal-agent and contract-design problems under adversarial settings.\n\n**On the case when the principal receives only noisy feedback:**\n\nUnder stochastic bandit feedback, our upper-bound results for single-arm incentives under the greedy model extend naturally to the case where the principal’s rewards are unknown, as follows. We retain the current discretization of the incentive vector space and run Tsallis-INF over these discretized points, incurring a regret of $\\sqrt{KNT}$. However, in contrast to the known principal-reward setting, the dependence on $N$ cannot be improved to achieve a regret bound of $\\min\\left(\\sqrt{KT\\log N}, K\\sqrt{T}\\right)$. This is because an $N$-armed stochastic multi-armed bandit problem can easily be reduced to our principal-agent problem, and it is known that an $N$-armed stochastic multi-armed bandit problem has a regret lower bound of $\\Omega\\left(\\sqrt{NT}\\right)$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "There are no experimental evaluation criteria beyond a theoretical regret bound. It is not an issue to avoid experimental evaluation to me, since the paper is mostly about theoretical issues (as is the literature in this field).", "theoretical_claims": "All the claims of the paper are supported by clear proofs.", "experimental_designs_or_analyses": "There are no experiments in this paper.", "relation_to_broader_scientific_literature": "The paper provides a consistent literature review in two areas: principal-agents problems (an economics' field) and online learning. Relying on recent works that consider repeated principal-agent problems (typically Dogan et al. Repeated principal-agent games with unobserved agent rewards and perfect-knowledge agents, Scheid et al., Incentivized learning in principal-agent bandit games, and then Ben-Porat et al., Principal-Agent Reward Shaping in MDPs which considers a MDP setup, among other extensions), the paper introduces a new complexity to the problem which is the adversarial agents arrivals (with different types).\n\nTo tackle it, the paper introduces a regret definition very close to the one defined in Zhu et al., The sample complexity of online contract design (this paper studies a repeated contract design setting with unobserved action and unknown types) and uses a discretization of the incentives' space a bit similar. While the discussion on the relation with the [repeated] principal-agent literature seem consistent to me, a  discussion with the latter reference might be interesting.", "essential_references_not_discussed": "NA.", "other_strengths_and_weaknesses": "I really appreciate the setup: it seems to interesting to me to account for adversarial agents' types. Also, I enjoy the technical approach which consists in first discretizing the incentives' space and then running an adversarial bandit algorithm. The work is nicely supported by a lot of lower bounds provided.\n\nI appreciate having an outline of the important proofs in the main text and the full proof in the appendix.\n\nFrom my reading, the regret upper bounds in page 8 for Instance-dependent Algorithm for Single-Arm/General Incentives are stated without a theorem nor a clear proof. I think that the paper would benefit from a clear presentation of the algorithm used in that setup (including the application of the Zooming algorithm), a formal theorem as well as proofs. The employed tools seem very interesting but the way they are presented in the current version is definitely too brief.", "other_comments_or_suggestions": "I would have appreciated a clear statement of the proposed algorithms. I believe that it would improve readability.", "questions_for_authors": "Could you discuss a bit more the relation between the technical issues of your approach as compared to Zhu et al., The sample complexity of online contract design? Especially the way of discretizing the contract/incentives space.\n\nIs the definition of regret that you give common in the unknown opponent principal-agent literature? Or in contract design more generally.\n\nDo you believe that tackling the extension where the principal only observes noisy rewards is doable or close in the analysis?", "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": "QoknpZMRUv", "reviewer": "Reviewer_wWxu", "summary": "This work explores sequential incentive design in a repeated principal-agent problem with adversarially ordered agents. The principal faces $K \\geq 2$ agent types (unknown) and selects incentives for one of $N$ arms to influence agent decisions, which are made based on both intrinsic utility and offered incentives. The goal is to minimize regret relative to the optimal ex-post incentive strategy. The contributions of this paper are:\n\n1. Demonstrate that algorithms lacking prior knowledge of agent behaviors (e.g., best-response functions) inevitably incur linear regret in greedy-response, single-arm incentive settings.  \n\n2. Propose a reduction-based approach for adversarial linear bandits by discretizing the continuous incentive space. Achieved an upper bound of O(min{ $ \\sqrt{KT log(KN)}, K\\sqrt{T}$ }) for greedy-response agents with known types.  \n\n3. Introduce a novel polytope discretization for large incentive spaces, enabling $O\\left(K\\sqrt{T}\\right)$ regret when incentivizing multiple arms. \n\n4.  Design an algorithm achieving $\\tilde{O}\\left(L^{1/3}N^{1/3}T^{2/3}\\right)$ regret for Lipschitz-smooth agent responses.  \n  \nThis study pioneers the analysis of adaptive incentive mechanisms against adversarial agent arrivals, establishing tight regret bounds under assumptions and addressing exploration-exploitation trade-offs in dynamic incentive allocation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review. We now address their concerns.\n\n**Typo regarding $L$:** Thanks for pointing out this typo. This should be $L \\ge 1$.\n\n**Regarding the parameter $\\Delta$ in our linear-regret lower bound:** In the principal-agent problem, the incentives provided to any arm lie within the range $[0,1]$. In our lower bound instance, the optimal incentive to provide to arm $1$ is $\\Delta$; any deviation above or below this value results in linear regret for the algorithm. We select $\\Delta \\in [0.7, 0.71]$, which is relatively large on the $[0,1]$ scale.\n\n**Response to reviewer's question:** Our upper bound applies to all scenarios; the tie-breaking assumption is made only for simplicity of presentation. We have addressed all possible tie-breaking scenarios in the appendix. In contrast, our lower bound is a worst-case bound. Thus, analogous to multi-armed bandit problems, establishing instance-dependent upper and lower bounds in this setting would be an interesting direction for future research.", "claims_and_evidence": "In lines 192-196, the authors claim that to achieve sub-linear regret, the method must exactly learn $\\Delta$. In this paper, $\\Delta \\in [0.7, 0.71]$. Does this imply that achieving sub-linear regret is difficult only when $\\Delta$ is relatively small?", "methods_and_evaluation_criteria": "The method makes sense, and there are no evaluation datasets.", "theoretical_claims": "I have checked the correctness of any proofs for theoretical claims.", "experimental_designs_or_analyses": "There are no experiments.", "relation_to_broader_scientific_literature": "This paper focuses on repeated principal-multi-agent problems, which have been extensively studied. The difference lies in the fact that this paper emphasizes agents arriving in an adversarial order, whereas previous work assumes that agents arrive in a fixed distributional order.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "**Strengths**\n\n1. This paper provides a detailed discussion on the upper and lower bounds of the repeated principal-agent problem under different agent behaviors and incentive strategies.\n\n2. This article has a clear logical structure and rigorous proofs for the theorems.\n\n3. This paper innovatively defines a polytope to address the issue of an excessively large incentive space, using the extreme points of the polytope to determine the optimal incentive.", "other_comments_or_suggestions": "1. In line 149, \" $L \\geq$ \" is incomplete.", "questions_for_authors": "In Section 2.2, the arms are mapped to {0, 1}, and the rewards are approximately set to 0.5. Additionally, in Section 3.1, the assumptions regarding tie-breaking have been simplified. If the discretization were to be closer to the real setting and more complex, would it affect the derivation of the upper and lower bounds?", "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:

Meta-review: All the Reviewers agreed that the paper clearly passes the bar for acceptance at ICML. Thus, I will propose acceptance.
Decision: Accept (poster)