# Contextual Bandits and Optimistically Universal Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 31 Dec 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Nonparametric Stochastic Contextual Bandits](https://mlsanity.com/paper/1801.01750/) (2018)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Self-Tuning Bandits over Unknown Covariate-Shifts](https://mlsanity.com/paper/2007.08584/) (2020)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?](https://mlsanity.com/paper/2107.09542/) (2021)
- [Universally Consistent Online Learning with Arbitrarily Dependent Responses](https://mlsanity.com/paper/2203.06046/) (2022)
- [Universal Regression with Adversarial Responses](https://mlsanity.com/paper/2203.05067/) (2022)

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

- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Computable universal online learning](https://mlsanity.com/paper/2510.18352/) (2025)

## Abstract (arXiv)

We consider the contextual bandit problem on general action and context spaces, where the learner's rewards depend on their selected actions and an observable context. This generalizes the standard multi-armed bandit to the case where side information is available, e.g., patients' records or customers' history, which allows for personalized treatment. We focus on consistency -- vanishing regret compared to the optimal policy -- and show that for large classes of non-i.i.d. contexts, consistency can be achieved regardless of the time-invariant reward mechanism, a property known as universal consistency. Precisely, we first give necessary and sufficient conditions on the context-generating process for universal consistency to be possible. Second, we show that there always exists an algorithm that guarantees universal consistency whenever this is achievable, called an optimistically universal learning rule. Interestingly, for finite action spaces, learnable processes for universal learning are exactly the same as in the full-feedback setting of supervised learning, previously studied in the literature. In other words, learning can be performed with partial feedback without any generalization cost. The algorithms balance a trade-off between generalization (similar to structural risk minimization) and personalization (tailoring actions to specific contexts). Lastly, we consider the case of added continuity assumptions on rewards and show that these lead to universal consistency for significantly larger classes of data-generating processes.