Abstract
Unlike traditional reinforcement learning (RL), market-based RL is in principle applicable to worlds described by partially observable Markov Decision Processes (POMDPs), where an agent needs to learn short-term memories of relevant previous events in order to execute optimal actions. Most previous work, however, has focused on reactive settings (MDPs) instead of POMDPs. Here we reimplement a recent approach to market-based RL and for the first time evaluate it in a toy POMDP setting.
Introduction
Traditional Reinforcement Learning (RL) algorithms often rely on the Markov property, assuming that current sensory input provides sufficient information for optimal decision-making. However, real-world environments are typically Partially Observable Markov Decision Processes (POMDPs), characterized by perceptual aliasing. In such cases, distinct environmental states appear identical to sensors but require different actions. For example, navigating a series of identical intersections requires memory of previous turns. This paper investigates whether a decentralized, economic model of RL—specifically a "Hayek machine"—can evolve the capacity to utilize short-term memory to solve these challenges.
The Hayek4 Architecture
The study utilizes the Hayek4 system, a market-based RL architecture where agents compete in an artificial economy.
Economic Mechanism
The system comprises a population of agents, each defined by a "Post production" rule (an IF-THEN statement), a wealth balance, and a bidding strategy. When an input is received, matching agents bid to take action. The highest bidder wins control for one step and pays their bid to the previous winner, facilitating a "bucket brigade" credit assignment. This enforces strict property rights and credit conservation, preventing the "money inflation" common in earlier classifier systems.
Evolution and Memory
Successful agents accumulate wealth and reproduce, passing on mutated rules to offspring, while bankrupt agents are removed. To address POMDPs, the researchers introduced a 1-bit memory register. Agents can perform "write" actions to modify this bit and include its state in their "read" rules, allowing the economy to store and retrieve a single piece of historical information.
Experimental Evaluation
The system was evaluated on two benchmarks: Blockworld and an adapted Woods101 grid-world.
Blockworld
Blockworld is a classic AI task where agents manipulate block stacks to match a target configuration. This environment served primarily to verify the reimplementation of the Hayek4 architecture and its ability to handle complex state transitions.
Woods101 (POMDP)
The Woods101 environment is a 2D grid-world designed as a toy POMDP. Agents start at positions L or R and must navigate to food at point F. The paths contain aliased positions that look identical to the agent's sensors but require different directional turns (East vs. West) to reach the goal.
Results and Discussion
The experiments demonstrated that the market-based approach can effectively "de-alias" environments through emergent cooperation.
Emergent Memory Usage
In the Woods101 task, the system successfully evolved a stable population of agents that used the 1-bit memory to solve the aliasing problem within approximately 1,000 training instances. One agent would learn to "tag" the environment by setting the memory bit based on the starting position (e.g., '1' for right, '0' for left), while subsequent agents used this bit as context for navigation at ambiguous intersections. This demonstrates emergent cooperation where specialized "memory writers" and "decision makers" work together through the bidding process.
Stability and Scalability
While successful in the toy POMDP, the system faced challenges in larger Blockworld tasks. Universal agents solved stacks up to level 30 when hardwired, but evolving such solvers from scratch for stacks larger than size 5 proved difficult. The evolutionary process often settled for over-specialized agents rather than generalizable rules. Furthermore, the system exhibited high sensitivity to parameter tuning, making stability difficult to maintain without careful adjustment.
Conclusion
This work demonstrates that market-based RL can evolve simple memory-based strategies to solve POMDPs. While scalability and parameter sensitivity remain significant hurdles, the ability of a decentralized economy of agents to establish internal communication protocols offers a promising path for learning in partially observable environments.
Summary updated