기록: 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 = $\mathrm{\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 $\mathrm{\Delta }\mathbf{w}$, where
• $$\begin{gathered} \mathrm{\Delta }\mathbf{w}=-\frac{1}{2}\alpha {\mathrm{\nabla }}_{\mathbf{w}}J(\mathbf{w}) \\ =\alpha {\mathbb{E}}_{\pi }[(v_{\pi }(S)-\hat{v}(S,\mathbf{w})){\mathrm{\nabla }}_{\mathbf{w}}\hat{v}(S,\mathbf{w})] \end{gathered}$$
  $\mathbf{w}\leftarrow \mathbf{w}+\mathrm{\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^{\prime },A^{\prime })-Q(S,A))$ 식을 통해 update했다. 이제부터는 lookup table이 아니라 function approximator를 쓸 거고, 그를 업데이트하기 위해 parameter space에서 $\mathbf{w}\leftarrow \mathbf{w}+\mathrm{\Delta }\mathbf{w}$로 update할 거다. 아래 Control with Value Function Approximation 참고
• Repeat this procedure until convergence
• Expect that $v_{\ast }\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:
• $\mathrm{\Delta }\mathbf{w}=\alpha (v_{\pi }(s)-\hat{v}(s,\mathbf{w})){\mathrm{\nabla }}_{\mathbf{w}}\hat{v}(s,\mathbf{w})$
  $\mathbf{w}\leftarrow \mathbf{w}+\mathrm{\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}\mathrm{vector}{)}^T\mathbf{w}$
  $\therefore {\mathrm{\nabla }}_{\mathbf{w}}\hat{v}(s,\mathbf{w})=(\mathrm{feature}\mathrm{vector})$
• Note: $\mathrm{\Delta }\mathbf{w}=\alpha (v_{\pi }(s)-\hat{v}(s,\mathbf{w})){\mathrm{\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를 계산한다. 즉 ${\mathrm{\nabla }}_{\mathbf{w}}{G}_t$ 등은 무시한다. Target도 model parameter의 함수라 두고 gradient를 계산하는 알고리즘도 있지만, 단순하게 미분하면 오답으로 수렴한다.
• 
• Linear model이 아니면 $\mathbf{x}(S_t)$ 자리에 ${\mathrm{\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}^{\mathrm{\infty }}\mathrm{\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

• 별거 없고, $ϵ$-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 ($ϵ$-greedy)
• Repeat until terminal:
• Take action, observe a reward and a next state $S^{\prime }$
• Choose an action from the approximator as above ($ϵ$-greedy)
• Calculate a TD/MC target
• Update the approximator:
• $\mathbf{w}\leftarrow \mathbf{w}+\mathrm{\Delta }\mathbf{w}$
• as an analogous to $Q(S,A)\leftarrow Q(S,A)+\alpha (R+\gamma Q(S^{\prime },A^{\prime })-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}+\mathrm{\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할 수도 있을 듯
• 
• 덕분에 oscilication이나 훈련 과정에서 loss가 폭발하는 일이 없음. 훈련이 안정화.