mlsanityData to 7 Oct 2026

Multi-User Reinforcement Learning with Low Rank Rewards

arXiv 2210.05355 ↗First posted 11 Oct 2022cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we consider the problem of collaborative multi-user reinforcement learning. In this setting there are multiple users with the same state-action space and transition probabilities but with different rewards. Under the assumption that the reward matrix of the N users has a low-rank structure -- a standard and practically successful assumption in the offline collaborative filtering setting -- the question is can we design algorithms with significantly lower sample complexity compared to the ones that learn the MDP individually for each user. Our main contribution is an algorithm which explores rewards collaboratively with N user-specific MDPs and can learn rewards efficiently in two key settings: tabular MDPs and linear MDPs. When N is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which represents an exponential reduction (in the state-space size) when compared to the standard ``non-collaborative'' algorithms.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 24 of its 53 references that are in the map. First posted on arXiv 11 Oct 2022.

Builds on

24 of 53 references.

References · 24

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Distral: Robust Multitask Reinforcement Learningcited by 231
  3. 2021Reinforcement learning based recommender systems: A surveycited by 187
  4. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  5. 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 169
  6. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  7. 2018Multi-task Deep Reinforcement Learning with PopArtcited by 138
  8. 2017Non-convex Optimization for Machine Learningcited by 132
  9. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  10. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  11. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  12. 2017Markov Decision Processes with Continuous Side Informationcited by 54
12 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  3. 2019Inference and Uncertainty Quantification for Noisy Matrix Completioncited by 39
  4. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  5. 2020Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimationcited by 25
  6. 2021Learning User Preferences in Non-Stationary Environmentscited by 10
  7. 2022Online Low Rank Matrix Completioncited by 9
  8. 2017Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filteringcited by 7
  9. 2019Recommendation System-based Upper Confidence Bound for Online Advertisingcited by 7
  10. 2020Kullback-Leibler-Quadratic Optimal Controlcited by 4
  11. 2020Regret in Online Recommendation Systemscited by 4
  12. 2019When Collaborative Filtering Meets Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 3.

4 papers.

  1. 2024The Bandit Whisperer: Communication Learning for Restless Banditscited by 5
  2. 2026Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewardscited by 1
  3. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0
  4. 2026Scalable Multi-Task Inverse Reinforcement Learningcited by 0