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

arXiv: https://arxiv.org/abs/2303.03327 · HTML: https://mlsanity.com/paper/2303.03327/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 6 Mar 2023.

## Builds on (most cited first, 15 of 15)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Oracle-Efficient Online Learning and Auction Design](https://mlsanity.com/paper/1611.01688/) (2016)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [LeadCache: Regret-Optimal Caching in Networks](https://mlsanity.com/paper/2009.08228/) (2020)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent](https://mlsanity.com/paper/2011.02817/) (2020)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [On Submodular Contextual Bandits](https://mlsanity.com/paper/2112.02165/) (2021)

## Abstract (arXiv)

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.