18.7. 마르코프 결정 과정

20세기 초 수학자 안드레이 마르코프(Andrey Markov)가 메모리가 없는 확률 과정(Stochastic process)인 마르코프 연쇄(Markov chain)에 관해 연구했음. 이 과정은 정해진 개수의 상태를 가지고 있으며 각 스텝마다 한 상태에서 다른 상태로 랜덤하게 전이됨. 특정 상태에서 다른 상태로 전이되기 위한 확률은 고정되어 있으며 시스템에 메모리가 없으므로 과거 상태에 상관 없이 $(s, s')$ 쌍에 의존함. 이러한 성질을 마르코프 성질(Markov property)라고 함.

특정 상태에서 나오는 길이 없는 경우를 종료 상태(Terminal state)라고 함.

…

마르코프 결정 과정(Markovian decision process)은 1950년대 리처드 벨만(Richard Bellman)이 처음으로 논문에 기술함. 마르코프 연쇄와 비슷하지만 다른 점이 있음.

• 각 스텝에서 Agent가 여러 가능한 Action 중 하나를 선택할 수 있음.
• 전이 확률은 선택한 Action에 따라 달라짐.
• 어떤 상태 전이는 Reward(음수 또는 양수)을 반환함.
• Agent의 목적은 시간이 지남에 따라 보상을 최대화하기 위한 Policy를 찾는 것.

마르코프 결정 과정의 모든 상태에 행동이 하나씩 있고 모든 보상이 동일하다면 마르코프 연쇄로 표현할 수 있음.

…

최적의 상태 가치와 벨만 최적 방정식

벨만은 어떤 상태 $s$의 최적의 상태 가치(Optimal state value) $V^*(s)$를 추정하는 방법을 찾았음. 최적의 상태 가치란 Agent가 상태 $s$에 도달한 후 최적으로 행동한다고 가정하고 평균적으로 기대할 수 있는 할인된 미래 보상의 합임. 벨만은 Agent가 최적으로 행동하면 벨만 최적 방정식(Bellman optimality equation)이 적용된다는 것을 입증하였음. 이 재귀식은 Agent가 최적으로 행동하면 현재 상태의 최적 가치는 하나의 최적 행동으로 인해 평균적으로 받게 될 보상과 이 행동이 유발할 수 있는 가능한 모든 다음 상태의 최적 가치의 기대치를 합한 것과 같다는 것을 의미함.

$$ V^*(s)=\underset{a}{\max}\sum_{s'} T(s,a,s')\left[R(s,a,s')+\gamma\cdot V_k(s')\right] $$

• $T(s,a,s')$는 Agent가 행동 $a$를 선택했을 때 상태 $s$에서 $s'$로 전이될 확률임.
• $R(s,a,s')$는 Agent가 행동 $a$를 선택해 상태 $s$에서 $s'$로 전이했을 때 Agent가 받을 수 있는 Reward임.
• $\gamma$는 할인 계수(Discount factor)임.

위 식은 알고리즘이 가능한 모든 상태에 대한 최적의 상태 가치를 정확히 추정할 수 있도록 도와줌.