PaperlayerView exact revision on arXiv

Source-linked AI summary

Taylor Expansion of Discount Factors

Yunhao Tang, Mark Rowland, Rémi Munos, Michal Valko

arXiv:2106.06170v2cs.LGstat.ML

TL;DR

Practical RL often evaluates undiscounted cumulative return while using discounted models, raising questions about discount-factor mismatch during learning. This paper develops interpolating objectives and updates using Taylor expansions and reports empirical performance gains.

  • Problem

    Practical RL often evaluates undiscounted cumulative return while relying on discounted models, leaving a gap between the evaluation objective and value estimation.

    Source: §1 · p. 1

  • Method

    The paper derives Taylor-expansion-based objectives that interpolate value functions at two discount factors and extends the approach to policy-gradient updates.

    Source: §1 · p. 2, §8 · p. 9

  • Results

    The framework achieves empirical performance gains in estimating value functions or gradient updates.

    Source: §8 · p. 9

  • Takeaways & Limitations

    The framework sheds light on heuristics used to bridge fully discounted theory and undiscounted practice in deep RL.

    Source: §8 · p. 9

    The no-sampling approximation to the lower-discount value may not be accurate.

    Source: §3.2 · p. 3

Abstract

from arXiv · show

In practical reinforcement learning (RL), the discount factor used for estimating value functions often differs from that used for defining the evaluation objective. In this work, we study the effect that this discrepancy of discount factors has during learning, and discover a family of objectives that interpolate value functions of two distinct discount factors. Our analysis suggests new ways for estimating value functions and performing policy optimization updates, which demonstrate empirical performance gains. This framework also leads to new insights on commonly-used deep RL heuristic modifications to policy optimization algorithms.

1. Introduction

The introduction identifies a mismatch between discounted RL algorithms and finite-horizon, undiscounted evaluation objectives. It motivates using Taylor expansions to bridge that gap through interpolating objectives and policy updates.

1. Introduction

  • Practical RL often evaluates expected undiscounted cumulative return over a finite horizon, while popular algorithms are built around infinite-horizon exponential discounting.The horizon may be the first terminal state or an enforced deterministic cutoff.Source: §1 · p. 1
  • Policy-gradient implementations commonly omit discount factors, using an approximate update because discounting can make later updates too weak for long evaluation horizons.For MuJoCo tasks, γ = 0.99 gives an effective horizon of 100 versus an evaluation horizon of 1000.Source: §1 · p. 1
  • Simply increasing γ to match the evaluation horizon rarely works well, potentially because it raises estimation variance or collapses action gaps under function approximation.The example requires γ ≥ 0.999; the cited potential causes are higher variance and action-gap collapse.Source: §1 · p. 1
  • The paper proposes Taylor expansions to evaluate and optimize a less-myopic discount-factor objective, identifying interpolating objectives between it and the more myopic objective.The introduction says this approximation is more accurate than using the original γ-discounted objective.Source: §1 · p. 2
  • The authors apply Taylor expansions to heuristic policy updates to derive interpolating updates, then use theoretical insights to improve established deep RL algorithms and report performance gains.The update analysis first examines why omitting discount factors may help in practice.Source: §1 · p. 2

2. Background

The background defines discounted value quantities in an MDP and introduces a linear-program view linking value functions to discounted state visitation.

2. Background

  • The setup is a discounted MDP with deterministic bounded rewards and policy-induced trajectories; Q-, value-, and advantage functions depend on γ, marked by subscripts.A policy maps states to distributions over actions, and rewards lie in [0, Rmax].Source: §2 · p. 2

2.1. Linear programs for reinforcement learning

  • The Bellman equations can be encoded as a linear program whose primal optimum is V^π.The LP objective may also use a general state distribution.Source: §2.1 · p. 2
  • The dual solution is the discounted visitation distribution; by strong duality, V^π_γ(x) is its normalized expected reward.The dual constraint includes an initial-state term and discounted transitions.Source: §2.1 · p. 2

3. Taylor Expansions of Value Functions

The section develops Taylor expansions that transfer value estimates from lower to higher discount factors, then characterizes sample-based estimation and its finite-sample bias–variance tradeoff.

3.1. Taylor expansions of discount factors

  • For γ < γ′ < 1, the residual norm vanishes and truncated expansions approach Vπγ′ as K grows; γ′ = 1 remains valid for absorbing chains with zero-reward absorbing states.Source: §3.1 · pp. 2–3

3.2. Sample-based approximations of Taylor expansions

  • Higher-order estimates recursively bootstrap lower-order expansions, with geometric-time sampling yielding unbiased estimates; the zeroth-order estimate needs no sampling but may be inaccurate.Source: §3.2 · pp. 3–4
  • The value-function expansion framework also extends to Q-functions, with similar theoretical guarantees and estimation procedures.Source: §3.2 · p. 4

3.3. Approximation errors with finite samples

  • Finite-sample K trades lower expected approximation error against potentially higher variance, and noisier base estimates favor smaller optimal K to control variance.Source: §3.3 · p. 4
  • Analytic approximation errors decay exponentially with K, while sample-based errors initially fall and then rise slightly, making an intermediate K best in the example.The example also shows that large K does not incur a large variance penalty in this particular setting.Source: §3.3 · p. 4, Figure 1 · p. 5

4. Taylor Expansions of Gradient Updates

The section decomposes the full policy gradient for a value objective with discount γ′ and develops Taylor approximations to its first partial gradient. This explains a common policy-update heuristic and how approximations interpolate between it and the full first partial gradient.

4.1. V π γ′ as a weighted mixture of V π

  • For γ<γ′<1, Lemma 4.1 expresses V π γ′ as a weighted mixture of V π γ values.The passage states that Eqn (16) still holds when its quantities might be undefined, provided assumptions A.1 and A.2 are satisfied.Source: §4.1 · p. 5

4.2. Decomposing the full gradient ∇θV πθ γ′ (x)

  • The full gradient ∇θV πθ γ′ decomposes into two partial gradients, and the second is practically challenging because its unbiased REINFORCE estimator requires estimating γ-discounted values under γ′.The paper’s premise is that estimating values under γ′≈1 is difficult.Source: §4.2 · p. 5, §4 · p. 5
  • The common update in Eqn (18), though not generally a gradient, is a partial gradient of V πθ γ′=1 and uniformly averages over states to offset vanilla PG’s over-discounting.Proposition 4.3 provides this interpretation under assumption A.1; if termination is externally imposed, augmenting states with time makes the absorbing time state-dependent and restores the proposition’s applicability.Source: §4.2 · pp. 5–6
  • Proposition 4.3 may not hold when an external time limit terminates an MDP without a natural terminal state; augmenting the state with time makes the absorbing time depend on state.The passage names Brockman et al. (2016) as examples of external time limits and Pardo et al. (2018) as empirical study of time augmentation.Source: §4.2 · p. 6

4.3. Taylor expansions of partial gradients

  • Taylor approximations to the first partial gradient vary with order K: K=0 recovers vanilla PG, while K→∞ recovers the full first partial gradient.Intermediate K values interpolate between the updates and may offer a better bias-variance trade-off.Source: §4.3 · p. 6
  • Taylor approximation is with respect to the weight vector ρπθ because ∇θV πθ γ does not depend on γ′.The partial gradient can be represented as a weighted mixture of local gradients Qπθ γ(xt,at)∇θ log πθ(at|xt).Source: §4.3 · p. 6

5. Policy optimization with Taylor expansions

The section proposes two changes to baseline policy optimization: Taylor-expansion Q-function estimation and Taylor-expansion weighting of policy updates.

5.2. Taylor expansion Q-function estimation

  • The first change constructs a Kth-order Taylor expansion of Q^πθ_{γ′} using Q^πθ_γ as its building blocks, then uses it instead of Q^πθ_γ for downstream optimization.The authors expect this to account for an objective with a longer effective horizon.Source: §5.2 · p. 6

5.3. Taylor expansion update weighting

  • The second change weights policy updates by w_t, a Kth-order approximation to the gradient of V^πθ_γ; setting w_t=1 recovers a common deep-RL heuristic.The algorithm applies these weights to estimated Q-values and policy log-gradient terms.Source: §5.3 · pp. 6–7

6. Related work

Related work treats discount selection as a trade-off, explores adapting or using multiple discounts, and applies Taylor expansions to value functions under different policies. This work instead studies connections between value functions defined with different discounts.

Discount factors in RL

  • Prior work finds large discounts harder to solve, while small-discount policies can underperform on large-discount objectives.Nonlinear Bellman-target transformations have been proposed for numerical stability, while small discounts may regularize learning when data is scarce.Source: §6 · p. 7
  • Discount selection also echoes TD(λ), where λ trades off bias and variance in TD updates.Source: §6 · p. 7

Adapting discount factors & multiple discount factors

  • Prior work adapts discounts through human-designed (Prokhorov and Wunsch, 1997; François-Lavet et al., 2015) or black-box methods, or trains multiple discounts for TD and representation learning (Fedus et al., 2019).Complementary to these approaches, this work studies connections between value functions defined with different discounts.Source: §6 · p. 7

Taylor expansions for RL

  • Tang et al. (2020) used Taylor expansions to relate value functions under a shared discount but different policies for off-policy learning.The present work is orthogonal and could potentially be combined with this approach.Source: §6 · p. 7

7. Experiments

The experiments test Taylor-expansion changes in continuous-control robotics tasks, comparing undiscounted cumulative rewards over an evaluation horizon of T = 1000. The reported results cover Q-function estimation, update weighting, and extensions to off-policy algorithms.

7.1. Taylor expansion Q-function estimation

  • With η = 0.01, PPO(K) generally improves performance over PPO baselines, through faster learning, better asymptotic performance, or lower variance across tasks.Figure 2 compares PPO(K) with PPO using the default γ = 0.99 and a high discount factor γ = 0.999.Source: §7.1 · pp. 7–8, Figure 2 · p. 8
  • Simply raising PPO’s discount factor to γ = 0.999 generally degrades performance, supporting the concern that directly using high discount factors can be unstable.Source: §7.1 · p. 8
  • The recursive Q-difference estimator of Romoff et al. (2019), conceptually similar to Taylor expansion with K = ∞, does not improve performance out of the box.The paper attributes this to the need for a careful trade-off mediated by smaller K.Source: §7.1 · p. 8

7.2. Taylor expansion update weighting

  • PPO(K) update weighting and PPO with time limits generally outperform default PPO, but time-limit performance is unstable in some cases.Figure 3 reports median ± standard deviation across five seeds.Source: §7.2 · pp. 8–9, Figure 3 · p. 8
  • Because evaluation stops at t = T, PPO(K) downweights late local gradients, while time-limit PPO augments states with time to restore stationarity.The authors suggest late gradients contribute less to the final objective; default PPO instead weights updates uniformly.Source: §7.2 · pp. 8–9
  • Appendix F extends similar techniques to off-policy actor-critic algorithms including TD3 and SAC in continuous-control domains.Source: §7.2 · p. 9

8. Conclusion

The paper proposes discount-interpolating objectives for value functions and policy-gradient updates, enabling trade-offs that yield empirical gains. It also uses this framework to clarify the gap between theoretical and practical objectives and the heuristics that help bridge it.

8. Conclusion

  • The framework interpolates value functions defined by two discount factors and extends to other discounted cumulative quantities, including policy-gradient updates, enabling trade-offs and empirical gains.The authors identify value estimation and gradient updates as settings where these trade-offs apply.Source: §8 · p. 9
  • The framework clarifies the gap between fully discounted theoretical objectives and undiscounted practical ones, shedding light on heuristics needed for good empirical performance.The authors expect this perspective to inform new practical algorithms.Source: §8 · p. 9

APPENDICES: Taylor Expansions of Discount Factors · A. Proofs

The proof appendix establishes convergence of the discount-factor expansion for γ < γ′ < 1 and specifies absorbing-chain conditions for the γ′ = 1 case. It also derives the gradient and weighting-distribution results used in the paper.

A. Proofs

  • For γ < γ′ < 1, the residual norm decays exponentially to zero as K → ∞, so the infinite series converges.The proof appendix also combines intermediate lemmas to establish a Kth-order expansion with a vanishing residual.Source: A. Proofs · pp. 12, 14
  • For γ′ = 1, finiteness of V^π is assumed under an absorbing Markov chain with zero reward at every absorbing state.The proof restricts analysis to transient states, whose transition submatrix is invertible under these assumptions.Source: A. Proofs · pp. 12–13
  • Under the absorbing-chain assumptions, the value-function series converges for all γ < 1.The proof uses the finite expected-visit matrix for transient states to bound the residual.Source: A. Proofs · pp. 13–14
  • The proof of the main claim combines Lemmas A.2–A.4 to establish the Kth-order expansion and show that its residual vanishes.For absorbing states, the proof applies Proposition 3.2’s matrix equalities using the zero-reward condition.Source: A. Proofs · p. 14
  • Lemma 4.1’s expectation representation is derived by expressing the resolvent identity as a weight matrix and indexing its row for state x.The proof uses the commutation of (I − γP^π) with (I − γ′P^π)^−1.Source: A. Proofs · p. 15
  • The proof of Proposition 4.3 shows that the coefficient at time t equals (γ′)^t and states that the first partial gradient exists at γ′ = 1 under assumptions A.1 and A.2.For γ′ = 1, the proof handles the potentially undefined inverse using zero gradients at absorbing states and the fact that later local-gradient terms vanish.Source: A. Proofs · pp. 16–17
  • Under γ < γ′ < 1, for any x ∈ X, Proposition 4.4 defines the Kth Taylor expansion to ρπ; truncating the infinite series to its first K + 1 terms derives the Kth-order expansion.Source: A. Proofs · pp. 17–18

B. Further results on Taylor expansions in the dual space … D.1. Further discussions on the objectives

The appendices connect primal Taylor approximations to approximations of discounted visitation distributions, detail Q-function expansion estimation and update weighting, and explain why estimating a full-gradient term is challenging.

B. Further results on Taylor expansions in the dual space

  • The dual Taylor expansion truncates after K + 1 terms, and its residual vanishes under γ < γ′ < 1.The passages establish convergence for this discount-factor condition.Source: B. Further results on Taylor… · pp. 18–19
  • For any K ≥ 0, the Kth order primal value-function approximation equals the Kth order dual visitation-distribution approximation.The dual residual norm tends to zero when γ < γ′ < 1.Source: B. Further results on Taylor… · pp. 18–19

C. Details on Taylor expansion Q-function advantage estimation

  • The Q-function expansion estimator samples K independent geometric times with parameter 1 − γ from a trajectory to estimate its Kth term.The derivation uses a transition kernel over state-action pairs, which differs from the state-transition kernel used for value functions.Source: C. Details on Taylor expansion… · p. 19

D. Details on Taylor expansion update weighting

  • The update-weighting proof regroups expansion terms by their total index and weights each group using the count F(s, K + 1).The count is obtained by recursively decomposing the set and proving the resulting formula by induction.Source: D. Details on Taylor expansion update… · pp. 20–21

D.1. Further discussions on the objectives

  • The second full-gradient term differentiates an expression while holding V^πθ_γ(x_t) fixed, making it equivalent to a value function with those values as rewards and discount γ′.The resulting term involves W^πθ_{γ,γ′}.Source: §D.1 · p. 22
  • An unbiased estimator of that gradient term requires estimating W^πθ_{γ,γ′}, which is difficult because estimated value functions can add bias and variance and discount γ′ can yield high variance.The passages identify both difficulties as practical concerns.Source: §D.1 · p. 22

E. Details on approximation errors with finite samples … F.4.2. TAYLOR EXPANSION UPDATE WEIGHTING: ABLATION ON K

The finite-sample analysis identifies a bias–variance trade-off as Taylor order K increases, while the update-weighting ablation finds that intermediate K values perform best on average. The further experiments also describe Q-function estimation and the experimental configurations used to evaluate it.

E. Details on approximation errors with finite samples

  • As K increases, the estimator’s variance grows, Taylor-expansion bias decreases, and the contraction generally slows; the bounds illustrate this trade-off.The finite-sample error term vanishes as sample size n increases, whereas the gap between the expected Kth-order expansion and the higher-discount value function decreases with K and does not depend on n. The bounds are intended to illustrate the trade-off and could be improved.Source: E. Details on approximation errors… · pp. 22–23

F.1. Further details on the toy example

  • The toy example uses a 10-state, 2-action tabular MDP with sparse transitions and random rewards.Transitions are drawn from a Dirichlet distribution with α = 0.01; reward means are uniform on [0, 1], with Gaussian noise of variance 0.22.Source: §F.1 · p. 24

F.2. Deep RL algorithms

  • TRPO shares PPO’s actor–critic pipeline but uses a strict KL-divergence constraint (ε = 0.01) and line search; PPO’s GAE uses γ = 0.99 and λ = 0.95.Source: §F.2 · p. 24

F.3. Deep RL architecture

  • The experiments use two-layer neural networks with 64 hidden units and tanh activations for both policy means and value functions.Neither network’s output layer has an activation function.Source: §F.3 · p. 24

F.4. Additional deep RL experiment results

  • The additional experiments use K = 1 and mix the default Q-function estimator with the Taylor-expansion estimator.The estimator’s mixture weight η balances their numerical scales, and the implementation is more stable when η is small in absolute scale.Source: §F.4 · p. 24, §F.4.1 · p. 24

F.4.1. TAYLOR EXPANSION Q-FUNCTION ESTIMATION: ABLATION STUDY ON

  • Across tasks, average performance initially rises as η increases from zero and then declines; the authors select η = 0.01 to account for performance variance.The effect is task-dependent: larger η works better on HalfCheetah(B), while Ant(B) improves marginally before degrading as η increases.Source: §F.4.1 · p. 24

F.4.2. TAYLOR EXPANSION UPDATE WEIGHTING: ABLATION ON K

  • In Figure 5(d), K = 10 and K = 100 achieve locally optimal mean performance, while K = 10 also achieves locally optimal median performance.The effect varies by environment: larger K improves HalfCheetah(G), while improvement is less prominent across a wide range of K for Walker(G).Source: §F.4.2 · p. 25
  • Practical mini-batch updates self-normalize local-gradient weights, which can partly offset the aggressive discount at K = 0 and explain its limited underperformance.The theoretical K = 0 update recovers vanilla policy gradient, described as generally too conservative for the undiscounted objective; the authors offer self-normalization as an explanation for the practical result.Source: §F.4.2 · p. 25

F.4.3. COMPARISON TO RESULTS IN … G.3. Algorithm details for update weighting

The paper contrasts intermediate Taylor-expansion estimators with the difficulty of recursive bootstrapping at K = ∞, and extends update weighting to off-policy actor-critic methods. In the reported benchmarks, TD3(γ) gives a modest consistent boost over TD3, while SAC(γ) remains competitive with SAC.

F.4.3. COMPARISON TO RESULTS IN

  • The authors conjecture that K = ∞ Taylor-expansion estimation is as difficult as directly estimating V π, while K = 0 may be too conservative.Although K = ∞ aims at exact value functions, recursive bootstrapping may induce challenging variance.Source: §F.4.3 · p. 25

G. Extensions of update weighting techniques to off-policy algorithms

G.1. Off-policy actor-critic algorithms

  • Off-policy actor-critics learn a deterministic policy and Q-function from replay-buffer data, updating the policy with a deterministic policy gradient.The paper describes DDPG, TD3, and SAC as related off-policy actor-critic approaches.Source: §G.1 · p. 27

G.2. Architecture

  • The shared architecture uses two-layer, 256-unit ReLU networks for policy and critic; stochastic policies additionally parameterize log standard deviation and squash actions with tanh.The deterministic policy output is also squashed with tanh, while the critic output has no activation.Source: §G.2 · p. 27

G.3. Algorithm details for update weighting

  • The off-policy extension weights policy updates using a density ratio estimated between the replay buffer D and a fast buffer Df of recent data.Weights are normalized across the batch and temperature-adjusted with τ = 0.1; the critic is updated by TD-learning.Source: §G.3 · p. 28
  • Using γ′ = 1 makes the target distribution uniform over sampled trajectory states without discounting, simplifying implementation; Taylor-expansion extensions are left for future work.This differs from prior reweighting based on the fully discounted visitation distribution; the proposed weighting targets policy-training speed rather than critic stabilization.Source: §G.3 · pp. 28–29
  • TD3(γ) provides a modest, consistent boost over TD3 across four tasks, performing similarly to or marginally better than the baseline.The comparison also includes PPO for sample-efficiency context and DDPG results from prior work; Table 1 reports final scores averaged over five seeds.Source: Figure 6 · p. 29, Table 1 · p. 30
  • SAC(γ) gains marginally on Walker2d and Ant but trails SAC slightly on HalfCheetah and Hopper, remaining competitive overall.The authors suggest SAC's tuned HalfCheetah hyperparameters may limit further gains without exhaustive search.Source: Figure 7 · p. 29, §G.3 · p. 29, Table 1 · p. 30
Loading 2106.06170v2…