마르코프 의사결정 과정(Markov Decision Process, MDP)은 강화학습에서 중요한 개념으로, 이는 현재의 환경을 수학적으로 모델링하는 방법을 제공합니다. MDP는 관찰, 행동, 보상이라는 세 가지 주요 요소로 구성되며, 이 요소들은 강화학습에서 에이전트가 학습하고 결정을 내리는 데 사용됩니다. 마르코프 속성은 MDP의 핵심적인 특징으로, 간단히 말해 "미래는 오직 현재에만 의존한다"는 것을 의미합니다. 즉, 미래의 상태를 예측하거나 결정할 때 과거의 상황은 중요하지 않으며 오로지 현재의 상태만이 중요합니다. 강화학습에서 에이전트는 이 마르코프 속성을 따릅니다. 에이전트는 현재 관찰되는 환경에서 어떤 행동을 선택할지 결정하고, 그 행동에 따른 보상을 받습니다. 이 과정은 순환적으로 일어나며, 각 순간에서의 결정은 그 이전의 상황에 영향을 받지 않고 오직 그 순간의 상태에 기반하여 이루어집니다. 예를 들어, 에이전트가 어떤 게임을 하고 있다고 할 때, 게임의 특정 시점에서의 선택은 그 이전에 어떤 경로를 통해 왔는지와 상관없이 단지 그 시점에서의 게임 상황에만 기반합니다. 그러므로 각 선택은 그 순간의 게임 상태에 최적화되어 있어야 하며, 이는 에이전트가 최적의 행동 전략을 학습하는 데 중요한 원칙이 됩니다.
강화학습 환경은 크게 두 가지 유형으로 구분됩니다: 완전 관찰 가능한 환경(Fully Observable Environments)과 부분 관찰 가능한 환경(Partially Observable Environments). 완전 관찰 가능한 환경에서는 에이전트가 환경의 모든 정보를 명확하게 알 수 있어 현재의 상태를 완벽하게 인식할 수 있습니다. 반면, 부분 관찰 가능한 환경에서는 일부 정보만 접근 가능하여 에이전트가 환경을 완전히 이해하지 못할 수도 있습니다. 환경의 상태 변화를 설명할 때 사용하는 중요한 개념이 상태 전환 확률입니다. 이는 특정 시점에서 현재 상태가 주어졌을 때, 다음 시점에 다른 상태로 이동할 확률을 나타내며, 이러한 확률들을 행렬로 정리할 수 있습니다. 예를 들어, 현재 상태 s에서 다음 상태 s′로 이동할 확률을 행렬의 원소로 표현하면, 이 행렬을 사용하여 다양한 상태 간의 전환 확률을 한눈에 볼 수 있습니다. 강화학습에서 에이전트가 최적의 행동을 계획하는 방법에는 두 가지 주요 접근법이 있습니다: 모델 기반(Model-based)과 모델-프리(Model-free) 접근법입니다. 여기서 '모델'이라는 용어는 신경망 같은 예측 모델을 의미하지 않고, 오히려 에이전트가 환경의 동작 방식을 이해하고 예측하는 내부적인 표현을 가리킵니다. 모델 기반(Model-based) 접근법: 이 방법에서는 에이전트가 환경의 동작 원리(즉, 상태 전환 확률과 보상 구조)에 대한 모델을 구축하고 이를 사용하여 최적의 행동을 계획합니다. 에이전트는 모델을 통해 다양한 상황을 시뮬레이션하고, 가능한 최선의 결과를 도출하기 위한 전략을 세울 수 있습니다. 모델-프리(Model-free) 접근법: 이 방식에서는 에이전트가 환경의 모델을 명시적으로 구축하지 않습니다. 대신, 에이전트는 경험을 통해 직접 행동하고 결과를 관찰함으로써 학습합니다. 이 방법은 환경의 복잡한 모델을 만들 필요가 없기 때문에 구현이 간단하며, 모델을 만드는 데 필요한 정확한 정보가 부족할 때 유용합니다. 이 두 접근법은 각각의 장단점을 가지고 있으며, 특정 환경이나 상황에 따라 적절한 방법을 선택할 수 있습니다. 각각의 방식은 에이전트가 환경과 상호 작용하며 학습하는 방식을 다르게 설정합니다. Pss' = P(St+1=s' | St=s) 리턴은 마르코프 환경에서 현재상태 S에서 다음 상태 St+1로 진행될때마다 에이전트가 받는 보상의 총합을 말합니다. 강화학습은 t시점이 연속적으로 t+1, r+2...t+n 으로 진행되고, 진행될때마다 많은 상태를 접하게 됩니다. 그리고 현재상태에서 학습이 진행되고 에이전트가 다음 상태로 넘어갈때 받을 수 있는 보상의 조합은 그 경우의 수가 매우 많게 됩니다. 에피소드 시간이 진행될때마다 에이전트의 상태가 변하고 이에 따른 각각의 보상이 출력됩니다. 그래서 보상은 고정된 값이 아닌 상태의 변화에 따라 확률적으로 발생하고 이러한 확률요소를 대표하는 결과로 보상을 기댓값 형태로 표기하게 됩니다. 보상은 R로 표현하고 시간 t에서부터 마르코프 환경 종료 시점까지 얻을 모든 보상의 총합을 리턴이라고 합니다. 상태 S에서 행동 A에 의한 보상 = 기댓값 E[Rt+1 | St=s, At=a] 보상은 이렇게 풀어서 표기할 수 있습니다. 다음엔 리턴값인 G를 표기하자면 다음과 같습니다. Gt = Rt + 감마γ(Rt+1) + 두번째감마γ(Rt+2) + ... 이 수식은 에이전트가 얻는 보상의 합입니다. 여기서 감마 γ라는 새로운 표현이 나옵니다. γ는 할인률(discount rate)이라고 하며 0.0에서 1.0 사이의 실수로 표현할 수 있고, 이 할인률은 연속적인 상태에서 수익이 무한대로 늘어나는 것을 방지하기위해 도입한 것입니다. 할인률 계산은 매 상태 전이가 이루어질수록 즉, St에서 St+1, St+2... 이런 식으로 갈수록 처음 지정한 할인률 γ에 제곱, 세제곱, 네제곱...이런 식으로 무한등비급수 공식으로 정해집니다. 할인률은 가까운 미래의 보상을 더 중요하게 보이도록 하는데, 그 의미는 오늘의 100만원이 10년 후 200만원보다 더 가치가 있다는 것을 표현한 것입니다. 여기서의 할인률은 현실 세계의 인플레이션과 같은 역할을 하는 것으로 보셔도 좋습니다. 결국 이러한 할인률로 인해 미래 보상이 기하급수적으로 줄어든다면 즉시 얻을 수 있는 보상에 더 큰 매력을 느낄 것이고, 또한 MDP상황에서 무의미한 반복적, 움직임을 최소화하면서 목표치에 가장 빨리 도달하게 유도하는 역할을 하고 있습니다. 에이전트는 다음 행동을 확률적으로 결정할 수 있고, 상태 역시 확률적으로 전이될 수 있으므로 에이전트와 환경이 확률적으로 동작할 수 있습니다. 이러한 확률적 동작에 대응하기 위해서는 기댓값, 즉 수익의 기댓값을 지표로 삼아야 합니다.
에이전트의 목표는 매 상태의 행동을 잘 판단해서 리턴을 최대화하는 것입니다. 리턴은 매 회에서 얻게되는 보상의 총합을 지칭합니다. 매 회에서는 상태가 주어지고 이에 따른 에이전트의 행동이 있게 되고 이 행동으로 인한 보상값을 받게 되는데, 이러한 보상값을 모은 것이 리턴이고 이러한 리턴을 최대화하기 위해서 에이전트가 어떤 식으로 행동을 해야하는지를 지칭하는게 정책입니다. 매 회의 상태에서 에이전트가 할수 있는 행동을 최적의 행동으로 결정할 수 있습니다. 최적의 행동을 하기 위해서는 행동확률 함수의 분포를 파악하는게 중요합니다. 이러한 행동확률함수의 분포를 정책이라고 할수 있습니다. π(a|s) = P(At=a | St=s) 이와 같은 수식으로 표현하고, π(a=왼쪽문 | s=현재상태 방안) = 0.8 π(a=오른쪽문 | s=현재상태 방안) = 0.2 이런 식으로 행동확률 함수의 분포를 파악할 수 있습니다. 위와 같은 상황에서 에이전트의 행동이 결정적(또는 탐욕적 greedy)이라면 에이전트는 가장 높은 확률분포를 보이는 왼쪽문으로 나가는 행동을 하게 됩니다. 만약 확률적(epsilon greedy)이라도 대부분은 왼쪽문을 선택할 테지만, 일정 확률로는 탐험의 개념으로 오른쪽 문을 선택할 수도 있습니다. 이와같이 π(a|s) 이 식의 정의는, 상태 S에서 a를 선택할 조건부 확률에서, 정책(policy)가 될 것입니다.
가치함수란 에이전트가 처한 현재 상태로부터 얻을 할인 누적보상의 기댓값입니다. 가치함수의 영어 명칭은 Value function이고 이러한 가치함수를 표현하는 방식은 V(s)와 같이 합니다. V(s) = E[Gt | St = s] 가치함수 = 시점 t까지의 상태(state)에서 보상 Reward의 모든 총합인 Gt의 기댓값(확률)이 됩니다. 쉬운 말로 표현하면, 첫번째 에피소드가 진행되고, 상태 St에서 Sn까지의 시점동안 모든 보상의 총합 Gt를 얻고, 두번째 에피소드가 진행되고, 상태 St에서 Sn까지의 시점동안 모든 보상의 총합 Gt를 얻고, 세번째 에피소드가 진행되고, 상태 St에서 Sn까지의 시점동안 모든 보상의 총합 Gt를 얻고, 여기서 얻어진 모든 Gt를 샘플링합니다. 그러면 다양한 리턴값(Gt)가 나오게 될 것입니다. 다시 위의 식을 풀어서 재미있는 관계를 만들어 낼수 있습니다. V(s) = E[Gt | St = s] = E[Rt+1 + γRt+2 + γ^2 Rt+3 +... | St=s] = E[Rt+1 + γ(Rt+1 + γR t+2 +...)|St=s] = E[Rt+1 + γGt | St=s] 현재의 가치는 미래의 가치로 표현한 점화식 관계라는 걸 알수 있습니다. 이처럼 현재의 가치를 구하는 큰 문제는 상대적으로 작은 문제인 미래의 가치를 이요해 풀이하는 동적 계획법 자료구조를 만족하고 있고 이런 형태의 가치함수를 벨만방정식이라고 부릅니다. 가치함수는 상태에 보상값만 다루었는데, 여기서 상태 뿐 아니라 행동에 대한 가치를 평가하는 것을 액션-가치함수라고 하며 이를 Q함수라고 합니다. Q(s,a) = E[Gt | St = s, At = a] = E[Rt+1 + γQ(s',a') | St=s, At=a] 가치함수는 정책(π)이라는 확률 분포에 종속된 Q함수라는 랜덤 변수의 기댓값과 같습니다. Q함수라는 확률변수에 해당하는 확률이 바로 정책(π)입니다. 그러므로 가치함수를 Q함수와 정책으로 만들어진 형태의 수식으로 표현됩니다. 가치함수 V(s)가 정책(π)이라는 확률 분포에 종속되어 있음을 표현하기위해 가치함수와 Q함수의 아래 첨자에 정책(π)를 표기하게 됩니다. Vπ(s) = Σa∈A π(a|s)Qπ(s,a) 이 식을 시간적 순서에 따라 쉽게 풀이해 보겠습니다. 특정 정책 π 하에서 상태 s의 가치를 계산하는 방법을 설명합니다. 여기서, Vπ(s)는 상태 s에서 시작하여 정책 π를 따랐을 때 기대할 수 있는 누적 보상의 총합입니다. Qπ(s,a)는 상태 s에서 행동 a를 선택하고 그 후에 정책 π를 따를 때 기대할 수 있는 누적 보상입니다. 이 식을 풀이하는 방법을 단계별로 쉽게 설명하기 위해 간단한 예시를 들어보겠습니다: 예시: 미로 찾기 게임 에이전트가 미로 안에서 출구를 찾아가는 게임을 생각해 봅시다. 상태 s는 에이전트의 현재 위치, 행동 a는 "북(N)", "남(S)", "동(E)", "서(W)"로 이동하는 것이 될 수 있습니다. 1. 정책 π 정의하기 에이전트의 정책 π(a∣s)를 각 상태에서 모든 가능한 행동에 대해 동일한 확률을 부여하는 균등 정책이라고 가정해 봅시다. 예를 들어, 어떤 상태 s에서 가능한 행동이 "북", "동", "서" 세 가지라면, 각 행동을 선택할 확률은 모두 1/3이 됩니다. 2. Qπ(s,a) 값 미로의 각 상태에서 각 행동을 취했을 때의 Qπ값을 예측하거나 계산해야 합니다. 예를 들어, 상태 s에서 "북"으로 이동했을 때 출구에 한 걸음 더 가까워진다면, 북 Qπ(s,"북")의 값은 다른 행동보다 높게 설정될 수 있습니다. 3. Vπ(s) 계산하기 이제 각 상태의 가치 Vπ(s)를 계산할 수 있습니다. 모든 가능한 행동에 대해 Qπ(s,a) 값을 π(a∣s)로 가중 평균하여 합산합니다. 수식적 풀이 상태 s에서 가능한 행동이 "북", "동", "서"라고 할 때: 북π("북"∣s)=1/3 동π("동"∣s)=1/3 서π("서"∣s)=1/3 각 행동에 대한 Qπ(s,a) 값이 다음과 같다고 가정해 보겠습니다: 북 Qπ(s,"북")=5 동 Qπ(s,"동")=2 서 Qπ(s,"서")=2 그러면 Vπ(s)는 다음과 같이 계산됩니다: Vπ(s)= 1/3 ×5+ 1/3×2+ 1/3×2= (5+2+2)/3 =3 이렇게 Vπ(s)는 상태 s에서 정책 π에 따라 기대할 수 있는 평균적인 누적 보상을 나타내며, 각 상태마다 이 값을 계산할 수 있습니다. 이는 에이전트가 미래에 어떤 행동을 취할지 결정하는 데 중요한 기준이 됩니다. 직관적으로 설명하자면, 한 개의 상태에서의 가치함수 V(s)에 선택할 수 있는 n개의 Q(s,a) 함숫값이 있습니다. 현재상태 s에서 다음상태 s'으로 넘어가면서 행동 a를 취하고 얻은 Q함수로부터 보상 R를 얻게 됩니다. 다시 Q(s,a)에서 다음 상태 가치함수인 V(s')으로 상태변이 하면서 할인률이 적용됩니다. 이때 V(s')또한 n개만큼의 확률이 있습니다. 가치함수를 정책에 대해 샘플링하고 상태개수가 n개라고 가정하면 가치함수와 보상은 n차원의 벡터 그리고 상태변환 확률함수는 n*n 크기의 행렬로 표현됩니다. n의 갯수를 다시 살펴보겠습니다. 이와같이 계산할때 대상 갯수가 커짐에 따라 계산비용이 기하급수적으로 증가하는 문제를 차원의 저주라 부르는데, 이것을 해결하기위해 벨만방정식을 풀수 있는 실질적 대안인 동적 계획법을 적용하게 됩니다.
동적 계획법 풀이법은 복잡한 문제를 작은 문제로 분리해서 풀이합니다. 각각의 작은 문제를 최적화 가능하고, 이를 합치면 큰 문제의 최적화와 동일하게 됩니다. 대표적인 예시로 피보나치 수열 계산식이 있습니다. 0,1,1,2,3,5,8... 이와 같은 방식으로 마지막 수와 그 바로 전의 수를 합친 수가 다음 수가 되는 방식입니다. 기본 계산식을 살펴보겠습니다. 먼저 함수를 정의합니다. def fib_1(n): 이 함수안에 아래 코드를 작성합니다. if n <= 1: 만약 n이 1보다 작거나 같다면, (0이나 1) return n n을 그대로 반환합니다. else: return fib_1(n-1) + fib_1(n-2) 그 이외에는 여기서 정의한 함수를 다시 불러와 n-1과 n-2를 합친 값을 반환합니다. n이 10이라면 fib_1(9) + fib_1(8)을 호출하여 계산하고, 또 fib_1(8) + fib_1(7)을 호출하여 계산하고, 또 fib_1(7) + fib_1(6)를 호출하여 계산하고....이렇게 반복합니다. 반면, 메모이제이션의 계산식 기본을 알아보겠습니다. fib={} fib[0], fib[1] =0,1 def fib_2(n): global fib if n in fib.keys(): return fib[n] else: fib[n] = fib_2(n-1) + fib_2(n-2) return fib[n] 이 방식이 일반적인 재귀 함수를 사용하는 방법보다 훨씬 빠른 이유는 메모이제이션 때문입니다. 메모이제이션은 한 번 계산된 결과를 저장하고, 같은 계산이 요구될 때 다시 계산하는 대신 저장된 결과를 재사용하는 기법입니다. 이로 인해, 같은 결과를 여러 번 계산하는 시간 낭비를 피할 수 있습니다. 예를 들어, fib_2(5)를 계산할 때 일반적인 재귀 함수는 fib_2(4), fib_2(3), fib_2(2), fib_2(1) 등을 중복해서 여러 번 호출할 수 있습니다. 그러나 메모이제이션을 사용하면, 각 숫자에 대한 피보나치 수는 한 번만 계산되고, 그 결과가 fib 딕셔너리에 저장되어 필요할 때마다 즉시 재사용됩니다. 결과적으로, 메모이제이션을 사용한 이 함수는 더 많은 입력값에 대해서도 매우 빠르게 결과를 제공할 수 있습니다. 이런 특성 덕분에, 메모이제이션은 동적 프로그래밍 기법의 핵심 요소로 널리 사용됩니다. 이와같이 메모이제이션은 마르코프 의사결정 문제(MDP)를 해결할 때 특히 동적 프로그래밍 방식과 결합되어 사용됩니다. 이는 각 상태의 최적의 가치 함수를 계산하는 데 있어서 중복 계산을 방지하고 효율성을 높이는 데 큰 도움을 줍니다. 마르코프 의사결정 문제에서는 각 상태(state)에서의 최적의 행동(action)을 결정하기 위해 가치 함수(value function) 또는 행동 가치 함수(action-value function)를 사용합니다. 가치 함수 V(s)는 특정 정책(policy) 하에 상태 s에서 시작해 얻을 수 있는 기대되는 미래 보상의 합을 나타냅니다. 행동 가치 함수 Q(s,a)는 상태 s에서 행동 a를 취한 후 특정 정책을 따를 때 기대할 수 있는 보상의 합입니다. 동적 프로그래밍과 메모이제이션의 적용 MDP에서 동적 프로그래밍은 Bellman 방정식을 이용하여 이러한 가치 함수들을 재귀적으로 계산합니다. Bellman 방정식은 현재 상태의 가치가 다음 가능한 모든 상태의 가치에 의존한다는 원리를 사용합니다: Vπ(s)=∑a∈A π(a∣s)∑s' P(s′∣s,a)[R(s,a,s′)+γVπ(s′)] 여기서 P(s′∣s,a)는 상태 s에서 행동 a를 취했을 때 상태 s′로 이동할 확률, R(s,a,s′)는 그 결과로 받는 보상, 그리고 γ는 할인 계수입니다. 메모이제이션은 이 계산 과정에서 각 상태의 가치 V(s) 또는 Q(s,a)를 한 번 계산하고 나면, 그 결과를 저장합니다. 이후 같은 상태나 상태-행동 쌍의 가치를 다시 계산할 필요가 있을 때 저장된 값을 재사용합니다. 이렇게 함으로써, 계산량을 크게 줄일 수 있으며, 복잡한 MDP 문제에서도 효율적으로 최적 정책을 찾을 수 있게 됩니다. 메모이제이션의 장점 효율성: 이미 계산된 결과는 다시 계산할 필요가 없어져서 계산 시간이 크게 단축됩니다. 복잡도 감소: 크고 복잡한 상태 공간을 가진 문제에서도 메모이제이션을 사용하면 필요한 계산량을 관리 가능한 수준으로 유지할 수 있습니다. 결과적으로, 메모이제이션은 MDP 문제를 해결하는 동적 프로그래밍 접근법에서 중요한 최적화 기술로 활용됩니다. 동적 프로그래밍과 메모이제이션은 정책 반복(policy iteration)이나 가치 반복(value iteration)과 같은 알고리즘에 통합되어 MDP의 최적 해를 효과적으로 찾을 수 있도록 돕습니다.
벨만 기대방정식의 해를 구하는 과정은 동적 계획법을 이용합니다. 벨만 기대방정식의 해는 가치함수를 최대한으로 끌어내는 정책인 최적 정책 π*(파이스타)와 해당 정책으로 만들어진 가치함수인 최적가치함수 V*입니다. 에이전트는 행동을 하나만 취할 수 있고 그 행동은 합리적일때만 시행하므로 합리적 행동일때 정책의 확률값이 1이고 그 외의 확률값은 0으로 설정하게 되는데, 한 번의 최적가치함수와 최적정책을 바로 알기 어렵습니다. 그래서 계산 가능한 작게 분리하여 해결하는 동적 계획법을 이용하게 됩니다. 한번의 시도로 최적의 가치함수와 최적 정책을 구할 수 없으니 해당 시점마다 최고의 가치함수를 도출하는 정책을 구하고 또 그에 따른 가치함수를 구합니다. 다음 시점에는 이전에 구했던 가치함수를 토대로 또다시 최선의 정책을 구하고 다시 그에맞는 가치함수를 구하는 과정을 반복하여 가치함수와 정책을 업데이트하게 됩니다. 정책평가는 아래와 같은 식으로 표현할 수 있습니다. Vk+1 <- R+γPVk 정책 평가 과정에서 사용되는 식은 강화학습과 마르코프 의사결정 문제에서 중요한 부분입니다. 이 식을 사용하여 특정 정책(policy) 하에서 각 상태(state)의 가치(value)를 반복적으로 계산하고 업데이트합니다. 여기서 정책은 에이전트가 특정 상태에서 어떤 행동을 취할지 결정하는 규칙입니다. Vk : k번째 반복에서 각 상태의 가치를 나타내는 벡터입니다. R: 각 상태에 대한 즉각적인 보상을 나타내는 벡터입니다. γ: 할인 계수(discount factor)로, 미래의 보상을 현재 가치로 환산할 때 사용하는 계수입니다. 이 값은 0과 1 사이입니다. P: 상태 전이 확률 행렬(state transition probability matrix)로, 상태 s에서 행동 a를 취했을 때 다른 상태 s′로 이동할 확률을 나타냅니다. Vk+1 : 업데이트된 가치 벡터로, 다음 반복(k+1)에서의 각 상태의 새로운 가치를 나타냅니다. 정책 평가 과정에서 이 식은 주어진 정책 아래에서 각 상태의 장기적 가치를 계산합니다. 각 반복에서, 모든 상태의 가치는 그 상태에서 받을 수 있는 즉각적인 보상과, 그 상태에서 취할 수 있는 행동으로 인해 가능한 모든 다음 상태의 현재 가치의 기대치를 합산하여 업데이트됩니다. 즉각적 보상 R: 현재 상태에서 취할 수 있는 행동에 따른 즉각적인 보상입니다. 할인된 미래 가치 γPVk : 현재 상태에서 가능한 모든 행동을 고려하여, 그 결과로 도달할 수 있는 다음 상태들의 가치의 합을 할인 계수 γ를 사용하여 현재 가치로 환산합니다. 여기서 PVk 는 각 상태에서 가능한 모든 다음 상태로의 전이 확률과 이러한 상태들의 현재 가치의 곱을 나타냅니다. 이 과정은 k번째의 정책에 대한 가치를 새롭게 구하는 것과 같으므로 정책평가라고 합니다. 정책 업데이트는 정책평가->가치함수 업데이트->정책 업데이트 이와 같은 순서로 진행됩니다. 가치함수는 정책에 따라 취할수 있는 경우의 수가 정해지게 됩니다. 이는 가치함수가 정책에 의존적이라고 할수 있고, 새롭게 업데이트되는 정책 πk+1은 k번 업데이트된 가치함수 Vk를 가장 크게 만드는 정책을 선택합니다. πk+1 <- greedy Vk 그리디 알고리즘(탐욕 알고리즘)이라고 하며 주어진 상황에서 최적의 선택을 할때 무조건 최선의 선택을 하는 옵션만 택하는 알고리즘입니다. 이를 표현할때 π를 π*(파이스타)라고 하고 가치함수 V는 V*로 표현합니다. 이처럼 가치함수와 이를 지배하는 정책의 해를 얻는 과정은 과거와 상관없이 현재 구한 가치함수와 정책을 서로 번갈아가며 업데이트하는 과정을 반복하게 되고, 이는 앞서 살펴보았던 동적 계획법의 메모이제이션과 동일합니다.