13
$\begingroup$

In reinforcement learning, linear function approximation is often used when large state spaces are present. (When look up tables become unfeasible.)

The form of the $Q-$value with linear function approximation is given by

$$Q(s,a) = w_1 f_1(s,a) + w_2 f_2(s,a) + \cdots, $$

where $w_i$ are the weights, and $f_i$ are the features.

The features are predefined by the user. My question is, how are the weights assigned?

I have read/downloaded some lecture slides on $Q-$learning with function approximation. Most of them have slides on linear regression that follow. Since they are just slides, they tend to be incomplete. I wonder what the connection/relation is between the two topics.

$\endgroup$

1 Answer 1

16
+50
$\begingroup$

Function approximation is basically a regression problem (in the general sense, i.e. opposed to classification where the class is discrete), i.e. one tries to learn a function mapping from input (in your case $f(s,a)$) to a real-valued output $Q(s,a)$. Since we do not have a full table of all input / output values, but instead learn and estimate $Q(s,a)$ at the same time, the parameters (here: the weights $w$) cannot be calculated directly from the data. A common approach here is to use gradient descent.

Here is the general algorithm for learning $Q(s,a)$ with Value Function Approximation

  • Init parameter-vector $w=(w_1,w_2,....,w_n)$ randomly (e.g. in [0,1])
  • For each episode:

    1. $s\leftarrow$initial state of episode
    2. $a\leftarrow$action given by policy $\pi$ (recommend: $\epsilon$-greedy)
    3. Take action $a$, observe reward $r$ and next state $s'$
    4. $w\leftarrow w+ \alpha(r+\gamma * max_{a'}Q(s',a') - Q(s,a)) \vec\nabla_wQ(s,a)$
    5. $s\leftarrow s'$

    Repeat 2-5 until $s$ is terminal

where ...

  • $\alpha\in[0,1]$ is the learning rate
  • $\gamma\in[0,1]$ is the discount rate
  • $max_{a'}Q(s',a')$ is the action $a'$ in state $s'$ maximizing $Q(s',a)$
  • $\vec\nabla_wQ(s,a)$ is the gradient of $Q(s,a)$ in $w$. In your linear case, the gradient is simply a vector $(f_1(s,a),...,f_n(s,a))$

The parameters/weights-update (4th step) can be read in such a way:

  • $(r+\gamma * max_a'Q(s',a')) - (Q(s,a))$ is the error between prediction $Q(s,a)$ and the "actual" value for $Q(s,a)$, which is the reward $r$ obtained now PLUS the expected, discounted reward following the greedy policy afterwards $\gamma * max_a'Q(s',a')$
  • So the parameter/weight-vector is shifted into the steepest direction (given by the gradient $\vec\nabla_wQ(s,a)$) by the amount of the measured error, adjusted by $\alpha$.

Main Source:

Chapter 8 Value Approximation of the (overall recommended) book Reinforcement Learning: An Introduction by Sutton and Barto (First Edition). The general algorithm has been modified as it is commonly done to calculate $Q(s,a)$ instead of $V(s)$. I have also dropped the eligibility traces $e$ to focus on gradient descent, hence using only one-step-backups

More references

$\endgroup$
5
  • 3
    $\begingroup$ Broken link for Barto & Sutton! Now here -> incompleteideas.net/book/the-book.html :) and as ebook incompleteideas.net/book/ebook but i don't know where to find a mobi file $\endgroup$ Commented Jan 6, 2019 at 23:18
  • 1
    $\begingroup$ Isn't the gradient of Q(s,a) in relation to w a column vector where each element is fi(s,a), instead of being the summation of all fi as you said? The objective is that each weight is changed accordingly to the value of the feature it is multiplicating to. $\endgroup$ Commented Dec 30, 2019 at 2:21
  • $\begingroup$ @MiguelSaraiva Yes, fixed it. Thank you very much. $\endgroup$
    – steffen
    Commented Dec 30, 2019 at 22:30
  • $\begingroup$ Isn't Q-learning off-policy? Why take an action according to policy $\pi$? $\endgroup$
    – mesllo
    Commented Dec 16, 2021 at 14:14
  • $\begingroup$ @mesllo Here are some great explanations: stats.stackexchange.com/questions/184657/… $\endgroup$
    – steffen
    Commented Dec 26, 2021 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.