2026/06/09 by Yunbei Xu · 1 voice · 1 citation
#cs.LG #cond-mat.stat-mech #cs.IT #math.IT #math.OC #math.ST #stat.TH
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 give a negative resolution to a canonical, widely studied form of the GP-UCB minimax-optimality question. For every 0<α<1/4, there exists a single bounded continuous kernel whose minimax regret is Θ(T1-α) along an infinite sequence of horizons. On the same problem, a finite-marginal action-index AIR Bellman policy attains this order, whereas both an anytime maximal-information GP-UCB rule and the unit-ball specialization of the original RKHS GP-UCB exploration schedule incur linear regret. This separates realized information acquisition from the cost of uniform optimism and explains why localization can be essential within the Bellman recursion. A reproducible finite-scale experiment illustrates the predicted cloud-exploration mechanism for both headline GP-UCB calibrations.