Learning to Play Sequential Games versus Unknown Opponents
This work addresses the challenge of interacting with unknown opponents in sequential games, which is incremental as it builds on prior work by extending to unknown opponent models with specific assumptions.
The paper tackles the problem of designing strategies for a learner in repeated sequential games against unknown opponents, using kernel-based regularity assumptions to model opponent responses and proposing a novel algorithm that balances exploration and exploitation. The results include sublinear regret guarantees dependent on opponent regularity and empirical effectiveness in traffic routing and wildlife conservation tasks.
We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We seek to design strategies for the learner to successfully interact with the opponent. While most previous approaches consider known opponent models, we focus on the setting in which the opponent's model is unknown. To this end, we use kernel-based regularity assumptions to capture and exploit the structure in the opponent's response. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. The algorithm combines ideas from bilevel optimization and online learning to effectively balance between exploration (learning about the opponent's model) and exploitation (selecting highly rewarding actions for the learner). Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response and scale sublinearly with the number of game rounds. Moreover, we specialize our approach to repeated Stackelberg games, and empirically demonstrate its effectiveness in a traffic routing and wildlife conservation task