Technical Summary: Owen-Shapley Policy Optimization (OSPO)

Problem Statement

Large Language Models (LLMs) are increasingly deployed in generative recommendation systems, where they synthesize user preferences and refine search queries to condition downstream retrieval and ranking. While Reinforcement Learning (RL) methods like Group-Relative Policy Optimization (GRPO) enable training without parametric value models by using sequence-level terminal rewards (e.g., NDCG from a retriever), they suffer from a critical credit assignment gap.

In standard value-model-free RL, a single scalar advantage is assigned uniformly to all tokens in a generated sequence. This obscures which specific phrases or semantic segments actually contributed to the high-quality output. This limitation is particularly acute in recommendation tasks where models must infer latent user intent from under-specified language without ground-truth labels. Furthermore, uniform credit assignment makes models vulnerable to reward hacking, where the model overfits to surface-level cues or exploits shortcuts in black-box retrievers rather than learning robust, semantically coherent query representations. Existing solutions like Process Reward Models (PRMs) require labeled intermediate steps, and attention-based methods often entangle spurious correlations.

Methodology: Owen-Shapley Policy Optimization (OSPO)

The authors introduce OSPO, a framework that redistributes sequence-level advantages based on the marginal contributions of semantically coherent token segments (coalitions) to the final outcome. OSPO operates in the critic-free regime, requiring no external value networks.

Core Mechanism

1. Segmentation and Coalitions: Generated responses are decomposed into $N$ semantically meaningful segments (e.g., phrases, sentences). Instead of evaluating all $2^N$ possible subsets (intractable), OSPO restricts evaluation to contiguous coalitions (consecutive segments). This preserves semantic coherence and reduces computational complexity from exponential to linear $O(N \cdot w_{max})$, where $w_{max}$ is the maximum coalition width.
2. Owen-Shapley Attribution: Using cooperative game theory, OSPO computes Owen values for each segment. The value $\phi_j$ of a segment $j$ is its expected marginal contribution to the reward when added to various contiguous coalitions $S$:
   $$\phi_j^{Owen} = \frac{1}{|C_j|} \sum_{S \in C_j} (v(S \cup \{j\}) - v(S))$$
   Here, $v(S)$ is the reward obtained by querying the retriever (or reward model) with the partial sequence formed by concatenating segments in coalition $S$.
3. Advantage Redistribution: The sequence-level advantage $\hat{A}^{(g)}$ (computed via group-relative normalization in GRPO) is redistributed to individual tokens. The token-level advantage $A_t^{(g)}$ is calculated as:
   $$A_t^{(g)} = T \cdot \tilde{\phi}_t^{(g)} \cdot \hat{A}^{(g)}$$
   where $\tilde{\phi}_t$ is the normalized Owen value for the token's segment, and $T$ is the sequence length. The multiplication by $T$ ensures length invariance, preventing longer sequences from receiving disproportionately weaker gradient signals compared to shorter ones.
4. Objective: The policy is updated using a clipped surrogate objective (similar to PPO/GRPO) but utilizing these fine-grained, Owen-weighted token advantages.

Variants

The paper evaluates three redistribution strategies:

• OSPO-PROP: Proportional redistribution based on normalized Owen values.
• OSPO-RANK: Redistributes based on the ordinal rank of Owen values to handle noisy estimates.
• OSPO-CLIP: Constrains redistributed advantages to a range based on Chebyshev's inequality for stability.

Key Contributions

1. Principled Credit Assignment without Value Models: OSPO bridges the gap between sparse terminal rewards and fine-grained token updates by leveraging Owen-Shapley values, eliminating the need for learned critics or process reward models.
2. Coalition-Based Semantics: By treating semantically coherent phrases as players in a coalition game, OSPO identifies which parts of a response drive downstream utility (e.g., retrieval success), offering better interpretability than uniform assignment.
3. Efficiency and Scalability: The contiguous coalition constraint makes the computation tractable for online RL training, scaling linearly with the number of segments, unlike quadratic approximations in prior Shapley-based works.
4. Robustness to Distribution Shift: The method learns retriever-agnostic query representations that generalize well to unseen retrievers and embedding spaces.

Experimental Results

The authors evaluated OSPO on two e-commerce datasets: Amazon ESCI (product search query refinement) and H&M Fashion (contextualized search and user profile summarization).

• Performance Gains: OSPO-PROP consistently outperformed baselines (SFT, DPO, GRPO) across all metrics (NDCG, AP, MRR, Recall). On the ESCI dataset, OSPO-PROP (7B) achieved an NDCG of 0.522, surpassing the 32B model (0.496) and the 72B model (0.543, though 72B degraded on H&M). On H&M, OSPO-PROP (7B) reached 0.436 NDCG, outperforming GRPO (0.379) and approaching the performance of GPT-4o (0.433) at a fraction of the parameter count.
• Sample Efficiency: OSPO reached target performance in approximately 50% fewer training steps than GRPO.
• Generalization: In cross-retriever evaluations (training on one embedding model, testing on another), OSPO maintained strong performance, whereas GRPO and offline methods (DPO, SFT) degraded significantly. This suggests OSPO learns more transferable alignment signals.
• Stability: OSPO demonstrated lower reward variance and avoided the "reward hacking" collapse (e.g., generating empty or minimal sequences) observed in GRPO during later training stages.
• Ablation Studies: The authors found that moderate-width contiguous coalitions (e.g., $w_{max}=4$ to $8$) with sufficient sampling provided the best balance between local context and exploration. Non-contiguous coalitions led to performance collapse, and very narrow coalitions caused overfitting to surface patterns.

Significance and Claims

The paper claims that OSPO provides a principled, critic-free approach to solving the credit assignment problem in generative recommendation. By shifting from token-level uniformity to segment-level marginal attribution, OSPO enables models to learn why a response was successful, focusing gradient updates on high-contribution semantic units.

The authors emphasize that this approach allows smaller models (e.g., 7B) to compete with or exceed much larger models (32B, 72B) and frontier zero-shot models (GPT-4o) in specific retrieval tasks. Furthermore, the method's ability to generalize across unseen retrievers and embedding spaces highlights its potential for robust deployment in dynamic recommendation environments where ground-truth preferences are latent and feedback is sparse. The work suggests that coalition-based attributions act as an intrinsic regularizer, promoting stable, transferable, and interpretable behaviors without the computational overhead of training value functions.