2 minute read

벨만 방정식을 이용하면 연립 방정식을 얻을 수 있고, 그 연립 방정식을 풀 수 있다면 가치 함수를 구할 수 있다.

상태 전이 확률, 보상 함수, 정책에 대한 정보가 있다면 벨만 방정식을 이용해 연립 방정식을 구할 수 있다.

연립 방정식을 푸는 프로그램을 사용하여 가치 함수를 구할 수 있다.

동적 프로그래밍은 상태와 행동의 수가 많아져도 가치 함수를 구할 수 있다.

1. 동적 프로그래밍과 정책 평가

강화학습에서는 두 가지 문제를 해결해야 한다.

  1. 정책 평가 : 정책 $\pi$가 주어졌을 때 그 정책의 상태 가치 함수 $v_\pi(s)$ 또는 행동 가치 함수 $q_\pi(s, a)$를 구하는 문제
  2. 정책 제어 : 정책을 조정하여 최적 정책을 만들어내는 것

강화학습의 궁극적인 목표는 정책 제어이다. 하지만 첫 목표로 정책 평가부터 정복하는 경우가 많다. 대부분 문제에서 최적 정책을 직접 구하기는 매우 어렵기 때문이다.

이번 절에서는 동적 프로그래밍 알고리즘을 이용한 정책 평가 방법을 살펴본다.

1.1 동적 프로그래밍 기초

가치 함수의 정의

\[v_\pi(s) = \mathbb{E}_\pi \left[ R_t + \gamma R_{t+1} + \gamma^2 R_{t + 2} + \dots \vert S_t = s \right]\]

무한대가 포함되어 있는 식은 일반적으로 계산할 수 없다. 하지만 벨만 방정식을 이용하여 무한대에서 탈출할 수 있다.

\[v_\pi(s) = \sum_{a, s'} \pi (a \vert s) p(s' \vert s, a) \left[ r(s, a, s') + \gamma v_\pi (s') \right]\]

벨만 방정식은 ‘현재 상태 s의 가치 함수 $v_\pi(s)$와 다음 상태 s의 가치 함수 $v_\pi(s’)$의 관계를 나타낸다.

DP를 사용한 방법은 벨만 방정식에서 파생된다. 벨만 방정식을 갱신식으로 변경하는 것이다.

\[V_{k+1}(s) = \sum_{a, s'} \pi (a \vert s) p(s' \vert s, a) \left[ r(s, a, s') + \gamma V_k(s') \right]\]
  • $V_{k+1} (s)$ : k + 1 번째로 갱신된 가치 함수
  • $V_k (s)$ : k 번째로 갱신된 가치 함수

이는 추정치이므로 실제 가치 함수 $v(s)$와 다르기 때문에 대문자로 표기한다.

위 식의 특징

  1. 다음 상태의 가치 함수 $V_k(s’)$를 이용하여 지금 상태의 가치 함수 $V_{k+1}(s)$를 갱신한다.
  2. 추정치 $V_k(s’)$를 사용하여 또 다른 추정치 $V_{k+1}(s)$를 개선한다.

Bootstrapping : 추정치를 사용하여 추정치를 개선하는 과정

반복적 정책 평가

  1. $V_0(s)$의 초깃값을 설정한다. 예를 들어 모든 상태에서 $V_0(s)$로 초기화한다.
  2. 위 식을 이용하여 $V_0(s)$에서 $V_1(s)$로 갱신한다.
  3. $V_1(s)$에서 $V_2(s)$로 갱신한다.
  4. 최종 목표 $V_\pi(s)$에 가까워질 때까지 이를 반복한다.

위 식에 따라 갱신을 반복하면 $V_\pi(s)$에 수렴한다는 사실은 증명되어있다.

1.2 반복적 정책 평가 - 첫 번째 구현

‘두 칸짜리 그리드 월드’에 반복적 정책 평가 알고리즘의 흐름을 살펴보겠다.

  • 이 문제에서 에이전트는 무작위 정책 $\pi$에 따라 행동한다.
  • 상태 전이는 결정적이다. 즉 어떤 상태 s에서 행동 a를 수행하면 다음 상태 s’는 한 가지로 귀결된다. 수식에서는 다음 상태 s’가 함수 $f(s, a)$에 의해 고유하게 결정된다고 가정한다.

$s’ = f(s, a)$ 일 때,

\[\begin{align*} V_{k+1}(s) &= \sum_{a, s'} \pi(a \vert s) p(s' \vert s, a) \left[ r(s, a, s') + \gamma V_{k+1}(s') \right] \\ &= \sum_{a} \pi(a \vert s) \sum_{s'} p(s' \vert s, a) \left[ r(s, a, s') + \gamma V_{k+1}(s') \right] \\ &= \sum_{a} \pi(a \vert s) \left[ r(s, a, s') + \gamma V_{k+1}(s') \right] \\ \end{align*}\]

상태 전이가 결정적이기 때문에 식을 더욱 단순화할 수 있다. 다음 상태 $s’$가 고유하게 결정되므로 모든 상태에 대한 합을 구할 필요 없이 하나의 s’에 대해서만 계산하면 된다.

반복적 정책 평가 알고리즘을 이용하여 정책 $\pi$의 가치 함수를 구해보자.

1.3 반복적 정팩 평가 - 다른 구현 방법

2. 더 큰 문제를 향해

2.1 GridWorld 클래스 구현

2.2 defaultdict 사용법

2.3 반복적 정책 평가 구현

3. 정책 반복법

3.1 정책 개선

3.2 평가와 개선 반복

4. 정책 반복법

4.1 정책 개선

4.2 평가와 개선 반복

5. 가치 반복법

5.1 가치 반복법 도출

5.2 가치 반복법 구현

6. 정리

Reference

Deep Learning from Scratch 4

You may also enjoy