Tight Bounds for γ-Regret via the Decision-Estimation Coefficient

In this work, we give a statistical characterization of the γ-regret for arbitrary structured bandit problems, the regret which arises when comparing against a benchmark that is γ times the optimal solution. The γ-regret emerges in structured bandit problems over a function class F where finding an exact optimum of f ∈ F is intractable. Our characterization is given in terms of the γ-DEC, a statistical complexity parameter for the class F, which is a modification of the constrained Decision-Estimation Coefficient (DEC) of Foster et al., 2023 (and closely related to the original offset DEC of Foster et al., 2021). Our lower bound shows that the γ-DEC is a fundamental limit for any model class F: for any algorithm, there exists some f ∈ F for which the γ-regret of that algorithm scales (nearly) with the γ-DEC of F. We provide an upper bound showing that there exists an algorithm attaining a nearly matching γ-regret. Due to significant challenges in applying the prior results on the DEC to the γ-regret case, both our lower and upper bounds require novel techniques and a new algorithm.