Contextual multi-armed bandit algorithm for semiparametric reward model

Abstract

Contextual multi-armed bandit (MAB) algorithms have been shown promising for maximizing cumulative rewards in sequential decision tasks under uncertainty when contextual information is given. Applications include news article recommendation systems, web page ad placement algorithms, revenue management, and mobile health. However, most of the proposed contextual MAB algorithms rely on strong, linear assumptions between the reward and the context of the action. This thesis proposes a new contextual MAB algorithm for a relaxed, semiparametric reward model that supports nonstationarity. The proposed method is less restrictive, easier to implement and faster than two alternative algorithms that consider the same model. It can be shown that the high-probability upper bound of the regret incurred by the proposed algorithm has the same order as the Thompson sampling algorithm for linear reward models without restricting action choice probabilities. The proposed algorithm and existing algorithms are evaluated via simulation and also applied to Yahoo! news article recommendation log data provided by Yahoo! Webscope.

다중 슬롯 머신 (MAB) 알고리즘은 순차 결정 문제를 다루는 연구 분야로서, 특정 환경 안에서 학습자에게 선택 가능한 다수의 행동들이 주어졌을 때, 이들 중 보상을 최대화하는 행동을 선택하는 방법론이다. 학습자는 행동을 선택하고 보상을 받는 과정을 반복하면서 보상 메커니즘에 대한 정보를 축적하고 학습하여 시간이 지남에 따라 최적의 행동에 가까운 행동을 선택하게 된다. 사이드 정보를 활용하는 다중 슬롯 머신 (Contextual MAB) 알고리즘은 순차적 의사 결정 시에 사이드 정보를 활용하는 MAB 알고리즘이며 최근 Yahoo!의 뉴스 기사 추천 시스템에 적용되어 기존에 비해 기사 클릭수를 크게 증가시키면서 많은 성과를 거두었다. 이외에도 Contextual MAB 알고리즘이 주로 이용되는 분야로는 웹 페이지 광고 배치 알고리즘, 수익 관리, 모바일 헬스 시스템 등 다양하다. 더 좋은 MAB 알고리즘은 더 많은 보상과 수익을 창출할 수 있다는 점에서 매우 중요한 연구 분야다. 그러나 현재까지 제안된 대부분의 Contextual MAB 알고리즘은 보상과 사이드 정보 사이에 제한적인 선형 모형을 가정한다. 특히 보상 값의 분포가 시간에 따라 변하지 않는 다는 가정은 앞서 소개한 실제 문제들에 적용하기에는 비현실적이라는 지적을 받는다. 본 논문에서는 선형 가정보다 완화된 준모수적 가법 모형 하에서도 좋은 성능을 가지는 새로운 Contextual MAB 알고리즘을 제안한다. 준모수적 보상 모형 하에서 제안된 알고리즘에 의해 발생되는 누적 보상이 최적 보상으로 수렴하는 속도는 더 제한적인 선형 모형 하에서 톰슨 샘플링 알고리즘에 의해 발생되는 누적 보상이 수렴하는 속도와 유사하다. 또한, 제안된 방법은 동일한 모형을 다루는 두개의 선행 연구에 비해 덜 제한적이고 구현하기 쉬우며, 구현 속도가 더 빠르다. 시뮬레이션을 통해 제안된 알고리즘과 기존 알고리즘의 표본 성질을 비교한 결과를 소개한다. 더불어, Yahoo! 웹스코프가 제공하는 Yahoo! 뉴스 기사 추천 로그 데이터에 제안된 방법을 적용한 결과도 소개한다.