머신러닝 5주차 - (04/01) 몬테카를로 방법

 

이번 포스트에서는 몬테카를로 방법에 대해 작성해보고자 한다.

 

이전에 작성했던 동적 계획법을 떠올려보자.

동적 계획법에서는 우리가 환경에 대한 정보를 오나전히 파악하고 있다는 가정하에 가치와 정책을 계산했기 때문에

최적가치와 최적 정책을 계산할 수 있었다.

그리고, 결정론적 환경으로 P 상태전이확률이 1로 가정했었다.

 

그치만, 실세계에서는 그렇지 않기에 P를 계산할 수 없다.

따라서 동적계획법으로 강화학습 문제를 푸는 것은 불가능하다.

상태전이확률을 몰라도 가치함수와 정책을 몰라도 가치함수와 정책을 계산할 수 있는 알고리즘이 필요해졌는데

 

이러한 알고리즘, 즉 상태전이확률을 몰라도 되는 알고리즘을 모델프리 알고리즘이라 한다.

 

우리는 모델프리 알고리즘에서 몬테카를로 방법과 시간차 학습을 알아볼 것이다.

 

몬테카를로 Prediction

몬테카를로 방버은 탐색적인 방법을 이용해 상태가치함수와 행동가치함수를 학습한다.

어떻게 이동할지에 대한 상태전이확률 정보가 전혀 없기에 경험으로 상태전이확률을 대신한다.

 

방법은, 하나의 Path만 재귀로 끝까지 모든 depth를 탐색하는 것이다.

 

조금 더 자세히 설명해보자면,

에이전트는 도착지점을 제외한 s0부터 s7까지 미로의 모든 상태에서 에피소드를 시작하고 에피소드 별로 얻은 수익 G를 저장한다.

모든 단계에서 행동은 간으한 행동들 중에서 무작위로 선택한다. 

그렇게 지정된 횟수 n번만큼(많으면 많을수록 좋다) 에피소드가 끝나면 수익 G들의 평균을 각 상태마다 계산해서 각 상태의 상태가치로 저장한다.

 

에피소드는 도착지점까지 상태 s3와 상태6을 두 번씪 지나가고 있다. 이러한 중복을 막기위해 아래의 두가지 방법을 제안한다.

 

1. First-visit MC(몬테카를로)

첫번째로 도착한 상태의 보상만 참고하는 방법으로 이후 중복된 상태의 보상은 계산에 포함하지 않는다.

 

2. Every-visit MC(몬테카를로)

Last-visit MC로도 생각할 수 있다.

Every-visit MC는 거쳐간 모든 상태의 보상을 수익에 참고한다

 

FIrst와 Every중 둘 중 적용하는 알고리즘에 맞게 하나만  선택한다

 

몬테카를로 방법이 제대로 학습하기 위한 전제조건은 다음과 같다

1. 모든 상태에서 시작할 수 있어야 한다

2. 에피소드는 반드시 끝이 있어야한다

이때, 끝이 없다고 계산이 불가능하다는 것은 아니다

만약 끝이 없다면, 임의로 에피소드를 끊어서 하나의 에피소드로 만들어 몬테카를로 방법을 적용할 수도 있다.

 

몬테카를로 방법의 Control

아래의 내용은 학습중일 때의 Control에 대한 것이며, 이것은 최적의 정책을 찾는 방법이다.

어떤 상태에서 행동을 선택하는 정책은 아래의 세 가지 정책 외에도 여러 가지 정책이 있다.

1. 무작위로 행동을 선택하는 정책

2. 행동 가치를 이용해 확률로 행동을 선택하는 정책

3. 행동 가치 중 가치가 가장 높은 행동을 선택하는 정책

 

*탐욕정책 : 여러가지 정책 중에서 현재 가능한 행동 중에서 행동가치가 가장 높은 행동을 선택하는 것

우리가 계속해서 실행했던 방법은 상태 가치 함수, 행동가치 함수를 계산하여 가장 큰 값을 선택하는 3번의 방법을 통해 값을 계산했었지만,

몬테카를로에서는 국소해 때문에 3번을 선택하면 안된다. 

그렇다면 국소해란 무엇일까?

*국소해 : 몬테카를로에서는 경험을 가지고 상태, 행동 가치 함수를 게산하기 때문에 예를들어, 미로에서 아래와 오른쪽으로 갈 수 있는 두 가지 선택지가 존재한다고 가정해보자.

 

이때, 처음 학습이기 때문에 어디로 가든 값은 동일하기에 랜덤한 값을 선택할 것이다

오른쪽을 선택해 학습을 진행했다고 해보자,

몬테카를로에서는 경험 학습이기에 경험이 있는 오른쪽만.아래쪽과 오른쪽 중, 아래쪽이 더 거시적으로 봤을 때 최단거리임에도 오른쪽에 대해서만 학습을 진행할 것이다.

따라서 아래쪽에 대한 학습은 절대로 진행 할 수가 없다.

따라서 전체적인 면에서 더 좋은 방법이 있으나, 부분적으로만 살펴봐 잘못된 경로를 최적의 경로라 판단하는 것을 국소해라 한다.

 

따라서, 이러한 탐욕정책을 따랐을 때 국소해에 빠지는 것을 방지하기 위해 ε-greedy(탐욕) 정책이 고안되었다.