Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition
Authors: Zichen Wang
Chuanhao Li
Huazheng Wang
Venue: ICML 2025 poster (2025)
Keywords: Online information acquisition
multi-armed bandits
principal-agent game
Primary area: theory->game_theory
TL;DR: We investigate the problem of identifying the optimal scoring rule within the principal-agent framework for online information acquisition problem.

Abstract: We investigate the problem of identifying the optimal scoring rule within the principal-agent framework for online information acquisition problem. We focus on the principal's perspective, seeking to determine the desired scoring rule through interactions with the agent. To address this challenge, we propose two algorithms: OIAFC and OIAFB, tailored for fixed confidence and fixed budget settings, respectively. Our theoretical analysis demonstrates that OIAFC can extract the desired $(\epsilon, \delta)$-scoring rule with a efficient instance-dependent sample complexity or an instance-independent sample complexity. Our analysis also shows that OIAFB matches the instance-independent performance bound of OIAFC, while both algorithms share the same complexity across fixed confidence and fixed budget settings.

Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition
Zichen Wang' Chuanhao Li
Huazheng Wang?
Abstract
such consumer preferences competitive dynamics, that influence the strategy's potential. The manager first designs a scoring rule S and announces it to the expert. The expert investigates w by selecting a research method (action k), which incurs a cost Ck- The expert chooses the research method that maximizes its expected profit, i.e. the method that maximizes S(ō, w) Ck. where ((ā,w) w) represents the payment from the manager based on the accuracy of the report. After performing the selected method, the expert ob- serves the outcome and produces report ô. The manager then uses á to make an investment decision d (e.g.. imple- menting the proposed strategy). The utility the manager u(w, d) is determined based on the true state w and d.
We investigate the problem of identifying the opti- mal scoring rule within the principal-agent frame- work for online information acquisition problem. We focus on the principal's perspective, seeking to determine the desired scoring rule through in- teractions with the agent. To address this chal- lenge, we propose two algorithms: OIAFC and OIAFB, tailored for fixed confidence and fixed budget settings, respectively. Our theoretical anal- ysis demonstrates that OIAFC can extract the de- sired (c, -scoring rule with efficient instance- dependent sample complexity or an instance- independent sample complexity. Our analysis also shows that OIAFB matches the instance- independent performance bound of OIAFC, while both algorithms share the same complexity across fixed confidence and fixed budget settings.
While most existing research (Neyman et al. 2021 Li et al.
2022 Hartline et al. 2023) focuses on designing optimal scoring rules in offline settings, relatively little attention has been given to the online scenario, where the principal seeks to achieve learning objectives through repeated interactions with the agent. To the best of our knowledge, only two prior studies have explored the online information acquisition problem (Chen et al.) 2023 Caceiamani et al. 2023). How- ever, these studies primarily focus on regret minimization from the principal's perspective, aiming to reduce cumu- lative regret from sub-optimal decisions. A less-explored aspect is best scoring rule identification (BSRI), where the principal's 's goal is to identify an estimated optimal scor- ing rule that maximizes expected profit through repeated interactions.
1. Introduction
The information acquisition problem, framed within the framework of the principal-agent model (Laffont & Maskin
1981), studies how a principal hires an agent to gather criti- cal information for decision-making processes (Oesterheld Conitzer 2020 Neyman et al.) 202T). In this setup, the principal relies on the effort and expertise of the agent to provide high-quality information. Consider strategic inter- action between manager (principal) and a domain expert (agent). The manager is tasked with evaluating the suit- ability of an advertising strategy for a given market. The effectiveness of this strategy depends on an uncertain un- derlying factor, which we refer to as the environment state w. This state could represent characteristics of the market,
Chen et al. (2023) presents iestance-independer BSRI re- sults for their algorithm in the fixed-confidenc setting (see Corollary 4.4 in Chen et al. (2023) They show that their algorithm can identify an (c, ò) o'-ottmall scoring rule using Ô OC& samples, where represents the number of the agent's actions, and Co denotes the total number of pos- sible observations. However, this sample complexity is rela- tively higher than that of standard best arm identification al- gorithms for multi-armed bandit problems (Even-Dar et al., 2002. Kalyanakrishnan et al. 2012), which typically require only O(Ke samples. Moreover, no instance-dependent results are currently available for fixed-confidence BSRI, where the sample complexity upper bound would depend on the expected profit gap between the optimal and sub-optimal
'Department Electrical and Computer Engincering and Coordinated Science Laboratory, University of Illinois Urbana- Champaign, Illinois. USA 'Deparmment of Statisties and Data Science, Yale University, Connecticut, USA "Shoool of Electronic Engineering and Computer Science, Oregon State University, USA. Correspondence to: Zichen Wang <zichenwó edi..
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Principal-Agent Information Acquisition
actions (research methods). Additionally, the fixed-budget setting of BSRT also remains unexplored, leaving open ques- tions about performance in scenarios with limited sample availability.
the agent to pull the desired arm. This complication requires to learn the response region of arm k (will be introduce in the following sections).
Based on the above observation, we address the BSRI prob- lem and build upon the setting and results presented in Chen ct al. (2023). We introduce two algorithms: OIAFC for the fixed-confieence setting and OIAFB for the
Online learning in strategic environments. Our problem falls under the topic of online learning in strategic environ- ments, In this category, the online learner's 's reward in each round is influenced by their actions (such as the scoring rule in our paper) as well as the strategic responses of other players (such as the agent in our paper) in repeated games. These repeated games are grounded in influential economic models, including Stackelberg games (Sessa et al. [0200] Balcan et al.]
set- ting. We introduce new trade-off parameters af' along with breaking rule and parameter St. as well as a decision rule. These innovations ensure that we achieve (c. oppttmal scoring rule while maintaining an instance instance-dependent sam- ple complexity upper bound. To the best of our knowledge, our results are the first instance-dependent results for the online information acquisition problem. The contributions summarized as follows:
2015; Haghtalab et al. 2022). auction de-
sign (Amin et al.
2013
Feng et al.] 2017 Golrezaei et al.
2018 Guo et al.
2022). matching (Jagadeesan et al. 2021]
contract design (Ho et al.) 2014 Cohen et al.
2022 Zhu
et al. suasion (Castiglioni et al., 2020
2022 Wu et al. [024]] Zuo
2224a b). Bayesian per-
OIAFC identifies the (c, opptimal scoring rule with an depennetde sample complexity upper bound of Ô [M (Eizk- 4, + + in the fixed- confidence setting, where AG represents the profit gap, and M < K x Co. We also demonstrate that in a sim- ple setting, OIAFC's instance- destencedeepedent result aligns with the known instance dependent outcomes for the fixed-confidence best-arm identification problem in multi-armed bandits.
2022
2021: Bernasconi
et al. 2022 2023] Gan et al.
2021: Zuu et al.
2021 Wu
ct al. 2022: Agrawal al., 2024 Bacchiocchi et al. 2024).
principal-agent games (Alon et al. 2021 Han al.
2024
Ben et al. 2024) Ivanov et al. 2024 Scheid et al.
2024 Chakraborty et al.). Chen et al. (2023) presented
the first study on online information acquisition, primarily focusing on the regret minimization problem. They also
proposed a fxxe-coofiieecc result for best scoring rule iden- tification, but their sample complexity upper bound is loose and instance independent.
OIAFC identifies the (epttmml scoring rule with an instance-independent sample complexity upper bound of Ó ((M in the fixed-confidence setting, which improves the result proposed by Chen et al. (2023). This result aligns with the known instance- independent result for the fixed-confidence best arm identification problem in the MAB.
Best scoring rule. Our problem is also related to the topic of offline optimal scoring rule design. Previous studies have made different assumptions regarding the number of states and action numbers. Some prior works ([Neyman al., 2021 Hartline et al.] 2023)) assume there are only two possible states. In contrast, our paper allows the number of states to be any finite number 2 2. Similarly, some previous studies (CChen & Yu, 2021 Li ct al., 2022: Papireddygari & Waggoner (022 assume the action number is K 2. In our work, we allow K to be any finite number 2 2. Additionally, while all the papers mentioned above model the state exogenously given, our paper allows for the prior of the state to potentially be influenced by the agent's s actions (Chen et al. 2023).
The OIAFB algorithm, consistent with the instance- independent results of OIAFC, identifies an (c, optimal scoring rule, given a budget of T Ó(MKe-))
2. Related Work
Best arm/policy identification.
Best arm identification in
bandits (Manno&& & Tsitsiklis 2004
Even- -ar et al.) 2006
Bubeck et al. 2009: Gabillon et al.
2011 Kalyanakrishnan
ct al.) 2012: Gabillon et al. 2012; Jamieson et al.] 2013
3. Preliminaries
Garivier & Kaufmann 2016 Chen et al. [0166] Wang et al.
2023 Azize et al.) (024) shares similar goal with our prob- lem: finding optrmoptimal arm (scoring rule) with minimal sample complexity. The smaller the sample complexity, the better the algorithm's 's performance. However, one of the key differences between our setting and theirs is that we cannot directly pull an arm (Chen et al.) 2023] Cacciamani et al.] 2023): ; instead, we must use the scoring rule to incentivize
Notations. In this paper, we define log(-) as the natural logarithm, log2(-) as the binary logarithm, R* the set of all positive real numbers, N+ as the set of all positive integers, A(?) as the probability simplex over Ω and [t] = (1,2,... t}. Additionally, we use a = O(b) to indicate the existence of a constant d' such that e'b 2 a, and use Ô to suppress -ogaritigi factors.
2

---

Online Principal-Agent Information Acquisition
3.1. Online information acquisition model
The agent organizes group of investigators conduct face-to-face surveys on the street, where each distinct type of survey rep- resents specific action. The principal can require that some of these investigators include trusted employ- ees from the principal's ''s company, ensuring that the principal can observe this category of surveys.
Offline In-Person Surveys:
The setting we study was initially explored by Chen et al. (2023). as outlined below.
Interaction protocol. The information acquisition model involes three key components: a principal, an agent, and a stochastic environment. The interaction between these entities in each round proceeds as follows:
In the rest of the Section 2, we will forget the subscript t and introduce the agent's arm selection and belief report- ing policies, along with the decision-making policy of the principal
1. The principal announces scoring rule St Ω x (52) + R
2. The agent selects an action, or "arm", ke from the K- armed set A based on the scoring rule St and incurrs a cost ck, Note that while k₂ is observed by the principal, the cost C₁ is private to the agent.
Information structure. The almighty agent is aware of both fex k== and the observation generation process p(w, olk). With this knowledge. the agent refines its belief a E (1)) about the hidden state using the Bayes's 's rule: o (w) = =p(wlo, kt) = p(w, /p(o)/(( Here, a is a ran- dom measure mapping observations from O to probabilities in AQ)), reflecting the uncertainty in o. Let E C A(2) represent the support of a, and define M as the cardinal- ity of Σ. Due to the discrete nature of A and O we have M < K x Co. We also introduce qu (or E A(E) as the dis- tribution of a based on the agent's choice of action & E A. Since a encapsulates all the relevant information about o, the observation o can be omitted, and { along with {c& k= are referred to as the information structure.
K
3. The stochastic environment generates a state Wi E Ω unknown to both the agent and the principal and sends an observation Og E O the agent based p(wr, ke)
4. The agent submits reported belief o, E A(?) to the principal about the hidden state. This belief helps the principal in learning the stochastic environment. The principal then makes a decision d, E D based on knowledge {St, ô.).
5.
The stochastic environment reveals the hidden state wi. The principal compensates the agent according to the scoring rule (1(,,, 6x) and gains utility u(we, de).
Optimal scoring rule The information acquisition problem can be framed as general Stackelberg game. In this setting, let r S x A(?) x A + 'D represent the principal's 's decision-making policy, while μa S + A and v : S x Σ + (l)) denote the agent's 's arm selection and belief reporting policies, respectively. For any given scoring rule S E S. the agent chooses an arm k = psS) and reports â = v(S,a, k) to maximize its expected profit, which is ex- pressed as g(M, v; S) := E [S (w, (S, o, ((S))) cp(s)] The expectation here accounts for the randomness in both w and according to the distribution gu(S). The principal's objective is to design an optimal scoring rule S and estab- lish a decision policy v) that maximizes its own expected profit, given that the agent will respond optimally with its best strategies (μ²", v.), i.e., h "u",,""; S,n) = El u (w, (S,v" (S, (S,0,,1 (())((( (S)))) S (w, o" (8,0,1"
More details are provided in Section B of the Appendix. We assume the principal selects Sy from the scoring rule set S where || xe I Bg for all S E S, the norm of the utility function Ω x D is bounded by |||||oc S Bu, the arm number, K 2 2, is finite integer which is known to the principal (Chen et al.) 2023), and the observation set O is also finite with Co observations.
Note that, in our setting, the principal can observe the action (c.g., research method) selected by the agent (Chen et al. 2023). The practicality of this assumption will be illustrated through the following example.
Example 1. Suppose the ugent's 's action ki denotes a re- search method or a type of investigation. The principal can design processes to make the agent's 's actions observable. Below are practical examples:
where the expectation con- siders the randomness of ws and o with respect to (s-())- The optimal leader strategies are referred to as strong Stackelberg equilibria, which can be framed as solutions to a bilevel optimization problem, as introduced by Conitzerr 2015): Chen et al. (2023). i.e.,
The agent deploys a web-based ques- tionnaire to gather information, where each distinct type of web-based questionnaire represents specific action. The principal can mandate that the question- naire be hosted on the principal's 's company's 's official website or made easily accessible online, enabling the principal to readily observe the process.
Online Surveys:
max (p",, S.m)) n,E s.t. (²") E arg max g (1, v; S). n.
(I)
3

---

Online Principal-Agent Information Acquisition
To simplify Eq I.. we will introduce the definition of proper scoring rule (Savage 1971). Under this rule, the agent is incentivized to report truthfully (i.e., x o).
probability parameter. The algorithm should find esti- mated optimal scoring rule S E which satisfies
Definition 1 (Proper scoring rule (Savage, (97II). A scoring rule& S E S is considered proper if. for any given belief E ((2) and any reported belief â E (Q2), we have Euwal [S(w, Ø]] & Ewwa [Sw,, o.}. If this inequality is true for any o o, then S is said to be strietly proper.
P ((((St) ((5)) sc) 21 1
(3)
A smaller sample complexity 7 implies better algorithmic performance.
Under a proper scoring rule, the concept of reporting a truth- ful belief is, by definition, the most profitable for the agent. According to the revelation principle (Myerson| 1979). any equilibrium that involves dishonest belief reporting has an equivalent equilibrium involving truthful belief reporting. This implies that the principal's optimal scoring rules can be considered proper without loss of generality (Chen et al.] 2023). allowing us limit the reporting scheme v to the ones that are truthful.
Fixed budget. In the fixed budget setting, the learning al- gorithm should utilize T interactions to derive an estimated optimal scoring rule S* which satisfies
P
2 1-8.
(4)
A smaller error probability 8 iimplies better algorithmic per- formance.
Lemma 1 (Revelation principal (Myerson 1979)). We let S denote the set of the proper scoring rule with bounded norm || < Bg, there exists a S E S that is an optimal solution to Eq (.
Remark 1. The best scoring rule identification problem is
significantly more challenging than the best arm identificu- rion problems in standard multi-armed bandits Even- et al. (2002) and principal-agee -agett bandits bandits[Scheid et al. (2024) In the principal- aagent bandit setting Scheid et al. (2024) the principal's 's objective is relatively straightforward: to incentivize the agent to take a good action, as the agent's 's action directly determines the principal's 's utility. In contrast, our setting introduces an added layer of complexity due to the presence of an underlying state that is unobservable to the principal but directly impacts the agent's 's utility. The principal must rely on the agent's 's report to derive the infor- mation about the state. Consequently, maximizing utility in our setting requires addressing two intertwined challenges: it must incentivize the agent (1) take the optimal action, and (2) trushfully report its belief about the underlying state.
We define& K* = k(S*)) as the optimal response of S*. The proof of Lemma i shown in Section C.1 of Chen et al.] (202)). We here further simplify the notations. The optimal decision policy for the principal 17" can be simplified to d' (o) 17" (S, a, k) since S and k add no information to the
hidden state given a. Similarly, we define (S) =S))),
u(()) = Fa [u(w, d" (a)) and 5(r) = Faw [S(w.,)) We can reformulate the optimization program in Eq as
follows:
(o (8) [u(o)- -[o)]
max SES
s.t. (S) E arg max Ho [S(o) - ck)
REA
Consequently, while the payment rule in Scheid et al. (2024) can be designed solely based on the agent's 's action, the scor- ing rule in our setting instead depends on the agent's 's report. This introduces another layer of difficulty: the scoring rule must not only incentivize the agent to take the optimal action, but also to truthfully report its belief. Hence, identifying the optimal scoring rule in our setting demands more nuanced and sophisticated analysis.
We denote the agent's profit function as g(k, S) :
Eowgu (S(o) - c*j and the principal's 's profit function un- der the agent's optimal response (S))) as h(S) == (o [u(o) - S(r)]. Section 4 we will convert
Eq ( into linear programming that only includes learnable parameters.
3.2. Learning objectives
4. Learning the Optimal Scoring Rule
In this paper, we consider both the fixed confidence setting and the fixed budget setting.
In this section, we demonstrate how algorithms iteratively learn the optimal scoring rule. In Section 4.1] we will sim- plify the information acquisition problem into a bandit-like problem, identifying the key parameters to be learned. In Section 4.2 we will delve into the strategy of learning these unknown parameters. In Section 4.3 we will use the learned parameters to establish the linear program UCB-LPk,, and use it to select the estimated best arm.
Fixed confidence. In the fixed confidence setting, the al- gorithm wants to obtain an estimated optimal scoring rule S" that can satisfy the (e, -condiitoo with a finite sample complexity т.
Definition 2 ((c, --oodiiii,,, We define 0 << <<<52(Bg + Bu) as the reward gap parameter and 0- < 5 <1 as the
4

---

Online Principal-Agent Information Acquisition
4.1. Simplify the information acquisition problem
) We suppose that there is an oracle that can provide the learning algorithm with K K-scoring rules (5kkmm, If the principal announces St. the agent's 's best response is arm k. Moreover, for the agent's 's profit g(k, S), we suppose there exists a positive constant that g(k, Sk) - g(k', Sx) > E. vk' # k.
Assumption 1 (Action-informed oracle Chen et al. (202)),
We first illustrate how simplify the information acqui- sition problem into bandit-liked liked problem. Define V4 {S S g .) 2 g(k', (S), Vk' A} as the region in which the agent takes action h as its best response. The problem Eq ( can be reformulated as
maxh(S?) REA s.t. h(SE) = sup Bo ( S(a)].
(5) Intuitively, equipped with the action-informed oracle, the principal holds the power to induce the agent to select its preferred arm (i.e., announce the corresponding scoring rule). In Section (.2 we will show that we can utilize q'. O" and their corresponding confidence radius to efficiently estimate g and C.
SEV.
where h(S)) represents the principal's maximum profit when the agent's s optimal response is k. and St is the op- timal solution to the inner problem in Eq ( If the prin- cipal is aware of V&, Ok and the pairwise cost difference C(K, k') = Ck- - cv, the inner problem of Eq (5) can be solved by the following linear programming LPx
4.2. Learning belief distributions and pairwise cost differences
LPk: : (($))= = max us- - us( (k) SEB
= 1[k: = F} denote the total count of times the agent selects arm ic before round t. For all k E A, we define the empirical estimator of qu as
(6)
s.t. ug (k) (k)) 2 k(k,k', Vk A,,
where (k) = (S(.). 9x. (.)) denotes the expected pay- ment of scoring rule S if the agent takes arm k and ug- (u(-), 9k ()),; denotes the expected utility if the agent takes arm k. The information acquisition problem is simplified to bandit problem, where A is the K K-armed set and h(5)) is the reward of the arm. However, the region VR. the brief distribution qs and pairwise cost difference C(k, k') are unknown to the principal. Therefore, the principal needs to learn this information. Recall the definitions of V4 and g(,, 5): V2= = {5 SI (qu qke, 5) C(K, K), Vk E AJ. To identify Vn. we just need to estimate the belief distri- bution q& with estimator o and the pairwise cost difference kk) = Ck- Ct' with estimator Č¹ (k)) Note that estimator Oo can be updated using the following identity
1-1
(0)
Σ 1o, -o, k E. (8) = NE
We define the confidence radius for belief estimator dh as
2 log( 1og(4K2MM2/4)
Fixed Confidence I,(1)) =
(9)
No
Fixed Budget [k V N/
(10)
where the definition of parameter a will be provided in Theorem 2 We define the estimated payment of scoring rule S if the agent responds by taking arm as (k) (S(.). d (.)s. Besides, we define the estimated utility if the agent takes arm k as i (u(.). ())))
C(k, k') us (k)) (k'),, VS E V4 n Vir,
where we can replace the qb in (k) with o Furthermore, we need to find scoring rule S that belongs to V4 n Vv to use Eq 77) effectively. To achieve this, we utilize a bi- nary search approach on the convex combination of Si and S2, where k= (Si) k and k*(S)
The definition of the pairwise cost difference estimator Ö' (k: K') and its confidence radius (k, k') are shown in Section C in the Appendix. By the following Lemma we show that Es and C(k, K') can be successfully learned with high probability.
k. Besides, we aim to inform the principal about the K arms and ensure they can find a scoring rule S such that k (S) = k for binary search. To achieve this, we introduce the action-informed oracle, This oracle provides the principal with K scoring rules $,,..., Sx such that ks (5x) = k. This assumption is also adopted by Chen al.) (0023) where they demonstrated the practical implementation of the action-informed oracle (see Example 3.4 and 3.5 in Chen et al. (2023). Further- more, they presented a hard instance in which no learning algorithm can identify the scoring rule that triggers the best arm without the action iettooninffomed oracle (Lemma 3.2 in Chen et al. (203)).
Lemma 2. Define event & = {llat qulli S 12(K). Vt e [r]. Vk- E A). E will occur with probability at least when (((k) is defined in the fixed confidence style Eq (9) and with probability at least
T TK2M (if 0 < TM < 1) when defined in the fixed budget style Eq (10). Furthermore, under the occurrence of event E, we have:
(k)( -b((k)] S BsI, Ak A, S 10% - uu! S (1)) Vk A, IC(, R²) - C'(1,, s k'), V(k,k).
5

---

Online Principal-Agent Information Acquisition
4.3. Solving for the optimal scoring rule via UCB-LPRg, k.t
the algorithm employs a conservative scoring rule S. akp Sk; + (1 o ) After receiving the agent's feed- back, the algorithm checks if further exploration is needed. If the agent chooses k, # kç it suggests that the estimate of Va; is not accurate, prompting a binary search (details can be found in Algorithm 3 in the Appendix) to refine the estimate. Conversely, ke kig. this suggests a satisfac- tory estimate of Ve;, and the algorithm proceeds to check the stopping condition. If ( (k;)) I Be holds, the exploration halts, returning S = St as the estimated optimal scoring rule.
Rewriting the LP (6) by replacing q and C with their esti- mations g', C* and incorporating their confidence radiuses,
we obtain
UCB-LPRA
hig = = at + Ba v SES
s.l. 10- (k((=)] - Bs (k)
(K) > (k, - (kk(k + (k), AK tk.
In UCB-LPR,t, we employ igg to provide a high- probabiiyyy upper bound on the true value of h(Sī), as demonstrated in L in the Appendix. Through the linear programming described above, we can derive the estimated value ft, and scoring rule Sk., for arm h in round t. In cases where UCB-LPkat is infeasible, we set htg = oi. (5()s) + (Bu, (k)) and St.t =S..
In the following sections, we will illustrate the insight be- hind the design of Algorithm [ and establish upper bounds for normal exploration rounds Σi= lkk, = };} and forced exploration rounds Σi=1 like + k in Lemma 3 and Lemma _ respectively. Finally, by utilizing Lemma 5 we demonstrate that OIAFC successfully identifies the esti- mated best arm that satisfies condition Eq (3). Combining these results, we can prove that OIAFC outputs an estimated best-scoring rule that satisfies Eq (3) with a near-optimal sample complexity (shown in Theorem D).
5. Learning Algorithms
5.1. Online information acquisition fixed confidence (OIAFC)
Sampling rule. In each round, the principal identifies k = arg A hig as the current estimated best arm and wants to induce the agent to pull the arm ki using the scoring rule St. However, at times, (*( k) + (k2 k) and o + I (kt) may not be precise enough to estimate C(ki k) and yuz due to limited observations of arm kj- Consequently, the agent might not choose arm ky under scoring rule Skz, This indicates directly setting St = =Saa.+ .t is not sufficient to induce arm kj Hence, we let the principal adopt conserva- tive scoring rule S, = a²SA;; + (1 a Say,t- Intuitively, since the scoring rule 5,; ensures the agent will select arm kj, incorporating it with Skz, increases the likelihood that the agent pulls arm Kj compared to using S alone, as the combined rule strengthens the agent's 's preference for the estimated best arm.
Before presenting the learning algorithm, we first define the concepts of the reward gap and problem complexity.
Definition 3 (Reward gap and problem complexity). We define the reward gap between the optimal arm and a sub-optimal arm l as As = M(5*) h((s)). Further- more, the instance-dependent problem complexity is de- fined as HA = 4(Bs + B²,)² + Enpps A/² and instance-indepea innepeeedideeendent problem complexity as He 4BBs + K/ee.
The reward gap A represents the difference between the maximum profit that the principal obtain when the agent pulls the optimal arm k- versus a sub-optimal arm k. In the bandit literature, problem complexity is commonly defined as HA- = c - + Σnzt- --2 and H, = Ke This defi- nition arises from the assumption that the rewards of each arm are bounded within [0, 1], leading to 0 < A < and A S é S 1. In our context, we have 0 < B., S
Remark 2. Therefore, if St contains more ingredients from Sw: (meaning or is relatively large), it's more likely to prompt the agent to select kद and requires fewer binary searches. Consider the extreme case that ot = for all t, then the OIAFC will directly present the action-ing ection-informed or- acle of arm k and the agent must respond with ke = k. How- ever, this might increase the simple regret h((*)) -l(S.) leading the algorithm to employ more regular rounds (i.e.. kn ke) to estimate a suitable S* such that it can satisfy the condition in Eq G.. Therefore, selecting suitable {ak, K and 3e to bulance the trude-off between normal exploration (i.e., = -E=1 1,k, = kū }) and forced exploration (i.e., To = E [1k + kt), note that rounds ky + k include the rounds in the binary search) is one of the key challenges addressed in this paper.
and 0 V 2 J S 1. This consideration motivates our selection of problem complexity in Definition 3
We now introduce the OIAFC algorithm.
As outlined in lines 2-4 of Algorithm 1, OIAFC begins with an initialization phase, where action-informed oracles of different arms are presented to the agent, feed- back is collected, and estimates are updated. The algo- rithm then enters the exploration phase, where the princi- pal's 's task is to identify the currently estimated best arm, denoted as kg = arg max ht. with hj derived from PP..- To incentivize the agent to select this arm,
OIAFC.
6

---

Online Principal-Agent Information Acquisition
Algorithm 1 Online Information Acquisition Fixed Confidence (OIAFC)
1: Inputs: Arm set A, action-informed oracle {
2: for = 1: K do
3: Principal announces St St and updates the data based on its observation
Initialization
4: end for
5: while / < 0c do
6: Calculate l.. (*(,,, K", (k) Eq k() for all & E A and pair (k, k))
7: for k : K do
8: Solve UCB-LP and derive ht and Sk.c
9: end for
10: Set K arg maxxe hig and S, at- (1 -1-10 a4;) Suz.
Sampling rule
Principal announces St and observes the responding arm of the agent K.
12:
if la + k then
13:
Conduct binary search (S( Sug, ((
Forced exploration
14:
else
15:
2B3 - (k)))(R)) & 3, then
Output S* St the estimated best scoring rule and break
Decision rule
17:
end if
18: end if
19:
Set / 1. +++ and begin a new round
20:
end while
Define 2 = = lik, = kg = k} as the number that & appears in a normal exploration till round t. With the following Lemma 3] we can derive a destnetede upper bound of Ti.
Lemma 4. we select at and Br as Lemma under event E, we have T2 = = Remark 3. One of the key technical contributions of this pa- per is the introduction of new trade-off parameters { and breaking parameter Be, which are used to derive the irstance-dependent sample complexity upper bound. (Chen) et al. (023)) set at. -min (1/5. for all k A, which Tonils them to a sub-optimal, instance-independen sample complexity upper bound. In contrast, parameters ensure that C = (
K
Lemma 3. we select at min (V
M 1). Be
2-2ajz Bu) when a 1 and 3r when oz
1-ai; under event E, we have Tı = ((MHs).
B.)² for all k + k" (see the proof of Lemma 4 in the Appendix). allowing us to establish an instance-dee deeennded upper bound for T1. Moreover, these parameters link Tı and T2, demonstrating that the number of binary searches can be bounded by Ö(5i (T,BBE-- (see Section E.2 the Appendix). Ultimately, this enables us to derive instance cettance-deendeent upper bound for T1 + T2-
The result described above related to the definition of of the stopping rule outlined in line 15 of Algorithm [ well as the structure of the fixed confidence style confidence radius in Eq 99)
Forced exploration. If the agent does not choose kn = Ke after the principal announces St, it indicates that our estimate of VRz (the second constraint UCB-LPxg is insufficient. To ensure the agent selects kg future rounds, further exploration is required improve the estimate of Vis- Specifically, using the structure Se = ai, Suz + (1 ) we update the boundary of Va: between S, and Sey- This is done by performing binary search along the region connecting S, and Se; to determine where the agent's preferred arm shifts from K another arm. This binary search efficiently refines the estimate of Vız in logarithmic time. More details on the binary search algorithm can be found in Algorithm in the Appendix.
The subsequent Lemma 5 demonstrates that the returned estimated best scoring rule 5 can meet the (e, - in Eq (3).
Lemma 5. we select of and Be as Lemma 3 the returned estimated optimal scoring rule of OIAFC (i.e., S*) can satisfy the (c, -'oonditoo in Eq (3).
Together with Lemma 3 we can provide the instance- dependent learning performance of the OIAFC
Theorem 1. We set at. min (V M 1). 3,
C-20 (Bs+Ba) when aty < and 3 0 when af; 1.
In the following Lemma 4 we provide an instance- dependent upper bound of 72-
I-
Under such cireumstance, OIAFC can output an estimated
7

---

Online Principal-Agent Information Acquisition
best scoring rule which satisfies the (e, (-onndinnn in Eq The sample complexity of the algorithm can be upper bounded by T = Ö( (BMM)) with probability at least 1- --5 5.
For For Cacciamaaii el al. 2023), we believe their explore-then- commit (ETC) algorithm can achieve a sample complexity bound of K/ē² by appropriately calibrating the length of the exploration phase with respect to c. However, obtain- ing an instance- dependeet sample complexity bound from ETC-based methods is challenging due to the necessity of setting the exploration phase length in advance, without prior knowledge of the actual pnstance-specifee reward gaps or problem complexity.
Remark 4 (Theorem 1 provides a sample complexity up- per bound that is near-optimal). The presence of the M term in our sample complexity upper bound arises because Is. is a probability distribution supported on a finite set of cardinality M. To bound qs, we rely a concentration inequality (Lemma 6 in the Appendix). Consider a sim- ple setting where the belief set is {oi and the agent returns belief 02k-1 or 02k to the principal only when it pulls arm k E A (this knowledge is known by the princi- pal). Let qu represents the distribution of 02 and o2k based on the agent's action k. By replacing the previous belief estimator with (1) No E==1 1fa,- a, k2 k), a E 1022-1, and defining the confidence radius 2 21og(16K1210)
In summary, our algorithm achieves near-oplimal instance- dependent sample complexity due to: (1) the selection of appropriate parameters, (2) the design of suitable breaking and decision rules, and (3) the adoption of an effective algorithm structure (UCB).
By selecting suitable of and 3r, we can also derive an iestance-independent sample complexity upper bound. This is tailored to the circumstances that As is relatively small and é is relatively large.
we can upper bound the sam- ple complexity by Ö (E-2 B3HH). This result aligns with sample complexity upper bounds of common best arm identi- fication algorithms in the MAB literature (i.e., Ö(H)). e.g.,
as 12(k)= -
NE
Corollary 1. We set oj B.Bs-B.) for all l E A and
t E [T] and Be = c-2aiz (Bs+ OIAFC can output an es- timated best scoring rule which satisfies the (e, -)-ondiiioon in Eq 3 The sample complexity of the algorithm can be upper bounded by T = Ö(s MH. with probability at least 1 1- 8.
1-a;;
Bvvnn-Dar et al. (2006); Gabillon et al. 2011 : Jamieson et al. (2033).
Remark 5 (Origin of the 1/2² term in the sample complexity bound). To find the near-optimal scoring rule, we must identify both the best arm KS and the set of scoring rules that can trigger the best arm Vz-. Intuitively, the dependency on A arises from identifying the best arm, whereas the dependency on 1/e2 emerges because, even after identifyng the best arm, additional samples are required to estimate the set Vk- at an c-accurate level. Only then can we determine a scoring rule that meets the required accuracy.
The proof of Corollary | follows a similar approach to the proof of Theorem [ i.e., we separately upper bound 71 and T2, and demonstrate that the estimated best arm satisfies Eq (3. In Chen et al.] (2023), the authors show that their algorithm can find the (c, (c,))-optmmal scoring rule with at most T = Ō Bs + 08 their Corollary 4.4), which is significantly larger than our sample complexity upper bound O ?) (note that M S K Co) in Corollary [ Our results also align with the efficient instance-independent bound in MAB, i.e.,
samples (see
Remark 6 (Advantages of our algorithm over existing ap- proaches). We now provide intuition for why our algorithu can achieve near-optimal dnstance-dependeen sample com- plexity, while Chen et al. (2023): : Cacciamani et al. (2023) fails to do so. The primary reason for the suboptimal sam- ple complexity in Chen et al. (2023), aside from choosing an inappropriate parameter, is the adoption of subop- timal termination criterion. Specifically, they employ the breaking rule originally introduced by Jin et al. (2018), which terminates the algorithm after Ö(E "le=6K"CC K*CO) iter- ations and selects the scoring rule identified in the final round as the best estimate. This termination strategy is in- herently inefficient because it intuitively demands large number of samples to ensure the accuracy of the identified scoring rule. In contrast, our proposed breaking rule (line 15 in Algorithm 1) and corresponding decision rule (line 16 in Algoritium 1) enable a more efficient evaluation of whether a scoring rule satisfies the necessary conditions. Consequently, our approach achieves significantly improved sample complexity.
== (Ke))) (Even-Dar et al. 2002 Kalyanakrishnan
ct al. 2012).
5.2. Online information acquisition fixed budget (OIAFB)
The OIAFB algorithm shares the same sampling rule and forced exploration strategy as OIAFC. However, it diverges in its stopping and decision rules. OIAFB stops once it exhausts the allocated budget T, returning the estimated best scoring rule as S Sr-, where 8 arg minte7 2(Bs + B,)))(kt) and T denotes the set of all satisfying h; = kj. Another difference is that OIAFB utilizes confidence radius in Eq (T)) to design UCB-LP A. The pseudocode for OIAFB is provided in Algorithm 2 in the Appendix, and its theoretical performance is detailed in Theorem 2 below.
OIAFB.
8

---

Online Principal-Agent Information Acquisition
Theorem 2. If we run OIAFB with of t E [T] and & E A, and T satisfies
4[By+B,) B.) for all
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
T-K
log (TK2M) 144H, max (B3E 3 2, ITg)(T)
Choose parameter a such that
Acknowledgements
T- K 2 llg(TTK2M) sac 144H, max (Bze-2, 1) log2 (T)
Huazheng Wang is supported by National Science Founda- tion under grant IIS- IIS-2403401.
then OIAFB can output (c, esttimated optimal scoring rule with < e e 1a $ 1.
Theorem 2 can directly lead to the following corollary:
Corollary 2. we set 8 E (0, 1).
T 288H max (B3e-2, (T))(T)
M + log
TK
(5)
)) K,
where
T= (115H max (Bze -2 BB (K/6))/2) + k) x))
a ((B+BB.) for all t [T] and &o A. and 2 log (TK2 Then OIAFB can output (c, estimated optimal scoring rule with 8 < 6.
Corollary 2 demonstrates that, given a budget Ó(E B.. the OIAFB algorithm can identify an esti- mated best arm that satisfies the condition in 3 aligning with the results stated in Corollary [ More generally, the analysis presented in this paper suggests that the perfor- mance of the OIAFC and OIAFB algorithms for scoring rule identification is characterized by the same complexity notion monstance-indeendee across both fixed confidence and fixed budget settings.
6. Conclusion
In this paper, addressed the Best Scoring Rule Identifica- tion problem, building on the framework and results from Chen et al. (2023). We proposed two algorithms: OIAFC for the fixed-confidence setting and OLAFB for the fixed- budget setting. Our analysis shows that OIAFC can iden- tify the (e, eesttmmtte optimal scoring rule, achieving an instance-dependent upper bound of - M HA) and an instance- inndeeedeeddeee upper bound of Ō M.) The OIAFB algorithm demonstrates similar efficiency in the fixed-budget setting. A promising avenue for future work would be to extend the Best Scoring Rule Identification framework to more complex multi-agent environments, as explored in Cacciamani et al. (2023).
9

---

Online Principal-Agent Information Acquisition
References
Castiglioni, M., Celli, A., Marchesi, A., and Gatti,
N. Online bayesian persuasion. In Neural Infor- mation Processing Systems, 2020. URL https /app. 221275502
Agrawal, S., Feng, Y., and Tang, W. Dynamic pricing and learning with bayesian persuasion. Advances in Neural Information Processing Systems, 36, 2024.
org/ /o//orpssI
Alon, T., Dütting, P., and Falgam-Cohen, I. Contracts with private cost per unit-of-effort. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp- 52-69, 2021.
Castiglioni, M., Marchesi, A., Celli, A., and Gatti, N. Multi-receiver online bayesian persuasion. ArXiv, abs/2106.06480, 2021. URL https:
wwt.eeeannnccccooooooooooooo//oe 235417398
Amin, K., Rostamizadeh, A., and Syed, U. Learn- ing prices for repeated auctions with strategic buy- ers. In Neural Information Processing Systems, 2013. URL stttpss:/api...mmattii.o htc//oorpuSD::670225
Castiglioni, M., Marchesi, A., and Gatti, N. Bayesian persuasion meets mechanism design: Going beyond in- tractability with type reporting. ArXiv, abs/2202.00605. 2022. URL https://api. hwm.a//ppp...aa......aaammmaa... semant i cschola lar
Azize, A., Jourdan, M., Al Marjani, A., and Basu, D. On the complexity of differentially private best-arm iden- tification with fixed confidence. Advances in Neural Information Processing Systems, 36, 2024.
oxg/CoorpusD::24444222
Chakraborty. S., Bedi, A., Koppel, A., Huang, F., and Wang, M. Principal-driven reward design and agent policy align- ment via bilevel-rl.
Bacchiocchi, F., Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Markov persuasion processes: Learning to persuade from scratch. arXiv preprint arXiv:240..03077, 2024.
Chen, L., Li, J., and Qiao, M. Towards instance optimal bounds for best arm identification. In Annual Conference Computational Learning Theory, 2016. URL attts::/ap..semmatiiss... sewanticscheeee
Balcan, M.-F, Blum, A., Haghtalab, N., and Procaccia, A. D. Commitment without regrets: Online learning in stackelberg security games. Proceedings of the Six- teenth ACM Conference on Economics and Computation, 2015. URL https: h/tp:./ppp.aa wew.nteeannttii icschooaai org/ Co Co PoorpusTin :D: 14830193)
orq Peg//oorpusD:1127544
Chen, S., Wu, J., Wu, Y., and Yang, Z. Learning to incen- tivize information acquisition: Proper scoring rules meet principal-agent model. In International Conference on Machine Learning. pp. 5194-5215 PMLR, 2023.
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. 5502-9510, 2024.
Chen, Y. and Yu, F.-Y. Optimal scoring rule design. arXiv preprint arXiv:2107.07420, 2021.
Cohen, A., Deligkas, A., and Koren, M. Learning approxi- mately optimal contracts. In International Symposium on Algorithmic Game Theory, pp. 331-346. Springer, 2022.
Bernasconi, M.. Castiglioni, M.. Marchesi, A., Gatti, N., and Trovò, F. Sequential information design: Learn- ing to persuade the dark. ArXiv, abs/2209.03921 2022. URL org
Conitzer, V. On stackelberg mixed strategics. Syn- these, 193:689 703, 2015. URL https::// /api Semanticscholat Cttp//orppsID:::: 726055
http::/://ppppp..a....s.se Ttte/GorppsDD::2211633 Cot/Corpuslii..aai.
Bernasconi, M., Castiglioni, M., Celli, A., March- esi, A., Trovò, F., and Gatti, N. Optimal rates and efficient algorithms for online bayesian persua- sion. ArXiv, abs/2303.01296, 2023. URL https:
Even-Dar, E., Mannor, S., and Mansour, Y. Pac bounds for multi-armed bandit and markov decision processes. In Annual Conference Computational Learning Theory, 2002. URL https: /ppi. www.nticscooollaaa.... org/ CorpusID:122577
www.matticsccooar..rrroo//oooo 262231443
Even-Dar, E., Mannor, S., and Mansour, Y. Action elimina- tion and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 7:1079-1105. 2006.
Bubeck, S., Munos, R., and Stoltz, G. Pure exploration in multi-armed bandits problems. In International Confer- ence on Algorithmic Learning Theory, 2009.
Cacciamani, F., Castiglioni, M., and Gatti, N. Online in- formation acquisition: Hiring multiple agents. arXiv preprint arXiv:2307.062 10, 2023.
Feng, Z., Podimata, C., and Syrgkanis, V. Learning to bid without knowing your value. Proceedings of the 2018 ACM Conference on Economics and Computation,
10

---

Online Principal-Agent Information Acquisition
2017. URL https::/api.semaatiiccsss htg/CorpustD:227440000
Ivanov, D., Dütting, P., Talgam-Cohen, I., Wang, T., and
Parkes, D. C. Principal-agent reinforcement learning. arXiv preprint arXiv:2407. 18074, 2024.
Gabillon, V., Ghavamzadeh, M., Lazaric, A., and Bubeck, S. Multi-bandit best arm identification. In NIPS, 2011. URL
Jagadeesan, M., Wei, A., Wang, Y., Jordan, M. I., and Steinhardt, J. Learning equilibria in matching mar- kets from bandit feedback. ArXiv, abs/2108.08843. 2021. URL org hrg/Corppu1D:2232133333
sew.ttiissaatttschl.... org/CorpusID:1139241
semanticscoolla.
Gabillon, V., Ghavamzadeh, M., and Lazaric, A. Best identification: A unified approach to fixed budget and fixed confidence. In NIPS, 2012.
Jamieson, K. G., Malloy, M., Nowak, R. D., and Bubeck, S. lil' ucb An optimal exploration algo- rithm for multi-armed bandits. ArXiv, abs/1312.7308, 2013. URL soctts::/app: sem.niiiscsctccccocc.o org Cttp//orrpiiDD./ :6004443
Gan, J., Majumdar, R.,
Radanovic, G., and Singla, A. K. Bayesian persuasion sequential decision- making. ArXiv, abs/2106.05137, 2021. URL https: www.eeeccccoolar.oorooooooooo 235376944
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.,
Garivier, A. and Kaufmann, E. Optimal best arm identifica- tion with fixed confidence. Annual Conference Compu- tational Learning Theory, 2016. URLhttts:://api semanticschol www.aaarrrrrreeeeee wttp:/ooorrss1:11271890.9
cc/ htcp/ppper_ffleeeppppre//1111111 hewp:/occceeddnoo...e...oo.... neurips
2018. URL http:://prrooeedingg..
Golrezaei, N., Javanmard, A., and Mirrokni, V. S. Dy- namic incentive-aware learning: Robust pricing in contextual auctions. Microeconomics: Production, 2018. URL https:/app...mmatccccco... www.nticsccoollltt.....ao org/Cor Prg/CorpusID: ( 169598123
d3b1 33b16660224444662277772223333333 - Paper pdf
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection stochastic multi-armed ban- dits. In International Conference on Machine Learning. 2012. URL https:// semant. i escholat org Corppss1::
Guo, W., Jordan, M. I., and Vitereik, E. No-regret learning in partially-infomeed auctions. In Inter- national Conference on Machine Learning, 2022.
URL
Corpus 1D:
Laffont, J.-J. and Maskin, E. The theory of incentives: An overview. Université des sciences sociales, Faculté des sciences économiques, 1981.
Haghtalab, N., Lykouris, T., Nietert, S., and Wei, A. Learning in stackelberg games with non-myopic agents. Proceedings of the 23rd ACM Conference Economics and Computation, 2022. URL https:
Li, Y., Hartline, J. D., Shan, L.., and Wu, Y. Optimization of scoring rules. In Proceedings of the 23rd ACM Con- ference on Economics and Computation, pp. 988-99 988-989, 2022.
h wtw.tticccoolaa..r/go/oooo 250497033
Han, M., Albert, M., and Xu, H. Learning in online principal-agent interactions: The power of menus. In Proceedings of the AAA/ Conference Artificial Intelli gence, volume 38, pp. 17426-1744 11434, 2024.
Mannor, S. and Tsitsiklis, J. N. The sample complexity exploration in the multi-armed bandit problem. In Journal of machine learning research, 2004.
Hartline, J. D., Shan, I.., Li, Y., and Wu, Y. Optimal scoring rules for mintiidiimessioall effort. In The Thirty Sixth Annual Conference on Learning Theory, pp. PMLR, 2023.
Mardia, J. Jiao, J., Tánczos, E., Nowak, R. D., and Weissman, T. Concentration inequalities for the empirical distribution. ArXiv, abs/1809.06522. 2018. URL ozq/CorrusID:5229831
Ho, C.-J. Slivkins, A., and Vaughan, J. W. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated aancipal-agem problems. In Proceedings of the fifreenth ACM conference on Economics and computation, pp. 356, 2014.
Myerson, R. B. Incentive compatibility and the bar- gaining problem. Econometrica, 47:61-73, 1979.
URL https: http:://ppl..smmatticcchoooee CorpusSDD:1522513111

---

Online Principal-Agent Information Acquisition
Neyman, E., Noarov, G., and Weinberg, S. M. Binary ing rules that incentivize precision. In Proceedings of the 22nd ACM Conference Economics and Computation, pp. 718-733, 2021.
2021. URL https: /ppi........ semanticscho ar org 2tc//orppuTDD::2188800 2339693227 986327
Zuo, S. New perspectives online contract design: Het- erogeneous, homogeneous, non-myopic agents and team production. arXiv preprint urXiv:2403.07145. 2024a.
Ossterheld, C. and Conitzer, V. Minimum-regre contracts for principal-exper problems. In International Con- ference on Web and Internet Economics, pp. 430-443, Springer, 2020.
Zuo, S. Principal-agent multitasking: the uniformity of op- timal contracts and its efficient learning via instrumental regression. arXiv preprint arXiv:2405. 20642, 2024b.
Papireddygari, M. and Waggoner, B. Contracts with infor- mation acquisition, via scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computa- tion, pp. 703-704, 2022.
Savage, I. J. Elicitation of personal probabilities and expectations. Journal of the American Statisti- cal Association, 66:783-801, 1971. URL https:
//api. www.ntcschhcaaa. //tp.//.eeaantecaaaaa..../////// hww.cacccoaa...or/coopuuu..... 120427654]
Scheid, A.. Tiapkin, D.. Boursier, E., Capitaine, A., Mhamdi, E. M. E., Moulines, É., Jordan, M. I., and Dur- mus, A. Incentivized learning in principal-agent bandit games. arXiv preprint arXiv:2403.0381/ 2024.
Sessa, P. G., Bogunovic, I., Kamgarpour, M., and Krause, A. Learning to play sequential games ver- sus unknown opponents. ArXiv, Abs/2007.05271 2020. URL org/ htc/Coopuu1D::20457000
http://aapp..mmmniccccc........
Wang, Z., Li, C., Song, C., Wang, L., Gu, Q., and Wang, H. Pure exploration in asynchronous federated bandits. arXiv preprint ar arXiv:2310.11011 2023.
Wu, J., Zhang, Z., Feng. Z., Wang, Z., Yang. Z., Jordan, M. I., and Xu, H. Sequential informa- tion design: Markov persuasion process and its ef- ficient reinforcement learning. Proceedings of the 23rd ACM Conference on Economics and Computation, 2022. URL https://api. stcp::///pp..smmnniccchhoooo semanticscholat
Wu, J., Chen, S., Wang, M., Wang, H., and Xu, H. Contrac- tual reinforcement learning: Pulling arms with invisible hands. arXiv preprint S.Ki::2407.0155. 2024.
Zhu, B., Bates, S., Yang. Z. Wang, Y., Jiao, J. and Jordan, M. I. The sample complexity of online contract design. Proceedings of the 24th ACM Conference on Economics and Computation. 2022. URL
oxc/CooppusD:25344700
Zu, Y., Iyer, K., and Xu, H. Learning to persuade on the fly: Robustness against ignorance. Proceedings of the 22nd ACM Conference on Economics and Computation,
12

---

Online Principal-Agent Information Acquisition
A. Notations
A
Arm set
Number arms
Time index
Terminated round in the fixed confidence setting Budget in the fixed budget setting
T
W
State
True belief of the agent Reported belief of the agent
ōz
St
Scoring rule
kt
Agent's s action
Principal's desired arm
((S)
Principal's profit function under the scoring rule S Agent's ' profit function under the scoring rule S and arm k Set of the scoring rule that can trigger the agent to respond by taking arm k Best response of S* Best scoring rule Estimated best scoring rule
k)
Vk
k*
S*
S*
Belief distribution of arm k
Ck
Cost of arm Cost difference of pair (k:, K))
(kk, R)
Estimator of 9l:
(k, k')
Estimator C K')
(1))
Confidence radius of d
I. (k,,))
Confidence radius of (*(k, k))
Probability parameter of the fixed-contidence setting
Probability parameter of the fixed-budget setting
Utility gap (h(S*) h((S*)) parameter of the fixed-confidence pure exploration problem Utility gap parameter of the action-informed oracle
Sa.
Scoring rule solving by UCB-LPPa.
(S
Action-informed oracle Estimator ((S))
3,
Breaking threshold in round t Trade-off parameter of arm Expected payment of the scoring rule S if the agent responds by taking arm k Estimated payment of the scoring rule S in round t if the agent responds by taking arm k Expected utility of the principal under arm Estimated utility of the principal under arm k Number rounds that arm is observed till round
at
(s())
(K)
us
N
Bs
Upper bound of ||S||oo
B.
Upper bound of ||a]| Instance gettanceddeendeen problem complexity
H
He
Instance Instance-independee independent problem complexity
13

---

Online Principal-Agent Information Acquisition
B. Details A bbut The Iteration Processes and The Information Structure
To formulate the problem of optimally acquiring information within a principal-agent framework, we model the system as a stochastic environment, a principal and an agent. In each round t, the environment will generate a hidden state w/ E Ω which is depended on the agent action, and will influence the principal's utility. However, this hidden state remains unknown to both the principal and the agent until the end of the round.
The principal's 's goal is to elicit the agent's belief about this hidden state. To achieve this, the principal first offers scoring rule St that provides a payment based on the quality of the agent's reported belief. This reward incentivizes the agent to provide a more precise estimation of the hidden state. In response to this incentive, the agent incurs a cost Ck. to take an action (arm) k; from its Kaarmed set A. gather an observation o regarding the hidden state from the stochastic environment, and subsequently generate a belief report o, for the principal.
This belief report, in turn, aids the principal to make decision d,- At the end of each round, the hidden state is revealed to both agent and principal, enabling the principal to compute the corresponding utility. Based this, the agent is payed according to the scoring rule initially provided by the principal.
The following table displays the information structure of the online information acquisition problem.
Public Info
Agent's s Info Principal's Info Delayed Info
St, Ōz
{c)) (m))21100,00 0t,
u
W/
Table 1. This table outlines the different types of information in the model. Public Info represents information that is accessible both the principal and the agent at each round. Agent's s Info consists of information known only to the agent, while P Principal ppal's Info pertains to information exclusive to the principal. Lastly, Del pelayed Info refers the hidden state wa, which remains unknown throughout the round but becomes revealed at the end of round f.
C. Learning The Pairwise Cost Differences
In this section, we introduce how to utilize estimator (*(Kk, k²) to learn the pairwise cost difference C'kk, k'). We define for each pair (k, k'),
C4 (ks, k') = min
+ (0%s, (k) - 00'0) (k')) + Bs (s( I()))),
sctk, =k
C (k,k') = max
(k) - i's. (k)) - Bs (1,()) + 1(()).
sktkk ke'
We also define
0² R²) (ki,kk))
Ct (k)
C4 (k, )'(k,k)=
C* kk)
(1))
2
Consider graph G = (B, where the nodes in B represent the K arms, and the edges in E' represent the pairwise cost differences C(k, k') C Cy. Additionally, introduce (k: k') as the "length" assigned to the edge C(k, K²), indicating the uncertainty when using 0¹ (k: k') to estimate the cost difference. To estimate C(k: k') with minimal error, we aim to find the shortest path between arms i and on the graph G. This means we're looking for the shortest path between the arms to minimize the errors in estimating their cost difference. Based on this idea, we can estimate the pairwise cost difference by
be = shortest path(G, k,),, (²(K)k')= Σ
(i(i))),
(1,))lee
(((kk))=
Σ (
(L.)
where le. denotes the shortest path between arm 1: and k'' in graph G, (kk k3) is the confidence radius of the pairwise cost estimator (hi,,, k.). Besides, it is evident that Ot (kk, k²) - (k:, k²) due 1R.K' lec and 0' (k,,,, k') = OK'(K', kb).
14

---

Online Principal-Agent Information Acquisition
D. Omitted Algorithms
D.I. OIAFB
Algorithm 2 Online Information Acquisition- Fixed Budget (OIAFB)
Inputs: Arm A, action-informed oracle {S k= and budget T
2: for L= : K do
3: Principal announces Se and updates the data based on its observation
Initialization
4: end for
5: while t S T do
6: Calculate /% (", (k) in Eq (T)). (k, k)) for all E A and pair (k:, k²)
7: for k = 1: K do
8: Solve UCB-LPkst and derive hig and Sk.t
9: end for
10: Set K arg A hig and St of Sk: + (1 - [1-0
Sampling rule
11:
Principal announces St and observes the responding arm of the agent k.
12:
if h = K then
13:
Conduct binary search (S, Sxy kt,
Forced exploration
14:
end if
Set +++1111 1 and begin a new round
end while
Define set T the set of all that satisfies Kr kg
18: Set t" arg min 2(Bs + (k)))
19: Output S- St- as the estimated best scoring rule
Decision rule
D.2. Binary search
Algorithm 3 Binary Search (1, (S)),, (T(())))
1: Inputs: Sy, S1, (*.k(*(S)))))) (81), (A))
2: Initiate Amin = 0, Amax = 1, and 1,
while Amax Amin 2 minn (So)), (k*())) do
4: Start new round
5: Set À = (Amin + Amax) 2/2 as the middle point
6: The principal announces S. = (1- A)So + AS and obtain the agent's response k;
7: if lip = kSi) then
8:
Set Amax =
9: else
Set Amin A
11: end if
12:
end while
13:
Return:
Binary search In binary search, the algorithm continues searching for the initial point of transition where the agent switches from responding to arm (Si))) to another arm within the region (Sp, S1). Amax and Amin define the interval containing the switching point. After each round, the binary search assigns = (Amax + Amin)/2 to either Amin or Amax. effectively halving the candidate interval. The binary search stops once the searching error Amax - Amin becomes smaller than the minimum confidence radius between (S)) and k. (S2). It's important to note that the depth of the binary search, denoted as m, is less than loga mmin(15(k=(S)) (S.)).4;( (also less than logz(t) by the definition of the confidence interval). Therefore, the binary search ensures sufficient accuracy within a logarithmic time.
New notations We hereby introduce new notations to describe more details the binary search. We define binary search operation as (So S1, Amax: Aminy ko  lo f1), wherein Sn and S₁ denote the input scoring rules. Notation
15

---

Online Principal-Agent Information Acquisition
Amase Amiu) represents the (min the end of this binary search. Additionally, ho and k determined as ke ((1 Amin + Sm) and k* ((1 Amax) S.0 + X1ax respectively. Lastly, to and & signify the initiation and culmination rounds of the binary search process. It's important to note that while ky represents the optimal response under S1, ko may not necessarily be the optimal response under Sg.
E. Proof of Lemma 2
To prove Lemma
2 we need to employ the concentration result of Mardia al. (2018).
Lemma (Mardia et al. 2018), Lemma 1, Concentration for empirical distribution). Let X denote probability distribution that is supported in finite set with cardinality of at most M. Let X1, X2,..., Xn be ii.dd random variables drawn from
X. The sample mean is denoted by X 1 Li== X For any sample size n E N+ and 0 S ô S 1, the following holds:
P |X - 8112
2log(2M
S 6.
(12)
71
Proof of Lemma Recalling the event & of E. By applying the union bound, we obtain:
{llø6 9xl11 $ (k),, vs [t], Wk A}, define E as the complement
K t
P(E9) S
Σ
P |1 - qulla > 1())
(13)
1=1
Based on Lemma 6 and the definition of the fixed-confidence confidence radius (k) in Eq (9). follows that P (196
0:ll: 12(h)) < 8/(KK=)), Vs E [4], & E A. Substituting this result into Eq 13 we obtain:
K
8
P(E))
S
4K 82
k=1
It implies P(E)= 1 - 8.
Employing Lemma and following a procedure analogous to the previous one, it is straightforward to demonstrate that P(E)= 2 1 - IK2 M a if (k) is defined in the fixed-budget style, as in Eq (10).
Consider the case when occurs. Based on ||S S Bg and ||u|loo & Bus it follows that
(K) - us(k)]] = (ot oh. S) S (k) e KEA,
(14)
ii un| - q, u) S BkIz(k), vk A.
Besides, based on the definition of C₁, and Ct, we have
C (k. 2 min Us. (k) us, (k') 2 C(k,k),
=<tik==k
(15)
C (k, <
max
Us. (k) Us. (K) < C(k, K').
s<tRk=
16

---

Online Principal-Agent Information Acquisition
Utilize Eq 15
have
+ Ci((.) - -c(.))))C(..))
- =
Σ
2
(1.jiEl2,
Σ
- (C(((.))- + (C((.)))
2
(6,j)
Σ
(c1(6.5)- C(..1) +
1 Σ (c1() c(.
2
(K.)EL
(
$ 2
Σ
- + c (i,)) - c(t,)))
(i.)EL
E
(K
where the first and second inequalities follow from the triangle inequality, the third equality follows from Eq (5) and the last equality follows from the definition of (k, K). This completes the proof of Lemma
F. Proof of Lemma 5 and Theorem
F.1. Proof of Lemma 3
Proof of Lemma 3 We will break this proof into three steps. In the first step, we upper bound Exes= L% In the second
step, upper bound CT.. Finally, in the third step, upper bound TI Ex CT.
First step: We want to prove
(B + B.) log (4K2
C S
Wk + Kt"
(16)
A
Define arm k o k2 and let l be the final round in which arm is observed, with = kip = hig Then, based on Lemma and Lemma when at < 1, can derive
2
(h(S)) at 2 h(Sw)) 2(Bs B.) (k) h M N h(8*),
(17)
2x
where the second inequality is owing to k = kū, and the definition of kiz We can rewrite Eq 17 as
it
A
ok
(M(S)) h((5)) + 2(B Ba) (k)
Ck
k
(18)
2 k
(Bs + B.,) + 2(Bs + B.,) T2 (k:)
ag
When A
20 1
(Bs + Bu), based on the definition of the fixed confidence style confidence radius, the above incqualities
can be converted to
8(Bs B,)² log log(4K2 20 1- - (Bs + Bw))
8(Bs Ba)² log 1og(4K2 2n
=== che S Art S
(19)
2
(A.
(A: i-a (Bs + Bu))
where the first equality follows from the definition of tu. the first inequality holds because N2- = - 1ike D 11 (k= kg k.), and the third inequality follows from 4 S r.
k} 2 4
17

---

Online Principal-Agent Information Acquisition
Suppose
(2V2+8)(Bs + logg
4
(20)
A
Note that under this assumption, we have Ag >
2a I-ah
(Bs + Bu)
2n
(Bs + B.) and og = ox. SSbbsituting
1-0
Eq (0
into Eq
19p. we obtain
8(Bs + B,)² log (4K22>210
C% <
A 1-07
20% (Bs + BBu)
8(Bs + lo,) (0KK42M777 72/8)
AA. 1
M c
(Bs + Bu))
(21)
2222BBs + Ba) V (og + 4(Bs + B.)V
A
(2V2+8) B.) (wg(lll2oaa//..o 4K2M
A
where the second step follows from holds.
VM. The above inequality contradicts Eq 20 which implies that Eq
16
Second step:
We want to prove
G7 (2V2+2) + B.) B.) (ogg(44222222//))
+1.
(22)
?
If ks" is only triggered in the initialization phase, this result trivially holds. Besides, suppose f.- the penultimate round that arm k is observed in round that k ki kec.. According the stopping rule (line 15 of Algorithm D. we derive
Bex 2 + Br) (k)
(23)
If Br.- >> then we can substitute Eq (9) (the definition of the fixed confidence style confidence radius) into Eq (23 and derive
8(Bs + B2,
4K2M2 12 K*
C/- = Ehe +1 +15
log
+1
32
8
(24)
8(Bs B
2
4K2M 72
log
+ 1,
where the first equality is owing to the definition of ba- and Lt-- and the last inequality owing 44- S T. Suppose
(2VZ+4)(Bs + B.) B.) 1og((oo22222///0
(25)
18

---

Online Principal-Agent Information Acquisition
note that this implies Bec. > O. Recall the definition of the Sr, Eq 24
can be further expressed
8g + B.)²
44K2 72
Ci k- +15
log
+
1
20 41" (Bs + Bu)) 2 / -
)
8
Ok-
8(Bs + B.)²²
4K22 72
log
+1
20 (Bs Bu))
(26)
2v2(Bs + BB) log( 4K2M 72/8) + 2(Bs B.)
(2V2+ + 4 + Ba) 1og(44222222)) 2
+1,
where the first inequality owing a and c 2a (Bs Bu) > Since Eq (26) contradicts Eq can finally conclude that Eq 22 holds.
Third step:
Combine Eq
16 and Eq (22) Ti can bounded by
K
C
k=1
4K2
(96 48 HA log
+1
8
4K72
< + 48 HA
log
+ M)
+ 1.
Note that the right-hand side of the above equation includes the T term. the following proof of Theorem we will eliminate this term ensure that the upper bound does not depend on т. This completes the proof of Lemma
The proof of Lemma 3 relies on the following Lemma and
Lemma 7. Under the event &, have
h(S2) S h - uk (k) 2(Bs + Bk)
(27)
for all k E A.
Proof of Lemma 7 Recall the definition of h,; = at + Bal;(k) - -7.r. Based on Lemma
we can derive that
ust (k) 2 Usg (k) C(k,k')
2 (k)+ C*( k') I'(kk))))
(28)
2 0d (k. k)) + &k; (k') ) (T.(k,))) + (s), VK k,
The first inequality follows from the definitions of V4 and St. while the second and third inequalities follow from Lemma According to Eq 28 St satisfies all the constraints in UCB-LP With the definition of UCB-LPk.t~ we have
S/ + Bakg(k) usz (k) S th + Bul((k) vip = 14.
(29)
Based on Lemma 2 it has
us S o B,IT(k)..
(30)
Combining Eq 29 and Eq 33 we finally obtain i > u - ast (k) M(S)). Ak E.A
19

---

Online Principal-Agent Information Acquisition
We will then prove the second inequality of Eq 27p. There is
R 2 + Bulg(h Vi.
1 2 8 (k)) + +Bs + (k)
(31)
Uk S2 (k) 2(Bs + B.)
where the first inequality follows from the first constraint of UCB-LPR,t, k,,, and the last inequality follows from Lemma This completes the proof of Lemma] 7
Lemma 8. Given event &, if kg ki and aiz < 1 in round t, then we have
(h(St:) -(, +(Bs B.)
(32)
Proof of Lemma g Remember, k = kt implies that S. can successfully induce the agent to pull kz- According to the
definition of Sh we have
h(ST:) 2 h(()))
-haaz Swz (1 a Skt.e)
(33)
= =aigh(Ss;) + (1 axy (uxt V8ug. (kt)).
Eq 33 can be rewritten as
(K/)) v
(h(5k;) abe h(kk)))
(34)
1 ab
Based on Lemma] 7 we can finally get
h uk V882 + + (k))
(35)
< 1 axi
(h(Stt)) h/5h((k:)) + 2(Bs + (.)
Here we finish the proof of Lemma
F.2. Proof of Lemma
For binary search that concludes at round f, we define (t))) as the initial round of the search, (ko(t), ky (1)) as the optimal response at the end of the search, and (t)) the input scoring rule for this binary search.
Proof of Lemma
4
We can first decompose 72
T2
1 1k # kr}
1=1
1 (BS -1, to (ko(t),ki(t) <
da(t)
1(BS tott) (Ro())) (o)
lol))
))
(olt))
Besides, based on Lemma 10 and Lemma 13 we know that under event E, E 11 1(BS 1, (k) (1)) s
20

---

Online Principal-Agent Information Acquisition
} and Ei=1 {BS 1, T,oo (Mi((); > so(t) Ro())
to(1)
} S Ek=1 NE log2(T). Therefore, we have
(R((t)
K
4KK2M,2
Σ a
?)
22 (o0g(())og) log
72
8
k=1
4K2
< 96 + (12 2H 1og2(1 (T) log²
8
<(96 + 4882) 11 Bs) 2H
2 - ( M + 2og
5
Here we finish the proof of Lemma
The proof of Lemma 4 mainly relies on Lemma 10 and 13
To prove Lemma T0 we need to invoke the following Lemma
Lemma 9. We assume that ['(Koo, ki) S o and kn + kn Under the event E, the agent will not respond by pulling arm ki
according the scoring rule St = a 3km + (1 agg )
Proof of Lemma 9 Under the scoring rule S. ag Sko + - (2/
and the event &, the expected profit for the agent ) 111-///l
generated by responding with arm 1j satisfies
Vo Skg +11 (1 S0 (k1) Cki S a u (R:)) + (1 0 ) 1' (R:1) cb. + (1 a BsT
and the expected profit generated by arm Ko satisfies
Vo Sko +11 (1 / (ko) Cko 2 at, us (ke) + (1 a ) )0/ (ko) Cko - (1 Is
By the action-informed oracle assumption, we already have
U Sko
(Ko)
Cko US., (k1) + Ck1 2 E.
Since Skg, is the solution to UCB-LP following the last constraint of UCB-LP . we obtain
S (ko)
o' S (k1) N C* ('(ko, k1) Bs (1, + 1 (k1))
(36)
Combining the above inequalities, we obtain
1 Vai 5kg + (1 (1- Stp (ko) Cho - Vot, (1 (ko) - cka
20 kg
130 (ki)) - Cho - -5500 (k1) + Cki)
+ (1 - -ate 3 (ki) Ss (ki) C(kos kn)
(1 kg BB 11 (ko) + (k1))
2a E + (1 a/w,) C" k2) -C(ko, k1) - I2(Ku, 12) - Bs Bs (1,(()) + (g(k)))
- - ag1) ) (ko) [k(kk))
20/ 8 + 2(1 a [k ki) - Bs Bs (T) + 12(k1)))
zak E + +2(
(ko,, k1) - Bs (K) + (k1)))
When at, 2 2 [K k1) + Bs (1 (kg) (kx))) it follows that Us... (Ka) - -k. - -3.., (k)) ck. 2 0, which means that the agent prefers to respond by taking arm ko rather than arm ky. This completes the proof of Lemma
Based on Lemma 9 we can directly prove Lemma 10
Lemma 10. Under the event E, we have Σi= 1 1, Too (t) S a
fo(t) } = 0.
21

---

Online Principal-Agent Information Acquisition
Proof of Lemma 10
When conducting binary search, the scoring rule Se falls within the segment (So(1), (1)) (refer fa(t)
Algorithm 3). It's worth noting that (t) " ko(t) Sk,,.. (1 (k(())
Ao(t) Su. fo(t) and (t) Spy,eo Therefore, the
scoring rule during the binary search can be represented as
S = a' a'S (0))
+ (1 - a²) S (c) (o(())
(37)
ta(t) where a ko()) S a' S 1. Hence, under assumption (t) (o(t),:z(t)) I also holds. We now consider two different scenarios.
foll) (k)))) the inequality Faste) (eote) (Ro(t), S a'
The first scenario arises during the binary search (from lo(4) + 1 to 1 (()), where the agent only responds by taking arm
(t) = (o) This implics that ko(t) kto(t)- However, the condition kt(t) * (t), together with the assumption I' (o (t), k1 (t)) S ka(t)
to(t) and Lemma implies that the agent cannot respond by taking ko (t) in the to (t) round, which
contradicts the definition of this scenario.
The second scenario emerges during the binary search, where the agent responds by taking an arm not equal to ky (t) at least once. However, given that ko (L) + kn (l), the assumption I' (o)( (Ko (4), ki (1) I
(t(
S a', and Lemma 9 the agent will
ku()))
not respond by taking ko (t) during the binary search. This also contradicts the definition of the scenario.
The above discussion implies that in every binary search, I' to)o (ko(t), As (t))
tal() (t))
Therefore, under the event E, we
have Σi= IBBS= to()) (t), Ra (t) S (k(()) J 0. Here finish the proof of Lemma 13
to(t)
We now utilize Lemma 11
12 and 13 to show that Et= 1 ( = to0) (ko(t), (t)
200) s Ex= Ng log)
Lemma 11 and Lemma 12 demonstrate how binary search can decrease In and establish the stopping criteria for essential binary search, respectively.
Lemma 11. For binary search (S(,,, S1, Amin Åmax, Ko, k1, to f1), we have
4K2M 72
(K k1) s 2 2
Bs
8
Proof of Lemmal 77 The proof of Lemma 11 directly follows the proof of Proposition F.9 in Chen et al. (2023).
Lemma 12. For binary search (S,,,, S1, Amin ko: K1, tu, 42), if event & happens and
(4K2
min ko N 2 (12Bs(aX, log
=Nko:
(38)
8
then we have at 2 Te k1) for t < t S T, and no more essential binary search ending with the same (ka, k1) is possible.
Proof of Lemmal 12
For any <t T, we have
a 2 ako
2 2log 74K2M22/8)
= =(125 Bss) (BBs
Ni.
2 (25- (2g1Bs)
2 2log
4K2
6
8
min (Ni
ku No
<4K2 ?2
2 (25-1 (e= 2log (
2
+2
+
v
N
/Nh
N
2 -2 2-
(lo(ko ki) Bs (T,(k)) + 12(k1))
li(ko,ki))
22

---

Online Principal-Agen Information Acquisition
where the first inequality is owing of is is parameter that is monotonically non-increasing over time, the first equality is due to the definition of . the first inequality is due to Eq (38) the second inequality is due N2 2 No Ak A, and the third inequality is owing to Lemma 11 Therefore, we conclude that after round E1, a is larger than I (Ko, k1) and no
more essential binary search will ending with (Ko, k1). Here we finish the proof of Lemma 12
Lemma 13. A binary search BS( S1, Amin: Amaxs for Ri tog (1) is essential binary search if and only if (Rig, k.) >
to Ko
The total number of essential binary searches rounds can be bounded by Ek=1 Ngm S =k== Ng log2(T) ") 2
>x (12Bs(aTs)
(T) log
4K2 1K2
Proof of Lemma
13
The result directly follows the proof of Lemma F.4 in Chen et al. (2023) and Lemma 12
F.3. Proof of 3
Proof of Lemma 5
We have
2(Bw + Bs)
h - +( (B5)
h un; + U22 (Kt) - 2(BB - Bs) 2(B, + (k)
(39)
h(8*) uny + us (Kt),
where the first inequality follows from the definition of kj, and the second and third inequalities follow from Lemma According to the definition of the termination round t, oz; must be less than I; otherwise, ;r = 0 cannot exceed 2( Bs B.)lg (k2), since the latter term is strictly positive. We have
C- -220 (Bs + Ba)
h(S*) un; + U.g.,r (kt) S B,
a/,
Moreover, since Sr S, = ux; 3kz + +11 - -ak; ( and the best response to S* is kiz we have
M(S*) - 1((5)) h(8*) - -uk; + Uai S.p +(1 (1-10),, )5p.. (k?)
axk (h((S) h((kz)) )) + (1 ax;) (h(S*) -u;; UBgg.r (k+t)
20 (Bs + B.) (1-o (1(S*) uk= + U.S (kt)) 2ah; (Bs + Ba) + (1 - ax; 3r+
(40)
where the last equality is owing to the definition B,. Note that E happens with probability at least (as shown in Lemma 2). we can conclude that S can satisfy the (e, coondiiin 3.. Here finish the proof of Lemma
F.4. Proof of Theorem 1
Proof of Theorem 7 Lemma directly shows that the estimated optimal scoring rule S satisfies condition 3 Here, we present the upper bound of the sample complexity. Recalling that Ti T2, and combining Lemma and Lemma we obtain
4K72 )) +1
(1+ (126-11) Bs) 210o (T) M log [KT7)) 1+
1
I (96 (66+48V2)H, M + log
(41)
23

---

Online Principal-Agent Information Acquisition
We define (97 + 48/2)2, Eq
be rewritten
Se 12s Bg) Ha logg(T) (M+
12s
(ogg(()M (MM log
(-8
(KK
))
(42)
=c 120 (Bs)
Ha log2(t) M 2log
(4KT2)
1
log²
(4K72
M
8
Define parameter A, such that
A S =C + 12: 11:-12eB Bs) 2
4KA22
HA loga (A)M
M + log
8
sc(1+ 1 12: Bs) 1 Ha logo(A)M
4KA 2)
M + log
8
<128c + 12s 1+12-BBss Bs) HA log2 ((A)1/2)
[4KA 1/4
M + log
(43)
$128c + 12: 125-11ss Bss Ha [1/4122 +2M
4KA
3/8
[4KA
1/2
+
8
2
2
4K
3/8
4K
1/2)
128c 1 1+ 12= 11:11---1- (es))))) HA M2 + 2M
+
8
where the third inequality is owing to v 2 (zg)(x) 2 log(z) for all x finally derive
> 0. Substituting Eq
(43
into Eg
we can
2 sc(1+ 1+ 12 He (l) M + 2og
4KT2
/4KT2
+ M
log?
8
(44)
Note that the right-hand side of the above upper bound does not contain т. Here we finish the proof of Theorem |
24

---

Online Principal-Agent Information Acquisition
G. Proof of Corollary
Following a similar approach as in the previous section, we split this analysis into three parts. First, we will establish an upper bound for T = =E== L(k; ). Then, in the second part, we will derive an upper bound for 72 = E 1 * k7). Finally, by summing the upper bounds of Ti and T2, and applying some basic algebraic manipulations, we obtain the upper bound for We will also demonstrate that, with the parameters specified in Corollary [ the estimated best arm satisfies condition
Upper bound T)
Under event &, we want to prove
C 16(Bs B.)
4K2 + K, A.
log
(45)
2
8
Suppose arm & is only triggered during the initialization phase; in this case, the result holds trivially. Furthermore, let tu represent the penultimate round in which arm k is observed, such that k* = ktz ke, Based on the stopping rule (line 15 of Algorithm]] T). we can derive that
Be S 22(B + Bs)
(46)
Note that based the setting in Corollary T it has 0 Be for all t. We substitute Eq confidence style confidence radius) into Eq (46) and derive
9
(the definition of the fixed
4BB + Bu)²
4K2
C c +1
A M
log
+1
P7.
4(Bs + Bu)²
4K22
log
+1
(47)
P
16 Bs + B.)² 22
4K22 y2
log
+ 1,
where the first equality is owing to the definition of tx and C. the third inequality is owing to ty S 5 and the last incquality owing to 3r, 2 2. With the last term in Eq (47). we can derive Eq 45). and
16(Bs + BB)2K
4K2M,2
C
log
K
2
7K2M,2
(48)
=411. log
+ K
<AK+2 (445²) + K.
<Alle M + log
Upper bound T2
Based on the discussion the previous section, if happens, we have
Ngm
[2Bs (afe) "1) (oog(())
[K22 72
(49)
4Kr2 8
1152H, B&E (ogg(())
M + log
Note that the event occurs with probability at least 8. By combining Eq (45) and Eq (49) and following the steps outlined in the previous section, conclude that the following holds with probability at least -6: 6:
Upper bound 7 and demonstrate S' satisfies Eq 3
(50)
25

---

Online Principal-Agent Information Acquisition
Furthermore, following the reasoning in the proof of Lemma 5 the proof of Corollary
we can show that S satisfies Eq
This concludes
26

---

Online Principal-Agent Information Acquisition
H. Proof of Theorem 2
Proof sketch of Theorem 2 In Lemma 14, we demonstrate that OIAFB will output an estimated best scoring rule if and only if0 0 < a 144H, Bg= (T) Furthermore, we show that, within the event E, if the simple regret h(S*) h(S²)
exceeds c, then T S 4aH.+K. K. follows that selecting
(T-K 4HH, MAA (Tg leads to T > 4H K, which contradicts our previous findings. Consequently, within the event E, OLAFB will yield an estimated scoring rule
min
T
with simple regret no larger than Additionally, Lemma 2 indicates that the event & occurs with probability of at least
1 1 TK2M e 1aa when adopting the confidence radius defined in Eq (TO).
T Lemma 14. Suppose O < <ac < 144H, B&e (T) Under event &, if((5*) - MS²*) > 6, then we have T S 44Ha + K.
Proof of Lemma 14 Note that OIAFB will return an estimated best scoring rule if and only if " [ - kī} is greater than 1 (see Algorithm 2 for details). When we select T as defined in Eq (10). ET= 11 [kk * ky) can be bounded by 144H, 2 logz(? (T) (similarly to Lemma 4 and using m S ITg2(T) ) in the fixed-budget literature). Thus, to ensure that OIAFB outputs an estimated best arm, a must satisfies 0 < a < 144H, B 2 IT)
We want to show C S 4H,a + 1, for all & A. If arm k is only triggered in the initial phase, this inequality trivially holds. Otherwise, define to as the penultimate round that arm is triggered by the agent and K2 kç. has
> - 2a (Bs + B.) = 3
2(Bs + B 2 2sBs + BB)D (R²) 2 h(5*) - ug- + Ug. (k*)
(51)
of.
where h- is the best response of S*. The first inequality of Eq inequality is based on Eq (39). and the third inequality is owing to
511 is owing to the definition of k and 8", the second
MSS* ug- + (k+) h(S*) - h(S²) - aa (h(S*) - -h(Sa.)
ok
h(5²)) - 1(S²) ( + +B))
(52)
1- a
20 + Bu) 1-oh 0
where the first equality is based on the second equality of Eq (40). Based on Eq 5I), the definition of fixed budget style (k) and the definition of tk. is easy to derive
Bu) 4(Bs +
CT = c +15 +15
+ 1, Vk A.
(53)
This implies
K T
4K(Bs + B.y) Pa
CT.
K.
(54)
B3
1mm
According to the setting that af B..)+B.)' we have Bg 2 s.
This means
2
T T 4Haa + K.
(55)
Here we finish the proof of Lemma 14
Proof of Theorem 2 If we set 2 log (TK2M) S a < min
TT-K iH, 144H1 Bg. logg(T)
T
it indicates that 4H. + K < T. T-K
which contradicts the previous result. Therefore, under event E, if 2 log (TK2
S a 144H, max (Bge-2.1) [T)
T-K min
THE 144H, (Tg then h(S*) - 1($5)) < e. According to Lemma
T
E will happen with probability at least
1 M - ta if we set 12 as Eq 1Tp. This implies 5 < TK2M to < This completes the proof of Theorem 2
27

---

Online Principal-Agent Information Acquisition
I. Proof of Corollay 2
Due to a = 2 log (TK2* /6) should be smaller than
T-K
T should satisfies
144H, max
(Bze 2,1) (T)
TK (5))
T > 288/1 max (B3E 2, logg(T) (T)
M + log
+ K.
(56)
We define r
1152H, max (B3=-2,1)
(M (K/6)1/22 + K then
1152H, max (B3--3 1) M + (K/0) + k
21152H, max (B3 - 1) [T M (TK/O)) +
(57)
21152H, max (B3e 2 1) loga (1 M + log
(o (1TK18)/2)) + K
> 288 max (Bze loga (T) M + log (TK/8)) + K,
where the first inequality is owing to log(#) I logz (2) S v for all x > If
T = 288 max (B3 logz (T) M 1 log (TK/6)) K
(58)
then, we have r > T, and Eq 56 trivially holds. Finally, by substituting = 2log (TK2M /8) into TK2M 6 t0 we obtain 8 < 8.
28


Reviews:
[{"review_id": "uuykOLS8Im", "reviewer": "Reviewer_aBfB", "summary": "This work considers optimal scoring rules for principal/agent problems in online settings, in two variants: with a fixed budget, or fixed confidence, where the principal is trying to make investment decisions based on the knowledge/actions of the agent. The utility of the principal is driven by the quality of the knowledge/actions of the agent. \n\nPrior work in scoring rules usually focuses on offline settings, so generating optimal fixed scoring rule according to a metric like minimizing regret on the principals part. Chen et al [2023] had studied the online setting with fixed confidence target, with a large instance-independent sample complexity bound.\n\nThis work adds instance-dependent parameters to the algorithm and the analysis, which improves both actual performance and sample complexity bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the novelty and importance of our work. We truly appreciate your encouraging feedback.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear theoretical evidence and proofs.", "methods_and_evaluation_criteria": "Yes, the theoretical methods make sense for the problem at hand.", "theoretical_claims": "I did not verify proof correctness.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work improves significantly on the literature for online best scoring rule identification, with improved performance and sample complexity bounds that brings bounds closer to online bandit sample complexity.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "The paper is well written and consistently raises the higher-level conceptual impacts and meanings of different aspects, starting from succinctly covering the reason these bounds should exist: the large gap between performance in non-incentive-based online bandit problems and the online scoring rule from Chen et al. 2023.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "none", "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": "fqITH0rWQT", "reviewer": "Reviewer_DrTq", "summary": "The paper addresses the Best Scoring Rule Identification problem, proposing two algorithms: OIAFC (Online Information Acquisition Fixed Confidence) and OIAFB (Online Information Acquisition Fixed Budget). These algorithms aim to identify the optimal scoring rule through online learning. The key contributions are the introduction of a novel method to balance exploration and exploitation, the use of conservative scoring rules, and the design of efficient stopping and decision rules. The paper provides theoretical upper bounds for the sample complexity of these algorithms, showing that they can identify an estimated optimal scoring rule with high confidence, achieving instance-dependent and instance-independent bounds. The algorithms are evaluated in both fixed-confidence and fixed-budget settings, with an emphasis on improving sample efficiency compared to previous methods.", "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 sincerely thank you for your comments and questions.\n\n**About the references:**\n\nThank you for pointing out these relevant references. We will include the three suggested papers in our revised manuscript. We greatly appreciate your helpful suggestion.\n\n**About the Experiments:**\n\nThank you for your suggestion. In response, we have conducted additional experiments to validate the effectiveness of our proposed algorithm OIAFC.Thank you for your suggestion. We present several experimental results here to demonstrate the effectiveness of our algorithm OIAFC.\n\n**Experiment 1:**  \nWe set $B_S = 1$, the number of actions $K = 3$, the number of beliefs $M = 3$, and the number of states = 2.  \nWe vary the minimum reward gap between the best arm and the sub-optimal arm from 0.1 to 0.5 by adjusting $q_1,...,q_K$ and $c_1,...,c_K$.  We set $\\delta = 0.05$ and $\\epsilon = 0.1$. The results are presented in Table 1.\n\n**Experiment 2:**  \nWe fix the minimum reward gap at 0.2 and vary both the number of arms and the number of beliefs simultaneously from $\\{2, 4, 6, 8, 10\\}$, i.e., the number of arms equals the number of beliefs in each setting.  \nAll other settings are the same as in Experiment 1. The results are presented in Table 2.\n\nEach data point in the table is the averaged over 10 independent runs.\n\n**Table 1:**\n| Reward gap | Samples   |\n|------------|-----------|\n| 0.5        | 8909.4    |\n| 0.4        | 13972.5   |\n| 0.3        | 46331.3   |\n| 0.2        | 69542.0   |\n| 0.1        | 117963.8  |\n\n**Table 2:**\n| Arm and belief number | Samples   |\n|-----------------------|-----------|\n| 2                     | 54732.6   |\n| 4                     | 77321.5   |\n| 6                     | 89125.4   |\n| 8                     | 10052.9   |\n| 10                    | 113592.4  |\n\nAs shown in Tables 1 and 2, the sample complexity increases as the reward gap decreases and as the number of arms and beliefs grows. These trends are consistent with theoretical expectations, since smaller gaps and larger action spaces make accurate identification more challenging.\n\n**Q1**：Can you provide more detailed explanations or examples of how the reward gap and problem complexity are calculated in practical scenarios?\n\n**A1**: Thank you for your question. We would like to clarify that our algorithm does not require knowledge of the reward gap or the instance-dependent problem complexity. These quantities—such as the reward gap and instance-dependent problem complexity—are unknown to the algorithm and are not used as inputs. Their role is purely theoretical, as they only appear in the analysis of sample complexity upper bounds. This is analogous to the setting in pure exploration bandit problems].\n\n**Q2：** Can you elaborate on how the selection of the parameters alpha and beta affects the performance of the algorithm, especially in terms of sample complexity and exploration vs. exploitation balance? \n\n**A2:** Thank you very much for your thoughtful question. Since our work focuses on the pure exploration setting, our algorithm is not concerned with the exploration–exploitation trade-off as in the regret minimization setting. The parameter $\\alpha$ in our algorithm is used to balance the trade-off between exploration to identify the best scoring rule and exploration to estimate the feasible region $\\mathcal{V}_k$ as shown in line 10 of Algorithm 1. The parameter $\\beta$ is used in the breaking rule in line 15 to determine whether the optimal scoring rule has been attained with high probability.\n\nSpecifically, if $\\alpha$ is relatively large, the algorithm is more inclined to prompt the agent to choose the action we wish it to take, which reduces the number of binary searches required. For example, in the extreme case where $\\alpha_k^t = 1$ for all $t$, the OIAFC algorithm would directly present the action-informed oracle of arm $k$, and the agent respond with $k_t = k$. However, this could potentially lead to an increased simple regret $h(S^*) - h(S_t)$, requiring more regular rounds to estimate a suitable $\\hat{S}^*$ that satisfies the feasibility condition. Conversely, if we choose $\\alpha_k^t = 0$ for all $t$, due to the absence of accurate estimation for the feasible region $\\mathcal{V}_k$, the agent may not return the desired arm. In this case, the algorithm needs to perform more binary searches to estimate $\\mathcal{V}_k$.\n\nAs for $\\beta$, setting it too high may cause the algorithm to terminate prematurely with a small number of samples, but the estimated best scoring rule may not satisfy the required condition. On the other hand, if $\\beta$ is set too low, the algorithm becomes overly conservative and continues sampling until the reward gap between the estimated and true best scoring rule is much smaller than the target threshold $\\epsilon$, which may lead to significantly higher sample complexity than necessary.", "claims_and_evidence": "The claims made in the submission are generally supported by theoretical evidence. However, a few claims could benefit from more empirical or practical validation:\n- Sample Complexity Bounds: While the paper presents theoretical upper bounds for sample complexity (both instance-dependent and independent), these bounds are derived under certain assumptions (e.g., the agent's behavior and the confidence levels). These claims could be seen as problematic if not empirically validated, especially since sample complexity is highly dependent on specific real-world conditions that are not fully addressed in the paper.\n- The claim that forced exploration via binary search is efficient is supported theoretically, but the practical impact on performance (e.g., in terms of time or sample efficiency) is not clearly demonstrated. Empirical evidence or simulation results would help verify the actual effectiveness of this approach in practice.\n- While the paper compares its results to prior work (like Chen et al., 2023), the paper primarily focuses on theoretical performance without empirical validation or concrete case studies. This leaves the claim that the proposed method is more efficient somewhat unsubstantiated outside the theoretical context.", "methods_and_evaluation_criteria": "The OIAFC and OIAFB algorithms are well-suited to the problem as they are designed to identify the best scoring rule efficiently under both fixed-confidence and fixed-budget settings. These algorithms take into account the reward gap and problem complexity, which are critical for addressing the exploration-exploitation trade-off inherent in the multi-armed bandit framework. The use of conservative scoring rules, forced exploration, and binary search strategies are appropriate for ensuring that the best arm is identified with minimal sample complexity.\n\nThe evaluation criteria, specifically the sample complexity bounds (both instance-dependent and independent), are appropriate for measuring the efficiency of the proposed methods. The focus on deriving upper bounds for sample complexity is standard in MAB research, allowing for a theoretical assessment of the algorithm's performance. Additionally, the use of (ϵ, δ)-optimality as a measure of success aligns with common practices in bandit theory.\n\nWhile the theoretical evaluation is solid, the absence of empirical results or benchmarks (e.g., performance on real or simulated datasets) makes it harder to assess the practical utility of the methods in real-world applications. Including empirical validation against standard MAB benchmarks would strengthen the claim that these methods are practically applicable.", "theoretical_claims": "High-level but did not follow the details and appendix. Based on the main submission, the proofs referenced in Lemmas, and Theorem 1 seem logically consistent with standard practices in multi-armed bandit theory, particularly around sample complexity bounds and exploration strategies, but admit for not detail following every steps in mathematical proofs.", "experimental_designs_or_analyses": "no experimental designs in the paper.", "relation_to_broader_scientific_literature": "The key contributions of the paper—specifically the OIAFC and OIAFB algorithms—build on existing work in the Multi-Armed Bandit (MAB) literature, particularly in the context of best arm identification and optimal scoring rule problems. The approach extends prior work on bandit algorithms by introducing a more nuanced trade-off between exploration and exploitation, which improves the sample complexity bounds.\n\nThe paper distinguishes itself by introducing new parameters that fine-tune the balance between normal and forced exploration, contributing to a more efficient sample complexity, especially in instance-dependent settings. This contrasts with prior methods like those in Chen et al. (2023), which use simpler parameterization and result in higher sample complexity. Additionally, the comparison to Jin et al. (2018) highlights the inefficiencies of their naive breaking rule, further demonstrating the novelty and practical improvements of the proposed methods. In summary, the paper builds on established MAB and best arm identification frameworks but introduces more refined techniques for better sample complexity, offering an improvement over previous approaches.", "essential_references_not_discussed": "The paper cites important works like Chen et al. (2023) and Jin et al. (2018), below lists additional papers that might provide related works in the broader best-arm identification and exploration-exploitation trade-off literature. Specifically:\n- the work of Auer et al. (2002) on UCB (Upper Confidence Bound) algorithms is foundational and could help provide context for understanding the theoretical underpinnings of the proposed algorithms.\n- The paper mentions fixed-budget and fixed-confidence settings, Kalyanakrishnan et al. (2012) might also be relevant to provide a more comprehensive understanding of multi-armed bandit algorithms under these constraints.\n- While the paper introduces a more efficient exploration strategy, Lattimore and Szepesvári (2018) might also be relevant.", "other_strengths_and_weaknesses": "Strengths:\n- The paper introduces a novel algorithm (OIAFC) for best scoring rule identification, combining existing bandit methods with a conservative scoring rule to improve exploration efficiency. This approach is an interesting extension of prior work.\n- The theoretical contributions are impactful, offering a refined understanding of sample complexity in the best arm identification problem, with applications to optimal scoring rule determination.\n- The writing is generally clear, especially in explaining the algorithm’s workings and key definitions.\n\nWeaknesses:\nWhile the theoretical analysis is strong, there is little practical evaluation or comparison with state-of-the-art algorithms, which weakens the paper's applicability in real-world scenarios.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Can you provide more detailed explanations or examples of how the reward gap and problem complexity are calculated in practical scenarios? \n\n2. Can you elaborate on how the selection of the parameters alpha and beta affects the performance of the algorithm, especially in terms of sample complexity and exploration vs. exploitation balance? also the theoretical results mention upper bounds for the sample complexity, but it’s unclear how these bounds behave in practice with varying values of M, K, and the other parameters.", "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": "0BB8pTLvSK", "reviewer": "Reviewer_XcZh", "summary": "The paper studies how to learn scoring rules within the principal-agent problem for information acquisition. In particular, the authors study how to identify approximately optimal scoring rules with high probability through interaction with the environment. They design two algorithms depending on whether the setting is with fixed confidence or fixed budget. The first algorithm guarantees both an instance-dependent and an instance-independent bound with $O(1/\\epsilon^2)$ samples, where $\\epsilon$ is the required accuracy. This improves upon the $O(1/\\epsilon^3)$ bound of Chen et al. (2023).  The second algorithm fixes the number of samples (budget) and identifies approximately optimal scoring rules.", "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 sincerely thank you for your insightful comments and questions, which have helped us improve the quality of our work.\n\n**Q1:** Why are the algorithms of Chen et al. and Cacciamani et al. suboptimal for sample complexity problems?\n\n**A1:** Thank you for the question. \n\nThe primary reason for the suboptimal sample complexity in Chen (2023), aside from choosing an inappropriate parameter, is the adoption of a suboptimal termination criterion. Specifically, Chen (2023) employs the breaking rule originally introduced by Jin (2018), which terminates the algorithm after $\\tilde{O}(\\varepsilon^{-6} K^6 C_{\\mathcal{O}}^3)$ iterations and selects the scoring rule identified in the final round as the best estimate. This termination strategy is inherently inefficient because it intuitively demands a large number of samples to ensure the accuracy of the identified scoring rule. In contrast, our proposed breaking rule (line 15 in Algorithm 1) and corresponding decision rule (line 16 in Algorithm 1) enable a more efficient evaluation of whether a scoring rule satisfies the necessary conditions. Consequently, our approach achieves significantly improved sample complexity.\n\nFor Cacciamani (2023). We believe Cacciamani’s ETC algorithm can achieve a sample complexity bound of $K/\\epsilon^2$ by carefully selecting the exploration phase based on the $\\epsilon$. However, obtaining an instance-dependent sample complexity bound from ETC-based methods is challenging due to the necessity of setting the exploration phase length in advance, without prior knowledge of the actual instance-specific reward gaps or problem complexity. To our knowledge, there are currently no known ETC-based fixed confidence best arm identification algorithms in MAB problems that achieve instance-dependent complexity results. \n\nIn summary, our algorithm achieves near-optimal instance-dependent sample complexity due to: (1) the selection of appropriate parameters, (2) the design of suitable breaking and decision rules, and (3) the adoption of an effective algorithm structure (UCB).\n\n**Q2:** At line 173 in the \"fixed budget\" paragraph it is unclear which are the inputs of the problem (I guess $T$) and which are the outputs (I guess $\\epsilon$ and $\\delta$).\n\n**A2:** Thank you for your question. In the fixed budget setting, $T$ and $\\epsilon$ are the inputs, while $\\tilde{\\delta}$ is the output (the smaller the $\\tilde{\\delta}$, the better the algorithm’s performance). We will clarify this in the revisednext version of our paper.\n\n**Q3:** Why is the dependency on $1/\\epsilon^2$ required also in instance-dependent bounds?\n\n**A3:** Thank you for this insightful question.\n\nTo find the near-optimal scoring rule, we must identify both the best arm $k^*$ and the set of scoring rules that can trigger the best arm, denoted by $\\mathcal{V}_{{k^*}}$. Intuitively, the dependency on $1/\\Delta_i^2$ arises from identifying the best arm, whereas the dependency on $1/\\epsilon^2$ emerges because, even after identifying the best arm, additional samples are required to estimate the set $\\mathcal{V}{k^*}$ at an $\\epsilon$-accurate level. Only then can we determine a scoring rule that meets the required accuracy.\n\n**Reference:**\n\nChen, S., Wu, J., Wu, Y., & Yang, Z. (2023, July). Learning to incentivize information acquisition: Proper scoring rules meet principal-agent model. In International Conference on Machine Learning (pp. 5194-5218). PMLR.\n\nCacciamani, F., Castiglioni, M., & Gatti, N. (2023). Online information acquisition: Hiring multiple agents. arXiv preprint arXiv:2307.06210.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I didn't check the appendix.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper studies problems related to best arm identification for information acquisition. Previous works focus on the related problem of regret minimization.", "essential_references_not_discussed": "None, although a more comprehensive comparison with Cacciamani et al. (2023) could be beneficial. Indeed, since it generalizes the problem studied in the paper, their techniques can in principle be applied to the paper setting.", "other_strengths_and_weaknesses": "The problem of learning how to incentivize information acquisition is interesting. The paper improves upon the guarantees of Chen et al. (2023). \n\nThe authors discuss extensively the relatrion between their work and Chen et al.. However, it remains unclear how novel the presented algorithm is since the structure is very similar to Chen et al. It would be interesting to better highlight the algorithmic contributions (except with setting parameters differently), and why the algorithm of Chen et al. fails to achieve optimal bounds.\n\nI feel that also a more extensive comparison with Cacciamani et al. is required. Indeed, their work can be applied to your problem. Since the algorithm of Cacciamani et al. has an explore then commit flavor and achieve $T^{2/3}$ regret, I would not be surprised if it directly implies a $1/\\epsilon^2$ sample complexity bound.", "other_comments_or_suggestions": "At line 173 in the \"fixed budget\" paragraph it is unclear which are the inputs of the problem (I guess T) and which are the outputs (I guess $\\epsilon$ and $\\delta$).", "questions_for_authors": "Why are the algorithms of Chen et al. and Cacciamani et al. suboptimal for sample complexity problems?\n\nWhy is the dependency on $1/\\epsilon^2$ required also in instance-dependent bounds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EEZj3bKYu3", "reviewer": "Reviewer_ksDs", "summary": "This paper studies a principal-agent problem, where the principal aims at learning the optimal scoring rule for that problem. Notably, it proposes pure exploration algorithms in both settings of fixed budget and fixed confidence", "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": "Thank you for your valuable feedback, which has greatly contributed to improving our work.\n\n**Q1:** My main concern about this work is about the (over)complexity of the setting ... help in that direction.\n\n**A1:** Thank you for your insightful comment. We understand the concern about complexity, and we’d like to clarify why our framework is intentionally more involved than works like Scheid (2024).\n\nThe key difference from Scheid (2024) lies in the presence of an underlying state in our setting. The principal in our setting seeks to acquire high-quality information about this hidden state through the agent’s report, as the report quality and the underlying state-generating process have a direct impact on the principal’s profit. To achieve this, the principal designs a scoring rule that incentivizes the agent to conduct a good investigation (action) and report truthfully. This setup closely mirrors real-world scenarios—such as a manager hiring a domain expert to assess a situation—where **the profit of the principal depends on the true state and the quality of the report, not just the agent’s action**. \n\nIn contrast, the setting of Scheid (2024) does not involve an underlying state—the principal’s objective is to induce a desirable action via a payment rule. While this is suitable for scenarios where **the principal’s profit depends directly on the agent’s action**, it is less appropriate for richer interactions such as the manager–expert example introduced earlier.\n\nAnother advantage of our setting is its generality—it subsumes several important principal–agent problems as special cases, including the contract design problem (see the discussion in Chen (2023), Appendix B).\n\n**Q2:** Also, the agent is here assumed to be myopic... Moreover, the agents are even assumed to be truthful...\n\n**A2:** Thank you for your comment. Assuming the agent is myopic is a standard modeling choice in famous online principal–agent problems (e.g., Zhu 2022; Chen 2023; Scheid 2024). This is mainly because, in practice, the agent often lacks sufficient information about the principal’s future policy, making it difficult for them to plan long-term strategies that maximize their own profit. We agree that relaxing the myopic assumption and studying strategic, far-sighted agents is an interesting direction for future work.\n\nAdditionally, we would like to clarify that our framework focuses solely on proper scoring rules. By the revelation principle, this restriction will not result in any loss of optimality in terms of the principal’s expected profit [Chen (2023), Cacciamani et al. (2023)]. Therefore, our goal is to identify an optimal rule within the set of proper scoring rules that maximizes the principal’s expected profit. Thus we do not need to transform arbitrary scoring rules into proper ones.\n\n**Q3:** It is not clear what is the ... $p$ is necessary.\n\n**A3:** Thank you very much for your question. The principal is assumed to know its own utility function $u$. We respectfully notice that in the UCB-LP, there is no parameter named $p$. If your question refers to $q$, which denotes the distribution over the agent’s belief, then indeed the principal does not know it. Instead, the principal must gradually learn this belief distribution over time based on interactions with the agent (see Section 4.2).\n\n**Q4:** What is the value of $B_S$ in Lemma 1 ?\n\n**A4:** The constant $B_S$ is a boxing parameter that bounds the payment of the scoring rule $S$. Specifically, we assume $\\| S \\|_{\\infty} < B_S$. \n\n**Q5:** How computationally intense is the solving of the LP programming in UCB-LP?\n\n**A5:** Thank you for your question. Our UCB-LP involves parameters and constraints that are polynomial in the number of arms $K$ and the number of belief $M$. Therefore, the LP can be solved in polynomial time w.r.t. $K$ and $M$. We also note that a similar LP was solved by Cacciamani (2023) (see their Eq (2)),  who provided a discussion on its computational complexity in Corollary 3.2, further supporting the tractability of our approach.\n\n**Q6:** Line 310 ... are happy about.\n\n**A6:** Thank you very much for your question. Our paper primarily focuses on the pure exploration setting, which is analogous to the pure exploration problem in the bandit literature [Lattimore (2020)]. In this context, we typically do not consider the regret incurred during the exploration phase. That said, there has been published work in the bandit literature on minimizing regret while identifying the best arm. We view this (minimizing regret and identifying the best scoring rule) as a valuable direction for future research.\n\n**Reference:**\n\nChen (2023). Learning to incentivize information acquisition.\n\nCacciamani (2023). Online information acquisition: Hiring multiple agents.\n\nLattimore (2020). Bandit algorithms.\n\nZhu (2022). The sample complexity of online contract design. \n\nScheid (2024). Incentivized learning in principal-agent bandit games.", "claims_and_evidence": "See below", "methods_and_evaluation_criteria": "See below", "theoretical_claims": "See below", "experimental_designs_or_analyses": "See below", "relation_to_broader_scientific_literature": "See below", "essential_references_not_discussed": "See below", "other_strengths_and_weaknesses": "See below", "other_comments_or_suggestions": "The problem of learning optimal pricing/scoring rules in principal agent is interesting and has been widely considered in the literature, as suggested by the related work section of this paper.\n\nMy main concern about this work is about the (over)complexity of the setting. I indeed find it quite overcomplicated, while similar ideas and messages can be found with much simpler problems. Notably, I fear that the Assumption 1, along with the fact that the agent plays before observing the nature state (which leads to Equation 5), makes this problem nearly equivalent to much simpler settings considered in the literature, such as the mentioned work of Scheid et al (2024). While the setting should be more intricate here, the Assumption 1 drastically simplifies the setting, ending up in something close to Scheid et al (2024), but in a pure exploration setting. If that is indeed the case, I would have just preferred an adaptation of this simpler setting to pure exploration.\n\nThis overcomplexity also makes the paper unnecessarily unclear: there are a lot of technical notations and considerations and it is hard to read through. I really think that the use of a simpler, but morally similar setting, would clearly help in that direction.\n\nAlso, the agent is here assumed to be myopic, i.e., they only react optimally to the current scoring rule. An agent could be nastier in reality, manipulating the learning of the principal so that it can maximize their own reward. Moreover, the agents are even assumed to be truthful, based on the existence of proper scoring rules. \nWhile Myerson guarantees the existence of an optimal proper rule, how easy is it to transform any scoring rule into a proper one? This would probably require some knowledge of the game environment, that the principal does not have at the beginning of the game here (+ a potentially intensive computation).\n\n----------\n\nHere are more minor remarks/comments:\n- it is not clear what is the exact knowledge of the principal? Notably for the UCB-LP formulation, it seems that knowledge of the outcome probability $p$ is necessary\n- what is the value of B_S in Lemma 1 ? I guess it cannot be made arbitrarily small\n- How computationally intense is the solving of the LP programming in UCB-LP?\n- line 310: if $k_t=k_t^*$, this could also mean the principal is overpaying, which is not something we are happy about", "questions_for_authors": "see above", "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: The reviewers found the work appealing and were generally in its favor. While they raised some issues, they did not find them to be sufficiently problematic to submit a single negative opinion (but, also, they did not engage much in defending the paper).
Decision: Accept (poster)