Recently, the importance of the recommender system has grown as personal preferences become more diversified. This dissertation proposes reinforcement learning algorithms for the recommender system that the system improves the performance by itself over time. I firstly model recommender systems as Markov decision processes that the agent iteratively selects items to recommend among the possible candidates and receives the selection results. In the first part, I introduce a concept of bankruptcy in the recommender system, so the agent needs to consider a trade-off between avoiding bankruptcy and maximizing the benefits. I propose a variant of the multi-armed bandit algorithm, which achieves the asymptotically optimal performances without any bankruptcy. In the second part, I develop a deep reinforcement learning algorithm where the agent recommends multiple items simultaneously. The algorithm takes advantage of graph neural networks and the idea of greedy algorithm to relieve the scalability issue of selecting the best combination of the multiple items once. I theoretically prove that the applied ideas never degrades the performance. The proposed algorithms in the dissertation are tested in various environments, and the results insist that the algorithms successfully improve their item selection policy over time.
최근 사람들의 생활양식이 점점 더 개인화됨에 따라서 추천 시스템의 중요성이 올라가고 있다. 본 학위논문에서는 강화 학습을 활용하여 시간이 지남에 따라서 추천 시스템의 성능을 스스로 개선하는 알고리즘을 제안하였다. 이를 위해 우선 추천 시스템 문제들을 에이전트가 가능한 아이템 후보들중 일부 아이템을 반복해서 선택하고 선택에 따른 결과를 받는 마르코프 결정 과정들로 모델링하였다. 첫 번째 부분에서는 추천 시스템의 파산이라는 개념을 도입하여 파산을 회피하는 것과 이득을 극대화하는 사이에서 균형을 고려해야 하도록 하였다. 이를 위해 다중 슬롯머신 문제 기반의 알고리즘을 제시하고, 제시된 알고리즘이 파산의 위험없이 장기적인 관점에서 최적의 성능을 보임을 확인하였다. 두 번째 부분에서는 여러 가지의 아이템을 동시에 추천해야 하는 깊은 강화학습 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 구조 기반의 인경신경망과 탐욕 알고리즘의 장점을 활용하여 동시에 가장 좋은 아이템들의 조합을 선택하는 과정에서 발생하는 확장성 이슈를 완화하였다. 이 과정에서 도입된 방법들이 알고리즘의 성능을 저하하지 않음은 이론적으로 확인하였다. 본 학위논문에서 제안된 알고리즘들은 다양한 환경에서 검증되었고, 아이템을 선택하는 방식이 시간이 지남에 따라서 성공적으로 개선됨을 확인할 수 있었다.
