A central problem in online learning and decision making—from bandits to reinforcement learning—is to understand whatmodeling assumptions lead to sample-efficient learning guarantees. With a focus on stochastic environments, a recent line of research provides general structural conditions under which sample-efficient learning is possible, but robust learning guarantees for agnostic or adversarial settings have remained elusive. We consider a general adversarial decision making framework that enc…