Low-rank State-action Value-function Approximation

2021/04/18 by Rozada, Sergio, Tenorio, Victor, Marques, Antonio G. · 1 citation
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2104.08805

Abstract

Value functions are central to Dynamic Programming and Reinforcement Learning but their exact estimation suffers from the curse of dimensionality, challenging the development of practical value-function (VF) estimation algorithms. Several approaches have been proposed to overcome this issue, from non-parametric schemes that aggregate states or actions to parametric approximations of state and action VFs via, e.g., linear estimators or deep neural networks. Relevantly, several high-dimensional state problems can be well-approximated by an intrinsic low-rank structure. Motivated by this and leveraging results from low-rank optimization, this paper proposes different stochastic algorithms to estimate a low-rank factorization of the Q(s, a) matrix. This is a non-parametric alternative to VF approximation that dramatically reduces the computational and sample complexities relative to classical Q-learning methods that estimate Q(s,a) separately for each state-action pair.

Cited by

• ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty

Related

• Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning
• Uncertainty-aware Low-Rank Q-Matrix Estimation for Deep Reinforcement Learning
• Harnessing Structures for Value-Based Planning and Reinforcement Learning
• Matrix Low-Rank Approximation For Policy Gradient Methods
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation