Completion vs Optimality: Policy Gradient in Long-Horizon Cumulative-Damage Problems

Wolfgang Maass; Sabine Janzen

cs.AIMay 26, 2026

Completion vs Optimality: Policy Gradient in Long-Horizon Cumulative-Damage Problems

Authors: Wolfgang Maass, Sabine Janzen

Organizations: Saarland University & German Research Center for Artificial Intelligence (DFKI) · German Research Center for Artificial Intelligence (DFKI)

Abstract

Long-horizon decision problems with cumulative damage couple locally attractive actions to globally adverse outcomes. We identify two orthogonal failure modes for policy-gradient methods on this class and propose a decomposition that separates them: \emph{completion} (reaching the terminal horizon rather than exiting via an implicit terminal constraint) and \emph{optimality} (matching the dynamic-programming reference given completion). Under PPO with a linear soft penalty, granting horizon access alone reduces the completion rate: the penalty's equilibrium drives the dominant-activity share to zero, while action-space restriction combined with horizon access achieves completion but leaves an optimality gap ( $ΔM_{\text{final}} = 0.271$ ) that we trace to first-phase greedy commitment at the damage origin. We derive four testable predictions and evaluate them in two separately calibrated environments that share the same abstract structure but differ in domain, horizon, activity set, and calibration data: a 49-step bricklayer career and a 20-season NBA power-forward career. All four predictions replicate qualitatively. The horizon-invariance prediction is met at three of four tested horizons, with the exception at $H = 15$ consistent with the $H^*$ boundary ( $H^* \in [6, 14]$ under the NBA parameters).

Explore similar work

Jul 25, 2026cs.LG

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size

η_t=η

, we prove that NPG converges sublinearly with a rate of

\mathcal{O}(H^{2}/t)

after

t

iterations, where

H

is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of

\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)

for a problem-dependent constant

\vartheta_ρ> 1

, and the horizon-only robust schedule of the form

η_t=η_0(H/(H-1))^t

where

η_0>0

and

H \geq 2

, attains this same geometric rate.

Asha Barua, Sajad Khodadadian

Policy Gradient Finite Planning Horizon Markov Decision Processes Finite Time Analysis Gradient

Ask PDF

May 7, 2026cs.CL

Milestone-Guided Policy Learning for Long-Horizon Language Agents

While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO's 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is available at https://github.com/ZJU-REAL/BEACON.

Zixuan Wang, Yuchen Yan, Hongxing Li +7

Long-Horizon Agents Reinforcement-Learning Policies Fine-Grained Credit Assignment Vision-Language-Action Policies

Ask PDF

May 12, 2026cs.LG

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs). While existing theoretical guarantees typically hold for the mixture policy, deploying such a policy is computationally and memory intensive. This leads to a practical mismatch where a single (last-iterate) policy must be deployed. Recent theoretical works have thus focused on proving last-iterate convergence, but are largely limited to the tabular setting or to algorithmic variants that are rarely used in practice. To address this, we use the classic inexact augmented Lagrangian (

\texttt{AL}

) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs. We first focus on the tabular setting and propose to solve the

\texttt{AL}

sub-problem with projected Q-ascent (

\texttt{PQA}

). Combining the theoretical guarantees of

\texttt{PQA}

and the standard

\texttt{AL}

analysis enables us to establish global last-iterate convergence. We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of

\texttt{PQA}

can achieve last-iterate convergence with comparable guarantees as prior work. Finally, we demonstrate that our framework scales to complex non-linear policies, and evaluate it on continuous control tasks.

Michael Lu, Max Qiushi Lin, Mo Chen +1

Markov Decision Processes Finite Planning Horizon Policy Optimization Constrained Optimization Optimization Convergence Analysis Lagrangian Methods

Ask PDF