기록: UCL Course on RL 요약 및 정리 (Lecture 6: Value Function Approximation)

This post covers Lecture 6: Value Function Approximation (davidsilver.uk)

The entire course materials can be found on the following page: Teaching - David Silver.

Lecture Goal

Learn how to deal with a large-scale (potentially continuous) state space with RL
Learn value function approximation
Learn Deep Q-Network (DQN) and batch methods

Credit: Find order of polynomial approximation and LeastSquares for given datapoints

Value Function Approximation

Lookup table

Table store an entry for each lookup index.
Value-state

Index = \(\forall s \in S\), where \(S\) is a finite and discrete state space
Entry = \(V(s)\)

Action-state

Or every state-action pair \(s, a\) has an entry \(Q(s,a)\)
Or every state \(s\) has entries \(Q(s,a)\) for all actions \(a \in A\)

So far, we have represented a value function by a lookup table.

Large MDPs

Memory inefficiency: too many states or actions to store in memory
Too slow to learn the value of each state individually

Note: neighboring states might strongly correlate with each other, and we may utilize the characteristic to learn a value function.

Solution for large MDPs

Estimate a value function with function approximation

\(\hat{v}(s,\mathbf{w}) \approx v_{\pi}(s)\)
or \(\hat{q}(s,a,\mathbf{w}) \approx q_{\pi}(s,a)\)
, where \(\mathbf{w}\) is a set (vector) of parameters of the function approximator

Generalize from seen states to unseen states
Update parameter \(\mathbf{w}\) using MC or TD learning

Requirements for Value Function Approximators

RL considers differentiable function approximators, e.g.

Linear combination of features (linear regressor);
Neural network (non-linear regressor).

Furthermore, we require a training method that is suitable for non-stationary and non-i.i.d data.

I.i.d random variables = independent and identically distributed random variables
State-/action-value keeps change during every episode and every step.
Typically, classification models assume stationary and i.i.d data (e.g., CIFAR10).

Ideal Incremental Methods for Updating Value Function Approximators

Gradient descent

Goal: find parameter vector \(\mathbf{w}\) minimizing mean-squared error between \(\hat{v}(s,\mathbf{w})\) (i.e., value function approximator) and \(v_{\pi}(s)\) (i.e., true value)

\(J(\mathbf{w}) = \mathbb{E}_{\pi}[(v_{\pi}(S) - \hat{v}(S, \mathbf{w}))^2]\)

Gradient descent finds a local mimimum by velocity of \(\Delta \mathbf{w}\), where

\(\Delta \mathbf{w} = - \frac{1}{2}\alpha \nabla_{\mathbf{w}} J(\mathbf{w})
\\ = \alpha \mathbb{E}_{\pi}[(v_{\pi}(S) - \hat{v}(S, \mathbf{w}))\nabla_{\mathbf{w}}\hat{v}(S,\mathbf{w})] \)
\(\mathbf{w} \leftarrow \mathbf{w} + \Delta \mathbf{w}\)
and a step size hyperparameter \(\alpha\).
Note: 원래는 policy evaluation 과정에서 lookup table 내의 각 entry를 \(Q(S,A) \leftarrow Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A))\) 식을 통해 update했다. 이제부터는 lookup table이 아니라 function approximator를 쓸 거고, 그를 업데이트하기 위해 parameter space에서 \(\mathbf{w} \leftarrow \mathbf{w} + \Delta \mathbf{w}\)로 update할 거다. 아래 Control with Value Function Approximation 참고
Repeat this procedure until convergence

Expect that \(v_{*} \leftarrow \hat{v}\) during policy iteration

Stochastic gradient descent samples the gradient by a single value-/action-state sample (in this case, \(s \in S\)):

For every episode and every step in an episode:

\(\Delta \mathbf{w} = \alpha (v_{\pi}(s) - \hat{v}(s, \mathbf{w}))\nabla_{\mathbf{w}}\hat{v}(s,\mathbf{w}) \)
\(\mathbf{w} \leftarrow \mathbf{w} + \Delta \mathbf{w}\)

Repeat this procedure until convergence
The expected update is equal to the full gradient update.

In practice, the true value function \(v_{\pi}\) is not given at all!

Function Approximator Example: Linear Model

Feature vector

Represents a state by a vector of features
For example:

Coordinates, velocity, and acceleration of a robot
Stock prices in the stock market
Piece and pawn configurations in chess

Linear model

\(\hat{v}(s,\mathbf{w}) = (\mathrm{feature\; vector})^T \mathbf{w}\)
\(\therefore \nabla_{\mathbf{w}} \hat{v}(s,\mathbf{w}) = (\mathrm{feature\; vector})\)
Note: \(\Delta \mathbf{w} = \alpha (v_{\pi}(s) - \hat{v}(s, \mathbf{w}))\nabla_{\mathbf{w}}\hat{v}(s,\mathbf{w}) \)

In practice, the true value function \(v_{\pi}\) is not given at all!!

Incremental Prediction Methods for Updating Value Function Approximators

RL is not supervised learning as we assumed above (i.e., we don't know the true value samples \(v_{\pi}\)).
In practice, we substitute a MC/TD target for \(v_{\pi}\).

That is, the target dataset is also noisy in the sense of supervised learning!
Even worse, a MC/TD target is non-stationary and non-i.i.d..

참고로 이때의 MC/TD target은 model parameter \(\mathbf{w}\)에 대해 상수라고 놓고 gradient를 계산한다. 즉 \(\nabla_{\mathbf{w}}G_t\) 등은 무시한다. Target도 model parameter의 함수라 두고 gradient를 계산하는 알고리즘도 있지만, 단순하게 미분하면 오답으로 수렴한다.

Linear model이 아니면 \(\mathbf{x}(S_t)\) 자리에 \(\nabla_{\mathbf{w}}\hat{v}(S_t,\mathbf{w})\) 넣으면 된다.
이때의 eligibility trace는 TD에서 배웠던 state별 trace와는 다르다. 이건 오직 model의 parameter \(\mathbf{w}\)를 update하기 위한 eligibility trace이다. 지금껏 배웠던 state별 trace를 계산할 때는 특정 state에 도착할 때 eligibility를 상승시키기 위해서 \(\mathbf{1}(S_t=s)\) 값을 고려하지만, function approximator에서는 어떤 state에 있느냐에 상관없이 항상 parameter 전체를 update해야 하므로, \(\mathbf{1}(\cdot)\)는 필요 없다.

TD에서 배웠던 state trace:

Forward와 backward의 \(\sum_{t=1}^{\infty}\Delta \mathbf{w}_t\)를 비교하면 같다.

Monte Carlo with value function approximation

An MC target, return \(G_t\), is an unbiased estimator of true value \(v_{\pi}\).
Though the return is unbiased, it is so noisy that MC evaluation converges to a local optimum even when using a non-linear value function approximator.

Temporal-difference with value function approximation

Though a TD target is biased, linear TD(0) converges (close) to the global optimum.

Action-value function approximation도 비슷하게 해주면 된다.

Control with Value Function Approximation

별거 없고, \(\epsilon\)-greedy 써서 policy improvement하면 된다.

Repeat for each episode:

Choose a starting state \(S\) randomly
Choose an action from the state using policy derived from the (initialized) action-value approximator (\(\epsilon\)-greedy)
Repeat until terminal:

Take action, observe a reward and a next state \(S'\)
Choose an action from the approximator as above (\(\epsilon\)-greedy)
Calculate a TD/MC target
Update the approximator:

\(\mathbf{w} \leftarrow \mathbf{w} + \Delta \mathbf{w}\)
as an analogous to \(Q(S,A) \leftarrow Q(S,A) + \alpha(R+\gamma Q(S',A') - Q(S,A))\)

Proceed to the next state and action

On-policy SARSA 참고:

Parameter Convergence of Prediction Algorithms

TD는 on-policy + non-linear 케이스와 off-policy 케이스 때 policy evaluation iteration 중 value approximator update가 발산하는 예가 있다. Empirical하게는 안전 (MC는 이론상 항상 안전).
Gradient TD는 이 문제를 완전히 해결한다.

Parameter Convergence of Control Algorithms

Batch Prediction Methods for Updating Value Function Approximators

Stochastic gradient descent에서는 한 번 \(\mathbf{w} \leftarrow \mathbf{w} + \Delta \mathbf{w}\)로 update하고 나면, 해당 transition에 관한 정보를 버렸다. transition에 관한 정보를 모아서 계속 재활용하자는 게 batch RL.

Deep Q-Networks (DQN)

Q-learning with function approximation
DQN이 다양한 atari 게임을 잘 학습했던 주 요인 두 가지:

Experience replay

원래 stochastic GD는 sample 하나만 갖고 학습해서 full GD에서 활용하는 expected gradient를 잘 근사할 거라는 가정이 옳아야 잘 동장한다. 그러나 이제껏 배운 것처럼 incremental하게 배우면 각 episode에서 인접한 transition 쌍인 \(S_t, S_{t+1}\)들이 지나치게 서로 연관성이 높아서 학습에 방해된다. 다양한 데이터에 관해 동시에 사용하여 batch gradient를 구해야 제대로 expected gradient를 구할 수 있고, 학습 효율이 증가한다.

Fixed Q-targets

Bootstrap(다음 state/action의 value를 추정)용 neural network과 action-value를 학습할 network를 분리한다 (target, behavior network 분리).
아래 슬라이드에서 보이는 바와 같이, bootstrap할 때는 이전에 배워둔 네트워크를 (e.g., 1000 step 전의 model paramaters) 이용해 Q target를 계산하고, 막상 Q target을 배우는 건 또 다른 네트워크이다 (e.g., 현재의 model parameters).
Note: model parameters에 관한 replay buffer를 만든 뒤 그들의 ensemble 모델을 갖고 bootstrap할 수도 있을 듯