The price of knowledge: Optimal algorithms for costly bandits

We study stochastic bandits in which observing a reward is optional but incurs an action-dependent cost. This setting captures applications where feedback acquisition (e.g., human evaluation or randomized testing) is expensive, and the learner must trade off exploration, exploitation, and observation cost. We formulate regret to include both reward loss and the cumulative cost of requested observations. Our first result is structural: for minimizing regret, it is without loss of generality to consider two-phase policies that first request observations during an exploration phase and then commit to a single action without further observations. Building on this reduction, we introduce two cost-sensitive complexity measures that extend maximum information gain: a cost-adjusted information gain ΓT(c) for minimax analysis, and a cost- and gap-adjusted information gain Γgap T(∆c) for instance-dependent analysis. Using these quantities, we develop two Gaussian-process-based algorithms, C3-GP and GP-C-LUCB, and derive regret upper bounds for correlated-action settings with heterogeneous (i.e. action-dependent) observation costs. In the finite independent-action setting, we further prove matching lower and upper bounds (up to constants/logarithmic factors), yielding a tight characterization of both minimax and instance-dependent regret in terms of the proposed cost-aware complexity measures.