Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
The success of deep reinforcement learning (DRL) lies in its ability to learn a representation that is well-suited for the exploration and exploitation task. To understand how the choice of representation can improve the efficiency of reinforcement learning (RL), we study representation selection for a class of low-rank Markov Decision Processes (MDPs) where the transition kernel can be represented in a bilinear form. We propose an efficient algorithm, called ReLEX, for representation learning in both online and offline RL. Specifically, we show that the online version of ReLEX, called ReLEX-UCB, always performs no worse than the state-of-the-art algorithm without representation selection, and achieves a strictly better constant regret if the representation function class has a "coverage" property over the entire state-action space. For the offline counterpart, ReLEX-LCB, we show that the algorithm can find the optimal policy if the representation class can cover the state-action space and achieves gap-dependent sample complexity. This is the first result with constant sample complexity for representation learning in offline RL.
Code (0)
등록된 구현이 없습니다.
Tasks
Deep Reinforcement LearningOffline RLreinforcement-learningReinforcement LearningReinforcement Learning (RL)Representation LearningSimilar Papers 제목 키워드 기반
Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learning
In view of its power in extracting feature representation, contrastive self-supervised learning has been successfully integrated into the practice of (deep) reinforcement learning (RL), leading to efficient policy learni…
Contrastive LearningDeep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)+2Provably Efficient CVaR RL in Low-rank MDPs
We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize the Conditional Value at Risk (CVaR) with a fixed risk tolerance $\tau$. Prior theoretical work studying risk-sensitive RL focuses on the tabu…
Reinforcement Learning (RL)Representation LearningA Kernel Perspective on Behavioural Metrics for Markov Decision Processes
Behavioural metrics have been shown to be an effective mechanism for constructing representations in reinforcement learning. We present a novel perspective on behavioural metrics for Markov decision processes via the use…
reinforcement-learningReinforcement LearningEfficient Duple Perturbation Robustness in Low-rank MDPs
The pursuit of robustness has recently been a popular topic in reinforcement learning (RL) research, yet the existing methods generally suffer from efficiency issues that obstruct their real-world implementation. In this…
Reinforcement Learning (RL)Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP
In this paper, we study representation learning in partially observable Markov Decision Processes (POMDPs), where the agent learns a decoder function that maps a series of high-dimensional raw observations to a compact r…
DecoderEfficient ExplorationRepresentation Learning