Sign betting improves misspecified regression with variance adaptivity
Sign Betting for Misspecified Regression: Variance Adaptivity and Optimal Approximation
Machine Learning
Summary
This paper looks at how to measure errors in predictions when the model might not be perfect. Instead of using a common squared error, the authors focus on a different way to measure mistakes that matters more for certain decision-making tasks like learning from experience. They study a specific method called sign-betting regression, showing it can adapt to how uncertain the data is and perform nearly as well as the best possible method. The paper also shows limits on how well any method can do under these conditions. They tested their findings with experiments on synthetic and real data.
What this means in practice
- •For bandit algorithm developers: Improve decision-making models by using sign-betting regression to handle errors more reliably under misspecified assumptions.
- •For reinforcement learning engineers: Enhance reinforcement learning models by adopting L1-based regression methods that better adapt to data variance and model errors.
Authors
Yinan Li, Han Han, Kwang-Sung Jun
Abstract
We study bounded regression under model misspecification, evaluating a function $f$ by its $L_1(P_X)$ distance to the conditional mean $η(x)=\mathbb{E}[Y\mid X=x]$, rather than the standard $L_2(P_X)$. This $L_1$ metric is natural for downstream decision problems such as bandits and reinforcement learning. We analyze the min--max estimator of Baraud & Maillard (2025), which we call \emph{sign-betting regression}. Our main results show that sign-betting regression achieves high-probability $L_1$ oracle inequalities under misspecification. Under realizability, our bound adapts to the average conditional variance and recovers the variance-adaptive rate of Li et al. (2026). We further characterize the optimal universal approximation factor for proper learning by showing that sign betting achieves factor 3, while no proper learner can satisfy a distribution-free, high-probability $L_1$ oracle inequality with a universal approximation factor strictly below 3. We extend the upper-bound analysis beyond finite classes and complement the theory with experiments in synthetic and real-world model-selection tasks.