POST 개념 정리
강화학습의 근간 (5): 탐험의 이론 — Multi-Armed Bandit, Regret, 그리고 UCB
탐험-활용 딜레마를 상태도 전이도 없는 가장 순수한 형태로 격리한 Multi-Armed Bandit 문제를 형식화하고, 알고리즘의 성적표인 regret을 정의한다 — regret의 gap 분해, greedy와 고정 ε-greedy가 선형 regret을 벗어나지 못하는 이유, 로그가 넘을 수 없는 바닥임을 밝힌 Lai-Robbins 하한, 그리고 "불확실하면 낙관하라"는 원리를 Hoeffding 부등식으로 구현해 그 바닥에 도달하는 UCB1까지. 이 이론이 ε-greedy의 좌표와 UCT·알파고의 탐색 규칙이 서 있는 지반이다.