Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML, PMLR, 2025)

Citation

Omar Bennouna, Jiawei Zhang, Saurabh Amin, and Asuman E. Ozdaglar, “Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach,” Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:3749-3775, 2025.

Paper · PDF · OpenReview

1. Introduction

• Contextual Optimization: 在现实决策中, 很多优化目标参数是不确定的. 但在决策之前能观测到一些有关的 contextual information 来帮助了解决策参数.

  • 例如: 一个交通路网有 $d$ 条连边, 定义 $\mathbf{c}\in {\mathbb{R}}^d$ 为每条边的通行成本, 其在决策前是未知的. 但在决策前可以观测到一些 contextual information $\mathbf{x}\in {\mathbb{R}}^k$ (例如天气, 时间, 交通流量等), 算法会根据这些 contextual information, 根据某种 policy $\pi (\mathbf{x})$ 来进行具体决策 $\mathbf{w}=\pi (\mathbf{x})$ (例如选择一条路径, 或流量分配等).
  • 文章定义, 标准的 contextual optimization 问题为: $$\underset{\pi \in \Pi }{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\mathbf{c}}^{\top }\pi (\mathbf{x})\right]$$
    • $(\mathbf{x},\mathbf{c})\sim \mathcal{P}$ 表示二者的联合分布, 强调二者之间的相关性, contextual information $\mathbf{x}$ 可以帮助了解 $\mathbf{c}$ 的分布.
    • $\Pi$ 表示 policy 的函数空间, 其中 $\pi :{\mathbb{R}}^k\to \mathcal{W}\subseteq {\mathbb{R}}^d$. $\mathcal{W}$ 表示决策空间 (例如路径选择集合, 资产权重, 订货量等), 且假设其是 convex & bounded.
  • 然而由于真实的联合分布 $\mathcal{P}$ 是未知的, 因此上述优化问题无法直接求解. 我们有的是一些历史数据 $\{({\mathbf{x}}_i,{\mathbf{c}}_i){\}}_{i=1}^n$ , 因此需要从某个 hypothesis class $\mathcal{H}$ 中学习一个参数化 predictor ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\in {\mathbb{R}}^d$ 来预测 $\mathbf{c}$, 进而求解.

• 对于 contextual optimization, 最经典的方法是 predict-then-optimize (PTO): 先学习一个 predictor ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$, 而后求解

  $$\hat{\mathbf{w}}\in \arg \underset{\mathbf{w}\in \mathcal{W}}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}$$

  注意, 这里的实际支付成本应当是 ${\mathbf{c}}^{\top }\hat{\mathbf{w}}$, 而不是 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\hat{\mathbf{w}}$. 落实到具体实现, 还有如下两个路径:

  • Sequential Learning and Optimization (SLO): 即传统的先预测后决策, 两阶段方法.
  • Integrated Learning and Optimization (ILO): 即端到端方法, 直接在预测时就考虑到后续优化效果.

• 然而上述两种方法都假设 hypothesis class $\mathcal{H}$ 是 well-specified 的, 即存在一个 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\in \mathcal{H}$ 使得

  $${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})={\mathbf{c}}^{\star }(\mathbf{x})\text{almost everywhere}$$

  但这并非现实中常见的情况. 更为现实的场景往往是 misspecified 的, 即使样本量趋于无穷大, 算法收敛到全局最优解, 但可能由于模型本身表现能力不足, 仍然无法得到最优的决策. 例如有如下几个重要的 misspecification 来源:

  • Incomplete features: 存在重要的遗漏特征
  • Unmodeled dependencies: 存在未建模的依赖关系, 例如 $\mathbf{c}$ 的分布可能依赖于 $\mathbf{x}$ 的某些非线性组合, 但模型假设是线性的.
  • Distribution shift: 训练数据和测试数据的分布不一致, 例如训练数据来自于过去的交通流量, 而测试数据来自于未来的交通流量, 其分布可能发生了变化.

• 本文核心重点区分了如下两种 misspecification:

  • Prediction misspecification: 即 $\mathcal{H}$ 中不存在一个 predictor ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 能够准确预测 $\mathbf{c}$. 典型的度量是:

    $$\underset{{\hat{\mathbf{c}}}_{\theta }\in \mathcal{H}}{\inf }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[\Vert {\hat{\mathbf{c}}}_{\theta }(\mathbf{x})-\mathbf{c}{\Vert }_2^2\right]>0$$

  • Decision misspecification: 即 $\mathcal{H}$ 不存在一个 predictor ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$, 使其能够诱导的决策 $\hat{\mathbf{w}}$ 与真实 cost 所诱导的最优决策 ${\mathbf{w}}^{\star }$ 几乎处处相同.

• 类似 SPO 当时的论述, 预测的好坏并不能决定性地影响最终决策的好坏.

  • 最重要的不是 prediction, 而是 decision misspecification, 即当前的 $\hat{\mathbf{c}}$ 能否导出 $\mathcal{H}$ 内最好的 decision.
  • 然而文中指出, 即使是 SPO 尽管已经是 decision awareness 的算法, 但仍没有给出在 misspecification 下的 consistency guarantee.

1.1 Problem Setup

下面正式给出问题 formulation. 在观察到某个具体的 context $\mathbf{x}$ 后, 我们希望求解如下的决策问题:

$$\underset{\mathbf{w}\in \mathcal{W}}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\mathbf{c}}^{\top }\mathbf{w}\mid \mathbf{x}\right]=\underset{\mathbf{w}\in \mathcal{W}}{\min }\mathbb{E}{\left[\mathbf{c}\mid \mathbf{x}\right]}^{\top }\mathbf{w}$$

由于分布 $\mathcal{P}$ 未知, 因此先根据历史数据 $\{({\mathbf{x}}_i,{\mathbf{c}}_i){\}}_{i=1}^n$ 在参数化 hypothesis class $\mathcal{H}$ 中学习一个 predictor ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ (可能是 misspecified 的), 而后求解 decision

$$\hat{\mathbf{w}}({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))\in \arg \underset{\mathbf{w}\in \mathcal{W}}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}=:{\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))$$

由于最优决策 ${\mathbf{w}}^{\star }(\mathbf{x})$ 可能不唯一, 因此定义 ${\mathcal{W}}^{\star }(\mathbf{c})$ 为所有最优决策的集合. 而最终的优化目标损失函数则定义为, 在最优决策集合中的, 以真实成本 $\mathbf{c}$ (而不是预测成本 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$) 计算的 worst-case 成本之期望:

$${\ell }_{\mathcal{P}}(\theta ):={\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[\underset{\mathbf{w}\in {\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))}{\max }{\mathbf{c}}^{\top }\mathbf{w}\right]$$

2. Main Approach

2.1 Rewriting target loss under uniqueness assumption

文章指出, ${\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))$ 尽管理论上可能多解, 但实践中, 若 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 是连续随机变量, 且 $\mathcal{W}$ 是 polyhedron, 则往往具有唯一解. 因此文章将唯一性单独列为 Assumption 1: 对任意 $\theta \in {\mathbb{R}}^m$, 若 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\ne 0$ almost surely, 则 ${\min }_{\mathbf{w}\in \mathcal{W}}{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}$ 在 $(\mathbf{x},\mathbf{c})\sim \mathcal{P}$ 下以概率 $1$ 有唯一解. 需要注意, ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\ne 0$ 本身并不足以推出唯一性; 它必须与 Assumption 1 一起使用.

在唯一性假设成立下, 最小化上述 target loss 就可以改写为:

$$\begin{array}{r}\underset{\theta \in {\mathbb{R}}^m}{\min }\left\{{\ell }_{\mathcal{P}}(\theta )=\underset{w_{\mathcal{P}}\in {\mathcal{W}}_{\mathcal{P}}}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\mathbf{c}}^{\top }{w}_{\mathcal{P}}(\mathbf{x})\right]\right\}\\ \text{s.t.}{w}_{\mathcal{P}}(\mathbf{x})\in \arg \underset{\mathbf{w}\in \mathcal{W}}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w},\text{for all }\mathbf{x}\in {\mathbb{R}}^k\end{array}$$

其中强调 ${\mathcal{W}}_{\mathcal{P}}$ 是决策规则的集合, 其元素 $w_{\mathcal{P}}(\mathbf{x})$ 不是具体的决策, 而是一个函数, 其输入是 context $\mathbf{x}$, 输出是 $\mathcal{W}$ 中的一个决策.

2.2 Surrogate loss: Consistent Integrated Learning and Optimization (CILO)

给定所有 measurable decision mappings 集合 ${\mathcal{W}}_{\mathcal{P}}$, 提取所有在真实成本下诱导出的 cost 不超过 $\beta \in \mathbb{R}$ 的 policy subset 为

$${\bar{\mathcal{W}}}_{\mathcal{P}}^{\beta }:=\left\{{\bar{w}}_{\mathcal{P}}\in {\mathcal{W}}_{\mathcal{P}}:{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\mathbf{c}}^{\top }{\bar{w}}_{\mathcal{P}}(\mathbf{x})\right]\le \beta \right\}$$

由此给出 CILO surrogate loss: 对于任意 $\beta \in \mathbb{R}$, 任意 $\theta \in {\mathbb{R}}^m$, 定义

$$\begin{array}{r}{\ell }_{\mathcal{P}}^{\beta }(\theta ):=\underset{{\bar{w}}_{\mathcal{P}}\in {\bar{\mathcal{W}}}_{\mathcal{P}}^{\beta }}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }{\bar{w}}_{\mathcal{P}}^{\beta }(\mathbf{x})\right]-\underset{w_{\mathcal{P}}\in {\mathcal{W}}_{\mathcal{P}}}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }{w}_{\mathcal{P}}(\mathbf{x})\right]\end{array}$$

该 loss 可以理解为如下两个部分的差值:

• 第一个 loss 表示: 在真实 cost 确定的 performance 达到 $\beta$ 的 policy subset 中, 根据预测 cost ${\hat{\mathbf{c}}}_{\theta }$ 的评价下, 最好的 objective value.
• 第二个 loss 表示: 在所有 policy 中, 根据预测 cost ${\hat{\mathbf{c}}}_{\theta }$ 的评价下, 最好的 objective value.

因此这个 loss 的意义在于, 在限制 policy 为真实 cost 不超过 $\beta$ 的 subset 中, 其在预测 cost 下的表现与在所有 policy 中的表现的 gap. 在下面 Theorem 1 的条件下, 有关系:

$${\ell }_{\mathcal{P}}^{\beta }(\theta )=0⟺{\ell }_{\mathcal{P}}(\theta )\le \beta$$

论文进一步证明, 当 $\beta \ge {\beta }_{\mathcal{H},\mathcal{P}}^{\star }$ 时, ${\ell }_{\mathcal{P}}^{\beta }(\theta )\ge 0$. 因此在 Theorem 1 的条件下, ${\ell }_{\mathcal{P}}^{\beta }(\theta )=0$ 又等价于 $\theta$ 是 ${\ell }_{\mathcal{P}}^{\beta }$ 的 minimizer. 因此有如下定理:

Theorem 1

令 $\beta \in \mathbb{R}$ 满足 ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }\le \beta <{\beta }_{\max ,\mathcal{P}}$. 在 Assumption 1 下, 对任意满足 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\ne 0$ almost surely 的 $\theta \in {\mathbb{R}}^m$, 有 ${\ell }_{\mathcal{P}}(\theta )\le \beta$ 当且仅当 $\theta$ 是 ${\ell }_{\mathcal{P}}^{\beta }$ 的 minimizer. 特别地, 当 $\beta ={\beta }_{\mathcal{H},\mathcal{P}}^{\star }$ 时, $\theta$ 是 ${\ell }_{\mathcal{P}}^{\beta }$ 的 minimizer 当且仅当它是 ${\ell }_{\mathcal{P}}$ 的 minimizer.

• 最小化 CILO loss ${\ell }_{\mathcal{P}}^{\beta }$ 等价于找出所有在真实 cost 下 performance 不超过 $\beta$ 的 predictor ${\hat{\mathbf{c}}}_{\theta }$.

接着定义

$${\beta }_{\mathcal{H},\mathcal{P}}^{\star }:=\underset{{\hat{c}}_{\theta }\in \mathcal{H}}{\min }{\ell }_{\mathcal{P}}({\hat{\mathbf{c}}}_{\theta })=\underset{{\hat{c}}_{\theta }\in \mathcal{H}}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[\underset{\mathbf{w}\in {\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))}{\max }{\mathbf{c}}^{\top }\mathbf{w}\right]$$

即整个 hypothesis class $\mathcal{H}$ 能达到的最优真实 decision loss. 定义

$${\beta }_{\max ,\mathcal{P}}={\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left[\underset{\mathbf{w}\in \mathcal{W}}{\max }{\mathbf{c}}^{\top }\mathbf{w}\right]$$

即在 $\mathcal{W}$ 中效果最差的决策在真实 cost 下的 performance. 故应取 $\beta \in [{\beta }_{\mathcal{H},\mathcal{P}}^{\star },{\beta }_{\max ,\mathcal{P}})$ 来保证 surrogate loss 的 non-triviality.

此外, 若令 $\beta ={\beta }_{\mathcal{H},\mathcal{P}}^{\star }$, 则由定理:

$$\theta \in \arg \underset{\theta \in {\mathbb{R}}^m}{\min }{\ell }_{\mathcal{P}}^{{\beta }_{\mathcal{H},\mathcal{P}}^{\star }}(\theta )⟺{\ell }_{\mathcal{P}}(\theta )\le {\beta }_{\mathcal{H},\mathcal{P}}^{\star }=\underset{{\hat{c}}_{\theta }\in \mathcal{H}}{\min }{\ell }_{\mathcal{P}}({\hat{\mathbf{c}}}_{\theta })⟹{\ell }_{\mathcal{P}}(\theta )={\beta }_{\mathcal{H},\mathcal{P}}^{\star }$$

即

$$\theta \in \arg \underset{\theta \in {\mathbb{R}}^m}{\min }{\ell }_{\mathcal{P}}^{{\beta }_{\mathcal{H},\mathcal{P}}^{\star }}(\theta )⟺\theta \in \arg \underset{\theta \in {\mathbb{R}}^m}{\min }{\ell }_{\mathcal{P}}({\hat{\mathbf{c}}}_{\theta })$$

这个定理给出了最小化真正 decision loss ${\ell }_{\mathcal{P}}$ 的 surrogate loss ${\ell }_{\mathcal{P}}^{{\beta }_{\mathcal{H},\mathcal{P}}^{\star }}$ 的构造方法. 并且当 $\beta ={\beta }_{\mathcal{H},\mathcal{P}}^{\star }$ 时, ${\ell }_{\mathcal{P}}^{{\beta }_{\mathcal{H},\mathcal{P}}^{\star }}$ 的 minimizer 与 ${\ell }_{\mathcal{P}}$ 的 minimizer 是完全一致的. 然而在实践中, ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }$ 是未知的, 因此需要通过 line search 的方法, 确定若干 $\beta$ 值, 并在每个 $\beta$ 下最小化 ${\ell }_{\mathcal{P}}^{\beta }$, 进而找到最优的 ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }$.

3. Technical Approach

这里展示了具体优化过程中的技术问题和处理方法. 主要问题包括

1. $\mathcal{P}$ 是未知的, 因此期望需要用样本均值 empirically ${\mathcal{P}}_n$ 近似 $\mathcal{P}$. 故存在泛化性之问题.
2. ${\ell }_{\mathcal{P}}^{\beta }$ 本身也是 non-convex, non-smooth 的, 故还需要额外的光滑手段.
3. 上述定理还需要 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\ne 0$ 几乎处处成立以保证下游决策的唯一性, 因此还需要具体的手段确保其成立.

约定这里的 norm 取 ${\ell }_2$ norm.

3.1 Generalization Guarantee

为确保泛化性, 做如下假设:

• 此处不要求 hypothesis set 具有线性形式; 只假设 predictor 由 $\theta \in {\mathbb{R}}^m$ 参数化, 并满足下面的 boundedness 和 regularity 条件.

• 决策的可行域 $\mathcal{W}$ 是 closed and bounded, 故存在一个常数 $B_{\mathcal{W}}>0$, 使得 $\Vert \mathbf{w}{\Vert }_2\le B_{\mathcal{W}}$ 对于任意 $\mathbf{w}\in \mathcal{W}$ 都成立. 给定 context $\mathbf{x}$, 真实 cost $\mathbf{c}$ bounded: 存在 $K$, 使得 $\Vert \mathbf{c}{\Vert }_2\le K$ 对于任意 $(\mathbf{x},\mathbf{c})\sim \mathcal{P}$ 都成立. 从而有:

  $$⟨\mathbf{c},\mathbf{w}⟩\le K{B}_{\mathcal{W}},\forall (\mathbf{x},\mathbf{c})\sim \mathcal{P},\forall \mathbf{w}\in \mathcal{W}$$

• 当 $\theta =0$ 时, ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})=0$ 对于任意 $\mathbf{x}$ (这个很基本的假设, 只是为了推导方便). 此外, 要求 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 的梯度 ${\nabla }_{\theta }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\in {\mathbb{R}}^{d\times m}$ 有上界 $B_{\Phi }$, 即

  $$\Vert {\nabla }_{\theta }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}){\Vert }_2\le B_{\Phi },\forall \mathbf{x}\in {\mathbb{R}}^k,\forall \theta \in {\mathbb{R}}^m$$

  此外要求梯度 ${\nabla }_{\theta }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 是 piecewise continuous 的 (只在有限个点不连续) 以便后续的积分操作.

  根据上述假设, 由积分放缩, 可以得到如下不等式:

  $$\Vert {\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\Vert \le B_{\Phi }\Vert \theta {\Vert }_2,\forall \mathbf{x}\in {\mathbb{R}}^k,\forall \theta \in {\mathbb{R}}^m$$

  这说明 predictive cost ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 的大小可以被 $\Vert \theta {\Vert }_2$ 控制.

由此可以得到如下的泛化性定理.

Theorem 2

令 $\beta \ge {\beta }_{\mathcal{H},\mathcal{P}}^{\star }$. 在根据历史数据 $S=\{({\mathbf{x}}_i,{\mathbf{c}}_i){\}}_{i=1}^n$ 形成的经验分布 ${\mathcal{P}}_n$ 下, 取某个 ${\theta }^{\star }\in {\mathbb{R}}^m$ 为 empirical CILO loss 足够小的 minimizer, 即 ${\ell }_{{\mathcal{P}}_n}^{\beta }({\theta }^{\star })\le \epsilon$. 接着假设 ${\theta }^{\star }$ 同样可以被一个正常数 $D$ 控制, 即 $\Vert {\theta }^{\star }{\Vert }_2\le D$. 则在上述假设基础上, 以及 ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }>{\beta }_{\min ,\mathcal{P}}$ 的前提下 (其中 RHS 是一个给定的 oracle 下界), 以概率至少 $1-\delta$ , 有:

$${\ell }_{\mathcal{P}}^{\beta }({\theta }^{\star })\le \underset{\text{empirical CILO}}{\underbrace{\epsilon }}+\underset{\text{generalization gap}}{\underbrace{\mathcal{O}\left(\frac{1}{\beta -{\beta }_{\min ,\mathcal{P}}}\cdot \sqrt{\frac{\log (1/\delta )}{n}}\right)}}$$

其中 ${\beta }_{\min ,\mathcal{P}}:={\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim \mathcal{P}}\left({\min }_{\mathbf{w}\in \mathcal{W}}{\mathbf{c}}^{\top }\mathbf{w}\right)$ 为理想的 oracle 水平, 即能够看到真实 cost $\mathbf{c}$ 后, 在 $\mathcal{W}$ 中做出的最优决策的 performance.

• 注意区分 ${\beta }_{\min ,\mathcal{P}}$ 与 ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }$, 前者是 oracle 下界, 后者是当前 hypothesis class $\mathcal{H}$ 能够达到的最优真实 decision loss. 故恒有 ${\beta }_{\min ,\mathcal{P}}\le {\beta }_{\mathcal{H},\mathcal{P}}^{\star }$.
  • 若 $\mathcal{H}$ 是 well-specified 的, 则确实能够产生 oracle-optimal 的决策, 故 ${\beta }_{\min ,\mathcal{P}}={\beta }_{\mathcal{H},\mathcal{P}}^{\star }$.
  • 若 $\mathcal{H}$ 是 misspecified 的, 则 ${\beta }_{\min ,\mathcal{P}}<{\beta }_{\mathcal{H},\mathcal{P}}^{\star }$.
• 在表达式中, $1/(\beta -{\beta }_{\min ,\mathcal{P}})$ 表明, 当 CILO 中规定的允许真实成本门槛 $\beta$ 越接近 oracle 下界 ${\beta }_{\min ,\mathcal{P}}$, 则要求越严格, 表明当前只允许十分接近 oracle 的 policy subset, 这会导致泛化性很差, 反之亦然.
• 不过反而天然的, 当模型是 misspecified 的时, ${\beta }_{\mathcal{H},\mathcal{P}}^{\star }>{\beta }_{\min ,\mathcal{P}}$, 因此 $\beta -{\beta }_{\min ,\mathcal{P}}\ge {\beta }_{\mathcal{H},\mathcal{P}}^{\star }-{\beta }_{\min ,\mathcal{P}}>0$, 因此泛化性是有保证的. 对应的, 当模型是 well-specified 的, 则需要适当调大 $\beta$ 来保证泛化性.

3.2 Stronger Consistency Guarantee

Theorem 1 给出了 ${\ell }_{\mathcal{P}}^{\beta }=0⟹{\ell }_{\mathcal{P}}\le \beta$ 的 guarantee, 然而在实践中往往无法严格保证 ${\ell }_{\mathcal{P}}^{\beta }=0$, 因此需要更强的 guarantee.

假设:

1. 只要 $\theta \ne 0$, 则 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})\ne 0$ a.s. 成立. 这结合之前的 Assumption 1 保证 ${\min }_{\mathbf{w}\in \mathcal{W}}{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}$ 的唯一性成立.

2. $\mathcal{W}$ 是一个 polyhedron, 记其所有 extreme points 为 ${\mathcal{W}}_{\text{ext}}$. 由于目标 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}$ 是线性的, 因此最优点 ${\mathbf{w}}^{\star }$ 必然是 ${\mathcal{W}}_{\text{ext}}$ 中取到. 因此考虑如下差值以衡量解的稳定性: 当 ${\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))\ne {\mathcal{W}}_{\text{ext}}$ 时,

   $${\Delta }_{\theta }(\mathbf{x}):=\underset{\mathbf{w}\in {\mathcal{W}}_{\text{ext}}\setminus {\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}-\underset{\mathbf{w}\in {\mathcal{W}}_{\text{ext}}}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}$$
   • 第一项表示在所有非最优 extreme points 中, 其在 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 下的最小值. 第二项表示在所有 extreme points 中, 其在 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 下的最小值. 因此 ${\Delta }_{\theta }(\mathbf{x})$ 表示最优点与次优点之间的 gap. 这个 gap 越大, 则 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 的唯一性越强, 也就越不容易被噪声干扰.
   • 当 ${\mathcal{W}}^{\star }({\hat{\mathbf{c}}}_{\theta }(\mathbf{x}))={\mathcal{W}}_{\text{ext}}$ 时, 定义 ${\Delta }_{\theta }(\mathbf{x})=0$.

   且假设, 存在常数 $\alpha >0$, $\gamma \ge 0$, 使得对于任意 $\theta \in {\mathbb{R}}^m$, 有

   $$\mathbb{P}\left(0<{\Delta }_{\theta }(\mathbf{x})\le \Vert \theta \Vert t\right)\le {\left(\frac{\gamma t}{B_{\mathcal{W}}}\right)}^{\alpha },\forall t>0$$

   即, 解不稳定的 gap 只以 $\mathcal{O}(t^{\alpha })$ 的小概率出现, 通常的解的 gap 都是稳定的, 这保证了 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 的唯一性.

在上述假设下, 有如下定理:

Theorem 3

在 Assumptions 2, 3 和 5 下, 存在 $\alpha >0$, 使得对于任意固定的 $u>0$、任意满足 $\Vert \theta {\Vert }_2\ge u$ 的 $\theta \in {\mathbb{R}}^m$, 以及任意 $\beta \ge {\beta }_{\mathcal{H},\mathcal{P}}^{\star }$, 有

$${\ell }_{\mathcal{P}}(\theta )\le \beta +\mathcal{O}\left({\ell }_{\mathcal{P}}^{\beta }(\theta {)}^{\frac{\alpha }{1+\alpha }}\right)$$

• 即使 ${\ell }_{\mathcal{P}}^{\beta }(\theta )$ 不是严格为零, 也可以保证 ${\ell }_{\mathcal{P}}(\theta )$ 不会偏离 $\beta$ 太远, 其以 $\mathcal{O}\left({\ell }_{\mathcal{P}}^{\beta }(\theta {)}^{\frac{\alpha }{1+\alpha }}\right)$ 的速度收敛到 $\beta$.

3.3 Optimizing the Surrogate

根据上面的推导, 只需要找到一个 $\theta \ne 0$ 且有界, 使得 empirical surrogate ${\ell }_{{\mathcal{P}}_n}^{\beta }(\theta )$ 足够小, 即可保证 target loss ${\ell }_{\mathcal{P}}(\theta )$ 足够小. 故这一小节的目标即为优化该经验 CILO.

对于任意 $\theta \in {\mathbb{R}}^m$, 其 empirical CILO loss 可以拆分如下 (纯粹代数整理):

$${\ell }_{{\mathcal{P}}_n}^{\beta }(\theta )=g_{{\mathcal{P}}_n}(\theta )-{\bar{g}}_{{\mathcal{P}}_n}^{\beta }(\theta )$$

其中

$$g_{{\mathcal{P}}_n}(\theta ):=-{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim {\mathcal{P}}_n}\left[\underset{\mathbf{w}\in \mathcal{W}}{\min }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }\mathbf{w}\right]=-\underset{{\mathbf{w}}_{{\mathcal{P}}_n}\in {\mathcal{W}}_{{\mathcal{P}}_n}}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim {\mathcal{P}}_n}\left[{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }{w}_{{\mathcal{P}}_n}(\mathbf{x})\right]$$ $${\bar{g}}_{{\mathcal{P}}_n}^{\beta }(\theta ):=-\underset{{\bar{w}}_{{\mathcal{P}}_n}\in {\bar{\mathcal{W}}}_{{\mathcal{P}}_n}^{\beta }}{\min }{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim {\mathcal{P}}_n}\left[{\hat{\mathbf{c}}}_{\theta }(\mathbf{x}{)}^{\top }{\bar{w}}_{{\mathcal{P}}_n}^{\beta }(\mathbf{x})\right]$$

假设 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 是一个连续函数, 且 ${\nabla }_{\theta }{\hat{\mathbf{c}}}_{\theta }(\mathbf{x})$ 是 $B_L>0$ Lipschitz continuous 的, 则可以证明这两个函数都是 weakly convex 的. 通过给二者添加同一个足够大的二次项, 可以将它们分别写成 convex functions, 因此 ${\ell }_{{\mathcal{P}}_n}^{\beta }(\theta )$ 是一个 DC function.

这里又重新进行了一次 rename: $g_{{\mathcal{P}}_n}^1(\theta ):=g_{{\mathcal{P}}_n}(\theta )$, $g_{{\mathcal{P}}_n}^2(\theta ):={\bar{g}}_{{\mathcal{P}}_n}^{\beta }(\theta )$, 则 ${\ell }_{{\mathcal{P}}_n}^{\beta }(\theta )=g_{{\mathcal{P}}_n}^1(\theta )-g_{{\mathcal{P}}_n}^2(\theta )$. 此时对每个函数进行 Moreau Smoothing:

$$M_{{\mathcal{P}}_n}^i(\lambda ):=\underset{\theta \in {\mathbb{R}}^m}{\min }\left\{g_{{\mathcal{P}}_n}^i(\theta )+\frac{1}{2}\Vert \lambda -\theta {\Vert }_2^2\right\},i=1,2$$

以及

$${\theta }_{{\mathcal{P}}_n}^i(\lambda ):=\arg \underset{\theta \in {\mathbb{R}}^m}{\min }\left\{g_{{\mathcal{P}}_n}^i(\theta )+\frac{1}{2}\Vert \lambda -\theta {\Vert }_2^2\right\},i=1,2$$

然后就可以定义 s-CILO (smoothed CILO) loss:

$$r_{{\mathcal{P}}_n}^{\beta }(\lambda ):=M_{{\mathcal{P}}_n}^1(\lambda )-M_{{\mathcal{P}}_n}^2(\lambda )$$

根据 gradient:

$$\nabla r_{{\mathcal{P}}_n}^{\beta }(\lambda )={\theta }_{{\mathcal{P}}_n}^2(\lambda )-{\theta }_{{\mathcal{P}}_n}^1(\lambda )$$

因此若 $\lambda$ 是 s-CILO 的 stationary point, 则 ${\theta }_{{\mathcal{P}}_n}^1(\lambda )={\theta }_{{\mathcal{P}}_n}^2(\lambda )$. 且这个共同的 $\theta$ 也是原始 empirical CILO ${\ell }_{{\mathcal{P}}_n}^{\beta }(\theta )$ 的 stationary point. 因此可以通过优化 s-CILO 来间接优化原始的 empirical CILO.

为得到后续的集合表示, 下面进一步假设 hypothesis set 是线性的: 存在 $\Phi :{\mathbb{R}}^k\to {\mathbb{R}}^{d\times m}$, 使得 ${\hat{\mathbf{c}}}_{\theta }(\mathbf{x})=\Phi (\mathbf{x})\theta$.

下面讨论如何避免出现 $\theta =0$ 的情况. 定义如下的 log-CILO loss:

$$f_{{\mathcal{P}}_n}^{\beta }(\lambda ):=\log d(\lambda ,-V_{{\mathcal{P}}_n}^{\beta })-\log d(\lambda ,-V_{{\mathcal{P}}_n})$$

其中

$$V_{{\mathcal{P}}_n}=\{{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim {\mathcal{P}}_n}\left[\Phi (\mathbf{x}{)}^{\top }{w}_{{\mathcal{P}}_n}(\mathbf{x})\right]:{\mathbf{w}}_{{\mathcal{P}}_n}\in {\mathcal{W}}_{{\mathcal{P}}_n}\}$$ $$V_{{\mathcal{P}}_n}^{\beta }=\{{\mathbb{E}}_{(\mathbf{x},\mathbf{c})\sim {\mathcal{P}}_n}\left[\Phi (\mathbf{x}{)}^{\top }{\bar{w}}_{{\mathcal{P}}_n}^{\beta }(\mathbf{x})\right]:{\bar{w}}_{{\mathcal{P}}_n}^{\beta }\in {\bar{\mathcal{W}}}_{{\mathcal{P}}_n}^{\beta }\}$$

前者对应所有 policies, 后者对应所有在真实 cost 下 performance 不超过 $\beta$ 的 policies. $d$ 是欧氏距离.

由于 $V_{{\mathcal{P}}_n}^{\beta }\subseteq V_{{\mathcal{P}}_n}$, 有 $d(\lambda ,-V_{{\mathcal{P}}_n}^{\beta })\ge d(\lambda ,-V_{{\mathcal{P}}_n})$. 因而在两个距离均为正的定义域上恒有 $f_{{\mathcal{P}}_n}^{\beta }(\lambda )\ge 0$, 且两个距离相等时 $f_{{\mathcal{P}}_n}^{\beta }(\lambda )=0$. 论文进一步证明, log-CILO 的 stationary point 也是 s-CILO 的 stationary point, 反向关系则不由该结论保证.

总结下来, log-CILO 用于引导优化过程避开对应 $\theta =0$ 的共同边界情形. 完整方法还需要结合 s-CILO 上的 gradient descent 与论文 Theorem 6 的构造; 单独优化 log-CILO 并不能无条件保证 $\theta \ne 0$.