마르코프 결정 과정

3. 가치 함수

마르코프 결정 과정(MDP)의 핵심 목표는 장기적으로 가장 많은 보상을 얻을 수 있는 최적의 행동 규칙, 즉 정책($\backslash pi$)을 찾는 것이다. 정책은 각 상태 $s$에서 어떤 행동 $a$를 선택할지를 결정하는 함수 $\backslash pi(s)$ 또는 확률 분포 $\backslash pi(s,\; a)$로 정의된다.

어떤 정책이 좋은지를 평가하기 위해 가치 함수(value function)라는 개념을 사용한다. 가치 함수는 특정 상태에서 시작하여 특정 정책을 따랐을 때, 미래에 받을 것으로 기대되는 보상의 총합을 나타낸다. 일반적으로 미래의 보상은 현재의 보상보다 가치를 낮게 평가하기 위해 할인율($\backslash gamma$, $0\; \backslash le\; \backslash gamma\; \backslash le\; 1$)을 적용하여 합산한다. 할인율이 1에 가까울수록 미래 보상을 중요하게 생각하고, 0에 가까울수록 즉각적인 보상만을 중요하게 여긴다.

무한한 시간 동안 얻게 될 할인된 보상의 총합에 대한 기대치를 최대화하는 것이 일반적인 목표이며, 이는 다음과 같은 수식으로 표현될 수 있다.

:$E\backslash left[\backslash sum^\{\backslash infty\}\_\{t=0\}\; \{\backslash gamma^t\; R\_\{a\_t\}\; (s\_t,\; s\_\{t+1\})\}\backslash right]$

여기서 $a\_t\; =\; \backslash pi(s\_t)$는 정책 $\backslash pi$에 따라 상태 $s\_t$에서 선택된 행동이고, $R\_\{a\_t\}\; (s\_t,\; s\_\{t+1\})$는 상태 $s\_t$에서 행동 $a\_t$를 하여 상태 $s\_\{t+1\}$로 전이했을 때 받는 즉각적인 보상이다. 기대값 $E[\backslash cdot]$는 상태 전이 확률과 정책 $\backslash pi$에 따라 계산된다.

이처럼 특정 정책 $\backslash pi$를 따랐을 때 각 상태 $s$에서 기대되는 누적 할인 보상의 값을 상태 가치 함수(state-value function), $V^\backslash pi(s)$라고 부른다. 상태 가치 함수는 특정 정책의 효율성을 상태별로 평가하는 척도이다. MDP의 궁극적인 목표는 모든 상태에서 가장 높은 가치 함수 값을 갖는 최적 정책($\backslash pi^*$)을 찾는 것이며, 이 최적 정책에 해당하는 가치 함수를 최적 상태 가치 함수($V^*(s)$)라고 한다. 이러한 최적 가치 함수를 찾는 방법과 그 특성은 벨만 방정식 섹션에서 더 자세히 다룬다.

3. 1. 벨만 방정식

4. 알고리즘

마르코프 결정 과정(MDP)은 선형 계획법이나 동적 계획법을 사용하여 풀 수 있다. 이 섹션에서는 동적 계획법에 기반한 알고리즘들을 설명한다.

MDP 문제의 목표는 주어진 상태 전이 함수 $P$와 보상 함수 $R$을 바탕으로, 할인된 보상의 총계 기댓값을 최대화하는 정책 $\backslash pi$를 찾는 것이다.

이러한 최적 정책을 찾는 표준적인 알고리즘들은 상태별로 인덱싱된 두 개의 배열을 필요로 한다. 첫 번째 배열 $V$는 각 상태의 기댓값(가치)을 저장하며, 두 번째 배열 $\backslash pi$는 각 상태에서 취해야 할 최적의 행동(정책)을 저장한다. 알고리즘이 종료되면, $\backslash pi$는 최적 정책을 나타내고, $V(s)$는 상태 $s$에서 시작하여 최적 정책을 따랐을 때 기대되는 할인된 보상의 총계를 저장하게 된다.

알고리즘은 기본적으로 다음 두 단계를 재귀적으로 반복하여 최적해를 찾아나간다.

• 가치 갱신 (정책 평가): 현재 정책 $\backslash pi$를 따를 때 각 상태 $s$의 가치 $V(s)$를 계산한다.

• 정책 갱신 (정책 개선): 현재 가치 함수 $V$를 기반으로 더 나은 정책 $\backslash pi(s)$를 찾는다. 즉, 각 상태 $s$에서 기대 보상을 최대화하는 행동 $a$를 선택한다.

• 수정된 정책 반복법 (Modified Policy Iteration): 정책 평가 단계를 완전히 수렴시키지 않고 정해진 횟수만큼만 반복한 후 정책 개선 단계로 넘어가는 방식이다.^[10][11]
• 우선순위 스위핑 (Prioritized Sweeping): 모든 상태를 동일하게 갱신하는 대신, 어떤 방식으로든 중요한 상태(예: 최근 가치 변화가 컸던 상태, 시작 상태 근처 등)를 우선적으로 갱신하는 방식이다.

5. 확장 및 일반화

마르코프 결정 과정은 플레이어가 한 명뿐인 확률적 게임으로 볼 수 있다. 기본적인 마르코프 결정 과정 모델은 다양한 방식으로 확장 및 일반화될 수 있다.

'''부분 관측 마르코프 결정 과정 (POMDP)'''

기본적인 마르코프 결정 과정 해결책은 행동 $\backslash pi(s)$를 계산할 때 현재 상태 $s$를 정확히 알고 있다고 가정한다. 하지만 실제 상황에서는 상태를 완벽하게 관측하기 어렵거나 관측에 불확실성이 따르는 경우가 많다. 이렇게 상태 정보가 불완전한 문제를 다루기 위해 확장된 모델이 부분 관측 마르코프 결정 과정(Partially Observable Markov Decision Process, POMDP)이다.

'''제약 마르코프 결정 과정 (CMDP)'''

제약 마르코프 결정 과정(Constrained Markov Decision Process, CMDP)은 마르코프 결정 과정(MDP)을 확장한 모델이다. MDP와 CMDP 사이에는 다음과 같은 세 가지 주요 차이점이 있다.^[14]

CMDP 문제를 풀기 위해서는 주로 라그랑주 승수 방법과 같은 선형 계획법 기법이 사용된다. 라그랑주 승수 기반의 다양한 알고리즘이 개발되었으며, 예를 들어 자연 정책 기울기 쌍대 방법(natural policy gradient primal-dual method) 등이 있다.^[15] CMDP는 다양한 분야에 응용될 수 있으며, 최근에는 로봇 공학 분야의 동작 계획 문제 해결에 활용되고 있다.^[16]

'''연속 시간 마르코프 결정 과정 (CT-MDP)'''

이산 시간 마르코프 결정 과정(Discrete-time MDP)에서는 정해진 시간 간격마다 결정을 내리지만, 연속 시간 마르코프 결정 과정(Continuous-time Markov Decision Process, CT-MDP)에서는 결정 주체가 원하는 시점에 언제든지 결정을 내릴 수 있다. CT-MDP는 시스템의 동역학이 상미분 방정식(ODE)으로 표현되는 연속 시간 시스템의 의사 결정 과정을 모델링하는 데 더 적합하다. 이러한 시스템은 대기열 시스템, 전염병 확산 과정, 개체군 과정 등에서 찾아볼 수 있다.

CT-MDP에서도 목표는 기대 누적 보상을 최대화하는 최적의 정책을 찾는 것이다. 다만 시간 변수가 연속적이므로, 보상의 합계를 구하는 대신 적분을 사용한다.

:$\backslash max\; \backslash operatorname\{E\}\_\backslash pi\backslash left[\backslash left.\; \backslash int\_0^\backslash infty\backslash gamma^t\; r(s(t),\backslash pi(s(t)))\; \backslash ,\; dt\; \backslash ;\backslash right|\; s\_0\; \backslash right]$

여기서 는 할인 인자이다.

상태 공간과 행동 공간이 유한하다면, 선형 계획법을 사용하여 최적 정책을 찾을 수 있다. 특히, 시스템이 에르고딕 특성을 가진다고 가정하면(즉, 고정된 정책 하에서 시스템이 에르고딕 연속 시간 마르코프 연쇄가 됨), 결정은 상태가 변하는 순간에만 내리는 것으로 충분하다. 일부 조건 하에서,^[17] 최적 가치 함수 $V^*$가 상태 $i$와 무관한 상수 $g$(평균 보상)가 될 때, 다음과 같은 벨만 부등식이 성립한다.

:$g\backslash geq\; R(i,a)+\backslash sum\_\{j\backslash in\; S\}q(j\backslash mid\; i,a)h(j)\; \backslash quad\; \backslash forall\; i\; \backslash in\; S\; \backslash text\{\; and\; \}\; a\; \backslash in\; A(i)$

여기서 $h(j)$는 상대 가치 함수이며, $R(i,a)$는 상태 $i$에서 행동 $a$를 했을 때의 즉각적인 보상률, $q(j\backslash mid\; i,a)$는 상태 $i$에서 행동 $a$를 했을 때 상태 $j$로 전이하는 비율이다. 최적 평균 보상 $\backslash bar\; V^*$는 위 부등식을 만족하는 가장 작은 $g$ 값이다. 이를 찾기 위해 다음과 같은 선형 계획법 모델을 사용할 수 있다.

• 원 문제 선형 계획법 (Primal Linear Program, P-LP)

• 쌍대 문제 선형 계획법 (Dual Linear Program, D-LP)

6. 강화 학습

강화 학습은 기계 학습과 최적 제어의 학제 간 분야로, 주요 목표는 전이 확률과 보상이 알려지지 않은 MDP(마르코프 결정 과정)에 대한 대략적인 최적 정책을 찾는 것이다.^[18]

강화 학습은 정책 반복을 수행하는 데 필요한 전이 확률을 명시적으로 지정하지 않고도 마르코프 결정 과정을 해결할 수 있다. 이 설정에서 전이 확률과 보상은 경험, 즉 에이전트가 주어진 단계 수 동안 MDP와 상호 작용함으로써 학습되어야 한다. 이론적 및 실용적 수준 모두에서 샘플 효율성을 최대화하는 데 노력을 기울이고 있으며, 즉, 성능이 최적의 성능에 $\backslash varepsilon-$ 근접한 정책을 학습하는 데 필요한 샘플 수를 최소화하는 데 노력을 기울인다(프로세스의 확률적 특성으로 인해, 유한한 수의 샘플로 최적 정책을 학습하는 것은 일반적으로 불가능하다).

상태 $s$에서 행동 $a$를 취한 다음, 최적 정책(또는 현재 정책)에 따라 행동했을 때 얻게 될 총 기대 보상을 나타내는 '''행동 가치 함수'''(action-value function) $Q(s,a)$를 정의하는 것이 유용하다.

:$\backslash \; Q(s,a)\; =\; \backslash sum\_\{s\text{'}\}\; P\_a(s,s\text{'})\; (R\_a(s,s\text{'})\; +\; \backslash gamma\; V(s\text{'})).\backslash$

여기서 $P\_a(s,s\text{'})$는 상태 $s$에서 행동 $a$를 했을 때 상태 $s\text{'}$으로 전이될 확률, $R\_a(s,s\text{'})$는 이때 받는 즉각적인 보상, $\backslash gamma$는 할인 인자, $V(s\text{'})$는 상태 $s\text{'}$의 가치 함수이다.

이 $Q$ 함수 역시 처음에는 알 수 없지만, 에이전트는 환경과의 상호작용을 통해 얻는 경험 $(s,\; a,\; s\text{'},\; r)$ (상태 $s$에서 행동 $a$를 하여 상태 $s\text{'}$이 되고 보상 $r$을 받음)을 기반으로 $Q(s,a)$ 값을 점진적으로 학습하고 업데이트한다. 이러한 방식을 Q-러닝이라고 한다. Q-러닝은 다음과 같은 업데이트 규칙을 따른다.

$$$$

Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha [r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)]



여기서 $\backslash alpha$는 학습률(learning rate)이다. 최적의 행동 가치 함수 $Q^*(s,a)\; =\; \backslash max\_\backslash pi\; Q^\backslash pi(s,a)$를 학습하면, 각 상태 $s$에서 $Q^*(s,a)$를 최대화하는 행동 $a$를 선택함으로써 최적 정책 $\backslash pi^*$를 얻을 수 있다 ($V^*(s)\; =\; \backslash max\_\{a\}\; Q^*(s,a)$). 실제 학습 과정에서는 모든 상태-행동 쌍을 충분히 탐험(exploration)하기 위해 확률적인 요소를 가미하여 행동을 선택하기도 한다 (예: 엡실론-탐욕 정책).

기계 학습 이론에서 MDP 프로세스의 또 다른 응용 분야는 학습 자동 장치(Learning Automata)이다. 환경이 확률적일 때, 이는 강화 학습의 한 형태로 볼 수 있다. 나렌드라와 타타차르(1974)는 학습 자동 장치를 유한 상태 자동 장치로 설명하는 초기 연구를 수행했다.^[19] 강화 학습처럼 학습 자동 장치 알고리즘도 전이 확률이나 보상을 알지 못해도 문제를 해결할 수 있다. 하지만 Q-러닝과 달리 학습 자동 장치는 Q-값을 저장하는 대신 행동 선택 확률을 직접 업데이트하여 학습한다. 학습 자동 장치는 수렴성이 수학적으로 증명된 학습 방법이다.^[20]

학습 자동 장치 이론에서 '''확률적 자동 장치'''는 다음 요소로 구성된다.

• 가능한 입력 집합 ''x''
• 가능한 내부 상태 집합 Φ = { Φ₁, ..., Φ_''s'' }
• 가능한 출력 또는 행동 집합 α = { α₁, ..., α_''r'' } (단, ''r'' ≤ ''s'')
• 초기 상태 확률 벡터 ''p''(0) = ≪ ''p''₁(0), ..., ''p_s''(0) ≫
• 각 시간 단계 ''t''마다 현재 입력과 상태를 이용해 상태 확률 벡터 ''p''(''t'')를 ''p''(''t'' + 1)로 업데이트하는 계산 가능 함수 ''A''
• 각 시간 단계에서 상태 Φ로부터 출력 α를 생성하는 함수 ''G'': Φ → α

7. 기타 응용

마르코프 결정 과정(MDP)은 다양한 분야에서 응용될 수 있다. 대표적인 예로 기계 학습 이론에서 활용되는 학습 오토마톤(eng)이 있으며, 이는 환경이 확률적인 특성을 가질 때 사용되는 강화 학습의 한 형태이다. 또한 MDP는 범주론적 관점에서도 해석될 수 있다. 이러한 응용에 대한 자세한 내용은 이어지는 하위 섹션에서 다룬다.

7. 1. 학습 오토마타

• 가능한 입력의 집합 ''x''
• 가능한 내부 상태의 집합 Φ = { Φ₁, ..., Φ_''s'' }
• 가능한 출력 또는 행동의 집합 α = { α₁, ..., α_''r'' } (여기서 ''r'' ≤ ''s'')
• 초기 상태 확률 벡터 ''p''(0) = ≪ ''p''₁(0), ..., ''p_s''(0) ≫
• 각 시간 단계 ''t''마다 현재 입력과 현재 상태를 기반으로 상태 확률 벡터 ''p''(''t'')를 ''p''(''t'' + 1)로 업데이트하는 계산 가능 함수 ''A''
• 각 시간 단계에서 상태에 따라 출력을 생성하는 함수 ''G'': Φ → α

7. 2. 범주론적 해석

참조

_[1] 서적 Markov decision processes: discrete stochastic dynamic programming Wiley 1994
_[2] 서적 Papers presented at the February 26-28, 1957, western joint computer conference: Techniques for reliability on - IRE-AIEE-ACM '57 (Western) Association for Computing Machinery 1957-02-26
_[3] 간행물 Dynamic programming and stochastic control processes https://linkinghub.e[...] 1958-09-01
_[4] 서적 Reinforcement learning: an introduction The MIT Press 2018
_[5] 간행물 A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes 2002
_[6] 서적 Reinforcement Learning: Theory and Python Implementation China Machine Press
_[7] 간행물 Stochastic Games
_[8] 서적 Handbook of Markov decision processes: methods and applications Springer
_[9] 문서 Comments on the Origin and Application of Markov Decision Processes https://pubsonline.i[...] Howard 2002
_[10] 간행물 Modified Policy Iteration Algorithms for Discounted Markov Decision Problems
_[11] 간행물 A set of successive approximation methods for discounted Markovian decision problems
_[12] 간행물 The Complexity of Markov Decision Processes https://pubsonline.i[...] 2023-11-02
_[13] 간행물 A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes 2002-11
_[14] 서적 Constrained Markov decision processes CRC Press
_[15] 학술회의 Natural policy gradient primal-dual method for constrained Markov decision processes
_[16] 학술회의 Risk-aware path planning using hierarchical constrained Markov Decision Processes https://www.research[...] 2014-08-18
_[17] 서적 Continuous-Time Markov Decision Processes https://link.springe[...] 2009
_[18] 간행물 Multi-agent reinforcement learning: a critical survey http://jmvidal.cse.s[...] 2018-12-12
_[19] 간행물 Learning Automata – A Survey
_[20] 서적 Learning automata: An introduction https://archive.org/[...] Prentice Hall
_[21] 서적 DYNAMIC PROGRAMMING AND MARKOV PROCESSES https://trid.trb.org[...] Massachusetts Institute of Technology Press 1960
_[22] 간행물 A Markovian Decision Process http://www.jstor.org[...] Indiana University Mathematics Department 1957
_[23] 간행물 Stochastic Games http://www.pnas.org/[...] 1953-10-01
_[24] 서적 Finite State and Action MDPS https://link.springe[...] Springer, Boston, MA 2003