효율적인 온라인 레키시코그래픽 일반화된 저랭크 행렬 멀티-암드 반딧불 문제

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

본 논문에서는 여러 우선순위를 가진 목표를 가지는 일반화된 저랭크 행렬 멀티-암드 반딧불 문제를 다룬다. 각 라운드마다, 학습자는 행렬 값을 갖는 암을 선택하고 벡터 값을 갖는 보상을 관찰하는데, 이 벡터의 구성 요소들은 서로 다른 우선순위 수준을 가진 여러 목표에 해당한다. 각 목표는 목표별 일반화된 저랭크 행렬 모델로 표현되며, 학습자는 레키시코그래픽 선호 순서에 따라 암을 평가하며, 더 높은 수준의 목표를 낮은 수준의 목표보다 먼저 고려한다. 우리는 extsc{Lexi-LowGLM}이라는 효율적인 온라인 알고리즘을 제안하는데, 이 알고리즘은 먼저 목표별 저랭크 부분 공간을 추정하고, 그 다음 축소된 특징 공간에서 레키시코그래픽 학습을 수행한다. 기존의 단일 목표 알고리즘이 모든 과거 관찰값을 사용하여 반복적으로 배치 일반화 선형 추정기를 해결하는 것과 달리, extsc{Lexi-LowGLM}은 각 목표별 추정기를 온라인 뉴턴 스텝을 통해 업데이트하여 $T$ 라운드 동안 추정기 업데이트 복잡도를 $O(T^2)$에서 $O(T)$로 줄인다. 우리는 각 목표 $i ext{ }orall ext{ }i ext{ } ext{in} ext{[}m ext{]}$에 대해 $ ilde Oigl(W_i^{ m lex} tag{m} tag{(d_1+d_2)r tag{ au}Tigr)$의 후회 경계를 제시하며, 여기서 $r$은 목표별 파라미터 행렬의 랭크에 대한 상한이며, $W_i^{ m lex}$는 레키시코그래픽 트레이드오프 효과를 나타낸다. 이 경계는 실제 차원인 $d_1d_2$가 아닌, 효과적인 저랭크 차원 $(d_1+d_2)r$에 의존한다. 수치 실험을 통해 제안된 방법의 효과성과 계산 효율성을 추가적으로 검증하였다.

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.