Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition

Thank you for your valuable feedback, which has greatly contributed to improving our work.

Q1: My main concern about this work is about the (over)complexity of the setting ... help in that direction.

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

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

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

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

Q2: Also, the agent is here assumed to be myopic... Moreover, the agents are even assumed to be truthful...

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.

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

Q3: It is not clear what is the ... $p$ is necessary.

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

Q4: What is the value of $B_S$ in Lemma 1 ?

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

Q5: How computationally intense is the solving of the LP programming in UCB-LP?

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.

Q6: Line 310 ... are happy about.

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.

Reference:

Chen (2023). Learning to incentivize information acquisition.

Cacciamani (2023). Online information acquisition: Hiring multiple agents.

Lattimore (2020). Bandit algorithms.

Zhu (2022). The sample complexity of online contract design.

Scheid (2024). Incentivized learning in principal-agent bandit games.

We sincerely thank you for your insightful comments and questions, which have helped us improve the quality of our work.

Q1: Why are the algorithms of Chen et al. and Cacciamani et al. suboptimal for sample complexity problems?

A1: Thank you for the question.

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

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

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

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

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.

Q3: Why is the dependency on $1/\epsilon^2$ required also in instance-dependent bounds?

A3: Thank you for this insightful question.

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

Reference:

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

Cacciamani, F., Castiglioni, M., & Gatti, N. (2023). Online information acquisition: Hiring multiple agents. arXiv preprint arXiv:2307.06210.

We sincerely thank you for your comments and questions.

About the references:

Thank you for pointing out these relevant references. We will include the three suggested papers in our revised manuscript. We greatly appreciate your helpful suggestion.

About the Experiments:

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

Experiment 1:
We set $B_S = 1$, the number of actions $K = 3$, the number of beliefs $M = 3$, and the number of states = 2.
We 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.

Experiment 2:
We 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.
All other settings are the same as in Experiment 1. The results are presented in Table 2.

Each data point in the table is the averaged over 10 independent runs.

Table 1:

Table 2:

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

Q1：Can you provide more detailed explanations or examples of how the reward gap and problem complexity are calculated in practical scenarios?

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

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?

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.

Specifically, 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$.

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

Thank you for recognizing the novelty and importance of our work. We truly appreciate your encouraging feedback.