본 노트는 교재 "파이썬과 케라스로 배우는 강화학습"을 공부하며 만든 필기입니다.

강화학습 개요

강화학습의 개념

"강화" = "시행착오"

머신러닝Machine Learning
= 지도학습Supervised + 비지도학습Unsupervised + 강화학습Reinforcement

1. 지도학습
   → 정답이 있는 데이터 (label이 있는 데이터) 를 이용해서 자신이 낸 답과의 차이를 좁혀감.
   → 회귀분석Regression, 분류Classification
2. 비지도학습
   → 정답이 주어지지 않고 비슷한 것들끼리 묶어줌.
   → 군집화Clustering
3. 강화학습
   → 보상Reward 을 통해 학습함.
   → 보상은 컴퓨터Agent 가 선택한 행동Action 에 대한 환경의 반응

순차적 행동 결정 문제

강화학습 → 결정을 순차적으로 내려야 하는 문제에 적용
다이나믹 프로그래밍Dynamic Programming, 진화 알고리즘Evolutionary Algorithm으로도 순차적 행동 결정 문제를 해결할 수 있음.
→ 각각 한계를 가지고 있으며, 강화학습이 그 한계를 극복할 수 있음.

순차적 행동 결정 문제를 수학적으로 정의해서 Agent가 이를 해결할 수 있도록 함.
→ 순차적 행동 결정 문제를 정의하는 방법 MDPMarcov Decision Process

순차적 행동 결정 문제의 구성 요소

1. 상태 State
   에이전트의 상태. 즉 관찰에 대한 정보를 나타냄.
2. 행동 Action
   에이전트가 어떠한 상태에서 취할 수 있는 행동
   에이전트가 행동을 취하면 환경은 에이전트에게 보상을 주고 다음 상태를 알려줌.
3. 보상 Reward
   에이전트가 학습할 수 있는 유일한 정보
   강화학습의 목표 = 시간에 따라 얻는 보상들의 합을 최대로 하는 것
   에이전트는 어떤 상황에서 얼마의 보상이 나오는지 미리 알지 못한다.

4. 정책 Policy
   에이전트가 모든 상태에 대해 어떤 행동을 해야 하는지 정해 놓은 것
   순차적 행동 결정 문제에서 구해야 할 답

   최적 정책Optimal Policy → 가장 좋은 정책
   최적 정책에 따라 행동했을 때 에이전트는 보상의 합을 최대로 받을 수 있다.

한계점

체스같이 비교적 방대하지 않은 상태를 가진 문제에서는 한계점이 드러나지 않음.

로봇의 학습 문제 → 로봇이 관찰하는 정보, 행동, 보상이 모두 연속적이므로 계산으로 해결 불가능.
→ 로봇에 강화학습을 적용하기 위해서는 인공신경망Artificial Neural Network를 이용해 정보를 함수와 같은 형태로 근사해야한다.
→ 행동이 얼마나 좋은지 알려주는 큐함수Q Function에 인공신경망을 적용한 DQNDeep Q-Network를 사용함.

강화학습 기초

MDPMarkov Decision Process

MDP의 구성 요소 = 상태 + 행동 + 보상함수 + 상태 변환 확률

1. 상태 (자신의 상황에 대한 관찰)

$S$ = 에이전트가 관찰 가능한 상태의 집합
$S = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5)\}$

시간 $t$에서의 상태 $S_t = \text{s}$
어떤 시간에서의 상태는 정해져있지 않음.

2. 행동

에이전트가 상태 $S_t$에서 할 수 있는 가능한 행동의 집합 $A$
보통 에이전트가 할 수 있는 행동은 모든 상태에서 같기 때문에 하나의 집합으로도 표현 가능.

시간 $t$에서 에이전트가 특정한 행동 $a$를 했다 → $A_t = a$

3. 보상함수 Reward Function

시간 $t$일 때 상태가 $s$이고 그 상태에서 행동 $a$를 했을 경우에 받을 보상에 대한 기댓값 $E$
$r(s, a) = E[R_{t+1} | S_t = s, A_t = a]$ = $R_a(s, s')$로 표기하기도 함.

에이전트가 어떤 상태에서 행동한 것은 시간 $t$에서지만 보상을 받는 것은 $t+1$이다.
→ 보상을 에이전트가 알고 있는 것이 아니고 환경이 알려주는 것이기 때문.
→ 환경이 에이전트에게 알려주는 시점이 $t+1$인 시점 → 에이전트가 받는 보상을 $R_{t+1}$이라고 표현함.

에이전트는 환경으로부터 하나의 시간 단위가 지난 다음에 보상을 받음
→ 이 시간 단위를 타임 스텝으로 한다.

4. 상태 변환 확률

에이전트가 상태 $s$에서 행동 $a$를 해서 $s'$으로 가게 되는 확률
$P_{ss'}^{a} = P[S_{t+1} = s' | S_t = s, A_t = a]$

$P_a(s, s')$로 표기하기도 함.

• 할인율 Discount Factor
  $\gamma \in [0, 1]$

할인율을 고려한 미래 보상의 현재 가치
$\gamma^{k-1}R_{t+k}$ → 현재로부터 $k$만큼 지났기 때문에 보상이 $\gamma^{k-1}$만큼 할인됨.

• 정책

모든 상태에서 에이전트가 할 행동
상태가 입력으로 들어오면 행동을 출력으로 내보내는 일종의 함수로 보아도 된다.

시간 $t$에 상태 $s$인 에이전트가 있을 때 가능한 행동 중 $a$를 할 확률
$\pi(a|s) = P[A_t = a | S_t = s]$

• 가치함수

에이전트는 최적 정책을 찾아야 한다.
→ 현재 상태에서 앞으로 받을 보상들을 고려하면 된다.

MDP → 가치함수 → 행동 선택
에이전트는 가치함수를 통해 행동을 선택할 수 있다.
가치함수 = 앞으로 받을 보상에 대한 개념.

할인율을 적용한 반환값
$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...$

특정 상태에 대한 반환값은 에피소드마다 다를 수 있다.
→ 반환값에 대한 기대값으로 특정 상태의 가치를 판단할 수 있다.

따라서, 가치함수를 수식화하면 다음과 같다.

$v(s) = E[G_t | S_t = s]$
$v(s) = E[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} ... | S_t = s]$
$v(s) = E[R_{t+1} + \gamma G_{t+1} | S_t = s]$
$= E[R_{t+1} + \gamma v(S_{t+1}) | S_t = s]$ → 가치함수로 표현하는 가치함수

→ 여기까지는 가치함수를 정의할 때 정책을 고려하지 않음.

정책을 고려한 가치함수의 표현 : 벨만 기대 방정식 Bellman Expectation Equation
$v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi (S_{t+1}) | S_t = s]$
아래 첨자로 정책을 써서 가치함수가 정책 $\pi$에 의존한다는 것을 알려줌. (기댓값도 정책에 따라 계산해야 함)

• 큐함수

지금까지의 가치함수
상태 가치함수 state value-function
상태가 입력으로 들어오면 그 상태에서 앞으로 받을 보상의 합을 출력하는 함수

행동 가치함수 action value-function (Q Function) or state-action value-function
어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수 $q_\pi(s, a)$

가치함수와 큐함수 사이의 관계식
$v_\pi(s) = \sum_{a \in A} \pi(a|s) q_\pi (s,a)$

벨만 기대 방정식으로 나타낸 큐함수 - 큐함수의 벨만 기대 방정식
$q_\pi(s,a) = E_\pi [R_{t+1}+ \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$

벨만 방정식

• 벨만 기대 방정식
  반환값으로 가치함수를 나타낼 경우, 앞으로 받을 모든 보상에 대해 고려해야함.
  → 정의상 가능하지만 상태가 많아질수록 상당히 비효율적인 방법임.
• 계산 가능한 벨만 방정식
  → 기댓값에는 행동을 할 확률 (정책) 과 상태로 가게 되는 확률 (상태 변환 확률 $P_{ss'}^a$) 이 포함되어 있음.
  → 정책과 상태 변환 확률을 포함해서 수식을 작성해주면 됨.
  $v_\pi(s) = \sum_{a \in A}\pi(a | s)(r(s, a) + \gamma\sum_{s'\in S}P_{ss'}^av_\pi(s'))$

→ 상태 변환 확률이 1인 경우의 벨만 기대 방정식
$v_\pi(s) = \sum_{a \in A}\pi(a | s)(r(s, a) + \gamma v_\pi(s'))$

• 벨만 최적 방정식
  벨만 기대 방정식을 통해 계속 계산을 진행하면 왼쪽 항과 오른쪽 항이 동일해짐.
  $v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s]$
• 기댓값이 계산 가능한 형태의 벨만 기대 방정식
  $v_{k+1}(s) \leftarrow \sum_{a \in A}\pi(a | s)(r(s, a) + \gamma v_k(s'))$

계산을 반복하다보면 방정식의 왼쪽 식과 오른쪽 식이 같아짐 → 참 가치함수를 찾은 것임.

• 참 가치함수 : 어떤 정책을 따라서 움직였을 경우 받게 되는 보상에 대한 참값($\Leftrightarrow$ 기댓값)

참 가치함수 $\neq$ 최적 가치함수Optimul Value Function

• 최적 가치함수 : 수많은 정책 중에서 가장 높은 보상을 얻게 되는 정책을 따랐을 때의 가치함수

정책이 좋은 것? 이란 무슨 의미를 내포하고 있을까. 어떤 정책이 더 좋은 정책일까?
→ 정책을 따라갔을 때 받을 보상들의 합인 가치함수를 통해 판단할 수 있다.

모든 정책 중 가장 큰 가치함수를 주는 정책 = 최적 정책
최적 정책을 따라갔을 때 받을 보상의 합 = 최적 가치함수 (큐함수도 마찬가지)

• 최적의 가치함수
  $v_*(s) = \max_\pi [v_\pi(s)]$
• 최적의 큐함수
  $q_*(s) = \max_\pi[q_\pi(s, a)]$
• 최적 정책은 최적의 큐함수가 정해졌을 때, 가장 큰 큐함수를 가진 행동을 하면 구할 수 있다.
  $\pi_*(s, a) = \begin{cases}1&\text{if }a \text{ = argmax}_{a \in A}q_*(s, a) \\ 0 & \text{otherwise}\end{cases}$

최적 가치함수끼리의 관계

벨만 방정식 = 현재 상태의 가치함수와 다음 타임스텝 상태의 가치함수 사이의 관계

현재 상태의 가치함수가 최적이라 가정
→ 에이전트가 가장 좋은 행동을 선택함.
→ 무엇을 기준으로 가장 좋은 행동인지 알까 ? = 큐함수!

• 큐함수가 최적의 큐함수가 아니라면 아무리 큐함수에서 최대인 행동을 하더라도 가치함수는 최적의 가치함수가 될 수 없다.

큐함수 중 최대를 선택하는 최적 가치함수
$v_*(s) = \max_a[q_*(s, a) |S_t = s, A_t = a]$

벨만 최적 방정식Bellman Optimality Equation - 큐함수를 가치함수로 변화
$v_*(s) =\max_aE[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a]$

큐함수에 대한 벨만 최적 방정식 $q_*(s, a) = E[R_{t+1} + \gamma \max_{a'}q_*(S_{t+1}, a') | S_t = s, A_t = a]$
다음 상태에 선택 가능한 행동 중 가장 높은 값을 가진 행동의 큐함수를 1번 할인하고 보상 받는 것과 같다.