PaperlayerView exact revision on arXiv

Source-linked AI summary

AlgaeDICE: Policy Gradient from Arbitrary Experience

Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, Dale Schuurmans

arXiv:1912.02074v1cs.LGcs.AI

TL;DR

Limited environment interaction makes on-policy reinforcement learning impractical because max-return optimization depends on on-policy expectations. AlgaeDICE reformulates the objective using arbitrary off-policy data and auxiliary dual variables. When optimized, these variables yield the exact on-policy policy gradient without importance weighting, while practical results are roughly competitive with SAC and TD3.

  • Problem

    Costly or infeasible environment interaction limits access to on-policy samples required by traditional max-return reinforcement learning methods.

  • Method

    AlgaeDICE derives a regularized and then Lagrangian off-policy max-return formulation using arbitrary behavior-agnostic data and auxiliary dual variables.

  • Results

    Optimizing the auxiliary dual variables makes the off-policy objective’s gradient exactly equal to the on-policy policy gradient without importance weighting.

  • Takeaways & Limitations

    AlgaeDICE automatically compensates for distribution shift and supports behavior-agnostic off-policy policy improvement, with performance roughly competitive with SAC and TD3.

  • Takeaways & Limitations

    The Lagrangian’s linear structure can induce numerical instability in practice.

Abstract

from arXiv · show

In many real-world applications of reinforcement learning (RL), interactions with the environment are limited due to cost or feasibility. This presents a challenge to traditional RL algorithms since the max-return objective involves an expectation over on-policy samples. We introduce a new formulation of max-return optimization that allows the problem to be re-expressed by an expectation over an arbitrary behavior-agnostic and off-policy data distribution. We first derive this result by considering a regularized version of the dual max-return objective before extending our findings to unregularized objectives through the use of a Lagrangian formulation of the linear programming characterization of Q-values. We show that, if auxiliary dual variables of the objective are optimized, then the gradient of the off-policy objective is exactly the on-policy policy gradient, without any use of importance weighting. In addition to revealing the appealing theoretical properties of this approach, we also show that it delivers good practical performance.

1 Introduction

Off-policy reinforcement learning is needed when environment interaction is costly, but standard policy-gradient and value-based objectives still depend on on-policy information. AlgaeDICE reformulates max-return optimization around arbitrary off-policy data.

  • Limited or infeasible environment interaction motivates learning from logged experience generated by unknown or multiple behavior policies.
  • Standard policy-gradient methods require on-policy samples, while importance weighting can introduce high variance and instability.
  • Function-approximation value methods use Bellman-error expectations whose appropriate data distribution remains theoretically tied to the on-policy distribution.
  • AlgaeDICE introduces policy-gradient optimization from arbitrary experience as an alternative to policy-gradient and value-based methods.
  • DICE denotes distribution correction estimation, although AlgaeDICE focuses on policy optimization and only implicitly estimates distribution corrections.
  • The method combines a controllable regularizer with a change of variables to form a policy-and-critic objective using arbitrary off-policy samples.

2 Background

The background formulates reinforcement learning as an MDP and relates policy performance to value functions, visitation distributions, and policy gradients. It highlights that both policy-gradient and actor-critic approaches require on-policy information despite off-policy data availability.

  • An MDP comprises states, actions, rewards, transitions, and an initial-state distribution, with a policy generating actions and receiving rewards over time.
  • The max-return objective can be expressed through the policy’s normalized state-action visitation distribution, which is dual to a linear-programming formulation.
  • The policy-gradient theorem expresses the gradient as an expectation under dπ involving Qπ(s, a) and ∇log π(a|s).
  • Estimating this gradient requires on-policy samples and Q-value estimates, making repeated environment interaction necessary for gradient estimation.
  • The Bellman equation defines Qπ through immediate reward plus discounted future value under the transition dynamics and policy.
  • Although Bellman-error objectives may use an arbitrary distribution β, compatible function approximation theory points to the on-policy distribution dπ.
  • The off-policy setting assumes a dataset of transitions with actions sampled by an unknown process and access to initial-state samples.

3 AlgaeDICE via Density Regularization

AlgaeDICE reformulates max-return optimization with a regularized off-policy objective and auxiliary dual variables. After optimizing the dual function, its gradient recovers the regularized on-policy policy gradient without explicit importance weighting.

  • Regularized off-policy objective: A change of variables based on a Bellman fixed point removes on-policy expectations, yielding an objective that uses only initial-state and off-policy dataset samples.The transformation defines ν through ν(s, a) := −α · x(s, a) + Bπν(s, a), with x(s, a) = (Bπν −ν)(s, a)/α.
  • Regularized off-policy objective: Under mild conditions, the regularized max-return objective has a max-min formulation over the policy and dual function ν.The paper also notes that strong duality can support rearranging the inner min-max form of a more practical objective.
  • Regularized off-policy objective: The authors regularize the on-policy max-return objective with an f-divergence to an off-policy dataset distribution dD, then express it variationally through a dual function.The regularizer encourages policy occupancies to remain close to dD while enabling subsequent off-policy derivations.
  • Practical considerations: The Fenchel formulation faces a double-sampling challenge because Bπ requires an expectation over transitions while data typically provide one empirical transition sample per state-action pair.The paper states that this issue can prevent finding the desired value function even with infinite data.
  • Consistent policy gradient: When ν is optimized, the gradient of the off-policy objective is the regularized on-policy policy gradient, with ν* serving as the Q-value function for an augmented reward.Danskin’s theorem permits ignoring policy gradients through the optimized dual function.
  • Connection to actor-critic: With a quadratic convex function f, the objective resembles actor-critic while unifying policy and value training under one off-policy objective.The first term transforms the off-policy actor-critic interpretation into an on-policy actor-critic without explicit importance weights.

4 A Lagrangian View of AlgaeDICE

The section derives AlgaeDICE from the Lagrangian of the linear-programming characterization of Qπ, yielding a regularized saddle-point objective over arbitrary data. This formulation simultaneously recovers Q-values and state-action distribution corrections, and extends to unregularized and undiscounted settings.

  • LP characterization: The LP formulation expresses a policy’s average return in primal and dual forms, with Bellman inequalities constraining ν and optimal dual variables recovering occupancy-related quantities.For reachable state-action pairs, the optimal primal solution corresponds to Qπ.
  • Lagrangian derivation: AlgaeDICE is derived by reparametrizing the dual variable as ζ(s,a)=ρ(s,a)dD(s,a), expressing the Lagrangian under the data distribution dD.The resulting saddle-point objective combines an initial-state term with Bellman-constraint terms averaged over dD.
  • Lagrangian derivation: Adding the convex regularizer α·EdD[f(ζ(s,a))] produces the regularized primal-dual objective used to characterize AlgaeDICE.The regularized Lagrangian is optimized over bounded primal variables ν and nonnegative dual variables ζ.
  • Optimization properties: The regularized solution recovers the target correction wπ/D as the optimal dual variable, while the optimal value is characterized through the regularized objective.The derivation connects the Lagrangian solution to the Fenchel and primal AlgaeDICE objectives.
  • Optimization properties: Strong duality permits optimization over bounded function spaces when the optimal solution lies within them, supporting computational optimization of the policy through the Lagrangian objective.The boundedness conditions concern wπ/D and the reward function.
  • Extensions: The Lagrangian view extends AlgaeDICE to α=0 and γ=1, and its LP form also supports behavior-agnostic off-policy evaluation through regularized primal and dual variables.Different Lagrangian regularizations recover existing behavior-agnostic OPE estimators while providing Q-values and corrections simultaneously.

5 Related Work

Related work includes saddle-point and regularized reinforcement-learning methods, as well as off-policy policy-gradient approaches based on distribution correction. AlgaeDICE differs by using a single unified objective and by being behavior-agnostic.

  • Saddle-point methods: Prior saddle-point formulations for policy improvement use different perspectives, including multi-step consistency conditions between optimal value functions and policies.These approaches are distinguished from AlgaeDICE by their derivational basis.
  • Regularization: Regularization has been used in reinforcement learning for exploration, smoothing, and related purposes, while f-divergence regularization is especially close in spirit to AlgaeDICE.The cited prior approach differs in objective structure and optimization procedure.
  • Unified optimization: AlgaeDICE uses a single unified objective for both policy and value learning, unlike the separate objectives and bi-level optimization described for related methods.This is presented as a key distinction from prior regularized approaches and explicit distribution-correction methods.
  • Distribution correction: Eligibility-trace corrections can suffer from high variance as trajectory length increases, a difficulty described as the curse of horizon.These methods compute corrections by multiplying per-action importance weights over a trajectory.
  • Distribution correction: AlgaeDICE implicitly estimates state-action distribution corrections within a unified objective and does not require knowledge of the behavior policy.The contrast is with related methods that explicitly estimate corrections or require behavior-policy information.

6 Experiments

Experiments evaluate AlgaeDICE first in tabular Four Rooms and then on continuous-control benchmarks, using fixed offline data and neural-network optimization. The results show distribution correction in Four Rooms and roughly competitive continuous-control performance, while practical design choices remain open.

  • Experiments cover Four Rooms and continuous-control benchmarks from MuJoCo and OpenAI Gym.
  • Four Rooms: A fixed offline dataset of 500 uniformly random-policy trajectories is used in Four Rooms, with random initial states and length-10 trajectories.Training solves ν by matrix operations and updates π with gradient steps, using α = 0.01 and γ = 0.97.
  • Four Rooms: As training progresses, Bellman residuals form paths from initial to target states, while learned actions identify preferred trajectories.The residual patterns are interpreted through the ratios w_π/D and show correction for distribution shifts.
  • Four Rooms: AlgaeDICE improves over the offline behavior-policy baseline with average reward 0.03, and its performance is only negligibly affected by dataset type.Actor-critic performance degrades in the offline regime, whereas all variants significantly improve on the behavior-policy baseline.
  • Continuous Control: Continuous-control experiments parameterize π and ν with neural networks and use alternating stochastic gradient descent.The empirical objective uses a single-sample Bellman-residual estimate, with entropy regularization, target-value mixing, and lower clipping of δ in policy gradients.
  • Continuous Control: AlgaeDICE performs roughly competitively with SAC and TD3, while polynomial choices of f sometimes improve performance beyond f(x) = 1^2x^2.A systematic study of these and other implementation choices is left for future work.

7 Conclusion

The conclusion presents AlgaeDICE as a behavior-agnostic, off-policy policy-improvement method and summarizes its empirical comparisons. It reports Four Rooms evaluation against actor-critic and continuous-control results against SAC, TD3, and DDPG.

  • Figure 2 compares average per-step reward for AlgaeDICE and actor-critic on Four Rooms over training iterations.
  • AlgaeDICE is introduced for behavior-agnostic, off-policy policy improvement in reinforcement learning.
  • Figure 3 compares AlgaeDICE with SAC, TD3, and DDPG under a protocol using 10 randomly seeded runs and half-standard-deviation shading.The horizontal axis is environment steps.
  • The method derives from a Lagrangian saddle-point formulation based on a linear-programming characterization of the Q-function.The resulting algorithm compensates for distribution shift and estimates the on-policy policy gradient from off-policy data.

A Proof Details

The proof details connect Q-function linear programs and Fenchel duality to a reparameterized objective over off-policy data. Under stated assumptions, the resulting primal and dual formulations recover policy occupancies, values, and regularized return expressions.

  • Theorem 3 states that a policy’s average return has both primal and dual forms.
  • The primal constraints require ν(s,a) ≥ B_πν(s,a), while the dual formulation uses state-action occupancy variables and strong duality under Assumptions 1 and 2.
  • Any feasible ν dominates successive applications of B_π and therefore dominates Q_π, establishing the first linear-programming claim.
  • The dual equality constraints form a |S| × |A| linear system with a nonsingular matrix I − γ(P_π)^⊤, yielding a unique occupancy solution.
  • Fenchel duality and the change of variables x(s,a) := 1/α(B_πν − ν)(s,a) re-express the objective using expectations under d_π and d_D.
  • The transformed optimum satisfies x*_π(s,a) = f′(w_π/D(s,a)), and the resulting value is E_dπ[r(s,a)] − αD_f(d_π||d_D).

A.1 Extension to γ = 1

For γ = 1, the analysis extends the LP and Fenchel formulations by adding a scalar λ and assuming an ergodic policy-induced Markov chain. The resulting formulation preserves occupancy correction and handles offset-invariant dual solutions under boundedness conditions.

  • The undiscounted formulation adds a scalar primal variable λ to the dual variables ν.
  • Under ergodicity, the induced Markov chain has a unique invariant distribution d_π and mixing time T_mix.
  • Theorem 5 gives primal and dual forms for the average return, with strong duality under Assumptions 1 and 2.
  • Unlike the discounted case, optimal ν solutions are not unique because adding a constant offset leaves them optimal.
  • The γ = 1 Primal and Fenchel AlgaeDICE objectives use λ + α E_dD[f*(−λ + B_πν − ν)/α].
  • Theorem 6 shows that the optimal auxiliary variable satisfies the occupancy ratio w_π/D and automatically obeys nonnegativity and unit normalization constraints.This avoids the nontrivial self-normalization step described for Liu et al. (2018).
  • The proof uses the invariant-distribution identity E_dπ[P_πν − ν] = 0 to simplify the transformed objective.
  • Bounded occupancy ratios and the mixing-time argument place ν in the finite range N = [−CT_mix, CT_mix], after an offset shift.

B Experiment Details

The Four Rooms experiments use fixed trajectory settings for online and offline training, while continuous-control experiments specify network architectures and learning rates for several algorithms.

  • Four Rooms: Four Rooms experiments use 100 trajectories of length 100, resampling them each iteration online but fixing a behavior-policy dataset offline.The offline dataset uses the GridWalk behavior policy from Nachum et al. (2019b).
  • Four Rooms: The Four Rooms actor-critic implementation solves Qπ in closed form before taking one policy-gradient step per training iteration.The procedure uses standard matrix operations for the Qπ solution.
  • Continuous Control: Continuous-control experiments set AlgaeDICE’s regularization coefficient α to 0.01.
  • Continuous Control: AlgaeDICE uses 256-256 policy and critic networks with an actor learning rate of 10−3, compared with 400-300 networks for DDPG and TD3.

C Additional Results

Additional results examine AlgaeDICE across other initial states in Four Rooms and across choices of the function f∗.

  • Four Rooms: Figure 4 reports Four Rooms results using other initial states.
  • Function Choice: Figure 5 reports AlgaeDICE results over the choice of function f∗(x) = 1.
  • Function Choice: Different polynomial choices of f can produce slightly different results, with p = 1.5 typically performing best in the reported investigation.
Loading 1912.02074v1…