EnvSched (arXiv:2610.37609): Environment-Aware Scheduling untuk Rollout-Efficient Agent Reinforcement Learning — Dual-Relation Graph, Prediksi Reward Variance, dan Rekor 48.81 Skor Qwen3-8B pada 40 Langkah GRPO

// Production Implementation: EnvSched Online Scheduler Engine
// Berdasarkan Prinsip Rekayasa arXiv:2610.37609 (PKU, Tsinghua, XJTU, CASIA)
// Mengoptimalkan Rollout Reinforcement Learning (GRPO/PPO) via Dual-Relation Graph

export interface EnvironmentTaskNode {
  id: string;
  envId: string;
  taskPrompt: string;
  tools: string[];
  stateSchema: Record<string, string>;
  verifierType: 'state_diff' | 'exact_match' | 'llm_judge';
  abstractTopology: string; // e.g., 'lookup -> eligibility -> relation_update -> validation'
  
  // Historical rollout statistics
  rolloutCount: number;
  cumulativeExposure: number;
  rewardHistory: number[];
  meanReward: number;
  rewardVariance: number;
  meanCorrectedDispersion: number;
}

export interface DualRelationEdge {
  sourceId: string;
  targetId: string;
  relationType: 'within_env' | 'cross_env';
  weight: number; // Cosine similarity in feature space
}

export class EnvSchedController {
  private readonly nodes: Map<string, EnvironmentTaskNode> = new Map();
  private readonly withinEdges: Map<string, DualRelationEdge[]> = new Map();
  private readonly crossEdges: Map<string, DualRelationEdge[]> = new Map();

  constructor(
    private readonly coverageRatio: number = 0.5, // rho = 0.5 (50% coverage, 50% exploitation)
    private readonly exposureHalfLife: number = 10,  // c_0 discount scale
    private readonly maxBatchPerEnv: number = 4     // Quota per environment in single batch
  ) {}

  public registerNode(node: EnvironmentTaskNode): void {
    this.nodes.set(node.id, {
      ...node,
      rolloutCount: node.rolloutCount || 0,
      cumulativeExposure: node.cumulativeExposure || 0,
      rewardHistory: node.rewardHistory || [],
      meanReward: node.meanReward || 0,
      rewardVariance: node.rewardVariance || 0,
      meanCorrectedDispersion: node.meanCorrectedDispersion || 0,
    });
  }

  public addEdge(edge: DualRelationEdge): void {
    const map = edge.relationType === 'within_env' ? this.withinEdges : this.crossEdges;
    if (!map.has(edge.sourceId)) {
      map.set(edge.sourceId, []);
    }
    map.get(edge.sourceId)!.push(edge);
  }

  /**
   * Mengupdate statistik reward dari hasil rollout batch terkini
   */
  public recordBatchRollouts(batchResults: Array<{ taskId: string; rewards: number[] }>): void {
    for (const res of batchResults) {
      const node = this.nodes.get(res.taskId);
      if (!node) continue;

      node.rolloutCount += res.rewards.length;
      node.cumulativeExposure += 1;
      node.rewardHistory.push(...res.rewards);

      // Hitung mean reward dan variance
      const n = node.rewardHistory.length;
      const mean = node.rewardHistory.reduce((a, b) => a + b, 0) / n;
      const variance = node.rewardHistory.reduce((acc, r) => acc + Math.pow(r - mean, 2), 0) / n;
      
      // Mean-corrected dispersion: d = variance / (mean * (1 - mean) + 1e-5)
      const maxVar = Math.max(1e-5, mean * (1 - mean));
      const dispersion = variance / maxVar;

      node.meanReward = mean;
      node.rewardVariance = variance;
      node.meanCorrectedDispersion = dispersion;
    }
  }

  /**
   * Memprediksi Informativeness (Reward Variance) via Propagasi Dual-Relation Graph
   */
  public predictInformativeness(taskId: string): number {
    const node = this.nodes.get(taskId);
    if (!node) return 0;

    // Jika node memiliki riwayat rollout yang cukup (>= 5), gunakan variance historisnya
    if (node.rolloutCount >= 5) {
      return node.rewardVariance;
    }

    // Jika unobserved atau underobserved, propagasikan estimasi dari tetangga terdekat
    let withinVarianceSum = 0;
    let withinWeightSum = 0;
    const withinNeighbors = this.withinEdges.get(taskId) || [];
    for (const edge of withinNeighbors) {
      const neighbor = this.nodes.get(edge.targetId);
      if (neighbor && neighbor.rolloutCount > 0) {
        withinVarianceSum += neighbor.rewardVariance * edge.weight;
        withinWeightSum += edge.weight;
      }
    }

    let crossVarianceSum = 0;
    let crossWeightSum = 0;
    const crossNeighbors = this.crossEdges.get(taskId) || [];
    for (const edge of crossNeighbors) {
      const neighbor = this.nodes.get(edge.targetId);
      if (neighbor && neighbor.rolloutCount > 0) {
        crossVarianceSum += neighbor.rewardVariance * edge.weight;
        crossWeightSum += edge.weight;
      }
    }

    const withinEstimate = withinWeightSum > 0 ? withinVarianceSum / withinWeightSum : 0.02;
    const crossEstimate = crossWeightSum > 0 ? crossVarianceSum / crossWeightSum : 0.02;

    // Graph Prior: Bobot seimbang antara within-environment dan cross-environment
    const graphPrior = 0.6 * withinEstimate + 0.4 * crossEstimate;

    if (node.rolloutCount === 0) {
      return graphPrior;
    }

    // Fusi antara graph prior dan data lokal yang terbatas
    const alpha = node.rolloutCount / 5;
    return alpha * node.rewardVariance + (1 - alpha) * graphPrior;
  }

  /**
   * Memilih Batch Rollout untuk Iterasi Pelatihan RL Berikutnya
   * Menyeimbangkan Coverage (50%) dan Exploitation Informativeness (50%)
   */
  public sampleBatch(batchSize: number): EnvironmentTaskNode[] {
    const selectedNodes: EnvironmentTaskNode[] = [];
    const envCounts: Map<string, number> = new Map();
    const candidatePool = Array.from(this.nodes.values());

    const numCoverage = Math.floor(batchSize * this.coverageRatio);
    const numExploit = batchSize - numCoverage;

    // 1. Coverage Phase: Prioritaskan environment yang underobserved & task yang jarang dicoba
    candidatePool.sort((a, b) => {
      // Prioritas 1: Lingkungan dengan eksposur kumulatif terkecil
      if (a.cumulativeExposure !== b.cumulativeExposure) {
        return a.cumulativeExposure - b.cumulativeExposure;
      }
      // Prioritas 2: Task dengan rollout count terkecil
      return a.rolloutCount - b.rolloutCount;
    });

    for (const node of candidatePool) {
      if (selectedNodes.length >= numCoverage) break;
      const count = envCounts.get(node.envId) || 0;
      if (count < this.maxBatchPerEnv) {
        selectedNodes.push(node);
        envCounts.set(node.envId, count + 1);
      }
    }

    // 2. Exploitation Phase: Prioritaskan task dengan predicted reward variance tertinggi
    const remainingCandidates = candidatePool.filter(n => !selectedNodes.includes(n));
    remainingCandidates.sort((a, b) => {
      const varA = this.predictInformativeness(a.id);
      const varB = this.predictInformativeness(b.id);
      
      // Terapkan exposure discount factor: (1 + c_{i,t} / c_0)^(-1/2)
      const discountA = Math.pow(1 + a.cumulativeExposure / this.exposureHalfLife, -0.5);
      const discountB = Math.pow(1 + b.cumulativeExposure / this.exposureHalfLife, -0.5);

      return (varB * discountB) - (varA * discountA);
    });

    for (const node of remainingCandidates) {
      if (selectedNodes.length >= batchSize) break;
      const count = envCounts.get(node.envId) || 0;
      if (count < this.maxBatchPerEnv) {
        selectedNodes.push(node);
        envCounts.set(node.envId, count + 1);
      }
    }

    return selectedNodes;
  }
}