목차
챕터 2. 마르코프 결정 과정
2.1 마르코프 결정 과정 (MDP)이란?
2.2 환경과 에이전트를 수식으로
2.3 MDP의 목표
2.4 MDP 예제
챕터 2. 마르코프 결정 과정
- 밴디트: 에이전트 행동에 따라 문제의 설정 변화 X
- 실제: 에이전트 행동에 따라 문제의 설정 변화 O
- 마르코프 결정 과정 Markov Decision Process (MDP)
2.1 마르코프 결정 과정 (MDP)이란?
- 결정 과정: 에이전트가 환경과 상호작용하면서 행동을 결정하는 과정
- MDP 문제 예시: 그리드 월드
- 에이전트 agent: 로봇
- 주변 environment: 환경
- 보상 reward: 사과를 얻을 때 +1, 폭탄을 얻을 때 -2
- 상태 state: 에이전트의 행동에 따라 에이전트가 처하는 상황이 달라짐
- 타임 스텝 time step:
- 에이전트가 다음 행동을 결정하는 간격
- 특정 시간에 에이전트가 행동, 그 결과 새로운 상태로 전이
- 에이전트와 환경의 상호작용
- 에이전트가 행동 → 상태 변화 → 보상 변화
- 상태 $S_t$에서 행동 $A_t$를 수행, 보상 $R_t$를 받고 다음 상태인 $S_{t+1}$로 전환
2.2 환경과 에이전트를 수식으로
- 상태 전이
- 왼쪽 그림: 에이전트가 ‘반드시’ 왼쪽으로 이동하는 모습 = “결정적 deterministic”
- $s'=f(s,a_)$
- 상태 전이 함수: 상태 s와 행동 a 입력하면 다음 상태를 출력하는 함수
- 오른쪽 그림: 이동을 확률적 stochastic
- $p(s'|s,a)$
- 상태 전이 확률: “현재” 상태 s에서 행동 a를 선택할 확률
- 마르코프 성질 markov property: 현재 정보만 고려하는 성질
- 보상 함수
- 보상 $r(s,a,s')$ : 에이전트가 상태 s에서 행동 a를 수행하여 다음 상태 s’가 되었을 때 얻는 보상
- 가정: 보상은 ‘결정적’으로 주어진다고 가정 (문제 단순화)
- 그림 예시) $r(s = L2, a = Left, s' = LI) = 1$
- 에이전트가 상태 L2에서(s=L2), 행동 Left 선택, 상태 L1로 전이
- 에이전트의 정책
- 정책: 에이전트가 행동을 결정하는 방식
- 에이전트는 “현재 상태”만으로 행동 결정
- 환경의 상태 전이가 마르코프 성질에 따라 이루어지기 때문에
- ‘결정적’ 정책 또는 ‘확률적’ 정책
- 왼쪽 그림
- 결정적 정책(반드시 왼쪽으로 이동): $\alpha = \mu(s)$
- 오른쪽 그림
- 확률적 정책: $\pi(\alpha | s)$
- 상태 s에서 행동 a를 취할 확률
- $\pi(\alpha = Left | s = L3) = 0.4$
- $\pi(\alpha = Right | s = L3) = 0.6$
2.3 MDP의 목표
- 정리
- 에이전트: 정책 $\pi(\alpha | s)$에 따라 행동
- 상태: $p(s'|s,a)$에 의해 다음 상태 결정
- 보상: $r(s,a,s')$가 결정
- MDP 목표: 이 틀 안에서 최적 정책을 찾는 것
- 최적 정책 optimal policy: 수익이 최대가 되는 정책
- 일회성 과제와 지속적 과제
- MDP는 문제에 따라 일회성 과제와 지속적 과제로 나뉨
- 일회성 과제 episodic task
- ‘끝’이 있는 문제
- 예) 바둑 → 승리/패배/무승부 중 하나로 끝
- 에피소드 episode: 시작부터 끝까지의 일련의 시도
- 지속적 과제 continuous task
- ‘끝’이 없는 문제
- 예) 재고 관리 → 끝이 정해져 있지 않고 영원히 지속될 수 있음
- 수익 return
- 에이전트의 목표=수익을 극대화하는 것
- 수익 $G_t = R_t + \gamma R_{t+1}+\gamma^2R_{t+2}+ ...$
- 행동 $A_t$, 보상 $R_t$, 상태 $S_t$
- 수익: 에이전트가 얻는 보상의 합
- 시간이 지날수록 보상은 $\gamma$에 의해 기하급수적으로 줄어듦음
- $\gamma$ 를 할인율, 0.0~1.0 사이의 실수로 설정
- 할인율 도입 이유: 지속적 과제에서 수익이 무한대가 되지 않도록 방지, 가까운 미래의 보상을 더 중요하게 설정
- 상태 가치 함수
- 수익은 “확률적”으로 달라짐
- 에이전트와 환경이 “확률적”으로 동작하기 때문에
- → “수익의 기댓값”을 지표로 삼아야 함
- = 상태 가치 함수 state-value function $v_\pi(s)$
- $v_\pi(s)=E[G_t|S_t=s,\pi]$, $v_\pi(s)=E_\pi[G_t|S_t=s]$
- 최적 정책과 최적 가치 함수
- 최적 정책이란: 모든 상태에서 상태 가치 함수의 값이 다른 어떤 정책보다 큰 정책이 최적 정책
- 그림 2-10과 같이 상태에 따라 우열이 달라지는 경우 → 우열 가리기 불가, 최적 정책 X
- 그림 2-12와 같이 상태가 달라져도 모든 상태에서 더 좋거나 최소한 같은 경우 → 최적 정책 O
- 최적 정책 = ‘결정적 정책’
- $\alpha = \mu_*(s)$
- 상태 S를 입력하면 행동a를 출력하는 함수 $\mu_*$
- 최적 정책의 상태 가치 함수 = 최적 상태 가치 함수 optimal state-value function = $v_*$
2.4 MDP 예제
- 예제: 두 칸짜리 그리드 월드
- 그림 2-14) 에이전트의 정책: 결정적
- 그림 2-15) 에이전트가 50%의 확률로 오른쪽, 나머진 왼쪽으로 이동
- 본 챕터: 그림 2-14 (다음 챕터에서 그림 2-15와 같이 에이전트가 확률적으로 행동하는 경우 다룸)
- 최적 정책
- 최적 정책 = 결정적 정책
- 예제 → 상태 2개, 행동 2개 → 결정적 정책 4개
- 상태 가치 함수
- 할인율 0.9로 가정, 무한등비급수 합 공식 이용
- s=L1, $\mu_1$의 상태 가치 함수: -8
- s=L2, $\mu_1$의 상태 가치 함수: -10
# s=L1, 정책 u1의 상태 가치 함수
V = 1
for i in range(1, 100):
V += -1 * (0.9 ** i)
print(V)
- 각 정책의 상태 가치 함수 그래프
- 정책 $\mu_2$ 가 모든 상태에서 다른 정책들보다 상태 가치 함수의 값이 더 큼
- 정책 $\mu_2$ = 최적 정책
