Adaptive Opponent Policy Detection in Multi-Agent MDPs: Real-Time Strategy Switch Identification Using Running Error Estimation

The paper introduces OPS-DeMo, an online algorithm that effectively detects and adapts to changes in opponent policies within multi-agent MDPs, overcoming the limitations of traditional MARL algorithms like PPO in dynamic and non-stationary environments.

Abstract

In Multi-agent Reinforcement Learning (MARL), accurately perceiving opponents' strategies is essential for both cooperative and adversarial contexts, particularly within dynamic environments. While Proximal Policy Optimization (PPO) and related algorithms such as Actor-Critic with Experience Replay (ACER), Trust Region Policy Optimization (TRPO), and Deep Deterministic Policy Gradient (DDPG) perform well in single-agent, stationary environments, they suffer from high variance in MARL due to non-stationary and hidden policies of opponents, leading to diminished reward performance. Additionally, existing methods in MARL face significant challenges, including the need for inter-agent communication, reliance on explicit reward information, high computational demands, and sampling inefficiencies. These issues render them less effective in continuous environments where opponents may abruptly change their policies without prior notice. Against this background, we present OPS-DeMo (Online Policy Switch-Detection Model), an online algorithm that employs dynamic error decay to detect changes in opponents' policies. OPS-DeMo continuously updates its beliefs using an Assumed Opponent Policy (AOP) Bank and selects corresponding responses from a pre-trained Response Policy Bank. Each response policy is trained against consistently strategizing opponents, reducing training uncertainty and enabling the effective use of algorithms like PPO in multi-agent environments. Comparative assessments show that our approach outperforms PPO-trained models in dynamic scenarios like the Predator-Prey setting, providing greater robustness to sudden policy shifts and enabling more informed decision-making through precise opponent policy insights.

Method

The authors used a methodology that involves training response policies against a set of potential opponent policies and then employing an online algorithm to detect changes in the opponent's policy. This algorithm, OPS-DeMo, utilizes a running error estimation metric to assess compliance with a stochastic policy and a dynamic error decay mechanism to prevent error escalation. Upon detecting a policy switch, the algorithm selects the most probable opponent policy and adjusts the response policy accordingly. The approach is designed to operate within resource constraints and process observations on the fly without the need for storage.

Main Finding

The authors discovered that their proposed algorithm, OPS-DeMo, outperforms traditional Proximal Policy Optimization (PPO) models in dynamic scenarios, particularly in the Predator-Prey setting. OPS-DeMo demonstrated greater robustness to sudden policy shifts by opponents, enabling more informed decision-making through precise insights into opponent policies. The authors also found that the strictness factor of the error decay mechanism significantly impacts the model's performance, with higher strictness leading to quicker detection of policy switches but potentially more false positives due to environmental noise.

Conclusion

The paper concludes that the proposed OPS-DeMo algorithm effectively detects policy switches in non-stationary multi-agent environments and outperforms standalone PPO models in terms of mean episodic rewards and consistency. The authors highlight the importance of the strictness factor in the error decay mechanism and its impact on the accuracy of assumed opponent policies. Future work will focus on incorporating continuous learning for more precise opponent policy estimation and developing methods to handle uniform action probability distributions and unforeseen opponent policies.

Keywords

Online Algorithm, Dynamic Environment, Collaborative-Competitive Scenario, Dynamic Decay