# Feasibility-Ranked Group Policy Gradient

- ID: 2345
- Canonical URL: https://synthcore.org/idea/2345/feasibility-ranked-group-policy-gradient
- API JSON: https://synthcore.org/api/idea/2345.json
- API Markdown: https://synthcore.org/api/idea/2345.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.15359](https://arxiv.org/abs/2608.15359)
- Category: dynamics
- Solves: stability, sample-efficiency
- ML areas: rl, optimizer, transformer, training-dynamics
- Math tags: optimization, probability, statistics, control-theory, dynamical-systems
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace a learned critic with group-relative trajectory advantages whose weights are explicitly ordered by terminal feasibility. Feasible rollouts receive larger positive update weight than violating rollouts, while per-timestep normalization prevents high-variance late-horizon returns from dominating the policy gradient.

## Mathematical statement

For a batch of B trajectories of horizon T, let G_b be the return of trajectory b, let v_b >= 0 be its terminal constraint violation, and let F_b = 1[v_b <= delta] denote feasibility. Define a raw group-relative advantage A_{b,t} = G_b - B^{-1} sum_j G_j or a return-to-go analogue. Normalize independently at each timestep using A_tilde_{b,t} = (A_{b,t} - mu_t)/(sigma_t + epsilon), where mu_t = B^{-1} sum_b A_{b,t} and sigma_t^2 = B^{-1} sum_b (A_{b,t} - mu_t)^2. Introduce ranking weights w_b = w_F for feasible trajectories and w_b = w_V for violating trajectories, with w_F > w_V >= 0, or use a monotone rank function of v_b. The policy update maximizes the clipped objective with importance ratio rho_{b,t} = pi_theta(a_{b,t}|o_{b,t}) / pi_theta_old(a_{b,t}|o_{b,t}). The normalization controls per-timestep group variance, while the ranking mechanism has a positive expected feasibility bias whenever w_F E[A_tilde_t | F = 1] > w_V E[A_tilde_t | F = 0].

## Key formulas

- $$\widetilde A_{b,t}=\frac{A_{b,t}-\mu_t}{\sigma_t+\varepsilon},\qquad \mu_t=\frac{1}{B}\sum_{b=1}^{B}A_{b,t},\qquad \sigma_t^2=\frac{1}{B}\sum_{b=1}^{B}(A_{b,t}-\mu_t)^2.$$
- $$L_{\mathrm{rank\text{-}clip}}(\theta)=\frac{1}{BT}\sum_{b=1}^{B}\sum_{t=0}^{T-1}w_b\min\left(\rho_{b,t}\widetilde A_{b,t},\operatorname{clip}(\rho_{b,t},1-\epsilon,1+\epsilon)\widetilde A_{b,t}\right).$$
- $$w_F\,\mathbb E[\widetilde A_t\mid F=1]>w_V\,\mathbb E[\widetilde A_t\mid F=0]\quad\Longrightarrow\quad \text{the expected update has a positive feasible-trajectory component}.$$

## Implementation notes

Integrate this at the PPO/GRPO minibatch construction stage for an autoregressive Transformer policy or recurrent control policy. Collect B complete rollouts with the current policy, retaining observations, actions, rewards, old log probabilities, and the terminal constraint quantity. Compute each trajectory return G_b and terminal violation v_b = max(0, |c(x_{b,T}) - c_star| - delta); set F_b = 1 when v_b = 0. For every timestep, form group-relative raw advantages, compute the batch mean and standard deviation across trajectories, and normalize with a small epsilon. Choose w_b = w_F for feasible trajectories and w_b = w_V otherwise, initially using (w_F,w_V) = (2,1); optionally interpolate weights continuously with violation rank. Then optimize the clipped objective for several epochs, recomputing neither the normalization nor old-policy ratios during those epochs. Pseudocode is: rollout; compute G,v,F; compute A,mu_t,sigma_t,A_tilde; assign w; evaluate rho; backpropagate -L_rank-clip. The paper supplies the normalization and ranking mechanism; empirical estimates are mu_t, sigma_t, and conditional gradient statistics. First test on constrained CartPole or Pendulum with a terminal-state target, comparing PPO, critic-free GRPO, and this method at equal environment steps. Log normalized variance, feasible and violating weighted advantage means, and sustained feasibility. The quantitative prediction is that each timestep's normalized group variance remains approximately one and that the measured feasible-update margin w_F Abar_F - w_V Abar_V becomes positive before sustained feasibility improves. If the margin is negative, increasing ranking strength should not help and indicates that the ranking condition is unmet.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built and ran a self-contained feasibility-ranked group policy-gradient MVP with timestep-wise normalization, clipped ratios, and feasible/violating trajectory weights. The mechanism manifested: normalized variance matched the exact prediction across scales (0.9999996–0.999999999), and observed feasibility-margin values tracked analytical predictions closely across return separations and weight ratios. In the toy policy experiment, ranking increased final feasibility from 2.20e-9 to 3.21e-5 and reduced risky-action probability from 0.9815 to 0.8741, at the expected cost of lower unconstrained reward.

### Mechanism check

- Verdict: Built and ran a self-contained feasibility-ranked group policy-gradient MVP with timestep-wise normalization, clipped ratios, and feasible/violating trajectory weights. The mechanism manifested: normalized variance matched the exact prediction across scales (0.9999996–0.999999999), and observed feasibility-margin values tracked analytical predictions closely across return separations and weight ratios. In the toy policy experiment, ranking increased final feasibility from 2.20e-9 to 3.21e-5 and reduced risky-action probability from 0.9815 to 0.8741, at the expected cost of lower unconstrained reward.
- Confidence: 8/10
- Limitations: The policy comparison is a tiny synthetic Bernoulli horizon rather than CartPole/Pendulum, and does not compare against a learned-critic PPO implementation. The feasibility gain is absolute but both methods remain poor under the deliberately conflicting reward/constraint setup; no larger-scale sample-efficiency or wall-clock study was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0533
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/924/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/924/bench_report.json)
- [experiment.py](https://synthcore.org/code/924/experiment.py)
- [report.md](https://synthcore.org/code/924/report.md)
- [report_bench_2026-09-02T233524.md](https://synthcore.org/code/924/report_bench_2026-09-02T233524.md)
- [rerun.json](https://synthcore.org/code/924/rerun.json)
- [results.json](https://synthcore.org/code/924/results.json)
- [Download all files as ZIP](https://synthcore.org/download/924)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.