上下文赌博机应在观察到替代指标后再获取主结局吗?

替代指标后的获取时机可优于获取前,但仅在残余不确定性集中于策略分歧处时成立。

直接答案

在本文设定中,学习者应在看到免费的替代指标之后再决定是否获取主结局,因为替代指标在动作之后、测量之前到达。Audited Surrogate Bandit 在替代指标之前依据决策相关性设定获取水平,之后用估计的残余不确定性重新分配该水平;对于 K 个动作上 N 个策略的有限类,其相对最优策略的遗憾为 sqrt(KT log N)(1 + sqrt(T/B)) 量级,同时在 T 轮中恰好花费 B 次主结局获取。

1篇文献引用

本文由 WisPaper 驱动的搜索和论文分析生成。

替代指标来得太晚,无法改变动作

每一轮都按上下文、动作、替代指标、然后决定是否获取主结局的顺序进行。替代指标到达时,动作已经固定,因此它无法修改动作。它仍能改变的是:那个定义动作价值和遗憾的昂贵主结局是否被测量。

这是本文的核心区分。替代指标不是替代奖励,也不重新定义遗憾;动作价值和累积遗憾仍与主结局绑定。替代指标是获取侧的信息:它帮助决定有限的测量预算花在哪里,而主结局继续定义学习者试图优化的目标。

论文把一轮描述为上下文、动作、替代指标、获取决策,然后才观察到主结局。获取决策只决定主结局是否被观察到,不改变未来的上下文或结局。这种被动性是范围条件,不是关于测量的一般性主张。

决策相关性与残余不确定性都重要

论文认为,测量主结局的价值取决于两个独立的量。决策相关性问的是当前结局对尚未解决的策略比较有多重要:如果相互竞争的策略选择同一动作,观察主结局在该轮并不能区分它们。残余不确定性问的是看到替代指标后还剩多少变异:如果策略有分歧但残余变异很小,主结局对区分它们的帮助也很小。

这两个要素在不同时间使用。在观察到替代指标之前,方法依据决策相关性设定替代指标前的获取水平。在观察到替代指标之后,它用残余不确定性的估计重新分配该水平,具体是主结局减去拟合桥后的学习均方根残差分数。

论文对这种划分的解释来自策略比较证据的方差分解。获取概率除了一项包含策略比较系数平方和残余方差的项,因此相关性设定水平,残余不确定性在替代指标取值之间重新分配它。

硬预算与无偏的增广更新

Audited Surrogate Bandit 在 N 个确定性策略的有限类上学习上下文策略,同时在 T 轮中分配 B 次主结局获取的硬预算。论文指出,该方法在每条路径上恰好获取 B 次主结局,使用剩余预算和剩余轮数规则,而不是期望预算。

选择性测量可能使未校正的策略更新产生偏差,因此方法使用增广反馈:拟合桥加上逆获取概率校正,作用于观察到的主结局与桥之间的残差。在所述获取抽取与主结局在给定历史和替代指标后状态下条件独立的条件下,该校正保持主结局的条件均值。论文指出,最坏情况保证不要求拟合桥、残差分数或替代指标律正确;它们的误差会损害预算使用效率,但不改变增广更新所保持的主目标。

随后用二阶指数权重规则更新策略权重,并在线重新拟合桥、残差分数和条件替代指标律。论文在附录中给出了一种具体的在线拟合设定。

遗憾随 T 与 B 之比的平方根增长

对于 K 个动作上 N 个策略的有限类,论文报告该方法相对类中最优策略的遗憾为 sqrt(KT log N) 乘以 (1 + sqrt(T/B)) 量级,忽略对数因子。预算 B 出现在平方根惩罚内部,因此获取预算越小,保证越差。

论文还给出一个下界:在表示出最优策略的子类上,获取预算的 sqrt(T/B) 依赖在对数因子内不可避免。这是关于预算惩罚的最坏情况陈述,并不声称每个小预算问题都表现相同。

论文的讨论补充了主结局稀缺本身带来的另一个限制:下界表明,即使把逐路径硬预算放宽为期望获取预算,最坏情况 sqrt(T/B) 惩罚仍然存在。

替代指标后的时机可改变可达遗憾

论文比较了观察替代指标之前和之后的获取。对于相同平均获取率下的固定策略比较,它表明允许获取使用替代指标可以严格降低主结局价值差的无偏估计的最小方差。

更强的结果关于速率。在一个替代指标不揭示更优动作的两动作族中,先观察替代指标再决定是否获取的学习者可实现有界遗憾,而任何必须在看到替代指标之前决定的学习者在相同预算下会承受 T/B 量级的最坏情况遗憾。论文强调,即使替代指标不揭示最优动作,这种时机效应仍然成立。

这是论文对其标题问题最尖锐的回答:获取决策相对于替代指标的先后顺序不是细节,因为它可以改变可达遗憾速率,而不仅仅是常数。

去掉任一获取要素都会提高遗憾

在合成实验中,论文报告获取设计的两个部分都对遗憾重要:去掉决策相关性或去掉替代指标后的残差均方根精炼,都会增加累积遗憾。实验还表明,即使替代指标不揭示最优动作,使用当前替代指标进行获取也能降低遗憾。

另一个合成结果关于残余信息所在的位置。当更多残余信息位于所表示策略分歧之处而非一致之处时,该方法遗憾更低,即使残余信息总量固定。这把经验模式与决策相关性思想联系起来:相同的平均残余信息,当它集中在策略比较尚未解决之处时更有用。

KuaiRec 差距随预算先扩大后收窄

在用户-视频交互的 KuaiRec 基准上,论文构建了一个上下文获取基准,K = 5 个动作,N = 9 个所表示策略,时间跨度 T = 22,417。每轮学习者从五个候选视频中选择一个,观察一个免费替代指标,定义为播放时长是否超过 7 秒,然后决定是否获取主结局,定义为封顶为 1 的观看比例。遗憾和终期策略价值都用该观看比例主结局评估。

该方法与匹配的仅相关性参照比较,后者只去掉观察替代指标后的学习重分配,因此该比较在主结局预算变化时分离出替代指标后精炼的贡献。评估的预算为 2、3、4、6、8、12、16 和 24 个百分点。

论文报告,相对仅相关性获取的遗憾差距随预算增长先扩大后收窄,最清晰的分离出现在 4 到 8 个百分点。在低端,全获取初始化消耗了大部分预算,留给后续替代指标后精炼改变获取内容的轮数很少。在高端,两种方法都观察到多得多的主结局,对比收窄。

论文还区分了两种评估摘要:累积遗憾概括学习轨迹,而终期策略价值评估最终混合。在终期价值对比接近零的预算上,遗憾对比仍为正,因此学习路径上的收益不一定延续到终期价值。

有机会使用替代指标不等于能利用它

论文的讨论区分了选择性测量带来的三个问题。第一,选择性测量可能使未校正更新产生偏差,增广反馈在不要求桥正确的情况下处理了这一点。第二,一旦目标得到保护,时机问题仍然存在:在测量前看到当前替代指标,在某些设定下可能使最小比较方差不变,在另一些设定下则改变可达遗憾速率,取决于替代指标是否在对策略比较重要的轮次上区分残余不确定性。第三,学习者事先不知道哪些轮次值得测量,而选择性获取的主结局同时喂给策略更新以及桥和残差拟合,因此为动作学习收集的证据也会改变之后获取哪些结局。

论文还指出,其表述把测量视为被动的:获取当前主结局只是揭示它,不改变未来上下文或结局。如果测量本身改变未来状态,获取就成为动态决策问题的一部分,这超出了所研究的设定。

本文引出的实际优先级是一个比较,而不是一般规则。相关问题是:当前替代指标是否仍能改变为未来学习而测量的主结局,以及它留下的残余不确定性是否集中在所表示策略分歧的轮次上。KuaiRec 模式给出了预算背景:相对仅相关性获取的分离在 4 到 8 个百分点主结局预算时最清晰,在最低预算时较弱,因为初始化留给后续精炼的空间很小,而在高端再次收窄,因为两种方法都观察到多得多的主结局。

本文引用的文献

1

The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits

Audited Surrogate Bandit 在替代指标之前依据决策相关性设定获取水平,并在替代指标之后用估计的残余不确定性精炼它;对于 K 个动作上 N 个策略的有限类,其遗憾为 sqrt(KT log N)(1 + sqrt(T/B)) 量级,同时在 T 轮中恰好获取 B 次主结局;在一个替代指标不揭示更优动作的两动作族中,替代指标后获取实现有界遗憾,而替代指标前获取在相同预算下承受 T/B 量级的最坏情况遗憾。