Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing

Sanae Amani, Khushbu Pahwa, Vladimir Braverman, Lin F. Yang

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:

  1. 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.
  2. Server Querying: The agent sends this estimate to the central server. The server compares it against a lookup table of already-solved tasks.
  3. Policy Execution or Deep Exploration (Phase 2):
  4. If the server recognizes the task as "already solved," it sends back the learned $\epsilon$-optimal policy, saving the agent from redundant exploration.
  5. 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.
Figure 1: Normalized AR and AT.

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).

Figure 2: Number of frames required by DistMT-LSVI agents to reach x% {20, 40, 60, 80, 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:

  1. 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.
  2. 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

Abstract

Recently, DARPA launched the ShELL program, which aims to explore how experience sharing can benefit distributed lifelong learning agents in adapting to new challenges. In this paper, we address this issue by conducting both theoretical and empirical research on distributed multi-task reinforcement learning (RL), where a group of $N$ agents collaboratively solves $M$ tasks without prior knowledge of their identities. We approach the problem by formulating it as linearly parameterized contextual Markov decision processes (MDPs), where each task is represented by a context that specifies the transition dynamics and rewards. To tackle this problem, we propose an algorithm called DistMT-LSVI. First, the agents identify the tasks, and then they exchange information through a central server to derive $ε$-optimal policies for the tasks. Our research demonstrates that to achieve $ε$-optimal policies for all $M$ tasks, a single agent using DistMT-LSVI needs to run a total number of episodes that is at most $\tilde{\mathcal{O}}({d^3H^6(ε^{-2}+c_{\rm sep}^{-2})}\cdot M/N)$, where $c_{\rm sep}>0$ is a constant representing task separability, $H$ is the horizon of each episode, and $d$ is the feature dimension of the dynamics and rewards. Notably, DistMT-LSVI improves the sample complexity of non-distributed settings by a factor of $1/N$, as each agent independently learns $ε$-optimal policies for all $M$ tasks using $\tilde{\mathcal{O}}(d^3H^6Mε^{-2})$ episodes. Additionally, we provide numerical experiments conducted on OpenAI Gym Atari environments that validate our theoretical findings.
BibTeX
@misc{amani2023scaling,
  author = {Sanae Amani and Khushbu Pahwa and Vladimir Braverman and Lin F. Yang},
  title = {{Scaling Distributed Multi-task Reinforcement Learning with Experience Sharing}},
  year = {2023},
  eprint = {2307.05834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.05834},
}
Figure