Learning in Prophet Inequalities with Noisy Observations
Authors: Jung-hun Kim
Vianney Perchet
Venue: ICLR 2026 Poster (2026)
Keywords: Optimal Stopping
Prophet Inequalities
Learning
Decision-Making
Primary area: learning theory

Abstract: We study the prophet inequality, a fundamental problem in online decision-making and optimal stopping, in a practical setting where rewards are observed only through noisy realizations and reward distributions are unknown. At each stage, the decision-maker receives a noisy reward whose true value follows a linear model with an unknown latent parameter, and observes a feature vector drawn from a distribution. To address this challenge, we propose algorithms that integrate learning and decision-making via lower-confidence-bound (LCB) thresholding. In the i.i.d. setting, we establish that both an Explore-then-Decide strategy and an $\varepsilon$-Greedy variant achieve the sharp competitive ratio of $1 - 1/e$, under a mild condition on the optimal value. For non-identical distributions, we show that a competitive ratio of $1/2$ can be guaranteed against a relaxed benchmark. Moreover, with limited window access to past rewards, the tight ratio of $1/2$ against the optimal benchmark is achieved.

Published as a conference paper at ICLR 2026
LEARNING IN PROPHET INEQUALITIES WITH NOISY OBSERVATIONS
Jung-hun Kim
Vianney Perchet
CREST, ENSAE, IP Paris
"Criteo Lab
FairPPay joint team
junghun. www.ensaee.e.....em...........ee fr
vianney, wianney.perchetenne pww.rpeeeceeeeeeeeeeeuu...ooo.
ABSTRACT
We study the prophet inequality, a fundamental problem in online decision- making and optimal stopping, practical setting where rewards are observed only through noisy realizations and reward distributions are unknown. At each stage, the decision-men makerr receives a noisy reward whose true value follows lin- ear model with an unknown latent parameter, and observes a feature vector drawn from a distribution. To address this challenge, we propose algorithms that inte- grate learning and pacision-making via lower-confidence-bnn ing. In the i.i.d. setting, we establish that both an Explore- cesooore-hen---e and an E- e-Greedy variant achieve the sharp competitive ratio of 1/e, under a mild condition on the optimal value. For non-identical distributions, we show that competitive ratio of 1/2 can be guaranteed against relaxed benchmark. More- over, with limited window access to past rewards, the tight ratio of 1/2 against the optimal benchmark is achieved.
(LCB) threshold- strategy
INTRODUCTION
The prophet inequality is a fundamental problem in online decision maaiing and optimal stopping (Hill Kertz] [1992.. preisiin-maker (or gambler) sequentially observes a stream of random vari- ables (or rewards) revealed one by one and must decide at each stage whether to accept the current value and stop, or continue the next stage. The benchmark the prophet, an omniscient agent who knows all realizations in advance. The objective of the gambler is to design an online stopping rule whose expected payoff is competitive with that the prophet, aiming to maximize the compet- itive ratio. This framework has been extensively studied, owing to its rich mathematical structure and broad applications such as posted-price mechanisms (Lucier 2017), online ad allocation (Alaei et al. 2012), and hiring processes in labor markets (Arsenis & Kleinberg/ (022).
Classical work has established sharp guarantees when the underlying distributions are known. In particular, (Samuel-Cahn (1984) showed that single-threshold strategy achieves the optimal com- petitive ratio 1/2 for independent but non-identical distributions. the i.i.d. case, Hill & Kertz 1982) established the ratio 1/e, which is the optimal under single threshold/quantile rule (Cor- rea et al. 2019b 2017).
Crucially, all of these guarantees assume full knowledge of the underlying reward distributions-an assumption that is rarely met in practice. This has motivated a recent line of work on prophet inequal-
ities with unknown distributions (Correa et al. 2019a 2020 Goldenshluger Zeevi 2022 Immor- lica et al., 2023). A striking negative result of Correa et al. (2019a) is that, in this setting, there is no meaningful online learning of the distribution: the best achievable competitive ratio 1/e Rs 0.368, attained by the classical secretary algorithm. Achieving larger ratio of - 1/e s 0.632 for i.i.d. setting requires ((n) additional offline samples (Correa et al. 2019a). Similarly, in the non-i.idd case with unknown distributions, obtaining 1/2 competitive ratio also necessitates O(n) offline samples (Rubinstein et al.] 2019). More broadly, the literature indicates that nontrivial learning is impossible without either (n)) offline data access to multiple independent repetitions of the deci- sion problem, as in regret- siirett-iniizzaionn formulations rather than single-sequence competitive-ratie guarantees (Gatmiry al. 2024 Liu al. 2025). These requirements substantially constrain appli-

---

Published as a conference paper at ICLR 2026
cability in real-world settings, where large offline datasets and repeated independent sequences often unavailable.
In this work, we study the prophet incquality in novel and practical setting, in which reward distributions are unknown without available offline reward samples, and furthermore, at each stage only noisy realization of the random variable is observed. Instead, the decision-makes has access observable feature vectors drawn from distributions, and the rewards follow a linear model with an unknown latent parameter. This structural information enables estimation of the reward distribution and fundamentally distinguishes our setting from the classical unknown-distributin model (Correa al., 2019a] Rubinstein al., 2019). This feature-bass formulation is motivated by applications such as online advertising, hiring, and recommendation systems, where contextual information (e.g., ad profiles, candidate attributes, or item descriptions) and noisy feedback are observable, while the underlying reward distributions remain unknown.
Exploration under stopping. In our setting, exploration tied to the stopping decision: once the decision-make maker chooses stop and accept, the process ends and no further information be gath- ered. As a result, continuing to explore serves two intertwined purpsees. First, it provides additional noisy, feature-dependent observations that help learn the unknown reward model (and thereby duce statistical uncertainty). Second, it keeps the option open to encounter new opportuniries, i.e., potentially higher future rewards. Since stopping irrevocably terminates both learning and opportu- nity, the decision-maker faces a delicate tradeoff between gathering more information and waiting for better candidates versus committing early exploit seemingly promising one under uncer- tainty.
We study tarming-basedd stopping policies that couple estimation and stopping under noisy observa- tions and feature feedback, and provides performance guarantees for our proposed policy. The main contributions are as follows:
Summary of Contributions.
Noisy linear prophet model with online learning. Motivated by practical scenarios, we introduce a prophet-inequalle setting in which the gambler observes only noisy rewards together with contextual features, while the latent rewards follow an unknown linear model. This structure enables online-learning approach prophet inequalities.
i..dd guarantees. In the i.i.d. case, we propose learning- based stopping policies based on lower-confidence-boume (LCB) thresholding and prove that they achieve the sharp compet- itive ratio 1/e against the optimal prophet benchmark under mild condition on the optimal value.
Non-identical guarantees. For non-identical distributions, we analyze an algorithm that attains a 1/2 competitive ratio against a relaxed benchmark. Moreover, with limited win- dow access to past rewards, our method achieves the optimal competitive ratio 1/2 against the standard prophet benchmark.
2 RELATED WORK
The study of prophet inequalities originates from Krengel & Sucheston (1977 1978). A key milestone was established by (Samuel-
Prophet Inequalities under Known Reward Distributions.
Cahn 1984), who showed that Lingle-threshole strategy achieves the optimal competitive ratio of 1/2 the case of independent but non -ddennantiaal distributions. In the order-selection variant, where the gambler can choose the order of arrivals, Chawla et al. (2010) achieved ratio of -- 1/e. For Ye, which is optimal under single (time-invariant) threshold/quntiile policies (Correa et al. 2019b 2017). Subsequent work showed that this bound can be surpassed by allowing adaptive strategics (Abolhassani et al. 2017 Correa
the i...d. case, Hill Kertz (1982 established ratio of
al. 2017).
Extending beyond exact observations, Assaf et al. (1998) demonstrated that analogous guarantees remain valid under noisy observations. though only with respect to Bayesian version of the prophet benchmark, which is weaker than the classical one. Indeed, under noisy observations, any non- trivial guarantee with respect the classical benchmark becomes impossible without additional
2

---

Published as a conference paper at ICLR 2026
structural assumptions, will show later. Finally, all of these results assume full knowledge of the underlying reward distributions- an assumption rarely satisfied in practical applications.
Prophet Inequalities under Unknown Reward Distributions. To address the limitation of knowing distributions, recent work has studied prophet inequalities under unknown reward distri- butions (Correa al. et al. 2024,1 Li et al. 2022). For the i.i.d. setting, /orreaa et al. (2019a) showed that competitive can achieved by the classical optimal algorithm for the secretary problem
2019a 2020: Goldenshluger & Zeevi 2022; Immorlica al.) 2023 Gatmiry
ratio I/E(= 0.368)
as the horizon grows. To obtain the higher ratio of - 1/e(=> 0.632), however, (n) additional
offline reward samples are required. Building on this, Goldenshluger & Zeevi (2022) showed that
an asymptotic ratio approaching 1 is attainable, but only for fixed distributions whose maxima lie in the Gumbel or reverse- reverse-Weibull Weibull domains of attraction as the horizon grows.
The case of unknown non-identical distributions has been examined in Kaplan et al.
2020); Rubin-
stein et al. 22019; Gatmiry et al. (2024); Liu et al. (2025). However, achieving a
2 competitive
ratio requires (n) offline samples. Although Gatmiry et al. (2024) and Liu et al. (2025) avoid of- fline samples, their setting involves repeated sequences of rounds rather than a single sequence. This repetition allows information to be aggregated across rounds, making the learning problem tractable under bandit feedback. In contrast, our setting involves only a single sequence, and is therefore fun- damentally different. Prophet incqualities under unknown and non-independent distributions were also studied in Immorlica et al. (2023), achieving a ratio of 1/ 1/(er) for r-sparse correlated struc- tures, but their model still assumes distributional knowledge of the independent components of the rewards.
In contrast, we study novel and practical setting that targets the optimal prophet under noisy reward observations and unknown reward distributions without available offline reward samples. Instead, we exploit observable feature vectors and their distribution, setting motivated by real-world appli- cations where feature information is available but the reward distribution is unknown.
3 PROBLEM STATEMENT
We consider n non-negative random variables (or rewards) XI...., X,, where each X; is indepen- dently drawn from an unknown distribution D;. In particular, we assume that
X; = ie [n].
where E Ed is a feature vector drawn independently from distribution Da,s to which the learner has sampling access, and E IR is an unknown latent parameter. Since 0 is unknown, the induced distributions D. of the X, are also unknown to the gambler.
At each stage i, the gambler does not observe X, directly. Instead, it observes a noisy measurement
y/ X; M/:
where the noise n, is i.i.d drawn from o-sub- Gaussian distribution for a >> 0. The noisy observa- tions yı, ... are revealed sequentially.
After observing (vi, n.) at stage i, the gambler must make an irrevocable decision to either accept the current index and stop, or continue the next stage. We denote by 7 E [n+ 1] the stopping time at which an index is accepted, with 7 + 1 corresponding to the event that the gambler rejects all observations, in which case the realized payoff is set to X = 0.
The gambler's expected payoff is E[X+]. As a benchmark, we consider the prophet-an omniscient decision maker who knows all values .I...., Xx, in advance-whin achieves E [max{e(n] X,] The goal of the stopping policy is to maximize the asymptotic competitive ratio against the prophet, given by
E[X]]
lim inf
100000
E [max X1]
Notation. For a square matrix M, Amin(M) denotes its minimum eigenvalue.
We consider regularization conditions follows.
3

---

Published as a conference paper at ICLR 2026
Assumption 3.1. There exists S such that ||01|2 S S.
Assumption 3.2. There exists L such that, for all i E [nx] and x Da, 1 L
Our regularization assumptions are standard in the online linear learning literature (Abbasi- Yadkori et al. 2011 Ruan et al. 2021: Liu al. 2025).
4 THE I.I.D SETTING
Here, we focus on the case where all reward distributions are identical, i.e., D; D for every E [n]. This holds, for instance, when the feature distributions are identical across stages, i.e., Da, = Dr for E [n]. Under this setting, we propose algorithms and analyze their competitive ratios.
4.1 EXPLORE- THEN-- DECCDE WITH LCB THRESHOLDING
We first propose algorithm (Algorithm(] I) based Explore-then then- with lower-confidence- bound (LCB) thresholding. To address the unknown distribution DD the algorithm begins with a forced exploration phase of length f, provided rithm enters the decision phase, where it computes an LCB for the reward at each stage and applies an (Csebased thresholding rule to decide whether stop or continue. This thresholding mechanism explicitly accounts for estimation uncertainty. The full procedure is detailed below.
input. After the exploration phase, the algo-
4.1.1 STRATEGY
Exploration. With setting Ln o(n), during the first ln stages, collect pairs of noisy rewards y/ and features 2, at each stage t. Using these observations, we estimate the unknown parameter as 0 - V- V---- VeTe, where V = E
n. + BI2 for constant /3 0.
After this exploration phase. the algorithm enters the decision phase, where it determines at each stage whether to stop or continue. The details regarding LCB Thresholding are given below.
Lower Confidence Bound (LCB). We define the lower confidence bound for X; as
XPCBB = x E(x)),
where E(x;)) Vx V V-r,, log(( L/d3) + /83).
Decision with LCB Threshold.
Using the CDF of PAWD, (Z < ald, V) where ZLCB
2T - [(z), we threshold a
PP PINDA (ZLCB < a00 V)
The algorithm stops at stage i > En if X.C.BBBBBBBB 2 in which case we set 7 i. By definition, if no stopping occurs throughout the horizon, we set = n + Although Algorithm i presented assuming oracle access to D2 for clarity, the quantile defining the threshold can be approximated arbitrarily well via Monte Carlo sampling from D
4.1.2 THEORETICAL ANALYSTS
In this setting, a fundamental limitation emerges due to noisy observations. In fact, it is possible construct instances where the observation noise drives the competitive ratio trivial limit, as formalized below (see Appendix A. for the proof).
Proposition 4.1. There exists a bounded i.i.d. distribution for (X together with an observation noise model such that, for any stopping policy based on the observations,
E[X+]
lim n0 E Em X,
4

---

Published as a conference paper at ICLR 2026
Algorithm Exxplore-Then-Decite with LCB Thresholding (ETD-LCBT)
Input: Exploration length bi regularization parameter Output: Stopping time for 1....,7. do if S L, then
Observe (yi, (i))
if i in then
Eim Te + Bly; 0+ V-1 V-12 Ft
Compute a from
(2) (or (5) for non-i.i.d)
else
Observe (yi, Compute X|CB from 1
X. 2 a then Stop and set +-
10
The trivial outcome in Proposition 4. explains eexplanns why Assaf et al. (998) studied a Bayesian version of the prophet inequality rather than the classical one (LD) [ X.I) under the noisy observation. As Proposition 4.1 shows, even with full knowledge of the reward distribution, no algorithm can avoid this collapse trivial competitive ratio. To overcome this fundamental challenge both in target- ing the classical prophet under noisy observation and in the presence of an unknown latent parameter the reward distribution we later impose a mild non-degeneracy condition on reward scaling.
For notational convenience, let À Amin (Eg-D, [a:x: the minimum eigenvalue of the covariance matrix of the feature distribution. Without loss of generality, we restrict attention to the case >> 0, ensuring non-degencracy of the feature covariance. Under this notation,
state our main
guarantee on the competitive ratio (see Appendix
A.2 for the proof).
Theorem 4.2. The stopping policy of Algorithm with e = o(n). la = w( Llogd). and a constant
O, achieves an asymptotic competitive ratio
[[[
liminf n 200
2
lim sup En:
E [max,c
X²]
n-+00 e
where
Lioad + log(Ln)
O
E maxxie(n X.]
X
This result highlights the critical role of the optimal value OPT := [a X,] in determining the competitive ratio under noisy learning. As shown in Proposition 4.1 without further structural assumptions, the competitive ratio can collapse to zero. To circumvent this issue, we impose a non-degeneracy condition on reward scaling, specifically the growth of OPT, which ensures learnailityy under noise and allows us to recover the sharp bound established in Theorem
Corollary 4.3. We set En d(o3 (n) log(Ln) some function (n) (e.g.. f(n) O(lgg" n) then the stopping
forp > O, or O(n²) for < < 1) satisfying e, = o(n). IFPPT
policy T of Algorithm Canorihhmmahhiie achieves an asymptotic competitive ratio of
lim inf n00
2
E [mma
X.]
The non-degeneracy condition of OPT w(1 w1////////// (n)) in Corollary 4.3 is mild in practice. For example, by using (n) 2/3 for setting l., the requirement is satisfied in most applications since OPT typically remains bounded away from zero. In particular, it suffices that OPT 2 C' for some constant C and all sufficiently large
Our competitive ratio of 1 1/e matches that of Hill & Kertz (982) in the known i.idd setting and that of Correa et al. (2019a) in the unknown i.i.d. setting but with (n)) additional offline reward
5

---

Published as a conference paper at ICLR 2026
samples. Without such samples, only 1/ce ratio can be guaranteed (Correa et al. 2019a), which is strictly weaker than our result. Moreover, because rewards in our setting are observed only through noisy realizations, these prior guarantees no longer apply. Also note that 1/c is the best possible competitive ratio attainable by single quantile-threshold policies (Correa et al. 2019b 2017). and algorithm provides close approximation to this class of policies.
Importantly, while Correa et al. 2019a) show that 1/c is optimal for unknown distributions without sufficiently many offline reward samples of [2()), we demonstrate that by exploiting feature infor- mation under structural assumptions, the sharp bound of 1 1/ce can in fact be achieved. Moreover, our analysis sis accommodates distributions whose support grows with the horizon n (e.g.. when setting fn) = log n in Corollary 4.3), so that both the support and the variance of D may diverge as - oo. This highlights that our framework not restricted to the fixed distributional domains considered in Goldenshluger & Zeevi] (2022), but instead applies more broadly to settings where distributions may evolve with the horizon.
vn
4.2 E- E-GREEDY WITH LCB THRESHOLDING
While the Explore-then-Deciie method achieves a sharp competitive ratio, its deterministic separa- tion between exploration and decision phases-and the fact that exploration is confined to the early its practicality in applications where exploration spread across time is preferable, such as online advertising or sequential recommendation systems. To address this, we propose an e- G-Greeyy approach (Algorithm 2)
that selects decision stages uniformly at random over the time horizon. The details of the strategy are described follows.
Randomized Exploration. At each stage [n]. we draw a Bernoulli random variable 4, BernoullicE). where E = Vnn/n n with setting ln = o(n).
If b; = 1, we perform exploration by observing the noisy reward yi and feature 2;, and update, 0, = V Eiez, yr where Vú = E,EI, N,ي; + 3Ta for constant >>> 0.
If b; = 0, we enter the decision phase and determine whether to stop based on dynamic threshold.
Unlike the Explore-then-Dee Decide method, here the exploration rounds are distributed over the entire horizon. Consequently, Ó, and V; are updated continuously, which in turn affects both the LCB and the threshold dynamically, described below.
Lower Confidence Bound.
We redefine the LCB for X, = 2z f as
X = xz. 0, (xxx)
where (x(x)) V V ( (dVdlog(n + n m|IILL/d3) + VSBB.
Decision with LCB Threshold. Using a CDF of P.~D. (Z..CB S a 6,, V., I,) where 2. 2T 0. Ei),, for each i [n], set the dynamic threshold a; such that
PAND, (z). a; 0 V..I.) = =1- 72
(4)
The algorithm stops at stage i if XLCB 2 a, in which case we set T = i. Unlike Explore-then- Decide, this procedure employs dynamic threshold. Recall X = Amiu (EawD, [xx [I. Then, the algorithm satisfies the following theorem (see Appendix A.3 for the proof).
Ven/n, ln = =(n), en M(max I. log d logg l)gn)), and constant B > 0, achieves an asymptotic competitive ratio of
Theorem 4.4. The stopping policy of Algorithm
2 with
E[X,]
1
lim inf
1
limsup En
200 E|maxieja] Xi]
R-

---

Published as a conference paper at ICLR 2026
Algorithm 2 e-Greedy with LCB Thresholding (e (e-Greedy-LC51)
Input: Bernoulli parameter E; regularization parameter
Output: Stopping time r for l....... do
Sample b; Bernoulli(E)
if b; = then + [
Observe (2i, 91)
Vi + EiET,
Tttt 3lai 0. + V Vr
else
I I-1, 0: - 0 Vi V
Observe (Fi, y/)
Compute XLCB from (3 and a; using
10
if X. 2 a; then
II
12
Stop with <-
where
L(o2d + 5) log Ln) Xln
En O
B B[mmaxeen]] X.}
Furthermore, by setting ln M( f(n)) log(Ln) for some function f(n) (e.g. f(n) = Ologg" n) for > O, or ((ni) for 0 < 1) satisfying en o(n), if OPT w(1/ w(I/V[(n). then
B
lim 2-000
2
max X,
Notably, the e-Greedy approach achieves the same competitive ratio established for the Explore- then-Decide method in Corollary 4.3 while ensuring uniformly random decision stages.
5 NON-IDENTICAL DISTRIBUTIONS
In this section, we consider the setting where the distributions D; are not identical across E [n]. In what follows, we propose algorithms and analyze their competitive ratios.
5.1 EXPLORE--HEN THENDDEDDEE WITH LCB THRESHOLDING
We build on the Explore-then-Deciin framework in Algorithm 1 adapting the thresholding pol- icy accordingly. In the initial exploration phase of length tn. collect data and estimate i = V-I yr where V = - xæaa + 31 for a constant 8 > 0. In the subsequent decision phase, we apply LCB-based thresholding for non-identical distributions, as described below.
Decision with LCB Threshold. Let {2, 1 be independent random vectors with 2, Dr.s- We define the threshold:
a = E
z 2 +l
max
(5)
Recall the lower confidence bound for X; in the Explore-then-Decide framework: X.LBB = x E(x;), where (xx) = V- V (og( + L/dB) + /SB). Then, the algorithm stops at stage if x LCB > a.
For notational convenience, let X' = min Amin EE [xx T). Then, the algorithm satisfies with the following theorem (see Appendix A.5 for the proof).
7

---

Published as a conference paper at ICLR 2026
Theorem 5.1. Consider the stopping policy T of Algorithm I with & o(n), a constant > O. where the threshold value is chosen according to Then
in w( (logd) and
[[
lim inf n n-000
2
lim sup En En.
E
ma +1, +1..... Xi
2
n0000
where
M(odd + +))55))oool log(In)
En == O
E maxic (fa (I. xi]
X Nln
Ler OPT E (eattg Xi] and set lu 1(aa++5) x
f(1) log( Ln) for some function O(n") for 0 qq 1) satisfying en o(n).
f(n) (e.g. f(n) = O(log" n) for p
ÓPT = wLL/ f(n)), then
E[X,]
lim inf 10000 E
+1.) X; 2
In the theorem, we target the relaxed prophet of E B|max Xi] due to the inherent difficulty of the non-i.i.d. setting against the original prophet, as shown Proposition 5.2 (see Appendix A.4 for the proof).
Proposition 5.2. There exist non-identical distributions (Dz,) for the feature vectors vs 's, and a parameter vector Rd, such that when observing noise-free rewards X; = x. 0 for E [n]. the following holds: for any stopping rule
EX
11 S min ( 7
E maxie[m] X.)
shows that, even in the noise-free case (a 0), the initial stages must be sacrificed to learn 0. For the standard prophet of F[maxx,e[]] X,). the competitive ratio approaches zero with large enough (e.g. d log(m)). This motivates our focus on the relaxed prophet benchmark [fxx.e(f++......)) X.), under which meaningful guarantees are attainable.
Proposition 5.2
The optimal competitive ratio for non-identical distributions is known to be 1/2 (Samucl-Cahn 1984). In our setting with unknown distributions, Theorem5.I]shows that attaining this ratio requires relaxing the prophet benchmark by excluding the initial exploration phase. In the next subsection, we present the case with a logarithmic number of offline samples under which the optimal prophet benchmark can be attained in our setting.
5.2 EXPLORE- T TTHEE-DECCII WITH WINDOW ACCESS
In the standard non-identical distribution setting, items are revealed sequentially, and the gambler decide immediately whether accept or reject the current observation. As discussed in Mar- shall et al. (2020); Benomar et al. (2024), this assumption, however, can be overly pessimistic; in many practical scenarios, early opportunities are not irrevocably lost but may remain available for short period of time. For instance, in a hiring process, one may be able to interview several candi- dates sequentially before making final choice among them.
Window Access. Motivated by this observation, we consider mild relaxation of the standard setting by using window access for the previous time steps, same as Marshall et al.] (2020). More specifically, given window size wn. at time i the decision-maker has access to the indices in the window [i - w,, + i, and may choose any index in this window at which to stop; if no such index is selected. the process continues to time i + 1. Interestingly, even for any w,, setting remains as hard as the standard model (corresponding to window size wn, = 1), in the sense that the optimal competitive ratio does not improve, shown in the following (see Appendix A.6 for the proof).
1. the non-ii.d.
Proposition 5.3. In the non-i.i.d. setting with window access of size Wn. 1. any algoritim, there always exist non-ioeninn identical distributions such that the competitive ratio is bounded above by
[[X+]
m X.} 11/2.
8

---

Published as a conference paper at ICLR 2026
These observations raise the following question: Can the optimal competitive ratio under window access also achieved in the setting of unknown non con-idetiical distributions and noisy reward ob- servations? so, what window size W,, is required. and how frequentiy is window access required?
To handle this setting, we propose an algorithm (Algorithm ] in Appendix A.7) adopting the aoplore-then-Deciiee method. After the exploration phase, at time la 1, the decision-make is granted window access with size Wn = in + and may stop at any index in [e, + 1]; if no such index is selected, the process continues to time L,
Notably, our algorithm requires only single window access at time L, 1, with window size &, + 1. Due to space constraints, defer the detailed description of the algorithm Appendix A.7 In what follows, we provide a theorem for the competitive ratio of the method with window access (see Appendix A.8 for the proof).
Theorem 5.4. the non-i.idd setting with unknown distributions and window access of size W.
n. the stopping policy T of Algorithm with l, = o(n), En = w( Loog d) and a constant B > achieves the following asymptotic competitive ratio:
x
E[X,]
lim inf n
2
-lim Sumpppe
E maXie(n) X.
2 n
where
LioRd + (S)dd)))ogg(n))) + +VLS ( ( )) )
d exen1sL)
En =
E [maxiee(n) Xi)
Mln
Furthermore, by setting tu L(od++)) log(Ln) for some function f(n) (e.g. f(n) Ologg n) for p > O, or O(n9) for O w( (mmax[1/ 1///f/(() LS)n)), then
1) satisfying in = o(n). if OPT
lim inf 12-000
maxxee[]]
X3]
Notably, Algorithm Ba the optimal ratio, matching the upper bound in Proposition 5.3
Remark 5.5. The 1/2 guarantee can also be obtained by running (CB-Thresholding with e,, offline samples, without window access. Exploiting the linear structure allows method achieve the optimal 1/2 ratio using only &, samples forr example, & Ollog*+1 n) when (n) = O(ogg n) for p > O. Further details are provided in Appendix A.9
EXPERIMENTS
We evaluate algorithms synthetic data with Gaussian reward noise of variance o², We set d 2, E,, = 2/3 and 3 = 1. As no prior method directly fits our setting, we use the Gusein Zade rule (Gusein-Zaai
1966) as baseline: it skips the first n/ samples and then stops at the first record exceeding the maximum of this prefix. This rule guarantees worst-case competitive ratio of I/e for unknown i.i.d. distributions (Correa et al. 2019a) and can be asymptotically optimal for certain distributions (Goldenshluger & Zeevi 2022) results averaged over independent Monte Carlo runs
L..d. distribution. In the i.i.d. setting with n. 100,000, we draw 0 and x; coordinate-wise uni- formly and then normalize. Figure T shows that our algorithms, ETD-LCBT (iid) (Algorithm) [T] and e-Greedy-LCC LCBT (Algorithm 2). achieve competitive ratios exceeding 1- 1/e, consistent with Corollary 4 and Theorem 4.4, and outperform Gusein- ineeiin-ee -adee. Moreover, the performance gap widens as increases, suggesting that our approaches are robust to observation noise.
Coode: http::/:wsccc....../a//.////ee/e htt.://a.a..........oooooooeaarr

---

Published as a conference paper at ICLR 2026
Computt kato digorihmm 200000
Competticc Aut diperttti you L030000
Computtioe kato Alpetthna (8-163868)
Klbscame Gued Zate 2-34
Cocomia
Con Prlzes
0.1
(b) 0.5
0.8
Figure I: Competitive ratio under the ii.d. setting with noise standard deviation a.
Compettion Maonttmm 20000
Concatitive falls Jn
Compott ta Rats dfAlgattom 20000
Steucsitrevaa desen Zank
Zore
Canth-2ats
0T0-UCE SAA
Gamii-2ads
0.1
(b)
0.5
0.8
Figure 2: Competitive ratio under non-identical distributions with noise standard deviation a.
Non-i..d. distributions. For n = 30,000, we draw as above, while each x; comes from distinct distribution by first sampling coordinate wise range and then drawing z; uniformly within that range. Figure [ shows that the window-access method ETD-LCBT-W- WA (Algorithm (3] achieves a competitive ratio above 1/2, matching Theorem 5.4 Even LTD-LCBT (non-iid) (Algorithm []. analyzed only against a relaxed benchmark (Theorem 5.1 empirically exceeds 1/2 against the standard prophet. As expected, STD-LCBT--T improves upon ETD-LCBT (non- iid) and both outperform Gusein- Zade, with gap that widens as o² increases.
CONCLUSION
We introduced new framework for prophet inequalities under noisy observations and unknown reward distributions, motivated by real-world applications where noisy reward and contextual formation are observable but reward distributions are not. By combining learning with LCB-based stopping rules, we achieved the sharp competitive ratio of 1 - 1/e in the i.id. setting. For non- identical distributions, we showed that the optimal bound of 1/2 can be attained under window access or under relaxed prophet benchmark. Our empirical results demonstrate the efficiency of algorithms.
REPRODUCIBILITY STATEMENT
All theoretical claims stated under explicit assumptions and supported by complete proofs in the appendix. Algorithmic details, including full pseudocode, are provided in the main paper and appendix. For the experimental results, describe the data- Rata-generation process in the main paper and release the complete source code needed to reproduce all figures and numerical results at the provided URL.
ACKNOWLEDGEMENTS
The authors acknowledge the support of ANR through the PEPR IA FOUNDRY project (ANR-23- PEIA-0003) and the Doom project (-NR-23-CE23-0002), as well as the ERC through the Ocean project
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghi Hajiaghayi. Robert Kleinberg, and Brendan Lucier. Beating 1-1/e for ordered prophets. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 61-71, 2017.
Saeed Alaei, Mohammad Taghi Hajiaghayi, and Vahid Liaghat. Online prophet-inequaliy matching with applications to ad allocation. In Proceedings of the 13th ACM Conference Electronic Commerce, pp. 18-35, 2012.
Makis Arsenis and Robert Kleinberg. Individual fairness prophet inequalities. arXiv preprint arXiv:2205.10300 2022.
David Assaf, Larry Goldstein, and Ester Samuel-Cahn. A statistical version of prophet inequalities. The Annals of Statistics, 26(3): 190-1197, 1998.
Ziyad Benomar, Dorian Baudry, and Vianney Perchet. Lookback prophet incqualities. Advances in Neural Information Processing Systems, 37:42123-421611 2024.
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. Multi-paramete mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM sym- posium Theory of computing, pp. 311-320, 2010.
José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for random stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 169-186, 2017.
José Correa, Paul Dütting, Felix Fischer, and Kevin Schewior. Prophet inequalities for iid random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Eco- nomics and Computation, pp. 3-17, 2019a.
Jose Correa, Patricio Foncea, Ruben Hocksma, Tim Oosterwijk, and Tjark Vredeveld. Recent de- velopments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019b.
José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, and Bruno Ziliotto. Unknown iid prophets: Better bounds, streaming algorithms, and a new impossibility. arXiv preprint arXiv:2007.061 10, 2020.
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora's box. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 462-500. SIAM, 2024.
Alexander Goldenshluger and Assaf Zeevi. Optimal stopping of a random sequence with unknown distribution. Mathematics of Operations Research, 47(1):29 49, 2022.
SM Gusein-Zade. The problem of choice and the optimal stopping rule for a sequence of indepen- dent trials. Theory of Probability & Its Applications, 11(3):472-44 476, 1966.
Theodore Hill and Robert P Kertz. Comparisons of stop rule and supremum expectations of iid random variables. The Annals of Probability, pp. 336-345, 1982.
Theodore P Hill and Robert P Kertz. A survey of prophet inequalities in optimal stopping theory. Contemporury Mathematics, 125(1):191, 1992.
Nicole Immorlica, Sahil Singla, and Bo Waggoner. Prophet inequalities with linear correlations and augmentations. ACM Transactions on Economics and Computation, 11(3-4):1-29, 2023.
Haim Kaplan, David Naori, and Danny Raz. Competitive analysis with sample and the secretary problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algo- rithms, pp. 2082-2095 SIAM, 2020.
Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977.
11

---

Published as a conference paper at ICLR 2026
Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Prob- ability on Banach spaces, 4(197-266):12,, 1978.
Bo Li, Xiaowei Wu, and Yutong Wu. Prophet inequality on iid distributions: beating 1-1/e with single query. arXiv preprint M2Kv::2200.05599 2022.
Junyan Liu, Ziyun Chen, Kun Wang. Haipeng Luo, and Lillian J Ratliff, Improved regret and contex- tual linear extension for pandora's 's box and prophet inequality. arXiv preprint arXiv:2505./882. 2025.
Brendan Lucier. An economic view of prophet incqualities. ACM SIGecom Exchanges, 16(1):24-47, 2017.
William Marshall, Nolan Miranda, and Albert Zuo. Windowed prophet inequalities. arXiv preprini arXiv:2011.1492,, 2020.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distri- butional optimal design. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-87, 2021.
Aviad Rubinstein, Jack Z Wang, and S Matthew Weinberg. Optimal single-choice prophet inequali- ties from samples. arXiv preprint 1rXiv:191..07945, 2019. 2019.
Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pp. 1213-1216, 1984.
Joel Tropp al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230) 2015.
12

---

Published as a conference paper at ICLR 2026
A APPENDIX
A.I PROOF OF PROPOSITION 4.1
We give construction under additive Gaussian noise, which
Let XI...., Xn be i..d. Bernoulli with success probability = c/nn for some fixed (0, oc). Let (n)) be i..d. (/ o²) for constant a > independent of (Xx))=1+ and suppose the gambler observes
y = X; + 7/-
,.
Let be any (possibly randomized) index valued in {l...., n) that is measurable with respect to Y = (Y,...,,YY,, Yn). Then, conditioning Y and using - Pr(r i Y) 1 and Xx+1 := 0,
B[X, |Y]
Σ Pr(r=i
YJ
max E[X; Y]- Isis
Moreover, since (Xi, 1R:) are independent across i, we have IE[X; YJ E|X; Y = Pr(X;
Y:). Let
( := = - y).
By Bayes' rule for the Gaussian likelihoods,
TVV (1 - Pn Pn)) + Pa Pa (y (y- where you (1)
Pn
11/222))
2
Hence, using (1 pn) (1) lower bound on the denominator,
(ty)= <
Pn Py
Pn Pr
exp
2y
- Pp Pa
20
Now define the event
En = {
max Y, I tn
:= 1 1 1 Blogn.
Ussisn
Since X; E 10,1). > tu implies 17s > tu - 1, and Gaussian tails give
Pr(E.) < Pr(m > tn - 1) nexp (1n-- 11)2 -)))
ne
4 4logn
0.
202
n-000
On En, we have max; π (Y:)= S π (ln.). so
2c exp v n
2lm -1
E[X+]
max 7 (Vi) S (t,)) + Pr(E,) 13i5n
+ o(1)
0,
20
where we used P. = c/n n and 1/(1 - p..)= < 2 for large n.
On the other hand, the oracle that sees the true X's obtains max; X,.
(1- 9
max X; = =1 -pp-pp)" = =1 Isisn
1 -->
n1 20000
Therefore,
E E[X,]
0.
[max; X.]
and the conclusion holds for any algorithm.
13

---

Published as a conference paper at ICLR 2026
A.2 PROOF OF THEOREM 4.2
We first provide lemma for estimation error.
Lemma A.1 (Theorem Abbasi-Yadkori et (011)). ), For 6 O, we have
P 110- 01lv Ollv
/Sg + ov doog
L/L/ 2 1 -
The above lemma implies that
x T (0 8) - v VV (oV dlo((n =l V vx E Rd
21-1/m (6)
We define an event ε₁ = { (0- S Vx V-lx(o nln vo E Bd), which holds with P(E1) 2 1 - +.
We define g v L| 1 dlog(n nl L/dL/dB) VBB.. Recall
{(x:) = v V-lx; d'log(n + nl, m/d3//3)) + VS
Then we have {(x,) g. Under 1,, for any i Ln have
X; 2g s - 0 S xz {(x,) X.CB S X,
We define a' s.t. PX-D(X S aa)) = 1 n Then we have the following lemma regarding the bounds for the threshold value. We denote He. 10, Lemma A.2. Under y for any Hi,, we have
a" - 2g S a²
Proof. For Dr, define Z 2 and 2 = TT. = Then, under E1, for any given He, we have
Z 2g < 2 g < 2 {(2) < with {(=) g. Since 2 {(z) Z and P(Z <(z) 2
He.)) P(Z 2 a* (Hs.) = 1/n, we can easily obtain
5 a'.
Likewise, for a' s.t. (P - 2g 2 a' He.)) = 4, from 2g S 2 - [(2) and IP(Z - 2g 2 0'
He P(2 {(=) > H 1/n, have a' S a. Therefore, with a' 2g ax from
P(2 2 a" Ho.,) P(Z 2g 2 a' Ho.)) 1/n, we have
a" 2g a,
which concludes the proof.
sid. De satisfying Assumption 3.2 Recall
Lemma A.3. For 1 2 1, let 21....,
Amin(E-- [zz 1) 0. Then
A1
P
2z
Ta
2 dexp
8L
Proof. Let Mmii Amii [ == 2T By the matrix Chernoff bound (Theorem 5.1.1 in Tropp al. 2015)) for sums of independent PSD matrices with Assumption 3.2 for any [0, 1).
EE
{
-
Mmin/ L
(- 82 Mmin
Pr Amin
Σ
202
< (1 8) S d
(1- 8) 1-8
I d dexp
(-2 2
Choosing yields
Pr Amin
Σ 2o T
Umin 2
< d dexp
(oopp-Hump
_mmin dexp
81.
(88
a=1
14

---

Published as a conference paper at ICLR 2026
Equivalently, with probability at least 1 - dexp(->1((8L),
Mmin
Ia = 1X
282 =
Id.
2
2
which completes the proof.
Let &2
1Eim
in sml F.ag = Me Ta), which holds with probability at least / 1 2l2 S 2 xe_
from
2
Lemma A.3
Then under E2, we have
||V s IE ",0,
Then, have
{(x:) S V- dloo nl,,//33) S 8VB)(=
2 v Xen +2/
Here define h / L x², (d n² L/d3) SVD) and & & O &2. For analyzing Xy, we first examine the probability that the stopping time equals i.
Lemma A.4. For i > en we have
P(r= = 1 Hee,) -(1
i-t,,
Proof. For i > ln we have
PPr = Hen)
PPX S a......
x < a xa
LCB
X.C.B > He,)
IP S a , XLCB a He P(X L.B
Hi,)
-P(XLCB Sa.... a....., ....B.,I.CBBBBB. <a Hi. _
1
n
where the second equality is obtained from the fact that, given and V, X.CBB is independent to XLCB X.C.,, :n..:...; XLCB Similarly, for the term above, we have
P(X a, X. S He.))
He,)) 1 n
= P(X1,OB 6,+1 < 0 a,...,, X <a He, (P LLC Sa
XLCB < He.) 1 (1-1) 1 1
P(XLCB 4,+1 <
n1
1 f-n-1
1 11
which concludes the proof.
15

---

Published as a conference paper at ICLR 2026
From the exploration phase in the algorithm, we have P(T i E) 0 for all 1 s i 1 n. Therefore, we have
E X ((8) | He,lll
E
Σ
P(T = He, H(,) | T== i,Hlen)
=
1
E
P(r = i Me, ((Xx1 | T= =1, Henl
E
P(T = He, |
LCB ((8) T= i, Hem.
i +1
i-6n-1
1 1
E
E B[x (() 1 i, H,Heea
n
|=
E
1 n2
x (E(a)(E)
T = i, He,l + -() X 2 a, Heml)
t= 2 +1
i-tn-1
1
E
x (E())(E) He.. + B[(X! LCB - a)* 1(8) x 2 Heal)
n
1
i-6 -1
x (B(w((8) Ho,,I+ E[(X a)+ 1(8) He..
E
P(X 2 a Hen))
n
n
i +1
x (()a1(E) - (g) Hr,,1 + +nB (X: - 2g a²) 1()) Hon.. [km.))] 1)
E
1
1-
i= +1
(8)
where the second inequality is obtained from Lemma A.4. and the last inequality is obtained from Lemma A.2 and 77). Let i.i.d. Z DD for [n]. Then, with e,, = o(n), for the last term in (8)
we have
i-Ln
(g) [He..) + nB [xx 2g x²)+1(E) (He.. 1)..]]
E
[BI(a=
1
n
f=
n
i- -1
1
E Ela*1((2
He.. 28/h1(E) He.. + nE 2h a²) 1(8) [e..
n
n
+1
i-Pa-
1
x
E
Ela" 1(8) He..] - 28)(1(() He,,1 +E
Σ
(Z. 2h - -a*) 1(8) Hi.
+1
xE(m)
1-6-1 1
((E) | [He.] - 2B[h](E) He.. + E
max (Z. 2h - a²) 1(8) | He.
n
[d((m)
+1
1
x (a'((E) - -2hP(E) +E
max (Z, - 2h a²) a²) 1(8) SE[N
n
16

---

Published as a conference paper at ICLR 2026
Σ
22
1
apP(E)
2hI((E) +E
max Z, [eE(m)
P(E) (2h + a²) )P(E))
m
71
+1++1
Σ
7
Em -
1
x
max [5(nn
((()) -4h)
n1
n
k +1
(1
(ovā+v ))
i-6n
Llog(nL) Xln
1
x
E
max X, [E(
PP(E) -
inn+1
1 (1 1 ))n=
(1-
d
Llog(nL)
1/n
E
[eE[n]
max X,
eden/8LL
-
Xen
(ovd+ VS)
where the first inequality is obtained from g S Finally, from
8 and
have
E[X,]
E[x, He, 11
lim inf
lim inf +00000
E [ma Xi]
maxxe]|] Xi]
E E X, (8)
He,,]l
iim n-000
E [max(e(()) X₂)
lová++vs) ))
(1 1 2
(1-
log(Ln)
lim n-+00
0
1/n
exnnn/I /8L
E[maxieeni Xi)
den
(1- -
I(o2d + (5)log((n))
lim sup n-+00
E[maxiejal X.]
Nln
where the last inequality is obtained from limits lim (1 - 1/n)" = 1/e and limm-+o0 1/n)6n = (since en = o(n)) and L, = w( Logg
A.3 PROOF OF THEOREM
Lemma A.5 (Theorem 2 in Abbasi- Abbasi-Yadkori et al. (0111). We huve
Vi [n]. |0, Olvv. S 553 + o dlog 1+
) (1+ L/)B8)
2
The above lemma implies that
x (0, - 0) s 2/ VV (oVdlog (n + + nII + VSB) Yo E vie [n] 21 1- 1/n.
(10)
Let On
Vnt
We define an event
0) <
x VV, Ila dlog(n Ta L/dB3) + VSB), Yo E Rd Vi E [an + 1, n]].
From
10
we have P(εi)= 2 1. Then we define = LIVV_,
112 Illo / dogg( + L/d3) + VSB) so
that, for i ans (xx;)) I g (recall ((x,)) /2. 1 dlog(n + nII + VSB)). We
denote H. (0, I.].
Lemma A.6. Under Ex, for any > On and any given Hi have
a' 2g E 05 a"
17

---

Published as a conference paper at ICLR 2026
Proof. For 2 D. we define Z = 0 and Z; =, Then, under &1, for any given V; and 6, have 7-24 2g I 24 9 S 74 ((=) - Z with {x(=) S g-
Let a* be the oracle threshold satisfying P(Z a' (= P(Z a²)) = 1/n. From 2, (x)()=) s Z and P(Z: (2) 2 a; H4) P(Z ス a* H.)) (= 1/n), we can easily obtain
a a
Likewise, for a' s.t. PZZ 2g 2 a' H.) 1. from Z 2g S 2 S - and P(Z - 2g 2 o' H.) = P(2 - (=) 2 04
H:). we have a' S az. Therefore, with a' + 2g a² H.) = 1/n, we have
from P(Z 2g 2 a H4) P(Z a²
a' 2g aii ai.
which concludes the proof.
Lemma A.7 (Multiplicative Chernoff Bound). Let Zi,... ... Ze be Bernoulli random variables with
mean Then for 0 < S 1 we have
1 Σ
7.
110
2 81p
S (2exp(-8lp/3)
==1
From the above lemma, we define Eg- {|IIA| ivenn//
S / ni.. which
holds with probability at least 2exp( =6,] 2 expp nnt
12
From Lemma A.3 for any 2 1, suppose 21,..., 21 ~ Dr are i.d drawn from a distribution Dz
satisfying Assumption 3.2 Recall X = Amin (anin(Ewwe) (BIND, [22 O. We have that
Al 8L
P
28
Ia 21 - dexp (-8L
Then, we define Es = {ESeT, IsTg 2
Kanl Alay. which holds, under Es, with prob-
ability at least - (nn7(1o This implies P(E2 n Ea) = P(Ea E))(()) z
(1 (at//oos)
(1-2exp(
2 expl -fa) 2expl vvnl.
Then under &g n Eg, we have ||Va,'ll I ||EE,e,, 2,07) 12 S 2 NTon
I 4 1
Then for
i Ons have
6.(x;) S 11 1 / 9)
4
s V
L
(a (oVdlog(n + n /S3).
(11)
Me,
Here we define h =
/
4 Xt, (a /dlog( + n²L/d3) + VS3) and È = & N n
We define the set of decision stages until: i as J, : [i] so that J, UT, = [1] and Ji C Jz...., Tn. Then, analyze the stopping probability i in the following lemma.
Lemma A.8. For i E In with any given J. = (J,, b. we have
P(T=i|J,88 = (1
1
18

---

Published as a conference paper at ICLR 2026
Proof. For notation simplicity, we define Ji .., Ts for k E [[A]]]. Then, for i E Tn. we have
P(T i E(, -[[[(T = Hi, 81,8) 8,
-][((XX S a Vt M.NEEJ(... J(1611-1), >a H,, J.
E [P((xX]. Savle -. H, > His Je,8) T
E [F((x] S a E J, ((151-11) | (t.J(, J..
= =P((X Sa J. 1-11111 (1 -) !
7
E[P((X s E J. (11111)1 Hais T.. E
E [P([X]OB Vt E J. || 2/ | Ti, x P(X S Hz 11111 Ti, &
1
- = Savt J. (1111-211 H. Ji,E) g ( | (1_
71 n
=P((X Savle J. (11-111 (1,,8)
1 -1- 1 1
71 n
15.1-1 -(1-7) n2
1
n
From the decision strategy of the algorithm, we have PP(r il J2 = 0 for all i E I,, Therefore, for analyzing X,, we have
E E]
P(r = il [
Σ P( = il b 8)E T= 1,
E
Σ P(r=i| Jr, | | 7=
i
>
E
Σ
|
J,, 8)E E[X -- H4 , 3
Noml
(1-1) 1 13.1-1
2
E
E [E
T i, 1=
JEJoNaa Maa1
2
Σ
(1-2)
1
13-1-
E ELX
-== i, H4, H E (12)
JEJr. (oo.
For the last term above, for i E In (an)) have
19

---

Published as a conference paper at ICLR 2026
_[ T= i,,
E B|a
T T= i, H4. Jr, 8] + ( - XLCB 2 a, 8
M4. El - -
Mi,
= E las
P( 0: Hi Ti,
2 E ja" - 2g H., El + nB [X: 2g a² a²) Hip8
(13)
where the last term is obtained from Lemma A.6 (xa))) I g, and the definition of dz.
In what follows, consider the case of E [[max]e[m] X,] - (VaLlood + 5) log Lm)) cause otherwise, it holds trivially:
0, be-
Nen
E|X, [8 2 (1-22) Vnla - -(1-11
n- Vitta 3
L|max X₂] - ( (V 8) log(Ln)
1 n
rE(m)
Nen
Recall : V V n + VSB). Let iid. Zμ D for k E [nt]. Then, for the
last term above in 112 with (13.. under E, we have
10.1-1
Σ
1
1
E[aa 2g
Hi, El + nl
(X: -2g aa') 1/|+1111 8))
71
IEJ
Vanl
J.1-1
Σ
E ||a"
2g H4, El + nE (Z, - 2g a²)* Hzs El
π
iET [anl
5|-1
(Zx 2g a²)* ) 144, E
H4, El Faa" -29
max kE(r)
71
n
iEJ |/n
1
J.
1-
E
max Zh ME(M)
H4 E
4h
JEJn |oml
n
n
1
Vitan
|Jn1
Al
E
max Ze kE(M)
His E
4h
71
Vnen
n Iz,
1
max Zz kE(m)
4h
n
Vnen
n- 1-tant-1
E
max Z RE [2]
4h
(14)
n
where the last inequality is obtained from & Finally, from 12
13 and
14
have
20

---

Published as a conference paper at ICLR 2026
E [[X7
lim inf
8-000
E [m] X
B[X+
(E)
lim inf
El [[maxxe[[] Xi]
R-+00
vnt.
(1-1)
lim
1
E
max X ke(n]
4h P(E)
n-+00 E[maxie[n]] Xi]
(11- Vnla
(1
n- @vne -1
Ld(o²d d + S) ()gg(Ln)
2
lim n=0000
1-0
[l[max.e(]] X;]
Aln
IP(E)
- -(1- -1--) ( 01-0(
Ld(o2d + 8) log(Ln)
(ii [iimsup sup - El Elmaxxeln Xi]
Nen
where the last equality is obtained from En = 2(max ( Llog d 12
log n)) and Ey = o(n), and
2
P(E) 2 n (1 extn/(10L) (1 (1-2expí - 2exp( mpd
A.4 PROOF OF PROPOSITION 5.2
ExIo S 4 Let (0,,..., 0a) Rdd Consider
We first provide a proof for E. 2. 8j identical distribution Da. that generates the following deterministic points:
I1 = (1, (1.0..... 0), Ø2 = (0,1, 0),
Id = (O....... ......0.1 1), x = (O.....0) for ie {d+I....,,
For any algorithm, let 7 denote its stopping time.
Case 1. Set 0, = for 0 < e < 1. = 1) < 1/d. we set 02 =... 02 = 0. Then
01
max iE
x
0 = 01,
Eix 0 $
d
so the competitive ratio satisfies
B
1/d.
E|max a
Case 2. Otherwise if (T = 1)
1/d we set 02 = 01/E / = for 0
< I. = 2) S 1/d,
<E
then we set 0g- 01 02
0. Then
E
max x. T 0 1, :E(m)
E Bix,
T 0 S
02
+
+
d
d
again yielding, O, E[max;c[m] 07 S 1/d.
E|r,]
Case 3. Likewise, otherwise if IP(T = 2) > 1/d, we set 0g = 02/e 1/c. P( =3) S 1/d, then
we set 04 = 0g 0a = 0. We have
1 cd
E max J. 0
0g
E|x, 0 <
+ 1 +1
iE(n)
3|= 0
again yielding, as + O. E|maxxe(m)
0 $ 11/d.
There must exist some E {l.....d df such that PPr i) < 1/d. Therefore, in similar way, by choosing 0 to place the largest mass of 0 1/11/e on that coordinate, as - 0, we can show that
Elx,00 0
E mmmax 2. 0 <
Thus, in all cases, one can construct 0 such that the competitive ratio satisfies
Bla emax..tu 20 8
S 1/d.
21

---

Published as a conference paper at ICLR 2026
We next provide a proof for E/max:c[s]]
I 2' We can construct Dæ.1 such that ø1
(1, o,....0) .0) are drawn deterministically. We also consider 0 .1......,0) 0) such that X1 1. We also consider 2z,2 such that it generates a2 = (1/e, O,........ 0) with probability and otherwise, 22 = (0, 0........... .)) with probability 1 - e. For 2 3, we consider x; = (0,... (O.....0).
Then for any algorithm which does not know X; for i E [n] in advance, we have E|x, 0] < 1. On the other hands, the prophet who knows X; in advance can stop at = with XI =
X2 0 with probability
é or stop at 2 if X₂ 1/e with probability e. This implies that B|e 81
E[max,e]m] == 0) 1/(2 c). As + O, we can conclude E/max #; - 1/2.
B(x 6]
A.5 PROOF OF THEOREM 5
From Lemma A.1 we can show that
PP
0) < VV (ov dlog(n + nLnL/d3) + VSB) Ve E Ry) 2 1 1/n.
We define an event & = { (0 0)1 S Vo Vx V-lloo dlog(n - nl +
/SB), Vo E Rd),
which holds with P(E 2 1 Then under ε1, we have
X, - E(x;) & z 0 < X, + E(x,).
(15)
Lemma A.9. For L 2 1, let 2 ~ for E [4] be independent random vectors (not necessarily i.i.d) satisfying Assumption 3.2 Then
XI
Pr
Σ
Xlo 2 dexp
7
8L
Proof. Let Umin = Amin (E|Ei= 2,, T). By the matrix Chernoff bound (Theorem 5.1.1 in Tropp et al. (2115)) for sums of independent PSD matrices with Assumption 3.2 for any 8 E [0, 1].
Pr Amin Σ
S d (1 - 1-8
-6
Mmun/
(- 82 Umin
S (1 5)mm
S dexp
2
Choosing 8 yields
Pr
Amin
Σ t=1
Mmin 2
S dexp( dcxp(-Maull
Mmin
S dexp
IX 8L
8L
where the last inequality is obtained from Weyl's eigenvalue inequalities. probability least 1 deexp(-X1/(8E)))
This implies that, with
1X' x Mmin Ia t
Σ 1=1
24,
Is.
2
which completes the proof.
Let Es 1 mtar - 1 12), which holds with probability least ea/tte) from
Lemma A.9 Then under Eg, we have ||V 11 200 - 2x.. Then for i > ln have
E(x,)) S alll
+ + /S
2L (o + 53).
I V XE,
(16)
22

---

Published as a conference paper at ICLR 2026
Here we define h = V 25 (a /dlogg + nl.I1/d8) + VSB).
Let 2/ ~ Da,s and a*
Xte
E [max,e]e, +1,n] 2,3 0). Then, from 15 and (16), we have
1 sassaa a² + 2
(17)
Let 8 = & n &2 and He. (0.V) Then for i > en we have
B| | = i, (T = i He,))
T= [E) He,,IP(T = (e,,) + B[X! LCB 1(E) al(E) T i= i,, i He.))
(E) [H,,|P(=== = i |HH,,)
+ - ())) | 2 a, Hi, PX 2 a H.,,)
II
P(X < alHHe.)
jE((,+1,i-1]
(E) He, = i He, ) + BI(X - -a)+ HP, - n + He.))
2 (E) IPT = He..)
+ E [(x; - -2((x;) - a)+ 18)) He. P(T = n + He..)
E (a' 2 [A)](() |He. P(( i Hen)
1
+ [B (xx
(B)
a- 21 1(8) He. P(T n 11 He,))
where the last inequality is obtained from 17) and E(x,) S h.
Using the above, we have
E (E) He..
E E[
1(8) | T = He.. P(T = i He.)) He..
E
[ LCB (() | i, 1PP(T = i Hew) Hem]
+1
n
E
E (a< 2
()) He.
P(T = (lee)
+1
1(8) Hen 1) P(T + (Hn,) Hen
+
E
X; - a²
h
2
+
1
2 E
E Ea 1()'((E) He,1
P(r - il HlHl.)
2n)
i= +1
+E
max (E((,+I,m)
X, (x,- ax--a' a²
h1 ) +
5
1(8) Hi, -(==++1 11++1HHr) He.
1 )
E
E la 1(8) He..]
21 (1 - F(r = n + 1 He,))
E
max
X;1(E) Hi.
-E(a'((E) He.. - "1 P(T = n n1+ Hee,) Hi.
E
(a "P(E He,))
[ h) -P(T = n n 1 He,))
5
+
E
max iE((ntl,n)
X; P(E | He..) - a 'P(E He.))
P(r = n n 11 He..
2
5
2 a aPP(E He.,)
(18)
23

---

Published as a conference paper at ICLR 2026
where the last inequality is obtained from the definition of a².
Finally, using the above, we have
[[X;]
E B (8))H,
limin
lim 70000
2-000
1e +l6, X1)
EE]
(ea X;]
Inf
Pp)(E) h
2=000
E 1m Xi]
lim
1
1
d
O
Llog(Ln)
(ova+ Nln
(ovd + v$) vSS))
2
extta/8L
E |f +1.m) Xz)
L(o2d + log Ln)
-
lim sup
2
n n=-00
E
[m,
X,]
Nln
A.6 PROOF OF PROPOSITION 5.3
The argument follows the statement used in Marshall et al. (2020). For completeness, we provide the details here. Consider the instance where X1 deterministically, X₂ X3 =
X, deterministically. and X,, takes value 1/c with probability (for any 0 < 6 < 1) and 0 otherwise. For any wn, S n the gambler receives an expected payoff of 1, while the prophet receives an expected payoff' of 2 - 6. Thus, the ratio satisfies / Xi] - 1/(2 e). We can conclude the proof with <->
A.7 DETAILS OF AN ALGORITHM FOR NON-IID DISTRIBUTIONS UNDER WINDOW ACCESS
In the initial exploration phase of length e,, collect data and estimate 0 V V Ye where = E o + 3I for constant 0. In the subsequent decision phase, we apply LCB-based thresholding with window access for non-identical distributions, described below.
Decision with LCB Threshold under Window Access. the threshold value is
Let 2 ~ Dac for it E [en + 1.n]. Then
T.O. 50)
max
max iE(f.l
x: max 1,
Fe.,
(19)
and we define LCBs as
XLCBB x (x();
(20)
where (x(x)) 2x V-ix; (a dog((n LL33 VSB).
At stage En + 1, the algorithm checks whether maXke +1] X XLCB > a. so, it stops with T arg max X XLCB, otherwise, it continues. For en + 1, the algorithm stops at stage i XLCB 2 a.
A.8 PROOF OF THEOREM 5.4
From Lemma A.I we can show that
0) Vx - (o (lV/log(n nlnL/d3) + VSB) Vz E Bd) 2 1 1/n.
P
/olooo/llllnnnn We define event El {1 1o- 0)1 s V2 V V 1 dlog(n nf, L/d3) SB), Vo R*), which holds with ((EE) > 1
Let &g
(Eeete. xtza 2
Xta Iz}. which holds with probability at least
N 2x2//5 from
2
Lemma
A.9
Then under Ez, have ||V- < ((Eeje,))=e)) )))))) - 2 2x Then for all
24

---

Published as a conference paper at ICLR 2026
Algorithm 3 Explore-Then-Deciie with LCB Thresholding
under
Window
Access
(ETD-LCBTWA))
Input: Exploration length b; regularization parameter 3 Output: Stopping time for 1,..., do if Ln then
L Observe (2,, 34)
else i = L, + then
Observe (xi,, y/
Compute a from 19 and X for k S ln from (20).
if ma +1 XLCB 2 a then XLCB
Stop with arg max X
else
10
Observe (24,
Compute X-CBB from (00
11
if X.!.BBB 2 then
13
Stop with f- i
i E [n)], we have
(1(1)) S
+ S3)
2
n VBB) (o
(21)
Xln
Here we define h = v
L 2 (a Vlloognn + /53), & = & ng. Then, on E, for
I Dz,i for any i [n]. we have
x T h s x 0 - {(x) < ~x x 0 {(x) S xx T
Also, for all [n].
X; 2h s ..CB < X
We aggregate the whole window into single random variable. Define the window-maximum LCB at time fn +1: 1:
LLCB max XLCB +1]
For r = 2,... m where m == En- define
XLCB = LLCB
Define the associated threshold stopping time the reduced sequence:
7 = in E [m] XLCB a),
7= + 1 if the set is empty.
Then Algorithm is equivalent (i) stop at if LLCB > and return the argmax in [1, l, + +1], otherwise (ii) stop the first r such that LLCB > a. In particular, the realized LCB payoff satisfies
XLCB XLCB with the convention Å = 0. We also define X1 = maxxe[1.4.t] X and X, Xi,+r for (zr, (00.1)) be the full sigma-field generated by the exploration data and 2, = 27 0 for z; Dr..- By the fact that (Z.)22441 has the same conditional law as (X,) given Fe.,, on E, we have
(22)
[2, ml]. Let Fe.,
J. 0 max -/0 2a iE(e..] kl.
Fe.
<
E
max
max X1, max Zs Fen +h iE((m)
*Ele,
IE max X, Fen h. rE(m]
(23)
25

---

Published as a conference paper at ICLR 2026
Then for r E [m], we have
B[ - Fi.))
(F, | =
+ ((8) (, Fe.)
+ +[((x,c8-)),163 -))+ X7 2 a Fe. IP P.. 2 a F(,))((X) XI ca.vje/r-1]12
Fe.
(E) Frf = Fr..) + P[ x Ft. = m + F1.)
(E) Fr,,]P(F - Fr..)
+ E ( (x,, 2h - u) 1(8) Fr,
P(F= m m F1..).
(24)
Using the above, summing over r E [m].
E (() Fr...
2 al(E))((F S m Fe.)) 1(8)P(F m +1| I
Σ (X, 2h -0)+ F
re(m
z al(E)P(FF S Fe.)) + 1())P(T= m + FF,,)EE
max (X, 2h a)+ Fe.. (25)
rE(mm]
Using max, (X, 24 - a)+ 2 max, X, 2h- and 23). the RHS of 25
becomes
2 1(8) (a(1 pp) + [[mmax X, Ft.l 2h
2 1(8) (a(1- p) + p(2a- a - -33))
2 1(E)a 3h,
where p = P = m + 1 Fr.). Hence, taking expectation gives
FLCB [8) 2 Ela (()) - 3h.
On E, have X, XLCB XLCB Therefore,
E 2 E[x,1(E)] 2 ELX 1()) 2 E/a 1(8)] - 3h.
(26)
Also we have
E 1{ 2 E
max X, (( ré(ml
1 h
hh=
E
max X; 1(8)
1
h.
2
iE(n
2
Let M == max X₁. Since 0 s M S VLS, we have
E[MI(E) E[M] - VIST((E).
Thus,
E|a 1()] > 2 EIM E[M 1(8) I/ 2 2
[B[M] SIMI-VISS VILP--E) -h).
Combining with 26 yields
VLS
E[X,] 2 E
max X, - -01) 2
P(
(27)
2
:E(m]
Finally, since P(E9) < + (exxp(-Xen/iie we get
E[X=]
1 -0 > 2
L(o2d + 5) (n)
X (W.1/10))
+ VLS
+ de
E max, X²]
Elmmxx Xi]
Nln
26

---

Published as a conference paper at ICLR 2026
Algorithm 4 Decide with Offline Samples and LCB Thresholding (DOS 1OS--LC LCBT)
Input: Offline samples (xf, vf) for E S; regularization parameter 3
Output: Stopping time
V ELes
Bld A + V-1 Eies
Compute a from 28
for lari= 71 do
Observe (z))
Compute XL-B from (T)
X. a then Stop and set T t-
A.9 FURTHER DETAILS ON THE METHOD USING OFFLINE SAMPLES UNDER NON-L.LD. DISTRIBUTIONS
For any given S S [nx] such that |S| = en for ln > O (specified later), we assume that the gambler receives offline samples (ef, vf) where xa ~ Da,t for E S and yf = x? 0 + Th. In Algorithm using this offline samples, we obtain V = Σ Ies 292; + BIa and 0 = V-1 'ies Vi 2f for constant 0. Then we follow the following decision strategy.
Decision with LCB Threshold. For each time i > for 2, Da,a for all [1, n). define the threshold:
E a 2 [E
max 2 A
(28)
Recall the lower confidence bound for X; in the Explore-then-Decide framework: X x 0 {(a,), where [xxx)) == x. V- / dloggn + né,, I./d3) + The algorithm stops at stage i X.LBB 2 a.
Theorem A.10. In the non-i.i.d setting with unknown distributions and en offline samples of S, Al- gorithm 4 with e,, o(n), L, w( I. [.logd) ), and constant O achieves the following asymptotic competitive ratio:
B[X]]
lim inf 000
X,] 2 O
[immsu) sup n=000 E [[aaxee[]] X.IV
E [[max
N
Furthermore, by setting ln L(o2d+)) f(n) log(Ln) for some function f(n) (e.g. f(n) (log" n) for p > O, or O(n²) for 0 < 1) satisfying e, o(n), if OPT w(1/ /Jn)). then Algorithm Aatorithmaccheeve Fachieves the following asymptotic competitive ratio:
E[X,]
lim inf 200
2 2
E Emmaxeenn
X1]
Proof. From Lemma
A. we can show that
IP (0-
0) Vv V a (dvglog nl,, 1/d3) vS33 Vo E R²) 2 1 111nn
We define an event E = [|xT(0 (0-0(0) 0)1 S Vx V-la(o ni Ve E Rd),
which holds with P(E;) 2 1 n Then under E1, we have
X; - {(x)) < 0 < +(xx))
(29)
Lemma A.1I. For any S C random vectors (not necessarily ii.dd) satisfying Assumption 3.2
[n] with |S| = for 1 > let 2
Da for t. E be independent Then
X1
Pr
Σ IES
य.य z XLa
2 1 dexp
7
8L
27

---

Published as a conference paper at ICLR 2026
Let Mmin Amin (E) LE LES 2) By the matrix Chernoff bound (Theorem 5.1.1 in Tropp et al. 2015)) for sums of independent PSD matrices with Assumption 3.2 for any 8 E [0, 1).
Proof.
Pr Amin Σ
zt
1 (1 8mmm
3 (1 (1- 1-8
Raun/ L
I dexp
8²
Umin
2
L.
LES
Choosing 8 yields
Pr
Amin
Σ 222
Mmin
s d exp
Mmii 7L
1X' S dxxp
2
8L
YES
where the last inequality is obtained from Weyl's eigenvalue inequalities. Equivalently, with proba- bility at least
Σ IES
21
Mmin
IX' 2
Ia
ld.
2
which completes the proof.
Let E2
Lies 29 ua 2 Nfa 2/ [a]. which holds with probability least e from
2 Then under Ez, we have ||~ |1Eres 2657 > > s 1. Then for i E [m],
Lemma A.11 have
(3) {(x:)= S /|1 (ool://v=llllooo//oooo / gg))
2L
V Ne,
(a /dogln + nl + VS
(30)
Here we define =
X (a dllognn + nl, L/d3)) + VSB). Let 21 Dz,i and a*
E [ in] 2 0]. Then, from
29 and 30 we have
1 2t. h shaasa
a'
(31)
Let E = E and He, = (0, VJ. Then for 2 1, we have
E[x((01(E)) r= i, He, IP(T = H
-E(a1(E) He, [P(( = i He.)) + E LCB 1(E) - -a1(E) | T= =- ii, = i He.))
[[aa(EE] He,, |P( i He..)
+ +E[(X! (()) X.C.B 2 a. He,,IFF(X... 2 (He.)
II
P(X < (ee)
JE|-1]
2 [[) He, IP(T = i He.) + EX (() He, IP(T n He,))
2 [E) He, (P i He.))
[X, 2{(x:) - a)4 1(8) He.] P([]] + |1
2 (a" 1))(E)) He.
PP(T = He.))
2
1(8) | He, 1) P(T = =n n 1 He.).
X1 (x,-
5 21
+ E
where the last inequality is obtained from
31 and (xxx) h.
28

---

Published as a conference paper at ICLR 2026
Using the above, we have
E [())((E) He,.
7
E
E
(() = i,Hee [.(]].P(T = i He.)) He..
E
E [X (E) 7 He.] IP(T He.)) Heel
E
E
(a* ()) | Hee
PP(T = =il [Htee
1(8) Hen )) P(T P(T= P(T=n+h He,)) He,
X; a --- -//)
+
+
E
E [o= (())
Hee, |
P(r -i ((Hee)
+IE
max iE(m]
X; a"
h
2 +
1(8) Hin P n He,, He,
EE
[a 1(8) He..]
2 (1 P( n n+1177 1(He)))
5 2
E
max X,1(E) Hen iE(n)
P Hen
E
(a 'P(E Hoe)) 11
P(r n H).,)
5 h. + E||max (,) He. P'E Hen) 2) P(r +1 He.) He.
vE(x)
2 PP He.)) 2
Finally, using the above, we have
E[X+]
E [ I1
lim inf
lim inf
n 100
E [ax X.]
E E(maxye mm] X,]
5 ('P(E))
lim inf
h
n-+00
E[max4e(1) X²]
2
(ova+ vS) ))
Llog( (log(mm)
inf
1
O
n-+00
n
edT
E[maxse X.]
Mtn
1
1
L(oRd + S) log(Ln)
0
lim sup
2
E mmax Xi)
Nen
n=+00
29


Reviews:
[{"review_id": "9BWIifiVzt", "reviewer": "Reviewer_Y9sN", "summary": "This paper studies a variant of the bandit problem, which the authors describe as a “prophet inequality.” The agent observes the context $x_i$ and its sampling distribution $D_{x,i}$ at each round $i$, but the only available actions are **go** or **stop**. Once the agent chooses **stop**, the received reward is evaluated based on its ratio against the outcomes of all $n$ rounds.", "questions": "1. **Difficulty compared to linear bandits:**\n   Since the action is only *stop*, the environment handles the exploration, and the estimation method seems nearly identical, in what sense is this problem more challenging than linear bandits?\n   1.1. Why is the ratio necessarily $1 - 1/e$ in the i.i.d. setting?\n   1.2. In the non-i.i.d. setting, why can’t the ratio exceed $1/2$ even with access to offline data? A mathematical explanation would be appreciated.\n\n2. Regarding $\\lambda$ (and $\\lambda'$ in Section 5), what assumptions are made in relation to $n$?\n\n3. Proposition 5.2 claims that a minimal amount of exploration is necessary. However, as $l_n$ grows, the upper bound of the ratio is expected to increase. Is $d$ the best possible scaling? Is there any lower bound result showing that no improvement beyond the authors’ $l_n$ choice is possible?\n   3.1. It is also confusing that the authors effectively use $l_n$ offline data before starting the stopping process, yet in the offline setting the optimal ratio is $1/2$, while the proposed method achieves a higher value. How can this be reconciled?\n\n4. Why must the rewards be non-negative? Is there any trick or condition in the proof that specifically requires “above-zero” rewards?\n\n5. In the *Contributions* section, the authors claim that their setting is “the first scenario that only observes noisy rewards together with feature information and reward distributions are unknown.”\n   5.1. However, according to line 123, the agent does observe $x_i$ in every round, and even $D_{x,i}$ is known. Doesn’t this statement overstate the novelty of the contribution?\n   5.2. Then what exactly did previous works observe in addition to noisy rewards, and how does this work differ in that regard?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "According to the authors’ claim, this paper is the first to study *bandit reward–based prophet inequality* and successfully achieves competitive ratios comparable to related results in the literature. The introduction of the *window access* setting seems conceptually reasonable and somewhat interesting.", "weaknesses": "### Weaknesses\n\n1. From a *linear bandit* perspective, the problem seems rather simplistic. Hasn’t the estimation of $\\hat{\\theta}$ been extensively studied for a long time?\n   1.1. The LCB bound appears very similar to what we typically observe in linear bandit results; in fact, it looks almost identical to the classic bound from OFUL.\n   1.2. The setting assumes that the agent knows not only the context distribution (even future distributions $D_{x,i}$) but also that the reward probability $\\alpha$ can be easily computed via the inverse CDF. There is no exploration strategy involved — the agent merely decides whether to **go** or **stop**. If the sampling is sufficiently uniform so that $\\hat{\\theta}$ can be well estimated (or if $\\theta$ were known), the problem seems almost trivial.\n   Particularly, the only dimension-related constant one can rely on under limited exploration is the minimum eigenvalue, and it seems that in Proposition 4.1, the result holds mainly because $\\lambda$ is assumed to be independent of $n$ and $1/\\lambda$ is sufficiently small compared to $n$.\n   Taken together, it seems that the algorithm performs well simply because $n$ is large enough so that the dimension and minimum eigenvalue are no longer critical issues. Therefore, while the algorithm works as expected, it does not appear particularly *novel* or surprising.\n\nOverall, while there is a long line of work suggesting that the topic has intrinsic research value, I personally do not find it very clear what aspect of the problem is *challenging* compared to standard linear bandit analysis.\n\n### Clarity\n\n1. What is $w$? It suddenly appears starting from Theorem 4.2 and seems to play a critical role, yet I could not find a clear definition. Also, the notation involving $l_n = o(n)$ and $l_n = w(\\cdot)$ keeps appearing — could the notation be simplified?\n   For example, in Theorem 4.2, it would be clearer to specify the minimal $n$ (e.g., $n > \\dots$) for which $l_n \\in o(n)$ holds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gO2S3netLB", "reviewer": "Reviewer_g2Ym", "summary": "This paper studies prophet inequality with linear-bandit-type reward: the $i$th true reward is $X_i = x_i^T \\theta$, where $x_i$ is an observable feature vector distributed according to known distribution $D_{x, i}$, while $\\theta$ is an unknown latent parameter in $R^d$.  The decision maker observes a noisy value $y_i = X_i + \\eta_i$ each round, and needs to irrevocably decide to accept $X_i$ or continue.  The differences with classical prophet inequality are unknown reward distribution (because $\\theta$ is unknown) and noisy observation.  The paper designs algorithms achieving approximation ratios $1 - 1/e$ for the iid setting and $1/2$ for the non-iid setting.  These bounds are claimed to be tight.  The main algorithmic idea is explore-then-decide: use ridge regression to estimate $\\theta$ with samples from the first $l_n$ rounds; then use a classical thresholding algorithm for known-distribution prophet inequality but apply to the lower-confidence bound on the reward, computed from the estimated parameter $\\hat \\theta$.  Simulation results show that this algorithm achieves the desired approximation ratios and is better than heuristic algorithms.", "questions": "## Questions for the authors\n\n(Q1)  See (W1). \n\n(Q2) The iid experiment considers both ETD and $\\epsilon$-Greedy, but the non-iid experiment only has ETD.  Why?  How does $\\epsilon$-Greedy perform in non-iid setting?  \n\n\n\n## Suggestions\n\n* Typo: line 125-126: $X_{\\tau+1}$ should be $X_{n+1}$ ?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "(S1) This paper approaches the problem of prophet inequality with unknown reward distributions (which has been studied by some previous works) from a different angle: a linear reward structure with observable feature and unobservable latent parameter.  This is different from previous works (such as Correa et al, 2019) that assume unstructured unknown distributions.  This linear structure assumption allows the authors to prove very nice positive results: without any additional samples, by just going over the reward sequence once, the algorithm can achieve $1-1/e$ approximation ratio, which was achievable only with at least $\\Omega(n)$ additional samples in the unstructured case.  Such a linear structure also allows noise in the reward observation.  This structural assumption is arguably realistic but has not been widely considered in the literature of learning-based optimal stopping or sequential search problems, so it is a good conceptual contribution to the literature in my opinion. \n\n(S2) Besides the Explore-Then-Decide algorithm, the authors also analyze the performance of $\\epsilon$-Greedy, the classical algorithm that mixes exploration and exploitation.  This makes the picture more complete.  \n\n(S3) The approximation ratios, $1-1/e$ for iid and $1/2$ for non-iid settings, are claimed to be tight.  (While these results seem to be true, I do have a question for the authors regarding formal proofs for these results.)", "weaknesses": "(W1) A small weakness is the lack of formal argument that the $1-1/e$ bound for the iid setting is tight.  The authors claim in Remark 4.4 that $1-1/e$ is tight, because Correa et al (2019) show that one cannot do better than $1 - 1/e$ if the number of samples from the unknown reward distributions is $O(n)$, _if the reward distribution is unstructured_.  However, in this paper, the reward distribution has a linear structure, and ridge regression can estimate the true reward parameter very accurately and efficiently.  So, I am not sure whether the previous $1-1/e$ negative result (for unstructured distributions) can imply the same negative result for the linear structured distributions. @authors: Can you comment on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SgQAFbfcEr", "reviewer": "Reviewer_KgWu", "summary": "This paper studies the prophet inequality in a novel and practical setting where the underlying reward distributions are unknown, and the decision-maker only observes noisy realizations of the rewards. The authors propose algorithms based on Lower-Confidence-Bound (LCB) thresholding.\n\n1.  For i.i.d. setting, the paper presents two algorithms, Explore-then-Decide (ETD-LCBT) and $\\epsilon$-Greedy-LCBT, that both achieve the sharp $1-1/e$ asymptotic competitive ratio. This matches the optimal bound for the classical known-distribution case and is achieved under a mild non-degeneracy condition on the growth of the optimal prophet's value.\n2.  For non-i.i.d. setting, the paper shows that the optimal $1/2$ competitive ratio can be achieved against a relaxed benchmark that excludes the initial exploration phase.\n3.  By introducing a mild relaxation of window access, i.e., allowing the decision-maker to choose from a small set of past items, the proposed algorithm (ETD-LCBT-WA) achieves the optimal $1/2$ ratio against the standard, non-relaxed prophet benchmark.\n\nEmpirical results on synthetic datasets validate the theoretical findings, showing the algorithms achieve the claimed ratios and are robust to noise.", "questions": "1.  The $1-1/e$ ratio in Corollary 4.3 depends on $OPT = \\omega(1/\\sqrt{f(n)})$. Could the authors elaborate on scenarios where this might not hold? For example, if the rewards $X_i \\sim \\text{Bernoulli}(p_n)$ where $p_n \\to 0$ rapidly, thus $X_i$ are all extremely small, then $OPT$ might shrink too fast. How does this non-degeneracy condition compare to similar assumptions in the learning-to-price or contextual bandit literature?\n2.  The paper shows that for the non-i.i.d. case, a $1/2$ ratio is achieved against a relaxed benchmark or the full benchmark with window access. Proposition 5.2 justifies the difficulty. Is it known or conjectured whether the $1/2$ ratio is impossible for the standard non-i.i.d. problem no window against the full $\\mathbb{E}[\\max_{i \\in [n]} X_i]$ benchmark in this linear learning setting?\n3.  The required exploration length $l_n$ depends on $L$ from Assumption 3.2. Remark 3.3 states $L$ may depend on $n$ and diverge. Remark 4.4 gives an example of $L=\\sqrt{n}$. Could you elaborate on the practical implications of a diverging $L$? If $L=\\sqrt{n}$, $l_n$ must be $\\omega(\\sqrt{n})$, which seems to fit the $l_n=o(n)$ requirement. Is this a common scenario, and does it present any practical challenges for the algorithm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.  The paper introduces a compelling new model for prophet inequalities that incorporates unknown distributions, noisy observations, and contextual features. This setting is well-motivated by real-world applications like hiring or ad allocation, where contextual data is available but true reward values are unknown and feedback is noisy.\n2.  In this new, challenging learning setting, the paper achieves the sharp, classical competitive ratios of $1-1/e$ for i.i.d. and $1/2$ for non-i.i.d. with a window. It shows that the linear structure is sufficient to replace full distributional knowledge without sacrificing performance, given a mild non-degeneracy condition.\n3.  The paper is very clear about why its assumptions are necessary. It explicitly provides impossibility results of Proposition 4.1 for noise and Proposition 5.2 for non-i.i.d. learning that motivate the need for its structural assumptions (the linear model) and conditions (the $OPT$ growth condition and the window-access relaxation).", "weaknesses": "1.  The sharp $1-1/e$ bound in the i.i.d. case (Corollary 4.3) hinges on the $OPT = \\omega(1/\\sqrt{f(n)})$ condition. The paper argues this is \"mild\" because $OPT$ is often bounded away from zero. While this is a reasonable assumption, it is the key condition that allows the algorithm to overcome the impossibility from noise shown in Prop 4.1. The paper could be strengthened by discussing this assumption in more detail, perhaps with examples of reward distributions where it might be violated, e.g., if $OPT \\to 0$ quickly.\n2.  To achieve the optimal $1/2$ ratio, the paper relies on either a relaxed benchmark (Theorem 5.1) or a relaxed problem setting (Theorem 5.4, window access). While both are well-justified, it leaves open the question of the standard non-i.i.d. problem against the full benchmark. The paper shows it's hard, but it's not clear if it's proven impossible to achieve $1/2$.\n3.  The experiments are supportive but limited to synthetic data. While this is standard for a theoretical paper, the practical motivation would be bolstered by testing on semi-synthetic data, e.g., using features from a real-world dataset to generate the linear rewards.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xC3aOnfffT", "reviewer": "Reviewer_YYur", "summary": "The paper studies Prophet Inequalities under a novel setting. In such a setting, the rewards at time $i\\in[n]$ are defined as $x_i^\\top \\theta$ where $\\theta$ is an unknown fixed latent vector, while $x_i$ is a stochastic feature vector sampled at each time from a known distribution $\\mathcal{D}_i$ (which can potentially varies over time). At each time, the decision maker observes both $x_i$ and a nosy observation of the rewards and decides whether to accept the reward (and then stop) or continuing the interaction. The objective is to attain a \"good\" competitive ratio w.r.t. the optimum a posteriori over the $n$ time steps. The authors propose two algorithm for the i.i.d. setting ($\\mathcal{D}_i=\\mathcal{D}$) attaining the $1-1/e$ competitive ratio, under a growth condition of the optimum. In the non i.i.d. setting, the author propose two algorithms. The first one attains $1/2$ competitive ratio against an optimum which considers the round from a fixed threshold to the end of the interaction, under a growth condition of the optimum. The second one assumes to have access to past samples (in the decision) and attains $1/2$ competitive ratio against the standard optimum.", "questions": "Could you elaborate on the assumptions?\n\nSince I am not an expert on this literature I will be happy to increase my score if the answers turn out to be pretty positive.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I believe the results attained in this paper are interesting. Assuming that the rewards is linear in a latent vector is reasonable in practice and the authors effectively adapts techniques from contextual bandits to this \"new\" prophet inequality setting. The paper studies both the i.i.d. setting and the non i.i.d. one, thus extending the analysis to non-stationary settings.", "weaknesses": "My main concern is about the various assumptions which are made throughout the paper. Specifically,\n\n1. It is not clear to me why the growth assumption should be either mild or reasonable in practice. To me, it seems just an artefact to overcome the theoretical hardness of the problem.\n2. I believe this \"new\" contextual prophet inequality setting is interesting. Nonetheless, I have some concerns on the non i.i.id. setting. Indeed, the distributions can vary over time; still, they are known to the decision maker. Differently, the latent vector is unknown but fixed. Thus, in some sense, the non-stationarity of the problem is known.\n3. Finally, I see the results on the adversarial setting as less meaningful than the i.i.d. ones. To me, the relaxed benchmark in Theorem 5.1. is really weak since it depends on the exploration phase of the algorithm. Moreover, the window access assumption seems again just a way to overcome the weakness of the previous result, since it cancels the inherent difficulty of the prophet inequality problem.\n\nMinor: Line 361-362 I think the $\\max$ should be inside the expectation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)