Markov Decision Processes

Markov Processes

Markov Property

현재 state가 주어지면 미래 state는 과거의 정보에 의존하지 않고 현재 state만으로 결정됨.

정의

어떤 상태 $S_t$가 Markov 상태가 되려면 다음 조건을 만족

P[S_t+1 | S_t] : 미래 상태가 현재 상태 $S_t$만으로 결정됨.
P[S_t+1 | $S_1$,$S_2$, … , S_t] : 과거 상태 $S_1$,$S_2$, … ,S_(t−1) 같은 정보를 더 추가해도 결과는 변하지 않음.

Sufficient Statistic :

현재 state는 과거의 모든 정보를 압축해서 필요한 모든 정보를 포함하고 있음.
history는 필요 없으며, 현재 state만으로 미래 예측이 가능.

State Transition Matrix

State Transition Probability (상태 전이 확률)

상태 s에서 다음 상태 s'로 전이할 확률
= 현재 상태 s를 알고 있을 때 다음 상태 s'로 전환될 확률 :

State Transition Matrix P (상태 전이 행렬)

상태 전이 행렬 P : 상태 전이 확률을 모든 상태 쌍에 대해 모아놓은 것

• P의 각 원소 P_ij : 상태 i에서 상태 j로 전이할 확률
• 각 행의 합 = 1 (모든 상태에서 다음 상태로 전이할 확률의 총합은 항상 100%)

Markov Process

Markov Process : memoryless random process.
현재 상태가 주어지면, 미래 상태는 과거 상태와 독립적.

정의

Markov Process(or Markov Chain)는 ⟨S,P⟩ 와 같은 튜플로 표현

S: 상태들의 집합 (state set), 유한(finite)
P: 상태 전이 확률 행렬 (State Transition Probability Matrix)

Example: Student Markov Chain

• 상태(State)
: 원으로 표시된 각 state는 학생이 할 수 있는 활동을 나타냄.

• 전이 확률(Transition Probability)
: 화살표 위의 숫자는 한 state에서 다른 state로 전환될 확률.

ex. 학생이 Class 1에 있을 때 :
Facebook으로 전이할 확률은 0.5.
Class 2로 전이할 확률은 0.5.
현재 state만이 다음 state를 결정하며, 과거 상태는 영향을 주지 않음.
(= Markov Property)

Markov Reward Processes

Markov Reward Process

Markov Chain에 Reward와 Discount Factor을 추가한 것.
→ 각 state에서 미래 state로 전이할 때 보상을 받는 확률 과정.

정의
MRP는 4가지 요소로 이루어진 튜플 : ⟨S,P,R,γ⟩

• S : 상태 집합 (Set of States)
유한한(finite) 상태들의 집합.

• P : 상태 전이 확률 행렬 (State Transition Probability Matrix)
현재 상태 S_t에서 다음 상태 S_t+1로 전이할 확률.

• R : 보상 함수 (Reward Function)
특정 상태 S_t=s에서 다음 상태로 이동할 때 받을 Reward을 의미.

• γ : 할인율 (Discount Factor)
할인율 γ을 사용해 미래 Reward의 현재 가치를 조절.
γ∈[0,1] 이며, 1에 가까울수록 미래 보상을 더 중요하게 여김.

γ가 높으면 → 미래 보상을 중요하게 생각
γ가 낮으면 → 현재 보상을 더 중요하게 생각

Return ($G_t$, 반환값)

특정 시점 t에서부터 시작하여 미래에 받을 모든 보상의 총합.

할인율 γ (0≤γ≤1) 을 거듭 제곱하여 미래 보상의 영향을 조절함.

할인율(Discount Factor, γ)의 의미

• 할인율 γ가 0에 가까우면:
먼 미래의 보상을 거의 무시함.
즉각적인 보상을 선호 ("myopic" evaluation, 근시안적 평가).

• 할인율 γ가 1에 가까우면:
미래의 보상을 현재처럼 중요하게 여김.
장기적인 보상을 고려 ("far-sighted" evaluation, 장기적인 평가).

Return의 역할

강화 학습(RL)에서 에이전트는 가능한 높은 Return을 얻도록 학습.
보상을 최대화하기 위해 현재의 행동이 미래의 Return에 미치는 영향을 학습.
즉각적인 보상 vs. 장기적인 보상 간의 균형 조절

Discount하는 이유

• Avoids infinite returns in cyclic Markov processes
순환 구조에서는 상태가 반복되어 보상이 무한대로 커지는 문제가 발생.
γ<1이면 보상 총합이 유한한 값으로 수렴.

• Uncertainty about the future
미래의 상태는 예측이 어렵고, 불확실성이 크므로 보상을 현재보다 덜 중요하게 평가

• Animal/human behavior shows preference for immediate reward

• γ=1을 사용하면 possible to use undiscounted rewards

Value Function v(s)

현재 특정 상태 s에 있을 때, 앞으로 받을 총 보상의 기댓값

Bellman Equation for MRPs

Bellman Equation : 현재 state의 가치 함수 v(s)를 즉각적인 보상과 미래 상태의 가치 함수로 나누어 표현하는 방정식.

두 개의 요소로 분해

• 즉각적인 보상 R_t+1
현재 상태에서 바로 받는 보상의 기댓값.

• 할인된 미래 보상의 기댓값 γv(S_t+1)
다음 상태에서 받을 가치 함수의 기댓값 v(S_t+1)에 할인율을 곱한 값.

상태 전이 확률을 반영한 Bellman Equation

상태 s에서 다음 상태 s′로 전이할 확률이 존재하는 경우, 벨만 방정식 :

• $R_s$
: 상태 s에서 받는 즉각적인 보상 (Expected Immediate Reward)

• P_ss
: 상태 s에서 상태 s′로 전이할 확률 (Transition Probability)

• v(s′)
: 다음 상태 s′에서의 가치 함수

→ 현재 상태의 가치는 즉각 보상과, 미래 상태의 가치 함수들의 가중합으로 표현.

Example: Bellman Equation for Student MRP

할인율 γ=1 일때,
ex. 특정 state에서 가치 v(s)=4.3의 계산 과정

가치 함수 v(s)

(1) 즉각적인 보상 $R_s$
현재 state에서 받는 보상 $R_s$=-2

(2) 미래 상태 가치의 기대값
상태 $s$에서 두 개의 가능성이 있음:
60% 확률(0.6)로 "Pass" 상태(보상 10)로 이동
40% 확률(0.4)로 "Pub" 상태(보상 0.8)로 이동

(3) 할인율 적용 γ=1
v(s)
= −2 + 0.6×v(Pass)×1 + 0.4×v(Pub)×1
=−2+(0.6×10)+(0.4×0.8)
= 4.32

Bellman Equation in Matrix Form

Bellman Equation의 행렬 표현

v: 상태 가치 함수 벡터 (각 상태의 v(s)를 담고 있는 열 벡터)
R: 즉각적인 보상 벡터 ($R_1$,$R_2$,…,$R_n$)
P: 상태 전이 확률 행렬 (P_ss′)

선형 방정식 형태로 변형

연산 복잡도

행렬의 역행렬 계산 ((I−γP)^−1)의 계산 복잡도는 O(n^3).
→ state의 개수 n이 커질수록 계산 비용이 매우 커지므로 큰 MRP에서는 직접 계산이 어려움.

Markov Decision Process

에이전트(Agent)가 환경(Environment)에서 의사 결정을 수행하는 문제를 모델링하는데 사용.
→ MRP와 달리, MDP에서는 에이전트가 직접 행동을 선택할 수 있음.
강화 학습에서 최적 정책(policy)을 학습하는 모델.

정의

MDP는 5가지 요소로 이루어진 튜플 : ⟨S,A,P,R,γ⟩

• A : 행동 집합
에이전트가 선택할 수 있는 모든 행동(Action) 집합.

MRP vs. MDP

MRP: 상태 S, 보상 R, 전이 확률 P, 할인율 γ 로 구성됨.
MDP: MRP에 행동(Action) 집합 A이 추가됨
→ 즉, 의사결정(Decision-Making)이 가능.

Policies in MDP

정책(Policy) π
: 주어진 상태 s에서 특정 행동 a를 선택할 확률 분포.

• policy은 에이전트의 행동을 완전히 정의함.
→ 에이전트가 어떤 상태에서 어떤 행동을 할지 예측 가능.

• MDP에서 policy은 현재 상태만을 기반으로 함.
policy은 history(과거의 모든 상태)를 기억하지 않고, 현재 상태에만 의존함.
→ Markov Property (마르코프 성질)

정책의 유형

(1) 결정론적 정책 (Deterministic Policy)
특정 상태에서 항상 같은 행동을 선택하는 정책.

f(s) : 상태 s에서 결정론적으로 선택하는 행동.

(2) 확률적 정책 (Stochastic Policy)
특정 상태에서 행동을 확률적으로 선택하는 정책.
ex. 특정 state $s$에서 두 개의 행동을 선택할 수 있을 때:

→ 강화 학습(RL)에서 정책을 최적화하여 보상을 최대화하는 것이 목표.

policy π가 적용된 MDP

MDP에서 정책 π가 결정되면 에이전트는 상태 $S_t$에서 행동을 확률적으로 결정.
→ 행동 $A_t$는 더 이상 선택 변수가 아니라 정책 π에 의해 결정되는 확률 변수.
→ 상태 전이 과정이 확률적으로 결정되므로 MDP가 MRP로 변환됨.

상태 전이 확률 P 및 보상 함수 R의 변환

MDP에서의 기존 상태 전이 확률 :

Value Function