Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Learning with Multiple Correct Answers - Regret Bounds under Different Feedback Models

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Ranking bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes realizable online mistake bounds for learning with multiple correct answers under three feedback models (mistake-unknown, mistake-known, set-valued) via new Littlestone-type dimensions, and derives agnostic regret rates ranging from linear to constant.

Problem

Online learning when each instance admits a set of valid labels (e.g., language generation with many acceptable completions), under different feedback models, where the learner must output one valid label per round.

Approach

Introduces multi-label Littlestone dimensions LD_U, LD_K, LD_S for three feedback models, shows they exactly characterize optimal realizable mistake bounds, and shows agnostic regret can be linear, sublinear, or constant depending on feedback model; set-valued feedback allows constant regret for some classes via a weighted-majority algorithm.

Key results

• Realizable mistake bounds are exactly min(LD_U(H),T), min(LD_K(H),T), min(LD_S(H),T) for the three feedback models.
• Mistake-unknown agnostic regret can be linear in T even for a 3-hypothesis class with LD_U=1, while set-valued regret for that class is at most log2(3).
• Mistake-known agnostic regret is O(sqrt(LD_K |Y| T log T)); set-valued regret is O(sqrt(LD_S T log T)) independent of label set size.

Surprising findings

• Realizable learnability (finite Littlestone-type dimension) does not imply sublinear agnostic regret in the mistake-unknown model.
• Multi-label classes can have constant regret independent of their Littlestone dimension, unlike single-label multiclass where regret is order sqrt(LD T).

Limitations

• Results are purely theoretical with no experiments on real language generation tasks.
• Mistake-unknown agnostic regret can be linear, so the characterization gives no meaningful agnostic guarantees in that model.
• Set-valued constant-regret result requires a finite class satisfying a specific weight condition on hypotheses.

Experimental setup

Metrics: mistake bound regret sample complexity

Baselines: mistake-unknown multi-label online learning (finite classes) set Littlestone dimension learner multiclass agnostic online learning

Builds on: Littlestone dimension Standard Optimal Algorithm EXP4 multiclass online learning

Closest papers by meaning

• On Bits and Bandits: Quantifying the Regret-Information Trade-off (ICLR 2025 · similarity 0.86)
• Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.85)
• Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.85)
• Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.84)
• Generating in the Limit with Infinitely Many Hallucinations (NeurIPS 2026 · similarity 0.84)
• Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.84)