# Diversity-Weighted Leave-One-Out Policy Baseline

- ID: 2183
- Canonical URL: https://synthcore.org/idea/2183/diversity-weighted-leave-one-out-policy-baseline
- API JSON: https://synthcore.org/api/idea/2183.json
- API Markdown: https://synthcore.org/api/idea/2183.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.12443](https://arxiv.org/abs/2608.12443)
- Category: optimization
- Solves: stability, sample-efficiency, accuracy
- ML areas: optimizer, rl, training, graph-nn
- Math tags: probability, optimization, linear-algebra, geometry
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace the usual best-sample or uniform group baseline in sampled-policy training with a leave-one-out baseline weighted toward structurally dissimilar solutions. Diverse peers contribute more independent information, while near-duplicate trajectories contribute less redundant signal.

## Mathematical statement

The paper defines the expected-cost objective $\mathcal{J}(\theta)=\mathbb{E}_{\mathbf{s}\sim\pi_\theta}[c(\mathbf{s})]$, where $\pi_\theta$ is an autoregressive policy, $\mathbf{s}$ is a complete sampled solution, and $c(\mathbf{s})$ is a cost to minimize. For a group of $B$ samples $\{\mathbf{s}_1,\ldots,\mathbf{s}_B\}$ from the same instance, construct an embedding $z_i\in\mathbb{R}^d$ for each solution from the encoder's existing node representations; the paper specifies Hadamard-product aggregation for TSP and mean-pooling for EFL/JSP, followed by centering. A concrete implementation of the stated pairwise-dissimilarity weighting is $d_{ij}=\|z_i-z_j\|_2^2$ and $w_{ij}=(d_{ij}+\varepsilon)^p$ for $i\neq j$, where $\varepsilon>0$ prevents zero weights and $p\geq0$ controls diversity emphasis. The leave-one-out baseline for sample $i$ is $b_i=\frac{\sum_{j\neq i}w_{ij}c_j}{\sum_{j\neq i}w_{ij}}$, with $c_j=c(\mathbf{s}_j)$. For minimization, the advantage is $A_i=b_i-c_i$: a sample cheaper than its structurally distinct peers has positive advantage. The adapted surrogate loss is $\mathcal{L}_{\mathrm{SSPO}}=-\frac{1}{B}\sum_{i=1}^B\operatorname{stopgrad}(A_i)\log\pi_\theta(\mathbf{s}_i)$, where $\log\pi_\theta(\mathbf{s}_i)=\sum_t\log\pi_\theta(s_{i,t}\mid s_{i,<t})$. Stop-gradient is required through costs, embeddings, distances, weights, and baselines.

## Key formulas

- $$\mathcal{J}(\theta)=\mathbb{E}_{\mathbf{s}\sim\pi_{\theta}}\bigl[c(\mathbf{s})\bigr]$$
- $$d_{ij}=\lVert z_i-z_j\rVert_2^2,\qquad w_{ij}=(d_{ij}+\varepsilon)^p\quad(i\neq j)$$
- $$b_i=\frac{\sum_{j\neq i}w_{ij}c_j}{\sum_{j\neq i}w_{ij}},\qquad A_i=b_i-c_i$$
- $$\mathcal{L}_{\mathrm{SSPO}}=-\frac{1}{B}\sum_{i=1}^{B}\operatorname{stopgrad}(A_i)\sum_{t=0}^{T-1}\log\pi_{\theta}(s_{i,t}\mid s_{i,<t})$$

## Implementation notes

(1) Integrate this into the sampled-policy loss for a neural combinatorial solver or any grouped trajectory optimizer. For each input instance, sample $B$ complete solutions with the current policy and retain their per-sample costs $c_i$. At the same time, expose the encoder node states $h_{i,1},\ldots,h_{i,N}$ used while decoding. Build one solution embedding per sample: for TSP, aggregate representations of consecutive selected nodes using a Hadamard product and mean-pool the resulting edge features; for a simpler first implementation, mean-pool encoder states indexed by selected solution elements. For EFL/JSP, directly mean-pool representations of selected or assigned nodes. Center embeddings across the group with $z_i=\tilde z_i-B^{-1}\sum_k\tilde z_k$. (2) Compute pairwise squared distances $d_{ij}=\|z_i-z_j\|_2^2$, weights $w_{ij}=(d_{ij}+10^{-8})^p$ with $p=1$ initially, and baselines $b_i=\sum_{j\ne i}w_{ij}c_j/\sum_{j\ne i}w_{ij}$. Form $A_i=b_i-c_i$, optionally divide by the group cost standard deviation, detach all baseline quantities, and backpropagate $-B^{-1}\sum_iA_i\log\pi_\theta(\mathbf{s}_i)$. (3) The exact mathematical computations are centered embeddings, pairwise dissimilarities, normalized leave-one-out weights, and advantages; no learned baseline parameters are added. Sweep $p\in\{0,0.5,1,2\}$ and measure the effective baseline sample count $1/\sum_j\bar w_{ij}^2$, where $\bar w_{ij}=w_{ij}/\sum_{k\ne i}w_{ik}$. (4) First test on a small attention-based TSP solver on TSP-50, using the same batch size, number of samples, optimizer, and compute budget as REINFORCE with a uniform leave-one-out baseline and a best-sample baseline. Track gradient-norm variance, cost versus environment samples, training throughput, and final tour length. Success means lower gradient variance and reaching a fixed tour-quality threshold with fewer samples or training steps, while the additional pairwise $O(B^2d)$ computation does not materially increase wall-clock time.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built the diversity-weighted leave-one-out baseline and detached PyTorch SSPO loss. The mechanism checks matched predictions: p=0 recovered uniform LOO and effective count 5.0, distance ratios matched the squared-distance power law (16.0), and effective count fell from 4.0 to 2.00 as p increased from 0 to 2. The secondary categorical policy proxy did not show a win: diversity weighting increased gradient variance 3.47x versus uniform LOO, so this is mechanism-validated but not evidence of improved training.

### Mechanism check

- Verdict: Built the diversity-weighted leave-one-out baseline and detached PyTorch SSPO loss. The mechanism checks matched predictions: p=0 recovered uniform LOO and effective count 5.0, distance ratios matched the squared-distance power law (16.0), and effective count fell from 4.0 to 2.00 as p increased from 0 to 2. The secondary categorical policy proxy did not show a win: diversity weighting increased gradient variance 3.47x versus uniform LOO, so this is mechanism-validated but not evidence of improved training.
- Confidence: 9/10
- Limitations: No neural TSP-50 solver, multi-step training curve, wall-clock throughput, final tour quality, or GPU experiment was tested. The toy variance comparison used a four-action categorical policy and does not establish general RL performance.

### Practical benchmark

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

## Artifacts

- [bench_report.json](https://synthcore.org/code/872/bench_report.json)
- [diversity_baseline.py](https://synthcore.org/code/872/diversity_baseline.py)
- [report.md](https://synthcore.org/code/872/report.md)
- [report_bench_2026-09-01T132743.md](https://synthcore.org/code/872/report_bench_2026-09-01T132743.md)
- [run_experiment.py](https://synthcore.org/code/872/run_experiment.py)
- [stage2_bench.py](https://synthcore.org/code/872/stage2_bench.py)
- [verification.json](https://synthcore.org/code/872/verification.json)
- [Download all files as ZIP](https://synthcore.org/download/872)

## Disclaimer

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