精读笔记
Problem Setting
论文标题：MINTS: Minimalist Thompson Sampling（arXiv preprint / 2026-06-02）。
这篇论文实际处理的是结构化 stochastic optimization，重点落在 multi-armed bandits with mean constraints。问题不是“如何再设计一个 bandit 算法”，而是：当可行参数空间 Θ 带有复杂结构约束，例如 unimodality、Lipschitz、多个 shape constraints 叠加时，如何做 Thompson-style exploration 而不需要对整个 θ 建 Bayesian model。
核心困难在于 Bayesian TS 的 belief state 通常是 full posterior over θ。结构约束越复杂，posterior 越难指定、越难采样；尤其是 Lipschitz graph bandit 这类 polyhedral constrained mean space，完整 posterior sampling 会退化成高维受限采样问题。频率派结构化 bandit 可以绕开 full posterior，但通常需要针对每种结构手工推导 exploration rule 或 tracking rule，泛化性弱。
因此关键矛盾是：结构信息最自然的表达形式是硬约束 Θ，但 Bayesian 决策最自然的表达形式是概率模型；两者之间存在建模与计算错配。MINTS 的切入点是把 belief 的对象从“完整问题实例”降维到“最优位置”。
Motivation
已有路线不够的地方很具体：标准 TS 在结构化 bandit 中要求一个完整 prior p(θ)，并且每轮要从 p(θ | D_t, θ ∈ Θ) 中采样；但很多结构先验并不是概率先验，而是可行性约束。把 hard constraints 人工转成 generative prior 往往既不自然，也不稳定，还可能引入不必要的 modeling bias。
作者的核心观察是：sequential decision 的动作选择只需要 posterior probability of being optimal，而不一定需要 posterior distribution of all parameters。也就是说，TS 真正用到的是 P(x 是最优 | data)，完整 θ posterior 只是传统 Bayesian 框架下生成这个概率的一种路径，不是必要路径。
关键缺口因此是一个“optimizer-level Bayesian update”：既保留 probability matching 的自适应探索，又避免对 nuisance parameters 建先验和采样。profile likelihood 正好提供了一个统计上已有的工具：对 composite hypothesis H_x = {θ: x optimal}，用 constrained maximum likelihood 衡量该假设对数据的解释能力。
Core Idea
MINTS 的核心思想是 minimalist Bayes：只在 optimizer x* 上放 prior，把所有非目标参数作为 nuisance variables，通过 profile likelihood 消掉。对每个候选 arm j，定义 Θ_j = {θ ∈ Θ: j 是 θ 下的最优 arm}，然后计算 \bar L(j; D_t)=sup_{θ∈Θ_j} L(θ;D_t)。最后用 \bar L(j;D_t)Q_0(j) 归一化得到 generalized posterior，并从中采样下一步 arm。
这改变了建模方式：传统 TS 是“先对完整 θ 建 posterior，再诱导 optimizer distribution”；MINTS 是“直接对 optimizer 建 generalized posterior，并用 Θ_j 上的 profile likelihood 汇聚 nuisance uncertainty”。它引入的 inductive bias 是：一个 arm 的 posterior mass 只取决于“是否存在一个满足结构约束且让该 arm 最优的参数解释数据得足够好”，而不是依赖对所有可行 θ 的概率体积积分。
这个 bias 很关键。它让结构约束以几何可行集的形式进入探索机制：如果某个 arm 想成为最优必须同时扭曲邻近 arm 或相关 arm 的均值，那么 profile loss 会变大，posterior mass 自动下降；如果结构允许只局部改变某个 arm 就解释为最优，则它仍会得到探索。换句话说，信息流从“全参数 posterior sampling”重组为“每个最优性假设的最小证伪代价”。
Method
1. Optimizer-level prior：解决 full prior 难指定的问题。prior 只定义在 X 或 arms 上，表达“哪个决策最优”的初始信念。这不是完整 Bayesian model，而是有意丢掉 nuisance uncertainty 的低维 belief。
2. Profile likelihood over optimality hypotheses：解决结构约束如何进入 posterior update 的问题。每个 arm j 对应 composite hypothesis Θ_j。MINTS 不积分 Θ_j 内所有 θ，而是取最大 likelihood，即寻找“让 j 成为最优且最能解释数据”的参数。这一步把统计更新转成 constrained optimization。
3. Generalized posterior：解决如何恢复 TS 的 probability matching。更新公式形式上类似 Bayes rule，但 likelihood 换成 profile likelihood。它不是严格的 Bayesian posterior；更接近 generalized Bayes / exponential weights over hypotheses。
4. Gaussian likelihood instantiation：在 bandit mean constraints 下，profile likelihood 等价于加权最小二乘投影：Λ(j,D_t)=inf_{θ∈Θ_j} 1/2 ∑_k N_k(\hat μ_k-θ_k)^2。若 Θ_j convex，则每个 posterior mass 可通过凸优化得到。核心变化是 sampling cost 变成 K 个 projection / constrained regression 问题。
5. Thompson sampling action rule：仍按 generalized posterior 抽 arm。这部分不是创新，重要的是 posterior mass 的来源变了：它来自结构约束下的 likelihood geometry，而不是 full posterior volume。
Key Insight / Why It Works
MINTS 真正有效的原因不是“Bayesian”本身，而是 profile loss Λ(j,D_t) 对 suboptimal arm 的增长速度恰好编码了 regret lower bound 中的信息代价。一个 suboptimal arm j 若要继续被认为可能最优，必须存在某个 θ∈Θ_j 贴近 empirical means。随着 j 被采样，其 empirical mean 趋近真实低均值，把它抬成最优需要付出约 N_j Δ_j^2/2 的 quadratic loss，因此 posterior mass 按 exp(-N_j Δ_j^2/2) 衰减。TS 的随机采样自然会把 N_j 调到约 2 log T / Δ_j^2，这就是 Lai–Robbins 常数的来源。
结构自适应的关键也在这里。对于 unimodal constraints，远离最优 arm 的 suboptimal arms 不需要单独探索到 Lai–Robbins 级别，因为要让它们成为 mode，必须同时穿过最优 arm 附近的邻居约束。邻居 arm 的探索已经提供了证伪远端 arm 的证据；profile likelihood 会把这种几何耦合反映到 Λ(j,D_t) 里。因此 MINTS 自动只为 immediate neighbors 付 asymptotic exploration cost。
最核心贡献是“用最优性假设的 profile likelihood 替代 full posterior”。这既是算法机制，也是理论机制。它不是 scaling，不是 data coverage，也不是 benchmark trick；它是更合适的 inductive bias：把结构化 bandit 的学习问题表达为一组 alternative-to-optimality hypotheses 的最小证伪代价。
但也要注意，profile likelihood 使用的是 supremum 而不是 integral，因此它更偏 optimistic / GLR-style。它忽略 hypothesis set 的 volume 信息，这在 finite-arm asymptotics 中不伤 leading constant，但在连续、高维或弱识别问题中可能导致 posterior calibration 很差。所谓 generalized posterior 不是概率模型意义上的 posterior，这一点不能被 Bayesian 术语掩盖。
理论中的辅助部分包括 lazy updates、warm start、convex optimization tractability 等，这些更偏 engineering。真正推动 regret 常数的是 profile loss 的几何，而不是这些实现技巧。
Relation To Prior Work
最接近的谱系有三条：标准 Thompson sampling、结构化 bandit 的最小探索 / lower-bound tracking 方法、以及 profile likelihood / generalized Bayes。
相对标准 TS，MINTS 的本质差异是 posterior 的对象变了。标准 TS 是 prior over θ → posterior over θ → induced distribution over argmax；MINTS 是 prior over argmax → profile likelihood update。它不是简单换一个 prior，而是取消了完整参数模型。
相对 structured bandit algorithms，如 OSUB、OSSB、UTS、Combes et al. 的 minimal exploration 方法，MINTS 的差异是不用为每个结构显式设计 tracking rule。结构只通过 Θ_j 的 constrained optimization 进入算法。因此它更像一个通用 template，而不是某个 unimodal/Lipschitz 特化算法。
相对 Souza et al. 这类 “prior for the optimum” 工作，MINTS 的关键新增是 profile likelihood：不是在 full Bayesian model 上额外加 optimum prior，而是直接避免 nuisance parameter prior。这个点是实质创新。
看似新的地方中，generalized posterior / exponential weights over hypotheses 并不新；profile likelihood 和 GLR 也不新。真正的新组合是把“最优 arm 是 composite hypothesis”这件事系统用于 partial-feedback bandit，并证明它在 regret 常数上不会丢失、还可结构自适应。
Dataset / Evaluation
实验部分相对薄，主要是一个 K=12 的 Gaussian unimodal bandit，比较 unstructured MINTS/UCB/TS 与 structured MINTS/OSUB/UTS/OSSB。它验证了两个有限 claim：一是 MINTS 在 unstructured 情况下没有明显崩；二是在 unimodal 情况下 profile-likelihood posterior 的确能利用结构，且比若干基于点估计最优 arm 的算法更稳。
但 evaluation 覆盖范围不足以支撑“general stochastic optimization under structural constraints”的广泛 claim。没有 Lipschitz graph、多约束叠加、大 K、高维结构、连续 action space、真实应用或非 Gaussian heavy-tail 场景。实验更像 sanity check，而不是系统验证 scalability。
benchmark 设计与理论主张高度一致：Gaussian rewards、unimodal means、有限 arms。这有利于展示理论机制，但也意味着实验没有真正测试 profile likelihood 在复杂 Θ 上的计算瓶颈。文中提到 lazy update / warm-start，但没有严肃评估优化开销随 K、constraints、graph density 的增长。因此 computation claim 仍部分未充分说明。
Limitation
1. 方法把采样难题转移成优化难题。MINTS 避免了 high-dimensional constrained posterior sampling，但每轮需要对每个候选 optimizer 解 profile likelihood。若 Θ_j 不是凸的、数量巨大、或 X 连续高维，这个优势会迅速消失。
2. 适用范围依赖“decision space 简单、parameter space 复杂”。作者自己也承认 combinatorial bandit 这类 X 本身复杂的问题不适合。更一般地，只要 optimizer posterior 不能低维枚举，MINTS 的 minimalist advantage 就不明显。
3. generalized posterior 不是 calibrated Bayesian posterior。profile likelihood 用 supremum 忽略 volume 和 prior density over nuisance parameters；在 finite-arm regret leading constant 上可以成立，但在 uncertainty quantification、risk-sensitive decisions、continuous optimization 中可能过度自信。文中未充分说明这种 miscalibration 的代价。
4. 理论主要集中在 mean-constrained finite-arm bandits。非渐近结构化 regret 没有给出 sharp general result；asymptotic expected regret 也未解决。almost-sure regret 常数很强，但不等价于 expected regret sharpness。
5. misspecification 问题只被部分处理。理论允许 rewards 非 Gaussian，但算法使用 Gaussian likelihood；在 finite variance / sub-Gaussian 条件下 regret 可控。然而对更复杂 feedback model、heteroscedasticity、heavy-tail 或 objective not equal to mean 的场景，profile likelihood 的鲁棒性未充分说明。
6. 实验规模不足。所谓 scalability 主要是论证层面的：convex optimization 比 constrained MCMC 更容易。但没有系统 wall-clock、large K、dense graph、nonconvex constraints 对比。因此计算增益来源仍可能部分是 problem size 小，而不是机制天然 scalable。
Takeaway
- 1. 最值得迁移的 insight 是：在 sequential decision 中，belief state 不必总是 full parameter posterior；如果决策只依赖某个低维 functional，例如 optimizer、best policy、active constraint，可以直接对该 functional 做 generalized posterior。
- 2. profile likelihood 是把 hard structural constraints 接入 Bayesian-style exploration 的有效接口。
- 它把“结构能排除哪些 alternatives”转化为 profile loss 的增长率，从而自动影响探索分配。
- 3. MINTS 给 structured bandit 提供了一种介于 Bayesian TS 和 frequentist GLR/tracking 之间的路线：保留 TS 的随机化和简单 action rule，但用 frequentist profile likelihood 计算证据。
一句话总结
MINTS 是一种把 Thompson sampling 从 full-parameter Bayesian posterior 改造成 optimizer-level profile-likelihood posterior 的结构化 bandit 方法，真正贡献在于用最优性假设的几何证伪代价实现结构自适应探索。