Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
Authors: Junyan Liu
Ziyun Chen
Kun Wang
Haipeng Luo
Lillian J. Ratliff
Venue: NeurIPS 2025 poster ()
Keywords: Pandora's Box
Prophet Inequality
Semi-bandits
Regret minimization
Primary area: theory

Abstract: 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 $\widetilde{O}(\sqrt{nT})$ regret after $T$ rounds, which improves the $\widetilde{O}(n\sqrt{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 $\widetilde{O}(nd\sqrt{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.

Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
Junyan Liu" University of Washington junyan1 10cs washington edu
Ziyun Chen' University of Washington eiyunco0cs.washiiggtooo edu
Kun Wang"
Haipeng Luo
Purdue University
University of Southern California haipengl@usc.enm edu
wang5675@purdue. edu
Lillian J. Ratliff
University of Washington
ratliffl@ur edu
Abstract
We study the Pandora's Box problem in an online learning setting with semi-bandit feedback. In each round, the learner sequentially pays open up to n boxes with unknown reward distributions, observes rewards upon opening, and decides when 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 (VVnT) regret after rounds, which improves the (nvTT) 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 natural but challenging contextual linear setting, where each box's expected reward linear some known but time-ngrying d- dimensional context and the noise distribution is fixed over time. We design an algorithm that learns both linear function and the noise distributions, achieving (ndyTT) 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 revealed reward. In both non-contextual and contextual settings, our approach achieves similar improvements and regret bounds.
Introduction
Pandora's Box is fundamental problem in stochastic optimization, initiated by Weitzman [1978). In this problem, the learner is given n boxes, each associated with a known cost and a known reward distribution. The Iearner may open box time, paying the corresponding cost to observe realized reward. Based on the known distributions, the learner designs a policy that specifies the order of inspecting boxes and stopping rule for when to halt the process and select reward. Weitzman [1978] shows that the optimal policy computes a threshold (i.e., reservation value) for each box based on its cost and distribution, and opens boxes in descending order of these thresholds until stopping condition met. This model abstracts a wide range of sequential decision- making scenarios where
"qqual contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

information is costly to acquire and decisions must be made under uncertainty. For example, in the hiring process, an employer interviews candidates one by one, where each interview incurs cost (e.g., time), and each candidate's performance is drawn from a known distribution (e.g., candidate's profile). The employer must decide when to stop interviewing and make an offer, balancing the expected benefit of finding a better candidate in the future against the accumulated cost of continued search. Other real-world applications include online shopping and path planning [Atsidakou et al., 2024].
While the classic Pandora's Box problem and its variants have been extensively studied (see survey [Beyhaghi and Cai, 2024]). recent work [Fu and Lin, 2020, Guo et al., 2021, Gatmiry et al., 2024, Agarwal et al., 2024, Atsidakou et al.. 2024] has started to explore settings where the reward distributions are unknown. This line of work is motivated by practical scenarios where distributions are unavailable upfront and must be learned through interaction. These formulations move beyond the classical setting by requiring the learner to adapt based on observed outcomes. Prior studies have considered probably approximately correct (PAC) guarantees, establishing the near-optimal sample complexity Fu and Lin [2020]. Guo et al. [2021], and regret minimization over a Torudnnd repeated game Gergatsouli and Tzamos [2022], Gatmiry et al. [2024], Agarwal et al. [2024]. Atsidakou et al. [2024]. In the basic regret minimization setting, the learner repeatedly solves a Pandora's Box problem at each round and observes the rewards of the opened boxes (a.k.a. semi-bandit feedback), drawn from fixed but unknown distributions. However, even in this setting, gap remains between the (VVTT) lower bound of Gatmiry et al. [2024] and the best known upper bound of (UUnVT) by Agarwal et al. [2024], where U is the magnitude of the utility function that can be as large as n..
In addition to the fixedddittrbutton setting, prior work studied the online Pandora's 's Box problems with time-varying reward distributions, which better capture many real-world scenarios Gergatsouli and Tzamos [2022], Atsidakou et al. [2024]. For example, in the hiring process, the distribution of candidate quality may shift over time due to market trends or seasonal patterns. To model such dynamies, Gergatsouli and Tzamos [2022] consider setting where the rewards are chosen by an oblivious adversary and show that sublinear regret is achievable when the algorithm competes against benchmark weaker than the optimal policy, obtained by imposing constraints the set of boxes it can open. Later, Gatmiry et al. [2024] showed that in the same setting, when the algorithm competes against the optimal policy, no algorithm can achieve sublinear regret, even with full information feedback (i.e.. the learner observes the rewards of all boxes regardless of which policy is played). To make the problem tractable while still allowing distributions to change over time, Atsidakou et al. [2024] propose a contextual model where, in each round, the learner observes a context vector for each box. whose optimal threshold can be approximated by a function of the context and an unknown vector. Their approach reduces the problem to Ainear-quarrati online regression, which provides generality but leads to a regret bound with poor dependence on the horizon T. In particular, if the function is linear, they achieve ((155/6) regret bound with semi-bandit feedback (referred to as bandit feedback in their work).
Motivated by these limitations, we address two main challenges in this paper. First, we close the gap in the regret dependence on the number of boxes n. Second, we propose a new contextual model that allows the reward distributions to vary over time, and under this setting, we achieve improved dependence on the time horizon T. Our contributions are summarized as follows, and further related work is discussed in Appendix B.
For the online Pandora's 's Box problem, propose a new algorithm that achieves regret bound of Ö(VnT) improving upon the Ö(Un/T) bound by Agarwal et al. [2024] and matching the known 2 D(VnT) lower bound (up to logarithmic factors) [Gatmiry et al., 2024]. Our algorithm builds on the optimism-based framework of Agarwal et al. [2024], but introduces a simple yet crucial modification. Specifically, we first construct empirical distributions for each box using the observed reward samples, and then shift probability mass to form optimistic distributions that encourage exploration. In contrast to the fixed-mass shifting scheme used in Agarwal et al. [2024], we adaptively reallocate mass at each point based on problem-dependent factors. As we demonstrate below, this adaptive construction is central to enabling a more refined regret analysis.
We extend these results to the 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. Our algorithm preserves the overall structure of the non-contextual case, but modifies the construction of optimistic distributions to account for context-dependenn variation. Since the reward

---

samples are no longer identically distributed, we adjust not only the probability mass but also the observed rewards themselves in a value-optimistic manner to maintain optimism. While the algorithm of Atsidakou et al. [2024] applies to our setting with O(n25/6) regret (see Appendix B), we establish ((dv/T) regret. As long as d = /3T our algorithm yields better regret guarantee.
Finally, we extend our algorithms and analytical techniques the Prophet Inequality problem in both non-contextual and contextual settings. In the non non-contextual case, our algorithm achieves O (VTTT) regret bound, which again improves upon the (n regret bound of Agarwal et al. [2024]. For the contextual linear setup, we also establish O(ndy TT) regret bound. Due to space constraints, all results and proof's for the Prophet Inequality problem are deferred to the appendix.
Technical Overview for O( (VnT)) Improvement. Inspired by Agarwal et al. [2024], decompose the regret at any round by Σ, Term,,i. where Terms, captures the difference in expected reward when replacing the optimistic distribution of the i-th box, denoted by &,,i. with its true distribution Dj, while keeping all other boxes fixed. Agarwal et al. [2024] bound Term., by (TTV( D:)), where TV denotes the total variation distance. However, simply bounding Term, by the TV distance results in Ön vT) regret bound. To obtain tighter bound, take different approach to handle Term Let (o,, 2) be the expected utility when using threshold vector or, and the i-th box has a fixed value 2. We then write Term,, = fo (FD, (2) Fe., (z)) 0
85 (o, 2) da where FD is the cumulative density function of distribution D. Our main techniques to bound this term
follows. Technique 1: Bernstein-type Bound. Both our analysis and algorithm design are based on Bernstein-type concentration bound. In particular, our algorithm adaptively adjusts the probability mass when constructing empirical distributions, guided by this bound. This introduces an extra factor / Fb, (+) (1- (.) in the upper bound on (.) - Fe,. (-)., where & is the empirical distribution constructed at round t by assigning equal probability mass to iid samples from D;.
Technique 2: Sharp Bound of a Ro 2). We show 1-Lipschitz and monotonically -ncreaasing 8z
properties for Ra 2), which imply that S 8z prove a sharper bound where 0z (ar, 2) is bounded by the probability that the first i 1 boxes have values no larger than 2.
a Rç(o,, 2) S 1. Moreover, when 2 small, we
Next, we apply the techniques above to obtain a sharper bound for Term;, = So (z) Fg,, (2)) a bound for (FD,(2) Fe,, (2)) contributes to a factor (=) (1 - FD. (x)). which is small since a large 2 implies a small Fb, (z); on the other hand, when z is small, we use the sharper bound 8 on 02 R,,,,, 2) to obtain a tighter bound.
0z (, 2) dz. The high-level idea is follows: when is large, the Bernstein- type
Techniques for Contextual Linear Case. We first build virtual empirical distribution Dt,s for each box at round f, by using all available noise samples from this box plus the mean of the current round. This is virtual since only observe non-i.i.d. reward samples, not the noises. To overcome this issue, we introduce value-optimistic empirical distribution ε., by using the linear mean model to shift the observed samples to overestimate Dr,-- We then decompose Term,, into three terms, two of which can be handled in similar way as in the non-contextual case. The remaining piece is Ezwe,, [o ; 2)] E.. [R, =)] which measures the mean estimation error. This term is bounded by applying the 1-Lipschitz property of Rg(ogg, z) and contextual linear bandit techniques.
2 Preliminaries
In this section, introduce online Pandora's Box problem in both non-contextual and contextual settings. Due to the limited space, the Prophet Inequality problem is deferred to Appendix A.
Online Pandora's Box. In this problem, the learner is given n boxes, each with known cost G E [0, 1] and an unknown fixed reward distribution D. supported on [0, 1]. The learner plays T'round repeated game where at each round t [T], the learer decides an order to inspect boxes
3

---

Algorithm/ 1 Generic descending threshold algorithm for Pandora's Box
Input: threshold (0l...., Fn).
Initialize: Viax - -c. Let E [n] be the box with the i-th largest threshold. The environment generates an unknown realization 2 = (.i...., Cn.). for i = 1, ................................ do
Pay Cr. to open box Ty observe Ux,, and update Vmax = max Viaax Uz If i = or Vmaxx 2 Dn441 then stop and take reward Viax.
and stopping rule. Upon opening a box i, the learner pays cost o; and receives reward iy,, E [0, 1] independently sampled from D,. Once the stopping rule is met, she selects the highest observed reward far. The utility for the round is the chosen reward minus the total cost of opened boxes.
Contextual Linear Pandora's Box. This setting extends the above by allowing each box's distribu- tion to vary across rounds. Specifically, each box i E [rx] is associated with a known cost c; E [0, 1]. an unknown parameter 8; E R. and fixed unknown noise distribution D; with zero-mean supported on |- 1 11, At the beginning of each round E [ the learner observes context Tt. IR for each ji]jn]
1'
box i E [m]. These contexts { can be chosen arbitrarily by an adaptive adversary. Based on these contexts and past observations, the learner then decides an inspection order and a stopping rule to open boxes. Different from the non-contextual setup, upon opening box i, the learner observes the reward Ut2 = 1/t,5 + Mt. where [t, 0. It.; E [a 3] is the mean and 7/t,, a noise independently
drawn from 2 That is, the reward is drawn from the [o, 1]-bounded distribution Dr., = H4.s + D; mean ae.a- Following standard assumptions in contextual linear bandits, we assume that ||0:112 S 1 and || I 1 for all t,
which shifts D, by the context-depender
Optimal Policy and Regret. To measure the performance, we compete our algorithm against the per-round optimal policy. For both settings, the optimal policy at round t is the Weitzman's 's algorithm [Weitzman, 1978] which operates with the distribution D. = (Dr,1.... ............ D- In the non-contextual setting, the distribution is fixed across rounds i.c., D. = D = (D) we will retain the notation D; in the following. More specifically, Weitzman's 's algorithm proceeds by computing a threshold of for each box i, which the solution of Ez.D,,. 1( +[,,)+] = G, where (z)+ = max(0, .}. Then, the algorithm inspects the boxes in descending order of of, and stops as the maximum observed reward so far exceeds the threshold of the next unopened box.
Dn). and thus,
To formally define regret, we introduce the following notations. For any product distribution D (Dr...., D.). let ØD (Ø. D..) denote the optimal threshold vector, where each d is the solution of EE [( oD,) Cz. For any threshold vector a = (ø1...., σn) E [0, 1]" and reward realization v (VI,..., vn) E [0, 1J", we use W (a;v) C [r]] to denote boxes opened by Algorithm 1. Further, we define the utility function and expected utility function respectively as:
R(o;v) = max Uy NEW (o:))
Σ Cs. and D)o; = EuN-D(
(E:();))
With these definitions, the optimal expected utility is R(aD,; D:) since when v ~ Dr. the set W (a corresponds to the boxes opened by the Weitzman's 's algorithm. Let a; E T denote the threshold vector selected by the algorithm at round t. Throughout the paper, all our algorithms follow Algorithm I using o, as input at round f, and thus the expected utility our algorithm at round is R(o,; Dz). The cumulative regret in T rounds Regr is then defined as follows: Regr
E
Σ
t=1 R(oD,: D.) R(o;; Di)]. where D. = D for the non-contextual case.
3 Õ(VTT) Regret Bound for Non-Contextual Pandora's Box
In this section, we first present Algorithm 2 for the non-contextual Pandora's Box problem and the main result, and then discuss the analysis.
'The boundedness assumptions on the noise and mean ensure that rewards lie in [0, 1]. which avoids re- deriving standard results under a different scaling. Our results readily extends to sub Gaussian rewards. We refer readers to Appendix C.7 for details.

---

3.1 Algorithm and Main Result
While Algorithm 2 inspired by the principle of optimism in the face of uncertainty, its application differs from that in the classic mulli--ameed bandit setting, such as in the Upper Confidence Bound (UCB) algorithm [Auer et al., 2002]. In bandit problems, optimism is typically applied to the mean reward of each arm. In contrast, the Pandora's s Box problem requires learning the entire distribution of each box, particularly its cumulative distribution function (CDF). We follow similar idea to Agarwal et al. [2024], but employ different approach in the construction of optimistic estimate of the distribution. The threshold 0, is computed from this optimistic distribution, which implicitly ensures optimism in the algorithm''s decisions. More formally, we begin by introducing the notion of stochastic dominance.
Definition 3.1.1 (Stochastic dominance). Let D and E' be two probability distributions with CDFs FD and Fg, respectively. If Px==e(X 2 a) 2 PY~D(Y 2 a) for all E R, we say that E stochastically dominates D. and we denote this by IsD
For any two product distributions D = (D.,..., Dr)) and 3 = (Ei,..., E,), we use E EsD D to indicate that & sDD Dr for all i E [n]. Let ; be the number of samples for each box at round t and let (2()) be the round that the j-th reward sample of box is observed by the learner. We define empirical distribution and optimistic distribution as follows.
Empirical distribution Es.i- For each box i E [n]] we use my, i.idd samples (11,6),)) mea to construct E,, with respect to the underlying distribution D, by assigning each sample with probability mass mi,;" Specifically, FE., (x) = mi, EØ= I (v,,)) I x) for all x E [0.1].
Optimistic distribution E,,, Let L log((2nT /8). The CDF of &,, is constructed as follows:
x x= 1;
Fg,, (x) =
2F (a) Fe,,, (z))
(x),,
(I)
max 0, (x)
0<r<1.
Me,1
As verified in Lemma C.I.4, the construction in Eq. (1) ensures that F.e..() is a valid CDF We
denote &, (E,, Ei,n) and E. (Ê., (f., ). This type of construction has been previously used in [Guo et al., 2019, 2021], but our use differs substantially in the analysis. The following lemma shows that the optimistic product distribution stochastically dominates the underlying product distribution.
Lemma 3.1.2. With probability at least - 6, for all t E [T', we have & s D.
It is noteworthy that our approach to constructing the optimistic distribution is more adaptive than that of [Agarwal et al., 2024]. In particular, Agarwal et al. [2024] move a fixed amount of probability mass, approximately 1/ //m the maximal value that D; can take. In contrast, we adjust the CDF based on data-dependent confidence interval, resulting in a more fine- ane-grained and adaptive optimistic distribution. As stated in the following theorem, this construction results in tighter regret bound.
Theorem 3.1.3. For Pandora's 's Box problem, with ā = T-1 Algorithm ensures Regr = Ö(VnT)
Again, our bound matches the ?(vnT) lower bound of Gatmiry et al. [2024] up to logarithmic factors. It is worth noting that their lower bound is proven under the easier full full-information setting and thus applicable to our setting.
regret bound). Under regret metric Σ (R(aD: D) R(o; ( D)). our proposed algorithm also achieves high-probability bound of Ö(VnT) via two modifications only in our analysis. We refer readers to Appendix C.6 for details.
Remark 3.1.4
3.2 Analysis
In this subsection, we sketch the main proof ideas for Theorem 3.1.3 1.3 and summarize the new analytical techniques. We start by leveraging a monotonicity property for Pandora's Box problem, established by Guo et al. [2021]: for any distributions D, E, if >DD D, then R(āg; E) 2 R(op; D). Since
5

---

Algorithm 2 Near-optimal algorithm for Pandora's Box
Input: confidence (0, 1), horizon T' Initialize: open all boxes once and observe rewards. Set m1,; = 1 for all [m]. for f 1, .......................... ................................ do
For each [n]. construct an optimistic distribution E,,, according Eq. (1).
Compute o, = (0,,1..... rra)) where tr is the solution of I m-,, [
01.))+ Gs.
Run Algorithm with o to open set of boxes, denoted by B, and observe rewards (v,sheB, Update counters 14+1, My,s + 1, Vi E B, and m4+1, M4,i Vi $ B,.
the algorithm uses threshold gg at each round and Lemma 3.1.2 shows &, sSD D, the regret at round t, denoted by Reg(t), is bounded as
Reg t) E R(aD: D) R(o,; R(on&))) R(o,; D)] R(oo Es) - R(o;;; -
For simplicity of the exposition, without loss of generality, we assume that ot,1 2 0t,2 2 ... Ot. Following Agarwal et al. [2024], we define
H4.0 Es, and He (Di, Di. &i, ... ,,,,) for a,
(2)
Therefore Hi, D so that
R(o R(or; D) =
Σ Rior Ha,1-1) - R(ar H.,))
The decomposition in Eq. (3) breaks the reward difference into sequence of steps, where each step replaces one coordinate of the optimistic distribution with its true counterpart, thereby allowing for isolation of the effect of each individual coordinate change.
Let E be the event that box is opened under the threshold a, and let Eg be the corresponding complementary event. We define Qt, as the probability that a opens box given the true product distribution D. Using the same argument as in [Agarwal et al., 2024], we have that
E [R(or H1,i-1) - Mars He,s)l
E Qt, (ExwHeen [R (0)1z) Eord Eynn [R (or;z) Eoy,l)
(4)
Torm:;
The key step is carefully bound Termy,; and this is where our analysis fundamentally diverges from Agarwal et al. [2024]. Before presenting our analysis, we explain below why the previous analysis fails to achieve the Ö(VnT') regret bound.
ÖUUnTT) bound of Agarwal et al. [2024]. In the analysis of Agarwal et al. [2024], if the product distribution D discrete, then they bound Term,,, < O(U TVDD,, &), (cf. [Agarwal et al., 2024, Lemma 1.3)) where U is the upper bound of the absolute value of function R and could be as large as n. Therefore,
- Regr Σ Reg(() < Σ R(or&&) R(a D) < U Σ
Lo
( R
Since their algorithm moves probability mass by fixed amount, approximately each distribution i, simple calculation gives TV(D,, E.D,,,&, &..) < Õ(1/ /m,,), which in turn implies that
for
T
Q M
))
T
1) z (UNNT)). (5)
Reg, < o U.E
7
Σ
M
Q
1=1
t=1
where the second inequality follows from the standard analysis optimistic algorithms (e.g.. [Slivkins, 2019]), and the last inequality uses the fact that Σ Qi S for all t. It is noteworthy that

---

Σi= Qt. = 1 appears in multi-armes bandit problems since only one arm is played in each round. However, in the problems we consider, there chance open all boxes in one round.
Refined analysis for O(VTT)) bound. To get the Ö(vnT) regret bound, suffices to show
Reg(t) & (iV Q.s/ma)) since
T
Q
T
Qt
Regr $ Ô
E
Σ
Σ SEim
E
I
(VTT) nT
me,
mc,
t=1
EE
where the second inequality follows from the Cauchy-Schwand inequality, and the last inequality results from the bound Ee,' Qr./mm, I (n).. For any threshold [0, 1J" and E [0, 1]. define
Ra 2) Eg-He. [R (o; (Z1,..., 8i-1: 2, 2, , xn)) Ea,i.
(6)
Based on these definitions and the fact that E is independent of i-th box's reward, we write
Term = =E E- [o(( RE (o))
The following lemma is key enabler for refined analysis of both problems.
Lemma 3.2.1 (L-Lipschitzness and monotonicity). Consider the Pandora's 's box problem. For all e [T]. i E [n]]. the function R2 z) is 1-Lipschitz and monotonically-innraaatii with respect
Since =)) is I-Lipschitz with respect to z, the map [ay; z) is absolutely continuous on [0, 1). which implies that is differentiable almost everywhere in [0, 1]. By the fundamental theorem of calculus, for any E [0, IJ. we have that (oGG)) = [or 0) fo a (a 2) dz. Then it is straightforward to deduce that
Term = 1/² (1 Fe,,())
① 2x(onz) de ( (1-Fb,())) Oz
R. 2) de
Oz
[/¹ (Fo,(2) - -F&,
R((0(2) dz
Oz
2 p (Fo.(z) - Fé (z)
(2) Fe., (z)
dz
R2(on)))
de,
Oz
Br,
where the incquality holds since R2 (or: 2) is 1-Lipschitz with respect and thus its derivative is bounded in [] almost everywhere. Here, we decompose Term,, into two parts AG, and B to isolate contributions from different value regions, enabling a problem-dependent analysis that yields sharper regret bound. An advantage of this analysis is to avoid using [Agarwal et al., 2024, Lemma 1.3], which incurs a linear dependence on U. Indeed, we have
(2. - (=), dz + {' Jest
Ar, S
(e), - (x) dz
de,
L
Fo, -FD,
(e), FEr, (z))L
dz +
dz
Mii
Jonis
Mi,
Me,
L
(1 (o.(otii1))
Fe. (o1,4+1)
0
+
Mi,i
mi,i
My,5
FD.
L
50
M7,5
mi,s
where the second inequality bounds [Fb, (2) F&,, (2) by Bernstein-type Dvoretzky- Kiefer-
Wolfowitz inequality (cf. Lemma C.1.2 in Appendix C.1) and bounds Fe, (z) Fé., (=)) by the
7

---

construction Eq. (1); the third inequality bounds 1 FD, (z) < FD, (0t,)))) and an analogous inequality holds for Fe,. (z) since 2 2 01 the last inequality replaces Fe., (0r,)41) with FD, (or,i+)) by paying term of the same order (ef. Eq. (19)).
To handle the term Br instead of bounding the derivative by one as before, we introduce the following lemma which more tightly bounds the derivative by the probability that the first boxes have values no larger than 2, conditioning on opening box i.
Lemma 3.2.2. Suppose that 01,1 2 012 2 ... St,-- Pandora's 's Box problem satisfies
0 (o 2) s III 0 s 8z
FD, (z)/Qu,
4a E (0,00,,00 00,01,
jei
For shorthand, define of Appendix C), have that
= Iiisi Fn,
By Lemma 3.2.2 and some calculations (deferred to
V 08-1v--- dz
Bi, -
ED.(2) - FF
Qr,
a dz Qti
(IFD,()) (2), Fer((z) - (e), V
L m4i
1 I' Voo//o/ (at-1(1-Pn(())
L me,
dz
VQu.
where the second inequality follows from ai-1 S a, S 0, Qui for all 0r and
the last inequality repeats the same argument used to bound Ar,i to bound (FD Fe,,, (=) and [Fs., (z) - Fé.. F (2)]. respectively.
Plugging the above bounds of At.; into Eq. (3) and Eq. (4), the regret contribution of {Ar i at round I (omitting L/m,, and some constant) is bounded by
LQu.
LQ Mas
Ean sE[m]
Σ EEix]
M4,5
mas
EE
where the first inequality follows from the Cauchy-Schward inequality, and the second inequality fol- 0t. lows from Eie(n) Qt,i(1 Fn, (o), < 1. Indeed, since Qt,i 0;-1 and 0t,1 2 022 2 Tt,n.
we have that Qr,i S 0;-1 01.+1 which in turn yields the telescoping sum > Qt, (1 (o..44.)))) S
EE Similarly, the regret contribution of {Bia}i round (omitting L/ma, and some constant) is bounded by
(4-11 0tat1
0; ((.t1) 1.
Σ/ a di sE|n]
LQu dz < f me,
(af of) KE(n)
Σ
Σ KE
LQ dz Mi,i
S
LQ Σ KE|D
my,5
where the first incquality scoping sum and at < for all Hence, the cumulative regret is bounded by O O(VEe Qu. Combining all the results completes the proof of Theorem 1.1.3.
the Cauchy-Schwarz inequality and the second inequality uses the tele-
4 ((ndVT) Regret Bound for Contextual Linear Pandora's Box
In this section, we present Algorithm (in Appendix D) for the contextual linear Pandora's Box prob- lem. While our algorithm inherits the main structure of Algorithm 2, it introduces key modifications to ensure optimism, which is critical in the contextual setting. construct optimistic product distribution which stochastically dominates the underlying product distribution D, for each round In the non-contextual case, the optimistic distribution is constructed by using iid samples to first construct empirical distribution and then move the probability mass.
ensure the optimism, we need to

---

However, due to -oneettdeeennentt shifts, this strategy no longer applies. To address this, we leverage the fact that the shift in each box's 's distribution is determined by a fixed but unknown vector 8,. M where (.. () + Pr.. since they can be treated ma,i iid samples drawn from Dr. However, the learner never directly observes the noise sample Tt,()).- To overcome this, we maintain an estimation Oz, at each round by using ridge regression on past observations. Specifically, for each opened box Bi, we make the following updates: 0G, = Vi,i EeStriE, Ls,,",,i where =+,=++>> E.ESiEE Ts.ifg,i. T Let X' denote the context space. By the analysis of linear bandits (e.g.. [Abbasi- et al., 201 for each box i E [n]] there exists known function B : X x (0, 1) R such that with probability at least 6, for all x E X' and t.
natural idea here is to construct empirical distribution by using samples {)),))))
(0, 0-1..) s (1, 8), where (x, 6) o (1ellvzL, Vlog(nd-1) + dlog T/d)
With a confidence radius of 0, we construct a value-optimistic empirical distribution & by assigning each of the following with equal probability mass m,
.or min 1,w.) LCB| (0, - Fua)) + UCB (0-1,, 21.5
Optimistic dehiased noise sample
Optimistic estimated mean
where for any context x E X, any failure probability 8 (0, and any 0 IRd
(0) := x (z, and LCB == x (I,
(8)
The construction of E is value-optinistic because (), 2 2... holds. If one has ma,s samples round for box i, then ε.,; stochastically dominates the empirical distribution constructed by using samples {=f, (f). m.. Then, for each box we construct the optimistic distribution &L, by moving a small amount probability mass for the value-optimistic empirical distribution &,, so that it dominates the true distribution (the detailed construction of E.:; and the proof are deferred to Appendix D).
Lemma 4.1. With probahility at least for all E [T], & EsD D;-
Once the optimism is ensured, we prove the following regret bound for Algorithm 5 in Appendix D. Theorem 4.2. For contextual linear Pandora's 's Box problem, choosing = T for Algorithm ensures Regy- = O(nd/T) regret bound.
While the algorithm of [Atsidakou et al., 2024] applies to setting with ((TT5/5) regret, The- orem 4.2 gives VT regret bound in the contextual linear setting, which is better whenever d d= o(T The tightness of ((dv/T) remains an open question. In the contextual linear bandit setting with 01 however requires learning separate noise distribution for each box, and we conjecture that this makes the linear dependence on n unavoidable, even when all boxes share the same O.
0n the known lower bound is ((d/T) [Dani al., 2008]. Our setting
Analysis. As Lemma 4.1 ensures that & sD D, for all I, we follow the same argument in the non-contextual case to arrive at Eq. (4). The decomposition of the main term in Eq. (4) slightly differs from that of the non-contextual case. We introduce an empirical distribution Dr for the decomposition, which is constructed by assigning equal probability mass m for each (2 1mmr
Notice that conditioning on history before f, D, is product distribution. Then, conditioning on the history before t, for any i, the main term rewritten as
Term. E E
R((0t12) - E.wEL (((()12)) + E ExwEr,
R((o - E E...D. D.,
(2(222
(1)
+ E BenD.. Ra(oni2) - EewDes R((on22)
(1))

---

Here, term (I) captures the error of optimistic reweighting, which arises from shifting probability mass in the empirical distribution Eτ,; to construct the optimistic distribution Et,- Term (III) quantifies the estimation error between the empirical distribution Dr.: and the true underlying distribution D.. Both can be bounded in similar way as in the non-contextual case. It thus remains to handle (II, which captures the eπror incurred by the optimistic value shifts. One can show that
midi
1
1II
MeZ
1=1
where the inequality uses 1-Lipschitz property (see Lemma 3.2.1). Following standard linear bandit. analysis (e.g., [Abbasi- Yadkori et al., 201 I], the total regret incurred by (II) for all boxes bounded by (omitting constant)
T2
E2
Q
Ma,s
T
n2
E
Qui
(((
1 ma,i
122.
Σ j=1
ma,5
j=1
i=1
The first summation term can be bounded by
n ΣΣ B 01) So Ō
T
mry
min p v ÖnddTT), Σ
where the last incquality applies the Seuuhh-Sccwwazz incquality followed by the elliptical potential lemma [Abbasi-Yadkori Yadkori al., 2011, Lemma 11]. The second summation term be bounded similarly. We refer readers to Appendix for the omitted details.
Conclusion and Future Work
In this paper, propose new algorithms for the Pandora's Box problem in both non-contextual and contextual settings. In the non-contextual case, our algorithm achieves a regret of Ö which matches the known lower bound up to logarithmic factors. For the contextual case, we design modified algorithm that attains (ndv/T) regret. We further extend our methods and analysis to the Prophet Inequality problem both settings, achieving similar improvements and regret bounds. Our results also elicit compelling open questions:
1. Minimax regret for Prophet Inequality. We establish an upper bound of Ö(VnT) for Prophet Inequality problem, while Gatmiry al. [2024] proved lower bound of Q (2(TT). leaving /n-gap. In fact, Jin et al. [2024] show that the optimal sample complexity Prophet Incquality is (())), independent of n. which suggests that simple explore-then-comee strategy achieves an n-independent regret upper bound of ((T2/3). Whether Ö(VT) is achievable remains open.
2. Tighter regret for contextual linear case. In the non-contextual case, bound scales as /n, while the contextual linear setting, it grows linearly with n. Can this dependence be improved? It also remains unclear whether the linear dependence on the dimension d is improvable.
Acknowledgments and Disclosure of Funding
HL is supported by NSF Award IIS- 1944673 LJR and are supported in part by ONR YIP N000142012571, and NSF awards AF-2312775, CPS-1844729.
References
Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Infommtionn Processing Systems, 2011.
A. Agarwal, R. Ghuge, and V. Nagarajan. Semi-bandit learning for monotone stochastic optimization. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1260-1274 IEEE, 2024.
10

---

S. Alaci. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972, 2014.
A. Atsidakou, C. Caramanis, E. Gergatsouli, O. Papadigenopoulos, and C. Tzamos. Contextual pandora's box. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10944-10952, 2024.
Auer, Desa-Bianchi, and Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002.
H. Beyhaghi and L. Cai. Pandora's problem with nonobligatory inspection: Optimal structure and a ptas. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 803-816, 2023.
H. Beyhaghi and L. Cai. Recent developments in pandora's box problem: Variants and applications. ACM SIGecom Exchanges, 21(1):20-33 3:20-34,,22 2024.
S. Boodaghians, F. Fusco, P. Lazos, and S. Leonardi. Pandora's box problem with order constraints. In Proceedings of the st ACM Conference on Economics and Computation, pages 439 2020.
S. Chawla, E. Gergatsouli, Y. Teng, C. Tzamos, and R. Zhang, Pandora's box with correlations: Learning and approximation. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1214-1225. IEEE, 2020.
V. Dani, T. Hayes, and S. M. Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, 2008.
Ezra, M. Feldman, N. Gravin, and Z. G. Tang. Prophet matching with general arrivals. Mathematics of Operations Research, 47(2):878-88) 898, 2022.
M. Feldman, O. Svensson, and Zenklusen. Online contention resolution schemes with applications
to bayesian selection problems. SIAM Journal Computing, 50(2):255-300, 2021.
H. Fu and T. Lin. Learning utilities and equilibria in non-truthful auctions. Advances in Neural Information Processing Systems, 33:14231-11244 2020.
H. Fu, J. Li, and D. Liu, Pandora box problem with nonobligatory inspection: Hardness and approx- imation scheme. In Proceedings of the 55th Anmual ACM Symposium Theory of Computing, pages 789-802, 2023.
K. Gatmiry, T. Kesselheim, S. Singla, and Y. Wang. Bandit algorithms for prophet inequality and pandora's 's box. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 462-500. SIAM, 2024.
E. Gergatsouli and C. Tzamos. Online learning for min sum set cover and pandora's box. In International Conference Machine Learning, pages 7382-7403. PMLR, 2022.
E. Gergatsouli and C. Tzamos. Weitzman's rule for pandora's 's box with correlations. Advances in Neural Information Processing Systems, 36: 1644-11664, 2023.
N. Gravin and H. Wang. Prophet inequality for bipartite matching: Merits of being simple and non adaptive. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 93 93-109, 2019.
C. Guo, Huang, and X. Zhang. Settling the sample complexity of panlee- revenue maxi- mization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 662-673, 2019.
C. Guo, Z. Huang, Z. G. Tang, and X. Zhang. Generalizing complex hypotheses product distributions: Auctions, prophet inequalities, and pandora's problem. In Conference on Learning Theory, pages
PMLR, 2021.

---

J. Jiang, W. Ma, and J. Zhang. Tight guarantees for multi-uni uniti--mit prophet inequalities and online stochastic knapsack. In Proceedings of the 2022 Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
B. Jin, T. Kesselheim, W. Ma, and S. Singla. Sample complexity of posted pricing for single item. arXiv preprint arXiv:2406.008: 00819, 2024.
R. Kleinberg and S. M. Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth anmual ACM symposium Theory of computing, pages 123-136, 2012.
R. Kleinberg and S. M. Weinberg. Matroid prophet inequalities and applications dittesinmmn mechanism design. Games and Economic Behavior, 1 113:97-115, 2019.
U. Krengel and L. Sucheston. Semiamarts and finite values. 1977.
B. Kveton, C. Szepesvari, Z. Wen, and A. Ashkan. Cascading bandits: Learning rank in the cascade model. In International conference on machine learning, pages 767-776. PMLR, 2015.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
E. Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pages 1213-1216, 1984.
Singla. The price of information in combinatorial optimization. In Proceedings of the twenty-ninth ammual ACM-SIAM symposium on discrete algorithms, pages 2523-2533 SIAM, 2018.
A. Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12(1-2): 2019.
M. Weitzman. Optimal search for the best alternative, volume 78. Department of Energy, 1978.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide clear motivations for the research questions in the introduction section and explicitly itemize contributions, outlining how address and resolve these challenges throughout the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In this paper, for the contextual model, we only study the linear structure of rewards for both Pandora's 's Box and Prophet Inequality problems.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
All assumptions are clearly stated in Section 2 and we defer the proof to Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper is theoretically oriented. There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper is theoretically oriented. There are no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce cc/
sow.eedosaummsiiooooooooroo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp..ccc ccppp.ccpppullc///eecccc/ gealdiic/guiee...ee /CodeSubmia agionoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper is theoretically oriented. There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper is theoretically oriented. There are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper is theoretically oriented. There are no experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips: httpp//p...ccpbicicccccccooeeeee
Answer: [Yes]
Justification:
We have reviewed NeurlPS Code Ethics and commit to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the introduction, we highlight that our research can benefit sequential decision makiing problems, modeled by Pandora's Box and Prophet Inequality. We do not foresee any negative societal impacts arising from this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is theoretically oriented and does not release any data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This is theory-oriented paper with experiments code.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is theory-oriented paper. There are no new assets introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the datasettcodeemmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This is theory-oriented paper. There are no experiments or research with human objects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is theory-oriented paper. There are no experiments or research with human objects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This work does not involve LLMs as any important, original, or non- non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https /tt////eurippp//ee Weeeurips.cc/ooffeeeee wtw.feeeeneeee2//////// /LLMM for what should or should be described.
19

---

Appendix
Problem Setting of Prophet Inequality
21
Related Work
21
Omitted Details from the Non-Contextuni Settings
23
C.I Technical Lemmas
23
C.2 Lipschitz Property, Monotonicity, and Sharp Derivative for Pandora's Box
24
C.3 Lipschitz Property, Monotonicity, and Sharp Derivative for Prophet Inequality
27
C,4 Proof of (VViT)) Regret Bound for Pandora's Box
28
C.S ÖVVTT) Regret Bound for Prophet Inequality
C.6 Sroo-Prrbbbilitty Regret Bounds..
................................
32
C.7 Extension to Subgaussian Rewards
32
D Omitted Details of Contextual Linear Setting
33
D.I Preliminaries.
33
D.2 Algorithms and (ndyT) Bounds for Pandora's 's Box and Prophet Inequality
................................
34
D.3 Proof of Lemma D.2.2
36
20

---

Algorithm 3 Generic threshold algorithm for Prophet Inequality
Input: threshold = (o1...., Fx).
The environment generates an unknown realization v = (.1,..., Un).
for i 1, ..... do
Open box to observe Ug. If u, 2 o3 i n, then stop and take reward e4.
A Problem Setting of Prophet Inequality
Online Prophet Inequality. In this problem, the learner given n boxes, each with an unknown fixed reward distribution D; supported on [0, 1]. The learner plays a '''round repeated game where at each round t E [T]. the learner inspects boxes fixed order. Upon opening box i, the learner receives a reward 2t,4 E [0, 1] independently sampled from D,. Then, she needs to decide immediately whether to accept this reward and stop the process at round or discard this reward and open the next box. The utility for the round is the chosen reward.
Contextual Linear Prophet Inequality. This setting extends the non-contextual one, and the assumptions on reward distributions and boundedness are the same as Section 2.
compare our algorithm against the per-round optimal policy. Let D. = (Dt,1, ..., Dt..) be the product distribution of boxes. The optimal policy for Prophet Inequality in round t is also threshold policy, in which the threshold for each box i, demoted by o7,; is derived from a reverse/backward programming.
Optimal Policy and Regret. To measure the performance,
Definition A.1 (Optimal Threshold on D.). Let oi Ex~D,, [X] For i = n - 1,..., 1, ler
of = ExxD,, [max(XX X, H.
The optimal policy at round t is to run Algorithm 3 with threshold vector oj. In fact, the optimal threshold of box computed from Definition A. is equal to the expected reward obtained by running directly from box [Gatmiry et al., 2024].
oinn -
More formally, similar to those definitions in Pandora's Box setting, for any product distribution D = (Di...,,D) D,). let OD = (DD...... DD.) denote the optimal threshold vector, where each D, the threshold calculated by reverse programming. For any threshold vector (aI, on.) [0, 1J" and realization V = (V1,..., Up) E [0, 1]",, we use S(orv)) v) E [n] corresponds to the box where Algorithm stops. Further, we define the utility function and expected utility function, respectively:
R(o;v) = and R(o; D) EV-D (R(o
With these definitions, the optimal expected utility is R(oD,; D2) since when v ~ D,, S(oD,;)) e [n] corresponds to the box chosen by the optimal policy. Let σ, R" denote the threshold vector selected by the algorithm at round f. Throughout the paper, all our algorithms in the Prophet Inequality setting follow the general structure outlined in Algorithm 3 using o, input at round f, and thus the expected utility of our algorithms at round t is R(o;; Dz). The cumulative regret in T rounds Reg, then defined as
T
Regr
Σ
R(ong D.) R(ag D.)
where D. = D for the non-contextual case.
B Related Work
The Pandora's Box problem, introduced by Weitzman [1978], has been extended in various directions, including matroid constraints [Singla, 2018], correlated distributions [Chawla et al., 2020, Gergatsouli and Tzamos, 2023], order constraints [Boodaghians et al., 2020], and settings without inspection [Fu et al., 2023, Beyhaghi and Cai, 2023]. The Prophet Inequality problem was first studied by Krengel and Sucheston [1977], Samuel-Call [1984], with subsequent generalizations to k-selection [Alaei, 2014, Jiang et al., 2022], matroid constraints [Kleinberg and Weinberg, 2012, 2019, Feldman et al., 202 and online matching [Gravin and Wang, 2019, Ezra et al., 2022). These works typically assume known distributions and focus on achieving constant-factor approximation guarantees.
21

---

A growing body of work has begun to study online variants of the Prophet Inequality and Pandora's s Box problems [Guo et al., 2019, Fu and Lin, 2020. Guo et al., 2021, Gatmiry et al., 2024, Agarwal et al., 2024]. In the PAC setting, Fu and Lin [2020]. Guo et al. [2021] establish a sample complexity upper bound of ((2) ) for Pandora's 's Box, matching the known lower bound up to logarithmic factors, where с denotes the desired accuracy. Guo et al. [2021] further develop a general framework for learning over product distributions, which applies to both problems and yields sample complexity of ((*) for Prophet Inequality as well. Later, Jin et al. [2024] provide near-optimal sample complexity ( ) for Prophet Inequality, which removes the linear dependence on n. For the regret minimization problem, Gatmiry al. [2024] establish Ö( VT) regret bound for Prophet Inequality and O VT) regret bound for Pandora's Box under a constrained feedback model, where the learner observes only the final reward without knowing which box produced it. Subsequently, Agarwal et al. [2024] introduce general framework for monotone stochastic optimization under semi-bandit feedback, achieving (nnVT) regret for both problems. All these works assume fixed but unknown product distribution. Moreover, despite this progress, the best known regret bounds for both Prophet Inequality and Pandora's 's Box under semi-bandit feedback remain at (T)TT), which falls short of the known lower bounds [Gatmiry et al., 2024].
To better capture the dynamics in docisionn-mkingg scenarios, Gergatsouli and Tzamos [2022] study the Pandora's ss Box problem in the adversarial setting where the reward of each box chosen by an adversary and obtain sublinear regret bounds by comparing the algorithm against a weak benchmark. Later, Gatmiry al. [2024] show that in the same setting, when the algorithm competes against the optimal policy, no algorithm can achieve sublinear regret, even with full information feedback. To make the problem tractable while still allowing distributions to change over time, Atsidakou et al. [2024] explore contextual Pandora's 's Box model where in each round, the learner observes context vector for each box, whose optimal threshold can be approximated by a function of the context and an unknown vector. They provide a reduction from contextual Pandora's Box to an instance of online regression. Their algorithm suffers ((T5/6) regret bound if the threshold can be linearly approximated. We note that their algorithm for the linear case also applies to our setting (see the discussion below), but our algorithm enjoys Ö(ndyT) which is improves on the aforementioned bound whenever d = o(T2/3).
Discussion of [Atsidakou et al., 2024]. Here, we show how the algorithm proposed by Atsidakou et al. [2024] can be applicd to our setting. Their work makes the following realizability assumption.
Assumption 1 (Realizability of [Atsidakou et al., 2024]). There exists wi...., Wn Rdd and a function h such that every time i E [T] and every box i E [n], the optimal threshold for distribution Drs is equal to h(w,, 2 2',)), ie., o. = h(w,; s1,,)) where x'c, is a context vector of box i at round and
IE X-Dr,,
[[X - -r,,),+)++ =
Below, we show that in our setting, the optimal threshold can be realized by linear function (that is, h(a, b) = a b). To see this, first note that the optimal threshold o7, in our setting satisfies Ex [(X ot,)+]
C,, which, based on the definition of Dr is equivalent to Ex-D. [(X- (07, - [],]]]]] C where μe, = 0. 21,5. Therefore, if we let of be the unique solution of Ex=D, 1(X of) = C₁ then we have
o = Ma, + o
21,)) a(w,,21,)))
for wi = (0.,1, 0c,s, oI, E RRd+0 and x/,,- = ([z,,)),..... [ze, O,..., 1,..,,,,... 1,..., 0) E
Rd+=, where 2²,, takes value one at the d i index. This proves that the optimal threshold is realized by a linear function of some context, making the algorithm of [Atsidakou et al., 2024] applicable to our setting.
seemingly related strand is cascading bandits [Kveton et al., 2015], where the learner presents an ordered list of items to a user, with items corresponding to boxes in our setting. Then, the user scans the list and clicks the first attractive item if any. The learner observes binary click signals for items up to that click, which yields order dependent semi bandit feedback. Despite this shared feedback structure, Pandora's 's Box and Prophet Inequality differ in who controls how many items are inspected. In cascading bandits the number is user driven since observation stops at the first click. In Pandora's '
22

---

Box and in Prophet Inequality the number is policy driven since the algorithm adaptively opens boxes and decides when stop.
Omitted Details from the Non-Contextual Settings
C.1
Technical Lemmas
Lemma C.1.1 (Bernstein inequality). Given mn N, X2,X2,...
Xm be ii.d. random variables
such that [[X,] = 0, E[X?] o², and [xil S M for some constant M >> O. Then, for all >> 0
t²
X >)) S eexp 2mo Mt
Lemma C.1.2. Let D D Da) be a [0. 1l-bounded product distribution, for each i, let ENLA be the empirical distribution constructed by assigning N₂ i.i.d. samples from D, with equal probubility mass 1/N, With probability at least 1 8, for any [m]. any N; [T], and any
2 E 10,
2F 2F), - (z) log(2T2nd81) log 1og(27"'o N
- -Fx, (z) S
(10)
N;
Proof. This proof follows similar idea to Guo et al. [2019, Lemma 5], but apply additional union bound to account for all possible N.. Fix and N,. It is suffices to show that for all z E [o, I] such that FD, (z) is multiples of 1/N, the following holds.
(z) - (2) log(2T2 2 2log(2T
(2) - (2)) S
(11)
N₂
3N,
This is because given the results above, the general bound on the difference of CDF of any value
differs at most an extra additive factor N. 1n 3N;
Then fix any z such that Fb, is multiples I/, Let Y, be the indicator function of the i-th sample smaller than and let X, Y E[Y]]. By Bemsstein inequality (see Lemma C.I.I), taking t be N₁ times the RHS Eq. (11),
N; Σ
2
X
>
exp
2N, FD. (z))
<
T
Since N₁ < T, by a union bound over all N,, with probability at least 1 z such that FD, (z) multiples I/N,. Further, by union bounds over all [n] and N, E [T]. we get that Eq. (10) does not hold with probability at most 5.
7 Eq. (11) holds for all
4
O
As (.) is unknown, we present the following corollary, which provides a confidence bound depending known (.)
Corollary C.1.3. Under the same setting of Lemma C.1.2, suppose that the concentration bounds of Lemma C.1.2 all hold, and then for any E [n]). any N, [T] and any x E [0, 1].
2Fxx. (I) - FEX,, (I))L
L N."
(D) FEx.. (x) S
where 4log (2nI (12)
N
Proof. Fix any and N₂. For notional simplicity, we write & EN. For any x. E [0, 1).
FD, (x) Fr, (x)) Fe,
Fe, (z)) - 1Fr,
(x)) Pe, (x) Fe, (x))
< Fe, Fe, (x)) + (x) (x) F5, (z)l,
(13)
where the last inequality the fact that function y² is 1-Lipschitz for y [0.1].
23

---

Let L' = -ogg(2nT281) From Eq. (10), we can show for any E [0,
2FD. (x) (x))
L'
(x) 5
N,
N
21. (F) - (e) (F) - (x)(
In
N.
N;
2L'Fe, (x) -F,(x))
2L 1L, Fe, (x))
L'
N;
N₂
N
2L'Fe, (z) FF,
(D.(F) - Fe, (x)(
2L'
(14)
N.
N
where the second incquality uses Eq. (13), and the last inequality uses 2 ab S a a for any a, 2 (here L' LN, and b = ] Fn (z:) F', (r)).. Rearranging the above inequality gives the claimed bound for fixed i, N,. Since this argument holds for all i, N,, the lemma thus follows.
Lemma C.1.4. For all t, Fe,, constructed by Eq. (1) is a valid CDF
Proof. To show Fg,, Fg.. (.) is valid, we show that it is right-continuous, non-decreasing function in the range of [0, 1]. Consider any given I, é. From Eq. (1), one easily F (1) [0, for all x E [0. 1]. As (-). is right-continuous and max function preserves the right-continuous property, Fe.. (.) is again right-continuous.
Now, we verify the monotonicity of Fe,,(). (:). Since F.,,()) is non-decreasing, we only need to show Feg,, (x) non-decreasing as function of (x). Let = ب. For the interval x such that Fe,, (x) < k. Fe., (x) is 0, and thus it is non-decreasing. Then we only need to consider the interval of x such that Fe,, (a:) 2 k. We let y Fe., (z), and rewrite the formulation for Fe., (x) as vE(1-2y) V2y(1-y) When y 2 1.4 this is obviously non-negative, and thus fy) is non-decreasing. Then, we consider the case of < and show that 22y(1- y) > vk(1 2y). As y k, is enough to show 22y(1- y) vT 2y). This is equivalent show 4y² 2y 1 < 0 when y 2, which can easily verified.
f(v) 2ky(1 1 y) k. In this case, (v)
As the argument holds for all 1, i, the lemma thus follows.
Lemma C.1.5 (Restatement of Lemma 3.1.2). With probability at least for all [T]. ε, >s D.
Proof. For this proof, we show E., ssD D, for all f, Fix t, suffices to show that for all [0, 1], Pe.,()) < FD, (x). For 1, Fe., (x) FD, (x) = 1. For [0, 1), we have
(F), Fe,., (x))
Fe,, (z) max 0, Fe,,
Ma.6
Me,
S max Fb, (x)} = (x),
where the inequality follows from Corollary C.1.3. Repeating the same argument for all E [m] completes the proof.
C.2 Lipschitz Property, Monotonicity, and Sharp Derivative for Pandora's Box
Before proving Lipschitz property and monotonicity for Ri 2), we first introduce the following supporting results.
24

---

Definition C.2.1 ((n, D, ca)adaadds box instance), We use (n, D, c) to characterize Pandora' 's box instance where product distribution D (D....., Dn) is over boxes, each of which is associated with a cost Ct.
For any (n, D, Pandora's box instance, let W.: [0 x [0, 1J"h + 2 be a general threshold rule with imitial value u. Specifically, for any initial value u, threshold 0, and realization ~ D, (a 2) the set opened boxes following rule W.. For any u, a. the initial value 2 max, ds. then Wa Wa(a. -) = 0, that is, the learner does not open any box and keeps the initial value u. Otherwise, the learner keeps the initial value u in hand but continues to open boxes by running Algorithm with Vinx and threshold a. Let
R;;; max (",
max IG (EW.(o;)
Σ C
iEW.lo;2
R(o; D; = E xnD
Here, R(o;x; x; u; We) the utility if the learner adopts rule W. to run threshold o with initial value over realization æ. As shown by Weitzman [1978], for any initial value u, the expected utility R( D; u; Wa) enjoys the optimality.
Lemma C.2.2 (Monotonicity and 1-Lipschitz Property for Pandora's Box), For any initial values u, u, if the learner runs general threshold rules W,, and W. with a 2 o, respectively on (n, D, c)- Panddrr'' 's Box instance, then we have
S
E [R(OD;;;; u. R~D
E ( S aND
Consequenctly, the following 1-Lipschitz property holds: for any u, U.
[R u; r>D
E
E. [R(an; W.)] x>D
I v/.
Proof. Consider any u 2 For any realization x = (II,.... un) drawn from product distribution D, the utility given the initial value (= u or v) and rule W is
R(ap; 8; W) max
max (oDa))
Ii
(aDaa)))
Taking W = W., and s = a and v, respectively, we have
E
[Roon;,;
E (RODD;I;;;W... r~D
} max {
E z~D
max
U, max (EDD()
max (EWs(oD:s)
34
Given the initial value u and threshold an, using rule W., recovers the Weitzman's 's optimal algorithm. Thus, the corresponding expected utility should be no smaller than that running rule W. with the same threshold a and initial value u, i.e., EzED [R(o x;; u; W. < Ez=D [R(ap; ue W.)), which implies 0 < Eg-D D [R(a x;; u; W.]] Eg-D [R(aD: 3; W.))
Taking W W.. and and respectively, have
[R(OD; u; Ww)] [R(oD; W.)) z>D
zND
}
max u, max sEWalOD:E)
Ti
max
v, max NEW.
2;
Z>D
Su
where the inequality holds since for any x, (v) = max(u, U, x is 1-Lipschitz with respect to U.
As W,, is optimal given initial value v and threshold an we have EgnD [R(apaa; u; Ww)) <
ExED [[app;;; az; v; W.)]. implying Er Pann(R(ap))) [R(ap; u: W.)) E (, W.)] $ Thus, the lemma follows.
25

---

For any E [0,1]", we define 2si == (I++1...... In) and 2<i == Ti-1). Based on the
definition of H (D1,'" Di, E,, C. we define
H4 = (E,, (E,,441..... Enn and H4 == (D,...,,II.I..
For any 2 E [0, any a e [0, 1J", and any [0, 1J we define Re(o; =
[ (o; -1-1 2441 ,.tt Tn)]] z Husi
(15)
E
[ (a; (T), (I1y..,, :.. Tn))],
where the expectation is taken only for 2>1 == (Ii+1...... Tn).
Lemma C.2.3 (Restatement of Lemma 3.2.1). For all E [T] and i [n], the map Ro 2) is 1 1-Lipschitz and monotonically-inceaaann with respect to z in the Pandora's 's Box problem.
otn. For any 2 [0, 1] and any z E [0, 1 if box i is opened at round f, then the map R, [;; T<i 2) is the expected utility of running di (I++1,..., Tn)) He,5 with initial value max ................................ 1) key fact here is that o = ogg and He,s = (E,,41,.... E, which imply that the algorithm runs the optimal threshold in descending order. Thus Lemma C.2.2 implies that (, Feis 2) is 1-Lipschitz with respect to and for any u 2 v, and that R((or;eei, Re(os;Tes, v) E [0, u - v]. This, in turn, implies that
Proof. For simplicity, we assume without loss of generality that ot1 ot2 2
R,(og u) R((or;u)= scm(Dr -D-)) Ralonieen u) R.(onFe))) Eo., E 00 v).
E
The 1-Lipschitz property of [2(0;²) 2) is an immediate corollary, and the proof is thus complete.
Lemma C.2.4 (Restatement of Lemma 3.2.2). Suppose that 0t,1 ot, 2 2 Ot, The Pandora' Box problem satisfies the following:
Ô (((a2) 02
FD, Qr
0
Ae E (0,0
Proof. According to Lemma 3.2.1, the map R₁ (or,; 2) is monotonically increasing with respect to which implies that 0 < 02 (an Then, only need to prove for any 0 0r,--1,
8
II [ Se,FFD, (u)
Rd u) o)(an;)) & (u v)-
(16)
Qt
To this end, we deduce the following:
Ri(oru)) - R((or;))
R( - (( Ea.t]
(D Dj 1)
E
Ra max fax u}) R2 (a max fren vf) Eors
CeinDrr... Dj 1)
max ( u) max (xei, Eags)
E < (u v) Dcin(D,. Di-i)
(max (Z max (Fch R maxx,
}
Bood
(D Di-1)
jzb
E Ruz maxas }
Eort
jei
(u 11)
max x. < Fass jzt
(D
26

---

P Prer (maxj<i 22 < Boci)
(u U)
P (D Di-)) Di-1) (Poyi)
(u Pe D.-1 (max)< <1 23 < u)
Pre D.-1) (o,s))
(w)
-u
Qr.i
where (a) holds since conditioning on Eo., (i..., opening box i), the expected reward remains unchanged by replacing u (or v) by the maximum so far, the inequality Ri(o (e), with respect variable 2, (b) follows from the fact that max (Zigis u) max (Zics v) is non-zero only when mäxjei 2jj < as 2 v, and (c) holds due to [maxj<i < [u] C E where this containment follows from the fact that u < 0e S or,i and E,,, {maxjei Ty < ati)..
the 1-Lipschitz property of
Thus, the stated claim holds.
C.3 Lipschitz Property, Monotonicity, and Sharp Derivative for Prophet Inequality
In the following, we prove the similar results for Prophet Inequality.
Lemma C.3.1. Consider any two product distributions Du = (u, (2, D3...., Dn) and D, = (v. D2, Da...., Dn), where the first box deterministically produces rewards and respectively, and the remaining boxes share the same distributions. If 2 U, then
0 5 R(OD.: D.) R(OD.: D.)
As a corollary, we have the following 1-Lipschitz property. For any u, V.
[R(D.. D.) R(op.; D.)1 S v/-
Proof. As TD. is computed by backward induction from Definition A.1, we have R(OD,; Du) OD..1 max {u, D...2) Moreover, since the distribution of boxes from 2...., n are the same, DD... = D.. for all 2 2. For any u 2 v.
R(ap,; D.) R(oD.; D.) max (u, (D.22 max (D.2) E [0, v], where the inequality holds since max function is 1-Lipschitz and p = DD.22 Thus, the lemma follows.
In the Prophet Incquality problem, the definition of R.(o;; 2) takes the same form as Eq. (6), but uses the utility function R defined in Eq. (9). Similarly, we follow Eq. (15) to define Ro 2). again using the utility function defined in Eq. (9).
Lemma C.3.2. For all t [T), E (n). Re(a;)) 1-Lipschitz and monotonically-incresiing with respect to in Prophet Inequality problem.
Proof. As the order the boxes is fixed across time, we use Lemma C.3.1 to repeat similar argument in Lemma 3.2.1 to complete the proof. The only difference is that conditioning on event that the learner opens box i, R2(a;; K-ci z) can be interpreted as the expected utility of running o (Di+1,.... 2nn ~ H4,5i with 2; = since Tı, I1,..., 2;-1 are discarded.
Lemma C.3.3 (Sharp Bound Derivative for Prophet Inequality). The Prophet Inequality problem satisfies
i (()=))
Vz E (0,
8z
Proof. For any 5 S oeii we have that
R((og;)- - R,(0)v)= (D. D.-.) [R(lo - Ra v) Ears) 0,
E
where the second equality uses the fact that if the learner opens box and the realized value smaller than deis then they will discard it and keep opening subsequent boxes. Thus, the lemma follows. D
27

---

C.4 Proof of (VnTT) Regret Bound for Pandora's 's Box
The analysis in this section conditions on the event that the concentration bounds of Lemma C.1.2 hold with respect to D and & for all t. Recall from Section 3.2 that regret is bounded by
n
(R((01))
Regr
E
Que
E znd,
(17)
EniEe
=:Torm,,
Consider any given round / and suppose, without loss of generality, that
o11 2 ot2 ... Ttn.
Since (o 2) is I-Lipschitz with respect to 2, the map (ay; 2) is absolutely continuous on [0, 1]. which implies that is differentiable almost everywhere in [0, 1). By the fundamental theorem of calculus, for any x E [0, 1), have that Ro) (a,; + Jo d= (a(a)) dz. Therefore, have that
Term = E
[
R)(onz)
2nD:
R)(00) + L
2
0 (o,t)) dt /
E
(ontt) dt
E anDD
R. 0)
2-Et,
0l
[/'
θ Rr(ont)](z 2 1 dt
a Ra t)T(=)(((== 2 1 dt
E znbe,e
E
Ot
anD
ōt
= = (1-Fg.
θ Oz
[ (1 (1- F-)(
Ri(oi; dz
Ra dz.
Oz
According to the analysis in Section 3.2, we bound
② Termy S S Fb.(2) - Fe., (=) dz + corit (FD, Fe,, (z)
R.(o)))) dz.
Oz
Ar,
Big
Now, we complete the bounds Ae,i and Br,ū. Bounding Ar.- We have
(2) dz f'
A S
(Fb.
FE,
Fe,,( de
L
(2) (2)(
(ey.(=)(1 - FE,,(()))
0
dz
dz
My,i
Jolil1
M4,
mi
Fe,, (ots41)))
0
My,i
Ma,i
FD.
L
00
(18)
Mi,
Mi,
where the second inequality bounds [FD, (=) Fe,. (z)] by Lemma C.1.2 and bounds Fe,, (z) F5., (2)l by the construction Eq. (1), and the third inequality bounds 1 Fp, (2) S Fp. (0),
(similar for (z)) as = 2 01.411 The last inequality follows from the following reasoning:
Fe,, (o),41))
Ma,i
(1 FD, (0r,st))) L Fe,, - Fp. (0),
Mi,
28

---

(or
Fe., (or,11))))))))))))))))))))))))) - FD, (0t,++1)
V
m4,5
m4,1
11 FD, (02,6111))
- -FD, (o,,(0
L
m4,5
2
M2,1
11 (o,(o1s+1))
L
(19)
Ma,
M1,5
where the third inequality uses 2ab I + for any a, 2 0, and the last inequality bounds Fe,,( (ot,4+1) - FD, (0e,4+1) by Lemma C.1.2.
Bounding it. By Lemma 3.2.2, we bound
Vlber (2) Iliss (x)
06,61
BB <
(r) - (x)
dz
Qt,
Ilies (2)
(IFb Fe,, Fe),()) + (e).(=) Fē, (z)
dz,
(20)
Q1i
where the second inequality bounds ]T F2,(2) I IIi FD, (oe,44)) I IIiess FD, (o,(0)))) = Qi, for z < 01
On the one hand, we use Lemma C.1.2 to bound for any
(2) - (+)l o ( (D, Fb. (z))L
L
5
(1 Fb)
ma,i
m4,5
ma,5
my,i
On the other hand, we use the construction of optimistic distribution EG, in Eq. (1) to show for any
(e). Fe., (3) so $0(v
(1 (v(1- Fe, FE),()))
(vV
L
(2)
0
+
ma,
m4,5
ma.5
me,
where the last inequality repeats the same argument in Eq. (19). Plugging the two bounds above into Eq. (20), we have that
Fb,
L
)
ITyes (2)
B₁ 0
dz
mi,s
m4,
Qi
mati
Il FD, (=) FD, FD, (=))
II FD5(2)
L
o
+V
dz
Qesmur
Qui
mis
L
[I JIK
FD. -D(1))
0
dz
My
Qeiman
L
L''
Hi FD, (z) (z))L
00
dz
m4,i
Qu,imui
where the second inequality follows from
I (x) Qu.t
Hies FD, Qut
Is FD, (or.)
<
<
Qu,
based on the fact that J0,441 and Qt,i II (o..)
29

---

Regret for round t. From the bounds of At, and Br, the regret at round t is bounded as
FD, (0r,s+1))
Reg(() -
Σ
Term SO E Σ
m4,1
iE|n]
ic(m)
Lise PD, (=) Fb. (=))
LQQ.
Σ
dz +
m4,i
ma,s
kE(ni
The first term is bounded as follows:
(o.(4)11))
E
Qu
Maz
Mm(m
LQI, me,i
LQu.i
E
2r,(1 - (o.(t)))))
Σ EEIn
s
E
mi,
kE|m]
MEin
where the first inequality uses the Cauchy-Schree inequality, and the second inequality follows from the the fact that
Σ Qu,(1- (D. = vE(n)
II Foy - FD,(Orst1))
AE|m]
Σ AE|m] jób
II
Fny (o)st)))) Fr, (o(,4)))
Σ EEIn
II jUi
(o15t))))) II Fb, (o1j41) J5A
S1 1.
Here, the first inequality holds since the descending sorted assumption on o, gives Otji11 2 oe. for all j < i, and the last inequality follows from the fact that the summation forms telescoping sum.
To bound the second term, show that
II J (b) (2) dz
Σ /E|m]
m4,i
LQua de mi,i
II (1) FD.())) (FF()()))
jes
LQ dz
<
Σ II (2) - (D)()))
Σ
kE(m)ses
kE(m)
my,i
LQ
<
Ma,i
kE(M)
where the first inequality uses the Cauchy-Schwarz inequality, and the last inequality follows from the fact that Eie(o] ] FD, (=) Fr, (=)) forms a telescoping sum.
Combining all bounds above. we have
LQu.
LQQu
Reg(t) S
Σ
mi,5
mi.s
VEin)
30

---

Algorithm 4 Proposed algorithm for Prophet Inequality
Input: confidence (0, 1), horizon T' Initialize: open all boxes once and observe rewards. Set m1,; = 1 for all E [m]. for t 1, 2....... do
For each i [n]. construct an optimistic distribution ε,, according Eq. (1).
Use Definition A. with distribution & to compute o₃ (0 Tt.n).
Run Algorithm with o open set of boxes, denoted by B, and observe rewards (v.J)eB,
Update counters m4+1, Ma, + 1, Vi E B, and m4+1,5 me,s, Vi & B.
Summing Reg(t) over all t. The Cauchy- -ehehar inequality gives
LQ
LQQ, my,i
Regr S O
E
Σ
mi,i
8EIn
LQ mid
LQ ma,
0
E
T
VE(N
LQ mi,i
LQt.
SO
T
Σ SEim
E
+ E
(21)
my,
where the last incquality uses Jensen's 's inequality. Finally, it remains to bound E
Σ
LQua/mes]]
Let Le,i 1=111 1.
LQ
LE
Lhta
E
-E
E
S O (og))) (22)
may
[m
iE(m]
iE(m]
where the second equality holds due to my, deterministic given history before round t.
Combining the bound E [> LQQ. m..] = log with Eq. (21) completes the proof of Theorem 3.1.3.
C.5 Ō(vnI Regret Bound for Prophet Inequality
The proposed algorithm for the Prophet Inequality problem shown in Algorithm Theorem C.5.1. For the Prophet Inequality problem, choosing T 1 for Algorithm 4 ensures
Regr = ( logTT)))))
log(n(T) + log log(T))
Proof. The analysis conditions on the event that the concentration bounds of Lemma C.1.2 hold with respect to and &, for all t. As shown by Guo et al. [2021], J], the Prophet Inequality satisfies the same monotonicity Pandora's 's Box. Thus, the analysis follows the same approach as used in the Pandora's Box problem bound Regy < Σ'" Σn E [Qr.: Term, where Term,, has the same definition as in Eq. (4) with new utility function R defined in Eq. (9).
As shown in Lemma C.3.2, the Prophet Inequality problem has both monotonicity and smoothness properties. Therefore, repeating the same analysis in Scction 3.2 (splitting the integral on oe, instead of 01,++1) gives
['
F2. FFe.( dz dz+ Fe, (FFll((
(FD.le)
θ
Term <
Ra 2) dz
0z
FD.(2) Pee, (z) dz,
0,,
Ar.
31

---

where the equality applies Lemma C.3.3, We use the same argument as in Eq. (18) to bound Ar.s: indeed,
(ors)))
)
A,, SO
+ ma,s
me,i
Thus, the regret round / bounded by
(1 (D.
Qua
Reg(t) s 5
Σ Eui
m4,i
iE(n)
iE(m
In partieular, bound
(1 FD, (or,)))
Qray
me,i
QeeL
s
Qr (ora))
Σ
Meii
iE(ml
(E(M)
Qeit Σ
QuaL m4,i
ΣII VE(N
FI, (or,) (F,.)((
mz,
(E(M)
KE(M)
where the equality holds since Qt Iīsci FD, (oe.s) in the Prophet Inequality setting.
By repeating the same argument as in Eq. (21) and Eq. (22), the proof of Theorem C.5.1 is complete.
C.6 High-Probability Regret Bounds
The regret metric now is
Reg' [(B(OD: D) - R(o;; D)).
(23)
t=1
Following the same argument in Section 3.2, we arrive at Eq. (4) without expectation. As a and Has are deterministic given history, we have
R(a,; H1,5-1 R(or; H.,)) R2 [R(a,; H1.-1) - R(o,; Hr,)),
where [-] is the conditional expectation given history before round Then, we can follow the same analysis to arrive at / Ex,r Qu.t, To handle this, let M,,, = Qui-tes and {Me,sh is martingale difference sequence. By Freedman's 's inequality, with probability least 1- we have Σ. M <
mec.:
/2V 1og log(1/8)) where V V= "I [M,]]] Notice that V= Qr.c-Qi. S Qui. Thus, we have Σ. M,, S / /2 log(1/))) E, Qt,/mm,i (ogg(16))) I 1 E. Qts/mi, + 2logg(1/) where the last step the AM-GM inequality. Rearranging gives Σt=1 Qui O(log(1/6) + Σt- A.s)).
me..
me.
Therefore, by choosing properly and applying union bound, with high probability, the regret is bounded by Ö(vnT).
C.7 Extension to Subgaussian Rewards
For each box, if the reward distribution is sub-Gaussian then our algorithms still work with minor modifications. Specifically, the reward distribution box is K,-sub-Gaussian one can set a range [- 1 log(222n)) K.y2 Inn Then, the algorithm updates parameters only the received reward of each box is within range of [-K; (ogg(()mm) 2 K, / log n2] On those rounds, the algorithm and its regret analysis coincide exactly with the bounded- setting. Meanwhile, by a union bound on uab-Gausiian tails, the probability that any reward ever exceeds its range is most L/T' Therefore, its contribution to the expected regret is only Õ(1).
32

---

D Omitted Details of Contextual Linear Setting
D.1 Preliminaries
Lemma D.1.1 (DKW Inequality). Given a natural number N, let X XN be i.idd samples from distribution D with cumulative distribution function FD(.). Let Fg(.) be the associated empirical distribution fianciion & such that for all TR, we define Fe( N E 1(x; S x.). For every
> 0
P supl Pe(a)) Fn(x)) > < 2exp(-2NN8)
ØER
Lemma D.1.2. Let == (D....., Dz) be a product distribution, and for each i, let EN be the empirical distribution built from N; i.i.d. samples of D.. With probability at least 1 8/2, for any i [n), any N; E (T),
log(4Tnó ))
sup =ER
(D. (x),
(24)
2N,
Proof. We first fix any and N; and apply Lemma D.1.1. Then, the lemma follows by using union bound over all E [n] and N; (T].
Lemma D.1.3.
With probability at least 1 8/2, any and any E [n].
00 0..1ll,, 08,
where 08 =1=1+ 2 2log(2n/0) + dloog (1+
T
Proof. Fix any E [n]. Since the noise distribution of each box is --subgaussian, and { is Rd-vvlued stochastic process such that 2t,; is measurable with respect to the history, [Lattimore and Szepesvári, 2020, Theorem 20.5] directly gives the claimed result for the fixed i. Using union bound over all E [n] completes the proof.
Lemma D.1.4 (Elliptical Potential Lemma (see, e.g., Lemma 11 in [Abbasi- Yadkori et al., 201 Let E Raxd be an identity matrix and a sequence of vectors @1 u1,...,0N Rd with ||a: 2l S 1 fooor all E [N]. Let V E.st aza!. Then, for all E N, we have
Σ min (1, loelli, :} < 2d (1+ )
Definition D.1.5 (Delinition of D.) Let Dj = Dr..)
where each D1. is empirical distribution which assigns my,i ii.dd noise samples from D, with equal probability mass 1/m4,-
Definition D.1.6 (Nicc"" event). Let & be the nice event that the concentration bounds in Lemma D) 1.2 for D, Dr hold for all E (T), and the concentration bounds in Lemma D. 1.3 hold simultaneously.
Lemma D.1.7. Suppose that & holds. For any context E X and any round t [T).
K2, - 0.) < (x). (x).
Proof. For any t, i, x, one can show that
( (s.00.. 0. 0,) s |= |0:- Biul vo, S as Lasl|=lly.. (,+1(x),
where the first inequality follows from the Cauchy-Schwarz inequality and the second inequality uses Lemma D.I.3.
33

---

D.2 Algorithms and ((ndVT) Bounds for Pandora's Box and Prophet Inequality
The omitted algorithm for both the Pandora's Box and Prophet Inequality problems presented in Algorithm 5. Unlike the non-contextuul case (see Eq. (I)), we use a slightly different construction for the optimistic distribution. This is because the Bernstein-type construction requires access the CDF of an empirical distribution based on i.i.d. samples, which is unavailable in our setting. As result, we use the following approach instead.
Optimistic distribution Et,t. Let L log(4nT/66. The CDF of Et,i is constructed as follows:
(1,
1,
1;
Fe,, (1)
mmxx {0, Fe,,
(25)
0 1.
me,s
Now, we prove Lemma 4.1 which shows that the optimistic distribution &, stochastically dominates D, for all
Lemma D.2.1 (Restatement of Lemma 4.1), Suppose that holds. For E [T], & s0 D..
Proof. For this proof, we show Ei, EsD D for all i,t. Fix a box i E [n] and a round E [T].
2 1, then
Px (X S c) - PX-D, (X s c) =.
For any e 1, we have that
L
P Px~e. (x) max 0, OxPe (x)
mi,
I max {0.P2~D.. (Z sc
Fz-Do. c))
The inequality holds due to the following reason:
Pxwei 5
me,s
24,1 + + LL + 2C, S sa - -1 m4,i
I.
1=1
L
11 Muin + +UC sc
m j=1
m4ss
Le my,i
if HmAGA S c- sc-
PX (X S.C c- p4,i)
= =PZ-D., (Z c)
where the first inequality follows from the facts that (uut). LCB( ()) 0, the second inequality uses the fact that U (e., 2 Mr,is and the last inequality follows from the concentration bound given by 6.
Conditioning on the "nice" event, the argument holds for all i and t. The proof complete.
Next, present the following lemma, whose proof is in the next subsection.
Lemma D.2.2. Suppose that holds. For both the Pandora's 's Box and Prophet Inequality problems, we have that
T ΣΣ
Reg S
Qti
M4,5
M j=1
t=1
34

---

Algorithm 5 Proposed algorithm for contextual linear model
Input: confidence (0, 1), horizon T.
Initialize: observe context (Zo, hie(m] for each box, open each box, observe rewards {uo, he(n) and
update counters f NE(M)) and parameters (fo,s hEE[M] where :0.: = (I To. -1 Vb,
for / = 1, .,2,..., do
Observe contexts (Zi,,1...,,, Tt,n)) and compute āi, (ōi-1,5, v...) for each [n].
For each i E [n], use Eq. (25) to construct empirical distribution E,, by using samples Va.i -
+ (CB sctiEBs
if Pandora's Box then Compute o, (fc.)--.;; r,,)) where of is the solution of E. &owe, Is axd) = Cs. Run Algorithm with o; to open a set of boxes, denoted by B, to observe rewards for, heB.
else if Prophet Inequality then
Use Definition A. with distribution &, to compute o; = (or,1,..... Tta))
Run Algorithm 3 with to open set of boxes, denoted by B, to observe rewards (1r,))EB,
Update counters m4+1, = my, + 1, Vi E Bg and m4+1, = -e,i, Vi & B..
Update estimate for each i Bi:
V4, I
Σ
where 0..1 V
Σ
*St:EB
With Lemma D.2.2 in hand, we are now ready to prove Theorem 4.2.
Proof of Theorem 4.2. The analysis conditions on event & which is defined in Definition 1.1.6 and occurs with probability at least 1 5. Recall that T,2 T( For the first term, take the iterated expectation and use the facts that Qr = [ and me,i is deterministic given the history get
T
T
E
Quay
E
Jo
s ((nVTL)
mai
Next, we bound the summation of the second term. To this end, we show that
2t E
- - - #6.0
min
min
M.G), + +M,, min 110)) (1 UCB
< min
PRIDA -
me. - 71,(5) - -M.
min
PLUD LCB 24 (.).)) - m.on. +
meii)
min
MNGIA LCB( T.
UCB me.
(GGD). 0: - 0-11.) + 3/ (
(urs 10:00,-0.0 θ.-1.) + 3 (((r))
min
min 11, (2).0)))) 23 (x),
min {1, 2 (x)) min (1 (x,,))
(26)
where the first equality holds due to z(. "n E [0, 1), the first inequality uses |b (--minn minn11,a]|
la b) for b = [0, 1]. and the third inequality follows from Lemma D.1.7.
35

---

Using Eq. (26), we have that
a
Qia
Me,a
maii
15
1 me,
E
Qr,i
min (1, 8)} +
min (
me,i
For the second term on the right hand side, we have that
Qr
E
Mi,i
Q
min {1, (
068
E
mi,i
[=1
T
Q
min 1, {1.1pencssalllaadmm
0
E
m4,
[=1
T
Qu.
min 1, I v
066
E
ma,s
vito
m
[=1
i=1
/=1
dlog(1 T/dd
50
06
E
Quey
0o (ar-nn .n. d' log(1 + +T/d)
where the second inequality follows from V,-1, 2 V1,())-11 for all and i, the third inequality uses Cauchy-Schward inequality, and the fourth inequality follows from Lemma D.1.4.
Analogously, we take the iterated expectation and use the fact that Qr, = Ee[4,,l and || 1.: is deterministic given the history to conclude that
E Q1,i (1r2, 8)]
12
E Qr. min { 1|
06
i=1
1 min {1, (1lllaalll
06
E
min 1, Alllauonnilll (ll
06
E
mr.i
1, aol
E
Mrr
min
1=1
0
(s ny do'log(1 + T/d)
Combining the bounds above completes the proof of Theorem 4.2.
D.3 Proof of Lemma D.2.2
We follow similar analysis of the non-contextual case focus on the regret bound at each round and then sum them up together. Let us consider round t. For Pandora's 's Box problem, we assume
36

---

W.L.O.G. that ot, 2 022 2 ... On.. Similar to the non-contextual analysis, we define for all t, i
H4.0 & and Ha.s (Di,,.... Dr.is E1,,,1, EL,..)
We have H... Dj based on this definition. As Lemma 4. ensures the stochastic dominance and both problems enjoy a certain monotonicity, we follow the same analysis in Section 3.2 to show that
Reg(() EE [R(on; D) R(oe D)]
E
Qr E
[R(G) Bo..]
E y-HHe.
(R(o))) Bord
i=
Terme
Now, we define
Rl, = (Da1," (De3,1, Dess " E.m). &t. and
Na. = (DiI,... D2,5-1, E1,411, E.m.
Based on the definitions of He,s, He Ho,s, we compute the following decomposition:
Term:
E
[R (a(G))
Bo,,ll E
[R( v)
Eora
x~Hi,i-1
E
Eoril - E
[R(g) Eoral
H1
[((o Eorll E [R(o, Eoodl
zMH
(
[R(gx))
Facil
(((35)))
Food
z (M)
In the remaining analysis, we retain the same definition of Re z) as in Eq. (6). The analysis conditions this history before round I, and thus D, is product distribution.
Bounding (L) By using the fact that Eor, is independent of i-th box's reward, we can bound [o( Ea..)
11
E
(o);))))) Eaaal
z~H
E 2-Ei
R((oriz)]
- I SnNEs
[((oriz)
Oz (11 dz f" (1- Fe,
θ (1-Fe,s (=)) Rilan;)) dz Oz
(F- (3)
/ (Fein(e) (2).
θ R((o dz
Oz
f/' (z), Fg., (z) dz
<
L ma,5
where the first inequality follows from the fact that R, 2) is 1-Lipschitz for both Pandora's Box and Prophet Inequality problems (see Lemma 3.2.1 and Lemma C.3.2, respectively), and the last incquality uses the construction of E,, in Eq. (25).
37

---

Bounding (II). One can show that
(I)
(R(g))
Bocal
[R(azz) | Boci
xmd H
znH
E
[
[R((ori2)
zuDiee
mass
1 ma.t
RS ( (on1))))))))
R3 (on
Mi,1
m4,
jml
24 22.00,1/
My,
where the inequality again the faet that (2)0)))) is 1-Lipschitz for both Pandora's Box and Prophet Inequality problems.
Bounding (III). Then, we have
[R
Eandl
E Hr
[R(G)
|
Eocd
a-H
[Ri(oriz)]=
E zwDe
[R((otz)]
-S (F).,())-Fap) FD... (z)
0
(ots)) dz
Oz
FD.,(2) - -FD,, (2) (2) dz
$
(. Fb, - -Miii) - F' (z- -mei) dz
(v me.s)
o
where the first inequality follows from the fact that a2 R, 2) E [-1, 1] due to 1-Lipschitzness, and the last inequality follows from the concentration bound given by 6.
Putting together. Combining all bounds above, we have
L
Reg(t) s
o
E
Qt.
1=1
Summing over all t E [T', we complete the proof of Lemma D.2.2.
38


Reviews:
[{"review_id": "t64mdTNXVk", "reviewer": "Reviewer_HDSt", "summary": "This paper studies the online Pandora’s Box problem and proposes an algorithm that achieves a regret bound matching the known lower bound and improves over Agarwal et al. in the non-contextual setting. The authors then extend their approach to both the contextual linear setting and online Prophet Inequality problem. The key idea is to mimic Weitzman’s optimal policy by constructing optimistic empirical distributions that stochastically dominate the unknown true distributions. This allows the algorithm to compute reservation values using Weitzman’s thresholding rule, while encouraging exploration.", "questions": "Why the contextual-linear setting is defined on a  [−1/4,1/4] support?\n\nWhy the principle of optimism under uncertainty is helpful for improving the regret guarantee in this work?\n\nWhat is the weak benchmark considered by Gergatsouli and Tzamos? Similarly, what is the optimal policy benchmark considered in Gatmiry et al.? What is the benchmark used in this work for both the non-contextual and contextual cases?", "limitations": "The limitations in the assumptions of the contextual linear setting compared to real-world motivations could be mentioned.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThis paper tackles the online Pandora’s Box problem and proposes a novel algorithm that improves over prior work in both regret performance and generality. By leveraging optimistic empirical distributions to mimic Weitzman’s optimal threshold-based policy, the authors match the known minimax regret lower bound in the non-contextual setting, improving over the prior regret bound from Agarwal et al. The theoretical contributions are technically sound and show clear improvement over existing methods, and the analysis is rigorous with detailed proofs included.\n\nWeaknesses:\n\nThe main weaknesses of this paper lie in clarity and structure, which make the contributions harder to interpret than necessary:\n\nSome terms (e.g., full-information feedback, magnitude of the utility function) lack explanations.\n\nSeveral naming choices could be improved: e.g., “Term” in Equation (4) is vague and could be replaced with something more meaningful.\n\nThe thresholds in Weitzman’s algorithm can be referred to more meaningful standard terminology such as reservation values, Weitzman’s indices or Gittins indices that are widely used in prior work.\n\nThe paper does not clearly distinguish between previously known and newly introduced formulations and results. For example, Section 3 should be titled \"non-contextual online Pandora’s Box\" to reflect the setting.\n\nTheorem statements and algorithm descriptions lack sufficient context. For example, Algorithm 2 is used for the online problem, but is simply labeled for “Pandora’s Box”, which could be misread as referring to the classic setting. Similarly, Algorithm 1 is essentially Weitzman’s original policy for the classic setting, but this is never explicitly stated — and could be deferred to the appendix to prioritize space for the new contributions like Algorithm 5. Parameters such as delta are not referred with meaningful names in all theorem statements.\n\nThe problem formulation is fragmented: the assumptions, utility function definitions, and cumulative regret notions are introduced in separate places, making it difficult for readers to see the overall setup. A unified and clearly structured formulation section, distinguishing old and new contributions, would greatly improve clarity. It is also unclear why the contextual-linear setting is defined on a  [−1/4,1/4] support — this choice is not motivated or explained.\n\nMoreover, the benchmark definitions used for regret are not clearly stated across settings. For example, the paper mentions that Gergatsouli and Tzamos consider a weak benchmark—but what precisely is that benchmark? Similarly, what is the optimal policy benchmark considered in Gatmiry et al.? What is the benchmark used in this work for both the non-contextual and contextual cases?\n\nFinally, the proofs in the main text could be better structured by emphasizing high-level intuition and key steps, rather than presenting long sequences of inequalities that would be more appropriate in the appendix.", "was_revised": true, "final_justification": "After reading the responses, I agree the technical contribution is significant but can be stated more clearly. The writing also needs much improvement.", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concerns.\n\n---\n**W1:** Improvement of clarity and structure.\n\n**A:** Thank you for the suggestions; we will edit the paper accordingly.  In particular, we will better emphasize the  intuition for the proofs in the main text and defer technical details to the appendix.\nThat said, several of\nyour comments are very minor and can be easily addressed. In fact, it is worth noting that all other reviewers commented and agreed that the paper is well-written. While we appreciate your suggestions and will revise accordingly, we sincerely hope that you could consider raising the score given that the main weakness you pointed out pertains to clarity and structure.\n\n---\n**W2:** Algorithm 1 is essentially Weitzman’s original policy for the classic setting, but this is never explicitly stated.\n\n**A:** Algorithm 1 is a general version of Weitzman's algorithm since it accepts any threshold vector as an input. Algorithm 1 coincides with the classical Weitzman algorithm precisely when those thresholds are chosen optimally for the true underlying distributions, as noted in Section 2.\n\n---\n**Q1:** Why the contextual-linear setting is defined on a $[-1/4,1/4]$ support?\n\n**A:** This choice is made purely for simplicity, avoiding the need to re‑derive some standard results under a different scaling. In fact, both our algorithm and analysis easily extend to any other $[-K,K]$ support setting by simply replacing every $[-1/4,-1/4]$-bounded argument with its $[-K,K]$-bounded analogue. \nWe will clarify this in the revision to make it clear that $[-1/4,1/4]$ is for convenience and to make the paper concise by citing existing work where possible.\n\n\n---\n**Q2:** Why the principle of optimism under uncertainty is helpful for improving the regret guarantee in this work?\n\n**A:** Our contribution here does not stem from the optimism under uncertainty principle, which Agarwal et al. (2024) already apply   yielding only a $\\widetilde{O}(n\\sqrt{T})$ regret bound. \nWhile we build on their framework, the improvement we obtain derives from taking different approach altogether wherein we  construct the *optimistic distribution* (shift probability mass based on Bernstein type bound), and more importantly, the improvement owes to our highly refined analysis.\nWe highlight these differences in algorithm design and analysis in Section 3.1 and Section 3.2, respectively.\n\n\n\n---\n**Q3:** What is the weak benchmark considered by Gergatsouli and Tzamos? Similarly, what is the optimal policy benchmark considered in Gatmiry et al.? What is the benchmark used in this work for both the non-contextual and contextual cases?\n\n\n**A:**\nSince Gergatsouli and Tzamos (2022) allow the  distributions of the boxes to be chosen adversarially across rounds, competing against the optimal strategy is intractable.\nTherefore to ensure sublinear regret, Gergatsouli and Tzamos (2022) introduce two weak benchmarks: (1) a non-adaptive benchmark that opens the same fixed set of boxes in every round, and (2) a partially-adaptive benchmark that may choose a different set in each round based on the algorithm’s past choices.\nOn the other hand, Gatmiry et al., (2024) and our work (in both non-contextual and contextual settings) both use the *optimal strategy* as the benchmark. This is Weitzman's algorithm with  full knowledge of the product distribution at each round.\nWe will make clarification in the next version."}, {"review_id": "2livFm5nlL", "reviewer": "Reviewer_vRPG", "summary": "This paper studies an online variant of the Pandora’s box problem with $n$ boxes. In this problem, the player sequentially plays T instances of the Pandora’s box problems, one in each round. The assumption is that the reward distributions are unknown to the player but remain fixed throughout the horizon. In this setting, the authors prove an $O(\\sqrt{nT})$ regret bound against the best policy in hindsight, thereby improving the existing $O(n\\sqrt{T})$ regret bound. Their algorithm first constructs an optimistic version of the empirical distributions for each box, and then it computes the thresholds by using Weitzman’s method applied to the optimistic distributions. They obtain improved regret by using a sharper bound for a regret upper bound obtained earlier by [Agarwal et al].", "questions": "1. Is it possible to establish $O(\\sqrt{nT})$ regret bound with high probability? The paper only proves this bound in expectation.\n2. The authors assume that the reward distributions have a bounded support. Can the results be extended to distributions with unbounded support?\n3. For completeness, it is better to briefly reproduce the arguments from [2] leading to Eqn (4).", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The refined analysis is technically novel and interesting. The authors also extend their result to a linear contextual setting and the prophet inequality. The paper is well-written, easy to follow, and the related work has been discussed adequately.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I'll keep my positive score.", "rebuttal": "We thank the reviewer for positive feedback and your acknowledgment on our contributions. Below we address your concerns.\n\n---\n**Q1:** Is it possible to establish $\\widetilde{O}(\\sqrt{nT})$ regret bound with high probability?\n\n\n**A:** Yes. We can obtain a high-probability bound of $\\widetilde{O}(\\sqrt{nT})$ under regret metric $\\sum_{t=1}^T (R(\\sigma\\_{D};D)-R(\\sigma\\_{t};D))$ via two modifications in our analysis. First, LHS of Eq(4) now has no expectation, but since $\\sigma_t$ and $H_{t,i}$ are deterministic given history, we have $R(\\sigma\\_t;H\\_{t,i-1})-R(\\sigma\\_t;H\\_{t,i}) = \\mathbb{E}\\_t [R(\\sigma_t;H_{t,i-1})-R(\\sigma_t;H_{t,i})]$ where $\\mathbb{E}\\_t[\\cdot]$ is the conditional expectation given history before round $t$. Then, we can follow the same analysis to arrive at $\\sqrt{\\sum_{i,t} \\frac{Q_{t,i}}{m_{t,i}} }$. \nTo handle this, let $M_{t,i}=\\frac{Q_{t,i}-I_{t,i}}{m_{t,i}}$, and $\\\\{M_{t,i}\\\\}\\_{t}$ is martingale difference sequence. By Freedman's inequality, with probability at least $1-\\delta$, we have $\\sum_{t} M_{t,i} \\leq \\sqrt{2V \\log(1/\\delta)} + \\log(1/\\delta)$ where $V= \\sum_{t=1}^T \\mathbb{E}\\_t [M_{t,i}^2 ]$. Notice that $V =\\frac{ Q_{t,i} -Q_{t,i}^2   }{m_{t,i}} \\leq \\frac{ Q_{t,i}  }{m_{t,i}}$. Thus, we have $\\sum_{t} M_{t,i} \\leq \\sqrt{ 2\\log(1/\\delta)\\sum_{t}Q_{t,i}/m_{t,i}  }+\\log(1/\\delta) \\leq  \\frac{1}{2}\\sum_{t}Q_{t,i}/m_{t,i}+ 2\\log(1/\\delta) $ where the last step uses the AM-GM inequality. Rearranging it gives \n$\\sum_{t=1}^T \\frac{Q_{t,i}}{m_{t,i}} \\leq O (\\log(1/\\delta)+\\sum_{t=1}^T \\frac{I_{t,i}}{m_{t,i}} )$.\nTherefore, by choosing $\\delta$ properly and applying a union bound, with high probability, the regret is bounded by $\\widetilde{O}(\\sqrt{nT})$.\n\n---\n**Q2:** The authors assume that the reward distributions have a bounded support. Can the results be extended to distributions with unbounded support?\n\n\n**A:** For an arbitrary unbounded distribution, we believe the online Pandora's Box is intractable without further assumption.\nThe main hardness here is that a box may yield an extremely large reward with a very small probability. For example, consider two instances in which there is only one box cost $1$. In instance $I_1$, the box generates reward $2^T$ with probability $2^{-T+1}$, and generates reward $0$ otherwise. In the other instance $I_2$, the box generates the same reward with probability $2^{-T-1}$ and $0$ otherwise. Then, the learner needs to decide whether to open the box. The optimal strategy in $I_1$ always opens the box, whereas the optimal strategy in $I_2$ never opens it. However, distinguishing these two instances are statistically hard within $T$ rounds, and thus the online Pandora's Box with arbitrary unbounded distribution is intractable.\n\n\nHowever, if the reward distribution of each box is subgaussian, then, our algorithms still work with minor modifications. Specifically, if the reward distribution of box $i$ is $K_i$-subgaussian, one can set a range $[-K_i \\sqrt{2\\log(2T^2n)},K_i\\sqrt{2\\log(2T^2n)}]$.\nThen, the algorithm updates parameters only if the received reward of each box $i$ is within range of $[-K_i \\sqrt{2\\log(2T^2n)},K_i\\sqrt{2\\log(2T^2n)}]$.\nOn those rounds, the algorithm and its regret analysis coincide exactly with the bounded‑reward setting.\nMeanwhile, by a union bound on subgaussian tails, the probability that any reward ever exceeds its range is at most \n$1/T$. Therefore, its contribution to the expected regret is only $\\widetilde{O}(1)$.\n\n\n---\n**Q3:** For completeness, it is better to briefly reproduce the arguments from [2] leading to Eqn (4).\n\n**A:** Thank you for the suggestion. We will reproduce those arguments in the next version."}, {"review_id": "sRQSRBkL1c", "reviewer": "Reviewer_oZNk", "summary": "The authors study the Pandora's Box problem in a semi-bandit feedback setting, where the learning agent observes the realized rewards of the open boxes in a round. The first main contribution is regret bound of $\\tilde{O}(\\sqrt{nT})$, which improves upon the state-of-the-art. The improvement is brought about by an application of a Bernstein-type concentration inequality for a tighter upper confidence bound in the OFU-based algorithm, as well as a more refined sensitivity analysis on the error term $Term_{i, t}$ in Section 3.2. The authors also provide an improvement in a linear contextual generalization, and they improve the regret bound scaling from $T^{5/6}$ ($T$ is the number of rounds) to $T^{1/2}$.", "questions": "In addition to the question raised in Weakness point 2, I have an additional question and an additional suggestion:\n\nQuestion: It appears to me that the construction of the empirical distributions in the linear contextual case is different from the non-contextual case. Can I check that if I apply the algorithm in Section 4 on the non-contextual case (1 feature dimension per box), do we end up with $O(n^2 \\sqrt{T})$ regret, or is there some better way? \n\nSuggestion: The authors' model could have some connection to the cascading bandit model:\n\nhttps://arxiv.org/abs/1502.02763\n\nWhile the two models involve semi-bandit feedback depending on the ordering of basic arms/boxes, they are quite different in terms of the reward function. Nevertheless, I believe the above work is worth mentioning.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. I find the overall theoretical contributions substantial and worthwhile. Although the algorithm design is following the well-established optimism-in-face-of-uncertainty principle, the overall careful analysis that leads to $\\sqrt{n}$ is still an interesting technical contributions. The sensitivity analysis is tailored to the Pandora's Box setting, and appears novel in my opinion.\n\n2. The sketch proof in Section 3.2 is quite clearly written, and will be interesting to researchers to explore further generalizations.\n\n3. In the linear contextual case, the improvement in regret bound is substantial. \n\nWeaknesses:\n\n1. The boundedness assumption on the random noise in the linear contextual case seems to be a limiting assumption. In the traditional linear bandits, it suffices to assume a bounded mean reward, while the noise can have an unbounded supported as long as it is sub-Guassian. What is the fundamental barrier that forbids such a generalization. \n\n2. The authors assert that their regret bound of $O(\\sqrt{n T})$ is tight, due to the regret lower bound of $\\Omega(\\sqrt{nT})$ in Gatmiry et al. [16]. My understanding is that Gatmiry et al. [16] focuses on the purely bandit feedback case, meaning that after each round, the learning agent only observes the net utility gained, but does not observe the individual rewards of the opened boxes. Can the authors confirm that the lower bound in Gatmiry et al. [16] also applies in the authors' semi-bandit feedback setting? If yes, the authors should provide more explanations. If it is the otherwise, the authors should emphasize on the difference between the feedback model.", "was_revised": true, "final_justification": "I have read the response, and is satisfied with the response on the lower bound. I recommend the authors to provide more details that the lower bounds apply also to the authors' feedback setting to make things clearer.", "rebuttal": "We thank the reviewer for the valuable and positive feedback. Below we address your concerns.\n\n---\n**W1:** The boundedness assumption on the random noise in the linear contextual case seems to be a limiting assumption. In the traditional linear bandits, it suffices to assume a bounded mean reward, while the noise can have an unbounded supported as long as it is sub-Guassian.\n\n**A:** In fact, this assumption can be relaxed.\nFor each box, if the noise distribution is sub-Gaussian, then, the reward distribution is also sub-Gaussian, and our algorithms still work with minor modifications. Specifically, if the reward distribution of box $i$ is $K_i$-sub-Gaussian, one can set a range $[-K_i \\sqrt{2\\log(2T^2n)},K_i\\sqrt{2\\log(2T^2n)}]$.\nThen, the algorithm updates parameters only if the received reward of each box $i$ is within range of $[-K_i \\sqrt{2\\log(2T^2n)},K_i\\sqrt{2\\log(2T^2n)}]$.\nOn those rounds, the algorithm and its regret analysis coincide exactly with the bounded‑reward setting.\nMeanwhile, by a union bound on sub-Gaussian tails, the probability that any reward ever exceeds its range is at most \n$1/T$.   Therefore, its contribution to the expected regret is only $\\widetilde{O}(1)$.\n\n---\n**W2:** Does $\\Omega(\\sqrt{nT})$ lower bound in Gatmiry et al. [16] apply here?\n\n**A:** The $\\Omega(\\sqrt{nT})$ lower bound in Gatmiry et al. [16] indeed applies to our setting since their lower bound holds even in the full-information setting, thereby applying to ours. Specifically, Gatmiry et al., prove $\\Omega(\\sqrt{nT})$ regret lower bound by using $\\Omega(n/\\epsilon^2)$ lower bound for sample complexity. To see this, we here reiterate their proof idea. For the full-information feedback, if an online algorithm achieves $o(\\sqrt{nT})$ regret, then one can use online-to-batch conversion to get a $\\epsilon$-optimal policy with $o(n/\\epsilon^2)$ sample complexity, which contradicts to $\\Omega(n/\\epsilon^2)$ lower bound.\n\n\n---\n**Q1:** Can I check that if I apply the algorithm in Section 4 on the non-contextual case (1 feature dimension per box), do we end up with $O(n^2\\sqrt{T})$ regret bound?\n\n\n**A:** Our contextual setting uses a separate parameter $\\theta_i$ for each box $i$, which subsumes the non-contextual case as a special instance. In the non-contextual case, it suffices to set the feature dimension $d=1$, leading to a $\\widetilde{O}(n\\sqrt{T})$ regret bound. While this is worse than the $\\widetilde{O}(\\sqrt{nT})$ bound of our dedicated non-contextual algorithm, the linear dependence on $n$ arises from the estimation error of context-dependent means. The technique used to obtain the tighter $\\widetilde{O}(\\sqrt{nT})$ bound does not carry over to the contextual setting. Whether the $\\widetilde{O}(nd\\sqrt{T})$ bound is tight remains an open question for future work.\n\n\n---\n**Q2:** The authors' model could have some connection to the cascading bandit model: ``Kveton et al., Cascading Bandits: Learning to Rank in the Cascade Model, ICML 2015''. While the two models involve semi-bandit feedback depending on the ordering of basic arms/boxes, they are quite different in terms of the reward function. Nevertheless, I believe the above work is worth mentioning.\n\n**A:** We thank the reviewer for highlighting this interesting paper. We will make sure to include this reference in the revision."}, {"review_id": "v9q04vYW0L", "reviewer": "Reviewer_3xhg", "summary": "This work improves the regret guarantee for the online learning problem in the Pandora's box problem from $\\tilde{O}(n\\sqrt{T})$ to $\\tilde{O}(\\sqrt{nT})$, via a Bernstein-type construction for the optimistic construction. \nThe paper further extends the problem to the contextual case with linear rewards, and achieves an $\\tilde{O}(nd\\sqrt{T})$ regret in that problem, where $d$ is the dimension of the context.", "questions": "- Could the authors explain in detail how their use of Bernstein inequality is different from Guo at al. (2019)? \n- Could the authors address why the similar algorithm gives different reliance on $n$ for the regret bound on the non-contextual and contextual problems?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The results of this paper are solid, and the paper is written well, striking a good balance between intuitions and technical details. \nHowever, I think some discussions are still required to further improve the readability of this paper. \n\nFirst, Bernstein-type solutions are given in Guo et al. (2019) to solve the sample complexity for auctions and other related problems. \nThis paper mentions that the use in analysis is substantially different from that of Guo et al. (2019), but not in detail. \nAs for me, the idea of using Bernstein inequality to construct stochastically dominated empirical distributions is similar. \n\nSecond, it is interesting and also natural to ask why the dependence on the number of boxes $n$ is different for the non-contextual and contextual problems in this paper, but the authors do not discuss this point.", "was_revised": true, "final_justification": "I will keep my score.", "rebuttal": "We thank the reviewer for the valuable feedback. Below we address your concerns.\n\n---\n**W1 and Q1:** This paper mentions that the use in analysis is substantially different from that of Guo et al. (2019), but not in detail. As for me, the idea of using Bernstein inequality to construct stochastically dominated empirical distributions is similar. Could the authors explain in detail how their use of Bernstein inequality is different from Guo et al. (2019)?\n\n**A:** Our use differs significantly in both the algorithmic perspective and the analysis. \n\n\n- **Algorithmic perspective.** Since Guo et al. (2019) focuses on the sample complexity, they first collect sufficient samples over all the distributions of the boxes to construct empirical distributions, and then output a near-optimal policy from *pessimistic distributions*, which reallocate the probability mass of empirical distributions toward *lower outcomes*. \nThis is *exactly the opposite of our optimistic scheme*, where we shift mass to *higher outcomes*. \nAs we focus on the regret minimization, the algorithm needs to balance exploration and exploitation.\nTo this end, our algorithm uses optimistic distributions with Bernstein-type adjustment, which encourages the algorithm to adaptively explore the distributions of the boxes.\n\n\n\n- **Analytical perspective.** The analysis of (Guo et al. 2019) requires *sufficient and equal* amount of samples for each box. However, since our algorithm adaptively explores boxes, the  sample size varies across boxes, and some boxes may only have a small sample size. \nWe therefore conduct a finer‑grained study of the exploration process and show that a Bernstein‑type concentration bound naturally captures its adaptiveness and delivers the desired regret guarantees.\n\n\n\n---\n**W2 and Q2:** it is interesting and also natural to ask why the dependence on the number of boxes $n$ is different for the non-contextual and contextual problems in this paper, but the authors do not discuss this point. Could the authors address why the similar algorithm gives different reliance on $n$ for the regret bound on the non-contextual and contextual problems?\n\n**A:** The different dependence on $n$ arises primarily because in the contextual setting, our analysis needs to bound the estimation error of context-dependent mean, which leads to a linear dependence on $n$.\nUnlike the non-contextual case where the reward samples are i.i.d., in the contextual case the mean reward varies with the context, and the observed samples are not identically distributed across rounds. \nTo ensure stochastic dominance, we construct an optimistic distribution by shifting the sample values in an optimistic manner. The regret introduced by this value-shifting scales linearly with $n$, and the technique that yields the $\\widetilde{O}(\\sqrt{nT})$ bound in the non-contextual setting, does not  extend to the contextual case."}]

Author rebuttal:

Meta-review: The paper studies an online setting of the classic Pandora's box problem and improves the regret bound of prior work. Overall, reviewers are positive about the submission, and they think the paper has interesting technical contributions. I would also recommend authors to include some clarification discussions in the rebuttal to the final version of the paper.
Decision: Accept (poster)