Avoiding Catastrophe in Online Learning by Asking for Help

## Abstract

Abstract Most learning algorithms with formal regret guarantees assume that no mistake is irreparable 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 that round and aim to maximize the product of payoffs (the overall chance of avoiding catastrophe) while allowing a limited number of queries to a mentor. We first show that in general, any algorithm either constantly queries the mentor or is nearly guaranteed to cause catastrophe. However, in settings where the mentor policy class is learnable in the standard online learning model, we provide an algorithm whose regret and rate of querying the mentor both approach 0 as the time horizon grows. 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.

## 1 Introduction

There has been mounting concern over catastrophic risk from AI, including but not limited to autonomous weapon accidents [], bioterrorism [], and cyberattacks on critical infrastructure []. See [] and [] for taxonomies of societal-scale AI risks. In this paper, we use “catastrophe” to refer to any kind of irreparable harm. This definition also covers smaller-scale (yet still unacceptable) incidents such as serious medical errors [], crashing a robotic vehicle [], or discriminatory sentencing [].

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 no single mistake is too costly. We focus on *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, trial-and-error-style algorithms only work when catastrophe is assumed to be impossible. This assumption manifests differently in different subtypes of online learning. In the standard online learning model, the agent’s actions have no permanent effect on the environment.(^1^11More precisely, the state can depend on the agent’s previous actions, but the agent’s performance is always evaluated with respect to the optimal policy on the same sequence of states.) Online reinforcement learning allows the agent’s actions to permanently affect the environment, but typically assumes that either no action has irreversible effects (e.g., []) or that the agent is reset at the start of each “episode” (e.g., []). One could train an agent entirely in a controlled lab setting where the above assumptions do 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 unfamiliar environments (see, e.g., []), and we do not want AI biologists or robotic vehicles to behave unpredictably.

The goal of this paper is to understand the conditions under which it is possible to formally guarantee avoidance of catastrophe in online learning. Certainly some conditions are necessary, because if the agent can only learn by trying actions directly, the problem is hopeless: any untried action could lead to paradise or disaster and the agent has no way to predict which. In the real world, however, one needn’t learn through pure trial-and-error: one can also ask for help.

### 1.1 Our model

We propose an online learning model of avoiding catastrophe with mentor help. On each time step, the agent observes a state, selects an action (or queries the mentor), and obtains a payoff.(^2^22Depending on the field, states are also known as inputs, instances, or contexts, actions are also known as outputs, labels, or arms, and payoffs are also known as rewards or losses.) Each payoff represents the probability of avoiding catastrophe on that time step, and the agent’s goal is to maximize the *product* of payoffs, which corresponds to minimizing the total chance of catastrophe. We consider the product of payoffs obtained while learning, not the product of payoffs of some final policy: finding a catastrophe-avoiding policy is futile if catastrophe occurs while learning.

The (possibly suboptimal) mentor has a fixed policy, and when queried, the mentor illustrates their policy’s action in the current state. We desire an agent whose regret – defined as the gap between the mentor’s performance and the agent’s performance – approaches zero as the time horizon $T$ grows. In other words, with enough time, the agent should avoid catastrophe nearly as well as the mentor. We also expect the agent to become self-sufficient over time: formally, the number of queries to the mentor should be sublinear in $T$, or equivalently, the rate of querying the mentor should go to zero.

### 1.2 Our assumptions

The agent needs some way to make inferences about unseen states in order to decide when to ask for help. Much past work has used Bayesian inference, which suffers tractability issues in complex environments.(^3^33For the curious reader, [] provides a thorough treatment. See also Section 2.) In this paper, we instead assume that the mentor policy satisfies a Lipschitz-flavored condition we call “local generalization”: informally, if the mentor told us that action $a$ was safe in a nearby state, then $a$ is probably (but not certainly) also safe in the current state. Local generalization captures the intuition that one can transfer knowledge between similar states but the generalization becomes progressively less reliable as the states become less similar. Unlike Bayesian inference, local generalization only requires computing distances and is compatible with any state space which admits a distance metric.

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 catastrophe on that time step. In the real world, one only observes whether catastrophe occurred, not its probability.(^4^44One may be able to detect “close calls” in some cases, but observing the precise probability seems unrealistic.)

### 1.3 Standard online learning

An overview of standard online learning is in order before discussing our results. In the standard model, the agent observes a state on each time step and must choose an action. An adversary then reveals the correct action, which results in some payoff for the agent. The goal is sublinear regret, i.e., the average regret per time step should go to 0 as $T\to\infty$. Figure 1 delineates the precise differences between the standard model and our model.

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 [], or (2) the hypothesis class has finite VC dimension [] and the input is *$\sigma$-smooth*(^5^55Informally, the adversarial chooses a distribution over states instead of a precise state. See Section 3.) [].

The goal of sublinear regret in online learning implicitly assumes catastrophe is impossible: the agent can make arbitrarily many (and arbitrarily costly) mistakes as long as the *average* regret per time step goes to 0. In contrast, we demand subconstant regret: the *total* probability of catastrophe should go to 0. Furthermore, standard online learning allows the agent to observe payoffs on every time step, while our agent only receives feedback on time steps with queries. However, access to a mentor (and local generalization) allows our agent to learn without trying actions directly, which is enough to offset all of the above disadvantages.

Figure: Figure 1: Comparison between the standard online learning model and our model. On a technical level, sublinear vs subconstant regret is a more important distinction than the sum vs product of payoffs: for example, taking a logarithm can transform the product into a sum. However, the multiplicative objective and the goal of subconstant regret are tightly related, since the former’s interpretation as the chance of catastrophe is what gives rise to the latter: we want the total (not average) chance of catastrophe to go to 0.

### 1.4 Our results

Informally, we show that avoiding catastrophe with the help of a mentor and local generalization is no harder than online learning without catastrophic risk.

More precisely, we first show that in general, any algorithm with sublinear queries to the mentor has arbitrarily poor regret in the worst-case (Theorem 4.1). As a corollary, even when it is possible to avoid catastrophe with certainty, any algorithm either asks for help on a constant fraction of time steps or is nearly guaranteed to cause catastrophe. Unlike online learning where the general impossibility result is trivial (the agent might as well guess randomly given an unconstrained adversary), local generalization significantly limits the adversary’s power and necessitates a careful construction.

Next, we present a simple algorithm whose total regret and rate of querying the mentor both go to 0 as $T\to\infty$ when either (1) the mentor policy class has finite Littlestone dimension or (2) the mentor policy class has finite VC dimension and the state sequence is $\sigma$-smooth. Our algorithm can handle a multi-dimensional unbounded state space and does not need detailed access to the feature embedding, instead using two simple operations. It does need to know the mentor policy class, as is standard in online learning. We initially prove the theorem for binary actions (Theorem 5.2) and then reduce learning with (finitely) many actions to the binary action case (Theorem C.1).

Finally, Appendix D presents another algorithm with the same guarantees of subconstant regret and sublinear queries under different assumptions. Most importantly, this result applies to the class of thresholds on $[0,1]$, which is known to be hard for standard online learning (see Section 2). This shows that our problem and standard online learning do not have exactly the same difficulty, but rather our problem is no harder than online learning.

The rest of the paper is structured as follows. Section 2 discusses related work. Section 3 formally defines our model. Section 4 presents our negative result for general mentor policies. Section 5 presents our positive result for simple mentor policy classes. Proofs are deferred to the appendix.

## 2 Related work

#### Learning with irreversible costs.

Despite the ubiquity of irreparable/irreversible 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 states or actions without actually trying them.

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 solution 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 environments satisfies both conditions, but is unrealistic in many real-world scenarios. In contrast, our algorithm can handle an uncountable policy class and a continuous unbounded state space, which is crucial for many real-world scenarios in which one never sees the exact same state twice.

Bayesian inference combined with asking for help is studied by [; ; ; ]. We also mention [; ; ], which utilize Bayesian inference in the context of safe (online) reinforcement learning without asking for help (and without regret bounds).

We are only aware of two papers which theoretically address irreversibility without Bayesian inference: [] and []. The former proposes to sample trajectories and learn reversibility based on temporal consistency between states: intuitively, if $s_{1}$ always precedes $s_{2}$, we can infer that $s_{1}$ is unreachable from $s_{2}$. 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 dependence on the $\gamma^{*}$ parameter which roughly captures how bad an irreversible action can be. In contrast, our algorithm achieves good regret even when actions are maximally bad.

To our knowledge, we are the first to provide an algorithm which formally guarantees avoidance of catastrophe (with high probability) without Bayesian inference.

#### Online learning.

See [] and Chapter 21 of [] for introductions to online learning. A classical result states that sublinear regret is possible iff the hypothesis class has finite Littlestone dimension []. However, even some simple hypothesis classes have infinite Littlestone dimension, such as the class of thresholds on $[0,1]$ (Example 21.4 in []). Recently, [] showed that if the adversary only chooses a distribution over states rather than the precise state, only the weaker assumption of finite VC dimension [] is needed for sublinear regret. Specifically, they assume that each state is sampled from a distribution whose concentration is upper bounded by $\frac{1}{\sigma}$ times the uniform distribution. This framework is known as *smoothed analysis*.

#### Smoothed analysis.

Smoothed analysis was originally proposed by [] to explain the fact that some algorithms almost always perform well in practice, despite the theoretical existence of pathological inputs. Informally, algorithms which perform well under smoothed analysis are guaranteed to perform well for nearly all – but not necessarily all – inputs.

#### Active learning.

Our assumption that the agent only receives feedback in response to queries falls under the umbrella of active learning []. This contrasts with passive learning, where the agent receives feedback automatically. Although ideas from active learning could be useful in our domain, we are not aware of any results from that literature which account for irreversible costs.

#### Multiplicative objectives.

Perhaps the best-studied example of a multiplicative objective is the Nash welfare function (also known as the Nash bargaining solution), defined as the geometric mean of agent utilities [; ]. Inspired by Nash welfare, [] recently studied algorithms for maximizing the geometric mean of payoffs across time steps in the multi-armed bandit problem. However, the geometric mean of payoffs is much more forgiving of errors compared to the product of payoffs. Imagine that the agent obtains a payoff of $1-1/\sqrt{T}$ per time step: then $\lim_{T\to\infty}(1-1/\sqrt{T})^{T}=0$ but $\lim_{T\to\infty}((1-1/\sqrt{T})^{T})^{1/T}=\lim_{T\to\infty}(1-1/\sqrt{T})=1$. In our setting, it is crucial that the *total* chance of catastrophe (the product of payoffs) is small, not just the *average* chance of catastrophe per time step (the geometric mean of payoffs). This is closely related to the difference between sublinear and subconstant regret discussed in Section 1.3.

## 3 Model

#### States.

Let $\mathbb{N}$ refer to the set of strictly positive integers and let $T\in\mathbb{N}$ be the time horizon. Let $S\subseteq\mathbb{R}^{n}$ be the state space and let $\mathbf{s}=(s_{1},s_{2},\dots s_{T})\in S^{T}$ be the sequence of states. In the adversarial setting, each $s_{t}$ can have arbitrary dependence on the events of prior time steps. In the smoothed setting, the adversary only chooses the distribution $s_{t}$ from which $s_{t}$ is sampled. Formally, a distribution $\mathcal{D}$ over $S$ is $\sigma$-smooth if for any $X\subseteq S$, $\mathcal{D}(X)\leq\frac{1}{\sigma}U(X)$. (In the smoothed setting, we assume that $S$ supports a uniform distribution $U$.(^6^66For example, $S$ having finite Lebesgue measure is sufficient. Note that this does not imply boundedness. Alternatively, $\sigma$-smoothness can be defined with respect to a different distribution, as long as the Radon-Nikodym derivative is uniformly bounded; see Definition 1 of [].)) If each $s_{t}$ is sampled from a $\sigma$-smooth $\mathcal{D}_{t}$, we say that $\mathbf{s}$ is $\sigma$-smooth. The sequence $\boldsymbol{\mathcal{D}}=\mathcal{D}_{1},\dots,\mathcal{D}_{T}$ can still be adaptive, i.e., the choice of $\mathcal{D}_{t}$ can depend on the events of prior time steps.

#### Actions.

Let $A$ be a finite set of actions. There also exists a special action $\hat{a}$ which corresponds to querying the mentor. For $k\in\mathbb{N}$, let $[k]=\{1,2,\dots,k\}$. On each time step $t\in[T]$, the agent must select an action $a_{t}\in\ A\cup\{\hat{a}\}$, which generates payoff $\mu(s_{t},a_{t})\in[0,1]$.

#### Asking for help.

The mentor is endowed with a (not necessarily optimal) policy $\pi^{m}:S\to A$. When action $\hat{a}$ is chosen, the mentor informs the agent of the action $\pi^{m}(s_{t})$ and the agent obtains payoff $\mu(s_{t},\pi^{m}(s_{t}))$. For brevity, let $\mu^{m}(s)=\mu(s,\pi^{m}(s))$. The agent never observes payoffs: the only way to learn about $\mu$ 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 0 as $T\to\infty$. Intuitively, this is equivalent to the cumulative number of queries being sublinear in $T$: $|Q_{T}|\in o(T)$, where $Q_{T}=\{t\in[T]:a_{t}=\hat{a}\}$. However, interpreted literally, $|Q_{T}|\in o(T)$ is not a rigorous statement. This is because $|Q_{T}|$ is not just a function of $T$: it can also depend on $\mathbf{s}$, $\mu$, $\pi^{m}$, and any randomness in the agent’s actions.

To formalize this, let $Q_{T}(\mathbf{s},\mu,\pi^{m})$ be the set of time steps with queries given $\mathbf{s},\mu$, and $\pi^{m}$. Then we say that $|Q_{T}|$ is sublinear in $T$, denoted $|Q_{T}|\in o(T)$, if there exists $g:\mathbb{N}\to\mathbb{N}$ such that $g(T)\in o(T)$ and $|Q_{T}(\mathbf{s},\mu,\pi^{m})|\leq g(T)$ for all $\mathbf{s},\mu,\pi^{m}$ (and for all possible realizations of the agent’s randomization). However, we will mostly write $Q_{T}$ and $|Q_{T}|\in o(T)$ for brevity.

#### Local generalization.

We assume that the mentor policy permits “local generalization”. Formally, we assume there exists $L>0$ such that for all $s,s^{\prime}\in S$, $|\mu^{m}(s)-\mu(s,\pi^{m}(s^{\prime}))|\leq L||s-s^{\prime}||$, where $||\cdot||$ denotes Euclidean distance. Informally, if the agent is in state $s$, taking the mentor action from a nearby state $s^{\prime}$ is almost as good as taking the mentor action for $s$. In other words, it’s okay to use an action you learned from a nearby state.

This assumption might initially feel less intuitive than a standard Lipschitz continuity assumption of $|\mu(s,a)-\mu(s^{\prime},a)|\leq L||s-s^{\prime}||$. However, Lipschitz continuity is strictly stronger than local generalization when the mentor is optimal (Proposition E.1). The properties are incomparable in general, but Lipschitz continuity allows odd situations where the mentor provides an action which is only acceptable in that specific state. This sets the agent up for failure: even if such actions exist, a thoughtful mentor should avoid those actions when possible. See Figure 2 for an illustration.

Figure: Figure 2: The difference between local generalization and Lipschitz continuity. The x-axis corresponds to a one-dimensional state space, with $s_{1}$ and $s_{2}$ denoting two nearby states. The y-axis is the payoff. In all figures, $\pi^{m}(s_{1})=0$ and $\pi^{m}(s_{2})=1$. Left: What one might consider the “typical case” with a near-optimal mentor. The mentor takes action 0 in $s_{1}$, so $|\mu(s_{2},0)-\mu(s_{2},\pi^{m}(s_{2})|$ is small (local generalization) and $|\mu(s_{2},0)-\mu(s_{1},0)|$ is small (Lipschitz continiuty). Middle: Local generalization without Lipschitz continuity. Action 0 is much worse in $s_{2}$, but it is still nearly as good as the mentor’s action in $s_{2}$, which is also quite bad. We primarily care about the agent’s performance relative to the mentor. Right: Lipschitz continuity without local generalization. The payoff of each action is similar in nearby states. However, despite the mentor recommending action 0 in $s_{1}$, action 0 is much worse than the mentor’s action in $s_{2}$. The mentor is setting up the agent for failure by recommending action 0 in $s_{1}$.

#### Multiplicative objective and regret.

If $\mu(s_{t},a_{t})\in[0,1]$ is the chance of avoiding catastrophe on time step $t$ (conditioned on no prior catastrophe), then $\prod_{t=1}^{T}\mu(s_{t},a_{t})$ is the agent’s overall chance of avoiding catastrophe.(^7^77Conditioning 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 to the chain rule of probability.) For a fixed state sequence $\mathbf{s}$ and agent actions $\mathbf{a}=(a_{1},\dots,a_{T})$, the agent’s *regret* is

$$ $R_{T}(\mathbf{s},\mathbf{a},\mu,\pi^{m})=\prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{ t=1}^{T}\mu(s_{t},a_{t})$ $$

We will usually write $R_{T}=R_{T}(\mathbf{s},\mathbf{a},\mu,\pi^{m})$ for brevity. We will study the expected regret over any randomness in $\mathbf{s}$ and/or $\mathbf{a}$. We desire subconstant worst-case regret: the total (not average) expected regret should go to 0 for any $\mu$ and $\pi^{m}$. Formally, we want $\lim_{T\to\infty}\sup_{\mu,\pi^{m}}\operatorname*{\mathbb{E}}[R_{T}]=0$.

#### VC and Littlestone dimensions.

VC dimension [] and Littlestone dimension [] 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 dimensions since we only utilize these concept via existing results. See [] for a comprehensive overview.

#### Misc.

The diameter of $X\subseteq S$ is defined by $\operatorname*{diam}(X)=\max_{x,y\in X}||x-y||$. All logarithms and exponents are base $e$ unless otherwise noted.

## 4 Avoiding catastrophe is impossible in general

We begin by showing that in general, any algorithm with sublinear mentor queries has arbitrary poor regret in the worst-case, even when states are i.i.d. on $[0,1]$. The result also holds even if the algorithm knows $L$ and $\mathbf{s}$ ahead of time. We use $\operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\mathbf{a}}$ denote the expectation over both $\mathbf{s}$ and any additional randomness in the algorithm.

###### Theorem 4.1 .

The worst-case expected regret of any algorithm with sublinear queries goes to 1 as $T$ goes to infinity. Formally, $\lim_{T\to\infty}\ \,\sup_{\mu,\pi^{m}}\ \,\operatorname*{\mathbb{E}}_{\mathbf
{s}\sim U^{T},\mathbf{a}}\ \,[R_{T}]=1$.

###### Theorem 4.1 .

### 4.1 Intuition

We partition $S$ into equally-sized sections that are “independent” in the sense that querying a state in section $i$ gives you no information about section $j$. The number of sections is determined by a function $f:\mathbb{N}\to\mathbb{N}$ that we will choose. If $|Q_{T}|\in o(f(T))$, most of these sections will never contain a query. When the agent sees a state in a section not containing a query, it essentially has to guess, meaning it will be wrong a constant fraction of the time. Figure 3 fleshes out this idea.

Figure: Figure 3: An illustration of the construction we use to prove Theorem 4.1 (not to scale). The horizontal axis indicates the state $s\in[0,1]$ and the vertical axis indicates the payoff $\mu(s,a)\in[0,1]$. The solid line represents $\mu(s,0)$ and the dotted line represents $\mu(s,1)$. In each section, one of the actions has the optimal payoff of 1, and the other action has the worst possible payoff allowed by $L$, reaching a minimum of $1-\frac{L}{2f(T)}$. Crucially, both actions result in a payoff of 1 at the boundaries between sections: this allows us to “reset” for the next section. As a result, we can freely toggle the optimal action for each section independently.

#### Picking 𝒇 ⁢ ( 𝑻 ) 𝒇 𝑻 \boldsymbol{f(T)} bold_italic_f bold_( bold_italic_T bold_) .

A natural idea is to try $f(T)=T$, but this doesn’t quite work: even if the agent chooses wrong on every time step, the minimum payoff is still at least $1-\frac{L}{2T}$, and $\lim_{T\to\infty}\prod_{t=1}^{T}\left(1-\frac{L}{2T}\right)=\lim_{T\to\infty}
\left(1-\frac{L}{2T}\right)^{T}=e^{-L/2}$. In order for the regret to approach 1, we need $f(T)$ to be asymptotically between $|Q_{T}|$ and $T$ (such $f$ must exist since $|Q_{T}|\leq g(T)\in o(T)$). This leads to the following bound: $\prod_{t=1}^{T}\mu(s_{t},a_{t})\leq\big{(}1-\frac{L}{\Theta(f(T))}\big{)}^{
\Theta(T)}$. When $f(T)\in o(T)$, the right hand side converges to 0, while $\prod_{t=1}^{T}\mu^{m}(s_{t})=1$. In words, the agent is nearly guaranteed to cause catastrophe, despite the existence of a policy which is guaranteed to avoid catastrophe.

#### VC dimension.

The class of mentor policies induced by our construction has VC dimension $f(T)$; considered over all possible values of $T$, this implies infinite VC (and Littlestone) dimension. This is necessary given our positive results in Section 5.

### 4.2 Formal definition of construction

Let $S=[0,1]$ and $\mathcal{D}_{t}=U$ for each $t\in[T]$. Assume that $L\leq 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:\mathbb{N}\to\mathbb{N}$ and a bit string $\mathbf{x}=(x_{1},x_{2},\dots,x_{f(T)})\in\{0,1\}^{f(T)}$. The bit $x_{j}$ will denote the optimal action in section $j$. Note that $f(T)\geq 1$ and since we defined $\mathbb{N}$ to exclude 0.

For each $j\in[f(T)]$, we refer to $S_{j}=\left[\mfrac{j-1}{f(T)},\mfrac{j}{f(T)}\right]$ as the $j$th section. Let $m_{j}=\mfrac{j-0.5}{f(T)}$ be the midpoint of $S_{j}$. Assume that each $s_{t}$ belongs to exactly one $S_{j}$ (this happens with probability 1, so this assumption does affect the expected regret). Let $j(s)$ denote the index of the section containing state $s$. Then $\mu_{f,\mathbf{x}}$ is defined by

$$ $\mu_{f,\mathbf{x}}(s,a)=\begin{cases}1&\textnormal{ if }a=x_{j(s)}\\ 1-L\left(\cfrac{1}{2f(T)}-|m_{j(s)}-s|\right)&\textnormal{ if }a\neq x_{j(s)} \\ \end{cases}$ $$

Let $\pi^{m}$ be any policy which is optimal for $\mu_{f,\mathbf{x}}$. Note
that there is a unique optimal action for each $s_{t}$, since each $s_{t}$ belongs to exactly one $S_{j}$; formally, $\pi^{m}(s_{t})=x_{j(s_{t})}$.

For any $\mathbf{x}\in\{0,1\}^{f(T)}$, $\mu_{f,\mathbf{x}}$ is piecewise linear (trivially) and continuous (because both actions have payoff 1 on the boundary between sections). Since the slope of each piece is in $\{-L,0,L\}$, $\mu_{f,\mathbf{x}}$ is Lipschitz continuous. Thus by Proposition E.1, $\pi^{m}$ satisfies local generalization.

## 5 Avoiding catastrophe given finite VC or Littlestone dimension

Theorem 4.1 shows that avoiding catastrophe is impossible in general, which is also true in online learning. What if we restrict ourselves to settings where standard online learning is possible? Specifically, we assume that $\pi^{m}$ belongs to a policy class $\Pi$ where either (1) $\Pi$ has finite VC dimension $d$ and $\mathbf{s}$ is $\sigma$-smooth or (2) $\Pi$ has finite Littlestone dimension $d$.(^8^88Recall from Section 1.3 that standard online learning becomes tractable under either of these assumptions.)

This section presents a simple algorithm which guarantees subconstant regret and sublinear queries under either of those assumptions. Our algorithm needs to know $\Pi$, as is standard in online learning. The algorithm does not need to know $\sigma$ (in the smooth case) or $L$, and can handle an unbounded state space (the number of queries simply scales with the maximum distance between observed states). For simplicity, we initially prove our result for $A=\{0,1\}$. Appendix C extends our result to many actions using the“one versus rest” reduction.(^9^99For each action $a$, we learn a binary classifier which predicts whether $\pi^{m}(s)=a$. If every binary classifier is correct, we can correctly determine $\pi^{m}(s)$. See, e.g., Chapter 29 of [].)

### 5.1 Intuition behind the algorithm

Algorithm 1 has two simple components: (1) run a modified version of the Hedge algorithm for online learning, but (2) ask for help in unfamiliar states (specifically, when the current state is far from any queried state with the same action under the proposed policy). Hedge ensures that the number of time steps where the agent’s action doesn’t match the mentor’s is small, and asking for help in unfamiliar states ensures that when we do make a mistake, the cost isn’t too high. This algorithmic structure seems quite natural: mostly follow a baseline strategy, but ask for help when out-of-distribution.

#### Simple operations.

The algorithm does not require detailed access to the state embedding, instead relying on two simple operations: evaluating a policy on a particular state, and computing a nearest neighbor distance. The former seems necessary for any algorithm. The latter could be modeled as an out-of-distribution detector score, for which many methods are available (see e.g., []).

#### Hedge.

Hedge [] is a standard online learning algorithm which ensures sublinear regret when the number of hypotheses (in our case, the number of policies in $\Pi$) is finite.(^10^1010See Chapter 5 of [] and Chapter 21 of [] for modern introductions to Hedge.) We would prefer not to assume that $\Pi$ is finite. Luckily, any policy $\Pi$ can be approximated within $\varepsilon$ when either (1) $\Pi$ has finite VC dimension and $\mathbf{s}$ $\sigma$-smooth or (2) $\Pi$ has finite Littlestone dimension. Thus we can run Hedge on this approximative policy class instead.

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, we modify Hedge to only perform updates on time steps with queries and to issue a query with probability $p$ on each time step. Continuing our lucky streak, [] analyzes exactly this modification of Hedge.

Figure: Algorithm 1 successfully avoids catastrophe assuming finite VC or Littlestone dimension.

We prove the following theorem parametrized by $\varepsilon$:

###### Theorem 5.1 .

Let $A=\{0,1\}$. Assume $\pi^{m}\in\Pi$ where either (1) $\Pi$ has finite VC dimension $d$, $\mathbf{s}$ is $\sigma$-smooth, and $\varepsilon T\log T>12\sigma d\log(4e^{2}/\varepsilon)$ or (2) $\Pi$ has finite Littlestone dimension $d$. Then for any $T\in\mathbb{N}$ and $\varepsilon>0$, Algorithm 1 satisfies

$$ $\displaystyle\operatorname*{\mathbb{E}}\left[R_{T}\right]\in$ $\displaystyle\ O\left(\frac{dL}{\sigma}T\varepsilon^{1+1/n}\log(1/\varepsilon) \log T\right)$ $\displaystyle\operatorname*{\mathbb{E}}[|Q_{T}|]\in$ $\displaystyle\ O\left(\sqrt{\frac{T}{\varepsilon}}+\frac{d}{\sigma}T \varepsilon\log(1/\varepsilon)\log T+\frac{\operatorname*{diam}(\mathbf{s})^{n }}{\varepsilon}\right)$ $$

In Case 1, the expectation is over the randomness of both $\mathbf{s}$ and the algorithm, while in Case 2, the expectation is over only the randomness of the algorithm. Also, $R_{T}$ and $Q_{T}$ clearly have no dependence on $\sigma$ in Case 2, but we include $\sigma$ anyway to avoid writing two separate bounds.

To obtain subconstant regret and sublinear queries, we can choose $\varepsilon=T^{\frac{-2n}{2n+1}}$. This also satisfies the requirement of $\varepsilon T\log T>12\sigma d\log(4e^{2}/\varepsilon)$ for large enough $T$.

###### Theorem 5.2 .

Let $A=\{0,1\}$. Assume $\pi^{m}\in\Pi$ where either (1) $\Pi$ has finite VC dimension $d$ and $\mathbf{s}$ is $\sigma$-smooth or (2) $\Pi$ has finite Littlestone dimension $d$. Then for any $T\in\mathbb{N}$, Algorithm 1 with $\varepsilon=T^{\frac{-2n}{2n+1}}$ satisfies

$$ $\displaystyle\operatorname*{\mathbb{E}}\left[R_{T}\right]\in$ $\displaystyle\ O\left(\frac{dL}{\sigma}T^{\frac{-1}{2n+1}}\log T\right)$ $\displaystyle\operatorname*{\mathbb{E}}[|Q_{T}|]\in$ $\displaystyle\ O\left(T^{\frac{4n+1}{4n+2}}\left(\frac{d}{\sigma}\log T+ \operatorname*{diam}(\mathbf{s})^{n}\right)\right)$ $$

We can also make the query bound unconditional in exchange for slightly worse bounds. The probability that $|Q_{T}|$ asymptotically exceeds the bound from Theorem 5.2 goes to 0, so the query threshold in Corollary 5.2.1 is almost never reached. Thus we still obtain subconstant regret.

###### Corollary 5.2.1 .

If Algorithm 1 is modified to stop querying after $T^{\frac{4n+1.5}{4n+2}}(\frac{d}{\sigma}\log T+\operatorname*{diam}(\mathbf{s}
)^{n})$ queries, then under the conditions of Theorem 5.2, we have $\operatorname*{\mathbb{E}}[R_{T}]\in O\big{(}\frac{dL}{\sigma}T^{\frac{-1}{8n+
4}}\log T\big{)}$.

###### Theorem 5.1 .

###### Theorem 5.2 .

###### Corollary 5.2.1 .

### 5.2 Proof sketch

The formal proof of Theorem 5.1 can be found in Appendix 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-distrubtion” 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 match the mentor’s), and the latter will bound the cost of any single mistake. We must also carefully show that the latter does not result in excessively many queries, which we do via a novel packing argument.

We begin by formalizing two notion of approximating a policy class:

###### Definition 5.3 .

Let $U$ be the uniform distribution over $S$. For $\varepsilon>0$, a policy class $\tilde{\Pi}$ is a *smooth $\varepsilon$-cover* of a policy class $\Pi$ is for every $\pi\in\Pi$, there exists $\tilde{\pi}\in\tilde{\Pi}$ such that $\Pr_{s\sim U}[\pi(s)\neq\tilde{\pi}(s)]\leq\varepsilon$.

###### Definition 5.4 .

A policy class $\tilde{\Pi}$ is an *adversarial cover* of a policy class $\Pi$ is for every $\mathbf{s}\in S^{T}$ and $\pi\in\Pi$, there exists $\tilde{\pi}\in\tilde{\Pi}$ such that $\pi(s_{t})=\tilde{\pi}(s_{t})$ for all $t\in[T]$.

The existence of small covers is crucial:

###### Lemma 5.1 (Lemma 7.3.2 in [ 16 ] 11 11 11 See also [ 19 ] or Lemma 13.6 in [ 6 ] for variants which are less convenient for our purposes. ) .

For all $\varepsilon>0$, any policy class of VC dimension $d$ admits a smooth $\varepsilon$-cover of size at most $(41/\varepsilon)^{d}$.

###### Lemma 5.2 (Lemmas 21.13 and A.5 in [ 34 ] ) .

Any policy class of Littlestone dimension $d$ admits an adversarial cover of size at most $(eT/d)^{d}$.

An adversarial cover is a perfect cover by definition. The following lemma establishes that a smooth $\varepsilon$-cover is a good approximation for any sequence of $\sigma$-smooth distributions.

###### Lemma 5.3 (Equation 2 and Lemma 3.3 in [ 17 ] ) .

Let $\tilde{\Pi}$ be a finite smooth $\varepsilon$-cover of $\Pi$ and let $\boldsymbol{\mathcal{D}}=\mathcal{D}_{1},\dots,\mathcal{D}_{T}$ be a sequence of $\sigma$-smooth distributions. If $\varepsilon T\log T>12\sigma d\log(4e^{2}/\varepsilon)$, then

$$ $\operatorname*{\mathbb{E}}_{\mathbf{s}\sim\boldsymbol{\mathcal{D}}}\left[\sup \limits_{\pi\in\Pi}\min\limits_{\tilde{\pi}\in\tilde{\Pi}}\sum_{t=1}^{T} \mathbf{1}(\pi(s_{t})\neq\tilde{\pi}(s_{t}))\right]\in O\left(\sqrt{\frac{d \varepsilon T}{\sigma}\log T\log(1/\varepsilon)}+\frac{\varepsilon T}{\sigma} \log T\right)$ $$

We will run a variant of Hedge on $\tilde{\Pi}$. The vanilla Hedge algorithm operates in the standard online learning model where on each time step, the agent selects a 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 $\ell(t,\pi)=\mathbf{1}(\pi(s_{t})\neq\pi^{m}(s_{t}))$. Crucially, whenever we query and learn $\pi^{m}(s_{t})$, we can compute $\ell(t,\pi)$ for every $\pi\in\tilde{\Pi}$.

We cannot afford to query on every time step, however. Recently, [] 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 Appendix B for details). Although their result is stated for non-adaptive adversaries, we explain in Section B.3 how their argument easily generalizes to adaptive adversaries. Full pseudocode for HedgeWithQueries can also be found in the appendix (Algorithm 2).

###### Lemma 5.4 (Lemma 3.5 in [ 33 ] ) .

Assume $\tilde{\Pi}$ is finite. Then for any loss function $\ell:[T]\times\tilde{\Pi}\to[0,1]$ and query probability $p$, HedgeWithQueries enjoys the regret bound

$$ $\sum_{t=1}^{T}\operatorname*{\mathbb{E}}[\ell(t,\pi_{t})]-\min_{\tilde{\pi}\in \tilde{\Pi}}\sum_{t=1}^{T}\ell(t,\pi)\leq\frac{2\log|\tilde{\Pi}|}{p^{2}}$ $$

where $\pi_{t}$ is the policy chosen at time $t$ and the expectation is over the randomness of the algorithm.

We apply Lemma 5.4 with $\ell(t,\pi)=\mathbf{1}(\pi(s_{t})\neq\pi^{m}(s_{t}))$ and combine this with Lemmas 5.1 and 5.3 (in the $\sigma$-smooth case) and with Lemma 5.2 (in the adversarial case). This yields a $O\left(\frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T\right)$ bound on the number of mistakes made by Algorithm 1 (Lemma B.1).

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.2). The trickier part is bounding the number of resulting queries. It is tempting to claim that the states queried in the out-of-distribution case must all be separated by at least $\varepsilon^{1/n}$ and thus form an $\varepsilon^{1/n}$-packing, but this is actually not true. Instead, the packing analysis must be performed on a per-action basis, and we reuse Lemma B.1 to crucially show that there isn’t too much “spillover” between actions. The resulting overall query bound is given by Lemma B.7.

###### Definition 5.3 .

###### Definition 5.4 .

###### Lemma 5.1 (Lemma 7.3.2 in [ 16 ] 11 11 11 See also [ 19 ] or Lemma 13.6 in [ 6 ] for variants which are less convenient for our purposes. ) .

###### Lemma 5.2 (Lemmas 21.13 and A.5 in [ 34 ] ) .

###### Lemma 5.3 (Equation 2 and Lemma 3.3 in [ 17 ] ) .

###### Lemma 5.4 (Lemma 3.5 in [ 33 ] ) .

## 6 Conclusion and future work

In this paper, we proposed a model of avoiding catastrophe in online learning. We showed that achieving subconstant regret in our problem (with the help of a mentor and local generalization) is no harder than achieving sublinear regret in standard online learning.

There remain some technical questions within this paper’s model. One question is whether the time complexity of Algorithm 1 be improved, which currently stands at $\Omega(|\tilde{\Pi}|\cdot T)$ plus the time to compute the $\varepsilon$-cover. Also, we have not resolved whether our problem is tractable for finite VC dimension 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).

We are also interested in alternatives to the local generalization assumption, since an action which is safe in one state may not always be safe in a nearby state (depending on the definition of “nearby”). Some assumption is necessary, or there is no way to avoid costly mistakes without querying on every time step. One possibility is Bayesian inference. We intentionally avoided Bayesian approaches in this paper due to tractability concerns, but it seems premature to abandon those ideas entirely.

Finally, we are excited to apply the ideas in this paper to Markov Decision Processes (MDPs):
specifically, MDPs where some actions are irreversible (“non-communicating”) and the agent only gets one attempt (“single-episode”). In such MDPs, the agent must not only avoid catastrophe but also obtain 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:

Is there an algorithm for non-communicating single-episode undiscounted MDPs which ensures that both the regret and the number of mentor queries are sublinear in $T$?

## Acknowledgements

This work was supported in part by a gift from Open Philanthropy to the Center for Human-Compatible AI (CHAI) at UC Berkeley. This paper also benefited from discussions with many other researchers. We would like to especially thank (in alphabetical order) Cameron Allen, Michael Cohen, Scott Emmons, Nika Haghtalab, Aly Lidayan, Juan Liévano-Karim, Bhaskar Mishra, and Matteo Russo.

## Appendix A Proof of Theorem 4.1

### A.1 Proof roadmap

Throughout the proof, let $V_{j}$ be the set of time steps $t\leq T$ where $|m_{j}-s_{t}|\leq\mfrac{1}{4f(T)}$. In words, $s_{t}$ is relatively close to the midpoint of $S_{j}$. This will imply that the suboptimal action is in fact quite suboptimal. This also implies that $s_{t}$ is in $S_{j}$, since each $S_{j}$ has length $1/f(T)$.

Recall that $\operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\mathbf{a}}$ denotes the expectation over both the random states and any additional randomness in the algorithm.

The proof proceeds via the following steps:

- 1.
Prove that $f(T)=\sqrt{(|Q_{T}|+1)T}$ is asymptotically between $|Q_{T}|$ and $T$ (Lemma A.1).
- 2.
Provide a simple variant of the Chernoff bound which we will apply multiple times (Lemma A.2).
- 3.
Show that with high probability, $\sum_{j\in A}|V_{j}|$ is adequately large (Lemma A.3).
- 4.
The key lemma is Lemma A.4, which shows that a randomly sampled $\mathbf{x}$ produces poor agent performance with high probability. The central idea is that at least $f(T)-|Q_{T}|$ sections are never queried (which is large, by Lemma A.1), 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 a quarter of the time with high probability). Lemma A.3 implies that a constant fraction of those time steps will have quite suboptimal payoffs, again with high probability.
- 5.
To complete the proof, we observe that $\sup_{\mu}\ \operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\,\mathbf{a}}\ R_
{T}(\mathbf{s},\mathbf{a},\mu,\pi^{m})\geq\operatorname*{\mathbb{E}}_{\mathbf{
x}\sim U(\{0,1\}^{f(T)})}\ \operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\,
\mathbf{a}}\ R_{T}(\mathbf{s},\mathbf{a},\mu_{f,\mathbf{x}},\pi^{m})$. This is essentially an application of the probabilistic method: if a randomly chosen $\mu_{f,\mathbf{x}}$ has high expected regret, then the worst case $\mu$ also has high expected regret.

Note that $\mathbf{s},\mathbf{a}$, and $\mathbf{x}$ are random variables, so all variables defined on top of them (such as $V_{j}$) are also random variables. In contrast, the partition $S=\{S_{1},\dots,S_{f(T)}\}$ and properties thereof (like the midpoints $m_{j}$) are not random variables.

Lastly, while the intuition provided in Section 4.1 is accurate, the analysis will mostly occur in log space, so the bounds will look different. However, bounds of the form discussed in Section 4.1 can still be found as an intermediate step in Part 4 of the proof of Lemma A.4.

### A.2 Proof

###### Lemma A.1 .

Let $a,b:\mathbb{N}\to\mathbb{N}$ be functions such that $a(x)\in o(b(x))$. Then $c(x)=\sqrt{a(x)b(x)}$ satisfies $a(x)\in o(c(x))$ and $c(x)\in o(b(x))$.

###### Proof.

Since $a$ and $b$ are strictly positive (and thus $c$ is as well), we have

$$ $\frac{a(x)}{c(x)}=\frac{a(x)}{\sqrt{a(x)b(x)}}=\sqrt{\frac{a(x)}{b(x)}}=\frac{ \sqrt{a(x)b(x)}}{b(x)}=\frac{c(x)}{b(x)}$ $$

Then $a(x)\in o(b(x))$ implies

$$ $\displaystyle\lim_{x\to\infty}\frac{a(x)}{c(x)}=\lim_{x\to\infty}\frac{c(x)}{b (x)}=\lim_{x\to\infty}\sqrt{\frac{a(x)}{b(x)}}=0$ $$

as required.
∎

###### Lemma A.2 .

Let $z_{1},\dots,z_{n}$ be i.i.d. variables in $\{0,1\}$ and let $Z=\sum_{i=1}^{n}z_{i}$. If $\operatorname*{\mathbb{E}}[Z]\geq M$, then $\Pr\big{[}Z\leq M/2\big{]}\leq\exp(-M/8)$.

###### Proof.

By the Chernoff bound for i.i.d. binary variables, we have $\Pr[Z\leq\operatorname*{\mathbb{E}}[Z]/2]\leq\exp(-\operatorname*{\mathbb{E}}[
Z]/8)$. Since $-\operatorname*{\mathbb{E}}[Z]\leq-M$ and $\exp$ is an increasing function, we have $\exp(-\operatorname*{\mathbb{E}}[Z]/8)\leq\exp(-M/8)$. Also, $M/2\leq E[Z]/2$ implies $\Pr[Z\leq M/2]\leq\Pr[Z\leq\operatorname*{\mathbb{E}}[Z]/2]$. Combining these inequalities proves the lemma.
∎

###### Lemma A.3 .

let $A\subseteq[f(T)]$ be any nonempty subset of sections. Then

$$ $\Pr\left[\sum_{j\in A}|V_{j}|\leq\frac{T|A|}{4f(T)}\right]\leq\exp\left(\frac{ -T}{16f(T)}\right)$ $$

###### Proof.

Fix any $j\in[f(T)]$. For each $t\in[T]$ , define the random variable $z_{t}$ by $z_{t}=1$ if $t\in V_{j}$ for some $j\in A$ and 0 otherwise. We have $t\in V_{j}$ iff $s_{t}$ falls within a particular interval of length $\mfrac{1}{2f(T)}$. Since these intervals are disjoint for different $j$’s, we have $z_{t}=1$ iff $s_{t}$ falls within a portion of the state space with total measure $\mfrac{|A|}{2f(T)}$. Since $s_{t}$ is uniformly random across $[0,1]$, we have $\operatorname*{\mathbb{E}}[z_{t}]=\frac{|A|}{2f(T)}$. Then $\operatorname*{\mathbb{E}}[\sum_{t=1}^{T}z_{t}]=\operatorname*{\mathbb{E}}[
\sum_{j\in A}|V_{j}|]=\frac{T|A|}{2f(T)}$. Furthermore, since $s_{1},\dots,s_{T}$ are i.i.d., so are $z_{1},\dots,z_{T}$. Then by Lemma A.2,

$$ $\Pr\left[\sum_{j\in A}|V_{j}|\leq\frac{T|A|}{4f(T)}\right]\leq\exp\left(\frac{ -T|A|}{16f(T)}\right)\leq\exp\left(\frac{-T}{16f(T)}\right)$ $$

with the last step due to $|A|\geq 1$.
∎

###### Lemma A.4 .

Independently sample $\mathbf{x}\sim U(\{0,1\}^{f(T)})$ and $\mathbf{s}\sim U^{T}$.(^12^1212That is, the entire set $\{x_{1},\dots,x_{f(T)},s_{1},\dots,s_{T}\}$ is mutually independent.) Then with probability at least $1-\exp\big{(}\frac{-T}{16f(T)}\big{)}-\exp\big{(}-\frac{f(T)-|Q_{T}|}{16}\big{)}$,

$$ $\prod_{t=1}^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\leq\exp\left(-\frac{LT(f(T)-|Q_ {T}|)}{2^{7}f(T)^{2}}\right)$ $$

###### Proof.

Part 1: setup. Let $J_{\neg Q}=\{j\in[f(T)]:s_{t}\not\in S_{j}\ \forall t\in Q_{T}\}$ be the set of sections that are never queried. Since each query appears in exactly one section (because each state appears in exactly one section), $|J_{\neg Q}|\geq f(T)-|Q_{T}|$.

For each $j\in J_{\neg Q}$, let $y_{j}$ be the action taken most frequently among time steps in $V_{j}$:

$$ $y_{j}=\operatorname*{arg\,max}_{a\in\{0,1\}}\Big{|}\{t\in V_{j}:a=a_{t}\}\Big{|}$ $$

Let $\bar{J}=\{j\in J_{\neg Q}:x_{j}\neq y_{j}\}$. For each $j\in\bar{J}$, let $V_{j}^{\prime}=\{t\in V_{j}:a_{t}\neq x_{j}\}$ be the set of time steps where the agent chooses the wrong action (assuming payoff function $\mu_{f,\mathbf{x}}$).

Part 2: $\bar{J}$ is not too small. Define a random variable $z_{j}=\mathbf{1}_{j\in\bar{J}}$ for each $j\in J_{\neg Q}$. By definition, if $j\in J_{\neg Q}$, no state in $S_{j}$ is queried. Since queries outside of $S_{j}$ provide no information about $x_{j}$, the agent’s actions must be independent of $x_{j}$. In particular, the random variables $x_{j}$ and $y_{j}$ are independent. Combining that independence with $\Pr[x_{j}=0]=\Pr[x_{j}=1]=0.5$ yields $\Pr[z_{j}=1]=0.5$ for all $j\in J_{\neg Q}$. Furthermore, since $x_{1},\dots,x_{f(T)}$ are independent, the random variables $\{z_{j}:j\in J_{\neg Q}\}$ are also independent. Since $\operatorname*{\mathbb{E}}[|\bar{J}|]=\operatorname*{\mathbb{E}}[\sum_{j\in J_
{\neg Q}}z_{j}]=|J_{\neg Q}|/2\geq\mfrac{f(T)-|Q_{T}|}{2}$, Lemma A.2 implies that

$$ $\Pr\left[|\bar{J}|\leq\frac{f(T)-|Q_{T}|}{4}\right]\leq\exp\left(-\frac{f(T)-| Q_{T}|}{16}\right)$ $$

Part 3: $|V_{j}^{\prime}|\geq|V_{j}|/2$.
Since $j\in J_{\neg Q}$, the mentor is not queried on any time step $t\in V_{j}$, so $a_{t}\in\{0,1\}$ for all $t\in V_{j}$. Since the agent chooses one of two actions for each $t\in V_{j}$, the more frequent action must be chosen chosen at least half of the time: $a_{t}=y_{j}$ for at least half of the time steps in $V_{j}$. Since $x_{j}\neq y_{j}$ for $j\in\bar{J}$, we have $a_{t}=y_{j}\neq x_{j}$ for those time steps, so $|V_{j}^{\prime}|\geq|V_{j}|/2$.

Part 4: a bound in terms of $\bar{J}$ and $V_{j}$. Consider any $j\in\bar{J}$ and $t\in V_{j}^{\prime}\subseteq V_{j}$. By definition of $V_{j}$, we have $|m_{j}-s_{t}|\leq\frac{1}{4f(T)}$. Then by definition of $\mu_{f,\mathbf{x}}$,

$$ $\displaystyle\mu_{f,\mathbf{x}}(s_{t},a_{t})=$ $\displaystyle\ 1-L\left(\frac{1}{2f(T)}-|s_{t}-m_{j}|\right)$ $\displaystyle\leq$ $\displaystyle\ 1-L\left(\frac{1}{2f(T)}-\frac{1}{4f(T)}\right)$ $\displaystyle=$ $\displaystyle\ =1-\frac{L}{4f(T)}$ $$

Now aggregating across time steps,

$$ $\displaystyle\prod_{t=1}^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\leq$ $\displaystyle\ \prod_{j\in\bar{J}}\prod_{t\in V_{j}^{\prime}}\mu_{f,\mathbf{x} }(s_{t},a_{t})$ $\displaystyle(\text{$\mu_{f,\mathbf{x}}(s_{t},a_{t})\in[0,1]$ for all $t$})$ $\displaystyle\leq$ $\displaystyle\ \prod_{j\in\bar{J}}\left(1-\frac{L}{4f(T)}\right)^{|V_{j}^{ \prime}|}$ $\displaystyle(\text{bound on $\mu_{f,\mathbf{x}}(s_{t},a_{t})$ when $t\in V_{j }^{\prime}$})$ $\displaystyle\leq$ $\displaystyle\ \prod_{j\in\bar{J}}\left(1-\frac{L}{4f(T)}\right)^{|V_{j}|/2}$ $\displaystyle(\text{$|V_{j}^{\prime}|\geq|V_{j}|/2$})$ $$

The last step also relies on $1-\mfrac{L}{4f(T)}\in[0,1]$, which is due to $L\leq 1$ and $f(T)\geq 1$. Converting into log space and using the standard inequality $\log(1+x)\leq x$ for all $x\in\mathbb{R}$, we have

$$ $\displaystyle\log\prod_{t=1}^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\leq$ $\displaystyle\ \log\prod_{j\in\bar{J}}\left(1-\frac{L}{4f(T)}\right)^{|V_{j}|/2}$ $\displaystyle=$ $\displaystyle\ \sum_{j\in\bar{J}}\frac{|V_{j}|}{2}\log\left(1-\frac{L}{4f(T)}\right)$ $\displaystyle\leq$ $\displaystyle\ -\sum_{j\in\bar{J}}\frac{L|V_{j}|}{8f(T)}$ $$

Part 5: putting it all together. By Lemma A.3, Part 2 of this lemma, and the union bound, with probability at least $1-\exp\big{(}\frac{-T}{16f(T)}\big{)}-\exp\big{(}-\frac{f(T)-|Q_{T}|}{16}\big{)}$ we have $\sum_{j\in\bar{J}}|V_{j}|\geq\mfrac{T|\bar{J}|}{4f(T)}$ for all $j\in[f(T)]$ and $|\bar{J}|\geq\mfrac{f(T)-|Q_{T}|}{4}$. Assuming those inequalities hold, we have

$$ $\displaystyle\log\prod_{t=1}^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\leq$ $\displaystyle\ -\sum_{j\in\bar{J}}\frac{L|V_{j}|}{8f(T)}$ $\displaystyle\leq$ $\displaystyle\ -\frac{L}{8f(T)}\cdot\frac{T|\bar{J}|}{4f(T)}$ $\displaystyle\leq$ $\displaystyle\ -\frac{L}{8f(T)}\cdot\frac{T}{4f(T)}\cdot\frac{f(T)-|Q_{T}|}{4}$ $\displaystyle=$ $\displaystyle\ -\frac{LT(f(T)-|Q_{T}|)}{2^{7}f(T)^{2}}$ $$

Exponentiating both sides proves the lemma.
∎

Let $\alpha(T)=\exp\big{(}\frac{-T}{16f(T)}\big{)}+\exp\big{(}-\frac{f(T)-|Q_{T}|}{
16}\big{)}$ for brevity.
See 4.1

###### Proof.

If the algorithm has sublinear queries, then there exists $g(T)\in o(T)$ such that $|Q_{T}|\leq g(T)$ for all $\mathbf{s},\mu,\pi^{m}$. Let $f(T)=\sqrt{(g(T)+1)T}$. Then by Lemma A.1, $g(T)\in o(f(T))$ and $f(T)\in o(T)$. Combining this with $|Q_{T}|\leq g(T)$, we get $\lim_{T\to\infty}\alpha(T)=0$. Also, since $|Q_{T}|\in o(f(T))$, there exists $T_{0}$ such that $|Q_{T}|\leq f(T)/2$ for all $T\geq T_{0}$. Combining this with Lemma A.4 and noting that $\prod_{t=1}^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\leq 1$, we have

$$ $\displaystyle\ \operatorname*{\mathbb{E}}_{\mathbf{x}\sim U(\{0,1\}^{f(T)})}\ \,\operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\,\mathbf{a}}\ \>\prod_{t=1 }^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})$ $\displaystyle\leq$ $\displaystyle\ \alpha(T)\cdot 1+\big{(}1-\alpha(T)\big{)}\exp\left(-\frac{LT(f (T)-|Q_{T}|)}{2^{7}f(T)^{2}}\right)$ $\displaystyle\leq$ $\displaystyle\ \alpha(T)+\big{(}1-\alpha(T)\big{)}\exp\left(-\frac{LTf(T)/2}{2 ^{7}f(T)^{2}}\right)$ $\displaystyle=$ $\displaystyle\ \alpha(T)+\big{(}1-\alpha(T)\big{)}\exp\left(-\frac{LT}{2^{8}f( T)}\right)$ $$

whenever $T\geq T_{0}$. Since $\prod_{t=1}^{T}\mu_{f,\mathbf{x}}^{m}(s_{t})=1$ always, we have(^13^1313Fubini’s theorem means we need not worry about the order of the expectation operators.)

$$ $\displaystyle\sup_{\mu}\ \operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\, \mathbf{a}}\ R_{T}(\mathbf{s},\mathbf{a},\mu,\pi^{m})\geq$ $\displaystyle\ \operatorname*{\mathbb{E}}_{\mathbf{x}\sim U(\{0,1\}^{f(T)})}\ \,\operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\,\mathbf{a}}\ R_{T}( \mathbf{s},\mathbf{a},\mu_{f,\mathbf{x}},\pi^{m})$ $\displaystyle=\operatorname*{\mathbb{E}}_{\mathbf{x}\sim U(\{0,1\}^{f(T)})}\ \,\operatorname*{\mathbb{E}}_{\mathbf{s}\sim U^{T},\,\mathbf{a}}$ $\displaystyle\ \,\left[\prod_{t=1}^{T}\mu_{f,\mathbf{x}}^{m}(s_{t})-\prod_{t=1 }^{T}\mu_{f,\mathbf{x}}(s_{t},a_{t})\right]$ $\displaystyle\geq$ $\displaystyle\ 1-\alpha(T)-\big{(}1-\alpha(T)\big{)}\exp\left(-\frac{LT}{2^{8} f(T)}\right)$ $$

Therefore

$$ $\displaystyle\lim_{T\to\infty}\sup_{\mu}\ \operatorname*{\mathbb{E}}_{\mathbf{ s}\sim U^{T},\,\mathbf{a}}\ R_{T}(\mathbf{s},\mathbf{a},\mu,\pi^{m})\geq$ $\displaystyle\ 1-\lim_{T\to\infty}\alpha(T)-\big{(}1-\lim_{T\to\infty}\alpha(T )\big{)}\cdot\exp\left(\lim_{T\to\infty}-\frac{LT}{2^{8}f(T)}\right)$ $\displaystyle=$ $\displaystyle\ 1-0-(1-0)\cdot\exp(-\infty)$ $\displaystyle=$ $\displaystyle\ 1$ $$

as required.
∎

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Lemma A.3 .

###### Proof.

###### Lemma A.4 .

###### Proof.

###### Proof.

## Appendix 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:

See 5.4

Lemma 5.4 is a restatement and simplification of Lemma 3.5 in []. First, [] parametrize their algorithm by the expected number of queries $\hat{k}$ instead of the query probability $p=\hat{k}/T$. Second, [] include a second parameter $k$, which is the eventual target number of queries for their unconditional query bound. In our case, an expected query bound is sufficient, so we simply set $k=\hat{k}$. Third, [] provide a second bound which is tighter for small $k$; that bound is less useful for us so we omit it. Fourth, their number of actions $n$ is equal to $|\tilde{\Pi}|$ in our setting. (Their actions correspond to policies in $\tilde{\Pi}$, not our actions in $A$.) Since [] set $\eta=\max\Big{(}\frac{1}{T}\sqrt{\frac{\hat{k}\log n}{2}},\frac{k\hat{k}}{
\sqrt{2}T^{2}}\Big{)}$, we end up with $\eta=\max\Big{(}\sqrt{\frac{p\log|\tilde{\Pi}|}{2T}},\>\frac{p^{2}}{\sqrt{2}}
\Big{)}$. Algorithm 2 provides precise pseudocode for the HedgeWithQueries algorithm to which Lemma 5.4 refers.

Figure: Algorithm 2 A variant of the Hedge algorithm which only observes losses in response to queries.

### B.2 Main proof

We use the following notation throughout the proof:

- 1.
For each $t\in[T]$, let $X_{t}$ refer to the value of $X$ at the start of time step $t$.
- 2.
Let $V_{T}=\{t\in[T]:\pi_{t}(s_{t})\neq\pi^{m}(s_{t})\}$ be the set of time steps where Hedge’s proposed action doesn’t match the mentor’s. Note that $|V_{T}|$ upper bounds the number of mistakes the algorithm makes (the number of mistakes could be smaller, since the algorithm sometimes queries instead of taking action $\pi_{t}(s_{t})$).
- 3.
For $K\subseteq S$, let $\operatorname*{vol}(K)$ denote the $n$-dimensional Lebesgue measure of $K$.
- 4.
With slight abuse of notation, we will use inequalities of the form $f(T)\leq g(T)+O(h(T))$ to mean that there exists a constant $C$ such that $f(T)\leq g(T)+Ch(T)$.
- 5.
We will use “Case 1” to refer to finite VC dimension and $\sigma$-smooth $\mathbf{s}$ and “Case 2” to refer to finite Littlestone dimension. In Case 1, expectations are over the randomness of both $\mathbf{s}$ and the algorithm, while in Case 2, expectations are over just the randomness of the algorithm. When we need to distinction, we use $\operatorname*{\mathbb{E}}_{\mathbf{a}}$ to denote the expectation over randomness of the algorithm and $\operatorname*{\mathbb{E}}_{\mathbf{s}\sim\boldsymbol{\mathcal{D}}}$ to denote the expectation over $\mathbf{s}$.

###### Lemma B.1 .

Under the conditions of Theorem 5.1, Algorithm 1 satisfies

$$ $\operatorname*{\mathbb{E}}[|V_{T}|]\in O\left(\frac{d}{\sigma}T\varepsilon\log (1/\varepsilon)\log T\right)$ $$

###### Proof.

Define $\ell:[T]\times\tilde{\Pi}\to[0,1]$ by $\ell(t,\pi)=\mathbf{1}(\pi(s_{t})\neq\pi^{m}(s_{t}))$, and let $w^{h}$ and $\pi_{t}^{h}$ denote the values of $w$ and $\pi_{t}$ respectively in HedgeWithQueries, while $w$ and $\pi_{t}$ refer to the variables in Algorithm 1. Then $w$ and $w^{h}$ evolve in the exact same way, so the distributions of $\pi_{t}$ and $\pi_{t}^{h}$ coincide. Thus by Lemma 5.4,

$$ $\operatorname*{\mathbb{E}}_{\mathbf{a}}\left[\sum_{t=1}^{T}\ell(t,\pi_{t}) \right]-\min_{\tilde{\pi}\in\tilde{\Pi}}\sum_{t=1}^{T}\ell(t,\tilde{\pi})\leq \frac{2\log|\tilde{\Pi}|}{p^{2}}=2T\varepsilon\log|\tilde{\Pi}|$ $$

Since Lemma 5.4 holds for any loss function, the bound above holds for any $\mathbf{s}\in S^{T}$, so the bound also holds in expectation over $\mathbf{s}\sim\boldsymbol{\mathcal{D}}$ (which is needed for Case 1). Next, observe that $|V_{T}|=\sum_{t=1}^{T}\mathbf{1}(\pi_{t}(s_{t})\neq\pi^{m}(s_{t}))=\sum_{t=1}^
{T}\ell(t,\pi_{t})$, so

$$ $\operatorname*{\mathbb{E}}_{\mathbf{a}}[|V_{T}|]\leq 2T\varepsilon\log|\tilde{ \Pi}|+\min_{\tilde{\pi}\in\tilde{\Pi}}\sum_{t=1}^{T}\mathbf{1}(\tilde{\pi}(s_{ t})\neq\pi^{m}(s_{t}))$ $$

Case 1: Since $\tilde{\Pi}$ is a smooth $\varepsilon$-cover of $\Pi$, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{s}\sim\boldsymbol{\mathcal{D} }}\left[\min_{\tilde{\pi}\in\tilde{\Pi}}\sum_{t=1}^{T}\mathbf{1}(\tilde{\pi}(s _{t})\neq\pi^{m}(s_{t}))\right]\leq$ $\displaystyle\ \operatorname*{\mathbb{E}}_{\mathbf{s}\sim\boldsymbol{\mathcal{ D}}}\left[\sup_{\pi\in\Pi}\min_{\tilde{\pi}\in\tilde{\Pi}}\sum_{t=1}^{T} \mathbf{1}(\tilde{\pi}(s_{t})\neq\pi(s_{t}))\right]$ $\displaystyle\in$ $\displaystyle\ O\left(\frac{1}{\sigma}T\varepsilon\log T\sqrt{d\log(1/ \varepsilon)}\right)$ $$

with the first step due to $\pi^{m}\in\Pi$ and the second step due to Lemma 5.3. The last component we need is that $|\tilde{\Pi}|\leq(41/\varepsilon)^{d}$ by construction (and such a $\tilde{\Pi}$ is guaranteed to exist by Lemma 5.1). Combining the above inequalities and taking the expectation over $\mathbf{s}\sim\boldsymbol{\mathcal{D}}$ (in addition to the randomness of the algorithm), we get

$$ $\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{s}\sim\boldsymbol{\mathcal{D} },\,\mathbf{a}}\,[|V_{T}|]\leq$ $\displaystyle\ 2T\varepsilon\log|\tilde{\Pi}|+\operatorname*{\mathbb{E}}_{ \mathbf{s}\sim\boldsymbol{\mathcal{D}}}\left[\min_{\tilde{\pi}\in\tilde{\Pi}} \sum_{t=1}^{T}\mathbf{1}(\tilde{\pi}(s_{t})\neq\pi^{m}(s_{t}))\right]$ $\displaystyle\leq$ $\displaystyle\ 2dT\varepsilon\log(41/\varepsilon)+O\left(\frac{1}{\sigma}T \varepsilon\log T\sqrt{d\log(1/\varepsilon)}\right)$ $\displaystyle\in$ $\displaystyle\ O\left(\frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T\right)$ $$

Case 2: Since $\tilde{\Pi}$ is an adversarial cover of $\Pi$ and $\pi^{m}\in\Pi$, there exists $\tilde{\pi}\in\tilde{\Pi}$ such that $\sum_{t=1}^{T}\mathbf{1}(\tilde{\pi}(s_{t})\neq\pi^{m}(s_{t}))=0$. Since $|\tilde{\Pi}|\leq(eT/d)^{d}$ (with such a $\tilde{\Pi}$ guaranteed to exist by Lemma 5.2),

$$ $\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{a}}[|V_{T}|]\leq$ $\displaystyle\ 2T\varepsilon\log|\tilde{\Pi}|+\min_{\tilde{\pi}\in\tilde{\Pi}} \sum_{t=1}^{T}\mathbf{1}(\tilde{\pi}(s_{t})\neq\pi^{m}(s_{t}))$ $\displaystyle\leq$ $\displaystyle\ 2T\varepsilon d\ln(eT/d)$ $\displaystyle\in$ $\displaystyle\ O\left(\frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T\right)$ $$

as required.
∎

###### Lemma B.2 .

For all $t\in[T]$, $\mu(s_{t},a_{t})\geq\mu^{m}(s_{t})-L\varepsilon^{1/n}$.

###### Proof.

Fix any $t\in[T]$. If $t\in Q_{T}$, then $\mu(s_{t},a_{t})=\mu^{m}(s_{t})$, so assume $t\not\in Q_{T}$. Let $(s^{\prime},a^{\prime})=\operatorname*{arg\,min}_{(s,a)\in X_{t}:\pi_{t}(s_{t}
)=a}||s_{t}-s||$. Since $t\not\in Q_{T}$, we must have $||s_{t}-s^{\prime}||\leq\varepsilon^{1/n}$.

We have $a^{\prime}=\pi^{m}(s^{\prime})$ by construction of $X_{t}$ and $\pi_{t}(s_{t})=a^{\prime}$ by construction of $a^{\prime}$. Combining these with the local generalization assumption, we get

$$ $\mu(s_{t},a_{t})=\mu(s_{t},\pi_{t}(s_{t}))=\mu(s_{t},\pi^{m}(s^{\prime}))\geq \mu^{m}(s_{t})-L||s_{t}-s^{\prime}||\geq\mu^{m}(s_{t})-L\varepsilon^{1/n}$ $$

as required.
∎

###### Lemma B.3 .

Assume $x_{1},\dots,x_{T},y_{1},\dots,y_{T}\in[0,1]$ and $x_{t}\geq y_{t}$ for all $t\in[T]$. Then

$$ $\prod_{t=1}^{T}x_{t}-\prod_{t=1}^{T}y_{t}\leq\sum_{t=1}^{T}x_{t}-\sum_{t=1}^{T }y_{t}$ $$

###### Proof.

We proceed by induction on $T$. The claim is trivially satisfied for $T=1$, so suppose $T>1$ and assume that $\prod_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}y_{t}\leq\sum_{t=1}^{T-1}x_{t}-\sum_{t
=1}^{T-1}y_{t}$. Then

$$ $\displaystyle\sum_{t=1}^{T}x_{t}-\sum_{t=1}^{T}y_{t}-\prod_{t=1}^{T}x_{t}+ \prod_{t=1}^{T}y_{t}=$ $\displaystyle\ x_{T}\sum_{t=1}^{T-1}x_{t}-y_{T}\sum_{t=1}^{T-1}y_{t}-x_{T} \prod_{t=1}^{T-1}x_{t}+y_{T}\prod_{t=1}^{T-1}y_{t}$ $\displaystyle=$ $\displaystyle\ x_{T}\left(\sum_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}x_{t}\right)- y_{T}\left(\sum_{t=1}^{T-1}y_{t}-\prod_{t=1}^{T-1}y_{t}\right)$ $$

Since $T>1$ and $x_{t}\in[0,1]$ for all $t\in[T]$, we have $\sum_{t=1}^{T-1}x_{t}\geq x_{1}\geq\sum_{t=1}^{T-1}x_{t}$. Thus $\sum_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}x_{t}\geq 0$. Combining this with $x_{T}\geq y_{T}$, we get

$$ $\displaystyle\sum_{t=1}^{T}x_{t}-\sum_{t=1}^{T}y_{t}-\prod_{t=1}^{T}x_{t}+ \prod_{t=1}^{T}y_{t}=$ $\displaystyle\ x_{T}\left(\sum_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}x_{t}\right)- y_{T}\left(\sum_{t=1}^{T-1}y_{t}-\prod_{t=1}^{T-1}y_{t}\right)$ $\displaystyle\geq$ $\displaystyle\ y_{T}\left(\sum_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}x_{t}\right)- y_{T}\left(\sum_{t=1}^{T-1}y_{t}-\prod_{t=1}^{T-1}y_{t}\right)$ $\displaystyle=$ $\displaystyle\ y_{T}\left(\sum_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}x_{t}-\sum_{t =1}^{T-1}y_{t}+\prod_{t=1}^{T-1}y_{t}\right)$ $\displaystyle\geq$ $\displaystyle\ 0$ $$

The last step is due to $y_{T}\geq 0$ and our assumption of $\prod_{t=1}^{T-1}x_{t}-\prod_{t=1}^{T-1}y_{t}\leq\sum_{t=1}^{T-1}x_{t}-\sum_{t
=1}^{T-1}y_{t}$.
∎

###### Lemma B.4 .

Under the conditions of Theorem 5.1, Algorithm 1 satisfies

$$ $\operatorname*{\mathbb{E}}\left[R_{T}\right]\in O\left(\frac{dL}{\sigma}T \varepsilon^{1+1/n}\log(1/\varepsilon)\log T\right)$ $$

###### Proof.

We first claim that $a_{t}=\pi^{m}(s_{t})$ for all $t\not\in V_{T}$. If $t\in Q_{T}$, the claim is immediate; if not, we have $a_{t}=\pi_{t}(s_{t})$, and $\pi_{t}(s_{t})=\pi^{m}(s_{t})$ due to $t\not\in V_{T}$. Thus $\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))=\mu^{m}(s_{t})$ for $t\not\in V_{T}$.

We next claim that $\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\leq L\varepsilon^{1/n}$ for all $t\in[T]$. If $\mu(s_{t},a_{t})\leq\mu^{m}(s_{t})$, this follows from Lemma B.2. If $\mu(s_{t},a_{t})>\mu^{m}(s_{t})$, then $\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))=0\leq L\varepsilon^{1/n}$. Therefore

$$ $\displaystyle\sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t} ,a_{t}))\Big{)}\leq$ $\displaystyle\ \sum_{t\in V_{T}}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu( s_{t},a_{t}))\Big{)}$ $\displaystyle\leq$ $\displaystyle\ \sum_{t\in V_{T}}L\varepsilon^{1/n}$ $\displaystyle=$ $\displaystyle\ |V_{T}|L\varepsilon^{1/n}$ $$

Now let $x_{t}=\mu^{m}(s_{t})$ and $y_{t}=\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))$ for all $t\in[T]$. Then by Lemma B.3,

$$ $\displaystyle\prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{t=1}^{T}\min(\mu^{m}(s_{t}), \mu(s_{t},a_{t}))\leq$ $\displaystyle\ \sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{ t},a_{t}))\Big{)}$ $$

Since $\mu(s_{t},a_{t})\geq\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))$ for all $t\in[T]$, we have

$$ $\displaystyle R_{T}=$ $\displaystyle\ \prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{t=1}^{T}\mu(s_{t},a_{t})$ $\displaystyle\leq$ $\displaystyle\ \sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{ t},a_{t}))\Big{)}$ $\displaystyle\leq$ $\displaystyle\ |V_{T}|L\varepsilon^{1/n}$ $$

Taking the expectation and applying Lemma B.1 completes the proof.
∎

###### Definition B.1 .

Let $(K,||\cdot||)$ be a normed vector space and let $\delta>0$. Then $W\subseteq K$ is a $\delta$-packing of $K$ if for all $x,y\in W$, $||x-y||>\delta$. The $\delta$-packing number of $K$, denoted $\mathcal{M}(K,||\cdot||,\delta)$, is the maximum cardinality of any $\delta$-packing of $K$.

In this paper, we only consider the Euclidean distance norm, so we just write $M(K,||\cdot||,\delta)=M(K,\delta)$.

###### Lemma B.5 (Theorem 14.2 in [ 40 ] ) .

If $K\subset\mathbb{R}^{n}$ is convex, bounded, and contains a ball with radius $\delta>0$, then

$$ $\mathcal{M}(K,\delta)\leq\frac{3^{n}\operatorname*{vol}(K)}{\delta^{n} \operatorname*{vol}(B)}$ $$

where $B$ is a unit ball.

###### Lemma B.6 (Jung’s Theorem [ 22 ] ) .

If $K\subset\mathbb{R}^{n}$ is compact, then there exists a closed ball with radius at most $\operatorname*{diam}(K)\sqrt{\mfrac{n}{2(n+1)}}$ containing $K$.

###### Lemma B.7 .

Under the conditions of Theorem 5.1, Algorithm 1 satisfies

$$ $\operatorname*{\mathbb{E}}[|Q_{T}|]\in O\left(\sqrt{\frac{T}{\varepsilon}}+ \frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T+\frac{\operatorname*{ diam}(\mathbf{s})^{n}}{\varepsilon}\right)$ $$

###### Proof.

If $t\in Q_{T}$, then either $\texttt{hedgeQuery}=\texttt{true}$ or $\min_{(s,a)\in X_{t}:\pi_{t}(s_{t})=a}|s_{t}-s|>r$. The expected number of time steps with $\texttt{hedgeQuery}=\texttt{true}$ is $pT=\sqrt{T/\varepsilon}$, so let $\hat{S}=\{s_{t}:t\in Q_{T}\text{ and }\min_{(s,a)\in X_{t}:\pi_{t}(s_{t})=a}|s
_{t}-s|>r)\}$. We further subdivide $\hat{S}$ into $\hat{S}_{1}=\{s_{t}\in\hat{S}:\pi_{t}(s_{t})\neq\pi^{m}(s_{t})\}$ and $\hat{S}_{2}=\{s_{t}\in\hat{S}:\pi_{t}(s_{t})=\pi^{m}(s_{t})\}$. Since $\hat{S}_{1}\subseteq V_{T}$, Lemma B.1 implies that $\operatorname*{\mathbb{E}}[|\hat{S}_{1}|]\in O\left(\frac{d}{\sigma}T
\varepsilon\log(1/\varepsilon)\log T\right)$.

Next, fix an $a\in A$ and let $S_{a}=\{s\in\mathbf{s}:\pi^{m}(s)=a\}$ be the set of observed states which share a mentor action. We claim that $\hat{S}_{2}\cap S_{a}$ is a packing of $S_{a}$. Suppose instead that there exists $s,s^{\prime}\in\hat{S}_{2}\cap S_{a}$, with $||s-s^{\prime}||\leq\varepsilon^{1/n}$. WLOG assume $s$ was queried after $s^{\prime}$ and let $t$ be the time step on which $s$ was queried. Then $(s^{\prime},\pi^{m}(s^{\prime}))\in X_{t}$. Also, $s,s^{\prime}\in\hat{S}_{2}\cap S_{a}$ implies that and $\pi_{t}(s_{t})=\pi^{m}(s_{t})=a=\pi^{m}(s^{\prime})$. Therefore

$$ $\min_{(s^{\prime\prime},a^{\prime\prime})\in X_{t}:a^{\prime\prime}=\pi_{t}(s_ {t})}||s_{t}-s^{\prime\prime}||\leq||s_{t}-s^{\prime}||\leq\varepsilon^{1/n}$ $$

which contradicts $s_{t}\in\hat{S}$. Thus $\hat{S}_{2}\cap S_{a}$ is a $\varepsilon^{1/n}$-packing of $S_{a}$.

By Lemma B.6, there exists a ball $B_{1}$ of diameter $\operatorname*{diam}(\mathbf{s})\sqrt{\frac{n}{2(n+1)}}$ which contains $\mathbf{s}$. Let $R=\operatorname*{diam}(\mathbf{s})\sqrt{\frac{n}{8(n+1)}}$ denote the radius of $B_{1}$. Let $B_{2}$ be the ball with the same center as $B_{1}$ but with radius $\max(R,\varepsilon^{1/n})$. Since $S_{a}\subset\mathbf{s}\subset B_{1}\subset B_{2}$, $\hat{S}_{2}\cap S_{a}$ is also a $\varepsilon^{1/n}$-packing of $B_{2}$. Also, $B_{2}$ must contain a ball of radius $\varepsilon^{1/n}$, so Lemma B.5 implies that

$$ $\displaystyle|\hat{S}_{2}\cap S_{a}|\leq$ $\displaystyle\ \mathcal{M}(B_{2},\varepsilon^{1/n})$ $\displaystyle\leq$ $\displaystyle\ \frac{3^{n}\operatorname*{vol}(B_{2})}{\varepsilon\operatorname *{vol}(B)}$ $\displaystyle=$ $\displaystyle\ \big{(}\max(R,\varepsilon^{1/n})\big{)}^{n}\,\frac{3^{n} \operatorname*{vol}(B)}{\varepsilon\operatorname*{vol}(B)}$ $\displaystyle=$ $\displaystyle\ \max\left(\operatorname*{diam}(\mathbf{s})^{n}\left(\frac{n}{8( n+1)}\right)^{n/2},\>\varepsilon\right)\frac{3^{n}}{\varepsilon}$ $\displaystyle\leq$ $\displaystyle\ O\left(\frac{\operatorname*{diam}(\mathbf{s})^{n}}{\varepsilon} +1\right)$ $$

(The $+1$ is necessary for now since $\operatorname*{diam}(\mathbf{s})$ could theoretically be zero.) Therefore

$$ $\displaystyle\operatorname*{\mathbb{E}}[|Q_{T}|]=$ $\displaystyle\ \sqrt{\frac{T}{\varepsilon}}+\operatorname*{\mathbb{E}}[|\hat{S }|]$ $\displaystyle=$ $\displaystyle\ \sqrt{\frac{T}{\varepsilon}}+\operatorname*{\mathbb{E}}[|\hat{S }_{1}|]+\operatorname*{\mathbb{E}}\left[\sum_{a\in A}|\hat{S}_{2}\cap S_{a}|\right]$ $\displaystyle\leq$ $\displaystyle\ \sqrt{\frac{T}{\varepsilon}}+O\left(\frac{d}{\sigma}T \varepsilon\log(1/\varepsilon)\log T\right)+\sum_{a\in A}O\left(\frac{ \operatorname*{diam}(\mathbf{s})^{n}}{\varepsilon}+1\right)$ $\displaystyle\leq$ $\displaystyle\ \sqrt{\frac{T}{\varepsilon}}+O\left(\frac{d}{\sigma}T \varepsilon\log(1/\varepsilon)\log T\right)+|A|\cdot O\left(\frac{ \operatorname*{diam}(\mathbf{s})^{n}}{\varepsilon}+1\right)$ $\displaystyle\leq$ $\displaystyle\ O\left(\sqrt{\frac{T}{\varepsilon}}+\frac{d}{\sigma}T \varepsilon\log(1/\varepsilon)\log T+\frac{\operatorname*{diam}(\mathbf{s})^{n }}{\varepsilon}\right)$ $$

as required.
∎

Theorem 5.1 follows from Lemmas B.4 and B.7:

See 5.1

We then perform some arithmetic to get Theorem 5.2:

See 5.2

###### Proof.

We have

$$ $\displaystyle\operatorname*{\mathbb{E}}\left[R_{T}\right]\in$ $\displaystyle\ O\left(\frac{dL}{\sigma}T^{1-\frac{2n}{2n+1}-\frac{2}{2n+1}} \log(1/\varepsilon)\log T\right)$ $\displaystyle=$ $\displaystyle\ O\left(\frac{dL}{\sigma}T^{\frac{-1}{2n+1}}\log T\right)$ $$

and

$$ $\displaystyle\operatorname*{\mathbb{E}}[|Q_{T}|]\in$ $\displaystyle\ O\left(\sqrt{T^{1+\frac{2n}{2n+1}}}+\frac{d}{\sigma}T^{1-\frac{ -2n}{2n+1}}\log(T^{\frac{2n}{2n+1}})\log T+T^{\frac{2n}{2n+1}}\operatorname*{ diam}(\mathbf{s})^{n}\right)$ $\displaystyle=$ $\displaystyle\ O\left(T^{\frac{2n+0.5}{2n+1}}+\frac{d}{\sigma}T^{\frac{1}{2n+1 }}\log T+T^{\frac{2n}{2n+1}}\operatorname*{diam}(\mathbf{s})^{n}\right)$ $\displaystyle\leq$ $\displaystyle\ O\left(T^{\frac{4n+1}{4n+2}}\Big{(}\frac{d}{\sigma}\log T+ \operatorname*{diam}(\mathbf{s})^{n}\Big{)}\right)$ $$

∎

See 5.2.1

###### Proof.

Let $\xi$ be the event that Algorithm 1 exceeds $T^{\frac{4n+1.5}{4n+2}}(\frac{d}{\sigma}\log T+\operatorname*{diam}(\mathbf{s}
)^{n})$ queries. Noting that $|Q_{T}|\leq T$ always, we have

$$ $\displaystyle\operatorname*{\mathbb{E}}\big{[}|Q_{T}|\big{]}=$ $\displaystyle\ \Pr[\xi]\,\operatorname*{\mathbb{E}}\big{[}|Q_{T}|\mid\xi\big{] }+\Pr[\neg\xi]\,\operatorname*{\mathbb{E}}\big{[}|Q_{T}|\mid\neg\xi\big{]}$ $\displaystyle\geq$ $\displaystyle\ \Pr[\xi]\,T^{\frac{4n+1.5}{4n+2}}\left(\frac{d}{\sigma}\log T+ \operatorname*{diam}(\mathbf{s})^{n}\right)$ $$

Therefore by Theorem 5.2,

$$ $\Pr[\xi]\leq\frac{O\left(T^{\frac{4n+1}{4n+2}}\left(\frac{d}{\sigma}\log T+ \operatorname*{diam}(\mathbf{s})^{n}\right)\right)}{T^{\frac{4n+1.5}{4n+2}} \left(\frac{d}{\sigma}\log T+\operatorname*{diam}(\mathbf{s})^{n}\right)}\leq O \left(T^{\frac{-0.5}{4n+2}}\right)$ $$

If $\xi$ does not occur, then the regret bound from Theorem 5.2 holds. If not, we still have $R_{T}\leq 1$ unconditionally. Thus the regret of the modified version of Algorithm 1 satisfies

$$ $\displaystyle\operatorname*{\mathbb{E}}[R_{T}]\leq$ $\displaystyle\ \Pr[\xi]\,\operatorname*{\mathbb{E}}[R_{T}\mid\xi]+\Pr[\neg\xi] \,\operatorname*{\mathbb{E}}[R_{T}\mid\neg\xi]$ $\displaystyle\leq$ $\displaystyle\ O\left(T^{\frac{-0.5}{4n+2}}\right)\cdot 1+1\cdot O\left(\frac{ dL}{\sigma}T^{\frac{-1}{2n+1}}\log T\right)$ $\displaystyle\leq$ $\displaystyle\ O\left(\frac{dL}{\sigma}T^{\frac{-1}{8n+4}}\log T\right)$ $$

∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

###### Lemma B.4 .

###### Proof.

###### Definition B.1 .

###### Lemma B.5 (Theorem 14.2 in [ 40 ] ) .

###### Lemma B.6 (Jung’s Theorem [ 22 ] ) .

###### Lemma B.7 .

###### Proof.

###### Proof.

###### Proof.

### B.3 Adaptive adversaries

If $s_{t}$ is allowed to depend on the events of prior time steps, we say that the adversary is adaptive. In contrast, a non-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 $s_{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 5 of [] or Chapter 21 of []). However, [] 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 []) 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 this rest of Section B.3, lemma numbers refer to the numbering in [].

#### The importance of independent queries.

Recall from Section B.1 that [] allow two separate parameters $k$ and $\hat{k}$, which we unify for simplicity. Recall also that Lemma 3.5 refers to the variant of Hedge which queries with probability $p=\hat{k}/T=k/T$ independently on each time step (Algorithm 2. More precisely, on each time step $t$, the algorithm samples a Bernoulli random variable $X_{t}\sim\text{Ber}(p)$ and queries if $X_{t}=1$. The key idea is that $X_{t}$ is independent of events on previous time steps. Thus even conditioning on the history up to time $t$, for any for any random variable $Y_{t}$ we can write

$$ $\operatorname*{\mathbb{E}}[Y_{t}]=(1-p)\operatorname*{\mathbb{E}}[Y_{t}\mid X_ {t}=0]+p\operatorname*{\mathbb{E}}[Y_{t}\mid X_{t}=1]$ $$

This insight immediately extends Observation 3.3 to adaptive adversaries (with the minor modification that queries are now issued independently with probability $p$ on each time step instead of issuing $k$ uniformly distributed queries). Specifically, using the notation from [] where $i_{t}$ is the action chosen at time $t$, $i_{t}^{0}$ is the action chosen at time $t$ if a query is not issued, and $i_{t}^{*}$ is the optimal action at time $t$, we have

$$ $\operatorname*{\mathbb{E}}[\ell_{t}(i_{t})]=(1-p)\operatorname*{\mathbb{E}}[ \ell_{t}(i_{t}^{0})]+p\operatorname*{\mathbb{E}}[\ell_{t}(i_{t}^{*})]=\left(1- \frac{k}{T}\right)\operatorname*{\mathbb{E}}[\ell_{t}(i_{t}^{0})]+\frac{k}{T} \operatorname*{\mathbb{E}}[\ell_{t}(i_{t}^{*})]$ $$

The same logic applies to other statements like $\operatorname*{\mathbb{E}}[\hat{\ell}_{t}(i)\mid X_{\leq t-1},I_{\leq t-1}]=
\ell_{t}(i)-\ell_{t}(i_{t}^{*})$ and immediately extends those statements to adaptive adversaries as well.

#### Applying Observation 3.3.

The other tricky part of the proof is applying Observation 3.3 using a new loss function $\hat{\ell}$ defined by $\hat{\ell}_{t}=\frac{T}{\hat{k}}(\ell_{t}(i)-\ell_{t}(i_{t}^{*}))\mathbf{1}(X_
{t}=1)$. To do so, we must argue that standard Hedge run on $\hat{\ell}$ is the “counterpart without queries” of HedgeWithQueries. Specifically, both algorithms must have the same weight vectors on every time step, and the only difference should be that HedgeWithQueries takes the optimal action on each time step independently with probability $p$ (and otherwise behaves the same as standard Hedge). On time steps with $X_{t}=0$, standard Hedge observes $\hat{\ell}_{t}(i)=0$ for all actions $i$ and thus makes no updates, and HedgeWithQueries makes no updates by definition. On time steps with $X_{t}=1$, both algorithms perform the typical updates $w_{t+1}(i)=w_{t}(i)\cdot\exp(-\eta(\hat{\ell}_{t}(i)-\hat{\ell}_{t}(i_{t}^{*})))$. Thus the weight vectors are the same for both algorithms on every time step. Furthermore, HedgeWithQueries takes the optimal action at time $t$ iff $X_{t}=1$, which occurs independently with probability $p$ on each time step. Thus standard Hedge run on $\hat{\ell}$ is the “counterpart without queries” of HedgeWithQueries.

#### The rest of the proof.

The other elements of the proof of Lemma 3.5 are as follows:

- 1.
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 a $\hat{\ell}$.
- 3.
Arithmetic and rearranging terms.

The proof of Lemma 3.1 relies on simple arithmetic properties of the Hedge weights. Regardless of the adversary’s behavior, $\hat{\ell}$ is a 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.

## Appendix C Generalizing Theorem 5.2 to many actions

We use the standard “one versus rest” reduction (see, e.g., Chapter 29 of []). For each action $a$, we will learn a binary classifier which predicts whether action $a$ is the mentor’s action. Formally, for each $a\in A$, define the policy class $\Pi_{a}=\{\pi_{a}:\pi\in\Pi\text{ and }\pi_{a}(s)=\mathbf{1}(\pi(s)=a))\
\forall s\in S\}$. Informally, for each policy $\pi:S\to A$ in $\Pi$, there exists a policy $\pi_{a}:S\to\{0,1\}$ in $\Pi_{a}$ such that $\pi_{a}(s)=\mathbf{1}(\pi(s)=a)$ for all $s\in S$.

Algorithm 3 runs one copy of our binary-action algorithm Algorithm 1 for each action $a\in A$. At each time step $t$, the copy for action $a$ returns an action $b_{t}^{a}$, with $b_{t}^{a}=1$ indicating a belief that $a=\pi^{m}(s_{t})$ and $b_{t}^{a}=0$ indicating a belief that $a\neq\pi^{m}(s_{t})$. (Note that $b_{t}^{a}=\hat{a}$ is also possible, indicating that the mentor was queried.)

The key idea is that if $b_{t}^{a}$ is correct for each action $a$, there will be exactly one $a$ such that $b_{t}^{a}=1$, and specifically it will be $a=\pi^{m}(s_{t})$. Thus we are guaranteed to take the mentor’s action on such time steps. The analysis for Theorem 5.2 (specifically, Lemma B.1) bounds the number of time steps when a given copy of Algorithm 1 is incorrect, so by the union bound, the number of time steps where *any* copy is incorrect is $|A|$ times that bound. That in 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 3 is at most $|A|$ times the bound from Theorem 5.2. The result is the following theorem:

Figure: Algorithm 3 extends Algorithm 1 to many actions.

###### Theorem C.1 .

Assume $\pi^{m}\in\Pi$ where either (1) $\Pi_{a}$ has finite VC dimension $d$ and $\mathbf{s}$ is $\sigma$-smooth or (2) $\Pi_{a}$ has finite Littlestone dimension $d$ for all $a\in A$. Then for any $T\in\mathbb{N}$, Algorithm 3 with $T$ and $\varepsilon=T^{\frac{-2n}{2n+1}}$ satisfies

$$ $\displaystyle\operatorname*{\mathbb{E}}\left[R_{T}\right]\in$ $\displaystyle\ O\left(\frac{|A|dL}{\sigma}T^{\frac{-1}{2n+1}}\log T\right)$ $\displaystyle\operatorname*{\mathbb{E}}[|Q_{T}|]\in$ $\displaystyle\ O\left(|A|T^{\frac{4n+1}{4n+2}}\left(\frac{d}{\sigma}\log T+ \operatorname*{diam}(\mathbf{s})^{n}\right)\right)$ $$

We use the following terminology and notation in the proof of Theorem C.1:

- 1.
We refer to the copy of Algorithm 1 running on $\Pi_{a}$ as “copy $a$ of Algorithm 1”.
- 2.
Let $\pi_{t}^{a}$ and $X_{t}^{a}$ refer to the values of $\pi_{t}$ and $X_{t}$ for copy $a$ of Algorithm 1.
- 3.
Let $\pi^{ma}:S\to\{0,1\}$ be the policy defined by $\pi^{ma}(s)=\mathbf{1}(\pi^{m}(s_{t})=a)$. Note that querying the mentor tells the agent $\pi^{m}(s_{t})$, which allows the agent to compute $\pi^{ma}(s_{t})$: this is necessary when Algorithm 1 queries while running on some $\Pi_{a}$.
- 4.
Let $V_{T}^{a}=\{t\in[T]:b_{t}^{a}\neq\pi^{ma}(s_{t})\}$ be the set of time steps where $\pi_{t}^{a}$ does not correctly determine whether the mentor would take action $a$ and let $V_{T}=\{t\in[T]:a_{t}\neq\pi^{m}(s_{t})\}$ be the set of time steps where the agent’s action doesn’t match the mentor’s.

###### Lemma C.1 .

We have $|V_{T}|\leq\sum_{a\in A}|V_{T}^{a}|$.

###### Proof.

We claim that $V_{T}\subseteq\cup_{a\in A}V_{T}^{a}$. Suppose the opposite: then there exists $t\in V_{T}$ such that $b_{t}^{a}=\pi^{ma}(s_{t})$ for all $a\in A$. Since $\pi^{m}(s_{t})\in A$, there is exactly one $a\in A$ such that $\mathbf{1}(\pi^{m}(s_{t})=a)=\pi^{ma}(s_{t})=b_{t}^{a}=1$. Specifically, this holds for $a=\pi^{m}(s_{t})$. But then Algorithm 3 takes action $\min\{a\in A:b_{t}^{a}=1\}=\pi^{m}(s_{t})$, which contradicts $t\in V_{T}$. Therefore $V_{T}\subseteq\cup_{a\in A}V_{T}^{a}$, and applying the union bound completes the proof.
∎

###### Lemma C.2 .

For all $t\in[T]$, $\mu^{m}(s_{t})-\mu(s_{t},a_{t})\leq L\varepsilon^{1/n}$.

###### Proof.

The argument is similar to the proof of Lemma B.2. If $\mu^{m}(s_{t})\neq\mu(s_{t},a_{t})$, then $a_{t}=a$ for some $a\in A$ where $b_{t}^{a}=1$. Therefore copy $a$ of Algorithm 1 did not query at time $t$ and $\pi_{t}^{a}(s_{t})=1$. Let $(s^{\prime},a^{\prime})=\operatorname*{arg\,min}_{(s,a)\in X_{t}^{a}:\pi_{t}^{
a}(s_{t})=a}||s_{t}-s||$. Then $||s_{t}-s^{\prime}||\leq\varepsilon^{1/n}$ and $a^{\prime}=\pi_{t}^{a}(s_{t})=1$.

By construction of $X_{t}^{a}$, $a^{\prime}=\pi^{ma}(s^{\prime})$ so $\pi^{ma}(s^{\prime})=1$ which implies $\pi^{m}(s^{\prime})=a$. Then by the local generalization assumption,

$$ $\mu(s_{t},a_{t})=\mu(s_{t},a)=\mu(s_{t},\pi^{m}(s^{\prime}))\geq\mu^{m}(s_{t}) -L||s_{t}-s^{\prime}||\geq\mu^{m}(s_{t})-L\varepsilon^{1/n}$ $$

as required.
∎

See C.1

###### Proof.

Theorem 5.2 implies that each copy of Algorithm 1 makes $O\big{(}T^{\frac{4n+1}{4n+2}}\big{(}\frac{d}{\sigma}\log T+\operatorname*{diam
}(\mathbf{s})^{n}\big{)}\big{)}$ queries in expectation, so by linearity of expectation, the expected number of queries made by Algorithm 3 is $O\big{(}|A|T^{\frac{4n+1}{4n+2}}\big{(}\frac{d}{\sigma}\log T+\operatorname*{
diam}(\mathbf{s})^{n}\big{)}\big{)}$. Using the same argument as in the proof of Lemma B.7 (with Lemma C.2 replacing Lemma B.2), we get

$$ $\displaystyle R_{T}=$ $\displaystyle\ \prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{t=1}^{T}\mu(s_{t},a_{t})$ $\displaystyle\leq$ $\displaystyle\ \sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{ t},a_{t}))\Big{)}$ $\displaystyle\leq$ $\displaystyle\ |V_{T}|L\varepsilon^{1/n}$ $$

Then by Lemma C.1, $R_{T}\leq L\varepsilon^{1/n}\sum_{a\in A}|V_{T}^{a}|$. Taking the expectation and applying Lemma B.1 to each $V_{T}^{a}$ gives us

$$ $\operatorname*{\mathbb{E}}[R_{T}]\leq L\varepsilon^{1/n}\sum_{a\in A}O\left( \frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T\right)=O\left(|A|L \varepsilon^{1/n}\frac{d}{\sigma}T\varepsilon\log(1/\varepsilon)\log T\right)$ $$

as required.
∎

###### Theorem C.1 .

###### Lemma C.1 .

###### Proof.

###### Lemma C.2 .

###### Proof.

###### Proof.

## Appendix 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 most important aspect of our algorithm is that it can handle the class of thresholds on $[0,1]$, which is known to have infinite Littlestone dimension and thus be hard in the standard online learning model. (Example 21.4 in []).

Specifically, we assume a 1D state space and we allow the state sequence to be fully adversarial chosen. Instead of VC/Littlestone dimension, we consider the following notion of simplicity:

###### Definition D.1 .

Given a mentor policy $\pi^{m}$, partition the state space $S$ into intervals such that all states within each interval share the same mentor action. Let $\{S_{1},\dots,S_{k}\}$ be a partition that minimizes the number of intervals. We call each $S_{j}$ a *segment*. Let $f(\pi^{m})$ denote the number of segments in $\pi^{m}$.

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 $\mathbf{s}$. For example, if $\Pi$ is the class of thresholds on $[0,1]$, every $\pi\in\Pi$ 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.

We prove the following result:

###### Theorem D.2 .

For any $\mathbf{s}\in S^{T}$, any $\pi^{m}$ with $f(\pi^{m})\leq K$, and any function $g:\mathbb{N}\to\mathbb{N}$, Algorithm 4 makes at most $(\operatorname*{diam}(\mathbf{s})+4)g(T)$ queries and satisfies $R_{T}\leq\mfrac{2LKT}{g(T)^{2}}$.

Choosing $g(T)=T^{c}$ for $c\in(1/2,1)$ is sufficient to subconstant regret and sublinear queries:

###### Theorem D.3 .

For any $c\in(1/2,1)$, Algorithm 4 with $g(T)=T^{c}$ makes $O(T^{c}(\operatorname*{diam}(\mathbf{s})+1))$ queries and satisfies

$$ $\lim_{T\to\infty}\ \sup_{\mathbf{s}\in S^{T}}\ \sup_{\mu}\ \sup_{\pi^{m}:f(\pi ^{m})\leq K}\ R_{T}=0$ $$

Our algorithm does not need to know $L$ or the number of segments; it only needs to know $T$.

###### Definition D.1 .

###### Theorem D.2 .

###### Theorem D.3 .

### D.1 Intuition behind the algorithm

The algorithm maintains a set of buckets which partition the observed portion of the state space. Each bucket’s length determines the maximum loss in payoff we will allow from that subset of the state space. As long as the bucket contains a query from a prior time step, local generalization allows us to bound $\mu^{m}(s_{t})-\mu(s_{t},a_{t})$ based on the length of the bucket containing $s_{t}$. We always query if the bucket does not contain a prior query

The granularity of the buckets is controlled by a function $g$, with the initial buckets having length $1/g(T)$. Since we can expect one query per bucket, we need $g(T)\in 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 $\mu^{m}(s_{t})-O(\operatorname*{len}(B))$ whenever we choose not to query. We can endure a limited number of such payoffs, but if we never query again in that bucket, we may suffer $\Theta(T)$ such payoffs. Letting $\mu^{m}(s_{t})=1$ for simplicity, that would lead to $\prod_{t=1}^{T}\mu(s_{t},a_{t})\leq\big{(}1-\frac{1}{O(g(T))}\big{)}^{\Theta(T)}$, which converges to 0 (i.e., guaranteed catastrophe) when $g(T)\in o(T)$.

This failure mode suggests a natural countermeasure: if we start to suffer significant (potential) losses in the same bucket, then we should probably query there again. One way to structure these supplementary queries is by splitting the bucket in half when enough time steps have involved that bucket. It turns out that splitting after $T/g(T)$ time steps is a sweet spot.

Figure: Algorithm 4 achieves subconstant regret when the mentor’s policy has a bounded number of segments.

### D.2 Notation for the proof

We will use the following notation throughout the proof of Theorem D.2:

- •
Let $V_{T}=\{t\in[T]:\mu(s_{t},a_{t})<\mu^{m}(s_{t})\}$ be the set of time steps with a suboptimal payoff.
- •
Let $B_{t}$ be the bucket that is used on time step $t$ (as defined on line 14 of Algorithm 4).
- •
Let $d(B)$ be the *depth* of bucket $B$
–
Buckets created on line 9 are depth 0.
–
We refer to $B_{1},B_{2}$ created on line 26 as the children of the bucket $B$ defined on line 14.
–
If $B^{\prime}$ is the child of $B$, $d(B^{\prime})=d(B)+1$.
–
Note that $\operatorname*{len}(B)=\mfrac{1}{g(T)2^{d(B)}}$.
- •
Viewing the set of buckets are a binary tree defined by the “child” relation, we use the terms “ancestor” and ”descendant” in accordance with their standard tree definitions.
- •
Let $\mathcal{B}_{V}=\{B:\exists t\in V_{T}\text{ s.t. }B_{t}=B\}$ be the set of buckets that ever produced a suboptimal payoff.
- •
Let $\mathcal{B}_{V}^{\prime}=\{B\in\mathcal{B}_{V}:\text{no descendant of $B$ is
in $\mathcal{B}_{V}$}\}$.

### 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 a 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 suboptimality.
- 4.
As in the proof of Theorem 5.2, Lemma B.3 transforms the multiplicative objective into an additive form. Lemma D.5 bounds the additive objective using Lemmas D.2 and D.4.
- 5.
Combining Lemmas D.5 and B.3 bounds the regret (Lemma D.6).
- 6.
Theorem D.2 directly follows from Lemmas D.1 and D.6.

### D.4 Proof

###### Lemma D.1 .

Algorithm 4 performs at most $(\operatorname*{diam}(\mathbf{s})+4)g(T)$ 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 a bucket: from scratch (line 9), or by splitting an existing bucket (line 26).

Since depth 0 buckets overlap only at their boundaries, and each depth 0 bucket has length $1/g(T)$, at most $g(T)\max_{t,t^{\prime}\in[T]}|s_{t}-s_{t^{\prime}}|=g(T)\operatorname*{diam}(
\mathbf{s})$ depth 0 buckets are subsets of the interval $[\min_{t\in[T]}s_{t},\max_{t\in[T]}s_{t}]$. At most two depth 0 buckets are not subsets of that interval (one at each end), so the total number of depth 0 buckets is at most $g(T)\operatorname*{diam}(\mathbf{s})+2$.

We split a bucket $B$ when $n_{B}$ reaches $T/g(T)$, which creates two new buckets. Since each time step increments $n_{B}$ for a single bucket $B$, and there are a total of $T$ time steps, the total number of buckets created via splitting is at most

$$ $\frac{2T}{T/g(T)}=2g(T)$ $$

Therefore the total number of buckets ever in existence is $(\operatorname*{diam}(\mathbf{s})+2)g(T)+2\leq(\operatorname*{diam}(\mathbf{s}
)+4)g(T)$, so Algorithm 4 performs at most $(\operatorname*{diam}(\mathbf{s})+4)g(T)$ queries.
∎

###### Lemma D.2 .

For each $t\in[T]$, $\mu(s_{t},a_{t})\geq\mu^{m}(s_{t})-L\operatorname*{len}(B_{t})$.

###### Proof.

If we query the mentor at time $t$, $\mu(s_{t},a_{t})=\mu^{m}(s_{t})$. Thus assume we do not query the mentor at time $t$: then there exists $s^{\prime}\in B_{t}$ (as defined on line 21 of Algorithm 4) such that $a_{t}=\pi(s^{\prime})=\pi^{m}(s^{\prime})$. Since $s_{t}$ and $s^{\prime}$ are both in $B_{t}$, $|s_{t}-s^{\prime}|\leq\operatorname*{len}(B_{t})$. Then by the local generalization assumption,

$$ $\mu(s_{t},a_{t})=\mu(s_{t},\pi^{m}(s^{\prime}))\geq\mu^{m}(s_{t})-L||s_{t}-s^{ \prime}||\geq\mu^{m}(s_{t})-L\operatorname*{len}(B_{t})$ $$

as required.
∎

###### Lemma D.3 .

If $\pi^{m}$ has at most $K$ segments, $|\mathcal{B}_{V}^{\prime}|\leq K$.

###### Proof.

If two buckets $B$ and $B^{\prime}$ overlap by more than at a single point, one must be the descendant of the other. Thus by definition of $\mathcal{B}_{V}^{\prime}$, any two buckets in $\mathcal{B}_{V}^{\prime}$ overlap by at most a single point.

Now consider any $B\in\mathcal{B}_{V}^{\prime}$. By definition, there exists $t\in V_{T}$ such that $s_{t}\in B$. Then there exists $s^{\prime}\in B$ (as defined in Algorithm 4) such that $a_{t}=\pi(s^{\prime})=\pi^{m}(s^{\prime})$. Since $t\in V_{T}$, we have $\pi^{m}(s_{t})\neq a_{t}=\pi^{m}(s^{\prime})$. Thus $s_{t}$ and $s^{\prime}$ are in different segments; let $S_{B}$ be the segment containing $\min(s_{t},s^{\prime})$. Then $\min(s_{t},s^{\prime})\leq\max(S_{B})<\max(s_{t},s^{\prime})\leq\max(B)$.

Consider any $B,B^{\prime}\in\mathcal{B}_{V}^{\prime}$ with $B\neq B^{\prime}$ and WLOG assume $\max(B)<\max(B^{\prime})$. Then $\max(S_{B})<\max(B)\leq\max(S_{B^{\prime}})$, so $S_{B}\neq S_{B^{\prime}}$. Thus the number of segments in $\pi^{m}$ is at least $\mathcal{B}_{V}^{\prime}$. Since the number of segments in $\pi^{m}$ is at most $K$, we must have $|\mathcal{B}_{V}^{\prime}|\leq K$.
∎

###### Lemma D.4 .

We have $\sum\limits_{t\in V_{T}}\operatorname*{len}(B_{t})\leq\mfrac{2KT}{g(T)^{2}}$.

###### Proof.

For every $t\in V_{T}$, we have $B_{t}=B$ for some $B\in\mathcal{B}_{V}$, so

$$ $\sum_{t\in V_{T}}\operatorname*{len}(B_{t})=\sum_{B\in\mathcal{B}_{V}}\ \sum_{ t\in V_{T}:B=B_{t}}\operatorname*{len}(B_{t})$ $$

Next, observe that every $B\in\mathcal{B}_{V}\setminus\mathcal{B}_{V}^{\prime}$ must have a descendent in $\mathcal{B}_{V}^{\prime}$: otherwise we would have $B\in\mathcal{B}_{V}^{\prime}$. Let $\mathcal{A}(B)$ denote the set of ancestors of $B$, plus $B$ itself. Then we can write

$$ $\displaystyle\sum_{t\in V_{T}}$ $\displaystyle\ \operatorname*{len}(B_{t})\leq\sum_{B^{\prime}\in\mathcal{B}_{V }^{\prime}}\ \sum_{B\in\mathcal{A}(B^{\prime})}\ \sum_{t\in V_{T}:B=B_{t}} \operatorname*{len}(B_{t})$ $\displaystyle=$ $\displaystyle\ \sum_{B^{\prime}\in\mathcal{B}_{V}^{\prime}}\ \sum_{B\in \mathcal{A}(B^{\prime})}\ |\{t\in V_{T}:B=B_{t}\}|\cdot\operatorname*{len}(B_{ t})$ $$

For any bucket $B$, the number of time steps $t$ with $B=B_{t}$ is at most $T/g(T)$. Also recall that $\operatorname*{len}(B)=\mfrac{1}{g(T)2^{d(B)}}$. Therefore

$$ $\displaystyle\sum_{B\in\mathcal{A}(B^{\prime})}$ $\displaystyle\ \frac{|\{t\in V_{T}:B=B_{t}\}|}{g(T)2^{d(B)}}\leq\frac{T}{g(T)^ {2}}\sum_{B\in\mathcal{A}(B^{\prime})}\ \frac{1}{2^{d(B)}}$ $\displaystyle=$ $\displaystyle\ \frac{T}{g(T)^{2}}\sum_{d=0}^{d(B^{\prime})}\frac{1}{2^{d}}\leq \frac{T}{g(T)^{2}}\sum_{d=0}^{\infty}\frac{1}{2^{d}}=\frac{2T}{g(T)^{2}}$ $$

Then by Lemma D.3,

$$ $\sum_{t\in V_{T}}\operatorname*{len}(B_{t})\leq\sum_{B^{\prime}\in\mathcal{B}_ {V}^{\prime}}\frac{2T}{g(T)^{2}}=\frac{2T|\mathcal{B}_{V}^{\prime}|}{g(T)^{2}} \leq\frac{2KT}{g(T)^{2}}$ $$

as claimed.
∎

###### Lemma D.5 .

Under the conditions of Theorem D.2, Algorithm 4 satisfies

$$ $\sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\Big{ )}\leq\frac{2LKT}{g(T)^{2}}$ $$

###### Proof.

For $t\not\in V_{T}$ we have $\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))=\mu^{m}(s_{t})$ by definition, and Lemma D.2 implies that $\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\geq L\operatorname*{len}(B_{t})$ for all $t\in[T]$. Thus

$$ $\sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\Big{ )}\leq\sum_{t\in V_{T}}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{ t}))\Big{)}\leq L\sum_{t\in V_{T}}\operatorname*{len}(B_{t})$ $$

Then by Lemma D.4,

$$ $\sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\Big{ )}\leq\frac{2LKT}{g(T)^{2}}$ $$

as required.
∎

###### Lemma D.6 .

Under the conditions of Theorem D.2, Algorithm 4 satisfies $R_{T}\leq\frac{2LKT}{g(T)^{2}}$.

###### Proof.

Let $x_{t}=\mu^{m}(s_{t})$ and $y_{t}=\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))$ for all $t\in[T]$. Then by Lemma B.3,

$$ $\displaystyle\prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{t=1}^{T}\min(\mu^{m}(s_{t}), \mu(s_{t},a_{t}))\leq$ $\displaystyle\ \sum_{t=1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{ t},a_{t}))\Big{)}$ $$

Since $\mu(s_{t},a_{t})\geq\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))$ for all $t\in[T]$, we have

$$ $R_{T}=\prod_{t=1}^{T}\mu^{m}(s_{t})-\prod_{t=1}^{T}\mu(s_{t},a_{t})\leq\sum_{t =1}^{T}\Big{(}\mu^{m}(s_{t})-\min(\mu^{m}(s_{t}),\mu(s_{t},a_{t}))\Big{)}$ $$

Applying Lemma D.5 completes the proof.
∎

Theorem D.2 follows from Lemma D.1 and Lemma D.6.

###### Lemma D.1 .

###### Proof.

###### Lemma D.2 .

###### Proof.

###### Lemma D.3 .

###### Proof.

###### Lemma D.4 .

###### Proof.

###### Lemma D.5 .

###### Proof.

###### Lemma D.6 .

###### Proof.

## Appendix E Other proofs

###### Proposition E.1 .

Suppose $\mu$ is $L$-Lipschitz continuous and $\pi^{m}$ is optimal, i.e., $\mu(s,\pi^{m}(s))=\max_{a\in A}\mu(s,a)$ for all $s\in S$. Then $\pi^{m}$ satisfies local generalization with constant $2L$.

###### Proof.

For any $s,s^{\prime}\in S$, we have

$$ $\displaystyle\mu(s,\pi^{m}(s^{\prime}))\geq$ $\displaystyle\ \mu(s^{\prime},\pi^{m}(s^{\prime}))-L||s-s^{\prime}||$ (Lipschitz continuity of $\mu$ ) $\displaystyle\geq$ $\displaystyle\ \mu(s^{\prime},\pi^{m}(s))-L||s-s^{\prime}||$ ( $\pi^{m}$ is optimal for $s^{\prime}$ ) $\displaystyle\geq$ $\displaystyle\ \mu(s,\pi^{m}(s))-2L||s-s^{\prime}||$ (Lipschitz continuity of $\mu$ again) $\displaystyle=$ $\displaystyle\ \mu^{m}(s)-2L||s-s^{\prime}||$ (Definition of $\mu^{m}(s)$ ) $$

Since $\pi^{m}$ is optimal for $s$, we have

$$ $\mu^{m}(s)+2L||s-s^{\prime}||\geq\mu^{m}(s)\geq\mu(s,\pi^{m}(s^{\prime}))$ $$

Thus $-2L||s-s^{\prime}||\leq\mu(s,\pi^{m}(s^{\prime}))-\mu^{m}(s)\leq 2L||s-s^{
\prime}||$. This is equivalent to $|\mu(s,\pi^{m}(s^{\prime}))-\mu^{m}(s)|\leq 2L||s-s^{\prime}||$, completing the proof.

∎

###### Proposition E.1 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: - (1) Are there other impossibility results besides Theorem 4.1, especially in the Bayesian regime? If the submission provides the first impossibility result, that is a contribution, too. If there are other impossibility results, we should list them and compare them with Theorem 4.1. 
- (2) Is the multiplicative objective really a good choice? For example, consider the following two payoff sequences: (0, 0.999, 0.999, 0.999) and (0.1, 0.1, 0.1, 0.1). The total payoff (multiplicative) of the first sequence is 0 and is smaller than that of the second one. But intuitively, the second sequence may have a better chance of avoiding a disaster.
soundness: 3
strengths: - A non-Bayesian approach to address the online disaster avoidance problem.
- The analysis simultaneously controls the regret and the query frequency.
- A novel packing argument is developed to bound the query complexity.
summary: The submission studies an online disaster avoidance problem. The learning agent is allowed to query the mentor to acquire information to avoid disaster. To circumvent the tractability issue of Bayesian methods, a hedge-based algorithm is proposed under an additional assumption called “local generalization.” Also, unlike conventional online learning, the regret is defined in a multiplicative way, and the proven regret bound (Theorem 5.2) is subconstant. Besides the positive result, the submission also shows an impossibility result (Theorem 4.1) in a general case.
weaknesses: - (1) It seems to be too advantageous for the learning agent to be able to query the optimal policy (i.e., the mentor), given that a local generalization assumption has been made for exploitation. Practically speaking, if querying is allowed, the learning agent should also have to find out who the optimal target to query in the policy class is.
- (2) The argument (lines 508–514) for the novel packing (line 460) is not clear enough. An explanation of the difficulty and the technical contribution is needed.
- (3) There are confusing sentences hindering the readability. These are the sentences in line 126 (As a corollary, …) and line 134 (We initially …).

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: In Sec 3, Q_T is defined to be a deterministic quantity of the algorithm. But all the bounds are in terms of E[Q_T].
soundness: 3
strengths: I believe it makes much sense to formulate "asking for help" in terms of query complexity. It is clearly of importance to understand how access to expert advice helps online learners. The proposed algorithm, though looks standard, may also be of techical interest,
summary: This paper proposes a new model of online learning, with the performance measured in terms of the product of the per-step value (probabilities). Under this new setting, the authors provide both difficulty results and an algorithm for VC/Littlestone classes.
weaknesses: I am a little bit skeptical of the formulation of regret. 

1. The probabilistic interpretation of the product $\prod_{t=1}^T \mu(s_t,a_t)$ is unclear. Given the observed sequence of $(s_1,a_1,...,s_T,a_T)$, the product is the probability of avoiding catastrophe only if the catastrophe at step t does not affect the s_{t+1}.

2. For the regret to be non-trivial, it is necessary that $\sum_{t=1}^T -\log \mu^m(s_t)$ to be bounded by a constant as T tends to infinity. I believe this is a very strong assumption on the mentor, and the hence the upper bound can be trivial for most scenarios. It is possible to consider a less restrictive setting? The hardness result may not be an excuse here.

3. It looks possible to take a logarithm and convert this problem to the standard no-regret learning setting, with the goal of achieving sub-constant regret. Given that the mentor needs to achieve constant loss, this goal seems to be achievable. It would be beneficial to include a discussion on why it is infeasible.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: Is the local generalization assumption fundamental? See comments above
soundness: 3
strengths: This paper makes a reasonable contribution to the online learning literature by proposing what is, to my knowledge, a novel setting and problem formulation. I believe the upper and lower bounds the authors provide are novel and do not necessarily follow from existing work. I also found the paper to be generally well written and easy to follow.
summary: This paper considers a new variant of the classical online learning setting in which the aim is to avoid "catastrophe" relative to a mentor policy \pi^m. Concretely, letting \mu denote the reward, the aim is to choose a sequence of actions a_1, ..., a_T based on a sequence of covariates s_1, ..., s_T such that the following notion of regret is small:

\prod_{t=1}^{T}\mu(s_t, pi^m(s_t)) - \prod_{t=1}^{T}\mu(s_t, a_t).

That is, compared to the standard online learning formulation (e.g., Cesa-Bianchi and Lugosi), which considers regret of the form \sum_{t=1}^{T}\mu(s_t, pi^m(s_t)) - \sum_{t=1}^{T}\mu(s_t, a_t), we care about the product of rewards instead of the sum of rewards. This reflects the fact that we are averse to catastrophe, since a very small reward at any round $t$ can completely ruin our prospects of achieving low regret.

Beyond the differences above, the setting the authors consider also has the feature that the reward is never observed. Rather, the learner can choose to query the mentor at each round $t$ and observe pi^m(s_t). The aim is to ensure the regret and the number of mentor queries is sublinear in $T$.

The authors provide the following results:
* When (1) the mentor satisfies a "local generalization" property related to Lipschitzness and (2) their policy belongs to a class \Pi which is either a Littlestone class or a VC class (with the additional assumption that outcomes are "smooth") it is possible to achieve sublinear regret and expert queries through a variant of the exponential weights algorithm.

* Without the Littlestone or VC assumptions, sublinear regret is impossible, even under the local generalization assumption.
weaknesses: The main drawbacks preventing me from giving a higher score are as follows:

* While the problem formulation is loosely inspired by literature on AI risk, it is unclear whether the new problem formulation the authors provide actually has implications for this literature. Spelling out potential connections and implications of the results seems important, as otherwise I am worried the impact might be rather limited (e.g., a niche setting of interest to online learning experts, but not necessarily of interesting outside the core theory community). Overall, if there are interesting consequences of algorithic results here it would be great to highlight this.

* Given that the main contribution of the paper is to introduce a new problem formulation, it seems important to justify all of the assumptions and argue that they are fundamental. Here, I am somewhat concerned about the local generalization assumption, which seems a bit arbitrary and inelegant. While I can believe that some assumption of this type might be required, it is not clear that this specific one is fundamental. In particular, I do not like that the assumption requires that $s$ lies in Euclidean space, which feels quite arbitrary and not really in the spirit of online learning (which is generally agnostic to the space of covariates, and depends on it only through assumptions on the class \Pi itself). Nailing down what is the right notion of local generalization would definitely strengthen the paper.

-----

Some minor comments:
* The authors may want to compare with the literature on online learning with the logarithmic loss. E.g., if we do standard online learning with additive regret, but choose \log(\mu(s_t, a)) as the reward, then a standard additive regret bound of the form \sum_t reward(s_t, \pi^m) - reward(s_t, a_t) \leq Reg implies that \log(\prod \mu(s_t, pi^m)/\mu(s_t, a_t)) \leq Reg. This is a different guarantee from what the authors provide, but has a similar flavor, so it might be interesting to compare.

* This setting also has an imitation learning flavor, so it would be good to add some discussion on how it connects to the IL literature.

* The term "state" is a bit confusing/misleading since this is a standard online learning setting as opposed to RL (i.e., we just take the states as given, and are not interesting in counterfactuals wrt how they might have evolved if we had acted differently). Calling them "contexts" or "covariates" would be more clear.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Could you please discuss on the second weakness? Which are the main advantages of your setting w.r.t. the one described above?
soundness: 3
strengths: I believe that the setting proposed in this work is of interest from a theoretical perspective.
Indeed, to the best of my knowledge, the framework is novel, and as pointed out in the work, it presents some peculiar theoretical challenges. The results seem correct and reasonable to me. Finally, the authors put much effort into explaining the main ideas behind the theoretical results.
summary: This paper proposes a novel online learning framework in which the learner aims to minimize the catastrophe probability, that is, avoid choosing catastrophic actions. In order to do that, it is assumed the possibility to query a mentor (the baseline) at time $t\in[T]$, which returns the mentor's action associated with the current state $s_t$. Moreover, local generalization of the mentor policy is assumed (namely, a sort of continuity assumption between states given the mentor policy). The performance metrics used to evaluate the online algorithms are the regret between the product of the avoiding catastrophe probabilities attained by the learner and the mentor and the number of queries performed. First, the authors show the impossibility of learning in the general setting. Thus, the authors focus on the case of finite VC or Littlestone dimension. In such a setting, the authors provide a simple hedge-kind of algorithm that attains sub constant regret and a sublinear number of queries to the mentor during the learning dynamic.
weaknesses: To me, there are two main weaknesses in this work. The first one is the lack of particular algorithmic novelty. The algorithm proposed is a clear, simple adaptation of hedge. Moreover, this work strongly relies on many different results from statistical learning theory and online learning (see Section 5.2, where all the results belong to existing works). This is indeed not a sufficient reason for rejection, but somehow, it worsens the contribution of the work. 

The second weakness concerns the practical relevance of the setting. While I agree that the setting is interesting from a theoretical perspective, it is not clear to me why it should be of interest in real-world scenarios. Specifically, the authors clearly state that this setting is of practical relevance since, unlike standard online learning, it allows for the avoidance of catastrophic actions. In contrast, the standard exploration-exploitation trade-off requires, in general, to try all the possible actions, even really dangerous ones. Nevertheless, there exist many works on learning in the presence of **unknown** constraints which exactly tackle the problem specified above. While without further assumptions, it is not possible to satisfy unknown constraints in every round, it is sufficient to require a feasible solution in input, to be simultaneously no-regret w.r.t. the rewards and avoiding possible dangerous actions with high probability (see, e.g., [Liu et al. 2021], [Stradi et al. 2024] for online learning in MDPs). Moreover, notice that those papers do not need any query to the mentor, and as previously specified, do not focus only on avoiding bad actions, but they maximize specific unknown rewards functions. Finally, while their regret is sublinear in $T$, their regret definition seems to be much stronger since the baseline is the optimal solution and not a general mentor policy.


[Liu et al., 2021] "Learning policies with zero or bounded constraint violation for constrained mdps."

[Stradi et al. 2024] "Learning Adversarial MDPs with Stochastic Hard Constraints"

Meta-review: This is a borderline paper with potential. However, there is also criticism and there is a feeling that the paper is not quite there yet. This concerns, in particular, links to the AI risk literature and, more importantly, the local generalization assumption. I believe that the paper needs more work before being ready for publication.

Decision: Reject