From √T to log T: New SME-OFU Algorithm Slashes Regret in Bandit Problems

In a new paper on arXiv, researchers Haonan Xu and Yingying Li tackle a classic reinforcement learning problem: stochastic linear contextual bandits (SLCB). Existing algorithms assume sub-Gaussian reward noise, leading to optimal regret bounds of O(√T). However, many real-world applications—like ad placement or clinical trials—have naturally bounded rewards, meaning the noise is also bounded. This stronger condition has been largely overlooked. The authors propose SME-OFU, a method that explicitly exploits bounded noise via set-membership estimation (SME) combined with optimism in the face of uncertainty (OFU). The result is an improved regret bound of O(log T), which is exponentially better in theory and practice.

The algorithm works by constructing confidence sets for the unknown parameter vector using the bounded noise assumption, rather than relying on looser sub-Gaussian concentration inequalities. This allows SME-OFU to eliminate suboptimal arms faster. The paper includes theoretical proofs and simulations showing that SME-OFU outperforms standard OFU algorithms (designed for sub-Gaussian noise) when rewards are bounded. Practical implications are significant: for recommendation systems, dynamic pricing, or any sequential decision-making with bounded feedback, SME-OFU learns the best action in far fewer rounds, reducing regret and improving user experience.