Reproduce “The Pareto Frontier of model selection for general Contextual Bandits” on OpenResearch

About this paper

Teodor V. Marinov, Julian Zimmert

Google Research's Teodor Marinov and Julian Zimmert characterize the fundamental limits of model selection in general contextual bandits by establishing a tight Pareto frontier for regret bounds. The work demonstrates that simultaneous, universally optimal regret guarantees over a nested sequence of policy classes are largely unobtainable, directly resolving an open problem posed at COLT 2020.

Key insights

• There is no single algorithm that can simultaneously achieve optimal regret guarantees across all nested policy classes in general contextual bandits; an inherent trade-off exists between adapting to model complexity and achieving low regret with respect to the time horizon.
• Adaptive adversaries can force algorithms to incur higher regret, demonstrating that adapting to the number of optimal policy switches (S-switch problem) is fundamentally impossible in certain settings.
• In stochastic environments, the lack of information gained from certain actions can make it impossible to distinguish between different environments, leading to fundamental limits on regret even for proper and improper algorithms.

Summary by alphaXiv.