  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.
