강화학습 문제와 가치기반 강화학습 문제의 풀이기법

"강화학습 문제"

강화학습의 순차적인 문제를 우리는 Markov Decision Process(마르코프 결정과정), 또는 MDP라고 정의합니다.(Markov Chain)

---

"강화학습의 문제 풀이 방법"

환경에 대해서 알 때 : Dynamic Programming(DP : 동적 계획법)

                    장점 : (상대적으로) 문제를 해결하기 쉬움, 매우 효율적임

                    단점 : 현실적이지 못함

 

환경에 대해서 모를 때 : Monte-Carlo(MC : 몬테 카를로), Temporal Difference(TD : 시간차)

                       장점 : 현실의 문제상황에 적용이 가능

                       단점 : (DP에 비해) 효율성이 떨어짐

---

"마르코프 특성(Markov property)"

"어떠한 상태 $s_{t}$는 Markov 하다"의 정의 :

$$P(s_{t+1} \mid s_{t}) = P(s_{t+1} \mid s_{t}, s_{t-1}, ..., s_{0})$$

현재상태 $s_{t}$를 알면, 역사를 아는 것과 동일한 수준으로 미래 상태를 추론할 수 있다. (미래의 상태는 과거와 무관하게 현재의 상태만으로 결정된다.)

---

"마르코프 과정(Markov Process)"

Markov Process :

• Markov Process(Markov Chain)는 $<S, P>$인 튜플입니다.
  • $S$는 (유한한) 상태의 집합
  • $P$는 상태전이행렬(State Transition Matrix)

---

"상태 천이 행렬(State Transition Matrix)"

현재 상태 $s$에서 다음 상태 $s^{'}$으로 이동할 확률을 $P_{ss'}$ 이라 부르고

$$P_{ss'} \doteq P(S_{t+1} = s^{'} \mid S_{t} = s)$$

상태 천이 행렬(State Transition Matrix)은 모든 현재 상태에서 다음 상태로 이동할 확률을 정의합니다.

$$P = \begin{bmatrix}
P_{11} & \cdot\cdot\cdot &  P_{1n} \\ 
: & \ : & : \\ 
P_{n1} & \cdot\cdot\cdot & P_{nn}
\end{bmatrix}$$

$$P_{ij} : i에서 j로 갈 확률$$

---

"마르코프 보상 과정(Markov Reward Process)"

 

MRP는 MP에 Reward를 추가한 확률 과정입니다.

MRP는 $<S,P,R,\gamma>$인 튜플입니다.

• $S$는 (유한한) 상태의 집합
• $P$는 상태 천이 행렬
• $R$은 보상 함수, $R:S \rightarrow R$(Stochastic / Deterministic일 수 있음)
• $\gamma$는 감가율, $\gamma \in [0,1]$(0 ~ 1사이의 실수값)

---

"리턴 (Return)"

Return은 Agent가 현재 상태로부터 미래에 일을 고려할 수 있게 해주는 장치입니다.

Return $G_{t}$는 현재 시점 $t$부터 전체 미래에 대한 "감가된 보상의 합"

$$G_{t} \doteq R_{t+1} = \gamma R_{t+2} + \gamma^{2}R_{t+3} + \cdot\cdot\cdot = \sum_{t=1}^{\infty }\gamma^{t-1}R_{t}$$

$\gamma = 0$ : 미래에 대한 고려 X

$\gamma \rightarrow 1$ : 미래에 대한 고려가 커짐

$R_{t}$는 확률 변수, 즉 아직 하나의 결정된 값이 아님

"Return을 감가하는 이유?"

\[G_{t} \doteq R_{t+1} = \gamma R_{t+2} + \gamma^{2}R_{t+3} + \cdot\cdot\cdot = \sum_{t=1}^{\infty }\gamma^{t-1}R_{t}\]

1. 감가를 하면 값이 무한히 커지는 것을 방지해서, 수치적으로 안정적입니다.

2. 수학적 분석이 쉬워집니다.

3. "먼 미래는 불확실하다"는 철학을 반영하였습니다.

4. 사람은 먼 미래에 실현되는 이익을 선호하지 않습니다.

하지만, 항상 에피소드가 끝나는 경우에는 $\gamma = 1.0$을 사용하기도 한다.

---

"가치함수(Value Function)"

가치함수 $V(s)$는 현재 상태 s에서 미래의 "감가된 보상의 합"(리턴($G_{t}$))의 기댓값

$$V(s) = E[G_{t} \mid S_{t} = s]$$(현재 $t$의 상태가 $s$일 때, 미래의 기대(평균) 리턴은 얼마일까??)

---

"Bellman Expectation Equation"

$$V(s) = R_{t+1} = E[G_{t+1}\mid S_{t} = s]
\\\  = E[R_{t+1} + \gamma R_{t+1} + \gamma R_{t+2} + \gamma^{2}R_{t+3} + \cdot\cdot\cdot \mid S_{t} = s]
\\\  = E[R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \cdot\cdot\cdot) \mid S_{t} = s]
\\\ (4) = E[R_{t+1} + \gamma G_{t+1} \mid S_{t} = s]
\\\ (5) = E[R_{t+1} + \gamma V(S_{t+1})\mid S_{t} = s]$$

$(4) \rightarrow (5) : E[A] = E[E[A]]$를 활용.

 

"Bellman Expectation Equation"

$$V(s) = E[R_{t+1} + \gamma V(S_{t+1})\mid S_{t} = s]$$

다음과 같이 변경됨

$$V(s) = R(s) + \gamma\sum_{s^{'} \in S_{t+1}}P_{ss^{'}}V(s^{'})$$ ($s$가 유한하다 / $R(s)$가 Deterministic하다를 가정)

"Bellman Expectation Equation"

Bellman Expectation Equation은 선형 연립방정식을 활용해서 표현이 가능합니다.

$$v = R + \gamma Pv$$ 

• $v$는 모든 상태의 value function 값을 담은 벡터.  $v \in R^{n}$($R$은 실수공간을 의미함)
• $R$은 모든 상태의 reward function값을 담은 벡터. $R \in R^{n}$
• $\gamma$은 감가율. $\gamma \in R$(혹은 $\gamma \in R^{1}$로 표현)
• $P$는 상태천이 매트릭스. $P \in R^{n \times n}$

$$\begin{bmatrix}
V(1)\\ 
: \\\
V(n)
\end{bmatrix} = \begin{bmatrix}
R(1)\\ 
:\\ 
R(n)
\end{bmatrix} + \begin{bmatrix}
P_{11} & \cdot\cdot\cdot & P_{1n}\\ 
: & . & :\\ 
P_{n1} & ... & P_{nn}
\end{bmatrix}\begin{bmatrix}
V(1)\\ 
:\\ 
V(n)
\end{bmatrix}$$

"Bellman Expectation Equation의 풀이법"

$$v = R + \gamma Pv \\\ v = R + \gamma Pv \\\ (I - \gamma P)v = R \\\ v = (I - \gamma P)^{-1}R$$

• Bellman Expectaion Equation은 선형 방정식이기 때문에 직접적으로 해를 구하는 것(수식을 만족하는 $v$를 찾는 것)이 가능.
• 하지만 , $n$이 커질수록 직접적으로 문제를 푸는 것이 어려워짐
  • DP, MC, TD 등을 활용해 문제를 풀 수 있습니다.