Reproduce “Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality” on OpenResearch

About this paper

Junyan Liu, Ziyun Chen, Kun Wang, Haipeng Luo, Lillian J. Ratliff

A distributionally optimistic learning framework improves online threshold decision-making under uncertainty. For Pandora’s Box and Prophet Inequality, it achieves \(\widetilde{O}(\sqrt{nT})\) regret in the non-contextual setting, matching the known lower bound up to logarithmic factors, and \(\widetilde{O}(nd\sqrt{T})\) regret when rewards have box-specific linear contextual means.

Key insights

• Optimism over full reward distributions, rather than only their means, is sufficient for learning sequential inspection and acceptance policies.
• The distributional error analysis becomes sharper in low-value regions because the utility derivative is controlled by the probability that earlier boxes remain unopened, producing telescoping rather than linear accumulation.
• The same framework extends beyond Pandora’s Box to Prophet Inequality, suggesting that the analysis applies to a broader class of threshold-based stochastic decision problems.

Summary by alphaXiv.