Foundations of Reinforcement Learning XII: E2D Regret Is at Most the Decision-Estimation Coefficient Times T Plus γ·EstSqTextbook
In a structured bandit a learner repeatedly picks a decision from a possibly huge or continuous set and observes a noisy reward with mean , where belongs to a known class of functions . The optimal regret depends on in ways that are hard to predict: optimism (UCB) and posterior sampling…