Counterfactual Conditional Likelihood Rewards for Multiagent Exploration

1. Problem Statement

The paper addresses the critical challenge of efficient exploration in cooperative multiagent systems, particularly in environments with sparse global rewards (e.g., search and rescue, planetary surveying).

• The Core Issue: In sparse reward settings, agents receive feedback only when a specific team-level goal is achieved. Standard exploration methods often rely on local observation entropy maximization (encouraging agents to visit diverse local states).
• The Limitation: Local exploration leads to redundancy. Agents explore independently without awareness of teammates, often clustering in the same areas or failing to discover the specific coordinated behaviors required to trigger the sparse global reward.
• The Technical Hurdle: Directly estimating joint state entropy is computationally intractable due to the combinatorial explosion of the joint observation space and the non-stationarity caused by concurrently learning agents (which destabilizes density estimators).

2. Methodology: Counterfactual Conditional Likelihood (CCL)

The authors propose a novel intrinsic reward mechanism called Counterfactual Conditional Likelihood (CCL) to promote coordinated exploration without requiring a learned joint embedding network.

Key Concept

CCL quantifies an agent's unique informational contribution to the team's joint observation. It rewards an agent not just for seeing something new, but for seeing something that changes the likelihood of the team's joint observation compared to a scenario where the agent was inactive or static.

Technical Implementation

1. Random Encoders: Instead of training a complex joint embedding network (which is unstable), the system uses fixed random encoders ($\phi$) to map each agent's local observation ($o^i_t$) into a low-dimensional vector ($z^i_t$).
2. Joint Embedding: The team's joint state is represented by concatenating these local embeddings: $z_t = [z^1_t, \dots, z^N_t]$.
3. Counterfactual Construction: For each agent $i$, a counterfactual joint embedding $\tilde{z}^{(i)}_t$ is created by replacing the agent's current embedding $z^i_t$ with its embedding from the previous timestep ($\tilde{z}^i_t = \phi(o^i_{t-1}$). This simulates the agent "doing nothing" or staying static while the rest of the team moves.
4. Likelihood Estimation via k-NN:
   • The system maintains an episodic memory $M$ of past joint embeddings.
   • It calculates the distance from the actual joint embedding ($z_t$) and the counterfactual joint embedding ($\tilde{z}^{(i)}_t$) to their $k$-nearest neighbors in $M$.
   • To ensure stability, a shared radius ($\epsilon_{shared} = \max(\epsilon_{act}, \epsilon_{cfact})$) is used for both estimates (inspired by KSG estimators).
5. Reward Calculation:
   The CCL reward is the difference in the conditional log-likelihoods, approximated using the digamma function ($\psi$) of the neighbor counts ($n_{act}$ and $n_{cfact}$):
   $$r^{CCL}_i = \psi(n_{act} + 1) - \psi(n_{cfact} + 1)$$
   • If the agent's actual observation makes the joint state more likely (more neighbors) than the counterfactual, the reward is positive.
   • Stabilization: The raw reward is passed through a Softplus function and clamped (max 5.0) to ensure non-negativity and prevent gradient explosions.

Hybrid Approach (Mixture Rewards)

The authors also propose a Mixture Reward strategy that combines CCL with Local Observation Entropy Maximization (OEM):
$$r^{mix}_t = r_{team} + V(s_t) \cdot (r^{CCL}_i + \alpha \cdot r^{Local}_{OEM})$$
This allows agents to maintain local diversity (via OEM) while being guided toward coordinated joint exploration (via CCL).

3. Key Contributions

1. Novel Reward Function: Introduction of CCL, which isolates an agent's marginal contribution to joint exploration using counterfactual reasoning, avoiding the need for unstable joint density estimators.
2. Scalability: By using fixed random encoders and local k-NN density estimation, the method scales to high-dimensional and partially observable multiagent settings where traditional joint entropy methods fail.
3. Coordination Awareness: Unlike standard novelty rewards that encourage individual diversity, CCL explicitly incentivizes behaviors that are informative with respect to the team, reducing redundant exploration.
4. Empirical Validation: Comprehensive experiments demonstrating that CCL outperforms local entropy maximization in sparse, tightly coupled tasks.

4. Experimental Results

The authors evaluated CCL in two primary domains: Multi-Rover Exploration (continuous, sparse rewards) and Particle Environments (partially observable, adversarial settings).

• Sparse Reward Domains (Multi-Rover):

  • Single POI (Point of Interest): In the hardest scenario (1 POI, high coupling factor), agents using Local Entropy failed completely (receiving zero reward) because they could not coordinate. CCL agents successfully discovered coordinated strategies to observe the POI.
  • Redundancy Reduction: Heat maps showed that Local Entropy agents clustered in the same areas, while CCL agents distributed themselves to cover the environment complementarily.
  • Scaling: CCL performance gains were most pronounced as the number of agents and coupling factors increased.

• Particle Environments (Adversarial):

  • In tasks like Physical Deception, Keep Away, and Predator-Prey, CCL consistently outperformed Local Entropy agents in terms of team reward and coordination quality.
  • CCL agents learned to block adversaries or capture prey more effectively than those relying solely on local novelty.

• Mixture Rewards:

  • Combining CCL with Local Entropy (Mixture) often yielded the fastest convergence and highest peak performance in moderately complex tasks.
  • However, in extremely sparse/highly coupled tasks (e.g., Single POI), pure CCL was superior, suggesting that local diversity can sometimes distract from the critical coordination needed.

5. Significance and Conclusion

• Bridging Local and Global: CCL provides a principled way to bridge the gap between local novelty incentives and global coordination requirements in Multi-Agent Reinforcement Learning (MARL).
• Solving the Credit Assignment Problem: By rewarding agents based on their unique contribution to the joint likelihood, CCL effectively solves the credit assignment problem in sparse reward settings without needing explicit communication or centralized policies during execution.
• Future Directions: The authors note that as team size grows, particle-based density estimators (k-NN) may degrade in accuracy. Future work could integrate model-based exploration strategies to address this limitation.

In summary, this paper presents a robust, scalable solution for multiagent exploration that moves beyond individual curiosity to foster coordinated, complementary behaviors, significantly accelerating learning in sparse and complex cooperative environments.