Avoiding Catastrophe in Online Learning by Asking for Help

We thank the reviewer for helpful comments. We respond to each of the weaknesses mentioned.

1. Lack of algorithmic novelty. Although we agree that the algorithm is quite simple, this can also be seen as an advantage, since simple algorithms are both more accessible to readers and more likely to be used in practice. Also, although our analysis utilizes many prior results, we believe that the packing technique we use to bound the number of queries is novel. Essentially, we have provided a technique for bounding the number of data points needed to cover a particular set with respect to the realized actions of the algorithm. For merely covering the set without regard for the algorithm’s actions, existing packing/covering number bounds would suffice, but our technique may be useful in contexts where a more refined packing argument is needed than one which deals with all data points in aggregate. See also lines 508-514 in the paper.

2. Related work on CMDPs. The two linked papers study a related but distinct problem. Both papers assume that the learner knows a safe policy (what the reviewer calls “a feasible solution”) upfront, and ask whether the learner can obtain high reward while also remaining safe. In our setting, the learner has no prior knowledge about which actions are safe, and must learn a safe policy from scratch. In this sense, our work complements theirs: our goal is essentially to learn the baseline safe policy that their algorithms require. One can also view our problem as the “pessimistic” model and their problem as the “optimistic” model, with some applications better captured by our model while other applications are better captured by theirs. We will add a discussion of this related work to our paper.

We thank the reviewer for helpful comments. We respond to each of the weaknesses mentioned and also to the reviewer’s question (which corresponds to one of the weaknesses).

1. Connections to AI risk. The AI risk literature discusses in depth the importance of safety guarantees, but has had comparatively little success in formally establishing those guarantees. In particular, to our knowledge, we are the first to formally guarantee avoidance of catastrophe with a computationally tractable algorithm (e.g., without Bayesian inference). Although we do not claim that our model perfectly captures all real-world safety concerns, our model is quite flexible, allowing a wide range of state/context sequences, mentor policies, payoff functions, etc. We view our work not just as a stylized model of catastrophe, but as a real step towards the practical safety guarantees sought by the AI risk literature. If future work extends our results to not only avoid catastrophe but also guarantee high reward (e.g., in an MDP), one can start thinking about using such algorithms in practice.

2. Local generalization. We agree with the reviewer on the importance of justifying assumptions, and we appreciate the opportunity to respond. Local generalization states that if the mentor told us that an action is safe in state $s’$, the action is likely also safe in a similar state $s$. To be precise, $\mu(s, \pi^m(s))$ is the payoff from taking the actual safe action in the current state $s$, while $\mu(s, \pi^m(s’))$ is the payoff from using what we learned in a previous state $s’$ in $s$. Local generalization states that the gap between these is bounded proportional to the similarity between those states: $|\mu(s,\pi^m(s)) - \mu(s, \pi^m(s’))| \le L||s-s’||$. The concept of borrowing knowledge from similar experiences seems fundamental to learning and is well-understood in the psychology literature (example) and education literature (example).

   Crucially, our state space is not necessarily the 3D orientation of the agent, but can be any feature embedding of the agent’s situation. This allows for more abstract notions of "similarity". Also, our algorithm does not require knowledge of the feature embedding (see lines 406-409) and does not need to know $L$, so it suffices that there exists some feature embedding which satisfies local generalization. The agent does not even need to know which embedding it is.

   Finally, note that in the case of an optimal mentor, local generalization implies the more familiar Lipschitz continuity (Proposition E.1). The assumption of Lipschitz continuity is common in the bandit literature (see Chapter 4 of this book).

3. Euclidean space. The reviewer makes a fair point regarding our Euclidean space assumption and the spirit of online learning. However, this assumption is actually not necessary: all of our results go through for a general metric space, with the difference that the regret would then depend explicitly on the packing number. We thought this would be less intuitive for readers since the subconstant nature of our regret bound is less obvious with the packing number present, and we also think that most real-world applications would involve feature embeddings in $\mathbb{R}^n$. However, we can switch our analysis to a general metric space if the reviewer thinks the trade-off is worth it.

4. Online learning with log loss. We agree that this literature is relevant, and thank the reviewer for pointing it out. The key difference is that those regret bounds are sublinear in T while our regret bound is subconstant in T. In other words, the help of a mentor and local generalization can reduce the regret by an entire factor of T. We will add a discussion of this to the paper.

5. Imitation learning. Thank you for the pointer; we will also add a discussion of imitation learning.

6. The term “state”. We agree with this point and ask whether the reviewer would be okay with the term “input”, which we hope is intuitive to readers from both online learning and RL.

We thank the reviewer for helpful comments. We respond to each of the questions and weaknesses stated by the reviewer.

Questions:

1. We are not aware of other impossibility results, including in the Bayesian regime (except for the trivial result that the problem is hopeless without some sort of help, since the agent has no way to prevent the first action it takes from causing catastrophe). We do believe that our impossibility result is a significant contribution, and we will make this clearer when revising. Thank you for pointing this out.
2. Recall that the payoff is the chance of avoiding catastrophe that round (conditioned on no prior catastrophe), not the chance of causing catastrophe. Under this definition, the chain rule of probability implies that the product of payoffs is exactly the overall chance of avoiding catastrophe. Our goal is to maximize that product. If the agent has 0% chance of avoiding catastrophe on the first round, then catastrophe is in fact guaranteed. This is worse than the second sequence, which retains a nonzero probability of avoiding catastrophe. Correspondingly, $0 \cdot 0.999^3 < 0.1^4$.

Weaknesses:

1. We first remind the reviewer that we do not assume the mentor to be optimal. More importantly, we are motivated by applications in which there exists an actual human supervisor (or potentially a more powerful AI model) who can respond to queries. Examples include a human doctor supervising AI doctors, a robotic vehicle with a human driver who can take over in emergencies, autonomous weapons with a human operator, and many more. In fact, we suggest that it is crucial for any high-stakes AI applications to have a designated supervisor who can be asked for help. In such applications, the target for queries is known to the agent.

   Also, if we understand correctly what the reviewer means by “find out who the optimal target to query in the policy class is”, this essentially makes queries useless. For example, suppose the policy class contains only the mentor policy and its complement: the agent has no way to know which is which and thus has no way to know which policy it should query. Let us know if we have misunderstood.

2. We will flesh out this discussion in the paper and are also happy to briefly elaborate here. The technical challenge is that vanilla packing arguments do not consider the actions of the algorithm. Our overall proof requires a set of queries which cover the observed state space with respect to the realized actions of the algorithm, and our technical contribution is to provide a novel method to deal with this scenario. Our technique may be useful for other contexts where a more refined packing argument is needed than one which deals with all data points in aggregate.

3. Thank you for this feedback. We will address these issues when revising.

We have now uploaded a revised version of the paper which incorporates the feedback from all reviewers. We believe that this revision addresses each of the questions/weaknesses raised by Reviewer Qo6Q. Changes are highlighted in red. The relevant changes for this reviewer's feedback can be found on the following line numbers in the revised PDF:

Q1: Clarified the lack of other impossibility results (lines 171-172)

Q2: Clarified the relationship between the product of payoffs and probability of catastrophe (lines 064-066)

W1: Added justification for the existence of a mentor known to the agent (lines 055-058)

W2: Expanded the description of the novel packing argument (lines 511-515)

W3: Improved the phrasing of the sentences on lines 126 and 134.

See also lines 262-273 for a discussion of the "goodness" of the mentor.

Please let us know if this adequately addresses your concerns. If not, we would welcome further discussion.

We thank the reviewer for helpful comments. We respond to each of the weaknesses and also to the reviewer’s question.

Weaknesses:

1. The formal definition of $\mu(s_t, a_t)$ is actually the chance of catastrophe at time $t$ conditioned on no prior catastrophe (line 263). (Note that the probability of catastrophe at time $t$ conditioned on prior catastrophe already occurring is irrelevant, since the agent has already failed.) Formally, if $E_t$ is the event that catastrophe is avoided at time $t$, then the chain rule of probability implies that $\Pr[\text{no catastrophe ever}] = \Pr[\cap_{t=1}^T E_t] = \prod_{t=1}^T \Pr[E_t \mid \cap_{k=1}^{t-1} E_k] = \prod_{t=1}^T \mu(s_t, a_t)$ We will update the paper to better explain the role of this conditioning.

2. We have two responses here:

   (A) If $\sum_{t=1}^T - \log \mu^m(s_t)$ is not bounded by a constant, this implies that $\prod_{t=1}^T \mu^m(s_t)$ goes to 0. In other words, the environment is sufficiently dangerous and/or the mentor is sufficiently fallible that the mentor’s own policy is guaranteed to eventually cause catastrophe. In such cases, perhaps the task should be avoided altogether; we are imagining applications where the mentor does know a reasonably safe policy.

   (B) The reviewer is correct that subconstant regret becomes trivial if $\sum_{t=1}^T - \log \mu^m(s_t)$ is unbounded and thus $\prod_{t=1}^T \mu^m(s_t)$ goes to 0, but our results say more about the regret than simply that it is subconstant: we also provide rates of convergence. In other words, even if the mentor is guaranteed to eventually cause catastrophe, we can estimate the time horizons on which we can expect the agent to still be relatively safe. If the reviewer recommends this, we could emphasize our convergence rate bounds more in the introduction.

3. The reviewer is roughly correct that taking a logarithm can convert our multiplicative objective into an additive objective. Without help from a mentor, subconstant regret (additive or multiplicative) is impossible because the agent essentially must guess on the first time step, so the agent is wrong with constant probability (and that’s just the first time step). With sublinear queries to a mentor, subconstant additive regret is indeed achievable: we actually prove this as an intermediate step to our main result (lines 1050-1054). To our knowledge, this is a novel result in online learning, which we could also highlight if the reviewer recommends.

   Also, even after the transformation to an additive objective, our problem remains harder than standard online learning. This is because we only receive feedback from queries (whose rate tends to 0 as $T \to \infty$), while online learning typically assumes that payoffs are observed on every time step.

Question:

$Q_T$ is in fact a random variable since $a_1,\dots,a_T$ are random variables. We will add an explicit mention of this to avoid confusion.