No Limitation
[Reinforcement Learning] Multi-Arm Bandit (1) - Intro 본문
본 포스팅은 카이스트 산업 및 시스템 공학과 신하용 교수님의 동적계획법과 강화학습 강의 자료를 바탕으로 작성되었음을 밝힙니다.
Exploration vs Exploitation
이 둘 간의 어떤 것을 선택하는 지가 많은 RL 기반의 문제에서 딜레마가 됩니다. Exploitation은 말 그대로 지금 가장 좋은 것을 선택하는 행동을 의미합니다. 하지만 exploitation이 좋아보이지만, 만약 지금 내가 가지고 있는 정보가 충분하지 않다면 더 optimal한 선택을 할 수 있는 가능성을 애초에 놓치게 됩니다. 그래서 정보를 더 얻기 위한 방법을 수행해야 하는데, 그럴 때 Exploration을 통해 다른 길을 가봄으로써 더 선택에 도움을 주는 정보들을 얻게 됩니다. 에이전트는 매번 이 딜레마에 빠지게 되는데 그것을 바로 Exploitation과 Exploration 사이에서의 딜레마라고 합니다. 결국 이 둘 간의 balancing을 잘 해야지 가장 좋은 선택을 할 수 있게 되는데요, 바로 이번 포스팅에서는 이 문제를 Multi-Arm Bandit Framework 관점에서 살펴보도록 하겠습니다.
위 그림은 여러 개의 팔로 slot machine을 당기는 것을 보여주는 그림입니다. 진짜 말 그대로 multi-arm bandit인거죠. 바로 사용자는 여러 개의 slot machine을 돌려보면서 어떻게 가장 자신의 이익을 최대로 하는 지를 고민하는 문제입니다. 그것을 바로 MAB라고 하는 거죠. Environment를 정의하면 어떻게 될까요? 우선 action space는 다음과 같이 정리할 수 있습니다.
A는 각 slot 머신을 의미하고 at는 t 시간에 어떤 slot machine을 당길 것인지를 의미합니다. 각 슬롯 머신에 대해 reward distribution은 아래와 같이 정의됩니다.
그래고 t 시점의 at에 대한 보상을 r(at)로 표기할 수 있습니다. 하지만 아쉽게도 우리는 이 Da에 대한 값을 알지 못합니다. 따라서 이런 MAB 상황에서 목표는, average reward를 최대화하는 것을 목적으로 합니다. 기본적으로 MAB에서는 discount factor를 정의하지 않습니다. 또한 구체적으로 Finite horizon 상황과 Infinite horizon 상황에서의 목표는 다르게 되는데 아래와 같이 표기될 수 있습니다.
Finite horizon은 일반적인 몬테 카를로 방법을 통해 average reward가 계산이 됩니다. 이를 구분한 이유는, 제한된 시간이 있냐의 유무에 따라 exploitation을 할 건지 exploration을 할건지 달라지기 때문입니다. 예를 들어 10판만 하고 집에 갈 건데 8판 째면, 사실 exploration보단 exploitation을 선택할 가능성이 높겠죠. 이런 차이가 있기 때문에 objective function이 다르게 형성되게 됩니다.
그리고 위에서 보시다시피 어떠한 state나 state transition이 정의되지 않았습니다. 즉 MAB는 state를 따로 정의하지 않는 single state MDP 문제로 볼 수 있습니다. 조금 특수한 MDP problem이 되는 것이죠.
그렇다면 이 action을 바탕으로 한 action value는 어떻게 정의되는지 살펴보겠습니다.
위 수식을 보면 q(a)라는 값이 나오는데 이는 arm a를 당겼을 때 갖는 expected reward를 의미합니다. 물론 이 값은 현재 우리가 모르는 값입니다. 그리고 이 q(a)를 최대화하는 action이 optimal action a*가 되고 q(a*)에서 q(a)를 뺀 값이 바로 optimality gap이 됩니다.
그렇다면 이런 MAB의 성능을 측정할 수 있는 metric은 무엇을 사용할까요? 여기서는 'regret'이라는 개념이 도입됩니다.
정책 함수 π가 있고, action과 reward를 담고 있는 history를 정의한 다음, N(a)라는 것을 정의하는데 이는 t시점까지 action a를 선택한 횟수를 의미합니다.
그렇다면 regret은 어떻게 구해질까요? 우선 one-step regret은 optimality gap의 정책 π를 따를 때의 expectation을 의미합니다. 그리고 이게 total step이 되면 바로 그 optimality gap의 합의 expectation으로 정의될 수 있습니다.
그렇다면 어떤 regret을 가지면 좋은 걸까요? 최악의 상황을 가정해봅시다. optimality gap이 높은, 그다지 좋지 않은 slot machine을 계속 당기게 되는 경우를 생각해봅시다. 그렇다면 시간이 지날수록 일정한 gap을 계속 얻게 될 것이고 이는 결국 linear 한 형태가 될 것입니다. 바로 이 경우가 최악이 됩니다. 물론 그 정도에 따라 linear의 기울기는 다르겠지만 어쨌든 linear의 특징을 갖는 것은 그다지 좋은 결과가 아닌 것입니다. 그래서 목표는 이러한 linear보다 더 좋은 sub-linear한 regret을 갖는 것을 찾는 것이 바로 MAB의 goal이라고 할 수 있습니다. 부가적으로 one-step regret는 저 total regret 그래프의 한 지점에서의 기울기를 의미하게 됩니다.
자, 그러면 결국 어떠한 policy를 선택하느냐, 즉 어떻게 exploration과 exploitation을 적절히 사용하는 policy를 디자인할 것인지가 숙제이게 됩니다. 다양한 policy를 선택할 알고리즘이 존재하게 되는데 하나씩 살펴보죠.
먼저 Greedy policy를 살펴보겠습니다.
Greedy policy
이 greedy policy는 말 그대로 exploration을 수행하지 않는 것입니다. 오직 exploitation만 수행하게 되는 거죠. 이런 경우는 regret이 sub-linear하게 형성이 될까요? 우선, 그 전에 action value를 정의하는 것이 중요하기 때문에 history ht의 정보를 바탕으로 아래와 같이 정의를 할 수 있게 됩니다.
즉, Q(a)는 각 arm을 당겼을 때, 그 reward들의 평균을 의미하게 됩니다. 이는 밑의 방법처럼 incremental하게 계산을수행할 수도 있습니다. 이렇게 action value를 정의하겠습니다. 이럴 때 regret은 어떻게 계산이 될까요?
우선 greedy policy기 때문에 가장 Q(a)를 최대로 하는 action을 선택할 것이며, 만약 a가 optimal이면 좋지만, 그렇지 않다면, local optima에 빠지게 되면, lt는 더이상 감소하지 않는 문제가 발생하게 됩니다. 따라서 이는 linear regret을 형성하게 됩니다. 결국 greedy policy는 그다지 좋은 선택지가 아닌 것을 알 수 있습니다.
자 그럼, 반대로 그냥 랜덤하게 막 선택한다고 생각하면 어떨까요? 이를 random policy라고 표현합니다.
action을 uniform distribution에 있는 어떠한 random한 값으로 action을 선택하면 P(at=a)는 1/|A|가 될 것입니다. 결국 a를 선택하는 것은 전체 action space 중 하나를 선택하는 확률이 되고, 이 값을 바탕으로 expectation이 계산이 됩니다. 저렇게 되면 lt는 constant한 상황이 되고, lt가 constant하다는 건 결국 total regret Lt의 기울기가 일정한 것이기 때문에 결국 저 값 또한 total regret이 linear한 형태가 됩니다.
그렇다면 ε-greedy는 어떨까요? ε-greedy의 one-step regret은 아래 처럼 정의할 수 있습니다.
여기서 학습이 점점 수행하게 되면 greedy regret는 점차 줄어드는 값을 보일 것입니다. 하지만, random regret term의 경우 그렇지 않기 때문에 결국 점차 감소하는 특성을 갖지 않습니다. 따라서 lt가 0으로 수렴하지 않아, 결국 linear total regret을 가지게 됩니다. 그렇다면 이 ε을 decaying하면 저 random regret 항목도 diminish할 수 있지 않을까요?
잘 ε을 design하면 logarithmic regret을 달성할 수 있다고 합니다. 바로 위에 나와있는 'min' term처럼 말이죠. 저기서는 d라는 value를 구해야 하는데 d는 바로 optimality gap의 최소값을 의미합니다. 하지만, 우리는 현재 optimality gap을 모르는 상황이기 때문에, 저 알고리즘은 적용할 수 없게 됩니다.
자 그렇다면, regret을 기준으로 linear보다 더 잘하는 경우를 찾으려면 결국 얼마나 더 잘할 수 있을까요? 그 Lower bound는 어떻게 될까요? 이 부분에 대해서 공부해봅시다!
MAB는 쉬운 문제인 경우는 regret이 작지만, 어려운 문제인 경우는 regret이 상대적으로 크게 되겠죠. 이럴 때 이 MAB 문제의 어려운 '정도'를 측정할 수 있는 지표를 정의할 수 있을까요? 아래 그림을 보시죠.
우선 optimality gap이 클수록 더 regret이 크니까 어려운 문제이겠죠. 또한 optimal reward distribution과 아닌 것 사이의 차이가 적다면 이도 구분이 어려워 문제가 어렵겠죠. 바로 이 2개의 term을 사용해서 맨 밑의 수식처럼 difficulty를 정의할 수 있게 됩니다.
Lai and Robbins Theorem
Lai / Robbins는 이 difficulty를 가지고 다음과 같은 정리를 제안하였습니다. 이 정리는, total regret은 기껏해야 logarithmic까지 작아지고 그 밑으로는 더 갈 수 없다는 것입니다. 즉, difficulty*log(t) 이하로 내려갈 수는 없다는 것이죠. 즉 이 boundary가 바로 total regret이 가질 수 있는 가장 optimal한 상황임을 보여줍니다. 그리고 이 정도의 performance를 갖는 MAB 알고리즘을 찾기 위해 많은 연구들이 수행되었고 어떠한 연구들이 있는 지를 살펴보도록 하겠습니다.
"Optimism in the face of uncertainty Principle"
이 원칙은, 불확실성이 있을 때는 낙관적인 선택을 할 때 더 잘되더라는 원칙입니다. 즉, uncertainty가 높을 수록 더 exploration을 수행하라는 의미가 됩니다. 구체적으로 이게 뭘 의미하는 지를 살펴봅시다.
자 왼쪽 그림을 보시죠. 왼쪽 그래프에서, 0, 1, 2, 3은 각각 회사를 의미하고 P(Q)는 월급이라고 해봅시다. 그러면, 어떤 회사에 취업을 하는게 좋을까요? 낙관적인 추정치를 고려하게 되면 가장 우측 끝단에서 value가 가장 높은 1번 회사에 취업을 하려고 할 것입니다. 그런데 만약 1번 회사에 취업을 해서 막상 월급을 받아보니 생각보다 별로였고 uncertainty가 줄어들기 때문에 우측 그래프처럼 바뀌었다고 해봅시다. 그럼 다음으로는 이제 낙관적인 선택을 고려해서 2번 회사를 선택하게 될 겁니다. 이런 방법을 구체적으로 policy로 만든 것이 바로 Upper Confidence Bound (UCB) policy입니다.
UCB policy
위 그래프를 보시면, Q(a)가 평균적인 estimation이고 95% confidence level을 설정하게 되면 Lower confidence bound와 Upper confidence bound가 형성이 되게 됩니다. True value q(a)는 이 interval 내에 있을 확률이 95%가 되는 거죠.
바로 저 UCB를 가지고 action을 선택하게 되는 것입니다. 구체적으로는 아래 수식처럼 표기가 됩니다.
위 수식처럼 value function은 평균 Q(a)에다가 uncertainty U(a) 가 더해지는 형태로 계산이 됨을 알 수 있습니다. 바로 저 Q(a)가 exploitation, U(a)가 exploration을 의미하게 되겠네요. 그러면 저 U(a)를 어떻게 계산하게 될까요? 그 방법에 따라 다양한 UCB 알고리즘이 정의될 수 있습니다. UCB1과 Bayesian UCB가 대표적인 예입니다.
UCB1은 action a를 수행한 횟수만 가지고 UCB를 정의할 수 있다고 언급합니다. 반면 bayesian UCB는 posterior를 이용해서 UCB를 계산할 수 있다고 합니다.
분량이 많아 이번 포스팅은 여기까지 마치고 다음 포스팅에서는 위에서 언급한 UCB1, Bayesian UCB에 대해 정리하고, 나아가 Thompson sampling까지 정리하도록 하겠습니다.
긴 글 읽어주셔서 감사합니다!
