강화학습 - (14) 몬테카를로

 

 

강화학습

몬테카를로 (Monte-Carlo)

몬테카를로는 강화학습 뿐만 아니라, 더 넓은 의미에서 랜덤 샘플링 기반의 반복적인 샘플링 기법으로 알려져 있다.

강화학습에서는 경험, 즉 상태, 행동, 보상의 시퀀스에 기반해서 가치를 추정하는데 사용된다.

경험에서 학습하는 것은 생각보다 많이 효율적이다.

이는 환경에 대한 사전 지식이 없이도 가치함수를 추정할 수 있게 해주기 때문이다.

 

다이나믹 프로그래밍의 한계

다이나믹 프로그래밍을 강화학습에 사용하려면, 

에이전트는 환경의 상태들간의 상태전환확률(transition probability)를 알고있어야 한다.

하지만 특정 문제들에서 우리는 이 상태정환확률을 할수 없다.

 

예제)

 

 

우리가 미래의 날씨에 대해서 예측한다고 해보자.

날씨를 변화시키는 데에는 너무나도 많은 요인이 있기 때문에 미래의 날씨가 어떻게 될지 알 수 없다.

따라서 날씨를 예측환경에서는 상태전환확률을 알 수 없게 된다.

 

몬테카를로 기법 (Monte-Carlo Method)

몬테카를로 기법은 이러한 상황을 더 쉽게 예측하게 해준다.

우리는 상태전환확률을 알아낼 필요가 없이, 경험을 통해 이를 학습한다.

아주 많은 양의 샘플을 수집한 뒤 이를 평균을 내서 이 값을 가치함수로서 사용하게 된다.

$v(s) \dot{=} \mathbb{E} [G_t | S_t = s]$

 

 

 

가치함수를 예측하기 위해서 몬테카를로 기법을 사용한다면,

각 상태에 대해서 가능한 많은 양의 경험을 한다.

샘플이 모이면 모일 수록 이 경험들의 평균은 실제 기대값과 비슷해지게 된다.

 

 

 

몬테카를로 기법은 에피소드 형태의 문제들에 적합하다.

각 샘플(결과값 $G_i$)을 얻어 가치를 산정하기 위해서는 에피소드가 끝나야 하기 떄문이다.

 

예제)

 

 

12개의 주사위를 한번에 던져서 나올 수 있는 수를 예측하는것 과같이

상식적으로 생각 가능한 일들 또한 모든 경우의 수에 대한 상태전환확률을 알기 힘들다.

 

 

 

12개의 주사위를 돌렸을 때 나올 수 있는 수를 예측한다고 하자.

이를 많은 양의 실험을 통해 예측을 한다면, 41.57이 나온다.

이는 실제 값인 42와 매우 유사한 값이 나오게 된다.

 

상태가치함수의 추정

이 처럼 몬테카를로 기법은 밴딧 문제와 유사하다.

밴딧 문제에서의 샘플평균기법을 통해 각 밴딧이 어떠한 결과를 낼지를 유추했다.

이와 비슷하게 몬테카를로 기법에서는 정책의 결과를 유추하기 위해서 샘플을 모은다.

모아진 보상을 통해 가치를 추정하는것은 큰 상태들에 대해서 꽤 효율적인 것을 알 수 있다.

또한 이 가치함수 역시 밴딧 문제에서 사용된 점진적인 갱신 법칙을 사용할 수 있다.

 

예제)

 

 

한 에피소드에서 위 그림에 나온 수만큼의 보상을 얻었고, 감가율 0.5를 고려한다고 가정해보자.

이를 역추적을 통해 계산하면 다음과 같이 계산이 가능한다.

$G_5$에서의 결과값은 최종 상태이기 때문에 당연히 0이 된다.

또한 각각 다음 상태의 보상값은 모두 그 후의 보상값들을 포함하고 있다.

이를 모두 계산하면 다음과 같다:

$G_5 = 0$

$G_4 = R_5 + \gamma G_5 = 2$

$G_3 = R_4 + \gamma G_4 = 2$

$G_2 = R_3 + \gamma G_3 = 8$

$G_1 = R_2 + \gamma G_2 = 8$

$G_0 = R_1 + \gamma G_1 = 7$

 

다음은 몬테카를로 가치 추정 알고리즘이다:

 

 

 

행동가치함수의 추정

행동가치함수의 추정은 상태가치의 추정과 매우 유사하다.

상태와 행동의 페어 $(s, a)$를 따라 행동해 결과에 대한 정보를 수집하고,이를 평균하면 된다.

$q_{\pi}(s,a) \dot{=} \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$

 

하지만 왜 우리는 행동가치함수를 추정해야 할까?

행동가치함수는, 특정 상태에서 행동을 선택할 때 많은 도움이 된다.

 

 

 

 

만약 우리가 확정적(deterministic) 정책을 사용하고, 위와 같이 한번도 선택하지 않은 행동이 있다고 가정해보자.

이러한 상황에서 에이전트는 이 행동들에 대한 정확한 가치를 추정할 수 없다.

따라서 이를 위해서 에이전트는 모든 상태에 대한 충분한 탐색이 필요하다.

 

예제)

 

 

현실에서의 예를 들어보자.

우리가 집에 가는 길이고, 최근에 새로 지어진 길이 있다.

우리는 실제로 가보기 전까지는 이 길이 얼마나 빠른지 절대 알 수 없다.

 

탐색적인 시작 (Exploring Starts)

탐색 문제를 해결하기 위한 한가지 방법은, 랜덤한 시작점에서 랜덤한 행동을 선택으로 시작하는 것이다.

 

 

 

위의 그리드월드에서 정책 $\pi$가 있다면, 우리는 랜덤한 시작점에서 첫 행동을 정책을 따라 하지 않는 것이다.

랜덤한 첫 상태에서 랜덤한 행동을 고른 이후에는 정책을 따라 목표지점까지 도달한다.

이는 확정적 정책에서 유용하다. (확률적 정책에서는 $\epsilon$-Greedy 를 활용하면 된다)

 

일반화된 정책 반복 (Generalized Policy Iteration)

일반화된 정책 반복에서는, 먼저 에이전트가 이전보다 나은 정책을 만들고,

탐욕적 선택을 통해 정책 향상을 한다는 것을 기억하자.

몬테카를로 기법을 사용하면, 이 과정속에서 평가 과정이 몬테카를로 기법을 통해 이뤄지게 된다.

 

다음은 몬테카를로를 활용한 일반화된 정책 반복 알고리즘이다:

 

 

먼저 랜덤한 시작점에서 상태와 행동을 선택한다.

그리고 해당 시작점 이후로부터 정책 $\pi$를 따라 에피소드를 진행한다.

에피소드를 통해 모든 결과값이 모아지면, 결과값들의 평균을 통해 행동가치함수를 추정하고,

탐욕적인 행동가치 선택을 통해 정책을 업데이트 한다.

이를 정책이 최적 정책이 될 때까지 반복한다.

 

이 과정은 다이나믹 프로그래밍에서보다 많이 간소해진 것을 볼 수있다.

우리는 행동가치를 추정하기 위해서 평균만 취하면 되기 때문이다.