Ski rental with predictions: consistency, robustness and a graded rule

A touring play needs a lighting rig. Renting costs 1 per night; buying costs $B$ , after which every night is free. The run ends on a night nobody knows in advance. Each morning the run is still on, you rent again or buy.

The example with B = 12: buying on night 12 against hindsight, for runs of 1 to 30 nights.

Before opening night the producer gives a forecast of how many nights the run will last. It may be right. It may be wildly wrong.

A rule maps the forecast to the night you buy: buy_night(forecast, B) returns a night 1, 2, 3, ..., or math.inf to never buy.

If the run lasts $d$ nights, buying on night $t$ costs $d$ when $d < t$ , and $t - 1 + B$ otherwise. Someone who knew $d$ in advance would pay $min (d, B)$ .

Consistency: the worst ratio of what you pay to what hindsight pays, over runs where the forecast was exactly right.
Robustness: the worst ratio over every forecast and every run.

Example

With $B = 12$ and the rule "buy on night $B$ whatever the forecast":

forecast	run	you pay	hindsight	ratio
20	20	11 + 12 = 23	12	1.92
3	40	23	12	1.92

Its consistency and its robustness are both $23 / 12 \approx 1.92$ .

Grading

A hidden adversary plays $B \in {5, 12, 37, 100}$ : every run up to $20 B$ with a correct forecast, and every forecast up to $20 B$ plus two huge ones, each against its worst run.
No timing decides a grade. The whole check must finish within 5 seconds.
buy_night returns a whole number at least 1, or math.inf.

Background, if you want it: Online Algorithms, rent or buy without a forecast.

The key idea

At first, only one thing about a forecast matters: does it say the run will reach $B$ nights? Say it does, and you buy on night $a$ . If the forecast is right, the run reaches night $a$ and you pay $a - 1 + B$ against $B$ , so the consistency is $1 + (a - 1) / B$ . If it is wrong, the adversary ends the run on night $a$ : you pay $a - 1 + B$ against $a$ , so the robustness is $1 + (B - 1) / a$ . Buying early is good when the forecast is right and bad when it is wrong. With $a \approx λ B$ , consistency is about $1 + λ$ and robustness about $1 + 1 / λ$ .

Part B, proved

Take any deterministic rule, even one that uses the exact forecast. Fix the forecast 1,000 and let $a$ be the night the rule buys under it. If the forecast is right, the run lasts 1,000 nights. If $a > 1000$ you pay 1,000 against 12; otherwise you pay $a + 11$ against 12. So consistency at most 1.25 forces $a \leq 4$ . Keep the forecast, and let the adversary end the run on night $a$ : you pay $a + 11$ against $a$ , a ratio of $1 + 11 / a \geq 1 + 11 / 4$ . So no rule does better than 3.75, and buying on night 4 when the forecast says long, and on night 12 otherwise, achieves it.

Part C

Buy on night $⌈ B / 2 ⌉$ when the forecast is at least $B$ , and on any night from $B$ to $2 B$ otherwise. A correct forecast below $B$ means the run ends before you buy, so you pay exactly what hindsight pays. The adversary's best run against buy night $t$ ends on night $t$ , which gives the two ratios above.

Part D: what the two numbers miss

"Buy on night $B$ when the forecast says short" passes part C. Yet at $B = 12$ , with forecast 10 and run 12, it pays 23 where part D's bound allows $1.5 \cdot 12 + 2 \cdot 2 = 22$ : a small error costs it the full penalty. Waiting until night $2 B$ keeps renting through small errors. That is the rule of Purohit, Svitkina and Kumar with $λ = 1 / 2$ : buy on night $⌈ λ B ⌉$ if the forecast says long, and on night $⌈ B / λ ⌉$ otherwise. It never pays more than $(1 + λ) O P T + η / (1 - λ)$ , where $η$ is the forecast's error. For $λ = 1 / 2$ that is part D's bound. Consistency and robustness alone could not tell these two rules apart.

Going further

Randomize. Without a forecast, a random buy night guarantees about $e / (e - 1) \approx 1.58$ against an adversary who cannot see the coin (Karlin, Manasse, McGeoch and Owicki). Purohit, Svitkina and Kumar also give a randomized rule that uses the forecast.
The trade-off is optimal. Wei and Zhang proved that no deterministic rule beats $1 + λ$ against $1 + 1 / λ$ ; part B is the discrete case of their argument.
Algorithms with predictions is now a research area, covering caching, scheduling, matching and more. Start with Mitzenmacher and Vassilvitskii's survey; papers are listed at algorithms-with-predictions.github.io.
Several forecasters. Gollapudi and Panigrahi study rent or buy with advice from several experts, which connects this problem to Multiplicative Weights.

References

A. R. Karlin, M. S. Manasse, L. A. McGeoch, S. Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica 11 (1994).
M. Purohit, Z. Svitkina, R. Kumar. Improving online algorithms via ML predictions. NeurIPS 2018.
S. Gollapudi, D. Panigrahi. Online algorithms for rent-or-buy with expert advice. ICML 2019.
A. Wei, F. Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. NeurIPS 2020.
M. Mitzenmacher, S. Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, Cambridge University Press, 2021.

The Forecast and the Lighting Rig