aiqbench analysis
This arXiv paper is a theoretical machine learning result on contextual bandits with stage-wise cost constraints, where only the chosen action's reward and cost are observed. Its main claim is that the proposed CS-UCCB algorithm achieves feasibility at every round and roughly √T regret without the eluder-dimension term that prior bounds rely on, under polylogarithmic covering-entropy assumptions. For practitioners, the key question is whether those assumptions hold in their setting, and the extension to infinite action sets depends on an explicit reward-design condition that deserves scrutiny.
Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression
arXiv:2505.07101v4 Announce Type: replace-cross Abstract: Contextual bandits with stage-wise constraints model decisions that must control risk while learning from their outcomes. We study this problem when only the selected action's reward and cost are observed, with a general reward class and a convex class of nonlinear cost functions. We propose CS-UCCB, which combines offline regression, cost confidence sets, and upper counterfactual confidence bounds. Each regression fit defines a valid cost confidence set, while a geometry derived from covering entropy controls cumulative cost uncertainty along the sampled decisions. Under polylogarithmic covering entropy for both classes and polylogarithmic offline estimation error, the finite-action algorithm guarantees, with high probability, feasibility at every round and $\widetilde{\mathcal O}(\sqrt T)$ regret without an eluder-dimension term. We also extend the analysis to infinite actions under an explicit reward-design condition and compare our bound with existing eluder-dimension bounds.
Abstract:Contextual bandits with stage-wise constraints model decisions that must control risk while learning from their outcomes. We study this problem when only the selected action's reward and cost are observed, with a general reward class and a convex class of nonlinear cost functions. We propose CS-UCCB, which combines offline regression, cost confidence sets, and upper counterfactual confidence bounds. Each regression fit defines a valid cost confidence set, while a geometry derived from covering entropy controls cumulative cost uncertainty along the sampled decisions. Under polylogarithmic covering entropy for both classes and polylogarithmic offline estimation error, the finite-action algorithm guarantees, with high probability, feasibility at every round and $\widetilde{\mathcal O}(\sqrt T)$ regret without an eluder-dimension term. We also extend the analysis to infinite actions under an explicit reward-design condition and compare our bound with existing eluder-dimension bounds.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2505.07101 [stat.ML]
(or arXiv:2505.07101v4 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2505.07101 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.
Full text under the publisher's open licence · 230 words