Finite Markov Decision Process - (2) notation

앞서 Markov propery 개념을 이해으니,

이론을 공부하기 전에 notation들을 정의해둘 필요가 있다.

1. MDP dynamics

아래 함수는 현재 state가 $s$로 주어져 있고 $a$라는 action을 취했을 때 결과로 얻는 다음 시점 state가 $s'$, reward가 $r$일 확률이다.

$P(s', r|s,a)=Pr\{S_{t}=s', R_{t}=r|S_{t-1}=s,A_{t-1}=a\}$

이는 같은 $s'$으로 진행하더라도 reward는 다를 수 있다는 점에 착안한다. 확률 개념으로 설명하는 이유는 randomness가 있기 때문이다. Inventory problem을 생각해보자. 어떤 상품이 일 평균 8개를 팔린다고 해서 내일도 8개가 팔릴지는 단정할 수 없다.

즉 현실 세계에서 수요란 확률변수이고 정확한 수요를 개수로 말하기 어려우며 단지 몇 개일 확률만을 안다. 따라서 MDP 문제는 대부분 stochastic이고 $s$에서 $a$를 하면 무조건 $s'$으로 전이되는 확률이 1인 deterministic한 상황은 잘 안 다뤄진다.

2. State-transition probability

아래 함수에서는 좌변에 reward가 빠진 것을 알 수 있다. 이것의 의미는 우변처럼 모든 가능한 reward에 대해서 확률 값들을 다 더해준다는 의미다.

$P(s'|s, a)=\sum_{r \in R}p(s',r|s,a)$

3. State-action pairs

이것은 이전 state가 $s$이고 action $a$를 취했을 때 다음 시점에 얻게 될 reward에 대한 기댓값이다. 다시 Inventory problem을 생각해보면 내가 재고를 얼마나 채웠든 실제로 팔리는 개수도 얻는 reward도 다를 것이므로 기댓값을 생각해볼 수 있다.

$r(s,a) \doteq \mathbb{E}\big[R_{t}|S_{t-1}=s,A_{t-1}=a\big]=\sum_{r \in R}r\sum_{s' \in S}p(s',r|s,a)$

4. State-action-next state triples

이것은 state $s$에서 action $a$를 선택한 다음 $s'$이라는 state로 갔다는 것까지가 조건으로 걸렸을 때 reward의 기댓값을 나타낸다.

$r(s,a,s') \doteq \mathbb{E}\big[R_{t}|S_{t-1}=s,A_{t-1}=a,S_{t}=s'\big]=\sum_{r \in R}r\frac{p(s',r|s,a)}{p(s'|s,a)}$

5. Goal

앞서 MDP 문제는 sequential decision making 문제라고 했고, 그것의 goal은 다음과 같이 정리할 수 있다.

Maximizing the expected value of the cumulative reward received in a long term

그러나 이 문제는 일반적으로 randomness가 있어서 같은 decision을 해도 reward가 항상 같지는 않다. 따라서 이 문제에서 reward를 최대화한다는 것은 기댓값을 최대화한다는 뜻이 된다. 그럼 cumulative, long term이라는 말은 왜 들어갔느냐.

우리가 어떤 decision을 할 때 당장은 reward가 더 많이 벌리지만 장기적으로 봤을 때는 손해인 일들이 꽤 있다. 따라서 이 문제에서는 현재의 decision으로 인해 다음 state가 바뀌니까 현재의 reward를 포기하고 나중에 reward를 더 많이 벌 수 있는 state로 가는 게 더 나을 수도 있다는 뜻이다.

미래의 이익을 위해 현재의 이익을 포기하는 이러한 행위를 투자라 부른다. 어떤 시점 $t$에서 성취하는 goal을 $G_{t}$라 표기하면, 이것은 결국 지금 그리고 앞으로 내가 벌어들일 모든 reward들의 합으로 정의할 수 있다.

$G_{t}=R_{t+1}+\gamma R_{t+2} + \gamma^{2} R_{t+3} + \cdots = \sum_{k=0}^{\infin}\gamma^{k}R_{t+k+1}$

$\gamma$는 discount rate를 뜻한다. 미래에 얻을 수익을 현재 가치로 환산할 때 쓴다. 왜냐하면 현재 내게 100원이 있는 것과 10년 뒤에 내게 100원이 있는 것은 다르기 때문이다.

그리고 위에 수식을 잘 보면 시점을 무한대까지 잡아놨는데 실제로 continuing task도 있지만 앞으로 우리가 주로 다룰 문제는 시점이 유한한 episodic task다.

이 경우에는 decision 과정을 하나의 episode 또는 trial이라고 부른다. 그리고 더 이상 decision을 내리지 않아도 되는 state에 들어갔을 때 terminal state에 들어갔다고 한다.

앞으로 수식이 나올 때마다 이것들을 참고할 일이 있을 것이다.

참고: SUTTON, Richard S.; BARTO, Andrew G. Reinforcement learning: An introduction. MIT press, 2018.
사사: 숭실대학교 산업정보시스템공학과 강창묵 교수님.