[강화학습] 강화 학습이란?(마르코프 결정 프로세스)

들어가며

연구실에서 강화학습 기반 타임 슬롯 할당 기법에 대한 연구를 진행하고 있다. 이쪽 바닥에서 강화학습, 특히 DQN, DDPG 등 Q러닝 계열 강화학습 기법이 자주 쓰이고 있는 모양이다.

아무튼 간에 결국 강화학습을 배워야 하는 처지에 이르렀으니, 이번 포스팅에서는 간단하게 강화학습이 무엇인지 맛만 살짝 보자.

1. 강화학습

머신러닝의 한 분야로, 어떤 행동을 수행하는 에이전트, 에이전트가 상호작용하는 대상인 환경, 행동의 결과를 평가하여 에이전트에게 주어지는 보상의 세 개념을 중심으로 학습을 진행한다.

어떻게 동작하는가

1. 에이전트는 환경에서 어떤 행동을 진행한다.
2. 그 행동의 결과로 환경은 에이전트에게 보상을 제공한다. 보상은 긍정적일 수도, 부정적일 수도 있다.
3. 에이전트는 앞서 받은 보상을 반영하여 다음에 진행할 행동 전략을 세운다.
4. 위 단계를 반복하면 에이전트는 환경에서 가장 나은 행동 전략을 세울 수 있다.

...?

이렇게만 보면 너무 두루뭉술하다. 하지만 조금 더 깊은 이해를 위해서는 마르코프 결정 프로세스를 이해해야 한다.

2. 마르코프 결정 프로세스(MDP: Markov Decision Process)

• 의사 결정 과정을 모델링하는 수학적 틀
• 다이나믹 프로그래밍, 강화 학습에서의 최적화 문제에 사용

용어 설명

상태: State, $S$

• 에이전트가 인식할 수 있는 환경의 모든 가능한 상황
• 미래의 상태는 오직 현재 상태와 행동에만 의존하여야 함
  = 마르코프 성질을 만족해야 함

행동: Action, $a$

• 에이전트가 상황 $S$에서 취할 수 있는 모든 조치

보상 함수: Reward Function, $R(S, a)$

• 에이전트가 상황 $S$에서 취한 행동 $a$에 대한 보상 함수

할인 계수: Discount Factor, $γ$

• 미래의 보상 $R$을 현재 시점에서의 가치로 환산할 때 사용하는 계수
• 미래의 보상 $R$을 얼마나 중요하게 간주할지 결정
• $0 ≤ γ ≤ 1$

정책: Policy, $π$

• 에이전트가 어떤 상태에서 어떤 행동을 취할지 결정하는 규칙

가치 함수: Value Function, $V(S, a)$

• 어떤 정책 $π$이 적용된 에이전트가, 상태 $S$에서 시작하여 얻을 수 있는 누적 보상 $R$의 기대치

Q-함수: Q-Function, $Q(S, a)$

• 어떤 정책 $π$이 적용된 에이전트가, 어떤 상태 $S$에서 시작하여 어떤 행동 $a$를 취한 경우 얻을 수 있는 누적 보상 $R$의 기대치

상태 전이 확률: State Transition Probabillity: $P(s'|s, a)$

• 현재 상태 $S$에서 어떤 행동 $a$를 취했을 때, 다음 상태 $S$로 전이될 확률

마르코프 결정 프로세스의 정의

상태 공간 $S$,
행동 공간 $A$,
전이 확률 $P_a(s, s') = Pr(s_{t+1}=s'|s_t=s, a_t=a)$,
보상 함수 $R(s, s')$: 상태 $s$에서 행동 $a$로 인해 상태 $s'$로 전이할 경우 받는 즉각적 보상의 기댓값,
할인 계수 $γ$, $0 ≤ γ ≤ 1$에 대하여,

$MDP≡(S, A, P, R, γ)$

에이전트의 정책 $π$를 구하는 확률적 제어 과정

3. Q-learning

• 마르코프 결정 프로세스의 틀 안에서 작동하는 강화학습의 한 종류
• 상태 $S$와 행동 $A$으로 구성된 쌍 $(S, A)$에 대한 가치: Value를 추정
  - 가치의 추정치 $V_{est}$에 대하여 $V_{est} = Q-value$

어떻게 동작하는가

Q-learning에서는 상태 $S$, 행동 $A$의 상태-행동 순서쌍과 그것에 대한 $Q-value$를 담은 Q-table을 이용한다.
Q-table에 담긴 $Q-value$는 다음 업데이트 규칙을 통해 조정된다.

$Q(s,a) ← Q(s, a) + \alpha(R(s, a) + \tau \max_{a'}(Q(s', a') - Q(s, a))$

($\alpha$는 학습률, $R$은 보상 함수, $\tau$는 할인 계수,
$\max_{a'}Q(s, a)$는 다음 상태 $s'$에서 가능한 모든 행동 $a'$에 대한 최대 $Q-value$)

Q-learning의 문제점

• 탐색공간이 이산적 조합으로 구성된 순서쌍으로 제한된다. - 가장 큰 문제
• 특정 상태와 행동에 대해 독립적으로 학습하여, 각 상태가 유사한 경우 일반화가 어려움