Can I read Adversarial Rewards in Universal Learning for Contextual Bandits on EtoBox?

Adversarial Rewards in Universal Learning for Contextual Bandits by Blanchard, Moise; Hanneke, Steve; Jaillet, Patrick is a scholarly article available to read on EtoBox.

What is Adversarial Rewards in Universal Learning for Contextual Bandits about?

We study the fundamental limits of learning in contextual bandits, where a learner's rewards depend on their actions and a known context, which extends the canonical multi-armed bandit to the case where side-information is available. We are interested in universally consistent algorithms, which achieve sublinear regret compared to any measurable fixed policy, without any function class restriction. For stationary contextual bandits, when the underlying reward mechanism is time-invariant, Blanchard et. al (2022) characterized learnable context processes for which universal consistency is achievable; and further gave algorithms ensuring universal consistency whenever this is achievable, a property known as optimistic universal consistency. It is well understood, however, that reward mechanisms can evolve over time, possibly adversarially, and depending on the learner's actions. We show that optimistic universal learning for contextual bandits with adversarial rewards is impossible in general, contrary to all previously studied settings in online learning -- including standard supervised learning. We also give necessary and sufficient conditions for universal learning under various ad

Author

Blanchard, Moise; Hanneke, Steve; Jaillet, Patrick

Published

2023

Language

EN