[RL] 마르코프 보상 과정 (MRP) | 마르코프 결정 과정 (MDP)

마르코프 보상 과정 (MRP)

*(마르코프 연쇄)에 ‘보상’과 ‘시간에 따른 보상의 감가율’의 개념이 추가된 것

마르코프 속성을 지닌 시스템의 시간에 따른 상태 변화
상태 집합(S)와 상태 전이 매트릭스(P)로 구성

상태에 전이확률만 주어졌지, 상태 변화가 얼마나 가치가 있는지 모름

MRP은 상태 집합(S), 상태 전이 매트릭스(P), 보상함수(R) 그리고 감가율(r)

상태 변화에 대한 가치를 계산할 수 있음

S(상태 집합): 다루고 있는 ‘환경’이 가질 수 있는 다양한 상태

MRP에서 상태는 유한해야 함 (개수가 정해짐)

*환경: 우리가 다루는 시스템 또는 문제로,
백화점 매출 예측은 ‘고객정보, 매출정보, 재무정보, ..’등이 환경에 해당

P(상태전이 매트릭스): 각각의 상태가 다른 상태로 변할 수 있는 조건부 확률을 매트릭스로 표현

시간 t에서 상태가 s일 때, 시간 t+1에서 상태가 s’이 될 조건부 확률

R(보상함수): 확률의 기댓값(E) 형태로 표현

시간 t에서 s일 때, 시간 t + 1에서 받을 수 있는 보상의 기댓값

위 그림에서

상태 s가 t+1에서 가질 수 있는 상태는 2개(s2, s3)

각 상태 변화에 따른 보상이 r1, r2일 때

보상 함수의 값 = p1r1 + p2r2

시간 t에서 상태가 s1일 때,
보상함수를 통해 구할 수 있는 보상은 ‘그 순간에 받는 보상’만 계산가능

ex) 상태 s1의 보상이 계산되는 시간 = t+1에서 상태 s1의 보상이 계산된다.

시간 t에서는 상태는 s이고, 시간 t+1에서의 상태는 s’이다.

시간이 한 타임스텝 지나 t+1로 이동되고, 상태는 s’로 이동될 때,

상태 s의 보상이 계산되는 것이다.

r(감마): 감가율(할인율)을 의미, 0 ~ 1사이의 값을 가질 수 있음

시간의 흐름에 따라 가치를 얼마의 비율로 할인할지 결정

MRP의 목적

가치를 계산하는 것
이 가치 계산은 ‘현재 가치’로 환산되어야 하고,
보상 함수를 사용해서 한순간의 가치만 계산하는 것이 아닌,
하나의 에피소드 혹은 전체 환경의 가치까지 한 번에 모두 계산

위 처럼 하나의 에피소드 전체 가치를 계산하기 위해서는

에피소드가 끝날 때까지 몇 개의 타임스텝을 진행해야 함 → 이 때 감가율이 필요

감가율을 통해 몇 타임스텝 후에 얻을 수 있는 가치를 현재 가치로 환산하고,

현 시점에서 바라보는 에피소드의 가치를 구할 수 있음

감가율은 현재 보상과 미래 보상을 바라보는 관점과 관계가 있음

r = 0 → 미래 보상을 전혀 고려 X

r = 1 → 현재 보상과 미래 보상을 똑같이 평가

G(반환값): 타입스텝 t에서 계산한 누적 보상의 합계 (감가율로 할인되어 계산)

주로 전체 환경이 아닌, 에피소드 단위로 계산되는데 효율성이나 가치를 반환값을 통해 평가

이 반환값을 극대화할 수 있도록 환경을 설계하는 것이 MRP 목적

반환값 계산식에서 ‘상태 전이 확률’은 고려하지 않음

반환값은 하나의 선택된 경로(에피소드)에 대한 전체적인 보상을 계산하는 방식

즉, 이미 경로가 선택되었으므로 상태전이 확률 사용 X

반환값을 통해 3번째 에피소드가 가장 효율이 좋다는 것을 알게됨

v(상태 가치 함수): 반환값(G)으로 에피소드 하나에 대한 가치를 측정할 수 있다면,

상태 가치 함수는 환경 전체에 대한 가치를 측정할 수 있음 = 상태전이 확률을 같이 고려함

1. 타임스텝 t에서 상태가 s일 때, 상태 가치 함수는 반환값에 대한 기댓값으로 구할 수 있음
   즉, 상태 s에서 다음 상태로 이동할 경우의 수가 2가지라면
   다음 타임스텝에 이동할 수 있는 상태에서 반환값(g1, g2)을 각각 구하고 각 상태로 이동할 수 있는 조건부 확률(p1, p2)을 곱해 더 해주면 (v(s) = p1 * g1 + p2 * g2)
2. Gt 반환값 구하는 수식을 그대로 넣음
3. 다음 타입 스텝의 반환값을 감가율로 묶은 것
4. 다시 이것을 다음 타임스텝의 반환값으로 대치한 것
5. 반환값 G(t+1) 대신에 상태 가치 함수 (v(S+1))을 집어넣음

기댓값을 구하는 상황에서는 반환값 = 상태 가치 함수 같은 역할을 함

벨만 방정식

일반적으로 기댓값을 시그마 기호를 사용한 수열의 합으로 표현하며
현재 상태와 다음 상태의 관계로 나타냄

마르코프 결정 과정 (MDP)

• 핵심

    환경의 가치를 극대화하는 정책을 결정하는 것
    정책? → 행동을 결정하는 확률
    가치를 극대화하는 정책 = 정책을 따라 행동할 때 가치 함수의 결과가 가장 좋음

개념

MRP = 에피소드나 환경 전체의 가치를 계산하는 것이 목적
MDP = 환경의 가치를 극대화하는 정책을 결정

MDP는 “MRP에 행동과 정책”이 추가된 개념

에이전트의 이동

MRP: 에이전트는 타임 스텝에 따라 상태 전이 확률에 영향을 받으며 자연스레 이동 (수동)
MDP: 에이전트는 타임스텝 별로 정책에 따라 행동을 선택하고
상태 전이 확률에 영향을 받아 이동 (능동)

MDP에서 에이전트 라는 용어가 도입된다.

에이전트 = 행위자, 어떤 행동을 하는 주체라는 의미

MDP에서 에이전트는 정책(pie)에 따라 행동(Action)을 다르게 하며

상태는 에이전트가 취한 행동과 상태 전이 확률 (P)에 따라 바뀜

P(상태 전이 매트릭스): 시간 t에서 상태가 s일 때, a의 행동을 할 경우 t+1에서 상태가 s’일 조건부 확률 (MRP는 s → s’에 갈 확률)

R(보상함수): 시간 t에서 상태가 s일 때, a행동을 할 경우 t+1에서 받는 보상의 기댓값

MDP에는 ‘행동(Action)’이 추가되었기 때문에 상태 전이 매트릭스와 보상 함수 또한 행동을 생각

행동이란, 다음 상태에 영향을 미치는 행위로

MDP에서 취할 수 있는 행동의 개수는 상태(S)와 마찬가지로 종류가 정해져 있다.

MRP = 타임스텝 t1에서의 상태는 s1,

타임스텝 t2에서 상태는 s2, s3가 있는데 각각 상태 전이 확률은 0.7, 0.3

타임스텝 t2에서 s2일 확률은 상태 전이 확률과 동일함

MDP 환경에서 s2에 있을 확률 구하기

s1에서 할 수 있는 행동은 a1, a2이다.

행동 a1 → 상태 s2로 이동 | 행동 a2 → 상태 s3로 이동

각각 정책은 a1, a2를 선택할 확률이 각각 0.4와 0.6

에이전트가 정책에 따라 a1을 선택했다고 s2로 가는게 아님

상태 전이 확률을 받기 때문

따라서 정책에 대한 확률과 상태 전이 확률을 각각 곱해서 더해야 함

MDP에서 에이전트의 행동은 오로지 정책에 의해 결정되며

정책은 시간에 따라 변하지 않음 (현재 상태에만 영향 받음)

상태전이 매트릭스(P): 환경에서 상태가 변할 수 있는 조건부 확률을 매트릭스 형태로 나눔

MDP에서 행동이 추가되고, 행동을 결정하는 유일한 요소는 정책(pie)

정책 또한 매트릭스 형태의 조건부 확률

즉, MDP에서 상태가 변한다 = 원래 가지고 있던 상태 전이 매트릭스와 정책의 영향을 동시에 받는다

MDP의 상태 가치 함수 (v(s) = vpie(s)) = 상태가 얼마나 가치있냐

v(s) = vpie(s)는 v(s)에서 가치를 계산할 때 정책이라는 요소를 하나 더 고려한 것 뿐

pie에 의존적 (정책)1029

행동 가치 함수 (Q)

선택할 수 있는 여러 가지 행동 중에 하나를 선택했을 때의 가치를 계산
하나의 행동(a)을 했을 때 그 가치가 어떻게 되는지 계산

행동가치 함수는 내가 선택한 행동의 가치를 계산하는 함수,

상태가치 함수는 특정 상태의 가치를 계산하는 함수

MDP에서 하나의 상태에서 다른 상태로 이동하기 위해서는 상태 전이 메트릭스와 함께 행동을 선택할 확률, 즉 정책을 같이 고려해야 함

1. 행동 가치 함수를 사용해서 상태 가치 함수를 구하기 위해서는
   정책에 대한 기댓값, 즉 평균을 구해야 함
2. 상태 전이 매트릭스에서 모든 행동을 고려하는 것이 아니라 하나의 행동만을 고려하는 것