상한 신뢰구간 알고리즘 (upper confidence bound)
쉽게 풀면
각 선택지에 대해 지금까지의 평균 성과에다 “아직 덜 시도해 봐서 더 좋을지도 모른다”는 여유분을 더해 점수를 매깁니다. 적게 시도한 선택지일수록 이 여유분이 크므로 자연스럽게 시험 대상이 되고, 많이 시도해 확신이 생긴 선택지는 여유분이 줄어 평균 성과만으로 경쟁하게 됩니다. 불확실할 때는 낙관적으로 행동하라는 원리를 식으로 옮긴 것입니다.
왜 중요한가
무작위성에 기대지 않고 결정론적 규칙만으로 탐색과 활용을 조절하면서도 누적 후회의 상한을 수학적으로 증명할 수 있다는 점에서 이론적 가치가 큽니다. 이 원리는 밴딧을 넘어 몬테카를로 트리 탐색의 노드 선택 규칙으로 확장되어 바둑·체스 인공지능의 핵심이 되었습니다. 강화학습의 탐색 설계 전반에 개념적 영향을 미쳤습니다.
논문에서는 이렇게 쓰입니다
불확실성에 얼마나 큰 가산점을 줄지 조절해 탐색 정도를 튜닝했다는 뜻입니다.
조금 더 깊게 보면
대표적인 UCB1은 각 선택지의 표본평균에 전체 시행 횟수의 로그를 해당 선택지 시행 횟수로 나눈 값의 제곱근에 상수를 곱해 더합니다. 이 보너스 항은 호프딩 부등식으로 유도되는 신뢰구간의 폭에서 나오며, 그 덕분에 누적 후회가 시행 횟수의 로그에 비례하는 상한을 갖는다는 것이 증명됩니다. 트리 탐색에 적용한 UCT는 각 노드에서 이 규칙으로 자식을 고르며, 깊은 탐색과 넓은 탐색의 균형을 자동으로 맞춥니다.
주의할 점
신뢰구간이라는 이름을 공유하지만 통계적 추정치를 보고하는 목적이 아니라 선택을 위한 점수로 쓰인다는 점에서 용도가 다릅니다. 보상 분포가 유계가 아니거나 시간에 따라 변하면 기본 형태의 보장이 깨지므로 변형이 필요합니다.