  The growing interest in complex decision-making and language modeling
problems highlights the importance of sample-efficient learning over very long
horizons. This work takes a step in this direction by investigating contextual
linear bandits where the current reward depends on at most $s$ prior actions
and contexts (not necessarily consecutive), up to a time horizon of $h$. In
order to avoid polynomial dependence on $h$, we propose new algorithms that
leverage sparsity to discover the dependence pattern and arm parameters
jointly. We consider both the data-poor ($T<h$) and data-rich ($T\ge h$)
regimes, and derive respective regret upper bounds $\tilde O(d\sqrt{sT} +\min\{
q, T\})$ and $\tilde O(\sqrt{sdT})$, with sparsity $s$, feature dimension $d$,
total time horizon $T$, and $q$ that is adaptive to the reward dependence
pattern. Complementing upper bounds, we also show that learning over a single
trajectory brings inherent challenges: While the dependence pattern and arm
parameters form a rank-1 matrix, circulant matrices are not isometric over
rank-1 manifolds and sample complexity indeed benefits from the sparse reward
dependence structure. Our results necessitate a new analysis to address
long-range temporal dependencies across data and avoid polynomial dependence on
the reward horizon $h$. Specifically, we utilize connections to the restricted
isometry property of circulant matrices formed by dependent sub-Gaussian
vectors and establish new guarantees that are also of independent interest.
