Technical Summary: Learning with Multiple Correct Answers – Regret Bounds under Different Feedback Models

1. Problem Definition and Motivation

This work addresses the problem of online learning with multiple correct answers, a setting where a single input instance $x$ admits a set of valid labels $S \subseteq \mathcal{Y}$ rather than a single target label. This formulation is motivated by modern tasks such as language generation (where a prompt has many acceptable completions), open-ended question answering, dialogue generation, and recommendation systems.

The study focuses on the online learning paradigm, proceeding in rounds $t \in [T]$. In each round, an adversary presents an instance $x_t$ and a set of acceptable labels $S_t$. The learner predicts a label $\hat{y}_t$ and incurs a loss of 1 if $\hat{y}_t \notin S_t$. The paper analyzes this problem under three distinct feedback models:

1. Mistake-unknown: The learner receives only a single valid label $y_t \in S_t$ (chosen by the adversary) but does not know if their prediction was correct.
2. Mistake-known: The learner receives a single valid label $y_t \in S_t$ and a binary indicator revealing whether their prediction $\hat{y}_t$ was a mistake.
3. Set-valued: The learner is revealed the entire set of valid labels $S_t$.

The analysis covers both the realizable setting (where a hypothesis $h^* \in \mathcal{H}$ exists such that $h^*(x_t) = S_t$ for all $t$) and the agnostic setting (where the learner competes against the best hypothesis in $\mathcal{H}$ minimizing cumulative loss).

2. Methodology and Combinatorial Characterizations

The authors introduce novel combinatorial dimensions to characterize the learnability of multi-label hypothesis classes $\mathcal{H}$ under each feedback model. These dimensions are defined via tree-shattering arguments adapted to the specific information available in each model.

Combinatorial Dimensions

• Set-Valued Littlestone Dimension ($LD_{set}$): Defined on a set-valued tree where nodes are labeled with subsets of $\mathcal{Y}$. A tree is shattered if for every path of predictions, there exists a hypothesis consistent with the revealed sets $S_t$ but making a mistake on the predicted label.
• Mistake-Known Littlestone Dimension ($LD_{known}$): Defined on a multi-label tree where nodes are labeled with single labels. Shattering requires consistency with the revealed single label $y_t$ and a mistake on the prediction.
• Mistake-Unknown Littlestone Dimension ($LD_{unknown}$): Defined using a "mistake offset" function. A tree is $d$-shattered if the cumulative number of mistakes along any path, plus an offset for the hypothesis, exceeds $d$. This accounts for the lack of immediate feedback on correctness.

Algorithms

For the realizable setting, the authors propose Standard Optimal Algorithms (SOA) for each feedback model. These algorithms maintain a version space of consistent hypotheses and select predictions that minimize the worst-case dimension of the remaining version space.

• SOA for Mistake-Unknown: Maintains a version space and an offset function, predicting the label that minimizes the maximum $LD_{unknown}$ of the resulting sub-classes.
• SOA for Mistake-Known: Predicts to minimize the maximum $LD_{known}$ of the sub-classes formed by the potential mistake bit.
• SOA for Set-Valued: Predicts to minimize the maximum $LD_{set}$ of the sub-classes formed by the revealed set $S_t$.

3. Key Results

Realizable Online Learning

The paper provides a complete characterization of the optimal mistake bound for any multi-label class $\mathcal{H}$ in the realizable setting:

• Mistake-unknown: The optimal mistake bound is $\min(LD_{unknown}(\mathcal{H}), T)$.
• Mistake-known: The optimal mistake bound is $\min(LD_{known}(\mathcal{H}), T)$.
• Set-valued: The optimal mistake bound is $\min(LD_{set}(\mathcal{H}), T)$.

These results generalize previous work on finite classes to arbitrary (possibly infinite) hypothesis classes. The authors prove that $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$, which occurs if and only if the intersection of all hypotheses' label sets for any instance is non-empty.

Agnostic Online Learning (Regret Bounds)

A significant contribution is the demonstration that regret rates vary drastically across feedback models in the agnostic setting, contrasting with single-label learning where regret is typically $\tilde{\Theta}(\sqrt{T})$.

1. Mistake-Unknown: The authors show that regret can grow linearly in $T$ ($\Omega(T)$), even for simple hypothesis classes with $LD_{unknown}=1$. This implies that realizable learnability (characterized by $LD_{unknown}$) does not guarantee sublinear regret in the agnostic setting for this feedback model.
2. Mistake-Known: The paper establishes a sublinear regret upper bound of $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$. This is achieved by reducing the problem to non-stochastic bandits with expert advice, utilizing a set of SOA-based experts.
3. Set-Valued:
   • For specific classes (e.g., the example class $H_3$), the regret is constant ($O(1)$).
   • For general classes, the regret is bounded by $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$. Notably, this bound is independent of the label space size $|\mathcal{Y}|$, allowing it to hold for infinite label spaces.

Batch Learning Implications

The derived combinatorial dimensions and online bounds imply sample complexity bounds for the corresponding batch learning problems. The authors provide the first known upper bounds for batch learning under the full-set feedback model and improve existing bounds for the single-correct-answer case from finite to infinite classes.

4. Significance and Claims

The paper claims to provide the first complete combinatorial characterization of realizable online multi-label learning under three distinct feedback models. Its primary theoretical significance lies in the separation between realizable and agnostic learnability in the mistake-unknown setting, where the standard Littlestone dimension fails to capture meaningful regret bounds.

Furthermore, the work highlights a rich structure in agnostic multi-label learning:

• The feedback model fundamentally alters the achievable regret rates (from linear to constant).
• The set-valued feedback model allows for constant regret on specific classes and dimension-independent bounds for general classes, a phenomenon not observed in single-label learning.
• The results suggest that characterizing agnostic multi-label learning requires combinatorial objects beyond those sufficient for realizable learnability.

The authors explicitly note that their regret definitions differ from prior works (e.g., Joshi et al. [JLB+25] and Raman et al. [RST24]) to better align with the underlying prediction task of minimizing error against the true set of acceptable labels, rather than competing against a hypothesis that merely contains a specific revealed label.