hemisus
참고한 자료
1. Reinforcement Learning?
강화학습은 머신러닝의 한 분야로, 지도학습과 비지도학습과는 다르게 정답이나 데이터에 대해 학습하는 것이 아닌, 주어진 환경에서 에이전트(Agent)의 행동에 따른 “보상”을 통해 학습하는 머신러닝 기법이다.
에이전트가 환경에서 어떤 행동을 하면 보상이 주어지는데, 이 보상을 최대화 하는 방법을 시행착오를 겪으며 학습하는 것이다.
이러한 강화학습은 단순히 한 시점에서 단번의 결정으로 해결되는 문제가 아닌, 여러 차례에 순차적인 결정을 요구하는 문제에 적용된다. 이러한 순차적 행동 결정 문제를 정의하는데 MDP(Markov Decision Process)를 사용한다.
2. MDP(Markov Decision Process)
MDP는 순차적 행동 결정 문제를 정의하는 프레임워크로, 크게 다섯 가지 요소로 구성된다.
\[\text{MDP} = \langle S,\ A,\ R,\ P,\ \gamma \rangle\]- 상태 집합 $S$
- 행동 집합 $A$
- 보상 함수 $R$
- 상태 변환 확률 $P$
- 할인율 $\gamma$
상태 (State)
\[S_t = s\]상태는 에이전트가 관찰할 수 있는 자신의 상황이다. 환경이 그리드월드일 때 에이전트가 있는 좌표 $(x, y)$ 가 상태가 되고, 전체가 5×5라면 상태 집합은 다음과 같다.
\[S = \{(1,1), (1,2), \dots, (5,5)\}\]주의할 점은 $S_t$ 가 확률변수라는 것이다. “시간 $t$ 에 에이전트가 어떤 상태에 있을지”는 그 전까지의 행동과 환경에 따라 달라지므로 고정된 값이 아니다. 그래서 “시간 $t$ 에 에이전트가 상태 $s$ 에 있다”는 사실은 $S_t = s$ 라고 표현한다.
행동 (Action)
\[A_t = a\]행동은 에이전트가 어떤 상태에서 취할 수 있는 선택지다. 그리드월드의 경우에는 상하좌우 네 가지다.
\[A = \{\text{up},\ \text{down},\ \text{left},\ \text{right}\}\]보상 함수 (Reward Function)
\[r(s, a) = E[R_{t+1} \mid S_t = s,\ A_t = a]\]보상은 환경이 에이전트에게 주는 유일한 학습할 수 있는 정보이다. 강화학습의 목표는 시간에 따라 얻는 보상의 합을 최대로 하는 행동을 에이전트가 선택하도록 만드는 것이다.
보상함수는 시간 $t$ 일 때 상태 $S_t = s$ 에서 $A_t = a$ 행동을 했을 경우 받을 보상에 대한 기댓값 $E[\cdot]$ 이다. 보상을 계산하는 주체는 환경인데, 환경에 따라서 같은 상태에 같은 행동을 해도 다른 보상을 줄 수 있기 때문에 확률적인 환경도 표현할 수 있도록 기댓값으로 정의한다.
또한 상태와 행동은 $S_t,\ A_t$ 인 반면 보상은 $R_{t+1}$ 이다. 에이전트는 시간 $t$ 에 행동을 결정하고, 그 행동에 대한 보상은 환경으로부터 다음 시점에 전달받는다. 즉 에이전트 입장에서 보상은 “행동한 뒤에 환경으로부터 받는 것”이므로 $t+1$ 인 시점에서 에이전트가 받는 보상을 $R_{t+1}$ 으로 표현한다.
보상은 에이전트가 알고 있는 것이 아닌, 환경이 알려주는 것이다.
상태 변환 확률 (State Transition Probability)
\[P_{ss'}^a = P[S_{t+1} = s' \mid S_t = s,\ A_t = a]\]상태 $s$ 에서 행동 $a$ 를 했을 때 다음 상태가 $s’$ 이 될 확률이다.
어떤 행동을 하였더라도 의도한대로 원하는 상태에 도달하지 못할 수도 있다. 미끄러지는 로봇, 바람이 불어 밀리는 등 상태의 변화는 환경의 불확실성, 확률적인 요인을 포함하고 있다.
이 확률 또한 에이전트는 알지 못하는 값으로, 환경의 모델(model)이라고도 부른다.
할인율 (Discount Factor)
\[\gamma \in [0, 1]\]동일한 보상일지라도 미래에 받게 될 보상은 당장 현재 받는 보상에 비해 가치가 떨어진다. 할인율은 미래의 가치를 현재의 가치로 할인하는 비율로, 시간 $t$로부터 $k$가 지난 뒤에 받을 보상이 $R_{t+k}$라고 하면, 이것의 현재 가치는 $\gamma^{k-1} R_{t+k}$ 이다.
\[\gamma^{k-1} R_{t+k}\]3. 정책 (Policy)
MDP가 문제를 정의했다면, 정책은 에이전트가 문제의 모든 상태에서 취할 행동 양식이다.
\[\pi(a \mid s) = P[A_t = a \mid S_t = s]\]각 상태에서 어떤 행동을 할 확률인지를 나타내는 함수다. 그리드월드의 어떤 칸에서 정책이 $\pi(\text{up} \mid s) = 0.7,\ \pi(\text{right} \mid s) = 0.3$ 이라면, 그 칸에서는 70% 확률로 위로, 30% 확률로 오른쪽으로 간다는 뜻이다.
강화학습의 목표는 결국 누적 보상의 기댓값을 최대로 만드는 최적 정책 $\pi_*$ 를 찾는 것이다. 이를 위해 정책의 좋고 나쁨을 수치화할 기준이 필요하다. 그것이 다음에 나올 가치함수다.
4. 가치함수
에이전트는 현재 시점에서 앞으로 받을 보상을 고려해서 행동을 선택해야 한다. 이 “앞으로 받을 보상” 을 평가하는 개념이 바로 가치함수이다.
반환값 (Return)
에이전트가 시간 $t$로부터 행동을 하면서 받게 될 보상들을 할인해서 모두 더한 값이다.
\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\]보상은 행동을 한 그 다음 타임스텝에 받으므로 $R_{t+1}$에서 시작한다는 것을 유의. 에이전트가 최대화하려는 대상은 당장의 보상 $R_{t+1}$ 이 아니라 이 반환값 이다.
또한 반환값은 “실제로 환경에서 행동하며 받은 보상의 합”이다. 반환값을 구하려면 에이전트의 행동이 유한한 시간에 끝나야 하고, 이렇게 유한한 에이전트와 환경의 상호작용을 “에피소드”라고 부른다.
환경과 정책이 확률적(불확실성을 포함)이므로 같은 상태에서 시작해도 반환값은 에피소드마다 다를 수 있다.
가치함수 (Value Function)
따라서 반환값의 기댓값을 쓴다.
\[v_\pi(s) = E_\pi[G_t \mid S_t = s]\]“정책 $\pi$ 를 따를 때, 현재시점 t의 상태 $s$ 에서 앞으로 받을 것으로 기대되는 보상들의 합”이다.
큐함수 (Q-Function)
가치함수는 상태의 가치만 알려준다. 하지만 실제로 상태를 옮기려면 에이전트는 행동을 해야 하고, 행동에 따라 보상이 달라지거나 상태 변환 확률 때문에 의도한 대로 되지 않을 수도 있다. 그래서 행동을 고르려면 “현재 상태에서 각 행동을 했을 때의 가치”를 알아야 한다. 그것이 큐함수다.
\[q_\pi(s, a) = E_\pi[G_t \mid S_t = s,\ A_t = a]\]가치함수와 큐함수는 다음 관계로 이어져 있다. 상태의 가치는 그 상태에서 가능한 각 행동의 큐함수 $q_\pi(s,a)$ 를 그 행동을 할 확률 $\pi(a \mid s)$ 로 가중해서 모두 더한 것이다. 즉 정책에 따라 행동을 골랐을 때 큐함수의 기댓값이다.
\[v_\pi(s) = \sum_{a \in A} \pi(a \mid s)\, q_\pi(s, a)\]실전에서 에이전트가 행동을 선택하는 기준으로는 큐함수가 훨씬 유용하다. 가치함수만 있으면 “다음 상태의 가치”를 알기 위해 환경 모델($P_{ss’}^a$)이 필요하지만, 큐함수는 상태에서 각 행동의 가치를 직접 알려주기 때문이다.
5. 벨만 방정식 (Bellman Equation)
가치함수를 정의는 했지만, 정의대로 계산하려면 무한한 미래의 보상을 전부 합쳐야 한다. 이걸 계산 가능한 형태로 바꿔주는 것이 벨만 방정식이다.
벨만 기대 방정식
반환값은 보상들의 합이었다. 여기서 $\gamma R_{t+2}$ 부터 뒤의 항들을 $\gamma$ 로 묶어보면, 묶인 괄호 안이 다시 반환값의 형태가 된다.
\[\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \\ &= R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots \right) \\ &= R_{t+1} + \gamma G_{t+1} \end{aligned}\]즉 반환값은 “바로 다음에 받을 보상 + 할인된 다음 시점의 반환값” 으로 쪼갤 수 있다. 이를 가치함수에 그대로 대입하면 다음과 같다.
\[v_\pi(s) = E_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s]\]그런데 $G_{t+1}$ 은 에이전트가 실제로 받은 보상이 아닌, 앞으로 받을 것이라 예상하는 값이다. 그리고 “어떤 상태에서 앞으로 받을 보상의 기댓값”은 바로 가치함수의 정의다. 따라서 $G_{t+1}$ 자리를 다음 상태의 가치함수로 바꿔 쓸 수 있다.
\[v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s]\]이것이 벨만 기대 방정식이다. 현재 상태의 가치함수 $v_\pi(s)$ 와 다음 상태의 가치함수 $v_\pi(S_{t+1})$ 사이의 관계를 나타낸 식으로, 미래의 보상을 전부 더하지 않고도 한 스텝 앞만 보면 가치를 계산할 수 있게 해준다.
정책과 환경을 명시적으로 풀어 쓰면 다음과 같다.
\[v_\pi(s) = \sum_{a \in A} \pi(a \mid s) \left( r(s, a) + \gamma \sum_{s' \in S} P_{ss'}^a\, v_\pi(s') \right)\]큐함수에 대해서도 같은 형태가 성립한다.
\[q_\pi(s, a) = E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s,\ A_t = a]\]벨만 최적 방정식
벨만 기대 방정식은 “주어진 정책 $\pi$ 의 가치”를 계산한다. 하지만 우리가 원하는 건 최적 정책이다.
최적 정책이라는 것은 정책을 따라갔을 때 받을 보상들의 합인 가치함수가 가장 큰 정책이다. 이를 위해 먼저 최적 가치함수, 최적 큐함수를 정의한다.
\[v_*(s) = \max_{\pi} \left[ v_\pi(s) \right], \qquad q_*(s, a) = \max_{\pi} \left[ q_\pi(s, a) \right]\]여기서 $\max_{\pi}[\cdot]$ 는 가능한 모든 정책 $\pi$ 에 대해 대괄호 안의 값 중 최댓값을 반환하는 함수다. 즉 \(v_*(s)\) 는 어떤 정책을 쓰든 상태 $s$ 에서 얻을 수 있는 가치의 최댓값이고, \(q_*(s,a)\) 는 각 $(s,a)$ 쌍마다 모든 정책을 다 넣어 봤을 때 나오는 가장 큰 큐함수의 값이다.
이 정의에는 최적 정책 $\pi_*$ 가 등장하지 않는다는 점에 유의하자. \(v_*\) 와 \(q_*\) 는 최적 정책을 몰라도 정의되는 값이고, 최적 정책은 뒤에서 이 값들로부터 만들어진다.
최적 가치함수와 최적 큐함수의 관계
최적 큐함수 \(q_*(s,a)\) 에는 “지금 행동 $a$ 를 한 뒤, 이후 모든 시점에서도 계속 최적으로 행동한다” 는 가정이 담겨 있다. 즉 미래의 최적성이 값 안에 이미 포함되어 있으므로, 현재 상태에서는 \(q_*\)값이 가장 큰 행동 하나만 고르면 된다. 이 직관을 부등식으로 확인해 보자.
(1) \(v_*(s) \le \max_a q_*(s,a)\)
임의의 정책 $\pi$ 에 대해 다음이 성립한다.
\[v_\pi(s) = \sum_{a \in A} \pi(a \mid s)\, q_\pi(s,a) \;\le\; \sum_{a \in A} \pi(a \mid s)\, q_*(s,a) \;\le\; \max_{a \in A} q_*(s,a)\]첫 번째 부등호는 \(q_*\) 의 정의에 의해 모든 정책에 대해 \(q_\pi(s,a) \le q_*(s,a)\) 이기 때문에 성립한다. 두 번째 부등호는 확률 $\pi(a \mid s)$ 로 가중합한 값이 그 최댓값을 넘을 수 없으므로 성립한다. 이 부등식은 모든 $\pi$ 에 대해 성립하므로, 좌변에 $\max_\pi$ 를 취해도 그대로 유지된다.
(2) \(v_*(s) \ge \max_a q_*(s,a)\)
\(a^* = \arg\max_{a} q_*(s,a)\) 라 하자. 상태 $s$ 에서 $a^*$ 를 하고, 이후에도 최적으로 행동하면 그 가치는 정확히 \(q_*(s,a^*)\) 이다. \(v_*(s)\) 는 모든 정책의 가치 중 최댓값이므로, 이 정책의 가치보다 작을 수 없다.
두 부등식을 합치면 다음 성질이 유도된다.
\[v_*(s) = \max_{a \in A} q_*(s, a)\]$v_\pi(s) = \sum_a \pi(a \mid s)\, q_\pi(s,a)$ 는 행동들에 대한 가중평균이었다. 최적에서는 평균을 내는 대신 가장 좋은 행동 하나에 확률을 몰아주므로, 가중합 자리에 $\max$ 가 들어간다.
최적 정책
이제 최적 정책은 각 상태에서 최적 큐함수 \(q_*(s,a)\) 값이 가장 큰 행동을 선택하여 만들 수 있다. 즉 \(q_*\) 를 최대로 만드는 행동은 확률 1로 선택하고, 나머지 행동은 선택하지 않는다.
\[\pi_*(a \mid s) = \begin{cases} 1 & \text{if } a = \arg\max_{a' \in A} \left[ q_*(s, a') \right] \\ 0 & \text{otherwise} \end{cases}\]여기서 $\arg\max_{a’ \in A}[\cdot]$ 는 대괄호 안의 값을 최대로 만드는 행동 $a’$ 를 반환한다.
\(q_*\) 의 정의에서 $\max_\pi$ 는 $(s,a)$ 쌍마다 따로 계산되므로, 원칙적으로는 상태마다 최댓값을 주는 정책이 서로 다를 수도 있다. 그러나 MDP에서는 모든 상태에서 동시에 최댓값을 달성하는 결정론적 정책이 항상 존재하며, 위처럼 \(q_*\) 에 대해 greedy하게 행동하는 정책이 바로 그것이다. 즉 “\(q_*\) 로 만든 greedy 정책을 따르면, 그 결과가 다시 \(q_*\) 를 달성한다”는 일관성이 성립한다.
주의할 점은, greedy 선택의 기준이 반드시 최적 큐함수여야 한다는 것이다. 최적이 아닌 큐함수 $q_\pi$ 는 \(q_*\) 와 달리 “현재 행동 이후에는 기존 정책 $\pi$ 를 따른다”는 가정 위에서 계산된 값이다. 따라서 $q_\pi$ 에 대해 greedy하게 행동하면 정책이 $\pi$ 보다 좋아지기는 하지만, 최적이라는 보장은 없다. 이 개선을 반복해 최적 정책에 도달하는 방법이 정책 이터레이션이다.
벨만 최적 방정식
위에서 유도한 \(v_*(s) = \max_a q_*(s,a)\) 에서 큐함수 \(q_*(s,a)\) 를 그 정의로 풀어 가치함수 형태로 고쳐 표현하면 벨만 최적 방정식이 된다. 기대 방정식에서 정책에 대한 가중합 $\sum_a \pi(a \mid s)$ 자리에 $\max_a$ 가 들어간 형태다.
\[v_*(s) = \max_{a} E\left[R_{t+1} + \gamma v_*(S_{t+1}) \mid S_t = s,\ A_t = a\right]\] \[q_*(s, a) = E\left[R_{t+1} + \gamma \max_{a'} q_*(S_{t+1}, a') \mid S_t = s,\ A_t = a\right]\]이 두 식의 우변에는 어떤 정책도 등장하지 않는다. 따라서 모든 정책을 나열해 $\max_\pi$ 를 직접 계산할 필요 없이, 이 방정식을 만족하는 \(v_*\) 또는 \(q_*\) 를 먼저 구한 뒤 greedy하게 행동하기만 하면 최적 정책을 얻을 수 있다.