Introduction
In reinforcement learning and operations research, agents often know how to solve individual tasks in isolation—such as a robot navigating a room or picking up an object. However, real-world scenarios frequently require performing these tasks simultaneously (e.g., navigating while carrying an object while avoiding a moving person).
The standard approach to handling this is creating a "composite MDP" where the state space is the cross-product of all individual state spaces. Unfortunately, this triggers the "curse of dimensionality," making computation incredibly expensive. For instance, combining two tasks with 100 states each results in a combined task with 10,000 states. Traditional methods often treat these as inefficient "nonstationary" problems, which struggle to adapt when new tasks arrive unexpectedly.
This paper introduces a method to efficiently combine multiple Markov Decision Processes (MDPs) into a single composite task. By using the optimal solutions of individual tasks to establish upper and lower bounds, the proposed algorithm prunes irrelevant actions and focuses computation only on reachable, competitive states, achieving a significant speedup over standard methods.
Methods: Modified Value Iteration
The authors propose a Modified Value Iteration Algorithm designed specifically for dynamic merging. The core innovation lies in how it initializes and restricts the search space:
- Bounding the Value Function: Instead of starting from scratch, the algorithm calculates initial bounds for the composite state $s$:
- Upper Bound ($U$): The sum of the values of the individual tasks. Because constraints usually make tasks harder, the sum of unconstrained tasks serves as an optimistic ceiling.
- Lower Bound ($L$): The maximum value of any single individual task. At worst, the agent can choose to ignore other tasks and just perform the most important one perfectly.
- Action Pruning: During value iteration, if an action’s upper bound is lower than another action’s lower bound, that action is considered "strictly dominated" and is discarded.
- Focused Backups: The algorithm only updates states that are reachable from the starting state via "competitive" (non-pruned) actions.
- Dynamic Assimilation: Because the algorithm relies on bounds, new tasks can be added "online." The existing bounds are simply adjusted to incorporate the new task's value function without restarting the entire process.
Evaluation Environment
The paper evaluates the algorithm using a synthetic "Avoiding Predators and Eating Food" grid-world environment.
The environment consists of the following components:
- Task 1: An agent (A) must find food (f) in an $n \times n$ grid.
- Task 2: The agent must avoid a predator (p) that actively moves toward it.
- Composite Task: The agent must maximize its food intake while staying alive.
In terms of scale, each individual task contained 625 states, resulting in a composite task with 15,625 states.
Key Insights
- Individual Knowledge is a Shortcut: The critical realization is that even if tasks interfere with each other (e.g., a robot cannot be in two places at once), the solutions to those tasks in isolation provide rigorous mathematical bounds. These bounds allow the algorithm to skip roughly 80% of the computational work in the combined space.
- Greedy is Not Enough: The authors demonstrate that a "naive greedy" policy—simply picking the best immediate action based on individual task values—is significantly suboptimal. The look-ahead provided by value iteration is necessary to handle long-term trade-offs between competing tasks.
- Reachability Matters: In many complex problems, most of the theoretical state space is never actually visited. By starting from the current state and only evaluating competitive paths, the algorithm avoids wasting time on irrelevant calculations.
Key Results
The proposed merging algorithm demonstrated substantial improvements in both efficiency and convergence compared to baseline methods.
- Efficiency: The merging algorithm reached the optimal solution 4-5 times faster (measured in the number of backups) than standard value iteration performed on the full composite state space.
- Convergence: While standard value iteration for the composite problem required roughly 1,000,000 backups to converge, the merging algorithm—initialized with 5,000-backup solutions for the individual tasks—converged much more rapidly.
- Performance: The algorithm successfully found the optimal policy, whereas the heuristic greedy approach fell substantially short of optimal performance.
Limitations and Future Work
- Model Dependency: The current algorithm assumes that the transition and payoff models ($P$ and $R$) are fully known. The authors suggest exploring "model-free" versions, such as Q-learning, in future research.
- Discount Factors: The underlying mathematics currently require all merged MDPs to share the exact same discount factor ($\gamma$).
- Complexity of Constraints: While the paper successfully handles action constraints (e.g., not using the same resource for two jobs simultaneously), the authors aim to extend this framework to Semi-Markov Decision Processes (SMDPs) to accommodate tasks that take varying amounts of time.
- Real-world Application: The evaluation relies on a grid-world toy example. Applying this dynamic merging technique to complex, real-world scenarios like job-shop scheduling represents the next major step for this research.
Summary updated