스펙트럴 밴디트 (Spectral Bandits)

그래프 위의 매끄러운 함수 (smooth functions) 는 다양체 학습 (manifold learning) 과 준지도 학습 (semi-supervised learning) 에서 광범위한 응용을 가지고 있습니다. 본 논문에서는 팔 (arms) 의 보상 (payoffs) 이 그래프 위에서 매끄러운 밴디트 문제를 연구합니다. 이 프레임워크는 콘텐츠 기반 추천 (content-based recommendation) 과 같이 그래프를 포함하는 온라인 학습 문제 (online learning problems) 를 해결하기 적합합니다. 이 문제에서 우리가 추천할 수 있는 각 항목 (item) 은 무방향 그래프 (undirected graph) 의 노드 (node) 이며, 그 기대 평점 (expected rating) 은 이웃 노드의 것과 유사합니다. 목표는 높은 기대 평점을 가진 항목을 추천하는 것입니다. 우리는 최적 정책 (optimal policy) 에 대한 누적 후회 (cumulative regret) 가 노드 수 (number of nodes) 와 함께 나쁜 비율로 확장되지 않는 알고리즘을 목표로 합니다. 특히, 우리는 실제 세계 그래프에서 작은 유효 차원 (effective dimension) 의 개념을 도입하고, 이 차원에 대해 선형 (linearly) 과 아선형 (sublinearly) 으로 확장되는 우리의 문제를 해결하기 위한 세 가지 알고리즘을 제안합니다. 콘텐츠 추천 문제에 대한 실험 결과, 수천 개의 항목에 대한 사용자 선호도 (user preferences) 에 대한 좋은 추정량 (good estimator) 은 단지 수십 개의 노드 평가 (node evaluations) 로부터 학습될 수 있음을 보여줍니다.