# Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 17 May 2022.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Efficient Online Bandit Multiclass Learning with tildeO(√T) Regret](https://mlsanity.com/paper/1702.07958/) (2017)
- [Learning Multiclass Classifier Under Noisy Bandit Feedback](https://mlsanity.com/paper/2006.03545/) (2020)
- [Multiclass Classification using dilute bandit feedback](https://mlsanity.com/paper/2105.08093/) (2021)

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

- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)

## Abstract (arXiv)

In this paper, we present online algorithm called it Delaytron for learning multi class classifiers using delayed bandit feedbacks. The sequence of feedback delays dtt=1T is unknown to the algorithm. At the t-th round, the algorithm observes an example xt and predicts a label tildeyt and receives the bandit feedback mathbbI[tildeyt=yt] only dt rounds later. When t+dt>T, we consider that the feedback for the t-th round is missing. We show that the proposed algorithm achieves regret of Oleft(√frac2 Kγleft[fracT2+left(2+fracL2R2Vert WVertF2right)sumt=1Tdtright]right) when the loss for each missing sample is upper bounded by L. In the case when the loss for missing samples is not upper bounded, the regret achieved by Delaytron is Oleft(√frac2 Kγleft[fracT2+2sumt=1Tdt+vert Mvert Tright]right) where M is the set of missing samples in T rounds. These bounds were achieved with a constant step size which requires the knowledge of T and sumt=1Tdt. For the case when T and sumt=1Tdt are unknown, we use a doubling trick for online learning and proposed Adaptive Delaytron. We show that Adaptive Delaytron achieves a regret bound of Oleft(√T+sumt=1Tdtright). We show the effectiveness of our approach by experimenting on various datasets and comparing with state-of-the-art approaches.