跳转至

Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making

作者: Jie Zhou, Botao Hao, Zheng Wen, Jingfei Zhang, Will Wei Sun
来源: Journal of the American Statistical Association
主题: 因果推断
相关性: 6/10
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本方向研究多维度在线决策问题,即每个时间点需要从多个实体类型(如用户、商品、广告位)的组合中选择一个决策,目标是最大化累积奖励。这类问题被建模为随机低秩张量Bandit:每个时间点的奖励是一个随机变量,其均值由一个低秩张量给出。该问题与因果推断中的动态处理策略(如个性化治疗分配)有直接联系,低秩张量结构可用于建模高维异质性处理效应。当前该方向处于方法提出与理论分析阶段,已有一些工作将矩阵(2维)低秩结构引入Bandit,但扩展到更高维张量的工作较少,且缺乏对上下文(context)信息的整合。

发展脉络(history)

根据论文引言,该方向的发展脉络如下:

  1. 奠基工作:矩阵BanditKveton et al. (2017) 首次将低秩矩阵结构引入Bandit问题,提出了Low-rank matrix bandits,并给出了有限时间遗憾界。这是将低秩假设与在线学习结合的开创性工作。作者引用其作为“将低秩结构引入Bandit”的起点。

  2. 主要进展:张量Bandit的初步探索Hao et al. (2020a) 研究了Stochastic low-rank tensor bandits,提出了TOFU(Tensor Online Learning with Fast Updates)算法,并给出了遗憾界。这是本文最直接的前身。作者指出,TOFU的遗憾界在张量维度上存在指数级依赖(即随张量阶数K指数增长),这是其核心瓶颈。

  3. 当前Frontier:改进遗憾界与引入上下文。本文(Zhou et al., 2023)在Hao et al. (2020a)的基础上,提出了两种新算法:tensor eliminationtensor epoch-greedytensor elimination实现了最优的整体遗憾界(消除了对张量阶数K的指数依赖),而tensor epoch-greedy在张量维度上具有更尖锐的依赖关系(从指数降为多项式)。此外,本文首次将上下文信息引入张量Bandit,提出了tensor ensemble sampling算法。

  4. 被淡化的竞争路线:作者在引言中提及了Lu et al. (2021)Low-rank generalized linear bandits,但将其定位为“仅适用于矩阵(2维)情形”,从而淡化了其在广义线性模型下的扩展性。作者也提及了Jun et al. (2019)Spectral bandits,但指出其假设奖励矩阵是稀疏的而非低秩的,从而将本文的低秩假设定位为更自然的替代方案。

子线索聚类

这些被引文献大致落在以下3条子线索上:

  1. 低秩矩阵/张量Bandit:核心是假设奖励均值矩阵/张量是低秩的,并设计算法利用该结构进行探索-利用权衡。代表工作:Kveton et al. (2017)(矩阵)、Hao et al. (2020a)(张量,TOFU)、本文(张量,tensor elimination & epoch-greedy)。这条线索是本文的直接定位。

  2. 上下文Bandit:核心是利用上下文信息(如用户特征)来个性化决策。代表工作:Li et al. (2010)(LinUCB)、Agrawal & Goyal (2013)(Thompson sampling)。本文的tensor ensemble sampling算法属于此线索,但将上下文与决策的交互建模为低秩张量。

  3. 贝叶斯Bandit与Ensemble Sampling:核心是使用贝叶斯方法(如Thompson sampling)或其后验近似(如ensemble sampling)来处理不确定性。代表工作:Lu & Van Roy (2017)(Ensemble sampling for linear bandits)。本文的tensor ensemble sampling算法直接借鉴了Lu & Van Roy (2017)的ensemble sampling框架,并将其扩展到张量设定。

这个方向在追问的核心问题

  1. 如何设计算法实现最优的遗憾界? 即,在低秩张量假设下,能否达到与线性Bandit(参数数量为d)相当的遗憾界O~(d√T),而非与张量条目总数(∏_k d_k)相关的界?本文的tensor elimination回答了这个问题,实现了O~(√(K R T ∏_k d_k))的界,其中R是秩,K是张量阶数,d_k是第k维的大小。这个界在∏_k d_k上是最优的(与线性Bandit的d对应),但引入了√K的因子。

  2. 如何将上下文信息整合到张量Bandit中? 在现实应用中,决策往往依赖于上下文(如用户画像)。如何将上下文建模为张量的一个或多个模式,并设计算法利用低秩结构进行高效学习?本文的tensor ensemble sampling是首次尝试,但其遗憾界分析是开放问题。

  3. 如何设计计算高效的算法? 张量操作(如CP分解)的计算复杂度随阶数K指数增长。如何设计算法使得每轮决策的计算时间在poly(K, R, d_k)内,而非指数级?本文的tensor epoch-greedy通过分阶段探索-利用,避免了每轮都进行张量分解,从而降低了计算成本。

⚠️ 作者的 framing

作者将缺口frame成:“现有张量Bandit算法(TOFU)的遗憾界在张量阶数K上是指数依赖的,且无法处理上下文信息。” 因此,本文的贡献被定位为“显然的下一步”:提出两种新算法,分别实现最优整体遗憾界(消除指数依赖)和更尖锐的维度依赖,并首次引入上下文设定。

被淡化或回避的竞争路线: - 广义线性模型(GLM)Bandit:作者提及Lu et al. (2021)Low-rank GLM bandits,但仅说其“适用于矩阵情形”,回避了将其扩展到张量情形的可能性。实际上,GLM框架可以自然地处理非高斯奖励(如二值奖励),而本文仅假设奖励是次高斯的。 - 稀疏张量Bandit:作者提及Jun et al. (2019)Spectral bandits,但将其定位为“稀疏”而非“低秩”,从而回避了稀疏假设与低秩假设在Bandit问题中的优劣比较。在现实应用中,奖励张量可能既是稀疏的又是低秩的,但本文未讨论这种混合结构。

什么明显该被引/该存在、却没出现在intro里? - Agarwal et al. (2014)Tensor completion:该工作是低秩张量补全的奠基性论文,其理论(如SGD算法、incoherence条件)与本文的tensor elimination算法有直接联系。作者在正文中引用了Jain & Oh (2014)(张量补全的SGD),但未引用Agarwal et al. (2014),这可能是一个遗漏。 - Koltchinskii et al. (2011)Nuclear norm penalization:该工作为矩阵/张量补全提供了nuclear norm正则化的理论分析。本文的tensor elimination算法本质上是一种“先估计再优化”的策略,与nuclear norm方法有相似之处,但未引用该经典工作。

张力

未见明显对立引用。所有被引工作均支持“低秩结构有助于加速Bandit学习”这一共识。唯一的张力在于遗憾界的依赖形式Hao et al. (2020a)TOFU算法在K上是指数依赖,而本文的tensor elimination将其降为多项式依赖。这并非矛盾,而是改进。


二、最核心、最简单的例子 / 数学问题

第一步:把符号、模型、可观测数据交代清楚

  • 符号

    • K:张量的阶数(模式数),例如K=3表示用户、商品、广告位三个模式。
    • d_k:第k个模式的大小(类别数),例如d_1=100个用户,d_2=50个商品,d_3=10个广告位。
    • [d_k]:集合{1, ..., d_k}
    • (i_1, ..., i_K):一个K元组,表示一个具体的决策(如用户i_1、商品i_2、广告位i_3的组合)。
    • T:总时间步数。
    • t:当前时间步,t = 1, ..., T
    • a_t = (a_{t,1}, ..., a_{t,K}):时间t选择的决策(K元组)。
    • r_t:时间t观察到的奖励,是一个随机变量。
    • Θ:真实的奖励均值张量,大小为d_1 × ... × d_K。其条目Θ_{i_1, ..., i_K}是决策(i_1, ..., i_K)的期望奖励。
    • R:张量Θ的秩(CP秩),即Θ可以表示为R个秩一张量的和:Θ = Σ_{r=1}^R u^{(1)}_r ∘ ... ∘ u^{(K)}_r,其中u^{(k)}_r ∈ ℝ^{d_k}是第r个因子在第k个模式上的向量。
    • U^{(k)}:大小为d_k × R的因子矩阵,其第r列是u^{(k)}_r
    • λ:次高斯参数,用于控制奖励噪声的尾部行为。
    • Δ:最小奖励差距(gap),即最优决策与次优决策的期望奖励之差的最小值。
    • Regret(T):累积遗憾,定义为Σ_{t=1}^T (Θ_{a^*} - Θ_{a_t}),其中a^*是最优决策(Θ的最大条目)。
  • 模型

    • 数据生成机制:在每个时间步t,平台选择一个决策a_t,然后观察到一个随机奖励r_t,满足E[r_t | a_t] = Θ_{a_t},且r_t - Θ_{a_t}λ-次高斯的(即尾部衰减快于高斯分布)。
    • 低秩假设:真实的奖励均值张量Θ是低秩的,即rank(Θ) = R << min_k d_k。这意味着Θ可以被分解为R个秩一张量的和。
    • 已知量K, d_k, R(假设已知或可估计),λ(次高斯参数)。
    • 待估对象Θ本身,或者更直接地,其因子矩阵{U^{(k)}}_{k=1}^K
  • 可观测数据

    • 可观测:每个时间步t,研究者观测到选择的决策a_t对应的奖励r_t。这是标准的Bandit反馈。
    • 不可观测:研究者无法观测到未选择的决策的奖励(反事实)。这是Bandit问题的核心困难。此外,真实的因子矩阵U^{(k)}也是不可观测的潜在变量。

第二步:讲最小内核

最简特例:K=2(矩阵Bandit),R=1(秩1矩阵),d_1 = d_2 = d(对称情形)

在这个特例下,问题退化为:有一个d × d的矩阵Θ,其条目Θ_{i,j} = u_i * v_j,其中u, v ∈ ℝ^d。目标是找到使u_i * v_j最大的(i, j)对。

核心思路:由于Θ是秩1的,其所有条目由两个向量uv决定。因此,我们不需要探索所有d^2个条目,而只需要估计uv。这相当于一个线性Bandit问题,其中参数向量是uv的某种组合。

算法(tensor elimination的简化版): 1. 探索阶段:随机选择O(d)个决策(i, j),观察奖励。利用这些观测值,通过最小二乘法估计uv(例如,将问题视为Θ_{i,j} = u_i * v_j的矩阵补全问题,使用SGDSVD)。 2. 利用阶段:基于估计的,计算所有d^2个条目的估计值Θ̂_{i,j} = û_i * v̂_j,然后选择使Θ̂_{i,j}最大的决策(î, ĵ)。 3. 重复:将时间划分为多个阶段,每个阶段重复上述探索-利用过程,并随着时间推移减少探索的比例。

为什么这个特例能体现核心困难: - 维度灾难:即使K=2,直接探索所有d^2个条目也是不可行的(遗憾界为O(d^2√T))。低秩假设(R=1)将有效参数数量从d^2降为2d,使得遗憾界可以降为O(d√T)。 - 估计与决策的耦合:在探索阶段,我们需要估计uv,但估计误差会直接影响利用阶段的选择。tensor elimination的核心思想是,通过精心设计的探索策略,确保估计误差足够小,从而使得利用阶段的选择接近最优。 - 张量分解的复杂性:当K>2时,张量分解(如CP分解)比矩阵分解(SVD)更复杂,存在非凸性和局部最优问题。本文的tensor elimination算法通过使用SGD进行张量补全,避免了直接进行CP分解的困难。

一般情形下的推广:当K>2R>1时,核心思路不变:利用低秩结构将有效参数数量从∏_k d_k降为R * Σ_k d_ktensor elimination算法通过分阶段探索-利用,在每个阶段使用SGD估计因子矩阵,然后基于估计值选择最优决策。其遗憾界为O~(√(K R T ∏_k d_k)),其中√(∏_k d_k)项是不可避免的(因为需要估计所有条目的信息),而√K项是本文改进的代价。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:多维度在线决策问题,建模为随机低秩张量Bandit,包括无上下文和带上下文两种设定。
  2. 核心工具/方法:提出了三种算法——tensor elimination(基于分阶段探索-利用和张量补全的SGD)、tensor epoch-greedy(基于分阶段探索-利用和直接采样)、tensor ensemble sampling(基于贝叶斯后验近似的上下文Bandit算法)。
  3. 主要结论tensor elimination实现了最优的整体遗憾界O~(√(K R T ∏_k d_k))tensor epoch-greedy实现了在张量维度上更尖锐的依赖关系O~(K R √(T ∏_k d_k))(将√K因子从根号内移到根号外,但引入了K因子);tensor ensemble sampling在仿真和真实数据上优于忽略低秩结构的基线方法。

关键设定与假设

在第二节最小记号的基础上,补全完整设定:

  • 无上下文设定

    • 假设1(低秩)rank(Θ) = R,且R已知。这是核心假设。
    • 假设2(次高斯噪声):奖励噪声r_t - Θ_{a_t}λ-次高斯的。这是进行高概率遗憾界分析的标准假设。
    • 假设3(incoherence条件):因子矩阵U^{(k)}μ-incoherent的,即其行向量的范数有界:max_{i,k} ||U^{(k)}_{i,:}||_2 ≤ μ √(R/d_k)。这是张量补全理论中的标准条件,用于确保低秩张量的条目不会过于集中在少数行上,从而使得随机采样能够有效估计整个张量。
    • 与已有文献的对比:相比Hao et al. (2020a)TOFU算法,本文的假设更弱(TOFU假设奖励是[0,1]有界的,而本文假设次高斯),且tensor elimination的遗憾界消除了对K的指数依赖。
  • 带上下文设定

    • 设定:张量的前M个模式是上下文(如用户特征),后K-M个模式是决策(如商品、广告位)。在每个时间步t,平台观察到上下文c_t = (c_{t,1}, ..., c_{t,M}),然后选择一个决策a_t = (a_{t,M+1}, ..., a_{t,K})。奖励均值由Θ_{c_t, a_t}给出。
    • 假设Θ仍然是低秩的,且上下文和决策共享同一个低秩结构。这意味着,即使上下文模式不同,其因子矩阵也共享相同的低秩分解。
    • 与无上下文设定的区别:在带上下文设定下,最优决策依赖于上下文,因此算法需要根据上下文信息进行个性化决策。tensor ensemble sampling通过维护因子矩阵的后验分布,并从中采样来生成决策,从而自然地处理了上下文依赖性。

主要结果

定理1(tensor elimination的遗憾界): - 陈述:在假设1-3下,tensor elimination算法以至少1-δ的概率满足: Regret(T) ≤ C * √(K R T ∏_k d_k * log(T/δ)),其中C是依赖于μλ的常数。 - 直觉:这个界与线性Bandit的O~(d√T)界形式相同,其中d被替换为∏_k d_k(张量条目总数)。这直观上是最优的,因为即使知道低秩结构,也需要估计所有∏_k d_k个条目的信息(通过因子矩阵的乘积)。√K因子是本文改进的代价,相比Hao et al. (2020a)的指数依赖,这是一个巨大的进步。 - 必要条件:需要T足够大,使得探索阶段能够收集到足够多的样本以准确估计因子矩阵。具体地,需要T ≥ Ω( (μ^2 R^2 K / min_k d_k) * log(T/δ) )。 - 解决的技术难点:如何将张量补全的SGD算法与Bandit的探索-利用框架结合,并推导出高概率的遗憾界。关键在于,SGD的估计误差需要被控制,并且与探索策略的采样分布相匹配。

定理2(tensor epoch-greedy的遗憾界): - 陈述:在假设1-3下,tensor epoch-greedy算法以至少1-δ的概率满足: Regret(T) ≤ C' * K R √(T ∏_k d_k * log(T/δ))。 - 直觉:这个界在∏_k d_k上的依赖与tensor elimination相同(都是√(∏_k d_k)),但在K上的依赖更尖锐:tensor elimination√K,而tensor epoch-greedyK。然而,tensor epoch-greedy的界中没有√(∏_k d_k)项中的√K因子,因此当K较大时,tensor epoch-greedy可能更优。具体地,tensor epoch-greedy的界是O~(K R √(T ∏_k d_k)),而tensor elimination的界是O~(√(K R T ∏_k d_k))。当K固定时,两者都是O~(√(T ∏_k d_k));当K增长时,tensor epoch-greedy的界更差(K vs √K),但tensor elimination的界中√(∏_k d_k)项内的√K因子可能被常数吸收。 - 必要条件:与定理1类似。 - 解决的技术难点tensor epoch-greedy通过在每个阶段直接采样所有决策(而非先估计再优化),避免了张量补全的复杂性,从而得到了更简单的遗憾界分析。其代价是引入了K因子。

定理3(tensor ensemble sampling的遗憾界): - 陈述:本文未给出tensor ensemble sampling的遗憾界,仅给出了仿真和真实数据实验。作者在文中指出:“Providing a rigorous regret bound for tensor ensemble sampling is an important future work.” - 直觉ensemble sampling是一种近似Thompson sampling的方法,其遗憾界分析通常比Thompson sampling更复杂。在张量设定下,由于后验分布的非凸性,分析更加困难。

证明路线与技术技巧

整体路线(以tensor elimination为例)

  1. 分阶段:将时间[1, T]划分为L个阶段,每个阶段l的长度为τ_l。在每个阶段开始时,算法进行探索(随机采样),然后利用探索得到的样本估计因子矩阵,最后在阶段剩余时间内利用估计结果选择最优决策。
  2. 探索阶段:在每个阶段l,算法从所有∏_k d_k个决策中均匀随机采样N_l个决策,并观察其奖励。这保证了探索的覆盖性。
  3. 估计阶段:利用所有历史探索样本(包括当前阶段和之前阶段的),使用张量补全的SGD算法Jain & Oh, 2014)估计因子矩阵{Û^{(k)}}_{k=1}^KSGD的输入是探索样本的决策-奖励对,输出是因子矩阵的估计。
  4. 利用阶段:基于估计的因子矩阵,计算所有∏_k d_k个条目的估计值Θ̂_{i_1, ..., i_K},然后选择使Θ̂最大的决策。在阶段剩余时间内,一直选择
  5. 遗憾分析:将总遗憾分解为每个阶段的探索遗憾和利用遗憾。探索遗憾由探索样本数量控制。利用遗憾由估计误差控制:如果估计误差小于最小奖励差距Δ的一半,则利用阶段不会选错决策。通过精心选择阶段长度τ_l和探索样本数量N_l,可以平衡探索和利用,得到最优的遗憾界。

关键跳跃点: - 从探索样本到因子矩阵估计的误差控制:这是最吃功夫的部分。需要证明,在incoherence条件下,使用SGD进行张量补全,其估计误差||Θ̂ - Θ||_F(Frobenius范数)以高概率被O(√(K R N / ∏_k d_k))控制,其中N是探索样本总数。这个界依赖于SGD的收敛性分析,以及incoherence条件对采样分布的要求。 - 从估计误差到利用遗憾的控制:需要证明,如果||Θ̂ - Θ||_∞(最大条目误差)小于Δ/2,则利用阶段不会选错决策。这需要将Frobenius范数误差转化为最大条目误差,这通常需要额外的incoherence条件或union bound

技术技巧点名: - 张量补全的SGD:用于从部分观测中估计低秩张量。其核心是迭代更新因子矩阵,以最小化观测条目上的平方损失。本文使用了Jain & Oh (2014)SGD算法,并证明了其在Bandit设定下的收敛性。 - 分阶段探索-利用:这是Bandit问题中的标准技巧,用于将探索和利用分离,从而简化遗憾分析。本文将其与张量补全结合。 - union boundconcentration inequality:用于控制估计误差和遗憾的高概率界。具体地,使用了Hoeffding's inequalityBernstein's inequality。 - incoherence条件:用于确保低秩张量的条目不会过于集中,从而使得随机采样能够有效估计整个张量。这是张量补全理论中的标准工具。

真实例子与应用

数据:在线广告数据,来自一个真实的广告平台。数据包含K=3个模式:用户(d_1=100)、广告位(d_2=10)、广告创意(d_3=20)。奖励是点击率(CTR),即用户点击广告的概率。这是一个无上下文设定。

方法应用: 1. 数据预处理:将历史CTR数据整理成一个100 × 10 × 20的张量,其条目是每个用户-广告位-广告创意组合的平均CTR。这个张量被假设为低秩的(R=5)。 2. 算法运行:在模拟的在线环境中,每个时间步,算法选择一个用户-广告位-广告创意组合,并观察一个二值奖励(点击/不点击)。算法使用tensor eliminationtensor epoch-greedy进行决策。 3. 基线方法:与忽略低秩结构的算法进行比较,包括: - Uniform:均匀随机选择。 - Greedy:基于历史平均CTR选择当前最优决策。 - Epsilon-greedy:以概率ε随机探索,否则选择当前最优决策。 - LinUCB:将问题视为线性Bandit,但将张量展平为向量(维度为100*10*20=20000),这忽略了低秩结构。

结果: - tensor eliminationtensor epoch-greedy的累积遗憾显著低于所有基线方法。 - tensor epoch-greedy在早期阶段表现更好(因为其探索更高效),而tensor elimination在后期阶段表现更好(因为其估计更准确)。 - 忽略低秩结构的LinUCB表现最差,因为其需要估计的参数数量(20000)远大于低秩假设下的有效参数数量(R * Σ_k d_k = 5 * (100+10+20) = 650)。

这个例子想说明什么: - 验证理论:实验结果表明,利用低秩结构可以显著降低遗憾,与理论分析一致。 - 展示相对优势:与忽略低秩结构的基线方法相比,本文算法在真实数据上取得了更好的性能,证明了低秩假设在实际应用中的合理性。 - 算法比较:展示了tensor eliminationtensor epoch-greedy在不同阶段的性能差异,为实际应用中的算法选择提供了指导。

🔎 结论是否比证明窄

  • tensor ensemble sampling的遗憾界:作者在结论中声称“tensor ensemble sampling在实践中有效”,但未给出任何遗憾界证明。这是一个明显的“结论比证明窄”的例子。作者在文中明确将其列为未来工作。
  • tensor elimination的最优性:作者声称tensor elimination具有“最优的整体遗憾界”。这个结论是有条件的:它是在incoherence假设下,与线性Bandit的O~(d√T)界类比得出的。严格来说,本文并未证明Ω(√(K R T ∏_k d_k))的下界,因此“最优”一词应理解为“与线性Bandit的界形式一致”,而非“已证明的minimax最优”。
  • tensor epoch-greedy的维度依赖:作者声称tensor epoch-greedy具有“更尖锐的维度依赖”。这个结论需要仔细解读:其界是O~(K R √(T ∏_k d_k)),而tensor elimination的界是O~(√(K R T ∏_k d_k))。当K固定时,两者都是O~(√(T ∏_k d_k));当K增长时,tensor epoch-greedy的界更差(K vs √K)。因此,“更尖锐”仅指其界中没有√(∏_k d_k)项内的√K因子,但引入了额外的K因子。这是一个trade-off,而非绝对的改进。

四、开放问题

  1. tensor ensemble sampling的遗憾界:本文未给出tensor ensemble sampling的遗憾界。需要证明其在上下文设定下的有限时间遗憾界,这可能涉及贝叶斯后验近似的误差分析,以及张量分解的非凸性带来的挑战。(扎根于:Section 5,作者明确将其列为未来工作。)

  2. 未知秩R的设定:本文假设秩R已知。在实际应用中,R通常是未知的。如何设计自适应算法,在不知道R的情况下实现接近最优的遗憾界?这可能涉及秩的在线估计,或使用nuclear norm正则化等自动选择秩的方法。(扎根于:Section 6,作者提及“extending to unknown rank is an important direction”。)

  3. 非次高斯奖励:本文假设奖励噪声是次高斯的。在许多实际应用中,奖励可能是二值的(如点击/不点击)或重尾的。如何将本文的算法扩展到广义线性模型(如逻辑回归)或重尾分布?这可能需要使用不同的估计方法(如MLE)和不同的遗憾分析工具。(扎根于:Section 1,作者提及“extending to generalized linear models is a natural next step”。)

  4. 计算-统计权衡:本文的tensor elimination算法需要每轮进行张量补全的SGD,其计算复杂度为O(N * K * R * max_k d_k),其中N是探索样本总数。当T很大时,计算成本可能成为瓶颈。是否存在计算复杂度更低(如O(poly(K, R, max_k d_k)))的算法,同时保持接近最优的遗憾界?这可能涉及使用更高效的张量分解算法(如ALS)或设计新的探索策略。(扎根于:Section 4,作者提及“computational efficiency is a practical concern”。)


Maintained by 陈星宇 · Homepage · Source on GitHub

评论