👨‍🏫학습목표

오늘은 $\epsilon$-greedy policy와 MC Control 그리고 GLIE에 대해 배워볼 예정이다.

👨‍🎓강의영상: https://www.youtube.com/watch?v=TF63tYx-fdk&list=PLvbUC2Zh5oJtYXow4jawpZJ2xBel6vGhC&index=12

1️⃣ Monte Carlo method

📕 지난 시간에 배운 내용

• Monte Carlo 방식은 sample을 이용한 GPI 방식을 사용한다.
• Sample data는 episode 단위로 구성되어 있다.
• $Q(s, a)$ 추정치를 사용한다.
• $q_\pi(s, a) = \mathbb{E}_\pi[G_t | S_t = s, A_t = a]$

---

2️⃣ $\epsilon$-greedy policy

🔷 Exploitation

• Exploitation이란 우리가 이미 알고 있는 정보 내에서 최선의 결정을 내리는 것.
  ex) 자주 가는 집 중에서 가장 맛있는 집을 찾아가는 방식

• 가장 큰 Q-value를 사용하여 action을 선택하는 방법.

• greedy policy와 같은 개념

• 이미 알고 있는 정보에서 최적의 policy를 찾는 것이기 때문에 효율적으로 업데이트하는 방식으로 이해할 수 있다.

• 단점: 경험하지 않는 sample에 대해서는 접근하지 않는다.

🔷 Exploration

• Exploration이란 우리가 알고 있는 것 외에 추가적인 정보를 참고해서 새로운 결정을 내릴 수 있도록 찾는 방법
  ex) 가보지는 않았지만 새로운 맛집의 정보를 찾아 시도해보는 것

• Exploitation에서 선택할 최적의 action을 $1-\epsilon$ 확률로 취한다.

• $\epsilon$만큼은 random하게 다른 action을 취한다.

• 장점: 그동안 경험하지 않았던 state-action을 경험하여 더 좋은 policy를 찾을 수 있다.

• 단점: risk가 따른다.

🔷 $\epsilon$-greedy policy

• $\epsilon$-greedy policy이란 Exploitation 방법과 Exploration 방법을 trade-off로 조절하는 방법이다.

• $\epsilon$만큼은 ramdom하게 선택하고 $1-\epsilon$만큼은 최적의 $Q$-value를 선택하는 방법이다.

• 궁극적으로 더 좋은 decision을 할 수 있다.

• 물론 short-term sacrifice 가 존재한다.

---

3️⃣ MC Control

🔷 MC Control

• MC Control에서는 policy를 개선한다. 그 전에 앞서 살펴본 $\epsilon$-greedy policy를 생각해보자.

• $\epsilon$-greedy Policy에서 ramdom action을 취할 확률은 $\epsilon$이다.

• 이때 모델이 취할 수 있는 action의 수가 m개라면, 각 action은 $\frac{\epsilon}{m}$의 확률로 발생한다.

🔻 기존의 greedy policy

$\pi'(s) = \arg \max_a Q^\pi(s, a) \Rightarrow \text{deterministic policy}$

• 기존의 Greedy policy에서는 $max \ Q(s,a)$를 선택하기 때문에 action을 취하는 방식 자체가 deteministic 하다.

🔻 $\epsilon$-greedy Policy

$pi'(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{m} & \text{if } a = \arg \max_{a'} Q^\pi(s, a') \\ \frac{\epsilon}{m} & \text{otherwise }(m-1 \text{ actions}) \end{cases}$

• $\epsilon$-greedy는 $\frac{\epsilon}{m}$확률로 random action을 취하기 때문에 stochastic하다고 할 수 있다.

❗여기서 잠깐!

Stochastic policy를 사용할 때도 policy를 개선할 때마다 더 좋은 policy가 도출된다는 보장이 있을까?🤔

$\text{For any } \epsilon\text{-greedy policy } \pi, \epsilon\text{-greedy policy } \pi' \text{ w.r.t. } q_\pi \text{ is always improved.} \\ v_{\pi'}(s) \geq v_\pi(s)$

• 결론부터 말하자면 $\epsilon$-greedy Policy에서도 Policy는 개선된다.

✍ 증명 과정

$q_\pi(s, \pi'(s)) = \sum_a \pi'(a|s) q_\pi(s,a)$

• Action-value function을 취할 수 있는 action으로 분해하여 $\sum$ 기호로 표현한다.

$= \frac{\epsilon}{m} \sum_a q_\pi(s,a) + (1-\epsilon) \max_{a'} q_\pi(s,a')$

• $\pi'(a|s)$ 함수를 최적의 action과 random action으로 구분하여 작성한다.

$\geq \frac{\epsilon}{m} \sum_a q_\pi(s,a) + (1-\epsilon) \sum_a \frac{\pi(a|s) - \epsilon/m}{1-\epsilon} q_\pi(s,a) \quad (\because \sum_a \frac{\pi(a|s) - \epsilon/m}{1-\epsilon} = 1)$

• 부등호가 성립하는 이유는 최대값이 기대값보다 항상 크다는 $\max_x f(x) \geq \mathbb{E}[f(X)]$ 때문이다.

• $\sum_a \frac{\pi(a|s) - \epsilon/m}{1-\epsilon} :$ 합은 1을 만족하지만, 음수인 항 역시 존재할 수 있다. 기존 policy의 action에 대한 확률 분포와 개선된 policy의 확률 분포는 다를 수 있기 때문이다.

$= \sum_a \pi(a|s) q_\pi(s,a) = v_\pi(s)$

• 최종적으로 각 항의 공통 부분을 제거하면 state-value function에 도달한다.

📕 Policy Improvement Theorem

$\text{If} \ \ Q^\pi(s, \pi'(s)) \geq V^\pi(s) \text{ for all } s \in \mathcal{S}, V^{\pi'}(s) \geq V^\pi(s) \text{ for all } s \in \mathcal{S}.$

Policy Improvement Theorem에 따라 $\epsilon$-greedy Policy Improvement 방식에서는 policy가 계속해서 개선된다.

---

4️⃣ Greedy in Limit with Infinite Exploration

🔷 Greedy in Limit with Infinite Exploration의 조건

아래의 2조건을 만족하면 이를 GLIE라고 한다.

🔻 1. $\lim_{k \to \infty} n_k(s, a) = \infty$

• State-action pair의 sample을 무한히 방문해야 한다.

• State-action에 대한 정확한 mean Return값을 구하기 위해서다.

• Sample data를 늘리는 방법으로 조건을 만족할 수 있다.

🔻 2. $\lim_{k \to \infty} \pi_k(a|s) = 1 \text{ where } a = \arg \max_{a'} Q_k(s, a')$

• 최종적으로 stochastice이 사라지고, Greedy policy에 수렴해야 한다.

• $\epsilon$값이 0에 수렴하도록 조정해야 한다.

🔷 GLIE MC Control

$n(S_t, A_t) \leftarrow n(S_t, A_t) + 1$

• Sample 수를 계속 늘린다.

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \frac{1}{n(S_t, A_t)} [G_t - Q(S_t, A_t)]$

• Incremental Monte Carlo update를 적용한 것이다.

• 물론 $Constant-\alpha \ MC$를 적용할 수도 있다.

• $\epsilon = \frac{1}{k}$ and $\pi \leftarrow \epsilon$- $greedy(Q)$ 을 통해 $\epsilon$값을 조절할 수 있다.

$Q(s, a) \rightarrow q_*(s, a)$

• 이러한 방식을 통해 Optimal action function을 구할 수 있다.

---

5️⃣ Monte Carlo method의 pseudo code

🔷 Monte Carlo method

🔻 1. Initialize

• 모든 state, action 쌍에 대한 Q-value $Q(S,A)$를 초기화한다.

• Terminal state의 Q-value값은 암묵적으로 0으로 한다.

• Return $G_t$를 저장할 리스트를 만든다.

• Policy $\pi$ 역시 초기화하되, 모든 action이 약간의 확률을 가지도록 한다.

2, 3 단계는 각 episode별로 반복한다.

🔻 2. MC Policy Evaluation

• Data sample: $S_0, A_0, R_1, S_1, \dots, S_{T-1}, A_{T-1}, R_T, S_T$

• Return값은 0으로 초기화

• $G \leftarrow \gamma G + R_{t+1}$ 연산을 통해 $G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$을 계산한다.

• Unless 부터는 처음 등장한 $(S_t, A_t)$에 적용하는 방식으로 first-visit에만 적용된다.

• Return값을 통해 mean Return 값을 적용할 수 있다.

  • Incremental MC: $n(S_t, A_t)$
  • constant- $\alpha$ MC: $\alpha$

🔻 3. $\epsilon$-greedy Policy Imprevement

$A^* \leftarrow \arg \max_a Q(S_t, a)$

$\text{For all } a \in \mathcal{A}(S_t): \\ \pi(a|S_t) \leftarrow \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}(S)|} & \text{if } a = A^* \\ \frac{\epsilon}{|\mathcal{A}(S)|} & \text{otherwise} \end{cases}$

• 하나의 episode 내에 존재하는 state action에 대해 업데이트를 진행한다.

• $|\mathcal{A}(S)|:$ Action의 수
  
  

  이러한 과정을 반복하면 Policy Evaluation과 Policy Improvement가 각각 수렴하게 된다. 이때 학습을 종료하면 된다.

---

6️⃣ 정리

🔷 12강에서 배운 내용은 아래와 같다.

1. $\epsilon$-greedy Policy에 대해 배웠다.
2. Policy를 개선하는 MC Control 단계에 대해 배웠다.
3. $\epsilon$-greedy Policy에서도 policy가 개선됨을 증명하였다.
4. GLIE와 GLIE가 되기 위한 조건 2가지를 살펴보았다.
5. Monte Carlo method의 pseudo code에 ****대해 살펴보았다.