🤖 AI

Learning CLI Agents with Structured Action Credit under Selective Observation

This paper addresses the challenges of selective observation and sparse reward credit assignment in learning CLI agents by introducing the $\sigma$ -Reveal inference-time mechanism, the Action Advantage Assignment ( $\mathrm{A}^3$ ) reinforcement learning method, and the ShellOps dataset suite for verifiable evaluation.

Original authors: Haoyang Su, Ying Wen

Published 2026-05-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Haoyang Su, Ying Wen

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 hiring a very smart but slightly blind assistant to manage a massive, chaotic library. This assistant can read books, move shelves, and write new notes, but they can only see a tiny corner of the library at any given time. Furthermore, you only tell them if they solved the entire puzzle at the very end, not if they picked up the right book in step one or wrote the right note in step two.

This is the challenge the paper tackles: teaching CLI Agents (computer programs that talk to a computer's command line) to work in complex file systems where they can't see everything and only get a "good job" or "fail" signal at the very end.

The authors propose a new way to train these agents using two main tricks: σ-Reveal and A3.

The Two Big Problems

The "Blindfold" Problem (Selective Observation):
The library (the computer's file system) has thousands of files. The agent can't read them all at once because it has a limited memory (token budget). If you show it the whole library, it gets overwhelmed. If you show it nothing, it's guessing.
- The Paper's Solution (σ-Reveal): Think of this as a smart librarian who looks at the agent's specific question and pulls out only the relevant books and folders to show the agent before they start working. Instead of dumping the whole library on the desk, the librarian says, "Here are the 5 files you actually need to solve this. Ignore the rest." This helps the agent focus on the right evidence without getting lost.
The "Black Box" Reward Problem (Credit Assignment):
The agent takes many steps (turns) to solve a task. At the end, you say, "Success!" or "Fail." But which specific step made the difference? Did the agent find the right file in step 2? Did it type the wrong command in step 4?
- The Paper's Solution (A3): This is a new way to give credit to the agent's actions. Instead of just saying "Good job overall," A3 breaks the score down into three layers:
  - The Episode Score: Did this whole attempt work better than other attempts at the same task?
  - The Turn Score: Did this specific command look like the commands that worked in other successful attempts? (The paper uses a special "fingerprint" called an AST to compare the structure of commands, like comparing the skeleton of a sentence rather than just the words).
  - The Tree Score: Did this specific path of actions lead to a better outcome than similar paths taken by other agents?
- Analogy: Imagine a coach watching a soccer team. Instead of just saying "We won," the coach says, "Great pass in the 10th minute (Turn Score), that move was exactly like the one that scored last week (Structure Score), and choosing to attack the left side was the right strategy compared to the right side (Tree Score)." This helps the agent learn exactly what to repeat.

The New Playground: ShellOps

To test this, the authors built a new training ground called ShellOps.

Think of this as a gym for computer agents.
It contains 1,600+ tasks ranging from simple "find this file" to complex "edit these 20 files and give me a summary."
It's designed to be verifiable: The computer can automatically check if the agent actually did the right thing (e.g., did the file actually get edited correctly?), rather than just guessing if the answer sounds good.

What Happened When They Tried It?

The authors tested their new method (A3 + σ-Reveal) against other top-tier AI agents using a 14-billion-parameter model (a mid-sized but powerful brain).

The Results: Their method significantly outperformed the others.
- On the hardest tasks (the "Hybrid" ones that require both finding info and editing files), their agent got about 24.6% correct, while the next best method only got 11.3%.
- It was also cheaper and faster to train. Some other methods require a second "judge" AI to grade every step, which is slow and expensive. Their method does the grading mathematically using the structure of the code itself, keeping costs low.

The Bottom Line

The paper claims that by giving agents a focused view of the files they need (σ-Reveal) and a detailed report card on exactly which actions were good (A3), we can teach them to be much better at navigating and fixing computer file systems.

They didn't claim this works for medical diagnosis, self-driving cars, or creative writing. They specifically focused on command-line tasks: finding logs, editing code, aggregating data from spreadsheets, and fixing database entries. In that specific world, their new "smart librarian" and "detailed coach" approach made the agents significantly smarter and more reliable.

Technical Summary: Learning CLI Agents with Structured Action Credit under Selective Observation

Problem Statement

Command Line Interface (CLI) agents represent a practical paradigm for agent-computer interaction, operating directly within filesystem environments via shell commands rather than predefined tool APIs. However, training these agents faces two coupled bottlenecks:

Selective Observation: Agents must identify task-relevant evidence within large, high-dimensional codebases and filesystems from partial observations. The initial view often covers only a limited projection of the environment, making it difficult to select the correct files or directories for action.
Sparse Action Credit: In multi-turn interactions, terminal rewards are often sparse and delayed, appearing only at the episode's end. Assigning credit to specific actions that shape a long trajectory is challenging, particularly when the state space is large and nearly every observation is unique, weakening assumptions made by existing reinforcement learning (RL) methods that rely on repeated states for normalization.

Current approaches, such as trajectory-level supervised fine-tuning, often lead to memorization of interface patterns rather than genuine task understanding. Conversely, existing RL methods (e.g., Group Relative Policy Optimization variants) struggle with credit assignment in CLI settings due to the lack of repeated states and the complexity of mapping sparse terminal rewards to specific shell command structures.

Methodology

The paper proposes a unified framework addressing both observation and credit assignment through two primary mechanisms: $\sigma$ -Reveal and Action Advantage Assignment (A3).

1. $\sigma$ -Reveal: Selective Observation

To address the partial observation bottleneck, the authors introduce $\sigma$ -Reveal, an inference-time mechanism that constructs a token-budgeted initial workspace view.

Mechanism: Before the first action, $\sigma$ -Reveal selects a subtree-closed set of files from the initial file tree ( $FS_0$ ) that maximizes a relevance score $\hat{\mu}(x | o_0)$ under a token budget $B$ .
Relevance Scoring: The score combines three signals:
1. Name Matching: Whether the file name matches tokens in the task instruction.
2. Depth Prior: A geometric decay based on the file's depth in the directory tree.
3. Extension Prior: The likelihood of the file extension being relevant to the inferred task type.
Outcome: This ensures the agent receives a contextually rich but token-efficient view of the workspace, preserving directory context for selected files.

2. Action Advantage Assignment (A3)

To address sparse credit assignment, A3 is a native agentic RL method that constructs per-turn advantages by fusing three complementary signals without requiring auxiliary value models or state anchoring.

AST-Based Action Similarity: The method quantifies action intent by comparing Abstract Syntax Tree (AST) signatures of shell commands. Using Tree-sitter for Bash, actions are converted into structural signatures (verbs, literals, control structures) independent of specific file paths or literal values. The distance between actions is calculated via normalized Levenshtein distance on these signatures.
Three-Channel Advantage Fusion:
1. Episode Backbone ( $A^{ep}$ ): Contrasts a rollout's return against the median return of sibling rollouts for the same prompt, normalized by Median Absolute Deviation (MAD). This provides a global signal of task success.
2. Turn-Level Action Sub-Chain Residual ( $A^{intent}$ ): Clusters trajectories at a specific turn based on the structural similarity of their recent action sub-chains (using the AST distance). It computes a leave-one-out (LOO) mean of returns for structurally similar actions and assigns credit based on the deviation from this mean. This isolates the value of specific command structures.
3. Tree Advantage ( $A^{tree}$ ): Abstracts interaction histories into "buckets" based on past action signatures. It calculates the value difference between taking a specific abstract action branch versus the average branch from the same abstract state. This signal is gated by group size to prevent noise in small clusters.
Fusion: These three signals are normalized, weighted, and passed through a bounded activation function (tanh) to produce the final advantage $A_i$ used for policy gradient updates.

3. ShellOps Dataset

To evaluate this setting, the authors constructed ShellOps and ShellOps-Pro, verifiable dataset suites covering CLI tasks in repository environments.

Scope: Tasks include Lookup (extracting values), Aggregate (scalar answers from scattered evidence), Edit (verifiable file rewrites), and Mixed (combining stdout and file edits).
Scale: ShellOps contains 1,624 tasks; ShellOps-Pro adds 150 harder, out-of-distribution tasks with larger workspaces (median 25 files per task vs. 3 in the standard set) and diverse file extensions.

Key Results

Experiments were conducted using the Qwen3-14B policy model across multiple benchmarks (AgentBench, DataBench, EHRCon, TableBench, and ShellOps).

Performance: A3 with $\sigma$ -Reveal achieved the strongest results among Qwen3-14B methods. On the ShellOps hybrid tasks (requiring both file edits and stdout), A3 achieved a 24.6% exact match score, significantly outperforming the strongest baseline (11.3%).
Sampling Efficiency: In terms of Pass@k, A3 with $\sigma$ -Reveal reached 55.7% on ShellOps (Pass@5), compared to 28.6% for the best non-A3 baseline.
Long-Horizon Transfer: On ShellOps-Pro with extended horizons (up to 10 steps), A3 maintained the best performance among Qwen3-14B agents, reaching performance levels comparable to much larger frontier models (e.g., Qwen3-235B) in specific settings, though gaps remained with models like Kimi-K2.6.
Stability: Training diagnostics showed that A3 maintained stable surrogate KL and policy entropy, avoiding the "KL spikes" and entropy collapse observed in baselines like HGPO and RetroAgent.
Efficiency: A3's advantage computation cost is comparable to standard group-relative training, unlike methods relying on LLM judges (e.g., GiGPO, HGPO) which incur significantly higher computational overhead.

Significance and Claims

The paper claims that workspace evidence selection and command structure are effective bases for CLI agent learning.

Structural Credit: By leveraging the native structured attributes of CLI actions (AST signatures) rather than surface text, A3 provides a scalable and computationally efficient method for credit assignment that does not rely on repeated states or external judges.
Observation Management: $\sigma$ -Reveal demonstrates that selective, token-budgeted context injection can effectively mitigate the partial observation problem in large filesystems without requiring exhaustive search.
Practical Paradigm: The work establishes a verifiable loop for CLI agents where rewards are derived from executable outcomes (file states and terminal outputs), moving beyond isolated input-output pairs to true multi-turn interaction optimization.

The authors note limitations, including the reliance on shell structure as a proxy for intent (which may miss semantic differences in paths or file contents) and the current scope being limited to shell-driven filesystem interactions, requiring further validation for GUI or networked settings.