Skip to content

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

🕒 Published (v1): 2025-05-23 01:30 UTC · Source: Arxiv · Venue: ICML 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper addresses Best Scoring Rule Identification (BSRI) in online principal-agent information acquisition: a principal iteratively learns which scoring rule (incentive payment scheme) best elicits high-quality information from a strategic agent. Two algorithms—OIAFC (fixed confidence) and OIAFB (fixed budget)—achieve the first instance-dependent sample complexity bounds and substantially improve prior instance-independent bounds.

Problem

Prior online information acquisition work (Chen et al., 2023; Cacciamani et al., 2023) focused on regret minimization, not best-rule identification. For BSRI specifically: (1) no instance-dependent sample complexity bounds existed; (2) the fixed-budget setting was entirely unexplored; (3) the best known instance-independent bound was \(\tilde{O}(C_O^3 K^6 \varepsilon^{-3})\), far worse than the \(\tilde{O}(K\varepsilon^{-2})\) of standard best-arm identification (BAI) in MABs. The added difficulty over MABs is that the principal cannot directly pull an arm—it must design a scoring rule to incentivize the agent, while simultaneously learning the agent's belief distributions \(\{q_k\}\) and private cost structure.

Method

The approach reduces BSRI to a bandit-like problem in three layers:

  1. LP reformulation. For each arm \(k\), the principal's optimal profit is \(h(S_k^*) = \max_{S \in V_k} (u_k - v_S(k))\) where \(V_k = \{S \mid \langle q_k - q_{k'}, S\rangle_\Sigma \geq C(k,k'), \forall k'\}\) is the agent's best-response region. The principal solves \(\text{LP}_k\) if \(q_k\) and \(C(k,k') = c_k - c_{k'}\) are known.

  2. UCB-LP\(_{k,t}\). Unknown quantities \(q_k\) and \(C(k,k')\) are estimated empirically (\(\hat{q}_k^t\), \(\hat{C}^t(k,k')\)) with confidence radii \(I_q^t(k)\) and \(I_c^t(k,k')\). UCB-LP\(_{k,t}\) substitutes these into \(\text{LP}_k\) with optimistic inflations to produce an upper-confidence value \(\hat{h}_k^t\).

  3. Conservative scoring + binary search. Because \(\hat{S}_{k^*,t}\) alone may fail to induce arm \(k^*\), OIAFC uses \(S_t = \alpha_{k^*}^t \tilde{S}_{k^*} + (1 - \alpha_{k^*}^t)\hat{S}_{k^*,t}\), mixing the action-informed oracle rule with the estimated optimal. If the agent deviates (\(k_t \neq k_t^*\)), a binary search on the oracle-to-estimated convex combination refines the boundary of \(V_{k^*}\). Exploration stops when \(2(B_S + B_u)I_q^t(k_t^*) \leq \beta_t\).

OIAFB follows the same structure but uses a fixed interaction budget \(T\) and replaces the stopping condition with a time-based criterion; the confidence radius adopts the fixed-budget form \(I_q^t(k) = \sqrt{a/N_k^t}\).

Key Contributions

  • First instance-dependent BSRI bound (OIAFC, fixed confidence): \(\tilde{O}\!\left(M\!\left(\sum_{k \neq k^*} \Delta_k^{-2} + \varepsilon^{-2}\right)\right)\), where \(\Delta_k = h(S^*) - h(S_k^*)\) and \(M \leq K \times C_O\).
  • Improved instance-independent bound (OIAFC, fixed confidence): \(\tilde{O}(MK\varepsilon^{-2})\), beating Chen et al. (2023)'s \(\tilde{O}(C_O^3 K^6 \varepsilon^{-3})\).
  • Fixed-budget algorithm (OIAFB): matches OIAFC's instance-independent rate with budget \(T = \tilde{O}(MK\varepsilon^{-2})\); first fixed-budget result for BSRI.
  • Both algorithms match classical MAB BAI complexity up to the \(M\) factor arising from belief-distribution learning.

Results

  • Instance-independent (OIAFC): \(\tilde{O}(MK\varepsilon^{-2})\) samples vs. prior \(\tilde{O}(C_O^3 K^6 \varepsilon^{-3})\) (Chen et al., 2023) — exponential improvement in \(K\) and \(\varepsilon\).
  • Instance-dependent (OIAFC): \(\tilde{O}\!\left(M(\sum_{k\neq k^*}\Delta_k^{-2} + \varepsilon^{-2})\right)\) — first such result; aligns with MAB instance-dependent BAI up to the \(M\) factor.
  • Fixed-budget (OIAFB): given \(T = \tilde{O}(MK\varepsilon^{-2})\), identifies an \((\varepsilon,\delta)\)-optimal scoring rule — matches OIAFC's instance-independent rate.
  • In the degenerate case where \(M=1\) (single belief outcome), instance-dependent bound recovers the standard MAB result exactly.

Limitations

  • Action-informed oracle required: the algorithm assumes \(K\) pre-supplied scoring rules \(\{\tilde{S}_k\}_{k=1}^K\) that each guarantee the agent selects arm \(k\); obtaining these in practice may be non-trivial.
  • Observable actions: assumes the principal can always observe which arm \(k_t\) the agent selected; violates standard hidden-effort settings.
  • Stationary environment: analysis assumes fixed \(\{q_k, c_k\}\); non-stationary or adversarial agents are not addressed.
  • \(M\) overhead: the \(M \leq K \times C_O\) factor can be large; the gap from pure MAB complexity is not fully closed.
  • No lower bounds for instance-dependent setting: matching minimax lower bounds for BSRI are not provided, leaving tightness open.

Relevance to Harnesses / Meta-Harnesses

The scoring rule functions as an incentive harness—a designed wrapper around the agent that steers its behavior toward a principal-preferred outcome without directly controlling it. The iterative, feedback-driven process of tightening this harness (UCB-LP plus binary search to refine response regions) is structurally analogous to a meta-harness loop that adaptively reconfigures sub-agent incentives based on observed compliance. For researchers tracking harness design in multi-agent systems, this paper offers rigorous sample-complexity guarantees for when an outer controller must learn, rather than assume, the parameters needed to reliably govern an inner strategic agent—a gap that empirical harness frameworks rarely address formally.