TL;DR
This paper introduces GM-Sarsa(O), a novel reinforcement learning algorithm designed for complex tasks with multiple, interdependent goals. Unlike previous modular approaches that optimize sub-goals in isolation, GM-Sarsa(O) trains modules concurrently within the composite task, leading to more effective policies and improved performance on a challenging multi-goal problem.
What Problem Does This Paper Address?
Traditional reinforcement learning (RL) excels at single-goal tasks but struggles with scaling to more complex scenarios. This paper focuses on a specific scaling challenge: problems involving multiple, potentially hierarchical goals that must be addressed simultaneously by a single agent. A naive approach of creating a single, massive state space for all goals quickly becomes intractable due to the "curse of dimensionality." Modular approaches, where individual modules learn policies for sub-goals, offer a promising alternative. However, existing modular RL methods, often based on Q-learning, suffer from a critical flaw: optimizing sub-goals independently can lead to suboptimal composite policies because they don't account for the fact that modules must share control and compromise on actions. This paper aims to fix this by developing a modular RL algorithm that learns good policies in the context of the composite task.
Methods
The core of the paper is the introduction of GM-Sarsa(O), an extension of the modular Q-learning approach. The authors frame the problem as a set of $N$ component Markov Decision Processes (MDPs) that share a common action space.
Here's a breakdown of the methods:
- Modular Architecture: The approach decomposes the complex problem into several smaller, manageable MDPs, each handled by a dedicated learning module.
- Composite MDP: The overall problem is viewed as a single, larger composite MDP, where the goal is to maximize the sum of discounted rewards across all component MDPs.
- Action Selection Mechanism: The paper discusses various ways to combine the internal Q-values from individual modules to select a single action for the agent. They focus on the "greatest mass" (GM) approach, which sums the Q-values from all modules to determine the best action.
- GM-Sarsa(O) vs. GM-Q: The key innovation is replacing the standard Q-learning update rule with the Sarsa(O) update rule for training each module.
- Q-learning (off-policy): Updates are based on the maximum possible future Q-value, assuming optimal future actions. This is problematic in modular settings because future actions are a compromise, not necessarily optimal for any single module. This leads to a "positive bias" in Q-values.
- Sarsa(O) (on-policy): Updates are based on the actual Q-value of the next state-action pair that is observed. This on-policy nature means the updates reflect the true expected return under the current (compromise) policy, avoiding the positive bias issue.
Datasets
The paper evaluates GM-Sarsa(O) on a custom-designed sample problem:
- Food Gathering Task: A 5x5 grid world where an agent must gather stationary food items while avoiding a predator. This task is decomposed into one MDP for the agent-predator interaction and three MDPs for the agent-food item interactions. The state space is large (25^5 * 10 million states), making it suitable for a modular approach.
Key Insights and Ideas
- The "Positive Bias" Problem: The most significant insight is the identification of a fundamental flaw in existing modular Q-learning algorithms. By optimizing sub-goals independently using off-policy Q-learning, the learned Q-values are biased upwards, not reflecting the true expected return under the composite policy.
- On-Policy Learning for Compromise: The paper highlights that on-policy learning methods like Sarsa(O) are crucial for modular RL when modules must share control. Sarsa(O) naturally accounts for the actual actions taken, leading to more accurate Q-value estimates in such compromise scenarios.
- GM-Sarsa(O) as a Solution: The proposed GM-Sarsa(O) algorithm directly addresses the positive bias by using Sarsa(O) for module training and the "greatest mass" action selection to leverage the summed utility estimates.
Key Results
The paper presents empirical results demonstrating the effectiveness of GM-Sarsa(O):
- Superior Performance: On the food gathering task, GM-Sarsa(O) significantly outperformed three Q-learning based modular algorithms (GM-Q, Top-Q, and Negotiated-W) in terms of average reward per step during training.
- Visual Evidence: Figure 1 in the paper visually depicts GM-Sarsa(O) achieving the highest average reward per step, indicating faster and more effective learning.
Limitations and Future Work
- Convergence Proof: The authors acknowledge that they do not currently have a formal convergence proof for the GM-Sarsa(O) algorithm. This is a significant area for future work.
- Exploration Strategy: While the paper mentions an $\epsilon$-greedy exploration policy with a linearly decaying $\epsilon$, further research into more sophisticated exploration strategies for modular RL could be beneficial.
- Generalization: The paper focuses on a specific task. Future work could explore the algorithm's performance on a wider range of composite MDP problems and investigate its generalization capabilities.
- Action Selection Mechanisms: While "greatest mass" is explored, other action selection mechanisms could be revisited and adapted for Sarsa(O) to see if they yield further improvements.
Summary updated