next up previous contents
Next: 9.6 Trajectory Sampling Up: 9. Planning and Learning Previous: 9.4 Prioritized Sweeping   Contents

9.5 Full vs. Sample Backups

The examples in the previous sections give some idea of the range of possibilities for combining methods of learning and planning. In the rest of this chapter, we analyze some of the component ideas involved, starting with the relative advantages of full and sample backups.

Figure 9.12: The one-step backups.

Much of this book has been about different kinds of backups, and we have considered a great many varieties. Focusing for the moment on one-step backups, they vary primarily along three binary dimensions. The first two dimensions are whether they back up state values or action values and whether they estimate the value for the optimal policy or for an arbitrary given policy. These two dimensions give rise to four classes of backups for approximating the four value functions, , , , and . The other binary dimension is whether the backups are full backups, considering all possible events that might happen, or sample backups, considering a single sample of what might happen. These three binary dimensions give rise to eight cases, seven of which correspond to specific algorithms, as shown in Figure  9.12. (The eighth case does not seem to correspond to any useful backup.) Any of these one-step backups can be used in planning methods. The Dyna-Q agents discussed earlier use sample backups, but they could just as well use full backups, or either full or sample backups. The Dyna-AC system uses sample backups together with a learning policy structure. For stochastic problems, prioritized sweeping is always done using one of the full backups.

When we introduced one-step sample backups in Chapter 6, we presented them as substitutes for full backups. In the absence of a distribution model, full backups are not possible, but sample backups can be done using sample transitions from the environment or a sample model. Implicit in that point of view is that full backups, if possible, are preferable to sample backups. But are they? Full backups certainly yield a better estimate because they are uncorrupted by sampling error, but they also require more computation, and computation is often the limiting resource in planning. To properly assess the relative merits of full and sample backups for planning we must control for their different computational requirements.

For concreteness, consider the full and sample backups for approximating , and the special case of discrete states and actions, a table-lookup representation of the approximate value function, , and a model in the form of estimated state-transition probabilities, , and expected rewards, . The full backup for a state-action pair, , is:


The corresponding sample backup for , given a sample next state, , is the Q-learning-like update:


where is the usual positive step-size parameter and the model's expected value of the reward, is used in place of the sample reward that is used in applying Q-learning without a model.

The difference between these full and sample backups is significant to the extent that the environment is stochastic, specifically, to the extent that, given a state and action, many possible next states may occur with various probabilities. If only one next state is possible, then the full and sample backups given above are identical (taking ). If there are many possible next states, then there may be significant differences. In favor of the full backup is that it is an exact computation, resulting in a new whose correctness is limited only by the correctness of the at successor states. The sample backup is in addition affected by sampling error. On the other hand, the sample backup is cheaper computationally because it considers only one next state, not all possible next states. In practice, the computation required by backup operations is usually dominated by the number of state-action pairs at which is evaluated. For a particular starting pair, , let be the branching factor, the number of possible next states, , for which . Then a full backup of this pair requires roughly times as much computation as a sample backup.

If there is enough time to complete a full backup, then the resulting estimate is generally better than that of sample backups because of the absence of sampling error. But if there is insufficient time to complete a full backup, then sample backups are always preferable because they at least make some improvement in the value estimate with fewer than backups. In a large problem with many state-action pairs, we are often in the latter situation. With so many state-action pairs, full backups of all of them would take a very long time. Before that we may be much better off with a few sample backups at many state-action pairs than with full backups at a few pairs. Given a unit of computational effort, is it better devoted to a few full backups or to -times as many sample backups?

Figure  9.13 shows the results of an analysis that suggests an answer to this question. It shows the estimation error as a function of computation time for full and sample backups for a variety of branching factors, . The case considered is that in which all successor states are equally likely and in which the error in the initial estimate is 1. The values at the next states are assumed correct, so the full backup reduces the error to zero upon its completion. In this case, sample backups reduce the error according to where is the number of sample backups that have been performed (assuming sample averages, i.e., ). The key observation is that for moderately large the error falls dramatically with a tiny fraction of backups. For these cases, many state-action pairs could have their values improved dramatically, to within a few percent of the effect of a full backup, in the same time that one state-action pair could be backed up fully.

Figure 9.13: Comparison of efficiency of full and sample backups.

The advantage of sample backups shown in Figure  9.13 is probably an underestimate of the real effect. In a real problem, the values of the successor states would themselves be estimates updated by backups. By causingestimates to be more accurate sooner, sample backups will have a second advantage in that the values backed up from the successor states will be more accurate. These results suggest that sample backups are likely to be superior to full backups on problems with large stochastic branching factors and too many states to be solved exactly.

Exercise 9.5   The analysis above assumed that all of the possible next states were equally likely to occur. Suppose instead that the distribution was highly skewed, that some of the states were much more likely to occur than most. Would this strengthen or weaken the case for sample backups over full backups? Support your answer.

next up previous contents
Next: 9.6 Trajectory Sampling Up: 9. Planning and Learning Previous: 9.4 Prioritized Sweeping   Contents
Mark Lee 2005-01-04