문맥적 밴딧(Contextual Bandits)을 위한 그래프 차원 축소: 근사적 매끄러움(Approximate Smoothness) 및

그래프 구조를 가진 팔(arms)을 사용하는 문맥적 밴딧(Contextual bandits)은 추천, 인용 검색, 소셜 광고 등에서 발생하며, 그래프 상에서 연결된 팔들은 보상 신호를 공유하는 경향이 있습니다. 표준적인 차원 축소(dimensionality reduction) 방식은 이러한 구조를 무시하여 탐색 비용을 $d/k$ 배만큼 부풀립니다. 우리는 팔의 특징(features)을 그래프의 저주파 스펙트럼 부분 공간(low-frequency spectral subspace)으로 투영하고, 결과로 생성된 $k$차원 공간에서 선형 UCB(linear UCB)를 실행하는 GraphDR-LinUCB를 제안합니다. 우리는 스펙트럼 투영 기반 문맥적 밴딧에 대해 최초의 $\wtO(k\sqrt{T})$ 후회 경계(regret bound)를 증명하여, 차원 의존성을 $d$에서 $k$로 줄였습니다. 섭동 논증(perturbation argument)을 통해 이를 노이즈가 있는 그래프로 확장하였으며, 보상 매끄러움(reward-smoothness) 불일치 및 그래프 추정 오차에 대한 명시적인 페널티를 포함했습니다. 우리의 핵심적인 이론적 발견은 고주파 보상 성분이 반드시 최악의 경우 $T$에 비례하는 선형 페널티를 발생시킬 필요는 없다는 것입니다. 즉, 그 실제 비용은 전체 에너지(total energy)가 아니라, 실행된 경로를 따라 실현된 영향력에 따라 결정됩니다. 부분 공간($Γ_k$) 간의 간단한 스펙트럼 비교는 주어진 데이터셋에서 어떤 축소기(reducer)가 승리할지를 예측하며, 별도의 적합된 임계값(fitted threshold) 없이도 6개의 실제 데이터셋 결과 중 5개를 정확히 맞추었습니다. 합성 벤치마크와 6개의 실제 데이터셋(MovieLens, Amazon, LastFM, ogbn-arxiv, MIND) 전반에 걸쳐, GraphDR-LinUCB는 전체 차원 LinUCB 대비 누적 후회(cumulative regret)를 $15\times$ 감소시켰으며, 6개 중 5개에서 경쟁하는 그래프 인식(graph-aware) 방법들보다 우수한 성능을 보였습니다. 단 하나의 실패 사례는 그래프의 스펙트럼 부분 공간이 보상과 정렬되지 않은 경우였습니다.