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

Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear 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.

Proposes a block-level UCB algorithm for latent linear-dynamics bandits with bilinear rewards, using a cyclic finite-memory approximation to achieve Õ(√T) regret versus the prior Õ(T^{2/3}) explore-then-commit bound.

Problem

Endogenous nonstationary bandit where actions drive an unobserved latent linear state and rewards are bilinear in action and state; the goal is low regret against the best open-loop action sequence, previously only Õ(T^{2/3}) achieved.

Approach

Under stable dynamics, truncate the infinite-memory reward to m steps and optimize a cyclic block of length m+L; the truncated block reward is linear in vectorized Markov parameters, so each block becomes a composite arm in a linear UCB problem updated after every block.

Key results

• Theoretical regret bound of Õ(√T) for the block-UCB algorithm (versus Õ(T^{2/3}) for prior ETC) under stable dynamics with open-loop benchmark.
• On synthetic instances with spectral radius 0.95 and 0.3, the proposed method accumulates more cumulative reward than ETC; gap grows over time for rho=0.95.
• Regret constant scales as p^{3/2}/log(1/rho)^{5/4} + p^2/log(1/rho) times sqrt(T).

Limitations

• Assumes exact maximization oracle for block UCB, which is computationally expensive over U^{m+L}.
• Regret is proven for pseudo-regret; translation to actual expected regret incurs an adaptation-gap term and requires stability and known parameters (choice of m, L depends on rho and T).
• Benchmark is an open-loop action sequence rather than feedback policies; experiments are small synthetic instances only.

Experimental setup

Benchmarks: synthetic latent linear-dynamics bandit instances with rho=0.95 and rho=0.3

Metrics: cumulative reward

Baselines: explore-then-commit (Choi et al., 2026) random policy

Builds on: explore-then-commit for latent linear-dynamics bandits (Choi et al., 2026) cyclic block approximation for finite-memory linear bandits self-normalized martingale concentration elliptical potential lemma

Closest papers by meaning

• Generalized Linear Bandits with Memory (ICML 2026 · similarity 0.90)
• An Information-Theoretic Analysis of Nonstationary Bandit Learning (ICML 2023 · similarity 0.90)
• Dynamical Linear Bandits (ICML 2023 · similarity 0.90)
• An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints (NeurIPS 2021 · similarity 0.90)
• Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.89)
• Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.88)