Particle Thompson Sampling for online matrix factorization recommendation is described. In one or more implementations, a recommendation system provides a recommendation of an item to a user using Thompson Sampling. The recommendation system then receives a rating of the item from the user. Unlike conventional solutions which only update the user latent features, the recommendation system updates both user latent features and item latent features in a matrix factorization model based on the rating of the item. The updating is performed in real time which enables the recommendation system to quickly adapt to the user ratings to provide new recommendations. In one or more implementations, to update the user latent features and the item latent features in the matrix factorization model, the recommendation system utilizes a Rao-Blackwellized particle filter for online matrix factorization.