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.