Upper confidence reinforcement learning (UCRL) algorithms are shown to be very effective to solve online reinforcement learning problems in which the environment is given by a Markov decision process (MDP) with unknown reward distributions and unknown state transition probabilities. Analogously to upper confidence bound (UCB) algorithm, UCRL algorithm constructs a set of plausible MDPs that contains the true MDP with a high probability, and finds an exploration policy based on optimistic interpretation of this confidence set. To achieve optimal balance between exploration and exploitation, it is crucial to construct the set of plausible MDPs as tight as possible.
We introduce bootstrap techniques in construction of the set of plausible MDPs, in addition to the concentration inequalities such as Hoeffding's inequality and empirical Bernstein inequality used in the previous UCRL algorithms. By doing so, we can further utilize the whole distribution of given data thereby making the set of plausible MDPs tighter while preserving theoretical guarantees on the performance of worst case. We demonstrate through experiments that our proposed bootstrapping UCRL algorithms improve the existing UCRL algorithms by 5%-30% in terms of cumulative regret, and also provide theoretical analysis showing that this improvement can be carried out without degrading their performance guarantees.
본 연구에서는 부트스트랩을 활용하여 개선된 신뢰 상한 강화학습 알고리즘을 제안한다. 신뢰 상한 강화학습 알고리즘은 온라인 강화학습 문제를 푸는 효과적인 알고리즘이다. 일반적으로 온라인 학습 문제에서의 환경은 마르코프 결정 과정으로 표현되며 그 환경의 보상 분포와 상태 전이 확률은 알려지지 않은 채로 문제를 푼다. 신뢰 상한 강화학습 알고리즘은 마르코프 결정 과정의 신뢰 집합을 구성하고 그 안에서 낙관적인 시선을 통해 탐색을 위한 정책을 결정한다. 이 정책이 더 효율적인 탐색을 해내어 알고리즘의 성능을 높이기 위해서는 더 정확하고 딱 맞는 신뢰 집합을 구성해야 한다. 본 연구에서는 부트스트랩 기법을 통해서 기존 알고리즘의 신뢰 집합을 더 정확하고 딱 맞도록 개선하였다. 그리고 새로운 알고리즘이 기존의 알고리즘의 최악의 경우의 성능에 대한 이론적 보장을 그대로 유지한다는 것을 증명하였다. 마지막으로 실험을 통해서 새로운 알고리즘이 기존의 알고리즘의 누적 후회의 값을 5%-30% 줄인다는 것을 보였다.
