Abstract
Querying expert predictions or human feedback incurs explicit, often heterogeneous costs—a challenge central to crowdsourcing and LLM training. We study online learning with expert advice under observation costs, where the learner must adaptively select which experts to query (p_i is expert-dependent) to minimize cumulative cost (losses plus query costs). While classical bandits and recent paid observation models have advanced the field, they fail to capture the rich cost-adaptive selection landscape and do not provide tight, problem-dependent performance guarantees for heterogeneous costs. This paper provides the first comprehensive characterization. For adversarial losses, we prove tight minimax regret Θ(m∈{1,…,K}min{√(K/m Tlog K) + (m-1)p̅T}), interpolating between bandit and full-information regimes and revealing the optimal observation budget, where p̅ is a tight upper bound of p_is. For stochastic losses, our novel m-ELIM algorithm achieves instance-dependent regret of O(log T/m∑_i ≠ i^*1/Δ_i + (m-1)p̅T), Δ_i being the suboptimality gap of the i-th arm, showing how gap structure and costs interact. Matching lower bounds (adversarial and stochastic) establishes minimax optimality. These results provide the first rigorous framework for optimally allocating annotation budgets across heterogeneous workers in crowdsourcing systems, directly informing cost-effective strategies for collecting human feedback in adaptive learning applications.