Context-lumpable bandits skip partition recovery: online regret now matches the lower bound up to log factors

Online expected regret for context-lumpable bandits is brought to within logarithmic factors of the known lower bound, for arbitrary block and context distributions. The earlier online upper bound of Lee et al. 2023 carried an extra factor, because its algorithm refined a context partition while eliminating arms and had to ensure refinements never split a true block. The rate matches the lower bound of Lee et al. 2023 up to logarithmic factors and removes that extra factor; Algorithm 4 attains it for a known horizon, and a standard doubling restart gives the same order without knowing the horizon.

The algorithm does not first recover the unknown context partition; it builds a shared set of candidate arms containing a sufficiently good arm for every block, then selects among those candidates separately at each context. Sharing observations across contexts previously required finding the block partition first, and keeping refinements from splitting a true block carried an extra cost. The guarantee holds without any positive separation between the mean-reward vectors of distinct blocks, and no restriction is imposed on the block distribution.

Exploration runs in phases over dyadic accuracy levels, first estimating the preceding policy at every context as a baseline, then stopping sampling early on a confidence bound. Running a separate bandit for each context gives regret linear in the number of contexts, while exploring across contexts itself incurs regret because an informative arm may be poor where it is sampled. On the joint concentration event, every arm stopped early is worse than the preceding policy by a constant multiple of the target accuracy, whereas every arm that completes its budget has an estimate at that accuracy.

Cross-context elimination uses the fact that mean rewards are identical within a block: selecting one arm deletes all surviving records from that block, so at most a bounded number of selections is needed at each level. The block partition is never identified, yet the elimination step still empties whole blocks of records. 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.

The report covers an online expected-regret result for context-lumpable stochastic bandits: contexts are partitioned into unknown blocks, every arm has the same mean reward across contexts in a block, and the learner sees context identities without their block assignments. It is aimed at readers working on bandits, online learning, and low-rank structure, and it applies to arbitrary block and context distributions without requiring positive separation between the reward vectors of different blocks. The authors propose extending the approach to general lumpable Markov decision processes, where transitions may depend on state and action.

The guarantee is stated as expected regret and hides polylogarithmic factors in the number of contexts, arms, blocks, and the horizon. Algorithm 4 attains it for a known horizon, while a standard doubling restart gives the same order without knowing the horizon. For arbitrary context distributions, contexts are first grouped by estimated arrival probabilities and the procedure runs separately within each retained group, with probability at least a stated level that each group's conditional context distribution meets the approximately uniform assumptions, while the remaining low-frequency contexts carry total probability at most a stated small amount.