Understanding the Role of Feedback in Online Learning with Switching Costs

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.