We study methods based on reproducing kernel Hilbert spaces for estimating
the value function of an infinite-horizon discounted Markov reward process
(MRP). We study a regularized form of the kernel least-squares temporal
difference (LSTD) estimate; in the population limit of infinite data, it
corresponds to the fixed point of a projected Bellman operator defined by the
associated reproducing kernel Hilbert space. The estimator itself is obtained
by computing the projected fixed point induced by a regularized version of the
empirical operator; due to the underlying kernel structure, this reduces to
solving a linear system involving kernel matrices. We analyze the error of this
estimate in the $L^2(\mu)$-norm, where $\mu$ denotes the stationary
distribution of the underlying Markov chain. Our analysis imposes no
assumptions on the transition operator of the Markov chain, but rather only
conditions on the reward function and population-level kernel LSTD solutions.
We use empirical process theory techniques to derive a non-asymptotic upper
bound on the error with explicit dependence on the eigenvalues of the
associated kernel operator, as well as the instance-dependent variance of the
Bellman residual error. In addition, we prove minimax lower bounds over
sub-classes of MRPs, which shows that our rate is optimal in terms of the
sample size $n$ and the effective horizon $H = (1 - \gamma)^{-1}$. Whereas
existing worst-case theory predicts cubic scaling ($H^3$) in the effective
horizon, our theory reveals that there is in fact a much wider range of
scalings, depending on the kernel, the stationary distribution, and the
variance of the Bellman residual error. Notably, it is only parametric and
near-parametric problems that can ever achieve the worst-case cubic scaling.

本文提出一种基于重现核希尔伯特空间的方法来估算无限时间折扣马尔可夫奖励过程的值函数的方法，并使用经验过程理论技术导出了误差的上界，同时证明了在样本大小 n 和有效时间跨度 H = (1-gamma)^{-1} 方面具有最优的最小值。

基于核的时间差分方法的最优策略评估

Optimal policy evaluation using kernel-based temporal difference methods

We consider the problem of estimating the common mean of independently
sampled data, where samples are drawn in a possibly non-identical manner from
symmetric, unimodal distributions with a common mean. This generalizes the
setting of Gaussian mixture modeling, since the number of distinct mixture
components may diverge with the number of observations. We propose an estimator
that adapts to the level of heterogeneity in the data, achieving
near-optimality in both the i.i.d. setting and some heterogeneous settings,
where the fraction of ``low-noise'' points is as small as $\frac{\log n}{n}$.
Our estimator is a hybrid of the modal interval, shorth, and median estimators
from classical statistics; however, the key technical contributions rely on
novel empirical process theory results that we derive for independent but
non-i.i.d. data. In the multivariate setting, we generalize our theory to mean
estimation for mixtures of radially symmetric distributions, and derive minimax
lower bounds on the expected error of any estimator that is agnostic to the
scales of individual data points. Finally, we describe an extension of our
estimators applicable to linear regression. In the multivariate mean estimation
and regression settings, we present computationally feasible versions of our
estimators that run in time polynomial in the number of data points.

本研究考虑了独立采样数据的公共平均值估计问题，提出了一种估计器，它能够适应数据异质性的水平，在 i.i.d. 和某些非同质​​​​​​​的设置下均达到近似最优，其估计器既考虑了传统统计学中的模态区间、shorth、中位数估计器，又利用了新型经验过程理论结果，在多元估计和回归的情况下，我们提出了可在多项式时间内运行的估计器版本。

估计纠缠单样本分布中的位置参数

Estimating location parameters in entangled single-sample distributions

Suppose that we observe entries or, more generally, linear combinations of
entries of an unknown $m\times T$-matrix $A$ corrupted by noise. We are
particularly interested in the high-dimensional setting where the number $mT$
of unknown entries can be much larger than the sample size $N$. Motivated by
several applications, we consider estimation of matrix $A$ under the assumption
that it has small rank. This can be viewed as dimension reduction or sparsity
assumption. In order to shrink toward a low-rank representation, we investigate
penalized least squares estimators with a Schatten-$p$ quasi-norm penalty term,
$p\leq1$. We study these estimators under two possible assumptions---a modified
version of the restricted isometry condition and a uniform bound on the ratio
"empirical norm induced by the sampling operator/Frobenius norm." The main
results are stated as nonasymptotic upper bounds on the prediction risk and on
the Schatten-$q$ risk of the estimators, where $q\in[p,2]$. The rates that we
obtain for the prediction risk are of the form $rm/N$ (for $m=T$), up to
logarithmic factors, where $r$ is the rank of $A$. The particular examples of
multi-task learning and matrix completion are worked out in detail. The proofs
are based on tools from the theory of empirical processes. As a by-product, we
derive bounds for the $k$th entropy numbers of the quasi-convex Schatten class
embeddings $S_p^M\hookrightarrow S_2^M$, $p<1$, which are of independent
interest.

本文研究用惯性系数约束和 Frobenius 范数限制下的惩罚最小二乘估计的 Schatten-p 准范惩罚项估计法，能够有效地在高维数据下进行矩阵估计。