Multi-User Reinforcement Learning with Low Rank Rewards
This addresses the problem of efficient learning in multi-agent systems for researchers and practitioners, offering a novel approach to reduce sample complexity, though it builds on standard low-rank assumptions from collaborative filtering.
The paper tackles collaborative multi-user reinforcement learning by assuming low-rank reward matrices, enabling algorithms with significantly lower sample complexity per user. The main result is an algorithm achieving exponential reduction in sample complexity, with per-MDP complexity scaling logarithmically with state-space size when user count is large and rank is constant.
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.