Tracking the Best Strategy in an Extensive-Form Game
Not on the map. Why?
Abstract (arXiv)
We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter ρ>0 and achieves a switching regret of tildeO((1/ρ+ρ K)√H A T) where K is the number of switches in the comparator sequence, H is the maximum number of the learner's information sets that can be traversed during a play of the game and A is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only O(H B) where B is the maximum number of actions available to the learner at any of its information sets.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 12 of its 19 references that are in the map. First posted on arXiv 10 Aug 2026.
Builds on
12 of 19 references.
References · 12
- 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
- 2023High-Dimensional Prediction for Sequential Decision Makingcited by 41
- 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
- 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
- 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
- 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
- 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
- 2021Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibriacited by 13
- 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
- 2023Nearest Neighbour with Bandit Feedbackcited by 5
- 2025Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversariescited by 5
- 2026Differential Privacy in the Extensive-Form Bandit Problemcited by 1
Built on by
Not cited yet.