[Markov Decision Process - 1] 용어 정리

Elements

MDP 뿐만 아니라 control task라는 분야에 사용되는 elements이다.

State($S_t$)

Task environment가 어떤 상황에 놓여있는지 설명하는 모든 관련된 정보이다.

• ex: 체스 (체스판의 어떤 말의 위치 / 남은 시간)

Action($A_t$)

: Agent가 Task 도중 수행하는 행동이다.

• ex: 체스 (각 말의 이동)

: Action은 Task의 State에 기반하여 선택된다.

• 이는 Agent가 State를 관찰하여 State의 특성에 기반하여 Action을 수행한다는 뜻이다.

Reward($R_t$)

: Agent에게 decision making에 대한 effectiveness(효용)를 알려주는 메커니즘이자, Action을 수행한 뒤 Agent가 받는 numerical value이다. 이는 action을 수행한 뒤 즉각적으로 바로 결정되며, rewards가 점점 커질 수록, tasks의 목표들이 더 잘 완수된다.

• ex: 내가 체크메이트를 했을 경우 positive / 당했을 경우 negative / 이외 0

Agent

: State를 관찰하고 각각의 시점에서 Action을 수행하는 주체이다.

Environment

: Agent가 영향은 줄 수 있지만 control하지는 못하는 task의 모든 측면들이다.

• ex: 체스 (남은 시간 / 적의 Move) → Agent가 시간을 조정할 수 는 없다.

Trajectory and Episode($\tau$)

Trajectory

: Agent가 어떤 State에서 다른 State로 이동할 때 generated 되는 Elements 이다.

• 미로에서 Agent 가 3번 이동했을 때의 Trajectory 는 아래와 같다.

 

$$\tau = S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, S_3$$

 

Episode

: 처음(initial state)부터 끝(terminal state)까지의 Trajectory이다.

 

$$\tau = S_0, A_0, R_1, S_1, A_1, R_2, S_2, . . . , R_T, S_T$$

 

Reward vs Return

Reward($R_t$)

: Action에 대한 즉각적인 결과(Short-term)이자, Task에 대한 Goal을 정량적으로 표현한 것이다. Short-term reward는 Long-term reward를 더 안좋게 할 수도 있다. 따라서 우리는 Long-term sum of rewards를 maximize 해야한다.

• ex : 체스에서 상대 말을 잡는 수가 중요한 위치를 빼앗겨 게임을 지게하는 요인이 될 수 있다.

Return($G_t$)

: 특정 시점 t에서 Task가 완료되는 시점까지의 reward들의 합이다.

• Long-term sum of rewards = Expected Return

 

$$ G_t = R_{t+1} + R_{t+2} + R_{t+3} + ... + R_{T} $$

 

Discount factor($\gamma$)

 

$$ G_0 = R_{1} + R_{2} + R_{3} + ... + R_{T} $$

 

5x5 미로에서 목적지로가는 최단거리를 찾는다고 가정하자. 매 이동은 0의 reward를 얻고 오직 목적지에 도착했을 때 1의 reward를 얻는다고 가정했을 때, 최단거리로 가도 결국 1의 return을 얻고 빙빙돌아서 도착해도 1의 return을 얻는다. 하지만 우리의 목적은 최단거리를 얻는 것이다.

 

$$ G_0 = R_{1} + \gamma R_{2} + \gamma^2R_{3} + ... + \gamma^{T-t-1}R_{T} $$

$$ \gamma \in [0, 1] $$

 

이를 해결하기 위해 discount factor($\gamma$)를 rewards에 곱한다. 우리는 미래의 reward의 시점에서 현재 시점(위 수식에서 현재시점 t는 0)을 빼고 다시 1을 뺀 값 만큼 $\gamma$ 를 reward에 곱한다. $\gamma$ 는 0~1사이의 값이므로 여러번 곱할수록 값이 더 작아진다. 이로써 최단 거리일 수록 더 높은 return을 얻는다. $\gamma = 0$ 일 경우 return은 첫번째 reward만 얻게 될 것이며, 매우 근시의 reward만 반영한다. $\gamma = 1$ 일 경우 return은 시간과 관계없이 반영한다.

• cf) $\gamma$는 일반적으로 0.99를 사용한다.

Policy($\pi(s)$)

: Policy는 State를 넣으면 해당 State에서 해야하는 Action을 반환하는 함수이다.

 

$$\pi(s) \quad \quad \pi : S \mapsto A$$

 

Deterministic Policy

: Deterministic Policy인 경우 $\pi(s)$는 state s 일 때, 행해야하는 action 자체를 반환한다.

• 예시: $\pi(s) = a_1$

 

$$ \pi(s) \to a $$

 

Stochastic Policy

: Stochastic Policy인 경우 $\pi(a|s)$는 State s 일 때, Action a 를 행할 조건부 확률을 반환한다.

• 예시: $\pi(s) = [0.3, 0.2, 0.5]$ 일 때, $\pi(a_1|s) = 0.3$ 이다.

 

$$ \pi(s) = [p(a_1),p(a_2),p(a_3),...,p(a_n)]$$

 

Optimal Policy($\pi_*$)

: 즉, 우리는 Sum of discounted rewards(=expected return)를 최대화하는 optimal policy($\pi_*$)를 찾아야한다.