Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Triple-Optimistic Learning for Stochastic Contextual Bandits with General 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 Optimistic3, a triple-optimistic primal-dual framework (optimistic parameter learning, primal decision, dual update) that achieves Õ(√T) regret and violation for contextual bandits with general constraints without Slater's condition.
Problem
Contextual bandits with general long-term constraints where the learner must maximize cumulative reward while satisfying cost constraints; prior methods get only Õ(T^{3/4}) without Slater's condition or Õ(√T/δ) with it, and no efficient method achieves optimal Õ(√T) without Slater's condition.
Approach
Integrates optimism into parameter learning (UCB rewards, LCB costs), the primal decision (optimistic surrogate with KL-regularized mirror descent / Exp3-style update), and the dual update (adds a momentum-like correction term to the dual gradient step), yielding a gradient-based, computationally cheap primal-dual method that avoids Slater's condition.
Key results
- Optimistic3 achieves Õ(√T) regret and violation for contextual bandits with general constraints without Slater's condition, improving on Õ(T^{3/4}) of prior work.
- Compared with Slater-based Õ(√T/δ) bounds, removes the 1/δ dependence.
- Experiments on MSLR-WEB30k show Optimistic3 outperforms LOE2D and LagrangeCBwLC in averaged reward and violation (averaged over 50 trials).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add optimistic learning, optimistic primal decisions, and optimistic dual updates | Contextual bandits with general constraints · Contextual bandits with general constraints | regret: ˜O(T^{3/4}) -> ˜O(√T) | Helped |
| Add optimistic learning, optimistic primal decisions, and optimistic dual updates | Contextual bandits with general constraints · Contextual bandits with general constraints | constraint violation: ˜O(T^{3/4}) -> ˜O(√T) | Helped |
| Use Optimistic3 without requiring Slater’s condition or prior knowledge of δ | Contextual bandits with general constraints · Contextual bandits with general constraints | regret: ˜O(√T/δ) -> ˜O(√T) | Helped |
| Use Optimistic3 without requiring Slater’s condition or prior knowledge of δ | Contextual bandits with general constraints · Contextual bandits with general constraints | constraint violation: ˜O(√T/δ) -> ˜O(√T) | Helped |
| Use Optimistic3 for contextual bandits with knapsack constraints | Optimistic3 · Contextual bandits with knapsack constraints | regret: ˜O((1 + ν∗/b)√T) | Helped |
| Use EXP3-style reward estimators and adaptive weighted constraint estimators with Optimistic3 | MAB with stochastic constraints · MAB with stochastic constraints | regret: ˜O(√T) | Helped |
| Use EXP3-style reward estimators and adaptive weighted constraint estimators with Optimistic3 | MAB with stochastic constraints · MAB with stochastic constraints | constraint violation: ˜O(√T) | Helped |
| Use Optimistic3’s gradient-based update instead of constructing a feasible set and solving a linear program each round | MAB with stochastic and adversarial constraints · MAB with stochastic and adversarial constraints | computational overhead | Helped |
| Use Optimistic3 instead of LOE2D | MSLR-WEB30k · Microsoft MSLR-WEB30k | reward | Helped |
| Use Optimistic3 instead of LagrangeCBwLC | MSLR-WEB30k · Microsoft MSLR-WEB30k | constraint violation | Helped |
Surprising findings
- The optimistic dual correction achieves minimal violation even without Slater's condition.
Limitations
- Requires known context distribution for the dual update; unknown distributions not analyzed.
- Experiments are limited to a single learning-to-rank dataset with synthetic costs.
- Single-constraint analysis; extension to multiple constraints stated as readily generalizable but not shown.
Experimental setup
Datasets: Microsoft MSLR-WEB30k
Benchmarks: MSLR-WEB30k
Metrics: averaged reward constraint violation
Baselines: LOE2D LagrangeCBwLC
Builds on: LagrangeCBwLC LOE2D Bernasconi et al. 2024 constrained MAB online mirror descent Exp3
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.90)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.89)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.88)
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.