# Nonstochastic Bandits with Infinitely Many Experts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 9 Feb 2021.

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

- [Learning agile and dynamic motor skills for legged robots](https://mlsanity.com/paper/1901.08652/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [From self-tuning regulators to reinforcement learning and back again](https://mlsanity.com/paper/1906.11392/) (2019)
- [Multiarmed Bandits With Limited Expert Advice](https://mlsanity.com/paper/1306.4653/) (2013)

## Abstract (arXiv)

We study the problem of nonstochastic bandits with expert advice, extending the setting from finitely many experts to any countably infinite set: A learner aims to maximize the total reward by taking actions sequentially based on bandit feedback while benchmarking against a set of experts. We propose a variant of Exp4.P that, for finitely many experts, enables inference of correct expert rankings while preserving the order of the regret upper bound. We then incorporate the variant into a meta-algorithm that works on infinitely many experts. We prove a high-probability upper bound of tildeO big( i^*K + √KT big) on the regret, up to polylog factors, where i^* is the unknown position of the best expert, K is the number of actions, and T is the time horizon. We also provide an example of structured experts and discuss how to expedite learning in such case. Our meta-learning algorithm achieves optimal regret up to polylog factors when i^* = tildeO big( √T/K big). If a prior distribution is assumed to exist for i^*, the probability of optimality increases with T, the rate of which can be fast.