Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards

arXiv:2606.30118 · cs.GT, cs.DM, cs.DS, econ.TH, math.OC · Submitted 2026-06-29 · Read on arXiv

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

Where the paper says it

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.

i.d. setting The main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i. p. 0
Where the paper says it

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.

i.d. 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. 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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

i.d. settings. In the independent but non-identically distributed (non-i. p. 0
Where the paper says it

, 2019, 2017]. On the other side, for independent but non-identically distributed (non-i.

i.d.) case, SamuelCahn [1984] showed that a threshold stopping rule attains the optimal competitive ratio of 1/2. p. 2
Where the paper says it

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.

In the i.i.d. 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. p. 2
Where the paper says it

) 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.

, 2019, Ehsani et al. p. 2
Where the paper says it

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.

, 2018, Goldenshluger et al. p. 1
Where the paper says it

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.

, 2024]. In contrast to the above literature, our work studies single-threshold stopping policies under a discounting-induced nonstationary reward model. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

Discounting has also appeared in related prophet-region, secretary-type, and random-horizon settings. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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-inequality literature has established tight constant-factor guarantees On one side, in stationary i. p. 0
Where the paper says it

The prophet-inequalities literature has established tight constant-factor guarantees. On one side, in stationary i.

i.d. 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. p. 0
Where the paper says it

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.

, 2017, 2019]. p. 0
Where the paper says it

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.

On the other side, for independent but non-identically distributed (non-i. p. 0
Where the paper says it

, 2019, 2017]. On the other side, for independent but non-identically distributed (non-i.

i.d.) reward sequences, the optimal competitive ratio degrades to 1/2, as shown by Samuel-Cahn [1984]. p. 1
Where the paper says it

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.

Beyond single-threshold policies, more adaptive but computationally involved approaches have been proposed to improve performance in related settings, such as Abolhassani et al. p. 2
Where the paper says it

, 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.

[2017] and Correa et al. p. 0
Where the paper says it

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.

[2017]. In contrast to the above literature, our work studies single-threshold stopping policies under a discounting-induced nonstationary reward model. 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. p. 2
Where the paper says it

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 discounted secretary problem, Babaioff et al. p. 2
Where the paper says it

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.

[2009] consider random-order arrivals with time-dependent discount factors and obtain competitive guarantees for fixed sets of arbitrary values. p. 2
Where the paper says it

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.

Relatedly, Giambartolomei et al. p. 2
Where the paper says it

[2009] consider random-order arrivals with time-dependent discount factors and obtain competitive guarantees for fixed sets of arbitrary values. Relatedly, Giambartolomei et al.

[2024] study i. p. 2
Where the paper says it

Relatedly, Giambartolomei et al. [2024] study i.

i.d. 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. p. 2
Where the paper says it

[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.

Theodore P Hill and Robert P Kertz. p. 0
Where the paper says it

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].

Comparisons of stop rule and supremum expectations of iid random variables. p. 2
Where the paper says it

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.

Ulrich Krengel and Louis Sucheston. p. 2
Where the paper says it

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].

Semiamarts and finite values. p. 3
Where the paper says it

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].

Brendan Lucier. p. 0
Where the paper says it

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.

An economic view of prophet inequalities. p. 1
Where the paper says it

[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.

Thomas Nedelec, Clément Calauzènes, Noureddine El Karoui, and Vianney Perchet. p. 0
Where the paper says it

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.

Learning in repeated auctions. Alexander Goldenshluger, Yaakov Malinovsky, and Assaf Zeevi. p. 1
Where the paper says it

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.

Optimal single threshold stopping rules and sharp prophet inequalities. p. 1
Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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).

  5. 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

Related papers