Research map / Bandits and online learning / Contextual bandits and Thompson sampling

High Probability Bound for Cross-Learning Contextual Bandits with Unknown Context Distributions

ICML 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Re-analyzes the epoch-based EXP3-type cross-learning bandit algorithm of Schneider and Zimmert (2023) and proves it attains near-optimal Õ(√(KT log(1/δ))) regret with high probability when contexts are i.i.d. from an unknown distribution.

Problem

Contextual bandits with cross-learning, adversarial losses and i.i.d. contexts from an unknown distribution; prior analysis only bounded expected regret, leaving open whether high-probability near-optimal regret holds.

Approach

Exploits weak dependence between epochs of the existing algorithm, rearranges the regret decomposition (keeping a bias term that gives a negative drift), and uses an indicator-truncated surrogate sequence with refined Freedman-type martingale inequalities to convert the expected bound into a high-probability one.

Key results

• Shows the Schneider and Zimmert (2023) algorithm achieves Õ(√(KT log(1/δ))) regret with probability at least 1-δ for any policy π.
• Parameter choice L = Θ̃(√(KT log(1/δ))), γ = Θ̃(√(log(1/δ)/(KT))), η = Θ̃(1/√(KT log(1/δ))) yields the high-probability bound.

Measured effects reported in the paper

Surprising findings

• The original analysis of Schneider and Zimmert (2023) has a small flaw: it assumes conditional independence between the indicator G and the bias term, which the authors correct by using F_e instead.

Limitations

• Results are purely theoretical with no empirical evaluation.
• Relies on an oblivious adversary and i.i.d. contexts from a fixed distribution.
• Analysis is specific to the epoch structure of the prior algorithm; the technique's transfer to other multi-epoch algorithms is untested.

Experimental setup

Metrics: regret

Baselines: Schneider and Zimmert (2023)

Builds on: Schneider and Zimmert (2023) EXP3-IX Freedman's inequality Azuma-Hoeffding inequality

Closest papers by meaning

• Optimal cross-learning for contextual bandits with unknown context distributions (NeurIPS 2023 · similarity 0.96)
• Contextual Bandits with Cross-Learning (NeurIPS 2019 · similarity 0.93)
• Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.91)
• Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.90)
• Mixed-Effects Contextual Bandits (AAAI 2024 · similarity 0.90)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)