아이템(Item)별 예산이 존재하는 Contextual bandit 문제는 제한된 비용으로 보상을 최대화하기 위해 중요한 문제이며, 특히 예산이 한정된 온라인 광고에서 중요하다. 기존 Contextual bandit 연구에서는 전체 예산에만 제약이 있고 아이템별 예산은 고려된 바 없다.
본 연구에서는 아이템별로 최대 예산이 존재하는 상황을 가정하고, Upper Confidence Bound (UCB) 및 Thompson Sampling (TS)에 기반한 Linear contextual bandit 알고리즘을 제안한다. 제안 알고리즘을 포털사이트 뉴스기사 클릭 로그 데이터 (Yahoo R6A)에서 실험한 결과, 아이템별 예산의 존재를 가정하지 않은 기존 알고리즘과 비교하여 높은 평균기대보상을 얻을 수 있었다.