Research map / Bandits and online learning / Multi-armed bandits

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

ICML 2025 · Bandits and online learning › Multi-armed bandits · approach: Pure exploration algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes OIAFC and OIAFB, fixed-confidence and fixed-budget online algorithms that learn a near-optimal proper scoring rule for a principal facing a strategic agent in information acquisition, using UCB-style confidence bounds and linear programming.

Problem

Online learning of the optimal scoring rule for a principal in a principal-agent information acquisition problem, where the agent's information structure (belief distributions and costs) is unknown to the principal.

Approach

Reduces the principal's problem to a best-arm-identification bandit over agent actions, estimates the agent's belief distributions and pairwise cost differences with confidence bounds, solves a UCB-style linear program per arm to find the best incentive-compatible proper scoring rule, and mixes in action-informed oracle rules to drive gap-reduction and forced-exploration rounds.

Key results

• OIIAFC (fixed confidence) achieves sample complexity tilde-O((B_S+B_u)^2 B_S^2 K/(eps*varepsilon)^2) with probability at least 1-delta, per the stated theorem.
• The fixed-budget algorithm OIAFB is presented with a theorem whose budget condition and error bound are left as placeholders ('?') in the text, so no concrete fixed-budget guarantee is established in the provided text.

Limitations

• No empirical experiments in the provided text.
• Fixed-budget theorem is incomplete (placeholders for budget condition and error bound).
• Relies on an action-informed oracle assumption providing K scoring rules that induce each arm.

Experimental setup

Metrics: sample complexity error probability

Builds on: UCB proper scoring rules action-informed oracle

Closest papers by meaning

• Online Information Acquisition: Hiring Multiple Agents (ICLR 2024 · similarity 0.88)
• Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.84)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.83)
• Eliciting Kemeny Rankings (AAAI 2024 · similarity 0.82)
• Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.82)
• Stochastically Dominant Peer Prediction (NeurIPS 2025 · similarity 0.82)