2
$\begingroup$

In Temporal-Difference Learning, we update our value function by $V\left(S_{t}\right) \leftarrow V\left(S_{t}\right)+\alpha\left(R_{t+1}+\gamma V\left(S_{t+1}\right)-V\left(S_{t}\right)\right)$

If we choose a constant $\alpha$, will the algorithm eventually give us the true state value function? Why or why not?

$\endgroup$
2
  • $\begingroup$ There are multiple TD-learning algorithms (e.g. Q-learning, SARSA, or even just policy evaluation algorithms, which is what you seem to be referring to). It may be a good idea to clarify what you're exactly referring to (e.g. provide the link to or name of section/chapter of book that describes the algorithm you have in mind: for example, this one https://incompleteideas.net/book/RLbook2020.pdf#page=142), so that people do not misinterpret your question/context. $\endgroup$
    – nbro
    Oct 16 '21 at 13:44
  • 2
    $\begingroup$ @nbro: This looks like single-step TD learning for sample-based policy evaluation, not a specific optimal control algorithm (and not dynamic programming). This is the core of many model-free prediction and control algorithms, and described in S&B chapter 6 sections 1 to 3. It would help if the OP did add some scope to the question, since in simple, tabular environments it is possible to guarantee exact convergence even with $\alpha = 1$ - whilst the answer so far focuses on function approximation, it is not clear if that is important to OP. $\endgroup$ Oct 17 '21 at 7:42
3
$\begingroup$

It should be noted that the selection of $\alpha$ is a classic problem in stochastic approximation, rather than a specific problem in RL. Once you know this it will be clear.

What is stochastic approximation? As its name suggests, it is a method that uses data to approximate (typically) expectations. For example, suppose \begin{align*} w=\mathbb{E}[X] \end{align*} where $X$ is a random variable. If we have some iid samples of $X$ as $\{x_i\}$, then we can estimate $w$ by \begin{align*} w_{k+1}=w_k-a _k(w_k-x_k). \end{align*}

Here, you note that $a _k$ is time-varying instead of a constant. In fact, in order to ensure the (almost surely) convergence of $w_k$, a necessary condition is \begin{align*} \sum_k a _k&=\infty\\ \sum_k a_k^2&<\infty \end{align*} Why such a condition is required? A rigorous proof can be found in Robbins-Monro Algorithm. Here, I merely show some intuition why it is necessary.

  • First, $\sum_{k=1}^\infty a_k=\infty$ says that have $a_k$ should be sufficiently large in order to counter arbitrary initial conditions. In particular, the mathematically reasoning is as follows: hypothetically if $\sum_{k=1}^\infty a_k<\infty$, and also $\delta_k\doteq w_k-x_k$ is bounded, we have $\sum_{k=1}^\infty a_k \delta_k<\infty$. As a result, the difference between $w_\infty$ and $w_1$ is bounded. If the initial condition is very far from the solution, then it is not able to converge to the true solution.
  • Secondly, the condition of $\sum_k a _k^2<\infty$ says that $a_k$ should converge to zero. In particular, mathematically, the difference between $w_k$ and $w_{k+1}$is $a_k\delta_k$. If $a_k$ does not go to zero, then $w_k$ and $w_{k+1}$ will still fluctuate significantly after when $k$ is very large.

Of course, if $a_k=\alpha$ is constant, then $\sum_k a _k^2<\infty$ is not satisfied.

Now, let's come back to the TD algorithm. In fact, it can be viewed as a stochastic approximation algorithm. In particular, recall that the Bellman equation is \begin{align} v_\pi(s)=\mathbb{E}[R+\gamma v_\pi(S')|s],\quad \forall s \end{align} If we write $X\doteq R+\gamma v_\pi(S')$, then it becomes $v_\pi(s)=\mathbb{E}[X|s]$, which is very similar to the case of $w=\mathbb{E}[X]$. Hence, the stochastic approximation algorithm solve such a equation using data is \begin{align}\label{eq_SAAlgorithmSolvingBellmanEquation} v_{t+1}(s_t) &=v_t(s_t)-a _t(s_t)[v_t(s_t)-(r_t+\gamma v_t(s_{t+1}))],\qquad t=1,2,\dots \end{align}

Now, you may see how TD is obtained and why the step size should be $a _t(s_t)$ instead of a constant.

$\endgroup$
0
$\begingroup$

In general, NO.

You don't get the "true" state value function. TD-learning approximates the true value function. It can be a very close, or even exact approximation in simple cases, but, in general, it is just an approximation.

Depending on the difficulty of the problem, a non-constant $\alpha$ value can help the policy approximate the true value function more quickly, or help the learning from getting stuck in a local minimum.

There are implementations, like ADAM, which will adaptively change the learning rate for each feature.

Usually, you can expect convergence must faster if you adaptively change the learning rate by using an implementation like ADAM (see this).

$\endgroup$
2
  • $\begingroup$ So why can't it get the "true" value function? Could you perhaps show it mathematically? $\endgroup$
    – GGG
    Oct 16 '21 at 12:50
  • $\begingroup$ Most of the time the "true" value function is not known, and cannot be known. We then use iterate learning to try to approximate this value function. A good read can be found here -> machinelearningmastery.com/…. Also sorry nbro, i meant 'non-constanct', i've fixed the post. $\endgroup$ Oct 17 '21 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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