Expert Advice with Costly Observations

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 $\Theta(\underset{m\in\{1,…,K\}}{\min} \{\sqrt{\frac{K}{m}\,T\log K} + (m-1)\bar pT\}),$ interpolating between bandit and full-information regimes and revealing the optimal observation budget, where $\bar p$ is a tight upper bound of $p_i$s. For stochastic losses, our novel $m$-ELIM algorithm achieves instance-dependent regret of $O\left(\frac{\log T}{m}\sum_{i \neq i^*} \frac{1}{\Delta_i} + (m-1)\bar{p}T\right)$, $\Delta_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.