We study multiclass PAC learning with bandit feedback, where inputs are
classified into one of $K$ possible labels and feedback is limited to whether
or not the predicted labels are correct. Our main contribution is in designing
a novel learning algorithm for the agnostic $(\varepsilon,\delta)$-PAC version
of the problem, with sample complexity of $O\big( (\operatorname{poly}(K) + 1 /
\varepsilon^2) \log (|H| / \delta) \big)$ for any finite hypothesis class $H$.
In terms of the leading dependence on $\varepsilon$, this improves upon
existing bounds for the problem, that are of the form $O(K/\varepsilon^2)$. We
also provide an extension of this result to general classes and establish
similar sample complexity bounds in which $\log |H|$ is replaced by the
Natarajan dimension. This matches the optimal rate in the full-information
version of the problem and resolves an open question studied by Daniely,
Sabato, Ben-David, and Shalev-Shwartz (2011) who demonstrated that the
multiplicative price of bandit feedback in realizable PAC learning is
$\Theta(K)$. We complement this by revealing a stark contrast with the agnostic
case, where the price of bandit feedback is only $O(1)$ as $\varepsilon \to 0$.
Our algorithm utilizes a stochastic optimization technique to minimize a
log-barrier potential based on Frank-Wolfe updates for computing a low-variance
exploration distribution over the hypotheses, and is made computationally
efficient provided access to an ERM oracle over $H$.

我们研究了具有强化学习反馈的多分类 PAC 学习问题，提出了一种新颖的学习算法将样本复杂度降低到 O ((poly (K) + 1/ε²) log (|H|/δ))，改进了现有问题的边界，同时在一般类别情况下也得到了类似的样本复杂度边界，算法利用随机优化技术通过 Frank-Wolfe 更新计算低方差探索分布。