Online Conformal Prediction Beyond Feedback

Online Conformal Prediction Beyond Feedback Joar Skalse1∗ , Edoardo Pona1 , Osvaldo Simeone2 , Nicola Paoletti1 1

King’s College London Northeastern University London joar.skalse@kcl.ac.uk, edoardo.1.pona@kcl.ac.uk, o.simeone@nulondon.ac.uk, nicola.paoletti@kcl.ac.uk 2

arXiv:2608.07139v1 [cs.LG] 7 Aug 2026

Abstract Uncertainty quantification is essential when deploying machine learning models in safety-critical applications. Online conformal prediction (OCP) provides theoretically principled uncertainty quantification for arbitrary black-box classifiers and non-i.i.d. data streams by constructing prediction sets that are guaranteed to contain the true label at a user-specified frequency. OCP usually updates prediction sets using feedback from previously deployed predictions. We instead study an OCP setting beyond feedback: on each round, the learner can either output a prediction set or query the correct label, but not both. Thus, no deployed prediction is ever evaluated directly. We reduce this problem to a partial monitoring game in which prediction actions return no observation and a separate query action reveals the label. The reward function is constructed in a way that encourages the learner to output small prediction sets while ensuring that the correct label is covered with a sufficiently high probability. To solve this game, we develop OCP with queries (OCPQ) by adapting the label efficient forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004) to our setting. For any black box classifier and any (non-i.i.d.) oblivious data stream of length T , OCPQ has O(T 2/3 ) expected regret and expected coverage at least β −O(T −1/3 ) for a userdefined β, while querying only an expected T −1/3 fraction of rounds. This provides coverage comparable to bandit-based OCP methods while requiring no feedback from deployed prediction sets. Experiments on real-world datasets further demonstrate the effectiveness of our approach.

Introduction Background and Motivation Uncertainty quantification is important for decision-making, especially in safety-critical domains. Conformal prediction is a theoretically principled framework for uncertainty quantification of black-box models, such as neural networks (see, e.g., Angelopoulos and Bates 2022; Vovk, Gammerman, and Shafer 2022). Typically, a conformal prediction method takes an arbitrary pre-trained function approximator and translates its outputs into sets of outputs, such that the true label is provably guaranteed to be contained within this set with some user-specified probability or frequency, and where the prediction sets are otherwise ideally as small as possible. These methods allow us to derive formal guarantees without ∗

Corresponding author.

making any assumptions about the data distribution or the underlying black-box model, though a more accurate model yields smaller prediction sets. The prediction sets act as confidence intervals that can be used to optimize the policy of a risk-averse agent (Kiyani et al. 2025; Simeone 2026). In online conformal prediction (OCP), we assume that the data arrives sequentially, and no assumptions are made about the exchangeability of calibration and test data. OCP methods adopt a worst-case, per-sequence, performance objective, and can provide principled uncertainty quantification for applications including large language models (e.g., Lee, Jung, and Park 2026; Rubashevskii et al. 2026), distributed systems (e.g., Zhu et al. 2025), telecommunications networks (e.g., Cohen et al. 2023), and world models for robot systems (e.g., Lindemann et al. 2023; Zhao et al. 2025). Existing OCP methods typically assume that the correct labels can be obtained after a set prediction is issued — in other words, they assume that the algorithm gets feedback. Feedback may potentially be partial or delayed (e.g., Wang, Zecchin, and Simeone 2025, 2026, etc), but it always refers to decisions made by the algorithm. This feedback is leveraged to compensate for past mistakes: miscoverage events are compensated by increasing the size of future prediction sets, while coverage events yield smaller future sets. While obtaining feedback is feasible in many contexts, there are also many potential applications of OCP where this requirement is prohibitive. For example, consider a latent probe for a large language model (LLM) that must be designed to classify the LLM’s input into a number of safetyrelevant categories (as, e.g., Chia, Wong, and Pan 2025; McKenzie et al. 2026; Jiao et al. 2026; Zhao et al. 2026; Pona et al. 2026, etc). In this case, if the probe could reliably access the correct labels, then there would be little reason to design the probe in the first place. However, inputs on which the probe abstains may be deferred to a human or a stronger system, and their labels may later become available. Labels are not obtained for inputs on which the probe makes a deployed decision. This is beyond feedback in the usual OCP sense: observations concern queried rounds, not past predictions. Methods that require a coverage signal from deployed prediction sets cannot be applied directly. In this paper, we introduce Online Conformal Prediction with Queries (OCPQ), a new OCP method for this beyond feedback protocol. We tackle the problem in two steps. First,

we reduce it to a finite partial monitoring game whose prediction actions return no observation and whose query action reveals the outcome. Second, we solve the resulting game using an adapted version of the label efficient exponentially weighted forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004). In this adaptation, experts correspond to conformal prediction thresholds and a query replaces, rather than follows, a prediction. Random queries provide unbiased estimates of the cumulative rewards of all thresholds, including thresholds that were not deployed. For any black box classifier, any data stream of length T , and any user-defined β ∈ [0, 1], OCPQ guarantees that the expected coverage rate pcover satisfies E[pcover ] ≥ β − O(T −1/3 ), while querying an expected T −1/3 fraction of the rounds. OCPQ thus obtains provable finite horizon guarantees using very little data, and without ever observing whether any deployed prediction set covered its label.

Problem Formulation We focus on a standard online prediction setting operating along a discrete time index t = 1, 2, . . . , T , in which the input xt belongs to an input space X and the correct label yt belongs to an output space Y. We assume that Y is finite, but X need not be finite.1 We adopt an adversarial formulation in which the sequence z

T

= ⟨(xt , yt )⟩Tt=1 ∈ (X × Y)T ,

z T , while not offering any direct feedback signal on the past predictions of the learner. The learner selects action at based on a generally stochastic policy π : H × X → ∆(A), where ∆(A) is the set of all probability distributions over the action space A and H ⊂ (X × A × Ω)⋆ is the set of all histories hn = ⟨(xt , at , ωt )⟩nt=1 ,

(3)

where ωt is the observation at time t. The learner has access to a classifier C : X → ∆(Y), which it can use to construct the prediction sets St . We use pC (y | x) to denote the probability that C assigns to label y given input x. Following existing OCP methods, we assume that the learner selects a prediction threshold mt ∈ [0, 1], and then let the prediction set St for input xt be obtained as the superlevel set ΓC (xt , mt ) defined by ΓC (xt , mt ) = {y ∈ Y | pC (y | xt ) ≥ max pC (y ⋆ | xt ) − mt }, ⋆ y ∈Y

(4)

where the choice of mt determines how conservative the learner is: if mt = 1 then Γ(xt , mt ) = Y, (i.e., it is the trivial set of all labels), and if mt = 0 then Γ(xt , mt ) includes only the most likely label (as judged by C).2 Given a data stream z T and an action sequence aT = ⟨a1 . . . aT ⟩, we use Q to denote the total number of queries, Q=

(1)

T X

1{at = query}.

(5)

t=1

with zt = (xt , yt ) for t = 1, . . . , T , is selected in advance, possibly in an adversarial way (i.e., we have an oblivious adversary). On each round t, the learner observes the input xt and returns an action at ∈ A = P(Y) ∪ {query} as  St ⊆ Y (produce a prediction set) at = (2) query (request to observe yt ). After selecting an action, the learner receives an observation ωt ∈ Ω = Y ∪ {⊥}, where ωt = yt if at = query, and otherwise ωt is a null observation ⊥. Note that this means that the learner never obtains feedback about the true label yt , or even about the coverage event {yt ∈ St }, on rounds in which it produces a prediction set St . In this way, the output yt can only be observed on time steps at which the learner declined to make a prediction. This marks a key shift compared with existing formulations of OCP, which assume the availability of feedback about the prediction sets produced by the learner (though this feedback may be partial or delayed, see the Related Work section). This information is leveraged by the learner to compensate for past errors when designing future prediction sets, ensuring long-term risk guarantees. In our setting, however, such compensation is not possible, as the only available outputs yt provide information solely about the pre-selected sequence

We are interested in controlling the coverage rate pcover =

The assumption that Y is finite is mostly made out of convenience, and can be lifted. For details, see the Appendix.

(6)

i.e., the proportion of the rounds on which a prediction set St is produced and the true label yt is contained in St . By this definition, a query counts as a miscoverage event, and so the learner is incentivised to keep the total number of queries low in order to control pcover . While coverage can be trivially controlled by choosing the full set St = Y on every round, prediction sets need to be informative, i.e., as small as possible. Thus, we also consider the average size of St , also known as the inefficiency I: PT 1{at ̸= query} · |St | I = t=1 . (7) PT t=1 1{at ̸= query} Note that if the actions are sampled from a stochastic policy, then Q, pcover , and I are all random variables. In summary, we wish to simultaneously control the expected coverage rate and the expected query rate, regardless of which data stream the adversary picks, while keeping the size of prediction sets as small as possible. 2

1

T 1 X · 1{at ̸= query} · 1{yt ∈ St }, T t=1

In (O)CP literature, the inclusion condition is often expressed in terms of a score function: s(xt , y) ≤ mt . We can retrieve this form by setting s(xt , y) = maxy⋆ ∈Y pC (y ⋆ | xt ) − pC (y | xt ).

Related Work Table 1 compares our method to some of the most relevant OCP methods in terms of feedback models and guarantees. OCP With Feedback Most OCP methods observe the label (e.g., Gibbs and Candès 2021; Bhatnagar et al. 2023; Angelopoulos, Barber, and Bates 2024a,b, etc) or a coverage signal (Wang and Qiao 2024; Gollapudi et al. 2026) after issuing a prediction set. Some OCP methods take semi-bandit feedback, meaning that they observe the label only if the prediction set has coverage (Ge, Bastani, and Bastani 2025; Yang, Kim, and Park 2026; Lee, Jung, and Park 2026). Wang, Zecchin, and Simeone (2025) allows feedback to arrive intermittently with exogenous probabilities pt , while Wang, Zecchin, and Simeone (2026) study binary coverage feedback that may be adversarially corrupted. These methods reduce the amount or reliability of feedback, but still update from observations associated with deployed predictions. Bandit Approaches to OCP Several previous works have shown that OCP can be reduced to a multi-armed bandit problem (Wang and Qiao 2024; Ge, Bastani, and Bastani 2025; Yang, Kim, and Park 2026), leading to both coverage and regret guarantees (Ramalingam, Kiyani, and Roth 2025). In these works, however, the deployed action still produces an observation, either a correctness signal or a label on covered rounds. In contrast, OCPQ receives no information from deployed predictions. It observes labels only through separate query actions, used on an expected T −1/3 fraction of rounds, while obtaining a O(T −1/3 ) coverage deficit. Queries and Label-Efficient Adversarial Learning Zhao et al. (2025) combine intermittent observations with active queries in OCP for interactive imitation learning. Our setting is similar but uses a fixed query probability, and does not assume the existence of any intermittent observations. The learning rule underlying OCPQ is an adaptation of the label efficient exponentially weighted forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004), which queries outcomes at random and updates all expert weights using inverse probability estimates. Our contribution is thus not a new generic adversarial learning rule, but rather, the use of label efficient learning to obtain an OCP method beyond feedback, together with the threshold reward, the query-only estimator, and the regret to coverage result. General partial monitoring game algorithms (e.g., Rustichini 1999; Lattimore and Szepesvari 2018, 2019) can also be applied in this setting, an option which we discuss in the Appendix. Contributions • We formulate OCP beyond feedback, where the learner must choose between predicting and querying, and therefore never observes the outcome of a deployed prediction. • We reduce OCP beyond feedback to a partial monitoring game, and adapt the label efficient adversarial learning technique of Cesa-Bianchi, Lugosi, and Stoltz (2004) to solve the resulting game. • We prove finite horizon expected regret O(T 2/3 ) and expected coverage at least β − O(T −1/3 ) using an expected

query rate of T −1/3 . We also give a high probability regret bound and a high-probability coverage bound. • We evaluate the method under distribution shift and on adversarially rewritten safety prompts, showing that the coverage and efficiency can be controlled in practice.

Online Conformal Prediction With Queries Partial Monitoring Game Formulation We cast the beyond feedback OCP problem as a finite partial monitoring game, a generalization of the adversarial multiarmed bandit framework in which the feedback generated by an action need not reveal its reward. The full game formulation is given in the Appendix. The “arms” are a finite set of prediction thresholds M ⊂ [0, 1], where action m ∈ M returns the prediction set ΓC (xt , m) (Equation 4), together with the additional action query. For each observed input xt and hidden label yt , these actions induce the reward vector defined in Definition 1: queries get no reward, and a threshold is rewarded according to whether its prediction set contains yt and how tight the threshold is. The best fixed prediction action in this game therefore corresponds to the best fixed conformal threshold over the full data stream. The feedback structure captures the key difficulty of OCP beyond feedback. Prediction actions reveal neither the label nor their coverage or reward. By contrast, the action query returns no prediction set and has zero reward, but reveals yt . This allows the learner to reconstruct the reward R(m, t) for every threshold m ∈ M . As shown in the Appendix, this problem belongs to the hard class of partial monitoring games, for which the characteristic regret rate is T 2/3 .

The OCPQ Algorithm Having reduced our OCP settings to the partial monitoring game above, we solve the game using Algorithm 1. The algorithm adapts the label efficient exponentially weighted forecaster rule of Cesa-Bianchi, Lugosi, and Stoltz (2004). The main protocol adaptation, in addition to applying this approach to OCP for the first time, is the estimated reward update, since labels are observed only when the learner takes this separate action. The method takes the following inputs: • a classifier C : X → ∆(Y), • a finite set of prediction thresholds M ⊂ [0, 1], such that 0 ∈ M and 1 ∈ M , • a query rate ϵ ∈ (0, 1), • a baseline parameter β ∈ (0, 1], • a learning rate η ∈ (0, 1], and • a time horizon T ∈ N. The parameter β is used to control the trade-off between coverage and efficiency, and can be used to derive a lower bound on the coverage rate (c.f. Corollary 1). Theorem 1 in the next section gives guidance on how to set the values of ϵ and η based on T . C can be any black-box classifier, including a neural network. On round t, OCPQ makes a query with probability ϵ (line 6). A query returns yt but produces no prediction set. Otherwise, the method samples a threshold mt from the exponentially weighted distribution (lines 11 and 12) and outputs

Method

Data Model

Feedback

Main Guarantees

Wang and Qiao (2024)

stochastic/iid

bandit feedback at every round

sublinear regret, finite-time coverage

Ge, Bastani, and Bastani (2025)

stochastic/iid

semi-bandit feedback at every round

sublinear regret

Yang, Kim, and Park (2026)

adversarial

semi-bandit feedback at every round

sublinear regret, finite-time coverage

Wang, Zecchin, and Simeone (2025)

adversarial

intermittent miscoverage feedback

sublinear regret, finite-time coverage

Zhao et al. (2025)

adversarial

intermittent miscoverage feedback

finite-sample coverage

OCPQ (ours)

adversarial

true label revealed with fixed probability, but no feedback on deployed prediction

sublinear regret, finite-time coverage

Table 1: Feedback models and guarantees of OCPQ compared to related OCP methods. Bandit feedback: the learner proposes a label y and receives feedback 1(yt = y). Semi-bandit feedback: the learner proposes a set S and receives feedback yt if 1(yt ∈ S). Intermittent miscoverage feedback: the learner receives only 1(yt ∈ S) as feedback, not on every round, but with a positive probability. Regret is defined w.r.t. an optimal fixed threshold for the prediction region. Regret bounds are finite-sample. A finite-time coverage guarantee proves a finite-sample bound on the coverage rate. Algorithm 1: OCP With Queries 1: input: classifier C, thresholds M , query rate ϵ, baseline

β, learning rate η, horizon T 2: output: actions ⟨a1 , . . . , aT ⟩ as per Equation 2. 3: let Ẑm,1 = 0 for all m ∈ M 4: for t ∈ {1 . . . T } do 5: observe xt 6: let at = query with probability ϵ 7: if at = query then 8: observe yt for all m ∈ M , 9: let Ẑm,t+1 = Ẑm,t + 1 − 1−R(m,t) ϵ 10: 11:

with R(m, t) as per Definition 1 else exp(η·Ẑm,t ) for m ∈ M let pm,t = P exp(η·Ẑ ) i∈M

i,t

12: let mt = m with probability pm,t 13: let at = ΓC (xt , mt ) (Equation 4) 14: let Ẑm,t+1 = Ẑm,t + 1 for all m ∈ M 15: end if 16: end for

St = ΓC (xt , mt ) (line 13). The prediction set contains labels whose classifier scores lie within mt of the largest score. No label or coverage indicator is observed after this prediction. This separation between prediction and observation is the beyond feedback feature of the method. To find the best prediction threshold, OCPQ implicitly tries to maximise an auxiliary reward function, defined as follows: Definition 1. Given a data stream z T , classifier C, and set of prediction thresholds M , let the auxiliary reward function R : M ∪ {query} × {1 . . . T } → [0, 1] be the function such that R(query, t) = 0 for all t, and such that for m ∈ M ,  1 − m · (1 − β) if yt ∈ ΓC (xt , m), R(m, t) = 0 otherwise, where ΓC (xt , m) is defined as in Equation 4.

In other words, the algorithm never gets any reward when it makes a query or when it outputs a prediction set St such that yt ̸∈ St . Otherwise, if yt ∈ St , the algorithm gets a higher reward for selecting a tighter prediction threshold; this will encourage the algorithm to select small prediction thresholds (which in turn leads to small prediction sets), but without selecting thresholds that are too small, since this would lead to 0 reward. The value of β lets us control the trade-off between achieving a higher coverage rate and a better efficiency (c.f. Corollary 1 and Figure 1). In particular, with β = 1 all coverage events are treated equally; with β = 0, a coverage event yields a 1 − m reward, meaning that the prediction threshold has the highest impact on reward. We provide further discussion of the construction of the reward function in the Appendix, where we also compare the reward in Definition 1 to other reward functions in the existing literature. Note that OCPQ never actually directly observes the value of the reward function — this is why we say that it only implicitly maximises this reward. If it makes a query then it can calculate how much reward each prediction threshold would have got on that round, but at the expense of getting 0 actual reward on that round. To estimate the reward of each prediction threshold, OCPQ associates each m ∈ M with a weight Ẑm,t , initially set to 0, and then updates these weights in a way that tracks the value of the corresponding prediction threshold (lines 3, 9, and 14). In particular, for each m ∈ M and t ≤ T , we have that Ẑm,t is an unbiased estimator of the cumulative reward (up to t) of threshold m, as long as ϵ > 0, where the expectation is over the randomness in OCPQ (c.f. Lemma 1 in the Appendix). The main difference from the original label efficient protocol of Cesa-Bianchi, Lugosi, and Stoltz (2004) is that a query is treated as a distinct action; in Cesa-Bianchi, Lugosi, and Stoltz (2004), the learner may take an action and query the outcome on the same round. Extensions In the Appendix, we describe a few ways to generalise the OCPQ algorithm. Specifically, we describe how to accept delayed observations, how to support infinite or unknown time horizons, how to use it with set-valued classifiers, and how to use it with non-discrete label spaces.

Theoretical Results In this section, we present our theoretical results about OCPQ. All proofs are provided in the Appendix. We first prove a regret bound for OCPQ. Let R be the auxiliary reward function given in Definition 1, and define the regret of a sequence of actions aT = ⟨a1 . . . aT ⟩ as reg(aT ) = max

m∈M

T X t=1

R(m, t) −

T X

R(at , t),

t=1

where each action at is either query or an element of M . 3 Similarly, for a given algorithm, we can define its expected regret (when using a classifier C on a data stream z T ) as the expectation of the regret of the actions that the algorithm takes. We can now state the following result: Theorem 1. For any data stream z T and classifier C, and any η ∈ (0, 1] and ϵ ∈ (0, 0.5], the expected regret of Algorithm 1 with the auxiliary reward (Definition 1) is at most η ln(|M |) · T. +ϵ·T + η ϵ p If we set ϵ = T −1/3 and η = T −2/3 · ln(|M |) then this simplifies to p T 2/3 · (2 ln(|M |) + 1). In other words, with an appropriate query and learning rate, the expected regret of OCPQ grows as O(T 2/3 ). Using the results in Lattimore and Szepesvari (2018), it is possible to show that this growth rate is asymptotically optimal — for details, see Proposition 2 in the Appendix. It is also worth noting that this can be achieved with a very low query rate of only T −1/3 . Of course, for this to be of interest to us, we must also establish some kind of connection between the regret and the coverage rate (or inefficiency). Our next result provides such a connection to the coverage rate: Theorem 2. Given a data stream z T , classifier C, and sequence of actions aT = ⟨a1 . . . aT ⟩ ∈ (M ∪ {query})T , if reg(aT ) ≤ N , then the coverage of aT is at least β − N/T . Using these two results, we can now derive a lower bound on the expected coverage rate of OCPQ: Corollary 1. On any data stream z T and for any classifier C, the coverage rate pcover of Algorithm 1 satisfies ! p 2 ln(|M |) + 1 √ E [pcover ] ≥ β − 3 T p provided that η = T −2/3 · ln |M | and ϵ = T −1/3 ≤ 0.5. Note that Corollary 1 means that β is nearly a lower bound on the expected coverage rate.4 Since a higher coverage rate typically will correspond to lower efficiency, and vice versa, 3 It is important to note that the regret is defined relative to a given classifier C, set of thresholds M , and data stream z T . 4 Note that |M | and T can be assumed to be known beforehand. This means that if we wish to target a specific pcoverage rate, then √ we can actually calculate the exact value of (2 ln(|M |) + 1)/ 3 T and simply increase the value of β accordingly.

this means that we can use β to control the trade-off between the two. However, it is important to note that Corollary 1 is a lower bound (for any data stream), and that the actual coverage rate may be higher than this bound (at the expense of higher inefficiency), see Figure 1. In addition to having a lower bound on the coverage rate, it would be nice to also have an upper bound on the inefficiency. Unfortunately, it would be impossible to derive such a bound without making any assumptions about the classifier or the data stream. To see this, note that z T could be a data stream on which the correct label is always the one which C assigns the lowest probability — in that case, the inefficiency of an optimal learner will converge to |Y|, which is also a trivial general upper bound. However, note that Theorem 1 implies that the expected regret of OCPQ per time step goes to 0 as T increases. This means that if T is sufficiently large, then we should expect OCPQ to converge to mostly using the prediction threshold m ∈ M that maximises the auxiliary reward. The way this reward function is constructed means that the learner will be encouraged to use a prediction threshold that is as small as possible. It is also possible to derive a bound on |St | by making assumptions about C and xt . For example: Proposition 1. For any classifier C, any xt ∈ X , and any threshold mt ∈ [0, 1], let St be constructed as in Equation 4. Let maxy∈Y pC (y | xt ) = pmax . If mt < pmax then |St | ≤ max 1 + p1−p , and if mt ≥ pmax then |St | = |Y|. max −mt We next provide a high-probability bound on the regret of OCPQ, which shows that its variance cannot be too large: p Theorem 3. If ϵ = T −1/3 ≤ 0.5 and η = T −2/3 · ln(|M |), then for any δ ∈ (0, 1/3) we have that the regret of Algorithm 1 is at most p 2 · T 5/6+δ/2 + 2 · T 3/4 + (1 + 2 ln(|M |)) · T 2/3 p p + ln(|M |) · T 1/3 + ln(|M |) · T (1+δ)/2 with probability at least (1 − 3 exp(−2T δ ))· (1 − exp(−2T 1/2 ) − exp(−2(T 1/6 − T δ/2 ))).

(8)

The Appendix provides a more general version of Theorem 3. To make the meaning of this theorem a bit more intuitive, first note that (1−3 exp(−2T δ ))·(1−exp(−2T 1/2 )− exp(−2(T 1/6 − T δ/2 ))) will approach 1 as T approaches infinity, provided that 0 < δ < 1/3. Moreover, also note that we can make T 5/6+δ/2 arbitrarily close to T 5/6 by making δ sufficiently small, and note that this term will dominate the other terms in the expression. In other words, Theorem 3 states that for large T , the regret of OCPQ will be less than approximately 2 · T 5/6 with very high probability. While it is unclear if this bound is tight, Theorem 3 demonstrates that there is no data stream on which OCPQ has pathologically high variance. For example, it is worth noting that an analogous result cannot be derived for EXP3 (see Lattimore and Szepesvari 2020, exercise 11.6). Cesa-Bianchi, Lugosi, and Stoltz (2004) also prove a high-probability regret bound for their label-efficient forecaster — we provide

Inefficiency

Coverage

MNIST → USPS

MNIST → MNIST-C

CIFAR-10 → CIFAR-10-C

CIFAR-100 → CIFAR-100-C

1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2 0.0

0.2 0.0

0.2 0.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

0.2 0.0

1.0

10

10

10

100

8

8

8

80

6

6

6

60

4

4

4

40

2

2

2

20

0 0.0

0.2

0.4

0.6

0.8

1.0

0 0.0

0.2

0.4

0.6

0.8

0 0.0

1.0

0.2

0.4

0.6

0.8

0 0.0

1.0

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

Figure 1: Effect of β on coverage and efficiency. We use a neural network trained on MNIST (LeCun et al. 1998), CIFAR-10, or CIFAR-100 (Krizhevsky 2009), and let the data stream be the USPS handwritten digit data set (Hull 1994), MNIST-C (Mu and Gilmer 2019), CIFAR-10-C, or CIFAR-100-C (Hendrycks and Dietterich 2019). We vary β from 0 to 1 in increments of 0.1 and p run OCPQ 10 times for each value of β with M = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}, ϵ = T −1/3 , and η = T −2/3 · ln |M |, where T is the size of the data set. The graphs show the average resulting coverage rate and efficiency, with error bars showing the mean absolute deviation. The black dashed line is the lower bound from Corollary 1, and the blue dashed line is the accuracy of the network on the relevant data set when no conformal prediction is used.

pcover ≥ β − 2 · T δ/2−1/6 − 2 · T −1/4 p − (1 + 2 ln(|M |)) · T −1/3 p p − ln(|M |) · T −2/3 − ln(|M |) · T (δ−1)/2 with probability at least as given in Equation 8.

Empirical Results The Coverage-Efficiency Tradeoff Figure 1 shows the results of a number of experiments in which we apply OCPQ to several standard benchmarks. In the experiments we let C be a neural network trained on one data set, but we let the data stream z T be a different data set, in order to simulate distribution shifts. We vary β from 0 to 1 and show the resulting coverage rate and efficiency. As we can see, we can control the trade-off between coverage and efficiency via the choice of β. The coverage is always above the accuracy of the base classifier and the analytic bound (as we expect), but the learner appears to typically be more conservative than the bound requires. It is interesting to note that the graphs for the coverage and efficiency both seem to consistently have a sigmoid shape, meaning that there is a relatively small range of β in which the learner quickly goes from low to high coverage. This suggests that

Vanilla

1.0

Adversarial

Overall coverage 10

0.9 0.8 0.7

Theoretical bound

Prediction-set size

Classes

Corollary 2. If ϵ = T −1/3 ≤ 0.5 and η = T −2/3 · p ln(|M |), then for any δ ∈ (0, 1/3) we have that the coverage rate pcover of Algorithm 1 satisfies

the precise choice of β may be a delicate matter in practice.5 Many additional results are discussed in the Appendix, including experiments on varying the granularity of M , different choices of adversaries and reward functions, and the effects of distribution shifts.

Coverage rate

a comparison of this bound and the bound proven in Theorem 3 in the Appendix. Finally, we note that Theorem 3 also induces a high-probability bound on the coverage rate:

0.0 0.2 0.00 0.25 0.50 0.75 1.00

8 6 4 2 0 0.0

0.2

0.4

0.6

0.8

1.0

Figure 2: β against coverage and efficiency for OCPQ on vanilla and adversarial WildGuardMix prompts. Solid lines and shaded regions show means and mean absolute deviations over ten shuffled single-pass streams. Dashed lines show the finite-horizon coverage lower bound.

5 It is also interesting to note that the inflection point appears to be close to the value of β for which the lower bound on the coverage rate intersects the accuracy of the base classifier. Yet, we cannot predict the location of the inflection point a priori, since we typically do not have prior knowledge of the accuracy of the base classifier in the online setting.

Overall coverage

0.70

6 5 4

32 128 512 2048

Thresholds

8

32

128

512

Thresholds

2048

Figure 3: Sensitivity of OCPQ to the size of M on adversarial WildGuardMix prompts at β = 0.75. Solid lines and shaded regions show means and mean absolute deviations over ten independently shuffled, single-pass streams. The dashed line shows the finite-horizon coverage lower bound.

Adversarial

1.0

0.9

0.9

0.8

0.8

0.7

OCPQ (partial feedback) 0.7 ACI (full feedback)

0

3 8

Vanilla

1.0

Overall coverage

0.75

0.5 0.4

Prediction-set size

Overall Theoretical bound

Classes

Coverage rate

0.80

5

10

Average prediction-set size

0

5

10

Average prediction-set size

Figure 4: Static comparison with full-feedback ACI on vanilla and adversarial WildGuardMix prompts. ACI sweeps target coverage from 0.65 to 0.95 and OCPQ sweeps β ∈ {0, 0.1, . . . , 1}. Points show means over 10 runs. ACI observes every label, whereas OCPQ queries ∼ 4.9% and ∼ 5.5% of the vanilla and adversarial streams respectively. less information, especially in the adversarial setting.

LLM Safety Monitoring With Adversarial Shifts We next consider safety monitoring for LLM prompts, where obtaining human labels during deployment may be costly and users may deliberately pose unsafe requests in an adversarial manner to evade a safeguard. We use WildGuardMix (Han et al. 2024), which contains both vanilla prompts and adversarial rewrites labelled according to a safety-risk taxonomy. We formulate the task as 14-way classification: one class represents safe prompts and the remaining 13 represent distinct risk categories. The adversarial prompts preserve the underlying safety task while introducing a shift in how potentially harmful requests are expressed. Our base classifier is DistilBERT (Sanh et al. 2020) with a 14-way classification head, fine-tuned using only vanilla prompts. Full training and data preparation details are provided in the Appendix. We evaluate the monitor on 8,584 vanilla prompts and 6,404 adversarial prompts over ten independent runs. The distribution shift is substantial: the base classifier’s accuracy falls from (0.7854) on vanilla prompts to (0.5914) on adversarial prompts. Figure 2 reports overall coverage and efficiency as β varies. As expected, adversarial prompts make coverage substantially more expensive, and the empirical coverage remains above the theoretical bound. We also examine sensitivity to the number of candidate thresholds at β = 0.75 on adversarial prompts (Figure 3). Increasing |M | from 8 to 64 reduces inefficiency from 5.75 to 2.99 while the coverage decreases from 0.776 to 0.721. Beyond 64 thresholds, both quantities remain broadly stable. Comparison with full-feedback ACI. We compare OCPQ with Adaptive Conformal Inference ( ACI) (Gibbs and Candes 2021) using a fixed calibration set of 2,141 vanilla prompts. ACI observes the label after every prediction and selects continuous empirical-quantile thresholds. OCPQ instead receives feedback on approximately 5% of rounds and selects among 32 uniformly spaced thresholds. Because ACI’s target coverage and OCPQ’s β have different meanings, we compare their coverage–inefficiency frontiers rather than individual values. As expected, the full-feedback reference is more efficient at comparable coverage. Nonetheless, this gap is surprisingly small considering that OCPQ uses much

Discussion Conclusions and Significance We have developed an OCP method for a setting where labels are available only through rounds on which the learner declines to predict. OCPQ reduces this problem to a partial monitoring game and solves the resulting game using a version of the label efficient forecaster (Cesa-Bianchi, Lugosi, and Stoltz 2004) that has been adapted so that queries replace actions. Its expected regret and coverage guarantees hold for any fixed black box classifier and any oblivious adversarial data stream. The expected query fraction is only T −1/3 , while the coverage deficit is O(T −1/3 ). This separates OCPQ from bandit and semi-bandit OCP methods that obtain information from deployed actions, and from intermittent methods that require exogenous feedback. The experiments show that this sparse supervision can still support useful coverage and efficiency tradeoffs, even under adversarial distribution shifts.

Limitations and Future Work There are a number of ways that our work can be extended. The parameter β allows the user to control the coverageefficiency trade-off in OCPQ, with larger values yielding stronger coverage guarantees (Corollary 1). However, in practice, the achieved coverage is often higher than the guaranteed level, with a corresponding loss in efficiency (Figure 1). This conservatism is a consequence of the weak assumptions of the partial monitoring game, which allows adversarial data and provides no label feedback on prediction rounds. Developing less conservative methods with finer control of the trade-off is an important direction for future work. OCPQ works for any data stream z T , but it assumes that this data stream is fixed at the start of the interaction. In particular, the value of xt and yt cannot depend on the past predictions of the learner (i.e., we assume that the adversary is oblivious rather than adaptive). This is often a reasonable assumption, but there are cases when it does not hold. Generalising OCPQ to handle such dependencies would be an interesting extension, though this also comes with wellknown challenges (see, e.g., Arora, Dekel, and Tewari 2012).

References Angelopoulos, A. N.; Barber, R.; and Bates, S. 2024a. Online conformal prediction with decaying step sizes. In Salakhutdinov, R.; Kolter, Z.; Heller, K.; Weller, A.; Oliver, N.; Scarlett, J.; and Berkenkamp, F., eds., Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 1616–1630. PMLR. Angelopoulos, A. N.; Barber, R. F.; and Bates, S. 2024b. Online conformal prediction with decaying step sizes. arXiv:2402.01139. Angelopoulos, A. N.; and Bates, S. 2022. A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification. arXiv:2107.07511. Arora, R.; Dekel, O.; and Tewari, A. 2012. Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret. arXiv:1206.6400. Besson, L.; and Kaufmann, E. 2018. What Doubling Tricks Can and Can’t Do for Multi-Armed Bandits. arXiv:1803.06971. Bhatnagar, A.; Wang, H.; Xiong, C.; and Bai, Y. 2023. Improved Online Conformal Prediction via Strongly Adaptive Online Learning. arXiv:2302.07869. Bistritz, I.; Zhou, Z.; Chen, X.; Bambos, N.; and Blanchet, J. 2019. Online EXP3 Learning in Adversarial Bandits with Delayed Feedback. In Wallach, H.; Larochelle, H.; Beygelzimer, A.; d'Alché-Buc, F.; Fox, E.; and Garnett, R., eds., Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc. Cesa-Bianchi, N.; Lugosi, G.; and Stoltz, G. 2004. Minimizing Regret with Label Efficient Prediction. In Shawe-Taylor, J.; and Singer, Y., eds., Learning Theory, 77–92. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-54027819-1. Cherenson, D. M.; and Panagou, D. 2026. Staggered Integral Online Conformal Prediction for Safe Dynamics Adaptation with Multi-Step Coverage Guarantees. arXiv:2604.06058. Chia, X. W.; Wong, S. L.; and Pan, J. 2025. Probing Latent Subspaces in LLM for AI Security: Identifying and Manipulating Adversarial States. arXiv:2503.09066. Cohen, K. M.; Park, S.; Simeone, O.; and Shamai Shitz, S. 2023. Calibrating AI Models for Wireless Communications via Conformal Prediction. IEEE Transactions on Machine Learning in Communications and Networking, 1: 296–312. Ge, H.; Bastani, H.; and Bastani, O. 2025. Stochastic Online Conformal Prediction with Semi-Bandit Feedback. In Singh, A.; Fazel, M.; Hsu, D.; Lacoste-Julien, S.; Berkenkamp, F.; Maharaj, T.; Wagstaff, K.; and Zhu, J., eds., Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, 18954–18965. PMLR. Gibbs, I.; and Candes, E. 2021. Adaptive Conformal Inference Under Distribution Shift. In Beygelzimer, A.; Dauphin, Y.; Liang, P.; and Vaughan, J. W., eds., Advances in Neural Information Processing Systems.

Gibbs, I.; and Candès, E. 2021. Adaptive Conformal Inference Under Distribution Shift. arXiv:2106.00170. Gollapudi, S.; Kollias, K.; Munagala, K.; and Sinop, A. 2026. Efficient Online Conformal Selection with Limited Feedback. arXiv:2605.14953. Han, S.; Rao, K.; Ettinger, A.; Jiang, L.; Lin, B. Y.; Lambert, N.; Choi, Y.; and Dziri, N. 2024. WildGuard: Open One-Stop Moderation Tools for Safety Risks, Jailbreaks, and Refusals of LLMs. arXiv:2406.18495. Hendrycks, D.; and Dietterich, T. 2019. Benchmarking Neural Network Robustness to Common Corruptions and Perturbations. Proceedings of the International Conference on Learning Representations. Hull, J. 1994. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5): 550–554. Jiao, D.; Liu, Y.; Yuan, Y.; Tang, Z.; Du, L.; Wu, H.; and Anderson, A. 2026. LLM Safety From Within: Detecting Harmful Content with Internal Representations. arXiv:2604.18519. Kiyani, S.; Pappas, G.; Roth, A.; and Hassani, H. 2025. Decision theoretic foundations for conformal prediction: Optimal uncertainty quantification for risk-averse agents. arXiv preprint arXiv:2502.02561. Krizhevsky, A. 2009. Learning Multiple Layers of Features from Tiny Images. In University of Toronto. Lattimore, T.; and Szepesvari, C. 2018. Cleaning up the neighborhood: A full classification for adversarial partial monitoring. arXiv:1805.09247. Lattimore, T.; and Szepesvari, C. 2019. Exploration by Optimisation in Partial Monitoring. arXiv:1907.05772. Lattimore, T.; and Szepesvari, C. 2020. Bandit Algorithms. Cambridge University Press. LeCun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P. 1998. Gradient-Based Learning Applied to Document Recognition. In Proceedings of the IEEE, volume 86, 2278–2324. Lee, M.; Jung, Y.; and Park, S. 2026. Online Conformal Abstention for Factuality Control Under Adversarial Bandit Feedback. arXiv:2506.14067. Lindemann, L.; Cleaveland, M.; Shim, G.; and Pappas, G. J. 2023. Safe Planning in Dynamic Environments using Conformal Prediction. arXiv:2210.10254. McKenzie, A.; Pawar, U.; Blandfort, P.; Bankes, W.; Krueger, D.; Lubana, E. S.; and Krasheninnikov, D. 2026. Detecting High-Stakes Interactions with Activation Probes. arXiv:2506.10805. Mu, N.; and Gilmer, J. 2019. MNIST-C: A Robustness Benchmark for Computer Vision. arXiv:1906.02337. Pona, E.; Kazemi, M.; Hosseini, M.; Du, Y.; Watson, D.; Simeone, O.; and Paoletti, N. 2026. Calibrate-ThenDelegate: Safety Monitoring with Risk and Budget Guarantees via Model Cascades. arXiv:2604.14251. Ramalingam, R.; Kiyani, S.; and Roth, A. 2025. The Relationship between No-Regret Learning and Online Conformal Prediction. arXiv:2502.10947.

Rubashevskii, A.; Piatrashyn, D.; Nakov, P.; and Panov, M. 2026. Adaptive Conformal Prediction for Improving Factuality of Generations by Large Language Models. arXiv:2604.13991. Rustichini, A. 1999. Minimizing Regret: The General Case. Games and Economic Behavior, 29(1): 224–243. Sanh, V.; Debut, L.; Chaumond, J.; and Wolf, T. 2020. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv:1910.01108. Simeone, O. 2026. Decision Making Needs Uncertainty Quantification [Lecture Notes]. arXiv preprint arXiv:2607.14407. Vovk, V.; Gammerman, A.; and Shafer, G. 2022. Algorithmic Learning in a Random World. Springer Nature. Wang, B.; Zecchin, M.; and Simeone, O. 2025. Mirror Online Conformal Prediction with Intermittent Feedback. arXiv:2503.10345. Wang, B.; Zecchin, M.; and Simeone, O. 2026. Online Conformal Prediction with Corrupted Feedback. arXiv:2605.20515. Wang, Z.; and Qiao, X. 2024. Efficient Online Set-valued Classification with Bandit Feedback. arXiv:2405.04393. Yang, J.; Kim, K.; and Park, S. 2026. Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization. arXiv:2604.17984. Zhao, J.; Huang, J.; Wu, Z.; Bau, D.; and Shi, W. 2026. LLMs Encode Harmfulness and Refusal Separately. arXiv:2507.11878. Zhao, M.; Simmons, R.; Admoni, H.; Ramdas, A.; and Bajcsy, A. 2025. Conformalized Interactive Imitation Learning: Handling Expert Shift and Intermittent Feedback. arXiv:2410.08852. Zhu, M.; Zecchin, M.; Park, S.; Guo, C.; Feng, C.; Popovski, P.; and Simeone, O. 2025. Conformal Distributed Remote Inference in Sensor Networks Under Reliability and Communication Constraints. arXiv:2409.07902.

OCP as a Bandit Problem The OCPQ algorithm approaches OCP as an instance of a bandit problem — more specifically, it treats OCP as a partial monitoring game. In this Appendix, we describe this connection in more detail. Specifically, we describe a scheme that reduces OCP (without feedback) to an instance of a partial monitoring game, thereby allowing any bandit algorithm for general partial monitoring games to be used in this setting. We show that OCPQ is asymptotically optimal for the resulting game, and we discuss how it compares to existing partial monitoring game algorithms (especially Cesa-Bianchi, Lugosi, and Stoltz 2004; Lattimore and Szepesvari 2019). For a detailed overview of partial monitoring games, see, e.g., Lattimore and Szepesvari (2020). In brief, a partial monitoring game is a game between two players, a learner and an adversary. The game is defined in terms of a set of actions A, a set of observations Ω, and a set of states S. We assume that A, Ω, and S all are finite. The game also includes a reward matrix R : A × S → [0, 1] and an observation matrix Φ : A × S → Ω. These matrices are both known at the start of the game. The game is played over T rounds. At the start of the game the adversary picks a sequence of states ξ ∈ S T , which the learner does not get to observe. On each round the learner picks an action at ∈ A, possibly by sampling from some distribution over A. The learner then observes Φ(at , ξt ) and receives R(at , ξt ) reward. Unlike in a typical bandit problem, the learner does not observe its reward, except when this can be inferred from Φ(at , ξt ). This setting generalises the standard adversarial bandit setting, since we can let Φ reveal the reward to the learner, or choose to give the learner more limited information (potentially with a complex structure behind the feedback that is given to the learner). The goal of the learner is to maximise its cumulative reward over the T rounds of the game. The learner is typically evaluated based on its expected regret, defined as max ⋆

a ∈A

T X t=1

R(a⋆ , ξt ) −

T X

EAt ∼Pt [R(At , ξt )] ,

3. On each round, we observe an xt . If we make a query, we also observe yt . Otherwise, we pick a prediction threshold mt ∈ M , and let C(y ⋆ , xt ) − mt }. St = {y ∈ Y : C(y, xt ) ≥ max ⋆ y

We must also specify the action space, observation space, and state space. We could let the states S represent x and y directly, but this becomes very unwieldy, so we will instead let the state at time t correspond to the optimal prediction threshold at time t. Specifically, let 1. A = M ∪ {query}, 2. S = M , 3. Ω = M ∪ {⊥}. Using this representation, if st = m, then this should be interpreted as m being the smallest value in M such that C(yt , xt ) ≥ maxy⋆ C(y ⋆ , xt ) − m, where yt is the correct label at time t. If we make a query then we find out what this optimal threshold would have been, and otherwise we get a null observation ⊥. Note that while the data stream is “actually” a sequence over (X × Y )T , we can w.l.o.g. represent it as a sequence over M T for a given classifier C in the resulting game. Similarly, when the learner makes a query, it would normally observes yt , but this is equivalent to observing the corresponding optimal prediction threshold mt for the purposes of solving this game. Representing the states, actions, and observations in this way will make things cleaner and easier to work with. The observation matrix Φ is given by Φ(query, m) = m for each m, and Φ(a, m) = ⊥ for each a ̸= query. We can use different kinds of reward functions, but for now, let the reward correspond to the auxiliary reward function (Definition 1). Specifically, let R(query, m) = 0 for all m, and let R(ma , ms ) = 0 whenever ma < ms . Otherwise, let R(ma , ms ) = 1−ma ·(1−β) for a given baseline parameter β. The matrices below show what Φ and R look like when M = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0} and β = 0.75:

t=1

where Pt is the distribution over A that the learner samples from on round t. In other words, we compare the reward that the agent obtains to the reward of the single action that would have been best in hindsight, if we had to pick the same action on each round of the game. How well we can do in a partial monitoring game depends on the structure of R and Φ. Lattimore and Szepesvari (2018) show that in any partial monitoring game, the optimal worst-case expected regret will scale as either O(1), O(T 1/2 ), O(T 2/3 ), or O(T ). For an example of an algorithm for partial monitoring games, see, e.g., ExO, due to Lattimore and Szepesvari (2019). We can represent OCP without feedback as a partial monitoring game in the following way: 1. We assume that we have a classifier C : X → ∆(Y ), so that C(x) is a distribution over Y . For convenience, let C(x, y) = C(x)y . 2. We discretise [0, 1] into a finite set of prediction thresholds M ⊂ [0, 1].

0.0 0.2 0.4 R= 0.6 0.8 1.0 query

0.0 1 0.95 0.90 0.85 0.80 0.75 0

0.00 0.2 0.4 Φ= 0.6 0.8 1.0 query

0.0 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 0.0

0.2 0 0.95 0.90 0.85 0.80 0.75 0 0.2 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 0.2

0.4 0.6 0.8 1.00 0 0 0 0 0 0 0 0 0.90 0 0 0 0.85 0.85 0 0 0.80 0.80 0.80 0 0.75 0.75 0.75 0.75 0 0 0 0 0.4 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 0.4

0.6 0.8 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 0.6 0.8

1.0 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ 1.0

Let this partial monitoring game be called the Online Conformal Prediction Without Feedback (OCPWF) game. Note

that we can vary M and β, and the resulting game will still be considered to be an instance of OCPWF. Using this construction, any algorithm for playing partial monitoring games can be used to do online conformal prediction with partial feedback, similar to our Algorithm 1. Exploration by Optimisation (ExO) is a state-of-the-art algorithm for general partial monitoring games, due to Lattimore and Szepesvari (2019). In brief, this algorithm maintains a probability distribution Qt over the actions A, which can be viewed as an “exploitation policy” that is only based on the estimated reward of each action, and not its value of information. To generate its action distribution, ExO then solves a certain optimisation problem to find a distribution Pt over A and a function Gt ∈ A × Ω × A → R, where Pt is used to sample the action at time t and Gt is used to estimate the reward of each action at time t (with these estimates then being used together with Qt to compute Qt+1 ). This optimisation problem is designed in such a way that Pt will balance exploration and exploitation, and such that Gt will create accurate reward estimates in expectation. The optimisation problem does not have an analytic solution, but it is convex, and contains |A| + |A|2 · |Ω| variables. For details, see Lattimore and Szepesvari (2019). In Figure 5, we compare the empirical performance of OCPQ against ExO in the OCPWF game using a number of synthetic data streams. As we can see, ExO consistently suffers less regret than OCPQ (meaning that ExO is better). However, this difference is not huge, and OCPQ is substantially faster than ExO (since the action distribution in OCPQ can be computed directly, whereas ExO has to solve a moderately complex optimisation problem at each time step). Moreover, for OCPQ, it is easy to calculate an exact value for the upper bound on the regret, and thereby get an exact bound on the coverage rate (Theorem 1 and Corollary 1). By contrast, the regret bound of ExO is expressed in terms of a constant opt∗ (η) which is in general difficult to estimate and infeasible to calculate analytically (see Lattimore and Szepesvari 2019, their Theorem 5). Furthermore, it is also easy to bound the number of queries that OCPQ makes, since they are simply sampled i.i.d. from a fixed, known distribution. By contrast, the querying behaviour of ExO is an entirely emergent behaviour stemming from the optimisation problem that lies at the core of the ExO algorithm, and it seems like it would be very difficult to bound the resulting query rate analytically. Using the results in Lattimore and Szepesvari (2018), it is straightforward to show that OCPWF is a “hard” game, meaning that no algorithm can get a worst-case expected regret that grows slower than O(T 2/3 ) (unless β = 1, in which case we can trivially get 0 regret by letting mt = 1 every round). Since the worst-case expected regret OCPQ grows as O(T 2/3 ) (Theorem 1), this means that OCPQ is asymptotically optimal in OCPWF. Proposition 2. The optimal worst-case expected regret in OCPWF is Θ(T 2/3 ), unless β = 1, in which case we get 0 regret by picking at = 1 every round. Proof. The optimal worst-case expected regret of a partial monitoring game G = (R, Φ) satisfies

1. 0 if G has no pairs of neighbouring actions, 2. Θ(T 1/2 ) if G is locally observable and has neighbouring actions, 3. Θ(T 2/3 ) if G is globally observable but not locally observable, and 4. Θ(T ) otherwise, see Theorem 1 in Lattimore and Szepesvari (2018). This proof will use terminology from Lattimore and Szepesvari (2018), but for the sake of brevity we will not define this terminology here, and instead refer to Lattimore and Szepesvari (2018) for the relevant formal definitions. Theorem 1 already implies that OCPWF must be globally observable, but for the sake of completeness, let us also spell out a direct argument. We must show that for any two pareto-optimal actions a1 , a2 ∈ A, there exists a function f : A × Ω → R such that, for any state s, we have that X f (a, Φ(a, s)) = R(a1 , s) − R(a2 , s). a∈A

For OCPWF, we can find an f with this property by simply letting f (query, m) = R(a1 , m) − R(a2 , m). for each m ∈ M , and letting f (a, ⊥) = 0 for all a ̸= query (note that this construction works for all actions in A, not just the pareto-optimal actions). This shows that OCPWF is globally observable. A game is locally observable if we can additionally let f (a, ω) = 0 unless Ca1 ∩ Ca2 ⊆ Ca . In the case of OCPWF, we have that R(query, s) = 0 for all s. However, for all states s we have that there exists an action a such that R(a, s) > 0 (in particular, we can let a = s). This means that Cquery = ∅, and so Ca1 ∩ Ca2 ̸⊆ Cquery for all paretooptimal actions a1 , a2 . As a consequence, we need an f where f (query, m) = 0 for all m ∈ M . However, since Φ(a, m) = ⊥ for all states m and actions a ̸= query, this would imply that there is a constant c ∈ R such that X f (a, Φ(a, s)) = c a∈A

regardless of the state s. However, there are states m1 , m2 such that R(a1 , m1 )−R(a2 , m1 ) ̸= R(a1 , m2 )−R(a2 , m2 ) (in particular, we could let m1 = s1 and m2 = s2 ). This means that OCPWF is not locally observable. Finally, it is only possible for a game to not have any neighbouring actions if there is a single action a that is (at least weakly) optimal for all states s. If β = 1 then a = 1 satisfies this condition. If β < 1 then R(1, 0) = β and R(0, 0) = 1, meaning that 1 is not (weakly) optimal for all states. Similarly, R(query, 1) = 0 but R(1, 1) = 1, and so query is not weakly optimal for all states. Finally, for any m ̸∈ {1, query} we have that R(m, 1) = 0 but R(1, 1) = 1, and so m is likewise not weakly optimal for all states. Thus, unless β = 1, OCPWF must have some neighbouring actions. As we have noted, Cesa-Bianchi, Lugosi, and Stoltz (2004) have also introduced two algorithms for a setting with a feedback structure that is similar to that of the OCPWF game.

In particular, Cesa-Bianchi, Lugosi, and Stoltz (2004) consider a multi-armed bandit problem setting with adversarial rewards, and where the learner does not observe the reward of any action unless it makes a query. This setting can be viewed as a special case of a partial monitoring game. CesaBianchi, Lugosi, and Stoltz (2004) do not study OCP, but they consider a feedback structure that is very similar to the one we are interested in, with the minor difference that they allow the learner to both make a query and select an arm on the same round, whereas we only allow the learner to either pick an action or make a query on a given round (but not both). The update rule for the weights Ẑ in OCPQ is an adaptation of the update rule in Cesa-Bianchi, Lugosi, and Stoltz (2004) for this modified feedback structure.

Constructing the Reward Function In order to represent OCP as a bandit problem where the arms correspond to different prediction thresholds, we must first associate each prediction threshold with a reward (or, equivalently, a loss). This reward function (or loss function) has to incentivise the learner to both achieve a high coverage and to achieve a high efficiency, and thereby control the trade-off between the two. We have used the auxiliary reward function described in Definition 1, but this is not the only option. For example, Yang, Kim, and Park (2026) use a bandit-like algorithm for OCP, whose loss function is defined as ℓt (π, α) = dt (π, α) + at (π) where π ∈ [0, 1] is a prediction threshold, 1 − α is a target coverage rate, at (π) is some function that penalises large prediction sets, and dt (π, α) is mt (π) +1{mt (π) = 0}(α + α(1 − α)) +1{mt (π) = 1}(−α(1 − α)), where mt (π) is an indicator variable that is equal to 1 if prediction threshold π has coverage on round t, and which is equal to 0 otherwise. If we simplify slightly, we can see that dt (π, α) is equal to α(2 − α) when π has coverage, and 1 − α + α2 otherwise. They show that any learning algorithm which suffers a regret of at most Reg(T ) with respect to this reward function satisfies 1 MC(T ) − α ≤ · Reg(T ) + CM C (T ), T where MC(T ) is the miscoverage of the algorithm (i.e., MC(T ) = 1 − pcover in our terminology), and CM C (T ) is a constant term of order O(T −1 ). We can thus rewrite the bound of Yang, Kim, and Park (2026) as Reg(T ) − O(T −1 ). T By contrast, we show that the reward function in Definition 1 induces the very similar bound given by pcover ≥ 1 − α −

Reg(T ) , T where β corresponds to 1 − α (see Theorem 2). Our reward function has the benefit of being easier to construct, and the pcover ≥ β −

corresponding bound on the coverage rate is also easier to express. Note that since we can calculate the value of Reg(T ) and CM C (T ), there is no sense in which either bound gives us a “tighter” bound on pcover — we can simply pick the value of β or α that gives the right-hand side of the inequality the bound we desire for the coverage rate. Nonetheless, different reward functions can be used with Algorithm 1 (and similar algorithms), and it is possible that some reward functions lead to better behaviour than the one we have chosen. To use Algorithm 1 with a different reward function, note that Ẑm,t+1 = Ẑm,t + 1 − 1−R(m,t) if the algorithm makes ϵ a query at time t, and otherwise, Ẑm,t+1 = Ẑm,t + 1. Any reward function can be used in place of R, and both Theorem 1 and 3 will still hold, as long as R(query, t) = 0 for all t. Theorem 2 holds for any reward function such that R(query, t) = 0 for all t, such that R(m, t) = 0 if yt ̸∈ St , and such that R(m, t) ≥ β if yt ∈ St . In particular, the reward does not have to be linearly interpolated between 1 and β — it could instead follow a convex (or concave) curve, and thereby give the algorithm a greater (or smaller) penalty for using a larger prediction threshold. In Figure 11, we show the results of an experiment in which we compare the reward of Definition 1 against two different convex reward functions. Based on this experiment, there does not appear to be a big difference between these three reward functions. It is also worth noting that the quantiles of a distribution can be estimated using the pinball loss, defined as  q · (τ − τ̂ ) if τ ≥ τ̂ , Lq (τ̂ , τ ) = (1 − q) · (τ − τ̂ ) otherwise. Here q ∈ [0, 1] is a target quantile, τ̂ is an estimate, and τ ∈ R is a random variable sampled from some distribution D. The estimate τ̂ which minimises the expectation of the pinball loss is the q’th quantile of D. This loss function can be used in the context of conformal prediction; see, e.g., Gibbs and Candès (2021); Bhatnagar et al. (2023), etc, or see Ramalingam, Kiyani, and Roth (2025) for a more extensive discussion. In particular, we can treat τ̂ ∈ [0, 1] as a prediction threshold and use this to construct a prediction set St = {y ∈ Y : s(x, y) ≤ τ } (9) where s : X × Y → [0, 1] is an arbitrary function referred to as a non-conformity score. For example, note that we can let s(x, y) = maxy⋆ ∈Y pC (y ⋆ | x) − pC (y | x), in which case Equation 9 is the same as Equation 4. Moreover, given a data point zt = (xt , yt ), we let τ = s(xt , yt ), and we let q be a target coverage rate. If each (xt , yt ) is sampled i.i.d. from some fixed distribution, then this loss function will be minimised by the smallest prediction threshold τ̂ that leads to a coverage rate of at least q. By letting R(m, t) ∝ −Lq (m, st ), this loss function can also be used as a reward function. However, while regret with respect to the pinball loss is closely related to the coverage rate in the i.i.d. setting, this connection is more complicated in the adversarial setting — for details, see Ramalingam, Kiyani, and Roth (2025).

Generalisations In this appendix we describe a number of small ways to generalise Algorithm 1. These generalisations are relatively

(a) Random Adversary

(b) Alternating Adversary

(c) Deterministic Adversary

(d) Hard Shift Adversary

Figure 5: Synthetic data for the OCPPF game with β = 0.75 and M = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}, using ExO, OCPQ, and an agent that picks an action uniformly at random every round. The plots show regret rather than reward, so a lower value is better. The “random adversary” picks a random state st each round, the “alternating adversary” cycles through the states in S sequentially, the “deterministic adversary” lets st = 0.8 every round, and the “hard shift adversary” lets st = 1.0 for t ≤ T /2 and st = 0.0 for t > T /2. Each line shows the regret for each type of agent (green for ExO, blue for OCPQ, and red for the random agent) averaged over 10 runs, with error bars corresponding to the average distance to the average value (i.e., the mean absolute deviation). Note that the mean absolute deviation is so small that the error bars are barely visible in the plot. The dashed line shows the analytic bound on the expected worst-case regret of OCPQ, using the relevant value of T . simple, but may still be helpful to point out explicitly.

Delayed Observations Algorithm 1 assumes that the learner receives information immediately whenever it makes a query. However, it is easy to imagine situations where this information could be delayed, so that if the learner makes a query on round t, then it gets to observe yt on round t + n for some n > 0. Fortunately, it is relatively straightforward to generalise Algorithm 1 to this setting. In particular, suppose that the observations can never be delayed by more than n rounds. In this case, we can run n different copies of Algorithm 1 sequentially, such that the i’th copy is run on round t if t ≡ i + 1 mod n (so, for example, the 2nd copy is run on round 2, n+2, 2n+2, etc). Effectively, this splits the data stream into n different interleaving data streams, each of which has length T /n, and each of which is solved by a separate instance of Algorithm 1. Since each separate instance of Algorithm 1 now is guaranteed to make an observation between the rounds of its own sub-stream, our existing theoretical guarantees will apply to each sub-stream. If the expected regret of Algorithm 1 on a data stream of p length T is at most T 2/3 ·(2 ln(|M |)+1), then the resulting (total) expected regret will be at most  p  n · (T /n)2/3 · 2 ln(|M |) + 1  p  = n1/3 · T 2/3 · 2 ln(|M |) + 1 . A scheme similar to this setup is used by Cherenson and Panagou (2026). Note that this requires an upper bound n on the delay of the observations — if the delay is random and without any reasonable upper bound, then more sophisticated techniques may be required (see, e.g, Bistritz et al. 2019).

convert Algorithm 1 into an anytime algorithm using the well-known doubling trick (see, e.g., Besson and Kaufmann 2018). In brief, we first execute Algorithm 1 using T = 1, and then reset it and execute it using T = 2, and then T = 4, then T = 8, etc, until the actual time horizon is reached. Since the expected regret p of Algorithm 1 for a known time horizon T is T 2/3 · (2 ln(|M |) + 1), the resulting expected regret of the modified algorithm for an arbitrary unknown time horizon T will be at most log2 T

X

2i


2/3  p · 2 ln(|M |) + 1

i=0

 2/3 2/3    p 2 ·T −1 = · 2 ln(|M |) + 1 22/3 − 1  p  ≤ 2.71 · T 2/3 · 2 ln(|M |) + 1 .

Set-valued Classifiers We have assumed that the classifier C outputs a distribution over the label space Y , and that each instance xt only has a single true label yt . However, what if each instance xt is instead associated with a set of labels Yt ⊆ Y , and C assigns an independent probability to each label (so C has the type signature X → [0, 1]Y )? It is straightforward to adapt Algorithm 1 to this setting – the only change that is required is that we let st be the smallest value in M such that C(y, xt ) ≥ maxy⋆ C(y ⋆ , xt ) − st for all y ∈ Yt . For the theoretical guarantees, simply redefine the coverage rate to require that Yt ⊆ St instead of yt ∈ St , and let the auxiliary reward function be 0 whenever Yt ̸⊆ St , and all theoretical guarantees will still hold.

Infinite Label Spaces Infinite or Unknown Time Horizons Algorithm 1 is defined relative to a finite time horizon T , at least if we wish to use values of η and ϵ that lead to as low expected regret as possible. However, in practice it is often desirable to have an anytime algorithm. Fortunately, we can

We have assumed that the label space Y is finite. However, what if Y instead consists of an interval? It is fairly easy to adapt Algorithm 1 to this setting, at least if Y is bounded. In particular, suppose Y is a bounded interval I ⊂ R. We then let M be a finite subset of [0, |I|] such that 0 ∈ M

and |I| ∈ M . If Algorithm 1 picks prediction threshold m on round t, then we let St = [C(x) − m, C(x) + m]. In the specification of Algorithm 1, we should let st be the smallest value in M such that yt ∈ [C(x) − st , C(x) + st ]. Moreover, when the algorithm makes a query, we should let Ẑi,t+1 = Ẑi,t +1− (m/|I|)·(1−β) instead of Ẑi,t +1− m·(1−β) ϵ ϵ for all i ∈ M such that i ≥ st . We should also modify the definition of the auxiliary reward function so that R(m, t) = 1 − (m/|I|) · (1 − β) when yt ∈ [C(x) − m, C(x) + m]. With these changes, all the theoretical guarantees we have derived will still hold.

Additional Experiments In this appendix, we provide the results of several additional experiments that we were not able to fit in the main text. First of all, in Figure 6, we show how the choice of M impacts the coverage rate and efficiency of OCPQ on a number of real-world data sets. As we can see, larger sizes of M seems to generally lead to better performance, but only up to some asymptote. In Figure 8 we explore the pareto trade-off between coverage and efficiency, and compare the performance of OCPQ to the “trivial” conformal predictor that outputs Y with probability p and ∅ with probability 1 − p. As we can see, OCPQ improves the pareto frontier compared to the trivial predictor (as we should expect). In Figure 7 we show how the coverage rate and inefficiency of OCPQ evolve over time for a number of real-world data sets (for some specific hyperparameter values). As in our other experiments, we can see that the (empirical) coverage rate of OCPQ typically is quite a bit higher than the analytic bound. In Figure 9 we measure how the average prediction threshold m used by OCPQ depends on β, showing that it generally follows a sigmoidal shape with the same inflexion point that we observe in Figure 1. In Figure 10 we show the coverage rate of each prediction threshold in M for a number of data sets, as well as the reward and expected reward of each prediction threshold for a specific example value of β. As we can see from these plots, many values of β will lead to either of the two “trivial” prediction thresholds m = 0 or m = 1 being the prediction threshold that maximises the expected reward. This reaffirms the impression that picking a good value of β may be a fairly delicate matter in practice. In Figure 11 we use OCPQ with three different reward functions — namely, the reward function given in Definition 1, and two convex reward functions that are designed to give the algorithm a greater penalty (compared to the reward of Definition 1) for using a larger prediction threshold. As we can see, all three reward functions seem to induce similar behaviour in OCPQ (so, in particular, they are not effective for making the empirical cover rate of OCPQ closer to the analytic bound).

WildGuardMix Experimental Details Dataset and task. We construct the LLM-safety monitoring task from WildGuardMix (Han et al. 2024). We formulate prompt-risk detection as 14-way classification, with one benign class and 13 unsafe risk subcategories covering privacy, misinformation, harmful language, and malicious use. Examples assigned to the dataset’s others category are ex-

Partition

Vanilla

Adversarial

Total

Training Model selection Online stream

10,719 2,141 8,584

7,997 1,596 6,404

18,716 3,737 14,988

Table 2: WildGuardTrain partitions after filtering and exact prompt-level deduplication. Classifier fitting uses only the vanilla portion of the training partition. Hyperparameter

Value

Pretrained encoder Number of classes Maximum sequence length Training epochs Batch size Optimizer Learning rate Weight decay Learning-rate schedule Warm-up fraction Gradient clipping Random seed Checkpoint criterion Selected checkpoint

distilbert-base-uncased 14 384 tokens 3 128 AdamW 5 × 10−5 0.01 Linear warm-up and decay 0.06 1.0 0 Calibration macro-F1 Final epoch

Table 3: Training configuration for the WildGuardMix base classifier. cluded because they do not carry a consistent fine-grained risk label. We operate at the prompt level. Prompts are lowercased, stripped, and normalized by collapsing consecutive whitespace, after which exact duplicates are removed. The resulting 37,441 WildGuardTrain prompts are divided into training, model-selection, and online-monitoring partitions using a 50%/10%/40% split. Splitting uses seed 0 and is stratified jointly by risk label and the vanilla/adversarial indicator. Base classifier. We initialize a 14-way sequenceclassification model from distilbert-base-uncased (Sanh et al. 2020) and fine-tune it using only the 10,719 vanilla prompts in the training partition. Inputs are dynamically padded within each batch. The complete training configuration is reported in Table 3. The checkpoint with the highest macro-F1 on the complete model-selection partition is retained; this is the checkpoint from the final epoch. We separately evaluate the classifier on the provided WGTest split after applying the same label filtering and exactdeduplication procedure. The resulting test set contains 834 vanilla and 793 adversarial prompts. The classifier obtains overall accuracy 0.6908 and macro-F1 0.3915. Its accuracy is 0.7854 on the vanilla subset and 0.5914 on the adversarial subset. Online monitoring protocol. The online experiments use the distinct monitoring partition in Table 2: 8,584 vanilla prompts and 6,404 adversarial prompts. Vanilla and adversarial prompts are evaluated as separate static streams. Each

1.0

0.8

0.8

0.6

0.6

0.6

0.6

0.4

coverage rate analytic bound classifier accuracy

0.2 0.0

23

24

25

26

27 |M|

28

29

210

211

0.4 0.2 0.0

(a) Coverage on USPS.

23

24

25

26

27 |M|

28

29

210

211

(b) Coverage on MNIST-C.

0.4

coverage rate analytic bound classifier accuracy

0.2 0.0

23

24

25

26

27 |M|

28

29

210

0.0

100

8

80

6

6

6

60

2 0

2

set size 23

24

25

26

27 |M|

28

29

210

(e) Efficiency on USPS.

211

0

size set

10

8

size set

10

4

4 2

set size 23

24

25

26

27 |M|

28

29

210

211

(f) Efficiency on MNIST-C.

0

23

24

25

26

27 |M|

28

29

210

211

(d) Coverage on CIFAR-100-C.

8

4

coverage rate analytic bound classifier accuracy

0.2

211

(c) Coverage on CIFAR-10-C.

0.4

10

size set

size set

coverage rate analytic bound classifier accuracy

coverage rate

1.0

0.8 coverage rate

1.0

0.8 coverage rate

coverage rate

1.0

40 20

set size 23

24

25

26

27 |M|

28

29

210

211

(g) Efficiency on CIFAR-10-C.

0

set size 23

24

25

26

27 |M|

28

29

210

211

(h) Efficiency on CIFAR-100-C.

Figure 6: These graphs show how the choice of |M | affects the coverage rate and efficiency on a number of real-world data sets. We use a neural network that is trained on one data set but evaluated on a different data set (MNIST to USPS or MNIST-C, CIFAR-10 to CIFAR-10-C, or CIFAR-100 to CIFAR-100-C). We let M consist of evenly spaced prediction thresholds, vary the total number of these thresholds, run OCPQ 10 times for each value of |M |, and record the resulting coverage rates and average prediction set sizes. We use β = 0.9 for MNIST-C and USPS, β = 0.7 for CIFAR-10-C, and β = 0.5 for CIFAR-100-C – these choices were informed by the data shown in Figure 1. The graphs show the average of these values across 10 runs, with error bars corresponding to the average distance to the average value (i.e., the mean absolute deviation). Note that the mean absolute deviation is so small that the error bars are barely visible in the plot. Also note that the x-axes are logarithmic. For the graphs displaying the coverage rates, the black dashed line corresponds to the analytic lower bound on the expected coverage rate, and the blue line corresponds to the baseline accuracy of the network on the relevant data set.

(a) USPS

(b) MNIST-C

(c) CIFAR-10-C

(d) CIFAR-100-C

Figure 7: These graphs show how the long-run coverage rate and efficiency evolves over time on a number of real-world data sets. We use a neural network that is trained on one data set but evaluated on a different data set (MNIST to USPS or MNIST-C, CIFAR-10 to CIFAR-10-C, or CIFAR-100 to CIFAR-100-C). We let M = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}, β = 0.9 for USPS and MNIST-C, and β = 0.5 for CIFAR-10-C and CIFAR-100-C. OCPQ is run 10 times for each data set, with the plot showing the average and the mean absolute deviation for each value over these 10 runs. The purple line shows the coverage rate, the red line shows the inefficiency, the blue line shows the accuracy of the underlying classifier, and the dashed black line shows the analytic bound on the (final) cover rate. The efficiency has been normalised to lie between 0 and 1.

0.8

0.8

0.8

0.8

0.6

0.6

0.4

0.6

0.4

0.2 0.2

0.4

0.6

efficiency

0.8

0.4

0.2

0.0 0.0

1.0

0.6

0.4

0.2

0.0 0.0

coverage

1.0

coverage

1.0

coverage

1.0

coverage

1.0

0.2

(a) USPS

0.4

0.6

efficiency

0.8

0.2

0.0 0.0

1.0

(b) MNIST-C

0.2

0.4

0.6

efficiency

0.8

0.0 0.0

1.0

(c) CIFAR-10-C

0.2

0.4

0.6

efficiency

0.8

1.0

(d) CIFAR-100-C

Figure 8: These graphs show the pareto frontier over the coverage rate and the efficiency. We use a neural network that is trained on one data set but evaluated on a different data set (MNIST to USPS or MNIST-C, CIFAR-10 to CIFAR-10-C, or CIFAR-100 to CIFAR-100-C). Each blue dot corresponds to a run of OCPQ, where β has been varied from 0 to 1 in increments of 0.1, and the red dot corresponds to the underlying classifier without conformal prediction. The orange line corresponds to the trivial conformal predictor that simply outputs Y with probability p and ∅ with probability 1 − p. In these plots, we have normalised the efficiency to lie between 0 (St = Y) and 1 (St = ∅), meaning that a higher value is better.

0.8

0.8

0.8

0.8

0.6

0.6

0.4

0.0 0.0

0.6

0.4

0.2 0.2

0.4

0.6

0.8

1.0

0.6

0.4

0.2 0.0 0.0

thresholds

1.0

thresholds

1.0

thresholds

1.0

thresholds

1.0

0.4

0.2

0.2

(a) USPS

0.4

0.6

0.8

1.0

0.0 0.0

(b) MNIST-C

0.2

0.2

0.4

0.6

0.8

1.0

0.0 0.0

(c) CIFAR-10-C

0.2

0.4

0.6

0.8

1.0

(d) CIFAR-100-C

Figure 9: These graphs show how the hyperparameter β affects the average prediction threshold on a number of real-world data sets. We use a neural network that is trained on one data set but evaluated on a different data set (MNIST to USPS or MNIST-C, CIFAR-10 to CIFAR-10-C, or CIFAR-100 to CIFAR-100-C). We vary β from 0 to 1 in increments of 0.1, run OCPQ, and record the resulting average prediction threshold m (over the full data set). The orange line corresponds to the average prediction threshold used by OCPQ, and the red line to the average of the tightest prediction threshold with coverage. 1.0

1.0

1.0

1.0

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.0 0.0

0.2

0.4

0.6

threshold m (a) USPS

0.8

1.0

0.0 0.0

0.2

0.4

0.6

threshold m (b) MNIST-C

0.8

1.0

0.0 0.0

0.2

0.4

0.6

threshold m

(c) CIFAR-10-C

0.8

1.0

0.0 0.0

0.2

0.4

0.6

threshold m

0.8

1.0

(d) CIFAR-100-C

Figure 10: These graphs show the accuracy for each prediction threshold on a number of real-world data sets. We use a neural network that is trained on one data set but evaluated on a different data set (MNIST to USPS or MNIST-C, CIFAR-10 to CIFAR-10-C, or CIFAR-100 to CIFAR-100-C). We vary m from 0 to 1 in increments of 0.1, and measure what fraction of the time the true label yt is contained in the resulting prediction set St if this value of m is used on every round. For reference, we also plot an example of the auxiliary reward function using different values of β (0.9 for MNIST-C and USPS, 0.65 for CIFAR-10-C, and 0.3 for CIFAR-100-C), as well as the expected total reward of each prediction threshold for this reward function. The green dot indicates the prediction threshold with the highest expected reward for the relevant choice of β, meaning that this is the threshold that OCPQ will converge towards (for the given data set, classifier, and choice of β).

1.0

1.0

1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.0 0.0

0.2

0.4

0.6

0.8

1.0

0.0 0.0

(a) Coverage, linear reward.

0.2

0.4

0.6

0.8

1.0

0.0 0.0

(b) Coverage, quadratic reward.

100

100

80

80

80

60

60

60

40

40

40

20

20

20

0.2

0.4

0.6

0.8

1.0

0 0.0

(d) Efficiency, linear reward.

0.2

0.4

0.6

0.8

1.0

0 0.0

(e) Efficiency, quadratic reward.

1.0

1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.4

0.6

threshold m

0.8

1.0

(g) Reward per action, linear reward.

0.0 0.0

0.2

0.4

0.6

threshold m

0.8

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

(f) Efficiency, quartic reward.

1.0

0.0 0.0

0.4

(c) Coverage, quartic reward.

100

0 0.0

0.2

1.0

(h) Reward per action, quadratic reward.

0.0 0.0

0.2

0.4

0.6

threshold m

0.8

1.0

(i) Reward per action, quartic reward.

Figure 11: These graphs show the coverage rate and average prediction set size for OCPQ using three different reward functions. The linear reward function is the reward function described in Definition 1. The quadratic reward function is equivalent to the linear reward function except that R(m, t) = β + (1 − β) · (m − 1)2 instead of 1 − m · (1 − β) when yt ∈ St . Similarly, the quartic reward function is equal to β + (1 − β) · (m − 1)4 when yt ∈ St . We use a neural network that is trained on the −1/3 , CIFAR-100 training p set, and the data stream is the CIFAR-100 test set. We let M = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}, ϵ = T −2/3 and η = T · ln |M |, where T is the size of the data set. We vary β from 0 to 1 in increments of 0.1, run OCPQ 10 times for each value of β, and record the resulting coverage and efficiency. The graphs show the average of these values across 10 runs, with error bars corresponding to the average distance to the average value. For the graphs displaying the coverage rates, the black dashed line corresponds to the lower bound from Corollary 1, and the blue line corresponds to the accuracy of the network on the CIFAR-100 test set when no conformal prediction is used. The bottom plots show the fraction of the time that the true label yt is contained in the resulting prediction set St for each value of m. For reference, the bottom plots also show the reward for each value of m conditional on yt ∈ St , as well as the expected reward for each value of m over the entire data set, for each of the three reward functions (using β = 0.5). The green dot shows the prediction threshold with the highest expected reward, which is 0 for all three reward functions when β = 0.5.

run traverses every prompt in the relevant partition exactly once, without replacement, in a seeded random order. We report means over ten independently shuffled trajectories, with mean absolute deviations as the uncertainty measure. The classifier produces a softmax probability vector pt . For threshold q, its nested prediction set is   Cq (xt ) = k : max pt,j − pt,k ≤ q . j

For the principal experiment, we use M = {0, 0.2, 0.4, 0.6, 0.8, 1} and sweep β ∈ {0, 0.1, . . . , 1}. At horizon T , OCPQ uses p ϵ = T −1/3 , η = T −2/3 ln |M |. The corresponding expected query rates are 0.04884 for the vanilla stream and 0.05385 for the adversarial stream. For the threshold-grid sensitivity experiment, we fix β = 0.75 and use uniformly spaced grids with |M | ∈ {8, 16, 32, 64, 128, 256, 512, 1024, 2048}. We report overall coverage, under which query rounds count as uncovered. Average prediction-set size is calculated only over rounds on which OCPQ outputs a prediction set.

Proofs In this appendix, we provide the proofs of our theorems. However, before we can do so, we will first introduce a few new definitions and a few lemmas. First of all, in this section, we will generally consider the “actions” of the algorithm to be taken from M ∪ {query}, and use at to denote the action on round t. This is in slight contrast to our original problem formulation, where we define the action space A as P(Y ) ∪ {query}. Since our notion of regret is defined relative to the reward function of Definition 1, and since this reward function is defined over M ∪ {query} rather than P(Y ) ∪ {query}, it will be easier to treat the actions as elements of M ∪ {query}. This is just a terminological detail which will make the proofs easier to read, and it should regardless always be clear from the context, but it may be worth keeping this in mind. Moreover, for each m ∈ M and t ≤ T , we define a random variable X̂m,t that is equal to 1 if at ̸= query, and otherwise, X̂m,t = 1 − 1−R(m,t) . Note that this means that ϵ Ẑm,t+1 = Ẑm,t + X̂m,t . Moreover, X̂m,t acts as an estimator for R(m, t). Its slightly convoluted definition is required to ensure that X̂m,t ≤ 1 with probability 1, which is important in one step of the proof of the regret bound. Before we give the main proof, we will first show that X̂m,t and Ẑm,t are Pt unbiased estimators of R(m, t) and j=1 R(m, j): Lemma 1. We have that E[X̂m,t ] = R(m, t) and E[Ẑm,t ] = Pt−1 j=1 R(m, j), where the expectation is over the randomness in the learning algorithm.

Proof. The value of X̂m,t depends on whether or not the algorithm makes a query at time t. We can thus calculate its expectation as follows: E[X̂m,t ] =P(at = query) · 1   1 − R(m, t) + P(at ̸= query) · 1 − ϵ   1 − R(m, t) =(1 − ϵ) · 1 + ϵ · 1 − ϵ =1 − ϵ + ϵ − (1 − R(m, t)) =R(m, t) We thus have that E[X̂m,t ] = R(m, t). From this, and the linearity of expectation, it also follows that E[Ẑm,t ] = Pt j=1 R(m, j). We will also type out the following calculation, which will be used at one step in the proof (but which is otherwise not very interesting, so the main proof can be kept more readable by listing this calculation separately):
2 . Then Lemma 2. Let ϵ ∈ (0, 0.5] and f (r) = ϵ 1 − 1−r ϵ f (r) ≤ 1ϵ + ϵ − 2 for r ∈ [0, 1]. Proof. Let us first expand the terms in f :  2 1−r f (r) = ϵ 1 − ϵ     1−r (1 − r)2 =ϵ 1−2 + ϵ ϵ2 1 − 2r + r2 = ϵ − 2 + 2r + ϵ 1 2 1 = ϵ − 2 + 2r + − r + r2 ϵ ϵ ϵ      1 1 2 2 = +ϵ−2 . r + 2− r+ ϵ ϵ ϵ

From this, we have that f ′ (r) = 2ϵ r + 2 − 2ϵ . Thus, if f ′ (r) = 0 then r = 1 − ϵ. We can also straightforwardly determine that 1. f (0) = 1ϵ + ϵ − 2 2. f (1) = ϵ 3. f (1 − ϵ) = 0 If 1ϵ + ϵ − 2 = ϵ then ϵ = 0.5, and for ϵ ∈ (0, 0.5) we have that 1ϵ + ϵ − 2 < ϵ. This means that f (r) ≤ 1ϵ + ϵ − 2 for r ∈ [0, 1]. We can now prove the main regret bound: Theorem 1. For any data stream ξ and classifier C, and any η ∈ (0, 1] and ϵ ∈ (0, 0.5], the expected regret of Algorithm 1 with the auxiliary reward is at most η ln(|M |) +ϵ·T + · T. η ϵ p If we set ϵ = T −1/3 and η = T −2/3 · ln(|M |) then this simplifies to p T 2/3 · (2 ln(|M |) + 1).

Proof. This proof is similar to a standard regret bound proof for EXP3 or Hedge, but with  a few minor modifications. P First, let wm,t = exp η · Ẑm,t and Wt = m∈M wm,t . This means that if the algorithm is not making a query at time t, then the probability that it will pick a given prediction threshold m is equal to wt,m /Wt . Also recall that Zm,t is Pt−1 an unbiased estimate of j=1 R(m, j) (see Lemma 1). In PT particular, Zm,T +1 is an unbiased estimate of t=1 R(m, t). The basic proof strategy relies on establishing that, roughly speaking,

P since WT +1 = m∈M wm,T +1 . Also note that X Wt+1 = wm,t+1 m∈M

=

X

exp η Ẑm,t+1

m∈M

=

X

exp η(Ẑm,t + X̂m,t )

m∈M

=

X

exp η Ẑm,t · exp η X̂m,t

m∈M

=

X

wm,t · exp η X̂m,t

m∈M

=

1. if some threshold m gets a lot of reward, then Ẑm,T +1 , and hence wm,T +1 , and hence WT +1 will be large in expectation, and

X

Wt ·

wm,t · exp η X̂i,t Wt

X

PAt ∼Pt (At = m) · exp η X̂m,t

m∈M

= Wt ·

m∈M

2. if the learner does not get a lot of reward in expectation, then WT +1 will be small in expectation.

i h = Wt · EAt ∼Pt exp η X̂At ,t .

Together, this can be used to bound the expected reward of the learning algorithm in terms of the total reward of the best individual prediction threshold.

We can chain this statement to obtain that h i WT +1 = W1 · ΠTt=1 EAt ∼Pt exp η X̂At ,t h i = |M | · ΠTt=1 EAt ∼Pt exp η X̂At ,t

In this proof, it will be convenient to distinguish between the action probabilities that are suggested by the exponential weights {wi,t }i∈M and the action probabilities that the agent is actually using. Therefore, let Pt be the action probabilities of the exponential weights, so that

P P noting that W1 = m∈M exp η Ẑm,1 = m∈M exp 0 = |M |. Putting these two things together, we have thus established that h i exp η Ẑm,T +1 ≤ |M | · ΠTt=1 EAt ∼Pt exp η X̂At ,t

PA∼Pt (A = m) =

wm,t Wt

for m ∈ M , and PA∼Pt (A = query) = 0. Note that, from the definition of the weights {wm,t }m∈M , this is equivalent to applying a softmax function with temperature η to {Ẑm,t }m∈M . Similarly, let Qt be the action probabilities that Algorithm 1 will use at time t, so that PA∼Qt (A = query) = ϵ, and  PA∼Qt (A = m) = (1 − ϵ) ·

wm,t Wt



for m ∈ A. In the proof, we will first bound the regret in terms of the action probabilities Pt , but pretending that the weights {wm,t }m∈A are distributed based on actions drawn from Qt . We will then show that the regret of actions drawn from Qt is not much larger than this quantity. We now provide the proof. First note that for any m ∈ M ,

Taking the natural logarithm of both sides and dividing by η gives  X T h i 1 ln |M | + ln EAt ∼Pt exp η X̂At ,t . Ẑm,T +1 ≤ η η t=1 Note that Ẑm,T +1 is an unbiased estimate of the total reward of threshold m over all T rounds, and the rightmost term looks quite close to being an estimate for the expected reward of Algorithm 1. However, intuitively, the exp and ln functions are getting in the way, so we need to find a way to unpack this expression and make it more linear. Note that ex ≤ 1+x+x2 when x ≤ 1, and that η X̂At ,t ≤ 1 with probability 1 (this is why it was important to define the estimators X̂i,t such that they are bounded by 1). Therefore: T X

h i ln EAt ∼Pt exp η X̂At ,t

t=1

≤

T X

h i 2 ln EAt ∼Pt 1 + η X̂At ,t + η 2 X̂A t ,t

t=1

  exp η · Ẑm,T +1 = wm,T +1 ≤ WT +1

=

T X t=1

 h i h i 2 ln 1 + EAt ∼Pt η X̂At ,t + EAt ∼Pt η 2 X̂A . ,t t

Note that 1 + x ≤ ex for all x ∈ R. We can thus derive that ≤

T X

 h i h i 2 ln exp EAt ∼Pt η X̂At ,t + EAt ∼Pt η 2 X̂A t ,t

t=1

=

T  X

i h i h 2 EAt ∼Pt η X̂At ,t + EAt ∼Pt η 2 X̂A t ,t

t=1

=

T X

T h i i h X 2 η · EAt ∼Pt X̂At ,t + η 2 · . EAt ∼Pt X̂A t ,t

t=1

t=1

on ϵ, xt , yt , and This h C, none of iwhichhare random i h variables. i means that E Pm,t · X̂m,t = E Pm,t · E X̂m,t . Note that this expression is the expected regret with respect to the probability distributions Pt , but where the estimators X̂m,t are coming from a run of Algorithm 1, which is not sampling its actions from Pt . What we are actually interested in the expected regret with respect to the probability distributions Qt , since this is what Algorithm 1 actually uses. However, we can extract this regret with a simple rewrite:

Putting this back into the previous inequality, and rearranging, gives us that Ẑm,T +1 −

T X

h

EAt ∼Pt X̂At ,t

i

t=1 T i h X ln |M | 2 +η . EAt ∼Pt X̂A ≤ t ,t η t=1

At this point, is worth reflecting on the fact that we have not yet used any probabilities or randomness to arrive at this statement. More specifically, the statement above holds for any arbitrary collection of numbers {X̂m,t }m∈M,t∈{1...T } , where Ẑm,T +1 and Pt are derived from these numbers in the way we specified. In fact, the only thing that we have actually assumed about the numbers {X̂m,t }m∈M,t∈{1...T } is that they are bounded above by 1. To proceed, we will now treat the numbers {X̂m,t } as random variables that are generated during a run of Algorithm 1, and take the expectation of both sides of the inequality with respect to these random P variables. For clarity, we will also replace EAt ∼Pt with m∈M Pm,t to emphasise the fact that the values of Pm,t are also random variables dependent on {X̂m,t }, and that the overall expectation of the expression is with respect to these probabilities (not the probabilities Pt ). Note that Pm,t = wm,t /Wt . The left-hand side of the inequality then becomes # " T X X Pm,t · X̂m,t E Ẑm,T +1 − t=1 m∈M T X h i X h i = E Ẑm,T +1 − E Pm,t · X̂m,t t=1 m∈M

=

T X

R(m, t) −

t=1

=

T X

R(m, t) −

=

t=1

T X X

T X

t=1

=

T X

T X

EAt ∼Pt [R(At , t)]

t=1

R(m, t) −

t=1

T X

EAt ∼Qt [R(At , t)]

t=1

−ϵ·

T X

EAt ∼Pt [R(At , t)]

t=1

≥

T X

R(m, t) −

t=1

T X

EAt ∼Qt [R(At , t)] − ϵ · T

t=1

We are here using the fact that EAt ∼Qt [R(At , t)] = (1 − ϵ) · EAt ∼Pt [R(At , t)], which we can of course rewrite as

EAt ∼Pt [R(At , t)] = EAt ∼Qt [R(At , t)] + ϵ · EAt ∼Pt [R(At , t)]. For the last step we are also using the fact that ϵ · PT t=1 EAt ∼Pt [R(At , t)] ≤ ϵ · T , which is a straightforward consequence of the fact that R(m, t) ∈ [0, 1]. Let us now turn to the right-hand side of the inequality. This side of the inequality is equal to

# T X X ln |M | 2 +η Pm,t · X̂m,t E η t=1 m∈M " # T X X ln |M | 2 = +η E Pm,t · X̂m,t η t=1 "

h i E Pm,t · R(m, t)

t=1 m∈M

R(m, t) −

R(m, t) −

h i h i E Pm,t · E X̂m,t

t=1 m∈M

t=1 T X

T X X

T X

EAt ∼Pt [R(At , t)]

m∈M

t=1

We are here using Lemma 1. Also note that Pm,t and X̂At ,t are independent, since the distribution of X̂At ,t only depends

where the expectation is with respect to the parameters {X̂m,t }m∈M,t∈{1...T } . Let A⋆ = M ∪ {query}. We can

Note that R(1, t) = β for all t, which means that β · T ≤ PT maxa⋆ ∈A t=1 R(a⋆ , t). Combining this with the inequality above gives us that

expand the expression inside the expectation: " # X 2 E Pm,t · X̂m,t m∈M

=

X

PAt ∼Qt (At = j)

j∈A⋆

h

X

2 Pm,t X̂m,j At = j

i

m∈M

= PAt ∼Qt (At ̸= query)

X

Pm,t · 12 +

m∈M

2  1 − R(m, t) PAt ∼Qt (At = query) Pm,t 1 − ϵ m∈M  2 X 1 − R(m, t) = (1 − ϵ) + ϵ · Pm,t · 1 − ϵ m∈M   X 1 ≤ 1−ϵ+ Pm,t +ϵ−2 ϵ X

m∈M

1 −1 ϵ 1 ≤ ϵ =

where the first inequality comes from Lemma 2. Putting all of this together, we thus have that T X

R(m, t) −

T X

EAt ∼Qt [R(At , t)] − ϵ · T

t=1

t=1

T X ln |M | 1 +η η ϵ t=1   η ln |M | + = ·T η ϵ

≤

Moving ϵ · T to the right-hand side gives us that T X

R(m, t) −

t=1

≤

T X

We next move on to Theorem 2, which is fairly straightforward to prove: Theorem 2. Given a data stream ξ, classifier C, and sequence of actions µ = ⟨a1 . . . aT ⟩ ∈ (M ∪ {query})T , if the regret of µ with the auxiliary reward of Definition 1 is less than N , then the coverage of µ is at least β − N/T . Proof. By assumption, we have that

a ∈A

t=1

R(at , t) ≤ N.

t=1

Rearranging this expression, and dividing both sides by T , gives us that PT R(at , t) β − N/T ≤ t=1 . T Note that R(at , t) = 0 if β lacks coverage on round t, and that the reward per round can never exceed 1. This means PT that t=1 R(at , t)/T ≤ pcover . Substituting this into the inequality above completes the proof. Using this, we also obtain the following: Corollary 1. On any data stream ξ and for any classifier C, the coverage rate pcover of Algorithm 1 satisfies ! p 2 ln(|M |) + 1 √ E [pcover ] ≥ β − 3 T p provided that η = T −2/3 · ln(|M |) and ϵ = T −1/3 ≤ 0.5. Proof. Immediate from Theorems 1 and 2. Specifically, p if ϵ = T −1/3 ≤ 0.5 and η = T −2/3 · ln(|M |), then the p expected regret of Algorithm 1 is no larger than T 2/3 · (2 ln(|M |) + 1). Theorem 2 then implies that the expected coverage rate of Algorithm 1 must be at least p T 2/3 · (2 ln(|M |) + 1) β− , T which simplifies to ! p 2 ln(|M |) + 1 √ β− . 3 T

EAt ∼Qt [R(At , t)]

Letting m be the prediction threshold that maximises PT t=1 R(m, t) completes the proof.

T X

T X

t=1

η ln |M | +ϵ·T + ·T η ϵ

max ⋆

β·T −

R(a⋆ , t) −

T X t=1

R(at , t) ≤ N.

We also prove our bound on the size of the prediction sets, based on the value of maxy∈Y pC (y | xt ): Proposition 1. For any classifier C, any xt ∈ X , and any threshold mt ∈ [0, 1], let St be constructed as in Equation 4. Let maxy∈Y pC (y | xt ) = pmax . If mt < pmax then |St | ≤ max , and if mt ≥ pmax then |St | = |Y|. 1 + p1−p max −mt Proof. Note that pmax + (|St | − 1) · (pmax − mt ) ≤ 1, since at least one y ∈ St has probability mass pmax , since all other y ∈ St have a probability mass of at least pmax − mt under pC , and since these numbers sum to a value less than one. By rearranging this expression, we obtain that |St | ≤ 1 +

1 − pmax pmax − mt

if mt < pmax . Moreover, if mt ≥ pmax then we of course have that St = Y, since the condition in Equation 4 will be satisfied by all y ∈ Y.

We next prove our high-probability bound on the regret of Algorithm 1. The theorem statement below is more general than the version given in the main text, with the version in the main text being a special case of this version (however, the version in the main text is more readable, which is why we have delegated the more general version to the Appendix). Theorem 3. For any ϵ ∈ (0, 0.5], η ∈ (0, 1], n > 0 and λ > 0, we have that the regret of Algorithm 1 is at most n η η ln(|M |) 2 + 2λT + ϵT + ηT + T + 2 n+ ϵ ϵ ϵ η with probability at least 2

(1 − 3 exp(−2n /T ))· (1 − exp(−2T λ2 ) − exp(−2λ2 (ϵT − n))) p If we let ϵ = T −1/3 , η = T −2/3 · ln(|M |), n = T (1+δ)/2 for some δ ∈ (0, 1/3), and λ = T −1/4 , then we have that regret is at most p 2 · T 5/6+δ/2 + 2 · T 3/4 + (1 + 2 ln(|M |)) · T 2/3 p p + ln(|M |) · T 1/3 + ln(|M |) · T (1+δ)/2 with probability at least (1 − 3 exp(−2T δ ))· (1 − exp(−2T 1/2 ) − exp(−2(T 1/6 − T δ/2 ))). Proof. To prove this, we first define the following quantities: 1. Let RT,m be the total reward of prediction threshold m, PT i.e., t=1 R(m, t). 2. Let RT,π be the (random) total reward of the learner, i.e., PT t=1 R(At , t). 3. Let R̂T,m be the total estimated reward of arm i, i.e., Ẑm,T +1 . 4. Let R̃T,π be the “pseudo-expected regret” of the learner, i.e., T X K X R̃T,π = Pi,t · X̂i,t ,

The inequality is proven in the same way as in the proof of Theorem 1. Note that this holds with probability 1. To complete the proof, we will create high-probability bounds for the last three terms in this expression (note that ln |K|/η is not a random variable, and thus does not need to be bounded). We start with the first term, which contains the square of the reward estimators: X

2 Pm,t · X̂m,t

m∈M

X

=

Pm,t ·

1{at ̸= query} · 12 +

m∈M

  2 ! 1 − R(m, t) 1{at = query} 1 − ϵ   2 1 ≤1{at ̸= query} + 1{at = query} 2 + 1 − ϵ ϵ   2 1 =1 + 1{at = query} 2 − ϵ ϵ   1 ≤1 + 1{at = query} 2 ϵ where we are using Lemma 2 for the first inequality. Let Q be the total number of queries that the agent makes. This implies that

η

T X X t=1 m∈M

  Q T+ 2 ϵ η =η·T + 2 ·Q ϵ

2 Pm,t · X̂m,t ≤η

Note that the expected value of Q is ϵT , and that the probability of making a query on a given round is i.i.d. By Hoeffding’s inequality, we therefore have that for any n,

t=1 i=1

P where Pm,t = exp η Ẑm,t / i∈M exp η Ẑi,t . 5. Let REGm be the random regret that learner suffers with respect to prediction threshold m (so, i.e., REGm = RT,m − RT π ).

=⇒ P(Q ≤ ϵT + n) ≥ 1 − exp(−2n2 /T ). Combining this with the above, this gives us that

We then have that REGm = RT,m − RT,π

η

= RT,m − RT,π + (R̂T,m − R̂T,m ) + (R̃T,π − R̃T,π ) = (R̂T,m − R̃T,π )+ (RT,m − R̂T,m ) + (R̃T,π − RT,π ) ≤

P(Q − ϵT ≥ n) ≤ exp(−2n2 /T )

T X X ln |M | 2 +η Pm,t · X̂m,t + η t=1 m∈M

(RT,m − R̂T,m ) + (R̃T,π − RT,π ).

T X K X

2 Pm,t · X̂m,t ≤η·T +

t=1 m∈M

=η·T +

η ϵ2 η ϵ

· (ϵT + n)

T+

η ϵ2

n

with probability at least 1 − exp(−2n2 /T ). This gives us a bound on the magnitude of the first term. Let us now move on to the next term, which measures the mismatch between the actual reward and the estimated

reward of prediction threshold m: RT,m − R̂T,m =RT,m −

T X

1{at ̸= query} · 1+

t=1

! 1 − R(m, t) 1{at = query} 1 − ϵ  X T 1 =RT,m − T + 1{at = query}(1 − R(m, t)). ϵ t=1 

Let vt = 1{at = query} · (1 − R(m, t)) and let VT = PT t=1 vt . Now the variables vt are independent, and vt ∈ [0, 1]. Thus, by Hoeffding’s inequality, =⇒ P((Vt ≤ E [Vt ] + n) ≥ 1 − exp(−2n2 /T ). PT Moreover, E [Vt ] = t=1 ϵ · (1 − R(m, t)) = ϵT − ϵRT,m . Thus, with probability at least 1 − exp(−2n2 /T ), we have that   1 (ϵT − ϵRT,m + n) RT,m − R̂T,m ≤ RT,m − T + ϵ n = RT,m − T + T − RT,m + ϵ n = ϵ This gives us a bound on the magnitude of the second term. Let us now move on to the last term, which describes the discrepancy between the agent’s “pseudo-expected reward” and its actual reward. We have:

T X

X

1{at ̸= query} ·

t=1

Pm,t · 1+

m∈M

X

1{at = query} ·

t=1

m∈M

  1 − R(m, t) Pm,t · 1 − ϵ

− RT,π =

T X

t=1

This means that with probability at least 1 − exp(−2n2 /T ), we have that R̃T,π − RT,π  ϵT − n ≤T · (1 − r1 ) − · (1 − r2 ) ϵ   n · (1 − r2 ) =T − T · r1 − T − ϵ n n =T − T · r1 − T + T · r2 + − · r2 ϵ ϵ n · (1 − r2 ) + T · (r2 − r2 ) = ϵ n ≤ + T · (r2 − r2 ) ϵ Putting together everything we have so far, and using a simple union bound for the joint probability, we have that for any n > 0, the regret is at most n η η ln |M | 2 , + T · (r2 − r1 ) + ηT + ·T + 2 ·n+ ϵ ϵ ϵ η and that ϵ · T − n ≤ Q ≤ ϵ · T + n, with probability at least

=⇒ P (E[r1 ] − λ ≤ r1 ) ≥ 1 − exp(−2T λ2 ).

1{at ̸= query}+ 1{at = query} 1 −

All that remains is to bound T · (r2 − r1 ) by something that is less than T . By Hoeffding’s Inequality, for any λ,   E[RT,π ] − RT,π P ≥ λ ≤ exp(−2T λ2 ) T   E[RT,π ] RT,π =⇒ P −λ≥ ≤ exp(−2T λ2 ) T T =⇒ P (E[r1 ] − λ ≥ r1 ) ≤ exp(−2T λ2 )

t=1 T X

=⇒ P(ϵT − n ≤ Q) ≥ 1 − exp(−2n2 /T ).

1 − 3 exp(−2n2 /T ).

R̃T,π − RT,π T X

P(ϵT − Q ≥ n) ≤ exp(−2n2 /T )



P(Vt − E [Vt ] ≥ n) ≤ exp(−2n2 /T )

=

where Q is the total number of queries made by the learner, r1 = RT,π /T , and PT P t=1 1{at = query} m∈M Pm,t · R(m, t) r2 = . Q Note that r1 and r2 both approximately track the expected reward of the learner, though we should expect r1 to be smaller by a factor of (1 − ϵ), due to the queries. By Hoeffding’s inequality, we have that for any n,

K X m∈M

1 − R(m, t) Pm,t · ϵ

!

− RT,π =T − RT,π − !   X T K X 1 · 1{at = query} 1 − Pi,t · R(i, t) ϵ t=1 i=1   Q =T · (1 − r1 ) − · (1 − r2 ), ϵ

Similarly, we also have that P (r2 − E[r2 ] ≥ λ) ≤ exp(−2Qλ2 ) ≤ exp(−2(ϵ · T − n) · λ2 ) =⇒ P (r2 ≤ E[r2 ] + λ) ≥ 1 − exp(−2(ϵ · T − n) · λ2 ). Moreover, note that E[r1 ] = (1 − ϵ) · E[r2 ]. This means that T · (r2 − r1 ) ≤ T · ((E[r2 ] + λ) − (E[r2 ] − λ)) = T · (E[r2 ] − (1 − ϵ) · E[r2 ] + 2λ) = T · (ϵ · E[r2 ] + 2λ) ≤ T · (ϵ + 2λ)

with probability at least 1 − exp(−2T λ2 ) − exp(−2(ϵT − n)λ2 ), conditional on Q being at least ϵ · T − n. Putting this together gives us that the regret is at most η η n ln |M | + 2λT + ϵT + ηT + T + 2 n+ 2 ϵ ϵ ϵ η with probability at least (1 − 3 exp(−2n2 /T ))· (1 − exp(−2T λ2 ) − exp(−2λ2 (ϵT − n))). p If we let ϵ = T −1/3 , η = T −2/3 · ln(|M |), n = T (1+δ)/2 for some δ ∈ (0, 1/3), and λ = T −1/4 , then we get the version of this bound that is given in the main text of the paper. Note that we can make the upper bound on the regret slightly smaller by letting λ = T −1/(3+γ) for some very small γ > 0, at the expense of also making the corresponding bound on the probability lower (and messier). Concretely, this will reduce the exponent of the T 3/4 term, but make the probability a bit worse. Also note that n ≤ T −1/2 or λ ≤ T 1/3 will make it so that the probability does not approach 1 as T approaches infinity. Thus, letting n and λ be just slightly larger than T −1/2 and T −1/3 gives us the best asymptotic bound. Finally, we also note that Theorem 3 induces a highprobability bound on the coverage rate of OCPQ: Corollary 2. If ϵ = T −1/3 ≤ 0.5 and η = T −2/3 · p ln(|M |), then for any δ ∈ (0, 1/3) we have that the coverage rate pcover of Algorithm 1 satisfies pcover ≥ β − 2 · T δ/2−1/6 + 2 · T −1/4 p − (1 + 2 ln(|M |)) · T −1/3 p p − ln(|M |) · T −2/3 − ln(|M |) · T (δ−1)/2 with probability at least (1 − 3 exp(−2T δ ))· (1 − exp(−2T 1/2 ) − exp(−2(T 1/6 − T δ/2 ))). Proof. Immediate from Theorems 3 and 2.

High-Probability Bound Comparisons As noted previously, Cesa-Bianchi, Lugosi, and Stoltz (2004) introduce two algorithms for a class of partial monitoring games, of which OCPWF is a special case. They prove (in their Theorem 2) that for any T ∈ N, any m ∈ N, and any ∆ ∈ (0, 1), if their label efficient exponentially weighted average forecaster is run with the right parameters (depending on T , m, and ∆) then with probability at least 1 − ∆, it will make at most m queries and incur a regret of at most r r ln(K) ln(4 · T /∆) 2·T · +6·T · m m where K is the number of actions (meaning that K = |M | for OCPWF). To compare this bound against our Theorem 3

we calculate the value of the regret r1 and the probability p using the bound in Theorem 3 for each value of δ ∈ {10−i : i ∈ 1 . . . 10} and each value of T ∈ {10i : i ∈ 1 . . . 10}. We then let m = T 2/3 and ∆ = 1−p, and calculate the resulting bound on the regret using the bound of Cesa-Bianchi, Lugosi, and Stoltz (2004). In this way, we can compare the bound on the regret using the same bound on the probability. Using these parameters, we find that Theorem 3 gives a tighter bound on the regret for T ≤ 100, 000 whereas Cesa-Bianchi, Lugosi, and Stoltz (2004) give a tighter bound on the regret for T ≥ 1, 000, 000, regardless of the value of δ. Part of this data is shown in Table 4.

103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103 1 · 103 , 2 · 103

104 9 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104 8 · 103 , 1 · 104

Horizon T 105 106 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 4 4 5 · 10 , 5 · 10 3 · 105 , 3 · 105 5 · 104 , 5 · 104 3 · 105 , 3 · 105 5 · 104 , 5 · 104 3 · 105 , 3 · 105 5 · 104 , 5 · 104 3 · 105 , 3 · 105 5 · 104 , 5 · 104 3 · 105 , 3 · 105 107 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106 2 · 106 , 1 · 106

108 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106 1 · 107 , 7 · 106

109 9 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107 8 · 107 , 3 · 107

Table 4: We compare the high-probability regret bound in Theorem 3 to the high-probability regret bound by Cesa-Bianchi, Lugosi, and Stoltz (2004) (their Theorem 2). Using different values of δ and T , we compute the resulting upper bound on the regret and the lower bound on the probability using Theorem 3, assuming that |M | = 10. We then use the same value of T and |M | and the resulting probability p to calculate a bound on the regret using TheoremCesa-Bianchi, Lugosi, and Stoltz (2004) in Cesa-Bianchi, Lugosi, and Stoltz (2004) — in this way, each comparison is for a bound that holds with the same probability. Each cell in the table lists our bound first and the bound from Cesa-Bianchi, Lugosi, and Stoltz (2004) second, with the lower (and thus better) bound being coloured blue, and the larger bound being coloured red (before rounding, so two non-equal values may appear the same in the table).

δ

10 10−3 10−4 10−5 10−6 10−7 10−8 10−9 10−10 10−11

−2

102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102 3 · 102 , 4 · 102

Related documents

• Optimal Conformal Prediction under Epistemic Uncertainty#653879
• SPACR: Single-Pass Adaptive Training of Uncertainty-Aware Conformal Regressors#925179
• SPACR: Single-Pass Adaptive Training of Uncertainty-Aware Conformal Regressors#920944
• DisCoMBO: Steering Expert-in-the-Loop Black Box Optimization via Distributional Conformance#1131314
• Adaptive Conformal Prediction for Image Regression Models with Application to an Inertial Confinement Fusion Emulator#1155470