ch 04. MDP를 알 때의 플래닝

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

 

간단한 그리드 월드 MDP 상황을 예시로

정책 \( \pi \)가 주어졌을 때 각 상태의 밸류를 평가하는 prediction문제와

최적의 정책 함수를 찾는 control 문제를 푸는 방법에 대해 설명한다.

 

2가지 전제조건이 있다.

1. 작은문제 ( 상태집합(S)과 액션집합(A)의 크기가 작은 문제 )

2. MDP에 대해 알고 있다. (즉, 보상과 전이확률을 알고 있다)

 

이 전제조건이 만족하기에 테이블 기반 방법론을 활용하여 문제를 풀어나간다.

(테이블 기반 방법론 이란 - 모든 상태 s 혹은 상태와 액션의 페어(s, a)에 대한 테이블을 만들어서 값을 기록해 놓고 그 값을 조금씩 업데이트하는 방식)

 

1. 밸류 평가하기 - 반복적 정책 평가

풀어야 할 문제와 상황은 다음과 같이 정리할 수 있다.

4방향 랜덤이라는 정책함수 \( \pi \)가 주어졌고 이때 각 상태 s에 대한 가치함수 \( \nu(s) \)를 구하는 전형적인 prediction 문제이다.

이 문제는 테이블 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트해 나가는 반복적 정책 평가 방법론을 사용하여 풀게 된다.

 

보상은 모든 상태에서 -1 이다.

전이확률 \( P_{ss^{'}}^a \) 은 100%이다( 예를 들면, 좌측 이동 액션을 선택한 경우 다음 상태는 100% 좌측상태로 이동하기 때문)

\( \gamma \) 는 편의상 1 로 정한다

 

(1) 테이블 초기화 과정

테이블 빈칸은 상태별 밸류 \( \nu(s) \)를 기록해야 하기 때문에 상태 개수만큼 필요하다.

임의의 값 0으로 초기화한다. 추후 반복적 정책평가를 진행하면서 각 상태의 밸류들은 특정값으로 수렴해 갈 것이다.

 

(2) 상태의 값을 업데이트하는 과정

\( s_5 \) 상태의 밸류를 좀 더 정확하게 업데이트 하려면 , 정책이 주어져 있고 MDP를 알고 있으므로

아래의 벨만 기대 방정식 2단계 공식을 이용해서 상태밸류를 계산할 수 있다.

이 수식은 현재 상태 s의 가치를 다음에 도달하게 되는 상태 \( s^{'} \)의 가치로 표현한 식이다.

이 식을 토대로 위 그림의 파란색 셀( \( s_5 \) )의 밸류를 노란색 셀의 밸류를 이용해 업데이트 한다.

 

위의 벨만 기대 방정식을 그리드 월드에 맞게 풀어 적으면 아래와 같다.

$$ \nu_{\pi}(s_5) = \pi( 좌|s_5) ( r_{s_5}^좌 + \gamma ( P_{s_{5}s_{4}}^{좌} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{좌} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{좌} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{좌} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 우|s_5) ( r_{s_5}^우 + \gamma ( P_{s_{5}s_{4}}^{우} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{우} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{우} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 상|s_5) ( r_{s_5}^상 + \gamma ( P_{s_{5}s_{4}}^{상} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{상} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{상} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{상} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 하|s_5) ( r_{s_5}^하 + \gamma ( P_{s_{5}s_{4}}^{하} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{하} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{하} \nu_{\pi}(s_9) ) ) $$

 

이 식에 실제 값을 대입해보자

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times ( 1 \times 0 + 0 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 1 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 0 \times 0 + 1 \times 0 ) ) $$

 

정리하면,

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

 

결과값은, 

$$ \nu_{\pi}(s_5) = -1 $$

 

따라서 테이블의 파란색 셀, 즉 상태 \( s_5 \)의 밸류를 -1로 업데이트한다.

여기서 노란색 셀의 밸류들이 초기에 임의의 값으로 지정했기 때문에 그 값을 이용해 계산된 파란색 셀의 값도 정확한 값이 아니다. 하지만 실제 값인 보상값이 포함되어 계산되었기 때문에 초기 임의의 값보다는 실제값에 조금 가까워졌다고 볼 수 있다.

이런 과정을 상태를 이동해가며 계속 반복적으로 진행하다 보면 점차 상태들의 밸류값들이 실제값에 가까워진다.

 

(3) 모든 상태에 대해 (2)의 과정 적용

 

(2)의 과정을 마지막 상태를 제외한 15개 상태에 대해서 진행하여 위 그림의 오른쪽과 같은 결과를 얻는다.

가장자리 상태의 업데이트 계산은 바깥을 향하는 액션은 제외시킨다

예를 들면, \( s_0 \) 상태에서 보면 좌, 상 이동은 선택액션에서 제외되어야 한다.

(2)과정의 수식을 \( s_0 \) 상태에 적용해서 나열하면 다음과 같다.

$$ \nu_{\pi}(s_0) = \pi( 우|s_0) ( r_{s_0}^우 + \gamma ( P_{s_{0}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{우} \nu_{\pi}(s_4) ) ) $$

$$ \quad\qquad + \pi( 하|s_0) ( r_{s_0}^하 + \gamma ( P_{s_{0}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{하} \nu_{\pi}(s_4) ) ) $$

 

정리하면,

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times (1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times (0 \times 0 + 1 \times 0 ) ) $$

 

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times 0 ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times 0 ) $$

 

$$ \nu_{\pi}(s_0) = 0.5 \times -1 + 0.5 \times -1 $$

$$ \nu_{\pi}(s_0) = -1 $$

 

결과값은, 

$$ \nu_{\pi}(s_0) = -1 $$

정책이 정해져 있는 상태에서 (여기서는 4방향 랜덤한 액션 선택 정책) 마지막 상태를 제외한 모든 상태에 대해서 반복적인 정책평가를 진행하다보면 각 상태별로 특정값에 수렴해간다.

예를 들어, 상태 \( s_0 \)의 수렴값이 -59.4 가 나왔다.

즉, 이 값은 상태 \( s_0 \)의 가치밸류가 -59.4 라는 의미이고 현재 상황에서 의미는 4방향으로 무작위로 움직이다 보면 평균적으로 대략 60번은 움직여야 종료 상태에 도달하게 된다는 뜻이다.

 

2. 최고의 정책 찾기 - 정책 이터레이션

최적의 정책을 찾는 방법은 정책 이터레이션과 밸류 이터레이션 방법이 있다.

이 중 정책 이터레이션은 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론이다.

 

정책 이터레이션은 2단계로 구성된다.

1단계 ) 정책평가단계: 임의의 정책으로 \( \pi \)를 고정해놓고 반복적 정책 평가 방법을 사용하여 각 상태의 밸류를 계산한다.

2단계 ) 정책개선단계: 1단계에서 계산해 놓은 상태별 밸류값 \( \nu(s) \)을 이용하여 그리디 정책을 생성한다. 

여기서 그리디 정책이란 현재상태에서 바로 앞의 이익을 최대화하는 선택을 하도록 하는 정책을 의미하며 현재 상황에 적용하면 현재 위치한 상태에서 4방향의 다음 상태를 선택할 때 상태밸류 \( \nu(s) \)값이 최대인 상태로 이동을 선택하도록 하는 정책을 의미한다.

 

1단계=>2단계=>1단계=>2단계... 반복적으로 진행하다보면 정책평가 결과인 가치밸류가 변하지 않고 그리디정책도 변화하지 않는 상태에 도달하게 된다.

이때가 최적의 정책과 최적 가치에 도달한 것으로 판단하면 된다.

 

그리디 정책 선택이 정책 개선을 의미하는 이유는,

\( \pi_{greedy} \) : 현재 상태에서 바로 다음 상태 이동만 그리디 정책으로 움직이고 그 후 상태 이동은 기존 정책으로 움직이는 정책

\( \pi \) : 기존 정책

위 2가지 정책 중 상태밸류가 높은 쪽은 당연히 \( \pi_{greedy} \) 정책이다. 이 논리를 t 시점뿐만이 아니라 t+1, t+2, .. 모든 시점에 대해 적용하면 결국 모든 상태에서 그리디 정책을 선택하는 것이 정책개선 효과가 있다고 판단할 수 있다.

 

- 정책평가 방법 간소화 하기

위에서 언급한 정책 이터레이션 방법은 1단계 정책평가 과정에서 정책을 평가하기 위해 반복적 정책평가방법을 사용하며 그 부분에서 상당한 시간을 소요하게 된다.

우리의 목적은 최적정책을 찾기 위해 정책을 평가하는 것이므로 정확한 값을 도출해내지 않더라도 큰 문제는 없다.

상태밸류값이 변하지 않을 때까지 반복평가하는 것이 아니라 예를 들면, 5번만 반복평가를 해도 그리드 정책을 선택에 문제가 없다는 것이다.

이런 논리를 적용하여 정책 이터레이션에서 1단계 정책평가는 1번만 계산하는 것으로 한다.

 

3. 최고의 정책찾기 - 밸류 이터레이션

 

밸류 이터레이션도 테이블 기반 방법론을 사용한다.

각 셀은 최적 정책 \( \pi^{*} \)의 밸류인 \( \nu_{*} (s) \) 를 의미하게 된다.

초기에는 셀의 값들을 0으로 초기화한다.

 

MDP를 알고 있으므로 ( 보상과 전이확률값을 알고 있음을 의미 )

벨만 최적 방정식 2단계 공식을 사용해 각 셀의 최적밸류를 구한다.

예를 들어 \( s_5 \) 상태의 최적 밸류를 계산하면 아래와 같다.

같은 방식을 모든 셀에 적용한다.

각 셀의 밸류가 특정값에 수렴할 때까지 위의 방법을 반복적으로 수행한다.

최적 정책을 찾는 것이 목표인데 최적 밸류를 먼저 계산했다. 

이유는 MDP를 모두 알고 있는 상황에서는 최적 밸류를 계산하는 것이 최적 정책을 찾는 빠른 방법이다.

최적 밸류를 모두 계산해놓으면 임의의 상태에서 다음 상태 이동은 밸류가 가장 큰 셀로 이동하는 것이 최적 정책이다.

즉, 최적 밸류에 대한 그리디 정책이다.!!

 

의견 => 정책 이터레이션에서 계산 간소화를 위해 주어진 정책에서 상태밸류 계산시 반복적으로 계산하지 않고 1번만 계산하고 그리디 정책을 선택했다. 이 논리를 밸류 이터레이션에도 적용할 수 있을까?

즉, 최적 정책을 찾기 위해 최적밸류가 수렴할 때까지 반복적 계산이 필요할까 ? 하는 질문이다.

밸류 계산은 1번만 한 상태에서 그리디 정책을 적용하면 어떨까?

질문을 남겨두고 다음챕터로 넘어간다.