# Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality

arXiv: https://arxiv.org/abs/2505.18828 · HTML: https://mlsanity.com/paper/2505.18828/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 32 references that are in the map.
- First posted on arXiv 24 May 2025.

## Builds on (most cited first, 19 of 19)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Pandora's Box Problem with Order Constraints](https://mlsanity.com/paper/2002.06968/) (2020)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Sample Complexity of Posted Pricing for a Single Item](https://mlsanity.com/paper/2406.00819/) (2024)
- [Pandora's Box with Correlations: Learning and Approximation](https://mlsanity.com/paper/1911.01632/) (2019)
- [Learning Utilities and Equilibria in Non-Truthful Auctions](https://mlsanity.com/paper/2007.01722/) (2020)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Weitzman's Rule for Pandora's Box with Correlations](https://mlsanity.com/paper/2301.13534/) (2023)
- [Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack](https://mlsanity.com/paper/2107.02058/) (2021)
- [Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS](https://mlsanity.com/paper/2212.01524/) (2022)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme](https://mlsanity.com/paper/2207.09545/) (2022)
- [Recent Developments in Pandora's Box Problem: Variants and Applications](https://mlsanity.com/paper/2308.12242/) (2023)
- [Prophet inequality for bipartite matching: merits of being simple and non adaptive](https://mlsanity.com/paper/1902.06243/) (2019)

## Built on by (most cited first, 5 of 5)

- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Learning Markov Decision Processes under Fully Bandit Feedback](https://mlsanity.com/paper/2602.02260/) (2026)
- [Online Pandora's Box for Contextual LLM Cascading](https://mlsanity.com/paper/2606.07392/) (2026)
- [Learning in Prophet Inequalities with Noisy Observations](https://mlsanity.com/paper/2604.01789/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

We study the Pandora's Box problem in an online learning setting with semi-bandit feedback. In each round, the learner sequentially pays to open up to n boxes with unknown reward distributions, observes rewards upon opening, and decides when to stop. The utility of the learner is the maximum observed reward minus the cumulative cost of opened boxes, and the goal is to minimize regret defined as the gap between the cumulative expected utility and that of the optimal policy. We propose a new algorithm that achieves widetildeO(√nT) regret after T rounds, which improves the widetildeO(n√T) bound of Agarwal et al. [2024] and matches the known lower bound up to logarithmic factors. To better capture real-life applications, we then extend our results to a natural but challenging contextual linear setting, where each box's expected reward is linear in some known but time-varying d-dimensional context and the noise distribution is fixed over time. We design an algorithm that learns both the linear function and the noise distributions, achieving widetildeO(nd√T) regret. Finally, we show that our techniques also apply to the online Prophet Inequality problem, where the learner must decide immediately whether or not to accept a revealed reward. In both non-contextual and contextual settings, our approach achieves similar improvements and regret bounds.