Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
summary
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.
In short
The study investigates prophet inequalities when rewards are discounted, even if they are independent and identically distributed (i.i.d.). It shows that even this structured nonstationarity erases the classical advantage of the stationary i.i.d. setting, leading to a worst-case competitive ratio of 1/2 for single-threshold policies.
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 used across episodes
This episode discusses
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards · Paper Radio
- 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
The paper
Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards · Read on arXiv
Jung-hun Kim, Vianney Perchet
FairPlay Team · CREST · ENSAE · Institut Polytechnique de Paris · Criteo AI Lab
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.
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 >
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game