# Constant regret for sequence prediction with limited advice

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 47 references that are in the map.
- First posted on arXiv 5 Oct 2022.

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

- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Budget-Constrained Multi-Armed Bandits with Multiple Plays](https://mlsanity.com/paper/1711.05928/) (2017)
- [Adaptation to Easy Data in Prediction with Limited Advice](https://mlsanity.com/paper/1807.00636/) (2018)
- [Fast rates for prediction with limited expert advice](https://mlsanity.com/paper/2110.14485/) (2021)

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

- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)

## Abstract (arXiv)

We investigate the problem of cumulative regret minimization for individual sequence prediction with respect to the best expert in a finite family of size K under limited access to information. We assume that in each round, the learner can predict using a convex combination of at most p experts for prediction, then they can observe a posteriori the losses of at most m experts. We assume that the loss function is range-bounded and exp-concave. In the standard multi-armed bandits setting, when the learner is allowed to play only one expert per round and observe only its feedback, known optimal regret bounds are of the order O(√ KT). We show that allowing the learner to play one additional expert per round and observe one additional feedback improves substantially the guarantees on regret. We provide a strategy combining only p = 2 experts per round for prediction and observing m ≥ 2 experts' losses. Its randomized regret (wrt. internal randomization of the learners' strategy) is of order O (K/m) log(Kδ --1) with probability 1 -- δ, i.e., is independent of the horizon T ("constant" or "fast rate" regret) if (p ≥ 2 and m ≥ 3). We prove that this rate is optimal up to a logarithmic factor in K. In the case p = m = 2, we provide an upper bound of order O(K 2 log(Kδ --1)), with probability 1 -- δ. Our strategies do not require any prior knowledge of the horizon T nor of the confidence parameter δ. Finally, we show that if the learner is constrained to observe only one expert feedback per round, the worst-case regret is the "slow rate" Omega(√ KT), suggesting that synchronous observation of at least two experts per round is necessary to have a constant regret.