Value Function Approximation

In the previous post, we introduced TD learning algorithms. At that time, all state/action values were represented by tables. This is inefficient for handling large state or action spaces.

In this post, we will use the function approximation method for TD learning. It is also where artificial neural networks are incorporated into reinforcement learning as function approximators.

Sources:

1. Shiyu Zhao. Chapter 8: Value Function Approximation. Mathematical Foundations of Reinforcement Learning.

TD learning with function approximation

With function approximation methods, the goal of TD learning is equivalent to is finding the best $w$ that can minimize the loss function $J(w)$ $$\begin{array}{}\text{(1)}& J(w)={\mathbb{E}}_{s\in \mathcal{S}}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]\end{array}$$ # Stationary distribution

The expectation in $\text{(1)}$ is with respect to the random variable $S\in \mathcal{S}$. There are several ways to define the probability distribution of $S$.

In reinforcement learning (RL), we commonly use the stationary distribution of $S$ as the distribution of $S$.

The stationary distribution of $S$ under policy $\pi$ can bedenoted by ${\{d_{\pi }(s)\}}_{s\in \mathcal{S}}$. By definition, $d_{\pi }(s)\ge 0$ and $\sum _{s\in \mathcal{S}}{d}_{\pi }(s)=1$.

Let $n_{\pi }(s)$ denote the number of times that $s$ has been visited in a very ong episode generated by $\pi$. Then, $d_{\pi }(s)$ can be approximated by $$d_{\pi }(s)\approx \frac{n_{\pi }(s)}{\sum _{s^{\prime }\in \mathcal{S}}{n}_{\pi }\left(s^{\prime }\right)}$$ Meanwhile, the converged values $d_{\pi }(s)$ can be computed directly by solving equation: $$d_{\pi }^T=d_{\pi }^T{P}_{\pi },$$ i.e., $d_{\pi }$ is the left eigenvector of $P_{\pi }$ associated with the eigenvalue 1. The proof is here.

Optimization algorithms

The loss function $\text{(1)}$ can be rewritten as $$J(w)=\mathbb{E}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]=\sum _{s\in \mathcal{S}}{d}_{\pi }(s){(v_{\pi }(s)-\hat{v}(s,w))}^2$$

While we have the objective function, the next step is to optimize it.

To minimize $J(w)$, we can use the gradient-descent algorithm: $$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J\left(w_k\right)$$

The true gradient is $$\begin{array}{rl}{\mathrm{\nabla }}_{w}J(w)& ={\mathrm{\nabla }}_w\mathbb{E}\left[{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]\\ & =\mathbb{E}\left[{\mathrm{\nabla }}_w{(v_{\pi }(S)-\hat{v}(S,w))}^2\right]\\ & =2\mathbb{E}\left[(v_{\pi }(S)-\hat{v}(S,w))(-{\mathrm{\nabla }}_w\hat{v}(S,w))\right]\\ & =-2\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w)){\mathrm{\nabla }}_w\hat{v}(S,w)]\end{array}$$

The true gradient above involves the calculation of an expectation. We can use the stochastic gradient to replace the true gradient: $$w_{t+1}=w_t+{\alpha }_t\left(v_{\pi }\left(s_t\right)-\hat{v}(s_t,w_t)\right){\mathrm{\nabla }}_w\hat{v}(s_t,w_t)$$ where $s_t$ is a sample of $S$. Here, $2{\alpha }_k$ is merged to ${\alpha }_k$. - This algorithm is not implementable because it requires the true state value $v_{\pi }$, which is the unknown to be estimated. - We can replace $v_{\pi }\left(s_t\right)$ with an approximation so that the algorithm is implementable.

In particular, - First, Monte Carlo learning with function approximation: Let $g_t$ be the discounted return starting from $s_t$ in the episode. Then, $g_t$ can be used to approximate $v_{\pi }\left(s_t\right)$. The algorithm becomes $$w_{t+1}=w_t+{\alpha }_t(g_t-\hat{v}(s_t,w_t)){\mathrm{\nabla }}_w\hat{v}(s_t,w_t)$$ - Second, TD learning with function approximation: By the spirit of TD learning, we can replace $v_{\pi }\left(s_t\right)$ with $r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)$. Please remember this substitution is not rigorous. The reason is omitted for simplicity.

After all, the algorithm becomes $$w_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]{\mathrm{\nabla }}_w\hat{v}(s_t,w_t)$$

Therefore, we can solve TD learning problems[^1] with the function approximation method.

TD learning of action values based on function approximation

Sarsa with function approximation

Algorithm 8.2

Suppose that $q_{\pi }(s,a)$ is approximated by $\hat{q}(s,a,w)$. Replacing $\hat{v}(s,w)$ in $$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)]{\mathrm{\nabla }}_w\hat{v}(s_t,w_t)$$ by $\hat{q}(s,a,w)$ gives $$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)]{\mathrm{\nabla }}_w\hat{q}(s_t,a_t,w_t).$$

Q-learning with function approximation

Algorithm 8.3

Tabular Q-learning can also be extended to the case of function approximation. The update rule is $$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \underset{a\in \mathcal{A}\left(s_{t+1}\right)}{max}\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)]{\mathrm{\nabla }}_w\hat{q}(s_t,a_t,w_t).$$

Here, the function approximator is $r_{t+1}+\gamma \underset{a\in \mathcal{A}\left(s_{t+1}\right)}{max}\hat{q}(s_{t+1},a,w_t)$. It's similar to Sarsa with function approximation except that $\hat{q}(s_{t+1},a_{t+1},w_t)$ is replaced with $\underset{a\in \mathcal{A}\left(s_{t+1}\right)}{max}\hat{q}(s_{t+1},a,w_t)$.

NOTE: altough Q-learning with function approximation can be implemented by neural networks. In practice, we choose to use, instead of this method, Deep Q-learning or deep Q-network (DQN). DQN is not Q learning, at least not the specific Q learning algorithm introduced in my post, but it shares the core idea of Q learning.

1 "TD learning problems" refer to the problems aimed to solve by TD learning algorithms, i.e., the state/action value function estimation given a dataset generated by a given policy $\pi$.