Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Authors: Junyan Liu
Lillian J. Ratliff
Venue: ICML 2025 poster (2025)
Keywords: Bandits
Principal-agent problem
Incentive design
Regret minimization
Primary area: theory->online_learning_and_bandits

Abstract: We study the repeated principal-agent bandit game, where the principal indirectly explores an unknown environment by incentivizing an agent to play arms. 
Unlike prior work that assumes a greedy agent with full knowledge of reward means, we consider a self-interested learning agent who iteratively updates reward estimates and may explore arbitrarily with some probability.
As a warm-up, we first consider a self-interested learning agent without exploration.
We propose algorithms for both i.i.d. and linear reward settings with bandit feedback in a finite horizon $T$, achieving regret bounds of $\widetilde{O}(\sqrt{T})$ and $\widetilde{O}(T^{\frac{2}{3}})$, respectively. 
Specifically, these algorithms rely on a novel elimination framework coupled with new search algorithms which accommodate the uncertainty from the agent's learning behavior. We then extend the framework to handle an exploratory learning agent and develop an algorithm to achieve a $\widetilde{O}(T^{\frac{2}{3}})$ regret bound in i.i.d. reward setup by enhancing the robustness of our elimination framework to the potential agent exploration. Finally, when our agent model reduces to that in (Dogan et al., 2023a), we propose an algorithm based on our robust framework, which achieves a $\widetilde{O}(\sqrt{T})$ regret bound, significantly improving upon their $\widetilde{O}(T^{\frac{11}{12}})$ bound.

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Junyan Liu
Lillian J. R
Abstract
more et al., 2015). In most bandit frameworks, player directly interacts with unknown environment by repeat- edly playing arms and observing the corresponding rewards. However, those frameworks often fail to capture the unique challenges faced in many online marketplaces, where the player can only indirectly interact with the environment. For instance, in online shopping, the website (player) learns users' preference (unknown environment) by observing pur- chase behaviors. To acquire a comprehensive knowledge of users' preferences, the website typically needs to provide external incentives, such as discounts or coupons, for agents to encourage exploration.
This paper studies the repeated principal-agent bandit game, where the principal indirectly ex- plores an unknown environment by incentivizing an agent to play arms. Unlike prior work that assumes greedy agent with full knowledge of reward means, we consider self-interested learn- ing agent who iteratively updates reward estimates and may explore arbitrarily with some probability. As a warm-up, we first consider self-interested learning agent without exploration. We propose algorithms for both i.i.d. and linear reward set- tings with bandit feedback in a finite horizon T, achieving regret bounds of Ö(VT) and ((T%)s. respectively. Specifically, these algorithms rely novel elimination framework coupled with new search algorithms which accommodate the uncertainty from the agent's learning behavior. We then extend the framework to handle an ex- ploratory learning agent and develop an algorithm to achieve a O(T%)s regret bound in i.i.d. reward setup by enhancing the robustness of our elimina- tion framework the potential agent exploration. Finally, when our agent model reduces to that in Dogan et al. (2023a), we propose an algorithm based on our robust framework, which achieves a ((VT) regret bound, significantly improving upon their (/12) bound.
Motivated by such scenarios, recent work (c.g., Dogan et al. (2023a;b); Scheid et al. (2024b)) frames this prob- lem principul-agent bandit game, modifying the classic principal-agent problem in economics (see, e.g., Bolton & Dewatripont (2004); Laffont & Martimort (2009)) with repeated engagements and stochastic rewards where the aforementioned player refers to a principal, and the agent refers to end-users. With arms representing vector of incentives, in each round of the game, the principal first selects arm, and after observing these incentives, the agent greedily selects amongst their own arms to maximize their expected reward plus the offered incentive (henceforth we call this arm miee-maiiiizer.. The chosen arm yields two stochastic rewards drawn from different distributions: one for the principal and one for the agent. Notably, the principal observes their own reward and the selected arm, yet remains agnostic of the reward the agent side.
Despite the merger of classic models of incentives with ban- dits, most work relies on an oracle-agent assumption, where the agent has complete knowledge of the true reward means (expected rewards) and always selects the true-maximizer. This assumption, general, will not hold in real-world sce- narios. For instance, in the case of online shopping, users rarely fully understand their own preferences over many options without a prolonged learning process. Recently, a notable step towards more realistic model was taken by Dogan et al. (2023a) who consider an an agent that employs an exploratory learning behavior: the agent allowed to explore an arm, different from the true-maximizer, with a small probability decreasing over time. However, even in
1. Introduction
Bandits learning is a powerful framework for solving broad spectrum of sequential decision-making problems, such recommendation systems (Li et al., 2010), clinical trials (Villar et al.. 2015), and resource allocation (Latti-
Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, WA USA "Electrical & Com- puter Engineering, University of Washington, Seattle, WA USA. Correspondence to: Junyan Liu <junyanll @cs, wwc.saaiintooo.dou
Proceedings of the 4dnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
this more practical model, the assumption remains that the agent selects the true-maximizer when not exploring', and their result only achieves an (12))) regret bound where T is the horizon.
L.I.D rewards: We first propose Algorithm 1 for the i.i.d. reward and greedy agent setting, where the agent always greedily chooses the empirical maximizer without exploration. The proposed algorithm enjoys expected regret bound, where K is the number of arms. The proposed algorithm is estab- lished upon a novel elimination framework coupled with an efficient search algorithm (Algorithm 3). Different from existing elimination approaches that permanently eliminate badly-behaved arms, our algorithm plays bad arms in some rounds so as to benefit Algorithm 3 in future searches for optimal incentives. The regret up- per bound of our algorithm matches the lower bound up to a logarithmic factor. Notably, when reducing to the oracle-agent setup, our worst-case bound matches that of (Scheid al., 2024b, Algorithm 1) as long as T > K.
O( lo7log((7))
A more recent work by Scheid et al. (2024a) allows the agent to adopt no-regret learning algorithms that adhere to the key assumption that the no-regret property holds universally for any time period and any principal's ' algorithm offering con- stant incentives during this period. However, this universal no-regret preservation assumption limits their framework's applicability to certain simple, yet realistic, learning behav- iors. This is due to the fact that their assumption implicitly requires the agent's 's no-regret algorithm to strategically ex- plore the environment, but in many real-world applications such as online shopping, the agent (buyer) is unlikely to design such sophisticated strategies. Consequently, their agent model does not encompass simple but arguably realis- tic agent models such as the eff-iinterested learning agent with and without arbitrary exploration (see Appendix B for details). Given results, it still remains unclear what regret bounds can be achieved for these realistic agent models and whether ((T)))2) regret bound in Dogan et al. (2023a) can be improved. This motivates two natural questions:
We further propose Algorithm 5 for a self-interested learning agent with exploration and the i.i.d. reward set- ting, achieving a ((KV/T3/a) regret bound. In partic- ular, Algorithm 5 builds upon Algorithm I and lever- ages the probability amplification idea to enhance its robustness to agent exploration. Abstractly, Algorithm 5 repeats the incentive search and elimination processes logarithmically many times. It uses an incentive testing procedure to identify the most reliable estimated incen- tives and employs a median selection strategy to refine the active arm set. Since we consider more general learning behavior than Dogan et al. (2023a), our algo- rithm improves their regret bounds from ((71))1) to ÖTT4)). Furthermore, by reducing our agent's learning behavior to the one studied by Dogan et al. (2023a), we can achieve an even better regret bound (VKT),
1. Can we generalize the agent's 's behavior considered in Dogan et al. (2023a)?
2. Given the aforementioned generalization, can we design algorithms that outperform the (TT))122 regret bound?
In this paper, we provide affirmative answers to both ques- tions. To address the first question, we consider a self- interested learning agent with exploration behavior which allows the agent to explore non-maximizer arms with a de- creasing probability similar to to the setup in (Dogan et al., 2023a). The key distinction is that when the agent decides not to explore, she plays an arm that maximizes the empir- ical mean plus the incentive (henceforth we call this arm empirical maximizer), instead of the true-maximizer as- sumed by Dogan et al. (2023a). As discussed in Section 2, this learning behavior subsumes that of (Dogan et al., 2023a) as a special case. Under this more realistic learning behav- ior, we examine the i.i.d. reward setting, where the rewards of the principle and the agent are independently sampled from distinct yet fixed distributions. Further, we study the linear reward setting, in which the rewards of arms can be linearly approximated.
Linear rewards: We introduce Algorithm 7 for the lin- ear reward setting, achieving an expected regret bound of (dHa)44)s where d is the dimension. Our algorithm is grounded in the new elimination framework analogous to the i.i.d. case, but more importantly it is equipped with an efficient and robust search method Allgorithm 8) for the high-dimensional case. Specifically, Algorithm 8 is built upon (Liu al., 2021, Algorithm 1), but it cuts the space conservatively to account for the uncertainty resultant from the learning agent.
Related Works. The principal-agent model is a fundamen- tal problem in contract theory (Bolton & Dewatripont, 2004; Grossman & Hart, 1992; Laffont & Martimort, 2009). Moti- vated by online marketplaces, a substantial body of research has explored repeated principal-agent models to, for exam- ple, estimate the agent model or minimize the regret for the principal (Ben-Porat et al., 2024; Fiez et al., 201 Sa;;; Ho et al., 2014; Ivanov et al., 2024; Ratliff & Fiez, 2020; Zhu et al., 2022; 2023). Categorized by different types of information asymmetry, principal-agens problems are typ-
The contributions are summarized as follows; refer to Ta- ble 1 for a summary table of regret bounds.
'One caveat here is that with a special coordination between the principal and the agent, agent can select the true-maximizer without the knowledge of the expected rewards. We refer readers to Appendix C for a discussion.
2

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Table I: Overview of related work for principal-agent bandit games with different agent's behaviors.
Agent behavior involves
Algorithms
Reward
Regret bound
Empirical mean?"
Exploration?
Dogan et al. (2023b)
X
O max K, Vlg TVVT)
IPA Scheid et al. (2024b)*
X
O WVKTT/ WKTlogg(1 log(T)
Algorithm 1 (This paper)
/
X
i.i.d.
O KT log(T))
Dogan et al. (2023a)
O ( (K)T vlog
Algorithm 6 (This paper)
O log (T)VKT) o (K log (T))
Algorithm 5 (This paper)
/
C-IPA Scheid et al. (2024b)d
X
X
OddVTlogs T) (d T log (T)
linear
Algorithm 7 (This paper)
8 We use X to indicate that the agent behavior is defined by true means. b For fair comparison, we use the same regret metric to compare all regret bounds. We refer readers to Appendix A for details. All our algorithms can work in the oracle-agent setup without modification and maintain the same regret bounds. We assume large I' to drop lower order terms.
We here present the worst-case bound of IPA, but also enjoys gap-dependent bound the oracle-agent setup. Contextual IPA (C-IPA) works for time-varying arm sets and thus also works in our fixed arm linear reward setting.
ically studied in moral hazard setting (Abreu et al., 1990: Radner, 1981; Rogerson, 1985; Sannikov, 2013; Wu et al., 2024) where the agents' actions are invisible to the principal, and adverse selection setting (Dogan et al., 2023a;b; Esö & Szentes, 2017; Fiez et al., 201 Sa;b; Gottlieb & Moreira, 2022; Halac et al., 2016; Ratliff& & Fiez, 2020; Scheid et al., 2024b), in which the principal does not known the agent types/preferences. While theoretical results are well estab- lished in these models, they typically assume that the agent has a full knowledge of the underlying parameters, and the reward functions remain fixed for both principal and agent.
A recent work by Scheid et al. (2024a) studies the principal- agent interactions under the assumption that for any time period and any principal's algorithm offering constant in- centives during this period, the agent's learning algorithm always preserves the no-regret property. While this en- ables regret bound of O(T%) if the agent adopt some al algorithms with Vi-type regret, this framework excludes simple yet realistic agent behaviors, such as self-interested learning agents with or without arbitrary exploration (see Appendix B for details). Moreover, their approach involves binary search per arm, which impractical in linear reward settings due to its linear dependence on the number of arms. In this paper, we address these questions by focusing on these simple yet realistic learning behaviors.
Recently, Lin & Chen (2025) considers a no-regret learning agent problem, but assume that the principal has full knowl- edge of its utility function. Fiez et al. (201 (a;b) consider incentive design as a bandit problem in a dynamic envi- ronment where the users preferences may change in time according to Markov process thereby resulting in dynamic, stochastic rewards that are correlated over time from the per- spective of the principal. Different from our approach, this work employs an epoch-based algorithm to take advantage of the mixing of the Markov process. Dogan et al. (2023b); Scheid et al. (2024b); Wu et al. (2024) consider reward un- certainty on the principal's side, though they still rely on the assumption of an oracle-agent who always selects the true maximizer. Dogan et al. (2023a) took a step further by in- corporating small degree of uncertainty on the agent's 's side, yet the agent still acts as true maximizer with increasingly high probability. In contrast, we study the scenario where both the agent and principal are always faced with uncer- tainty and the agent can only make decisions based on her empirical estimations and incentives. This problem raises new challenges and requires novel approaches to solve.
Let Vol(.) be the standard volume in I2 and let ||ق||| be fn-mo of vector z. For a positive definite matrix A E ddd the weighted 2-norm of vector x E Rd is given by ||~||| = Vx Az. For matrices A, B, we use A > B (A = B) to indicate that A B is positive (semi-)definll For two sets A, B, we use A A- B to indicate the exclusion. We use ((.) to suppress (poly) terms.
Notations.
2. Preliminaries
We consider a repeated principal-agent game over a finite horizon T, where the agent given an arm set A with |A| K, and A is also known to the principal. At each round E [T], the principal first proposes an incentive (t) = (t) (t)))) E 20- Then, the agent ob- serves incentive (t) and plays an arm A, E A according to a certain strategy. After playing arm A,, the agent observes reward R., (1) while the principal observes only the arm A,
3

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
played by the agent and herself reward XA. (1). The utility of the principal round is given by Xx, (1) nA. (t)- Throughout the interaction, the agent updates the empirical means {Aa (t) aaEA whenever playing an arm. In this paper, we focus on the following two learning behaviors.
be chosen arbitrarily in the range of [o. 11-
Linear reward setting. We assume A S B(0, 1) where ( 1) {a E R ||æ||| I 1}. and without loss of generality, A spans R The reward observed by the agent is (t) = (8" AA) + (t), and the reward on the principal side is XA, (t) - (v",, At) + (t) where s* u*= E B 1) are unknown to agent and principal, and 17 (t) and (t) are assumed to be conditionally 1 I-subgaussian. Assume that at each round t, the agent uses the ordinary least square to estimate 8 = (Ei A,AJ)) ''' RA, (s) for t. 2 2 where for any matrix M, MM is Moore- Penrose inverse. Moreover, $1 can be arbitrarily selected from (0,, 1). Then, The (L) (Fe; a) is the empirical mean of arm a at round t.
Self-interested learning agent: At each round 6, the agent selects an arm A, that maximizes the empirical mean plus an incentive proposed by the principal:
At E argmax (1) + (a)),,
aEA
where ties are broken arbitrarily. Similar to Dogan et al. (2023b); Scheid et al. (2024b), we assume the principal knows the agent's selection strategy in Eq. (1), but has knowledge of the empirical means, (Pa(t)),,a
Optimal incentive and regret. For any arbitrary e > 0, the principal ensures to incentivize the agent play arm by proposing incentive x²(() arm as:
This behavior generalizes the above by allowing the agent to play arms other than the empirical maximizer. Formally:
Exploratory learning agent:
T (t)
max (t) (t((t +, BEA
Definition 2.1. Let the probability that agent explores at round / be Pt P (A, $ argmax (!) + na (4))). There exists absolute constant co 2 0 such that Pt S co log/))))((2)) at any time step & E [T, T" where 7 2 is minimum value satisfying co / /log(2 (2) VT.
and Te (t) = 0 for all a' * a. This incentive ensures that TH (t) + (t) > (t) for all b * a, which implies that A. = a. The minimum incentive to force the agent to play a target arm a at round is
In fact, Pt in Definition 2.1 captures the probability that the agent deviates from playing the empirical empirical-maximizer. maxxmmzerr. This exploration behavior is not only analytically convenient but also motivated by behavioral and cognitive science where this type of model has been widely used to characterize how humans make sequential decisions under uncertainty (Barron & Frev, 2003; Daw et al., 2006; Gershman, 2018; Kalidindi & Bowman, 2007; Lee et al., 1).
n (t) == inf (t()) = max (is) - (t)..). e>0
(2)
The principal aims to minimize regret E [Ryy] where
T
RT
Σ tml
max (8. - -+)( (0.. =al(t))) (3)
aEA
Similar to Dogan et al. (2023a), we do not restrict how the agent explores arms and assume that the principal knows: (i) the agent either chooses an maxxmizee or arbi- trarily explores an arm; (ii) pr is upper bounded by a known function co /to-lolll2222 log(2t). We further assume that pe is as a function of history. In fact, our algorithm also works when Pt. only depends on t (e.g., agent adopts e-greedy algorithm).
Here, E[Rr]] measures the cumulative per-round gap be- tween the expected utility of an oracle with knowledge of the optimal incentives and that of our algorithm. In other words, we hope to find the best per-iterate incentive adapt- ing to agent's empirical means at each round, rather than the best fixed incentive in hindsight. For the exploratory learning agent, since A may be an arbitrary arm when agent explores, independent of the offered incentives, achieving maximal utility is infeasible in certain rounds. However, the total regret incurred during exploration is most O(VT) regardless of the benchmark. To maintain consistency, still compare against the best achievable utility, as in (Do- gan et al., 2023a). Moreover, if the principal is restricted to incentivize only a single arm, our regret aligns with that of Scheid et al. (2024b). We refer readers to Appendix A for a more detailed discussion on the implications of different regret definitions.
Then, we specify the reward models and how agent updates the empirical means for the i.i.d. and linear reward settings.
LLI.. reward setting. In this setting, we let A = [K] := (L...., K.. For each arm a E [K], the reward of each arm for the principal is drawn from (0, 1]-bounded distribu- tion D'P with mean 0., and the reward of each arm for the agent is drawn from another (0, -b-uundded distribution DA with mean Paa The agent is unaware of Pa. but keeps track of (t),), the number of plays of arm a before round and computes Pa (t) + RA, (A) where 220 the initial empirical mean for arm a² which is allowed to
max(1, (4)
all equal to zero, but our algorithms work for the general unknown [70] a case with only constant modification. We refer readers Appendix D.1 for more details.
For simplicity, we assume that the initial empirical means are
4

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Remark 2.2 (Generalization). Since the principal is agnos- tic to the agent's empirical means, by assuming that the agent always receives the constant reward equal to the true mean and the initial value is Pa Ha for every E A, one can see that Eq. (1) generalizes the agent model of (Scheid 2 et al., 2024b), and Definition 2.1 generalizes the agent's behavior of Dogan al. (2023a).
Algorithm Proposed algorithm for i.i.d. reward Input: confidence 5 E (0, 1). horizon T.
Initialize: A = [K]. B1 = 0, To = 1.
for m = 2.. do
Set T'm as
Tm = max {22m log( (4TTKKK |Am log T}. (4)
for E Bn do
Stabilize estimators for bad arms
Remark 2.3 (Lower bound). As our setting subsumes the oracle-agent setting as special case when Ra = 2 Ha. the lower bound for the oracle-agent problem serves as lower bound for problem. This implies that it remains to lower-bound (0. + ) (e=, MA.)]. Further, even if the principal has access to optimal incentives, the principle still needs to solve a stochastic 7 bandits problem with mean 0g + Ma. Thus, the lower bound of stochastic MAB (e.g.. Lattimore & Szepesvári (2020)) E[Ry] 22 KT) also serves as lower bound for our i..dd reward problem and the lower bound of stochastic
Propose incentives > 1 + 1/T"" for Zm rounds where Zm is given in Eq. (7).
5 for Am do
Invoke Algorithm 3 with input (a,T) to get bm.e- Search hear-optima incentive
Set bm,a based on Eq. (6).
Propose incentives T (a; bm.a) for Tm rounds.
for E Am do
Online Elimination
Let & be the round current, and (1))a)) empirical means of all arms round t.
linear bandits E[AT] ??( (((vdT) serves as a lower bound
Propose incentives T()) with Ta(t) = 1 (t) +
for our linear reward problem setting (Dani et al., 2008).
} 222m TT(()) 1 (s),), vb E Am - {a}, and (;(t) = 0. Vi B.m. If A, * a, then update An+1 = Am - {a} and
3. Self-Interested Learning Agent & IID Rewards
12
Bm+1 = Bm U {a}.
In this section, we propose Algorithm 13 for the self- interested learning agent and i.i.d. reward case, which achieves O( logg KT)) regret bound. The omitted proof can be found in Appendix D.
Incentivize which arm? Now, we figure out which arm should be incentivized. To minimize regret, we aim to incen- tivize agent to play arm with small regret. From Eq. (3), the regret of a single round t is max.e.4 {0a (t) (AA, TA (1)) Assume that we have accurate estimates of optimal incentives (T.,, (t) = T (t)). and the regret at round is max {0. + (a) - -0A, + aa As the agent observes more samples, the empirical mean (t()) will be closer to the true mean Mla- Therefore, the regret large round will be roughly maX.6. {0. + Ne} (fA, + MA.) Hence, our algorithm will incentivize an arm that maximizes the joint true means of the principal and the agent.
3.1. Novel Elimination Framework
We build our algorithm upon a new phased chased-elimination scheme, which consists of three components, each with an underscore in Algorithm 1. The algorithm proceeds in phases indexed by m, and the phase length increases ex- ponentially. In each phase m, the algorithm maintains active good arm set Am and bad arm set Bm [K] Am
One distinction between our elimination framework and that of Even-Dar et al. (2006) is that in each phase, the algorithm plays all bad arms (if any) for a moderate number of times. This stabilizes their estimators while incurring only moderate regret. Once the estimators are stable, the algorithm searches for optimal incentives, with the error decreasing inversely with the phase length. As the algorithm proceeds in phases, estimation accuracy improves, while the number of searches is only logarithmic. The algorithm then uses accurately estimated incentives to entice the agent to uniformly explore the active arms. Finally, the algorithm identifies had-bchaved arms and steps into the next phase.
Before explaining each component, let (a;a)) E 20 be a single-arm incentive, Va E [K], Ve Ryo:
fc, c if = a, 0, otherwise.
[ (a;())
(5)
3.2. Efficient Incentive Search
We first describe our key subroutine (Algorithm 3 deferred to Appendix D.2) for the near-optimal incentive search. The search algorithm aims to provide an estimation for the target arm a. The following lemma characterizes the estimation error and efficiency. Let bm,a be the estimated incentive for arm in phase m, outputted by Algorithm
'For all algorithms proposed this paper, the principal tracks and updates (t), 0. (t))et] whenever an arm is played. We omit these updates for the ease of presentation.
5

---

Principal-Agent Bandit Games with Self-Intereste and Exploratory Learning Agents
Lemma 3.1. For each phase m, if Algorithm 3 ends the search for arm a at round t in phase m, then
in subsequent rounds when empirical means are updated. To this end, we enlarge im.a to bm, given
bm.a- (l)
4 [ogg T1 + min N.())
2
bm_a min { bmm + 4Cm + Z
{1+
1 T
(6)
(t)
Moreover, Algorithm 3 lasts at most 2 [log22 T rounds.
where C.. 1og(4K(7/) The idea behind this enlarge- 2T... ment is to leverage the fact that the rewards are i.i.d. with Hoeffding's s inequality which provides an interval for the possible fluctuation of empirical means. Such an interval shrinks as more observations are collected. We use 4Cm as upper bound, accounting for all future fluctuations. Let m. be set of all rounds when Algorithm explores active arm at line 8 in phase m. Then, we have the following.
The estimation error suffers (miinge[]] (1)) because the search algorithm compares the empirical means be- tween the target arm and the agent's best empirical arm argmnabb((]] (1), which could be arbitrarily suboptimal on the principal's Iss side. To control this error, we lower- bound it by min:e[K] (4). Algorithm 3 inherits a basic binary search structure (line 4-line 11), while incorporating an asymmetric check for better accuracy.
Lemma 3.2. With probability at least 1 - 8, for each phase m and arm a E Am, agent plays arm a for all t E T
Asymmetric check. The goal of this design is ensure the output estimation a is strictly larger than and close to the optimal incentive for arm a. The algorithm refines the search range [y, (t). (t) by testing whether the of- fered incentive entice the agent to play the target arm. In oracle-agent setup, running standard binary search (log T) times ensures n (1) E ly (1), [a) with an error at most y. (t) = 2). However, in our setup where (a(t) y
3.3. Necessity of Playing Bad Arms
Since the algorithm only searches for incentives for active arms and Lemma 3.2 ensures each active arm is played for Tm times in phase m, .o (t) will be sufficiently small. Thus, it remains to control (minge(k) (N(())- for the esti- mation error in Lemma 3.1. In fact, this can be achieved by playing bad arms for Zn times for each phase where
the agent keeps update empirical means, simply running binary search does not ensure (t) & ly, (t). T. (t)]. Con- sider a round & where binary search is used for target arm a, and arm z achieves (t) maxbe[K] (t) and (t(t) - Pr, (t) O). If arm is played at round gen- erating reward 1, the agent updates Pe (t + 1), potentially causing (t (ft++1 1)- (t+ - P.a (t 1) > Te (t), which pushes T (1++ 1) outside the search range. Since the search lasts Olog 7' rounds, (t) increases at most (log T) times. To ensure the estimated incentive is strictly larger than the optimal when search ends, we enlarge Tg 2
Zm = VlAml (max(1, [Bml)) Tm--1,
where Tm is defined in Eq. (4).
If one follows the classical phased-elimination framework (Even-Dar et al., 2006), then min (t(t) could be ex- ponentially smaller than Tm because the arm that realizes the minimum might have been permanently eliminated in an early phase. As result, this term may cause linear regret in their framework. In our algorithm, playing all bad arms Zm times ensures the regret on cumulative estimation errors between bm,a and nt (t) is bounded by Ö(VT).
(t) ac- in count for possible increases, which makes minsej]] NT(3)
T N:(1). As result, an extra Lemma 3.1 becomes minseli] logarithmic multiplication appears in the regret bound.
3.4. Online Elimination
To address the above issue, we introduce an asymmetric check procedure in binary search. The algorithm tracks recorddng the latest incentive that successfully en- ticed agent to play the target arm. When agent does not play the target arm, the algorithm immediately re-offers y yupper, If yuppe: also fails, the search terminates, indicating that the optimal incentive exceeds the search range. This design quickly detects the out-of-range issue, reducing the error to min,eikj (.( which saves a logarithmic factor. Since the check step is triggered only when the incentive fails, we thus call it asymmetric check.
Recall that bad arm is with small value of 0, Ma. and thus the algorithm aims to find arms with small value of the corre- sponding estimate 0. + (t).).. Since the empirical means maintained by the agent are unknown, the algorithm cannot eliminate arms in an offline fashion by simply comparing estimators. To this end, the algorithm adopts an online ap- proach to compare, by proposing proper incentives. Specifi- cally, the algorithm tests each active arm a E Am by adding its own estimators (t))auu)) (line 11) into the incentive. By doing this, the algorithm can compare their joint estima- tion 0, (t) (t)+Aa (t) by observing the played arm. Note that the incentive increased by one for all active arms so that the comparisons are limited within active arms. If A o a, then 3b E Am such that Pa (t) + (t) S (t) + T (T) which
Enlarged incentive. Lemma 3.1 ensures bm,a is close to (t) when search ends at round t. However, there is no guarantee that b can incentivize the agent to play arm
6

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
leads (1) 0,)) (1) (()) 2 3 2- Therefore, the algorithm is able realize the elimination procedure in an online manner.
Algorithm 2 Informal Version of Algorithm 5 for phase m
Play bad arms ((T)-))) times where Tm is given in Eq. (8). m-1)
Repeat Algorithm 3 (log I') times for each a E Am to get (bm )i,a which is sorted in ascending order. Enlarge Om,a bm, a + O
Remark 3.3 (Offline elimination). Our algorithm can also do the elimination in an offline manner, and the modified algorithm maintains the same regret bound. We refer readers to Appendix D.8 for more details.
for each i,
for Am do
for i = L.....
..... (log T) do
Incentive testing
(i) Set counter Cm,a = and Ymm. O.
3.5. Main Result
repeat
The main result is given as follows.
Offer x (a; b mm.)) and update Y = Y + 1
Theorem 3.4. By choosing ō = T-1 for Algorithm 1, we have [[ = O (K log" T + / /KT KTTlog(KT) KT)).
(6] (i)
If agent does not play arm a, Cm.a = Cm.a + 1.
until (6) Cma exceeds threshold or Y-(i)
m,a = 2T
If Djs - (1) 2 Tm. then break loop i.
According to the (T) lower bound in Remark 2.3, our upper bound matches the lower bound up logarithmic factor. Moreover, if one reduces the learning agent to the oracle-agent, our worst-case bound matches that of Scheid et al. (2024b) as long as T 2 K. However, our algorithm cannot achieve a gap-dependent bound since it keeps playing bad arms. While Scheid et al. (2024b) show that a gap- dependent bound attainable in the wrgete problem, it remains open whether it is achievable in our setting,
for a E Am do Set L,,a = 0 and repeat incentive strategy in Algo- rithm for Ollog 7') times.
> Trustworthy online elimination
If agent plays target arm then Lm, = Lm, U {{} and Lm = -m, U {0} otherwise. Then, sort Dm, in ascending order.
if Medi annd = then
L Update Am+1 = Am - {a) and Bm+1 = B,n Uat.
4. Exploratory Learning Agent & IID Reward
In this section, we study the problem of an exploratory learn- ing agent in the i..dd reward setting, where the agent may arbitrarily select arms other than the empirical maximizer. This problem is initiated by Dogan et al. (2023a), but our setup generalizes theirs.
probability pa (potentially depending on history), repeating it logarithmic times ensures at least one success with high probability. We refer to the call of Algorithm 3 where the agent does not explore, as a "successfil call". Indeed, the incentive generated by the successful call is close to the optimal one only at that specific round. We further enlarge those incentives by O to force the agent to play the target arm unless exploration occurs.
4.1. Algorithm Description
At a high-level, Algorithm 5 (see Appendix 1) is a robust version of Algorithm I, ensuring the agent exploration does not disrupt the learning process. We maintain main building blocks in Algorithm 1 and introduce new adjustments to enhance the robustness to the agent's 's exploration behavior.
As the algorithm is unaware of the occurrence of explo- ration, a successful call cannot be directly identified by the algorithm, even if we know the existence. To address this, the algorithm sorts all estimated incentives (bm,.) J in ascending order and tests each of them iteratively. We refer to the incentive from a successful call as "successful incentive". Such a sorting ensures (i) the error of incentives before the successful incentive is bounded by the error of successful incentive (id) the iteration for the incentive test- ing does not exceed that of the successful incentive. It is obvious that (i) holds due to ascending order sorting, and then we will explain the underlying reason that (ii) holds. During the test, the algorithm tracks am the number of times that agent does not play target arm and y-( a, the total number of rounds in the i-th iteration. If cm.a exceeds a threshold, indicating excessive non-target plays, the al- gorithm believes 5 is inaccurate and tests the next one (1+1) Since a successful incentive guarantees the agent
Incentive testing. Recall from Algorithm 1 that incen- tivize the agent to play the target active arms, the algorithm needs to accurately estimate optimal incentives by calling Algorithm 3. However, obtaining accurate estimations in this setup becomes challenging because the agent occasion- ally ignores the incentive to explore an arbitrary arm. To circumvent this issue, we repeat the search for logarithmic times, which leads the following result.
Lemma 4.1. With probability at least 1 1- 8/4, Vm 2 2, among total 2 log(4 (4 log, T/8) calls, there is at least one call of Algorithm such that the agent makes no exploration.
This design leverages the probability amplification (see Lemma E.3): if random trial succeeds at round with
7

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
plays the target arm unless exploring (similar to that of Al- gorithm 1), and the exploration probability is bounded, we can set a threshold (smaller than Tm)) ensuring cmla never exceeds when testing successful incentive. Consequently, the repeat-loop breaks only when YIA = 27 If j is the iteration that corresponds to the successful incentive, then Ejs, (Y caia) 2 Tm. which implies (tt) holds and the algorithm can acquire at least Tm samples per target arm a (refer to Lemma E.11), where
certainty. For a fair comparison, we adopt [[] (see Ap- pendix A) consistent with (Dogan al., 2023a).
Theorem 4.3. By choosing ō = 1/T, Algorithm 6 ensures that B[ =
KT + K" log" logooKK (KT)).
Theorem 4.3 gives a Ó (VT) regret bound, which matches the lower bound up to some logarithmic factors. More im- portantly, it significantly improves upon ((T11/12) regret bound in (Dogan al., 2023a).
Tmm = =2c2 2mm K (6
5. Selfe- Learning Agent & Linear Reward
and 16KT log, T log(4 log, T/8)6-1.
Trustworthy online climination. The online and offline elimination approaches previously shown in Section 3.4 cannot be directly applied. For the online elimination, the agent's 's exploration could cause the algorithm to incorrectly eliminate good arms and retain bad ones. The offline elim- ination (recall Algorithm 4) requires exact knowledge of successful incentive, which is hard be identified. To tackle this issue, we propose trustworthy online elimination. For each active arm a, the algorithm offers the same incentive logarithmically many times, observes the agent's 's action Ar, and updates the set Lm.a- = Lm,a U {1} if A, = a and Cm,a- = Lm.a U {0}. otherwise. After gathering enough data, the algorithm sorts Lm.a and uses the median of L.,a to determine whether to eliminate arm a. This median- based approach ensures that the climination process is robust against the agent's exploration, with high probability.
In this section, we propose an algorithm (Algorithm 7) for the linear reward setting with the self-interested learning agent. The omitted details in this section can be found in Appendix G. Algorithm 7 is built upon the framework of Algorithm 1. However, to bypass the linear dependence on K, the framework needs to be carefully tailored for the linear reward structure. We will show how to modify each component of Algorithm for the linear reward model.
Recall from Algorithm I that all arms will played for fixed number of times in each phase. However, this results in a linear dependence on K. To address this, we use G-optimal design (Kiefer & Wolfowitz, 1960) a standard technique in the linear bandit literature (Lattimore et al., 2020). is noteworthy that our algorithm computes design not only for active arms, but also for bad arms. The reason is similar to that of i.idd. reward setting, i.e. to acquire accurate estimations of optimal incentives, one needs to stabilize the estimators of bad arms.
4.2. Main Result
We present the regret bound of Algorithm 5 as follows.
Moreover, the algorithm cannot directly apply the elimina- tion approach used in Algorithm I to check each arm. This is because the online elimination procedure requires the principal to test each active arm once, but the total number of test scales with K. Fortunately, our search algorithm (will be clear in the following subsection) can accurately predict the underlying parameter s", which allows to have good estimations of (Fa(t)) Consequently, the algo- rithm conducts the elimination in an offline manner, similar to classical elimination methods.
Theorem 4.2. Suppose T (.K)) Choosing å = 1/T for Algorithu 5 ensures E[ = O (Kllog" T) ///1
Recall that Algorithm 1 enlarges the bm.a to om.a ((I/VT) to ensure the algorithm always successfully in- centivizes the agent to play the target active arm. However, due the exploration behavior, we need to enlarge bm,a further by 0/)- to achieve the goal. This modifica- tion requires the algorithm plays each bad arm for ((T)/)) times, compared to O(TT) plays in Algorithm 1, which incurs (T7%) regret bound. Closing the gap between the upper and lower bounds is left for the future work.
a by roughly
5.1. Robust High Dimensional Search
In the linear reward setting, adopting a similar approach in Algorithm I to search for the incentive for each active arm is undesirable, as incurs a linear dependence on K. Therefore, instead search a space in each phase in which s* resides and all points in this space are close to s" Specifically, let Cm be an arbitrary point in this space. It follows that (cm: a) = (s", a). Furthermore, when the agent collects more samples, her own estimates š, also gets closer to the true parameter st, which implies that
4.3. Refinement for Exploratory Oracle-Agent
When we reduce the learning behavior in Definition 2.1 to the exploratory oracle-agent considered by (Dogan et al., 2023a), Algorithm 6 (see Appendix F) achieves a VT-type regret bound. As the agent selects the true maximizer when not exploring in the reduced setting, we simplify certain algorithmic designs used to handle the agent's 's learning un-
8

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
(Fe, a) R as*,a) 2 (Cm,a) for all arms a E A. Hence, the optimal incentive (1) m (Ft, b a) can be well- approximated by A (cm: b - a). This idea previously appears in (Scheid et al., 2024b) where the feasible space is refined based on s" in the oracle-agent setup, but in our learning agent setting, their approach would fail to learn s". This is because the space is refined based on the estimate &
the threshold make the cutting more conservative than before. As result, the algorithm can guarantee 8* E SS for all t. The analysis is deferred to Appendix G.4.
5.2. Main Result
We present the regret bound in the following theorem.
in the learning agent setting, and thus the fluctuation of 8 could mislead the algorithm wrongly exclude s". To this end, we adjust Multiscale Steiner Potential (MSP) (Liu et al., 2021) to cut the space conservatively, accounting for the uncertainty caused by the learning agent. Before showing our algorithm, we first define the width for set S C IRd and vector u E R2d as follows:
Theorem 5.1. Suppose T = (dd). By choosing d = TT- in Algorithm we have that [[[ O log (KT)).
Theorem 5.1 gives the first sublinear regret bound for linear rewards in the learning agent setting. One may notice that for some T, we have E[Rr] = (dd/sT44s Unfortunately, the regret bound does not match the lower bound given in Remark 2.3, so there is room for further improvement. Moreover, compared this bound with other T ttye bound in linear bandits problem (typically 2/ our bound suffers an extra multiplicative dependence on d. This extra d serves as a cost for the conservative cut. It remains unclear whether this extra d can be removed by more careful analysis or additional adjustment for the search algorithm. We left this problem for future work.
width(S,w) = max (u, x - v) a.ESS
(9)
Algorithm 8 keeps track of a sequence of confidence sets { iteratively. The algorithm initializes S = B(0, 1), ensuring that the unknown parameter 8* E S1. At each iteration 6, Algorithm 8 first picks at - af that maximizes wi width((e, a. - a?) where at, of E A. and sets direction D = (a! - at) ||a - ofl - The idea behind the choices of ot, aj is to enable the algorithm to explore a direction with the maximum uncertainty.
6. Conclusion & Future Work
In this paper, we study principal-agent bandit games with self-interested learning and exploratory agents. We first con- sider the learning agent who greedily chooses the empirical- maximizer and propose Algorithm 1, which achieves a re- gret bound matching the lower bound up to logarithmic factors. Then, we extend Algorithm I to more general set- ting in which the agent is allowed explore an arm different from the empirical maximizer with a small probability, and introduce Algorithm 5 to achieve O(T%) regret bounds. Building on this, we reduce our setting to that of Dogan et al. (2023a) and propose Algorithm 6 with ((VT)) regret, which significantly improves upon (TT))))) (Dogan et al., 2023a). Finally, we present Algorithm 7 for the linear re- ward setting and propose an algorithm with (d4/3122/3) regret bound.
Then, it finds an integer i such that wi ai,th(S,, E 12---1,--), and the length of the interval reflects the uncertainty of St along the direction 24. When the if-
condition (line 4) is satisfied, the algorithm will return an arbitrary point in S, because the estimation error for the optimal incentive is up to (c)) If the condition is not sat- isfied, then the algorithm finds a y/ E which reduces Vol(S. + 2; (0, 1)) (known as Steiner potential) by half, where the sum is the Minkowski sum
S + 2, ((0, 1) = {s + z, b: 8 E S B(0 1)}-
Such a cut decreases the volume of S. + 2, B(, 1) by constant multiplicative factor, and thus the total number of iterations is at most (dlog? (de) by Lemma G.5.
Since (Bt, a) S || ||l|| S d for all L E [T], adding d + for aT (t), Toz(t) ensures that the agent plays only either at or of. Here, we use A, = af as an example (the other one is analogous) to show why we update S4+1 with e shift. From Eq. (1), the condition A,- = ot implies (Be, +
Our results leave several intriguing questions open for fur- ther investigation. First, closing the gap between the upper and lower regret bounds in the linear setting, even without agent exploration, remains open. Additionally, it remains unclear whether the ( regret bound in Theorem 4.2 could be further improved to O( OVVT). Finally, extending our results handle more general exploration behaviors (e.g.. Pt ((t=a) for any a E (0, 1)) is promising direction.
To (1) S (Z., + (1). Rearranging it and dividing |a! - afll on both sides gives (Ge, 21) < ||a: -odl-2?ll]- o2l1 yt. An natural idea is to update S4+1 = {u E S. xt) S
||t| ---d of y/ since it ensures 8* E S:+1 in the oracle- agent setting. However, the estimate 3, varies across time in our learning agent setting, and thus if the algorithm cuts the space based on $, it is entirely possible that S.41 = @ which invalidates the algorithm. To avoid this issue, we enlarge
A Acknovledeements
This work was supported in part by an ONR YIP Award (#N00014-20-11257) and an NSF CAREER Award (#1844729).
9

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Impact Statement
Gershman, S. Deconstructing the human algorithms for
exploration. Cognition, 173:34 42, 2018.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Gottlieb, D. and Moreira, Simple contracts with adverse selection and moral hazard. Theoretical Economics, 17 (3):1357-1401, 2022.
References
Grossman, S. J. and Hart, O. An analysis of the principal-agent problem. In Foundations of Insurance Economics: Readings in Economics and Finance, pp. 802-340. Springer, 1992.
Abreu, D., Pearce, D., and Stacchetti, E. Toward theory of discounted repeated games with imperfect monitoring. Econometrica: Journal of the Econometric Society, pp. 1041-1063, 1990.
Halac, M., Kartik, N., and Liu, Q. Optimal contracts for experimentation. The Review of Economic Studies, 83(3): 1040-1091, 2016.
Barron, G. and Frev, Small feedback-based decisions and their limited correspondence to description-base decisions. Journal of behavioral decision making, 16(3):
Ho, C.-J, Slivkins, A., and Vaughan, J. W. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal- -agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pp. 359-376, 2014.
215-233, 2003.
Ben-Porat, O., Mansour, Y., Moshkovitz, M., and Taitler, B. Principal-agent reward shaping in mdps. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9502-9510, 2024.
Ivanov, D., Dütting, P., Talgam-Colee I., Wang, T., and Parkes, D. C. Principal-agent reinforcement learning: Orchestrating ai agents with contracts. arXiv preprint arXiv:2407.180744 2024.
Bolton, P. and Dewatripont, M. Contract theory. MIT press, 2004.
Dani, V., Hayes, P., and Kakade, M. Stochastic linear optimization under bandit feedback. In Conference on Learning Thheory 2008.
Kalidindi, and Bowman, H. Using c-greedy reinforce- ment learning methods further understand ventrome- dial prefrontal patients' deficits the iowa gambling task. Neural Networks, 2066):67--689, 2007.
Daw, N. D., O'doherty, J. P.. Dayan, P., Seymour, B., and Dolan, R. J. Cortical substrates for exploratory decisions in humans. Nature, 441(7095):87--87) 2006.
Kiefer, J. and Wolfowitz, J. The equivalence of ex- tremum problems. Canadian Journal of Mathematics, 12: 363-366, 1960.
Dogan, I., Shen, Z.-J. M., and Aswani, A. Estimating and incentivizing imperfect-knowledd agents with hidden rewards. arXiv preprint arXiv:2308.067 06717, 2023a.
Laffont, J.-J. and Martimort, D. The theory of incentives: the principal-agent model. In The theory of incentives. Princeton university press, 2009.
Dogan, I., Shen, Z.J.. M., and Aswani, peated principal-agent games with unobserved agent re- wards and perfect-knowledde agents. arXiv preprint arXiv:2304.07407, 2023b.
Re-
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Esö, P. and Szentes, B. Dynamic contracting: An irrelevance theorem. Theoretical Economics, 12(1):109-139, 2017.
Lattimore, T., Crammer, K., and Szepesvári, C. Linear multi- resource allocation with semi-bandit feedback. Advances in Neural Informaion Processing Systems, 28, 2015.
Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, S. Action climination and stopping conditions for the aumti-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
Lattimore, T., Szepesvari, C., and Weisz, G. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Ma- chine Learning. 2020.
Fiez, T., Sekar, S., and Ratliff, I. J. Multi-armed bandits for correlated markovian environments with smoothed re- ward feedback. arXiv preprint arXiv: 1803 04000, 201 8a.
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), 2018b.
Lee, M. D., Zhang, S., Munro, M., and Steyvers, M. Psy- chological models of human and optimal performance in bandit problems. Cognitive systems research, 12(2): 164-174, 2011.
10

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandit approach to personalized news article recommendation. In International Conference on World Wide Web, 2010.
Zhu, B., Bates, S., Yang, Z.,, Wang, Y., Jiao, J., and Jordan, M. I. The sample complexity of online contract design. arXiv preprint 2tti::22221.00733. 2022.
Zhu, B., Karimireddy, S. P., Jiao, J., and Jordan, M. I.
Lin, T. and Chen, Y. Generalized principal-agent problem with a learning agent. Proceedings of the International Conference on Learning Representation (ICLR), 2025.
Online learning in creator economy. arXiv preprint arXiv: /1381, 2023.
Liu, A., Leme, R. P., and Schneider, J. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM- SIAM Symposium Discrete Algorithms (SODA), pp. 1079- SIAM, 2021.
Pogodin, R. and Lattimore, T. On first-order bounds, vari- ance and gap-dependent bounds for adversarial bandits. In Proceedings of The 35th Uncertainty in Artificial Intel- ligence Conference. PMLR, 2020.
Radner, R. Monitoring cooperative agreements in a repeated principal-agent relationship. Econometrica: Journal of the Econometric Society, pp. 1127-1148, 1981.
Ratliff, L. J. and Fiez, T. Adaptive incentive design. IEEE Transactions on Automatic Control, 66(8):3871-3878, 2020.
Rogerson, W. P. Repeated moral hazard. Econometrica:
Journal of the Econometric Society, pp. 69-76, 1985.
Sannikov, Y. Contracts: the theory of dynamic principal- agent relationships and the continuous-timg approach. In Advances in economics and econometrics, 10th world congress of the Econometric Society, volume 1, pp. 89- 124, 2013.
Scheid, A., Capitaine, A., Boursier, E., Moulines, E., Jordan, I., and Durmus, A. Learning to mitigate externali- ties: the coase theorem with hindsight rationality. arXiv preprint arXiv:2406. 19824, 2024a.
Scheid, A., Tiapkin, D., Boursier, E., Capitaine, A., Mhamdi, E. M. E., Moulines, E., Jordan, M. I., and Dur- mus, A. Incentivized learning in principal-agent bandit games. ICML, 2024b.
Todd, M. J. Minimum-volume ellipsoids: Theory and algo- rithms. SIAM, 2016.
Villar, S. S., Bowden, J., and Wason, J. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Wu, J., Chen, S., Wang, M., Wang, H., and Xu, H. Contrac- tual reinforcement learning: Pulling arms with invisible hands. arXiv preprint M.Xx:2407.004555 2024.

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
A. Comparisons of Regret Notions and Additional Notations
As the optimal incentive is time-varyee aine-narying in our setting, Rr compares the cumulative utility difference between the per-round optimal arm and the arm selected by the algorithm.
Ry
Σ
max (0. -=]((t)) (0,. (at(t)))
(10)
aEA
Notice that one reduces our setting to the oracle-ugent setting by letting Pa Ma and Rt) = p4 for all then E[AT] Bl where
(maxx μbb (a) [ (0A, -(0,
R
Roracle
Σ
max
0a
(11)
aeA
beA
In (Scheid et al., 2024b), the principal only proposes one-hot incentives i.e., only one coordinate of xtt) is positive each round, and they define regret
[na) (0,, IIA 23 FA, (A. (1)) (
E
Σ
max aEA
0a 1mmaxxxpp bEA
(max pbb
where E A is an arm that the principal gives positive incentive at round t. If we also restrict the principal to always provide one-hot incentives, [[[Rgsacie] is exactly the same as that of Scheid et al. (2024b). However, the principal needs to provide incentives for multiple arms, then their notion will ill-defined.
Dogan et (2023a) uses the regret [[ evaluate the algorithm performance where
T
(0x- Σ (1) ) aEA
RT
max (0, + 1bb max u12 bE[K]
(12)
ZE[K]
One can observe that RT > Rgracle, Therefore, the regret bound under [[[ in (Dogan et al., 2023a) can be directly translated to the regret bound measured by E[Rgracle]. In fact, changing the regret measure from Roracle to Ry only slightly impacts the low-order terms in the regret bounds of some of our algorithms because our algorithms use one-hot incentives in most of the rounds. For fair comparison, all results in Table are compared via [[Rgracle).
Notice that all our algorithms can get the same regret bound under E Rgracte] and E[Rr] without any modification. This because algorithm reward R. (t) = Na for all i, a.
handle the unknown empirical means, and thus
assume the agent receives constant
Additional Notations. Based on the definition of (t) in Eq. (2), Ry can be rewritten as
T
-mx-(x (1) - (T.(1)) (0 TA, (0))
Rr
max aed
0.
DEA -DE
Oa; Mo (1) max (1) -O0A. TA)( BEA
(13)
where at is defined as:
(i.id. reward)
a E argmaax {0. + (t)} aeA
and (linear reward)
a E arggmax ((v",a) + (t))
aeA
We further define the gap A = 0nr + pa- (0. + pa) where
(ii.d. reward)
a' E argmaxx (0. + Ha} and (linear reward) aEA
a* argmax (v/ + +s"
aEA
12

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
B. Discussion on Universal No-Regret Preservation Assumption
We translate the assumption (Scheid et al., 2024a, H2) with our notations the following.
Assumption B.1. There exist C, <> 0, E [0, 1) such that for any 8, E [T] with + + T, any {TaJuE E R$ and any policy of principal that offers almost surely an incentive = T (āz, Tai) (see Eq. (5)) for any / E {s + 1,..., . +tt), the batched regret of the agent following policy II satisfies, with probability at least 1 --
Σ aEd Pe + lāā a} F (PA, IfAr = āi} -Ta)) S Ct".
Since Assumption B.I requires the no-regret property preservers for any time period from + to f, and also for any principal's policy, their model does not cover the self-intereste learning agent in our paper. Specifically, let us consider two-armed setup with = 0.1 and f42 = 0.9, and Bernoulli distributions with mean M1. respectively. As our model allows the initial values of empirical means are chosen arbitrarily, we assume them to be zero. Suppose that in the first round, the principal incentivizes the agent to play arm I and the agent receives reward 1, which occurs with a probability T 0.1. Then, we have (t) and (t) = O. Then, the principal always proposes incentive 7 (2. T 10) for all rounds I such that 2 < 1 S T. According the self-interested learning agent behavior A, E argmax (Ta + Ta (t)}, we have with probability 0.1 (i.e., the probability that agent gets reward 1 at the first round),
s+t
Σ 1=++1
max (Na + [(ār = =a- na.) (Mr, + I(Ai = ā1} Ta.) = =((() AEA
Then, we show that Assumption B.1 also does not cover the self-interested learning agent with exploration (refer to Definition 2.1.. The reason that in our model (also in (Dogan et al., 2023a)), we consider general exploration behavior of the agent, in the sense that we do not add any assumption how the agent explores aon-emppricallmmximizz However, Assumption B.I implicitly requires the algorithm to strategically explore the environment.
C. Discussion on Agent's Behavior in (Dogan et al., 2023a)
noteworthy that even if an agent's behavior characterized by the true means (i.e., expected rewards), this does not necessarily require the agent have the knowledge of those underlying parameters. For example, in Assumption 2 of Dogan et al. (2023a), the authors assume that if the agent does not explore, then the agent must choose true-maximizer (i.e., the maximizer of the expected reward plus incentive). Dogan et al. (2023a) show that the agent can adopt learning algorithm without the knowledge of expected rewards to simulate that behavior. However, this simulation requires a special coordination between the principal and the agent, in the sense that the agent and principal must adopt specific algorithms with specific parameters. In real-world applications, however, it is often infeasible for the principal or the agent to enforce the other party's s use of particular algorithms or parameters.
D. Omitted Proof for LLLD. Reward in Section 3
D.1. Discussion on Modifications for General Initial Empirical Means
To avoid clutter in our analysis, we assume for i.i.d. case that the initial empirical means [Ta)ae]k] are all zeros. For initial empirical means which are selected arbitrarily in [0, 1] and unknown to principal, our algorithms still work with two simple modifications. Note that these modifications work for Algorithm 1, Algorithm 4, Algorithm 5, and Algorithm 6. These two modifications rely on the fact that the mismatch of empirical mean of arm a at round t between assuming it to be zero and an arbitrary one, is at most N.(F). Such mismatch only causes issue for active arms since every bad arm played deterministically. Moreover, the number of plays of each active arm is proportional phase length, and thus (.( (2 2m) (if ( is in phase m). For the first modification, when the algorithm aims to incentive the agent to play active arm a at round t, one can enlarge the offered incentive by Nu(t). Such an enlargement accounts for all possible initial
1
values since the deviation of each arm a is bounded as (e)
Σ (.). As this change is small enough, it does not impact
the order of our regret bounds.
13

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Algorithm 3 Noisy binary search with asymmetric check
Input: target arm a, horizon T'
Initialize: Check False, ya pupper C1 C2 0. Let to be the current round, and we To (la) and L (ln) O.
for ! = lo, l0 + + 1...do do
Check = False then
Set Va mic (t) = v2(0) (4) and C1 = C1 +
2
Propose incentives (a; (aid))))))))))))))))))))))) and observe A..
if A. = then
if 1 2 [log2 7 then
L Return (t) + 7.
Set ypper / (t) Vt + 1 va (t) and yo (t+ 1) yo
10
else
Set Check = True, Na (L + 1) = Na (1) and ya (L + 1) = ya (1).
11
else
Propose incentives (a; ()Feer) and observe A.. if A then C2 = C2 + 1.
16
C2 = [log, T then
L Return y
17
18
Set Check = False.
19
Set Na (1 + 1) (1), and y, (1 + () = (t)...
else
Return yupper # + (a(t)
21
mingc(k] N.(A)*
The second change is in elimination period. We take online elimination period as an example. Let 3 > 0 be a absolute constant. The algorithm now proposes incentives (1) with (t) = 2 vb E An - {a). and n, (t) = 0, Vi E Bm. Notice that the newly added (subtracted) N.(e) (otty is used to account for possible mismatch. Since the elimination process only focuses active arms, this change may cause ((2-2m) inaccuracy in elimination. Then one adjust the constant to accommodate this change such that analysis again holds (can be equivalently seen enlarging the threshold from 3 2 2- to (32-") and consequently the order of regret bound retains the same. For offline elimination Algorithm 4, one can directly enlarge the threshold to accommodate possible mismatch.
N.try. (t)() = 2 (t) N.Try
D.2. Omitted Pseudocode of Algorithm 3
The omitted pseudo-code of our search algorithm can be found in Algorithm 3.
D.3. Notations
The following common notations that adopt in this section. Refer to Appendix for general notations.
Let T. be the set of rounds, excluding the elimination period that in phase
Let Tm.a {t Tm A, = a.} denote the set of rounds in Tm such that A, =
Let T be the set of rounds that Algorithm runs in line 8 for arm a in phase m. Notice that T excludes those rounds from Tm,a such that Algorithm 3 plays arm a.
Define event & as follows:
14

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
log(4TK/55 (a(()) 0a
log(4TK/0) 2Na(t)
8 = a(t,a) E [T] x [K] (t)(t) Mal S
(14)
(Na(t)
D.4. Proof of Theorem 3.4
The following analyzes conditions on E. In Lemma D.3 below we show that (EE) > 1 6. As the algorithm runs in phases, we bound the regret in each phase m. Since the elimination period will last at most K rounds in each phase, the number of phases is at most Ollog T), and the per-round regret is bounded by an absolute constant, we have
RT S O (K (Klgg T) + E Rm
where Rm, is defined follows:
Rm
Σ TETm
max {0, - =z(1)] - (0s, - -A.))) <E[K]
In which follows, we focus phase with 2 2 and Tm # Am log I since Rm O (K Io for either phase 1 or the phase m that satisfies Tm |Amm log T. One can show that
Rm =
Σ
max (0. mZ(()) - (0,. (TA(())) [E|K]
DETm
max {0a (t)) (0s. TA. (t)) [aE[K]
aEAmm TTTm
max {0u (t)) (OA. mA))
aE|K]
Bm TETm.
max {0. - [t)) - (0A. - ((A) +0 (VIAm. Bm Tmm
aE[K]
a..Am. TETm.
As Algorithm will last O(K log T) rounds and the elimination period will last at most rounds, and the per-round regret bounded by a absolute constant, we have that
Σ aE TETm.a
Σ
max (0. =(((t) (0A. TA((1))
[aE[K]
Σ
max (0.- - =x((1)} (0s, =Aa( + O (Klog
(E(K)
am LETE
mia
Σ
0az pox (B)
max (i)(t) (0. -((()) +O log bE(K]
am LETER
where the last step uses the definition of at and (t).
Then, for each Am and each t ThE we turn bound
0ur + (1)
max (1)( - (0. (1)
DE[K]
1og(4TK/0)
< 0o; + Mo;
max (t) - (0a (t))
2Na;(1)
bE[K]
log(4TK/5)
< 0og + +Ma
max (t) (0. (t))))
2T
bE[K]
15

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
log(4TK/6)
0ag Mo;
max (t( (0. -bm,a)
2T 2-m-1
be[k]
log(4TK/0)
< 0g Ma
max (b(()) (0. bm,
2T 21
be [K]
log (TT/))
log T
max Bmnl
0
a
mm-1
T mm
T Tm-1 |m
log( (TT/6)
[og T
mmax (1, Bmil
0 Da +
+
+
+ +V
(15)
1 (t)
T
Tm-1
T mmm
where the first inequality holds due to &, the second inequality uses Na; (1) 2 mm by Lemma D.13, the equality follows from the fact that for each m and Am. (t) bm.a for all t E T and the second-to-lase inequality uses Lemma D.9 upper-bound bn.a- maX к (t). and the last inequality holds because Tmm ((m-1) by Lemma D.2 and all active arms in phase played for Tm times by Lemma D.8.
By again Lemma D.8, each active arm in period Th will be played for Tm times. Hence, using |T = Tm and Tm = (Tm) for all m from Lemma D.2, we have
Σ aEAm
Σ
0n + (aa max mia(1) (0. -Ta(())
max aE(K)
bE(R]
TET mia
0
Σ aE
Σ
A +
Σ
log( (TT/))
1+ NA, + [mml
I'
+ log T
Tm max(1, Bml] |
(16)
T
Am
LETE m.m
LET
From Lemma 1212, if a suboptimal arm a is active in phase m, then m S ma where ma is the smallest phase such that Aa > mm This implies that
(1 (og(KT/8)
[og((T)
Ag
Va E Am with A. 0:
< 2 (ma-1) < 2- < 00
(17)
2
Tm
where the reader may recall that our focus on phase m 2 with Ti * Am log T. Hence, we can bound
log (T
ΣΣ
5.
Σ
T'm
LETE m, A
C cEAm EE mia
0
Σ
Σ
log (T(6)
1 N (t)
deAAm TET
log (KT()))))
so
1+ I+N N., (t)
MET
where the second incquality follows the same reason of Eq. (15). Then, we have
log(KT/0)
T
log (T/0)
ΣΣ M TT
I+N
+ (()
IAA a)
log(KT
[E[K]] VI + No
1 = 0)
= -Vlog(KT/8)
<E[K]
1+ E 1(A
16

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
0
Vlog(KT/5)
Σ
Σ T(A, d)
aE|K]
0 (OOVVTlog(KT))
where the first inequality uses Lemma D.I, and the last inequality uses the Cauchy-Schward inequality together with the fact EeE(K) Et=1 [AA, = a) T.
By the fact [Am I'm = (([Tm)) and the above results, we have
Rr 0 0
K Klog T v KT KTTlolgoT log(KT/ +
Σ v Bm |m [Tm
0o
K Klog T + KT Log(KT/T//)) (T//)) + Σ Bm [m
0o (VKTlog(KT)8))
where the last inequality first bounds |Bml < K and then uses Hölder's inequality with the fact that the number of phases is most Oloog T). This completes the proof.
D.5. Auxiliary Lemmas
In this subsection, we present several technical lemmas that are used the proof Theorem 3.4. Lemma D.1. (Pogodin & Lattimore, 2020, Lemma 4.8) Let { be a sequence with a, E [0, B] for all E [T]. Then, the following estimate holds:
Σ
Et
4
1
Jt + B.
Es=1 F3
Lemma D.2. For all m E it the case that T Tm+1 (Tm))
Proof. We consider the following cases for any phase m.
If =Tm+1 Aml log T, then the claim holds.
2. If If, = |Amm T and Tm++1 * |mm log T, then Tm I Tm+1 S 4Tm-
3. If Tm * |Amllog T and Tm+11 * |A log T, the claim again holds as Tm+1 = 4T
Notice that it is impossible for Tm+1 Am log T and T. * |Am log T. Thus, the proof is complete.
Lemma D.3. The estimate (P(E)= 2 - holds.
Proof. By Hoeffding's 's inequality and invoking union bound, one can obtain the desired claim.
Lemma D.4. For all t [T] and a E [K]. we have that
Pa + 1) - (t) Na)++1))
(18)
(a + (t) Na(t)
(19)
Proof. To show (18), we observe, for all a E [K], that we have
(t + 1) (t)()= (t) Palt) + (t]{A,, = a}
(t.(t)
Na(++1)
17

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
N.(t) io (t) + R., (t) = d}
(a((t)
(t) +
(t)t)[(A, a} - (t((t 2 Na(t) +1 2 Nalt Na(t+1)
1
1
Na(t)+ +1
+1)
On the other hand, show (19), observe that
No(t) Pa(t) + (t) = a} [ta(t)
+ - Pal()
Na(t+1 +1
No(t) Po (1) + Rao (t)[((A a}
S
(ta
Na(t)
(a(t)[(A a} (t())
$ Na(t)
(t
Hence, the claims hold.
D.6. Lemmas for Algorithm 3
In this subsection, we include technical lemmas for Algorithm 3.
Lemma D.5. If Algorithm runs for target arm o and breaks at line 21 at round t, then A a.
Proof. We prove the claim by contradiction. Suppose that A,- * a. The only possible situation for A F that Algorithm enters line 10-11, in which the algorithm sets Check True. Once Check True is set, must have A,-1 and Check Fa 1 se at round 1, and otherwise the algorithm will terminate. Notice that Algorithm cannot break at line 21 round whether not the algorithm plays A, This presents contradiction, and the proof is thus complete.
Lemma D.6 (Restatement of Lemma 3.1). For each phase m, if Algorithmm 3 ends the search for arm round in phase m, then
(0. 4 Moga T
2
Um,0 (1)
(20)
(t)
min,e[K] (:(1)
where (1) max (1) (t). MoreoverAlgoorttmm 3 lasts at most 2[og T7 rounds.
Proof. Let first prove the duration bound. It suffices to consider the worst case that the agent always plays non-target arm (i.e., A # a). Since single play for non-target arm during line 4-line 11 will cause check which takes one round and C2 is at most [log2 71. Therefore the total number of rounds in Algorithm 3 is 2 2[ogg T7. Then, we prove the estimation error by considering the following cases.
Case 1. and
Algorithm 3 breaks at line 8 and there exists E [to. t n N such that A, & a. In this case, we have A,
m' (1) 2 max (1) - (1).
kE[
Let [to, t - 1] N be the last round such that A, * Then, NA. (t) = (T) holds and
nA, (1) A (T) (T) Mu, (T) + RA (T) (T) (A.(T) - PTA.
(21)
NA, +1
NA. (7) +1
NA, (1)
By definition of T and A,, we also have
y_ (t) = ya (7) S max (T)(T) Pa( = (AA(T)) - Pa(
(22)
bE(k]
Then, one can show that
0 5 (tid(t) max (t) - (t)
[
18

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
ya (1) -1)--AA FA, (1) (1)
D.(t) + g.
(T) + 1
loga (T) (r)
+ (T) +
2
NA, (1)
Fa(t) - y/ (t)
[log (T)
2
NA, (t)
(T(
1
1
[log(()) (7)]
+
T Nt.(t)
(a(T)
1
1
loga (T)
T
min (.(I)
Na(T)
where the third inequality holds due to Eq. (21) and repeatedly arguing (1) S - 1) + N.(r-j S Ma - 2) +
(1
(a-1-1) + Na(e-2) -... from t to (refer to Eq. (19)), the fourth inequality follows from Eq. (22), and the fifth inequality holds by the standard binary search property, i.c. Fa (t) - Lg (t) exponentially shrinking and the number of shrinks is at least [log, T7.
Recall that if Algorithm 3 breaks at line 8, then bm.a (1) + 7. and Eq. (20) holds.
Case 2. Algorithm 3 breaks at line 8 and for all [to, t - 1] n N such that A, a. In this case, y (t) 0 and
Va (t) = 21-(loR,(T) [7,7]
0 S (t)
max (+s(t) - [uu(t)) S Va (t) S T (E(K]
Recall that if Algorithm 3 breaks at line 8, then binaa Va (t) + 1. and Eq. (20) holds.
Algorithm& breaks at line 17 and 3z E [4o, 1 IJ such that yopper gets updated at round z. Let E [lo, 1--1--1111 1J be the last round such that yu gets updated at this round. this case, we have A. = a and
Case 3.
2 apper val (s) Va (1+++1 Fa S y (1 1) T Vo
(23)
where the last inequality holds since there will be at least [log2 7 updates among fy. (T)}r until the break.
Let b be the arm that such that fin. - 1) = maxbe[K] its - 1) and A = 4 Then,
0 S Vo
upper
max (t) Ba (ta(t) bE(K]
S yo
mid (t- 1) + T
max (t) + (t( bE[K]
2
S Vo mid (1 1) +
pon. (1) + (1)
T
2
1
vol (t (t- 1) + T
ioo... (t (6-1) 1) +
+ Paatt 1)
No. (1)
Na 1)
2 $ T (o...()
+
+ Na -
where the first inequality follows from Eq. (23) together with y, (t - 1) s in - 1), the fourth inequality Eq. (18) and Eq. (19), and the last inequality holds since A,- b.-1.
If Algorithm 3 breaks at line 17, then bn,a- yopper + 2. and thus we have Eq. (20).
Case 4. Algorithm breaks at line 17 and Vz E |to, - 1] n N, yupper never gets updated. In this case, ypeer 1 and
y (t) 21-12111 21-1log, (T) E [1 2, J]. One can show
0 2 Ve
upper
max (ts(t) - Pa (t)
[E[K]
19

---

Principal-Agen Bandit Games with Self-Interested and Exploratory Learning Agents
2
m (1)
max Tis( (1) - D (1) [E[
1
max Pb(() - Pt be[k]
T
1
If Algorithm 3 breaks at line 17, then bm.a yo + T. and thus we have Eq. (20).
Case 5. Algorithm breaks at line 21. this case, we have 1 F a, A # a. By Lemma D.5, we further have Ar-2 a. Therefore, one can show
ya
uppes
max Pu((t) -aa(t) DE[K]
Va
upper
BA, (1) + Tall 1)
2
Va
uppe:
Tr, (t -2) (t +
-2) +
Na(t - 1)
Va
upper
max (b - 2) bE(K]
NA. - + Mall - 2) - (a(t-1)
2
(t - 2) 11)
where the second inequality uses Eq. (18) and Eq. (19), and the last inequality holds as Ar- If Algorithm 3 breaks at line 21, then bm. yapee + } No(i) + minje[j] N.()). By noticing Na - 1) 2 (t) and
NA, 2) 2 (1) 2 min:e[k] N:()), we have Eq. (20).
Once Eq. (20) has been proved for phase m, Lemma D.8 immediately gives that arm a will be played for the following Tm consecutive rounds. Therefore, the proof is complete.
Lemma D.7. Suppose that & occurs. For all 2 2 and all Aun if every active arm is played for Tm-1 times, then have A, for all t The
Proof. Let consider fixed phase 2 2 and arm Am E Am-1 and let tm,a be the round that Algorithm 3 ends the search for target arm in phase m. Recall that THE is the set of rounds that Algorithm I runs in line 8 for arm in phase m We strong induction on f in THE to prove the claim. For the base case (the first round in T
bm,a
T (mm, +
-bma- min
{1, x (tm,a + 1)}
Inna
min
1, n (m
minje(k] Nt(t)
mmx (1ax(1111 (Bml
> Im min
1, x. (tm.a) +
T 1m
1 1 To bmm
log(4KT/6)
max { 1, |Bml]
max 1, Bmmll
min
+ 1V
min n (1m,a) +
2Tm-1
Tm- Am
Tm Am
0,
where the first inequality holds since the one-up shifting is at most min,epx) (,) the second inequality holds because the active arm is played for at least Tm-1 by the assumption and each bad arm is played for at least T- 11m-l times (by
mmax[1]]6m)
Tm-1 11 2 Amm-1 Amml we have
T.n 144m max 1,I Tm-1)) and the last inequality holds due Lemma 3.1.
20

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Suppose that arm a gets played for all rounds / in The and then consider the round ( 4 1. To this end, first show
log log(4KT/0)
max Ps(t+ 1) max Po (tma 1) +1)5 2// 2fm-1
(24)
bE[K]
bE[K]
The induction hypothesis gives that if arm a gets played for all rounds S in Tm.a i.e., no bad arms will be played, then for all bad arms Bm. (1 1) pzl(mma 1). By Hoeffding" inequality, for all active a Am and W/T E Tm (Na(T) Tm-1 and
log log(4KT/6)
log (
VT T
(T( E
Ma
Ma +
(25)
2I 2I
21 21m-1
Therefore, to verify Eq. (24), we only need to consider the two maximums are achieved by two active arms, and their difference is at most 2
log (6K
27 27
Hence, one can show
max (t 1) maall (1((++1) bE[K]
1, max ios (f+ -oa +11 bE(K]
=bm,a-
min-
log(4KT/6)
2 Um.a min
1, max 7o(4m,a a + - -aalmma + 1) + 11 he
27
mmx 1,|mml)
log(4KT/0))
min
1, max (oltmaa) Poltmaa) bE(K]
+ 1V
Tm- 1mm
21 21m-1
max(1, L, 1Bm }
log( 4KT/6)
min
1, (mm. +
+ +4V
Tm- 1 Am
2T m1
0,
where the first inequality uses Eq. (24) and Eq. (25), the second inequality follows from the fact that there will be only one arm played at lm.a. and the the per-update error is bounded by together with the assumption.
max [... and the last inequality uses Lemma 3.1 T
Am
This inequality implies that arm gets played at round + 1. Once the induction is done, get the desired claim for fixed m, a. Conditioning on E, the claim holds for all m, a, which thus completes the proof.
We are now ready to prove Lemma 3.2. Since (PE)) 2 1 - we make an equivalent statement as follows.
Lemma D.8 (Restatement of Lemma 3.2). Suppose that & occurs. For each phase m and each active arm a E Am, the agent plays arm a for all t T
Proof. Let a be the round that Algorithm ends the search for target arm a in phase m. We prove the claim by induction on m. For m 1, the incentive on each arm E .A + E. then all arms will be played for Tj times. Suppose that the claim holds for and then we consider for + 1. By induction hypothesis, every active arm E Am is played for Tm times, then we directly invoking Lemma D.7 to get that E Am+1 are played for Tm+11 times, which completes the induction. Once the induction is done, we get the claim for the fixed m, Conditioning on E, this argument holds for all m, a, thereby completing the proof.
Lemma D.9. Suppose that E occurs. For each phase m 2 2 and each arm E Am, we have
log(4KT/0)
4 T
[lga 7
max (1, Bml T Tm-1 Am
VI T
bm max (1) 1/ V
5/
bE[K]
2T 2Tm-1
Tm-1
21

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Proof. Consider fixed m, a. Let lmm be the round that Algorithm 3 ends the search for arm a round m. For all & E T one can show
(0)(4KT/6)
max 11, Bmm]
bmm S bmm + +
2T
T Am
4 +
Moga T
2
log(4KT
max (1, [Bml]
Fo (mm,) +
+
+
+ 4
T
(a
min Ne(1m,,))
27 m-
Tm- Am
4
Mogg2 M
log(4KT/0)
max 11,1mml)
n (bm,a) +
+4/
+
3
T
mm-1
mm
Tm-1lAAn
Mogg T
log (6K
max f 1, [Bm
max Pb (b((maa)= Taa (m) be[K]
+
+
+
+VVV
/
3
T
-1
2T
21
T Am
log (gg(4T///) 16)
4
Mog, T1
max 18m |} Am
$ max Po + +1 - Pa (tm, + 11 + +4V
+ /
be[K]
2Tm-1
Tm-1
(og(4K7/0)
4
Mogg T
max (1, |Bml
max (b) - 14 + 7 bE(k]
+ +5V T mm
2Tm-1
T
Tm-1
where the first inequality holds as the definition of bm. takes the minimum, the second incquality follows from Lemma 3.1, the third inequality bounds Na ( 2 Tm-1 and mingg[K] (tm, a) 2 mmxx[1,B.... _IA.. )1/2 the fourth inequality uses Lemma D.4 to bound the per-update error, and the last inequality uses the same reasoning to prove Eq. (24). Conditioning
on E, the argument holds for each m 2 2 and Am, and thus the proof is complete.
D.7. Lemmas for Online Elimination
Lemma D.10. Suppose event & occuus. For all m E N, at E Am holds.
Proof. We prove the claim by the induction. For m = 1, the claim trivially holds. Suppose the claim holds for m and consider for m + 1. Let tm be the round that the algorithm tries to entice arm a" in phase m (in line 11). As Va E Am (1m) 2 Tm, we have for each E Am:
0 0s + pa- (0. Ma) S (tm) + Par (tm) (tm + (tm)) +
where the last inequality holds by event E, the induction hypothesis a* E Am,, and Lemma 3.2.
From Algorithm 1, when the algorithm tries to entice arm a", na- (fm) = 1 1 Da. (tm) + 3 2 m and 1 + (fm) for all E Am {a"}. Plugging these into the above gives
0 S na. (1m) + Th (fm) - (Ta((mm) + The (bm))) 2-
which gives na- (tm) + Pa. (tm) > Ta (fm) + Paa (tm) for all E Am- {a* }. thereby a" E Am+1. Once the induction done, the proof is complete.
Lemma D.11. Suppose event occurs. For each arm a [K], if arm a E Am and & Am+1 then Da 2-
Proof. Notice that E Am and & Am+1 imply that the proposed incentive does not successfully entice arm at the end of phase m, thereby being eliminated. Suppose that such an elimination occurs at round t. When testing arm a at round t,
we have n. (L) 1 + (1) + 3 2-m and 1 + (l)()) for all & E Am {a}. Since arm gets eliminated at round I, we have
0 5 max JEAm (a)
(7,(1) (1) (7a(1) + (t))
(,,())+0000) (t) + -.(()) 3 2-
max jEAAm1a
22

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
S max jEAm
(2,(0)+ (5a(0)+0.0
3 2
-2-
Then, we can further show
3
2- max (p.(t) + +,, - (Ra(t) + oc(()) jEAm
2
max { + 0 + m] (Ha + 0a -2 2-
jeAm
< A. + 2 2-
where the second inequality holds due to E together with Lemma 3.2 and the last inequality holds follows from Lemma D.10 that a" E Am for all m. Rearranging the above, we obtain the desired claim.
Lemma D.12. Let m. be the smallest phase such that A > ma, Suppose that & occurs. For each arm with A. 0, it will not be in Am for all phases 2 ma + 1.
Proof. Consider any arm a with A. > O. We only need to consider E Am, and otherwise, the claim naturally holds. Let t be the round in phase when the algorithm aims to test if arm should be active in the next phase. When testing arm round t, we have Na (t) = 1 (t) 2-- Th and 1 + (t) for all E An {a}. Then,
max (1) + mm( - (1)(() + +aa()))
AE (a)
bEAmu ((a {mall) - -6(1)} (āa(1)) + +ba(l)
3 -2 2m
max
2 na. (1) + 0a (1) (ma(()) + +a((1)
3
2-m
3
2 A, - 2-
2-ma
2
Au
> A. 2 x
2
= 0,
where the first inequality follows from Lemma D.10 that a" E Am, and A. > O, and the second inequality holds due to E and Lemma 3.2.
According to the climination rule (see climination period in Algorithm 1), arm a will not be in phases m for all m ma + 1.
Lemma D.13. Let A(t) be the set of active arms at round f. Suppose event & occurs. For all E [T], oj E A(t) holds.
Proof. We prove this by induction. The claim holds trivially at round = 1. Suppose that the claim holds at round and then consider f + round. We then use contradiction to show that 4;41 cannot be a bad arm. To this end, we assume at+1 & A(t ( 1) and then show a contradiction. Assume that round t is in phase m and phase 7 is the last phase such that dit1 E Ar.
Then, have
0az + paa (t+ 1) Bujt - -aain (t+1)
0az +Baz (t)
Na; It+ Paim - Raz (t + 1)
2 0a. Ma. (1)
Oajn - - (t + 1)
Naz (1 11)
(4g(4)/8))
(og(4T(K/0) 2Na; (1+11
2 0.- + Ma-
Oajes Majts
2N.-(1) (1)
Na; (1+
23

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Algorithm 4 Proposed algorithm for i.i.d. reward with offline elimination
Input: confidence E (0, 1), horizon T.
Initialize: active arm set A1 = [K], bad arm set B = 0. To = 1. for m = 2...... do Set m according to Eq. (4).
for E B, do
Stabilize estimators for bad arms
L Propose incentives (a; 1 L/T)) for Zm rounds where Zm is given in Eq. (7).
for E Am do
Invoke Algorithm 3 with input (a, I') get output bm,a.
Search near-optimal incentive
Set bm. based on Eq. (6).
Propose incentives (a; bm,a) for Tm rounds.
for E Am do Invoke Algorithm 3 again with imput (a, T) to get output in and denote the last round of search by fm.a-
Offline elimination
10
Let (aa((m.a))aejk) be empirical means of all arms round Im.a- Let us define
11
12
2 + [ogg T
Bm
cm
T
+
Tm
+ +2 [Amml 7-
(26)
if ma (tm,a) km (0((mm,)) (mm,a) k/m,e
3/ 2m + Cm then
Update Am+l Am - {a} and Bm+1 Bm U {a}.
2 0a + Ma.
-(0a;_, + Motti
2 2-m-2 -2 --3
(t (1++)
1
22
- 2-m-2 2-3
No; (t+(t+]
2 2-2m 2m
> >
2
2-m-2
2 --3
32
> 0,
where the first inequality uses Eq. (18), the second inequality holds as ož achieves the maximum and Lemma D.10 gives that a" is always active, the third inequality follows from the definition of E, the fourth inequality uses No; (t + 1) > T, and No- (4) > Tm-1 by Lemma D.10, the fifth inequality uses Lemma D.15, the sixth inequality holds since the induction hypothesis gives at E A. = Am, and the last inequality holds since S m.
The above result forms a contradiction as it does not satisfy the definition of 0,41 Thus, the proof is complete.
D.8. Alternative Elimination Approach: Offline Elimination
In this subsection, we show an alternative way to conducting the elimination, and the regret bound of our algorithm maintains the same order. In other words, our algorithm can also be implemented by proposing a one-hot incentive (i.e., only one coordinate of (t) has positive value) similar to that (Scheid et al., 2024b).
As the other two components remain the same, we then show the counterparts of online elimination lemmas in Appendix D.7 for offline elimination. Before that, first notice that for 6n given in Definition 26
[log 77 (1m,a)
T +
S cm:
(27)
min (e(tmm.))
which can be easily verified by considering cases B.n 1 and Bm + 0 and using the lower bound the number of plays. Lemma D.14. Suppose event occurs. For all m E N, a* E Am holds.
24

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Proof. We prove the claim by the induction. For m 1, the claim trivially holds. Suppose the claim holds for and consider for m 1. As Va Am Na(tm) 2 Tm, we have for each E Am:
s aa. + Ha. (0a + Haa
Oa. (lm + Pa (m - (4m.a) ) + Ta (km,a) + 2mm
ae (lm,a) - n (lm,a) - (0u (tm.a)) Tal (4m,a)
+ +22 2
[lgg2 T Na (tm,a)
2
S Da (lm,a) - D Bm (ma()))a) - Vmm + 2
m
+ T
+
m [K] N (2(tm.a)
Sem
where the second inequality holds by event E, the induction hypothesis a" E Am. and Lemma 3.2, the last equality adds and subtracts m) 766 (fm,a) on both sides, and the last inequality uses Lemma 3.1 with Eq. (27). This inequality implies a" E Am+1. Once the induction done, the proof is complete.
Lemma D.15. Suppose event occurs. For each
[K], if arm E Am and & Am+1 then Da 2 2m
Proof. Notice that a E Am and a $ Am+1 imply that
3 2--m + cm
(Ri((mm)) - km (To (mma)) - Um,a))
max jEAm
2
s max (āz(tm..)) - (tm(m))) (Poltmaa) Ia (tm,a)) + cm
jEAm
max [py )+)+)++ ( (tmma))))) (aaltma) + Ba (m(tma)) + Cm
jEAm
< max {1g + +0 + 2- (Ma Oa 2 jEAm
< A. + 2 m- + tm,
where the second inequality uses Lemma 3.1 with Eq. (27), and the third inequality holds due to & together with Lemma 3.2 and the last inequality holds follows from Lemma D.10 that a* E Am for all m. Rearranging the above, obtain the desired claim.
Lemma D.16. Let ma be the smallest phase such that A, > m- +1 + em. Suppose that occurs. For each arm a with Aa 0, it will not be in Am all phases m 2 ma + 1.
Proof. Consider any arm a with A. > O. We only need to consider a E Am, and otherwise, the claim naturally holds. One can show
max { {o by bmenit } - (mm( tlna.a) 2
2-
zEAAm
(t,(tma TTz (tmmaa) (Ba (tmmnna)) - Thy (tima.a)
3 2- Cma
2 max =EAma
2
= max beAAm
(mm(tma + Osl Ooltmana)) - (Da(mmaa)) + Oa (tmara)
2 2-ma
Ema
2 Pa (e + far (tmo,a) - (aa (t) + Da (a(tmaa))
2
ma -ya
2
3
Ag 2
2- ma Ema
2
0,
where the first inequality uses Lemma 3.1 with Eq. (27), the second inequality follows from Lemma D.10 that a" E Am and the third inequality holds due to E and Lemma 3.2.
According to the elimination rule, arm will not in phases m for all m 2 ma +
25

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Now, will show how these lemmas impact the analysis of Theorem 3.4. These changes mainly affect EaEAm EIETE, Aa in Eq. (16).
From Lemma D.12, if suboptimal arm a is active phase m, then m S my where ma is the smallest phase such that Aa 2- m.+1 Cm. This implies that Va E Am with Da > 0 (recall that we focus on phase m 2 2):
A 2
log (T)
max (1, 1Bml
(m -1] Cm, - $2
22 m+1
Em-1 10
(28)
T'
T'm Am
One observe that the only difference is extra
max 1. [mml term, which be handled by the same way Tm Am
shown in Appendix D.4. Therefore, the regret bound maintains the same order.
E. Omitted Proof of Self-interested Learning Agent with Exploration
E.1. Omitted Pseudocode of Algorithm 5
The omitted pseudocode of search algorithm can be found in Algorithm 5.
E.2. Notations
We first introduce some notations used throughout the proof. Refer Appendix for some general notations.
Let (1; Am: be the set of rounds that the algorithm runs in line 12 for active arm E Am in the i-th iteration of phase m.
Let T(a; Bm) be the set of rounds that the algorithm runs in line for bad arm a phase m.
Let I be an indicator that the agent chooses to explore at round
Let Jm,a be the first index of (Dmja;; such that the agent makes no exploration during Algorithm runs to get (m.a)
Let Tm be the set of all rounds in phase m.
Let im be the last iteration when the algorithm proposes incentive for arm in phase m.
Notice that there exist rounds in ( (a; Am) and T(a; Br)) such that the agent does not play target due the agent exploration.
E.3. Construction of nice event & Let us define event Eg
log(16TK/0) 2Na(t)
log(16T
Eo = v(t,a) [T] x [K] (ta(t) Mal
(t)()) - 0a S
(30)
2Na
Lemma E.1. IP(E)) 2 - 6/4 holds.
Proof. By Hoeffding's inequality and invoking union bound, one can obtain the desired claim.
Lemma E.2. With probability at least - 5/4, for all phases m and all bad arms a E Bm
8 Slog(SKTTogg log, (T)8-1)
Σ
4 200y Zm log(21)) +
Zm
(a:(a:
for all phases m. all active arms Am and all iterations
8 llg((1)
Σ
1 200
((()) m. log(2T) +
(i)
(a:AA)
26

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Algorithm Proposed algorithm for self-interested learning agent with exploration
Input: confidences 8 (0, 1), horizon T'
Initialize: active arm set A1 [K], bad arm set B3 = 0, To = 1. for m = 1,2,... do Set 7. based on Eq. (8).
for a E Bm do
Stabilize estimators for bad arms
2/3
Propose incentives (a; 1 T-1) for Zm 2 2log (16KT/6)
Am
rounds.
max B
for a E A. do Invoke Algorithm 3 with input (a, T) for 2 2log(4 (2log T/ times and sort outputs such that
Search Incentives repeatedly
mna <
b(2) S ...
log(4 log, T/8))
m_a
Set T min { T-1, bm. +
1n 1)
2/3
+ Tm + dem / for all where 6n is defined as
T' Am
Cm (og((66KT/)) max |Bmli
1/s
log(16KT/8)
+
(29)
T Tm-1/ Am
Tm-1
for a E Am do
for i = 1ori==...,, log((4 ( log, T/5) do
Incentive testing
Set a counter (t) = 0 and Y-(1) O.
repeat
Propose incentives n" (a; 6 m,a) and denote the current round by t.
Update y:(1) Y-(i). 1, and if A, F a, update cli) Cm.a 1.
(e)
( until Cmaa 200
(1) log(2T)
logí() y.
vr(1)
27m
If js (r dil))) 2 Tm, then break the loop for i. E
15
for a E Am do
Trustworthy online elimination
16
Set Lm,a =
Let t0
be the current round, and (ta (ofn.a)aeel [a][K] are empirical means this round.
17
for 1. 10 m.......44 . + logg(8 logz T/5) do
18
Propose incentives TT (t) with (t) = 1 - 0a (t + 5// log (18(16)888)
Tb(()) - vb E Am (a),
21
and (t( 0, E Bm- A, # a, then update L.,a Lama U (0): else L.ma Lmm U (1).
21
Sort Cm,e in ascending order. Median (eed,an(mm.a) then Update Am+1 An {a} and Bm+1 Bm {a).
22
27

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Proof. We first fix phase m and bad a E Bm Then [T mm) Zm is also fixed. Notice that T(a; Bm) is set that contains Zm consecutive rounds, and thus there total T Z + 1 possible cases. Now, we consider fixed T(a; Bm). By Azuma-Hoel inequality for martingale difference sequence, with probability at least 1 - 8,,
8 8log(1/8) (T Bm)l S 200 / Zm (og((())
8 (log(1/8')
Σ
I
Σ Pt + (ET(a:Bm)
Zm
(ET(a;
where the second inequality first bounds log(2t) I 1og(27) and then bounds EieT(a 1/2 for pt. By choosing ō = 8' (8K// logg 7) and applying a union bound over m, a, and all possible sets T(a; Bm). ) the above result holds with probability at least 1 - 8/8 for all m and a E Bm
Then, one can first fix a, i, and fixed (a; Once (1; Am) fixed, Vigla = (a; Am)) is also fixed. Since (+) (a; Am) ) is set contains consecutive rounds, the number of different ( (a; Am) must be smaller than T Following a similar reasoning gives with probability at least 1 6/8, for all m, i, ( (0; Am):
( m, S 200 / x log(2T)
8 8log log, T (4gg, 1
(i)
Finally, taking union bound for the results of bad arms and active arms completes the proof.
Lemma E.3. Let p E 10,1),8 E 10, Consider a sequence of (og(118")/pp trials. Each trial has success probability possibly depending on previous trial outcomes and is lower bounded p. Then, with probability at least 1 - 8', there will be at least one success umong all these trials.
Proof. As the success probabilities of all trials are uniformly bounded below by constant p, we have
P (no success in r repetitions) S (1 p)" exp(-p-r) S exp( - log(1/8)) = 8',
where the second inequality uses + x S et for all x E.
Lemma E.4 (Restatement of Lemma 4.1). With probability at least 1 - 8/4, all m 2 2, among total 2og (oog(41g) log, T/ calls, there will be at least one call of Algorithm 3 such that the agent makes no exploration.
Proof. We first consider a fixed phase m 2 2. The probability that no exploration occurs in a single call in phase m is (to
save notation, the following product takes over all rounds in this single call)
2[1og T7
1og(2Tmm-)) (1-)))) p.) N co
log(2T)
21 -1-2 2[ogg T cov Tm-1 2 2
T Tm-1
where the first inequality lower bounds pt and uses Lemma E.9 that Algorithm 3 lasts at most 2 2[og2 T rounds, the second inequality follows from the Bernoulli inequality, and the last inequality holds due Tm- Ti > 16cg log((2)) [log, T722.
By invoking Lemma E.3 with 1. we obtain the claim for fixed phase m. Invoking union bound for all and using the fact that there will be at most log, T phases completes the proof.
Lemma E.5. With probability at least 1 - 8/4. for all phases m and all Ams if arm satisfies that for all rounds t E am z0 mm + 8 1og((8K5 log, T)):
max (Tb(t) + (t)(t) < (t) + (t)))) DEA... (a)
(31)
then E Am+1i if arm a satisfies that for all rounds t [to a m, + 8log log, T)]:
max (Tb(1) + (1) > (1) + (1)), bEA... ((a)-(a) (a)
(32)
then a But1-
28

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Proof. Recall that I an indicator that the agent explores round L. Let consider fixed phase m and a fixed active Am- If the arm satisfies Eq. (31) for all rounds t E [m ( log(8KK8 log2 7)), then only when Median(Cm..r when the algorithm enters the elimination period in phase m for arm a. Let B [[-[Fi-i] and let Lt,e = {Ac a, satisfies Eq. (31), Tm.a) be an indicator function.
holds would mislead the algorithm to deem arm a as bad arm. Let T be the set of rounds
As the elimination period starts at the end of each phase m, we can upper bound S co (lg(())) S 1 by using Tm 2 Ti 2 16c6 log( Then, we have
E L, = Pt 2 4'
which implies
Σ 1ET.
E, LL,aa 2 6 6log (8K log, T/6).
(33)
Note that Mediant vediannCmm.d implies that Eiero Leaa S 4log(8K loga T/6). Then
P
Lia S 4log(8K 1og2 T/6) Σ TET
P
Σ
(Lra Ee(he,al) 2 2lgg(8K log, T/6)
BETM.
8K log2 T
where the last inequality uses the Azuma-Hoeffding inequality for martingale difference sequence. By union bound for all E A. and m (with the fact that the total number of phases is log, T), with probability 5/8, the claim holds for all active arm in all phases.
Now, if the arm does not satisfy Eq. (31), then only when Median (Cm,a) deem arm as active arm. We reload the definition Lt,a {A, * a not satisfies Eq. (31) ,t E Th and with this definition, Lr,a satisfies Eq. (33). Median (LCm.)) = gives LETS. L... I 4 log(8K log, T/6). Again, we have
holds would mislead the algorithm to
Lr.o = 1 - pr 2 3. Finally, using a union bound over two results completes the proof.
7. Then, one can repeat a similar argument to get the claimed result.
Remark E.6. noteworthy that Lemma E.5 does not provide any guarantee for the arm that may hold the equality in Eq. (31) for some rounds. In fact, since these arms sits on the boundary, it does not affect the analysis whether eliminate them or not.
Definition E.7 (Define E). Let & be the event that event E, and inequalities in Lemma E.2, Lemma 4.1, and Lemma E.5 hold simultaneously.
Based on Definition E.7, one can easily see ((E)) 2 1 - 8, by using a union bound.
E.4. Proof of Theorem 4.2
The following analysis conditions on E. Since the elimination lasts at most O(K log (og(KO-1 log(T)) rounds in each phase, the number of phases is at most (log T), and the per-round regret is bounded by absolute constant, the total regret during all elimination periods is bounded by
O (K (og
The search algorithm last at most O(K K log (T)) log(5-1 log T)) rounds in single phase and the per-round regret is bounded by an absolute constant. Hence, the total regret during the search is at most
O(K log (T) log ( log T)).
29

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
The regret in the first phase can be bounded by O (K log (KT)6)) Thus, write
Rr S [K
(KT/5)) + Σ
Rm:
m22
where R., is defined as: (see Appendix E.2 for notations)
Rm Σ Σ
E
max {0, T3 (t)} (0A, xA,(
bE[K]
AEAm iStm,a (a:A))
Σ
max (0p mz (0,, - =A,
bE[K]
B (a:(a:
One can show for all m 2 2
Rm S ΣE
E
max 10, Ti (t) - (0 TA.
DE[K]
acAm istmia TET (aiAm)
+ 0 (log)) (KT/ (I.m, 11) 12/8)
Σ Σ Σ
max (0, Tī (f) - (0. 1 =a((1) T(Ar = a}
bE[K]
aEAm iSmma LE (+)( (aiAmn)
ΣΣ
Σ
Virle mi log(T)) +
log (i)
+ O (1 (KT/8)]Bml (KT (1.m ([Aml|mm-) 12/3)
+o
nEAm
iStmma
where the second inequality uses the repeat-condition. Further, one can bound
(Vrlld log(T) (Tg)) +
log Ymk.
Σ E
aE is iStma
Σ
( (VTn I'm log(T") Vlog2)
aeAm iSimaa
< (|Ama log(0- log(0-+logT)) log
(VIm log(T)) + log 4)
S 0 10- (vl (VIAml|TT Tm log(T) Am Vlog
(34)
where the first inequality uses the fact that y.( < 2T and the second inequality holds due to the number of iterations is at most Ollog(8~ log T),, and the last inequality uses (m S .Tml
We continue to bound the total regret of Eq. (34) as
o
| Σ log(0-1 T) (VlAm Tm log(s) (nll)g))
0 (log(0- loo T) (VKT log Tlog(1)
(ae(o~'logT])
Then, for any E Am, is im and t E (() Am) with A, a, we can bound
max (0, - (t)} - (0. - Ta (t))
KE(K]
= 0u; + Paz (t) - max (t) - (f. (t))
Ke
log(16TK/8)
$ 0a; Ma;
max (b(() (0. TTa (t))
2Noo (t)
bE[K]
30

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Ouz Mug
Cm
max (t)
(0, Ta (())
DE[K]
= 0az + +Maa +
Em
max [1)(1) [E[K]
(0.. Um.a)
(0. Bumga
I fa
Ma +
Cm
max pi((t) bE(K]
|max(1, 1, 1Bml)
2/3
I Da +
+ Cm
(35)
T Tm- Aml
where the first inequality holds due to E, the second inequality uses Eq. (39), the third inequality uses the fact that T I J(mma)) for all S Jm.a by Lemma E.11, and the last inequality uses Lemma E.12.
Note that line 14 of Algorithm implies that Eisin, EIETO(EAA.)) 1(A = a} - ((T,) Hence, using Tm41 ((T,)) for all m, have
Σ Σ E Am iStmau (a:Am))
max f0o xz((t) (0. - (0a- IsA = a}
DE[K]
KT
1/3 ))
KT
0 Tm De aEA.m.
Aot
Klog
K log
(Im (AmlAm + Am T'm log
From Lemma E.15, if suboptimal arm active in phase m, then m S ma where ma is the smallest phase such that log( (6KT)6) This implies that 27ma
An 9
log(16KT/6)
log(16KT/o)
Ya Am with A. >0 4. 10.
< 9
(36)
21m.-1
m-
Hence, can bound
Tm E.
5. log(KT/8))
A.
(37)
By bounding Tm Aml <
[Tm]. we can further bound
ΣΣ
Σ
max {0s - (0,-m((1) (0. - -=a((()) T(A, a}
[b[[]]
mmm i5/maa BET (a;(A)))
KT
1/3
KT
50
Σ
Klog
K
([Tma))
Amm Tm log
5
m22
((
KT
1/3 T/
KT
K log T log
+
KT log(o log
8
where the last inequality uses Hölder's inequality with the fact that the number of phases is at most Ollog T). Combining the above results, we have
Ry =0 Tlog
KT
))
1/3
T 4/ + (KT + K Klog" (KT/6) Klog"(KT/8)
8
By choosing 1//,, we get the claimed bound for E. Rr..
31

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
E.5. Proof of Theorem 4.3
This proof idea is similar to that of Theorem 4.2. Let us first bound the regret caused by elimination. Notice that since the proposed incentive during trustworthy elimination is not one-hot, the regret in single phase evaluated is bounded by the product of per-round regret upper bound ( and the upper bound of total number of rounds O ( log (K6 (K-1 log(T))). As the number of phases is at most (log T), the total regret incurred by the elimination is bounded by
o (K² log loo log(T)))
Then, we bound the regret incurred by searching. Since the algorithm proposes one-hot incentive, and the search process lasts (log T) rounds for each active arm in each phase, the total regret incurred by searching is bounded by
O(K log' log² log( log T))-
Moreover, the total regret in phase m is bounded by
O (K lo
Note that since the algorithm always proposes the one-hot incentive, except elimination period, we thus can write
Rr = O (K² (KT((K1)))) + Σ
Rm.
m22
where
Rm = Σ
E aEAm iSim,a (a:AAm)
E
10, m6
Us
OA Σ (t)
DE(K]
zE[A]
[E]
Σ
Σ
max (On + 1b) BE(K]
max Ps =E[K]
0a, Σ (1)
oEBm (a:
nE[K]
Σ
Σ
Σ
max (0s + mb) BEIK]
max f1= (0.s TA, (t) =E|K]
aE i5 iSima (a:Ad))
Σ
Σ
(O, + 1b) max HS (OA. (t)(
max
sE[K]
B.B... ta:(a:
where the last equality follows from the fact that the proposed incentives are one-hot during T(a; Bm) and 7 (a; Am).
The analysis on regret in phases m 2 2 simplified version of the proof of Theorem 4.2. The only difference is to use Lemma E. to obtain Eq. (35). Thus, the regret bound for Σmze Rm, remains the same.
E.6. Supporting Lemmas
Lemma E.8. Suppose holds. For each phase m with Bm, + every bad arm By will be played for at least log (16KT/8)
2/3
[Aml T ) times.
ma.x(1,
Proof. Let I be an indicator that the agent explores at round f. Consider fixed phase m with B, * 0 (i.e., m 2 2), and we fix a bad arm E Bm- Lemma E.2 gives
Slog(8KT (T))-)))
Σ
4 200 Zm log(2T))
Zm
IaT(a:Bm)
32

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Notice that if the agent does not explore at round, then she must play the target based the proposed incentive. Thus, it suffices to show
8 (8K' log2 (T)6-1)
7mm
Zm
200 V Zm (2T) +
Zm
To this end, we let
anax|2cx (2T() V /log((877 log, (T)/6)}.
Then, it suffices to show Zm 20 Zm 1/vZm) 2 0. One easily show that for 2 1, the function f(x)
20(vI + 1/vz) is monotonically increasing for x 2 a² and f(16a²) 2 0. Then, we verify Zm 2 16a as:
7m log (16KT/5)
Am
2/3
Ti
2/3
(maxf11|BmL) [mml
Tm-1
z
2 802
2
We thus complete the proof.
(ima) Lemma E.9. Let tm,a be the round that Algorithm: 3 ends the search for arm a in phase m and outputs Um,a" For each phase m, we have
Gma)
blmm,a) m,a
( (mmma
(t()m.a))
E
4 0,
+
[lgg2 7
2
(38)
T Na(Hlma))
minge[K] N₂ (mm.a)
Proof. Since in Jm.a-th iteration, the agents does not explore, the proof directly follows Lemma 3.1.
Lemma E.10. Suppose that & occurs. For all m 2 2 and E Am. if every active arm in Am-1 is played for Tm-1 times, then we have
Wi U T(o)
(dm.a)
> (t)...
iS.mmaa
Proof. Let consider fixed phase 2 2 and arm Am Am-1 and let (m.a) be the round that Algorithm ends the search for arm at round m and outputs b (jmma)
log(16KT/0)
log log(16KT/8)
2 2min:e[k] Ni(1)
2 min T Tm-1, log (16KT/8)
AAml T 1-
2/3
max Bmnl
log log(16KT/0)
lox(16KT/8)
+
21 21m--1
2m log (16KT/6)) (max((111B...) Tm-
1Am
2/3
cm
(39)
where the first inequality uses the assumption (i.e., the number of plays of active arms) and Lemma E.8, and the last inequality holds due to the definition of em given in Eq. (29).
By Hoeffding" inequality and the fact that the confidence interval is monotonically decreasing as samples increase, we have for all b E A and Vt E Uisima Tre
(here a is the fixed arm mentioned above)
log(16KCT/))
log log(16KT/8)
(t())=
Pb
+
2N:(t)
2No(t)
log 1og(16AT/0)
log log(16kT//)
C
μ4b
minee]k) Ni(1) 14h +
2 minne]k] N.(1)
33

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
C [n cm: Mb
Em]
(40)
where the last inequality uses Eq. (39). Let b, E argmaa Pa (1). Note that Eq. (40) gives that
AI E
U T max M6, (1) Tbn, (1) S Mb, m, + 1) 2pm S max Ths (tiimm))) + 1) + 2c
(41)
BE[K]
bE[K]
$55m.a
Hence, following similar reasoning in Lemma D.7, one can show 1A E Uisima T
max (bt()) (Ta(t)
bE|K]
(imma)
max [i)(() tio Ti0(1) bE(R]
m,,a
min
((im.a)
min
max Nin bE[K]
(is(t (tlimm))) + 1) Ra (tlima)) 1) + dem
(im.a)
min
Pio (thheaa)) Poo (clhmaa)) ) bE[K]
max
mmax 1,, |Bml
2/3
1
+ 4em
T ('m Aml
Tm-1
which implies that arm a gets played at round L ++ 1. Once the induction is done, we get the desired claim for fixed m, a. Conditioning on E, the claim holds for all m, a, which thus completes the proof.
Lemma E.11. Suppose that & occurs. For each phase m, each active arm a E Am will be played for at least Tm times before trustworthy online elimination starts. Moreover. for each phase m, active arm a E Am, we have in,a S Im and T & 3(Ama) for all S Jm,a-
Proof. Before that, we first show for all m
8 8log(1) Tm
2T
200 v 2T log(2T)
+ V
2
Tm-
(42)
For shorthand, we define
max 220 / log (2T) logg
To show Eq. (42), it suffices to show Tm a(v + 1/VTm 2 0. One can easily show that for 2 2, the function f(x) = x-- a(va + 1/vI)) is monotonically increasing for x 2 a² and f(4a²) 2 0. As we have T. 2 Ti 2 4a Eq. (42) holds for all m 2
Now, we start prove the first claim by using induction on m. For the base case, one can see that the incentive on every arm is always + T-1, which implies that if the agent does not explore, then she must play arm Thus, by Lemma E.2, in the first iteration, the repeat-loop only breaks when y-(!) = 2T, By Eq. (42), for every arm a, the number plays of each is at least Tj times. Therefore, the base case holds.
Suppose that the claim holds for phase m 1. Then, we aim prove for phase m and consider fixed E Am- Assume that the number of plays for show that the number of plays of arm in the -mh iteration is at least T,, times. Based on Lemma E. we know that in the Jm.a-th th iteration (the exploration does not occur when generate corresponding incentive), the agent will always play the target arm a. Thus, by Lemma E.2, in jm.o-th iteration, the repeat-loop only breaks when y(Om.a) 2T By Eq. (42), for every arm a, the number of plays of each a least Tm times. Once the induction done, we complete the proof for the first claim.
is less than Tm before the Jm,a th iteration (otherwise the claim holds truc). We will
For the second claim, we consider fixed m, Since the above shows that the number of plays a is at least T'm in the jm iteration. According to line of Algorithm 5, the iteration number cannot go beyond jm.a- Moreover, (1(0)
34

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
assorted in ascending order, and thus byn S Dm,a" for all i S Jm.a- Conditioning on &, we repeat this argument for all m, complete the proof.
Lemma E.12. Suppose that occurs. For each phase m 2 and each arm a E Ams we have
vt E U (a;
I max (t) - Ma +
4
+
[log2 T1
+
[max(1, 1, |Bml]
) Tmm1lAmi
3/3
+ Tm-1
4
+ 5cm-
bE|R]
T Tm-1
iS.hm.a
Proof. Consider fixed m, a. Let (mma)) be the round that Algorithm ends the search for amm a round m, which Ema
outputs (im.a) For all & Uisim.a
T6
(a; (a; Am), we use a similar reasoning of Lemma D.9 with counterparts Lemma E.11,
Lemma E.8 and Eq. (40) to show
p(mmaa) mm,a
max (1, 1, |mml
2/3
1
+
+
4cm
Tm- Aml
Tm
4 + +
1log2 71
max{1, 11 (8,
2/5
3
S Ty m,
+3
+
+ 4em
T
Tm-1
T Am
Tm-1
4
loog '
max(1, |Bm 1
2/8
3
max Po (tllimm be[k]
(m,
Pu (tlimmaa)
+
T
+
Tm-1
+
T 1mm1lAmm
+
Tm-1
+ 4cm
+ Moga 71
|max 1Bmml1
4/3
max Po (t be[k]
mi,
+ +1 - (tlimia) mome
Pa(ttiima
+ 1)
+
T
Tm-1
+4
T Tm-1|Aml
+ Tm-1
+ 4cm
4 +
[ogg2 T
max [1, [Bml]
2/3
4
max (t( - Ma + bE[k]
+4
+
+ 5cm-
T
Tm-1
Tm-1
Conditioning on E, the argument holds for each m and Am, and thus the proof is complete.
Lemma E.13. Suppose that & occurs. For each phase m 2 2 and each arm E Amn have
E U (a;
(m.a)) max Pbb
Ma +
4 T
[log2 77
+
mmxx(1, 18m
2/3
+
4
+ 6em-
be(K]
Tm
T
Tm-1
iSIm,
Proof. Consider fixed m, a. Let by E argmax
(t). For any E Uisime T( Amp), Am), we can use Eq. (40) to bound
Tb, (t) I Mb. Cm I max Ha + Cm.
aE(K]
Pluggin the above into Lemma 12, we show the claim for the fixed m, a. Conditioning on E, the argument holds for each 2 and E Ams and thus the proof is complete.
Lemma E.14 Suppose event & occurs. For all E N. a" E Am holds.
Proof. We prove the claim by the induction. For we consider phase m 1. For each round & E [tu [lm,ar> 1 mm.. + 8 8log(8K88 logg T)] and each E Am {a }. we have
the claim trivially holds. Suppose the claim holds for m, and then
0 S Oar + Ma- - (0, + ma)
log (16KT/5)
pa (Con.a)) + Tha (1) - (0a (1o,.r))) + + +4V
2T,
log (16KT/8))
... (1) + Da (1) (Ta + m.
2Tn,.
where the second inequality holds since Lemma E. 11 gives that in each phase m, every active arm is played for Tm times before the elimination starts, and active in phase m by the hypothesis induction, and the equality holds since when
35

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
testing arm a", aa (t) (t. 5V
log(16KT/o) and the incentives of all other active arms Am {a*) 2T
all equal to + 0a a.) Since above holds for a E Am, we rearrange to get
(og(16KT/0)
Ta- (1) + Pa
max acAm
{ar] (1) + (1)) +
max aEAAm. 1:0A-maaa (a*)
(Ta + (1)).
2Tm
Conditioning on &, we use Lemma E.5 to get a" E Am+11 Once the induction done, the proof is complete.
Lemma E.15. Let ma be the smallest phase such that Da > VV A, 0, it will not in Am for all phuses m 2 ma + 1.
log(BKT/A)
Suppose that & occurs. For each arm with 21
Proof. Consider any arm a with Aa > O. only need to consider E Am, and otherwise, the claim naturally holds. For any round an ama + 8 8log(8K8 log, 7),, we have
max BEAm {a}
(To(t) + =b(t)} - (Pa(t) + aa)i))
(Pa. (t) + Ta- (t)) - (Pa(t) + TT(t))
log 1og(16KT/5)
pa. (t) + Da- (tmma) (Pa(t) + +la(tmaa) 5//
2Tm.
(og(16K7/8)
2 Aa VV
2Tm.
where the first inequality uses * a* and Lemma E.14 that a* E Am,. the equality holds since when testing arm o, (t) 1 (to..)) + + (16 and the incentives of all other (non-target) active arms E Am are all equal to 1 (.(( and the second inequality holds since Lemma E. gives that in each phase m, every active arm is played for Tm times before the climination starts.
2TT
According to Lemma E.5, arm a will not be in phases m for all m 2 ma + 1.
36

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
F. Omitted Proof of Self-interested Oracle-Agent with Exploration
Algorithm 6 Proposed algorithm for celf-interested oracle-agent with exploration
Input: confidences 5 (0. 1), horizon T.
Initialize: active arm A1 [K], bad arm set B1 = 0. To 1. for 1, do
Set Tm based on Eq. (8).
for a E Am do
Search Incentives repeatedly
Use binary search for 2og loga T/6) times and sort outputs such that
6(1) S 6(2) S ... 6 log( log, T/6)),
(1
Set m,a bm.a T-1 for all
for E Am do
for i = I,..., 2 log log, T/6) do
Incentive testing
Set a counter ( = 0 and y 0. repeat
Propose incentives n (a; ( ) and denote the current round by t.
Update Y/h y1( 1, and if A + a, update (6) Cmaa + 1.
(6) until Cm.a 200 Y! 1og(2T) +
logit) Y
or m.a 2T
ES (Y cma) ) 2 Tm. then break the loop for i.
for E. Am do
Trustworthy online elimination
Set Lm,a = V.
Let 4n.a the current round, and (0a (tm..a) ]e([k]] are empirical means at this round.
15
for t = 40 m......: to + 8 log(8K log2 T/5) do
16
Propose incentives s(t) with (t( 1 (to + 3/ log (8
TT(t) + (b vb E A.. {aa,
21m
and (() = O, Vi E Bm- A # a, then update Lm.a = Lm, U {0}; else Cm, = Lm, U f1}.
18
19
Sort Lm,e in ascending order. Mediani aandiannmmmaal = 0 then
20
Update Am+1 = An - {a} and Bm+1 = Bn U {a).
21
F.1. Notations
Throughout the proof in this section, we follow the exactly same notations used in Appendix E.2.
F.2 Construction of Nice Event E
All lemmas in this section follows exactly the same argument used in Appendix E.3.
Let us define event & as
log(8TK/8) 2No(t)
Eu v(t,a)e [K] [t. 0a S
(43)
Lemma F.1. ((E)) 2 1 8/4 holds.
Proof. By Hoeffding's inequality and invoking union bound, one can obtain the desired claim.
37

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Lemma F.2. With probability at least 1 A/A.for all phases m, all active arms Ams and all iterations i,
8 log(s)
Σ
4 200 Y log(2T)
(o;Am)
m.a
Lemma F.3. With probability at least 8/4, for all m 2 2, among total 1og(4 logg T/6) calls, there will be at least one call of Algorithm 3 such that the agent makes no exploration.
Lemma E.4, With probability at least - 8/4, for all phases m and all a E Ams if arm a satisfies that for all rounds t E 700 10 Log(8K6-11ogg T)):
a
max beeAm (a)
(To(t) + 146) < (T) + pa),
then Am+1i if arm satisfies that for all rounds E [ a m, +logg(8K3 log, T)]:
max
(TT(!) + mb) (To + Ha),
BE (a)
then Bm+1- Definition F.5 (Define E). Let & be the event that &n and inequalities in Lemma F.2, Lemma 4.1, and Lemma F.4 hold simultaneously.
Based on Definition E.5, one can easily see PP()) 2 1 6, by using union bound.
F.3. Supporting Lemmas
Lemma F.6. Suppose that & occurs. For all phases m. and all active arms a, we have
J(mmaa) E T T
2 T
Proof. As holds, Lemma F.3 ensures the existence of Jm.a. Then, (Scheid et al., 2024b, Lemma 8) gives the desired result.
Lemma F.7. Suppose that occurs. For each phase m, each active arm Am will be played for at least Tm times
before the elimination starts. Moreover, for each phase m. and active arm a E Ams im.a S Jm.a and bm I -Dnna for all i < Jm.a.
(mma)
Proof. Since we assume holds, Lemma F.6 implies that if the algorithm tests (mm.a) for target active arm a, then the agent will always play arm a, except exploration occurs. Thus, the desired claim is immediate via the exact same argument in Lemma E.11.
Lemma F.8. Suppose that & holds. For all m E N, a" E Am-
Proof. This proof is similar to Lemma E.14. We prove the claim by the induction. For 1, the claim trivially holds. Suppose the claim holds for and consider for m + 1. For each round E [o 1 mma + 8 Mog(8K6 logg 7)] and each E Am. - {a" }. we have
S 0.t + Ma.
(0., + Ma)
log(8KT//0
Oar (Cm.a) )+ + por - (0m(t + Ma) 2
2T.
log(16KT/6)
= (t) + Pa- - (Ma + (t))
21'
38

---

Principal-Agen Bandit Games with Self-Interested and Exploratory Learning Agents
where the second inequality holds since Lemma F.7 gives that in each phase m, every active is played for Tm times before the elimination starts, and a" is active in phase m by the hypothesis induction, and the equality holds since when
testing arm a", To (t) 1 0a- (bm..-) + 3/ all equal to + 0a (.) Since the above holds for all a E Ams we rearrange it to get
(ng(16KT/)) and the incentives of all other active arms Am {aa are 2f.
log(16KT/0)
Fa (1) + M 2 max
(ma + =a(()} +
max A {ar}
(Ma(1) + (1))-
aEAAm {a*)
27m
Conditioning on E, Lemma F.4 to get a" E Am+11 Once the induction done, the proof is complete.
Lemma F.9. Let ma be the smallest phase such that Da > BB
Tog(SKT/0)
Suppose that & occurs. For each arm a with 2T
Aa 0, it will not be in Am all phases m 2 ma +
Proof. This proof follows a similar to Lemma E.15. Consider any arm with A. > 0. We only need to consider a E Am. and otherwise, the claim naturally holds. For any round E [mm 'n + 8 1ogg(860-11 log, 7)], we have
max {[a] beAm.
{ub + Tb(1)] (Na + Ta(1))
2 (Ma. + na- (t)) - (Ha + xa(t))
Mar + 0a (tmma) - (Na + (a(tfrna))
log 1og(16KT/8)
2Tm.
log( (6KT/))
2 A. B/
2T m.
> 0,
where the first inequality uses * a² and Lemma F.8 that a' Am, the equality holds since when testing (16 and the incentives of all other (non-target) active arms E A,,. are all equal to 27
(t) + (t).a) + 3/
1 1 (t) and the second inequality holds since Lemma F.7 gives that in each phase m, every active arm is played for Tm times before the elimination starts.
According to Lemma F.4, arm a will be in phases m for all ma 1.
F44. Comparison with (Dogan et al., 2023a) under Same Regret Metric
Dogan et al. (2023a) use different regret definition E[Rr] where
T
Σ Ta (t) )) aEA
R
Σ
max {Op + 1b) max Ms
0A.
(44)
bE[K]
sE[K]
To fairly compare the regret bound, we evaluate the regret bound by E[Rr]. Theorem F.10. Suppose T = (2(K). By choosing 5 = 1/T, Algorithm 5 ensures
E Ry o (log $ (KT)KTT + (KT) K log" K2log"(KT))
Proof. We first follow the same reasoning in Appendix E.5 to bound the regret in binary search, elimination period, and the first phase by O (K2 log" (KT/8)). Then, Ri can be written as:
R O (K² log (KT/))) + Ru.
m
39

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
where (recall that Algorithm 6 does not play bad arms for stabilization)
Σ To(()) )
Rm Σ
Σ
Σ
max {8s + +bb DE(K]
max M =E[K]
AA. --
Am iStm,u (a:Am)
VEA
Σ
E
max {0s + [bb}
max 1t= (0s, - na(t))
6E(K]
=
aE.Am 1Stm,o (ai(A)
where the second equality follows from the fact that the proposed incentive is one-hot (arm a has the only positive value) for all rounds in ( (a; Am..
According to the incentive testing, the algorithm proposes one-hot incentives, and thus we have
Rm = Σ Σ
Σ
max {06 + 14b) bE(K]
max uz= - (HA, - -Ta(t)) =E(K]
oEAm iSmma (a:A)))
Σ
Σ
E
max (0s + 11.) - max u1 - 0^1 T BE(K]
=E(K]
oEAm is am, LET (asAA))
Σ Σ
E
max {As + 110 bE(K]
max u4 - A.. + n + =E(K]
T
aEAm i5mma (ET((a:Am)
Σ
Σ
Σ
Aa + T
T(A, = a}
oελm is immma ((m
Σ Σ
E
max {6, + no}
max μ1 - 0r, + =x + 2 =E[R]
I(A, + a).
[E(K]
T
acAm
&5 iSimma (e:A))
where the inequality uses Lemma F.7 and Lemma F.6 bound for all i S jm
J I Tlhmau) I - + T
2
Then, Eq. (34) to bound
ΣΣS ΣΣΣ
max M2 AA. + T + 2 sE(K]
max {0o + pm KE(K]
u(Ai #a)
a. iSt... (eiAA)
s 0 (1og(0-11 log
(v Tm lTg + |mm Vlog
Note that line 12 of Algorithm implics that Σ Eistm, EIETO(ASAM) IfAe = a} < O(Tm). Hence, using Tm+1 = O(Tm) for all m. we have
Σ Σ A eEAm iStma (a:A))
Tm Σ Au acAmm
< 0 (lAm / log KT/6)
<0 (VIAm | log( KT/5))
where the second inequality uses the same approach Eq. (37) with Lemma F9,, and the last inequality holds due to |A TT I |Tml Therefore,
ΣR,, Rm 50
Σ (VIAm) Tm (KT()) + logg( log (VK(Tm) log(T) + [Aml vloge))
m22
m22
40

---

Principal-Agen Bandit Games with Self-Interested and Exploratory Learning Agents
Algorithm 7 Proposed algorithm for linear reward model
Input: confidence E (0, 1), horizon T.
Initialize: active arm set A1 = A. bad arm set B1 = 0, =1 for m ..2,...0 do
=1
Set mm - +4d log( (4K88-)) and Em 4 (ddoo:. ")
2log(4KT6 1)
* mm
then Find a design wm for Bm and for E Bm do Propose incentives (a; 2d + 1) for Un (a) = (4)) T
Definition G.I.
Stabilize estimators for bad arms
rounds.
Find design find design Pm for 2 = Am and C 2 in Definition G.1. Invoke Algorithm 8 with imput (fm-1, 1) get output Cm Rd.
Search parameter for s*
for a E Am do
Set bm,a- min {2d + T- maxsEA (cm, a) + (1 32d)cm + 11 For the following Ppm [a) rounds, propose incentive x (a; bm.a).
10
TJ-
Update estimates
m = -V- Σ (t), where
Vn=
Σ [m aE-Am
Σ (a)ob
(45)
where Tm is a set contains rounds when interaction occurs line 11 and line 6 in phase m. Invoke Algorithm 8 again with imput (em, T-1 to get output cm Rd
13
for E A. do if maxbeAm (pm + Cm, b a) (7 32d)em then L Update Am+1 = Am - {a} and Bm+1 = Bm {a}
Offline Elimination
(0g
Combining all the above, we have
= 00gg (KTT + log
By choosing 8 = complete the proof.
G. Omitted Proof for Linear Reward in Section 5
G.1. Omitted Pseudocode Algorithm and Algorithm 8
We present the following definition.
Definition G.I. Let Z C Rd be finite and compact set. A distribution 2 - 10 is C-approximate design with approximation factor 2 1, supzez |lalle( S C. d where G(T;; 2) Σ.ez π (2)22TT
Since the exactly optimal design (i.e., C= = 1) is typically hard compute, consider the 2-approximately optimal design, which can be computed efficiently (Todd, 2016).
The omitted pscudocode can be found in Algorithm and Algorithm 8.
G.2. Notations
We introduce some notations that will be used throughout the proof. Refer to Appendix A for some general notations.
Let mt)) be the phase that round lies in.

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Algorithm 8 Multiscale steiner potential with conservative cut
Input: error с 0, O. Initialize: let current round to. Sto B(0, B) (2:2=r- x x y A}. 2, = Vi N.
for i. lo. -.. do
Pick #; (a. a ||; - afll where af -a3 ur width(S,, u) and at * ta EA
Find largest index i such that wi width(S,, v4) S 2
if 2 < 4 al of then
L Break and randomly pick vector from St to return.
else
Query such that
Vol (v E S. + (u, 2 ||4] a²'l
(vt o) - Vol (S. + 2; (()
Propose incentive at) + Taf (t) d + Vrs and Tb(() 0 for all b a/ A, = at then
Update S141 = U Se (x) 2 a at || - (1/+ - }))
10
11
else
Update S411 = {uE Se: (0, $ | afll
(ye + e)}
Let Tm the set of rounds that in phase m, excluding those rounds for running Algorithm In other words, Tm is a set contains all rounds when interaction occurs in line and line 6 in phase m.
Let Tm,a = {t E Tm : A = aa.
Let T set of all rounds when Algorithm 7 runs line 11 or line 6 for target arm a in phase m. In fact, Lemma G.6 implies that conditioning E, T
Tm.a.
Let U, = E' A.A and let U/ be its invere- With the definition of Us, St can be written as:
3, U. Bs.(s)A..
Let Ts be the set of all rounds that not in phase 1 and let us define event
a gFrinciple n gagent
where
(4KT
Agentt
(a.t) Ts: -5, s,,aa)= /2 2 2alallu, log
and
gerinciple
V(a.m) E AAN:: (P -mm-mmmm--- -v*,a) s bois221llllee 2/lallu. log
4KT
Notice that in phase 1, every arm will be played deterministically according to (approximately) G-optimal design. Therefore, once phase ends, for all E T2I. U, is invertible which implies that U. U,
42

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
G.3. Proof of Theorem 5.1
The following analysis conditions on E, which occurs with probability at least 1 1 by a standard analysis of linear bandits (Lattimore & Szepesvári. 2020, Section 20). As the algorithm runs in phases, bound the regret in phase m can be 1)). Then we bound the regret in each phase m 2 2. Lemma G.5 shows Algorithm 8 lasts at most (d (dello"(demm1)) - (d (ddKTg))dKT))) rounds in phase m 2. As the number of phases is at most (log T). have
bounded by (df (ogg(T//o/) /6)) since per-round regret is (d) and Ti O(dlog(KTT))
RT S 1.0500 (d log (dKT/5) log(T)) + Σ
Rms
m22
where
Rim= = Σ
max "EAA {("', .a) - [a(()) -
TA, (11)
TT
It remains bound Rm for mn 2. Then, let consider a fixed m and bound
Rm= = E
(u' (p* oj) + (St.a)) - -max (št, b) - ((v", - -A. (t)) bEA
TT
(v' (v",at) + a5)
max (5t, b) - (1v2 "10",A,) ,Ae - -A, (t))
BEA
ac Am tETme
+ Σ Σ
(v', (v',at) + +B2,, - max (5e, b) - =(w²,, ,A)) TA. (t))
BEA
aEBm.. LETma
Σ
(v",a)) + (8),, (T)
max (8c, b) - (11", BEA
(007,aa-ooo) - -xa(t)))
Am EE TTTm
Σ
Σ
(w'aat) + (B))
max (5 b) ((v', ,a) =o(())
BEA
BEBm TETm,
Σ
(w"att) + (B),
-max (Be, - ((/",0) - (t))
BEA
ae AEA... TETm,
+ O
T log (log(((KK))))))))
where the first equality holds due to the definition of aj, the third equality follows from Lemma G.6, and the fact that the proposed incentives in these rounds are one-hot, and the last inequality bounds the regret on all bad arms by multiplying the number of rounds by (d) (the upper bound of per-round regret).
Then, for each active arm Am and E Tm.e we turn to bound
(V", + a7) - max (Se, b) - ((vt, - (t))
BEA
$ (v*, , at) + (s, at) 6m-1
max (3,, b) - ((22 a) T (t))))
BEA
S (v' + aa) + 6m- - max (8t, b) ((v', (t)) BEA
s 0 Da + d d ++++)
+ 1 7)
where the first inequality holds due to Lemma G.7, and the last inequality uses Lemma G.8.
By Lemma G.6, each active arm a E Am will be played for [mm(a) (a)Tm times in Tmma = TEE As TTmaal= = [p (a)mm for any active arm a, Tm+1= = (Tm.) for all m, and [supp(y.) I Od log d), we have
Σ
( (ut,at) + (Be, 07) -ma (Fc. B) ((V", a) TT (0))
DEA
GEAm TETma.
43

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Pml(a + Tm + Tmddm-1 1 + log log T
S Tm
Σ a.Am
Pm(a) + d# TT log (T//)) + Tm
0 Tm
Σ
+ dd T logglog( (TK/8) + lo logglogg)
T
am
where the last inequality bounds
dlog (4KT8-1)
6m-1 = 4
min (dlog( (dlog(4KTTTT--- (4T881)))) m
d log (4KT8-1)
d log (4KT8-1)
S 4
+ 2 V (dlog(4KTT-1))
Tm-1
From Lemma G.10, if suboptimal arm a is active phase m, then S my where my is the smallest phase such that Au (9 64d) This implies that Va Ami
log (og(K)/8) Tm-1
+ d (Im-1)- log Log((TK/6)) (TK/8))
Au s (9 + 64d)cm. -1 S (9 64d) 6m SO di
(46)
where the second inequality uses m S Ma- By again using Tm+1 = (Tm) for all m and ExeAm Pm(() = 1, we have
RT 5 d Vlog(K/88) Σ VT + d' log (KT/8) Σ TT dl log (dKT/5) log
00 ( log((T + d log (KT/5) de log (8KT/8) log log
where the last inequality uses Hölder's inequality together with the fact that the number of phases at most O(log 7) < (log(TK/))).
G.4. Technical Lemmas for Algorithm
Lemma G.2. If index is selected at round t and the algorithm does not break this round, then
7 (ol + 2,B).
Vol(S +, S
Proof. According to the incentive proposed during running Algorithm 8, the agent picks either of or at at any round t. For the case A, = a, similar argument of (Liu et al., 2021) gives that Vol(S.+1 + B) I Vol(S, + BB.. For the case A₁ = a², we have St+1 = {o E S. : (v, $ ||a] aîll (Vl + +)) Notice that
v S4+ + BB (v, || a3ll (st - o
E S. + zB (1) - ||a! a²ll (ve (we- {]
Due to the half-eut (line 7 in Algorithm 8), have
Vol (LEE Set BB (t) < |ot a2'l- (yr - -))}) Vol(S, + BB).
1
Then, bound the volume of S411 B with (v) > ||at a?ll- (yx c). Let C be the largest volume of section of St + BBB along the direction zt. By the analysis of (Liu et al., 2021, Lemma 2. 1), we have
Vol(S, B) 2 42,C.
(47)
44

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Since {o S + 2,B: (e, 2 a --ح (v+ (v)-))
} has cross-section with volume at most C, the width is 2, +
2 | abll c z where the inequality uses the non-break condition (recall line 4), we have
Vol (LVE Si+1 + aBB: x1) 2 ||a| a²ll (ve- -))- 2
3 2, 2 $
3 Vol(S. + 2,B),
8
where the last inequality holds due to Eq. (47). Combining both volumes, the proof is complete.
Lemma G.3. For each round t that Algorithm 8 runs in phase m. if (st s*,a) S f/2 all A, then S St all those t.
Proof. For any round I, we assume A, at (the other case A, = ag is analogous). The agent selects of indicates that
(3..a)) + + a;) + d + yr-
By rearranging the above, we have yt S (3,, a) -a?). We use the assumption to get
y/ S (5c. af at) S (s at ag)) +
Dividing the above by |la] - af]
on both sides, we have
s" af af |a! afl
3/+
+ |aa aZll = xz) + laa! af
||a -a2l
Based on the update rule, we have 8 E S141. As this holds for each I, the proof is complete. Lemma G.4. If Algorithm breaks at round and the condition Lemma G.3 holds, then
max width(S,, u) S 32de where A= {=: 12:2=2= y such that x + y A}.
Proof. At each round t, if index is selected, then width(S, xτ) s 2- hence the index i well-defined. When the algorithm breaks, we have
We note that Lemma G.3 gives that s* E S, and
2
S 4 ||a
afll
21
Sd
which immediately leads to
4 a|at at || -1 2 width(S,,,.))
As s. = ||a - a2ll (at - az), multiplying ||at - ag || on both sides gives width(S,, at - at) S 32de. Recall the definition of A and the way to picking at of from Algorithm 8, and thus the proof is complete.
Lemma G.5. Suppose & holds. If Algorithm 8 runs in phuse m and the input satisfies (&. s a) 1 6/2 all a E A and all t that the algorithm runs in this phase, then it lasts at most O ldgo (de))) rounds.
Proof. From Lemma G.3, s E St for all t, and thus Vol(S, + B, 2 Vo, = 2 Vol Whenever index i is chosen, VSl(S, + B) decreases by a constant factor, which implies that an index i can be picked at most (1/log(1/2))) times.
Then, we claim that any index that does not incur break, must satisfy x < (2e)-1 and < (log2(4d/e)) We prove this by contradiction. Assume the algorithm picks index i with 2, 1/(2)) and does not break. In this case, have 2 de <
4c
which forms a contradiction.
offl
Rearranging कं < (2c) yields < most
Therefore, the total number of round that the algorithm will last is at
o
Σ
(ogg(z]))
50
Σ
dlog(1/e)
s 5 Odlog" (d/)g)
(4d/cc)
(5[logg (4d/c)]
which completes the proof.
45

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Lemma G.6. Suppose that occurs. For all phase m, all a E A and all E T
Ta (t).
Proof. Notice that since every target bad arm a will be assigned with incentive ma(t) 2d + T-1, and x1()) A (St, b a) < A A |e ||b all 2d. have (a( (L) for all T
We then prove the claim for all active arms by using induction on For the base case and all E m. (t) = 2d + T-1, From the same analysis for bad arms, the claim holds for m = 1.
1. In this case, for all Am
Assume that the claim also holds for phase m 1 2 1, and then we prove the claim for phase m. In what follows, we focus on those rounds E Tm... For shorthand, let
E argmax (5t, a).
aEA
If Ta (t) 2 then, we have (t(t)= (t) by the same argument used to prove for bad arms. Thus, we assume that (t( & +
By the definition of E, for any round I in phase m 2 2:
4KT
max aEA
,
max aEA
2 |allu,- log
5
[KK
max aE.A
2 ||aa| m1/0-
log
8
dlog (4KT6-1)
(48)
min min(Tm(()11 (d)
1))
2/3
m(0)1
where the first inequality uses the definition of &, the second inequality holds due U2 2 Vm(t)- and the last inequality follows from the induction hypothesis that each a E A is played for E Tm We further show that for all rounds t E T...
(t) - (t)
max (Cm(t), a) + (1+ 32d)).m mm()) (t) BEA
(3t, 21 - a)
T
1
2 (Cm(t); 2t - aa + +(1 (1+33d)) m()) +
(8e, 2t - a)
T
1
2 (Cm(t); 2 - a) + (1 (1+32d)en (m())) (
((s* 2x a) + (m)())-)
T
1
(Cm(t) - -8", - a) + 32d +
T
1
2 -22de + 32de 32dem m() + T mm(())
1
T
where the first inequality uses the definition of 2, the second inequality uses Eq, (48), and the last inequality uses Lemma G.4 with <m(()-1 (the condition to invoke this lemma checked by Eq. (48)). Once the induction is done, we complete the proof.
Lemma G.7. Suppose & holds. For all E [T] with m(t) 2 2,
max (0g - = aa}l S mm(()-1 A
46

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
Proof. With Lemma G.6 in hand, repeat Eq. (48) for all m(() 2 2 to complete the proof.
Lemma G.8. For all m 2, all a E and all E T
[t) - mmax ($e, b) (s,aa) $ (2 + 64d) Em(t) - T
BEA
Proof. be E argmax (cm(t)) b), E argmax (ge, a), and m(t) be the phase that round & lies in. One can show
(t)
max ($t, b) - -ss" hEA
1
max (Cm(e), - a) + +(1++1+1 +11 +m2))mm()) bEa
mm T
(Bt, 22) + (0"
I (Cm(t)) bt -)) (1+ (m)))) + T
(st, be) + (s"
1
S (Cm(t) s",b - a) + (2 + 32d) mm(1)1 T
1
$ (2 + 64d) Cm(t) -1 + T
where the first inequality uses the definition of 2,, the second inequality holds due to & and the last inequality uses Lemma G.4 with -1
G.S. Lemmas for Elimination
Lemma G.9. Suppose that occurs. For every phase m, a" Am
Proof. We prove this by induction on m. Obviously, the base case holds. Suppose that the claim holds for phase m and we consider phase m + 1. By the definition of E, for any phase m
4KT
dlog (4KT5-1)
Va E Am 10mm - v²' a>) & $ 22laall=m log
I 2
S Cm:
(49)
Tm
where the second inequality uses Lemma G.6 which gives that each active arm a will be played for [pm (am{m) times. We have for each E A.
0 (v" 8* s²,""" a- -
(im + s* a- - a) + 2em
(um + 6n a- - a) + (8* cm, a" a) + 20m
S (Dm em. a² a) + 32de + 2cm:
where the second inequality follows from Eq. (49) as well as the induction hypothesis a* E Am and the last inequality uses Lemma G.4 with Cn- To use Lemma G.4, we needs to verify the condition. By the definition of &, for any round in elimination period:
4KT 8
max
18t ss.aa)) a") AEA
max aEAA
2 ||aloo log
[4KT
max aE
2 2||a||y
log ml)
dlog (4KT8-1
22
(50)
min min(Tm (4KT (00(444TT6)))//// 11) m())
47

---

Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents
where the first inequality follows from the definition of &, the second inequality uses Lemma G.6, and the last inequality holds due Vitt) EoEAm P (m) aa and Vm(()) EbEB.. (m(a)bb where Un (a) [wm (4 T
This inequality implies a" E Am+1. Once the induction done, the proof is complete.
Lemma G.10. Let ma be the smallest phase such that Aa (9 + 64d)em.. Suppose that & occurs. For each arm with Aa > O, it will not be in Am for all phases m Z ma + 1.
Proof. Consider any arm a with Aa > O. We only need to consider a E Am, and otherwise, the claim naturally holds. One can show
max (Cm, + Dma, b) - (Cm, + Dma, a) -77 + (7+3 32d)mmm
Ama
(mma + D a²) - (cmm + +Dmmg - (7+22))m..
(cmo +v², aa)) (cmo V² ,0) -99 32d)
(s" + v=v""" a," a) (s" Cm, a a) + 32m2))mm
A. (9 + 64d)cma
0,
where the first inequality follows from Lemma G.9 that a* Am_ the second inequality holds due to Eq. (49), and the third inequality uses Lemma G.4 with = c. (the condition to use Lemma G.4 is checked in Eq. (50)). According to the elimination rule (see climination period in Algorithm 7), arm will not be in phases m for all m 2 ma + 1.
48


Reviews:
[{"review_id": "qZt9JGc7Cr", "reviewer": "Reviewer_RBF5", "summary": "This paper studies the problem of principal-agent interactions with self-interested agents. Different from previous studies like Dogan et al.(2023a, 2023b) and Scheid et al. (2024b), this paper assumes an empirical mean maximizer agent behavior model rather than true mean maximizer. The authors’ elimination framework and search algorithms are novel, efficiently handling uncertainty from greedy agent learning with iid rewards while achieving strong regret bounds. The authors also extend their algorithm to exploratory agents and linear rewards and show strong regret bounds under those settings as well.", "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 the valuable feedback. Below we address your concerns.\n\n---\n**W1:** I think the outperformance of soft $O(T^{11/12})$ is not a fair comparison, since their regret is defined with respect to different behavior models, i.e., true mean versus empirical mean.\n\n**A1:** We would like to clarify that the comparison with the $O(T^{11/12})$ regret bound (Dogan et al., 2023a), as well as others in Table 1, **is indeed fair** because they can all be evaluated under the same behavior model and regret definition. Specifically, our behavior model generalizes theirs: by letting the agent always receive the constant reward equal to the true mean (as noted in Remark 2.2), our model reduces to theirs. In this case, the empirical mean becomes the true mean, ensuring that the regret definitions and behavior models align. Thus, our comparisons are fair.\n\n---\n**W2:** If we compare regret under different models, then it seems the proposed Algorithm 7 performs worse than C-IPA Scheid et al. (2024b) under the linear reward model.\n\n**A2:** As mentioned in A1, regret bounds can be fairly compared when the models and regret definitions align, particularly when one model strictly generalizes another. Our setting is strictly more general than that of Scheid et al. (2024b), as their oracle-agent model is a special case of our learning agent framework. While our regret bound is indeed worse when restricted to this special case, our algorithm is designed to work in the broader and more challenging learning agent setting which is not addressed in Scheid et al. (2024b).\n\n---\n**W3:** The \"significantly improve\" claim remains unsubstantiated in practice without empirical comparisons.\n\n**A3:** We thank the reviewer for this suggestion. Our primary focus in this work is on theoretical improvements in the order of the regret bound (improving from $O(T^{11/12})$ to $O(\\sqrt{T})$ in exploratory oracle-agent setup). As such, this version does not include experiments. We do agree that empirical evaluation is a valuable direction and plan to pursue it in future work.\n\nNonetheless, we would like to highlight several practical advantages of our algorithm compared to Dogan et al. (2023a), particularly in terms of implementation:\n\n- **Computational efficiency.** Their algorithm solves a linear program at each round, with the number of constraints growing linearly in $t$, leading to increasing runtime. In contrast, our Algorithms 5 and 6 only require simple arithmetic operations per round, resulting in much greater efficiency. \n    \n- **Memory usage.** Their method stores all past incentives and actions, resulting in memory usage that scales with $t$. Our algorithms avoid this by maintaining only a few counters or estimates, ensuring constant or sublinear memory usage.\n    \n- **Hyperparameter tuning.** Their algorithm requires two hyperparameters that must be carefully tuned. Our algorithms, by contrast, only require a standard confidence parameter $\\delta \\in (0,1)$, which typically does not require fine-tuning in practice.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "n/a.", "theoretical_claims": "I did not check the correctness of proofs.", "experimental_designs_or_analyses": "n/a.", "relation_to_broader_scientific_literature": "This paper is related to the literature of principal-agent bandit games.", "essential_references_not_discussed": "I did not notice any essential reference not being discussed.", "other_strengths_and_weaknesses": "On the positive side, this paper considers a learning approach to learning the near-optimal/no-regret principal policy in principal-agent bandit games. I found the problem presented by the paper interesting, and relevant. In general, this paper proposed an innovative research topic.\n\nOn the other hand, I think the outperformance of soft-O(T^{11/12}) is not a fair comparison, since their regret is defined with respect to different behavior models, i.e., true mean versus empirical mean. If we compare regret under different models, then it seems the proposed Algorithm 7 performs worse than C-IPA Scheid et al. (2024b) under the linear reward model.\n\nWhat is more, besides the unfair comparison to prior work (e.g., Dogan et al., 2023a) due to different agent behavior model, the \"significantly improve\" claim remains unsubstantiated in practice without empirical comparisons. This paper is missing comparable algorithms to validate its performance, I wonder maybe if some naive heuristic strategies can perform well in practice.  Even simple synthetic experiments would strengthen its claims, and provide more insights for the algorithm's performance improvement.", "other_comments_or_suggestions": "n/a.", "questions_for_authors": "n/a.", "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": "GFCU8UppRQ", "reviewer": "Reviewer_YpW5", "summary": "This paper studies the bandit principal-agent problem, where a principal tries to incentivize an agent playing a bandit instance so as to maximize their own cumulative reward. It extends the previous works of Scheid 2023 and Dogan 2023 by considering an agent who selects the arm based on *empirical* reward means. It covers both the i.i.d reward case and the linear reward case, with agents either self-interested (that is, greedy) or exploratory.\n\n## update after rebuttal\nI thank the authors for having clarified the validity of definition 2.1. I think the revised version of the article should feature the general version of definition 2.1 with the constants (a,b) (as explained by the authors in their reply) rather than just the special case (a,b) = (1/2, 1/2); as well as the discussion about the algorithms satisfying def 2.1. \nI keep my score unchanged because I still think def 2.1 is slightly restrictive, but I'm convinced by the overall quality of the work.", "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 the valuable feedback. Below we address your concerns.\n\n---\n**W1:** It seems that this paper employs many technics from these papers (Dogan et al., 2023a) and (Scheid et al., 2024b) without bringing a lot novelties from a mathematical point of view (except using online elimination and MSP).\n\n**A1:** Here, we clarify that our techniques and analysis are **significantly different** from those in Scheid et al. (2024b), and **entirely distinct** from those in Dogan et al. (2023a).\n\n- **Comparison with Scheid et al. (2024b).** While Scheid et al. (2024b) use a standard binary search in an oracle-agent setting, we propose a noise-robust variant (Algorithm 3) specifically designed for the more challenging learning-agent setting. This is a non-trivial extension, as optimal incentives in our setting are time-varying—they depend on the agent’s evolving internal estimates. The search procedure must therefore be robust to fluctuations introduced by the agent’s learning process. Algorithm 3 is carefully designed to address these issues and is supported by a detailed analysis (see Lemma 3.1).\nWe also introduce a novel elimination framework tailored to learning agents. Unlike traditional methods (e.g., Even-Dar et al., 2006), our algorithm does not permanently eliminate suboptimal arms but continues to play them moderately to stabilize the agent’s estimates. This is essential to avoid linear regret, as discussed in Section 3.3. In contrast, Scheid et al. (2024b) do not face these challenges, as agent responses in the oracle model are fixed for a given incentive.\n     \n- **Comparison with Dogan et al. (2023a).** Our algorithms (Algorithms 5 and 6 in Appendices F and G) are fundamentally different from those of Dogan et al. (2023a). Their approach relies on an $\\epsilon$-greedy strategy and explicitly estimates the agent’s model by solving an optimization problem at every round.\nIn contrast, our approach is built around a **newly developed, novel** online elimination framework that **does not require** estimating the agent’s model. As noted in our response to Reviewer RBF5 (see W3 and A3), such estimation would incur significant computational and memory costs. A key innovation is our probabilistic amplification technique (see Section 4.2, also Algorithms 5 and 6), which ensures robustness to the randomness induced by the agent’s exploratory behavior. This technique supports two central components of our algorithm: **incentive testing** and **trustworthy online elimination**. Specifically, incentive testing refers to the process of identifying reliable incentives in the presence of agent learning, while trustworthy elimination ensures that, with high probability, the elimination process is not disrupted by exploratory actions of the agent.\n\nWe believe that the techniques developed around probabilistic amplification offer a robust and flexible foundation for principal-agent interactions with learning agents, and may inspire further exploration in related dynamic settings. \n\n---\n**W2:** Presentation of Algorithm 1 and introducing $\\pi^0$ earlier.\n\n**A2:** Thanks for your suggestions. We will make sure to polish up our presentation according to your suggestions in the next version.\n\n---\n**Q1:** Is assumption in definition 2.1 satisfied by classic bandit routines, such as UCB or Thompson sampling?\n\n**A:** Thank you for the insightful question. UCB does not satisfy Definition 2.1, as it continues to explore suboptimal arms indefinitely rather than decaying exploration over time. Whether Thompson Sampling satisfies the definition is unclear and may warrant further study. Since our focus is on designing principal algorithms for agents satisfying Definition 2.1, characterizing which other bandit algorithms meet this condition is beyond the scope of this work.\n\n---\n**Q2:** Unclear why considering a vector of incentives rather than just a scalar incentive on one arm at each round (just as in Scheid 2024b) is better. What are the advantages of this approach, given that the agent only pulls one arm at a time?\n\n**A:** Incentivizing multiple arms is critical for our online elimination process as detailed in Section 3.4 (and its robust version for exploratory agent). Specifically, when conducting elimination at round $t$, the principal needs to compare $\\hat{\\theta}_a(t)+\\hat{\\mu}_a(t)+\\epsilon$ against the empirical maximum $\\max_b \\hat{\\theta}_b(t)+\\hat{\\mu}_b(t)$ over all active arm $a$, where $\\epsilon>0$ is an error specified by the algorithm, $\\hat{\\theta}_a(t)$ is the principal's estimate and $\\hat{\\mu}_a(t)$ is the agent's estimate. Since the agent's estimates are unknown to the principal, the principal is unaware of which active arm achieves empirical maximum. To address this, the algorithm incentivizes every active arm $a$ by $\\hat{\\theta}_a(t)$ at round $t$. By doing this, the algorithm indirectly compares $\\hat{\\theta}_a(t)+\\hat{\\mu}_a(t)+\\epsilon$ against empirical maximum by observing the played arm.", "claims_and_evidence": "The claims in the paper are appropriate, clear and supported by strong theoretical guarantees. The rates in the regret bound are consistent with existing literature, while derived under a less stringent assumption regarding the agent's behavior.", "methods_and_evaluation_criteria": "There is not experiment supporting the results. This is not a problem to me, as the theoretical results seem strong enough.", "theoretical_claims": "I did went the correctness of the proofs in the appendix.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "I find the discussion about the existing scientific literature very satisfactory. While the number of references is relatively low (I counted 32), this is understandable given that that principal-agent bandit games are a fairly new topic of research. The authors made a clear efffort to compare their results and assumptions with the two closest papers, namely Scheid 2023 and Dogan 2023. I particularly appreciated table 1, which gives a clear overview of these differences.", "essential_references_not_discussed": "I do not think of any essential reference not discussed by the authors.", "other_strengths_and_weaknesses": "STRENGHTS:\n\n- The results are interesting. The authors manage to match the existing bounds on regret (or with a slightly degraded rate, such as in the contextual case) while working under a less restrictive assumption for the agent.\n\n- The paper is precise and well written. I particularly appreciated the effort to intuitively explain the steps of the algorithms, as well as the additional discussions in the appendix. \n\nWEAKNESSES:\n\n- While considering  an agent that compares empirical means rather than theoretical means is an improvement over Dogan (2023) and Scheid (2023), it seems that this paper employs many technics from these papers without bringing a lot  novelties from a mathematical point of view (except using online elimination and MSP).\n\n- The pseucode of algorithm 1 is a bit hard to parse.", "other_comments_or_suggestions": "- The definition of pi^0 should be introduced earlier in the paper, as it appears in the pseudo code of algorithm 1 without having been defined beforehand.\n- The pseudo code of algorithm 1 could be clearer. For instance, in each phase m, it is not clear that the first Z_m rounds are dedicated to stabilizing estimators, then next T_m ones to determining optimal incentivizes: there could be an ambiguity about whether these rounds overlap.", "questions_for_authors": "- Is assumption in definition 2.1 satisfied by classic bandit routines, such as UCB or Thompson sampling? \n\n- It is not clear to me why considering a vector of incentives rather than just a scalar incentive on one arm at each round (just as in Scheid 2023) is better. What are the advantages of this approach, given that the agent only pulls one arm at a time? \n\n-", "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": "Oc85m9fa1b", "reviewer": "Reviewer_YgEB", "summary": "The paper studies a principal-agent bandit game where the principal first provides an incentive, and then the agent selects the arm based on estimation and the provided incentive. The authors propose a novel elimination algorithm for the i.i.d. setting and the linear bandit setting. The corresponding regret upper bounds are $\\sqrt{T}$ and $T^{2/3}$. The algorithm's regret outperforms that of Dogan et al 2023.", "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 the valuable feedback. Below we address your concerns.\n\n---\n**W:** I understand that the paper is of theoretical nature, but I believe that the paper can benefit from experiments on simulated data and real-world data.\n\n**A:** Thank you for the suggestion. We do agree that experiments could provide additional value. Please see our response to Reviewer RBF5 (W3 and A3)\n\n---\n**Q:** I'm confused of the annotation in Table 1 \"worst-case bound......enjoys a gap-dependent bound\". What are the gap-dependent bounds? Are they logarithmic of $T$ ?\n\n**A:** The gap-dependent bound we refer to is of the form $O ( \\sum_{a \\in [K]: \\Delta_a>0}\\frac{\\log T}{\\Delta_a})$ where $\\Delta_a := \\max_{b \\in [K]} \\\\{\\theta_b + \\mu_b\\\\} - (\\theta_a + \\mu_a)$ measures the suboptimality gap of arm $a$ in the oracle-agent setup.\nAs noted in the footnote of Table 1, Scheid et al. (2024b) obtain a similar gap-dependent regret bound, but only under the oracle-agent model. In contrast, for the more general learning agent setting, whether such a bound can be achieved remains an open question (see the discussion below Theorem 3.4). Intuitively, we are pessimistic about this possibility, as it appears necessary for the algorithm to continue sampling suboptimal arms in order to stabilize the agent’s internal estimates and reduce the estimation error of the optimal incentive (see Section 3.3 for a more detailed discussion).", "claims_and_evidence": "The paper proposes elimination algorithms with detailed analysis on the regret upper bounds. From my level of understanding, I do not find big issues in the analysis.", "methods_and_evaluation_criteria": "Table 1 provides detailed regret comparison for different algorithms along with underlying assumptions, which makes a convincing point that the proposed algorithms outperform previous algorithms.", "theoretical_claims": "I have not checked correctness of all proofs.", "experimental_designs_or_analyses": "The paper does not have experiments.", "relation_to_broader_scientific_literature": "The principal-agent bandit game is well motivated in the introduction with a good example. Previous papers on this topic usually assume that agents have access to true means, while this paper along with Dogan et al. 2023 bridge the gap without the assumption.", "essential_references_not_discussed": "I'm unfamiliar with principal-agent bandit games so I'm unsure whether essential references are missed.", "other_strengths_and_weaknesses": "Strengths:\nThe proposed elimination framework with searching is novel and balances a good tradeoff between exploration and exploitation in the problem. Compared with Dogan et al. 2023, the algorithm outperforms in terms of regret upper bound.  \n\nWeakness:\nI understand that the paper is of theoretical nature, but I believe that the paper can benefit from experiments on simulated data and real-world data.", "other_comments_or_suggestions": "I do not have other comments.", "questions_for_authors": "I'm confused of the annotation in Table 1 \"worst-case bound......enjoys a gap-dependent bound\". What are the gap-dependent bounds? Are they logarithmic of $T$?", "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 4 reviewers appreciated the novel setup and developed approaches about the paper, which studies principal-agent framework for online learning. There is some concern during the discussion about agent's behavioral modeling and lack of experiments, but overall the reviewers are all positive about the contributions of this paper. Hope the authors could take into account various useful comments from the review process to improve the paper in its next version, but overall this paper is a great addition to ICML!
Decision: Accept (poster)