🤖 AI

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

This paper identifies and decomposes two orthogonal failure modes—completion and optimality—in policy-gradient methods for long-horizon cumulative-damage problems, demonstrating through empirical validation in bricklayer and NBA career simulations that while action-space restrictions enable task completion, they often leave a significant optimality gap caused by early greedy commitments.

Original authors: Wolfgang Maass, Sabine Janzen

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wolfgang Maass, Sabine Janzen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are training a robot to play a very long game of "Career." The goal is to stay in the game as long as possible while collecting as many points as possible. However, there's a catch: the moves that give you the most points right now also slowly break your robot's legs. If the legs break too much, the game ends immediately.

This paper, titled "Completion vs. Optimality," investigates why smart AI learning methods (specifically something called "Policy Gradient") often fail at this type of game. The authors, Wolfgang Maass and Sabine Janzen, discovered that these AIs fail in two completely different ways, and they need to be fixed with different tools.

Here is the breakdown using simple analogies:

1. The Two Ways to Fail

The authors realized that when an AI does poorly, it's usually failing at one of two distinct tasks, but standard scoring systems mix them up:

Failure A: "Quitting Early" (Completion Failure)
- The Analogy: Imagine a marathon runner who starts sprinting at full speed because they want to get to the finish line fast. They burn out their muscles in the first mile and have to quit the race entirely.
- The AI Problem: The AI sees the "greedy" move (the one with the most immediate points) and takes it. This move secretly damages the robot's "health." Because the damage signal is hidden until it's too late, the AI keeps taking the damaging move until the robot breaks and the episode ends early. It never even gets to the later, high-reward stages of the career.
Failure B: "Playing Too Hard" (Optimality Failure)
- The Analogy: Imagine a runner who does finish the marathon, but they sprinted so hard at the start that they are limping and exhausted by the end. They finished, but they could have run a much better race if they had paced themselves.
- The AI Problem: Even if the AI manages to survive the whole career, it often gets stuck in a "trap." It learns to go 100% effort at the very beginning because that looks like the best move for the first step. Once it commits to this "all-out" start, it can't recover. It ends up with a lower total score than it could have achieved if it had started gently.

2. The Two Experiments

To prove this, the authors built two different "career simulators" that act like video games:

The Bricklayer: A 49-year career of a construction worker doing heavy lifting.
The NBA Player: A 20-season career of a basketball power forward.

Both games have the same hidden rule: Do too much work too soon, and you get injured (the game ends).

3. What They Found

The authors tested three different approaches on these games:

The "Real" AI (PPO): This is the standard AI trying to learn by trial and error.
- Result: It failed Completion. In the bricklayer game, it quit at age 27.8 (instead of 65). In the NBA game, it quit at age 22.6 (instead of 38). It sprinted too hard and broke down.
The "Unrestricted" AI with a Soft Penalty: The researchers tried to help the AI by giving it a "soft warning" (a small penalty) if it worked too hard, and letting it see the whole career length.
- Result: This actually made things worse. The AI quit even earlier (age 24.7). The penalty confused the AI, causing it to stop working entirely or quit prematurely.
The "Restricted" AI (Fixed-Share): The researchers forced the AI to follow a specific rule: "You must only do 15% of the dangerous heavy lifting." The AI was only allowed to decide how hard to work, not what to work on.
- Result: This AI achieved Completion. It finished the full 49 years or 20 seasons without quitting.
- The Catch: Even though it finished, it still failed Optimality. It finished with a score of 0.52 (on a scale where the perfect score is 0.79). It survived, but it didn't play the best possible game because it got stuck in that "sprint at the start" trap.

4. The "First Step" Trap

The most interesting discovery is why the AI plays too hard at the start.
The authors found that the AI makes a "greedy commitment" in the very first second of training.

The Metaphor: Imagine a student taking a test. The first question is easy and gives 100 points. The student thinks, "I'll just answer this one super fast!" They do, but in doing so, they use up all their mental energy for the rest of the test.
The Science: The AI calculates that the "all-out" move gives a huge reward right now. Because the damage doesn't show up until later, the AI's first instinct is to go for the big reward. Once it locks into that "all-out" strategy, it's too late to change. Even if you train it for a million years, it keeps making that same first mistake.

5. The Conclusion

The paper concludes that you cannot fix these problems with just one tool.

To stop the AI from quitting early, you have to restrict its choices (force it to not do the dangerous move 100% of the time).
To stop the AI from playing poorly (even when it survives), you need to fix how it learns from the very first step, because it gets "stuck" in a bad habit immediately.

In short: The AI is like a worker who either quits the job too soon because they work too hard, or stays in the job but burns out their career because they started too hard. The paper shows that simply telling the AI "don't work too hard" isn't enough; you have to change the rules of the game and how the AI thinks about the very first move.

Technical Summary: Completion vs. Optimality in Long-Horizon Cumulative-Damage Problems

1. Problem Definition

This paper addresses a specific class of long-horizon sequential decision problems characterized by cumulative damage. In these environments, actions that maximize immediate reward (locally attractive) simultaneously increase a latent cumulative damage state ( $D_t$ ). The episode terminates implicitly when $D_t$ crosses a threshold or when a "role-viability" constraint is violated (e.g., the share of high-damage activities falls below a critical level).

The core challenge is that the damage signal is often latent or uninformative at low damage levels. Agents using standard policy-gradient methods (like PPO) often fail to learn prudent policies because:

They cannot observe the damage until it is too late (the "implicit terminal boundary").
Greedy credit assignment favors immediate reward over long-term preservation, leading to early termination.

The authors identify that standard return-based evaluation conflates two distinct failure modes:

Completion Failure: The agent exits the episode early (before the full horizon $H$ ) due to violating the implicit constraint.
Optimality Failure: The agent completes the full horizon but achieves a suboptimal final state (e.g., lower preservation of health/capacity) because it committed to a greedy strategy early on.

2. Methodology and Decomposition

The paper proposes a decomposition to evaluate agents on two orthogonal axes:

Completion: Does the policy reach the terminal horizon $H$ ?
Optimality: Given completion, does the policy match the value of a backward-induction reference ( $\pi^*$ )?

Experimental Setup

The authors evaluate this decomposition in two distinct, calibrated environments sharing the same abstract structure but differing in domain and parameters:

Bricklayer Career: A 49-step (49-year) simulation of a construction worker managing 7 activities, calibrated to human knee biomechanics and epidemiological data.
NBA Power-Forward Career: A 20-season simulation of a basketball player managing 6 activities, calibrated to sports-medicine literature.

Both environments feature:

Latent Damage: The agent observes only a proxy signal $S_t = g(D_t)$ , which is uninformative at low damage levels.
Dominant-Activity Structure: One activity maximizes both reward and damage.
Self-Amplifying Degradation: A secondary channel where preservation ( $M_t$ ) degrades at an accelerating rate once it falls below a threshold ( $M_{amp} = 0.6$ ).

Algorithms Compared

PPO-real: Standard Proximal Policy Optimization trained on real rollouts with the implicit termination constraint active.
Unrestricted Dyna: A model-based variant (Dyna) with access to the full horizon (via a no_exit flag during training) and a linear soft penalty for violating the role-viability constraint.
Fixed-share Dyna: A variant where the activity share is clamped to the Dynamic Programming (DP) optimal allocation, and only the effort level is learned.
DP-optimal: A backward-induction reference using full state knowledge ( $D, M, t$ ) to compute the theoretical upper bound.

3. Key Findings and Results

The Completion Gap

PPO-real Failure: PPO trained on real rollouts fails to complete the horizon in both environments (0% completion rate). The mean exit age is significantly lower than the horizon (27.8 years in Bricklayer; 22.6 years in NBA).
Harm of Horizon Access Alone: Granting horizon access to an unrestricted agent (Unrestricted Dyna) with a linear soft penalty worsens performance. The penalty drives the dominant-activity share to zero, violating the constraint even more aggressively than PPO-real.
Action-Space Restriction: Restricting the action space to the DP-optimal share allocation (Fixed-share Dyna) unlocks completion. This agent achieves 100% completion in both environments, proving that the failure to complete is structural (related to the share constraint) rather than purely a credit-assignment issue.

The Optimality Gap

Even when completion is achieved (Fixed-share Dyna), a significant optimality gap ( $\Delta M_{final}$ ) remains:

Bricklayer: $\Delta M_{final} = 0.271$ (Fixed-share Dyna $M_{final} \approx 0.52$ vs. DP-optimal $0.79$).
NBA: $\Delta M_{final} = 0.150$ (Fixed-share Dyna $M_{final} \approx 0.61$ vs. DP-optimal $0.76$).

Mechanism of Optimality Failure: First-Phase Basin Entry

The paper identifies the cause of the optimality gap as a first-phase greedy commitment:

Reactive Decline Attractor: In 8/10 seeds (Bricklayer) and 4/10 seeds (NBA), the agent commits to maximum effort on the dominant activity at $t=0$ .
Irreversibility: This initial high effort drives the preservation variable $M$ below the self-amplification threshold ( $M_{amp}$ ) irreversibly.
Step-0 Basin Entry: The expected first policy-gradient update points toward the greedy action because the immediate reward gap outweighs the discounted future damage cost (formalized in Proposition 1). This commitment happens within the first 1% of training, before long-horizon signals accumulate.
Horizon Invariance: The dominance of this "reactive decline" attractor is invariant to training horizon length ( $H$ ) up to a critical boundary $H^*$ , confirming that the failure is driven by initial conditions, not long-horizon credit assignment.

4. Contributions

Formalization: A formal definition of the "horizon-mismatched cumulative-damage" problem class and a decomposition of failure into completion and optimality axes.
Empirical Decomposition: A three-way comparison (PPO-real, Fixed-share Dyna, DP-optimal) quantifying both gaps in two distinct domains.
Causal Analysis: Evidence that horizon access alone is harmful under linear soft penalties and that action-space restriction is the necessary intervention for completion.
Mechanism Identification: Identification of "first-phase greedy commitment" as the driver of optimality failure, supported by a theoretical proposition on the direction of the expected first gradient update.

5. Significance and Claims

The paper claims that standard policy-gradient methods fail in cumulative-damage problems not just due to long-horizon credit assignment, but due to a structural inability to satisfy implicit terminal constraints (completion) and a tendency to commit to greedy strategies at the very start of the episode (optimality).

Diagnostic Value: The decomposition reveals that interventions targeting one axis (e.g., action-space restriction for completion) do not solve the other (optimality).
Generalizability: The findings replicate across two domains (occupational health and sports medicine), suggesting the failure modes are inherent to the problem structure (latent damage, dominant-activity alignment, self-amplifying degradation) rather than specific to a simulator.
Theoretical Insight: The work connects the empirical "reactive decline" pattern to a formal condition where the immediate reward gap dominates the continuation value at $t=0$ , explaining why agents converge to suboptimal fixed points regardless of training horizon length.

The authors explicitly state that their theoretical proposition (Proposition 1) applies to a minimal binary-action MDP and serves as a structural analogy for the multi-activity testbeds, rather than a direct derivation for them. They also note limitations regarding the use of a single simulation engine and the specific penalty functions used (linear soft penalties).