在部分观测下实现线性推荐的低误差学习,突破信息瓶颈。
Stochastic Linear Bandits with Partially Observed Actions

- 通过掩码动作估计潜在子空间,用冻结表示填补缺失
- 理论证明$\ ext{regret} = O(\sqrt{T})$,依赖内在维度而非全维
- 适用于推荐、医疗等高维但结构简单的场景
随机线性贝叶斯问题中,动作由向量表示,奖励为线性关系,是序列决策的核心范式。本文研究一种部分观测变体:学习者仅能观测每个动作的随机子集坐标。此类部分可观测性自然出现在推荐与医疗等场景,因完整动作描述可能昂贵或不可得。一般情况下,亚线性遗憾在信息论上不可能实现。然而,当动作向量具有低内在维度时,该障碍可被克服。本文提出算法TOFU-POV:利用掩码动作估计隐含动作子空间,以周期冻结表示填补当前动作,并在低维坐标中运行OFUL。理论表明,TOFU-POV的$\ ext{regret} = O(\sqrt{T})$,其尺度依赖于内在子空间维度而非环境维度,并量化了该维度与缺失率、决策集大小、子空间条件数之间的交互关系。我们还设计了一种无需预知内在维度的自适应秩算法。通过新颖的产品构造推导出下界,分离了常规奖励学习不确定性与由缺失引起的固有成本。合成与真实数据实验支持理论分析,显示TOFU-POV在该挑战性问题中显著优于自然基线。
原文摘要 · Abstract (English)
The stochastic linear bandit, where actions are represented as vectors and rewards are linear, is a central paradigm for sequential decision making. We study a partially observed variant of this problem in which the learning agent only sees a random subset of coordinates for each action. Such partial observability arises naturally in settings like recommendation and healthcare, where full action descriptions can be expensive or even impossible to obtain. In general, this makes sublinear regret information-theoretically impossible. However, we show that this barrier can be overcome when the action vectors have low intrinsic dimension. We propose an algorithm, TOFU-POV, that estimates the latent action subspace using the masked actions, imputes current actions using an epoch-wise frozen representation, and runs OFUL in the resulting low-dimensional coordinates. Our theory shows that TOFU-POV enjoys a $\sqrt{T}$ regret that scales with the intrinsic action subspace dimension as opposed to the ambient dimension and quantifies the interaction between these quantities and the missingness, decision set size, and subspace conditioning. We also devise a rank-adaptive algorithm that does not require the knowledge of the intrinsic dimension. We complement these guarantees with a lower bound based on a novel product construction that separates usual reward-learning uncertainty from a missingness-dependent cost intrinsic to partial observation. Synthetic and real data experiments support our theory and show that TOFU-POV can substantially improve upon natural baselines in this challenging problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。