Learning Good State and Action Representations via Tensor Decomposition

Abstract

The transition kernel of a continuous-state-action Markov decision process (MDP) admits a natural tensor structure. This paper proposes a tensor-inspired unsupervised learning method to identify meaningful low-dimensional state and action representations from empirical trajectories. The method exploits the MDP's tensor structure by kernelization, importance sampling and low-Tucker-rank approximation. This method can be further used to cluster states and actions respectively and find the best discrete MDP abstraction. We provide sharp statistical error bounds for tensor concentration and the preservation of diffusion distance after embedding. We further prove that the learned state/action abstractions provide accurate approximations to latent block structures if they exist, enabling function approximation in downstream tasks such as policy evaluation.

References in corpus (9)

• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Eigendecompositions of Transfer Operators in Reproducing Kernel Hilbert Spaces
• A statistical model for tensor PCA
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
• Learning low-dimensional state embeddings and metastable clusters from time series data
• Online Learning in Kernelized Markov Decision Processes

Cited by in corpus (2)

• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs