<p>You can choose any function approximator that is differentiable.
Two commonly used classes of value function approximators are:</p>

<ol>
<li><p>Linear function approximators: Linear combinations of features</p>

<pre><code> For approximating Q (the action-value)
 1. Find features that are functions of states and actions.
 2. Represent q as a weighted combination of these features.
</code></pre>

<p><a href="https://i.stack.imgur.com/8jZuk.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8jZuk.gif" alt="enter image description here"></a></p>

<p>where <a href="https://i.stack.imgur.com/ujHyW.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ujHyW.gif" alt="phi_sa"></a> is a vector in <a href="https://i.stack.imgur.com/gcc4q.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gcc4q.gif" alt="Rd"></a> with <a href="https://i.stack.imgur.com/Enalq.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Enalq.gif" alt="ith"></a> component given by <a href="https://i.stack.imgur.com/lNjix.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lNjix.gif" alt="enter image description here"></a> and <a href="https://i.stack.imgur.com/zPEq4.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zPEq4.gif" alt="w"></a> is the weight vector <a href="https://i.stack.imgur.com/akfxk.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/akfxk.gif" alt="enter image description here"></a> whose <a href="https://i.stack.imgur.com/Enalq.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Enalq.gif" alt="ith"></a> componenet is given by <a href="https://i.stack.imgur.com/ZJ1o0.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZJ1o0.gif" alt="enter image description here"></a>.</p></li>
<li><p>Neural Network</p>

<p>Represent <a href="https://i.stack.imgur.com/zlo1v.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/zlo1v.gif" alt="qSAW"></a> using a neural network. You can either approximate using <em>action-in</em> (left of figure below) type or <em>action-out</em> (right of figure below) type. The difference being that the neural network can either take as input representations of both the state and the action and produce a single value (<em>Q-value</em>) as the output or take as input only the representation of state <code>s</code> and provide as output one value for each action, <em>a</em> in the action space (This type is easier to realize if the action space is discrete and finite).</p>

<p><a href="https://i.stack.imgur.com/c5xAJ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/c5xAJ.png" alt="enter image description here"></a></p>

<p>Using the first type (<em>action-in</em>) for the example as it is close to the example in the linear case, you could create a Q-value approximator using a neural network with the following approach:</p>

<pre><code>  Represent the state-action value as a normalized vector
  (or as a one-hot vector representing the state and action)
  1. Input layer : Size= number of inputs
  2. `n` hidden layers with `m` neurons
  3. Output layer: single output neuron
  Sigmoid activation function.
  Update weights using gradient descent as per the * semi-gradient Sarsa algorithm*.
</code></pre>

<p>You could also directly use the visuals (if available) as the input and use convolutional layers like in the <a href="https://arxiv.org/pdf/1312.5602" rel="nofollow noreferrer">DQN paper</a>. But read the note below regarding the convergence and additional tricks to stabilize such non-linear approximator based method.           </p></li>
</ol>

<hr>

<p>Graphically the function approximator looks like this:</p>

<p><a href="https://i.stack.imgur.com/pSa4o.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/pSa4o.png" alt="linearFA"></a></p>

<p>Note that <a href="https://i.stack.imgur.com/mMdzE.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/mMdzE.gif" alt="varphi_eqphi"></a> is an <a href="https://en.wikipedia.org/wiki/Elementary_function" rel="nofollow noreferrer">elementary function</a> and <a href="https://i.stack.imgur.com/O8yd5.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/O8yd5.gif" alt="xi"></a> is used to represent elements of the state-action vector.
   You can use any elementary function in place of <a href="https://i.stack.imgur.com/E44Fl.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/E44Fl.gif" alt="enter image description here"></a>. Some common ones are linear regressors, <a href="https://en.wikipedia.org/wiki/Radial_basis_function#Approximation" rel="nofollow noreferrer">Radial Basis Functions</a> etc.</p>

<p>A <em>good differentiable function</em> depends on the context. But in reinforcement learning settings, convergence properties and the error bounds are important. The <em>Episodic semi-gradient Sarsa</em> algorithm discussed in the book has similar convergence properties as of TD(0) for a constant policy.</p>

<p>Since you specifically asked for on-policy prediction, using a <em>linear</em> function approximator is advisable to use because it is guaranteed to converge. The following are some of the other properties that make the Linear function approximators suitable:</p>

<ul>
<li>The error surface becomes a quadratic surface with a single minimum with mean square error function. This makes it a sure-shot solution as gradient descent is guaranteed to find the minima which is the global optimum.</li>
<li><p>The error bound (as proved by <a href="http://castlelab.princeton.edu/ORF544/Readings/Tsitsiklis%20van%20Roy%20-%20Analysis%20of%20Temporal-Difference%20Learning%20with%20Function%20Approximations-IEEE%20TAC.pdf" rel="nofollow noreferrer">Tsitsiklis &amp; Roy,1997</a> for the general case of TD(lambda) ) is:</p>

<p><a href="https://i.stack.imgur.com/ZH7HR.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZH7HR.gif" alt="enter image description here"></a></p>

<p>Which means that the asymptotic error will be no more than <a href="https://i.stack.imgur.com/Y78BK.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Y78BK.gif" alt="enter image description here"></a> times the smallest possible error. Where <a href="https://i.stack.imgur.com/2Upqn.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/2Upqn.gif" alt="gamma"></a> is the discount factor.
The gradient is simple to calculate! </p></li>
</ul>

<p>Using a non-linear approximator (like a (deep) neural network) however does not inherently guarantee convergence.
Gradient TD method uses the true gradient of the projected bellman error for the updates instead of the <em>semi-gradient</em> used in the <em>Episodic semi-gradient Sarsa algorithm</em> which is known to provide <a href="https://papers.nips.cc/paper/3809-convergent-temporal-difference-learning-with-arbitrary-smooth-function-approximation.pdf" rel="nofollow noreferrer">convergence even with non-linear function approximators</a> (even for off-policy prediction) if certain conditions are met.</p>
Choose function for On-Policy prediction with approximation
<p>I am currently reading Sutton's introduction about reinforcement learning. After arriving in chapter 10 (On-Policy prediction with approximation), I am now wondering how to choose the form of the function <code>q</code> for which the optimal weights <code>w</code> shall be approximated.</p>

<p>I am referring to the first line of the pseudo code below from Sutton: How do I choose a good differentiable function <a href="https://i.stack.imgur.com/xrbyk.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xrbyk.gif" alt="enter image description here"></a>? Are there any standard strategies to choose it?</p>

<p><a href="https://i.stack.imgur.com/NM3wo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NM3wo.png" alt="enter image description here"></a></p>