Online Algorithms, in depth: competitive ratios, ski rental, paging, randomisation and learning-augmented decisions

The model and the competitive ratio

Formally, an input is a sequence of requests σ = r1, r2, ..., rn. The online algorithm ALG processes r_i knowing only r1..r_i and its own past decisions. The offline optimum OPT sees the whole sequence and pays the least possible cost. For a minimisation problem, ALG is c-competitive if there is a constant a such that, for every sequence,

ALG(σ) <= c * OPT(σ) + a

If the inequality holds with a = 0, ALG is strictly c-competitive. For maximisation problems, such as matching, the ratio is usually written the other way round: ALG gets at least a fraction of OPT, for example 1/2 or 1 − 1/e.

Two things make this definition demanding. First, it is a worst case over all inputs, so one bad sequence settles the ratio. Second, OPT is allowed hindsight, so the ratio isolates exactly the cost of not knowing the future. It says nothing about computation: an online algorithm may run a slow procedure per request, and OPT may be NP-hard to compute. Competitive analysis is about information, not time.

It is useful to picture an adversary who knows your algorithm and builds the input to hurt it. For deterministic algorithms the adversary can simulate you exactly, so it always knows what you will do next. That is why deterministic lower bounds are often simple constructions: request whatever the algorithm just gave up.

Ski rental: the rent-or-buy template

Ski rental is the smallest problem that shows the whole idea. Renting skis costs 1 per day. Buying costs B. You do not know how many days you will ski; one morning you simply stop. Each morning you have not yet bought, you decide whether to rent again or buy.

With hindsight the answer is easy: if you skied d days, OPT pays min(d, B). Online, any deterministic strategy is just a day t on which you buy if you are still skiing. The adversary stops you the day after you buy. If you buy on day t, you pay (t − 1) + B against OPT's min(t, B).

Break-even is the strategy: rent for B − 1 days, buy on day B. If you stop before day B you paid exactly what OPT paid. If you reach day B you pay (B − 1) + B = 2B − 1 while OPT pays B, so the ratio is 2 − 1/B. Buying any earlier or later makes the worst case larger, and no deterministic strategy can do better: this ratio is tight.

The same structure, paying a small recurring cost until it adds up to a large one-off cost, appears everywhere: spin-then-block locks (spin for about as long as a context switch would cost), keeping an idle server or disk powered versus shutting it down, on-demand versus reserved cloud capacity, and keeping a TCP connection open versus reconnecting. Each is a ski rental problem with different constants.

Worked example: B = 10

Take B = 10. The script below simulates every stopping day up to a long horizon and reports the worst ratio for several buy days.

def ski_cost(days_skied, buy_day, B):
    """Rent at 1 per day until buy_day, then buy for B. buy_day=None means never buy."""
    if buy_day is None or days_skied < buy_day:
        return days_skied
    return (buy_day - 1) + B

def opt_cost(days_skied, B):
    return min(days_skied, B)

def worst_ratio(buy_day, B, horizon=200):
    return max(ski_cost(d, buy_day, B) / opt_cost(d, B) for d in range(1, horizon))

for buy_day in (1, 5, 10, 15, 20, None):
    print(buy_day, round(worst_ratio(buy_day, 10), 3))

Those are the actual outputs. Notice the shape: buying too early loses to short seasons, buying too late loses to long ones, and break-even balances the two regrets. That balancing argument is the most reusable idea in the field.

Randomisation and adversary models

A deterministic algorithm loses because the adversary knows the buy day. If you choose the buy day at random, an oblivious adversary (one who fixes the sequence in advance, knowing your algorithm but not your coin flips) can no longer stop you the day after you buy. The ratio is then measured on expected cost. For ski rental, Karlin and co-authors showed that buying on day i ≤ B with probability proportional to ((B − 1)/B)^(B − i) gives an expected ratio that approaches e/(e − 1) ≈ 1.58 as B grows, and that this is optimal for randomised algorithms.

import random

def randomized_buy_day(B, rng=random):
    weights = [((B - 1) / B) ** (B - i) for i in range(1, B + 1)]
    return rng.choices(range(1, B + 1), weights=weights)[0]

A Monte Carlo run of that sampler against every stopping day at B = 10 measured a worst expected ratio of about 1.58, against 1.9 for break-even.

Adversary strength matters. Against an adaptive online adversary, which sees your past random choices before choosing the next request, randomisation helps less; against an adaptive offline adversary it provably cannot beat the best deterministic ratio. In practice, if inputs can react to your behaviour (an attacker probing a cache, a client gaming a rate limiter), assume the stronger adversary.

Paging: LRU, FIFO and Belady

Paging is the classic online problem with direct engineering impact. A cache holds k pages. Each request either hits or faults; on a fault with a full cache you must evict a page. Cost is the number of faults.

The offline optimum is Belady's MIN: evict the page whose next use is furthest in the future. Sleator and Tarjan showed that LRU and FIFO are both k-competitive, and that no deterministic algorithm does better than k. The lower bound is easy to see with k + 1 distinct pages: the adversary always requests the one page not in the cache, so every request faults, while MIN faults at most once every k requests.

import math
from collections import OrderedDict, deque

def faults_lru(seq, k):
    cache, faults = OrderedDict(), 0
    for p in seq:
        if p in cache:
            cache.move_to_end(p)
            continue
        faults += 1
        if len(cache) == k:
            cache.popitem(last=False)          # least recently used
        cache[p] = True
    return faults

def faults_opt(seq, k):
    """Belady's MIN: evict the page whose next use is furthest away (offline)."""
    cache, faults = set(), 0
    for i, p in enumerate(seq):
        if p in cache:
            continue
        faults += 1
        if len(cache) == k:
            def next_use(q):
                for j in range(i + 1, len(seq)):
                    if seq[j] == q:
                        return j
                return math.inf
            cache.discard(max(cache, key=next_use))
        cache.add(p)
    return faults

seq = [1, 2, 3, 4] * 25        # 100 requests cycling over k + 1 pages
print(faults_lru(seq, 3), faults_opt(seq, 3))   # 100 36

On the cyclic sequence LRU faults on all 100 requests while MIN faults 36 times. That cyclic scan is not an exotic input: a loop over an array slightly larger than the cache does exactly this, which is why database buffer pools and CPU caches add scan resistance.

Two refinements explain why LRU is still good in practice. Randomised marking (evict a random unmarked page; when all are marked, start a new phase) is about 2·H_k-competitive, where H_k is the k-th harmonic number, roughly ln k, and H_k is a lower bound for any randomised algorithm. On the sequence above it averaged about 63 faults. Resource augmentation compares LRU with k pages to OPT with h < k pages; the ratio becomes k/(k − h + 1), so LRU with twice OPT's memory is within a factor of about 2. Real request streams also have locality, which worst-case analysis ignores.

Other classic online problems

Online matching is the model for ad allocation, where impressions arrive one at a time and advertisers have budgets. The secretary problem is the model for stopping rules under random arrival order, which is a weaker and often more realistic adversary than worst case.

Algorithms with predictions

Worst-case ratios are pessimistic because real systems usually have a forecast: yesterday's traffic, a model's estimate of the session length, a hint from the application. Learning-augmented online algorithms take a prediction as extra input and aim for two properties at once: consistency (near-optimal when the prediction is good) and robustness (a bounded ratio however bad it is).

For ski rental with a predicted number of days y, Purohit, Svitkina and Kumar use a trust parameter λ in (0, 1]: if the prediction says you will ski at least B days, buy early, on day about λB; otherwise buy late, on day about B/λ. With λ small you trust the forecast and get close to 1 when it is right; the guaranteed worst case is about 1 + 1/λ. Setting λ = 1 recovers break-even. The pattern carries over to caching, scheduling and many other problems: start from a robust online rule, and let predictions move the decision only as far as the robustness budget allows.

Failure modes

• Optimising the average when the tail matters. A policy tuned on typical traces can be unboundedly bad on an adversarial or shifted one, such as never buying, or a cache with no scan resistance.
• Wrong cost constants. The break-even point is the ratio of the costs. If a context switch costs 5 µs on one machine and 40 µs on another, a hard-coded spin time is wrong on one of them. Measure the one-off cost and derive the threshold from it.
• Assuming an oblivious adversary. Randomised guarantees hold only if the input cannot observe your coin flips. A client that can time cache hits can adapt to them.
• Ignoring that OPT is a yardstick, not a goal. A competitive ratio of k for LRU sounds terrible, yet LRU performs well on real workloads with locality. Use the ratio to rule out catastrophic policies, then use traces to choose among the safe ones.
• Trusting predictions without a fallback. A learned policy with no robust floor fails badly exactly when the distribution shifts, which is when you most need it to behave.

Applying it in production

Turn the theory into a routine. Identify each place a system commits to a decision before knowing the future: eviction, provisioning, retries, timeouts, connection pooling, batching. Write down the recurring cost and the one-off cost in the same units. Pick a policy with a known bound, often break-even, then replay recorded traces through both the policy and an offline optimum (Belady for caches, a dynamic program for provisioning) so you can see the gap on real data, not only the worst case.

Log enough to compute OPT after the fact: the request sequence, or at least inter-arrival times and durations. Alert on the empirical ratio drifting up, which usually means the workload changed shape. If you add a learned predictor, keep the robust rule as the fallback and cap how far the prediction can move the threshold.

What to do next

1. Run the ski rental script with your own B and confirm the break-even ratio is 2 − 1/B.
2. Replay a real cache trace through LRU, FIFO and Belady's MIN, and record the fault gap.
3. List three rent-or-buy decisions in your system and write the cost of each side in the same unit.
4. Replace one hard-coded threshold (a spin time, an idle timeout) with one derived from measured costs.
5. Decide which adversary model applies: can the input observe and react to your choices?
6. If you have a forecast, prototype a λ-style policy and measure consistency and robustness on traces.

Related reading on this site: LRU caches and ARC for eviction policies in practice, LFU for frequency-based eviction, bipartite matching for the offline problem behind online matching, and reservoir sampling for another one-pass decision rule.