RL 009

Function Approximation

$\hat{v}(s, \mathbf{w}) \approx v_\pi(s)$

$\hat{q}(s, a, \mathbf{w}) \approx q_\pi(s, a)$

• Incremental methods for prediction
• Model-free VFA: MC and TD targets

GPI, Generalized Policy Iteration

• Iterate between policy evaluation and policy improvement
• Policy Evaluation: Approximate policy evaluation. $\hat{q}(\cdot, \cdot, \mathbf{w}) \approx q_\pi$
• Policy Improvement: $\epsilon$-greedy policy improvement.

Types of Action-Value FA

$$s \to \text{FA}(\mathbf{w}) \to \hat{q}(s, \mathbf{w})$$

• State Value Function Approximation

$$(s, a) \to \text{FA}(\mathbf{w}) \to \hat{q}(s, a, \mathbf{w})$$

• Action Value Function Approximation
  • $\hat{q}(s, \text{Left}, \mathbf{w}) = 3.2$
  • $\hat{q}(s, \text{Right}, \mathbf{w}) = 8.7$

$$s \to \text{FA}(\mathbf{w}) \to \hat{q}(s,a_1, \mathbf{w}) \cdots \hat{q}(s,a_n, \mathbf{w})$$

• The network output is a vector of Q-values for each action.
• More convenient to use discrete action spaces.

Action	Q-value
Left	3.2
Right	8.7
Jump	5.3

Action VFA

$\hat{q}(s, a, \mathbf{w}) \approx q_\pi(s, a)$

• Approximate the Action-value function.
• Doing action $a$ at state $s$, Approximate the Q-value of that action.

$\mathcal{J} = \mathbb{E}_{\pi} \left[ (q_\pi(s, a) - \hat{q}(s, a, \mathbf{w}))^2 \right]$

• Minimize mean-squared error (MSE) between the approximate Q-value $\hat{q}(s, a, \mathbf{w})$ and the true Q-value $q_\pi(s, a)$.

$\Delta \mathbf{w} = \alpha (q_{\pi}(s,a) - \hat{q}(s,a,\mathbf{w})) \nabla_{\mathbf{w}} \hat{q}(s,a,\mathbf{w})$

• Use SGD to find the local minimum.
• $q_{\pi} - \hat{q}$ tells us how much the prediction is off from the target.
• $\nabla_{\mathbf{w}} \hat{q}(s,a,\mathbf{w})$ tells us how each weight affects the predicted $Q$-value.

Linear Action VFA

$$x(s, a) = \begin{bmatrix} x_1(s, a) \\ x_2(s, a) \\ \vdots \\ x_n(s, a) \end{bmatrix}$$

• Feature vector is used to represent the state and action pair.

$\hat{q}(s, a, w) \approx x(s, a)^T w = \sum_j x_j (s, a) w_j$

• Predicted Q-value is a linear combination of the feature values. (sum of each feature value $x_j$ multiplied by the weight $w_j$)

$$\begin{aligned} \hat{q}(s, a, w) = x(s, a)^T w \\ \hat{q} = x_1w_1 + x_2w_2 + \cdots + x_n w_n \end{aligned}$$

• $x_1, x_2, \cdots$: features of the state and action pair.
• $w_1, w_2, \cdots$: weights that need to be learned.
• derivative $\hat{q}$ with respect to $w$.
  • $\frac{\partial \hat{q}}{\partial w_1} = x_1$
  • $\frac{\partial \hat{q}}{\partial w_2} = x_2$

$$\nabla_w\hat{q} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = x(s, a)$$

• e.g. $\hat{q} = 2w_1 + 5w_2$, then $\nabla_w\hat{q} = \begin{bmatrix} 2 \\ 5 \end{bmatrix}$

$$\begin{aligned} \Delta w \\ &= \alpha (q_{\pi} - \hat{q}) \nabla_w\hat{q} \\ &= \alpha (q_{\pi} - \hat{q}) x(s, a) \\ &= \alpha (q_{\pi}(s, a) - \hat{q}(s, a, w)) x(s, a) \end{aligned}$$