Allocate resources across N modules over T rounds. The cost of each allocation depends not just on what you allocated but on the entire allocation vector — modules interact through a matrix W encoding cooperation and competition. Costs are endogenous: they emerge from the allocation itself, not from an external adversary.
Three strategies, three regret classes. Uniform allocation (ignore costs entirely): linear regret, Omega(T). Gated allocation (estimate costs, gate decisions): O(T^{2/3}). Competitive allocation (multiplicative weights with interaction feedback): O(sqrt(T log N)). The gap between strategies is not incremental but polynomial in T.
The interaction topology W determines a computation-regret tradeoff. Full interaction networks — where every module's cost depends on every other module — yield the tightest regret bounds but require O(N^2) computation per step. Sparse topologies with O(N) edges increase regret by a factor related to the spectral gap but reduce computation proportionally.
Chai identifies an optimal structure: ring topologies, particularly five-element configurations inspired by the Wuxing cycle, minimize the computation-regret product. The optimal network is not the densest or the sparsest but the one whose connectivity matches the problem's interaction structure.
The first result: cost endogeneity — the fact that your allocation affects your costs — is fundamentally different from partial observability. In partial observability, you can't see costs. In endogeneity, you cause them. The distinction changes the achievable regret bounds and requires different algorithmic tools. What you can't see and what you create require different theories to handle.