提出部分反馈在线学习新范式，解决标签观测受限下的学习难题
Partial Feedback Online Learning
- 用集合版本空间替代传统版本空间，处理每轮仅观测一个可接受标签的情况
- 定义PFLdim和PMSdim，分别精确刻画确定性与随机学习者的最坏情况后悔率
- 揭示确定性与随机学习等价的条件，解决公开问题，并指出超集合可实现性的障碍
我们研究一种新型学习协议——部分反馈在线学习，其中每个实例对应一组可接受标签，但学习者每轮仅观测到其中一个可接受标签。我们指出，经典版本空间在该设置下无法直接适用。为此，我们引入集合版本空间，维护假设集合而非单个假设。利用这一工具，我们实现了在集合可实现情形下的学习性紧致刻画。具体地，我们定义了部分反馈Littlestone维数（PFLdim）和部分反馈测度破碎维数（PMSdim），分别精确刻画确定性与随机学习者的最小最大后悔率。此外，我们识别出一个嵌套包含条件，在此条件下确定性与随机学习性等价，从而解决了Raman等人（2024b）提出的开放问题。最后，对于任意假设空间H，我们证明：超出集合可实现性时，即使|H|=2，最小最大后悔率仍可能为线性，揭示了超越集合可实现性的根本障碍。
原文摘要 · Abstract (English)
We study a new learning protocol, termed partial-feedback online learning, where each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round. We highlight that, while classical version space is widely used for online learnability, it does not directly extend to this setting. We address this obstacle by introducing a collection version space, which maintains sets of hypotheses rather than individual hypotheses. Using this tool, we obtain a tight characterization of learnability in the set-realizable regime. In particular, we define the Partial-Feedback Littlestone dimension (PFLdim) and the Partial-Feedback Measure Shattering dimension (PMSdim), and show that they tightly characterize the minimax regret for deterministic and randomized learners, respectively. We further identify a nested inclusion condition under which deterministic and randomized learnability coincide, resolving an open question of Raman et al. (2024b). Finally, given a hypothesis space H, we show that beyond set realizability, the minimax regret can be linear even when |H|=2, highlighting a barrier beyond set realizability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。