Best-of-Both Worlds for linear contextual bandits with paid observations

arXiv:2510.07424v3 Announce Type: replace Abstract: We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic $T^{2/3}$ adversarial regret rate and logarithmic dependence on $T$ in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive $\widetilde{O}(T^{2/3})$ adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the $T^{2/3}$ adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.

Abstract:We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic $T^{2/3}$ adversarial regret rate and logarithmic dependence on $T$ in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive $\widetilde{O}(T^{2/3})$ adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the $T^{2/3}$ adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.

Machine Learning (cs.LG)

arXiv:2510.07424 [cs.LG]

(or arXiv:2510.07424v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2510.07424 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Best-of-Both Worlds for linear contextual bandits with paid observations

Related coverage