技术摘要：具有适应性与最优性的非平稳动态定价

1. 问题定义

本文研究了非平稳环境下的上下文动态定价问题。一家公司向 $T$ 个依次到达的消费者销售产品。在每个时刻 $t$，观测到一个上下文向量 $z_t \in \mathbb{R}^d$（编码了产品和消费者信息）。公司设定一个价格 $p_t \in [l, u]$，并观察到需求响应 $y_t$。

需求模型被假设为一个广义线性模型 (GLM)，其未知参数 $\theta_t \in \mathbb{R}^{2d}$ 随时间演变。具体而言，期望需求由下式给出：
$$\mathbb{E}[y_t | x_t, \theta_t] = \psi'(x_t^\top \theta_t) = \psi'(z_t^\top \alpha_t - (z_t^\top \beta_t)p_t)$$
其中 $x_t = (z_t^\top, -p_t z_t^\top)^\top$。

核心挑战在于参数序列 $\{\theta_t\}_{t=1}^T$ 是非平稳的，且其性质对公司而言是未知的。本文考虑了两种不同的非平稳机制：

1. 结构化非平稳性 (Structured Non-Stationarity)： 参数是分段常数的，存在 $s_T - 1$ 个未知的突变点。
2. 非结构化非平稳性 (Unstructured Non-Stationarity)： 参数随时间平滑或任意变化，受总变动预算 $V_T$ 的限制。

目标是设计一种定价策略，以最小化遗憾值 (Regret)。遗憾值定义为：与一个能够预知真实参数序列 $\{\theta_t\}$ 并在每一步都能设定最优价格 $p_t^*$ 的全知者相比，所造成的累积收入损失。至关重要的是，该算法必须具有适应性 (Adaptive)，即在无需预先知道环境是结构化还是非结构化、也无需预知 $s_T$ 或 $V_T$ 具体数值的情况下，实现最优性能。

2. 方法论：MCP-DP 算法

作者提出了基于多尺度变化点检测的动态定价算法 (MCP-DP)。该算法以“轮次 (Epochs)”为单位运行，每个轮次进一步划分为二进块 (Dyadic blocks)。在每个块内，它结合了先探索后提交 (Explore-Then-Commit, ETC) 策略与一种新型的多尺度采样方案 (Multiscale Sampling Scheme, MSS) 以及似然比检验 (Likelihood-Ratio Test, LRT)。

核心组件：

• 参考模型估计 (Reference Model Estimation)： 在每个块的开始，算法利用从前一个块积累的价格探索集，通过极大似然估计 (MLE) 来估计参考参数 $\hat{\theta}$。
• 局部价格探索 (Localized Price Exploration)： MCP-DP 并非采用均匀的价格采样，而是在贪婪价格 $p^*(z_t, \hat{\theta})$ 周围使用局部扰动方案。这在进行探索时减少了遗憾值，同时保持了统计有效性（确保设计矩阵保持良置）。
• 多尺度调度 (Multiscale Scheduling, MSS)： 为了检测幅度与时机均未知的变化，MSS 在每个块内随机调度不同长度（尺度）的价格探索间隔。较短的间隔被更频繁地采样以检测大规模的突发变化，而较长的间隔则用于检测微小的平滑漂移。
• 似然比检验 (LRT)： 在每个调度的探索间隔结束时，算法执行 LRT，将参考模型 $\hat{\theta}_{pre}$ 与在该间隔上拟合的新 MLE $\hat{\theta}_J$ 进行比较。
  • 检验统计量为 $\Lambda_J(\hat{\theta}_{pre}) = L_J(\hat{\theta}_{pre}) - L_J(\hat{\theta}_J)$。
  • 如果统计量超过阈值 $\gamma \propto d \log(dT)$，算法则假定发生了显著变化，从而终止当前轮次，并以新轮次重新开始。
• 适应性 (Adaptivity)： 这种多尺度的探索特性使得算法能够同时处理突发变化（结构化）和平滑变化（非结构化），而无需预先了解特定的机制或参数（$s_T, V_T$）。

3. 主要贡献

1. MCP-DP 算法及其遗憾值界限

本文引入了 MCP-DP，这是第一个被证明能适应结构化与非结构化非平稳性的动态定价算法。

• 遗憾值上界： 该算法实现的遗憾值阶数为：
  $$\tilde{O}\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$
  该界限代表了“两全其美 (Best-of-both-worlds)”的速率，同时匹配了纯结构化和纯非结构化设置下的最优速率。
• 无需先验知识： 该算法不需要预知变化点数量 $s_T$、变动预算 $V_T$、最小变化规模或分段长度。

2. 设计调整后的变动预算 (Design-Adjusted Variation Budget)

作者引入了一个新概念——设计调整后的变动预算 ($V_T$)。不同于现有衡量参数间原始距离 $\|\theta_t - \theta_{t-1}\|$ 的变动预算，$V_T$ 通过上下文分布（具体为设计矩阵 $\Sigma_z$）对变动进行了加权。

• 意义： 这为上下文环境下的非平稳性提供了更精确的刻画。它捕捉到了这样一个直觉：沿着上下文 $z_t$ 极少出现的方向发生的参数变化，对需求和遗憾值的影响较小。这一定义推广并收紧了现有文献中的界限。

3. Minimax 下界

本文为非平稳上下文动态定价建立了新的 Minimax 下界：
$$\Omega\left( \sqrt{s_T d T} \wedge \left( \sqrt{dT} + d^{1/3} V_T^{1/3} T^{2/3} \right) \right)$$

• 维度依赖性： 这是动态定价文献中第一个明确刻画了在结构化和非结构化情况下对上下文维度 $d$ 依赖关系的下界。
• 技术创新： 证明过程利用了一种基于 Assouad 引理 的新构造方法，以处理当 $T \to \infty$ 时趋于无穷大的维度 $d$，从而将遗憾值与多分类错误问题联系起来。

4. 理论与统计基础

• 高概率 MLE 界限： 作者推导出了非平稳环境下混合 GLM 预测误差的一个新的高概率上界。这一结果具有独立的学术价值，并构成了 LRT 最优性的基础。
• LRT 作为遗憾值的代理： 本文证明了 LRT 统计量可以作为未观测到的执行（Exploitation）遗憾值的代理，使得算法能够在不知道真实参数的情况下检测到过高的遗憾值。

4. 结果与实证验证

研究人员在不同上下文维度 ($d$) 和时间跨度 ($T$) 的线性及逻辑回归需求模型上进行了广泛的数值实验。

• 基准设置： 将 MCP-DP 与 CPDP（针对突发变化优化）和 MWDP（针对平滑变化优化）进行了对比。
  • 在平稳设置中，MCP-DP 的表现与 CPDP 持平，并优于 MWDP。
  • 在突发变化设置中，MCP-DP 与 CPDP 表现相当。
  • 在平滑变化设置中，MCP-DP 与 MWDP 表现相当。
  • 至关重要的是，MCP-DP 在无需调参的情况下在所有机制下都保持了鲁棒的性能，而基准算法在环境与其特定假设不符时表现失效。
• 复杂设置： 在对抗性变化模式（即 CPDP 的固定调度失效）或变化计数/预算发散的情景下，MCP-DP 展示了比非适应性基准算法更高的鲁棒性和更低的遗憾值。
• 设计调整预算验证： 通过不同上下文分布（Z1 vs. Z2）的实验证实，当使用设计调整后的预算进行衡量时，MCP-DP 的性能保持稳定，而标准的 $L_2$ 变动预算则无法解释这种稳定性。

5. 重要性与主张

本文声称填补了动态定价领域的一个长期存在的空白。以往关于非平稳定价的研究通常是非适应性的，需要针对突发变化与平滑变化分别设计算法，并且往往要求预知变化的幅度或预算。

• 首个适应性算法： MCP-DP 被认为是第一个在单一、适应性框架下，无需预知变化性质（$s_T$ 或 $V_T$）即可实现两种非平稳性（结构化与非结构化）最优遗憾率的算法。
• 最优性： 该算法被证明是 Minimax 最优的（忽略对数因子），达到了新推导出的下界。
• 方法论进展： 本研究强调，现有的自适应多臂老虎机理论（如切换老虎机）不能直接应用于上下文动态定价，因为后者具有连续的动作空间，且“最佳臂”（最优价格）会随上下文而变化。提出的基于 LRT 的方法通过追踪定价策略相对于上下文分布的遗憾值，专门解决了这一问题。

作者指出，虽然目前的工作假设上下文是随机的，但如何将该方法扩展到对抗性上下文仍是未来的研究方向，因为目前的 LRT 成功依赖于设计矩阵的随机性质。