1. 강화학습으로 풀 수 있는 문제
Markov Model로 추상화된 환경에서 Prediction과 Control 문제를 풀 수 있다. Prediction이란 Model based 또는 Planning라고 불리며, 여러 번의 시뮬레이션을 통해 해당 State의 가치를 계산하는 것이다. Control은 Reward를 최고로 하는 최고의 policy를 찾는 것이다.
- Policy: State에서 어떤 Action을 취할지에 관한 확률 분포 함수(PDF)이다.
- State: Markov Model에서 노드로 추상화된 상태이다.
- Action: State에서 다른 노드로 이동하기 위해 할 수 있는 행동들의 집합이다.
즉, State에서 Policy를 보고 어떤 Action을 할 확률을 알 수 있다.
위 그림을 예시로 들면
Prediction: 어떤 State에서 예상되는 Reward가 가장 클까? (공부를 하기 위해선 어떤 상태를 유지해야 하는가?)
Control: 해당 상태에서 어떤 선택(Action)을 해야 Reward가 클까?
2. 용어 정리
S: 상태들의 집합.
P: State Transition Probability (상태 천이 확률)어떤 State에서 Action이 일어났을 때 다른 State로 이동하는 확률이다. Transformation Matrix 형태로 나타난다.
R(Reward): 보상의 집합,
$\gamma$: Discount Factor RL의 Prediction을 위해 쓰인다. 추후 posting에서 설명하겠다.
A: 액션의 집합
Environment: 환경은 P(State Transition Probability)와 R(Reward)에 의해 결정된다. MDP에서 2단계 벨만망정식을 풀기 위해 필요한 것들이다. Environment를 알면 MDP를 안다고 할 수 있다. 만약 Environment를 모른다면 Model-free방식을 여러 번의 학습을 통해 알 수 있다. 즉, 학습을 통해 R, P를 계산할 수 있다. S에서 Action을 취해서 어디 가는지 보면 된다.
2. Markov Model
Agent: Environment에서 State를 이동하는 대상이다.
State: Markov Model에서 Node를 담당하는 상태이다.
Markov Assumtion: 과거는 미래에 영향을 미치지 않는다. 통계가 충분하다면, 현재는 과거의 데이터를 함축할 수 있다.
2.1 Makov Process (Markov Chain)
S와 P만 존재한다.
알고리즘 문제해결전략 8.17 두니발 박사의 탈옥문제 참조.
2.2 Hidden Markov Model (HMM)
알고리즘 문제해결전략 9.5 광학 문자 인식 탈옥문제 참조. 비터비 알고리즘으로 음성인식 DNA정보 분석에 사용된다.
2.3 Markov Decision Process (MDP)
(S, P, R, $\gamma$, A) 5가지 요소로 구성된다.
두단계에 거쳐서 State의 변화가 일어난다. Action 그리고 State Transition이다. Action을 취한다고 해서 무조건 해당 노드로 가는 것이 아니라 다른 노드로 갈 수 있다.
2.4 Patially Obserable MDP (POMDP)
Active SLAM이 POMDP 문제이다. observation과 odometry를 정확히 모르는 상태에서, Reward를 줘가면서 정확한 로봇의 위치를 찾는 것이기 때문이다. 로봇이 위치가 변할 때마다 observation과 odometry가 변한다. 최적의 보상을 주는 정책(policy)을 찾는 제어 문제이다.
2.4 Markov Game (Stochastic Game)
Agent가 여러 개인 MDP.
2.5 Patially Obserable Stochastic Game
Agent가 여러개인 POMDP.
2.6 Markov Reward Process (MRP)
MDP의 이전 단계로 (S, P, R, $\gamma$) 4가지 요소로 구성된다. MDP와 다르게 Action이 없다. 그래서 상태에 도착한 순간 Reward를 준다.
