PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex-Concave Reinforcement Learning

Shripad V. Deshmukh, Yaswanth Chittepu, Dhawal Gupta, Philip Thomas, Scott Niekum

arXiv:2610.09108v1cs.LGcs.AI

TL;DR

Exact iterative policy improvement is non-convex when trajectory terms multiply across decisions, prompting methods to rely on single-step surrogates. CCRL reformulates the objective as a difference-of-convex program and solves it with sequential convex programming; it is competitive with tuned PPO and reaches near-optimal sepsis survival faster.

  • Problem

    For k ≥2, iterative policy improvement is non-convex because trajectory importance ratios multiply policy terms, so gradient-based methods cannot guarantee global optimality.

    Source: §2.1 · p. 5

  • Method

    CCRL uses log policy ratios to formulate exact per-iteration improvement as a difference-of-convex program and solves it with sequential convex programming, with k controlling coupled decisions.

    Source: §1 · p. 3

  • Results

    CCRL’s advantage over tuned PPO grows with decision-dependency length, is competitive on classic control, and reaches the same near-optimal sepsis survival faster with 11.3% higher area under the training curve.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The horizon k spans single-step methods and full-horizon unbiased return, allowing one update to credit actions for outcomes several steps later.

    Source: §1 · p. 3

    Each policy iteration requires several SCP rounds, k can be delicate to tune, and outer-loop contraction requires bounded concentrability and a globally solved inner problem.

    Source: §9 · p. 13

Abstract

from arXiv · show

Policy learning drives many of the most consequential and heavily-invested applications of reinforcement learning today. Yet the core optimization problem it rests on (maximizing expected return) is notoriously non-convex, even under a direct policy parameterization, and the field has largely responded by avoiding it: optimizing convex surrogate approximations of the return under trust-region constraints (NPG, TRPO, PPO, AWR). We show that this seemingly unstructured problem is not actually structureless. In log-density-ratio coordinates $y := \log[\pi/\pi_n]$, the exact per-iteration objective, computable via per-decision importance sampling (PDIS), is a difference-of-convex-constrained difference-of-convex (DC-constrained DC) program. This structure lets us move beyond surrogate approximations: it recovers CPI, NPG, TRPO, and AWR as special cases along interpretable axes, and it opens a multi-step axis $k$ that couples consecutive decisions. We solve the per-iteration program with sequential convex programming (SCP), the standard solver for difference-of-convex problems, and give convergence guarantees under mild conditions, bridging the difference-of-convex optimization and RL literatures. Empirically, multi-step Convex-Concave RL (CCRL) wins on diagnostic MDPs where credit must propagate across a horizon (its advantage growing with the dependency length), is competitive with a tuned PPO on classic control, and on a realistic, stochastic, mid-horizon healthcare domain converges markedly faster than tuned PPO to the same near-optimal survival, with an 11.3% higher area under the training curve.

1 Introduction

Policy-gradient methods often optimize single-step convex surrogates rather than confront the non-convex expected-return objective directly. CCRL reformulates exact per-iteration improvement as a difference-of-convex program and extends policy updates to couple decisions across multiple steps.

1 Introduction

  • The expected-return objective is non-convex, so prevailing policy-gradient methods instead optimize convex single-step surrogates within trust regions.When several timesteps jointly determine outcomes, the single-step update can move away from the optimum until value estimates catch up.Source: §1 · pp. 2–3
  • CCRL uses log policy ratios to express exact per-iteration improvement as a difference of convex functions, rather than optimizing a surrogate.The objective is estimable from on-policy trajectories by per-decision importance sampling.Source: §1 · p. 3
  • The horizon k extends single-step methods: k ≥2 couples consecutive decisions, while k = H optimizes the exact, unbiased return.At k = 1, the formulation recovers the single-step surrogate optimized by CPI, NPG, TRPO, PPO, and AWR.Source: §1 · p. 3
  • Sequential convex programming solves convex approximations to global optimality at each round, yielding monotonic objective improvement and convergence to a stationary point, not a global optimum.The per-update guarantee is unconditional; the policy-sequence guarantee requires full-horizon updates under one particular trust region. Each round also costs more computation than one policy-gradient step.Source: §1 · p. 3
  • The deployed algorithm enforces policy validity only at the end of an update, preserving monotonic improvement but forfeiting the convergence guarantees.It also caps log-ratios to keep k-step estimates well behaved.Source: §1 · p. 3
  • On a stochastic healthcare task, CCRL reached the same near-optimal survival as tuned PPO markedly faster, with 11.3% higher area under the training curve.CCRL was competitive with PPO on classic-control tasks, while its advantage grew on diagnostic MDPs as reward depended on coordinating more consecutive decisions.Source: §1 · p. 3

2 Preliminaries

The preliminaries define iterative on-policy improvement and explain why current-policy data requires either a biased surrogate or importance-sampling correction. For multiple-step updates, the resulting objective is generally non-convex, but admits a difference-of-convex structure.

2 Preliminaries

  • The setup is a finite-horizon discounted MDP with finite state and action sets, a transition and reward function, and an initial-state distribution.Policies induce trajectory distributions; policy performance is expected return from the initial-state distribution.Source: §2 · p. 4
  • Each iteration collects trajectories under the current policy and searches for an improved candidate, whose improvement must be estimated from current-policy data.Candidate-policy expectations are unavailable, and data-based estimates are reliable only when the candidate stays near the current policy.Source: §2 · p. 4
  • Substituting current-policy state visitation for candidate-policy visitation yields the biased CPI surrogate used by NPG, TRPO, and PPO.Its bias grows with divergence between the candidate and current policies.Source: §2 · p. 4
  • Per-decision importance sampling exactly corrects the trajectory distribution, but its variance grows exponentially with horizon; truncation adds bias, while a trust region constrains policy changes.The k-step window controls the bias-variance tradeoff, and the trust-region constraint is an f-divergence ball around the current policy.Source: §2 · pp. 4–5

2.1 Non-convexity of general iterative on-policy optimization

  • For k ≥2, products of policy terms across a trajectory make the iterative improvement objective non-convex, so gradient-based methods cannot guarantee global optimality.At k = 1 the objective is linear in the policy and the problem is convex.Source: §2.1 · p. 5
  • A difference-of-convex decomposition enables a principled iteration: linearizing the concave part yields a convex subproblem, with monotonic decrease toward a stationary point rather than guaranteed global optimality.The trust-region PDIS problem admits an explicit DC decomposition under a suitable change of variable.Source: §2.1 · p. 5

3 Iterative On-Policy Improvement as a Difference-of-Convex Program

In log-density-ratio coordinates, the k-step PDIS objective has difference-of-convex structure, and CCRL combines it with policy-validity and trust-region constraints. At k = 1 it recovers familiar on-policy methods, while larger k incorporates longer temporal dependence.

3.1 DC structure of the k-step PDIS objective

  • The log-ratio transformation exposes a difference-of-convex decomposition of the k-step PDIS objective for every k.It turns products of importance ratios into sums of exponentials; terms with positive and negative advantages form the two convex parts.Source: §3 · p. 5, §3.1 · p. 6

3 Iterative On-Policy Improvement as a Difference-of-Convex Program

  • The section’s central formulation expresses iterative on-policy improvement as a DC program in log-density ratios.The reformulation targets the per-iteration improvement objective.Source: §3 · p. 5

3.3 Representing f-divergence trust region constraints in terms of log-density ratios

  • For finite α outside [0, 1], the three α-divergence trust-region forms are convex in log-ratio coordinates.The α parameterization keeps the transformed constraints in exponential-of-affine form, though it does not represent every possible divergence.Source: §3.3 · p. 6

3.4 Full iterative on-policy improvement problem in log-density ratios

  • CCRL combines a DC objective, a DC validity equality, and a convex trust-region inequality in each policy iteration.Validity requires the per-state normalizer to equal one.Source: §3.2 · p. 6, §3.4 · p. 7

3.5 Relationship between CCRL and the prevalent trust-region based on-policy algorithms

  • At k = 1, CCRL recovers the CPI surrogate optimized by CPI, NPG, TRPO, and AWR; varying k and α extends the framework to longer dependence and different divergences.TRPO and NPG correspond to reverse-KL proximity at the objective-and-divergence level, while AWR uses forward KL.Source: §3.5 · p. 7

4 Policy optimization using Sequential Convex Programming (SCP)

The section adapts sequential convex programming to the policy-validity constraint: textbook SCP freezes at a valid iterate, while tangent-plane linearization and softmax retraction allow updates that restore validity.

4.1 Solving the DC-constrained DC program

  • Textbook SCP freezes at a valid iterate because its linearized reverse-convex validity constraint collapses the feasible set to that anchor.The resulting subproblem cannot move.Source: §4.1 · pp. 7–8
  • The modified SCP linearizes validity as an equality and applies per-state softmax retraction to restore exact validity after each tangent-plane update.The trust region is imposed exactly, while a scheduled support floor is used for α > 1.Source: §4.1 · p. 8
  • After R rounds, the final iterate defines the next policy, or serves as a target distribution for maximum-likelihood fitting in a parametric policy class.Each iteration collects episodes under the current policy and initializes the log-ratios at zero.Source: §4.1 · p. 8

5 Convergence Analysis

The convergence analysis gives an inner-loop guarantee for SCP rounds and a conditional outer-loop contraction guarantee for the policy sequence. The outer result concerns exact full-horizon PDIS under strict per-state χ2 trust regions and contracts only to a neighborhood.

5 Convergence Analysis

  • The analysis uses direct parameterization on log-density ratios to establish inner-loop and outer-loop guarantees.The outer-loop result specializes to exact PDIS with k = H and strict per-state χ2 trust regions with α = 2.Source: §5 · p. 8, §5.2 · p. 9

5.1 Inner-loop convergence

  • Under the stated full-support and trust-region assumptions, every SCP subproblem is feasible, and the minimum squared proximal-step residual decreases at an O(1/R) bound.Limit points are d-stationary over the limiting feasible set when LICQ holds for the active constraints.Source: §5.1 · pp. 8–9

5.2 Outer-loop convergence

  • With an outer support floor and bounded concentrability, the policy sequence contracts geometrically toward a neighborhood whose radius depends on floor bias and inner-solve error.The contraction rate degrades with horizon and coverage; the outer assumptions do not follow from the inner stationarity result.Source: §5.2 · p. 9

6 Practical implementation of CCRL

The deployed implementation simplifies the theoretical SCP loop for practicality, but this drops guarantees that depend on maintaining validity at every round.

6 Practical implementation of CCRL

  • The deployed version replaces tangent-plane SCP with a plain trust-region convex program and restores validity only with a final recovery softmax.For parametric policies, it fits a target distribution by maximum likelihood.Source: §6 · p. 9
  • A box constraint on log-ratios prevents k-step importance weights from overflowing, with tighter clipping trading some bias for lower variance.Source: §6 · p. 9
  • Restoring validity only at the end retains monotone inner-loop descent but forfeits guarantees requiring in-loop validity, including outer-loop contraction.These include per-round feasibility and limit-point d-stationarity.Source: §6 · p. 10

7 Experiments

The experiments test whether multi-step credit helps as reward dependencies deepen, while comparing CCRL with tuned on-policy baselines under matched interaction budgets. CCRL reaches near-optimal healthcare survival faster than PPO, and its advantage grows with dependency length.

7.1 Multi-step credit propagation via k > 1 truncated PDIS

  • 1.38 iterations: CCRL alone reaches 90% of optimal in under two iterations, committing to the rewarding action despite its locally negative signal.All four methods identify the downstream action; only CCRL also commits to L at s0.Source: §7.1 · p. 10, Figure 1 · p. 10

7.2 Gains amplify with dependency horizon

  • t90 ≤1.3 and final normalized return 1.000: full-depth CCRL remains fast across N=4–6, while PPO’s t90 rises from 3.9 to 9.4 iterations.Both methods use the same networks and budget; intermediate CCRL depths can be non-monotonic, while k=N is best or tied on every metric.Source: Table 1 · p. 11, §7.2 · p. 11

7.3 CCRL is competitive on classic control

  • CCRL at k=1 is competitive with PPO across four control tasks, but larger k degrades performance, most visibly on CartPole and LunarLander.The authors attribute the tradeoff to added estimator variance outweighing the credit-assignment benefit on these tasks.Source: §7.3 · p. 11, Figure 2 · p. 12

7.4 CCRL can outperform PPO on a stochastic, medium-horizon task

  • 0.815±0.008 vs 0.732±0.009 nAUC: CCRL reaches near-optimal sepsis survival sooner, while PPO and CCRL finish at similar survival.The table covers 100 seeds and 500 updates; its controlled sweep shows tightening ymax makes multi-step credit usable at each depth.Source: §7.4 · pp. 12–13, Table 2 · p. 13

8 Related Work

CCRL is situated among surrogate policy-optimization methods, multi-step credit-assignment methods, and work on difference-of-convex optimization and policy-gradient convergence.

8 Related Work

  • CCRL generalizes the CPI-surrogate family, including CPI, NPG, TRPO, and AWR.The paper discusses this connection in Section 3.5.Source: §8 · p. 13
  • Unlike TD(λ), GAE, and Retrace, which shape value or advantage targets, CCRL uses multi-step coupling in the objective.Its truncation depth k couples consecutive decisions.Source: §8 · p. 13
  • CCRL is closest in spirit to POIS, but exposes difference-of-convex structure and uses k to couple decisions.The analysis also builds on difference-of-convex optimization and policy-gradient convergence work.Source: §8 · p. 13

9 Conclusion

CCRL formulates iterative on-policy improvement as a log-sum-exp difference-of-convex program, recovering several trust-region methods and extending them through divergence order and truncation depth. Its multi-step objective recovers credit missed by single-step methods on diagnostic MDPs, while the method remains computationally costly and has theoretical assumptions.

9 Conclusion

  • On risky corridor and chain MDPs, the multi-step objective recovered credit missed by single-step methods, with the margin widening as the chain deepened.On classic control it was competitive with PPO but not consistently better; on a stochastic, horizon-20 clinical task it showed a convergence edge.Source: §9 · p. 13
  • CCRL recovers CPI, NPG, TRPO, and AWR as special cases and extends them along divergence order α and truncation depth k.The paper establishes an unconditional O(1/R) inner-loop stationarity guarantee for any k, and conditional geometric contraction of the outer policy sequence at k=H with a χ2 trust region and bounded concentrability.Source: §9 · p. 13
  • Each policy iteration requires several SCP rounds, making it more expensive than PPO’s single gradient step, and truncation depth k can be delicate to tune.The outer-loop contraction relies on bounded concentrability and a globally solved inner problem; inner-loop analysis assumes α > 1, excluding the reverse-KL endpoint.Source: §9 · p. 13
  • The authors identify variance reduction for k-step couplings, dynamic coupling estimates, scaling to larger domains, and sharper inner-loop convergence analysis as open directions.Source: §9 · p. 13

Contributions

The contribution statements assign formalization, algorithm design, convergence theory, and experimentation across the author team. They also describe the origins of the log-importance-ratio variables and the manuscript’s development.

Contributions

  • SD formalized multi-step trust-region policy improvement as a DC program with YC and DG, while PT and SN advised on aspects of the formalization.Source: Contributions · p. 14
  • SD designed the SCP-based CCRL algorithm with YC, developed convergence theory with AI tools, and connected the framework to existing policy-gradient methods.Source: Contributions · p. 14
  • SD designed failure-case MDPs, scaled experiments, diagnosed SCP-based CCRL limitations, and identified a healthcare use case; PT and SN advised on the work and manuscript.Source: Contributions · p. 14
  • DG contributed the importance-weighted policy-improvement perspective and proposed log importance ratios as optimization variables for their useful convex structure.YC helped develop the DC formalism, which followed unsuccessful attempts to frame the objective as a geometric program.Source: Contributions · p. 14

Supplementary Materials The following content was not necessarily subject to peer review.

The supplementary materials document CCRL’s algorithms and supporting optimization results. They include the deployed experimental procedure, SCP subproblem conditions, a validity-constraint construction, and convexity results for divergence constraints.

Supplementary Materials The following content was not necessarily subject to peer review.

  • The appendix collects the full CCRL algorithm, SCP subproblem Lagrangian and KKT conditions, divergence convexity facts, stationarity background, proofs, additional experiments, and related work.Source: Supplementary Materials The following… · p. 17

A The full CCRL algorithm

  • The theoretical outer loop collects fresh data, fits an advantage critic, runs tangent-plane SCP rounds with retraction, and recovers the next policy from the final iterate.The stated algorithm targets discrete action spaces.Source: A The full CCRL algorithm · p. 17
  • The deployed algorithm replaces the tangent-plane subproblem with a trust-region convex program, drops per-round retraction and the support-floor schedule, and adds a log-ratio clip.It restores policy validity by final row-normalization and uses a parametric maximum-likelihood step to fit the policy to the normalized target.Source: A The full CCRL algorithm · p. 17

B Lagrangian Form and KKT Conditions for the SCP Subproblem

  • The SCP subproblem’s Lagrangian uses a nonnegative trust-region multiplier, free equality multipliers, and nonnegative floor multipliers; its convexity and Slater condition support KKT stationarity conditions.Source: §B.1 · p. 18, §B.2 · p. 18

B.5 Why the equality is linearized as an equality

  • Linearizing validity as an equality avoids a naive DC split that would freeze the iteration at its anchor; retraction restores exact validity after each round.The retraction’s effect on the objective is second order and is absorbed by the proximal term.Source: §B.5 · p. 19

C.2 α-divergence in y-space: finite α

  • For finite α outside [0, 1], the trajectory-level, strict per-state, and expected per-state α-divergence constraints are convex in log-ratio variables y.An f-divergence is convex in policy space when its defining function is convex and f(1)=0.Source: §C.1 · p. 19, §C.2 · p. 20

C.3 The KL endpoints: one convex, one not

The appendix distinguishes the convexity behavior of the two KL endpoints in log-ratio coordinates and states when the policy iteration’s fixed points are directionally stationary. It also outlines and proves the DC decomposition of the k-step objective.

C.3 The KL endpoints: one convex, one not

  • The reverse-KL endpoint is convex in y, whereas the forward-KL expression is not; TRPO’s reverse-KL correspondence needs no caveat, while AWR’s forward-KL solution uses convexity in policy space.CCRL uses finite α outside [0, 1], where its trust-region constraints are convex in y.Source: §C.3 · p. 20

D Directional Stationarity

  • When the retracted iteration is fixed and LICQ holds, its anchor is a directionally stationary point of the original program.The appendix defines tangent-cone directions as those along which the feasible set can be approached to first order.Source: D Directional Stationarity · p. 21

E Proofs for the DC Reformulation

E.1 Proof of Theorem 1 (DC structure)

  • The proof establishes the DC decomposition by expressing positive and negative advantage-weighted terms as nonnegative weighted sums of convex exponential functions of y.Source: §E.1 · p. 22

E.2 Proof of Proposition 3 (CPI/NPG/TRPO objective recovery)

This section derives AWR and TRPO/NPG objective recovery at k = 1 and establishes feasibility and convergence guarantees for the retraction-SCP inner loop and exact-PDIS strict-χ²-trust-region outer loop, with their required assumptions and comparator bounds.

E.2 Proof of Proposition 3 (CPI/NPG/TRPO objective recovery)

  • At k = 1, the cumulative product in (2) reduces to the single-step ratio ρ(St, At) = ey(St,At), which is then substituted into (2).Source: §E.2 · p. 22

E.3 Proof of Proposition on AWR recovery

  • At k = 1, the forward-KL-constrained CCRL program recovers AWR’s objective, constraint, and closed-form policy, after dropping validity and normalizing post hoc.The recovered policy is π*(a|s) ∝ πn(a|s) exp(Aπn(s, a)/ηawr) [Peng et al., 2019].Source: §E.3 · pp. 22–23

F.1 The retraction lemma

  • The retraction subtracts a statewise constant to restore exact policy validity, with its shift bounded using convexity, tangency, and smoothness.The proofs use finite sums of exponentials of affine maps, fixed-box smoothness and Lipschitz bounds, Jensen’s inequality, strong convexity, telescoping, the performance-difference lemma, and a concentrability step.Source: §F.1 · p. 23, F Proofs for the Convergence Analysis · p. 23

F.2 Two lemmas that close the feasibility induction

  • For α > 1, the retraction’s statewise shifts do not increase the trajectory-level, strict per-state, or expected per-state trust-region divergences, enabling the trust-region feasibility step.The nonexpansiveness does not extend to α < 0 or the reverse-KL endpoint; the inner-loop guarantee uses the strict per-state form.Source: §F.2 · pp. 23–24

F.3 Feasibility, compactness, and the well-posed induction

  • The feasibility induction confines iterates to a compact set while preserving exact validity and trust-region feasibility; its scheduled floor bounds policy support and is necessary for compactness when α ≥ 1.The effective support floor is πr(a|s) ≥ pmine^−B(ρ), with B(ρ) = O(1/ρ); without a floor, feasible coordinates can escape to −∞.Source: §F.3 · pp. 25–26

F.4 Inner-loop convergence

  • With α > 1, strict per-state trust regions, and the stated proximal-weight conditions, retraction-SCP decreases the objective, reaches an ε-sized proximal-step residual within O(1/ε^2) rounds, and has d-stationary limit points under LICQ.The guarantee also implies the proximal-step residual and iterate gap tend to zero.Source: §F.4 · p. 26
  • Under LICQ, a zero residual implies d-stationarity, and the smallest squared residual through R inner rounds is O(1/R).The residual measures approximate first-order progress through the proximal step.Source: §F.4 · p. 27

F.5 Outer-loop setup and assumptions

  • The outer-loop analysis assumes a uniform action-probability floor on every iterate and finite concentrability; the floor is explicit, not implied by the inner-loop guarantee.It specializes to exact PDIS (k = H) and strict per-state χ2 trust regions (α = 2).Source: §F.5 · pp. 27–28

F.6 Mixture state-visitation dominance

  • Mixtures of the current policy and another policy retain a lower bound on state visitation relative to the current policy.The proof uses an entrywise lower bound on the mixture transition kernel and sums the resulting time-step bounds over the horizon.Source: §F.6 · p. 28

F.7 Floored greedy comparator

  • The floored-greedy comparator admits a statewise advantage decomposition, separating its main contribution from a signed residual due to the probability floor.The lower-bound proof treats that residual separately.Source: §F.7 · p. 28, §F.8 · p. 29

F.8 Global inner optimum lower bound

  • Under Assumptions 1–2, Lemma 20 lower-bounds the global inner optimum using a feasible mixture of the current policy and a floored-greedy comparator.Its residual is bounded uniformly using total visitation mass; the resulting worst-case factor |A| Amax ZH vanishes linearly as pmin → 0.Source: §F.8 · pp. 29–30

F.9 Per-step improvement and outer-loop contraction

  • Under Assumptions 1–2, Theorem 21 gives per-step improvement, and the outer-loop analysis needs only inner-solution feasibility and value gap—not d-stationarity or an inner-iteration rate.At k = H, the objective equals the true performance difference, without surrogate bias.Source: §F.9 · p. 30

F.10 Proof of Theorem 6 (Outer-loop contraction)

The appendix combines a conditional outer-loop contraction analysis with experimental analyses of advantage estimation, PDIS-k variance, and risky-task protocols. On CartPole, increasing k raises estimator variance sharply, while advantage-estimation quality varies across metrics and declines as the policy improves.

F.10 Proof of Theorem 6 (Outer-loop contraction)

  • Outer-loop contraction is conditional: c decays exponentially with horizon for fixed λ, while pmin→0 reduces floor bias but worsens inner-loop conditioning.The contraction bound is informative when the inner-solve gap is small; the residual neighborhood also contains the floor bias.Source: §F.10 · pp. 30–31

G.1 Risky Corridor MDP: advantage under the uniform behavior policy

  • Under behavior policy πb, optimal action L has advantage −7 while R has +7, so this MDP is a stress test for the CPI surrogate at k = 1.Source: §G.1 · p. 31

G.2 Risky Corridor MDP: detailed results

  • The corridor comparison uses 32 episodes per update over 10 updates, with four methods tuned in a two-stage protocol and reported over 100 validation seeds.Configurations are ranked by AUC, with final return and t90 as tie-breakers.Source: §G.2 · p. 31

G.3 Advantage-estimation quality on CartPole

  • TD(0) correlation falls from 0.25 to 0.03 and sign agreement declines from ∼68% toward chance; low-λ GAE and TD(0) minimize MSE, but no estimator dominates.The MC baseline and high-λ GAE incur an order-of-magnitude larger MSE than low-λ GAE and TD(0).Source: Figure 3 · p. 32, §G.3 · p. 33

G.4 PDIS-k objective variance on CartPole

  • At every checkpoint, PDIS objective variance rises with k (k=1<k=2<k=3), separating by 2–3 orders per increment; final variances are ≈10^4, ≈10^6, and ≈10^10.The widening spread of importance-sampling weights explains the increase; their maximum rises from ∼20 at k=1 to ∼8000 at k=3.Source: Figure 4 · p. 33, §G.4 · p. 34

G.5 Risky Chain: hyperparameter grids and tuning protocol

  • Risky Chain configurations are tuned independently at 128 trajectories per update and 200 iterations; top configurations are validated on 300 fresh seeds.PPO and CCRL share the entropy grid, but their grids span 1296 and 3456 configurations per cell, respectively.Source: §G.5 · pp. 34–35

G.6 Therapeutic-Threshold Sepsis MDP: environment and experimental setup

The sepsis setup makes survival depend on a sequence of dose decisions, while the related-work discussion distinguishes CCRL’s multi-step objective from methods that alter value targets or optimize single-step surrogates. The supplied classic-control and related-work passages describe evaluation setup and methodological context, not comparative results.

G.6 Therapeutic-Threshold Sepsis MDP: environment and experimental setup

  • The sepsis MDP has sparse terminal reward equal to survival probability; survival requires D successive doses before administering, so credit-assignment depth is D.The setup uses five severity levels, three doses to threshold, and a 20-step horizon; its dynamic-programming optimum survives 0.840 of episodes.Source: §G.6 · pp. 35–36

G.7 Classic control: environment and experimental setup

  • Classic control compares tuned PPO with CCRL at k∈{1,2,3} across four Gymnasium tasks, reporting learning curves, final return, and AUC over 100 seeds.Each environment–algorithm cell is tuned independently and run for 200 policy iterations.Source: §G.7 · p. 36

H Extended related work

  • CPI, NPG, TRPO, and AWR are described as single-step CPI-surrogate cases of CCRL; PPO clipping and AWAC off-policy reuse lie outside that stated special-case family.CCRL extends the template along a multi-step axis k≥2.Source: H Extended related work · p. 36
  • CCRL places horizon k inside the optimization objective, coupling consecutive decisions, whereas TD(λ), GAE, and Retrace(λ) shape advantage or value targets for single-step updates.Thus the policy update itself, rather than only its critic target, incorporates multi-step information.Source: H Extended related work · p. 37
  • CCRL uses PDIS as an optimization target and exposes its DC structure in log-ratio coordinates, with k trading multi-step credit propagation against variance.POIS is cited as a related approach that optimizes an importance-sampling surrogate offline with a high-confidence variance penalty.Source: H Extended related work · p. 37
  • The analysis gives an unconditional O(1/R) inner-loop stationarity rate for any k, but outer policy-sequence contraction is conditional at k=H under χ2 trust regions and concentrability.The related-work passage contrasts this with global-convergence results relying on the k=1 CPI-surrogate objective being linear in π.Source: H Extended related work · p. 37
  • The log change of variables exposes the PDIS objective’s DC structure, and the SCP procedure handles policy-simplex validity as a DC equality.The stated guarantees remain at the assumption-free level standard for difference-of-convex algorithms.Source: H Extended related work · p. 37

Related papers

Loading 2610.09108v1…