A note on the price of bandit feedback for mistake-bounded online learning

DOI10.1016/J.TCS.2021.05.009zbMATH Open1504.68085arXiv2101.06891OpenAlexW3160023654MaRDI QIDQ2034409FDOQ2034409

Publication date: 22 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The standard model and the bandit model are two generalizations of the mistake-bound model to online multiclass classification. In both models the learner guesses a classification in each round, but in the standard model the learner recieves the correct classification after each guess, while in the bandit model the learner is only told whether or not their guess is correct in each round. For any set

F

of multiclass classifiers, define

o p t_{s t d} (F)

and

o p t_{b a n d i t} (F)

to be the optimal worst-case number of prediction mistakes in the standard and bandit models respectively. Long (Theoretical Computer Science, 2020) claimed that for all

M > 2

and infinitely many

k

, there exists a set

F

of functions from a set

X

to a set

Y

of size

k

such that

o p t_{s t d} (F) = M

and

o p t_{b a n d i t} (F) g e (1 - o (1)) (| Y | l n | Y |) o p t_{s t d} (F)

. The proof of this result depended on the following lemma, which is false e.g. for all prime

p g e 5

,

s = m a t h b f 1

(the all

1

vector),

t = m a t h b f 2

(the all

2

vector), and all

z

. Lemma: Fix

n g e 2

and prime

p

, and let

u

be chosen uniformly at random from

l e f t {0, d o t s, p - 1 i g h t}^{n}

. For any

s, t i n l e f t {1, d o t s, p - 1 i g h t}^{n}

with

s e q t

and for any

z i n l e f t 0, d o t s, p - 1 i g h t

, we have

P r (t c d o t u = z m o d p e x t | e x t s c d o t u = z m o d p) = f r a c 1 p

. We show that this lemma is false precisely when

s

and

t

are multiples of each other mod

p

. Then using a new lemma, we fix Long's proof.

Full work available at URL: https://arxiv.org/abs/2101.06891

Recommendations

zbMATH Keywords

learning theory online learning mistake-bound model bandit feedback

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Online algorithms; streaming algorithms (68W27) Computational learning theory (68Q32) Optimal stopping in statistics (62L15)

Cites Work

Cited In (3)

This page was built for publication: A note on the price of bandit feedback for mistake-bounded online learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034409)