Adaptive Regret Minimization in Bounded-Memory Games
From MaRDI portal
Abstract: Online learning algorithms that minimize regret provide strong guarantees in situations that involve repeatedly making decisions in an uncertain environment, e.g. a driver deciding what route to drive to work every day. While regret minimization has been extensively studied in repeated games, we study regret minimization for a richer class of games called bounded memory games. In each round of a two-player bounded memory-m game, both players simultaneously play an action, observe an outcome and receive a reward. The reward may depend on the last m outcomes as well as the actions of the players in the current round. The standard notion of regret for repeated games is no longer suitable because actions and rewards can depend on the history of play. To account for this generality, we introduce the notion of k-adaptive regret, which compares the reward obtained by playing actions prescribed by the algorithm against a hypothetical k-adaptive adversary with the reward obtained by the best expert in hindsight against the same adversary. Roughly, a hypothetical k-adaptive adversary adapts her strategy to the defender's actions exactly as the real adversary would within each window of k rounds. Our definition is parametrized by a set of experts, which can include both fixed and adaptive defender strategies. We investigate the inherent complexity of and design algorithms for adaptive regret minimization in bounded memory games of perfect and imperfect information. We prove a hardness result showing that, with imperfect information, any k-adaptive regret minimizing algorithm (with fixed strategies as experts) must be inefficient unless NP=RP even when playing against an oblivious adversary. In contrast, for bounded memory games of perfect and imperfect information we present approximate 0-adaptive regret minimization algorithms against an oblivious adversary running in time n^{O(1)}.
Recommendations
- scientific article; zbMATH DE number 1944045
- scientific article; zbMATH DE number 1804100
- Learning in games with bounded memory
- Learning with bounded memory in games
- Minimizing regret in discounted-sum games
- Iterated regret minimization in game graphs
- A closer look at adaptive regret
- A closer look at adaptive regret
- Adaptive learning in extensive form games and sequential equilibrium
- Optimal strategies for adaptive zero-sum average Markov games
Cited in
(3)
This page was built for publication: Adaptive Regret Minimization in Bounded-Memory Games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3190039)
