Research map / Bandits and online learning / Online convex optimization and games
Avoiding Catastrophe in Online Learning by Asking for Help
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.
Proposes an online learning model where an agent maximizes the product of payoffs (chance of avoiding catastrophe) while querying a mentor, and shows sublinear queries are impossible in general but achievable with finite VC/Littlestone mentor classes under local generalization.
Problem
Standard online learning with regret guarantees assumes mistakes are recoverable; when some mistakes are irreparable, agents need to minimize the total chance of catastrophe while learning from limited mentor queries.
Approach
Model catastrophe avoidance as maximizing the product of per-step payoffs with limited mentor queries, assume a local generalization property (Lipschitz-style transfer across similar inputs), and combine a label-efficient Hedge with asking for help on out-of-distribution inputs (nearest-neighbor distance threshold).
Key results
- Any algorithm with sublinear mentor queries has worst-case regret Omega(L sqrt(T/(sup E|Q_T|+1))), unbounded as T grows, and causes catastrophe with probability approaching 1 even when the mentor is always safe.
- The proposed algorithm achieves E[R_T^x] in O(d L/(sigma mu_0^m) T^{-1/(2n+1)} log T) and E[R_T^+] in O(d L/sigma T^{-1/(2n+1)} log T) with sublinear queries, under finite VC dimension with smooth inputs or finite Littlestone dimension.
- Expected number of queries is O(T^{(4n+1)/(4n+2)}(d/sigma log T + E[diam(x)^n])).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Help-seeking Hedge with local generalization and a finite-VC or finite-Littlestone mentor policy class | Online learning with mentor help · Finite VC dimension with σ-smooth inputs, or finite Littlestone dimension | expected multiplicative regret: O(\frac{d L}{\sigma \mu_0^m} T^{\frac{-1}{2n+1}} \log T) | Helped |
| Use Help-seeking Hedge with local generalization and a finite-VC or finite-Littlestone mentor policy class | Online learning with mentor help · Finite VC dimension with σ-smooth inputs, or finite Littlestone dimension | expected additive regret: O(\frac{d L}{\sigma} T^{\frac{-1}{2n+1}} \log T) | Helped |
| Limit mentor queries to a sublinear number | Any online learning algorithm in the general setting · General setting | worst-case expected multiplicative regret: \Omega\left( L \sqrt{\frac{T}{\sup_{\boldsymbol{\mu},\pi^m}\E[|Q_T|] + 1}}\right) | Hurt |
| Limit mentor queries to a sublinear number, even with a mentor that avoids catastrophe with certainty | Any online learning algorithm in the general setting · General setting | overall probability of avoiding catastrophe: 0 | Hurt |
Surprising findings
- Sublinear mentor queries alone are insufficient: any algorithm with sublinear queries causes catastrophe with probability tending to 1 in the worst case, even if the mentor never causes catastrophe.
Limitations
- Algorithm's per-step time complexity scales with the size of the policy cover, which is computationally expensive.
- Open whether the problem is tractable for finite VC dimension with fully adversarial inputs.
- Relies on local generalization and a nearest-neighbor OOD detection that may not align with standard OOD detection methods.
Experimental setup
Metrics: multiplicative regret additive regret expected number of mentor queries
Builds on: Hedge label-efficient feedback Hedge smoothed online learning Littlestone dimension
Closest papers by meaning
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.88)
- Online Non-Convex Optimization with Imperfect Feedback (NeurIPS 2020 · similarity 0.87)
- Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.86)
- Regret Analysis of Repeated Delegated Choice (AAAI 2024 · similarity 0.86)
- Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.86)
- Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.