PaperlayerView exact revision on arXiv

Source-linked AI summary

Lenient Multi-Agent Deep Reinforcement Learning

Gregory Palmer, Karl Tuyls, Daan Bloembergen, Rahul Savani

arXiv:1707.04402v2cs.MAcs.AIcs.LG

TL;DR

MA-DRL replay memories can contain outdated transitions because agents update their policies in parallel, complicating coordination under stochastic rewards. The paper applies decaying-temperature leniency through LDQN and evaluates it against standard and scheduled HDQN in extended CMOTP tasks, finding that LDQN more often converges to optimal joint policies. Preliminary prioritized-replay trials nevertheless converged to a sub-optimal joint policy, leaving compatibility with other components unresolved.

  • Problem

    Parallel policy updates can make replayed transitions outdated in MA-DRL, while fully cooperative stochastic-reward tasks require agents to learn implicit coordination.

  • Method

    LDQN stores decaying state-action temperatures to control leniency toward negative replay updates, using retroactive temperature decay and T(s)-Greedy exploration, and is evaluated against standard and scheduled HDQN.

  • Results

    LDQNs significantly outperform standard and scheduled HDQNs in stochastic-reward environments and are more likely to converge to optimal joint policies.

  • Takeaways & Limitations

    Leniency can be applied to MA-DRL to support optimal joint policies in fully cooperative environments requiring implicit coordination and stochastic rewards.

  • Takeaways & Limitations

    Preliminary LDQN trials with Prioritized Experience Replay consistently converged to a sub-optimal joint policy, leaving performance with other state-of-the-art components unresolved.

Abstract

from arXiv · show

Much of the success of single agent deep reinforcement learning (DRL) in recent years can be attributed to the use of experience replay memories (ERM), which allow Deep Q-Networks (DQNs) to be trained efficiently through sampling stored state transitions. However, care is required when using ERMs for multi-agent deep reinforcement learning (MA-DRL), as stored transitions can become outdated because agents update their policies in parallel [11]. In this work we apply leniency [23] to MA-DRL. Lenient agents map state-action pairs to decaying temperature values that control the amount of leniency applied towards negative policy updates that are sampled from the ERM. This introduces optimism in the value-function update, and has been shown to facilitate cooperation in tabular fully-cooperative multi-agent reinforcement learning problems. We evaluate our Lenient-DQN (LDQN) empirically against the related Hysteretic-DQN (HDQN) algorithm [22] as well as a modified version we call scheduled-HDQN, that uses average reward learning near terminal states. Evaluations take place in extended variations of the Coordinated Multi-Agent Object Transportation Problem (CMOTP) [8] which include fully-cooperative sub-tasks and stochastic rewards. We find that LDQN agents are more likely to converge to the optimal policy in a stochastic reward CMOTP compared to standard and scheduled-HDQN agents.

1 INTRODUCTION

MA-DRL is difficult because agents’ changing policies make replayed transitions outdated, especially when coordination and stochastic rewards are required. The paper extends leniency to deep multi-agent learning through LDQN and related scheduling and exploration mechanisms.

  • Motivation: MA-DRL faces a moving-target problem because agents’ non-stationary policies make stored experience-replay transitions deprecated.This complicates learning optimal policies in fully cooperative settings.
  • Motivation: Standard HDQN struggles in fully cooperative domains with stochastic rewards, while lenient learners have outperformed hysteretic agents in tabular stochastic games.These findings motivate extending leniency to MA-DRL.
  • Approach: LDQN associates state-action pairs with decaying temperatures that control leniency toward negative policy updates sampled from replay.Temperature decay gradually shifts frequently encountered pairs from optimism toward average-reward learning.
  • Contributions: The paper introduces LDQN with retroactive temperature decay and T(s)-Greedy exploration to sustain exploration until later transitions establish average rewards.It also proposes scheduled-HDQN, which reduces optimism near terminal states.
  • Evaluation: The evaluation extends CMOTP with fully cooperative sub-tasks, stochastic rewards, narrow passages, and noisy observations, comparing LDQN and scheduled-HDQN with standard HDQN.The paper reports empirical evaluation of these methods in challenging coordination tasks.

2 RELATED WORK

Related work addresses coordination in multi-agent reinforcement learning through decentralized learning, hysteretic optimism, and leniency. These approaches differ in their treatment of non-stationarity, stochastic rewards, communication, and convergence behavior.

  • Multi-agent learning: Prior methods include policy-gradient, temporal-difference, and actor-critic approaches evaluated with decentralized parameter sharing and centralized learning.Other work used importance sampling and action-observation histories to identify outdated transitions.
  • Multi-agent learning: The present work avoids maintaining other agents’ action-observation histories and instead studies optimistic agents using implicit coordination.Implicit coordination can reduce reliance on communication protocols, which may be expensive in practical applications.
  • Hysteretic learning: Hysteretic Q-learning uses separate learning rates, with smaller β updates for decreases in state-action values, but tends to perform sub-optimally with stochastic rewards.Its performance in such settings has been attributed to β’s interdependencies with other agents’ exploration strategies.
  • Lenient learning: Lenient learners initially act optimistically before becoming average-reward learners and have converged to superior policies in small-state stochastic games.Lenient methods have also been criticized for slow convergence and difficult hyperparameter selection.

3 BACKGROUND

This section introduces Q-learning and DQNs, then explains why optimistic updates such as hysteretic Q-learning and leniency are useful for cooperative multi-agent learning. It also describes temperature-based leniency, exploration, and state clustering for large observation spaces.

  • Q-Learning: Q-learning estimates discounted future returns for state-action pairs and updates them using temporal-difference targets.The target combines immediate reward with discounted future value, while the learning rate controls the update magnitude.
  • Deep Q-Networks: DQNs approximate Q-values with neural networks trained by sampling stored transitions from an experience replay memory.Double-DQN uses a current network to select the target action and a target network to compute its value, reducing overoptimistic estimates.
  • Hysteretic Q-Learning: Hysteretic Q-learning uses a smaller learning rate for negative updates, producing optimism that emphasizes positive experiences in cooperative settings.Its behavior lies between traditional Q-learning and maximum-based learning, depending on the smaller rate β.
  • Leniency: Leniency initially forgives low-reward outcomes from teammates and decays for repeatedly visited state-action pairs.This optimistic-to-average-reward transition is intended to reduce relative overgeneralization during cooperative exploration.
  • Temperature-Based Exploration: Lenient agents can use average state temperature to influence exploration, becoming more greedy in frequently visited states while continuing to explore elsewhere.Average-temperature folding transfers temperature information from successor actions to the current state-action pair.
  • State Clustering: For high-dimensional observations, an autoencoder and SimHash map semantically similar states to shared temperature keys.The hash granularity is controlled by k, with higher values producing finer clustering.

4 ALGORITHMIC CONTRIBUTIONS

The paper’s algorithmic contributions combine lenient learning with DQNs and introduce mechanisms for temperature handling, exploration, and scheduled hysteretic updates. These mechanisms address premature temperature decay and adapt learning near terminal transitions.

  • Contributions: The authors introduce Lenient-DQN and Scheduled-HDQN as their main algorithmic contributions.Scheduled-HDQN extends hysteretic learning with a scheduled update rate, while LDQN combines leniency with DQN mechanisms.
  • Lenient Deep Q-Network: LDQN stores temperatures for hashed state-action pairs and uses them to determine leniency for replayed transitions.The temperature dictionary is initialized at MaxTemperature and decayed after subsequent encounters with semantically similar states.
  • Temperature Decay Schedule: The retroactive temperature decay schedule applies precomputed decay values at episode termination to prevent premature cooling.It decays early-episode state-action temperatures more slowly than those near terminal transitions.
  • Temperature Decay Schedule: Applying the schedule after failed tasks can repeatedly decay temperatures before difficult subtasks are learned.The paper illustrates this issue with agents requiring many more steps than trained agents to transport a heavy item through a doorway.
  • Lenient Deep Q-Network: T(st)-Greedy exploration replaces ε with average state temperature to control the transition from exploration to exploitation.The greedy action is selected with probability determined by the state temperature and exponent ξ.
  • Scheduled-HDQN: Scheduled-HDQN uses a precomputed learning-rate schedule whose negative-update rate approaches the positive-update rate near terminal transitions.This applies the same slower-early, faster-late scheduling principle used for lenient temperature decay.

5 EMPIRICAL EVALUATION

The evaluation extends CMOTP into larger and more challenging layouts and tests agents using a Double-DQN-based architecture with grid-world image inputs.

  • CMOTP Extensions: The extended CMOTP tasks test coordinated transport across larger layouts and narrow passages.Agents must jointly grasp goods, move in the same direction, and deliver them to a drop-zone.
  • Setup: Agents receive 16 × 16 grayscale grid-world tensors representing agents, goods, and obstacles.The inputs encode entities with distinct pixel values for the two agents, goods, and obstacles.
  • Setup: Evaluations use Double-DQN networks with two convolutional layers, a 1024-neuron fully connected layer, and action-specific output neurons.The same architecture forms the basis for the evaluated algorithms.

6 DETERMINISTIC CMOTP RESULTS

The deterministic CMOTP results show that leniency and hysteresis improve coordination over standard Double-DQN, while temperature-decay scheduling is important in narrow passages.

  • Original CMOTP: Agents with β < 0.8 significantly outperform standard Double-DQN, approaching the optimal 33-step joint policy.LDQN and HDQN configurations were evaluated over 30 runs of 5000 episodes each.
  • Narrow Passage CMOTP: ATF-based lenient agents struggle in narrow passages because temperatures cool rapidly during the first 100 episodes.TDS preserves leniency for roughly the first 1000 episodes, allowing rewards to propagate backward from terminal states.
  • Narrow Passage CMOTP: Only LDQN-TDS and HDQN with β = 0.5 converge to near-optimal joint policies in the narrow-passage CMOTP.HDQN with β > 0.5 struggles to coordinate, while β = 0.5 uses fewer training steps with less overhead.

7 STOCHASTIC CMOTP RESULTS

In stochastic CMOTP experiments, LDQN configurations using T(st)-Greedy exploration achieved the highest optimal-policy convergence, while performance depended strongly on temperature and exploration hyperparameters. Autoencoder-based state representations enabled LDQN-TDS to remain effective under noisy observations.

  • Stochastic CMOTP comparison: 42.5% of HDQN (β = 0.7) runs converged to the optimal policy, compared with 77.5% for scheduled-HDQN and 93% for scheduled-HDQN with a funnel-like passage.The optimal policy delivers goods to dropzone 1 for reward 0.8 rather than dropzone 2 for average reward 0.76.
  • Exploration strategy: 75% of LDQN runs using ϵ-Greedy exploration converged optimally, while T(st)-Greedy reached 100% for K = 3.0, d = 0.9, ξ = 0.25 and µ = 0.9995.The 100% configuration was identified as the best-performing combination in the reported trials.
  • Hyperparameter analysis: The strongest hyperparameter combinations used d = 0.9 or d = 0.95, K = 2 or K = 3, and ξ = 0.25 or ξ = 0.5.These settings maintain high temperatures for early transitions, slow the shift toward average-reward learning, and delay the transition from exploration to exploitation.
  • Hyperparameter analysis: µ = 0.9995 produced optimal-policy convergence on 100% of runs but required an additional 1’674’106 steps on average per run.The slower-decaying temperature caused agents to explore longer and required more time to converge.
  • Noisy observations: LDQN-TDS with an autoencoder converged to the optimal policy on 97.5% of noisy-environment runs, whereas xxhash-based LDQN converged to a sub-optimal policy.The autoencoder introduces additional hyperparameters, including the dense-layer size D and hash-key dimensions K.

8 DISCUSSION & CONCLUSION

The paper concludes that leniency can be applied to MA-DRL to support optimal joint policies in cooperative environments with implicit coordination and stochastic rewards. It also identifies open questions involving prioritized replay, stochastic rewards throughout episodes, and larger agent populations.

  • Open questions: Preliminary LDQN trials with Prioritized Experience Replay converged consistently to a sub-optimal joint policy in the stochastic reward CMOTP.The authors leave investigation of this behavior for future work.
  • Open questions: The reported scope does not establish performance with stochastic rewards throughout episodes or with more than two agents.The authors propose future tests in hunter-prey and four-agent CMOTP scenarios.
  • Main findings: Leniency enabled MA-DRL agents to converge on optimal joint policies in fully cooperative environments requiring implicit coordination and stochastic rewards.The work demonstrated this in a challenging CMOTP with high-dimensional, noisy image observations.
  • Main findings: LDQNs significantly outperformed standard and scheduled-HDQNs in environments with stochastic rewards.The authors report that this replicates findings from tabular settings.
  • Contributions: The paper introduced a retroactive temperature decay schedule and a T(st)-Greedy exploration strategy as extensions to leniency.The extensions are described as applicable in theory to lenient agents outside deep settings.
Loading 1707.04402v2…