[RL] Markov Decision Process
앞선 밴디트 문제에서는 에이전트가 어떤 행동을 취하든 다음에 도전할 문제의 설정이 변하지 않았다.
하지만 현실의 문제들 중에는 에이전트의 행동에 따라 상황이 시시각각 변하는 문제가 존재한다.
‘에이전트의 행동에 따라’ 환경의 상태가 변하는 문제 -> 2칸 짜리 그리드 월드 문제
1. Markov Decision Process
결정 과정 : 에이전트가 환경과 상호작용하면서 행동을 결정하는 과정
1.1 구체적인 예
MDP에서는 에이전트의 행동에 따라 상태가 바뀌고, 상태가 바뀐 곳에서 새로운 행동을 하게 된다.
MDP에는 ‘시간’의 개념이 필요하다. 특정 시간에 에이전트가 행동을 취하고 그 결과 새로운 상태로 전이한다. 이때의 시간 단위를 타임 스텝이라고 한다.
1.2 에이전트와 환경의 상호작용
MDP에서는 에이전트와 환경 사이에 상호작용
명심해야 할 사실은 에이전트가 행동을 취함으로써 상태가 변한다.
2. 환경과 에이전트를 수식으로
다음 세 가지를 모두 수식으로 표현한다면 MDP를 공식으로 표현할 수 있다.
- 상태 전이 : 상태는 어떻게 전이되는가?
- 보상 : 보상은 어떻게 주어지는가?
- 정책 : 에이전트는 행동을 어떻게 결정하는가?
2.1 상태 전이
- 결정적 -> 상태 전이 함수
- 확률적 -> 상태 전이 확률
마르코프 성질 : 현재의 정보만을 고려하는 성질
2.2 Reward Function
2.3 에이전트의 정책
- 정책 : 에이전트가 행동을 결정하는 방식
정책에서 중요한 점은 에이전트가 현재 상태만으로 행동을 결정할 수 있다는 것
에이전트는 현재 상태를 보고 행동을 결정하는 데, 행동을 결정하는 방식인 정책은 ‘결정적’ 또는 ‘확률적’인 경우로 나눌 수 있다.
3. MDP의 목표
최적 정책 : 수익이 최대가 되는 정책
MDP 문제는 크게 두 가지로 나뉜다.
- 일회성 과제
- 지속적 과제
3.1 일회성 과제와 지속적 과제
- 일회성 과제 : 끝이 있는 문제. 목표가 있고 그 목표에 도달하면 끝난다. 그 후에는 다시 초기 상태에서 새로운 에피소드가 시작된다.
- 에피소드 : 일회성 과제에서 시작부터 끝가지의 일련의 시도
- 지속적 과제 : 끝이 없는 문제.
3.2 수익
- 수익 : 에이전트가 얻는 보상의 합
Agent의 목표는 수익을 극대화하는 것이다.
할인율
- 지속적 과제에서 수익이 무한대가 되지 않도록 방지하기 위해
- 가까운 미래의 보상을 더 중요하게 보이도록 한다.
3.3 상태 가치 함수
에이전트와 환경이 확률적으로 동작하므로 확률적 동작에 대응하기 위해서는 기댓값, 즉 ‘수익의 기댓값’을 지표로 삼아야 한다.
상태가 $S_t$가 s이고, 에이전트의 정책이 $\pi$일 때 에이전트가 얻을 수 있는 기대 수익
상태 가치 함수
\[v_\pi = \mathbb{E}[G_t \vert S_t = s, \pi]\]3.4 최적 정책과 최적 가치 함수
강화학습의 목표는 최적 정책을 찾는 것이다.
최적 정책이란 무엇일까?
최적을 어떻게 표현할 수 있을까?
상태에 따라 상태 가치 함수의 크고 작음이 달라지는 경우에는 두 정책의 우열을 가릴 수 없다.
두 정책이 우열을 가리려면 하나의 정책이 다른 정책보다 모든 상태에서 더 좋거나 최소한 같아야 한다.
최적 정책 : 다른 정책과 비교하여 모든 상태에서 상태 가치 함수의 값이 더 큰 정책
MDP에서 최적 정책이 적어도 하나 존재한다.(수학적 증명 가능) 그리고 그 최적 정책은 결정적 정책이다.
4. MDP 예제
4.1 백업 다이어그램
백업 다이어그램 : 방향 있는 그래프를 활용하여 상태, 행동, 보상의 전이를 표현한 그래프
4.2 최적 정책 찾기
5. 정리
Reference
Deep Learning from Scratch 4