강화학습 Markov Decision Process
마르코프 프로세스 (MP)
마르코프 프로세스는 현재 상태가 주어지면, 미래 상태는 과거 상태와 독립적으로 현재 상태에만 의존한다는 개념입니다.
미로 게임: 4x4 그리드 형태의 미로가 있고, 각 칸이 하나의 상태입니다(총 16개 상태). 캐릭터는 각 상태에서 상/하/좌/우로 이동할 수 있지만, 이동할 때 80%는 의도한 방향으로, 20%는 무작위 방향으로 미끄러집니다.
여기서 마르코프 속성은: 캐릭터가 다음에 어디로 이동할지는 오직 현재 위치에만 의존하고, 이전에 어떤 경로로 왔는지는 중요하지 않습니다.
상태 전이 확률(State Transition Probability): P(s'|s) = 현재 상태 s에서 다음 상태 s'로 이동할 확률
마르코프 리워드 프로세스 (MRP)
MRP는 MP에 보상(리워드)을 추가한 것입니다. 각 상태에 도달했을 때 특정 보상을 받습니다.
보상이 있는 미로 게임: 위 미로에 보상을 추가합니다:
- 목표 지점(보물)에 도착하면 +10점
- 함정에 빠지면 -5점
- 매 이동마다 -1점(시간 소모)
이제 각 상태에 있는 것의 가치(밸류)가 생깁니다. 목표 지점 근처의 상태는 높은 가치를, 함정 근처의 상태는 낮은 가치를 가집니다.
보상 함수(Reward Function): R(s) = 상태 s에 있을 때 얻는 즉각적인 보상의 기대값
밸류 함수(Value Function = State Value Function = "이 상태가 얼마나 좋은가?"를 나타냄) : V(s) = R(s) + γ∑P(s'|s)V(s') = "현재 보상 + (할인된) 다음 상태들의 가치의 기대값"
할인된?(=discount factor) V(s) = E[R₀ + γR₁ + γ²R₂ + γ³R₃ + ... | S₀ = s]
discount factor : MRP에서는 미래에 받을 보상의 현재 가치를 계산하기 위해 할인율을 도입합니다. 할인율은 미래의 보상을 현재보다 낮게 평가합니다. 이유는 미래는 불확실하므로, 지금 당장 받는 보상이 먼 미래의 보상보다 더 확실하고, 일반적으로 인간은 지연된 보상보다 즉각적인 보상을 선호한다. 그리고 할인율을 사용하면 무한 시간대에서도 총 보상이 유한한 값으로 수렴합니다.(수학적수렴)
상태 가치 함수(State Value Function) : 표기: V(s) 또는 Vπ(s)으로 하고, 상태 s에서 시작하여 정책 π를 따를 때 기대되는 보상의 합을 말한다.
마르코프 결정 프로세스 (MDP)
MDP는 MRP에 행동(액션)을 추가한 것입니다. 각 상태에서 여러 행동을 선택할 수 있고, 그 행동에 따라 다음 상태로 이동할 확률과 받는 보상이 달라집니다.
MRP는 보상은 있지만 행동 선택이 없어서 진정한 의미의 '학습'이 이루어지기 어렵습니다. MDP에서는 행동 선택을 통해 환경에 영향을 미치고, 이에 따른 보상을 받으며 학습할 수 있습니다. MDP의 목표는 총 보상을 최대화하는 최적 정책(π*)을 찾는 것입니다. 이를 위해 가치 함수(V)와 액션 가치 함수(Q)를 활용합니다.
- 정책(Policy): π(a|s) = P(At = a|St = s)
- "상태 s에서 행동 a를 선택할 확률"
- 정책은 에이전트의 행동 전략을 정의합니다.
- 액션-밸류 함수(Action-value function): Qπ(s,a) = Eπ[Gt|St = s, At = a]
- "상태 s에서 행동 a를 취하고 정책 π를 따를 때 기대되는 보상의 합"
- 특정 상태에서 특정 행동을 취하는 것이 얼마나 좋은지 평가합니다.
- MDP의 구성 요소: ⟨S, A, Ptran, R, γ⟩
- S: 상태들의 집합
- A: 행동들의 집합
- Ptran: 상태 전이 확률 행렬 (행동에 따라 상태가 변화할 확률)
- R: 보상 함수
- γ: 할인율 (미래 보상의 현재 가치)
개념의 확장 관계로 정리를 해보면?
- 마르코프 프로세스(MP)
- 핵심 요소: 상태(State), 상태 전이 확률(Transition Probability)
- 이 단계에서는 보상이나 행동 개념이 없음
- 주요 수식
- P(s'|s) = 상태 s에서 s'로 전이할 확률
- 마르코프 리워드 프로세스(MRP)
- MP + 보상(Reward)
- 이 단계에서 밸류 함수(Value Function)가 처음 등장
- V(s): 특정 상태에서 시작했을 때 앞으로 받을 수 있는 모든 보상의 할인된 합의 기대값
- 주요 수식
- R(s) = 상태 s에서 받는 즉각적인 보상의 기대값
V(s) = E[Rt + γRt+1 + γ²Rt+2 + ... | St = s]
= R(s) + γ∑P(s'|s)V(s')
- R(s) = 상태 s에서 받는 즉각적인 보상의 기대값
- 마르코프 결정 프로세스(MDP)
- MRP + 행동(Action)
- 이 단계에서 액션 밸류 함수(Action Value Function)가 추가로 등장
- Q(s,a): 특정 상태에서 특정 행동을 했을 때 앞으로 받을 수 있는 모든 보상의 할인된 합의 기대값
- 정책(Policy)의 개념도 이 단계에서 중요해짐 (어떤 상태에서 어떤 행동을 선택할지)
- 주요 수식
- P(s'|s,a) = 상태 s에서 행동 a를 취했을 때 상태 s'로 전이할 확률
R(s,a) = 상태 s에서 행동 a를 취했을 때 받는 즉각적인 보상의 기대값
π(a|s) = 상태 s에서 행동 a를 선택할 확률
상태 가치 함수(State Value Function):
Vπ(s) = E[Rt + γRt+1 + γ²Rt+2 + ... | St = s, π]
= ∑π(a|s)[R(s,a) + γ∑P(s'|s,a)Vπ(s')]
액션 가치 함수(Action Value Function):
Qπ(s,a) = E[Rt + γRt+1 + γ²Rt+2 + ... | St = s, At = a, π]
= R(s,a) + γ∑P(s'|s,a)∑π(a'|s')Qπ(s',a')
벨만 최적 방정식(Bellman Optimality Equation):
V*(s) = max_a[R(s,a) + γ∑P(s'|s,a)V*(s')]
Q*(s,a) = R(s,a) + γ∑P(s'|s,a)max_a'Q*(s',a')
- P(s'|s,a) = 상태 s에서 행동 a를 취했을 때 상태 s'로 전이할 확률
밸류 함수는 보상(Reward)이 도입된 MRP부터 등장하고, 액션 밸류 함수는 행동(Action)이 도입된 MDP에서 등장합니다.
MRP에서 상태 전이가 자동으로 일어난다는것은 에이전트가 다음에 갈 상태를 선택할수 없다는것이다. 확률적전이 = 현재 상태에서 다음 상태로의 전이는 미리 정의된 확률에 따라 자동으로 일어난다. 그래서 에이전트는 어떤 상태로 갈지 선택할수 없고, 오직 시스템의 동작에 따라 자동으로 전이된다. 에이전트는 단지 상태 변화를 관찰하고 그에 따른 보상을 받을 뿐이다.
반면에 MDP에서는 에이전트가 각 상태에서 취할 행동을 선택할수 있다. 선택한 행동에 따라 다른 확률로 다음 상태에 도달한다. MRP는 단순히 상태 전이와 보상을 모델링하는 반면, MDP는 여기에 의사결정 요소를 추가하여 에이전트가 환경에 영향을 미칠 수 있게 합니다.
대부분의 실제 강화학습 시스템에서 에이전트는
- 현재 상태 s를 관찰
- 학습된 액션 밸류 함수 Q(s,a)나 정책 π(a|s)를 사용해 행동 선택
- 행동 a를 수행
- 환경으로부터 즉각적인 보상 r을 받음
- 다음 상태 s'로 전이
- 이 경험(s, a, r, s')을 사용해 Q 함수나 정책을 업데이트
중요한 점은, 에이전트가 행동하기 전에 "미래의 보상"을 직접 보지는 못한다는 것입니다. 대신 과거 경험을 통해 학습한 가치 함수(Q 함수)를 통해 각 행동의 예상 가치를 추정합니다.
결론적으로, 에이전트는 직접 보상 함수를 보는 것이 아니라, 학습된 가치 함수를 통해 행동의 가치를 평가하고 결정합니다.