추정 - Value Function Approximation

모든 Value function 을 반드시 다 계산 해야 할까? 추정 할 수 있는 방법을 알아보자

---

이전 글 : 모델프리 off-policy Control

[Artificial Intelligence/Reinforcement Learning] - 모델프리 학습 - Model Free Learning - Control technique on Off-Policy

모델프리 학습 - Model Free Learning - Control technique on Off-Policy

 

Value Function Approximation 개요

Value Funtion Appox. 는 가치 함수 추정이라는 용어로 국내학계에서 종종 사용 되기도 하며, 실제로 모든 state 또는 action 에 대한 value function 을 구하는 것이 아니라 어떠한 파라미터를 통해 approximation 즉, 추정 하는 형태로서 value function 을 취하는 기법이다.

지금까지 정리 한 바에 따르면 강화학습을 진행하기 위해 우리는 모든 state 가 정의 된 아래 형태의 lookup table이 필요 했다.

• state value function 을 담는다면?
  • 1차원 형태의 모든 state s 별로 산출되어 기록 할 $V(s)$
• action value function 을 담는다면?
  • 2차원 형태의 모든 state actioin pair $(s,a)$를 colum, row로 가져서 해당하는 pair set 에 대해 산출 되어 기록할 $Q(s,a)$

문제점이 바로 드러나지 않는가?

맞다. 현실 세계에서 실제로 발생할 매우 큰 사이즈의 MDP를 대상으로 하기에 이런 lookup table방식으로 학습을 진행하는 것은 너무나도 비효율 적이며 table 을 구성하는 것 부터가 불가능하다. 또한 lookup table을 만든다고 하더라도 한정된 computation power 로 인한 memory lack 문제와 환경이 실시간으로 변하는 continuous state space 와 같은 문제로는 접근 조차 할 수 없다. (예를 들어 헬리콥터의 이동)

이러한 문제를 해결 하기 위해 적용한 것이 바로 value function 을 측정할때 기존 experience 대신 parameter 를 활용하여 approximation 하는 기법이다.

직관적으로 이해가 되지 않아 아래의 설명을 다른 블로그 search를 통해 참조 하였다. (sumniya.tistory.com/17)

 

우리가 사용할 data가 아래 왼쪽 그림과 같다고 가정해보겠다. 각각을 정확하게 알고 있으면 좋겠지만, 그 양이 무수히 많으면 모두 저장하고 있는 것에 한계가 있다. 그래서, 오른쪽 그림과 같이 이를 대신하여 data들이 일정한 경향성을 가지고 있다면, 그리고 이를 함수화시켜 놓는다면 필요할 때마다 실측값에 근사하여 사용할 수 있고 이렇게 되면 상당한 이점이 있다.

 

1) 실제로 가지고 있지 않은 data도 func.을 통해서 구할 수 있다

2) 실제 data의 noise를 배제하고 training할 수 있다

3) 고차원의 data 도 효율적으로 저장이 가능하다

즉, 이렇게 각각의 data들을 모두 저장하는 것이 아니라 만약 $ax^3+bx^2+cx+d$ 라는 식의 형태로 표현이 가능하다면 방대한 양의 data를 저장하는 것 대신, parameter(a,b,c,d)만 저장하는 방식을 택한다.

이처럼 강화학습에서는 차원이 큰 문제를 다루기 위해 table을 이용하여 값을 저장하는 것이 아닌 새로운 변수 w에 대해 parameterizing한 function을 이용한다.

그리고 이렇게 parameter를 이용하여 실제 값에 approximate하는 함수를 function approximator 라고 한다. 우리는 아래와 같이 value function과 action value function에 w로 parameterization하여 함수화하는 것이다.

여기서 파라미터 $w$ 가 곧 approximator 가 되며 이 $w$를 학습 하여 state value function 을 추정한다.

‘Generalization from seen state to unseen state’ 라는 문구가 이 approximation 을 간랴히 설명 하고 있는데, 일단 몇개의 state에 대한 샘플을 보고 function 을 generalization 한 다음, 이것을 기반으로 새 unseen 값이 들어와도 추정 가능 하다는 아이디어를 담고 있다.

가장 간단한 예시를 들어 보자면, 우리가 정규분포에서 사실 모집단에 대한 모든 속성을 샘플링 하지 않는데 평균과 분산인 $\mu$ 와 $\sigma$ 두개 파라미터만 가지고도 실제 분포를 유사하게 만들어 내는 방식과 유사한 개념이며 본 정규분포 추정 예시 처럼 value function 자체를 approximation 하자는 것이 핵심이다.

 

Types of Value function Approximation

Value function approx. 는 무엇을 추정하느냐에 따라 두가지 타입으로 분류 되는데 우선 아래 그림을 살펴보자.

두 function 에 대해 각각 의미를 해석 해보면,

(세번째 function 은 action value function 을 추정하는 것으로 사실 두번째 function 에서 발전된 개념이다.)

• s를 인풋으로 받아, state value function 을 추정
  • 간단히 state $s$를 입력으로 받아 weight parameter 인 $w$와 함께 function을 태워 state value function을 추정
• s,a 두가지를 인풋으로 받아, action value function 추정
  • state $s$와 action $a$ pair 를 입력 받고 weight parmeter 인 $w$와 함께 function 을 태우는 방식
  • action value function 을 추정하는 제 1목적이 무엇인가? 어떤 action 을 택했을때 Q를 maximize 할 수 있는지를 찾는것이 제 1목적이다.
  • 그렇다면, 모든 $s,a$ pair set을 다 넣어 보기 보다 $s$만 인풋으로 넣고 가능한 각각 action에 대한 value function 을 N개로 뽑는것이 훨씬 연산량도 줄고 간단하지 않을까?
• s를 인풋으로 받아, action value function 추정
  • state $s$를 입력받는 대신 function 을 신경망 (Neural Network)로 구성하여 $w$를 학습하는 방식
  • 즉, $s,w$ 를 trainning data 로 구성하여 머신러닝기법을 적용하여 최종 action value function 을 총 N개 도출 (가능한 action 의 수 : N)
  • 이 function을 학습 하는 행위 자체가 policy 를 구성하는 policy network 를 만들어 주는 과정이 된다.

 

Types of function Approximator

핵심은 $f(s,a;w)$든 $f(s;w)$든 이것을 어떻게 구성 할 까인데 이 실제 값에 approximate 하는 함수는 아래와 같은 여러 function 들이 활용 되고 있다.

• Linear combination of features
• Neural Networks
• Decision trees
• Nearest neighbors
• Fourier / wavelet bases

우리는 실제 값에 approximation 을 해야 하므로 ‘미분’을 통해 loss 의 변화량을 측정하는 전통적인 기계학습을 적용해야 한다. 지금까지는 Linear combination of features 나 Neural Networks 와 같은 미분 가능한 함수들을 활용하여 딥러닝 기법들을 적용하는것이 approximator로서 가장 이상적인 것으로 알려져 있다.

결론은? 결국 Gradient Descent 기법을 써야 하니 approximator는 미분 가능해야 한다.

---

 

Gradient Descent

머신러닝에서 실제 값과 예측값의 차이를 좁혀 나가는데 빠질 수 없는 개념인 Gradient Descent (경사하강법)는 이러한 approximation 에 매우 적절한 방법론이다. 실제값과 예측값의 차이를 loss 라고 정의하고 이러한 loss를 최소화 하는 것이 목적이므로 loss 자체를 Mean squared error (MSE) 로 정의 하고 loss function을 아래와 같이 정의 해보자.

$$ E(w)= \mathbb E[(V_\pi(s) - \widehat{V}(s;w))^2] $$

• $E(w)$ : 우리가 얻고자 하는 것은 parameter $w$를 적용 했을때의 MSE
• $V_\pi(s)$ : 어떤 policy $\pi$를 따랐을 때의 value function (실제 값)
• $\widehat{V}(s;w)$ : approximator 가 estimation 한 value function (추정 값)
• MSE : 샘플들의 실제값-추정값 의 차를 제곱한 값들의 평균

종합하면, 우리는 각 샘플들에서 traning data 를 만들 수 있고,

현재 state 에서의 실제 value function 을 구한 것과, 우리의 approximator 가 $w$를 기반으로 estimation 한 value 값의 차이로 loss function 을 구성 했다고 보면 된다.

우리는 이 MSE를 최소화 하는 것이 목표이므로 이것이 곧 경사하강법이 적용 되는 이유이다.

 

간단한 Gradient Descent 의 소개

weight parameter 가 하나라고 가정 했을때, loss function 의 움직임은 아래와 같은 2차원 그래프로 그려진다.

기본적으로 $w$를 랜덤으로 취하면 $w$위치에서 가장 먼저 $w$를 늘리느냐? 감소시키느냐? 에 대한 방향을 결정 해야한다. 이 기준이 바로 loss function 그래프의 기울기가 되는데, 이 loss 의 변화량을 뜻하는 기울기를 구하기 위해 미분을 하는 것이다.

방향을 결정 한 후에는 좀 더 기울기 loss를 감소시킬 수 있는 $w$’ 로 이동하기 위한 이동 거리를 구해야 하는데 이때 적용할 수 있는 테크닉이 learning rate 다. 이 learning rate $\eta$를 곱해 줌으로서 기울기의 크기를 보고 이동속도 를 조절 할 수 있다.

이런 식으로 loss function의 기울기가 0으로 만드는 지점을 최소 MSE 를 만드는 지점으로 특정하고 $w$을 최적으로 만드는 학습이 완료 된 것으로 간주한다.

수식을 해석해보자.

• $w_1(j+1)$ : 다음 번째 업데이트 될 weight 를 표현
• $w_1(j)$ : 현재 step 에서의 weight
• $-\nabla E(w_1(j))$ : 기울기와 반대 방향으로 $w$를 이동 시킨다는 의미
• $\eta$ : learning rate

weight 파라미터가 하나씩 증가 할때 마다 loss function 의 dimenstion 역시 증가 하게 된다.

아래는 weight parameter 가 두개인 경우의 loss function 을 시각적으로 표시한 예시이다.

뭔가 수식이 좀더 복잡 해진 것 같지만 기본적인 아이디어는 동일하다.

다만 $w$가 복수이므로 $w(i)$ 에 해당하는 값은 $w_1$과 $w_2$의 조합으로 이루어진 vector 형태가 될 것이므로 변화량을 뽑기위해서는 vector의 element 마다 편미분을 통해 전체적인 기울기를 구하는 점이 다르다고 볼 수 있다.

 

Value Function Approx. 에서의 Gradient Descent

다시 본 주제인 Value function approximation으로 돌아와 보자. 앞서 우리는 loss 를 MSE로 정의 하였고 이를 state value function 에 적용 시켜서 아래와 같은 loss function 을 도출 한 바 있다.

$$ E(w)= \mathbb E[(V_\pi(s) - \widehat{V}(s;w))^2] $$

그리고, Gradient Descent 에 대한 일반화 된 아래 수식을 하나씩 뜯어서 분석 해보았다.

$$ w(i+1) = w(i) - \eta \nabla_wE(w(i)) $$

이 수식에서 우변의 $w(i)$를 좌변으로 넘겨주고, MSE를 미분 할때 좀 더 쉽게 미분 할 수 있게 1/2 를 보정치로 곱해주면 아래와 같은 식이 되며,

$$ \nabla w = -\frac 12 \eta \nabla_wE(w) $$

이를 weight 와 관련된 term 만 미분 해버리면 아래와 같이 미분 된다.

$$ \nabla w = \eta \mathbb E[(V_\pi(s) - \widehat{V}(s;w)) \nabla_w \widehat{V}(s;w)] $$

앞에 expectation 인 $\mathbb E$가 붙은 이유는 Gradient Descent 기법 자체가 tranning data 의 모든 샘플에 대한 expectation 을 가지고 update 하기 때문이다.

---

 

SGD를 활용한 Incremental Prediction / Control

앞서 살펴본 수식은 tranning data 샘플 전체 train set에 대한 expectation 을 고려 했기 때문에 Batch Gradient Descent 기법이었다고 할 수 있다. Stochastic gradient descent 는 BGD를 기반으로 하여 train 하는 방식을 더 효율적으로 만들어 주는 테크닉이다.

BGD는 loss function 계산 시 전체 train set 을 사용하므로 한번 step을 내딛을 때, 전체 데이터에 대한 loss function 연산이 발생 하므로 비효율적인 학습이 진행 된다. 이를 방지 하기 위해 보통 SGD를 활용 하는데, SGD는 loss function 계산할 때, 전체 train set 대신 일부 데이터의 모음인 Mini-batch 를 사용하여 loss functio n을 계산한다. Stochastic 이라는 용어가 붙는 이유는 각 batch 를 포함하는 하나의 예가 확률적으로 무작위 선택 된다는 것을 의미한다.

BGD에 비해 다소 부정확 할 수 있지만, 계산속도가 훨씬 빠르기 때문에 같은 시간에 더 많은 step 을 시도 할 수 있으며 이러한 계산 시간의 merit 를 더 많은 train 으로 분배 해준다면 결국 BGD의 결과로 수렴 할 수도 있다.

또한 Local minima 에 빠지지 않고 Global minima 에 수렴할 가능성도 커지며, Momentum, Adagrid, AdaDelta, RMSprop 등의 native SGD에서 파생된 여러 알고리즘들을 고려하면 범용성 역시 뛰어 나다고 할 수 있다.

본 주제에서의 핵심은, BGD 대신 mini batch size를 1로 한 SGD형태로 loss function 을 계산하여 train set 샘플이 하나씩 들어올때마다, 미분한 값을 가지고 loss function 을 계산 한다는데 있다.

Expectation이 고려된 BGD 수식을 매번 loss function 의 loss를 최소화 하는 방향으로 weight 를 업데이트 하는 SGD수식으로 일반화 하면 아래와 같은 수식이 최종적으로 만들어 진다.

$$ \nabla w = \eta (V_\pi(s) - \widehat{V}(s;w)) \nabla_w \widehat{V}(s;w) $$

여기서 현재의 state value function 을 의미하는 $V_\pi(s)$를 MC나 TD등 어떤 방식을 쓰냐에 따라 state value function 이 의미하는 return은 달라 질 수 있다.

 

Incremental Prediction with SGD

SGD가 진행되는 과정에서 value function evaluation에 MC와 TD 방식이 각각 적용 된다고 생각해보자. SGD 수식에서 state value function 즉, return에 해당하는 $V_\pi(s)$ 이 치환되어야 할 것이다.

• MC 기법을 쓴다면 target 은 return $G_t$ 로 치환 될 것이다.
  • $\nabla w = \eta (G_t - \widehat{V}(s;w)) \nabla_w \widehat{V}(s;w)$
• TD 기법을 쓴다면 target 은 TD target 인 $R_{t+1} + \gamma \widehat{V}(S_{t+1};w)$ 으로 치환 될 것이다.
  • $\nabla w = \eta (R_{t+1} + \gamma \widehat{V}(S_{t+1};w) - \widehat{V}(s;w)) \nabla_w \widehat{V}(s;w)$

일단 prediction 된 value function을 가지고 value iteration, policy iteration 을 통해 역시 control 까지 할 수 있다.

하지만 아래 그림을 보면, 인풋 state s 라는 것은 추상적인 개념이며 함수에 넣으려면 일단 수치화 하여야 한다. 따라서 state s 는 보통 feature vector 형태로 뽑아내어 함수로 넣는다.

얼핏 보면 비슷한 그림이지만 인풋이 s에서 실제 feature vector인 $x(s)$ 로 달라 졌고 계산 되는 value functio n은 지금까지 살펴 본 바와 같이 approximated 된 value function이다.

Prediction 을 했으니 이제 Control을 할 차례인데, Control 도 approximated 된 value function을 대상으로 이루어 진다.

 

Incremental Control with SGD

앞서 model free 상황에서의 control 개념에서 아래와 비슷한 형태의 그림을 본적 있을 것이다.

여기서도 동일하게 policy $\pi$를 $\epsilon$-Greedy 형태로 수렴 시켜 나가는데, 얻고자 하는 값은 결국 q* 이며 이 q*는 파라미터 $w$가 학습 된 $q_w$로 부터 근사 추정 된다.

지금까지의 방법은 value function 을 가지고 policy를 먼저 evaluation 한 후, 그 중에서 gradient 하게 policy를 improve하는 것이었다.

여기서는 실제로 policy evaluation 을 할때 value function 이 approximation 되어있다면 policy 는 자동적으로 greedy 하게 behavior를 선택해서 진행 한다.

역시 policy iteration 에 MC와 TD가 쓰인다고 가정 해보자. 여기서도 얻고자하는 $Q_\pi(s)$에 대한 target은 MC와 TD냐에 따라 각각의 방식에서의 주요 관심사인 return 과 TD target 으로 치환 된다.

prediction 에서 value funtion 을 썼다면 역시 control 에서는 action value function 을 쓴다.

• MC 기법을 쓴다면 target 은 return $G_t$ 로 치환 될 것이다.
  • $\nabla w = \eta (G_t - \widehat{Q}(S_t;A_t;w)) \nabla_w \widehat{Q}(S_t;A_t;w)$
• TD 기법을 쓴다면 target 은 TD target 인 $R_{t+1} + \gamma \widehat{Q}(S_{t+1},A_{t+1};w)$ 으로 치환 될 것이다.
  • $\nabla w = \eta (R_{t+1} + \gamma \widehat{Q}(S_{t+1},A_{t+1};w) - \widehat{Q}(S_t,A_t;w)) \nabla_w \widehat{Q}(S_t, A_t;w)$
  • 기존에 답습 해왔던 방식 대로 이 TD target 은 다음 state 에서의 Q값을 기반으로 업데이트 한다는 의미를 담고 있다.

---

 

Deep Q-Networks (DQN)

DQN은 approximator 를 Q러닝에 적용한 것으로 off policy learning 기법 중 하나이다.

Deep Q-Network (DQN)은 이름에서 알 수 있듯이, state-action value Q값을 Deep Learning을 통해서 Approximate하는 방식이다. DQN이 나오기 전에는, state-action에 따른 값들을 모두 Table 형태 (Q-Table)로 Update하면서 갖고 있다가, 이를 참고하여 Action을 선택하는 방식으로 Policy가 구성되어 있었다. 이렇게 Episode를 진행하면서, 최종적인 Cumulative Reward를 최대화하도록 Q-Table을 Update해나가는 방식이었다.

지금까지의 정리 과정에서 확인 했듯이, 현재 갖고있는 Q-Table을 기반으로 Policy를 정하되, Updating Policy와 Target Policy가 같으면 On-policy인 SARSA, 두 Policy가 다르면 Off-Policy인 Q-Learning이 된다. 어떤 방식이던, Table을 기반으로 하고, State-Action에 대한 모든 값을 갖고 있어야하기 때문에, State가 많아지면, 엄청나게 큰 Table을 가져야 한다. 가장 예로 많이 드는 Atari Game의 경우, State가 Color Image이기 때문에, State가 엄청 커지고, Memory 소모도 커지고, Training에도 문제가 생긴다. DQN은 이를 보완하기 위해, Table 형태가 아니라, w라는 가중치를 갖고 있는 Deep Learning 모델로 Approximate한다.

현실에 있는 대부분의 Case는 High Dimension Data (e.g., Vision)을 대상으로 하고 있기 때문에, DQN은 강화학습 알고리즘을 발전시키는 큰 축 중에 하나로 꼽힌다

Q러닝의 장점 중 하나는 이전에 활용한 old policy 에서 얻은 결과를 활용 가능한 off policy learning 이라는데에 있는데 이를 위해 DQN은 episode 를 매번 진행 할때 마다 나온 결과 값을 매 state 마다 저장하여 experience replay 할 수 있게 해준다.

또한 action $a_t$를 선택 시 $\epsilon$-Greedy 방식을 취하며, replay memory D에 transition 에 대한 값 $(s_t , a_t, r_{t+1}, s_{t+1})$을 저장한다.

Q learning targ 을 연산 함에 있어 fixed parameter 인 $w^-$ 값을 활용 하며, Q-network 와 Q- learning target 사이의 MSE를 최소화 하는 방향으로 optimize 한다.

fixed parameter 인 $w^-$ 를 주는 이유는 아래 식을 통해 설명 될 수 있다.

$Q(s',a';w^-)$ 를 target 으로 잡는데, $w$가 변한다면 target 도 변하니 학습이 어려워 진다. 그래서 weight 을 fix 하고 고정 학습을 진행한다는 의미 이다.

DQN은 굉장히 유명한 구글 딥 마인드 논문인 “Playing Atari with Deep Reinforcement Learning (2013)” 에 상세히 소개 되어 있고, 아래 블로그에 잘 정리 되어 있으니 DQN의 feature 들에 대해 차근차근 짚어 보자.

https://velog.io/@sjinu/개념정리-7.-DQNDeep-Q-NEtwork

[개념정리] 7. DQN(Deep Q NEtwork)

 

 

---

Value function 을 일일이 계산 하지 않고 파라미터 w를 학습하여 approximation 하는 과정을 알아 보았다. 학습 과정에서 머신러닝 기법으로 optimize 하기위해 Gradient Descent 가 접목 되는 과정도 살펴 보았고, off policy 의 대표적인 테크닉인 DQN에 대해 알아보았다.

다음 정리는 value function 조차 고려 하지 않고 policy 자체를 approximation 하여 policy 를 구하는 Policy Gradient 기법에 대해 정리 하고자 한다.