精读笔记

Problem Setting

【Algorithmic and Minimax Complexities in Kernel Bandits】（arXiv preprint / 2026）

这篇论文不是在提出一个更强的 GP-UCB 常数改进，也不是单纯把 DEC 套到 kernel bandit 上。它实际解决的是一个理论比较问题：在 frequentist RKHS bandits 中，GP-UCB 的 log-determinant / realized information analysis 和 DEC/MAMS 的 minimax regret-information coefficient analysis 到底在衡量什么，什么时候能比较，什么时候不能比较。

关键矛盾是：GP-UCB 的 Gaussian process posterior 在 frequentist setting 里只是 algorithmic reference，不是真实数据生成 prior。它的 information gain 是沿着算法实际采样轨迹、在所选 posterior geometry 下积累的复杂度；而 DEC/MAMS 是对整个模型类的 robust offset，天然看 worst-case alternatives。前者是 algorithm-dependent / pointwise / geometry-sensitive，后者是 class-wide / minimax / adversarial-belief-sensitive。把二者都叫“信息复杂度”会掩盖它们的语义差异。

以前方法卡在两个方向：GP-UCB 方向能给可计算且常常 sharp 的 kernel-algebraic bound，但不直接解决 DEC offset optimization；DEC/MAMS 方向能给 minimax 证书，但 kernel class 上通常需要 discretization/covering，容易把原本 clean 的 log-det estimation complexity 替换成粗糙的 covering complexity。这篇论文试图把这个错位形式化。

Motivation

作者的核心动机是纠正一个常见但不精确的比较方式：用 full-class maximal information gain 或 DEC coefficient 去判断 GP-UCB 的“信息论最优性”。论文认为这类比较经常混淆了三种对象：fixed-truth expected regret、Bayesian-average regret、class-wide minimax regret。

已有路线缺的是一个共同语言。GP-UCB 的 posterior variance/log-det 是算法参考 prior 诱导出来的，不必等同于真实先验；DEC 的 coefficient 是给定 DMSO class 的 robust certificate，不关心某个具体 algorithmic prior 是否在某个 structured truth 上特别合适。作者看到的缺口是：需要一个 identity 同时容纳 posterior-reference information 和 minimax regret-information offset，并让二者的差异在同一个公式中显现。

为什么会想到 heterogeneous prior：因为 scalar ridge 把 inductive bias 隐藏了。若允许 PSD precision Γ，算法到底偏好哪些方向、惩罚哪些方向就变成可见的数学对象。这样可以构造出 hub-cloud separation：同一个 ambient class 的 worst-case/minimax 很大，但某个 prior-biased GP-UCB 在 hub subfamily 上复杂度很小。

Core Idea

核心思想可以压缩成一句：把 GP-UCB 看成“固定 algorithmic posterior reference 后，用 calibration + optimism 验证 MAIR bracket 的算法”，把 MAMS 看成“直接优化同一个 MAIR bracket 的 robust saddle-point 算法”。这样 GP-UCB 和 DEC 不再是两套无关理论，而是同一个 regret-information identity 的两种投影。

本质变化在于建模方式：Gaussian prior 不被解释为 Bayesian truth，而被解释为 algorithmic coding geometry。异质 PSD prior Γ 同时决定四件事：posterior variance、log-det information gain、truth code length θ*ᵀΓθ*、以及算法对某些方向的盲区。这个 inductive bias 是论文最重要的对象；它说明 algorithmic complexity 可以比 class-wide minimax certificate 更贴近某个实际算法在某个结构化 truth 上的表现。

和 prior 的本质区别：传统 GP-UCB 分析通常把 information gain 当成 kernel 的全局复杂度，至多区分 realized vs maximum；DEC/MAMS 则从 class-wide offset 出发。本文把“选择 posterior geometry”本身提升为算法设计维度，并强调这不是简单 regularization trick，而是改变了复杂度度量的参照系。

Method

1. Posterior-reference telescope：解决 GP posterior information 如何进入 MAIR potential 的问题。Theorem 2.1 给出 posterior density-ratio 的 telescoping identity；Gaussian reference 下 one-step mutual information 正好等于 1/2 log(1 + σ²/λ)，累加为 realized log determinant。这个步骤的作用是把 GP-UCB 的 log-det 复杂度放进 MAIR 语言。

2. Fixed-truth transfer：解决 frequentist truth 不是从 GP prior 抽样的问题。Lemma 2.3 表明固定 θ* 下 posterior likelihood-ratio 可由 realized information 加上 code length θ*ᵀΓθ*/(2λ) 控制。这是 frequentist RKHS bound 的关键桥梁：不是假设 θ* 是 Bayesian sample，而是付出相对于 algorithmic prior 的 coding cost。

3. MAIR gradient bracket：解决 GP-UCB 与 MAMS 的统一代数问题。Lemma 3.2 展开 MAIR 对 algorithmic belief μ 的梯度，得到 regret minus information minus prior-ratio 的 bracket。若 μ=ρ，得到 posterior-reference 形式；若 μ 是 MAIR maximizer，gradient term 非正，得到 MAMS/DEC 风格控制。

4. Heterogeneous GP-UCB：解决 scalar ridge 无法表达方向性 inductive bias 的问题。用 PSD precision Γ 定义 algorithmic covariance，UCB acquisition 仍是 μ+βσ，但 β 中出现 θ*ᵀΓθ* 和 realized information。核心变化是：regret bound 不只由 kernel class 决定，还由算法选择的几何和 truth 在该几何下的 code length 决定。

5. Finite-cover MAMS 与 safeguard：MAMS 提供 class-wide insurance，但要付 cover size 和 misspecification cost；safeguarded master 只是概念性地说明可以用 corral 类方法取 GP-UCB 与 MAMS 两个 base 的较好者。这里不是主要技术创新，更像为“algorithmic gain 与 minimax robustness 可兼容”提供接口。

6. Hub-cloud separation：用独立臂 diagonal kernel 构造 hub directions 与 massive cloud directions。Γ 给 cloud 很小 prior variance，使 hub truths 低 code length、低 realized complexity；但 full class 因包含 N 个 cloud alternatives，minimax 和 DEC 仍线性大。这是论文用于支撑核心论点的最清晰证据。

Key Insight / Why It Works

最核心的 insight 是：在 frequentist kernel bandit 中，GP-UCB 的 posterior 不是概率真相，而是压缩/编码 truth 的算法坐标系。一旦承认这一点，GP-UCB 的性能就应当用“truth 在该坐标系下是否便宜 + 算法实际轨迹积累了多少 log-det information”来解释，而不是只看 ambient RKHS class 的 worst-case minimax coefficient。

方法有效的原因分两层。第一层是代数层：MAIR bracket 本身允许把 regret 和 information 放在一个 offset 中；GP-UCB 通过 optimism 把 instantaneous regret 控制为 confidence width，再通过 log(1+σ²/λ) 把 squared width 转成 information increment。这解释了为什么 GP-UCB 能被塞进 MAIR 框架。第二层是几何层：Γ 改变哪些方向 variance 大、哪些方向 code length 小，从而改变算法探索优先级和 regret certificate。真正的性能增益来自 better inductive bias，而不是 scaling、retrieval、data coverage 或 test-time compute。

最可能的核心贡献是 fixed-truth posterior-reference transfer + heterogeneous-prior interpretation + hub-cloud separation 这组三件事。它们共同说明“algorithmic information can be more informative than class-wide minimax”不是口号，而是可以在同一个 DMSO/kernel bandit 实例中被数学化。

相对辅助的部分是 safeguarded master。它在概念上合理，但文中只是 meta-oracle statement，没有真正解决如何高效运行 MAMS cover、如何控制 continuous action 的 overhead、如何选择 base algorithms 的问题。它更像是防止读者误解为“GP-UCB beats DEC”的理论保险，而不是实质算法贡献。

需要直接指出：hub-cloud gain 本质上来自 prior-induced bias/localization。它不是免费泛化，也不是证明 GP-UCB 在 full class 上更优。异质 prior 把 cloud directions 变得 algorithmically expensive，因此 hub 上好、cloud 上差是设计结果。论文诚实地承认这一点；因此其 claim 应理解为 pointwise/algorithmic complexity 的重要性，而不是 minimax superiority。

Relation To Prior Work

最接近的两条线是 GP-UCB/kernel bandit regret analysis 和 DEC/MAIR/DMSO interactive learning complexity。

相对 Srinivas et al., Chowdhury-Gopalan, Vakili, Whitehouse 等 GP-UCB 路线，本文的新意不在 sharper kernel information gain estimate，而在解释 information gain 的语义：它是 algorithmic posterior reference 的 realized information，而不是自动等同于 full-class statistical complexity。Whitehouse 等改进的是 calibration coefficient；Iwazaki/Takeno-Iwazaki 强调 realized trajectory information 可能远小于 worst-case variance-reduction trajectory；本文把这些观察放到 MAIR/DEC 框架里。

相对 Foster et al. 的 DEC/E2D 和 Xu-Zeevi 的 MAIR/MAMS，本文不是发明 MAIR identity，而是把 GP-UCB 解释为满足 MAIR gradient-error condition 的具体 calibrated algorithm。MAMS 的 saddle-point部分基本沿用已有思想；实质新增是说明 kernel finite-cover MAMS 与 GP-UCB log-det route 的复杂度差异，以及用 heterogeneous prior 构造 separation。

看似新的地方：heterogeneous PSD prior 可以被视为 generalized ridge / anisotropic kernel 的自然扩展，不是从零开始的新算法。但实质创新在于把它作为“算法复杂度参照系”来使用，并把 θ*ᵀΓθ*、I_T,Γ、DEC/minimax gap 放在同一讨论中。

技术谱系上，这篇属于 information-ratio/DEC 与 kernel bandit regret theory 的桥接论文，偏 conceptual/theoretical unification，而不是 benchmark-driven algorithm paper。

Dataset / Evaluation

论文没有真正意义上的实验数据集或数值评估。第 5.2 节给的是 experimental protocol：Bayesian GP sample paths、frequentist RKHS functions、class-wide stress test，建议比较 regret、realized information、local r_t²/g_t ratios、MAMS/DEC envelope 等。

这类 evaluation proposal 与论文核心 claim 是匹配的：作者明确说不应只比较 regret，而应同时画 algorithmic、Bayesian、minimax 三类曲线。但由于没有实际实验，不能判断 heterogeneous GP-UCB 或 safeguarded master 在真实 BO benchmarks、Matérn/SE kernels、continuous domains 上是否有实用收益。

hub-cloud construction 是理论 stress test，不是现实任务。它很好地验证“full-class minimax/DEC 会被 cloud alternatives 拉高，而 prior-biased GP-UCB 可在 hub truths 上更好”这个 claim；但它不能证明常见 kernel optimization 场景中 DEC pessimism 总是主要瓶颈。文中未充分说明在非人工构造 kernel 上如何选择 Γ，也没有展示 MAMS finite-cover 的计算可行性。

Limitation

1. Γ 的来源是最大未解问题。论文强调 heterogeneous prior 是算法 inductive bias，但没有给出 principled learning/selection mechanism。若 Γ 选错，GP-UCB 在 cloud/high-complexity truths 上会系统性失败；这不是分析松的问题，而是算法设计本身的 tradeoff。

2. MAMS 的 kernel extension 仍然不 scalable。finite ε-net 带来 log|M_ε|、2εT、χ_εT/η 等项，这正是作者批评 DEC route 的地方。论文没有真正消除这个成本，只是把它作为 robust comparator。

3. Safeguarded master 停留在 meta-oracle 层面。实际 corralling 两个 bandit algorithms 在 partial feedback 下的 overhead、稳定性、continuous action 兼容性都没有展开。这里的增益来源不清，更像概念性组合而非可部署算法。

4. Hub-cloud separation 是清晰但高度构造化的。它证明了存在性 gap，但不能直接推出 Matérn、SE 或实际 overparameterized kernel models 中也会出现同量级分离。若要支撑更强 claim，需要真实或自然分布下的 localized complexity evidence。

5. GP-UCB 的 coefficient 问题没有被解决。论文把 realized information 和 MAIR coefficient 分开是对的，但 heterogeneous GP-UCB 仍靠 confidence width/β 控制 regret，并没有像 MAMS 那样优化 offset。未来真正的算法进步应发生在 coefficient-aware kernel acquisition，而不是仅换一个 Γ。

6. 这不是 scaling paper，也不是 data-driven gain。论文的 gain 来自表示几何/inductive bias。若读成“用更大模型/更多数据能解决 minimax pessimism”，就是误读。

Takeaway

• 1. kernel bandit 的“信息复杂度”至少要拆成两类：algorithmic realized information 和 class-wide minimax/DEC coefficient。
• 二者都重要，但不能互相替代。
• 2. GP prior 在 frequentist RKHS bandit 中应被视为 coding geometry。
• 这个视角可迁移到其他 sequential learning：算法选择的 reference distribution 本身就是 inductive bias，不只是分析工具。

一句话总结

这篇论文把 GP-UCB 的 realized posterior-geometry complexity 和 DEC/MAMS 的 class-wide minimax complexity 放进同一个 MAIR 框架，真正贡献是澄清二者衡量的问题不同，并用 heterogeneous prior 证明 algorithmic inductive bias 可以产生与 full-class DEC 证书分离的点态优势。