하쿠's 강화학습 :: [Ch. V] Monte Carlo Methods

포스팅에 앞서 이 게시글은 Reference의 contents를 review하는 글임을 밝힌다.

 

 

 

 

「Monte Carlo Method(몬테카를로 방법)」

이번 포스트의 주제는 'Monte Carlo Method(몬테카를로 방법, 이하 MC)'이다.

 

앞선 포스트에서 살펴보았듯, 강화학습의 문제를 제공되는 정보의 양을 기준으로 그 해결법에 대해 2가지 분류를 했었다.

 - 환경정보에 대해 완벽히 안다(Model Based) = Dynamic Programming(DP) = Planning
 - 환경정보에 대해 일부만 안다(Model Free) = Reinforcement Learning(RL) = Learning

 

앞서 알아본 DP는 정보를 온전히 다 안다는 전제하에 계획을 세우는 계획법(Planning)으로서 분류가 되었던 반면,
이번에 알아볼 MC는 정보를 불충분하게 안 상태에서 얻은 정보로 최적의 정책을 배워나가는 학습법(Learning)의 한 종류이다.

 

Learning 방식의 솔루션은 완벽한 정보를 기반으로하지 않기 때문에 완벽한 최적의 정책을 찾을 순 없지만,
현실에서의 발생하는 문제에 대한 정보 수집의 한계가 있기때문에 실전에서 DP보다 더욱이 적합한 방법이라고 할 수 있다.

 

또한, 이전까지 알아본 Planning(계획법)에서는 'Evaluation(평가)'과 Improvement(개선)라는 표현을 사용하였으나,
Learning(학습법)은 'Prediction(예측)'과 Control(제어)이라는 표현을 사용한다.

이는 역시, 완벽한 정보를 활용하여 최적의 정책을 구성하는 Planning과 달리, Learning의 경우 최적일 것이라 추측하는 방식으로 갱신을 해나가는 입장이기 때문에 이러한 표현을 쓰지않을까 하는 생각을 했다. 또한, 개선과 제어의 표현 차이 역시, 같은 맥락이라고 생각된다(사견).

 

돌아와서, MC는 문제해결에 있어 경험(에피소드)들의 반환값의 평균을 기준값으로 사용한다.

반환값에 대한 연산을 수월하게 진행하기위해, Episodic Task과제를 중심으로 알아볼 예정이다.
뒤에서 보다 상세히 설명하겠지만, MC방식자체가 반환값 즉, 에피소드가 종료된 상태에서 종합된 총보상을 기준으로 가치함수와 정책에 대한 연산을 진행해나가기 때문에, 종결되지 않는 경우도 존재하는 Continuous Task의 경우에는 적용이 어렵기 때문이다.

이러한 특징으로 알 수 있듯이, MC방식은 에피소드단위의 증분형태 Learning 방식이며, 실시간 업데이트(Step-by-Step Update)가 아니다.

 

또한 MC의 Sample(에피소드=경험)과 행동가치함숫값은 MAB의 Sample과 행동가치함숫값과 매우 유사하다.
차이점은 단지 MC는 앞서 다루었던 '연관적 과제(Associative Search = Context Bandits)'라는 점이다.

MC는 특정 시점의 행동에 대한 연산이 추후 종결될 때까지 선택된 행동들을 통해 영향을 받기 때문에 이러한 점에서 연관적 과제라고 하는 것이다.

 

추가적으로, 위에서 말한 '특정시점'의 이후 절차는 불확실하다.
이 말은 확립된 절차(Constant=Optimal)가 아닌 이후에 대해 알 수 없는 절차(Variable)라는 이야기인데,

학습을 위해, 이전에 배운 DP에서는 이러한 불확실성을 완벽한 제거(For Optimality)하기 위해, 완벽한 정보를 가지고 GPI방식을 활용했다면 이번에 배울 MC에서는 이러한 불확실성을 부분적 제거(For Approximation to Optimality)하기위해 지엽적 정보(Sample)을 가지고 GPI방식을 통해 학습한다.

 

결론적으로 요약하자면, DP가 그러했듯, MC 역시 가치함수평가 → 정책 개선 → 정책기반제어의 매커니즘(GPI)은 동일하다. 단지, 학습에 대한 정보가 제한적이라는 차이가 있을 뿐이다.

 

 

 

 

「Monte Carlo Prediction(몬테카를로 예측)」

'Monte Carlo Method(몬테카를로 방법)'은 주로 수학이나, 물리학에서 '난수를 이용하여 함수의 값을 확률적으로 계산하는 알고리즘'을 말한다.

 

예를 들어, 주사위 '6'이 나올 확률을 수학적으로 모른다는 가정하에 수많은 시행 뒤에 '숫자 '6'이 나온 횟수 / 전체 시행횟수'를 계산하여 주사위 눈 '6'에 대한 수학적 확률의 근사치를 구할 수 있게 되는데, 이러한 방식이 바로 MC방법이다(대수의 법칙을 활용한 방법).

 

이를 가지고 강화학습에서 예측(Prediction)을 위한 MC방법의 적용에 대해 알아보도록 하겠다(기준은 상태가치함수이다).

 

이전 장에서 평가의 기준이 되는 보상은 'Expected Return(기대된 보상)'이라고 하는 최적의 반환값이었다.
MC를 활용하여 가치함수를 계산(예측)하는 것은 '여러 에피소드(경험)를 통해 평가 대상이 되는 상태에서의 반환값들의 평균치를 계산하는 것'이다.

 

이러한 방식은 해당 상태를 도달한 횟수가 많아질수록 즉, 에피소드(시행)이 많아질수록 예측이 최적해에 수렴한다는 특징을 가진다. MC예측은 이렇게 반환값을 계산하여, 추후 개선을 위한 정책 개선에 사용될 값을 준비한다.

 

그렇다면, 여기서 의문점이 하나 생기게 된다. 반환값은 결국 에피소드가 종결된 이후에 나타나는 것인데, 중간에 여러번 방문하는 지점에 대해서는 어떻게 처리할 것인가? 라는 의문이 생길 수 있다.

 

그렇다. 방문횟수에 따라 다르게 연산을 다르게 처리한다.
이에 대한 설명에 앞서 우리는 어떤 상태에 도달하는 것을 'Visit(방문)'이라고 표현할 것이다.

 

방문 횟수에 따라 나눈 연산방식에는 2가지가 존재한다.
1) First-visit Monte Carlo Method(이하 FVMC)
2) Every-visit Monte Carlo Method(이하 EVMC)

 

이름에서도 알 수 있듯, 1번의 경우에는 '첫번째 방문시에 산출된 가치함숫값만을 연산의 대상으로 삼는 방법'이고,
2번은 '매 방문마다 산출된 가치함숫값을 연산의 대상으로 삼는 방법'이다.

결론부터 말하자면, 현재 널리 논의되는 방식은 주로 FVMC방식이고, EVMC방식에 대한 활용은 이후 포스트에서 살펴볼 예정이다.

 

여기서 주의할 점이 있다. 분명 여지껏 설명은 FVMC방식에 대한 설명이었으나, 책에서 제시한 알고리즘의 의사코드 구조는 FVMC는 물론 EVMC도 아닌, 'Last-visit Monte Carlo Method(이하 LVMC)'이다.

 

Last-visit Monte Carlo Method Prediction(≒Evaluation)

 

방문에 대한 처리방식을 떠나서 기본적으로 Monte Carlo 방법은 대수의 법칙에 의해 경험한 에피소드의 수가 많아질수록 모두 최적의 값으로 수렴한다.

 

 

 

 

「Monte Carlo Q-value Estimation(몬테카를로 방식의 행동가치함수 평가)」

모델에 대해 불완전한 정보를 가지고 있을 시에는 행동가치함수(Q-value)를 활용하는 것이 유용하다.

이는 정확한 정보가 없기 때문에, 임의의 정책에 따라 평가된 상태가치함숫값에 의해 우수한 행동가치함숫값을 가진 행동에 대한 평가가 절하될 가능성이 있기 때문이다.

아래의 그림을 보자.

 

Safe path(안전경로) & Optimal path(최적경로)

 

그림은 추후에 배울 알고리즘들을 활용하여 Grid World에서의 최적경로를 산출한 것이다.

A 알고리즘은 상태가치함숫값을 기준으로 정책을 구성하고, 이에 대한 결과는 'Safe path'로 나타났다.
B 알고리즘은 행동가치함숫값을 기준으로 정책을 구성하고, 이에 대한 결과는 'Optimal path'로 나타났다.

분명, Optimal path가 목표에 도달함에 있어서 Safe path보다 더 적은 비용이 소요된다.

 

하지만 상태가치함숫값을 기준(A 알고리즘 방식)으로 연산할 경우, 이러한 정책을 구성할 수 없게되는데, 이는 Optimal path의 상태들이 Cliff(Hazard=Task Fail)에 근접해있기때문에 해당 상태로 빠질 위험이 있는 행동의 가치함숫값이 상태가치함숫값을 끌어내리기 때문이다.

 

이러한 연유로, 우리는 MC에서의 주 목표중 하나는 '정확한 Q-value(행동가치함수)를 찾는 일'이다
(추가적으로 환경에 대한 완벽한 정보가 없기에 상태가치함숫값을 계산하는 것은 Noise(노이즈)가 상당히 많다).

 

하지만 아이러니하게도, MC의 문제점은 Q-value를 활용하는데서 발생하는데, 이것은 '다수의 상태-행동 쌍이 방문되지않을 수 있다는 점'이다.

기본적으로 Q-value를 활용한 학습의 목적은 '각 상태에서의 최적 행동을 선택하기위한 토대마련'인데,
최적의 행동은 시점마다 다를 수 있고, Q-value기반 갱신작업의 맹점인 'Local Optimum(경험부재로 인해 학습이 되지않을 경우)'에 빠질 경우, 이러한 목표(Global Optimum)를 달성할 수 없기 때문이다.

 

이것은 MAB 포스트에서 살펴보았던 '탐험-이용 알고리즘'이 등장하게된 계기이며, 해당 알고리즘을 통하여 최소한의 탐험성을 유지해 미지의 Global Optimum을 찾아가야한다는 내용이였다.

 

그렇다면 이러한 탐험에 대한 보장을 어떻게할 수 있을까?
MAB에서는 'Optimistic initial values(바람직한 초깃값)'이라는 테크닉을 사용하여 학습에 대해 도움을 받을 수 있는 시작상태를 세팅할 수 있었다.

 

반면, 이러한 방법은 동적환경에서는 잘 들어맞지않는다고 했었는데, Learning 환경에서는 정보가 불완전하기 때문에 이러한 Planning의 테크닉은 활용할 수 없다.

 

다만 MC에서는 'Exploring Start(탐험적 시작)'라는 테크닉을 사용할 수 있는데, 무작위의 상태에서 Task Start를 함으로써 경험해보지 못한 상태-행동 쌍(Q-value)를 줄여나가는 방법이다.

이 방법은 때로는 유용하지만, 얻어진 정보에 대해 시시각각변하는 동적환경(실시간 상호작용)에서는 잘 들어맞지 않는다.

 

결국 더 나은 대안을 찾게되는데, 이는 '모든 상태-행동 쌍(Q-value)에 대해 '0'이 아닌 확률적 정책을 구성하는 방법'이다.

 

 

 

 

「Monte Carlo Control with Exploring Starts(탐험시작기반 몬테카를로 제어, 미완성 MC제어)」

MC제어는 GPI의 원리와 같은 패턴을 띈다.

 

Generalized Policy Iteration(GPI)

GPI의 진행과정(Policy by Q-value)

 

여기서 우리는 잠시동안 MC방법에 의한 제어가 효과적이기 위한 2가지 가정을 전제하에 프로세스를 진행해보겠다.
1) 탐험시작(Exploring Start, 이하 ES) 추정
2) 무한번에 가까운 시행(에피소드)

 

위 전제를 기반으로 MC제어를 구성할 시, 임의의 정책에서 평가를 통한 행동가치함수를 파악, 이후 이를 기반으로 새 정책구성(이는 곧 GPI의 원리)이 가능하며, 이는 완벽한 모델 없이(Model Free) 경험(Sample)만으로 Greedy(그리디, ≒ Oplimal) 정책의 구성을 한 것이다.

 

이번엔 실적용을 위해 사전 2가지의 가정을 없애보겠다.

1번가정은 잠시 보류하고 2번가정부터 살펴보자면,
2번가정에 대한 해결책은 2가지로 나뉜다.

 

첫번째 해결책은 '완벽히 계산해보자!'는 취지의 방식인데, 측정과 추정 모두 바운드의 차이와 에러의 확률을 계산하여 얻고 충분한 단계스텝을 거쳐 이러한 간극을 충분히 좁히는 방식이다.

이러한 방식은 실질적으로 연산에 충분히 많은 에피소드를 요구한다.

 

따라서, 두번째 해결책으로는 현실적으로 우리가 완벽하다고 생각하는 평가값이 나오기 전에 평가작업을 중단하는 것이다. 이러한 방식의 극단적 형태가 DP에서 배운 'Value Iteration 알고리즘'인데, 한번의 평가로 최적행동을 구해 그것을 중심으로 개선하는 방법이다.

 

GPI방식의 순서에 따라 우선적으로 MC 방식의 평가와 개선을 위해서는 아래와 같은 절차를 거친다.

 

Monte Carlo with Exploring Starts

 

책에서는 이 부분을 MC 방식의 평가에 대한 부분이라고 설명하였으나, 실질적으로 맨 아래쪽 코드를 보면 행동가치함숫값과 정책을 수정함으로써 개선(Update) 역시 행하는 것으로 보인다.

또한, Unless절 이후의 알고리즘들은 자세히 보면 역순으로 진행해나가며 반환값 배열(리스트)에 기록되지않은 상태일 경우에만 개선을 하는데, 이는 FVMC도 EVMC도 아닌 Last-visit Monte Carlo(LVMC)라고 할 수 있다.

 

이러한 부분들을 인지하고 다시 의사코드를 보면, MC는 에피소드 단위의 평가와 개선의 반복을 기반으로 하는데,
반환값에 대한 보다 정확한 연산을 하기위해서이다.

에피소드 종결 후, 반환값을 가지고 지나온 상태들에 있었던 행동들에 대한 가치평가(Q-value)를 하고, 이후 이에 대한 개선을 한다.

 

이런식으로의 진행은 결국 가치함수가 특정 정책에 발이 묶이지 않고 평가되며, 이를 따르는 정책 역시 Local Optimum에 빠지지 않고 Global Optimum으로 수렴하게된다.

 

 

 

 

「On-Policy vs Off-Policy, On-Policy Monte Carlo Control(온폴리시 몬테카를로 제어, 완성 MC제어)」

효과적인 MC제어를 위한 2가지 가정으로 아래와 같은 조건들이 있었는데,

1) 탐험시작(Exploring Start) 추정
2) 무한번에 가까운 시행(에피소드)

 

앞서 전제한 가정을 다시 살펴보면, MC제어가 효과를 보기위한 2가지 조건 중 '무한번에 가까운 시행'은 Q-value를 활용함으로써 현실적용에 보다 한발짝 다가갔다.

 

남은 가정은 '탐험 시작(Exploring Start) 추정'인데, 이 가정의 핵심은 결국 '탐험성 확보를 통한 Global Optimum 수렴'에 있다.

 

그러나 현실적인 상황(동적환경)에서는 이러한 방법 적용에 어려움이 있다고 하였는데, 이를 제거하면 비로소 'MC원리를 이용한 완전한 제어방법'이라고 할 수 있다.

 

따라서 이것을 위해 등장하는 개념이 'On-Policy'와 'Off-Policy'이다.
우선 이 개념들에 대한 설명에 앞서 '행동 정책'과 '목표 정책'에 대해 이야기하고 넘어가려한다.

 

'행동 정책(Behavior Policy)'란?
행동 선택에 사용되는 정책(학습데이터=경험 발생정책)을 말하며, 탐험성을 유지하기 위해 고안된 정책이다.

'목표 정책(Target Policy)'란?
학습하는 정책(학습대상 정책)을 말하며, 우리가 계속해서 개선해나갈 대상이되는 정책이다.

 

이제 이를 숙지하고 On-Policy와 Off-Policy에 대해 알아보자.

On-Policy(이하 온폴리시) 방법 - Behavior Policy = Target Policy
Off-Policy(이하 오프폴리시) 방법 - Behavior Policy ≠ Target Policy

 

On-Policy MC제어는 기본적으로 GPI의 아이디어에 기반을 두는데, E(Epsilon)-greedy 알고리즘을 사용함으로써, 
ES없이 탐험해보지 못한 행동가치값에 대한 평가와 개선을 반복하여 최적화한다
(Greedy 알고리즘을 사용할 경우, 초기정책에 묶여 탐험이 불가하기 때문).

 

이러한 On-Policy MC의 경우, 학습데이터가 되는 경험(Sample)이 결국 현재 지향하는 정책에 의해 생성되기 때문에,
분산(Variance)이 작아 빠른 수렴을 통해 학습을 좀 더 수월하게 진행할 수 있는 장점이 있지만, 점차 탐험성이 줄어들 수 밖에 없게되고, 이러한 편향(Bias)이 Local Optimum에 빠지게할 가능성이 있다.

앞서 계속해서 이야기한 MC Prediction이 바로 On-Policy방식의 MC Prediction이었다.

 

아래는 On-Policy Monte Carlo Control에 대한 의사코드이다(이 부분 역시 LVMC방법으로 구현되어있다).

 

On-Policy Monte Carlo Control(Last-visit)

 

 

 

 

 

「Off-Policy Monte Carlo Prediction(오프폴리시 몬테카를로 예측)」

줄곧 이야기했던 강화학습의 행동선택에 있어서 Dilema(딜레마)는 결국 '탐험과 이용사이 갈등'이었다.

 

이에 대한 On-Policy MC Prediction의 타협점은 "학습에 간편함을 얻는 대신, 최적에 근접한 근사정책을 찾는 것"이었다. 초기에는 탐험을 통해 빠르게 보다 나은 정책을 구성할 수 있지만, 시간이 갈수록 행동 선택에 있어 현재 지향하고있는 정책에 발이 묶여, 종국에는 Local Optimum에 빠질 가능성이 있다고 했다.

 

이를 해결하기 위해, 조금 시간과 노력이 걸리더라도 'Global Optimum을 찾기위해 탐험에 대한 좀 더 확실한 보장을 하는 방법'이 'Off-Policy MC Prediction'이다.

 

'Off-Policy'는 Sample 행동을 선택함에 있어서 Target Policy의 기능을 Off했다고 해서 'Off-Policy(오프폴리시)'라고 불린다(On-Policy 역시, 같은 원리로 이름붙여졌다).

 

이러한 Off-Policy MC Prediction은 학습데이터가 되는 경험(Sample)이 Behavior Policy에 의해 생성되고, 이 Sample을 가지고 Target Policy를 평가한다.

따라서, 이후 Target Policy는 탐험성을 유지한 채 지속적인 개선이 가능해 결국 Global Optimum을 얻을 수 있게된다.
앞서 ES를 대체할 대안으로 지목된 '모든 상태-행동 쌍(Q-value)에 대해 '0'이 아닌 확률적 정책을 구성하는 방법'이 바로 Bahavior Policy를 구성하는 것이다.

 

하지만, 이러한 Off-Policy MC Prediction은 On-Policy MC Prediction보다 많은 경험이 필요하고  비교적 편향(Bias)은 작지만 분산(Variance)이 크기때문에 학습시간도 오래걸린다.

 

하지만, 이러한 부분들은 치명적인 단점으로 볼 수 없기때문에, 오프폴리시 방식은 좀 더 일반적으로 많이 사용되고 그 효과가 강력하다.

 

 

 

 

「Off-Policy Monte Carlo Prediction에 대한 깊은 이해, Importance Sampling(중요도 샘플링)」

지금부터 오프폴리시 MC예측에 대해서 더 깊게 이해하기위해 필요한 'Importance Sampling(중요도 샘플링)' 개념을 설명할 것이다.

설명에 앞서 이번 절에서는 오프폴리시 MC예측에 대한 내용을 다룰 때, 목표 정책과 행동 정책에 대한 값 변화(갱신)이 없이 고정된 상수로 간주하고 설명을 이어나가도록 하겠다.

 

오프폴리시 MC예측의 매커니즘적 핵심은,

행동 정책을 활용하여, 목표 정책을 평가한다는 것.
즉, 목표 정책에 의한 최적행동이 있어도 기타의 다른 행동을 취하여 더 나은 행동가치값을 탐색하려는 의도를 가진다는 것이다.

이는 ‘Assumtion of Coverage(탐색의 가정)’이라고 한다.

 

이는 행동 정책은 곧 확률적이여야하며, 탐색에 목적을 둔 정책이라는 뜻이 된다.
반면, 목표 정책은 결정적이여야하며, 결정된 값을 가지고 목표를 위한 제어에 목적을 둔 정책이라는 뜻이다.

기본적으로 이렇게 두 가지의 정책이 공존하며 최적의 정책을 찾아내는 방식이 오프폴리시 방식인데,
이러한 오프폴리시 방식을 활용한 MC예측의 특징 중 하나가 ‘Importance Sampling(중요도 샘플링)’이다.

 

중요도 샘플링은 통계학에서 조사의 대상이 되는 모집단의 분포(확률분포)를 알고싶으나, 해당 확률변수 X가 소속된 집합 A크기가 작아 샘플링이 어려울 때, 외부 확률분포의 표본을 가지고 기댓값을 추정하는 기법인데, 방법은 대상 확률분포를 외부확률분포로 나눈 값이다.

 

여기서는 연산의 대상이 되는 값이 각 정책의 ‘Trajectory(궤적)’이다.

 

잠깐 용어 ‘Trajectory’에 대해 설명하고 넘어가자면, 주로 물리학에서 쓰는 용어로 탄도, 궤적 등의 어떠한 물체의 운동에 의해 순차적으로 생성되는 기록을 말하는데,

여기서는 '에피소드의 종결시까지 거쳐온 상태와 행동에 대한 일련의 과정'을 말한다.
(Trajectory = S0, A0, R1, S1, A1, R2, S2, A2, R3, ... , Rn-1, Sn-1, An-1, Rn, Sn)

 

돌아와서, 대상이 되는 목표정책의 확률을 구하기위해 행동정책의 확률의 표본(Sample)을 빌려다쓰는 방식인데,
에피소드 내의 Trajectory의 확률분포에 대한 수식을 나타내면 아래와 같이 표현할 수 있다.

 

Trajectorcy의 확률분포

 

위와 같은 원리로 목표 정책과 행동정책에 의한 에피소드내의 Trajectory 확률을 표현할 수 있는데,
목표정책에 대한 값을 행동정책에 대한 값으로 나누어주면 아래와 같은 식이 된다.

 

Importance Sampling Ratio(중요도 샘플링 비율)

 

이러한 식의 결과를 'Importance Sampling Ratio(중요도 샘플링 비율)'이라고하는데, 해당 Trajectory가 얼마나 중요했는가(최적의 정책에 근접)에 대한 수치이다.

 

이 결과는 '배수(Multiply Factor)'로 취급하며, 어떠한 행동이 목표 정책에서 갖는 중요성을 나타내는 지표라고 생각하면된다.

 

다소 생소할 수 있는 중요도 샘플링 개념은 다음과 같은 이유때문에 중요한데,

우리의 목표는 목표 정책(최적)을 통한 Expected Return(최적의 반환값)을 예측하는 것이지만, 우리가 가진 것은 오로지 행동 정책에 의한 행동으로 얻어진 반환값 뿐이기 때문에, 이를 기반으로 최적의 정책과 가치함수를 찾을 때 정확한 평가를 기반으로 하기위해서 중요도 샘플링을 한다고 생각하면 된다.

 

 

 

 

「Importance Sampling의 종류」

중요도 샘플링에는 여러가지 방식이 존재하는데, 여기서 알아볼 방법은 2가지이다.

 

1) Ordinary Importance Sampling(이하 보통 중요도 샘플링)
2) Weighted Importance Sampling(이하 가중 중요도 샘플링)

 

이 둘의 차이는 편향(Bias)과 분산(Variance)로 구분이 가능한데,

보통 중요도 샘플링의 식은 다음과 같다.

 

Ordinary Importance Sampling

 

특정 한 에피소드(Trajectory) 내에서 연산을 진행할 때, 분자는 각 상태에 대해 방문한 시점에서의 각각의 반환값과 중요도 비율의 곱을 모두 합한 값이고, 분모는 해당 상태에 방문한 횟수이다(FVMC는 1번, EVMC는 n번).

 

즉, 이것은 방문 당 해당 상태의 평균의 중요도 비율 값으로서, 가중치된 반환값(비율)을 결과로 뱉는다.
따라서, 이는 편향(Bias)되지 않는다.

다만, 분산(Variance)의 측면에서는 비율 값에 대한 분산은 일반적으로 제한이 없기에 분산이 높을 수 있다.

 

반면, 가중 중요도 샘플링의 식은 다음과 같은데,

 

Weighted Importance Sampling

 

분자는 이전과 같고, 분모는 중요도비율의 곱을 해당상태에 방문한 횟수만큼 더한 값이다.

 

이는 소거하면 해당시점의 반환값만 나오는데, 이는 결국 행동정책에 의해 얻어진 하나의 샘플이기에 편향적(Biased)이다. 하지만, 분산(Variance)의 측면에서는 최고의 가중치를 가진 값은 하나이기에(최적의 반환값을 갖는 Trajectory는 하나이기 때문에), 분산은 ‘0’으로 수렴하는 형태이다(분산이 작다).

 

일반적으로는 분산이 작다는 이유로 가중 중요도 샘플링 방식을 선호하지만,
추후 있을 포스트에서의 개념설명 때문에 보통 중요도 샘플링 방식 역시 알아두어야한다.

 

다음 그래프는 게임 '블랙잭'의 게임내 가질 수 있는 상태들을 기준으로 2가지 중요도 샘플링을 통한 Off-Policy MC Prediction의 성능을 비교한 것이다.

 

Ordinary Importance Sampling vs Weighted Importance Sampling

 

 

 

 

「증분식 형태의 Monte Carlo Method」

이전 MAB에서 다뤘던 증분형태의 방식을 MC에서도 사용가능한데,

MAB에서 즉각보상을 평균화했다면, MC에서는 반환값을 평균화한다는 점이 차이점이다
(MC는 연관적 과제이기 때문).

 

Off-Policy MC의 경우,
보통 중요도 샘플링과 가중 중요도 샘플링 방식을 구분지어 고려해야한다.

 

Ordinary Importance Sampling의 경우,
MAB에서 사용한 증분식을 그대로 사용하고 연산의 대상이 되는 값만 보상에서 반환값으로 바꾸어주면 된다.

 

반면, Weighted Importance Sampling의 경우,
우선, 가치함수에 대한 식은 다음과 같다.

가중 중요도 샘플링에서의 가치함수

여러 시행(에피소드)통해서 특정 상태에서의 반환값과 그 상태의 가중치를 곱한 값을 모두 더하여 그 상태의 가중치만 모두 더한 값으로 나누면 평균화된 상태가치가 나온다.

 

이러한 상태가치를 유지함과 더불어 ‘Cumulative weight Sum(축적된 가중치 합계)’라는 값을 유지해야하는데,
이는 각 상태별로 여러 시행(에피소드)을 거치며 n번째 시행을 거칠 때까지 해당 상태에서 각 시행당 첫번째로 얻어진 가중치들의 합이다.

식은 아래와 같다.

 

가중 중요도 샘플링을 통해 얻는 상태가치 증분식

축적된 가중치 합계

 

이는 상태가치에 반환값과 가치함숫값의 차이(Error)의 가중치에 해당 시행(에피소드)에서 가중치 값을 조정해주는 역할을 하여 증분식을 지원하는 방식으로 사용된다.

 

돌아와서, 오프폴리시는 2개의 정책을 각기 다른 역할을 수행하게하여 Global Optimum으로 나아갈 수 있게하는 방법이며, 이때, 중요도 샘플링을 통해 이러한 결과를 이끌어낼 수 있는 것이다.

 

아래는 이러한 원리들을 적용한 Off-Policy Monte Carlo Control에 대한 의사코드이다
(이 부분은 EVMC방법으로 구현되어있다).

 

Off-Policy Monte Carlo Control(Every-visit)

 

가중 중요도 샘플링방법을 사용했고, Behavior Policy=Target Policy라는 전제가 깔리게 되면 온폴리시 MC평가로도 가능하다.

 

 

 

 

「On-Policy vs Off-Policy, Off-Policy Monte Carlo Control(오프폴리시 몬테카를로 제어, 완성 MC제어)」

온폴리시 MC제어는 GPI의 원리를 따른다고 하였다.

오프폴리스 MC제어 역시, 기본적으로 GPI의 아이디어가 기저에 깔려있다.
이에 추가적으로, 최적의 행동가치함숫값과 최적의 정책을 평가하기 위한 가중 중요도 샘플링을 구현한다.

 

이에 대한 의사코드는 아래와 같다.

 

Off-Policy Monte

 

오프폴리시 MC제어의 문제점은 Goal State 근처에서만 비교적 효율적으로 학습한다는 점이다.

 

MC는 기본적으로 소프트한(Non-greedy) 행동 정책을 활용하여 데이터 수집을 진행해나가며 해당 에피소드 종결 후,
반환값을 기준으로 평가와 개선을 해나가는 방식인데,

목표 달성(종결)이전에 무한히 많은 에피소드가 소모되는 경우, 같은 상태만을 맴도는 경우 혹은 환경이 종료되는 경우와 같이 종결되지 않을 수 있다. 이런 경우들은 충분한 경험 부족으로 이어져 학습에 차질이 생긴다.

 

이것이 필수적으로 에피소드 기반(에피소드가 종결되어야 하는 성질)이어야하는 Monte Carlo 방법의 치명적 결함이다.

 

이 부분에 대한 사견은 이 문제가 MC 자체의 한계적 결함이라고 생각된다.

온폴리시의 경우에도 그리디 정책 기반의 행동 선택을 통해 수렴이 가속화되어 사정이 좀 더 나을 수 있지만,
결론적으로 Local Optimum에 빠질 확률이 커진다는 부분에서 완전한 대안이라고할 수 없기 때문이다.

 

따라서 이를 해결하기위해, 종결되지않아도 곧바로 평가와 개선을 해 나갈 수 있는 방식(Step by Step Method)이 등장하게 되는데, 이것이 다음 포스트에서 다룰 'Temporal-Difference Error(TD에러) 알고리즘'이다.

 

 

 

 

「마무리」

오늘 알아본 Monte Carlo 방법은 경험(Sample)을 통해 학습해 환경정보가 불완전한 경우(Model Free)에서도 문제를 풀 수 있는 방법이다.

 

MC는 DP에 비해 4가지 측면에서 우수한데,

1) 정보의 불완전성 타개
 - 완벽한 환경정보 없이도 문제를 풀 수 있다는 점에서 현실 강화학습 문제에 적합하다고할 수 있다.
2) 샘플링을 통한 방식을 사용함으로써 모델 구축 용이
 - DP는 초기에 정보를 가지고 완벽하고 복잡한 모델을 구축해야하는 반면,
 - MC는 샘플링을 통해 모델을 구축해나가는 방식이라, 복잡한 구조의 모델도 DP보다 쉽게 구현가능
 - 이는 어떠한 물건을 만들어냄에 있어 조각의 방식(DP)와 주조의 방식(MC)의 차이라고 이해하면 쉽게 와닿음
3) 지엽적인 부분에 효율적이고 적용이 수월
 - 1번과 비슷한 이유인데, 원하는 지엽적인 부분에 대한 모델을 뽑을 때, 보다 쉽고 효율적이다.
 - 모든 상태에 대한 탐색없이도, 원하는 부분에 대한 솔루션을 찾을 수 있다.
4) 부트스트래핑(Bootstraping) 사용 안함
 - DP는 평가 및 개선을 진행함에 있어 이전 평가에 의존한 추정가치를 사용하지만(Bootstrap방식),
 - MC는 그때그때의 샘플을 기반으로 실제 가치를 활용하기 때문에,
 - 편향(Bias)는 줄고, 분산(Variance)는 증가한다고 볼 수 있다.

 

Monte Carlo가 가지는 한계는 반드시 '에피소드 기반의 과제'여야 한다는 점이다.
따라서 이러한 조건 없이도 활용할 수 있는 'Temporal Difference Error(TD에러) 알고리즘'에 대해 알아볼 것이다. 

 

 

 

 

「참고」

Reinforcement Learning, Second Edition : An Introduction
Richard S. Sutton and Andrew G. Barto

https://mitpress.mit.edu/books/reinforcement-learning-second-edition

Reinforcement Learning, Second Edition