기술 요약: 확률적 최단 경로 문제(Stochastic Shortest Path Problem)를 위한 베이지안 학습

1. 문제 정의

본 논문은 흡수 상태(absorbing terminal state)가 존재하는 무한 시계(infinite-horizon), 비할인(undiscounted) 마르코프 결정 과정(MDP)으로 정의되는 확률적 최단 경로(Stochastic Shortest Path, SSP) 문제를 다룬다. 표준적인 할인 MDP($\gamma < 1$)와 달리, SSP 공식($\gamma = 1$)은 고유한 보상 0의 목표 상태($s_g$)가 존재해야 하며, 적어도 하나의 "적절한 정책(proper policy)"(모든 상태에서 확률 1로 $s_g$에 도달하는 정책)이 존재해야 한다.

주요 목표는 벨만 최적 방정식(Bellman Optimality Equations, BOEs)을 만족하는 최적 행동-가치 함수 $Q^*$를 학습하는 것이다. 문제는 $Q^*$가 직접 관찰되지 않으며, 상호작용을 통해 상태-행동-보상 튜플 $(s, a, r)$만이 관찰된다는 점이다. 저자들은 $Q^*$에 대한 불확ness(uncertainty)를 정량화하고, 기존 베이지안 강화 학습(RL) 문헌에서 흔히 볼 수 있는 비현실적인 가정이나 임시방편적인 근사법에 의존하지 않고 톰슨 샘플링(Thompson Sampling, 사후 샘플링)을 통해 탐색-활용(exploration-exploitation) 트레이드오프를 촉진하기 위한 베이지안 프레임워크를 구축하고자 한다.

2. 방법론

2.1. 벨만 방정식을 통한 가능도(Likelihood) 구축

핵심적인 방법론적 기여는 확률적 근사 알고리즘(예: Q-learning)이나 시간차(Temporal Difference, TD) 오차가 아니라, 벨만 최적 방정식(BOEs)에 기반하여 가능도 함수를 직접 구축하는 것이다.

• 매개변수화: 최적 가치 함수는 매개변수 함수 $Q_\theta$로 근사된다.
• 제약 조건: 상태-행동 쌍 $(s, a)$에 대해, 기대 보상 $\bar{r}_{s,a}$는 반드시 BOE $\bar{r}_{s,a} = Q_\theta(s, a) - \mathbb{E}[\max_{a'} Q_\theta(S', a')]$를 만족해야 한다.
• 가능도: 저자들은 관측된 보상 $r_t$가 결정론적인 기대 보상에 노이즈가 더해진 것으로 모델링되는 가능도 함수 $p(r_t | \theta, \psi, s_t, a_t)$를 정의한다. 이는 관측된 BOE와 일치하도록 매개변수 $\theta$를 제약한다.

2.2. 결정론적 보상 및 매니폴드 사후 분포 처리

보상이 결정론적(노이즈가 없는 경우)일 때 중대한 이론적 과제가 발생한다. 이 경우, BOE는 $\theta$에 대해 엄격한 등식 제약을 부과한다.

• 매니폴드 밀도: $\theta$의 사후 분포는 전체 매개변수 공간에서 BOE 제약의 교차로 정의되는 저차원 매니폴드로 붕괴된다.
• 하우스도르프 측도(Hausdorff Measure): 저자들은 이 사후 분포를 표준 르베그 밀도(Lebesgue density)가 아닌 하우스도르프 측도에 대한 밀도로서 특성화한다(정리 2). 이는 노이즈가 없는 보상에 대한 사후 분포를 수학적으로 엄밀하게 기술한다.

2.3. 가능도 완화 및 근사

매니폴드 밀도로부터 직접 샘플링하는 것은 표준 몬테카를로 방법으로는 계산적으로 불가능하다. 추론을 용이하게 하기 위해 저자들은 **가능도를 완화(relaxing the likelihood)**할 것을 제안한다.

• 컨볼루션(Convolution): 정확한 가능도를 허용 오차 $\epsilon$을 가진 커널(예: 가우시안 또는 균등 분포)과 컨볼루션한다.
• 르베그 밀도: 이러한 완화는 매니폴드를 "두껍게" 만들어, MCMC 샘플링에 적합한 표준 르베그 밀도를 가진 사후 분포를 생성한다.
• 트레이드오프: 본 논문은 이러한 완화의 결과를 엄밀하게 분석한다. 완화는 계산 가능한 샘플링을 가능하게 하지만, 식별 불가능성(unidentifiability) 문제를 유발한다. 구체적으로, 테이블형 매개변수화(tabular parametrization)의 경우, 완화된 가능도는 부적절한 정책(목표에 도달하지 못하는 정책)에 해당하는 매개변수 집합에 무한한 질량을 할당할 수 있는 반면, 정확한 사후 분포는 그렇지 않다.

2.4. 탐색을 위한 사후 샘플링

프레임워크는 탐색을 위해 톰슨 샘플링(사후 샘플링)을 활용한다. 각 에피소드마다 $Q_\theta$의 사후 분포로부터 정책을 샘플링하며(직접 $\theta$를 샘플링하거나 정책에 대한 확률 질량을 계산함), 목표에 도달하거나 부적절한 루프가 감지될 때까지 해당 정책을 실행한다.

3. 주요 기여

1. 엄밀한 베이지안 공식화: 본 논문은 TD 기반 베이지안 RL에서 흔히 사용되는 휴리스틱한 가능도를 피하고, 벨만 최적 방정식으로부터 직접 가능도를 도출하는 SSP를 위한 제일 원칙(first-principles) 기반의 베이지안 공식을 제공한다.
2. 매니폴드 특성화: 결정론적 보상의 경우 사후 분포가 저차원 매니폴드에 존재함을 입증하고, 하우스도르프 측도에 대한 명시적인 밀도 공식을 제공한다(정리 2).
3. 완화 및 식별 불가능성 분석: 저자들은 (Lebesgue 밀도를 위해) 가우시안 커널로 가능도를 완화하는 과정이 가져오는 특정 식별 불가능성 문제를 수학적으로 증명한다: 즉, 사전 분산(prior variance)이 클 경우 완화된 가능도가 부적절한 정책(목표에 도절하지 못하는 정책)에 지배적인 사후 분포를 만들 수 있다(정리 4). 이는 정확한 사후 분포가 부적절한 정책을 올바르게 배제하는 것과 대조적이다.
4. 테이블형 사후 분포 도출: 가우시안 사전 분포와 완화된 가능도를 가진 테이블형 매개변수화의 경우, 사후 분포가 절단된 가우시안(truncated Gaussians)의 혼합(mixture)임을 보여준다(명제 1).
5. 벤치마킹 및 실증적 검증: 저자들은 TD 기반 베이지안 방식(Bayes-TD, Bayes-TD-En, Bayes-TD-Max)과 비교하기 위해 "Deep Sea" 환경 변형을 사용하는 벤치마킹 프로토콜을 도입한다.

4. 결과

4.1. 이론적 발견

• 수렴: 완화 허용 오차 $\epsilon \to 0$에 따라, 근사 사후 분포는 정확한 매니폴드 사후 분포로 수렴한다.
• 부적절한 정책의 지배: 부적절한 정책이 존재하는 상황에서, 가우시안 사전 분포와 완화된 가능성을 결합하면 사후 분포의 질량이 부적절한 정책에 해당하는 방향으로 "늘어나서", 최적 행동 선택을 편향시킬 수 있다. 이 효과는 더 작은 $\epsilon$을 사용하거나 부적절한 정책을 명시적으로 페널티를 주는 사전 분포를 사용함으로써 완화될 수 있다.

4.2. 수치 실험

실험은 Deep Sea 벤치마크 변형(표준, 피라미드, 스월 환경)에서 수행되었다.

• 데이터 효율성: 제안된 프레임워크(Bayes-BR)는 특히 완화 허용 오차 $\epsilon$이 작을 때(예: 0.01) TD 기반 베이지안 방법들보다 우수한 데이터 효율성을 보였다.
• 수렴: 표준 Deep Sea 환경(깊이 3)에서 최적 정책의 사후 확률이 1로 빠르게 수렴했다.
• 다중 최적해: 여러 최적 정책이 존재하는 "Deep Sea Pyramid" 변형에서, 사후 분포는 모든 최적 정책에 질량을 균등하게 배분하였다.
• 부적절한 정책: 부적절한 정책이 포함된 "Deep Sea Swirl" 변형에서, 프레-임워크는 이론적인 부적절한 정책 지배 위험에도 불구하고, $\epsilon$이 충분히 작다면 최적 정책 클래스를 성공적으로 회복하였다.
• 샘PLING 과제: 연구에서는 $\epsilon$이 매우 작을 때(0.01) 표준 해밀토니안 몬테카를로(HMC)가 완화된 사후 분포로부터 효과적으로 샘플링하는 데 어려움을 겪는다는 점을 언급하며, 완화 후에도 매니폴드 근처에서의 샘플링이 어려움을 강조했다.

5. 의의 및 주장

본 논문은 자신의 프레임워크가 (Q-learning 업데이트에서 기인하는) "비현실적인 모델링 가정"이나 "임시방편적인 근사"에 의존하지 않고, SSP 설정에서 불확실성을 충실하게 정량화한다고 주장한다.

• 충실성(Faithfulness): 벨만 방정식으로부터 가능도를 도출함으로써, 결과적인 사후 분포는 MDP의 최적성 조건에 이론적으로 근거한다.
• 근사에 대한 통찰: 본 연구는 실제 적용 시 자주 사용되는 "완화" 단계에 대한 비판적인 수학적 분석을 제공한다. 이는 완화가 추론을 가능하게 하지만, 근본적으로 사후 분포의 기하학적 구조를 변화시켜 주의 깊게 관리하지 않으면 부적절한 정책을 선택하게 만들 수 있음을 밝혀낸다.
• 벤치마킹: 저자들은 새로운 베이esian RL 벤치마크를 제공하며, 자신들의 접근 방식이 SSP 설정에서 경쟁적인 TD 기반 베이지안 방법론보다 더 데이터 효율적임을 보여준다.

논문은 프레임워크가 견고하지만, 부적절한 정책을 명시적으로 제외하는 사전 분포를 설계하고 작은 $\epsilon$ 값을 다루기 위한 더 정교한 샘플링 방법을 개발하는 후속 연구가 필요함을 인정하며 겸허하게 결론을 맺는다.