Week7. MDP-3

 

 

 Week5부터는 Markov Decision Process(MDP)를 살펴보고 있다. Week5에서는 MDP의 구성요소(상태 공간, 시간 공간, 행동 공간, 상태전이확률, 보상)를 살펴보았다. Week6에서는 일반적인 상황에서 상태 가치함수와 행동 가치함수 그리고 이들의 벨만 기대 방정식과 함께 벨만 최적 방정식까지 살펴보았다. 특히, 시간 공간이 유한한 finite-horizion MDP 모델에서는 벨만 최적 방정식을 풀기 위해 역진 귀납법을 사용했다.

 특히 중요한 부분은 강화학습의 수학적 근간이 되는 Infinite-horizon MDP 모델이다. Infinite-horizon MDP 모델에서는 정상성 가정(stationary assumption)이 중요한데, 보상과 상태전이확률이 시간에 의존하지 않는다는 개념이다. 이러한 정상성 가정을 만족하는 Infinite-horizon MDP 모델의 경우, 정상 최적 정책(stationary optimal policy)이 존재한다는 사실이 알려져 있으며, 모든 시점에 대해 특정 상태 $s$에 대해 어떤 행동 $a$를 해야할 지 의사결정 규칙이 동일한 정책을 의미한다. 이때 우리의 목적은 가치함수 값을 바탕으로 최적의 정상정책을 찾아내는 것이다. 이를 위해 정상성 가정을 만족하는 Infinite-horizon MDP 모델 역시 벨만 최적 방정식을 가지고 있는데, 다음과 같다.

$$v^*(s) = \underset{a}{\max}{[r(a,s) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)\cdot v^*(s^\prime)]}}$$

이때 좌변의 가치함수 $v^*$와 우변의 가치함수 $v^*$는 동일한 가치함수다. 이러한 상황에서 모든 상황 $s$에 대한 $v^*$를 어떻게 구할 수 있을까? 즉, 이번주는 Infinite-horizon MDP 모델에서는 벨만 최적 방정식을 어떻게 풀것인지에 대해 살펴보자.

1. Value Iteration

 가치 반복 알고리즘(value iteration algorithm)은 좌변과 우변의 가치함수 $v^*$가 동일하니, 이 값에 대해 반복적으로 풀 수 있다는 아이디어에서 출발하는 간단한 방법이다. 다시 한 번 정상성 가정을 만족하는 Infinite-horizon MDP의 벨만 최적 방정식을 살펴보자.

$$v^*(s) = \underset{a}{\max}{[r(a,s) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)\cdot v^*(s^\prime)]}}$$

가치 반복 알고리즘은 먼저 초기화를 진행하고 식을 반복적으로 풀어나간다. 이때 모든 상태에 대한 상태 가치함수 값을 0으로 초기화했지만, 임의의 값으로 초기화하더라도 항상 수렴한다는 사실이 알려져있다.

1. 초기화
   • $v_0(s)=0,~ \forall s$
   • k = 1
2. 문제 풀이(반복)
   • $v_{k}^*(s) = \underset{a}{\max}{[r(a,s) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)\cdot v_{k-1}^*(s^\prime)]}}$
   • 모든 가능한 상태 $s$에 대해 각각 행동 $a$에 대한 우변 풀이 후 최대값을 해당 $s$에 대한 $v_k(s)$로 갱신
   • 만약 $||v_k(s) - v_{k-1}|| < \epsilon,~\forall s$라면 종료. 아니면 $k = k+1$

 

예시

 

 상태는 $s \in \{Cool, Warm, Overheated\}$, 각 상태에 대한 행동은 $a \in \{Slow, Fast\}$로 주어진 아래와 같은 예시를 생각해보자. 이때 상태 간 전이는 각 상태에 따라 어떤 행동을 취하는지에 따라 MDP에 의해 프로세스가 진행되며, 시점 별로 상태전이확률이 달라지지 않는 정상성을 만족한다고 가정하자. 이러한 상황에서 가치 반복 알고리즘을 통해 벨만 최적 방정식을 풀고, 정상 최적 정책을 구해보자.

 

 

1.초기화

$v_0(C)=v_0(W)=v_0(O)=0$

 

2. 문제 풀이 ($\epsilon = 0.001$)

• 2.1

$v_1(C) = \max{\{r(Cool,Slow), r(Cool, Fast)\}} = \max{\{1, 2\}} = 2$

$v_1(W) = \max{\{r(Warm,Slow), r(Warm, Fast)\}} = \max{\{1, -10\}} = 1$

$v_1(O) = 0$

 

• 2.2

$v_2(C) = \max{\{r(Cool,Slow)+0.8\cdot v_1(C), r(Cool, Fast) + 0.8(0.5 v_1(C)+0.5 v_1(W)\}} = \max{\{2.6, 2.2\}} = 2.6$

$v_2(W) = \max{\{r(Warm,Slow) + 0.8 \cdot (0.5 v_1(C)+0.5 v_1(W)), r(Warm, Fast)+0.8\cdot v_1(Overheated)\}} = \max{\{2.2, -10\}} = 2.2$

$v_2(O) = 0$

 

    - $|v_k - v_{k-1}| < 0.001$까지 반복

 

 

위 그래프에서 x축은 반복 횟수, y축은 가치함수의 값이다. 상태가 Cool일때 $v(C)$는 8로 수렴, 상태가 Warm일때 $v(W)$는 7로 수렴하고 있다. Cool상태에서 최적 정책을 통해 얻을 수 있는 누적보상합 기대치의 최대값이 8이고, Warm 상태에서 최적 정책을 통해 얻을 수 있는 누적보상합 기대치의 최대값이 7이라고 이해할 수 있다. 

$$v^*(Cool)=8. ~ v^*(Warm)=7$$

 이 결과를 통해 최적 정책을 도출해낼 수 있다. 즉, 최적 정책을 나타내는 아래 식에 위 값을 대입해 최대값을 만드는 행동 $a$를 선택하면 된다.

$$\pi^*(s) = \arg\max_a{[r(s,a) + \gamma \sum_{s^\prime}{P(s^\prime|s,a)v^*(s^\prime)}]}$$

 

$$\pi^*(C) = \arg\max{\{ 1 + 0.8\cdot v^*(C), 2+0.8\cdot (0.5 v^*(C) + 0.5 v^*(Warm)) \}} = Fast$$

$$\pi^*(W) = \arg\max{\{1+0.8\cdot (0.5 v^*(C) + 0.5 v^*(Warm)), -10 +0.8 v^*(O) \}} = Slow$$

 

즉, 가치 반복 알고리즘을 활용해 구한 최적 정책은 Cool 상태에서는 Fast, Warm 상태에서는 Slow를 선택하는 것이다.

 

 

2. Policy Iteration

 가치 반복 알고리즘이 모든 상태에 대한 가치함수 값에 대해 반복을 진행했다면, 정책 반복 알고리즘(policy iteration algorithm)은 정책 $\pi$에 대한 반복 갱신 방법이다. 가치 반복 알고리즘에서는 가치 함수 값을 계산해야하기 때문에 가치함수 값에 대한 초기화를 진행했듯이, 정책 반복 알고리즘에서는 임의의 정책 $\pi$를 초기화하고, 모든 상태에 대한 정책의 변화가 없을 때까지 갱신을 반복한다. 이때 반복 과정은 정책 평가 단계와 정책 개선 단계 두 가지로 이루어진다. 참고로, 정책 업데이트 시 가치 함수 값이 항상 크거나 같다는 것($v^{\pi^{\prime}} \ge v^\pi$)이 알려져있다.

 

1.초기화 단계

• 임의의 정책 $\pi$를 선택

 

2. 반복 단계

• 2.1 정책 평가 (policy evaluation): 정책이 주어졌을 때, 모든 상태에 대한 가치함수 값 계산

$$v^\pi(s) = r(a,\delta(s)) + \gamma \sum_{s^\prime}{P(s^\prime|s,\delta(a)) \cdot v^{\pi}(s^\prime)}$$

=> $V^\pi = (I-\gamma P_\pi)^{-1} R_\pi$

• 2.2 정책 개선 (policy improvement)

- 모든 $s$에 대해, $\pi^\prime(s) = \arg\max_a{\{ r(s,a) + \gamma \sum_{s^\prime}{P(s^\prime|s,a) v^{\pi}(s^\prime)}\}}$ 계산. 이때, 정책 평가 단계에서 계산한 $v^\pi$값을 우변에 사용

 

- 정책 갱신: $\pi$ ← $\pi^\prime$

 

• 2.3 모든 상태에 대해 정책의 변화가 없을 때까지 반복

 

예시

 

 상태는 $s \in \{Cool, Warm, Overheated\}$, 각 상태에 대한 행동은 $a \in \{Slow, Fast\}$로 주어진 위의 예시를 다시 한 번 살펴보자.

 

 

1.초기화 단계: 임의의 정책

• $\pi = (S, S, -)$ where $(a_C, a_W, a_O)$

 

2. 반복 단계

• 2.1-1 정책 평가: 모든 상태에 대해 가치함수 값 계산

$$v^\pi(C) = r(C,S) + 0.8 \sum_{s^\prime}{P(s^\prime|C,S)v^\pi(s^\prime)} \\ = 1 + 0.8v^\pi(C)$$

$$v^\pi(W) = r(W,S) + 0.8 \sum_{s^\prime}{P(s^\prime|C,S)v^\pi(s^\prime)} \\ = 1 + 0.8(0.5v^\pi(C) + 0.5v^\pi(W))$$

$$v^\pi(O) = r(O,S) + 0.8 \sum_{s^\prime}{P(s^\prime|C,S)v^\pi(s^\prime)} \\ = 0 + v^\pi(O)$$

 

-> $v^\pi(C)=5, ~~ v^\pi(W)=5, ~~v^\pi(O)=0$

 

• 2.2-1 정책 개선

$\pi^\prime(C) = \arg\max_a{[r(C,a) +\gamma \sum_{s^\prime}{P(s^\prime|C,a) v^\pi(s^\prime)}]}$

        $=\arg\max_a{[1+0.8v^\pi(C), 2+0.8(0.5v^\pi(C) + 0.5v^\pi(W))]}$

        $=\arg\max{[5,6]} = Fast$

 

$\pi^\prime(W) = \arg\max_a{[r(W,a) +\gamma \sum_{s^\prime}{P(s^\prime|W,a) v^\pi(s^\prime)}]}$

        $=\arg\max_a{[1+0.8(0.5v^\pi(C) + 0.5v^\pi(W)), -10 +0.8v^\pi(s^\prime)]}$

        $=\arg\max{[5,-10]} = Slow$

 

$\pi^\prime(O)=-$

 

→ $\pi = (F, S, -)$

 

(반복)

 

• 2.1-2 정책 평가: 모든 상태에 대해 가치함수 값 계산

$$v^\pi(C) = r(C,F) + 0.8 \sum_{s^\prime}{P(s^\prime|C,F)v^\pi(s^\prime)} \\ = 2 + 0.8(0.5v^\pi(C) + 0.5v^\pi(W))$$

$$v^\pi(W) = r(W,S) + 0.8 \sum_{s^\prime}{P(s^\prime|C,S)v^\pi(s^\prime)} \\ = 1 + 0.8(0.5v^\pi(C) + 0.5v^\pi(W))$$

$$v^\pi(O) = r(O,S) + 0.8 \sum_{s^\prime}{P(s^\prime|C,S)v^\pi(s^\prime)} \\ = 0 + v^\pi(O)$$

 

-> $v^\pi(C)=8, ~~ v^\pi(W)=7, ~~v^\pi(O)=0$

 

• 2.2-2 정책 개선

$\pi^\prime(C) = \arg\max_a{[r(C,a) +\gamma \sum_{s^\prime}{P(s^\prime|C,a) v^\pi(s^\prime)}]}$

        $=\arg\max_a{[1+0.8v^\pi(C), 2+0.8(0.5v^\pi(C) + 0.5v^\pi(W))]}$

        $=\arg\max{[7.4,8]} = Fast$

 

$\pi^\prime(W) = \arg\max_a{[r(W,a) +\gamma \sum_{s^\prime}{P(s^\prime|W,a) v^\pi(s^\prime)}]}$

        $=\arg\max_a{[1+0.8(0.5v^\pi(C) + 0.5v^\pi(W)), -10 +0.8v^\pi(s^\prime)]}$

        $=\arg\max{[7,-10]} = Slow$

 

$\pi^\prime(O)=-$

 

→$\pi = (F, S, -)$

 

$\therefore \pi = \pi^\prime$  → 반복 중지

 

 

 그런데, 사실 이 예시의 경우 상태가 총 3개, 행동도 2개뿐으로 모든 정책을 나열해볼 수 있다. 즉, 가능한 정책은 총 4개만 가능한 경우이므로, 아래와 같이 정책과 그에 따른 상태전이행렬과 보상행렬을 정의하고 정책 평가를 통해 가장 최상의 정책을 선택하면 된다.

 

가능한 모든 정책

정책 평가