Contextual Combinatorial Bandits with Post-Serving Contexts

We study contextual combinatorial bandits with post-serving contexts (C${}^2$MAB-PC), where the learner selects $K$ of $m$ base arms using their pre-serving contexts, while additional contexts that also determine the rewards, such as follow-up engagement in slate recommendation, are revealed only after the selected arms are served. We first propose OFUC${}^2$-PC, which is jointly optimistic over the reward parameter and the mean post-serving contexts, and analyze it with a new noisy batched truncated elliptical potential lemma (NBT-EPL). OFUC${}^2$-PC achieves a leading regret of $\tilde{\mathcal{O}}(m^{\alpha }(KT{)}^{1-\alpha }{d}_x^{\alpha }+d_u\sqrt{KT})$, where $\alpha \in (0,1/2]$ is the learnability rate of the post-serving mappings and $d_x$ and $d_u$ are the pre-serving and augmented context dimensions, and a minimax lower bound matches this rate for additive rewards and $\alpha =1/2$. We then propose C${}^2$UCB-PC, an oracle-efficient alternative with the same leading reward-learning term, and variance-aware versions of both algorithms that improve this term from $\tilde{\mathcal{O}}(\sqrt{KT})$ to $\tilde{\mathcal{O}}(\sqrt{T})$ under variance-modulated smoothness. Experiments on synthetic and MovieLens environments show that our algorithms incur lower regret than the baselines and that the oracle-efficient algorithms are $18$–$36\times$ faster than the joint ones.