ch06. MDP를 모를 때 최고의 정책 찾기

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

 

본 챕터를 진행하기 전에 2가지 전제조건을 다시한번 언급하면,

1. 작은 모델(상태집합과 액션집합이 작다)

2. MDP를 모른다 (보상함수와 전이확률분포를 모른다)

 

이런 조건 하에서 그리드 월드 환경에서 최고의 정책을 찾는 방법을 3가지 소개한다.

1) 몬테카를로 컨트롤,

2) SARSA

3) Q 러닝

 

1. 몬테카를로 컨트롤

CH04 에서 언급한  MDP를 알 때 최적 정책함수 구하는 방법 중 정책이터레이션 방법이 있다.

위 그림이 정책 이터레이션 방법을 구조화 시킨 것이다.

하지만, 모델 프리 상황에서는 정책이터레이션을 그대로 사용할 수 없다.

이유는 2가지이다.

첫번째, 보상과 전이확률을 모르기 때문에 정책평가단에서 반복적 정책평가를 사용할 수 없다.

벨만 기대 방정식 2단계 공식을 보면 아래와 같다.

위 식을 통해 상태별로 반복적 정책 평가가 이루어지는데 공식 중에

보상 \( r_s^a \)와 전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 계산을 할 수 없게 된다.

 

두번째, 만일 첫번째 문제를 해결해서 각 상태의 밸류를 알고 있는 상태라고 가정할 때,

전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 그리드 정책을 수행할 수 없다.

즉, 다음상태의 리턴 기댓값이 큰 상태로 이동하는 정책을 수립해야 하는데 각 액션이 정해진 상태에서 다음상태로 이동을 예측할 수 없기 때문에 밸류를 계산할 수 없어서 그리디 정책을 수립할 수 없다.
따라서 모델 프리 상황에서 정책 이터레이션을 적용하려면 몇 가지 변형을 주어야 한다.

변형 1 : 
반복적 정책평가 방법에 앞에서 언급했던 MC를 적용하는 것이다.
MC는 MDP를 모를 때 밸류를 계산하는 방법이므로 적용가능하다.

변형 2:
정책개선단계에서 \( \nu(s) \) 대신 액션가치함수 q(s, a)를 이용한다.

q(s,a)를 알게 되면 MDP정보를 몰라도 q(s,a)가 큰 액션을 선택해 나가는 그리디 액션을 선택할 수 있다.

 

위 2가지 내용을 종합하면,

몬테카를로 방법을 이용하여 q(s,a)를 계산하고 평가된 q(s,a)를 이용해 새로운 그리디정책을 만들고, 이 정책에 대해 다시 MC를 이용하여 q(s,a)를 계산하는 일련의 과정을 반복하는 방법으로 MDP를 몰라도 최적의 정책을 찾을 수 있다.

 

마지막으로 여기에 추가되어야 하는 것이 있다.

에이전트가 최적의 정책을 찾으려면 MDP 상에 많은 상태를 충분히 탐색해야 한다.

만일 학습과정에서 도달해보지 못한 상태가 있는데 그 상태가 가장 좋은 상태인 경우 최적의 정책을 못찾게 되는 것이다.

하지만, 모든 액션을 완전히 랜덤하게 선택하면 모든 상태를 방문할 확률은 높지만 최적의 정책을 찾지는 못 할 것이다.

따라서 랜덤의 정도를 정해주는 \( \epsilon \) - greedy 방법론을 적용한다.

 

변형 3: greedy  대신 decaying \( \epsilon \) - greedy 방법론 적용

 

 

위 수식에서 \( \epsilon \) = 0.1 이라면, 

90%  확률로 q(s,a)값이 가장 높은 액션 a를 선택하고, 나머지 10% 확률로 랜덤하게 액션을 선택한다.

 

이 내용을 활용하여 학습을 진행할 수록 랜덤확률을 줄이고 파악된 정보를 이용해 최적의 정책을 찾아갈 수 있도록 \( \epsilon \)값을 줄여나가는 방법을 추천한다.

 

decaying \( \epsilon \)-greedy 방법론:

초기 학습과정에는 수집된 정보가 많지 않기 때문에 \( \epsilon \)값을 높게 주어 많은 상태를 접할 수 있도록 하며, 점차로 \( \epsilon \)값을 낮추어 학습에서 얻은 정보를 활용하여 최적의 액션을 선택할 수 있도록 유도한다.

또한 학습과정에 성능이슈를 줄이기 위해 정책평가단계에서 가치테이블에 값들을 한번만 계산하고 정책개선 단계로 넘어가도록 한다. (간소화된 정책 이터레이션)

2. TD 컨트롤 1 (SARSR)

정책평가 단계에서 MC 대신 TD를 사용하는 정책 이터레이션 방법이다.

위 그림은 TD컨트롤을 SARSA 라고 부르는 이유를 설명하고 있다.

 

SARSA는 정책평가 단계에서 MC대신 TD를 사용하여 평가를 진행한다.

각 상테에서 다음 상태로 이동해가면서 액션가치함수 q를 업데이트 시키게 된다.

이때 업데이트 식은 아래와 같다.

여기서 빨간색 부분인 \( R + \gamma Q(S^{'}, A^{'}) \) 을 TD타깃으로 볼 수 있다.

결국 이 부분을 스텝별로 계산해가면서 업데이트 하게 되면  정책개선 단계에서 활용하여 더 좋은 정책을 선별할 수 있게 된다.

3. TD 컨트롤 2 (Q러닝)

Q러닝 설명 전에 타깃정책과 행동정책, Off-Policy 와 On-Policy 개념을 설명한다.

 

타깃정책 : 강화하고자 하는 목표가 되는 정책이다. 학습의 대상이 되는 정책이며 업데이트 됨에 따라 점점 강화되는 정책이다.

행동정책 : 실제로 환경과 상호 작용하며 경험을 쌓고 있는 정책을 의미한다.

On-Policy : 타깃정책과 행동정책이 일치하는 경우를 의미(현재까지 논의되었던 모든 상황)

Off-Policy : 타깃정책과 행동정책이 일치하지 않는 경우를 의미 (간접경험을 통해 실력을 향상시키는 방법- 예를 들면, 게임을 하고 있는 친구의 행동을 관찰하면서 실력을 향상시키는 상황)

 

3.1 Off-Policy 학습의 장점

(1) 과거의 경험을 재사용할 수 있다.

일반적인 On-Policy 방법론에서는 타킷정책과 행동정책이 일치해야 한다.

SARSA 를 사용한다고 가정할 때 에이전트의 초기 정책 \( \pi_0 \)를 이용하여 하나의 에피소드를 진행해나가며 행동가치함수 q를 업데이트하고 이를 활용해 정책을 \( \pi_1 \)로 수정한다. 새로 수립된 정책을 가지고 다시 처음부터 경험을 쌓아 가야 한다. 

여기서 새로 수립된 정책 \( \pi_1 \)정책이 타깃정책이며 실제 행동을 취했던 정책이 \( \pi_0 \)정책인데 On-Policy정책에서는 타깃정책과 행동정책이 일치해야 하므로 \( \pi_1 \)정책을 강화하기 위해서는 \( \pi_1 \)정책을 사용하여 액션을 통해 경험을 쌓아가야 한다.

하지만 Off-Policy 방법론은 타깃정책과 행동정책이 다르므로 \( \pi_1 \)정책을 강화하기 위해 \( \pi_0 \)정책을 근거로 액션을 선택하며 경험을 쌓은 정보를 재활용할 수 있다.

 

(2) 전문가들의 정책을 액션정책으로 활용할 수 있다.

보통은 랜덤정책으로 초기화하고 학습을 진행하면서 조금씩 유의미한 학습이 이루어지도록 하게된다. 따라서 초기에 유의미한 학습이 이루어지기까지 상당한 양의 학습이 필요하게 된다.

만일 초기에 전문가들의 정책을 적용하여 학습을 시작하게 되면 학습속도를 높일 수 있게 된다.

 

(3) 일대다, 다대일 학습이 가능하다

동시에 여러 개의 정책을 학습키는 경우, Off-Policy 학습을 이용하면 1개의 정책만 경험을 쌓게 하고, 그 결과 데이터를 이용해 동시에 여러 개의 정책을 학습시킬 수 있다.

반대로 동시에 여러 개의 정책이 각각의 경험을 통해 얻은 데이터를 모아서 1개의 정책을 업데이트 할 수도 있다.

 

3.2 Q러닝의 이론적 배경 - 벨만 최적 방정식

 

위 식은 \( q_{*}(s,a) \)의 정의를 식으로 표현한 것으로 상태집합 S와 행동집합A가 주어진 MDP 상황에서 존재하는 모든 정책 중에 가장 좋은 정책을 따를 때의 가치함수를 의미한다.

 

또한, \( q_{*} \)를 알게 되면 상태마다 \( q_{*} \)의 값이 가장 높은 액션을 선택하면 그것이 가장 좋은 정책, 최적 정책이 된다.

수식으로 표현하면 아래와 같다.

결국 최적정책을 찾기 위해서 최적의 액션가치함수 \( q_{*} \) 를 찾으면 된다.

 

이제 \( q_{*} \) 를 찾는 방법을 설명한다.

기본이 되는 수식은 아래의 벨만 최적 방정식 0단계이다.

 

이 식을 근거로 Q러닝의 업데이트 식은 아래와 같다.

앞에서 언급한 SARSA 의 업데이트식과 비교해보면 아래와 같다.

빨간색 글자 부분이 Q러닝과 SARSA  업데이트식의 차이부분이다.

 

위 식에서 알 수 있듯이 밸류 업데이트 수식은 비슷하지만 아래의 표에서 보는 것처럼 SARSA는 On-policy방식이고, Q러닝은 Off-Policy방식이다.

SARSA와 Q러닝이 다른 이유는 기초가 되는 수식이 다르기 때문이다.