**General Response**

We thank all reviewers for taking the time to read our manuscript carefully and for providing constructive and insightful feedback.

We provide detailed responses to each reviewer separately. We look forward to engaging in further discussion with the reviewers, answering questions, and discussing improvements.

**Response to Reviewer LpfF**

> The analysis of the linear classification case seems rather straightforward, and it is not clear to me what are the technical challenges authors had to face. In particular, I would like to see an argument that justify the adoption of the normalized losses.

The main techincal challenge of the online setting is that the adversary at round $t$ may select an example with small (or even zero) margin with respect to the current hypothesis $w^{(t)}$ of the learner. In that case, simply using the Leaky-ReLU loss (like the prior work [DGT19]) does not work as the loss would be zero and the Online Gradient Descent learner would not make progress (see also the definition of $C_{\Delta}(\cdot)$ at page 4). By rescaling the loss with the margin with respect to $w^{(t)}$ we avoid this and make sure that when an incorrect prediction happens, OGD will make some non-trivial progress. We will add a remark about this in our manuscript.

[DGT19] Distribution-Independent PAC Learning of Halfspaces with Massart Noise, Diakonikolas I., Gouleakis T., Tzamos C., NeurIPS2019

>As the focus of the paper is in obtaining efficient algorithms, it would be nice to see more explicit runtime bounds than poly(d).

Our algorithm is a simple online gradient descent iteration and the runtime per round is linear in the dimension. The total runtime over all rounds is thus $O(d T)$.

> The results in the MBA setting looks rather pessimistic with a T^5/6 rate. How does this rates compare against more general settings?

While information-theoretically better rates could be possible, we stress that in this work we focus on (and provide) **computationally efficient** algorithms, i.e., that run in time polynomial in the feature dimension $d$. Prior to our work, even for 2 arms nothing better than the trivial $T/2$ bound was known. We agree with the reviewer that improving the additive term of $T^{5/6}$ is interesting and we plan to investigate it in future work.

**Response to Reviewer d5iA**

We thank the reviewer for the insightfull feedback and questions. We provide detailed explanations and clarifications to the quesetions. We will include them in our updated manuscript.

> At the beginning of Page 6, it is claimed that the regret guarantees imply that $\sum_{i\not\in J}E[\ell^t(w^t)]\leq \bar{R}(T)$ It is not clear to me why this is the case.

To prove the aforementioned claim, we first note that in the last paragraph of page 5, we have shown the following: 1) $-\sum_{i\not\in J}E[\ell^t(w^*)]\geq 0$ and 2) $\sum_{i\in J}(E[\ell^t(w^t)]-E[\ell^t(w^*)])\geq |J|\frac{\epsilon \gamma}{4\tau}\geq 0$. Furthermore, from assumption of Lemma 2.2, we have that 3)
$\sum_{i=1}^T(E[\ell^t(w^t)]-E[\ell^t(w^*)])\leq \bar{R}(T)$.
Note that 3) can be equivalently written as $\sum_{i\not\in J}E[\ell^t(w^t)]\leq \bar{R}(T) \underbrace{-\sum_{i\in J}(E[\ell^t(w^t)]-E[\ell^t(w^*)])}_{I_1}+\underbrace{\sum_{i\not\in J}E[\ell^t(w^*)]}_{I_2}$.
The aforementioned claim follows from the fact that $I_1\leq 0$ from 2) and $I_2\leq 0$ from 1).

> Could the author(s) elaborate more on the proof of Lemma 2.2? More precisely, I could not obtain Eq(3) from previous claims.

Given that $\sum_{i\not\in J}E[\ell^t(w^t)]\leq \bar{R}(T)$ and that $J=\{x^t:|w^t\cdot t|\leq \tau \}$, we have that that
4)$\sum_{i\not\in J}g^t[E[y]]=\sum_{i\not\in J}E[\ell^t(w^t)]\leq \bar{R}(T)$, furthermore, by definition, we have that for all $g^t[E[y]]\leq 2$, hence, 5)$\sum_{i\in J}g^t[E[y]]\leq \sum_{i\in J}2=2|J|$. Adding, 4) and 5) we get Eq(3). (Indeed, we have a typo and it should be $2|J|$ instead of $J$ but this only change the final constant by a factor of $2$.)

**Response to Reviewer Khgz**

> I am not sure how meaningful the result of the bandit setting is. ... uniformly at random is interesting or meaningful.

It is possible to compare our reward with the optimal algorithm that knows the ground truth vector $w^\ast$. This algorithm will pick arm 1 when $f^*(X^{(t)})= \mathrm{sgn}(w^\ast \cdot (x_1^{(t)} - x_2^{(t)})$ is positive and arm 2 otherwise. The reward of the optimal algorithm can be then expressed as $r_*^{(t)} = (r_1^{(t)} + r_2^{(t)})/2 + (r_1^{(t)} - r_2^{(t)})/2 f^*(X^{(t)})$. Therefore, the reward of our algorithm (which denote by $\hat r^{(t)}$) minus the optimal expected reward (using the bound of Corollary 1) is equal to
$$
\mathbf E[\sum_{t=1}^T( \hat r^{(t)}-r_*^{(t)})]
\geq
\mathbf E[\sum_{t=1}^T( \Delta - f^*(X^{(t)}) (r_1^{(t)}-r_2^{(t)}) ] - o(T).
$$
We observe that as the gap $\Delta$ between the expected rewards grows larger (closer to maximum possible $M$), our algorithm gets reward closer to the optimal reward. That said, for constant $\Delta$ our reward is still linearly far from the optimal. We stress that the reward achieved by our algorithm is essentially best possible (up to the lower order $o(T)$ terms) given the statistical query lower bounds. We will include the above remark in our revised manuscript.

> Following Theorem 1.8, you mention that the algorithm is essentially optimal ... asking if the additional additive rate of $T^{2/3}/\gamma$ is optimal?

We clarify that the $\eta T$ mistake bound is not an information theoretic lower bound. As we mention in our manuscript the information theoretic boudns were given in the work of [1]. The $\eta T$ error is essentially best possible (given the statistical query lower bounds of [2]) when considering **computationally efficient** algorithms as we do here. We stress that prior to our work no computationally efficient algorithm was known that could beat the random guessing benchmark (that makes $T/2$ mistakes). We used the term "optimal" as we were able to achieve the best possible constant (up to polylogarithmic factors) in front of the linear term in the mistake bound. We also stress that our result that gets $\eta T$ mistakes with a computationally efficient algorithm is far from trivial. In particular, even in the offline setting of linear classification under Massart noise the first computationally efficient that achieved classification error $\eta$ (the offline equivalent of $\eta T$ mistakes) was only given in the relatively (given the history of the problem) recent work [3].

Finally, we agree with the reviewer that the lower order (sublinear in $T$) terms could potentially be improved and we believe that this is a very interesting question for future work. Since our work is the first that gives computationally efficent online algorithms with Massart noise we focused on obtaining the best dependence on the linear term. We will include this discusssion in our manuscript and clarify that by optimal we refer to the linear term dependence in the mistake bound.

[1] Ben-David, S., P´al, D., and Shalev-Shwartz, S. Agnostic online learning. COLT 2009.
[2] Diakonikolas, I., Kane, D., Ren, L., and Sun, Y. Sq lower bounds for learning single neurons with massart noise. NeurIPS 2022.
[3] Diakonikolas I., Gouleakis T., Tzamos C.
Distribution-Independent PAC Learning of Halfspaces with Massart Noise, NeurIPS2019

**Response to Reviewer RwaM**

>Can the authors clarify the reason for the negative sign before $w^*$ in Claim 2.3? This does not appear to be consistent with the proof provided;

This is indeed a typo, it should not contain the $-$ sign anywhere in $C_{\tilde{\Delta}}$.

>In the paragraph above equation (2), how do you obtain the lower bound $|J|\frac{\epsilon \gamma}{4\tau}$. It seems to me the bound should be $-T/2+|J|\frac{\epsilon \gamma}{2\tau}$, and there is no evidence that and are related in any way.

We have shown that in the same paragraph that 1) $\sum_{i\in J}-E[\ell^t(w^*)]\geq |J|\frac{\epsilon \gamma}{2\tau}$ and furthermore by the definition of the losses $\ell^t$, we have that 2) $\sum_{i\in J}E[\ell^t(w^*)]
\geq -\sum_{i\in J}1=-|J|$. Adding 1) and 2), we get that the lower bound should be $-|J|+|J|\frac{\epsilon \gamma}{2\tau}=\underbrace{-|J|+|J|\frac{\epsilon \gamma}{4\tau}}_{I}+|J|\frac{\epsilon \gamma}{4\tau}$. Furthermore from the assumption that $\tau\leq \epsilon\gamma/2$, we have that $I\geq 0$, hence, we obtained the claimed bound.

> Why does the regret bound imply $\sum_{t\not\in J}E[\ell^t(w^t)]\leq \bar{R}(T)$. Can't the losses $E[\ell^t(w^t)]$ indexed by $t\in J$ be negative?

We provide a detailed proof of this claim: see our response to reviewer d5iA.

> Can you provide a derivation of the gradients of the losses $\ell^t(w)$.

By construction $\ell^t(u):=\frac{C_{\Delta}(u\cdot x^t;y^t)}{\max((|w^t\cdot x^t),\tau)}$. By taking the gradient with respect the vector $u$, we get that $\nabla_u\ell^t(u):=\frac{\nabla_uC_{\Delta}(u\cdot x^t;y^t)}{\max((|w^t\cdot x^t),\tau)}$ and we have that $\nabla_uC_{\Delta}(u\cdot x^t;y^t)=\frac 12\nabla_u(\Delta |u\cdot x^t|-y^tu\cdot x^t)=\frac 12(\Delta \nabla_u|u\cdot x^t|-y^t\nabla_u u\cdot x^t)$. And note that $\nabla_u|u\cdot x^t|=\mathrm{sign}(u\cdot x^t)x^t$ and $\nabla_u u\cdot x^t=x^t$.

> It appears to me that the authors aim to achieve a mistake bound (not regret) ... he non-triviality of the referenced lower bounds lie in the low noise regime.

Indeed we provide a mistake bound (as we mention in Remark 1.2 -- we will remove the term regret from other places to avoid confusion).

We stress that in the online classification with Massart noise the noisy label $y^{(t)}$ is flipped with probability *at most* $\eta$ at every round. The bound $\eta T$ is trivially best-possible only in the much easier Random Classification Noise (RCN) setting (as the reviewer mentions). Our algorithm achieves the mistake bound $\eta T$ in the much more challenging Massart setting and matches the best-known (offline) classification guarantee of [1] and the SQ lower bound of [2].

Comparing with the clean labels is possible, however we opted to compare with the noisy label as is standard in previous works classification with Massart noise [1,3]. To get a mistake bound with respect to the clean labels, we denote by $\xi^{(t)}$ the random variable determining whether the ground truth label is flipped at every round. Then our mistake bound of Theorem 1.8 becomes $\mathbf E[\sum_{t=1}^T 1\{\hat y^{(t)} \neq f^*(x^{(t)})\} (1- 2 \xi^{(t)})] \leq \mathbf E [\sum_{t=1}^T (\eta - \xi^{(t)})] + o(T)$. This mistake bound (compared to the ground truth is also the best known [1] and most likely best possible (up to the sublinear term $o(T)$ )) [2] even in the offline setting. We observe that in the Random Classification noise setting (when all $\xi^{(t)}$ are 1 with probability $\eta$) our mistake bound is sublinear in $T$. We will include the above discussion in our updated manuscript.

[1] Diakonikolas I., Gouleakis T., Tzamos C. Distribution-Independent PAC Learning of Halfspaces with Massart Noise, NeurIPS2019
[2] Diakonikolas, I., Kane, D., Ren, L., and Sun, Y. Sq lower bounds for learning single neurons with massart noise. NeurIPS 2022.
[3] Sitan C., Frederic K., Ankur M., Morris Y. NeurIPS 2021 Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability

> I think the reference to prior literature on online classification with ... are quite similar in spirit to what is employed in the current paper.

We thank the reviewer for bringing the work [4] to our attention: it is indeed relevant and we will include it in the first revision of our work. As the reviewer mentions, the crucial difference is that in our work we focus on *computationally efficient* algorithms.

We will include the clean label mistake bound of [5] together with the explanation of comparing with the noisy labels that we gave above.

[4] Changlong W. Ananth G. Wojciech S Robust Online Classification: From Estimation to Denoising

[5] Ben-David, S., P´al, D., and Shalev-Shwartz, S. Agnostic online learning. COLT 2009.

> Currently, it appears to me ... Can the authors comment on what the essential technical originality here is compared to the online case? I think a more interesting extension would be to study how tight the second term ...

We respectfully disagree with the reviewer: our main *technical* contribution is indeed the online Massart classification algorithm. Our contribution in the bandit literature is *the definition of a new semi-random contextual bandit model that goes beyond the standard (regression-based) realizability assumptions [6]* considered in the prior works. We remark that the classification based bandit settings in the prior works are pessimistic (agnostic) precluding the existence of computationlly efficient algorithms in essentially any non-trivial setting (see also our discussion in Section 1). By the reduction to online massart classification we established that our proposed bandit model is a non-adversarial classification-based model that admits end-to-end efficient algorithms. There are many interesting questions for future work in this model (see also the conclusion section) and we believe that our model will aim in the design of potentially practical bandit algorithms (that do not rely on strong regression oracles).

[6] Foster, D., Agarwal, A., Dud´ık, M., Luo, H., and Schapire, R. Practical contextual bandits with regression oracles.