Abstract
High sample complexity remains a barrier to the application of reinforcement learning (RL), particularly in multi-agent systems. A large body of work has demonstrated that exploration mechanisms based on "optimism under uncertainty" can achieve polynomial sample complexity in single-agent and cooperative settings. However, in competitive zero-sum games, standard optimism leads to "cooperative exploration," where agents waste resources exploring states that a rational opponent would never allow them to reach. This paper introduces the concept of strategic efficiency and proposes two algorithms, Strategic ULCB and Strategic Nash-Q, which leverage the adversarial nature of competition to ignore strategically irrelevant states, achieving significantly higher sample efficiency.
Introduction
Standard RL exploration relies on the principle of "Optimism Under Uncertainty" (e.g., UCB). While effective in single-agent environments, this principle falters in two-player zero-sum games. Agents become "optimistic" that their opponent will cooperate to help them reach unknown, high-reward states. This results in "cooperative exploration" in a competitive context, which is strategically inefficient.
Imagine a game where you can choose between a difficult target task and 50 "decoy" tasks. In the decoys, your opponent can end the game in a tie at any moment. A standard optimistic agent will insist on trying to solve all 50 decoys, assuming the opponent might "cooperate" and let them win. In reality, a rational opponent would never do that. The agent wastes millions of samples exploring parts of the game that have no impact on the actual Nash equilibrium.
Methods
The authors define Strategic Efficiency and introduce two algorithms to address this:
- Strategic ULCB (Model-based): This algorithm maintains separate evaluation policies for each player. Instead of solving for a joint optimistic equilibrium, it computes an exploration policy by finding an optimistic best-response against the strongest known adversary strategy. This allows the agent to realize when an unknown state, however promising, can be blocked by an opponent.
- Strategic Nash-Q (Model-free): A version of the strategic principle adapted for Q-learning, which updates value bounds online rather than recomputing a full model every episode.
These methods act similarly to Alpha-Beta pruning in classical game-tree search but are designed for the RL setting where transition dynamics and rewards are initially unknown.
Experimental Results
The algorithms were evaluated on a custom-designed Decoy Task Game and random tree-structured games. The strategic algorithms demonstrated dramatic improvements in sample efficiency. In the Decoy Task Game, the sample complexity for Strategic ULCB and Strategic Nash-Q remained nearly constant regardless of the number of decoys (e.g., 10 vs. 50). In contrast, standard optimistic algorithms saw their sample requirements grow linearly with the number of decoys.
Strategic algorithms quickly learned to focus their episodes on the target task, whereas optimistic baselines remained trapped in decoys. In random tree-structured games, Strategic ULCB also converged to the Nash equilibrium significantly faster than its optimistic counterparts.
Conclusion
The "cooperation trap" in multi-agent RL can be avoided by leveraging the adversarial nature of the game during exploration. By maintaining separate evaluation policies and assuming a rational opponent, agents can ignore strategically irrelevant regions of the state space. Future work includes scaling these principles to deep RL with function approximation and extending the theory to n-player or general-sum games.
Summary updated