PaperlayerView exact revision on arXiv

Source-linked AI summary

Marginal Coverage Credit Reduces Redundant Exploration in Parallel State-Entropy Optimization

Junhao Cao, Hongyi Xia, Jianian Wu, Xiaopeng Yi, Lixia Huang, Ping Guo

arXiv:2608.27507v1cs.LGcs.AI

TL;DR

PGPSE’s pooled team-entropy score measures collective exploration but cannot identify which policies provide non-redundant coverage. MCC-PGPSE combines leave-one-policy-out coverage with state-owner specialization to redistribute auxiliary rewards while preserving total mass and the pooled objective. Across controlled, public, and original-protocol settings, it improved final-window team entropy and state support, with significance varying by evaluation protocol.

  • Problem

    PGPSE’s pooled team-entropy score measures collective exploration but does not isolate each policy’s marginal contribution to non-redundant coverage.

  • Method

    MCC-PGPSE combines leave-one-policy-out coverage with state-owner specialization to redistribute non-negative auxiliary intrinsic rewards while preserving PGPSE’s pooled objective and total reward mass.

  • Results

    MCC-PGPSE produced positive final-window gains in normalized team state entropy and state support across controlled environments, seven public benchmarks, and representative original protocols.

  • Takeaways & Limitations

    Contribution-conditioned auxiliary reward allocation is supported as an interpretable approach to improving complementary coverage among parallel policies in discrete state spaces.

  • Takeaways & Limitations

    Five-seed original-protocol comparisons were treated as directional replication rather than standalone 5% significance, and a single map pair cannot attribute between-map differences to stochasticity.

Abstract

from arXiv · show

Policy Gradient for Parallel State Entropy maximization (PGPSE) expands state-space coverage by training independently parameterized policies in replicated copies of the same environment. However, its pooled team-entropy score measures only collective exploration and cannot identify policies that contribute non-redundant coverage. We introduce Marginal Coverage Credit for PGPSE (MCC-PGPSE), which combines leave-one-policy-out coverage with state-owner specialization to estimate policy-specific credit. MCC-PGPSE preserves PGPSE's pooled objective and redistributes non-negative auxiliary intrinsic rewards according to these credits without changing their total mass. This redistribution is designed to discourage redundant visitation and promote complementary coverage. We evaluated MCC-PGPSE in controlled environments, seven public discrete-state benchmarks, and representative Room and Maze settings from the original PGPSE protocol. Across all tested settings, MCC-PGPSE produced positive final window gains in normalized team state entropy and state support over the Entropy baseline. Controlled-task comparisons and the fixed-suite public aggregate were significant, whereas five-seed original-protocol comparisons were directionally consistent. Ablations and credit alignment controls indicate that most gains arise from leave-one-policy-out coverage rather than non-uniform weighting, mismatched credit, or neural novelty alone. These results support contribution-conditioned auxiliary reward allocation as an interpretable approach to improving complementary coverage among parallel policies in discrete state spaces.

1. Introduction

PGPSE broadens exploration through pooled team entropy, but that shared score does not identify each policy’s non-redundant contribution. MCC-PGPSE adds policy-specific credit while preserving the pooled objective and total auxiliary reward mass.

  • Motivation: The contribution targets redundancy that existing single-policy novelty methods and parallel-training mechanisms do not explicitly address.Related multi-agent credit-assignment methods generally concern joint actions in a shared environment, unlike policies exploring separate copies.
  • Motivation: PGPSE trains independently parameterized policies in replicated environments and optimizes entropy over their pooled state distribution.Its shared rollout-level scalar favors aggregate coverage but does not isolate individual marginal contributions.
  • Proposed method: MCC-PGPSE estimates policy-specific credit using leave-one-policy-out coverage and state-owner specialization.The leave-one-policy-out term measures coverage lost when a policy is removed, while specialization adds policy- and transition-specific weighting.
  • Proposed method: MCC-PGPSE redistributes non-negative auxiliary intrinsic rewards without replacing the pooled team-entropy objective or changing total auxiliary reward mass.The redistribution applies to online novelty and replay pathways and reduces the signal assigned to redundant trajectories.
  • Evaluation: The study evaluates MCC-PGPSE in controlled environments, seven public discrete-state benchmarks, and representative Room and Maze settings from the original PGPSE protocol.These evaluations test the method across controlled, public, and project-native settings.

2. Related methods

Related methods improve exploration through novelty, replay, parallel training, or cooperative credit assignment, but these approaches do not directly ensure complementary coverage across policies exploring separate environment copies.

  • Exploration methods: Maximum state-entropy, count-based, pseudo-count, curiosity, random-distillation, and ensemble methods provide complementary exploration signals.These methods use state-distribution objectives, visitation counts, prediction error, fixed random targets, or model uncertainty.
  • Exploration methods: Replay-enhanced methods reuse stored transitions to provide additional learning from prior experience.Replay is presented as one pathway for improving exploration-related training signals.
  • Parallel training: Asynchronous reinforcement learning and population-based training distribute collection or adapt concurrently trained models, but do not ensure complementary state coverage.These mechanisms mainly improve collection throughput or optimization.
  • Credit assignment: COMA, VDN, QMIX, and Shapley-style methods assign credit under shared objectives, primarily for agents taking joint actions in one environment.MCC-PGPSE instead considers policies exploring separate environment copies without learning joint action-values or decomposing pooled entropy.

3. Methods

MCC-PGPSE extends parallel state-entropy exploration with policy-specific coverage credit while retaining the shared team-entropy objective. It combines leave-one-policy-out support loss with state-owner specialization and reallocates auxiliary rewards without increasing their total mass.

  • Problem setting: The method runs N independently parameterized policies in replicated environments, coupling them through pooled exploration and coverage-credit calculations.Their trajectories are pooled to define collective state coverage, while policies do not share parameters or execute joint actions in one environment.
  • Method overview: MCC-PGPSE retains the shared team state-entropy objective and applies marginal coverage credit only to auxiliary rewards from online novelty and replay pathways.Each discrete state is represented as a unique one-hot observation, and the shared objective remains part of the policy update.
  • Base auxiliary exploration rewards: The online auxiliary signal combines count novelty, ensemble prediction surprise, disagreement, and an adaptive gain based on running surprise statistics.The forward ensemble is updated after transitions, while the adaptive gain uses the running mean and variance of surprise averaged across policies.
  • Reward-conserving allocation: The conservation operator reallocates non-negative online and replay rewards using credit weights while preserving the original auxiliary reward total.Online rewards are redistributed at each transition, whereas replay uses each policy’s final within-rollout weight.
  • Marginal coverage credit: MCC estimates policy-specific contribution from leave-one-policy-out coverage loss and state-owner specialization, providing trajectory-level and transition-level credit.Support loss measures states that disappear when a policy is removed, while specialization favors successor states visited by fewer policies.
  • Marginal coverage credit: Credit is smoothed within rollouts, converted to temperature-controlled probabilities, and mixed with a uniform minimum-credit component so every policy retains an auxiliary signal.The default smoothing coefficient is 0.9, the credit temperature is 0.5, and the minimum-credit mixture is 0.1.

4. Experiments

The experiments test MCC-PGPSE across controlled exploration structures, original PGPSE settings, and seven public discrete-state benchmarks using matched evaluation protocols and coverage-focused metrics.

  • Controlled environments: The evaluation covers four controlled grid-map families designed to test open coverage, bottleneck traversal, branch specialization, and stochastic-transition robustness.Policies act in replicated map copies rather than jointly in one shared world.
  • Controlled environments: Bottleneck-memory and branching-specialization are the primary controlled tasks for evaluating marginal coverage credit.Open-field verifies pipeline stability, while stochastic-loops provides robustness evidence.
  • Evaluation settings: The study also reproduces representative deterministic Room and stochastic Maze settings from the original PGPSE protocol without isolating individual credit components.Both maps contain 43 reachable states, but topology, stochasticity, and rollout horizon differ.
  • Evaluation settings: Cross-environment validity is assessed on FrozenLake-v1, Taxi-v3, CliffWalking-v0, and four MiniGrid tasks under a reward-free state-coverage protocol.Outcomes concern normalized team state entropy and state support rather than extrinsic return or task success.
  • Protocol and metrics: The primary comparison includes Entropy, Count, ICM, RND, Online, Triad, and MCC-PGPSE across six independently parameterized policies.Primary controlled comparisons and public benchmarks use eight matched seeds and 300 updates; sensitivity analyses use five seeds.
  • Protocol and metrics: Final-window normalized team state entropy and state support are computed over the final 20% of training using unsmoothed data and bootstrap confidence intervals.Matched-seed comparisons use exact two-sided sign-flip tests with Holm correction within prespecified hypothesis families.

4.3. Experimental results and analysis

In bottleneck-memory and branching-specialization, MCC-PGPSE improves final-window team coverage over Entropy, with larger gains where redundant constrained traversal is more costly.

  • Bottleneck-memory: MCC-PGPSE continued improving during later bottleneck-memory updates while Entropy, Online, and Triad remained within a narrow range.The divergence emerged after distinct visitation histories accumulated, consistent with leave-one-policy-out credit identifying non-redundant remote-state contributors.
  • Bottleneck-memory: 5.98% higher Objective and 10.13% higher Support were achieved by MCC-PGPSE than Entropy in the bottleneck-memory final window.MCC-PGPSE recorded Objective 0.4911 and Support 14.04.
  • Bottleneck-memory: All eight bottleneck-memory seed-matched differences favored MCC-PGPSE, with significant comparisons against Entropy, Count, ICM, and Triad after Holm correction.Adjusted p-values were 0.0234 for Entropy, Count, and ICM, and 0.0078 for Triad.
  • Branching-specialization: MCC-PGPSE maintained a positive later-window shift in branching-specialization, assigning more auxiliary weight to policies contributing branch-specific states.The comparison uses smoothed learning curves with standard-error bands and seed-level final-window estimates.
  • Branching-specialization: 1.19% higher Objective and 3.11% higher Support were achieved by MCC-PGPSE than Entropy in branching-specialization.Every seed-matched difference was positive, with significant comparisons against Entropy, Count, ICM, and Triad.
  • Cross-environment comparison: The larger bottleneck-memory separation indicates that marginal credit has greater leverage when constrained routes impose a higher exploration opportunity cost.Branching-specialization showed smaller effects because alternative branches already encouraged some natural policy diversity.

4.4. Ablation and mechanism analysis

Matched ablations and controls indicate that leave-one-policy-out coverage supplies most of MCC-PGPSE’s gain, while state-owner specialization provides a smaller refinement. The benefits align with reduced overlap and increased unique-state coverage, and require contribution-aligned rather than merely non-uniform reward weighting.

  • Component ablation: LOO-only recovered most of MCC-PGPSE’s performance, whereas Specialization-only remained closer to Triad.MCC-PGPSE still exceeded both single-component variants on final-window Objective and Support in both environments, with Holm-adjusted p≤0.0234.
  • Behavioral diagnostics: MCC-PGPSE reduced final pairwise overlap by 0.022 in bottleneck-memory and 0.006 in branching-specialization relative to Triad.It also increased unique-state fraction by approximately 0.006 in both tasks.
  • Credit definition: Coverage-based credit outperformed direct marginal-entropy credit on Objective and Support in all eight matched seeds across both tasks.The comparison was significant with Holm-adjusted p=0.0078; support loss asks whether removing a policy eliminates a team-covered state, whereas marginal entropy is sensitive to frequency changes.
  • Allocation target: MCC-on-entropy increased Objective by 0.0711 and Support by 4.118 in bottleneck-memory relative to auxiliary allocation.The corresponding increases in branching-specialization were 0.0367 and 3.419, with Holm-adjusted p=0.0078 for each comparison.
  • Credit alignment controls: Static and Reversed credit remained close to Triad, while MCC-PGPSE remained significantly better on both Objective and Support.Both comparisons had Holm-adjusted p=0.0234 for each metric, indicating that non-uniformity alone and reversed assignment did not reproduce the gain.
  • Attribution boundary: The experiments do not support fixed-budget arbitration as an independent explanation of the observed gain.Within the implemented controls, the evidence instead supports contribution-conditioned redistribution while leaving other credit mechanisms untested.

4.5. Protocol replication, robustness, and cross-environment validation

MCC-PGPSE showed positive coverage gains under the original PGPSE protocol, stochastic transitions, and seven public discrete-state tasks. The original-protocol results were directional, while the public-suite aggregate was significant despite no individually corrected taskwise comparison crossing 0.05.

  • Original-protocol replication: MCC-PGPSE exceeded Entropy for every seed and both metrics in Room and Maze.Mean final-window gains in Maze were 0.124 for Objective and 7.63 for Support; Room gains were 0.093 and 7.76.
  • Original-protocol replication: Five-seed original-protocol replication was treated as directional rather than standalone 5% significance.With five pairs, the smallest attainable exact two-sided sign-flip p-value was 0.0625, and a single map pair could not attribute between-map differences to stochasticity.
  • Stochastic-transition robustness: MCC-PGPSE exceeded Entropy by 0.0026 in Objective and 0.209 in Support in stochastic-loops.It also exceeded Triad by 0.0026 and 0.198; all eight matched-seed differences were positive and comparisons remained significant after Holm correction.
  • Public benchmarks: Across all seven public tasks, paired final-window Objective and Support differences were positive relative to Entropy and Triad.No individual task met the corrected 0.05 threshold, so the suite-level ordering supports contribution-aware redistribution without independently decisive taskwise effects.
  • Public benchmarks: Public-benchmark effect sizes varied across tasks, with larger shifts on CliffWalking-v0 and several MiniGrid layouts than on FrozenLake-v1 and Taxi-v3.The comparisons do not isolate which task property drove this variation.
  • Public benchmarks: The fixed-suite aggregate increased mean Objective by 0.0403 and mean relative Support by 16.29%.Both aggregates had exact p=0.0078; the evidence supports a positive average effect on discrete-state coverage, not gains in extrinsic return, pixel observations, continuous actions, or actor–critic backbones.

4.6. Hyperparameter sensitivity analysis

Sensitivity tests found that lower credit temperatures aligned with stronger coverage and less overlap, while increasing either credit coefficient aligned with higher coverage within the tested range. MCC-PGPSE incurred primarily computational-time overhead rather than additional parameters or memory.

  • Credit temperature: Lower credit temperatures were associated with higher Objective AUC, final Objective, and final Support, alongside lower policy overlap and higher unique-state fraction.The pattern was consistent with sharper allocation toward policies providing irreplaceable coverage.
  • Credit coefficients: Increasing either credit coefficient was associated with higher coverage within the tested range, with a larger change for leave-one-policy-out coverage.These one-factor patterns agreed with the component ablation but did not estimate parameter interactions or behavior beyond the tested ranges.
  • Computational cost: MCC-PGPSE increased update time by 178.05% relative to Entropy and by 21.53% relative to Triad, while reducing throughput by 17.72% versus Triad.The incremental set-based credit cost was primarily computational time.

5. Conclusions

The study concludes that MCC-PGPSE assigns policy-specific marginal coverage credit while preserving PGPSE’s pooled objective and total auxiliary reward mass. Across the evaluated settings, it improved final-window coverage metrics, with evidence indicating leave-one-policy-out coverage as the main contributor.

  • 5. Conclusions: MCC-PGPSE combines leave-one-policy-out coverage with state-owner specialization to redistribute non-negative auxiliary intrinsic rewards without changing PGPSE’s pooled objective or total reward mass.The method was evaluated in controlled environments, seven public discrete-state benchmarks, and representative original PGPSE protocols.
  • 5. Conclusions: MCC-PGPSE produced positive final-window gains in normalized team state entropy and state support across the evaluated settings.Controlled-task comparisons and the fixed-suite public aggregate were significant, while five-seed original-protocol comparisons were directionally consistent.
  • 5. Conclusions: Ablations and credit-alignment controls indicate that most gains arose from leave-one-policy-out coverage rather than alternative weighting, mismatched credit, or neural novelty alone.This supports contribution-conditioned auxiliary reward allocation as an interpretable approach to complementary coverage among parallel policies in discrete state spaces.

CRediT authorship contribution statement

The CRediT statement assigns distinct research, software, methodology, analysis, visualization, and supervisory contributions across the six authors.

  • CRediT authorship contribution statement: Junhao Cao contributed writing, visualization, validation, software, resources, project administration, and methodology.
  • CRediT authorship contribution statement: Hongyi Xia contributed visualization and funding acquisition, while Jianian Wu contributed data curation and conceptualization.
  • CRediT authorship contribution statement: Xiaopeng Yi contributed software, Lixia Huang contributed methodology and data curation, and Ping Guo contributed supervision, resources, and formal analysis.

Data availability

The study’s data and source code are included in the accompanying review package, with a versioned public archive planned upon acceptance.

  • Data availability: The data and source code supporting the study are included in the accompanying review package.
  • Data availability: A versioned public archive with a DOI will be released upon acceptance.
Loading 2608.27507v1…