# Bayesian Design Principles for Frequentist Sequential Learning

arXiv: https://arxiv.org/abs/2310.00806 · HTML: https://mlsanity.com/paper/2310.00806/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 55 references that are in the map.
- First posted on arXiv 1 Oct 2023.

## Builds on (most cited first, 28 of 28)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Regret Bounds for Information-Directed Reinforcement Learning](https://mlsanity.com/paper/2206.04640/) (2022)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory](https://mlsanity.com/paper/2011.06186/) (2020)
- [Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory](https://mlsanity.com/paper/2304.12466/) (2023)

## Built on by (most cited first, 18 of 18)

- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Bayesian Design Principles for Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2405.20984/) (2024)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [The Benefit of Being Bayesian in Online Conformal Prediction](https://mlsanity.com/paper/2410.02561/) (2024)
- [Decision Making in Hybrid Environments: A Model Aggregation Approach](https://mlsanity.com/paper/2502.05974/) (2025)
- [Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity](https://mlsanity.com/paper/2312.17248/) (2023)
- [Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.19292/) (2024)
- [An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs](https://mlsanity.com/paper/2510.08882/) (2025)
- [Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation](https://mlsanity.com/paper/2606.07931/) (2026)
- [Thompson Sampling for Repeated Newsvendor](https://mlsanity.com/paper/2502.09900/) (2025)
- [One-shot acceleration of transient PDE solvers via online-learned preconditioners](https://mlsanity.com/paper/2509.08765/) (2025)
- [Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces](https://mlsanity.com/paper/2502.14790/) (2025)
- [Exploring the Link Between Bayesian Inference and Embodied Intelligence: Toward Open Physical-World Embodied AI Systems](https://mlsanity.com/paper/2507.21589/) (2025)
- [Mind the Sim-to-Real Gap & Think Like a Scientist](https://mlsanity.com/paper/2605.21458/) (2026)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)

## Abstract (arXiv)

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.