docs/reward_design_notes.md

Reward Design Notes

This environment uses a composite reward that adapts ideas from:

• AutoGraph-R1 (arXiv:2510.15339)
• UniRel (arXiv:2512.17043)
• DeepPath (EMNLP 2017, D17-1060)
• Multi-Hop KG Reasoning with Reward Shaping (EMNLP 2018, D18-1362)
• Kimi K2.5 (arXiv:2602.02276) for PARL-style swarm auxiliary shaping

Additional related context consulted:

• MINERVA (arXiv:1711.05851) for query-conditioned walk-style reasoning over KG paths.

Components in this Branch

The implementation follows a staged reward design:

1. edge-level rewards during graph construction (ADD_EDGE)
2. answer-level rewards for retrieval usefulness and final task utility (ANSWER)
3. evaluation-level composite leaderboard score for benchmark ranking

1) Edge addition reward

For each ADD_EDGE, the reward combines:

• Global accuracy term (DeepPath):
  • $r_{global} = +1$ if a candidate edge is correct, else $-1$ (scaled in code for stability).
• Soft shaping term (D18 reward shaping):
  • $R = R_b + (1 - R_b) f(s, r, o)$, where $f$ is a soft fact plausibility score.
  • In code, $f$ is approximated by relation/type priors plus small domain priors.
• Efficiency term (DeepPath):
  • $r_{efficiency} \propto 1 / \text{step_count}$.
• Diversity term (DeepPath):
  • novelty from cosine dissimilarity of edge signatures; repeated patterns are down-weighted.
• Relation/entity informativeness (UniRel):
  • relation rarity via normalized IDF of relation labels,
  • entity informativeness via inverse hub-penalty.
• Connectivity gain term:
  • rewards bridge edges that connect previously disconnected graph regions.

2) Final answer reward

For ANSWER, the reward combines:

• format validity,
• answer correctness,
• knowledge-carrying utility (AutoGraph-R1 style):
  • $R_C(q, y, G) = \mathbb{{I}}[\text{{deducible}}(q, y \mid G)]$.
• knowledge-indexing utility (AutoGraph-R1 style):
  • $R_I(q, D_{{gold}}, G) = |Top\text{{-}}k(G,q) \cap D_{{gold}}| / |D_{{gold}}|$,
  • approximated in this environment with evidence recall over tool outputs.
• connectivity (UniRel style):
  • discrete connectivity reward over extracted seed entities, normalized for stable mixing.
• graph F1 against supporting edges,
• compactness penalty for unnecessary extra edges,
• efficiency bonus,
• relation/entity informativeness for the constructed subgraph,
• repetition penalty to discourage redundant relation generation patterns.

UniRel-style aggregate view represented in this branch:

$$R(a)\approx R_{fmt}+R_{con}+w_1{R}_{ent}+w_2{R}_{rel}+\text{task utility terms}R(a)\; \backslash approx\; R\_\{\{fmt\}\}\; +\; R\_\{\{con\}\}\; +\; w\_1\; R\_\{\{ent\}\}\; +\; w\_2\; R\_\{\{rel\}\}\; +\; \backslash text\{\{task\; utility\; terms\}\}$$

with task utility terms coming from AutoGraph-inspired $R_C$ and $R_I$ components.

Telemetry

Per-step component rewards are aggregated into info["reward_components"], enabling:

• richer benchmark summaries,
• leaderboard ranking by composite utility,
• visual diagnostics in dashboard exports.

Evaluation also computes derived retrieval and structural utility signals used in leaderboard ranking.

Future Multi-Agent Notes

This branch now includes a low-width swarm baseline orchestrator that adds PARL-style auxiliary shaping on top of the core edge and answer rewards.

The helper implementation is in:

• src/osint_env/env/spawn_reward_hooks.py

It follows the Kimi K2.5 style decomposition:

• $r_{{PARL}}(x,y) = r_{{perf}}(x,y) + \lambda_1 r_{{parallel}} + \lambda_2 r_{{finish}}$,
• optional critical-steps shaping for latency-sensitive training,
• optional annealing of $\lambda_1, \lambda_2$ toward zero,
• optional breadth/depth shaping hooks for future branch integration.

The expanded project-level walkthrough is in README.md under "Reward Design (Integrated Notes)".