깃북에 강화학습에 대해 정리가 잘 된 글이 있어서, 1회독 후에 제 언어로 흐름을 정리해보았습니다.
Definition
먼저, 강화학습 (Reinforcement Learning, RL)은 기계학습 (Machine Learning, ML)의 세가지 분류 중 하나입니다. ML은 크게 1) 지도학습 (Supervised Learning) 2) 비지도학습 (Unsupervised Learning) 3) 강화학습으로 나뉘는데, 지도학습은 input을 기반해서 label과 유사한 prediction을 만들어내는 것이 목표이고, 비지도학습은 label없이 데이터의 분포를 학습하여 생성 및 clustering에 활용됩니다. 강화학습은 보상 즉, reward를 정의하고 이를 최대화하는 방식을 찾아내는 것이 목표인데, 학습의목표가 되는 reward가 정의하기 나름이기 때문에 자유도가 굉장히 높아서 다양한 분야에 활용이 가능할 것으로 생각됩니다.
지도학습과 비지도학습 개념에 대해서는 공부 또는 실습한 경험이 있는데, 강화학습은 처음이라 기대가 되면서도 좀 어려울 것 같다는 생각이 듭니다..
Introduction
강화학습의 특징은 1) Trial and Error 2) Delayed Reward 이 두 가지 키워드로 설명합니다. 바둑게임을 강화학습으로 학습시킬 때를 예로 들어보겠습니다. 먼저 \(t\) 시간의 바둑게임의 이미지를 입력으로 하면, 모델은 그 상태에서 가장 이길 가능성이 높은 \(t+1\)시간의 수를 두게 됩니다. 이렇게 계속 게임을 진행하고 해당 게임이 끝나면 게임의 승패가 보상으로 주어지게 됩니다. 모델을 학습시키기 위해, 각 시간에서 다양한 수를 둬보는 과정이 1)으로 설명됩니다. 또한 바둑과 같이 행동을 취할 때마다 보상이 주어지지 않는 문제가 존재하는데, 강화학습은 2)와 같은 특징으로 인해 이런 문제도 학습할 수 있습니다. 주체 즉 Agent가 여러 Action을 해보고 각각의 Reward을 비교하면서 Reward을 최대화하도록 행동하는 방식을 학습하는 것이 메커니즘입니다. 주어진 데이터뿐만 아니라 Agent의 Action도 Reward에 영향을 준다는 점이 앞선 지도, 비지도 학습과의 차이점입니다.
강화학습은 Dynamic Programming (DP)에서 출발했는데, 차이점을 먼저 설명드리면 “환경”에 대한 정보가 주어졌는지에 따라 DP와 RL이 나뉩니다. 기본적인 개념 및 용어가 유사하기 때문에 예에 대한 설명으로 시작하도록 하겠습니다.
Markov Decision Process (MDP)
강화학습은 MDP로 정의되는 문제를 풀 수 있다고 말합니다. (MDP가 아닌 문제를 푸는 연구도 진행되어왔으나, 대부분의 강화학습연구는 MDP를 기반한다고 합니다.) MDP는 \( \prec \mathcal{S,A,P,R,\gamma} \succ \)의 튜플로 정의됩니다. 하나씩 살펴보면, 먼저 $\mathcal{S}$가 State의 집합을 의미합니다. 바둑 게임으로 이어서 설명하면, 해당 단계에서의 바둑판의 상태로 표현됩니다. \(\mathcal{A}\)는 Action의 집합을 의미하며, 각 단계에 두는 수가 됩니다. \(\mathcal{P}\)는 State transition probability 행렬으로 state간 이동할 확률을 표현합니다. 수식으로 표현하면,
\[\mathcal{P}^{a}_{ss’} = \mathcal{P}(S_{t+1}=s’\mid A_{t}=a, S_{t}=s)\]\(\mathcal{R}\)는 Reward 함수로 각 단계의 reward의 기댓값을 도출합니다. 수식으로 표현하면,
\[R^{a}_{s} = \mathbb{E}[R_{t+1}\mid A_{t}=a, S_{t}=s].\]\(\gamma\)는 Discount factor로 시간에 따른 reward의 감소를 표현하기 위한 상수입니다. \(R^{a}_{s}\)의 경우 state \(s\)의 reward를 표현하지만 바둑 하나의 게임이 끝났을 때, 즉 하나의 episode가 끝났을 때 모든 reward의 합인 return을 표현할 수 있습니다.
\[\begin{aligned} G_{t} &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+2} + \cdots \\ \therefore G_{t} &= R_{t+1} + \sum_{k=1}^{\infty }\gamma^{k}R_{t+k+1} \\ \end{aligned}\]이외에도 Policy라는 개념이 있습니다. State가 주어졌을 때 어떤 액션을 취할지 정하는 방식으로 다음과 같이 정의됩니다.
\[\pi (a\mid s) =P(\mathcal{A_{t}}=a \mid \mathcal{S_{t}}=s)\]Value function
다시 한 번 정리하면, DP 및 RL의 목표는 “Reward를 최대화하는 Policy를 찾는 것”입니다.
기본 개념들을 이용하여 학습에 필요한 개념을 정의해보도록 하겠습니다. State \(s\)에서 얻을 수 있는 reward의 기댓값을 표현하기 위해서 State-value function을 정의합니다.
\[V_{\pi}(s) = \mathbb{E}_{\pi}(G_{t}\mid S_{t}=s)\]따라서 state \(s\)에서 여러 state 중 가장 reward를 많이 받을 수 있을 것 같은 state로 움직이는 전략을 짤 수 있습니다. 하지만 이 때, \(\mathbb{P}\)에 따라 움직이기 때문에, 원하는 state로 움직이지 못할 수 있다는 한계가 존재합니다. 이를 보완하기 위한 개념이 state와 action에 따른 기대 reward를 계산하는 State action-value function입니다.
\[q_{\pi}(s,a)\ = \mathbb{E}_{\pi}(G_{t}\mid S_{t}=s, A_{t}=a)\]Bellman equation
Value function이 한 state에서의 reward를 표현했다면, 현재 state //(s//)와 다음 state //(s’//)간의 value function의 관계를 표현한 것이 Bellman equation입니다. 먼저 state-value function의 경우에는 다음과 같이 풀어서 표현할 수 있습니다.
\[\begin{aligned} V_{\pi}(s) &= \mathbb{E}(G_{t}\mid S_{t}=s) = \mathbb{E}( R_{t+1} + \sum_{k=1}^{\infty } \gamma^{k} R_{t+k+1} \mid S_{t}=s) = \mathbb{E}( R_{t+1} + \gamma v(s’) \mid S_{t}=s) \\ Q_{\pi}(s,a) &= \mathbb{E}(G_{t}\mid S_{t}=s) = \mathbb{E}( R_{t+1} + \sum_{k=1}^{\infty } \gamma^{k} R_{t+k+1} \mid S_{t}=s, A_{t}=a) = \mathbb{E}( R_{t+1} + \gamma Q_{\pi}(s’) \mid S_{t}=s, A_{t}=a) \end{aligned}\]기댓값으로 표현한 Bellman equation을 다시 풀어보면 다음과 같이 쓸 수 있습니다.
\[\begin{aligned} V_{\pi}(s) &= \sum_{a\in \mathcal{A}} \pi(a \mid s) Q_{\pi}(a,s) \\ Q_{\pi}(s,a) &= \mathcal{R}^a_{s} + \gamma \sum_{s’\in \mathcal{S}} P^{a}_{ss’}V_{\pi}(s’) \\ \therefore V_{\pi}(s) &= \sum_{a\in \mathcal{A}} \pi(a \mid s) \left( \mathcal{R}^a_{s} + \gamma \sum_{s’\in \mathcal{S}} P^{a}_{ss’}V_{\pi}(s’) \right) \\ \therefore Q_{\pi}(s,a) &= \mathcal{R}^a_{s} + \gamma \sum_{s’\in \mathcal{S}} P^{a}_{ss’} \left( \sum_{a’\in \mathcal{A}} \pi(a’ \mid s’) Q_{\pi}(a’,s’) \right) \\ \end{aligned}\]Bellman equation을 이용하기 위해서는 //(\mathcal{R}^a_{s} , P^{a}_{ss’}//) 즉, 환경에 대해 알고 있어야합니다. 하지만 실생활에서는 이런 조건을 만족시키기 쉽지 않습니다. Reward와 state transition probability를 MDP의 model이라고 표현하는데, RL의 경우 MDP model을 모르는 상태에서도 학습할 수 있다는 점에서 DP와 차이가 있습니다.
Dynamic Programming, Monte-Carlo method, Time Difference method
Bellman equation을 기반으로 Dynamic Programming (DP), Monte-Carlo method (MC), Time Difference method (TD)도 많이 사용되는 기법들입니다. 원 링크와 링크가 기반한 강의들에서도 이 세 기법을 자세히 다루고 있으나, 강화학습을 중점적으로 다루기 위해서 간략히 개념 및 의미만 짚고 넘어가도록 하겠습니다.
DP는 위의 Bellman equation을 기반으로 모든 state의 reward를 계산합니다. 
예시에서 표현되는 모든 14(16-2)개의 state에 대해서 //(k//) 번째의 value function 값을 계산합니다. 이렇게 iterative하게 업데이트해서 구한 true value function을 maximize할 수 있는 policy를 구하는 방식이 DP입니다. 이 때 모든 state에 대한 value function을 계산하는 과정이 문제에 따라 굉장히 cost가 클 수 있습니다. 따라서 state를 sampling하여 구하는 방식이 등장하였는데, 여기에 해당되는 방법론이 MC와 TD입니다.
MC와 TD는 둘 다 현재 policy를 기반으로 state를 sampling해서 value function을 계산합니다. 이렇게 되면 model-free한 기법이기 때문에 많은 문제에 적용할 수 있다는 장점이 있습니다. 이 둘의 차이점은 MC는 episode가 끝난 후에, TD는 한 step단위로 reward를 계산한다는 점입니다.
Q learning
위 기법들의 한계점으로는 value function을 계산할 때 현재의 policy를 기반으로 한다는 점입니다. 현재의 policy안에서 최선의 선택을 하지만, 이는 결과적으로 local optima일 가능성이 높기 때문입니다. 따라서 지금 당장은 optimal이 아니더라도 다른 action을 취하는 과정이 필요합니다. 현재의 policy에서 greedy하게 학습하는 방식을 “On-policy”라고 표현하고 이와 다르게 다른 경로를 탐험하는 policy와 이를 기반으로 학습하는 policy를 분리한 개념을“Off-policy”라 표현합니다. MC와 TD도 사실 off-policy화 시켜 사용할 수 있으나 (유명한 방법론인 SARSA가 off-policy MD), importance sampling이라는 트릭을 사용해서 //(\mu//) 분포의 reward를 통해 타겟인 //(\pi//) 분포를 update하는 과정이 필요합니다. 이 때 임의의 //(\mu//)에 따라 학습 성능이 많이 좌우되기 때문에 importance sampling을 사용하지 않는 Q learning이 도입되었습니다.
가장 유명한 Q learning 알고리즘은, Behavior policy로는 //(\epsilon//)-greedy. Target policy로는 greedy를 이용하는 방법입니다.
\[\pi(a’ \mid s) = \text{argmax}_{a’} Q(s, a’)\] \[\begin{aligned} \mu(a \mid s) = \left\{\begin{matrix} 1 - \epsilon + \frac{\epsilon}{m} & a = \text{argmax}_{a'} Q(s, a') \\ \frac{\epsilon}{m} \quad \quad \quad & otherwise \end{matrix}\right. \\ \end{aligned}\] \[Q(s,a) \leftarrow Q(s,a) + \alpha (R^{a}_{s} + \gamma \text{max}_{a}Q(s’,a) - Q(s,a))\]마지막 줄의 //((R^a_s+\gamma\text{max}_{a}Q(s’,a)-Q(s,a))//)는 incremental mean에서 온 것으로,
//(\mu_{T-1}=\frac{1}{T-1}\sum_{t=1}^{T-1}x_{t}//)라고 하면,
\[\begin{aligned} \mu_{T} &= \frac{1}{T}\left( \sum_{t=1}^{T} x_{t} \right) \\ &= \frac{1}{T}\left( x_{T} + \sum_{t=1}^{T-1} x_{t} \right) = \frac{1}{T}\left( x_{T} + (T-1) \mu_{T-1} \right)\\ &= \frac{1}{T} x_{T} + \frac{(T-1)}{T}\mu_{T-1} \\ &= \mu_{T-1} + \frac{1}{T} (x_{T} + - \mu_{T-1}) \\ \end{aligned}\]Policy Gradient
지금까지의 방식들은 모두 value function based method 즉, “True value function을 얼마나 잘 찾을 수 있냐”에 초점을 맞췄고, 그 이후에 value를 높일 수 있는 action을 선택하는 policy를 택했습니다. 하지만 이런 방식으로는 action이 연속적이거나, space가 넓은 경우에는 부적합하다는 한계가 존재합니다. 따라서 optimal한 policy를 바로 찾을 수 있는 policy-based method에 대해 살펴보도록 하겠습니다. (그 중에서도 미분가능한 policy model을 기반으로 하는 policy gradient method에 집중하도록 하겠습니다.)
Policy gradient를 학습시키기 위해서 objective function //(J(\theta)//)를 정의합니다.
\[J(\theta) = \sum_{s \in S} d_{\pi} (s) V(s) = \sum_{s \in S} d_{\pi} (s) \sum_{a \in A} \pi_{\theta}(a \mid s) Q(s,a)\]이는 state transition probability //(d_{\pi} (s)//) 와 state //(s//)에 Return의 기댓값인 //(V(s)//)의 곱으로 이루어져있습니다. //(d_{\pi} (s)//)는 정확히 stationary transition probability라고 하는데, 우리가 가정하는 Markov process에서 무한히 step을 이동하면 state간에 이동할 확률이 특정 값으로 수렴한다는 것이 알려져 있습니다. 이 때 수렴한 정적인 (stationary) 확률을 //(d_{\pi} (s)//)로 표현합니다. Objective function을 최대화하는 parameter //(\theta//)를 찾도록 학습시키기 위해, //(J(\theta)//)를 미분합니다.
\[\begin{aligned} \nabla_{\theta} J(\theta) &= \nabla_{\theta} \left(\sum_{s \in S} d_{\pi} (s) \sum_{a \in A} \pi_{\theta}(a \mid s) Q(s,a) \right) \\ &= \left(\sum_{s \in S} d_{\pi} (s) \sum_{a \in A} \nabla_{\theta} \pi_{\theta}(a \mid s) Q(s,a) \right) \\ &=\left(\sum_{s \in S} d_{\pi} (s) \sum_{a \in A} \frac{\pi_{\theta}(a \mid s) \nabla_{\theta}\pi_{\theta}(a \mid s)}{\pi_{\theta}(a \mid s)} Q(s,a) \right) \\ &= \left(\sum_{s \in S} d_{\pi} (s) \sum_{a \in A} \pi_{\theta}(a \mid s) \nabla_{\theta}\text{log}\pi_{\theta}(a \mid s) Q(s,a) \right) \\ &= \mathbb{E}\left(\nabla_{\theta}\text{log}\pi_{\theta}(a \mid s) Q(s,a) \right) \\ \end{aligned}\]여기서 //(\pi_{\theta}\left(a \mid s\right)//)를 통해서 //(\text{log}//) 취해주는데, 이 부분이 사라진 //(\pi_{\theta}\left(a \mid s\right)//)을 살려서 sampling의 expectation을 위한 과정입니다. 고전적인 DP와 달리 RL은 전체를 다 알고 시작하는 것이 아니라 경험해보고 배운 것을 토대로 학습하는 특성을 가지기 때문에 Expectation이 필요하다고 합니다. (하지만 피상적으로만 이해한 것 같아서 좀 더 살펴볼 필요가 있음.)
원문에서는 Policy gradient 방식 중 REINFORCE와 Actor-Critic에 대한 소개를 끝으로 마무리하고 있습니다. Policy gradient의 미분 전개나, 최신의 Policy gradient 방법론들이 많이 나와서 이 부분은 새로운 포스팅으로 소개하는 것이 좋을 것 같아서 여기서 마무리하도록 하겠습니다. 감사합니다.