# Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 75 references that are in the map.
- First posted on arXiv 13 Apr 2022.

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

- [Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error](https://mlsanity.com/paper/2108.08780/) (2021)
- [Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments](https://mlsanity.com/paper/2009.09249/) (2020)
- [Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering](https://mlsanity.com/paper/2109.02082/) (2021)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles](https://mlsanity.com/paper/2108.06411/) (2021)
- [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)
- [Generalized Translation and Scale Invariant Online Algorithm for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2109.09212/) (2021)

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

- [Data Dependent Regret Guarantees Against General Comparators for Full or Bandit Feedback](https://mlsanity.com/paper/2303.06526/) (2023)

## Abstract (arXiv)

We study the problem of expert advice under partial bandit feedback setting and create a sequential minimax optimal algorithm. Our algorithm works with a more general partial monitoring setting, where, in contrast to the classical bandit feedback, the losses can be revealed in an adversarial manner. Our algorithm adopts a universal prediction perspective, whose performance is analyzed with regret against a general expert selection sequence. The regret we study is against a general competition class that covers many settings (such as the switching or contextual experts settings) and the expert selection sequences in the competition class are determined by the application at hand. Our regret bounds are second order bounds in terms of the sum of squared losses and the normalized regret of our algorithm is invariant under arbitrary affine transforms of the loss sequence. Our algorithm is truly online and does not use any preliminary information about the loss sequences.