로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!== 전략 == === 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들의 확률분포에 관한 정보가 있을 경우에 사용할 수 있는 알고리즘이다. 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 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: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț