2023/10/01 by Yunbei Xu, Assaf Zeevi, Xu, Yunbei +1 · 1 voice · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Statistics Theory (math.ST) #cs.LG #math.OC #math.ST
paper · pdf · doi:10.48550/arxiv.2310.00806
openalex publication_date 2023/10/01 · arxiv published 2023/10/01 · arxiv updated 2024/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a general theory to optimize the frequentist regret for sequential learning problems, where efficient bandit and reinforcement learning algorithms can be derived from unified Bayesian principles. We propose a novel optimization approach to generate "algorithmic beliefs" at each round, and use Bayesian posteriors to make decisions. The optimization objective to create "algorithmic beliefs," which we term "Algorithmic Information Ratio," represents an intrinsic complexity measure that effectively characterizes the frequentist regret of any algorithm. To the best of our knowledge, this is the first systematical approach to make Bayesian-type algorithms prior-free and applicable to adversarial settings, in a generic and optimal manner. Moreover, the algorithms are simple and often efficient to implement. As a major application, we present a novel algorithm for multi-armed bandits that achieves the "best-of-all-worlds" empirical performance in the stochastic, adversarial, and non-stationary environments. And we illustrate how these principles can be used in linear bandits, bandit convex optimization, and reinforcement learning.