[바닥부터 배우는 강화학습] - Chapter 4. MDP를 알 때의 플래닝

방선생·2025년 8월 3일

바닥부터 배우는 강화학습

목록 보기

4/5

벨만 방정식 학습으로 간단한 MDP를 풀 수 있습니다. 벨만 방정식을 반복적으로 적용하는 방법론을 통해 아주 간단한 MDP를 직접 풀어봅니다.

작은문제 : MDP에서 상태 집합 S나 액션의 집합 A의 크기가 작은 경우
MDP를 알 때 : 보상 함수와 전이 확률 행렬을 알고있는 것
플래닝(planning) : MDP에 대한 모든 정보를 알 때, 이를 이용하여 정책을 개선해 나가는 과정
- 즉, 미래가 어떤 과정을 거쳐 정해지는지 알고있는 상황에서 시뮬레이션 하며 계획을 세우는 것
테이블 기반 방법론(tabular method) : 모든 상태 $s$ 혹은 상태와 액션의 페어 $(s, a)$ 에 대한 테이블을 만들어서 값을 기록해 놓고, 그 값을 조금씩 업데이트하는 방식
- 상태나 액션의 개수가 많지 않아 그에 해당하는 테이블을 만들 수 있어서 가능한 방법론

4방향 랜덤이라는 정책 함수 $\pi$ 가 주어졌고 이때 각 상태 s에 대한 가치 함수 $v(s)$ 를 구하는 전형적인 prediction 문제
반복적 정책 평가(iterative policy evaluation) : 테이블의 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트해 나가는 방법론
- MDP에 대한 모든 정보를 알 때 사용

테이블에 상태별 밸류 $v(s)$ 를 기록하기 때문에 테이블의 빈칸은 MDP 안의 상태 s의 개수만큼 필요함 (그림 4-2기준 16개)
- 어떤 값으로 초기화해도 상관없지만, 정답과 멀수록 업데이트 횟수가 더 많이 필요함 (정답을 모르는 경우 적당한 값인 0으로 초기화)

$s_5$ 가 업데이트를 진행하는 상황
- MDP를 알기 때문에 노란색 상태가 후보가 됨
현재상태와 다음 상태의 밸류 사이 관계식 : 벨만 기대 방정식
- $v_{\pi}(s) = \sum_{a \in A} \pi(a|s) \left( r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \right)$
- 그림 4-3에서의 계산식 : $v_{\pi}(s_5) = 0.25*(-1 + 0.0) + 0.25*(-1 + 0.0) + 0.25*(-1 + 0.0) + 0.25*(-1 + 0.0) = -1.0$

현재 테이블에 담겨 있는 값은 마음대로 정한 무의미한 값이지만, 이를 다음 상태의 값과 보상이라는 실제 환경이 주는 정확한 값을 섞어서 업데이트 하기 때문에 조금씩 정확한 값에 다가가게됨

MDP를 알때 최적 정책을 찾는 2가지 방법 : 정책 이터레이션, 밸류 이터레이션
정책 이터레이션 : 기본적으로 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론
$s_5$ 기준으로 밸류가 더 큰 상태로 이동하는 것이 좋은 액션임 (즉, 동쪽과 남쪽)
- $\pi'(a_{\text{동}}|s_5) = 1.0 \text{ or } \pi'(a_{\text{남}}|s_5) = 1.0$
  - 여기서 $\pi'$ 는 원래 정책 $\pi$ 보다 나은 정책이며, 이를 그리디 정책(greedy policy)라고 함
주어진 랜덤 정책 $\pi$ 에 대해 밸류를 평가하고, 그에 대해 greedy한 정책을 표시하면, 그 정책이 곧 최적 정책과 일치함

정책 이터레이션은 총 2단계로 이루어져 있음
- 처음에는 정책 $\pi$ 를 임의의 정책으로 초기화해놓고 시작함
- 정책 평가(policy evaluation) : $\pi$ 를 따랐을 때 각 상태의 가치를 평가하는 일
  - 반복적 정책 평가를 사용하여 테이블에 각 상태의 밸류를 채워넣음
- 정책 개선(policy improvement) : 앞서 정책 평가 단계에서 구한 $v(s)$ 를 이용해 $v(s)$ 에 대한 그리디 정책을 만들어 새로운 정책 $\pi'$ 를 생성함
  - $\pi'$ 를 생성하면 $\pi'$ 이 $\pi$ 보다 좋은 정책이기 때문에, 즉 $\pi' \geq \pi$ 가 성립하기 때문에 정책의 개선이 발생함
- 이렇게 $\pi'$ 이 생성되면 $\pi'$ 에 대해 다시 정책 평가를 진행함. 즉, 정책의 평가와 개선을 반복
어느 순간 정책도 변하지 않고, 그에 따른 가치도 변하지 않는 단계에 도달하게 되어 수렴하는 곳이 바로 최적 정책(optimal policy)과 최적 가치(optimal value)가 됨

그림 4-10에 경우 k=6까지만 진행하여도 그에 따른 그리디 정책이 이미 최적 정책에 도달함

즉 가치 함수를 끝까지 학습하지 않아도 됨(early stopping)

정책 이터레이션은 단계마다 서로 다른 정책의 가치를 평가함. 계선 단계를 지날때 마다 새로운 정책이 나오고, 평가 단계에선 방금 만들어진 새로운 정책의 밸류를 평가했기 때문
- 하지만, 밸류 이터레이션(value iteration)은 오로지 최적 정책이 만들어내는 최적 밸류 하나만 확인함
- 최적 밸류(optimal value) : 존재하는 모든 정책들 중 가장 보상을 많이 받을 수 있는 정책(최적 정책)을 따랐을 때 얻는 밸류

아까와 같이 $s_5$ 의 값을 업데이트하지만, 주어진 정책이 따로 없음
반복적 정책 평가에서는 $\pi$ 가 주어져 있기 때문에 벨만 기대 방정식을 사용함. 하지만, 지금은 테이블에서 각 칸은 최적 밸류를 나타내고, 최적 밸류 사이의 관계를 알고 싶은 것이므로 벨만 최적 방정식을 사용함
- $v_{*}(s) = \max_{a} \left[ r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') \right]$
- 그리드 월드는 환경에 확률적인 성질이 없어서 전이 확률은 항상 1임
  - $v_{*}(s_5) = max(-1+1.0*0, -1+1.0*0, -1+1.0*0, -1+1.0*0) = -1.0$