我们开发了一个概率框架，用于分析基于模型的加强学习在整个概念环境中。然后，我们将其应用于使用线性动力学但未知的系数和凸起的有限时间地平线随机控制问题，但可能是不规则的，客观的函数。使用概率表示，我们研究相关成本函数的规律性，并建立精确估计，用于应用估计和真实模型参数的最佳反馈控制之间的性能差距。我们确定这种性能差距是二次，提高近期工作的线性性能差距的条件[X.郭，A. Hu和Y. Zhang，Arxiv预印，arxiv：2104.09311，（2021）]，它与随机线性二次问题获得的结果相匹配。接下来，我们提出了一种基于阶段的学习算法，我们展示了如何优化探索剥削权衡，并在高概率和期望中实现索布林遗憾。当对二次性能间隙保持所需的假设时，该算法在一般情况下实现了订单$ \ mathcal {o}（\ sqrt {n \ ln n）$高概率后悔，以及订单$ \ mathcal {o} （（\ ln n）^ 2）$预期遗憾，在自我探索案例中，超过$ n $剧集，匹配文献中的最佳结果。分析需要新的浓度不等式，用于相关的连续时间观察，我们得出。

这项工作使用熵调查的放松随机控制视角作为设计增强学习（RL）算法的原则框架。本代理通过根据最佳放松政策分配的嘈杂控制来与环境进行交互。一方面，嘈杂的政策探索了空间，因此有助于学习，但另一方面，通过为非最佳行为分配积极的可能性来引入偏见。这种探索解释权取舍取决于熵正规化的强度。我们研究了两种熵正则化公式产生的算法：探索性控制方法，其中熵被添加到成本目标以及近端政策更新方法中，熵惩罚了两个连续事件之间的策略差异。我们分析了有限的地平线连续时间线性季度（LQ）RL问题，这两种算法都产生了高斯轻松的策略。我们量化了高斯政策的价值函数与其嘈杂评估之间的确切差异，并表明执行噪声必须在整个时间内独立。通过调整轻松策略的采样频率和管理熵正则强度的参数，我们证明，对于两种学习算法而言，遗憾是$ \ MATHCAL {O}（\ sqrt {n}）的顺序（上升）超过$ n $插曲的对数因素），与文献相符。

我们研究有限的时间范围连续时间线性季节增强学习问题，在情节环境中，控制器的状态和控制系数都不清楚。我们首先提出了基于连续时间观察和控件的最小二乘算法，并建立对数的对数遗憾，以$ o（（\ ln m）（\ ln \ ln m））$，$ m $是数字学习情节。该分析由两个部分组成：扰动分析，这些分析利用了相关的riccati微分方程的规律性和鲁棒性；和参数估计误差，依赖于连续的最小二乘估计器的亚指数属性。我们进一步提出了一种基于离散时间观察和分段恒定控制的实际实现最小二乘算法，该算法根据算法中使用的时间步骤明确地取决于额外的术语，从而实现相似的对数后悔。

Despite its popularity in the reinforcement learning community, a provably convergent policy gradient method for continuous space-time control problems with nonlinear state dynamics has been elusive. This paper proposes proximal gradient algorithms for feedback controls of finite-time horizon stochastic control problems. The state dynamics are nonlinear diffusions with control-affine drift, and the cost functions are nonconvex in the state and nonsmooth in the control. The system noise can degenerate, which allows for deterministic control problems as special cases. We prove under suitable conditions that the algorithm converges linearly to a stationary point of the control problem, and is stable with respect to policy updates by approximate gradient steps. The convergence result justifies the recent reinforcement learning heuristics that adding entropy regularization or a fictitious discount factor to the optimization objective accelerates the convergence of policy gradient methods. The proof exploits careful regularity estimates of backward stochastic differential equations.

根据线性随机微分方程进化的扩散过程是连续时间动态决策模型的重要家族。最佳政策对它们进行了充分研究，并确定了漂移矩阵。然而，对于不确定的漂移矩阵的扩散过程的数据驱动的控制知之甚少，因为常规离散时间分析技术不适用。此外，尽管该任务可以被视为涉及探索和剥削权衡取舍的强化学习问题，但确保系统稳定性是设计最佳政策的基本组成部分。我们确定流行的汤普森采样算法可以快速学习最佳动作，仅产生了时间根的遗憾，并在短时间内稳定了系统。据我们所知，这是汤普森在扩散过程控制问题中抽样的第一个结果。我们通过从两个飞机和血糖控制的两个设置的实际参数矩阵的经验模拟来验证理论结果。此外，我们观察到，与最先进的算法相比，汤普森采样显着改善（最坏的）遗憾，这表明汤普森采样以一种更加保护的方式探索。我们的理论分析涉及特定的特定最优歧管，该歧管将漂移参数的局部几何形状与扩散过程的最佳控制。我们希望这项技术具有更广泛的兴趣。

我们研究了无限 - 马，连续状态和行动空间的政策梯度的全球融合以及熵登记的马尔可夫决策过程（MDPS）。我们考虑了在平均场状态下具有（单隐层）神经网络近似（一层）神经网络近似的策略。添加了相关的平均场概率度量中的其他熵正则化，并在2-Wasserstein度量中研究了相应的梯度流。我们表明，目标函数正在沿梯度流量增加。此外，我们证明，如果按平均场测量的正则化足够，则梯度流将成倍收敛到唯一的固定溶液，这是正则化MDP物镜的独特最大化器。最后，我们研究了相对于正则参数和初始条件，沿梯度流的值函数的灵敏度。我们的结果依赖于对非线性Fokker-Planck-Kolmogorov方程的仔细分析，并扩展了Mei等人的开拓性工作。 2020和Agarwal等。 2020年，量化表格环境中熵调控MDP的策略梯度的全局收敛速率。

我们将一般的多军匪徒问题视为一个相关（和简单的上下文和不安）元素，是一个放松的控制问题。通过引入熵正则化，我们获得了对值函数的平滑渐近近似。这产生了最佳决策过程的新型半指数近似。该半指数可以被解释为明确平衡探索 - 探索 - 探索权衡取舍，就像乐观的（UCB）原则中，学习溢价明确描述了环境中可用的信息的不对称性和奖励功能中的非线性。所得的渐近随机对照（ARC）算法的性能与其他相关的多臂匪徒的方法相比有利。

我们考虑使用时间差异学习算法进行连续时间过程的政策评估问题。更确切地说，从随机微分方程的时间离散化，我们打算使用TD（0）学习连续的值函数。首先，我们证明标准TD（0）算法注定要失败，因为动力学的随机部分由于时间步骤趋于零。然后，我们提出对时间差的添加零均值校正，使其相对于消失的时间步骤进行稳健。我们提出了两种算法：第一种算法是基于模型的，因为它需要了解动力学的漂移函数。第二个是无模型的。我们证明了基于模型的算法在两个不同的方案中的线性参数化假设下与连续时间解的收敛性：一个具有问题的凸正则化；第二次使用具有恒定步长且无正则化的Polyak-juditsy平均方法。在后一种方案中获得的收敛速率与最简单的使用随机梯度下降方法的线性回归问题相媲美。从完全不同的角度来看，我们的方法可以应用于使用机器学习以非发散形式求解二阶椭圆方程。

显示了最佳的收敛速率，显示了对保守随机偏微分方程的平均场限制对解决方案解决方案解决方案解决方案的收敛。作为第二个主要结果，该SPDE的定量中心极限定理再次得出，并以最佳的收敛速率得出。该结果尤其适用于在过叠层化的，浅的神经网络中与SPDES溶液中随机梯度下降动力学的平均场缩放率的收敛性。结果表明，在限制SPDE中包含波动可以提高收敛速度，并保留有关随机梯度下降的波动的信息。

我们考虑通过有限的地平线$ t $控制线性二次调节器（LQR）系统的问题，以固定和已知的成本矩阵$ q，r $但未知和非静止动力$ \ {a_t，b_t \} $。动态矩阵的序列可以是任意的，但总体变化，V_T $，假设为$ O（t）$和控制器未知。在假设所有$ $ $的稳定序列，但潜在的子最优控制器中，我们介绍了一种实现$ \ tilde {\ mathcal {o}} \ left的最佳动态遗憾的算法（v_t ^ { 2/5} t ^ {3/5} \右）$。通过分词恒定动态，我们的算法实现了$ \ tilde {\ mathcal {o}}（\ sqrt {st}）$的最佳遗憾，其中$ s $是交换机的数量。我们的算法的关键是一种自适应的非平稳性检测策略，它在最近开发的用于上下文多武装匪徒问题的方法中构建。我们还争辩说，不适应忘记（例如，重新启动或使用静态窗口大小的滑动窗口学习）可能对LQR问题的后悔最佳，即使窗口大小以$ V_T $的知识最佳地调整。我们算法分析中的主要技术挑战是证明普通的最小二乘（OLS）估计器在待估计的参数是非静止的情况下具有小的偏差。我们的分析还突出了推动遗憾的关键主题是LQR问题在于LQR问题是具有线性反馈和局部二次成本的强盗问题。这个主题比LQR问题本身更普及，因此我们相信我们的结果应该找到更广泛的应用。

汤普森采样（TS）是在不确定性下进行决策的有效方法，其中从精心规定的分布中采样了动作，该分布根据观察到的数据进行更新。在这项工作中，我们研究了使用TS的可稳定线性季度调节剂（LQR）自适应控制的问题，其中系统动力学是未知的。先前的作品已经确定，$ \ tilde o（\ sqrt {t}）$频繁的遗憾对于LQR的自适应控制是最佳的。但是，现有方法要么仅在限制性设置中起作用，需要先验已知的稳定控制器，要么使用计算上棘手的方法。我们提出了一种有效的TS算法，用于对LQR的自适应控制，TS基于TS的自适应控制，TSAC，该算法达到了$ \ tilde o（\ sqrt {t}）$遗憾，即使对于多维系统和Lazaric（2018）。 TSAC不需要先验已知的稳定控制器，并通过在早期阶段有效探索环境来实现基础系统的快速稳定。我们的结果取决于开发新颖的下限TS提供乐观样本的概率。通过仔细规定早期的探索策略和政策更新规则，我们表明TS在适应性控制多维可稳定性LQR方面实现了最佳的遗憾。我们从经验上证明了TSAC在几个自适应控制任务中的性能和效率。

这项工作研究了无处不在的强化学习政策的理论绩效保证，用于控制随机线性季节系统的规范模型。我们表明，随机确定性等效策略解决了探索 - 开发困境，以最大程度地减少根据随机微分方程进化的线性动力学系统中的二次成本。更确切地说，我们建立了时间段的正方形遗憾界限，表明随机确定性等效策略可以从单个状态轨迹中快速学习最佳控制动作。此外，显示了与参数数量的线性缩放。提出的分析介绍了新颖而有用的技术方法，并阐明了连续时间增强学习的基本挑战。

我们在$ \ Gamma $ -diScounted MDP中使用Polyak-Ruppert平均（A.K.A.，平均Q-Leaning）进行同步Q学习。我们为平均迭代$ \ bar {\ boldsymbol {q}}建立渐近常态。此外，我们展示$ \ bar {\ boldsymbol {q}} _ t $实际上是一个常规的渐近线性（RAL）估计值，用于最佳q-value函数$ \ boldsymbol {q} ^ * $与最有效的影响功能。它意味着平均Q学习迭代在所有RAL估算器之间具有最小的渐近方差。此外，我们为$ \ ell _ {\ infty} $错误$ \ mathbb {e} \ | \ | \ bar {\ boldsymbol {q}} _ t- \ boldsymbol {q} ^ *} ^ *} _ {\ idty} $，显示它与实例相关的下限以及最佳最低限度复杂性下限。作为一个副产品，我们发现Bellman噪音具有var-gaussian坐标，具有方差$ \ mathcal {o}（（1- \ gamma）^ {-1}）$而不是现行$ \ mathcal {o}（（1- \ Gamma）^ { - 2}）$根据标准界限奖励假设。子高斯结果有可能提高许多R1算法的样本复杂性。简而言之，我们的理论分析显示平均Q倾斜在统计上有效。

我们研究了随机近似程序，以便基于观察来自ergodic Markov链的长度$ n $的轨迹来求近求解$ d -dimension的线性固定点方程。我们首先表现出$ t _ {\ mathrm {mix}} \ tfrac {n}} \ tfrac {n}} \ tfrac {d}} \ tfrac {d} {n} $的非渐近性界限。$ t _ {\ mathrm {mix $是混合时间。然后，我们证明了一种在适当平均迭代序列上的非渐近实例依赖性，具有匹配局部渐近最小的限制的领先术语，包括对参数$的敏锐依赖（d，t _ {\ mathrm {mix}}） $以高阶术语。我们将这些上限与非渐近Minimax的下限补充，该下限是建立平均SA估计器的实例 - 最优性。我们通过Markov噪声的政策评估导出了这些结果的推导 - 覆盖了所有$ \ lambda \中的TD（$ \ lambda $）算法，以便[0,1）$ - 和线性自回归模型。我们的实例依赖性表征为HyperParameter调整的细粒度模型选择程序的设计开放了门（例如，在运行TD（$ \ Lambda $）算法时选择$ \ lambda $的值）。

我们证明了连续和离散时间添加功能的浓度不平等和相关的PAC界限，用于可能是多元，不可逆扩散过程的无界函数。我们的分析依赖于通过泊松方程的方法，使我们能够考虑一系列非常广泛的指数性千古过程。这些结果增加了现有的浓度不平等，用于扩散过程的加性功能，这些功能仅适用于有界函数或从明显较小的类别中的过程的无限函数。我们通过两个截然不同的区域的例子来证明这些指数不平等的力量。考虑到在稀疏性约束下可能具有高维参数非线性漂移模型，我们应用连续的时间浓度结果来验证套索估计的受限特征值条件，这对于甲骨文不平等的推导至关重要。离散添加功能的结果用于研究未经调整的Langevin MCMC算法，用于采样中等重尾密度$ \ pi $。特别是，我们为多项式增长功能$ f $的样品蒙特卡洛估计量$ \ pi（f）提供PAC边界，以量化足够的样本和阶梯尺寸，以在规定的边距内近似具有很高的可能性。

我们考虑使用$ K $臂的随机匪徒问题，每一个都与$ [m，m] $范围内支持的有限分布相关。我们不认为$ [m，m] $是已知的范围，并表明学习此范围有成本。确实，出现了与分销相关和无分配后悔界限之间的新权衡，这阻止了同时实现典型的$ \ ln t $和$ \ sqrt {t} $ bunds。例如，仅当与分布相关的遗憾界限至少属于$ \ sqrt {t} $的顺序时，才能实现$ \ sqrt {t} $}无分布遗憾。我们展示了一项策略，以实现新的权衡表明的遗憾。

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed.This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)-a classical algorithm frequently studied in the linear setting-achieves O( √ d 3 H 3 T ) regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions.

我们考虑在随机凸成本和状态和成本函数的全部反馈下控制未知线性动力学系统的问题。我们提出了一种计算高效的算法，该算法与最佳的稳定线性控制器相比，该算法达到了最佳的$ \ sqrt {t} $遗憾。与以前的工作相反，我们的算法基于面对不确定性范式的乐观情绪。这导致了大大改善的计算复杂性和更简单的分析。

Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and should not be used to distribute the papers in print or online or to submit the papers to another publication.

本文提供了强盗实验的决策理论分析。强盗设置对应于动态编程问题，但是直接解决这通常是不可行的。在扩散渐近框架内工作，我们定义了合适的渐近贝叶斯风险概念的强盗设置。对于正常分布的奖励，最小贝叶斯风险可以表征为非线性二阶偏微分方程（PDE）的解决方案。使用实验限制方法，我们表明，该PDE表征也在参数和非参数分布下呈渐近的奖励。该方法进一步描述了它渐近的状态变量足以限制注意力，因此表明了尺寸减少的实际策略。结果是我们可以近似使用PDE定义带状设置的动态编程问题，该PDE可以使用稀疏矩阵例程有效地解决。我们从这些方程中的数值解源于近最佳的政策。拟议的政策大大主导了现有的现有方法，如汤普森采样。该框架还允许对强盗问题进行大量概括，例如时间折扣和纯粹的探索动机。