Towards Understanding the Role of Feedback in Online Learning

Online learning provides a simple yet powerful way to model sequential decision-making under uncertainty. The process repeats: make a choice, observe feedback, and update strategy. This cycle appears in many areas - from recommendation system, to reconfiguring resources in large networks, to managing financial portfolios. One thing that determines the effectiveness of learning is the feedback the learner receives. Feedback comes in many forms. In the bandit setting, only the outcome of the chosen action is revealed. In the fullinformation setting, the outcomes of all actions are visible. In practice, feedback can also be partial, noisy, delayed, or heavy-tailed. Each variation fundamentally changes what the learner can achieve.