Paper deep dive
Convex-Concave Reinforcement Learning
Shripad V. Deshmukh, Yaswanth Chittepu, Dhawal Gupta, Philip Thomas, Scott Niekum
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/8/2026, 6:53:25 AM
Summary
The paper introduces Convex-Concave Reinforcement Learning (CCRL), a framework that reformulates the non-convex policy optimization problem as a difference-of-convex (DC) program using log-density-ratio coordinates. By leveraging per-decision importance sampling (PDIS) and sequential convex programming (SCP), CCRL unifies existing methods like PPO, TRPO, and NPG as special cases while enabling multi-step credit assignment. Empirical results show CCRL converges faster than PPO in healthcare domains and performs competitively on classic control tasks.
Entities (9)
Relation Signals (8)
CCRL → reformulates → DC Program
confidence 95% · the exact per-iteration objective... is a difference-of-convex-constrained difference-of-convex (DC-constrained DC) program.
CCRL → uses → SCP
confidence 95% · We solve the per-iteration program with sequential convex programming (SCP)
CCRL → outperforms → PPO
confidence 92% · on a realistic, stochastic, mid-horizon healthcare domain converges markedly faster than tuned PPO
CCRL → unifies → AWR
confidence 90% · it recovers CPI, NPG, TRPO, and AWR as special cases
CCRL → unifies → NPG
confidence 90% · it recovers CPI, NPG, TRPO, and AWR as special cases
CCRL → unifies → PPO
confidence 90% · it recovers CPI, NPG, TRPO, and AWR as special cases
CCRL → unifies → TRPO
confidence 90% · it recovers CPI, NPG, TRPO, and AWR as special cases
CCRL → uses → PDIS
confidence 90% · computable via per-decision importance sampling (PDIS)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2610.09108v1
- Canonical: https://arxiv.org/abs/2610.09108v1
Trouble viewing inline? Open PDF directly →
Full Text
154,993 characters extracted from source content.
Expand or collapse full text
Convex-Concave Reinforcement Learning Shripad Deshmukh Yaswanth Chittepu Dhawal Gupta Philip Thomas Scott Niekum Keywords: policy optimization, difference-of-convex programming, trust-region methods. Summary 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[π/πn]y:= [π/ _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) 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, 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. Contribution(s) 1. We show that the exact (non-convex) objective of iterative on-policy improvement can be rewritten, via a logarithmic change of variables, as a difference-of-convex (DC) program in two log-sum-exp functions, and that classic trust-region methods (CPI, NPG, TRPO, AWR) are a special case we call the “single-step” case. Context: The reformulation targets the per-iteration improvement objective that on-policy methods already optimize, not the total return, which occupancy-measure and convex-analytic formulations restructure instead. PPO’s clipping falls outside the parameterization, so the framework explains what PPO approximates without recovering it. 2. We give an algorithm that solves this program by sequential convex programming, repeatedly solving a convex approximation while keeping the policy a valid probability distribution, and prove convergence for the true non-convex objective rather than a linear surrogate (Agarwal et al., 2021; Xiao, 2022). Context: The two guarantees differ in strength. The per-update result is unconditional and reaches a stationary point at a standard rate. The policy-sequence result holds only when the update accounts for the full horizon, under one particular trust region, and contracts to a neighborhood of the optimum whose size depends on a state-coverage assumption and on how accurately each update is solved. 3. In our experiments, CCRL’s advantage over PPO grows as the reward depends on coordinating more consecutive decisions, leaving it competitive with PPO on standard control benchmarks and converging markedly faster on a realistic healthcare task, with an 11.3%11.3\% higher area under the training curve. Context: On control, accounting for more steps adds estimation variance without improving credit assignment; on the healthcare task both methods reach the same near-optimal outcome, so the gain is speed, not final performance. All methods are individually tuned under matched interaction budgets. Abstract 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[π/πn]y:= [π/ _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%11.3\% higher area under the training curve. The code is publicly available at: https://github.com/UMass-SCALAR-Lab/Convex-Concave-RL. 1 Introduction Learning a good policy is the defining problem of reinforcement learning (RL) for researchers and, for practitioners, the lever behind much of the current investment in AI, where pushing model capabilities increasingly reduces to more efficient policy learning. The workhorse behind many of these successes, in robotics and increasingly in large language models, is policy-gradient optimization (Schulman et al., 2015; Schulman et al., 2017; Shao et al., 2024), so any structural insight into how it works translates directly into more efficient and reliable learning. At its core, policy-gradient methods optimize the expected return J(π)J(π) of a policy π, an objective that is non-convex even under the direct policy parameterization. Rather than confront this non-convexity in J(π)J(π), prevailing methods optimize a convex single-step surrogate, the Conservative Policy Iteration (CPI) objective (Kakade and Langford, 2002), within a trust region around the current policy; NPG (Kakade, 2002), TRPO (Schulman et al., 2015), PPO (Schulman et al., 2017), and AWR (Peng et al., 2019) all instantiate this template. This surrogate is a biased proxy for J, and optimizing it typically improves the policy one timestep at a time. On problems where several timesteps couple to determine the outcome, this single-step view falls short: the update can move the policy away from the optimum until the value estimates catch up. As a workaround, the multi-step dependence is instead carried by the value or advantage estimates that feed the update, while the policy-optimization objective itself remains a single-step proxy (Sutton, 1988; Schulman et al., 2016). In this work we confront this seemingly unyielding non-convex optimization directly, through a structured reformulation of the RL objective. Our idea is to optimize the exact per-iteration improvement rather than a surrogate of it. The return difference J(π)−J(πn)J(π)-J( _n) is estimable from on-policy trajectories by per-decision importance sampling (PDIS) (Precup et al., 2000), and is non-convex in π only because it contains products of importance ratios. Re-expressing each policy through its log-ratio to the current one, y:=log(π/πn)y:= (π/ _n), converts these products into sums of exponentials and decomposes the objective as a difference of two convex functions, a difference-of-convex (DC) program. We call the resulting framework Convex-Concave Reinforcement Learning (CCRL). The formulation has three consequences. First, it makes the exact objective directly optimizable, rather than only through a surrogate. Second, it unifies existing methods: at horizon k=1k=1 the program reduces to the single-step surrogate optimized by CPI, NPG, TRPO, PPO, and AWR. Third, it exposes the horizon k as a free parameter: k≥2k≥ 2 couples several consecutive decisions within a single update, so one update can credit an action for outcomes several steps later, and k=Hk=H, the full horizon, optimizes the exact, unbiased return. We solve the program by sequential convex programming (SCP), the standard method for DC problems, adapted so that each step preserves a valid policy, and we establish convergence guarantees. What the reformulation changes is the iteration. Each SCP round replaces the objective by a convex approximation that is solved to global optimality, so the objective improves monotonically by construction rather than through a tuned step size, and the iterates approach a stationary point at a known rate. This is bought with computation: a round solves a convex program where a policy-gradient method takes one gradient step. The problem itself remains non-convex, so a stationary point, not a global optimum, is what the iteration delivers. The algorithm we deploy simplifies this procedure. Rather than keeping the policy valid at every round, it enforces validity only once, at the end, and it caps the log-ratios so that the k-step estimates stay well behaved. Enforcing validity only at the end preserves the monotone improvement within an update but forfeits the convergence guarantees (Section 6). The cap is one of two knobs PPO does not have, alongside the truncation depth k, which was the consequential one in our experiments. We evaluate CCRL against a strongly tuned PPO baseline in four settings. On diagnostic MDPs with delayed reward (a risky corridor and increasingly deep risky chains), CCRL’s advantage grows as the delay lengthens. On classic-control tasks (CartPole, Acrobot, MountainCar, and LunarLander) it is competitive with PPO: there, a larger k recovers credit that the dense per-step rewards already supply, while adding the cost of noisier advantage estimates and higher importance-weight variance. On a realistic, stochastic, mid-horizon sepsis task, both reach the same near-optimal survival, but CCRL gets there markedly faster, with an 11.3%11.3\% higher area under the training curve. Contributions. (1) We show that iterative on-policy policy improvement, though non-convex, can be written exactly as a difference of convex log-sum-exp functions, i.e., a difference-of-convex (DC) program, and that methods built on the single-step CPI surrogate are a special case we call the “single-step” case; the framework extends above them along a temporal axis that couples decisions across several steps (Sections 3 and 3.5). (2) We design a sequential convex programming (SCP) approach to solve the reformulated problem, and prove an unconditional O(1/R)O(1/R) rate to a stationary point per policy update and, at k=Hk=H, geometric contraction of the policy sequence to a neighborhood of the optimum under bounded concentrability (Sections 4 and 5). (3) We find that CCRL’s advantage over a strongly tuned PPO grows as reward depends on coordinating more consecutive decisions, that it is competitive with PPO on standard control tasks, and that it converges faster on a stochastic healthcare task (Sections 6 and 7). Beyond the specific algorithm, this difference-of-convex view of policy optimization offers a structural handle on an objective long treated as intractable, and a principled route to policy-gradient methods that exploit multi-step dependencies for more efficient training. 2 Preliminaries Markov decision process. For a set X, let Δ() (X) denote the set of probability distributions over X. We work with a finite-horizon discounted MDP (Puterman, 2014) of horizon H<∞H<∞, given by the tuple (,,p,r,γ,d0)(S,A,p,r,γ,d_0): a finite state set S, a finite action set A, a discount factor γ∈[0,1)γ∈[0,1), and an initial-state distribution d0∈Δ()d_0∈ (S). Capital letters denote random variables: St∈S_t and At∈A_t are the state and action at time t, and Rt+1∈ℝR_t+1 the reward that follows. The transition function p(s′∣s,a):=Pr(St+1=s′∣St=s,At=a)p(s s,a):= (S_t+1=s S_t=s,A_t=a) gives the probability of moving to s′s , and the reward function r(s,a):=[Rt+1∣St=s,At=a]r(s,a):=E[R_t+1 S_t=s,A_t=a] the expected immediate reward. As is standard in the finite-horizon setting, the state includes the time index. A policy π:→Δ()π:S→ (A) acts by π(a∣s):=Pr(At=a∣St=s)π(a s):= (A_t=a S_t=s) and induces a distribution over trajectories τ=(S0,A0,…,SH)τ=(S_0,A_0,…,S_H), pπ(τ)=d0(S0)∏t=0H−1π(At∣St)p(St+1∣St,At)p_π(τ)=d_0(S_0) _t=0^H-1π(A_t S_t)\,p(S_t+1 S_t,A_t). Write Gt:=∑j=tH−1γj−tRj+1G_t:= _j=t^H-1γ^j-tR_j+1 for the discounted return from time t. The state-value Vπ(s):=π[Gt∣St=s]V^π(s):=E_π[G_t S_t=s], action-value Qπ(s,a):=π[Gt∣St=s,At=a]Q^π(s,a):=E_π[G_t S_t=s,A_t=a], and advantage Aπ(s,a):=Qπ(s,a)−Vπ(s)A^π(s,a):=Q^π(s,a)-V^π(s), and the policy performance is J(π):=S0∼d0[Vπ(S0)]J(π):=E_S_0 d_0[V^π(S_0)]. We will also use the discounted state-visitation distribution dπ(s):=ηπ(s)/ZHd^π(s):=η^π(s)/Z_H, where ηπ(s):=∑t=0H−1γtPr(St=s∣π)η^π(s):= _t=0^H-1γ^t (S_t=s π) is the un-normalized state-visitation count (the expected discounted number of visits to s under π), and ZH:=(1−γH)/(1−γ)Z_H:=(1-γ^H)/(1-γ) is its total mass. Iterative on-policy improvement. Our setting is iterative on-policy improvement: at every iteration n, the algorithm samples a batch of trajectories under the current policy πn _n and uses those trajectories to produce an improved candidate π, which then becomes πn+1 _n+1. The objective at each iteration is to maximize J(π)J(π), or equivalently (since J(πn)J( _n) is constant), the one-step improvement J(π)−J(πn)J(π)-J( _n). Because the candidate must be scored from πn _n-data, the search is restricted to a neighborhood of πn _n, where data-based estimates of J(π)−J(πn)J(π)-J( _n) are reliable only when π is close to πn _n. The performance-difference lemma (Kakade and Langford, 2002) expresses the improvement J(π)−J(πn)J(π)-J( _n) as an expectation of πn _n’s advantages under the candidate policy’s distribution, in two equivalent forms: J(π)−J(πn)=ZH⋅S∼dπ[∑aπ(a|S)Aπn(S,a)]⏟state-visitation form=τ∼pπ[∑t=0H−1γtAπn(St,At)]⏟trajectory form.J(π)-J( _n)\;=\; Z_H·E_S d^π\! [ _aπ(a|S)\,A _n(S,a) ]_state-visitation form\;=\; E_τ p_π\! [\, _t=0^H-1γ^t\,A _n(S_t,A_t)\, ]_trajectory form. Both forms require expectations under the candidate policy’s distribution (dπd^π or pπp_π), which are unavailable, whereas the data at hand is collected under πn _n. There are broadly two routes forward. Route 1: Distribution substitution (biased). We can substitute dπnd _n for dπd^π in the state-visitation form, yielding the data-estimable objective L(π,πn):=S∼dπn[∑aπ(a|S)Aπn(S,a)]L(π; _n):=E_S d _n\! [ _aπ(a|S)\,A _n(S,a) ]. This is a biased proxy for J(π)−J(πn)J(π)-J( _n), with bias that is small when π is close to πn _n and grows with the divergence. The substituted objective L is precisely the CPI surrogate of Kakade and Langford (2002), and the basis for the optimization target of NPG (Kakade, 2002), TRPO (Schulman et al., 2015), and PPO (Schulman et al., 2017). Route 2: Distribution correction. We can correct the mismatch exactly by reweighting trajectories with importance-sampling ratios. With single-step IS ratio ρ(s,a):=π(a∣s)/πn(a∣s)ρ(s,a):=π(a s)/ _n(a s), the trajectory form becomes an exact expectation under pπnp_ _n: J(π)−J(πn)=τ∼pπn[∑t=0H−1γt(∏t′=0tρ(St′,At′))Aπn(St,At)].J(π)-J( _n)\;=\;E_τ p_ _n\! [ _t=0^H-1γ^t ( _t =0^tρ(S_t ,A_t ) )A _n(S_t,A_t) ]. (1) This is the per-decision importance-sampling (PDIS) identity (Precup et al., 2000): the cumulative product is an exact distribution correction from pπnp_ _n to pπp_π, recovering the true improvement with no bias, at the cost of variance that grows exponentially with the horizon. To control the variance, we can use two devices: (i) truncating the product to a k-step window (adding bias), (i) constraining π to a trust region around πn _n. k-step PDIS. Truncating the cumulative product in (1) to the most recent k steps gives Jk(π,πn):=τ∼pπn[∑t=0H−1γt(∏t′=max(0,t−k+1)tρ(St′,At′))Aπn(St,At)].J_k(π; _n):=E_τ p_ _n\! [ _t=0^H-1γ^t ( _t = (0,\,t-k+1)^tρ(S_t ,A_t ) )A _n(S_t,A_t) ]. (2) At k=1k=1 the product collapses to the single-step ratio and J1=ZHdπn[⋅]=ZHLJ_1=Z_HE_d _n[·]=Z_H\,L (Route 1); at k=Hk=H no truncation occurs and JH=J(π)−J(πn)J_H=J(π)-J( _n) (Route 2). For 1<k<H1<k<H, k controls a bias-variance tradeoff (Guo et al., 2017). Trust-region constrained problem. Since Jk(π,πn)J_k(π; _n) is a reliable surrogate only when π stays close to πn _n, we must explicitly constrain the candidate to a neighborhood of πn _n. This is the trust-region constraint familiar from TRPO and PPO (Schulman et al., 2015; Schulman et al., 2017), specifically an f-divergence ball Df(π∥πn)≤δD_f(π\,\|\, _n)≤δ (Belousov and Peters, 2017), where δ>0δ>0 is the trust-region size. The divergence DfD_f can be instantiated in several ways, which we cover in Table 3 (Section 3.3). The iteration’s problem reads maxπJk(π;πn)subject toDf(π∥πn)≤δ. _π\;J_k(π; _n) to D_f(π\,\|\, _n)≤δ. (3) 2.1 Non-convexity of general iterative on-policy optimization The iterative on-policy improvement problem (3) is generally non-convex in the policy π. For instance, take the direct parameterization of π, where every state-action pair (s,a)(s,a) has a separate parameter π(a|s)π(a|s). The feasible set here is convex; the space of valid policies Π is a product of probability simplices, and the f-divergence trust region Df(π∥πn)≤δD_f(π\,\|\, _n)≤δ is convex in π as long as the generator f is convex (Belousov and Peters, 2017). The non-convexity lies in the optimization objective Jk(π,πn)J_k(π; _n). At k=1k=1, J1J_1 is linear in π and problem (3) is convex; but for k≥2k≥ 2, the cumulative IS product ∏t′ρ(St′,At′) _t ρ(S_t ,A_t ) is a product of linear functions of π across distinct (s,a)(s,a) pairs along a trajectory, and this multiplicative coupling makes JkJ_k non-convex in π. Gradient-based optimization techniques applied to problem (3) cannot guarantee global optimality of the solution obtained. The optimization problem being non-convex does not mean it is completely structureless, however. Non-convex functions can sometimes be re-cast in forms that enable more effective optimization than generic gradient methods. One such structure is the difference-of-convex (DC) decomposition: a function is DC if it can be written as g−hg-h with both g and h convex. DC programs are well-studied in the optimization theory literature (Tao and An, 1997), though optimizing a difference of convex functions is NP-hard in general. The structure instead gives a principled iteration: linearizing the concave part at the current iterate leaves a convex subproblem solvable to global optimality in polynomial time, and the resulting sequence decreases the objective monotonically and converges to a stationary point, which is more than generic gradient descent guarantees and less than global optimality. In the next section, we show that under a suitable change of variable, the trust-region PDIS problem (3) admits an explicit DC decomposition. 3 Iterative On-Policy Improvement as a Difference-of-Convex Program The k-step PDIS objective Jk(π,πn)J_k(π; _n) is non-convex in π because of the multiplicative IS product across distinct (s,a)(s,a) pairs (Section 2.1). Applying a logarithmic change of variable—a classical geometric-programming technique (Boyd and Vandenberghe, 2004) that turns products into sums inside an exponential—yields an explicit difference-of-convex (DC) decomposition for every k (Theorem 1). This DC structure underlies our algorithm and convergence analysis (Sections 4, 5) and recovers CPI, TRPO, and AWR as (k,α)(k,α) special cases (Section 3.5). 3.1 DC structure of the k-step PDIS objective Let y(s,a):=log(π(a|s)/πn(a|s))∈ℝy(s,a):= (π(a|s)/ _n(a|s)) denote the log-density ratio and, along a trajectory τ, write Ytk:=∑t′=max(0,t−k+1)ty(St′,At′)Y^k_t\;:=\; _t = (0,\,t-k+1)^ty(S_t ,A_t ) (4) for its sum over the k-step window ending at t, and abbreviate Atπn:=Aπn(St,At)A _n_t:=A _n(S_t,A_t). Then ρ(s,a)=ey(s,a)ρ(s,a)=e^y(s,a) and π(a|s)=πn(a|s)ey(s,a)π(a|s)= _n(a|s)\,e^y(s,a), so the IS product over that window is ∏t′ρ(St′,At′)=eYtk _t ρ(S_t ,A_t )=e^Y^k_t, a convex function of y, and the PDIS objective in y-coordinates reads Jk(y)=τ∼pπn[∑t=0H−1γteYtkAtπn]J_k(y)=E_τ p_ _n [ _t=0^H-1γ^te^Y^k_tA _n_t ], a weighted sum of convex exponentials with weights γtAtπnγ^tA _n_t of either sign. Writing (x)+:=max(x,0)(x)_+:= (x,0) and (x)−:=max(−x,0)(x)_-:= (-x,0) for the positive and negative parts, gathering the terms by the sign of the advantage yields a difference-of-convex decomposition. Theorem 1 (DC structure of the k-step PDIS objective). For any k≥1k≥ 1, the k-step PDIS objective decomposes as Jk(y)=Jk+(y)−Jk−(y)J_k(y)=J_k^+(y)-J_k^-(y), where Jk+J_k^+ and Jk−J_k^- collect the terms with positive and with negative advantage: Jk+(y) J_k^+(y) :=τ∼pπn[∑t=0H−1γteYtk(Atπn)+], :=E_τ p_ _n [ _t=0^H-1γ^te^Y^k_t(A _n_t)_+ ], Jk−(y) J_k^-(y) :=τ∼pπn[∑t=0H−1γteYtk(Atπn)−]. :=E_τ p_ _n [ _t=0^H-1γ^te^Y^k_t(A _n_t)_- ]. (5) Both are non-negative-weighted sums of convex exponentials, hence convex (proof in Appendix E.1). 3.2 The space of valid log-density ratios y(s,a)y(s,a) Any policy π defined via π(a|s)=πn(a|s)ey(s,a)π(a|s)= _n(a|s)\,e^y(s,a) must satisfy the per-state probability simplex constraint. That is, for each state s∈s , π(a|s)≥0π(a|s)≥ 0 for all a∈a and ∑aπ(a|s)=1 _aπ(a|s)=1. Of these, the non-negativity is implicitly handled due to ey(s,a)>0e^y(s,a)>0. For the normalization, define the per-state normalizer fs(y):=∑a∈πn(a|s)ey(s,a),s∈,f_s(y)\;:=\; _a _n(a|s)\,e^y(s,a), s , (6) so that ∑aπ(a|s)=fs(y) _aπ(a|s)=f_s(y), and the normalization constraint is exactly fs(y)=1f_s(y)=1 at every state. The set of valid log-density ratios is therefore the validity manifold ℳ:=y∈ℝ||||:fs(y)=1,∀s∈.M\;:=\; \\,y ^|S||A|\;:\;f_s(y)=1,\;\;∀\,s \, \. (7) Each fsf_s is convex in y (a non-negative weighted sum of exponentials of affine maps), so the equality fs(y)=1f_s(y)=1 is a DC constraint: the inequality fs(y)≤1f_s(y)≤ 1 is convex, while fs(y)≥1f_s(y)≥ 1 is reverse-convex. The set ℳM is a smooth embedded manifold of dimension ||(||−1)|S|(|A|-1): the constraint gradients ∇fs(y)∇ f_s(y) have disjoint per-state supports and are never zero (each has strictly positive entries within its state block), so they are linearly independent at every y, and the implicit function theorem applies. 3.3 Representing f-divergence trust region constraints in terms of log-density ratios Since y is the optimization variable, the trust region must be expressed in y as well, and a general f-divergence does not survive that substitution in a usable form. We therefore work with Amari’s α-divergence family (Amari, 1985): for distributions p and q on a common domain and a parameter α∈ℝ∖0,1α \0,1\, Dα(p∥q):=1α(α−1)(X∼q[(p(X)/q(X))α]−1).D_α(p\|q):= 1α(α-1) (E_X q [(p(X)/q(X))^α ]-1 ). (8) The ratio enters as a power (π/πn)α(π/ _n)^α, so the same logarithmic change of variable turns it into eαye^α\,y (Section 3.1), keeping the trust region in the exponential-of-affine form the DC analysis needs. While it does not represent every possible divergence, specific choices of α recover the ones commonly used in RL, which we list in Table 4 in Appendix C. Beyond the divergence, three trust-region forms are common—trajectory-level, strict per-state, and expected per-state; under the log-density transform π(a|s)=πn(a|s)ey(s,a)π(a|s)= _n(a|s)\,e^y(s,a) each becomes an exponential-of-affine (eαye^α y) constraint. Their f-divergence and α-divergence forms are collected in Appendix C (Table 3). Proposition 2 (Trust-region convexity, finite α). For every finite α∈ℝ∖[0,1]α [0,1], all three α-divergence forms in Table 3 are convex in y on all of ℝ||||R^|S||A|. In the limit α→0−α→ 0^- (reverse KL, KL(πn∥π)KL( _n\|π)), the per-state divergence converges to −∑aπn(a|s)y(s,a)- _a _n(a|s)\,y(s,a), which is linear—hence convex—in y, everywhere. In the limit α→1+α→ 1^+ (forward KL, KL(π∥πn)KL(π\| _n)), the limit exists only on the validity manifold ℳM, where it equals ∑aπn(a|s)ey(s,a)y(s,a) _a _n(a|s)\,e^y(s,a)\,y(s,a). The proof is in Appendix C. In practice we use a finite α∉[0,1]α∉[0,1] (χ2χ^2, α=2α=2), globally convex in y. 3.4 Full iterative on-policy improvement problem in log-density ratios We now combine the DC objective (Theorem 1) defined over the validity manifold under a trust-region constraint form from Table 3 (with finite α∉[0,1]α∉[0,1]) into a single optimization problem at each policy iteration: maxy∈ℝ||||Jk+(y)−Jk−(y)(DC objective)s.t.Dα(π∥πn)≤δ(trust region, convex)fs(y)=1,∀s∈(validity, DC) aligned _y ^|S||A| &J_k^+(y)-J_k^-(y)&&(DC objective)\\ s.t. &D_α(π\,\|\, _n)≤δ&&(trust region, convex)\\ &f_s(y)=1, ∀\,s &&(validity, DC) aligned (9) We call this the Convex-Concave Reinforcement Learning (CCRL) formulation: a DC objective under a DC (validity) equality and a convex (trust-region) inequality. 3.5 Relationship between CCRL and the prevalent trust-region based on-policy algorithms CPI (Kakade and Langford, 2002), NPG (Kakade, 2002), TRPO (Schulman et al., 2015), and AWR (Peng et al., 2019) are popular methods for iterative on-policy policy optimization. Proposition 3 (CPI/NPG/TRPO/AWR objective recovery). At k=1k=1, the CCRL objective reduces to the CPI surrogate: J1(y)=ZHL(π,πn)J_1(y)=Z_H\,L(π; _n), where L(π,πn)L(π; _n) approximates the candidate policy π’s performance from data sampled under the current iterate πn _n. Since ZH>0Z_H>0 is a constant in y, the two objectives have the same maximizers under any common constraint set. The same surrogate is optimized by NPG, TRPO, and AWR (proof in Appendix E.2). Further, the main distinguishing factor among these approaches comes from the trust-region constraints employed. Both TRPO and AWR use the expected per-state form, differing in the direction of the KL divergence. TRPO constrains S∼dπn[KL(πn(⋅|S)∥π(⋅|S))]E_S d _n[KL( _n(·|S)\,\|\,π(·|S))], the reverse KL with respect to the candidate. NPG optimizes this same objective under a reverse-KL proximity as well, but realizes it in parameter space through a Fisher-matrix (quadratic-KL) step rather than an exact constraint; at the level our formulation captures—the objective and the divergence direction—it thus coincides with the TRPO program. AWR constrains S∼dπn[KL(π(⋅|S)∥πn(⋅|S))]E_S d _n[KL(π(·|S)\,\|\, _n(·|S))], the forward KL. This is the one endpoint of the α-family whose log-ratio form is confined to the validity manifold (Proposition 2), which is consistent with AWR dropping the validity constraint and normalizing post-hoc; we therefore handle this correspondence in policy space. Detailed derivations are provided in Appendices E.2 and E.3. Thus, the CCRL framework enables unified treatment of these existing approaches. More importantly, it extends beyond them along two axes: increasing k allows us to incorporate longer temporal dependence between decisions into the policy optimization and varying α enables a choice among different divergences. 4 Policy optimization using Sequential Convex Programming (SCP) 4.1 Solving the DC-constrained DC program Given the data collected under πn _n, the PDIS estimators of Jk+J_k^+ and Jk−J_k^- turn problem (9) into a concrete DC-constrained DC program in y; we work with the minimization objective Φ:=Jk−Jk+ :=J_k^--J_k^+ and the validity manifold ℳ:=y:fs(y)=1,∀s∈M:=\y:f_s(y)=1,\ ∀ s \. Its natural solver is sequential convex programming (SCP) (Tao and An, 1997; Lipp and Boyd, 2016): repeatedly form a convex approximation around the current anchor yr∈ℳy^r , solve it, and use the solution as the next anchor. The textbook version breaks on our program; we show why, then give the modification that fixes it. Textbook SCP degenerates. The standard SCP recipe treats the validity equality fs(y)=1f_s(y)=1 as an inequality pair: keep the convex side fs(y)≤1f_s(y)≤ 1 as-is, and linearize the reverse-convex side fs(y)≥1f_s(y)≥ 1 at the anchor to ∇fs(yr)⊤(y−yr)≥0∇ f_s(y^r) (y-y^r)≥ 0. On our program this freezes the iteration. Proposition 4 (Degeneracy of the textbook split). If fs(yr)=1f_s(y^r)=1 for all s, the linearized feasible set collapses to the anchor, y:fs(y)≤1,∇fs(yr)⊤(y−yr)≥0∀s=yr \y:f_s(y)≤ 1,\ ∇ f_s(y^r) (y-y^r)≥ 0\ ∀ s \=\y^r\, so the subproblem cannot move (proof in Appendix B.5). Our fix: tangent-plane linearization with a softmax retraction. We modify SCP in two ways. First, linearize validity as an equality—replace the inequality pair with the single tangent plane Tr:=y:∇fs(yr)⊤(y−yr)=0,∀sT_r:=\y:∇ f_s(y^r) (y-y^r)=0,\ ∀ s\—so the iterate moves freely within TrT_r. Second, since the tangent-plane solution generally leaves ℳM, restore validity exactly with a per-state renormalization, which is just the softmax already used in practice. Writing the linearized objective as Φ~r(y):=Jk−(y)−∇Jk+(yr)⊤y _r(y):=J_k^-(y)-∇ J_k^+(y^r) y, a round from anchor yry^r is then (Step 1)y^r+1 (Step 1) y^r+1 =argminy∈r(Φ~r(y)+ρ2‖y−yr‖2), \;=\; _y _r\; ( _r(y)\,+\, ρ2\|y-y^r\|^2 ), (10) r _r :=y:Dα(y)≤δ,∇fs(yr)⊤(y−yr)=0∀s,y≥br, := \\,y\;:\;D_α(y)≤δ,\;∇ f_s(y^r) (y-y^r)=0\;∀ s,\;y≥ b_r\, \, (11) (Step 2)yr+1(s,a) (Step 2) y^r+1(s,a) :=y^r+1(s,a)−logfs(y^r+1), \;:=\; y^r+1(s,a)- f_s( y^r+1), (12) where Step 2 is, in policy space, the per-state softmax πr+1(a|s)∝πn(a|s)ey^r+1(s,a) _r+1(a|s) _n(a|s)\,e y^r+1(s,a) that practical pipelines already apply when turning log-ratios into a policy. Step 1 linearizes the concave-side objective −Jk+-J_k^+ at yry^r over TrT_r, subject to the trust region—imposed exactly, with no margin—and (for α>1α>1) a scheduled support floor y≥bry≥ b_r, ymin(s,a):=log(pmin/πn(a|s))y_ (s,a):= (p_ / _n(a|s)), which keeps the feasible set compact (Section 5.1). Step 2 gives fs(yr+1)=1f_s(y^r+1)=1 at every state by construction. Validity and the trust region survive the retraction; the floor is relaxed by a controlled amount. The retraction subtracts a non-negative constant cs=logfs(y^r+1)≥0c_s= f_s( y^r+1)≥ 0 from each state block, which for α>1α>1 can only lower the trust-region value DαD_α (Lemma 14), so no margin is needed. Only this last step restricts α: the retraction itself is defined for every α, and Remark 2 treats the excluded cases. An O(1/ρ)O(1/ρ) relaxation of the floor, bounded by the descent telescope, keeps yr+1y^r+1 feasible for the next round (Appendix F); the proximal weight ρ controls it directly. Recovering the policy. After R rounds, the final iterate yRy^R satisfies fs(yR)=1f_s(y^R)=1 exactly and defines the next policy directly: πn+1(a|s)=πn(a|s)eyR(s,a), _n+1(a|s)\;=\; _n(a|s)\,e^y^R(s,a), (13) a valid distribution at every state. For parametric policy classes, the right-hand side is the target distribution to which πθ _θ is fit by maximum likelihood (Section 6). To summarize, each policy iteration collects episodes under πn _n, fits the critic to obtain advantage estimates A^πn A _n, initializes y0=0y^0=0 (that is, π=πnπ= _n, which lies on ℳM), runs R rounds of Steps 1–2, and recovers πn+1 _n+1 via (13); Algorithm 1 in Appendix A states this in full, additionally tracking the support-floor schedule. The modified iteration retains the guarantees of textbook SCP: monotone descent and convergence to a directional-stationary (d-stationary) point (defined in Appendix D), made precise in Section 5. 5 Convergence Analysis We now state what the algorithm guarantees. Prior policy-gradient analyses prove global k=1k=1 under tabular direct parameterization (Mei et al., 2020; Agarwal et al., 2021; Xiao, 2022); outside it, the general treatment falls back to gradient stationarity (Agarwal et al., 2022). Our exact objective at k=Hk=H is non-convex, yet its DC structure lets us do better. We give an inner-loop guarantee (convergence of the SCP rounds within one policy iteration) and an outer-loop guarantee (contraction of the policy sequence). All results assume the direct parameterization on log-density ratios; full statements and proofs are in Appendix F. 5.1 Inner-loop convergence The analysis below uses the strict per-state trust region and a moving floor brb_r (Eq. (22)). It starts at ymin(s,a)=log(pmin/πn(a|s))y_ (s,a)= (p_ / _n(a|s)) and converges to b∞≥ymin−B(ρ)b_∞≥ y_ -B(ρ)1. The compact limiting feasible set is ℱ∞=y:Dαs(y)≤δ∀s,fs(y)=1∀s,y≥b∞F_∞=\y:D_α^s(y)≤δ\ ∀ s,\ f_s(y)=1\ ∀ s,\ y≥ b_∞\. All stationarity statements refer to this set; the nominal floor need not be preserved by retraction. Write z^r=y^r+1−yr z_r= y^r+1-y^r. The bound on this proximal-step residual below gives an approximate first-order certificate. At a fixed point, it is zero and the point is d-stationary under the linear independence constraint qualification (LICQ), which makes the linearization faithful to the local geometry (Proposition 11). Theorem 5 (Inner-loop convergence, strict per-state trust region). Fix α>1α>1, δ>0δ>0, a full-support tabular πn _n, and 0<pmin≤mins,aπn(a|s)0<p_ ≤ _s,a _n(a|s) with ||pmin<1|A|p_ <1. Run the exact tangent-plane subproblem with the floor schedule and choose ρ as in Proposition 16. With ρ0=LΦLf|||| _0=L_ L_f |S||A| and the fixed enlarged box KextK_ ext defined there, (i) Every subproblem is feasible, the retracted iterates are valid and trust-region feasible, and Φ(yr+1)≤Φ(yr)−(ρ−ρ0)‖z^r‖2/2 (y^r+1)≤ (y^r)-(ρ- _0)\| z_r\|^2/2. (i) For every R≥1R≥ 1, minr<R‖z^r‖2≤2[Φ(y0)−infKextΦ]/[(ρ−ρ0)R] _r<R\| z_r\|^2≤ 2[ (y^0)- _K_ ext ]/[(ρ- _0)R]. In particular, z^r→0 z_r→ 0. (i) Every limit point lies in ℱ∞F_∞ and is d-stationary for Φ over ℱ∞F_∞ if LICQ holds for its active validity, trust-region, and floor constraints. This is the standard proximal-DC guarantee profile (Tao and An, 1997; Razaviyayn et al., 2013; Lipp and Boyd, 2016); d-stationarity is the strongest first-order notion available here—stronger than the gradient stationarity a gradient-based analysis gives. 5.2 Outer-loop convergence The inner guarantee concerns one policy iteration; we now bound the outer policy sequence π0,π1,… _0, _1,…. We specialize to exact PDIS (k=Hk=H), which removes surrogate bias (JH=J(π)−J(πn)J_H=J(π)-J( _n)), and to strict per-state χ2χ^2 trust regions (α=2α=2). Write Δn:=J(π∗)−J(πn) _n:=J(π^*)-J( _n) for the optimality gap, ϵn≥0 _n≥ 0 for the inner-solve gap (how far the SCP solve at iteration n falls short of its global minimum; zero when solved exactly), and ϵ¯:=supnϵn ε:= _n _n. Theorem 6 (Outer-loop contraction). Assume separately that a support floor πn(a|s)≥pmin _n(a|s)≥ p_ holds on all outer iterates (with ||pmin<1|A|\,p_ <1) and bounded concentrability maxn,sdπ∗(s)/dπn(s)≤C∞ _n,sd^π^*(s)/d _n(s)≤ C_∞. Then there are constants c∈(0,1)c∈(0,1) and β≥0β≥ 0 (explicit in Appendix F.9) with J(πn+1)−J(πn)≥cΔn−β−ϵn,henceΔN≤(1−c)NΔ0+β+ϵ¯c.J( _n+1)-J( _n)\;≥\;c\, _n-β- _n, _N\;≤\;(1-c)^N _0+ β+ εc. (14) Telescoping gives geometric contraction to a neighborhood of radius (β+ϵ¯)/c(β+ ε)/c, with the floor bias β→0β→ 0 as pmin→0p_ → 0. The bound is conditional: neither the common outer support floor nor the global inner value gap ϵ¯ ε follows from the inner stationarity result. It is informative when ϵ¯ ε is small. The rate c degrades with horizon (a (1−λ)H−1(1-λ)^H-1 factor from the CPI-style mixture argument) and coverage C∞C_∞—comparable to the tabular linear rates, but proven for the exact multi-step objective (Appendix F). 6 Practical implementation of CCRL The theoretical algorithm keeps the policy valid inside the SCP loop—via the tangent-plane subproblem (10), its per-round softmax retraction, and the support-floor schedule—whereas the deployed version makes three changes for practicality. (i) It replaces the tangent-plane subproblem and retraction with the plain trust-region convex program yr+1=argminy(Jk−(y)−∇Jk+(yr)⊤y+ρ2∥y−yr∥2)s.t.Dα(y)≤δ,∥y∥∞≤ymax,y^r+1= _y (J_k^-(y)-∇ J_k^+(y^r) y+ ρ2\|y-y^r\|^2 )\ \ s.t.\ \ D_α(y)≤δ,\ \ \|y\|_∞≤ y_ , (15) dropping the validity constraint, retraction, and floor schedule—validity is restored only once, by the final recovery softmax. (i) The added box constraint ‖y‖∞≤ymax\|y\|_∞≤ y_ (a y-clip) bounds every log-ratio so the k-step importance weights e∑ye^Σ y cannot overflow; being products of k exponentials, those weights also make it a variance knob—tightening ymaxy_ trades a little bias for lower variance (Appendix G.4). (i) The exact recovery (13) becomes a target π~n+1(a|s)∝πθn(a|s)eyR(s,a) π_n+1(a|s) _ _n(a|s)\,e^y^R(s,a) that a parametric policy πθ _θ is fit to by maximum likelihood. Only the first change bears on the convergence theory: restoring validity once at the end rather than each round keeps the monotone inner-loop descent but forgoes the guarantees that rely on in-loop validity—per-round feasibility (Proposition 16), limit-point d-stationarity (Theorem 5(i)), and outer-loop contraction (Theorem 6). 7 Experiments We evaluate CCRL against strong on-policy baselines to answer four questions. (i) Does multi-step PDIS (k≥2k≥ 2) recover credit that the single-step CPI surrogate (k=1k=1) misses (Section 7.1)? (i) Do those gains amplify as the dependency horizon deepens (Section 7.2)? (i) How does CCRL compare against strong baselines on standard classic-control benchmarks (CartPole, Acrobot, MountainCar, LunarLander; Section 7.3)? (iv) Does the multi-step objective help on a realistic, stochastic task (Section 7.4)? Every method is tuned independently under matched per-iteration budgets. 7.1 Multi-step credit propagation via k>1k>1 truncated PDIS s0s_0sLs_LsRs_RsTs_TsTs_TsTs_TL,r=−20L,\ r=-20R,r=+3R,\ r=+3a1,r=+100a_1,\ r=+100a2,r=−80a_2,\ r=-80a0,r=+1a_0,\ r=+1 (a) Risky Corridor MDP. (b) Normalized expected return. (c) Policy-space trajectory. Figure 1: Risky Corridor MDP and convergence behavior across PPO, TRPO, AWR, and CCRL. A “pay-now-gain-later” MDP designed to test how locally greedy behavior by CPI surrogate methods can lead to slow convergence: the rewarding path at s0s_0 requires paying an immediate loss in exchange for a large downstream payoff, while the safe alternative pays a small immediate reward and yields a low total return. All methods use the same per-iteration interaction budget (3232 episodes per update, 1010 updates) and are individually hyperparameter-tuned (protocol in Appendix G.2). (a) The MDP; (b) expected return over policy iterations, normalized so that 11 is optimal and 00 is the uniform-policy return (mean over 100100 seeds; shaded band is ±1± 1 SE): CCRL is the only method to reach 90%90\% of optimal in under two iterations and also achieves the highest area under the learning curve (quantitative numbers in Appendix G.2); (c) policy trajectory in (q,u)=(π(aL|s0),π(a1|sL))(q,u)=(π(a_L|s_0),\,π(a_1|s_L)) space, from uniform (0.5,0.5)(0.5,0.5) toward the optimum (1,1)(1,1), over the normalized-return landscape (shading red-to-green for low-to-high return, with labelled contours): all methods identify the rewarding action at sLs_L, only CCRL commits to the pay-now direction at s0s_0. The Risky Corridor (Figure 1(a)) places a pay-now/gain-later choice at s0s_0: the optimal action L pays an immediate loss for a large downstream payoff, while the safe action R yields a small reward into a low-return basin. Under the uniform policy this inverts the local signal—Aπb(s0,L)=−7A _b(s_0,L)=-7 (Appendix G.1)—so a k=1k=1 update reads the negative advantage as evidence against the optimal action, whereas k=2k=2 couples s0s_0 with sLs_L and can commit to L once the downstream action is identified. We compare PPO, TRPO, AWR, and CCRL (k=2k=2) over 100100 seeds under a common budget of 3232 episodes per update over 1010 updates, with per-method tuning (Appendix G.2). All four methods come close to the optimum (final normalized return 0.9660.966–0.99960.9996; Appendix G.2) but differ in speed: CCRL reaches 90%90\% of optimal in 1.381.38 iterations on average—the only method under two—against 3.293.29, 3.133.13, and 2.092.09 for PPO, TRPO, and AWR. Figure 1(c) shows the mechanism: all four identify the downstream action at sLs_L within roughly one iteration, but only CCRL simultaneously commits to L at s0s_0; the k=1k=1 methods first move away from L in response to its locally negative advantage. This supports (i)—the k=2k=2 surrogate recovers credit the k=1k=1 methods miss—and the pathology sharpens as the reward chain lengthens, which we study next. 7.2 Gains amplify with dependency horizon The Risky Chain (Figure 5) generalizes the corridor to N stages: the large terminal reward is reachable only by continuing through all N−1N-1 stages and then taking the correct terminal action (optimal return 100−5(N−1)100-5(N-1)). The corridor of Section 7.1 is the N=2N=2 case; with γ=1γ=1 we vary N∈4,5,6N∈\4,5,6\ to test whether the multi-step advantage seen there grows with the dependency horizon, as that analysis predicts. We benchmark CCRL against PPO (the most widely used iterative on-policy method), tuning both identically: (i) an equal budget—128128 trajectories per update and 200200 iterations, each (algorithm, N, k) cell tuned from scratch; (i) the entropy bonus swept over the same grid for both, so PPO is never starved of exploration; and (i) an exhaustive grid search—we rank every configuration on 1010 tuning seeds by nAUC, keep the top 1212, and report the best of those on 300300 validation seeds disjoint from the tuning seeds (full grids in Appendix G.5). Table 1: PPO vs. CCRL on the Risky Chain. For each depth N we report the final normalized return (F; ↑ , 11=optimal, 00=uniform-policy return), nAUC (↑ ; mean normalized return over the 200200 training iterations), and t90t_90 (↓ ; iterations to reach 90%90\% of optimal), each as mean over 300300 validation seeds with the stderr in parentheses in units of the last displayed digit (e.g. 0.939(13)=0.939±0.0130.939(13)=0.939± 0.013, 9.4(23)=9.4±2.39.4(23)=9.4± 2.3). Best per metric column (within each N) in bold. Full-depth CCRL reaches 90%90\% of optimal within about one iteration at every N and ends at a normalized return of 1.0001.000, whereas PPO’s final return and t90t_90 steadily degrade as the chain deepens. N=4N=4 N=5N=5 N=6N=6 Method F↑ nAUC↑ t90↓t_90\! F↑ nAUC↑ t90↓t_90\! F↑ nAUC↑ t90↓t_90\! PPO 0.939(13) 0.937(12) 3.9(13) 0.920(15) 0.920(14) 5.4(16) 0.916(15) 0.916(14) 9.4(23) CCRL k=1k=1 1.000(0) 0.997(0) 1.3(0) 0.980(8) 0.975(8) 5.7(16) 1.000(0) 0.995(0) 1.6(0) CCRL k=2k=2 0.990(6) 0.987(6) 3.2(11) 0.960(11) 0.957(11) 9.2(23) 1.000(0) 0.996(0) 1.4(0) CCRL k=3k=3 0.990(5) 0.987(5) 3.2(12) 0.997(3) 0.991(3) 2.3(7) 1.000(0) 0.996(0) 1.4(0) CCRL k=4k=4 1.000(0) 0.997(1) 1.2(1) 0.996(4) 0.989(5) 2.7(9) 0.996(4) 0.993(4) 2.0(7) CCRL k=5k=5 −- −- −- 1.000(0) 0.996(1) 1.2(1) 0.996(4) 0.993(4) 2.0(7) CCRL k=6k=6 −- −- −- −- −- −- 1.000(0) 0.996(0) 1.3(0) Results. We measure the final normalized return (11=optimal, 00=uniform), the normalized area under the learning curve (nAUC, the mean normalized return over the 200200 iterations), and t90t_90, the iterations needed to reach 90%90\% of optimal. Full-depth CCRL (k=Nk=N) reaches 90%90\% of optimal within about one iteration at every depth (t90≤1.3t_90≤ 1.3 for N≥4N≥ 4) and converges to a normalized return of 1.0001.000. Tuned PPO, by contrast, degrades steadily as the chain lengthens: its final return falls from 0.9390.939 at N=4N=4 to 0.9200.920 and 0.9160.916 at N=5,6N=5,6, and its t90t_90 climbs from 3.93.9 to 9.49.4 iterations. Since the two methods share the same networks and budget, this widening gap points to the policy-improvement operator rather than to capacity or budget, and it is sharpest in t90t_90—flat in N for CCRL but growing for PPO, the O(1)O(1)-vs-O(N)O(N) signature of one-step bootstrapping whose error compounds with depth. Among CCRL depths, k=Nk=N is best or tied on every metric at every N and uniquely fastest to the 90%90\% threshold, while intermediate k is occasionally non-monotonic (per-arm tuning variance). Together these support question (i): the multi-step advantage grows with the dependency horizon. 7.3 CCRL is competitive on classic control Figure 2: Classic control: CCRL vs. PPO over 100100 seeds. Return over 200200 iterations (mean over 100100 seeds; shaded band is ±1± 1 SE) for PPO and CCRL at k∈1,2,3k∈\1,2,3\ on CartPole, Acrobot, MountainCar, and LunarLander. CCRL (k=1k=1) is competitive with PPO across all tasks, while larger k degrades performance—most visibly on CartPole and LunarLander—since the added variance of a larger window outweighs its credit-assignment benefit on these tasks (Section 7.3). This experiment tests question (i): whether CCRL holds up against a strong PPO baseline on standard control. On four discrete-action benchmarks (CartPole, Acrobot, MountainCar, LunarLander) we compare tuned PPO against CCRL at k∈1,2,3k∈\1,2,3\, each tuned per configuration and run over 100100 seeds for 200200 iterations (Figure 2; setup in Appendix G.7). At k=1k=1 CCRL is competitive with PPO—matching it on CartPole and Acrobot and trailing modestly on the harder-exploration MountainCar and LunarLander—but does not outperform it. In contrast to the chain, increasing k here hurts: convergence speed and final return degrade monotonically from k=1k=1 to 33, most sharply on CartPole and LunarLander. Why k>1k>1 does not help here. We cannot rule out multi-step coupling in these environments; what we can say is that the conditions are unfavourable for exploiting it. Dense per-step rewards already supply a usable learning signal, so the marginal benefit of a wider window is small, while two costs grow with k over these long episodes. First, sensitivity to advantage-sign error. Where a gradient method merely follows a noisy advantage, CCRL’s DC reformulation uses the sign of Aπn(s,a)A _n(s,a) to place each trajectory term into the convex component Jk+J_k^+ or Jk−J_k^- (Theorem 1); a single sign flip therefore moves a term to the wrong side of the decomposition and perturbs the optimized objective itself, not just the step direction, and a k-step term aggregates k advantages so this corruption compounds with depth. The critic is unreliable exactly where this bites: on CartPole, sign agreement with near-exact Monte-Carlo advantages stays below 70%70\% and decays as the policy improves and advantages shrink toward zero (Appendix G.3). Second, estimator variance. The k-step objective weights each term by the cumulative importance ratio e∑t′y(St′,At′)e _t y(S_t ,A_t ); being the exponential of a k-term sum of log-ratios, its variance blows up—by two to three orders of magnitude per unit increase in k (Appendix G.4)—so the per-update objective grows progressively noisier. Together these dominate what benefit a wider window offers here, which is why performance degrades monotonically in k. This is a statement about the conditions, not about the objective: it suggests widening the window selectively—per state or per iteration—rather than uniformly, which we leave to future work. Where credit is deep and sparse throughout (Sections 7.2, 7.4), a uniform k already suffices. 7.4 CCRL can outperform PPO on a stochastic, medium-horizon task Sepsis care is a canonical sequential-decision problem in clinical RL (Komorowski et al., 2018; Oberst and Sontag, 2019): a clinician treats a patient whose condition evolves stochastically, with survival revealed only at the end of the episode. Crucially, many first-line therapies act only once built up to a therapeutic level, so their benefit is realized several decisions after treatment begins. Our Therapeutic-Threshold Sepsis MDP captures this. A state pairs illness severity h with an accumulated dose d, and at each of H=20H=20 steps the clinician chooses to rest, dose (advance d toward the therapeutic threshold, with no immediate benefit), or administer (a high-probability recovery once the threshold d=D−1d=D-1 is reached, but ineffective and dose-resetting otherwise). Survival, a sparse terminal reward, is thus earned only by carrying the patient through D preparatory doses and then administering, so the payoff is separated from the actions that earn it by the full depth D. With M=5M=5 severity levels and D=3D=3 doses to threshold, the optimal policy survives 84.0%84.0\% of episodes (full dynamics in Appendix G.6). In this regime, credit is genuinely multi-step (each preparatory dose has a negative one-step advantage, so a k=1k=1 method like PPO is initially misled away from dosing), while the moderate horizon keeps the advantage structure learnable and the one real threat, transition variance, is controllable with a tight y-clip. Since data is the binding constraint in clinical RL, we compare how quickly each method reaches a good policy, sweeping each method’s variance knob (CCRL’s ymaxy_ , PPO’s ε ) with the remaining hyperparameters sub-tuned (parametric MLP; 500500 updates; 100100 seeds; Table 2(a)). Trained to convergence both reach the same near-optimal survival (CCRL 0.828±0.0090.828±0.009, PPO 0.822±0.0090.822±0.009; ≈98%≈\!98\% of the 0.8400.840 optimum), so the task does not separate them at the endpoint—it separates them on speed: CCRL’s mean survival over training is 0.815±0.0080.815±0.008 versus PPO’s 0.732±0.0090.732±0.009, i.e. CCRL is near-optimal almost from the start while PPO climbs slowly. Both levers are necessary: at a loose clip the k>1k>1 objective is too noisy to help (Table 2(b): deeper truncation collapses to 0.110.11 at k=3k=3, ymax=5y_ =5), while tightening ymaxy_ makes every depth usable and lets multi-step credit resolve the negative-advantage dosing that PPO reaches only slowly. PPO (clip ε ) CCRL k=2k=2 (clip ymaxy_ ) ε F↑ nAUC↑ ymaxy_ F↑ nAUC↑ 0.050.05 0.822(9) 0.732(9) 1.01.0 0.828(9) 0.815(8) 0.100.10 0.771(21) 0.709(11) 1.51.5 0.796(19) 0.786(18) 0.200.20 0.765(23) 0.693(16) 2.02.0 0.778(22) 0.762(22) 0.300.30 0.754(24) 0.689(16) 3.03.0 0.719(29) 0.684(30) 0.500.50 0.736(28) 0.652(22) 5.05.0 0.750(25) 0.681(25) (a) Each method’s variance knob swept. final survival ↑ k \, \,y_ 55 33 22 22 0.721(28) 0.708(30) 0.760(24) 33 0.110(29) 0.504(41) 0.603(38) 44 0.251(39) 0.434(42) 0.552(40) (b) CCRL vs. depth k and clip ymaxy_ . Table 2: Therapeutic-Threshold Sepsis (parametric MLP; 100100 seeds; 500500 updates; DP-optimal survival 0.8400.840). Values are mean over seeds with the standard error in parentheses in units of the last digit (e.g. 0.822(9)=0.822±0.0090.822(9)=0.822±0.009). (a) Final survival and nAUC (mean survival over training): with each variance knob tuned, PPO and CCRL converge to the same final survival (≈0.82≈ 0.82), but CCRL’s nAUC is far higher—it reaches near-optimal survival much sooner. Best per column in bold. (b) Controlled sweep isolating the mechanism: tightening ymaxy_ makes multi-step credit usable at every depth (row-max in bold), while a loose clip collapses deep k. 8 Related Work CCRL connects to three lines of work, each discussed in the paper where it is used: the CPI-surrogate family it generalizes (CPI, NPG, TRPO, AWR; Section 3.5); multi-step credit-assignment methods that shape the value or advantage target rather than the objective (TD(λ), GAE, Retrace); and the difference-of-convex and policy-gradient-convergence literatures our analysis builds on (Section 5). Closest in spirit is POIS (Metelli et al., 2018), which likewise treats importance sampling as an optimization objective; CCRL differs by exposing its difference-of-convex structure and using the truncation depth k to couple consecutive decisions. A comprehensive, fully-referenced treatment is given in Appendix H. 9 Conclusion This work studied iterative on-policy improvement as a log-sum-exp difference-of-convex (DC) program and proposed Convex-Concave RL (CCRL), which recovers CPI, NPG, TRPO, and AWR as special cases and extends them along the divergence order α and the truncation depth k. Theoretically, we established an unconditional O(1/R)O(1/R) inner-loop stationarity guarantee for any k and, at the exact-improvement setting k=Hk=H with a χ2χ^2 trust region, a conditional geometric contraction of the outer policy sequence under bounded concentrability. Empirically, on the risky corridor and chain MDPs the multi-step objective recovered credit that single-step methods missed, with a margin that widened as the chain deepened. On classic control it is competitive with PPO but not consistently better, which we attribute to noisy advantage estimates and k-step PDIS variance; on a stochastic, horizon-2020 clinical task it shows a convergence edge. Limitations and open directions. CCRL brings convex-optimization machinery to policy optimization, subject to several limitations. Each policy iteration runs several SCP rounds and is therefore more expensive than PPO’s single gradient step; the truncation depth k is an additional knob that can be delicate to tune; and the theory leans on relatively strong assumptions—bounded concentrability and a globally solved inner problem for the outer-loop contraction, and α>1α>1 (excluding the reverse-KL endpoint) for the inner-loop analysis. Promising directions include (1) variance reduction for the k-step couplings, (2) estimating appropriate couplings k dynamically (per state or per iteration), (3) scaling to larger, higher-dimensional domains, and (4) sharper convergence analysis giving full-sequence bounds for the inner loop. Contributions Authors and their abbreviations: Shripad Deshmukh: SD, Yaswanth Chittepu: YC, Dhawal Gupta: DG, Philip Thomas: PT, Scott Niekum: SN. Individual author contributions: SD: Through ideation with YC and DG, SD formalized multi-step trust-region policy improvement as a difference-of-convex (DC) program. PT and SN advised on different aspects of this formalization. With YC’s help, SD designed a sequential convex programming (SCP)-based algorithm for convex-concave RL. He also designed failure-case MDPs for current surrogate-objective methods, made theoretical connections to existing policy gradient methods, scaled up the experiments, diagnosed the current limitations of SCP-based CCRL, and identified a realistic healthcare use case demonstrating its effectiveness over PPO. With the help of AI tools, SD developed the convergence theory for the framework and contrasted it with existing convergence analyses of policy gradient methods in RL. Finally, he wrote the manuscript under the guidance of PT and SN, with suggestions from YC and DG. YC: YC helped SD develop the DC programming formalism, which originated from earlier unsuccessful attempts to frame the policy improvement objective as a geometric program. DG: DG contributed to the early ideation underlying CCRL, drawing on prior work on trust-region policy improvement with batch reuse developed with collaborators. In particular, DG brought the importance-weighted policy improvement perspective and contributed the idea of using log importance ratios, y(s,a)y(s,a), as the optimization variables, motivated by the useful convex structure this parameterization exposes. PT: PT advised on the development of the formalization, methods, and experiments, and provided feedback on early drafts. SN: SN advised on the development of the formalization, methods, experiments, and writing. References Agarwal et al. (2022) A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun Reinforcement learning: theory and algorithms. Note: Monograph draftAvailable at https://rltheorybook.github.io/ Cited by: Appendix H, §5. Agarwal et al. (2021) A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. External Links: Link Cited by: Appendix H, item 2, §5. Alfano et al. (2023) C. Alfano, R. Yuan, and P. Rebeschini A novel framework for policy mirror descent with general parameterization and linear convergence. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: Appendix H. Amari (1985) S. Amari Differential-geometrical methods in statistics. Lecture Notes in Statistics, Vol. 28, Springer. Cited by: §3.3. Belousov and Peters (2017) B. Belousov and J. Peters F-divergence constrained policy improvement. arXiv preprint arXiv:1801.00056. Cited by: §2.1, §2. Boyd et al. (2007) S. Boyd, S. Kim, L. Vandenberghe, and A. Hassibi A tutorial on geometric programming. Optimization and Engineering 8 (1), p. 67–127. Cited by: Appendix H. Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe Convex optimization. Cambridge University Press. Cited by: §3. Cen et al. (2022) S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research 70 (4), p. 2563–2578. External Links: Document Cited by: Appendix H. Guo et al. (2017) Z. Guo, P. S. Thomas, and E. Brunskill Using options and covariance testing for long horizon off-policy policy evaluation. In Advances in Neural Information Processing Systems, Vol. 30. Cited by: §2. Jiang and Li (2016) N. Jiang and L. Li Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), Vol. 48, p. 652–661. Cited by: Appendix H. Kakade and Langford (2002) S. M. Kakade and J. Langford Approximately optimal approximate reinforcement learning. In Proceedings of the 19th International Conference on Machine Learning (ICML), San Francisco, CA, USA, p. 267–274. Cited by: Appendix H, §1, §2, §2, §3.5. Kakade (2002) S. M. Kakade A natural policy gradient. Advances in Neural Information Processing Systems 14, p. 1531–1538. Cited by: §E.2, Appendix H, §1, §2, §3.5. Komorowski et al. (2018) M. Komorowski, L. A. Celi, O. Badawi, A. C. Gordon, and A. A. Faisal The artificial intelligence clinician learns optimal treatment strategies for sepsis in intensive care. Nature Medicine 24 (11), p. 1716–1720. Cited by: §7.4. Lan (2023) G. Lan Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming 198 (1), p. 1059–1106. Cited by: Appendix H. Li et al. (2023) G. Li, Y. Wei, Y. Chi, and Y. Chen Softmax policy gradient methods can take exponential time to converge. Mathematical Programming 201 (1–2), p. 707–802. Cited by: Appendix H. Lipp and Boyd (2016) T. Lipp and S. Boyd Variations and extension of the convex–concave procedure. Optimization and Engineering 17 (2), p. 263–287. External Links: Document Cited by: Appendix D, §F.4, Appendix H, §4.1, §5.1. Mei et al. (2020) J. Mei, C. Xiao, C. Szepesvári, and D. Schuurmans On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, p. 6820–6829. Cited by: Appendix H, §5. Metelli et al. (2018) A. M. Metelli, M. Papini, F. Faccio, and M. Restelli Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, Vol. 31. Cited by: Appendix H, §8. Munos et al. (2016) R. Munos, T. Stepleton, A. Harutyunyan, and M. G. Bellemare Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 29. Cited by: Appendix H. Nair et al. (2020) A. Nair, A. Gupta, M. Dalal, and S. Levine AWAC: accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.09359. Cited by: Appendix H. Oberst and Sontag (2019) M. Oberst and D. Sontag Counterfactual off-policy evaluation with Gumbel-max structural causal models. In Proceedings of the 36th International Conference on Machine Learning (ICML), Cited by: §7.4. Peng et al. (2019) X. B. Peng, A. Kumar, G. Zhang, and S. Levine Advantage-weighted regression: simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00177. Cited by: §E.3, Appendix H, §1, §3.5, Proposition 12. Peters et al. (2010) J. Peters, K. Mülling, and Y. Altün Relative entropy policy search. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 24, p. 1607–1612. Cited by: §E.3. Precup et al. (2000) D. Precup, R. S. Sutton, and S. Singh Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning (ICML), p. 759–766. Cited by: Appendix H, §1, §2. Puterman (2014) M. L. Puterman Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §2. Razaviyayn et al. (2013) M. Razaviyayn, M. Hong, and Z. Luo A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization 23 (2), p. 1126–1153. Cited by: Appendix D, §F.4, §5.1. Schulman et al. (2015) J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML), Vol. 37, p. 1889–1897. Cited by: §E.2, Appendix H, §1, §1, §2, §2, §3.5. Schulman et al. (2016) J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel High-dimensional continuous control using generalized advantage estimation. In International Conference on Learning Representations (ICLR), Cited by: Appendix H, §1. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: Appendix H, §1, §1, §2, §2. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y.K. Li, Y. Wu, et al. DeepSeekMath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: §1. Sutton (1988) R. S. Sutton Learning to predict by the methods of temporal differences. Machine Learning 3 (1), p. 9–44. Cited by: Appendix H, §1. Tao and An (1997) P. D. Tao and L. T. H. An Convex analysis approach to DC programming: theory, algorithms and applications. Acta Mathematica Vietnamica 22 (1), p. 289–355. Cited by: §F.4, Appendix H, §2.1, §4.1, §5.1. Thi and Dinh (2018) H. A. L. Thi and T. P. Dinh DC programming and DCA: thirty years of developments. Mathematical Programming 169 (1), p. 5–68. External Links: Document Cited by: Appendix H. Xiao (2022) L. Xiao On the convergence rates of policy gradient methods. Journal of Machine Learning Research 23 (282), p. 1–36. External Links: Link Cited by: Appendix H, item 2, §5. Supplementary Materials The following content was not necessarily subject to peer review. This appendix provides: the full CCRL algorithm (Appendix A); the Lagrangian form and KKT conditions for the tangent-plane SCP subproblem (Appendix B); convexity facts for the α-divergence trust regions, including the KL endpoints (Appendix C); background facts on directional stationarity (Appendix D); full proofs of all results stated in the main text (Appendices E and F, including the two lemmas that make the inner-loop feasibility induction well-posed, Lemmas 14–15); additional experimental results and setups (Appendix G); and an extended related-work discussion (Appendix H). Appendix A The full CCRL algorithm Algorithm 1 states the full outer loop of CCRL (Section 4). Each policy iteration collects fresh data under πn _n, fits a critic for advantage estimation, runs R rounds of tangent-plane SCP with retraction starting from y0=0y^0=0, and recovers πn+1 _n+1 from the final iterate yRy^R. As stated, the algorithm targets discrete action spaces, and Section 6 discusses its practical instantiation. Algorithm 1 CCRL: Convex-Concave Reinforcement Learning 0: initial policy π0 _0, critic VϕV_φ, trust region δ, divergence order α, SCP rounds R, truncation depth k, proximal weight ρ 1: for n=0,1,2,…n=0,1,2,… do 2: Collect N episodes under πn _n 3: Fit critic VϕV_φ; compute advantage estimates A^πn(St,At) A _n(S_t,A_t) (e.g. via GAE) 4: Initialize y0←0y^0← 0, floor b0←ymin=log(pmin/πn)b_0← y_ = (p_ / _n) 5: for r=0,1,…,R−1r=0,1,…,R-1 do 6: Solve tangent-plane subproblem (10) with anchor yry^r and floor brb_r to obtain y^r+1 y^r+1 7: Retract: yr+1(s,a)←y^r+1(s,a)−logfs(y^r+1)y^r+1(s,a)← y^r+1(s,a)- f_s( y^r+1) (per-state renormalization) 8: γr←maxslogfs(y^r+1) _r← _s f_s( y^r+1); br+1←br−γrb_r+1← b_r- _r1 (floor schedule (22)) 9: end for 10: Recover πn+1(a|s)∝πn(a|s)eyR(s,a) _n+1(a|s) _n(a|s)\,e^y^R(s,a) 11: end for Algorithm 2 gives the deployed form used in our experiments (Section 6). Its differences from the theoretical Algorithm 1 are shown in blue: (i) the tangent-plane subproblem is replaced by the plain trust-region convex program (15); (i) the per-round softmax retraction and the support-floor schedule are dropped (validity is restored only once, by the final row-normalization); (i) a y-clip ‖y‖∞≤ymax\|y\|_∞≤ y_ is added to the subproblem to keep the k-step importance weights e∑jye _jy bounded; and (iv) the exact policy recovery becomes a parametric maximum-likelihood M-step that fits πθ _θ to the row-normalized target. Algorithm 2 CCRL, deployed form (parametric E-step / M-step) 0: policy network πθ _θ, critic VϕV_φ; trust radius δ, divergence order α, truncation depth k, SCP rounds R, proximal weight ρ, M-step epochs E 1: for n=0,1,2,…n=0,1,2,… do 2: Collect episodes under πθn _ _n; fit VϕV_φ and estimate advantages A^πn A _n (e.g. GAE) (E-step: build the improved target) 3: y0←0y^0← 0 4: for r=0,…,R−1r=0,…,R-1 do 5: yr+1←argminy(Jk−(y)−∇Jk+(yr)⊤y+ρ2∥y−yr∥2)y^r+1← _y (J_k^-(y)-∇ J_k^+(y^r) y+ ρ2\|y-y^r\|^2 ) s.t. Dα(y)≤δ,‖y‖∞≤ymaxD_α(y)≤δ,\ \,\|y\|_∞≤ y_ (plain trust region + y-clip; no validity/floor) 6: end for 7: Target π~n+1(a∣s)∝πθn(a∣s)eyR(s,a) π_n+1(a s) _ _n(a s)\,e^y^R(s,a) (row-normalized recovery) 8: M-step: fit πθ _θ to the target for E epochs by minimizing −S∑aπ~n+1(a∣S)logπθ(a∣S)-\,E_S _a π_n+1(a S) _θ(a S); set θn+1←θ _n+1←θ (critic and entropy losses as in PPO) 9: end for Appendix B Lagrangian Form and KKT Conditions for the SCP Subproblem With anchor yr∈ℳy^r , the tangent-plane subproblem (10) is y^r+1=argminy∈r(Φ~r(y)+ρ2∥y−yr∥2),Φ~r(y)=Jk−(y)−∇Jk+(yr)⊤y, y^r+1\;=\; _y _r\; ( _r(y)+ ρ2\|y-y^r\|^2 ), _r(y)=J_k^-(y)-∇ J_k^+(y^r) y, over r=y:Dα(y)≤δ,∇fs(yr)⊤(y−yr)=0∀s,y≥br,C_r= \y:D_α(y)≤δ,\;∇ f_s(y^r) (y-y^r)=0\;∀ s,\;y≥ b_r \, with brb_r the floor schedule (22). B.1 Lagrangian form Introduce multipliers: ξ≥0ξ≥ 0 for the trust region; μs∈ℝμ^s (sign-free) for each tangent-plane equality ∇fs(yr)⊤(y−yr)=0∇ f_s(y^r) (y-y^r)=0; and ζs,a≥0 _s,a≥ 0 for each floor constraint. The Lagrangian is ℒr(y,ξ,μ,ζ) _r(y,ξ,μ,ζ) =Φ~r(y)+ρ2‖y−yr‖2+ξ(Dα(y)−δ) = _r(y)+ ρ2\|y-y^r\|^2+ξ (D_α(y)-δ ) +∑sμs∇fs(yr)⊤(y−yr)+∑s,aζs,a(br(s,a)−y(s,a)). + _sμ^s\,∇ f_s(y^r) (y-y^r)+ _s,a _s,a\, (b_r(s,a)-y(s,a) ). (16) B.2 KKT conditions The subproblem is convex with affine equalities; Slater’s condition holds in the relative-interior sense (the tangent plane intersected with the open trust region and strict floor is non-empty whenever δ>0δ>0, since the anchor yry^r is feasible by Proposition 16 and lies strictly above the relaxed floor brb_r at interior anchors). Stationarity reads 0=∇Φ~r(y^)+ρ(y^−yr)+ξ∇Dα(y^)+∑sμs∇fs(yr)−∑s,aζs,ae(s,a),0=∇ _r( y)+ρ( y-y^r)+ξ\,∇ D_α( y)+ _sμ^s\,∇ f_s(y^r)- _s,a _s,a\,e_(s,a), (17) where e(s,a)e_(s,a) is the coordinate basis vector for (s,a)(s,a), together with primal feasibility, dual feasibility (ξ,ζs,a≥0ξ, _s,a≥ 0; μsμ^s free), and complementary slackness for the inequalities. B.3 Gradient expressions For implementation: ∂fs(y)∂y(s¯,a¯) ∂ f_s(y)∂ y( s, a) =s¯=sπn(a¯|s¯)ey(s¯,a¯), =1\ s=s\\, _n( a| s)\,e^y( s, a), (18) ∂Dαs(y)∂y(s¯,a¯) ∂ D_α^s(y)∂ y( s, a) =s¯=s1α−1πn(a¯|s¯)eαy(s¯,a¯), =1\ s=s\\, 1α-1\, _n( a| s)\,e^α\,y( s, a), (19) ∂Jk±(y)∂y(s¯,a¯) ∂ J_k^±(y)∂ y( s, a) =τ∼pπn[∑t=0H−1γte∑t′=max(0,t−k+1)ty(St′,At′)[Aπn(St,At)]± =E_τ p_ _n\! [ _t=0^H-1γ^t\,e _t = (0,t-k+1)^ty(S_t ,A_t )\,[A _n(S_t,A_t)]^± . ⋅∑t′=max(0,t−k+1)t(St′,At′)=(s¯,a¯)]. .·\! _t = (0,t-k+1)^t\!1\(S_t ,A_t )=( s, a)\ ]. (20) B.4 Primal-dual gradient solver The subproblems are solved by standard primal-dual gradient steps on (16): ym+1 y^m+1 =Π[br,∞)(ym−ηy∇yℒr(ym,ξm,μm,ζm)), = _[b_r,∞)\! (y^m- _y\, _yL_r(y^m,ξ^m,μ^m,ζ^m) ), ξm+1 ξ^m+1 =[ξm+ηξ(Dα(ym)−δ)]+, =[ξ^m+ _ξ\,(D_α(y^m)-δ)]_+, μs,m+1 μ^s,m+1 =μs,m+ημ∇fs(yr)⊤(ym−yr)(sign-free ascent), =μ^s,m+ _μ\,∇ f_s(y^r) (y^m-y^r) (sign-free ascent), with projection Π applied only when the floor is imposed. After the final SCP round, the retraction (12) (per-state renormalization) is applied; this is the same normalization step every implementation performs when converting log-ratios to a policy. B.5 Why the equality is linearized as an equality Proposition 4 in Section 4.1 states that the naive DC split of the validity equality freezes the iteration at the anchor. We give the proof here. Proof of Proposition 4. Fix s and write za:=y(s,a)−yr(s,a)z_a:=y(s,a)-y^r(s,a) and wa:=πn(a|s)eyr(s,a)w_a:= _n(a|s)\,e^y^r(s,a). Feasibility of the anchor gives ∑awa=1 _aw_a=1 with wa>0w_a>0, so w is a probability vector. The two constraints read ∑awaeza≤1 _aw_ae^z_a≤ 1 and ∑awaza≥0 _aw_az_a≥ 0. By Jensen’s inequality for the strictly convex exponential, ∑awaeza≥exp(∑awaza)≥e0=1 _aw_ae^z_a≥ ( _aw_az_a )≥ e^0=1. Hence both inequalities hold with equality; equality in Jensen forces all zaz_a equal (strict convexity, wa>0w_a>0), and ∑awaza=0 _aw_az_a=0 then forces za=0z_a=0 for every a. This holds at every state, so y=yry=y^r. ∎ The tangent-plane construction of Section 4.1 avoids the trap by dropping the one-sided convex inequality and linearizing the equality as an equality; exact validity is restored by the retraction, whose effect on the objective is second order (Lemma 13) and absorbed by the proximal term (Theorem 17). Appendix C Convexity of α-Divergence Constraints This appendix collects the convexity facts that keep the trust region tractable in log-density-ratio coordinates: the three trust-region forms (Table 3), convexity of the α-divergence in y for finite α∉[0,1]α∉[0,1], the two KL endpoints, and the common divergences recovered as special cases. Table 3: Three variants of the trust-region constraint (Section 3.3), each in its general f-divergence form (policy space) and its corresponding α-divergence form in log-density-ratio coordinates. Variant f-divergence (policy space) α-divergence (y-space) Trajectory-level τ∼pπn[f(pπ(τ)/pπn(τ))]≤δE_τ p_ _n\! [f(p_π(τ)/p_ _n(τ)) ]≤δ 1α(α−1)τ∼pπn[eα∑ty(St,At)−1]≤δ 1α(α-1)E_τ p_ _n\! [e^α _ty(S_t,A_t)-1 ]≤δ Strict per-state A∼πn(⋅|s)[f(π(A|s)/πn(A|s))]≤δs,∀sE_A _n(·|s)\! [f(π(A|s)/ _n(A|s)) ]≤ _s,\;∀ s 1α(α−1)(A∼πn(⋅|s)[eαy(s,A)]−1)≤δs,∀s 1α(α-1) (E_A _n(·|s)\! [e^α\,y(s,A) ]-1 )≤ _s,\;∀ s Expected per-state S∼dπn[A∼πn(⋅|S)[f(π(A|S)/πn(A|S))]]≤δE_S d _n\! [E_A _n(·|S)\! [f(π(A|S)/ _n(A|S)) ] ]≤δ S∼dπn[1α(α−1)(A∼πn(⋅|S)[eαy(S,A)]−1)]≤δE_S d _n\! [ 1α(α-1) (E_A _n(·|S)\! [e^α\,y(S,A) ]-1 ) ]≤δ C.1 f-divergence convexity in π Proposition 7 (Convexity of f-divergence in π). Let f:ℝ+→ℝf:R_+ be convex with f(1)=0f(1)=0, and let πn _n have full support. Then Df(π(⋅|s)∥πn(⋅|s))=∑aπn(a|s)f(π(a|s)/πn(a|s))D_f(π(·|s)\| _n(·|s))= _a _n(a|s)\,f(π(a|s)/ _n(a|s)) is convex in π(⋅|s)π(·|s) for every s. Proof. Fix s and let qa=πn(a|s)>0q_a= _n(a|s)>0. The map π(a|s)↦f(π(a|s)/qa)π(a|s) f(π(a|s)/q_a) is convex (composition of the convex f with an affine map). Multiplying by qa≥0q_a≥ 0 preserves convexity, and the sum over a preserves convexity. ∎ C.2 α-divergence in y-space: finite α Proposition 8 (Convexity for finite α∉[0,1]α∉[0,1]). For every finite α∈ℝ∖[0,1]α [0,1], the trajectory-level, strict per-state, and expected per-state α-divergence forms of Table 3 are convex in y on all of ℝ||||R^|S||A|. Proof. Each integrand y↦eαℓ(y)y e^α\, (y) with ℓ affine is convex. The prefactor 1/[α(α−1)]1/[α(α-1)] is positive exactly on ℝ∖[0,1]R [0,1], and the constant −1-1 inside the bracket does not affect convexity. Non-negative weighted sums and expectations under fixed measures (pπnp_ _n, πn(⋅|s) _n(·|s), dπnd _n) preserve convexity. ∎ C.3 The KL endpoints: one convex, one not Proposition 9 (Reverse-KL endpoint on the validity manifold). The off-manifold limit of the strict per-state formula in Table 3 as α→0−α→ 0^- is −∑aπn(a|s)y(s,a)- _a _n(a|s)y(s,a), a linear function of y. On fs(y)=1f_s(y)=1 it equals KL(πn(⋅|s)∥π(⋅|s))KL( _n(·|s)\|π(·|s)). For the normalized policy defined at an arbitrary y, the reverse KL instead equals −∑aπn(a|s)y(s,a)+logfs(y)- _a _n(a|s)y(s,a)+ f_s(y); this is a different, convex off-manifold extension with the same values on fs=1f_s=1. Proof. Put F(α)=∑aπn(a|s)eαy(s,a)F(α)= _a _n(a|s)e^α y(s,a). Since F(0)=1F(0)=1 and F′(0)=∑aπn(a|s)y(s,a)F (0)= _a _n(a|s)y(s,a), limα→0−(F(α)−1)/[α(α−1)]=−F′(0) _α→ 0^-(F(α)-1)/[α(α-1)]=-F (0). For the normalized policy πy(a|s)=πn(a|s)ey(s,a)/fs(y) _y(a|s)= _n(a|s)e^y(s,a)/f_s(y), direct substitution in the definition of KL adds logfs(y) f_s(y). ∎ Proposition 10 (Forward-KL endpoint is not convex in y). On the validity manifold, the strict per-state α-divergence converges as α→1+α→ 1^+ to KL(π(⋅|s)∥πn(⋅|s))=∑aπn(a|s)ey(s,a)y(s,a)(on ℳ).KL (π(·|s)\,\|\, _n(·|s) )\;=\; _a _n(a|s)\,e^y(s,a)\,y(s,a) (on M). The right-hand expression, viewed as a function on ℝ||R^|A| (i.e., extended off the manifold), is not convex. Proof. Limit. Let F(α)=∑aπn(a|s)eαy(s,a)F(α)= _a _n(a|s)e^α y(s,a). On the manifold F(1)=1F(1)=1, so Dαs=(F(α)−1)/[α(α−1)]D_α^s=(F(α)-1)/[α(α-1)] is 0/00/0 at α=1α=1 and L’Hôpital gives limα→1+Dαs=F′(1)=∑aπneyy=∑aπ(a|s)y(s,a)=KL(π∥πn) _α→ 1^+D_α^s=F (1)= _a _ne^yy= _aπ(a|s)\,y(s,a)=KL(π\| _n). Non-convexity. The scalar map g(u)=ueug(u)=u\,e^u has g′(u)=eu(u+2)<0g (u)=e^u(u+2)<0 for u<−2u<-2. Concretely, take ||=2|A|=2, πn=(1/2,1/2) _n=(1/2,1/2), and evaluate the Hessian of h(y1,y2)=12(y1ey1+y2ey2)h(y_1,y_2)= 12(y_1e^y_1+y_2e^y_2) at y=(−3,−3)y=(-3,-3): it is diagonal with entries 12e−3(−3+2)=−12e−3<0 12e^-3(-3+2)=- 12e^-3<0. Hence h is not convex on any neighborhood containing such points. Points with y(s,a)<−2y(s,a)<-2 are not excluded by the problem data: the support floor gives only y≥log(pmin/πn(a|s))y≥ (p_ / _n(a|s)), which is below −2-2 whenever πn(a|s)>e2pmin _n(a|s)>e^2p_ . ∎ Remark 1 (Consequences). The non-convexity of the forward-KL expression in y (Proposition 10) has two consequences for the correspondences of Section 3.5. (i) TRPO’s constraint, dπn[KL(πn∥π)]E_d _n[KL( _n\|π)], is the reverse-KL endpoint α→0−α→ 0^- (Proposition 9) and is convex in y everywhere, so the TRPO correspondence needs no caveat. (i) AWR’s constraint, dπn[KL(π∥πn)]E_d _n[KL(π\| _n)], is the forward-KL endpoint; the AWR correspondence (Appendix E.3) derives the closed-form solution from the Lagrangian in policy space, where the forward KL is convex in π (Proposition 7), so no convexity in y is used or needed. For CCRL’s own trust regions we use finite α∉[0,1]α∉[0,1] (in the experiments, α=2α=2), where Proposition 8 applies. C.4 α-divergence family as special cases Table 4: Common f-divergences as special cases of the α-divergence Dα(p∥q)=1α(α−1)(q[(p/q)α]−1)D_α(p\|q)= 1α(α-1)(E_q[(p/q)^α]-1). “Convex in y” refers to global convexity of the constraint in log-density-ratio coordinates. α Divergence Convex in y Generator f(t)f(t) α=2α=2 χ2χ^2 Yes (t−1)2(t-1)^2 α=−1α=-1 Reverse χ2χ^2 Yes (1−t)2/t(1-t)^2/t α→1+α→ 1^+ Forward KL No (limit on ℳM only) tlogt t α→0−α→ 0^- Reverse KL Yes (linear on ℳM) −logt- t α=1/2α=1/2 Squared Hellinger No 2(t−1)22( t-1)^2 α>1α>1 Rényi (order α) Yes (tα−1)/[α(α−1)](t^α-1)/[α(α-1)] α<0α<0 Rényi (order α) Yes (tα−1)/[α(α−1)](t^α-1)/[α(α-1)] Appendix D Directional Stationarity We define the directional-stationarity notion used in the inner-loop convergence guarantee (Theorem 5). Definition (Tangent cone). Let ℱ⊆ℝdF ^d be closed and y⋆∈ℱy . The tangent cone of ℱF at y⋆y is Tℱ(y⋆):=d∈ℝd:∃tk↓0,dk→d with y⋆+tkdk∈ℱ∀k.T_F(y )\;:=\; \\,d ^d:∃\,t_k 0,\ d_k→ d with y +t_kd_k \,∀ k\, \. Intuitively, Tℱ(y⋆)T_F(y ) is the set of directions along which ℱF can be approached from y⋆y to first order. Definition (d-stationarity). Let Φ:ℝd→ℝ :R^d admit one-sided directional derivatives Φ′(y⋆,d):=limt↓0[Φ(y⋆+td)−Φ(y⋆)]/t (y ;d):= _t 0 [ (y +td)- (y ) ]/t. A point y⋆∈ℱy is a directional (d-)stationary point of Φ over ℱF if Φ′(y⋆,d)≥ 0for every d∈Tℱ(y⋆). (y ;d)\;≥\;0 every d∈ T_F(y ). Proposition 11 (Fixed points of the retraction iteration are d-stationary). Suppose y^r+1=yr y^r+1=y^r (the tangent-plane subproblem returns the anchor; the retraction then leaves it unchanged, so yr+1=yry^r+1=y^r), and LICQ holds at yry^r. Then yry^r is a d-stationary point of Φ over ℱF. Proof. Since the constraints of ℱF at yry^r consist of the smooth equality fs(y)=1f_s(y)=1 (whose tangent space at yry^r is precisely TrT_r), the trust-region inequality, and the floor, LICQ gives Tℱ(yr)=d∈Tr:∇Dα(yr)⊤d≤0 if active,d(s,a)≥0 for active floorsT_F(y^r)=\d∈ T_r:∇ D_α(y^r) d≤ 0 if active,\;d_(s,a)≥ 0 for active floors\. Optimality of yry^r for the convex subproblem over rC_r gives, for every such d, (∇Φ~r(yr))⊤d≥0 (∇ _r(y^r) ) d≥ 0: the constraint sets agree at a fixed point, since the trust region and validity are imposed exactly in (11) and the floor brb_r has settled (y^r+1=yr y^r+1=y^r gives γr=0 _r=0, so br′=brb_r =b_r for all r′≥r ≥ r). Note that the retraction is the identity here, so no normal vector is transported and active inequalities are handled correctly. Finally ∇Φ~r(yr)=∇Jk−(yr)−∇Jk+(yr)=∇Φ(yr)∇ _r(y^r)=∇ J_k^-(y^r)-∇ J_k^+(y^r)=∇ (y^r), so Φ′(yr;d)=∇Φ(yr)⊤d≥0 (y^r;d)=∇ (y^r) d≥ 0 on the tangent cone, which is d-stationarity. ∎ This is the expected outcome for successive-convex-approximation schemes: fixed points of the linearized iteration are d-stationary for the original program (Razaviyayn et al., 2013; Lipp and Boyd, 2016). Appendix E Proofs for the DC Reformulation This appendix proves the results of Section 3: the DC structure of the k-step objective (Theorem 1) and the recovery of CPI, NPG, TRPO, and AWR (Propositions 3 onward). E.1 Proof of Theorem 1 (DC structure) Proof. For any trajectory τ and any time t, the map y↦exp(∑t′y(St′,At′))y \! ( _t y(S_t ,A_t ) ) is convex (a composition of an affine map with the convex exponential). The non-negative weights max(±Aπn(St,At),0) (± A _n(S_t,A_t),0) and γtγ^t do not depend on y, so each integrand in (5) is a non-negative constant times a convex function of y. The expectation under τ∼pπnτ p_ _n does not depend on y, since the trajectory distribution is fixed by πn _n. Therefore Jk+J_k^+ and Jk−J_k^- are non-negative weighted sums of convex functions, hence convex. Finally, (Atπn)+−(Atπn)−=Atπn(A _n_t)_+-(A _n_t)_-=A _n_t pointwise, so subtracting the two lines of (5) termwise recovers JkJ_k. ∎ E.2 Proof of Proposition 3 (CPI/NPG/TRPO objective recovery) Proof. At k=1k=1, the cumulative product in (2) reduces to the single-step ratio ρ(St,At)=ey(St,At)ρ(S_t,A_t)=e^y(S_t,A_t). Substituting into (2): J1(π,πn)=τ∼pπn[∑t=0H−1γtρ(St,At)Aπn(St,At)].J_1(π; _n)=E_τ p_ _n\! [ _t=0^H-1γ^t\,ρ(S_t,A_t)\,A _n(S_t,A_t) ]. Taking the inner expectation over At∼πn(⋅∣St)A_t _n(· S_t): At∼πn[ρ(St,At)Aπn(St,At)]=∑aπ(a∣St)Aπn(St,a)E_A_t _n[ρ(S_t,A_t)A _n(S_t,A_t)]= _aπ(a S_t)\,A _n(S_t,a). Summing over t with weights γtγ^t under the marginals μtπn(s)=Pr(St=s∣πn) _t _n(s)= (S_t=s _n) and using ηπn(s)=∑tγtμtπn(s)=ZHdπn(s)η _n(s)= _tγ^t _t _n(s)=Z_H\,d _n(s): J1=∑sηπn(s)∑aπ(a|s)Aπn(s,a)=ZHS∼dπn[∑aπ(a|S)Aπn(S,a)]=ZHL(π,πn).J_1= _sη _n(s) _aπ(a|s)A _n(s,a)=Z_HE_S d _n\! [ _aπ(a|S)A _n(S,a) ]=Z_H\,L(π; _n). For the TRPO statement: TRPO’s constraint is the expected per-state reverse KL, S∼dπn[KL(πn(⋅|S)∥π(⋅|S))]≤δE_S d _n[KL( _n(·|S)\|π(·|S))]≤δ, which is the α→0−α→ 0^- endpoint of the expected per-state α-divergence (Proposition 9); together with J1=ZHLJ_1=Z_HL this is the TRPO optimization program up to the positive constant ZHZ_H, which does not change the maximizers. For the NPG statement: NPG ascends the same k=1k=1 objective L under a reverse-KL proximity, but taken as a second-order (Fisher-matrix) approximation of the KL in parameter space rather than an exact constraint (Kakade, 2002; Schulman et al., 2015). Our formulation captures the objective and the divergence direction, not the parameter-space Fisher preconditioning; at this level NPG therefore coincides with the reverse-KL (TRPO) program above, and we recover its objective rather than reproducing its update. ∎ E.3 Proof of Proposition on AWR recovery Proposition 12 (AWR recovery). At k=1k=1, with the expected per-state forward-KL constraint S∼dπn[KL(π(⋅|S)∥πn(⋅|S))]≤δE_S d _n[KL(π(·|S)\| _n(·|S))]≤δ (the α→1+α→ 1^+ endpoint) and the validity constraint dropped with normalization applied post-hoc, the CCRL program matches the optimization form of AWR (Peng et al., 2019): the same objective, the same constraint, and the same closed-form solution π∗(a|s)∝πn(a|s)exp(Aπn(s,a)/ηawr)π^*(a|s) _n(a|s)\, (A _n(s,a)/ _awr). Proof. At k=1k=1 the objective is ZHL(π,πn)Z_HL(π; _n) (Proposition 3); dropping the positive constant, we work with L. Following the AWR derivation (Peters et al., 2010; Peng et al., 2019), treat π(⋅|s)π(·|s) as a non-negative function (validity unenforced) and form the policy-space Lagrangian of the constrained problem with dual variable ηawr≥0 _awr≥ 0: ∑sdπn(s)[∑aπ(a|s)Aπn(s,a)−ηawr∑aπ(a|s)logπ(a|s)πn(a|s)]−ηawrδ. _sd _n(s) [ _aπ(a|s)\,A _n(s,a)- _awr _aπ(a|s) π(a|s) _n(a|s) ]- _awr\,δ. Every term is expressed in policy space, where the forward KL is convex in π (Proposition 7); no convexity in y-coordinates is invoked (cf. Proposition 10 and Remark 1). The problem decomposes across states (no cross-state coupling at k=1k=1). Pointwise stationarity in π(a|s)π(a|s) gives Aπn(s,a)−ηawr(logπ(a|s)πn(a|s)+1)=const(s)A _n(s,a)- _awr( π(a|s) _n(a|s)+1)=const(s), i.e. π∗(a|s)∝πn(a|s)eAπn(s,a)/ηawrπ^*(a|s) _n(a|s)\,e^A _n(s,a)/ _awr, with the per-state normalization applied post-hoc (as AWR does). This coincides with the CCRL policy recovery (13) under the identification y∗(s,a)=Aπn(s,a)/ηawr−logZsy^*(s,a)=A _n(s,a)/ _awr- Z_s with ZsZ_s the per-state normalizer. ∎ Appendix F Proofs for the Convergence Analysis This appendix proves the inner-loop results under the strict per-state trust region (the retraction lemma, the two feasibility lemmas (Lemmas 14–15), Proposition 16, and Theorem 17) and the outer-loop results (three supporting lemmas, Theorem 21, Theorem 6). Throughout the inner-loop analysis we fix α>1α>1 (Remark 2). Every proof below uses only convexity of finite sums of exponentials of affine maps, Lipschitz and smoothness bounds on a fixed box, Jensen’s inequality, strong convexity of the proximal subproblem, a telescoping sum, the performance-difference lemma, and one concentrability step. F.1 The retraction lemma Lemma 13 (Second-order retraction shift). Let yr∈ℳy^r and let y^∈Tr y∈ T_r (i.e., ∇fs(yr)⊤(y^−yr)=0∇ f_s(y^r) ( y-y^r)=0 for all s) with y^,yr y,y^r in a convex compact set K (constructed in Proposition 16) on which each fsf_s is LfL_f-smooth. Then for every s, 0≤cs:=logfs(y^)≤fs(y^)−1≤Lf2‖y^−yr‖2,0\;≤\;c_s:= f_s( y)\;≤\;f_s( y)-1\;≤\; L_f2\,\| y-y^r\|^2, (21) and the retracted point y+:=y^−∑scs 1sy^+:= y- _sc_s\,1_s (where s1_s is the indicator vector of state block s) satisfies fs(y+)=1f_s(y^+)=1 for all s and ‖y+−y^‖≤||||Lf2‖y^−yr‖2.\|y^+- y\|\;≤\; |S||A|\; L_f2\,\| y-y^r\|^2. Proof. Lower bound. By convexity of fsf_s and tangency, fs(y^)≥fs(yr)+∇fs(yr)⊤(y^−yr)=1f_s( y)≥ f_s(y^r)+∇ f_s(y^r) ( y-y^r)=1, so cs=logfs(y^)≥0c_s= f_s( y)≥ 0. Upper bound. By LfL_f-smoothness and tangency, fs(y^)≤fs(yr)+∇fs(yr)⊤(y^−yr)+Lf2∥y^−yr∥2=1+Lf2∥y^−yr∥2f_s( y)≤ f_s(y^r)+∇ f_s(y^r) ( y-y^r)+ L_f2\| y-y^r\|^2=1+ L_f2\| y-y^r\|^2; and log(1+u)≤u (1+u)≤ u for u≥0u≥ 0. Exactness of the retraction. Subtracting the constant csc_s from every coordinate of state block s multiplies each term πn(a|s)ey^(s,a) _n(a|s)e y(s,a) by e−cs=1/fs(y^)e^-c_s=1/f_s( y), so fs(y+)=fs(y^)/fs(y^)=1f_s(y^+)=f_s( y)/f_s( y)=1. Displacement. Each of the |||A| coordinates in state block s shifts by exactly csc_s, so ‖y+−y^‖2=||∑scs2≤||||(maxscs)2\|y^+- y\|^2=|A| _sc_s^2≤|A|\,|S|\,( _sc_s)^2, giving ‖y+−y^‖≤||||maxscs≤||||Lf2‖y^−yr‖2\|y^+- y\|≤ |S||A|\, _sc_s≤ |S||A|\, L_f2\,\| y-y^r\|^2. ∎ F.2 Two lemmas that close the feasibility induction The subproblem (11) uses the scheduled floor y≥bry≥ b_r: it starts at b0:=yminb_0:=y_ and, after each round, is relaxed by exactly the retraction shift the round absorbs, γr:=maxslogfs(y^r+1)≥ 0,br+1:=br−γr, _r\;:=\; _s f_s( y^r+1)\;≥\;0, b_r+1\;:=\;b_r- _r1, (22) where γr _r is a free byproduct of the retraction (12). This schedule is what makes the anchor of the next round feasible, as Step 2 of Theorem 17 requires: the trust region needs no bookkeeping because the retraction can only decrease DαD_α (Lemma 14), and the floor relaxation makes yr+1≥br+1y^r+1≥ b_r+1 automatic while its total drift is paid for by the descent telescope (Lemma 15). Lemma 14 (Retraction is DαD_α-nonexpansive for α>1α>1). Let y+=y−∑scssy^+=y- _sc_s1_s with cs≥0c_s≥ 0 for every s, where s1_s is the indicator vector of state block s (in particular, the retraction (12), for which cs=logfs(y)≥0c_s= f_s(y)≥ 0 by Lemma 13). Then for every α>1α>1, all three trust-region forms of Table 3—trajectory-level, strict per-state, and expected per-state—satisfy Dα(y+)≤Dα(y).D_α(y^+)\;≤\;D_α(y). Proof. Strict per-state. Fix s. Every coordinate of block s drops by the same constant csc_s, so ∑aπn(a|s)eα(y(s,a)−cs)=e−αcs∑aπn(a|s)eαy(s,a)≤∑aπn(a|s)eαy(s,a), _a _n(a|s)\,e^α(y(s,a)-c_s)\;=\;e^-α c_s _a _n(a|s)\,e^α y(s,a)\;≤\; _a _n(a|s)\,e^α y(s,a), since e−αcs≤1e^-α c_s≤ 1 for α>0α>0 and cs≥0c_s≥ 0, and the sum is non-negative. The prefactor 1/[α(α−1)]1/[α(α-1)] is positive for α>1α>1, and the additive −1-1 is unaffected, so Dαs(y+)≤Dαs(y)D_α^s(y^+)≤ D_α^s(y) for every s. Trajectory-level. Along any trajectory τ the exponent α∑ty(St,At)α _ty(S_t,A_t) decreases by α∑tcSt≥0α _tc_S_t≥ 0, so eα∑ty+(St,At)≤eα∑ty(St,At)e^α _ty^+(S_t,A_t)≤ e^α _ty(S_t,A_t) pointwise on trajectories. Taking the expectation under the fixed measure pπnp_ _n preserves the inequality, and the prefactor is positive for α>1α>1. Expected per-state. Take the dπnd _n-expectation of the strict per-state inequality, again a fixed non-negative measure. ∎ Remark 2 (Scope of Lemma 14). The lemma is specific to α>1α>1. For α<0α<0 the prefactor 1/[α(α−1)]1/[α(α-1)] is still positive but e−αcs≥1e^-α c_s≥ 1, so the retraction increases the divergence; and for the reverse-KL endpoint, whose per-state form is the linear −∑aπn(a|s)y(s,a)- _a _n(a|s)\,y(s,a) (Proposition 9), subtracting csc_s adds csc_s to the value. The inner-loop guarantee (Theorem 17) is stated for α>1α>1 under the strict per-state trust region. Other trust forms need additional state or trajectory coverage assumptions for the compactness argument. This covers α=2α=2 (χ2χ^2), the only setting used in the experiments and the one the outer-loop analysis of Section 5.2 requires. We make no inner-loop claim for α<0α<0 or for the reverse-KL endpoint; for those, a trust-region margin dominating the retraction shift would have to be reinstated, together with the bookkeeping the schedule below replaces. Lemma 15 (Drift budget for the floor schedule). Let K and KextK_ ext be the boxes of Proposition 16. Let each fsf_s be LfL_f-smooth on K and Φ be LΦL_ -Lipschitz on KextK_ ext, and let ρ>ρ0:=LΦLf||||ρ> _0:=L_ L_f |S||A|. If the descent inequality (25) holds through round R, then ∑r=0R−1γr≤Lf2∑r=0R−1‖z^r‖2≤Lf(Φ(y0)−infKextΦ)ρ−ρ0=:B(ρ),z^r:=y^r+1−yr. _r=0^R-1 _r\;≤\; L_f2 _r=0^R-1\| z_r\|^2\;≤\; L_f\, ( (y^0)- _K_ ext )ρ- _0\;=:\;B(ρ), z_r:= y^r+1-y^r. Consequently every floor satisfies br≥ymin−B(ρ)b_r≥ y_ -B(ρ)1 and every iterate yr≥ymin−B(ρ)y^r≥ y_ -B(ρ)1, i.e. the enforced support floor is πr(a|s)≥pmine−B(ρ)π^r(a|s)≥ p_ e^-B(ρ). The budget B(ρ)=O(1/ρ)B(ρ)=O(1/ρ) is a user-controlled quantity: it is determined a priori by (πn,α,δ,pmin,ρ)( _n,α,δ,p_ ,ρ) and shrinks as ρ grows. Proof. The first inequality is Lemma 13 applied at each round: γr=maxslogfs(y^r+1)≤Lf2‖z^r‖2 _r= _s f_s( y^r+1)≤ L_f2\| z_r\|^2. The second telescopes the descent inequality (25): ∑r<Rρ−ρ02‖z^r‖2≤∑r<R[Φ(yr)−Φ(yr+1)]=Φ(y0)−Φ(yR)≤Φ(y0)−infKextΦ. _r<R ρ- _02\| z_r\|^2\;≤\; _r<R [ (y^r)- (y^r+1) ]\;=\; (y^0)- (y^R)\;≤\; (y^0)- _K_ ext . Multiplying by Lf/(ρ−ρ0)L_f/(ρ- _0) gives the claim. The floor statement follows from br=ymin−(∑j<rγj)≥ymin−B(ρ)b_r=y_ - ( _j<r _j )1≥ y_ -B(ρ)1 and yr≥bry^r≥ b_r. ∎ F.3 Feasibility, compactness, and the well-posed induction Proposition 16 (Feasibility, compactness, and the well-posed induction). Fix α>1α>1 and the strict per-state trust region, and suppose πn(a|s)≥pmin _n(a|s)≥ p_ for all (s,a)(s,a) with ||pmin<1|A|\,p_ <1. Define the box K:=y:ymin(s,a)−1≤y(s,a)≤1αlog(1+α(α−1)δpmin)∀(s,a),K\;:=\; \\,y\;:\;y_ (s,a)-1\;≤\;y(s,a)\;≤\; 1α \! ( 1+α(α-1)δp_ ) ∀(s,a)\, \, (23) define U:=α−1log((1+α(α−1)δ)/pmin)U:=α^-1 ((1+α(α-1)δ)/p_ ) (the upper face of K), and define the larger fixed box Kext:=y:ymin(s,a)−1−U≤y(s,a)≤U∀(s,a).K_ ext:=\y:y_ (s,a)-1-U≤ y(s,a)≤ U ∀(s,a)\. Let LfL_f be a smoothness constant for every fsf_s on K and LΦL_ a Lipschitz constant for Φ on KextK_ ext, put ρ0:=LΦLf|||| _0:=L_ L_f |S||A|, and choose the proximal weight ρ>ρ0+Lf(supKextΦ−infKextΦ),ρ\;>\; _0\;+\;L_f\, ( _K_ ext - _K_ ext ), (24) so that the drift budget of Lemma 15 satisfies B(ρ)≤1B(ρ)≤ 1. Then, with the constraint sets (11) and the floor schedule (22): (i) (Base case.) y0=0∈0y^0=0 _0: indeed fs(0)=1f_s(0)=1, Dα(0)=0≤δD_α(0)=0≤δ, and 0≥ymin=b00≥ y_ =b_0 because πn(a|s)≥pmin _n(a|s)≥ p_ . (i) (Induction step.) For every r: r⊆KC_r K; the round-r subproblem is feasible, since its anchor satisfies yr∈ry^r _r; and the retracted iterate satisfies exact validity fs(yr+1)=1f_s(y^r+1)=1 for all s, the trust region Dα(yr+1)≤δD_α(y^r+1)≤δ, and the next floor yr+1≥br+1y^r+1≥ b_r+1—hence yr+1∈r+1y^r+1 _r+1. (i) (Uniform confinement.) All iterates remain in K and satisfy the effective support floor πr(a|s)≥pmine−B(ρ)≥pmine−1π^r(a|s)≥ p_ e^-B(ρ)≥ p_ e^-1. The limiting feasible set ℱ=y:Dαs(y)≤δ∀s,fs(y)=1∀s,y≥b∞F=\y:D_α^s(y)≤δ\ ∀ s,\ f_s(y)=1\ ∀ s,\ y≥ b_∞\ (Remark 3) is compact. Proof. Step 0 (Fixed boxes). For the strict per-state constraint, Dαs(y)≤δD_α^s(y)≤δ bounds every coordinate above by U. If y^∈K y∈ K, then fs(y^)≤eUf_s( y)≤ e^U and thus 0≤cs=logfs(y^)≤U0≤ c_s= f_s( y)≤ U (the lower bound uses tangency). Consequently its retraction and the whole retraction segment lie in KextK_ ext even before descent and the floor budget have been proved. All constants used below are fixed by the problem data in advance. Step 1 (Base case). At y=0y=0 we have π=πnπ= _n, so fs(0)=1f_s(0)=1 for every s and Dα(0)=0≤δD_α(0)=0≤δ; and b0=ymin=log(pmin/πn)≤0b_0=y_ = (p_ / _n)≤ 0 since πn≥pmin _n≥ p_ . The tangent-plane equalities hold trivially at the anchor. Hence y0=0∈0y^0=0 _0, and 0∈K0∈ K (the lower face because ymin−1<ymin≤0y_ -1<y_ ≤ 0, the upper face because 1αlog((1+α(α−1)δ)/pmin)≥1αlog(1/pmin)>0 1α ((1+α(α-1)δ)/p_ )≥ 1α (1/p_ )>0). Step 2 (Upper coordinate bound from the trust region alone). For the strict per-state form, any y with Dα(y)≤δD_α(y)≤δ satisfies, for each (s,a)(s,a), πn(a|s)eαy(s,a)≤∑a′πn(a′|s)eαy(s,a′)≤ 1+α(α−1)δ, _n(a|s)\,e^α y(s,a)\;≤\; _a _n(a |s)\,e^α y(s,a )\;≤\;1+α(α-1)\,δ, the first step because every summand is non-negative and the second by rearranging Dαs(y)≤δD_α^s(y)≤δ with the positive prefactor (α>1α>1). Using πn(a|s)≥pmin _n(a|s)≥ p_ and taking logarithms, y(s,a)≤1αlog((1+α(α−1)δ)/pmin)y(s,a)≤ 1α ((1+α(α-1)δ)/p_ ): the trust region alone confines every feasible point below the upper face of K. Step 3 (Descent and the budget, without circular confinement). Suppose yr∈ry^r _r and r⊂KC_r⊂ K. The subproblem minimizer y^∈K y∈ K exists by compactness. The majorization and anchor comparison in Theorem 17 give Φ(y^)≤Φ(yr)−ρ‖z^r‖2/2 ( y)≤ (y^r)-ρ\| z_r\|^2/2. By Step 0 the retraction segment is in KextK_ ext, so its Lipschitz bound is valid now, and Lemma 13 gives Φ(yr+1)≤Φ(yr)−(ρ−ρ0)‖z^r‖2/2 (y^r+1)≤ (y^r)-(ρ- _0)\| z_r\|^2/2. Telescoping the inequalities through this round and using yr+1∈Kexty^r+1∈ K_ ext gives ∑j≤rγj≤Lf[Φ(y0)−infKextΦ]/(ρ−ρ0)=B(ρ)≤1 _j≤ r _j≤ L_f[ (y^0)- _K_ ext ]/(ρ- _0)=B(ρ)≤ 1. Thus br+1≥ymin−b_r+1≥ y_ -1. Step 2 supplies the upper face, so r+1⊂KC_r+1⊂ K. Step 4 (Anchor feasibility at round r+1r+1, constructively). Write y^:=y^r+1 y:= y^r+1. Validity: fs(yr+1)=1f_s(y^r+1)=1 exactly, by Lemma 13. Trust region: the subproblem enforced Dα(y^)≤δD_α( y)≤δ, and the retraction subtracts cs=logfs(y^)≥0c_s= f_s( y)≥ 0 from each state block, so Lemma 14 (α>1α>1) gives Dα(yr+1)≤Dα(y^)≤δD_α(y^r+1)≤ D_α( y)≤δ. Floor: the subproblem enforced y^≥br y≥ b_r, and each coordinate of block s drops by cs≤maxs′cs′=γrc_s≤ _s c_s = _r, so yr+1≥br−γr=br+1y^r+1≥ b_r- _r1=b_r+1. Finally the tangent-plane equalities at the new anchor hold trivially at y=yr+1y=y^r+1. Hence yr+1∈r+1y^r+1 _r+1 and the hypothesis advances to round r+1r+1, which proves (i)–(i). Note that no step here appeals to Theorem 17’s conclusions, only to its Steps 1–3 under the hypothesis. Step 5 (Uniform confinement). By Lemma 15 and B(ρ)≤1B(ρ)≤ 1, every iterate satisfies yr≥br≥ymin−B(ρ)y^r≥ b_r≥ y_ -B(ρ)1, i.e. πr(a|s)=πn(a|s)eyr(s,a)≥pmine−B(ρ)≥pmine−1π^r(a|s)= _n(a|s)e^y^r(s,a)≥ p_ e^-B(ρ)≥ p_ e^-1, giving (i). Step 6 (Compactness). Each rC_r is closed, convex and contained in the compact box K; it is nonempty because it contains its anchor. The limiting feasible set is closed and contained in K, hence compact. No relative-interior claim is needed for the descent or existence arguments. ∎ Remark 3 (The feasible set ℱF and its floor). Since γr≤Lf2‖z^r‖2→0 _r≤ L_f2\| z_r\|^2→ 0 and ∑rγr≤B(ρ)<∞ _r _r≤ B(ρ)<∞ (Lemma 15), the floors brb_r decrease monotonically to a limit b∞:=ymin−(∑r≥0γr)≥ymin−B(ρ),b_∞\;:=\;y_ - ( _r≥ 0 _r )1\;≥\;y_ -B(ρ)1, and we define the fixed limiting feasible set ℱ:=y:Dαs(y)≤δ∀s,fs(y)=1∀s,y≥b∞.F\;:=\;\\,y\;:\;D_α^s(y)≤δ\ ∀ s,\;\;f_s(y)=1\;∀ s,\;\;y≥ b_∞\,\. The inner-loop theorem refers to this limiting set, rather than to the nominal floor yminy_ . Its gap from the nominal floor is at most B(ρ)=O(1/ρ)B(ρ)=O(1/ρ); if the floor is inactive at a limit point, the two sets have the same local tangent cone there. The floor is needed for compactness (Remark 4). Remark 4 (Why the floor is needed for α≥1α≥ 1). Without the floor, compactness fails. Consider ||=1|S|=1, ||=2|A|=2, πn=(1/2,1/2) _n=(1/2,1/2), and yM=(−M,log(2−e−M))y_M=(-M, (2-e^-M)). The validity equality holds exactly, while for α=2α=2, D2s(yM)→1/2D_2^s(y_M)→ 1/2 as M→∞M→∞; so if δ≥1/2δ≥ 1/2, the sequence yMy_M stays feasible while one coordinate escapes to −∞-∞. Similar behavior occurs for any α≥1α≥ 1, and in particular throughout the regime α>1α>1 of Remark 2: this is why the floor cannot simply be dropped, and why its relaxation has to be budgeted rather than unbounded (Lemma 15). F.4 Inner-loop convergence Theorem 5 of the main text is the following detailed statement. It is the standard guarantee profile for proximal DC algorithms on non-convex programs (Tao and An, 1997; Razaviyayn et al., 2013; Lipp and Boyd, 2016), and it needs no growth condition; part (i) assumes LICQ at the limit point. Theorem 17 (Inner-loop convergence, strict per-state trust region). Let α>1α>1 and the strict per-state trust region be used; let K be the box (23), let LfL_f be the smoothness constant of the fsf_s on K and LΦL_ a Lipschitz constant of Φ on KextK_ ext, and set ρ0:=LΦLf|||| _0:=L_ L_f |S||A|. Let the proximal weight satisfy ρ>ρ0ρ> _0 together with (24), so that the drift budget obeys B(ρ)≤1B(ρ)≤ 1 and Proposition 16 confines all iterates to K. Write z^r:=y^r+1−yr z_r:= y^r+1-y^r. Then the retraction-SCP iterates satisfy: (i) (Monotone descent.) For every r, Φ(yr+1)≤Φ(yr)−ρ−ρ02‖z^r‖2. (y^r+1)\;≤\; (y^r)\;-\; ρ- _02\,\| z_r\|^2. (25) (i) (Stationarity rate.) min0≤r<R‖z^r‖2≤2(Φ(y0)−infKextΦ)(ρ−ρ0)R. _0≤ r<R\| z_r\|^2\;≤\; 2 ( (y^0)- _K_ ext )(ρ- _0)\,R. (26) In particular, a round with proximal-step residual ‖z^r‖≤ε\| z_r\|≤ is reached within O(1/ε2)O(1/ ^2) SCP rounds, and ‖z^r‖→0\| z_r\|→ 0, ‖yr+1−yr‖→0\|y^r+1-y^r\|→ 0. (i) (Subsequential d-stationarity.) Every limit point y⋆y of yr\y^r\ lies in ℱF, and if LICQ holds for the active constraints of ℱF at y⋆y , then y⋆y is a d-stationary point of Φ over ℱF. The threshold ρ0 _0 pays for the second-order retraction shift (21). Proof. Write y^:=y^r+1 y:= y^r+1 and z:=z^r=y^−yrz:= z_r= y-y^r. Steps 1–3 prove part (i), Step 4 part (i), and Step 5 part (i). Step 1 (DC majorization on the tangent plane). Convexity of Jk+J_k^+ gives Φ~r(y)≥Φ(y)+cr _r(y)≥ (y)+c_r for all y, with equality at y=yry=y^r, where cr:=Jk+(yr)−∇Jk+(yr)⊤yrc_r:=J_k^+(y^r)-∇ J_k^+(y^r) y^r. Step 2 (Proximal decrease at y y). Since yr∈ry^r _r and y y minimizes the ρ-strongly-convex objective Φ~r+ρ2∥⋅−yr∥2 _r+ ρ2\|·-y^r\|^2 over the convex rC_r, Φ~r(y^)+ρ2‖z‖2≤Φ~r(yr)⟹Φ(y^)≤Φ(yr)−ρ2‖z‖2, _r( y)+ ρ2\|z\|^2\;≤\; _r(y^r) ( y)\;≤\; (y^r)- ρ2\|z\|^2, using the majorization from Step 1 on both sides. Step 3 (Retraction perturbation). By Lemma 13, ‖yr+1−y^‖≤||||Lf2‖z‖2\|y^r+1- y\|≤ |S||A|\, L_f2\|z\|^2, and the retraction segment lies in KextK_ ext, where Φ is LΦL_ -Lipschitz, so Φ(yr+1)≤Φ(y^)+LΦ||||Lf2‖z‖2=Φ(y^)+ρ02‖z‖2, (y^r+1)\;≤\; ( y)+L_ |S||A|\, L_f2\,\|z\|^2\;=\; ( y)+ _02\|z\|^2, with ρ0:=LΦLf|||| _0:=L_ L_f |S||A|. Combining with Step 2: Φ(yr+1)≤Φ(yr)−ρ−ρ02‖z‖2, (y^r+1)\;≤\; (y^r)- ρ- _02\|z\|^2, which is (25). For ρ>ρ0ρ> _0 this gives monotone decrease, strict unless z=0z=0. Step 4 (Stationarity rate). Sum (25) over r<Rr<R and use the lower bound of Φ on the fixed compact box KextK_ ext: ρ−ρ02∑r=0R−1‖z^r‖2≤∑r=0R−1[Φ(yr)−Φ(yr+1)]=Φ(y0)−Φ(yR)≤Φ(y0)−infKextΦ. ρ- _02 _r=0^R-1\| z_r\|^2\;≤\; _r=0^R-1 [ (y^r)- (y^r+1) ]\;=\; (y^0)- (y^R)\;≤\; (y^0)- _K_ ext . Since the minimum of R non-negative terms is at most their average, this gives (26); letting R→∞R→∞ gives ∑r‖z^r‖2<∞ _r\| z_r\|^2<∞, hence ‖z^r‖→0\| z_r\|→ 0. For the iterate gap, the retraction moves y^r+1 y^r+1 by only O(‖z^r‖2)O(\| z_r\|^2) by Lemma 13, so ‖yr+1−yr‖≤‖z^r‖+‖yr+1−y^r+1‖≤|z^r|(1+O(‖z^r‖))≤ 2‖z^r‖\|y^r+1-y^r\|\;≤\;\| z_r\|+\|y^r+1- y^r+1\|\;≤\;\| z_r\| (1+O(\| z_r\|) )\;≤\;2\| z_r\| for r large, whence ‖yr+1−yr‖→0\|y^r+1-y^r\|→ 0 as well. Step 5 (Subsequential d-stationarity). Take a subsequence yrj→y⋆y^r_j→ y . The trust region and validity pass to the limit, and yrj≥brj→b∞y^r_j≥ b_r_j→ b_∞, so y⋆∈ℱy . Also y^rj+1→y⋆ y^r_j+1→ y because z^rj→0 z_r_j→ 0. For each convex subproblem, its first-order condition holds with equality multipliers for ∇fs(yrj)∇ f_s(y^r_j), a nonnegative multiplier for each active strict per-state trust inequality, and nonnegative multipliers for active coordinate floors. Assume LICQ for the active constraints of ℱF at y⋆y . Any constraint active along a further subsequence must be active at y⋆y by continuity and brj→b∞b_r_j→ b_∞. The corresponding gradients converge to a linearly independent subset of those at y⋆y . Their smallest singular value is therefore bounded away from zero for all sufficiently large j. The subproblem gradients are bounded on K, so the first-order equation bounds all multipliers. Pass to a convergent multiplier subsequence. Since z^rj→0 z_r_j→ 0, ∇Φ~rj(y^rj+1)+ρz^rj→∇Φ(y⋆)∇ _r_j( y^r_j+1)+ρ z_r_j→∇ (y ). The limiting stationarity equation, feasibility, multiplier signs, and complementary slackness are precisely the KKT conditions for Φ over ℱF. LICQ identifies its tangent cone with the linearized feasible cone; dotting the stationarity equation with any direction in that cone shows ∇Φ(y⋆)⊤d≥0∇ (y ) d≥ 0. Thus y⋆y is d-stationary over ℱF. ∎ By Proposition 11, a zero residual gives d-stationarity under LICQ. The residual is therefore a proximal-step measure of approximate first-order progress, and part (i) reads: the smallest squared residual through round R is O(1/R)O(1/R), i.e. the smallest residual is O(1/R)O(1/ R). F.5 Outer-loop setup and assumptions The outer-loop analysis (Theorem 6) specializes to exact PDIS (k=Hk=H), which removes surrogate bias (JH=J(π)−J(πn)J_H=J(π)-J( _n)), and to strict per-state χ2χ^2 trust regions (α=2α=2). It uses two assumptions and the advantage scale Amax:=supn,s,a|Aπn(s,a)|≤2ZHRmaxA_ := _n,s,a|A _n(s,a)|≤ 2Z_HR_ (for rewards in [−Rmax,Rmax][-R_ ,R_ ]), which controls the bias term. Assumption 1 (Support floor on outer iterates). Every outer iterate satisfies πn(a|s)≥pmin _n(a|s)≥ p_ for all n,s,an,s,a, with ||pmin<1|A|\,p_ <1. The moving inner floor guarantees only πn+1(a|s)≥pmine−Bn(ρn) _n+1(a|s)≥ p_ e^-B_n( _n) when its nominal floor is pminp_ ; repeating this estimate alone does not give one positive uniform floor over infinitely many outer iterations. Assumption 1 is therefore a separate condition on all outer iterates, not a consequence of the initial policy or the inner convergence theorem. In particular, raising the nominal floor above an action probability of πn _n would make y0=0y^0=0 infeasible. The contraction theorem below is conditional on this explicit assumption. Assumption 2 (Concentrability). There is a finite constant C∞C_∞ such that maxn,s:dπn(s)>0dπ∗(s)/dπn(s)≤C∞ _n,s:d _n(s)>0\,d^π^*(s)/d _n(s)≤ C_∞, and dπ∗(s)=0d^π^*(s)=0 whenever dπn(s)=0d _n(s)=0. F.6 Mixture state-visitation dominance Throughout the outer-loop proofs we use the un-normalized visitation measure ηπ(s)=ZHdπ(s)η^π(s)=Z_H\,d^π(s); recall ∑sηπ(s)=ZH _sη^π(s)=Z_H. Lemma 18 (Mixture state-visitation dominance). For any λ∈[0,1]λ∈[0,1] and any policies πn,π _n, π, define π~λ=(1−λ)πn+λπ π_λ=(1-λ) _n+λ π. Then for finite horizon H: ηπ~λ(s)≥∑t=0H−1γt(1−λ)tPr(St=s∣πn)≥(1−λ)H−1ηπn(s)∀s∈.η π_λ(s)\;≥\; _t=0^H-1γ^t(1-λ)^t\, (S_t=s _n)\;≥\;(1-λ)^H-1\,η _n(s) ∀ s . Proof. The policy-induced state-transition kernel satisfies Pπ~λ(s′|s)≥(1−λ)Pπn(s′|s)P π_λ(s |s)≥(1-λ)\,P _n(s |s) entrywise. Let μtλ(s):=Pr(St=s∣π~λ) _t^λ(s):= (S_t=s π_λ) and μtn(s):=Pr(St=s∣πn) _t^n(s):= (S_t=s _n). Induction on t (base μ0λ=μ0n=d0 _0^λ= _0^n=d_0; inductive step μt+1λ(s′)=∑sμtλ(s)Pπ~λ(s′|s)≥(1−λ)t+1μt+1n(s′) _t+1^λ(s )= _s _t^λ(s)P π_λ(s |s)≥(1-λ)^t+1 _t+1^n(s )) gives μtλ≥(1−λ)tμtn _t^λ≥(1-λ)^t _t^n. Summing with γtγ^t weights and bounding (1−λ)t≥(1−λ)H−1(1-λ)^t≥(1-λ)^H-1 for t≤H−1t≤ H-1 completes the proof. ∎ F.7 Floored greedy comparator Definition 1 (Floored greedy policy). The floored greedy policy at iterate πn _n is πnG,pmin(a|s)=1−(||−1)pmin,a=as∗:=argmaxaQπn(s,a),pmin,a≠as∗. _n^G,p_ (a|s)= cases1-(|A|-1)\,p_ ,&a=a_s^*:= _aQ _n(s,a),\\ p_ ,&a≠ a_s^*. cases Lemma 19 (Floored-greedy advantage decomposition). For every state s, ∑aπnG,pmin(a|s)Aπn(s,a)=(1−||pmin)maxaAπn(s,a)+pmin∑aAπn(s,a), _a _n^G,p_ (a|s)\,A _n(s,a)\;=\;(1-|A|\,p_ )\, _aA _n(s,a)\;+\;p_ _aA _n(s,a), and consequently ∑aπnG,pmin(a|s)Aπn(s,a)≥(1−||pmin)maxaAπn(s,a)−pmin||Amax. _a _n^G,p_ (a|s)\,A _n(s,a)\;≥\;(1-|A|\,p_ )\, _aA _n(s,a)\;-\;p_ \,|A|\,A_ . Proof. Directly, ∑aπnG,pmin(a|s)Aπn(s,a)=(1−(||−1)pmin)Aπn(s,as∗)+pmin∑a≠as∗Aπn(s,a). _a _n^G,p_ (a|s)\,A _n(s,a)=(1-(|A|-1)p_ )A _n(s,a_s^*)+p_ _a≠ a_s^*A _n(s,a). Writing the first coefficient as 1−||pmin+pmin1-|A|p_ +p_ and combining the pminp_ terms gives the equality. The inequality follows from ∑aAπn(s,a)≥−||Amax _aA _n(s,a)≥-|A|A_ and Aπn(s,as∗)=maxaAπn(s,a)≥0A _n(s,a_s^*)= _aA _n(s,a)≥ 0. ∎ F.8 Global inner optimum lower bound Lemma 20 (Global inner optimum lower bound). Under Assumptions 1–2, with λ=min(2δ/CG,1/2)λ= ( 2δ/C_G,1/2), CG=1/pmin−1C_G=1/p_ -1, c=λ(1−||pmin)(1−λ)H−1/C∞c=λ(1-|A|p_ )(1-λ)^H-1/C_∞ and β=λpmin||AmaxZHβ=λ\,p_ \,|A|\,A_ \,Z_H: −Φn∗=maxy∈ℱn[J(π)−J(πn)]≥cΔn−β.- _n^*\;=\; _y _n\,[J(π)-J( _n)]\;≥\;c\, _n\;-\;β. Proof. Consider the mixture π~λ=(1−λ)πn+λπnG,pmin π_λ=(1-λ) _n+λ\, _n^G,p_ . Step 1 (Feasibility). Both components satisfy the floor (πn _n by Assumption 1, the floored greedy by construction), and the floor is preserved under mixtures: π~λ(a|s)≥(1−λ)pmin+λpmin=pmin π_λ(a|s)≥(1-λ)p_ +λ p_ =p_ . For the per-state χ2χ^2 trust region, χ2(πnG,pmin(⋅|s)∥πn(⋅|s))=∑aπnG,pmin(a|s)2/πn(a|s)−1≤1/pmin−1=CGχ^2( _n^G,p_ (·|s)\| _n(·|s))= _a _n^G,p_ (a|s)^2/ _n(a|s)-1≤ 1/p_ -1=C_G (using ∑aqa2≤maxaqa≤1 _aq_a^2≤ _aq_a≤ 1 for any distribution q and πn≥pmin _n≥ p_ ). The affine identity χ2((1−λ)q+λp∥q)=λ2χ2(p∥q)χ^2((1-λ)q+λ p\,\|\,q)=λ^2χ^2(p\|q) then gives D2s(π~λ∥πn)=λ22χ2(πnG,pmin∥πn)≤λ2CG2≤δD_2^s( π_λ\| _n)= λ^22χ^2( _n^G,p_ \| _n)≤ λ^2C_G2≤δ. So π~λ∈ℱn π_λ _n (its log-ratio satisfies validity exactly since π~λ π_λ is a distribution). Step 2 (PDL for the mixture). Using the state-visitation form with the un-normalized measure and ∑aπn(a|s)Aπn(s,a)=0 _a _n(a|s)A _n(s,a)=0: J(π~λ)−J(πn)=∑sηπ~λ(s)∑aπ~λ(a|s)Aπn(s,a)=λ∑sηπ~λ(s)∑aπnG,pmin(a|s)Aπn(s,a).J( π_λ)-J( _n)= _sη π_λ(s) _a π_λ(a|s)\,A _n(s,a)=λ _sη π_λ(s) _a _n^G,p_ (a|s)\,A _n(s,a). Step 3 (Split via the advantage decomposition). By Lemma 19 (equality form), the inner sum splits into a non-negative main term and a signed residual: ∑aπnG,pmin(a|s)Aπn(s,a)=(1−||pmin)Δ∗(s)+pminΣ(s), _a _n^G,p_ (a|s)A _n(s,a)=(1-|A|p_ )\, ^*(s)+p_ (s), with Δ∗(s):=maxaAπn(s,a)≥0 ^*(s):= _aA _n(s,a)≥ 0 and Σ(s):=∑aAπn(s,a) (s):= _aA _n(s,a), |Σ(s)|≤||Amax| (s)|≤|A|A_ . Step 4 (Main term: dominance and concentrability). Since Δ∗(s)≥0 ^*(s)≥ 0, Lemma 18 and Assumption 2 give ∑sηπ~λ(s)Δ∗(s)≥(1−λ)H−1∑sηπn(s)Δ∗(s)≥(1−λ)H−1C∞∑sηπ∗(s)Δ∗(s). _sη π_λ(s)\, ^*(s)\;≥\;(1-λ)^H-1 _sη _n(s)\, ^*(s)\;≥\; (1-λ)^H-1C_∞ _sη^π^*(s)\, ^*(s). Pointwise domination Δ∗(s)≥∑aπ∗(a|s)Aπn(s,a) ^*(s)≥ _aπ^*(a|s)A _n(s,a) and the PDL applied to π∗π^* give ∑sηπ∗(s)Δ∗(s)≥J(π∗)−J(πn)=Δn _sη^π^*(s) ^*(s)≥ J(π^*)-J( _n)= _n. Step 5 (Residual term: uniform bound). The residual is weighted by the mixture measure ηπ~λη π_λ, which neither the (one-sided) concentrability assumption nor the (lower-bound) dominance lemma can relate to ηπ∗η^π^*. We therefore bound it uniformly: |∑sηπ~λ(s)pminΣ(s)|≤pmin||Amax∑sηπ~λ(s)=pmin||AmaxZH, | _sη π_λ(s)\,p_ \, (s) |\;≤\;p_ \,|A|\,A_ _sη π_λ(s)\;=\;p_ \,|A|\,A_ \,Z_H, using only that the total mass of ηπ~λη π_λ is ZHZ_H. No distribution-shift step is needed or used. Step 6 (Collecting). Combining Steps 2–5: J(π~λ)−J(πn)≥λ(1−||pmin)(1−λ)H−1C∞⏟cΔn−λpmin||AmaxZH⏟β.J( π_λ)-J( _n)\;≥\; λ(1-|A|p_ )(1-λ)^H-1C_∞_c\, _n\;-\; λ\,p_ \,|A|\,A_ \,Z_H_β. Since π~λ∈ℱn π_λ _n and −Φn∗- _n^* maximizes J(π)−J(πn)J(π)-J( _n) over ℱnF_n, the bound transfers to −Φn∗- _n^*. ∎ Remark 5 (On the uniform bound in Step 5). The floor forces the comparator to place mass pminp_ on every action, including those of negative advantage, producing the residual pminΣ(s)p_ (s) weighted by the mixture occupancy ηπ~λη π_λ. That residual cannot be re-weighted to ηπ∗η^π^*: Assumption 2 bounds ηπ∗/ηπnη^π^*/η _n from above while Lemma 18 bounds ηπ~λη π_λ from below, so neither controls ηπ~λη π_λ from above by ηπ∗η^π^*; a state rarely visited by π∗π^* but heavily visited by the mixture would break such an inequality. We therefore bound it uniformly, using only that ηπ~λη π_λ has total mass ZHZ_H. The price is the worst-case product ||AmaxZH|A|\,A_ \,Z_H in β, which still vanishes linearly as pmin→0p_ → 0. F.9 Per-step improvement and outer-loop contraction Let Φn _n be the inner objective of Section 5.1 instantiated at iteration n (with data sampled under πn _n) and Φn∗:=minℱnΦn _n^*:= _F_n _n its global minimum. Let yny_n be any point returned by the inner loop: Proposition 16 guarantees feasibility for ℱnF_n; as R grows, Theorem 17 drives the stationarity residual to zero, but the bound below uses only feasibility and the value gap ϵn:=Φn(yn)−Φn∗≥ 0, _n\;:=\; _n(y_n)- _n^*\;≥\;0, the inner-solve gap. In particular the outer-loop analysis needs neither d-stationarity of yny_n nor any rate for the inner iteration, which is what makes the two guarantees modular. The constants λ=min(2δ/CG,1/2)λ= ( 2δ/C_G,1/2), CG=1/pmin−1C_G=1/p_ -1, c=λ(1−||pmin)(1−λ)H−1/C∞c=λ(1-|A|p_ )(1-λ)^H-1/C_∞ and β=λpmin||AmaxZHβ=λ\,p_ \,|A|\,A_ \,Z_H are as in Lemma 20. The two inequalities of Theorem 6 follow from the per-step bound below and its telescoping (Appendix F.10). Theorem 21 (Per-step improvement). Under Assumptions 1–2, with the constants above, J(πn+1)−J(πn)≥cΔn−β−ϵn.J( _n+1)-J( _n)\;≥\;c\, _n\;-\;β\;-\; _n. (27) Proof. The policy πn+1 _n+1 is recovered from the returned point yny_n, feasible for ℱnF_n, with value Φn(yn)=Φn∗+ϵn _n(y_n)= _n^*+ _n by definition of the gap ϵn _n. Because at k=Hk=H the inner objective equals the true performance difference (no surrogate bias), J(πn+1)−J(πn)=−Φn(yn)=−Φn∗−ϵnJ( _n+1)-J( _n)=- _n(y_n)=- _n^*- _n. Applying Lemma 20: −Φn∗≥cΔn−β- _n^*≥ c\, _n-β. Substituting: J(πn+1)−J(πn)≥cΔn−β−ϵnJ( _n+1)-J( _n)≥ c\, _n-β- _n. ∎ F.10 Proof of Theorem 6 (Outer-loop contraction) Proof. By Theorem 21, Δn+1=Δn−[J(πn+1)−J(πn)]≤(1−c)Δn+β+ϵn≤(1−c)Δn+β+ϵ¯. _n+1= _n-[J( _n+1)-J( _n)]≤(1-c)\, _n+β+ _n≤(1-c)\, _n+β+ ε. Iterating the affine recursion: ΔN≤(1−c)NΔ0+(β+ϵ¯)∑j=0N−1(1−c)j≤(1−c)NΔ0+β+ϵ¯c.∎ _N≤(1-c)^N\, _0+(β+ ε) _j=0^N-1(1-c)^j≤(1-c)^N\, _0+ β+ εc. Remark 6 (Status of Theorem 6). This is a conditional contraction, not a stand-alone convergence guarantee. Theorem 17 drives the stationarity residual of the inner iteration to zero, but provides no algorithmic upper bound on the gap ϵn _n between the returned point’s value and the global minimum of the (non-convex) per-iteration program. The bound is informative when ϵ¯ ε is small—which can be probed empirically, e.g. by multi-start SCP—and uninformative otherwise. The residual neighborhood (β+ϵ¯)/c(β+ ε)/c likewise contains the floor bias β, which is a property of the algorithm’s feasible set and vanishes as pmin→0p_ → 0 (though the inner-loop constants degrade in that limit; cf. Remark 8). Remark 7 (Horizon dependence). The contraction constant c contains the factor (1−λ)H−1(1-λ)^H-1, which decays exponentially in the horizon for fixed λ. This is inherited from the mixture state-visitation dominance argument (Lemma 18) and is a known cost of CPI-style mixture analyses; improving it (e.g. per-state improvement accounting) is an open direction. Remark 8 (Dependence of constants on pminp_ ). The smoothness constants Lf,LΦL_f,L_ (hence ρ0 _0 and the Tier-2 rate constant κ) are finite on the compact box K of (23) but degrade as pmin→0p_ → 0, since K grows and the exponentials steepen; the drift budget B(ρ)=Lf(Φ(y0)−infKextΦ)/(ρ−ρ0)B(ρ)=L_f( (y^0)- _K_ ext )/(ρ- _0) grows with them, so holding B(ρ)≤1B(ρ)≤ 1 requires a larger ρ. The “β→0β→ 0 as pmin→0p_ → 0” statement in Remark 6 therefore trades outer-loop bias against inner-loop conditioning. Appendix G Additional Experimental Results This appendix reports the supporting analyses and full experimental setups referenced in Section 7. G.1 Risky Corridor MDP: advantage under the uniform behavior policy We derive Aπb(s0,L)A _b(s_0,L) used in Section 7.1. The Risky Corridor MDP has horizon H=2H=2, γ=1γ=1, and deterministic transitions (Figure 1(a)). Under a uniform behavior policy πb _b: Vπb(sR) V _b(s_R) =1(single action, terminal), =1 (single action, terminal), Vπb(sL) V _b(s_L) =12(100)+12(−80)=10, = 12(100)+ 12(-80)=10, Vπb(s0) V _b(s_0) =12(−20+Vπb(sL))+12(3+Vπb(sR)) = 12 (-20+V _b(s_L) )+ 12 (3+V _b(s_R) ) =12(−10)+12(4)=−3. = 12(-10)+ 12(4)=-3. The Q-values at s0s_0 are Qπb(s0,L)=−20+Vπb(sL)=−10Q _b(s_0,L)=-20+V _b(s_L)=-10 and Qπb(s0,R)=3+Vπb(sR)=4Q _b(s_0,R)=3+V _b(s_R)=4, giving Aπb(s0,L)=−10−(−3)=−7,Aπb(s0,R)=4−(−3)=7.A _b(s_0,L)=-10-(-3)=-7, A _b(s_0,R)=4-(-3)=7. The single-step advantage of the optimal action L is therefore negative under πb _b, which is what makes the MDP a stress test for the CPI surrogate at k=1k=1. G.2 Risky Corridor MDP: detailed results Table 5 reports the quantitative results corresponding to the convergence experiment in Section 7.1: area under the normalized return curve (AUC), final normalized return, and steps to reach 90%90\% of optimal performance (t90t_90). All four methods use a common budget of 3232 episodes per update over 1010 updates, and each is tuned by the same two-stage protocol. We first evaluate every configuration in the method’s grid (900900, 432432, 432432, and 288288 configurations for PPO, CCRL, AWR, and TRPO) on 1010 tuning seeds, rank by AUC with final return and t90t_90 as tie-breakers, and retain the top five. These five are re-evaluated on 100100 validation seeds, disjoint from the tuning seeds, and the best of the five is reported. Means and standard errors below are over those 100100 validation seeds. Method AUC Final return t90t_90 PPO 8.1951 ± 0.0509 0.9662 ± 0.0056 3.29 ± 0.09 TRPO 8.4924 ± 0.0261 0.9996 ± 0.0002 3.13 ± 0.04 AWR 8.9028 ± 0.0817 0.9908 ± 0.0091 2.09 ± 0.09 CCRL 9.2057 ± 0.0882 0.9908 ± 0.0091 1.38 ± 0.11 Table 5: Risky Corridor MDP results across PPO, TRPO, AWR, and CCRL: AUC of the normalized return curve, final normalized return, and steps-to-90%90\%-of-optimal (t90t_90). Mean ± SE over 100100 validation seeds. Best mean per metric in bold where unique. G.3 Advantage-estimation quality on CartPole This appendix details the advantage-estimation quality experiment referenced in Section 7.3; the results are summarized in Figure 3. Figure 3: Advantage-estimation quality across training checkpoints (CartPole). Six advantage estimators—a Monte-Carlo baseline (Gt−VG_t-V), TD(0), and GAE at λ∈0,0.5,0.9,0.95λ∈\0,0.5,0.9,0.95\—are compared against a Monte-Carlo ground-truth advantage at five policy checkpoints (x-axis), along MSE on a log scale (left), Pearson correlation (center), and sign agreement (right). Dotted reference lines mark zero correlation and 50%50\% (chance) sign agreement. No single estimator dominates: the MC baseline and high-λ GAE (0.9,0.950.9,0.95) incur the largest MSE by an order of magnitude, while TD(0) and low-λ GAE (λ=0λ=0) achieve both the lowest MSE and the highest correlation and sign agreement; the GAE variants interpolate between these extremes as λ grows. Across all estimators, correlation and sign agreement decay toward their no-information values (zero correlation, 50%50\% sign agreement) as the policy improves. Environment and policy. We use CartPole (horizon H=200H=200, undiscounted γ=1γ=1, +1+1 per surviving step) with a softmax policy parameterized by a 4→32→32→24→32→32→2 tanh MLP. The policy is trained for 20002000 episodes by REINFORCE with return standardization, batch size 1616, and Adam at learning rate 10−310^-3, saving a checkpoint every 400400 episodes. This yields five checkpoints whose average return rises from 24.524.5 to 60.460.4, letting us track estimation quality as the policy improves. Ground-truth advantage. At each checkpoint we freeze the policy πn _n and collect 5050 evaluation trajectories. For every visited state-action pair (s,a)(s,a) we form a near-unbiased target Aπn(s,a)=Qπn(s,a)−Vπn(s)A _n(s,a)=Q _n(s,a)-V _n(s) by Monte-Carlo rollouts under πn _n: Vπn(s)V _n(s) averages the return of 5050 rollouts from s, and Qπn(s,a)Q _n(s,a) averages 5050 rollouts that first take a and then follow πn _n. All estimators are scored against this target. Estimators. We evaluate six estimators, each built on a learned value critic (a 4→64→64→14→64→64→1 tanh MLP trained 300300 epochs with Adam at 10−310^-3). Two distinct critics are fit, and each estimator uses the one conventional for it: • the TD(0) critic is trained by minimizing the squared TD error (V(S)−[R+V(S′)])2 (V(S)-[\,R+V(S )\,] )^2 (one-step bootstrapping, with a stop-gradient on the target V(S′)V(S )); • the MC critic is trained by regression onto Monte-Carlo return samples, i.e. minimizing (V(St)−Gt)2(V(S_t)-G_t)^2 against the empirical return-to-go GtG_t. The estimators are then: • MC baseline: A^(St,At)=Gt−V(St) A(S_t,A_t)=G_t-V(S_t), with GtG_t the empirical return-to-go and V the MC critic; • TD(0): A^(St,At)=Rt+1+V(St+1)−V(St) A(S_t,A_t)=R_t+1+V(S_t+1)-V(S_t) using the TD(0) critic; • GAE(λ) for λ∈0,0.5,0.9,0.95λ∈\0,0.5,0.9,0.95\: the exponentially-weighted sum A^t=∑l≥0λlδt+l A_t= _l≥ 0λ^l _t+l, computed by the backward recursion A^t=δt+λA^t+1 A_t= _t+λ\, A_t+1 with one-step TD residual δt=Rt+1+V(St+1)−V(St) _t=R_t+1+V(S_t+1)-V(S_t) on the MC critic (terms truncated at episode end). Thus the TD(0) advantage draws on the TD-error-trained critic, while the MC baseline and every GAE variant draw on the MC-return-trained critic. Since γ=1γ=1, the discount is dropped throughout; GAE(00) reduces to the one-step residual on the MC critic. Metrics. We report three metrics, each computed over state-action pairs with a non-negligible true advantage (|Aπn|>0.5|A _n|>0.5): Pearson correlation between estimated and true advantage, sign agreement (the fraction of pairs whose estimated advantage has the correct sign), and mean-squared error (MSE). Findings. Figure 3 reports all three metrics against training progress. Two patterns stand out. First, no estimator is uniformly best: low-λ GAE and TD(0) minimize MSE (≈22–37≈ 22--37) but the Monte-Carlo baseline and high-λ GAE incur an order-of-magnitude larger MSE (∼102–103 \!10^2--10^3). Second, and most relevant to CCRL, correlation and sign agreement are modest and deteriorate as the policy improves: TD(0) correlation falls from 0.250.25 to 0.030.03 and sign agreement drifts from ∼68% \!68\% toward the 50%50\% chance line. Because the DC decomposition (Theorem 1) assigns terms to Jk+J_k^+ / Jk−J_k^- by advantage sign, this sign-error rate directly sets how far the optimized manifold departs from the true one. G.4 PDIS-k objective variance on CartPole This appendix details the variance experiment referenced in Section 7.3; the results are summarized in Figure 4. The experiment isolates the effect of the truncation depth k on the variance of the per-trajectory objective estimator, holding the advantages fixed so that variance differences are attributable to the k-step importance-sampling window alone. Figure 4: PDIS-k objective variance grows with the truncation depth k (CartPole). At five policy checkpoints (x-axis), the per-trajectory objective J^k(τ) J_k(τ) is evaluated at the SCP-optimized log-ratios for k∈1,2,3k∈\1,2,3\ over 200200 trajectories, with the advantages held fixed at their Monte-Carlo ground-truth values. Left: variance of J^k J_k across trajectories (log scale); center: its coefficient of variation (std over ||mean||); right: the standard deviation of the cumulative importance-sampling weights e∑ye^Σ y (log scale). Variance is ordered k=1<k=2<k=3k=1<k=2<k=3 throughout and separates by two to three orders of magnitude per increment of k, driven by the widening spread of the IS weights. Environment, policy, and checkpoints. We use the same CartPole setup and REINFORCE-trained policy as in Appendix G.3 (4→32→32→24→32→32→2 tanh softmax policy, 20002000 episodes, checkpoint every 400400), giving five checkpoints with average return rising from 24.524.5 to 62.362.3. Here we discount with γ=0.99γ=0.99. Protocol. At each checkpoint we freeze the policy and collect N=200N=200 trajectories. For every visited pair we compute the near-exact Monte-Carlo advantage Aπn(s,a)=Qπn(s,a)−Vπn(s)A _n(s,a)=Q _n(s,a)-V _n(s) (5050 rollouts each for QπnQ _n and VπnV _n), exactly as in Appendix G.3. We then solve the CCRL inner problem (9) by SCP (44 rounds of 5050 inner primal-dual iterations, step size 0.10.1, per-state χ2χ^2 trust region with α=2α=2, δ=0.2δ=0.2, log-ratios clipped to |y|≤3|y|≤ 3) separately for each k∈1,2,3k∈\1,2,3\, obtaining optimized log-ratios y(s,a)y(s,a). Crucially, the advantages are shared across all three solves; only the k-window in the objective changes. Variance measure. For each k and each trajectory τi _i we evaluate the per-trajectory objective J^k(τi)=∑t=0Li−1γtexp(∑t′=max(0,t−k+1)ty(st′,at′))Aπn(st,at), J_k( _i)= _t=0^L_i-1γ^t\, \! ( _t = (0,\,t-k+1)^ty(s_t ,a_t ) )\,A _n(s_t,a_t), (28) and report its variance and coefficient of variation (std over ||mean||) across the N trajectories, together with the standard deviation of the cumulative importance-sampling weights e∑ye^Σ y that appear inside (28). Findings. Figure 4 reports all three quantities against training progress. The estimator variance is ordered k=1<k=2<k=3k=1<k=2<k=3 at every checkpoint, separating by roughly two to three orders of magnitude per unit increase in k (e.g. at the final checkpoint, Var[J^1]≈104Var[ J_1]≈ 10^4, Var[J^2]≈106Var[ J_2]≈ 10^6, and Var[J^3]≈1010Var[ J_3]≈ 10^10). The coefficient of variation is likewise ordered by k, and the right panel shows the mechanism directly: the spread of the IS weights e∑ye^Σ y grows sharply with k (the maximum weight rises from ∼20 \!20 at k=1k=1 to ∼8000 \!8000 at k=3k=3), since the exponential of a k-term sum of log-ratios amplifies trajectory-to-trajectory variation. This is the bias–variance tension of the truncation depth: larger k couples credit across more decisions but at rapidly growing estimator variance. G.5 Risky Chain: hyperparameter grids and tuning protocol This appendix gives the full tuning setup behind the Risky Chain results of Section 7.2, so that the fairness of the PPO comparison can be checked directly. The MDP is illustrated in Figure 5. s0s_0s1s_1⋯·ssN−2s_N-2sN−1s_N-1continue, −5-5continue, −5-5continue, −5-5continue, −5-5exit, +1+1exit, +1+1exit, +1+1a+,+100a^+,+100a−,−80a^-,-80 Figure 5: Risky chain MDP with N stages (γ=1γ=1). Each intermediate state sis_i (i<N−1i<N-1) offers a safe-exit action (reward +1+1, terminal) or a continue action (reward −5-5, advance). The terminal state sN−1s_N-1 has two actions: a+a^+ (reward +100+100) and a−a^- (reward −80-80). The optimal trajectory is s0→s1→⋯→sN−1→a+s_0→ s_1→·s→ s_N-1→ a^+, with return 100−5(N−1)100-5(N-1). Networks. The policy and value are each a one-hidden-layer MLP (tanh activation; 1616 or 3232 hidden units, selected by tuning) mapping a one-hot state encoding to action logits and to a scalar value, respectively. PPO and CCRL use the identical architecture, so any performance difference is attributable to the policy-improvement operator alone. Two-stage protocol. Each (algorithm, N, k) cell is tuned independently; nothing is shared or transferred across cells. The per-update data budget is fixed at 128128 trajectories and the number of policy-improvement iterations at 200200 for every arm. Stage 1 (selection). We evaluate the entire grid on a fixed set of 1010 tuning seeds 7,11,19,23,31,37,41,43,47,53\7,11,19,23,31,37,41,43,47,53\ and rank configurations by nAUC (with final return and then −t90-t_90 as tie-breakers). We rank by nAUC rather than final return because the per-seed final return is near-bimodal on this task—a seed either solves the chain or collapses to early exit—so nAUC is the lower-variance selection signal. We keep the top 1212 configurations. Stage 2 (validation). The top 1212 are re-evaluated on 300300 fresh validation seeds (seed base 300,000300,000, disjoint from the tuning seeds), and the configuration with the best mean final return is reported. All numbers in Table 1 are Stage-2 validation numbers. Search grids. Table 6 lists the grids. The entropy-bonus coefficient uses the same six values for both algorithms, and both tune the hidden width, so PPO is never disadvantaged on exploration or capacity. The PPO grid spans 12961296 configurations per cell and the CCRL grid 34563456; deeper chains require the larger entropy values to reliably reach the optimum under either algorithm. Table 6: Hyperparameter grids for the Risky Chain study (batch fixed at 128128, 200200 iterations, γ=1γ=1). The entropy grid is shared across methods. PPO (12961296 configs/cell) hidden width 16,32\16,32\ policy learning rate 0.01,0.05,0.1\0.01,0.05,0.1\ critic learning rate 0.05,0.1\0.05,0.1\ epochs per update 10,20,40\10,20,40\ clip ε 0.1,0.2,0.3\0.1,0.2,0.3\ GAE-λ 0.95,1.0\0.95,1.0\ entropy-bonus coef. 0,7,15,30,50,80\0,7,15,30,50,80\ CCRL (34563456 configs/cell) hidden width 16,32\16,32\ policy (M-step) learning rate 0.05,0.1\0.05,0.1\ M-step epochs 40,80\40,80\ divergence order α 1.5,2.0,3.0\1.5,2.0,3.0\ trust radius δ 0.05,0.1,0.2\0.05,0.1,0.2\ SCP rounds 5,8\5,8\ SCP inner iterations 120,240\120,240\ SCP inner learning rate 0.01,0.03\0.01,0.03\ GAE-λ 0.95,1.0\0.95,1.0\ entropy-bonus coef. 0,7,15,30,50,80\0,7,15,30,50,80\ G.6 Therapeutic-Threshold Sepsis MDP: environment and experimental setup This appendix specifies the Therapeutic-Threshold Sepsis MDP of Section 7.4 and the protocol used for the PPO/CCRL comparison reported there. Environment. A state is a pair (h,d)(h,d): illness severity h∈0,…,M−1h∈\0,…,M-1\ and accumulated dose level d∈0,…,D−1d∈\0,…,D-1\, giving ||=M⋅D|S|=M\!·\!D states. Severity h=0h=0 (recovered) and h=M−1h=M-1 (dead) are absorbing. Every episode starts deterministically at mid-severity with zero dose, (h,d)=(⌊(M−1)/2⌋, 0)(h,d)=( (M-1)/2 ,\,0), and runs for a fixed horizon H=20H=20. Three actions are available—rest, dose, and administer—with the following transitions from a non-terminal (h,d)(h,d) (severity moves by at most one level per step): • rest: d is unchanged; h→h+1h→ h+1 with probability prest=0.40p_rest=0.40, otherwise unchanged. • dose: d→min(d+1,D−1)d→ (d+1,\,D-1); h→h+1h→ h+1 with probability pdose=0.20p_dose=0.20, otherwise unchanged. • administer: the dose resets, d→0d→ 0, and at threshold (d=D−1d=D-1) the patient recovers, h→h−1h→ h-1, with probability prec=0.90p_rec=0.90 (else unchanged), while below threshold (d<D−1d<D-1) the patient is harmed, h→h+1h→ h+1, with probability pharm=0.70p_harm=0.70 (else unchanged). A reward of +1+1 is delivered on any transition into h=0h=0 (recovery) and 00 on every other transition, including into h=M−1h=M-1 (death); the reward is thus sparse and terminal, and the undiscounted expected return equals the survival probability. We use M=5M=5 severity levels and D=3D=3 doses to threshold, for which the finite-horizon optimal policy—computed exactly by dynamic programming—survives 0.8400.840 of episodes. Because dose never yields reward and can only hold or worsen severity, its one-step advantage is negative; survival requires committing to D successive doses before administering, so the credit-assignment depth is exactly D. Algorithms and training. Both PPO and CCRL use a parametric MLP policy and critic with a one-hot state encoding, fit a GAE value baseline, and train for 500500 updates at a matched per-update budget. CCRL solves the per-iteration DC program (9) by SCP with a per-state α-divergence trust region and the y-clip of Section 6; PPO uses the standard clipped surrogate. The k-step objective and the clipped surrogate each carry a variance-control knob—CCRL’s clip ymaxy_ and PPO’s clip ε —so we sweep that knob for each method and, at every value, sub-tune the remaining hyperparameters (learning rates, trust-region and inner-loop settings, entropy) so that each reported point is the best that setting attains. Configurations are evaluated over 100100 seeds, and we report the final survival rate, the area under the survival curve (AUC), and t90t_90 (updates to first reach 90%90\% of the dynamic-programming optimum, i.e. 0.7560.756). Hyperparameter tuning. Each cell is tuned independently by the same two-stage protocol used for the Risky Chain (Appendix G.5), at a fixed budget of 128128 episodes per update; nothing is shared or warm-started across cells. Stage 1 (selection). We evaluate the method’s entire grid on 1010 tuning seeds 7,11,19,23,31,37,41,43,47,53\7,11,19,23,31,37,41,43,47,53\ and rank configurations by AUC. The PPO grid sweeps hidden width 16,32\16,32\, policy learning rate 0.01,0.05,0.1\0.01,0.05,0.1\, epochs per update 10,20,40\10,20,40\, clip ε∈0.1,0.2,0.3 ∈\0.1,0.2,0.3\, discount 0.99,1.0\0.99,1.0\, critic learning rate 0.05,0.1\0.05,0.1\, and entropy coefficient 0,0.02,0.05,0.1,0.2,0.5\0,0.02,0.05,0.1,0.2,0.5\, giving 12961296 configurations per cell. The CCRL grid sweeps hidden width 16,32\16,32\, policy learning rate 0.05,0.1\0.05,0.1\, policy-fit projection steps 40,80\40,80\, divergence order α∈1.5,2.0,3.0α∈\1.5,2.0,3.0\, trust-region budget δ∈0.05,0.1,0.2δ∈\0.05,0.1,0.2\, inner step size 0.01,0.03\0.01,0.03\, SCP rounds 5,8\5,8\, inner primal-dual iterations 120,240\120,240\, and the same entropy grid, giving 34563456 configurations per cell. Stage 2 (validation). The top 1212 configurations are re-evaluated on 100100 validation seeds disjoint from the tuning seeds, and the best of those is reported. The entropy coefficient is swept on the same grid for both methods, so PPO is never disadvantaged on exploration or capacity. G.7 Classic control: environment and experimental setup This appendix details the classic-control comparison of Section 7.3; the main-text figure is Figure 2. We use four standard discrete-action Gymnasium environments—CartPole-v1, Acrobot-v1, MountainCar-v0, and LunarLander-v3—and compare a tuned PPO baseline against CCRL at truncation depths k∈1,2,3k∈\1,2,3\. Each of the sixteen (environment, algorithm) cells is independently hyperparameter-tuned; the selected configurations are then run over 100100 seeds (seeds 00–9999) for 200200 policy iterations. For CCRL, advantages are estimated by GAE and the per-iteration DC program is solved by the tangent-plane SCP of Section 4; PPO uses the standard clipped surrogate. We report the per-seed learning curve (return vs. iteration), the final return (average over the last 1010 iterations), and the area under the learning curve (AUC, mean return per iteration), aggregated as mean ± standard error over seeds. Appendix H Extended related work Iterative on-policy policy optimization. A large family of methods improves a policy by repeatedly maximizing a per-iteration surrogate of J(π)J(π) under a proximity constraint to the current iterate. Conservative Policy Iteration (CPI) (Kakade and Langford, 2002) established the surrogate-based template; natural policy gradient (NPG) (Kakade, 2002), TRPO (Schulman et al., 2015), and PPO (Schulman et al., 2017) instantiate it with different trust-region mechanisms (exact KL, clipping), and advantage-weighted regression—AWR (Peng et al., 2019) and AWAC (Nair et al., 2020)—recasts the update as regression onto an exponentially-tilted behavior policy, π∗(a|s)∝πb(a|s)exp(Aπb(s,a)/η)π^*(a|s) _b(a|s) (A _b(s,a)/η). All of these optimize the single-step (k=1k=1) CPI surrogate; CCRL recovers that surrogate and instantiates CPI, NPG, TRPO, and AWR as (k,α,validity)(k,α,validity) special cases (Section 3.5)—PPO’s clipping heuristic and AWAC’s off-policy reuse lie outside this (α,validity)(α,validity) family—and extends the template along the multi-step axis k≥2k≥ 2. Multi-step credit assignment. The difficulty of propagating credit across delayed rewards is classically addressed by injecting multi-step information into the value target: TD(λ) and eligibility traces (Sutton, 1988) interpolate between one-step bootstrapping and Monte-Carlo returns, generalized advantage estimation (GAE) (Schulman et al., 2016) applies the same exponential weighting to advantage estimates for variance reduction, and off-policy return operators such as Retrace(λ) (Munos et al., 2016) correct for the behavior–target mismatch with truncated importance weights. These methods shape the advantage estimates fed into a single-step update; CCRL is complementary—it places the multi-step horizon k inside the optimization objective itself (2), so the policy update, not just the critic target, couples consecutive decisions. Importance sampling as an optimization objective. PDIS and its variants (Precup et al., 2000; Jiang and Li, 2016) are primarily studied for off-policy evaluation. A closer line uses importance sampling as an optimization objective: POIS (Metelli et al., 2018) reuses collected trajectories by optimizing an IS-based surrogate offline, with a high-confidence penalty controlling the estimator’s variance. We likewise treat PDIS as the optimization target rather than an evaluation estimator, but expose the surrogate’s difference-of-convex structure in log-density-ratio coordinates and use the truncation depth k to trade off multi-step credit propagation against variance. Convergence of policy-gradient methods. Tabular policy-gradient convergence has been established at several rates. Mei et al. (2020) give O(1/t)O(1/t) global convergence for softmax PG via a non-uniform Łojasiewicz inequality, though Li et al. (2023) show the effective iteration count can be exponential in ||/(1−γ)|S|/(1-γ). Agarwal et al. (2021) give O(1/ε)O(1/ ) suboptimality for natural policy gradient (NPG) under direct parameterization. Cen et al. (2022) obtain linear convergence for entropy-regularized NPG, and Xiao (2022) sharpens this to linear convergence for policy mirror descent (PMD) with geometrically increasing step sizes (subsuming NPG) without entropy regularization. This line has since been generalized: Lan (2023) establishes linear convergence and sampling-complexity bounds for PMD across a broad class of regularized MDPs, and Alfano et al. (2023) extends linear-convergence guarantees to PMD with general (including neural) parameterizations. All of these global-convergence results depend on the k=1k=1 CPI-surrogate objective being linear in π; when the objective is non-convex, the general policy-gradient treatment in the RL-theory monograph of Agarwal et al. (2022) yields only gradient-stationarity guarantees rather than global rates. Our convergence analysis (Section 5) applies to k≥1k≥ 1 via the DC structure: an unconditional O(1/R)O(1/R) inner-loop stationarity rate for any k, and a conditional geometric contraction of the outer policy sequence at the exact-improvement setting k=Hk=H (with χ2χ^2 trust regions) under concentrability—comparable in form to the tabular linear rates above but proven for the exact multi-step objective, where linearity in π no longer holds. Difference-of-convex and geometric programming. The change of variable that convexifies our objective—taking logarithms to turn multiplicative importance-ratio products into additive exponentials—is the defining move of geometric programming, in which posynomial programs become convex in log-transformed variables (Boyd et al., 2007). Applied to the k-step PDIS objective, this exposes a difference-of-convex (DC) structure. DC programming has a long history (Tao and An, 1997; Lipp and Boyd, 2016; Thi and Dinh, 2018) but has seen limited use in reinforcement learning; our contribution is to identify the DC structure in the PDIS objective and to handle the policy-simplex validity constraint—a DC equality—within our SCP procedure (Section 4). We keep our guarantees at the assumption-free level standard for DCA, leaving full-sequence rates as an extension.