강화학습 3 <환경을 모를때 MDP 풀이, MC, TD, SARSA, Q-Learning>

강화학습은 MDP로 정의된 문제를 푸는 방법이다. 문제를 푸는 방법(알고리즘)에는 여러 종류가 있는데, 문제의 특성에 따라 적용가능한 방법이 달라진다. 가장 중요한 문제의 특성은 환경을 아느냐 (MDP로 정의된 문제의 P와 R을 아느냐) 이다. 환경을 안다면 Dynamic Programming (이하 DP)을 사용한다. DP에는 동기적 DP로 분류되는 정책 반복과 가치 반복이 있다. 전체 state의 가치 함수를 업데이트 하는 동기 DP의 연산량을 줄이기 위해 비동기 DP 방법이 개발되었다. DP방법은 약 3가지 단점이 있는데 각각 state 수 증가에 따른 연산량 증가, state 차원 수 증가에 따른 연산량 증가, 환경을 아는 상황에만 적용 가능하다는 것이다.

 

현실의 MDP로 정의된 문제들은 모르는 경우가 많다. 그래서 DP의 3번째 단점을 해결하기 위해, 몇가지 방법들이 개발되었고 이것을 금일 정리할 것이다. 이들은 환경을 모르는 상황에서 Agent가 환경과 상호작용(state에서 action을 선택하고 reward를 얻으며) 하며 '학습'하고 이를 통해 최적 정책과 최적 가치/행동 상태 함수를 얻는 방법이다.

 

우선 DP에서 문제를 푸는 순서는 각 state 별로 가치/행동 함수를 계산하는 것, 이를 기반으로 정책을 업데이트 하는 법 2가지로 전개된다. 전자는 Prediction이라하고, 후자는 Control 이라고 칭한다. (영단어와 의미가 매칭되지는 않는 것 같다.)

 

이에 따라 금일도 Prediction과 Control을 나누어 개념을 공부해보자.

---

1. Monte Carlo prediction 

Monte Carlo 방식은 문제의 답을 (구해내고자 하는 것을) 계산해 내는 것이 아니라 여러번의 시도에서 나온 결과를 바탕으로 값을 지속적으로 업데이트 해 나가는 것이다. 따라서 특정 값을 지속적으로 추정해 나간다.

 

MDP에서 MC 기법의 역할은 각 상태에서 상태 가치 함수를 구하는 것이다. 한 Episode가 종료된 후 모든 state에서 반환 값(Return)을 계산한 후 기존의 상태 가치 함수에 반영한다. 즉, 하나의 Episode가 끝날 때마다, Epdisode에서 얻은 결과(Reward, Return)를 반영하는 것이다. 따라서 Monte Carlo prediction을 사용하기 위해서는 반드시 Episode가 종료되어야 한다. 그리고 업데이트 횟 수만큼 step size를 반영하는데, 이는 충분히 작은 숫자로 설정을 해주어도 위 알고리즘이 수렴됨이 증명되어 있다. MC기법은 내재된 편향은 없지만 (Episode가 종료된 후 결과를 바탕으로 학습되므로), 분산이 큰 편이다.

 

2. Temporal Difference

Monte Carlo 방식은 환경을 모를 때 적용할 수 있고, 충분히 많은 학습이 이루어지면 수렴함이 증명되어 있다. MC의 단점은 Episode가 종료되어야 지만, 상태 가치 함수를 업데이트할 수 있다는 것이다. 그렇다면 Episode가 너무 길거나 끝나지 않는 문제에서는 Monte Carlo prediction을 사용할 수 없다. 이를 보완하기 위해 Temporal Difference가 제안되었다. 

 

Temporal Difference는 한 Episode내에서 Agent가 action을 통해 state가 변경될때마다 상태 가치 함수를 업데이트 한다. 이때 목표 값은 Return + 감가율 x 다음 상태에서의 상태 가치 함수이다. 이때 반환값의 정의 중 미래 부분은 다음 state의 상태 가치 함수로 치환한 식을 사용한다. (즉, 특정 상태에서 얻을 수 있는 실제 Return이 아닌, 학습되고 있는 값인 상태 가치 함수를 사용하는 것이다.)

 

Temporal Difference는 업데이트 목표 값이 실제 목표해야 하는 값이 아니라 (Episode가 종료된 후 가 아니라) 현재 상태에서 Agent가 가지고 있는 값이다. 학습 중인 값을 업데이트 목표로 사용하기 때문에, 본 방법은 편향을 가지게 된다. (이러한 방식을 Bootstrap이라 한다. 자신이 가진 업데이트 중인 값을 업데이트 목표로 설정하는 방식) 직관적으로 이 방식은 수렴하지 않을 것이라 생각되지만, 충분히 많은 샘플링으로 업데이트 하면 참 가치 함수에 수렴하고, 보통 Monte Carlo 방식보다 더 효율적으로 빠른 시간에 근접한다고 한다. 하지만 충분히 많은 학습을 해도 편향에 의한 오차는 포함하고 있는 것이 단점이다.

 

이렇게 환경을 모를 때 상태 가치 함수를 추정할 수 있는 Monte Carlo와 Temporal Difference을 공부했다. MC는 Episode가 끝난 후 결과를 바탕으로 상태 가치 함수를 업데이트 하고, 참 값에 수렴 가능하지만 분산이 존재한다. TD는 Episode 중에도 상태 가치 함수를 업데이트 할 수 있지만, 참 값이 수렴하지 못하고 분산은 작은 편이다.

---

지금부터는 MC와 TD로 업데이트 된 상태가치함수를 바탕으로 최적 정책을 얻을 수 있는 SARSA와 Q-Learning을 공부할 것이다. 

 

3. SARSA

SARSA는 정책을 업데이트 하는 방법에 관한 방법이다. DP에서는 정책 개선(Policy Improvement)에서 탐욕 정책(Greedy)을 사용했다. 이는 특정 state에서 state value function이 가장 높은 action의 policy 값을 1로 설정하고 나머지 policy는 0으로 설정하는 것이다. SARSA에서는 P를 모르기 때문에, policy를 학습하기 위해 각 state의 action state function을 사용한다. 이때 해당 함수를 업데이트 하는 식은 아래와 같다. 즉, 현재 상태에서 특정 Action에 대한 Q함수는 "Reward + Action 이후 도달하는 State에서 특정 Action을 선택할 때의 Q함수"를 목표값으로 두게 된다. 이때 현재 state, 현재 Action, Reward, 다음 state, 다음 action을 사용하기 때문에 이를 하나씩 철자로 가져와 SARSA 방법이라 지칭한다. 

 

이때 다음 state에서 특정 action을 선택할 Q함수를 사용하게 된다. 이때 agent가 충분히 학습되지 않은 초기 상황이라면 해당 q함수가 잘못된 행동을 할 확률이 있다. 그래서 policy는 탐욕정책이 아닌 탐험이 필요하다. 탐험의 개념을 도입하기 위해 e-탐욕 정책을 도입하게 된다. 이는 특정 확률 로 q함수가 가장 큰 action이 아닌 다른 action을 선택하는 것이다. 이를 통해 SARSA에서 초기 학습 시 잘못된 학습 하는 것을 방지할 수 있다. 그런데 충분히 학습이 된 이후에도 특정 확률로 다른 action을 선택하는 것은 비효율적일 수 있다. 그래서 학습 진행 정도에 따라 e 값을 감소하는 전략을 쓰기도 한다. 하지만 SARSA와 다음에 배울 Q-learning에서는 e값이 일정한 e-탐욕 정책을 사용한다.

 

이처럼 SARSA는 정책 반복에서의 정책 평가를 Action state function 기반으로, 정책 개선을 e-탐용 정책으로 개선한 강화학습 알고리즘이다.

 

4. Q-learning

SARSA의 단점은 action value function을 업데이트 할 때 action 이후 다음 state에서의 action에 대한 action value function을 사용하는데, 이때 다음 state에서 action을 결정할 때도 e-탐욕 정책에 의해 max action value function이 아닌 탐험을 하게 될 수 있다는 것이다. 이는 다음 state에서의 action이 reward가 낮은 선택이라면, 현재 state에서의 action은 reward가 실제로 높은 선택임에도 불구하고, 낮은 reward로 업데이트 하게 되는 문제가 생긴다. 그래서 실제로 현재 state에서 reward가 높은 선택이지만, reward가 낮아지는 잘못된 학습을 하게 된다.

 

이를 보완하기 위해 Q-Learning에서는 다음 state에서의 policy는 e-탐욕 정책이 아닌, 탐욕 정책을 사용해 action value function을 사용하게 된다. 즉, 현재 state에서 action을 결정할 때는 e-탐욕 정책(탐험 포함), 다음 state에서 action을 선택할 때는 탐욕 정책을 사용하는 것이다.

 

Q-learning은 실제 agent가 행동할 때는 e-탐욕 정책을 사용하지만, Prediction과 Control을 할때는 e-탐욕정책 + 탐욕 정책을 사용한다. 즉, 실제 행동과 학습에 사용되는 policy가 다르기 때문에 Off-Policy 방법이라 불리기도 한다. Q-learning은 이후 많은 강화학습 알고리즘의 토대가 되었다.

 

잘 생각해보면, SARSA는 벨만 기대 방정식을 사용해 Action value function을 업데이트 하고, Q-Learning은 벨만 최적 방정식을 사용해 Action value function을 업데이트 하는 구조이다.

 

---

오늘은 환경을 모르는 상황일 때 MDP 문제를 풀 수 있는 방법인 Monte Carlo, Temporal Difference, SARSA, Q-Learning을 공부했다.  이 방법들은 DP 방법이 가진 단점 중 환경을 모르는 상황에서 적용 불가 라는 문제는 해결하였지만,  state 수 증가에 따른 연산량 증가, state 차원 증가에 따른 연산량 증가는 여전히 존재한다. 

 

다음에는 이 문제들을 해결한 방법들에 대해 알아보자.