Convex-Concave Reinforcement Learning

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

cs.LGOct 6, 2026

Convex-Concave Reinforcement Learning

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

Organizations: University of Massachusetts · Institute of Foundation Models

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]$ , 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.

Figures & tables

Panel of Figure 1 — 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 $s_{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 ( $32$ episodes per update, $10$ updates) and are individually hyperparameter-tuned (protocol in Appendix G.2 ). (a) The MDP; (b) expected return over policy iterations, normalized so that $1$ is optimal and $0$ is the uniform-policy return (mean over $100$ seeds; shaded band is $\pm 1$ SE): CCRL is the only method to reach $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)=(\pi(a_{L}|s_{0}),\,\pi(a_{1}|s_{L}))$ space, from uniform $(0.5,0.5)$ toward the optimum $(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 $s_{L}$ , only CCRL commits to the pay-now direction at $s_{0}$ .

	$N=4$			$N=5$			$N=6$
Method	F $\uparrow$	nAUC $\uparrow$	$t_{90}\!\downarrow$	F $\uparrow$	nAUC $\uparrow$	$t_{90}\!\downarrow$	F $\uparrow$	nAUC $\uparrow$	$t_{90}\!\downarrow$
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{=}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{=}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{=}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{=}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)

Table 1 : PPO vs. CCRL on the Risky Chain. For each depth

N

we report the final normalized return (F;

\uparrow

1

=optimal,

0

=uniform-policy return), nAUC (

\uparrow

; mean normalized return over the

200

training iterations), and

t_{90}

(

\downarrow

; iterations to reach

90\%

of optimal), each as mean over

300

validation seeds with the stderr in parentheses in units of the last displayed digit (e.g.

0.939(13)=0.939\pm 0.013

9.4(23)=9.4\pm 2.3

). Best per metric column (within each

N

) in bold. Full-depth CCRL reaches

90\%

of optimal within about one iteration at every

N

and ends at a normalized return of

1.000

, whereas PPO’s final return and

t_{90}

steadily degrade as the chain deepens.

Figure 2 : Classic control: CCRL vs. PPO over

100

seeds. Return over

200

iterations (mean over

100

seeds; shaded band is

\pm 1

SE) for PPO and CCRL at

k\in\{1,2,3\}

on CartPole, Acrobot, MountainCar, and LunarLander. CCRL (

k=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 ).

Table 2 : Therapeutic-Threshold Sepsis (parametric MLP;

100

seeds;

500

updates; DP-optimal survival

0.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{\pm}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 (

\approx 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

y_{\max}

makes multi-step credit usable at every depth (row-max in bold), while a loose clip collapses deep

k

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Variant	$f$ -divergence (policy space)	$\alpha$ -divergence ( $y$ -space)
Trajectory-level	$\mathbb{E}_{\tau\sim p_{\pi_{n}}}\!\bigl[f(p_{\pi}(\tau)/p_{\pi_{n}}(\tau))\bigr]\leq\delta$	$\frac{1}{\alpha(\alpha-1)}\mathbb{E}_{\tau\sim p_{\pi_{n}}}\!\bigl[e^{\alpha\sum_{t}y(S_{t},A_{t})}-1\bigr]\leq\delta$
Strict per-state	$\mathbb{E}_{A\sim\pi_{n}(\cdot\|s)}\!\bigl[f(\pi(A\|s)/\pi_{n}(A\|s))\bigr]\leq\delta_{s},\;\forall s$	$\frac{1}{\alpha(\alpha-1)}\bigl(\mathbb{E}_{A\sim\pi_{n}(\cdot\|s)}\!\bigl[e^{\alpha\,y(s,A)}\bigr]-1\bigr)\leq\delta_{s},\;\forall s$
Expected per-state	$\mathbb{E}_{S\sim d^{\pi_{n}}}\!\bigl[\mathbb{E}_{A\sim\pi_{n}(\cdot\|S)}\!\bigl[f(\pi(A\|S)/\pi_{n}(A\|S))\bigr]\bigr]\leq\delta$	$\mathbb{E}_{S\sim d^{\pi_{n}}}\!\Bigl[\frac{1}{\alpha(\alpha-1)}\bigl(\mathbb{E}_{A\sim\pi_{n}(\cdot\|S)}\!\bigl[e^{\alpha\,y(S,A)}\bigr]-1\bigr)\Bigr]\leq\delta$

Appendix

Table 3 : Three variants of the trust-region constraint (Section 3.3 ), each in its general

f

-divergence form (policy space) and its corresponding

\alpha

-divergence form in log-density-ratio coordinates.

$\boldsymbol{\alpha}$	Divergence	Convex in $y$	Generator $f(t)$
$\alpha=2$	$\chi^{2}$	Yes	$(t-1)^{2}$
$\alpha=-1$	Reverse $\chi^{2}$	Yes	$(1-t)^{2}/t$
$\alpha\to 1^{+}$	Forward KL	No (limit on $\mathcal{M}$ only)	$t\log t$
$\alpha\to 0^{-}$	Reverse KL	Yes (linear on $\mathcal{M}$ )	$-\log t$
$\alpha=1/2$	Squared Hellinger	No	$2(\sqrt{t}-1)^{2}$
$\alpha>1$	Rényi (order $\alpha$ )	Yes	$(t^{\alpha}-1)/[\alpha(\alpha-1)]$

Appendix

Table 4 : Common

f

-divergences as special cases of the

\alpha

-divergence

D_{\alpha}(p\|q)=\tfrac{1}{\alpha(\alpha-1)}(\mathbb{E}_{q}[(p/q)^{\alpha}]-1)

. “Convex in

y

” refers to global convexity of the constraint in log-density-ratio coordinates.

Method	AUC		Final return		$t_{90}$
PPO	8.1951 $\pm$	0.0509	0.9662 $\pm$	0.0056	3.29 $\pm$	0.09
TRPO	8.4924 $\pm$	0.0261	0.9996 $\pm$	0.0002	3.13 $\pm$	0.04
AWR	8.9028 $\pm$	0.0817	0.9908 $\pm$	0.0091	2.09 $\pm$	0.09
CCRL	9.2057 $\pm$	0.0882	0.9908 $\pm$	0.0091	1.38 $\pm$	0.11

Appendix

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\%

-of-optimal (

t_{90}

). Mean

\pm

SE over

100

validation seeds. Best mean per metric in bold where unique.

Figure 3 : Advantage-estimation quality across training checkpoints (CartPole). Six advantage estimators—a Monte-Carlo baseline (

G_{t}-V

), TD(0), and GAE at

\lambda\in\{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\%

(chance) sign agreement. No single estimator dominates: the MC baseline and high-

\lambda

GAE (

0.9,0.95

) incur the largest MSE by an order of magnitude, while TD(0) and low-

\lambda

GAE (

\lambda{=}0

) achieve both the lowest MSE and the highest correlation and sign agreement; the GAE variants interpolate between these extremes as

\lambda

grows. Across all estimators, correlation and sign agreement decay toward their no-information values (zero correlation,

50\%

sign agreement) as the policy improves.

Figure 4 : PDIS-

k

objective variance grows with the truncation depth

k

(CartPole). At five policy checkpoints (x-axis), the per-trajectory objective

\hat{J}_{k}(\tau)

is evaluated at the SCP-optimized log-ratios for

k\in\{1,2,3\}

over

200

trajectories, with the advantages held fixed at their Monte-Carlo ground-truth values. Left: variance of

\hat{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^{\sum y}

(log scale). Variance is ordered

k{=}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.

Panel of Figure 5 — Figure 5 : Risky chain MDP with $N$ stages ( $\gamma=1$ ). Each intermediate state $s_{i}$ ( $i<N{-}1$ ) offers a safe-exit action (reward $+1$ , terminal) or a continue action (reward $-5$ , advance). The terminal state $s_{N-1}$ has two actions: $a^{+}$ (reward $+100$ ) and $a^{-}$ (reward $-80$ ). The optimal trajectory is $s_{0}\to s_{1}\to\cdots\to s_{N-1}\to a^{+}$ , with return $100-5(N-1)$ .

PPO ( $1296$ configs/cell)
hidden width	$\{16,32\}$
policy learning rate	$\{0.01,0.05,0.1\}$
critic learning rate	$\{0.05,0.1\}$
epochs per update	$\{10,20,40\}$
clip $\varepsilon$	$\{0.1,0.2,0.3\}$
GAE- $\lambda$	$\{0.95,1.0\}$

Appendix

Table 6 : Hyperparameter grids for the Risky Chain study (batch fixed at

128

200

iterations,

\gamma=1

). The entropy grid is shared across methods.

Explore similar work

Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
Jun 23, 2026Ankur Naskar, Swetha Ganesh, Vaneet AggarwalMulti-Objective Reinforcement Learning Soft Actor-Critic
Indian Institute of Science, Bengaluru, India · Purdue University, USA
Mathematical methods of reinforcement learning
Jul 8, 2026Denis Belomestny, Alexander Gasnikov, Egor Gladin +5Markov Decision Processes Stochastic Approximation
Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1
Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions
Jul 6, 2026Kyohei Suzuki, Konstantinos SlavakisEntropy Regularized Reinforcement Learning Lipschitz Continuity
Department of Information and Communications Engineering, Institute of Science Tokyo, Yokohama, 226-8501, Japan

Jun 23, 2026, cs.LGJ/K move · Enter open · S save

Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL

Ankur Naskar, Swetha Ganesh, Vaneet Aggarwal

Indian Institute of Science, Bengaluru, India · Purdue University, USA

Multi-Objective Reinforcement Learning Soft Actor-Critic

Open paper AskPDF arXiv

Many reinforcement learning (RL) problems in the infinite-horizon average-reward setting require optimizing multiple conflicting objectives while satisfying multiple safety constraints. A common approach is concave scalarization, where the agent maximizes a utility

f(J^π_{r_1}, \ldots, J^π_{r_M})

subject to a scalarized constraint

g(J^π_{c_1}, \ldots, J^π_{c_N}) \ge 0

, where

J^π_{r_m}

and

J^π_{c_n}

denote the average-reward and cost under policy

π

. However, the nonlinearity of

f

and

g

introduces bias in policy-gradient and actor-critic methods, since gradients must be evaluated using noisy estimates of

J^π,

and

\mathbb{E}[\partial f(J^π)] \neq \partial f(\mathbb{E}[J^π]),

and this bias propagates through both primal and dual updates. We propose an MLMC-based primal-dual Natural Actor-Critic algorithm for average-reward MDPs that controls bias in scalarized objectives, constraint evaluation, and actor-critic estimation without requiring mixing-time knowledge. We show that the algorithm achieves optimal global convergence and constraint-violation rates of

\tilde{O}(1/\sqrt{T})

. To our knowledge, this is the first result establishing optimal convergence for concave scalarized multi-objective RL in the average-reward setting, both with and without constraints, and the first to do so without mixing-time information even in the absence of scalarization.

Abstract

Explore similar work

Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL

Mathematical methods of reinforcement learning

Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions