AI6 [RL] Dynamic Programming Introduction Dynamic programming, 동적 프로그래밍이란 복잡한 하나의 문제를 여러 개의 소문제로 나눈 후, 각 소문제의 해를 합쳐 문제를 풀어나가는 문제해결 패러다임이다. 동적 프로그래밍은 다음과 같은 2가지 성질을 가진 문제를 풀 때 사용될 수 있다. Optimal substructure Principle of optimality (최적성의 원리)가 적용될 수 있음 문제의 최적의 해가 소문제의 해들로 분해될 수 있음 Overlapping subproblems Subproblems recur many times 문제의 솔루션들은 저장되어 재사용할 수 있음 위 성질을 만족하는 예시 중 하나가 바로 MDP이다. 벨만 방정식은 재귀적으로 분해될 수 있으며, 각 state에 대한 v.. 2023. 6. 21. [RL] Markov Decision Process Markov Process $\mathbf{Definition.}$ Markov State State $S_t$가 다음과 같은 조건을 만족할 경우, $S_t$가 Markov property를 만족한다고 한다. 또는 $S_t$를 Markov state라고 부른다. $$ \begin{align*} P[S_{t+1} | S_t] = P[S_{t+1} | S_1, \cdots, S_t] \end{align*} $$ 즉, 어떤 마르코프 상태 $S_t = s$와 다음 상태 $S_{t+1} = s^\prime$라면, 다음과 같은 확률 값이 정의될 수 있다. $$ \begin{align*} \mathcal{P}_{ss^\prime} = P[S_{t+1} = s^\prime | S_t = s] \end{align*} $.. 2023. 6. 16. 이전 1 2 다음
