arXiv:2512.20368stat.MLcs.IT2025-12被引 2

提出稳定算法,让线性上下文博弈的推断无需承担适应性代价。

Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability

  • 设计正则化EXP4算法,满足Lai-Wei稳定性条件
  • 在稳定条件下实现经典置信区间,无需额外√(d log T)膨胀
  • 兼具最优后悔率与有效推断,适合自适应实验设计

上下文博弈中的统计推断因数据的自适应、非独立同分布特性而困难重重。已有研究指出,经典最小二乘推断在自适应采样下会失效,对线性泛函的有效置信区间通常需$\sqrt{d \log T}$量级的放大。这一现象常被称为‘适应性代价’,反映了在一般上下文博弈策略下可靠推断的内在难度。克服该限制的关键结构条件是Lai和Wei提出的稳定性条件,要求经验特征协方差收敛到确定性极限。当稳定性成立时,普通最小二乘估计满足中心极限定理,经典Wald型置信区间在适应性下仍渐近有效,无需承担$\sqrt{d \log T}$的代价。本文提出并分析一种用于线性上下文博弈的正则化EXP4算法。第一个主要结果表明,该算法满足Lai–Wei稳定性条件,因而对线性泛函可构造有效的Wald型置信区间。我们还提供了相关中心极限定理的量化收敛速率。第二个结果证明,该算法达到几乎最优的后悔率(对数因子内),展示了稳定性与统计效率可在单一方法中共存。作为理论应用,我们展示了如何利用该框架在自适应采集数据下构建条件平均处理效应(CATE)的置信区间。最后,通过模拟验证了估计量的实证正态性及置信区间的精确性。

原文摘要 · Abstract (English)

Statistical inference in contextual bandits is challenging due to the adaptive, non-i.i.d. nature of the data. A growing body of work shows that classical least-squares inference can fail under adaptive sampling, and that valid confidence intervals for linear functionals typically require an inflation of order $\sqrt{d \log T}$. This phenomenon -- often termed the price of adaptivity -- reflects the intrinsic difficulty of reliable inference under general contextual bandit policies. A key structural condition that overcomes this limitation is the stability condition of Lai and Wei, which requires the empirical feature covariance to converge to a deterministic limit. When stability holds, the ordinary least-squares estimator satisfies a central limit theorem, and classical Wald-type confidence intervals remain asymptotically valid under adaptation, without incurring the $\sqrt{d \log T}$ price of adaptivity. In this paper, we propose and analyze a regularized EXP4 algorithm for linear contextual bandits. Our first main result shows that this procedure satisfies the Lai--Wei stability condition and therefore admits valid Wald-type confidence intervals for linear functionals. We additionally provide quantitative rates of convergence in the associated central limit theorem. Our second result establishes that the same algorithm achieves regret guarantees that are minimax optimal up to logarithmic factors, demonstrating that stability and statistical efficiency can coexist within a single contextual bandit method. As an application of our theory, we show how it can be used to construct confidence intervals for the conditional average treatment effect (CATE) under adaptively collected data. Finally, we complement our theory with simulations illustrating the empirical normality of the resulting estimators and the sharpness of the corresponding confidence intervals.

上下文博弈推断稳定性置信区间

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。