arXiv:2608.04324cs.LGcs.AI2026-08

多目标推荐中按优先级排序,用低秩矩阵提升效率与性能。

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

  • 分目标建模低秩子空间,在线更新减少计算开销。
  • 理论证明每轮复杂度降至O(T),优于传统方法的O(T²)。
  • 适合多优先级决策场景,如个性化推荐与资源调度。

本文研究具有多个优先级目标的广义低秩矩阵强化学习问题。每轮中,学习者选择一个矩阵型动作并观测一个向量奖励,各分量对应不同优先级的目标。每个目标由特定的广义低秩矩阵模型控制,学习者依据字典序偏好评估动作,优先考虑高优先级目标。提出 extsc{Lexi-LowGLM} 算法,先估计各目标的低秩子空间,再在降维特征空间中进行字典序学习。相比传统单目标算法需重复使用全部历史数据求解批量广义线性估计,该算法通过在线牛顿步更新各目标估计器,将 $T$ 轮内的估计器更新复杂度从 $O(T^2)$ 降低至 $O(T)$。理论分析给出每个目标 $i o[m]$ 的遗憾界为 $ ilde Oig(W_i^{ m lex} oot m imes (d_1+d_2)r oot Tig)$,其中 $r$ 为参数矩阵秩的上界,$W_i^{ m lex}$ 表征字典序权衡效应。该界依赖于有效低秩维度 $(d_1+d_2)r$,而非环境维度 $d_1d_2$。数值实验验证了方法的有效性与计算高效性。

原文摘要 · Abstract (English)

This paper studies generalized low-rank matrix bandits with multiple prioritized objectives. At each round, the learner selects a matrix-valued arm and observes a vector-valued reward, whose components correspond to multiple objectives with different priority levels. Each objective is governed by an objective-specific generalized low-rank matrix model, and the learner evaluates arms according to a lexicographic preference order, prioritizing higher-level objectives before lower-level ones. We propose \textsc{Lexi-LowGLM}, an efficient online algorithm that first estimates objective-specific low-rank subspaces and then performs lexicographic learning in the reduced feature spaces. Unlike existing single-objective algorithms that repeatedly solve a batch generalized linear estimator using all historical observations, \textsc{Lexi-LowGLM} updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over $T$ rounds from $O(T^2)$ to $O(T)$. We establish a regret bound of $\widetilde O\left(W_i^{\rm lex}\sqrt{m}\,(d_1+d_2)r\sqrt{T}\right)$ for each objective $i\in[m]$, where $r$ is an upper bound on the ranks of the objective-specific parameter matrices and $W_i^{\rm lex}$ characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension $(d_1+d_2)r$ rather than the ambient dimension $d_1d_2$. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.

矩阵带宽多目标优化在线学习低秩建模

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