# Bellman-sufficient Information Complexity

arXiv: https://arxiv.org/abs/2606.11171 · HTML: https://mlsanity.com/paper/2606.11171/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 9 Jun 2026.

## Builds on (most cited first, 7 of 7)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [On the Suboptimality of GP-UCB under Polynomial Effective Optimism](https://mlsanity.com/paper/2312.01386/) (2023)
- [Pointwise Generalization in Deep Neural Networks](https://mlsanity.com/paper/2605.18598/) (2026)
- [Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation](https://mlsanity.com/paper/2606.07931/) (2026)
- [Truncated LinUCB for Stochastic Linear Bandits](https://mlsanity.com/paper/2202.11735/) (2022)

## Built on by (most cited first, 1 of 1)

- [Local Search with Correlated Randomness](https://mlsanity.com/paper/2607.17469/) (2026)

## Abstract (arXiv)

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index Y=chi(Omega) specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every 0<α<1/4, we construct one bounded continuous kernel whose minimax regret is Theta(T1-α) along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.