A (Long) Peek into Reinforcement Learning -Part 3

 

자, 여태까지 강화학습의 기본 개념들, MDP, 그리고 그 MDP를 풀기 위한 방법인 Bellman Equation까지 다뤄보았다. 이번에는 RL을 푸는 대표적이고 고전적인 알고리즘들에 대해서 알아볼 것이다.

 

우선은 environment에 대한 정보를 다 알 때 사용하는 Dynamic Programming 부터 시작하여, environment에 대한 정보를 모를 때의 방법들을 다루고, 이것도 모자라 environment에 대한 정보도 제대로 모르는데 문제가 점점 커지는 경우 (state, action space가 매우 큰 경우), DNN을 사용해서 Value, Q, policy를 모델링하는 방법으로 넘어가도록 하자.  

 

---

 

알고리즘 분류법

 

출처: https://ai-sinq.tistory.com/entry/%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5-Planning-by-Dynamic-Programming

 

굉장히 좋은 사진이 있어서 가져왔다. 여러 알고리즘들이 어떤 카테고리에 속하는지 한 눈에 볼 수 있다.

 

 

 

Planning & Learning

 

Dynamic Programming에 대해 알아보기 전에, planning과 learning에 대해서 짚고 넘어가보도록 하자. 간단히 말하자면, planning은 model을 다 알고 있을 때, 그리고 learning은 model을 모를 때, 환경과 상호작용하면서 학습하는 것이다. Model을 다 아니까 우리는 계획만 하면 되기에, planning이다. DP가 여기에 속한다. DP는 우리가 environment의 (P, R) 을 안다는 것을 전제로 Bellman Equation을 사용해서 문제를 푸는 것을 의미한다. 여기서 P는 state-transition probability, R은 reward function이다. 

 

모델을 다 알고 있을 때는 Planning만 하면 되기에 DP를 사용하고, 이후 모델을 모르는 경우들이 훨씬 더 많을 것인데, 이때는 다른 method들을 사용해 환경에 직접 부딪혀가면서 Learning을 한다고 이해하면 된다. 우선 모델을 다 알고 있는 DP를 먼저 보고, 차례차례 확장해나가 보자.

---

 

 

Dynamic Programming

 

 

아까도 말했듯이 DP는 우리가 environment의 (P, R) 을 안다는 것을 전제로 Bellman Equation을 사용해서 문제를 푸는 것을 의미한다. 두 가지의 방법론으로 나눠볼 수 있는데, Policy iteration과 Value iteration이다.

 

먼저 Policy iteration은 Bellman Expectation equation을 사용하고,

Value iteration은 Bellman Optimality Equation을 사용한다. 

 

Prediction & Control

 

Policy iteration과 Value iteration에 대해 알아보기 전에, prediction과 control에 대해서 짚고 넘어가보자. DP에서 하는 일은 크게 두 가지인데, 

 

• Action을 뱉어내는 특정 Policy가 얼마나 좋은지에 대한 가치평가
• 그걸 토대로 더 나은 Policy로 업데이트

의 반복이 바로 DP이다. 그래서 Policy iteration, Value iteration 모두 뒤에 iteration이 들어가는데, 이는 위의 두 가지 과정을 반복하면서 optimal로 가겠다는 뜻이다.

 

가치평가 부분이 Prediction, 업데이트 부분이 Control이다. 조금 더 엄밀히 말하면, 현재 optimal하지 않는 어떤 policy에 대해서 value function을 구하고(prediction) 현재의 value function을 토대로 더 나은 policy를 구하는(control) 과정의 반복이라고 보면 된다.

 

---

 

Policy iteration

 

Policy iteration도 그렇고, Value iteration도 마찬가지로 가치평가 + 업데이트 의 방식으로 진행되는 건 똑같다.

 

다만 Policy iteration의 경우에는 먼저 특정 policy를 evaluation 해주고, 그 다음 더 나은 policy로 improvement 해주는 과정을 거치는 반면,

 

Value iteration은 evaluation과 improvement를 한 방에 해준다는 차이가 있다.

 

 

Policy Evaluation

 

Policy Evaluation은 말 그대로 지금 가지고 있는 policy에 대한 value function을 계산해주는 것이다. 이 계산은 이전에 봤던 Bellman Expectation equation으로 구할 수 있다.

 

지금 가지고 있는 어떤 policy π에 따른 value를 iteratively하게 계산하는 것이다. 왼쪽을 보면 k+1로,  V0부터 V1, V2, 이런 식으로 값이 나올 것을 알 수 있다. 

 

Policy Improvement

 

Evaluation으로 policy에 대한 value를 얻었으면, 더 나은 방향으로 policy를 업데이트 해줘야한다. 

 

이 업데이트는 greedy 하게 이루어진다. Greedy라 함은 가장 큰 값을 주는 걸 선택하겠다는 뜻이다. 

 

 

마찬가지로 iteratively하게 진행된다. 저 V(s) 값을 알고 있고, R과 P도 알고 있으므로 그 값을 가장 크게 만들어주는 action a가 바로 업데이트 된 policy이다. 

 

 

Understanding with Example

 

 

3x3 GridWorld Example을 볼 건데, 세팅은 다음과 같다:

 

 

3x3 grid이고, Terminal state에 들어가면 reward 0을 준다. terminal state에 들어가지 않는 행동들은 매 timestep마다 -1의 reward가 주어진다. 그러니까 계속 음수의 reward를 받지 않고 싶다면 최단으로 terminal state에 들어가는게 optimal일 것이다. 감마는 0.9로 설정하고, initial policy는 (위, 아래, 왼쪽, 오른쪽) 이렇게 각각 uniform하게 1/4의 확률로 선택되도록 하는 policy가 있다고 해보자.

 

그리고 우리는 매번 다음의 과정을 거치면 된다.

 

 

Default는 다음과 같을 것이다.

 

(0,0), (2,2) 지점에 terminal state가 있다.

 

 

Initial인 V0에서는 모든 reward를 0으로 세팅해주고, policy π 또한 처음 설정해 준 1/4의 uniform한 action distribution을 가진다.

 

 

여기서 포인트는, 우리가 어떤 한 점에서 시작하는게 아니라 모든 칸에 대한 보상과 path를 고려하기 때문에 모든 칸에 대해서 계산이 된다는 점이다. 이 포인트는 맨 마지막에 full-width backup과 sample backup의 차이를 이해하는데에 매우 중요한 직관이 된다.

 

t = 0 -> 1의 과정

 

t = 1 -> 2의 과정

 

 

 

---

 

 

Value Iteration

 

 

초반부에 이야기 했듯이, Value iteration은 evaluation과 improvement를 한 방에 하는 방법이다. 이건 위의 bellman expectation equation을 쓰는 policy iteration과 다르게 bellman optimality equation을 사용한다. 

 

 Value iteration의 생각은, 뭐든지 max 값을 내는게 제일 좋은 policy라는 것이다. 그래서 일단 value를 제일 크게 해주는 것들로 쭉 업데이트한 후, 그게 제일 좋은 policy일게 뻔하므로 policy를 거기서 뽑아내면 된다.

 

Value Update

 

 

 Value Converge

 

 

 

Policy Extraction

 

그리고 이제 최대 value를 계산했으니 여기서 policy를 뽑아내자. 어떻게? 저 값을 max 해주는 a를 찾으면, 그게 policy이다. policy는 state -> action 이렇게 매핑해주는 함수이고, 결과값이 action이 되기 때문이다.

 

 

Q-value로도 가능하다.

 

 

 

---

 

 

Sample Backup

 

 

DP는 full-width backup을 사용한다. full-width update는 한 번 업데이트할 때 모든 non-terminal한 state를 다 업데이트 시켜준다. 아까 GridWorld 예시에서 "어떤 길"을 따라 천천히 돌다리를 두들겨보면서 가는게 아닌, 다 알고 있기 때문에 모든 칸에서의 가치를 다 업데이트 시켜주는 것이다. 

 

sample backup 부터 드디어 강화학습이 시작되는데, 이게 돌다리를 두들겨보면서, agent가 한 state씩 탐험해나가면서 각 state의 value를 알아보는 것이다. 기존의 full-width backup은 전부 다 계산해야되기 때문에 한 step 업데이트에 계산량이 매우 많다는 점이 있는데, 이렇게 하면 계산도 적어지고 드디어! Model-Free가 가능해진다. 더 이상 모델에 의존하는 게 아닌, 모델에 대한 모든 정보 없이도 하나하나 확인해나가면서 업데이트하며 최적으로 나아가는 것이다.

 

다음부터는 Model-Free일 때의 방법론들을 알아보자.