[강화학습] Markov Decision Process & Q-Learning

1. 마르코프 결정 프로세스(MDP)

바닥부터 배우는 강화학습 - 마르코프 결정 프로세스(Markov Decision Process)

마르코프 프로세스(Markov Process)

• 상태 S와 전이확률행렬 P로 정의됨
  • 하나의 상태에서 다른 상태로 전이가 일어남
  • 상태 전이에 각각 확률 존재
  • S4의 경우 종료상태

마르코프 성질(Markov property)

$$ P[S_{t+1} | S_t] = P[S_{t+1} |S_1,S_2, ... S_t] $$

• 상태가 되기까지의 과정은 확률 계산에 영향을 주지 않음.
• 어느 시점의 상태로 다음 상태를 결정할 수 있을 때 마르코프한 상태라고 함.반례) 운전하는 사진(어느 시점의 사진으로는 후진/전진/속도 등을 파악 불가 → 다음 상태 결정 불가능)
• ex) 체스 게임(어느 시점의 사진으로 다음 수 결정 가능)

어떤 현상을 마르코프 프로세스로 모델링하려면 상태가 마르코프 해야하며, 단일 상태 정보만으로도 정보가 충분하도록 상태를 잘 구성해야 함

마르코브 결정 프로세스(MDP)

• 에이전트가 상황마다 액션을 취하면 액션에 따라 상태가 변하고 그에 따라 보상이 주어짐

$$ MDP = (S, A, P, R, \gamma) $$

• S ⇒ 상태 집합
• A ⇒ 액션 집합
• P ⇒ 전이 확률 행렬
  • 현재 상태 s에서 a 를 선택했을 때 다음 상태가 s’가 될 확률
  $$ P^a_{SS'} = P[S_{t+1} = s'|S_t = s, A_t = a] $$
• 보상함수 R
  • 현재 상태 s에서 a를 선택했을 때 받는 보상의 기댓값
  $$ R^a_S = E[R_{t+1} | S_t = s, A_t = a] $$
• 감쇠인자 ${\gamma}$
  • 0 < ${\gamma}$ < 1
  • 미래에 얻을 보상과 당장 얻을 보상의 중요도를 결정
  • 미래에 얻을 보상 값에 ${\gamma}$가 여러번 곱해지며 그 값을 작게 만듬

정책 함수

• 각 상태에서 어떤 액션을 선택할지 결정하는 함수= 상태 s에서 액션 a를 선택할 확률
  • s에서 선택할 수 있는 액션이 a0, a1, a2라고 할 때,
  $$ \pi(a_0|s) = 0.2, \pi(a_1|s) = 0.3, \pi(a_2|s) = 0.5 $$
  • 액션에 대한 확률 부여
• $$ \pi(a|s) = P[A_t = a | s_t = s] $$

상태 가치 함수

• 주어진 상태에서 정책함수로 정한 액션에 따라 행동했을 때 얻을 수 있는 리턴의 기댓값
• s → 끝까지 정책함수 따라서 움직일 때

$$ v_\pi(s) = E_\pi[r_{t+1} + \gamma r_{t+1} + \gamma^2r_{t+1} + ... | S_t = s] = E_\pi[G_t|S_t = s] $$

액션 가치 함수

• 각 상태에서 선택할 수 있는 액션을 전부 평가해보고 가장 보상이 큰 액션 선택
• input ⇒ state 와 action ⇒ action과 상태를 결합해서 평가

$$ q_\pi(s, a) = E_\pi[G_t|S_t = s, A_t = a] $$

• s에서 a를 선택한 뒤 그 뒤로는 정책 함수를 따라서 움직일 때 얻는 리턴의 기댓값

 

2. Q-Learning

Model Free Algorithm

• 기존의 model based algorithm 들은 어떤 상태에서 어떤 행동을 한다고 했을 때, 다음의 상태가 될 확률
• 환경에 대해 알고, 행동에 따른 환경의 변화를 아는 알고리즘
  • 계속 탐험해서 Trail and error를 얻고 policy function을 점차 학습시키는 방향model free algorithm ⇒ agent가 행동을 통해 예상되는 보상의 총합을 최대로 하는 policy function을 찾는 것이 목표

• 환경에 대해 모르고, 환경이 알려주는 다음 상태와 다음 보상을 수동적으로 획득

Q-Learning

• 유한한 마르코프 결정 과정에서 특정 상황해서 특정 행동을 하라는 최적의 policy 를 배우는 것

Markov Decision Process

Q-Value

• 현재 상태로부터 시작해 모든 연속적인 단계를 거쳤을 때 전체 보상의 예측값 극대화
• Q ⇒ 현재 상태에서 취한 행동의 보상(Quality)
• 액션 가치 함수(행동 가치 함수) 기반으로 Q-Value 계산
  • $\gamma$ 는 현재로부터 t 시간 후의 보상에 대한 영향력을 얼마나 줄일지, 즉 현재 상태에 대한 보상의 중요도를 어느정도로 책정할지를 결정하는 값

Q-Learning

• Q 함수가 고정된 임의의 값을 갖고 시작 → 매 time-step마다 Agent가 행동 at를 선택하고, 보상 rt를 받으며 새로운 상태 s(t+1)로 전이하고 Q 값을 갱신
• 이전 값과 새로운 정보의 가중합(weighted sum)을 이용하는 Value Iteration update기법이 핵심

$$ Q(s_{t},a_{t})\leftarrow (1-\alpha )\cdot \underbrace {Q(s_{t},a_{t})} _{\rm {old~value}}+\underbrace {\alpha } {\rm {learning~rate}}\cdot \left(\overbrace {\underbrace {r{t}} _{\rm {reward}}+\underbrace {\gamma } _{\rm {discount~factor}}\cdot \underbrace {\max {a}Q(s{t+1},a)} _{\rm {estimate~of~optimal~future~value}}} ^{\rm {learned~value}}\right) $$