Function Approximation in Reinforcement Learning
On the 10-armed testbed, UCB generally performs better than epsilon-greedy action selection.
From Bandit Choices to Generalization
The 10-armed testbed shows that UCB generally performs better than epsilon-greedy action selection. UCB still explores: it investigates actions whose values are uncertain rather than eliminating exploration. However, this result belongs to a compact bandit setting. When reward distributions change over time or the state space becomes large, extending UCB becomes much more difficult. Function approximation addresses a related large-scale problem by helping reinforcement-learning systems generalize from available examples instead of treating every possible situation as completely separate.
The central transition is from selecting among a manageable set of actions to representing useful information across a potentially large state space.
UCB's Startup Choices
UCB has a special startup period. During the first k steps, it selects randomly among actions that have not yet been tried. These actions do not yet have reward experience available for comparison, so the startup behavior ensures that each action gets investigated. After this initial period, UCB can use the information collected about the actions and continue balancing estimated value with uncertainty.
A startup with three actions
Imagine a bandit with three actions and no previous trials. Describe the purpose of the first three UCB choices.
Beginning: All three actions are untried, so UCB has no collected experience with which to compare them.
Startup selection: During the startup period, UCB selects randomly among actions that have not yet been tried.
Coverage: After the initial three steps, each action has been tried, giving UCB experience from which to continue its selection process.
The startup period is not ordinary exploitation. It is an initial investigation that makes every action available for later comparison.
Why UCB Wins in the Testbed
On the 10-armed testbed, UCB generally achieves higher reward than epsilon-greedy action selection. The comparison is about how effectively the selection rule handles exploration and action choice. Epsilon-greedy explores by choosing actions outside its current preferred choice according to its exploration rule. UCB also explores, but its startup and uncertainty-directed behavior allow it to investigate actions whose value is not yet well established. The testbed therefore favors UCB in general, although the result is not a guarantee that UCB transfers easily to every reinforcement-learning problem.
When UCB's Evidence Ages
UCB is easiest to interpret when the underlying action-reward behavior does not require continual adaptation to a changing probability distribution. In a nonstationary problem, the underlying probability distribution changes over time. Evidence collected earlier may then become less useful for judging what an action is like now. Historical estimates and confidence information can no longer describe the current situation as reliably as they did when the evidence was collected.
The problem is not simply that UCB has too little data. In a changing environment, older data may describe an earlier distribution rather than the current one.
Why Large State Spaces Matter
A bandit presents a compact decision problem, but general reinforcement learning can involve a large state space. Extending UCB from bandits to these settings is difficult, especially when function approximation is needed. The source identifies no currently known practical way to use the idea of UCB action selection in these advanced settings. This limitation motivates a separate question: how can a learner represent useful value information when it has examples but not a complete description for every possible state?
What Function Approximation Builds
Function approximation uses examples from a desired function to construct a broader representation that can generalize beyond the examples. In reinforcement learning, the desired function can be a value function. The learner may have examples of that function without having a complete description of the function itself.
Three parts must be kept separate. The desired function is the function the learner would like to represent. The examples are the evidence available to the learner. The approximation is the generalized representation constructed from those examples. The purpose is not merely to store the examples; it is to use them to represent the function more broadly.
Keeping the three parts distinct
Suppose reinforcement learning provides several examples related to a value function. Identify the desired function, the examples, and the approximation.
Desired function: This is the value function the learner wants to represent, even though it does not have a complete description of it.
Examples: These are the available pieces of evidence about the desired function.
Approximation: This is the broader representation constructed from the available examples.
Purpose: The approximation supports generalization rather than merely memorizing the examples.
The desired function is the target, examples are the evidence, and the approximation is the learned representation built from that evidence.
Function Approximation as Supervised Learning
Function approximation is an instance of supervised learning. Supervised learning is also studied in artificial neural networks, pattern recognition, and statistical curve fitting. This connection matters because reinforcement learning does not need an entirely new approach to generalization. Methods from these fields can take the role of a function approximator within reinforcement-learning algorithms.
The combination has a clear division of roles. Reinforcement learning supplies the learning problem and the information produced through interaction. A generalization method supplies a way to construct a broader representation from available examples. In practice, these methods are not equally convenient: some fit more easily into reinforcement-learning algorithms than others.
When analyzing a function-approximation method, ask two separate questions: what examples does reinforcement learning provide, and how does the chosen supervised-learning method generalize from those examples? Keeping these roles separate prevents the approximation from being confused with the desired function.
Common Conceptual Mistakes
Treating UCB's better testbed performance as a universal guarantee.
The testbed is a compact bandit comparison, while large state spaces and function approximation make UCB difficult to extend in general.
Fix:
Interpret the result as a setting-specific comparison: UCB generally performs better than epsilon-greedy on the testbed, but transfer is not guaranteed.Saying that UCB does not explore.
UCB investigates actions whose values are uncertain and randomly selects among untried actions during its first k steps.
Fix:
Describe UCB as an exploration method whose uncertainty-directed choices can perform better in the testbed.Confusing old evidence with current evidence in a nonstationary problem.
A changing probability distribution can make earlier evidence less useful over time.
Fix:
Check whether the underlying action-reward distribution is changing before treating historical estimates as reliable.Calling the available examples the function approximation.
Examples are evidence; the approximation is the broader representation built from that evidence.
Fix:
Name the desired function, examples, and approximation as three distinct parts.Assuming reinforcement learning must invent all generalization methods itself.
Function approximation is an instance of supervised learning, and methods from related fields can serve as approximators.
Fix:
Explain how reinforcement-learning methods can be combined with existing generalization methods, while recognizing that some methods fit more easily than others.
Check Your Understanding
Explain, in your own words, why UCB generally performs better than epsilon-greedy on the 10-armed testbed. Then describe what happens during UCB's first k steps, identify one reason nonstationarity is difficult for UCB, and distinguish the desired function, examples, and approximation in a reinforcement-learning function-approximation problem.
Hints
- Mention UCB's treatment of uncertain or untried actions.
- Remember that changing probability distributions can reduce the usefulness of historical evidence.
- Use the three-part distinction: target, evidence, and broader representation.
Key Takeaways
- UCB generally performs better than epsilon-greedy action selection on the 10-armed testbed, while still preserving exploration.
- During its first k steps, UCB selects randomly among actions that have not yet been tried.
- Changing probability distributions make historical estimates and confidence information less reliable over time.
- Large state spaces and function approximation make it difficult to extend UCB practically beyond bandits.
- Function approximation uses examples of a desired function to construct a broader representation, and it can use generalization methods from supervised learning and related fields.
Key Takeaways
- UCB generally outperforms epsilon-greedy selection on the 10-armed testbed because its exploration behavior handles uncertain actions effectively in that setting.
- UCB's first k choices form a special startup period in which it randomly selects among untried actions.
- Nonstationary reward distributions weaken the usefulness of historical evidence, and large state spaces make practical UCB extensions difficult.
- Function approximation constructs a broader representation of a desired function from available examples.
- Because function approximation is an instance of supervised learning, reinforcement learning can combine with generalization methods from related fields.