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

Jun 23, 2026cs.LG

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

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.

Ankur Naskar, Swetha Ganesh, Vaneet Aggarwal

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

Multi-Objective Reinforcement Learning Soft Actor-Critic

Ask PDF

Jul 8, 2026math.OC

Mathematical methods of reinforcement learning

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Denis Belomestny, Alexander Gasnikov, Egor Gladin +5

Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1

Markov Decision Processes Stochastic Approximation Mathematics Prompt Optimization

Ask PDF

Jul 6, 2026cs.LG

Non-Convex Sparse Reinforcement Learning via Non-Monotone Inclusions

This work delivers two key contributions: one to efficient feature selection in reinforcement learning (RL), the other to the theory of non-monotone inclusions. On the RL side, the estimation bias inherent in conventional regularization schemes is addressed by augmenting classical least-squares temporal-difference (LSTD) policy evaluation with the sparsity-inducing, non-convex projected minimax concave (PMC) penalty. Because the PMC penalty is weakly convex, the resulting fixed-point problem is no longer monotone; instead, it falls under a broader class of non-monotone inclusions involving the sum of a monotone Lipschitz operator and a hypomonotone operator. On the theory side, novel convergence conditions are developed for the forward-reflected-backward splitting (FRBS) method applied to this broader class of non-monotone inclusion problems. Under mild conditions, Lyapunov stability and the existence of a limit point of the sequence of FRBS iterates are established; alternatively, under the weak Minty variational inequality assumption, exact convergence is guaranteed. Numerical tests on benchmark datasets show that the proposed FRBS iterates, applied to the non-convexly regularized LSTD problem, substantially outperform state-of-the-art feature-selection methods, especially when many noisy features are present.

Kyohei Suzuki, Konstantinos Slavakis

Department of Information and Communications Engineering, Institute of Science Tokyo, Yokohama, 226-8501, Japan

Entropy Regularized Reinforcement Learning Lipschitz Continuity Monotonicity Temporal Difference

Ask PDF