# Tracking the Best Strategy in an Extensive-Form Game

arXiv: https://arxiv.org/abs/2608.09501 · HTML: https://mlsanity.com/paper/2608.09501/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 19 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 12 of 12)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [Stochastic Regret Minimization in Extensive-Form Games](https://mlsanity.com/paper/2002.08493/) (2020)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries](https://mlsanity.com/paper/2504.00461/) (2025)
- [Nearest Neighbour with Bandit Feedback](https://mlsanity.com/paper/2306.13773/) (2023)
- [Differential Privacy in the Extensive-Form Bandit Problem](https://mlsanity.com/paper/2605.05266/) (2026)

## 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.