On the Difficulty of Modular Reinforcement Learning for Real-World Partial Programming

Sooraj Bhat, Charles Lee Isbell Jr., Michael MateasAAAI 2006

Abstract

Modular Reinforcement Learning (MRL) aims to solve complex tasks by decomposing them into simpler, concurrent subgoals managed by individual subagents. However, a significant challenge arises when an arbitrator must combine the preferences of these subagents into a single action. This paper demonstrates that the problem of arbitration is mathematically equivalent to social choice, proving that a universal, scale-invariant arbitrator is impossible. We propose a shift from mathematical arbitration to a "scheduling" paradigm, implemented via the Adaptive Behavior Language ($A^2BL$), to explicitly manage trade-offs in modular systems.

Introduction

Reinforcement Learning (RL) has seen significant success in controlled environments, yet it frequently struggles with the "curse of dimensionality" in large-scale, real-world applications. Modular Reinforcement Learning (MRL) offers a potential solution by breaking a global task into smaller, manageable sub-problems. For example, a robot might have one module dedicated to "finding food" and another to "avoiding predators." Each module learns its own policy and expresses preferences via Q-values. The central challenge lies in the arbitration process: how should the system reconcile these competing preferences to select an optimal action?

The Challenge of Reward Incomparability

The primary obstacle in MRL is reward incomparability. In standard RL, a single reward signal serves as the ground truth. In MRL, however, human designers typically craft separate reward functions for each module. This creates a software engineering nightmare: how can a designer ensure that +10 units of "food reward" are equivalent to -10 units of "predator damage"?

Most existing MRL techniques rely on simple summation of Q-values. This approach assumes that rewards are on the same scale, which is rarely true in complex systems, especially when different modules are developed by different programmers or reused across different environments. If the scales are not perfectly aligned, one module may inadvertently dominate the others simply because its reward values are numerically larger, not because its goal is more important.

MRL through the Lens of Social Choice

To analyze this problem formally, the authors bridge the gap between AI and economics by applying Social Choice Theory. They reframe MRL arbitration as a voting problem where subagents are "voters" and the arbitrator is a "social welfare function" tasked with deciding a collective action.

The Impossibility Theorem

By adapting Arrow’s Impossibility Theorem to the MRL context, the authors define five desirable properties for an "ideal" arbitrator:

  1. Universality: The arbitrator should work for any possible set of subagent preferences.
  2. Unanimity: If all subagents agree that action A is better than action B, the arbitrator must choose A over B.
  3. Independence of Irrelevant Alternatives (IIA): The relative ranking of two actions should only depend on how subagents rank those two actions, not on a third "irrelevant" action.
  4. Scale Invariance: Multiplying a subagent’s rewards by a constant factor should not change the arbitrator’s final decision.
  5. Non-Dictatorship: No single subagent should always determine the final outcome regardless of others.

The authors prove that for any environment with three or more possible actions ($|A| \ge 3$), it is mathematically impossible for an arbitration function to satisfy all five properties simultaneously. Specifically, requiring scale invariance—which is essential for modular software reuse—mathematically forces the system toward a dictatorship.

From Arbitration to Scheduling: The $A^2BL$ Language

Since a perfect mathematical formula for arbitration does not exist, the paper suggests reframing the arbitrator as a scheduler, analogous to an operating system scheduler. Instead of seeking a "fair" sum, the programmer acts as a "benevolent dictator" who uses domain-specific knowledge to explicitly define how subagents are weighted.

To facilitate this, the authors introduce the Adaptive Behavior Language ($A^2BL$). An extension of the reactive planning language ABL, $A^2BL$ allows developers to define adaptive behaviors. In this framework:

  • Subagents learn their own policies independently.
  • The top-level behavior (the scheduler) explicitly manages trade-offs using coordination logic.
  • Programmers can codify specific exchange rates (e.g., "finding food is 10x more important than avoiding minor damage"), making the system’s decision-making process transparent and maintainable.

Discussion and Conclusion

The theoretical findings in this paper represent a conceptual shift for MRL. The proof of reward incomparability suggests that the search for a universal Q-value summation formula is a dead end. Instead, the difficulty of MRL should be treated as a software engineering challenge centered on reward consistency and modular reuse.

While the $A^2BL$ approach provides a structured way to handle these trade-offs, it places the burden of coordination back on the programmer. Future research is required to explore how these "mixture decompositions" perform in massive, multi-programmer environments and to develop better tools for managing the complex interplay between sequential and concurrent tasks in modular architectures.

Summary updated

BibTeX
@inproceedings{bhat2006difficulty,
  author = {Sooraj Bhat and Charles Lee Isbell Jr. and Michael Mateas},
  title = {{On the Difficulty of Modular Reinforcement Learning for Real-World Partial Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure