Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

The reduction from an infinite-memory nonstationary problem to a stationary block-level linear-bandit proxy is elegant and correctly backed by the geometric truncation error bound in Equation (3). The authors carefully decompose the block reward into linear signal, current-block noise, action-tail bias, and process-noise tail (Lemma 2), identifying that pre-block process noise can be correlated with the adaptively chosen block. Their resolution via a uniform high-probability bound on the noise tail (Lemma 7) enables valid confidence sets under block adaptivity, which is the key technical step lifting the analysis beyond the prior ETC result. The regret scaling of $\widetilde{\mathcal{O}}(\sqrt{T})$ is a meaningful improvement for this model. The concentration argument also builds on classic self-normalized martingale bounds for linear bandits.

The biggest practical limitation is the exact-maximization oracle assumed for block selection. The UCB objective is nonconcave over the composite action space $\mathcal{U}^{m+L}$, so the algorithm as written may be computationally intractable, and the paper does not quantify the effect of approximate maximization on regret. As noted: "our theoretical analysis assumes access to an exact maximization oracle" (Remark 2).\nSecond, the theoretically optimal tuning $m = -\frac{1}{2}\log_{\rho} T$ requires knowledge of the stability constant $\rho$, and $L = \sqrt{mT}/d^{3/4} - m$ requires knowledge of the horizon $T$ and dimension. Without a parameter-free or adaptive tuning scheme, the guarantee is not fully operational when $\rho$ is unknown.\nThird, the confidence radius $\gamma_{\tau}$ incorporates a uniform bound with $\log(2\cdot 5^{p}T/\delta)$, implying a linear-in-$p$ penalty inside the noise tail that is not discussed explicitly. This hidden dimension dependence weakens the bound for moderate action dimension.

The authors fairly contrast their model with exogenous nonstationary bandits, finite-memory bandits, dynamical linear bandits, and the earlier ETC approach. The experiments compare Block-OFUL against the ETC baseline on two synthetic instances ($\rho(\mathbf{A})=0.95$ and $0.3$). While Block-OFUL consistently outperforms ETC, the experiment is limited to small latent state ($n=4$) and action ($p=3$) dimensions, a single exploratory horizon $H$ for ETC, and no sensitivity analysis for $m$ and $L$. As reported: "Across both stability regimes, Block-OFUL consistently accumulates reward faster than ETC, while the random baseline remains close to zero." The claim of favorable empirical performance rests on one baseline and two parameter settings; stronger empirical diagnostics would strengthen the evidence.

The paper does not mention a code repository. Although the experimental hyperparameters are specified for the two tested instances, reproducing the results would require implementing the exact block-UCB maximization oracle, which is left ill-defined. The algorithm also depends on setting $m$ and $L$ via the true unknown $\rho$, raising a barrier for independent reproduction. To make the work reproducible, the authors should release code and either provide a computationally tractable approximate oracle with corresponding regret guarantees or describe a parameter-free tuning procedure. While the exact oracle is standard in some bandit literature, it is particularly restrictive here because the composite action space grows with the chosen memory length $m$.