Approximate Solution Methods in Reinforcement Learning

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.

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.

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.

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 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.

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.

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.