Convex concave reinforcement learning improves credit assignment and training speed
Convex-Concave Reinforcement Learning
Machine LearningArtificial Intelligence
Summary
Reinforcement learning helps computers learn how to make good decisions, but the math behind it can be very hard to solve directly. The authors show that the problem can be rewritten in a way that highlights hidden structure, making it easier to solve by breaking it into simpler convex parts. Their approach connects and extends several existing algorithms and works well on tasks where decisions affect future rewards far down the line. Tests show it learns faster and better in both simple control tasks and a complex healthcare example compared to popular methods.
What this means in practice
- •For healthcare data teams: Train treatment policies faster and more reliably in stochastic healthcare scenarios with longer-horizon effects.
- •For control system engineers: Improve learning on control problems where rewards depend on decisions made far in the past.
Authors
Shripad V. Deshmukh, Yaswanth Chittepu, Dhawal Gupta, Philip Thomas, Scott Niekum
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.