# Multi-User Reinforcement Learning with Low Rank Rewards

arXiv: https://arxiv.org/abs/2210.05355 · HTML: https://mlsanity.com/paper/2210.05355/

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Distral: Robust Multitask Reinforcement Learning](https://mlsanity.com/paper/1707.04175/) (2017)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Multi-Task Reinforcement Learning with Context-based Representations](https://mlsanity.com/paper/2102.06177/) (2021)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Multi-task Deep Reinforcement Learning with PopArt](https://mlsanity.com/paper/1809.04474/) (2018)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Markov Decision Processes with Continuous Side Information](https://mlsanity.com/paper/1711.05726/) (2017)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)
- [Nearly Minimax Optimal Reward-free Reinforcement Learning](https://mlsanity.com/paper/2010.05901/) (2020)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering](https://mlsanity.com/paper/1711.02198/) (2017)
- [Recommendation System-based Upper Confidence Bound for Online Advertising](https://mlsanity.com/paper/1909.04190/) (2019)
- [Kullback-Leibler-Quadratic Optimal Control](https://mlsanity.com/paper/2004.01798/) (2020)
- [Regret in Online Recommendation Systems](https://mlsanity.com/paper/2010.12363/) (2020)
- [When Collaborative Filtering Meets Reinforcement Learning](https://mlsanity.com/paper/1902.00715/) (2019)

## Built on by (most cited first, 4 of 4)

- [The Bandit Whisperer: Communication Learning for Restless Bandits](https://mlsanity.com/paper/2408.05686/) (2024)
- [Provable Multi-Task Reinforcement Learning: A Representation Learning Framework with Low Rank Rewards](https://mlsanity.com/paper/2604.03891/) (2026)
- [Multi-Task Representation Learning for Conservative Linear Bandits](https://mlsanity.com/paper/2605.12176/) (2026)
- [Scalable Multi-Task Inverse Reinforcement Learning](https://mlsanity.com/paper/2610.00758/) (2026)

## 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.