[Reinforcement Learning] Monte Carlo Control

2025.06.29 - [Data & Research] - [Reinforcement Learning] Table of Contents

---

지난 포스팅들에서는 환경에 대한 정보를 알 수 없을 때 (Generalized) Policy evaluation하는 방법인 Monte Carlo 방법, Temporal Difference 방법에 대해서 알아보았습니다. 그럼 이번에는 환경에 대한 정보를 알 수 없을 때 (Generalized) Policy improvement하는 방법에 대해서 알아보고 최종적으로 (Generalized) Policy Iteration을 어떻게 수행하는지에 대해서 알아보려 합니다. 본 내용에 들어가기에 앞 서 2가지 정도 짚어볼 포인트가 있습니다. 

 

(1) Policy Improvement를 위한 가치함수

policy evaluation에서는 상태가치함수(state value function)를 활용해서 그 상태의 가치를 측정했습니다. 말 그대로 상태 가치 함수 \(V(s)\)는 '현재 상태 s가 얼마나 좋은지'를 알려줍니다. 이 정보로 최적의 행동을 선택하려면, 각 행동 \(a\)를 했을 때 어떤 상태 \(s'\)로 갈지, 그리고 그 보상은 무엇일지를 모두 고려하여 \(Q\)값을 계산해야 합니다. \[ \underset{a}{\operatorname{argmax}} \sum_{s' \in \mathcal{S}} P(s'|s,a) \left[ R(s,a,s') + \gamma V(s') \right] \] 하지만 model-free 환경에서는 상태 전이 확률 \(P(s'|s,a)\)와 보상 \(R(s,a,s')\)을 전혀 알지 못합니다. 따라서 위 식을 계산하는 것이 불가능합니다. \(V\)함수는 '목적지의 가치'는 알려주지만, '어떤 문(행동)이 그 목적지로 향하는지'는 알려주지 못하는 것과 같습니다. 

model-free 세팅에서 policy improvement를 할 때, 상태가치함수 대신 행동가치함수를 활용한다면 이 문제를 비껴갈 수 있습니다. (action들 중에서 \(Q\)값이 제일 높은것을 새로운 Policy로 정하는 방식) \[ \pi'(s) = \underset{a}{\operatorname{argmax}} Q(s,a) \]

(2) Exploitation & Exploration (Local Optima에 빠지는 것을 방지)

환경에 대한 정보를 알고 있을 때는 Policy Improvement를 어떻게 했었는지 기억나시나요? Greedy Policy였습니다. 다른 정책을 선택할 어떠한 여지도 두지 않고 그냥 "가장 좋은" 정책을 계속 선택해 나가면 되는 방식이었습니다. 왜냐면 환경에 대해 모두 알고 있기 때문에 직접 하면서 경험해보지 않아도 이미 어떤 상황에서 어떻게하면 행동가치 함수의 값이 얼마가 나오는지 "계산"하는 것이지 "추정"하는 것이 아니었습니다. 

이것이 환경에 대해 알지 못하는 model-free 세팅으로 오게되면 그대로 적용할 수가 없습니다. 이제는 어떤 정책이 좋은 정책인지 직접 해보면서(Sampling을 통해) 선택해야하는데 여기서도 Greedy Policy를 채택해버리면 현재 행동가치함수의 "추정치"가 가장 높은 행동만 계속 선택하게 됩니다. 이 경우, 다른 행동들은 영원히 시도되지 않을 수 있으며, 그 행동들의 \(Q\)값은 부정확한 초기값 또는 적은 샘플에 기반한 추정치에 머물게 됩니다.

그래서 model-free 세팅에서는 Exploitation뿐만 아니라 Exploration도 할 수 있는 방식을 채택해야 합니다. 나름의 근거를 바탕으로 예상한 value function "추정치"가 높은 방향으로 나아가면서도 그 추정이 엇나갔을 경우를 감안하여 다른 가능성도 일부 염두해두어야 하는 것이죠. 그러한 방향의 대표 방법론이 \(\epsilon\)-Geedy policy improvement입니다. 

 

1. ε-Greedy policy

입실론-탐욕(ε-Greedy) 정책은 대부분의 경우(확률 $1-\epsilon$)에는 가장 좋다고 알려진 행동을 선택하고(exploitation), 아주 가끔(확률 \(\epsilon\))은 가능한 행동 중 하나를 무작위로 선택하여(exploration) 균형을 맞춥니다.

\[ \pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}|}, & \text{if } a = \underset{a' \in \mathcal{A}}{\operatorname{argmax}} Q^{\pi}(s,a') \\ \frac{\epsilon}{|\mathcal{A}|}, & \text{otherwise} \end{cases} \]

• \(\epsilon\): 0과 1 사이의 작은 값으로, 탐색을 할 확률입니다. (예: 0.1)
• \(|\mathcal{A}|\): 해당 상태에서 가능한 총 행동의 개수입니다.

 

2. 몬테카를로 제어 (Monte Carlo Control)

MC control은 MC policy evaluation과 ε-Greedy policy improvement을 결합한 알고리즘입니다.

1. 임의의 Q함수와, 이 Q함수에 대한 ε-Greedy 정책 \(\pi\)로 시작합니다.
2. 현재 정책 \(\pi\)를 따라 하나의 에피소드를 생성합니다.
3. 에피소드에 등장한 모든 상태-행동 쌍 \((s,a)\)에 대해, 얻은 리턴 \(G_t\)를 이용해 Q값을 업데이트합니다.
   \[ Q(s,a) \leftarrow Q(s,a) + \alpha (G_t - Q(s,a)) \]
4. 업데이트된 Q값에 따라 ε-Greedy 정책 \(\pi\)는 자동으로 개선됩니다. (가장 좋다고 생각하는 행동이 바뀔 수 있으므로)
5. 2번 과정으로 돌아가 다음 에피소드를 생성하며 이 과정을 무한히 반복합니다.

Q함수는 점차 최적 Q함수 \(Q^*\)에 수렴하게 됩니다.

 

3. 최적 정책으로의 수렴 조건: GLIE

MC 제어가 최적 정책으로 수렴하기 위해서는 GLIE(Greedy in the Limit of Infinite Exploration)라는 조건을 만족해야 합니다.

• 조건 1: 모든 상태-행동 쌍은 무한히 많이 탐색되어야 합니다.
• 조건 2: 시간이 지남에 따라(학습이 진행됨에 따라) 정책이 점차 탐욕적(greedy) 정책에 가까워져야 합니다.

GLIE를 만족시키기 위한 일반적인 방법은 \(\epsilon\) 값을 시간에 따라 점차 감소시키는 것입니다. 예를 들어, \(k\)번째 에피소드에서의 입실론 값을 \(\epsilon_k = 1/k\)로 설정합니다. 이렇게 하면,

• 초기(k가 작을 때): \(\epsilon\)이 커서 탐색을 활발하게 수행합니다.
• 후기(k가 클 때): \(\epsilon\)이 0에 가까워져서, 충분히 학습된 Q값에 기반한 탐욕적 행동에 집중하게 됩니다.