Model-based reinforcement learning (MBRL) is known to have better sample efficiency. However, acquiring an accurate world model is challenging due to the non-stationarity of data generated from agent interaction, which typically causes catastrophic interference for neural networks (NN). From the online learning perspective, a Follow-The-Leader (FTL) world model is desirable: a model that is optimal for all previous experiences. Unfortunately, for NN-based models, FTL means re-training the NN on all accumulated data at every interaction step, which is computationally expensive for lifelong agents. In this paper, we revisit models that can achieve FTL with efficient incremental updates. Specifically, our world model is a linear regression model supported by nonlinear random features. The linear part ensures efficient FTL update while the nonlinear random feature empowers the fitting of complex environments. To best trade off model capacity and computation efficiency, we introduce a locality sensitive encoding that is sparse in nature, which allows us to perform efficient online update even with very high dimensional nonlinear features. We present empirical results to validate the representation power of our encoding and verify that it is capable of learning incrementally under data covariate shift, a setting neural networks simply fail. Building on the demonstrated strength of our encoding, we further showcase its efficacy in MBRL settings, spanning both discrete and continuous control tasks. Our online world models, trained using a single pass of trajectory data, either surpass or match the capabilities of neural networks trained with replay and other continual learning methods.