带有部分观测动作的随机线性赌博机

# 随机部分观测动作的线性赌博机††感谢：本工作主要是在Vineet Gattani于亚利桑那州立大学攻读博士学位期间完成的，并部分得到美国国家科学基金会奖CCF-2048223的支持。来源：https://arxiv.org/html/2607.08971

###### 摘要

随机线性赌博机（其中动作表示为向量，奖励为线性函数）是序贯决策制定的核心范式。我们研究了该问题的一个部分观测变体，其中学习智能体对于每个动作仅能看到一个随机坐标子集。这种部分观测性在推荐系统和医疗保健等场景中自然出现，因为在这些场景中，获取完整的动作描述可能成本高昂甚至不可能。通常，这使得次线性遗憾在信息论上不可能实现。然而，我们证明，当动作向量具有低本征维度时，可以克服这一障碍。我们提出了一种算法TOFU-POV，它利用掩码动作估计潜在动作子空间，使用按轮次冻结的表示填充当前动作，并在由此产生的低维坐标中运行OFUL。我们的理论表明，TOFU-POV享有与动作子空间本征维度（而非环境维度）成比例的T√T遗憾，并量化了这些量之间以及与缺失性、决策集大小和子空间条件数之间的相互作用。我们还设计了一种秩自适应算法，该算法无需知道本征维度。我们通过一个基于新颖乘积结构的下界来补充这些保证，该结构将通常的奖励学习不确定性与部分观测所固有的、依赖于缺失性的代价区分开来。合成数据和真实数据的实验支持我们的理论，并表明TOFU-POV可以在这一具有挑战性的问题上显著优于自然基线。

## 1 引言

随机线性赌博机（SLB）是不确定性下序贯决策制定的重要框架，其中向量值动作的期望奖励被假定为其特征的线性函数 [1 (https://arxiv.org/html/2607.08971#bib.bib1), 2 (https://arxiv.org/html/2607.08971#bib.bib2), 3 (https://arxiv.org/html/2607.08971#bib.bib3)]。在每个回合t，学习智能体被呈现一个决策集Dt={Xt,1,Xt,2,...}并选择一个动作Xt∈Dt，这产生奖励rt=⟨Xt,θ⋆⟩+ηt，其中θ⋆∈Rd未知，ηt是条件零均值随机噪声。这里的目标是最小化相对于一个预言机的累积遗憾，该预言机（a）知道θ⋆，因此（b）每一轮都选择Dt中最大化期望奖励的动作。该设置中一个被广泛研究的算法是OFUL [1 (https://arxiv.org/html/2607.08971#bib.bib1)]，其遗憾已知由O~(dT)界定，与已知下界匹配至对数因子。SLB已在推荐系统、广告和医疗分配等领域得到广泛应用 [4 (https://arxiv.org/html/2607.08971#bib.bib4), 5 (https://arxiv.org/html/2607.08971#bib.bib5), 6 (https://arxiv.org/html/2607.08971#bib.bib6)]。

然而，在许多现代应用中，观察每个动作的完整特征向量过于昂贵、不可行或不可能。在推荐系统中 [4 (https://arxiv.org/html/2607.08971#bib.bib4)]，由于隐私、存储或计算限制，可能只能访问物品特征的一个稀疏子集。类似地，在科学或医疗保健应用中，感测或数据收集的限制自然会导致观测缺失。这引出了SLB问题的一个更具挑战性的变体，其中在每个回合，智能体仅观察每个动作向量的一个子集条目——我们称之为*部分观测性*。形式上，对于每个动作向量Xt∈Rd，每个坐标独立地以概率p∈(0,1]被揭示。如果没有进一步的结构，这里的奖励学习在信息论上是不可能的：智能体无法推断完整的线性奖励模型，并会支付一个随时间呈线性的次优性代价（即遗憾）。

幸运的是，许多现实世界问题表现出低维结构。例如，在推荐系统中，用户-物品交互通常由少数潜在因素控制，这意味着真实的特征向量位于一个低维子空间附近。受此启发，我们研究*有限可观测性*和*低秩结构*下的SLB问题：我们假设理想的（完全观测的）动作向量X∈Rd位于一个未知的m维子空间中，其中m可能远小于d。我们的设置介于两条研究路线之间，但并未被其涵盖。最近关于具有部分观测特征的赌博机的工作 [7 (https://arxiv.org/html/2607.08971#bib.bib7), 8 (https://arxiv.org/html/2607.08971#bib.bib8)] 研究了不同的观测模型，其中缺失或潜在成分以规定的方式进入奖励问题。相比之下，在这里，动作本身位于一个低维子空间，学习器看到（变化的）每个提供动作的随机坐标掩码。[9 (https://arxiv.org/html/2607.08971#bib.bib9)] 研究了低秩动作表示赌博机问题，其中动作向量是*完全观测的*，并采用投影OFUL式的分析来为其算法PSLB获得遗憾保证。这与我们的方法不同，我们的方法创建潜在动作子空间的估计，并使用按轮次冻结的子空间表示为每一组动作进行插补。然后我们证明，在每个轮次内，我们都有一个近似线性赌博机，其近似误差可以被仔细控制以获得我们的遗憾保证。

还有一个技术原因需要小心直接引入投影OFUL分析。如果估计的投影随时间更新并应用于过去的数据，那么投影噪声过程不是OFUL中使用的标准可预测鞅变换，并且投影设计不再通过通常的秩一更新演化。此外，当所选动作是由OFU规则选择时，所选动作的协方差矩阵的下特征值增长不能从提供动作的总体协方差推断出来。这就是为什么TOFU-POV在轮次内冻结表示：条件于轮次开始的估计，奖励学习是一个普通的固定坐标OFUL问题，而子空间和插补错误被分别控制。我们在附录A (https://arxiv.org/html/2607.08971#A1) 中给出了详细比较。

我们首先概述我们论文的**主要贡献**。

- • **问题表述。** 我们表述了部分观测的低秩SLB问题，其中每个提供的动作位于Rd的一个未知m维子空间中，但学习器仅观察到其特征的一个随机子集（由独立的坐标掩码决定）。
- • **算法。** 我们引入了TOFU-POV，一种按轮次的算法，它从所有提供的掩码动作中估计潜在子空间，在每个轮次内冻结表示，填充当前动作集，并在由此产生的低维坐标中运行OFUL。
- • **遗憾保证。** 当m已知时，在标准非相干条件和标准化BX,‖θ⋆‖=O(1)下，我们证明，以高概率，TOFU-POV的遗憾缩放为 O~(κ2mp4K+mT+κmTp2K)，其中κ衡量动作协方差矩阵的条件数（见第3节）。等效地，忽略不随T增长的额外预热成本，有效缩放为O~(mT+κmT/(p2K))。这个界限将环境维度d替换为通常更小的m，同时揭示了缺失性p、决策集大小K和子空间条件数κ如何影响遗憾。为了实现这一点，我们基于轮次的论证将OFUL的统计困难性与一个受控的误设项分开。正如我们在附录A (https://arxiv.org/html/2607.08971#A1) 中所展示的，这解决了投影低秩赌博机论证中的关键障碍。
- • **秩自适应。** 我们还设计了一个TOFU-POV的秩自适应变体，它不需要知道m（也不需要其上界），并享有相同的遗憾缩放；秩识别成本，在常数范围内，被吸收到插补预热中。
- • **下界。** 我们通过一个新颖的论证为下界补充了上界，该论证将通常的奖励不确定性与一个缺失发现成本分开。
- • **实验。** 我们在合成和真实数据上评估了TOFU-POV及其自然变体。结果证实了我们的理论，在更严重的缺失下，相对于基线的最大提升出现。

## 2 相关工作

**结构化线性赌博机。** 线性随机赌博机通常以环境特征维度d进行分析 [1 (https://arxiv.org/html/2607.08971#bib.bib1), 3 (https://arxiv.org/html/2607.08971#bib.bib3)]。大量文献通过施加结构来减少这种依赖，包括θ⋆的稀疏性 [10 (https://arxiv.org/html/2607.08971#bib.bib10), 11 (https://arxiv.org/html/2607.08971#bib.bib11), 12 (https://arxiv.org/html/2607.08971#bib.bib12), 13 (https://arxiv.org/html/2607.08971#bib.bib13)] 以及低秩矩阵或双线性奖励结构 [14 (https://arxiv.org/html/2607.08971#bib.bib14), 15 (https://arxiv.org/html/2607.08971#bib.bib15), 16 (https://arxiv.org/html/2607.08971#bib.bib16), 17 (https://arxiv.org/html/2607.08971#bib.bib17)]。这些利用参数结构，而我们的设置利用动作向量本身的低秩结构。动作空间上的其他类型结构，例如谱结构，同样已知有助于遗憾和纯探索性能 [18 (https://arxiv.org/html/2607.08971#bib.bib18), 19 (https://arxiv.org/html/2607.08971#bib.bib19), 20 (https://arxiv.org/html/2607.08971#bib.bib20)]。

**低秩动作表示。** 最接近的前驱是Lale等人 [9 (https://arxiv.org/html/2607.08971#bib.bib9)]，他们研究了具有完全观测、近似低秩动作表示的线性赌博机。我们的范式添加了坐标级缺失，但区别不仅仅是建模：一个带有持续更新投影的直接投影OFUL证明不会自动继承标准的自归一化或椭圆势参数。我们的按轮次构造通过冻结每个轮次内的表示并仔细控制由此产生的表示偏差来避免这一点；有关此比较的更多细节，请参见附录A (https://arxiv.org/html/2607.08971#A1)。

**具有部分观测特征的赌博机。** 最近的工作也研究了具有部分观测或潜在特征的赌博机 [7 (https://arxiv.org/html/2607.08971#bib.bib7), 8 (https://arxiv.org/html/2607.08971#bib.bib8)]，但在不同的观测模型下。在这些设置中，缺失或潜在成分通过规定的结构或已知的感测通道进入奖励问题。相比之下，TOFU-POV假设动作向量本身位于一个未知的低秩子空间中，而每个提供的臂通过随机的、与臂和时间相关的坐标掩码被揭示。

**含缺失数据的子空间估计。** 我们的工作也与从不完整观测中进行子空间估计有关，这已被广泛研究，无论是在离线环境如矩阵补全 [21 (https://arxiv.org/html/2607.08971#bib.bib21)] 和鲁棒PCA [22 (https://arxiv.org/html/2607.08971#bib.bib22)]，还是在线或流式环境中使用方法如Oja算法 [23 (https://arxiv.org/html/2607.08971#bib.bib23)]、GROUSE [24 (https://arxiv.org/html/2607.08971#bib.bib24)] 和PETRELS [25 (https://arxiv.org/html/2607.08971#bib.bib25)]。最近的高维分析也对几个此类在线更新给出了统一视角 [26 (https://arxiv.org/html/2607.08971#bib.bib26)]。我们使用一些类似的技术，但我们的重点是控制由近似子空间估计引起的偏差及其与在线算法遗憾的相互作用。

## 3 问题设置

**低维动作向量模型。** 对于自然数n∈N，令[n]:={1,2,...,n}。我们考虑一个为期T轮的d维随机线性赌博机，并假设理想的动作向量位于Rd的一个未知m维子空间中。令U∈Rd×m为该未知子空间的一个标准正交基。在每个回合t∈[T]，生成一个理想决策集Dt:={Xt,1,...,Xt,K}，其中理想动作向量Xt,i（跨臂和回合）从一个支撑在span(U)上的固定分布中独立同分布地抽取。我们对此分布做出以下两个假设。

###### 假设1（有界动作）存在已知常数BX，使得对于所有t∈[T]和i∈[K]，几乎必然有‖Xt,i‖2≤BX。

###### 假设2（动作协方差秩）协方差矩阵Σ:=E[Xt,iXt,i⊤]的秩为m，且其非零特征值满足λ̄≥λ1≥⋯≥λm>0，对于某个常数λ̄>0。如同赌博机文献中的标准做法 [5 (https://arxiv.org/html/2607.08971#bib.bib5), 27 (https://arxiv.org/html/2607.08971#bib.bib27), 28 (https://arxiv.org/html/2607.08971#bib.bib28), 29 (https://arxiv.org/html/2607.08971#bib.bib29), 1 (https://arxiv.org/html/2607.08971#bib.bib1)]，我们将假设BX=O(1)且算法已知。假设2表明动作分布激励了潜在子空间的每个方向，并提供其能量的一个包络。我们注意到λ̄不必已知：由于λ1≤E‖Xt,i‖22≤BX2，总可取λ̄=BX2，更精确的包络只会收紧我们的界限。

**例子。** 满足这些假设的一个自然设置是以下加载矩阵模型
Xt,i=UΛZt,i,  (1)
其中Λ∈Rm×m是一个固定对角加载矩阵，潜在向量Zt,i∈Rm独立同分布，且E[Zt,i]=0, E[Zt,iZt,i⊤]⪰νIm对于某个ν>0，以及几乎必然‖Zt,i‖∞≤BZ。该模型满足假设1，其中BX=maxj∈[m]|Λjj|mBZ，和假设2，其中λm≥νminj∈[m]Λjj2。

**动作协方差的条件数。** 重要的是要注意