PaperlayerView exact revision on arXiv

Source-linked AI summary

Divide-and-Conquer Reinforcement Learning

Dibya Ghosh, Avi Singh, Aravind Rajeswaran, Vikash Kumar, Sergey Levine

arXiv:1711.09874v2cs.LGcs.RO

TL;DR

High variability in initial states can make policy-gradient learning difficult. DnC partitions that variation, trains mutually constrained local policies, and combines them into a global policy. The paper reports that DnC substantially outperforms standard RL and prior ensemble methods, while noting the added complexity of training policy ensembles.

  • Problem

    Wide initial-state distributions produce high-variance policy-gradient estimates that hamper effective learning.

    Source: §1 · p. 1

  • Method

    DnC partitions initial-state variation into contexts, trains local policies constrained to remain coherent with one another, and fits a global policy.

    Source: §1 · p. 1, §4.1 · p. 3

  • Results

    DnC substantially outperforms standard RL methods sampling initial and goal states each trial and previously proposed policy ensembles; standard policy-gradient methods generally fail to find successful solutions in the evaluated domains.

    Source: §8 · p. 9

  • Takeaways & Limitations

    DnC performs well on difficult manipulation and locomotion tasks, including manipulation in low-level torque space without demonstrations or high-level action representations.

    Source: §1 · p. 2

    Training policy ensembles adds complexity, and information sharing is limited to KL-divergence constraints without other explicit representation sharing.

    Source: §8 · p. 9

Abstract

from arXiv · show

Standard model-free deep reinforcement learning (RL) algorithms sample a new initial state for each trial, allowing them to optimize policies that can perform well even in highly stochastic environments. However, problems that exhibit considerable initial state variation typically produce high-variance gradient estimates for model-free RL, making direct policy or value function optimization challenging. In this paper, we develop a novel algorithm that instead partitions the initial state space into "slices", and optimizes an ensemble of policies, each on a different slice. The ensemble is gradually unified into a single policy that can succeed on the whole state space. This approach, which we term divide-and-conquer RL, is able to solve complex tasks where conventional deep RL methods are ineffective. Our results show that divide-and-conquer RL greatly outperforms conventional policy gradient methods on challenging grasping, manipulation, and locomotion tasks, and exceeds the performance of a variety of prior methods. Videos of policies learned by our algorithm can be viewed at http://bit.ly/dnc-rl

1 INTRODUCTION

Realistic reinforcement-learning tasks can vary widely in their initial states and goals, but such variability creates high-variance policy-gradient estimates that hamper learning. Divide-and-conquer RL partitions this variation into slices, trains local policies, and combines them into a global policy; the paper reports improved performance on difficult manipulation and locomotion tasks.

1 INTRODUCTION

  • Wide initial-state distributions, and sometimes wide goal distributions, create high-variance policy-gradient estimates that hamper effective learning.Many standard benchmarks lack the diversity found in realistic environments.Source: §1 · p. 1
  • The method partitions initial-state variation into slices, trains a separate policy for each, then merges them into one global policy.The merger uses mutual KL-divergence constraints and supervised distillation.Source: §1 · pp. 1–2
  • Localizing intermediate policies can improve gradient estimates, while intermediate distillation shares information, accelerates slow learners, and helps avoid local optima.The authors argue this is useful because policies must represent intermediate as well as final learning stages.Source: §1 · p. 2
  • DnC substantially improves performance over prior techniques in evaluations spanning difficult robotic manipulation and locomotion scenarios.The paper presents the algorithm as designed for tasks with substantial diversity and variability.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses diverse behaviors in locomotion and manipulation, but often relies on demonstrations, high-level actions, or simpler tasks. DnC is presented as a way to handle more complex tasks, including low-level torque control and automatically generated initial-state decompositions.

2 RELATED WORK

  • Earlier diverse-behavior methods for locomotion and manipulation often use demonstrations or high-level action representations, whereas DnC handles grasping and catching in low-level torque space without either.The cited prior methods include Osa et al. (2016), Kober et al. (2012), Andrychowicz et al. (2017), Nair et al. (2017), and Rajeswaran et al. (2017a).Source: §2 · p. 2
  • The evaluated tasks are more complex than prior Cartesian-action benchmarks and Popov et al. (2017)'s minimally varied picking setup; DnC also outperforms Heess et al. (2017) in locomotion.Unlike curricula requiring a human-designed progression, DnC permits arbitrary decompositions and automatically generated ones without human intervention.Source: §2 · p. 2
  • Unlike guided policy search, which typically constrains local policies to one central policy, DnC uses flexible neural-network local policies and constrains them to one another.The paper reports that constraining the policies to one another substantially improves performance.Source: §2 · p. 2
  • DnC also resembles Teh et al. (2017) in using nonlinear local policies, but the paper reports substantially better performance when that transfer-learning method is adapted to stochastic initial states.Source: §2 · pp. 2–3

3 PRELIMINARIES

The paper formulates episodic reinforcement learning with contexts that condition the initial-state distribution. This structure provides a way to express variation while ultimately seeking a policy that operates on the underlying MDP state.

3 PRELIMINARIES

  • An episodic MDP is specified by states, actions, transition probabilities, reward, and an initial-state distribution.The paper assumes continuous state and action sets.Source: §3 · p. 3
  • Contexts are finite values sampled jointly with initial states, so sampling can be viewed as choosing a context and then drawing a state conditioned on it.The context-conditioned distribution is distinct from the similarly named contextual MDP formulation of Hallak et al. (2015).Source: §3 · p. 3
  • A context can be embedded as a state variable, but the target policy is defined over the raw MDP state and is intended to need no context information.The objective is to maximize expected trajectory reward.Source: §3 · p. 3

4 DIVIDE-AND-CONQUER REINFORCEMENT LEARNING

DnC uses context to decompose a task into local policy-learning problems, then encourages those policies to generalize across contexts so they can yield a global policy. Its practical algorithm partitions initial states, optimizes mutually constrained local policies, and fits and iteratively refines a central policy.

4.1 LEARNING POLICIES FOR MDPS WITH CONTEXT

  • The framework treats the task as an augmented MDP with context or as context-restricted MDPs with a fixed context.The algorithm derives a contextual policy-learning framework and then provides a practical implementation.Source: §4 · p. 3, §4.1 · p. 3
  • Policies in the augmented MDP correspond to a family of policies for context-restricted MDPs, and the family can induce a central policy in the original MDP.The central policy combines local policies according to a belief over contexts.Source: §4.1 · p. 3
  • Local policies should work beyond their designated contexts, allowing difficult contexts to bootstrap from easier ones and supporting a global policy that operates without context.Source: §4.1 · p. 3
  • The objective rewards local policies while penalizing divergence from a central policy; a Jensen-bound approach replaces the intractable KL optimization with a weighted sum of pairwise local-policy KL terms.The penalty weight α balances expected reward against divergence.Source: §4.1 · pp. 3–4

4.2 THE DIVIDE-AND-CONQUER REINFORCEMENT LEARNING ALGORITHM

  • The practical algorithm partitions sampled initial states into contexts, using k-means in the evaluation, and searches for local policies that maximize contextual reward while remaining mutually constrained.The authors recommend alternative clustering procedures for more intricate stochasticity.Source: §4.2 · p. 4
  • DnC adapts TRPO's surrogate policy-gradient optimization to its reward-and-divergence objective, and the procedure can extend to other policy-gradient methods.TRPO is selected for its practical performance on high-dimensional continuous-control problems.Source: §4.2 · p. 4

4.2 THE DIVIDE-AND-CONQUER REINFORCEMENT LEINFORCEMENT LEARNING ALGORITHM

  • Each local policy is trained on its own context's trajectories but also uses data from other contexts to enforce pairwise KL constraints.The penalties encourage policies to agree on their own contexts and mimic one another on other contexts.Source: §4.2 · p. 4

4.2 THE DIVIDE-AND-CONQUER REINFORCEMENT LEARNING ALGORITHM

  • After a fixed number of trajectory-collection and policy-optimization iterations, the method retrieves a central policy by minimizing KL divergence, equivalent to maximum likelihood on samples from all local policies.If the central policy performs inadequately on the full task, local training restarts from it, and local and global policies are alternately optimized until convergence.Source: §4.2 · p. 5

5 EXPERIMENTAL EVALUATION

The evaluation tests divide-and-conquer RL on challenging manipulation and locomotion tasks, focusing on whether it can solve tasks conventional policy-gradient methods struggle with and how ensemble constraints affect the final policy.

5 EXPERIMENTAL EVALUATION

  • The study evaluates manipulation and locomotion tasks designed to expose complex, contact-rich behaviors under considerable variation, using MuJoCo simulations.The authors describe standard continuous-control benchmarks as relatively mild representational challenges.Source: §5 · p. 5
  • The experiments ask whether DnC can solve complex tasks that conventional policy-gradient methods cannot, and how ensemble constraints affect final-policy performance.Source: §5 · p. 5
  • Comparisons include TRPO, adapted Distral, unconstrained DnC, and centralized DnC, which uses an oracle to identify context.Distral constrains policies against a supervised global policy and omits DnC’s periodic distillation; centralized DnC distills every R steps.Source: §5 · pp. 5–6
  • Each task’s initial-state space is partitioned into four k-means contexts, and experiments use five random seeds with hyperparameter sweeps for the penalty weight.The authors report mean statistics and standard deviations because policy-gradient performance varies between runs.Source: §5 · p. 6

6 ROBOTIC MANIPULATION

Across the manipulation tasks, DnC outperforms alternative methods, while standard TRPO fails to achieve high success. The results highlight gains over ablations and adapted Distral, with task-specific differences in performance.

6 ROBOTIC MANIPULATION

  • DnC outperforms alternative methods on all manipulation tasks, while TRPO’s success rate remains below 10% on each task.Figure 1 reports average return and success-rate learning curves for the global policy distilled from local policies.Source: §6 · p. 6, Figure 1 · p. 7
  • 16% higher success rate: DnC exceeds the next-best ablated variant on Picking, and places the Lobbing object three times closer to the goal than other methods.The authors report that pairwise KL penalties and periodic resets appear crucial to performance.Source: §6 · p. 8
  • On Catching, DnC variants distilled every 100 iterations perform well while Distral lags, with its unstable grasp attributed to an awkward ball-catching orientation.The authors link Distral’s failure to escape this local optimum to its lack of distillation and local-policy resets.Source: §6 · p. 8

7 LOCOMOTION

In locomotion, DnC performs on par with or better than alternatives. The results also show reduced sample complexity on Ant and context-specific gait behavior on Stairs.

7 LOCOMOTION

  • 400 million samples: TRPO solves Ant only at that sample count, while DnC variants solve it with one-tenth the sample complexity.Source: §7 · p. 8
  • DnC performs on par with or better than the alternatives on each locomotion task.Source: §7 · p. 8
  • On Stairs, DnC separates context updates to limit stronger short-stair rewards from affecting other contexts, and learns striding and jumping gaits that share structure.Other partitioning algorithms learn hopping motions that work on tall stairs but are suboptimal on shorter ones.Source: §7 · p. 9

8 DISCUSSION AND FUTURE WORK

DnC learns separate policies for local tasks and constrains them into a globally coherent policy. The approach improves on standard RL and prior ensemble methods, but requires training policy ensembles.

8 DISCUSSION AND FUTURE WORK

  • DnC separates complex tasks into local tasks, learns a policy for each, and constrains the policies to form a globally coherent solution usable from any initial state.Source: §8 · p. 9
  • Experiments report substantial improvement over standard RL methods that sample initial and goal states each trial, as well as previously proposed policy ensembles.Standard policy-gradient methods generally fail to find successful solutions in the evaluated domains.Source: §8 · p. 9
  • Training an ensemble of policies adds complexity, and the method shares information through KL constraints without explicit representation sharing.The authors identify reducing computational burden and improving representation sharing as future directions.Source: §8 · p. 9

A EXPERIMENTAL DETAILS

The experiments use a shared TRPO objective and adjust simulation samples for TRPO to match the partition-based methods. Policies use a three-layer neural network with learned diagonal covariance; learning rates and penalties are selected per task.

A EXPERIMENTAL DETAILS

  • TRPO receives B×N simulation timesteps per policy update, matching the total used by DnC's N local policies, each using B timesteps.All methods use the TRPO objective; Distral is ported from soft Q-learning to TRPO.Source: A EXPERIMENTAL DETAILS · p. 11
  • The stochastic policy mean uses a neural network with 150, 100, and 50 hidden units, while its learned diagonal covariance starts at the identity matrix.The network has three hidden layers.Source: A EXPERIMENTAL DETAILS · p. 11
  • For each task, the learning rate and each method's penalty are selected from five tested values, with results averaged over five random seeds and reported with standard deviations.The learning-rate candidates are .0025, .005, .01, .02, and .04; penalties are tuned separately for DnC, Centralized DnC, and Distral.Source: A EXPERIMENTAL DETAILS · p. 11

B TASK DESCRIPTIONS

The paper describes manipulation and locomotion tasks with varied initial or target conditions, then evaluates how automated initial-state partitions affect DnC. Four contexts perform best or nearly best across all tasks, balancing gradient-noise reduction with information sharing.

B TASK DESCRIPTIONS

  • Jaco tasks use seven-dimensional low-level joint-torque actions at 20 Hz, and target distances are normalized by their initial values.Picking randomizes the box over a 30 cm by 30 cm tabletop and rewards lifting it within 8 cm of the end-effector; lobbing randomizes targets over a 1 m by 1 m square, while catching randomizes catchable ball positions and velocities.Source: B TASK DESCRIPTIONS · p. 12
  • Ant Position randomizes targets on a circle of radius 5 m, while Stairs randomizes stair heights from 5 to 25 cm and lengths from 50 to 60 cm.The stairs task provides terrain heights at 25 points spanning 0.5 m behind to 1 m ahead of the robot; its reward weighs forward velocity and torque magnitude.Source: B TASK DESCRIPTIONS · p. 12

C AUTOMATED PARTITIONING

  • DnC partitions 10,000 sampled initial states with K-means and assigns each state to its nearest cluster center; the comparison tests two, four, and eight contexts plus a manual four-context grid.The manual grid follows axes of stochasticity; sample complexity is held constant across variants.Source: C AUTOMATED PARTITIONING · p. 13
  • K-means partitions are sensitive to relative state scaling, but the authors report that they produced sensible partitions on all benchmark tasks.For two contexts, each local policy uses twice as many samples as in the four-context condition.Source: C AUTOMATED PARTITIONING · p. 13
  • Four-context DnC is best or closely matches the best method on every task, balancing smaller contexts against information sharing among similar states.Two contexts retain noisy-gradient challenges, while eight create a representation-sharing bottleneck through the KL constraint.Source: C AUTOMATED PARTITIONING · p. 13
  • The automated-partitioning plots report average return for Picking, Lobbing, Ant, and Stairs, and success rate for Catching.These panels identify the task-specific evaluation measures, without supplying numerical outcomes in the provided passages.Source: C AUTOMATED PARTITIONING · p. 13

D ORACLE-BASED ABLATIONS

Oracle-based ablations compare the final global policy with an ensemble of local policies and test removing periodic distillation. The reported results show little loss in transferring to a global policy on most tasks, while distillation improves performance on three tasks and matches the variant on two.

D ORACLE-BASED ABLATIONS

  • The final global policy loses little performance relative to the oracle-selected ensemble of final local policies on most tasks.The comparison uses the final local policies instead of the resulting global policy as the ensemble output.Source: D ORACLE-BASED ABLATIONS · p. 14
  • DnC significantly outperforms the no-distillation variant on three tasks and has equivalent performance on the other two.The authors hypothesize that distillation helps local policies adjust out of local minima.Source: D ORACLE-BASED ABLATIONS · p. 14
Loading 1711.09874v2…