[RL] Lecture 2: Markov Decision Processes by David Silver

Minseo Jeong·2025년 5월 15일

RL by David Silver

목록 보기
2/11
post-thumbnail

| 1. Markov Process (MP)

Markov Property

"현재 상태가 미래를 결정한다. 과거는 필요 없다."

P(St+1∣St)=P(St+1∣S1,...,St)P(S_{t+1} | S_t) = P(S_{t+1} | S_1, ..., S_t)
  • 상태는 미래에 대한 충분한 정보를 담고 있어야 한다.

정의: Markov Process

MP=⟨S,P⟩\text{MP} = \langle S, P \rangle
  • SS: 상태 집합
  • PP: 상태 전이 행렬
    → Pss′=P(St+1=s′∣St=s)P_{ss'} = P(S_{t+1} = s' | S_t = s)

예시: 학생 마르코프 체인

  • 상태: Class 1, Class 2, Class 3, Facebook, Pub, Pass, Sleep
  • 상태 간 전이 확률을 시각화 → 상태 전이 행렬로 표현 가능

| 2. Markov Reward Process (MRP)

정의: MRP

MRP=⟨S,P,R,γ⟩\text{MRP} = \langle S, P, R, \gamma \rangle
  • Rs=E[Rt+1∣St=s]R_s = \mathbb{E}[R_{t+1} | S_t = s]
  • γ∈[0,1]\gamma \in [0, 1]: 할인율

보상이 추가된 마르코프 체인

Return

Gt=Rt+1+γRt+2+γ2Rt+3+⋯=∑k=0∞γkRt+k+1G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}
  • 미래 보상에 할인 적용

γ가 작으면 '단기적', 크면 '장기적' 관점의 가치 계산

Value Function

상태 s에서 시작할 때의 기대 return

v(s)=E[Gt∣St=s]v(s) = \mathbb{E}[G_t | S_t = s]

Bellman Equation (MRP용)

v(s)=Rs+γ∑s′Pss′v(s′)v(s) = R_s + \gamma \sum_{s'} P_{ss'} v(s')

또는 행렬로 표현:

v=R+γPv\mathbf{v} = \mathbf{R} + \gamma \mathbf{P} \mathbf{v}

→ 선형 방정식 ⇒v=(I−γP)−1R\Rightarrow v = (I - \gamma P)^{-1} R
단, 계산 복잡도 O(n3)\mathcal{O}(n^3) → 작을 때만 가능

| 3. Markov Decision Process (MDP)

정의: MDP

MDP=⟨S,A,P,R,γ⟩\text{MDP} = \langle S, A, P, R, \gamma \rangle
  • AA: 행동 집합
  • Pss′a=P(St+1=s′∣St=s,At=a)P^a_{ss'} = P(S_{t+1} = s' | S_t = s, A_t = a)
  • Rsa=E[Rt+1∣St=s,At=a]R^a_s = \mathbb{E}[R_{t+1} | S_t = s, A_t = a]

이제는 에이전트가 행동을 선택할 수 있음!

Policy

π(a∣s)=P(At=a∣St=s)\pi(a|s) = P(A_t = a | S_t = s)
  • 상태 s에서 행동 a를 선택할 확률
  • 확률적 또는 결정적 정책

Policy 기반 전이/보상

  • 전이:
Pss′π=∑aπ(a∣s)Pss′aP^{\pi}_{ss'} = \sum_{a} \pi(a|s) P^a_{ss'}
  • 보상:
Rsπ=∑aπ(a∣s)RsaR^{\pi}_s = \sum_{a} \pi(a|s) R^a_s

Value Function in MDP

  • 상태 가치 함수:
vπ(s)=Eπ[Gt∣St=s]v^{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s]
  • 행동 가치 함수:
qπ(s,a)=Eπ[Gt∣St=s,At=a]q^{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]

Bellman Expectation Equations

  • 상태 가치 함수:
vπ(s)=∑aπ(a∣s)[Rsa+γ∑s′Pss′avπ(s′)]v^{\pi}(s) = \sum_{a} \pi(a|s) \left[ R^a_s + \gamma \sum_{s'} P^a_{ss'} v^{\pi}(s') \right]
  • 행동 가치 함수:
qπ(s,a)=Rsa+γ∑s′Pss′a∑a′π(a′∣s′)qπ(s′,a′)q^{\pi}(s, a) = R^a_s + \gamma \sum_{s'} P^a_{ss'} \sum_{a'} \pi(a'|s') q^{\pi}(s', a')

| Optimal Value Functions

최적 상태/행동 가치 함수

  • 최적 상태 가치 함수:
v∗(s)=max⁡πvπ(s)v^*(s) = \max_{\pi} v^{\pi}(s)
  • 최적 행동 가치 함수:
q∗(s,a)=max⁡πqπ(s,a)q^*(s, a) = \max_{\pi} q^{\pi}(s, a)

Bellman Optimality Equations

  • 상태:
v∗(s)=max⁡a[Rsa+γ∑s′Pss′av∗(s′)]v^*(s) = \max_{a} \left[ R^a_s + \gamma \sum_{s'} P^a_{ss'} v^*(s') \right]
  • 행동:
q∗(s,a)=Rsa+γ∑s′Pss′amax⁡a′q∗(s′,a′)q^*(s,a) = R^a_s + \gamma \sum_{s'} P^a_{ss'} \max_{a'} q^*(s', a')

최적 정책

  • 최적 정책:
π∗(s)=arg⁡max⁡aq∗(s,a)\pi^*(s) = \arg\max_a q^*(s, a)
  • 모든 MDP에는 항상 결정적 최적 정책이 존재함

| MDP 확장 개념들

Infinite MDP

  • 상태/행동이 무한 (연속)한 경우
  • HJB 방정식 (Continuous MDP의 수학적 모델)

POMDP (Partially Observable MDP)

  • 상태를 직접 관측할 수 없는 경우
  • 상태 대신 belief state 사용
b(h)=P(St=s∣Ht=h)b(h) = P(S_t = s | H_t = h)

평균 보상 MDP

  • 할인 없이 장기 평균 보상 사용:
ρπ=lim⁡T→∞1TE[∑t=1TRt]\rho^{\pi} = \lim_{T \to \infty} \frac{1}{T} \mathbb{E} \left[ \sum_{t=1}^T R_t \right]

| 정리

항목설명
MP상태만 존재, 확률적 전이
MRP보상 추가됨
MDP행동 선택이 추가됨
정책상태 → 행동 확률 매핑
가치 함수상태/행동의 장기적 가치
최적 정책가치 함수 최대화
profile
Minseo Jeong
로봇 소프트웨어 개발자입니다. AI 공부도 합니다.
이전 포스트

[RL] Lecture 1: Introduction to Reinforcement Learning by David Silver

다음 포스트

[RL] Lecture 3: Planning by Dynamic Programming by David Silver

0개의 댓글