Part 10 - Reinforcement Learning: Function Approximation and Introduction to Deep RL

If we instead can find a good approximate solution using limited computational resources, while not losing (much) generalization, we can solve much larger problems.

But, how can experience with a limited subset of the state space be used to produce a good approximation for the entire state space?

This is what function approximation aims to solve.

We represent the state value function approximation as a parameterized function with weight vector $\mathbf{w} \in \mathbb{R}^d$,

$\hat{v}$ might be a linear function but it can also be a function computed by a neural network.

Typically, the number of (shared) weights (the dimensionality of $\mathbf{w}$) is much smaller than the number of states, i.e., $d \ll |\mathcal{S}|$. When a single state is updated, the change generalizes from that state to affect the values of many other states.

We denote the individual update (target) by the notation $s \mapsto u$,

• MC Updatew: $S_t \mapsto G_t$

• TD(0) Update: $S_t \mapsto R_{t + 1} + \gamma \hat{v}(S_{t + 1}, \mathbf{w})$

• $n$-step TD Update: $S_t \mapsto G_{t:t+n}$

• DP Update: $s \mapsto \mathbb{E}_{\pi}[R_{t + 1} + \gamma \hat{v}(S_{t + 1}, \mathbf{w}) | S_t = s]$

The update $s \mapsto u$ means that the estimated value for state $s$ should be “more like” the updated target $u$.

Thus, we can treat this as a supervised learning problem! However, there is a fundamental difference, in classical supervised learning, we have a stating training dataset. While in RL, learning occurs online (i.e., when the agent interacts with the environment), and the targets are incremental (i.e., non i.i.d. data) and non-stationary (i.e., the target changes as the value function changes).

For a supervised learning task, we need some notion of error or loss, a common choice is the mean squared value error ($\bar{VE}$),

where $\mu(s)$ is the weighting factor such that $\mu(s) \geq 0, \sum_s \mu(s) = 1$, is chosen to be the fraction of the time spent in state $s$ under policy $\pi$ (also called the on-policy distribution).

Another common choice is the square root of $\bar{VE}$, called the root mean squared value error (RMSVE).

Let $h(s)$ be the probability that an episode starts in state $s$. Further, let $\eta(s)$ be the number of time steps spent, on average, in state $s$ in a single episode,

This system of equations can be solved for the expected number of visits $\eta(s)$ to each state $s$.

The on-policy distribution is then obtained by normalization,

The next logical step would be to find a global optimum, in terms of the weights $\mathbf{w}$, that minimizes the prediction objective $\bar{VE}(\mathbf{w})$. This is possible if we have a nice simple function, such as linear, convex, or differentiable. However, this is rarely possible for more complex models, such as neural networks.

Thus, we instead will suffice with finding a local optimum.

Firstly, the weightt vector is a column vector with a fixed number of real valued elements,

Secondly, the function $\hat{v}(s, \mathbf{w})$ is a differentiable function with respect to $\mathbf{w} \forall s \in \mathcal{S}$.

Since we will be updating $\mathbf{w}$ at each of a series of discrete time steps $t = 0, 1, 2, \ldots$, we will denote the weight vector at time $t$ by $\mathbf{w}_t$. Further, assume at time step $t$, the agent observes a new example $S_t \mapsto v_{\pi}(S_t)$ consisting of a state $S_t$ and its (true) value under the policy.

Lastly, for simplicity, assume that the states appearing in the examples have the same distribution $\mu(s)$.

Thus, the SGD update rule is given by,

where $\alpha > 0$ is the step-size parameter (or learning rate).

However, unlike the classical supervised learning setting, in RL we do not have acces to the true value $v_{\pi}(S_t)$. Instead, we have to use an approximate target $U_t \in \mathbb{R}$ of the $t$-th training example $S_t \mapsto U_t$, e.g., a noise-corrupted version of the true value or a bootstrapped estimate.

In this setting, we simply substitute $U_t$ for $v_{\pi}(S_t)$ in the SGD update rule,

Input: the policy $\pi$ to be evaluated

Input: a differentiable function $\hat{v} : \mathcal{S} \times \mathbb{R}^d \rightarrow \mathbb{R}$

Algorithm parameter: step-size $\alpha > 0$

Initialize value-function weights $\mathbf{w} \in \mathbb{R}^d$ arbitrarily (e.g., $\mathbf{w} = \mathbf{0}$)

Loop forever (for each episode):

• Generate an episode $S_0, A_0, R_1, S_1, A_1, \ldots, R_T, S_T$ using policy $\pi$
• Loop for each step of episode $t = 0, 1, \ldots, T - 1$:
  • $\mathbf{w} \leftarrow \mathbf{w} + \alpha [G_t - \hat{v}(S_t, \mathbf{w})] \nabla \hat{v}(S_t, \mathbf{w})$

When we are dealing with bootstrapping targets, such as the $n$-step TD target $G_{t:t+n}$ or the DP target $\sum_{a, s^{\prime}, r} \pi(a | S_t) \mathcal{p}(s^{\prime}, r | S_t, a) [r + \gamma \hat{v}(s^{\prime}, \mathbf{w})]$, all depend on the current value of the weight vector $\mathbf{w}_t$. Thus, the targets will be biased and they will not produce a true gradient descent method.

We instead call these methods semi-gradient methods.

Input: the policy $\pi$ to be evaluated

Input: a differentiable function $\hat{v} : \mathcal{S} \times \mathbb{R}^d \rightarrow \mathbb{R}$ such that $\hat{v}(\text{terminal}, \cdot) = 0$

Algorithm parameters: step-size $\alpha > 0$

Initialize value-function weights $\mathbf{w} \in \mathbb{R}^d$ arbitrarily (e.g., $\mathbf{w} = \mathbf{0}$)

Loop for each episode:

• Initialize $S$
• Loop for each step of episode:
  • Choose $A \sim \pi(\cdot | S)$
  • Take action $A$, observe $R, S^{\prime}$
  • $\mathbf{w} \leftarrow \mathbf{w} + \alpha [R + \gamma \hat{v}(S^{\prime}, \mathbf{w}) - \hat{v}(S, \mathbf{w})] \nabla \hat{v}(S, \mathbf{w})$
  • $S \leftarrow S^{\prime}$
• until $S$ is terminal

A simple form of generalizing function approximation is state aggregation, where states are grouped together, with one estimated value (one element in the weight vector $\mathbf{w}$) for each group. The value of a state is estimated as its group’s component, and when the state is updated, that component alone is updated.

Thus, this is a special case of SGD in which the gradient $\nabla \hat{v}(s, \mathbf{w})$ is 1 for $S_t$’s group’s component and 0 for all other components.

A more general and powerful form of function approximation is linear methods, where the value of a state is estimated as a linear combination of features. For every state $s$, there is a vector $\mathbf{x}(s) \coloneqq \begin{bmatrix} x_1(s) & x_2(s) & \ldots & x_d(s) \end{bmatrix}^T$ with the same number of components as $\mathbf{w}$.

Linear methods approximate the state-value function by,

The real valued vector $\mathbf{x}(s)$ is called the feature vector representing state $s$.

The gradient of the linear approximate value function with respect to $\mathbf{w}$ is simply the feature vector,

Thus, the SGD update is,

Further, local optima are guaranteed to be global optima 22Why? The answer is, the prediction objective $\bar{VE}(\mathbf{w})$ is a quadratic function in terms of $\mathbf{w}$, thus it is convex..

Neural networks are widely used for nonlinear function approximation [^1] in RL. They can for example use the TD error/target to learn value functions. We use backpropagation to estimate the partial derivative of an objective function with respect to each weight in the network.

However, they can suffer from overfitting, especially for deep networks with many layers and parameters.

So far, we have discussed the parametric approach to approximating value functions, let’s summarize the main points.

• A learning algorithm adjusts the parameters of a functional form intended to approximate the value function.
• Each update $s \mapsto g$ is a training example used by the learning algorithm to change the parameters with the aim of reducing the approximation error.
• After the update, the training example can be discarded (although, it might be saved to be used again).
• When an approximate value of a state (sometimes called the query state) is needed, the function is simply evaluated at that state using the latest parameters produced by the learning algorithm.

In the parametric setting, we update the parameters each time we receive a new training example, and then discard the example. However, in the non-parametric (memory-based) setting, we store the training examples without explicitly updating a parameterized function.

Whenever a query state’s value is needed, a set of examples is retrieved from memory and used to compute a value estimate for the query state. It is also sometimes called, lazy learning, because processing training examples is postponed until the system is queried to provide an output.

Local-learning methods are a class of methods where we approximate a value function only locally in the neighborhood of the current query state. The closer a training example’s state is to the query state, the more relevant it is considered to be. Distance can be defined in many different ways, e.g., Euclidean distance, Manhattan distance, or domain-specific distance measures.

An example is the nearest neighbor method, it simply finds the example in memory whose state is closest to the query state and returns that example’s valuea s the approximate value of the query state.