Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression

Haichen Hu, David Simchi-Levi, Navid Azizan · 2025

Read Eluder-Dimension-Free Regret for Stage-Wise Constrained Contextual Bandits via Offline Regression by Haichen Hu, David Simchi-Levi, Navid Azizan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07101.txt.

Description

Haichen Hu, David Simchi-Levi, and Navid Azizan study contextual bandits that must respect safety constraints at every step while learning which action pays best. Only the chosen action's reward and cost are seen, rewards come from a broad function class, and costs are nonlinear. Their algorithm blends offline regression with confidence sets for cost and optimistic bounds for reward.

Each regression fit yields a valid set of plausible costs, and a covering-entropy argument keeps total cost uncertainty under control. Under mild conditions, the method stays feasible at every round with high probability. Its regret grows like the square root of the horizon, without the eluder-dimension term earlier bounds carried. An extension handles infinitely many actions.

Catalog record

CREATORHaichen Hu, David Simchi-Levi, Navid Azizan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE168 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-07101

Browse the full library · About the Tower of Babel