Multiclass Online Learnability under Bandit Feedback

Ananth Raman, Vinod Raman, Unique Subedi, Idan Mehalel, Ambuj Tewari
8/8/2023
cs.LGstat.ML

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

We study online multiclass classification under bandit feedback. We extend the results of Daniely and Helbertal [2013] by showing that the finiteness of the Bandit Littlestone dimension is necessary and sufficient for bandit online learnability even when the label space is unbounded. Moreover, we show that, unlike the full-information setting, sequential uniform convergence is necessary but not sufficient for bandit online learnability. Our result complements the recent work by Hanneke, Moran, Raman, Subedi, and Tewari [2023] who show that the Littlestone dimension characterizes online multiclass learnability in the full-information setting even when the label space is unbounded.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Multiclass Online Learning and Uniform Convergence

87% match2023

Online Learning with Set-Valued Feedback

87% match2023

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

86% match2026

Multiclass Transductive Online Learning

86% match2024

A Combinatorial Characterization of Supervised Online Learnability

85% match2023

Smoothed Online Classification can be Harder than Batch Classification

83% match2024

Cite this paper

@article{raman2023multiclass,
  title  = {Multiclass Online Learnability under Bandit Feedback},
  author = {Ananth Raman and Vinod Raman and Unique Subedi and Idan Mehalel and Ambuj Tewari},
  year   = {2023},
  eprint = {2308.04620},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2308.04620v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2308.04620.svg)](https://codeofpaper.com/paper/2308.04620)

Discussion