Introduction
이 논문에서는 Markov Decision Process (MDP)에서의 planning 문제가, probabilistic graphical model에서의 여러 inference(marginal, MAP, MMAP 등) 가운데 어느 것과 가장 유사한지, 그리고 기존 방식들이 실제로 어떤 식으로 planning을 근사하고 있는지를 Variational Inference (VI) 관점에서 새롭게 분석했다. 결론적으로, 논문은 planning은 “기존 inference 중 어디에도 완벽히 속하지 않는 별도의 inference”에 해당하며, 이 planning inference가 확률 그래프 구조에서의 entropy 항을 특정 방식으로 가중하는 것과 정확히 일치한다고 주장했다.
이 관점에서, 이전에 “planning as inference”로 소개된 다양한 방법들(MAP, MMAP, marginal 등)이 사실은 정말로 planning 문제를 풀기 위한 최적의 inference가 아니라는 사실이 드러났다. 다만, 동적 환경에서(즉 확률적, 즉 stochastic dynamics가 존재할 때) MAP나 MMAP 방식은 비반응적(non-reactive) 정책을 가정하고 있어서 최적해로부터 크게 벗어날 수 있는 반면, 이 논문에서 제시한 “planning inference”가 이론적으로 정확한 접근임을 보여준다.
또한, 이 논문은 factored-state MDP에 대해서는 메시지 패싱 기반의 Value Belief Propagation (VBP) 알고리즘을 제안했다. 이는 standard MDP에서는 Bellman Backup과 동일하게, factored MDP에서는 이를 근사적으로 수행하게 된다. 그 과정에서 기존 loopy belief propagation (LBP) 알고리즘과 매우 흡사한 형태의 메시지 업데이트를 사용한다.
주요 아이디어와 수식
1. Planning을 Exponential Utility로 정식화
논문에서는 planning 시 얻고자 하는 목표로 다음을 정의했다:
$
F_{\lambda}^{\text{planning}} = \frac{1}{\lambda} \log \max_{\pi} \sum_{x,a} \exp\bigl(\lambda R(x,a)\bigr), P(x \mid a),\pi(a \mid x)
$
여기서
- $x = {x_t}$, $a = {a_t}$는 상태와 행동의 전 시점 시퀀스,
- $\lambda > 0$는 risk 매개변수,
- $R(x,a)$는 (누적) reward,
- $P(x \mid a)$는 MDP에서의 dynamics(초기 상태 $x_1$ 포함)이다.
이는 보통 additive reward(즉, $\sum R_t$) 대신 exponentiated sum인 형태로, $\lambda \to 0^+$일 때 기존의 risk-neutral planning(즉 기대 reward 최대화)로 수렴한다.
2. Planning Inference를 위한 Variational Formulation
$\max_{\pi}$ 형태 대신, 논문은 이 $\max_{\pi}$가 결국 variational 분포 $q(x,a)$(또는 $q(a_t|x_t)$)를 최적화하는 문제와 동일함을 보였다. 정리하면 다음과 같은 최적화 문제로 변환된다:
$ F_{\lambda}^{\text{planning}} = \max_{q(x,a)} \Big[\frac{1}{\lambda}\big(-E_{\lambda}(q)+ H_{\text{planning}}(q)\big)\Big] $
여기서
- $E_{\lambda}(q) = -\bigl\langle \log P(x_1)\bigr\rangle_{q} -\sum_{t=1}^{T-1}\bigl\langle \log P(x_{t+1}\mid x_t,a_t) + \lambda R_{t}(x_t,a_t,x_{t+1})\bigr\rangle_{q},$
- $H_{\text{planning}}(q) = H_q(x_1) + \sum_{t=1}^{T-1} H_q(x_{t+1}\mid x_t,a_t).$
이를 “planning inference”라고 부르며, 이때 entropy 항이 $H_{\text{planning}}(q)$가 된다. 이 항은 $H_q(x_1) + \sum_{t=1}^{T-1}H_q(x_{t+1}\mid x_t,a_t)$ 형태로, 기존 marginal inference의 entropy(즉 $H_q(x,a)$)와는 다르다.
3. 다른 Inference 타입 (MAP, MMAP, Marginal 등)과 비교
다른 inference 타입들도 유사하게 VI 문제로 표현 가능함이 알려져 있다. 예컨대,
- Marginal inference는 $H_q(x,a)$,
- MAP inference는 entropy가 0,
- MMAP inference는 $H_q(x,a)-H_q(a)$와 같이 특정 가중으로 구성.
이 논문의 주요 결론 중 하나는, 아래 부등식을 통해 각 inference가 planning 문제에서 만들어내는 하한(혹은 상한) 관계를 분석했다:
$ F_{\lambda}^{\text{MAP}}\text{ or }F_{\lambda}^{\text{marginalU}} \le F_{\lambda}^{\text{MMAP}} \le F_{\lambda}^{\text{planning}} \le F_{\lambda}^{\text{marginal}}, $
단, dynamics가 deterministic할 경우, MMAP와 planning이 같아지고 MAP도 동일 값이 되지만, 일반적 확률적(= stochastic) 환경에서는 이 관계가 중요하다. 즉, stochastic한 환경에서는 MAP나 MMAP가 잘못된(=비반응적) 정책을 줄 가능성이 커진다.
4. Factored MDP에서의 Value Belief Propagation
state가 factored (즉, $x_t=(x_t^{(1)},\dots,x_t^{(Ne)})$)되어 있고, 각 entity가 제한된 parent에 의존하는 식으로 표현된 MDP에서는 상태 공간이 지수적으로 커진다. 기존의 “non-factored” MDP에서는 value iteration으로 정확 계산이 가능했으나, factored MDP에서는 일반적으로 infeasible하다.
논문은 standard Belief Propagation (BP)를 응용한 Value Belief Propagation (VBP) 알고리즘을 제안했다. 이는 variational formulation에서 pseudo-marginal 기반의 Bethe approximation을 도입하고, entropy 항을 $H_{\text{planning}}(q)$ 형태로 설정해서 message passing을 한다. 일반 loopy BP와 마찬가지로 수렴 보장은 없지만, 수렴 시 그 고정점은 해당 Bethe free energy에 대한 stationary point라는 점이 동일하다.
- $T$ 스텝 동안 각 factor(transition, reward)에 대해 메시지 업데이트를 반복한다.
- 최종 forward/backward 메시지가 Q-function 유사한 값을 형성해, $q(a_t|x_t)$를 근사 계산함.
- non-factored MDP(즉, 사슬 구조)에서는 이 방법이 Bellman update와 정확히 일치한다.
5. 실험 결과
- Synthetic factored MDP 실험에서, VBP가 “stochastic성이 큰” MDP에서 MAP이나 MMAP 대비 훨씬 우수한 결과를 냈다.
- IPPC 2011 벤치마크 실험에서도, stochastic도가 중간 정도일 때 VBP가 SOGBOFA (MMAP 방식) 등을 이기는 양상을 보였다.
- Determinization in hindsight 기법도 VI 관점에서 단일 concave 문제로 풀 수 있음을 보여, 기존처럼 샘플링 다수 필요 없이 일괄 계산 가능하다고 한다(물론 이 역시 상한에 불과).
결론 및 논의
- “Planning as inference”라는 구호는 예전부터 존재했지만, 정확히 어떤 inference가 이에 해당하는지는 혼재돼 있었다.
- 이 논문은 $H_{\text{planning}}(q)$라는 특정 entropy 가중으로 정의되는 inference가 진정한 “planning inference”임을 제시했다.
- 기존 MAP, MMAP, marginal inference 등은 stochastic 환경에서 suboptimal한 정책을 만들 수 있음을 보여주었다.
- factored MDP에 대해서는 (loopy) BP에 영감을 받은 VBP를 설계했고, 실험적으로 다른 기법 대비 우수함을 시사했다(특히 stochastic성이 충분히 큰 문제에서).
- 논문은 또한, risk parameter $\lambda$를 $\to 0^+$로 보내면 standard additive MDP로 환원되고, linear program (LP)으로도 표현된다는 점 등 추가 이론적 연계도 제시했다.
요약하자면, planning은 곧 “기존에 제시된 MAP나 marginal이 아닌, 새로운 entropy 구조를 가지는 inference”로 이해할 수 있으며, 그에 따른 VI formulation과 message passing 기법(VBP)이 효율적으로 factored MDP를 풀 수 있는 길을 연다는 점이 이 논문의 핵심 기여이다.
