Research map / Learning theory and algorithms / Sample complexity
Lookback Prophet Inequalities
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that prophet inequalities with lookback decay functions reduce, in adversarial, random-order and IID models, to a single parameter gamma = inf D_j(x)/x, and gives matching/improved competitive-ratio bounds as functions of gamma.
Problem
Prophet inequalities model online selection without revisiting rejected items, which is overly pessimistic; the paper asks how allowing lookback (recovering a decayed fraction of a rejected value) improves the competitive ratio.
Approach
General decay functions D_j recovering value from an item rejected j steps earlier are reduced (via limit D_infinity and a rescaling argument on {0,a,b} instances) to the linear decay gamma*x, so the competitive ratio depends only on gamma = inf_x inf_j D_j(x)/x; tight bound 1/(2-gamma) in adversarial order, and bounds for random order and IID.
Key results
- In the adversarial order model the competitive ratio is exactly 1/(2-gamma) for any decay sequence, achieved by a single-threshold algorithm.
- In the random order model the upper bound is (1-gamma)^{3/2}(sqrt(3-gamma)-sqrt(1-gamma))+gamma, matching sqrt(3)-1 at gamma=0 and 1 at gamma=1, with a single-threshold lower bound 1-(1-gamma)p_gamma.
- In the IID model the upper bound U(gamma) is increasing, with U(0)≈0.778 and U(1)=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase lookback decay γ in the adversarial-order model | Prophet inequality · Adversarial order | competitive ratio: \frac{1}{2-\gamma} | Helped |
| Increase lookback decay γ | Single-threshold algorithm · Random order | competitive ratio lower bound: 1 - (1-\gamma) p_\gamma | Helped |
| Increase lookback decay γ | Prophet inequality · Random order | competitive ratio upper bound: (1-\gamma)^{3/2}(\sqrt{3-\gamma} - \sqrt{1-\gamma}) + \gamma | Helped |
| Increase lookback decay γ | Single-threshold algorithm · IID | competitive ratio lower bound: 1 - (1-\gamma) p_\gamma | Helped |
| Increase lookback decay γ | Prophet inequality · IID | competitive ratio upper bound: U(0) = \frac{4-\log 3}{2(2-\frac{1}{e}^2)} \approx 0.778; U(1) = 1 | Helped |
| Use decay functions with γ_D = 0 rather than a positive uniform fractional recovery | Prophet inequality · Random order and IID | competitive ratio | No clear effect |
| Replace general decay functions with their asymptotic decay D∞ | Prophet inequality · Adversarial order and random order | competitive ratio | No clear effect |
| Replace general decay functions with their asymptotic decay D∞ | Prophet inequality · IID | competitive ratio: O(n^{-1/3}) | No clear effect |
Limitations
- Random-order and IID gap between upper and lower bounds remains; tight only in adversarial order.
- Upper bounds for D-prophet in random and IID models carry an O(n^{-1/3}) or limit-argument caveat.
- Analysis restricted to deterministic decay functions in main text.
Experimental setup
Metrics: competitive ratio
Baselines: classical prophet inequality dynamic programming single-threshold algorithm (1-1/e) sqrt(3)-1 upper bound (random order) 0.745 IID upper bound
Builds on: prophet inequality prophet secretary single-threshold algorithm
Closest papers by meaning
- Intrinsic Robustness of Prophet Inequality to Strategic Reward Signaling (NeurIPS 2024 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.83)
- Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems (NeurIPS 2026 · similarity 0.83)
- Stable Matching with Ties: Approximation Ratios and Learning (NeurIPS 2025 · similarity 0.82)
- Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL (NeurIPS 2024 · similarity 0.82)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.