# Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 20 Feb 2025.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Online Linear Optimization via Smoothing](https://mlsanity.com/paper/1405.6076/) (2014)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [Non-exponentially weighted aggregation: regret bounds for unbounded loss functions](https://mlsanity.com/paper/2009.03017/) (2020)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Prediction by Random-Walk Perturbation](https://mlsanity.com/paper/1302.5797/) (2013)

## Abstract (arXiv)

We develop a form Thompson sampling for online learning under full feedback - also known as prediction with expert advice - where the learner's prior is defined over the space of an adversary's future actions, rather than the space of experts. We show regret decomposes into regret the learner expected a priori, plus a prior-robustness-type term we call excess regret. In the classical finite-expert setting, this recovers optimal rates. As an initial step towards practical online learning in settings with a potentially-uncountably-infinite number of experts, we show that Thompson sampling over the d-dimensional unit cube, using a certain Gaussian process prior widely-used in the Bayesian optimization literature, has a OBig(β√Tdlog(1+√dfracλβ)Big) rate against a β-bounded λ-Lipschitz adversary.