[RL] Lecture 6. Value Function Approximation

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

6. Value Function Approximation

지금까지는 Grid World를 통해서 작은 상황을 설정했고 table로 저장하는 것이 가능했다. 그리고 value function과 policy를 구하는 과정을 살펴보았다. 이러한 문제들을 Tabular Method라고 부른다. 하지만 실제 문제에 대해서 강화학습을 적용하기에는 너무 크다.

지금 강화학습으로 해결할 수 있거나 해결하려고 하는 문제에 대해서 state의 갯수를 알아보면 다음과 같다. Backgammon은 10²⁰, 알파고는 10¹⁷⁰, 헬리콥터(자율주행)은 사실상 무한대의 상태들을 가지고 있다. 따라서 이러한 문제에 대해서 value function과 policy를 구하고자 하는 것은 어렵다. 따라서 이 값들을 추정하는 방법들에서 배우도록 한다.

function approximation을 하는 방법은 어렵지 않다. 새로운 변수 w를 대입해서 이 변수가 table의 정보를 대변하도록 만들면 된다. 즉 다음과 같이 함수화 할 수 있다.

w는 학습을 통해서 update하며, true value와 근사하도록 맞춰나간다. 최근에는 이 학습을 하는 과정에 deep learning을 사용하기도 한다.

Value Function Approximation에는 다음과 같은 종류들이 있다고 한다.

function approximator에는 여러 개가 있지만 그 중 미분가능한 Linear combinations of features, Neural network를 이번 장에서 소개하도록 한다. 그리고 이들은 non-stationary, non-iid한 data라고 하는데, 분포가 계속해서 바뀌며 독립적이지 않다.

Incremental Methods

w를 업데이트를 하는 방법중 가장 좋은 것은 Gradient Descent이다. 이 방법은 간단하고 프로그램 상으로도 강력하다. 하지만 시작점에서 조금만 달라져도 다른 점에 도착할 수 있고, 이 점이 local optima일 수도 있다.

w로 표현되는 loss function인 J(w)는 true value와의 error로써 이를 최소화하는 것이 목적이다.

이를 미분해서 값을 update 할 수 있는데 expectation을 쓰는 방법과 sampling을 하는 방법이 있고 다음과 같다.

MC와 TD에서 했던 것처럼 v_π(S)를 대체해서 사용할 수 있다.

MC with Value Function Approximation

MC의 G_t는 unbiased 하고, true value의 noisy sample이다. 그러므로 training data를 지도학습으로 적용할 수 있다. 그래서 위와 같이 사용가능하며, local optimum으로 수렴하게 된다. 그리고 non-linear한 경우에도 적용할 수 있다고 한다.

TD Learning with Value Function Approximation

TD-target은 guess를 사용하는 것이기 때문에 true value의 biased sample이다. 하지만 여전히 training data를 지도학습으로 적용이 가능하고 위에서 소개한 것처럼 TD(0)를 적용할 수 있다.

Linear TD(0)는 (거의) global optimum에 수렴한다.

TD(λ) with Value Function Approximation

G_t^λ도 true value의 biased sample이다. 그러므로 역시 training data를 지도학습으로 적용할 수 있으며 Forward view linear TD(λ), Backward view linear TD(λ)로 각각 적용할 수 있고, 서로 equivalent하다.

Control with Value Function Approximation

하지만 value function을 사용하면 control 문제를 다룰 때 발생했던 model-free가 발생한다. 따라서 이번에도 value function을 q-function으로 바꾸도록 한다.

그리고 그 뒤로는 value function을 했던 내용과 동일합니다.

Batch Methods

Gradient descent는 간단하고 매력적이지만 한번 쓰고 버린다. 따라서 sample efficient하지 않다고 한다. 따라서 Batch method는 1000개의 데이터가 있으면 그 중 10개를 sample로 해서 사용하는 방식이다. 이를 통해 value function의 best fitting을 찾을 수 있다고 한다.

value function approximation을 사용하고, experience D는 <state, value>의 쌍으로 구성된다. 이 때 best fitting value인 파라미터 w를 찾기 위해서 Least squares 알고리즘을 사용한다.

Least squares 알고리즘은 추측값과 참값 사이의 sum-squared error를 최소화하는 w를 찾는 알고리즘이다.

Stochastic Gradient Descent with Experience Replay

<state, value>로 쌍이 묶어진 experience D가 있을 때, 다음을 반복한다.

그러면 이는 다음과 같이 수렴한다.

이러한 방법을 Experience replay라고 하며 강화학습에서 자주 사용하는 방법이다.

Experience replay in Deep Q Networks

Non-linear랑 off-policy일 때 학습을 진행하면 수렴을 하지 않고 발산한다는 문제점이 발생한다. 따라서 이러한 문제를 해결하기 위해 DQN은 experience replay와 fixed Q-target을 사용한다고 한다.

• Experience reaply: 어떤 action에 어떤 reward와 그 state등 정보들이 있는 transition을 replay memory에 저장하고, random하게 mini batch를 뽑는다. 그리고 MSE를 통해 학습한다.
• Fixed Q-target: target을 계산할 때에 예전 parameter를 쓰는 것, 두 개의 파라미터 set이 있다. 하나는 고정시키고 다른 하나는 업데이트 중인 파라미터 set을 가진다. non-linear 함수일 때에 업데이트 방향이 계속 바뀌기 때문에 수렴되기 어렵다. 따라서 1000번 정도는 고정된 parameter set을 사용하며 진행하다가 그 이후에 고정된 parameter set을 업데이트 하던 parameter set으로 바꾼다. 예전 버전을 w^-, 현재 버전을 w라 했을 때, target에서는 고정된 것을 사용하기 때문에 fixed Q-target이라 한다.