Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
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.
Improves online Pandora's Box regret to Õ(√(nT)) with an adaptive Bernstein-based optimistic distribution, extends to a contextual linear setting with Õ(nd√T) regret, and applies the techniques to online Prophet Inequality.
Problem
Regret minimization for online Pandora's Box and Prophet Inequality with unknown fixed (non-contextual) or context-dependent linear reward distributions under semi-bandit feedback; prior bounds were Õ(n√T) and Õ(nT^{5/6}) in the contextual linear case.
Approach
Builds optimistic empirical CDFs with an adaptive Bernstein-type mass shift instead of a fixed shift, and bounds the per-box regret term via Lipschitz/monotonicity of the expected utility and a sharper derivative bound, giving a sqrt(sum Q/m) regret term; in the contextual case it uses value-optimistic shifts of observed rewards using ridge-regression confidence bounds.
Key results
- Non-contextual Pandora's Box achieves Õ(√(nT)) regret, improving the prior Õ(n√T) and matching the Ω(√(nT)) lower bound up to logarithmic factors.
- Contextual linear Pandora's Box achieves Õ(nd√T) regret, better than Õ(nT^{5/6}) whenever d=o(T^{1/3}).
- Prophet Inequality non-contextual achieves Õ(√(nT)) regret, improving Õ(n√T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive, data-dependent probability-mass reallocation when constructing optimistic distributions instead of fixed-mass shifting | Online Pandora's Box algorithm · Pandora's Box, non-contextual | regret: \otil(n\sqrt{T}) -> \otil(\sqrt{nT}) | Helped |
| Use value-optimistic empirical distributions that shift observed rewards as well as probability mass | Online Pandora's Box algorithm · Pandora's Box, contextual linear | regret: \otil(nT^{5/6}) -> \otil(nd\sqrt{T}) | Helped |
| Extend the approach to Prophet Inequality in the non-contextual setting | Online Prophet Inequality algorithm · Prophet Inequality, non-contextual | regret: \otil(n\sqrt{T}) -> \otil(\sqrt{nT}) | Helped |
Limitations
- Contextual linear bound grows linearly in n, with an open question of tightness.
- Prophet Inequality gap of √n to the known Ω(√T) lower bound remains.
- Contextual analysis assumes bounded noise supported on [-1/4,1/4] and bounded means.
Experimental setup
Metrics: cumulative regret
Baselines: Agrawal et al. Õ(n√T) semi-bandit algorithm Chen et al. contextual linear Pandora's Box reduction (Õ(nT^{5/6}))
Builds on: Weitzman's algorithm Agrawal et al. optimistic Pandora's Box (semi-bandit) elliptical potential lemma
Closest papers by meaning
- Contextual Pandora’s Box (AAAI 2024 · similarity 0.90)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.89)
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.89)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.88)
- Logarithmic Regret for Online KL-Regularized Reinforcement Learning (ICML 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.