TY - JOUR
T1 - Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space
AU - Long , Jihao
AU - Han , Jiequn
JO - Journal of Machine Learning
VL - 1
SP - 1
EP - 37
PY - 2022
DA - 2022/03
SN - 1
DO - http://doi.org/10.4208/jml.220114
UR - https://global-sci.org/intro/article_detail/jml/20370.html
KW - Reinforcement learning, Reproducing kernel Hilbert space, Perturbational complexity by distribution mismatch, High-dimensionality analysis.
AB - <p style="text-align: justify;">Most existing theoretical analysis of reinforcement learning (RL) is limited to the tabular setting or
linear models due to the difficulty in dealing with function approximation in high dimensional space with an
uncertain environment. This work offers a fresh perspective into this challenge by analyzing RL in a general
reproducing kernel Hilbert space (RKHS). We consider a family of Markov decision processes $\mathcal{M}$ of which the
reward functions lie in the unit ball of an RKHS and transition probabilities lie in a given arbitrary set. We
define a quantity called perturbational complexity by distribution mismatch $∆_{\mathcal{M}}(\epsilon)$ to characterize the complexity
of the admissible state-action distribution space in response to a perturbation in the RKHS with scale $\epsilon$. We
show that $∆_{\mathcal{M}}(\epsilon)$ gives both the lower bound of the error of all possible algorithms and the upper bound of
two specific algorithms (fitted reward and fitted $Q$-iteration) for the RL problem. Hence, the decay of $∆_{\mathcal{M}}(\epsilon)$ with respect to $\epsilon$ measures the difficulty of the RL problem on $\mathcal{M}.$ We further provide some concrete examples
and discuss whether $∆_{\mathcal{M}}(\epsilon)$ decays fast or not in these examples. As a byproduct, we show that when the
reward functions lie in a high dimensional RKHS, even if the transition probability is known and the action
space is finite, it is still possible for RL problems to suffer from the curse of dimensionality.</p>