Assistive Dueling Bandits: No-Regret Algorithms for Assisting No-Regret Users

We study a stochastic bandit problem in which learning is split between two agents. In each round, a human observes rewards but can choose only between a pair of arms selected by an assistant, while the assistant observes the human's behavior but not realized rewards. We call this model the **assistive dueling bandit**. The human is modeled as a learning agent whose regret on any subset of arms is bounded by a function $g(T)$ unknown to the assistant. This is a natural model for recommender systems or AI assistants that must present a slate of options to a user who may be still learning about their own preferences. We provide a general reduction from assistive dueling bandits to the problem of **max-finding with imprecise feedback.** With it, we design assistant algorithms that cooperate with any $g(T)$-regret human to achieve a joint regret of $\tilde{\mathcal{O}}(K \cdot g(T/K))$, even without knowledge of $g(T)$. Crucially, when $g(T) \in \mathcal{O}(\sqrt{T})$, our method recovers the nearly optimal minimax rate of $\tilde{\mathcal{O}}(\sqrt{KT})$, implying that splitting up the responsibilities of learning in this way can be done without suffering any excess regret asymptotically. We complement our theoretical analysis with experimental evidence that this algorithm outperforms an assistant implemented via standard dueling bandit algorithms.