Multiscale Reward Hedging from Correct Demonstrations

技术摘要：基于正确演示的多尺度奖励对冲 (Multiscale Reward Hedging from Correct Demonstrations)

问题定义
本文研究了在存在多个最优动作的场景下，如何从正确的演示（correct demonstrations）中学习的问题。与标准的监督学习不同，学习者观察到一个针对上下文 $x_t$ 的单一有效演示 $a^*_t$，但无法得知其自身的预测 $\hat{a}_t$ 是否正确，也无法观测到潜在的奖励函数或其损失的大小。其目标是最小化针对未知奖励函数 $r^*$ 的累积“隐藏差距”（hidden gap，即最优动作与学习者动作之间的奖励差）。

这一设定将之前针对有限奖励类（Joshi 等人，2026）的工作推广到了连续奖励类，而这在之前是未被解决的空白。该反馈模型有别于在线逆优化（online inverse optimization）或标准的情境老虎机（contextual bandits）：学习者既不会观测到奖励值，也不会观测到正确性位（correctness bit），仅能观测到未知最优动作集中的一个有效动作。

方法论：多尺度奖励对冲
其核心贡献是一个在未知时间跨度下运行的确定性多尺度奖励对冲算法。该方法依赖于以下组件：

1. 差距度量与代理（Gap Metric and Proxies）： 算法关注的是差距函数 $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$。算法并非直接估计奖励函数，而是维护着对一组“容错二元代理”（tolerant binary proxies）的加权投票。
2. 多尺度覆盖（Multiscale Covering）： 对于一系列精度尺度 $\epsilon_j = 2^{-j-1}$，算法为差距函数类 $G$ 构建适当的 $\epsilon_j$-覆盖（$C_j$）。每个元素 $h \in C_j$ 定义了一个代理 $q_{j,h}$，该代理将一个动作标记为“好”，当且仅当 $h(x, a) \le \epsilon_j$。
3. 共享投票（Shared Vote）： 算法并非为每个尺度运行独立的学习器（这会导致动作不兼容），而是将所有尺度的代理聚合到一个单一的加权投票中。尺度 $j$ 处代理的初始权重与 $2^{-j}$ 成正比。
4. 更新规则： 该更新是“无错误感知”（mistake unaware）的。在观察到演示 $a^*_t$ 后，算法仅根据代理对演示的判断与学习者预测之间的比较来更新权重：
   • 如果代理认为演示是“好”的，但学习者的动作是“坏”的，则该代理的权重翻倍。
   • 如果代理认为演示是“坏”的，则将其权重归零。
   • 否则，权重保持不变。
     该规则确保了如果学习者的动作相对于特定尺度具有较大的差距，代表该尺度的代理权重就会增加，从而有效地针对该尺度的误差进行“对冲”。

关键理论结果

• 无时间跨度尾部界限（Horizon-Free Tail Bounds）： 算法提供了一个关于损失超过阈值 $2^{-j}$ 的轮数量的同步尾部界限：
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  其中 $N(G, \epsilon)$ 是差距类 $G$ 的覆盖数。通过整合这些尾部，可以得到一个独立于时间跨度 $T$ 的累积隐藏差距界限：
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  该和式受限于度量熵积分 $H_{dyad}(G)$。

• 多项式熵与遗憾率（Polynomial Entropy and Regret Rates）：

  • 对于具有多项式覆盖数 $N(G, \epsilon) \le (A/\epsilon)^d$ 的类别，总差距由 $O(d \log A)$ 约束。
  • 在在线转批量（online-to-batch）设置中，这转化为 $O(d/m)$ 的统计速率。
  • 线性情境推荐： 对于具有参数半径 $B$ 和菜单直径 $K$ 的有界线性奖励，对于任意紧凑菜单，其遗憾度为 $O(d)$。这是第一个通过非适当预测器（improper predictor）实现的、无需结构限制（如 M-凸性）即可处理任意菜单的多项式有限界限。
  • 低秩与神经网络奖励： 该框架可扩展至低秩双线性奖励（$O(BKr(m+n))$）以及取决于网络深度和参数的有界 ReLU 网络。

• 计算复杂度：

  • 通用算法是信息论层面的，由于需要枚举覆盖，计算成本可能很高。
  • 然而，对于一维 Lipschitz 参数曲线（例如固定半径的二阶秩推荐），该算法是精确的且能在多项式时间内运行。具体而言，对于菜单规模为 $k$、奖励评估成本为 $C$ 的固定半径二阶秩推荐，时间复杂度为 $O(kCT^2)$。

• 下界与鲁棒性：

  • 论文证明了对于具有熵指数 $d$ 的连续类，存在匹配的 $\Omega(d)$ 下界，证实了 $O(d)$ 依赖性的紧密性。
  • 一个鲁棒变体可以处理次优演示，仅在遗憾界限中增加演示者的累积次优性 $\Delta_T$。

意义与主张
本文声称解决了连续奖励类下从正确演示中学习的开放性问题。其主要意义在于：

1. 首个针对连续类的无时间跨度保证： 它提供了第一个不依赖于时间跨度 $T$、而是依赖于度量熵的连续类遗憾界限。
2. 针对任意菜单的非适当预测： 它实现了线性情境推荐在任意紧凑菜单下的 $O(d)$ 遗憾度，在以往的算法中，实现这一目标需要结构限制（如 M-凸性）或会承受更高的维度依赖。
3. 特定几何结构下的高效性： 虽然通用投票开销较大，但论文分离出了一个非平凡的情况（一维 Lipschitz 曲线），在该情况下精确算法是多项式时间的，从而弥合了信息论界限与计算可行性之间的鸿沟。
4. 经验验证： 在 MovieLens 数据集上的可复现压力测试表明，该算法能够适应不同尺度，并仅使用动作演示（而不观测奖励）的情况下，相比于演示评分策略和适当的在线基准，提升了平均潜在差距。

作者强调，虽然通用的解是非适当的（即投票结果可能并不对应于单个有效的奖励参数），但它能成功最小化目标奖励差距，这区别于旨在估计奖励参数本身的适当在线逆优化方法。