Agentic RL & Long-Horizon Coding

For NAO + anyone trying to understand the "Alice can code" mission from the ground up. [[rlvr]] taught a model to reason in a single long chain-of-thought: ask once, think for 30K tokens, check the final answer, reward 1 or 0. Agentic RL is the next layer up. Now the model doesn't answer once — it acts: read a file, run a test, see the traceback, edit code, run the test again, for 30, 50, 100+ turns. Only at the very end do we know if the bug is fixed. The brutal new problem is: which of those 100 actions deserve the credit (or the blame)? That is the long-horizon credit assignment problem, and solving it is what separates a model that can chat about code from one that can actually fix a GitHub issue autonomously. This article goes intuition-first, then gives the real mechanics (the POMDP setup, the GRPO advantage formula, turn-level reformulations, process reward models, the exact DeepSWE recipe), then is honest about how much of this is still frontier and unsolved.

What it is (intuition)

Imagine you're learning to fix bugs by trial and error, with a coach who only ever tells you one thing at the end: "the tests passed" or "the tests failed." Nothing in between. You made 80 moves — opened 12 files, ran the test suite 9 times, wrote 3 patches, reverted 2 — and all you get back is a single thumbs-up or thumbs-down. To get better, you have to figure out on your own which of those 80 moves were the smart ones and which were wasted motion. That is exactly the situation a coding agent is in, and agentic reinforcement learning is the machinery for turning that single end-of-episode signal into a learning gradient that flows back to the individual actions.

Three words define the regime:

• Agentic — the model is a decision-maker in a loop (see [[agentic-loops]]), not a one-shot text generator. It interleaves thinking (free-text reasoning) with acting (tool calls: bash, edit_file, run_tests, search). The environment talks back: a test fails, a file doesn't exist, a command times out. The agent must react to what it observes.
• Long-horizon — a single task ("fix this issue") unfolds over 10–100+ turns and 100K–1M+ tokens of total context. The reward is sparse (one signal at the end) and delayed (you don't learn anything until the episode is over).
• RL — we optimize the policy (the model's weights) so that, over many attempts, it takes trajectories that end in success more often. Not by imitating human demos, but by trying, observing the outcome, and reinforcing what worked.

The flagship benchmark is SWE-bench Verified: real GitHub issues from real Python repositories, where success = "your patch makes the hidden test suite go green." This is the concrete, measurable target of OpenAlice's "Alice can code" mission. (More on evaluating these agents in [[agent-evaluation]] and [[llm-evaluation]].)

The one-line distinction from plain reasoning RL: in [[rlvr]] the entire output is one chain of thought and the only stochasticity is the model's own sampling. In agentic RL the environment is part of the loop — tools return data the model couldn't have predicted, the state is only partially observable, and the action sequence is genuinely interactive. That turns a relatively clean optimization problem into a messy, high-variance one.

Why it matters

1. It's the difference between an assistant and an engineer. A model that scores well on "single-turn code completion" can suggest a snippet. A model trained with agentic RL can be dropped into a repo and asked to fix a bug end-to-end — clone, reproduce, locate, patch, verify. That autonomy is the capability OpenAlice is chasing (the "repo → PR" base-AGI capability NAO flagged), and SWE-bench is how we measure progress toward it.

1. It produced a real, reproducible jump. This is not hype. Concrete, replicated results: - DeepSWE (Together AI + Agentica, 2025): pure RL on Qwen3-32B, no SFT bootstrap, reached 42.2% Pass@1 and 59% on SWE-bench Verified with test-time scaling — SOTA for open-weight agents at the time, with everything open-sourced (data, code, logs). - A separate pipeline took a 72B open model from 11% → 39% Pass@1 on SWE-bench Verified purely by training on long-context multi-turn trajectories (arXiv:2508.03501). These are large, RL-attributable gains on a hard, real-world benchmark.

1. It forces us to solve credit assignment for real. Reasoning RL could get away with giving every token the same reward (the whole chain is one "action"). Agentic RL cannot — a 100-turn trajectory with one brilliant turn and 99 filler turns will never learn efficiently if all 100 turns get identical credit. So agentic RL is driving genuinely new algorithmic ideas (hindsight counterfactuals, asymmetric critics, turn-level MDPs) that have no precedent in the reasoning-RL literature. It's where the frontier actually is in 2026.

How it works (real mechanics)

1. The formal setup: from degenerate MDP to full POMDP

The 2025 survey (arXiv:2509.02547) makes the cleanest formal distinction. Ordinary RLHF/RLVR fine-tuning — the survey calls it PBRFT (Preference-Based RL Fine-Tuning) — is a degenerate one-step MDP:

PBRFT:   ⟨ S_trad, A_trad, P_trad, R_trad,  T = 1,  γ = 1 ⟩

One prompt in, one response out, episode ends. The reward r(a) lands on the final output and that's it. Objective:

J_trad(θ) = E_{a ~ π_θ} [ r(a) ]        # maximize expected single-turn reward

Agentic RL is a full POMDP (partially observable, because the agent never sees the whole world state — only what its tools return):

Agentic: ⟨ S_agent, A_agent, P_agent, R_agent,  γ,  O ⟩

    state transition:   s_{t+1} ~ P(s_{t+1} | s_t, a_t)     # stochastic — env reacts
    observation:        o_t     = O(s_t)                     # partial — agent sees a slice
    action space:       A_agent = A_text ∪ A_action          # talk OR act

That action-space split is the heart of it: A_text is free-form natural-language tokens (the agent's reasoning), and A_action is abstract, non-linguistic actions — tool calls and environment mutations, usually delimited by special tokens (see [[tool-use-function-calling]]). The objective becomes a discounted sum over a whole trajectory τ:

J_agent(θ) = E_{τ ~ π_θ} [ Σ_t  γ^t · R_agent(s_t, a_t) ],     0 < γ < 1

The reward itself is now multi-level — a sparse task reward plus optional dense sub-rewards:

R_agent(s_t, a_t) = {  r_task     on task completion
                    {  r_sub      for step-level progress      (optional, hard to get right)
                    {  0          otherwise

In practice, for SWE-bench, the honest version is brutally sparse: `r_task = +1` iff the test suite passes, else `0` — and r_sub is usually absent because nobody trusts hand-built process rewards (more on that below). The agent's capabilities the survey says RL can sharpen: planning, tool use, memory ([[agent-memory-systems]]), self-improvement/reflection, reasoning, and perception.

2. The baseline: GRPO and why it's too coarse for long horizons

Most agentic-coding RL today uses GRPO (Group Relative Policy Optimization, from DeepSeekMath 2402.03300 — see [[grpo]]). GRPO is critic-free: instead of training a value network, it samples a group of G trajectories for the same task and normalizes each one's reward against the group:

Â^i_GRPO = ( R(τ_i) − mean_j R(τ_j) ) / std_j R(τ_j)       # group-relative advantage

This is beautiful for reasoning and it's why GRPO ate the world. But look closely at what it does in the agentic case: every token in trajectory `τ_i` receives the *same* advantage `Â^i_GRPO`. A 100-turn trajectory gets one scalar smeared uniformly across all of it. The credit-assignment survey (2604.09459) names this exactly: GRPO is an episode-level mechanism, "unsuitable for long agentic horizons." It tells you the trajectory was good; it cannot tell you which turn was good.

3. The new ideas: making credit flow to turns, not just episodes

The 2026 credit-assignment survey catalogs ~47 methods along two axes — granularity (token / segment / step / turn / multi-agent) and methodology (Monte-Carlo / temporal-difference / model-based / game-theoretic / information-theoretic). Three families are genuinely new to the agentic regime (no reasoning-RL precedent):

(a) Turn-level MDP reformulation. Treat each turn's whole response as one atomic action. Learn a turn-level value function and decompose the episode reward across turns. E.g. AgentPRM applies TD learning at turn granularity:

V(s_t) ≈ E[ R(τ) | s_t ]          # turn-level state value
Â_t    via GAE / TD on V           # then advantages per turn, not per episode

Examples the survey cites: GiGPO (turn-level advantage estimation), SPA-RL (stepwise progress attribution).

(b) Hindsight counterfactual analysis. Ask the literal counterfactual: what if turn `t` hadn't happened? Re-roll or ablate the trajectory without turn t and measure the swing:

c_t = R(τ_actual) − R(τ_{−t})       # credit of turn t = how much it changed the outcome

Methods: HCAPO, C3, and information-theoretic variants like IGPO that attribute credit via mutual information between a turn and the final outcome. Expensive (you need extra rollouts), but it directly answers "which turn mattered."

(c) Privileged asymmetric critics. Train a critic that, only at training time, gets to peek at information the agent never sees at inference — the ground-truth fix, oracle test results, the gold patch. That critic emits dense per-turn value estimates; at rollout it's thrown away. SWEET-RL is the canonical SWE example. "Asymmetric" = the critic knows more than the actor, which is fair game in training and a clean way to manufacture a dense signal from a sparse task.

4. Process Reward Models for long-horizon coding (SWE-TRACE)

A complementary attack: instead of decomposing the final reward, manufacture a dense one. SWE-TRACE (2604.14820) builds a Rubric Process Reward Model. A "Rubric Agent" first writes issue-specific criteria — target-localization, edit constraints, trajectory discipline, budget awareness — each a weighted tuple (u_k, z_k, w_k). A whole trajectory is then scored:

s_prm(τ, R_x) = Σ_{k=1..K}  w_k · q_k(τ, c_k),      q_k ∈ [0,1]

The clever bit is how it's composed with the real execution reward so process scoring never overrides ground truth. With a margin γ ∈ (½, 1):

R(τ_i) = {  (1−γ) · s_prm(τ_i)            if r_exec(τ_i) = 0   →  score ∈ [0, 1−γ]
         {  γ + (1−γ) · s_prm(τ_i)        if r_exec(τ_i) = 1   →  score ∈ [γ, 1]

So every passing trajectory still strictly beats every failing one (no reward hacking the PRM into faking success), but among equally-passing trajectories the cleaner, shorter, more disciplined one wins. This fixes the three pathologies of binary execution rewards: reward indifference (all passes look identical), trajectory inflation (padding with useless steps is free), and reward noise (flaky tests). This is the agentic, long-horizon descendant of the ideas in [[process-outcome-rewards]]. SWE-TRACE also reuses the PRM at inference for heuristic test-time scaling — reweighting candidate actions mid-rollout q_t(a) ∝ π_θ(a) · exp(β · u_t(a)) and only executing the top-B — turning expensive full-trajectory best-of-N into cheap step-level pruning (connects to [[test-time-compute-reasoning]]).

5. A real end-to-end recipe (DeepSWE)

To make it concrete, here is the actual DeepSWE training loop — the clearest open recipe for an RL coding agent. Notice how much of it is engineering discipline, not new math:

• Base: Qwen3-32B. No SFT cold-start — pure RL from the base reasoning model.
• Data: 4,500 real SWE tasks from R2E-Gym (repos overlapping SWE-bench Verified, e.g. sympy, excluded to prevent leakage).
• Agent scaffold: tools = bash, search, file-editor, finish/submit. Up to ~50 steps / long context per episode.
• Reward: sparse outcome only. `+1` if the full test suite passes, `0` if anything fails or it exceeds a 5-minute timeout. That's it — honest [[rlvr]]-style verifiable reward.
• Algorithm — "GRPO++", which is really GRPO with a stack of stabilizers borrowed from DAPO / Dr.GRPO / RLOO: 1. Clip-High (DAPO) — raise the surrogate-loss upper clip to encourage exploration. 2. No KL loss (DAPO) — don't tether to the SFT policy; let it move. 3. No reward-std normalization (Dr.GRPO) — removes GRPO's difficulty bias. 4. Length normalization (Dr.GRPO) — divide loss by max context length, kills length bias. 5. Leave-One-Out advantage (RLOO/LOOP) — lower-variance baseline, no bias. 6. Compact filtering — mask out trajectories that hit max-context / max-steps / timeout so a truncation isn't mistaken for a real failure. (Critical for long horizons.) 7. No entropy bonus — found unstable; dropped.
• Infra: rLLM framework (built on verl), 64× H100, ~6 days.
• Test-time scaling: hybrid verifier (execution-based + execution-free) over K=16 rollouts → 59%; K=8 captures most of it. Pass@1 42.2%, Pass@16 71.0%.

Pseudocode for one RL step, stripped to essentials:

for task in batch:
    # 1. ROLLOUT: G parallel agent trajectories in sandboxed repos
    group = [run_agent(policy, task, max_steps=50) for _ in range(G)]  # each is 10-100+ turns

    # 2. REWARD: run the hidden test suite (the verifier)
    R = [1.0 if tests_pass(traj.patch) else 0.0 for traj in group]      # sparse, delayed

    # 3. COMPACT FILTER: drop truncated/timed-out trajectories from the loss
    group, R = drop_truncated(group, R)

    # 4. ADVANTAGE: group-relative (GRPO), Dr.GRPO = no /std, length-normalized
    A = [r - mean(R) for r in R]            # leave-one-out baseline in practice

    # 5. POLICY GRADIENT: clip-high surrogate, no KL, no entropy, advantage broadcast per-token
    loss = grpo_pp_surrogate(policy, group, A)
    loss.backward(); opt.step()

The thing to internalize: DeepSWE's headline result comes from sparse outcome reward + heavy optimization discipline, not from a fancy dense credit-assignment scheme. The turn-level / hindsight / PRM methods in §3–4 are the frontier trying to do better than this — and as of 2026 they show gains on the margin but haven't dethroned "scale clean GRPO on real tasks."

Key ideas & tradeoffs

The deep tension running through all of it: dense signal vs. honest signal. The denser you make the reward, the faster you learn — and the more you risk teaching the model to satisfy your proxy (looks like good engineering) instead of the goal (tests actually pass). Outcome rewards are honest but starving; process rewards are rich but corruptible. Every method above is a different point on that curve.

Honest caveats & open questions

• Credit assignment is *not solved*. The 2026 survey is explicit: turn-level methods exist but "the problem remains largely unsolved for multi-turn reasoning horizons." The current SOTA recipe (DeepSWE) sidesteps it with brute-force clean GRPO + filtering rather than truly solving per-turn credit. Treat anyone claiming a clean solution with suspicion.
• The [[rlvr]] ceiling question carries over, magnified. There is a live debate (Yue et al. 2504.13837, "the invisible leash" 2507.14843) about whether RLVR teaches new reasoning or just sharpens what the base model already samples — and whether it shrinks the policy's support. In the agentic setting this is worse: if RL only re-weights behaviors already in the base model, an agent can't RL its way to a tool-use strategy it never stumbles into. How much agentic RL adds vs. amplifies is genuinely open.
• Benchmark validity is fragile. SWE-bench numbers are extremely sensitive to the agent scaffold, the test-time-scaling budget, and train/test contamination (DeepSWE had to explicitly exclude SWE-bench-Verified repos from R2E-Gym). A "59%" with K=16 best-of-16 is not comparable to a "42%" Pass@1. Always read the harness and the N. Solving an issue's given tests is also not the same as a correct fix — patches can pass the suite and still be wrong.
• Cost & reproducibility. 64 H100s for 6 days is one 32B model on 4.5K tasks. Long-horizon rollouts (100K–1M tokens each, × G group size × thousands of tasks × many steps) make agentic RL brutally expensive — the rollout, not the gradient step, dominates (hence "rollout-as-a- service" systems like ProRL/Polar). This is a real barrier for a small lab.
• Process Reward Models are double-edged. They're the obvious way to densify the signal, but PRMs are exactly what gets reward-hacked. SWE-TRACE's margin composition is one mitigation; it is not a guarantee. Hand-authored r_sub step rewards are widely distrusted for this reason.
• Stochastic, partially-observable environments break clean theory. GRPO's group-relative baseline assumes comparable rollouts; when two trajectories diverge because the environment behaved differently (a flaky test, a timeout), the comparison is noisy and the gradient lies. Compact filtering patches the worst of this empirically, not theoretically.

Bottom line for a builder: the reliable recipe in 2026 is sparse verifiable reward + GRPO with the DeepSWE stabilizer stack + ruthless trajectory filtering + test-time scaling at eval. The dense-credit-assignment literature (turn-level, hindsight, PRM) is real, active, and worth tracking — but it's frontier, marginal-gain, and not yet a free lunch.

How it connects to OpenAlice

• This *is* the "Alice can code" mission. NAO's directive frames autonomous repo→PR as a base AGI capability of Alice, measured by SWE-bench — not a separate Devin clone. Everything above is the literature for how you actually train that capability rather than prompt-engineer around it. The honest near-term path mirrors DeepSWE: a clean verifiable reward (tests pass / 0), GRPO with the stabilizer stack, and test-time scaling at eval — not an exotic credit scheme.
• The agent already exists; the RL loop is the missing layer. Alice's substrate is an [[agentic-loops]]-style think→act→observe controller with real tools (bash/browse/pty/edit), and OpenAlice runs an internal bench.blal.pro UI-bench platform plus a lab/ranker/inspector rig. The gap between "Alice runs a coding loop" and "Alice learns from coding loops" is exactly the agentic-RL machinery described here: turning thousands of trajectory outcomes into a gradient.
• Reward = the verifier you already trust. OpenAlice's whole quality culture ("Safety First, Science Second", zero-regression gates, tests-with-every-change) is a verifiable-reward signal. The cargo test / suite-passes check that gates every merge is, in RL terms, r_task. That's a feature: the org already has the ungameable signal that agentic coding RL needs.
• Evaluation discipline maps directly. Don't trust a single SWE-bench number — read the scaffold, the test-time budget, and contamination, per [[agent-evaluation]] and [[llm-evaluation]]. This is the same hygiene the lab already enforces ("next build, not just tsc", "cargo is source of truth", re-gate sub-agent work independently).
• Reuse the existing stack. [[grpo]] and [[rlvr]] are the algorithmic foundation; SWE-TRACE-style process rewards relate to [[process-outcome-rewards]]; long episodes pressure [[long-context]] and [[agent-memory-systems]] (verbatim-anchor memory buffers are literally how SWE-TRACE survives 100-turn trajectories); tool definitions live in [[tool-use-function-calling]] and ride the same [[mcp]] / [[a2a-protocols]] plumbing the lab uses; eval-time best-of-N is [[test-time-compute-reasoning]]. Agentic-RL isn't a new pillar for OpenAlice — it's the training loop that wires the pillars it already has into a model that gets better at coding by coding.

Beginner ramp: read [[rlvr]] first (single-turn verifiable reward), then [[agentic-loops]] (the think-act-observe controller), then this article (RL over those loops). For algorithm internals drop into [[grpo]]; for "is the signal honest?" see [[process-outcome-rewards]]; for "did it actually work?" see [[agent-evaluation]].