Function Approximation in Reinforcement Learning

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.

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.

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.

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.

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?

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.

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.