Online Selective Generation with Adversarial Bandit Feedback

## Abstract

Abstract Large language generative models increasingly interact with humans, while their falsified responses raise concerns. To mitigate this hallucination effect, selectively abstaining from answering, called selective generation , provides an effective way for generators to control the hallucination when uncertain about their answers.
However, as selective generators interact under adversarial environments
and
receive partial feedback from users on selected generation ( e.g., thumbs up or down on the selected answer),
learning methods for selective generation under such practical setups are crucial but currently missing.
To address this limitation, we propose an online learning algorithm for selective generation with partial feedback under an adaptive adversary.
In particular, we re-purpose an adversarial bandit algorithm to design an online selective generation method with controllable false discovery rates (FDR), which measures the rate of hallucination. The key building blocks include a novel conversion lemma from regret of any bandit algorithm to the FDR, and the exploitation of a unique structure of selective generation to reuse partial feedback, which we call feedback unlocking .
We empirically evaluate the efficacy of the proposed online selective generation algorithm with partial feedback over diverse learning environments,
demonstrating its ability to control the FDR, while maintaining reasonable selection efficiency, i.e., the ratio of non-abstaining answers, compared to baselines.

## 1 Introduction

As large language generators (OpenAI, 2023; Meta AI, 2024) surpass average human performance, their interaction with humans becomes increasingly prevalent.
However,
their tendency to generate incorrect information, or so-called hallucination, has significantly raised community concerns on their mis-alignment issues.
One simple but effective approach to mitigating hallucination is selective generation, selectively abstaining from generation if the generator is unsure of its response (Geifman & El-Yaniv, 2017; Goren et al., 2024; Mohri et al., 2023; Lee et al., 2024).
By the abstention, the selective generator may control its high precision, or equivalently a low false discovery rate (FDR), *i.e.,* whenever it says answers, they are mostly correct.
Interestingly, few selective prediction and generation methods (Geifman & El-Yaniv, 2017; Goren et al., 2024; Lee et al., 2024) provide theoretical guarantees on the controllability of the FDR to ensure the trustworthiness of generators.

However, conventional selective prediction methods (Geifman & El-Yaniv, 2017; Goren et al., 2024; Lee et al., 2024) are designed under limited *stochastic assumptions*, *i.e.,* data are independently drawn from a fixed distribution, which undermines their applicability to real world applications in adversarial and distribution-shifted environments.
Moreover, the methods require *full feedback* (*e.g.,* a true answer is given) instead of *partial feedback* (*e.g.,* the correctness of a selectively generated answer), where partial feedback is more practical and easier to obtain (*e.g.,* thumbs-up buttons in dialog systems).
To mitigate these limitations,
we propose a novel online selective generation algorithm to control a false discovery rate (FDR), while maximizing selection efficiency (*i.e.,* the ratio of non-abstaining cases), with partial feedback.

First, we address online selective generation under partial feedback by leveraging profound achievements from online learning and multi-armed bandits.
To this end,
we reduce online selective generation to bandits
and exploit any regret minimization algorithms,
by
introducing a novel *Regret-to-FDR conversion lemma*.

Second, we design an algorithm tailored for selective generation which fully exploits feedback information.
Although partial feedback is practical, it provides the insufficient amount of information compared to full feedback, leading to sample inefficiency and slower convergence speed.
To address this challenge,
we exploit the unique structure of selective generation to *unlock* additional information from partial feedback, a technique we call *partial feedback unlocking*.
Leveraging this idea, we extend the Exp3-IX algorithm (Neu, 2015) for adversarial bandits to online Selective generation with partial feedback UnLocking (ExSUL).
Moreover, we provide the $\mathcal{{O}}(\sqrt{T\ln|\mathcal{{H}}|})$ expected regret bound of ExSUL—which affects the convergence of the FDR guarantee—better than a learner with partial feedback, *i.e.,* $\mathcal{{O}}(\sqrt{T|\mathcal{{H}}|\ln|\mathcal{{H}}|})$, and compatible to that with full feedback, *i.e.,* $\mathcal{{O}}(\sqrt{T\ln|\mathcal{{H}}|})$, where $T$ is a time horizon and $\mathcal{{H}}$ is a set of hypotheses of selective generators.

Finally, we empirically evaluate the efficacy of the proposed online selective generation algorithm ExSUL.
In particular,
we consider
two tasks (question-answering over TriviaQA (Joshi et al., 2017) and Natural Question (Kwiatkowski et al., 2019) and dialog conversations via two dialog agents),
three learning environments
(stochastic, distribution-shifted, and interactive),
and
two language models (GPT-3.5-turbo (OpenAI, 2023) and LLaMA3.1 (Meta AI, 2024)),
demonstrating that our method
(1) controls the desired FDR and
(2) maintains reasonably low selection inefficiency, *i.e.,* the ratio of abstention.
See Figure [1](https://arxiv.org/html/2506.14067v2#S1.F1) for qualitative results that control an FDR in an interactive environment.

Figure: Figure 1: Qualitative examples from interactive dialog simulation. This demonstrates that our proposed method ExSUL effectively controls the rate of hallucination in the FDR by abstaining from answering under a practical online setup with partial feedback. See Section [4.3](https://arxiv.org/html/2506.14067v2#S4.SS3) for details.
Refer to caption: x1.png

### 1.1 Related Work

Here, we introduce closely related literature, including selective prediction, online learning, and bandit problems. See Appendix [C](https://arxiv.org/html/2506.14067v2#A3) for additional related work.

Selective Prediction.
Selective prediction is a method that abstains from making a prediction to control the FDR in a certified manner.
(Geifman & El-Yaniv, 2017) proposes selective classification, which abstains from uncertain predictions by learning a threshold for a scoring function.
(Goren et al., 2024) extends this framework by leveraging the hierarchical structure of classification labels to improve efficiency.
(Mohri et al., 2023) adapts this idea to generation tasks, though the focus is primarily on the decontextualization without providing an FDR guarantee.
(Lee et al., 2024) further generalizes selective prediction to generation tasks by introducing the concept of an entailment set, which addresses the challenge of open-ended question-answering.
In particular,
they propose a semi-supervised method to leverage unlabeled entailment data, providing
an FDR guarantee.
However, prior work mainly focuses on a batch learning under a stochastic assumption, *i.e.,* i.i.d. assumption on data distributions, which may be fragile in real-world applications.
In contrast, we consider a non-stochastic setup that allows for distribution shift and propose online selective generation methods.

Online Learning and Bandit Problems.
Sequential prediction (Cesa-Bianchi & Lugosi, 2006; Mohri et al., 2012; Sankararaman, 2016; Foster & Rakhlin, 2023) designs learners that adapt to sequentially arriving data.
Unlike stochastic learning, online learning methods (*e.g.,* exponential weighting (Littlestone & Warmuth, 1994)) make minimal distributional assumptions and analyze worst-case, possibly adaptive sequences, with guarantees in terms of regret minimization.
In the full-information setting, the learner observes the loss of every action each round.

Furthermore, bandit problems, such as multi-armed bandits (Agrawal, 1995) and adversarial bandits (Auer et al., 2002; Bubeck et al., 2012), address a partial-feedback setting, where the learner only observes feedback of the chosen action (arm) each round.
A well-known algorithm is Exp3 (Auer et al., 2002), which leverages exponential weighting (Littlestone & Warmuth, 1994) with an importance-weighted unbiased loss estimator.
However, Exp3 suffers from a dishearteningly large variance of the regret, leading to looser concentration.
To obtain high-probability bounds, variants introduce exploration explicitly or implicitly, *i.e.,* Exp3.P (Auer et al., 2002; Bubeck et al., 2012) explicitly mixes the uniform distribution,
and Exp3-IX (Neu, 2015) implements implicit exploration by adding an exploration parameter to the loss estimator.
To efficiently leverage partial feedback, structured bandits (Russo & Van Roy, 2013) exploit the functional structure of arms-to-loss functions and semi-bandits (Sankararaman, 2016) allows to choose a set of arms with fixed size for better learning efficiency.

In particular, we exploit adversarial bandits to mitigate stochastic assumptions in traditional selective prediction
and to consider learning under partial feedback.
Moreover, we leverage a unique structure between arms and loss in selective generation to achieve better learning efficiency.

## 2 Problem: Online Selective Generation with Partial Feedback

We consider online learning of a selective generator under partial feedback for language models. See Appendix [B](https://arxiv.org/html/2506.14067v2#A2) for its preliminary.
Let $\mathcal{{W}}$ be a set of tokens
and
$\mathcal{{X}}=\mathcal{{Y}}\coloneqq\cup_{i=0}^{\infty}\mathcal{{W}}^{i}$ be a set of (token) sequences.
Here, given a generator $G:\mathcal{{X}}\to\mathcal{{Y}}$, we consider a time-varying selective generator $\hat{{S}}_{t}:\mathcal{{X}}\to\mathcal{{Y}}\cup\{\texttt{IDK}\}$ that abstains from answering if a generated answer $G(\mathbf{x}_{t})$ at time $t$ is uncertain, *i.e.,* $\hat{{S}}_{t}(\mathbf{x}_{t})\coloneqq\begin{cases}G(\mathbf{x}_{t})&\text{if~}\hat{{s}}(\mathbf{x}_{t},G(\mathbf{x}_{t}))=1\\
\texttt{IDK}&\text{otherwise}\end{cases},$
where
$\hat{{s}}:\mathcal{{X}}\times\mathcal{{Y}}\to\{0,1\}$ is a selection function
and
IDK represents “I don’t know”.
Following the conventional selective prediction literature, we consider the scalar parameterization of the selection function $\hat{{s}}$ given a scoring function $f:\mathcal{{X}}\times\mathcal{{Y}}\to{[0,1)}$, *i.e.,* $\hat{{s}}(\mathbf{x}_{t},G(\mathbf{x}_{t}))\coloneqq\mathbbm{1}\left(f(\mathbf{x}_{t},G(\mathbf{x}_{t}))\geq\tau\right),$
thus the selective generator $\hat{{S}}$ is parameterized by $\tau$, denoted by $\hat{{S}}(\cdot;\tau)$.
Here,
the scoring function $f$ measures the confidence of $G(\mathbf{x}_{t})$ being an answer of $\mathbf{x}_{t}$.
Also,
we specifically consider that $\tau$ is from the finely-quantized, finite space of $[0,1]$,
*i.e.,* $\mathcal{{H}}=\left\{k/(H-1):k=0,1,\dots,H-1\right\}$, where $H$ is the number of hypotheses.

To formalize supervision signals in online learning,
we define a feedback function $\mathcal{{E}}_{t}:\mathcal{{H}}\rightarrow\{0,1\}$ that outputs feedback given a selective generator $\hat{{S}}$,
*i.e.,* $\mathcal{{E}}_{t}(\hat{{S}})\coloneqq\mathbbm{1}(\hat{S}(\mathbf{x}_{t})\neq_{E}\mathbf{y}_{t})$,
and assume that a learner does not observe a ground-truth $\mathbf{y}_{t}$ but instead receives *partial feedback* $\mathcal{{E}}_{t}(\hat{{S}}_{t})$,
which we simply denote as $e_{t}$ in the paper.
Here, $A\neq_{E}B$ means that $A$ and $B$ are different in terms of a given correctness relation $E$, *e.g.,* textual-entailment (Bowman et al., 2015); thus, $e_{t}=0$ if the generation is correct and $e_{t}=1$ if it is incorrect or $\hat{S}_{t}(\mathbf{x}_{t})=\texttt{IDK}$ by definition. This setup reflects real-world scenarios, where a user typically provides $e_{t}=0$ or $1$, *e.g.,* thumbs-up or down, instead of $\mathbf{y}_{t}$.

To learn an online selective generator with this partial feedback,
we consider online learning in a non-stochastic assumption:
each step $t$ until a time horizon $T$,
(1) an adversary chooses $\mathbf{x}_{t}\in\mathcal{{X}}$ and
$\mathbf{y}_{t}\in\mathcal{{Y}}$, which determine the feedback function $\mathcal{{E}}_{t}$
(2) a learner observes $\mathbf{x}_{t}\in\mathcal{{X}}$ and predicts $\hat{{S}}_{t}(\mathbf{x}_{t})$ where $\hat{{S}}_{t}$ is drawn from a learned distribution $p_{t}$ over selective generators,
and
(3) the leaner observes partial feedback $e_{t}$ and update $p_{t}$ by using it.
Here, we consider an adaptive adversary, *i.e.,* $(\mathbf{x}_{t},\mathbf{y}_{t})$ is drawn from a distribution that depends on
the learner’s previous decisions $\hat{{S}}_{1},\dots,\hat{{S}}_{t-1}$ but crucially not on the current decision $\hat{{S}}_{t}$.

Goal.
Under this learning setup,
our primary goal is to control the false discovery rate (FDR) of a selective generator at a desired level $\alpha\in[0,1]$ up to a time horizon $T$.
To this end, we define the *FDR risk* as follows:

$$ $\mathcal{{R}}_{T}^{\textbf{FDR}}\coloneqq\sum_{t=1}^{T}\Big[\mathbbm{1}(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK}\wedge e_{t}=1)-\alpha\mathbbm{1}(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK})\Big].$ (1) $$

The main objective is to ensure $\mathcal{{R}}_{T}^{\textbf{FDR}}\leq 0$, equivalent to requiring the empirical FDR less than $\alpha$:

$$ $\textbf{FDR}_{T}\coloneqq\frac{\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK}~\wedge~e_{t}=1\right)}{\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK}\right)}\leq\alpha,$ (2) $$

where $\textbf{FDR}_{T}=\alpha$ if
$\hat{{S}}_{t}(\mathbf{x}_{t})=\texttt{IDK}$ for all $t$.
Then, the goal is to learn a distribution $p_{t}$ over selective generators
such that a drawn selective generator $\hat{{S}}_{t}\sim p_{t}$ controls $\mathcal{{R}}_{T}^{\textbf{FDR}}$ close to zero, *i.e.,* $\sum_{t=1}^{T}\big[\mathbbm{1}(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK}\wedge e_{t}=1)-\alpha\mathbbm{1}(\hat{{S}}_{t}(\mathbf{x}_{t})\neq\texttt{IDK})\big]\leq\varepsilon(T),$
where $\varepsilon(T)$ is some non-increasing function in $T$.
Note that the learner controls $\mathcal{{R}}_{T}^{\textbf{FDR}}$ while the adaptive adversary tries to maximize it.
Additionally, while FDR controllability is the primary objective, we also wish to minimize selection inefficiency
$\textbf{Ineff}_{T}\coloneqq\frac{1}{T}\sum_{t=1}^{T}\mathbbm{1}(\hat{{S}}_{t}(\mathbf{x}_{t})=\texttt{IDK}).$

## 3 ExSUL : Online Selective Generation with Feedback Unlocking

We leverage a regret perspective from bandit problems to design a learning algorithm for selective generation that controls the FDR under partial feedback. As a preliminary, we first introduce the necessary background on regret minimization in adversarial bandits (Section [3.1](https://arxiv.org/html/2506.14067v2#S3.SS1)).
We then reduce online selective generation problems to adversarial bandit problems
with partial feedback (Section [3.2](https://arxiv.org/html/2506.14067v2#S3.SS2)).
This reduction enables us to leverage any regret minimization algorithms
with their regret bounds
for selective generation algorithms with FDR bounds.
However, the connection between regret and FDR is missing.
To fill this gap, we introduce a novel conversion lemma from the regret to the FDR (Section [3.3](https://arxiv.org/html/2506.14067v2#S3.SS3)).

However, under partial feedback, simply leveraging existing bandit algorithms may not lead to sample efficiency without exploiting unique properties of selective generation.
To address this, we propose a novel sample-efficient method for online selective generation under partial feedback.
In particular, we extend the Exp3-IX algorithm (Neu, 2015) to learn selective generators, exploiting the unique structure of their selection functions by *feedback unlocking*, theoretically and empirically demonstrating its efficient regret bound (Section [3.4](https://arxiv.org/html/2506.14067v2#S3.SS4)),
which eventually leads to an FDR bound by using our conversion lemma.
Note that online selective generation under full feedback can be devised in a similar way.
See Appendix [D.1](https://arxiv.org/html/2506.14067v2#A4.SS1) for the detail via exponential weighting (EW).

### 3.1 Regret Minimization and Adversarial Bandits

The adversarial bandit problem (Auer et al., 2002) is formulated as an interactive game between a learner and an adversary. At each round $t\in{1,\dots,T}$, the *learner* selects an arm $\tau_{t}\in\mathcal{{H}}$ among a set of arms $\mathcal{{H}}$, while the *adversary* simultaneously chooses a loss function $\ell_{t}:\mathcal{{H}}\to\mathbb{R}_{\geq 0}$. The learner then observes only the incurred loss $\ell_{t}(\tau_{t})$ as partial feedback.
The learner’s performance is evaluated by the *regret* (Bubeck et al., 2012), *i.e.,*

$$ $\textbf{Reg}_{T}\coloneqq\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau),$ (3) $$

and the goal of the learner is to minimize $\textbf{Reg}_{T}$ so that it grows sublinearly in $T$.
Here, the *adaptive adversary* maximizes $\textbf{Reg}_{T}$ by choosing $\ell_{t}$ based on the previously chosen arms by the learner, *i.e.,* $\tau_{1},\dots,\tau_{t-1}$. This makes $\textbf{Reg}_{T}$ a random variable, so we analyze high-probability or expected regret bounds.
For further details on regret minimization and Exp3-IX (Neu, 2015), see Appendix [B.3](https://arxiv.org/html/2506.14067v2#A2.SS3) and [B.4](https://arxiv.org/html/2506.14067v2#A2.SS4).

### 3.2 Reduction: From Online Selective Generation to Adversarial Bandits

**Table 1: From online selective generation to adversarial bandits**
|  | online selective generation | adversarial bandits |
| --- | --- | --- |
| models | selective generators $\mathcal{{H}}$ | finite arms $\mathcal{{H}}$ |
| feedback | $e_{t}$ | $\ell_{t}(\tau_{t},\alpha)$ |
| metric | $\textbf{FDR}_{T}$ and $\textbf{Ineff}_{T}$ | $\textbf{Reg}_{T}$ |

Here, we map the components of online selective generation with partial feedback to those of adversarial bandits to leverage existing algorithms and regret bounds.
In particular, a parameter $\tau\in\mathcal{{H}}$ of our learner corresponds to a bandit arm in adversarial bandits.

For the feedback,
we first define a special loss $\ell_{t}(\tau,\alpha)$ and connect this to $e_{t}$. In particular, we introduce the following two key components:
$a_{t}(\tau)\coloneqq\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)=\texttt{IDK})$, which measures the selection inefficiency at time $t$, called *inefficiency loss*,
and
$d_{t}(\tau,\alpha)\coloneqq\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)\neq\texttt{IDK}\wedge e_{t}=1)-\alpha\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)\neq\texttt{IDK})+\alpha$, which measures the violation of the FDR risk at time $t$ with a
margin by $\alpha$ to penalize the IDK response, called *FDR loss* with a margin.
Based on these, we define the loss function for bandits as follows:

$$ $\ell_{t}(\tau,\alpha)\coloneqq\frac{a_{t}(\tau)+\lambda d_{t}(\tau,\alpha)}{1+\lambda}\in\left\{0,\frac{\lambda}{1+\lambda},\frac{1+\lambda\alpha}{1+\lambda}\right\}\in[0,1],$ (4) $$

where $\lambda$ is a hyperparameter that controls the trade-off between the FDR loss and the efficiency loss.
Note that from the bandits’ perspective, the learner receives feedback in two steps: get feedback $e_{t}$ from the adversary
and
uses this to compute the loss $\ell_{t}(\tau_{t},\alpha)$ for the chosen arm $\tau_{t}$.

Finally, the link between two metrics for online selective generation and adversarial bandits remains to be established.
In the following section, we propose a novel conversion lemma to connect $\textbf{FDR}_{T}$ and $\textbf{Ineff}_{T}$ to $\textbf{Reg}_{T}$.
See Figure [2](https://arxiv.org/html/2506.14067v2#S3.F2) for an illustration of our full learning pipeline from online selective generation to adversarial bandits and back again.

### 3.3 Regret-to-FDR Conversion

We mainly leverage algorithms that minimize $\textbf{Reg}_{T}$ for learning selective generators.
Yet, the key requirement for selective generation is the FDR guarantee of a learner at a desired level.
To this end, we introduce a novel perspective on the connection of a regret bound to an FDR bound.
In particular,
*any learner*, including learners for bandits, which minimizes the regret ([3](https://arxiv.org/html/2506.14067v2#S3.E3)) with the loss ([4](https://arxiv.org/html/2506.14067v2#S3.E4)), controls the FDR ([1](https://arxiv.org/html/2506.14067v2#S2.E1)).
This is achievable as the designed loss ([4](https://arxiv.org/html/2506.14067v2#S3.E4)) penalizes when *FDR loss* at each $t$ is higher than $\alpha$, weighted by a parameter $\lambda$.
See Appendix [H.3](https://arxiv.org/html/2506.14067v2#A8.SS3) for a proof and details on choosing $\lambda$.

###### Lemma 1 .

Let $T\in\mathbb{N}$ and $\alpha\in(0,1)$.
For any $(\mathbf{x}_{t},\mathbf{y}_{t})$ sequences, leading to any loss sequences $\ell_{t}$ of ([4](https://arxiv.org/html/2506.14067v2#S3.E4)),
we have

$$ $\mathcal{{R}}_{T}^{\textbf{FDR}}\leq\frac{(1-\textbf{Ineff}_{T})+(1+\lambda)\textbf{Reg}_{T}/T}{\lambda}=\frac{(1-\textbf{Ineff}_{T})}{T^{\nicefrac{{1}}{{4}}}}+\frac{(1+T^{\nicefrac{{1}}{{4}}})\textbf{Reg}_{T}}{T^{\nicefrac{{5}}{{4}}}},$ (5) $$

where the last equality holds if we take $\lambda=1/T^{\nicefrac{{1}}{{4}}}$.

Importantly, this lemma is applicable to learning for both full and partial feedback, as it is agnostic to feedback mechanisms.
Also, the lemma implies that if $\textbf{Reg}_{T}$ has a sublinear bound,
satisfied by most bandit learners,
then $\mathcal{{R}}_{T}^{\textbf{FDR}}$ gets closer to 0 at most the rate of $\mathcal{{O}}(1/T^{1/4})$, *i.e.,* $\mathcal{{R}}_{T}^{\textbf{FDR}}\leq\mathcal{{O}}(1/T^{1/4})$.

The Connection between $\mathcal{{R}}_{T}^{\textbf{FDR}}$ and $\textbf{FDR}_{T}$.
We can derive the bound for $\textbf{FDR}_{T}$ by dividing ([5](https://arxiv.org/html/2506.14067v2#S3.E5)) by $1-\textbf{Ineff}_{T}$ if $\textbf{Ineff}_{T}\neq 1$, *i.e.,*

$$ $\textbf{FDR}_{T}\leq\alpha+\frac{1}{T^{\nicefrac{{1}}{{4}}}}+\frac{(1+T^{\nicefrac{{1}}{{4}}})\textbf{Reg}_{T}}{T^{\nicefrac{{5}}{{4}}}(1-\textbf{Ineff}_{T})},$ $$

which remains sublinear in $T$ unless $\textbf{Ineff}_{T}$ converges to $1$.
In other words, $\textbf{FDR}_{T}$ may fail to be bounded if
$1-\textbf{Ineff}_{T}\approx 0$ as $\sum_{t=1}^{T}e_{t}\approx T$,
due to the nature of the empirical metric with the variance induced by randomized bandit algorithms.
For instance, if the generator $G$ consistently produces incorrect outputs,
the learner will try to converge to an always-abstaining solution. However, due to randomization, if the learner mistakenly accepts even a single sample in the early stage of learning, then regardless of convergence to an always-abstaining solution, the empirical FDR may still exceed the desired level $\alpha$.
We highlight that this reflects an intrinsic limitation of the empirical FDR evaluation in sequential prediction.
Thus, we consider the *FDR risk*,
where our adaptive adversary assumes to maximize the $\mathcal{{R}}_{T}^{\textbf{FDR}}$, where it does not consider this pathological case.

Figure: Figure 2: An example of our proposed framework for online selective generation. At each step $t$, (1) the user provides an input $\mathbf{x}_{t}$, (2) the learner selects an arm $\tau_{t}\sim p_{t}$, (3-4) selectively generates $\hat{{S}}_{t}(\mathbf{x}_{t};\tau_{t})$ , (5-6) the user provides partial feedback $e_{t}$, (7) the loss $\ell_{t}(\tau_{t})$ is computed from $e_{t}$, and (8) the learner update $p_{t}$ by the loss estimator $\tilde{\ell}_{t}$. Note that the user can be modeled as an adversary.
Refer to caption: x2.png

###### Lemma 1 .

### 3.4 ExSUL : Exp3-IX for Online Selective Generation with Feedback Unlocking

As for the adversarial bandit learner, we leverage Exp3-IX (Neu, 2015),
which is based on EW (Littlestone & Warmuth, 1994) for partial feedback.
The key challenge from full to partial feedback is the slow convergence of learning due to the lack of feedback information.
To address this, we exploit the unique loss function structure of selective generators ([4](https://arxiv.org/html/2506.14067v2#S3.E4)) to unlock feedback of other arms by a chosen arm, dubbed by *feedback unlocking*.
In particular,
by the monotonicity of a selection function in $\tau$, *i.e.,* $\hat{{s}}(\mathbf{x})\coloneqq\mathbbm{1}(f_{t}\geq\tau)$ where $f_{t}\coloneqq f(\mathbf{x}_{t},G(\mathbf{x}_{t}))$ and the definition of a selective generator $\hat{{S}}$,
the following relation among feedback holds, where $e_{t}$ is observed feedback by a chosen arm $\tau_{t}$:

$$ $e_{t}=\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq_{E}\mathbf{y}_{t})=\begin{cases}\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)\neq_{E}\mathbf{y}_{t})\text{~for~}\tau\leq f_{t}&\text{if~}\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}\\ \mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)\neq_{E}\mathbf{y}_{t})\text{~for~}\tau>f_{t}&\text{if~}\hat{{S}}(\mathbf{x}_{t};\tau_{t})=\texttt{IDK}\end{cases}.$ (6) $$

To exploit this feedback unlocking within Exp3-IX,
we propose a novel loss estimator

$$ $\ell_{t}(\tau,\alpha\mid\mathcal{{H}}_{t}({\tau_{t}}))\coloneqq\frac{\ell_{t}(\tau,\alpha)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))\in[0,\infty),$ (7) $$

where
$\gamma_{t}>0$,
$\mathcal{{H}}_{t}({\tau_{t}})\coloneqq\{\tau\in\mathcal{{H}}\mid\tau\leq f_{t}\}$
if $\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}$ and $\mathcal{{H}}_{t}(\tau_{t})\coloneqq\{\tau\in\mathcal{{H}}\mid\tau>f_{t}\}$ otherwise – see Figure [29](https://arxiv.org/html/2506.14067v2#A8.F29) for the visualization of $\mathcal{{H}}_{t}(\tau)$.
With learning rate $\eta_{t}>0$, Algorithm [1](https://arxiv.org/html/2506.14067v2#alg1) presents our fixed-parameter extension of Exp3-IX with partial feedback unlocking.
Note that
our algorithm can be reduced to Exp3-IX by letting $\mathcal{{H}}_{t}({\tau})=\{\tau_{t}\}$ for any $\tau$,
recovering the Exp3-IX estimator in ([9](https://arxiv.org/html/2506.14067v2#A2.E9)) from our estimator ([7](https://arxiv.org/html/2506.14067v2#S3.E7)).
Also, our algorithm does not use $f_{t}$ to choose $\tau_{t}$.

Figure: Algorithm 1 Exp3-IX for Online Selective Generation with Feedback Unlocking (ExSUL)

Regret Bound.
Based on the original proof of Exp3-IX but along with our novel loss estimator ([7](https://arxiv.org/html/2506.14067v2#S3.E7)), our Algorithm [1](https://arxiv.org/html/2506.14067v2#alg1) achieves a sublinear regret bound, which leads to faster convergence of the FDR guarantee by Lemma [1](https://arxiv.org/html/2506.14067v2#Thmlemma1).
See Appendix [H.4](https://arxiv.org/html/2506.14067v2#A8.SS4) for a general proof on our regret bound.

###### Theorem 1 .

Let $\ell_{t}(\cdot)\in[0,1]$ of the form ([4](https://arxiv.org/html/2506.14067v2#S3.E4)).
For any $T\in\mathbb{N}$ and finite hypotheses $\mathcal{{H}}$,
Algorithm [1](https://arxiv.org/html/2506.14067v2#alg1) provides the following regret bound
with probability at least $1-\delta$,
if $\eta=2\gamma=\sqrt{\frac{\ln|\mathcal{H}|}{T}}$:

$$ $\textbf{Reg}_{T}\leq 4\sqrt{T\ln|\mathcal{H}|}+\left(1+\sqrt{\frac{T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}.$ $$

Interestingly,
despite of partial feedback, our algorithm achieves the same upper bound as EW with full feedback, *i.e.,* $\sqrt{{T\ln|\mathcal{{H}}|}/{2}}$, up to a constant factor
due to
our loss estimator with feedback unlocking ([7](https://arxiv.org/html/2506.14067v2#S3.E7))
for rich information, whereas Exp3-IX suffers from an additional factor of $\sqrt{|\mathcal{{H}}|}$, as in ([10](https://arxiv.org/html/2506.14067v2#A2.E10)), due to its loss estimator with limited information.

###### Theorem 1 .

## 4 Experiments

We empirically justify that ExSUL controls the FDR while maximizing selection efficiency under three diverse environments:(1) stochastic, (2) distribution-shift, and (3) interactive environments.

Datasets and Models.
We use two datasets for stochastic and distribution-shift environments, $79\mathrm{K}$ Natural Question (NQ) (Kwiatkowski et al., 2019) and $93\mathrm{K}$ TriviaQA (Joshi et al., 2017) with two base models, GPT-3.5-turbo (OpenAI, 2023) and LLaMA3.1-8B-Instruct (Meta AI, 2024).
We simulate
distribution-shift environments by mixing two datasets in diverse ways and an
interactive environment by generating interaction between two GPT-3.5-turbo models
(see Section [F.2](https://arxiv.org/html/2506.14067v2#A6.SS2) and [F.3](https://arxiv.org/html/2506.14067v2#A6.SS3), respectively for details).
To obtain feedback and self-consistency scores, we use GPT-3.5-turbo.

Scoring functions.
We consider two scoring functions $f_{\texttt{std}}$ and $f_{\texttt{con}}$, introduced in Section [B.1](https://arxiv.org/html/2506.14067v2#A2.SS1).
In short,
$f_{\texttt{std}}$ is a standard log-likelihood score defined as the conditional probability of an answer given a question.
$f_{\texttt{con}}$ is a self-consistency score of an answer computed via entailment scores (from an entailment model) across samples.
We use $f_{\texttt{con}}$ unless specified.

Methods.
We consider two baselines, Exp3-IX-SG and No-SG, and one performance upper bound algorithm, EW-SG.
In particular,
(1) Exp3-IX-SG (Algorithm [6](https://arxiv.org/html/2506.14067v2#alg6)) is an online selective generator with partial feedback by adapting Exp3-IX (Neu, 2015) via our regret-to-FDR conversion lemma.
(2) No-SG is a non-selective generator (*i.e.,* $\tau_{t}=0$ for all $t$), to serve as a standard use of a generator without abstention.
(3) EW-SG (Algorithm [5](https://arxiv.org/html/2506.14067v2#alg5)) is an online selective generator with full feedback.
As it exploits full feedback, we use it as our empirical performance upper bound.

Metrics.
We measure performance of ours along with comparing methods via
the empirical FDR, *i.e.,* $\textbf{FDR}_{t}$ and selection inefficiency, *i.e.,* $\textbf{Ineff}_{t}$.
Note that No-SG achieves zero selection inefficiency by definition, so we do not explicitly add in figures.

Parameters.
We set $|\mathcal{{H}}|=1\mathrm{K}$ and $\lambda=T^{\nicefrac{{1}}{{4}}}$ by default.
Also, a desired FDR level $\alpha$ and
time horizon $T$ depend on tasks,
where $\alpha$ is provided by users.

### 4.1 Stochastic Environment

Figure: (a) FDR over time
Refer to caption: x3.png

In Figure [3](https://arxiv.org/html/2506.14067v2#S4.F3) and [8](https://arxiv.org/html/2506.14067v2#A7.F8), we observe that ExSUL has clearly better convergence speed to the desired FDR compared to Exp3-IX-SG, since Exp3-IX-SG only observes $\ell_{t}(\tau_{t})$, requiring a much longer horizon $T$ (Figure [24](https://arxiv.org/html/2506.14067v2#A7.F24)).
These results demonstrate that our partial feedback unlocking is beneficial in a faster convergence to the desired FDR, supporting the regret bound analysis discussed in Section [3.4](https://arxiv.org/html/2506.14067v2#S3.SS4).

In addition, Figure [22](https://arxiv.org/html/2506.14067v2#A7.F22) shows that our algorithm effectively controls the FDR across different $\alpha$. Moreover, Figure [28](https://arxiv.org/html/2506.14067v2#A7.F28) indicates that the inefficiency loss $a_{t}$ enables the algorithm to achieve efficient FDR guarantees.
Note that algorithms with $f_{\texttt{con}}$ have better controllability over the FDR than those with $f_{\texttt{std}}$ (*e.g.,* Figure [10](https://arxiv.org/html/2506.14067v2#A7.F10) v.s. [12](https://arxiv.org/html/2506.14067v2#A7.F12)), suggesting that a well-calibrated scoring function can have a positive effect on convergence speed.
See additional results in Section [G.1](https://arxiv.org/html/2506.14067v2#A7.SS1).

### 4.2 Distribution-shift Environment

To evaluate the robustness of the methods, we consider three distribution-shift scenarios: (1) a single instantaneous change by concatenating two datasets, (2) frequent shifts by interleaving fixed-size chunks randomly drawn from each dataset, and (3) progressive shifts by sampling each example according to a linearly increasing mixing probability. See Appendix [F.2](https://arxiv.org/html/2506.14067v2#A6.SS2) for details.

Interestingly, in Figure [4](https://arxiv.org/html/2506.14067v2#S4.F4), [5](https://arxiv.org/html/2506.14067v2#S4.F5), and [6](https://arxiv.org/html/2506.14067v2#S4.F6), Exp3-IX-SG exhibits a sharp increase in FDR immediately following the distribution shift, highlighting its sensitivity to sudden changes in the data distribution, while the proposed ExSUL does not.
In addition, Figure [23](https://arxiv.org/html/2506.14067v2#A7.F23) shows that our algorithm still effectively controls the FDR across different $\alpha$ in the distribution shift environment. See additional results on varying generators and shift types in Section [G.2](https://arxiv.org/html/2506.14067v2#A7.SS2) and a longer time horizon in Figure [25](https://arxiv.org/html/2506.14067v2#A7.F25).

Figure: (a) FDR over time
Refer to caption: x6.png

Figure: (a) FDR over time
Refer to caption: x9.png

Figure: (a) FDR over time
Refer to caption: x12.png

### 4.3 Interactive Environment

We empirically demonstrate the efficacy of ExSUL in real-world interactive applications.
In particular,
we simulate an interactive environment by implementing a user-acting agent, a question-answering agent, and an evaluating agent by states,
where these agents interact over multiple turns,
and ExSUL decides whether to abstain from answering as shown in Figure [1](https://arxiv.org/html/2506.14067v2#S1.F1).

In Figure [7](https://arxiv.org/html/2506.14067v2#S4.F7), we observe that ExSUL consistently controls the FDR under $\alpha$, despite the instability of $\textbf{FDR}_{t}$
demonstrating the robustness of ExSUL under frequently shifting distributions over time.
In Figure [1](https://arxiv.org/html/2506.14067v2#S1.F1), ExSUL successfully abstains from incorrect answers, achieving the desired FDR level $\alpha$.

Figure: (a) FDR over time
Refer to caption: x15.png

## 5 Conclusion

We propose a learning algorithm for online selective generation with partial feedback, which provides an FDR controllability guarantee, while allowing $\lambda$ to adjust the trade-off between the selection efficiency and convergence speed.
To this end, we leverage the well-developed adversarial bandit problem.
In particular,
we reduce selective generation to adversarial bandits
and extend
the Exp3-IX algorithm for adversarial bandits by *partial feedback unlocking*, which addresses the lack of feedback information due to the nature of partial feedback.
Finally,
we introduce a novel *Regret-to-FDR conversion lemma* such that we can use any regret minimization algorithm, including our extended Exp3-IX for selective generation to control an FDR at a desired level.
We theoretically and empirically justify our method by providing an efficient regret bound and evaluating diverse learning environments,
including stochastic, distribution-shift, and interactive environments.

Limitations.
The main limitation of our method is that our online selective generator selects a hypothesis independently of the observed input $\mathbf{x}_{t}$. As future work, extending to the contextual bandits, where the input is taken into account when pulling an arm, would be a promising direction.

## Acknowledgment

We appreciate constructive feedback by anonymous reviewers.
This work was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (RS-2019-II191906, Artificial Intelligence Graduate School Program (POSTECH) (5%); RS-2024-00457882, National AI Research Lab Project (20%); No. RS-2024-00509258 and No. RS-2024-00469482, Global AI Frontier Lab (40%); RS-2025-00560062 (35%)).

## References

- Agrawal (1995)
Rajeev Agrawal.
Sample mean based index policies by o (log n) regret for the multi-armed bandit problem.
*Advances in applied probability*, 27(4):1054–1078, 1995.
- Auer et al. (2002)
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.
The nonstochastic multiarmed bandit problem.
*SIAM journal on computing*, 32(1):48–77, 2002.
- Bowman et al. (2015)
Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning.
A large annotated corpus for learning natural language inference.
In *Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing*, pp. 632–642, 2015.
- Bubeck et al. (2012)
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al.
Regret analysis of stochastic and nonstochastic multi-armed bandit problems.
*Foundations and Trends® in Machine Learning*, 5(1):1–122, 2012.
- Cesa-Bianchi & Lugosi (2006)
Nicolo Cesa-Bianchi and Gábor Lugosi.
*Prediction, learning, and games*.
Cambridge university press, 2006.
- Chase (2022)
Harrison Chase.
LangChain, October 2022.
URL [https://github.com/langchain-ai/langchain](https://github.com/langchain-ai/langchain).
- Chen et al. (2017)
Tianyi Chen, Qing Ling, and Georgios B Giannakis.
An online convex optimization approach to proactive network resource allocation.
*IEEE Transactions on Signal Processing*, 65(24):6350–6364, 2017.
- Foster & Rakhlin (2023)
Dylan J. Foster and Alexander Rakhlin.
Foundations of reinforcement learning and interactive decision making, 2023.
URL [https://arxiv.org/abs/2312.16730](https://arxiv.org/abs/2312.16730).
- Ge et al. (2024)
Haosen Ge, Hamsa Bastani, and Osbert Bastani.
Stochastic online conformal prediction with semi-bandit feedback.
*arXiv preprint arXiv:2405.13268*, 2024.
- Geifman & El-Yaniv (2017)
Yonatan Geifman and Ran El-Yaniv.
Selective classification for deep neural networks.
*Advances in neural information processing systems*, 30, 2017.
- Goren et al. (2024)
Shani Goren, Ido Galil, and Ran El-Yaniv.
Hierarchical selective classification.
*arXiv preprint arXiv:2405.11533*, 2024.
- Joshi et al. (2017)
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer.
TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension.
In *Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)*, pp. 1601–1611, Vancouver, Canada, July 2017. Association for Computational Linguistics.
doi: 10.18653/v1/P17-1147.
URL [https://aclanthology.org/P17-1147](https://aclanthology.org/P17-1147).
- Kwiatkowski et al. (2019)
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al.
Natural questions: a benchmark for question answering research.
*Transactions of the Association for Computational Linguistics*, 7:453–466, 2019.
- Lee et al. (2024)
Minjae Lee, Kyungmin Kim, Taesoo Kim, and Sangdon Park.
Selective generation for controllable language models.
In *The Thirty-eighth Annual Conference on Neural Information Processing Systems*, 2024.
URL [https://openreview.net/forum?id=glfYOAzh2f](https://openreview.net/forum?id=glfYOAzh2f).
- Littlestone & Warmuth (1994)
Nick Littlestone and Manfred K Warmuth.
The weighted majority algorithm.
*Information and computation*, 108(2):212–261, 1994.
- Mahdavi et al. (2012)
Mehrdad Mahdavi, Rong Jin, and Tianbao Yang.
Trading regret for efficiency: online convex optimization with long term constraints.
*The Journal of Machine Learning Research*, 13(1):2503–2528, 2012.
- Manakul et al. (2023)
Potsawee Manakul, Adian Liusie, and Mark Gales.
Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models.
In *The 2023 Conference on Empirical Methods in Natural Language Processing*, 2023.
- Meta AI (2024)
Meta AI.
LLaMA 3.1 8B-Instruct model card.
[https://huggingface.co/meta-llama/Llama-3.1-8B-Instruct](https://huggingface.co/meta-llama/Llama-3.1-8B-Instruct), 2024.
- Mohri et al. (2023)
Christopher Mohri, Daniel Andor, Eunsol Choi, and Michael Collins.
Learning to reject with a fixed predictor: Application to decontextualization.
*arXiv preprint arXiv:2301.09044*, 2023.
- Mohri et al. (2012)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
*Foundations of machine learning*.
MIT press, 2012.
- Neu (2015)
Gergely Neu.
Explore no more: Improved high-probability regret bounds for non-stochastic bandits.
*Advances in Neural Information Processing Systems*, 28, 2015.
- OpenAI (2023)
OpenAI.
GPT-3.5-turbo model card.
[https://platform.openai.com/docs/models/gpt-3-5-turbo](https://platform.openai.com/docs/models/gpt-3-5-turbo), 2023.
- Rajpurkar et al. (2016)
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang.
Squad: 100,000+ questions for machine comprehension of text.
*arXiv preprint arXiv:1606.05250*, 2016.
- Russo & Van Roy (2013)
Daniel Russo and Benjamin Van Roy.
Eluder dimension and the sample complexity of optimistic exploration.
*Advances in Neural Information Processing Systems*, 26, 2013.
- Sankararaman (2016)
Karthik Abinav Sankararaman.
Semi-bandit feedback: A survey of results.
*ARXIV CoRR*, 2016.
- Sid-Ali et al. (2024)
Ahmed Sid-Ali, Ioannis Lambadaris, Yiqiang Q Zhao, Gennady Shaikhet, and Amirhossein Asgharnia.
Exponentially weighted algorithm for online network resource allocation with long-term constraints.
*arXiv preprint arXiv:2405.02373*, 2024.
- Sinha & Vaze (2024)
Abhishek Sinha and Rahul Vaze.
Optimal algorithms for online convex optimization with adversarial constraints.
*Advances in Neural Information Processing Systems*, 37:41274–41302, 2024.

## Appendix A LLM Usage

LLMs were used for minor grammar suggestions, and for assistance with code implementation.

## Appendix B Preliminary

We introduce preliminaries on language generation, selective prediction, and adversarial bandits.
To this end,
let
$\mathcal{{X}}$ be a set of inputs (*e.g.,* examples or questions)
and
$\mathcal{{Y}}$ be a set of outputs (*e.g.,* labels or answers).

### B.1 Language Generation

We mainly consider language generators as our model to control hallucination.
In particular,
let $G:\mathcal{{X}}\to\mathcal{{Y}}$ be a language generator, where $\mathcal{{W}}$ is a set of tokens and $\mathcal{{X}}=\mathcal{{Y}}\coloneqq\cup_{i=0}^{\infty}\mathcal{{W}}^{i}$. Here, each $i$-th token $\hat{\mathbf{y}}_{i}$ of a generated answer $\hat{\mathbf{y}}\in\mathcal{{Y}}$ is decoded from
an underlying probability distribution $p(\mathbf{y}\mid\mathbf{x})$, where $p$ is usually learned via language data.
For the decoding strategy, we consider greedy decoding, *i.e.,* $\hat{\mathbf{y}}_{i}=\arg\max_{w\in\mathcal{{W}}}p(w\mid\mathbf{x},\hat{\mathbf{y}}_{1:i-1})$, where $\mathbf{y}_{a:b}\coloneqq(\mathbf{y}_{a},\dots,\mathbf{y}_{b})$.
Given a generated answer $\hat{\mathbf{y}}$, there are multiple ways to measure its likelihood of correctness $f:\mathcal{{X}}\times\mathcal{{Y}}\to\mathbb{R}$.
A standard way $f_{\texttt{std}}$ considers a length-normalized token probability, *i.e.,* $f_{\texttt{std}}(\mathbf{x},\hat{\mathbf{y}})\coloneqq(p(\hat{\mathbf{y}}_{1}\mid\mathbf{x})\prod_{i=2}^{|\hat{\mathbf{y}}|}p(\hat{\mathbf{y}}_{i}\mid\mathbf{x},\mathbf{\hat{y}}_{1:i-1}))^{\nicefrac{{1}}{{|\hat{\mathbf{y}}|}}}$. A better alternative is to consider consistency of $\hat{\mathbf{y}}$ to multiple generated answers with sampling (Manakul et al., 2023), *i.e.,* $f_{\texttt{con}}(\mathbf{x},\hat{\mathbf{y}})=\hat{\mathbbm{E}}_{\mathbf{y}^{\prime}\sim G(x)}f_{E}(\mathbf{y}^{\prime},\hat{\mathbf{y}})$, denoted by a consistency score, where we use sampling for decoding $\mathbf{y}^{\prime}$, $f_{E}(\mathbf{y}^{\prime},\hat{\mathbf{y}})$ measures an entailment score of $\hat{\mathbf{y}}$ given $\mathbf{y}^{\prime}$ (*i.e.,* whether $\mathbf{y}^{\prime}$ entails $\hat{\mathbf{y}}$) via an entailment model (*e.g.,* GPT-3.5-turbo).

### B.2 Selective Prediction

Selective prediction (Geifman & El-Yaniv, 2017) and generation (Lee et al., 2024) provide certified control over the risk of incorrect predictions by abstaining answers (saying IDK) when the prediction is uncertain.
Given a predictor $\hat{\mathbf{y}}:\mathcal{{X}}\to\mathcal{{Y}}$, a selective predictor $\hat{{S}}:\mathcal{{X}}\to\mathcal{{Y}}\cup\{\texttt{IDK}\}$ abstains from returning $\hat{\mathbf{y}}(\mathbf{x})$ if a selection function $\hat{{s}}:\mathcal{{X}}\times\mathcal{{Y}}\to\{0,1\}$ deems the prediction uncertain, *i.e.,* $\hat{{S}}(\mathbf{x})\coloneqq\begin{cases}\hat{\mathbf{y}}(\mathbf{x})&\text{if~}\hat{{s}}(\mathbf{x},\hat{\mathbf{y}}(\mathbf{x}))=1\\
\texttt{IDK}&\text{otherwise}\end{cases}.$
In learning, the selection function $\hat{{s}}$ is chosen to possibly satisfy a desired level of a false discovery rate *i.e.,* $\mathbbm{P}(\hat{{S}}(\mathbf{x})\neq_{E}\mathbf{y}\mid\hat{{S}}(\mathbf{x})\neq\texttt{IDK})$ over the i.i.d. samples of $(\mathbf{x},\mathbf{y})$.
In selective classification (Geifman & El-Yaniv, 2017), the equality relation $\neq_{E}$ is usually the standard exact matching, which is extended to capture semantic correctness via entailment relation in selective generation (Lee et al., 2024).
In contrast to the standard stochastic setup as in the previous literature, we consider online learning under partial feedback.

### B.3 Regret Minimization

Sequential prediction in multi-armed bandit problems is formulated as an interactive game between a learner and an adversary (also called an environment).
In particular, for each time $t\in\{1,\dots,T\}$, a learner selects an arm $\tau_{t}\in\mathcal{{H}}$ among a set of arms $\mathcal{{H}}$ and an adversary selects a loss function $\ell_{t}:\mathcal{{H}}\to\mathbb{R}_{\geq 0}$, where a loss associated to an arm $\tau_{t}$ is denoted by $\ell_{t}(\tau_{t})$ and provided to the learner as partial feedback (*i.e.,* only the loss for the selected arm is provided). Note that this interactive game often describes in rewards, but we consider losses, instead of rewards.

The main goal of this interactive game is to find a learner whose performance is as good as the best learner in hindsight.
Here, the performance is measured by *regret*, following standard bandits literatures (Bubeck et al., 2012), *i.e.,*

$$ $\textbf{Reg}_{T}\coloneqq\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau).$ (8) $$

Thus, the the goal becomes to find a learner that minimizes the regret such that an achieved regret bound is sublinear in $T$.
Here, we say that the adversary is *oblivious* if the sequence of loss functions are chosen regardless of learner’s previous selections
(or chosen in advance before the game),
and the adversary is *adaptive* if the loss function at time $t$, *i.e.,* $\ell_{t}$, is drawn a distribution that depends on the previously chosen arms, *i.e.,* $\tau_{1},\dots,\tau_{t-1}$.
In this paper, we consider the adaptive adversary which is more stronger than the oblivious one. Moreover, under the adaptive adversary setup, a deterministic learner cannot win the game (*i.e.,* it does not achieve a sub-linear regret bound), so we consider a randomized learner.
This implies that $\tau_{t}$ and $\ell_{t}$ are two sources of randomness, so $\textbf{Reg}_{T}$ is a random variable. Thus, we consider the high-probable regret bound or a bound of an expected regret $\mathbbm{E}\textbf{Reg}_{T}$.
Note that we only consider the learner’s randomization in the analysis, since our bounds are derived to hold for any adversary (Bubeck et al., 2012; Neu, 2015).

In the following section, we review
one regret minimization algorithm for bandits with an adaptive adversary, called Exp3-IX, and see Appendix [E](https://arxiv.org/html/2506.14067v2#A5) for other algorithms.

### B.4 Adversarial Bandits and Exp3-IX Algorithm

Traditional online learning typically assumes full feedback, *i.e.,* loss for any hypothesis is computable.
However, practical applications may only have partial feedback, *i.e.,* loss for a chosen hypothesis is only given.
We model this via the adversarial multi-armed bandit problem. The regret is as in online learning, but the learner only receives for a chosen arm, while the sequence $\ell_{t}(\tau_{t})$ is chosen by an oblivious or adaptive adversary that may condition on the history of chosen arms but not on the learner’s fresh randomness at time $t$.

To obtain the high-probability control of the $\textbf{Reg}_{T}$ over an adaptive adversary, Exponential-weights for Exploration and Exploitation with Implicit Exploration (Exp3-IX)(Neu, 2015) is a natural choice. It employs implicit-exploration (IX) loss estimates within an exponential-weights scheme and does not require explicit mixing with the uniform distribution like Exp3.P (Auer et al., 2002). In particular, Exp3-IX uses the variance-reduced loss estimator for each arm $\tau\in\mathcal{{H}}$ constructed from the observed loss of the chosen arm $\tau_{t}$, *i.e.,*

$$ $\displaystyle\tilde{\ell}_{t}(\tau\mid\{\tau_{t}\})\coloneqq\frac{\ell_{t}(\tau)}{\gamma_{t}+p_{t}(\tau)}\cdot\mathbbm{1}(\tau_{t}=\tau)\in[0,\infty).$ (9) $$

where $\gamma_{t}>0$ is properly selected by an analysis; thus by using ([9](https://arxiv.org/html/2506.14067v2#A2.E9)) in $\textbf{Reg}_{T}$, with non-increasing learning rate $\eta_{t}$, we have the following regret with high probability for Exp3-IX .
See Appendix[H.2](https://arxiv.org/html/2506.14067v2#A8.SS2) for a complete proof.

###### Theorem 2 .

(Neu, 2015)
Let $\ell_{t}(\cdot)\in[0,\ell_{\text{max}}]$.
For any $T\in\mathbb{N}$, finite arms $\mathcal{{H}}$,
and
$\delta\in(0,1)$,
Algorithm [4](https://arxiv.org/html/2506.14067v2#alg4) provides the following regret bound with probability at least$1-\delta$ if $\eta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}=\sqrt{{2\ln|\mathcal{H}|}/{(\ell_{\max}^{2}T|\mathcal{H}|)}}$:

$$ $\textbf{Reg}_{T}\leq\ell_{\text{max}}\left(2\sqrt{2T|\mathcal{{H}}|\ln|\mathcal{{H}}|}+\left(1+\sqrt{\frac{T|\mathcal{{H}}|}{2\ln|\mathcal{{H}}|}}\right)\ln\delta^{-1}\right).$ (10) $$

We will exploit Exp3-IX for learning selective generators with partial feedback under an adaptive adversary. See Appendix [D](https://arxiv.org/html/2506.14067v2#A4) for other online learning and bandit algorithms.

###### Theorem 2 .

### B.5 Online Learning and EW Algorithm

Online learning considers to design a learner that adapts to any sequence of full feedback on hypotheses without any or with little assumption on data generation process. In particular,
the goal of an online learner is to
find a distribution $p_{t}$ over hypotheses with full feedback that minimizes the regret.

Along with many online learning algorithms, we introduce
Exponential Weighting (EW) (Littlestone & Warmuth, 1994), which minimizes the regret with finite hypotheses (Algorithm [3](https://arxiv.org/html/2506.14067v2#alg3)).
In particular,
EW maintains the goodness of weights for each hypothesis in terms of cumulative loss and updates them from feedback. The feedback of a hypothesis $\tau_{t}$ at time $t$ is represented by loss $\ell_{t}(\tau_{t})$ but we can compute this loss for all hypotheses other than a chosen hypothesis $\tau_{t}$ as we directly observe a true label $\mathbbm{1}(G(\mathbf{x}_{t})=_{E}\mathbf{y}_{t})$ at the same time $t$. This EW algorithm satisfies the following regret bound. See Appendix [H.1](https://arxiv.org/html/2506.14067v2#A8.SS1) for a proof.

###### Theorem 3 .

(Littlestone & Warmuth, 1994; Foster & Rakhlin, 2023)
Let $\ell_{t}(\cdot)\in[0,\ell_{\text{max}}]$.
For any $T\in\mathbb{N}$ and finite hypotheses $\mathcal{{H}}$,
Algorithm [3](https://arxiv.org/html/2506.14067v2#alg3) provides the following expected regret bound if $\eta=\sqrt{{8\ln|\mathcal{{H}}|}/{(\ell_{\text{max}}^{2}T)}}$:

$$ $\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)\leq\ell_{\text{max}}\sqrt{{T\ln|\mathcal{{H}}|}/{2}}=\mathcal{{O}}(\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|}),$ (11) $$

which holds for arbitrary loss sequences,
thus, implying that $\mathbbm{E}\textbf{Reg}_{T}$ is also bounded by $\mathcal{{O}}(\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|})$ as the linearity of expectation and Tower property.
Moreover, for any $0<\delta<1$, the following regret bound also holds:

$$ $\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)\leq\ell_{\text{max}}\sqrt{\frac{T\ln|\mathcal{{H}}|}{2}}+\ell_{\text{max}}\sqrt{\frac{T\ln\delta^{-1}}{2}},$ $$

with probability at least $1-\delta$.

We will leverage and extend this EW for learning selective generators with full feedback.

###### Theorem 3 .

## Appendix C Additional Related Work

Constrained Online Learning
Several works have studied online learning with constraints. (Mahdavi et al., 2012) first proposes long-term constraints in online convex optimization with time-invariant constraints, which allows to have the constraint function $g_{t}$ to be violated at each time step, *i.e.,* $g(\mathbf{x}_{t})>0$, but eventually satisfied, *i.e.,* $\sum_{t=1}^{T}g(\mathbf{x}_{t})\leq 0$.
Some other works solve a similar problem but with time-varying constraints, which is more challenging.
(Chen et al., 2017; Sid-Ali et al., 2024) solve a network resource allocation task by viewing this as an constrained optimization problem. Especially, (Sid-Ali et al., 2024) solves the problem without a convex assumption on loss.
(Sinha & Vaze, 2024) gives analysis on optimal algorithms for online convex optimization with adversarial constraints.
We similarly consider a FDR guarantee to be satisfied over time but with partial feedback.

Conformal Prediction with Bandit Feedback
There is little work about selective or conformal prediction in bandit settings.
(Ge et al., 2024) proposes an online conformal prediction method with semi-bandit feedback, where we can observe the true label only if it is predicted.
Our method follows the practical motivation in having partial feedback idea but we consider selective generation.

## Appendix D Additional Method

### D.1 Online Selective Generation with Full Feedback

Here, we specifically leverage the conventional exponential weighting (EW) algorithm (Littlestone & Warmuth, 1994) for online learning under adaptive adversaries to re-purpose it for addressing online selective generation with full feedback. This is an oracle method with the performance upper bound of our method with partial feedback.
To this end, we provide the reduction of online selective generation with full feedback to the online learning problem.
Then,
we introduce a modified EW algorithm for selective generation, called EW-SG, followed by its regret bound.
Finally,
we leverage the proposed conversion lemma, which converts the regret bound of any online learning algorithms into the FDR bound, to show the FDR controllability of EW-SG at a desired level.

#### D.1.1 Reduction: From Online Selective Generation to Online Learning

**Table 2: From online selective generation to online learning**
|  | online selective generation | online learning |
| --- | --- | --- |
| models | selective generators $\mathcal{{H}}$ | hypotheses $\mathcal{{H}}$ |
| feedback | $\mathbbm{1}(G(\mathbf{x}_{t})\neq_{E}\mathbf{y}_{t})$ | $\ell_{t}(\tau,\alpha)$ |
| metric | $\textbf{FDR}_{T}$ and $\textbf{Ineff}_{T}$ | $\textbf{Reg}_{T}$ |

We convert online selective generation with full feedback to conventional online learning
(See Table [2](https://arxiv.org/html/2506.14067v2#A4.T2) for a summary).
In selective generation,
models are defined as a set of selective generators $\hat{{S}}$ or equivalently a set of selection parameters $\mathcal{{H}}$, considered as hypotheses $\mathcal{{H}}$ in online learning.
This model is sequentially updated by leveraging online feedback. In particular, we consider feedback whether a generated answer $G(\mathbf{x}_{t})$ is semantically incorrect with respect to a true answer $\mathbf{y}_{t}$, *i.e.,* $\mathbbm{1}(G(\mathbf{x}_{t})\neq_{E}\mathbf{y}_{t})$.
This essentially provides full feedback for any $\tau\in\mathcal{{H}}$ as it is the same as $\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau)\neq_{E}\mathbf{y}_{t})$ by the definition of $\hat{{S}}$ if $\hat{{S}}(\mathbf{x}_{t};\tau)\neq\texttt{IDK}$.
This feedback is converted into loss in online learning, as defined in ([4](https://arxiv.org/html/2506.14067v2#S3.E4)).
Note that $d_{t}$ in the loss leverages the feedback $\mathbbm{1}(G(\mathbf{x}_{t})\neq_{E}\mathbf{y}_{t})$ by the definition.
Finally, our goal of finding a learning algorithm, which controls the FDR by $\alpha$ and minimizes selection inefficiency in online selective generation, is reduced to finding an online learning algorithm that minimizes the regret $\textbf{Reg}_{T}$ with any loss sequences $\ell_{t}(\tau,\alpha)$ in ([4](https://arxiv.org/html/2506.14067v2#S3.E4)).

#### D.1.2 Algorithm and Its Regret Bound

We re-purpose EW for selective generation called EW-SG.
This mainly uses
the special loss
$\ell_{t}(\tau,\alpha)$ in ([4](https://arxiv.org/html/2506.14067v2#S3.E4)) for selective generation.
See Algorithm [5](https://arxiv.org/html/2506.14067v2#alg5) for details.
The corresponding regret bound is directly obtained from Theorem [3](https://arxiv.org/html/2506.14067v2#Thmtheorem3) where $\ell_{\text{max}}\coloneqq\max(\lambda,1+\lambda\alpha)\leq 1+\lambda$.

### D.2 Regret-to-FDR Conversion

Once we devise a regret minimization algorithm, *i.e.,* EW-SG, the regret guarantee is simply interpreted as the FDR guarantee by Lemma [1](https://arxiv.org/html/2506.14067v2#Thmlemma1).
This eventually provides the FDR bound for EW-SG.

## Appendix E Algorithms

Figure: Algorithm 2 Procedure for Computing the Loss ([4](https://arxiv.org/html/2506.14067v2#S3.E4)) with Partial Feedback

Figure: Algorithm 3 Exponential Weighting (EW) (Littlestone & Warmuth, 1994; Foster & Rakhlin, 2023)

Figure: Algorithm 4 Exp3 with Implicit eXploration (Exp3-IX) (Neu, 2015)

Figure: Algorithm 5 Exponential Weighting for Online Selective Generation (EW-SG)

Figure: Algorithm 6 Exp3-IX for Online Selective Generation with Partial Feedback (Exp3-IX-SG)

## Appendix F Experiment Setup

### F.1 Computing Environment

We use 4 NVIDIA A100 80GB with 128 CPUs for experiments.

### F.2 Distribution-shift Environment Setup

We describe the experimental setup used to evaluate the robustness of selective generation by three distinct distribution-shift scenarios. We detail the chunking strategy and the procedure for constructing each shift environment in the following.

Single Shift.
The dataset is composed of two large homogeneous segments, each containing 15$\mathrm{K}$ examples randomly sampled from NQ and TriviaQA. A single distribution shift occurs at the boundary between these two segments.

Alternating Shift. The dataset constructed by a sequence of ten 3$\mathrm{K}$-example chunks that alternate between NQ and TriviaQA (e.g., NQ, TriviaQA, NQ, TriviaQA and so forth). Each chunk induces a distribution transition at its endpoint, resulting in frequent and periodic shifts.

Gradual Shift. This setup generates a smooth distribution change over time by drawing individual samples probabilistically between NQ and TriviaQA, with the sampling probability gradually shifting from pure NQ (or TriviaQA) at the start to pure TriviaQA (or NQ) at the end.
In particular, given a multinomial distribution $[\frac{t}{T},T-\frac{t}{T}]$ for each dataset that changes over time, we first randomly choose a dataset which follows this multinomial distribution, and then we sample one question-answering pair in the sampled dataset.
Over the full sequence length, this creates linear interpolation between the two datasets, enabling analysis of model performance under a progressive distribution shift.

### F.3 Interactive Environment Setup

For the interactive environment, we consider dialog-based conversations.
In particular,
GPT-3.5-Turbo serves as a question-answering agent, while we utilize two GPT-4o APIs, where one is a user-acting agent to generate questions, and another is an evaluating agent, having assess to the responses.

To instruct the user-acting agent to generate questions,
we use the SQuAD (Rajpurkar et al., 2016) dataset,
which consists of many question-answer pairs, each associated with a gold context.
Here, we discard the QA pairs and only use $20,962$ context passages, which vary over a range of topics (*e.g.,* science, history, celebrities, entertainment, etc.), forming a diverse set of natural distributions.
During the simulation, we randomly select a context from the dataset and provide it to the user-acting agent, which is prompted to continuously generate questions based on the given context.
(*e.g.,* Figure [1](https://arxiv.org/html/2506.14067v2#S1.F1)).
To mimic a dynamically shifting environment, *e.g.,* the user’s interest shifts over time, we further instruct the user-acting agent to change the context during the interaction when it determines it is done with the current one (*e.g.,* "When you are done with the current context, say ’SHIFT’ to request a new context.") or after at most 10 question-answering turns.
To design this custom workflow, we implement the core functions of the simulation, including memory handling and multi-turn conversation, using LangGraph, a framework built on LangChain (Chase, 2022).

## Appendix G Additional Experiments

### G.1 Stochastic Environment

Figure: (a) FDR over time
Refer to caption: x17.png

Figure: (a) FDR over time
Refer to caption: x20.png

Figure: (a) FDR over time
Refer to caption: x23.png

Figure: (a) FDR over time
Refer to caption: x26.png

Figure: (a) FDR over time
Refer to caption: x29.png

### G.2 Distribution-shift Environment

#### G.2.1 Single Shift

Figure: (a) FDR over time
Refer to caption: x32.png

Figure: (a) FDR over time
Refer to caption: x35.png

Figure: (a) FDR over time
Refer to caption: x38.png

#### G.2.2 Alternating Shift

Figure: (a) FDR over time
Refer to caption: x41.png

Figure: (a) FDR over time
Refer to caption: x44.png

Figure: (a) FDR over time
Refer to caption: x47.png

#### G.2.3 Gradual Shift

Figure: (a) FDR over time
Refer to caption: x50.png

Figure: (a) FDR over time
Refer to caption: x53.png

Figure: (a) FDR over time
Refer to caption: x56.png

### G.3 Analysis on Time Horizon and Desired FDR Parameters

Figure: (a) NQ dataset along with GPT-3.5-Turbo
Refer to caption: x59.png

Figure: (a) TrviaQA shifts to NQ with GPT-3.5-Turbo
Refer to caption: x63.png

Figure: (a) NQ dataset along with GPT-3.5-Turbo
Refer to caption: x67.png

Figure: (a) NQ dataset shift to TriviaQA dataset along with GPT-3.5-Turbo
Refer to caption: x71.png

### G.4 Analysis on Varying λ \lambda

Figure: (a) NQ dataset along with GPT-3.5-Turbo
Refer to caption: x75.png

Figure: (a) NQ dataset along with GPT-3.5-Turbo
Refer to caption: x79.png

### G.5 Ablation Study

Figure: (a) FDR over time
Refer to caption: x83.png

## Appendix H Proofs

### H.1 A Proof of Theorem 3

We follow the standard proof (Foster & Rakhlin, 2023), followed by extending it for a loss range with $[0,\ell_{\text{max}}]$.

Let the cumulative loss of the $i$-th hypothesis $\tau_{i}\in\mathcal{{H}}$ be $L_{t}^{i}\coloneqq\sum_{s=1}^{t}\ell_{t}(\tau_{i})$,
$W_{t}\coloneqq\sum_{i=1}^{|\mathcal{{H}}|}\exp\left\{-\eta L_{t}^{i}\right\}$.

The upper bound of $\ln\frac{W_{t}}{W_{t-1}}$.
We have the following upper bound of $\ln\frac{W_{t}}{W_{t-1}}$:

$$ $\displaystyle\ln\frac{W_{t}}{W_{t-1}}$ $\displaystyle=\ln\frac{\sum_{i=1}^{|\mathcal{{H}}|}\exp\left\{-\eta L_{t}^{i}\right\}}{\sum_{i=1}^{|\mathcal{{H}}|}\exp\{-\eta L_{t-1}^{i}\}}$ $\displaystyle=\ln\sum_{i=1}^{|\mathcal{{H}}|}\exp\left\{-\eta\ell_{t}(\tau_{i})\right\}\frac{\exp\{-\eta L_{t-1}^{i}\}}{\sum_{i=1}^{|\mathcal{{H}}|}\exp\{-\eta L_{t-1}^{i}\}}$ $\displaystyle=\ln\mathbbm{E}_{\tau_{t}\sim p_{t}}\exp\left\{-\eta\ell_{t}(\tau_{t})\right\}$ $\displaystyle\leq-\eta\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})+\frac{\eta^{2}\ell_{\text{max}}^{2}}{8},$ (12) $$

where ([12](https://arxiv.org/html/2506.14067v2#A8.E12)) holds by the Hoeffding’s lemma and the fact that $\ell_{t}(\tau_{i})\in[0,\ell_{\text{max}}]$.
Thus, we have

$$ $\ln\frac{W_{T}}{W_{0}}=\sum_{t=1}^{T}\ln\frac{W_{t}}{W_{t-1}}\leq-\eta\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})+\frac{\eta^{2}\ell_{\text{max}}^{2}T}{8}.$ $$

The lower bound of $\ln\frac{W_{t}}{W_{t-1}}$.
We have the lower bound of $\ln\frac{W_{t}}{W_{t-1}}$ as follows:

$$ $\displaystyle\ln{\frac{W_{T}}{W_{0}}}=\ln\sum_{i=1}^{|\mathcal{{H}}|}\exp\{-\eta L_{T}^{i}\}-\ln|\mathcal{{H}}|$ $\displaystyle\geq\ln\left(\max_{i\in\{1,\dots,|\mathcal{{H}}|\}}\exp\{-\eta L^{i}_{T}\}\right)-\ln|\mathcal{{H}}|$ $\displaystyle=-\eta\min_{i\in\{1,\dots,|\mathcal{{H}}|\}}L^{i}_{T}-\ln|\mathcal{{H}}|$ $\displaystyle=-\eta\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)-\ln|\mathcal{{H}}|.$ $$

Combine the lower and upper bounds.
If we combine the lower bound and the upper bound, we obtain the following inequality:

$$ $\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)\leq\frac{\eta\ell_{\text{max}}^{2}T}{8}+\frac{\ln|\mathcal{{H}}|}{\eta}.$ $$

If $\eta=\sqrt{8\ln|\mathcal{{H}}|/\ell_{\text{max}}^{2}T}$,

$$ $\displaystyle\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)$ $\displaystyle\leq\ell_{\text{max}}\sqrt{\frac{T\ln|\mathcal{{H}}|}{2}}.$ (13) $$

Since the guarantee in ([13](https://arxiv.org/html/2506.14067v2#A8.E13)) holds for any sequence of loss functions in EW, the bound is also valid against an adaptive adversary. Furthermore, the expected regret is given by $\mathbbm{E}\left[\textbf{Reg}_{T}\right]=\mathbbm{E}\left[\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)\right],$ which follows from the tower property of expectation.

High probability bound.
Moreover, we have

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)$ $\displaystyle=\left(\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\right)+\left(\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)\right).$ $$

Since $\mathbbm{E}_{t}\left[\ell_{t}(\tau_{t})-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\right]=0$, which implies that $\sum_{t=1}^{T}\left[\ell_{t}(\tau_{t})-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\right]$ is a martingale,
we can use Hoeffding-Azuma inequality

$$ $\displaystyle\mathbbm{P}\left(\sum_{t=1}^{T}\left[\ell_{t}(\tau_{t})-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\right]\geq\varepsilon\right)\leq\exp\left(-\frac{2\varepsilon^{2}}{\sum_{t=1}^{T}c_{t}^{2}}\right)$ $$

for all $\varepsilon\geq 0$ where $c_{t}=\ell_{\text{max}}$ since $\ell_{t}(\tau_{t})-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\in[-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t}),\ell_{\text{max}}-\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})]$.

Thus, if we put $\delta=\exp\left(-\frac{2\varepsilon^{2}}{T\ell_{\text{max}}^{2}}\right)$ we get

$$ $\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\sum_{t=1}^{T}\mathbbm{E}_{\tau_{t}\sim p_{t}}\ell_{t}(\tau_{t})\leq\ell_{\text{max}}\sqrt{\frac{T\ln\delta^{-1}}{2}},$ $$

with probability at least $1-\delta$,
which suggests that

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)$ $\displaystyle\leq\frac{\eta\ell_{\text{max}}^{2}T}{8}+\frac{\ln|\mathcal{{H}}|}{\eta}+\ell_{\text{max}}\sqrt{\frac{T\ln\delta^{-1}}{2}}$ $$

with probability at least $1-\delta$.

If $\eta=\sqrt{8\ln|\mathcal{{H}}|/\ell_{\text{max}}^{2}T}$,

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\ell_{t}(\tau)$ $\displaystyle\leq\ell_{\text{max}}\sqrt{\frac{T\ln|\mathcal{{H}}|}{2}}+\ell_{\text{max}}\sqrt{\frac{T\ln\delta^{-1}}{2}}.$ (14) $$

### H.2 A Proof of Theorem 2

This proof follows standard proof (Neu, 2015) but with a non-trivial loss range $[0,\ell_{\text{max}}]$.
Recall that $\ell_{t}(\tau)\in[0,\ell_{\text{max}}]$ and its biased estimator $\tilde{\ell}_{t}(\tau\mid\{\tau_{t}\})\in[0,\infty)$, as defined in ([9](https://arxiv.org/html/2506.14067v2#A2.E9)).

We first introduce new Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16) and Corollary [23](https://arxiv.org/html/2506.14067v2#A8.E23) that establish a high probability bound between the loss estimator and the empirical loss. Corollary [23](https://arxiv.org/html/2506.14067v2#A8.E23) provides a bound for a fixed value of $\tau$, and its proof follows directly from the Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16) by applying a union bound. Together, Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16) and Corollary [23](https://arxiv.org/html/2506.14067v2#A8.E23) allow us to translate the upper bound on the estimator equation into a high-probability regret bound.

###### Lemma 2 .

Let $\gamma_{t}\geq 0$ for $t\in\{1,2,\dots,T\}$ be a fixed non-increasing sequence and $\alpha_{t,\tau}$ be a real value that satisfies $\alpha_{t,\tau}\leq 2\gamma_{t}$ for all $t\in\mathbb{N}$ and $\tau\in\mathcal{{H}}$. Then, we have

$$ $\sum_{t=1}^{T}\sum_{\tau\in\mathcal{{H}}}\alpha_{t,\tau}\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\ell_{t}(\tau)\right)\leq\ell_{\text{max}}\ln\frac{1}{\delta},$ $$

with probability $1-\delta$.

###### Proof.

First, letting $\beta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}$, we have

$$ $\displaystyle\ell_{t}(\tau\mid\{\tau_{t}\})$ $\displaystyle=\frac{\ell_{t}(\tau)}{p_{t}(\tau)+\gamma_{t}}\cdot\mathbbm{1}(\tau_{t}=\tau)$ $\displaystyle=\ell_{\text{max}}\cdot\frac{\ell_{t}(\tau)/\ell_{\text{max}}}{p_{t}(\tau)+\gamma_{t}}\cdot\mathbbm{1}(\tau_{t}=\tau)$ $\displaystyle\leq\ell_{\text{max}}\cdot\frac{\ell_{t}(\tau)/\ell_{\text{max}}}{p_{t}(\tau)+\gamma_{t}\cdot\ell_{t}(\tau)/\ell_{\text{max}}}\cdot\mathbbm{1}(\tau_{t}=\tau)$ $\displaystyle=\frac{\ell_{\text{max}}}{2\gamma_{t}}\cdot\frac{2\gamma_{t}\cdot\frac{\ell_{t}(\tau)}{\ell_{\text{max}}p_{t}(\tau)}}{1+\gamma_{t}\cdot\frac{\ell_{t}(\tau)}{\ell_{\text{max}}p_{t}(\tau)}}\mathbbm{1}(\tau_{t}=\tau)$ $\displaystyle\leq\frac{\ell_{\text{max}}}{2\gamma_{t}}\cdot\ln\left(1+2\gamma_{t}\cdot\frac{\ell_{t}(\tau)}{\ell_{\text{max}}p_{t}(\tau)}\mathbbm{1}(\tau_{t}=\tau)\right)$ (15) $\displaystyle=\frac{1}{\beta_{t}}\cdot\ln\left(1+\beta_{t}\frac{\ell_{t}(\tau)}{p_{t}(\tau)}\mathbbm{1}(\tau_{t}=\tau)\right)$ (16) $$

where the inequality ([15](https://arxiv.org/html/2506.14067v2#A8.E15)) holds by $\frac{x}{1+x/2}\leq\ln(1+x)$ for $x\geq 0$ and the range $\{0,1\}$ of the indicator function.

Second, we explicitly define the following auxiliary quantities:

$$ $\tilde{S}_{t}=\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\ell_{t}(\tau\mid\{\tau_{t}\})\quad\text{and}\quad S_{t}=\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\ell_{t}(\tau).$ $$

Denoting by $\mathbbm{E}_{t}$ the conditional expectation with respect to $\tau_{t}$, given the past learner’s choices $\tau_{1},\ldots,\tau_{t-1}$, we have the following relation between $\tilde{S}_{t}$ and $S_{t}$:

$$ $\displaystyle\mathbbm{E}_{t}\left[\exp\tilde{S}_{t}\right]$ $\displaystyle\leq\mathbbm{E}_{t}\left[\exp\left(\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}\beta_{t}}\cdot\ln\left(1+\beta_{t}\cdot\frac{\ell_{t}(\tau)}{p_{t}(\tau)}\mathbbm{1}(\tau_{t}=\tau)\right)\right)\right]$ (17) $\displaystyle=\mathbbm{E}_{t}\left[\prod_{\tau\in\mathcal{{H}}}\left(1+\beta_{t}\frac{\ell_{t}(\tau)}{p_{t}(\tau)}\mathbbm{1}(\tau_{t}=\tau)\right)^{\frac{\alpha_{t,\tau}}{\ell_{\text{max}}\beta_{t}}}\right]$ $\displaystyle\leq\mathbbm{E}_{t}\left[1+\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\cdot\frac{\ell_{t}(\tau)}{p_{t}(\tau)}\cdot\mathbbm{1}(\tau_{t}=\tau)\right]$ (18) $\displaystyle\leq 1+\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\cdot\ell_{t}(\tau)$ $\displaystyle\leq\exp\left(\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\cdot\ell_{t}(\tau)\right)=\exp\left(S_{t}\right).$ (19) $$

Here, the inequality ([17](https://arxiv.org/html/2506.14067v2#A8.E17)) follows directly from ([16](https://arxiv.org/html/2506.14067v2#A8.E16)). Subsequently, ([18](https://arxiv.org/html/2506.14067v2#A8.E18)) is obtained by applying the Bernoulli inequality $(1+z)^{a}\leq(1+az)$ which is valid for $z\geq 0$ and $0\leq a\leq 1$ and the condition of $\alpha_{t}\leq 2\gamma_{t}$, followed by the property of the indicator function.

Finally we define:

$$ $\displaystyle W_{t}:=\exp\left(\sum_{i=1}^{t}\big(\tilde{S}_{i}-S_{i}\big)\right).$ $$

This immediately implies that $W_{t}=W_{t-1}\cdot\exp\left(\tilde{S}_{t}-S_{t}\right)$.
Taking the conditional expectation with respect to $\tau_{t}$, we obtain

$$ $\displaystyle\mathbbm{E}_{t}[W_{t}]$ $\displaystyle=\mathbbm{E}_{t}\left[W_{t-1}\cdot\exp\left(\tilde{S}_{t}-S_{t}\right)\right]$ $\displaystyle=W_{t-1}\mathbbm{E}_{t}\left[\exp\left(\tilde{S}_{t}-S_{t}\right)\right]$ $\displaystyle=W_{t-1}\exp\left(-S_{t}\right)\mathbbm{E}_{t}\left[\exp\left(\tilde{S}_{t}\right)\right]$ (20) $\displaystyle\leq W_{t-1}\exp\left(-S_{t}\right)\exp\left(S_{t}\right)$ (21) $\displaystyle\leq W_{t-1},$ (22) $$

where ([20](https://arxiv.org/html/2506.14067v2#A8.E20)) $W_{t-1}$ and $S_{t}$ are dependent on the history up to time $t-1$, we pull $W_{t-1}$ and $\exp(-S_{t})$ outside of the conditional expectation.
Also, ([21](https://arxiv.org/html/2506.14067v2#A8.E21)) holds due to ([19](https://arxiv.org/html/2506.14067v2#A8.E19)).

From
([22](https://arxiv.org/html/2506.14067v2#A8.E22)),
we have $\mathbbm{E}_{T}[W_{T}]\leq\mathbbm{E}_{T-1}[W_{T-1}]\leq\dots\leq\mathbbm{E}_{0}[W_{0}]$.
As $W_{0}=1$, we have $\mathbbm{E}_{T}[W_{T}]\leq 1$.

Then, by this and the Markov’s inequality, we have

$$ $\displaystyle\mathbbm{P}\left(\sum_{t=1}^{T}(\tilde{S}_{t}-S_{t})>\ln\frac{1}{\delta}\right)=\mathbbm{P}\left(W_{T}>\frac{1}{\delta}\right)\leq\delta\mathbbm{E}_{T}[W_{T}]\leq\delta.$ $$

Recall that $\ln W_{T}=\sum_{t=1}^{T}\left(\tilde{S}_{t}-S_{t}\right)=\sum_{t=1}^{T}\sum_{\tau\in\mathcal{{H}}}\frac{\alpha_{t,\tau}}{\ell_{\text{max}}}\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\ell_{t}(\tau)\right)$ then we have

$$ $\displaystyle\sum_{t=1}^{T}\sum_{\tau\in\mathcal{{H}}}\alpha_{t,\tau}\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\ell_{t}(\tau)\right)\leq\ell_{\text{max}}\ln\frac{1}{\delta}$ $$

with probability at least $1-\delta$, which completes the proof.
∎

###### Corollary 1 .

Let $\gamma_{t}\geq\gamma>0$ for all $t$.
Simultaneously for all $\tau\in\mathcal{{H}}$, we have

$$ $\sum_{t=1}^{T}\ell_{t}(\tau\mid\{\tau_{t}\})-\sum_{t=1}^{T}\ell_{t}(\tau)\leq\frac{\ell_{\text{max}}}{2\gamma}\ln\frac{|\mathcal{{H}}|}{\delta}$ (23) $$

with probability $1-\delta$.

###### Proof.

For each $\bar{\tau}\in\mathcal{{H}}$, let $\alpha_{t,\tau}\coloneqq 2\gamma\mathbbm{1}(\tau=\bar{\tau})\leq 2\gamma_{t}$, which satisfies the condition for Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16). Then, due to Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16), we have

$$ $\displaystyle\ell_{\text{max}}\ln\frac{|\mathcal{{H}}|}{\delta}$ $\displaystyle\geq\sum_{t=1}^{T}\sum_{\tau\in\mathcal{{H}}}\alpha_{t,\tau}\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\ell_{t}(\tau)\right)$ $\displaystyle=\sum_{t=1}^{T}\sum_{\tau\in\mathcal{{H}}}2\gamma\mathbbm{1}(\tau=\bar{\tau})\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\ell_{t}(\tau)\right)$ $\displaystyle=\sum_{t=1}^{T}2\gamma\left(\ell_{t}(\bar{\tau}\mid\{\tau_{t}\})-\ell_{t}(\bar{\tau})\right)$ $$

with probability at least $1-\frac{\delta}{|\mathcal{{H}}|}$.
By taking the union bound for all $\bar{\tau}\in\mathcal{{H}}$, we complete the proof.
∎

Then, we provide the main proof.

###### Lemma 2 .

###### Proof.

###### Corollary 1 .

###### Proof.

##### First step.

We split the expected loss estimator into two logarithmic terms (Bubeck et al., 2012, Eq. (3.7)): a variability term and the log of an exponential expectation. We will rewrite each term in the following steps.

$$ $\mathbbm{E}_{\tau\sim p_{t}}\ell(\tau\mid\{\tau_{t}\})=\frac{1}{\eta_{t}}\underbrace{\ln\mathbbm{E}_{\tau\sim p_{t}}\exp\Big(-\eta_{t}\Big(\ell_{t}(\tau\mid\{\tau_{t}\})-\mathbbm{E}_{\bar{\tau}\sim p_{t}}\ell_{t}(\bar{\tau}\mid\{\tau_{t}\})\Big)\Big)}_{\text{variability term}}\\ -\frac{1}{\eta_{t}}\underbrace{\ln\mathbbm{E}_{\tau\sim p_{t}}\exp\Big(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\Big)}_{\text{log of an exponential expectation term}}.$ (24) $$

##### Second step.

We provide an upper bound on the variability term.

$$ $\displaystyle\ln\mathbbm{E}_{\tau}\exp\Big(-\eta_{t}$ $\displaystyle\left(\ell_{t}(\tau\mid\{\tau_{t}\})-\mathbbm{E}_{\bar{\tau}}\ell_{t}(\bar{\tau}\mid\{{\tau}_{t}\})\right)\Big)$ $\displaystyle=\ln\mathbbm{E}_{\tau}\exp\Big(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})+\eta_{t}\mathbbm{E}_{\bar{\tau}}\ell(\bar{\tau}\mid\{\tau_{t}\})\Big)$ $\displaystyle=\ln\mathbbm{E}_{\tau}\exp\Big(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\Big)+\ln\exp\Big(\eta_{t}\mathbbm{E}_{\bar{\tau}}\ell(\bar{\tau}\mid\{\tau_{t}\})\Big)$ $\displaystyle\leq\mathbbm{E}_{\tau}\exp\left(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\right)-1+\eta_{t}\mathbbm{E}_{\bar{\tau}}\ell(\bar{\tau}\mid\{\tau_{t}\})$ (25) $\displaystyle\leq\mathbbm{E}_{\tau}\Big[\exp\left(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\right)-1+\eta_{t}\ell(\tau\mid\{\tau_{t}\})\Big]$ $\displaystyle\leq\mathbbm{E}_{\tau}\eta_{t}^{2}\frac{{\ell_{t}(\tau\mid\{\tau_{t}\})}^{2}}{2}$ (26) $\displaystyle=\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau){\ell_{t}(\tau\mid\{\tau_{t}\})}^{2}$ $\displaystyle=\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\left(\frac{\ell_{t}(\tau)}{p_{t}(\tau)+\gamma_{t}}\cdot\mathbbm{1}(\tau_{t}=\tau)\right)\ell_{t}(\tau\mid\{\tau_{t}\})$ $\displaystyle\leq\frac{\ell_{\text{max}}\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\}),$ (27) $$

where
([25](https://arxiv.org/html/2506.14067v2#A8.E25)) holds due to $\ln(x)\leq x-1$ for $x\leq 1$, and ([26](https://arxiv.org/html/2506.14067v2#A8.E26)) uses $\exp(x)\leq 1+x+x^{2}/2$ for $x\leq 0$.

##### Third step.

Let $\tilde{L}_{t}(\tau)\coloneqq\sum_{i=1}^{t}\ell_{i}(\tau\mid\{\tau_{i}\})$ and $\tilde{L}_{0}(\tau)=0$. Then, we have

$$ $\displaystyle-\frac{1}{\eta_{t}}\ln\mathbbm{E}_{\tau\sim p_{t}}\exp$ $\displaystyle\bigg(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\exp\bigg(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\sum_{\tau\in\mathcal{{H}}}\frac{\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}{\sum_{\bar{\tau}\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\bar{\tau}))}\exp\bigg(-\eta_{t}\ell_{t}(\tau\mid\{\tau_{t}\})\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}.$ (28) $$

##### Fourth step.

We combine rewritten forms to continue the derivation as follows:

$$ $\displaystyle\sum_{t=1}^{T}\mathbbm{E}_{\tau\sim p_{t}}$ $\displaystyle\ell(\tau\mid\{\tau_{t}\})$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})-\sum_{t=1}^{T}\frac{1}{\eta_{t}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t}(\tau)\right)}{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t-1}(\tau)\right)}$ (29) $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})-\frac{1}{\eta_{T}}\sum_{t=1}^{T}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t}(\tau)\right)}{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t-1}(\tau)\right)}$ (30) $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})-\frac{1}{\eta_{T}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{T}\tilde{L}_{T}(\tau)\right)}{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{0}\tilde{L}_{0}(\tau)\right)}$ $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})-\frac{1}{\eta_{T}}\ln\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{T}\tilde{L}_{T}(\tau)\right)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{T}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})-\frac{1}{\eta_{T}}\ln\left(\max_{\tau}\exp\left(-\eta_{T}\tilde{L}_{T}(\tau)\right)\right)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}$ $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})+\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\{\tau_{t}\})+\frac{\ln|\mathcal{{H}}|}{\eta_{T}},$ (31) $$

where ([29](https://arxiv.org/html/2506.14067v2#A8.E29)) holds from
([24](https://arxiv.org/html/2506.14067v2#A8.E24)),
([27](https://arxiv.org/html/2506.14067v2#A8.E27)), and
([28](https://arxiv.org/html/2506.14067v2#A8.E28)).
Also,
([30](https://arxiv.org/html/2506.14067v2#A8.E30)) holds as
$\eta_{t}$ is non-increasing
and
$\frac{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t}(\tau)\right)}{\sum_{\tau\in\mathcal{{H}}}\exp\left(-\eta_{t}\tilde{L}_{t-1}(\tau)\right)}\leq 1$.

Note that
$\mathbbm{E}_{\tau\sim p_{t}}\ell(\tau\mid\{\tau_{t}\})=\ell_{t}(\tau_{t})-\gamma_{t}\sum_{\tau\in\mathcal{{H}}}\ell(\tau\mid\{\tau_{t}\})$ for the following reason:

$$ $\displaystyle\mathbbm{E}_{\tau\sim p_{t}}\ell_{t}(\tau\mid\{\tau_{t}\})$ $\displaystyle=\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\frac{\ell_{t}(\tau)}{p_{t}(\tau)+\gamma_{t}}\mathbbm{1}(\tau_{t}=\tau)$ $\displaystyle=\sum_{\tau\in\mathcal{{H}}}\left(\frac{p_{t}(\tau)+\gamma_{t}}{p_{t}(\tau)+\gamma_{t}}\ell_{t}(\tau)\mathbbm{1}(\tau_{t}=\tau)-\frac{\gamma_{t}}{p_{t}(\tau)+\gamma_{t}}\ell_{t}(\tau)\mathbbm{1}(\tau_{t}=\tau)\right)$ $\displaystyle=\ell_{t}(\tau_{t})-\gamma_{t}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\}).$ $$

From this fact and ([31](https://arxiv.org/html/2506.14067v2#A8.E31)), we have

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\{\tau_{t}\})$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})+\sum_{t=1}^{T}\gamma_{t}\sum_{\tau\in\mathcal{{H}}}\ell(\tau\mid\{\tau_{t}\})+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}$ $\displaystyle=\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau\mid\{\tau_{t}\})+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}.$ (32) $$

If $\eta_{t}\leq\frac{2\gamma_{t}}{\ell_{\text{max}}}$ then it satisfies the Lemma condition *i.e.,* $\alpha_{t,\tau}=\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\leq 2\gamma_{t}$, we can apply Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16), from ([32](https://arxiv.org/html/2506.14067v2#A8.E32)) to get

$$ $\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\{\tau_{t}\})\leq\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}$ $$

with probability $1-\delta/2$.

After that, by Corollary [23](https://arxiv.org/html/2506.14067v2#A8.E23), we get

$$ $\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau)\leq\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\{\tau_{t}\})+\frac{\ell_{\text{max}}}{2\gamma}\ln\frac{2|\mathcal{{H}}|}{\delta}$ $$

with probability $1-\delta/2$.

Finally, we get combining the above two via the union bound as follows:

$$ $\textbf{Reg}_{T}=\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau)\\ \leq\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}+\frac{\ell_{\text{max}}}{2\gamma}\ln\frac{2|\mathcal{{H}}|}{\delta}$ $$

with probability $1-\delta$.

The concluding steps of our proof closely follow the analysis presented by (Neu, 2015).
Recall that if the learning rate $\eta_{t}\leq\frac{2\gamma_{t}}{\ell_{\max}}$ it satisfies the conditions of Lemma [2](https://arxiv.org/html/2506.14067v2#A8.Ex16).
Then, letting $\eta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}$ and $\gamma=\frac{\eta_{T}\ell_{\text{max}}}{2}$
due to Corollary [23](https://arxiv.org/html/2506.14067v2#A8.E23), we can bound the regret bound as follows:

$$ $\displaystyle\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)$ $\displaystyle\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}+\frac{\ell_{\text{max}}}{2\gamma}\ln\frac{2|\mathcal{{H}}|}{\delta}$ $\displaystyle=\sum_{t=1}^{T}\ell_{\text{max}}\eta_{t}\sum_{\tau\in\mathcal{{H}}}\ell_{t}(\tau)+\frac{2\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}+\frac{1}{\eta_{T}}\ln\frac{2}{\delta}$ $\displaystyle\leq\sum_{t=1}^{T}\ell_{\text{max}}^{2}|\mathcal{{H}}|\eta_{t}+\frac{2\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}+\frac{1}{\eta_{T}}\ln\frac{2}{\delta}.$ (33) $$

First, we consider the setting with a known time horizon. In this case, we use a fixed learning rate, $\eta_{t}=\eta_{T}$ for all $t$, which simplifies the general regret bound to:

$$ $\textbf{Reg}_{T}\leq\ell_{\text{max}}^{2}T|\mathcal{{H}}|\eta_{T}+\frac{2\ln|\mathcal{{H}}|}{\eta_{T}}+\ell_{\text{max}}\ln\frac{2}{\delta}+\frac{1}{\eta_{T}}\ln\frac{2}{\delta}.$ (34) $$

Finally, we can get the optimal learning rate $\eta_{t}=\sqrt{\frac{2\ln|\mathcal{{H}}|+\ln(2/\delta)}{\ell_{\max}^{2}T|\mathcal{{H}}|}}$.
Here, to make the learning rate agnostic to $\delta$, we approximate
$\eta_{t}\approx\sqrt{\frac{2\ln|\mathcal{{H}}|}{\ell_{\max}^{2}T|\mathcal{{H}}|}}$, which follows
the convention in the original analysis (Neu, 2015).

Then, from ([34](https://arxiv.org/html/2506.14067v2#A8.E34)), we obtain the following upper bound:

$$ $\displaystyle\textbf{Reg}_{T}$ $\displaystyle\leq\ell_{\text{max}}\left(2\sqrt{2T|\mathcal{{H}}|\ln|\mathcal{{H}}|}+\left(1+\sqrt{\frac{T|\mathcal{{H}}|}{2\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}\right)$ $\displaystyle=\mathcal{O}\left(2\ell_{\text{max}}\sqrt{2T|\mathcal{{H}}|\ln|\mathcal{{H}}|/\delta}\right).$ (35) $$

Second, for the setting with a unknown time horizon, we use the learning rate $\eta_{t}=\sqrt{\frac{\ln|\mathcal{{H}}|}{\ell_{\max}^{2}t|\mathcal{{H}}|}}$. Then we get general regret bound from ([33](https://arxiv.org/html/2506.14067v2#A8.E33)), noting that $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$

$$ $\displaystyle\textbf{Reg}_{T}$ $\displaystyle\leq\ell_{\text{max}}\left(4\sqrt{T|\mathcal{{H}}|\ln|\mathcal{{H}}|}+\left(1+\sqrt{\frac{T|\mathcal{{H}}|}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}\right)$ $\displaystyle=\mathcal{O}\left(4\ell_{\text{max}}\sqrt{T|\mathcal{{H}}|\ln|\mathcal{{H}}|/\delta}\right).$ $$

##### Expected regret

The expected regret can be obtained via integrating the deviations in ([35](https://arxiv.org/html/2506.14067v2#A8.E35)), *i.e.,*

$$ $\mathbbm{E}[W]\leq\int_{0}^{2}\frac{1}{2\delta}\mathbbm{P}\left(W>\ln\frac{2}{\delta}\right)d\delta.$ $$

Here, if we take $W=\frac{1}{\ell_{\text{max}}\left(1+\sqrt{T|\mathcal{{H}}|/(2\ln|\mathcal{{H}}|)}\right)}\left(\textbf{Reg}_{T}-2\ell_{\text{max}}\sqrt{2T|\mathcal{{H}}|\ln|\mathcal{{H}}|}\right)>\ln\frac{2}{\delta}$ with probability $\delta$
then

$$ $\mathbbm{E}[W]\leq 1,$ $$

which suggests that

$$ $\mathbbm{E}[\textbf{Reg}_{T}]\leq\ell_{\text{max}}\left(2\sqrt{2T|\mathcal{{H}}|\ln|\mathcal{{H}}|}+1+\sqrt{\frac{T|\mathcal{{H}}|}{2\ln|\mathcal{{H}}|}}\right)=\mathcal{{O}}(\ell_{\text{max}}\sqrt{T|\mathcal{{H}}|\ln|\mathcal{{H}}|}).$ (36) $$

### H.3 A Proof of Lemma 1

We derive a lower bound of $\textbf{Reg}_{T}$ which consists of $\textbf{FDR}_{T}$.
In particular, from the definition of $\textbf{Reg}_{T}$ and loss $\ell_{t}(\tau_{,}\alpha)$ in ([4](https://arxiv.org/html/2506.14067v2#S3.E4)), we have the following:

$$ $\displaystyle(1+\lambda)\textbf{Reg}_{T}$ $\displaystyle=\sum_{t=1}^{T}\Big[a_{t}(\tau_{t})+\lambda d_{t}(\tau_{t},\alpha)\Big]-\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\left[a_{t}(\tau)+\lambda d_{t}(\tau,\alpha)\right]$ $\displaystyle\geq\sum_{t=1}^{T}\Big[a_{t}(\tau_{t})+\lambda d_{t}(\tau_{t},\alpha)\Big]-\sum_{t=1}^{T}a_{t}(\overline{\tau})-\sum_{t=1}^{T}\lambda d_{t}(\overline{\tau},\alpha)$ (37) $\displaystyle=\sum_{t=1}^{T}\left[a_{t}(\tau_{t})-a_{t}(\overline{\tau})\right]+\sum_{t=1}^{T}\lambda d_{t}(\tau_{t},\alpha)-\sum_{t=1}^{T}\lambda d_{t}(\overline{\tau},\alpha)$ $\displaystyle\geq T(\textbf{Ineff}_{T}-1)+\sum_{t=1}^{T}\lambda d_{t}(\tau_{t},\alpha)-\sum_{t=1}^{T}\lambda d_{t}(\overline{\tau},\alpha),$ (38) $$

where
([37](https://arxiv.org/html/2506.14067v2#A8.E37)) holds as
$\overline{\tau}=\arg\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\lambda d_{t}({\tau},\alpha)$, implying

$$ $\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}\left[a_{t}(\tau)+\lambda d_{t}(\tau,\alpha)\right]\leq\sum_{t=1}^{T}\left[a_{t}(\overline{\tau})+\lambda d_{t}(\overline{\tau},\alpha)\right]$ $$

and
([38](https://arxiv.org/html/2506.14067v2#A8.E38)) holds as $a_{t}(\tau)\in[0,1]$ for any $t$ and $\tau$.

This implies that

$$ $\displaystyle\sum_{t=1}^{T}d_{t}(\tau_{t},\alpha)$ $\displaystyle\leq\frac{T(1-\textbf{Ineff}_{T})+(1+\lambda)\textbf{Reg}_{T}}{\lambda}+\min_{\tau\in\mathcal{{H}}}\sum_{t=1}^{T}d_{t}({\tau},\alpha)$ $$

Then,
by the definition of $d_{t}(\tau_{t},\alpha)$,
we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}$ $\displaystyle\left[\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}\wedge e_{t}\right)-\alpha\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}\right)+\alpha\right]$ $\displaystyle\leq\frac{(1-\textbf{Ineff}_{T})+(1+\lambda)\textbf{Reg}_{T}/T}{\lambda}+\min_{\tau\in\mathcal{{H}}}\frac{1}{T}\sum_{t=1}^{T}d_{t}({\tau},\alpha),$ $$

which implies

$$ $\displaystyle\mathcal{{R}}_{T}^{\textbf{FDR}}$ $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\left[\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}\wedge e_{t}\right)-\alpha\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau_{t})\neq\texttt{IDK}\right)\right]$ $\displaystyle\leq\frac{(1-\textbf{Ineff}_{T})+(1+\lambda)\textbf{Reg}_{T}/T}{\lambda}+\min_{\tau\in\mathcal{{H}}}\frac{1}{T}\sum_{t=1}^{T}d_{t}({\tau},\alpha)-\alpha$ $\displaystyle\leq\frac{(1-\textbf{Ineff}_{T})+{(1+\lambda)\textbf{Reg}_{T}/T}}{\lambda},$ (39) $$

where ([39](https://arxiv.org/html/2506.14067v2#A8.E39)) holds as $\tau^{\prime}=1$ (*i.e.,* always abstaining) satisfies the following:

$$ $\min_{\tau\in\mathcal{{H}}}\frac{1}{T}\sum_{t=1}^{T}d_{t}({\tau},\alpha)\leq\frac{1}{T}\sum_{t=1}^{T}d_{t}({\tau^{\prime}},\alpha)=\alpha.$ $$

If we take $\lambda=T^{\nicefrac{{1}}{{4}}}$,

$$ $\mathcal{{R}}_{T}^{\textbf{FDR}}\leq\frac{(1-\textbf{Ineff}_{T})}{T^{\nicefrac{{1}}{{4}}}}+\frac{(1+T^{\nicefrac{{1}}{{4}}})\textbf{Reg}_{T}}{T^{\nicefrac{{5}}{{4}}}},$ $$

which completes the proof.

###### Remark .

Finally, we clarify that $\textbf{Ineff}_{T}$ depends on the capability of $G$, the calibration of $f$, and the choice of $\lambda$. In particular, a larger $\lambda$ accelerates convergence but also increases $\textbf{Ineff}_{T}$. Therefore, in practice, choosing a moderately small $\lambda$ can achieve high efficiency while still satisfying the desired FDR under fast convergence.

Nevertheless, if the model or the scoring function $f$ is severely inaccurate, one may heuristically increase $\lambda$ to a large value so that the learner approaches the performance of the best expert that always guarantees the FDR if achievable (Section [I](https://arxiv.org/html/2506.14067v2#A9) for discussion on selection efficiency). In this sense, the exponent $d\in\mathbb{R}^{+}$ in $\lambda=\mathcal{O}(T^{d})$ acts as a hyperparameter of the algorithm.

In our implementation and experiments, we set $\lambda=T^{1/4}$. For empirical trends under different values of $\lambda$, see Figure [26](https://arxiv.org/html/2506.14067v2#A7.F26) and [27](https://arxiv.org/html/2506.14067v2#A7.F27).

###### Remark .

### H.4 A Proof of Theorem 1

Here, we derive a novel regret bound of our algorithm, Theorem [4](https://arxiv.org/html/2506.14067v2#Thmtheorem4), which is a general case of our main Theorem [1](https://arxiv.org/html/2506.14067v2#Thmtheorem1) when the loss range is arbitrarily bounded, *i.e.,* $\in\ell_{t}(\cdot)\in[0,\ell_{\text{max}}]$ and the learning rate $\eta$ is non-increasing function in time $t$.

###### Theorem 4 .

Let $\ell_{t}(\cdot)\in[0,\ell_{\text{max}}]$ with the form of ([4](https://arxiv.org/html/2506.14067v2#S3.E4)).
For any $T\in\mathbb{N}$ and finite hypotheses $\mathcal{{H}}$,
Algorithm [1](https://arxiv.org/html/2506.14067v2#alg1) provides the following regret bound
with probability at least $1-\delta$
if $\eta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}=\sqrt{\frac{\ln|\mathcal{H}|}{\ell_{\text{max}}^{2}T}}$

$$ $\textbf{Reg}_{T}\leq\ell_{\text{max}}\left(4\sqrt{T\ln|\mathcal{H}|}+\left(1+\sqrt{\frac{T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}\right).$ $$

The proof technique follows that of the Exp3-IX (Neu, 2015) regret bound except that we use a novel loss estimator for feedback unlocking.
Note that we abbreviate $\ell_{t}(\tau,\alpha\mid\mathcal{{H}}_{t}(\tau_{t}))$ as $\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ in this proof.

First,
we introduce some properties of
$\mathcal{{H}}_{t}(\tau_{t})$ in our algorithm.

Figure: (a) Case for $\tau>f_{t}$

- 1.
(self-inclusion) The first trivial property is that $\tau$ is in $\mathcal{{H}}_{t}(\tau)$ itself:
$\tau\in\mathcal{{H}}_{t}(\tau).$
(40)
- 2.
(partition) The second property is that if $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)$, then we have
$\mathcal{{H}}_{t}(\tau^{\prime})=\mathcal{{H}}_{t}(\tau).$
(41)
This holds since
if $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)$ and $\tau\in\mathcal{{H}}_{t}(\tau)$ due to ([40](https://arxiv.org/html/2506.14067v2#A8.E40)),
$\tau$ and $\tau^{\prime}$ are in the same side from $f_{t}$
(*i.e.,* either $\tau\leq f_{t}\wedge\tau^{\prime}\leq f_{t}$ or $\tau>f_{t}\wedge\tau^{\prime}>f_{t}$), thus
$\hat{{S}}(\mathbf{x}_{t};\tau)=\hat{{S}}(\mathbf{x}_{t};\tau^{\prime})$, implying
$\mathcal{{H}}_{t}(\tau^{\prime})=\mathcal{{H}}_{t}(\tau)$ by our construction of $\mathcal{{H}}_{t}(\cdot)$ in our algorithm.
The second case when $\tau\in\mathcal{{H}}_{t}(\tau^{\prime})$ similarly holds as well.
- 3.
(complement) The third property, similar to the second one, is that
if $\tau^{\prime}\in\mathcal{{H}}_{t}^{C}(\tau)$,
then we have
$\displaystyle\mathcal{{H}}_{t}^{C}(\tau)=\mathcal{{H}}_{t}(\tau^{\prime}),\text{ or equivalently }\mathcal{{H}}_{t}(\tau)=\mathcal{{H}}_{t}^{C}(\tau^{\prime}).$
(42)
This property holds as follows:
$\tau^{\prime}\in\mathcal{{H}}_{t}(\tau^{\prime})$ holds due to ([40](https://arxiv.org/html/2506.14067v2#A8.E40)).
Suppose $\tau^{\prime}\in\mathcal{{H}}_{t}^{C}(\tau)$, then
we have $\tau^{\prime}\notin\mathcal{{H}}_{t}(\tau)$.
This along with $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau^{\prime})$
implies $\mathcal{{H}}_{t}(\tau^{\prime})\neq\mathcal{{H}}_{t}(\tau)$.
Since $\mathcal{{H}}_{t}(\tau_{t})$ is either $\{\tau\mid\tau\leq f_{t}\}$ or $\{\tau\mid\tau>f_{t}\}$ depending on the value of $\tau_{t}$, $\mathcal{{H}}_{t}(\cdot)$ partitions the space $[0,1]$ into two disjoint sets based on $f_{t}$,
where one set is the complement of the other.
Therefore, $\mathcal{{H}}_{t}(\tau)\neq\mathcal{{H}}_{t}(\tau^{\prime})$ is equivalent to either $\mathcal{{H}}_{t}^{C}(\tau)=\mathcal{{H}}_{t}(\tau^{\prime})$ or $\mathcal{{H}}_{t}(\tau)=\mathcal{{H}}_{t}^{C}(\tau^{\prime})$.
- 4.
(swap) The final property is that
$\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)\quad\text{if and only if}\quad\tau\in\mathcal{{H}}_{t}(\tau^{\prime}).$
(43)
Suppose that $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)$ and $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau^{\prime})$, then the above holds as follows:
$\displaystyle\tau\in\mathcal{{H}}_{t}(\tau)=\mathcal{{H}}_{t}(\tau^{\prime}),$
where
the inclusion holds due to ([40](https://arxiv.org/html/2506.14067v2#A8.E40))
and
the equality holds due to ([41](https://arxiv.org/html/2506.14067v2#A8.E41)) if $\tau^{\prime},\tau\in\mathcal{{H}}_{t}(\tau)$. The reverse holds similarly as well.

With these properties, we can derive the following two useful equalities.
Let

$$ $\hat{\ell}_{t}(\tau\mid\mathcal{{H}}(\tau_{t}))=\frac{\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}})),$ $$

which is our loss estimator without $\gamma_{t}$.
Then, the following equality holds:

$$ $\displaystyle\mathbbm{E}_{\tau_{t}\sim p_{t}}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=\sum_{\tau^{\prime}\in\mathcal{{H}}}p_{t}(\tau^{\prime})\left[\frac{\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau^{\prime}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau^{\prime}}))\right]$ $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau^{\prime}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau^{\prime}}))$ $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau^{\prime})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\mathbbm{1}({\tau^{\prime}\in\mathcal{{H}}_{t}({\tau})})$ (44) $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau^{\prime})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}$ (45) $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}$ (46) $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}\mathbbm{1}(\bar{\tau}\in\mathcal{{H}}_{t}({\tau}))\cdot p_{t}(\bar{\tau})}$ (47) $\displaystyle=\ell_{t}(\tau)\sum_{\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)}\frac{p_{t}(\tau^{\prime})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}$ $\displaystyle=\ell_{t}(\tau),$ (48) $$

where
([44](https://arxiv.org/html/2506.14067v2#A8.E44)) holds as ([43](https://arxiv.org/html/2506.14067v2#A8.E43)),
([45](https://arxiv.org/html/2506.14067v2#A8.E45)) follows from the properties of the summation and indicator function,
([46](https://arxiv.org/html/2506.14067v2#A8.E46)) holds as
([41](https://arxiv.org/html/2506.14067v2#A8.E41)) from $\tau^{\prime}\in\mathcal{{H}}_{t}(\tau)$ in the summation,
and ([47](https://arxiv.org/html/2506.14067v2#A8.E47))
follows by the same argument as ([44](https://arxiv.org/html/2506.14067v2#A8.E44)) from the property ([43](https://arxiv.org/html/2506.14067v2#A8.E43)),
*i.e.,* $\bar{\tau}\in\mathcal{{H}}_{t}(\tau)\text{~if~}\tau\in\mathcal{{H}}_{t}(\bar{\tau})$.

Also, the following equality with respect to our loss estimator ([7](https://arxiv.org/html/2506.14067v2#S3.E7)) holds similarly:

$$ $\displaystyle\mathbbm{E}_{\tau\sim p_{t}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle=\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}(\bar{\tau}))p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle=\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}(\bar{\tau}))p_{t}(\bar{\tau})}$ $\displaystyle=\ell_{t}(\tau_{t})\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}\frac{p_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}(\bar{\tau}))p_{t}(\bar{\tau})}$ (49) $\displaystyle=\ell_{t}(\tau_{t})\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}\frac{p_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\bar{\tau})}$ (50) $\displaystyle=\ell_{t}(\tau_{t})\frac{\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\bar{\tau})}$ $\displaystyle=\ell_{t}(\tau_{t})\frac{\gamma_{t}+\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\bar{\tau})}-\ell_{t}(\tau_{t})\frac{\gamma_{t}}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\bar{\tau})}$ (51) $\displaystyle=\ell_{t}(\tau_{t})-\gamma_{t}\frac{\ell_{t}(\tau_{t})}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}\mathbbm{1}(\tau_{t}\in\mathcal{{H}}_{t}(\bar{\tau}))p_{t}(\bar{\tau})}\mathbbm{1}(\tau_{t}\in\mathcal{{H}}_{t}(\tau_{t}))$ (52) $\displaystyle=\ell_{t}(\tau_{t})-\gamma_{t}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t})),$ (53) $$

where ([49](https://arxiv.org/html/2506.14067v2#A8.E49)) holds as $\ell_{t}(\tau)=\ell_{t}(\tau^{\prime})$ for all $\tau\in\mathcal{{H}}(\tau^{\prime})$ by the definition of the specialized loss in ([4](https://arxiv.org/html/2506.14067v2#S3.E4)), ([50](https://arxiv.org/html/2506.14067v2#A8.E50)) holds as the same as ([47](https://arxiv.org/html/2506.14067v2#A8.E47)), ([51](https://arxiv.org/html/2506.14067v2#A8.E51)) holds as $\tau_{t}\in\mathcal{{H}}_{t}(\tau_{t})$ and ([43](https://arxiv.org/html/2506.14067v2#A8.E43)),
([52](https://arxiv.org/html/2506.14067v2#A8.E52)) holds due to the property of the indicator function,
and
([53](https://arxiv.org/html/2506.14067v2#A8.E53)) holds by the definition.

Then, we first introduce a new Lemma [54](https://arxiv.org/html/2506.14067v2#A8.E54) and Corollary [63](https://arxiv.org/html/2506.14067v2#A8.E63) to establish a high probability bound.

###### Lemma 3 .

Let $\alpha_{t}\leq 2\gamma_{t}$ where $\gamma_{t}$ is non-increasing in $t$. Then, the following inequality holds with probability at least $1-\delta$:

$$ $\sum_{t=1}^{T}\alpha_{t}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\sum_{t=1}^{T}{2\alpha_{t}\ell_{\text{max}}}\leq\ell_{\text{max}}\ln(1/\delta).$ (54) $$

###### Proof.

First, the following inequality holds for any $\tau\in\mathcal{{H}}$:

$$ $\displaystyle\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle=\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=\ell_{\text{max}}\cdot\frac{\ell_{t}(\tau)/\ell_{\text{max}}}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle\leq\ell_{\text{max}}\cdot\frac{\ell_{t}(\tau)/\ell_{\text{max}}}{\gamma_{t}\ell_{t}(\tau)/\ell_{\text{max}}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=\frac{\ell_{\text{max}}}{2\gamma_{t}}\cdot\frac{2\gamma_{t}\ell_{t}(\tau)/\ell_{\text{max}}}{\gamma_{t}\ell_{t}(\tau)/\ell_{\text{max}}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=\frac{1}{\beta_{t}}\cdot\frac{\frac{\beta_{t}\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}}{\frac{\beta\ell_{t}(\tau)}{2\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}+1}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=\frac{1}{\beta_{t}}\cdot\frac{\frac{\beta_{t}\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))}{\frac{\beta_{t}\ell_{t}(\tau)}{2\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))+1}$ $\displaystyle=\frac{1}{\beta_{t}}\cdot\frac{\beta_{t}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))}{\beta_{t}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))/2+1}$ $\displaystyle\leq\frac{1}{\beta_{t}}\cdot\ln\left(1+\beta_{t}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right),$ (55) $$

where $\beta_{t}=2\gamma_{t}/\ell_{\text{max}}$, $\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\coloneqq\frac{\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$, and the last inequality holds as $\frac{x}{1+x/2}\leq\ln(1+x)$ for all $x\geq 0$.

Let $\mathbbm{E}_{t}$ be the expectation conditioned on $\tau_{1},\dots,\tau_{t-1}$
and $\tau^{\prime}$ be any element in $\mathcal{{H}}$.
Then, we have

$$ $\displaystyle\mathbbm{E}_{t}$ $\displaystyle\left[\exp\left(\frac{\alpha_{t}}{\ell_{\text{max}}}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right]$ $\displaystyle\leq\mathbbm{E}_{t}\left[\exp\left(\frac{\alpha_{t}}{\ell_{\text{max}}\beta_{t}}\ln\left(1+\beta_{t}\hat{\ell}_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right)\right]$ (56) $\displaystyle\leq\mathbbm{E}_{t}\left[1+\frac{\alpha_{t}}{\ell_{\text{max}}}\hat{\ell}_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))\right]$ (57) $\displaystyle=1+\frac{\alpha_{t}}{\ell_{\text{max}}}\mathbbm{E}_{t}\hat{\ell}_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle=1+\frac{\alpha_{t}}{\ell_{\text{max}}}\sum_{\tau_{t}\in\mathcal{{H}}}p_{t}(\tau_{t})\frac{\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))$ $\displaystyle=1+\frac{\alpha_{t}}{\ell_{\text{max}}}\sum_{\tau_{t}\in\mathcal{{H}}}p_{t}(\tau_{t})\frac{\ell_{t}(\tau_{t})}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\bar{\tau})}$ $\displaystyle=1+\frac{\alpha_{t}}{\ell_{\text{max}}}\left(\sum_{\tau\in\mathcal{{H}}_{t}(\tau^{\prime})}\frac{p_{t}(\tau)\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}+\sum_{\tau\in\mathcal{{H}}_{t}^{C}(\tau^{\prime})}\frac{p_{t}(\tau)\ell_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}\right)$ $\displaystyle\leq 1+\frac{\alpha_{t}}{\ell_{\text{max}}}\ell_{\text{max}}\left(\sum_{\tau\in\mathcal{{H}}_{t}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}+\sum_{\tau\in\mathcal{{H}}_{t}^{C}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}\right)$ $\displaystyle=1+\alpha_{t}\left(\sum_{\tau\in\mathcal{{H}}_{t}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau^{\prime}})}p_{t}(\bar{\tau})}+\sum_{\tau\in\mathcal{{H}}_{t}^{C}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}(\tau)}p_{t}(\bar{\tau})}\right)$ (58) $\displaystyle=1+\alpha_{t}\left(\sum_{\tau\in\mathcal{{H}}_{t}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau^{\prime}})}p_{t}(\bar{\tau})}+\sum_{\tau\in\mathcal{{H}}_{t}^{C}(\tau^{\prime})}\frac{p_{t}(\tau)}{\sum_{\bar{\tau}\in{\mathcal{{H}}_{t}^{C}(\tau^{\prime})}}p_{t}(\bar{\tau})}\right)$ (59) $\displaystyle\leq 1+2\alpha_{t}$ (60) $\displaystyle\leq\exp(2\alpha_{t}),$ (61) $$

where
([56](https://arxiv.org/html/2506.14067v2#A8.E56) holds as ([55](https://arxiv.org/html/2506.14067v2#A8.E55)).
([57](https://arxiv.org/html/2506.14067v2#A8.E57)) uses $x\ln(1+y)\leq\ln(1+xy)$ for all $y>-1$ and $x\in[0,1]$ since $\alpha_{t}\leq 2\gamma_{t}=\ell_{\text{max}}\beta_{t}$.
([58](https://arxiv.org/html/2506.14067v2#A8.E58)) holds as ([41](https://arxiv.org/html/2506.14067v2#A8.E41)), *i.e.,* $\mathcal{{H}}_{t}(\tau)=\mathcal{{H}}_{t}(\tau_{t})$ due to $\tau\in\mathcal{{H}}_{t}(\tau_{t})$ in the summation.
Also,
([59](https://arxiv.org/html/2506.14067v2#A8.E59)) holds due to ([42](https://arxiv.org/html/2506.14067v2#A8.E42)),
*i.e.,* $\mathcal{{H}}_{t}(\tau)=\mathcal{{H}}_{t}^{C}(\tau_{t})$ as $\tau\in\mathcal{{H}}_{t}^{C}(\tau_{t})$ from the summation condition.
Finally, ([60](https://arxiv.org/html/2506.14067v2#A8.E60)) holds with the equality unless $\mathcal{{H}}_{t}(\tau)=\emptyset$ or $\mathcal{{H}}_{t}^{C}(\tau)=\emptyset$, *i.e.,* $f_{t}=0$, in which case the inequality holds.

Thus, we can find that $W_{t}\coloneqq\exp\left(\sum_{s=1}^{t}\frac{\alpha_{s}}{\ell_{\text{max}}}\left(\ell_{s}(\tau_{s}\mid\mathcal{{H}}_{s}(\tau_{s}))-2\ell_{\text{max}}\right)\right)$ is a supermartingale with respect to $\mathbbm{E}_{t}$, *i.e.,* $\mathbbm{E}_{t}\left[W_{t}\right]\leq W_{t-1}$ as follows:

$$ $\displaystyle\mathbbm{E}_{t}[W_{t}]$ $\displaystyle=\mathbbm{E}_{t}\left[W_{t-1}\exp\left(\frac{\alpha_{s}}{\ell_{\text{max}}}\left(\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-2\ell_{\text{max}}\right)\right)\right]$ $\displaystyle=W_{t-1}\mathbbm{E}_{t}\left[\exp\left(\frac{\alpha_{s}}{\ell_{\text{max}}}\left(\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-2\ell_{\text{max}}\right)\right)\right]$ $\displaystyle=W_{t-1}\mathbbm{E}_{t}\left[\exp\left(\frac{\alpha_{s}}{\ell_{\text{max}}}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right]\exp\left(-2\alpha_{s}\right)$ $\displaystyle\leq W_{t-1}\exp\left(2\alpha_{t}\right)\exp\left(-2\alpha_{s}\right)$ (62) $\displaystyle=W_{t-1},$ $$

where ([62](https://arxiv.org/html/2506.14067v2#A8.E62)) holds due to ([61](https://arxiv.org/html/2506.14067v2#A8.E61)).
Due to $W_{0}=1$ by the definition, the above implies $\mathbbm{E}\left[W_{T}\right]\leq 1$.
Then, by applying this with the Markov’s inequality, we have

$$ $\displaystyle\mathbbm{P}\left(\sum_{t=1}^{T}\frac{\alpha_{t}}{\ell_{\text{max}}}\left(\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-2\ell_{\text{max}}\right)>\ln\frac{1}{\delta}\right)=\mathbbm{P}\left(W_{T}>\frac{1}{\delta}\right)\leq\delta\mathbbm{E}_{T}[W_{T}]\leq\delta.$ $$

Thus,

$$ $\sum_{t=1}^{T}\frac{\alpha_{t}}{\ell_{\text{max}}}\left(\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-2\ell_{\text{max}}\right)\leq\ln(1/\delta),$ $$

with probability at least $1-\delta$, which completes the proof.
∎

###### Corollary 2 .

Let $\gamma_{t}=\gamma>0$ for all $t$. Then, simultaneously for all $\tau\in\mathcal{{H}}$,

$$ $\sum_{t=1}^{T}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\sum_{t=1}^{T}\ell_{t}(\tau)\leq\frac{\ell_{\text{max}}\ln(|\mathcal{{H}}|/\delta)}{2\gamma},$ (63) $$

with probability at least $1-\delta$.

###### Proof.

The proof of this corollary can be derived from Lemma [54](https://arxiv.org/html/2506.14067v2#A8.E54),
but here we provide a direct proof, which uses similar proof techniques as in Lemma [54](https://arxiv.org/html/2506.14067v2#A8.E54).

Let $\gamma_{t}=\gamma\geq 0$.
Then, we have

$$ $\displaystyle\mathbbm{E}_{t}\left[\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right]$ $\displaystyle\leq\mathbbm{E}_{t}\left[\exp\left(\frac{2\gamma}{\ell_{\text{max}}\beta}\ln\left(1+\beta\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right)\right]$ (64) $\displaystyle\leq\mathbbm{E}_{t}\left[1+\frac{2\gamma}{\ell_{\text{max}}}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right]$ (65) $\displaystyle=1+\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau)$ (66) $\displaystyle\leq\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau)\right),$ (67) $$

where ([64](https://arxiv.org/html/2506.14067v2#A8.E64)) holds same as ([55](https://arxiv.org/html/2506.14067v2#A8.E55)) with fixed $\gamma_{t}=\gamma$ and $\beta_{t}=\beta$ for all $t$.
Also, ([65](https://arxiv.org/html/2506.14067v2#A8.E65)) uses $x\ln(1+y)\leq\ln(1+xy)$ for all $y>-1$ and $x\in[0,1]$ along with the fact that $2\gamma=\ell_{\text{max}}\beta$ and thus $\frac{2\gamma}{\beta\ell_{\text{max}}}=1$.
([66](https://arxiv.org/html/2506.14067v2#A8.E66)) holds as $\mathbbm{E}_{t}\hat{\ell}_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))=\ell_{t}(\tau)$ from [48](https://arxiv.org/html/2506.14067v2#A8.E48).

Thus, we can find that $W_{t}\coloneqq\exp\left(\sum_{s=1}^{t}\frac{2\gamma}{\ell_{\text{max}}}\left(\ell_{s}(\tau\mid\mathcal{{H}}_{s}(\tau_{s}))-\ell_{s}(\tau)\right)\right)$ is a supermartingale
with respect to $\mathbbm{E}_{t}$, *i.e.,* $\mathbbm{E}\left[W_{t}\right]\leq W_{t-1}$ as follows:

$$ $\displaystyle\mathbbm{E}_{t}\left[W_{t}\right]$ $\displaystyle=\mathbbm{E}_{t}\left[W_{t-1}\cdot\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\left(\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\ell_{t}(\tau)\right)\right)\right]$ $\displaystyle=W_{t-1}\mathbbm{E}_{t}\left[\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\left(\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\ell_{t}(\tau)\right)\right)\right]$ $\displaystyle=W_{t-1}\mathbbm{E}_{t}\left[\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right)\right]\exp\left(-\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau)\right)$ $\displaystyle\leq W_{t-1}\exp\left(\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau)\right)\exp\left(-\frac{2\gamma}{\ell_{\text{max}}}\ell_{t}(\tau)\right)$ (68) $\displaystyle=W_{t-1}.$ $$

where ([68](https://arxiv.org/html/2506.14067v2#A8.E68)) holds as ([67](https://arxiv.org/html/2506.14067v2#A8.E67)).
From this and $W_{0}=1$ by the definition, we have $\mathbbm{E}\left[W_{T}\right]\leq\mathbbm{E}\left[W_{T-1}\right]\leq\dots\leq 1$.
By this and the Markov’s inequality, we have

$$ $\displaystyle\mathbbm{P}\left(\sum_{t=1}^{T}\frac{2\gamma}{\ell_{\text{max}}}\left(\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\ell_{t}(\tau)\right)>\ln\frac{1}{\delta}\right)=\mathbbm{P}\left(W_{T}>\frac{1}{\delta}\right)\leq\delta\mathbbm{E}_{T}[W_{T}]\leq\delta.$ $$

Then, by the union bound, for all $\tau$, we have

$$ $\sum_{t=1}^{T}\left(\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\ell_{t}(\tau)\right)\leq\frac{\ell_{\text{max}}\ln(|\mathcal{{H}}|/\delta)}{2\gamma}$ $$

with probability at least $1-\delta$, which completes the proof.

∎

We then prove our main theorem, which consists of four steps.

###### Theorem 4 .

###### Lemma 3 .

###### Proof.

###### Corollary 2 .

###### Proof.

##### First step.

We split the expected loss estimator into two logarithmic terms (Bubeck et al., 2012, Eq. (3.7)):

$$ $\mathbbm{E}_{\tau\sim p_{t}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))=\frac{1}{\eta_{t}}\underbrace{\ln\mathbbm{E}_{\tau\sim p_{t}}\exp\bigg(-\eta_{t}\Big(\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\mathbbm{E}_{\bar{\tau}\sim p_{t}}\ell_{t}(\bar{\tau}\mid\mathcal{{H}}_{t}(\tau_{t}))\Big)\bigg)}_{\text{variability term}}\\ -\frac{1}{\eta_{t}}\underbrace{\ln\mathbbm{E}_{\tau\sim p_{t}}\exp\bigg(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\bigg)}_{\text{log of an exponential expectation term}},$ (69) $$

where $\eta_{t}$ is non-increasing in $t\in\mathbb{N}$.
In the following steps, each term will be rewritten.

##### Second step.

We provide an upper bound on the first term:

$$ $\displaystyle\ln\mathbbm{E}_{\tau\sim p_{t}}$ $\displaystyle\exp\left(-\eta_{t}\Big(\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))-\mathbbm{E}_{\bar{\tau}\sim w_{t}}\ell_{t}(\bar{\tau}\mid\mathcal{{H}}_{t}(\tau_{t}))\Big)\right)$ $\displaystyle=\ln\mathbbm{E}_{\tau\sim p_{t}}\exp\big(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\big)+\eta_{t}\mathbbm{E}_{\bar{\tau}\sim p_{t}}\ell_{t}(\bar{\tau}\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle\leq\mathbbm{E}_{\tau\sim p_{t}}\left[\exp\big(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\big)-1+\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\right]$ (70) $\displaystyle\leq\mathbbm{E}_{\tau\sim p_{t}}\eta_{t}^{2}\frac{\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))^{2}}{2}$ (71) $\displaystyle\leq\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))^{2}$ $\displaystyle=\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\left(\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}}))\right)^{2}$ $\displaystyle=\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)\left(\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\right)^{2}$ $\displaystyle=\frac{\eta_{t}^{2}}{2}\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)\left(\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}p_{t}(\bar{\tau})}\right)^{2}$ (72) $\displaystyle=\frac{\eta_{t}^{2}}{2}\frac{\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)\ell_{t}(\tau)^{2}}{\left(\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}p_{t}(\bar{\tau})\right)^{2}}$ $\displaystyle\leq\frac{\ell_{\text{max}}\eta_{t}^{2}}{2}\frac{\sum_{\tau\in\mathcal{{H}}_{t}(\tau_{t})}p_{t}(\tau)}{\left(\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}p_{t}(\bar{\tau})\right)^{2}}\ell_{t}(\tau_{t})$ (73) $\displaystyle\leq\frac{\ell_{\text{max}}\eta_{t}^{2}}{2}\frac{\ell_{t}(\tau_{t})}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}p_{t}(\bar{\tau})}$ $\displaystyle=\frac{\ell_{\text{max}}\eta_{t}^{2}}{2}\frac{\ell_{t}(\tau)}{\gamma_{t}+\sum_{\bar{\tau}\in\mathcal{{H}}_{t}({\tau_{t}})}\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\bar{\tau}}))\cdot p_{t}(\bar{\tau})}\cdot\mathbbm{1}(\tau\in\mathcal{{H}}_{t}({\tau_{t}})),$ (74) $\displaystyle=\frac{\ell_{\text{max}}\eta_{t}^{2}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t})),$ (75) $$

where ([70](https://arxiv.org/html/2506.14067v2#A8.E70)) holds due to $\ln(x)\leq x-1$ for $x\leq 1$,
([71](https://arxiv.org/html/2506.14067v2#A8.E71)) uses $\exp(x)\leq 1+x+x^{2}/2$ for $x\leq 0$,
([72](https://arxiv.org/html/2506.14067v2#A8.E72)) holds as the same as ([50](https://arxiv.org/html/2506.14067v2#A8.E50)),
([73](https://arxiv.org/html/2506.14067v2#A8.E73)) holds as $\ell_{t}(\tau)=\ell_{t}(\tau^{\prime})$ for all $\tau\in\mathcal{{H}}(\tau^{\prime})$ by the definition of the specialized loss ([4](https://arxiv.org/html/2506.14067v2#S3.E4)) and its domain $[0,\ell_{\text{max}}]$,
and ([74](https://arxiv.org/html/2506.14067v2#A8.E74)) holds as the same as ([52](https://arxiv.org/html/2506.14067v2#A8.E52)), *i.e.,* the property of the indicator function.

##### Third step.

Next, we reformulate
the second term, the log of an exponential expectation term.
Let $\tilde{L}_{t}(\tau)\coloneqq\sum_{t=1}^{T}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ and $\tilde{L}_{0}(\tau)=0$. Then, we have

$$ $\displaystyle-\frac{1}{\eta_{t}}\ln\mathbbm{E}_{\tau\sim p_{t}}\exp$ $\displaystyle\bigg(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\sum_{\tau\in\mathcal{{H}}}p_{t}(\tau)\exp\bigg(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\sum_{\tau\in\mathcal{{H}}}\frac{\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}{\sum_{\bar{\tau}\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\bar{\tau}))}\exp\bigg(-\eta_{t}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))\bigg)$ $\displaystyle=-\frac{1}{\eta_{t}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}.$ (76) $$

##### Fourth step.

Then, combining rewritten terms, ([75](https://arxiv.org/html/2506.14067v2#A8.E75)) and ([76](https://arxiv.org/html/2506.14067v2#A8.E76)), the following inequality holds:

$$ $\displaystyle\sum_{t=1}^{T}\mathbbm{E}_{\tau\sim p_{t}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\sum_{t=1}^{T}\frac{1}{\eta_{t}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\frac{1}{\eta_{T}}\sum_{t=1}^{T}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}$ (77) $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\frac{1}{\eta_{T}}\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{T}\tilde{L}_{T}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{1}\tilde{L}_{0}(\tau))}$ $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\frac{1}{\eta_{T}}\ln\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{T}\tilde{L}_{T}(\tau))+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))-\frac{1}{\eta_{T}}\ln\left(\max_{\tau}\exp(-\eta_{T}\tilde{L}_{T}(\tau))\right)+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}$ $\displaystyle=\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))+\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))+\frac{\ln|\mathcal{{H}}|}{\eta_{T}},$ $$

where ([77](https://arxiv.org/html/2506.14067v2#A8.E77)) holds as $\eta_{t}$ is non-increasing
and $\ln\frac{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t}(\tau))}{\sum_{\tau\in\mathcal{{H}}}\exp(-\eta_{t}\tilde{L}_{t-1}(\tau))}\leq 0$ for all $t$.

From this and the fact ([53](https://arxiv.org/html/2506.14067v2#A8.E53)) that $\mathbbm{E}_{\tau\sim p_{t}}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))=\ell_{t}(\tau_{t})-\gamma_{t}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))$, we have

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle\leq\sum_{t=1}^{T}\frac{\ell_{\text{max}}\eta_{t}}{2}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\sum_{t=1}^{T}\gamma_{t}\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))$ $\displaystyle=\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}.$ $$

Then, from Lemma [54](https://arxiv.org/html/2506.14067v2#A8.E54) and Corollary [63](https://arxiv.org/html/2506.14067v2#A8.E63) along with the union bound, the following inequality holds with probability at least $1-2\delta^{\prime}$, where $\delta^{\prime}=\delta/2$ if $\eta_{t}\leq\frac{2\gamma_{t}}{\ell_{\text{max}}}$:

$$ $\displaystyle\sum_{t=1}^{T}\ell_{t}(\tau_{t})-\min_{\tau}\sum_{t=1}^{T}\ell_{t}(\tau)$ $\displaystyle\leq\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)\ell_{t}(\tau_{t}\mid\mathcal{{H}}_{t}(\tau_{t}))+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\frac{\ell_{\text{max}}\ln(2|\mathcal{{H}}|/\delta)}{2\gamma}$ $\displaystyle\leq 2\ell_{\text{max}}\sum_{t=1}^{T}\left(\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\right)+\ell_{\text{max}}\ln{\frac{2}{\delta}}+\frac{\ln|\mathcal{{H}}|}{\eta_{T}}+\frac{\ell_{\text{max}}\ln(2|\mathcal{{H}}|/\delta)}{2\gamma},$ $$

where the first inequality holds with probability at least $1-\delta^{\prime}$ from Corollary [63](https://arxiv.org/html/2506.14067v2#A8.E63)
and
the second inequality holds with probability at least $1-\delta^{\prime}$ from Lemma [54](https://arxiv.org/html/2506.14067v2#A8.E54) when $\alpha_{t}=\frac{\ell_{\text{max}}\eta_{t}}{2}+\gamma_{t}\leq 2\gamma_{t}$.

Final Bounds.
We have our regret bound depending on the setup of the learning rate $\eta_{t}$.

If $\eta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}=\sqrt{\frac{\ln|\mathcal{H}|}{\ell_{\text{max}}^{2}T}}$, with probability at least $1-\delta$,

$$ $\displaystyle\textbf{Reg}_{T}$ $\displaystyle\leq 2\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|}+\ell_{\text{max}}\left(1+\sqrt{\frac{T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}+2\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|}$ $\displaystyle=\ell_{\text{max}}\left(4\sqrt{T\ln|\mathcal{{H}}|}+\left(1+\sqrt{\frac{T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}\right)$ $\displaystyle=\mathcal{{O}}(\ell_{\text{max}}\sqrt{T\ln(|\mathcal{{H}}|/\delta)}).$ (78) $$

If $\eta_{t}=\frac{2\gamma_{t}}{\ell_{\text{max}}}=\sqrt{\frac{\ln|\mathcal{H}|}{2\ell_{\text{max}}^{2}t}}$, with probability at least $1-\delta$,

$$ $\displaystyle\textbf{Reg}_{T}$ $\displaystyle\leq 2\ell_{\text{max}}\sqrt{2T\ln|\mathcal{H}|}+\ell_{\text{max}}\left(1+\sqrt{\frac{2T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}+2\ell_{\text{max}}\sqrt{2T\ln|\mathcal{H}|}$ $\displaystyle=\ell_{\text{max}}\left(4\sqrt{2T\ln|\mathcal{H}|}+\left(1+\sqrt{\frac{2T}{\ln|\mathcal{{H}}|}}\right)\ln\frac{2}{\delta}\right)$ $\displaystyle=\mathcal{{O}}(\ell_{\text{max}}\sqrt{T\ln(|\mathcal{{H}}|/\delta)}),$ $$

noting that $\sum_{t=1}^{T}1/\sqrt{t}\leq 2\sqrt{T}$.

##### Expected regret

The expected regret can be obtained via integrating the deviations in ([78](https://arxiv.org/html/2506.14067v2#A8.E78)), *i.e.,*

$$ $\mathbbm{E}[W]\leq\int_{0}^{2}\frac{1}{2\delta}\mathbbm{P}\left(W>\ln\frac{2}{\delta}\right)d\delta.$ $$

Here, if we take $W=\frac{1}{\ell_{\text{max}}\left(1+\sqrt{T/\ln|\mathcal{{H}}|}\right)}\left(\textbf{Reg}_{T}-4\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|}\right)>\ln\frac{2}{\delta}$, which holds with probability at most $\delta$,
then,

$$ $\mathbbm{E}[W]\leq 1,$ $$

which suggests that

$$ $\mathbbm{E}[\textbf{Reg}_{T}]\leq\ell_{\text{max}}\left(4\sqrt{T\ln|\mathcal{{H}}|}+1+\sqrt{\frac{T}{\ln|\mathcal{{H}}|}}\right)=\mathcal{{O}}(\ell_{\text{max}}\sqrt{T\ln|\mathcal{{H}}|}).$ (79) $$

## Appendix I Discussion on Selection Efficiency

In this section, we demonstrate that our algorithm does not converge to a trivial selective generator in the aspect of full-feedback setting, *i.e.,* $\operatorname*{arg\,min}_{\tau}\sum_{t=1}^{T}[a_{t}(\tau)+\lambda d_{t}(\tau,\alpha)]\notin\mathcal{{H}}^{\text{triv}}$, if there exists some $\tau\in\mathcal{{H}}\setminus\mathcal{{H}}^{\text{triv}}$ that satisfies the FDR guarantee,
where $\mathcal{{H}}^{\text{triv}}\coloneqq\{\tau\mid\sum_{t=1}^{T}a_{t}(\tau)=T\}$.

Let $e_{t}^{\tau}\coloneqq\mathcal{{E}}_{t}(\hat{{S}}(;\tau))$, and $\tau^{\text{triv}}\in\mathcal{{H}}^{\text{triv}}$, which is always abstaining, then
for any $\tau^{\text{non-triv}}\in\mathcal{{H}}\setminus\mathcal{{H}}^{\text{triv}}$ that satisfies the FDR guarantee, the following inequality holds,

$$ $\displaystyle\frac{\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{non-triv}}}\right)}{\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)}\leq\alpha$ $\displaystyle\Rightarrow\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{non-triv}}}\right)\leq\alpha\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right).$ (80) $$

Let $L_{T}(\tau,\alpha)\coloneqq\sum_{t=1}^{T}\frac{a_{t}(\tau)+\lambda d_{t}(\tau,\alpha)}{1+\lambda}$, which is the cumulative loss of $\tau$,
and consider the difference of cumulative loss between $\tau^{\text{triv}}$ and $\tau^{\text{non-triv}}$,

$$ $\displaystyle{(1+\lambda)}$ $\displaystyle(L_{T}(\tau^{\text{triv}})-L_{T}(\tau^{\text{non-triv}}))$ $\displaystyle=\sum_{t=1}^{T}[a_{t}(\tau^{\text{triv}})+\lambda d_{t}(\tau^{\text{triv}},\alpha)]-\sum_{t=1}^{T}[a_{t}(\tau^{\text{non-triv}})+\lambda d_{t}(\tau^{\text{non-triv}},\alpha)]$ $\displaystyle=\sum_{t=1}^{T}\bigg[\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{triv}})=\texttt{IDK}\right)$ $\displaystyle\qquad\qquad+\lambda\left(\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{triv}}})-\alpha\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{triv}})\neq\texttt{IDK})+\alpha\right)\bigg]$ $\displaystyle\qquad-\sum_{t=1}^{T}\bigg[\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})=\texttt{IDK}\right)$ $\displaystyle\qquad\qquad+\lambda\left(\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{non-triv}}})-\alpha\mathbbm{1}(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK})+\alpha\right)\bigg]$ $\displaystyle=T+\lambda\alpha T-\Bigg[T-\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)$ $\displaystyle\qquad\qquad\qquad+\lambda\bigg\{\alpha\bigg(T-\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)\bigg)$ $\displaystyle\qquad\qquad\qquad\qquad+\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{non-triv}}}\right)\bigg\}\Bigg]$ $\displaystyle=\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)+\lambda\alpha\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)$ $\displaystyle\qquad\qquad\qquad\qquad-\lambda\sum_{t=1}^{T}\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\wedge e_{t}^{\tau^{\text{non-triv}}}\right).$ $$

Since $\tau^{\text{non-triv}}$ satisfies the FDR guarantee ([80](https://arxiv.org/html/2506.14067v2#A9.E80)),
we get

$$ $L_{T}(\tau^{\text{triv}})-L_{T}(\tau^{\text{non-triv}})\geq\sum_{t=1}^{T}\frac{\mathbbm{1}\left(\hat{{S}}(\mathbf{x}_{t};\tau^{\text{non-triv}})\neq\texttt{IDK}\right)}{1+\lambda}=\frac{T-\sum_{t=1}^{T}a_{t}(\tau^{\text{non-triv}})}{1+\lambda}>0,$ (81) $$

where $T-\sum_{t=1}^{T}a_{t}(\tau^{\text{non-triv}})>0$ holds due to $\tau^{\text{non-triv}}\notin\mathcal{{H}}^{\text{triv}}$.
This implies that, given sufficiently many data points, any $\tau^{\text{non-triv}}$ that satisfies the FDR guarantee incurs at least $T-\sum_{t=1}^{T}a_{t}(\tau^{\text{non-triv}})$ less loss than $\tau^{\text{triv}}$.
This is empirically supported by
Figure [22](https://arxiv.org/html/2506.14067v2#A7.F22),
[23](https://arxiv.org/html/2506.14067v2#A7.F23), and
[28](https://arxiv.org/html/2506.14067v2#A7.F28).

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 3
questions: See weakness.
soundness: 2
strengths: 1. The paper focuses on preventing hallucination, directly contributing to a major area of concern for LLM safety and usability.

2. The proposed method's efficacy is experimentally validated by its success in lowering the false discovery rate.
summary: This work studies selective generation in Large Language Models, a mechanism that allows the model to selectively abstain from answering and prevent hallucination. The authors reduce this problem to a standard adversarial bandit problem and provide a theoretical analysis for the relationship between the bandit regret and the false discovery rate. Based on this reduction, the authors proposed a new algorithm, and experiments support the efficiency of the proposed method.
weaknesses: 1. The motivation for Selective Generation is not sufficiently strong, as the strategy's high cost in utility may outweigh its benefit in reducing hallucination. While selectively abstaining from answers helps reduce the False Discovery Rate, Figures 3-6 show an alarming inefficiency rate of 40% to 50%, meaning the LLM refuses to answer nearly half of the questions, which severely limits its practical impact. This approach risks reducing the problem to a trivial solution (e.g., only answering simple, high-certainty questions) that offers minimal real-world help. Instead of outright abstention, a more reasonable approach would be to output the low-confidence answer along with the low-confidence sign. This allows the user to still potentially gain some minor insight or utility while remaining informed and able to control for the risk of hallucination.

2. The reduction of the selective generation problem to an adversarial bandit framework is theoretically questionable due to a fundamental conflict in objectives. In standard adversarial bandits, regret is a comparative metric focused on minimizing the sub-optimality gap between the learner's performance and the performance of the unknown optimal policy ($\tau$). Conversely, the FDR risk in selective generation is a stand-alone metric that only measures the learner's performance without requiring a comparison to an optimal policy.

The authors address this gap by only comparing their algorithm against the trivial policy that always abstains from answering, as seen in the proof of Lemma 1 (Lines 1953-1957). This trivial policy yields a constant loss that simplifies the analysis. However, since the comparison policy is already known and fixed, the core difficulty of the bandit problem—dealing with the unknown optimal action—is bypassed. This decision to only ensure the learner does not perform significantly worse than the simplest, least effective baseline weakens the theoretical utility and necessity of employing complex bandit regret analysis.

3. The derived upper bound for the False Discovery Rate, presented in lines 253-257, is concerning. Even when neglecting the term related to inefficiency, the bound is $\alpha + 1/T^{1/4}$. This is worse than the optimal $\alpha$ achieved by the trivial policy that always abstains from answering. This finding supports the prior critique regarding the theoretical reduction: Theorem 1 essentially only guarantees that the FDR of the proposed method will not be significantly worse than that of the least-effective, baseline "always abstain" policy.

4. A significant concern regarding the experiments is the unexpected increasing trend observed in both the False Discovery Rate for Exp3-IX-SG and No-SG, and the inefficiency for ExSUL and Exp3-IX-SG after several thousand rounds (as shown in Figures 4 to 6). Intuitively, for a bandit algorithm, the cumulative regret increases, but the average regret per round should decrease; consequently, we would expect the FDR to decrease as the learner becomes more accurate. Similarly, a more accurate learner should result in decreasing inefficiency (fewer unnecessary abstentions). The observed increase directly contradicts the expected behavior for effective bandit learning.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: - The theory assumes an adaptive adversary, but the experiments don’t seem to include one. How does the method perform against a strategy-aware adaptive adversary?
- How was the threshold grid size $|H|$ selected?
soundness: 3
strengths: - The paper is clearly written and easy to follow.
- The paper relaxes i.i.d. to non-stochastic inputs with partial feedback. This matches real-world use.
- Results across multiple distribution-shift settings (single, alternating, gradual) substantiate the claims.
summary: This work proposes an online selective-generation method that leverages “feedback unlocking” to learn a threshold from partial feedback, controlling FDR with competitive selection efficiency.
weaknesses: - The theory permits an adaptive adversary, but the experiments cover only distribution shifts and a templated interactive setup.
- The main text says the interactive environment uses two GPT-3.5-turbo models, whereas the appendix specifies GPT-3.5-turbo + two GPT-4o.

---

confidence: 1
contribution: 3
initial_rating: 4
presentation: 3
questions: 1. Can the proposed method be integrated with large-scale language model training pipelines?
2. How is the feedback unlocking mechanism implemented in practice—does it assume stationarity in the abstention threshold?
I am not very familiar with the learning theory field, so I leave a low confidence for my review.
soundness: 3
strengths: - The paper addresses a realistic and underexplored setting - online generation with partial and adversarial feedback and provide theoretical link between bandit regret and false discovery rate, offering a principled approach to uncertainty control in generative models.
- This seems aligns well with human-in-the-loop and reinforcement learning from human feedback (RLHF) settings.
summary: This paper introduces a novel framework for online selective generation—a setting where a large language model (LLM) can abstain from answering uncertain queries to reduce hallucination. The authors focus on a realistic adversarial and partial feedback scenario, where feedback is limited (e.g., thumbs-up/down on generated answers) instead of full supervision.
To tackle this, the paper reformulates selective generation as an adversarial multi-armed bandit problem and proposes an online learning algorithm that controls the False Discovery Rate (FDR)—the proportion of hallucinated outputs among generated ones—while maintaining high selection efficiency (i.e., answering rate). The key technical innovations are:
A Regret-to-FDR conversion lemma that connects the regret bounds of any bandit algorithm to FDR control guarantees.
A feedback unlocking mechanism that exploits structural properties of selective generation to reuse partial feedback efficiently.
Extensive experiments under diverse environments demonstrate that the proposed algorithm achieves effective FDR control and maintains competitive efficiency compared to baselines, showing robustness in adversarial and distribution-shifted conditions
weaknesses: - Some algorithmic components (especially feedback unlocking) may require additional clarification for reproducibility.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. To what extent does GPT-generated simulated user feedback deviate from genuine noisy and random user feedback?
2. Does ExSUL maintain its performance advantage under conditions of noisy and sparse user feedback?
3. In real-world model deployment, how should one balance false positive rate (FDR) with over-rejection?
soundness: 3
strengths: 1. The paper presents a novel framework that effectively utilizes partial, binary feedback signals to learn abstention policies in language generation tasks. 
2. By adapting adversarial bandit algorithms, the proposed ExSUL method provides formal regret bounds, ensuring that the model's accumulated reward converges close to that of the best fixed policy in hindsight. 
3. Experiments demonstrate that ExSUL achieves superior control over hallucination rates, maintaining high answer accuracy and low FDR across various datasets and under distribution shifts.
summary: This paper introduces a novel online learning framework called ExSUL for selective language generation. The goal is to enable models to judiciously decide when to generate answers and when to abstain, especially in environments with noisy, incomplete, or adversarial feedback. The method leverages partial feedback—such as binary signals indicating correctness—to learn effective abstention policies without requiring full supervision. By incorporating techniques from adversarial bandit algorithms and providing regret guarantees, ExSUL balances the trade-off between reducing hallucinations and maintaining answer coverage. The experimental results demonstrate that the approach outperforms existing methods in controlling hallucinations while sustaining high answer quality across multiple datasets and settings.
weaknesses: 1. This paper investigates online selective generation, yet lacks corresponding online experiments or genuine user feedback, which to some extent undermines the reliability of the results. For instance, this paper employs GPT as a generative model and similarly utilises the GPT series to simulate user feedback. Homogeneous models may exhibit similar hallucinations and also harbour homogeneous biases, which diverge significantly from real-world user feedback. While the paper provides promising results in simulated and benchmark environments, it offers limited discussion on how the proposed abstention and learning strategies scale to large-scale, noise real-world applications.
2. The method relies on the presence of binary or weak feedback signals, which may vary in quality and consistency across different deployment scenarios. The paper does not thoroughly analyze how noisy or sparse feedback could impact the learning process, leaving some uncertainty about robustness to imperfect supervision.
3. The evaluations focus on their defined metrics (e.g., FDR, regret) without incorporating human judgment or user-centric metrics. Including such evaluation would better demonstrate the practical benefits and acceptance of the abstention policy in real-world decision-making contexts. Moreover, this paper aims to enhance the output quality of LLMs from the perspective of selective generation. However, it appears to place undue emphasis on FDR. An LLM that is overly reluctant to provide answers may exhibit a low FDR, yet it would hardly be considered a good model.


Decision: Reject