# Data Dependent Regret Guarantees Against General Comparators for Full or Bandit Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 75 references that are in the map.
- First posted on arXiv 12 Mar 2023.

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

- [Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments](https://mlsanity.com/paper/2009.09249/) (2020)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [RELEAF: An Algorithm for Learning and Exploiting Relevance](https://mlsanity.com/paper/1502.01418/) (2015)
- [Distributed Online Learning in Social Recommender Systems](https://mlsanity.com/paper/1309.6707/) (2013)
- [A Comprehensive Approach to Universal Piecewise Nonlinear Regression Based on Trees](https://mlsanity.com/paper/1311.6392/) (2013)
- [Feedback Solution to Optimal Switching Problems with Switching Cost](https://mlsanity.com/paper/1411.4695/) (2014)
- [Periodic Bandits and Wireless Network Selection](https://mlsanity.com/paper/1904.12355/) (2019)
- [Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2109.09212/) (2021)
- [Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback](https://mlsanity.com/paper/2204.06660/) (2022)

## Abstract (arXiv)

We study the adversarial online learning problem and create a completely online algorithmic framework that has data dependent regret guarantees in both full expert feedback and bandit feedback settings. We study the expected performance of our algorithm against general comparators, which makes it applicable for a wide variety of problem scenarios. Our algorithm works from a universal prediction perspective and the performance measure used is the expected regret against arbitrary comparator sequences, which is the difference between our losses and a competing loss sequence. The competition class can be designed to include fixed arm selections, switching bandits, contextual bandits, periodic bandits or any other competition of interest. The sequences in the competition class are generally determined by the specific application at hand and should be designed accordingly. Our algorithm neither uses nor needs any preliminary information about the loss sequences and is completely online. Its performance bounds are data dependent, where any affine transform of the losses has no effect on the normalized regret.