Auditing Rectangularization in Robust MDPs: Selective Recoupling of Shared Transition Uncertainty

Robust MDPs are often made tractable by assuming transition uncertainty is independent across time, states, and actions. Under this rectangular assumption, an adversary chooses the worst transition at each time-state-action triple, enabling Bellman recursion. This can be overly pessimistic when transitions share an episode-persistent factor, because locally adverse choices may not be jointly realizable. We study the intervening design problem: which declared transition dependencies yield the largest certified reduction when at most $k$ modeling blocks are recoupled? For a fixed policy and transitions affine in shared scalar factors, we derive an exact decomposition of the rectangularization gap into nonnegative defects at reachable rows. These defects yield computable certificates and a Global-Balance rule for jointly selecting dependencies, including complementarities between groups. We also provide a mixed-integer formulation, approximation and selection guarantees, and finite-data certificates valid after data-dependent selection. In generated routing and queue systems with binary persistent regimes, Global Balance captures cross-block certificate gains on 47.3% of policy-subset pairs. Restoring eight of ten blocks reduces held-out candidate-menu regret relative to full release, while an incorrect sharing map reverses the benefit of full recoupling. With six independent factors, certificate-selected blocks recover 89.5% of the full recoupling gain using 4 of the 64 conditional evaluations required by full recoupling.