  We present online boosting algorithms for multiclass classification with
bandit feedback, where the learner only receives feedback about the correctness
of its prediction. We propose an unbiased estimate of the loss using a
randomized prediction, allowing the model to update its weak learners with
limited information. Using the unbiased estimate, we extend two full
information boosting algorithms (Jung et al., 2017) to the bandit setting. We
prove that the asymptotic error bounds of the bandit algorithms exactly match
their full information counterparts. The cost of restricted feedback is
reflected in the larger sample complexity. Experimental results also support
our theoretical findings, and performance of the proposed models is comparable
to that of an existing bandit boosting algorithm, which is limited to use
binary weak learners.
