Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We address stochastic contextual bandits with an unknown context-lumpable structure, where contexts are partitioned into $r$ blocks with identical arm means within each block. Our algorithm achieves an expected regret of $\widetilde{O}(\sqrt{r(S+K)T})$, matching the known lower bound and improving upon prior upper bounds by a factor of $r$. The approach leverages dyadic accuracy levels, a baseline policy, confidence-based early stopping, and a novel cross-context elimination strategy coupled with multi-scale exploration.
Contextual bandits with lumpable structure can be solved with $r$ times less regret than previously thought possible.
We study stochastic contextual bandits with an unknown context-lumpable structure. The $S$ contexts are partitioned into $r$ blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret $\widetilde{O}(\sqrt{r(S+K)T})$, matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of $r$. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most $r$ selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.