[강화학습 이론] 몬테카를로 예측 (Monte-Carlo Prediction)

책: wikibook.co.kr/rlrev/

파이썬과 케라스로 배우는 강화학습 (개정판): 내 손으로 직접 구현하는 게임 인공지능

참고: dnddnjs.gitbooks.io/rl/content/

※본문 내용은 위의 자료들을 요약·정리한 것이 포함되어있습니다.

 

강화학습의 예측과 제어

이전 포스팅에서 DP에 대해 설명했는데 DP는 벨만 방정식을 통해 가치함수와 정책을 업데이트시켜 최적의 정책을 찾아가는 방식이었다. 이 방법은 MDP의 모든 정보를 알고 있어야 풀 수 있다. 특히 환경의 모델이라고 부르는 "보상함수"와 "상태 변환 확률"을 알고 있어야 계산 가능하다. 

하지만 이렇게 환경을 알고 있는 경우(Model-based 한 방법)에는 몇 가지 문제점이 있다고 했다. 

1. Full-width backup

: 가능한 모든 다음 상태의 가치함수를 사용하여 현재 상태의 가치함수를 백업하는 방법

 full-width backup의 방법을 통해 백업을 한다면 계산 복잡도가 크다. 상태의 수가 많을수록 더욱 커지는데, DP의 경우   계산 복잡도는 상태 크기의 3 제곱에 비례한다. 

2. 환경에 대한 완벽한 정보가 필요함

위에서 언급한 것처럼 MDP에 대한 모든 정보를 알고 있어야 하며, 특히 환경의 모델에 해당하는 보상과 상태 변환 확률에 대해 알고 있어야 한다. 

따라서 이런 문제점들을 보안하는 방법이 필요하다. full-width backup 보단 실제로 경험한 정보들을 통해 업데이트하는 방법인 sample backup을 통해 계산 복잡도를 줄인다. 또한 실제로 경험한 정보들을 사용하기 때문에 처음부터 모든 환경에 대해 완벽히 알 필요가 없다. 따라서 모델을 모르는 Model-free 한 방법을 사용한다. 이러한 개념이 강화학습에서 사용되는 개념들이고 실세계에서 사람의 학습과 비슷한 모습이다. 실제로 사람이 무언가를 학습할 때에도 모든 것을 다 알고 움직이지 않는다. Trial and error를 통해 그냥 해보고 자신을 평가하며 평가대로 자신을 업데이트시켜가는 것이다. DP는 효율적으로 "계산"을 하기 위한 알고리즘이다. ("학습"의 개념 들어가 있지 않음) 

DP에서 정책 평가에 해당하는 것이 강화학습에선 "예측" (또는 추정)이라고 하며 환경과의 상호작용을 통해 주어진 정책에 대한 가치함수를 학습한다. DP에서 정책발전에 해당하는 것은 강화학습에서 "제어"라고 한다.  예측을 기반으로 정책을 발전시켜 최적의 정책을 학습하는 것이다. 예측에는 오늘 설명할 몬테카를로 예측(MC)과 시간차 예측(TD)이 있고, 제어에는 시간차 제어(SARSA)와 오프폴리시 제어(Q-Learning)가 있다. 

 

몬테카를로 예측

몬테카를로 근사 

몬테카를로 예측에 대해 살펴보기 전에 몬테카를로 근사의 개념에 대해 먼저 알아보자. "몬테카를로 (Monte-Carlo)"라는 말은 무엇인가를 무작위 하게 측정하는 것을 의미한다. 통계적인 추정이며 sample을 통해 원래의 값에 대해 추정하는 것이다. 

예를 들어 종이 위에 원이 하나 그려져 있는데, 원의 방정식을 사용하지 않고 원의 넓이를 구하는 방법에 대해 고민해보자. 일단 종이 위에 무작위로 점을 계속 찍는다. 그 점들 중에는 원 안에 찍힌 점도 있을 것이고 원 밖에 찍힌 점도 있을 것이다. 이 점을 찍는 행위를 무수히 많이 하여 빼곡하게 점이 찍혔다면 이 점들의 비율로 넓이를 추정할 수 있다. (원 안의 점 개수) / (전체 찍은 점 개수)를 통해 구할 수 있는 것이다. 

몬테카를로 예측 

몬테카를로 근사를 이용해 참 가치함수를 추정하는 것이 몬테카를로 예측이다. 즉, 샘플링을 통해서 얻은 샘플의 평균으로 참 가치함수 값을 추정한다. 위에서 예시로 든 원의 넓이 구하는 몬테카를로 근사에서 점을 찍는 행위가 샘플링이었다. 그렇다면 가치함수를 구하는 몬테카를로 예측에서 샘플링은 무엇일까? 바로 에피소드를 한 번 진행하는 것이다. 다시 말해 몬테카를로 예측은 에피소드를 여러 번 진행해서 얻은 샘플들의 평균을 통해 참 가치함수에 수렴해가는 과정이다. 

DP의 정책 이터레이션에서 정책 평가는 벨만 기대 방정식을 이용해서 가치함수를 "계산"하는 과정이었다. 벨만 기대 방정식에 포함되어있는 기댓값을 계산하려면 환경 모델을 알아야 하기 때문에, 몬데카를로 예측에서는 환경을 몰라도 계산할 수 있는 반환값을 이용한다. 현재 정책에 따라 계속 행동을 하면 그에 따른 보상을 받고 반환값을 계산할 수 있다. 따라서 몬테카를로 예측에서는 여러 에피소드를 통해 구한 반환값의 평균을 통해 가치함수를 추정한다. 

몬테카를로 예측 예시

위의 그림을 살펴보면 현재 상태 s에서 빨간색으로 표시된 마지막 상태까지의 상태 이동 과정을 에피소드 별로 나타낸 것이다. 여기서 i가 에피소드를 뜻하며 총 5번의 에피소드를 진행한 모습이다. 5번의 에피소드 모두 상태 s를 지났으므로 위의 5개의 에피소드에서 구한 s에서의 반환값을 평균 내 상태 s에서의 가치함수 값을 추정할 수 있다. 상태 s를 지난 에피소드가 더욱 많을수록 참 가치함수에 수렴하게 되는 것이다. 

 

가치함수 업데이트

위에서 설명한 가치함수를 추정하는 수식을 변형시키면 아래와 같다. 

편의상 상태에 대한 표현을 생략하고 n개의 반환값의 합을 n번째 반환값과 n-1개의 반환값의 합으로 나눌 수 있다. 

세 번째 줄의 수식은 임의로 (n-1)/(n-1)을 곱해주었다. 

네 번째 줄의 수식에서 n-1개의 반환값을 합한 것에 n-1을 나눠준 평균값은 몬테카를로 예측에서 가치함수 추정식과 같기 때문에 이전 에피소드(n-1)에서 구한 가치함수로 생각할 수 있다. 

그리고 마지막 수식은 윗 수식을 정리한 것이다. 

위의 과정을 거쳐 나온 수식이 가치함수를 업데이트할 때 사용하는 수식이다. 앞서 말했듯이 몬테카를로 예측으로 가치함수를 추정하는 방식은 여러 번의 에피소드를 진행하면 참 가치함수 값에 수렴한다. 그렇다는 뜻은 초반에 적은 수의 에피소드로 가치함수를 추정한 것은 참 가치함수와 거리가 멀다는 뜻이고 에피소드를 계속 진행하면서 업데이트를 진행해야 한다는 것이다. 이때 사용하는 수식이 이 수식이다. 

몬테카를로 예측에서 가치함수의 업데이트 식

이 업데이트 식의 의미를 보자면, G(s)가 이번에 새로 진행한 에피소드에서 구한 반환값으로 업데이트의 목표가 된다. 위 수식에서 우항에 있는 가치함수는 이전 에피소드까지 추정한 가치함수이고 좌항에 있는 가치함수는 이번 에피소드에서 구한 샘플 정보를 통해 업데이트 시킬 가치함수이다. 따라서 업데이트 목표에서 전에 구한 가치함수를 빼주면 그 의미는 이번 에피소드를 통해 변화가 생긴 정도를 나타낸다. 업데이트에 이 오차를 반영할 정도를 결정하는 스텝사이즈를 곱해서 이전 가치함수에 더한게 업데이트된 가치함수이다. 

에피소드가 진행되면서 지난 모든 상태에 대해 표현

위에서 예시로 든 환경을 통해 업데이트를 표현하면 에피소드가 5번 진행되면서 지난 상태들에 대해 가치함수를 업데이트 시킨 모습이다. 방문한 횟수가 많아 업데이트를 많이 시킨 상태일 수록 가치함수를 진하게 표현했다. 

 

First-visit / Every-visit

한 에피소드에서 특정 상태에 대한 반환값을 저장해놓았고, 다음 에피소드에서 동일한 상태를 또 방문해 새로운 반환값을 얻었다면 이 두 반환값의 평균을 구하는 것이 몬테카를로 방법인 것이다. 그런데 만약 한 에피소드에서 같은 상태를 여러번 방문한다면 언제 방문한 상태에서의 반환값을 이용해야 할까? 단순하게 처음 방문한 상태에서의 반환값만 이용하여 다른 에피소드에서의 반환값과 평균을 취하는 것이 First-visit 방법이고 방문할 때마다 따로따로 반환값을 계산해놓는 방법이 every-visit이다. 두 방법 모두 에피소드가 무한대로 가면 참 가치함수로 수렴한다.