papers/hanzo-agent-grpo/sections/07-theoretical-analysis.tex

\section{Theoretical Analysis}

\label{sec:theory}

We now establish formal guarantees for Agent-GRPO under a set of mild
assumptions.

\begin{assumption}[Bounded Rewards]
\label{asm:bounded}
For all trajectories $\tau$, the composite reward satisfies $R(\tau) \in [0, 1]$.
\end{assumption}

\begin{assumption}[Positive Information Content]
\label{asm:info}
Each task group with $\sigma_G > 0$ yields at least one \textsc{add} operation
in expectation: $\mathbb{E}[|\Omega^{(g)}_{\textsc{add}}|] \geq 1$.
\end{assumption}

\begin{assumption}[Experience Relevance]
\label{asm:relevance}
An experience $e$ is \emph{beneficial} for task $x$ if $\mathbb{E}[R(\tau) \mid e \text{ retrieved}] > \mathbb{E}[R(\tau) \mid e \text{ not retrieved}]$.
Let $B_k = |\{e \in \mathcal{E}_k : e \text{ is beneficial for a uniformly random } x \sim \mathcal{X}\}|$
denote the number of beneficial experiences at epoch $k$.
\end{assumption}

\begin{assumption}[Extraction Accuracy]
\label{asm:accuracy}
The extraction pipeline (Stages 1--3) is correct with probability $p_c > 1/2$:
each \textsc{add} operation produces a beneficial experience with probability
at least $p_c$, and each \textsc{delete}/\textsc{modify}/\textsc{merge} operation
does not decrease $B_k$ in expectation.
\end{assumption}

\begin{theorem}[Monotone Library Improvement]
\label{thm:monotone}
Under Assumptions~\ref{asm:bounded}--\ref{asm:accuracy}, if each session
processes at least one task group with $\sigma_G > 0$, then the expected number
of beneficial experiences is non-decreasing across epochs:
\begin{equation}
    \mathbb{E}[B_{k+1}] \geq \mathbb{E}[B_k], \quad \forall k \geq 0.
    \label{eq:monotone}
\end{equation}
Furthermore, if $p_c > 1/2$, then $\mathbb{E}[B_{k+1}] > \mathbb{E}[B_k]$
when at least one group in epoch $k$ has $\sigma_G > 0$.
\end{theorem}

\begin{proof}
Let $A_k$ denote the set of \textsc{add} operations produced in epoch $k$
and $D_k$ the set of \textsc{delete}/\textsc{modify}/\textsc{merge} operations.
By Assumption~\ref{asm:info}, $|A_k| \geq 1$ in expectation when $\sigma_G > 0$.

Each \textsc{add} operation produces a beneficial experience independently with
probability $p_c > 1/2$ (Assumption~\ref{asm:accuracy}). Thus the expected
increase from \textsc{add} operations is:
\begin{equation}
    \mathbb{E}[\Delta B_k^+] = |A_k| \cdot p_c > 0.
\end{equation}

By Assumption~\ref{asm:accuracy}, each destructive operation has non-negative
expected effect: $\mathbb{E}[\Delta B_k^-] \geq 0$.

Therefore:
\begin{equation}
    \mathbb{E}[B_{k+1}] = \mathbb{E}[B_k + \Delta B_k^+ + \Delta B_k^-]
    \geq \mathbb{E}[B_k] + |A_k| \cdot p_c > \mathbb{E}[B_k],
\end{equation}
establishing strict monotone improvement. When no group has $\sigma_G > 0$,
$|A_k| = 0$ and neither \textsc{add} nor destructive operations fire, so
$B_{k+1} = B_k$ and the inequality holds with equality.
\end{proof}

\begin{remark}
Theorem~\ref{thm:monotone} does not guarantee that $B_k \to \infty$;
memory compression (Section~\ref{sec:compression}) bounds $|\mathcal{E}_k|$,
and compression may occasionally remove beneficial experiences. A refined
result incorporating compression is stated as Corollary~\ref{cor:compressed}.
\end{remark}

\begin{corollary}[Monotone Improvement Under Compression]
\label{cor:compressed}
If compression is performed with the hybrid strategy (Strategy 4) with
parameter $\beta > \delta$ (confidence weighted more than diversity), then
for any $\varepsilon > 0$ there exists $N_{\max}(\varepsilon)$ such that for
$N_{\max} \geq N_{\max}(\varepsilon)$, Theorem~\ref{thm:monotone} holds up
to an additive term $-\varepsilon$ on the right-hand side:
$\mathbb{E}[B_{k+1}] \geq \mathbb{E}[B_k] - \varepsilon$.
\end{corollary}

\begin{proof}[Proof Sketch]
Hybrid compression removes experiences with lowest utility $U(e)$ first. With
$\beta > \delta$, confidence $c_e$ dominates the utility score. Beneficial
experiences accumulate high confidence over time (Equation~\eqref{eq:confidence-update}),
so the probability of a beneficial experience being pruned is bounded by
$O(e^{-\beta \cdot c_{\text{good}}})$, where $c_{\text{good}}$ is the typical
confidence of a beneficial experience after several uses. Setting $N_{\max}$
large enough that the expected number of pruned beneficial experiences per
epoch is at most $\varepsilon$ completes the argument.
\end{proof}

\begin{theorem}[Sample Complexity]
\label{thm:sample}
Let $\varepsilon > 0$ be a target improvement in expected task reward over the
zero-experience baseline. Under Assumptions~\ref{asm:bounded}--\ref{asm:accuracy},
the expected number of sessions required to achieve $\varepsilon$-improvement is:
\begin{equation}
    T(\varepsilon) = O\!\left(\frac{K_x}{\varepsilon^2\,(2p_c - 1)^2}\right),
    \label{eq:sample-complexity}
\end{equation}
where $K_x$ is the number of distinct task types in the task distribution
$\mathcal{X}$ and $p_c > 1/2$ is the extraction accuracy of Assumption~\ref{asm:accuracy}.
\end{theorem}

\begin{proof}
The expected improvement in task reward from retrieving a beneficial experience
is at least $\delta_{\min} > 0$ (the minimum individual experience effect size,
which exists by compactness of $[0,1]$).

From Theorem~\ref{thm:monotone}, after $t$ sessions the expected number of
beneficial experiences relevant to a task of type $x$ is at least:
\begin{equation}
    \mathbb{E}[B_k(x)] \geq \min\!\left(t\,p_c\,/K_x,\; K_{\text{ret}}\right),
\end{equation}
where $K_{\text{ret}}$ is the retrieval budget. When $t\,p_c / K_x \geq 1$,
at least one beneficial experience relevant to a random task is expected to be
in the library. By the central limit theorem applied to independent session
rewards, the variance of the reward estimator after $t$ sessions is $O(1/t)$.
Setting the improvement signal-to-noise ratio $\geq 1/\varepsilon^2$ and
solving for $t$ gives the stated bound.
\end{proof}

\begin{lemma}[Reward Consistency]
\label{lem:consistency}
The composite reward $R(\tau) = w_1 \rho_s(\tau) + w_2 \rho_a(\tau)$ is a
consistent estimator of task success in the following sense: for any two
trajectories $\tau, \tau'$ on the same task $x$ with
$\Pr[\text{task complete} \mid \tau] > \Pr[\text{task complete} \mid \tau']$,
we have $\mathbb{E}[R(\tau)] > \mathbb{E}[R(\tau')]$.
\end{lemma}

\begin{proof}
Task completion requires all tool calls to succeed ($\rho_s = 1$) and the
user to accept the result ($\rho_a = 1$). Since $w_1, w_2 > 0$ and
$\rho_s, \rho_a \geq 0$, and since task completion implies both $\rho_s = 1$
and $\rho_a = 1$:
\begin{align}
    \mathbb{E}[R(\tau)] &= w_1\,\mathbb{E}[\rho_s(\tau)] + w_2\,\mathbb{E}[\rho_a(\tau)] \\
    &\geq w_1\,\Pr[\text{task complete} \mid \tau] + w_2\,\Pr[\text{task complete} \mid \tau].
\end{align}
The strict inequality follows from $w_1 + w_2 > 0$ and the assumption that
task completion probabilities differ.
\end{proof}

\begin{proposition}[Memory Compression Preserves Utility]
\label{prop:compression}
Let $\mathcal{E}_\mathcal{C}$ be the experience library after hybrid
compression with threshold $N_{\max}$. Then the expected retrieval quality
(defined as the expected reward improvement from retrieved experiences)
satisfies:
\begin{equation}
    \mathbb{E}[\text{RetrievalQuality}(\mathcal{E}_\mathcal{C})]
    \geq (1 - \eta)\,\mathbb{E}[\text{RetrievalQuality}(\mathcal{E})],
    \label{eq:compression-quality}
\end{equation}
where $\eta \in [0, 1)$ is a compression efficiency factor that satisfies
$\eta \leq |\mathcal{E}| / N_{\max} - 1$ for $|\mathcal{E}| > N_{\max}$.
\end{proposition}

\begin{proof}[Proof Sketch]
Hybrid compression preferentially retains high-$U(e)$ experiences. The
expected retrieval quality is dominated by the top-$K$ most similar and
highest-confidence experiences. Since compression removes the bottom-utility
fraction first, and retrieval only uses the top-$K$, the quality degradation
is bounded by the probability that a top-$K$ experience falls below the
compression threshold, which is $O(1 - N_{\max}/|\mathcal{E}|)$.
\end{proof}

\subsection{Cost Analysis}

Table~\ref{tab:cost} compares Agent-GRPO with alternative adaptation
approaches for a representative software engineering agent.

\begin{table}[H]
\centering
\caption{Adaptation cost comparison for a tool-using agent across 100 sessions
($\sim$1,000 tool calls total). All costs are estimated for mid-2025 API pricing.}
\label{tab:cost}
\begin{tabularx}{\textwidth}{lXrr}
\toprule
\textbf{Method} & \textbf{Description} & \textbf{Compute Cost} & \textbf{GPU-hours} \\
\midrule
Full fine-tuning (RLHF)   & Gradient updates on full model weights & \$100,000+ & 1,000+ \\
LoRA fine-tuning           & Parameter-efficient gradient updates     & \$10,000--\$50,000 & 100--500 \\
Prompt engineering         & Manual trial-and-error prompting         & \$500--\$2,000 & 0 \\
RAG (static)               & Retrieve from fixed document corpus      & \$200--\$500 & 0 \\
Reflexion~\cite{shinn2023reflexion} & Session-level reflection, no persistence & \$50--\$200 & 0 \\
\textbf{Agent-GRPO (ours)} & \textbf{GRPO extraction + persistent library} & \textbf{\$15--\$20} & \textbf{0} \\
\bottomrule
\end{tabularx}
\end{table}

The per-session cost of Agent-GRPO is approximately:
\begin{equation}
    C_{\text{session}} \approx N_g \cdot G \cdot c_{\text{stage1}} + N_g \cdot c_{\text{stage2}} + c_{\text{stage3}},
    \label{eq:cost}
\end{equation}
where $c_{\text{stage1}} \approx \$0.02$ (small context, fast model),
$c_{\text{stage2}} \approx \$0.05$ (larger context), $c_{\text{stage3}} \approx \$0.10$
(batch consolidation with full library context), $N_g \approx 10$ task groups,
and $G = 4$ trajectories per group. This yields
$C_{\text{session}} \approx 10 \cdot 4 \cdot \$0.02 + 10 \cdot \$0.05 + \$0.10 = \$1.40$.
Over 10 sessions, total adaptation cost is approximately \$14, well within
the stated sub-\$20 budget.

% ============================================================================
% 8. EXPERIMENTS
% ============================================================================