Research map / Bandits and online learning / Online convex optimization and games
Online Learning with Unknown Constraints
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 a meta-algorithm for online learning under unknown safety constraints that combines an online regression oracle (to shrink a version space of constraint functions) with an online learning oracle, with a per-round complexity measure V_t that trades off loss minimization against constraint information gain, plus an asymptotic lower bound showing this measure is necessary.
Problem
Online learning where every action must satisfy an unknown safety constraint at every round, with regret measured against the best safe action in hindsight and no constraint violations with high probability.
Approach
Build optimistic action sets O_t (superset of safe actions) for the online learner and pessimistic sets P_t (guaranteed safe) from a regression-based version space; a mapping M converts the learner's distribution over O_t into one over P_t, with a per-round tradeoff term V_kappa bounded via eluder dimension, yielding a regret bound and a matching asymptotic lower bound. For linear constraints, a s
Key results
- For linear constraints with linear losses, the algorithm achieves regret O((d/b) sqrt(T) log(T/(dδ))) with high probability while never violating constraints.
- An asymptotic lower bound shows that if the time-averaged complexity measure V_kappa stays bounded away from zero for any mapping M, no safe algorithm achieves o(T) regret.
- The authors state that the best prior bound in this linear-constraint setting was O(T^{2/3}), which their method improves to O(sqrt T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed safe-set mapping with online regression and online learning oracles | General constrained online learning · Online learning with unknown constraints | regret: the theorem gives a regret bound in terms of the oracle regrets, eluder dimension, and safe-learning complexity | Helped |
| Use a scaling-based mapping to ensure actions lie in the pessimistic safe set | Online learning with linear constraints · Linear losses and linear constraints | regret: \mathcal O \left( \frac{d}{b}\sqrt{T} \log(\frac{T}{d\delta})\right) | Helped |
| Use a scaling-based mapping with the intersection of pessimistic sets | Online learning with polytopic constraints · Linear losses and polytopic constraints | regret: \mathcal O \left( \frac{md}{b}\sqrt{T} \log(\frac{T}{d\delta})\right) | Helped |
| Replace the Euclidean initial safe set with an ℓ1 ball (ablation) | Linear-constraint method · Linear constraints | eluder dimension: increases by a factor of \log(d) | Hurt |
| Remove the pessimistic-set mapping and play from optimistic sets (ablation) | Online learning with long-term constraints · Online learning with long-term constraints | sum of constraint violations: Regret_T ≤ regretol(T,δ); sum_t f*(a_t,x_t) ≤ inf_α{αT + 20 Regsq(T,δ,F_0) edim(F_0,α)/α} | Mixed |
| Use an initial safe set that cannot be expanded with informative safe actions | Safe online learning · Unknown constraints with initial safe set {0} | regret: Regret_T ≥ T c^* | Hurt |
| Use the scaling-based mapping for generalized linear constraints | Online learning with generalized linear constraints · Generalized linear constraints | mapping parameter: \kappa^* \leq \frac{rD_\ell D_a}{b \underline c} | Helped |
| Use the scaling-based mapping for multiple polytopic constraints | Online learning with multiple linear constraints · Polytopic constraints | mapping parameter: \kappa^* \leq \frac{D_\ell D_a}{b} | Helped |
Surprising findings
- Playing only from the optimistic sets (without the pessimistic mapping) can satisfy only long-term constraints; with no initial safe set beyond {0}, no progress is possible, so the pessimistic mapping is necessary.
Limitations
- The general meta-algorithm is non-constructive; explicit algorithms are given only for finite, linear, generalized linear and polytopic constraints.
- Analysis is limited to full-information feedback with no contexts in the examples and no bandit or stateful RL extension.
- The lower bound holds only asymptotically and requires the existence of a mapping M with bounded complexity.
Experimental setup
Metrics: regret constraint violation
Baselines: SO-PGD ROFUL
Builds on: eluder dimension decision estimation coefficient Vovk-Azoury-Warmuth forecaster EXP3
Closest papers by meaning
- Avoiding Catastrophe in Online Learning by Asking for Help (ICML 2025 · similarity 0.88)
- Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.88)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.88)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.88)
- Online Optimization for Offline Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.88)
- An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.87)
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.