다이나믹 프로그래밍에서는 모델을 알고 있다(Model Based)는 전제하에서 정책을 평가하고 제어했다. 모델을 알고 있는 상태에서는 다음 상태를 알 수 있기 때문에 문제를 작은 단위로 나누어서 순차적으로 계산해서 최적의 정책을 찾을 수 있었다.
하지만 모델을 알지 못하는 상태(Model Free)에서는 보상 함수(R: Reward Function)와 상태전이확률(P: State Transition Probability)을 알 수 없고, 특히 다음 상태가 무엇인지 알 수 없기 때문에 다이나믹 프로그래밍 같은 문제 해결 방법을 사용할 수 없다. 이때 필요한 것이 몬테카를로(Monte-Carlo Prediction) 예측이다.
다이나믹 프로그래밍은 전체 상태를 한 번씩 모두 실행하면서 각 상태(State)의 가치를 업데이트 했지만, 몬테카를로 예측에서는 하나의 에피소드가 끝날 때까지 실행하면서 경험을 모으고 그 경험으로부터 가치함수를 계산한다.
환경에 대한 정보가 충분하지 않기 때문에 많이 사용하는 방법 중에 하나가 바로 몬테카를로 방법(MC: Monte-Carlo Method)이다. 몬테카를로 방법은 정확한 수학 수식에 의해 계산하거나 측정하는 것이 아니라 확률적인 방법에 의해 값을 통계적으로 계산하는 방법이다. 계산하려는 값이 복잡할 때 정확한 결과를 얻기 보다는 근사적인 결과를 얻을 경우에 사용한다.
몬테카를로라는 이름은 이 방법을 개발한 폴란드계 미국인 수학자인 스타니스와프 울람이 모로코의 유명한 도박 도시 이름을 따온 데서 유래했다. 몬테카를로 방법은 컴퓨터로 계산하는 것에 적합하여 원자폭탄이나 수소폭탄 개발과 같은 컴퓨터 모의 실험에 사용되었으며 현재도 다양한 분야 활발히 응용되고 있다.
몬테카를로 방법
우리가 어떤 복잡한 다각형의 면적을 구해야 한다고 해보자. 수학적으로 식을 세워서 정확하게 계산하는 것도 가능하겠지만, 도형이 아주 복잡하다면 쉽지 않다. 이럴 때는 조금 더 직관적이고 간단한 방법으로 접근해볼 수 있다. 바로 몬테카를로 방법(Monte Carlo Method) 이다.
방법은 이렇다. 먼저 다각형을 완전히 감쌀 수 있는 정사각형을 하나 그린다. 가로와 세로의 길이가 1미터인 정사각형이라고 해보자. 이 사각형의 면적은 가로 × 세로니까 1㎡로 쉽게 계산된다.
이제 이 사각형 안에 무작위로 동그란 공을 던져 넣어보자. 예를 들어 총 30개의 공을 뿌렸는데, 그중 15개가 다각형 안에 들어갔다고 하자. 그렇다면 전체 공 중 절반이 다각형 안에 들어간 셈이므로, 우리는 이렇게 추정할 수 있다.
“다각형의 면적은 전체 정사각형 면적의 절반, 즉 0.5㎡ 정도 되겠구나.”
실제로 다각형의 면적을 직접 측정하지 않고, 무작위로 실험한 결과를 바탕으로 면적을 추정한 것이다. 이처럼 복잡한 문제를 직접 계산하지 않고 확률과 통계를 이용해 ‘대략적으로’ 구하는 방법이 바로 몬테카를로 방법이다.
강화학습에서도 이 방식이 유용하게 쓰인다. 에이전트가 어떤 환경에서 움직이는데, 그 환경에 대한 정보가 충분하지 않은 경우가 많다. 어떤 행동을 했을 때 다음에 어떤 일이 벌어질지, 보상을 받을지 말지도 알 수 없는 상황이다. 이럴 땐 정밀한 수식으로 계산하는 다이나믹 프로그래밍을 쓸 수 없다. 대신 몬테카를로 방법처럼 직접 행동해 보고 그 경험을 바탕으로 학습하는 방식이 효과적이다.
예를 들어 어떤 게임을 하는 에이전트를 생각해보자. 이 에이전트는 게임을 한 판 플레이하면서 경험을 쌓는다. 이 한 판을 우리는 ‘에피소드’라고 부른다. 에피소드가 끝나면, 에이전트는 자신이 어떤 상태에서 어떤 행동을 했고, 그 결과 어떤 보상을 받았는지 전체 흐름을 복기하면서 학습한다.
이때 중요한 조건이 있다. 몬테카를로 방법을 사용하려면, 반드시 에피소드가 있어야 한다. 다시 말해, 시작과 끝이 있는 구조여야 한다. 예를 들어 디아블로 같은 게임은 한 판이 시작되고 끝나기 때문에 몬테카를로 방법을 적용할 수 있다. 반면 리니지 같은 MMORPG 게임은 끝이 없이 계속 이어지므로, 에피소드가 없고 몬테카를로 방식이 적용되기 어렵다.
몬테카를로 방법에서는 에피소드를 끝까지 실행한 후, 그 결과를 바탕으로 가치 함수를 계산한다. 가치 함수란 쉽게 말해, 어떤 상태에서 출발했을 때 기대할 수 있는 보상의 총합이다. 만약 우리가 환경에 대해 모든 정보를 알고 있다면, 어떤 행동을 했을 때 어떤 상태로 가는지도 알고 있기 때문에 수식으로 계산할 수 있다. 이게 바로 다이나믹 프로그래밍 방식이다.
하지만 현실은 대부분 그렇지 않다. 다음 상태가 어디일지, 어떤 결과가 나올지 모를 경우에는 수식 계산이 어렵다. 그래서 실제로 에피소드를 수행하면서 나오는 경험을 바탕으로, 실제로 받은 보상을 합산하여 상태의 가치를 추정하게 된다.
물론 한 번의 에피소드만으로는 정확한 값을 얻기 어렵다. 하지만 에피소드를 수십 번, 수백 번 반복하게 되면, 각 상태의 가치에 대한 평균값이 점점 더 진짜 답에 가까워진다. 결국, 수많은 시행착오를 통해 얻어진 경험들이 누적되어 참 가치 함수에 근접하게 되는 것이다. 이 과정을 바로 몬테카를로 방법을 통한 학습이라고 부른다.
