arXiv:2502.06142stat.MLcs.LG2025-02ICML被引 3

解决特征部分不可见时的线性强化学习问题,实现更优的长期收益。

Linear Bandits with Partially Observable Features

  • 通过补充正交基向量增强特征,构建完整表示空间。
  • 理论证明算法在时间T内仅产生约sqrt((d+d_h)T)的次线性遗憾。
  • 无需事先知道隐藏特征,适用于动态隐藏场景。

我们研究了存在部分可观测特征的线性老虎机问题。若不妥善处理,未观测特征会因对奖励的影响未知而导致线性遗憾。为此,我们提出一种新理论框架与算法,具备次线性遗憾保证。核心方法包括:(i) 特征扩充,通过添加与已观测特征行空间正交的基向量;(ii) 引入双重稳健估计器。该算法达到遗憾界$ ilde{O}(ig( ext{d} + ext{d}_ ext{h}ig)T)$,其中$ ext{d}$为可观测特征维度,$ ext{d}_ ext{h}$反映未观测特征空间被观测空间包含的程度,从而刻画问题内在难度。值得注意的是,算法无需预先知晓未观测特征空间,该空间可随更多特征被隐藏而扩展。数值实验表明,本算法优于非上下文多臂老虎机及仅依赖可观测特征的线性老虎机算法。

原文摘要 · Abstract (English)

We study the linear bandit problem that accounts for partially observable features. Without proper handling, unobserved features can lead to linear regret in the decision horizon $T$, as their influence on rewards is unknown. To tackle this challenge, we propose a novel theoretical framework and an algorithm with sublinear regret guarantees. The core of our algorithm consists of (i) feature augmentation, by appending basis vectors that are orthogonal to the row space of the observed features; and (ii) the introduction of a doubly robust estimator. Our approach achieves a regret bound of $\tilde{O}(\sqrt{(d + d_h)T})$, where $d$ is the dimension of the observed features and $d_h$ depends on the extent to which the unobserved feature space is contained in the observed one, thereby capturing the intrinsic difficulty of the problem. Notably, our algorithm requires no prior knowledge of the unobserved feature space, which may expand as more features become hidden. Numerical experiments confirm that our algorithm outperforms both non-contextual multi-armed bandits and linear bandit algorithms depending solely on observed features.

强化学习线性带宽部分可观测

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。