在本文中，我们研究了一个学习问题，其中预报师仅观察部分信息。通过适当地重新缩放问题，我们在瓦斯坦斯坦空间上启发了一个有限的PDE，它表征了预报员的遗憾的渐近行为。使用验证类型参数，我们表明，可以通过找到此抛物线PDE的合适的平滑子/超溶液来解决获得遗憾界限和有效算法的问题。
translated by 谷歌翻译
我们开发了一种新的方法来漂移游戏，一类两人游戏，其中包括许多应用程序来增强和在线学习设置，包括使用专家建议和对冲游戏的预测。我们的方法涉及（a）通过求解相关的部分微分方程（PDE）来猜测渐近的最佳潜力；然后（b）通过证明最终时间损失的上限和下限来证明猜测的合理性，它们的差异像个时间步数的负能力一样。我们潜在的基于上限的证据是基本的，只需使用泰勒的扩展。我们潜在的基于潜在的下限的证明也相当基本，将泰勒的扩展与概率或组合论证相结合。先前关于渐近最佳策略的大多数工作都使用了通过解决离散动态编程原理获得的潜力。这些论点因其离散性而变得复杂。我们使用的潜力是PDE的明确解决方案，这使我们的方法促进了我们的方法。这些论点基于基本的演算。我们的方法不仅更基本，而且还提供了新的电位，并得出相应的上和下限，这些上限和下限在渐近方面相互匹配。
translated by 谷歌翻译
这项工作介绍了两臂的伯努利强盗问题的版本，其中武器的平均值是一个（对称的两臂伯努利强盗）。在这些均值之间的差距为零的差距和预测期的次数接近无穷大的制度中，我们通过将它们与线性抛物线偏差的解决方案相关联，获得了预期的遗憾和伪造问题的领先顺序条款方程。我们的结果改善了先前已知的结果；具体而言，我们明确计算出最佳遗憾的主要顺序项和伪造的三种不同缩放制度。此外，我们在任何给定的时间范围内获得了新的非反应界限。
translated by 谷歌翻译
不受限制的在线线性优化（OLO）是研究机器学习模型培训的实用问题。现有作品提出了许多基于潜在的算法，但总的来说，这些潜在功能的设计在很大程度上取决于猜测。为了简化此工作流程，我们提出了一个框架，该框架通过求解部分微分方程（PDE）来生成新的潜在功能。具体来说，当损失是1-lipschitz时，我们的框架会产生一种新颖的算法，并随时随地遗憾绑定$ c \ sqrt {t}+|| || u || \ sqrt {2t} [\ sqrt {\ sqrt {\ log（1+|| |||/c）}+2] $，其中$ c $是用户指定的常数，$ u $是任何比较器未知和无限的先验者。这样的界限实现了最佳的损失重格折衷，而没有不切实际的tuble俩。此外，匹配的下限表明，包括常量乘数$ \ sqrt {2} $在内的领先订单项很紧。据我们所知，提出的算法是第一个实现此类最佳性的算法。
translated by 谷歌翻译
本文提供了强盗实验的决策理论分析。强盗设置对应于动态编程问题，但是直接解决这通常是不可行的。在扩散渐近框架内工作，我们定义了合适的渐近贝叶斯风险概念的强盗设置。对于正常分布的奖励，最小贝叶斯风险可以表征为非线性二阶偏微分方程（PDE）的解决方案。使用实验限制方法，我们表明，该PDE表征也在参数和非参数分布下呈渐近的奖励。该方法进一步描述了它渐近的状态变量足以限制注意力，因此表明了尺寸减少的实际策略。结果是我们可以近似使用PDE定义带状设置的动态编程问题，该PDE可以使用稀疏矩阵例程有效地解决。我们从这些方程中的数值解源于近最佳的政策。拟议的政策大大主导了现有的现有方法，如汤普森采样。该框架还允许对强盗问题进行大量概括，例如时间折扣和纯粹的探索动机。
translated by 谷歌翻译
由于Bellman〜\ Cite {Bellman1952theory}引起的向后感应方法是解决优化，最优控制和应用数学许多其他领域的问题的流行方法。在本文中，我们在最小/最大条件下分析了逆机诱导方法。我们表明，如果价值函数具有严格的顺序衍生物1-4，那么对手的最佳策略是布朗运动。使用该事实，我们分析了不同的潜在功能，并表明正常对冲潜力是最佳的。
translated by 谷歌翻译
我们将一般的多军匪徒问题视为一个相关（和简单的上下文和不安）元素，是一个放松的控制问题。通过引入熵正则化，我们获得了对值函数的平滑渐近近似。这产生了最佳决策过程的新型半指数近似。该半指数可以被解释为明确平衡探索 - 探索 - 探索权衡取舍，就像乐观的（UCB）原则中，学习溢价明确描述了环境中可用的信息的不对称性和奖励功能中的非线性。所得的渐近随机对照（ARC）算法的性能与其他相关的多臂匪徒的方法相比有利。
translated by 谷歌翻译
显示了最佳的收敛速率，显示了对保守随机偏微分方程的平均场限制对解决方案解决方案解决方案解决方案的收敛。作为第二个主要结果，该SPDE的定量中心极限定理再次得出，并以最佳的收敛速率得出。该结果尤其适用于在过叠层化的，浅的神经网络中与SPDES溶液中随机梯度下降动力学的平均场缩放率的收敛性。结果表明，在限制SPDE中包含波动可以提高收敛速度，并保留有关随机梯度下降的波动的信息。
translated by 谷歌翻译
我们开发了一个概率框架，用于分析基于模型的加强学习在整个概念环境中。然后，我们将其应用于使用线性动力学但未知的系数和凸起的有限时间地平线随机控制问题，但可能是不规则的，客观的函数。使用概率表示，我们研究相关成本函数的规律性，并建立精确估计，用于应用估计和真实模型参数的最佳反馈控制之间的性能差距。我们确定这种性能差距是二次，提高近期工作的线性性能差距的条件[X.郭，A. Hu和Y. Zhang，Arxiv预印，arxiv：2104.09311，（2021）]，它与随机线性二次问题获得的结果相匹配。接下来，我们提出了一种基于阶段的学习算法，我们展示了如何优化探索剥削权衡，并在高概率和期望中实现索布林遗憾。当对二次性能间隙保持所需的假设时，该算法在一般情况下实现了订单$ \ mathcal {o}（\ sqrt {n \ ln n）$高概率后悔，以及订单$ \ mathcal {o} （（\ ln n）^ 2）$预期遗憾，在自我探索案例中，超过$ n $剧集，匹配文献中的最佳结果。分析需要新的浓度不等式，用于相关的连续时间观察，我们得出。
translated by 谷歌翻译
We study the uniform-in-time propagation of chaos for mean field Langevin dynamics with convex mean field potenital. Convergences in both Wasserstein-$2$ distance and relative entropy are established. We do not require the mean field potenital functional to bear either small mean field interaction or displacement convexity, which are common constraints in the literature. In particular, it allows us to study the efficiency of the noisy gradient descent algorithm for training two-layer neural networks.
translated by 谷歌翻译
我们研究了无限 - 马，连续状态和行动空间的政策梯度的全球融合以及熵登记的马尔可夫决策过程（MDPS）。我们考虑了在平均场状态下具有（单隐层）神经网络近似（一层）神经网络近似的策略。添加了相关的平均场概率度量中的其他熵正则化，并在2-Wasserstein度量中研究了相应的梯度流。我们表明，目标函数正在沿梯度流量增加。此外，我们证明，如果按平均场测量的正则化足够，则梯度流将成倍收敛到唯一的固定溶液，这是正则化MDP物镜的独特最大化器。最后，我们研究了相对于正则参数和初始条件，沿梯度流的值函数的灵敏度。我们的结果依赖于对非线性Fokker-Planck-Kolmogorov方程的仔细分析，并扩展了Mei等人的开拓性工作。 2020和Agarwal等。 2020年，量化表格环境中熵调控MDP的策略梯度的全局收敛速率。
translated by 谷歌翻译
在线学习和决策中的一个核心问题 - 从土匪到强化学习 - 是要了解哪种建模假设会导致样本有效的学习保证。我们考虑了一个普遍的对抗性决策框架，该框架涵盖了（结构化的）匪徒问题，这些问题与对抗性动力学有关。我们的主要结果是通过新的上限和下限显示决策估计系数，这是Foster等人引入的复杂度度量。在与我们环境的随机对应物中，对于对抗性决策而言是必要和足够的遗憾。但是，与随机设置相比，必须将决策估计系数应用于所考虑的模型类（或假设）的凸壳。这就确定了容纳对抗奖励或动态的价格受凸层化模型类的行为的约束，并恢复了许多现有结果 - 既积极又负面。在获得这些保证的途径中，我们提供了新的结构结果，将决策估计系数与其他众所周知的复杂性度量的变体联系起来，包括Russo和Van Roy的信息比以及Lattimore和Gy的探索目标\“ {o} rgy。
translated by 谷歌翻译
当在未知约束集中任意变化的分布中生成数据时，我们会考虑使用专家建议的预测。这种半反向的设置包括（在极端）经典的I.I.D.设置时，当未知约束集限制为单身人士时，当约束集是所有分布的集合时，不受约束的对抗设置。对冲状态中，对冲算法（长期以来已知是最佳的最佳速率（速率））最近被证明是对I.I.D.的最佳最小值。数据。在这项工作中，我们建议放松I.I.D.通过在约束集的所有自然顺序上寻求适应性来假设。我们在各个级别的Minimax遗憾中提供匹配的上限和下限，表明确定性学习率的对冲在极端之外是次优的，并证明人们可以在各个级别的各个层面上都能适应Minimax的遗憾。我们使用以下规范化领导者（FTRL）框架实现了这种最佳适应性，并采用了一种新型的自适应正则化方案，该方案隐含地缩放为当前预测分布的熵的平方根，而不是初始预测分布的熵。最后，我们提供了新的技术工具来研究FTRL沿半逆转频谱的统计性能。
translated by 谷歌翻译
我们考虑使用$ K $臂的随机匪徒问题，每一个都与$ [m，m] $范围内支持的有限分布相关。我们不认为$ [m，m] $是已知的范围，并表明学习此范围有成本。确实，出现了与分销相关和无分配后悔界限之间的新权衡，这阻止了同时实现典型的$ \ ln t $和$ \ sqrt {t} $ bunds。例如，仅当与分布相关的遗憾界限至少属于$ \ sqrt {t} $的顺序时，才能实现$ \ sqrt {t} $}无分布遗憾。我们展示了一项策略，以实现新的权衡表明的遗憾。
translated by 谷歌翻译
当今许多大型系统的设计，从交通路由环境到智能电网，都依赖游戏理论平衡概念。但是，随着$ n $玩家游戏的大小通常会随着$ n $而成倍增长，标准游戏理论分析实际上是不可行的。最近的方法通过考虑平均场游戏，匿名$ n $玩家游戏的近似值，在这种限制中，玩家的数量是无限的，而人口的状态分布，而不是每个单独的球员的状态，是兴趣。然而，迄今为止研究最多的平均场平衡的平均场nash平衡的实际可计算性通常取决于有益的非一般结构特性，例如单调性或收缩性能，这是已知的算法收敛所必需的。在这项工作中，我们通过开发均值相关和与粗相关的平衡的概念来研究平均场比赛的替代途径。我们证明，可以使用三种经典算法在\ emph {ash All Games}中有效地学习它们，而无需对游戏结构进行任何其他假设。此外，我们在文献中已经建立了对应关系，从而获得了平均场 - $ n $玩家过渡的最佳范围，并经验证明了这些算法在简单游戏中的收敛性。
translated by 谷歌翻译
我们考虑激励探索：一种多臂匪徒的版本，其中武器的选择由自私者控制，而算法只能发布建议。该算法控制信息流，信息不对称可以激励代理探索。先前的工作达到了最佳的遗憾率，直到乘法因素，这些因素根据贝叶斯先验而变得很大，并在武器数量上成倍规模扩展。采样每只手臂的一个更基本的问题一旦遇到了类似的因素。我们专注于激励措施的价格：出于激励兼容的目的，绩效的损失，广泛解释为。我们证明，如果用足够多的数据点初始化，则标准的匪徒汤普森采样是激励兼容的。因此，当收集这些数据点时，由于激励措施的绩效损失仅限于初始回合。这个问题主要降低到样本复杂性的问题：需要多少个回合？我们解决了这个问题，提供了匹配的上限和下限，并在各种推论中实例化。通常，最佳样品复杂性在“信念强度”中的武器数量和指数中是多项式。
translated by 谷歌翻译
我们分析了一个随机近似算法的决策依赖性问题，其中算法沿迭代序列演变的数据分布。此类问题的主要示例出现在表演预测及其多人游戏扩展中。我们表明，在温和的假设下，算法的平均迭代和溶液之间的偏差在渐近正常上，协方差很好地解除了梯度噪声和分布移位的影响。此外，在H \'Ajek和Le Cam的工作中，我们表明该算法的渐近性能是本地最小的最佳选择。
translated by 谷歌翻译
在随机微分方程（SDE）的固定分布上进行优化在计算上具有挑战性。最近提出了一种新的远期传播算法，以在线优化SDE。该算法求解了使用正向分化得出的SDE，从而为梯度提供了随机估计。该算法连续更新SDE模型的参数和梯度估计值。本文研究了非线性耗散SDE的正向传播算法的收敛性。我们利用这类非线性SDE的怪异性来表征过渡半组及其衍生物的收敛速率。然后，我们证明了泊松部分微分方程（PDE）的求和，对于算法的随机波动的预期时间积分围绕最陡下降的方向而言。然后，我们使用PDE溶液重写算法，这使我们能够表征围绕最陡下降方向的参数演化。我们的主要结果是针对非线性耗散SDE的正向传播算法的收敛定理。
translated by 谷歌翻译
我们在随机多臂匪徒问题中使用固定预算和上下文（协变）信息研究最佳武器识别。在观察上下文信息之后，在每一轮中，我们使用过去的观察和当前上下文选择一个治疗臂。我们的目标是确定最好的治疗组，这是一个在上下文分布中被边缘化的最大预期奖励的治疗组，而错误识别的可能性最小。首先，我们为此问题得出半参数的下限，在这里我们将最佳和次优的治疗臂的预期奖励之间的差距视为感兴趣的参数，以及所有其他参数，例如在上下文中的预期奖励，作为滋扰参数。然后，我们开发“上下文RS-AIPW策略”，该策略由随机采样（RS）规则组成，跟踪目标分配比和使用增强反向概率加权（AIPW）估算器的建议规则。我们提出的上下文RS-AIPW策略是最佳的，因为错误识别概率的上限与预算到Infinity时的半参数下限相匹配，并且差距趋于零。
translated by 谷歌翻译
在一个拟合训练数据的深度神经网络（NN）中找到参数是一个非渗透优化问题，但基本的一阶优化方法（梯度下降）在许多实际情况下，具有完美拟合（零损失）的全局优化器。我们在限制性制度中检查残留神经网络（Reset）的剩余神经网络（Reset）的情况的这种现象，其中每个层（宽度）的层数（深度）和权重的数量均转到无穷大。首先，我们使用平均场限制参数来证明参数训练的梯度下降成为概率分布的梯度流，其特征在于大NN限制中的部分微分方程（PDE）。接下来，我们表明，在某些假设下，PDE的解决方案在训练时间内收敛到零损失解决方案。这些结果表明，如果Reset足够大，则reset的培训给出了近零损失。我们给出了减少给定阈值以下低于给定阈值的损失所需的深度和宽度的估计值。
translated by 谷歌翻译