Minimum variance controllers have been employed in a wide-range of industrial
applications. A key challenge experienced by many adaptive controllers is their
poor empirical performance in the initial stages of learning. In this paper, we
address the problem of initializing them so that they provide acceptable
transients, and also provide an accompanying finite-time regret analysis, for
adaptive minimum variance control of an auto-regressive system with exogenous
inputs (ARX). Following [3], we consider a modified version of the Certainty
Equivalence (CE) adaptive controller, which we call PIECE, that utilizes
probing inputs for exploration. We show that it has a $C \log T$ bound on the
regret after $T$ time-steps for bounded noise, and $C\log^2 T$ in the case of
sub-Gaussian noise. The simulation results demonstrate the advantage of PIECE
over the algorithm proposed in [3] as well as the standard Certainty
Equivalence controller especially in the initial learning phase. To the best of
our knowledge, this is the first work that provides finite-time regret bounds
for an adaptive minimum variance controller.

本文提出了一种使用探索输入的自适应最小方差控制算法 PIECE，该算法具有有限时间后的悔恨上限，并通过仿真实验证明了其在初始学习阶段具有比标准方法更优异的表现，这是首次针对最小方差控制器提出有限时间后悔上限的研究。

自回归系统外部输入下的最小方差控制的有限时间遗憾界

Finite Time Regret Bounds for Minimum Variance Control of Autoregressive  Systems with Exogenous Inputs

We consider the dynamics of a linear stochastic approximation algorithm
driven by Markovian noise, and derive finite-time bounds on the moments of the
error, i.e., deviation of the output of the algorithm from the equilibrium
point of an associated ordinary differential equation (ODE). We obtain
finite-time bounds on the mean-square error in the case of constant step-size
algorithms by considering the drift of an appropriately chosen Lyapunov
function. The Lyapunov function can be interpreted either in terms of Stein's
method to obtain bounds on steady-state performance or in terms of Lyapunov
stability theory for linear ODEs. We also provide a comprehensive treatment of
the moments of the square of the 2-norm of the approximation error. Our
analysis yields the following results: (i) for a given step-size, we show that
the lower-order moments can be made small as a function of the step-size and
can be upper-bounded by the moments of a Gaussian random variable; (ii) we show
that the higher-order moments beyond a threshold may be infinite in
steady-state; and (iii) we characterize the number of samples needed for the
finite-time bounds to be of the same order as the steady-state bounds. As a
by-product of our analysis, we also solve the open problem of obtaining
finite-time bounds for the performance of temporal difference learning
algorithms with linear function approximation and a constant step-size, without
requiring a projection step or an i.i.d. noise assumption.

考虑由 Markovian 噪声驱动的线性随机逼近算法的动态特性，通过考虑适当选择的 Lyapunov 函数的漂移，获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差 2 范数的平方的矩进行了全面的处理。

线性随机逼近和 TD 学习的有限时间误差界

Finite-Time Error Bounds For Linear Stochastic Approximation and TD  Learning

Recent studies on diffusion-based sampling methods have shown that Langevin
Monte Carlo (LMC) algorithms can be beneficial for non-convex optimization, and
rigorous theoretical guarantees have been proven for both asymptotic and
finite-time regimes. Algorithmically, LMC-based algorithms resemble the
well-known gradient descent (GD) algorithm, where the GD recursion is perturbed
by an additive Gaussian noise whose variance has a particular form. Fractional
Langevin Monte Carlo (FLMC) is a recently proposed extension of LMC, where the
Gaussian noise is replaced by a heavy-tailed {\alpha}-stable noise. As opposed
to its Gaussian counterpart, these heavy-tailed perturbations can incur large
jumps and it has been empirically demonstrated that the choice of
{\alpha}-stable noise can provide several advantages in modern machine learning
problems, both in optimization and sampling contexts. However, as opposed to
LMC, only asymptotic convergence properties of FLMC have been yet established.
In this study, we analyze the non-asymptotic behavior of FLMC for non-convex
optimization and prove finite-time bounds for its expected suboptimality. Our
results show that the weak-error of FLMC increases faster than LMC, which
suggests using smaller step-sizes in FLMC. We finally extend our results to the
case where the exact gradients are replaced by stochastic gradients and show
that similar results hold in this setting as well.

研究了 Langevin Monte Carlo 算法及其扩展 Fractional Langevin Monte Carlo 在非凸优化问题中的用法和收敛性，证明了 Fractional Langevin Monte Carlo 算法的有限时间界，得到了选择较小步长的建议。