Tight Bounds for $γ$-Regret via the Decision-Estimation Coefficient
This work addresses a fundamental limitation in structured bandit theory for researchers, providing tight bounds on γ-regret, though it is incremental as it builds on prior DEC frameworks.
The paper tackles the problem of characterizing γ-regret in structured bandit problems, where exact optimization is intractable, by introducing the γ-DEC as a statistical complexity parameter. It provides nearly matching lower and upper bounds, showing that γ-regret scales with γ-DEC for any algorithm and that an algorithm can achieve this bound.
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 $\mathcal{F}$ where finding an exact optimum of $f \in \mathcal{F}$ is intractable. Our characterization is given in terms of the $γ$-DEC, a statistical complexity parameter for the class $\mathcal{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 $\mathcal{F}$: for any algorithm, there exists some $f \in \mathcal{F}$ for which the $γ$-regret of that algorithm scales (nearly) with the $γ$-DEC of $\mathcal{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.