This work provides a Deep Reinforcement Learning approach to solving a periodic review inventory control system with stochastic vendor lead times, lost sales, correlated demand, and price matching. While this dynamic program has historically been considered intractable, our results show that several policy learning approaches are competitive with or outperform classical methods. In order to train these algorithms, we develop novel techniques to convert historical data into a simulator. On the theoretical side, we present learnability results on a subclass of inventory control problems, where we provide a provable reduction of the reinforcement learning problem to that of supervised learning. On the algorithmic side, we present a model-based reinforcement learning procedure (Direct Backprop) to solve the periodic review inventory control problem by constructing a differentiable simulator. Under a variety of metrics Direct Backprop outperforms model-free RL and newsvendor baselines, in both simulations and real-world deployments.

我们研究了协变量偏移下的线性回归，其中输入协变量的边际分布在源和目标域上有所不同，而在两个域中，给定输入协变量的输出的条件分布相似。我们根据针对此问题的目标数据（均由在线SGD进行的目标数据（均由在线SGD执行）进行预处理研究，研究了转移学习方法。我们为这种方法建立了尖锐的实例依赖性高风险上限和下限。我们的界限表明，对于大量的线性回归实例，使用$ O（n^2）$源数据（以及稀缺或无目标数据）转移学习与使用$ n $目标数据的监督学习一样有效。此外，我们表明，即使只有少量的目标数据，也可能会大大减少预处理所需的源数据量。我们的理论阐明了预处理的有效性和局限性以及对解决协变量转移问题的填补的好处。

互动学习和决策的基本挑战，从强盗问题到加固学习，是提供了实现的采样效率，自适应学习算法，实现了近乎最佳的遗憾。这个问题类似于最佳（监督）统计学习的经典问题，其中有众所周知的复杂性措施（例如，VC维度和Rademacher复杂性），用于控制学习的统计复杂性。然而，由于问题的适应性，表征交互式学习的统计复杂性基本上更具挑战性。这项工作的主要结果提供了复杂性措施，决策系数，被证明是必要的，并且足以用于采样有效的互动学习。特别是，我们提供：1。对于任何交互式决策问题的最佳遗憾的下限，将决策估计系数作为基本限制建立。 2.统一算法设计原理，估算到决策（E2D），它将任何用于监督估算的算法转换为决策的在线算法。 E2D遗憾的是符合我们下限的遗憾，从而实现了最佳的样本高效学习，其特征在于决策估计系数。一起参加，这些结果构成了互动决策的可读性理论。当应用于增强学习设置时，决策估计系数基本上恢复所有现有的硬度结果和下限。更广泛地，该方法可以被视为统计估算的经典LE CAM理论的决策理论;它还统一了许多现有方法 - 贝叶斯和频繁的方法。

随机梯度下降（SGD）已被证明在许多深度学习应用中都很好地概括了。在实践中，人们经常以几何衰减的步骤运行SGD，即，恒定的初始步骤，然后是多个几何步骤衰减，并将最后一个迭代用作输出。已知这种SGD几乎对经典有限维线性回归问题几乎是最佳的（Ge等，2019）。但是，在过度参数化设置中对SGD的最后一次迭代进行了彻底的分析。在本文中，我们对SGD的最后一个迭代风险界限进行了依赖问题的分析，并具有腐烂的步骤，以（过度参数化）线性回归问题。特别是，对于带有（尾部）几何衰减步骤的最后迭代SGD，我们证明了多余风险的上限和下限几乎匹配。此外，我们为最后一次迭代的SGD提供了多余的风险下限，并以多项式衰减的步骤进行了大小，并以实例的方式证明了几何腐烂的步骤的优势，这补充了先前工作中的最小值比较。

随机梯度下降（SGD）在实践中表现出强烈的算法正则化效应，该效果已被认为在现代机器学习方法的概括中起着重要作用。在这项工作中，我们试图在线性回归的更简单环境（包括量身范围的和过度参数化的制度）中理解这些问题，在此，我们的目标是对（未注册）平均SGD与（未注册的）平均SGD进行基于实例的敏锐比较。脊回归的明确正规化。对于一系列最小二乘问题的问题实例（在高维设置中是自然的），我们显示：（1）对于每个问题实例和每个脊参数（未注册）SGD，当时提供比对数的样本比提供的样本更多的样本时对于脊算法，概括的概括不及脊解决方案（提供SGD使用调谐常数步骤）； （2）相反，存在（在这个宽阔的问题类中），其中最佳调整的脊回归需要比SGD更高的样本以具有相同的概括性能。综上所述，我们的结果表明，在对数因素上，SGD的概括性能总是不到脊回归的差异，而在各种过度参数的问题中，对于某些问题实例，实际上可能会更好。更普遍地，我们的结果表明，即使在更简单（过度参数化）凸设置中，算法正则化如何产生重要的后果。

深度加强学习（RL）由Q函数的神经网络近似，具有巨大的经验成功。虽然RL的理论传统上专注于线性函数近似（或雕刻尺寸）方法，但是关于非线性RL的近似已知Q功能的神经网络近似。这是这项工作的重点，在那里我们研究了与双层神经网络的函数逼近（考虑到Relu和多项式激活功能）。我们的第一个结果是在两层神经网络的完整性下的生成模型设置中的计算上和统计学高效的算法。我们的第二个结果考虑了这个设置，而是通过神经网络函数类的可实现性。这里，假设确定性动态，样本复杂度在代数维度中线性缩放。在所有情况下，我们的结果显着改善了线性（或雕刻尺寸）方法可以获得的。

This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the wellknown convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free.Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.

This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models-including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation-which exploits a certain tensor structure in their low-order observable moments (typically, of second-and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models.

Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze GP-UCB, an intuitive upper-confidence based algorithm, and bound its cumulative regret in terms of maximal information gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.

神经网络（NNS）也很难有效地学习某些问题，例如奇偶校验问题，即使对于这些问题有简单的学习算法。NNS可以自己发现学习算法吗？我们展示了一个NN体系结构，在多项式时期，可以通过恒定尺寸的学习算法来学习以及任何有效的学习算法。例如，在奇偶校验问题上，NN学习和减少行，这是一种可以简单描述的有效算法。我们的体系结构结合了层和卷积重量共享之间的重复分享，即使网络本身可能具有数万亿个节点，也将参数数量降低到常数。在实践中，我们的分析中的常数太大而无法直接有意义，但我们的工作表明，经常性和卷积NNS（RCNN）的协同作用可能比单独的任何一个更强大。