The Six Primitives of Adaptation: Necessity Proofs and Regret Bounds

What computational primitives are necessary for robust adaptation? We prove that six are indispensable: objective specification, breakpoint identification, global attraction, minimal intervention, feasibility projection, and feedback adaptation. For each primitive, we construct environments where any algorithm lacking it suffers Ω(T) regret (or Ω(√T log T) for minimal intervention) within a broad class of challenging partially observable, non-stationary environments. These primitives are computationally independent under standard complexity assumptions, yet we provide a concrete algorithm that integrates all six and achieves Õ(√T) regret under mild conditions. This work establishes a unified framework for analyzing adaptive systems and offers principled guidance for building robust AI.