So far in this chapter we have considered only nonassociative tasks, in which there is no need to associate different actions with different situations. In these tasks the learner either tries to find a single best action when the task is stationary, or tries to track the best action as it changes over time when the task is nonstationary. However, in a general reinforcement learning task there is more than one situation, and the goal is to learn a policy: a mapping from situations to the actions that are best in those situations. To set the stage for the full problem, we briefly discuss the simplest way in which nonassociative tasks extend to the associative setting.
As an example, suppose there are several different 
-armed bandit tasks, and that on
each play you confront one of these chosen at random. Thus, the bandit task changes
randomly from play to play. This would appear to you as a single, nonstationary
-armed bandit task whose true action values change randomly from play to play.
You could try using one of the methods described in this chapter that can handle
nonstationarity, but unless the true action values change slowly, these methods will
not work very well. Now suppose, however, that when a bandit task is selected for you,
you are given some distinctive clue about its identity (but not its action values).
Maybe you are facing an actual slot machine that changes the color of its display as
it changes its action values. Now you can learn a policy associating each task,
signaled by the color you see, with the best action to take when facing that
task--for instance, if red, play arm 1; if green, play arm 2. With the right
policy you can usually do much better than you could in the absence of any
information distinguishing one bandit task from another.
This is an example of an associative search task, so called because it involves
both trial-and-error learning in the form of search for the best actions and
association of these actions with the situations in which they are best.
Associative search tasks are intermediate between the -armed bandit problem and
the full reinforcement learning problem. They are like the full reinforcement
learning problem in that they involve learning a policy, but like our version
of the
-armed bandit problem in that each action affects only the immediate reward. If
actions are allowed to affect the next situation as well as the reward, then
we have the full reinforcement learning problem. We present this problem in the next
chapter and consider its ramifications throughout the rest of the book.
Exercise 2.16 Suppose you face a binary bandit task whose true action values change randomly from play to play. Specifically, suppose that for any play the true values of actions
and 
are respectively 0.1 and 0.2 with probability 0.5 (case A), and 0.9 and 0.8 with
probability 0.5 (case B). If you are not able to tell which case you face at any play,
what is the best expectation of success you can achieve and how should you behave to
achieve it? Now suppose that on each play you are told if you are facing case A or
case B (although you still don't know the true action values). This is an associative
search task. What is the best expectation of success you can achieve in this task,
and how should you behave to achieve it?