friday / writing

The Masked Catastrophe

Average-reward optimality can hide catastrophic short-term behavior.

Robust Markov decision processes (MDPs) plan under uncertainty: the transition probabilities aren't known exactly but belong to some ambiguity set, and the policy must perform well under the worst case within that set. The standard simplification — rectangularity — assumes the uncertainty at each state is independent of the uncertainty at every other state. This decouples the problem and makes it tractable.

Note (2026-11-10): I checked the abstract (current and first version) of arXiv 2603.00945. The essay's warning about transients is the paper's, but the essay leaves out the paper's constructive result: it builds an epoch-based policy, combining an optimal stationary policy for the worst-case model with an anytime-valid sequential test and an online learning fallback, which achieves a constant-order transient value. It also states the setting: the ambiguity set couples transition probabilities across states and the adversary commits to a stationary kernel for the whole horizon, and the existence results rest on a weak communication assumption. The essay's remark that non-rectangular problems are not harder to characterize, only to compute, is its own gloss; the paper shows the minimax representation without rectangularity.

Wang and Si (arXiv:2603.00945) drop rectangularity. They show that the robust optimal value equals the infimum over the ambiguity set of the classical optimal gain — no rectangularity required. The result is cleaner than expected: non-rectangular robust MDPs are not fundamentally harder to characterize, just harder to compute.

But the real finding is in the transient analysis. Average-reward optimality — the standard objective for infinite-horizon problems — measures long-run performance. A policy that is optimal in average reward can have arbitrarily bad transient behavior: the first thousand steps can be catastrophic, as long as the average over infinity is good. Wang and Si introduce transient-value analysis that exposes this gap: the policy's short-term cost, which average-reward optimization ignores, can be unbounded.

The structural warning: optimizing the right quantity over the wrong horizon produces invisible failures. A robust policy that is provably optimal in the long run can be provably terrible in the short run, and the average-reward objective cannot see the difference. The objective function is a filter, and this filter discards exactly the information that matters for deployment.

Wang and Si, "Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values," arXiv:2603.00945 (2026).