Market-Based Reinforcement Learning in Partially Observable Worlds

Ivo Kwee, Marcus Hutter, Jürgen Schmidhuber

TL;DR

This paper explores how "market-based" reinforcement learning—where agents compete in an artificial economy—can solve problems involving hidden information (POMDPs). By adding a simple 1-bit memory register to a Hayek machine, the authors demonstrate that an evolving population of agents can learn to "tag" their environment, effectively remembering past events to make correct decisions in the present.

What Problem Does This Paper Address?

Most traditional Reinforcement Learning (RL) algorithms assume the Markov property: the idea that your current sensory input provides all the information you need to choose the optimal next action. In the real world, this is rarely true. We live in Partially Observable Markov Decision Processes (POMDPs).

The authors highlight the problem of perceptual aliasing: when two different states in the world look identical to your sensors but require different actions. Imagine a set of directions: "Turn left at the first light, right at the second." When you reach a light, your immediate "input" (a red light) doesn't tell you if it's the first or second one. To succeed, you need a memory of past events. This paper investigates whether a decentralized, economic model of RL can evolve the ability to use such a memory.

Methods

The researchers focus on the Hayek4 System, a specific "market-based" RL architecture.

  • The Economy: The system consists of a population of agents. Each agent has a "Post production" rule (an IF-THEN statement), a wealth balance, and a bid.
  • The Auction: When the system receives an input, agents whose rules match the input bid to take action. The highest bidder wins, "owns" the world for one step, and pays their bid to the previous winner (a "bucket brigade" credit assignment).
  • Evolution: Successful agents (those that accumulate wealth) can "reproduce," creating children with mutated rules. Unsuccessful agents eventually go bankrupt and are removed.
  • The Memory Extension: The core novelty here is adding a 1-bit memory register. Agents can now perform a "write" action to change this bit and include the state of this bit in their "read" rules. This allows the economy to store a single piece of information about the past.

Datasets

The authors evaluated their system on two primary benchmarks:

  1. Blockworld: A classic AI task where agents must move blocks between stacks to match a target configuration. This was used primarily to verify their reimplementation of the Hayek4 architecture.
  2. Woods101 (Adapted): A 2D grid-world "toy POMDP." In this environment, an agent starts at either point L or R and must reach food at point F. Crucially, the paths from L and R contain "aliased" positions—locations that look identical to the agent's sensors but require different turns (East vs. West) to reach the goal.

Key Insights and Ideas

  • De-aliasing via "Tagging": The most significant "aha moment" is seeing the economy solve the POMDP. One agent learns to set the memory bit to "1" if the path started from the right, while another sets it to "0" for the left. Later agents then use that bit as a "context" to decide which way to turn at the ambiguous intersection.
  • Credit Conservation is Key: Unlike earlier classifier systems, Hayek machines enforce strict property rights and credit conservation. Money isn't created out of thin air; it must be earned through successful actions or passed between agents. This prevents "money inflation" and leads to a more stable learning process.
  • Emergent Cooperation: No single agent solves the whole problem. Instead, a chain of specialized agents evolves—some act as "memory writers" and others as "decision makers," cooperating through the bidding process to reach the reward.

Key Results

  • Blockworld Success: The hardwired "universal" agents reliably solved stacks up to level 30. However, the system struggled to evolve a universal solver from scratch for stacks larger than size 5, indicating a ceiling on current evolutionary efficiency.
  • Solving the POMDP: In the Woods101 test, the system successfully evolved a stable population of roughly 8 agents that used the 1-bit memory to solve the aliasing problem within about 1,000 training instances.
  • Local Optima: The system tended to converge on a specific "convention" (e.g., 0 for left, 1 for right) and stick to it, showing that the market can effectively establish and maintain internal communication protocols.

Limitations and Future Work

The authors are candid about the difficulties of this approach:

  • Stability is an "Art": Reimplementing Hayek4 was difficult because the system is highly sensitive to parameters. Tuning the economy to be stable without collapsing or stagnating remains a challenge.
  • Scalability: While the system solved the toy POMDP, it struggled with larger versions of the Blockworld task. The evolutionary process often failed to find "universal" rules, instead settling for over-specialized agents.
  • Generalization: The agents didn't always use "don't care" symbols (wildcards) optimally, leading to redundant agents in the economy.

Future work will likely focus on making these market-based systems more robust and capable of handling more complex memory structures beyond a single bit.

Summary updated

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.
BibTeX
@inproceedings{kwee2001market,
  author = {Ivo Kwee and Marcus Hutter and Jürgen Schmidhuber},
  title = {{Market-Based Reinforcement Learning in Partially Observable Worlds}},
  booktitle = {ICANN},
  year = {2001},
  doi = {10.1007/3-540-44668-0\_120},
}

Loading related content...

Figure