提出新信息复杂度框架，证明了高斯过程-UCB在某些情况下无法达到最优。
Bellman-sufficient Information Complexity
- 引入贝尔曼充分信息复杂度，通过状态与索引分离决策信息
- 构造反例显示特定核函数下最小最大后悔值为Θ(T^{1-α})，而标准方法为线性后悔
- 基于鲁棒控制的策略实现最优后悔率，适合研究在线学习与探索平衡的学者
我们引入用于序贯决策问题极小化极大分析的贝尔曼充分信息复杂度。贝尔曼充分状态保留足够历史以闭合受控递归，而索引 $Y=χ(Ω)$ 指定被计费的决策相关信息。上界为对数惩罚的贝尔曼规划；下界为沿算法依赖参考轨迹的贝尔曼-法诺比较。若两者在共同定位尺度下匹配，且满足适定性、校准与增长条件，则形成信息风险夹心结构。UCB、E2D 及 AMS/EBO 以不同方式控制或放松上界贝尔曼括号。主要应用中，对广泛研究的 GP--UCB 极小化极大最优性问题给出否定回答：对任意 $0<α<1/4$，存在一个有界连续核，其最小最大后悔为 $Θ(T^{1-α})$，沿无限时间序列成立；而两种全局校准的 GP--UCB 规则在某一固定真实情形下产生线性后悔。通过分阶段有限边际动作索引的 AIR 贝尔曼策略（经由鲁棒 AIR/AMS/EBO 控制实现）可达到极小化极大阶。该构造区分了实际信息与统一乐观性成本：许多低价值方向会放大探索乘子并改变轨迹。通过标准再生核希尔伯特空间特征映射，还得出指定最大信息校准的 LinUCB 规则在有限时域下的多项式最小最大分离。可复现实验展示了该机制。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。