Tracking Most Significant Shifts in Nonparametric Contextual Bandits
Authors: Joe Suk, Samory Kpotufe
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study nonparametric contextual bandits where Lipschitz mean reward functions may change over time. We first establish the minimax dynamic regret rate in this less understood setting in terms of number of changes L and total-variation V , both capturing all changes in distribution over context space, and argue that state-of-the-art procedures are suboptimal in this setting. Next, we tend to the question of an adaptivity for this setting, i.e. achieving the minimax rate without knowledge of L or V. ... As a first result for this nonparametric setting, we establish some minimax lower-bounds as a baseline in terms of either L or V , and argue that state-of-the-art procedures for the parametric case extended to the class of Lipschitz functions do not achieve these baselines. ... Our main result is to show that this more tolerant notion of change can in fact be adapted to. |
| Researcher Affiliation | Academia | Joe Suk Columbia University joe.suk@columbia.edu Samory Kpotufe Columbia University samory@columbia.edu |
| Pseudocode | Yes | Algorithm 1: Contextual Meta-Elimination while Tracking Arms (CMETA) and Algorithm 2: Base-Alg(tstart, m0): Adaptively Binned Elimination with randomized arm-pulls |
| Open Source Code | No | No explicit statement about open-source code release or links to code repositories found. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, thus no training dataset is specified or made available. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on datasets, thus no validation dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and presents algorithms but does not specify software dependencies with version numbers for implementation or experiments. |
| Experiment Setup | No | The paper is theoretical and does not report on specific experimental setup details or hyperparameters. |