Adaptive Learning Rate Selection for Temporal Difference Learning

Harsh Gupta 1 R. Srikant 1 Lei Ying 2

Abstract
Temporal Difference (TD) learning is a widelyused class of algorithms in reinforcement learning. The success of TD learning algorithms relies
heavily on the choice of the learning rate used.
In this paper, we use recent results on finite-time
performance of TD learning with linear function
approximation to design an adaptive learning rate
selection rule. The rule comprises a diagnostic
test which determines whether the algorithm hasreached the steady-state, i.e., the algorithm has
stopped learning. Once such a determination is
made, the rule adapts the learning rate (reducing the step size) so that the algorithm continues
to learn. We implement our proposed rule on avariety of popular reinforcement learning applications and show that in all these scenarios, ourrule outperforms the best fixed learning rate aswell as other commonly used adaptive learning
rate selection rules.

1. Introduction
Reinforcement learning (RL) refers to a collection of learning algorithms to compute near optimal policies in dynamic
programming and Markov Decision Processes (MDP) when
the underying model is unknown or too complicated to describe. Here, we consider a critical component of RL, whichis the estimation of a value function of a given feedback
policy in an MDP. Temporal difference (TD) learning iscommonly used for this purpose, along with some form offunction approximation to approximate the value function.
Common function approximation schemes include linear
function and neural network approximations. In this paper,
we study TD learning with linear function approximation,
given Markovian samples from an MDP operating under afixed feedback/control policy.
The convergence rate of TD learning can vary significantly
1
ECE and CSL, University of Illinois at Urbana-Champaign,
USA 2 ECEE, Arizona State University, USA. Correspondence to:Harsh Gupta <hgupta10@illinois.edu>.

Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s).

depending on the learning rate rule that is used. The threecommonly studied learning rate rules are the following:• Diminishing learning rates: The most widely studied
learning rate rule in the theoretical literature is the diminishing learning rate rule motivated by the stochastic
approximation theory. Under this rule, if k denotes
the learning
Prate at time-stepPk, then {k } is chosen
to satisfy k k = ∞ and k 2k < ∞ (popularly
known as a Robbins-Monro sequence). The reason
for these conditions on the learning rates is that, underthese conditions, it can be shown that the TD learningalgorithm converges asymptotically with probability 1.
However, this learning rate rule is typically not used inpractice due to the fact that the learning rate quickly
becomes very small and thus, parameter updates under
TD learning change very slowly. In this family of learning rates, the most well-known is the simple back-off
strategy, which sets k = αk for some constant α > 0.
Note that we can replace k in the above strategy by k β ,where β ∈ ( 12 , 1], and still satisfy the Robbins-Monrosequence conditions (see (George & Powell, 2006) fora detailed discussion).
• Constant learning rate: The other extreme from diminishing learning rates is a constant learning rate, i.e.,k =  ∀k. The rationale here is that, since the learning rate is fixed, it cannot become arbitrarily small andhence, learning will never slow down. However, givena certain number of samples from which one has tolearn the value function, it may be difficult to determine the optimal or appropriate fixed  to use. If  is“large,” the learning proceeds quickly initially but theerror at the end will be large, and on the other hand, if 
is “small,” the transient phase of the learning algorithm
will last a long time and one may not be able to get adesirable accuracy before the samples are exhausted.
• Learning rate schedules: In practice, most RL softwaredevelopers use a learning rate schedule, i.e., a fixed  isused for a certain amount of time and then it is reduced,
and this is repeated a few times. The choice of when
the learning rate  should be reduced is determinedby extensive experimentation and is chosen carefullyfor each RL environment studied. Typically, these are
published by researchers on platforms such as github
and then used by others.

Adaptive Learning Rate Selection for Temporal Difference Learning

Our goal in this paper is to adaptively choose the learning
rate for TD learning with linear function approximation byobserving the evolution of the function parameters as thealgorithm progresses. For this purpose, we will leverage
the recent results on finite-time performance bounds forTD-learning in (Srikant & Ying, 2019).

convenient for our subsequent discussion.
θk+1 −θ∗ = θk −θ∗ + (A(Xk )(θk − θ∗ ) + b(Xk )) , (2)where A(XK ) is a matrix whose entries are functions of thestate Xk , b(Xk ) is a zero-mean random vector, and θ∗ is thecentering offset from 0, the equilibrium point of the ODEdθ= E(A(X∞ ))θ,dt

2. BackgroundWe consider a discounted cost MDP, and let {Xk } denotethe Markov chain associated with the MDP operating undera fixed policy. Here it is assumed that Xk takes values in a
finite state space. We let V (i) denote the value function instate i and thus, it satisfies the Bellman equationX
V (i) = c(i) + α
pij V (j),jwhere c is the instantaneous cost, α is the discount factor,
and pij is the probability of transitioning from state i to j.
The tabular version of the TD learning algorithm estimates
V from samples Xk as follows:
Vk+1 (Xk ) = Vk (Xk ) − (V (Xk ) − c(Xk ) − αV (Xk+1 )),where  is a fixed learning rate. Since the theory from which
we derive our adaptive learning rate rule later is based ona fixed learning rate, we have presented the TD learning
equation above in terms of a fixed learning rate, but otherlearning rate rules can be used as well. However, this versionof TD learning requires one to store the value function for
all states and when the state space is large, such a storage
requirement makes the algorithm infeasible to implement.
Instead, a common approach is to approximate the valuefunction V (i) by θT φ(i), i.e., V (i) ≈ θT φ(i), where φ(i)is a known feature vector associated with state i and θ is theunknown parameter to be estimated.
The TD learning algorithm associated with linear function
approximation is as follows:θk+1 = θk− θkT φ(Xk ) − c(Xk ) − αθkT φ(Xk+1 ) φ(Xk )(1)
Recently, a number of papers have studied the convergenceproperties of the above algorithms, under additional assumptions such as the i.i.d. samples assumption and the additionof a projection step (Lakshminarayanan & Szepesvari, 2018;
Bhandari et al., 2018). Some of these papers also allow for
averaging of the iterates.
The starting point for our work is the result in (Srikant& Ying, 2019) which studies the basic TD algorithm (1),with no significant additional assumptions, and provides
convergence rate bounds. We first note that, as in (Srikant& Ying, 2019), we can rewrite (1) in a form that is more

where X∞ denotes a random variable with a distribution
equal to the stationary distribution (which is assumed toexist) of the Markov chain X. In (Srikant & Ying, 2019), thelinear stochastic approximation algorithm (2) was studied
and the following result was established.
Theorem 1
E(kθk − θ∗ k2 ) ≤ K1 (1 − K2 )k + K3 ,
for all sufficiently small  and large k, where K1 , K2 andK3 are problem-dependent constants.


3. Adaptive Learning Rate Rule
Suppose that our goal is to choose the learning rate as a function of the time step in order to minimize the mean-squared
error for a given number of samples. In principle, one canassume time-varying learning rates, use the mean-squared
error expressions for time-varying learning rates in (Srikant& Ying, 2019) (which are generalizations of Theorem 1),
and try to optimize the learning rates to minimize the error
for the given number of samples. However, this optimization
problem is computationally intractable. We note that even if
we assume that we are only going to change the learning ratea finite number of times, the resulting optimization problemof finding the times at which such changes are performed
and finding the learning rate at these change points is anequally intractable optimization problem. Therefore, wehave to devise simpler adaptive learning rate rules.
To motivate our learning rate rule, we first consider a time
T such that error due to the transient and steady-state partsin Theorem 1 are equal, i.e.,
K1 (1 − K2 )T = K3 

(3)From this time onwards, running the TD algorithm any
further with  as the learning rate is not going to significantly
improve the mean-squared error. In particular, the meansquared error beyond this time is upper bounded by twice
the steady-state error K3 . Thus, at time T, it makes sense
to reset  as  ← /ξ, where ξ > 1 is a hyperparameter.
Roughly speaking, T is a time at which one is close tosteady-state for a given learning rate, and therefore, it is thetime to reduce the learning rate to get to a new ”steady-state”
with a smaller error.

Adaptive Learning Rate Selection for Temporal Difference Learning

The key difficulty with implementing the above idea is that itis difficult to determine T. If we were able to plot kθk − θ∗ k
as a function of k, then one can devise some algorithm
to determine whether this expression has reached close to
its steady-state. However, θ∗ is unknown and hence, it isdifficult to use this approach.
Our second key idea is to estimate whether the algorithm isclose to its steady-state by observing kθk − θ0 k where θ0 is
our initial guess for the unknown parameter vector and isthus known to us. Note that kθk − θ0 k is zero at k = 0 andwill increase to kθ∗ − θ0 k in steady-state in the absence ofany randomness, see Figure 1 for an illustration.

Algorithm 1 Adaptive Learning Rate Rule
Hyperparameters: α, σ, ξ,√NInitialize  = α, ψN = 2σ , θ0 , θini = θ0 .
for i = 1, 2, ... do
Do TD learning update.
N −1Compute ψN = Slope {k, kθi−k − θini k}k=0.
√
σ 
if |ψN | < N then = ξ .
θini = θi .
end ifend forwhen the algorithm is in the transient state, the difference
between kθk+m −θ0 k and kθk −θ0 k will be O(m) since θkin (2) changes by O() from one time slot to the next. Using
this fact, the slope of the best-fit line through N consecutive
points in the transient state can be shown to be O (), similar
to (5). Since we choose N ≥ √κ , the slope of the best-fit√ line in steady state, i.e., O N will be lower than the

Figure 1. The evolution of kθk − θ0 k.

To derive a test to estimate whether kθk − θ0 k has reachedsteady-state, we first note the following inequality for k ≥ T(i.e., after entering the steady-state time defined in (3)):∗∗

E[kθ0 − θ k] − E[kθk − θ k]
≤ E[kθk − θ0 k] ≤ E[kθk − θ∗ k] + E[kθ0 − θ∗ k]pp⇒ c − 2K3  ≤ E[kθk − θ0 k] ≤ c + 2K3 (4)where the first pair of inequalities follow from the triangle
inequality and the second pair of inequalities follow from
Theorem 1, Jensen’s inequality and letting c = E[kθ0 −θ∗ k].
Now, for k ≥ T , consider the following N points: {xi =i, yi = kθk+i − θ0 k}N
i=1 . Since these points are all obtained
after the steady-state is reached, if we draw the best-fit
line through these points, its slope should be small. Moreprecisely, let ψN denote the slope of the best-fit line passing
through these N points. Using (4) along with formulas
for the slope in linear regression, and after some algebraic
manipulations, one can show that:
√ 



1
(5)
|E[ψN ]| = O, Var(ψN ) = O
NN2Therefore, if N ≥ √κ , then the slope of the best-fit line√ connecting {xi , yi } will be O N with high probability(for a sufficiently large constant κ > 0). On the other hand,slope of the best-fit line in the transient phase, i.e., O ()(for a sufficiently large κ). We use this fact as a diagnostic
test to determine whether or not the algorithm has enteredsteady-state. If the diagnostic test returns true, we update
the learning rate (see Algorithm 1).

4. Experiments
4.1. Setup
We implemented our adaptive learning rate selection rule
on a variety of popular reinforcement learning domains
and compared its performance with that of the best fixedlearning rate and the best diminishing/back-off learning
rate schedule (as discussed in Section 1). We consider thefollowing reinforcement learning problems/domains1 :1. Mountain Car: In the basic mountain car problem,
an underpowered car is positioned in a valley between
two mountains on a one-dimensional track. The aimof the problem is to drive the car to the top of themountain on the right-hand side, but the engine power
available is insufficient to simply accelerate and power
through to the top. Therefore, a player has to build
up momentum by going back and forth between thetwo mountains until the car has sufficient momentum
to reach its goal. The state space, action space, cost
structure and initialization details for the mountain car
problem are as follows:• State Space: (Car Position, Car Velocity) ∈[−1.2, 0.6] × [−0.07, 0.07].
1
We used the OpenAI Gym implementation of these environments, available at https://gym.openai.com/.

Adaptive Learning Rate Selection for Temporal Difference Learning• Action Space: 0, 1 and 2 (denoting left, no andright acceleration respectively).
• Cost Structure: +1 cost incurred for every time
step the car has not achieved its goal. 0 cost incurred upon reaching the goal.
• Initialization/Starting State: The car’s position
is initialized to a random value in [−0.6, 0.4]. Its
velocity is initialized to 0.
2. Inverted Pendulum: In the classic inverted pendulum swing-up problem, a frictionless pendulum ishinged/pivoted at one end and the aim of the problem
is to keep the pendulum in an upright position (withrespect to the pivot) for as long as possible by applying
a torque at the pivot point (sometimes referred to as thejoint effort). The state space, action space, cost structure and initialization details for the inverted pendulum
problem are as follows:• State Space: (cos(θ), sin(θ), θ̇) ∈ [−1.0, 1.0] ×[−1.0, 1.0] × [−8.0, 8.0]. Here, θ ∈ [−π, π] denotes the angular position of the pendulum withrespect to the pivot.
• Action Space: Torque ∈ [−2.0, 2.0].
• Cost Structure: The equation associated with thecost function is the following:θ2 + 0.1θ̇ + 0.001 × torque2 .
• Initialization/Starting State: The pendulum’s
angular position is initialized to a random valuein [−π, π]. Its angular velocity is initialized to arandom value ∈ [−1, 1].
3. Frozen Lake: The frozen lake game is a single player
game in which the player has to navigate a 4 × 4 gridwith the goal of arriving at the finish point on the gridfrom the starting position without falling in any of thedeath zones (also known as holes). At each point on
the grid, the player has the option to move around toany of the neighboring points. If the player moves to ahole, the player is killed and re-spawned at the starting
point. The state space, action space, cost structure andinitialization details for the frozen lake game are as
follows:• State Space: A set with a cardinality of 16, i.e.,
the total number of points on the grid.
• Action Space: Up, Down, Left or Right. Notethat if the point on the grid is such that it does nothave a neighbor in a particular direction, moving
in that direction will keep the player at his/hercurrent position.
• Cost Structure: 0 cost associated with every time
step until the player reaches his/her goal. −1 cost
incurred upon reaching the goal.

• Initialization/Starting State: The player is always
initialized to state 0 which is the starting positionon the grid.
We evaluate the following policies using TD learning foreach aforementioned problem/domain:• Mountain Car - At each time step, choose a random
action ∈ {0, 2}, i.e., accelerate randomly to the left or
right.
• Inverted Pendulum - At each time step, choose a random action in the entire action space, i.e., apply arandom torque ∈ [−2.0, 2.0] at the pivot point.
• Frozen Lake - At each time step, pick a random actionin the entire action space, i.e., go in a random direction
from the current position.
Since the true value of θ∗ is not known in the problem
domains we consider, to quantify the performance of the TD
learning algorithm, we use the error metric known as thenorm of the expected TD update (NEU, see (Sutton et al.,2009) for more details). For linear function approximation,in the Mountain Car and the Inverted Pendulum problems,
we use a O(3) Fourier basis (see (Konidaris et al., 2011)
for more details) and for the Frozen Lake game, we use
one-hot encoding for the different states. Also, for all theexperiments, we use γ = 0.95 as the discount factor.
4.2. Hyperparameter Tuning
For each learning rate rule, we did the following tuning tochoose the best hyperparameters:• For finding the best fixed learning rate in each problem
domain, we did a grid search over a wide variety of
fixed learning rates and found the following to be thebest: Mountain Car - 0.0075, Inverted Pendulum 0.001, Frozen Lake - 0.01.
• For finding the best back-off strategy (k =max{min , kαβ }), we first fixed α and conducted a gridsearch to find the best β. We considered the following
values for β: (0.6, 0.7, 0.8, 0.9, 1.0). In all the problem domains, the best performance was obtained for
β = 0.6. We subsequently conducted a grid search forα over a wide variety of values and found the following
to be the best: Mountain Car - 0.5, Inverted Pendulum- 0.2, Frozen Lake - 1.
• For the proposed adaptive learning rate rule, we fixedξ = 1.2, N = 200 in all the domains since we didn’t
want the decay in the learning rate to be too aggressive
and the resource consumption for slope computation
to be high. We then fixed α and conducted a gridsearch over a wide variety of values to find the best
σ. Subsequently, we conducted a grid search over

Adaptive Learning Rate Selection for Temporal Difference Learning

α. Interestingly, the adaptive learning rate rule wasreasonably robust to the value of α used and hence
we use α = 0.05 in all the domains. Effectively, theonly hyperparameter that really required tuning wasσ. The following values for σ were found to be thebest: Mountain Car - σ = 0.0075, Inverted Pendulum- σ = 10, Frozen Lake - σ = 0.01.
Note that for each learning rate rule we ensure that thelearning rate never goes below min = 10−5 . This is done toensure that the TD learning algorithm does not stop learning
altogether.
4.3. Results
For each experiment, one run involved the following:
10, 000 episodes with the number of iterations in each
episode varying from 50 − 200 depending on the problem/domain. After every 1, 000 episodes, training/learning
was paused and the NEU was computed, averaged over
1, 000 test episodes. Depending on the problem/domain,
50 − 250 of such runs were conducted and the results averaged over these runs. Note that the learning rate for each
adaptive strategy was adapted at the episodic level due tothe episodic nature of the problems. The results are reported
in Figures 2 - 4. We report the performance of the different
rules from the 5, 000th episode onward since the large error
values in the initial episodes make it hard to visually interpret the graph for the eventual performance of the different
rules.

Figure 3. Performance of different learning rate rules in the Inverted Pendulum problem.

Figure 4. Performance of different learning rate rules in the Frozen
Lake problem.

Remark 1 We also implemented a procedure similar to
SGD1/2 in (Chee & Toulis, 2018), which was proposed
recently and has a similar motivation as our idea but a different diagnostic test. We do not report the results of thatprocedure here as in all the domains that we considered,their diagnostic test was too conservative and failed to detect the steady state in a reasonable amount of time resulting
in a much worse performance as compared to our method.
Figure 2. Performance of different learning rate rules in the Mountain Car problem.

5. Conclusion

From the figures, we can observe that our rule performs
much better than the best fixed learning rate as well as thebest back-off learning rate strategy. Note that since we tuned
each strategy to have the lowest error at the end of 10, 000
episodes, the relative difference between the performanceof our strategy and others is significant.

In this paper, we presented an adaptive learning rate selection rule for TD learning with linear function approximation. The rule comprises a diagnostic test to determine
whether the algorithm has entered steady state and adapts
the learning rate accordingly. We implemented the ruleon various popular reinforcement learning applications anddemonstrated its significant utility in practice.

Adaptive Learning Rate Selection for Temporal Difference Learning

References
Bhandari, J., Russo, D., and Singal, R. A finite time analysis of temporal difference learning with linear function
approximation. In Conference On Learning Theory, pp.
1691–1692, 2018.
Chee, J. and Toulis, P. Convergence diagnostics for stochastic gradient descent with constant learning rate. In International Conference on Artificial Intelligence and Statistics,
pp. 1476–1485, 2018.
George, A. P. and Powell, W. B. Adaptive stepsizes forrecursive estimation with applications in approximate
dynamic programming. Machine learning, 65(1):167–
198, 2006.
Konidaris, G., Osentoski, S., and Thomas, P. Value function approximation in reinforcement learning using thefourier basis. In Twenty-fifth AAAI conference on artificial
intelligence, 2011.
Lakshminarayanan, C. and Szepesvari, C. Linear stochastic approximation: How far does constant step-size anditerate averaging go? In International Conference on Artificial Intelligence and Statistics, pp. 1347–1355, 2018.
Srikant, R. and Ying, L. Finite-time error bounds for linear stochastic approximation and TD learning. Conference on Learning Theory (COLT), 2019. ArXiv preprint
arXiv:1902.00923,.
Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. Fast gradientdescent methods for temporal-difference learning withlinear function approximation. In Proceedings of the 26th
Annual International Conference on Machine Learning,
pp. 993–1000. ACM, 2009.