aiqbench analysis
This paper gives a complete characterization of minimax regret under switching costs for online learning with feedback graphs. Regret is $\sqrt{T}$ for strongly revealing graphs and $T^{2/3}$ for other observable ones, which shows that observing all losses is neither necessary nor sufficient for the faster rate. For ML practitioners, the useful result is the boundary: when partial feedback can be exploited without raising the rate, and when switching costs force a slower one. The results are theoretical and the 70-page version's full proofs are not yet verified here.
The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback Graphs
arXiv:2606.03851v2 Announce Type: replace 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\Theta(\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\Theta(\gamma^{1/3}T^{2/3})$ for every other observable graph, where $\gamma$ 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.
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\Theta(\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\Theta(\gamma^{1/3}T^{2/3})$ for every other observable graph, where $\gamma$ 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.
70 pages. Substantially expanded version: extends the two-action apple-tasting result to a complete characterization for all feedback graphs. Title and author list updated. Accompanying Lean formalization covers the mathematical results, excluding computational complexity claims
Machine Learning (cs.LG)
arXiv:2606.03851 [cs.LG]
(or arXiv:2606.03851v2 [cs.LG] for this version)
Full text under the publisher's open licence · 326 words
Related coverage
Quantum Vector Light Cuts Particle Heating Rate in Optical Tweezers
Quantum Zeitgeist · Jul 30, 2026
When Does Synergy Help Active Feature Acquisition? A PID-Based Study
arXiv · Sep 30, 2026
Probing Quantum Information Scrambling via Local Randomized Measurements
arXiv · Aug 21, 2026
Task-Oriented Sensing and Covert Transmissions for Collaborative Multi-AUV Systems
arXiv · Oct 21, 2026