논의를 시작하기 전에 지난번 살펴보았던 확률변수의 개념에 대해 몇 가지 언급해야 할 사항이 있다.

첫째, 지난 포스트 /확률변수를 이해하다/에서는 이산 확률변수 중에서도 표본공간이 유한(finite)한 경우만을 다루었다. 유한인 경우의 모든 내용이 무한이면서 이산인 경우로 일반화되는데, 달라지는 거의 유일한 포인트는 극한 개념을 도입해야 한다는 것이다. 극한의 개념이 요구되는 이유를 두 가지로 생각해볼 수 있다.

  • 확률변수의 기반이 되는 표본공간이 무한일 경우.
  • 새로운 확률변수를 무한개 확률변수의 합으로 정의할 때.

표본공간이 무한인 이산의 경우는 각 항이 0보다 크거나 같고 $(a_n \ge 0)$ 급수의 합이 1로 수렴하는 $(\sum_{n=1}^\infty a_n = 1)$ 무한수열 $a_n$을 제시하는 것과 본질에서 동일하다. 여기서 $f(n) = a_n$ 으로 정의하면 $\Omega = \{1, 2, … \}$를 표본공간으로 하는 확률분포함수를 얻게 된다.

Infinite discrete distribution
무한 이산 확률분포함수 (using: Desmos online calculator)

이 확률분포함수에 관한 확률변수 $X: \{1, 2, \ldots \} \rightarrow \mathbb{R}$를 생각할 때 달라지는 점은 $X$의 정의구역인 표본공간 $\Omega = \{1, 2, \ldots \} $이 무한이라는 점이다.

무한개의 확률변수를 합하여 새로운 확률변수를 만드는 경우는 MDP의 개념을 이해해가면서 구체적으로 다루기로 하자. (다음 포스트에서 “가치함수”를 자세히 다룰 때 등장하게 된다.)

둘째, 확률변수의 공역은 반드시 실수의 집합이어야 하는 것은 아니다. 확률변수라는 함수의 역할을 살펴보면 정의구역인 표본공간의 확률분포에 관련된 시행이 일어났을 때 확률적으로 어떤 값을 취하게 된다. 따라서 그 값이 꼭 실수일 필요는 없다는 것을 어렵지 않게 이해할 수 있을 것이다. 세상 대부분의 정보 혹은 데이터를 (적어도 이론적으로는) 수로 표현할 수 있다는 사실을 상기하면 확률변수의 함숫값이 실수인 경우만을 고려해도 큰 문제는 없지만 실수가 아닌 수학적 대상 혹은 그 어떤 집합이라도 공역으로 허용하면 수학적 모델을 기술하는데 (인지학적으로?) 확실히 편리한 면이 있다.

마지막으로, 확률변수에 다른 함수를 합성하는 것이 새로운 확률변수를 만드는 자연스러운 방법의 하나다. (정의구역이 표본공간인 함수는 모두 확률변수라는 점을 상기하자!) 임의의 집합 $A, B$에 대해서 $X : \Omega \rightarrow A$가 확률변수이고 $f:A \rightarrow B$가 임의의 함수일 때,

는 새로운 확률변수이다.

요약하면,

  • 무한이면서 이산일 경우도 급수의 극한 개념을 이용하여 유한의 경우와 매우 유사하게 확률변수를 다룰 수 있다.
  • 확률변수의 공역은 실수의 집합이 아닌 집합이 될 수도 있다.
  • 확률변수와 다른 함수와의 합성을 이용하여 새로운 확률변수를 창조할 수 있다.

마코프 모델 (Markov model)

이산적으로 진행되는 시간의 변화에 따라 형성된 데이터를 수학적으로 기술할 때 (거의 필수적으로) 사용되는 것이 마코프 모델이다. 물론 시간순의 데이터를 모델링하는 중요한 이유 중 하나는 (미래에 대한) 예측이다. 시간이 $t = 0, 1, 2, \ldots$ 와 같이 이산적으로 흐른다고 가정했을 때 각 시점 $t$에 대응되는 확률적 데이터를 $X_t$라는 확률변수로 모델링하여 $X_0, X_1, \ldots$ 라는 일련의 확률변수를 얻게 된다. 이때 각 확률변수 $X_i$ 사이의 관계를 어떻게 설정해야 할까?

마코프 모델은 이런 상황에서 확률변수들간의 상호관계가 특정한 조건을 만족하는 상황을 모델링한다. 마코프 성질이라 불리는 이 조건이 말하는 것은 다음과 같다:

“The future is independent of the past, given the present.”

좀 더 엄밀하게 말하자면, “현재” 시점을 $t$라고 할 때 “미래” 시점에 확률적으로 형성되는 데이터 $X_{t+1}, X_{t+2}, \ldots$는 단지 현시점의 데이터 $X_t$에만 의존한다. 즉 $\ldots, X_{t-2}, X_{t-1}$과 독립이다. 이와 같은 모델을 Markov chain이라고 한다. (같은 문맥에서 시간이 이산적인 대신 연속적으로 파라미터화 되는 경우를 Markov process라고 부른다.) Markov chain의 기원에 관한 흥미로운 이야기를 담은 다음 영상을 시청해보기를 권한다: [2].

Markov chain의 개념에 action과 reward라는 개념을 추가하면 오늘의 주제인 MDP(Markov Decision Process)의 모델을 얻게된다.

MDP의 요소들

MDP의 개념은 다음의 다섯가지의 기본 요소의 역할을 명확히 이해하는 것이 중요하다.

  • Agent
  • Environment
  • Action
  • State
  • Reward

MDP 모델을 조금 쉽게 이해하기 위해 두 주체 간의 게임으로 생각해보자. 이 게임은 주인공인 agent와 주인공이 모험할 수 있도록 배경을 설정해주는 environment 간의 상호작용이다. 게임은 이산적인 time step (편의상 시점이라고 부르겠다) 을 따라가며 상호작용이 단계적으로 이루어진다. 좀 더 정확하게 표현해보면 시점을 나타내는 파라미터 $t$가 $t=0$, $t=1$, $t=2$, $\ldots$ 이렇게 변해가면서 agent와 environment가 각자의 활동을 하며 상호작용을 이어가게 된다. 각 시점에서 agent가 할 수 있는 선택을 action이라고 한다. Agent가 게임에서 취할 수 있는 모든 가능한 action을 다 모아놓은 집합을 $\mathscr{A}$라고 하고, 시점 $t$에 취하는 action을 $A_t$라고 표시하자. 자연스럽게 $A_t \in \mathscr{A}$임을 알 수 있다. 반면, 각 시점에서 environment는 두 가지 반응으로 agent의 action에 대응하는데 그것이 각각 state와 reward이다. Action의 경우와 마찬가지로 시점 $t$에 environment가 내놓게 되는 state를 $S_t$, reward를 $R_t$로 표시한다. 마찬가지로 $\mathscr{S}$와 $\mathscr{R}$는 각각 가능한 state와 reward의 집합을 나타낸다. 보통 $\mathscr{R}$는 실수의 집합 $\mathbb{R}$의 부분집합으로 선택하게 된다.

임의의 시점 $t$에서 agent와 environment 간의 상호작용이 어떤 식으로 진행되는지 로컬하게 살펴보자. 시점 $t$ 이전까지의 상황에 의하여 현시점 $t$에 agent는 $s$라는 state에 “처해”있다. 즉, $S_t= a$가 된다. 여기서 state는 실제 문제에 따라 agent의 공간적 위치일 수도 있고 그 어떤 다른 데이터를 포함할 수도 있다. 중요한 포인트 한가지는 각 시점에서 처한 state에 따라 agent가 선택할 수 있는 action이 제한될 수 있다는 것이다. $s$라는 state에서 agent가 취할 수 있는 모든 가능한 action의 집합을 $\mathscr{A}_s$ 혹은 $\mathscr{A}(s)$로 나타내기로 한다. 모든 state $s$에 대해 $\mathscr{A}_s$는 $\mathscr{A}$의 부분집합임을 알 수 있다.

Agent는 시점 $t$에 처한 $s$라는 state 위에서 허용된 action $a$를 $\mathscr{A_s}$로 부터 선택한다. Agent가 $A_t = a$라는 결정을 한 순간 environment는 이에 대응하여 agent를 다음 시점에 해당하는 state $S_{t+1} = s’$에 처하도록 확률적으로 $s’$을 선택하고 해당하는 reward $R_{t+1}=r’$을 agent에게 제시한다. 시점 $t+1$에서 처한 state $s’$과 제공받은 reward $r’$을 관찰한 agent는 그 시점에서의 action $A_{t+1} = a’$을 선택하게 되고 …

Sutton과 Barto의 텍스트에서는 집합 $\mathscr{A}, \mathscr{S}, \mathscr{R}$이 모두 유한집합인 finite MDP만을 다루고 있는데, 우리도 이를 따르기로 한다.

현재까지의 내용을 되짚어보면 각 시점에 agent가 action을 선택할 때, 그리고 environment가 state과 reward를 선택할 떄 확률적 요소가 포함되어 있으므로, 모든 $t \in \{0, 1, 2, \ldots \}$에 대해 $A_t, S_t, R_t$는 확률변수로 생각할 수 있음을 알 수 있다. 여기서 일련의 확률변수

가 Markov chain을 이룬다는 것이 이 모델을 “Markov” decision process로 규정하는 중요한 성질이 된다.

Policy, value function 그리고 MDP에 기반한 강화학습 문제

이제 MDP 라는 프레임웍을 가지고 어떤 문제를 제시하고 해결할 수 있는지 살펴보는 작업을 시작해보자. 어떤 MDP가 주어져 있다고 할 때, 이 모델 하에서 agent가 어떠한 방식으로 행동할 것인지를 확률적으로 기술한 것이 policy의 개념이다. 수학적으로 엄밀하게 말하면 policy는 각 state에서 어떤 action을 확률적으로 선택할 것인지를 지정해주는 함수이다.

모든 $s \in \mathscr{S}$에 대해

는 확률분포함수(확률질량함수)가 된다. 즉, $\sum_{s \in \mathscr{S}} \pi(a \vert s) = 1$. 여기서 한가지 주의해야 할 점은 state $s$에서 선택 가능하지 않은 action $a \in \mathscr{A} - \mathscr{A}_s$에 대해서는 policy의 함숫값이 $\pi(a \vert s) = 0$이 되어야 한다는 사실이다.

이렇게 특정 MDP에 대한 policy가 존재하면 이 모델 하에서 agent가 어떻게 행동해나갈지 확률적으로 완전히 결정된다. MDP 모델을 통한 강화학습 문제의 일반적인 목표는 agent가 이 모델 하에서 행동하면서 얻게 되는 reward의 총합을 극대화 하는 policy를 찾아내는 것으로 정의하게 된다. 즉, reward 총합의 관점에서 “최적의” 혹은 “최선의” policy를 찾아내야 하는 것이다. 그렇다면 최적의 policy는 어떻게 수학적으로 정의할 수 있을까?

이 목표를 달성하기 위한 중요한 방법론이 value 함수를 도입하는 것이다. Value 함수에는 중요한 두가지 종류가 존재하는데, state value 함수와 action value 함수가 그것이다.

State value 함수는

형태의 함수인데 $v$는 $s$라는 state의 value(가치 혹은 값어치)를 의미한다. 다시말해 $s$라는 state에 “위치”하게 되는 것이 어떤 가치를 가지는지 수치로 나타낸 것이 state value 함수의 역할인 것이다.

Action value 함수는

의 형태인데 agent가 $s$라는 state에 위치에 있는 경우 $a$라는 구체적인 action을 취하는 것의 가치를 나타낸다. 다른 말로 하면 $q$는 state $s$에서의 action $a$의 quality를 나타내는 수치다 [5].

그렇다면 대체 이 가치를 어떻게 평가할 것인가? 이에 대해서 optimal control 이론에 기인한 잘 정리된 방법론으로 최적의 가치함수와 최적의 policy의 개념을 도입할 수 있는데, 자세한 내용은 다음 포스트에서 다루기로 한다.

10-armed bandit revisited

이전 포스트 /열 개의 팔을 가진 강도/에서 다루었던 10-armed bandit 문제를 MDP 모델로 기술하는 것으로 이 글을 마치고자 한다.

10-armded bandit 문제에 대한 기억을 떠올려보면 agent가 처한 상황과 그 상황에서 선택할 수 있는 action은 고정되어 있었다. 즉, agent 앞에는 1번부터 10번까지의 슬롯머신이 놓여 있고 그중 하나의 레버를 당기는 action을 선택할 수 있었다. 이를 MDP의 관점에서 해석하면 state가 오직 하나인 모델이다. 즉, $\mathscr{S} = \{s\}$ 이고 모든 시점에서

인 것이다. 이 유일한 state에서 agent가 취할 수 있는 action의 집합은

이 되겠다. 여기서 $i$는 물론 $i$번째 슬롯머신의 팔을 당기는 선택을 의미한다. 각 시점에서 action을 취한 보상으로 받는 reward는 집합 $\mathscr{R} = \mathbb{R}$에서 agent가 취한 action에 따라 기댓값이 $q_*(i)$이고 분산이 $1$인 정규분포에 따라서 확률적으로 주어지게 된다.

참고자료

[1] R. Sutton, A. Barto, Reinforcement leaning: an introduction, second edition (final draft).
[2] Khan Academy, Origin of Markov chains.
[3] D. Silver, RL Course, Lecture 2: Markov Decision Process.
[4] Mathematical monk, Machine learning, 14.1–14.5.
[5] Quora, How was the term “Q-learning” coined?.

읽으시다 오류나 부정확한 내용을 발견하시면 꼭 알려주시길 부탁드립니다. 감사합니다.