What are good strategies for performing Gaussian process regression when the function I am trying to approximate changes over time? The naive approach that springs to my mind is to only use the N most recent data points to perform the regression. What are better strategies?
You could try this method:
We propose an active set selection framework for Gaussian process classification for cases when the dataset is large enough to render its inference prohibitive. Our scheme consists of a two step alternating procedure of active set update rules and hyperparameter optimization based upon marginal likelihood maximization. The active set update rules rely on the ability of the predictive distributions of a Gaussian process classifier to estimate the relative contribution of a datapoint when being either included or removed from the model.
If you want a fixed budget algorithm, see for e.g.,
M. Lázaro-Gredilla, S. Van Vaerenbergh and I. Santamaría, "A Bayesian Approach to Tracking with Kernel Recursive Least-Squares", IEEE International Workshop on Machine Learning for Signal Processing (MLSP 2011), Beijing, China, September, 2011.