Sequential Decision-Making
Bandit problems have a history spanning statistics, engineering, and psychology.
The First Choice Is Not the Whole Problem
Imagine choosing among several options when you do not yet know which one produces the best result. The important feature is not only the first choice. After making that choice, you observe an outcome and gain information. That information can influence what you choose next. This pattern is studied through bandit problems, which have a history spanning statistics, engineering, and psychology.
In sequential decision-making, an action has two consequences: it produces an immediate result and it changes what is known before the next decision.
Following Information Through Decisions
A Two-Step Illustrative Bandit Choice
A decision maker must choose between Option A and Option B over two decision steps. The outcomes are initially unknown.
Step 1: choose: The decision maker selects Option A. This is an action taken while information about the options is incomplete.
Step 1: observe: Option A produces an observed outcome. The observation provides information about Option A, although this example does not specify a formal rule for how much confidence to place in it.
Step 2: use information: Before the second choice, the decision maker can use the information from Option A. The second decision is therefore made with a different information state from the first.
The second choice is part of a sequence because it can depend on what happened during the first choice.
The word sequential is essential. Decisions are made in an order, and later decisions can depend on information obtained earlier. The decision maker is not repeatedly facing the same uninformed choice; the information state can change as observations accumulate.
Exploration and Exploitation
Exploration seeks information. It means selecting an option partly because its outcome may teach the decision maker something. Exploitation uses current knowledge. It means selecting an option based on what is currently believed or known about its results. In a sequential problem, these goals interact because an exploratory action can provide information for later decisions, while an exploitative action uses the information already available.
| Decision purpose | Main question | Related engineering language |
|---|---|---|
| Exploration | What can this option teach me? | Identification |
| Exploitation | How can I use what I currently know? | Control |
Designing the Next Experiment
The statistical perspective treats bandit problems as sequential design of experiments. At each point, an experimenter selects an option, observes what happens, uses the resulting information, and faces the design of a later decision. The next experiment is therefore connected to earlier observations rather than being designed independently.
This perspective also gives the topic a historical place in statistics. The source describes Thompson as introducing this perspective in 1933 and 1934, Robbins contributing to it in 1952, Bellman studying the area in 1956, and Berry and Fristedt providing an extensive statistical treatment in 1985.
One Pattern Across Four Fields
Bandit problems are not limited to one discipline. Statistics emphasizes sequential design of experiments. Engineering emphasizes the simultaneous problem of identification and control. Psychology has used bandit problems in statistical learning theory. In heuristic search literature, the term greedy is often used. These perspectives are connected because they all emphasize acting while still learning, even though each field highlights a different part of the pattern.
The terminology changes across fields, but the shared decision pattern remains: choose an action, learn from its outcome, and use that learning while choosing again.
Common Reasoning Mistakes
Treating each decision as isolated.
Sequential decisions are ordered, and later decisions can depend on information obtained earlier.
Fix:
Track how each observed outcome changes the information available for the next choice.Assuming exploration and exploitation are identical.
Exploration seeks information, while exploitation uses current knowledge.
Fix:
Ask whether the purpose of the choice is identification through information or control through current knowledge.Assigning every disciplinary term a completely separate meaning.
The source presents them as different perspectives on acting while still learning.
Fix:
Connect each term to the aspect of the shared decision pattern that its field emphasizes.
Check Your Understanding
A decision maker selects an option, observes its result, and then uses that result when choosing again. Explain why this is a sequential design of experiments rather than two isolated choices. Then identify which part represents exploration and which part represents exploitation if the decision maker chooses one option to learn about it and later chooses an option using current knowledge.
Hints
- Focus on what changes between the first and second decisions.
- Exploration is connected to seeking information.
- Exploitation is connected to using current knowledge.
A Complete Explanation
Explain the relationship among an observed outcome, a later decision, and the exploration-exploitation distinction.
Identify the sequence: The decisions occur in an order, so the later choice follows the earlier observation.
Identify the information change: The observed result adds information that was unavailable before the first choice.
Identify the purpose: Choosing to gain information is exploration; choosing by relying on current knowledge is exploitation.
Connect the perspectives: Statistics describes the pattern as sequential design of experiments, while engineering describes the tension between learning and acting as identification and control.
The defining feature is not merely repeated choice. It is the interaction between action, information gained from the outcome, and the design of the next action.
Key Takeaways
- Bandit problems are studied in statistics as sequential design of experiments because later decisions can depend on information obtained from earlier decisions.
- Exploration seeks information, while exploitation uses current knowledge.
- Engineering frames the related tension as simultaneous identification and control, also called dual control.
- Statistics, engineering, psychology, and heuristic search use different terms and emphases for a shared pattern: acting while still learning.
- A sequential decision should be understood as a loop in which a choice produces an outcome, the outcome changes available information, and that information influences the next choice.
Key Takeaways
- Sequential decision-making links each choice to information gained from earlier outcomes.
- Statistics treats bandit problems as sequential design of experiments.
- Exploration seeks information, whereas exploitation uses current knowledge.
- Engineering calls the combined learning-and-acting tension identification and control, or dual control.
- Several disciplines study the same difficult pattern from different perspectives.