Unlike the previous chapter, here we do not assume complete knowledge of the environment. Monte Carlo methods require only experience—sample sequences of states, actions, and rewards from actual or simulated interaction with an environment.
몬테카를로 방법은 sample return의 평균을 기반으로 강화 학습 문제를 해결하는 방법입니다. Well-defined return을 사용할 수 있도록 하기 위해, 여기서는 몬테카를로 방법을 episodic tasks에만 정의합니다. 즉, 경험이 에피소드로 나뉘고, 어떤 행동이 선택되든 모든 에피소드가 결국 종료된다고 가정합니다. 에피소드가 완료된 후에만 가치 추정치와 정책이 변경됩니다. 따라서 몬테카를로 방법은 step-by-step (online) 방식이 아닌 episode-by-episode 방식으로 incremental일 수 있습니다.
몬테카를로 방법은 각 상태-행동 쌍에 대한 반환을 샘플링하고 평균화합니다. The return after taking an action in one state depends on the actions taken in later states in the same episode. Because all the action selections are undergoing learning, the problem becomes nonstationary from the point of view of the earlier state.
Nonstationary를 처리하기 위해 4장에서 DP(Dynamic Programming)에 대해 개발된 일반 정책 반복(general policy iteration, GPI)의 아이디어를 적용합니다. 여기서는 MDP(Markov Decision Process)에 대한 지식으로부터 가치 함수를 계산했지만, 여기서는 MDP를 사용하여 샘플 반환값으로부터 가치 함수를 학습합니다. 가치 함수와 해당 정책은 여전히 본질적으로 동일한 방식(GPI)으로 상호 작용하여 최적성에 도달합니다.
특히, 정책 \pi를 따르고 s를 통과하여 얻은 에피소드 집합이 주어졌을 때 정책 \pi 하에서 상태 s의 값인 v_\pi(s)를 추정하고자 한다고 가정합니다. 에피소드에서 상태 s가 발생하는 각각의 경우를 s에 대한 방문이라고 합니다. 물론 s는 동일한 에피소드에서 여러 번 방문할 수 있습니다. 에피소드에서 처음 방문하는 시간을 s에 대한 첫 번째 방문이라고 합시다. First-visit MC 방법은 v_\pi(s)를 s에 대한 첫 번째 방문 후의 반환값의 평균으로 추정하는 반면, every-visit MC 방법은 s에 대한 모든 방문 후의 반환값을 평균합니다. 이 두 가지 Monte Carlo (MC) 방법은 매우 유사하지만 약간 다른 이론적 속성을 가지고 있습니다. First-visit MC는 1940년대부터 가장 널리 연구되었으며 이 장에서 우리가 집중하는 방법입니다. Every-visit MC는 9장과 12장에서 설명한 것처럼 함수 근사 및 eligibility traces로 보다 자연스럽게 확장됩니다. First-visit MC는 상자에 절차적 형태로 표시됩니다. Every-visit MC는 S_t가 에피소드에서 이전에 발생했는지에 대한 검사가 없다는 점을 제외하고는 동일합니다.
만약 모델을 사용할 수 없다면, 상태 값보다는 액션 값(상태-액션 쌍의 값)을 추정하는 것이 특히 유용합니다. 모델이 있다면, 상태 값만으로 정책을 결정하기에 충분합니다. DP 챕터에서 했던 것처럼, 한 단계 앞을 내다보고 보상과 다음 상태의 최상의 조합으로 이어지는 액션을 선택하면 됩니다. 그러나 모델이 없다면 상태 값만으로는 충분하지 않습니다. 정책을 제안하는 데 값이 유용하도록 각 액션의 값을 명시적으로 추정해야 합니다. 따라서 Monte Carlo 방법의 주요 목표 중 하나는 q^*를 추정하는 것입니다. 이를 달성하기 위해 먼저 액션 값에 대한 정책 평가 문제를 고려합니다.
액션 값에 대한 정책 평가 문제는 상태 s에서 시작하여 액션 a를 취하고 이후 정책 π를 따를 때의 기대 수익 q_π(s, a)를 추정하는 것입니다. 이를 위한 Monte Carlo 방법은 상태 값에 대해 방금 제시된 방법과 기본적으로 동일하지만, 이제는 상태가 아닌 상태-액션 쌍에 대한 방문에 대해 이야기합니다. 상태-액션 쌍 s, a는 상태 s가 방문되고 액션 a가 그 안에서 취해진다면 에피소드에서 방문되었다고 합니다. Every-visit MC 방법은 상태-액션 쌍의 값을 해당 쌍에 대한 모든 방문을 따른 수익의 평균으로 추정합니다. First-visit MC 방법은 각 에피소드에서 상태가 방문되고 액션이 선택된 첫 번째 시간 이후의 수익을 평균합니다. 이러한 방법은 이전과 마찬가지로 각 상태-액션 쌍에 대한 방문 횟수가 무한대에 가까워짐에 따라 실제 기대 값으로 이차적으로 수렴합니다.
유일한 복잡한 점은 많은 상태-액션 쌍이 방문되지 않을 수 있다는 것입니다. 만약 \pi가 결정론적 정책이라면, \pi를 따를 때 각 상태에서 하나의 액션에 대해서만 수익을 관찰할 수 있습니다. 평균할 수익이 없으면 다른 액션에 대한 Monte Carlo 추정치는 경험을 통해 개선되지 않습니다. 액션 값을 학습하는 목적은 각 상태에서 사용 가능한 액션 중에서 선택하는 데 도움을 주기 위한 것이기 때문에 이는 심각한 문제입니다. 대안을 비교하려면 현재 선호하는 액션뿐만 아니라 각 상태의 모든 액션 값을 추정해야 합니다.
이를 해결하는 한 가지 방법은 에피소드가 상태-액션 쌍에서 시작되고 모든 쌍이 시작으로 선택될 확률이 0이 아닌 것으로 지정하는 것입니다. 이는 무한한 수의 에피소드의 극한에서 모든 상태-액션 쌍이 무한 번 방문되도록 보장합니다. 이를 exploring starts 가정이라고 합니다. 이는 시뮬레이션이 아닌 실제 환경으로 학습할 때 불가하므로, 모든 상태-액션 쌍이 발생하도록 보장하는 가장 일반적인 대안적 접근 방식은 각 상태에서 모든 액션을 선택할 확률이 0이 아닌 확률적 정책만 고려하는 것입니다.
이제 몬테카를로 추정을 제어, 즉 최적 정책을 근사하는 데 사용하는 방법을 고려할 준비가 되었습니다. 전반적인 아이디어는 DP 챕터와 동일한 패턴, 즉 일반화된 정책 반복(generalized policy iteration) 아이디어에 따라 진행하는 것입니다. GPI에서는 근사 정책과 근사 가치 함수를 모두 유지합니다. 가치 함수는 현재 정책에 대한 가치 함수를 더 가깝게 근사하도록 반복적으로 변경되고, 정책은 오른쪽 다이어그램에서 제시된 바와 같이 현재 가치 함수에 대해 반복적으로 개선됩니다. 이러한 두 가지 종류의 변경은 어느 정도 서로 상충되며, 각각이 다른 하나에 대한 이동 목표를 생성하지만, 함께 정책과 가치 함수가 모두 최적성에 접근하도록 합니다.
정책 평가는 앞 절에서 설명한 대로 정확하게 수행됩니다. 많은 에피소드가 경험되고, 근사 행동-가치 함수가 점근적으로 참 함수에 접근합니다. 현재로서는 무한한 수의 에피소드를 실제로 관찰하고 에피소드가 exploring starts 로 생성된다고 가정해 보겠습니다. 이러한 가정 하에서 몬테카를로 방법은 임의의 q_πk 에 대해 각 π_k 를 정확하게 계산합니다.
정책 개선은 현재 가치 함수에 대해 정책을 greedy 하게 만드는 방식으로 수행됩니다. 이 경우 행동-가치 함수가 있으므로 greedy 정책을 구성하는 데 모델이 필요하지 않습니다. 임의의 행동-가치 함수 q에 대해 해당하는 greedy 정책은 각 s \in S에 대해 최대 행동-가치를 갖는 행동을 결정적으로 선택하는 정책입니다.
이전 장에서 논의했듯이, 이 정리는 각 \pi_{k+1}이 \pi_k보다 균일하게 더 낫거나, \pi_k만큼 좋다는 것을 보장하며, 이 경우 둘 다 최적 정책입니다. 이는 전체 프로세스가 최적 정책 및 최적 가치 함수로 수렴됨을 보장합니다. 이러한 방식으로 몬테카를로 방법은 샘플 에피소드만 주어지고 환경의 역학에 대한 다른 지식 없이도 최적 정책을 찾는 데 사용될 수 있습니다.
교재 4장 끝부분에서 말하는 bootstrapping은 “어떤 상태의 가치 추정치를 그 후속 상태들의 가치 추정치를 바탕으로 갱신하는 것”을 의미합니다. 즉, 추정(estimate)을 또 다른 추정에 의존해 업데이트하는 방식입니다. 예를 들어 DP나 TD 학습은 벨만 방정식을 기반으로 V(s) ← R + γ V(s') 꼴의 업데이트를 하므로, V(s')라는 아직 확실치 않은 값을 이용해 V(s)를 고치는 것이 bootstrapping입니다.
반면, first-visit Monte Carlo 방법은 각 상태에서 얻은 **전체 return (실제 에피소드 끝까지의 누적 보상)**만을 평균하여 가치 함수를 추정합니다 . 즉, 이미 확정된 실제 return을 이용하기 때문에 다른 상태의 추정치에 의존하지 않습니다. 따라서 Monte Carlo는 bootstrapping을 전혀 사용하지 않고, 이것이 교재에서 강조하는 중요한 차이점입니다.