The Cost of Information: Phase Transitions in Contextual Bandits with Paid Observations

We study contextual bandits with paid observations, where the learner actively chooses which actions to observe at a given cost in each round, with the goal of minimizing total regret that jointly accounts for learning loss and observation expenditure. We develop a near-optimal algorithm for adversarial environments and show that even small observation costs fundamentally raise the minimax regret order. We further uncover a novel phase transition under a free observation budget: below a critical threshold, free observations only reduce total cost without improving the regret rate; above it, asymptotic improvements become possible. To exploit this phenomenon, we design a meta-controller that adaptively switches between strategies to achieve near-optimal performance across all budget regimes. To handle large or infinite policy spaces, we also propose an oracle-efficient algorithm under a function approximation framework that maintains rigorous guarantees with computational efficiency. Our analysis also connects to related problems including switching costs, budgeted constraints, model misspecification, and knapsack bandits. Numerical experiments validate our theoretical findings.

In contextual bandits, observing outcomes often incurs a cost (e.g., paying evaluators). We design algorithms that adaptively purchase observations, balancing information gain against expense. For huge decision spaces, we use function approximation (e.g., neural networks) for efficiency with guarantees. We uncover a phase transition: below a critical free‑observation budget, costs drop but learning speed stagnates; above it, learning accelerates. A meta‑controller switches strategies accordingly. This provides cost‑efficient AI for recommendations and sensors, reveals that even small costs fundamentally change learning difficulty, and shows function approximation makes the approach scalable.