강화 학습은 머신러닝에서 중요한 한 영역입니다. 시간 t까지 관찰된 데이터를 토대로 시간 t+ 1에 취할 행동을 결정하는 상호 작용 문제를 해결하는 데 사용됩니다. 걷기와 같은 작업을 수행할 수 있도록 기계를 훈련시키기 위해 인공 지능(AI)에도 사용됩니다. 성공하면 AI에 보상을 하고, 실패하면 벌칙을 줍니다. 기계는 시행착오를 통해 학습합니다.
1. multi-armed bandit problem ( 다중 무장 강도 문제 )
확률 이론과 강화 학습에서 자주 다루어지는 고전적인 문제로, 탐험(exploration)과 활용(exploitation) 간의 균형을 잘 나타내고 있습니다. 이 문제는 슬롯 머신(또는 "한팔 강도")이 여러 대 있는 카지노의 도박꾼을 비유로 사용하여 설명됩니다.
문제 설명
상황 설정:
도박꾼은 여러 개의 슬롯 머신이 있는 카지노에 있습니다. 각 슬롯 머신은 다르게 설정된 보상(수익)을 가지고 있으며, 도박꾼은 어느 머신이 가장 높은 보상을 제공할지 알지 못합니다.
도박꾼의 목표는 제한된 시간 동안 가장 많은 보상을 얻는 것입니다.
탐험 vs. 활용:
탐험: 새로운 슬롯 머신을 시도하여 보상을 얻으려는 행동입니다. 이는 어떤 머신이 더 좋은지를 알아내기 위해 필요합니다.
활용: 이미 알고 있는 정보에 기반하여 가장 높은 보상을 제공하는 머신을 선택하는 행동입니다. 이는 현재 알고 있는 최선의 선택을 활용하여 최대의 보상을 얻으려는 것입니다.
문제의 도전:
도박꾼은 언제 탐험을 하고 언제 활용을 할지를 결정해야 하며, 이 균형을 잘 맞추는 것이 문제의 핵심입니다.
지나치게 탐험에 치중하면 이미 좋은 보상을 주는 머신을 놓칠 수 있고, 반대로 지나치게 활용에 치중하면 새로운 머신의 가능성을 탐색하지 못하게 됩니다.
해결 방법
다중 무장 강도 문제는 여러 가지 방법으로 접근할 수 있습니다. 일반적인 방법들은 다음과 같습니다:
ε-탐욕적 알고리즘 (ε-greedy algorithm):
일정 확률(ε)로 무작위로 슬롯 머신을 선택하고, 나머지 시간 동안 가장 높은 보상을 주는 머신을 선택합니다.
이 방식은 탐험과 활용의 균형을 유지하는 간단한 방법입니다.
UCB (Upper Confidence Bound):
각 머신의 평균 보상과 신뢰 구간을 계산하여, 신뢰 구간이 넓은 머신을 선택하여 탐험을 할 수 있도록 합니다.
토너먼트 선택 (Thompson Sampling):
각 슬롯 머신에 대해 베이지안 접근을 사용하여, 각 머신의 보상을 샘플링한 후 그 중에서 가장 높은 샘플을 선택합니다.
응용 분야
다중 무장 강도 문제는 여러 분야에 응용될 수 있습니다. 예를 들어:
온라인 광고: 여러 광고 중에서 어떤 광고가 가장 높은 클릭률을 보이는지 탐색하고 활용하는 데 사용됩니다.
의료 연구: 새로운 치료법과 기존 치료법 중 어떤 것이 더 효과적인지 결정하는 데 사용할 수 있습니다.
웹사이트 A/B 테스트: 여러 디자인이나 기능을 비교하여 어떤 것이 사용자에게 더 많은 가치를 제공하는지 파악하는 데 유용합니다.
이와 같은 다중 무장 강도 문제는 실제 상황에서의 결정-making 과정에서 매우 중요한 역할을 합니다.
2. 확률 분포의 특성과 다중 무장 강도 문제에서 어떤 분포가 더 나을까?
확률 분포:
확률 분포는 랜덤 변수의 값들에 대해 확률이 어떻게 분포되는지를 설명합니다. 슬롯 머신의 맥락에서, 각 머신은 다양한 결과(즉, 상금)의 확률을 나타내는 고유한 분포를 가지고 있습니다.
평균, 중앙값, 최빈값:
평균: 모든 결과의 평균으로, 확률에 의해 가중치가 부여됩니다. 평균이 높을수록 잠재적으로 높은 상금을 나타냅니다.
중앙값: 결과를 정렬했을 때 중간에 위치한 값으로, 전형적인 상금을 나타냅니다.
최빈값: 가장 자주 발생하는 결과로, 가장 일반적인 상금을 보여줍니다.
왜곡(Skewness):
왼쪽으로 치우친 분포: 왼쪽에 긴 꼬리를 가진 분포로, 일반적으로 더 큰 값(높은 상금)이 더 많이 집중되어 있고 몇 개의 작은 값(낮은 상금)이 존재합니다.
이런 분포는 높은 평균을 가지는 경향이 있습니다.
가장 좋은 슬롯 : 5번 왼쪽으로 치우친 분포를 가지고 있어 더 높은 평균, 중앙값, 최빈값을 제공하기 때문입니다. 또한 4번 머신도 이러한 특성을 가지므로 수용 가능하다고 여겨집니다. 기본적으로, 더 많은 면적(특히 높은 쪽)이 있는 분포가 더 좋다고 생각할 수 있지만, 평균, 중앙값, 최빈값 같은 통계적 특성을 통해 각 머신의 잠재적 수익을 더 잘 이해할 수 있습니다.
3. 상한 신뢰 구간(Upper Confidence Bound, UCB)
다중 무장 강도 문제에서 탐험(exploration)과 활용(exploitation)의 균형을 맞추기 위해 사용되는 인기 있는 알고리즘입니다. 이 알고리즘은 각 행동(또는 슬롯 머신)의 추정 가치를 기반으로 선택하되, 그 추정치에 대한 불확실성을 고려합니다.
UCB의 주요 개념
신뢰 구간(Confidence Bounds):
UCB는 각 행동의 잠재적 보상을 추정하기 위해 신뢰 구간을 사용합니다. "상한 신뢰 구간"은 이 신뢰 구간의 상한값을 의미합니다. 즉, 특정 행동을 선택했을 때 받을 수 있는 최대 보상에 대한 추정을 나타냅니다.
탐험 vs. 활용:
이 알고리즘은 시간에 따라 누적 보상을 극대화하기 위해 가장 높은 추정 보상을 가진 행동을 선택합니다. 이를 위해, 잘 알려진 행동뿐만 아니라 덜 알려진 행동에 대한 탐험도 고려합니다.
UCB의 장점
UCB는 효율적이고 수학적으로 잘 정의되어 있으며, 확률적 특성을 바탕으로 탐험과 활용을 적절히 조화롭게 수행할 수 있습니다.
여러 상황에서 좋은 성능을 보이며, 특히 변동성이 큰 환경에서도 안정적인 결과를 제공합니다.
UCB 알고리즘은 실제 응용에서도 많이 사용되며, 예를 들어 온라인 광고, 추천 시스템, A/B 테스트 등 다양한 분야에서 활용됩니다.
4. 톰슨 샘플링 (Thompson Sampling )
다중무기문제(Multi-Armed Bandit Problem)를 해결하기 위한 확률적 알고리즘입니다. 이 알고리즘은 각 선택 가능한 옵션(예: 광고, 제품 등)의 성능을 지속적으로 업데이트하고, 선택 확률에 기반하여 최적의 선택을 시도합니다.
기본 개념
확률적 접근:
이 알고리즘은 각 옵션의 성공 확률에 대한 사전 분포(prior distribution)를 설정하고, 이를 기반으로 각 옵션의 보상을 모델링합니다.
일반적으로 베르누이 분포(success/failure)나 정규 분포와 같은 분포를 사용합니다.
알고리즘 작동 방식
사전 분포 설정:
각 슬롯 머신(또는 광고)에 대해 초기 사전 분포를 설정합니다. 예를 들어, 각 머신의 성공 확률을 Beta 분포로 가정할 수 있습니다.
Beta 분포는 두 개의 매개변수 α\alphaα와 β\betaβ를 가지고 있으며, α\alphaα는 성공 횟수, β\betaβ는 실패 횟수를 나타냅니다.
샘플링:
각 슬롯 머신에 대한 사전 분포에서 랜덤 샘플을 생성합니다.
이 샘플은 해당 슬롯 머신이 선택될 확률을 나타냅니다.
선택:
샘플링된 값 중 가장 큰 값을 가진 슬롯 머신을 선택합니다.
선택된 머신에서 보상을 받고, 해당 머신의 성공 또는 실패에 따라 α\alphaα와 β\betaβ 값을 업데이트합니다.
반복:
이 과정을 여러 번 반복하면서 각 머신의 성능에 대한 정보를 업데이트하고, 장기적으로 보상이 최대화되도록 합니다.
장점
탐험과 활용의 균형: Thompson Sampling은 자연스럽게 탐험(exploration)과 활용(exploitation) 사이의 균형을 맞추어, 확률적으로 더 나은 선택을 하게 됩니다.
유연성: 여러 가지 분포를 사용하여 다양한 문제에 적용할 수 있습니다.
실시간 업데이트: 새로운 데이터를 받으면 각 머신의 확률 분포를 쉽게 업데이트할 수 있습니다.
단점
복잡성: 구현이 다소 복잡할 수 있으며, 분포의 선택이 결과에 영향을 미칠 수 있습니다.
추가적인 계산: 각 슬롯 머신의 확률 분포를 샘플링하는 과정이 추가적인 계산을 필요로 합니다.
요약
Thompson Sampling은 다중무기문제에서 효과적으로 보상을 최대화하기 위한 방법론으로, 각 선택 옵션의 성능을 확률적으로 모델링하여 탐험과 활용을 조화롭게 수행합니다. 이 알고리즘은 광고 추천, A/B 테스트, 웹사이트 최적화 등 다양한 분야에 널리 사용됩니다.
위의 척도를 고려해 보면, 가로축은 우리가 Bandit(무기)에서 얻는 수익(Return)을 나타냅니다. 여기서는 개념을 이해하기 위해 세 개의 Bandit(슬롯 머신)을 고려하고 있습니다. 각 머신(무기) 뒤에는 특정한 분포(distribution)가 존재합니다.
처음에는 모든 머신들이 동일합니다. 그래프 2에서는 몇 번의 시험 실행을 보여줍니다. 이러한 시험 실행을 바탕으로 알고리즘은 하나의 분포를 구성합니다.
예를 들어, 그래프 2에서 파란색 머신을 고려해 보면, 여러 번 선택해 몇 가지 값(예: 그래프에서 표시된 대로 4개의 값)을 얻습니다. 이 값들을 기반으로 하나의 분포를 구성하게 됩니다.이 분포는 실제 머신 뒤에 있는 진짜 분포를 나타내지 않습니다. 대신, 우리가 실제 기대값이 어디에 있을지 생각하는 분포를 구성하는 것입니다. 사실, 우리는 머신 자체를 재구성하는 것이 아니라, 이러한 머신들이 어떻게 만들어졌을지 추정하여 분포를 재구성하는 것입니다.
Thompson Sampling 알고리즘이 각 머신의 실제 분포를 완벽히 복원하는 것이 아니라, 시험 실행을 통해 기대값이 어디에 위치할지 추정하는 분포를 만들어내는 과정을 설명하고 있습니다.
이것은 확률적 알고리즘(Probabilistic Algorithm임을 보여줍니다 (그래프 3을 보면, μ∗ (실제 기대값)가 분포 곡선 내 어디에서나 위치할 수 있음을 나타냅니다. 즉, 알고리즘이 확률적으로 기대값을 추정하는 방식을 강조하고 있습니다.)
그래프 4에서, 각 분포(파란색, 녹색, 노란색)에서 값이 선택됩니다 이것은 "X"로 강조되어 있습니다. 이렇게 함으로써 우리는 자신만의 Bandit 구성을 생성하게 됩니다 (즉, 우리만의 가상 세계에서 가상의 머신 세트를 만든 것입니다). 문제를 해결하기 위해, 우리는 가장 높은 기대 수익을 가지고 있는 녹색 머신을 선택합니다.
이제 우리가 가상의 세트에서 얻은 이 결과들을 실제 세계로 변환해야 합니다.
가상으로 생성한 분포와 머신들에서 도출한 결과를 현실의 문제에 적용하는 과정이 필요합니다. Thompson Sampling의 가상 모델링 결과를 실제 선택에 반영하는 단계를 나타냅니다.
가상 세계에서 우리는 녹색 머신을 선택했으므로, 실제 세계에서도 알고리즘은 녹색 머신을 선택합니다. 이때 녹색 머신의 레버를 당기면, 하나의 값이 나옵니다. 이 값은 녹색 머신 뒤에 있는 실제 분포에 기반하여 결정됩니다(이것이 그래프 5에 표시된 실제 기대값입니다).
이제 우리는 새로운 정보(즉, 새로 얻은 값)를 얻었으며, 이 값을 기반으로 분포를 추가하고 조정해야 합니다. 그래프 6에서, 분포의 변화(즉, 분포가 좁아지는 것)를 볼 수 있습니다. 새로운 정보를 추가할 때마다 우리의 분포는 더욱 정밀해집니다. 새로운 데이터를 얻을 때마다, 그 데이터를 기반으로 분포를 업데이트하고 조정하는 과정입니다. 반복적으로 정보를 추가할수록 알고리즘이 예측하는 분포는 더 정확하고 세밀해집니다.
이제 그 다음에 일어나는 일은 새로운 라운드입니다. 다시 새로운 값을 뽑아서 가상 세계에서 우리만의 Bandit 구성을 생성합니다. 그리고 최적의 Bandit을 선택하고, 그 Bandit의 레버를 당겨서 어떤 값을 얻습니다 이것이 실제 세계에서 받은 실제 값입니다. 그런 다음 이 값을 실제 세계에 반영하고 그에 맞게 조정을 해야 합니다. 이 과정은 계속 반복됩니다...
우리는 분포를 충분히 정교하게 다듬을 때까지 이 과정을 계속해야 합니다. 그래프 8에서 볼 수 있듯이 말이죠.
2. 상한 신뢰 구간(Upper Confidence Bound, UCB) 실습하기
◼ 광고 클릭 데이터 다른 디자인의 10개의 광고를 준비하고 10000 시도를 통해 사용자가 어떤 광고를 클릭했는지 결과를 정리한 표
