들어가며
기초는 중요하다. 복잡하고 어려운 최신 AI 논문들을 읽으면서, 이해가 잘 되지 않고 익힘이 느리다면 기초가 부족한 경우가 많다. 대학교 3학년, 처음으로 (비교적) 최신 논문을 읽어보며 벽을 느꼈었던 기억이 아직도 새록새록하다. 그렇기에 정말 기초부터 다시 정리하기 위해 강화학습 포스트를 써 볼 계획이다. 그 처음은 모든 강화학습 알고리즘의 기초가 되는 Markov Decision Process(MDP)이다.
Markov Property
MDP의 정확한 정의는 찾아봐도 잘 나오지 않는다. Markov Property라는 게 있는데, 이 특성(Property)을 따르는 의사 결정 과정(Decision Process)이란다. Markov Property는 쉽게 말하자면 "바로 다음 올 미래를 예측하기 위해서는 과거는 몰라도 되고 현재면 충분하다"로 요약할 수 있다. 1초 뒤를 예측하기 위해서는 10초 전, 5초 전과 같은 정보는 몰라도 되고, 지금 현재의 정보만 있으면 된다는 말이다. 체스 게임에서 현재 보드판은 다음 수를 결정하기 위해 필요한 모든 정보가 있다는 것이고, 로봇의 현재 위치와 속도를 알면 다음 위치는 충분히 예측할 수 있다는 것이다.
추후 설명할 개념이지만, 강화학습은 어떤 문제를 수없이 시행하여 그 문제를 해결하는 최적의 전략(Policy)를 찾는 개념이다. 본문에서는 강화학습으로 해결하고 싶은 문제 상황을 환경(Environment), 환경 내에서 문제를 해결하는 주체를 에이전트(Agent)라는 용어가 등장한다.
MDP의 5가지 주요 구성 요소
MDP는 5가지 주요 구성 요소로 나타낼 수 있다.
- 상태(State), s
- 환경의 현재 상황을 나타내는 정보
- 예를 들면 로봇의 위치, 게임의 보드 상태와 같은 것들이 있다.
- 행동(Action), a
- 에이전트가 취할 수 있는 선택
- 예를 들면 로봇의 이동 방향, 게임에서 선택할 수 있는 수와 같은 것들이 있다.
- 전이 확률(Transition Probability), p(s'|s,a)
- 조건부 확률로 나타나는데, 에이전트가 특정 상태(s)에서 특정 행동(a)을 취했을 때 다음 상태(s')로 이동할 확률이다.
- 보상(Reward), r(s,a)
- 에이전트가 특정 상태에서 특정 행동을 취했을 때 환경으로부터 받는 피드백
- 목표에 근접할 수록 높은 보상, 목표에서 멀어질 수록 낮은 보상을 주어 목표 달성에 대한 신호로 사용된다.
- 할인 계수(Discount Factor), γ
- 현재의 보상(reward)과 미래의 보상의 중요도를 조절하는 계수
- 0~1 사이 값
- γ가 낮을 수록 즉각적인 보상을, 높을 수록 장기적인 보상을 중요시하는 것이다.
MDP의 목표: 최적 전략(Policy) 찾기
Policy(π)는 각 상태에서 어떤 행동을 취할지 결정하는 규칙이다. 여기에는 결정론적(Deterministic) 방법과 확률론적(Stochastic) 방법이 있다.
Deterministic policy는 어떤 상태가 주어지면 그 상태에서 취해야 하는 행동 하나를 결정해준다. Stochastic policy는 어떤 상태가 주어지면 그 상태에서 취할 수 있는 행동들의 확률 분포를 알려준다. 이 확률 분포에서 목표에 가까운 행동일 수록 높은 확률 값을 가지고, 목표에 먼 행동일 수록 낮은 확률 값을 가진다. 이상적으로는 당연히 목표에 가까운 행동만 하면 좋을 것 같지만, 현실에서는 현재 policy가 실제 최적의 policy가 아닐 가능성이 매우 높기 때문에, 이것 저것 해보면서 정답을 찾는 과정이라고 생각하자.
가치 함수(Value Function)
앞서 말했듯 강화학습은 어떤 문제를 수없이 시행하여 그 문제를 해결하는 최적의 policy를 찾는 개념이다. 그렇다면 이를 수식화한다면 어떻게 해야할까? 이를 위해 필요한 것이 Return과 가치 함수(Value Function)이다.
최적의 policy란 무엇일까? 한 에피소드(Episode) 동안 문제 환경을 탐험하면서, 보상을 최대화하는 policy가 최적이라고 할 수 있을 것이다. Return은 특정한 시점에서부터 에피소드가 끝날 때까지 받게 되는 보상들의 총합을 나타낸다. 이때 현재와 미래의 보상의 중요도를 고려하여 할인 계수를 사용하여 합한다. 특정 시점 t에서 Return Gt는 Gt = Rt+1 + γRt+2 + γ2Rt+3 + ... 와 같이 정의된다.
가치 함수(Value Function)는 Return의 기댓값(Expectation)의 두 가지 다른 표현이다.
- 상태 가치 함수(State-Value Function), V(s)
- 특정 상태의 Return의 기댓값
- V(st) = E[ Gt | st ]
- 행동 가치 함수(Action-Value Function), Q(s,a)
- 특정 상태에서 특정 행동을 취했을 때의 Return의 기댓값
- Q(st, at) = E[ Gt | st, at ]
MDP 풀이 방법
주요한 접근 방법으로는 1. 동적 계획법, 2. 몬테카를로(Monte-Carlo) 방법, 3. 시간차 학습(Temporal Difference)이 있다. 이들은 추후 포스팅에서 다룰 예정이다.