[강화학습] 동적 계획법 - 반복 정책 평가 (Iterative Policy Evaluation)

 

 

최적 정책을 구하는 3가지 방법

 

이 글을 읽기 전에 이전에 포스팅한 Bellman Equation을 읽고 본다면 이해가 더 잘될것이다.

2024.10.04 - [Data Science/강화학습] - [강화학습] 벨만 방정식 (Bellman equation)

[강화학습] 벨만 방정식 (Bellman equation)

 

 

앞으로 세 포스팅은 위 주제에 관한 내용을 다루어볼 예정이다.

최적 정책을 구한다는 것은 강화학습의 궁극적인 목표이다. 총 3가지 방법이 있다.

강화학습 종류, 그 중에서 Dynamic Programming, DP를 다뤄보는 중

1. Dynamic Programming (planning)
2. Monte-Carlo Method (learning)
3. Temporal-Difference Methods (learning)

 

총 3가지가 존재한다. 이번 포스팅에서는 동적 계획법(Dynamic Programming) 중에서 반복 정책 평가(Iterative Policy Evaluation)를 다루어보고자 한다.

 

그 전에, 동적 계획법(Dynamic Programming)이 무엇인지 알아보자.

 

 

 

동적 계획법(Dynamic Programming)

 

동적 계획법은 크고 복잡한 문제를 여러 개의 작고 단순한 문제로 나누어 계산하는 방식이다.

$$  \upsilon _{\pi }(s_{t})=R_{t+1}+\gamma \upsilon _{\pi }(s_{t+1}) $$

위 식에서 현재의 state인 $ s_{t} $ 를 큰 문제, 다음 state인 $ s_{t+1} $ 를 작은 문제라고 정의했을 때, 큰 문제를 해결하기 위해서는 작은 문제들을 계속해서 풀어나가야 한다.

하지만 그렇게 풀게되면 계산량이 너무 많아질 것이다.

같은 문제를 계속해서 반복해야할 수도 있다.

 

그래서 Richard Bellman이 고안한 방식은 다음과 같다.

중간 솔루션들을 table에 저장하고 재사용 하는 방식을 만들었다.

그래서 $ \upsilon _{\pi }(s_{t}) $을 풀 때 $ \upsilon _{\pi }(s_{t+1}) $ 이 이미 계산되어있는 값이라면 꺼내 쓴다는 것이다. 

 

Dynamic Programming 에는 3가지 종류가 존재한다.

1. Iterative Policy Evaluation (반복 정책 평가) algorithm
2. Policy Iteration (정책 반복) algorithm
3. Value Iteration algorithm

이 중에서 이번 포스팅에서는 Iterative Policy Evaluation을 다루어볼 예정이다.

 

 

 

반복 정책 평가(Iterative Policy Evaluation)

 

임의의 정책 π를 평가하여 State Value를 평가하는 방식이다.

3가지 방법 중에서 가장 기본적인 알고리즘이라고 할 수 있다. 

 

이때 정책 평가(Policy Evaluation)에 대해서 조금 더 알아볼 필요가 있다.

Poliocy Evaluation : 특정 policy π에 대하여 state value function $ \upsilon _{\pi } $ 를 계산하는 작업이다.

$$ \upsilon _{\pi }\doteq E_{\pi }[G_{t}|S_{t}=s] $$

$$ G_{t}\doteq \sum_{k=0}^{\infty }\gamma ^{k}R_{t+k+1} $$

policy π를 따를 때 state s의 기대이득(expected return)을 구하는 것임을 이전 포스팅에서 자세히 다루었었다.

$ G_{t} $ 또한 전체 보상값 R의 총합이라는 것을 다루었었다.

 

 

이제 반복 정책 평가에 대해서 자세히 알아보자

 

다음 식은 Bellman Equation 이다.

$$ \upsilon _{\pi }(s)=\sum_{a}^{}\pi (a|s)\sum_{s', r}^{}p(s', r|s, a)[r + \gamma \upsilon _{\pi }(s')] $$

이 식을 이용하여 current state의 가치 $ \upsilon _{\pi }(s) $를 업데이팅 하는데 쓰이게 된다.

이 Bellman Equation을 업데이트 룰로 사용된다.

 

위 업데이팅 과정을 무한반복(k → $ \infty $) 시킨다.

$$ \upsilon _{k+1}(s)\leftarrow \sum_{a}^{}\pi (a|s)\sum_{s', r}^{}p(s', r|s, a)[r + \gamma \upsilon _{k }(s')] $$

무한반복을 시키다 보면 $ \upsilon _{k} = \upsilon _{\pi } $ 되는 $ \upsilon _{k} $ 가 $ \upsilon _{\pi } $에 수렴되는 시점이 나오게 된다.

그 의미는 예측값이 실제 값에 가까워진다는 것을 의미한다.

 

 

식을 통해서 그 의미가 무엇인지 살펴보았는데 그림을 통해서 어떻게 수렴이 되는지, 어떻게 반복이 되는것인지 알아보자.

실제 코딩을 할 때는 2개의 array로 업데이팅을 진행한다.

1개의 array로 업데이팅을 할 수 있긴 하다.

 

2-array version (Full sweep)

 

일단 state value V와 V' 2개를 만든다.

그 목적은 Bellman equation로 V에 있는 state들을 통해서 위 그림과 같이 V'를 하나씩 sweep 하는 것에 있다.

그런 후 아래 그림과 같이 업데이팅된 V' 값들을 V에 다시 update 해준다.

2-array version (Full sweep 후 original array를 update)

 

이 과정을 계속해서 반복한다.

그럼 sweep를 통해서 계산된 값들이 V'에 저장되고, 그 값들이 V에 다시 업데이트 되고, 그 V에서 계산된 값들이 V'에 저장되는 반복되는 과정을 의미하는 것이다.

 

 

 

Iterative Policy Evaluation - Gridworld

 

이해를 돕기 위해 예제를 통해 더욱 자세히 알아보도록 하자.

 

Iterative Policy Evaluation example - Gridworld

Environment : 

• Episodic MDP
• 두 개의 Terminal state(회색 부분)에 도달하면 종료
• 그 외 모든 action의 reward는 -1

action : 

• action = up, down, right, left
  • π(a | s) = 0.25
• 각 action은 deterministic
  • p(s', r | s, a) = 1

위 조건들을 고려해보았을 때, Bellman Equation에서

 

$  V _{k+1}(s)=\sum_{a}^{}\pi (a|s)\sum_{s', r}^{}p(s', r|s, a)[r + \gamma V_{k }(s')] $

π(a | s) = 0.25, p(s', r | s, a) = 1 이므로

 

$ V _{k+1}(s)=\sum_{a}^{}\times 0.25\times [-1 + V_{k }(s'(s, a))] $

$ = [-1 + V_{k }(s'(s, a))] $

조금 더 간단하게 정리할 수 있다.

 

k는 현재 state에서 종료시 까지의 예상 step 수를 의미하는 것이다. (k → $ \infty $)

$ s'(s, a) $는 state s 에서 action a를 했을 때 next state s'를 의미하는 것이다.

 

이 Gridworld에서 최적경로를 찾는 optimal policy를 찾는 과정을 위에서 보여준 2 개의 array로 업데이팅 해보도록 하자.

일단 모든 state의 초기값은 0 이다.

Gridworld의 모든 초기 기댓값은 0

이제 각각 한 state에서 모든 action들을 고려했을 때의 합인 기댓값들을 구해야 한다.

sweep 하는 순서는 2-array version에서 중요하지 않다.

 

 

위의 식에서 간단화한 Bellman Equation을 통해서 V'에 있는 한 state의 기댓값을 구해본 결과 -1의 값을 가지게 되었다.

V를 통해서 V'를 sweep 하는 과정을 보이고 있는 것이다.

V를 통해서 V'를 sweep 하는 첫 번쨰 과정

 

 

모든 state의 초기값을 0으로 두었기 때문에 첫 sweep을 마친 결과는 아래 그림과 같이 state value는 모두 -1이 나오게 된다.

Terminal state는 value가 정해져 있기 때문에 sweep 하지 않는다.

after first sweep

 

이 다음으로 V' → V updating을 해야하는데 이때, 조건을 걸어 프로그램이 끝나는 시점을 정할 수 있다.

$$ \theta =0.001 $$

$$ \Delta \leftarrow max(\Delta , |V'(s)-V(s)) $$

델타($ \Delta  $)는 V와 V'의 각 state value의 차이값을 의미한다.

그 차이값이 $ \theta $ 보다 작을 때 종료된다는 조건을 걸었다.

즉, V와 V'의 각 state value의 차이값이 0.001보다 작을 때 updating이 종료된다.

first sweep을 하고난 후는 $  \Delta=1 $ 인 것을 알 수 있고, 종료되는 조건을 만족시키지 못하므로 updating이 실행된다.

after first update

 

이렇게 update가 끝난 후 다시 sweep이 일어난다.

after second sweep

after third sweep

 

Terminal State의 영향이 점점 전파되는 것을 확인할 수 있다.

위 sweep → update → sweep → update → ... 과정을 계속해서 반복했을 때 종료 조건에 만족되는 시점에 도달하게 된다.

after 113 iteration

차이가 거의 존재하지 않는다는 것을 확인할 수 있고, 수렴되었다고 할 수 있다.

Iterative Policy Evaluation algorithm을 통해 uniform random policy ( π(a | s)) = 0.25 )의 value function에 수렴된다는 것을 확인할 수 있다.

그렇다면 optimal policy를 특정할 수 있다.

각 state에서 사방에 있는 value값들을 보면서 가장 큰 값들이 있는 방향으로 움직이면 된다.

만약 state value = -20인 state 에서는 -18의 방향으로, -18에서는 -14, -14에서는 0의 방향으로 움직이면 된다.

Iterative Policy Evaluation으로 얻은 optimal policy

 

이 과정은 Random policy가 Greedy policy로 바뀌는 과정이라고 할 수 있다.