Approximate Solutions in Reinforcement Learning
The Bellman optimality equation gives a route to finding an optimal policy, but explicit solution is rarely directly useful.
The Ideal Route to Good Decisions
The Bellman optimality equation offers a direct-sounding route to an optimal policy. An agent can examine possible consequences of decisions, evaluate their expected rewards, and use that information to choose well. The difficulty is not only whether the equation defines an optimal solution. The practical difficulty is whether an agent can obtain and use that solution with the information, computation, and memory available.
Optimality is a theoretical target. In practical reinforcement learning, the agent generally works with an approximation because the exact information may be too large or too expensive to compute.
Choosing between two actions
Imagine an agent deciding between two actions. To choose optimally, it would need to consider the possible developments after each action, how likely those developments are, and how desirable their expected rewards are.
Consider consequences: The exact route investigates what might happen after each available decision.
Evaluate rewards: The possible developments are evaluated in terms of expected reward.
Compare decisions: The action with the better resulting evaluation can be used to construct an optimal policy.
The equation provides a route toward an optimal policy, but the route may require an enormous amount of information and computation.
When Exact Calculation Becomes Too Large
An exact approach is an exhaustive investigation. It considers possible developments, their likelihoods, and their expected rewards across the relevant states and actions. As the number of states and decisions grows, the amount of information and computation can become too large for the calculation to finish in a useful amount of time.
Backgammon illustrates the computational barrier. Its approximately 10^20 states make solving for the optimal state-value function or optimal action-value function take an estimated thousands of years on today's fastest computers.
Conditions for an Exact Solution
The exact approach depends on three supporting conditions. The environment dynamics must be known accurately, enough computational resources must be available to complete the calculation, and the Markov property must hold. In practical reinforcement learning tasks, these conditions are rarely all satisfied at the same time.
| Condition | Why it matters | What failure means |
|---|---|---|
| Accurate environment dynamics | The exact route depends on correct information about how the environment develops. | The calculation lacks the accurate environment information it requires. |
| Sufficient computational resources | The states, actions, consequences, and expected rewards must be processed. | Even a complete and accurate model may not be fully usable. |
| The Markov property | The exact approach requires this property to hold. | One of the supporting conditions for an exact solution is absent. |
The three conditions identified for an exact Bellman optimality solution
Assuming that the Bellman optimality equation automatically gives a usable policy.
The route may require more information, computation, or memory than the practical task provides.
Fix:
Separate the existence of a theoretical route from the feasibility of obtaining and using its result.Treating an accurate model as sufficient for exact planning.
Limited computation can still prevent the agent from fully using the model.
Fix:
Check both the quality of the model and the computational resources available.Forgetting that the Markov property is one of the required conditions.
The source identifies the Markov property as the third supporting condition.
Fix:
List all three conditions: accurate dynamics, sufficient computation, and the Markov property.
Memory Limits and Approximation
Reinforcement learning environments may contain too many states for exact tabular storage. A table with one exact entry for every state becomes impractical as the number of possible states grows. The agent then faces a storage problem as well as a computation problem: it may not have enough memory to retain exact information for every state.
Approximation is a response to these limits. Instead of requiring exact information for every possible state, an agent may maintain an approximation of a value function, a policy, or a model. These approximations reduce the demand for exact storage or complete computation, although they do not provide the exact solution.
A growing state table
Imagine an agent whose environment begins with a manageable number of possible states and later expands to many more possible states.
Manageable table: At the smaller scale, storing exact information for each state may be possible.
Growing requirements: As the number of possible states grows, the table requires more exact entries and therefore more memory.
Practical response: When exact tabular storage is no longer practical, the agent needs an approximation of relevant value, policy, or model information.
The approximation is not identical to an exact table, but it allows the agent to work within computation and memory limits.
Targeting Optimality Without Reaching It
Optimality remains useful even when exact achievement is unrealistic. The optimal solution gives the agent a theoretical standard: it describes the quality of decision-making that the exact route is intended to find. An approximate solution can then be understood as an attempt to approach that standard under practical limits.
| Exact solution | Approximate solution |
|---|---|
| Aims to represent the optimal result exactly. | Aims to approach the optimal result within practical limits. |
| Can require information for every state. | Avoids requiring exact tabular information for every possible state. |
| Depends on accurate dynamics, sufficient computation, and the Markov property. | Is used when computation or memory makes exact information impractical. |
| Provides the theoretical ideal. | Provides the practical result an agent can store and compute. |
Check Your Understanding
An environment has a very large number of possible states. Its dynamics are known accurately, but the agent has limited memory and computation. Explain why an exact Bellman optimality solution may still be impractical, and identify what kinds of information the agent may approximate instead.
Hints
- Separate environment knowledge from the resources needed to use that knowledge.
- Mention both exact tabular storage and computational scale.
- Name the three types of objects that may be approximated.
Reasoning through the limitation
An agent has accurate environment dynamics but cannot store one exact value for every state.
Check the assumptions: Accurate dynamics are available, but sufficient memory is not. The exact approach therefore cannot be assumed to be practical.
Identify the storage problem: The agent cannot maintain exact tabular information for every possible state.
Identify the practical response: The agent uses an approximation of a value function, policy, or model rather than requiring exact information everywhere.
Preserve the target: The optimal solution remains the theoretical target even though the result available to the agent is only approximate.
Limited memory alone can make exact storage impractical, so approximation becomes necessary without changing the role of optimality as the target.
What to Remember
- The Bellman optimality equation provides a route toward finding an optimal policy by considering consequences and expected rewards.
- An exact solution requires accurate environment dynamics, sufficient computational resources, and the Markov property.
- Large state spaces can make both exact computation and exact tabular storage impractical.
- Reinforcement learning agents therefore use approximations of value functions, policies, and models when memory or computation is limited.
- Optimality remains a theoretical target even when the agent can achieve only an approximation of it.
Key Takeaways
- Solving the Bellman optimality equation is intended to provide an optimal policy.
- Exact calculation depends on accurate dynamics, sufficient computation, and the Markov property.
- Very large state spaces can require more computation and memory than an agent can provide.
- Approximate solutions represent value functions, policies, or models without storing exact information for every state.
- An agent may aim for optimality while achieving only an approximation in practice.