从正确示范中学习,实现无时限的连续奖励鲁棒性。
Multiscale Reward Hedging from Correct Demonstrations
- 在多尺度上共享投票,通过容忍性最优测试进行奖励对冲。
- 首次获得连续奖励类别的无时域保证,总偏差为O(d log A)。
- 适合无结构限制的推荐系统,尤其适用于高维线性上下文场景。
从正确示范中学习比监督学习更难:预测后仅能观察到一个有效答案,却无法判断自身答案是否有效,也无法获得奖励。现有奖励对冲保证通常依赖有限奖励类。本文首次给出连续类的无时域保证。核心是于每个精度尺度上,在容忍性最优测试中进行共享投票。目标奖励在每尺度有一个存活代理,若预测误差超过该尺度,则代理数量翻倍。由此得到同时尾部界 $|\{t:\ ext{ℓ}_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j$,其中 $\mathcal G$ 为最优性差距函数类。积分尾部得累积隐藏误差受度量熵积分控制,与轮次无关。多项式熵 $(A/ε)^d$ 导致总误差 $O(d\log A)$ 及 $O(d/m)$ 快速统计速率。对有界线性上下文推荐,结果为任意紧菜单下的 $O(d)$ 期望后悔。这是首个无需菜单结构假设的多项式有限后悔界,代价为非正则预测。虽然一般投票开销大,但在一维Lipschitz参数曲线上为多项式时间。固定半径秩二推荐耗时 $O(KT^2)$(菜单大小 $K$)。还证明了 $Ω(d)$ 下界、低秩及有界ReLU网络推论,以及仅增加演示者累积次优性的鲁棒定理。可复现自适应压力测试验证了预测尺度适应性。分解后,对十用户电影评分数据集的精确审计仅需1.7秒CPU时间,且平均隐含差距优于示范评分策略与正规在线基线。
原文摘要 · Abstract (English)
Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound $|\{t:\ell_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j$, where $\mathcal G$ is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy $(A/ε)^d$ gives $O(d\log A)$ total gap and a fast $O(d/m)$ statistical rate. For bounded linear contextual recommendation, the result is $O(d)$ regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes $O(KT^2)$ time for menus of size $K$. We also prove an $Ω(d)$ lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。