My Brain is Full: When More Memory Helps

Christopher Lusena, Tong Li, Shelia Sittinger, Chris Wells, Judy GoldsmithUAI 1999

TL;DR

This paper explores how to find optimal control policies for Partially Observable Markov Decision Processes (POMDPs) using finite memory. The authors introduce and compare three search heuristics (local search, simulated annealing, and genetic algorithms) for finding these policies, finding that providing more memory than strictly necessary often leads to better policy convergence, even though it increases computation time.

What Problem Does This Paper Address?

POMDPs are powerful models for systems where both the state and the effects of actions are uncertain, making them applicable to domains like robotics and economics. However, finding optimal control policies for POMDPs is computationally intractable. Traditional approaches often lead to policies that are either suboptimal or require an infeasible amount of memory to store. This paper tackles the challenge of finding good, yet computationally manageable, policies by focusing on "free finite-memory policies," where the amount of memory is a parameter that can be tuned. The core problem is to balance the complexity of finding optimal policies with the need for practical, efficient solutions.

Methods

The authors investigate three search heuristics for finding free finite-memory policies:

  • Local Search: A technique that incrementally improves a solution by exploring its neighborhood. They use a "randomized first improvement" strategy.
  • Simulated Annealing: Another local search optimization technique inspired by annealing in metallurgy. It allows for occasional "bad" moves to escape local optima.
  • Genetic Algorithms: A population-based search method that evolves solutions through processes like mutation and reproduction.

These heuristics are used to search the space of policies, where a policy is a mapping from (observation, memory state) pairs to (action, memory state) pairs. The number of possible memory states is a key parameter. The performance of these heuristics is compared against each other and against an existing dynamic programming algorithm for finite-state controllers.

Datasets

The paper evaluates their algorithms on ten POMDPs:

  • Five from Cassandra's database (1D, 4x3.95, 4x3.CO.95, aloha.10, aloha.30).
  • Four from existing literature (Sutton's gridworld, McCallum's maze, Maze7, and Mazelo).
  • One additional small test case (test1).

These POMDPs were tested with varying numbers of memory states (from 1 to 10, depending on the specific POMDP).

Key Insights and Ideas

  • More Memory Can Be Better (Even Excessively): The most surprising finding is that providing more memory than is strictly needed for an optimal policy actually increases the likelihood of the search algorithms converging to an optimal-valued policy. This suggests that extra memory can help navigate complex search spaces and avoid local optima.
  • The Memory Trade-off: While more memory improves the chances of finding a better policy, it also significantly increases computation time. This creates a fundamental trade-off between policy quality and computational cost.
  • Finite Memory as a Compromise: Free finite-memory policies offer a practical compromise between the intractability of optimal history-dependent policies and the potential suboptimality of simpler stationary policies.
  • Search Heuristics vs. Exact Methods: The implemented search heuristics are shown to be competitive, and in some cases faster, than existing exact methods for finite-state controllers, especially for larger POMDP instances.

Key Results

  • Run Times: For smaller POMDPs, the run times of local search, simulated annealing, and genetic algorithms were comparable, with genetic algorithms often being slower. Local search was generally the fastest.
  • Policy Quality: The paper presents tables showing the likelihood of finding the optimal policy for various POMDPs and memory sizes. These tables consistently demonstrate that increasing memory beyond the minimum required often leads to a higher percentage of successful optimal policy findings. For example, in McCallum's maze, which has an optimal policy with two memory states, searches with more memory found the optimal policy more often.
  • Comparison to Hansen's Algorithm: For larger POMDP instances, Hansen's policy iteration algorithm either took an impractically long time or failed due to numerical instabilities, whereas the authors' search heuristics were more robust.

Limitations and Future Work

  • Computational Cost of Extra Memory: The authors acknowledge that while extra memory improves policy quality, it comes at a significant computational cost, presenting a clear time-quality trade-off.
  • Genetic Algorithm Implementation: The current genetic algorithm implementation was found to be the least likely to find optimal policies among the tested heuristics, and the authors expect substantial improvements with further development.
  • Parameter Tuning: The effects of different genetic algorithm parameters (cross-over and mutation rates) and simulated annealing cooling schemes were not extensively studied, suggesting avenues for future optimization.
  • Infinite Horizons and Discounted Rewards: The current work focuses on finite horizons and total rewards. Future work will explore infinite horizons and discounted rewards.
  • Policy Representation: The paper notes that while finite-state controllers have a tight link between memory and action, free finite memory policies allow for decoupling, which is a key difference and area of exploration.

Summary updated

BibTeX
@inproceedings{lusena1999my,
  author = {Christopher Lusena and Tong Li and Shelia Sittinger and Chris Wells and Judy Goldsmith},
  title = {{My Brain is Full: When More Memory Helps}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure