Avoiding Catastrophe in Online Learning by Asking for Help
Authors: Benjamin Plaut
Hanlin Zhu
Stuart Russell
Venue: ICML 2025 poster (2025)
Keywords: online learning
AI safety
asking for help
irreversibility
Primary area: theory->online_learning_and_bandits
TL;DR: If a policy class is learnable in the absence of catastrophic risk, it is learnable in the presence of catastrophic risk if the agent can ask for help.

Abstract: Most learning algorithms with formal regret guarantees assume that all mistakes are recoverable and essentially rely on trying all possible behaviors. This approach is problematic when some mistakes are *catastrophic*, i.e., irreparable. We propose an online learning problem where the goal is to minimize the chance of catastrophe. Specifically, we assume that the payoff in each round represents the chance of avoiding catastrophe in that round and try to maximize the product of payoffs (the overall chance of avoiding catastrophe) while allowing a limited number of queries to a mentor. We also assume that the agent can transfer knowledge between similar inputs. We first show that in general, any algorithm either queries the mentor at a linear rate or is nearly guaranteed to cause catastrophe. However, in settings where the mentor policy class is learnable in the standard online model, we provide an algorithm whose regret and rate of querying the mentor both approach 0 as the time horizon grows. Although our focus is the product of payoffs, we provide matching bounds for the typical additive regret. Conceptually, if a policy class is learnable in the absence of catastrophic risk, it is learnable in the presence of catastrophic risk if the agent can ask for help.

Avoiding Catastrophe in Online Learning by Asking for Help
Benjamin Plaut Hanlin Zhu
Stuart Russell
Abstract
ble harm. In addition the large-scale risks above, our definition also covers smaller-scale (yet still unacceptable) incidents such as serious medical errors (Rajpurkar et al., 2022), crashing a robotic vehicle (Kohli & Chadha, 2020), and discriminatory sentencing (Villasenor & Foggo, 2020).
Most learning algorithms with formal regret guar- antees assume that all mistakes are recoverable and essentially rely on trying all possible behav- iors. This approach is problematic when some mistakes are catastrophic, i.e., irreparable. We propose an online learning problem where the goal is to minimize the chance of catastrophe. Specifically, we assume that the payoff in each round represents the chance of avoiding catastro- phe in that round and try to maximize the product of payoff's (the overall chance of avoiding catastro- phe) while allowing a limited number of queries mentor. We also assume that the agent can trans- fer knowledge between similar inputs. We first show that in general, any algorithm either queries the mentor at a linear rate or is nearly guaranteed to cause catastrophe. However, in settings where the mentor policy class is learnable in the standard online model, we provide algorithm whose regret and rate of querying the mentor both ap- proach O as the time horizon grows. Although our focus is the product of payoffs, we provide match- ing bounds for the typical additive regret. Concep- tually, if a policy class is learnable in the absence of catastrophic risk, it is learnable in the presence of catastrophic risk if the agent can ask for help.
The gravity of these risks contrasts starkly with the dearth of theoretical understanding of how to avoid them. Nearly all of learning theory explicitly or implicitly assumes that single mistake is too costly. We focus online learning, where an agent repeatedly interacts with an unknown environment and uses its observations to gradually improve its performance. Most online learning algorithms essentially try all possible behaviors and see what works well. We do not want autonomous weapons or surgical robots to try all possible behaviors.
More precisely, iial-and-erro--stlle algorithms only work when catastrophe is assumed to be impossible. This assump- tion can take multiple forms, such as that the agent's 's actions do not affect future inputs (e.g., Slivkins, 2011), 1),, that no ac- tion has irreversible effects (e.g., Jaksch et al., 2010) or that the environment is reset at the start of each "episode" (c.g.. Azar et al., 2017). One could train an agent entirely in a con- trolled lab setting where one of those assumptions does hold, but we argue that sufficiently general agents will inevitably encounter novel scenarios when deployed in the real world. Machine learning models often behave unpredictably in un- familiar environments (see, c.g., Quiñoneeo-Candee et al., 2022), and we do not want AI biologists or robotic vehicles to behave unpredictably.
1. Introduction
The goal of this paper is to understand the conditions un- der which it is possible to formally guarantee avoidance of catastrophe in online learning. Certainly some conditions are necessary, because the problem is hopeless if the agent must rely purely on trial-and-error: any untried action could lead to paradise or disaster and the agent has no way to pre- dict which. In the real world, however, one need not learn through pure trial-and-error: one can also ask for help. We think it is critical for high-stakes Al applications to employ a designated supervisor who can be asked for help. Examples include a human doctor supervising AI doctors, a robotic vehicle with a human driver who can take over in emer- gencies, autonomous weapons with human operator, and many more. We hope that our work constitutes a step in the
There has been mounting concern over catastrophic risk from AI, including but not limited to autonomous weapon accidents (Abaimov& & Martellini, 2020), bioterrorism (Mou- ton et al., 2024), cyberattacks on critical infrastructure (Guembe et al., 2022), and loss of control (Bengio et al., 2024). See Critch & Russell (2023) and Hendrycks et al. (2023) for taxonomies of societal-scale AI risks. In this paper, we use "catastrophe" to refer to any kind of irrepara-
University of Califomia, Berkeley. Correspondence to: Ben- jamin Plaut <plaut beett@@eeerkee....>.>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Avoiding Catastrophe in Online Learning by Asking for Help
direction of practical safety guarantees for such applications.
Table 1: Comparison between the standard online learning model and our model.
1.1. Our model
Standard model
Our model
We propose an online learning model of avoiding catastro- phe with mentor help. On each time step, the agent observes an imput, selects action queries the mentor, and ob- tains& payoff. Each payoff' represents the probability of avoiding catastrophe on that time step (conditioned on no prior catastrophe). The agent's goal is to maximize the prod- act of payoffs, which is equal to the overall probability of avoiding catastrophe. ! As is standard in online learning, we consider the product of payoffs obtained while learning, not the product of payoffs of some final policy.
Objective Regret goal
Sum of payoffss
Product of payoff's
Sublinear
Subconstant
Feedback
Every time step
Only from queries
Mentor
No
Yes
Local generalization
No
Yes
1.3. Standard online learning
To properly understand our results, it is important to un- derstand standard online learning. In the standard model, the agent observes an input on each time step and must choose action. An adversary then reveals the correct action, which results in some payoff to the agent. The goal is sublinear regret with respect to the sum of payoff's, or equivalently, the average regret per time step should go to O as T + oc. Table delineates the precise differences between the standard model and our model.
The (possibly suboptimal) mentor has stationary policy, and when queried, the mentor illustrates their policy's 's action for the current input. We want the agent's 's regret- - defined as the gap between the mentor's s performance and the agent's 's performance - to go to zero as the time horizon T grows. In other words, with enough time, the agent should avoid catas- trophe nearly as well as the mentor. We also expect the agent to become self-sufficient over time: the number of queries to the mentor should be sublinear in T, or equivalently, the rate of querying the mentor should go to zero.
If the adversary's choices are unconstrained, the problem is hopeless: if the adversary determines the correct action on each time step randomly and independently, the agent can do no better than random guessing. However, sublinear regret becomes possible if (1) the hypothesis class has finite Littlestone dimension (Littlestone, 1988), or (2) the hypoth- esis class has finite VC dimension (Vapnik & Chervonenkis, 1971) and the input is a-smooth" (Haghtalab et al., 2024).
1.2. Our assumptions
The agent needs some way to make inferences about un- queried inputs in order to decide when to ask for help. Much past work has used Bayesian inference, which suffers from tractability issues in complex environments. 2 We instead assume that the mentor policy satisfies a novel property that we call local generalization: informally, if the mentor told us that an action was safe for a similar input, then that action is probably also safe for the current input. For example, if it is safe to ignore a 3 mm spot on an X-ray, it is likely (but not certainly) also safe to ignore a 3.1 mm spot with the same density, location, etc. Unlike Bayesian inference, local gen- eralization only requires computing distances and compat- ible with any input space that admits a distance metric. See Section 5.2 for further discussion of local generalization.
The goal of sublinear regret in online learning implicitly assumes catastrophe is impossible: the agent can make ar- bitrarily many (and arbitrarily costly) mistakes as long as the average regret per time step goes to O. In contrast, we demand subconstant regret: the total probability of catastro- phe should go to O. Furthermore, standard online learning allows the agent to observe payoff' on every time step, while our agent only receives feedback on time steps with queries. However, the combination of mentor and local generaliza- tion allows our agent to learn without trying actions directly, which is enough to offset all of the above disadvantages.
Unlike the standard online learning model, we assume that the agent does not observe payoffs. This is because the payoff in our model represents the chance of avoiding catas- trophe on that time step. In the real world, one only observes whether catastrophe occurred, not its probability."
1.4. Our results
At high level, we show that avoiding catastrophe with the help of a mentor and local generalization is no harder than online learning without catastrophic risk.
'Conditioning on no prior catastrophe means we do not need to assume that these probabilities are independent (and if catastrophe has already occurred, this time step does not matter). This is due the chain rule of probability.
We first show that in general, any algorithm with sublinear queries the mentor has unbounded regret in the worst- case (Theorem 4.1). As a corollary, even when the mentor
FFor the curious reader, Betancourt (2018) provides thorough treatment. See also Section 2.
*One may he able to detect "close calls" in some cases, but observing the precise probability seems unrealistic.
'Informally, the adversary chooses distribution over inputs instead of precise input. See Section for the formal definition.
2

---

Avoiding Catastrophe in Online Learning by Asking for Help
can avoid catastrophe with certainty, any algorithm either needs extensive supervision or is nearly guaranteed to cause catastrophe (Corollary 4.1.1).
We are only aware of two papers that theoretically address irreversibility without Bayesian inference: Grinsztajn et al. (2021) and Maillard et al. (2019). The former proposes to sample trajectories and learn reversibility based on temporal consistency between states: intuitively, if 81 always precedes 82, we can infer that $1 is unreachable from 82. Although the paper theoretically grounds this intuition, there is no formal regret guarantee. The latter presents an algorithm which asks for help in the form of rollouts from the current state. However, the regret bound and number of rollouts are both linear in the worst case, due to the de- pendence on the ? parameter which roughly captures how bad an irreversible action can be. In contrast, our algorithm achieves good regret even when actions are maximally bad.
Our primary result is a simple algorithm whose total regret and rate of querying the mentor both go to 0 as 7 -> oo when either (1) the mentor policy class has finite Littlestone dimension or (2) the mentor policy class has finite VC di- mension and the input sequence o-smooth (Theorem 5.2). Conceptually, the algorithm has two components: (1) for "in- distribution" inputs, run standard online learning algorithm (adjusted to account for only receiving feedback in response to queries), and (2) for "oott-of-disti di-strribuution " inputs, ask for help. Our algorithm can handle an unbounded input space and does not need to know the local generalization constant.
To our knowledge, we are the first to provide an algorithm which formally guarantees avoidance of catastrophe (with high probability) without Bayesian inference. We are also not aware of prior results comparable to our negative result, including in the Bayesian regime.
Although we focus on the product of payoff's, we show that the results above (both positive and negative) hold for the typical additive regret as well. In fact, we show that multiplicative regret and additive regret are tightly related in our setting (Lemma A.
Safe reinforcement learning (RL). The safe RL problem is typically formulated as a constrained Markov Decision Pro- cess (CMDP) (Altman, 2021). In CMDPs, the agent must maximize reward while also satisfying safety constraints. See Gu et al. (2024); Zhao et al. (2023); Wachi et al. (2024) for surveys. The two most relevant safe RL papers are Liu et al. (2021) and Stradi et al. (2024), both of which provide algorithms guaranteed to satisfy initially unknown safety constraints. Since neither paper allows external help, they require strong assumptions to make the problem tractable: the aforementioned results assume that the agent (1) knows strictly safe policy upfront (i.e.. a policy which satisfies the safety constraints with slack), (2) is periodically reset, and (3) observes the safety costs. In contrast, our agent has no prior knowledge, is never reset, and never observes payoffs.
In summary, the combination of local generalization and mentor allows us reduce the regret by an entire factor of T, resulting in subconstant regret (multiplicative or additive) instead of the typical sublinear regret.
2. Related work
Learning with irreversible costs. Despite the ubiquity of ineevesiible costs in the real world, theoretical work on this topic remains limited. This may be due to the fundamental modeling question of how the agent should learn about novel inputs or actions without trying them directly.
The most common approach is to allow the agent to ask for help. This alone is insufficient, however: the agent must have some way to decide when to ask for help. A popular so- lution is to perform Bayesian inference on the world model, but this has two tricky requirements: (1) a prior distribution which contains the true world model (or an approximation), and (2) an environment where computing (or approximating) the posterior is tractable. A finite set of possible environ- ments satisfies both conditions but is unrealistic in many worldworld scenarios. In contrast, our algorithm can handle an uncountable policy class and continuous unbounded input space, which is crucial for many real-world scenarios in which one never sees the exact same imput twice.
Online learning. See Chapter 21 of Shalev-Shwartz & Ben-David (2014) for introductions online learning. A classical result states that sublinear regret is possible if and only if the hypothesis class has finite Littlestone dimension (Littlestone, 1988). However, even some simple hypothesis classes have infinite Littlestone dimension, such as the class of thresholds on [0, 1] (Example 21 144 in Shalev-Shwartz. & Ben-David, 2014). Recently, Haghtalab et al. (2024) showed that if the adversary only chooses distribution over inputs rather than the precise input, only finite VC dimension (Vapnik & Cher- vonenkis, 1971) is needed for sublinear regret. Specifically, they assume that each input is sampled from a distribution whose concentration is upper bounded by 1 uniform distribution. This framework is known as smoothed analysis, originally due to Spielman & Teng (2004).
& Lugosi (2006) and
Bayesian inference combined with asking for help is studied by Cohen et al. (2021); Cohen & Hutter (2020); Kosoy (2019); Mindermann et al. (2018). We also mention Hadfield-Mende et al. (2017); Moldovan & Abbeel (2012); Turchetta et al. (2016), who utilize Bayesian inference in the context of safe (online) reinforcement learning without asking for help (and without regret bounds).
o times the
Multiplicative objectives. Although online learning tra- ditionally studies the sum of payoffs, there is some work
3

---

Avoiding Catastrophe in Online Learning by Asking for Help
which aims to maximize the product of payoff's (or equiva- lently, the sum of logarithms). See, e.g., Chapter 9 of Cesa- Bianchi & Lugosi (2006). However, these regret bounds are still sublinear in T, in comparison to our subconstant regret bounds. Also, like most online learning work, those results assume that payoffs are observed on every time step. In con- trast, our agent only receives feedback in response to queries (Table 1) and never observes payoff's. Barman et al. (2023) studied multiplicative objective in a multi-armed bandit context, but their objective is the geometric mean of payoff's instead of the product. Interpreted in our context, their re- gret bounds imply that the average chance of catastrophe goes to zero, while we guarantee that the total chance of catastrophe goes to zero. This distinction is closely related to the difference between subconstant and sublinear regret.
otherwise noted, all expectations are over any randomization in the agent's ' decisions, any randomization in æ; and any randomization in the adaptive choice of js.
Asking for help. The mentor is endowed with a (possibly suboptimal) policy nhh : X - J. When action ÿ is chosen, the mentor informs the agent of the action x²' (Ize and the agent obtains payoff fe (2,, (2))). For brevity, let p (x) = pe(a, x² (z)). The agent never observes payoffss: the only way learn about μs is by querying the mentor.
We would like an algorithm which becomes "self-sufficient" over time: the rate of querying the mentor should go to O as T + oo, or equivalently, the cumulative num- ber of queries should be sublinear in T. Formally, let Qr(,, = {t E [T] y = [ be the random vari- able denoting the set of time steps with queries. Then we say that the (expected) number of queries is sublinear in T if sup a.a (I, x=]]]] E o(T). In other words, there must exist g N:N + N which does not depend on or x" such that g(T) E o(T) and sup [I[QT(H, T T")l S (TT). For brevity, we will usually write Qr = Qr (M, (").
Active learning and imitation learning. Our assumption that the agent only receives feedback in response to queries falls under the umbrella of active learning (Hanneke, 2014). This contrasts with passive learning, where the agent re- ceives feedback automatically. The way our agent learns from the mentor is also reminiscent of imitation learning (Osa et al., 2018). Although ideas from these areas could be useful in our setting, we are not aware of any results from that literature which account for irreversible costs.
Local generalization. We assume that μ and T' satisfy local generalization. Informally, if the agent is given an input z, taking the mentor action for a similar input x' is almost as good as taking the mentor action for x. Formally, we assume X' C RR" and there exists L > 0 such that for all x, x' E X' and t E [T]. lnf" - (x xh (z")) S L||z æ'I,. where ||-I| denotes Euclidean distance. This represents the ability to transfer knowledge between similar inputs:
3. Model
Inputs. Let N denote the strictly positive integers and let T E N be the time horizon. Let x = (x1, .2. zr) E XT be the sequence of inputs. In the fully adversarial set- ting, each z; can have arbitrary (possibly randomized) de- pendence on the events of prior time steps. In the smoothed setting, the adversary only chooses the distribution D, from which It is sampled. Formally, a distribution 'D over X is o-smooth for any S C X. D(S)= < (S). (In the smoothed setting, we assume that X' supports a uniform distribution U.S) each 2, is sampled from a-soooth D., we say that is a -mooth. The sequence D= D Dr can still be adaptive, i.e., the choice of D, can depend on the events of prior time steps.
[1, x (o))
[e(x,, TT' (x"))
S
L||0 x'1|
Takinng the right action
Using what you learned in an"
Input sumilarity
This ability seems fundamental to intelligence and is well- understood in psychology (c.g., Esser et al., 2023) and ed- ucation (e.g., Hajian, 2019). Note that the input space X' S R" can be any encoding of the agent's ' situation, not just its physical positioning. See Section 5.2 for further discussion.
All suprema over μ1, T" pairs are assumed to be restricted to μu, th pairs which satisfy local generalization.
Actions and payoffs. Let y be a finite set of actions. There also exists a special action ÿ which corresponds to querying the mentor. For le E N. let kK = 21,2..... k). On each time step ł E [T'], the agent must select action b1 E ('(ū), which generates a payoff. Let y = (y1...., wr). We allow the payoff function to vary between time steps: let μ (TT) E (X' x y + [0, 1))T be the sequence of payoff functions. Then (1 yt) E [0, 1] is the agent's payoff at time t. Like D. we allow is to be adaptive. Unless
Regret. If pe 3.) E [0, is the chance of avoiding catastrophe at time & (conditioned on no prior catastrophe), then by the chain rule of probability, I[ He( B)) is the agent's overall chance of avoiding catastrophe. For given x, y, M, n", the agent's multiplicative regret is
T
T
R (x. y, 14, T1 = log II
14 (2.) - log II 14 (1( vt)
"One could also define the multiplicative regret as R Ih HITh (x.)) II= (e( but our definition is actually stricter: limr- Rt + 0 implies limy Ht + 0, while the reverse is not true. In particular, limy-+o0 R + O is trivial if lim I 14" (xx) -+ O.
For example, it suffices for X' to have finite Lebesgue mea- sure. Note that this does not imply boundedness. Alternatively, o-smoothness can be defined with respect to different distribu- tion; see Definition I of Block al. (2022).
4

---

Avoiding Catastrophe in Online Learning by Asking for Help
when all payoffs are strictly positive. To handle the case where some payoffs are zero, we assume the existence of 140" > 0 such that 14"(xx) 2 pD always. Thus only the agent's 's payoffs can be zero, so we can safely define R2 (z. y, J4, -") = oo whenever H4r (T(, y1) = O for some We write R = R2 (x. y, μ4, T" for brevity.
We also have the following corollary of Theorem 4.1: Corollary 4.1.1. Even when (²"()) 1 for all t and x, any algorithm with sublinear queries satisfies
T pr pe vr)
[T. E
lim T T-20 p.
sup
E
II [==1
=0
The assumption of 14 (2+) 2 pD > 0 means that the men- tor cannot be abysmal. In fact, we argue that high-stakes AI applications should employ mentor who is almost always safe, i.e., 140" Re 1. If no such mentor exists for some applica- tion, perhaps that application should be avoided altogether.
In other words, even if the mentor never causes catastrophe, any algorithm with sublinear queries causes catastrophe with probability 1 as T - oo in the worst case.
4.1. Intuition
We also define the agent's ss additive regret as
We partition X' into equally-sized sections that are "inde- pendent" in the sense that querying an input in section i provides no information about section j. There will be f(T) sections, where f is a function that we will choose. If [Qrl E o(J(T), most of these sections will never con- tain a query. When the agent sees an input in a section not containing a query, it essentially must guess, meaning will be wrong about half the time. We then choose a payoff function (which is the same for all time steps) which makes the wrong guesses costly as possible, subject to the local generalization constraint. Figure/ fleshes out this idea.
T
T Σ
(2r, y, 14, T") = Σ
14 (3T)
(1 we)
and similarly write Rij- (. y V. x) for brevity. For both objectives, we desire subconstant worst-case regret: the total (not average) expected regret should go to 0 for any f
and x x". Formally, we want lim sup pm E R 0 and limy- pm. E [[Rt] = 0.
VC and Littlestone dimensions. VC dimension (Vapnik & Chervonenkis, 1971) and Littlestone dimension (Littlestone, 1988) are standard measures of learning difficulty which capture the ability of a hypothesis class (in our case, a policy class) to realize arbitrary combinations of labels (in our case, actions). We omit the precise definitions since we only utilize these concepts via existing results. See Shalev- Shwartz& & Ben-David (2014) for comprehensive overview.
The choice of f is crucial. One idea is f(T) = T. If the agent is wrong about half the time, and the average payoff' for wrong actions 1 I7. we can estimate the regret as
T
T
pi (x)) - log II R = log II
(e Mt)
1=1
t=1
Misc. The diameter of a set S S. X is defined by (S) = max ||x- - 2'Il. All logarithms and expo- nents are base unless otherwise noted. For convenience, treat minzee (xr) do for any function f.
L
T/2
R log 1 - log
1
4T
T
L
log
1
2
4T
T
L
4. Avoiding catastrophe with sublinear queries is impossible in general
23
2 47
L
We first show that in general, any algorithm with sublinear mentor queries has unbounded regret in the worst-case, even when inputs are i.i.d on [0. 1] and fu does not vary over time. The formal proofs are deferred to Appendix A, but we provide intuition and define the construction here.
8
Thus f(T) = T can at best give us a constant lower bound on regret. Instead, we choose ʃ such that QQl E o(f(T)) and f(T) E o(T). Specifically, we choose f(T) max( / /sup 1I 1). Most sections still will not contain a query, so the agent is still wrong about half the time, but the payoff for wrong actions is worse. Then
Theorem 4.1. Any algorithm with sublinear queries has un- bounded worst-case regret (both multiplicative and additive) as T + cc. Specifically,
T/2
R RJ log 1- log (1-
L
T
sup B [R sup m
E(R# 1
EQ
T
AS(T)
sup
El[QT +1
LT
8f(T)
Intuitively, the regret decreases as the number of queries in- creases. However, as long as the number of queries remains sublinear in T, the regret is unbounded as T - co.
T
En
I sup mn E E(QT(] +
5

---

Avoiding Catastrophe in Online Learning by Asking for Help
p(2, 1)
2T(
payoff/ j
((xz, 0)
0
2 f(7)
3 S(T)
S(T)-1 S(T)
f(T)
input a
Figure An illustration of the construction we use to prove Theorem 4.1 (not to scale). The horizontal axis indicates input a E [0, 1] = X' and the vertical axis indicates the payoff p(a, y) E [0, 1]. The solid line represents (1r, 0) and the dotted line represents p(x; 1). In each section, one of the actions has the optimal payoff of I, and the other action has the worst possible payoff allowed by L, reaching a minimum of 2 Crucially, both actions result in a payoff of at boundaries between sections: this allows us to "reset" for the next section. result, we can freely toggle the optimal action for each section independently.
which produces the bound in Theorem 4.1.
Proposition E.I, x satisfies local generalization.
VC dimension. The class of mentor policies in our con- struction has VC dimension f(T); across all possible values of T' this implies infinite VC (and Littlestone) dimension. We know that this is necessary given positive results.
5. Avoiding catastrophe given finite VC or Littlestone dimension
Theorem 4.1 shows that avoiding catastrophe is impossible in general. What if we restrict ourselves to settings where standard online learning is possible? Specifically, we as- sume that nth belongs to a policy class IT where either (1) II has finite VC dimension d and æ is a-smooth or (2) II has finite Littlestone dimension d.? This section presents simple algorithm which guarantees subconstant regret (both multiplicative and additive) and sublinear queries under ei- ther of those assumptions. Formal proofs are deferred to Appendix B but we provide intuition and a proof sketch here.
4.2. Formal definition of construction
Let X' [o, 1] and D. = UX)) for each t E [T]. where (X) is the uniform distribution on X. Assume that L s 1 this will simplify the math and only makes the problem easier for the agent. We define a family of payoff functions parameterized by a function f : N + N and bit string a = (01, 02....,afm7) E {0, ()(T)) The bit aj will denote the optimal action in section j. Note that S(T) 2 1.
For each j [S(T)), we refer to X, the jth section. Let m, = 1-0.5 be the midpoint of Xj- f(T)
+-1 ((T) |
5.1. Intuition behind the algorithm
Algorithm has two simple components: (1) run a modified version of the Hedge algorithm for online learning, but (2) ask for help for unfamiliar inputs (specifically, when the input is very different from any queried input with the same action under the proposed policy). Hedge ensures that the number of mistakes (i.e., the number of time steps where the agent's ' action doesn't 't match the mentor's) is small, and asking for help for unfamiliar inputs ensures that when we do make a mistake, the cost isn' too high. This algorithmic structure seems quite natural: mostly follow baseline strategy, but ask for help when out-of-distribution.
Assume that each x, belongs to exactly one X, (this happens with probability 1, so this assumption does not affect the expected regret). Let jzx) denote the index of the section containing input æ. Then ffa is defined by
y = 0z(2)
(1,((x.)) = 1-L 2T(T)
(mj(s) -xl
if y # oz(x)
We use this payoff function for all time steps: 14 ffa for all t E [2'. Let Thth be any optimal policy for Pf.. Note that there is a unique optimal action for each xı, since each dr belongs to exactly one X,; formally, > = (x.))
Hedge. Hedge (Freund & Schapire, 1997) is standard online learning algorithm which ensures sublinear regret when the number of hypotheses (in our case, the number of
For any E {0, 1)( Mf.a is piecewise linear (trivially) and continuous (because both actions have payoff on the boundary between sections). Since the slope of each piece in {-L, O, L), Ps.a is Lipschitz continuous. Thus by
RReaal from Section 1.3 that standard online learning becomes tractable under either of these assumptions.
6

---

Avoiding Catastrophe in Online Learning by Asking for Help
policies in IT) is finite." We would prefer not to assume that IT is finite. Luckily, any policy in IT can be approximated within e when either (I) Il has finite VC dimension and æ is o-smooth or (2) II has finite Littlestone dimension. Thus we can run Hedge on this approximative policy class instead.
Algorithm I successfully avoids catastrophe assuming finite VC Littlestone dimension.
Inputs: T' E N, E R>o, d E N, policy class 11 if II has VC dimension then
IT < any smooth e-cover of II of size at most (41/e)4
(see Definition 5.3)
One other modification is necessary. In standard online learning, losses are observed on every time step, but our agent only receives feedback in response to queries. To handle this, modify Hedge to only perform updates time steps with queries and to issue query with probability on each time step. Continuing our lucky streak, Russo et al. (2024) analyze exactly this modification of Hedge.
else
II any adversarial cover of II of size most (eT/d)d (see Definition 5.4)
S - 0
w((T) ) + 1 for all a E II
p 1/VeT
1) 4- max plo IiI 2T
5.2. Local generalization
for from to T do
Run one step of Hedge, which selects policy nt with probability p hedgeQuery t true with probability 1 hedgeQuery + false if hedgeQuery' then
Local generalization is vital: this is what allows us to detect when an input is unfamiliar. Crucially, our algorithm does not need to know how inputs are encoded in IR" and does not need to know L: it only needs to be able to compute the nearest-neighhor distance (il(x.))eSty=m((e) || - æ=|- Thus only need to assume that there exists some encoding satisfying local generalization.
Query mentor and observe x (xx)
((l, +- (xx(2) + x (x;) for all x e f E 4- min ((t,
w(T) + ((T))ex(pp ((((((t ())) for i e īI
To elaborate, recall the example that 3 mm spot and a 3.1 mm spot on X-rays likely have similar risk levels (assuming similar density, location, etc.). the risk level abruptly increases for any spot over mm, then local generalization may not hold for a naive encoding which treats size as single dimension. However, more nuanced encoding would recognize that these two situations a 3 mm vs 3.1 mm spot are in fact not similar. Constructing suitable encoding may be challenging, but we do not require the agent to have explicit access to such an encoding: the agent only needs a nearest-neighbor distance oracle.
Te < arg migmin E(t,
else
P(x) t w(T)/ E w(x for all x e II Sample ne P
if min (a.))ES: I| æ1| > e//n then
Ask help if ofoutof-distributton
Query mentor (if not already queried this round) and observe π: TT (xx)
S 5 SU ((2,, H (x:)))
else
Otherwise, follow Hedge's 's chosen policy Take action (x(x)))
Conceptually, the algorithm only needs to be able detect when an input is unfamiliar. While this task remains far from trivial, we argue that it is more tractable than fully con- structing a suitable encoding. See Section 6 for discussion of potential future work on this topic.
standard "one versus rest" reduction. We first prove regret and query bounds parametrized by
Theorem 5.1. Let y {0, 1}. Assume Tth II where either (1) II has finite VC dimension d and x is o-smooth. or (2) IT has finite Littlestone dimension d. Then for any T E N and E E
We note that these encoding-relaan rellttdd questions apply simi- larly to the more standard assumption of Lipschitz continu- ity. In fact, Lipschitz continuity implies local generalization when the mentor is optimal (Proposition E. We also men- tion that without local generalization, avoiding catastrophe is impossible even when the mentor policy class has finite VC dimension and æ is a-sooohh (Theorem E.2).
P
Algorithm I satisfies
2T.
(
dI. Te 1+/n 1/n log(T (og(T+ 11E)
E R E
dL Te 14/m
E [ E
log(T + +1/E)
5.3. Main result
For simplicity, here we only state our results for y = {0, 1}: Appendix C extends our result to many actions using the
(TT
T
d Te log([ +
E E(diam(x)"'
E[[Qr| o
E
$Chapter 5 of Slivkins et al. (2019) and Chapter 21 of Shalev- Shwartz& & Ben-David (2014) give modern introductions to Hedge.
'The reader may notice that we do not update S in this case. This is simply because those updates not necessary for the desired bounds and omitting these updates simplifies the analysis.
7

---

Avoiding Catastrophe in Online Learning by Asking for Help
In Case 1, the expectation is over the randomness of both and the algorithm, while in Case 2, the expectation is over only the randomness of the algorithm. The bounds clearly have no dependence on a in Case 2, but we include anyway to avoid writing two separate sets of bounds.
We begin by formalizing two notions of approximating a policy class:
Definition 5.3. Let U be the uniform distribution over X. For > 0, a policy class II smooth s-cover of a policy class II if for every E II, there exists ã E Iî such that Prz-ul(T() # [()) S.
To obtain subconstant regret and sublinear queries, we can -2n
choose T'2+11 This also satisfies 2Le < pD for
Definition 5.4. A policy class IT is an adversarial cover of policy class II if for every a E X and iT E II. there exists ग E Iī such that π (xx) = 7 (1xa for all L E (T).
large enough T.
Theorem 5.2. Let y 10, Assume T.h E 1l where either (1) II has finite VC dimension d and x is o-smooth or (2) II has finite Littlestone dimension d. Then for any T E N, Algorithm 1 with e = T22441
An adversarial cover is a perfect cover by definition. The idea of a smooth E-cover is that if the probability of dis- agreement over the uniform distribution is small, then the probability of disagreement over a o-smooth distribution cannot be too much larger.
2n
2n41 satisfies
dL T'mmi log'r)
E [
E0
0/40
dL
Lemma 5.1. Let 11 be smooth s-cover of Il and let D be o-smooth distribution. Then for any π II, there exists I E I1 such that PI [=(x) + [xx)] SE/o.
B
[ E0
T log
B|[QT|| 60
(T
(1 loggT T + [z) (Ta+43
Am+1
Proof. Define S( for X' (xx) + (())). By the definition of a smooth e-cover, there exists # E IT such that Pre-u E S()) S s. Since D is a-smooth, Przeo ( (z) * [xx]] = Pra-n(æ E S(t) S Prz-u [x E (()))/o a S E//o, as claimed.
Before proceeding to the proof sketch, we highlight some advantages of our algorithm.
Limited knowledge required. Our algorithm needs to know II, as is standard. However, the algorithm does not need to know a (in the smooth case) or L. Although Al- gorithm as written does require T as an input, it can be converted into an infinite horizon/anytime algorithm via the standard "doubling trick" (see, e.g., Slivkins al., 2019).
The existence of small covers is crucial:
Lemma 5.2 (Lemma 7.3.2 in Haghtalab (2018)().. For all E >> O, any policy class of VC dimension d admits a smooth E-COver of size at most (41/E)².
Unbounded environment. Our algorithm can handle unbounded input space: the number of queries simply scales with the maximum distance between observed inputs in the form of [[diam(x))")
Lemma 5.3 (Lemmas 21.13 and A.5 in Shalev-Shwartz & Ben-David (2014)). Any policy class of Littestone dimen- sion d admits an adversarial cover of size at most (eT/dy
We will run a variant of Hedge on II. The vanilla Hedge algorithm operates in the standard online learning model where on each time step, the agent selects policy (or more generally, a hypothesis), and observes the loss of every policy. In general the loss function can depend arbitrarily on the time step, the policy, and prior events, but we will only use the indicator loss function é(t, л) = (xx(x;) * nT (x:)). Crucially, whenever we query and learn n" (2;), we can compute E(1, m) for every x E IT.
Simultaneous bounds for all μr. Recall that the agent never observes payoffs and only learns from mentor queries. This means that the agent's ss behavior does not depend on μe at all. In other words, the distribution of (æ,, depends on n but not μ. Consequently, a given x" induces single dis- tribution (z. y) which satisfies the bounds in Theorem 5.2 simultaneously for all ia satisfying local generalization.
5.4. Proof sketch
We cannot afford to query every time step, however. Recently, Russo et al. (2024) analyzed a variant of Hedge where losses are observed only in response to queries, which they call "label-efficient feedback". They proved a regret bound when a query is issued on each time step with fixed probability p. Lemma 5.4 restates their result in a form that is more convenient for us. See Appendices B.1 and B.3 for details our usage of results from Russo al. (2024). Full
The formal proof of Theorem 5.1 can be found in Ap- pendix B, but we outline the key elements here. The regret analysis consists of two ingredients: analyzing the Hedge component and analyzing the "ask for help when out-of- distribution" component. The former will bound the number of mistakes made by the algorithm (i.e., the number of time steps where the agent's action doesn't 't match the mentor's ss) and the latter will bound the cost of any single mistake. We must also show that the latter does not result in excessively many queries, which we do via a novel packing argument.
10See also Haussler & Long (1995) Lemma 13.6 in Boucheron et al. (2013) for variants of this lemma.
8

---

Avoiding Catastrophe in Online Learning by Asking for Help
pseudocode for HEDGEWTTHQUERRISS can also be found in the appendix (Algorithm 2).
and Haghtalab al. (2022) show how replace discretiza- tion approaches like ours with oracle-effcient approaches, where a small number of calls to an optimization oracle are made per round. We are optimistic about leveraging such techniques to obtain efficient algorithms in our setting.
Lemma 5.4 (Lemma 3.5 in Russo et al., 2024), Assume II is finite. Then for any loss function f [T] x II + [0, 1] and
query probability p > O, HEDGEWITIQUERRES, enjoys the regret bound
Local generalization. Our algorithm crucially relies on the ability to detect when an imput is unfamiliar, i.e., differs sig- nificantly from prior observations in a metric space which satisfies local generalization. Without this ability, the practi- cality of our algorithm would be fundamentally limited. One option is to use out-of-distribution (OOD) detection, which is conceptually similar and well-studied (see Yang et al., 2024 for a survey). However, is an open question whether standard OOD detection methods are measuring distance in metric space which satisfies local generalization.
T
< log I p²
Σ Bl
min Σ acn
B(e(t,
where n, is the policy chosen at time and the expectation is over the randomness of the algorithm.
We apply Lemma 5.4 with l(t, TT) 1(x(2;)) & xr' (xx)) and combine this with Lemmas 5.2 and 5.1 (in the o-smooth case) and with Lemma 5.3 (in the adversarial case). This
yields a O Te (og(1/)) log T) bound on the number of mistakes made by Algorithm (Lemma B.
We are also interested in alternatives to local generalization. Theorem E.2 shows that our positive result breaks down if local generalization is removed, so some sort of assumption is necessary. One possible alternative is Bayesian inference. We intentionally avoided Bayesian approaches in this pa- per due to tractability concerns, but it seems premature to abandon those ideas entirely.
The other key ingredient of the proof is analyzing the "ask for help when out-of-distribution component. Combined with the local generalization assumption, this allows us to fairly easily bound the cost of a single mistake (Lemma B .) The trickier part is bounding the number of resulting queries. is tempting to claim that the inputs queried in the out-of- distribution case must all be separated by at least //aa and thus form an g//"=--pcdar packing. but this is actually false.
MDPs. Finally, we are excited to apply the ideas in this paper to Markov Decision Processes (MDPs): specif- ically, MDPs where some actions are irreversible ("non- communicating") and the agent only gets one attempt ("singlc-episodee), In such MDPs, the agent must not only avoid catastrophe but also obtaín high reward. As discussed in Section 2, very little theory exists for RL in non-communicating single-episode MDPs. Can an agent learn near-optimal behavior in high-stakes environments while becoming self-sufficient over time? Formally, we pose the following open problem:
Instead, we bound the number of data points (i.e., queries) needed to cover set with respect to the realized actions of the algorithm (Lemma B.6). This contrasts with vanilla packing arguments which consider all data points in aggre- gate. The key to our analysis is that the number of mistakes made by the algorithm which we already bounded in Lemma B.1 gives us crucial information about how data points are distributed with respect to the actions of the al- gorithm. Our technique might be useful in other contexts where a more refined packing argument is needed and a bound on the number of mistakes already exists.
Is there algorithm for non-communicatiin single-episode undiscounted MDPs which ensures that both the regret and the number of mentor queries are sublinear in T?
6. Conclusion and future work
In this paper, we proposed model of avoiding catastrophe in online learning. We showed that achieving subconstant regret in our problem (with the help of mentor and local generalization) is no harder than achieving sublinear regret in standard online learning.
Impact statement
As Al systems become increasingly powerful, we believe that the safety guarantees of such systems should become commensurately robust. Irreversible costs are especially worrisome, and we hope that our work plays a small part in mitigating such risks. We do not believe that our work has any concrete potential risks that should be highlighted here.
Remaining technical questions. First, we have not re- solved whether our problem is tractable for finite VC di- mension and fully adversarial inputs (although Appendix D shows that the problem is tractable for at least some classes with finite VC but infinite Littlestone dimension). Second, the time complexity of Algorithm currently stands at a hefty ((īi per time step plus the time to compute îi. In the standard online learning setting, Block et al. (2022)
9

---

Avoiding Catastrophe in Online Learning by Asking for Help
Author contributions
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and
games. Cambridge university press, 2006.
B. Plaut conceived the project. B. Plaut designed the mathe- matical model with feedback from H. Zhu and Russell. B. Plaut proved all of the results. H. Zhu participated in proof brainstorming and designed counterexamples for several early conjectures. B. Plaut wrote the paper, with feedback from H. Zhu and S. Russell. S. Russell supervised the project and secured funding.
Cohen, M. K. and Hutter, M. Pessimism About Unknown Unknowns Inspires Conservatism. In Proceedings of Thirty Third Conference on Learning Theory, pp. 1344- 1373. PMLR, July 2020. ISSN: 2640-3498.
Cohen, M. K., Catt, E., and Hutter, M. Curiosity Killed or Incapacitated the Cat and the Asymptotically Optimal Agent. IEEE Journal on Selected Areas in Information Theory, 2(2):665-677, June 2021. Conference Name: IEEE Journal on Selected Areas in Information Theory.
Acknowledgements
This work was supported in part by gift from Open Phi- lanthropy to the Center for Hluann-Compatie AI (CHAI) at UC Berkeley. This paper also benefited from discus- sions with many other researchers. We would like to espe- cially thank (in alphabetical order) Aly Lidayan, Bhaskar Mishra, Cameron Allen, Juan Sevaao-KKainn Mattco Russo, Michael Cohen, Nika Haghtalab, and Scott Emmons. We would also like thank our anonymous reviewers for helpful feedback.
Critch, A. and Russell, S. TASRA: a taxonomy and anal- ysis of sccietal-scale risks from AL. arXiv preprint arXiv:2306.064 069244 2023.
Esser, S., Haider, H., Lustig, C., Tanaka, T., and Tanaka, K. Action-effect knowledge transfers similar effect stim- uli. Psychological Research, 87(7):2249-22) October 2023.
Freund, Y. and Schapire, R. E. A decision-theoreee general- ization of on-line learning and an application to boosting, Journal of computer and system sciences, 55(1):119-139 19-139, 1997.
References
Abaimov, S. and Martellini, M. Artificial Intelligence in Autonomous Weapon Systems, pp. 141-177. Springer International Publishing, Cham, 2020.
Grinsztajn, N., Ferret, J., Pietquin, O.,, Preux, P., and Geist, M. There Is No Turning Back: A Self-Supervised Ap- proach for Reversibility-Awar Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 34, pp. 1918-1 Curran Associates, Inc., 2021.
Altman, E. Constrained Markov Decision Processes. Rout- ledge, 2021.
Azar, M. G., Osband, I., and Munos, R. Minimax Regret Bounds for Reinforcement Learning. In Proceedings of the 34th International Conference on Machine Learning, pp. 263 272. PMLR, July 2017. ISSN: 2640-3498.
Gu, S., Yang, L., Du, Y., Chen, G., Walter, F., Wang, J., and Knoll, A. A review of safe reinforcement learning: Methods, theories, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12); 11216- 1123,, 2024.
Barman, S., Khan, A., Maiti, A., and Sawarni, A. Fairness and welfare quantification for regret in multi-armed ban- dits. In Proceedings of the Seventh Conference on Artificial Intelligence (AAAI 2023), 2023.
Guembe, B., Azeta, A., Misra, S., Osamor, V. C., Fernandez- Sanz, L., and Pospelova, V. The Emerging Threat of AT-driven Cyber Attacks: Review, Applied Artificial Intelligence, 36(1), December 2022.
Bengio, Y., Hinton, G., Yao, A., Song, D., Abbeel, P., Dar- rell, T. Harari, Y. N.. Zhang, Y.-Q., Xue, L., Shalev- Shwartz, S., et al. Managing extreme AI risks amid rapid progress. Science, 384(6698):842 8454 2024.
Hadfield-Menell D., Milli, S., Abbeel, P., Russell, S., and Dragan, A. D. Inverse reward design. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp.
Betancourt, M. A Conceptual Introduction to Hamiltonian Monte Carlo, July 2018 arXiv: 1e:::1001.2444 [stat].
Red Hook, NY, USA, December 2017. Curran Associates Inc.
Block, A., Dagan, Y.. Golowich, N., and Rakhlin, A. Smoothed online learning is as easy as statistical learn- ing. In Conference on Learning Theory, pp. 1716-1786. PMLR, 2022.
Haghtalab, N. Foundation of Machine Learning, by the People, for the People. PhD thesis, Microsoft Research, 2018.
Haghtalab, N., Han, Y., Shetty, A., and Yang, K. Oracle- efficient online learning for smoothed adversaries. Ad- vances in Neural Information Processing Systems, 35: 4072-4084, 2022.
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013.
10

---

Avoiding Catastrophe in Online Learning by Asking for Help
Haghtalab, N., Roughgarden, T., and Shetty, A. Smoothed analysis with adaptive adversaries. Journal of the ACM, 71(3):1-34, 2024.
Moldovan, T. M. and Abbeel, P. Safe exploration in Markov decision processes. In Proceedings of the 29th Interna- tional Conference on Machine Learning, ICML 12, pp. 1451-1458, Madison, WI, USA. June 2012. Omnipress.
Hajian, S. Transfer of Learning and Teaching: A Review of Transfer Theories and Effective Instructional Practices. IAFOR Journal of Education, 7(1):93-111, 2019. Pub- lisher: International Academic Forum ERIC Number: EJ1217940.
Mouton, C., Lucas, C.,, and Guest, E. The operational risks of AI in large-scale biological attacks. Technical report, RAND Corporation, Santa Monica, 2024.
Osa, T., Pajarinen, J., Neumann, G., Bagnell, J., Abbeel, P., and Peters, An Algorithmic Perspective on Imita- tion Learning. Foundations and trends in robotics. Now Publishers, 2018.
Hanneke, S. Theory of DisagreementtBaseer Active Learn- ing. volume 7. Now Publishers Inc., Hanover, MA, USA, June 2014.
Quiñonero-Cante J., Sugiyama, M., Schwaighofer, A., and Lawrence, N. D. Dataset shift in machine learning. MIT Press, 2022.
Haussler, D. and Long, P. M. A generalization of Sauer's lemma. Journal of Combinatorial Theory, Series A, 71 (2):219-240, August 1995.
Rajpurkar, P., Chen, E.,, Banerjee, O., and Topol, E. Al in health and medicine. Nature medicine, 28(1):31-38, 2022.
Hendryeks, D., Mazeika, M., and Woodside, T. An overview of catastrophic AI risks. arXiv preprint arXiv:2306. / 12001, 2023.
Russo, M., Celli, A., Colini Baldeschi, R., Fusco, F, Haimovich, D., Karamshuk, D., Leonardi, S., and Tax, N. Online learning with sublinear best-action queries. Advances in Neural Information Processing Systems, 37: 40407-40433, 2024.
Jaksch, T., Ortner, R., and Auer, P. Near-optimal Regret Bounds for Reinforcement Learning. Journal of Machine Learning Research, 11651)11633-1600 2010.
Jung, H. Ueber die kleinste kugel, die eine räumliche figur einschliesst. Journal für die reine und angewandte Math- ematik, 13:2241255,, 1901.
Shalev-Shwartz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, edition, May 2014.
Kohli, and Chadha, A. Enabling pedestrian safety using computer vision techniques: A case study of the 2018 Uber Inc. self-driving car crash. In Advances in Infor- mation and Communication: Proceedings of the 2019 Future of Information and Communication Conference (FICC), Volume 1, pp. 261-279. Springer, 2020.
Slivkins, A. Contextual Bandits with Similarity Informa- tion. In Proceedings of the 24th Annual Conference on Learning Theory (COLT), pp. 679-702, December 201 1. ISSN: 1938-7228.
Slivkins, A. et al. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1- 2):1-286, 2019.
Kosoy, V. Delegative Reinforcement Learning: learning to avoid traps with a little help. SafeML ICLR 2019 Workshop, July 2019.
Spielman, D. A. and Teng, S.-H. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3): 385 463, 2004.
Littlestone, N. Learning quickly when irrelevant attributes abound: A new threshll algorithm. Machine learning, 2:285-318, 1988.
Liu, T., Zhou, R., Kalathil, D., Kumar, P., and Tian, C. Learning policies with zero or bounded constraint viola- tion for constrained mdps. Advances in Neural Informa- fion Processing Systems, 34:17183-17193, 2021.
Stradi, F. E., Castiglioni, M., Marchesi, A., and Gatti, N. Learning adversarial MDPs with stochastic hard con- straints. arXiv preprini 2rXiv:2403.03672, 2024.
Turchetta, M., Berkenkamp. F., and Krause, A. Safe Explo- ration in Finite Markov Decision Processes with Gaussian Processes. In Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Maillard, O.-A., Mann, T., Ortner, R., and Mannor, S. Active Roll-outs in MDP with Inreversible Dynamics. July 2019.
Mindermann, S., Shah, R., Gleave, A., and Hadeilld-Menell, D. Active Inverse Reward Design. In Proceedings of the 1st Workshop on Goal Specifications for Reinforcement Learning, 2018
Vapnik, N. and Chervonenkis, A. Y. On the Uniform Convergence of Relative Frequencies Events to Their Probabilities. Theory of Probability & Its Applications,

---

Avoiding Catastrophe in Online Learning by Asking for Help
16(2):244-20, January 1971. Publisher: Society for Industrial and Applied Mathematics.
Villasenor, J. and Foggo, V. Artificial intelligence, due
process and criminal sentencing. Michigan State Law Review, pp. 295-354, 2020.
Wachi, A., Shen, X., and Sui, Y. A Survey of Constraint Formulations Safe Reinforcement Learning. volume 9, pp. 8262-8271, August 2024. ISSN: 1045-0823.
Wu, Y. Lecture notes on: Information-theorreic methods for high-dimensional statistics. 2020.
Yang. J., Zhou, K., Li, Y., and Liu, Z. Generalized out-of- distribution detection: A survey. International Journal of Computer Vision, pp. 1-28, 2024.
Zhao, W., He, T., Chen, R., Wei, T., and Liu, C. State-wise Safe Reinforcement Learning: Survey. volume 6, pp. 681 6814-682, August 2023. ISSN: 1045-0823.
12

---

Avoiding Catastrophe in Online Learning by Asking for Help
A. Proof of Theorem 4.1
A.I. Proof notation
1
4f(2) In words, 24 is relatively close the midpoint of X This will imply that the suboptimal action is in fact quite suboptimal. This also implies that 2y is in Xj, since each X) has length (T).
Let My be the set of time steps < T where [m - zrl S
2. Let q-q = (j E (S(T)) oi & Xj Vi E Qr be the set of sections that are never queried. Since each query appears in exactly one section (because each input appears in exactly one section), |J-ql 2 f(T) - -Qrl-
3. For earchch E J Q. let y be the most frequent action among time steps in My: y arg (a (tt E M, : y= y- Q = aj # y') be the set of sections where the more frequent action is wrong according to 1ffa-
4. Let J'-q (j
5. Let M = {t E M, yt # aj} } be the set of time steps where the agent chooses the wrong action according to jf,a. and
Tz is close to the midpoint of section j.
Since x, y, and contrast, the partition X' = .
random variables, all variables defined top of them (such M,) are also random variables. In
......,,.)))) Xyery) and properties thereof (like the midpoints my) are not random variables.
A.2. Proof roadmap
The proof considers arbitrary algorithm with sublinear queries, and proceeds via the following steps:
1. Show that multiplicative regret and additive regret are tightly related (Lemma A.1). We will also use this lemma for our positive results.
2. Prove an asymptotic density lemma which we will use to show that f(T) VIQrIT is asymptotically between [Qr] and T (Lemma A.2).
3. Prove a simple variant of the Chernoff bound which we will apply multiple times (Lemma A.3).
4. Show that with high probability, Ejes |M large for any subset of sections S (Lemma A.4).
5. Prove that | is large with high probability (Lemma A.5).
The key lemma is Lemma A. which shows that a randomly sampled produces poor agent performance with high probability. The central idea is that at least f(T) |Qrl sections are never queried (which is large, by Lemma A.2), so the agent has no way of knowing the optimal action in those sections. As a result, the agent picks the wrong answer at least half the time on average (and at least quarter of the time with high probability). Lemma A.4 implies that constant fraction of those time steps will have significantly suboptimal payoffss, again with high probability.
7. Apply sup E R (Ir, y. ,4, T)) 7 2.y
E Ry (a,, y, Pf, ). Here U(0, 1) is the uniform 2.y
distribution over bit strings of length S(T) and we write n" a ~ U(0,, ((T) with slight abuse of notation, since x is not drawn from U U(10, ())) but rather is determined by a which is drawn from U U(10, 1))))))
8. The analysis above results in a lower bound on Ry. The last step is to use Lemma A. obtain a lower bound on Rt
Step 7 is essentially an application of the probabilistic method: if a randomly chosen Hf.a has high expected regret, then the worst-case i also has high expected regret. We have included subscripts in the expectations above to distinguish between the randomness over a and x, y. When subscripts are omitted, the expected value over all randomness, i.e., a, œ, and y.
A.3. Proof
R min ae pe(
Lemma A.I. If (xx) 2 pe(ae, We) for all I, then Rt S R2. If (r(ee. > 0 foror all I, then R2
Proof. Recall the standard inequalities 1 - 1 5 log < 1 for any > 0.
Part 1: R$ < Ry. If (e(2z,))) = 0 for any E [T], then R = co and the claim is trivially satisfied. Thus assume
p4 (I 31) > 0 for all t E [T].
T
T
R$ = Σ
1h m (x:)
Σ
He( tml
(Definition of R
t=l
13

---

Avoiding Catastrophe in Online Learning by Asking for Help
T
(It)
Me(ass Mc)
ve) S M4 (2x) and 0 - M4 (x4) S 1)
p46 (2+)
po (x))
log a for any 0)
log
(1e yc)
a
[=1
T
log
mh (2:t) - log II pel We)
(Properties of logarithms)
Rt
(Definition of R
Part R I / eln (e ye). We have
R log II Pt (Ir) log II
pe Me)
(Definition of R given pe yo) Vt e [T])
t=1
T
14 (1:a)
log
(Properties of logarithms)
1e (1', Me)
144 (Ire)
14 (el Mbb
(log S a for any > 0)
(ee We)
Pe( Me)
(4, (21)) ( - (1 Mc)
(Me(Ie, Mr) 2 min (It, 0 Vt [T])
minselay (1 Mi)
Mel Me)
<E(T]
1
(4l - (o(
(Arithmetic)
|r Pe He)
R
(Definition of RT)))
min Pe (1),
claimed.
Lemma A.2. Let a, Rso + Rso be functions such that a(x) o(b(z)). Then d(x) va(x)b(x) satisfies a(x) o(c(x)) and e(x) o(b(x)).
Proof. Since a and are strictly positive (and thus well), we have
a(x) a(x)
a(x)
va(z)b(x) c(x)
c(x)
V va(x)b(x)
b(x)
b(x)
b(x:
Then a(x) E o(b(x:)) implies
lim a(x) lim cxx) lim
a(x)
2-000 c(x) x00
b(x)
2
| b(x)
= 0
as required.
Lemma A.3. Let 21,..., Fn be i.i.d. variables in (0, 1} and let Z = En 2i. E 2 W, then Pr Pr s W/2 < exp(-W/8).
Proof. By the Chernoff bound for i..d. binary variables, we have Pr/Z < E[Z]/2] < (pp(-E/2/8)) Since - E[Z < -W and exp is an increasing function, we have exp(-Elp E[Z]/8) &
Also, W/2 < E|Z)/2 implies Pr(Z < W/2] <
Pr[Z < [2))/2). Combining these inequalities proves the lemma.
14

---

Avoiding Catastrophe in Online Learning by Asking for Help
Lemma A.4. Let S C [S(T) be any nonempty subset sections. Then
TIS| 4
T I exp 16S(T)
Pr
Σ JES
M,
Proof. Fix any j [f(T).. For each E [T]. define the random variable 2, by 2 1ff M, for some j E S and
otherwise. We have & Mj iff xy falls within particular interval of length 2 Since these intervals are disjoint for different j's, we have 2
2y falls within portion of the input space with total measure 2/(2)
Since 2, is uniformly
random across [0, 1). we have B[za] = 2 Then E 1= z+] = EEjEE
Myll
T|SI
Furthermore, since T1,...,
2
are i.i.d., so are 21......2 2r. Then by Lemma A.3,
S 4S(T)
T1S1 16S(T)
-T 16f(T)
Pr
M1 S
S exp
< exp
jES
with the last step due to |S| 1. Lemma A.S. We have
Pr |W'م| f(T) B[[QT[]
f(T) - E
exp
16
Define random variable 2, 1jeJ' oo for each J-Q. By definition, if j J-Q, input in Xj is queried. Since queries outside of Xj provide information about djj the agent's actions must be independent of aj. In particular, the random variables aj and y are independent. Combining that independence with Pr(a; 0] Pr(a, = 1] = 0.5 yields Pr[z; = 1] = 0.5 for all j E J-Q. Then
Proof.
J Q1
E
Σ
jEJ-Q
11-21/2 [(T) - -EiQ011
Furthermore, since d1...., ()(T) independent, the random variables {2₁ E J-Q} are also independent. Applying Lemma A.3 yields the desired bound.
Lemma A.6. Suppose ʃ N N and independently sample U(10,1)1(2)) and U(X)F." 11 Then with probability at least exp (1ōJ(T7) exp [(T) -
16
LTU(T) -
R
fTT(T)²
Proof. Consider any j E J'Q and E Mj S My. By definition of My, we have |mj - xel s 45(T). Then by the definition of uff.a
1
Pf Bt) =
[ mj
2S(T)
51 L
(T(T)
4f(T)
1 4T(
Uhat is, the entire set .il....,,.000 "1,...,;T is mutually independent.
15

---

Avoiding Catastrophe in Online Learning by Asking for Help
Since (x1) 2 Fs Mt) always,
safely restrict ourselves to time steps & Mj for some j J'QQ and still
obtain a lower bound:
T E -A
R =
(Definition of R+)
Σ
E
(x))) (22,3
(ar)) 2 M ( 9t)
jeJiq LEM;
Σ
Σ
(1 - (3, Vc))
(14) = 1 always)
jeJiq tEM;
L
Σ Σ
1
(bound on (faa(Tt, (t) for I. E M2)
4f(T)
jEJ i
L|M
(Simplifying inner sum)
JEJL 4f(T)
Since j E J-Q. the mentor is not queried on any time step E Mj. so ye E {0, for all I Mj. Since the agent chooses one of two actions for each t Mj. the more frequent action must be chosen at least half of the time: y/- y for least half of the time steps in My. Since 0j + y for E J'-q we have Yt yd * aj for those time steps, so MM 2 |M 1/2. Thus
L
R
Σ
8f(T)
JEJ'_Q
By Lemma A.4, Lemma A.5, and the union bound, with probability at least exp (17(())) exp ( f(T) ((T))E((QU)) F[[@]]]
16
we
have Ejer'g |M,1 2 T|V'ol for all j E [f(T)] and |J'so 2
f(T)
= Assuming those inequalities hold, we have
4f(T)
4
L|MI
R 2 Σ
8f(T)
JEJ'A
L TIJ'
8f(T)
4T(T)
L
T
S(T) - -
8f(T)
4T(
4
LT( - El1Qrl1)
27 (T)
required.
For given f + N, define (T)(T) exp (1o7(T) exp (- .(T) ((T)-B[QT]) for brevity.
Theorem 4.1. Any algorithm with sublinear queries has unbounded worst-case regret (both multiplicative and additive) as T + sc. Specifically,
sup E[R sup E[R a (4g suppr." El[Qr[1+1
T
Proof. If the algorithm has sublinear queries, then there exists gT)) E o(T) such that sup,,, pm Eu.l < g(T). Consider any such s(T) satisfying g()) > 0. Since this holds for every p. also holds expectation over a U((O, ((T), so E
E[ < g(T).
Next, Lemma A.2 gives us gT) E ol o (T))) and Vo(T)T e o(T). Let f(T) = [ then f(T) E ((Vo(T)T) so (T) E (T)()) and I(T) E oT). First, this implies that limr- (T( = Second, g(T) E o({()) implies that
16

---

Avoiding Catastrophe in Online Learning by Asking for Help
exists To such that g(T) /(T)/2 for all T 2 To- We also have R 0 always since ffa (1i) Pffaat Me) always.
Then for all T 2 To we have
E
E
[ y, ue, π -"
Tht (m
m.y
(LI(
2ay(T) 0+ - ay(T))
(Lemma A.6 and R2 2 0)
2T)(T)²
LT(f(T) g(T))
2(1 (1-aa((T)) (y(l))
(R(Qr) S g(T))
27 f(T)²
LT
2 (1 aa(((()))
(o(T) s ((T)22)
22)((T)
Since lim 0g (T) = 0.
E
(x, y, u., [. 2
E
E
(R (ur....... (P..)......,.)...... xT))
,, z.y
x a~.(((01))1))
2.y
L.
- aa
(2)((T)
LT
EΩ
S(T)
T T
g(T)
This holds for any g(T o(T) such that s [[Q[]]] S g(T) and g(T) 0. Thus we can simply set g(T) sup,, E[[QT 1, since pm [r]] is indeed a function of only T.
Since "Ta (x1) 2 1/ (Zt, v1) for all E [T], Lemma A.1 implies that
sup E (x, y, u, [.,)
E
E
[R (a, y, (pfaa...,, m
" a.
2.1
T
EQ
sup
B1QQr|1+1 +1
completing the proof.
Corollary 4.1.1. Even when ppd (x) foror all and x, any algorithm with sublinear queries satisfies
lim T-400
sup E
II Po yt)
Proof. We have I1Th, p. (It)
from our construction. Then Lemma A.I implies that R2 > R so
exp(-Rt)) 2 exp( (sp(-R%) R
T
= exp log II
(1 ve) - log
1=1
ufa (Ie,
t=1
Then by Lemma A.6, with probability 1 1 (T),
T
LT(S(T) - B(QTTll)
LT
Pr. (V,, w1) 5 Sexp II
< exp
(T)(
( 28
17

---

Avoiding Catastrophe in Online Learning by Asking for Help
Since II Ps (ig ve) < always,
T
T
lim T-000 a ((0,1)10))
Psaa (1,, ye)
1 lim
Ps (1t,
7-+00 xm am(((001)110))
(1:ay(T) + -aa(() exp
28 (2S((T)) ))
LT
1 lim T-000
LT
v lim (1 - -aa(T)) lim exp
(-25((T)
T-x
T-000
= exp(-08
Since this upper bound holds for a randomly chosen Jf.a: nh, the same upper bound holds for a worst-case choice of μa, π among ,t, ,, which satisfy n4 (x) = for E [7], X. Formally,
T
lim T-000
sup (1)
E
II
Me vo)
50
Since IIT (e( Mr) 2 always, the inequality above holds with equality.
B. Proof of Theorem 5.2
B.1. Context on Lemma 5.4
Before diving into the main proof, we provide some context on Lemma 5.4 from Section 5: Lemma 5.4 (Lemma 3.5 in Russo et al., 2024). Assume is finite. Then for any loss function l: [7] x f + [0, 1] and query probability p > 0, HEDGeWITHQUERIES enjoys the regret bound
T
T
Σ E[E(t,
min Rell
E(e(t,
log
p²
where ny is the policy chosen at time and the expectation over the randomness of the algorithm.
Lemma 5.4 is restatement and simplification of Lemma 3.5 in Russo et al. (2024) with the following differences:
They parametrize their algorithm by the expected number of queries k instead of the query probability = k/T.
2. They include second parameter which is the eventual target number of queries for their unconditional query bound. In our case, expected query bound is sufficient, so simply set k = k.
3. They provide a second bound which is tighter for small k; that bound is less useful for us so we omit it.
4. Their "actions" correspond to policies in our setting, actions V. Their number of actions corresponds to [ii].
5. We include an expectation over both loss terms, while they only include an expectation over the agent's 's loss. This is because an adaptive adversary may choose the loss function for time t in a randomized manner. Since we eventually set Ett, π) = 1 (xx) + x (xx)), the randomization in corresponds to the randomization in It..
Altogether, since Russo et al. (2024) set = max (
Klogn kk
we end with r max (V p p² 2T
/2T"
Algorithm provides precise pseudocode for the HEDGE algorithm to which Lemma 5.4 refers.
B.2. Main proof
We use the following notation throughout the proof:
1. For each t [T], let St refer to the value of S at the start of time step t.
Let My = (t E [T] ne (xx) # (x;)) be the set of time steps where Hedge's proposed action doesn't 't match the mentor's 's. Note that MMr upper bounds the number mistakes the algorithm makes (the number mistakes could be smaller, since the algorithm sometimes queries instead of taking action n,(x)))
18

---

Avoiding Catastrophe in Online Learning by Asking for Help
Algorithm 2 A variant of the Hedge algorithm which only observes losses in response queries.
function HEDGEWITHQUERRESS w(x) < for all E II
(0, I], finite policy class Iī, unknown é: [T] π [0, 1J)
77 + max (v plog 2T
for from 1 to T do
with probability heddgequery + true with probability 1 - p: hedgeQuery + false if hedgeQuery then
Query and observe f(t, m) for all π πī 8* min ((l,
w(T) + w((r) exp(-n(( π) (*) for all e fT
Select policy arg min {(t, T)
else
P(T) t w(T)/ ( Erenn w(T') for all Ii
Sample иT ~ P
Select policy n
3. For S " X, let vol(S) denote the n--dimensional Lebesgue measure of S.
4. With slight abuse of notation, we will use inequalities of the form f(T) S g()) O(((T) to mean that there exists constant C' such that f(T) S 9(T)) + Ch(T).
5. We will use "Case 1" to refer to finite VC dimension and o-smooth æ and "Case 2" to refer to finite Littlestone dimension.
Lemma B.1. Let y {0, 13. Assume nrh E where either (1) 11 has finite VC dimension and æ is o-smooth, or (2) 11 has finite Littlestone dimension Then for any T and = 2 1/T," Algorithum satisfies
c (Tee ToT +1/E)
B[|MT]] EO
Proof. Define é [T] II J0, by by = ((T())) * TT (z;)) and let wh and प denote the values of w and ae respectively in BEEDGEIITHQUEREE while and ni refer the variables in Algorithm Then w and wa evolve in the exact same way, the distributions of n. and पद coincide. Also, 2 1/T implies that p 1/ VeT (0,1). Thus by Lemma 5.4,
T min Renl
log Iī p²
Ell(t,
B[l(t,
= Te log [
Since |Mrl -E= (xx( # (xx)) = EE (lt, Te), we have
Mr|] Te log |
min #ell
Σ (((() * x" (x:))
Case 1: Since il is a smooth e-cover and TM E 11, Lemma 5.1 implies that [ (x # T"' (x,))) s e/o for any स e Î..
Since [i]] < (41/e)a by construction (and such II guaranteed to exist by Lemma 5.2), we get
B[] < T' loogllg((()))) (ogg((1))())))))))) min RcNl
T'
dI' log'eoo((1/e))
Note that this lemma omits the assumption of ( n since do not need it for this lemma, and would like apply this lemma in the multi-action case without that assumption.
19

---

Avoiding Catastrophe in Online Learning by Asking for Help
d Te log(T To 1/e) EO
(
Case Since I1 an adversarial cover of and n II, there exists îi such that Ei ((a(Ie) + <²)x))
Since [1I] I (eT/d)² (with such II guaranteed to exist by Lemma 5.3),
|||MT|] s Te log
[I|]
min ( # (x))
#ell 1=1
s (edIn(eT/d))
6 Telog(T + 1/6)
eo
as required.
Lemma B.2. For all t (T), Me( y1) 2 (x.) Le
Proof. Consider an arbitrary [T]. If Qr, then (xr 36) pz (x)) trivially, so assume Qr. Let (x', arg (o)) |2: =|| Since & Qr, we must have ||2 x'1l S el/m.
We have y' = >='('') by construction of St and (xxx)) y' by construction of y/ Combining these with the local generalization assumption, we get
Melas, Ut) = pelze, Te (IIE)
Pelze, x == (x'))
2 (xr) ) -1|20 x'll
"1" (xx) L/
required.
Lemma B.3. Under the conditions of Theorem 5.1, Algorithm satisfies
dL
E
R
E
Te Tet+1/n log(T + 1/s)
dL To" 11/ log( ( + 1/6)
13
[
O
Proof. We first claim that yt = (zx) for all & Mr. Ift E Qr, the claim is immediate. If not, have 31 = TT (x;)) by
the definition of the algorithm and (xx))) nhhh (xx) by the definition of t My. Thus (r(r,, ye) 14t" (2:)) for t & Mr. For L E Mr, Lemma B.2 implies that u1 (x:) [x(,,,,) We) < Let/n, so
R = Σ (pT"(,;) - Me( v:))
tEMr
< Σ Let/r
tEMr
= Le
(1)
Since <
by assumption, we have Le//n I nb /2 and thus (4 vt) 2 p (x.)
L/
2 11
1 /2
p /2 0 for all é [T]. Then by Lemma A.
R
LL!/n
R
(2)
2
Taking the expectation and applying Lemma B.1 to Equations and completes the proof.
20

---

Avoiding Catastrophe in Online Learning by Asking for Help
Definition B.I. Let (K; || |I) be normed vector space and let ō O. Then multiset S K is ô-packing of K if for all
a, b E S. 1|a b1| 6. The ö-packing number of K, denoted MMK, |I Il. 6), is the maximum cardinality of any ô-packing of K.
We only consider the Euclidean distance norm, so we just write MK,, || (1. = ((K 8).
Lemma B.4 (Theorem 14.2 in (Wu, 2020)). If K C R" is convex, bounded, and contains ball with radius 5 > 0, then
3 vol(K)
M(K, 6) s 8m vol(B)
where a unit ball.
Lemma B.5 (Jung's Theorem (Jung, 1901)). If R is compact, then there exists a closed ball with radius at most
diam (S), Mn+1J containing S.
Lemma B.6. Under the conditions of Theorem 5.1, Algorithm satisfies
( T d log (T' 1/E) 3
+ (x)
E [[Q]]
8
Proof. If E Qr, then either hedgeQuery = true or min (
x|| > e//n (or both). The expected
number of time steps with hedgequery true is pf TTf.. Let {1 Qr (n) ||, x
el/n]. We further subdivide Q into Q = (t E Q (x,) # n"' (z,)) and Q2 = ft E Q (x(),) = (x))) Since
Q1 S Mr, Lemma B.I implies that E|[Q1|| E
log 1/))).
Next, fix y E y and let X, = {ar E x x"> y} be the multiset of observed inputs whose mentor action is y. Also let X2 = {z, t E )2) be the multiset of imputs associated with time steps in Q2. Note that [&2| = 1Q2), since X, is a multiset. We claim that X2 n Xy is an e3/" -packing of Xy. Suppose instead that there exists H, x' E N N,, with ||æ - z'll < g//n, WLOG assume I was queried after x' and let t be the time step on which was queried. Since x' E X2, this implies (x', nThh
"=',""(("""" (x))) E St. Also, since x, E X2 we have Te (x(e)) = x"' (1x) = (2²). Therefore
min ("
| x²1l ||,, x'11 S 1/n
which contradicts E Q Thus 82 X2 is an e//n packing Xy,
By Lemma B.5, there exists a ball B1 of radius R diam(x)) / 2(1+1) which contains æ. Let Bg be the ball with the same center Bj but with radius max(R, g1/n). Since X, C x C Bj Bg and X₂ n nx,, is an g1/""packing of Xy. X2 0 X,, is also an e e1/x-packing of Bg. Also, B3 must contain a ball of radius e//",, so Lemma B.4 implies that
182n Xnnx S M(B2,
3" vol( (B2)
vvol(B) (B)
" 3" vol evol(B) (B)
(max(R, R, E e/m)))
n/2
3"
diam(x))
max
2(n + 1)
E
<0 diam(x))
+
(The +1 is necessary for now since diam (a:) could theoretically be zero.) Since X2 S f .TT) S UpeyXy, we have [82] < EyEy 1821 n X,, by the union bound. Therefore
B|Q < ++ E
T
21

---

Avoiding Catastrophe in Online Learning by Asking for Help
T
E
+ E1
E
T E| + E||
E
T
QI
Σ DEY
X2 n
T +0
Te + +1/8)
+ =
E E(diam(x:))
+1)
E
E
yey
T
Fldiam(2:) +1)
V
+0
Telog(T + 1/E)
+ 1 o
+ TT Tolog (T +/E)+ B|diam(x:)*]
0
as required.
Theorem 5.1 follows from Lemmas B.3 and B.6:
Theorem 5.1. Let = 1). Assume nm E where either (1) IT has finite VC dimension and x is a-smooth, or (2)
has finite Littlssone dimension d. Then for any N and e E 7
Pd.
n
Algorithm satisfies
dL Te 1+1/ log(T + +/E))
[
e
0H0
dT.
[ E0
Te 1+1m log(T T + 1/6)
(
T d Te log log +
E E(diam [x)
B[[QT]] E0
8
We then perform some arithmetic to obtain Theorem 5.2:
Theorem 5.2. Let y {0. 1}. Assume Th 11 where either (1) 11 has finite VC dimension d and is a-smooth (2) 11
has finite Littlestone dimension Then for any T N. Algorithm I with = T satisfies
dL Tamts logT)
E [
E
0y4 dL
E E
[
T log
( (
B[[QT] 6
log T [[diam(a)))))
Proof. We have
[ 0
dL T
2n
Ih (log T + loog(T 2n
dT.
T
log
0110
and similarly for E For [[]
E[[Qr] EO
2n + d
mill
2n (1og T + log(T 2a
+ T B[diam(z:)")
22

---

Avoiding Catastrophe in Online Learning by Asking for Help
=0
2. T 2n41
d T log T + T Eldiam(())) (x))
<
T
4n+1 4n=2
d log 7 + E[diam(<)))))
B.3. Adaptive adversaries
If x is allowed to depend on the events of prior time steps, we say that the adversary is adaptive. In contrast, -on-adaptive or "oblivious" adversary must choose the entire input upfront. This distinction is not relevant for deterministic algorithms, since an adversary knows exactly how the algorithm will behave for any input. In other words, the adversary gains no new information during the execution of the algorithm. For randomized algorithms, an adaptive adversary can base the choice of T, on the results of randomization on previous time steps (but not on the current time step), while an oblivious adversary cannot.
In the standard online learning model, Hedge guarantees sublinear regret against both oblivious and adaptive adversaries (Chapter of Slivkins et al. (2019) or Chapter 21 of Shalev-Shwartz & Ben-David (2014)). However, Russo et al. (2024) state their result only for oblivious adversaries. In order for our overall proof of Theorem 5.1 to hold for adaptive adversaries, Lemma 5.4 (Lemma 3.5 in Russo et al., 2024) must also hold for adaptive adversaries. In this section, we argue why the proof of Lemma 5.4 (Lemma 3.5 in their paper) goes through for adaptive adversaries as well. For the rest of Appendix B.3, lemma numbers refer to the numbering in Russo et al. (2024).
The importance of independent queries. Recall from Appendix B.1 that Russo et al. (2024) allow two separate parameters I and k; which unify for simplicity. Recall also that Lemma 3.5 refers to the variant of Hedge which queries with probability p = k/T k/T independently on each time step (Algorithm 2). More precisely, on each time step t, the algorithm samples X, ~ Bernoulli()) and queries if X, 1. The key idea is that X, is independent of events on previous time steps. Thus even conditioning on the history up to time t, for any random variable Yú we can write
B[y] = (1 - p) E[Y X, = 0] + pE | X. =1]
This insight immediately extends Observation 3.3 to adaptive adversaries (with the minor modification that queries now issued independently with probability p on each time step instead of issuing & uniformly distributed queries). Specifically, using the notation from Russo et al. (2024) where is is the action chosen at time i, og is the action chosen at time /. if a query is not issued, and it is the optimal action at time t, we have
[1)) = (1 - p) B(er(12) + p E(4()))
= 1 (1-TT) E(ee(19) + ト B(0((1))
The same logic applies to other statements like E(((() | [g--1] = Ee(1) - -ee()) and immediately extends those statements to adaptive adversaries as well.
The other tricky part of the proof is applying Observation 3.3 using a new loss function i defined by (i) = (4) (xx 1). To do so, we must argue that standard Hedge run on é is the "counterpart Specifically, both algorithms must have the same weight vectors every time
Applying Observation 3.3.
without queries" of HEDGEWITHQUEREE step, and the only difference should be that HEDGEW
takes the optimal action each time step independently with probability (and otherwise behaves the same as standard Hedge). On time steps with X, = -., standard Hedge observes (i) = 0 for all actions i and thus makes no updates, and HEDGEWITHQUERISS makes no updates by definition. On time steps with X, 1, both algorithms perform the typical updates w:+1 (i) = wxx exp( (i) ((t))) Thus the weight vectors are the same for both algorithms on every time step. Furthermore, HEDGE HEDDGEITHQUERISS takes the optimal action at time t iff X,- = 1, which occurs independently with probability p on each time step. Thus standard Hedge run on i the "counterpart without queries" of HEDGEEITHQUERIES, Note that since é is itself a random variable, the law of iterated expectation is necessary to formalize this.
23

---

Avoiding Catastrophe in Online Learning by Asking for Help
Algorithm 3 extends Algorithm many actions.
Inputs: T E I,, E E N, policy class 11
for y E Y do
if y has VC dimension d then
Nl f- any smooth E-cover Ily of size at most (41/e)4
else if Hly has Littlestone dimension d then
II, f- any adversarial cover Lly of size at most (eT/d)d
for t from 1 to T do for E do
by action at time t from the copy of Algorithm running Hl (with the same T, e, d)
if by + ū Vy E y and 3a E 3 : by = then
Take any action y with by =
else
Take an arbitrary action y
The rest of the proof. The other elements of the proof of Lemma 3.5 are as follows:
Lemma 3.1, which analyzes the standard version of Hedge (i.e., no queries and losses are observed on every time step).
2. Applying Lemma 3.1 to f.
Arithmetic and rearranging terms.
The proof of Lemma 3.1 relies simple arithmetic properties of the Hedge weights. Regardless of the adversary's behavior, is well-defined loss function, so Lemma 3.1 can be applied. Step 3 clearly has no dependence on the type of adversary. Thus we conclude that Lemma 3.5 extends to adaptive adversaries.
C. Generalizing Theorem 5.2 to many actions
We use the standard "one versus rest" reduction (see, e-g., Chapter 29 of Shalev-Shwartz Ben-David, 2014). For each action y, will learn binary classifier which predicts whether action y is the mentor's action. Formally, for each y V, define the policy class HI {my there exists policy Ty X + {0, 1} in 11, such that (x) = ((T(x) = y) for all E X.
TI and (x) (xx(x) y) Va E X). In words, for each policy X - y in II,
Algorithm runs one copy of our binary-action algorithm (Algorithm 1) for each action y E y. At each time step f, the copy for action y returns an action by. with Dy = 1 indicating a belief that = x (xx) and by = indicating a belief that y * nM (zz). (Note that by = ÿ also possible, indicating that the mentor was queried.)
The key idea is that if by is correct for each action y, there will be exactly y such that by = and specifically it will be y T"' (xz). Thus are guaranteed to take the mentor's action such time steps. The analysis for Theorem 5.2 (specifically, Lemma B.1) bounds the number of time steps when given copy of Algorithm is incorrect, so by the union bound, the number of time steps where any copy is incorrect is [}] times that bound. That turn bounds the number of time steps where Algorithm 3 takes an action other than the mentor's. Similarly, the number of queries made by Algorithm most | times the bound from Theorem 5.2. The result is the following theorem:
Theorem C.1. Assume Th E II where either (1) Hy has finite VC dimension d and æ is a-smooth or (2) Hl has finite Littlestone dimension d for all y E D. Then for any T N, Algorithm 3 with T satisfies
Dldd 0n
[
E
T log
DDdd T log T
[
e
(DI till (d
E| B[Qr]]
e
log log + [xdiam)())"))
We use the following terminology and notation in the proof of Theorem C.I:
24

---

Avoiding Catastrophe in Online Learning by Asking for Help
1. We refer the copy of Algorithm running Hl as "copy y of Algorithm 1".
2. Recall that St refers to the value of S at the start of time step t in Algorithm 1. Let π. and Sy refer to the values of Te and Se for copy y of Algorithm 1.
Let x" X - {0, 13 be the policy defined by x (2)) (1)"(())= y). Note that querying the mentor tells the agent - (aze), which allows the agent compute "' (xx): this is necessary when Algorithm 1 queries while running on some 11.
4. Let My = (t E [T]: by # (xx)) be the set of time steps where म. does not correctly determine whether the mentor would take action y and let Mr = {t E [T] ye # n" {x+)} } be the set of time steps where the agent's 's action does not match the mentor's.
Lemma C.I. We have |MT & EnEy J
Proof. We claim that MT E My Suppose the opposite: then there exists E Mr such that by (xx) for all
y E V. Since ' (24) )/ there is exactly one y y such that 1 (2:4) y) = >x (24) by = 1. Specifically, this
holds for y = TT (x1). But then Algorithm 3 takes action min(y E y by = 1} -"' (x:)) which contradicts E Mr.
Therefore Mr C My and applying the union bound completes the proof.
Lemma C.2. For all t E [T], (T) (zz) - pe vo) S LE
Proof. The argument is similar to the proof of Lemma B.2. If (1 (xt) + pele,, Mt). then yt = for some y E y where by Therefore copy y of Algorithm did not query at time and np (x+) = Let (x', g/) = arg mig (x)))ssss | Then | ='1l S g²/n and y' = = (xx)
By construction of S.. y' =x²" (x))))) which implies n (x') y. Then by the local generalization
assumption,
pr( = pr( v) = pe( x (2²)) 2 (xx.) L||x; x'1l 2 1r (xx)) - L/
as required.
We now proceed to the proof of Theorem C.I.
Proof of Theorem C.I. Theorem 5.2 implies that each copy of Algorithm makes O tn (g log T + E[diam(())))) queries in expectation. Thus by linearity of expectation the expected number of queries made by Algorithm 3 is O 1n-2 (g log + [[diam(<)"))) Similar to the proof Lemma B.3, we have
R
Σ E(r"" (xx) (1 w:))
= (e ve) for all & Mr)
1EMr
< Σ Let/n
(Lemma C.2)
1EMr
Ls
(Simplifying sum) (Lemma C.1)
< LE
M
Since each copy satisfies the conditions of Lemma B.I, we get
Te log(E)) (1E)) (IE)) = (DVILCT Te Te
E
<
L/
Σo
BEY
Since 1im there exists To such that L/!/n s 1100 12 for all T 2 To. Then by Lemma A.1,
B[Rt]
E (DIIOO
d Telo
E
E
<
p /2
one
Plugging T to the bounds above E[R and E E[R yields the desired bounds (see the arithmetic in the proof of Theorem 5.2 in Appendix B).
This an overestimate because the agent makes at most one query per time step, even if multiple copies request a query.
25

---

Avoiding Catastrophe in Online Learning by Asking for Help
D. There exist policy classes which are learnable in our setting but not in the standard online model
This section presents another algorithm with subconstant regret and sublinear queries, but under different assumptions The primary takeaway here is that our algorithm can handle the class of thresholds on [0, 11, which is known to have infinite Littlestone dimension and thus be hard in the standard online learning model. (Example 21.4 in Shalev-Shwartz & Ben-David, 2014).
ID input space and we allow the input sequence to be fully adversarial chosen. Instead of VC/Littlestone dimension, we consider the following notion of simplicity:
Specifically, we assume a
Definition D.1. Given mentor policy x" partition the imput space X' into intervals such that all imputs within each interval share the same mentor action. Let (X1, {Xi..... X ) be partition that minimizes the number of intervals. We call each X, segment. Let ((T"") denote the number of segments in n.
Bounding the number of segments is similar conceptually to VC dimension in that it limits the ability of the policy class to realize arbitrary combinations of labels (i.e., mentor actions) on For example, if TT is the class of thresholds on [0, 1}, every π. E II has at most two segments, and thus the positive result in this section will apply. This demonstrates the existence of policy classes which are learnable in our setting but not learnable in the standard online learning model, meaning that the two settings do not exactly coincide.
Unlike our primary algorithm (Algorithm 1), this algorithm does require direct access the input encoding. However, the point of this section is not to present practical algorithm: it is simply to demonstrate that our setting and the standard online setting do not exactly coincide.
We prove the following regret bound. Like our previous results, this bound applies to both multiplicative and additive regret.
Theorem D.2. For any E XT, any xh with S(xTM) S K, and any function g N - N satisfying g(T) 2 2L/PD" Algorithm 4 satisfies
4LKT
R < 2
2LKT
R < g(T)²
1Qrl S (diam(x)) + 4)g(T)
Choosing g(T) = T for c E (1/2,1) is sufficient for subconstant regret and sublinear queries:
Theorem D.3. For any c E (1/2, 1), Algorithm with g(T) = T satisfies
R E [LKTI-20
Rt E O (LKT1-20 22)
1Qrl E (diam(x) + 1))
D.1. Intuition behind the algorithm
We call our algorithm "Dynamic Bucketing With Routine Querying", or DBWRQ (pronounced "DBWRQ"). The algorithm maintains a set buckets which partition the observed portion of the input space. Each bucket's length determines the maximum loss in payoff we will allow from that subset of the input space. As long as the bucket contains a query from a prior time step, local generalization allows to bound μ4"" (xx) [ 9t) based on the length of the bucket containing z;. We always query if the bucket does not contain prior query; in this sense the querying is "routine".
The granularity of the buckets is controlled by function g, with the initial buckets having length 1/9(T). Since we can expect one query per bucket, we need g()) E o(T") to ensure sublinear queries.
Regardless of the bucket length, the adversary can still place multiple segments in the same bucket B. A single query only tells us the optimal action for one of those segments, so we risk a payoff as bad as 14,1 (xx) - ((een()) whenever we
26

---

Avoiding Catastrophe in Online Learning by Asking for Help
Algorithm 4 achieves subconstant regret when the mentor's policy has bounded number of segments.
1: function DB E N, g N)
2: XQ t 0 (previously queried inputs)
3: и 0 (records n" (x) for each E XQ)
4: B <+ 0 (The of active buckets)
5: for t from to T do
6: EVALUATEINPUT((2)
7: end for
8: end function
9: function EVALUATHINPUT(Z X)
if x E B for all B
then
11:
B
i-1
for Z such that B
9(T) T
12:
B
13:
BB + 0
14:
EVALUATE(NPUT((2
15:
else
B any bucket containing x
if Xx n B / then
18:
Query mentor and observe n (I)
19:
<xx) +- --->>"<< (x)) XQ - Xq {x}
20:
21:
un < nm +
22:
else ng < <T) then
Let exQ 0 Take action (x')
24:
25:
nn ng
26:
else
27:
B = ba
(Bi, B2) f [aa 2+:
1 6])
28:
29:
( TB,) - (0, 0)
B- (1, B2)
31:
EVALUUTTEINPUUT(T"
32:
end if
33:
end if end function
34:
choose not to query. We can endure a limited number of such payoffs, but if we never query again that bucket, we may suffer (T')) such payoffs. Letting μ4" (2:) for simplicity, that would lead to 112 Pe( B1) S (1 o(a(T))
e())
which converges to 0 (i.e., guaranteed catastrophe) when gT)) E o()).
This failure mode suggests a natural countermeasure: we start suffer significant (potential) losses in the same bucket, then we should probably query there again. One way to structure these supplementary queries by splitting the bucket in half when enough time steps have involved that bucket. It turns that splitting after T/g(T) time steps is sweet spot.
D.2. Proof notation
We will use the following notation throughout the proof Theorem D.2:
1. Let My = (t [T] (1 yt) < f4th (mt)) > be the set of time steps with a suboptimal payoff.
Let B, be the bucket that used on time step t (as defined on line 16 of Algorithm 4).
3. Let d(B) be the depth of bucket B.
(a) Buckets created on line 11 are depth
27

---

Avoiding Catastrophe in Online Learning by Asking for Help
(b) We refer to B1: Bg created line 28 as the children of the bucket B defined on line 16.
(c) If B' is the child of B, d(') d(B)+ +1.
(d) Note that (en ((T)24(8))
4. Viewing the set of buckets binary tree defined by the "child" relation, use the terms "ancestor" and "descendant" in accordance with their standard tree definitions.
5. Let By = {B 3t E Mr s.t. B, = B3 be the set of buckets that ever produced a suboptimal payoff.
6. Let By {B E Bv no descendant of B is in Bv}.
D.3. Proof roadmap
The proof proceeds in the following steps:
1. Bound the total number of buckets and therefore the total number of queries (Lemma D.1).
2. Bound the suboptimality on single time step based on the bucket length and L (Lemma D.2).
3. Bound the sum of bucket lengths on time steps where we make a mistake (Lemma D.4), with Lemma D.3 as an intermediate step. This captures the "total amount of suboptimalit"..
4. Lemma D.5 uses Lemma D.2 and Lemma D.4 to bound the regret.
5. Theorem D.2 directly follows from Lemmas D.I and D.5.
D.4. Proof
Lemma D.I. Algorithm performs at most (diam((=)) 4T) queries.
Proof.
Algorithm 4 performs at most one query per bucket, so the total number of queries is bounded by the total number of buckets. There are two ways to create bucket: from scratch (line I1), or by splitting an existing bucket (line 28).
Since depth buckets overlap only at their boundaries, and each depth bucket has length 1/g(T), at most g(T) re(], [t, 1 zel gT) diam(x) depth 0 buckets are subsets of the interval [min Tt; max 2z]. At most two depth 0 buckets are not subsets of that interval (one each end), the total number of depth 0 buckets is at most (TT) diam(x:) + 2.
We split a bucket B when пy reaches TT)(T), which creates two new buckets. Since each time step increments n for a single bucket B, and there are total of T time steps, the total number of buckets created via splitting is at most 2T T/g(T) (T). Therefore the total number of buckets ever in existence is (diam + (T) + + (diam(z)+ (T))
so Algorithm 4 performs at most (diam( (z) + 4T) queries.
Lemma D.2. For each t E [T), po(e,, vn) 2 p47 (x,) L len
Proof. If we query at time t, then (r v.) = μ.th (Iz). Thus assume we do not query at time t: then there exists E B, (as defined on line 23 of Algorithm 4) such that yt = π (2x))= = (='). Since x, and are both in Br, | - -x'1 S len(B.), Then by local generalization, /4 (1, ve) 14 n"' (x')) 2 1. (xe) L| x'll 2 (x,) - L Len(B.).
Lemma D.3. Th has most K segments, |B < K.
Proof. Now consider any B E By. By definition of By, there exists t E My such that 33 E B. Then there exists E B (as defined in Algorithm 4) such that y/ = <<x') = x' are in different segments, but are both in B. Therefore any B E By must intersect at least two segments. Since B an interval, if intersects two segments, it must intersect two adjacent segments X, and Xj+1. Furthermore, B must contain an open neighborhood centered on the boundary between Xj and Xj+1-
="=')==><<>""" (a'). Since E Mr, we have x= (xx) * yt = T (x'). Thus 2, and
Now consider some B' E By with B # B'. We have |B n B'| < 1: otherwise one must be the descendant of the other, which contradicts the definition of By, Suppose B' also intersects both X, and X,+1: since B' is also an interval, B' must also contain an open neighborhood centered on the boundary between those two segments. But then | n B'| > 1, which is a contradiction.
28

---

Avoiding Catastrophe in Online Learning by Asking for Help
Therefore for any pair of adjacent segments X₃ and X++1, there is most bucket in By which contains open neigh- borhood around their boundary. Since there are most K - pairs of adjacent segments, we have |Byr] K - 1 v K.
2KT
Lemma D.4. We have
Σ len(B:) - 9(T)2*
LEMr
Proof. For every & Mr, we have B, B for some B Bv,
len(B,)
Σ
Σ
len( (B)
ME
BEBv BEMr:B=B.
Next, observe that every B By \ By must have descendant in B otherwise we would have Byy. Let A(B) denote the set of ancestors of B, plus B itself. Then we can write
Σ RE
len(Bi) S Σ
Σ
Σ
(en(Bi)
B'EB, BEA(B")
DE B-M B,
Σ
Σ
lite Mr B = BB len(B,)
B'EB, BEA(B")
For any bucket B, the number of time steps t with B B₁ is at most T/9(T). Also recall that len(B) "(T)24())
Σ
e MT B= B.Hl
T
Σ
1
<
(
(T)
2d(
BEA((B)
BEA(BO)
d(B')
T
Σ
2d
d=0
T
1
(T))²
2d
d=0
2T
g(T)2
Then by Lemma D.3,
Σ len(Bi) <
Σ B'E
2T
BT g(T)²
2KT
<
((T)²
EE Mr
as claimed.
Lemma D.5. Under the conditions of Theorem D.2, Algorithm 4 satisfies
R < 2LKT H ((T)2
2LKT
Rr s g())²
Proof. We have
R
Σ (4. (xt)
pe(a vc))
(44(21, 2 p4," (xx) for t &f My)
M
Σ LlenBB))
(Lemma D.2)
te 2LKT
(Lemma D.4)
g(T)2
29

---

Avoiding Catastrophe in Online Learning by Asking for Help
Since g(T) 2 2L/D8' and every bucket length is most g(T)'
[e( 2 14 (xt) len Ba)
L
2 1000 g(T)
2 16 1D0 /2
2 10 /2
> 0
Invoking Lemma A.I completes the proof:
R7 S 2
ALKT
11
1(T)210
Theorem D.2 follows from Lemma D.1 and Lemma D.5.
E. Properties of local generalization
Proposition E. states that Lipschitz continuity implies local generalization when the mentor is optimal.
Proposition E.1. Assume that μs satisfies Lipschitz continuity: for all x, x' E X and E y, |p(x, u))a''') w)1 S L| Also assume that p(z, nr' (x)) = maxyey p(z, y) for all x E N. Then μ satisfies local generalization with constant 2L.
Proof. For any x. x' E EX, we have
M(x, (T,,""(()) (x')) 2 u(x1, TT (x') - ||| x'
(Lipschitz continuity of j
2 u(x'; nTh (x)) - L x - x'1
(T is optimal for x')
2 u(x, x (x)) - 22|
(Lipschitz continuity of μ again)
n (x) 2L/11 x'1l
(Definition of nm (x))
Since nh is optimal for v, we have
(x) + 2L x z'11 nT (x"(() 2 u(z, TT' (2'))
So 21 x'1l
(x) s 21||r x'1l and therefore |p(a, -=²)))""(>)))) s 2L||x 2/1l.
Theorem E.2 shows that avoiding catastrophe is impossible without local generalization, even when is a-smooth and II has finite VC dimension. The first insight that without local generalization, we can define μıx,, y) 1 n"h (x=) so that a single mistake causes] 11. p(x 3r) = O. To lower bound Pr [I u(xx, M1) = =0] we use a similar approach to the proof of Theorem 4.1: divide X' [0, 1] into f(T) independent sections with |Qrl << f(T) << T, so that the agent can only query a small fraction of these sections. However, the proof of Theorem E.2 is bit easier, since only need the agent make single mistake.
Note that Theorem E.2 as stated only provides bound on Rz. A similar bound can be obtained for R but it is more tedious and we do not believe it would add much to the paper.
Theorem E.2. Let X [0, 1] y = 1). Let each input be sampled i..dd. from the uniform distribution on and define the mentor policy class as the set of intervals within X. i.e., 11 = {m 3a, b E [o, 1] s.t π(x) = 1(x E [a, 6]) Vx E X}. Then without the local generalization assumption, any algorithm with sublinear queries satisfies limy supp,, E E[R oc.
Proof. Part 1: Setup. Consider any algorithm which makes sublinear worst-case queries: then there exists g : N where supp.mm m [[ [[
|| < ((T) and g(T) E o(T). WLOG assume g(T) for all T; if not, redefine g(T) to be max (g("), 1).
Define f(T) = (T by Lemma A.2, (T) E (f())) and f(T) E (T). Divide X' into [T) equally sized sections X1...., XITT) in exactly the same way as in Section 4.2; see also Figure 1. Assume that each 2, is in exactly one section: this assumption holds with probability 1, so does not affect the regret.
30

---

Avoiding Catastrophe in Online Learning by Asking for Help
We use the probabilistic method: sample a segment jrh [S(T) uniformly at random, define n by (>) 1 (ar ymm) and define js by j( v) [yy (x)). In words, the mentor takes action 1 iff the input is in section jM and the agent receives payoff if its action matches the mentor's s and zero otherwise. Since any choice of yth defines valid μu and n""
sup E M.
V. M4,
E R m.
[R
(ar, y,
m²)]
Let J-Q Uj [f(T]] of sections queried by the agent: then k = 1Qrl S (T)).
Vt Qr) be the set of sections which are never queried. Let ji....,, ji be the sequence
Part 2: The agent is unlikely to determine jr By the chain rule of probability.
Prlj E J. = Pr J + vi
II Pr j 1 ド vr <1
Now fix and assume j. * n Vr Queries in sections other than jmH provide no information about the value of jmh so jT is uniformly distributed across the set of sections not yet queried, i.e. {j E [f( : +5 < i}. There are least f(T) -i++ i+ 1 such sections, since there are 1 prior queries at this point. Thus Pr[je j 1 jm Vr < é) 2 7(1)-i+1
((T)
(the inequality is because this probability could also be 1 if j: j. for some i < r). Therefore
Pr pr E J q] 2 II I(T) -i
f(T) -++1
J(T) -1 -( -2 [(T)- J(T) -h
((T) S(T) -1 ( k J(T) -
F(T) -k
S(T)
2 g(T)
S(T)
Part 3: If the agent fails to determine jrH, it likely make at least one mistake. For each j E J-Q, let Vj {t [T] x. {X,} be the set of time steps with inputs in section j. By Lemma A.4, Pr[|V]-| 0] s exp (1ef(r)):
Then by the union bound, Pr[j"" E J-Q and IVr-l > 0] 2 1 jTh E J-Q and Vyml O.
g( J exp (1877))) For the rest of Part 3, assume
Case I: For all j E J-Q and t E Vg, we have y/ = 0. In particular, this holds for j = jm and we know there exists at least one t E Vym since |Vmll
Then y1 # x(x)), so p(r,,3e) = and thus
Pr IT= M(xr: Mr)
jmM E J Q and [Viml > 0 and y = ovj E o, E Vj =1.
Case 2: There exists j E J q and & V, with y 1. Then p( v) 0 unless j jmh
Pr II p(ar, 4r) 0 nmh E J-Q and Vyml > and 3j E J-Q,t V, s.t. y/
2 Pr (u(xe; ve) 0 fm E J and Vym > 0 and 3j Q. 1 E V, s.t. y/ =1
Pr jm jmh E J-Q and Vym > 0 and コj J-q, E Vi s.t. 8/: =
Since jTh E J-Q. the agent has information about jm other than that it is in J-Q. This means that j is uniformly distributed across J-Q.
Pr Il pa vr) 0 jm E J-Q and |Vym| > 0 and 3j E J-q, Vg s.t. Ye
2 1
| 2 1
J(T) - gT))
Combining Case and Case 2, we get the overall bound of
Pr II p( v.) = 0 jr E J-Q and Vym >0 0
>
[(T) (T))
31

---

Avoiding Catastrophe in Online Learning by Asking for Help
and thus
T
p( = 0 and jrH E J Q and Vym= > 0
Pr
p (z,, we) =
2 Pr
Pr
II (1 (1) 0 5T E J-Q and Vin! 0 Pr 1t E J-Q and |Vgm > 0
1 ((T) (1-JM- g(T) (1 g(T)
S(T) exp (6](T)) ))
--
For brevity, let (T) denote this final bound. Since g(T) (f())) and f(T) E ((T), we have
- (1- (-- - 9(T) - (1- 9(T) exp ((T)
-T ( )) (1 (01-0)(11 (1-0))1-0-0) =1
lim a(T) T-000
lim
T +20
Part 4: Putting it all together. Consider any & E (0, 1]; to avoid dealing with infinite expectations, we will deal with
Pr[[I T (( Me)
I e] instead of Pr[[I==1 (( vt) 0j. Since II p(r,, we) < 1 always, we have
T
T p(x, 31) SE E
T
E
log
1 (Te: M1)
=
log
( y1)
II 1=1
Pr
Il
p v1)
SE
5m
2.3/
5 m.
1==1
T (1 vt)
T
T
+ E3 IE
log
II 1=1
p( Me) > E
Pr
(1 yc)
>
t=1
< lloge Pr
II pl Mo) S
+1 1-
1 Pr
II
pr 31)
[=1
$ 1 (1 log=) Pr II pl (c) SE
Since E (0, 1), we have logs 0. Also, Pr[[IT= (( v1) Se) Pr[[I'" 2' ((x1,31). =0].
T
E
E
log
(T M1) 1=1
51-(1-lop loge) Pr
(( Me) Se
mm
< 1 (1 log E) Pr
II pa( Mei = 0
< 1 (1 log (T)
Since Mh=10 (xz) always, have
E. (R y, 14, 9,, ",," a. a.y
sup
E
E.
[R
y, (M, ... .1), m))
jum
2.
log
E
E
log
p( Ut)
ymh
Z.y
2 - 1 - log (T)
Therefore
lim sup E [Rt y, u, 7 ""]] T-00 pm a.y
u,
]]
- + (1 - log 8)
lim (T))
T-00c
- 1 + (1 - log E)
2 - log
This holds for every (0, 1), which only possible if limr- sup
Em.yy [ y, p1, [0 cc, desired.
32


Reviews:
[{"review_id": "vColdoIBs4", "reviewer": "Reviewer_M11a", "summary": "This work introduces an online learning framework that avoids catastrophic mistakes by allowing an agent to query a mentor when uncertain, rather than relying solely on trial-and-error. The approach maximizes the product of payoffs, where each payoff represents the chance of avoiding catastrophe, and leverages local generalization to apply knowledge from similar inputs. The authors prove that without mentor assistance, any algorithm with sublinear queries incurs high regret, but with help, one can achieve subconstant regret and a sublinear query rate under standard learnability assumptions (finite VC or Littlestone dimensions). Their results offer theoretical guarantees for safe online learning in high-stakes scenarios where irreversible errors must be avoided.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review.\n> Page 4: \"Also, that work\" ---> Also, their work\n\nWe appreciate the correction and will make this change.\n\n> 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?\n\nThis 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.", "claims_and_evidence": "Yes the claims made in this work are supposed by clear and convincing evidence, as detailed in section 1.4.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I briefly checked the correctness of Theorem 4.1.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper extends classical online learning frameworks, which typically assume that all errors are recoverable by leveraging concepts like finite VC/Littlestone dimensions and algorithms such as Hedge, by incorporating a mentor query mechanism and local generalization to safely handle irreversible, catastrophic mistakes.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "Page 4: \"Also, that work\" ---> Also, their work", "questions_for_authors": "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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r7iy4JFCsK", "reviewer": "Reviewer_MoC3", "summary": "The paper studies how to design learning algorithms that avoid catastrophe. In particular, the goal of the learner is to minimize the chance of a catastrophe. This is modeled as an online learning problem in which the learner aims at minimizing the product of the payoffs. The learner is equipped with a mentor that can be queried to obtain the best action for the current round. The problem is in general unlearnable since any algorithm queries the mentor a linear number of times or guarantee to cause catastrophe with high probability. The authors show that when the policy class is learnable, it is possible to design a learning algorithm that queries the mentor a sublinear number of times and whose regret approaches $0$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. We respond to each of the reviewer’s concerns:\n\n**Concern 1**\n> 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.\n\nWe 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.\n\n**Concern 2**\n> 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.\n\nWe do agree that technical novelty is not our primary contribution. However, we offer some mild pushback:\n\n1. 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.\n\n2. 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. \n\n     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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Not Applicable.", "theoretical_claims": "I only checked the main paper.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The paper introduces a  new model. However, it borrows some techniques used for other online learning problems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper introduces a new problem, and the problem of avoiding catastrophe is well-motivated. 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.\n\nFrom  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.", "other_comments_or_suggestions": "None.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M9EKkNPI2L", "reviewer": "Reviewer_7tdC", "summary": "This paper formula the events of catastrophe as product of payoff functions where each payoff function can be seen as the probability of catastrophe occurs at each time step. Apart from the multiplicative objective in different to standard regret in online learning, the agent observes feedback only when asking for help from a mentor. The goal is to maximize product of pay off against mentor's performance while maintaining non-trivial query numbers.\n\nThis paper first establishes a worst-case impossibility result, showing that an agent cannot avoid catastrophe with sublinear mentor queries, even when the mentor follows a safe policy. For the case where catastrophe avoidance is possible, the paper identifies a connection to Littlestone and VC dimensions and leverages a variant of Hedge [Russo et al. (2024)], which enables achieving sublinear regret with sublinear queries.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. We believe the reviewer articulates only a single weakness:\n> 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\n\nWe agree that this is a weakness of our current algorithm. We offer two responses:\n1. 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.\n2. 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.\n\nWe would also like to clarify the regret bound. The reviewer writes:\n> ...which enables achieving sublinear regret with sublinear queries.\n\nHowever, our algorithm achieves **subconstant** regret with sublinear queries.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "the metric is analogous to regret in online learning with the mentor's performance as the comparitor, which makes sense.", "theoretical_claims": "Checked Theorem 4.1", "experimental_designs_or_analyses": "not applicable", "relation_to_broader_scientific_literature": "the first provable algorithm in learning with irreversible costs without bayesian inference", "essential_references_not_discussed": "well referenced.", "other_strengths_and_weaknesses": "Strength: \n- The paper does well in motivating the considered problem, the sensible formulation and iterative feedback set-up, and drawing differences of the novel formulation in comparison to standard online learning, thus it was clear that the formulation itself is not a trivial problem.\n- The result of this paper is considered as complete as it gives negative case and solvable cases\n\nWeakness: 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", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SVOYCG9yXM", "reviewer": "Reviewer_Ddiy", "summary": "The paper addresses a novel problem of avoiding catastrophe in online learning with the help of a mentor policy. Specifically, for each input and action, there is a probability of catastrophe. The objective is to minimize the probability of catastrophe over T rounds of play while keeping the number of queries to the mentor relatively low. The mentor policy is assumed to either belong to a class with finite VC dimension and the input distribution is \"smooth\"; or to have finite Littlestone dimension. Additionally, the authors assume some kind of Lipschitz continuity in the mentor's policy, which they refer to as \"local generalization.\"\n\nThe authors propose an algorithm with **sub-constant** regret and sub-linear queries to the mentor. The algorithm discretizes the policy class and, at a high level, queries the mentor with a fixed probability while running the Hedge algorithm on the discretized policy set over queried rounds. Furthermore, if an input is too far from a previously queried input, the algorithm also queries the mentor. The local generalization essentially ensures that if the input is close to an already queried input, the mentor's action will be approximately the same.\n\n## Post Rebuttal\nOverall, my assessment remains unchanged: I still find it odd that the regret compared to the mentor becomes somewhat vacuous unless the mentor avoids catastrophe with a probability close to 1. Additionally, I suggest the authors include a more detailed discussion regarding their packing argument, specifically addressing why current tools fail and how their approach overcomes these challenges. Currently, this aspect is quite vague, both in the main text and in their rebuttal.\n\nI will keep my score unchanged.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. We respond to each concern and question:\n\n**Concern 1**\n> 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.\n\nTo 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.\n\nWe also mention that our subconstant bound on standard additive regret (Theorem 5.3) is unaffected by this issue entirely.\n\n**Concern 2**\n> The local generalization assumption is not a standard one and is not adequately justified in the paper.\n\nWe agree on the importance of justifying assumptions and will expand this justification when revising. \n\nTo recap, local generalization states that\n$|\\mu_t^m(x) - \\mu_t(x, \\pi^m(x'))| \\le L  ||x-x'||$ for any $x,x’$. We make the following claims:\n\nA. 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).\n\nB. Local generalization captures the idea of Claim A. Specifically,\n\nB1. $\\mu_t^m(x)$ is the effect of taking the right action for the current input $x$ \n\nB2. $\\mu_t(x, \\pi^m(x'))$ is the effect of using what you learned in $x’$ for the current input $x$\n\nB3. $||x-x'||$ captures the similarity between $x$ and $x’$\n\nTo 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.\n\n**Concern 3**\n> ​​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.\n\nTo 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. \n\nIn 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.\n\n**Question 1**\n> In line 229, what do you mean by feature embedding? Isn't $x$ already the \"state\" embedding?\n\nYes, 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.\n\n**Question 2**\n> 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?\n\nThose 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.\n\n**Question 3**\n> Is there a specific policy class for which you can make the algorithm efficient (not exponential in $d$)? \n\nIn 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.\n\nHowever, 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.\n\n**Question 4**\n> 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?\n\nThis is simply a typo. We apologize for the confusion.", "claims_and_evidence": "I did not find problematic claims; the analysis combines a few known techniques, and the analysis overview in the main text made sense to me.", "methods_and_evaluation_criteria": "Overall, the evaluation criteria is not standard, but this is part of the paper's novelty. The requirement that the number of queries (or that the querying rate vanishes with $T$) makes perfect sense, as this essentially means that the algorithm becomes self-sufficient over time.\n\nThe multiplicative objective that quantifies the overall probability of avoiding catastrophe also makes sense to me.\n\nThe 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. I understand the authors' discussion regarding that in principle, but more technically, it implies that $\\mu_t(x_t,\\pi^m) \\to 1$, but $\\pi^m$ is fixed, so it kind of assumes that the $x$'s are such that the mentor's policy avoids catastrophe with a probability that becomes arbitrarily close to 1. If the mentor's policy were not fixed, it would make more sense.", "theoretical_claims": "I did not verify the appendix's proofs, but as mentioned, the analysis overview in the main text made sense to me.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "This is somewhat related in motivation to safety in online learning (say, in constrained MDPs), and also somewhat related to imitation learning, as here the algorithm learns by querying the mentor. In a sense, it combines motivation from these two lines of work, as in safety there is no component of requiring a mentor, and in imitation, there is no explicit safety requirement.", "essential_references_not_discussed": "Not that I'm aware of.", "other_strengths_and_weaknesses": "Overall, the paper is well-written and easy to follow.\n\nThe local generalization assumption is not a standard one and is not adequately justified in the paper.\n\nThe analysis mainly combines known techniques, which I find okay in this case since the setting is novel and well-motivated. Properly combining known techniques to solve a new problem is definitely not a trivial task. 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.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "In line 229, what do you mean by feature embedding? Isn't $x$ already the \"state\" embedding?\n\nIt 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?\n\nIs there a specific policy class for which you can make the algorithm efficient (not exponential in $d$)?\n\nIs 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?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: We thank the authors for their submission.
Some reviewers mentioned limited novelty compared to previous works. Others had reservations on the formulation itself and the fact the mentor can always avoid catastrophe.
That said, the reviewers did appreciate the overall formulation of the problem and the results therein.
Decision: Accept (poster)