Abstract
In many real-world multi-agent systems, agents must learn to optimize their strategies in repeated games where the underlying reward functions are unknown. This paper introduces GP-MW, a novel algorithm that bridges the gap between full-information and bandit feedback models. By combining Gaussian Processes (GPs) with the Multiplicative Weights (MW) update rule, GP-MW exploits correlations between payoffs to achieve low regret. We demonstrate the effectiveness of GP-MW across synthetic benchmarks, traffic routing simulations, and movie recommendation tasks, showing it significantly outperforms standard bandit algorithms and matches full-information performance.
Introduction
In environments like traffic networks or financial markets, agents often lack complete knowledge of the game's rules. Traditional learning approaches typically assume either "full information"—where rewards for all possible actions are known—or "bandit feedback"—where only the reward for the chosen action is observed. While the former allows for rapid convergence, it is often unrealistic; the latter is realistic but suffers from slow learning rates that scale poorly with the number of actions.
This work identifies a practical "middle ground": agents observe their own rewards and the actions taken by their opponents. By assuming the reward function is mathematically "smooth," agents can use Gaussian Processes to infer rewards for actions they did not take, effectively simulating a full-information environment.
The GP-MW Algorithm
The core contribution is the GP-MW algorithm, which integrates two powerful frameworks:
- Gaussian Processes (GPs): Used to model the unknown reward function. Given the history of actions and rewards, the GP provides a posterior distribution over the reward landscape.
- Multiplicative Weights (MW): A classic no-regret framework for strategy updates.
GP-MW uses the Upper Confidence Bound (UCB) from the GP as a proxy for the true reward. This optimistic estimate allows the MW component to update its strategy as if it had full-information feedback. This approach is particularly effective when payoffs are correlated (e.g., similar routes in a traffic network), allowing the agent to learn about many actions from a single observation.
Experimental Results
The authors evaluated GP-MW in three primary settings: synthetic matrix games, the Sioux Falls traffic network, and the MovieLens-100K dataset.
Performance and Robustness
In the MovieLens task and synthetic benchmarks, GP-MW demonstrated remarkable robustness. While standard Bayesian optimization tools often fail when opponents act strategically, GP-MW maintains a "no-regret" property, performing significantly better than bandit baselines like Exp3.P and approaching the performance of full-information algorithms like Hedge.
Traffic Network Efficiency
In the Sioux Falls traffic simulation (24 nodes, 528 agents), GP-MW significantly reduced both individual agent regret and overall network congestion compared to standard bandit algorithms like EXP3 and reinforcement learning baselines like Q-BRI. The algorithm's performance scales well with the number of learning agents, maintaining low final regret and congestion.
Key Insights
- Exploiting Correlations: GP-MW is the first algorithm to rigorously use payoff correlations to reduce regret in game-theoretic settings. It achieves a regret bound that depends only logarithmically on the number of actions ($log K$).
- Kernel Flexibility: The choice of GP kernel allows the model to adapt to various game structures, such as linear or polynomial dependencies on opponent actions.
Conclusion and Future Work
GP-MW provides a powerful framework for learning in unknown games by leveraging reward smoothness. While highly effective, the cubic computational complexity of GPs remains a challenge for long-duration games. Future research could investigate sparse GP approximations or more efficient ways to handle high-dimensional continuous action spaces.
Summary updated