如果你搞模型评估设计，这篇理论文章用严格上下界讲清楚了交互测试比固定测试省多少查询：最多二次方，不是指数级。
这篇论文研究模型评估中测试选择策略：固定全部测试还是根据已有回答动态选择后续测试。作者在有限结果空间 |X|=N 的条件查询模型下证明，两类分布可区分当且仅当它们的成对条件概率存在正分离；若分离为零，任意有限查询预算下最坏误差恰为 1/2。对任意 T 次自适应策略和 ρ∈(0,1)，他们构造了一个非自适应随机程序，只需预先选择 O(N^2(T+log(1/ρ))) 对查询，模拟记录与自适应记录的总变差距离不超过 ρ。匹配下界给出常数自适应查询复杂度与 Ω_ε(N^2) 非自适应复杂度，因此最坏情况自适应优势为 Θ_ε(N^2)。结论是交互最多带来二次方查询减少，而非指数级优势。
Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
Model evaluations may fix all tests before observing any responses or select later tests using earlier responses. We study this choice in a conditional-query model on a finite outcome space $\mathcal{X}$ with $|\mathcal{X}|=N$. We first ask which pairs of distribution classes can be reliably distinguished. We then ask how many additional queries are required to match an adaptive tester when all queried events must be fixed in advance. We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities. When this separation is zero, the optimal worst-case error is exactly $1/2$ at every finite query budget. For any $T$-query adaptive policy and any $ρ\in (0,1)$, we construct a randomized non-adaptive procedure using $O(N^2(T + \log(1/ρ)))$ pair queries chosen before any response is observed. Its simulated transcript is within $ρ$ in total variation of the adaptive transcript, uniformly over all distributions in the model. We also construct a matching family with constant adaptive query complexity and $Ω_\varepsilon(N^2)$ non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is $Θ_\varepsilon(N^2)$. Thus interaction can reduce the required number of tests by a quadratic factor, but the apparent exponential branching of an interactive evaluation does not yield an exponential query advantage.