Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards".
Jane: Here's the gist of the paper. The paper studies prophet inequalities with discounted rewards to show that even structured nonstationarity can erase the classical advantage of the stationary i.i.d.
Tom: setting The main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d.
Jane: setting Fundamental Limits under Reward Decay The study focuses on single-quantile threshold policies and derives fundamental performance limits under decaying rewards, showing a sharp transition from the classical 1−1/e guarantee to a worst-case 1/2 barrier This barrier is worst-case optimal, matching the classical non-i.i.d.
Tom: impossibility bound The analysis involves constructing hard distributions to upper bound every single-threshold policy and showing that this barrier persists even for arbitrary stopping rules.
Paper summary: Tom: We talked about how this paper, "Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards," shows that structured nonstationarity from discounting can erase the classical advantage of the stationary and i.i.d setting >
Jane: They focus on single-quantile threshold policies and demonstrate a sharp transition in performance guarantees, moving from the classical one minus one over e guarantee down to a fundamental two-fifths barrier >
Lu: The paper shows that this one/two barrier is worst-case optimal, matching the impossibility bound you see in the fully nonidentically distributed case > <ref:2606.30118#pg1>
Meng: So what they are really saying is that even though the base rewards are i.i.d., introducing discounting creates a form of nonstationarity that makes the problem as hard as if everything were totally different >
Lalam: They achieve this by designing single-quantile algorithms that match these tight bounds through an effective-horizon principle, where the decaying reward sequence behaves like a stationary i.i.d. sequence over a shorter horizon >
Tom: It’s about calibrating your acceptance decision to this effective horizon induced by discounting, and they show that this calibration works even for heterogeneous decay factors and unequal phase lengths >
Jane: And they also look at the infinite-horizon continuous-decay benchmark, which reveals a sharp discontinuity where introducing arbitrarily weak decay induces a worst-case competitive ratio of two-fifths >
Lu: This means that in the boundary regime between stationarity and decay, the stopping problem can be as difficult as the fully general nonidentically distributed setting >
Meng: If we look at this from a deployment side, it suggests that for systems with time preferences or depreciation, we have to fundamentally rethink how we set our stopping rules because i.i.d. assumptions are quickly invalidated by time decay >
Lalam: The framework extends to general phase-dependent decay factors and unequal phase lengths by defining an effective horizon based on the total discounted opportunity mass >
Tom: The main message is that this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d. setting entirely >
Conclusion: Jane: So, wrapping up, "Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards" investigates how discounting rewards fundamentally change the performance guarantees we get from assuming things are stationary and independent >
Tom: The authors show that for single-quantile threshold policies, the competitive ratio transitions from one minus one over e down to a fundamental two-fifths barrier as discounting accumulates over many phases in a canonical regime >
Lu: They proved that this one/two barrier is worst-case optimal and persists even for arbitrary stopping rules, confirming it's an intrinsic limitation of the discounted-reward model itself > <ref:2606.30118#pg1,persists even for arbitrary stopping rules>
Meng: From what I see, this means if you’re building something sequential where rewards are decaying over time, you can’t rely on the classic stationary i.i.d guarantees anymore; you have to plan for that one/two performance limit > <ref:2606.30118#pg1>
Lalam: The implication is that discounting alone can erase the classical advantage of stationarity, fundamentally reshaping the guarantees achievable by single-quantile stopping rules under decaying rewards >
Jung-hun Kim, Vianney Perchet
FairPlay Team · CREST · ENSAE · Institut Polytechnique de Paris · Criteo AI Lab
cs.GT, cs.DM, cs.DS, econ.TH, math.OC
Submitted: 2026-06-29
Updated: 2026-11-06
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: The paper studies prophet inequalities with discounted rewards to show that even structured nonstationarity can erase the classical advantage of the stationary i.i.d.
Key concepts
- Prophet Inequalities
- These are mathematical bounds that relate the expected maximum value achievable by a prophet inequality to the optimal stopping value under certain reward structures. The paper uses these inequalities to establish performance limits for stopping rules in various settings.
- Discounted Rewards
- This refers to a reward sequence where future rewards are worth less than immediate rewards due to a discount factor. This introduces nonstationarity into the problem, meaning the underlying distribution of rewards changes over time.
- Effective Horizon Principle
- This principle suggests that a decaying reward sequence behaves like a stationary i.i.d. sequence observed only over a shorter, effective horizon determined by the discounting mechanism rather than the raw observation length.
Terminology
Summary
The paper studies prophet inequalities with discounted rewards to show that even structured nonstationarity can erase the classical advantage of the stationary i. p. 0 base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily
weak form of nonstationarity can erase the classical advantage of the stationary i. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily
weak form of nonstationarity can erase the classical advantage of the stationary i.Where the paper says it
Where the paper says it
Fundamental Limits under Reward Decay
The study focuses on single-quantile threshold policies and derives fundamental performance limits under decaying rewards, showing a sharp transition from the classical 1−1/e guarantee to a worst-case 1/2 barrier This barrier is worst-case optimal, matching the classical non-i.i.d. impossibility bound The analysis involves constructing hard distributions to upper bound every single-threshold policy and showing that this barrier persists even for arbitrary stopping rules. p. 1 impossibility bound. We
also show that the 1/2 barrier is not an artifact of single-threshold policies: any arbitrary
stopping rules face the same worst-case barrier.Where the paper says it
Single-Threshold Optimality via an Effective-Horizon Principle
The authors design single-threshold algorithms that match the tight bounds by calibrating acceptance decisions to an effective horizon induced by discounting This calibration extends to heterogeneous decay factors and unequal phase lengths The key insight is the effective-horizon principle, where a decaying reward sequence behaves like a stationary i.i.d. sequence observed over a shorter horizon. p. 2 The key insight is an effective-horizon principle: at the level of the
prophet benchmark (expected maxima), a decaying reward sequence behaves like a stationary
i. sequence observed over a shorter horizon.Where the paper says it
Discontinuous Breakdown at the Stationarity Boundary
The analysis of the infinite-horizon continuous-decay benchmark reveals a sharp discontinuity: while the stationary infinite-horizon setting admits a trivial competitive ratio of 1, introducing arbitrarily weak decay induces a sharp breakdown, yielding a worst-case competitive ratio of 1/2 This suggests that in the boundary regime between stationarity and decay-induced nonstationarity, the stopping problem can be as hard as the fully general nonidentically distributed setting.
Extension to General Decay Factors and Phase Lengths
The framework is extended to general phase-dependent decay factors and unequal phase lengths by defining an effective horizon based on the total discounted opportunity mass The resulting upper bound expression directly reflects this generalized horizon, suggesting that the acceptance quantile should be set according to the total discounted opportunity mass rather than the raw horizon length.
Infinite-Horizon Continuous Decay Benchmark
The infinite-horizon continuous decay analysis confirms that arbitrarily weak reward decay suffices to collapse the attainable competitive ratio from 1 to 1/2 This loss of robustness highlights that discounting alone can erase the classical advantage of stationarity, fundamentally reshaping the guarantees achievable by single-threshold stopping rules.
Conclusion
The paper concludes that discounting alone can erase the classical advantage of stationarity, fundamentally reshaping the guarantees achievable by single-threshold stopping rules under decaying rewards The worst-case competitive ratio is driven down to a tight 1/2 barrier in the canonical setting. The optimal dynamic programming policy attains this limit, confirming that the fundamental limitation is intrinsic to the discounted-reward model itself. p. 7 Second, is the resulting 1/2 limit merely an artifact of the singlethreshold restriction, or is it an intrinsic limitation of the discounted-reward model? The next
section answers the first question by giving a matching effective-horizon threshold rule; we return
to the second question later by analyzing the optimal dynamic-programming policy.Where the paper says it
References
The study of prophet inequalities dates back to the seminal work of Krengel and Sucheston [Hill and Kertz, 1982] Subsequent work established sharp constant-factor benchmarks in the independent non-i.i.d. and stationary i. p. 0 base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily
weak form of nonstationarity can erase the classical advantage of the stationary i. , 2019, 2017]. On the other side, for independent
but non-identically distributed (non-i. In the independent but non-identically distributed (non-i. ) case, SamuelCahn [1984] showed that a threshold stopping rule attains the optimal competitive ratio of 1/2. ) case, SamuelCahn [1984] showed that a threshold stopping rule attains the optimal competitive ratio of 1/2. setting, Hill and Kertz [1982] established a competitive ratio of at least 1 − 1/e, later
reinterpreted in algorithmic terms as a single-quantile threshold policy that accepts the first observation exceeding a suitable quantile [Correa et al. setting, Hill and Kertz [1982] established a competitive ratio of at least 1 − 1/e, later
reinterpreted in algorithmic terms as a single-quantile threshold policy that accepts the first observation exceeding a suitable quantile [Correa et al. , 2019, Ehsani et al. setting, a fixed value-threshold rule attains the optimal worst-case competitive ratio 1/2
[Samuel-Cahn, 1984] (see also Ehsani et al. [2018], Goldenshluger et al. In contrast to the above literature, which primarily focuses on stationary i. rewards or fully
general non-identically distributed reward sequences, our work studies single-threshold stopping
policies under a discounting-induced nonstationary reward model. In contrast to the above literature, which primarily focuses on stationary i. rewards or fully
general non-identically distributed reward sequences, our work studies single-threshold stopping
policies under a discounting-induced nonstationary reward model. This framework captures a continuous transition from stationarity to reward decay, isolating the effect of discounting as a structured departure from the i. Discounting has also appeared in related prophet-region, secretary-type, and random-horizon
settings. This framework captures a continuous transition from stationarity to reward decay, isolating the effect of discounting as a structured departure from the i. Discounting has also appeared in related prophet-region, secretary-type, and random-horizon
settings. The prophet-inequalities literature has established tight constant-factor guarantees. On one side,
in stationary i. On one side,
in stationary i. reward settings, the classical 1−1/e competitive-ratio bound is known to be tight
for a class of single-threshold policies [Correa et al. Owing to their rich mathematical structure and practical relevance, prophet
inequalities have been extensively studied [Correa et al. , 2019] and have found applications in areas
such as posted-price mechanisms [Lucier, 2017], online advertisement allocation [Alaei et al. , 2019, 2017]. On the other side, for independent
but non-identically distributed (non-i. In the independent
non-i. setting, a fixed value-threshold rule attains the optimal worst-case competitive ratio 1/2
[Samuel-Cahn, 1984] (see also Ehsani et al. , 2018, Goldenshluger et al. Beyond single-threshold policies, more adaptive but computationally involved approaches
have been proposed to improve performance in related settings, such as Abolhassani et al. Owing to their rich mathematical structure and practical relevance, prophet
inequalities have been extensively studied [Correa et al. , 2019] and have found applications in areas
such as posted-price mechanisms [Lucier, 2017], online advertisement allocation [Alaei et al. Discounting has also appeared in related prophet-region, secretary-type, and random-horizon
settings. In the prophet-region literature, Allaart [2006] studies uniformly bounded random variables under discounting, and characterizes the corresponding prophet regions, yielding sharp additive
comparisons between the expected maximum and the optimal stopping value. In the prophet-region literature, Allaart [2006] studies uniformly bounded random variables under discounting, and characterizes the corresponding prophet regions, yielding sharp additive
comparisons between the expected maximum and the optimal stopping value. In the discounted secretary problem, Babaioff et al. In the discounted secretary problem, Babaioff et al. [2009] consider random-order arrivals with time-dependent discount
factors and obtain competitive guarantees for fixed sets of arbitrary values. [2009] consider random-order arrivals with time-dependent discount
factors and obtain competitive guarantees for fixed sets of arbitrary values. Relatedly, Giambartolomei et al. Relatedly, Giambartolomei et al. [2024] study i. [2024] study i. prophet inequalities with a random horizon, where the horizon
distribution is known but its realization is not; this model can be viewed through a discounted
optimal stopping problem with discount factors given by the horizon survival probabilities. We further show that
a similar discontinuous breakdown persists in an infinite-horizon continuous-decay benchmark,
where arbitrarily weak decay collapses the stationary benchmark from 1 to 1/2. 1 Introduction
Prophet inequalities constitute a fundamental class of problems in online optimal stopping [Hill
and Kertz, 1992]. Discounting has also appeared in related prophet-region, secretary-type, and random-horizon
settings. In the prophet-region literature, Allaart [2006] studies uniformly bounded random variables under discounting, and characterizes the corresponding prophet regions, yielding sharp additive
comparisons between the expected maximum and the optimal stopping value. Moreover, we prove that our
single-threshold rule is optimal in this benchmark and achieves this bound. 2 Related Work
The study of prophet inequalities dates back to the seminal work of Krengel and Sucheston [1977]. 3 Problem Statement
We consider the classical prophet-inequality framework over a finite horizon n ∈ N, where a nonnegative random reward Xi ≥ 0 is revealed sequentially to a gambler at each stage i ∈ [n]. To
model decaying reward distributions, we partition the time horizon into S ≥ 1 consecutive phases,
or time intervals, {Ts}
S
s=1, which form a disjoint partition of [n]. Owing to their rich mathematical structure and practical relevance, prophet
inequalities have been extensively studied [Correa et al. , 2019] and have found applications in areas
such as posted-price mechanisms [Lucier, 2017], online advertisement allocation [Alaei et al. [2018], Goldenshluger et al. From an economic
perspective, single-threshold stopping rules naturally correspond to standard posted-price mechanisms [Arnosti and Ma, 2023], in which the decision maker commits to a fixed acceptance rule in
advance. Prophet Inequalities with Discounted Rewards: As Hard as
the Non-i. Case
Jung-hun Kim∗1 and Vianney Perchet†1,2
1FairPlay Team, CREST, ENSAE, Institut Polytechnique de Paris
2Criteo AI Lab
Abstract
We study prophet inequalities with discounted rewards, where i. setting, a fixed value-threshold rule attains the optimal worst-case competitive ratio 1/2
[Samuel-Cahn, 1984] (see also Ehsani et al. [2018], Goldenshluger et al. We formulate our policies in terms of a fixed acceptance
quantile, and refer to them as single-threshold policies throughout. Threshold policies are a cornerstone of prophet inequalities due to their simplicity and sharp
guarantees.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive threshold calibration for decaying rewards: The improved system can use an effective horizon principle to calibrate acceptance decisions to a time-varying effective horizon, matching bounds derived from
an effective horizon principle: at the level of the prophet benchmark (expected maxima), a decaying reward sequence behaves like a stationary i.i.d. sequence observed over a shorter horizon.
-
Handling heterogeneous decay factors and phase lengths: The system can extend optimal single-threshold algorithms to settings with arbitrary phase-wise decay factors and unequal phase lengths by using an effective horizon based on the
total discounted mass of opportunities,
defined as BG:= Xs−1t=1 λt CS. -
Robust competitive ratio guarantees: The improved AI can provide tight worst-case competitive ratios for single-threshold policies under decaying rewards, matching bounds derived from theorems like Theorem 6 and Theorem 9, which show that
the optimal dynamic programming policy τDP matches our tight upper bounds.
-
Verification against the nonstationarity boundary: The system can distinguish between the stationary i.i.d. regime and structured nonstationarity by identifying a
sharp transition from the classical i.i.d. value 1 − 1/e to a worst-case 1/2 barrier
as accumulated discounting drives the competitive ratio down in the boundary regime between stationarity and decay reward sequences (discontinuous breakdown at the stationarity boundary
). -
Policy optimization via dynamic programming: The system can implement a dynamic programming policy that is proven to dominate any stopping rule on hard instance families, ensuring that
DP dominates any stopping rule on this (infinite-horizon) instance family,
leading to the optimal competitive ratio CRn(τDP).
Abstract
We study prophet inequalities for n i.i.d. base rewards subject to multiplicative discounts across S phases. For equal-length phases and a common discount factor γ, we characterize the optimal competitive ratio of single-quantile policies as n to infinity with S and γ fixed. The resulting sharp guarantee describes the dependence on the phase parameters: it recovers 1-1/e without discounting and approaches 1/2 in the worst-case regime. We also establish a distribution-free comparison that bounds the discounted prophet by a fractional i.i.d. maximum with effective horizon B, the sum of the discount weights across all observations. The comparison yields acceptance probability 1/B, determined only by the phase profile. This calibration attains the canonical optimum even among single-quantile policies that may choose their acceptance probability using the known base distribution. The comparison also gives guarantees for heterogeneous discounts and unequal phase lengths. A complementary optimal-stopping upper bound establishes the same limiting optimum of 1/2 for arbitrary stopping rules in the canonical model. Finally, the same effective-horizon calibration sets acceptance probability 1- γ under infinite-horizon geometric discounting. This explicit quantile rule attains Boshuizen's (1994) known optimal worst-case ratio 1/(1+ γ) without solving a Bellman equation.
Sources
- Individual Fairness in Prophet Inequalities
- IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
- Optimal single threshold stopping rules and sharp prophet inequalities
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments
- Fair Division Under Boolean Valuations: Beyond Normalization