Eligibility traces
Eligibility traces unify and generalize TD and Monte Carlo methods. When TD methods are augmented with eligibility traces, they produce a family of methods spanning a spectrum that has Monte Carlo methods at one end () and one-step TD methods at the other (). In between are intermediate methods that are often better than either extreme method. Eligibility traces also provide a way of implementing Monte Carlo methods online and on continuing problems without episodes.
Eligibility traces achieve significant computational advantages with the mechanism that is a short-term memory vector, the eligibility trace , that parallels the long-term weight vector . The rough idea is that when a component of participates in producing an estimated value, then the corresponding component of is bumped up and then begins to fade away. Learning will then occur in that component of if a nonzero TD error occurs before the trace falls back to zero. The trace-decay parameter determines the rate at which the trace falls.
The primary computational advantage of eligibility traces over n-step methods is that only a single trace vector is required rather than a store of the last n feature vectors. Learning also occurs continually and uniformly in time rather than being delayed and then catching up at the end of the episode. In addition learning can occur and affect behavior immediately after a state is encountered rather than being delayed n steps.
The -return
The n-step return is defined as the sum of the first n rewards plus the estimated value of the state reached in n steps, each appropriately discounted
The algorithm can be understood as one particular way of averaging n-step updates. The resulting update is toward a return, called the -return, defined in its state-based form by
In the off-line -return algorithm, it makes no changes to the weight vector during the episode. At the end of the episode, a whole sequence of off-line updates are made according to the usual semi-gradient rule, using the -return as the target
In the forward view of a learning algorithm, for each state visited, we look forward in time to all the future rewards and decide how best to combine them.
improves over the off-line -return algorithm in three ways. First it updates the weight vector on every step of an episode rather than only at the end, and thus its estimates may be better sooner. Second, its computations are equally distributed in time rather that all at the end of the episode. And third, it can be applied to continuing problems rather than just episodic problems.
With function approximation, the eligibility trace is a vector with the same number of components as the weight vector . Whereas the weight vector is a long-term memory, accumulating over the lifetime of the system, the eligibility trace is a short-term memory, typically lasting less time than the length of an episode. Eligibility traces assist in the learning process; their only consequence is that they affect the weight vector, and then the weight vector determines the estimated value.
In , the eligibility trace vector is initialized to zero at the beginning of the episode, is incremented on each time step by the value gradient, and then fades away by :
where is the discount rate and is the parameter introduced in -return. The eligibility trace keeps track of which components of the weight vector have contributed, positively or negatively, to recent state valuations, where “recent” is defined in terms . The trace is said to indicate the eligibility of each component of the weight vector for undergoing learning changes should a reinforcing event occur. The reinforcing events we are concerned with are the moment-by-moment one-step TD errors. The TD error for state-value prediction is
In , the weight vector is updated on each step proportional to the scalar TD error and the vector eligibility trace:
The procedure for Semi-gradient is
is oriented backward in time. At each moment we look at the current TD error and assign it backward to each prior state according to how much that state contributed to the current eligibility trace at that time.
True online
The n-step truncated -return is defined by
The truncated is defined by
Choosing the truncation parameter in Truncated involves a tradeoff. should be large so that the method closely approximates the off-line -return algorithm, but it should also be small so that the updates can be made sooner and can influence behavior sooner. To get the best of both, on each time step as you gather a new increment of data, you go back and redo all the updates since the beginning of the current episode. The new updates will be better than the ones you previously made because now they can take into account the time step’s new data. That is, the updates are always towards an n-step truncated -return target, but they always use the latest horizon.
This algorithm involves multiple passes over the episode, one at each horizon, each generating a different sequence of weight vectors. The general form for the update is
This update, together with defines the online -return algorithm. The online -return algorithm is fully online, determining a new weight vector at each step during an episode, using only information available at time . It’s main drawback is that it is computationally complex, passing over the entire episode so far on every step.
The on-line -return algorithm just presented is currently the best performing temporal-difference algorithm. It is an ideal which online only approximates. However, the on-line -return algorithm is very complex.
The true online algorithm is
where we use the shorthand , is defined as in , and is defined by
This algorithm has been proven to produce exactly the same sequence of weight vectors, , as the on-line -return algorithm.
The eligibility trace used in true online is called a dutch trace to distinguish it from the trace used in , which is called an accumulating trace. Earlier work often used a third kind of trace called the replacing trace which is deprecated now.
Very few changes are required in order to extend eligibility traces to action-value methods. To learn approximate action values, , rather than approximate state values, , we need to use the action-value form of the n-step return
for all and such that and . The action-value form of the off-line -return algorithm simply uses rather than :
where .
The temporal-difference method for action values, known as , approximates this forward view. It has the same update rule as given for
except using the action-value form of the TD error
and the action-value form of the eligibility trace
The procedure for with binary features and linear function approximation is
The procedure for true online is
Off-policy eligibility traces
Unlike in the case of n-step methods, for full non-truncated -returns one does not have a practical option in which the importance sampling is done outside the target return. Instead, we move directly to the bootstrapping generalization of per-reward importance sampling. In the state case, our final definition of the -return generalizes to
where is the usual single-step importance sampling ratio. The truncated version of this return can be approximated simply in terms of sums of the state-based TD error,
as
with the approximation becoming exact if the approximate value function does not change.
The above form of the -return is convenient to use in a forward-view update
which looks like an eligibility-based TD update – the product is like an eligibility trace and it is multiplied by TD errors. But this is just one time step of a forward view. The relationship that we are looking for is that the forward-view update, summed over time, is approximately equal to a backward-view update, summed over time. The sum of he forward-view update over time is
which would be in the form of the sum of a backward-view TD update if the entire expression from the second sum left could be written and updated incrementally as an eligibility trace, which we now show can be done. That is, we show that if this expression was the trace at time , then we could update it from its value at time by:
which, changing the index from to , is the general accumulating trace update for state values
A very similar series of steps can be followed to derive the off-policy eligibility traces for action-value methods and corresponding general algorithms.
When to use eligibility traces
Methods using eligibility traces require more computation than one-step methods, but in return they offer significantly faster learning, particularly when rewards are delayed by many steps. Thus it often makes sense to use eligibility traces when data are scare and cannot be repeatedly processed, as is often the case in on-line applications. On the other hand, in off-line applications in which data can be generated cheaply, perhaps from an inexpensive simulation, then it often does not pay to use eligibility traces. In these cases the objective is not to get more out of a limited amount of data, but simply to process as much data as possible as quickly as possible. In these cases the speedup per datum due to traces is typically not worth their computational cost, and one-step methods are favoured.
Policy gradient methods
We consider methods that learn a parameterized policy that can select actions without consulting a value function. A value function may still be used to learn the policy parameter, but is not required for action selection. We use the notation for the policy’s parameter vector. Thus we write for the probability that action is taken given that the environment is in state at time with parameter . If a method uses a learned value function as well, then the value function’s weight vector is denoted as usual, as in .
Consider methods for learning the policy parameter based on the gradient of some performance measure with respect to the policy parameter. These methods seek to maximize performance, so their udpates approximate gradient ascent in
where is a stochastic estimate whose expectation approximates the gradient of the performance measure with respect to its argument . All methods that follow this general schema we call policy gradient methods, whether or not they also learn an approximate value function. Methods that learn approximations to both policy and value functions are often called actor–critic methods, where ‘actor’ is a reference to the learned policy, and ‘critic’ refers to the learned value function, usually a state-value function.
Policy approximation
In policy gradient methods, the policy can be parameterized in any way, as long as is differentiable with respect to its parameters, that is, as long as exists and is always finite. In practice, to ensure exploration we generally require that the policy never becomes deterministic (i.e., that ) for all .
If the action space is discrete and not too large, then a natural kind of parameterization is to form parameterized numerical preferences for each state–action pair. The actions with the highest preferences in each state are given the highest probabilities of being selected, for example, according to an exponential softmax distribution:
The preferences themselves can be parameterized arbitrarily. For example, they might be computed by a deep neural network, where is the vector of all the connection weights of the network.
An immediate advantage of selecting actions according to the softmax in action preferences is that the approximate policy can approach a deterministic policy, whereas with -greedy action selection over action values there is always an probability of selecting a random action. Of course, one could select according to a softmax over action values, but this alone would not allow the policy to approach a deterministic policy. Instead, the action-value estimates would converge to their corresponding true values, which would differ by a finite amount, translating to specific probabilities other than 0 and 1. If the softmax included a temperature parameter, then the temperature could be reduced over time to approach determinism, but in practice it would be difficult to choose the reduction schedule, or even the initial temperature, without more prior knowledge of the true action values than we would like to assume. Action preferences are different because they do not approach specific values; instead they are driven to produce the optimal stochastic policy. If the optimal policy is deterministic, then the preferences of the optimal actions will be driven infinitely higher than all suboptimal actions (if permited by the parameterization).
In problems with significant function approximation, the best approximate policy may be stochastic. Action-value methods have no natural way of finding stochastic optimal policies, whereas policy approximating methods can. This is a second significant advantage of policy-based methods.
Perhaps the simplest advantage that policy parameterization may have over action-value parameterization is that the policy may be a simpler function to approximate. Problems vary in the complexity of their policies and action-value functions. For some, the action-value function is simpler and thus easier to approximate. For others, the policy is simpler.
Finally, we note that the choice of policy parameterization is sometimes a good way of injecting prior knowledge about the desired form of the policy into the reinforcement learning system. This is often the most important reason for using a policy-based learning method.
The policy gradient theorem
In addition to the practical advantages of policy parameterization over -greedy action selection, there is also an important theoretical advantage. With continuous policy parameterization the action probabilities change smoothly as a function of the learned parameter, whereas in -greedy selection the action probabilities may change dramatically for an arbitrarily small change in the estimated action values, if that change results in a different action having the maximal value. Largely because of this stronger convergence guarantees are available for policy-gradient methods than for action-value methods. In particular, it is the continuity of the policy dependence on the parameters that enables policy-gradient methods to approximate gradient ascent.
The episodic and continuing cases define the performance measure, , differently and thus have to be treated separately to some extent. In the episodic case we define performance as
where is the true value function for , the policy determined by .
With function approximation, it may seem challenging to change the policy parameter in a way that ensures improvement. The problem is that performance depends on both the action selections and the distribution of states in which those selections are made, and that both of these are affected by the policy parameter. Given a state, the effect of the policy parameter on the actions, and thus on reward, can be computed in a relatively straightforward way from knowledge of the parameterization. But the effect of the policy on the state distribution is a function of the environment and is typically unknown.
The policy gradient theorem provides us an analytic expression for the gradient of performance with respect to the policy parameter that does not involve the derivative of the state distribution. The policy gradient theorem establishes that
where the gradients are column vectors of partial derivatives with respect to the components of , and denotes the policy corresponding to parameter vector . In the episodic case, the constant of proportionality is the average length of an episode, and in the continuing case it is 1, so that the relationship is actually an equality. The distribution here is the on-policy distribution under .
REINFORCE: Monte Carlo policy gradient
Its update has an intuitive appeal. Each increment is proportional to the product of a return and a vector, the gradient of the probability of taking the action actually taken divided by the probability of taking that action. The vector is the direction in parameter space that most increases the probability of repeating the action on future visits to state . The update increases the parameter vector in this direction proportional to the return, and inversely proportional to the action probability. The former makes sense because it causes the parameter to move most in the directions that favor actions that yield the highest return. The latter makes sense because otherwise actions that are selected frequently are at an advantage (the updates will be more often in their direction) and might win out even if they do not yield the highest return.
The vector in the REINFORCE update is the only place the policy parameterization appears in the algorithm. This vector has been given several names and notations in the literature; we will refer to it simply as the eligibility vector.
REINFORCE with baseline
The policy gradient theorem can be generalized to include a comparison of the action value to an arbitrary baseline :
The baseline can be any function, even a random variable, as long as it does not vary with . The policy gradient theorem with baseline can be used to derive an update rule using similar steps. The update rule that we end up with is a new version of REINFORCE that includes a general baseline:
For MDPs the baseline should vary with state. In some states all actions have high values and we need a high baseline to differentiate the higher valued actions from the less highly valued ones; in other states all actions will have low values and a low baseline is appropriate.
One natural choice for the baseline is an estimate of the state value, , where is a weight vector learned by one of the methods presented in previous chapters. Because REINFORCE is a Monte Carlo method for learning the policy parameter, , it seems natural to also use a Monte Carlo method to learn the state-value weights, .
Actor-Critic method
Although the REINFORCE-with-baseline method learns both a policy and a state-value function, we do not consider it to be an actor–critic method because its state-value function is used only as a baseline, not as a critic. That is, it is not used for bootstrapping (updating the value estimate for a state from the estimated values of subsequent states), but only as a baseline for the state whose estimate is being updated. This is a useful distinction, for only through bootstrapping do we introduce bias and an asymptotic dependence on the quality of the function approximation. The bias introduced through bootstrapping and reliance on the state representation is often beneficial because it reduces variance and accelerates learning. REINFORCE with baseline is unbiased and will converge asymptotically to a local minimum, but like all Monte Carlo methods it tends to learn slowly (produce estimates of high variance) and to be inconvenient to implement online or for continuing problems. With temporal-difference methods we can eliminate these inconveniences, and through multi-step methods we can flexibly choose the degree of bootstrapping. In order to gain these advantages in the case of policy gradient methods we use actor–critic methods with a bootstrapping critic.
The procedure of one-step actor-critic is
The generalizations to the forward view of multi-step methods and then to a -return algorithm are straightforward. The one-step return is merely replaced by and respectively. The backward views are also straightforward, using separate eligibility traces for the actor and critic.
Policy gradient for continuing problems
For continuing problems without episode boundaries we need to define performance in terms of the average rate of reward per time step:
where is the steady-state distribution under , , which is assumed to exist and to be independent of (an ergodicity assumption). This is the special distribution under which, if you select actions according to , you remain in the same distribution:
We also define values, and , with respect to the differential return:
With these alternate definitions, the policy gradient theorem as given for the episodic case remains true for the continuing case. The forward and backward view equations also remain the same.
Policy parameterization for continuous actions
Policy-based methods offer practical ways of dealing with large actions spaces, even continuous spaces with an infinite number of actions. Instead of computing learned probabilities for each of the many actions, we instead learn statistics of the probability distribution. For example, the action set might be the real numbers, with actions chosen from a normal distribution.
The probability density function for the normal distribution is conventionally written
where and are the mean and standard deviation of the normal distribution. The value is the density of the probability at , not the probability.
To produce a policy parameterization, the policy can be defined as the normal probability density over a real-valued scalar action, with mean and standard deviation given by parametric function approximators that depend on the state. That is,
where and are two parameterized function approximators.
To complete the example we need only give a form for these approximators. For this we divide the policy’s parameter vector into two parts, , one part to be used for the approximation of the mean and one part for the approximation of the standard deviation. The mean can be approximated as a linear function. The standard deviation must always be positive and is better approximated as the exponential of a linear function. Thus
where is a state feature vector.
