틱택토 강화학습 (Tik-Tak-Toe RL) - [정보과학융합탐구 - 4월 과제]

2024.03.28 - [프로그래밍/강화학습 (RL)] - 틱택토 강화학습 (Tik-Tak-Toe RL) - [정보과학융합탐구 - 3월 과제]

틱택토 강화학습 (Tik-Tak-Toe RL) - [정보과학융합탐구 - 3월 과제]

이번 글에서는 제가 이 프로젝트를 수행하기 위해 필요한 여러 이론적 배경들에 대해 탐구해볼 것입니다.

---

이론적 배경

1. 강화학습 (Reinforcement Learning)

강화학습은 이전 글에서 설명했으므로 간략하게만 설명하겠습니다.
강화학습은 기계 학습의 한 영역으로, 어떤 환경 안에서 정의되어있는 에이전트(AI 등)가 현재의 상태를 인식해, 선택 가능한 행동들 중 보상을 최대화하는 행동을 선택하는 방법을 의미합니다.

1) 강화학습의 구성 요소

에이전트(Agent)	학습을 수행하는 대상
환경(Environment)	에이전트가 상호작용하는 대상
상태(State)	에이전트가 환경에 대해 파악할 수 있는 정보
보상(Reward)	에이전트가 취한 액션에 대한 결과 (양수, 음수 다 가능)
에피소드(Episode)	에이전트가 최종 상태에 도달하며 보상을 얻는 과정
정책(Policy)	에이전트가 상태를 입력받아 취해야 할 액션을 출력하는 함수
가치 함수(Value Fuction)	특정 상태에서 받을 수 있는 보상을 예측하는 함수

 
2) 강화학습 알고리즘의 종류
Value-Function만을 학습하고 policy는 암묵적으로만 갖게 강화학습하는 방식을 Value-Based 강화학습이라고 하고, 대표적으로 Q-Learning, SARSA, DQN 등이 있습니다.
Value-function 없이 policy만을 갖게 강화학습하는 방식을 Policy-Based 강화학습이라고 하고, 대표적으로 DDPG, A2C, A3C 등이 있습니다. 
Value-Based와 Policy-Based가 혼합되어있는 Actor-Critic 방식도 존재합니다. Actor-Critic에서 Actor는 policy을 학습하고, Critic은 value function을 학습합니다.

---

2. 마르코프 결정 과정 (Markov Decision Processes, MDP)

MDP(마르코프 결정 과정)는 강화학습의 큰 개념입니다. 강화학습이 이 큰 개념에서 잘 그려지고 요소들이 잘 정의되어야 좋은 결정을 한다고 할 수 있습니다. MDP의 구성 요소는 다음과 같습니다.

MDP의 구성 요소

 
1) 상태 (S)
상태는 에이전트가 관찰 가능한 상태의 집합입니다. 즉, 어떤 시점 t에서 가지고 있는 상태 $S_t$들의 집합이 S인 것입니다. 예를 들어, 아래와 같은 격자 세계가 있다고 해보면 여기에는 (1, 1)부터 (5, 5)까지 25가지의 상태가 있고, 시작했을 때 $S_1 = (1, 1)$이 될 것입니다.

격자 세계 (좌상단이 (1, 1), 우하단이 (5, 5)이다.)

 
2) 행동 (A)
행동은 어떤 상태 $S_t$에서 취할수 있는 행동을 의미합니다.
예를 들어 현재 저 격자 세계에서는 상하좌우로 움직이는 게 되겠죠. $S_1 = (1, 1)$에서 우로 이동한다면 $A_1$ = right가 될 것이고, 이대로 움직인다면 $S_2 = (1, 2)$가 될 것입니다.
 
3) 상태 변환 확률 (P)
상태 변환 확률이란 내가 지금 하려는 행동에 의해 상태가 그대로 변하지 않고, 어떤 변수에 의해 의도한 상태와 다른 상태로 바뀌는 것입니다.
쉽게 말해 내가 $S_1 = (1, 1)$에서 우로 1칸 이동하려고 했으나, 1%의 확률로 바람이 너무 세게 불어 움직이지 못할 수도 있고, 10% 확률로 너무 빨리 움직여 우로 2칸 이동할 수도 있는거죠. 이런 확률적인 요소들 때문에 수식이 이제부턴 확률 변수로 표현되게 됩니다.
$$ P_{ss'}^a = P[S_{t+1}=s | S_t=s, A_t=a] $$
 
4) 보상 함수 (R)
보상함수는 에이전트가 학습할 수 있는 유일한 정보로, 환경이 에이전트에게 주는 정보입니다.
상태가 변하는 것 자체가 확률적이기에 보상을 얼마나 받느냐도 당연히 기댓값 ,즉 확률로써 나타납니다.
$$ r(s, a) = E[R_{t+1}=s | S_t=s, A_t=a] $$
 
5) 감가율 ($\gamma$)
감가율은 0과 1 사이의 수로, 같은 크기의 보상이더라도 나중에 어느 정도의 가치가 되는지를 나타내는 것입니다.
예를 들어, 격자 세계에서는 에이전트가 짧은 거리로 갔는지 긴 거리로 갔는지에 따라 보상이 적어지므로 이를 결정해주는 것이 감가율이라고 할 수 있습니다.
 
결론적으로 마르코프 결정 과정은 위에서 봤듯이 상태에서 상태를 넘어다니며 확률적으로 변하는 것들을 모델링해주게 됩니다.

---

3. 벨만 방정식 (Bellman Equation)

벨만 방정식은 현재 상태의 가치 함수와 다음 상태의 가치 함수 사이의 관계를 식으로 나타낸 것입니다. 벨만 방정식을 알기 위해선 먼저 알아야 할 몇 가지 지식들이 있습니다.
 
1) 정책 (Policy)
정책이란 에이전트가 어떤 상황에서 취할 행동을 의미합니다. 

격자 세계

예를 들어, 격자 세계에선 위 그림과 같은 화살표를 통해 최단 거리로 도착지에 갈 수 있습니다. 그러나, 상태 변환 확률에서 말했듯 $S_t$에서 $A_t$는 확률적으로 이루어지기 때문에 이에 따른 정책 또한 확률로써 나타납니다. 정책은 조건부 확률로 나타나는데, "어떤 상태 s에서 행동 a를 취하는 것이 확률 p이다."라고 표현됩니다.
$$ \pi(a|s) = P[A_t=a | S_t=s] $$
 
이때, 최적의 경로는 당연히 파란 화살표만을 따라 6칸을 이동하는 것이겠죠. 그런데, 왜 6칸보다 많은 칸을 이동하여 도착지에 도착하면 최적의 경로가 아닌 것일까요? 그건 앞서 소개한 감가율 때문입니다. 우리는 파란색 화살표를 따라가지 않는 경로가 최선이 아니란 걸 알려줘야 하고, 그걸 감가율로 에이전트에게 전달할 수 있는 것입니다.
 
예를 들어 파란색 화살표로 이동해 6칸 만에 도착지에 도달했다면 $\gamma^6R$의 보상을 얻는 것이고, 그보다 긴 경로를 이동해 8칸만에 이동했다면 $\gamma^8R$의 보상을 얻게 하는 것입니다. 이때 $\gamma$는 0과 1 사이의 수이기 때문에 당연히 최단 경로가 가장 보상이 크겠죠.
 
이를 이용해 시점 t부터 현재 시점 k까지 받은 보상 $G_t$를 구할 수 있습니다.
$$ G_t = R_{t+1} + r^1 R_{t+2} + r^2R_{t+3} ... + r^{k-1}R_{t+k} $$
 
2) 가치 함수 (Value Function)
가치 함수는 내가 받을 수 있는 보상을 함수로 표현한 것입니다. 당연히 얘도 확률적으로 표현되고요. 가치 함수는 어떤 상태 s에서 받는 보상을 예측하는 상태 가치 함수와 어떤 상태 s에서 어떤 행동 a를 취했을 때 받는 보상을 예측하는 행동 가치 함수로 나뉘게 됩니다.
 
i) 상태 가치 함수 (State Value Function)
앞서 얘기했듯이 상태 가치 함수는 어떤 상태 s에서 받는 보상을 예측하는 함수이고, 다음과 같은 수식으로 나타낼 수 있습니다.
$$ v_\pi(s) = E_\pi[G_t | S_t = s] $$
$$ = E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3} + ... |S_t = s] $$
$$ = E_\pi[\sum_{k=0}\gamma^kR_{t+k+1} | S_t = s] $$
(여기서 밑에 $\pi$가 들어가는 건 전부 정책을 고려해준 것이라고 생각하면 됩니다.)
 
ii) 행동 가치 함수 (Action Value Function)
행동 가치 함수는 어떤 상태 s에서 행동 a를 했을 때 받는 보상을 예측하는 함수로, 이번에는 s, a에 대해 나타납니다.
$$ q_\pi(s, a) = E_\pi[G_t|S_t = s, A_t = a] $$
$$ = E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3} + ... |S_t = s, A-t = a] $$
$$ = E_\pi[\sum_{k=0}\gamma^kR_{t+k+1} | S_t = s, A_t = a] $$
 
3) 벨만 방정식 (Bellman Equation)
벨만 방정식은 현재 상태와 다음 상태의 가치 함수 사이의 관계를 나타낸 것으로 다음과 같은 식으로 나타납니다.
$$ v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) + |S_t = s] $$
 
이 벨만 방정식을 통해 최적의 정책을 찾는 것입니다. 따라서 상태 가치 함수, 행동 가치 함수 모두 최적을 선택해야 하고 이들은 다음과 같은 수식으로 나타납니다.
<최적의 상태 가치 함수> $ v_*(s) = max_\pi[v_\pi(s)] $
<최적의 행동 가치 함수> $ q_*(s, a) = max_\pi[q_\pi(s, a)] $
 
또, 벨만 방정식은 벨만 기대 방정식과 벨만 최적 방정식으로 나뉩니다.
벨만 기대 방정식은 특정 정책을 따라갔을 때 가치 함수 사이의 관계식이고, 벨만 최적 방정식은 최적의 정책만을 따라갔을 때 가치 함수 사이의 관계식입니다.

---

4. 몬테카를로 근사 (Monte Carlo Approximation)

몬테카를로 근사는 쉽게 말해 많은 시도를 통해 답을 찾아내는 것(노가다)입니다. 예를 들어, $\pi$값을 구하는 과정 등이 있죠.

몬테카를로 근사를 이용한 파이 값 구하기

 
이렇게 몬테카를로 근사를 통해 적절한 가치함수를 구할 수 있고, 그 유도 과정은 다음과 같습니다.
$$ v_\pi(s) ~ \frac{1}{N(s)}\sum_{i=1}^{N(s)}G_i(s) $$
$$ → V_{n+1} = \frac{1}{n}(G_n+(n-1)\frac{1}{n-1}\sum{i=1}^{n-1}G_i) $$
$$ = \frac{1}{n}(G_n + (n-1)V_n) $$
$$ = V_n + \frac{1}{n}(G_n-V_n) $$
 
따라서 결국 가치 함수는 다음과 같이 업데이트 되게 됩니다.
$$ V(s) ← V(s) + \frac{1}{n}(G(s)-V(s)) $$

or

$$ V(s) ← V(s) + \alpha(G(s)-V(s)) $$

---

5. 시간차 학습 (Temporal Differance Learning, TD)

앞서 설명한 몬테카를로 방식에는 단점이 있습니다. 바로 하나의 에피소드가 끝나고 나서야 업데이트가 이루어진다는 것입니다. 따라서 에피소드가 길거나 끝이 없는 문제에는 적용하기 힘듭니다.
그러나, TD(시간차 학습)는 에피소드 전체를 보지 않고 바로바로 업데이트가 진행됩니다. TD의 가치 함수 업데이트는 다음과 같습니다.
$$ V(S_t) ← V(S_t) + \alpha(R_{t+1} + \gamma V(S_{t+1}) - V(s)) $$
이때, $R_{t+1} + \gamma V(S_{t+1})$은 $G_t$로 나타낼 수 있습니다.
 
그러면 MC(몬테카를로 방식)랑 다른 점이 없다고 생각하실 수도 있지만, 사실 다른게 없는 게 맞습니다(?)
다만, MC는 $G_t$를 계산하므로 이미 지나온 길들에 대해 계산하고, TD는 그때그때 얻은 $S_t$와 $A_t$를 바탕으로 계산을 하기 때문에 TD는 실시간으로 업데이트가 가능한 것입니다.
 
1) SARSA 방식
SARSA는 TD의 한 종류입니다. 이름이 SARSA인 이유는 $S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$을 사용하기 때문입니다. 쉽게 말해 그냥 TD와는 달리 $S_{t+1}$에서의 정책에 따른 $A_{t+1}$까지 고려해준다고 이해하시면 될 것 같습니다. SARSA의 Q-함수 업데이트는 다음과 같습니다.
$$ Q(S_t, A_t) ← Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)) $$
 
2) Q-Learning
Q-Learning은 현재 강화학습에서 가장 자주 쓰이는 방법입니다. 가장 자주 쓰이는 건 가장 성능이 좋아서겠죠? 그럼 어떻게 작동하는지를 보겠습니다. Q_Learning에서의 Q-함수 업데이트는 다음과 같습니다.
$$ Q(S_t, A_t) ← Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, a') - Q(S_t, A_t)) $$
 
SARSA와의 차이점은 $A_t$가 a'로 바뀌었다는 것밖에 없습니다. 이때 a'은 $S_{t+1}$에서 가장 높은 행동 가치 함수 값을 가지는 행동을 의미합니다.
이 말이 뭔 말이냐면 SARSA에선 $S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$을 고려하지만, Q-Learning은 $S_t, A_t, R_{t+1}, S_{t+1}$만을 고려한다는 것입니다. 즉, SARSA는 정책에 따른 다른 행동을 고려하고 Q-Learning에서는 정책을 신경쓰지 않고 최적의 다음 행동(이라고 학습된 것)만 고려하는 것입니다.
 
이러한 이유 때문에 SARSA는 On-Policy라고, Q-Learning은 Off-Policy라고 불리기도 합니다.