Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach

Traditional stochastic linear contextual bandit (SLCB) algorithms typically assume sub-Gaussian noise, which leads to an optimal regret bound of O(sqrt(T)). However, many real-world applications—such as click-through rate prediction or physical activity tracking—involve rewards that are inherently bounded. This paper investigates whether explicitly leveraging this bounded noise condition can improve the regret performance of SLCB algorithms.

The authors propose a new algorithm, SME-OFU, which replaces the standard probabilistic confidence regions used in algorithms like LinUCB with set-membership estimation (SME). SME constructs a polytopic uncertainty set that is guaranteed to contain the true parameter vector with probability 1, provided the noise bound is known. By applying the principle of optimism in the face of uncertainty (OFU) to these polytopic sets, the algorithm selects actions that maximize the potential reward within the feasible parameter space.

The paper establishes that SME-OFU achieves an instance-independent regret bound of O(log T). This logarithmic scaling is a substantial improvement over the O(sqrt(T)) bound achieved by algorithms designed for sub-Gaussian noise. The authors provide a proof framework based on convex geometry, using the volume of the minimum-volume enclosing ellipsoid (MVEE) of the SME uncertainty set as a potential function to handle the complex evolution of the polytopes. Simulations confirm that SME-OFU outperforms benchmark algorithms when the noise is indeed bounded.

This work demonstrates that stronger, practical assumptions about noise can fundamentally change the theoretical limits of online learning. By moving away from sub-Gaussian assumptions toward set-membership approaches, researchers can achieve logarithmic regret, which is highly desirable for long-horizon decision-making tasks. The geometric proof techniques developed here also provide a new foundation for analyzing non-probabilistic uncertainty quantification in bandit settings.