# Understanding the Role of Feedback in Online Learning with Switching Costs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 16 Jun 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [Online learning with graph-structured feedback against adaptive adversaries](https://mlsanity.com/paper/1804.00335/) (2018)

## Built on by (most cited first, 4 of 4)

- [Online Learning with Sublinear Best-Action Queries](https://mlsanity.com/paper/2407.16355/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Hybrid Feedback-Guided Optimal Learning for Wireless Interactive Panoramic Scene Delivery](https://mlsanity.com/paper/2602.07273/) (2026)
- [Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees](https://mlsanity.com/paper/2610.14790/) (2026)

## Abstract (arXiv)

In this paper, we study the role of feedback in online learning with switching costs. It has been shown that the minimax regret is widetildeTheta(T2/3) under bandit feedback and improves to widetildeTheta(√T) under full-information feedback, where T is the length of the time horizon. However, it remains largely unknown how the amount and type of feedback generally impact regret. To this end, we first consider the setting of bandit learning with extra observations; that is, in addition to the typical bandit feedback, the learner can freely make a total of Bex extra observations. We fully characterize the minimax regret in this setting, which exhibits an interesting phase-transition phenomenon: when Bex = O(T2/3), the regret remains widetildeTheta(T2/3), but when Bex = Omega(T2/3), it becomes widetildeTheta(T/√Bex), which improves as the budget Bex increases. To design algorithms that can achieve the minimax regret, it is instructive to consider a more general setting where the learner has a budget of B total observations. We fully characterize the minimax regret in this setting as well and show that it is widetildeTheta(T/√B), which scales smoothly with the total budget B. Furthermore, we propose a generic algorithmic framework, which enables us to design different learning algorithms that can achieve matching upper bounds for both settings based on the amount and type of feedback. One interesting finding is that while bandit feedback can still guarantee optimal regret when the budget is relatively limited, it no longer suffices to achieve optimal regret when the budget is relatively large.