Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL

By Weitong Zhang, Jiafan He, Dongruo Zhou, Amy Zhang, Quanquan Gu. 2021

13 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Wen Sun
2. Xuezhou Zhang
3. Masatoshi Uehara
4. Nathan Kallus
5. Nan Jiang
6. Ofir Nachum
7. Ziyang Tang

In Electrical and Electronic Engineering

1. Wen Sun
2. Masatoshi Uehara

In Management Science and Operations Research

1. Wen Sun
2. Xuezhou Zhang
3. Masatoshi Uehara

Citations in the corpus

• Representation Learning for Online and Offline RL in Low-rank MDPs (2021, background): “Thus, our offline RL result generalizes prior offline RL works on linear MDPs (Jin et al., 2020b; Zhang et al., 2021) which assume representation is known a priori and use linear function approximation.”