[RL] David Silver RL Lecture 6: Value Function Approximation

1. Introduction

RL은 커다란 문제를 해결하기 위해 사용될 수 있다.

• Backgammon : \(10^{20}\) States
• Computer Go : \(10^{170}\) States
• Helicopter : continuous state space

Model free에서의 prediction과 control하는 방법을 앞선 4,5강에서 배웠는데 이것을 어떻게 Scale-up 할 수 있을까?

1.1 Value Function Approximation

• 지금까지는 lookup table을 통해 value function을 구했다.
  • 모든 state s 개수 만큼 빈칸이 있었다.
  • 모든 state-action pair 개수 만큼 빈칸이 있었다.
• large MDPs의 문제점
  • 메모리에 저장할 state와 action이 너무 많다.
  • 각 state를 개별적으로 연산하기엔 너무 오래걸린다.
• 문제에 대한 해결책

  • function approximation으로 가치 함수 평가

    

  • 가본 State부터 안가본 State까지 일반화를 한다.
  • MC, TD learning를 통해 parameter인 w를 update한다.

가운데는 blackbox라고 생각을 하고 input을 넣으면 output을 내보내준다.

q function의 경우 2가지 형태가 있다.

• s,a를 넣는 경우 (action in)
  • s,a를 input으로 q함수를 구한다.
• s를 넣는 경우 (action out)
  • state s에서 가능한 모든 action a에 대한 q함수를 구한다.

1.2 Function Approximator

많은 Function Approximator가 있다.

이 중에서 differentiable(미분가능한) function approximators를 사용한다. 꼭 미분 가능해야 하는 건 아니지만, 그래야 gradient를 구해 w를 업데이트 할 수 있다.

학습 방법은 non-stationary, non-iid 데이터에 적합하다.

large MDPs를 풀기에는 모든 state, action을 저장하는 table lookup 방식은 비효율적이다. 그래서 value function approximation을 통해 일반화를 하는 방식을 택한다. function approximator로는 differentiable 즉 미분 가능한 것을 사용한다. 꼭 그래야 하는 것은 아니지만 그래야 gradient를 구해 w를 업데이트 할 수 있다.

---

2. Incremental Methods

2.1 Gradient Descent

J(w) : vector w를 파라미터로 하는 미분가능한 함수

이 함수는 아래와 같이 정의 할 수있다.

J(w)의 local minimum을 찾기위한 식은

• \(α\) : step size parameter
• ”-“는 방향을 나타내고, 1/2는 수학적 편의를 위해 들어감

쉽게 요약하면 산정상에서 길을 모르는 상태에서 마을로 내려가기위해 현재 위치에서 조금씩 (step size 만큼)가장 기울기가 큰곳으로 걸어간다. 운이 좋다면 내려가는 거고, 운이 나쁘게 기울기가 가장큰 방향으로 갔더니 봉우리(local minimum)를 만나 갇히게 될 수도 있다.

Value Function Approx. By Stochastic Gradient Descent

목표 : 근사한 가치 함수와 실제 가치 함수의 MSE를 최소화 하는 vector w를 찾는 것

• Mean Square Error : 그 차이가 양이든 음이든 절대값을 최소화

w를 구하기 위한 식은

Δw : w의 변화량

J(w)를 w에 대해서 미분을 한다. \(v_π(S)\) : 상수

Stochastic Gradient Descent은 sample을 하나 뽑아서 그것을 전체에 적용

SGD의 update는 full gradient update랑 똑같다.

• 계산속도가 빠르다.

2.2 Linear Function Approximation

• feature vector로 state S를 표현하면 다음과 같이 표현할 수 있다.

• value function을 feature를 linear combination로 표현하면 아래와 같다.

  

  • value function의 근사값 = \(x_1(S)_{w_1}\) + \(x_2(S)_{w_2}\) + …

  

  • 이를 이용해 목적 함수인 J(w)를 표현할 수 있다.
• SGD는 global optimum에 수렴한다

• update rule은 매우 간단하다.

  

  앞서 구한 Δw를 구하는 식을 아래와 같이 변형할 수 있다.

  

선형 합으로 모방함수(근사값)를 구해서 처음 것보다 나은 w를 찾는다. 더 나은 w : 실제 value function과 근사 함수의 MSE를 최소화 하는 w 더 나은 w가 있어야 실제 value function과 유사한 근사 함수를 찾을 수 있다.

Table lookup Features

지금까지 Table lookup방법을 사용했었는데, table lookup과 linear value fuction이 전혀 다른 방식이라고 생각안했으면 좋겠다.
Table lookup은 linear value function approximation의 특별한 경우이다.

w가 table에 있었던 값 이라고 생각하면 됨

2.3 Incremental Prediction Algorithms

지금까지는 true value function $v_π(s)$를 supervisor가 알려줬다고 가정하고 했었다.

하지만 RL에는 supervisor는 없고 reward만 있다.

그래서 true value function을 지금까지 배웠던 method로 대체한다.

Monte-Carlo with Value Function Approximation

Return \(G_t\)는 true value function의 unbiased, nosiy 한 sample이다.

• unbiased : 같은 state에서 출발하더라도 모든 것이 stocastic하기 때문에 다른 return이 나올수있다.

  그러므로 정말 많은 수를 sampling해서 <\(S_1, G_1\)> , <\(S_2,G_2\)>, … <\(S_T, G_T\)>을 training data로 만들어 supervised learning을 해도 value function을 구할 수 있다.

• 예를 들어 linear Monte-Carlo policy evaluation을 사용하면 다음과 같이 나타낼 수 있다.

  

• MC evaluation은 local optimum에 수렴한다.
• 심지어 non-linear value function approximation에서도 적용이 가능하다.

TD Learning with Value Function Approximation

TD target은 true value function의 biased한 sample이다.

하지만 그래도 training data로 supervised learning이 가능하다.

• 예를 들어 Linear TD(0)을 사용하면 다음과 같이 나타낼 수 있다.

  

• Linear TD(0)은 global optimum에 가깝게 수렴한다.

TD(λ) with Value Function Approximation

λ-return도 true value function의 biased한 sample이다.

마찬가지로 training data를 만들어 supervised learning이 가능하다.

linear TD(λ)의 forward view & backward

• Forward view and backward view linear TD(λ)는 같다.

2.4 Incremental Control Algorithms

• policy evaluation : Approximate policy evaluation
• policy improvement : ε-greedy policy improvment

지금까지 value function에 대해서 했는데 Q function으로 해도 똑같다.

• action value function을 근사하면 다음과 같이 나타낼 수 있다.

  

• action-value 근사함수와 true action-value 함수의 MSE를 최소화한다.

  

• local minimum을 찾기위해 SGD를 사용한다.

  

• action, state를 feature vector로 나타낼 수 있다.

  

• action-value 함수를 features의 linear combination로 나타낼 수 있다.

• SGD Update

• 마찬가지로 true action-value function을 지금까지 배웠던 method로 대체한다.

2.5 Convergence

• Non-linear일수록 수렴성이 안좋다
• off-policy일수록 수렴성이 안좋다

Prediction

Gradient TD는 모든 상황에서 수렴성을 보장한다.

Control

---

3. Batch Methods

Batch RL : agent의 경험(training data)을 반복적으로 사용해 학습함.

• incremental method는 sample 하나를 보고 update하고 그 sample은 버려져 비효율적으로 sample을 사용한다.

3.1 Least Squares prediction

마찬가지로 value function을 근사할 수있는 함수가 있다.

어떤 파라미터 w가 모방함수에 가장 적합할까?

Least square algorithms은 모방함수와 true value function의 MSE를 최소화하는 파라미터 w를 찾기위한 알고리즘이다.

Stochastic Gradient Descent with Experience Replay

experience D는 <State, Value> pair 들로 이루어져있다.

이것을 계속 반복하는 것을 Experience replay라고 한다. 예를들어

1. D에 있는 sample 10개를 뽑는다.
2. 그 sample 10개만 가지고 w를 Update

⇒ 이것을 반복하면 같은 sample을 여러번 사용할 수 있다.

3.2 Experience Replay in Deep Q-Networks (DQN)

DQN은 experience replay와 fixed Q-targets을 사용한다.

• experience replay
  • action \(a_t\)는 ε-greedy에 의해 선택된다.
  • replay memory \(D\)에 transition (\(s_t, a_t, r_{t+1}, s_{t+1}\))을 저장한다.
  • \(D\)에서 transition 몇개를 random sampling한다.
• Fixed Q-targets w가 계속 업데이트되면 방향이 계속 바뀌면서 발산할 수 있음 그래서 발산하지 않게 일정 기간 w를 고정해두고 update
  • 파라미터 w를 저장하는 곳을 2개 만든다. (w , old w)
  • Q-learning target을 계산할 때 old w를 사용한다.
• Q-network와 Q-learning targets의 MSE를 최적화한다.

• 변형 SGD를 사용한다.

3.3 DQN in Atari

• pixel s로부터 Q(s,a)를 얻는다.
• input state s 는 마지막 4 frame의 raw pixels이다.
• output은 18개의 조이스틱, 버튼 position의 Q(s,a)
• reward는 그 step에서의 score의 변화

• 굉장히 좋은 결과를 얻었고, 사람보다 좋은 성능을 낸다.

• Replay experience와 Fixed-Q를 함께 사용하는 것이 가장 좋은 결과를 낸다.

맨 위로 이동하기

RL Lecture 카테고리 내 다른 글 보러가기