Avoiding Catastrophe in Online Learning by Asking for Help

We thank the reviewer for the thoughtful review. We believe the reviewer articulates only a single weakness:

Weakness: for the problem that is solvable, it generally relying on the VC / Littlestone Dimension as a parameter to Hedge Algorithm, which can be impractical to compute

We agree that this is a weakness of our current algorithm. We offer two responses:

1. We are the first to show that avoiding irreversible mistakes without Bayesian inference is possible at all. Eventually we would indeed like an efficient algorithm, but we believe that proving that the problem is solvable at all is an important step towards finding an efficient algorithm for the problem.
2. We are optimistic about the prospect of a more efficient algorithm based on techniques from Block et al. (2022). In the context of standard online learning (i.e., without irreversible mistakes), they show how to explore a hypothesis class without explicitly computing the VC dimension or constructing an $\varepsilon$-cover. We will add a mention of this to the conclusion, as we think this is an important avenue for future work.

We would also like to clarify the regret bound. The reviewer writes:

...which enables achieving sublinear regret with sublinear queries.

However, our algorithm achieves subconstant regret with sublinear queries.

We thank the reviewer for the thoughtful review. We respond to each concern and question:

Concern 1

The regret compared to the mentor makes sense on one hand; however, the fact that it becomes somewhat vacuous unless the mentor avoids catastrophe with a probability close to 1 is a bit odd…If the mentor's policy were not fixed, it would make more sense.

To clarify, the mentor’s policy $\pi^m$ is not fixed across values of $T$. When we stated in the paper that $\pi^m$ is fixed, we meant that $\pi^m$ does not vary across time steps in a given problem instance, i.e., we do not deal with non-stationarity. It is crucial that the mentor policy can vary across values of $T$ (and across problem instances) for the exact reason stated by the reviewer. Our original writing was unclear and we will fix this.

We also mention that our subconstant bound on standard additive regret (Theorem 5.3) is unaffected by this issue entirely.

Concern 2

The local generalization assumption is not a standard one and is not adequately justified in the paper.

We agree on the importance of justifying assumptions and will expand this justification when revising.

To recap, local generalization states that $|\mu_t^m(x) - \mu_t(x, \pi^m(x'))| \le L ||x-x'||$ for any $x,x’$. We make the following claims:

A. One can transfer knowledge between similar situations, with the reliability of the transfer depending on the degree of similarity. This is well-known in the education and psychology literature (e.g., Esser et al. 2023, Hajian 2019).

B. Local generalization captures the idea of Claim A. Specifically,

B1. $\mu_t^m(x)$ is the effect of taking the right action for the current input $x$

B2. $\mu_t(x, \pi^m(x'))$ is the effect of using what you learned in $x’$ for the current input $x$

B3. $||x-x'||$ captures the similarity between $x$ and $x’$

To effectively focus our revision, it would help us to understand which of these claims felt weakest to the reviewer, or if their skepticism is based on something else.

Concern 3

​​The main claim of technical novelty by the authors lies in the packing argument, which they only briefly discuss in the last paragraph of Section 5. However, I think that this paragraph does not adequately convey the technical challenge and how it is addressed.

To recap, we perform a packing argument with respect to an arbitrary categorization of the data instead of considering all data in aggregate as is typical in packing arguments. In our case, the categorization is based on the algorithm’s action. However, we should have emphasized in the paper that our technique can be applied to any categorization of the data.

In fact, we think our technique has promise as a general-purpose way to bound how well categorized data covers an input space. It’s often insufficient to simply have lots of data for each category: to ensure good generalization, each category should be represented well across the input space. For example, suppose one has plenty of data on healthy and sick patients, but all the sick patient data is from hospital visits: models trained on this data may make inaccurate predictions about sick patients outside of the hospital, despite plenty of sick patient data. We will expand this discussion.

Question 1

In line 229, what do you mean by feature embedding? Isn't $x$ already the "state" embedding?

Yes, we just mean state embedding. The idea is that the algorithm is agnostic to how the states are represented, so local generalization just has to be satisfied for some way of representing states. We will clarify this.

Question 2

It seems that whenever hedgeQuery is true, then X is not updated, and that whenever the algorithm "asks for help," the policy is not updated. This is not very intuitive; why is it that you don't need that?

Those updates are not necessary because the algorithm already learns enough from the existing updates. Omitting those updates from the algorithm allows us to fully separate the Hedge updates and the ask-for-help updates, which slightly simplifies the analysis. However, we see why this is unintuitive, and we will add an explanation of this. We are also open to including those updates in the algorithm.

Question 3

Is there a specific policy class for which you can make the algorithm efficient (not exponential in $d$)?

In general, the size of a cover of the policy class must be exponential in $d$. Intuitively, this is because a VC dimension of $d$ means that the policy class can realize all $2^d$ labelings of $d$ points.

However, we are optimistic about reducing the dependence on $d$ in future work via techniques from Block et al. (2022), who show how to bypass explicitly constructing covers. We will mention this in the conclusion.

Question 4

Is there a difference between ($s_t$ as mentioned in Algorithm 1) and $x_t$ in the rest of the paper, or is that just a typo?

This is simply a typo. We apologize for the confusion.

We thank the reviewer for the thoughtful review. We respond to each of the reviewer’s concerns:

Concern 1

However, how the problem is modeled as an online learning problem with mentor is a bit arbitrary. I'm not sure if the right way to sell the paper is yours, i.e., you model the problem of avoiding catastrophe as an online learning problem, or to focus more on a general online learning setting in which the goal is to maximize the product of the payoff which has as application avoiding catastrophe.

We appreciate the suggestion and are happy to make the paper’s framing more general if the reviewer thinks that would strengthen the paper. In fact, this seems more like a strength of our work than a weakness: if we understand correctly, the reviewer suggests that our work is actually more general than our current framing.

Concern 2

From a technical perspective, it seems that the paper is mostly putting together results from previous works. Moreover, it is unclear whether the paper introduces general techniques or models that can be applied to broader and more fundamental problems.

We do agree that technical novelty is not our primary contribution. However, we offer some mild pushback:

1. The existing results we utilize come from a variety of sources and topics. We think that combining previously disparate results in a new way can also be a form of technical novelty.

2. We believe our packing argument is novel, as discussed at the top of the right column of page 8. To recap, we perform a packing argument with respect to an arbitrary categorization of the data instead of considering all data in aggregate as is typical in packing arguments. In our case, the categorization is based on the algorithm’s action. However, we should have emphasized in the paper that our technique can be applied to any categorization of the data.

   In fact, we think our technique has promise as a general-purpose way to bound how well categorized data covers an input space. It’s often insufficient to simply have lots of data for each category: to ensure good generalization, each category should be represented well across the input space. For example, suppose one has plenty of data on healthy and sick patients, but all the sick patient data is from hospital visits: models trained on this data may make inaccurate predictions about sick patients outside of the hospital, despite plenty of sick patient data. We will expand this discussion when revising.

We thank the reviewer for the thoughtful review.

Page 4: "Also, that work" ---> Also, their work

We appreciate the correction and will make this change.

On the bottom of page 3 the authors state "sublinear regret is possible iff the hypothesis ...". Is this supposed to by an if and only if or is this a typo?

This is indeed “if and only if”. See, e.g., Corollary 21.8 in Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (2014). We will expand “iff” to “if and only if” to avoid reader confusion.