Planning over Matrix-Factorization MDPs Boosts Recommender Retrieval

Recommender systems typically retrieve candidates via static matrix-factorization scoring, treating each item independently and ignoring how a user's state evolves after each interaction. This paper challenges that assumption by modeling the entire recommendation chain as a Markov Decision Process (MDP) over the latent space. The authors use the posterior from implicit ALS as the state representation, define an action as selecting an item, and compute the next state using a rank-one fold-in update—a closed-form operation that keeps computation cheap. The reward combines relevance similarity with a posterior-alignment term, and they compare static retrieval, one-step planning, and horizon-K Monte Carlo tree search across five datasets under two evaluation protocols.

Results show that dynamics-aware planning consistently beats static retrieval on all datasets under the leave-last-n split, and gains hold on MovieLens-1M and VK-LSVD slices under a stricter global time split. Crucially, a single step of lookahead captures most of the improvement, making the approach lightweight—no retraining or representation changes are needed. The authors also find that cosine similarity (rather than inner product) is essential to avoid entanglement with item popularity. This work opens a practical path for enhancing any collaborative-filtering system with minimal overhead, turning static top-K scoring into a short decision process that accounts for user trajectory.