Multi-user Reinforcement Learning With Low Rank Rewards

Abstract

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-collabo

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyagarwal2022multi

Related papers

• Improved Sample Complexity For Reward-free Reinforcement Learning Under Low-rank Mdps (2023)0.00
• Provable Multi-task Reinforcement Learning: A Representation Learning Framework With Low Rank Rewards (2026)0.00
• Matrix Estimation For Offline Reinforcement Learning With Low-rank Structure (2023)0.00
• Model-free Representation Learning And Exploration In Low-rank Mdps (2021)0.00
• Exploiting Structure In Offline Multi-agent RL: The Benefits Of Low Interaction Rank (2024)0.00
• Model-free Low-rank Reinforcement Learning Via Leveraged Entry-wise Matrix Estimation (2024)0.00
• Provable Benefit Of Multitask Representation Learning In Reinforcement Learning (2022)0.00
• Provable Cooperative Multi-agent Exploration For Reward-free Mdps (2026)0.00