Bellman-sufficient Information Complexity

We develop Bellman-sufficient information complexity, a representation-level framework for the information-theoretic minimax analysis of sequential decision making. The theory covers interactive environments unfolding over long streams of experience and benchmarks all nonanticipating algorithms. A Bellman-sufficient state closes the controlled recursion, while an index Y=χ(Ω) identifies the decision-relevant information. Upper bounds arise from a log-penalized Bellman program, and lower bounds from a Bellman-Fano comparison along a reference trajectory. When the two sides exhibit matching information growth at a common localization scale, they yield an information-risk sandwich. Within this framework, UCB, E2D, and AMS/EBO arise through calibration, one-step offsets, and robust belief optimization, respectively. As a major application, we show that maximal-information calibration can make GP-UCB polynomially suboptimal in minimax regret. For every 0<α<1/4, there exists a single bounded continuous kernel whose minimax regret is Θ(T^{1-α}) along an infinite sequence of horizons. On the same problem, a finite-marginal action-index AIR Bellman policy attains this order, whereas the specified anytime GP-UCB rule incurs linear regret. This separates realized information acquisition from the cost of uniform optimism and shows why localization can be essential within the Bellman recursion.