Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Pandora’s Box
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.
Introduces a contextual online variant of Pandora's Box where contexts realize reservation values, and gives no-regret algorithms (full-information and bandit) via reduction to linear-quadratic online regression.
Problem
Learning near-optimal Pandora's Box search strategies online when value distributions are unknown and may change each round, with per-alternative contexts and opening costs.
Approach
Replace the standard mean-based realizability assumption of contextual bandits with realizability of the reservation value (a sufficient statistic of each box's distribution), and reduce regret minimization to linear-quadratic online regression via a sensitivity/robustness analysis of Weitzman's algorithm.
Key results
- Full-information FTRL-based reduction achieves regret bound 3n sqrt(max{M,c}) M^{1/4} T^{3/4}.
- Bandit setting achieves regret 2n (2 c_max M max{M,c_max}^2)^{1/6} T^{5/6}.
- Synthetic experiments (n=10, T=300, 20 repetitions) show the CPB algorithm has significantly smaller regret than linear regression in both full and bandit feedback.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the CPB algorithm instead of linear regression | Contextual Pandora's Box · Synthetic data, full feedback | regret | Helped |
| use the CPB algorithm instead of linear regression | Contextual Pandora's Box · Synthetic data, bandit feedback | regret | Helped |
Surprising findings
- Without realizability, the problem is information-theoretically hard online: an adversary can force linear regret.
Limitations
- Regret bounds are sublinear but not tight; no lower bounds derived.
- Experiments are limited to synthetic uniform distributions with small n and T.
- Realizability assumption is required for tractability.
Experimental setup
Datasets: synthetic uniform-distribution simulation
Benchmarks: synthetic Contextual Pandora's Box simulation
Metrics: cumulative regret
Baselines: linear regression
Builds on: Weitzman's Pandora's Box algorithm contextual bandits realizability follow the regularized leader
Closest papers by meaning
- Online Pandora’s Boxes and Bandits (AAAI 2019 · similarity 0.91)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.90)
- Online Learning for Min Sum Set Cover and Pandora’s Box (ICML 2022 · similarity 0.89)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.86)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.86)
- Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index (NeurIPS 2024 · similarity 0.86)
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.