Tensor Low-rank Approximation of Finite-horizon Value Functions
The goal of reinforcement learning is estimating a policy that maps states to actions and maximizes the cumulative reward of a Markov Decision Process (MDP). This is oftentimes achieved by estimating first the optimal (reward) value function (VF) associated with each state-action pair. When the MDP has an infinite horizon, the optimal VFs and policies are stationary under mild conditions. However, in finite-horizon MDPs, the VFs (hence, the policies) vary with time. This poses a challenge since the number of VFs to estimate grows not only with the size of the state-action space but also with the time horizon. This paper proposes a non-parametric low-rank stochastic algorithm to approximate the VFs of finite-horizon MDPs. First, we represent the (unknown) VFs as a multi-dimensional array, or tensor, where time is one of the dimensions. Then, we use rewards sampled from the MDP to estimate the optimal VFs. More precisely, we use the (truncated) PARAFAC decomposition to design an online low-rank algorithm that recovers the entries of the tensor of VFs. The size of the low-rank PARAFAC model grows additively with respect to each of its dimensions, rendering our approach efficient, as demonstrated via numerical experiments.
Code (1)
Similar Papers 제목 키워드 기반
Solving Finite-Horizon MDPs via Low-Rank Tensors
We study the problem of learning optimal policies in finite-horizon Markov Decision Processes (MDPs) using low-rank reinforcement learning (RL) methods. In finite-horizon MDPs, the policies, and therefore the value funct…
Reinforcement Learning (RL)tensorFM: Low-Rank Approximations of Cross-Order Feature Interactions
We address prediction problems on tabular categorical data, where each instance is defined by multiple categorical attributes, each taking values from a finite set. These attributes are often referred to as fields, and t…
Click-Through Rate PredictionDual-Channel Tensor Neural Networks: Finite-Sample Theory and Conformal Structure Selection
Tensor-valued data arise naturally in neuroimaging, genomics, climate science, and spatiotemporal networks, where multilinear dependencies across modes carry information that is destroyed under vectorization. Existing ap…
Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning (RL). When the state space is large or continuous, traditional tabular approaches are unfeasible and some form of function approxi…
Reinforcement LearningReinforcement Learning (RL)Nonnegative Low Rank Tensor Approximation and its Application to Multi-dimensional Images
The main aim of this paper is to develop a new algorithm for computing nonnegative low rank tensor approximation for nonnegative tensors that arise in many multi-dimensional imaging applications. Nonnegativity is one of …