Approximate Solutions in Reinforcement Learning
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.
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.
- 1Consider consequences
The exact route investigates what might happen after each available decision.
- 2Evaluate rewards
The possible developments are evaluated in terms of expected reward.
- 3Compare 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 1020 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
Common mistake Assuming that the Bellman optimality equation automatically gives a usable policy.
What it looks likeThe equation defines a route to an optimal policy, so an agent is assumed to be able to calculate that policy directly.
Why it failsThe route may require more information, computation, or memory than the practical task provides.
Do this insteadSeparate the existence of a theoretical route from the feasibility of obtaining and using its result.
Common mistake Treating an accurate model as sufficient for exact planning.
What it looks likeAn agent has a complete and accurate environment model, so exact computation is assumed to be easy.
Why it failsLimited computation can still prevent the agent from fully using the model.
Do this insteadCheck both the quality of the model and the computational resources available.
Common mistake Forgetting that the Markov property is one of the required conditions.
What it looks likeOnly environment dynamics and computer speed are considered when discussing exact solutions.
Why it failsThe source identifies the Markov property as the third supporting condition.
Do this insteadList 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.
- 1Manageable table
At the smaller scale, storing exact information for each state may be possible.
- 2Growing requirements
As the number of possible states grows, the table requires more exact entries and therefore more memory.
- 3Practical 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. |
Exact and approximate solutions differ in representation and feasibility, while the exact solution remains the reference target.
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.
- 1Check the assumptions
Accurate dynamics are available, but sufficient memory is not. The exact approach therefore cannot be assumed to be practical.
- 2Identify the storage problem
The agent cannot maintain exact tabular information for every possible state.
- 3Identify the practical response
The agent uses an approximation of a value function, policy, or model rather than requiring exact information everywhere.
- 4Preserve 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
- 1The Bellman optimality equation provides a route toward finding an optimal policy by considering consequences and expected rewards.
- 2An exact solution requires accurate environment dynamics, sufficient computational resources, and the Markov property.
- 3Large state spaces can make both exact computation and exact tabular storage impractical.
- 4Reinforcement learning agents therefore use approximations of value functions, policies, and models when memory or computation is limited.
- 5Optimality remains a theoretical target even when the agent can achieve only an approximation of it.
At a glance
- 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.