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

Junyan Liu, Ziyun Chen, Kun Wang +2

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…