When Can Pure Exploitation Succeed in Linear RL? Decoys and Self-Identifiability for Greedy LSVI

Manoj Saravanan; Rohit Kumar Salla

We study online episodic reinforcement learning in finite-horizon Markov decision processes with a finite action set, known features, bounded rewards, and linear Bellman completeness. We focus on Greedy-LSVI, which performs stage-wise ridge regression on Bellman targets followed by deterministic greedy action selection, with no optimism or randomization. We identify a precise information-theoretic obstruction to exploration-free learning: a decoy, namely an alternative environment in the same model class that induces the same trajectory law under a greedy-representable policy $\pi$ while making $\pi$ globally optimal, even though $\pi$ is suboptimal in the true environment. We call an instance self-identifiable if no suboptimal greedy-representable policy admits a decoy. Our main result shows that, up to a mild model-class closure assumption, decoys are equivalent to the existence of an on-policy covariance null direction that is still action-sensitive on states visited by $\pi$. This yields a dichotomy for Greedy-LSVI: decoys permit linear-regret instances, whereas under self-identifiability and additional bounded-parameter and leverage conditions, Greedy-LSVI achieves $\widetilde{O}(\sqrt{K})$ regret over $K$ episodes and, under a witnessed-margin condition, $\widetilde{O}(\log K)$ regret. We also construct a self-identifiable instance with rank-deficient on-policy covariance, showing that full-rank covariance is not necessary for pure exploitation to succeed.

When Can Pure Exploitation Succeed in Linear RL? Decoys and Self-Identifiability for Greedy LSVI

Abstract

BibTeX