[2603.02491] What Capable Agents Must Know: Selection Theorems for Robust Decision-Making under Uncertainty

Computer Science > Machine Learning arXiv:2603.02491 (cs) [Submitted on 3 Mar 2026] Title:What Capable Agents Must Know: Selection Theorems for Robust Decision-Making under Uncertainty Authors:Aran Nayebi View a PDF of the paper titled What Capable Agents Must Know: Selection Theorems for Robust Decision-Making under Uncertainty, by Aran Nayebi View PDF HTML (experimental) Abstract:As artificial agents become increasingly capable, what internal structure is *necessary* for an agent to act competently under uncertainty? Classical results show that optimal control can be *implemented* using belief states or world models, but not that such representations are required. We prove quantitative "selection theorems" showing that low *average-case regret* on structured families of action-conditioned prediction tasks forces an agent to implement a predictive, structured internal state. Our results cover stochastic policies, partial observability, and evaluation under task distributions, without assuming optimality, determinism, or access to an explicit model. Technically, we reduce predictive modeling to binary "betting" decisions and show that regret bounds limit probability mass on suboptimal bets, enforcing the predictive distinctions needed to separate high-margin outcomes. In fully observed settings, this yields approximate recovery of the interventional transition kernel; under partial observability, it implies necessity of belief-like memory and predictive state, addressing a...