2
$\begingroup$

In Sutton and Barto's book (Chapter 6: TD learning, 2nd edition), he mentions two ways of updating value function:

  1. Monte Carlo method: $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$.
  2. TD(0) method: $V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$.

I understand that $\alpha$ acts like a learning rate where it take some proportion of MC/TD error and update value function.

From my understanding, in stationary environments, transition probability distribution and reward distribution don't vary with time. Hence, one should supposedly use $\alpha-$decay to update value functions. On the other hand, since distributions change with time in non-stationary environments, $\alpha$ should be kept constant so as to keep updating the value function with recent TD/MC errors (in other words, history doesn't matter).

What's been bothering me is that in Example 6.2, 6.5, and 6.7, probability and reward distribution doesn't change. So why is constant-$\alpha$ being used?

Question: How does $\alpha$ vary in stationary and non-stationary environments?

$\endgroup$
2
$\begingroup$

So why is constant-$\alpha$ being used?

This is because control scenarios are inherently non-stationary with respect to value functions. Decaying alpha comes with a risk that improvements to the policy will occur progressively more slowly, because the impact to changing the policy will be learned slowly.

From my understanding, in stationary environments, transition probability distribution and reward distribution don't vary with time.

This is correct when considering immediate reward and transitions from any give $(s,a)$ pair. However you are forgetting that the policy function $\pi(a|s)$ does vary with time whilst the agent is discovering the optimal policy, and this affects trajetories and expected values that are being estimated.

Question: How does $\alpha$ vary in stationary and non-stationary environments?

For non-stationary environments, you will want to maintain some minimum learning rate $\alpha$ and also some mininum exploration ($\epsilon$ if you are using $\epsilon$-greedy exploration).

In stationary environments, then a learning rate schedule is still valid and may be useful. You will see it discussed in passing when referencing proofs of convergence for the basic algorithms.

For example in the second edition of Reinforcement Learning: An Introduction it says this regarding convergence of Q learning:

Under this assumption and a variant of the usual stochastic approximation conditions on the sequence of step-size parameters, Q has been shown to converge with probability 1 to $q_*$.

The "usual stochastic approximation conditions on the sequence of step-size parameters" part is a reference to decaying the learning rate.

However, due to the added complexity of handling exploration vs exploitation, the inherently non-stationary nature of value predictions in control scenarios, and the difficulty of getting function approximation to work, discussions of learning rate decay is a minor detail in texts like Sutton & Barto.

$\endgroup$
3
  • $\begingroup$ I don't follow how "this affects trajectories and expected values that are being estimated" relate to non-stationary environment. Regardless of what policy I follow, for a particular state-action pair, won't $R(s, a, s')$ be sampled from the same distribution (albeit, varying rewards)? $\endgroup$
    – user529295
    Aug 11 '21 at 17:56
  • 1
    $\begingroup$ @user529295 Yes, but the total return is dependent on the whole trajectory, which in turn depends on the policy, which is changing. Hence non-stationary expected returns (not individual expected rewards) even if the environment is itself stationary $\endgroup$ Aug 11 '21 at 18:29
  • $\begingroup$ Ah! Makes sense. $\endgroup$
    – user529295
    Aug 11 '21 at 18:34

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.