기술적 요약: 인식론적 몬테카를로 트리 탐색

문제 제기

AlphaZero/MuZero(A/MZ) 알고리즘 계열은 몬테카를로 트리 탐색 (MCTS) 과 가치 및 환경 동역학의 학습된 모델을 통합함으로써 큰 성공을 거두었습니다. 그러나 중요한 한계가 존재합니다. 학습된 모델은 제한된 훈련 데이터 커버리지에서 비롯된 **인식론적 불확실성 (epistemic uncertainty)**을 도입하지만, 표준 MCTS 는 탐색 과정에서 이러한 불확실성의 전파를 고려하지 않습니다. 결과적으로 A/MZ 는 희소 보상 환경에서 **심층 탐색 (deep exploration)**을 위해 MCTS 를 효과적으로 활용하지 못합니다. 심층 탐색은 에이전트가 현재 상태와의 거리에 관계없이 새로운 전이 (transitions) 를 향해 스스로를 유도해야 하므로, 보상이 희소하고 상태 공간이 광범위한 알고리즘 설계나 프로그래밍과 같은 작업에 필수적인 능력입니다. 인식론적 불확실성을 고려하지 않으면, 부정확한 모델 예측에 기반한 하위 최적 정책으로 수렴하여 상태 공간의 필수 영역을 탐색하지 못하게 됩니다.

방법론: 인식론적 MCTS (EMCTS)

저자들은 심층 탐색을 촉진하기 위해 MCTS 과정에 인식론적 불확실성을 통합하는 이론적으로 동기 부여된 프레임워크인 **인식론적 MCTS (EMCTS)**를 제안합니다. 이 방법론은 세 가지 주요 구성 요소를 포함합니다:

1. 불확실성을 고려한 탐색 수립

저자들은 학습된 환경 모델 $\hat{M}$을 확률 변수로 모델링합니다. 그들은 학습된 모델 내의 가치 예측의 분산에 기반하여 최적 가치 함수 $Q^*$에 대한 상한 신뢰 구간 (Upper Confidence Bound, UCB) 을 유도합니다.

• 이론적 근거: 정리 1 은 학습된 모델 $\hat{M}$에 대해, 실제 최적 가치 $Q^*(s, a)$가 모델 내 최대 기대 가치에 그 가치의 표준 편차에 비례하는 항을 더한 값으로 상한이 결정됨을 보여줍니다. 여기서 상한은 신뢰도 매개변수 $\delta$에 의해 조정됩니다.
• 탐색 정책: 표준 PUCT(예측기 상한 신뢰 구간) 선택 정책은 **인식론적 P/UCT (EP/UCT)**로 수정됩니다. 선택 기준은 다음과 같습니다:
  $$a = \arg\max_{a} \left( q_{\hat{M}}(s, a) + \beta \sqrt{V[q_{\hat{M}}(s, a)]} + \text{탐색 항} \right)$$
  여기서 $q_{\hat{M}}$은 추정된 가치를 나타내고, $\sqrt{V[q_{\hat{M}}]}$는 인식론적 불확실성을 나타냅니다. 하이퍼파라미터 $\beta$는 활용과 탐색 사이의 균형을 조절합니다.

2. 인식론적 불확실성 전파

핵심 기여는 가치뿐만 아니라 불확실성을 탐색 트리를 통해 전파하는 메커니즘입니다.

• 백업 단계의 불확실성: 백업 단계 $\nu$의 불확실성은 즉시 보상의 분산과 할인된 미래 가치 불확실성의 분산을 합산하여 계산됩니다.
• 노드 가치 불확실성: A/MZ 는 계획 전반에 걸쳐 동일한 모델을 사용하므로, 백업 반환값은 상관관계를 가집니다. 독립성을 가정하지 않기 위해, 저자들은 개별 백업 반환값의 표준 편차의 합을 사용하여 노드 가치 $V[q_{\hat{M}}(s, a)]$의 분산에 대한 상한을 제안합니다:
  $$V[q_{\hat{M}}(s, a)] \leq \left( \frac{1}{N(s, a)} \sum_{i=1}^{N(s, a)} \sqrt{V[\nu_i(s, a)]} \right)^2$$
• 추정기: 이 방법은 보상 (예: 무작위 네트워크 증류 (RND) 또는 해시 기반 카운팅) 과 가치 (예: 불확실성 벨만 방정식 (UBE)) 에 대한 기존 불확실성 추정기를 활용합니다. 관찰되지 않은 전이의 경우, 분산은 유계 확률 변수에 대해 가능한 최대 분산으로 설정됩니다.

3. 학습된 전이 모델 처리

이론적 유도는 알려진 전이 모델을 가정하지만, 저자들은 학습된 전이 동역학 (MuZero 의 경우와 같이) 의 과제를 다룹니다. 저자들은 궤적에서 첫 번째 불확실한 전이를 마주치면, 해당 궤적의 모든 후속 예측이 최대 불확실성을 가진다고 가정하는 "최대 낙관적" 근사법을 제안합니다. 이는 탐색 목적으로 UCB 가 유효한 상한이 되도록 보장합니다.

주요 기여

1. 인식론적 MCTS (EMCTS): 학습된 가치 및/또는 보상 모델로부터 인식론적 불확실성을 추정하고 전파하여 MCTS 를 확장한 새로운 알고리즘으로, 탐색 과정이 불확실한 영역을 능동적으로 찾도록 합니다.
2. 이론적 프레임워크: 학습된 모델의 분산에 이론적으로 근거한 UCB 기반 탐색 정책 (EP/UCT) 의 유도로서, 심층 탐색을 위한 공식적인 메커니즘을 제공합니다.
3. 구현: AlphaZero 에이전트와 짝을 이루는 병렬화된 JAX 기반 EMCTS 구현으로, 어셈블리 언어 subleq 환경과 Deep Sea 벤치마크에 적용되었습니다.

실험 결과

저자들은 두 가지 도전적인 희소 보상 도메인에서 EMCTS 를 평가했습니다:

1. Subleq 프로그래밍 작업

• 작업: 특정 함수 (양수 부호 반전 및 항등 함수) 를 해결하기 위해 subleq 어셈블리 언어로 코드를 작성합니다. 이는 약 $16^{10}$개의 상태로 구성된 상태 공간을 탐색하는 것을 포함합니다.
• 결과: AlphaZero 와 짝을 이룬 EMCTS(E-AZ) 는 기준선 AlphaZero 를 크게 능가했습니다. E-AZ 는 기준선보다 훨씬 적은 샘플로 더 어려운 "항등 함수" 작업을 해결했습니다. 이 방법은 적절한 불확실성 추정기 (예: 전체 상태 해시 대비 IO 해시) 를 사용하는 것이 샘플 효율성을 더욱 향상시킨다는 것을 보여주었습니다.

2. Deep Sea 벤치마크

• 작업: 에이전트가 희소 보상을 가진 고유한 최적 궤적을 찾아야 하는 그리드 월드 환경입니다. 무작위 탐색을 통해 솔루션을 찾을 확률은 그리드 크기에 따라 지수적으로 감소합니다.
• 결과:
  • 심층 탐색: 기준선 A/MZ 에이전트는 합리적인 훈련 예산 내에서 Deep Sea 변형 (결정론적 및 확률적 보상 모두) 을 해결하지 못했습니다. 반면, EMCTS 에이전트 (E-AZ 및 E-MZ) 는 이러한 작업을 해결하여 환경 크기에 따른 샘플 복잡도의 아지수 (sub-exponential) 스케일링을 보여주었습니다.
  • 탐색의 이점: EMCTS 는 불확실성을 행동 선택에 사용했지만 불확실성을 추정하기 위해 탐색을 사용하지 않은 제거 실험 (A/MZ+UBE) 보다 크게 우월했습니다. 이는 탐색 자체가 불확실성 추정의 질을 향상시켜 더 효율적인 탐색으로 이어진다는 것을 확인시켜 줍니다.
  • 견고성: 이 방법은 MuZero 의 학습된 전이 동역학 (가치 등가 추상화) 을 사용할 때와 확률적 보상이 존재할 때도 효과적이었습니다.

중요성 및 주장

이 논문은 EMCTS 가 모델 기반 강화 학습의 근본적인 격차, 즉 표준 MCTS 가 탐색을 위해 인식론적 불확실성을 활용하지 못하는 문제를 해결한다고 주장합니다. 불확실성 전파를 탐색 트리에 통합함으로써, 이 방법은 A/MZ 에이전트가 다음과 같은 능력을 갖추도록 합니다:

• 희소 보상 환경에서 샘플 효율성을 크게 향상시킵니다.
• 기준선 A/MZ 로는 실제로 해결 불가능한 심층 탐색 벤치마크 (Deep Sea 등) 를 해결합니다.
• 가치 예측에 대한 더 나은 불확실성 추정을 제공함으로써 오프라인 RL 및 오프폴리시 목표 생성의 신뢰성을 향상시킬 수 있습니다.

저자들은 EMCTS 를 A/MZ 계열에 대한 실용적이고 이론적으로 동기 부여된 개선으로 위치시켜, 심층 탐색이 중요한 알고리즘 설계 및 희소 보상이 관련된 실세계 응용 분야에서 이러한 알고리즘이 더 잘 준비되도록 합니다.