PaperlayerView exact revision on arXiv

Source-linked AI summary

Hindsight policy gradients

Paulo Rauber, Avinash Ummadisingu, Filipe Mutz, Juergen Schmidhuber

arXiv:1711.06006v3cs.LGcs.AIcs.NEcs.RO

TL;DR

Sparse-reward environments challenge reinforcement-learning agents because they may rarely receive reward for reaching a desired goal. This paper introduces importance-sampling-based hindsight policy gradients to learn about alternative goals from trajectories collected for another goal. The estimators show remarkable sample efficiency across a diverse selection of sparse-reward environments.

  • Problem

    Sparse-reward environments challenge reinforcement-learning algorithms because agents may rarely obtain reward signals when reaching a desired goal by chance is unlikely.

    Source: §1 · p. 1

  • Method

    The paper introduces hindsight policy gradients that use importance sampling to learn about alternative goals from trajectories collected while pursuing another goal.

    Source: §1 · p. 2, §4 · p. 3

  • Results

    Hindsight policy-gradient estimators show remarkable sample efficiency compared with conventional goal-conditional policy-gradient estimators across diverse sparse-reward environments.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A reported estimator variant supports natural task formulations requiring only trivial reward shaping, especially when direct reward signals are extremely difficult to obtain.

    Source: §7 · p. 9

    The main drawback is computational cost, which is directly related to the number of active goals in a batch.

    Source: §7 · p. 9

Abstract

from arXiv · show

A reinforcement learning agent that needs to pursue different goals across episodes requires a goal-conditional policy. In addition to their potential to generalize desirable behavior to unseen goals, such policies may also enable higher-level planning based on subgoals. In sparse-reward environments, the capacity to exploit information about the degree to which an arbitrary goal has been achieved while another goal was intended appears crucial to enable sample efficient learning. However, reinforcement learning agents have only recently been endowed with such capacity for hindsight. In this paper, we demonstrate how hindsight can be introduced to policy gradient methods, generalizing this idea to a broad class of successful algorithms. Our experiments on a diverse selection of sparse-reward environments show that hindsight leads to a remarkable increase in sample efficiency.

1 INTRODUCTION

Sparse-reward tasks make learning difficult because agents may rarely receive rewards, even though they can learn about visited goals while pursuing another. The paper introduces importance-sampling-based hindsight policy gradients and reports remarkable sample efficiency across sparse-reward environments.

1 INTRODUCTION

  • Sparse-reward environments are challenging because an agent may rarely receive reward when reaching its desired goal by chance is unlikely.The introduction notes that agents can be expected to learn to reach visited cities regardless of their intended destination.Source: §1 · pp. 1–2
  • Hindsight is the capacity to use information about how much an arbitrary goal was achieved while another goal was intended.Earlier work introduced it for off-policy reinforcement learning with experience replay and for policy search based on Bayesian optimization.Source: §1 · p. 2
  • The paper demonstrates how hindsight can be introduced to policy-gradient methods, extending it to a successful class of reinforcement-learning algorithms.Source: §1 · p. 2
  • Importance sampling lets the approach use information from the current policy for one goal to learn about different goals, yielding multiple formulations related to established policy-gradient results.Source: §1 · p. 2
  • Hindsight policy-gradient estimators show remarkable sample efficiency compared with conventional goal-conditional policy-gradient estimators across sparse-reward environments.The paper reports this result on a diverse selection of environments.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries define episodes with goals, states, rewards, and actions, and formalize goal-conditional policies and trajectory probabilities. They assume transitions are goal-independent and define expected return as the policy objective.

2 PRELIMINARIES

  • The notation uses uppercase letters for random variables, lowercase letters for assignments, and Val(X) for the valid assignments to X.Source: §2 · p. 2
  • Each episode has a goal, state observations, rewards, and actions; a goal-conditional policy assigns action probabilities for each state and goal and is reused at every time step.Source: §2 · p. 2
  • A trajectory’s probability conditioned on its goal and policy parameters is specified, with state-transition probabilities independent of the pursued goal.The formulation allows transition probabilities to vary across time steps and assumes trajectory probabilities are non-zero and differentiable with respect to policy parameters.Source: §2 · p. 2
  • The expected return of the policy is defined under the assumption that goals and policy parameters are independent.Source: §2 · p. 2

3 GOAL-CONDITIONAL POLICY GRADIENTS

This section establishes goal-conditional policy-gradient results analogous to conventional policy-gradient methods. It presents the expected-return gradient and its baseline and advantage formulations.

3 GOAL-CONDITIONAL POLICY GRADIENTS

  • The goal-conditional policy gradient gives a gradient-based route to finding policy parameters that maximize expected return.Source: §3 · p. 3
  • A baseline formulation can reduce the variance of the gradient estimator; the typical baseline function may depend on state and goal.Constant baselines that minimize estimator variance are usually impractical to compute or estimate, and a state- and goal-dependent baseline is generally suboptimal.Source: §3 · p. 3
  • The advantage formulation provides a goal-conditional policy-gradient result for actor-critic methods.Source: §3 · p. 3

4 HINDSIGHT POLICY GRADIENTS

The section introduces hindsight policy gradients, using importance sampling to evaluate trajectories collected for one goal under alternative goals. It develops per-decision, baseline, and advantage formulations.

4 HINDSIGHT POLICY GRADIENTS

  • When rewards are known for every state-goal combination, importance sampling permits evaluating a trajectory collected for one goal under an alternative goal.Source: §4 · p. 3
  • The every-decision formulation weights each reward by the full trajectory likelihood ratio, while the per-decision formulation uses a ratio covering the trajectory only up to the previous action.Source: §4 · pp. 3–4
  • A baseline lemma supports hindsight policy-gradient baselines, and a particular likelihood-ratio choice also underlies the advantage formulation.The authors suggest a baseline function by analogy with conventional practice; the likelihood-ratio choice is not unique.Source: §4 · p. 4
  • An advantage under one goal can be approximated using a state transition collected while pursuing another goal.Source: §4 · p. 4

5 HINDSIGHT GRADIENT ESTIMATORS

The section presents per-decision hindsight gradient estimators, including a consistent and unbiased estimator and a weighted variant intended to trade variance for bias. It also describes when goal expectations can be computed exactly and how arbitrary goal datasets may be used under additional assumptions.

5 HINDSIGHT GRADIENT ESTIMATORS

  • The per-decision hindsight policy gradient estimator is consistent and unbiased for the expected-return gradient.The weighted per-decision estimator is introduced as an attempt to trade variance for bias after preliminary experiments found unstable learning progress with the unweighted estimator, probably due to high variance.Source: §5 · p. 4
  • The weighted estimator normalizes each trajectory–alternative-goal–time-step likelihood ratio across trajectories.A consistency-preserving weighted baseline is also described.Source: §5 · p. 5
  • Only active goals contribute nonzero terms to the estimators’ expectation over goals.In many natural sparse-reward environments, active goals correspond to visited states, allowing exact computation of that expectation when the goal distribution is known.Source: §5 · p. 5
  • For the weighted estimators, only likelihood ratios for active goals affect the gradient estimate, and the original goal’s unnormalized ratios are one for its episode.For policies with strong optimal substructure, a trajectory reaching one goal through another state may also have high probability for the corresponding subgoal.Source: §5 · p. 5
  • Under mild additional assumptions, the estimators can use datasets with arbitrarily chosen goals instead of goals drawn from the goal distribution.The authors suggest this may help circumvent catastrophic forgetting during curriculum learning, but their experiments do not require this feature.Source: §5 · p. 5

6 EXPERIMENTS

The experiments compare goal-conditional and hindsight policy-gradient estimators across diverse sparse-reward environments. HPG often improves sample efficiency, though outcomes and stability vary by environment and estimator.

6 EXPERIMENTS

  • The comparison spans diverse sparse-reward environments and assesses sample efficiency with learning curves and average returns across evaluation steps and runs.Hyperparameters are selected by grid search, followed by definitive runs at small and medium batch sizes.Source: §6 · pp. 5–6
  • The experimental HPG variants do not precisely implement Expression 12: they may subsample active goals, and HPG+B uses an inconsistent estimator when its baseline considers only active goals.The authors report that these compromises still yield remarkable sample efficiency.Source: §6 · pp. 5–6

6.1 BIT FLIPPING ENVIRONMENTS

  • For k = 16 bit flipping, HPG learns stably and sample-efficiently, while GCPG and GCPG+B fail to outperform chance; HPG+B policies deteriorate with more training.For k = 8, HPG obtains excellent policies as early as HPG+B while remaining stable with additional training; HPG+B reaches them more than 400 batches before GCPG variants but later degrades.Source: Figure 5 · p. 6, §6.1 · pp. 6–7, Figure 4 · p. 6

6.2 GRID WORLD ENVIRONMENTS

  • The grid-world tasks use an 11 × 11 grid with a 32-step limit; four rooms adds walls, single-door connections, and a 0.2 probability of an ignored action.In the empty room, the agent starts in the upper-left corner; in four rooms, it starts in a corner chosen each episode.Source: §6.2 · p. 7
  • In grid worlds, HPG and HPG+B improve sample efficiency; all estimators achieve excellent policies in the empty room but unsatisfactory policies in four rooms.HPG+B is not unstable in these experiments, which the authors attribute to easier value-function estimation.Source: Figure 6 · p. 7, Figure 7 · p. 7, §6.2 · p. 7

6.3 MS. PAC-MAN ENVIRONMENT

  • In Ms. Pac-man, HPG performs better early, but GCPG achieves better final policies with medium batches when HPG subsamples 3 of up to 28 active goals.With a small batch size and all active goals, HPG outperforms GCPG.Source: Figure 8 · p. 8, §6.3 · p. 8

6.4 FETCHPUSH ENVIRONMENT

  • In FetchPush, HPG learns good policies after a reasonable number of batches, unlike GCPG; subsampling 3 active goals per episode is viable there.The environment has up to 50 potential active goals; similar results occur with a small batch size using all active goals.Source: Figure 9 · p. 8, §6.4 · p. 8

7 CONCLUSION

The conclusion presents hindsight policy gradients as a way to learn goal-conditional policies beyond earlier hindsight approaches limited to replay-based off-policy learning and Bayesian-optimization policy search. It reports comparative sample efficiency across sparse-reward environments, while noting computational cost and other open questions.

7 CONCLUSION

  • The paper introduces hindsight techniques for goal-conditional policies, extending beyond earlier approaches limited to replay-based off-policy algorithms and Bayesian-optimization policy search.Hindsight is the capacity to use information about how far an arbitrary goal was achieved while another goal was intended.Source: §7 · p. 9
  • A variant of the consistent hindsight policy-gradient estimator shows remarkable comparative sample efficiency across sparse-reward environments, especially when direct reward signals are extremely difficult to obtain.The authors say this supports natural task formulations requiring only trivial reward shaping.Source: §7 · p. 9
  • Hindsight policy-gradient estimators incur computational cost directly related to the number of active goals in a batch.Subsampling active goals may mitigate this cost but generally leads to inconsistent estimators; experiments suggest it can be viable.Source: §7 · p. 9
  • The authors identify further work on estimator variance, active-goal subsampling, continuous action spaces, and evaluating the techniques on dense-reward environments.They also list actor-critic implementations, curriculum learning, and reward approximation among future directions.Source: §7 · p. 9

A GOAL-CONDITIONAL POLICY GRADIENTS

  • Appendix A collects proofs for results from Section 3, including the goal-conditional policy-gradient theorem and auxiliary results.It also presents optimal constant baselines for goal-conditional policies.Source: A GOAL-CONDITIONAL POLICY GRADIENTS · p. 13

A.1 THEOREM A.1

  • Theorem A.1 concerns the gradient of expected return, and its proof invokes the likelihood-ratio trick to rewrite the derivative.The supplied appendix passage gives the theorem’s topic and proof step, but not the displayed formula.Source: §A.1 · p. 13

A.2 THEOREM 3.1

The appendix states goal-conditional policy-gradient results and their baseline and advantage formulations, then develops hindsight versions using importance sampling. It distinguishes every-decision and per-decision estimators and includes corresponding baseline, action-value, and advantage formulations.

A.2 THEOREM 3.1

  • Theorem 3.1 states a goal-conditional policy-gradient result for the gradient of expected return.The supplied passage identifies the theorem but does not include its displayed formula.Source: §A.2 · p. 13

A.4 THEOREM 3.2

  • Theorem 3.2 gives a baseline formulation of the goal-conditional policy gradient, with the proof obtained by subtracting the baseline-related result.The proof passage notes that a distinct baseline could be used for each parameter and time step.Source: §A.4 · p. 14

A.6 THEOREM 3.3

  • Theorem 3.3 states an advantage formulation of the goal-conditional policy gradient.The supplied passage identifies the formulation but does not include its displayed formula.Source: §A.6 · p. 15

B HINDSIGHT POLICY GRADIENTS

  • The hindsight results use importance sampling to state an every-decision estimator and a separate per-decision estimator for an arbitrary original goal.The supplied theorem passages distinguish these two estimator formulations.Source: §B.1 · p. 16, §B.2 · p. 16
  • The appendix also states hindsight baseline, action-value, and advantage formulations for an arbitrary original goal.The baseline theorem permits a distinct baseline for each parameter and time step.Source: §B.4 · p. 18, §B.5 · p. 18, §B.6 · p. 18

B.7 THEOREM B.2

This material states an optimal constant-baseline result and gives guarantees for the per-decision hindsight policy-gradient estimator. The estimator is unbiased and consistent for the expected-return gradient.

B.7 THEOREM B.2

  • When Var[h(T) | g′, θ] > 0, Theorem B.2 identifies the constant baseline minimizing the variance of f(T) − b_jh(T).The supplied passages state the minimizing objective and condition, but do not include the formula for b_j.Source: §B.7 · p. 19

C HINDSIGHT GRADIENT ESTIMATORS

C.1 THEOREM 5.1

  • The per-decision hindsight policy-gradient estimator is a consistent and unbiased estimator of the expected-return gradient.Source: §C.1 · p. 20

C.2 THEOREM 5.2

Theorem 5.2 develops a weighted per-decision hindsight estimator, with its proof analyzing convergent numerator and denominator terms. The following theorem supplies a weighted baseline result that can be combined with it.

C.2 THEOREM 5.2

  • Theorem 5.2 analyzes the weighted per-decision hindsight estimator through convergent numerator and denominator terms and the policy-gradient identity.Source: §C.2 · pp. 20–22

C.3 THEOREM C.1

  • The weighted baseline result is designed to preserve consistency and can be used in combination with Theorem 5.2.The proof notes that the baseline term converges almost surely to zero.Source: §C.3 · p. 22

D FUNDAMENTAL RESULTS

The appendix collects probability and variance results used by the paper’s hindsight-gradient estimators, then documents the experimental setup and network representations. Its supporting results include trajectory factorizations, an action-value identity, and a variance-minimizing baseline.

D FUNDAMENTAL RESULTS; E EXPERIMENTS

D.1 LEMMA D.1; D.2 LEMMA D.2

  • The proof uses backward induction starting at t = T−1 and expresses conditional future-trajectory probabilities via the full trajectory’s joint probability and policy and state-transition factors.Source: §D.1 · p. 23, §D.2 · p. 23

D.3 LEMMA D.3; D.4 THEOREM 4.4

  • Lemma D.3 uses transition independence from goals and policy parameters, and Theorem 4.4 follows from the advantage definition and Lemma D.3.Source: §D.3 · p. 24, §D.4 · p. 24

D.5 LEMMA D.4

  • Lemma D.4 gives the constant b that minimizes Var[f(X) − bh(X)] when E[h(X)] = 0 and Var[h(X)] > 0.Source: §D.5 · pp. 24–25

E.1 POLICY AND BASELINE REPRESENTATIONS

  • Policies take state-goal pairs as input and use softmax outputs; baselines take state, goal, and time step and use a single linear output, with Adam updates.The baseline is trained toward the value function using mean squared one-step temporal-difference error.Source: §E.1 · p. 26
  • Bit-flipping and grid-world networks use two 256-unit tanh hidden layers, Ms. Pac-man uses a convolutional network, and FetchPush uses three 256-unit tanh hidden layers.Source: §E.1 · p. 26

E.2 EXPERIMENTAL SETTINGS

The appendix reports cross-environment comparisons of hindsight methods, alongside experimental settings, performance summaries, and analyses of active likelihood ratios. The results vary by environment: HPG and DQN+HER each lead in some tasks, while applying hindsight is reported as consistently successful.

E.2 EXPERIMENTAL SETTINGS

  • Experimental settings report separate search and definitive-run counts, adapt training duration to apparent convergence, and use 100 total evaluation steps.Source: §E.2 · p. 26

E.3 RESULTS; E.3.1 HYPERPARAMETER SENSITIVITY PLOTS (BATCH SIZE 2); E.3.2 HYPERPARAMETER SENSITIVITY PLOTS (BATCH SIZE 16); E.3.3 LEARNING CURVES (BATCH SIZE 2); E.3.4 LEARNING CURVES (BATCH SIZE 16); E.3.5 AVERAGE PERFORMANCE RESULTS

  • The appendix includes sensitivity plots, learning curves for each environment and batch size, and a table of definitive average performance results.The sensitivity plots sort settings from best to worst; the supplied table passage gives its scope but no cell values.Source: §E.3 · p. 29, §E.3.5 · p. 32, Table 3 · p. 33

E.3.6 LIKELIHOOD RATIO PLOTS

  • The likelihood-ratio study plots distributions of active normalized ratios by episode time for each environment’s best-performing HPG agent.Ratios are active only when multiplying a non-zero reward; their behavior differs across environments, while changing slowly over time after the first step within an environment.Source: §E.3.6 · p. 34

E.3.7 HINDSIGHT EXPERIENCE REPLAY

  • In bit flipping, at k = 8, HPG and DQN+HER have equivalent sample efficiency, GCPG lags far behind, and DQN cannot learn; at k = 16, HPG leads DQN+HER by a small margin, and neither GCPG nor DQN can learn.Source: §E.3.7 · p. 36
  • In empty room, HPG is arguably most sample efficient, while DQN+HER is more stable after a good policy; in four rooms, DQN+HER outperforms all others by a large margin.Source: §E.3.7 · pp. 36–37, Figure 42 · p. 38, Figure 43 · p. 38
  • DQN+HER outperforms all methods in Ms. Pac-man, whereas HPG dramatically outperforms all methods in FetchPush; active goals are harshly subsampled in both tasks for HPG efficiency.Source: §E.3.7 · p. 37, Figure 44 · p. 38, Figure 45 · p. 38
  • The comparison concludes that choosing HPG versus DQN+HER requires experimentation by environment, while applying hindsight was always successful.Source: §E.3.7 · p. 37
  • The discussion says HPG may benefit from state-of-the-art policy-gradient extensions, and that omitted performance heuristics could help both GCPG and HPG in four rooms and Ms. Pac-man.Source: §E.3.7 · p. 37
Loading 1711.06006v3…