마르코프 결정 과정
강화 학습은 마르코프 결정 과정에 학습 개념을 추가한 것이라고 할 수 있다.
- 마르코프 프로세스(Markov Process)
마르코프 프로세스는 어떤 상태가 일정한 간격으로 변하고, 다음 상태는 현재 상태에만 의존하는 확률적 상태 변화를 의미한다.
즉, 현재 상태에 대해서만 다음 상태가 결정되며, 현재 상태까지의 과정은 전혀 고려할 필요가 없다.
변화 상태들이 체인처럼 엮여 있다고 하여 마르코프 체인(Markov chain)이라고도 한다.
또 다른 마르코프 프로세스의 정의로는 마르코프 특성(Markov property)을 지니는 이산 시간(discrete time)에 대한 확률 과정(stochastic process)이다.
확률 과정은 앞서 살펴보았듯이 시간에 따라 어떤 사건의 확률이 변화하는 과정을 의미하며, 이산 시간은 시간이 연속적이 아닌 이산적으로 변함을 의미한다.
또한, 마르코프 특성은 과거 상태들(S1, …, St-1)과 현재 상태(St)가 주어졌을 때, 미래 상태(St+1)는 과거 상태와는 독립적으로 현재 상태로만 결정된다는 것을 의미한다.
즉, 과거와 현재 상태 모두를 고려했을 때 미래 상태가 나타날 확률과 현재 상태만 고려했을 때 미래 상태가 발생할 확률이 동일하다는 의미입니다.
- 마르코프 체인(Markov Chain)
마르코프 체인은 시간에 따른 상태 변화를 나타내며, 이때 상태 변화를 전이(transition)라고 한다.
마르코프 프로세스에서 상태 간 이동인 전이는 확률로 표현하게 되는데, 이를 상태 전이 확률(state transition probability)이라고 한다.
즉, 시간 t에서의 상태를 s라고 하며, 시간 t+1에서의 상태를 s'라고 할 때 상태 전이 확률은 다음과 같이 수식으로 표현할 수 있다.
상태 전이 확률은 어떤 상태 i가 있을 때 그다음 상태 j가 될 확률을 의미한다.
여기에서 P(A|B)는 조건부 확률로 B가 발생했을 때 A가 발생할 확률을 의미한다.
예를 들어 다음 그림은 병원을 방문한 어느 하루에 대한 마르코프 체인을 표현한 것으로, 이 날의 상태가 병원에서의 대기와 진찰, 독서, 웹 서핑, 취침으로만 구성되어 있다고 가정하면, 다섯 가지 상태가 있는 마르코프 프로세스로 표현할 수 있다.
이때 하나의 상태에서 다른 상태로 이동할 확률의 합은 1을 유지한 상태로, 여러 상태가 연쇄적으로 이어져 있습니다.
예를 들어 대기 → 진찰, 대기 → 독서, 대기 → 웹 서핑으로 진행되는 모든 프로세스의 합은 1이 되어야 한다.
또한, ‘취침’은 하루를 끝마치는 종료 상태에 해당된다.
● 상태 전이 확률 행렬(State transition probability matrix)
상태 전이 확률을 다음과 같이 행렬 형태로 정리한 것을 상태 전이 확률 행렬이라고 한다.
한 가지 주의할 사항은 ‘현재 상태가 바로 이전의 상태로 결정된다’는 말을 오해하면 안 된다.
내용을 글자 그대로 해석하면 현재 상태가 A일 때 다음 상태는 A가 유일하게 결정하는, 다른 경우가 있을 수 없는 것이라고 오해할 수 있다.
그러나 핵심은 ‘유일하게 결정한다’가 아니라 ‘현재 상태는 바로 직전의 상태에만 의존한다’는 점.
다시 말해 이전에 아무리 많은 상태가 있었더라도 다음 상태에 영향을 미치는 것은 지금 현재 상태뿐이라는 것을 암시하며,
지금 현재 상태에서 다음 상태를 결정할 때는 여러 가지 확률 변수가 개입하게 된다.
- 마르코프 보상 프로세스 (Markov Reward Process)
마르코프 보상 프로세스는 마르코프 프로세스에서 각 상태마다 좋고 나쁨(reward)이 추가된 확률 모델이다.
다음 그림과 같이 상태 s에서 s'로 이동했을 때 이동 결과가 좋고 나쁨에 대해 보상(혹은 벌칙)을 주는 것이 마르코프 보상 프로세스이다.
이때 각 상태의 보상 총합을 리턴(return)이라고 한다.
하지만 상태의 정확한 가치를 구하기 위해서는 어느 시점에서 보상을 받을지가 중요.
즉, ‘특정 상태에 빨리 도달해서 즉시 보상을 받을 것인지? 아니면 나중에 도달해서 보상을 받을 것인지?’에 대한 가치 판단이 필요하다.
예를 들어 A가 B에게 돈을 빌려주면, A는 원금과 이자를 합산하여 돌려받는다.
이때 이자는 현재 가치와 미래 가치를 판단하게 해 주는 척도.
(현재 가치)에 (이자: 현재 가치×이자율)을 더하면 (미래 가치)가 된다.
(현재 가치)와 (미래 가치)를 비교하기 위해서는 시간 개념이 들어간다.
(현재 가치)는 t 시간이고 (미래 가치)는 t 시간보다 더 미래의 시간이므로,
미래 가치는 t 시간으로부터 충분히 시간이 지나고, 그에 따른 이자가 붙어야만 현재 가치와 동일해진다.
즉, 미래 가치를 현재 시점으로 보면 현재 가치보다 적은 것.
이를 수식적으로 반영한 것이 할인율(discounting factor, γ)이다.
보통 γ는 0과 1 사이의 값으로 하여 미래 가치를 현재 시점에서의 가치로 변환한다.
그리고 이 할인율이 0이 되어도 미래에 받게 될 보상들이 모두 0이 되면, 바로 다음의 보상만 추구하는 근시안적인 행동을 하게 될 것이다.
반대로 할인율이 1과 가까워질수록 미래 보상에 대한 할인이 적어지기 때문에 미래 보상들을 더 많이 고려하게 되는 원시안적인 행동을 하게 된다.
따라서 할인율이 적용된 리턴(Gt)은 다음 수식을 사용한다.
추가적으로 가치 함수(value function)에 대한 이해도 필요하다.
현재 상태가 s일 때 앞으로 발생할 것으로 기대되는(E) 모든 보상의 합을 가치(value)라고 한다.
즉, 가치 함수는 현재 시점에서 미래의 모든 기대되는 보상을 표현하는 미래 가치라고 할 수 있다.
따라서 강화 학습의 핵심은 가치 함수를 최대한 정확하게 찾는 것이다.
다시 말해 미래 가치가 가장 클 것으로 기대되는 결정을 하고 행동하는 것이 강화 학습의 목표라고 할 수 있다.
그러면 병원을 방문한 어느 하루에 대한 마르코프 프로세스에 보상을 추가해 보겠습니다.
예를 들어 대기에서 독서로 이동할 때의 보상이 추가되었는데, 이때의 보상이 +10이 됩니다.
예시에서 γ=0일 때 ‘웹 서핑’에 대한 가치(value) 값을 -2.4로, ‘진찰’에 대한 가치 값을 1.2로 가정하면 ‘독서’와 ‘대기’에 대한 가치는
“독서” = 10 + 0×[(-2.4×0.3) + (0×0.7)] = 10
“대기” = -2 + 0×[(-2.4×0.1) + (10×0.1) + (1.2×0.8)] = -2
할인율이 0이므로 미래의 보상을 고려하지 않았기 때문에 근시안적인 가치 값으로만 나타난다.
이번에는 할인율이 0.9라고 전제하고 가치 값을 구하면,
‘독서’와 ‘대기’에 대한 가치는 다음과 같이 구할 수 있다.
“독서” = 10 + 0.9×[(-2.4×0.3) + (0×0.7)] = 9.4
“대기” = -2 + 0.9×[(-2.4×0.1) + (9.4×0.1) + (1.2×0.8)] = -0.5
(소수점 둘째 자리에서 반올림)
이번에는 할인율이 1인 경우를 알아볼 텐데, 좀 더 극적인 효과를 위해 ‘웹 서핑’에 대한 가치 값을 -24로, ‘진찰’에 대한 가치 값을 0.3으로 가정해 보자.
“독서” = 10 + 1×[(-24×0.3) + (0×0.7)] = 2.8
“대기” = -2 + 1×[(-24×0.1) + (2.8×0.1) + (0.3×0.8)] = -3.9
(소수점 둘째 자리에서 반올림)
할인율이 1일 때는 모든 미래 가치를 할인 없이 고려하고 있으므로 매우 원시안적인 상태로 가치 값들이 나타난다.
- 마르코프 결정 과정(Markov decision process)
마르코프 결정 과정은 기존 마르코프 보상 과정에서 행동이 추가된 확률 모델이다.
MDP 목표는 정의된 문제에 대해 각 상태마다 전체적인 보상을 최대화하는 행동이 무엇인지 결정하는 것이다.
이때 각각의 상태마다 행동 분포(행동이 선택될 확률)를 표현하는 함수를 정책(policy, π)이라고 하며, π는 주어진 상태 s에 대한 행동 분포를 표현한 것이다.
MDP가 주어진 π를 따를 때 s에서 s′로 이동할 확률은 다음 수식으로 계산한다.
이때 s에서 얻을 수 있는 보상(R)은 다음과 같다.
또한, MDP를 이해하기 위해서는 가치 함수도 이해해야 한다.
MDP에서 가치 함수는 에이전트가 놓인 상태 가치를 함수로 표현한 상태-가치 함수(state-value function)와
상태와 행동에 대한 가치를 함수로 표현한 행동-가치 함수(action-value function)가 있다.
● 상태-가치 함수
MDP에서 상태-가치 함수(vπ(s))는 MRP의 가치 함수와 마찬가지로 상태 s에서 얻을 수 있는 리턴의 기댓값을 의미한다.
하지만 MRP와 차이는 주어진 정책(π)에 따라 행동을 결정하고 다음 상태로 이동한다.
여기에서 ①은 t+1 시점에 받는 보상, 즉, 즉각적 보상이며 ②는 미래의 보상에 할인율이 곱해진 것이다.
주목해야 할 것은 현재 시점(t)의 상태-가치 함수가 바로 다음 시점(t+1)의 상태-가치 함수로 표현된다는 것이다.
● 행동-가치 함수
행동-가치 함수(qπ(s,a))는 상태 s에서 a라는 행동을 취했을 때 얻을 수 있는 리턴의 기댓값을 의미한다.
가치 함수(상태-가치 함수, 행동-가치 함수)를 계산하는 방법은 O(n3)(세제곱 시간) 시간 복잡도가 필요하기 때문에 상태 수가 많으면 적용하기가 어렵다.
이 문제를 해결하는 방법은 다음 네 가지로,
각 방법론은 이전 단계의 단점을 보완하고 학습 효율을 높이는 방향으로 발전되었다.
1. 다이나믹 프로그래밍 (dynamic programming)
마르코프 결정 과정의 상태와 행동이 많지 않고 모든 상태와 전이 확률을 알고 있다면 다이나믹 프로그래밍 방식으로 각 상태의 가치와 최적의 행동을 찾을 수 있습니다.
하지만 대부분의 강화 학습 문제는 상태도 많고, 상태가 전이되는 경우의 수도 많으므로 다이나믹 프로그래밍을 적용하기 어렵습니다.
2. 몬테카를로 (Monte Carlo method)
마르코프 결정 과정에서 상태가 많거나 모든 상태를 알 수 없는 경우에는 다이나믹 프로그래밍을 적용할 수 없었습니다.
몬테카를로는 전체 상태 중 일부 구간만 방문하여 근사적으로 가치를 추정한다.
초기 상태에서 시작하여 중간 상태들을 경유해서 최종(terminal) 상태까지 간 후 최종 보상을 측정하고 방문했던 상태들의 가치를 업데이트한다.
3. 시간 차 학습 (temporal difference learning)
몬테카를로는 최종 상태까지 도달한 후에야 방문한 상태들의 업데이트가 가능하다는 단점이 있다.
시간 차 학습 방식은 최종 상태에 도달하기 전에 방문한 상태의 가치를 즉시 업데이트한다.
즉, 시간 차 학습은 다이나믹 프로그래밍과 몬테카를로의 중간적인 특성을 가지며 본격적인 강화 학습의 단계라고 할 수 있다.
4. 함수적 접근 학습 (function approximation learning)
마르코프 결정 과정의 상태가 아주 많거나, 상태가 연속적인 값을 갖는 경우는 상태-가치 함수나 행동-가치 함수를 테이블 형태로 학습하기 어렵습니다.
함수적 접근 학습 방법은 연속적인 상태를 학습하고자 상태와 관련된 특성 벡터를 도입했습니다.
특성의 가중치를 업데이트하여 가치의 근사치를 찾을 수 있습니다.