TL;DR
This paper introduces DistMT-LSVI, a novel distributed multi-task reinforcement learning algorithm that allows a network of $N$ agents to collaboratively master $M$ distinct tasks without knowing the tasks' identities in advance. By leveraging a central server to identify tasks and share experiences, the algorithm achieves a near-linear ($1/N$) reduction in sample complexity per agent compared to non-distributed methods.
What Problem Does This Paper Address?
In multi-task reinforcement learning (RL), agents face a variety of environments and must learn optimal policies across all of them. While distributed RL allows multiple agents to collect data in parallel, combining these two paradigms introduces a major hurdle: unknown task identities.
Imagine a fleet of robots deployed in different environments. They encounter various tasks (e.g., navigating different terrains or handling different objects) but lack explicit labels telling them which task they are currently facing. For these robots to share experiences effectively, they must first figure out if they are working on the same problem.
Prior works either assume tabular settings (finite states/actions), require a computationally heavy model-based planning oracle, or assume task labels are known. Inspired by DARPA’s Shared-Experience Lifelong Learning (ShELL) program, this paper addresses how a decentralized group of agents can cooperatively solve a pool of unknown tasks with maximum sample efficiency.
Methods
The authors model the problem as a linearly parameterized contextual Markov Decision Process (MDP), where each task's rewards and transition dynamics are determined by an unknown task-specific context vector.
To make task identification possible without explicit labels, they introduce a Task-Separability Assumption: the optimal value functions of any two distinct tasks must differ by at least a constant threshold ($c_{\rm sep}$) at the initial state $s_0$.
The proposed algorithm, Distributed Multi-Task Least Value Iteration (DistMT-LSVI), operates in consecutive learning rounds across $N$ parallel agents and a central server:
- Task Identification (Phase 1): At the start of a round, each agent is assigned an unknown task. The agent runs a brief exploration phase ($K_1$ episodes) to collect initial statistics and estimate the task's value function at the starting state.
- Server Querying: The agent sends this estimate to the central server. The server compares it against a lookup table of already-solved tasks.
- Policy Execution or Deep Exploration (Phase 2):
- If the server recognizes the task as "already solved," it sends back the learned $\epsilon$-optimal policy, saving the agent from redundant exploration.
- If the task is new, the server flags it, and the agent executes a deeper exploration phase ($K_2$ episodes) to solve the task from scratch. The agent then uploads the newly computed parameters to update the server's lookup table.
For practical deep RL implementation, the authors combine a Deep Q-Network (DQN) with Elastic Weight Consolidation (EWC) to prevent catastrophic forgetting as agents switch tasks. They also introduce a lightweight neural network called SimNet to rapidly measure task similarity via parameter distance in deployment.
Datasets
The algorithm was empirically validated using the OpenAI Gym Atari benchmark. The authors selected a suite of 10 distinct games to represent the task pool ($M=10$):
- Alien, Boxing, Battlezone, Breakout, Jamesbond, Frostbite, Freeway, Kangaroo, Krull, and DemonAttack.
Key Insights and Ideas
- Value Functions as Task Fingerprints: Instead of relying on explicit environment IDs, the algorithm uses the optimistic estimate of the state-value function ($V(s_0)$) as a reliable proxy for task identity.
- The Power of Collaboration ($1/N$ Speedup): By dividing the exploration burden, the total number of episodes any single agent needs to run scales as $\mathcal{O}(M/N)$. If you double the number of cooperative agents, the learning time per agent is cut in half.
- Avoiding Redundancy: The two-phase design ensures that agents only spend heavy exploration budgets ($K_2$) on genuinely novel tasks, instantly exploiting shared knowledge for tasks already solved by peers.
Key Results
Theoretical Guarantees
The authors prove that the total number of episodes a single agent needs to run to achieve $\epsilon$-optimal policies for all $M$ tasks is bounded by: $$\tilde{\mathcal{O}}\left(\frac{d^3H^6(\epsilon^{-2} + c_{\rm sep}^{-2}) \cdot M}{N}\right)$$ where $d$ is the feature dimension and $H$ is the episode horizon. This directly improves upon non-distributed settings by a factor of $1/N$.
Empirical Performance
In the Atari simulations (configured with $N=20$ agents and $M=10$ tasks), DistMT-LSVI significantly outperformed isolated agents that learned without experience sharing:
- Linear Reward Scaling: The system achieved an approximate $0.88N$ linear scaling in normalized Agent Reward (AR) as the number of agents increased.
- Reduced Training Time: Agent Time (AT)—the average time required to reach 90% of the baseline performance—dropped sharply as more agents were added to the network.
Furthermore, as shown in Figure 2, adding more agents drastically reduced the total number of training frames required to hit various performance thresholds (from 20% up to 99% of the single-agent reward).
Limitations and Future Work
While both the theoretical and empirical results are compelling, the authors note two primary limitations:
- Linear MDP Assumption: The theoretical proof relies heavily on linear function approximation. Extending these formal sample-complexity bounds to complex, non-linear deep neural networks remains an open theoretical challenge.
- Uniform Task Distribution: The current framework assumes tasks are assigned to agents based on a uniform distribution. Real-world applications may feature adversarial or highly non-stationary streaming sequences of tasks, which require further study.
Summary updated