바로 전의 챕터 4에서는 환경의 상태(state)가 다른 상태로 변화하는 확률인 p값들을 알고 있을 경우, dynamic programming(DP)로 문제를 푸는 방법에 대해 알아보았습니다. 이번 챕터 5에서는 그 p값들을 알지 못할 경우, 실제로 여러 에피소드를 실행해 그 평균값으로 V값을 추정하고 최적 정책을 찾아내는 Monte Carlo 방법에 대해 알아봅니다. 수익(return)이 잘 정의되어야 하기 때문에 여기서는 continuous task가 아닌, episodic task만 다룹니다.

이 챕터의 구성은 챕터 4와 동일합니다. 가장 먼저 어떤 정책이 주어졌을 때 V값을 계산하는 것부터 시작해서, 현재 정책을 개선하는 것을 살펴보고, 이 둘을 조합해서 최적 정책을 학습하는 알고리즘을 설명합니다.

5.1 Monte Carlo Prediction

먼저, V값을 추정하는 알고리즘에는 크게 두 가지가 있습니다. \(v_\pi(s)\)값을 추정하고자 할 때 에피소드별로 가장 첫번째로 해당 상태를 방문했을 때의 수익(return)만을 저장한 후 여러 에피소드 결과의 평균을 내는 것이 first-visit MC method이고, 에피소드 내에서 해당 상태에 방문하는 모든 경우의 수익을 전부 저장해서 평균내는 것이 every-visit MC method입니다. 여기에서는 first-visit만 설명하지만 every-visit도 거의 동일합니다.

출처: Sutton and Barto Textbook, p.92

인풋: 알고리즘의 인풋은 지난 챕터 Policy Evaluation와 마찬가지로 V값을 계산하고자 하는 정책입니다.
초기화:

• 모든 V(s)값을 무작위로 초기화하고,
• 수익들이 저장될 리스트 Returns(s)를 상태(state) 개수만큼 만들어 모두 빈 리스트로 초기화합니다.

각 에피소드별 루프:

• 정책 \(\pi\)를 따라 에피소드를 플레이해서 에피소드 결과를 생성합니다.
• 수익 변수 G를 0으로 둡니다.
• 에피소드 내 스텝을 역순으로 루프합니다.
  
  • a. 역순으로 루프하므로, G는 \(\gamma\)를 곱해 한 턴 할인한 후, 해당 턴 직후 보상 \(R_{t+1}\)을 수익에 더합니다.
  • b. First-visit MC이므로, \(S_t\)가 이전 타임 스텝들에 존재하는지 확인하고, 없으면 G를 Returns(\(S_t\)) 리스트에 추가한 후 평균을 내어 \(V(S_t)\)에 저장합니다.

샘플이 많아질수록 이 알고리즘을 통한 추정치는 실제값에 가까워지고, 각 추정치는 불편(unbiased) 추정치이며, 오차는 \(\frac{1}{\sqrt{n}}\)에 비례해 줄어듭니다. 이 알고리즘도 더 잘 이해하기 위해서는 Sutton and Barto 교과서 93페이지의 예시를 참조 바랍니다. 예시에서는 블랙잭 게임을 예로 드는데, 사실 블랙잭 게임은 환경의 역학(dynamic)인 p값을 우리가 계산 가능하므로 DP로 풀어도 되는 문제입니다. 그런데도 MC가 쓰이는 이유는, DP를 쓰려면 모든 경우의 수에 대한 확률 p값들을 먼저 다 계산해 놓아야하는 점이 부담스러운 경우가 있고, 그 계산 도중에 오류가 날 확률이 있는 문제들도 있기 때문입니다.

DP는 벨만 방정식을 통해 다른 상태(state)의 추정치를 이용해 현재 상태의 값을 추정하는 bootstrap 방법을 사용하는데, MC는 그와 달리 각 상태(state)에 대한 추정치가 독립(independent)입니다. 또한 어떤 특정한 하나의 상태(state)의 값을 추정하는 것에 대한 계산 비용 부담(computational expense)도 상태의 개수와 별개입니다. 따라서 만약 모든 상태의 값을 추정할 필요가 없을 경우 MC가 훨씬 더 장점을 갖습니다.

5.2 Monte Carlo Estimation of Action Values

만약 MDP 모델의 p값을 아예 모른다면, 상태 가치 함수(state-value function, V)만 가지고는 정책을 결정할 수 없기 때문에 행동 가치 함수(action-value function, Q)를 추정해야 합니다.

\(q_*\)를 추정하는 방법은 기본적으로 비슷합니다. V값을 추정할 때는 어떤 상태 s에서부터의 수익을 감안했다면, 여기서는 어떤 상태 s에서 행동 a를 취했을 경우부터의 수익을 감안하면 됩니다. 다만 선택할 수 있는 행동이 많을 경우에는, 많은 행동들이 아예 선택되지 않아서 선택되지 않은 행동 a들의 \(q_\pi(s,a)\)는 추정할 수 없을 수 있다는 것입니다. 이런 경우에는 에피소드를 처음부터가 아니라 어떤 상태-행동 쌍(state-action pair)부터 시작하도록 하고, 모든 쌍(pair)에서 에피소드가 시작될 확률을 0보다 큰 양의 확률을 가지도록 하면 됩니다. 이를 초기화를 탐색적으로 한다(assumption of exploring starts)고 합니다. 이 가정은 유용하지만, 실제 환경에서 직접 학습할 때는 에피소드 초기화를 원하는 방식으로 하지 못할 수도 있습니다. 이럴 경우 대안의 방법은, 결정론적(deterministic) 정책이 아닌 확률적(stochastic) 정책만 사용하는 것입니다. 나중 챕터에서 이에 대해 더 자세히 다루도록 합니다.

5.3 Monte Carlo Control

잠시 Prediction과 Control이라는 용어에 대해 짚고 넘어가겠습니다. 용어의 뜻 자체와 실제 문제가 매칭이 잘 안되기 때문에, 한번 숙지하는 것이 좋습니다. 강화학습의 컨택스트에서,

• Prediction 문제란 정책(policy)이 주어졌을 때, 이 정책이 얼마나 유용한지를 계산하는 일입니다. 즉, 어떠한 상태(state)에서 이 정책을 따랐을 때 기대할 수 있는 총 수익(return)을 찾는 것입니다.
• Control 문제란 정책이 아직 정해지지 않았을 때, 최적 정책을 찾는 일입니다.

Monte Carlo를 이용한 Control도 DP 챕터의 Generalized Policy Iteration (GPI)와 비슷한 패턴으로, 정책 평가(policy evaluation)와 정책 개선(policy improvement)을 반복하게 됩니다. 먼저, 정책 평가는 위의 5.2에서 다룬 것과 같이 행해집니다. 랜덤으로 초기화한 정책을 이용해서, 숱한 에피소드를 생성한 후 해당 정책을 따를 경우의 \(q_\pi(s,a)\) 들의 값을 찾아냅니다. 그 다음 정책 개선은, 상태 가치 함수 V가 아니라 행동 가치 함수 q를 찾아냈기 때문에 단순히,

\(\pi(s) = arg \max_{a} q(s, a)\)

로 설정하면 됩니다. 즉 각 상태마다, 그 상태에서 취할 수 있는 행동 중 \(q_\pi(s,a)\)값이 가장 큰 행동을 취하는 것으로 정책을 결정하면 됩니다. 이 방법은 아래의 Policy Improvement Theorem(챕터 4.2)을 충족하기 때문에, 개선된 정책은 매 스탭마다 이전 스탭의 정책보다 최소한 같거나 더 낫다는 것이 보장되며, 전체적인 프로세스가 최적의 정책과 최적의 가치 함수를 찾을 수 있게 됩니다.

하지만 우리는 위에서 두 가지 비현실적인 가정을 했는데, 1) 에피소드의 초기화를 탐색적으로(exploring starts) 한다는 것과, 2) 무한한 숫자의 에피소드를 경험한다는 것입니다. 1번은 조금 있다 다루고, 먼저 2번의 가정을 다루겠습니다. 2번의 가정을 해결하는 방법은 두 가지가 있는데,

1. DP의 경우처럼, 어떠한 오차 허용치 값을 설정하는 것입니다. 이 경우, 알고리즘이 설정한 허용치 이하까지 수렴하는 것을 보장할 수 있지만, 현실에서 적용할 때 여전히 너무나도 많은 에피소드가 필요할 수 있습니다.
2. 정책 평가(policy evaluation)을 완벽하게 끝까지 한 후에 정책 개선을 하기보다는, 적당히 근사한 후 정책 개선으로 넘어가는 것입니다. 그 극단적인 예는 Value Iteration 알고리즘인데, 이 경우 한 스탭의 정책 평가 후에 바로 정책 개선을 합니다.

2번의 방식을 이용한 Monte Carlo with Exploring Starts 알고리즘의 pseudocode는 아래에 있습니다.

초기화:

• 정책 함수 \(\pi(s)\)의 값들을 무작위의 행동으로 설정합니다.
• Q(s, a) 함수를 무작위로 초기화 합니다.
• Returns(s, a)는 모든 s, a 쌍에 대해 공간을 가지는 빈 리스트입니다.

루프를 무한히 합니다 (각 에피소드당):

• 시작할 상태 S0와 행동 A0를 무작위로 선택합니다.
• S0, A0에서 정책 \(\pi\)를 따라서 에피소드를 생성합니다.
• 리턴값인 G는 0으로 초기화합니다.
• 에피소드의 각 스탭을 역순으로 루프합니다, t = T -1, T - 2, ... 0:
  
  • 스탭을 역순으로 갈 때마다 리턴값 G는 \(\gamma\)로 할인한 후 해당 스탭의 보상을 더합니다.
  • G를 \(Returns(S_{t}, A_{t})\)의 리스트에 추가합니다.
  • \(Returns(S_{t}, A_{t})\)의 리스트의 평균값을 \(Q(S_{t}, A_{t}\)로 설정합니다.
  • 정책 함수값 \(\pi(S_{t})\)를 \(arg \max_{a} Q(S_{t}, a)\)로 설정합니다.

프로세스가 복잡해보이지만, 결국은 어떤 S, A 쌍(pair)을 업데이트하기 위해서는, 각 에피소드에서 해당 쌍이 나타나는 가장 첫번째 시점에서부터 시작해서, 에피소드 끝까지의 보상을 할인율을 적용하여 모두 더한 리턴 G를 리스트에 모읍니다. 그렇게 모아진 리턴값들을 평균 낸 것이 \(Q(S_{t}, A_{t})\)가 되는 것입니다.

5.4 Monte Carlo Control without Exploring Starts

앞서 언급한 비현실적인 가정 중 첫번째인 탐색적 초기화(exploring starts) 가정을 없애는 방법은 두 가지가 있는데, on-policy 방식과 off-policy 방식이 있습니다. On-policy 방식에서는 에피소드에서 결정을 내리는데 사용되는 정책과, 평가되고 개선되는 정책이 동일하고, Off-policy 방식에서는 에피소드를 생성하는 정책과 실제로 평가되고 개선되는 정책이 다릅니다. 5.3에서 다룬 방식은 on-policy 방식이고, 이 섹션에서 소개하는 방법 또한 on-policy입니다.

탐색적 초기화 없이 모든 S, A 쌍을 방문하도록 하는 방법은, \(\epsilon\)-greedy 정책을 이용하는 것입니다. \(\epsilon\)-greedy 정책이란, greedy action (원래 정책에서 선택할 행동)에는 1 - \(\epsilon\) + \(\frac{\epsilon}{|A(s)|}\)의 확률을 배정하고, 나머지 non-greedy action에는 각각 \(\frac{\epsilon}{|A(s)|}\)의 확률을 배정하는 방식입니다. 여기서 |A(s)|는 가능한 행동의 개수입니다.

조금 더 구체적으로 예를 들자면, \(\epsilon\) = 0.2이라고 하고 행동 A, B, C, D가 있으며, 원래의 greedy 정책에서 선택할 행동이 B라고 한다면, A, B, C, D에 각각 0.2 / 4 = 0.05의 확률씩을 배정하고, B는 1 - 0.2 = 0.8의 확률을 추가 배정합니다. 그렇게 해서 A, B, C, D에 greedy policy가 0, 1, 0, 0의 확률을 배정한다면, \(\epsilon\)-greedy policy는 0.05, 0.85, 0.05, 0.05의 확률을 배정합니다. 그렇게 해서 에피소드가 반복되면, A, C, D의 행동도 가끔씩은 취하게 되어서 q함수를 업데이트할 수 있는 데이터를 모을 수 있습니다.

이 알고리즘의 pseudocode는 위와 같은데, 정책 개선을 하는 부분을 제외하고는 5.3가 매우 유사합니다.

참고로 On-policy 방식에서 \(\pi(a|s)>0\) 가 모든 a와 s에 대해 성립할 경우 정책이 soft하다고 하는데, 여기서는 어떠한 양의 \(\epsilon\)값에 대해 \(\pi(a|s)>\frac{\epsilon}{|A(s)|}\) 가 성립할 경우 \(\epsilon\)-soft한 정책이라고 합니다. 본 알고리즘은 \(\epsilon\)-soft한 정책 중에서 최적의 정책을 찾아내지만, 탐색적 초기화의 가정은 없어도 되게 되었습니다. 최적의 정책으로 수렴한다는 증명은 102 페이지를 참조 바랍니다.

5.5 Off-policy Prediction via Importance Sampling

모든 learning control 방법은 최적 행동에 대한 행동 가치(action values)를 배우려 하지만, 모든 행동을 탐색하기 위해서는 최적이 아닌 행동을 해야한다는 딜레마에 봉착합니다. On-policy 방법은 이를 조율하기 위해, 최적의 정책이 아닌 탐색을 계속 하는 거의 최적인 정책(near-optimal)을 배우는 것으로 타협합니다. 그런데 이보다 더 직관적인 방법은 두 가지 다른 정책을 사용하는 것입니다. 이 때 값을 배우려고 하는 최적 정책을 target policy라고 하고, 에이전트의 행동을 위해 사용하는 정책을 behavior policy라고 하며, 이 방식을 off-policy learning이라 합니다.

이 섹션에서는 우선, target policy \(\pi\)와 behavior policy b가 둘 다 고정된 경우의 prediction 문제에 대해 알아봅니다. 다시 말해, 우리는 \(v_{\pi}\)나 \(q_{\pi}\)를 추정하려고 하는데, 정책 \(\pi\)가 아닌 정책 b에 따라 행동한 에피소드만 가지고 있는 경우입니다.우선 b를 따른 에피소드로 \(\pi\)에 관한 가치를 추정하기 위해서는 \(\pi\) 정책 하에서 가능한 모든 행동이 b에서도 가끔씩이라도 일어나야만 합니다. 다시 말해 \(\pi(a|s) > 0\)이면 \(b(a|s) > 0\)이어야 합니다. 이를 coverage의 가정이라고 부릅니다. 이 가정 하에서, 정책 \(\pi\)는 deterministic이어도 되지만, 정책 b의 경우 정책 \(\pi\)와 동일한 값을 가지는 상태(state) 외에는 stochastic이어야 합니다. 예를 들어 정책 \(\pi\)는 greedy policy, 정책 b는 \(\epsilon\)-greedy policy를 사용할 수 있습니다. 이 섹션에서는 prediction 문제를 다루기 때문에 \(\pi\)가 변하지 않고 고정적으로 주어졌다고 가정합니다.

거의 모든 off-policy 방법들이 importance sampling을 이용하는데, 이는 어떤 distribution의 샘플을 가지고 다른 distribution의 값을 추정하는 테크닉입니다. 이를 적용해, 각각 target과 behavior 정책 하에서 해당 trajectory가 발생할 상대적 확률의 비율을 가중평균한 수익(return)을 off-policy learning은 사용합니다. 이 비율을 importance-sampling ratio라고 합니다. 어떤 초기 상태 \(S_t\)에서 출발하여 어떤 특정한 상태-행동 trajectory가 펼쳐질 확률은 아래와 같습니다.

따라서 target과 behavior 정책 사이의 상대적인 확률 비율은 아래와 같습니다.

MDP의 transition probability p는 보통 모르는 상태이지만, 위와 같이 서로 상쇄됩니다. 따라서 importance sampling ratio는 MDP와 관계없이 두 정책과 시퀀스에만 의존합니다. 이제 이 ratio를 이용하여 \(v_b(s)\)를 \(v_\pi(s)\)로 변환할 수 있습니다.

위를 Monte Carlo 업데이트 식으로 적으면 아래와 같습니다. 분모의 \(\Im(s)\)은 해당 상태(state)를 얼마나 방문했는가를 나타내는 수로, every-visit Monte Carlo에서는 매 번 방문할 때마다 +1이 되고, first-visit Monte Carlo에서는 에피소드에서 첫번째 방문에만 +1이 됩니다.

위와 같이 단순하게 방문 횟수로 평균하는 것을 ordinary importance sampling이라고 하고, 아래와 같이 가중 평균하는 것을 weighted importance sampling이라고 합니다. 아래에서 분모가 0일 경우 V(s)값은 그냥 0으로 정의됩니다.

First-visit 방식 하에서 단순평균 방식과 가중평균 방식의 차이를 알기 위해서는 아주 간단한 예를 들어 한 에피소드에 한번만 방문할 경우를 생각해 보면 됩니다. 가중평균 방식에서는 분모와 분자가 상쇄되면서 그냥 관찰된 수익 \(G_t\)이 되며, 이 기대값은 \(v_\pi\)가 아닌 \(v_b\)이므로 통계학적으로 biased된 추정입니다. 반면 단순평균 방식은 언제나 기대값이 \(v_\pi\)가 되는 unbiased 추정이지만, 극단적인 결과가 나오기도 합니다. 예를 들어 ratio가 10, 즉 해당 trajectory는 target에서 일어날 확률이 behavior보다 10배가 높다고 하면, 추정치가 실제 관찰된 수익 \(G_t\)의 10배가 되어버리는 것입니다. 따라서 단순평균 방식은 variance가 unbounded인 반면 가중평균은 그렇지 않습니다. 이론적으로, 만일 수익(return)이 bounded라면, ratio의 variance가 무한이라 하더라도 가중평균 추정치의 variance는 0으로 수렴합니다. 그렇기 때문에 현업에서는 가중평균을 사용하는 추세입니다.

그런데 every-visit 방식의 경우에는 두 평균 방식이 다 biased이며 샘플이 많아지는 극한(asympototically)에서 bias는 0에 수렴합니다.

5.6 Incremental Implementation

아래는 가중평균 방식을 사용한 off-policy MC prediction의 pseudocode입니다.

5.7 Off-policy Monte Carlo Control

아래는 가중평균 방식을 이용한 off-policy MC control의 pseudocode입니다.

5.10 요약

Monte Carlo 방식은 DP 방식에 비해 여러 가지 이점이 있습니다.

• 우선 환경의 역학(dynamics)이 어떻게 되는지에 대한 모델이 없이도 환경과의 직접적인 interaction을 통해 최적의 행동을 찾아낼 수 있습니다.
• 둘째, 샘플 모델이나 시뮬레이션과 함께 사용될 수 있습니다. 생각보다 많은 문제들에서, DP가 요구하는 transition probability에 대한 직접적인 모델이 없다고 하더라도 샘플 에피소드를 구현하는 것이 가능합니다.
• 셋째, DP는 어떠한 특정 상태(state)의 값을 구하려면 연관된 다른 상태들의 값도 알아야 했지만, MC의 경우에는 특정한 상태들에만 포커스를 맞출 수가 있습니다.
• 마지막으로, Markov property의 가정이 틀릴 경우에 MC 방식은 DP에 비해 영향을 덜 받습니다. 이는 DP처럼 어떤 상태값을 구하기 위해서 이후의 연결된 상태값에 의존을 하지 않기 때문입니다.