Tabular Solution Methods in Reinforcement Learning

From One State to a General Problem

A useful way to organize reinforcement learning is to begin with the smallest structural case and then move toward the general formulation. A bandit problem has only one state. Finite Markov decision processes provide the broader formulation introduced after bandit problems. This progression matters because it separates methods that can be studied under a single-state restriction from ideas needed for a general finite-state problem.

Recognizing the Single-State Case

To recognize a bandit problem, begin by asking how many states the reinforcement learning problem contains. If the formulation contains only one state, it belongs to the bandit-problem case described here. The key simplification is structural: the problem is restricted to one state instead of being presented in the general finite-state formulation.

The Move to Finite MDPs

Bandit problems are treated as a special case because they restrict reinforcement learning to one state. The chapter sequence then moves from this focused case to finite Markov decision processes, which are the broader problem formulation treated through the rest of the book. This makes bandits a useful starting point for studying solution methods before the general formulation is introduced.

The general finite Markov decision process formulation introduces Bellman equations and value functions as main ideas. In the learning progression, their significance is not that they belong to the single-state bandit restriction, but that they are associated with the broader finite-state formulation that follows it.

Evolutionary Policy Search

Many reinforcement learning methods try to estimate how valuable states or actions are. Evolutionary methods take a different route. They use policy search and reward comparison rather than value-function estimation. A candidate agent follows its policy while interacting with the environment, receives reward for its lifetime of behavior, and is judged by the result. The strongest candidates become the basis for further search.

Following a Policy Population

The evolutionary process can be traced as a sequence across a group of agents. First, multiple candidates are available, with each candidate using a policy. Next, each candidate interacts with the environment during its lifetime. The method then evaluates the reward produced by each complete behavior. Candidates with more reward are favored, and they become the basis for further search. The individual agents do not need to improve during their own lifetimes for the broader search to favor better policies.

Whole Lifetimes Versus Local Estimates

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. This allows the method to search by comparing whole policies even when it never constructs a value function. A value function estimates the value of a state or action; evolutionary evaluation instead asks how well an entire policy performed over its interaction period.

When Evolutionary Methods Fit

Evolutionary methods may be effective when the policy space is small, when it can be organized so that good policies are common or easy to find, or when substantial time is available for searching. These conditions make it more plausible that comparison and selection will encounter useful policies.

They may also have an advantage when the learning agent cannot accurately sense the state of its environment. Methods that depend on accurate environmental sensing may face difficulty in that situation, while evolutionary evaluation can still compare the behavior produced by different policies according to the reward obtained.

• Treating every reinforcement learning problem as a general finite Markov decision process rather than checking whether it has only one state.

  The defining property of a bandit problem is the presence of only one state.

  Fix: Count the states first. A single-state formulation belongs to the bandit-problem case.

• Assuming evolutionary methods must estimate a value for every state or action.

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

  Fix: Track the complete policy behavior and compare the reward obtained over the agent's lifetime.

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

  The important evaluation unit is the agent's lifetime behavior.

  Fix: Judge the candidate by the reward produced by its complete behavior.

• Assuming an agent must improve during its own lifetime for evolution to work.

  The source describes non-learning agents whose policies are evaluated after their interaction periods.

  Fix: Distinguish individual lifetime behavior from the broader search that favors better candidates.

Practice and Takeaways

1. Bandit problems are the single-state special case of reinforcement learning. Finite Markov decision processes are the broader formulation that follows, and Bellman equations and value functions are main ideas associated with that formulation. Evolutionary methods use policy search and reward comparison instead of value-function estimation. They evaluate complete lifetime behavior, favor candidates that obtain more reward, and may be effective when policies are searchable, search time is available, or accurate environmental sensing is difficult.