[강화 학습] Markov Decision Process <MDP>

1. 강화 학습이란 무엇인가?

- 에이전트가 환경에 대한 사전 지식없이 환경과 상호 작용하여 경험에 의해 정책을 점진적으로 개선해 나아가는 것을 의미합니다.

 

2. 그럼 Planning은 무엇인가?

강화 학습과는 조금은 다른 의미를 가지고 있습니다.

- 에이전트가 주어진 환경에서 시작하여 내부적인 계산을 통해 외부적인 상호작용 없이 정책을 개선해 나아가는 과정을 의미합니다. 

 

강화 학습에서  중요한 내용 중 Exploration 과 Exploitation이 있는데,

2.1. Exploration?

해보지 않은 action (ex. 대표적으로 random action)을 통해 잠재적인 보상을 maximization 하는 과정입니다.

2.2. Exploitation?

경험적으로 가장 높았던 (ex. 평균 보상이 가장 높은 행동) action을 선택하여 따르는 과정입니다.

 

또한, 강화 학습에서는 Prediction과 Control을 우리가 알던 의미와는 사뭇 다르게 구분합니다.

2.3. Prediction?

미래를 evaluate 합니다. 

2.4. Control?

미래를 optimize 합니다.

즉, 기대되는 보상을 예측하고, 그 예측 안에서 가장 큰 보상을 주는 행위를 select 하는 것인 것 같습니다.

 

2.5. Markov Property?

\[\mathbb{P}[\mathrm{S_{t+1}\mid\mathrm{S_t}}]=\mathbb{P}[\mathrm{S_{t+1}\mid S_1,....,S_t}]\]

수식에서 볼 수 있듯이 Markov property에 의하면 미래를 알기 위해 과거는 필요없고 현재에만 의존한다는 내용입니다.

 

2.6. State Transition Matrix?

\[\mathcal{P}_{ss'}=\mathbb{P}[\mathrm{S_{t+1}=s'\mid}\mathrm{S_t=s}]\]

한 상태에서 다른 상태로 천이할 확률입니다.

MDP를 하기전에 조금은 더 간단한 MRP에 대해 알아봅니다.

 

3. Markov Reward Process (MRP)?

$\langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ 인 튜플로 이루어졌습니다.

$\mathcal{S}$는 상태

$\mathcal{P}$는 state transition probability

$\mathcal{R}$은 reward function입니다.

 

3.1. Return, 총 보상이 무엇인가?

$\mathrm{G_t=R_{t+1}+\gamma R_{t+2}+...=\sum\limits_{k=0}^\infty}\gamma^k \mathrm{R_{t+k+1}}$

상태 $S$에서 앞으로 받을 수 있는 누적되는 보상입니다.

 

3.2. Value function?

Value function은 return의 상태 $S$에서 expectation을 취한 것입니다. 

그 상태에 있을 때 앞으로 받을 수 있는 보상의 평균들이라 보면 될 것 같습니다.

 

4. Bellman Equation을 푸는 방법?

\[ \begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix} = \begin{bmatrix} \mathcal{R}_1 \\ \vdots \\ \mathcal{R}_n \end{bmatrix} + \gamma \begin{bmatrix} \mathcal{P}_{11} & \dots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \dots & \mathcal{P}_{nn} \end{bmatrix} \begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix} \]

위와 같이 bellman equation은 linear equation이기에, 선형 대수를 이용하면 해를 구할 수 있습니다.

하지만, $O(n^3)$라는 어마한 계산 비용을 가집니다.

 

5. Markov Decision Process?

MDP는 $\langle \mathcal{S},\mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$의 튜플로 이루어져있다.

$\mathcal{S}$ is a finite set of states 

$\mathcal{A}$ is a finite set of actions

$\mathcal{P}$ is a state transition probability matrix, $\mathcal{P}^{a}_{ss'} = \mathbb{P}[S_{t+1} = s' \mid \mathrm{S_t = s},A_t=a]$

$\mathcal{R}$ is a reward function, $\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t = s,A_t=a]$

 

5.1. Policy?

 

5.2. State Value Function?

 

5.3. Action Value Function?

 

5.4. Bellman Expected Equation?

 

5.5. Optimal Value Function?

 

5.6. Optimal Policy 찾는 법

 

5.7. Bellman Optimality Equation?

 

5.8. Solving the Bellman Optimality Equation?