[인공지능] Ch16 MDPs

 

MDP

MDP에 대해 알알보기 위해 우선 미로 탐색 인공지능의 예시를 먼저 살펴보자.

왼쪽 그림은 우리가 지금까지 봐온 Deterministic하게 움직이고 있는 것이다.

agent가 정해준 방향으로만 움직이고 있는 것을 확인할 수 있다.

 

그러나 현실에선 다른 방향으로도 agent가 움직이는 것이 자연스럽다.

이렇게 확률적으로 움직이는 걸 오른쪽 그림에서 나오는 Stochastic이라고 한다.

Stochastic은 "확률적" 또는 "비결정적"이라는 의미이다.

 

미로에서 길을 지날 때 여태까지 지나온 길에 대해서는 생각하지 않아도 된다. 

이렇게 오로지 현재의 상태에만 기반해서 행동하는 것을 Markov Transition Model이라고 한다.

 

MDP는 다음과 같이 구성되어 있다.

• 상태(State, S): 환경의 가능한 모든 상태를 나타낸다.
• 행동(Action, A): agent가 취할 수 있는 모든 행동을 정의한다.
• 상태 전이 함수(Transition Function, T(s,a,s′)): 현재 상태 s에서 행동 a를 취했을 때 다음 상태 s'으로 전이될 확률 P(s′∣s,a)를 나타낸다.
• 보상 함수(Reward Function, R(s,a,s′)):특정 상태에서 행동을 취한 결과로 얻는 보상을 정의한다.

Policies

Policy란, MDP에서 agent가 각 상태에서 어떤 행동을 선택할지 나타내는 규칙을 의미한다.

 

π(s): 주어진 상태 s에서 agent가 취해야 할 행동 a를 정의하는 함수이다.

 

수학적으로 π(s):S→A로 나태난다.

- S: 상태 공간(State Space)

- A: 행동 공간(Action Space)

 

즉, MDP는 Optimal Policy π∗:S→A를 찾는 것이 목표이다.

Optimal Policy는 reward의 합을 최대로 만드는 행동을 선택하도록 하는 정책을 의미한다.

 

Discounting

Discounting은 미래 보상의 현재 가치를 계산하는 방법으로, 미래 보상의 중요도를 점진적으로 낮추는 과정이다.

이를 통해 agent가 더 가까운 미래의 보상을 우선시하도록 만든다.

예를 들어 γ = 0.5이고, 보상 시퀀스는 순서대로 1,2,3을 얻는다고 하면 식은 아래와 같다.

U([1,2,3]) = 1 * 1 + 0.5 * 2 + 0.25 * 3

 

Quiz: Discounting

이제 문제를 풀어보자.

문제를 보면 상태 a과 e는 종료 상태이며, 보상은 각각 10과 1이다.

행동은 east(우측), west(좌측), exit이며 Deterministic 전이(행동 결과가 확정적)이다.

 

✅퀴즈1) γ=1일 때 Optimal Policy는?

상태 b, c, d에 대해서 west, east로 갈 때의 utility를 구하는 것이다.

γ=1은 미래 보상도 현재와 동일한 가치를 가짐을 의미한다.

 

- west로 이동하면 전부 보상 10을 얻고, east로 움직이면 전부 보상 1을 얻는다.

 

따라서 γ=1에서는 최대 보상을 위해 모든 상태가 west를 선택한다.

 

✅퀴즈2) γ=0.1일 때 Optimal Policy는?

 

- b의 경우: west로 움직이면 0.1 x 10 = 1, east로 움직이면 (0.1)^3×1=0.001이므로 west로 간다.

- c의 경우: west로 움직이면 (0.1)^2 × 10 = 0.1, east로 움직이면 (0.1)^2 × 1 = 0.01이므로 west로 간다. 

- d의 경우: west로 움직이면 (0.1)^3 × 10 = 0.01, east로 움직이면 0.1 × 1 = 0.1이므로 east로 간다. 

 

✅퀴즈3) 어떤 γ에서 west와 east가 d에서 동일하게 좋은가?

west로 움직일 때의 uitility는 γ^3 x 10, east로 움직일 때의 utility는 γ x 1이므로

 

γ = γ^3 x 10

γ = 1/√10이다.