The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback Graphs
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Emmanuel Esposito, Federico Fusco, Tomer Koren
cs.LG
Jun 2, 2026 · v2
TL;DR
The paper's mathematical results on minimax regret with switching costs for feedback graphs are formalized in Lean, with a public GitHub repository; the formalization was produced with AI assistance.
Abstract
We study how switching costs affect minimax regret under partial feedback. Which features of the feedback preserve the $\sqrt T$ rate, and which force the $T^{2/3}$ rate? We address this question in the framework of feedback graphs, which interpolate between full information and bandits: playing an action reveals the losses of its out-neighbors in a known directed graph. Prior work on feedback graphs with switching costs gave algorithms with regret of order $T^{2/3}$, but matching lower bounds only for restricted classes of graphs, leaving the question open. We establish a complete characterization of the minimax regret with switching costs for all feedback graphs: $\widetildeΘ(\sqrt T)$ if the graph is strongly revealing, meaning that every pair of distinct actions has an endpoint that observes the losses of both; $\widetildeΘ(γ^{1/3}T^{2/3})$ for every other observable graph, where $γ$ is the domination number; and linear otherwise. In particular, tournaments, in which every action observes its own loss and each pair of actions is joined by one directed edge, sit at the phase transition: they behave like full information, but deleting the edge of any pair forces the rate $T^{2/3}$. Hence an action that observes all losses is neither necessary nor sufficient for the rate $\sqrt T$. Our algorithm TournamentSteering for the strongly revealing case rests on a new principle: each observed comparison of two actions serves both to estimate losses and to steer play, and the loss reduction from steering pays for the variance of the estimates. For every strongly revealing graph, distributing the comparisons among observing actions keeps this variance, and hence the regret, polylogarithmic in the number of actions, by an argument similar to the greedy construction of logarithmic dominating sets in tournaments.
Problem
Open question: which feedback graphs keep the sqrt(T) minimax regret under switching costs, and which force T^{2/3}. Prior work matched lower bounds only for restricted graph classes.
Approach
Introduces the notion of strongly revealing graphs, in which every pair of distinct actions has an endpoint observing both losses. Proposes the TournamentSteering algorithm, which uses each observed comparison both to estimate losses and to steer play, using exponential weights over blocks with slowly switching Markov chains. Proves lower bounds for all other graphs in terms of the domination number. The mathematical results, excluding computational complexity claims, are formalized in Lean.
Results
Gives a complete characterization: Θ (sqrt T) for strongly revealing graphs, Θ (γ^{1/3}T^{2/3}) for other observable graphs, and linear regret otherwise. Tournaments sit exactly at the phase transition.
| Graph class | Minimax regret |
|---|
| Strongly revealing | Θ~(√T) |
| Observable, not strongly revealing | Θ~(γ^{1/3} T^{2/3}) |
| Not observable | linear |
Minimax regret with switching costs by feedback graph class