Abstract: Interactive learning systems like self-driving cars, recommender systems, and large language model chatbots are becoming increasingly ubiquitous in everyday life. From a machine learning perspective, the key technical challenge underlying such systems is that rather than simple prediction on i.i.d. data, an interactive learner influences the distribution of inputs it sees via the choices [...]