[CS234] Lecture 12: Fast Learning II 정리

지난 시간에 이어, 이번 강의도 Fast Learning에 관한 내용이다.

다만, 아직까지 "Bandit"을 어떻게 이해해야 할지 잘 모르겠다.

여러 대의 슬롯머신에서 최적의 전략을 뽑아내는 것을

"Multi-armed Bandits"라고 이해했는데, 

"Bayesian Bandits"라고 하면, 그건 또 무슨 말이람?

 

이런 남모를 고충을 강의에서도 이해했는지,

간략한 복습을 진행해주었다.

지난 시간에 정의한 "Bandit"은, MDP의 간소화된 예시였다.

그렇담 MDP는 무엇이었나?

(S, A, P, R)로 구성된 Markov Chain을 일컫는 말이었다.

다시 말하자면, "상태 - 행동 - 상태 전환 확률 - 보상" 변수들로 이루어지면서

현재 상태가 과거의 모든 정보를 포함하고 있는 모델이었다.

 

Bandit은 여기서 상태가 빠지고(동시에 상태전환 확률도 제외된다), 

보상은 확률 분포로 존재하게 된다.

그러므로, (A, R) 인 모델이며, R = $P[ r | a ]$라고 할 수 있을 테다.

주어지는 보상을 가지고 최적의 행동을 만들어내는 것이다.

 

최적의 행동을 찾아내면서 가장 높은 보상을 받기 위해서는

지금까지 나온 행동 중에서 가장 높은 보상을 주는 것을 위주로 선택하는 한편

지금까지 하지 않은 행동들을 적절히 섞어가면서 탐색하는 과정이 필요하다.

e-greedy라고 해서 $\epsilon$의 확률로 랜덤한 행동을 취하는 방법이 있지만

Upper Confidence Boundary는 랜덤한 확률을 취하는 방법을 좀 더 고도화 함으로써

최적의 행동을 더 빠르게 찾아낼 수 있도록 해준다. 

 

UCB의 예시 문제는 살짝 그로테스크한 감이 없지 않은데,

발가락이 부러졌을 때 대처 방법을 UCB를 통해 찾아내는 것이다.

좀 더 실생활에 관련되거나 산뜻한 설명방법이 있을텐데, 희한하다.

오랜 시간 강화학습을 연구하다 보니,

"차라리 내 발가락을 분지르고서라도 이 연구소를 떠나고 싶군" 하는 마음으로

예제를 작성했을까? 이제 공부하는 입장으로서는 퍽 난감하다.

 

여튼, 1) 수술을 받거나 2) 테이핑을 하거나 3) 아무 것도 하지 않는 선택지가 있고

각각 0.95, 0.9, 0.1의 확률로 완치될 수 있다.

여러 환자들이 대기하고 있다면,

의사의 입장에서 어떤 행동을 취하는 것이 최적일까?

이 때, 첫 세 환자에 대해 1~3의 행동을 한 번씩 시도해보았다.

 

UCB를 계산해보면, UCB($a_1$), UCB($a_2$)가 동일하게 나오고

UCB($a_3$)가 제일 작은 값을 가진다.

그러므로 $a_1, a_2$를 각각 50% 확률로 선택해가며

다음 환자들을 진료하는 것이 최적의 방안인 것이다.

물론 이런 방식은 시뮬레이션이기에 가능할 뿐,

실생활에서는 다른 방식의 모델이 필요할 것이다.

그 세 번째 방법이 바로 Bayes Rule을 사용한 Thompson Sampling 기법이다.

(첫 번째는 e-greedy, 두 번째는 UCB였다.)

나로서는 Bayes Rule에 대한 정보가 전무해서 강의를 듣는데 애를 많이 먹었다.

 

지금까지 예시에서는 보상 어떤 값일지에 대한 추정이 있었으나,

이번에는 보상이 어떤 분포를 따르는지 배울 예정이다.

왜 그래야 하는지를 생각해보면, 문제의 본질에 더 다가가는 느낌이랄까...

사실 보상에 대한 추정이나, 보상의 분포에 대한 추정이나

말장난 같은 느낌이 없지 않지만

결과적으로는 후자가 성능이 더 좋다(더 빠르게 최적의 행동을 찾는다).

 

Bayesian Bandits는 과거 경험을 살려서 

보상의 확률 분포를 추측해볼 수 있다.

이 때 사용하는 방법이 Bayes Rule이다.

 

Bayes Rule은 상당히 복잡한 형태를 띤다.

우선 알고자 하는 것은 무엇인가? 보상의 확률분포이다.

과거 보상을 받은 내역이 $r_1, r_2, .... $ 하는 식으로 주어졌을 때

확률분포를 나타내는 파라미터 $\phi$를 구해야 한다.

그러므로 조건부 확률인 p($\phi$ | r )로 표현할 수 있고,

이는 본래 p($\phi \cap r$) / p(r) 로 구할 수 있다.

p($\phi \cap r$)는 p($\phi$ | r ) * p(r) 또는

p($ r | \phi $) * p($\phi$) 로 구할 수 있으므로, 후자를 사용한다.

 

p($ r | \phi $)를 data evidence 또는 likelihood,

p($\phi$)를 prior, p($\phi | r$)을 posterior라고 해서

참 다양한 방식의 명칭이 있다.

이런 명칭들이 이해를 더 어렵게 만드는 느낌이 없지 않다. 

 

각 용어를 온전히 이해하기도 전에, 

또 다른 용어가 나온다. "베타 분포" 라는 것이다.

베타 분포를 이해하기 위해서는 "베르누이 분포"를 알아야하는데,

이렇게 파보다간 끝이 없을 것 같아 포기한 후 

개념적인 것만 잡아가기로 했다.

 

앞서 살펴보았던 Bayes Rule에서는 Prior와 Posterior가 나왔다.

Prior를 활용해서 Posterior를 구해줘야 하는데, 

확률 분포의 방식이 꽤나 다양하다는 문제가 있다.

 

"확률 분포" 하면 떠올릴 수 있는 Gaussian 분포(표준 정규분포)는

좌우가 대칭이고, 양 끝으로 갈 수록 확률이 낮아지는 예쁜 모습을 하고 있다.

일반적으로 자연에 존재하는 대부분의 분포는 Gaussian 형태라고들 하지만

모집단이 작아지면 꼭 그런 것도 아니다.

위와 같이 표준정규분포에 비해 양 꼬리 부분이 두껍고

중앙 부분이 얇은 분포가 있는가 하면 

더 특이하게 생긴 분포가 얼마든지 많다.

Prior분포와 Posterior분포가 다르다면,

동일한 범위에 대해서 값이 달라지므로

계산할 때 상당히 복잡해진다. 

그래서 두 분포를 동일하게 맞춰줘야 하는데, 

그런 역할을 하는 것을 Conjugate라고 한다.

 

Conjugate는 복소수를 배울 때 "켤레"라고도 불렀던 기억이 있는데

통계에서도 얼추 비슷한 역할을 해주는 것 같기도 하다.

 

Bayes Rule: $p(\phi | r)$ = p( r | $\phi$ ) * p($\phi$) / p(r)

 

어쨌든, 슬롯머신의 Prior 분포가 베르누이 분포를 따르는데,

Posterior도 베르누이 분포를 따르게 만들기 위해서는

Prior에 곱해지는 Likelihood가 베타 분포를 따라야 한다는 것이 핵심이다.

그래서 베타 분포에 대한 내용이 들어간 것이므로

Gamma Family니 뭐니 하는 내용은 넘기도록 하자.

 

그래서 위 내용을 몽땅 활용하는 방법이

Probability Matching이고, 그 대표격이 "Thompson Sampling"이다.

Probability Matching의 의미는 보상 분포를 추정한 후,

그 분포에서 최적의 값을 가져올 수 있는 행동을 취하는 방법을 뜻한다.

Thompson Sampling의 기본적인 알고리즘은 아래와 같다. 

 

이해하기 쉽게 쓰는 것이 수도코드인데, 

위와 같은 경우에는 수도코드를 또 이해하기 쉽게 풀어써야 할 판이다.

그래서 풀어 써보자면, 처음에 보상 분포를 초기화 한 뒤에

해당 분포에서 최적의 결과를 가져오는 행동을 취한 뒤에

그로 인한 결과를 분포 업데이트에 사용한다.

 

동전을 던져서 앞/뒤를 맞추는 예시라고 하자.

기존 분포가 두 번을 던졌을 때 앞 뒤 한 번씩 나왔다면

한 번 더 동전을 던져서 앞이 나왔으면 기존 분포를 (2:1)로 수정,

다음에 동전을 던지면 최적의 확률은 "앞"으로 예측하는 것이다.

만약에 "앞"이라면 기존 분포를 (3:1)로 수정,

"뒤"라면 (2:2)로 수정하는 작업을 반복하는 것이다.

 

"이게 다야?" 

이게 다다. 굉장히 멀리 돌아온 느낌이지만, 이런 내용이다.

 

지금까지 Fast Learning을 Bandit에 적용해봤다면

이제부터는 MDP에 적용해볼 차례이다.

앞서 말했듯이, Bandit은 MDP의 근사에 지나지 않으며

MDP는 Bandit에 상태 변수가 추가되어 (S, A, P, R)로 이뤄진다.

 

먼저 Optimistic Initialization 방법을 살펴보고, 

나머지는 다음 시간에 다룰 건데,

강의 시간이 많이 남지 않아 다음 시간 초반에 

아마 방법들을 전체적으로 복습한 뒤 진행할 듯 하다.

이번에는 간략한 내용만 정리해 보자면 아래와 같다.

 

설명은 상당히 복잡하지만, 원리는 꽤나 간단하다.

Value(MDP이므로 Q가 되겠지?) 를

모든 State-Action Pair에 대해 최댓값으로 설정한 뒤에

실제로 실행한 값으로 수정해나가는 것이다. 

말하자면, 실행할 수록 Q가 낮아지는데

이렇게 함으로써 아직 실행하지 않은 State-Action Pair를 우선적으로

검토해볼 수 있게 된다. 

 

---

이번 강의는 유난히 못알아먹겠는 부분이 많아서

들을수록 초조해졌다. 시간 낭비를 하는 느낌이었기 때문이다.

상당 부분을 다른 자료를 통해 이해해야했고,

강의에 대한 신뢰도도 점점 떨어졌다.

하지만 앞으로 세 강 정도 남은만큼 

일단 들어보고 판단해보는 "Exploration" 과정을 거칠 예정이다.

Value가 낮다고 판명되더라도 Exploration이므로 어쩔 수 없고,

Value가 높게 나온다면 Exploitation할 수 있는 기반이 되겠지.