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

Xueping Gong, Jiheng Zhang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:36013-36044, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-gong26i, title = {The Cost of Information: Phase Transitions in Contextual Bandits with Paid Observations}, author = {Gong, Xueping and Zhang, Jiheng}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {36013--36044}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/gong26i/gong26i.pdf}, url = {https://proceedings.mlr.press/v306/gong26i.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T The Cost of Information: Phase Transitions in Contextual Bandits with Paid Observations %A Xueping Gong %A Jiheng Zhang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-gong26i %I PMLR %P 36013--36044 %U https://proceedings.mlr.press/v306/gong26i.html %V 306 %X 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.
APA
Gong, X. & Zhang, J.. (2026). The Cost of Information: Phase Transitions in Contextual Bandits with Paid Observations. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:36013-36044 Available from https://proceedings.mlr.press/v306/gong26i.html.

Related Material