Approximate Solution Methods in Reinforcement Learning

Choosing a Solution Representation

A reinforcement learning problem can be approached in different ways depending on how large its state and action spaces are and what the method can represent. When the possible states and actions form a small collection, a tabular method can store a value estimate for each relevant case. When the problem is much larger, an approximate method can provide a general solution without storing every case explicitly. Evolutionary methods take a different route: they search over policies by comparing the rewards produced by complete agent behaviors.

Small Spaces and Explicit Tables

A tabular method stores value-function estimates directly in an array or table. Each entry corresponds to a relevant state, or to a state and action combination. This representation is practical when the collection of possible states and actions is small enough that all the required entries can be stored explicitly.

The table is useful because the problem is small, not because a table removes the need to solve the reinforcement learning problem. The method still has to determine useful value estimates and use them to identify a policy. The table simply provides a direct place to represent the estimates.

A Small Table in Practice

This example illustrates the reasoning chain: first assess the size of the state and action spaces, then ask whether the value estimates can be represented explicitly, and finally decide whether a tabular route is appropriate. The fact that entries can be stored does not by itself guarantee that the problem has already been solved.

Exact and Approximate Results

A tabular method is appropriate when the value function can be represented explicitly because the state and action spaces are small. Under those conditions, it can often produce an exactly optimal value function and policy. Approximate methods are intended for much larger problems. They make the problem manageable by providing approximate solutions rather than an exactly optimal result in every represented case.

Evolutionary Policy Search

Evolutionary methods use policy search and reward comparison rather than value-function estimation. A collection of agents uses different policies to interact with the environment. Each candidate is judged by the behavior it produces over its lifetime, and candidates that obtain more reward are favored for the next stage of the search.

The process is analogous to biological evolution in one specific sense: an individual agent can display successful behavior without learning during its own lifetime, while the broader search favors candidates associated with better results. In reinforcement learning, the object being searched is a policy or a set of policies.

Whole-Behavior Evaluation

The important unit of evaluation in an evolutionary method is the agent's lifetime behavior, not an isolated estimate attached to one state or one action. A value function estimates the value of a state or action. An evolutionary method instead asks how well an entire policy performed over its interaction period. Because of this difference, evolutionary search can compare whole policies without constructing a value function.

When Evolutionary Search Fits

• The policy space is small or searchable.
• The policy space can be organized so that good policies are common or easy to find.
• Substantial time is available for searching.
• The learning agent cannot accurately sense the state of its environment.

These conditions make it more plausible that repeated comparison and selection will encounter useful policies. Limited environmental sensing is especially relevant because methods that depend on accurate environmental sensing may face difficulty, while evolutionary evaluation can still compare the behavior produced by different policies according to the rewards they obtain.

Mistakes in Method Selection

• Assuming that a table is appropriate for every reinforcement learning problem.

  Tabular methods depend on being able to store the relevant value estimates explicitly.

  Fix: Assess the size of the state and action spaces before selecting a table.

• Treating an approximate solution as exactly optimal.

  Approximate methods provide approximate solutions.

  Fix: Reserve the term exact for a solution that is precisely optimal, and identify larger-problem results as approximate when appropriate.

• Assuming every reinforcement learning method must estimate a value function.

  Evolutionary methods use policy search and reward comparison rather than value-function estimation.

  Fix: Track the complete behavior of each candidate policy and compare the rewards obtained.

• Evaluating an evolutionary candidate from one isolated state or action.

  The evolutionary evaluation unit is the agent's lifetime behavior over its interaction period.

  Fix: Evaluate the reward associated with the complete behavior produced by the policy.

Check Your Reasoning

Key Takeaways

1. Tabular methods store value-function estimates directly in arrays or tables, so they are suitable when state and action spaces are small enough to represent explicitly. When this representation applies, the method can often identify the exactly optimal value function and policy. Approximate methods address much larger problems but provide approximate solutions. Evolutionary methods use a different evaluation unit: they compare complete policy behaviors by the rewards obtained over agent lifetimes, then favor stronger candidates for further search.