Planning over Matrix-Factorization MDPs for Candidate Generation

Maksim Utushkin; Mikhail Trapeznikov

arxiv: 2607.02115 · v1 · pith:2UVG3EBAnew · submitted 2026-07-02 · 💻 cs.IR

Planning over Matrix-Factorization MDPs for Candidate Generation

Mikhail Trapeznikov , Maksim Utushkin This is my paper

Pith reviewed 2026-07-03 06:49 UTC · model grok-4.3

classification 💻 cs.IR

keywords matrix factorizationMDP planningrecommender systemscandidate generationfold-inMCTSimplicit ALS

0 comments

The pith

Casting top-K retrieval as an MDP over matrix-factorization posteriors lets planning outperform static scoring.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models customer journeys in recommenders as sequences where each item recommendation updates the user's state via fold-in. It casts static top-K as an MDP with closed-form transitions on the ALS posterior and a composite reward. Experiments compare static retrieval to one-step and multi-step planning across datasets and splits. Planning tends to improve results, with most gains from a single lookahead step, using the same fixed embeddings. This holds without retraining the model.

Core claim

Under fixed implicit-ALS embeddings, dynamics-aware planning over the MDP defined by rank-one fold-in transitions and a relevance-plus-alignment reward produces higher-quality recommendation trajectories than static top-K scoring on most datasets under leave-last-n splits and on some under global time splits.

What carries the argument

The MDP whose state is the implicit-ALS posterior pair (A^{-1}, u), whose actions are items, whose transitions are closed-form rank-one updates, and whose reward combines cosine relevance with a posterior-alignment term.

If this is right

A single step of lookahead already captures most of the performance gain from planning.
The improvement depends on using cosine similarity for relevance rather than inner-product.
Gains appear across five datasets under per-user leave-last-n protocol.
Some gains persist under the stricter global time split on MovieLens-1M and VK-LSVD.
The approach requires no retraining and works on top of fixed collaborative-filtering embeddings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the fold-in model accurately captures state changes, similar planning could extend to other latent factor models beyond ALS.
Testing whether the gains scale to longer horizons or different MCTS depths would clarify the value of multi-step planning.
The method might improve candidate generation in production systems where user state evolves rapidly.
Exploring alternative reward terms could isolate whether alignment or relevance drives the improvement.

Load-bearing premise

The closed-form rank-one fold-in transition together with the composite reward produce trajectories that can be fairly compared in quality to those from static top-K scoring.

What would settle it

An experiment showing that one-step or horizon-K planning yields no improvement or worse performance than static top-K under the same embeddings and protocols on the reported datasets.

Figures

Figures reproduced from arXiv: 2607.02115 by Maksim Utushkin, Mikhail Trapeznikov.

**Figure 2.** Figure 2: One MCTS iteration over the MF-MDP: selection by [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: A MovieLens example of the tree-search planner. The top row shows a user’s consumed history; the root is the [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

read the original abstract

For a recommender service, we view the customer journey as a chain of item recommendations: a useful item changes the user's state and therefore what should be retrieved next. Standard matrix-factorization retrieval ignores this -- it builds one user vector and returns the top-$K$ items by a static score, treating them as independent. We ask a narrow question: when is it worth planning over the user-state dynamics that fold-in induces? To answer it we propose casting top-$K$ retrieval as an MDP over the implicit-ALS posterior $(A^{-1},u)$, where an action is an item and the transition is a closed-form rank-one fold-in, and the trajectory reward combines a relevance similarity with a posterior-alignment term. Under the same fixed embeddings we compare static retrieval, one-step planning, and horizon-$K$ MCTS across five datasets and two protocols: a per-user leave-last-$n$ split and a stricter global time split. Dynamics-aware planning tends to overcome static retrieval on all datasets under leave-last-$n$, and the gains hold on MovieLens-1M and the VK-LSVD slices under the global time split. A single step of lookahead already captures most of the gain, so the lightweight planning layer turns static top-$K$ scoring into a short decision and improves retrieval over fixed collaborative-filtering embeddings, with no retraining and no change to the representation. These gains depend on measuring relevance with cosine rather than inner-product similarity, which is otherwise entangled with item popularity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean MDP reduction for fold-in dynamics in matrix factorization and shows one-step lookahead beats static top-K on multiple datasets, but the gains appear tied to switching the similarity measure to cosine plus a posterior term rather than to planning itself.

read the letter

The useful takeaway is that a single step of planning over the rank-one fold-in transition already captures most of the reported lift, and the gains survive the stricter global time split on MovieLens-1M and the VK slices. That is the concrete result worth noting.

The formulation itself is straightforward and exact: they keep the implicit-ALS posterior fixed, treat item selection as actions, and use the closed-form update for the next user vector. No approximation in the transition, which is a small but real technical point. Running both leave-last-n and global time splits on five datasets is also better than the usual single-protocol setup.

The soft spot is the reward and similarity choice. The abstract states that the improvements require cosine rather than inner product, and the reward includes an extra posterior-alignment term. Standard static top-K uses inner product on the same embeddings, so the comparison does not show whether a static retriever under the identical composite reward and cosine measure would close the gap. Without that control, it is hard to attribute the difference to the planning step versus the changed objective. No error bars or statistical tests are mentioned either, which keeps the empirical claims at the level of trends.

This is for people who already run matrix factorization at inference time and want a lightweight way to make the next recommendation depend on the previous one. A reader focused on production candidate generation will see a usable trick; someone looking for a broader advance in recommender dynamics will find the scope narrow. The work is coherent on its own terms and the experiments are not obviously post-hoc, so it deserves a serious referee even if the controls around the reward need tightening in revision.

Referee Report

2 major / 3 minor

Summary. The paper models top-K retrieval as an MDP over implicit-ALS posteriors (A^{-1}, u), with actions as items, closed-form rank-one fold-in transitions, and a composite reward (relevance similarity + posterior-alignment term). Under fixed embeddings it compares static top-K retrieval against one-step lookahead and horizon-K MCTS on five datasets under leave-last-n and global time splits, reporting that dynamics-aware planning improves retrieval (most gains from one step) when relevance is measured by cosine rather than inner product.

Significance. If the reported gains are attributable to the planning component rather than the altered reward definition, the work supplies a lightweight, training-free layer that converts static matrix-factorization scoring into short-horizon decision making. The exact closed-form transition is a technical strength that avoids sampling or approximation error in the dynamics.

major comments (2)

[Abstract, §4] Abstract and §4 (experimental setup): the central comparison is to standard static top-K, which the abstract states uses inner-product similarity; the MDP reward is composite and the paper states that gains require cosine similarity. No static baseline under the identical composite reward and cosine measure is reported, so it is not shown that the performance lift is due to planning over dynamics rather than the changed objective itself.
[§5] §5 (results): the claim that 'dynamics-aware planning tends to overcome static retrieval' is load-bearing for the contribution, yet the manuscript supplies no error bars, statistical significance tests, or hyperparameter sensitivity analysis for the posterior-alignment coefficient or the cosine scaling; without these the robustness of the cross-dataset and cross-protocol claims cannot be assessed.

minor comments (3)

[Abstract, §1] The abstract and introduction should explicitly state the precise static baseline (inner-product vs. cosine, single-term vs. composite reward) used in each table so that the attribution to planning is unambiguous.
[§3] Notation for the composite reward (relevance term + alignment term) and the precise definition of the posterior-alignment term should be given in a single displayed equation early in §3.
[Figures 1-3, Tables 1-4] Figure captions and table footnotes should report the number of random seeds or runs underlying each reported metric.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and constructive suggestions. We address each major comment below and will revise the manuscript accordingly to strengthen the claims.

read point-by-point responses

Referee: [Abstract, §4] Abstract and §4 (experimental setup): the central comparison is to standard static top-K, which the abstract states uses inner-product similarity; the MDP reward is composite and the paper states that gains require cosine similarity. No static baseline under the identical composite reward and cosine measure is reported, so it is not shown that the performance lift is due to planning over dynamics rather than the changed objective itself.

Authors: We agree that isolating the effect of planning requires a static baseline under the identical composite reward (cosine relevance + posterior-alignment term). The current experiments compare against standard inner-product top-K, which does not control for the reward change. In the revision we will add this controlled static baseline using the same composite objective and cosine measure to clarify the source of the reported gains. revision: yes
Referee: [§5] §5 (results): the claim that 'dynamics-aware planning tends to overcome static retrieval' is load-bearing for the contribution, yet the manuscript supplies no error bars, statistical significance tests, or hyperparameter sensitivity analysis for the posterior-alignment coefficient or the cosine scaling; without these the robustness of the cross-dataset and cross-protocol claims cannot be assessed.

Authors: We acknowledge that the absence of error bars, significance tests, and hyperparameter sensitivity limits assessment of robustness. We will add error bars (computed over multiple seeds or folds), paired statistical significance tests across datasets/protocols, and a sensitivity analysis for the posterior-alignment coefficient and cosine scaling (e.g., additional plots or tables) in the revised manuscript or appendix. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained empirical comparison

full rationale

The paper defines an MDP over implicit-ALS posteriors with an explicit closed-form rank-one fold-in transition and a stated composite reward (relevance similarity + posterior-alignment), then reports direct empirical comparisons of static top-K vs. one-step lookahead vs. MCTS under identical fixed embeddings. No equation reduces a claimed prediction to a fitted parameter defined by the same data, no self-citation chain supports a uniqueness claim, and no ansatz is smuggled via prior work. The modeling choices are declared up front and the evaluation uses external benchmarks (leave-last-n and global time splits on multiple datasets), satisfying the self-contained criterion.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim rests on the unstated assumption that the chosen reward and transition model are appropriate for user-state dynamics.

pith-pipeline@v0.9.1-grok · 5800 in / 1201 out tokens · 26389 ms · 2026-07-03T06:49:53.811193+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 3 internal anchors

[1]

Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. 2015. Deep Reinforcement Learning in Large Discrete Action Spaces.arXiv preprint arXiv:1512.07679(2015)

work page internal anchor Pith review Pith/arXiv arXiv 2015
[2]

Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. 2022. KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems. InProceedings of the 31st ACM International Conference on Information & Knowledge Management. 540–550

work page 2022
[3]

F Maxwell Harper and Joseph A Konstan. 2015. The MovieLens Datasets: History and Context.Acm transactions on interactive intelligent systems (tiis)5, 4 (2015), 1–19

work page 2015
[4]

Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk

work page
[5]

Session-based Recommendations with Recurrent Neural Networks.arXiv preprint arXiv:1511.06939

work page internal anchor Pith review Pith/arXiv arXiv
[6]

Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets. In2008 Eighth IEEE international conference on data mining. Ieee, 263–272

work page 2008
[7]

Eugene Ie, Vihan Jain, Jing Wang, Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Morgane Lustman, Vince Gatto, Paul Covington, et al. 2019. Reinforcement Learning for Slate-based Recommender Systems: A Tractable De- composition and Practical Methodology.arXiv preprint arXiv:1905.12767(2019)

work page internal anchor Pith review Pith/arXiv arXiv 2019
[8]

Wang-Cheng Kang and Julian McAuley. 2018. Self-Attentive Sequential Recom- mendation. In2018 IEEE international conference on data mining (ICDM). IEEE, 197–206

work page 2018
[9]

Levente Kocsis and Csaba Szepesvári. 2006. Bandit Based Monte-Carlo Planning. InEuropean conference on machine learning. Springer, 282–293

work page 2006
[10]

Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix Factorization Tech- niques for Recommender Systems.Computer42, 8 (2009), 30–37

work page 2009
[11]

Tze Leung Lai and Herbert Robbins. 1985. Asymptotically efficient adaptive allocation rules.Advances in applied mathematics6, 1 (1985), 4–22

work page 1985
[12]

Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A Contextual- Bandit Approach to Personalized News Article Recommendation. InProceedings of the 19th international conference on World wide web. 661–670

work page 2010
[13]

Alexander Ploshkin, Vladislav Tytskiy, Alexey Pismenny, Vladimir Baikalov, Evgeny Taychinov, Artem Permiakov, Daniil Burlakov, and Eugene Krofto. 2025. Yambda-5B—A Large-Scale Multi-Modal Dataset for Ranking and Retrieval. In Proceedings of the Nineteenth ACM Conference on Recommender Systems. 894–901

work page 2025
[14]

Aleksandr Poslavsky, Alexander D’yakonov, Yuriy Dorn, and Andrey Zimovnov

work page
[15]

8657–8660 pages

VK-LSVD: A Large-Scale Industrial Dataset for Short-Video Recommenda- tion. 8657–8660 pages

work page
[16]

Steffen Rendle, Walid Krichene, Li Zhang, and Yehuda Koren. 2022. Revisiting the Performance of iALS on Item Recommendation Benchmarks. InProceedings of the 16th ACM Conference on Recommender Systems. 427–435

work page 2022
[17]

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. 2020. Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model.Nature588, 7839 (2020), 604–609

work page 2020
[18]

Guy Shani, David Heckerman, and Ronen I Brafman. 2005. An MDP-based Recommender System.Journal of machine Learning research6, Sep (2005), 1265– 1295

work page 2005
[19]

Jack Sherman and Winifred J Morrison. 1950. Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix.The Annals of Mathematical Statistics21, 1 (1950), 124–127

work page 1950
[20]

Harald Steck. 2011. Item Popularity and Recommendation Accuracy. InProceed- ings of the fifth ACM conference on Recommender systems. 125–132

work page 2011
[21]

Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang

work page
[22]

InProceedings of the 28th ACM international conference on information and knowledge management

BERT4Rec: Sequential Recommendation with Bidirectional Encoder Rep- resentations from Transformer. InProceedings of the 28th ACM international conference on information and knowledge management. 1441–1450. A ALS Fold-in Update This appendix spells out the rank-one algebra used by the optimistic ALS transition. All vectors are column vectors. Proposition A...

work page 2026

[1] [1]

Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. 2015. Deep Reinforcement Learning in Large Discrete Action Spaces.arXiv preprint arXiv:1512.07679(2015)

work page internal anchor Pith review Pith/arXiv arXiv 2015

[2] [2]

Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. 2022. KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems. InProceedings of the 31st ACM International Conference on Information & Knowledge Management. 540–550

work page 2022

[3] [3]

F Maxwell Harper and Joseph A Konstan. 2015. The MovieLens Datasets: History and Context.Acm transactions on interactive intelligent systems (tiis)5, 4 (2015), 1–19

work page 2015

[4] [4]

Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk

work page

[5] [5]

Session-based Recommendations with Recurrent Neural Networks.arXiv preprint arXiv:1511.06939

work page internal anchor Pith review Pith/arXiv arXiv

[6] [6]

Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets. In2008 Eighth IEEE international conference on data mining. Ieee, 263–272

work page 2008

[7] [7]

Eugene Ie, Vihan Jain, Jing Wang, Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Morgane Lustman, Vince Gatto, Paul Covington, et al. 2019. Reinforcement Learning for Slate-based Recommender Systems: A Tractable De- composition and Practical Methodology.arXiv preprint arXiv:1905.12767(2019)

work page internal anchor Pith review Pith/arXiv arXiv 2019

[8] [8]

Wang-Cheng Kang and Julian McAuley. 2018. Self-Attentive Sequential Recom- mendation. In2018 IEEE international conference on data mining (ICDM). IEEE, 197–206

work page 2018

[9] [9]

Levente Kocsis and Csaba Szepesvári. 2006. Bandit Based Monte-Carlo Planning. InEuropean conference on machine learning. Springer, 282–293

work page 2006

[10] [10]

Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix Factorization Tech- niques for Recommender Systems.Computer42, 8 (2009), 30–37

work page 2009

[11] [11]

Tze Leung Lai and Herbert Robbins. 1985. Asymptotically efficient adaptive allocation rules.Advances in applied mathematics6, 1 (1985), 4–22

work page 1985

[12] [12]

Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A Contextual- Bandit Approach to Personalized News Article Recommendation. InProceedings of the 19th international conference on World wide web. 661–670

work page 2010

[13] [13]

Alexander Ploshkin, Vladislav Tytskiy, Alexey Pismenny, Vladimir Baikalov, Evgeny Taychinov, Artem Permiakov, Daniil Burlakov, and Eugene Krofto. 2025. Yambda-5B—A Large-Scale Multi-Modal Dataset for Ranking and Retrieval. In Proceedings of the Nineteenth ACM Conference on Recommender Systems. 894–901

work page 2025

[14] [14]

Aleksandr Poslavsky, Alexander D’yakonov, Yuriy Dorn, and Andrey Zimovnov

work page

[15] [15]

8657–8660 pages

VK-LSVD: A Large-Scale Industrial Dataset for Short-Video Recommenda- tion. 8657–8660 pages

work page

[16] [16]

Steffen Rendle, Walid Krichene, Li Zhang, and Yehuda Koren. 2022. Revisiting the Performance of iALS on Item Recommendation Benchmarks. InProceedings of the 16th ACM Conference on Recommender Systems. 427–435

work page 2022

[17] [17]

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. 2020. Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model.Nature588, 7839 (2020), 604–609

work page 2020

[18] [18]

Guy Shani, David Heckerman, and Ronen I Brafman. 2005. An MDP-based Recommender System.Journal of machine Learning research6, Sep (2005), 1265– 1295

work page 2005

[19] [19]

Jack Sherman and Winifred J Morrison. 1950. Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix.The Annals of Mathematical Statistics21, 1 (1950), 124–127

work page 1950

[20] [20]

Harald Steck. 2011. Item Popularity and Recommendation Accuracy. InProceed- ings of the fifth ACM conference on Recommender systems. 125–132

work page 2011

[21] [21]

Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang

work page

[22] [22]

InProceedings of the 28th ACM international conference on information and knowledge management

BERT4Rec: Sequential Recommendation with Bidirectional Encoder Rep- resentations from Transformer. InProceedings of the 28th ACM international conference on information and knowledge management. 1441–1450. A ALS Fold-in Update This appendix spells out the rank-one algebra used by the optimistic ALS transition. All vectors are column vectors. Proposition A...

work page 2026