강화학습에는 밴딧 알고리즘이라는 세부 연구분야가 있어요.
그럼 우선 멀티암 밴딧 문제에 대해서 설명을 해야 하는데요,
이렇게 카지노에 있는 슬롯머신에서 최고의 이득을 얻는 policy 를 통계적으로 엄밀하게 설계해보자! 라는데서 출발한 것이 Multi-Armed Bandit 문제에요.
그러면 항상 최적화 문제가 그렇듯이, objective function 을 정의해야 하는데요,
이렇듯 현재 시각 t 에서 최적의 arm 이 얻을 수 있는 reward 의 평균과, 시뮬레이션에서 직접 누른 arm 에서 얻은 reward 의 차이를 누적해서 평균한 값을 objective function 으로 삼아요.
이것을 regret, 혹은 regret function 이라고 정의하는데요, 이것을 최소화하면 최적의 policy 를 찾을 수 있지 않겠나, 라는 생각에서 출발을 해요.
그러면 이제 optimal mean 과 estimated mean 간의 차이를 통계적으로 bound 할 수 있는 도구가 필요한데요,
이렇게 chebyshev inequality 를 이용하면 upperbound 를 구할 수 있어요. 그래서 아래와 같이 confidence interval 을 구할 수가 있답니다.
여기서 log(1/delta) term 은 asmptotical 한 bound 에요. 그리고 어떤 policy 를 설계하든 간에 저 log(1/delta) term 을 개선할 수 없음을 Lai 와 Robbins 가 증명했어요.
그러면 이제 upperbound 가 있음을 증명했고, 그럼 이 bound 를 활용해서 algorithm 을 만들던지 해야하는데
UCB1 알고리즘이 가장 기본이 되는 알고리즘이에요. 이 알고리즘은 저 mean + CI 가 가장 최대가 되는 arm 을 선택하는 것을 요지로 하는 알고리즘이에요.
이 알고리즘의 regret bound 는
위와 같음이 증명되어 있어요. 이렇게 여러 알고리즘을 설계해 가면서 log(1/delta) = log(n) term 앞의 constant 를 개선해 나가는 것이 밴딧 알고리즘의 주요한 연구과제였고, 앞으로도 계속되어져 나갈 거에요.
이외에도 reward distribution 이 i.i.d 가 아닌 arbitrary(즉 무작위인) 상황에서 알고리즘을 설계하는 adversarial bandit,
또 contextual bandit 이라고 해서 특정 task 의 prior knowledge 를 활용하는 방법론,
그리고 베이지언을 한 스푼 넣어서 Thompson Sampling 을 이용해 문제를 푸는 접근까지 아주 다양한 연구들이 이루어지고 있답니다.
선수과목은요
Measure theory, Stochastic process, Martingale 정도 배우고 시작하시면 될 것 같아요.
교재는 아직 출판되지는 않았지만 이 분야에서 최근 대가라고 할 수 있는 Tor Lattimore and Csaba Szepesv´ari 의 Bandit Algorithm 책을 읽어보시면 됩니다.
http://banditalgs.com/
꽁짜에요 ㅎㅎ
<style type="text/css"> p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica} </style>
ㅊㅊ
올
조용필 오르가즘 추신수...
변태들