Heavy-Tailed Durations

Heavy-tailed durations

A warehouse robot drives 10 cells to a shelf, and each step costs 1. Each move jams with probability 0.05. A jam lasts k steps, where P(k) is proportional to k^−1.5 for k = 1, …, 100. This truncated power law makes most jams short and a small number very long.

Model

State: (cell, remaining jam steps), 1,011 states in total.
Action: a single action, drive.
Transitions: when the robot is not jammed, it advances with probability 0.95, or enters a jam of length k with probability 0.05 · P(k). A jam decreases by one step per time step.
Terminal state: (10, 0). Reward −1 per step. Discount factor: 1.

With E[k] = 7.704, the expected cost has a closed form:

E[steps per cell] = (1 + p E[k]) / (1 − p)
V(start)          = −10 (1 + 0.05 · 7.704) / 0.95 = −14.5812

import aniate as an
from warehouse import RealRobot, closed_form, warehouse_robot

m, ks, pk = warehouse_robot()
m.initial @ m.evaluate(None)          # -14.5812, equal to closed_form() within a relative error of 1e-10

runs = an.simulate(m, None, episodes=20_000, seed=2)
runs.mean_return                      # -14.568, standard error 0.087

warehouse_robot(leak=0.03)            # raises ValueError with code row_sum for state (0, 0), action drive
an.check(m, env=RealRobot(p=0.10))    # fails with transition_frequency and return_mismatch

Properties demonstrated

Heavy tails. The median trip contains no jam and takes 10 steps. Occasional long jams raise the mean to 14.6 steps. The excess kurtosis of the return is approximately 25, compared with 0 for a normal distribution.
Constant martingale mean. The process M_t = G_<t + V(s_t) has mean −14.58 at every step. This holds when the model's values are correct. The heavy tail widens the confidence band without changing the mean.
Rejection of invalid models. When 3% of the jam distribution's probability mass is removed, construction fails and the error names the affected state and action.
Detection of an incorrect simulator. RealRobot(p=0.10) jams twice as often as the model specifies. check reports the discrepancy in transition frequencies and in the mean return.

Tests

pytest tests/heavy_tail

test	property verified
`test_matches_closed_form_and_its_martingale_is_flat`	the exact value equals the closed form; the excess kurtosis exceeds 10; the median exceeds the mean; the martingale mean lies within 5 standard errors of the value at every step
`test_leaky_jam_distribution_is_refused_and_a_wrong_robot_is_caught`	`leak=0.03` raises `row_sum` for `(0, 0) / drive`; `check` reports `transition_frequency` for the incorrect simulator

Plots

python tests/heavy_tail/plot.py

file	content
`tail.pdf`	P(trip longer than t) on logarithmic axes for 200,000 simulated trips, the exact distribution, and a normal distribution with the same mean and standard deviation
`overview.pdf`	for 20,000 trips: the return distribution, the running mean, the accumulated cost, and the value martingale

P(trip longer than t) on logarithmic axes for 200,000 simulated trips, the exact distribution, and a normal distribution with the same mean and standard deviation.

For 20,000 trips: the return distribution, the running mean, the accumulated cost, and the value martingale.

[View the source on GitHub]