마르코프 결정 프로세스를 MDP라고 부릅니다. Markov Decision Process의 약자입니다. 여기서 결정과정이란 에이전트가 환경과 상호작용하면서 행동 액션(a)를 결정하는 과정을 의미하는 것으로, 주어 자체가 환경이 아니라 에이전트의 결정 과정이 됩니다. 에이전트의 행동에 따라 변화하는 환경의 상태를 주로 다루게 되는 과정이라고 이해하면 쉽습니다. 강화학습 기초에 나오는 멀티 암드 밴디트 문제는 환경은 고정된 채 확률이 높은 밴딧을 찾는 문제였다면, 마르코프 결정 프로세스는 각 단계마다 에이전트의 액션이 있고, 이런 액션마다 환경이 변하고, 그 변화된 환경에서 에이전트의 행동을 유도하는 결정에 대한 과정이라 보시면 됩니다. 특히 MDP에서는 시간의 개념인 타임스텝(time step)이 적용되는데, 어느 한 시점에 에이전트가 행동을 취하고, 그 다음 시간과 변화된 환경에서의 에이전트의 결정을 해야하는 실시간에 가까운 결정, 환경에 따라 달라지는 결정과정입니다.
MDP에서 에이전트와 환경 사이에 상호작용이 밀접하게 일어납니다. 가장 중요하고 잊지 말아야 할 점은 에이전트가 어떤 행동을 한 이후에는 상태 s가 변한다는 점입니다. 여기서 시간을 t로 표현합니다. 시간이 흐르는 다음단계는 t+1, t+2, t+3,,,으로 표현을 합니다. 한 순간인 t에서의 상태를 St로 표현합니다. 한 순간인 t에서의 에이전트의 행동을 At라고 표현합니다. 한 순간인 t에서의 에이전트 행동으로 인해 받은 보상을 Rt라고 표현합니다. 한 순간의 상태 St에서 에이전트가 행동 At을 수행하면 보상 Rt를 얻고, 다음 상태인 St+1로 전환됩니다. 이런 에이전트와 환경간의 상호작용으로 다음과 같은 전이 상황이 만들어지게 됩니다. =>한 순간인 St 상태에서 에이전트의 At를 수행하면 보상 Rt가 주어지고, 그 다음 상태인 St+1 상태가 됩니다. 이어서 St+1 상태에서 에이전트의 At+1를 수행하면 보상 Rt+1이 주어지고, 그 다음 상태인 St+2 상태가 됩니다. 이어서 St+2 상태에서 에이전트의 At+2를 수행하면 보상 Rt+2이 주어지고, 그 다음 상태인 St+3 상태가 됩니다. ... 이와 같은 전이상태가 시간의 흐름과 환경의 변화, 에이전트의 행동과 보상으로 인해 계속해서 만들어지면서 이어지게 됩니다. 상태의 St (상태전이함수와 상태전이확률) 한 사람이 집 안에 있습니다. 집 밖으로 나가기 위해 2개의 문이 있습니다. 이때 이 사람에게는 왼쪽의 문만 허락된다면 외부로 나갈때 왼쪽의 문만 이용할 것입니다. 이것은 결정적(deterministic)이라고 하고 이것은, 상태 전이가 결정적일 경우 다음 상태 s'(에스 프라임이라고 읽음)는 현재 상태 s와 행동 a에 의해 단 하나의 결정 권한만 남게 됩니다. 따라서 함수로 표현하자면 다음과 같습니다. s' = f(s,a) f(s,a)는 상태 s가 주어지면 행동 a를 하고 다음상태 s'을 출력하는 함수입니다. 이 함수를 가리켜 상태 전이 함수(state transition function)이라고 합니다. 이 결정적 상태전이함수를 결정적이 아닌 확률적으로도 표현할 수 있습니다. 확률적으로 표현하는 식은 다음과 같습니다. p(s'|s,a) 기호 |의 오른쪽에는 조건을 나타내는 확률변수를 기재하는데, 이 함수는 상태 s에서 행동 a를 선택하는 것이 조건이 되고, 이 두가지 조건이 주어졌을 때 s'으로 전이될 확률을 이와같이 나타내게 됩니다. 이 확률에 기반하여 행동을 하게되는 함수를 상태 전이 확률(state transition probability)라고 합니다. 실제 환경에서 사람이 외부로 나가기 위해 반드시 왼쪽 문을 통과해야 한다는 결정적인 행동이 나오리라는 보장은 없는 것이, 환경에 따라 왼쪽 문을 통과할 수도 없는 경우가 있기 때문입니다. 꼭 이것을 결정적으로 표현 해야한다면 왼쪽문으로 나갈 확률이 1.0이고 오른쪽 문으로 나갈 확률이 0으로 표현할 수는 있습니다. 자, 여기서 한번 더 나가 보겠습니다. 한 사람이 외부로 나가기 위한 문이 왼쪽과 오른쪽 두개의 문이 있는데, 파란색 원이 그려진 문만 이용할 수 있다고 한다면, 그리고 처음 마주치는 두개의 문 중 왼쪽 문에 파란색 원이 그려져 있다면 사람은 왼쪽 문으로 나가게 될 것입니다. 그런데 여기서 왼쪽 문으로 나갔더니 복도가 나오고 다시 왼쪽과 오른쪽 문이 더 있고 이를 결정해야 하는 상황이 왔다고 가정하겠습니다. 이 상황은 St+1의 상황이 될 것이고 이 상황에서 그 전 St 상황에 이미 통과해 온 왼쪽과 오른쪽 문은 고려할 대상이 아니게 됩니다. 이처럼 그 전에 어떤 상황을 거쳐왔는지와 상관없이 현재 상태로, 현재의 정보만을 고려하는 성질을 마르코프 성질(markov property)라고 표현합니다. 우리가 앞으로 마주할 MDP는 이러한 마르코프 성질을 만족한다고 가정하고 상태전이와 보상 모델을 만들게 됩니다. 이처럼 마르코프 성질을 이용하는 이유는 문제를 더 쉽게 풀기 위해서이고, 만약 마르코프 성질을 따르지 않는다면 과거의 모든 상태와 행동까지 고려해야 하고 그 양이 많아진다면 감당할 수 없는 데이터 양으로 학습이 어려워 질수 있기 때문입니다.
환경의 상태 전이에서는 현재 상태 s와 에이전트의 행동 a만을 고려해 다음 상태 s'이 결정되고, 보상도 마찬가지로 현재상태 s와 행동 a 그리고 전이된 상태 s'만으로 결정됩니다. 이것이 의미하는 것은 환경에 필요한 정보는 모두 현재 상태에 있으므로, 현재 상태만을 고려해 에이전트가 결정하고 행동을 해야 한다는 것입니다. MDP의 마르코프 성질의 특성은 에이전트에 대한 제약이 아닌, 환경에 대한 제약으로 볼 수 있습니다. 이는 결국 마르코프 성질을 만족하도록 상태를 관리하는 것은 환경이지, 에이전트의 행동 a가 아니라는 의미입니다. 에이전트의 시야에서 보면 최선의 선택을 하기위한 정보가 모두 현재 상태에 담겨 있기 때문에 현재에서 가장 최선이 무엇인지를 결정해야 합니다. 이때 에이전트의 행동을 결정하는 방식인 정책(policy)은 결정적 또는 확률적인 경우로 나눌 수 있습니다. 앞서 사례처럼 사람이 외부로 나가기위해 왼쪽문과 오른쪽 문에서 파란색 원이 그려진 왼쪽 문을 열고 나가야만 한다는 결정적 정책(deterministic policy)을 따라야 한다면 수식은 다음과 같이 표현합니다. 액션 a = μ(s) μ(뮤 라고 발음)는 s인 상태에서는 반드시 행동 a를 반환해야 한다는 함수입니다. 그래서 이런 함수에서는 사람은 어떤 일이 있어도 왼쪽 문을 통해 외부로 나가게 됩니다. 다시 처음으로 돌아와서, 사람이 외부로 나갈때 왼쪽 파란색 원이 그려진 문을 열고 나갈 확률이 0.8이고 오른쪽 문을 열고 나갈 확률이 0.2라면 다음과 같은 함수로 표현합니다. π(a|s) 이 함수는 상태 s에서 행동 a를 취할 확률을 나타냅니다. 위의 확률 상태에 따른 수식을 아래와 같이 풀어서 쓸수도 있습니다. π(a=왼쪽문 | s=현재상태 방안) = 0.8 π(a=오른쪽문 | s=현재상태 방안) = 0.2 앞서 결정적 정책을 확률적 수식으로도 표현 가능하고 이럴때 왼쪽문은 1.0의 확률이 지정될 것이고, 오른쪽 문은 0.0 확률이 지정될 것입니다.
앞의 사례에서 사람인 에이전트가 파란색 원이 그려진 왼쪽 문을 열고 외부로 나가게 되면 보상 1을 받는다고 한다고 하면 보상함수는 다음과 같습니다. r(s=현재상태 방안, a=왼쪽문, s'=외부) = 1 에이전트가 방안인 상태 s에서 왼쪽문을 열고 나가는 a를 하게되어 외부인 s'으로 설계자가 원하는 방향으로 이동하면 보상을 1을 준다는 의미입니다. 이 보상함수에서 다음 상태 s'만 알면 보상이 결정되므로 보상함수를 r(s')으로도 표현할 수 있습니다. 앞으로 나올 MDP이론에서 나오는 벨만 방정식에서 보상 함수를 보상의 기댓값을 반환하도록 설정하면 보상이 결정적일 때와 다름없게 되는 것이지만, 무조건 결정적이라고 하기에는 무리가 있습니다. 하지만 이번 장에서는 쉽게 설명하기 위해 보상을 결정적으로 주어진다고 가정하고 설명했습니다.
지금까지의 과정을 간단히 복습해 보겠습니다. 에이전트는 정책 π(a|s)에 따라 행동합니다. π(행동|상태) = 어떤 상태가 주어졌을때 행동할 확률 그 행동과 상태전이확률 p(s'|s,a)에 의해 다음 상태가 결정됩니다. 어떤 상태 s에서 행동 a를 하면 다음 상태인 s'이 될 확률을 의미합니다. 그 다음 상태 s'에 따른 보상점수를 받게 됩니다. 보상함수 r(s,a,s')으로 표현됩니다. 이 틀 안에서 최적의 정책을 찾는것이 여기서 말하는 MDP의 최종 목표가 됩니다. 최적 정책(optimal policy)란 수익이 최대가 되는 정책을 말합니다. MDP에서 일회성 상태와 연속적 상태가 있습니다. 일회성 과제는 시작과 끝이 명확하게 나뉘어진 에피소드에 따른 과제를 말합니다. 오목을 예로들어 한 판에는 5개의 바둑알을 놓는 사람이 승리하게 됩니다. 승리한 이후에는 초기화를 시켜 바둑판에 알이 없는 상태에서 다시 시작하게 되고, 이때의 한 판을 한개의 에피소드라 표현합니다. 결국 이는 시작과 끝이 명확하고 끝이 나면 초기화가 되는 상태를 말합니다. 반면, 연속적 상태는 에피소드에서 말하는 시작과 끝이 없는 상태를 말합니다. 창고에서 주로 이루어지는 재고관리를 들수 있습니다. 이런 것처럼 시작과 끝이 정해지지 않고 계속해서 연속적으로 상태를 관찰하고 행동인 액션을 해야 하는 상태를 말합니다.
강화학습에서 자주 나오는 리턴은 쉽게 말하면 보상 r로 받는 수익이고, 에이전트의 최종 목표는 MDP 환경에서 이러한 리턴 값을 최대치로 하는 것입니다. MDP의 최종 목표는 최적의 정책을 찾는 것이라 하였고, 에이전트의 최종 목표는 최대의 리턴값을 만드는 것입니다. 시간 t에서의 상태 St에서 에이전트가 정책 π에 따라 행동 At를 한 후, 보상 Rt를 얻고, 그 다음 상태인 St+1로 전이되는 흐름이 이어집니다. 이때 수익(리턴값)은 Gt라고 표현을 하고 이 함수를 살펴보겠습니다. Gt = Rt + 감마γ(Rt+1) + 두번째감마γ(Rt+2) + ... 이 수식은 에이전트가 얻는 보상의 합입니다. 여기서 감마 γ라는 새로운 표현이 나옵니다. γ는 할인률(discount rate)이라고 하며 0.0에서 1.0 사이의 실수로 표현할 수 있고, 이 할인률은 연속적인 상태에서 수익이 무한대로 늘어나는 것을 방지하기위해 도입한 것입니다. 할인률 계산은 매 상태 전이가 이루어질수록 즉, St에서 St+1, St+2... 이런 식으로 갈수록 처음 지정한 할인률 γ에 제곱, 세제곱, 네제곱...이런 식으로 무한등비급수 공식으로 정해집니다. 할인률은 가까운 미래의 보상을 더 중요하게 보이도록 하는데, 그 의미는 오늘의 100만원이 10년 후 200만원보다 더 가치가 있다는 것을 표현한 것입니다. 여기서의 할인률은 현실 세계의 인플레이션과 같은 역할을 하는 것으로 보셔도 좋습니다. 결국 이러한 할인률로 인해 미래 보상이 기하급수적으로 줄어든다면 즉시 얻을 수 있는 보상에 더 큰 매력을 느낄 것이고, 또한 MDP상황에서 무의미한 반복적, 움직임을 최소화하면서 목표치에 가장 빨리 도달하게 유도하는 역할을 하고 있습니다. 에이전트는 다음 행동을 확률적으로 결정할 수 있고, 상태 역시 확률적으로 전이될 수 있으므로 에이전트와 환경이 확률적으로 동작할 수 있습니다. 이러한 확률적 동작에 대응하기 위해서는 기댓값, 즉 수익의 기댓값을 지표로 삼아야 합니다. 벨만 기대방정식을 통해 상태가치 함수를 표현하자면 다음과 같습니다. Vπ(s) = E[Gt | St = s,π] 이처럼 수익의 기댓값을 Vπ(s)로 표기하고 이것을 상태가치함수라 합니다. 이 식의 우변에서 에이전트 정책 π는 조건으로 주어지는데, 정책 π가 변하면 에이전트가 얻는 보상과 총합인 리턴값 수익도 변합니다. 이런 특성을 명시하기 위해 상태가치 함수는 π를 V밑으로 쓰는 방식을 많이 따릅니다. 위의 식을 다음과 같이 쓰기도 합니다. Vπ(s) = Eπ[Gt | St = s] 우변에서 π의 위치가 Eπ로 이동했습니다. 같은 의미로 사용되는 식으로 자주 볼수 있는 식은 두번째 식입니다. π라는 정책이 조건으로 주어져 있음을 나타내고 있습니다. 최적 상태 가치 함수는 강화학습에서 중요한 개념입니다. 이 함수는 주어진 환경의 모든 가능한 정책 중에서 최적의 정책을 따랐을 때, 각 상태에서 얻을 수 있는 최대 예상 누적 보상을 나타냅니다. 즉, 최적 상태 가치 함수는 상태의 최대 가치를 정량화한 것으로, 강화학습에서 에이전트가 달성할 수 있는 최고의 성능을 나타냅니다. 이를 풀어서 설명해 보자면, 먼저 여러개의 정책 π들이 있습니다. π1,π2,π3,π4..... 이런 식으로 표현한다고 했을때, 어떤 상태 St에서는 첫번째 π가 가장 좋은 정책이고 St+13상황에서는 9번째 π가 가장 좋은 정책일 수도 있습니다. 이럴때 모든 각각의 상태 S에서 다른 모든 π들과 비교해서 가장 좋은 π는 존재하게 됩니다. 이러한 비교에 의해 가장좋은 π를 π*로 표현한다면 모든 상태에서 상태가치함수인 Vπ*(s)가 값이 가장 큰 정책이라는 의미가 됩니다. 이러한 비교를 통해 π값을 찾았고 매 상태마다 가장 최고의 π정책은 유일하고 이것을 사용한다고 하면 에이전트가 각 상태에서의 행동이 유일하게 결정됩니다. 이것은 결국 a = μ*(s)와 같이 상태 s를 입력하면 행동 a를 출력하는 함수 μ*(뮤스타)로 나타낼 수 있습니다. 여기서 최적 상태 가치함수를 v* 로 표기합니다. 그런 최적상태 가치함수 수식은 다음과 같습니다. V∗(s) = max a∑s′,r P(s′,r∣s,a)[r+γV∗(s′)] V∗(s): 상태 s에서의 최적 가치. max a : 모든 가능한 행동 a에 대해 최대값을 선택. P(s′,r∣s,a): 상태 s에서 행동 a를 선택했을 때 상태 s′로 이동하고 보상 r을 받을 확률. r: 보상. γ: 할인율, 미래 보상을 현재 가치로 변환하는 데 사용. s′: 다음 상태 의사결정: 최적 상태 가치 함수는 각 상태에서 어떤 행동이 최적인지를 결정하는 데 중요한 기준이 됩니다. 정책 평가: 특정 정책의 성능을 평가하고 최적 정책에 얼마나 가까운지를 판단하는 데 사용됩니다. 정책 개선: 최적 상태 가치 함수를 통해 새로운, 더 좋은 정책을 도출할 수 있습니다. 최적 상태 가치 함수는 최적 정책과 밀접한 관련이 있습니다. 어떤 정책이 최적 상태 가치 함수를 만족시킨다면, 그 정책이 최적 정책이 됩니다. 최적 정책은 모든 상태에 대해 최적의 행동을 정의하는 정책으로, 이 정책을 따를 때 각 상태의 가치는 최적 상태 가치 함수에 의해 결정됩니다. 최적 상태 가치 함수는 강화학습에서 가장 중요한 개념 중 하나로, 에이전트가 학습을 통해 도달하려고 하는 목표를 나타냅니다. 이 함수를 최대화하는 정책을 찾는 것이 강화학습의 궁극적인 목표입니다.