aiqbench analysis
This paper proposes a bandit algorithm that builds its uncertainty sets with set membership estimation, a method from control and system identification, instead of the usual confidence intervals. The authors prove a sublinear regret bound under stated assumptions and report simulations against existing methods. For ML readers, the main value is a new theoretical bridge between control-theory uncertainty quantification and online decision-making, though the practical gains depend on how well those assumptions hold outside simulation.
Set Membership Estimation for Stochastic Linear Contextual Bandits
arXiv:2606.20022v2 Announce Type: replace-cross Abstract: Contextual bandit learning has attracted increasing attention in engineering applications due to its ability to incorporate side/context information in time-varying environments. A widely used approach for contextual bandits is optimism in the face of uncertainty (OFU), in which uncertainty sets for unknown parameters are constructed and decisions are made optimistically over these sets. In the bandit literature, uncertainty sets are typically derived using statistical learning tools, such as confidence intervals. In contrast, set membership estimation (SME), a well-established uncertainty quantification approach in control and system identification, has received little attention in the bandit literature. This paper investigates the connection between SME and contextual bandits by focusing on linear contextual bandits as a starting point. We propose an SME-based OFU algorithm and establish a sublinear regret bound under proper assumptions. Simulations further demonstrate the promising performance of SME-OFU compared with existing methods. This supplementary manuscript provides more proof details in Section IV and the Appendix.
Abstract:Contextual bandit learning has attracted increasing attention in engineering applications due to its ability to incorporate side/context information in time-varying environments. A widely used approach for contextual bandits is optimism in the face of uncertainty (OFU), in which uncertainty sets for unknown parameters are constructed and decisions are made optimistically over these sets. In the bandit literature, uncertainty sets are typically derived using statistical learning tools, such as confidence intervals. In contrast, set membership estimation (SME), a well-established uncertainty quantification approach in control and system identification, has received little attention in the bandit literature. This paper investigates the connection between SME and contextual bandits by focusing on linear contextual bandits as a starting point. We propose an SME-based OFU algorithm and establish a sublinear regret bound under proper assumptions. Simulations further demonstrate the promising performance of SME-OFU compared with existing methods. This supplementary manuscript provides more proof details in Section IV and the Appendix.
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2606.20022 [stat.ML]
(or arXiv:2606.20022v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2606.20022 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 253 words
Related coverage
Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback
arXiv · Oct 9, 2026
Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
arXiv · Sep 10, 2026
Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits
arXiv · Oct 16, 2026
Using Reward Uncertainty to Induce Diverse Behaviour in Reinforcement Learning
arXiv · Sep 11, 2026