Finite-budget group-relative policy update

Fix a nonempty finite ordered prompt list $(q_1,\dots ,q_M)$ with no repeated prompt. For each prompt $q_{\mathrm{\ell }}$, take the finite truncated response set $Y_{q_{\mathrm{\ell }}}$, ordered policy support $B_{q_{\mathrm{\ell }}}$, and policy family ${\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})$ from the generation protocol, with open parameter domain $U$. Fix a reference probability mass function ${\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }})$ that is positive on exactly $B_{q_{\mathrm{\ell }}}$, a finite reward function $r_{q_{\mathrm{\ell }}}:B_{q_{\mathrm{\ell }}}\to \mathbb{R}$, an initial parameter ${\theta }_0\in U$, group size $G\ge 2$, a positive integer number $T$ of outer iterations, a positive integer number $K$ of inner steps per outer iteration, a clipping threshold $ϵ\in (0,1)$, a penalty weight $\beta \ge 0$, and positive step sizes ${\eta }_{t,k}$ for $1\le t\le T$ and $1\le k\le K$. The prompt weights are uniform. Response draws, reward and policy-mass evaluations, scalar arithmetic, square roots, logarithms and comparisons are supplied terminating exact operations with finite per-call costs. Draws return supported responses with the specified independent law. Also supply an exact total domain oracle $M_U:{\mathbb{R}}^d\to \{0,1\}$, returning $1$ exactly on $U$, and an exact objective-gradient oracle: given the frozen outer-iteration data and a parameter in $U$, it returns the Euclidean gradient of $F_t$ when that total derivative exists and returns undefined-gradient otherwise. Both oracles terminate on every call with finite per-call cost. The gradient oracle includes the fixed finite objective data and any policy evaluations needed for its decision. This is a supplied-oracle model; it asserts neither an algorithm for deciding differentiability of arbitrary functions nor a general membership algorithm for arbitrary open sets.

At outer iteration $t$, freeze ${\theta }_{t-1}$ and, for each prompt $q_{\mathrm{\ell }}$, draw $G$ independent responses $Y_{\mathrm{\ell },1},\dots ,Y_{\mathrm{\ell },G}$ from ${\pi }_{{\theta }_{t-1}}(\cdot \mid q_{\mathrm{\ell }})$. Compute the finite rewards $R_{\mathrm{\ell },i}:=r_{q_{\mathrm{\ell }}}(Y_{\mathrm{\ell },i})$, their mean

${\bar{R}}_{\mathrm{\ell }}:=\frac{1}{G}{\sum }_{i=1}^G{R}_{\mathrm{\ell },i},$

and their population standard deviation

$s_{\mathrm{\ell }}:=\sqrt{\frac{1}{G}{\sum }_{i=1}^G(R_{\mathrm{\ell },i}-{\bar{R}}_{\mathrm{\ell }}{)}^2}\mathrm{.}$

Set $A_{\mathrm{\ell },i}:=(R_{\mathrm{\ell },i}-{\bar{R}}_{\mathrm{\ell }})\mathrm{/}{s}_{\mathrm{\ell }}$ when $s_{\mathrm{\ell }}>0$, and set $A_{\mathrm{\ell },i}=0$ for every $i$ when $s_{\mathrm{\ell }}=0$. Hold the responses, rewards, and advantages fixed through the $K$ inner steps. For a candidate parameter $\theta \in U$, use the sequence-level ratio

${\rho }_{\mathrm{\ell },i}(\theta ):=\frac{{\pi }_{\theta }(Y_{\mathrm{\ell },i}\mid q_{\mathrm{\ell }})}{{\pi }_{{\theta }_{t-1}}(Y_{\mathrm{\ell },i}\mid q_{\mathrm{\ell }})}\mathrm{.}$

The denominator is positive. Define $\mathrm{clip}(x,1-ϵ,1+ϵ):=\min (1+ϵ,\max (1-ϵ,x))$, and use the exact finite-distribution forward KL penalty

$D_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})\mathrm{\parallel }{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }})):={\sum }_{j=1}^{n_{q_{\mathrm{\ell }}}}{\pi }_{\theta }(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})\log \frac{{\pi }_{\theta }(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})}{{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(b_{q_{\mathrm{\ell }},j}\mid q_{\mathrm{\ell }})},$

where $(b_{q,1},\dots ,b_{q,n_q})$ is the ordered support from the generation protocol. The empirical objective is

$F_t(\theta ):=\frac{1}{M}{\sum }_{\mathrm{\ell }=1}^M[\frac{1}{G}{\sum }_{i=1}^G\min \{{\rho }_{\mathrm{\ell },i}(\theta )A_{\mathrm{\ell },i},\mathrm{clip}({\rho }_{\mathrm{\ell },i}(\theta ),1-ϵ,1+ϵ)A_{\mathrm{\ell },i}\}-\beta D_{\mathrm{K}\mathrm{L}}({\pi }_{\theta }(\cdot \mid q_{\mathrm{\ell }})\mathrm{\parallel }{\pi }_{\mathrm{r}\mathrm{e}\mathrm{f}}(\cdot \mid q_{\mathrm{\ell }}))]\mathrm{.}$

For each outer iteration, set ${\theta }^{(0)}:={\theta }_{t-1}$. For each inner step $k$, call the supplied objective-gradient oracle at ${\theta }^{(k-1)}$. If it returns a gradient, form the proposed update

${\theta }^{(k)}:={\theta }^{(k-1)}+{\eta }_{t,k}\mathrm{\nabla }{F}_t({\theta }^{(k-1)})$

and call $M_U$ at that proposal. If $M_U$ returns $1$, apply it; the stipulated fixed positive support then holds on $U$. If the gradient oracle returns undefined-gradient, stop and return the last valid parameter with status undefined-gradient. If $M_U$ returns $0$, stop and return the last valid parameter with status invalid-update. After $K$ successful inner steps set ${\theta }_t:={\theta }^{(K)}$ and continue to the next outer iteration. After $T$ successful outer iterations return ${\theta }_T$ with status complete. This procedure asserts no monotone improvement, unbiasedness, or convergence guarantee.

Finite group-relative updates preserve admissibility and have bounded oracle calls ↗: proves valid-parameter and finite-objective properties, finite termination, and the response-draw and gradient-attempt bounds in the supplied-oracle model.

The finite truncation, response sets, policy support, and prompt-wise probability masses.

The differentiable policy family and fixed positive support convention.

For positive finite response laws, the sequence-level probability ratio is the exact finite change-of-measure factor before clipping.

The finite sums used for group averages and the exact finite-distribution KL.

The probability laws that govern the finite response draws.