로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요![[파일:Multi-armed bandit.jpg|섬네일]] '''Multi-armed bandit'''(멀티 암드 밴딧, MAB)은 탐색과 이용(Exploitaion & Exploitation)에 관한 [[강화 학습]] 분야의 유명한 문제이다. 평균 수익이 얼마인지 모르는 여러 개의 [[슬롯 머신]]이 있을 때, 어떤 슬롯 머신의 레버를 얼마나 당겨야 가장 높은 수익을 낼 수 있는가에 관한 문제로, 이름은 슬롯 머신을 일컫는 은어인 외팔 [[강도죄|강도]](One-armed bandit)에서 따왔다. 이 문제는 상태가 하나뿐인 [[마르코프 결정 과정]](Markov Decision Process)으로 볼 수 있다. == 용어 == ;arm (암): 각각의 슬롯머신을 의미한다. action이라고도 한다. ;reward (보상): 슬롯머신의 arm을 당길 때 얻는 수익을 말한다. ;regret (리그렛): 후회라는 뜻인데, 최선이 아닌 arm을 선택해서 입은 손해를 뜻한다. arm A를 선택했다면 100의 reward를 얻을 수 있었는데, arm B를 선택해 60의 reward만 얻었다면 regret은 40이다. 실제로는 최선의 arm에서 얼마를 얻을지 모르기 때문에, 최선이 아닌 각 arm에 대해서, 최선의 arm의 [[기댓값]]과 해당 arm의 기댓값의 차이를 그 arm의 시행횟수만큼 곱한 것을 모두 더해 계산한다. 이 regret을 최소화하는 것을 목표로 한다. ;exploration (탐색): 어떤 arm이 최선인지 찾기 위해 (지금까지의 평균이 가장 높지 않은) arm들을 시행해보는 것을 말한다. [[큰 수의 법칙]]에 의해 어떤 arm을 많이 시행해볼 수록 더 정확한 기댓값을 얻을 수 있게 된다. ;exploitation (이용): 시행을 통해 추정한 최선의 arm을 시행해서 이득을 얻는 것을 말한다. 탐색에만 너무 치중할 경우 최선이 아닌 arm이 너무 많이 선택되어 손해를 보고, 이용에만 너무 치중할 경우 최선이 아닌 arm을 최선이라고 착각하는 경우가 발생할 수 있다. 따라서 탐색과 이용의 비율을 적절히 선택하는 것이 핵심이다. == 전략 == === Epsilon-greedy 전략 === Epsilon-greedy (<math>\epsilon</math>-greedy) 전략은 지금까지 관찰한 결과 가장 기댓값이 높은 arm을 <math>1 - \epsilon</math>의 확률로, 그렇지 않은 arm을 <math>\epsilon</math>의 확률로 시도해보는 전략이다. 무한히 많은 시행을 거치면 가장 기댓값이 큰 arm을 발견할 수 있지만, 그렇게 발견한 뒤에도 일정 확률로 계속 테스트해보기 때문에 Regret이 시행 횟수에 정비례(<math>O(n)</math>)한다. <math>\epsilon</math>을 고정해놓지 않고 시행 횟수에 반비례(<math>\epsilon \propto 1/t</math>)하게 만들면 Regret이 <math>O(\log n)</math>으로 좋아진다. 그러나 이 전략은 현저하게 나쁜 것으로 밝혀진 arm과, 최적일 가능성이 남아있는 arm을 구분하지 않고 <math>\epsilon</math>을 일정하게 나눠가지기 때문에 비효율적이다. === UCB 알고리즘 === UCB (Upper Confidence Bound) 알고리즘은 현재까지 테스트해본 arm의 평균값과 시행 횟수를 이용해 모평균이 어느 범위에 있을지 추정하고, 그 범위의 상한이 가장 높은 arm을 선택하는 알고리즘이다. 시행횟수가 적은 arm은 이 범위가 넓어지고, 시행횟수가 많은 arm은 범위가 좁아지도록 하여 탐색과 이용을 적절하게 분배할 수 있다. ==== UCB1 ==== UCB 알고리즘의 일종인 UCB1은 다음과 같다. # 우선 모든 arm을 한 번씩 시도해본다. # UCB <math>\bar {x}_i+\sqrt{2\log n \over n_i}</math>를 최대로 만드는 arm <math>i</math>를 선택한다. # 2를 반복한다. 여기서 <math>\bar {x}_i</math>는 arm <math>i</math>에서 지금까지 얻은 reward의 평균(empirical mean), <math>n</math>은 여태까지 어떤 arm이든 시도한 총 횟수이고, <math>n_i</math>는 그 중 arm <math>i</math>를 시도한 횟수이다. <math>K</math>개의 arm이 있는 밴딧 문제에서 이 알고리즘을 따랐을 경우, 최대 regret은 다음과 같다. <math>\displaystyle \left[8\sum_{i:\mu_i<\mu^*} \left({\log n \over \Delta_i}\right)\right] + \left(1+{\pi^2 \over 3}\right)\left(\sum_{i\in[K]} \Delta_i\right)</math> 여기서 <math>\mu_i</math>는 <math>i</math>번째 arm의 평균 reward, <math>\mu^*</math>는 최적의 arm의 평균 reward를 말하며, <math>\Delta_i :=\mu^*-\mu_i</math>는 최적의 arm과 <math>i</math>번째 arm간의 평균 reward 차이를 말한다. <math>[K]</math>는 1부터 <math>K</math>까지의 자연수 집합이다. ==== KL-UCB ==== KL-Divergence를 이용하는 알고리즘으로, reward들의 확률분포에 관한 정보가 있을 경우에 사용할 수 있는 알고리즘이다. == 활용 == 웹사이트나 모바일 애플리케이션 등의 업데이트가 긍정적인 고객 반응(웹사이트 방문, 광고 클릭, 상품 결제 등)을 유도하는지 아닌지를 확인하고 싶을 때, 일부의 사용자에게는 기존 버전을, 다른 일부의 사용자에게는 새 버전을 보여줘서 테스트하는 것을 [[A/B테스트]]라고 부른다. 만약 새 업데이트가 사용자에게 부정적인 영향을 미친다면, 새 버전을 계속 노출하는 것이 큰 손해가 될 수도 있으며, 충분한 테스트를 거치지 않고 조급하게 결정을 내려버리는 경우도 발생할 수 있다. 이러한 테스트 과정에 밴딧 문제를 응용하면 테스트 기간 동안 일어날 수 있는 잠재적인 손해를 줄일 수 있고, 신뢰할 수 있을 만큼 테스트가 되었는지 역시 이론적으로 확인할 수 있다는 장점이 있다. [[분류:기계 학습]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț