MDP Planning as Policy Inference

이 논문은 MDP 계획을 최적의 기대 보상이 높은 정책의 사후 분포 추론 문제로 재정의하고, 변분 시퀀셜 몬테카를로 (VSMC) 를 적용하여 정책 불확실성을 고려한 확률적 제어 정책을 도출하는 새로운 프레임워크를 제안합니다.

핵심

🎩 제목: "최고의 길 찾기: 확률적 추론을 통한 MDP 계획"

(원제: MDP Planning as Policy Inference)

1. 핵심 아이디어: "한 가지 정답"이 아니라 "가능성들의 모임"

기존의 인공지능 (RL) 은 보통 **"가장 확실히 이기는 한 가지 전략"**을 찾아내려고 애씁니다. 마치 체스 대회에서 "이 수를 두면 무조건 이긴다"는 하나의 정답을 외우는 것과 비슷하죠.

하지만 이 논문의 저자 (데이비드 톨핀) 는 이렇게 말합니다.

"세상은 복잡해서 정답이 하나만 있는 경우가 드뭅니다. 오히려 '어떤 상황에서는 A 가 좋고, 다른 상황에서는 B 가 나을 수도 있다'는 여러 가지 가능성 (불확실성) 을 동시에 가지고 있어야 합니다."

그래서 이 논문은 인공지능이 '한 가지 전략'을 외우는 게 아니라, '전략들의 모임 (확률 분포)'을 학습하도록 설계했습니다. 마치 우리가 길을 찾을 때 "A 길만 가자"가 아니라, "A 길도 괜찮고, B 길도 나쁘지 않네, 날씨에 따라 C 길로 갈 수도 있겠다"라고 여러 시나리오를 머릿속에 그려보는 것과 같습니다.

2. 비유: "요리사들의 시식 대회" (베이지안 추론)

이 논문의 핵심은 **베이지안 추론 (Bayesian Inference)**을 사용하는 것입니다. 이를 요리사에 비유해 볼까요?

• 기존 방식 (엔트로피 정규화): 한 명의 요리사가 "맛을 내기 위해 조금씩 다양한 재료를 섞어보자 (엔트로피)"라고 생각하며 실험합니다. 하지만 이 '다양함'은 단순히 맛을 섞으려는 의도일 뿐, 진짜 실수가 났을 때의 위험을 고려하지 않을 수 있습니다.
• 이 논문의 방식 (정책 추론): 우리는 **수많은 요리사 (입자/Particles)**를 초대합니다.
  1. 각 요리사는 서로 다른 레시피 (전략) 를 가지고 요리를 합니다.
  2. 모든 요리사가 동일한 재료를 사용하고 동일한 오븐 (환경) 에서 요리합니다. (이게 중요한데, 환경의 변수를 공유해서 요리사 실력만 비교합니다.)
  3. 맛을 본 후, "이 요리사가 가장 맛있었네!"라고 점수를 매깁니다.
  4. 결과: 점수가 높은 요리사들의 레시피를 모아 '최고의 레시피 모음집 (후분포)'을 만듭니다.

이때 중요한 점은, 점수가 높은 요리사들이 모두 같은 레시피를 쓰는 게 아니라, 서로 다른 레시피를 쓰더라도 모두 '최고'일 수 있다는 점을 인정한다는 것입니다.

3. 두 가지 중요한 규칙 (알고리즘의 핵심)

이 '요리사 대회'를 성공적으로 치르기 위해 두 가지 규칙을 정했습니다.

1. 일관성 유지 (Deterministic Policy Consistency):

   • 한 요리사가 "A 상태에서는 소금을 넣겠다"라고 결정하면, 나중에 다시 A 상태에 오더라도 반드시 소금을 넣어야 합니다.
   • 처음에 결정했던 것을 기억 (Memoization) 하고 반복해서 적용해야 합니다. 그래야 "이 요리사가 진짜 실력자인지, 아니면 운이 좋았는지"를 정확히 알 수 있습니다.

2. 공유된 운 (Coupled Transition Randomness):

   • 모든 요리사가 동일한 오븐의 온도 변화를 경험해야 합니다.
   • 만약 요리사 A 는 오븐이 뜨거워져서 실패했고, 요리사 B 는 오븐이 시원해서 성공했다면, 그건 요리사 실력 차이가 아니라 '운'의 차이입니다.
   • 그래서 모든 요리사가 **동일한 환경의 변수 (운)**를 공유하게 만들어, 오직 전략의 차이만 점수에 반영되도록 합니다.

4. 실제 행동: "토마스 샘플링" (Thompson Sampling)

학습이 끝나고 실제로 행동을 취할 때는 어떻게 할까요?

• 기존 방식: "가장 확률이 높은 행동을 하나만 고른다."
• 이 논문의 방식: "머릿속에 있는 '최고 레시피 모음집'에서 하나라도 무작위로 뽑아서 그 레시피대로 행동한다."

이것은 토마스 샘플링이라고 불리는 방식입니다.

"오늘은 A 요리사의 레시피로 요리해 볼까? 아니면 B 요리사의 레시피로?"

이렇게 하면, 어떤 행동이 정말 최선인지 확신이 서지 않을 때는 자연스럽게 다양한 시도를 하게 됩니다. 반대로, "A 가 무조건 최고다"라고 확신이 서면 자연스럽게 A 만 선택하게 됩니다. 즉, 불확실성이 행동의 다양성으로 자연스럽게 이어지는 것입니다.

5. 실험 결과: 왜 이 방식이 좋은가?

저자는 여러 게임 (그리드 월드, 블랙잭, 타이어 교체 게임 등) 에서 이 방식을 테스트했습니다.

• 그리드 월드: 기존 방식 (SAC) 은 엔트로피 (다양성) 를 높이기 위해 벽으로 가는 행동을 하기도 했지만, 이 방식은 "벽으로 가면 위험하니까 피해야지"라고 확실히 판단했습니다.
• 블랙잭: 기존 방식은 최적의 전략에 도달하려면 '엔트로피'를 아주 낮게 설정해야 했지만, 이 방식은 자연스럽게 최적의 전략에 가까워졌습니다.
• 타이어 게임 (Triangle Tireworld): 위험한 상황 (타이어 펑크) 이 있을 때, 보상의 크기에 따라 '불확실성'을 조절할 수 있었습니다. 보상이 너무 크면 너무 확신에 차서 위험을 감수하고, 보상을 작게 하면 더 신중하게 행동했습니다.

6. 결론: "불확실함을 인정하는 지혜"

이 논문의 가장 큰 메시지는 **"최고의 결정을 내리기 위해서는, '무엇이 정답인지'에 대한 불확실함을 인정하고 관리해야 한다"**는 것입니다.

기존의 인공지능은 "정답을 찾으자"고 외치며 한 가지 길만 쫓았지만, 이 논문의 인공지능은 **"여러 가지 가능성이 있을 수 있으니, 그 가능성을 모두 고려해서 상황에 맞게 유연하게 행동하자"**고 말합니다.

마치 우리가 길을 잃었을 때, "내 길만 믿고 가자"가 아니라 "지도에 여러 길이 표시되어 있으니, 상황에 따라 가장 유망한 길을 골라 가자"는 태도와 같습니다. 이것이 바로 불확실성 속에서도 최선의 결정을 내리는 새로운 지혜입니다.

기술 요약

논문 개요: MDP 계획 (Planning) 을 정책 추론 (Policy Inference) 으로

이 논문은 이산적 (discrete) 상태 공간을 가진 에피소드형 마르코프 결정 과정 (MDP) 의 계획 문제를 정책 (Policy) 에 대한 베이지안 추론으로 재구성합니다. 기존의 '제어로서의 추론 (Control-as-Inference)'이나 엔트로피 정규화 강화학습과 달리, 이 접근법은 원래의 기대 보상 (expected return) 최적화 목표를 유지하면서 불확실성을 명시적으로 모델링합니다.

1. 문제 정의 및 배경

• 기존 접근법의 한계:
  • 기존 확률적 계획 및 제어-as-추론 방법들은 종종 엔트로피 정규화 항을 도입하거나 가상의 최적성 변수 (optimality variables) 를 추가하여 표준적인 잠재 - 관측 모델 템플릿에 맞추는 방식을 취했습니다.
  • 이러한 방법들에서 확률성 (stochasticity) 은 주로 탐색 (exploration) 을 위한 모델링 선호도이거나 휴리스틱한 정규화 장치로 간주되며, 원래의 기대 보상 문제의 해에 대한 불확실성을 직접적으로 해석하기 어렵습니다.
• 목표:
  • 기대 보상 최적화 기준을 변경하지 않으면서, 최적 행동에 대한 불확실성을 '사후 분포의 분산 (posterior dispersion)'으로 명시적으로 표현하는 프레임워크를 제안합니다.
  • 추론된 정책 분포를 기반으로 행동 선택 시, 엔트로피 정규화가 아닌 Thompson Sampling의 관점에서 확률적 제어 정책을 유도합니다.

2. 방법론 (Methodology)

2.1 확률적 모델 (Probabilistic Model)

• 잠재 변수로서의 정책: 정책 $\pi$를 잠재 확률 변수로 간주합니다.
• 비정규화 확률 (Unnormalized Probability): 각 정책에 대해 기대 보상 (expected return) 에 단조 증가하는 비정규화 로그 확률을 정의합니다.
  $$\log \tilde{p}(\pi) = \mathbb{E}_{\tau_\pi} \left[ \sum_{t=1}^H R(s_t, a_t, s_{t+1}) \right]$$
  여기서 $\tau_\pi$는 정책 $\pi$에 따라 생성된 트래젝토리입니다.
• 결과: 이 정의는 정책 공간에 볼츠만 - 깁스 분포 (Boltzmann-Gibbs distribution) 를 유도하며, 사후 분포의 모드 (mode) 는 기대 보상을 최대화하는 정책과 일치합니다.

2.2 추론 알고리즘: 변분 시퀀셜 몬테카를로 (VSMC) 의 적응

이산적 MDP 와 확률적 전이 (stochastic transitions) 환경에서 사후 분포를 근사하기 위해 VSMC를 수정하여 적용했습니다.

1. 확정적 정책 일관성 (Deterministic Policy Consistency):
   • 입자 (particle) 당 각 상태에 처음 방문할 때만 행동을 샘플링하고, 이후 재방문 시에는 동일한 행동을 재사용합니다 (메모화).
   • 이는 입자가 하나의 확정적 정책을 따르도록 강제하여, 정책의 일관성을 유지합니다.
2. 결합된 전이 무작위성 (Coupled Transition Randomness):
   • 입자 간의 가중치 차이가 환경 노이즈가 아닌 정책의 차이를 반영하도록 합니다.
   • 동일한 상태와 행동을 취하는 입자들은 동일한 전이 결과 (shared random realization) 를 공유하도록 강제합니다. 이는 공통 무작위수 (Common Random Numbers) 기법과 유사하게 구현됩니다.
3. 최적화 목적 함수:
   • 이산 행동 공간에서는 재파라미터화 (reparameterization) 가 불가능하므로, 스코어 함수 (score-function) 항을 포함하여 편향되지 않은 그래디언트 추정치를 얻습니다.
   • 목적 함수는 SMC 로그 증거 (log-evidence) 의 기대값을 최대화하는 형태로 구성됩니다.

2.3 행동 선택 (Policy Selection)

• 사후 예측 샘플링 (Posterior Predictive Sampling):
  • 실행 시, 사후 분포에서 하나의 확정적 정책을 샘플링하고 해당 정책이 지시하는 행동을 수행합니다.
  • 이는 반복적 Thompson Sampling으로 해석됩니다.
  • 기대 보상이 명확히 구분되면 사후 분포가 집중되어 결정론적 행동에 가까워지고, 보상이 유사하면 분산이 커져 최적의 확률적 행동 (선호도에 대한 불확실성 하에서) 을 수행합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 프레임워크: 기대 보상 최적화 기준을 유지하면서 정책을 잠재 변수로 하는 베이지안 추론 프레임워크를 제안했습니다.
2. 알고리즘 개선: 확률적 전이를 가진 이산 MDP 에서 확정적 정책 추론을 위한 VSMC 적응 (정책 일관성 및 결합된 전이 무작위성) 을 제시했습니다.
3. 실험적 검증: 다양한 이산적 벤치마크 (Grid World, Blackjack, Tireworld, Academic Advising) 에서 유도된 확률적 제어 정책의 특성을 분석하고, **Discrete Soft Actor-Critic (SAC)**과 비교했습니다.

4. 실험 결과 (Results)

• Grid World:
  • VSMC 는 SAC 와 달리 엔트로피를 높이기 위해 경계로 향하는 행동을 피합니다. 대신 환경의 확률성 (미끄러짐) 만을 고려하여 목표 도달 가능성을 극대화하는 정책을 학습합니다.
  • 공유된 동역학 (shared dynamics) 을 사용할 때 미끄러운 환경에서 swamp(늪) 를 피하는 더 안정적인 정책을 학습했습니다.
• Blackjack:
  • 알려진 최적 정책과 비교 시, VSMC 는 SAC 보다 더 높은 기대 보상을 달성했습니다.
  • SAC 가 VSMC 와 유사한 성능을 내기 위해서는 엔트로피 가중치 ($\alpha$) 를 매우 낮게 (0.01 수준) 설정해야 했으며, 이는 VSMC 가 내재적으로 더 효율적인 탐색 - 이용 균형을 이룸을 시사합니다.
• Triangle Tireworld:
  • 보상의 크기가 클 경우 (큰 보상 간극), VSMC 의 사후 분포가 과도하게 집중되어 성능이 저하되는 경향을 보였습니다.
  • 보상을 축소 (scaling down) 하면 분산이 적절히 유지되어 SAC 와 유사한 성능을 보였습니다. 이는 베이지안 추론이 보상 스케일에 민감할 수 있음을 보여줍니다.
• Academic Advising:
  • 복잡한 조합적 문제에서 VSMC 와 SAC 모두 어려운 인스턴스에서 어려움을 겪었으나, VSMC 는 성공 가능한 인스턴스에서 더 두꺼운 꼬리 (heavier tails) 를 가진 수익 분포를 보였습니다. 이는 다양한 해결책에 대한 불확실성을 더 잘 포착함을 의미합니다.

5. 의의 및 결론 (Significance)

• 불확실성의 분리: 이 접근법은 환경의 무작위성 (aleatoric uncertainty) 과 최적 행동에 대한 인지적 불확실성 (epistemic uncertainty) 을 명확히 분리합니다.
• Thompson Sampling 의 해석: 유도된 확률적 제어 정책은 엔트로피 정규화가 아니라, 여러 개의 확정적 행동이 모두 타당할 때 발생하는 구조화된 Thompson Sampling으로 해석됩니다.
• 의사결정 의미: 단일 매개변수화된 확률적 정책을 최적화하는 대신, 일관된 행동들 (deterministic policies) 사이에서 확률적으로 선택함으로써, 선호도에 대한 불확실성이 행동의 확률성으로 자연스럽게 투영됩니다.
• 한계 및 확장: 현재는 이산 상태 공간에 초점을 맞추었으나, 연속 공간에서는 해시 가능한 상태 추상화나 공통 무작위수 기법을 통해 확장 가능하다고 주장합니다.

이 논문은 강화학습의 계획 문제를 추론의 관점에서 재해석함으로써, 기존 방법론들이 간과했던 '해에 대한 불확실성'을 정량화하고 이를 제어 정책에 효과적으로 통합하는 새로운 패러다임을 제시합니다.