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

Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits

ICLR 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear bandits

Read the paperCheck your idea against 108,967 papers

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

Designs batch learning algorithms for linear contextual bandits that achieve near-optimal regret for any batch number, number of actions, horizon, and dimension, establishing the full-parameter-range batch-regret tradeoff.

Problem

Batch linear contextual bandits, where actions must be committed in a small number of batches; the optimal regret as a function of batch number M, actions K, horizon T, and dimension d was previously not established across the full parameter range.

Approach

Designs batch algorithms whose regret matches the optimal batch-regret tradeoff (up to log factors) for all values of M, K, T, and d, thereby closing the full-parameter-range gap for batch linear contextual bandits.

Key results

• Achieves optimal regret bounds (up to logarithmic factors) for any batch number M, number of actions K, time horizon T, and dimension d for batch linear contextual bandits.

Experimental setup

Metrics: regret

Closest papers by meaning

• Optimal Batched Linear Bandits (ICML 2024 · similarity 0.94)
• Optimal and Practical Batched Linear Bandit Algorithm (ICML 2025 · similarity 0.92)
• Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.91)
• Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.89)
• Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.89)
• Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)