Bellman-sufficient Information Complexity
Abstract
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=χ(Ω) 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 Θ(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.
Related
- Transparency Is Necessary but Not Sufficient for Trust: Information Leakage and Procedural Overfitting in Supervised Machine Learning for Psychology
- Task-Sufficient Contraction: Source Selection for Machine Information Interfaces
- The optimal information complexity of VC learning
- Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
- Constant-Loss Round-Preserving Direct Sums for Information Complexity
BibTeX
@misc{xu2026bellmansufficient,
title = {{Bellman-sufficient Information Complexity}},
author = {Yunbei Xu},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2606.11171},
eprint = {2606.11171},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.11171},
}
RIS
TY - UNPB
TI - Bellman-sufficient Information Complexity
AU - Yunbei Xu
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2606.11171
UR - https://arxiv.org/abs/2606.11171
AB - 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=χ(Ω) 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 Θ(T^1−α) 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.
ER -